Halo evaluation without pairing check

When I first learned about zkSNARKS, the protocols used a pairing check to evaluate the polynomials. Later, cycles of elliptic curves such as 800 bit MNT curves which are pairing friendly were used to produce a recursive system. For Halo, the paper states that it does not require either curve in the cycle of elliptic curves to be pairing-friendly; the Pasta curves now used are not pairing friendly.

The reason for this is not explicitly stated in the Halo paper as far as I can see, and I am not able to fully understand the math - in simple terms, how is the need for a pairing friendly curve avoided in Halo?

In addition, if pairing friendly curves are used, must the system use a trusted setup? I can only grasp the general idea behind this, but I am still not really sure why Halo is trustless and whether it is related to it being able to use curves that are not pairing-friendly.

4 Likes

Hello, thanks for your question. I’m Daira, I designed the Pasta curves.

Modern zk proving systems are constructed from an “information-theoretic part” (which is statistically secure) and a “cryptographic part”. There are various ways to formalize this, but one way of describing the cryptographic part is as a “polynomial commitment scheme”. This takes a polynomial as input, and produces a short value that commits to the polynomial. It also has a protocol that allows proving that an evaluation of the polynomial at a point is consistent with its commitment.

There are, roughly speaking, three families of polynomial commitment schemes used in deployed protocols (there are others that are so far too inefficient to deploy), based on:

  • Inner products
  • Pairings
  • FRI (Fast Reed–Solomon Interactive oracle proof of proximity)

So the short answer is that Halo (and Halo 2) use an inner-product polynomial commitment scheme, which doesn’t need pairings.

Roughly speaking, if you have a cryptographic group with a pairing, then using the pairing on group elements allows you to check quadratic constraints (i.e. constraints that involve one level of multiplication) on the corresponding scalars, rather than only linear constraints.

An inner product argument allows you to construct a polynomial commitment scheme without needing to check quadratic constraints.

This has significant performance advantages, because of the smaller size of elliptic curves needed for inner product-based schemes vs. pairing-based schemes. Roughly speaking, for a 128-bit security level, an inner-product-based scheme requires ~256-bit curves, while a pairing-based scheme requires ~384-bit curves. Since the cost of curve arithmetic is roughly quadratic in the field size, the pairing-based schemes use ~2.25 times less efficient curve arithmetic. (This is for proof systems that don’t support efficient recursion; for those that do, see below.)

The inner-product-based and FRI-based schemes do not require a trusted setup. (There also exist pairing-based schemes that don’t require a trusted setup, but those aren’t commonly used.) However, inner-product-based schemes come with the trade-off that you can only fully verify a proof in time proportional to the circuit size (rather than in time logarithmic or constant in the circuit size).

What the Halo technique allows you to do is to construct a recursive proof system in which you only pay this cost of full checking once for a graph of proofs. So the cost is linear, but in the size of one circuit, rather than the whole computation.

It’s possible to use the Halo technique with other polynomial commitment schemes, e.g. pairing or FRI-based ones. The reason why Halo (and Halo 2) itself doesn’t do this is that, for circuits at the recursion threshold, it’s less efficient because pairing-friendly elliptic curves are larger.

Specifically, for ~128-bit security,

  • A curve 2-cycle in which neither curve is pairing-friendly, only needs to use ~256-bit fields.
  • A curve 2-cycle in which only one curve is pairing-friendly, needs to use ~384-bit fields.
  • A curve 2-cycle in which both curves are pairing-friendly needs at least 800-bit fields, probably more.

Please let me know if you have any further questions.

13 Likes