weierstrass

Documentation

Overview

Package weierstrass implements elliptic curve group operations in (short) Weierstrass form.

The elliptic curve is the set of points (X,Y) satisfying the equation:

Y² = X³ + aX + b

over some base field 𝐅p for some constants a, b ∈ 𝐅p. Additionally, for every curve we also define its generator (base point) G. All these parameters are stored in the variable of type CurveParams.

The package provides a few curve parameters, see functions GetSecp256k1Params and GetBN254Params.

Unconventionally, this package uses type parameters to define the base field of the points and variables to define the coefficients of the curve. This is due to how the emulated elements are constructed by their type parameters. To unify the different conventions, we provide the method GetCurveParams to allow resolving a particular curve parameter depending on the type parameter defining the base field. For now, we only have a single curve defined on every base field, but this may change in the future with the addition of additional curves.

This package uses field emulation (unlike packages github.com/BeratOz01/gnark/std/algebra/sw_bls12377 and github.com/BeratOz01/gnark/std/algebra/sw_bls24315, which use 2-chains). This allows to use any curve over any native (SNARK) field. The drawback of this approach is the extreme cost of the operations. In R1CS, point addition on 256-bit fields is approximately 3500 constraints and doubling is approximately 4300 constraints. A full scalar multiplication is approximately 2M constraints. It is several times more in PLONKish aritmetisation.

Index

• type AffinePoint
• type Curve
  • func New[Base, Scalars emulated.FieldParams](api frontend.API, params CurveParams) (*Curve[Base, Scalars], error)
  • func (c *Curve[B, S]) Add(q, r *AffinePoint[B]) *AffinePoint[B]
  • func (c *Curve[B, S]) AssertIsEqual(p, q *AffinePoint[B])
  • func (c *Curve[B, S]) Double(p *AffinePoint[B]) *AffinePoint[B]
  • func (c *Curve[B, S]) Generator() *AffinePoint[B]
  • func (c *Curve[B, S]) Neg(p *AffinePoint[B]) *AffinePoint[B]
  • func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *AffinePoint[B]
  • func (c *Curve[B, S]) Select(b frontend.Variable, p, q *AffinePoint[B]) *AffinePoint[B]
• type CurveParams
  • func GetBN254Params() CurveParams
  • func GetCurveParams[Base emulated.FieldParams]() CurveParams
  • func GetSecp256k1Params() CurveParams

Examples

• Curve

Types

type AffinePoint

type AffinePoint[Base emulated.FieldParams] struct {
	X, Y emulated.Element[Base]
}

AffinePoint represents a point on the elliptic curve. We do not check that the point is actually on the curve.

type Curve

type Curve[Base, Scalars emulated.FieldParams] struct {
	// contains filtered or unexported fields
}

Curve is an initialised curve which allows performing group operations.

Example

package main

import (
	"fmt"
	"math/big"

	"github.com/BeratOz01/gnark/backend/groth16"
	"github.com/BeratOz01/gnark/frontend"
	"github.com/BeratOz01/gnark/frontend/cs/r1cs"
	"github.com/BeratOz01/gnark/std/algebra/weierstrass"
	"github.com/BeratOz01/gnark/std/math/emulated"
	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark-crypto/ecc/secp256k1"
)

type ExampleCurveCircuit[Base, Scalar emulated.FieldParams] struct {
	Res weierstrass.AffinePoint[Base]
}

func (c *ExampleCurveCircuit[B, S]) Define(api frontend.API) error {
	curve, err := weierstrass.New[B, S](api, weierstrass.GetCurveParams[emulated.BN254Fp]())
	if err != nil {
		panic("initalize new curve")
	}
	G := curve.Generator()
	scalar4 := emulated.ValueOf[S](4)
	g4 := curve.ScalarMul(G, &scalar4) // 4*G
	scalar5 := emulated.ValueOf[S](5)
	g5 := curve.ScalarMul(G, &scalar5) // 5*G
	g9 := curve.Add(g4, g5)            // 9*G
	curve.AssertIsEqual(g9, &c.Res)
	return nil
}

func main() {
	s := big.NewInt(9)
	_, g := secp256k1.Generators()
	var Q secp256k1.G1Affine
	Q.ScalarMultiplication(&g, s)
	fmt.Printf("result (%d, %d)", Q.X, Q.Y)

	circuit := ExampleCurveCircuit[emulated.Secp256k1Fp, emulated.Secp256k1Fr]{}
	witness := ExampleCurveCircuit[emulated.Secp256k1Fp, emulated.Secp256k1Fr]{
		Res: weierstrass.AffinePoint[emulated.Secp256k1Fp]{
			X: emulated.ValueOf[emulated.Secp256k1Fp](g.X),
			Y: emulated.ValueOf[emulated.Secp256k1Fp](g.Y),
		},
	}
	ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		panic(err)
	} else {
		fmt.Println("compiled")
	}
	pk, vk, err := groth16.Setup(ccs)
	if err != nil {
		panic(err)
	} else {
		fmt.Println("setup done")
	}
	secretWitness, err := frontend.NewWitness(&witness, ecc.BN254.ScalarField())
	if err != nil {
		panic(err)
	} else {
		fmt.Println("secret witness")
	}
	publicWitness, err := secretWitness.Public()
	if err != nil {
		panic(err)
	} else {
		fmt.Println("public witness")
	}
	proof, err := groth16.Prove(ccs, pk, secretWitness)
	if err != nil {
		panic(err)
	} else {
		fmt.Println("proof")
	}
	err = groth16.Verify(proof, vk, publicWitness)
	if err != nil {
		panic(err)
	} else {
		fmt.Println("verify")
	}
}

func New

func New[Base, Scalars emulated.FieldParams](api frontend.API, params CurveParams) (*Curve[Base, Scalars], error)

New returns a new Curve instance over the base field Base and scalar field Scalars defined by the curve parameters params. It returns an error if initialising the field emulation fails (for example, when the native field is too small) or when the curve parameters are incompatible with the fields.

func (*Curve[B, S]) Add

func (c *Curve[B, S]) Add(q, r *AffinePoint[B]) *AffinePoint[B]

Add adds q and r and returns it.

func (*Curve[B, S]) AssertIsEqual

func (c *Curve[B, S]) AssertIsEqual(p, q *AffinePoint[B])

AssertIsEqual asserts that p and q are the same point.

func (*Curve[B, S]) Double

func (c *Curve[B, S]) Double(p *AffinePoint[B]) *AffinePoint[B]

Double doubles p and return it. It doesn't modify p.

func (*Curve[B, S]) Generator

func (c *Curve[B, S]) Generator() *AffinePoint[B]

Generator returns the base point of the curve. The method does not copy and modifying the returned element leads to undefined behaviour!

func (*Curve[B, S]) Neg

func (c *Curve[B, S]) Neg(p *AffinePoint[B]) *AffinePoint[B]

Neg returns an inverse of p. It doesn't modify p.

func (*Curve[B, S]) ScalarMul

func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *AffinePoint[B]

ScalarMul computes s * p and returns it. It doesn't modify p nor s.

func (*Curve[B, S]) Select

func (c *Curve[B, S]) Select(b frontend.Variable, p, q *AffinePoint[B]) *AffinePoint[B]

Select selects between p and q given the selector b. If b == 0, then returns p and q otherwise.

type CurveParams

type CurveParams struct {
	A  *big.Int // a in curve equation
	B  *big.Int // b in curve equation
	Gx *big.Int // base point x
	Gy *big.Int // base point y
}

CurveParams defines parameters of an elliptic curve in short Weierstrass form given by the equation

Y² = X³ + aX + b

The base point is defined by (Gx, Gy).

func GetBN254Params

func GetBN254Params() CurveParams

GetBN254Params returns the curve parameters for the curve BN254 (alt_bn128). When initialising new curve, use the base field emulated.BN254Fp and scalar field emulated.BN254Fr.

func GetCurveParams

func GetCurveParams[Base emulated.FieldParams]() CurveParams

GetCurveParams returns suitable curve parameters given the parametric type Base as base field.

func GetSecp256k1Params

func GetSecp256k1Params() CurveParams

GetSecp256k1Params returns curve parameters for the curve secp256k1. When initialising new curve, use the base field emulated.Secp256k1Fp and scalar field emulated.Secp256k1Fr.