5 ms·

Neat! I've been working on something quite similar: https://github.com/hoytech/quadrable https://github.com/hoytech/quadrable

tluyben2 6y ago
My complements for your documentation efforts; excellent README.
- hoytech 6y ago
  Thank you!
chjj 6y ago
Very cool. I haven't seen a very many implementations of the SMT aside from Google's. The SMT was one of my original considerations, but I found my proof-of-concept implementation required far too much hashing for insertions. It really felt like a bottle-neck. After playing around with things, I eventually switched to a base-2 trie and ultimately a base-2 radix tree.
- AR_1 6y ago
  @JJ big fan of yours and ideas behind Urkel. Now in C it’ll be very performant. Likewise, I’ve done testing with SMT and we were hitting the same bottlenecks. It will be interesting to test this implementation. We recently published a research paper where we propose a use of dynamic B+ Tree with efficient proof sizes. Dynamic Merkle B-Tree with Efficient Proofs: https://arxiv.org/abs/2006.01994 https://arxiv.org/abs/2006.01994
  - chjj 6y ago
    Oh, that's interesting. I think the main thing that turned me away from more typical persistent data structures was my assumption that the proof size would be unacceptably large (also that branch rewrites during insertion would cause too much growth). A solution to that would be amazing. I'll try to grok this later tonight.
    - AR_1 6y ago
      Happy to discuss and dive in. We’ve been thinking about this problem for quite some time. JP was supposed to put us in touch last year, as we had questions on Urkel, but it never happened. Happy to connect here.
- hoytech 6y ago
  Thanks! Yes I believe the SMT implementation as described in the Certificate Transparency paper always does the full 256 hashes per insertion. That seemed unreasonably high to me too, which is why Quadrable uses a "collapsed leaf" optimisation. The nice thing about this is we only need to do log2(num_records_in_db) hashes on average. If I understand correctly, liburkel does even fewer hashes in the case of common prefixes which is pretty sweet.
- jude- 6y ago
  Really impressed with Urkel! I've had my eye on it for some time. In an earlier version (https://github.com/handshake-org/urkel https://github.com/handshake-org/urkel), the documentation talked about compaction being an expensive and user-initiated operation. Does this version address this? If you're looking for more SMT implementations, we've got a home-grown one at Blockstack. We built a "merklized adaptive-radix forest" (MARF) to represent blockchain state as an authenticated key/value store, where you can query a key's value at any block height (and get a proof). I think the high-level differences between it an an Urkel tree are: * No delete operation -- we need to be able to service key lookups from any previous committed root hash, since a major use-case for the MARF is in allowing Blockstack smart contracts to cheaply query historic chain state in the same fork. * Key insertion order affects the root hash (but this is more of an artifact of the implementation than a deliberate design decision). * Variable-radix nodes, in order to minimize the number of nodes that would need to be loaded on a key lookup. Ours is based on adaptive-radix trees [1]. * Proof size is bigger, and has a different structure. The proof is meant to show a key's value, as well as its place in the blockchain history. * Implemented in Rust, as an index within a Sqlite database -- we rely in Sqlite to provide crash-consistency. Anyway, the technical documentation is here [2] and the code is here [3] if you want to take a look! [1] https://15721.courses.cs.cmu.edu/spring2016/papers/leis-icde2013.pdf https://15721.courses.cs.cmu.edu/spring2016/papers/leis-icde... [2] https://github.com/blockstack/stacks-blockchain/blob/master/sip/sip-004-materialized-view.md https://github.com/blockstack/stacks-blockchain/blob/master/... [3] https://github.com/blockstack/stacks-blockchain/tree/master/src/chainstate/stacks/index https://github.com/blockstack/stacks-blockchain/tree/master/...

tluyben2 6y ago

My complements for your documentation efforts; excellent README.

hoytech 6y ago
Thank you!

chjj 6y ago

Very cool. I haven't seen a very many implementations of the SMT aside from Google's. The SMT was one of my original considerations, but I found my proof-of-concept implementation required far too much hashing for insertions. It really felt like a bottle-neck. After playing around with things, I eventually switched to a base-2 trie and ultimately a base-2 radix tree.

AR_1 6y ago
@JJ big fan of yours and ideas behind Urkel. Now in C it’ll be very performant. Likewise, I’ve done testing with SMT and we were hitting the same bottlenecks. It will be interesting to test this implementation. We recently published a research paper where we propose a use of dynamic B+ Tree with efficient proof sizes. Dynamic Merkle B-Tree with Efficient Proofs: https://arxiv.org/abs/2006.01994 https://arxiv.org/abs/2006.01994
- chjj 6y ago
  Oh, that's interesting. I think the main thing that turned me away from more typical persistent data structures was my assumption that the proof size would be unacceptably large (also that branch rewrites during insertion would cause too much growth). A solution to that would be amazing. I'll try to grok this later tonight.
  - AR_1 6y ago
    Happy to discuss and dive in. We’ve been thinking about this problem for quite some time. JP was supposed to put us in touch last year, as we had questions on Urkel, but it never happened. Happy to connect here.
hoytech 6y ago
Thanks! Yes I believe the SMT implementation as described in the Certificate Transparency paper always does the full 256 hashes per insertion. That seemed unreasonably high to me too, which is why Quadrable uses a "collapsed leaf" optimisation. The nice thing about this is we only need to do log2(num_records_in_db) hashes on average. If I understand correctly, liburkel does even fewer hashes in the case of common prefixes which is pretty sweet.
jude- 6y ago
Really impressed with Urkel! I've had my eye on it for some time. In an earlier version (https://github.com/handshake-org/urkel https://github.com/handshake-org/urkel), the documentation talked about compaction being an expensive and user-initiated operation. Does this version address this? If you're looking for more SMT implementations, we've got a home-grown one at Blockstack. We built a "merklized adaptive-radix forest" (MARF) to represent blockchain state as an authenticated key/value store, where you can query a key's value at any block height (and get a proof). I think the high-level differences between it an an Urkel tree are: * No delete operation -- we need to be able to service key lookups from any previous committed root hash, since a major use-case for the MARF is in allowing Blockstack smart contracts to cheaply query historic chain state in the same fork. * Key insertion order affects the root hash (but this is more of an artifact of the implementation than a deliberate design decision). * Variable-radix nodes, in order to minimize the number of nodes that would need to be loaded on a key lookup. Ours is based on adaptive-radix trees [1]. * Proof size is bigger, and has a different structure. The proof is meant to show a key's value, as well as its place in the blockchain history. * Implemented in Rust, as an index within a Sqlite database -- we rely in Sqlite to provide crash-consistency. Anyway, the technical documentation is here [2] and the code is here [3] if you want to take a look! [1] https://15721.courses.cs.cmu.edu/spring2016/papers/leis-icde2013.pdf https://15721.courses.cs.cmu.edu/spring2016/papers/leis-icde... [2] https://github.com/blockstack/stacks-blockchain/blob/master/sip/sip-004-materialized-view.md https://github.com/blockstack/stacks-blockchain/blob/master/... [3] https://github.com/blockstack/stacks-blockchain/tree/master/src/chainstate/stacks/index https://github.com/blockstack/stacks-blockchain/tree/master/...