<|start_filename|>snark/polynomial/eq_test.go<|end_filename|>
package polynomial

import (
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"
	"testing"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
)

type TestEqCircuit struct {
	H, Q          [][]frontend.Variable
	ExpectedValue []frontend.Variable
}

func AllocateTestEqCircuit(nTests, testSize int) TestEqCircuit {
	H := make([][]frontend.Variable, nTests)
	Q := make([][]frontend.Variable, nTests)
	ExpectedValue := make([]frontend.Variable, nTests)

	for k := range H {
		H[k] = make([]frontend.Variable, testSize)
		Q[k] = make([]frontend.Variable, testSize)
	}

	return TestEqCircuit{
		H:             H,
		Q:             Q,
		ExpectedValue: ExpectedValue,
	}
}

func (eq *TestEqCircuit) Assign(H, Q [][]fr.Element) {
	for k := range H {
		for n := range Q {
			eq.H[k][n].Assign(H[k][n])
			eq.Q[k][n].Assign(Q[k][n])
		}
		eq.ExpectedValue[k].Assign(polynomial.EvalEq(Q[k], H[k]))
	}
}

func (eq *TestEqCircuit) Define(curveID ecc.ID, cs *frontend.ConstraintSystem) error {
	for i := range eq.H {
		h := EqEval(cs, eq.H[i], eq.Q[i])
		cs.AssertIsEqual(h, eq.ExpectedValue[i])
	}
	return nil
}

func TestEq(t *testing.T) {

	eq := AllocateTestEqCircuit(5, 5)
	r1cs, err := frontend.Compile(ecc.BN254, backend.GROTH16, &eq)

	assert := groth16.NewAssert(t)
	assert.NoError(err)

	witness := AllocateTestEqCircuit(5, 5)

	H := [][]fr.Element{
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
	}

	Q := [][]fr.Element{
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
		common.RandomFrArray(5),
	}

	witness.Assign(H, Q)
	assert.SolvingSucceeded(r1cs, &witness)
	assert.ProverSucceeded(r1cs, &witness)
}


<|start_filename|>circuit/gates.go<|end_filename|>
package circuit

import (
	"fmt"

	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/consensys/gnark/frontend"
)

// Gate assumes the gate can only have 2 inputs
type Gate interface {
	// ID returns an ID that is unique for the gate
	ID() string
	// GnarkEval performs the same computation as Eval but on Gnark variables
	GnarkEval(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable
	// Eval returns an evaluation for a unique pair of Eval
	Eval(res, vL, vR *fr.Element)
	// EvalManyVL returns multiple evaluations with the same vR
	EvalManyVL(res, vLs []fr.Element, vR *fr.Element)
	// EvalManyVR returns multiple evaluations with the same vL
	EvalManyVR(res []fr.Element, vL *fr.Element, vRs []fr.Element)
	// Degrees returns the degrees of the gate relatively to HL, HR, HPrime
	Degrees() (degHL, degHR, degHPrime int)
}

// EvaluateCombinator evaluate eq * \sum_i{ statics_i * gates_i(vL, vR) }
func EvaluateCombinator(vL, vR, eq *fr.Element, gates []Gate, statics []fr.Element) fr.Element {
	var tmp, res fr.Element
	for i := range gates {
		gates[i].Eval(&tmp, vL, vR)
		tmp.Mul(&statics[i], &tmp)
		res.Add(&res, &tmp)
	}
	res.Mul(&res, eq)
	return res
}

// AddGate performs an addition
type AddGate struct{}

// ID returns the gate ID
func (a AddGate) ID() string { return "AddGate" }

// Eval return the result vL + vR
func (a AddGate) Eval(res, vL, vR *fr.Element) {
	res.Add(vL, vR)
}

// GnarkEval compute the gate on a gnark circuit
func (a AddGate) GnarkEval(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
	// Unoptimized, but unlikely to cause any significant performance loss
	return cs.Add(vL, vR)
}

// EvalManyVR performs an element-wise addition of many vRs values by one vL value
// res must be initialized with the same size as vRs
func (a AddGate) EvalManyVR(res []fr.Element, vL *fr.Element, vRs []fr.Element) {
	for i, vR := range vRs {
		res[i].Add(vL, &vR)
	}
}

// EvalManyVL performs an element-wise addition of many vLs values by one vR value
func (a AddGate) EvalManyVL(res []fr.Element, vLs []fr.Element, vR *fr.Element) {
	for i, vL := range vLs {
		res[i].Add(&vL, vR)
	}
}

// Degrees returns the degrees of the gate on hL, hR and hPrime
func (a AddGate) Degrees() (degHL, degHR, degHPrime int) {
	return 1, 1, 1
}

// MulGate performs a multiplication
type MulGate struct{}

// ID returns the MulGate as ID
func (m MulGate) ID() string { return "MulGate" }

// Eval returns vL * vR
func (m MulGate) Eval(res, vL, vR *fr.Element) {
	res.Mul(vL, vR)
}

// GnarkEval performs the gate operation on gnark variables
func (m MulGate) GnarkEval(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
	return cs.Mul(vL, vR)
}

// EvalManyVR performs an element-wise multiplication of many vRs values by one vL value
func (m MulGate) EvalManyVR(res []fr.Element, vL *fr.Element, vRs []fr.Element) {
	for i, vR := range vRs {
		res[i].Mul(vL, &vR)
	}
}

// EvalManyVL performs an element-wise multiplication of many vLs values by one vR value
func (m MulGate) EvalManyVL(res, vLs []fr.Element, vR *fr.Element) {
	for i, vL := range vLs {
		res[i].Mul(&vL, vR)
	}
}

// Degrees returns the degrees of the gate on hL, hR and hPrime
func (m MulGate) Degrees() (degHL, degHR, degHPrime int) {
	return 1, 1, 2
}

// CopyGate performs a copy of the vL value and ignores the vR value
type CopyGate struct{}

// ID returns "CopyGate" as an ID for CopyGate
func (c CopyGate) ID() string { return "CopyGate" }

// Eval returns vL
func (c CopyGate) Eval(res, vL, vR *fr.Element) {
	res.Set(vL)
	// *res = vL
}

// GnarkEval performs the copy on gnark variable
func (c CopyGate) GnarkEval(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
	return vL
}

// EvalManyVR performs an element-wise copy of vL for many vRs. (ignoring the values of the vRs)
func (c CopyGate) EvalManyVR(res []fr.Element, vL *fr.Element, vRs []fr.Element) {
	for i := range vRs {
		res[i].Set(vL)
	}
}

// EvalManyVL performs an element-wise copy of many vLs values
func (c CopyGate) EvalManyVL(res, vLs []fr.Element, vR *fr.Element) {
	copy(res, vLs)
}

// Degrees returns the degrees of the gate on hL, hR and hPrime
func (c CopyGate) Degrees() (degHL, degHR, degHPrime int) {
	return 1, 0, 1
}

// CipherGate cipher gate returns vL + (vR + c)^7
type CipherGate struct {
	Ark fr.Element
}

// NewCipherGate construct a new cipher gate given an ark
func NewCipherGate(ark fr.Element) *CipherGate {
	return &CipherGate{Ark: ark}
}

// ID returns the id of the cipher gate and print the ark as well
func (c *CipherGate) ID() string { return fmt.Sprintf("CipherGate-%v", c.Ark.String()) }

// Eval returns vL + (vR + c)^7
func (c *CipherGate) Eval(res, vL, vR *fr.Element) {
	// tmp = vR + Ark
	var tmp fr.Element
	tmp.Add(vR, &c.Ark)
	// res = tmp^7
	res.Square(&tmp)
	res.Mul(res, &tmp)
	res.Square(res)
	res.Mul(res, &tmp)
	// Then add vL
	res.Add(res, vL)
}

// GnarkEval performs the cipher operation on gnark variables
func (c *CipherGate) GnarkEval(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
	tmp := cs.Add(vR, cs.Constant(c.Ark))
	cipher := cs.Mul(tmp, tmp)
	cipher = cs.Mul(cipher, tmp)
	cipher = cs.Mul(cipher, cipher)
	cipher = cs.Mul(cipher, tmp)
	return cs.Add(cipher, vL)
}

// EvalManyVR performs cipher evaluations of many vRs values by one vL value
// Nothing special to do here
func (c *CipherGate) EvalManyVR(res []fr.Element, vL *fr.Element, vRs []fr.Element) {
	var tmp fr.Element
	for i := 0; i < len(vRs); i++ {
		// tmp = vR + Ark
		tmp.Add(&vRs[i], &c.Ark)
		// res = tmp^7
		res[i].Square(&tmp)
		res[i].Mul(&res[i], &tmp)
		res[i].Square(&res[i])
		res[i].Mul(&res[i], &tmp)
		// Then add vL
		res[i].Add(&res[i], vL)
	}
}

// EvalManyVL performs an element-wise cipher of many vLs values by one vR
// This one is optimized to only do the vL exponentiation once
func (c *CipherGate) EvalManyVL(res, vLs []fr.Element, vR *fr.Element) {
	// tmp = vR + Ark
	var tmp, right fr.Element
	tmp.Add(vR, &c.Ark)
	// right = tmp^7
	right.Square(&tmp)
	right.Mul(&right, &tmp)
	right.Square(&right)
	right.Mul(&right, &tmp)

	for i := 0; i < len(vLs); i++ {
		res[i].Add(&right, &vLs[i])
	}
}

// Degrees returns the degrees of the gate on hL, hR and hPrime
func (c *CipherGate) Degrees() (degHL, degHR, degHPrime int) {
	return 1, 7, 7
}


<|start_filename|>circuit/circuit.go<|end_filename|>
package circuit

import (
	"sync"

	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"

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

// Circuit contains all the statical informations necessary to
// describe a GKR circuit.
type Circuit struct {
	Layers []Layer
}

// Assignment gathers all the values representing the steps of
// computations being proved by GKR
type Assignment struct {
	Values [][][]fr.Element
}

// NewCircuit construct a new circuit object
func NewCircuit(
	wiring [][]Wire,
) Circuit {
	layers := make([]Layer, len(wiring))
	for i := range layers {
		layers[i] = NewLayer(wiring[i])
	}
	return Circuit{
		Layers: layers,
	}
}

// Assign returns a complete assignment from a vector of inputs
func (c *Circuit) Assign(inputs [][]fr.Element, nCore int) Assignment {
	assignment := make([][][]fr.Element, len(c.Layers)+1)
	// The first layer of assignment is equal to the inputs
	assignment[0] = inputs
	// We use the transition funcs to create the next layers
	// one after the other
	for i, layer := range c.Layers {
		assignment[i+1] = layer.Evaluate(assignment[i], nCore)
	}
	return Assignment{Values: assignment}
}

// LayerAsBKTWithCopy creates a deep-copy of a given layer of the assignment
func (a *Assignment) LayerAsBKTWithCopy(layer, nCore int) []polynomial.BookKeepingTable {
	res := make([]polynomial.BookKeepingTable, len(a.Values[layer]))
	var wg sync.WaitGroup
	wg.Add(len(res))
	semaphore := common.NewSemaphore(nCore)
	defer semaphore.Close()
	// Deep-copies the values of the assignment
	for i, tab := range a.Values[layer] {
		go func(i int, tab []fr.Element) {
			semaphore.Acquire()
			res[i].Table = make([]fr.Element, len(tab))
			copy(res[i].Table, tab)
			semaphore.Release()
			wg.Done()
		}(i, tab)
	}
	wg.Wait()
	return res
}

// LayerAsBKTNoCopy creates a deep-copy of a given layer of the assignment
func (a *Assignment) LayerAsBKTNoCopy(layer int) []polynomial.BookKeepingTable {
	res := make([]polynomial.BookKeepingTable, len(a.Values[layer]))
	// Copies the headers of the slices
	for i, tab := range a.Values[layer] {
		res[i] = polynomial.NewBookKeepingTable(tab)
	}
	return res
}


<|start_filename|>snark/polynomial/univariate_test.go<|end_filename|>
package polynomial

import (
	"testing"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
)

type univariateTestCircuit struct {
	Poly     Univariate
	ZnO      frontend.Variable // for testing purposes only
	Expected frontend.Variable // for testing purposes only
}

func (pc *univariateTestCircuit) Define(curveID ecc.ID, cs *frontend.ConstraintSystem) error {

	zno := pc.Poly.ZeroAndOne(cs)
	x := cs.Constant(5)
	PAtX := pc.Poly.Eval(cs, x)

	cs.AssertIsEqual(zno, pc.ZnO)
	cs.AssertIsEqual(PAtX, pc.Expected)

	return nil
}

func TestUnivariate(t *testing.T) {

	degree := 3
	var pc univariateTestCircuit
	pc.Poly = AllocateUnivariate(degree)
	r1cs, err := frontend.Compile(ecc.BN254, backend.GROTH16, &pc)
	assert := groth16.NewAssert(t)
	assert.NoError(err)

	var witness univariateTestCircuit
	witness.Poly.Coefficients = make([]frontend.Variable, 4)
	// witness <---> X^3 + 2X^2 + 3X + 4
	witness.Poly.Coefficients[0].Assign(4)
	witness.Poly.Coefficients[1].Assign(3)
	witness.Poly.Coefficients[2].Assign(2)
	witness.Poly.Coefficients[3].Assign(1)
	witness.ZnO.Assign(14)
	witness.Expected.Assign(194)

	assert.ProverSucceeded(r1cs, &witness)

}


<|start_filename|>hash/poseidon.go<|end_filename|>
package hash

import (
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
)

// PoseidonT2 is a hasher with T = 2
var PoseidonT2 PoseidonHasher

// PoseidonT4 is a hasher with T = 4
var PoseidonT4 PoseidonHasher

// PoseidonT8 is a hasher with T = 8
var PoseidonT8 PoseidonHasher

// The parameters are set according to
// https://eprint.iacr.org/2020/179.pdf
func initPoseidon() {
	PoseidonT2 = newPoseidonHasher(2, 8, 82)
	PoseidonT4 = newPoseidonHasher(4, 8, 83)
	PoseidonT8 = newPoseidonHasher(8, 8, 84)
}

// PoseidonHasher contains all the parameters to specify a poseidon hash function
type PoseidonHasher struct {
	t        int // size of Cauchy matrix
	cauchy   [][]fr.Element
	nRoundsF int
	nRoundsP int
}

// NewPoseidonHasher generates the parameters to run poseidon
func newPoseidonHasher(t, nRoundsF, nRoundsP int) PoseidonHasher {
	return PoseidonHasher{
		t:        t,
		nRoundsF: nRoundsF,
		nRoundsP: nRoundsP,
		cauchy:   GenerateMDSMatrix(t),
	}
}

// Hash hashes a full message
func (p *PoseidonHasher) Hash(msg []fr.Element) fr.Element {
	state := make([]fr.Element, p.t)

	for i := 0; i < len(msg); i += p.t {
		block := make([]fr.Element, p.t)
		if i+p.t >= len(msg) {
			// Only zero-pad the input
			for j, w := range msg[i:] {
				block[j] = w
			}
		} else {
			// Take a full chunk
			for j, w := range msg[i : i+p.t] {
				block[j] = w
			}
		}
		p.Update(state, block)
	}

	return state[0]
}

// Update uses the poseidon permutation in a Miyaguchi-Preenel
// construction to create the hash function.
// https://en.wikipedia.org/wiki/One-way_compression_function#Miyaguchi.E2.80.93Preneel
func (p *PoseidonHasher) Update(state, block []fr.Element) {

	// Deep-copies the state
	oldState := append([]fr.Element{}, state...)

	// Runs the cipher
	for i := 0; i < p.nRoundsF; i++ {
		AddArkAndKeysInplace(state, block, Arks[i])
		FullRoundInPlace(state)
		state = MatrixMultiplication(p.cauchy, state)
	}

	for i := p.nRoundsF; i < p.nRoundsF+p.nRoundsP; i++ {
		AddArkAndKeysInplace(state, block, Arks[i])
		PartialRoundInplace(state)
		state = MatrixMultiplication(p.cauchy, state)
	}

	for i := p.nRoundsF + p.nRoundsP; i < 2*p.nRoundsF+p.nRoundsP; i++ {
		AddArkAndKeysInplace(state, block, Arks[i])
		FullRoundInPlace(state)
		state = MatrixMultiplication(p.cauchy, state)
	}

	// Recombine with the old state
	for i := range state {
		state[i].Add(&state[i], &oldState[i])
		state[i].Add(&state[i], &block[i])
	}
}

// GenerateMDSMatrix returns the MDS matrix for a given size
func GenerateMDSMatrix(t int) [][]fr.Element {
	result := make([][]fr.Element, t)
	for i := range result {
		result[i] = make([]fr.Element, t)
		for j := range result[i] {
			result[i][j].Set(&xArr[i])
			result[i][j].Add(&result[i][j], &yArr[j])
			result[i][j].Inverse(&result[i][j])
		}
	}
	return result
}

// MatrixMultiplication by a vector
// The dimensions are mat[k][n] * vec[n] = res[k]
func MatrixMultiplication(mat [][]fr.Element, vec []fr.Element) []fr.Element {
	res := make([]fr.Element, len(mat))
	var tmp fr.Element
	for i, col := range mat {
		for j, el := range col {
			tmp.Set(&vec[j])
			tmp.Mul(&tmp, &el)
			res[i].Add(&res[i], &tmp)
		}
	}
	return res
}

// SBoxInplace computes x^7 in-place
func SBoxInplace(x *fr.Element) {
	tmp := *x
	x.Square(x)
	x.Mul(x, &tmp)
	x.Square(x)
	x.Mul(x, &tmp)
}

// FullRoundInPlace applies the SBox on all entries
// of the state
func FullRoundInPlace(state []fr.Element) {
	for i := range state {
		SBoxInplace(&state[i])
	}
}

// AddArkAndKeysInplace adds the
func AddArkAndKeysInplace(state []fr.Element, keys []fr.Element, ark fr.Element) {
	for i := range state {
		state[i].Add(&state[i], &keys[i])
		state[i].Add(&state[i], &ark)
	}
}

// PartialRoundInplace applies the SBox on the first entry
func PartialRoundInplace(state []fr.Element) {
	SBoxInplace(&state[0])
}


<|start_filename|>snark/gkr/gate.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/consensys/gnark/frontend"
)

// Gate evaluate either a cipherGate or a copy gate
type Gate func(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable

// CipherGate returns a cipher gate
func CipherGate(ark fr.Element) Gate {
	return func(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
		tmp := cs.Add(vR, cs.Constant(ark))
		cipher := cs.Mul(tmp, tmp)
		cipher = cs.Mul(cipher, tmp)
		cipher = cs.Mul(cipher, cipher)
		cipher = cs.Mul(cipher, tmp)
		return cs.Add(cipher, vL)
	}
}

// CopyGate returns a copy gate
func CopyGate() Gate {
	return func(cs *frontend.ConstraintSystem, vL, vR frontend.Variable) frontend.Variable {
		return vL
	}
}


<|start_filename|>common/semaphore.go<|end_filename|>
package common

// Semaphore allows N threads to acquire at the same time
type Semaphore struct {
	channel chan struct{}
}

// NewSemaphore constructs a new semaphore that is initialized
func NewSemaphore(n int) Semaphore {
	res := Semaphore{channel: make(chan struct{}, n)}
	for i := 0; i < n; i++ {
		res.channel <- struct{}{}
	}
	return res
}

// Close kills the semaphore
func (s *Semaphore) Close() {
	close(s.channel)
}

// Acquire wait for the semaphore to be freed
func (s *Semaphore) Acquire() {
	<-s.channel
}

// Release frees the semaphore
func (s *Semaphore) Release() {
	s.channel <- struct{}{}
}


<|start_filename|>snark/gkr/mimc.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gkr-mimc/hash"
	"github.com/consensys/gkr-mimc/snark/polynomial"

	"github.com/consensys/gnark/frontend"
)

// CreateMimcCircuit creates a GKR circuit for Mimc
func CreateMimcCircuit() Circuit {
	nLayers := hash.MimcRounds
	layers := make([]Layer, hash.MimcRounds)

	for i := 0; i < nLayers-1; i++ {
		layers[i] = Layer{
			Gates: []Gate{
				CipherGate(hash.Arks[i]),
				CopyGate(),
			},
			StaticTable: []StaticTableGenerator{
				GetCipherTable,
				GetCopyTable,
			},
			BG:        1,
			DegHL:     2,
			DegHR:     8,
			DegHPrime: 8,
		}
	}

	layers[nLayers-1] = Layer{
		Gates:       []Gate{CipherGate(hash.Arks[nLayers-1])},
		StaticTable: []StaticTableGenerator{GetFinalCipherTable},
		BG:          1,
		DegHL:       2,
		DegHR:       8,
		DegHPrime:   8,
	}

	return Circuit{
		Layers: layers,
		BGOut:  0,
	}

}

// GetCopyTable returns a prefolded copy table for the intermediate rounds
func GetCopyTable(cs *frontend.ConstraintSystem, Q []frontend.Variable) polynomial.MultilinearByValues {
	return polynomial.NewMultilinearByValues([]frontend.Variable{
		cs.Constant(0),
		cs.Constant(0),
		Q[0],
		cs.Constant(0),
	})
}

// GetCipherTable returns a prefolded cipher table for the intermediate rounds
func GetCipherTable(cs *frontend.ConstraintSystem, Q []frontend.Variable) polynomial.MultilinearByValues {
	return polynomial.NewMultilinearByValues([]frontend.Variable{
		cs.Constant(0),
		cs.Constant(0),
		cs.Sub(1, Q[0]),
		cs.Constant(0),
	})
}

// GetFinalCipherTable returns a prefolded cipher table for the intermediate rounds
func GetFinalCipherTable(cs *frontend.ConstraintSystem, Q []frontend.Variable) polynomial.MultilinearByValues {
	return polynomial.NewMultilinearByValues([]frontend.Variable{
		cs.Constant(0),
		cs.Constant(0),
		cs.Constant(1),
		cs.Constant(0),
	})
}


<|start_filename|>hash/mimc.go<|end_filename|>
package hash

import (
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
)

// MimcRounds is the number of rounds for the Mimc function
const MimcRounds int = 91

// MimcHash returns the hash of a slice of field element
func MimcHash(input []fr.Element) fr.Element {
	// The state is initialized to zero
	var state fr.Element
	for _, x := range input {
		MimcUpdateInplace(&state, x)
	}
	return state
}

// MimcUpdateInplace performs a state update using the Mimc permutation
// Using Miyaguchi-Preenel
func MimcUpdateInplace(state *fr.Element, block fr.Element) {
	oldState := *state
	MimcPermutationInPlace(state, block)
	state.Add(state, &oldState)
	state.Add(state, &block)
}

// MimcPermutationInPlace applies the mimc permutation in place
// In the Miyaguchi-Preenel construct, the state is used as the key of a cipher function
// and the message to hash is set as the plaintext of the cipher
func MimcPermutationInPlace(state *fr.Element, block fr.Element) {
	for i := 0; i < MimcRounds; i++ {
		block.Add(&block, state)
		block.Add(&block, &Arks[i])
		SBoxInplace(&block)
	}
	// Re-add the state (key) to the block and put the result in the state
	// to update the state
	state.Add(state, &block)
}


<|start_filename|>snark/sumcheck/sumcheck_test.go<|end_filename|>
package sumcheck

import (
	"github.com/consensys/gkr-mimc/sumcheck"
	"testing"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
)

type SumcheckCircuit struct {
	InitialClaim   frontend.Variable
	Proof          Proof
	ExpectedQL     []frontend.Variable
	ExpectedQR     []frontend.Variable
	ExpectedQPrime []frontend.Variable
}

func AllocateSumcheckCircuit(bN, bG, degHL, degHR, degHPrime int) SumcheckCircuit {
	return SumcheckCircuit{
		Proof:          AllocateProof(bN, bG, degHL, degHR, degHPrime),
		ExpectedQL:     make([]frontend.Variable, bG),
		ExpectedQR:     make([]frontend.Variable, bG),
		ExpectedQPrime: make([]frontend.Variable, bN),
	}
}

func (scc *SumcheckCircuit) Define(curveID ecc.ID, cs *frontend.ConstraintSystem) error {
	hR, hL, hPrime, _ := scc.Proof.AssertValid(cs, scc.InitialClaim, 1)
	for i := range hR {
		cs.AssertIsEqual(hL[i], scc.ExpectedQL[i])
		cs.AssertIsEqual(hR[i], scc.ExpectedQR[i])
	}

	for i := range hPrime {
		cs.AssertIsEqual(hPrime[i], scc.ExpectedQPrime[i])
	}

	return nil
}

func TestSumcheckCircuit(t *testing.T) {

	var bN, bG, degHL, degHR, degHPrime = 4, 1, 2, 8, 8
	assert := groth16.NewAssert(t)

	// Attempts to compile the circuit
	scc := AllocateSumcheckCircuit(bN, bG, degHL, degHR, degHPrime)
	r1cs, err := frontend.Compile(ecc.BN254, backend.GROTH16, &scc)
	assert.NoError(err)

	// Runs a test sumcheck prover to get witness values
	scProver := sumcheck.InitializeProverForTests(bN)
	firstClaim := scProver.GetClaim()
	scVer := sumcheck.Verifier{}
	proof, expectedQPrime, expectedQR, expectedQL, _ := scProver.Prove()
	valid, _, _, _, _ := scVer.Verify(firstClaim, proof, bN, bG)

	assert.True(valid, "Sumcheck verifier refused")

	witness := AllocateSumcheckCircuit(bN, bG, degHL, degHR, degHPrime)
	witness.InitialClaim.Assign(firstClaim)
	witness.Proof.Assign(proof)

	for i := range expectedQL {
		witness.ExpectedQL[i].Assign(expectedQL[i])
		witness.ExpectedQR[i].Assign(expectedQR[i])

	}

	for i := range expectedQPrime {
		witness.ExpectedQPrime[i].Assign(expectedQPrime[i])
	}

	assert.SolvingSucceeded(r1cs, &witness)
	assert.ProverSucceeded(r1cs, &witness)
}


<|start_filename|>hash/hash_test.go<|end_filename|>
package hash

import (
	"testing"

	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/stretchr/testify/assert"
)

func TestHashes(t *testing.T) {
	inputs := make([]fr.Element, 100)
	PoseidonT2.Hash(inputs)
	PoseidonT4.Hash(inputs)
	PoseidonT8.Hash(inputs)
	GMimcT2.Hash(inputs)
	GMimcT4.Hash(inputs)
	GMimcT8.Hash(inputs)
	MimcHash(inputs)
}

func TestMimcCase(t *testing.T) {
	var x, expectedY fr.Element
	x.SetString("12")
	y := MimcHash([]fr.Element{x})
	expectedY.SetString("1808205620575546259657963589762746470347087906694759866517376279978241663265")
	assert.Equal(t, y, expectedY, "Got %v", y.String())
}


<|start_filename|>polynomial/lagrange.go<|end_filename|>
package polynomial

import (
	"github.com/consensys/gkr-mimc/common"

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

func init() {
	initLagrangePolynomials()
}

// GetLagrangePolynomial returns a precalculated array representing the univariate
// lagrange polynomials on domainSize.
func GetLagrangePolynomial(domainSize int) [][]fr.Element {
	return lagrangePolynomials[domainSize]
}

var lagrangePolynomials [][][]fr.Element

const maxDomainSize int = 12

func initLagrangePolynomials() {
	lagrangePolynomials = make([][][]fr.Element, maxDomainSize+1)
	for i := 0; i < maxDomainSize+1; i++ {
		lagrangePolynomials[i] = LagrangeCoefficient(i)
	}
}

// EvaluatePolynomial evaluates a polynomial from its coefficients
func EvaluatePolynomial(coeffs []fr.Element, x fr.Element) fr.Element {
	var result fr.Element
	result.Set(&coeffs[len(coeffs)-1])
	for i := len(coeffs) - 2; i >= 0; i-- {
		result.Mul(&result, &x)
		result.Add(&result, &coeffs[i])
	}
	return result
}

// LagrangeCoefficient returns the matrix of Lagrange polynomials for the domain [[0; n - 1]]
func LagrangeCoefficient(domainSize int) [][]fr.Element {
	// Declare the binomials
	binomials := make([][2]fr.Element, domainSize)
	for i := uint64(0); i < uint64(domainSize); i++ {
		var interceipts fr.Element
		interceipts.SetUint64(i)
		binomials[i][0].Neg(&interceipts)
		binomials[i][1].SetOne()
	}

	result := make([][]fr.Element, domainSize)

	for l := 0; l < domainSize; l++ {
		// Each iteration computes the the l-th Lagrange polynomial
		// on range [0, domainSize-1]
		accumulator := make([]fr.Element, domainSize)
		accumulator[0].SetOne()
		var tmp fr.Element

		for i := 0; i < domainSize; i++ {
			if i == l {
				// Skip the monomial
				continue
			}
			// Computes X(X-1)(X-2)..(X-i)..(X-domainSize-1) for i != l
			updated := make([]fr.Element, domainSize)
			for j := 0; j < domainSize; j++ {
				for k := 0; k < common.Min(2, domainSize-j); k++ {
					tmp.Set(&accumulator[j])
					tmp.Mul(&tmp, &binomials[i][k])
					updated[j+k].Add(&updated[j+k], &tmp)
				}
			}
			accumulator = updated
		}
		// Normalize the polynomial to have P(l) = 1.
		// Order to do so, we compute normalizationFactor = P(l),
		// and divide each coefficent by normalizationFactor
		var lFieldElement fr.Element
		lFieldElement.SetUint64(uint64(l))
		normalizationFactor := EvaluatePolynomial(accumulator, lFieldElement)
		// Now divide all coefficients
		normalizationFactor.Inverse(&normalizationFactor)
		for i := range accumulator {
			accumulator[i].Mul(&accumulator[i], &normalizationFactor)
		}
		result[l] = accumulator
	}

	return result
}

// InterpolateOnRange performs the interpolation of the given list of elements
// On the range [0, 1,..., len(values) - 1]
func InterpolateOnRange(values []fr.Element) []fr.Element {
	nEvals := len(values)
	lagrange := GetLagrangePolynomial(nEvals)
	result := make([]fr.Element, nEvals)
	var tmp fr.Element

	for i, value := range values {
		for j, lagrangeCoeff := range lagrange[i] {
			tmp.Set(&lagrangeCoeff)
			tmp.Mul(&tmp, &value)
			result[j].Add(&result[j], &tmp)
		}
	}

	return result
}


<|start_filename|>snark/polynomial/multilinear.go<|end_filename|>
package polynomial

import (
	"fmt"

	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
)

// MultilinearByValues represents a multilinear polynomial by its values
type MultilinearByValues struct {
	Table []frontend.Variable
}

// AllocateMultilinear returns an empty multilinear with a given size
func AllocateMultilinear(nVars int) MultilinearByValues {
	size := 1 << nVars
	return NewMultilinearByValues(make([]frontend.Variable, size))
}

// Assign a preallocated Multilinear with the given values
func (m *MultilinearByValues) Assign(values []interface{}) {
	if len(values) != len(m.Table) {
		panic(fmt.Sprintf("Inconsistent assignment expected len %v but got %v", len(m.Table), len(values)))
	}
	for i, c := range values {
		m.Table[i].Assign(c)
	}
}

// AssignFromChunkedBKT a preallocated Multilinear with the given values
func (m *MultilinearByValues) AssignFromChunkedBKT(values [][]fr.Element) {
	nChunks := len(values)
	for b := range values {
		for i := range values[b] {
			m.Table[b+i*nChunks].Assign(values[b][i])
		}
	}
}

// NewMultilinearByValues is the default constructor
func NewMultilinearByValues(Table []frontend.Variable) MultilinearByValues {
	return MultilinearByValues{Table: Table}
}

// DeepCopy returns a deepcopied value
func (m MultilinearByValues) DeepCopy() MultilinearByValues {
	tableDC := make([]frontend.Variable, len(m.Table))
	copy(tableDC, m.Table)
	return NewMultilinearByValues(tableDC)
}

// Fold partially evaluates the polynomial on one of the variable
func (m *MultilinearByValues) Fold(cs *frontend.ConstraintSystem, x frontend.Variable) {
	k := len(m.Table) / 2
	for i := 0; i < k; i++ {
		tmpLinExp := cs.Sub(m.Table[i+k], m.Table[i])
		// cs.LinearExpression(
		// 	cs.Term(m.Table[i+k], big.NewInt(1)),
		// 	cs.Term(m.Table[i], big.NewInt(-1)),
		// )
		tmp := cs.Mul(tmpLinExp, x)
		// Ideally we replace this by a r1c.LinearExpression too ...
		m.Table[i] = cs.Add(m.Table[i], tmp)
	}
	m.Table = m.Table[:k]
}

// Eval the multilinear polynomial
func (m MultilinearByValues) Eval(cs *frontend.ConstraintSystem, xs []frontend.Variable) frontend.Variable {
	f := m.DeepCopy()
	for _, x := range xs {
		// Repeatedly fold the table
		f.Fold(cs, x)
	}
	return f.Table[0]
}

// EvalMixed the multilinear polynomial
// We must have len(qL) == len(qR)
// And len(Table) = 2 ** len(qL) + len(qPrime)
func (m MultilinearByValues) EvalMixed(
	cs *frontend.ConstraintSystem,
	qL, qR, qPrime []frontend.Variable,
) (vL, vR frontend.Variable) {
	// The function proceeds by putting in common the evaluations over qPrime
	// to save a maximum of space
	nChunks := 1 << len(qL)
	chunkSize := len(m.Table) / nChunks
	intermediateTable := make([]frontend.Variable, nChunks)

	// Evaluate each portion of the table on qPrime. For different values of q.
	for i := range intermediateTable {
		multlin := NewMultilinearByValues(m.Table[i*chunkSize : (i+1)*chunkSize])
		intermediateTable[i] = multlin.Eval(cs, qPrime)
	}
	intermediatePoly := NewMultilinearByValues(intermediateTable)
	return intermediatePoly.Eval(cs, qL), intermediatePoly.Eval(cs, qR)
}


<|start_filename|>sumcheck/prover.go<|end_filename|>
package sumcheck

import (
	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"

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

// Proof is the object produced by the prover
type Proof struct {
	PolyCoeffs [][]fr.Element
}

// SingleThreadedProver computes the
type SingleThreadedProver struct {
	// Contains the values of the previous layer
	vL polynomial.BookKeepingTable
	vR polynomial.BookKeepingTable
	// Contains the static tables defining the circuit structure
	eq           polynomial.BookKeepingTable
	gates        []circuit.Gate
	staticTables []polynomial.BookKeepingTable
	// Degrees for the differents variables
	degreeHL     int
	degreeHR     int
	degreeHPrime int
}

// NewSingleThreadedProver constructs a new prover
func NewSingleThreadedProver(
	vL polynomial.BookKeepingTable,
	vR polynomial.BookKeepingTable,
	eq polynomial.BookKeepingTable,
	gates []circuit.Gate,
	staticTables []polynomial.BookKeepingTable,
) SingleThreadedProver {
	// Auto-computes the degree on each variables
	degreeHL, degreeHR, degreeHPrime := 0, 0, 0
	for _, gate := range gates {
		dL, dR, dPrime := gate.Degrees()
		degreeHL = common.Max(degreeHL, dL)
		degreeHR = common.Max(degreeHR, dR)
		degreeHPrime = common.Max(degreeHPrime, dPrime)
	}
	return SingleThreadedProver{
		vL:           vL,
		vR:           vR,
		eq:           eq,
		gates:        gates,
		staticTables: staticTables,
		degreeHL:     degreeHL + 1,
		degreeHR:     degreeHR + 1,
		degreeHPrime: degreeHPrime + 1,
	}
}

// Prove runs the prover of a sumcheck
func (p *SingleThreadedProver) Prove() (proof Proof, qPrime, qL, qR, finalClaims []fr.Element) {

	// Define usefull constants
	n := len(p.eq.Table)     // Number of subcircuit. Since we haven't fold on h' yet
	g := len(p.vR.Table) / n // SubCircuit size. Since we haven't fold on hR yet
	bN := common.Log2Ceil(n)
	bG := common.Log2Ceil(g)

	// Initialized the results
	proof.PolyCoeffs = make([][]fr.Element, bN+2*bG)
	qPrime = make([]fr.Element, bN)
	qL = make([]fr.Element, bG)
	qR = make([]fr.Element, bG)
	finalClaims = make([]fr.Element, 3+len(p.staticTables))

	// Run on hL
	for i := 0; i < bG; i++ {
		evals := p.GetEvalsOnHL()
		proof.PolyCoeffs[i] = polynomial.InterpolateOnRange(evals)
		r := common.GetChallenge(proof.PolyCoeffs[i])
		p.FoldHL(r)
		qL[i] = r
	}

	// Run on hR
	for i := bG; i < 2*bG; i++ {
		evals := p.GetEvalsOnHR()
		proof.PolyCoeffs[i] = polynomial.InterpolateOnRange(evals)
		r := common.GetChallenge(proof.PolyCoeffs[i])
		p.FoldHR(r)
		qR[i-bG] = r
	}

	// Run on hPrime
	for i := 2 * bG; i < bN+2*bG; i++ {
		evals := p.GetEvalsOnHPrime()
		proof.PolyCoeffs[i] = polynomial.InterpolateOnRange(evals)
		r := common.GetChallenge(proof.PolyCoeffs[i])
		p.FoldHPrime(r)
		qPrime[i-2*bG] = r
	}

	finalClaims[0] = p.vL.Table[0]
	finalClaims[1] = p.vR.Table[0]
	finalClaims[2] = p.eq.Table[0]
	for i, bkt := range p.staticTables {
		finalClaims[3+i] = bkt.Table[0]
	}

	return proof, qPrime, qL, qR, finalClaims
}

// FoldHL folds on the first variable of hR
func (p *SingleThreadedProver) FoldHL(r fr.Element) {
	for i := range p.staticTables {
		p.staticTables[i].Fold(r)
	}
	p.vL.Fold(r)
}

// FoldHR folds on the first variable of hR
func (p *SingleThreadedProver) FoldHR(r fr.Element) {
	for i := range p.staticTables {
		p.staticTables[i].Fold(r)
	}
	p.vR.Fold(r)
}

// FoldHPrime folds on the first variable of Eq
func (p *SingleThreadedProver) FoldHPrime(r fr.Element) {
	p.vR.Fold(r)
	p.vL.Fold(r)
	p.eq.Fold(r)
}


<|start_filename|>snark/hash/mimc.go<|end_filename|>
package hash

import (
	"github.com/consensys/gkr-mimc/hash"

	"github.com/consensys/gnark/frontend"
)

// MimcHash returns the result of the hashing function
func MimcHash(cs *frontend.ConstraintSystem, stream ...frontend.Variable) frontend.Variable {
	state := cs.Constant(0)
	for _, m := range stream {
		newM := m
		for i := 0; i < hash.MimcRounds; i++ {
			newM = cs.Add(newM, state)
			newM = cs.Add(newM, cs.Constant(hash.Arks[i]))
			// Raise to the power 7
			tmp := cs.Mul(newM, newM) // ^2
			tmp = cs.Mul(newM, tmp)   // ^3
			tmp = cs.Mul(tmp, tmp)    // ^6
			newM = cs.Mul(newM, tmp)  // ^7
		}
		state = cs.Add(state, newM, state, m)
	}
	return state
}


<|start_filename|>hash/ark.go<|end_filename|>
package hash

import "github.com/consensys/gnark-crypto/ecc/bn254/fr"

// 100 random strings of x's and y's smaller than q
// generated in Python using
// str(random.randrange(21888242871839275222246405745257275088548364400416034343698204186575808495617))
// Naturally, they only works if we use ecc/bn254
var xArr []fr.Element
var yArr []fr.Element

// Arks contains the round constants used by gMimc
var Arks []fr.Element

func initArk() {

	xArr = make([]fr.Element, 100)
	yArr = make([]fr.Element, 100)
	Arks = make([]fr.Element, 100)

	// Set the values of xArr
	for i, x := range [...]string{
		"20935598419934535773939197275086671883976426238465984892689893274776109706840",
		"19995897090389691161372090451896659673911988660285271218219666866949687188766",
		"6544978823936796530307517047600780472974960393678464677682762811474267306764",
		"13423806261013761719286154447241277236171190620841146940924235299828216919004",
		"483036459520899251433481070174077337588234874789277590744459238550542022336",
		"11834122008725238397540798432599519064159958632173342040922104816182977650323",
		"6214250652825909336042102302914495542350963467874575855196090802530598798684",
		"7170726223133665141339252286212434611716644939495742319100725465588758577975",
		"3628752144011358518780390633429771997829076043796856962918680101301334326717",
		"10995056073584958662633592981244351787463906518240783240839224906624462658946",
		"10316136354139206944774094995168509765583756998417835440724193449385724904064",
		"6887293571249137951954974829583961948681874052171040521689627599170432187821",
		"17679014255108003658018203734964304787939319117285088271374270937340979331088",
		"4248252868936221819819290432848672487864423222808359880150462211602494495796",
		"10838576758032918715215191218446338417881585877259434456182478933129676952115",
		"753652442023272502362984997608685353764283209436968416683175270126230919486",
		"17745848830945769523932902637022183346001315979559375020608322369317158742340",
		"15048113314350148976574068237122414221875489926515297088305374878755157475050",
		"9491283014185515531244157897882648088184249254485820722661277551261599129642",
		"4258129065487469195892729988726472140786148309087149042478972442852967621345",
		"5111992792738425366152826074931113105810075868173875109087887872181607527888",
		"17207570210536169229421619009051443126781777633310289161609677098462635375221",
		"11676857416455659283983679396450067066140186418683989409364053576635898614423",
		"17578181423085285483685548800623294414373345823336170149312376005897219810923",
		"16629480769556236124982722400255457396770056235490451205148220949109249575367",
		"8839117604736565297825617688776310968162145135592273200563883313600739705885",
		"1735306411626188875687496234040719696454614787672232638784102468564002525311",
		"1062690232563009764870609669688237582570790433844825729996364011137988522972",
		"10056158341775369056001372101480180671326250547841758558233836566253007463970",
		"12861676007242550257747460291682219623619046064334768768792486866981698984069",
		"10364293972625138632177507866607968975753973525749205969026186608034214999319",
		"3381310948007105111429534263163256529484284505313401397404454363021417678968",
		"5391644308855774040931138482213992529012013176810874072239316963239013418901",
		"5739902267984637424546093272789773631580642499147923310270611599926582772083",
		"20806058531191007742886071003337288700928126171889422302290828657325840002837",
		"1953912345352260990400998391590986884132317738887679700094700754944948270710",
		"6334107054196823364302483562051891503925658093315615419922191758990899370338",
		"14436872750302522612547342263479874128706597085400185002907467694318996568975",
		"7694649897497530249728485136604371802655316385667275552509740182346397459671",
		"19618789529866917206069877900825601316878403452146176103972243181682070108596",
		"2021370341346862593327202593746514936950566619994961739175029081766474759734",
		"8897565274181604271438529286082177443144026336582705290182549375856364873271",
		"2679449823911283247300632056535751191249091461631889726903592697866653888173",
		"20129895186588343211831804279732468237555926468631283725949859368323156032328",
		"13600013317168617656421359748934876309106612346394267276197743245554826828044",
		"4187390986581800164301365868618807900222521766711295721325192212473641955078",
		"17190735820869638808784313330525115090358120278752459902349090601764659379986",
		"7860693206750828547022882524196397915704308902872703437413899492234638169950",
		"263587684044448289719429684465217979694231526668589674423417665681979978672",
		"12954057757246385431776838652377320956920815107618502944864994612010557053917",
		"10625755329183920915841453005657772997523286066913835639471907499702448594328",
		"16175361036106772273053984695425631085622758695469708623031329115839090608091",
		"7924643236665918037726545377739468766171745922844271871159360253789090651662",
		"14745943428673947439440436509001772198518090233941952319627228181057581147947",
		"5200110725015095224900900401491425448872414730842690281649501292204903596258",
		"14844515653194611243517183917188743040195272988340890757893132638115648419361",
		"18284597462748499391597422334682707085291493485018550859047712392990049612585",
		"3312757768539360866544546712719153939543130555858880701206518185577866044127",
		"11494491995355104110478447591843802527037727080288399836711586597617930772246",
		"16270250187260095576918281103126175126400434232898666530090704942769826010320",
		"8680260951893149973525640389344225710096038075121190733144198459306153458739",
		"9081613210888370454812488310849186028647077567446266762039801934739912763318",
		"10956462511589282027775497802647259672358929202388777534828986598277518510940",
		"13370913492321313472348616113510256836815142270399966460977455242823363372922",
		"13435079246781743384843720328820403206129294071479578706749467351260674442286",
		"18388272646089823700512532610933652257193724639728928401647812388564816035072",
		"4824438688649902010762908031802598452324416083897401196317026545608670128170",
		"16639475199568140702564184960648997909998564302491101536025960422620186396737",
		"9698386349195157718988480221578364140594852561835995069755014032700861137184",
		"184730549537418551827887128923167602075009782174981658579083378380561403166",
		"5624105519689291645919891509613328425168570010590845601140173844081019857980",
		"7450716761741930677175278400352080652394237300409198906696001754049674530245",
		"5371470382394845195824877337361558168063810572261588627438109543648132090378",
		"15916615953942210085265747284146959402033948678792411724876166650637967413112",
		"17530212325321880583076096442221773546008840067636999101801153102182082050803",
		"3130575017506563486379643269706590265437956588003605259886854795479035081161",
		"21602532357228503237027076470426344915762613291631264074837835884431881157704",
		"18175480348381516617958634462144151473385342682669306435382223997224577647885",
		"11701690718026895346824771844850592436088535534550764165534456114515752003199",
		"12269837419960548249728971163700132941456486865685239188300851998035846614389",
		"2400291724637078032895220206931668428857913251539696626122517390770119598631",
		"3654343830276165868300300278633476909969601631321485759949471116592609195616",
		"17235144671932366808828254897445223424297026530200129204235663184234890499384",
		"20506680052641797427690296883223523332483431790083362449544093134410861331851",
		"17331504954904950505856350254389798927000070544870687548919051531188198807950",
		"6804161102614327828976510754243929743759943219061856517156987357363944829891",
		"2317479567028904415200602472561912467973945115634988693464542048750799278467",
		"18090469109511824152179049458653009408110373299245056594039366425863625295848",
		"10089848084586654625732745860585123183877862273820914158173224863878469115856",
		"1395836226546105948872057125025556411270566848892612832821620203563889793940",
		"10721598754291822821503791097285933118105954737347233142637972326192311886410",
		"8359345204686797469951453420353417935055941782617632382536541727457473046091",
		"11837750283757807457455756860464208427747288399432375587762853620364480448031",
		"15301971233817766320695731507409466149968450661632089583616278484482700364566",
		"6117002297131317426052982382004995803437168289348556329802949005764517586689",
		"8903395600979830544130884370204757215790326174543487725690925685601847291516",
		"13790842991390267676149228422665487445151021796150434526967048103377183722083",
		"9035559823192678393011406366902457990596065627959572306182158186900207605358",
		"8655223615688285377345725376026753443683911514166015415235267767049944934264",
		"17186780836005891388812353377183471046567173005401842455526923306475002070709"} {

		xArr[i].SetString(x)
	}

	for i, y := range [...]string{
		"7889220331855942390152844458153232881279298126168020718835532394961205897587",
		"4107703593865508008152532058450894262094481424817058071600894405707215391652",
		"2981965480119979542849598348825849434223710590643429757794916099804474854278",
		"6510902050797677829384445736759731040248069172634739272245379909319626488073",
		"8522870073131781488016212969787534099137132628889578006129058741893408941181",
		"11232025606036473857746482629338463504030960124294186766713483778447938231338",
		"21108530142895439895654172761661150753777692245579682285942822684968978554433",
		"10464664817782197858046869676929914985501473844890126267436644424377450552963",
		"9556974973279526871831633641120260160779911188908156358772760560288666751418",
		"1241372567008212377746166279809965298086156428510111101318502387802761219670",
		"16965808995810370462626517202842630591642545143655935980600413775621762532203",
		"14081836386157266284725623730380606274635205225974409983914017720589945843700",
		"15717493831146887482628108329054911883169147273489756037945534099976070774027",
		"18593090576191442420050903576531433518340171805085928714205763484336633105309",
		"1180731836490206389102149955923245281301919815522901801411607002856506167445",
		"5630609659278558017493034142969725450091515674276376879425166022960595487458",
		"21148350670392926881733606141800108701428090781255797670919919442016299030656",
		"15981546030195995367874935019352512874790725250109867282199269312633699915629",
		"7128052015328083284771085073609010750898929158617766974896019800003730550665",
		"6454471518821978428632182821258703281716542043625557058657747082108395391128",
		"18414607559334082314582901653915199096740838481712022680971572855497532846606",
		"4183726831064928874612108256656246798198704604512003866935655552220421419091",
		"507109504624490978450119158894577498030885167514463224819635968665207473223",
		"4808945797743944532330222116938040860765125452102486515966197626781851453765",
		"596504558625166257059093301467659831107500064953902351961806116733248199902",
		"1891458151530095404569000804740697696724660679385944694286672437478907510222",
		"12427768852750863462657510524722931983002850806185662441399170494087988656133",
		"12524602396618143105360965068865400589520832232935398577200379636653421496829",
		"10317176319397026634788809540621588848523541533718318733088702546661989262007",
		"1580596918288326863348722923866523000423264136344986653906336202047212027048",
		"6929143459167000241672166204183430630078568358548410719216285168231414683031",
		"10173256998300402553059050850081131439790068458053436588904913588514358470417",
		"9394145954207241148089853874036143168290380165365020395840910959745476073307",
		"13135390516961959054404413834161737161633928206137140011709268875521052233737",
		"12564350986146389941548491828894587312126483111975633109578712321107060383752",
		"1376491500521760150709492907973860555502715251541536838923266365618931406830",
		"8330775466866774738520407826351455126792841542039504412287605575890891747192",
		"8701576500767456261196164973750281031375892213475189335508532808123885067373",
		"16030142974555072707224309501362306430498788900149770180489521885630856377412",
		"17009220094833048875569562275612920502823608442311519823143885493886432964057",
		"13892080216395375698746931560259176937443429073833099032912514477312685821892",
		"16506694287892680248215076743413944982943234456066862229941320747945996007224",
		"2146811437233560927081428012168694503239422028313247606065184935643917198701",
		"3976229319282941213618566157961663797083392331239007102357688315789164689026",
		"16265853792125339173976869281862044762968348177681140751253978979029225522530",
		"14536954120167069032804365361277174806190017485542719968196592398476446880589",
		"18130529534729850307847740791671659268675809840961829951251618740400043870764",
		"14338057265451744973089233302821749361628076042233938369249313578334710172636",
		"19647231889458447797501252411484979149300154772839245739082606313523368528273",
		"20290678043421884446850792415593402100334966568961431979799398362492870969221",
		"7317436958444775238210672141424321168189998273907308555373508929036274633413",
		"9234435097223614475280721625079061129423171578705836489564699916616318385788",
		"5043619600308283288967791653456575033009808188361120667517975816759838969455",
		"14140513900676850412704402871686036764884759901882686270251696588209026919444",
		"2047328283108159420315021324644538293984254000489784806807390746008287238332",
		"5814411721062517079967797771653601251038338525707899051655286081361084310522",
		"6341197767327335307089281867928368166774239090958491991541758289006398667317",
		"9435915283405645088323234373771400328694005263909585840762615241219923218643",
		"13387243789278120572730908735093978599880866192723671043240558727701040341664",
		"14922064767941059898802635660418998171109153770248849019192832769461096614847",
		"5310923943943687463340194424403834984546129832719846198692245211825450770899",
		"851009140783773772512403908815075765128031465870408440630408820288915351355",
		"16697144460359443610930522567232593392051545681299784638301862128036778257566",
		"13669400607027362246135074818354681057821387163359271214689106684804762311417",
		"11141011258204312644640174523914553682780271756087434224860558481473358612359",
		"21043923187075097875733402828757809791382200839033414339963074884114432838476",
		"6774107457039269033319588169677712019543899952764388791605935463346806236879",
		"1431660334255478512185227973825287470142674265745864558177025018012516824381",
		"4695946731993663641084212622482542242369780629645938409682696955930468198734",
		"11288519124585374749333053504198144187726732736459576298847630122944821247265",
		"6627077352609406500088975387642304579089554332186025538151234828620879330636",
		"6482896472212179002872768082407898635388964565877980132395145112424810601918",
		"11001682864775142791446475972658780537632277347220793046046865329880263266846",
		"4277697710742254726581057339004435748034039969688558621456719243137568270875",
		"9481973311808249476289720795288455592483220972797058963968311255382356691809",
		"19971772865700811448218056122573347998664057348591672238129930017824012213547",
		"6110971391917572513629143113148458010047250352895271416327657609200332738295",
		"10208083437479749091663769290880341696951210333142239058982798491933369634658",
		"19371140597274853679292375926419652865869135313465054712996746675235918739169",
		"20971661560259707098854603768203949465180509867854450112616175986484870421138",
		"21838330569261441578087646010525345708120479655451726406087932484095187695549",
		"1076468390231167140360365402549282875608448404587397878869395031512647545868",
		"6092562878013814855183104955777715456621614617862565177117435129255704079816",
		"18170161495387533917334964667662143192347640390128446556717056467963418198054",
		"12109168190744162366750385102312029693950407650008338509019026459317895835309",
		"2544515291684966855280435972478516040217778310392748651232105437618227749994",
		"15507833383654996913475404388196490841449813254954018401673216235880494534754",
		"9380720655920370046211204946052206765055511343725830684785673543023741993312",
		"4075185557495157137658600992091098641694110615629352438267813211136993876650",
		"20717870862653987407155106996159787542440325578024314005823385621372755326674",
		"4815783172417066630729630018577795817279508567440163468943586637205331905419",
		"10191708984143774877397162783302180085783051650391418734913757161058566615716",
		"12709179554712235414695320020168637754351757243494418321394148981472365589549",
		"11713908815142029267977623070427886421590639997586227181669025742969514806643",
		"14975567209499876151412402594801810332666577737007342935060399369293114492453",
		"4297848205619735573379913160795364592161838502585648079402224506267602723902",
		"16395392222317019456016218924241407228380986050333722208118133679977446245065",
		"12959937773704006145335986634830507188953799862425156620262967430053968980597",
		"10611666550972266129080819432693421560818873779652376153152772165559569100498",
		"19720650681541961299836478555453123453649520285923438834236036850370957389533"} {

		yArr[i].SetString(y)
	}

	for i, a := range [...]string{
		"12136087830675299266258954793902014139747133950228959214677232437877732505267",
		"1949262915742616509924639087995052057439533688639443528419902050101511253219",
		"19696026105199390416727112585766461108620822978182620644600554326664686143928",
		"4837202928086718576193880638295431461498764555598430221157283092238776342056",
		"20604733757835564048563775050992717669420271708242272549953811572144277524421",
		"3211475718977376565880387313110606450525142591707961226303740825956563866938",
		"20322324153453907734144901224240556024026610989461831427966532469618423079473",
		"7934973319760976485021791030537501865656619719264759660277823446649082147312",
		"930415486950737914013769279801651475511858502656263669439342111832254726850",
		"13233069796564124818867608145207094060962111073577067140167532768756987412088",
		"21056848409984369169004352317081356901925342815742628419179104554944602838181",
		"7609965049060251551691128076452200168193674628022973404475256739231396295027",
		"2875569989607589080323784051637402876467307402338253586046146159474138388518",
		"1638405415371537336552461768985626566464351501714515162849864399640580102578",
		"15419971351110340210204119021937390512827818431981795058254849419538982779889",
		"6266520897908297023042570116888246900567139531590020770952602488348558265061",
		"14039893748423238973883972164169603996654684831868979824941451015257316714495",
		"17495914808944773938291362208338085117997720817217450529979495804567647637318",
		"5560043367941296663296908882927102318709803693167554571558317138775165457566",
		"679516368620232917376775416937269411660606739225677609931160531673791709159",
		"20771173458695616083113300195745636859853909352816078680615698162064064254487",
		"9061949945732349497554037671487309408019595175888253563639003740846345173268",
		"6589283089756049627166577132264171123481224689360969470370811604100156764233",
		"3533527516202756096389060356777395269308981839403476652028917646088724581131",
		"5616942227850617678046840250903304358333298306807220766347746809267032455299",
		"19134688161961603498559262912818080142324701420702686735061929518115443109100",
		"4455012138630075486254307533606858125267214265131501816598058811172692328101",
		"10793166202851599893237663367817743308639336679992856426902640679097285197834",
		"15056866545271068254544312503685146788561860865190761206515636207319868585312",
		"18588820303015761108497689698317977183405401884497470414262723108370171102023",
		"19833892328086915832797048699984794667331247199325415348986995942708708405059",
		"898953396730445825940003488465251983486876859688881180356386693085994272154",
		"11340240789075205057343229997968129213431697722131695573513514123825351727265",
		"19892667690111598338150747633561348627404155092311695371528902260306500224478",
		"5675265566752264879035374032667220698134217173464462106243551163373050847632",
		"20083467967117235977304805384179142748526655108920556941636271719496304583696",
		"17241462814856629393310447955833139605117065616411368427339901837278291194631",
		"459523005856707668283348902081873079675765291191967460823756003540662376503",
		"7536104111246397807428611027267470467060028762437526544651879177391629902952",
		"10590470262497492482063013216166955143786637478931633085736787678537413766247",
		"15043612058042949906959587136396856430320834576029342208816587940851697052752",
		"7330056066898340139347678689385900107077259949111182422329627141831221863855",
		"19916604609861621491722130626309103960340872015429661158412002662197451448107",
		"308306529997070213533139133875862443286398019572914380538015645187505823318",
		"16861578445042558674239888228729122953078668310622552358464602254565597746836",
		"2366359755939099031669574080770668941312280240662985815253933900628948645191",
		"8788914401574223424632781718358228468459844175515383031440552306265712071450",
		"9779987514099704007279027021166746630318148945176798063151889326895889174458",
		"13135609303826200140065220669831303027168227375851483214161433389386937614136",
		"11882415982617123710903704093174071260801610004108501667550482610326464450188",
		"4694986622157183973572682165500777613739137314689019399776788204304376634992",
		"2808898114262898635818480138517494241567797735868474755455378194917584076537",
		"5948815563212137849669729139804279433531777993372036737258762483412800936524",
		"8496838141077262636623013469780283761807018011829013896066741949043911303482",
		"13702702800086118773314822629146457886421384618509027653511022100403608735978",
		"128688574990165958444408798980207546660746573848805400153153989929390707086",
		"12715895361575110453437591483121803013655602937865783580504131050519779681504",
		"17179978120180957050330523849284167936336391317937861638141613431407020295629",
		"11588459002841336587102129061065070154347559648088906077759949716914737879289",
		"168729015953654988689927854892774175085256078299955360517770595983890795563",
		"17165830632129355357506266148952557268171444871293207481635264037052195045134",
		"12285138422811175780558426551904715989773712718224312428395575235466952713940",
		"1987154593247807270868347506717058470421782960151084491475247158475586184486",
		"936832494647391757736430222708683185711203089414475274201868885273866499292",
		"2763903754000480287708688930433393942277464250028040958350868219711066983212",
		"14557524245952597893636674984376061034140209715056307601099498105010811817976",
		"8621083546529398784671346534967410376642366851765751955141670352937262262964",
		"16627133697950876223520571090822797284529950315549243443213268507732589809668",
		"3037237623056839958281909328577143274349259163243900007898639886427035545715",
		"12995322444898226109150040488092296918287501169681313486450928080265859678431",
		"2733175139613460118331091475705229587335989342539982599327578628225987296693",
		"6330904024850799154241468252437391268363906860268077269679635105930910493698",
		"6737293883333053574354581827330797956286937344085463211929388455105153381840",
		"5169833748253678861646459610440007606812480863902145153341918680460199744937",
		"5663342152029876725337105797615457704649755088730278042317883168997297323658",
		"7823289338543622859281063471306327640697795333152031235270922571768144390442",
		"1340620010762718653929597746951102533345616951097596331852240652037854160258",
		"14897728869802140961598204911995631203157447569404601325674568226982309954150",
		"392018124866990209108785883333829486897323525593091953436038191276969589879",
		"435898044557960665437580260079284983588895103844486797156208731954139457048",
		"9993497896703025989867048646043173418345536355715949769299454237797386286833",
		"15450930933516186552123777405659014411420729103535031826405440554766901684012",
		"20903034268582375477673219601216374844076505392263195573819638253963628987677",
		"3482242022270674095230150345947605407241554167884470462727496514965587717020",
		"7327691729979824302166499451919150969294811677490604640371561147744223396077",
		"20320351461219902734279664936551332285309420491532838228883116430144043470224",
		"10080172065834582431913901068278960033644520993565022600527798146227389706243",
		"7585484857655643314874927439430217827126382955320388941459286281381839302612",
		"7020483570292313692729758704383267761829627767486597865215352770024378363713",
		"9412915321043344246413050595015332915226967771752410481732502466528909535915",
		"97172793343716602779526815707427204724123444268829991232994756079285191657",
		"9899367385098696963034612599611804167993369962788397262985493922791351318920",
		"20493102078330064462134068336666924427323601025383617983664121148357421387185",
		"3761041932368006457845986014429804620297172145142418054203286909040968118241",
		"1538739698002044525972417606140809601347518204915820728384854667109147333511",
		"13802243875617990810077229053159639403189861626210898918796014575383062790441",
		"14802416169101027248236235356384528498867388780049957297916199959694575989798",
		"12855744726651850023311564252614781422504814539761023618408723113057440886558",
		"3017365043038086323648780208528621420394032286007989775391627155784248978766",
		"6315674106586331242761612192226077184856834393892197849679034296526217823177",
	} {

		Arks[i].SetString(a)
	}
}


<|start_filename|>polynomial/book_keeping_test.go<|end_filename|>
package polynomial

import (
	"github.com/consensys/gkr-mimc/common"
	"testing"

	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/stretchr/testify/assert"
)

func TestLinearCombinationOfBookKeepingTables(t *testing.T) {

	i0 := 13
	i1 := 1789
	table0 := make([]fr.Element, 2)
	table1 := make([]fr.Element, 2)
	correctLinComb := make([]fr.Element, 2)
	for i := 0; i < 2; i++ {
		table0[i].SetUint64(uint64(i))
		table1[i].SetUint64(uint64(i*i + 3*i + 2))
		correctLinComb[i].SetUint64(uint64(i0*i + i1*(i*i+3*i+2)))
	}

	var a0, a1 fr.Element
	a0.SetUint64(uint64(i0))
	a1.SetUint64(uint64(i1))

	t0 := NewBookKeepingTable(table0)
	t1 := NewBookKeepingTable(table1)
	correctLinCombDenseTable := NewBookKeepingTable(correctLinComb)

	linCombDenseTable := LinearCombinationOfBookKeepingTables(t0, t1, a0, a1)

	assert.Equal(t, correctLinCombDenseTable, linCombDenseTable, "Linear combination failed.")
}

func TestFold(t *testing.T) {
	// [0, 1, 2, 3]
	table := make([]fr.Element, 4)
	for i := 0; i < 4; i++ {
		table[i].SetUint64(uint64(i))
	}

	var r fr.Element
	r.SetUint64(uint64(5))

	bkt := NewBookKeepingTable(table)
	// Folding on 5 should yield [10, 11]
	bkt.Fold(r)

	var ten, eleven fr.Element
	ten.SetUint64(uint64(10))
	eleven.SetUint64(uint64(11))

	assert.Equal(t, ten, bkt.Table[0], "Mismatch on 0")
	assert.Equal(t, eleven, bkt.Table[1], "Mismatch on 1")
}

func TestFuncEval(t *testing.T) {
	// [0, 1, 2, 3]
	table := make([]fr.Element, 4)
	for i := 0; i < 4; i++ {
		table[i].SetUint64(uint64(i))
	}

	bkt := NewBookKeepingTable(table)
	// Folding on 5 should yield [10, 11]
	evals := bkt.FunctionEvals()

	var two fr.Element
	two.SetUint64(uint64(2))

	assert.Equal(t, two, evals[0])
	assert.Equal(t, two, evals[1])
}

func BenchmarkFolding(b *testing.B) {

	size := 1 << 25

	// [0, 1, 2, 3]
	table := make([]fr.Element, size)
	for i := 0; i < size; i++ {
		table[i].SetUint64(uint64(i))
	}

	var r fr.Element
	r.SetUint64(uint64(5))

	bkt := NewBookKeepingTable(table)
	// Folding on 5 should yield [10, 11]

	b.ResetTimer()
	for k := 0; k < b.N; k++ {

		bkt2 := bkt.DeepCopy()
		common.ProfileTrace(b, false, false, func() {
			bkt2.Fold(r)
		})
	}
}

func BenchmarkEvals(b *testing.B) {
	size := 1 << 25

	// [0, 1, 2, 3]
	table := make([]fr.Element, size)
	for i := 0; i < size; i++ {
		table[i].SetUint64(uint64(i))
	}

	var r fr.Element
	r.SetUint64(uint64(5))

	bkt := NewBookKeepingTable(table)
	// Folding on 5 should yield [10, 11]
	b.ResetTimer()
	for k := 0; k < b.N; k++ {
		common.ProfileTrace(b, false, false, func() {
			fEvals = bkt.FunctionEvals()
		})
	}
}

var fEvals []fr.Element


<|start_filename|>snark/gkr/static.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gkr-mimc/snark/polynomial"

	"github.com/consensys/gnark/frontend"
)

// StaticTableGenerator returns a prefolded static table
type StaticTableGenerator func(cs *frontend.ConstraintSystem, Q []frontend.Variable) polynomial.MultilinearByValues


<|start_filename|>hash/gmimc.go<|end_filename|>
package hash

import (
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
)

// GMimcT2 is a hasher for t = 2
var GMimcT2 GMimcHasher

// GMimcT4 is a hasher for t = 4
var GMimcT4 GMimcHasher

// GMimcT8 is a hasher for t = 8
var GMimcT8 GMimcHasher

func initGMimc() {
	GMimcT2 = GMimcHasher{t: 2, nRounds: 91}
	GMimcT4 = GMimcHasher{t: 4, nRounds: 91}
	GMimcT8 = GMimcHasher{t: 8, nRounds: 91}
}

// GMimcHasher contains all the parameters to describe a GMimc function
type GMimcHasher struct {
	t       int // size of Cauchy matrix
	nRounds int // number of rounds of the Mimc hash function
}

// Hash hashes a full message
func (g *GMimcHasher) Hash(msg []fr.Element) fr.Element {
	state := make([]fr.Element, g.t)

	for i := 0; i < len(msg); i += g.t {
		block := make([]fr.Element, g.t)
		if i+g.t >= len(msg) {
			// Only zero-pad the input
			for j, w := range msg[i:] {
				block[j] = w
			}
		} else {
			// Take a full chunk
			for j, w := range msg[i : i+g.t] {
				block[j] = w
			}
		}
		g.UpdateInplace(state, block)
	}

	return state[0]
}

// UpdateInplace updates the state with the provided block of data
func (g *GMimcHasher) UpdateInplace(state []fr.Element, block []fr.Element) {
	oldState := append([]fr.Element{}, state...)
	for i := 0; i < g.nRounds; i++ {
		AddArkAndKeysInplace(state, block, Arks[i])
		SBoxInplace(&state[0])
		InPlaceCircularPermutation(state)
	}

	// Recombine with the old state
	for i := range state {
		state[i].Add(&state[i], &oldState[i])
		state[i].Add(&state[i], &block[i])
	}
}

// InPlaceCircularPermutation moves all the element to the left and place the first element
// at the end of the state
// ie: [a, b, c, d] -> [b, c, d, a]
func InPlaceCircularPermutation(state []fr.Element) {
	for i := 1; i < len(state); i++ {
		state[i-1], state[i] = state[i], state[i-1]
	}
}


<|start_filename|>sumcheck/verifier.go<|end_filename|>
package sumcheck

import (
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"

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

// Verifier holds the methods relative to the verifier algorithm
type Verifier struct{}

// Verify returns true if and only the sumcheck proof is valid
func (v Verifier) Verify(claim fr.Element, proof Proof, bN, bG int) (result bool, qPrime, qL, qR []fr.Element, finalClaim fr.Element) {
	// Initalize the structures
	challenges := make([]fr.Element, len(proof.PolyCoeffs))
	var expectedValue fr.Element = claim
	var actualValue, r, zero, one, evalAtOne fr.Element
	one.SetOne()

	for i := 0; i < len(proof.PolyCoeffs); i++ {
		// Check P_i(0) + P_i(1) == expected
		actualValue = polynomial.EvaluatePolynomial(proof.PolyCoeffs[i], zero)
		evalAtOne = polynomial.EvaluatePolynomial(proof.PolyCoeffs[i], one)
		actualValue.Add(&actualValue, &evalAtOne)

		if expectedValue != actualValue {
			return false, nil, nil, nil, [4]uint64{0, 0, 0, 0}
		}
		// expectedValue = P_i(r)
		r = common.GetChallenge(proof.PolyCoeffs[i])

		challenges[i] = r
		expectedValue = polynomial.EvaluatePolynomial(proof.PolyCoeffs[i], r)
	}

	// A deep-copy to avoid reusing the same underlying slice for all writes
	qL = append([]fr.Element{}, challenges[:bG]...)
	qR = append([]fr.Element{}, challenges[bG:2*bG]...)
	qPrime = append([]fr.Element{}, challenges[2*bG:]...)

	// final confrontation omitted for now
	return true, qPrime, qL, qR, expectedValue
}


<|start_filename|>snark/gkr/mimc_test.go<|end_filename|>
package gkr

import (
	"fmt"
	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/examples"
	"github.com/consensys/gkr-mimc/gkr"
	"github.com/consensys/gkr-mimc/snark/polynomial"
	"runtime"
	"testing"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/consensys/gnark/backend"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
)

type GKRMimcTestCircuit struct {
	Circuit                 Circuit
	Proof                   Proof
	QInitial, QInitialprime []frontend.Variable
	VInput, VOutput         polynomial.MultilinearByValues
}

func AllocateGKRMimcTestCircuit(bN int) GKRMimcTestCircuit {
	circuit := CreateMimcCircuit()
	return GKRMimcTestCircuit{
		Circuit:       circuit,
		Proof:         AllocateProof(bN, circuit),
		QInitial:      []frontend.Variable{},
		QInitialprime: make([]frontend.Variable, bN),
		VInput:        polynomial.AllocateMultilinear(bN + 1),
		VOutput:       polynomial.AllocateMultilinear(bN),
	}
}

func (c *GKRMimcTestCircuit) Assign(
	proof gkr.Proof,
	inputs [][]fr.Element,
	outputs [][]fr.Element,
	qInitialprime []fr.Element,
) {
	c.Proof.Assign(proof)
	for i := range qInitialprime {
		c.QInitialprime[i].Assign(qInitialprime[i])
	}
	c.VInput.AssignFromChunkedBKT(inputs)
	c.VOutput.AssignFromChunkedBKT(outputs)
}

func (c *GKRMimcTestCircuit) Define(curveID ecc.ID, cs *frontend.ConstraintSystem) error {
	c.Proof.AssertValid(cs, c.Circuit, c.QInitial, c.QInitialprime, c.VInput, c.VOutput)
	return nil
}

func TestMimcCircuit(t *testing.T) {

	bN := 2
	assert := groth16.NewAssert(t)

	mimcCircuit := AllocateGKRMimcTestCircuit(bN)
	// Attempt to compile the circuit
	r1cs, err := frontend.Compile(ecc.BN254, backend.GROTH16, &mimcCircuit)
	assert.NoError(err)

	// Generate the witness values by running the prover
	var witness GKRMimcTestCircuit

	// Creates the assignments values
	nativeCircuit := examples.CreateMimcCircuit()
	inputs := common.RandomFrDoubleSlice(1, 2*(1<<bN))
	assignment := nativeCircuit.Assign(inputs, 1)
	outputs := assignment.Values[91]
	prover := gkr.NewProver(nativeCircuit, assignment)
	proof := prover.Prove(1)
	qInitialprime, _ := gkr.GetInitialQPrimeAndQ(bN, 0)

	// Assigns the values
	witness = AllocateGKRMimcTestCircuit(bN)
	witness.Assign(proof, inputs, outputs, qInitialprime)

	assert.SolvingSucceeded(r1cs, &witness)
	// Takes 200sec on my laptop
	// assert.ProverSucceeded(r1cs, &witness)
}

func BenchmarkMimcCircuit(b *testing.B) {
	bN := common.GetBN()
	nChunk := common.GetNChunks()
	inputsChunkSize := 2 * (1 << bN) / nChunk
	nCore := runtime.GOMAXPROCS(0)

	fmt.Printf("bN = %v, nChunk = %v, nCore = %v \n", bN, nChunk, nCore)

	mimcCircuit := AllocateGKRMimcTestCircuit(bN)
	// Attempt to compile the circuit
	r1cs, _ := frontend.Compile(ecc.BN254, backend.GROTH16, &mimcCircuit)

	fmt.Printf("Nb constraints = %v\n", r1cs.GetNbConstraints())

	// Generate the witness values by running the prover
	var witness GKRMimcTestCircuit

	// Creates the assignments values
	var (
		proof      gkr.Proof
		assignment circuit.Assignment
		outputs    [][]fr.Element
	)

	nativeCircuit := examples.CreateMimcCircuit()
	qInitialprime, _ := gkr.GetInitialQPrimeAndQ(bN, 0)
	inputs := common.RandomFrDoubleSlice(nChunk, inputsChunkSize)

	b.Run("Assignment generation for GKR Prover", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			assignment = nativeCircuit.Assign(inputs, nCore)
			outputs = assignment.Values[91]
		}
	})

	b.Run("GKR Prover", func(b *testing.B) {
		b.ResetTimer()
		b.StopTimer()
		for i := 0; i < b.N; i++ {
			prover := gkr.NewProver(nativeCircuit, assignment)
			b.StartTimer()
			proof = prover.Prove(nCore)
			b.StopTimer()
		}
	})

	// Assigns the values
	b.Run("Gnark circuit assignment", func(b *testing.B) {
		b.StopTimer()
		for i := 0; i < b.N; i++ {
			witness = AllocateGKRMimcTestCircuit(bN)
			b.StartTimer()
			witness.Assign(proof, inputs, outputs, qInitialprime)
			b.StopTimer()
		}
	})

	pk, _ := groth16.DummySetup(r1cs)
	b.Run("Gnark prover", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			_, _ = groth16.Prove(r1cs, pk, &witness)
		}
	})
}


<|start_filename|>gkr/prover.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"
	"github.com/consensys/gkr-mimc/sumcheck"

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

// Prover contains all relevant data for a GKR prover
type Prover struct {
	bN         int
	circuit    circuit.Circuit
	assignment circuit.Assignment
}

// Proof contains all the data for a GKR to be verified
type Proof struct {
	SumcheckProofs []sumcheck.Proof
	ClaimsLeft     []fr.Element
	ClaimsRight    []fr.Element
}

// NewProver returns a new prover
func NewProver(circuit circuit.Circuit, assignment circuit.Assignment) Prover {
	bN := common.Log2Ceil(len(assignment.Values[0])*len(assignment.Values[0][0])) - circuit.Layers[0].BGInputs
	return Prover{
		bN:         bN,
		circuit:    circuit,
		assignment: assignment,
	}
}

// GetInitialQPrimeAndQ returns the initial randomness of the protocol
func GetInitialQPrimeAndQ(bN, bG int) ([]fr.Element, []fr.Element) {
	q := make([]fr.Element, bG)
	qPrime := make([]fr.Element, bN)

	// actually compute qInitial and qPrimeInitial
	// TODO: Uses actual randomness
	for i := range q {
		q[i].SetUint64(uint64(i + 1))
	}

	for i := range qPrime {
		qPrime[i].SetUint64(uint64(i + 1))
	}

	return qPrime, q
}

// GetBookKeepingTablesForInitialRound generates and prefold the book-keeping tables for a the initial GKR round
func (p *Prover) GetBookKeepingTablesForInitialRound(
	qPrime, q []fr.Element, nCore int,
) (
	vL, vR, eq []polynomial.BookKeepingTable,
	statics []polynomial.BookKeepingTable,
) {
	// For the initial round, we always take the last layer
	layer := len(p.circuit.Layers) - 1
	// Compute the static tables
	statics = p.circuit.Layers[layer].GetStaticTable(q)
	// And gate the remaining table
	vL = p.assignment.LayerAsBKTWithCopy(layer, nCore)
	vR = p.assignment.LayerAsBKTWithCopy(layer, nCore)
	eq = polynomial.GetChunkedEqTable(qPrime, len(vL), nCore)
	return vL, vR, eq, statics
}

// GetBookKeepingTablesForIntermediateRound generates and prefold the book-keeping tables for an intermediate round
func (p *Prover) GetBookKeepingTablesForIntermediateRound(
	layer int,
	qPrime, qL, qR []fr.Element,
	lambdaL, lambdaR fr.Element,
	nCore int,
) (
	vL, vR, eq []polynomial.BookKeepingTable,
	statics []polynomial.BookKeepingTable,
) {
	// First vL
	vL = p.assignment.LayerAsBKTWithCopy(layer, nCore)
	vR = p.assignment.LayerAsBKTWithCopy(layer, nCore)
	eq = polynomial.GetChunkedEqTable(qPrime, len(vL), nCore)

	// Get the static tables
	staticsL := p.circuit.Layers[layer].GetStaticTable(qL)
	staticsR := p.circuit.Layers[layer].GetStaticTable(qR)
	// Statics is placeholder for the last
	statics = make([]polynomial.BookKeepingTable, len(staticsL))

	// Then the staticTables in the order given by
	for i := range statics {
		statics[i] = polynomial.LinearCombinationOfBookKeepingTables(
			staticsL[i],
			staticsR[i],
			lambdaL,
			lambdaR,
		)
	}
	return vL, vR, eq, statics
}

// InitialRoundSumcheckProver returns a prover object for the initial round
func (p *Prover) InitialRoundSumcheckProver(qPrime []fr.Element, q []fr.Element, nCore int) sumcheck.MultiThreadedProver {
	layer := len(p.circuit.Layers)
	vL, vR, eq, statics := p.GetBookKeepingTablesForInitialRound(qPrime, q, nCore)
	return sumcheck.NewMultiThreadedProver(vL, vR, eq, p.circuit.Layers[layer-1].Gates, statics)
}

// IntermediateRoundsSumcheckProver returns a prover object for the intermediate round
func (p *Prover) IntermediateRoundsSumcheckProver(
	layer int,
	qPrime, qL, qR []fr.Element,
	lambdaL, lambdaR fr.Element,
	nCore int,
) sumcheck.MultiThreadedProver {
	vL, vR, eq, statics := p.GetBookKeepingTablesForIntermediateRound(layer, qPrime, qL, qR, lambdaL, lambdaR, nCore)
	return sumcheck.NewMultiThreadedProver(vL, vR, eq, p.circuit.Layers[layer].Gates, statics)
}

// Prove produces a GKR proof
func (p *Prover) Prove(nCore int) Proof {
	// bG := p.circuit.bG
	nLayers := len(p.circuit.Layers)
	ClaimsLeft := make([]fr.Element, nLayers)
	ClaimsRight := make([]fr.Element, nLayers)
	SumcheckProofs := make([]sumcheck.Proof, nLayers)

	// Initial round
	qPrime, q := GetInitialQPrimeAndQ(p.bN, p.circuit.Layers[nLayers-1].BGOutputs)
	prover := p.InitialRoundSumcheckProver(qPrime, q, nCore)
	proof, qPrime, qL, qR, finalClaims := prover.Prove(nCore)
	SumcheckProofs[nLayers-1] = proof
	ClaimsLeft[nLayers-1], ClaimsRight[nLayers-1] = finalClaims[0], finalClaims[1]

	for layer := nLayers - 2; layer >= 0; layer-- {

		// Compute the random linear comb of the claims
		var lambdaL fr.Element
		lambdaL.SetOne()
		lambdaR := common.GetChallenge([]fr.Element{ClaimsLeft[layer+1], ClaimsRight[layer+1]})
		claim := ClaimsRight[layer+1]
		claim.Mul(&claim, &lambdaR)
		claim.Add(&claim, &ClaimsLeft[layer+1])

		// Intermediate round sumcheck and update the GKR proof
		prover := p.IntermediateRoundsSumcheckProver(layer, qPrime, qL, qR, lambdaL, lambdaR, nCore)
		SumcheckProofs[layer], qPrime, qL, qR, finalClaims = prover.Prove(nCore)
		ClaimsLeft[layer], ClaimsRight[layer] = finalClaims[0], finalClaims[1]
	}

	return Proof{
		SumcheckProofs: SumcheckProofs,
		ClaimsLeft:     ClaimsLeft,
		ClaimsRight:    ClaimsRight,
	}

}


<|start_filename|>snark/gkr/proof.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gkr-mimc/gkr"
	"github.com/consensys/gkr-mimc/hash"
	hashGadget "github.com/consensys/gkr-mimc/snark/hash"
	"github.com/consensys/gkr-mimc/snark/polynomial"
	"github.com/consensys/gkr-mimc/snark/sumcheck"

	"github.com/consensys/gnark/frontend"
)

const nLayers = hash.MimcRounds

// Proof represents a GKR proof
// Only valid for the MiMC circuit
type Proof struct {
	SumcheckProofs []sumcheck.Proof
	ClaimsLeft     []frontend.Variable
	ClaimsRight    []frontend.Variable
}

// AllocateProof allocates a new proof gadget
func AllocateProof(bN int, circuit Circuit) Proof {
	nLayers := len(circuit.Layers)
	SumcheckProofs := make([]sumcheck.Proof, nLayers)
	ClaimsLeft := make([]frontend.Variable, nLayers)
	ClaimsRight := make([]frontend.Variable, nLayers)

	for i := range SumcheckProofs {
		SumcheckProofs[i] = sumcheck.AllocateProof(bN, circuit.Layers[i].BG, circuit.Layers[i].DegHL, circuit.Layers[i].DegHR, circuit.Layers[i].DegHPrime)
	}

	return Proof{
		SumcheckProofs: SumcheckProofs,
		ClaimsLeft:     ClaimsLeft,
		ClaimsRight:    ClaimsRight,
	}
}

// Assign the proof object
func (p *Proof) Assign(proof gkr.Proof) {
	for k := range p.SumcheckProofs {
		p.SumcheckProofs[k].Assign(proof.SumcheckProofs[k])
		p.ClaimsLeft[k].Assign(proof.ClaimsLeft[k])
		p.ClaimsRight[k].Assign(proof.ClaimsRight[k])
	}
}

// AssertValid runs the GKR verifier
func (p *Proof) AssertValid(
	cs *frontend.ConstraintSystem,
	circuit Circuit,
	qInitial []frontend.Variable,
	qPrimeInitial []frontend.Variable,
	vInput, vOutput polynomial.MultilinearByValues,
) {

	qqPrime := append(append([]frontend.Variable{}, qInitial...), qPrimeInitial...)
	claim := vOutput.Eval(cs, qqPrime)
	hL, hR, hPrime, expectedTotalClaim := p.SumcheckProofs[nLayers-1].AssertValid(cs, claim, circuit.Layers[nLayers-1].BG)
	actualTotalClaim := circuit.Layers[nLayers-1].Combine(
		cs,
		qInitial, qPrimeInitial,
		hL, hR, hPrime,
		p.ClaimsLeft[nLayers-1], p.ClaimsRight[nLayers-1],
	)
	cs.AssertIsEqual(expectedTotalClaim, actualTotalClaim)

	var qL, qR, qPrime []frontend.Variable

	for layer := nLayers - 2; layer >= 0; layer-- {
		lambdaL := cs.Constant(1)
		lambdaR := hashGadget.MimcHash(cs, p.ClaimsLeft[layer+1], p.ClaimsRight[layer+1])
		claim = cs.Add(p.ClaimsLeft[layer+1], cs.Mul(lambdaR, p.ClaimsRight[layer+1]))

		// Updates qL and qR values to initialize the next round
		qL = hL
		qR = hR
		qPrime = hPrime

		// Verify the sumcheck
		hL, hR, hPrime, expectedTotalClaim = p.SumcheckProofs[layer].AssertValid(cs, claim, circuit.Layers[layer].BG)
		actualTotalClaim = circuit.Layers[layer].CombineWithLinearComb(
			cs,
			qL, qR, qPrime,
			hL, hR, hPrime,
			lambdaL, lambdaR,
			p.ClaimsLeft[layer], p.ClaimsRight[layer],
		)
		cs.AssertIsEqual(expectedTotalClaim, actualTotalClaim)
	}

	actualVL, actualVR := p.ClaimsLeft[0], p.ClaimsRight[0]
	expectedVL, expectedVR := vInput.EvalMixed(cs, hL, hR, hPrime)

	cs.AssertIsEqual(expectedVL, actualVL)
	cs.AssertIsEqual(expectedVR, actualVR)
}


<|start_filename|>sumcheck/par.go<|end_filename|>
package sumcheck

import (
	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/polynomial"
	"sync"

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

// MultiThreadedProver can process on several threads
type MultiThreadedProver struct {
	// Contains the values of the previous layer
	vL []polynomial.BookKeepingTable
	vR []polynomial.BookKeepingTable
	// Contains the static tables defining the circuit structure
	eq           []polynomial.BookKeepingTable
	gates        []circuit.Gate
	staticTables []polynomial.BookKeepingTable
	// Degrees for the differents variables
	degreeHL     int
	degreeHR     int
	degreeHPrime int
}

type indexedProver struct {
	I int
	P SingleThreadedProver
}

// NewMultiThreadedProver constructs a new prover
func NewMultiThreadedProver(
	vL []polynomial.BookKeepingTable,
	vR []polynomial.BookKeepingTable,
	eq []polynomial.BookKeepingTable,
	gates []circuit.Gate,
	staticTables []polynomial.BookKeepingTable,
) MultiThreadedProver {
	// Auto-computes the degree on each variables
	degreeHL, degreeHR, degreeHPrime := 0, 0, 0
	for _, gate := range gates {
		dL, dR, dPrime := gate.Degrees()
		degreeHL = common.Max(degreeHL, dL)
		degreeHR = common.Max(degreeHR, dR)
		degreeHPrime = common.Max(degreeHPrime, dPrime)
	}
	return MultiThreadedProver{
		vL:           vL,
		vR:           vR,
		eq:           eq,
		gates:        gates,
		staticTables: staticTables,
		degreeHL:     degreeHL + 1,
		degreeHR:     degreeHR + 1,
		degreeHPrime: degreeHPrime + 1,
	}
}

// GetClaim returns the sum of all evaluations don't call after folding
func (p *MultiThreadedProver) GetClaim(nCore int) fr.Element {
	// Define usefull constants
	nChunks := len(p.eq)
	evalsChan := make(chan fr.Element, len(p.eq))
	semaphore := common.NewSemaphore(nCore)

	for i := 0; i < nChunks; i++ {
		go p.GetClaimForChunk(i, evalsChan, semaphore)
	}

	var res fr.Element
	for i := 0; i < nChunks; i++ {
		x := <-evalsChan
		res.Add(&x, &res)
	}

	return res
}

// Prove runs a prover with multi-threading
func (p *MultiThreadedProver) Prove(nCore int) (proof Proof, qPrime, qL, qR, finalClaims []fr.Element) {

	// Define usefull constants
	nChunks := len(p.eq)
	n := nChunks * len(p.eq[0].Table)     // Number of subcircuit. Since we haven't fold on h' yet
	g := nChunks * len(p.vL[0].Table) / n // SubCircuit size. Since we haven't fold on hR yet
	bN := common.Log2Ceil(n)
	bG := common.Log2Ceil(g)
	logNChunk := common.Log2Ceil(nChunks)

	// Initialized the results
	proof.PolyCoeffs = make([][]fr.Element, bN+2*bG)
	qPrime = make([]fr.Element, bN)
	qL = make([]fr.Element, bG)
	qR = make([]fr.Element, bG)
	finalClaims = make([]fr.Element, 3+len(p.staticTables))

	// Initialize the channels
	evalsChan := make(chan []fr.Element, nChunks)
	finChan := make(chan indexedProver, nChunks)
	rChans := make([]chan fr.Element, nChunks)
	semaphore := common.NewSemaphore(nCore)

	// Starts the sub-provers
	for i := 0; i < nChunks; i++ {
		rChans[i] = make(chan fr.Element, 1)
		go p.RunForChunk(i, evalsChan, rChans[i], finChan, semaphore)
	}

	// Process on all values until all the subprover are completely fold
	for i := 0; i < 2*bG+bN-logNChunk; i++ {
		evals := ConsumeAccumulate(evalsChan, nChunks)
		proof.PolyCoeffs[i] = polynomial.InterpolateOnRange(evals)
		r := common.GetChallenge(proof.PolyCoeffs[i])
		Broadcast(rChans, r)
		if i < bG {
			qL[i] = r
		} else if i < 2*bG {
			qR[i-bG] = r
		} else {
			qPrime[i-2*bG] = r
		}
	}

	newP := ConsumeMergeProvers(finChan, nChunks)

	// Finishes on hPrime. Identical to the single-threaded implementation
	for i := 2*bG + bN - logNChunk; i < bN+2*bG; i++ {
		evals := newP.GetEvalsOnHPrime()
		proof.PolyCoeffs[i] = polynomial.InterpolateOnRange(evals)
		r := common.GetChallenge(proof.PolyCoeffs[i])
		newP.FoldHPrime(r)
		qPrime[i-2*bG] = r
	}

	finalClaims[0] = newP.vL.Table[0]
	finalClaims[1] = newP.vR.Table[0]
	finalClaims[2] = newP.eq.Table[0]
	for i, bkt := range newP.staticTables {
		finalClaims[3+i] = bkt.Table[0]
	}

	close(evalsChan)
	close(finChan)

	return proof, qPrime, qL, qR, finalClaims

}

// ConsumeMergeProvers reallocate the provers from the content of the indexed prover,
// by concatenating their bookkeeping tables.
func ConsumeMergeProvers(ch chan indexedProver, nToMerge int) SingleThreadedProver {

	// Allocate the new Table
	newVL := make([]fr.Element, nToMerge)
	newVR := make([]fr.Element, nToMerge)
	newEq := make([]fr.Element, nToMerge)

	indexed := <-ch
	// First off the loop to take the static tables at the same time
	newVL[indexed.I] = indexed.P.vL.Table[0]
	newVR[indexed.I] = indexed.P.vR.Table[0]
	newEq[indexed.I] = indexed.P.eq.Table[0]
	// All subProvers have the same staticTables. So we can take the first one
	staticTables := indexed.P.staticTables
	gates := indexed.P.gates

	for i := 0; i < nToMerge-1; i++ {
		indexed = <-ch
		newVL[indexed.I] = indexed.P.vL.Table[0]
		newVR[indexed.I] = indexed.P.vR.Table[0]
		newEq[indexed.I] = indexed.P.eq.Table[0]
	}

	return NewSingleThreadedProver(
		polynomial.NewBookKeepingTable(newVL),
		polynomial.NewBookKeepingTable(newVR),
		polynomial.NewBookKeepingTable(newEq),
		gates,
		staticTables,
	)
}

// ConsumeAccumulate consumes `nToConsume` elements from `ch`,
// and return their sum Element-wise
func ConsumeAccumulate(ch chan []fr.Element, nToConsume int) []fr.Element {
	res := <-ch
	for i := 0; i < nToConsume-1; i++ {
		tmp := <-ch
		for i := range res {
			res[i].Add(&res[i], &tmp[i])
		}
	}
	return res
}

// Broadcast broadcasts r, to all channels
func Broadcast(chs []chan fr.Element, r fr.Element) {
	var wg sync.WaitGroup
	wg.Add(len(chs))
	for _, ch := range chs {
		go func(ch chan fr.Element) {
			ch <- r
			wg.Done()
		}(ch)
	}
	wg.Wait()
}

// GetClaimForChunk runs GetClaim on a chunk, and is aimed at being run in the Background
func (p *MultiThreadedProver) GetClaimForChunk(chunkIndex int, evalsChan chan fr.Element, semaphore common.Semaphore) {
	semaphore.Acquire()
	defer semaphore.Release()

	// Deep-copies the static tables
	staticTablesCopy := make([]polynomial.BookKeepingTable, len(p.staticTables))
	for i := range staticTablesCopy {
		staticTablesCopy[i] = p.staticTables[i].DeepCopy()
	}

	subProver := NewSingleThreadedProver(
		p.vL[chunkIndex],
		p.vR[chunkIndex],
		p.eq[chunkIndex],
		p.gates,
		staticTablesCopy,
	)

	evalsChan <- subProver.GetClaim()
}

// RunForChunk runs thread with a partial prover
func (p *MultiThreadedProver) RunForChunk(
	chunkIndex int,
	evalsChan chan []fr.Element,
	rChan chan fr.Element,
	finChan chan indexedProver,
	semaphore common.Semaphore,
) {
	semaphore.Acquire()
	// Deep-copies the static tables
	staticTablesCopy := make([]polynomial.BookKeepingTable, len(p.staticTables))
	for i := range staticTablesCopy {
		staticTablesCopy[i] = p.staticTables[i].DeepCopy()
	}

	subProver := NewSingleThreadedProver(
		p.vL[chunkIndex],
		p.vR[chunkIndex],
		p.eq[chunkIndex],
		p.gates,
		staticTablesCopy,
	)

	// Define usefull constants
	n := len(subProver.eq.Table)     // Number of subcircuit. Since we haven't fold on h' yet
	g := len(subProver.vR.Table) / n // SubCircuit size. Since we haven't fold on hR yet
	bN := common.Log2Ceil(n)
	bG := common.Log2Ceil(g)

	// Run on hL
	for i := 0; i < bG; i++ {
		evalsChan <- subProver.GetEvalsOnHL()
		semaphore.Release()
		r := <-rChan
		semaphore.Acquire()
		subProver.FoldHL(r)
	}

	// Run on hR
	for i := 0; i < bG; i++ {
		evalsChan <- subProver.GetEvalsOnHR()
		semaphore.Release()
		r := <-rChan
		semaphore.Acquire()
		subProver.FoldHR(r)
	}

	// Run on hPrime
	for i := 0; i < bN; i++ {
		evalsChan <- subProver.GetEvalsOnHPrime()
		semaphore.Release()
		r := <-rChan
		semaphore.Acquire()
		subProver.FoldHPrime(r)
	}

	finChan <- indexedProver{I: chunkIndex, P: subProver}
	semaphore.Release()
	close(rChan)
}


<|start_filename|>common/challenge.go<|end_filename|>
package common

import (
	"github.com/consensys/gkr-mimc/hash"

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

// GetChallenge returns a interaction challenge
func GetChallenge(challengeSeed []fr.Element) fr.Element {
	return hash.MimcHash(challengeSeed)
}


<|start_filename|>examples/mimc_test.go<|end_filename|>
package examples

import (
	"fmt"
	"runtime"
	"sync"
	"testing"

	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"github.com/consensys/gkr-mimc/gkr"
	"github.com/consensys/gkr-mimc/hash"
	"github.com/stretchr/testify/assert"

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

func randomInputs(nChunks, bN int) [][]fr.Element {
	size := 2 * (1 << bN)
	chunkSize := size / nChunks
	res := make([][]fr.Element, nChunks)
	for i := range res {
		res[i] = common.RandomFrArray(chunkSize)
	}
	return res
}

func TestMimc(t *testing.T) {

	// Initialize the circuit
	mimcCircuit := CreateMimcCircuit()

	// This checks the transition functions to be consistent
	// With the actual hash function

	// Test the consistency between the the combinator and the transition function
	bN := 3
	nChunks := 2
	inputChunkSize := 2 * (1 << bN) / nChunks
	var zero, one fr.Element
	one.SetOne()

	// Performs the assignment
	inputs := randomInputs(nChunks, bN)
	assignment := mimcCircuit.Assign(inputs, 1)
	outputs := assignment.Values[91]

	// Sees if the output is consistent with the result of calling Mimc permutation
	newState := inputs[0][inputChunkSize/2]
	block := inputs[0][0]
	oldState := inputs[0][inputChunkSize/2]
	// Our circuit expects the first addition to be made by the client
	block.Sub(&block, &oldState)
	hash.MimcPermutationInPlace(&newState, block)
	// An error here indicate an error in the transition functions definition
	assert.Equal(t, newState.String(), outputs[0][0].String(), "Error on the state calculation")

	layer1 := assignment.Values[1]
	gates := mimcCircuit.Layers[0].Gates
	layer1FromCombinator := []fr.Element{
		// Expected to output the value of copy
		circuit.EvaluateCombinator(
			&inputs[0][inputChunkSize/2], &inputs[0][0], &one, gates, []fr.Element{one, zero},
		),
		// Expected to output the value of cipher
		circuit.EvaluateCombinator(
			&inputs[0][inputChunkSize/2], &inputs[0][0], &one, gates, []fr.Element{zero, one},
		),
	}
	// An error here indicate an error in the combinator definition
	assert.Equal(t, layer1[0][0], layer1FromCombinator[0], "Error on cipher")
	assert.Equal(t, layer1[0][inputChunkSize/2], layer1FromCombinator[1], "Error on copy")

	ptest := gkr.NewProver(mimcCircuit, assignment)
	qPrime := make([]fr.Element, bN)

	// Get the sumcheck provers for the first layer on q = 0 and q = 1
	// And test that the claims are consistent with the assignment in layer 1
	sumcheckPQ0 := ptest.IntermediateRoundsSumcheckProver(0, qPrime, []fr.Element{zero}, []fr.Element{zero}, one, zero, 1)
	sumcheckPQ1 := ptest.IntermediateRoundsSumcheckProver(0, qPrime, []fr.Element{one}, []fr.Element{zero}, one, zero, 1)
	claimQ0 := sumcheckPQ0.GetClaim(1)
	claimQ1 := sumcheckPQ1.GetClaim(1)
	// If the test fails there, there is likely a problem with the tables
	assert.Equal(t, layer1[0][0], claimQ0, "Error with the claims")
	assert.Equal(t, layer1[0][inputChunkSize/2], claimQ1, "Error with the claims")

	// Get the sumcheck provers for the last layer on q = 0
	// And test that the claims are consistent with the assignment in layer n-1
	sumcheckPQInit := ptest.InitialRoundSumcheckProver(qPrime, []fr.Element{}, 1)
	claimQInit := sumcheckPQInit.GetClaim(1)
	// If the test fails there, there is likely a problem with the tables
	assert.Equal(t, outputs[0][0], claimQInit, "Error with the claims")

	// Finally checks the entire GKR protocol
	prover := gkr.NewProver(mimcCircuit, assignment)
	proof := prover.Prove(1)
	verifier := gkr.NewVerifier(bN, mimcCircuit)
	valid := verifier.Verify(proof, inputs, outputs)
	// An error here mostly indicate a problem with the degree calculator
	assert.True(t, valid, "GKR verifier refused")
}

var _mimcProof gkr.Proof

func benchmarkMIMCCircuit(b *testing.B, bN, nCore, nChunks int, profiled, traced bool) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		// Initialize the circuit
		mimcCircuit := CreateMimcCircuit()
		// Performs the assignment
		inputs := randomInputs(nChunks, bN)
		assignment := mimcCircuit.Assign(inputs, 1)
		// Finally checks the entire GKR protocol
		prover := gkr.NewProver(mimcCircuit, assignment)

		common.ProfileTrace(b, profiled, traced, func() {
			_mimcProof = prover.Prove(nCore)
		})
	}
}

func benchmarkMIMCGKRProverMultiProcess(b *testing.B, bN, nProcesses, nCore, nChunks int, profiled, traced bool) {

	b.ResetTimer()
	b.StopTimer()
	for _b := 0; _b < b.N; _b++ {
		var wgReady, wgGo, wgDone sync.WaitGroup
		wgReady.Add(nProcesses)
		wgGo.Add(1)
		wgDone.Add(nProcesses)
		for k := 0; k < nProcesses; k++ {
			go func() {
				nCore := nCore / nProcesses
				nChunks := nChunks / nProcesses
				bN := bN - common.Log2Ceil(nProcesses)
				// Redimensionate bN to take into account the
				// Initialize the circuit
				mimcCircuit := CreateMimcCircuit()
				// Performs the assignment
				inputs := randomInputs(nChunks, bN)
				assignment := mimcCircuit.Assign(inputs, nCore)
				// Finally checks the entire GKR protocol
				prover := gkr.NewProver(mimcCircuit, assignment)
				wgReady.Done()
				wgGo.Wait() // Wait for the main thread's signal
				_mimcProof = prover.Prove(nCore)
				wgDone.Done()
			}()
		}
		wgReady.Wait()

		b.StartTimer()
		common.ProfileTrace(b, profiled, traced, func() {
			wgGo.Done() // Gives the signal
			wgDone.Wait()
		})
		b.StopTimer()
	}

}

func BenchmarkMimcGKRProver(b *testing.B) {
	nChunks := common.GetNChunks()
	bN := common.GetBN()
	nCore := runtime.GOMAXPROCS(0)
	profiled := common.GetProfiled()
	traced := common.GetTraced()
	b.Run(fmt.Sprintf("bN=%d-nCore", bN), func(b *testing.B) {
		benchmarkMIMCCircuit(b, bN, nCore, nChunks, profiled, traced)
	})
}

func BenchmarkMimcGKRProverMultiProcess(b *testing.B) {
	nChunks := common.GetNChunks()
	bN := common.GetBN()
	nCore := runtime.GOMAXPROCS(0)
	nProcesses := common.GetNProcesses()
	profiled := common.GetProfiled()
	traced := common.GetTraced()
	b.Run(fmt.Sprintf("bN=%d-nCore", bN), func(b *testing.B) {
		benchmarkMIMCGKRProverMultiProcess(b, bN, nProcesses, nCore, nChunks, profiled, traced)
	})
}


<|start_filename|>gkr/gkr_test.go<|end_filename|>
package gkr

import (
	"github.com/consensys/gkr-mimc/circuit"
	"github.com/consensys/gkr-mimc/common"
	"testing"

	"github.com/consensys/gnark-crypto/ecc/bn254/fr"
	"github.com/stretchr/testify/assert"
)

// We test for the following circuit
//
//	  a + b + (a×b)	  (a+b) × a × b				  c + d + (c×d)	  (c+d) × c × d
//	________|_______________|_________			________|_______________|_________
// 	|	_________		_________	 |		 	|	_________		_________	 |
//	|	|		|		|		|	 |			|	|		|		|		|	 |
//	|	|	+	|		|	×	|	 |			|	|	+	|		|	×	|	 |
//	|	|_______|		|_______|	 |			|	|_______|		|_______|	 |
//	|________________________________|			|________________________________|
//			|				|							|				|
//		  a + b			  a × b						  c + d			  c × d
//	________|_______________|_________			________|_______________|_________
// 	|	_________		_________	 |		 	|	_________		_________	 |
//	|	|		|		|		|	 |			|	|		|		|		|	 |
//	|	|	+	|		|	×	|	 |			|	|	+	|		|	×	|	 |
//	|	|_______|		|_______|	 |			|	|_______|		|_______|	 |
//	|________________________________|			|________________________________|
//			|				|							|				|
//			a				b							c				d
//
// Note: bN = bG = 1.

// Testcase:
//
//	        5	            6				           19				84
//	________|_______________|_________			________|_______________|_________
// 	|	_________		_________	 |		 	|	_________		_________	 |
//	|	|		|		|		|	 |			|	|		|		|		|	 |
//	|	|	+	|		|	×	|	 |			|	|	+	|		|	×	|	 |
//	|	|_______|		|_______|	 |			|	|_______|		|_______|	 |
//	|________________________________|			|________________________________|
//			|				|							|				|
//		    3			    2						    7			   12
//	________|_______________|_________			________|_______________|_________
// 	|	_________		_________	 |		 	|	_________		_________	 |
//	|	|		|		|		|	 |			|	|		|		|		|	 |
//	|	|	+	|		|	×	|	 |			|	|	+	|		|	×	|	 |
//	|	|_______|		|_______|	 |			|	|_______|		|_______|	 |
//	|________________________________|			|________________________________|
//			|				|							|				|
//			1				2							3				4

func TestMultiBGs(t *testing.T) {
	var one fr.Element
	one.SetOne()

	c := circuit.NewCircuit(
		[][]circuit.Wire{
			// Layer 0
			[]circuit.Wire{
				circuit.Wire{L: 0, R: 1, O: 0, Gate: circuit.AddGate{}},
				circuit.Wire{L: 0, R: 1, O: 1, Gate: circuit.MulGate{}},
			},
			// Layer 1
			[]circuit.Wire{
				circuit.Wire{L: 0, R: 1, O: 0, Gate: circuit.AddGate{}},
			},
		},
	)

	inputs := [][]fr.Element{
		[]fr.Element{common.Uint64ToFr(1), common.Uint64ToFr(2)},
		[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(4)},
	}

	a := c.Assign(inputs, 2)
	inputsV := append([][]fr.Element{}, inputs...)
	outputsV := a.Values[2]

	p := NewProver(c, a)
	proof := p.Prove(1)
	v := NewVerifier(1, c)
	validity := v.Verify(proof, inputsV, outputsV)

	assert.Equal(
		t,
		validity,
		true,
		"Proof invalid.",
	)

	actualValues := [][][]fr.Element{
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(1), common.Uint64ToFr(2)},
			[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(4)},
		},
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(2)},
			[]fr.Element{common.Uint64ToFr(7), common.Uint64ToFr(12)},
		},
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(5)},
			[]fr.Element{common.Uint64ToFr(19)},
		},
	}

	assert.Equal(
		t,
		a.Values,
		actualValues,
		"Assignment invalid.",
	)
}

func TestGKR(t *testing.T) {
	var one fr.Element
	one.SetOne()

	c := circuit.NewCircuit(
		[][]circuit.Wire{
			// Layer 0
			[]circuit.Wire{
				circuit.Wire{L: 0, R: 1, O: 0, Gate: circuit.AddGate{}},
				circuit.Wire{L: 0, R: 1, O: 1, Gate: circuit.MulGate{}},
			},
			// Layer 1
			[]circuit.Wire{
				circuit.Wire{L: 0, R: 1, O: 0, Gate: circuit.AddGate{}},
				circuit.Wire{L: 0, R: 1, O: 1, Gate: circuit.MulGate{}},
			},
		},
	)

	inputs := [][]fr.Element{
		[]fr.Element{common.Uint64ToFr(1), common.Uint64ToFr(2)},
		[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(4)},
	}

	a := c.Assign(inputs, 2)

	expectedValues := [][][]fr.Element{
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(1), common.Uint64ToFr(2)},
			[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(4)},
		},
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(3), common.Uint64ToFr(2)},
			[]fr.Element{common.Uint64ToFr(7), common.Uint64ToFr(12)},
		},
		[][]fr.Element{
			[]fr.Element{common.Uint64ToFr(5), common.Uint64ToFr(6)},
			[]fr.Element{common.Uint64ToFr(19), common.Uint64ToFr(84)},
		},
	}

	assert.Equal(
		t,
		expectedValues,
		a.Values,
		"Assignment invalid.",
	)

	outputs := a.Values[2]

	p := NewProver(c, a)
	proof := p.Prove(1)
	v := NewVerifier(1, c)
	validity := v.Verify(proof, inputs, outputs)

	assert.Equal(
		t,
		validity,
		true,
		"Proof invalid.",
	)
}
