merkle

Documentation

Index

• Constants
• func CalculateMerkleRoot(proof *SimplifiedMMRProof, leafHash types.H256) types.H256
• func GenerateMerkleProof(inputPreLeaves [][]byte, leafIndex int64) ([]byte, []byte, [][32]byte, error)
• func Prove(preLeaf, root []byte, path []*Node, h Hasher) bool
• type Hasher
• type Node
  • func (n *Node) MarshalJSON() ([]byte, error)
  • func (n *Node) UnmarshalJSON(data []byte) error
• type SimplifiedMMRProof
  • func ConvertToSimplifiedMMRProof(blockhash types.H256, leafIndex uint64, leaf types.MMRLeaf, leafCount uint64, ...) (SimplifiedMMRProof, error)
• type Tree
  • func NewTree() *Tree
  • func (t *Tree) Depth() int
  • func (t *Tree) Hash(preLeaves [][]byte, h Hasher) error
  • func (t *Tree) MerklePath(preLeaf []byte) []*Node
  • func (t *Tree) Root() []byte

Constants

const (
	PositionLeft  = "left"
	PositionRight = "right"
)

Position constants are used in merkle path nodes to denote whether the node was a left child or right child. This allows hash concatenation can be performed correctly.

Functions

func CalculateMerkleRoot

func CalculateMerkleRoot(proof *SimplifiedMMRProof, leafHash types.H256) types.H256

used to verify correctness of generated proofs

func GenerateMerkleProof

func GenerateMerkleProof(inputPreLeaves [][]byte, leafIndex int64) ([]byte, []byte, [][32]byte, error)

func Prove

func Prove(preLeaf, root []byte, path []*Node, h Hasher) bool

Prove is used to confirm that a leaf is contained within a merkle tree. It does not require the full tree, only the leaf and root hashes, the merkle path, and the hash function used. The merkle path can be retrieved from a node in the P2P network that has a copy of the full tree.

Types

type Hasher

type Hasher interface {
	// Hash calculates the hash of a given input
	Hash([]byte) []byte
}

type Node

type Node struct {
	Hash     []byte `json:"hash"`
	Position string `json:"position"`
}

Node is used to represent the steps of a merkle path. This structure is not used within the Tree structure.

func (*Node) MarshalJSON

func (n *Node) MarshalJSON() ([]byte, error)

The Hash value is encoded into a base64 string

func (*Node) UnmarshalJSON

func (n *Node) UnmarshalJSON(data []byte) error

The Hash value is decoded from a base64 encoded string

type SimplifiedMMRProof

type SimplifiedMMRProof struct {
	MerkleProofItems []types.H256
	// Bitfield of the order in which each proof item should be hashed,
	// either left (1) or right (0).
	MerkleProofOrder uint64
	// Below fields are not part of proof directly, but they are included so that
	// we do not lose any information when converting from RPC response
	Blockhash types.H256
	// MMRLeaf in substrate with leaf_extra as merkle root of ParachainHeads
	// https://github.com/paritytech/substrate/blob/ea387c634715793f806286abf1e64cabf9b7026f/frame/beefy-mmr/src/lib.rs#L149-L156
	Leaf types.MMRLeaf
}

func ConvertToSimplifiedMMRProof

func ConvertToSimplifiedMMRProof(blockhash types.H256, leafIndex uint64, leaf types.MMRLeaf, leafCount uint64, proofItems []types.H256) (SimplifiedMMRProof, error)

SimplifiedMMRProof is pre-processed MMR proof format which makes it easy to verify in Solidity Original MMRProof is generated in substrate with https://github.com/nervosnetwork/merkle-mountain-range The optimization works by pre-calculating order of the merkle tree proof so that we don't have to use mathematic operation to determine the same on solidity side More details in https://github.com/Snowfork/snowbridge/pull/495

type Tree

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

Tree is the merkle tree structure. It is implemented as an array of arrays of arrays of bytes:

[
  [ root digest ],
  [ digest, digest ],
  [ digest, digest, digest, digest],
  ...
  [ leaf, leaf, leaf, leaf, ... ]
]

func NewTree

func NewTree() *Tree

func (*Tree) Depth

func (t *Tree) Depth() int

Depth returns the number of edges from the root to the leaf nodes

func (*Tree) Hash

func (t *Tree) Hash(preLeaves [][]byte, h Hasher) error

Hash creates a merkle tree from an array of pre-leaves. Pre-leaves are represented as an array of bytes.

func (*Tree) MerklePath

func (t *Tree) MerklePath(preLeaf []byte) []*Node

MerklePath generates an authentication path for the leaf. If the leaf is not contained in the tree than the return value is nil.

func (*Tree) Root

func (t *Tree) Root() []byte

Root returns the root hash of the tree or nil if it hasn't been hashed.