Plonky: Recursive proofs based on Plonk and Halo

Implementation
#1

Hi everyone, just wanted to share Plonky, a library that consists of a few parts: a proving system loosely based on Plonk, a circuit builder that supports custom gates, and an implementation of Halo-style recursion. It’s still in development, but we’ve seen encouraging performance results: the Halo verifier circuit consists of < 2^14 gates, and without much optimization, proofs are generated in ~10s on a laptop. We welcome feedback and would love to collaborate with others in the community.

3 Likes
#2

Here’s a writeup with more details: https://hackmd.io/@predicatelabs/B1rJVpTrU

The custom gate mechanics might be interesting to others working on Plonk implementations. We organize custom gates in a binary tree, which lets us select the appropriate constraint at a given gate index using a logarithmic number of selector polynomials. Our gate tree looks like this currently:

image
image1599×1083 59.9 KB

2 Likes
#3

Very nice! You mention on github you use 9 = 6 + 3 columns. Your constraints in the hackmd look like they use a lot fewer than that (4 for rescue, I’m not sure how many for the curve gate).

Do you actually use 9 columns or is the github out of date? And do you have some way of avoiding paying for the columns in constraints where you don’t use them?

Also I wondered if you considered reducing the degree of the rescue gates by using additional columns?

Like let’s say \alpha = 5, you can add e.g., additional columns t_1, t_2 and instead of x_i = y_i^5 have t_i = y_i^2 and x_i = t_i^2 y_i.

#4

Good points! We do still use 6 + 3 = 9 columns, but I oversimplified our Rescue implementation a bit in the writeup. Some more specifcs:

  • We use separate gates for the two steps of Rescue: RescueStepAGate and RescueStepBGate.
  • Our overall model uses 6 constant (aka selector) polynomials. Since the Rescue gates have a depth of 2 in the tree, 2 of those 6 are used for filtering.
  • That leaves 4 constants available to each Rescue gate, so we use a sponge width of 4.
  • We use \alpha = 5, so those constraints are degree 7 after incorporating the gate type filter. This is fine for us; we just want to keep constraints within degree 8 so that our largest FFTs are degree 8n.
  • RescueStepAGate uses 4 routed input wires, and 4 advice wires for the purported x^{1/\alpha} values. It doesn’t have explicit output wires; instead it constrains the input wires of the RescueStepBGate that follows it.
  • RescueStepBGate also uses 4 input wires, and similarly treats the wires of the following gate as its “outputs”. We add a no-op gate after the last RescueStepBGate to receive the final outputs and make them routable. (Now that I write this, I think we can do without that final gate by giving RescueStepBGate non-routed inputs and routed outputs.)

With \lambda=128 and our permutation width of 4, we have 16 recommended rounds per permutation, or 33 gates. So for a k-to-1 hash we end up using 33 \lceil k/3 \rceil gates.

Hope that makes sense? There are a ton of possible variants depending on how many constants are available etc., but this seems to fit pretty well with our particular circuit model.