Commit-carrying SNARK

[weikengchen]

This issue describes the branch commit-carrying.

According to LegoSNARK, Groth16 is a commit-carrying SNARK with weak binding. With a small modification below, Groth16 can become a full-fledged commit-carrying SNARK. Note that Groth16 is commit-carrying, but not commit-and-prove because the commitment's parameters are relation-dependent.

The modification is as follows:

• Augment the QAP so that the first n columns of the A matrices have a rank at least n, where n is the number of input elements. This step is done by simply adding n+1 constraints. A discussion is here: https://github.com/arkworks-rs/groth16/blob/commit-carrying/src/augmented_qap.rs#L1
• Modify the data structures of proving keys and verifying keys accordingly.
• Modify the proof generation and verification accordingly.

This issue is, very likely, not going to be merged into the master branch since its interface is drastically different.