Urkel – authenticated key-value store written in C | Hacker News Reader

Urkel – authenticated key-value store written in C

github.com

114 pointschjj14 comments

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

My complements for your documentation efforts; excellent README.

Thank you!

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.

@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

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.

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.

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!

[1] https://15721.courses.cs.cmu.edu/spring2016/papers/leis-icde...

[2] https://github.com/blockstack/stacks-blockchain/blob/master/...

[3] https://github.com/blockstack/stacks-blockchain/tree/master/...

Looks like a good alternative to Google's Trillian.

https://github.com/google/trillian

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?

Configuration typically, you can map a key store in azure to databricks key secrets. Only in beta, not really usable but hey it's what came to mind.

Thanks - but that raises further questions about what exactly an azure databrick is!

I love all the points stated.

Reply on news.ycombinator.com