merkletree

package module
v2.0.6 Latest Latest
Warning

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

 Go to latest Published: Jul 4, 2023 License: Apache-2.0, MIT Imports: 14 Imported by: 33

README

go-merkletree-sql GoDoc Go Report Card Test

MerkleTree compatible with version from circomlib.

Adaptation of the merkletree from https://github.com/iden3/go-iden3-core/tree/v0.0.8 with several changes and more functionalities.

Usage

More detailed examples can be found at the tests, and in the documentation.

import (
	"context"
	"math/big"
	"testing"

	"github.com/iden3/go-merkletree-sql/v2"
	"github.com/iden3/go-merkletree-sql/v2/db/memory"
	sql "github.com/iden3/go-merkletree-sql/v2/db/pgx"
	"github.com/stretchr/testify/require"
)

func TestMT(t *testing.T) {
	mtDepth := 40     // maximum depth of the tree
	mtId := uint64(1) // id of tree in sql database, you can have multiple trees with different ids
	ctx := context.Background()

	var treeStorage merkletree.Storage

	// setup pgxConn here
	treeStorage = sql.NewSqlStorage(pgxConn, mtId)
	// OR
	treeStorage = memory.NewMemoryStorage()

	mt, err := merkletree.NewMerkleTree(ctx, treeStorage, mtDepth)
	require.NoError(t, err)

	err = mt.Add(ctx, big.NewInt(1), big.NewInt(2))
	require.NoError(t, err)

	proof, _, err := mt.GenerateProof(ctx, big.NewInt(1), mt.Root())
	require.NoError(t, err)

	valid := merkletree.VerifyProof(mt.Root(), proof, big.NewInt(1), big.NewInt(2))
	require.True(t, valid)
}

Contributing

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as below, without any additional terms or conditions.

License

Copyright 2023 0kims Association

This project is licensed under either of

at your option.

Documentation

Index

Constants

View Source 
const (

	// IndexLen indicates how many elements are used for the index.
	IndexLen = 4
	// DataLen indicates how many elements are used for the data.
	DataLen = 8
)
View Source 
const (
	// ElemBytesLen is the length of the Hash byte array
	ElemBytesLen = 32
)

Variables

View Source 
var (
	// ErrNodeKeyAlreadyExists is used when a node key already exists.
	ErrNodeKeyAlreadyExists = errors.New("key already exists")
	// ErrKeyNotFound is used when a key is not found in the MerkleTree.
	ErrKeyNotFound = errors.New("Key not found in the MerkleTree")
	// ErrNodeBytesBadSize is used when the data of a node has an incorrect
	// size and can't be parsed.
	ErrNodeBytesBadSize = 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")
)
View Source 
var ErrNotFound = errors.New("key not found")

ErrNotFound is used by the implementations of the interface db.Storage for when a key is not found in the storage

View Source 
var (
	// HashZero is used at Empty nodes
	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}
)

Functions

func BytesToUint16 

func BytesToUint16(b []byte) uint16

BytesToUint16 returns a uint16 from a byte array

func CheckEntryInField 

func CheckEntryInField(e Entry) bool

func Clone 

func Clone(b0 []byte) []byte

Clone clones a byte array into a new byte array

func Concat 

func Concat(vs ...[]byte) []byte

Concat concatenates arrays of bytes

func ElemBytesToBigInts 

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

ElemBytesToBigInts serializes an array of ElemBytes to []byte.

func ElemBytesToBytes 

func ElemBytesToBytes(es []ElemBytes) []byte

ElemBytesToBytes serializes an array of ElemBytes to []byte.

func NewBigIntFromHashBytes 

func NewBigIntFromHashBytes(b []byte) (*big.Int, error)

NewBigIntFromHashBytes returns a *big.Int from a byte array, swapping the endianness in the process. This is the intended method to get a *big.Int from a byte array that previously has ben generated by the Hash.Bytes() method.

func SetBitBigEndian 

func SetBitBigEndian(bitmap []byte, n uint)

SetBitBigEndian sets the bit n in the bitmap to 1, in Big Endian.

func SwapEndianness 

func SwapEndianness(b []byte) []byte

SwapEndianness swaps the order of the bytes in the slice.

func TestBit 

func TestBit(bitmap []byte, n uint) bool

TestBit tests whether the bit n in bitmap is 1.

func TestBitBigEndian 

func TestBitBigEndian(bitmap []byte, n uint) bool

TestBitBigEndian tests whether the bit n in bitmap is 1, in Big Endian.

func Uint16ToBytes 

func Uint16ToBytes(u uint16) []byte

Uint16ToBytes returns a byte array from a uint16

func VerifyProof 

func VerifyProof(rootKey *Hash, proof *Proof, k, v *big.Int) bool

VerifyProof verifies the Merkle Proof for the entry and root.

Types

type CircomProcessorProof 

type CircomProcessorProof struct {
	OldRoot  *Hash   `json:"oldRoot"`
	NewRoot  *Hash   `json:"newRoot"`
	Siblings []*Hash `json:"siblings"`
	OldKey   *Hash   `json:"oldKey"`
	OldValue *Hash   `json:"oldValue"`
	NewKey   *Hash   `json:"newKey"`
	NewValue *Hash   `json:"newValue"`
	IsOld0   bool    `json:"isOld0"`
	// 0: NOP, 1: Update, 2: Insert, 3: Delete
	Fnc int `json:"fnc"`
}

CircomProcessorProof defines the ProcessorProof compatible with circom. Is the data of the proof between the transition from one state to another.

func (CircomProcessorProof) String 

func (p CircomProcessorProof) String() string

String returns a human readable string representation of the CircomProcessorProof

type CircomVerifierProof 

type CircomVerifierProof struct {
	Root     *Hash   `json:"root"`
	Siblings []*Hash `json:"siblings"`
	OldKey   *Hash   `json:"oldKey"`
	OldValue *Hash   `json:"oldValue"`
	IsOld0   bool    `json:"isOld0"`
	Key      *Hash   `json:"key"`
	Value    *Hash   `json:"value"`
	Fnc      int     `json:"fnc"` // 0: inclusion, 1: non inclusion
}

CircomVerifierProof defines the VerifierProof compatible with circom. Is the data of the proof that a certain leaf exists in the MerkleTree.

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

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

func (*ElemBytes) BigInt 

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 (*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 

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 [32]byte

Hash is the generic type stored in the MerkleTree

func CircomSiblingsFromSiblings 

func CircomSiblingsFromSiblings(siblings []*Hash, levels int) []*Hash

CircomSiblingsFromSiblings returns the full siblings compatible with circom

func HashElems 

func HashElems(elems ...*big.Int) (*Hash, error)

HashElems performs a poseidon hash over the array of ElemBytes, currently we are using 2 elements. Uses poseidon.Hash to be compatible with the circom circuits implementations.

func HashElemsKey 

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

HashElemsKey performs a poseidon hash over the array of ElemBytes, currently we are using 2 elements.

func LeafKey 

func LeafKey(k, v *Hash) (*Hash, error)

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

func NewHashFromBigInt 

func NewHashFromBigInt(b *big.Int) (*Hash, error)

NewHashFromBigInt returns a *Hash representation of the given *big.Int

func NewHashFromHex 

func NewHashFromHex(h string) (*Hash, error)

NewHashFromHex returns a *Hash representation of the given hex string

func NewHashFromString 

func NewHashFromString(s string) (*Hash, error)

NewHashFromString returns a *Hash representation of the given decimal string

func RootFromProof 

func RootFromProof(proof *Proof, k, v *big.Int) (*Hash, error)

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

func SiblingsFromProof 

func SiblingsFromProof(proof *Proof) []*Hash

SiblingsFromProof returns all the siblings of the proof.

func (*Hash) BigInt 

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

BigInt returns the *big.Int representation of the *Hash

func (*Hash) Equals 

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

func (Hash) Hex 

func (h Hash) Hex() string

Hex returns the hexadecimal representation of the Hash

func (Hash) MarshalText 

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

MarshalText implements the marshaler for the Hash type

func (Hash) String 

func (h Hash) String() string

String returns decimal representation in string format of the Hash

func (*Hash) UnmarshalText 

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

UnmarshalText implements the unmarshaler for the Hash type

type KV 

type KV struct {
	K []byte
	V Node
}

KV contains a key (K) and a value (V)

type KvMap 

type KvMap map[[sha256.Size]byte]KV

KvMap is a key-value map between a sha256 byte array hash, and a KV struct

func (KvMap) Get 

func (m KvMap) Get(k []byte) (Node, bool)

Get retrieves the value respective to a key from the KvMap

func (KvMap) Put 

func (m KvMap) Put(k []byte, v Node)

Put stores a key and a value in the KvMap

type MerkleTree 

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

MerkleTree is the struct with the main elements of the MerkleTree

func NewMerkleTree 

func NewMerkleTree(ctx context.Context, storage Storage,
	maxLevels int) (*MerkleTree, error)

NewMerkleTree loads a new MerkleTree. If in the storage already exists one will open that one, if not, will create a new one.

func (*MerkleTree) Add 

func (mt *MerkleTree) Add(ctx context.Context, k, v *big.Int) error

Add adds a Key & Value into the MerkleTree. Where the `k` determines the path from the Root to the Leaf.

func (*MerkleTree) AddAndGetCircomProof 

func (mt *MerkleTree) AddAndGetCircomProof(ctx context.Context,
	k, v *big.Int) (*CircomProcessorProof, error)

AddAndGetCircomProof does an Add, and returns a CircomProcessorProof

func (*MerkleTree) AddEntry 

func (mt *MerkleTree) AddEntry(ctx context.Context, e *Entry) error

AddEntry adds the Entry to the MerkleTree

func (*MerkleTree) Delete 

func (mt *MerkleTree) Delete(ctx context.Context, k *big.Int) error

Delete removes the specified Key from the MerkleTree and updates the path from the deleted key to the Root with the new values. This method removes the key from the MerkleTree, but does not remove the old nodes from the key-value database; this means that if the tree is accessed by an old Root where the key was not deleted yet, the key will still exist. If is desired to remove the key-values from the database that are not under the current Root, an option could be to dump all the leaves (using mt.DumpLeafs) and import them in a new MerkleTree in a new database (using mt.ImportDumpedLeafs), but this will loose all the Root history of the MerkleTree

func (*MerkleTree) DumpLeafs 

func (mt *MerkleTree) DumpLeafs(ctx context.Context,
	rootKey *Hash) ([]byte, error)

DumpLeafs returns all the Leafs that exist under the given Root. If no Root is given (nil), it uses the current Root of the MerkleTree.

func (*MerkleTree) GenerateCircomVerifierProof 

func (mt *MerkleTree) GenerateCircomVerifierProof(ctx context.Context,
	k *big.Int, rootKey *Hash) (*CircomVerifierProof, error)

GenerateCircomVerifierProof returns the CircomVerifierProof for a certain key in the MerkleTree. If the rootKey is nil, the current merkletree root is used.

func (*MerkleTree) GenerateProof 

func (mt *MerkleTree) GenerateProof(ctx context.Context, k *big.Int,
	rootKey *Hash) (*Proof, *big.Int, 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) GenerateSCVerifierProof 

func (mt *MerkleTree) GenerateSCVerifierProof(ctx context.Context, k *big.Int,
	rootKey *Hash) (*CircomVerifierProof, error)

GenerateSCVerifierProof returns the CircomVerifierProof for a certain key in the MerkleTree with the Siblings without the extra 0 needed at the circom circuits, which makes it straight forward to verifiy inside a Smart Contract. If the rootKey is nil, the current merkletree root is used.

func (*MerkleTree) Get 

func (mt *MerkleTree) Get(ctx context.Context,
	k *big.Int) (*big.Int, *big.Int, []*Hash, error)

Get returns the value of the leaf for the given key

func (*MerkleTree) GetNode 

func (mt *MerkleTree) GetNode(ctx context.Context, 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(ctx context.Context, 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) ImportDumpedLeafs 

func (mt *MerkleTree) ImportDumpedLeafs(ctx context.Context, b []byte) error

ImportDumpedLeafs parses and adds to the MerkleTree the dumped list of leafs from the DumpLeafs function.

func (*MerkleTree) MaxLevels 

func (mt *MerkleTree) MaxLevels() int

MaxLevels returns the MT maximum level

func (*MerkleTree) PrintGraphViz 

func (mt *MerkleTree) PrintGraphViz(ctx context.Context, rootKey *Hash) error

PrintGraphViz prints directly the GraphViz() output

func (*MerkleTree) Root 

func (mt *MerkleTree) Root() *Hash

Root returns the MerkleRoot

func (*MerkleTree) Snapshot 

func (mt *MerkleTree) Snapshot(
	ctx context.Context, rootKey *Hash) (*MerkleTree, error)

Snapshot returns a read-only copy of the MerkleTree

func (*MerkleTree) Update 

func (mt *MerkleTree) Update(ctx context.Context,
	k, v *big.Int) (*CircomProcessorProof, error)

Update updates the value of a specified key in the MerkleTree, and updates the path from the leaf to the Root with the new values. Returns the CircomProcessorProof.

func (*MerkleTree) Walk 

func (mt *MerkleTree) Walk(ctx context.Context, 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.go and merkletree_test.go

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 [2]*Hash
	// 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(k, v *Hash) *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 merkle 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 

type NodeAux struct {
	Key   *Hash `json:"key"`
	Value *Hash `json:"value"`
}

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 key &
	// value.
	NodeTypeLeaf NodeType = 1
	// NodeTypeEmpty indicates the type of an empty Node.
	NodeTypeEmpty NodeType = 2

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

type Proof 

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

	// Auxiliary node if needed
	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 NewProofFromData 

func NewProofFromData(existence bool,
	allSiblings []*Hash,
	nodeAux *NodeAux) (*Proof, error)

NewProofFromData reconstructs proof from siblings and auxiliary node

func (*Proof) AllSiblings 

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

AllSiblings returns all the siblings of the proof.

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)

MarshalJSON implements json.Marshaler interface

func (*Proof) UnmarshalJSON 

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

UnmarshalJSON implements json.Unmarshaler interface

type Storage 

type Storage interface {
	Get(context.Context, []byte) (*Node, error)
	Put(ctx context.Context, k []byte, v *Node) error
	GetRoot(context.Context) (*Hash, error)
	SetRoot(context.Context, *Hash) error
}

Storage is the interface that defines the methods for the storage used in the merkletree. Examples of the interface implementation can be found at db/memory and db/leveldb directories.

Source Files

View all Source files

Directories

Path Synopsis
db
memory
test

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.