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 Halostyle 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.
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:
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.
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
andRescueStepBGate
.  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 theRescueStepBGate
that follows it. 
RescueStepBGate
also uses 4 input wires, and similarly treats the wires of the following gate as its “outputs”. We add a noop gate after the lastRescueStepBGate
to receive the final outputs and make them routable. (Now that I write this, I think we can do without that final gate by givingRescueStepBGate
nonrouted 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 kto1 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.