system.go

// Copyright 2020 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.

// Code generated by gnark DO NOT EDIT

package cs

import (
	"io"
	"time"

	"github.com/consensys/gnark/backend/witness"
	"github.com/consensys/gnark/constraint"
	csolver "github.com/consensys/gnark/constraint/solver"
	"github.com/consensys/gnark/logger"

	"github.com/consensys/gnark-crypto/ecc"

	"github.com/consensys/gnark-crypto/ecc/bw6-633/fr"
)

type R1CS = system
type SparseR1CS = system

// system is a curved-typed constraint.System with a concrete coefficient table (fr.Element)
type system struct {
	constraint.System
	CoeffTable
	field
}

// NewR1CS is a constructor for R1CS. It is meant to be use by gnark frontend only,
// and should not be used by gnark users. See groth16.NewCS(...) instead.
func NewR1CS(capacity int) *R1CS {
	return newSystem(capacity, constraint.SystemR1CS)
}

// NewSparseR1CS is a constructor for SparseR1CS. It is meant to be use by gnark frontend only,
// and should not be used by gnark users. See plonk.NewCS(...) instead.
func NewSparseR1CS(capacity int) *SparseR1CS {
	return newSystem(capacity, constraint.SystemSparseR1CS)
}

func newSystem(capacity int, t constraint.SystemType) *system {
	return &system{
		System:     constraint.NewSystem(fr.Modulus(), capacity, t),
		CoeffTable: newCoeffTable(capacity / 10),
	}
}

// Solve solves the constraint system with provided witness.
// If it's a R1CS returns R1CSSolution
// If it's a SparseR1CS returns SparseR1CSSolution
func (cs *system) Solve(witness witness.Witness, opts ...csolver.Option) (any, error) {
	log := logger.Logger().With().Int("nbConstraints", cs.GetNbConstraints()).Logger()
	start := time.Now()

	v := witness.Vector().(fr.Vector)

	// init the solver
	solver, err := newSolver(cs, v, opts...)
	if err != nil {
		log.Err(err).Send()
		return nil, err
	}

	// reset the stateful blueprints
	for i := range cs.Blueprints {
		if b, ok := cs.Blueprints[i].(constraint.BlueprintStateful); ok {
			b.Reset()
		}
	}

	// defer log printing once all solver.values are computed
	// (or sooner, if a constraint is not satisfied)
	defer solver.printLogs(cs.Logs)

	// run it.
	if err := solver.run(); err != nil {
		log.Err(err).Send()
		return nil, err
	}

	log.Debug().Dur("took", time.Since(start)).Msg("constraint system solver done")

	// format the solution
	// TODO @gbotrel revisit post-refactor
	if cs.Type == constraint.SystemR1CS {
		var res R1CSSolution
		res.W = solver.values
		res.A = solver.a
		res.B = solver.b
		res.C = solver.c
		return &res, nil
	} else {
		// sparse R1CS
		var res SparseR1CSSolution
		// query l, r, o in Lagrange basis, not blinded
		res.L, res.R, res.O = evaluateLROSmallDomain(cs, solver.values)

		return &res, nil
	}

}

// IsSolved
// Deprecated: use _, err := Solve(...) instead
func (cs *system) IsSolved(witness witness.Witness, opts ...csolver.Option) error {
	_, err := cs.Solve(witness, opts...)
	return err
}

// GetR1Cs return the list of R1C
func (cs *system) GetR1Cs() []constraint.R1C {
	toReturn := make([]constraint.R1C, 0, cs.GetNbConstraints())

	for _, inst := range cs.Instructions {
		blueprint := cs.Blueprints[inst.BlueprintID]
		if bc, ok := blueprint.(constraint.BlueprintR1C); ok {
			var r1c constraint.R1C
			bc.DecompressR1C(&r1c, inst.Unpack(&cs.System))
			toReturn = append(toReturn, r1c)
		}
	}
	return toReturn
}

// GetNbCoefficients return the number of unique coefficients needed in the R1CS
func (cs *system) GetNbCoefficients() int {
	return len(cs.Coefficients)
}

// CurveID returns curve ID as defined in gnark-crypto
func (cs *system) CurveID() ecc.ID {
	return ecc.BW6_633
}

func (cs *system) GetCoefficient(i int) (r constraint.Element) {
	copy(r[:], cs.Coefficients[i][:])
	return
}

// GetSparseR1Cs return the list of SparseR1C
func (cs *system) GetSparseR1Cs() []constraint.SparseR1C {

	toReturn := make([]constraint.SparseR1C, 0, cs.GetNbConstraints())

	for _, inst := range cs.Instructions {
		blueprint := cs.Blueprints[inst.BlueprintID]
		if bc, ok := blueprint.(constraint.BlueprintSparseR1C); ok {
			var sparseR1C constraint.SparseR1C
			bc.DecompressSparseR1C(&sparseR1C, inst.Unpack(&cs.System))
			toReturn = append(toReturn, sparseR1C)
		}
	}
	return toReturn
}

// evaluateLROSmallDomain extracts the solver l, r, o, and returns it in lagrange form.
// solver = [ public | secret | internal ]
// TODO @gbotrel refactor; this seems to be a small util function for plonk
func evaluateLROSmallDomain(cs *system, solution []fr.Element) ([]fr.Element, []fr.Element, []fr.Element) {

	//s := int(pk.Domain[0].Cardinality)
	s := cs.GetNbConstraints() + len(cs.Public) // len(spr.Public) is for the placeholder constraints
	s = int(ecc.NextPowerOfTwo(uint64(s)))

	var l, r, o []fr.Element
	l = make([]fr.Element, s, s+4) // +4 to leave room for the blinding in plonk
	r = make([]fr.Element, s, s+4)
	o = make([]fr.Element, s, s+4)
	s0 := solution[0]

	for i := 0; i < len(cs.Public); i++ { // placeholders
		l[i] = solution[i]
		r[i] = s0
		o[i] = s0
	}
	offset := len(cs.Public)
	nbConstraints := cs.GetNbConstraints()

	var sparseR1C constraint.SparseR1C
	j := 0
	for _, inst := range cs.Instructions {
		blueprint := cs.Blueprints[inst.BlueprintID]
		if bc, ok := blueprint.(constraint.BlueprintSparseR1C); ok {
			bc.DecompressSparseR1C(&sparseR1C, inst.Unpack(&cs.System))

			l[offset+j] = solution[sparseR1C.XA]
			r[offset+j] = solution[sparseR1C.XB]
			o[offset+j] = solution[sparseR1C.XC]
			j++
		}
	}

	offset += nbConstraints

	for i := 0; i < s-offset; i++ { // offset to reach 2**n constraints (where the id of l,r,o is 0, so we assign solver[0])
		l[offset+i] = s0
		r[offset+i] = s0
		o[offset+i] = s0
	}

	return l, r, o

}

// R1CSSolution represent a valid assignment to all the variables in the constraint system.
// The vector W such that Aw o Bw - Cw = 0
type R1CSSolution struct {
	W       fr.Vector
	A, B, C fr.Vector
}

func (t *R1CSSolution) WriteTo(w io.Writer) (int64, error) {
	n, err := t.W.WriteTo(w)
	if err != nil {
		return n, err
	}
	a, err := t.A.WriteTo(w)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.B.WriteTo(w)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.C.WriteTo(w)
	n += a
	return n, err
}

func (t *R1CSSolution) ReadFrom(r io.Reader) (int64, error) {
	n, err := t.W.ReadFrom(r)
	if err != nil {
		return n, err
	}
	a, err := t.A.ReadFrom(r)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.B.ReadFrom(r)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.C.ReadFrom(r)
	n += a
	return n, err
}

// SparseR1CSSolution represent a valid assignment to all the variables in the constraint system.
type SparseR1CSSolution struct {
	L, R, O fr.Vector
}

func (t *SparseR1CSSolution) WriteTo(w io.Writer) (int64, error) {
	n, err := t.L.WriteTo(w)
	if err != nil {
		return n, err
	}
	a, err := t.R.WriteTo(w)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.O.WriteTo(w)
	n += a
	return n, err

}

func (t *SparseR1CSSolution) ReadFrom(r io.Reader) (int64, error) {
	n, err := t.L.ReadFrom(r)
	if err != nil {
		return n, err
	}
	a, err := t.R.ReadFrom(r)
	n += a
	if err != nil {
		return n, err
	}
	a, err = t.O.ReadFrom(r)
	n += a
	return n, err
}

func (s *system) AddGkr(gkr constraint.GkrInfo) error {
	return s.System.AddGkr(gkr)
}