Halo evaluation without pairing check

[sum]

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.

[daira]

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 that have an “accumulation scheme”, including pairing-based ones (not sure about FRI). The reason why Halo and Halo 2 don’t do this is that, for circuits at the recursion threshold, it’s less efficient because pairing-friendly elliptic curves are larger (and FRI-based schemes produce much larger proofs).

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.

[sum]

Thanks Daira, that’s really clear. I need to look in more detail to fully understand the reasons, but I see that a pairing friendly curve is not required for the commitment scheme used in Halo, and the benefits of that.

What I still can’t grasp, and possibly won’t be able to without a better low-level understanding, is why it is now trustless (transparent setup). Here, the inner product is described as requiring a trusted setup to produce a SRS, similar in principal to the Groth16 protocol SnarkPack: How to Aggregate SNARKs Efficiently | Protocol Labs Research. Is it because instead of the SRS, the verification is done by showing “a random linear combination of the commitments opens at a random point” as per Halo paper? I don’t fully comprehend why this can be done, but if you could point me in the right direction that would be really appreciated.

[daira]

To understand why Halo 2 is trustless, I think it’s best to first understand why pairing-based schemes based on KZG polynomial commitments, such as Groth16 do require a trusted setup.

As explained here, the way you compute a KZG commitment to a polynomial \phi(X) = \sum_{i \in [0,d]} \phi_i X^i is as \prod_{i \in [0, d]}\left(g^{\tau^i}\right)^{\phi_i}. That is why you need to know the “Structured Reference String” containing the precomputed g^{\tau^i} for some secret \tau. (The pairing checks then make use of the g^{\tau^i} structure.) If someone knew \tau, they would know non-trivial discrete log relations between the g^{\tau^i}, and so this would not be a binding commitment.

Halo 2’s polynomial commitment scheme is based on similar ideas to Bulletproofs. The explanations I’ve found most helpful to understand how these schemes work without using a Structured Reference String, are Justin Drake’s ZK Study Club on polynomial commitments, and (for more detail on Halo 2’s PCS) Ying Tong Lai’s section of our ZK Seoul deep dive. The sound quality is poor on the latter unfortunately.