snark icon indicating copy to clipboard operation
snark copied to clipboard

Add `Relation` trait

Open Pratyush opened this issue 3 years ago • 5 comments

Description

Adds two traits: Relation and NPRelation. Modifies the SNARK trait to use these, instead of the ConstraintSystem infrastructure.

TBD: How to integrate the old ConstraintSystem-based APIs into this. See https://github.com/arkworks-rs/snark/pull/348#discussion_r616286265 for an idea.

closes #323 closes #321 closes #341 closes #342


Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

  • [X] Targeted PR against correct branch (master)
  • [X] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
  • [ ] Wrote unit tests --- N/A
  • [X] Updated relevant documentation in the code
  • [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
  • [X] Re-reviewed Files changed in the Github PR explorer

Pratyush avatar Apr 20 '21 01:04 Pratyush

Accidentally just reviewed the last few commits lol

ValarDragon avatar Apr 20 '21 21:04 ValarDragon

Updated the PR further, I think it's now in the final form and is ready for merging as is (modulo the CHANGELOG)

Pratyush avatar Apr 21 '21 07:04 Pratyush

So the Relation trait is pretty generic, and allows for a generic Snark interface. Which is nice.

So I'm wondering if it's a good time to try to do, or at least plan for, a draft migration of the halo2 code, although @daira seemed to be saying its not exactly ready for that. But from my perspective, it maybe would help put an extra pair of eyes on zcash's code and help arkworks advance to being yet more featured and flexible.

I'll post an issue soon regarding an approach, also outlining potential friction areas and incompatibilities, and ideas for how to solve them.

I'll also try to see if there are any tweaks that could be made regarding this PR.


I'm also wondering if relatedly, a common "plonk description language" ought to be established to make at the very least, relations, which can consist of multiple sub-relations, compatible between various libraries. The description language can also contain meta data, such as subcircuit names and component names, or not.

If R1CS is a general-purpose processor, plonk/plookup is a sort of FPGA/ASIC, with reuseable components, lookup tables, wiring, fan-in/fan-out and locality constraints, custom gates. The glue that holds it all together is the wiring (permutation argument). There are also subtle tradeoffs between the maximum relation multiplicative depth and proof size/proving time.

Just like the differences between programming a CPU and programming an FPGA are huge, there is a need to manage, and hide, a lot more complexity when it comes to Plonk/Plookup.

jon-chuang avatar Apr 25 '21 15:04 jon-chuang

When should we merge this one (and plan for the next/next release)? And how many code changes to the other repos should we expect?

weikengchen avatar Jun 04 '21 00:06 weikengchen

I still have to make corresponding PRs for Groth16 and Marlin; let's push merging this until after 0.3 (so in 0.4).

Pratyush avatar Jun 04 '21 00:06 Pratyush