accumulator

package
v0.0.0-...-50d4516 Latest Latest
Warning

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

 Go to latest Published: Jan 9, 2025 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DeletionTrace 

type DeletionTrace[K, V io.WriterTo] struct {
	// Identifier for the tree this trace relates to
	Type     int    `json:"type"`
	Location string `json:"location"`

	// For consistency, we call it new next free node but
	// the value is not updated during a deletion
	NewNextFreeNode int     `json:"newNextFreeNode"`
	OldSubRoot      Bytes32 `json:"oldSubRoot"`
	NewSubRoot      Bytes32 `json:"newSubRoot"`

	// `New` correspond to the inserted leaf
	ProofMinus   smt.Proof `json:"leftProof"`
	ProofDeleted smt.Proof `json:"deletedProof"`
	ProofPlus    smt.Proof `json:"rightProof"`
	Key          K         `json:"key"`

	// Value of the leaf opening before being modified
	OldOpenMinus LeafOpening `json:"priorLeftLeaf"`
	DeletedOpen  LeafOpening `json:"priorDeletedLeaf"`
	OldOpenPlus  LeafOpening `json:"priorRightLeaf"`

	// The deleted value
	DeletedValue V `json:"deletedValue"`
}

DeletetionTrace gathers all the data necessary to audit the deletion of a key in the map.

func (DeletionTrace[K, V]) DeferMerkleChecks 

func (trace DeletionTrace[K, V]) DeferMerkleChecks(
	config *smt.Config,
	appendTo []smt.ProvedClaim,
) []smt.ProvedClaim

DeferMerkleChecks implements Trace

func (DeletionTrace[K, V]) HKey 

func (trace DeletionTrace[K, V]) HKey(_ *smt.Config) Bytes32

func (DeletionTrace[K, V]) RWInt 

func (trace DeletionTrace[K, V]) RWInt() int

type InsertionTrace 

type InsertionTrace[K, V io.WriterTo] struct {
	// Identifier for the tree this trace belongs to
	Type     int    `json:"type"`
	Location string `json:"location"`

	NewNextFreeNode int     `json:"newNextFreeNode"`
	OldSubRoot      Bytes32 `json:"oldSubRoot"`
	NewSubRoot      Bytes32 `json:"newSubRoot"`

	// `New` correspond to the inserted leaf
	ProofMinus smt.Proof `json:"leftProof"`
	ProofNew   smt.Proof `json:"newProof"`
	ProofPlus  smt.Proof `json:"rightProof"`
	Key        K         `json:"key"`
	Val        V         `json:"value"`

	// Value of the leaf opening before being modified
	OldOpenMinus LeafOpening `json:"priorLeftLeaf"`
	OldOpenPlus  LeafOpening `json:"priorRightLeaf"`
}

InsertionTrace gathers all the input needed for a verifier to audit the insertion of a key in the map.

func (InsertionTrace[K, V]) DeferMerkleChecks 

func (trace InsertionTrace[K, V]) DeferMerkleChecks(
	config *smt.Config,
	appendTo []smt.ProvedClaim,
) []smt.ProvedClaim

DeferMerkleChecks implements Trace

func (InsertionTrace[K, V]) HKey 

func (trace InsertionTrace[K, V]) HKey(cfg *smt.Config) Bytes32

func (InsertionTrace[K, V]) RWInt 

func (trace InsertionTrace[K, V]) RWInt() int

type KVOpeningTuple 

type KVOpeningTuple[K, V io.WriterTo] struct {
	LeafOpening LeafOpening
	Key         K
	Value       V
}

KVOpeningTuple is simple a tuple type of (key, value) adding the corresponding leaf opening

func (KVOpeningTuple[K, V]) CheckAndLeaf 

func (t KVOpeningTuple[K, V]) CheckAndLeaf(conf *smt.Config) (Bytes32, error)

CheckAndLeaf check the internal consistency of the tuple and returns the hash of the leaf opening (corresponding to a leaf).

func (KVOpeningTuple[K, V]) CopyWithNext 

func (t KVOpeningTuple[K, V]) CopyWithNext(next int64) KVOpeningTuple[K, V]

CopyWithNext copies the tuple and set the next in the copy

func (KVOpeningTuple[K, V]) CopyWithPrev 

func (t KVOpeningTuple[K, V]) CopyWithPrev(prev int64) KVOpeningTuple[K, V]

CopyWithPrev copies the tuple and set the prev in the copy

func (KVOpeningTuple[K, V]) CopyWithVal 

func (t KVOpeningTuple[K, V]) CopyWithVal(conf *smt.Config, val V) KVOpeningTuple[K, V]

CopyWithVal copies the tuple and give it a new new value

type LeafOpening 

type LeafOpening struct {
	Prev int64   `json:"prevLeaf"`
	Next int64   `json:"nextLeaf"`
	HKey Bytes32 `json:"hkey"` //it is mimc hash of the adress
	HVal Bytes32 `json:"hval"` // is it mimc of account
}

LeafOpening represents the opening of a leaf in the accumulator's tree.

The `json` format and the order of the fields is important 

func Head() LeafOpening

Head returns the "head" of the accumulator set

func Tail 

func Tail(config *smt.Config) LeafOpening

Tail returns the "tail" of the accumulator set

func (LeafOpening) CopyWithNext 

func (leaf LeafOpening) CopyWithNext(next int64) LeafOpening

CopyWithNext copies the leaf opening and set the next in the copy

func (LeafOpening) CopyWithPrev 

func (leaf LeafOpening) CopyWithPrev(prev int64) LeafOpening

CopyWithPrev copies the leaf opening and set the prev in the copy

func (LeafOpening) Hash 

func (leaf LeafOpening) Hash(conf *smt.Config) Bytes32

Hash returns a hash of the leaf opening

func (*LeafOpening) HeadOrTail 

func (leaf *LeafOpening) HeadOrTail(config *smt.Config) bool

HeadOrTail returns true if the leaf opening is either head or tail

func (*LeafOpening) MatchKey 

func (l *LeafOpening) MatchKey(conf *smt.Config, k io.WriterTo) bool

MatchKey returns true if the leaf opening opening matches the value

func (*LeafOpening) MatchValue 

func (l *LeafOpening) MatchValue(conf *smt.Config, v io.WriterTo) bool

MatchValue returns true if the leaf opening opening matches the value

func (LeafOpening) String 

func (l LeafOpening) String() string

String pretty prints a leaf opening

func (*LeafOpening) WriteTo 

func (leaf *LeafOpening) WriteTo(w io.Writer) (int64, error)

WriteTo implements the io.WriterTo interface and is used to hash the leaf opening into the leaves that we store in the tree.

type ProverState 

type ProverState[K, V io.WriterTo] struct {
	// Location, identifier for the tree
	Location string
	// Track the index of the next free node
	NextFreeNode int64
	// Internal tree
	Tree *smt.Tree
	// Keys associated to the leaf #i
	Data collection.Mapping[int64, KVOpeningTuple[K, V]]
}

ProverState holds the state of the accumulator: the tree itself and auxiliary structures to help tracking the positions of the tree.

func InitializeProverState 

func InitializeProverState[K, V io.WriterTo](conf *smt.Config, location string) *ProverState[K, V]

InitializeProverState returns an initialized empty accumulator state

func (*ProverState[K, V]) Config 

func (s *ProverState[K, V]) Config() *smt.Config

Config returns the configuration of the accumulator.

func (*ProverState[K, V]) DeleteAndProve 

func (p *ProverState[K, V]) DeleteAndProve(key K) (trace DeletionTrace[K, V])

DeleteAndProve deletes an entry in the accumulator and returns a DeletionTrace, the function will panic on failure: if the key could not be found or if the Tree is corrupted.

func (*ProverState[K, V]) FindKey 

func (s *ProverState[K, V]) FindKey(k K) (int64, bool)

FindKey finds the position of a key in the accumulator. If the key is absent, it returns 0, false. The returned position corresponds to the position in the tree.

func (*ProverState[K, V]) InsertAndProve 

func (p *ProverState[K, V]) InsertAndProve(key K, val V) (trace InsertionTrace[K, V])

InsertAndProve inserts in the accumulator and returns a trace. The function panics if the key is already in the accumulator or if the tree is corrupted.

func (*ProverState[K, V]) ListAllKeys 

func (s *ProverState[K, V]) ListAllKeys() []K

ListAllKeys is a function used for testing and traces sample generation which never should be called in production code as it is extremely inefficient

func (*ProverState[K, V]) ReadNonZeroAndProve 

func (p *ProverState[K, V]) ReadNonZeroAndProve(key K) ReadNonZeroTrace[K, V]

ReadNonZeroAndProve perform a read on the accumulator and returns a trace. Panics if the the associated key is missing.

func (*ProverState[K, V]) ReadZeroAndProve 

func (p *ProverState[K, V]) ReadZeroAndProve(key K) ReadZeroTrace[K, V]

ReadZeroAndProve performs a read-zero on the accumulator. Panics if the associated key exists in the tree. Returns a ReadZeroTrace object in case of success.

func (*ProverState[K, V]) SubTreeRoot 

func (s *ProverState[K, V]) SubTreeRoot() Bytes32

SubTreeRoot returns the root of the tree

func (*ProverState[K, V]) TopRoot 

func (s *ProverState[K, V]) TopRoot() Bytes32

TopRoot returns the top-root hash which includes `NextFreeNode` and the `SubTreeRoot`

func (*ProverState[K, V]) UpdateAndProve 

func (p *ProverState[K, V]) UpdateAndProve(key K, newVal V) UpdateTrace[K, V]

UpdateAndProve performs a read on the accumulator. Panics if the associated key is missing. Returns an UpdateTrace object in case of success.

func (*ProverState[K, V]) VerifierState 

func (p *ProverState[K, V]) VerifierState() VerifierState[K, V]

VerifierState create a verifier state from a prover state. The returned verifier state corresponds to a snapshot of the prover's state.

type ReadNonZeroTrace 

type ReadNonZeroTrace[K, V io.WriterTo] struct {
	// Identifier for the tree this trace belongs to
	Type         int         `json:"type"`
	Location     string      `json:"location"`
	NextFreeNode int         `json:"nextFreeNode"`
	Key          K           `json:"key"`
	Value        V           `json:"value"`
	SubRoot      Bytes32     `json:"subRoot"`
	LeafOpening  LeafOpening `json:"leaf"`
	Proof        smt.Proof   `json:"proof"`
}

ReadNonZeroTrace contains all the information needed to audit a read-only access to an existing key in the map.

func (ReadNonZeroTrace[K, V]) DeferMerkleChecks 

func (trace ReadNonZeroTrace[K, V]) DeferMerkleChecks(
	config *smt.Config,
	appendTo []smt.ProvedClaim,
) []smt.ProvedClaim

DeferMerkleChecks implements Trace

func (ReadNonZeroTrace[K, V]) HKey 

func (trace ReadNonZeroTrace[K, V]) HKey(cfg *smt.Config) Bytes32

func (ReadNonZeroTrace[K, V]) RWInt 

func (trace ReadNonZeroTrace[K, V]) RWInt() int

type ReadZeroTrace 

type ReadZeroTrace[K, V io.WriterTo] struct {
	Type         int         `json:"type"`
	Location     string      `json:"location"`
	Key          K           `json:"key"`
	SubRoot      Bytes32     `json:"subRoot"`
	NextFreeNode int         `json:"nextFreeNode"`
	OpeningMinus LeafOpening `json:"leftLeaf"`
	OpeningPlus  LeafOpening `json:"rightLeaf"`
	ProofMinus   smt.Proof   `json:"leftProof"`
	ProofPlus    smt.Proof   `json:"rightProof"`
}

Trace that allows checking a read zero operation: e.g. proof of non-membership

func (ReadZeroTrace[K, V]) DeferMerkleChecks 

func (trace ReadZeroTrace[K, V]) DeferMerkleChecks(
	config *smt.Config,
	appendTo []smt.ProvedClaim,
) []smt.ProvedClaim

DeferMerkleChecks implements the Trace interface.

func (ReadZeroTrace[K, V]) HKey 

func (trace ReadZeroTrace[K, V]) HKey(cfg *smt.Config) Bytes32

func (ReadZeroTrace[K, V]) RWInt 

func (trace ReadZeroTrace[K, V]) RWInt() int

type Trace 

type Trace interface {
	// DeferMerkleChecks appends all the merkle-proofs checks happening in a trace
	// verification into a slice of smt.ProvedClaim
	DeferMerkleChecks(config *smt.Config, appendTo []smt.ProvedClaim) []smt.ProvedClaim
	// HKey returns the HKey of the trace
	HKey(cfg *smt.Config) Bytes32
	// RWInt returns 0 is the trace is a read-only operation and 1 if it is a
	// read-write operation.
	RWInt() int
}

Trace is an interface shared by all the "traces" types. Used to collect MerkleProof verifications claims.

type UpdateTrace 

type UpdateTrace[K, V io.WriterTo] struct {
	Type     int    `json:"type"`
	Location string `json:"location"`
	Key      K      `json:"key"`
	OldValue V      `json:"oldValue"`
	NewValue V      `json:"newValue"`
	// We call it new next free node, but the value is not updated
	// during the update.
	NewNextFreeNode int         `json:"newNextFreeNode"`
	OldSubRoot      Bytes32     `json:"oldSubRoot"`
	NewSubRoot      Bytes32     `json:"newSubRoot"`
	OldOpening      LeafOpening `json:"priorUpdatedLeaf"`
	Proof           smt.Proof   `json:"proof"`
}

UpdateTrace contains all the necessary informations to carry an audit of an update of the value of a registered key in the tree.

func (UpdateTrace[K, V]) DeferMerkleChecks 

func (trace UpdateTrace[K, V]) DeferMerkleChecks(
	config *smt.Config,
	appendTo []smt.ProvedClaim,
) []smt.ProvedClaim

DeferMerkleChecks implements the Trace interface.

func (UpdateTrace[K, V]) HKey 

func (trace UpdateTrace[K, V]) HKey(cfg *smt.Config) Bytes32

func (UpdateTrace[K, V]) RWInt 

func (trace UpdateTrace[K, V]) RWInt() int

type VerifierState 

type VerifierState[K, V io.WriterTo] struct {
	// Location, identifier for the tree
	Location string
	// Track the index of the next free node
	NextFreeNode int64
	// Internal tree
	SubTreeRoot Bytes32
	// Config contains the parameters of the tree
	Config *smt.Config
}

Track the informations that are maintained by the verifier

func (*VerifierState[K, V]) ReadNonZeroVerify 

func (v *VerifierState[K, V]) ReadNonZeroVerify(trace ReadNonZeroTrace[K, V]) error

Verify a read on the accumulator. Returns an error if the verification fails.

func (*VerifierState[K, V]) ReadZeroVerify 

func (v *VerifierState[K, V]) ReadZeroVerify(trace ReadZeroTrace[K, V]) error

ReadZeroVerify verifies a ReadZeroTrace and returns an error in case of failure.

func (*VerifierState[K, V]) TopRoot 

func (v *VerifierState[K, V]) TopRoot() Bytes32

TopRoot returns the top-root hash which includes `NextFreeNode` and the `SubTreeRoot`

func (*VerifierState[K, V]) UpdateVerify 

func (v *VerifierState[K, V]) UpdateVerify(trace UpdateTrace[K, V]) error

UpdateVerify verifies an UpdateTrace against the verifier state. Returns an error if the verification fails.

func (*VerifierState[K, V]) VerifyDeletion 

func (v *VerifierState[K, V]) VerifyDeletion(trace DeletionTrace[K, V]) error

VerifyDeletion audits the validity of a DeletionTrace w.r.t. to the VerifierState.

func (*VerifierState[K, V]) VerifyInsertion 

func (v *VerifierState[K, V]) VerifyInsertion(trace InsertionTrace[K, V]) error

VerifyInsertion audit the insertion of an entry in the accumulator w.r.t to the state of the verifier. It returns an error if the verification failed.

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.