Skip to main content

​
Overview

BinaryTree implements the Binary State Tree structure proposed in EIP-7864. It provides a unified tree structure for Ethereum state using BLAKE3 hashing with stem-based key organization. 
import * as BinaryTree from '@tevm/voltaire/BinaryTree'

// Create empty tree
const tree = BinaryTree.init()

// Insert key-value pair
const key = new Uint8Array(32)
const value = new Uint8Array(32)
value[0] = 0x42

const updated = BinaryTree.insert(tree, key, value)

// Retrieve value
const retrieved = BinaryTree.get(updated, key)

// Compute root hash
const hash = BinaryTree.rootHash(updated)

​
Tree Structure

The tree consists of four node types:
Node TypeDescription
emptyEmpty node (zero hash)
internalInternal node with left/right child hashes
stemStem node with 31-byte stem and 256 value slots
leafLeaf node with raw value
type Node =
  | { type: 'empty' }
  | { type: 'internal'; left: Uint8Array; right: Uint8Array }
  | { type: 'stem'; stem: Uint8Array; values: (Uint8Array | null)[] }
  | { type: 'leaf'; value: Uint8Array }

​
Key Methods

​
init

Create an empty tree. 
const tree = BinaryTree.init()
console.log(tree.root.type) // 'empty'

​
insert

Insert a value at a 32-byte key. Returns a new tree (immutable). 
const key = new Uint8Array(32)
key[0] = 0x01

const value = new Uint8Array(32)
value[0] = 0xAB

const updated = BinaryTree.insert(tree, key, value)
Keys are split into:
  • Stem (31 bytes) - path through the tree
  • Subindex (1 byte) - slot index within stem node (0-255)

​
get

Retrieve a value by key. Returns null if not found. 
const value = BinaryTree.get(tree, key)
if (value) {
  console.log('Found:', value)
}

​
rootHash

Compute the 32-byte root hash of the tree. 
const hash = BinaryTree.rootHash(tree)
console.log(hash.length) // 32

​
rootHashHex

Get root hash as hex string. 
const hex = BinaryTree.rootHashHex(tree)
console.log(hex) // "0x0000...0000" (empty tree)

​
Key Utilities

​
addressToKey

Convert a 20-byte Ethereum address to a 32-byte key (pads with 12 zero bytes). 
const address = new Uint8Array(20)
address[0] = 0x42

const key = BinaryTree.addressToKey(address)
console.log(key.length) // 32
console.log(key[12]) // 0x42

​
splitKey

Split a 32-byte key into stem (31 bytes) and subindex (1 byte). 
const key = new Uint8Array(32)
key[31] = 0x42

const { stem, idx } = BinaryTree.splitKey(key)
console.log(stem.length) // 31
console.log(idx) // 0x42

​
getStemBit

Get bit value at position in a stem (for tree traversal). 
const stem = new Uint8Array(31)
stem[0] = 0b10101010

console.log(BinaryTree.getStemBit(stem, 0)) // 1
console.log(BinaryTree.getStemBit(stem, 1)) // 0
console.log(BinaryTree.getStemBit(stem, 2)) // 1

​
Hashing Functions

All hashing uses BLAKE3. Factory functions allow dependency injection for tree-shaking.

​
hashNode

Hash any node type. Returns 32-byte hash. 
// With auto-injected crypto (convenient)
const hash = BinaryTree.hashNode(node)

// With explicit dependency injection (tree-shakeable)
import { HashNode } from '@tevm/voltaire/BinaryTree'
import { blake3 } from '@noble/hashes/blake3'

const hashNode = HashNode({ blake3 })
const hash = hashNode(node)

​
hashInternal

Hash an internal node (concatenates left and right hashes). 
const left = new Uint8Array(32)
const right = new Uint8Array(32)
const hash = BinaryTree.hashInternal(left, right)

// If both children are zero, returns zero hash
console.log(hash.every(b => b === 0)) // true

​
hashStem

Hash a stem node (concatenates stem + all 256 values). 
const node = {
  type: 'stem' as const,
  stem: new Uint8Array(31),
  values: new Array(256).fill(null)
}
node.values[0] = new Uint8Array(32)

const hash = BinaryTree.hashStem(node)

​
hashLeaf

Hash a leaf node (hashes the value directly). 
const node = {
  type: 'leaf' as const,
  value: new Uint8Array(32)
}
const hash = BinaryTree.hashLeaf(node)

​
Types

​
BinaryTree

The tree container type. 
interface BinaryTree {
  readonly root: Node
}

​
AccountData

Layout for account data stored at index 0 of stem nodes. 
interface AccountData {
  readonly version: number    // 1 byte
  readonly codeSize: number   // 3 bytes
  readonly nonce: bigint      // 8 bytes
  readonly balance: bigint    // 16 bytes
}

​
Error Handling

import {
  InvalidAddressLengthError,
  InvalidKeyLengthError,
  InvalidTreeStateError
} from '@tevm/voltaire/BinaryTree'

try {
  // Invalid address (not 20 bytes)
  BinaryTree.addressToKey(new Uint8Array(10))
} catch (e) {
  if (e instanceof InvalidAddressLengthError) {
    console.log('Address must be 20 bytes')
  }
}

try {
  // Invalid key (not 32 bytes)
  BinaryTree.splitKey(new Uint8Array(16))
} catch (e) {
  if (e instanceof InvalidKeyLengthError) {
    console.log('Key must be 32 bytes')
  }
}

​
Example: State Storage

import * as BinaryTree from '@tevm/voltaire/BinaryTree'

// Create tree and store account data
let tree = BinaryTree.init()

// Convert address to key
const address = new Uint8Array(20)
address[0] = 0x42
const accountKey = BinaryTree.addressToKey(address)

// Store balance at account key
const balance = new Uint8Array(32)
balance[31] = 0x64 // 100 wei

tree = BinaryTree.insert(tree, accountKey, balance)

// Verify storage
const stored = BinaryTree.get(tree, accountKey)
console.log(stored?.[31]) // 100

// Get merkle root
const root = BinaryTree.rootHashHex(tree)
console.log('State root:', root)

​
See Also