{"id":16566,"library":"urkel","title":"Urkel Tree: Cryptographically Provable Key-Value Store","description":"Urkel Tree is an optimized, cryptographically provable key-value store implemented as a base-2 merkelized trie, specifically designed for the Handshake protocol. It significantly outperforms alternatives like Ethereum's base-16 trie by operating as its own database, storing nodes in flat, append-only files for snapshotting and crash consistency. The current stable version is 1.0.3, with releases focusing on stability, minor bug fixes, and internal optimizations rather than rapid feature additions. Key differentiators include its architectural simplicity (only two node types), compact internal node size (76 bytes), and extremely small proof sizes (32 bytes per sibling node), which are crucial for maintaining proof sizes under 1KB even with millions of leaves. It offers fully transactional capabilities and inherently provides history independence and non-destruction properties. A critical usage requirement is that Urkel must be used with uniformly distributed keys, typically achieved through hashing. While compaction is available, it is currently inefficient and manual, with future C implementation planned for optimization.","status":"active","version":"1.0.3","language":"javascript","source_language":"en","source_url":"git://github.com/handshake-org/urkel","tags":["javascript","net","tcp"],"install":[{"cmd":"npm install urkel","lang":"bash","label":"npm"},{"cmd":"yarn add urkel","lang":"bash","label":"yarn"},{"cmd":"pnpm add urkel","lang":"bash","label":"pnpm"}],"dependencies":[{"reason":"Cryptographic primitives (hashing, random bytes) are required for tree operations and proof verification.","package":"bcrypto","optional":false}],"imports":[{"note":"The library primarily uses CommonJS `require` syntax. Direct ESM `import` is not officially supported and may lead to issues.","wrong":"import { Tree } from 'urkel';","symbol":"Tree","correct":"const { Tree } = require('urkel');"},{"note":"Proof class for verifying cryptographic proofs is accessed via named CommonJS export.","wrong":"import { Proof } from 'urkel';","symbol":"Proof","correct":"const { Proof } = require('urkel');"},{"note":"Hashing algorithm like BLAKE2b from the `bcrypto` dependency is crucial for tree initialization and proof verification.","wrong":"import { BLAKE2b } from 'bcrypto';","symbol":"BLAKE2b","correct":"const { BLAKE2b } = require('bcrypto');"}],"quickstart":{"code":"const bcrypto = require('bcrypto');\nconst urkel = require('urkel');\nconst {BLAKE2b, randomBytes} = bcrypto;\nconst {Tree, Proof} = urkel;\n\nasync function runUrkelExample() {\n  // Create a tree using blake2b-256 with a 256-bit key size.\n  // Specify a unique prefix path for the database files.\n  const tree = new Tree({\n    hash: BLAKE2b,\n    bits: 256,\n    prefix: './urkel-db-example'\n  });\n\n  await tree.open();\n\n  let keyToProve;\n\n  // Transactions allow atomic operations on the tree.\n  const txn = tree.transaction();\n\n  // Insert 500 random key-value pairs.\n  for (let i = 0; i < 500; i++) {\n    const k = randomBytes(32); // 32 bytes for 256 bits\n    const v = randomBytes(300);\n    await txn.insert(k, v);\n    if (i === 250) keyToProve = k; // Save one key for proof\n  }\n\n  // Commit the transaction and retrieve the new root hash.\n  const root = await txn.commit();\n  const snapshot = tree.snapshot(root);\n\n  // Generate a cryptographic proof for the saved key.\n  const proof = await snapshot.prove(keyToProve);\n\n  // Verify the generated proof against the root, key, hash, and bits.\n  const [code, value] = proof.verify(root, keyToProve, BLAKE2b, 256);\n\n  if (code !== 0) {\n    console.log('Could not verify proof: %s.', Proof.code(code));\n  } else if (value) {\n    console.log('Valid proof for %s, value: %s', keyToProve.toString('hex'), value.toString('hex'));\n  } else {\n    console.log('Absence proof for %s.', keyToProve.toString('hex'));\n  }\n  \n  // Close the tree when done to release file handles.\n  await tree.close();\n}\n\nrunUrkelExample().catch(console.error);","lang":"javascript","description":"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."},"warnings":[{"fix":"Avoid frequent tree commissions or prepare for manual compaction, especially in high-throughput scenarios.","message":"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.","severity":"gotcha","affected_versions":">=1.0.0"},{"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.","message":"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.","severity":"breaking","affected_versions":">=1.0.0"},{"fix":"Always hash your keys (e.g., using BLAKE2b or SHA256) before inserting them into the Urkel Tree to ensure uniform distribution.","message":"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)'.","severity":"gotcha","affected_versions":">=1.0.0"}],"env_vars":null,"last_verified":"2026-04-22T00:00:00.000Z","next_check":"2026-07-21T00:00:00.000Z","problems":[{"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.","cause":"The cryptographic proof generated for a key-value pair failed verification against the tree's root, key, hash function, or bit depth.","error":"Could not verify proof: %s."},{"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.","cause":"Attempting to use `require()` in an ES module context or a browser environment without proper CommonJS polyfills/bundling.","error":"TypeError: require is not a function"}],"ecosystem":"npm"}