README

Merkle Tree

For smaller static data structures that don't require immutable snapshots or mutability; for instance the transactions and validation signatures of a block can be hashed using this simple merkle tree logic.

Expand ▾ Collapse ▴

Documentation

Overview

    Package merkle computes a deterministic minimal height Merkle tree hash. If the number of items is not a power of two, some leaves will be at different levels. Tries to keep both sides of the tree the same size, but the left may be one greater.

    Use this for short deterministic trees, such as the validator list. For larger datasets, use IAVLTree.

    Be aware that the current implementation by itself does not prevent second pre-image attacks. Hence, use this library with caution. Otherwise you might run into similar issues as, e.g., in early Bitcoin: https://bitcointalk.org/?topic=102395

                  *
                 / \
               /     \
             /         \
           /             \
          *               *
         / \             / \
        /   \           /   \
       /     \         /     \
      *       *       *       h6
     / \     / \     / \
    h0  h1  h2  h3  h4  h5
    

    TODO(ismail): add 2nd pre-image protection or clarify further on how we use this and why this secure.

    Index

    Constants

    View Source
    const (
    	KeyEncodingURL keyEncoding = iota
    	KeyEncodingHex
    	KeyEncodingMax // Number of known encodings. Used for testing
    )
    View Source
    const (
    	// MaxAunts is the maximum number of aunts that can be included in a Proof.
    	// This corresponds to a tree of size 2^100, which should be sufficient for all conceivable purposes.
    	// This maximum helps prevent Denial-of-Service attacks by limitting the size of the proofs.
    	MaxAunts = 100
    )
    View Source
    const ProofOpValue = "simple:v"

    Variables

    This section is empty.

    Functions

    func HashFromByteSlices

    func HashFromByteSlices(items [][]byte) []byte

      HashFromByteSlices computes a Merkle tree where the leaves are the byte slice, in the provided order. It follows RFC-6962.

      func HashFromByteSlicesIterative

      func HashFromByteSlicesIterative(input [][]byte) []byte

        HashFromByteSliceIterative is an iterative alternative to HashFromByteSlice motivated by potential performance improvements. (#2611) had suggested that an iterative version of HashFromByteSlice would be faster, presumably because we can envision some overhead accumulating from stack frames and function calls. Additionally, a recursive algorithm risks hitting the stack limit and causing a stack overflow should the tree be too large.

        Provided here is an iterative alternative, a test to assert correctness and a benchmark. On the performance side, there appears to be no overall difference:

        BenchmarkHashAlternatives/recursive-4 20000 77677 ns/op BenchmarkHashAlternatives/iterative-4 20000 76802 ns/op

        On the surface it might seem that the additional overhead is due to the different allocation patterns of the implementations. The recursive version uses a single [][]byte slices which it then re-slices at each level of the tree. The iterative version reproduces [][]byte once within the function and then rewrites sub-slices of that array at each level of the tree.

        Experimenting by modifying the code to simply calculate the hash and not store the result show little to no difference in performance.

        These preliminary results suggest:

        1. The performance of the HashFromByteSlice is pretty good 2. Go has low overhead for recursive functions 3. The performance of the HashFromByteSlice routine is dominated

        by the actual hashing of data
        

        Although this work is in no way exhaustive, point #3 suggests that optimization of this routine would need to take an alternative approach to make significant improvements on the current performance.

        Finally, considering that the recursive implementation is easier to read, it might not be worthwhile to switch to a less intuitive implementation for so little benefit.

        func KeyPathToKeys

        func KeyPathToKeys(path string) (keys [][]byte, err error)

          Decode a path to a list of keys. Path must begin with `/`. Each key must use a known encoding.

          Types

          type Key

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

          type KeyPath

          type KeyPath []Key

          func (KeyPath) AppendKey

          func (pth KeyPath) AppendKey(key []byte, enc keyEncoding) KeyPath

          func (KeyPath) String

          func (pth KeyPath) String() string

          type OpDecoder

          type OpDecoder func(tmcrypto.ProofOp) (ProofOperator, error)

          type Proof

          type Proof struct {
          	Total    int64    `json:"total"`     // Total number of items.
          	Index    int64    `json:"index"`     // Index of item to prove.
          	LeafHash []byte   `json:"leaf_hash"` // Hash of item value.
          	Aunts    [][]byte `json:"aunts"`     // Hashes from leaf's sibling to a root's child.
          }

            Proof represents a Merkle proof. NOTE: The convention for proofs is to include leaf hashes but to exclude the root hash. This convention is implemented across IAVL range proofs as well. Keep this consistent unless there's a very good reason to change everything. This also affects the generalized proof system as well.

            func ProofFromProto

            func ProofFromProto(pb *tmcrypto.Proof) (*Proof, error)

            func ProofsFromByteSlices

            func ProofsFromByteSlices(items [][]byte) (rootHash []byte, proofs []*Proof)

              ProofsFromByteSlices computes inclusion proof for given items. proofs[0] is the proof for items[0].

              func (*Proof) ComputeRootHash

              func (sp *Proof) ComputeRootHash() []byte

                Compute the root hash given a leaf hash. Does not verify the result.

                func (*Proof) String

                func (sp *Proof) String() string

                  String implements the stringer interface for Proof. It is a wrapper around StringIndented.

                  func (*Proof) StringIndented

                  func (sp *Proof) StringIndented(indent string) string

                    StringIndented generates a canonical string representation of a Proof.

                    func (*Proof) ToProto

                    func (sp *Proof) ToProto() *tmcrypto.Proof

                    func (*Proof) ValidateBasic

                    func (sp *Proof) ValidateBasic() error

                      ValidateBasic performs basic validation. NOTE: it expects the LeafHash and the elements of Aunts to be of size tmhash.Size, and it expects at most MaxAunts elements in Aunts.

                      func (*Proof) Verify

                      func (sp *Proof) Verify(rootHash []byte, leaf []byte) error

                        Verify that the Proof proves the root hash. Check sp.Index/sp.Total manually if needed

                        type ProofNode

                        type ProofNode struct {
                        	Hash   []byte
                        	Parent *ProofNode
                        	Left   *ProofNode // Left sibling  (only one of Left,Right is set)
                        	Right  *ProofNode // Right sibling (only one of Left,Right is set)
                        }

                          ProofNode is a helper structure to construct merkle proof. The node and the tree is thrown away afterwards. Exactly one of node.Left and node.Right is nil, unless node is the root, in which case both are nil. node.Parent.Hash = hash(node.Hash, node.Right.Hash) or hash(node.Left.Hash, node.Hash), depending on whether node is a left/right child.

                          func (*ProofNode) FlattenAunts

                          func (spn *ProofNode) FlattenAunts() [][]byte

                            FlattenAunts will return the inner hashes for the item corresponding to the leaf, starting from a leaf ProofNode.

                            type ProofOperator

                            type ProofOperator interface {
                            	Run([][]byte) ([][]byte, error)
                            	GetKey() []byte
                            	ProofOp() tmcrypto.ProofOp
                            }

                              ProofOperator is a layer for calculating intermediate Merkle roots when a series of Merkle trees are chained together. Run() takes leaf values from a tree and returns the Merkle root for the corresponding tree. It takes and returns a list of bytes to allow multiple leaves to be part of a single proof, for instance in a range proof. ProofOp() encodes the ProofOperator in a generic way so it can later be decoded with OpDecoder.

                              func ValueOpDecoder

                              func ValueOpDecoder(pop tmcrypto.ProofOp) (ProofOperator, error)

                              type ProofOperators

                              type ProofOperators []ProofOperator

                                ProofOperators is a slice of ProofOperator(s). Each operator will be applied to the input value sequentially and the last Merkle root will be verified with already known data

                                func (ProofOperators) Verify

                                func (poz ProofOperators) Verify(root []byte, keypath string, args [][]byte) (err error)

                                func (ProofOperators) VerifyValue

                                func (poz ProofOperators) VerifyValue(root []byte, keypath string, value []byte) (err error)

                                type ProofRuntime

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

                                func DefaultProofRuntime

                                func DefaultProofRuntime() (prt *ProofRuntime)

                                  DefaultProofRuntime only knows about value proofs. To use e.g. IAVL proofs, register op-decoders as defined in the IAVL package.

                                  func NewProofRuntime

                                  func NewProofRuntime() *ProofRuntime

                                  func (*ProofRuntime) Decode

                                  func (prt *ProofRuntime) Decode(pop tmcrypto.ProofOp) (ProofOperator, error)

                                  func (*ProofRuntime) DecodeProof

                                  func (prt *ProofRuntime) DecodeProof(proof *tmcrypto.ProofOps) (ProofOperators, error)

                                  func (*ProofRuntime) RegisterOpDecoder

                                  func (prt *ProofRuntime) RegisterOpDecoder(typ string, dec OpDecoder)

                                  func (*ProofRuntime) Verify

                                  func (prt *ProofRuntime) Verify(proof *tmcrypto.ProofOps, root []byte, keypath string, args [][]byte) (err error)

                                  func (*ProofRuntime) VerifyAbsence

                                  func (prt *ProofRuntime) VerifyAbsence(proof *tmcrypto.ProofOps, root []byte, keypath string) (err error)

                                    TODO In the long run we'll need a method of classifcation of ops, whether existence or absence or perhaps a third?

                                    func (*ProofRuntime) VerifyValue

                                    func (prt *ProofRuntime) VerifyValue(proof *tmcrypto.ProofOps, root []byte, keypath string, value []byte) (err error)

                                    type Tree

                                    type Tree interface {
                                    	Size() (size int)
                                    	Height() (height int8)
                                    	Has(key []byte) (has bool)
                                    	Proof(key []byte) (value []byte, proof []byte, exists bool) // TODO make it return an index
                                    	Get(key []byte) (index int, value []byte, exists bool)
                                    	GetByIndex(index int) (key []byte, value []byte)
                                    	Set(key []byte, value []byte) (updated bool)
                                    	Remove(key []byte) (value []byte, removed bool)
                                    	HashWithCount() (hash []byte, count int)
                                    	Hash() (hash []byte)
                                    	Save() (hash []byte)
                                    	Load(hash []byte)
                                    	Copy() Tree
                                    	Iterate(func(key []byte, value []byte) (stop bool)) (stopped bool)
                                    	IterateRange(start []byte, end []byte, ascending bool, fx func(key []byte, value []byte) (stop bool)) (stopped bool)
                                    }

                                      Tree is a Merkle tree interface.

                                      type ValueOp

                                      type ValueOp struct {
                                      
                                      	// To encode in ProofOp.Data
                                      	Proof *Proof `json:"proof"`
                                      	// contains filtered or unexported fields
                                      }

                                        ValueOp takes a key and a single value as argument and produces the root hash. The corresponding tree structure is the SimpleMap tree. SimpleMap takes a Hasher, and currently Tendermint uses tmhash. SimpleValueOp should support the hash function as used in tmhash. TODO support additional hash functions here as options/args to this operator.

                                        If the produced root hash matches the expected hash, the proof is good.

                                        func NewValueOp

                                        func NewValueOp(key []byte, proof *Proof) ValueOp

                                        func (ValueOp) GetKey

                                        func (op ValueOp) GetKey() []byte

                                        func (ValueOp) ProofOp

                                        func (op ValueOp) ProofOp() tmcrypto.ProofOp

                                        func (ValueOp) Run

                                        func (op ValueOp) Run(args [][]byte) ([][]byte, error)

                                        func (ValueOp) String

                                        func (op ValueOp) String() string