Documentation
¶
Index ¶
- Constants
- Variables
- func Verify(root crypto.GenericDigest, elems map[uint64]crypto.Hashable, proof *Proof) error
- func VerifyVectorCommitment(root crypto.GenericDigest, elems map[uint64]crypto.Hashable, proof *Proof) error
- type Array
- type Layer
- type Proof
- type SingleLeafProof
- func (_ *SingleLeafProof) CanMarshalMsg(z interface{}) bool
- func (_ *SingleLeafProof) CanUnmarshalMsg(z interface{}) bool
- func (p *SingleLeafProof) GetConcatenatedProof() []byte
- func (p *SingleLeafProof) GetFixedLengthHashableRepresentation() []byte
- func (z *SingleLeafProof) MarshalMsg(b []byte) (o []byte)
- func (z *SingleLeafProof) MsgIsZero() bool
- func (z *SingleLeafProof) Msgsize() (s int)
- func (p *SingleLeafProof) ToProof() *Proof
- func (z *SingleLeafProof) UnmarshalMsg(bts []byte) (o []byte, err error)
- type Tree
- func (_ *Tree) CanMarshalMsg(z interface{}) bool
- func (_ *Tree) CanUnmarshalMsg(z interface{}) bool
- func (z *Tree) MarshalMsg(b []byte) (o []byte)
- func (z *Tree) MsgIsZero() bool
- func (z *Tree) Msgsize() (s int)
- func (tree *Tree) Prove(idxs []uint64) (*Proof, error)
- func (tree *Tree) ProveSingleLeaf(idx uint64) (*SingleLeafProof, error)
- func (tree *Tree) Root() crypto.GenericDigest
- func (z *Tree) UnmarshalMsg(bts []byte) (o []byte, err error)
Constants ¶
const ( // MaxEncodedTreeDepth is the maximum tree depth (root only depth 0) for a tree which // is being encoded (either by msbpack or by the fixed length encoding) MaxEncodedTreeDepth = 16 // MaxNumLeavesOnEncodedTree is the maximum number of leaves allowed for a tree which // is being encoded (either by msbpack or by the fixed length encoding) MaxNumLeavesOnEncodedTree = 1 << MaxEncodedTreeDepth )
Variables ¶
var ( ErrRootMismatch = errors.New("root mismatch") ErrProvingZeroCommitment = errors.New("proving in zero-length commitment") ErrProofIsNil = errors.New("proof should not be nil") ErrNonEmptyProofForEmptyElements = errors.New("non-empty proof for empty set of elements") ErrUnexpectedTreeDepth = errors.New("unexpected tree depth") ErrPosOutOfBound = errors.New("pos out of bound") )
Merkle tree errors
var (
ErrGetOutOfBound = errors.New("can't get element out of padded array bound")
)
ErrGetOutOfBound returned when trying to retrieve an element which is out of the padded array bound.
Functions ¶
func Verify ¶
Verify ensures that the positions in elems correspond to the respective hashes in a tree with the given root hash. The proof is expected to be the proof returned by Prove().
func VerifyVectorCommitment ¶
func VerifyVectorCommitment(root crypto.GenericDigest, elems map[uint64]crypto.Hashable, proof *Proof) error
VerifyVectorCommitment verifies a vector commitment proof against a given root.
Types ¶
type Array ¶
type Array interface {
// Length returns number of elements in the array.
Length() uint64
// Marshal Returns a hash representation of the element located in position pos
Marshal(pos uint64) (crypto.Hashable, error)
}
An Array is an interface that is being using when creating Merkle trees. It represents a dense array of n (n is given by the Length() method) elements, and returns a hash representation for each leaf (in the range)
type Layer ¶
type Layer []crypto.GenericDigest
A Layer of the Merkle tree consists of a dense array of hashes at that level of the tree. Hashes beyond the end of the array (e.g., if the number of leaves is not an exact power of 2) are implicitly zero.
func (Layer) CanMarshalMsg ¶
func (*Layer) CanUnmarshalMsg ¶
func (Layer) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Proof ¶
type Proof struct {
// Path is bounded by MaxNumLeavesOnEncodedTree since there could be multiple reveals, and
// given the distribution of the elt positions and the depth of the tree,
// the path length can increase up to 2^MaxEncodedTreeDepth / 2
Path []crypto.GenericDigest `codec:"pth,allocbound=MaxNumLeavesOnEncodedTree/2"`
HashFactory crypto.HashFactory `codec:"hsh"`
// TreeDepth represents the depth of the tree that is being proven.
// It is the number of edges from the root to a leaf.
TreeDepth uint8 `codec:"td"`
// contains filtered or unexported fields
}
Proof is used to convince a verifier about membership of leaves: h0,h1...hn at indexes i0,i1...in on a tree. The verifier has a trusted value of the tree root hash.
func (*Proof) CanMarshalMsg ¶
func (*Proof) CanUnmarshalMsg ¶
func (*Proof) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type SingleLeafProof ¶
type SingleLeafProof struct {
Proof
// contains filtered or unexported fields
}
SingleLeafProof is used to convince a verifier about membership of a specific leaf h at index i on a tree. The verifier has a trusted value of the tree root hash. it corresponds to merkle verification path.
func (*SingleLeafProof) CanMarshalMsg ¶
func (_ *SingleLeafProof) CanMarshalMsg(z interface{}) bool
func (*SingleLeafProof) CanUnmarshalMsg ¶
func (_ *SingleLeafProof) CanUnmarshalMsg(z interface{}) bool
func (*SingleLeafProof) GetConcatenatedProof ¶
func (p *SingleLeafProof) GetConcatenatedProof() []byte
GetConcatenatedProof concats the verification path to a single slice This function converts an empty element in the path (i.e occurs when the tree is not a full tree) into a sequence of digest result of zero.
func (*SingleLeafProof) GetFixedLengthHashableRepresentation ¶
func (p *SingleLeafProof) GetFixedLengthHashableRepresentation() []byte
GetFixedLengthHashableRepresentation serializes the proof into a sequence of bytes. it basically concatenates the elements of the verification path one after another. The function returns a fixed length array for each hash function. which is 1 + MaxEncodedTreeDepth * digestsize
the path is guaranteed to be less than MaxEncodedTreeDepth and if the path length is less than MaxEncodedTreeDepth, array will have leading zeros (to fill the array to MaxEncodedTreeDepth * digestsize). more details could be found in the Algorand's spec.
func (*SingleLeafProof) MarshalMsg ¶
func (z *SingleLeafProof) MarshalMsg(b []byte) (o []byte)
MarshalMsg implements msgp.Marshaler
func (*SingleLeafProof) MsgIsZero ¶
func (z *SingleLeafProof) MsgIsZero() bool
MsgIsZero returns whether this is a zero value
func (*SingleLeafProof) Msgsize ¶
func (z *SingleLeafProof) Msgsize() (s int)
Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message
func (*SingleLeafProof) ToProof ¶
func (p *SingleLeafProof) ToProof() *Proof
ToProof export a Proof from a SingleProof. The result is used as an input for merklearray.Verify or merklearray.VerifyVectorCommitment
func (*SingleLeafProof) UnmarshalMsg ¶
func (z *SingleLeafProof) UnmarshalMsg(bts []byte) (o []byte, err error)
UnmarshalMsg implements msgp.Unmarshaler
type Tree ¶
type Tree struct {
// Levels represents the tree in layers. layer[0] contains the leaves.
Levels []Layer `codec:"lvls,allocbound=MaxEncodedTreeDepth+1"`
// NumOfElements represents the number of the elements in the array which the tree is built on.
// notice that the number of leaves might be larger in case of a vector commitment
// In addition, the code will not generate proofs on indexes larger than NumOfElements.
NumOfElements uint64 `codec:"nl"`
// Hash represents the hash function which is being used on elements in this tree.
Hash crypto.HashFactory `codec:"hsh"`
// IsVectorCommitment determines whether the tree was built as a vector commitment
IsVectorCommitment bool `codec:"vc"`
// contains filtered or unexported fields
}
Tree is a Merkle tree, represented by layers of nodes (hashes) in the tree at each height.
func Build ¶
func Build(array Array, factory crypto.HashFactory) (*Tree, error)
Build constructs a Merkle tree given an array. The tree can be used to generate proofs of membership on element. If a proof of position is require, a Vector Commitments is required
func BuildVectorCommitmentTree ¶
func BuildVectorCommitmentTree(array Array, factory crypto.HashFactory) (*Tree, error)
BuildVectorCommitmentTree constructs a Merkle tree given an array. the tree returned from this function can function as a vector commitment which has position binding property. (having a position binding means that an adversary can not create a commitment and open its entry i = 1 in two different ways, using proofs of different ‘depths.’)
In addition, the tree will also extend the array to have a length of 2^X leaves. i.e we always create a full tree
func (*Tree) CanMarshalMsg ¶
func (*Tree) CanUnmarshalMsg ¶
func (*Tree) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
func (*Tree) Msgsize ¶
Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message
func (*Tree) Prove ¶
Prove constructs a proof for some set of positions in the array that was used to construct the tree.
this function defines the following behavior: Tree is empty AND idxs list is empty results with an empty proof Tree is not empty AND idxs list is empty results with an empty proof Tree is empty AND idxs list not is empty results with an error Tree is not empty AND idxs list is not empty results with a proof
func (*Tree) ProveSingleLeaf ¶
func (tree *Tree) ProveSingleLeaf(idx uint64) (*SingleLeafProof, error)
ProveSingleLeaf constructs a proof for a leaf in a specific position in the array that was used to construct the tree.
func (*Tree) Root ¶
func (tree *Tree) Root() crypto.GenericDigest
Root returns the root hash of the tree. In case the tree is empty, the return value is an empty GenericDigest.
Source Files