[HN Gopher] Urkel - authenticated key-value store written in C ___________________________________________________________________ Urkel - authenticated key-value store written in C Author : chjj Score : 46 points Date : 2020-09-25 20:01 UTC (2 hours ago) (HTM) web link (github.com) (TXT) w3m dump (github.com) | Elo5555 wrote: | I love all the points stated. | ampdepolymerase wrote: | Looks like a good alternative to Google's Trillian. | | https://github.com/google/trillian | hoytech wrote: | Neat! I've been working on something quite similar: | https://github.com/hoytech/quadrable | tluyben2 wrote: | My complements for your documentation efforts; excellent | README. | hoytech wrote: | Thank you! | chjj wrote: | 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 wrote: | @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 | hoytech wrote: | 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. Maybe this isn't the best terminology -- I | believe you're right this makes it more of a radix tree. The | nice thing about this is we only need to do | log2(num_records_in_db) hashes on average. ___________________________________________________________________ (page generated 2020-09-25 23:00 UTC)