Documentation
¶
Overview ¶
Package merkle provides an implementation of a merkel tree for validation support for the blockchain.
Index ¶
- func WithHashStrategy[T Hashable[T]](hashStrategy func() hash.Hash) func(t *Tree[T])
- type Hashable
- type Node
- type Tree
- 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
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Hashable ¶
Hashable represents the behavior concrete data must exhibit to be used in the merkle 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 ¶
CalculateHash is a helper function that calculates the hash 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 defined by the Hashable constraint.
func NewTree ¶
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 ¶
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 ¶
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 ¶
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 ¶
Rebuild is a helper function that will rebuild the tree reusing only the data that it currently holds in the leaves.
func (*Tree[T]) 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. The last value in the tree might be a duplicate when there are an odd number of actual values.
func (*Tree[T]) Verify ¶
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 ¶
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.
Source Files