algebra

package
v0.2.13 Latest Latest
Warning

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

Go to latest
Published: Feb 6, 2024 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Overview

Package algebra implements:

  • base finite field 𝔽p arithmetic,
  • extension finite fields arithmetic (𝔽p², 𝔽p⁴, 𝔽p⁶, 𝔽p¹², 𝔽p²⁴),
  • short Weierstrass curve arithmetic over G1 (E/𝔽p) and G2 (Eₜ/𝔽p² or Eₜ/𝔽p⁴)
  • twisted Edwards curve arithmetic

These arithmetic operations are implemented

  • using native field via the 2-chains BLS12-377/BW6-761 and BLS24-315/BW-633 (`native/`) or associated twisted Edwards (e.g. Jubjub/BLS12-381) and
  • using nonnative field via field emulation (`emulated/`). This allows to use any curve over any (SNARK) field (e.g. secp256k1 curve arithmetic over BN254 SNARK field or BN254 pairing over BN254 SNARK field). The drawback of this approach is the additional cost (~15x) of the operations.

This package also defines the generic interfaces Curve and Pairing for downstream curve-agnostic usage.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Curve

type Curve[FR emulated.FieldParams, G1El G1ElementT] interface {
	// AddUnified adds _any_ two points and returns the sum. It does not modify the input
	// points.
	AddUnified(*G1El, *G1El) *G1El

	// Add adds two points and returns the sum. It does not modify the input
	// points.
	Add(*G1El, *G1El) *G1El

	// AssertIsEqual asserts that two points are equal.
	AssertIsEqual(*G1El, *G1El)

	// Neg negates the points and returns a negated point. It does not modify
	// the input.
	Neg(*G1El) *G1El

	// ScalarMul returns the scalar multiplication of the point by a scalar. It
	// does not modify the inputs.
	//
	// Depending on the implementation the scalar multiplication may be
	// incomplete for zero scalar or point at infinity. To allow the exceptional
	// case use the [algopts.WithCompleteArithmetic] option.
	ScalarMul(*G1El, *emulated.Element[FR], ...algopts.AlgebraOption) *G1El

	// ScalarMulBase returns the scalar multiplication of the curve base point
	// by a scalar. It does not modify the scalar.
	//
	// Depending on the implementation the scalar multiplication may be
	// incomplete for zero scalar. To allow the exceptional case use the
	// [algopts.WithCompleteArithmetic] option.
	ScalarMulBase(*emulated.Element[FR], ...algopts.AlgebraOption) *G1El

	// MultiScalarMul computes the sum ∑ s_i P_i for the input
	// scalars s_i and points P_i. It returns an error if the input lengths
	// mismatch.
	//
	// Depending on the implementation the scalar multiplication may be
	// incomplete for zero scalar or point at infinity. To allow the exceptional
	// case use the [algopts.WithCompleteArithmetic] option.
	MultiScalarMul([]*G1El, []*emulated.Element[FR], ...algopts.AlgebraOption) (*G1El, error)

	// MarshalG1 returns the binary decomposition G1.X || G1.Y. It matches the
	// output of gnark-crypto's Marshal method on G1 points.
	MarshalG1(G1El) []frontend.Variable

	// MarshalScalar returns the binary decomposition of the argument.
	MarshalScalar(emulated.Element[FR]) []frontend.Variable

	// Select sets p1 if b=1, p2 if b=0, and returns it. b must be boolean constrained
	Select(b frontend.Variable, p1 *G1El, p2 *G1El) *G1El

	// Lookup2 performs a 2-bit lookup between p1, p2, p3, p4 based on bits b0  and b1.
	// Returns:
	//   - p1 if b0=0 and b1=0,
	//   - p2 if b0=1 and b1=0,
	//   - p3 if b0=0 and b1=1,
	//   - p4 if b0=1 and b1=1.
	Lookup2(b1 frontend.Variable, b2 frontend.Variable, p1 *G1El, p2 *G1El, p3 *G1El, p4 *G1El) *G1El

	// Mux performs a lookup from the inputs and returns inputs[sel]. It is most
	// efficient for power of two lengths of the inputs, but works for any
	// number of inputs.
	Mux(sel frontend.Variable, inputs ...*G1El) *G1El
}

Curve defines group operations on an elliptic curve.

func GetCurve

func GetCurve[FR emulated.FieldParams, G1El G1ElementT](api frontend.API) (Curve[FR, G1El], error)

GetCurve returns the Curve implementation corresponding to the scalar and G1 type parameters. The method allows to have a fully generic implementation without taking into consideration the initialization differences of different curves.

type G1ElementT

type G1ElementT GroupElementT

type G2ElementT

type G2ElementT GroupElementT

type GroupElementT

type GroupElementT any

type GtElementT

type GtElementT GroupElementT

type Pairing

type Pairing[G1El G1ElementT, G2El G2ElementT, GtEl GtElementT] interface {
	// MillerLoop computes the Miller loop of the input pairs. It returns error
	// when the inputs are of mismatching length. It does not modify the inputs.
	MillerLoop([]*G1El, []*G2El) (*GtEl, error)

	// FinalExponentiation computes the final step in the pairing. It does not
	// modify the inputs.
	FinalExponentiation(*GtEl) *GtEl

	// Pair computes the full pairing of the input pairs. It returns error when
	// the inputs are of mismatching length. It does not modify the inputs.
	Pair([]*G1El, []*G2El) (*GtEl, error)

	// PairingCheck asserts that the pairing result is 1. It returns an error
	// when the inputs are of mismatching length. It does not modify the inputs.
	PairingCheck([]*G1El, []*G2El) error

	// AssertIsEqual asserts the equality of the inputs.
	AssertIsEqual(*GtEl, *GtEl)
}

Pairing allows to compute the bi-linear pairing of G1 and G2 elements. Additionally, the interface provides steps used in pairing computation and a dedicated optimised pairing check.

func GetPairing

func GetPairing[G1El G1ElementT, G2El G2ElementT, GtEl GtElementT](api frontend.API) (Pairing[G1El, G2El, GtEl], error)

GetPairing returns the Pairing implementation corresponding to the groups type parameters. The method allows to have a fully generic implementation without taking into consideration the initialization differences.

Directories

Path Synopsis
Package algopts provides shareable options for modifying algebraic operations.
Package algopts provides shareable options for modifying algebraic operations.
emulated
fields_bls12381
Package fields_bls12381 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BLS12-381 curve.
Package fields_bls12381 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BLS12-381 curve.
fields_bn254
Package fields_bn254 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BN254 curve.
Package fields_bn254 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BN254 curve.
fields_bw6761
Package fields_bw6761 implements the fields arithmetic of the Fp6 tower used to compute the pairing over the BW6-761 curve.
Package fields_bw6761 implements the fields arithmetic of the Fp6 tower used to compute the pairing over the BW6-761 curve.
sw_bls12381
Package sw_bls12381 implements G1 and G2 arithmetics and pairing computation over BLS12-381 curve.
Package sw_bls12381 implements G1 and G2 arithmetics and pairing computation over BLS12-381 curve.
sw_bn254
Package sw_bn254 implements G1 and G2 arithmetics and pairing computation over BN254 curve.
Package sw_bn254 implements G1 and G2 arithmetics and pairing computation over BN254 curve.
sw_bw6761
Package sw_bw6761 implements G1 and G2 arithmetics and pairing computation over BW6-761 curve.
Package sw_bw6761 implements G1 and G2 arithmetics and pairing computation over BW6-761 curve.
sw_emulated
Package sw_emulated implements elliptic curve group operations in (short) Weierstrass form.
Package sw_emulated implements elliptic curve group operations in (short) Weierstrass form.
native
fields_bls12377
Package fields_bls12377 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BLS12-377 curve.
Package fields_bls12377 implements the fields arithmetic of the Fp12 tower used to compute the pairing over the BLS12-377 curve.
fields_bls24315
Package fields_bls24315 implements the fields arithmetic of the Fp24 tower used to compute the pairing over the BLS24-315 curve.
Package fields_bls24315 implements the fields arithmetic of the Fp24 tower used to compute the pairing over the BLS24-315 curve.
sw_bls12377
Package sw_bls12377 implements the arithmetics of G1, G2 and the pairing computation on BLS12-377 as a SNARK circuit over BW6-761.
Package sw_bls12377 implements the arithmetics of G1, G2 and the pairing computation on BLS12-377 as a SNARK circuit over BW6-761.
sw_bls24315
Package sw_bls24315 implements the arithmetics of G1, G2 and the pairing computation on BLS24-315 as a SNARK circuit over BW6-633.
Package sw_bls24315 implements the arithmetics of G1, G2 and the pairing computation on BLS24-315 as a SNARK circuit over BW6-633.
twistededwards
Package twistededwards implements the arithmetic of twisted Edwards curves in native fields.
Package twistededwards implements the arithmetic of twisted Edwards curves in native fields.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL