trie

Documentation

Overview

Package trie defines utilities for sparse merkle tries for Ethereum consensus.

Index

• Constants
• func VerifyMerkleProof(root, leaf []byte, merkleIndex uint64, proof [][]byte) bool
• func VerifyMerkleProofWithDepth(root, item []byte, merkleIndex uint64, proof [][]byte, depth uint64) bool
• type SparseMerkleTrie
  • func NewFromItems(items [][]byte, depth uint64) (*SparseMerkleTrie, error)
  • func (m *SparseMerkleTrie) Copy() *SparseMerkleTrie
  • func (m *SparseMerkleTrie) HashTreeRoot() ([32]byte, error)
  • func (m *SparseMerkleTrie) Insert(item []byte, index int) error
  • func (m *SparseMerkleTrie) Items() [][]byte
  • func (m *SparseMerkleTrie) MerkleProof(index uint64) ([][]byte, error)
  • func (m *SparseMerkleTrie) NumOfItems() int

Constants

const (
	// 2^63 would overflow.
	MaxTrieDepth = 62
)

Functions

func VerifyMerkleProof

func VerifyMerkleProof(
	root, leaf []byte,
	merkleIndex uint64,
	proof [][]byte,
) bool

VerifyMerkleProof given a trie root, a leaf, the generalized merkle index of the leaf in the trie, and the proof itself.

func VerifyMerkleProofWithDepth

func VerifyMerkleProofWithDepth(
	root, item []byte,
	merkleIndex uint64,
	proof [][]byte,
	depth uint64,
) bool

VerifyMerkleProofWithDepth verifies a Merkle branch against a root of a trie.

Types

type SparseMerkleTrie

type SparseMerkleTrie struct {
	// contains filtered or unexported fields
}

SparseMerkleTrie implements a sparse, general purpose Merkle trie to be used across Ethereum consensus functionality.

func NewFromItems

func NewFromItems(
	items [][]byte,
	depth uint64,
) (*SparseMerkleTrie, error)

NewFromItems constructs a Merkle trie from a sequence of byte slices.

func (*SparseMerkleTrie) Copy

func (m *SparseMerkleTrie) Copy() *SparseMerkleTrie

Copy performs a deep copy of the trie.

func (*SparseMerkleTrie) HashTreeRoot

func (m *SparseMerkleTrie) HashTreeRoot() ([32]byte, error)

HashTreeRoot returns the hash root of the Merkle trie defined in the deposit contract.

func (*SparseMerkleTrie) Insert

func (m *SparseMerkleTrie) Insert(item []byte, index int) error

Insert an item into the trie.

func (*SparseMerkleTrie) Items

func (m *SparseMerkleTrie) Items() [][]byte

Items returns the original items passed in when creating the Merkle trie.

func (*SparseMerkleTrie) MerkleProof

func (m *SparseMerkleTrie) MerkleProof(index uint64) ([][]byte, error)

MerkleProof computes a proof from a trie's branches using a Merkle index.

func (*SparseMerkleTrie) NumOfItems

func (m *SparseMerkleTrie) NumOfItems() int

NumOfItems returns the num of items stored in the sparse merkle trie. We handle a special case where if there is only one item stored and it is an empty 32-byte root.