accumulator

package
v0.0.0-...-6ac58e8 Latest Latest
Warning

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

 Go to latest Published: Apr 18, 2022 License: MIT Imports: 19 Imported by: 3

README

A dynamic hash-based accumulator.

Overview

Package accumulator provides a general purpose dynamic accumulator. There are two main structs: Forest and Pollard.

The Forest contains the entire utreexo accumulator (all the nodes in the forest), and can be used to produce inclusion-proofs for Pollards to verify. Pollard contains a partially populated accumulator and can verify inclusion-proofs from the Forest. A Pollard can contain the entire accumulator. A Forest must contain everything.

Installation

To install, just run the below command. Then the package will be ready to be linked in your Go code.

go get github.com/mit-dci/utreexo/accumulator

Usage

To initialize a pollard or forest:

	// inits a Forest in memory. Refer to the documentation for NewForest() for an in-detail explanation
        // of all the different forest types.
	forest := accumulator.NewForest(RamForest, nil, "", 0)

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

To add/delete elements from the set:

	// Adds and Deletes leaves from the Forest
        // undoBlock is the data needed to revert the Modify. You can ignore it there's no
        // need to support rollbacks.
	undoBlock, err := forest.Modify(leavesToAdd, leavesToDelete)

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

To create an inclusion-proof (only forest is able to do this):

        // leavesToProve is a slice of leaves. To prove just one element, just have a slice with a single
        // element. ex: [ 1 ].
	proof, err := forest.ProveBatch(leavesToProve)

To verify the inclusion-proof (only implemented for pollard):

        // IngestBatchProof() first verifies the proof and returns an error if the proof is invalid.
        // It then readies the pollard for Modify() by populating the pollard which the proofs.
	err := pollard.IngestBatchProof(proof)

Documentation

You can read package documentation here.

IRC

We're on irc.libera.chat #utreexo.

Documentation

Index

Constants

View Source 
const (
	ErrorNotEnoughTrees uint32 = iota
	ErrorNoPollardNode
)

Variables

View Source 
var (
	ErrorCorruptManifest = errors.New("Manifest is corrupted. Recovery needed")
)
View Source 
var ErrorStrings = map[uint32]error{
	ErrorNotEnoughTrees: fmt.Errorf("ErrorNotEnoughTrees"),
	ErrorNoPollardNode:  fmt.Errorf("ErrorNoPollardNode"),
}

Functions

func ProofPositions 

func ProofPositions(
	targets []uint64, numLeaves uint64, forestRows uint8, proofPositions *[]uint64) int64

ProofPositions returns the positions that are needed to prove that the targets exist.

Types

type BatchProof 

type BatchProof struct {
	// Targets are the ist of leaf locations to delete. These are the bottommost leaves.
	// With the tree below, the Targets can only consist of one of these: 00, 01, 02, 03
	//
	// 06
	// |-------\
	// 04      05
	// |---\   |---\
	// 00  01  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
}

BatchProof is the inclusion-proof for multiple leaves.

func DeserializeBPFromBytes 

func DeserializeBPFromBytes(serialized []byte) (*BatchProof, error)

DeserializeBPFromBytes, given serialized bytes, returns a pointer to the deserialized batchproof. The deserialization is the same as Deserialize() method on BatchProof

func (*BatchProof) Deserialize 

func (bp *BatchProof) Deserialize(r io.Reader) (err error)

Deserialize gives a BatchProof back from a reader.

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

func (bp *BatchProof) Serialize(w io.Writer) (err error)

Serialize serializes a batchproof to a writer.

func (*BatchProof) SerializeBytes 

func (bp *BatchProof) SerializeBytes() ([]byte, error)

SerializeBytes serializes and returns the batchproof as raw bytes the serialization is the same as Serialize() method

func (*BatchProof) SerializeSize 

func (bp *BatchProof) SerializeSize() int

SerializeSize returns the number of bytes it would take to serialize the BatchProof.

func (*BatchProof) ToString 

func (bp *BatchProof) ToString() string

ToString for debugging, shows the blockproof

type Forest 

type Forest struct {
	// 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(forestType ForestType, forestFile *os.File, cowPath string, cowMaxCache int) *Forest

NewForest initializes a Forest and returns it. The given arguments determine what type of forest it will be.

func RestoreForest 

func RestoreForest(
	miscForestFile *os.File, forestFile *os.File,
	toRAM, cached bool, cow string, cowMaxCache int) (*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) AssertEqual 

func (f *Forest) AssertEqual(compareForest *Forest) error

AssertEqual compares the two forests. Returns an error if the forests are not equal. The data meant for statics are not checked and the function will return true if all other fields are equal.

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

func (f *Forest) GetRoots() []Hash

GetRoots returns all the roots of all the trees in the accumulator.

func (*Forest) Modify 

func (f *Forest) Modify(adds []Leaf, delsUn []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) PosMapSanity 

func (f *Forest) PosMapSanity() error

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

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: The order in which the hashes are given matter when verifying (aka permutation matters).

func (*Forest) ProveMany 

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

ProveMany :

func (*Forest) Stats 

func (f *Forest) Stats() string

Stats returns the current forest statics as a string. This includes number of total leaves, historic hashes, length of the position map, and the size of the forest

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 reverts a Modify() with the given 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(toProve []Hash, bp BatchProof) error

VerifyBatchProof is just a wrapper around 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, ram, cow bool) 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 ForestType 

type ForestType int

ForestType defines the 4 type of forests: DiskForest, RamForest, CacheForest, CowForest 

const (
	// DiskForest  - keeps the entire forest on disk as a flat file. Is the slowest
	//               of them all. Pass an os.File as forestFile to create a DiskForest.
	DiskForest ForestType = iota
	// RamForest   - keeps the entire forest on ram as a slice. Is the fastest but
	//               takes up a lot of ram. Is compatible with DiskForest (as in you
	//               can restart as RamForest even if you created a DiskForest. Pass
	//               nil, as the forestFile to create a RamForest.
	RamForest
	// CacheForest - keeps the entire forest on disk but caches recent nodes. It's
	//               faster than disk. Is compatible with the above two forest types.
	//               Pass cached = true to create a cacheForest.
	CacheForest
	// CowForest   - A copy-on-write (really a redirect on write) forest. It strikes
	//               a balance between ram usage and speed. Not compatible with other
	//               forest types though (meaning there isn't functionality implemented
	//               to convert a CowForest to DiskForest and vise-versa). Pass a filepath
	//               and cowMaxCache(how much MB to use in ram) to create a CowForest.
	CowForest
)

type Hash 

type Hash [32]byte

Hash is the 32 bytes of a sha256 hash

func HashFromString 

func HashFromString(s string) Hash

HashFromString takes a string and hashes with sha256

func (Hash) Mini 

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

Mini takes the first 12 slices of a hash and outputs a MiniHash

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 is the first 12 bytes of a sha256 hash

type Pollard 

type Pollard struct {

	// Lookahead is the threshold that sets which leaves should be cached.
	// TODO not currently implemented yet.
	Lookahead int32
	// contains filtered or unexported fields
}

Pollard is the sparse representation of the utreexo forest, represented as a collection of binary trees.

func NewFullPollard 

func NewFullPollard() Pollard

NewFullPollard gives you a Pollard with an activated

func (*Pollard) Deserialize 

func (p *Pollard) Deserialize(serialized []byte) error

Deserialize decodes the bytes into a Pollard

func (*Pollard) GetRoots 

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

GetRoots returns the hashes of the pollard roots

func (*Pollard) GetTotalCount 

func (p *Pollard) GetTotalCount() int64

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

func (*Pollard) IngestBatchProof 

func (p *Pollard) IngestBatchProof(toProve []Hash, bp BatchProof, rememberAll bool) error

IngestBatchProof populates the Pollard with all needed data to delete the targets in the block proof. If rememberAll is true, pollard will mark all the proofs given in the batchproof to be remembered.

NOTE: The order in which the hashes are given matter (aka permutation matters). The hashes being verified should be in the same order as they were proven.

func (*Pollard) Modify 

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

Modify deletes then adds elements to the accumulator.

func (*Pollard) NumLeaves 

func (p *Pollard) NumLeaves() uint64

NumLeaves returns the number of leaves that the accumulator has.

func (*Pollard) PosMapSanity 

func (p *Pollard) PosMapSanity() error

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

func (*Pollard) PrintRemembers 

func (p *Pollard) PrintRemembers() (string, error)

PrintRemembers prints all the nodes and their remember status. Useful for debugging.

func (*Pollard) ProveBatch 

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

ProveBatch but for pollard.

NOTE: The order in which the hashes are given matter when verifying (aka permutation matters).

func (*Pollard) PruneAll 

func (p *Pollard) PruneAll()

PruneAll prunes the accumulator down to the roots.

func (*Pollard) ReconstructStats 

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

ReconstructStats returns numleaves and row so that batch proofs can be reconstructed and hashes can be matches.

TODO 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

RestorePollard restores the pollard from the given reader

func (*Pollard) Serialize 

func (p *Pollard) Serialize() ([]byte, error)

Serialize serializes the numLeaves field and only the roots into a byte slice. Cached leaves are not included in the byte slice

func (*Pollard) Stats 

func (p *Pollard) Stats() string

Stats returns the current pollard statistics as a string.

func (*Pollard) ToString 

func (p *Pollard) ToString() string

ToString returns a string visualization of the Pollard that can be printed

func (*Pollard) VerifyBatchProof 

func (p *Pollard) VerifyBatchProof(toProve []Hash, bp BatchProof) error

VerifyBatchProof verifies the hash and the proof passed in. It does not make any modifications to the pollard.

NOTE: The order in which the hashes are given matter (aka permutation matters). The hashes being verified should be in the same order as they were proven.

func (*Pollard) WritePollard 

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

WritePollard writes the numLeaves field and only the roots into the given writer. Cached leaves are not included in the writer

type PositionList 

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

PositionList is a wrapper around slice of ints.

func NewPositionList 

func NewPositionList() *PositionList

NewPositionList returns a slice of uint64 from the pool

func (*PositionList) Free 

func (pl *PositionList) Free()

Free returns the slice of uint64 back to the pool

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 UndoBlock 

type UndoBlock struct {
	Height int32 // height of block
	// contains filtered or unexported fields
}

blockUndo is all the data needed to undo a block: number of adds, and all the hashes that got deleted and where they were from

func (*UndoBlock) Deserialize 

func (u *UndoBlock) Deserialize(r io.Reader) error

Deserialize decodes an undoblock from the reader.

func (*UndoBlock) Serialize 

func (u *UndoBlock) Serialize(w io.Writer) error

Serialize encodes the undoblock into the given writer.

func (*UndoBlock) SerializeSize 

func (u *UndoBlock) SerializeSize() int

SerializeSize returns how many bytes it would take to serialize this undoblock.

func (*UndoBlock) ToString 

func (u *UndoBlock) ToString() string

ToString returns a string

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.