Jump to content
Sign in to follow this  
devnullprod

Question pertaining to hashing / database lookups

Recommended Posts

Posted (edited)

Happy Saturday everyone! While looking to further our understanding of persistent ledger storage, we're spinning our wheels with figuring out how STLedger entry instances and SHAMap tree nodes are mapped together. I figured I'd open up the line of inquiry here, with the hopes that those more in the know can help us out.

So as previously explored in our analysis, we can see how transactions modify STLedgerEntry's (SLE's) locally stored in view instances (eg the RawStateTable and ApplyStateTable members of the OpenView and ApplyView classes respectively). The first thing that is unclear to us after this is how these SLEs stored here are persisted to the NodeStore Database. In src/rippled/app/ledger/impl/BuildLedger.cpp we first see the call to applyTxs, applying the txs to the OpenView (as described above) and then the calls to the flushDirty method on the two internal nodestore databases (the stateMap and the txMap). Through a series of dispatch calls flushDirty persists the local nodes to the db (flushDirty -> walkSubTree -> writeNode -> db.store)

What is missing is how the object in the view state tables are copied to nodes in the in memory SHAMap before they are persisted. Are we missing something that is happening between these calls?

---

The second part of this comes from trying to read ledger data from the local on-disk database directly. Our understanding is that rocksdb is the default storage system used to track persistent ledger data locally. To test this we attempted to write a script that used the rocksdb api to load an account object from the db but were unable to do so. To start off we take an account and convert it from it's Base58 representation to an int:

 

acct = 'rvYAfWj5gh67oV6fW32ZzP3Aw4Eubs59B'
acct = Base58.base58_to_int(acct, :ripple)

> 248331542315593529806310541400981408142246584199390275214

 

Next we split the account into bytes:

bytes = []
while acct != 0
  bytes << (acct & 255)
  acct = acct >> 8
end
bytes.reverse!

> [10, 32, 179, 200, 95, 72, 37, 50, 169, 87, 141, 187, 57, 80, 184, 92, 160, 101, 148, 209, 57, 89, 166, 142]

 

Since this account is only 24 bytes long we need to pad it with 8 leading zeros to make it 32 (32 bytes = 256bits = sizeof(uint256), rippled's internal representation of keys). We can then pack this into a byte string able to be passed to OpenSSL::Digest::SHA512#digest

 

bytes = ([0] * (32 - bytes.size) + bytes)

> [0, 0, 0, 0, 0, 0, 0, 0, 10, 32, 179, 200, 95, 72, 37, 50, 169, 87, 141, 187, 57, 80, 184, 92, 160, 101, 148, 209, 57, 89, 166, 142]

acct = bytes.pack("C*")

> "\x00\x00\x00\x00\x00\x00\x00\x00\n \xB3\xC8_H%2\xA9W\x8D\xBB9P\xB8\\\xA0e\x94\xD19Y\xA6\x8E"

 

Before passing the account ID though, we need to prefix it with the proper space key. In this case we use 'a' for an account.

 

sha512 = OpenSSL::Digest::SHA512.new
sha512.update 'a' 
sha512.update acct
hash = sha512.digest

> "\xC1I\xC5\x1A\xAA'\xCA\xB0^4{l9\rf\xA5e\x88\xCCs\x9Dp\xFD\xB3q\x90\x8Do6.\x87\x8D\xFFprp\xBA\xC9\xC6\x98A\x95\xDF\x89\xF3\xEAWl\xD6*Lkq\xA6\x84J\xD1h\x8BR\xCD\xAEq?"

 

rippled uses SHA512Half, so we only use the first 32 bytes of this hash (256 bits). Finally we pass this into the rocksdb lookup:

rocksdb = RocksDB::DB.new "/var/lib/rippled/db/rocksdb/rippledb.0899", {:readonly => true}
rocksdb[hash]

> nil

 

After all this we'd expect to retrieve the account corresponding to the id from the db but as you see above we're only getting nil. Any insights? Are we not understanding the algorithm or did we misapply it?

 

Much appreciated!

 

 

Edited by devnullprod

Share this post


Link to post
Share on other sites

 

19 hours ago, Sukrim said:

The clearest explanation I've found for the different formats is https://github.com/rubblelabs/ripple/blob/master/data/doc.go

Cool, thanks for the link @Sukrim. Not only will it be useful to further our understanding of the protocol but it will be a useful resource for us get better at Go!

 

19 hours ago, Sukrim said:

No, you can not just hash an address and pull out an account from the node database.

I figured, just wanted to try something easy incase it worked. I also tried pulling the ledger out of the DB directly but that didn't work either:

ledger = "26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D"
ledger = [ledger].pack("H*") # convert hex ledger to binary string

rocksdb = RocksDB::DB.new "/var/lib/rippled/db/rocksdb/rippledb.0899", {:readonly => true}
puts "DB: #{rocksdb[ledger]}"

 

I'm planning on keeping poking around with the source, hopefully between the ripple-labs and rubblelabs rippled projects it will become apparent how the SLEs are persisted to the DB and how they can read directly from there. Will update this thread when we have results!

 

Share this post


Link to post
Share on other sites

Are you sure that this ledger is in your database and that this is the correct way to get data from a RocksDB database? I personally use NuDB and generally write Python, so I can't help much with your code snippet without context up there, but in general you should be able to get a blob of data if querying for the ledger hash as key.

Code for rippled should be probably in https://github.com/ripple/rippled/tree/develop/src/ripple/nodestore

Share this post


Link to post
Share on other sites
58 minutes ago, Sukrim said:

Are you sure that this ledger is in your database and that this is the correct way to get data from a RocksDB database?

Yes

 

58 minutes ago, Sukrim said:

I personally use NuDB and generally write Python, so I can't help much with your code snippet without context up there, but in general you should be able to get a blob of data if querying for the ledger hash as key.

Do you happen to have an example of reading a ledger and/or account with the specified hex hash from the NuDB db directly (python is OK, we're quite familiar w/ that as well). Correct me if I'm wrong, but I think it would be reasonable to assume the keys/values would be the same regardless of which db backend you use.

 

 

58 minutes ago, Sukrim said:

Yes, though there are many constructs that are spread out amongst other directories (including src/ripple/ledger, src/ripple/app, + more). There's alot of code to go through!

Share this post


Link to post
Share on other sites
Posted (edited)
1 hour ago, devnullprod said:

Do you happen to have an example of reading a ledger and/or account with the specified hex hash from the NuDB db directly (python is OK, we're quite familiar w/ that as well). Correct me if I'm wrong, but I think it would be reasonable to assume the keys/values would be the same regardless of which db backend you use.

I re-wrote parts of NuDB I needed in Python, though I still need to fix that stuff up to actually publish it. There's also no real demand for that stuff anyways. "nudb.fetch(query_hash.to_bytes(32, byteorder="big")" is probably not really helpful if you don't have the implementation behind that... ;-)

Maybe you have issues with the correct byte order in your hash (it has to be big endian)?

Yes, keys/values should be the same no matter the backend, though values can be compressed in several different formats (https://github.com/ripple/rippled/blob/develop/src/ripple/nodestore/impl/codec.h) so don't expect raw values to be the same across servers/databases.

According to the following query (https://developers.ripple.com/websocket-api-tool.html#ledger):

{
  "command": "ledger",
  "ledger_hash": "26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D",
  "binary": true
}

You should get the following value for the key "26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D" (maybe after decompression):

02C612E501633DDECCEF1A6BD5AB292ED5C988A58F71909262FE055F30830832F3C4305D5AC44A2AD5251667FB0C7D64D4735958B34400D15C599D073E007B4F7D06F309F1559C91C73284D054AC346E5A094B24311CD2BBF9AEB72C5F819D0A99AE9F8BC8B1ACCA61CC6B7024462AC124462AC20A00

Full answer:

{
  "id": 1,
  "status": "success",
  "type": "response",
  "result": {
    "ledger": {
      "closed": true,
      "ledger_data": "02C612E501633DDECCEF1A6BD5AB292ED5C988A58F71909262FE055F30830832F3C4305D5AC44A2AD5251667FB0C7D64D4735958B34400D15C599D073E007B4F7D06F309F1559C91C73284D054AC346E5A094B24311CD2BBF9AEB72C5F819D0A99AE9F8BC8B1ACCA61CC6B7024462AC124462AC20A00"
    },
    "ledger_hash": "26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D",
    "ledger_index": 46535397,
    "validated": true
  }
}

 

Edited by Sukrim

Share this post


Link to post
Share on other sites
Posted (edited)
On 4/14/2019 at 4:17 PM, Sukrim said:

I re-wrote parts of NuDB I needed in Python, though I still need to fix that stuff up to actually publish it. There's also no real demand for that stuff anyways. "nudb.fetch(query_hash.to_bytes(32, byteorder="big")" is probably not really helpful if you don't have the implementation behind that... ;-)

Maybe you have issues with the correct byte order in your hash (it has to be big endian)?

Yes, keys/values should be the same no matter the backend, though values can be compressed in several different formats (https://github.com/ripple/rippled/blob/develop/src/ripple/nodestore/impl/codec.h) so don't expect raw values to be the same across servers/databases.

 

 

Again thanks for the response @Sukrim. Yes I'm sure the byte order is in big endian, to confirm the following is the array of bytes extracted from the ledger hash above:

[38 112 107 20 211 112 230 157 225 243 167 237 105 114 202 188 143 210 73 211 235 85 81 1 120 164 246 118 95 88 230 157]

 

We also just wrote a quick C++ app to try and do this but still no luck:

 

#include <iostream>
#include "rocksdb/db.h"

int char2int(char input)
{
  if(input >= '0' && input <= '9')
    return input - '0';
  if(input >= 'A' && input <= 'F')
    return input - 'A' + 10;
  if(input >= 'a' && input <= 'f')
    return input - 'a' + 10;
  throw std::invalid_argument("Invalid input string");
}

void hex2bin(const char* src, char* target)
{
  while(*src && src[1])
  {
    int v = (char2int(*src)*16 + char2int(src[1]));
    *(target++) = v;
    src += 2;
  }
}

int main(void){
  char key[32];
  hex2bin("26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D", key);
  std::string k(key);

  std::cout << "Key1: ";
  for(int i = 0; i < 32; ++i)
    std::cout << (key[i] > 0 ? (int)key[i] : 256 + key[i]) << " ";
  std::cout << std::endl;
  std::cout << "Key2: " <<   k << std::endl;

  ///

  rocksdb::DB* db;
  rocksdb::Options options;
  rocksdb::Status status =
    rocksdb::DB::OpenForReadOnly(options, "/var/lib/rippled/db/rocksdb/rippledb.0899", &db);
  if (!status.ok()){
    std::cerr << status.ToString() << std::endl;
    return 1;
  }

  std::string value;
  rocksdb::Status s = db->Get(rocksdb::ReadOptions(), k, &value);

  std::cout << "Value: " << value << std::endl;
  return 0;
}

 

Output:

 

Key1: 38 112 107 20 211 112 230 157 225 243 167 237 105 114 202 188 143 210 73 211 235 85 81 1 120 164 246 118 95 88 230 157 
Key2: &pk�p������irʼ��I��UQx��v_X��
Value: 

 

Continuing to dive into the code...

Edited by devnullprod

Share this post


Link to post
Share on other sites

I don't have the answers here, but if you're trying to look up an AccountRoot object, be sure you include the space key 0x0061 before hashing. (See AccountRoot ID Format and the corresponding pages for other object types. The Hash Prefixes table may also be useful for figuring out other hashes, though if you have the hash itself, that already takes it into account.)

Share this post


Link to post
Share on other sites
Posted (edited)
25 minutes ago, mDuo13 said:

I don't have the answers here, but if you're trying to look up an AccountRoot object, be sure you include the space key 0x0061 before hashing. (See AccountRoot ID Format and the corresponding pages for other object types. The Hash Prefixes table may also be useful for figuring out other hashes, though if you have the hash itself, that already takes it into account.)

Not in the node database. How should that even work, there are sometimes thousands of different versions of the same addresses' AccountRoot object in there (just think what the XRP balance of an account should be that you look up from the database). He needs the 0x4D4C4E00 prefix, the full encoded specific AccountRoot object and the (Index) hash you mention to actually get an instance of an AccountRoot object from the node store.

(and I know that this is a bit weird that you need the full object to even get the hash to look up the full object... that's why you have the SHAmap trie to break this circle - but to descend a SHAmap via the index hash you mentioned, you need its root node and the hash of that one is in a ledger header)

Edited by Sukrim

Share this post


Link to post
Share on other sites
46 minutes ago, Sukrim said:

Not in the node database. How should that even work, there are sometimes thousands of different versions of the same addresses' AccountRoot object in there (just think what the XRP balance of an account should be that you look up from the database). He needs the 0x4D4C4E00 prefix, the full encoded specific AccountRoot object and the (Index) hash you mention to actually get an instance of an AccountRoot object from the node store.

(and I know that this is a bit weird that you need the full object to even get the hash to look up the full object... that's why you have the SHAmap trie to break this circle - but to descend a SHAmap via the index hash you mentioned, you need its root node and the hash of that one is in a ledger header)

Understood, though in the case of ledgers, a direct lookup based on hash should work should it not? (would anyone be able to try the C++ example I gave? you can compile it with g++ rocksdb.cpp -lrocksdb)

I seem to have traced the entire path, the call that I was missing was literally between applyTxs and the calls to flushDirty, specifically the call to OpenView#apply passing the new Ledger instance created a few lines above results in the SHAMaps being modified (OpenView#apply -> RawStateTable#apply -> Ledger#rawErase|rawInsert|rawUpdate  and  OpenView#apply -> Ledger#rawTxInsert  with Serializer actually serializing the SLEs to NodeStore Object data)

Still trying to figure out the manual db lookup though...

 

Share this post


Link to post
Share on other sites
Posted (edited)
18 hours ago, Sukrim said:

It should.

Instead of writing code yourself, maybe you can try the ldb tool? https://github.com/facebook/rocksdb/wiki/Administration-and-Data-Access-Tool

OK, after quite a bit of fiddling around with it, we got it working first with the ldb tool and then in C++:

 

$ ldb --db=/var/lib/rippled/db/rocksdb/rippledb.0899 --try_load_options --ignore_unknown_options --hex get 0x26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D

> wal_dir loaded from the option file doesn't exist. Ignore it.
0x0000000000000000014C57520002C612E501633DDECCEF1A6BD5AB292ED5C988A58F71909262FE055F30830832F3C4305D5AC44A2AD5251667FB0C7D64D4735958B34400D15C599D073E007B4F7D06F309F1559C91C73284D054AC346E5A094B24311CD2BBF9AEB72C5F819D0A99AE9F8BC8B1ACCA61CC6B7024462AC124462AC20A00

 

The C++ example required us to clone and build rocksdb from the upstream source as the version shipped with our linux distributon (Fedora 28) does not include some required components (snappy compression). Once rocksdb was built (see docs on github) we were able to use the following code & compiler command to build an executable that could read from the db:

 

// Extract the ledger specified below from a rippled rocksdb database
//
// Make sure you have a recent version of rocksdb available and make sure to
// install dependencies before building:
//   https://github.com/facebook/rocksdb/blob/master/INSTALL.md
//
// If cloned/built in ../rocksdb, you can compile this with:
//
//   g++ -I../rocksdb/include -I../rocksdb/include/rocksdb/ -I../rocksdb/ rocks.cpp ../rocksdb/librocksdb.a
//       -lpthread -lsnappy -lbz2 -lz -std=c++11  -faligned-new
//       -DHAVE_ALIGNED_NEW -DROCKSDB_PLATFORM_POSIX -DROCKSDB_LIB_IO_POSIX -DOS_LINUX -fno-builtin-memcmp
//       -DROCKSDB_FALLOCATE_PRESENT -DSNAPPY -DZLIB -DBZIP2 -DROCKSDB_MALLOC_USABLE_SIZE
//       -DROCKSDB_PTHREAD_ADAPTIVE_MUTEX -DROCKSDB_BACKTRACE -DROCKSDB_RANGESYNC_PRESENT
//       -DROCKSDB_SCHED_GETCPU_PRESENT -march=native  -DHAVE_SSE42 -DHAVE_PCLMUL -DROCKSDB_SUPPORT_THREAD_LOCAL

#include <algorithm>
#include <iostream>
#include "rocksdb/db.h"
#include "rocksdb/utilities/options_util.h"
#include "rocksdb/table.h"
#include "rocksdb/filter_policy.h"

const char* ledger = "0x26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D";

std::string HexToString(const std::string& str) {
  std::string result;
  std::string::size_type len = str.length();
  if (len < 2 || str[0] != '0' || str[1] != 'x') {
    fprintf(stderr, "Invalid hex input %s.  Must start with 0x\n", str.c_str());
    throw "Invalid hex input";
  }
  if (!rocksdb::Slice(str.data() + 2, len - 2).DecodeHex(&result)) {
    throw "Invalid hex input";
  }
  return result;
}

std::string StringToHex(const std::string& str) {
  std::string result("0x");
  result.append(rocksdb::Slice(str).ToString(true));
  return result;
}

int main(void){
  std::string k = HexToString(ledger);
  rocksdb::Slice slice = k;

  rocksdb::Options options;
  options.max_open_files = 2000; // cap open files for performance

  rocksdb::DB* db;
  rocksdb::Status status = rocksdb::DB::OpenForReadOnly(options, "/var/lib/rippled/db/rocksdb/rippledb.0899", &db);
  if (!status.ok()){
    std::cerr << "Err ";
    std::cerr << status.ToString() << std::endl;
    return 1;
  }

  std::string value;
  status = db->Get(rocksdb::ReadOptions(), slice, &value);

  if (!status.ok()){
    std::cerr << "Err ";
    std::cerr << status.ToString() << std::endl;
    return 1;
  }

  std::cout << "Value: " << StringToHex(value) << std::endl;
  return 0;
}

 

Output:

Value: 0x0000000000000000014C57520002C612E501633DDECCEF1A6BD5AB292ED5C988A58F71909262FE055F30830832F3C4305D5AC44A2AD5251667FB0C7D64D4735958B34400D15C599D073E007B4F7D06F309F1559C91C73284D054AC346E5A094B24311CD2BBF9AEB72C5F819D0A99AE9F8BC8B1ACCA61CC6B7024462AC124462AC20A00

 

The final step for us will be to get the higher level rocksdb bindings working against the custom build rocksdb lib but I don't foresee that being too big of a challenge.

 

Thanks again for the help!

 

Edited by devnullprod

Share this post


Link to post
Share on other sites
Posted (edited)

Just to complete this issue, I was able to get this working with the ruby bindings.

The first step is to build rocksdb according to the instructions, make sure to also run 'make shared_lib' to build the shared libraries (some compile time flags may be needed: CXXFLAGS='-Wno-error=deprecated-copy -Wno-error=pessimizing-move')

To simplify things you can run 'make install' to install the library system wide but I personally don't like doing this. To get around this make sure to specify the location of your rocksdb checkout when installing the gem:

export ROCKSDB_DIR=/path/torocksdb

gem install rocksdb-ruby -- --with-rocksdb-dir=${ROCKSDB_DIR}/ --with-rocksdb-include=${ROCKSDB_DIR}/include --with-rocksdb-lib=${ROCKSDB_DIR}/ -fPIC

 

(One caveat, inorder to get the 'max_open_files' option working we had to include a custom rocksdb-ruby patch and rebuild the gem)

 

Once this is said and done the following script accomplishes the same as above:

 

require "rocksdb"                                                                  
                  
ledger = "26706B14D370E69DE1F3A7ED6972CABC8FD249D3EB55510178A4F6765F58E69D"
ledger = [ledger].pack("H*")                                                
puts ledger.bytes.join " "                                                  
                                                                            
rocksdb = RocksDB::DB.new "/var/lib/rippled/db/rocksdb/rippledb.0899", {:readonly => true, :max_open_files => 2000}
puts "DB: #{rocksdb[ledger].unpack("H*").join(" ")}" 

 

Run it with:

LD_LIBRARY_PATH='/path/to/rocksdb/' ruby rocks.rb

 

Output:

38 112 107 20 211 112 230 157 225 243 167 237 105 114 202 188 143 210 73 211 235 85 81 1 120 164 246 118 95 88 230 157
DB: 0000000000000000014c57520002c612e501633ddeccef1a6bd5ab292ed5c988a58f71909262fe055f30830832f3c4305d5ac44a2ad5251667fb0c7d64d4735958b34400d15c599d073e007b4f7d06f309f1559c91c73284d054ac346e5a094b24311cd2bbf9aeb72c5f819d0a99ae9f8bc8b1acca61cc6b7024462ac124462ac20a00

 

Easy as that!

easy.jpg

Edited by devnullprod

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...