Module binius_core::protocols

source ·
Expand description

Implementations of various virtual polynomial protocols.

A virtual polynomial protocol is subprotocol of a polynomial IOP. See DP23 Definition 4.7 for a formal definition. Each protocol has a prover-side implementation and a verifier-side implementation. These protocols are all public-coin and made non-interactive by the Fiat-Shamir transformation. Thus, the prover-side implementations all simulate a verifier in order to accurately construct the transcript.

The protocol implementations have separate functions for each round. We model the virtual polynomial protocols this way because in many settings we want the ability to batch together multiple protocols at different rounds. For example, if we had one sumcheck claim for an $\nu$-variate polynomial and one sumcheck claim for a $\nu - 1$-variate polynomial, we would want to run one sumcheck round on the first claim, then batch the remaining rounds with the second claim.

Each verifier round proceeds as

  1. Receive the round message (ie. read it from the non-interactive proof)
  2. Send the round message to the challenger
  3. Sample challenge from the challenger
  4. Verify the round message and reduce old claims, message, and challenge to new claims

Each prover round proceeds as

  1. (Simulate verifier’s last round) Send last round message to the challenger
  2. (Simulate verifier’s last round) Sample challenge from the challenger
  3. (Simulate verifier’s last round) Reduce old claims, message, and challenge to new claims
  4. Compute the round message

Modules§

  • abstract_sumcheck
  • evalcheck
    The multivariate evalcheck polynomial protocol.
  • fri
    Implementation of the Fast Reed–Solomon IOPP (FRI) over binary fields.
  • gkr_gpa
    The grand product argument protocol based on a GKR-instantiation.
  • gkr_sumcheck
    The multivariate sumcheck polynomial protocol, special cased when the sumcheck is part of the GKR Protocol.
  • greedy_evalcheck
    An interactive protocol for proving/verifying evaluation claims on virtual polynomials.
  • lasso
    Lasso lookup.
  • msetcheck
    The multiset check polynomial protocol.
  • sumcheck
    The multivariate sumcheck polynomial protocol.
  • sumcheck_v2
    The multivariate sumcheck and zerocheck polynomial protocols.
  • zerocheck
    The zerocheck interactive reduction, as defined in DP23, Section 4.