A Zero Knowledge Proof That A Point Is On The secp256k1 Curve

Implementing a ZKP SNARK for an (x,y) point

I love elliptic curves, and implementing Zero Knowledge Proofs, so let’s integrate them together.

The mighty secp256k1 curve

Satoshi Nakamoto selected the secp256k1 curve and the ECDSA signature for Bitcoin, and which has since been the foundation for cryptocurrency and Blockchain methods. This includes its usage in Ethereum. The core form of the elliptic curve is:

y²=x³+7 (mod p)

and where p=2²⁵⁶−2³²−977.

This gives us (x,y) points on the curve. With secp256k1, we then use a base point (G), and then have a secret key scale of sk. The public key is then a point at sk.G.

The base point of G is at:

(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424).

For 2.G, we get:

(89565891926547004231252920425935692360644145829622209833684329913297188986597, 12158399299693830322967808612713398636155367887041628176798871954788371653930).

If we have x=1, then we have a point at:

(1, 29896722852569046015560700294576055776214335159245303116488692907525646231534).

Here are the first 20 points for secp256k1:

First 10 Elliptic Curve Points for common elliptic curves

So, let’s say I have an elliptic curve point (x,y). Can I produce a Zero Knowledge Proof that this point is on the secp256k1 curve? Well, we can use a SNARK for this, and where we do not have to reveal the (x,y) point, but can prove that it complies with y²=x³+7 (mod p). One of the best SNARK methods is PLONK.

PLONK

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 define 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 we will have an (x,y)

point in the field:

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

And then we can define the constraints for the circuit, and where we use a sepc256k1 finite field and we check that y2=x3+7:

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
 }
 x3 := secp256k1.Mul(&circuit.X, &circuit.X)
 x3 = secp256k1.Mul(x3, &circuit.X)
 val7:=emulated.ValueOf[emulated.Secp256k1Fp]("7")
 x3 = secp256k1.Add(x3,&val7 )
 y2 := secp256k1.Mul(&circuit.Y, &circuit.Y)
 secp256k1.AssertIsEqual(x3, y2)
 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"
)
type Circuit struct {
 // Limbs of non-native elements X, Y
 X, Y 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
 }
 x3 := secp256k1.Mul(&circuit.X, &circuit.X)
 x3 = secp256k1.Mul(x3, &circuit.X)
 val7:=emulated.ValueOf[emulated.Secp256k1Fp]("7")
 x3 = secp256k1.Add(x3,&val7 )
 y2 := secp256k1.Mul(&circuit.Y, &circuit.Y)
 secp256k1.AssertIsEqual(x3, y2)
 return nil
}
func main() {
 var circuit Circuit
 logger.Disable()
 var w Circuit
 xval := "89565891926547004231252920425935692360644145829622209833684329913297188986597"
 yval := "12158399299693830322967808612713398636155367887041628176798871954788371653930"
 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)
 fmt.Printf("Creating ZKP for the point: (%s,%s) \n\n\n", xval, yval)
 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 is [here]:

Creating ZKP for the point: (55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424) 

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

For an incorrect point [here]:

Creating ZKP for the point: (89565891926547004231252920425935692360644145829622209833684329913297188986597,
12158399299693830322967808612713398636155367887041628176798871954788371653939)

Compiling circuit
Creating witness
Public witness
Setup Plonk
Plonk Prove
constraint #2600 is not satisfied: qLâ‹…xa + qRâ‹…xb + qOâ‹…xc + qMâ‹…(xaxb) + qC != 0 â†' 3150270966196088160524337660832903985234975229184314037291491272743120142761 + 1495050520580970511615677875775408417370687709488032764593856053960964183701 + 0 + 0 + 0 != 0
>>> 

If we try x=1, we get [here]:

Creating ZKP for the point: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)

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

Here are some valid and invalid proofs:

• Valid point Try!
• Valid point Try!
• Valid point Try!
• Valid point Try!
• Valid point Try!
• Invalid point Try!
• Invalid point Try!
• Invalid point Try!