merkletree2

package
v5.4.0+incompatible Latest Latest
Warning

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

 Go to latest Published: Apr 15, 2020 License: BSD-3-Clause, BSD-3-Clause Imports: 13 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 {
	BlindedSHA512_256v1Inner
	// contains filtered or unexported fields
}

func NewBlindedSHA512_256v1Encoder 

func NewBlindedSHA512_256v1Encoder() *BlindedSHA512_256v1Encoder

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) EncodeTo 

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

func (*BlindedSHA512_256v1Encoder) HashGeneric 

func (e *BlindedSHA512_256v1Encoder) HashGeneric(o interface{}, ret *Hash) error

func (*BlindedSHA512_256v1Encoder) HashKeyValuePairWithKeySpecificSecret 

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

type BlindedSHA512_256v1Inner 

type BlindedSHA512_256v1Inner struct{}

func (BlindedSHA512_256v1Inner) ComputeKeySpecificSecret 

func (e BlindedSHA512_256v1Inner) ComputeKeySpecificSecret(ms MasterSecret, k Key) (kss KeySpecificSecret)

func (BlindedSHA512_256v1Inner) ComputeKeySpecificSecretTo 

func (e BlindedSHA512_256v1Inner) ComputeKeySpecificSecretTo(ms MasterSecret, k Key, ret *KeySpecificSecret)

func (BlindedSHA512_256v1Inner) GenerateMasterSecret 

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

func (BlindedSHA512_256v1Inner) GetEncodingType 

func (e BlindedSHA512_256v1Inner) GetEncodingType() EncodingType

func (BlindedSHA512_256v1Inner) HashKeyEncodedValuePairWithKeySpecificSecret 

func (e BlindedSHA512_256v1Inner) HashKeyEncodedValuePairWithKeySpecificSecret(kevp KeyEncodedValuePair, kss KeySpecificSecret) (h Hash, err error)

func (BlindedSHA512_256v1Inner) HashKeyEncodedValuePairWithKeySpecificSecretTo 

func (e BlindedSHA512_256v1Inner) HashKeyEncodedValuePairWithKeySpecificSecretTo(kevp KeyEncodedValuePair, kss KeySpecificSecret, ret *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) GetChild 

func (t *Config) GetChild(p *Position, c ChildIndex) *Position

func (*Config) GetKeyIntervalUnderPosition 

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

func (*Config) GetRootPosition 

func (t *Config) GetRootPosition() *Position

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)
	// takes as input a []byte pointer dst to avoid creating new objects
	EncodeTo(o interface{}, dst *[]byte) (err error)

	EncodeAndHashGeneric(interface{}) (encoded []byte, hash Hash, err error)
	// takes as input an hash pointer ret to avoid creating new objects
	HashGeneric(o interface{}, ret *Hash) error

	GenerateMasterSecret(Seqno) (MasterSecret, error)
	ComputeKeySpecificSecret(MasterSecret, Key) KeySpecificSecret
	// takes as input a KeySpecificSecret pointer to avoid creating new objects
	ComputeKeySpecificSecretTo(MasterSecret, Key, *KeySpecificSecret)

	HashKeyValuePairWithKeySpecificSecret(KeyValuePair, KeySpecificSecret) (Hash, error)
	HashKeyEncodedValuePairWithKeySpecificSecret(KeyEncodedValuePair, KeySpecificSecret) (Hash, error)
	// takes as input an hash pointer ret to avoid creating new objects
	HashKeyEncodedValuePairWithKeySpecificSecretTo(KeyEncodedValuePair, KeySpecificSecret, *Hash) error

	GetEncodingType() EncodingType
}

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), v )) where p
	// = HMAC-SHA512-256 and s is a secret unique per Merkle seqno. Note that
	// users learn k, v and p(k,s) but not s itself, so the hash is a commitment
	// to the value only and not the key. However, the key is written and hashed
	// as part of the merkle tree leaf node, so keybase cannot equivocate that.
	// For generic data structures, this encoder uses SHA512-256 to hash the
	// msgpack canonical encoding.
	EncodingTypeBlindedSHA512_256v1 EncodingType = 1

	// Generic testing encoding.
	EncodingTypeForTesting EncodingType = 127
)

func (EncodingType) GetEncoder 

func (e EncodingType) GetEncoder() Encoder

func (EncodingType) GetUnsafeEncoder 

func (e EncodingType) GetUnsafeEncoder() Encoder

This function returns an encoder which is potentially unsafe for concurrent use.

type GetValueWithProofResponse 

type GetValueWithProofResponse struct {
	Value EncodedValue         `codec:"v"`
	Proof MerkleInclusionProof `codec:"r,omitempty"`
	// contains filtered or unexported fields
}

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 MerkleExtensionProof 

type MerkleExtensionProof struct {
	RootHashes           []Hash         `codec:"h"`
	PreviousRootsNoSkips []RootMetadata `codec:"k"`
	// contains filtered or unexported fields
}

A MerkleExtensionProof proves, given the RootMetadata hashes of two merkle trees and their respective Seqno values, that: - the two merkle trees have the expected Seqno values, - the most recent merkle tree "points back" to the least recent one through a chain of SkipPointers that refer to merkle trees at intermediate Seqnos.

type MerkleInclusionExtensionProof 

type MerkleInclusionExtensionProof struct {
	MerkleInclusionProof MerkleInclusionProof
	MerkleExtensionProof MerkleExtensionProof
	// contains filtered or unexported fields
}

An MerkleInclusionExtensionProof combines a MerkleInclusionProof and a MerkleExtensionProof. The redundant fields are deleted so that sending a combined proof is more efficient than sending both of them individually.

type MerkleInclusionProof 

type MerkleInclusionProof struct {
	KeySpecificSecret KeySpecificSecret `codec:"k"`
	// When this struct is used as an exclusion proof, OtherPairsInLeaf is set
	// to nil if the proof ends at an internal node, and set to a slice of
	// length 0 or more if the proof ends at a (possibly empty) leaf node. In
	// particular, a tree with no keys is encoded with the root being the only
	// (empty leaf) node.
	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
}

A MerkleInclusionProof proves that a specific key value pair is stored in a merkle tree, given the RootMetadata hash of such tree. It can also be used to prove that a specific key is not part of the tree (we call this an exclusion or absence proof)

type MerkleProofVerifier 

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

func NewMerkleProofVerifier 

func NewMerkleProofVerifier(c Config) MerkleProofVerifier

func (*MerkleProofVerifier) VerifyExclusionProof 

func (m *MerkleProofVerifier) VerifyExclusionProof(ctx logger.ContextInterface, k Key, proof *MerkleInclusionProof, expRootHash Hash) (err error)

VerifyExclusionProof uses a MerkleInclusionProof to assert that a specific key is not part of the tree

func (*MerkleProofVerifier) VerifyExtensionProof 

func (m *MerkleProofVerifier) VerifyExtensionProof(ctx logger.ContextInterface, proof *MerkleExtensionProof, initialSeqno Seqno, initialRootHash Hash, finalSeqno Seqno, expRootHash Hash) error

func (*MerkleProofVerifier) VerifyInclusionExtensionProof 

func (m *MerkleProofVerifier) VerifyInclusionExtensionProof(ctx logger.ContextInterface, kvp KeyValuePair, proof *MerkleInclusionExtensionProof, initialSeqno Seqno, initialRootHash Hash, finalSeqno Seqno, expRootHash Hash) (err error)

func (*MerkleProofVerifier) VerifyInclusionProof 

func (m *MerkleProofVerifier) VerifyInclusionProof(ctx logger.ContextInterface, kvp KeyValuePair, proof *MerkleInclusionProof, expRootHash Hash) (err 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 NodeNotFoundError 

type NodeNotFoundError struct{}

NodeNotFoundError is returned by a StorageEngine when trying to fetch an internal node which is not part of the tree at a specific Seqno.

func NewNodeNotFoundError 

func NewNodeNotFoundError() NodeNotFoundError

NewNodeNotFoundError returns a new error

func (NodeNotFoundError) Error 

func (e NodeNotFoundError) Error() string

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 {
	RootVersion      RootVersion
	EncodingType     EncodingType
	Seqno            Seqno
	BareRootHash     Hash
	SkipPointersHash Hash

	//  AddOnsHash is the (currently empty) hash of a (not yet defined) data
	//  structure which will contain a map[string]Hash (or even
	//  map[string]interface{}) which can contain arbitrary values. This AddOn
	//  struct is not used in verifying proofs, and new elements can be added to
	//  this map without bumping the RootVersion. Clients are expected to ignore
	//  fields in this map which they do not understand.
	AddOnsHash Hash
	// contains filtered or unexported fields
}

type RootVersion 

type RootVersion uint8
const (
	RootVersionV1      RootVersion = 1
	CurrentRootVersion RootVersion = RootVersionV1
)

type Seqno 

type Seqno int64

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

func ComputeRootHashSeqnosNeededInExtensionProof 

func ComputeRootHashSeqnosNeededInExtensionProof(start, end Seqno) (ret []Seqno, err error)

func ComputeRootMetadataSeqnosNeededInExtensionProof 

func ComputeRootMetadataSeqnosNeededInExtensionProof(start, end Seqno, isPartOfIncExtProof bool) ([]Seqno, error)

func SkipPointersForSeqno 

func SkipPointersForSeqno(s Seqno) (pointers []Seqno)

func SkipPointersPath 

func SkipPointersPath(start, end Seqno) (pointers []Seqno, err error)

SkipPointersPath takes two seqno 0 < start <= end. It returns a slice of Seqno `pointers` such that:

  • start \in SkipPointersForSeqno(pointers[0]),
  • pointers[len(pointers)] == end,
  • pointers[i-1] \in SkipPointersForSeqno(pointers[i]) for i = 1...len(pointers)-1.

If start == end, returns [end]. The sequence has length at most logarithmic in end - start.

type SeqnoSortedAsInt 

type SeqnoSortedAsInt []Seqno

func (SeqnoSortedAsInt) Len 

func (d SeqnoSortedAsInt) Len() int

func (SeqnoSortedAsInt) Less 

func (d SeqnoSortedAsInt) Less(i, j int) bool

func (SeqnoSortedAsInt) Swap 

func (d SeqnoSortedAsInt) Swap(i, j int)

type SkipPointers 

type SkipPointers []Hash

The SkipPointers struct is constructed for a specific Seqno s (version) of the tree and contains the hashes of RootMetadata structs at specific previous Seqnos (versions) of the tree. Such versions are fixed given s according to the algorithm in GenerateSkipPointersSeqnos so that a "chain" of SkipPointers can "connect" any two roots in a logarithmic number of steps.

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 stores the Hash (of a tree node) at the provided Position,
	// Seqno in the tree.
	StoreNode(logger.ContextInterface, Transaction, Seqno, *Position, Hash) error

	// StoreNode takes multiple pairs of a position and a hash, and stores each
	// hash (of a tree node) at the corresponding position and at the supplied
	// Seqno in the tree.
	StoreNodes(logger.ContextInterface, Transaction, Seqno, []PositionHashPair) error

	// StoreRootMetadata stores the supplied RootMetadata, along with the
	// corresponding Hash.
	StoreRootMetadata(logger.ContextInterface, Transaction, RootMetadata, Hash) 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)

	// Returns a RootMetadata given its Hash.
	LookupRootFromHash(logger.ContextInterface, Transaction, Hash) (RootMetadata, error)

	// LookupRoots returns the RootMetadata objects in the tree at the
	// supplied Seqnos, ordered by seqno.
	LookupRoots(logger.ContextInterface, Transaction, []Seqno) ([]RootMetadata, error)

	// LookupRootHashes returns hashes of the RootMetadata in the tree at the
	// corresponding Seqnos, ordered by seqno.
	LookupRootHashes(logger.ContextInterface, Transaction, []Seqno) ([]Hash, 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)

	// LookupAllKEVPairs returns all the keys and encoded values at the specified Seqno.
	LookupAllKEVPairs(ctx logger.ContextInterface, t Transaction, s Seqno) ([]KeyEncodedValuePair, 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, v RootVersion) (*Tree, error)

NewTree makes a new tree

func (*Tree) Build 

func (t *Tree) Build(
	ctx logger.ContextInterface, tr Transaction, sortedKVPairs []KeyValuePair, addOnsHash Hash) (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) GetEncodedValueWithInclusionExtensionProof 

func (t *Tree) GetEncodedValueWithInclusionExtensionProof(ctx logger.ContextInterface, tr Transaction, haveSeqno, wantSeqno Seqno, k Key) (val EncodedValue, proof MerkleInclusionExtensionProof, err error)

func (*Tree) GetEncodedValueWithInclusionOrExclusionProofFromRootHash 

func (t *Tree) GetEncodedValueWithInclusionOrExclusionProofFromRootHash(ctx logger.ContextInterface, tr Transaction, rootHash Hash, k Key) (val EncodedValue, proof MerkleInclusionProof, err error)

If the key is not in the tree at the root with the specified hash, this function returns a nil value, a proof which certifies that and no error.

func (*Tree) GetEncodedValueWithInclusionProof 

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

If the key is not in the tree at seqno s, this function returns a KeyNotFoundError and no absence proof.

func (*Tree) GetExtensionProof 

func (t *Tree) GetExtensionProof(ctx logger.ContextInterface, tr Transaction, fromSeqno, toSeqno Seqno) (proof MerkleExtensionProof, 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) GetKeyValuePairWithInclusionExtensionProof 

func (t *Tree) GetKeyValuePairWithInclusionExtensionProof(ctx logger.ContextInterface, tr Transaction, haveSeqno, wantSeqno Seqno, k Key) (kvp KeyValuePair, proof MerkleInclusionExtensionProof, err error)

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.

type UnsafeBlindedSHA512_256v1Encoder 

type UnsafeBlindedSHA512_256v1Encoder struct {
	BlindedSHA512_256v1Inner
	// contains filtered or unexported fields
}

UnsafeBlindedSHA512_256v1Encoder is analogous to BlindedSHA512_256v1Encoder, but sometimes faster and not safe for concurrent use.

func NewUnsafeBlindedSHA512_256v1Encoder 

func NewUnsafeBlindedSHA512_256v1Encoder() *UnsafeBlindedSHA512_256v1Encoder

func (*UnsafeBlindedSHA512_256v1Encoder) Decode 

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

func (*UnsafeBlindedSHA512_256v1Encoder) Encode 

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

func (*UnsafeBlindedSHA512_256v1Encoder) EncodeAndHashGeneric 

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

func (*UnsafeBlindedSHA512_256v1Encoder) EncodeTo 

func (e *UnsafeBlindedSHA512_256v1Encoder) EncodeTo(o interface{}, out *[]byte) (err error)

func (*UnsafeBlindedSHA512_256v1Encoder) HashGeneric 

func (e *UnsafeBlindedSHA512_256v1Encoder) HashGeneric(o interface{}, ret *Hash) error

func (*UnsafeBlindedSHA512_256v1Encoder) HashKeyValuePairWithKeySpecificSecret 

func (e *UnsafeBlindedSHA512_256v1Encoder) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, kss KeySpecificSecret) (Hash, 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.