merkletree2

package
v4.6.1+incompatible Latest Latest
Warning

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

 Go to latest Published: Oct 14, 2019 License: BSD-3-Clause, BSD-3-Clause Imports: 10 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlindedSHA512_256v1Encoder 

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

BlindedSHA512_256v1Encoder is not safe for concurrent use.

func NewBlindedSHA512_256v1Encoder 

func NewBlindedSHA512_256v1Encoder() BlindedSHA512_256v1Encoder

func (BlindedSHA512_256v1Encoder) ComputeKeySpecificSecret 

func (e BlindedSHA512_256v1Encoder) ComputeKeySpecificSecret(ms MasterSecret, k Key) KeySpecificSecret

func (BlindedSHA512_256v1Encoder) Decode 

func (e BlindedSHA512_256v1Encoder) Decode(dest interface{}, src []byte) error

func (BlindedSHA512_256v1Encoder) Encode 

func (e BlindedSHA512_256v1Encoder) Encode(o interface{}) (out []byte, err error)

func (BlindedSHA512_256v1Encoder) EncodeAndHashGeneric 

func (e BlindedSHA512_256v1Encoder) EncodeAndHashGeneric(o interface{}) ([]byte, Hash, error)

func (BlindedSHA512_256v1Encoder) GenerateMasterSecret 

func (e BlindedSHA512_256v1Encoder) GenerateMasterSecret(Seqno) (MasterSecret, error)

func (BlindedSHA512_256v1Encoder) HashKeyEncodedValuePairWithKeySpecificSecret 

func (e BlindedSHA512_256v1Encoder) HashKeyEncodedValuePairWithKeySpecificSecret(kevp KeyEncodedValuePair, kss KeySpecificSecret) (Hash, error)

func (BlindedSHA512_256v1Encoder) HashKeyValuePairWithKeySpecificSecret 

func (e BlindedSHA512_256v1Encoder) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, kss KeySpecificSecret) (Hash, error)

type ChildIndex 

type ChildIndex int

ChildIndex specifies one of an iNode's child nodes.

type Config 

type Config struct {
	// An encoder is used to compute hashes in this configuration, and also
	// manages the blinding secrets (see UseBlindedValueHashes).
	Encoder Encoder

	// UseBlindedValueHashes controls whether this tree blinds hashes of
	// KeyValuePairs with a per (Key,Seqno) specific secret (which is itself
	// derived from a per Seqno specific secret which is stored together with
	// the tree). This ensures values stored in the tree cannot are not leaked
	// by the membership proofs (but keys can leak, as well as the rough tree
	// size). If the tree is rebuilt at every Seqno, this also hides whether
	// values are changing (but not when a value is first inserted).
	UseBlindedValueHashes bool

	// The number of children per node. Must be a power of two. Some children
	// can be empty.
	ChildrenPerNode int

	// The maximum number of KeyValuePairs in a leaf node before we split
	MaxValuesPerLeaf int

	// The number of bits necessary to represent a ChildIndex, i.e.
	// log2(childrenPerNode)
	BitsPerIndex uint8

	// The length of all the keys which will be stored in the tree. For
	// simplicity, we enforce that all the keys have the same length and that
	// bitsPerIndex divides keyByteLength*8
	KeysByteLength int

	// The maximum depth of the tree. Should always equal keysByteLength*8/bitsPerIndex
	MaxDepth int

	// ConstructValueContainer constructs a new empty value for the value in a KeyValuePair, so that the
	// decoding routine has the correct type template.
	ConstructValueContainer func() interface{}
}

Config defines the shape of the MerkleTree.

func NewConfig 

func NewConfig(e Encoder, useBlindedValueHashes bool, logChildrenPerNode uint8, maxValuesPerLeaf int, keysByteLength int, constructValueFunc func() interface{}) (Config, error)

NewConfig makes a new config object. It takes a a Hasher, logChildrenPerNode which is the base 2 logarithm of the number of children per interior node, maxValuesPerLeaf the maximum number of entries in a leaf before the leaf is split into multiple nodes (at a lower level in the tree), keyByteLength the length of the Keys which the tree will store, and a ConstructValueContainer function (so that typed values can be pulled out of the Merkle Tree).

func (*Config) GetKeyIntervalUnderPosition 

func (t *Config) GetKeyIntervalUnderPosition(p *Position) (minKey, maxKey Key)

type EncodedValue 

type EncodedValue []byte

func (EncodedValue) Equal 

func (e EncodedValue) Equal(e2 EncodedValue) bool

type Encoder 

type Encoder interface {
	Decode(dest interface{}, src []byte) error
	Encode(src interface{}) (dst []byte, err error)

	EncodeAndHashGeneric(interface{}) (encoded []byte, hash Hash, err error)

	GenerateMasterSecret(Seqno) (MasterSecret, error)
	ComputeKeySpecificSecret(MasterSecret, Key) KeySpecificSecret

	HashKeyValuePairWithKeySpecificSecret(KeyValuePair, KeySpecificSecret) (Hash, error)
	HashKeyEncodedValuePairWithKeySpecificSecret(KeyEncodedValuePair, KeySpecificSecret) (Hash, error)
}

Encoder is an interface for cryptographically hashing MerkleTree data structures. It also manages blinding secrets.

type EncodingType 

type EncodingType uint8
const (
	// For KeyValuePairs, the hash of the pair (k, v) is p(p(k, s), (k,v) ))
	// where p = HMAC-SHA512-256 and s is a secret unique per Merkle seqno. For
	// generic data structures, use SHA512-256 to hash the msgpack canonical
	// encoding.
	EncodingTypeBlindedSHA512_256v1 EncodingType = 1

	// Simple messagepack encoding and SHA256_512 hashing. Used for testing.
	EncodingTypeSHA512_256ForTesting EncodingType = 127
)

func (EncodingType) GetEncoder 

func (e EncodingType) GetEncoder() Encoder

type GetLatestValueWithProofResponse 

type GetLatestValueWithProofResponse struct {
	Value EncodedValue
	Proof MerkleInclusionProof `codec:"r,omitempty"`
}

type Hash 

type Hash []byte

Hash is a byte-array, used to represent a full collision-resistant hash.

func (Hash) Equal 

func (h Hash) Equal(h2 Hash) bool

Equal compares two hashes byte by byte

type InvalidConfigError 

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

InvalidConfigError happens when trying to construct an invalid tree configuration.

func NewInvalidConfigError 

func NewInvalidConfigError(reason string) InvalidConfigError

NewInvalidConfigError returns a new error

func (InvalidConfigError) Error 

func (e InvalidConfigError) Error() string

type InvalidKeyError 

type InvalidKeyError struct{}

InvalidKeyError is returned when trying to use a key of the wrong length in a tree.

func NewInvalidKeyError 

func NewInvalidKeyError() InvalidKeyError

NewInvalidKeyError returns a new error

func (InvalidKeyError) Error 

func (e InvalidKeyError) Error() string

type InvalidSeqnoError 

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

InvalidSeqnoError is returned when trying to lookup a record with an invalid Seqno

func NewInvalidSeqnoError 

func NewInvalidSeqnoError(s Seqno, reason error) InvalidSeqnoError

NewInvalidConfigError returns a new error

func (InvalidSeqnoError) Error 

func (e InvalidSeqnoError) Error() string

type Key 

type Key []byte

Key is a byte-array, and it is the type of the keys in the KeyValuePairs that the tree can store.

func (Key) Cmp 

func (k Key) Cmp(k2 Key) int

Cmp compares two keys lexicographically as byte slices

func (Key) Equal 

func (k Key) Equal(k2 Key) bool

Equal compares two keys byte by byte

type KeyEncodedValuePair 

type KeyEncodedValuePair struct {
	Key   Key          `codec:"k"`
	Value EncodedValue `codec:"v"`
	// contains filtered or unexported fields
}

KeyEncodedValuePair is similar to a KeyValuePair, but the values is encoded as a byte slice.

type KeyHashPair 

type KeyHashPair struct {
	Key  Key  `codec:"k"`
	Hash Hash `codec:"h"`
	// contains filtered or unexported fields
}

type KeyNotFoundError 

type KeyNotFoundError struct{}

KeyNotFoundError is returned when trying to fetch a key which is not part of the tree at a specific Seqno.

func NewKeyNotFoundError 

func NewKeyNotFoundError() KeyNotFoundError

NewKeyNotFoundError returns a new error

func (KeyNotFoundError) Error 

func (e KeyNotFoundError) Error() string

type KeySpecificSecret 

type KeySpecificSecret []byte

MasterSecret is a secret used to hide wether a leaf value has changed between different versions (Seqnos) in a blinded merkle tree. This is derived from a per-Seqno MasterSecret as specified by the Encoder

type KeyValuePair 

type KeyValuePair struct {
	Key   Key         `codec:"k"`
	Value interface{} `codec:"v"`
	// contains filtered or unexported fields
}

KeyValuePair is something the merkle tree can store. The key can be something like a UID or a TLF ID. The Value is a generic interface, so you can store anything there, as long as it obeys Msgpack-decoding behavior. The Value must be of the same type returned by ValueConstructor in the TreeConfig, otherwise the behavior is undefined.

type MasterSecret 

type MasterSecret []byte

MasterSecret is a secret used to hide wether a leaf value has changed between different versions (Seqnos) in a blinded merkle tree. One MasterSecret per tree is generated for each Seqno, and such secret is then used to generate a KeySpecific secret per leaf.

type MerkleInclusionProof 

type MerkleInclusionProof struct {
	KeySpecificSecret KeySpecificSecret `codec:"k"`
	OtherPairsInLeaf  []KeyHashPair     `codec:"l"`
	// SiblingHashesOnPath are ordered by level from the farthest to the closest
	// to the root, and lexicographically within each level.
	SiblingHashesOnPath []Hash       `codec:"s"`
	RootMetadataNoHash  RootMetadata `codec:"e"`
	// contains filtered or unexported fields
}

type MerkleProofVerifier 

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

func NewMerkleProofVerifier 

func NewMerkleProofVerifier(c Config) MerkleProofVerifier

func (*MerkleProofVerifier) VerifyInclusionProof 

func (m *MerkleProofVerifier) VerifyInclusionProof(ctx logger.ContextInterface, kvp KeyValuePair, proof MerkleInclusionProof, expRootHash Hash) error

type NoLatestRootFoundError 

type NoLatestRootFoundError struct{}

NoLatestRootFoundError is returned when trying to fetch the latest root from an empty tree.

func NewNoLatestRootFoundError 

func NewNoLatestRootFoundError() NoLatestRootFoundError

NewNoLatestRootFoundError returns a new error

func (NoLatestRootFoundError) Error 

func (e NoLatestRootFoundError) Error() string

type Node 

type Node struct {
	INodes     []Hash
	LeafHashes []KeyHashPair
}

A Node is either an internal node or a leaf: INodes and LeafHashes cannot both have length > 0 (else msgpack encoding will fail).

func (*Node) CodecDecodeSelf 

func (n *Node) CodecDecodeSelf(d *codec.Decoder)

func (*Node) CodecEncodeSelf 

func (n *Node) CodecEncodeSelf(e *codec.Encoder)

type NodeType 

type NodeType uint8

NodeType is used to distinguish serialized internal nodes from leaves in the tree 

const (
	NodeTypeNone  NodeType = 0
	NodeTypeINode NodeType = 1
	NodeTypeLeaf  NodeType = 2
)

type PosHashPairsInMerkleProofOrder 

type PosHashPairsInMerkleProofOrder []PositionHashPair

This type orders positionHashPairs by position, more specificelly first by level descending (nodes with higher level first) and then within each level in ascending order. This is the order required by the merkle proof verifier to easily reconstruct a path.

func (PosHashPairsInMerkleProofOrder) Len 

func (p PosHashPairsInMerkleProofOrder) Len() int

func (PosHashPairsInMerkleProofOrder) Less 

func (p PosHashPairsInMerkleProofOrder) Less(i, j int) bool

func (PosHashPairsInMerkleProofOrder) Swap 

func (p PosHashPairsInMerkleProofOrder) Swap(i, j int)

type Position 

type Position big.Int

Position represents the position of a node in the tree. When converted to bytes, a Position can be interpreted as a 1 followed (from left to right) by a sequence of log2(Config.ChildrenPerNode)-bit symbols, where each such symbol identifies which child to descend to in a path from the root to a node. The sequence is padded with 0s on the left to the nearest byte. For example, in a binary tree the root has position 0x01 (i.e. 0b00000001), and the second child of the first child of the root has position 0x05 (0b00000101).

func NewPositionFromBytes 

func NewPositionFromBytes(pos []byte) *Position

func (*Position) AsString 

func (p *Position) AsString() string

func (*Position) Clone 

func (p *Position) Clone() *Position

Clone returns a pointer to a deep copy of a position

func (*Position) CmpInMerkleProofOrder 

func (p *Position) CmpInMerkleProofOrder(p2 *Position) int

func (*Position) Equals 

func (p *Position) Equals(q *Position) bool

func (*Position) GetBytes 

func (p *Position) GetBytes() []byte

func (*Position) Set 

func (p *Position) Set(q *Position)

Set updates p to the value of q

func (*Position) SetBytes 

func (p *Position) SetBytes(b []byte)

type PositionHashPair 

type PositionHashPair struct {
	Position Position `codec:"p"`
	Hash     Hash     `codec:"h"`
	// contains filtered or unexported fields
}

type ProofVerificationFailedError 

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

ProofVerificationFailedError is returned when a merkle tree proof verification fails.

func NewProofVerificationFailedError 

func NewProofVerificationFailedError(reason error) ProofVerificationFailedError

NewProofVerificationFailedError returns a new error

func (ProofVerificationFailedError) Error 

func (e ProofVerificationFailedError) Error() string

type RootMetadata 

type RootMetadata struct {
	Seqno            Seqno `codec:"n"`
	BareRootHash     Hash  `codec:"r"`
	SkipPointersHash Hash  `codec:"s"`
	// contains filtered or unexported fields
}

type Seqno 

type Seqno int64

Seqno is an integer used to differentiate different versions of a merkle tree.

type StorageEngine 

type StorageEngine interface {
	ExecTransaction(ctx logger.ContextInterface, txFn func(logger.ContextInterface, Transaction) error) error

	// StoreKVPairs stores the []KeyEncodedValuePair in the tree.
	StoreKEVPairs(logger.ContextInterface, Transaction, Seqno, []KeyEncodedValuePair) error

	StoreNode(logger.ContextInterface, Transaction, Seqno, *Position, Hash) error

	StoreNodes(logger.ContextInterface, Transaction, Seqno, []PositionHashPair) error

	StoreRootMetadata(logger.ContextInterface, Transaction, RootMetadata) error

	// LookupLatestRoot returns the latest root metadata and sequence number in
	// the tree. If no root is found, then a NoLatestRootFound error is returned.
	LookupLatestRoot(logger.ContextInterface, Transaction) (Seqno, RootMetadata, error)

	// If there is no root for the specified Seqno, an InvalidSeqnoError is returned.
	LookupRoot(logger.ContextInterface, Transaction, Seqno) (RootMetadata, error)

	// LookupNode returns, for any position, the hash of the node with the
	// highest Seqno s' <= s which was stored at position p. For example, if
	// StoreNode(ctx, t, 5, p, hash5) and StoreNode(ctx, 6, p, hash6) and
	// StoreNode(ctx, t, 8, p, hash8) were called for a specific position p,
	// then LookupNode(ctx, t, 7, p) would return hash6. It returns an error if
	// no such node was stored in the tree.
	LookupNode(c logger.ContextInterface, t Transaction, s Seqno, p *Position) (Hash, error)

	// LookupNodes is analogous to LookupNode, but it takes more than one
	// position and returns pairs of a Position and the corresponding node Hash
	// only for the nodes which are found in the tree. No error is returned if
	// some of the positions are not found.
	LookupNodes(c logger.ContextInterface, t Transaction, s Seqno, positions []Position) ([]PositionHashPair, error)

	// LookupKVPair returns the KeyEncodedValuePair with the highest Seqno s1 <=
	// s which was stored at position p (similarly to LookupNode).
	LookupKEVPair(c logger.ContextInterface, t Transaction, s Seqno, k Key) (val EncodedValue, s1 Seqno, err error)

	// LookupKeyHashPairsUnderPosition returns all KeyEncodedValuePairs (ordered by
	// Key) which were stored at a position p' which is a descendent of p and at
	// the maximum Seqno s' <= s (similarly to LookupNode). For each such pair,
	// it returns the Seqno at which it was stored (in the same order).
	LookupKEVPairsUnderPosition(ctx logger.ContextInterface, t Transaction, s Seqno, p *Position) ([]KeyEncodedValuePair, []Seqno, error)
}

StorageEngine specifies how to store and lookup merkle tree nodes, roots and KeyEncodedValuePairs. You can use a DB like Dynamo or SQL to do this.

type StorageEngineWithBlinding 

type StorageEngineWithBlinding interface {
	StorageEngine

	StoreMasterSecret(ctx logger.ContextInterface, t Transaction, s Seqno, ms MasterSecret) error
	LookupMasterSecrets(ctx logger.ContextInterface, t Transaction, s []Seqno) (map[Seqno]MasterSecret, error)
}

StorageEngineWithBlinding extends the StorageEngine interface with methods to support storing and retrieving the blinding secrets.

type Transaction 

type Transaction interface{}

Transaction references a DB transaction.

type Tree 

type Tree struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Tree is the MerkleTree class; it needs an engine and a configuration to run

func NewTree 

func NewTree(c Config, step int, e StorageEngine) (*Tree, error)

NewTree makes a new tree

func (*Tree) Build 

func (t *Tree) Build(
	ctx logger.ContextInterface, tr Transaction, sortedKVPairs []KeyValuePair) (s Seqno, rootHash Hash, err error)

Build builds a new tree version, taking a batch input. The sortedKeyValuePairs must be sorted (lexicographically) by Key.

NOTE: The input to this function should contain at least all the keys which were inserted in previous versions of the tree, and each key should only appear once, otherwise this procedure will put the tree into an inconsistent state. This function does not check the condition is true for efficiency reasons.

func (*Tree) ExecTransaction 

func (t *Tree) ExecTransaction(ctx logger.ContextInterface, txFn func(logger.ContextInterface, Transaction) error) error

func (*Tree) GenerateAndStoreMasterSecret 

func (t *Tree) GenerateAndStoreMasterSecret(
	ctx logger.ContextInterface, tr Transaction, s Seqno) (ms MasterSecret, err error)

func (*Tree) GetEncodedValueWithProof 

func (t *Tree) GetEncodedValueWithProof(ctx logger.ContextInterface, tr Transaction, s Seqno, k Key) (val EncodedValue, proof MerkleInclusionProof, err error)

func (*Tree) GetKeyValuePair 

func (t *Tree) GetKeyValuePair(ctx logger.ContextInterface, tr Transaction, s Seqno, k Key) (KeyValuePair, error)

Retrieves a KeyValuePair from the tree. Note that if the root at Seqno s was not committed yet, an InvalidSeqnoError is returned.

func (*Tree) GetKeyValuePairUnsafe 

func (t *Tree) GetKeyValuePairUnsafe(ctx logger.ContextInterface, tr Transaction, s Seqno, k Key) (kvp KeyValuePair, err error)

Retrieves a KeyValuePair from the tree. Note that if the root at Seqno s was not committed yet, there might be no proof for this pair yet (hence it is unsafe).

func (*Tree) GetKeyValuePairWithProof 

func (t *Tree) GetKeyValuePairWithProof(ctx logger.ContextInterface, tr Transaction, s Seqno, k Key) (kvp KeyValuePair, proof MerkleInclusionProof, err error)

func (*Tree) GetLatestRoot 

func (t *Tree) GetLatestRoot(ctx logger.ContextInterface, tr Transaction) (s Seqno, root RootMetadata, rootHash Hash, err error)

GetLatestRoot returns the latest RootMetadata which was stored in the tree (and its Hash and Seqno). If no such record was stored yet, GetLatestRoot returns 0 as a Seqno and a NoLatestRootFound error.

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.