Zero Knowledge Proofs Within A secp256k1 Finite Field

The day I got cryptography was the day that I understood finite fields, and where we use a prime number (p) with a (mod p) operation. The great thing about using (mod p) is that our normal maths operations still hold. For example, if x=65 and y=72, and with p=97, we get:

z = 65 + 72 (mod 97) = 40 (mod 97)

z = 65 x 72 (mod 97) = 24 (mod 97)

z = 65 — 72 (mod 97) = 90 (mod 97)

In this case, we will create a zero knowledge proof using a secp256k1 finite field for x multiplied by y. Overall, secp256k1 is the Bitcoin and Ethereum elliptic curve, and is used for ECDSA signatures.

Zero Knowledge Proofs

PLONK is part of the SNARK (Succinct Non-Interactive Arguments of Knowledge) family of zero-knowledge proofs. With this, we aim to prove that a polynomial f(x) vanishes within a given domain. In this case, we will define a circuit for the secp256k1 field, where we multiply x and y and discover res=x.y within the field of secp256k1. Overall, we work within a finite field of 2²⁵⁶−2³²−977. Thus we have:

res=x×y (mod 2²⁵⁶−2³²−977).

PLONK is part of the SNARK (Succinct Non-Interactive Arguments of Knowledge) family of zero-knowledge proofs. It is a polynomial commitment scheme and that uses elliptic curve pairing. This is typically BN-254 or BLS12–381. With a SNARK, we generally:

• Represent the program as an arithmetic circuit. This involves defining the proof formula with addition and multiplication gates. This format is defined as R1CS [here].
• Convert the circuit description into a polynomial identity. his coverts the arithmetic circuit into polynomials. .
• Commit using a Polynomial Commitment Scheme.
• Evaluate the polynomials at a random point.

An example of the circuit to represent the sepc256k1 field, and where the prime number used is 2²⁵⁶−2³²−977. For this we can define that there are X and Y inputs and a Res output:

type Circuit struct {
	// Limbs of non-native elements X, Y and Res
	X, Y, Res emulated.Element[emulated.Secp256k1Fp]
}

And then we can define the constraints for the circuit, and where we use a secp256k1 finite field and where we multiply x and y:

func (circuit *Circuit) Define(api frontend.API) error {
	// wrap API to work in SECP256k1 scalar field
	secp256k1, err := emulated.NewField[emulated.Secp256k1Fp](api)
	if err != nil {
		return err
	}
 tmp := secp256k1.Mul(&circuit.X, &circuit.Y)
 secp256k1.AssertIsEqual(tmp, &circuit.Res)
 return nil
}

Coding

The outline code is (based on [here]) [here]:

package main
import (
 "fmt"
 "github.com/consensys/gnark-crypto/ecc"
 "github.com/consensys/gnark/backend/plonk"
 cs "github.com/consensys/gnark/constraint/bn254"
 "github.com/consensys/gnark/frontend/cs/scs"
 "github.com/consensys/gnark/logger"
 "os"
 "github.com/consensys/gnark/frontend"
 "github.com/consensys/gnark/std/math/emulated"
 "github.com/consensys/gnark/test/unsafekzg"
 "math/big"
)
type Circuit struct {
 // Limbs of non-native elements X, Y and Res
 X, Y, Res emulated.Element[emulated.Secp256k1Fp]
}
func (circuit *Circuit) Define(api frontend.API) error {
 // wrap API to work in SECP256k1 scalar field
 secp256k1, err := emulated.NewField[emulated.Secp256k1Fp](api)
 if err != nil {
  return err
 }
 tmp := secp256k1.Mul(&circuit.X, &circuit.Y)
 secp256k1.AssertIsEqual(tmp, &circuit.Res)
 return nil
}
func main() {
 var circuit Circuit
 logger.Disable()
 var w Circuit
 xval := "48439561293906451759052585252797914202762949526041747995844080717082404635286"
 yval := "48439561293906451759052585252797914202762949526041747995844080717082404635286"
 argCount := len(os.Args[1:])
 if argCount > 0 {
  xval = os.Args[1]
 }
 if argCount > 1 {
  yval = os.Args[2]
 }
 w.X = emulated.ValueOf[emulated.Secp256k1Fp](xval)
 w.Y = emulated.ValueOf[emulated.Secp256k1Fp](yval)
 p1, _ := new(big.Int).SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16)
 x, _ := new(big.Int).SetString(xval, 10)
 y, _ := new(big.Int).SetString(yval, 10)
 var res = new(big.Int).Mul(x, y)
 res = new(big.Int).Mod(res, p1)
 w.Res = emulated.ValueOf[emulated.Secp256k1Fp](res)
 fmt.Printf("Using secp256k1 field: %s times %s  = %s\n\n", x, y, res)
 fmt.Println("Compiling circuit")
 ccs, err := frontend.Compile(ecc.BN254.ScalarField(), scs.NewBuilder, &circuit)
 if err != nil {
  fmt.Println("circuit compilation error")
 }
 scs := ccs.(*cs.SparseR1CS)
 srs, srsLagrange, err := unsafekzg.NewSRS(scs)
 if err != nil {
  fmt.Printf("%s", err)
 }
 fmt.Println("Creating witness")
 witnessFull, err := frontend.NewWitness(&w, ecc.BN254.ScalarField())
 if err != nil {
  fmt.Printf("%s", err)
 }
 fmt.Println("Public witness")
 witnessPublic, err := frontend.NewWitness(&w, ecc.BN254.ScalarField(), frontend.PublicOnly())
 if err != nil {
  fmt.Printf("%s", err)
 }
 fmt.Println("Setup Plonk")
 pk, vk, err := plonk.Setup(ccs, srs, srsLagrange)
 //_, err := plonk.Setup(r1cs, kate, &publicWitness)
 if err != nil {
  fmt.Printf("%s", err)
  os.Exit(0)
 }
 fmt.Println("Plonk Prove")
 proof, err := plonk.Prove(ccs, pk, witnessFull)
 if err != nil {
  fmt.Printf("%s", err)
  os.Exit(0)
 }
 fmt.Println("Plonk Verify")
 err = plonk.Verify(proof, vk, witnessPublic)
 if err != nil {
  fmt.Printf("Invalid proof")
 } else {
  fmt.Printf("Valid proof")
 }
}

A sample run for using x=48439561293906451759052585252797914202762949526041747995844080717082404635286 and y=48439561293906451759052585252797914202762949526041747995844080717082404635286 is [here]:

Using secp256k1 field: 48439561293906451759052585252797914202762949526041747995844080717082404635286 
times 48439561293906451759052585252797914202762949526041747995844080717082404635286  
= 14903764848667712212525216627803476226655225230958913533217812035779103341130

Compiling circuit
Creating witness
Public witness
Setup Plonk
Plonk Prove
Plonk Verify
Valid proof

If we check with Python, we get [here]:

>>> p= 2**256 - 2**32 - 977
>>> x=48439561293906451759052585252797914202762949526041747995844080717082404635286
>>> y=48439561293906451759052585252797914202762949526041747995844080717082404635286
>>> print ((x*y) % p)
14903764848667712212525216627803476226655225230958913533217812035779103341130

and we can see that the zero knowledge proof works.

Conclusions

If you are interested in Zero Knowledge Proofs, try here:

https://asecuritysite.com/zero