Try   HackMD

Yet another curve, but THE curve for your KZG!

With my co-authors Aurore Guillevic and Diego F. Aranha, we published on ePrint mid-May a survey of elliptic curves for proof systems (ePrint 2022/586). Recently, there have been many tailored constructions of these curves that aim at efficiently implementing different kinds of proof systems. In that survey we provide the reader with a comprehensive view on existing work and revisit the contributions in terms of efficiency and security. We present an overview at three stages of the process:

  1. curves to instantiate a SNARK,
  2. curves to instantiate a recursive SNARK, and
  3. curves to express an elliptic-curve related statement.

In this post, we are only interested in the first case. For pairing-based SNARKs, such as the circuit-specific Groth16 [1], bilinear pairings (

e:G1×G2GT) are needed for the proof verification. For universal SNARKs, such as PLONK [2] or Marlin [3], a polynomial commitment scheme is needed. An example of an efficient one is the Kate-Zaverucha-Goldberg (KZG) scheme [4]. The verifier needs to verify some polynomial openings using bilinear pairings.
So far, for both circuit-specific and universal constructions, the verification algorithms boil down mainly to pairing computations. However, the prover work is not the same. For Groth16, it is mainly multi-scalar-multiplications (MSM) in both
G1
and
G2
while for KZG-based schemes it is mainly MSMs in
G1
only. In section 4 of the survey paper, we look at a particular family of pairing-friendly elliptic curves suitable for KZG. We derive algorithm 6 to tailor this family to the SNARK context. Note that KZG is also useful for other compelling applications such as Verkle trees for blockchain stateless clients.

Pairing-friendly curves

A pairing is a non-degenrate bilinear map

e:G1×G2GT(P,Q)e(P,Q)
where

  • G1
    and
    G2
    are groups of order
    r
    defined over elliptic curves (with generators
    G1
    and resp.
    G2
    ) and
  • GT
    is also a group of order
    r
    defined over a finite field extension.

We usually deal with type-3 pairing where

  • G1
    is defined over a curve
    E(Fp)
    ,
    G2
    over
    E(Fpk)
    and
  • GT
    over
    Fpk
    .

The integer

k is defined as the smallest integer such that
rpk1
and
G2
coordinates can be sometimes compressed into a smaller field because
G2
can be isomorphic to the
r
-torsion on a different curve
E(Fpk/d)
for some
d
(the twist degree) that characterizes the curve
E
.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

A pairing-friendly curve construction aims at generating a curve with

k not too big (for efficient arithmetic in
G2
and
GT
) and not too small (for hard discrete logarithm DLP in
GT
). The widely used BLS12-381 curve [5], is defined over a field
Fp
of size 381 bits and has a prime subgroup order
r
of 255 bits. It has
k=12
so
GT
is over
Fp12
and
d=6
so
G2
is over
Fp2
. This curve is derived from the Barreto-Lynn-Scott of embedding degree 12 (BLS12) family and aims at optimizing the computations in all fronts:

  • Fr
    : size is 255 bits (1 spare-bit and hard DL)
  • G1
    : coordinates over a 381-bit field
  • G2
    : coordinates over a 762-bit field (
    381×2
    ) and
    Fp2[u]
    is constructed using the irreducible polynomial
    u2+1
    (
    p3mod4
    )
  • GT
    and pairing: elements over a 4572-bit field and the Hamming weight of the 64-bit Miller loop size (the curve seed for BLS) is just 6.

In some applications as we will see in KZG, not all fronts should be optimized to the same extent. One can for example reduce the size of the

G1 at the cost of the
G2
size.

KZG polynomial commitment

A polynomial commitment scheme allows to commit to a polynomial and then open it at any point (showing that the value of the polynomial at a point is equal to a claimed value, i.e.

p(z)=y).

The protocol

  • (vk,pk)setup(τ,1λ):
    For some security parameter
    λ
    , sample randomly
    τFr
    and then compute
    pk=τiG1
    for
    i{1,,m}
    and
    vk=τG2
    .
  • Ccommit(pk,p):
    given the polynomial
    p(x)Fr[x]
    and the proving key
    pk
    , compute
    C=p(τ)G1=i=0n<mpiτiG1
  • πopen(p,y,z):
    to prove that
    p(z)=y
    , compute the polynomial
    q(x)=(p(x)y)/(xz)
    and then the proof
    π=q(τ)G1
  • 0/1verify(C,π,vk):
    compute
    Pz=zG2
    and
    Py=yG1
    , and then verify that
    e(π,vkPz)=e(CPy,G2)

correctnes:
e(π,vkPz)=e(CPy,G2)e(q(τ)G1,τG2zG2)=e(p(τ)G1yG1,G2)e(G1,G2)q(τ)(τz)=e(G1,G2)p(τ)yXGTq(τ)(τz)=XGTp(τ)y

KZG-friendly curves

So far, we have seen that the KZG commitment is a MSM computation in

G1 only. Thus, a KZG-friendly curve should be a pairing-friendly curve where
G1
is the smallest possible, the pairing fast and
G2
can be big though. The BLS24 family is suitable for these goals because one can reduce
Fp
size (w.r.t. DLP in
Fp24
) and still have a fast pairing (curve seed is 32 bits, half the size of BLS12). However, for SNARKs, we need
Fr
to be highly 2-adic, i.e.
2larger1
to be able to implement efficient polynomial arithmetic using radix-2 Fast Fourier Transforms (FFT).

However, as mentioned in this GitHub thread [6], there are only

232 possible seeds that fit lead to
r<256
bits and by enumerating these the best high 2-adicity achieved is 22. In the survey paper, we propose a different Hensel-like technique for lifting multiple roots and thus increasing the 2-adicity. With this technique (Alg. 6), we found a particular BLS24 curve of 2-adicity 60. It has similar properties to BLS12-381 but is tailored for KZG-based SNARKs.

BLS24-317

curve seed
x
2-adicity
r=#G1
p,G1
pk/d,G2
p3mod4
security
BLS24-317 0xd9018000 (HW=6) 60 255 317 1268 Yes 127
BLS12-381 -0xd201000000010000 (HW=6) 32 255 381 762 Yes 126

Implementation

I implemented this curve in gnark-crypto and Diego implemented it in Relic. Hereafter, I benchmark KZG operations (gnark-crypto) over BLS24-317 and BLS12-381 curves on a AMD EPYC 7R32 AWS machine.

benchmark                        BLS12-381 ns/op     BLS24-317 ns/op     delta
BenchmarkKZGCommit-32            30658007            23818500            -22.31%
BenchmarkKZGOpen-32              32785660            25866237            -21.11%
BenchmarkKZGVerify-32            1411429             3379792             +139.46%
BenchmarkKZGBatchVerify10-32     1829747             3783824             +106.79%

We see that the commitments and openings are ~20% faster on the new BLS24-317 while the verification is way slower but still acceptable (3.3 ms vs. 1.4 ms). This is due to the cost of

Fp24 in the pairing computation. However, this can be somewhat reduced following [7], which we have not implemented in gnark-crypto yet.

Conclusion

For KZG-based applications that want to speed up the commitment (and opening) parts of the computations (e.g. PLONK or Marlin prover), it seems that the BLS24-317 curve is faster than the well-optimized BLS12-381 curve. However, this comes at the cost of a slower verification although, in many applications, the timings are acceptable (e.g. 3.7 ms for a batch verification of 10 commitments). It was also believed that BLS24 are incompatible with high 2-adicity in

Fr which we proved it is not.


References

[1] https://eprint.iacr.org/2016/260.pdf
[2] https://eprint.iacr.org/2019/953.pdf
[3] https://eprint.iacr.org/2019/1047.pdf
[4] https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf
[5] https://hackmd.io/@benjaminion/bls12-381
[6] https://github.com/arkworks-rs/curves/issues/10#issuecomment-714863120
[7] https://eprint.iacr.org/2010/104.pdf


Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Author: Youssef El Housni.

I'm part of a research team at ConsenSys. If you are interested in our work (fast finite field arithmetic, elliptic curves, pairings, and zero-knowledge proofs), give us a shout.