Optimization for `open` for linear-code based PCS

[mmagician]

Summary

The current interface doesn't allow room for certain optimizations to open.

Problem Definition

Specifically, for linear code schemes such as Ligero, during commit we compute the merkle root, and to create the proof in open we again recompute the merkle tree to then send merkle proofs for a bunch of leaf indices. Ideally the open stage shouldn't need to recompute the tree.

Proposal

We introduce a gap between the output of commit and the input to check.

Namely, commit would return an ExtendedCommitment (aka PrivateCommitment?) , and verify would only receive the Committment. We also introduce a trivial into() method that's a no-op in all current schemes, but for linear codes it sheds a few fields, such as the coefficients matrix, extended coefficients matrix and the merkle tree, saving the need to recompute them.

We can then leverage this new interface to further simplify the commit and open trait methods: instead of having a separate argument rands, we place the rands on the ExtendedComittment. Then the into() method would shed the rands field when converting it to be used in check.

@Antonio95 @autquis @Pratyush

---

For Admin Use

• [x] Not duplicate issue
• [x] Appropriate labels applied
• [x] Appropriate contributors tagged
• [x] Contributor assigned/self-assigned

[Antonio95]

Yes! I would propose the name CommitmentData for the larger structure containing the commitment and auxiliary data (whether it be randomness, previously computed values, or anything else). This also makes it less likely to be thought of as an actual "commitment on steroids", which I could see happening with ExtendedCommitment.

[mmagician]

As discussed with @autquis and @Antonio95 , an alternative approach would be to turn the rands into an aux_data structure, and have commit return a tuple of (commitment, aux_data). This has the advantage of being less likely to mis-use and accidentally pass the ExtendedCommitment to the verifier.

[Pratyush]

Sounds like a good idea to have commit output the commitment and an additional "commitment state" (I presume that this is used in opening?). If so, a descriptive name would could be CommitterState?

[mmagician]

Correct, that would be used in open.

[Pratyush]

Hm then perhaps CommitmentOpeningData would be slightly better? (Because if I call commit in a sequence it's not like I'll be passing the state from one call to the next)

[mmagician]

Sure, we can start with that and see how the name feels once it's implemented :)

[autquis]

Would you want all schemes in the repo to have the hiding property?

In #134 , we have added PCCommitmentState along with PCRandomness. Ideally, we should merge these two in one. One way to do so is to remove the methods from PCRandomness. This implies that we are not enforcing hiding property on the schemes of the repo. If a scheme is hiding, it implements these methods for its Randomness. However, if a scheme is not hiding, implementing these methods is unnecessary (e.g., #131 and #132).

[Pratyush]

We can merge PCCommitmentState and PCRandomness, I think, and put the methods from PCRandomness into PCCommitmentState. For schemes where we haven't implemented hiding, these methods can be no-ops.