merkletree

package
v0.0.8 Latest Latest
Warning

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

 Go to latest Published: Jun 3, 2020 License: GPL-3.0 Imports: 14 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// ElemBytesLen is the length in bytes of each element used for storing
	// data and hashing.
	ElemBytesLen = 32
	// IndexLen indicates how many elements are used for the index.
	IndexLen = 4
	// DataLen indicates how many elements are used for the data.
	DataLen = 8
)

Variables

View Source 
var (
	// ErrNodeKeyAlreadyExists is used when a node key already exists.
	ErrNodeKeyAlreadyExists = errors.New("node already exists")
	// ErrEntryIndexNotFound is used when no entry is found for an index.
	ErrEntryIndexNotFound = errors.New("node index not found in the DB")
	// ErrNodeDataBadSize is used when the data of a node has an incorrect
	// size and can't be parsed.
	ErrNodeDataBadSize = errors.New("node data has incorrect size in the DB")
	// ErrReachedMaxLevel is used when a traversal of the MT reaches the
	// maximum level.
	ErrReachedMaxLevel = errors.New("reached maximum level of the merkle tree")
	// ErrInvalidNodeFound is used when an invalid node is found and can't
	// be parsed.
	ErrInvalidNodeFound = errors.New("found an invalid node in the DB")
	// ErrInvalidProofBytes is used when a serialized proof is invalid.
	ErrInvalidProofBytes = errors.New("the serialized proof is invalid")
	// ErrInvalidDBValue is used when a value in the key value DB is
	// invalid (for example, it doen't contain a byte header and a []byte
	// body of at least len=1.
	ErrInvalidDBValue = errors.New("the value in the DB is invalid")
	// ErrEntryIndexAlreadyExists is used when the entry index already
	// exists in the tree.
	ErrEntryIndexAlreadyExists = errors.New("the entry index already exists in the tree")
	// ErrNotWritable is used when the MerkleTree is not writable and a write function is called
	ErrNotWritable = errors.New("Merkle Tree not writable")
	// ErrEntryDataNotMatch is used when the entry data doesn't match the expected one.
	ErrEntryDataNotMatch = errors.New("Entry data doesn't match the expected one")

	// HashZero is a hash value of zeros, and is the key of an empty node.
	HashZero = Hash{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	// ElemBytesOne is a constant element used as a prefix to compute leaf node keys.
	ElemBytesOne = ElemBytes{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
)

Functions

func CheckEntryInField 

func CheckEntryInField(e Entry) bool

func ElemBytesToBigInts 

func ElemBytesToBigInts(elems ...ElemBytes) []*big.Int

func ElemBytesToPoseidonInput added in v0.0.8 

func ElemBytesToPoseidonInput(elems ...ElemBytes) ([poseidon.T]*big.Int, error)

func ElemsBytesToBytes 

func ElemsBytesToBytes(es []ElemBytes) []byte

ElemsBytesToBytes serializes an array of ElemBytes to []byte.

func VerifyProof 

func VerifyProof(rootKey *Hash, proof *Proof, hIndex, hValue *Hash) bool

VerifyProof verifies the Merkle Proof for the entry and root.

Types

type Data 

type Data [DataLen]ElemBytes

Data is the type used to represent the data stored in an entry of the MT. It consists of 8 elements: e0, e1, e2, e3, ...; where v = [e0,e1], index = [e2,e3].

func BigIntsToData 

func BigIntsToData(a, b, c, d, e, f, g, h *big.Int) (data Data)

func HexsToData 

func HexsToData(_a, _b, _c, _d, _e, _f, _g, _h string) (Data, error)

func IntArrayToData 

func IntArrayToData(a []int64) Data

func IntsToData 

func IntsToData(_a, _b, _c, _d, _e, _f, _g, _h int64) Data

func NewDataFromBytes 

func NewDataFromBytes(b [ElemBytesLen * DataLen]byte) *Data

func (*Data) Bytes 

func (d *Data) Bytes() (b [ElemBytesLen * DataLen]byte)

func (*Data) Equal 

func (d1 *Data) Equal(d2 *Data) bool

func (Data) MarshalText 

func (d Data) MarshalText() ([]byte, error)

func (*Data) String 

func (d *Data) String() string

func (*Data) UnmarshalText 

func (d *Data) UnmarshalText(text []byte) error

type ElemBytes 

type ElemBytes [ElemBytesLen]byte

ElemBytes is the basic type used to store data in the MT. ElemBytes corresponds to the serialization of an element from mimc7.

func NewElemBytesFromBigInt added in v0.0.8 

func NewElemBytesFromBigInt(v *big.Int) (e ElemBytes)

func (*ElemBytes) BigInt added in v0.0.8 

func (e *ElemBytes) BigInt() *big.Int

func (*ElemBytes) String 

func (e *ElemBytes) String() string

String returns the first 4 bytes of ElemBytes in hex.

type Entrier 

type Entrier interface {
	Entry() *Entry
}

type Entry 

type Entry struct {
	Data Data
	// contains filtered or unexported fields
}

Entry is the generic type that is stored in the MT. The entry should not be modified after creating because the cached hIndex and hValue won't be updated.

func NewEntryFromBytes 

func NewEntryFromBytes(b []byte) (*Entry, error)

func NewEntryFromHexs 

func NewEntryFromHexs(a, b, c, d, e, f, g, h string) (entry Entry, err error)

func NewEntryFromIntArray 

func NewEntryFromIntArray(a []int64) Entry

func NewEntryFromInts 

func NewEntryFromInts(a, b, c, d, e, f, g, h int64) (entry Entry)

func (*Entry) Bytes 

func (e *Entry) Bytes() []byte

func (*Entry) Clone 

func (e *Entry) Clone() *Entry

func (*Entry) Equal 

func (e1 *Entry) Equal(e2 *Entry) bool

func (*Entry) HIndex 

func (e *Entry) HIndex() (*Hash, error)

HIndex calculates the hash of the Index of the Entry, used to find the path from the root to the leaf in the MT.

func (*Entry) HValue 

func (e *Entry) HValue() (*Hash, error)

HValue calculates the hash of the Value of the Entry

func (*Entry) HiHv added in v0.0.8 

func (e *Entry) HiHv() (*Hash, *Hash, error)

HiHv returns the HIndex and HValue of the Entry

func (*Entry) Index 

func (e *Entry) Index() []ElemBytes

func (Entry) MarshalText 

func (e Entry) MarshalText() ([]byte, error)

func (*Entry) UnmarshalText 

func (e *Entry) UnmarshalText(text []byte) error

func (*Entry) Value 

func (e *Entry) Value() []ElemBytes

type Hash 

type Hash ElemBytes

Hash is the type used to represent a hash used in the MT.

func HashElems 

func HashElems(elems ...ElemBytes) (*Hash, error)

HashElems performs a poseidon hash over the array of ElemBytes. Uses poseidon.PoseidonHash to be compatible with the circom circuits implementations. The maxim slice input size is poseidon.T

func HashElemsKey 

func HashElemsKey(key *big.Int, elems ...ElemBytes) (*Hash, error)

HashElemsKey performs a poseidon hash over the array of ElemBytes.

func HexStringToHash 

func HexStringToHash(s string) Hash

HexStringToHash decodes a hex string into a Hash.

func LeafKey 

func LeafKey(hIndex, hValue *Hash) (*Hash, error)

LeafKey computes the key of a leaf node given the hIndex and hValue of the entry of the leaf.

func NewHashFromBigInt added in v0.0.8 

func NewHashFromBigInt(e *big.Int) *Hash

func RootFromProof 

func RootFromProof(proof *Proof, hIndex, hValue *Hash) (*Hash, error)

RootFromProof calculates the root that would correspond to a tree whose siblings are the ones in the proof with the claim hashing to hIndex and hValue.

func SiblingsFromProof added in v0.0.8 

func SiblingsFromProof(proof *Proof) []*Hash

SiblingsFromProof returns all the siblings of the proof. This function is used to generate the siblings input for the circom circuits.

func (*Hash) BigInt added in v0.0.8 

func (h *Hash) BigInt() *big.Int

func (Hash) Bytes 

func (h Hash) Bytes() []byte

Bytes returns a byte array from a Hash.

func (*Hash) Equals 

func (h1 *Hash) Equals(h2 *Hash) bool

func (Hash) Hex 

func (h Hash) Hex() string

Hex returns a hex string from the Hash type.

func (Hash) MarshalText 

func (h Hash) MarshalText() ([]byte, error)

func (*Hash) String 

func (h *Hash) String() string

String returns the last 4 bytes of Hash in hex.

func (*Hash) UnmarshalText 

func (h *Hash) UnmarshalText(bs []byte) error

type Index 

type Index [IndexLen]ElemBytes

Index is the type used to represent the index of an entry in the MT, used to find the path from the root to the leaf that contains such entry.

type MerkleTree 

type MerkleTree struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

MerkleTree is the struct with the main elements of the Merkle Tree

func NewMerkleTree 

func NewMerkleTree(storage db.Storage, maxLevels int) (*MerkleTree, error)

NewMerkleTree generates a new Merkle Tree

func (*MerkleTree) AddClaim 

func (mt *MerkleTree) AddClaim(e Entrier) error

AddClaim adds the Claim that fullfills the Entrier interface to the MerkleTree

func (*MerkleTree) AddEntry 

func (mt *MerkleTree) AddEntry(e *Entry) error

AddEntry adds the Entry to the MerkleTree

func (*MerkleTree) DumpClaims 

func (mt *MerkleTree) DumpClaims(rootKey *Hash) ([]string, error)

DumpClaims outputs a list of all the claims in hex.

func (*MerkleTree) DumpClaimsIoWriter 

func (mt *MerkleTree) DumpClaimsIoWriter(w io.Writer, rootKey *Hash) error

DumpClaimsIoWriter uses Walk function to get all the Claims of the tree and write them to w. The output is JSON encoded with claims in hex.

func (*MerkleTree) DumpTree 

func (mt *MerkleTree) DumpTree(w io.Writer, rootKey *Hash) error

DumpTree outputs a list of all the key value in hex. Notice that this will output the full tree, which is not needed to reconstruct the Tree. To reconstruct the tree can be done from the output of DumpClaims funtion. The difference between DumpTree and DumpClaims is that with DumpTree the size of the output will be almost the double (in raw bytes, but with the current implementation DumpTree output is even smaller than DumpClaims output size, but because DumpTree stores in binary while DumpClaims stores in hex) but to recover the tree will not need to compute the Tree, while with DumpClaims will require to compute the Tree (with the computational cost of each hash)

func (*MerkleTree) EntryExists 

func (mt *MerkleTree) EntryExists(entry *Entry, rootKey *Hash) error

EntryExists checks if a given entry is in the merkle tree starting from the rootKey. If rootKey is nil, the current merkle tree root is used.

func (*MerkleTree) GenerateProof 

func (mt *MerkleTree) GenerateProof(hIndex *Hash, rootKey *Hash) (*Proof, error)

GenerateProof generates the proof of existence (or non-existence) of an Entry's hash Index for a Merkle Tree given the root. If the rootKey is nil, the current merkletree root is used

func (*MerkleTree) GetDataByIndex 

func (mt *MerkleTree) GetDataByIndex(hIndex *Hash) (*Data, error)

GetDataByIndex returns the data from the MT in the position of the hash of the index (hIndex)

func (*MerkleTree) GetNode 

func (mt *MerkleTree) GetNode(key *Hash) (*Node, error)

GetNode gets a node by key from the MT. Empty nodes are not stored in the tree; they are all the same and assumed to always exist.

func (*MerkleTree) GraphViz 

func (mt *MerkleTree) GraphViz(w io.Writer, rootKey *Hash) error

GraphViz uses Walk function to generate a string GraphViz representation of the tree and writes it to w

func (*MerkleTree) ImportDumpedClaims 

func (mt *MerkleTree) ImportDumpedClaims(dumpedClaims []string) error

ImportClaims parses and adds the dumped list of claims in hex from the DumpClaims function.

func (*MerkleTree) ImportTree 

func (mt *MerkleTree) ImportTree(i io.Reader) error

ImportTree imports the tree from the output from the DumpTree function

func (*MerkleTree) MaxLevels 

func (mt *MerkleTree) MaxLevels() int

MaxLevels returns the MT maximum level

func (*MerkleTree) PrintGraphViz added in v0.0.8 

func (mt *MerkleTree) PrintGraphViz(rootKey *Hash) error

PrintGraphViz prints directly the GraphViz() output

func (*MerkleTree) RootKey 

func (mt *MerkleTree) RootKey() *Hash

RootKey returns the MT root node key

func (*MerkleTree) Snapshot 

func (mt *MerkleTree) Snapshot(rootKey *Hash) (*MerkleTree, error)

func (*MerkleTree) Storage 

func (mt *MerkleTree) Storage() db.Storage

Storage returns the MT storage

func (*MerkleTree) Walk 

func (mt *MerkleTree) Walk(rootKey *Hash, f func(*Node)) error

Walk iterates over all the branches of a MerkleTree with the given rootKey if rootKey is nil, it will get the current RootKey of the current state of the MerkleTree. For each node, it calls the f function given in the parameters. See some examples of the Walk function usage in the merkletree_test.go test functions: TestMTWalk, TestMTWalkGraphViz, TestMTWalkDumpClaims

type Node 

type Node struct {
	// Type is the type of node in the tree.
	Type NodeType
	// ChildL is the left child of a middle node.
	ChildL *Hash
	// ChildR is the right child of a middle node.
	ChildR *Hash
	// Entry is the data stored in a leaf node.
	Entry *Entry
	// contains filtered or unexported fields
}

Node is the struct that represents a node in the MT. The node should not be modified after creation because the cached key won't be updated.

func NewNodeEmpty 

func NewNodeEmpty() *Node

NewNodeEmpty creates a new empty node.

func NewNodeFromBytes 

func NewNodeFromBytes(b []byte) (*Node, error)

NewNodeFromBytes creates a new node by parsing the input []byte.

func NewNodeLeaf 

func NewNodeLeaf(entry *Entry) *Node

NewNodeLeaf creates a new leaf node.

func NewNodeMiddle 

func NewNodeMiddle(childL *Hash, childR *Hash) *Node

NewNodeMiddle creates a new middle node.

func (*Node) Key 

func (n *Node) Key() (*Hash, error)

Key computes the key of the node by hashing the content in a specific way for each type of node. This key is used as the hash of the merklee tree for each node.

func (*Node) String 

func (n *Node) String() string

String outputs a string representation of a node (different for each type).

func (*Node) Value 

func (n *Node) Value() []byte

Value returns the value of the node. This is the content that is stored in the backend database.

type NodeAux added in v0.0.8 

type NodeAux struct {
	//key    *Hash
	HIndex *Hash
	HValue *Hash
}

NodeAux contains the auxiliary node used in a non-existence proof.

type NodeType 

type NodeType byte

NodeType defines the type of node in the MT. 

const (
	// NodeTypeMiddle indicates the type of middle Node that has children.
	NodeTypeMiddle NodeType = 0
	// NodeTypeLeaf indicates the type of a leaf Node that contains a claim.
	NodeTypeLeaf NodeType = 1
	// NodeTypeEmpty indicates the type of an empty Node.
	NodeTypeEmpty NodeType = 2

	// DBEntryTypeRoot indicates the type of a DB entry that indicates the current Root of a MerkleTree
	DBEntryTypeRoot NodeType = 3
)

type Proof 

type Proof struct {
	// existence indicates wether this is a proof of existence or non-existence.
	Existence bool

	// Siblings is a list of non-empty sibling keys.
	Siblings []*Hash
	NodeAux  *NodeAux
	// contains filtered or unexported fields
}

Proof defines the required elements for a MT proof of existence or non-existence.

func NewProofFromBytes 

func NewProofFromBytes(bs []byte) (*Proof, error)

NewProofFromBytes parses a byte array into a Proof.

func (*Proof) AllSiblings added in v0.0.8 

func (p *Proof) AllSiblings() []*Hash

func (*Proof) AllSiblingsCircom added in v0.0.8 

func (p *Proof) AllSiblingsCircom(levels int) []*big.Int

func (*Proof) Bytes 

func (p *Proof) Bytes() []byte

Bytes serializes a Proof into a byte array.

func (Proof) MarshalJSON 

func (p Proof) MarshalJSON() ([]byte, error)

func (Proof) String 

func (p Proof) String() string

String outputs a multiline string representation of the Proof.

func (*Proof) UnmarshalJSON 

func (p *Proof) UnmarshalJSON(bs []byte) error

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.