smt

README

Sparse Merkle Tree Implementation in Go

This repository contains an implementation of a Sparse Merkle Tree (SMT) in Go. An SMT is a kind of Merkle Tree, which is a tree of hashes where each non-leaf node is the hash of its children. Sparse Merkle Trees are 'sparse' because they are very large (often having 2^256 nodes) but are almost entirely empty.

This implementation is highly memory efficient because it only stores non-empty leaves, making it ideal for situations where the tree is mostly empty.

Key Features

• Sparse Merkle Tree representation: Contains the root node, depth, and a map of leaves.
• Merkle path generation and verification: Allows the generation of a Merkle path for a given leaf key, and can verify a provided Merkle path against an expected root hash.
• Leaf insertion: Supports the insertion of leaves at specific indexes.
• Deterministic Sparse Merkle Tree creation: Creates deterministic Sparse Merkle Trees with non-null leaves.

Code Structure

The repository includes the following important components:

• smt.go: Contains the main implementation of the Sparse Merkle Tree, including the definition of the tree structure, leaf insertion, and Merkle path generation and verification.
• helpers.go: Contains helper functions for the SMT implementation, such as functions for calculating the hash of an empty node, getting a padded binary string of a given integer, and more.

Installation and Usage

The code is written in Go, so you'll need to have Go installed on your machine to use it. You can download Go from the official Go website.

To use this code in your project, simply import the smt package.

import "github.com/pycckuu/smt"

You can then create a new Sparse Merkle Tree like so:

tree := smt.NewSparseMerkleTree(depth, zeroLeaf)

Where depth is the desired depth of your tree and zeroLeaf is the hash of the zero leaf.

To insert a new leaf into the tree:

tree.Insert(index, value)

Where index is the index at which to insert the new leaf and value is the value of the new leaf.

To generate a Merkle path for a given leaf index:

path, err := tree.GenerateMerklePath(index)

And to verify a Merkle path against an expected root:

valid := smt.VerifyMerklePath(leafHash, path, expectedRoot)

Contributions

Contributions to the repository are welcome! Please submit a pull request with your changes.

License

This project is licensed under the MIT License.

Documentation

Index

• func VerifyMerklePath(leafHash *big.Int, path []*MerklePathItem, expectedRoot *big.Int) bool
• type MerkleNode
• type MerklePathItem
• type SparseMerkleTree
  • func NewDeterministicSparseMerkleTree(depth int, zeroLeaf *big.Int) *SparseMerkleTree
  • func NewSparseMerkleTree(depth int, zeroLeaf *big.Int) *SparseMerkleTree
  • func (smt *SparseMerkleTree) GenerateMerklePath(index int) ([]*MerklePathItem, error)
  • func (smt *SparseMerkleTree) Insert(index int, value *big.Int)

Functions

func VerifyMerklePath

func VerifyMerklePath(leafHash *big.Int, path []*MerklePathItem, expectedRoot *big.Int) bool

VerifyMerklePath verifies a Merkle tree path against the expected root hash.

Types

type MerkleNode

type MerkleNode struct {
	Left  *MerkleNode // Left child of the current node.
	Right *MerkleNode // Right child of the current node.
	Data  *big.Int    // Hash of the current node.
}

MerkleNode represents an individual node in the Merkle Tree.

type MerklePathItem

type MerklePathItem struct {
	SiblingHash *big.Int // Hash of the sibling in the Merkle Path.
	IsRight     bool     // Indicates whether this sibling node is a right child.
}

MerklePathItem represents an item in the Merkle tree path.

type SparseMerkleTree

type SparseMerkleTree struct {
	Root     *MerkleNode         // The root node of the Sparse Merkle Tree.
	Depth    int                 // The depth of the Sparse Merkle Tree.
	Leaves   map[string]*big.Int // The leaves of the Sparse Merkle Tree, where keys are the binary representation of the index.
	ZeroLeaf *big.Int            // Hash of the zero leaf.
}

SparseMerkleTree represents a sparse Merkle tree.

func NewDeterministicSparseMerkleTree

func NewDeterministicSparseMerkleTree(depth int, zeroLeaf *big.Int) *SparseMerkleTree

NewDeterministicSparseMerkleTree creates a new deterministic sparse Merkle tree with non-null leaves.

func NewSparseMerkleTree

func NewSparseMerkleTree(depth int, zeroLeaf *big.Int) *SparseMerkleTree

NewSparseMerkleTree creates a new sparse Merkle tree with empty leaves.

func (*SparseMerkleTree) GenerateMerklePath

func (smt *SparseMerkleTree) GenerateMerklePath(index int) ([]*MerklePathItem, error)

GenerateMerklePath generates a Merkle tree path for the leaf with the given index.

func (*SparseMerkleTree) Insert

func (smt *SparseMerkleTree) Insert(index int, value *big.Int)

Insert inserts a leaf with the given index and value into the tree.