[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)