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.
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.
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.
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.
Really impressed with Urkel! I've had my eye on it for some time. In an earlier version (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!
I roughly understand the idea of a key-value store, but how are people using these in the wild? Which kind of data would a developer choose to store in one?
