agnostic

package
v1.2.23 Latest Latest
Warning

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

 Go to latest Published: Jul 22, 2026 License: Apache-2.0 Imports: 15 Imported by: 0

Documentation

Overview

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Index

Constants

View Source 
const USE_NEW_CHUNKUP = false

USE_NEW_CHUNKUP determines the chunkup algorithm to use. The new one is slower, but gets better results.

Variables

This section is empty.

Functions

func BoundsForMonomial 

func BoundsForMonomial(p DynamicMonomial) util.Bounds

BoundsForMonomial determines the largest positive / negative shift for any variable in a given monomial

func BoundsForPolynomial 

func BoundsForPolynomial(p DynamicPolynomial) util.Bounds

BoundsForPolynomial determines the largest positive / negative shift for any variable in a given polynomial.

func BoundsForRegister 

func BoundsForRegister(p register.AccessId) util.Bounds

BoundsForRegister determines the largest positive / negative shift for any relative register access.

func CombinedWidthOfRegisters 

func CombinedWidthOfRegisters(mapping register.Map, registers ...register.LimbId) uint

CombinedWidthOfRegisters returns the combined bitwidth of all limbs. For example, suppose we have three limbs: x:u8, y:u8, z:u11. Then the combined width is 8+8+11=27.

func DynamicPoly2String 

func DynamicPoly2String(p DynamicPolynomial, env register.Map) string

DynamicPoly2String provides a convenient helper function for debugging polynomials.

func EvalMonomial 

func EvalMonomial[F field.Element[F]](row uint, term DynamicMonomial, mod trace.Module[F]) F

EvalMonomial evaluates a given polynomial with a given environment (i.e. mapping of variables to values)

func EvalPolynomial 

func EvalPolynomial[F field.Element[F]](row uint, poly DynamicPolynomial, mod trace.Module[F]) F

EvalPolynomial evaluates a given polynomial with a given environment (i.e. mapping of variables to values)

func IntegerRangeOfMonomial 

func IntegerRangeOfMonomial[T RegisterIdentifier[T]](mono Monomial[T], env Environment[T]) util_math.Interval

IntegerRangeOfMonomial determines the smallest integer range in which all evaluations of the monomial lie. For example, consider the monomial "3*X*Y" where X and are 8bit and 16bit registers respectively. Then, the smallest enclosing integer range is 0 .. 3*255*65535.

func IntegerRangeOfPolynomial 

func IntegerRangeOfPolynomial[T RegisterIdentifier[T]](poly Polynomial[T], env Environment[T]) util_math.Interval

IntegerRangeOfPolynomial determines the smallest integer range in which all evaluations of this polynomial lie. For example, consider "2*X + 1" where X is an 8bit register. Then, the smallest integer range which includes this polynomial is "0..511".

func IntegerRangeOfRegister 

func IntegerRangeOfRegister[T RegisterIdentifier[T]](id T, env Environment[T]) util_math.Interval

IntegerRangeOfRegister determines the smallest integer range enclosing all possible values for a given register. For example, a register of width 16 has an integer range of 0..65535 (inclusive).

func RawWidthOfPolynomial 

func RawWidthOfPolynomial[T RegisterIdentifier[T]](source Polynomial[T], env Environment[T],
) (bitwidth uint, signed bool)

RawWidthOfPolynomial is essentially the same as WidthOfPolynomial, but does not adjust the returned width to include a sign bit.

func RegAccess2String 

func RegAccess2String(env register.Map) func(r register.AccessId) string

RegAccess2String provides a convenient helper function for debugging polynomials.

func RegisterReadSet 

func RegisterReadSet[T RegisterIdentifier[T]](p Polynomial[T]) bit.Set

RegisterReadSet returns the set of registers read by this instruction.

func RegistersRead 

func RegistersRead[T RegisterIdentifier[T]](p Polynomial[T]) []register.Id

RegistersRead returns the set of registers read by this instruction.

func SplitWidthOfPolynomial 

func SplitWidthOfPolynomial(source StaticPolynomial, env Environment[register.Id]) (poswidth uint, negwidth uint)

SplitWidthOfPolynomial resturns the number of bits required for all positive values, along with the number of bits required for all negative values. Observe that, unlike WidthOfPolynomial, this does not account for an additional sign bit.

func StaticPoly2String 

func StaticPoly2String(p StaticPolynomial, env register.Map) string

StaticPoly2String provides a convenient helper function for debugging polynomials.

func WidthOfMonomial 

func WidthOfMonomial[T RegisterIdentifier[T]](source Monomial[T], env Environment[T],
) (bitwidth uint, signed bool)

WidthOfMonomial determines the minimum number of bits required to store all possible evaluations of this mononomial. To determine the bitwidth of a monomial, this function first determines its smallest enclosing integer range.

func WidthOfPolynomial 

func WidthOfPolynomial[T RegisterIdentifier[T]](source Polynomial[T], env Environment[T],
) (bitwidth uint, signed bool)

WidthOfPolynomial determines the minimum number of bits required to store all possible evaluations of this polynomial. Observe that, in the case of negative values, this must include the sign bit as well. For example, a polynomial contained within the range 0..255 has a width of 8 bits. Likewise, a polynomial contained within the range -17 .. 15 has a width of 6bits. To understand this, consider that the positive component (0..15) has a width of 4 and the negative component (-17..-1) a width of 5. Since a sign bit is needed to distinguish the two cases, we have an overall width of 6 bits required for the polynomial.

To determine the bitwidth of a polynomial, this function first determines its smallest enclosing integer range. From this is then determines the required widths of the negative and positive components, before combining them to give the result.

Types

type Assignment 

type Assignment struct {
	// Target registers with least significant first
	LeftHandSide []register.Id
	// Right hand side.
	RightHandSide StaticPolynomial
}

Assignment provides a generic notion of an assignment from an arbitrary polynomial to a given set of target registers.

func NewAssignment 

func NewAssignment(lhs []register.Id, rhs StaticPolynomial) Assignment

NewAssignment constructs a new assignment with a given Left-Hand Side (LHS) and Right-Hand Side (RHS).

func (*Assignment) Signed 

func (p *Assignment) Signed(env register.Map) bool

Signed determines whether or not this is a signed assignment. That is, an assignment which must additionally consider negative values.

func (*Assignment) Split 

func (p *Assignment) Split(field field.Config, env RegisterAllocator) (eqs []Assignment)

Split an assignment according to a given field bandwidth. This creates one or more assignments implementing the original which operate safely within the given bandwidth. For example, consider the following assignment where all limbs are u8 (i.e. X'0, X'1, Y'0, and Y'1) and b is u1:

b, X'1, X'0 = (2^8*Y'1 + Y'0) + 1

This assignment cannot be safely evaluated within a field bandwidth of 16 bits (i.e. because the right-hand side could overflow). This is determined by checking the bandwidth against the computed width of the assignment (which, in this case, is 17). Since the computed width exceeds the available bandwidth, the assignment needs to split as follows:

b, X'1 = Y'1 + c

c, X'0 = Y'0 + 1

Here, c is an introduced u1 register for holding the "carry" (this is analoguous to carry flags as commonly found in CPU architectures). In general, the algorithm can result in temporary registers of arbitrary size being introduced. For example, consider a more complex case (again, u8 limbs):

X'3,X'2,X'1,X'0 = (2^8*Y'1 + Y'0) * (2^8*Z'1 + Z'0)

Here, the right-hand side expands as follows into the appropriate polynomial representation:

X'3,X'2,X'1,X'0 = (2^16*Y'1*Z'1) + (2^8*Y'1*Z'0) + (2^8*Y'0*Z'1) + (Y'0*Z'0)

The difficulty here is that the left- and right-hand sides are somewhat "misaligned". We can attempt to resolve this through large carry registers as follows: 

         X'3 = (Y'1*Z'1) + c1

c1, X'2, X'1 = (Y'1*Z'0) + (Y'0*Z'1) + c0

     c0, X'0 = (Y'0*Z'0)

Here, c0 and c1 are u8 and u1 carry registers respectively. Unfortunately, this means the middle assignment has a bandwidth requirement of 17bits (which still exceeds our original target of 16bits). Of course, if our bandwidth requirement was just slightly larger, then it would fit and we would be done.

For (sub-)assignments which still exceed the bandwidth requirement (such as above), we must further split them by introducing additional temporary registers.

func (*Assignment) String 

func (p *Assignment) String(env register.Map) string

func (*Assignment) Width 

func (p *Assignment) Width(env register.Map) (bitwidth uint, signed bool)

Width determines the minimal field width required to safely evaluate this assignment. Hence, this should not exceed the field bandwidth. The calculation is fairly straightforward: it is simply the maximum width of the left-hand and right-hand sides.

type Chunk 

type Chunk[T any] struct {
	// contains filtered or unexported fields
}

Chunk represents a "chunk of information bits".

type Computation 

type Computation = term.Computation[word.BigEndian]

Computation here represents an "agnostic" computation. That is one which operates over unbounded words.

type DynamicMonomial 

type DynamicMonomial = Monomial[register.AccessId]

DynamicMonomial defines the type of monomials contained within a given (relative) polynomial.

type DynamicPolynomial 

type DynamicPolynomial = Polynomial[register.AccessId]

DynamicPolynomial represents a polynomial over "relative registers". That is, it can refer to registers on the current row or on a row relative to the current row (e.g. the next row, or the previous row, etc).

func LimbPolynomial 

func LimbPolynomial(bitwidth uint, shift int, limbs []register.Id, widths []uint) (p DynamicPolynomial)

LimbPolynomial constructs a polynomial representing the combined value of all limbs according to their given bitwidths. For example, given [l0, l1, l2] with limbs widths [8,8,2] the resulting polynomial is: l0 + 2^8*l1 + 2^8*l2.

type Environment 

type Environment[T RegisterIdentifier[T]] func(T) uint

Environment provides a generic mechanism for associating the bitwidth of a register with its ID.

func ArrayEnvironment 

func ArrayEnvironment(registers []register.Register) Environment[register.Id]

ArrayEnvironment constructs an environment from a register array.

func DynamicEnvironment 

func DynamicEnvironment() Environment[register.AccessId]

DynamicEnvironment provides a simple implementation of Environment for rich register accesses.

func StaticEnvironment 

func StaticEnvironment(mapping register.Map) Environment[register.Id]

StaticEnvironment constructs an environment from a register map.

type Equation 

type Equation struct {
	// Left hand side.
	LeftHandSide DynamicPolynomial
	// Right hand side.
	RightHandSide DynamicPolynomial
}

Equation provides a generic notion of an equation between two polynomials. An equation is in *balanced form* if neither side contains a negative coefficient.

func NewEquation 

func NewEquation(lhs DynamicPolynomial, rhs DynamicPolynomial) Equation

NewEquation simply constructs a new equation.

func (*Equation) Balance 

func (p *Equation) Balance() Equation

Balance an equation means to convert it such that no negative coefficients remain. For example, balancing the equation "0 == x - 1" gives "1 == x". The benefit of balancing is simply that it eliminates any requirement for an interpretation of signed values.

func (*Equation) Split 

func (p *Equation) Split(field field.Config, env RegisterAllocator) (targets, context []Equation)

Split an equation according to a given field bandwidth. This creates one or more equations implementing the original which operate safely within the given bandwidth.

func (*Equation) String 

func (p *Equation) String(mapping register.Map) string

func (*Equation) Width 

func (p *Equation) Width(mapping register.Map) uint

Width determines the minimal field width required to safely evaluate this assignment. Hence, this should not exceed the field bandwidth. The calculation is fairly straightforward: it is simply the maximum width of the left-hand and right-hand sides.

type LhsChunk 

type LhsChunk = Chunk[[]register.Id]

LhsChunk captures the chunk type used for the Left-Hand Side (LHS) of an assignment.

type Monomial 

type Monomial[T util.Comparable[T]] = poly.Monomial[T]

Monomial defines the type of monomials contained within a given polynomial.

type PolyFil 

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

PolyFil is a simple construct used for filling the various temporary registers (e.g. for holding carry values) that arise as part of register splitting.

func NewPolyFil 

func NewPolyFil(rshift uint, poly DynamicPolynomial) *PolyFil

NewPolyFil constructs a new poly fil computation.

func (*PolyFil) ApplyShift 

func (p *PolyFil) ApplyShift(shift int) Computation

ApplyShift implementation for Term interface.

func (*PolyFil) Bounds 

func (p *PolyFil) Bounds() util.Bounds

Bounds implementation for Boundable interface.

func (*PolyFil) EvalAt 

func (p *PolyFil) EvalAt(k int, tr trace.Module[word.BigEndian], sc register.Map) (word.BigEndian, error)

EvalAt implementation for Evaluable interface.

func (*PolyFil) Lisp 

func (p *PolyFil) Lisp(global bool, mapping register.Map) sexp.SExp

Lisp implementation for Lispifiable interface.

func (*PolyFil) Polynomial 

func (p *PolyFil) Polynomial() DynamicPolynomial

Polynomial returns the underlying polynomial.

func (*PolyFil) RequiredCells 

func (p *PolyFil) RequiredCells(row int, mid trace.ModuleId) *set.AnySortedSet[trace.CellRef]

RequiredCells implementation for Contextual interface

func (*PolyFil) RequiredRegisters 

func (p *PolyFil) RequiredRegisters() *set.SortedSet[uint]

RequiredRegisters implementation for Contextual interface.

func (*PolyFil) RightShift 

func (p *PolyFil) RightShift() uint

RightShift returns the post-evaluation right shift.

func (*PolyFil) ShiftRange 

func (p *PolyFil) ShiftRange() (int, int)

ShiftRange implementation for Term interface.

func (*PolyFil) Simplify 

func (p *PolyFil) Simplify(casts bool) Computation

Simplify implementation for Term interface.

func (*PolyFil) Substitute 

func (p *PolyFil) Substitute(mapping map[string]word.BigEndian)

Substitute implementation for Substitutable interface.

func (*PolyFil) ValueRange 

func (p *PolyFil) ValueRange() math.Interval

ValueRange implementation for Term interface.

type Polynomial 

type Polynomial[T util.Comparable[T]] = *poly.ArrayPoly[T]

Polynomial defines the type of polynomials over which packets (and register splitting in general) operate.

func SubstituteMonomial 

func SubstituteMonomial[T RegisterIdentifier[T]](t Monomial[T], mapping func(T) Polynomial[T]) Polynomial[T]

SubstituteMonomial replaces all occurrences of a given variable with a set of (zero or more) variables (e.g. typically used for substituting limbs).

func SubstitutePolynomial 

func SubstitutePolynomial[T RegisterIdentifier[T]](p Polynomial[T], mapping func(T) Polynomial[T]) (r Polynomial[T])

SubstitutePolynomial replaces all occurrences of a given variable with a set of (zero or more) variables (e.g. typically used for substituting limbs).

type RegisterAllocator 

type RegisterAllocator = register.Allocator[term.Computation[word.BigEndian]]

RegisterAllocator is used to allocate fresh registers with optional "fillers". That is, computation which can be used to assign values to them in the final trace.

type RegisterIdentifier 

type RegisterIdentifier[T any] interface {
	util.Comparable[T]
	// Id returns the underlying register id for this identifier.
	Id() register.Id
}

RegisterIdentifier enables functions which are generic over the identifier used in a polynomial (either relative or not relative, etc).

type RegisterSplitter 

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

RegisterSplitter is used to manage the mechanism of splitting variables into limbs in order to improve the precision of a chunk.

func NewRegisterSplitter 

func NewRegisterSplitter(n uint) RegisterSplitter

NewRegisterSplitter constructs a new splitter for a given number of variables.

func (*RegisterSplitter) Apply 

func (p *RegisterSplitter) Apply(poly StaticPolynomial, mapping RegisterAllocator) StaticPolynomial

Apply the current subdivisions to a given polynomial. Specifically, this splits all registers into their limbs and subsitutes them into the polynomial. As a by-product this also records the assignments needed for the mapping from registers to their limbs.

func (*RegisterSplitter) ParentOf 

func (p *RegisterSplitter) ParentOf(v register.Id) register.Id

ParentOf gets the original source variable from which this variable was derived (if it was indeed derived). For example, if a register X is split into limbs X'1 and X'0, then the parent of the two limbs is X. In the case that a register was not derived through splitting, then it is its own parent.

func (*RegisterSplitter) Reset 

func (p *RegisterSplitter) Reset()

Reset assignments created for the current splitting, and the ledger of parents.

func (*RegisterSplitter) String 

func (p *RegisterSplitter) String(mapping register.Map) string

func (*RegisterSplitter) Subdivide 

func (p *RegisterSplitter) Subdivide(vars bit.Set) bool

Subdivide takes all registers in the given set and further subdivides them. For example, if they were previously being divided in 2, then they will now be divided in 4, etc.

type RhsChunk 

type RhsChunk = Chunk[StaticPolynomial]

RhsChunk captures the chunk type used for the Right-Hand Side (RHS) of an assignment.

type StaticMonomial 

type StaticMonomial = Monomial[register.Id]

StaticMonomial defines the type of monomials contained within a given (static) polynomial.

type StaticPolynomial 

type StaticPolynomial = Polynomial[register.Id]

StaticPolynomial represents a polynomial over registers on the current row. In other words, a polynomial which cannot refer to a register on a different (i.e. relative) row.

func StaticLimbPolynomial 

func StaticLimbPolynomial(bitwidth uint, limbs []register.Id, widths []uint) (p StaticPolynomial)

StaticLimbPolynomial constructs a polynomial representing the combined value of all limbs according to their given bitwidths. For example, given [l0, l1, l2] with limbs widths [8,8,2] the resulting polynomial is: l0 + 2^8*l1 + 2^8*l2.

type VariableSplitter 

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

VariableSplitter is responsible for splitting one or more variables into smaller limbs using a given maximum bitwidth. Furthermore, it can be used to efficiently substitute those variables for their limbs in a given polynomial.

func NewVariableSplitter 

func NewVariableSplitter(mapping RegisterAllocator, bitwidth uint) VariableSplitter

NewVariableSplitter constructs a new splitter for a given bitwidth.confui

func (*VariableSplitter) Apply 

func (p *VariableSplitter) Apply(poly DynamicPolynomial) DynamicPolynomial

Apply the splitting to a given polynomial by substituting through all split variables for their allocated limbs, whilst leaving all others untouched.

func (*VariableSplitter) SplitVariable 

func (p *VariableSplitter) SplitVariable(rid register.Id) Equation

SplitVariable splits a single variable into limbs of the given maximum bitwidth configured for this splitter, and produces an equation mapping that variable to its limbs.

func (*VariableSplitter) SplitVariables 

func (p *VariableSplitter) SplitVariables(vars bit.Set) (constraints []Equation)

SplitVariables splits a given set of variables into limbs of maximum bitwidth configured for this splitter. This produces a set of equations which map each variable to its limbs.

func (*VariableSplitter) StaticApply 

func (p *VariableSplitter) StaticApply(poly StaticPolynomial) StaticPolynomial

StaticApply the splitting to a given polynomial by substituting through all split variables for their allocated limbs, whilst leaving all others untouched.

func (*VariableSplitter) StaticSplitVar 

func (p *VariableSplitter) StaticSplitVar(rid register.Id) Assignment

StaticSplitVar splits a single variable into limbs of the given maximum bitwidth configured for this splitter, and produces an equation mapping that variable to its limbs.

func (*VariableSplitter) StaticSplitVars 

func (p *VariableSplitter) StaticSplitVars(vars bit.Set) (constraints []Assignment)

StaticSplitVars splits a given set of variables into limbs of maximum bitwidth configured for this splitter. This produces a set of equations which map each variable to its limbs.

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.