Urkel

An optimized and cryptographically provable key-value store. Written in C.

Design

The urkel tree is implemented as a base-2 merkelized radix tree. It builds on earlier research done by Bram Cohen and Amaury Séchet in order to create an alternative to Ethereum's base-16 trie.

Nodes are stored in a series of append-only files for snapshotting and crash consistency capabilities. Due to these presence of these features, Urkel has the ability to expose a fully transactional database.

Urkel is its own database. This is in contrast to earlier authenticated data structures which were typically implemented on top of an existing data store like LevelDB.

The urkel tree is currently used in production for the Handshake protocol.

Features

Transactions - Fully atomic and transactional API.
Snapshots - Transactions can also behave as snapshots, pointing to a historical root hash.
Iteration - Full tree iteration¹.
Compact Proofs - Small proof size, with proof nodes averaging ~34 bytes in size.
History Independence - Deterministic root hash calculation regardless of insertion/removal order.
Crash Consistency - kill -9'able.
Cross Platform - Runs on Windows XP and up, as well as any POSIX.1-2001 compatible OS.
WASM Support - Builds with both Emscripten as well as the WASI SDK.

Note that range iteration is not particularly useful for our use case.

Example Usage

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <urkel.h>

int main(void) {
  unsigned char key[32];
  unsigned char val[4] = {0xde, 0xad, 0xbe, 0xef};
  unsigned char key_out[32];
  unsigned char val_out[1023]; /* Max size (currently). */
  size_t val_len;
  urkel_t *db;
  urkel_tx_t *tx;

  /* Open database. */
  db = urkel_open("/path/to/db");

  assert(db != NULL);

  /* Create transaction. */
  tx = urkel_tx_create(db, NULL);

  assert(tx != NULL);

  /* Hash key. */
  urkel_hash(key, "my key", 6);

  /* Insert record. */
  assert(urkel_tx_insert(tx, key, val, sizeof(val)));

  /* Retrieve record. */
  assert(urkel_tx_get(tx, val_out, &val_len, key));
  assert(val_len == sizeof(val));
  assert(memcmp(val_out, val, val_len) == 0);

  /* Commit transaction. */
  assert(urkel_tx_commit(tx));

  {
    unsigned char root[32];
    unsigned char *proof_raw;
    size_t proof_len;
    int exists;

    /* Compute root. */
    urkel_tx_root(tx, root);

    /* Create proof. */
    assert(urkel_tx_prove(tx, &proof_raw, &proof_len, key));

    /* Verify proof. */
    assert(urkel_verify(&exists, val_out, &val_len,
                        proof_raw, proof_len, key, root));

    /* Returns our value. */
    assert(exists == 1);
    assert(val_len == sizeof(val));
    assert(memcmp(val_out, val, val_len) == 0);

    urkel_free(proof_raw);
  }

  {
    /* Create an iterator. */
    urkel_iter_t *iter = urkel_iter_create(tx);
    size_t i = 0;

    assert(iter != NULL);

    /* Iterate over our single record. */
    while (urkel_iter_next(iter, key_out, val_out, &val_len)) {
      assert(memcmp(key_out, key, 32) == 0);
      assert(val_len == sizeof(val));
      assert(memcmp(val_out, val, val_len) == 0);
      i += 1;
    }

    assert(urkel_errno == URKEL_EITEREND);
    assert(i == 1);

    urkel_iter_destroy(iter);
  }

  /* Cleanup. */
  urkel_tx_destroy(tx);
  urkel_close(db);

  return 0;
}

Compile with:

$ cc -o example example.c -lurkel

CLI Usage

The default build will provide you with an urkel executable. This allows very simple manipulation of an urkel database from the command line.

Example

Data manipulation:

$ urkel create
$ urkel root
0000000000000000000000000000000000000000000000000000000000000000
$ urkel insert foo 'deadbeef' -H
$ urkel root
1da2776eaa254ef65aeeee1f37f61c06bac2e82e221d37da21190191218f6631
$ urkel insert bar '01020304' -H
$ urkel root
497b751637ff244ab969a965f8d9dc7623f18d649d012276dfb317b0e38b9bec
$ urkel get bar -H
01020304
$ urkel remove bar -H
$ urkel root
1da2776eaa254ef65aeeee1f37f61c06bac2e82e221d37da21190191218f6631
$ urkel remove foo -H
$ urkel root
0000000000000000000000000000000000000000000000000000000000000000

Creating and verifying a proof:

$ urkel root
497b751637ff244ab969a965f8d9dc7623f18d649d012276dfb317b0e38b9bec
$ urkel prove foo -H
03c00100800280a6386fa1781a92e3905f718d4e0ea0d757abe962eefdd52a23d2ad6e1409fd8a0400deadbeef
$ urkel verify foo -H \
  '03c00100800280a6386fa1781a92e3905f718d4e0ea0d757abe962eefdd52a23d2ad6e1409fd8a0400deadbeef' \
  --root '497b751637ff244ab969a965f8d9dc7623f18d649d012276dfb317b0e38b9bec'
deadbeef

Usage

  Usage: urkel [options] [action] [args]

  Actions:

    create                create a new database
    destroy               destroy database
    info                  print database information
    root                  print root hash
    get <key>             retrieve value
    insert <key> <value>  insert value
    remove <key>          remove value
    list                  list all keys
    prove <key>           create proof
    verify <key> <proof>  verify proof (requires --root)

  Options:

    -p, --path <path>     path to database (default: $URKEL_PATH)
    -r, --root <hash>     root hash to use for snapshots
    -H, --hash            hash key with BLAKE2b-256
    -h, --help            output usage information

  Environment Variables:

    URKEL_PATH            path to database (default: ./)

Benchmarks

Benchmarks were run on a high-end but consumer-grade laptop, containing a Intel Core i7-8550U 1.80GHz and an NVMe PCIe SSD.

Benchmarking insert...
  Operations:  100000
  Nanoseconds: 176354477
  Seconds:     0.176354
  Ops/Sec:     567039.758225
  Sec/Op:      0.000002
Benchmarking get (cached)...
  Operations:  100000
  Nanoseconds: 91769518
  Seconds:     0.091770
  Ops/Sec:     1089686.446866
  Sec/Op:      0.000001
Benchmarking commit...
  Operations:  1
  Nanoseconds: 121798848
  Seconds:     0.121799
  Ops/Sec:     8.210258
  Sec/Op:      0.121799
Benchmarking get (uncached)...
  Operations:  100000
  Nanoseconds: 300755918
  Seconds:     0.300756
  Ops/Sec:     332495.535466
  Sec/Op:      0.000003
Benchmarking remove...
  Operations:  100000
  Nanoseconds: 88950509
  Seconds:     0.088951
  Ops/Sec:     1124220.660727
  Sec/Op:      0.000001
Benchmarking commit...
  Operations:  1
  Nanoseconds: 30168275
  Seconds:     0.030168
  Ops/Sec:     33.147404
  Sec/Op:      0.030168
Benchmarking commit (nothing)...
  Operations:  1
  Nanoseconds: 24088
  Seconds:     0.000024
  Ops/Sec:     41514.447028
  Sec/Op:      0.000024
Benchmarking prove...
  Operations:  100000
  Nanoseconds: 327144781
  Seconds:     0.327145
  Ops/Sec:     305675.058286
  Sec/Op:      0.000003
Benchmarking verify...
  Operations:  100000
  Nanoseconds: 330230736
  Seconds:     0.330231
  Ops/Sec:     302818.572285
  Sec/Op:      0.000003

Platforms without memory-mapped file support will suffer in performance (this includes Emscripten and WASI).

Contribution and License Agreement

If you contribute code to this project, you are implicitly allowing your code to be distributed under the MIT license. You are also implicitly verifying that all code is your original work. </legalese>

License

See LICENSE for more info.

Sh1Tt/liburkel