Add Hyrax multilinear PCS

[Antonio95]

Description

This PR implements the Hyrax polynomial commitment scheme: a multilinear PCS based on the hardness of the discrete logarithm problem introduced as part of the Hyrax zkSNARK in this 2017 article.

The PCS described therein is interactive. When implementing the Fiat-Shamir transform, this paper was consulted.

Modification note

In the PCS contained in the cited article, the verifier never learns the actual evaluation of the polynomial at the requested point, but is instead convinced that a previously received Pedersen commitment is indeed a commitment to said evaluation - this is what the SNARK proposed therein necessitates. However, the Arkworks framework requies the verifier to actually learn that value, which is why we have added the opening of the commitment at the end of the protocol. This likely does not result in an optimal non-hiding PCS, but we feel it is the most faithful adaptation of the original PCS that can be implemented with the current restrictions.

Future optimisations

Some natural optimisations to the scheme which are not part of the current PR, but would make sensible follow-up work, are the following:

• Deal with the modification described above: either modify the PCS trait to encompass hiding PCSs (in terms of the actual evaluation, not only the polynomial), or turn this scheme into a non-hiding one by removing unnecessary work (which would probably involve non-trivial theoretical work).
• Add parallelisation. There is at least one natural place where parallelisation could bring performance gains: in essence, the prover commits to the polynomial by expressing it as an evaluation matrix and Pederson-multi-committing to each row. Each of this commitments can be computed independently from the rest, and therefore, in parallel. It is still to be seen how much of an improvement this would entail, since each Pederson multi-commitment boils down to a multi-exponentiation and this operation is itself parallelised.
• Due to the homomorphic nature of Pedersen commitments, it is likely some of the following methods can be designed more efficiently than their default implementations: batch_open, batch_check, open_combinations, check_combinations. This is not discussed in the reference article, but the IPA and KZG modules might be a good starting point.
• On a related note to the previous point, there might be a more efficient way to open several polynomials at a single point (this is the functionality of the open method) than the currently implemented technique, where only the computation of the vectors L and R is shared across polynomials.
• The cited article proposes an optimisation in the section Reducing the cost of proof-of-dot-prod. It allows for non-square matrices (and hence removes the requirement for the number of variables to be even) and introduces a tradeoff between proof size and verifier time. It is probably worth pursuing.

---

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.

• [x] Targeted PR against correct branch (master)
• [x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [x] Wrote unit tests
• [x] Updated relevant documentation in the code
• [x] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [x] Re-reviewed Files changed in the Github PR explorer

[mmagician]

This PR relies on https://github.com/arkworks-rs/algebra/pull/691, so we temporarily expect CI to fail until that's merged.

[Pratyush]

Sorry for the late update on this, but happy to merge this as-is, once it's updated wrt master.

[autquis]

It is ready for review and to be merged. @Pratyush If you are merging these three PRs, please do this PR first. Then, I will resolve the conflicts of the other two and let you know when they are ready.

[autquis]

Ping to all :) I would be happy to resolve any remaining issues.

[Antonio95]

I am happy with the current state of things! Let us see if @Pratyush would like any further tweaks regarding the open threads of this discussion.

[autquis]

A gentle reminder @Pratyush :)

[autquis]

Gentle reminder @Pratyush. (It would be much simpler if we go ahead and merge, and then, we can always improve the code.)