utreexo

package module
v0.1.5 Latest Latest
Warning

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

 Go to latest Published: May 2, 2024 License: MIT Imports: 10 Imported by: 6

README

Utreexo

A hash based dynamic accumulator based on a merkle forest

Installation

go get github.com/utreexo/utreexo

Requirements

  • Need at least go1.18 or newer.

Usage

Utreexo is a data structure made of a collection of merkle trees. It allows for a compact representation of a set of elements and supports the following 4 operations:

  • Add Elements
  • Remove Elements
  • Prove Elements
  • Verify Merkle Proofs

Detailed writeup with playground links on the 4 operations are available at this Github Gist.

A prover keeps the entire merkle forest and is able to support all 4 operations.

A verifier only keeps the roots of the merkle forest and is not able to support proving elements. However, a verifier may choose to cache proof for some elements and be able to prove those specific elements.

// Prover supports all 4 operations.
prover := utreexo.NewAccumulator()

// Verifer does not support proving elements.
verifier := utreexo.Stump{}

// A verifier may keep the below to cache the leaves and the merkle branches
// for some of the elements.
cachedHashes := []utreexo.Hash{}
cachedProof := utreexo.Proof{}

Add :

data := []string{"utxo1", "utxo2", "utxo3", "utxo4"}

// Hash the data as the accumulator expects []utreexo.Hash (utreexo.Hash is just [32]byte).
// These hashes are commitments to the elements we're adding.
hashes := make([]utreexo.Hash, len(data))
leaves := make([]utreexo.Leaf, len(data))
for i, d := range data {
	hash := sha256.Sum256([]byte(d))
	hashes[i] = hash
	leaves[i] = utreexo.Leaf{Hash: hash}
}

// Add the elements to the prover and the verifier.
prover.Modify(leaves, nil, utreexo.Proof{})

updateData, _ := verifier.Update(nil, hashes, utreexo.Proof{})

// If we want to cache the proof for "utxo4", we give the index of the element to cache.
rememberIndexes := []uint32{3}
cachedHashes, _ = cachedProof.Update(cachedHashes, hashes, nil, rememberIndexes, updateData)

Delete :

// Now let's delete the element "utxo1" from the accumulator.
//
// For deletion, we first need to first prove the hashes of the elements being deleted.
proof, _ := prover.Prove(hashes[:1])

// Delete "utxo1" from the accumulator.
prover.Modify(nil, hashes[:1], proof)

// For the verifier, we need to first verify the proof before updating the state as
// the prover may give out false proofs.
_, err := utreexo.Verify(verifier, hashes[:1], proof)
if err != nil {
	fmt.Printf("Verify fail for proof %s. Error: %v\n", proof.String(), err)
	os.Exit(1)
}

// If the proof is correct, we can now modify the state of the verifier and delete "utxo1".
updateData, _ = verifier.Update(hashes[:1], nil, proof)

// Update the proof cache.
cachedHashes, _ = cachedProof.Update(cachedHashes, hashes[:1], proof.Targets, nil, updateData)

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AddProof 

func AddProof(proofA, proofB Proof, targetHashesA, targetHashesB []Hash, numLeaves uint64) ([]Hash, Proof)

AddProof adds the newProof onto the existing proof and return the new cachedDelHashes and proof. Newly calculateable positions and duplicates are excluded in the returned proof.

func AllSubTreesToString 

func AllSubTreesToString(ts ToString) string

AllSubTreesToString returns a string of all the individual subtrees in the accumulator.

func GetMissingPositions 

func GetMissingPositions(numLeaves uint64, proofTargets, desiredTargets []uint64) []uint64

GetMissingPositions returns the positions missing in the proof to proof the desiredTargets.

The proofTargets being passed in MUST be a from a valid proof. Having an invalid proof may result in errors.

The passed in desiredTargets also MUST be a valid position in the accumulator. There are no checks to make sure the desiredTargets exist in the accumulator so the caller must check that they indeed do exist.

func GetProofSubset 

func GetProofSubset(proof Proof, hashes []Hash, wants []uint64, numLeaves uint64) ([]Hash, Proof, error)

GetProofSubset trims away the un-needed data from the proof and returns a proof only for the passed in removes. An error is returned if the passed in proof does not have all the targets in the removes.

NOTE The returned hashes and proof targets are in the same permutation as the given wants.

func RootPositions 

func RootPositions(numLeaves uint64, totalRows uint8) []uint64

RootPositions returns all the rootPositions for the given numLeaves and totalRows.

func String 

func String(ts ToString) string

String prints out the whole thing. Only viable for forest that have height of 5 and less.

func SubTreeToString 

func SubTreeToString(ts ToString, position uint64, inHex bool) string

SubTreeToString returns a string of the subtree that the position is in.

func Verify 

func Verify(stump Stump, delHashes []Hash, proof Proof) ([]int, error)

Verify verifies the proof passed in against the passed in stump. The returned ints are the indexes of the roots that were matched with the roots calculated from the proof.

Types

type CachedLeavesInterface 

type CachedLeavesInterface interface {
	// Get returns the position and a boolean to indicate if it was found or not.
	Get(Hash) (uint64, bool)

	// Put puts the given hash and position.
	Put(Hash, uint64)

	// Delete removes the given hash.
	Delete(Hash)

	// Length returns the count of all the elements.
	Length() int

	// ForEach iterates through all the elements saved and calls the passed in
	// function for each one of them.
	ForEach(func(Hash, uint64) error) error
}

CachedLeavesInterface models the interface for the data storage for the map pollard.

type Hash 

type Hash [32]byte

Hash is the 32 byte of a 256 bit hash.

func (Hash) String 

func (h Hash) String() string

String returns a hex encoded string of the hash.

type Leaf 

type Leaf struct {
	Hash
	Remember bool
}

Leaf contains a hash and a hint about whether it should be cached.

func (Leaf) String 

func (l Leaf) String() string

String returns the leaf as a human-readable string.

type MapPollard 

type MapPollard struct {

	// CachedLeaves are the positions of the leaves that we always have cached.
	CachedLeaves CachedLeavesInterface

	// Nodes are the leaves in the accumulator. The hashes are mapped to their
	// position in the accumulator.
	Nodes NodesInterface

	// NumLeaves are the number of total additions that have happened in the
	// accumulator.
	NumLeaves uint64

	// TotalRows is the number of rows the accumulator has allocated for.
	TotalRows uint8

	// Full marks all the added leaves to be remembered if set to true.
	Full bool
	// contains filtered or unexported fields
}

MapPollard is an implementation of the utreexo accumulators that supports pollard functionality.

func NewMapPollard 

func NewMapPollard(full bool) MapPollard

NewMapPollard returns a MapPollard with the nodes map initialized. Passing the full boolean as true will make the map pollard cache all leaves.

NOTE: The default total rows is set to 63. This avoids costly remapping. For printing out the pollard for debugging purposes, set TotalRows 0 for pretty printing.

func NewMapPollardFromRoots 

func NewMapPollardFromRoots(rootHashes []Hash, numLeaves uint64, full bool) MapPollard

NewMapPollardFromRoots returns a new MapPollard initialized with the roots and the numLeaves that was passed in.

func (*MapPollard) AllSubTreesToString 

func (m *MapPollard) AllSubTreesToString() string

AllSubTreesToString returns a string of all the individual subtrees in the accumulator.

func (*MapPollard) GetHash 

func (m *MapPollard) GetHash(pos uint64) Hash

GetHash returns the hash for the given position. Empty hash (all values are 0) is returned if the given position is not cached.

func (*MapPollard) GetLeafHashPositions 

func (m *MapPollard) GetLeafHashPositions(hashes []Hash) []uint64

GetLeafHashPositions returns the positions for the given leaf hashes. If the leaf hash doesn't exist or if the leaf hash isn't cached, it'll be the default value of 0.

func (*MapPollard) GetLeafPosition 

func (m *MapPollard) GetLeafPosition(hash Hash) (uint64, bool)

GetLeafPosition returns the position of the leaf for the given hash. Returns false if the hash is not the hash of a leaf or if the hash wasn't found in the accumulator.

func (*MapPollard) GetMissingPositions 

func (m *MapPollard) GetMissingPositions(origTargets []uint64) []uint64

GetMissingPositions returns all the missing positions that are needed to verify the given targets.

func (*MapPollard) GetNumLeaves 

func (m *MapPollard) GetNumLeaves() uint64

GetNumLeaves returns the number of leaves that were ever added to the accumulator.

func (*MapPollard) GetRoots 

func (m *MapPollard) GetRoots() []Hash

getRoots returns the hashes of the roots.

func (*MapPollard) GetStump 

func (m *MapPollard) GetStump() Stump

GetStump returns a stump with the values fetched from the pollard.

func (*MapPollard) GetTreeRows 

func (m *MapPollard) GetTreeRows() uint8

GetTreeRows returns the tree rows that are allocated for this accumulator.

func (*MapPollard) Ingest 

func (m *MapPollard) Ingest(delHashes []Hash, proof Proof) error

Ingest places the proof in the tree and remembers them.

NOTE: there's no verification done that the passed in proof is valid. It's the caller's responsibility to verify that the given proof is valid.

func (*MapPollard) Modify 

func (m *MapPollard) Modify(adds []Leaf, delHashes []Hash, proof Proof) error

Modify takes in the additions and deletions and updates the accumulator accordingly.

func (*MapPollard) Prove 

func (m *MapPollard) Prove(proveHashes []Hash) (Proof, error)

Prove returns a proof of all the targets that are passed in. TODO: right now it refuses to prove anything but the explicitly cached leaves. There may be some leaves that it could prove that's not cached due to the proofs overlapping.

func (*MapPollard) Prune 

func (m *MapPollard) Prune(hashes []Hash) error

Prune prunes the passed in hashes and the proofs for them. Will not prune the proof if it's needed for another cached hash.

func (*MapPollard) Read 

func (m *MapPollard) Read(r io.Reader) (int, error)

Read reads the pollard from the reader into the map pollard variable.

func (*MapPollard) String 

func (m *MapPollard) String() string

String prints out the whole thing. Only viable for forest that have height of 5 and less.

func (*MapPollard) Undo 

func (m *MapPollard) Undo(numAdds uint64, proof Proof, hashes, origPrevRoots []Hash) error

Undo will undo the last modify. The numAdds, proof, hashes, MUST be the data from the previous modify. The origPrevRoots MUST be the roots that this Undo will go back to.

func (*MapPollard) Verify 

func (m *MapPollard) Verify(delHashes []Hash, proof Proof, remember bool) error

Verify returns an error if the given proof and the delHashes do not hash up to the stored roots. Passing the remember flag as true will cause the proof to be cached.

func (*MapPollard) VerifyPartialProof 

func (m *MapPollard) VerifyPartialProof(origTargets []uint64, delHashes, proofHashes []Hash, remember bool) error

VerifyPartialProof takes partial proof of the targets and attempts to prove their existence. If the remember bool is false, the accumulator is not modified. If it is true, the necessary hashes to prove the targets are cached.

NOTE: proofHashes MUST be sorted in relation to their positions in the accumulator.

func (*MapPollard) Write 

func (m *MapPollard) Write(w io.Writer) (int, error)

Write writes the entire pollard to the writer.

type NodesInterface 

type NodesInterface interface {
	// Get returns the position and a boolean to indicate if it was found or not.
	Get(uint64) (Leaf, bool)

	// Put puts the given hash and position.
	Put(uint64, Leaf)

	// Delete removes the given hash.
	Delete(uint64)

	// Length returns the count of all the elements.
	Length() int

	// ForEach iterates through all the elements saved and calls the passed in
	// function for each one of them.
	ForEach(func(uint64, Leaf) error) error
}

NodesInterface models the interface for the data storage for the map pollard.

type NodesMap 

type NodesMap struct {
	// contains filtered or unexported fields
}

NodesMap implements the NodesInterface interface. It's really just a map.

func (*NodesMap) Delete 

func (m *NodesMap) Delete(k uint64)

Delete removes the given key from the underlying map. No-op if the key doesn't exist.

func (*NodesMap) ForEach 

func (m *NodesMap) ForEach(fn func(uint64, Leaf) error) error

ForEach calls the given function for each of the elements in the underlying map.

func (*NodesMap) Get 

func (m *NodesMap) Get(k uint64) (Leaf, bool)

Get returns the data from the underlying map.

func (*NodesMap) Length 

func (m *NodesMap) Length() int

Length returns the amount of items in the underlying map.

func (*NodesMap) Put 

func (m *NodesMap) Put(k uint64, v Leaf)

Put puts the given data to the underlying map.

type Pollard 

type Pollard struct {
	// NodeMap maps hashes to polNodes. Used during proving individual elements
	// in the accumulator.
	NodeMap map[miniHash]*polNode

	// Roots are the roots of each tree in the forest.
	//
	// NOTE: Since roots don't have nieces, they point to children.
	// In the below tree, 06 is the root and it points to its children,
	// 04 and 05. However, 04 points to 02 and 03; 05 points to 00 and 01.
	// 04 and 05 are pointing to their nieces.
	//
	// 06
	// |-------\
	// 04      05
	// |---\   |---\
	// 00  01  02  03
	Roots []*polNode

	// NumLeaves is the number of all leaves that were ever added to the accumulator.
	NumLeaves uint64

	// NumDels is the number of all elements that were deleted from the accumulator.
	NumDels uint64
	// contains filtered or unexported fields
}

Pollard is a representation of the utreexo forest using a collection of binary trees. It contains the entire set.

func NewAccumulator 

func NewAccumulator() Pollard

NewAccumulator returns a initialized accumulator. To enable the generating proofs for all elements, set Full to true.

func RestorePollardFrom 

func RestorePollardFrom(r io.Reader) (int64, *Pollard, error)

RestorePollardFrom restores the pollard from the reader.

func (*Pollard) AllSubTreesToString 

func (p *Pollard) AllSubTreesToString() string

AllSubTreesToString is a wrapper around utreexo.AllSubTreesToString(). Returns a string representation of each of the subtrees in the pollard that's less than 6 rows tall.

func (*Pollard) GetHash 

func (p *Pollard) GetHash(pos uint64) Hash

GetHash returns the hash for the given position. Empty hash (all values are 0) is returned if the given position does not exist.

func (*Pollard) GetLeafPosition 

func (p *Pollard) GetLeafPosition(hash Hash) (uint64, bool)

GetLeafPosition returns the position of the leaf for the given hash. Returns false if the hash is not the hash of a leaf or if the hash wasn't found in the accumulator.

func (*Pollard) GetNumLeaves 

func (p *Pollard) GetNumLeaves() uint64

GetNumLeaves returns the total number of leaves added to the accumulator.

func (*Pollard) GetRoots 

func (p *Pollard) GetRoots() []Hash

GetRoots returns the hashes of all the roots.

func (*Pollard) GetTotalCount 

func (p *Pollard) GetTotalCount() int64

GetTotalCount returns the count of all the polNodes in the pollard.

func (*Pollard) GetTreeRows 

func (p *Pollard) GetTreeRows() uint8

GetTreeRows returns the total number of rows the accumulator has allocated for.

func (*Pollard) Modify 

func (p *Pollard) Modify(adds []Leaf, delHashes []Hash, proof Proof) error

Modify takes in the additions and deletions and updates the accumulator accordingly.

NOTE Modify does NOT do any validation and assumes that all the positions of the leaves being deleted have already been verified.

func (*Pollard) Prove 

func (p *Pollard) Prove(hashes []Hash) (Proof, error)

func (*Pollard) SerializeSize 

func (p *Pollard) SerializeSize() int

SerializeSize returns how many bytes it'd take to serialize the pollard.

func (*Pollard) String 

func (p *Pollard) String() string

String is a wrapper around utreexo.String(). Returns a string representation of the pollard that's less than 6 rows tall.

func (*Pollard) Undo 

func (p *Pollard) Undo(numAdds uint64, proof Proof, delHashes []Hash, prevRoots []Hash) error

Undo reverts the most recent modify that happened to the accumulator. The passed in numAdds, dels and delHashes should correspond to block being un-done. prevRoots should be of the block that the caller is trying to go back to.

Ex: If the caller is trying to go back to block 9, the numAdds, dels, and delHashes should be the adds and dels that happened to get to block 10. prevRoots should be the roots at block 9.

func (*Pollard) Verify 

func (p *Pollard) Verify(delHashes []Hash, proof Proof, remember bool) error

Verify calculates the root hashes from the passed in proof and delHashes and compares it against the current roots in the pollard.

func (*Pollard) WriteTo 

func (p *Pollard) WriteTo(w io.Writer) (int64, error)

Write to writes all the data of the pollard to the writer.

type Proof 

type Proof struct {
	// Targets are the ist of leaf locations to delete and they are the bottommost leaves.
	// With the tree below, the Targets can only consist of one of these: 02, 03, 04.
	//
	// 06
	// |-------\
	// 04      05
	// |---\   |---\
	//         02  03
	Targets []uint64

	// All the nodes in the tree that are needed to hash up to the root of
	// the tree. Here, the root is 06. If Targets are [00, 01], then Proof
	// would be [05] as you need 04 and 05 to hash to 06. 04 can be calculated
	// by hashing 00 and 01.
	//
	// 06
	// |-------\
	// 04      05
	// |---\   |---\
	// 00  01  02  03
	Proof []Hash
}

Proof is the inclusion-proof for multiple leaves.

func (*Proof) String 

func (p *Proof) String() string

String returns a string of the proof. Useful for debugging.

func (*Proof) Undo 

func (p *Proof) Undo(numAdds, numLeaves uint64, dels []uint64,
	delHashes, cachedHashes []Hash, toDestroy []uint64, proof Proof) ([]Hash, error)

Undo reverts the proof back to the previous state before the Update.

NOTE Undo does NOT re-cache the already deleted leaves that were previously cached. Those must be added back to the cached proof separately.

func (*Proof) Update 

func (p *Proof) Update(
	cachedHashes, addHashes []Hash, blockTargets []uint64, remembers []uint32, updateData UpdateData) ([]Hash, error)

Update updates the proof with the given data.

type Stump 

type Stump struct {
	// Roots are the state of the accumulator.
	Roots []Hash
	//  NumLeaves is how many leaves the accumulator has allocated for.
	NumLeaves uint64
}

Stump is bare-minimum data required to validate and update changes in the accumulator. Stump is client-side only and cannot generate proofs on its own. It can only validate them.

func (*Stump) String 

func (s *Stump) String() string

String returns the fields of stump in a human readable string.

func (*Stump) Update 

func (s *Stump) Update(delHashes, addHashes []Hash, proof Proof) (UpdateData, error)

Update verifies the proof and updates the Stump with the additions and the deletions. The returned update data can be used to update a cached proof.

type ToString 

type ToString interface {
	GetRoots() []Hash
	GetNumLeaves() uint64
	GetTreeRows() uint8
	GetHash(uint64) Hash
}

ToString is an interface that different Utreexo implementations have to meet inorder for it to use the string functionality.

type UpdateData 

type UpdateData struct {
	// ToDestroy is the positions of the empty roots removed after the add.
	ToDestroy []uint64
	// PrevNumLeaves is the numLeaves of the stump before the add.
	PrevNumLeaves uint64

	// NewDelHash are the new hashes after the deletion.
	NewDelHash []Hash
	// NewDelPos are the original positions of the new hashes.
	NewDelPos []uint64

	// NewAddHash are the new hashes for the newly created roots after the addition.
	NewAddHash []Hash
	// NewAddPos are the positions of the new hashes.
	NewAddPos []uint64
}

UpdateData is all the data needed from the stump to update a cached proof.

type Utreexo 

type Utreexo interface {
	// Modify subtracts then adds elements to the accumulator. The deletions are done in batches
	// so if.
	Modify(adds []Leaf, delHashes []Hash, proof Proof) error

	// Prove returns a proof of the given hashes.
	Prove(delHashes []Hash) (Proof, error)

	// Verify returns an error if the given hashes and proof hash up to a different root than
	// the one the accumulator has.  Remember flag of true will tell the accumulator to cache
	// the proof if it is valid.
	Verify(delHashes []Hash, proof Proof, remember bool) error

	// Undo reverts a modification done by Modify.
	Undo(numAdds uint64, proof Proof, delHashes, prevRoots []Hash) error

	// GetRoots returns the current roots of the accumulator.
	GetRoots() []Hash

	// GetHash returns the hash at the given position. Returns an empty hash if the position either
	// doesn't exist or if the position is not cached.
	GetHash(position uint64) Hash

	// GetLeafPosition returns the position for the given leaf hash. The boolean returns false if the
	// hash wasn't found.
	//
	// NOTE It always returns false for any non-leaf hashes.
	GetLeafPosition(Hash) (uint64, bool)

	// GetNumLeaves returns the number of total additions the accumulator has ever had.
	GetNumLeaves() uint64

	// GetTreeRows returns the current tree rows the accumulator has allocated for.
	GetTreeRows() uint8

	// String returns a string representation of the accumulator only if the result of GetTreeRows
	// is less than 7. Will return the hash of roots instead if the accumulator is too tall.
	String() string
}

Utreexo defines the interface that all consensus abiding Utreexo implementations should have.

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.