Urkel Tree: Cryptographically Provable Key-Value Store

Common errors

• Could not verify proof: %s.

  cause The cryptographic proof generated for a key-value pair failed verification against the tree's root, key, hash function, or bit depth.
  fix Check that the `root`, `key`, `hash` function (e.g., BLAKE2b), and `bits` (key size) passed to `proof.verify()` exactly match those used during tree creation and snapshot generation. Also, ensure the key being proved actually exists or its absence is correctly expected.

• TypeError: require is not a function

  cause Attempting to use `require()` in an ES module context or a browser environment without proper CommonJS polyfills/bundling.
  fix Ensure your Node.js project is configured to run as a CommonJS module (e.g., omit `"type": "module"` in `package.json` or rename files to `.cjs`). For browser usage, use a bundler like Webpack or Rollup configured for CommonJS.

Warnings

• gotcha Urkel compaction is currently inefficient and requires manual user intervention. It is not designed for frequent execution in consensus applications and will be optimized in a future C implementation.
  Fix: Avoid frequent tree commissions or prepare for manual compaction, especially in high-throughput scenarios.
• breaking Only the 'radix' variant of the Urkel Tree is currently maintained. Older 'trie' and 'optimized' backends were removed in version 1.0.0. Using or referencing these deprecated variants will result in errors.
  Fix: Ensure your implementation exclusively uses the `urkel/radix` variant, which is the default for current versions. Refer to the `old-variants` branch if legacy code needs to be adapted.
• gotcha Urkel Tree requires uniformly distributed keys for optimal performance and correctness. The documentation explicitly states it 'should only be used with uniformly distributed keys (i.e. hashed)'.
  Fix: Always hash your keys (e.g., using BLAKE2b or SHA256) before inserting them into the Urkel Tree to ensure uniform distribution.

Install

• npm install urkel npm
• yarn add urkel yarn
• pnpm add urkel pnpm

Imports

• Tree
  wrong:

  import { Tree } from 'urkel';

  correct:

  const { Tree } = require('urkel');

  The library primarily uses CommonJS `require` syntax. Direct ESM `import` is not officially supported and may lead to issues.
• Proof
  wrong:

  import { Proof } from 'urkel';

  correct:

  const { Proof } = require('urkel');

  Proof class for verifying cryptographic proofs is accessed via named CommonJS export.
• BLAKE2b
  wrong:

  import { BLAKE2b } from 'bcrypto';

  correct:

  const { BLAKE2b } = require('bcrypto');

  Hashing algorithm like BLAKE2b from the `bcrypto` dependency is crucial for tree initialization and proof verification.

Quickstart

This example demonstrates creating an Urkel Tree, performing a batch of insertions within a transaction, committing the changes to get a new root, and then generating and verifying a cryptographic proof for a specific key-value pair.

const bcrypto = require('bcrypto');
const urkel = require('urkel');
const {BLAKE2b, randomBytes} = bcrypto;
const {Tree, Proof} = urkel;

async function runUrkelExample() {
  // Create a tree using blake2b-256 with a 256-bit key size.
  // Specify a unique prefix path for the database files.
  const tree = new Tree({
    hash: BLAKE2b,
    bits: 256,
    prefix: './urkel-db-example'
  });

  await tree.open();

  let keyToProve;

  // Transactions allow atomic operations on the tree.
  const txn = tree.transaction();

  // Insert 500 random key-value pairs.
  for (let i = 0; i < 500; i++) {
    const k = randomBytes(32); // 32 bytes for 256 bits
    const v = randomBytes(300);
    await txn.insert(k, v);
    if (i === 250) keyToProve = k; // Save one key for proof
  }

  // Commit the transaction and retrieve the new root hash.
  const root = await txn.commit();
  const snapshot = tree.snapshot(root);

  // Generate a cryptographic proof for the saved key.
  const proof = await snapshot.prove(keyToProve);

  // Verify the generated proof against the root, key, hash, and bits.
  const [code, value] = proof.verify(root, keyToProve, BLAKE2b, 256);

  if (code !== 0) {
    console.log('Could not verify proof: %s.', Proof.code(code));
  } else if (value) {
    console.log('Valid proof for %s, value: %s', keyToProve.toString('hex'), value.toString('hex'));
  } else {
    console.log('Absence proof for %s.', keyToProve.toString('hex'));
  }
  
  // Close the tree when done to release file handles.
  await tree.close();
}

runUrkelExample().catch(console.error);