merkle

package
v0.31.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 2, 2019 License: Apache-2.0 Imports: 13 Imported by: 0

README

Simple 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.

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 ProofOpSimpleValue = "simple:v"

Variables

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

Functions

func KeyPathToKeys added in v0.27.4 

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 added in v0.27.4 

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

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

func SimpleHashFromMap 

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 

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.

Types

type KVPair 

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 added in v0.27.4 

func (kv KVPair) Bytes() []byte

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

type Key added in v0.27.4 

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

type KeyPath added in v0.27.4 

type KeyPath []Key

func (KeyPath) AppendKey added in v0.27.4 

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

func (KeyPath) String added in v0.27.4 

func (pth KeyPath) String() string

type OpDecoder added in v0.27.4 

type OpDecoder func(ProofOp) (ProofOperator, error)

type Proof added in v0.27.4 

type Proof struct {
	Ops                  []ProofOp `protobuf:"bytes,1,rep,name=ops" 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 added in v0.27.4 

func NewPopulatedProof(r randyMerkle, easy bool) *Proof

func (*Proof) Descriptor added in v0.27.4 

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

func (*Proof) Equal added in v0.27.4 

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

func (*Proof) GetOps added in v0.27.4 

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

func (*Proof) Marshal added in v0.27.4 

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

func (*Proof) MarshalTo added in v0.27.4 

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

func (*Proof) ProtoMessage added in v0.27.4 

func (*Proof) ProtoMessage()

func (*Proof) Reset added in v0.27.4 

func (m *Proof) Reset()

func (*Proof) Size added in v0.27.4 

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

func (*Proof) String added in v0.27.4 

func (m *Proof) String() string

func (*Proof) Unmarshal added in v0.27.4 

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

func (*Proof) XXX_DiscardUnknown added in v0.27.4 

func (m *Proof) XXX_DiscardUnknown()

func (*Proof) XXX_Marshal added in v0.27.4 

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

func (*Proof) XXX_Merge added in v0.27.4 

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

func (*Proof) XXX_Size added in v0.27.4 

func (m *Proof) XXX_Size() int

func (*Proof) XXX_Unmarshal added in v0.27.4 

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

type ProofOp added in v0.27.4 

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 added in v0.27.4 

func NewPopulatedProofOp(r randyMerkle, easy bool) *ProofOp

func (*ProofOp) Descriptor added in v0.27.4 

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

func (*ProofOp) Equal added in v0.27.4 

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

func (*ProofOp) GetData added in v0.27.4 

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

func (*ProofOp) GetKey added in v0.27.4 

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

func (*ProofOp) GetType added in v0.27.4 

func (m *ProofOp) GetType() string

func (*ProofOp) Marshal added in v0.27.4 

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

func (*ProofOp) MarshalTo added in v0.27.4 

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

func (*ProofOp) ProtoMessage added in v0.27.4 

func (*ProofOp) ProtoMessage()

func (*ProofOp) Reset added in v0.27.4 

func (m *ProofOp) Reset()

func (*ProofOp) Size added in v0.27.4 

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

func (*ProofOp) String added in v0.27.4 

func (m *ProofOp) String() string

func (*ProofOp) Unmarshal added in v0.27.4 

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

func (*ProofOp) XXX_DiscardUnknown added in v0.27.4 

func (m *ProofOp) XXX_DiscardUnknown()

func (*ProofOp) XXX_Marshal added in v0.27.4 

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

func (*ProofOp) XXX_Merge added in v0.27.4 

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

func (*ProofOp) XXX_Size added in v0.27.4 

func (m *ProofOp) XXX_Size() int

func (*ProofOp) XXX_Unmarshal added in v0.27.4 

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

type ProofOperator added in v0.27.4 

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 added in v0.27.4 

func SimpleValueOpDecoder(pop ProofOp) (ProofOperator, error)

type ProofOperators added in v0.27.4 

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 added in v0.27.4 

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

func (ProofOperators) VerifyValue added in v0.27.4 

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

type ProofRuntime added in v0.27.4 

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

func DefaultProofRuntime added in v0.27.4 

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 added in v0.27.4 

func NewProofRuntime() *ProofRuntime

func (*ProofRuntime) Decode added in v0.27.4 

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

func (*ProofRuntime) DecodeProof added in v0.27.4 

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

func (*ProofRuntime) RegisterOpDecoder added in v0.27.4 

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

func (*ProofRuntime) Verify added in v0.27.4 

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

func (*ProofRuntime) VerifyAbsence added in v0.27.4 

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 added in v0.27.4 

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

type SimpleProof 

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 added in v0.27.4 

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 added in v0.27.4 

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

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

func (*SimpleProof) String 

func (sp *SimpleProof) String() string

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

func (*SimpleProof) StringIndented 

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

StringIndented generates a canonical string representation of a SimpleProof.

func (*SimpleProof) Verify 

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

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

type SimpleProofNode 

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 

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 added in v0.27.4 

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 added in v0.27.4 

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

func (SimpleValueOp) GetKey added in v0.27.4 

func (op SimpleValueOp) GetKey() []byte

func (SimpleValueOp) ProofOp added in v0.27.4 

func (op SimpleValueOp) ProofOp() ProofOp

func (SimpleValueOp) Run added in v0.27.4 

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

func (SimpleValueOp) String added in v0.27.4 

func (op SimpleValueOp) String() string

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.