Add `&self` parameter to `PolynomialCommitment` trait methods

[mmagician]

Summary

Problem Definition

LigeroPCS requires the prover & the verifier to do some Merkle tree operations in the non-interactive setting. Specifically, the prover's commitment is a Merkle root, and the verifier should check well-formedness of such a commitment against the provider proofs (MT paths) for a couple of leaf indices.

We are trying to use a Merkle Tree from crypto-primitives inside the commit method (and equivalently, Path in the check method) - which requires the parties to provide a concrete instantiation of a CRHScheme and TwoToOneCRHScheme. Currently we can do it like:

impl<..., C> PolynomialCommitment<F, P, S>
    for Ligero<F, C, ...>
where
    ...,
    C: merkle_tree::Config + 'static,
{
...
    fn check<'a>(
        vk: &Self::VerifierKey,
        ...,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<bool, Self::Error>
    where
        Self::Commitment: 'a,
    {
        let mut rng = rng.unwrap();
        // take the first committment
        let labeled_commitment = commitments.into_iter().next().unwrap();
        // IS THERE A BETTER WAY?
        let leaf_hash_params = C::LeafHash::setup(&mut rng).unwrap();
        let two_to_one_params = C::TwoToOneHash::setup(&mut rng).unwrap();
        // well-formedness check internally verifies some merkle paths, which requires passing the params
        Self::well_formedness_check(
            labeled_commitment.commitment(),
            &leaf_hash_params,
            &two_to_one_params,
        );

This looks a bit hacky, because probably the rng parameter wasn't meant to be used for constructing structs that are part of the setup.

A more natural way to do this would be to have

pub struct LigeroPCS<
    F: PrimeField,
    C: Config,
    ...,
> {
    leaf_hash_params: C::LeafHash,
    two_to_one_params: C::TwoToOneHash,
}

and then when we need either of the params, we'd call self.leaf_hash_params, for example. The problem is of course that neither the interface for commit nor check exposes a &self parameter, so there's no way to access parameters from the struct implementing PolynomialCommitment.

Proposal

I propose changing the method signature of the associated PolynomialCommitment methods to include a (non-mutable) &self, e.g.

    /// check but with individual challenges
    fn check<'a>(
        &self,
        vk: &Self::VerifierKey,
        commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
        point: &'a P::Point,
        values: impl IntoIterator<Item = F>,
        proof: &Self::Proof,
        challenge_generator: &mut ChallengeGenerator<F, S>,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<bool, Self::Error>
    where
        Self::Commitment: 'a;

The alternative for this Ligero PC is to have the merkle tree parameters be part of Self::{Verifier,.Commiter}Key, but that introduces a great deal of additional constraints (serialization, Sync etc.) which are cumbersome to enforce on C::LeafHash etc.

@antonio95

---

For Admin Use

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

[Pratyush]

Why not pass it in the public parameters/commitment/verifying keys?

[mmagician]

They impose trait bounds which are not guaranteed on e.g. CRHScheme:

pub trait PCCommitterKey:
    Clone + core::fmt::Debug + CanonicalSerialize + CanonicalDeserialize

[Pratyush]

You can write a custom impl of those traits for those functions, right? I don't think you need to store CRHScheme inside PCCommitterKey, but rather only CRHScheme::Params, right?

[mmagician]

Yes I meant the CRHScheme::Params. That sounds like unnecessary boilerplate - is there any drawback to exposing a &self, aside from the breaking change that it introduces?

[Pratyush]

It sort of goes against how we construct every other cryptographic primitive, where we pass in parameters explicitly. The other way to do this would be to add the trait bounds to the CRH traits

[mmagician]

Besides, I think that if I want to implement CanonicalSerialize for PCCommitterKey, I'd need to assume that CRHScheme::Params has a CanonicalSerialize trait bound:

#[derive(CanonicalSerialize, CanonicalDeserialize)]
struct LigeroPCVerifierKey<C>
where
    C: Config,
    <<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters: CanonicalSerialize + other_stuff,
    <<C as Config>::LeafHash as CRHScheme>::Parameters: ...,

or without the derives, if I impl CanonicalSerialize myself, I'd still need to somehow assume I have a way to serialize the Parameters.

[mmagician]

So you're saying to add CanonicalSerialize bound etc. to CRHScheme::Parameters: https://github.com/arkworks-rs/crypto-primitives/blob/4b3bdac16443096b26426673bff409d4e78eec94/src/crh/mod.rs#L32:

pub trait CRHScheme {
    type Input: ?Sized;
    type Output: Clone
        + Eq
        + core::fmt::Debug
        + Hash
        + Default
        + CanonicalSerialize
        + CanonicalDeserialize;
    type Parameters: Clone + CanonicalSerialize + others;

Is that what you mean? I could do that, we don't have that many implementors anyway so shouldn't be too much work overhead.

[Pratyush]

Yes, I think it makes sense because those are things that need to be serialized and deserialized anyway

[mmagician]

Ok thanks @Pratyush! Will do that then