EspressoSystems / hyperplonk

MIT License
181 stars 38 forks source link

Enable Fiat-shamir in PolyIOP (big refactoring) #54

Closed chancharles92 closed 2 years ago

chancharles92 commented 2 years ago

I have to admit that I made a mistake when designing the APIs of PolyIOP. PolyIOP is much more complex to implement than using it in a paper as an abstract protocol. The key issue is that PolyIOP doesn't enable Fiat-shamir, hence we need to build an API for every round of the protocol.

This is super annoying especially when we want to compose two poly IOPs. E.g., when we instantiate prove() for a permutation check, it will call a product check. However, the product check involves the following steps:

  1. compute_prod_poly() builds a product polynomial. The outside SNARK caller will update the transcript using the commitment of the product polynomial.
  2. gen_challenge() uses the updated transcript to generate a challenge alpha
  3. prove_final() takes the challenge alpha, the product polynomial, and other polynomials, and conduct a zero-check.

The big issue is that the prove() in permutation check can't call compute_prod_poly(), gen_challenge(), prove_final() sequentially inside the function, because the outside SNARK caller should first update the transcript given the returned result of compute_prod_poly().

Proposed solution: Add PCS trait into the PolyIOP, and enable the PolyIOP APIs to update transcript itself using polynomial commitments. This will significantly simplify the APIs of XXX-Check PolyIOPs.

cc @zhenfeizhang (and apologize if we need to redo a lot of work...)

chancharles92 commented 2 years ago

close this and work on #55