Multiparty computation for R1CS proofs

[hdevalence]

Seed crystal for MPC for R1CS proofs.

Questions:

• [ ] how do we adapt the rangeproof MPC protocol for the R1CS protocol (probably just working out details)
• [ ] assuming we want to allow different parties to use different gadgets, how does that actually work as an API?
• [ ] how does the future 2-phase R1CS protocol (#222) work with the MPC protocol?

We probably don't want to start answering these until we've finished the single-party R1CS protocol, but when we do we can split them all off into individual issues and cross-reference them from here.

[KimWonLee]

assuming we want to allow different parties to use different gadgets, how does that actually work as an API?

Can you add more context to this?

[hdevalence]

All I meant was that there are decisions to be made about how the constraint systems are actually held internally when doing aggregated proofs -- right now, the constraint system is built up into a Verifier object; should an aggregated verifier take ownership of a bunch of those Verifier constraint systems and rearrange their components to do an aggregated verification, etc?

[lovesh]

I have added a rough implementation for R1CS proof aggregation in my fork. My objective was not to get MPC but make the proof smaller (and somewhat faster) when a single user creates several such proofs. An example is the holder of an anonymous credential proving several kinds predicates about the attributes in the credential. The API is described here. There are some basic tests to show that aggregation works starting from here. And there is one test that does aggregation of a set membership and non-membership proof, it has some benchmarks.

TODOs:

• Phase-2 support (I haven't felt the need in my circuits yet)
• I have created 3 new objects AggrProver, AggrVerifier and Aggregator. I should be combining AggrProver+Aggregator with Prover and AggrVerifier with Verifier.

Would love feedback on this.

[oleganza]

My objective was not to get MPC but make the proof smaller (and somewhat faster) when a single user creates several such proofs.

@lovesh, if you target design for a single user, then the easiest way to aggregate the proof is to simply construct a single proof. Current R1CS API allows composing arbitrary gadgets, so even if some subsets of them are independent, you still get a single CS and a single compact proof. MPC-oriented API is really necessary for multi-party case, and there are two very different approaches:

1. Each party has their own circuit, and aggregate only to make the proof more compact. This is similar to the current MPC for rangeproofs, but we probably want to allow circuits of different shapes and sizes.
2. Each party contributes to a single shared circuit, in order to improve confidentiality as well as achieve compactness (e.g. CoinJoin transaction where multiple "independent" payments are shuffled and look like one single payment)

The second approach might be harder because we need to indirectly compute commitments to joint secrets (e.g. output wire of a multiplier with left/right inputs supplied by different parties), without asking the parties to reveal secrets to each other. But if it's doable, it's a strictly more powerful framework, because even simple aggregation of distinct proofs could use the same API.