MatrixMultiplication

[sid-alluri]

Hi, I am trying to write a circuit for matrix multiplication.

type MatMulCircuit struct {
	A [][]frontend.Variable
	B [][]frontend.Variable
	Y [][]frontend.Variable
}

func MatMul(api frontend.API, A [][]frontend.Variable, B [][]frontend.Variable) [][]frontend.Variable {
	output := make([][]frontend.Variable, len(A))

	for i := 0; i < len(A); i++ {
		output[i] = make([]frontend.Variable, len(B[0]))
		for j := 0; j < len(B[0]); j++ {
			output[i][j] = frontend.Variable(0)
			for k := 0; k < len(A[0]); k++ {
				buf := api.Mul(A[i][k], B[k][j])
				output[i][j] = api.Add(buf, output[i][j])
			}
		}
	}

	return output
}

func (circuit *MatMulCircuit) Define(api frontend.API) error {
	output := MatMul(api, circuit.A, circuit.B)
	api.AssertIsEqual(output, circuit.Y)
	return nil
}

While testing, I am receiving the following error. Received unexpected error: parse circuit: [][]frontend.Variable to big.Int not supported frontend.parseCircuit.func2

My test looks like this:

  AObj := make([][]frontend.Variable, 3)
BObj := make([][]frontend.Variable, 3)
YObj := make([][]frontend.Variable, 3)

for i := 0; i < 3; i++ {
	AObj[i] = make([]frontend.Variable, 3)
}
for i := 0; i < 3; i++ {
	BObj[i] = make([]frontend.Variable, 2)
}
for i := 0; i < 3; i++ {
	YObj[i] = make([]frontend.Variable, 2)
}

matmul_circuit := MatMulCircuit{
	A: AObj,
	B: BObj,
	Y: YObj,
}
// Correctness
assert.ProverSucceeded(&matmul_circuit, &MatMulCircuit{
	A: [][]frontend.Variable{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
	B: [][]frontend.Variable{{0, 0}, {0, 0}, {0, 0}},
	Y: [][]frontend.Variable{{0, 0}, {0, 0}, {0, 0}},
}, test.WithBackends(backend.PLONK), test.WithCurves(ecc.BN254))

Can anyone kindly help me with where its going wrong?

[ivokub]

Hi, you are doing api.AssertIsEqual(output, circuit.Y), but both are of types [][]frontend.Variable. api.AssertIsEqual works on frontend.Variable types not, slice types. The following works

package matmul

import (
	"fmt"
	"testing"

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

type MatMulCircuit struct {
	A [][]frontend.Variable
	B [][]frontend.Variable
	Y [][]frontend.Variable
}

func MatMul(api frontend.API, A [][]frontend.Variable, B [][]frontend.Variable) [][]frontend.Variable {
	output := make([][]frontend.Variable, len(A))

	for i := 0; i < len(A); i++ {
		output[i] = make([]frontend.Variable, len(B[0]))
		for j := 0; j < len(B[0]); j++ {
			output[i][j] = frontend.Variable(0)
			for k := 0; k < len(A[0]); k++ {
				buf := api.Mul(A[i][k], B[k][j])
				output[i][j] = api.Add(buf, output[i][j])
			}
		}
	}

	return output
}

func (circuit *MatMulCircuit) Define(api frontend.API) error {
	output := MatMul(api, circuit.A, circuit.B)
	if len(output) != len(circuit.Y) {
		return fmt.Errorf("length mismatch")
	}
	for i := range output {
		if len(output[i]) != len(circuit.Y[i]) {
			return fmt.Errorf("length mismatch")
		}
		for j := range output[i] {
			api.AssertIsEqual(output[i][j], circuit.Y[i][j])
		}
	}
	return nil
}

func TestMatmul(t *testing.T) {
	assert := test.NewAssert(t)

	AObj := make([][]frontend.Variable, 3)
	BObj := make([][]frontend.Variable, 3)
	YObj := make([][]frontend.Variable, 3)

	for i := 0; i < 3; i++ {
		AObj[i] = make([]frontend.Variable, 3)
	}
	for i := 0; i < 3; i++ {
		BObj[i] = make([]frontend.Variable, 2)
	}
	for i := 0; i < 3; i++ {
		YObj[i] = make([]frontend.Variable, 2)
	}

	matmul_circuit := MatMulCircuit{
		A: AObj,
		B: BObj,
		Y: YObj,
	}
	// Correctness
	assert.ProverSucceeded(&matmul_circuit, &MatMulCircuit{
		A: [][]frontend.Variable{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
		B: [][]frontend.Variable{{0, 0}, {0, 0}, {0, 0}},
		Y: [][]frontend.Variable{{0, 0}, {0, 0}, {0, 0}},
	}, test.WithBackends(backend.PLONK), test.WithCurves(ecc.BN254))
}

[ivokub]

Additional note - you could try using Freivalds algorithm using api.Commit. It should be significantly more efficient for large inputs.

[sid-alluri]

Hi @ivokub

I am trying to implement Freivalds.

1. How to generate the randomness safely?
2. Build fails when using api.Commit with error api.Commit undefined (type frontend.API has no field or method Commit), how should I use commitment?

[ivokub]

See multicommit. It is an easier interface to work with commitments.

[sid-alluri]

Thank you so much for the help.