trieutil

Documentation

Index

• func ConcatGeneralizedIndices(indices []int) int
• func GeneralizedIndexBit(index uint64, pos uint64) bool
• func GeneralizedIndexChild(index int, rightSide bool) int
• func GeneralizedIndexLength(index int) int
• func GeneralizedIndexParent(index int) int
• func GeneralizedIndexSibling(index int) int
• func MerkleTree(leaves [][]byte) [][]byte
• func NextPowerOf2(n int) int
• func PrevPowerOf2(n int) int
• func VerifyMerkleProof(root []byte, item []byte, merkleIndex int, proof [][]byte) bool
• type MerkleTrie
  • func GenerateTrieFromItems(items [][]byte, depth int) (*MerkleTrie, error)
  • func NewTrie(depth int) (*MerkleTrie, error)
  • func (m *MerkleTrie) HashTreeRoot() [32]byte
  • func (m *MerkleTrie) InsertIntoTrie(item []byte, index int) error
  • func (m *MerkleTrie) Items() [][]byte
  • func (m *MerkleTrie) MerkleProof(index int) ([][]byte, error)
  • func (m *MerkleTrie) Root() [32]byte

Functions

func ConcatGeneralizedIndices

func ConcatGeneralizedIndices(indices []int) int

ConcatGeneralizedIndices concats the generalized indices together.

Spec pseudocode definition:

def concat_generalized_indices(*indices: GeneralizedIndex) -> GeneralizedIndex:
 """
 Given generalized indices i1 for A -> B, i2 for B -> C .... i_n for Y -> Z, returns
 the generalized index for A -> Z.
 """
 o = GeneralizedIndex(1)
 for i in indices:
     o = GeneralizedIndex(o * get_previous_power_of_two(i) + (i - get_previous_power_of_two(i)))
 return o

func GeneralizedIndexBit

func GeneralizedIndexBit(index uint64, pos uint64) bool

GeneralizedIndexBit returns the given bit of a generalized index.

Spec pseudocode definition:

def get_generalized_index_bit(index: GeneralizedIndex, position: int) -> bool:
 """
 Return the given bit of a generalized index.
 """
 return (index & (1 << position)) > 0

func GeneralizedIndexChild

func GeneralizedIndexChild(index int, rightSide bool) int

GeneralizedIndexChild returns the child of a generalized index.

Spec pseudocode definition:

def generalized_index_child(index: GeneralizedIndex, right_side: bool) -> GeneralizedIndex:
 return GeneralizedIndex(index * 2 + right_side)

func GeneralizedIndexLength

func GeneralizedIndexLength(index int) int

GeneralizedIndexLength returns the generalized index length from a given index.

Spec pseudocode definition:

def get_generalized_index_length(index: GeneralizedIndex) -> int:
 """
 Return the length of a path represented by a generalized index.
 """
 return int(log2(index))

func GeneralizedIndexParent

func GeneralizedIndexParent(index int) int

GeneralizedIndexParent returns the parent of a generalized index.

Spec pseudocode definition:

def generalized_index_parent(index: GeneralizedIndex) -> GeneralizedIndex:
 return GeneralizedIndex(index // 2)

func GeneralizedIndexSibling

func GeneralizedIndexSibling(index int) int

GeneralizedIndexSibling returns the sibling of a generalized index.

Spec pseudocode definition:

def generalized_index_sibling(index: GeneralizedIndex) -> GeneralizedIndex:
 return GeneralizedIndex(index ^ 1)

func MerkleTree

func MerkleTree(leaves [][]byte) [][]byte

MerkleTree returns all the nodes in a merkle tree from inputting merkle leaves.

Spec pseudocode definition:

def merkle_tree(leaves: Sequence[Hash]) -> Sequence[Hash]:
 padded_length = get_next_power_of_two(len(leaves))
 o = [Hash()] * padded_length + list(leaves) + [Hash()] * (padded_length - len(leaves))
 for i in range(padded_length - 1, 0, -1):
     o[i] = hash(o[i * 2] + o[i * 2 + 1])
 return o

func NextPowerOf2

func NextPowerOf2(n int) int

NextPowerOf2 returns the next power of 2 >= the input

Spec pseudocode definition:

def get_next_power_of_two(x: int) -> int:
 """
 Get next power of 2 >= the input.
 """
 if x <= 2:
     return x
 else:
     return 2 * get_next_power_of_two((x + 1) // 2)

func PrevPowerOf2

func PrevPowerOf2(n int) int

PrevPowerOf2 returns the previous power of 2 >= the input

Spec pseudocode definition:

def get_previous_power_of_two(x: int) -> int:
 """
 Get the previous power of 2 >= the input.
 """
 if x <= 2:
     return x
 else:
     return 2 * get_previous_power_of_two(x // 2)

func VerifyMerkleProof

func VerifyMerkleProof(root []byte, item []byte, merkleIndex int, proof [][]byte) bool

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

Types

type MerkleTrie

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

MerkleTrie implements a sparse, general purpose Merkle trie to be used across ETH2.0 Phase 0 functionality.

func GenerateTrieFromItems

func GenerateTrieFromItems(items [][]byte, depth int) (*MerkleTrie, error)

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

func NewTrie

func NewTrie(depth int) (*MerkleTrie, error)

NewTrie returns a new merkle trie filled with zerohashes to use.

func (*MerkleTrie) HashTreeRoot

func (m *MerkleTrie) HashTreeRoot() [32]byte

HashTreeRoot of the Merkle trie as defined in the deposit contract.

Spec Definition:
 sha256(concat(node, self.to_little_endian_64(self.deposit_count), slice(zero_bytes32, start=0, len=24)))

func (*MerkleTrie) InsertIntoTrie

func (m *MerkleTrie) InsertIntoTrie(item []byte, index int) error

InsertIntoTrie inserts an item(deposit hash) into the trie.

func (*MerkleTrie) Items

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

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

func (*MerkleTrie) MerkleProof

func (m *MerkleTrie) MerkleProof(index int) ([][]byte, error)

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

func (*MerkleTrie) Root

func (m *MerkleTrie) Root() [32]byte

Root returns the top-most, Merkle root of the trie.