Documentation
¶
Index ¶
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.
Source Files