leanimt

package module
v0.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 16, 2026 License: AGPL-3.0 Imports: 15 Imported by: 2

README ¶

Lean Incremental Merkle Tree (Go Implementation)

This is a Go implementation of the Lean Incremental Merkle Tree, originally developed by the ZK-Kit team. The original TypeScript implementation has been audited as part of the Semaphore V4 PSE audit.

The LeanIMT is an optimized binary version of traditional Incremental Merkle Trees (IMT), eliminating the need for zero values and allowing dynamic depth adjustment. Unlike standard IMTs that use zero hashes for incomplete nodes, the LeanIMT directly adopts the left child's value when a node lacks a right counterpart. The tree's depth dynamically adjusts to the count of leaves, enhancing efficiency by reducing the number of required hash calculations.

A compatible Solidity implementation is available at zk-kit.solidity. Which uses poseidon-solidity for hashing, an optimized version of Poseidon consuming ~20k gas.

Features

  • High Performance: Optimized for large-scale applications (tested with 20M+ leaves)
  • Thread-Safe: Concurrent read/write operations with RWMutex protection
  • Persistent Storage: Optional Pebble database backend for disk persistence
  • Parallel Insertion: Batch operations with configurable goroutine pools
  • Generic Types: Type-safe implementation with Go generics
  • Zero Dependencies: Core functionality requires no external dependencies
  • Memory Efficient: Optimized memory usage for cryptographic operations
  • Gnark zk-SNARK Circuit: Built-in circuit for verifying Merkle proofs in zero-knowledge proofs

Installation

go get github.com/vocdoni/lean-imt-go

Usage

Basic Usage
package main

import (
    "fmt"
    "math/big"
    
    leanimt "github.com/vocdoni/lean-imt-go"
)

func main() {
    // Create a new tree with a simple hash function
    tree, err := leanimt.New(
        leanimt.BigIntHasher,     // Hash function
        leanimt.BigIntEqual,      // Equality function
        nil, nil, nil,            // No persistence
    )
    if err != nil {
        panic(err)
    }

    // Insert leaves
    err = tree.Insert(big.NewInt(1))
    if err != nil {
        panic(err)
    }
    
    err = tree.Insert(big.NewInt(3))
    if err != nil {
        panic(err)
    }

    fmt.Printf("Tree size: %d\n", tree.Size())        // 2
    fmt.Printf("Tree depth: %d\n", tree.Depth())      // 1
    
    root, exists := tree.Root()
    if exists {
        fmt.Printf("Root: %s\n", root.String())
    }

    // Check if tree contains a value
    has := tree.Has(big.NewInt(3))
    fmt.Printf("Contains 3: %t\n", has)               // true

    // Get index of a value
    index := tree.IndexOf(big.NewInt(3))
    if index > -1 {
        fmt.Printf("Index of 3: %d\n", index)         // 1
    }

    // Update a leaf
    err = tree.Update(1, big.NewInt(2))
    if err != nil {
        panic(err)
    }

    // Generate and verify proof
    proof, err := tree.GenerateProof(0)
    if err != nil {
        panic(err)
    }
    
    isValid := tree.VerifyProof(proof)
    fmt.Printf("Proof valid: %t\n", isValid)          // true
}
Batch Operations
// Insert many leaves at once (much faster)
leaves := make([]*big.Int, 1000000)
for i := 0; i < 1000000; i++ {
    leaves[i] = big.NewInt(int64(i))
}

err := tree.InsertMany(leaves)
if err != nil {
    panic(err)
}

fmt.Printf("Inserted %d leaves\n", tree.Size())
With Poseidon Hash (Cryptographic)
import leanimt "github.com/vocdoni/lean-imt-go"

// Create tree with cryptographic Poseidon hash
tree, err := leanimt.New(
    leanimt.PoseidonHasher,   // Cryptographic hash function
    leanimt.BigIntEqual,      // Equality function
    nil, nil, nil,            // No persistence
)
if err != nil {
    panic(err)
}

// Use the tree normally...
With Persistence
// Create tree with Pebble database persistence
tree, err := leanimt.NewWithPebble(
    leanimt.BigIntHasher,
    leanimt.BigIntEqual,
    leanimt.BigIntEncoder,    // Encoder function
    leanimt.BigIntDecoder,    // Decoder function
    "./tree_data",           // Database directory
)
if err != nil {
    panic(err)
}

// Insert data
err = tree.InsertMany(leaves)
if err != nil {
    panic(err)
}

// Sync to disk
err = tree.Sync()
if err != nil {
    panic(err)
}

// Close the tree
err = tree.Close()
if err != nil {
    panic(err)
}

// Reopen the tree (data is automatically loaded)
tree2, err := leanimt.NewWithPebble(
    leanimt.BigIntHasher,
    leanimt.BigIntEqual,
    leanimt.BigIntEncoder,
    leanimt.BigIntDecoder,
    "./tree_data",
)
if err != nil {
    panic(err)
}

fmt.Printf("Loaded tree size: %d\n", tree2.Size())
Import/Export
// Export tree data
data, err := tree.Export()
if err != nil {
    panic(err)
}

// Save to file
err = os.WriteFile("tree.json", data, 0644)
if err != nil {
    panic(err)
}

// Load from file
data, err = os.ReadFile("tree.json")
if err != nil {
    panic(err)
}

// Import tree data
tree2, err := leanimt.Import(
    leanimt.BigIntHasher,
    leanimt.BigIntEqual,
    data,
)
if err != nil {
    panic(err)
}

Census Package

The census package provides a voting census implementation using Lean IMT for efficient address-weight storage with zero-knowledge proof support. It packs Ethereum addresses (160 bits) and voting weights (88 bits) into single 248-bit values that fit safely within the BN254 scalar field (~254 bits) for circuit compatibility.

The packing scheme combines address and weight into a single tree leaf: packed = (address << 88) | weight.

Usage
import "github.com/vocdoni/lean-imt-go/census"

// Create census with database persistence
census, err := census.NewCensusIMTWithPebble("./census_data")
if err != nil {
    panic(err)
}
defer census.Close()

// Add single address
addr := common.HexToAddress("0x742d35Cc6634C0532925a3b844Bc9e7595f0bEb7")
weight := big.NewInt(1000)
err = census.Add(addr, weight)
if err != nil {
    panic(err)
}

// Bulk add multiple addresses (more efficient)
addresses := []common.Address{
    common.HexToAddress("0x8ba1f109551bD432803012645Hac136c22C177ec"),
    common.HexToAddress("0x1234567890123456789012345678901234567890"),
}
weights := []*big.Int{big.NewInt(250), big.NewInt(75)}
err = census.AddBulk(addresses, weights)
if err != nil {
    panic(err)
}

// Generate proof for circuit verification
proof, err := census.GenerateProof(addr)
if err != nil {
    panic(err)
}

fmt.Printf("Census size: %d\n", census.Size())
fmt.Printf("Root: %s\n", proof.Root.String())
Export and Pagination

The census supports exporting entries:

// Export entire census (streams data, memory efficient)
reader := census.Dump()
decoder := json.NewDecoder(reader)

for decoder.More() {
    var entry census.CensusEntry
    if err := decoder.Decode(&entry); err != nil {
        panic(err)
    }
    fmt.Printf("%s: %s\n", entry.Address, entry.Weight)
}

// Paginated export (useful for APIs)
page1 := census.DumpRange(0, 100)    // First 100 entries
page2 := census.DumpRange(100, 100)  // Next 100 entries

// Process paginated data
decoder = json.NewDecoder(page1)
for decoder.More() {
    var entry census.CensusEntry
    if err := decoder.Decode(&entry); err != nil {
        panic(err)
    }
    // Process entry...
}

Gnark Circuit

The circuit package provides zero-knowledge proof verification of Lean IMT Merkle proofs using Gnark. It includes both generic proof verification and census-specific verification with address-weight packing.

The circuit uses github.com/vocdoni/gnark-crypto-primitives/hash/bn254/poseidon for hashing.

Basic Proof Verification
func (myCircuit *MyCircuit) Define(api frontend.API) error {
    isValid, err := circuit.VerifyLeanIMTProof(
        api,
        myCircuit.MerkleRoot,
        myCircuit.LeafValue,
        myCircuit.LeafIndex,
        myCircuit.ProofSiblings,
    )
    if err != nil {
        return err
    }
    
    // Assert proof is valid
    api.AssertIsEqual(isValid, 1)
    return nil
}
Census Proof Verification
func (votingCircuit *VotingCircuit) Define(api frontend.API) error {
    // Verify census membership
    isValid, err := circuit.VerifyCensusProof(
        api,
        votingCircuit.CensusRoot,
        votingCircuit.VoterAddress,
        votingCircuit.Weight,
        votingCircuit.PathBits,
        votingCircuit.LeafIndex,
        votingCircuit.Siblings,
    )
    if err != nil {
        return err
    }
    
    // Assert proof is valid (or use isValid in other logic)
    api.AssertIsEqual(isValid, 1)
    return nil
}
LeafIndex vs PathBits

LeafIndex and PathBits are related but not interchangeable:

  • LeafIndex: absolute position of the leaf in level-0 leaves (0..size-1).
  • PathBits: packed left/right directions used while hashing siblings in the proof path (bit i corresponds to siblings[i], LSB first).

In Lean IMT, proofs omit missing siblings. Because of that, PathBits encodes directions for the included siblings only, while LeafIndex remains the canonical absolute position of the leaf.

Constraints
Max Depth Constraints Variables Scaling Rate
3 745 747 Base
5 1,239 1,241 +247/level
8 1,980 1,982 +247/level
10 2,474 2,476 +247/level

🔗 References

Documentation ¶

Index ¶

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

func BigIntDecoder ¶ 

func BigIntDecoder(data []byte) (*big.Int, error)

BigIntDecoder decodes bytes to a *big.Int. This function is used by the LeanIMT for persistence operations. It explicitly handles zero values to ensure they are properly decoded.

Parameters:

  • data: Byte slice to decode

Returns: Decoded big.Int value, or error if decoding fails

func BigIntEncoder ¶ 

func BigIntEncoder(n *big.Int) ([]byte, error)

BigIntEncoder encodes a *big.Int to bytes using big-endian format. This function is used by the LeanIMT for persistence operations. It explicitly handles zero values to ensure they are properly encoded.

Parameters:

  • n: The big.Int value to encode

Returns: Byte slice representation of the value, or error if encoding fails

func BigIntEqual ¶ 

func BigIntEqual(a, b *big.Int) bool

BigIntEqual is an equality function for *big.Int values. This function is used by the LeanIMT to compare values for equality.

Parameters:

  • a: First value to compare
  • b: Second value to compare

Returns: true if a equals b, false otherwise

func Blake2bHasher ¶ 

func Blake2bHasher(a, b *big.Int) *big.Int

Blake2bHasher performs BLAKE2b-256 hash on two big.Int values. BLAKE2b is a cryptographic hash function that is faster than SHA-256 while providing similar security guarantees. It's optimized for 64-bit platforms and is widely used in modern cryptographic applications.

This hasher is suitable for:

  • High-performance hashing requirements
  • Modern cryptographic systems
  • Applications requiring fast, secure hashing

The function converts both inputs to bytes, writes them to a BLAKE2b hasher, and returns the 256-bit hash result.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the BLAKE2b initialization fails

func MiMC7Hasher ¶ 

func MiMC7Hasher(a, b *big.Int) *big.Int

MiMC7Hasher performs MiMC-7 hash on two big.Int values using the iden3 implementation. MiMC-7 is a variant of the MiMC hash function with 7 rounds per block, optimized for zero-knowledge proof systems. This implementation is compatible with iden3's circom circuits and other iden3 tooling.

This hasher is suitable for:

  • Compatibility with iden3 ecosystem (circom, snarkjs)
  • ZK applications using iden3 libraries
  • Systems requiring MiMC-7 specifically

The function operates over the BN254 scalar field and is compatible with iden3's circom MiMC7 implementation.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the hash operation fails

func MiMCBLS12377Hasher ¶ 

func MiMCBLS12377Hasher(a, b *big.Int) *big.Int

MiMCBLS12377Hasher performs MiMC hash on two big.Int values over the BLS12-377 curve. MiMC (Minimal Multiplicative Complexity) is a family of block ciphers and hash functions designed to be efficient in zero-knowledge proof systems. This variant operates over the scalar field of the BLS12-377 elliptic curve.

This hasher is suitable for:

  • ZK circuits using the BLS12-377 curve
  • Applications requiring BLS12-377 compatibility
  • Systems built with gnark using BLS12-377

The function ensures inputs are reduced modulo the BLS12-377 field order before hashing.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the hash operation fails

func MiMCBN254Hasher ¶ 

func MiMCBN254Hasher(a, b *big.Int) *big.Int

MiMCBN254Hasher performs MiMC hash on two big.Int values over the BN254 curve. MiMC (Minimal Multiplicative Complexity) is a family of block ciphers and hash functions designed to be efficient in zero-knowledge proof systems. This variant operates over the scalar field of the BN254 (also known as BN128 or alt_bn128) elliptic curve.

This hasher is suitable for:

  • ZK circuits using the BN254 curve (most common in Ethereum)
  • Applications requiring BN254 compatibility
  • Systems built with gnark using BN254
  • Ethereum-compatible ZK applications

The function ensures inputs are reduced modulo the BN254 field order before hashing.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the hash operation fails

func MultiPoseidonHasher ¶ 

func MultiPoseidonHasher(a, b *big.Int) *big.Int

MultiPoseidonHasher performs MultiPoseidon hash on two big.Int values. MultiPoseidon is Vocdoni's implementation of the Poseidon hash function that can efficiently handle variable-length inputs by automatically chunking them into field elements. This makes it particularly useful for hashing arbitrary-length data in ZK circuits.

This hasher is suitable for:

  • Vocdoni ecosystem applications
  • Variable-length input hashing in ZK circuits
  • Applications requiring efficient multi-element Poseidon hashing

The function operates over the BN254 scalar field and is optimized for use in gnark circuits.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the hash operation fails

func PoseidonHasher ¶ 

func PoseidonHasher(a, b *big.Int) *big.Int

PoseidonHasher performs Poseidon hash on two big.Int values using the iden3 implementation. Poseidon is a ZK-friendly cryptographic hash function optimized for use in zero-knowledge proof systems, particularly over the BN254 curve. It's significantly more efficient in circuits compared to traditional hash functions like SHA-256.

This hasher is suitable for:

  • Merkle tree constructions in ZK circuits
  • Privacy-preserving applications
  • Blockchain applications requiring ZK proofs

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int Panics if the hash operation fails (should not happen with valid inputs)

func SHA256Hasher ¶ 

func SHA256Hasher(a, b *big.Int) *big.Int

SHA256Hasher performs SHA-256 hash on two big.Int values. SHA-256 is a widely-used cryptographic hash function from the SHA-2 family. While not optimized for zero-knowledge circuits, it provides strong security guarantees and is well-tested in production systems.

This hasher is suitable for:

  • General-purpose cryptographic hashing
  • Systems requiring NIST-approved algorithms
  • Compatibility with existing SHA-256 based systems

The function converts both inputs to bytes (big-endian), concatenates them, and computes the SHA-256 hash. The result is interpreted as a big.Int.

Parameters:

  • a: First input value
  • b: Second input value

Returns: Hash result as *big.Int

func VerifyProofWith ¶ 

func VerifyProofWith[N any](proof MerkleProof[N], hash Hasher[N], eq Equal[N]) bool

VerifyProofWith verifies a proof using the provided hash and equality functions.

Types ¶

type Equal ¶ 

type Equal[N any] func(a, b N) bool

Equal is an optional equality comparator used for leaf lookups and proofs. If nil, reflect.DeepEqual is used.

type Hasher ¶ 

type Hasher[N any] func(a, b N) N

Hasher is the binary hash used for internal nodes.

type LeanIMT ¶ 

type LeanIMT[N any] struct {
	// contains filtered or unexported fields
}

LeanIMT is a binary Lean Incremental Merkle Tree.

  • dynamic depth (ceil(log2(size)))
  • no zero nodes; if a right child is missing, parent = left child
  • proofs omit missing siblings and encode the path as an index integer.

LeanIMT is safe for concurrent use by multiple goroutines.

func Import ¶ 

func Import[N any](hash Hasher[N], nodesJSON string, eq Equal[N], mapFn func(string) (N, error)) (*LeanIMT[N], error)

Import parses a JSON-encoded nodes matrix and returns a new tree. If mapFn is provided, every JSON scalar value that is encoded as a string will be passed through mapFn to build values of type N. If mapFn is nil, Import attempts to unmarshal directly into [][]N.

func New ¶ 

func New[N any](hash Hasher[N], eq Equal[N], storage db.Database, encoder func(N) ([]byte, error), decoder func([]byte) (N, error)) (*LeanIMT[N], error)

New creates a new empty LeanIMT with the provided hash function. If eq is nil, reflect.DeepEqual is used for equality. If storage is nil, the tree operates in memory-only mode. If storage is provided, encoder and decoder functions must also be provided.

Example usage: 

tree, err := New(BigIntHasher, BigIntEqual, nil, nil, nil)                    // in-memory
tree, err := New(BigIntHasher, BigIntEqual, db, BigIntEncoder, BigIntDecoder) // persistent

func NewWithPebble ¶ 

func NewWithPebble[N any](hash Hasher[N], eq Equal[N], encoder func(N) ([]byte, error), decoder func([]byte) (N, error), datadir string) (*LeanIMT[N], error)

NewWithPebble is a wrapper around New. Creates a new LeanIMT using a persistent Pebble DB at the specified directory.

func (*LeanIMT[N]) Close ¶ 

func (t *LeanIMT[N]) Close() error

Close ensures all changes are synced and closes the database connection.

func (*LeanIMT[N]) Depth ¶ 

func (t *LeanIMT[N]) Depth() int

Depth returns the current dynamic depth (levels - 1).

func (*LeanIMT[N]) Export ¶ 

func (t *LeanIMT[N]) Export() (string, error)

Export encodes the internal matrix as JSON. For *big.Int values, this results in JSON strings (via TextMarshaler), matching the TS behavior that stringifies bigints.

func (*LeanIMT[N]) GenerateProof ¶ 

func (t *LeanIMT[N]) GenerateProof(index int) (MerkleProof[N], error)

GenerateProof builds a LeanIMT proof for the leaf at index.

func (*LeanIMT[N]) Has ¶ 

func (t *LeanIMT[N]) Has(leaf N) bool

Has returns true if the leaf is present.

func (*LeanIMT[N]) IndexOf ¶ 

func (t *LeanIMT[N]) IndexOf(leaf N) int

IndexOf returns the index of a leaf by equality; -1 if not present.

func (*LeanIMT[N]) Insert ¶ 

func (t *LeanIMT[N]) Insert(leaf N) int

Insert inserts a single leaf at the end, updating path to root bottom-up.

func (*LeanIMT[N]) InsertMany ¶ 

func (t *LeanIMT[N]) InsertMany(leaves []N) error

InsertMany inserts m leaves in batch (more efficient than m x Insert).

func (*LeanIMT[N]) Leaves ¶ 

func (t *LeanIMT[N]) Leaves() []N

Leaves returns a copy of the leaves array.

func (*LeanIMT[N]) Load ¶ 

func (t *LeanIMT[N]) Load() error

Load restores the tree from persistent storage. It reads all leaves from the database and rebuilds the tree structure.

func (*LeanIMT[N]) Root ¶ 

func (t *LeanIMT[N]) Root() (N, bool)

Root returns the root and a boolean indicating whether it exists.

func (*LeanIMT[N]) Size ¶ 

func (t *LeanIMT[N]) Size() int

Size returns the number of leaves.

func (*LeanIMT[N]) Sync ¶ 

func (t *LeanIMT[N]) Sync() error

Sync persists the current tree state to disk atomically. Only the leaves are stored; intermediate nodes are computed on load.

func (*LeanIMT[N]) Update ¶ 

func (t *LeanIMT[N]) Update(index int, newLeaf N) error

Update replaces the leaf at index with newLeaf and updates path to root.

func (*LeanIMT[N]) UpdateMany ¶ 

func (t *LeanIMT[N]) UpdateMany(indices []int, leaves []N) error

UpdateMany updates multiple leaves efficiently in O(n). It validates indices (range and duplicates).

func (*LeanIMT[N]) VerifyProof ¶ 

func (t *LeanIMT[N]) VerifyProof(proof MerkleProof[N]) bool

VerifyProof verifies a proof against the current tree hash function.

type MerkleProof ¶ 

type MerkleProof[N any] struct {
	Root      N
	Leaf      N
	PathBits  uint64
	LeafIndex uint64
	Siblings  []N
}

MerkleProof contains the fields needed to verify membership: - Root: root at the time of proof - Leaf: the leaf value - PathBits: packed path bits (LSB is first sibling combined) - LeafIndex: absolute leaf position in the tree - Siblings: the sibling nodes included (missing siblings are omitted)

Source Files ¶

View all Source files

Directories ¶

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.