search

privacy-scaling-explorations / sonobe

Experimental folding schemes library
https://privacy-scaling-explorations.github.io/sonobe-docs/
MIT License
205 stars 54 forks source link

Feature/sumcheck #40

Closed dmpierre closed 11 months ago

dmpierre commented 1 year ago

edited before merging

We want folding_schemes to have a sum-check implementation generic over hash functions.

To achieve this, we re-use hyperplonk's sumcheck implementation. To be able to make it generic over any hash, we tweak it to be generic over our own [Transcript]() trait (not the one found in hyperplonk).

This PR: 1) re-defines SumCheck, SumCheckProver and SumCheckVerifier traits to be generic over a CurveGroup, with prove and verify methods generic over folding_schemes::Transcript. 2) sets the IOPProverState and IOPVerifier states to be generic over a CurveGroup.

Also, we change hyperplonk calls to its transcript object when re-implementing the prove and verify method cited above:

  1. transcript.append_serializable_element becomes transcript.absorb (example) or transcript.absorb_vec when needed (example).
  2. transcript.get_and_append_challenge becomes transcript.get_challenge (example)

The main disadvantage from taking this route is codebase inflation. However, we gain the short-term ability to have a somewhat robust and generic sum-check implementation. Still, although practical, it seems like a temporary implementation which might be re-evaluated in the future (e.g. implementing our own sum-check from scratch, hyperplonk's implementation might have possible low-hanging optimizations).

dmpierre commented 12 months ago

hypernova working with poseidon based transcript here

CPerezz commented 12 months ago

Is this ready for review @dmpierre ?

dmpierre commented 12 months ago

Is this ready for review @dmpierre ?

Yes thanks! Forgot to assign, so just added Arnau as well

dmpierre commented 12 months ago

Added a raw sum-check implementation in the meantime, might help to get rid of hyperplonk altogether. Started benchmarking it. I will be working on optimizing this over the next few days. Would be happy to hear your thoughts!

CPerezz commented 12 months ago

@arnaucube pinged me about code duplication. So I'll save time and review once the changes have been addressed!

Could you ping once done @dmpierre ??

dmpierre commented 11 months ago

@arnaucube pinged me about code duplication. So I'll save time and review once the changes have been addressed!

Could you ping once done @dmpierre ??

I think we are getting closer! We eventually go for implementing a more generic trait over hyperplonk directly.

Keeping our own sum-check implementation for later since it will require additional work on top of it if we want to use it - things like removing the dependency to VirtualPolynomial, scattered in quite a few key places (we will have to re-implement some strategic polynomial subroutines to do that).