Verkle Trie TypeScript

A production-ready TypeScript implementation of Verkle Tries (Vector Commitment Trees) with KZG polynomial commitments. Supports efficient multi-proof generation and verification, designed for compatibility with Solidity verifiers.

Overview

Verkle Tries are an advanced data structure that combines the benefits of Merkle trees with polynomial commitments (KZG). This implementation provides:

• Efficient Multi-Proofs: Prove multiple key-value pairs with a single fixed-size KZG proof
• Path Sharing: Multiple leaves sharing internal nodes are deduplicated in proofs
• Solidity-Compatible: Proof format matches Solidity verifier expectations
• Production-Ready: Comprehensive test coverage, security checks, and JSDoc documentation

Installation

npm install verkle-trie-ts

Or with yarn:

yarn add verkle-trie-ts

Quick Start

Basic Usage

import { VerkleTrie, VerkleTrieVerifier } from 'verkle-trie-ts';
import { encodeAbiParameters, keccak256 } from 'viem';

const FIELD_SIZE = BigInt('21888242871839275222246405745257275088548364400416034343698204186575808495617');

// Create a trie with segmentBits=8 (2^8 = 256 slots)
const trie = new VerkleTrie(8);

// Insert data values directly (they will be hashed internally)
const data1 = BigInt(42);
trie.insert(data1);

// Verkelize the trie (compute all KZG commitments)
// REQUIRED: Must call verkelize() after all insertions
trie.verkelize(trie.root);

// Generate proof
const rootCommitment = trie.getRootCommitment();
const [D, pi, uniqueCommitments, internalYvals, zvals, rootCommitmentIndex, commitmentIndices] = 
  trie.getProof([data1]);

// Verify proof
const verifier = new VerkleTrieVerifier(rootCommitment!);
const encodedData = [encodeAbiParameters([{ type: 'uint256' }], [data1])];
const isValid = verifier.verifyMultiProof(
  D, pi, uniqueCommitments, internalYvals, zvals, encodedData, rootCommitmentIndex, commitmentIndices
);

Using TrieJSONBuilder (Recommended)

For structured data, use TrieJSONBuilder which handles ABI encoding and hashing:

import { loadTrieFromJSON, generateProofForEntry } from 'verkle-trie-ts';

// Load trie from JSON file
// Note: loadTrieFromJSON still uses branchingFactor for backward compatibility
const { trie, entryHashes } = loadTrieFromJSON('./data.json', 256);

// Generate proof for an entry
const entry = {
  types: [{ name: 'address', type: 'address' }, { name: 'amount', type: 'uint256' }],
  values: ['0x742d35Cc6634C0532925a3b844Bc9e7595f0bEb', 1000000000000000000n]
};

const proof = generateProofForEntry(trie, entry);

// Verify
const verifier = new VerkleTrieVerifier(trie.getRootCommitment()!);
const isValid = verifier.verifyMultiProof(
  proof.D, proof.pi, proof.uniqueCommitments, proof.yvals, proof.zvals,
  [proof.encodedData], proof.rootCommitmentIndex, proof.commitmentIndices
);

## API Documentation

### VerkleTrie

Main class for managing the Verkle Trie structure.

#### Constructor

```typescript
constructor(segmentBits: number)

• segmentBits: Number of bits per segment (exponent for branching factor: 2^segmentBits)
  • segmentBits=8 → 256 slots (2^8)
  • segmentBits=6 → 64 slots (2^6)
  • Must be between 1 and 16 (branching factors from 2 to 65536)

Methods

insert(value: bigint): void

Inserts a value into the trie. This is the recommended method for inserting data. Creates a leaf node automatically and inserts it into the trie.

Important: After inserting all values, you MUST call verkelize() before generating proofs.

insertNode(n: VerkleTrieNode, verkelize: boolean)

Advanced method for inserting a pre-constructed node. If verkelize is true, computes KZG commitments along the insertion path (for incremental updates).

Note: For most use cases, use insert() instead, which handles node creation automatically.

verkelize(n: VerkleTrieNode)

Computes KZG commitments for a node and all its descendants. Must be called after all insertions before generating proofs.

getProof(data: bigint[]): [Commitment, Commitment, Commitment[], bigint[], bigint[], number, \0x${string}`]`

Generates a cryptographic proof for the given data values.

Returns:

• D: G1Point commitment to aggregated polynomial
• pi: G1Point proof
• uniqueCommitments: Array of unique commitments (deduplicated to reduce proof size)
• internalYvals: Array of y-values for internal nodes only (leaf yvals are computed from encodedData in verifier)
• zvals: Array of all z-values (child indices, includes both leaves and internal nodes)
• rootCommitmentIndex: Index of root commitment in uniqueCommitments array
• commitmentIndices: Packed uint16 array (as hex string) mapping each zval/yval position to its index in uniqueCommitments

Note: Commitments are deduplicated to reduce proof size. The commitmentIndices array (packed as uint16 values) allows the verifier to reconstruct the full commitment list when computing challenges.

getRootCommitment(): Commitment | null

Returns the root commitment if the trie has been verkelized.

VerkleTrieVerifier

Verifies cryptographic proofs for Verkle Trie membership.

Constructor

constructor(storedRootCommitment: Commitment)

Methods

verifyMultiProof(D, pi, uniqueCommitments, internalYvals, zvals, encodedData, rootCommitmentIndex, commitmentIndices): boolean

Verifies a Verkle multi-proof with security checks matching Solidity verifier.

Parameters:

• D: G1Point commitment to aggregated polynomial
• pi: G1Point proof
• uniqueCommitments: Array of unique commitments (deduplicated)
• internalYvals: Array of y-values for internal nodes only (leaves excluded)
• zvals: Array of all z-values (child indices, leaves + internal nodes)
• encodedData: Array of ABI-encoded data entries (as hex strings) for leaf nodes
• rootCommitmentIndex: Index of root commitment in uniqueCommitments array
• commitmentIndices: Packed uint16 array (as hex string) mapping each zval/yval position to its index in uniqueCommitments

Security Checks:

1. Root commitment matches stored root
2. Leaf yvals are computed from encodedData and verified against stored hashes
3. Yval indices are valid, unique, and data hashes match
4. Pairing equation verification

TrieJSONBuilder

Utilities for working with ABI-encoded entries.

loadTrieFromJSON(jsonPath: string, branchingFactor?: number)

Loads a Verkle trie from a JSON file with ABI-encoded entries.

Note: This function uses branchingFactor for backward compatibility. The branching factor must be a power of 2 (e.g., 256 = 2^8). For new code, prefer creating a VerkleTrie directly with segmentBits (e.g., new VerkleTrie(8) for 256 slots).

generateProofForEntry(trie: VerkleTrie, entry: ABIEncodedEntry)

Generates a proof for a specific ABI-encoded entry.

Examples

See the examples/ directory for complete examples:

• examples/main.ts: Basic usage example

Testing

Run the comprehensive test suite:

npm test

The test suite covers:

• ✅ Single element trie
• ✅ Multiple elements
• ✅ Empty trie edge cases
• ✅ Security checks (tampered proofs, invalid indices)
• ✅ Path sharing verification
• ✅ Different segmentBits values (branching factors)

Architecture

Key Components

1. VerkleTrie: Main trie structure with radix tree insertion (core operations only)
2. VerkleTrieNode: Individual nodes (internal or leaf)
3. VerkleTrieVerifier: Proof verification with security checks
4. KZG Module: Polynomial commitment operations (commit, prove, verify)
5. TrieJSONBuilder: Utilities for ABI-encoded data
6. VerkleTrieUtils: Debugging and analysis utilities (printing, validation, statistics)

Proof Structure

The proof follows the Verkle tree multiproof structure:

• Challenge r = H(C_0,...,C_m-1, y_0,...,y_m-1, z_0,...,z_m-1) where commitments are reconstructed from uniqueCommitments using commitmentIndices
• Challenge t = H(r, D[0], D[1])
• Aggregated polynomial g(X) = Σ r^i * (pi(X) - yi)/(X - zi)
• Proof π = [(h(s) - g(s) - y)/(s - t)]_1

Commitment Deduplication: To reduce proof size, commitments are deduplicated. The commitmentIndices array (packed as uint16 values) maps each position in the proof to the corresponding unique commitment. This significantly reduces calldata costs when multiple paths share common internal nodes.

Security

• Fiat-Shamir Heuristic: Challenges r and t are computed from hashes
• Root Commitment Verification: Prevents proofs from different tries
• Data Hash Verification: Ensures encoded data matches stored values
• Index Validation: Prevents duplicate or out-of-bounds indices

Type Definitions

• Commitment: G1Point (elliptic curve point, represented as [bigint, bigint] at runtime)
• Proof: G1Point
• Coefficient: bigint
• ABIEncodedEntry: Interface for ABI-encoded entries

Notes

• Segment Bits: The constructor takes segmentBits (exponent) not branchingFactor. Use segmentBits=8 for 256 slots (2^8), segmentBits=6 for 64 slots (2^6), etc.
• Insert Method: Use insert(value) for simple insertion. The value will be hashed internally to generate the key. For ABI-encoded data (e.g., for Solidity verification), use insertNode() with a node created from an ABI-encoded hash.
• Verkelization: Must call verkelize(trie.root) after all insertions before generating proofs
• Proof Yvals: The internalYvals returned from getProof() contains only internal node yvals. Leaf yvals are computed from encodedData in the verifier to reduce proof size.
• Commitment Deduplication: Commitments are automatically deduplicated in proofs to reduce size. The commitmentIndices array (packed as uint16 values) maps each position to the corresponding unique commitment.
• Single Element: Special handling for single-element tries (zero polynomial cases)

Solidity Integration

This TypeScript implementation is designed to work seamlessly with the Solidity verifier. The proof format matches exactly what the Solidity contract expects:

• Commitment Deduplication: Commitments are deduplicated and commitmentIndices are packed as uint16 values to minimize calldata
• Leaf Yvals: Leaf yvals are computed from encodedData in the verifier (not included in proof) to reduce size
• ABI Encoding: Data must be ABI-encoded (using encodeAbiParameters from viem) for Solidity compatibility

See the Solidity verifier repository for the on-chain verification contract.

License

MIT

References

• Verkle Trees Paper
• PCS multiproofs using random evaluation
• Verkle tries for efficient data verification in peer­to­peer networks