FPGA chip

[str4d]

In Office Hours today, @CPerezz explained how the zkEVM's ConstraintBuilder works. At a high level:

• A constant number of columns (of the desired mix of advice and fixed) are created.
• A single Region is assigned spanning all columns, with a constant number of rows.
• The CellManager assigns values into cells inside the region "in-order" (down rows first, then into the next available column).
• The ConstraintManager takes all of the constraints defined in it, and turns them into a single giant constraint which effectively queries every column at every rotation.

I realised that this is effectively an FPGA: a chip with a defined area and the ability to involve every cell in it as part of a computation (which due to how constraints work can be inherently a series of separate constraints, that are combined with random separators).

We designed the "gadget and chip" abstraction to enable people to write reusable components build around gadgets, and then end-circuit developers could instantiate those with specific chips targeted at their performance needs. But writing the chips themselves is akin to writing ASICs, and can require a significant investment in low-level constraint building expertise. Having an "FPGA chip" would enable people to prototype chips in a simpler fashion, while later making it possible to replace the FPGA implementation with a dedicated and more performant chip.

We should try and extract the zkEVM ConstraintBuilder logic into a (likely parameterisable) chip. This might make sense to go into a submodule of halo2_gadgets, or it might be complex enough that it belongs in its own crate. In either case, it should be made interoperable with the gadget ecosystem.

[str4d]

I made another point I noted during the Office Hours discussion that isn't directly relevant to the topic of extracting an FPGA chip, but is illustrative of the difference in effect on overall circuit cost that using an FPGA chip has.

In #550 I propose supporting DSLs by creating single-constraint regions, which heavily relies on equality constraints for intra-circuit communication. This effectively requires adding every column to the equality constraint permutation argument, increasing prover costs, but enables every constraint to be very simple, involve only the columns it needs, and use no rotations.

The FPGA chip approach instead adds every (column, rotation) tuple to the constraint, which increases proof size and verifier cost, but means that almost no equality constraints are necessary. For circuits of the magnitude of zkEVM, it makes sense to me that there would be a desire to increase the verifier cost and proof size, in order to reduce the prover cost enough to be at all viable to compute.