Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Generalize lookups to set inclusion constraints #427

Open
1 of 2 tasks
vlasin opened this issue Jan 6, 2025 · 2 comments · May be fixed by #445
Open
1 of 2 tasks

Generalize lookups to set inclusion constraints #427

vlasin opened this issue Jan 6, 2025 · 2 comments · May be fixed by #445
Assignees
@hovanja2011

Comments

@vlasin
Copy link
Contributor

vlasin commented Jan 6, 2025 •
edited by hovanja2011
Loading

After the discussion in #252, we arrived at the idea that ArithmeticCircuit is an intermediate representation of the computation that should allow an unrestricted ability to create polynomial, lookup, and fold constraints. If a particular proving system (e.g., Plonk) does not support a certain type of constraints, we convert them to the supported form during the protocol setup computation.

Given the above, we want to generalize the current lookup constraints to the inclusion checks:

$$ (x_1, \dots, x_{k}) \in T $$

Translating this to Haskell, we probably want T to be represented by Map and the tuple of variables to be a functor. We do not restrict the number of such sets T to be used in the same ArithmeticCircuit.

  • Refactor ArithmeticCircuit type, replacing acRange field
  • Refactor MonadCircuit and its instances
@vlasin vlasin mentioned this issue Jan 6, 2025
Closed
@TurtlePU
Copy link
Contributor

TurtlePU commented Jan 6, 2025 •
edited
Loading

during the protocol setup computation

Are we sure about this? Conversion will need access to quite low-level circuit APIs, doing this on the compilation stage seemed most reasonable.

Also this would help to keep protocol code dedicated to cryptography stuff only

@vlasin
Copy link
Contributor Author

vlasin commented Jan 6, 2025

Well, I believe the conversion to the proof protocol format is a separate step. The workflow probably should go like this:

  1. Compile the function to the IR of ArithmeticCircuit
  2. Post-compile optimization (as a general rule, we want to optimize as we go, but it might not be always possible)
  3. Convert to a proof protocol format
  4. Protocol-specific optimizations (?)

So, we can wrap all 4 steps in a compile function whose output is a prepared setup of a specific protocol. But we should also have "internal" compile that only produces "ArithmeticCircuit". The latter, for example, is useful in IVC.

@hovanja2011 hovanja2011 linked a pull request Jan 16, 2025 that will close this issue
Generalize lookups to set inclusion constraints #445
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@hovanja2011 hovanja2011

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Generalize lookups to set inclusion constraints zkFold/zkfold-base
3 participants
@vlasin @hovanja2011 @TurtlePU