tendermint: github.com/tendermint/tendermint/crypto/merkle Index | Files

package merkle

import "github.com/tendermint/tendermint/crypto/merkle"

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.

nolint: dupl

Index

Package Files

codec.go doc.go hash.go merkle.pb.go proof.go proof_key_path.go proof_simple_value.go result.go simple_map.go simple_proof.go simple_tree.go types.go

Constants

const (
    KeyEncodingURL keyEncoding = iota
    KeyEncodingHex
    KeyEncodingMax // Number of known encodings. Used for testing
)
const (
    // MaxAunts is the maximum number of aunts that can be included in a SimpleProof.
    // 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
)
const ProofOpSimpleValue = "simple:v"

Variables

var (
    ErrInvalidLengthMerkle = fmt.Errorf("proto: negative length found during unmarshaling")
    ErrIntOverflowMerkle   = fmt.Errorf("proto: integer overflow")
)

func KeyPathToKeys Uses

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.

func SimpleHashFromByteSlices Uses

func SimpleHashFromByteSlices(items [][]byte) []byte

SimpleHashFromByteSlices computes a Merkle tree where the leaves are the byte slice, in the provided order.

func SimpleHashFromByteSlicesIterative Uses

func SimpleHashFromByteSlicesIterative(input [][]byte) []byte

SimpleHashFromByteSliceIterative is an iterative alternative to SimpleHashFromByteSlice motivated by potential performance improvements. (#2611) had suggested that an iterative version of SimpleHashFromByteSlice 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 simple test to assert correctness and a benchmark. On the performance side, there appears to be no overall difference:

BenchmarkSimpleHashAlternatives/recursive-4 20000 77677 ns/op BenchmarkSimpleHashAlternatives/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 SimpleHashFromByteSlice is pretty good 2. Go has low overhead for recursive functions 3. The performance of the SimpleHashFromByteSlice 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 SimpleHashFromMap Uses

func SimpleHashFromMap(m map[string][]byte) []byte

SimpleHashFromMap computes a Merkle tree from sorted map. Like calling SimpleHashFromHashers with `item = []byte(Hash(key) | Hash(value))`, sorted by `item`.

func SimpleProofsFromMap Uses

func SimpleProofsFromMap(m map[string][]byte) (rootHash []byte, proofs map[string]*SimpleProof, keys []string)

SimpleProofsFromMap generates proofs from a map. The keys/values of the map will be used as the keys/values in the underlying key-value pairs. The keys are sorted before the proofs are computed.

type KVPair Uses

type KVPair cmn.KVPair

A local extension to KVPair that can be hashed. Key and value are length prefixed and concatenated, then hashed.

func (KVPair) Bytes Uses

func (kv KVPair) Bytes() []byte

Bytes returns key || value, with both the key and value length prefixed.

type Key Uses

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

type KeyPath Uses

type KeyPath []Key

func (KeyPath) AppendKey Uses

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

func (KeyPath) String Uses

func (pth KeyPath) String() string

type OpDecoder Uses

type OpDecoder func(ProofOp) (ProofOperator, error)

type Proof Uses

type Proof struct {
    Ops                  []ProofOp `protobuf:"bytes,1,rep,name=ops,proto3" json:"ops"`
    XXX_NoUnkeyedLiteral struct{}  `json:"-"`
    XXX_unrecognized     []byte    `json:"-"`
    XXX_sizecache        int32     `json:"-"`
}

Proof is Merkle proof defined by the list of ProofOps

func NewPopulatedProof Uses

func NewPopulatedProof(r randyMerkle, easy bool) *Proof

func (*Proof) Descriptor Uses

func (*Proof) Descriptor() ([]byte, []int)

func (*Proof) Equal Uses

func (this *Proof) Equal(that interface{}) bool

func (*Proof) GetOps Uses

func (m *Proof) GetOps() []ProofOp

func (*Proof) Marshal Uses

func (m *Proof) Marshal() (dAtA []byte, err error)

func (*Proof) MarshalJSON Uses

func (r *Proof) MarshalJSON() ([]byte, error)

func (*Proof) MarshalTo Uses

func (m *Proof) MarshalTo(dAtA []byte) (int, error)

func (*Proof) MarshalToSizedBuffer Uses

func (m *Proof) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*Proof) ProtoMessage Uses

func (*Proof) ProtoMessage()

func (*Proof) Reset Uses

func (m *Proof) Reset()

func (*Proof) Size Uses

func (m *Proof) Size() (n int)

func (*Proof) String Uses

func (m *Proof) String() string

func (*Proof) Unmarshal Uses

func (m *Proof) Unmarshal(dAtA []byte) error

func (*Proof) UnmarshalJSON Uses

func (r *Proof) UnmarshalJSON(b []byte) error

func (*Proof) XXX_DiscardUnknown Uses

func (m *Proof) XXX_DiscardUnknown()

func (*Proof) XXX_Marshal Uses

func (m *Proof) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Proof) XXX_Merge Uses

func (m *Proof) XXX_Merge(src proto.Message)

func (*Proof) XXX_Size Uses

func (m *Proof) XXX_Size() int

func (*Proof) XXX_Unmarshal Uses

func (m *Proof) XXX_Unmarshal(b []byte) error

type ProofOp Uses

type ProofOp struct {
    Type                 string   `protobuf:"bytes,1,opt,name=type,proto3" json:"type,omitempty"`
    Key                  []byte   `protobuf:"bytes,2,opt,name=key,proto3" json:"key,omitempty"`
    Data                 []byte   `protobuf:"bytes,3,opt,name=data,proto3" json:"data,omitempty"`
    XXX_NoUnkeyedLiteral struct{} `json:"-"`
    XXX_unrecognized     []byte   `json:"-"`
    XXX_sizecache        int32    `json:"-"`
}

ProofOp defines an operation used for calculating Merkle root The data could be arbitrary format, providing nessecary data for example neighbouring node hash

func NewPopulatedProofOp Uses

func NewPopulatedProofOp(r randyMerkle, easy bool) *ProofOp

func (*ProofOp) Descriptor Uses

func (*ProofOp) Descriptor() ([]byte, []int)

func (*ProofOp) Equal Uses

func (this *ProofOp) Equal(that interface{}) bool

func (*ProofOp) GetData Uses

func (m *ProofOp) GetData() []byte

func (*ProofOp) GetKey Uses

func (m *ProofOp) GetKey() []byte

func (*ProofOp) GetType Uses

func (m *ProofOp) GetType() string

func (*ProofOp) Marshal Uses

func (m *ProofOp) Marshal() (dAtA []byte, err error)

func (*ProofOp) MarshalJSON Uses

func (r *ProofOp) MarshalJSON() ([]byte, error)

func (*ProofOp) MarshalTo Uses

func (m *ProofOp) MarshalTo(dAtA []byte) (int, error)

func (*ProofOp) MarshalToSizedBuffer Uses

func (m *ProofOp) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*ProofOp) ProtoMessage Uses

func (*ProofOp) ProtoMessage()

func (*ProofOp) Reset Uses

func (m *ProofOp) Reset()

func (*ProofOp) Size Uses

func (m *ProofOp) Size() (n int)

func (*ProofOp) String Uses

func (m *ProofOp) String() string

func (*ProofOp) Unmarshal Uses

func (m *ProofOp) Unmarshal(dAtA []byte) error

func (*ProofOp) UnmarshalJSON Uses

func (r *ProofOp) UnmarshalJSON(b []byte) error

func (*ProofOp) XXX_DiscardUnknown Uses

func (m *ProofOp) XXX_DiscardUnknown()

func (*ProofOp) XXX_Marshal Uses

func (m *ProofOp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*ProofOp) XXX_Merge Uses

func (m *ProofOp) XXX_Merge(src proto.Message)

func (*ProofOp) XXX_Size Uses

func (m *ProofOp) XXX_Size() int

func (*ProofOp) XXX_Unmarshal Uses

func (m *ProofOp) XXX_Unmarshal(b []byte) error

type ProofOperator Uses

type ProofOperator interface {
    Run([][]byte) ([][]byte, error)
    GetKey() []byte
    ProofOp() 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 SimpleValueOpDecoder Uses

func SimpleValueOpDecoder(pop ProofOp) (ProofOperator, error)

type ProofOperators Uses

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 Uses

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

func (ProofOperators) VerifyValue Uses

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

type ProofRuntime Uses

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

func DefaultProofRuntime Uses

func DefaultProofRuntime() (prt *ProofRuntime)

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

func NewProofRuntime Uses

func NewProofRuntime() *ProofRuntime

func (*ProofRuntime) Decode Uses

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

func (*ProofRuntime) DecodeProof Uses

func (prt *ProofRuntime) DecodeProof(proof *Proof) (ProofOperators, error)

func (*ProofRuntime) RegisterOpDecoder Uses

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

func (*ProofRuntime) Verify Uses

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

func (*ProofRuntime) VerifyAbsence Uses

func (prt *ProofRuntime) VerifyAbsence(proof *Proof, 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 Uses

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

type SimpleProof Uses

type SimpleProof struct {
    Total    int      `json:"total"`     // Total number of items.
    Index    int      `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.
}

SimpleProof represents a simple 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 SimpleProofsFromByteSlices Uses

func SimpleProofsFromByteSlices(items [][]byte) (rootHash []byte, proofs []*SimpleProof)

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

func (*SimpleProof) ComputeRootHash Uses

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

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

func (*SimpleProof) String Uses

func (sp *SimpleProof) String() string

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

func (*SimpleProof) StringIndented Uses

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

StringIndented generates a canonical string representation of a SimpleProof.

func (*SimpleProof) ValidateBasic Uses

func (sp *SimpleProof) 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 (*SimpleProof) Verify Uses

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

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

type SimpleProofNode Uses

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

SimpleProofNode 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 (*SimpleProofNode) FlattenAunts Uses

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

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

type SimpleValueOp Uses

type SimpleValueOp struct {

    // To encode in ProofOp.Data
    Proof *SimpleProof `json:"simple_proof"`
    // contains filtered or unexported fields
}

SimpleValueOp 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 aminoHasher. SimpleValueOp should support the hash function as used in aminoHasher. 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 NewSimpleValueOp Uses

func NewSimpleValueOp(key []byte, proof *SimpleProof) SimpleValueOp

func (SimpleValueOp) GetKey Uses

func (op SimpleValueOp) GetKey() []byte

func (SimpleValueOp) ProofOp Uses

func (op SimpleValueOp) ProofOp() ProofOp

func (SimpleValueOp) Run Uses

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

func (SimpleValueOp) String Uses

func (op SimpleValueOp) String() string

type Tree Uses

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.

Package merkle imports 16 packages (graph) and is imported by 27 packages. Updated 2019-11-17. Refresh now. Tools for package owners.