cs

package
v0.1.0-alpha Latest Latest
Warning

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

 Go to latest Published: Mar 6, 2020 License: Apache-2.0 Imports: 8 Imported by: 0

README

Under the hood of a circuit

Technically, inside gnark, a circuit is implemented in a ConstraintSystem.

A ConstraintSystem is (mostly) a collection of Constraint. In a circuit, those would be "gates": a box that takes "wires" in, and outputs a single "wire". As we will see, a Constraint is a more abstract and more general representation.

In gnark, when we design a circuit, we declare inputs (i.e x := circuit.SECRET_INPUT("x")) and use gnark API to describe the circuit (i.e a := circuit.ADD(x, 3)).

This phase fills the data structure of the ConstraintSystem.

Some proving systems, like Groth16, use a particular type of constraint system called "rank 1 constraint system" (R1CS), which are constraints in the form a * b == c.

ConstraintSystem to R1CS

The Constraint struct used in the ConstraintSystem is different than the r1c (rank 1 constraint) used in the R1CS.

One can see the R1CS as a "compiled" circuit --> the data structure is immutable and hence, simpler. It is also pointer-less, to avoid garbage collection overhead with large circuits.

What is a Constraint?

A Constraint is a list of expression that must be equal to an output wire (if they are not, we say the Constraint is not satisfied).

An expression is an arithmetic statement (at most, operations are quadratic) f(x0, x1, ..xn) = y.

For example,

x := circuit.ADD(y, z)

creates the expression y * 1 + z * 1:

expression := &linearExpression{
	term{Wire: y.outputWire, Coeff: curve.One()},
	term{Wire: z.outputWire, Coeff: curve.One()},
}

Example: c = a xor b has this form as a rank one constraint: (2a)*b = a+b-c, so c = a+b-2ab, the expression is then a+b-2ab.

An expression has to be converted into a rank one constraint. For the previours example, a+b-2ab along with c will be converted to 2ab = a+b-c.

The conversion

From the ConstraintSystem , we build a R1CS in 4 steps:

  1. Loop through all the Constraint and collect the variables
  2. Loop though all the Constraint, isolate the expressions involved in the computational graph, link the variable computed from the expression to the expression
  3. Number the variables
  4. Split the Constraint into r1c
Solving the R1CS

Each expression provides one or several outputs once its inputs are instantiated. We can see then see them as a computational graph, each node being a constraint.

If the user specifies all the inputs, all the variables can be instantiated. The only way to declare unconstrained variables is to declare an input. All other constraints are using these or resulting constraints for operations on this to be computed.

The constraints involved in the computational graph have been isolated in the previous step. We just have to post order them to know in what order we should loop through them.

Example:

    s := cs.New()

    x := s.SECRET_INPUT("x")

    v1 := s.MUL(x, x)
    v2 := s.MUL(v1, v1)
    s.ADD(v1, v2)

    r1cs := cs.NewR1CS(&s)

The state of the r1cs is as follows (the numbering of the wires does not correspond to the variables v1 and v2):

variables:
wire_0, wire_1, wire_2, x, ONE_WIRE (=wire_4)

computational gaph:
0. (1*wire_2 )*(1*wire_2 )=1*wire_0
1. (1wire_2 +1*wire_0)*(1*wire_4) )=1*wire_1
2. (1*x )*(1*x)=1*wire_2

Graph ordering:
2, 0, 1

See that the constraints in the computational graph are not ordered (the order in which they are stored doesn't matter). After the post ordering, we see that the solver will use constraint 2 to compute the wire2 (corresponding to v1) from x, the user input, then the constraint 0, to compute wire0 (v2) from wire2, then the constraint 1 to get wire_1. The ONE_WIRE wire (wire_4) is a constant variable equal to 1, given to each circuit.

Documentation

Overview

Package cs contains Constraint System representation and R1CS to be used with zero knowledge proof systems in gnark

Index

Constants

View Source 
const CurveID = curve.CurveID

CurveID exposes the CurveID cs package is being compiled with (see internal/curve)

View Source 
const OneWire = "ONE_WIRE"

OneWire is the assignment label / name used for the constant wire one

Variables

View Source 
var (
	ErrDuplicateTag           = errors.New("duplicate tag")
	ErrInconsistantConstraint = errors.New("inconsistant constraint")
	ErrInputNotSet            = errors.New("input not set")
	ErrInputVisiblity         = errors.New("input has incorrect visibility (secret / public)")
	ErrUnsatisfiedConstraint  = errors.New("constraint is not satisfied")
)

Functions

func Element 

func Element(i1 interface{}) curve.Element

Element converts a [uint64, int, string, *Element] to a curve.Element see internal/curve this methods panic if the provided interface is not supported

Types

type Assert 

type Assert struct {
	*require.Assertions
	// contains filtered or unexported fields
}

Assert is a helper to test circuits

func NewAssert 

func NewAssert(t *testing.T) *Assert

NewAssert returns an helper to test Constraint Systems this helper embeds a stretch/testify Assert object for convenience

func (*Assert) NotSolved 

func (assert *Assert) NotSolved(circuit CS, solution Assignments)

NotSolved check that a solution does NOT solve a circuit error may be missing inputs or unsatisfied constraints

func (*Assert) Solved 

func (assert *Assert) Solved(circuit CS, solution Assignments, expectedValues map[string]interface{})

Solved check that a solution solves a circuit for each expectedValues, this helper compares the output from r1cs.Inspect() after Solving. this helper also ensure the result vectors a*b=c

type Assignment 

type Assignment struct {
	Value    curve.Element
	IsPublic bool // default == false (assignemnt is private)
}

Assignment is used to specify inputs to the Prove and Verify functions

type Assignments 

type Assignments map[string]Assignment

Assignments is used to specify inputs to the Prove and Verify functions

func NewAssignment 

func NewAssignment() Assignments

NewAssignment returns an empty Assigments object

func (Assignments) Assign 

func (a Assignments) Assign(visibility Visibility, name string, v interface{})

Assign assign a value to a Secret/Public input identified by its name

type CS 

type CS struct {

	// under the key i are all the expressions that must be equal to a single wire
	Constraints map[uint64]*Constraint

	// constraints yielding multiple outputs (eg unpacking)
	MOConstraints []moExpression

	// constraints yielding no outputs (eg boolean constraints)
	NOConstraints []expression
	// contains filtered or unexported fields
}

CS Constraint System

func New 

func New() CS

New returns a new constraint system

func (*CS) ADD 

func (cs *CS) ADD(i1, i2 interface{}, in ...interface{}) *Constraint

ADD Adds 2+ inputs and returns resulting Constraint

func (*CS) ALLOCATE 

func (cs *CS) ALLOCATE(input interface{}) *Constraint

ALLOCATE will return an allocated cs.Constraint from input {Constraint, element, uint64, int, ...}

func (*CS) DIV 

func (cs *CS) DIV(i1, i2 interface{}) *Constraint

DIV divides two constraints (i1/i2)

func (*CS) FROM_BINARY 

func (cs *CS) FROM_BINARY(b ...*Constraint) *Constraint

FROM_BINARY c = bi*2^i (first item of b = LSb of c)

func (*CS) INV 

func (cs *CS) INV(c1 *Constraint) *Constraint

INV inverse a Constraint

func (*CS) MUL 

func (cs *CS) MUL(i1, i2 interface{}, in ...interface{}) *Constraint

MUL Multiplies 2+ constraints together

func (*CS) MUSTBE_BOOLEAN 

func (cs *CS) MUSTBE_BOOLEAN(c *Constraint)

MUSTBE_BOOLEAN boolean constrains a variable

func (*CS) MUSTBE_EQ 

func (cs *CS) MUSTBE_EQ(i1, i2 interface{})

MUSTBE_EQ equalizes two constraints

func (*CS) MUSTBE_LESS_OR_EQ 

func (cs *CS) MUSTBE_LESS_OR_EQ(c *Constraint, input interface{})

MUSTBE_LESS_OR_EQ constrains c to be less or equal than e (taken as lifted Integer values from Fr)

func (*CS) PUBLIC_INPUT 

func (cs *CS) PUBLIC_INPUT(name string) *Constraint

PUBLIC_INPUT creates a Constraint containing an input

func (*CS) SECRET_INPUT 

func (cs *CS) SECRET_INPUT(name string) *Constraint

SECRET_INPUT creates a Constraint containing an input

func (*CS) SELECT 

func (cs *CS) SELECT(b *Constraint, i1, i2 interface{}) *Constraint

SELECT if b is true, yields c1 else yields c2

func (*CS) SELECT_LUT 

func (cs *CS) SELECT_LUT(c1, c0 *Constraint, lookuptable [4]curve.Element) *Constraint

SELECT_LUT select lookuptable[c1*2+c0] where c0 and c1 are boolean constrained cf https://z.cash/technology/jubjub/

func (*CS) SUB 

func (cs *CS) SUB(i1, i2 interface{}) *Constraint

SUB Adds two constraints

func (*CS) String 

func (cs *CS) String() string

func (*CS) TO_BINARY 

func (cs *CS) TO_BINARY(c *Constraint, nbBits int) []*Constraint

TO_BINARY unpacks a variable in binary, n is the number of bits of the variable The result in in little endian (first bit= lsb)

func (*CS) Write 

func (cs *CS) Write(path string)

Write creates a R1CS from the CS and writes it to disk

func (*CS) XOR 

func (cs *CS) XOR(c1, c2 *Constraint) *Constraint

XOR compute the xor between two constraints

type Constraint 

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

Constraint list of expressions that must be equal+an output wire, that can be computed out of the inputs wire. A Constraint is a list of expressions that are equal. Each expression yields the value of another wire. A Constraint contains only one wire expression, and at least one expression, unless the wire expression is an input. under the constraintID i are all the expressions that must be equal under the constraintID i, exactly one Constraint can be single wire and there is at least a linear Constraint or a single wire

func (*Constraint) Tag 

func (c *Constraint) Tag(tag string)

Tag adds a tag to the constraint's singleWire once the R1CS system is solved r1cs.Inspect() may return a map[string]value of constraints with Tags

type LinearCombination 

type LinearCombination []Term

LinearCombination linear combination of constraints

type R1CS 

type R1CS struct {

	//wiretracker = [..PrivateInputsStartIndex-1] || [PrivateInputsStartIndex..PublicInputsStartIndex-1] || [PublicInputsStartIndex...]. The label of the wire is the index in the wire tracker
	PrivateInputsStartIndex int
	PublicInputsStartIndex  int

	// index i = wire with index i
	WireTracker []wire

	// Actual description of the constraint system
	GraphOrdering      []int64 // order in which to compute the computational graph
	ComputationalGraph []r1c   // Constraints to instantiate the variables
	Constraints        []r1c   // Constraints left from the computational graph
}

R1CS decsribes a set of R1CS constraint

func NewR1CS 

func NewR1CS(circuit *CS) *R1CS

NewR1CS builds a R1CS from a system of Constraints

func (R1CS) Inspect 

func (r1cs R1CS) Inspect() (map[string]curve.Element, error)

Inspect returns the tagged variables with their corresponding value

func (*R1CS) NbConstraints 

func (r1cs *R1CS) NbConstraints() int

NbConstraints returns the number of Constraints

func (*R1CS) NbPrivateInputs 

func (r1cs *R1CS) NbPrivateInputs() int

NbPrivateInputs returns the number of Private inputs

func (*R1CS) NbPublicInputs 

func (r1cs *R1CS) NbPublicInputs() int

NbPublicInputs returns the number of Public inputs (without the ONEWIRE)

func (*R1CS) Solve 

func (r1cs *R1CS) Solve(assignment map[string]Assignment) (a, b, c []curve.Element, err error)

Solve sets all the wires and returns the a, b, c vectors. the r1cs system should have been compiled before. The entries in a, b, c are in Montgomery form. assignment: map[string]value: contains the input variables a, b, c vectors: ab-c = hz

func (R1CS) String 

func (r1cs R1CS) String() string

String string format of the r1cs

type Term 

type Term struct {
	Constraint *Constraint
	Coeff      curve.Element
}

Term coeff*constraint

type Visibility 

type Visibility string

Visibility type alias on string to define circuit input's visibility 

const (
	Secret Visibility = "secret"
	Public Visibility = "public"
)

Possible Visibility attributes for circuit inputs

Source Files

View all Source files

Directories

Path Synopsis
encoding
csv
gob
Package groth16 exposes zkSNARK (Groth16) 3 algorithms: Setup, Prove and Verify
 Package groth16 exposes zkSNARK (Groth16) 3 algorithms: Setup, Prove and Verify
internal
curve
Package curve enables the cs package to use various curves through build tags
 Package curve enables the cs package to use various curves through build tags
std
Package std contains 2 sub-tree: reference and gadget reference is completly independant from gadget gadget may use reference data-structures not all gadget need a reference implementation, but that's helpful, at least for testing purposes
 Package std contains 2 sub-tree: reference and gadget reference is completly independant from gadget gadget may use reference data-structures not all gadget need a reference implementation, but that's helpful, at least for testing purposes
gadget/accumulator/merkle
gadget/algebra/twisted_edwards
gadget/hash/mimc
gadget/signature/eddsa
reference/accumulator/merkle
reference/algebra/twisted_edwards
reference/hash/mimc
reference/signature/eddsa

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.