Circuit for proof of ownership of private key

[myronrotter]

I have been working on a circuit for a proof of ownership of a private key.
The circuit computes the public key given the input private key and matches the computed public key with the input public key.

package gnark

import (
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/std/algebra/twistededwards"
	"github.com/consensys/gnark/std/signature/eddsa"
	"github.com/consensys/gurvy"
)

// OwnershipSkCircuit defines circuit for proof of ownership of sk
type OwnershipSkCircuit struct {
	Pk eddsa.PublicKey `gnark:",public"`
	Sk frontend.Variable
}

// Define declares the circuit's constraints
func (circuit *OwnershipSkCircuit) Define(curveID gurvy.ID, cs *frontend.ConstraintSystem) error {
	params, err := twistededwards.NewEdCurve(curveID)
	if err != nil {
		return err
	}
	circuit.Pk.Curve = params

	computedPk := twistededwards.Point{}
	computedPk.ScalarMulFixedBase(cs, circuit.Pk.Curve.BaseX, circuit.Pk.Curve.BaseY, circuit.Sk, circuit.Pk.Curve)
	computedPk.MustBeOnCurve(cs, circuit.Pk.Curve)

	cs.AssertIsEqual(circuit.Pk.A.X, computedPk.X)
	cs.AssertIsEqual(circuit.Pk.A.Y, computedPk.Y)

	return nil
}

I wrote tests for the circuit similar to the tests of the std lib eddsa tests here, see below.
To my surprise, the tests pass for curve bn256 and bls381 but fail for bls377 and bw761.
Cannot find the issue in the circuit and tests, any suggestion would be greatly appreciated.

package gnark

import (
	"math/rand"
	"testing"

	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/crypto/signature"

	eddsabls377 "github.com/consensys/gnark/crypto/signature/eddsa/bls377"
	eddsabls381 "github.com/consensys/gnark/crypto/signature/eddsa/bls381"
	eddsabn256 "github.com/consensys/gnark/crypto/signature/eddsa/bn256"
	eddsabw761 "github.com/consensys/gnark/crypto/signature/eddsa/bw761"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gurvy"
	edwardsbls377 "github.com/consensys/gurvy/bls377/twistededwards"
	edwardsbls381 "github.com/consensys/gurvy/bls381/twistededwards"
	edwardsbn256 "github.com/consensys/gurvy/bn256/twistededwards"
	edwardsbw761 "github.com/consensys/gurvy/bw761/twistededwards"
)

func parseKeys(id gurvy.ID, pubKeyBuf []byte, privKeyBuf []byte) ([]byte, []byte, []byte) {
	var pointbn256 edwardsbn256.PointAffine
	var pointbls381 edwardsbls381.PointAffine
	var pointbls377 edwardsbls377.PointAffine
	var pointbw761 edwardsbw761.PointAffine

	switch id {
	case gurvy.BN256:
		pointbn256.SetBytes(pubKeyBuf[:32])
		aX := pointbn256.X.Bytes()
		aY := pointbn256.Y.Bytes()
		scalar := privKeyBuf[32:64]
		return aX[:], aY[:], scalar
	case gurvy.BLS381:
		pointbls381.SetBytes(pubKeyBuf[:32])
		aX := pointbls381.X.Bytes()
		aY := pointbls381.Y.Bytes()
		scalar := privKeyBuf[32:64]
		return aX[:], aY[:], scalar
	case gurvy.BLS377:
		pointbls377.SetBytes(pubKeyBuf[:32])
		aX := pointbls377.X.Bytes()
		aY := pointbls377.Y.Bytes()
		scalar := privKeyBuf[32:64]
		return aX[:], aY[:], scalar
	case gurvy.BW761:
		pointbw761.SetBytes(pubKeyBuf[:48])
		aX := pointbw761.X.Bytes()
		aY := pointbw761.Y.Bytes()
		scalar := privKeyBuf[48:96]
		return aX[:], aY[:], scalar
	default:
		return pubKeyBuf, pubKeyBuf, privKeyBuf
	}
}

func TestOwnershipSk(t *testing.T) {
	assert := groth16.NewAssert(t)

	signature.Register(signature.EDDSA_BN256, eddsabn256.GenerateKeyInterfaces)
	signature.Register(signature.EDDSA_BLS381, eddsabls381.GenerateKeyInterfaces)
	signature.Register(signature.EDDSA_BLS377, eddsabls377.GenerateKeyInterfaces)
	signature.Register(signature.EDDSA_BW761, eddsabw761.GenerateKeyInterfaces)

	confs := map[gurvy.ID]signature.SignatureScheme{
		gurvy.BN256:  signature.EDDSA_BN256,
		gurvy.BLS381: signature.EDDSA_BLS381,
		gurvy.BLS377: signature.EDDSA_BLS377,
		gurvy.BW761:  signature.EDDSA_BW761,
	}

	for id, ss := range confs {
		var ownershipSkCircuit OwnershipSkCircuit
		r1cs, err := frontend.Compile(id, &ownershipSkCircuit)
		assert.NoError(err)

		// Correct sk, pk
		{
			// Generate eddsa sk, pk
			src := rand.NewSource(0)
			r := rand.New(src)
			privKey, err := ss.New(r)
			assert.NoError(err)
			pubKey := privKey.Public()

			// Parse sk, pk
			pubkeyAx, pubkeyAy, privkeyScalar := parseKeys(id, pubKey.Bytes(), privKey.Bytes())

			var witness OwnershipSkCircuit
			witness.Pk.A.X.Assign(pubkeyAx)
			witness.Pk.A.Y.Assign(pubkeyAy)
			witness.Sk.Assign(privkeyScalar)

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

		// Incorrect sk, pk
		{
			var witness OwnershipSkCircuit
			witness.Pk.A.X.Assign(42)
			witness.Pk.A.Y.Assign(42)
			witness.Sk.Assign(42)

			assert.SolvingFailed(r1cs, &witness)
			//assert.ProverFailed(r1cs, &witness)
		}
	}
}

gnark version: v0.3.9-0.20210121051139-4078ebfe99fc
gurvy version: v0.3.8-0.20210118135515-02bca07c2b11

[ThomasPiellard]

Hi @myronrotter , here is what happens:

• witness.Sk.Assign(privkeyScalar) --> under the hood, privkeyScalar is reduced modulo r (the size of the field in which the variables of the SNARK circuit live, equal to the size of the r-torsion of the pairing curve, eg bn256, bls381, etc)
• During the key generation in eddsa (see signature/eddsa/bn256/eddsa.go, the function GenerateKey for instance), privkeyScalar is taken modulo the cardinality of the twisted Edwards curve.

Both reductions yield 2 different results, hence the discrepancy between what is computed by the circuit and what is computed by the eddsa signature lib. In fact it's deterministic here due to the lack of randomness (source=0), and the scalar is such that there is no reduction in bn256 and bls381, so the test passes.

To correct this, you need to write privkeyScalar in 2 chunks of say 128 bits each, assign each chunk as a 2 different private inputs, and in the circuit you need to do something like

// privkeyScalar = 2**128*chunk1 + chunk2
c1 = chunk1*base
c2 = chunk2*base
computedPubKey = 2**128*c1 + c2

Dividing privkeyScalar like this ensures that chunk1 and chunk2 are not be reduced.