search

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations
https://www.arkworks.rs
Apache License 2.0
769 stars 203 forks source link

Add `Relation` trait #348

Open Pratyush opened 3 years ago

Pratyush commented 3 years ago

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.

ValarDragon commented 3 years ago

Accidentally just reviewed the last few commits lol

Pratyush commented 3 years ago

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

jon-chuang commented 3 years ago

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.

weikengchen commented 3 years ago

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?

Pratyush commented 3 years ago

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