sw_emulated

package
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 19, 2023 License: Apache-2.0 Imports: 13 Imported by: 0

Documentation

Overview

Package sw_emulated 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.

This package implements unified and complete point addition. The method Curve.AddUnified can be used for point additions or in case of points at infinity. As such, this package does not expose separate Add and Double methods.

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/airchains-network/gnark/std/algebra/native/sw_bls12377 and github.com/airchains-network/gnark/std/algebra/native/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.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func GetHints 

func GetHints() []solver.Hint

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.

Point (0,0) represents point at the infinity. This representation is compatible with the EVM representations of points at infinity.

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/airchains-network/gnark/backend/groth16"
	"github.com/airchains-network/gnark/frontend"
	"github.com/airchains-network/gnark/frontend/cs/r1cs"
	"github.com/airchains-network/gnark/std/algebra/emulated/sw_emulated"
	"github.com/airchains-network/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 sw_emulated.AffinePoint[Base]
}

func (c *ExampleCurveCircuit[B, S]) Define(api frontend.API) error {
	curve, err := sw_emulated.New[B, S](api, sw_emulated.GetCurveParams[emulated.Secp256k1Fp]())
	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.AddUnified(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: sw_emulated.AffinePoint[emulated.Secp256k1Fp]{
			X: emulated.ValueOf[emulated.Secp256k1Fp](Q.X),
			Y: emulated.ValueOf[emulated.Secp256k1Fp](Q.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")
	}
}

Output:

result ([5101572491822586484 7988715582840633164 10154617462969804093 9788323565107423858], [12871521579461060004 12592355681102286208 17300415163085174132 96321138099943804])compiled
setup done
secret witness
public witness
proof
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(p, q *AffinePoint[B]) *AffinePoint[B]

Add performs unsafe addition of points p and q. For safe addition use Curve.AddUnified.

func (*Curve[B, S]) AddUnified 

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

AddUnified adds p and q and returns it. It doesn't modify p nor q.

✅ p can be equal to q, and either or both can be (0,0). (0,0) is not on the curve but we conventionally take it as the neutral/infinity point as per the EVM.

It uses the unified formulas of Brier and Joye ([BriJoy02] (Corollary 1)).

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]) AssertIsOnCurve 

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

AssertIsOnCurve asserts if p belongs to the curve. 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]) GeneratorMultiples 

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

GeneratorMultiples returns the pre-computed multiples of the base point of the curve. The method does not copy and modifying the returned element leads to undefined behaviour!

func (*Curve[B, S]) JointScalarMulBase 

func (c *Curve[B, S]) JointScalarMulBase(p *AffinePoint[B], s2, s1 *emulated.Element[S]) *AffinePoint[B]

JointScalarMulBase computes s2 * p + s1 * g and returns it, where g is the fixed generator. It doesn't modify p, s1 and s2.

⚠️ p must NOT be (0,0). ⚠️ s1 and s2 must NOT be 0.

It uses the logic from ScalarMul() for s1 * g and the logic from ScalarMulBase() for s2 * g.

JointScalarMulBase is used to verify an ECDSA signature (r,s) on the secp256k1 curve. In this case, p is a public key, s2=r/s and s1=hash/s.

  • hash cannot be 0, because of pre-image resistance.
  • r cannot be 0, because r is the x coordinate of a random point on secp256k1 (y²=x³+7 mod p) and 7 is not a square mod p. For any other curve, (_,0) is a point of order 2 which is not the prime subgroup.
  • (0,0) is not a valid public key.

The [EVM] specifies these checks, wich are performed on the zkEVM arithmetization side before calling the circuit that uses this method.

This saves the Select logic related to (0,0) and the use of AddUnified to handle the 0-scalar edge case.

func (*Curve[B, S]) Lookup2 

func (c *Curve[B, S]) Lookup2(b0, b1 frontend.Variable, i0, i1, i2, i3 *AffinePoint[B]) *AffinePoint[B]

Lookup2 performs a 2-bit lookup between i0, i1, i2, i3 based on bits b0 and b1. Returns:

  • i0 if b0=0 and b1=0,
  • i1 if b0=1 and b1=0,
  • i2 if b0=0 and b1=1,
  • i3 if b0=1 and b1=1.

func (*Curve[B, S]) MarshalG1 

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

MarshalG1 marshals the affine point into bits. The output is compatible with the point marshalling in gnark-crypto.

func (*Curve[B, S]) MarshalScalar 

func (c *Curve[B, S]) MarshalScalar(s emulated.Element[S]) []frontend.Variable

MarshalScalar marshals the scalar into bits. Compatible with scalar marshalling in gnark-crypto.

func (*Curve[B, S]) MultiScalarMul 

func (c *Curve[B, S]) MultiScalarMul(p []*AffinePoint[B], s []*emulated.Element[S], opts ...algopts.AlgebraOption) (*AffinePoint[B], error)

MultiScalarMul computes the multi scalar multiplication of the points P and scalars s. It returns an error if the length of the slices mismatch. If the input slices are empty, then returns point at infinity.

⚠️ Points and scalars must be nonzero.

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], opts ...algopts.AlgebraOption) *AffinePoint[B]

ScalarMul computes s * p and returns it. It doesn't modify p nor s. This function doesn't check that the p is on the curve. See AssertIsOnCurve.

ScalarMul calls ScalarMulGeneric or scalarMulGLV depending on whether an efficient endomorphism is available.

func (*Curve[B, S]) ScalarMulBase 

func (c *Curve[B, S]) ScalarMulBase(s *emulated.Element[S], opts ...algopts.AlgebraOption) *AffinePoint[B]

ScalarMulBase computes s * g and returns it, where g is the fixed generator. It doesn't modify s.

✅ When s=0, it returns (0,0). (0,0) is not on the curve but we conventionally take it as the neutral/infinity point as per the EVM.

It computes the standard little-endian fixed-base double-and-add algorithm HMV04 (Algorithm 3.26), with the points [2^i]g precomputed. The bits at positions 1 and 2 are handled outside of the loop to optimize the number of constraints using a Lookup2 with pre-computed [3]g, [5]g and [7]g points.

func (*Curve[B, S]) ScalarMulGeneric 

func (c *Curve[B, S]) ScalarMulGeneric(p *AffinePoint[B], s *emulated.Element[S], opts ...algopts.AlgebraOption) *AffinePoint[B]

ScalarMulGeneric computes s * p and returns it. It doesn't modify p nor s. This function doesn't check that the p is on the curve. See AssertIsOnCurve.

✅ p can can be (0,0) and s can be 0. (0,0) is not on the curve but we conventionally take it as the neutral/infinity point as per the EVM.

It computes the right-to-left variable-base double-and-add algorithm (Joye07, Alg.1).

Since we use incomplete formulas for the addition law, we need to start with a non-zero accumulator point (R0). To do this, we skip the LSB (bit at position 0) and proceed assuming it was 1. At the end, we conditionally subtract the initial value (p) if LSB is 1. We also handle the bits at positions 1 and n-1 outside of the loop to optimize the number of constraints using ELM03 (Section 3.1)

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 == 1, 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
	Gm           [][2]*big.Int // m*base point coords
	Eigenvalue   *big.Int      // endomorphism eigenvalue
	ThirdRootOne *big.Int      // endomorphism image scaler
}

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 GetBLS12381Params 

func GetBLS12381Params() CurveParams

GetBLS12381Params returns the curve parameters for the curve BLS12-381. When initialising new curve, use the base field emulated.BLS12381Fp and scalar field emulated.BLS12381Fr.

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 GetBW6761Params 

func GetBW6761Params() CurveParams

GetBW6761Params returns the curve parameters for the curve BW6-761. When initialising new curve, use the base field emulated.BW6761Fp and scalar field emulated.BW6761Fr.

func GetCurveParams 

func GetCurveParams[Base emulated.FieldParams]() CurveParams

GetCurveParams returns suitable curve parameters given the parametric type Base as base field. It caches the parameters and modifying the values in the parameters struct leads to undefined behaviour.

func GetP256Params 

func GetP256Params() CurveParams

GetP256Params returns the curve parameters for the curve P-256 (also SECP256r1). When initialising new curve, use the base field emulated.P256Fp and scalar field emulated.P256Fr.

func GetP384Params 

func GetP384Params() CurveParams

GetP384Params returns the curve parameters for the curve P-384 (also SECP384r1). When initialising new curve, use the base field emulated.P384Fp and scalar field emulated.P384Fr.

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.