merkletree

package
v0.0.0-...-11acf48 Latest Latest
Warning

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

 Go to latest Published: Jul 22, 2018 License: BSD-3-Clause Imports: 7 Imported by: 0

Documentation

Overview

Package merkletree implements a Merkle prefix tree and related data structures. The Merkle prefix tree is one of the most important components of the CONIKS protocol. We implemented this data structure separately as a library to help other developers use it in their implementation easily.

Persistent Authenticated Dictionary

This module implements a persistent authenticated dictionary (PAD) data structure, which supports dictionary operations with two additional features: (1) lookups return a cryptographic proof of correctness along with the result, and (2) it supports taking and storing snapshots of the current contents of the dictionary to allow lookups in historical versions of the dictionary. In CONIKS, the general PAD design is extended to return proofs for inserts. This design does not support deletions, and individual snapshots are linked via a hash chain to commit the entire history. This PAD implementation also supports randomizing the order of directory entries by changing the VRF private key. This protects the user's privacy against other malicious parties who wish to obtain information about users by querying the key directory.

Merkle Prefix Tree

This module implements the Merkle prefix tree, which is the data structure underlying our PAD implementation. It is a binary tree with two types of leaf nodes: empty node and user node. Each node contains the prefix of its lookup index and its level within the tree. It provides methods for inserting new key-value pairs, and for updating and looking up an existing key-value pair. The tree is append-only, meaning that user leaf nodes cannot be removed once inserted. This Merkle prefix tree implementation is also privacy-preserving: the lookup index is a cryptographic transformation (VRF) of the search key, and values are concealed using cryptographic commitments. The VRF, commitment scheme and hash operations are provided by our crypto package (see https://godoc.org/github.com/coniks-sys/coniks-go/crypto).

Index

Constants

View Source 
const (
	// EmptyBranchIdentifier is the domain separation prefix for
	// empty node hashes.
	EmptyBranchIdentifier = 'E'

	// LeafIdentifier is the domain separation prefix for user
	// leaf node hashes.
	LeafIdentifier = 'L'
)

Variables

View Source 
var (
	// ErrBindingsDiffer indicates that the value included in the proof
	// is different from the expected value.
	ErrBindingsDiffer = errors.New("[merkletree] The values included in the bindings are different")
	// ErrUnverifiableCommitment indicates that the leaf node's commitment is unverifiable.
	ErrUnverifiableCommitment = errors.New("[merkletree] Could not verify the commitment")
	// ErrIndicesMismatch indicates that there is a mismatch
	// between the lookup index and the leaf index.
	ErrIndicesMismatch = errors.New("[merkletree] The lookup index is inconsistent with the index of the proof node")
	// ErrUnequalTreeHashes indicates that the hash computed from the authentication path
	// and the hash taken from the signed tree root are different.
	ErrUnequalTreeHashes = errors.New("[merkletree] The hashes computed from the authentication path and the STR are unequal")
)
View Source 
var (
	// ErrInvalidTree indicates a panic due to
	// a malformed operation on the tree.
	ErrInvalidTree = errors.New("[merkletree] Invalid tree")
)
View Source 
var (
	// ErrSTRNotFound indicates that the STR has been evicted from
	// memory, because the maximum number of cached PAD snapshots
	// has been exceeded.
	ErrSTRNotFound = errors.New("[merkletree] STR not found")
)

Functions

This section is empty.

Types

type AssocData 

type AssocData interface {
	Serialize() []byte
}

AssocData is associated data to be hashed into the STR.

type AuthenticationPath 

type AuthenticationPath struct {
	TreeNonce   []byte
	PrunedTree  [][crypto.HashSizeByte]byte
	LookupIndex []byte
	VrfProof    []byte
	Leaf        *ProofNode
	// contains filtered or unexported fields
}

AuthenticationPath is a pruned tree containing the prefix path between the corresponding leaf node (of type ProofNode) and the root. This is a proof of inclusion or absence of requested index. A proof of inclusion is when the leaf index equals the lookup index.

func (*AuthenticationPath) ProofType 

func (ap *AuthenticationPath) ProofType() ProofType

ProofType returns the type of ap. It does a comparison between the leaf index and the lookup index to determine the proof type, and sets ap's proof type the first time this method called, memoizing the proof type for subsequent calls.

func (*AuthenticationPath) Verify 

func (ap *AuthenticationPath) Verify(key, value, treeHash []byte) error

Verify first compares the lookup index with the leaf index. It expects the lookup index and the leaf index match in the first l bits with l is the Level of the proof node if ap is a proof of absence. It also verifies the value and the commitment (in case of the proof of inclusion). Finally, it recomputes the tree's root node from ap, and compares it to treeHash, which is taken from a STR. Specifically, treeHash has to come from the STR whose tree returns ap.

This should be called after the VRF index is verified successfully.

type MerkleTree 

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

MerkleTree represents the Merkle prefix tree data structure, which includes the root node, its hash, and a random tree-specific nonce.

func NewMerkleTree 

func NewMerkleTree() (*MerkleTree, error)

NewMerkleTree returns an empty Merkle prefix tree with a secure random nonce. The tree root is an interior node and its children are two empty leaf nodes.

func (*MerkleTree) Clone 

func (m *MerkleTree) Clone() *MerkleTree

Clone returns a copy of the tree m. Any later change to the original tree m does not affect the cloned tree, and vice versa.

func (*MerkleTree) Get 

func (m *MerkleTree) Get(lookupIndex []byte) *AuthenticationPath

Get returns an AuthenticationPath used as a proof of inclusion/absence for the requested lookupIndex.

func (*MerkleTree) Set 

func (m *MerkleTree) Set(index []byte, key string, value []byte) error

Set inserts or updates the value of the given index calculated from the key to the tree. It will generate a new commitment for the leaf node. In the case of an update, the leaf node's value and commitment are replaced with the new value and newly generated commitment.

type PAD 

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

A PAD represents a persistent authenticated dictionary, and includes the underlying MerkleTree, cached snapshots, the latest SignedTreeRoot, two key pairs for signing and VRF computation, and additional developer-specified AssocData.

func NewPAD 

func NewPAD(ad AssocData, signKey sign.PrivateKey, vrfKey vrf.PrivateKey, len uint64) (*PAD, error)

NewPAD creates new PAD with the given associated data ad, signing key pair signKey, VRF key pair vrfKey, and the maximum capacity for the snapshot cache len.

func StaticPAD 

func StaticPAD(t *testing.T, ad AssocData) *PAD

StaticPAD returns a pad with a static initial STR for _tests_.

func (*PAD) GetSTR 

func (pad *PAD) GetSTR(epoch uint64) *SignedTreeRoot

GetSTR returns the signed tree root of the requested epoch. This signed tree root is read from the cached snapshots of the PAD. It returns nil if the signed tree root has been removed from the memory.

func (*PAD) Index 

func (pad *PAD) Index(key string) []byte

Index uses the _current_ VRF private key of the PAD to compute the private index for the requested key.

func (*PAD) LatestSTR 

func (pad *PAD) LatestSTR() *SignedTreeRoot

LatestSTR returns the latest signed tree root of the PAD.

func (*PAD) Lookup 

func (pad *PAD) Lookup(key string) (*AuthenticationPath, error)

Lookup searches the requested key in the latest snapshot of the PAD, and returns the corresponding AuthenticationPath proving inclusion or absence of the requested key.

func (*PAD) LookupInEpoch 

func (pad *PAD) LookupInEpoch(key string, epoch uint64) (*AuthenticationPath, error)

LookupInEpoch searches the requested key in the snapshot at the requested epoch. It returns ErrorSTRNotFound if the signed tree root of the requested epoch has been removed from memory, indicating to the server that the STR for the requested epoch should be retrieved from persistent storage.

func (*PAD) Set 

func (pad *PAD) Set(key string, value []byte) error

Set computes the private index for the given key using the current VRF private key to create a new index-to-value binding, and inserts it into the PAD's underlying Merkle tree. This ensures the index-to-value binding will be included in the next PAD snapshot.

func (*PAD) Sign 

func (pad *PAD) Sign(msg ...[]byte) []byte

Sign uses the _current_ signing key underlying the PAD to sign msg.

func (*PAD) Update 

func (pad *PAD) Update(ad AssocData)

Update generates a new snapshot of the tree. It should be called at the beginning of each epoch. Specifically, it extends the hash chain by issuing a new signed tree root. It may remove some older signed tree roots from memory if the cached PAD snapshots exceeded the maximum capacity. ad should be nil if the PAD's associated data ad do not change.

type ProofNode 

type ProofNode struct {
	Level      uint32
	Index      []byte
	Value      []byte
	IsEmpty    bool
	Commitment *crypto.Commit
}

ProofNode can be a user node or an empty node, which is included in the returned AuthenticationPath of a given index. The type of that node can be determined by the IsEmpty value. It also provides an opening of the commitment if the returned AuthenticationPath is a proof of inclusion.

type ProofType 

type ProofType int

A ProofType indicates whether an AuthenticationPath is a proof of inclusion or a proof of absence. 

const (
	ProofOfAbsence ProofType
	ProofOfInclusion
)

type SignedTreeRoot 

type SignedTreeRoot struct {
	TreeHash        []byte
	Epoch           uint64
	PreviousEpoch   uint64
	PreviousSTRHash []byte
	Signature       []byte
	Ad              AssocData `json:"-"`
	// contains filtered or unexported fields
}

SignedTreeRoot represents a signed tree root (STR), which is generated at the beginning of every epoch. Signed tree roots contain the current root node, the current and previous epochs, the hash of the previous STR, its signature, and developer-specified associated data. The epoch number is a counter from 0, and increases by 1 when a new signed tree root is issued by the PAD.

func NewSTR 

func NewSTR(key sign.PrivateKey, ad AssocData, m *MerkleTree, epoch uint64, prevHash []byte) *SignedTreeRoot

NewSTR constructs a SignedTreeRoot with the given signing key pair, associated data, MerkleTree, epoch, previous STR hash, and digitally signs the STR using the given signing key.

func (*SignedTreeRoot) Serialize 

func (str *SignedTreeRoot) Serialize() []byte

Serialize serializes the signed tree root and its associated data into a specified format for signing. One should use this function for signing as well as verifying the signature. Any composition struct of SignedTreeRoot with a specific AssocData should override this method.

func (*SignedTreeRoot) SerializeInternal 

func (str *SignedTreeRoot) SerializeInternal() []byte

SerializeInternal serializes the signed tree root into a specified format.

func (*SignedTreeRoot) VerifyHashChain 

func (str *SignedTreeRoot) VerifyHashChain(savedSTR *SignedTreeRoot) bool

VerifyHashChain computes the hash of savedSTR's signature, and compares it to the hash of previous STR included in the issued STR. The hash chain is valid if these two hash values are equal and consecutive.

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.