merklearray

package
v0.0.0-...-ff2c966 Latest Latest
Warning

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

 Go to latest Published: Apr 30, 2024 License: AGPL-3.0 Imports: 13 Imported by: 0

Documentation

Index

Constants

View Source 
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

View Source 
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")
	ErrProofLengthDigestSizeMismatch = errors.New("proof length and digest size mismatched")
)

Merkle tree errors

View Source 
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 LayerMaxSize 

func LayerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProofMaxSize 

func ProofMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProofMaxSizeByElements 

func ProofMaxSizeByElements(n int) (s int)

ProofMaxSizeByElements returns the maximum msgp encoded size of merklearray.Proof structs containing n signatures This is necessary because the allocbounds on the proof are actual theoretical bounds but for calculating maximum proof size for individual message types we have smaller valid bounds. Exported because it's used in the stateproof package for ensuring that SigPartProof constant is correct size.

func SingleLeafProofMaxSize 

func SingleLeafProofMaxSize() int

SingleLeafProofMaxSize returns the maximum msgp encoded size of proof verifying a single leaf It is manually defined here instead of letting msgp do it since we cannot annotate the embedded Proof struct with maxtotalbytes for msgp to autogenerate it.

func TreeMaxSize 

func TreeMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func Verify 

func Verify(root crypto.GenericDigest, elems map[uint64]crypto.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 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) CanMarshalMsg(z interface{}) bool

func (*Layer) CanUnmarshalMsg 

func (_ *Layer) CanUnmarshalMsg(z interface{}) bool

func (Layer) MarshalMsg 

func (z Layer) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (Layer) MsgIsZero 

func (z Layer) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (Layer) Msgsize 

func (z Layer) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Layer) UnmarshalMsg 

func (z *Layer) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*Layer) UnmarshalMsgWithState 

func (z *Layer) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

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. Path is bounded by MaxNumLeaves 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^MaxTreeDepth / 2

. Consider two different reveals for the same tree: . . z5 . z3 z4 . y z z1 z2 . q r s t u v w x . a b c d e f g h i j k l m n o p . ^ . hints: [a, r, z, z4] . len(hints) = 4 . You need a to combine with b to get q, need r to combine with the computed q and get y, and so on. . The worst case is this: . . z5 . z3 z4 . y z z1 z2 . q r s t u v w x . a b c d e f g h i j k l m n o p . ^ ^ ^ ^ ^ ^ ^ ^ . . hints: [b, d, e, g, j, l, m, o] . len(hints) = 2^4/2

func (*Proof) CanMarshalMsg 

func (_ *Proof) CanMarshalMsg(z interface{}) bool

func (*Proof) CanUnmarshalMsg 

func (_ *Proof) CanUnmarshalMsg(z interface{}) bool

func (*Proof) MarshalMsg 

func (z *Proof) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (*Proof) MsgIsZero 

func (z *Proof) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (*Proof) Msgsize 

func (z *Proof) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Proof) UnmarshalMsg 

func (z *Proof) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*Proof) UnmarshalMsgWithState 

func (z *Proof) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

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. The msgp directive belows tells msgp to not generate SingleLeafProofMaxSize method since we have one manually defined in this file.

func ProofDataToSingleLeafProof 

func ProofDataToSingleLeafProof(hashTypeData string, proofBytes []byte) (SingleLeafProof, error)

ProofDataToSingleLeafProof receives serialized proof data and uses it to construct a proof object.

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

func (*SingleLeafProof) UnmarshalMsgWithState 

func (z *SingleLeafProof) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (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) CanMarshalMsg(z interface{}) bool

func (*Tree) CanUnmarshalMsg 

func (_ *Tree) CanUnmarshalMsg(z interface{}) bool

func (*Tree) MarshalMsg 

func (z *Tree) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (*Tree) MsgIsZero 

func (z *Tree) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (*Tree) Msgsize 

func (z *Tree) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Tree) Prove 

func (tree *Tree) Prove(idxs []uint64) (*Proof, error)

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.

func (*Tree) UnmarshalMsg 

func (z *Tree) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*Tree) UnmarshalMsgWithState 

func (z *Tree) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

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.