accumulator

package
v0.0.0-...-77c8a84 Latest Latest
Warning

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

 Go to latest Published: Aug 29, 2020 License: MIT Imports: 10 Imported by: 0

README

the utreexo library

overview

There are two main structs that do all the work: Forest and Pollard. The Forest contains the entire utreexo accumulator structure and all data in it, and can be used to produce proofs and perform bridge node functions. Pollard contains a partially populated accumulator and can verify proofs from the Forest (and should be able to produce some of its own). A Pollard can contain the entire accumulator, but a Forest will be more efficient at doing so. A Forest must contain everything.

flow

Forest can be initialized and then have Modify() called repeatedly with hashes to add and positions to delete. If you need to remember the positions of the things to delete based on their hashes, ProveBlock() will provide that data.

The general flow for pollards will be as in pollard_test.go. A block proof is received by the pollard node, and IngestBlockProof() is called. This populates the Pollard with data needed to remove everything that has been proved. Then Modify() is called, with a list of things to delete and things to add. (This two step process could be merged into 1 function call, and would be a bunch faster / more efficient, but for now it's 2 separate functions)

Documentation

Overview

This package contains the tree structure used in the Utreexo accumulator library It is meant to be coin agnostic. Bitcoin specific code can be found in 'cmd/'.

The basic flow for using the accumulator package goes as such:

  1. Initialize Forest or Pollard. // inits a Forest in memory // pass a file in to init a forest on disk forest := accumulator.NewForest(nil)

    // declare pollard. No init function for pollard var pollard accumulator.Pollard

  1. Call the Modify() methods for each one. // Adds and Deletes leaves from the Forest forest.Modify(leavesToAdd, leavesToDelete)

    // Adds and Deletes leaves from the Pollard pollard.Modify(leavesToAdd, leavesToDelete)

Thats it!

To add transaction verification, existence of the transaction needs to be checked before to make sure the transaction exists. With Forest, this is done with FindLeaf() which is a wrapper around Golang maps. This is ok since Forest is aware of every tx in existence.

With Pollard, VerifyBatchProof() method needs to be called to check for tree tops. If it verifies, this means that the transaction(s) that was sent over exists.

Accumulator in detail:

Jargon: In parts of the forest code you'll see these terminology being used. 

Perfect tree - A tree with 2**x leaves. All trees in Utreexo
are perfect.
Root - The top most parts of the tree. A Utreexo tree may have
more than 1 top unlike a Merkle tree.
Parent - The hash of two leaves concatenated.
Sibling - The other leaf that shares the same parent.
Aunt - The sibling of the parent leaf.
Cousin - The children of the parent leaf's sibling.

Forest is a representation of a "full" Utreexo tree. The Forest implementation would be the Utreexo bridge node. "Full" means that all the hashes of the tree is stored.

This is done as either:

  1. byte slice
  2. contiguous data in a file

The ordering of the Utreexo tree is done in a similar fashion to that of a 2x2 array in row-major order. A Utreexo tree with 8 leaves would look like: 

06
|-------\
04......05
|---\...|---\
00..01..02..03

In the byte slice, this would be represented as such: 

byte[]{00, 01, 02, 03, 04, 05, 06}

It would be saved in the same fashion in the file.

For perfect trees, this is simple. However, for trees that aren't perfect, this is a little different.

If one leaf gets added to the above tree, a new 8 leave tree is initialized by Remap(). The new tree looks like such. 

em
|---------------\
12..............em
|-------\.......|-------\
08......09......em......em
|---\...|---\...|---\...|---\
00..01..02..03..04..em..em..em

em stands for empty and the leaf is initialized to either:

  1. uint64 of 0s for RAM
  2. whatever data there was on disk for on disk

The em leaves still have positions but just hold values of 0s.

Remap() is never called for when a leaf is deleted. For example, the forest will hold an empty tree when leaf 04 is deleted in the above tree. It will look like below: 

em
|---------------\
12..............em
|-------\.......|-------\
08......09......em......em
|---\...|---\...|---\...|---\
00..01..02..03..em..em..em..em

This is not a bug and is done on purpose for efficiency reasons. If a tree is adding and deleting between a leaf number of 2**x, it will cause an io bottleneck as the tree on the right is constantly deleted and re-initialized.

This will sometimes cause the Forest to have a total row value that is 1 greater than it actually is.

Pollard:

Pollard is a representation of a "sparse" Utreexo tree. "Sparse" means that not all leaves are stored. The above tree with 8 leaves may look like such. 

14
|---------------\
**..............**
|-------\.......|-------\
**......**......**......**
|---\...|---\...|---\...|---\
**..**..**..**..**..**..**..**

Some leaves may be saved for caching purposes but they do not have to be.

Pollard uses binary tree pointers instead of a byte slice. Each hash is of type PolNode. In a tree below, each number would represent a PolNode. 

14
|---------------\
12..............13
|-------\.......|-------\
08......09......10......11
|---\...|---\...|---\...|---\
00..01..02..03..04..05..06..07

Unlike traditional binary trees, the parent does NOT point to its children. It points to its nieces.

Number 08 PolNode would point to leaves 02 and 03. 12 Polnode would point to 10 and 11. This is done for efficiency reasons as Utreexo Pollard uses the Aunt to verify whether a leaf exists or not. Parents can be computed from its children but an Aunt needs to be provided.

For example, with a tree like below, to prove the inclusion of 03, the prover needs to provide 02, 03, 08, 13. 

14
|---------------\
12..............13
|-------\.......|-------\
08......09......10......11
|---\...|---\...|---\...|---\
00..01..02..03..04..05..06..07

A Pollard node is not aware of each individual PolNode's position in the tree. This is different from Forest, as Forest is aware of every single leaf and its position. Getting the position of the Polnode is done through grabPos()/descendToPos() methods.

Index

Constants

View Source 
const (
	ErrorNotEnoughTrees uint32 = iota
	ErrorNoPollardNode
)

Variables

View Source 
var ErrorStrings = map[uint32]error{
	ErrorNotEnoughTrees: fmt.Errorf("ErrorNotEnoughTrees"),
	ErrorNoPollardNode:  fmt.Errorf("ErrorNoPollardNode"),
}

Functions

func BinString 

func BinString(leaves uint64) string

BinString prints out the whole thing. Only viable for small forests

Types

type BatchProof 

type BatchProof struct {
	Targets []uint64
	Proof   []Hash
}

BatchProof :

func FromBytesBatchProof 

func FromBytesBatchProof(b []byte) (BatchProof, error)

FromBytesBatchProof gives a block proof back from the serialized bytes

func (*BatchProof) Reconstruct 

func (bp *BatchProof) Reconstruct(
	numleaves uint64, forestRows uint8) (map[uint64]Hash, error)

Reconstruct takes a number of leaves and rows, and turns a block proof back into a partial proof tree. Should leave bp intact

func (*BatchProof) SortTargets 

func (bp *BatchProof) SortTargets()

ToString for debugging, shows the blockproof

func (*BatchProof) ToBytes 

func (bp *BatchProof) ToBytes() []byte

ToBytes give the bytes for a BatchProof. It errors out silently because I don't think the binary.Write errors ever actually happen

func (*BatchProof) ToString 

func (bp *BatchProof) ToString() string

ToString for debugging, shows the blockproof

type Forest 

type Forest struct {

	// HistoricHashes represents how many hashes this forest has computed
	//
	// Meant for testing / benchmarking
	HistoricHashes uint64

	// TimeRem represents how long Remove() function took
	//
	// Meant for testing / benchmarking
	TimeRem time.Duration

	// TimeMST represents how long the moveSubTree() function took
	//
	// Meant for testing / benchmarking
	TimeMST time.Duration

	// TimeInHash represents how long the hash operations (reHash) took
	//
	// Meant for testing / benchmarking
	TimeInHash time.Duration

	// TimeInProve represents how long the Prove operations took
	//
	// Meant for testing / benchmarking
	TimeInProve time.Duration

	// TimeInVerify represents how long the verify operations took
	//
	// Meant for testing / benchmarking
	TimeInVerify time.Duration
	// contains filtered or unexported fields
}

Forest is the entire accumulator of the UTXO set as either a: 1) slice if the forest is stored in memory. 2) single file if the forest is stored in disk. A leaf represents a UTXO with additional data for verification. This leaf is numbered from bottom left to right. Example of a forest with 4 numLeaves: 

06
|------\
04......05
|---\...|---\
00..01..02..03

04 is the concatenation and the hash of 00 and 01. 06 is the root This tree would have a row of 2.

func NewForest 

func NewForest(forestFile *os.File, cached bool) *Forest

NewForest : use ram if not given a file

func RestoreForest 

func RestoreForest(
	miscForestFile *os.File, forestFile *os.File, toRAM, cached bool) (*Forest, error)

RestoreForest restores the forest on restart. Needed when resuming after exiting. miscForestFile is where numLeaves and rows is stored

func (*Forest) Add 

func (f *Forest) Add(adds []Leaf)

Add adds leaves to the forest. This is the easy part.

func (*Forest) BuildUndoData 

func (f *Forest) BuildUndoData(numadds uint64, dels []uint64) *undoBlock

BuildUndoData makes an undoBlock from the same data that you'd give to Modify

func (*Forest) FindLeaf 

func (f *Forest) FindLeaf(leaf Hash) bool

FindLeaf finds a leave from the positionMap and returns a bool

func (*Forest) Modify 

func (f *Forest) Modify(adds []Leaf, dels []uint64) (*undoBlock, error)

Modify changes the forest, adding and deleting leaves and updating internal nodes. Note that this does not modify in place! All deletes occur simultaneous with adds, which show up on the right. Also, the deletes need there to be correct proof data, so you should first call Verify().

func (*Forest) PrintPositionMap 

func (f *Forest) PrintPositionMap() string

func (*Forest) Prove 

func (f *Forest) Prove(wanted Hash) (Proof, error)

Prove :

func (*Forest) ProveBatch 

func (f *Forest) ProveBatch(hs []Hash) (BatchProof, error)

ProveBatch gets proofs (in the form of a node slice) for a bunch of leaves The ordering of Targets is the same as the ordering of hashes given as argument. NOTE However targets will need to be sorted before using the proof! TODO the elements to be proven should not be included in the proof.

func (*Forest) ProveMany 

func (f *Forest) ProveMany(hs []Hash) ([]Proof, error)

ProveMany :

func (*Forest) ReconstructStats 

func (f *Forest) ReconstructStats() (uint64, uint8)

TODO remove, only here for testing

func (*Forest) Stats 

func (f *Forest) Stats() string

Stats :

func (*Forest) ToString 

func (f *Forest) ToString() string

ToString prints out the whole thing. Only viable for small forests

func (*Forest) Undo 

func (f *Forest) Undo(ub undoBlock) error

Undo : undoes one block with the undoBlock

func (*Forest) Verify 

func (f *Forest) Verify(p Proof) bool

Verify checks an inclusion proof. returns false on any errors

func (*Forest) VerifyBatchProof 

func (f *Forest) VerifyBatchProof(bp BatchProof) bool

VerifyBatchProof :

func (*Forest) VerifyMany 

func (f *Forest) VerifyMany(ps []Proof) bool

VerifyMany is like verify but more.

func (*Forest) WriteForestToDisk 

func (f *Forest) WriteForestToDisk(dumpFile *os.File) error

WriteForestToDisk writes the whole forest to disk this only makes sense to do if the forest is in ram. So it'll return an error if it's not a ramForestData

func (*Forest) WriteMiscData 

func (f *Forest) WriteMiscData(miscForestFile *os.File) error

WriteMiscData writes the numLeaves and rows to miscForestFile

type ForestData 

type ForestData interface {
	// contains filtered or unexported methods
}

ForestData is the thing that holds all the hashes in the forest. Could be in a file, or in ram, or maybe something else.

type Hash 

type Hash [32]byte

Hash :

func HashFromString 

func HashFromString(s string) Hash

HashFromString :

func (Hash) Mini 

func (h Hash) Mini() (m MiniHash)

Mini :

func (Hash) Prefix 

func (h Hash) Prefix() []byte

Prefix for printfs

type Leaf 

type Leaf struct {
	Hash
	Remember bool // this leaf will be deleted soon, remember it
}

Leaf contains a hash and a hint about whether it should be saved to memory or not during ibdsim.

type MiniHash 

type MiniHash [12]byte

MiniHash :

type PatriciaLookup 

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

type PatriciaNode 

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

type Pollard 

type Pollard struct {
	Lookahead int32 // remember leafs below this TTL
	// contains filtered or unexported fields
}

Pollard :

func NewFullPollard 

func NewFullPollard() Pollard

NewFullPollard gives you a Pollard with an activated

func (*Pollard) IngestBatchProof 

func (p *Pollard) IngestBatchProof(bp BatchProof) error

IngestBatchProof populates the Pollard with all needed data to delete the targets in the block proof

func (*Pollard) Modify 

func (p *Pollard) Modify(adds []Leaf, dels []uint64) error

Modify is the main function that deletes then adds elements to the accumulator

func (*Pollard) PosMapSanity 

func (p *Pollard) PosMapSanity() error

PosMapSanity is costly / slow: check that everything in posMap is correct

func (*Pollard) ProveBatch 

func (p *Pollard) ProveBatch(hs []Hash) (BatchProof, error)

ProveBatch but for pollard. Now getting really obvious that forest and pollard should both satisfy some kind of utreexo-like interface. And maybe forest shouldn't be called forest. Anyway do that after this.

func (*Pollard) ReconstructStats 

func (p *Pollard) ReconstructStats() (uint64, uint8)

TODO remove Temporary -- returns numleaves and row so that batch proofs can be reconstructed and hashes can be matches. Replace this with proofs that do not include the things being proven, and take the proved leaves as a separate argument

func (*Pollard) RestorePollard 

func (p *Pollard) RestorePollard(r io.Reader) error

func (*Pollard) Stats 

func (p *Pollard) Stats() string

Stats :

func (*Pollard) ToString 

func (p *Pollard) ToString() string

func (*Pollard) WritePollard 

func (p *Pollard) WritePollard(w io.Writer) error

type Proof 

type Proof struct {
	Position uint64 // where at the bottom of the tree it sits
	Payload  Hash   // hash of the thing itself (what's getting proved)
	Siblings []Hash // slice of siblings up to a root
}

Proof :

type SimChain 

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

SimChain is for testing; it spits out "blocks" of adds and deletes

func NewSimChain 

func NewSimChain(duration uint32) *SimChain

NewSimChain :

func (*SimChain) BackOne 

func (s *SimChain) BackOne(leaves []Leaf, durations []int32, dels []Hash)

BackOne takes the output of NextBlock and undoes the block

func (*SimChain) NextBlock 

func (s *SimChain) NextBlock(numAdds uint32) ([]Leaf, []int32, []Hash)

NextBlock :

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.