1//! Main module for the HyperPlonk PolyIOP.
  2
  3use crate::selectors::SelectorColumn;
  4use ark_ec::PairingEngine;
  5use ark_ff::PrimeField;
  6use ark_poly::DenseMultilinearExtension;
  7use ark_std::cmp::max;
  8use pcs::PolynomialCommitmentScheme;
  9use poly_iop::prelude::{PermutationCheck, ZeroCheck};
 10use std::rc::Rc;
 11
 12/// The proof for the HyperPlonk PolyIOP, consists of the following:
 13///   - a batch commitment to all the witness MLEs
 14///   - a batch opening to all the MLEs at certain index
 15///   - the zero-check proof for checking custom gate-satisfiability
 16///   - the permutation-check proof for checking the copy constraints
 17#[derive(Clone, Debug, Default, PartialEq)]
 18pub struct HyperPlonkProof<E, PC, PCS>
 19where
 20    E: PairingEngine,
 21    PC: PermutationCheck<E, PCS>,
 22    PCS: PolynomialCommitmentScheme<E>,
 23{
 24    // =======================================================================
 25    // PCS components: common
 26    // =======================================================================
 27    /// PCS commit for witnesses
 28    pub w_merged_com: PCS::Commitment,
 29    // =======================================================================
 30    // PCS components: permutation check
 31    // =======================================================================
 32    /// prod(x)'s evaluations
 33    /// sequence: prod(0,x), prod(1, x), prod(x, 0), prod(x, 1), prod(1, ..., 1,
 34    /// 0)
 35    pub prod_evals: Vec<E::Fr>,
 36    /// prod(x)'s openings
 37    /// sequence: prod(0,x), prod(1, x), prod(x, 0), prod(x, 1), prod(1, ..., 1,
 38    /// 0)
 39    pub prod_openings: Vec<PCS::Proof>,
 40    /// PCS openings for witness on permutation check point
 41    // TODO: replace me with a batch opening
 42    pub witness_perm_check_opening: PCS::Proof,
 43    /// Evaluates of witnesses on permutation check point
 44    pub witness_perm_check_eval: E::Fr,
 45    /// PCS openings for selectors on permutation check point
 46    // TODO: replace me with a batch opening
 47    pub perm_oracle_opening: PCS::Proof,
 48    /// Evaluates of selectors on permutation check point
 49    pub perm_oracle_eval: E::Fr,
 50    // =======================================================================
 51    // PCS components: zero check
 52    // =======================================================================
 53    /// PCS openings for witness on zero check point
 54    // TODO: replace me with a batch opening
 55    pub witness_zero_check_openings: Vec<PCS::Proof>,
 56    /// Evaluates of witnesses on zero check point
 57    pub witness_zero_check_evals: Vec<E::Fr>,
 58    /// PCS openings for selectors on zero check point
 59    // TODO: replace me with a batch opening
 60    pub selector_oracle_openings: Vec<PCS::Proof>,
 61    /// Evaluates of selectors on zero check point
 62    pub selector_oracle_evals: Vec<E::Fr>,
 63    // =======================================================================
 64    // PCS components: public inputs
 65    // =======================================================================
 66    /// Evaluates of public inputs on r_pi from transcript
 67    pub pi_eval: E::Fr,
 68    /// Opening of public inputs on r_pi from transcript
 69    pub pi_opening: PCS::Proof,
 70    // =======================================================================
 71    // IOP components
 72    // =======================================================================
 73    /// the custom gate zerocheck proof
 74    pub zero_check_proof: <PC as ZeroCheck<E::Fr>>::ZeroCheckProof,
 75    /// the permutation check proof for copy constraints
 76    pub perm_check_proof: PC::PermutationProof,
 77}
 78
 79/// The HyperPlonk instance parameters, consists of the following:
 80///   - the number of variables in the poly-IOP
 81///   - binary log of the number of public input variables
 82///   - binary log of the number of selectors
 83///   - binary log of the number of witness wires
 84///   - the customized gate function
 85#[derive(Clone, Debug, Default, PartialEq, Eq)]
 86pub struct HyperPlonkParams {
 87    /// the number of variables in polys
 88    pub nv: usize,
 89    /// binary log of the public input length
 90    pub log_pub_input_len: usize,
 91    // binary log of the number of selectors
 92    pub log_n_selectors: usize,
 93    /// binary log of the number of witness wires
 94    pub log_n_wires: usize,
 95    /// customized gate function
 96    pub gate_func: CustomizedGates,
 97}
 98
 99/// The HyperPlonk index, consists of the following:
100///   - HyperPlonk parameters
101///   - the wire permutation
102///   - the selector vectors
103#[derive(Clone, Debug, Default, PartialEq, Eq)]
104pub struct HyperPlonkIndex<F: PrimeField> {
105    pub params: HyperPlonkParams,
106    pub permutation: Vec<F>,
107    pub selectors: Vec<SelectorColumn<F>>,
108}
109
110/// The HyperPlonk proving key, consists of the following:
111///   - the hyperplonk instance parameters
112///   - the preprocessed polynomials output by the indexer
113#[derive(Clone, Debug, Default, PartialEq)]
114pub struct HyperPlonkProvingKey<E: PairingEngine, PCS: PolynomialCommitmentScheme<E>> {
115    /// hyperplonk instance parameters
116    pub params: HyperPlonkParams,
117    /// the preprocessed permutation polynomials
118    pub permutation_oracle: Rc<DenseMultilinearExtension<E::Fr>>,
119    /// the preprocessed selector polynomials
120    // TODO: merge the list into a single MLE
121    pub selector_oracles: Vec<Rc<DenseMultilinearExtension<E::Fr>>>,
122    /// the parameters for PCS commitment
123    pub pcs_param: PCS::ProverParam,
124}
125
126/// The HyperPlonk verifying key, consists of the following:
127///   - the hyperplonk instance parameters
128///   - the preprocessed polynomials output by the indexer
129#[derive(Clone, Debug, Default, PartialEq)]
130pub struct HyperPlonkVerifyingKey<E: PairingEngine, PCS: PolynomialCommitmentScheme<E>> {
131    /// hyperplonk instance parameters
132    pub params: HyperPlonkParams,
133    /// the parameters for PCS commitment
134    pub pcs_param: PCS::VerifierParam,
135    /// Selector's commitment
136    // TODO: replace me with a batch commitment
137    pub selector_com: Vec<PCS::Commitment>,
138    /// Permutation oracle's commitment
139    pub perm_com: PCS::Commitment,
140}
141
142/// Customized gate is a list of tuples of
143///     (coefficient, selector_index, wire_indices)
144///
145/// Example:
146///     q_L(X) * W_1(X)^5 - W_2(X)
147/// is represented as
148/// vec![
149///     ( 1,    Some(id_qL),    vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
150///     (-1,    None,           vec![id_W2])
151/// ]
152///
153/// CustomizedGates {
154///     gates: vec![
155///         (1, Some(0), vec![0, 0, 0, 0, 0]),
156///         (-1, None, vec![1])
157///     ],
158/// };
159/// where id_qL = 0 // first selector
160/// id_W1 = 0 // first witness
161/// id_w2 = 1 // second witness
162///
163/// NOTE: here coeff is a signed integer, instead of a field element
164#[derive(Clone, Debug, Default, PartialEq, Eq)]
165pub struct CustomizedGates {
166    pub(crate) gates: Vec<(i64, Option<usize>, Vec<usize>)>,
167}
168
169impl CustomizedGates {
170    /// The degree of the algebraic customized gate
171    pub fn degree(&self) -> usize {
172        let mut res = 0;
173        for x in self.gates.iter() {
174            res = max(res, x.2.len() + (x.1.is_some() as usize))
175        }
176        res
177    }
178}