Two-phase low-level variable commitments in R1CS protocol

[oleganza]

Addresses #222.

At this stage, this PR adds notes on how we update the protocol to enable two-phase low-level variable commitments, enabling use of challenges encapsulated inside the gadgets.

FYI: the previous iteration of this was in PR #196. This PR basically "rebases" the older one on top of the latest code layout and documentation.

[oleganza]

Pasting the rendering for the reference when the makefile ain't at hand.

[oleganza]

Prover's algorithm

[oleganza]

Verifier's algorithm

[oleganza]

I'll make a branch off of this one to make the API changes. If they turn out to be pretty minimal, i'd just merge them into this PR, so we can review+merge docs and implementation in one go. If it will turn out to be messy, we can merge this PR first (after 1.0 release) and then do one or more PRs with implementation.

The plan was outlined yesterday in https://github.com/dalek-cryptography/bulletproofs/issues/222#issuecomment-446411621:

1. CS::challenge_scalar(label, |cs, z| { }) sounds like a good way to avoid having to store AST of operations on future values.
2. The cs provided to the closure is exposed only as a trait, so we do not actually expose any first-phase functionality.
3. We can replace pair of types Prover/ProverCS (similar for Verifier) with just one type Prover because we can allow making high level variable commitments during the first phase. This is safe, because in the second phase the Prover is available only via the generic trait bound (inside the challenge_scalar closure), so the gadget code is not able to add more high level commitments.
4. We don't need a OpaqueScalar as was done in #196, we can simply provide the normal scalar for challenges.

[hdevalence]

Looking over the notes for the constraint system proof all together, there's a bunch of things that were written before and haven't been updated (so they're now inaccurate), for instance:

• the R1CS notes have a section "Building Constraints" that mentions challenges (and has something about "request a challenge scalar"), but:
  • this is mentioned before the 2-phase protocol is actually described;
  • with the new API, users cannot request a challenge scalar;
• linear constraints equation appears before motivation;
• the "low-level variables" section describes LL variables as being "created" from multipliers, rather than explaining that they are the multiplier assignments;
  • also mentions challenges in a way that's not correct now that we have a 2-phase structure;
• "Gadget as a challenge" section also needs rewriting for 2-phase;
• "representation of constraints" should probably be integrated with the description of how the CS equations work;

I think it would be good to rewrite the CS notes just as building up to the 2-phase system, but since this is a bigger change it probably shouldn't be in this PR but could be done later in parallel with the plan @oleganza described above.

[oleganza]

with the new API, users cannot request a challenge scalar;

Henry points out that the new API is more about "randomizing constraints" than "requesting a challenge", and we should name the method accordingly. E.g. randomize_constraints(|cs,z|{ ...}).

[hdevalence]

Maybe randomized_constraints ?

[hdevalence]

Do we want to merge this now, and move that stuff into a new issue? I looked at the parts that are changed and they look OK to me.

[oleganza]

Cool, lets merge.