VidScheme allow disperse to reuse work done in commit_only

[ggutoski]

A significant fraction of the work of commit_only is duplicated in disperse. ie. computing polynomial commitments (dominant cost!), bytes_to_field, and possibly other things.

commit_only should return additional data beyond the commitment. At a minimum, it should also return the polynomial commitments

disperse should take a (optional) argument for pre-computed polynomial commitments.

Need to update VidScheme trait with these API changes, then update ADVZ impl to conform.

VidScheme is supposed to be abstract, so we can't just add a poly_commits: Option<Vec<KzgCommit<E>>> arg to disperse. Instead we could add yet another assoc type to VidScheme called DisperseHelperData or whatever. The proposal is something like

trait VidScheme {
  // ...
  type DisperseHelperData: Clone + Debug + DeserializeOwned + Eq + PartialEq + Hash + Serialize + Sync;
  fn commit_only<B>(&self, payload: B) -> VidResult<(Self::Commit, Self::DisperseHelperData)>
  fn disperse<B>(&self, payload: B, helper_data: Option<Self::DisperseHelperData>) -> VidResult<VidDisperse<Self>>
  // ...
}

cc @elliedavidson for visibility.

[ggutoski]

Discuss: If we change VidScheme trait then we also need to change everything downstream that depends on it. That will be a lot of work. 😕 An alternative is to make only additive changes to VidScheme. ie. new methods commit_only_with_helper_data and disperse_with_helper_data

@akonring If we do make breaking API changes then we should open PRs for everything downstream that will break. In order to do so we need to test everything locally via cargo patch directives.

EDIT: ...or maybe we can make a subtrait VidSchemeWithHelperData: VidScheme

[akonring]

I don't have a strong opinion on this. I see that breaking changes to VidScheme trait will add more downstream complications but on the other hand adding new methods creates a less clean trait interface. Maybe there are other reasons to not introduce new methods?

[ggutoski]

We already have an instance of the subtrait pattern with PayloadProver: VidScheme. I suggest we repeat that pattern for VidSchemeWithHelperData: VidScheme. (But please choose a better name!) We'll see how it looks in review and seek more opinions then.

[akonring]

Preliminary design of the subtrait below:

//! Trait for additional functionality in Verifiable Information Retrieval (VID)
//! for precomputation of specific data that allows for calling
//! methods using the data to save computation for the callee.

use core::fmt::Debug;

use super::{VidDisperse, VidResult, VidScheme};
use ark_std::hash::Hash;
use serde::{de::DeserializeOwned, Serialize};
/// Allow for precomputation of certain data for [`VidScheme`].
pub trait Precomputable: VidScheme {
    /// Precomputed data that can be (re-)used during disperse computation
    type PrecomputeData: Clone + Debug + Eq + PartialEq + Hash + Sync + Serialize + DeserializeOwned;

    /// Similar to [`VidScheme::commit_only`] but returns additional data that
    /// can be used as input to `disperse_precompute` for faster dispersal.
    fn commit_only_precompute<B>(
        &self,
        payload: B,
    ) -> VidResult<(Self::Commit, Self::PrecomputeData)>
    where
        B: AsRef<[u8]>;

    /// Similar to [`VidScheme::disperse`] but takes as input additional
    /// data for more efficient computation and faster disersal.
    fn disperse_precompute<B>(
        &self,
        payload: B,
        data: Self::PrecomputeData,
    ) -> VidResult<VidDisperse<Self>>
    where
        B: AsRef<[u8]>;
}

Currently, looking into the implementation: figure out the data we want to re-use and how to satisfy Serialize + DeserializeOwned for this data. Feedback is welcome.

[ggutoski]

Looks pretty good. Notes:

• data arg of disperse_precompute should probably be a reference type &Self::PrecomputeData
• which data to re-use: For ADVZ this will be just a single field poly_commits: Vec<KzgCommit<E>>,, exactly like in the Common struct.
• you can use Common as a model for how to satisfy serde traits. I suspect it'll look something like

#[derive(CanonicalSerialize, CanonicalDeserialize, Derivative, Deserialize, Serialize)]
#[derivative(
    Clone(bound = ""),
    Debug(bound = ""),
    Eq(bound = ""),
    Hash(bound = ""),
    PartialEq(bound = "")
)]
pub struct PrecomputeData<E>
where
    E: Pairing,
{
    #[serde(with = "canonical")]
    poly_commits: Vec<KzgCommit<E>>,
}

Because there's no H type param it might be possible to eliminate the derivative attribute with all the bound = "" fields and instead put all those trait bounds into the conventional derive attribute.