merkle

Documentation

Index

• func WithHashStrategy[T Hashable[T]](hashStrategy func() hash.Hash) func(t *Tree[T])
• type Hashable
• type Node
  • func (n *Node[T]) CalculateHash() ([]byte, error)
  • func (n *Node[T]) String() string
• type Tree
  • func NewTree[T Hashable[T]](values []T, options ...func(t *Tree[T])) (*Tree[T], error)
  • func (t *Tree[T]) Generate(values []T) error
  • func (t *Tree[T]) MarshalText() (text []byte, err error)
  • func (t *Tree[T]) Proof(data T) ([][]byte, []int64, error)
  • func (t *Tree[T]) Rebuild() error
  • func (t *Tree[T]) RootHex() string
  • func (t *Tree[T]) String() string
  • func (t *Tree[T]) Values() []T
  • func (t *Tree[T]) Verify() error
  • func (t *Tree[T]) VerifyData(data T) error

Functions

func WithHashStrategy

func WithHashStrategy[T Hashable[T]](hashStrategy func() hash.Hash) func(t *Tree[T])

WithHashStrategy is used to change the default hash strategy of using sha256 when constructing a new tree.

Types

type Hashable

type Hashable[T any] interface {
	Hash() ([]byte, error)
	Equals(other T) bool
}

Hashable represents the behavior concrete data must exhibit to be used in the markle tree.

type Node

type Node[T Hashable[T]] struct {
	Tree   *Tree[T]
	Parent *Node[T]
	Left   *Node[T]
	Right  *Node[T]
	Hash   []byte
	Value  T
	// contains filtered or unexported fields
}

Node represents a node, root, or leaf in the tree. It stores pointers to its immediate relationships, a hash, the data if it is a leaf, and other metadata.

func (*Node[T]) CalculateHash

func (n *Node[T]) CalculateHash() ([]byte, error)

CalculateHash is a helper function that calculates the hash of the node.

func (*Node[T]) String

func (n *Node[T]) String() string

String returns a string representation of the node.

type Tree

type Tree[T Hashable[T]] struct {
	Root       *Node[T]
	Leafs      []*Node[T]
	MerkleRoot []byte
	// contains filtered or unexported fields
}

Tree represents a merkle tree that uses data of some type T that exhibits the behavior define by the Hashable construct.

func NewTree

func NewTree[T Hashable[T]](values []T, options ...func(t *Tree[T])) (*Tree[T], error)

NewTree constructs a new merkle tree that uses data of some type T that exhibits the behavior defined by the Hashable interface.

func (*Tree[T]) Generate

func (t *Tree[T]) Generate(values []T) error

Generate constructs the leafs and nodes of the tree from the specified data. If the tree has been generated previously, the tree is re-generated from scratch.

func (*Tree[T]) MarshalText

func (t *Tree[T]) MarshalText() (text []byte, err error)

MarshalText implements the TextMarshaler interface and produces a panic if anyone tries to marshal the Merkle tree. I don't want this to happen. Use the Values function to return a slice that can be marshaled.

func (*Tree[T]) Proof

func (t *Tree[T]) Proof(data T) ([][]byte, []int64, error)

Proof returns the set of hashes and the order of concatenating those hashes for proving a transaction is in the tree. This is how you can use the information returned by this function.

Hash the data in question and know the merkle tree root hash. dataHash = "0x8e4c64afaeb4e6210a65eb7a54e51d90d20112a4c085209d3db12f0597f16fd6" merkle_root = "0xbc43b5296b8adc75aea5f1d9220bf3bc9dc0dbed9a75d367784b50a7bbbd1211"

Given this proof and proof order from this function for the data in question. proof = [

"0x23d2d2f2a0cbfb260492d42604728cdf8fd63b7d84e4a58094b90dbdd103cd23",
"0xdf25fb5ab5d1373ed6e260ead0a5c7b5fc78b0e9ccf9e09407a67bd2faaf3120",
"0x9dc3d2d31256f20044646614d0a6326627ccc5f1c42019c552c5929a5b9170f3"]

proof_order = [0, 1, 1]

Process the dataHash against the proof like this. bytes = concat(proof[0], dataHash) -- Order 0 says proof comes first.

sha1 = sha256.Sum256(bytes)

bytes = concat(sha1, proof[1]) -- Order 1 says proof comes second.

sha2 = sha256.Sum256(bytes)

bytes = concat(sha2, proof[2]) -- Order 1 says proof comes second.

root = sha256.Sum256(bytes)

The calculated root should match merkle_root.

func (*Tree[T]) Rebuild

func (t *Tree[T]) Rebuild() error

Rebuild is a helper function that will rebuild the tree reusing only the data that it currently holds in the leaves.

func (*Tree[T]) RootHex

func (t *Tree[T]) RootHex() string

RootHex converts the merkle root byte hash to a hex encoded string.

func (*Tree[T]) String

func (t *Tree[T]) String() string

String returns a string representation of the tree. Only leaf nodes are included in the output.

func (*Tree[T]) Values

func (t *Tree[T]) Values() []T

Values returns a slice of unique values stores in the tree.

func (*Tree[T]) Verify

func (t *Tree[T]) Verify() error

Verify validates the hashes at each level of the tree and returns true if the resulting hash at the root of the tree matches the resulting root hash.

func (*Tree[T]) VerifyData

func (t *Tree[T]) VerifyData(data T) error

VerifyData indicates whether a given piece of data is in the tree and if the hashes are valid for that data. Returns true if the expected merkle root is equivalent to the merkle root calculated on the critical path for a given piece of data.