merklearray

Documentation

Index

• Constants
• Variables
• func Verify(root stateproofcrypto.GenericDigest, ...) error
• func VerifyVectorCommitment(root stateproofcrypto.GenericDigest, ...) error
• type Layer
• type Proof
• type SingleLeafProof
  • func (p *SingleLeafProof) GetFixedLengthHashableRepresentation() []byte
  • func (p *SingleLeafProof) MsgIsZero() bool
  • func (p *SingleLeafProof) ToProof() *Proof
• type Tree

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
)

const MerkleArrayNode stateproofcrypto.HashID = "MA"

Variables

var (
	ErrRootMismatch                  = errors.New("root mismatch")
	ErrProofIsNil                    = errors.New("proof should not be nil")
	ErrNonEmptyProofForEmptyElements = errors.New("non-empty proof for empty set of elements")
	ErrPosOutOfBound                 = errors.New("pos out of bound")
)

Merkle tree errors

Functions

func Verify

func Verify(root stateproofcrypto.GenericDigest, elems map[uint64]stateproofcrypto.Hashable, proof *Proof) error

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 stateproofcrypto.GenericDigest, elems map[uint64]stateproofcrypto.Hashable, proof *Proof) error

VerifyVectorCommitment verifies a vector commitment proof against a given root.

Types

type Layer

type Layer []stateproofcrypto.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.

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        []stateproofcrypto.GenericDigest `codec:"pth,allocbound=MaxNumLeavesOnEncodedTree/2"`
	HashFactory stateproofcrypto.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.

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

func (p *SingleLeafProof) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

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

type Tree

type Tree struct {

	// Levels represents the tree in layers. layer[0] contains the leaves.
	Levels []Layer `codec:"lvls,allocbound=stateproofcrypto.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 stateproofcrypto.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.