@ethereumjs/binarytree v10 (EXPERIMENTAL)

Binary Trees are a novel cryptographic data structure proposed for Ethereum state storage with smaller proof sizes than Merkle Patricia Tries. Keys map to a stem (first 31 bytes) and index (last byte) within a stem node.

This library is experimental — APIs are not stable and it must not be used in production.

Runnable examples live in examples/.

Table of Contents

• Installation
• Getting Started
• Proofs
• Browser
• API
• EthereumJS
• License

Installation

npm install @ethereumjs/binarytree

Getting Started

Use createBinaryTree() to instantiate a tree. By default an in-memory MapDB is used; pass db for persistence.

// ./examples/basicUsage.ts

import { createBinaryTree } from '@ethereumjs/binarytree'
import { bytesToHex, hexToBytes } from '@ethereumjs/util'

const main = async () => {
  const tree = await createBinaryTree()

  const key = hexToBytes(`0x${'00'.repeat(32)}`)
  const value = hexToBytes(`0x${'01'.repeat(32)}`)
  const stem = key.slice(0, 31)
  const index = key[31]

  await tree.put(stem, [index], [value])
  const [retrieved] = await tree.get(stem, [index])

  console.log(`Root: ${bytesToHex(tree.root())}`)
  console.log(`Value match: ${bytesToHex(retrieved!)}`)
}

void main()

put(stem, indices, values) accepts parallel arrays of slot indices and 32-byte values within one stem. get(stem, indices) returns values in the same order.

Options (BinaryTreeOpts): db, useRootPersistence, cacheSize, hashFunction (defaults to BLAKE3).

Proofs

Create inclusion proofs with tree.createBinaryProof(key), verify with verifyBinaryProof(), and rebuild a sparse tree from proof nodes with binaryTreeFromProof():

// ./examples/binaryProof.ts

import { binaryTreeFromProof, createBinaryTree, verifyBinaryProof } from '@ethereumjs/binarytree'
import { bytesToHex, hexToBytes } from '@ethereumjs/util'
import { blake3 } from '@noble/hashes/blake3.js'

const main = async () => {
  const tree = await createBinaryTree()

  const key = hexToBytes(`0x${'00'.repeat(31)}01`)
  const hashedKey = blake3(key)
  const value = hexToBytes(`0x${'02'.repeat(32)}`)
  const stem = hashedKey.slice(0, 31)
  const index = hashedKey[31]

  await tree.put(stem, [index], [value])

  const proof = await tree.createBinaryProof(hashedKey)
  const verified = await verifyBinaryProof(tree.root(), hashedKey, proof)
  const sparse = await binaryTreeFromProof(proof)

  console.log(`Proof length: ${proof.length} nodes`)
  console.log(`Verified value: ${bytesToHex(verified!)}`)
  console.log(`Sparse tree root match: ${bytesToHex(sparse.root()) === bytesToHex(tree.root())}`)
}

void main()

Proof keys are typically blake3(address || treeIndex || subIndex) as used by the Verkle/binary-tree state layer. A valid proof of non-existence returns null / undefined from verifyBinaryProof().

Browser

Hybrid ESM/CJS builds are provided. For a browser setup see ./examples/browser.html (build the package, then npx vite from the package root).

API

Generated TypeDoc documentation.

Main exports: BinaryTree, createBinaryTree, binaryTreeFromProof, verifyBinaryProof, CheckpointDB, node types under ./node.

Used by StatefulBinaryTreeStateManager in @ethereumjs/statemanager when EIP-7864 is activated on Common.

EthereumJS

The EthereumJS GitHub organization and its repositories are managed by members of the former Ethereum Foundation JavaScript team and the broader Ethereum community. If you want to join for work or carry out improvements on the libraries see the developer docs for an overview of current standards and tools and review our code of conduct.

License

MIT