merkletree2

package
v4.5.0+incompatible Latest Latest
Warning

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

 Go to latest Published: Sep 19, 2019 License: BSD-3-Clause, BSD-3-Clause Imports: 11 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{}

func (BlindedSHA512_256v1Encoder) ComputeKeySpecificSecret 

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

func (BlindedSHA512_256v1Encoder) EncodeAndHashGeneric 

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

func (BlindedSHA512_256v1Encoder) GenerateMasterSecret 

func (e BlindedSHA512_256v1Encoder) GenerateMasterSecret(Seqno) (MasterSecret, 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 {
	// contains filtered or unexported fields
}

Config defines the shape of the MerkleTree.

func NewConfig 

func NewConfig(h Encoder, useBlindedValueHashes bool, logChildrenPerNode uint8, maxValuesPerLeaf int, keysByteLength int) (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 valueConstructor (so that typed values can be pulled out of the Merkle Tree).

type Encoder 

type Encoder interface {
	EncodeAndHashGeneric(interface{}) (Hash, error)
	HashKeyValuePairWithKeySpecificSecret(KeyValuePair, KeySpecificSecret) (Hash, error)
	GenerateMasterSecret(Seqno) (MasterSecret, error)
	ComputeKeySpecificSecret(MasterSecret, Key) KeySpecificSecret
}

Encoder is an interface for hashing MerkleTree data structures into their cryptographic hashes. 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 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 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 context.Context, 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 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 (*Position) Clone 

func (p *Position) Clone() *Position

Clone returns a pointer to a deep copy of a position

func (*Position) Set 

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

Set updates p to the value of q

type PositionHashPair 

type PositionHashPair struct {
	// 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 SHA512_256Encoder 

type SHA512_256Encoder struct{}

func (SHA512_256Encoder) ComputeKeySpecificSecret 

func (e SHA512_256Encoder) ComputeKeySpecificSecret(_ MasterSecret, _ Key) KeySpecificSecret

func (SHA512_256Encoder) EncodeAndHashGeneric 

func (e SHA512_256Encoder) EncodeAndHashGeneric(o interface{}) (Hash, error)

func (SHA512_256Encoder) GenerateMasterSecret 

func (e SHA512_256Encoder) GenerateMasterSecret(_ Seqno) (MasterSecret, error)

func (SHA512_256Encoder) HashKeyValuePairWithKeySpecificSecret 

func (e SHA512_256Encoder) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, _ KeySpecificSecret) (Hash, error)

type Seqno 

type Seqno int64

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

type StorageEngine 

type StorageEngine interface {
	// TODO update transaction management together with the blind architect
	NewTransaction(context.Context) (Transaction, error)
	CommitTransaction(context.Context, Transaction) error
	AbortTransaction(context.Context, Transaction)

	// StoreKVPairs stores the []KeyValuePair in the tree.
	StoreKVPairs(context.Context, Transaction, Seqno, []KeyValuePair) error

	StoreNode(context.Context, Transaction, Seqno, Position, Hash) error

	StoreRootMetadata(context.Context, 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(context.Context, Transaction) (Seqno, RootMetadata, error)

	// If there is no root for the specified Seqno, an InvalidSeqnoError is returned.
	LookupRoot(context.Context, 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 context.Context, 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. Positions should be
	// returned in the same order in which they are requested, and no error is
	// returned if some of the positions are not found.
	LookupNodes(c context.Context, t Transaction, s Seqno, positions []Position) ([]PositionHashPair, error)

	// LookupKVPair returns the KeyValuePair with the highest Seqno s1 <=
	// s which was stored at position p (similarly to LookupNode).
	LookupKVPair(c context.Context, t Transaction, s Seqno, k Key) (kvp KeyValuePair, s1 Seqno, err error)

	// LookupKeyHashPairsUnderPosition returns all KeyValuePairs (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).
	LookupKeyValuePairsUnderPosition(ctx context.Context, tr Transaction, s Seqno, p Position) ([]KeyValuePair, []Seqno, error)
}

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

type StorageEngineWithBlinding 

type StorageEngineWithBlinding interface {
	StorageEngine

	StoreMasterSecret(ctx context.Context, tr Transaction, s Seqno, ms MasterSecret) error
	LookupMasterSecrets(ctx context.Context, tr 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
	logger.Logger
	// 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, l logger.Logger) (*Tree, error)

NewTree makes a new tree

func (*Tree) Build 

func (t *Tree) Build(
	ctx context.Context, tr Transaction, sortedKVPairs []KeyValuePair) (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) GenerateAndStoreMasterSecret 

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

func (*Tree) GetKeyValuePair 

func (t *Tree) GetKeyValuePair(ctx context.Context, 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 context.Context, 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 context.Context, tr Transaction, s Seqno, k Key) (kvp KeyValuePair, proof MerkleInclusionProof, err error)

func (*Tree) GetLatestRoot 

func (t *Tree) GetLatestRoot(ctx context.Context, 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.

type ValueConstructor 

type ValueConstructor interface {
	// Construct a new template empty value for the leaf, so that the
	// Unmarshalling routine has the correct type template.
	Construct() interface{}
}

ValueConstructor is an interface for constructing values, so that typed values can be pulled out of the Merkle Tree. All Values must have the same type, howerver multiple types can be encoded by having this type implement the codec.Selfer 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.