column

package
v0.0.0-...-869bcdc Latest Latest
Warning

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

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

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllDownStreamBranches 

func AllDownStreamBranches(node ifaces.Column) []string

Returns all subbranches starting from the current node (including the current node). It counts as a list of unique identifiers for the derivation path.

func DeriveEvaluationPoint 

func DeriveEvaluationPoint(
	h ifaces.Column,
	upstream string,
	cachedXs collection.Mapping[string, field.Element],
	x field.Element,
) (xRes []field.Element)

DeriveEvaluationPoint, given a query at point "x" on the current handle, returns the list of "x" values we should query the "leaves" of the current handle to get an equivalent polynomial query only on "Non-Composites" handles. The result is stored in the map `finalXs` which will only contain the "leaves" derived Xs as opposed to the `cachedXs` which computes all intermediate values.

  • upstreamBranchRepr string : repr of the upstream-branch
  • cachedXs : map reprs of full-branches to already derived evaluation points. Essentially a cache for later uses.
  • x is the 'x' value of the univariate query to evaluate

@alex: we should completely refactor this function. As I am trying to retro- engineer it, None of the name or comment in this function make sense to me.

func DerivedYRepr 

func DerivedYRepr(upstream string, currNode ifaces.Column) string

func GnarkDeriveEvaluationPoint 

func GnarkDeriveEvaluationPoint(
	api frontend.API, h ifaces.Column, upstream string,
	cachedXs collection.Mapping[string, frontend.Variable],
	x frontend.Variable,
) (xRes []frontend.Variable)

GnarkDeriveEvaluationPoint mirrors DeriveEvaluationPoint but in a gnark circuit

func GnarkVerifyYConsistency 

func GnarkVerifyYConsistency(
	api frontend.API, h ifaces.Column, upstream string,
	cachedXs collection.Mapping[string, frontend.Variable],
	finalYs collection.Mapping[string, frontend.Variable],
) (y frontend.Variable)

GnarkVerifyYConsistency does the same as VerifyYConsistency but in a gnark circuit.

func NbLeaves 

func NbLeaves(h ifaces.Column) int

NbLeaves returns the number of underlying Natural columns for `h`. If `h` is neither an [Interleaved] nor derived from an [Interleaved], the function returns 1.

func RootParents 

func RootParents(h ifaces.Column) []ifaces.Column

RootParents returns the underlying base Natural of the current handle. If the provided [Column] `h` is an [Interleaved] or a derivative of an [Interleaved], the function returns the list of all the underlying Natural columns.

func Shift 

func Shift(parent ifaces.Column, offset int) ifaces.Column

Shift constructs a Shifted column. The function performs a few checks and normalization before instantiating the column. If the user provides an offset of zero, the function is a no-op and returns the parent column. Since, the shift is cyclic, the offset is normalized. If the column is already a shift then the function fuses the two shifts into a single one for simplification.

func StackOffsets 

func StackOffsets(h ifaces.Column) int

StackOffset sums all the offsets contained in the handle and return the result

If `h` is an [Interleaved] or derive from an [Interleaved] column, it will expect that the stacked offset of its parent is zero. (i.e, we should always shift an interleave but never interleave a shift. In practice, this does not cause issues as we do not have that in the arithmetization). This restriction is motivated by the fact that the "offset" would not be defined in this situation.

func VerifyYConsistency 

func VerifyYConsistency(
	h ifaces.Column, upstream string,
	cachedXs collection.Mapping[string, field.Element],
	finalYs collection.Mapping[string, field.Element],
) (y field.Element)

VerifyYConsistency verifies that the claimed values for y

  • upstream is a repr of the branch leading to the current node
  • cachedXs is the set of derived Xs computed by `DeriveEvaluationPoint`
  • finalYs is the map of the alleged evaluation for which we check the consistency.

@alex: we should completely refactor this function. As I am trying to retro- engineer it, None of the name or comment in this function make sense to me.

Types

type Natural 

type Natural struct {
	// The ID of the column
	ID ifaces.ColID
	// contains filtered or unexported fields
}

Natural represents a ifaces.Column that has been directly declared in the corresponding github.com/consensys/linea-monorepo/prover/protocol/wizard.CompiledIOP or github.com/consensys/linea-monorepo/prover/protocol/wizard.Builder object. The struct should not be constructed directly and should be constructed from the github.com/consensys/linea-monorepo/prover/protocol/wizard.CompiledIOP

func (Natural) GetColAssignment 

func (n Natural) GetColAssignment(run ifaces.Runtime) ifaces.ColAssignment

GetColAssignment implements ifaces.Column

func (Natural) GetColAssignmentAt 

func (n Natural) GetColAssignmentAt(run ifaces.Runtime, pos int) field.Element

GetColAssignmentAt implements ifaces.Column

func (Natural) GetColAssignmentGnark 

func (n Natural) GetColAssignmentGnark(run ifaces.GnarkRuntime) []frontend.Variable

GetColAssignmentGnark implements ifaces.Column

func (Natural) GetColAssignmentGnarkAt 

func (n Natural) GetColAssignmentGnarkAt(run ifaces.GnarkRuntime, pos int) frontend.Variable

GetColAssignmentGnarkAt implements ifaces.Column

func (Natural) GetColID 

func (n Natural) GetColID() ifaces.ColID

GetColID implements the ifaces.Column interface and returns the string identifier of the column.

func (Natural) IsComposite 

func (n Natural) IsComposite() bool

IsComposite implements ifaces.Column, by definition, it is not a composite thus it shall always return true

func (Natural) MustExists 

func (n Natural) MustExists()

MustExists validates the construction of the natural handle and implements the ifaces.Column interface.

func (Natural) Round 

func (n Natural) Round() int

Round retuns the round of definition of the column. See ifaces.Column as method implements the interface.

func (Natural) Size 

func (n Natural) Size() int

Size returns the size of the column, as required by the ifaces.Column interface.

func (Natural) Status 

func (n Natural) Status() Status

Status returns the status of the column. It is only implemented for Natural and not by the other composite columns.

func (Natural) String 

func (n Natural) String() string

String returns the ID of the column as a string and implements ifaces.Column and github.com/consensys/linea-monorepo/prover/symbolic.Metadata

type Shifted 

type Shifted struct {
	Parent ifaces.Column
	Offset int
}

Shifted represents a column that is obtains by (cyclic)-shifting the parent column by an Offset. This is useful to implement github.com/consensys/linea-monorepo/prover/protocol/query.GlobalConstraint constraints to express the "next" value of a column or the previous value of a column. For instance, say we want enforce that a column is assigned to a Fibonacci sequence: a[i+2] - a[i+1] - a[i] == 0. This can be done using the following constraint: 

var (
	aNextNext = ifaces.ColumnAsVariable(column.Shift(a, 2))
	aNext = ifaces.ColumnAsVariable(column.Shift(a, 1))
	a = ifaces.ColumnAsVariable(a)
)

expr := aNextNext.Sub(aNext).Sub(a)

The user should not directly instantiate the struct and should instead use the constructor Shift

func (Shifted) GetColAssignment 

func (s Shifted) GetColAssignment(run ifaces.Runtime) ifaces.ColAssignment

GetColAssignment implements ifaces.Column. The function resolves the assignment of the parent column and rotates it according to the offset.

func (Shifted) GetColAssignmentAt 

func (s Shifted) GetColAssignmentAt(run ifaces.Runtime, pos int) field.Element

GetColAssignmentAt gets a particular entry of the shifted column. The query is delegated to the underlying column and the requested position is shifted according to the offset. This implements the ifaces.Column interface.

func (Shifted) GetColAssignmentGnark 

func (s Shifted) GetColAssignmentGnark(run ifaces.GnarkRuntime) []frontend.Variable

GetColAssignmentGnark implements ifaces.Column and works like GetColAssignment.

func (Shifted) GetColAssignmentGnarkAt 

func (s Shifted) GetColAssignmentGnarkAt(run ifaces.GnarkRuntime, pos int) frontend.Variable

GetColAssignmentGnarkAt gets the witness from the parent and performs a shift in the gnark circuit setting. The method implements the ifaces.Column interface.

func (Shifted) GetColID 

func (s Shifted) GetColID() ifaces.ColID

GetColID implements the ifaces.Column interface and returns the string identifier of the column. The ColID is obtained as SHIFT_<Offset>_<ParentID>.

func (Shifted) IsComposite 

func (s Shifted) IsComposite() bool

IsComposite implements ifaces.Column, by definition, it is not a composite thus it shall always return true

func (Shifted) MustExists 

func (s Shifted) MustExists()

MustExists validates the construction of the natural handle and implements the ifaces.Column interface.

func (Shifted) Round 

func (s Shifted) Round() int

Round retuns the round of definition of the column. See ifaces.Column as method implements the interface.

func (Shifted) Size 

func (s Shifted) Size() int

Size returns the size of the column, as required by the ifaces.Column interface.

func (Shifted) String 

func (s Shifted) String() string

String returns the ID of the column as a string and implements ifaces.Column and github.com/consensys/linea-monorepo/prover/symbolic.Metadata. It returns the same as [GetColID] but as a string (required by Metadata).

type Status 

type Status int

Status is a tag that we associate to a github.com/consensys/linea-monorepo/prover/protocol/ifaces.Column. The status carries information about the role of the column in protocol: if it is visible by the verifier, whether the column is assigned at compilation-time or at runtime, etc...

The default value of Status is Ignored which denotes a value that is only accessible to the prover and which should not be subjected to compilation.

The status assigned to a column can be modified during the compilation. In principle, the compilation status should ensure that all columns are either Ignored, Proof or VerifyingKey. 

const (
	// Ignored denotes a Status indicating that the column should be ignored by
	// the compiler. The main use-case for this is to indicate that the column
	// has already been compiled-out. This happens when a [Committed] column is
	// compiled with the Vortex compiler as the value is then actually committed.
	// Another case is the splitting compiler, which breaks down a column in
	// several segments: in that case the broken down column is replaced by the
	// segments and the rest of the compilation should operate on the segment
	// and not on the original column anymore. The column is still visible to
	// the prover and should still be assigned.
	Ignored Status = iota + 1
	// Committed marks that a [github.com/consensys/linea-monorepo/prover/protocol/ifaces.Column] is to be sent to the oracle,
	// implicitly this is a request for the following steps of the compiler
	// to ensure that the column will be committed to and constitutes a part
	// of the witness of the protocol.
	Committed
	// Proof indicates that the [github.com/consensys/linea-monorepo/prover/protocol/ifaces.Column] should be sent to the verifier.
	// The fact that a step of the compiler marks a column as Proof is not a
	// definitive guarantee that the column will effectively be sent to the
	// verifier. The best example is self-recursion which converts the Proof
	// columns created by the Vortex compiler as Committed back. What is sent
	// to the prover is what is tagged as a proof at the end of the full
	// compilation process.
	Proof
	// Precomputed indicates that the [github.com/consensys/linea-monorepo/prover/protocol/ifaces.Column] is defined offline during
	// the definition or the compilation phase but should not be visible to the
	// verifier and this is an indication that the column should be committed
	// to. An example of such columns are the q_L, q_R, q_M, q_O, q_PI columns
	// defining a Plonk circuit. These columns are known offline but the
	// verifier only interacts with a commitment (or has oracle-access) to these
	// columns.
	Precomputed
	// PublicInput denotes that the column is part of the public inputs of the
	// protocol. Meaning that this is not part of the proof.
	//
	// Deprecated: we don't really use this to create public inputs.
	PublicInput
	// VerifyingKey indicates the column is defined offline during the definition
	// of the protocol or the compilation and that the column is directly
	// available to the verifier. It is preferable to avoid tagging large
	// columns as VerifyingKey as this increases the load on the verifier.
	VerifyingKey
	// VerifierDefined indicates that the column is a special type of column
	// that does not need to be assigned as it is constructible by the
	// verifier using data which it already has from other ways. For instance, a
	// column that is constructed from the parameters of an evaluation query or
	// a column that is constructed by stitching together random coins that
	// the verifier sampled through other means.
	VerifierDefined
)

func (Status) IsPublic 

func (s Status) IsPublic() bool

IsPublic returns true if the column is visible to the verifier

func (Status) MarshalJSON 

func (t Status) MarshalJSON() ([]byte, error)

MarshalJSON implements [json.Marshaler] directly returning the Itoa of the integer.

func (Status) String 

func (s Status) String() string

String returns a string representation of the status. Useful for logging or for debugging.

func (*Status) UnmarshalJSON 

func (t *Status) UnmarshalJSON(b []byte) error

UnmarshalJSON implements [json.Unmarshaler] and directly reuses ParseInt and performing validation : only 0 and 1 are acceptable values.

type Store 

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

Store registers Natural for structs that can return the infos given a name and it is used by the github.com/consensys/linea-monorepo/prover/protocol/wizard.ProverRuntime and the github.com/consensys/linea-monorepo/prover/protocol/wizard.VerifierRuntime to store the columns. The store keeps tracks of the definition rounds of the columns and offers a handful of methods to resolve all the columns that have a particular status.

func NewStore 

func NewStore() Store

NewStore constructs an empty Store object

func (*Store) AddToRound 

func (s *Store) AddToRound(round int, name ifaces.ColID, size int, status Status) ifaces.Column

AddToRound constructs a Natural, registers it in the Store and returns the column

  • name must not be an empty string
  • round must be provided
  • name must not have been registered already

func (*Store) AllHandleCommittedAt 

func (r *Store) AllHandleCommittedAt(round int) []ifaces.Column

AllHandleCommittedAt returns the list of all the Committed columns so far at a given round. The returned slice is ordered by order of insertion.

func (*Store) AllHandlesAtRound 

func (s *Store) AllHandlesAtRound(round int) []ifaces.Column

Returns all handle stores at a given round

func (*Store) AllHandlesAtRoundUnignored 

func (s *Store) AllHandlesAtRoundUnignored(round int) []ifaces.Column

Returns all handle stores at a given round

func (*Store) AllKeys 

func (r *Store) AllKeys() []ifaces.ColID

Returns the list of all the keys ever. The result is returned in Deterministic order.

func (*Store) AllKeysAt 

func (r *Store) AllKeysAt(round int) []ifaces.ColID

AllKeysAt returns the list of all keys for a given round. The result follows the insertion order of insertion) (=assignment order)

func (*Store) AllKeysCommitted 

func (r *Store) AllKeysCommitted() []ifaces.ColID

AllKeysCommitted returns the list of all the IDs of the all the Committed columns ordered by rounds and then by IDs.

func (*Store) AllKeysCommittedAt 

func (r *Store) AllKeysCommittedAt(round int) []ifaces.ColID

Returns the list of all the ifaces.ColID tagged with the Committed status so far at a given round. The order of the returned slice follows the insertion order.

func (*Store) AllKeysIgnored 

func (r *Store) AllKeysIgnored() []ifaces.ColID

Returns the list of all the ignored messages so far

func (*Store) AllKeysIgnoredAt 

func (r *Store) AllKeysIgnoredAt(round int) []ifaces.ColID

AllKeysIgnoredAt returns the list of all the Ignored columns ids so far at a given round. The returned slice is ordered by order of insertion.

func (*Store) AllKeysProof 

func (r *Store) AllKeysProof() []ifaces.ColID

AllKeysProof returns the list of all the Proof column's IDs ordered by round and then by order of insertion.

func (*Store) AllKeysProofAt 

func (r *Store) AllKeysProofAt(round int) []ifaces.ColID

AllKeysProofAt returns the list of all the IDs of the[Proof] messages at a given round. The returned list is ordered by order of insertion.

func (*Store) AllKeysProofsOrIgnoredButKeptInProverTranscript 

func (s *Store) AllKeysProofsOrIgnoredButKeptInProverTranscript(round int) []ifaces.ColID

AllKeysProofsOrIgnoredButKeptInProverTranscript returns the list of the columns to be used as part of the FS transcript.

func (*Store) AllKeysPublicInput 

func (r *Store) AllKeysPublicInput() []ifaces.ColID

AllKeysPublicInput returns the list of the PublicInput column's ID ordered by rounds and then by order ot insertion.

func (*Store) AllKeysPublicInputAt 

func (r *Store) AllKeysPublicInputAt(round int) []ifaces.ColID

AllKeysPublicInputAt returns the list of all the prover messages in a given round. The resulting slice is ordered by order of insertion.

func (*Store) AllPrecomputed 

func (r *Store) AllPrecomputed() []ifaces.ColID

Returns the list of all the Precomputed columns' ID. The returned slice is ordered by rounds and then by order of insertion.

func (*Store) AllVerifyingKey 

func (r *Store) AllVerifyingKey() []ifaces.ColID

AllVerifyingKey returns the list of all the IDs of the VerifyingKey columns ordered by rounds and then by order of insertion.

func (*Store) Exists 

func (s *Store) Exists(name ifaces.ColID) bool

Returns if the `name` exist in the commitment store

func (*Store) GetHandle 

func (s *Store) GetHandle(name ifaces.ColID) ifaces.Column

Returns the handle corresponding to a given name. Panic if not found.

func (*Store) GetSize 

func (s *Store) GetSize(n ifaces.ColID) int

GetSize returns the stored size of a Natural by its ID. This only works if the requested column is a Natural.

func (*Store) IgnoreButKeepInProverTranscript 

func (s *Store) IgnoreButKeepInProverTranscript(colName ifaces.ColID)

IgnoreButKeepInProverTranscript marks a column as ignored but also asks that the column stays included in the FS transcript. This is used as part of full-recursion where the commitments to an inner-proofs should not be sent to the verifier but should still play a part in the FS transcript.

func (*Store) IsIgnored 

func (s *Store) IsIgnored(name ifaces.ColID) (ignored bool)

IsIgnored returns true if the passed column ID relates to a column bearing the Ignored status.

func (*Store) IsIgnoredAndNotKeptInTranscript 

func (s *Store) IsIgnoredAndNotKeptInTranscript(colName ifaces.ColID) bool

IsIgnoredAndNotKeptInTranscript indicates whether the column can be ignored from the transcript and is used during the Fiat-Shamir randomness generation.

func (*Store) MarkAsIgnored 

func (s *Store) MarkAsIgnored(name ifaces.ColID)

Marks a commitment as ignored, this can happen during a vector slicing operation. Panics, if the name was not registered or if the commitment was already ignored.

func (*Store) MustBeInRound 

func (s *Store) MustBeInRound(name ifaces.ColID, round int)

Panics if the commitment name is not registered or if the round is the wrong one

func (*Store) MustHaveName 

func (s *Store) MustHaveName(name ifaces.ColID)

Panics if the store does not have the name registered

func (*Store) NumRounds 

func (r *Store) NumRounds() int

Returns the number of rounds

func (*Store) ReserveFor 

func (r *Store) ReserveFor(newLen int)

Make sure enough rounds are allocated up to the given length No-op if enough rounds have been allocated, otherwise, will reserve as many as necessary.

func (*Store) SetStatus 

func (s *Store) SetStatus(name ifaces.ColID, status Status)

Change the status of a commitment

func (*Store) Status 

func (s *Store) Status(name ifaces.ColID) Status

Returns the status of a column by its ID. This will panic if the provided column is not registered in the store.

Source Files

View all Source files

Directories

Path Synopsis

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.