1//! Main module for the ZeroCheck protocol.
  2
  3use std::fmt::Debug;
  4
  5use crate::{errors::PolyIOPErrors, sum_check::SumCheck, PolyIOP};
  6use arithmetic::build_eq_x_r;
  7use ark_ff::PrimeField;
  8use ark_poly::MultilinearExtension;
  9use ark_std::{end_timer, start_timer};
 10use transcript::IOPTranscript;
 11
 12/// A zero check IOP subclaim for \hat f(x) is 0, consists of the following:
 13///   - the SubClaim from the SumCheck
 14///   - the initial challenge r which is used to build eq(x, r) in ZeroCheck
 15#[derive(Clone, Debug, Default, PartialEq)]
 16pub struct ZeroCheckSubClaim<F: PrimeField, SC: SumCheck<F>> {
 17    // the SubClaim from the SumCheck
 18    pub sum_check_sub_claim: SC::SumCheckSubClaim,
 19    /// the expected evaluation
 20    pub expected_evaluation: F,
 21    // the initial challenge r which is used to build eq(x, r)
 22    pub init_challenge: Vec<F>,
 23}
 24
 25/// A ZeroCheck is derived from SumCheck.
 26pub trait ZeroCheck<F: PrimeField>: SumCheck<F> {
 27    type ZeroCheckSubClaim: Clone + Debug + Default + PartialEq;
 28    type ZeroCheckProof: Clone + Debug + Default + PartialEq;
 29
 30    /// Initialize the system with a transcript
 31    ///
 32    /// This function is optional -- in the case where a ZeroCheck is
 33    /// an building block for a more complex protocol, the transcript
 34    /// may be initialized by this complex protocol, and passed to the
 35    /// ZeroCheck prover/verifier.
 36    fn init_transcript() -> Self::Transcript;
 37
 38    /// initialize the prover to argue for the sum of polynomial over
 39    /// {0,1}^`num_vars` is zero.
 40    fn prove(
 41        poly: &Self::VirtualPolynomial,
 42        transcript: &mut Self::Transcript,
 43    ) -> Result<Self::ZeroCheckProof, PolyIOPErrors>;
 44
 45    /// verify the claimed sum using the proof
 46    fn verify(
 47        proof: &Self::ZeroCheckProof,
 48        aux_info: &Self::VPAuxInfo,
 49        transcript: &mut Self::Transcript,
 50    ) -> Result<Self::ZeroCheckSubClaim, PolyIOPErrors>;
 51}
 52
 53impl<F: PrimeField> ZeroCheck<F> for PolyIOP<F> {
 54    /// A ZeroCheck SubClaim consists of
 55    /// - the SubClaim from the SumCheck
 56    /// - the initial challenge r which is used to build eq(x, r)
 57    type ZeroCheckSubClaim = ZeroCheckSubClaim<F, Self>;
 58    /// A ZeroCheckProof is a SumCheckProof
 59    type ZeroCheckProof = Self::SumCheckProof;
 60
 61    /// Initialize the system with a transcript
 62    ///
 63    /// This function is optional -- in the case where a ZeroCheck is
 64    /// an building block for a more complex protocol, the transcript
 65    /// may be initialized by this complex protocol, and passed to the
 66    /// ZeroCheck prover/verifier.
 67    fn init_transcript() -> Self::Transcript {
 68        IOPTranscript::<F>::new(b"Initializing ZeroCheck transcript")
 69    }
 70
 71    /// Initialize the prover to argue for the sum of polynomial f(x) over
 72    /// {0,1}^`num_vars` is zero.
 73    ///
 74    /// f(x) is zero if \hat f(x) := f(x) * eq(x,r) is also a zero polynomial
 75    /// for a random r sampled from transcript.
 76    ///
 77    /// This function will build the \hat f(x) and then invoke the sumcheck
 78    /// protocol to generate a proof for which the sum of \hat f(x) is zero
 79    fn prove(
 80        poly: &Self::VirtualPolynomial,
 81        transcript: &mut Self::Transcript,
 82    ) -> Result<Self::ZeroCheckProof, PolyIOPErrors> {
 83        let start = start_timer!(|| "zero check prove");
 84
 85        let length = poly.aux_info.num_variables;
 86        let r = transcript.get_and_append_challenge_vectors(b"0check r", length)?;
 87        let f_hat = poly.build_f_hat(r.as_ref())?;
 88        let res = <Self as SumCheck<F>>::prove(&f_hat, transcript);
 89
 90        end_timer!(start);
 91        res
 92    }
 93
 94    /// Verify that the polynomial's sum is zero using the proof.
 95    /// Return a Self::Subclaim that consists of the
 96    ///
 97    /// - a Subclaim that the sum is zero
 98    /// - the initial challenge `r` that is used to build `eq(x, r)`
 99    ///
100    /// This function will check that \hat f(x)'s sum is zero. It does not check
101    /// `\hat f(x)` is build correctly. The caller needs to makes sure that
102    /// `\hat f(x) = f(x) * eq(x, r)`
103    fn verify(
104        proof: &Self::ZeroCheckProof,
105        fx_aux_info: &Self::VPAuxInfo,
106        transcript: &mut Self::Transcript,
107    ) -> Result<Self::ZeroCheckSubClaim, PolyIOPErrors> {
108        let start = start_timer!(|| "zero check verify");
109
110        // check that the sum is zero
111        if proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1] != F::zero() {
112            return Err(PolyIOPErrors::InvalidProof(format!(
113                "zero check: sum {} is not zero",
114                proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1]
115            )));
116        }
117
118        // generate `r` and pass it to the caller for correctness check
119        let length = fx_aux_info.num_variables;
120        let r = transcript.get_and_append_challenge_vectors(b"0check r", length)?;
121
122        // hat_fx's max degree is increased by eq(x, r).degree() which is 1
123        let mut hat_fx_aux_info = fx_aux_info.clone();
124        hat_fx_aux_info.max_degree += 1;
125        let subclaim =
126            <Self as SumCheck<F>>::verify(F::zero(), proof, &hat_fx_aux_info, transcript)?;
127
128        // expected_eval = sumcheck.expect_eval/eq(x, r)
129        // where x = sum_check_sub_claim.point
130        let eq_x_r = build_eq_x_r(&r)?;
131        let expected_evaluation = subclaim.expected_evaluation
132            / eq_x_r.evaluate(&subclaim.point).ok_or_else(|| {
133                PolyIOPErrors::InvalidParameters("evaluation dimension does not match".to_string())
134            })?;
135
136        end_timer!(start);
137        Ok(ZeroCheckSubClaim {
138            sum_check_sub_claim: subclaim,
139            expected_evaluation,
140            init_challenge: r,
141        })
142    }
143}
144
145#[cfg(test)]
146mod test {
147
148    use super::ZeroCheck;
149    use crate::{errors::PolyIOPErrors, PolyIOP};
150    use arithmetic::VirtualPolynomial;
151    use ark_bls12_381::Fr;
152    use ark_std::test_rng;
153
154    fn test_zerocheck(
155        nv: usize,
156        num_multiplicands_range: (usize, usize),
157        num_products: usize,
158    ) -> Result<(), PolyIOPErrors> {
159        let mut rng = test_rng();
160
161        {
162            // good path: zero virtual poly
163            let poly =
164                VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
165
166            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
167            transcript.append_message(b"testing", b"initializing transcript for testing")?;
168            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
169
170            let poly_info = poly.aux_info.clone();
171            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
172            transcript.append_message(b"testing", b"initializing transcript for testing")?;
173            let subclaim =
174                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?
175                    .sum_check_sub_claim;
176            assert!(
177                poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
178                "wrong subclaim"
179            );
180        }
181
182        {
183            // bad path: random virtual poly whose sum is not zero
184            let (poly, _sum) =
185                VirtualPolynomial::<Fr>::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
186
187            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
188            transcript.append_message(b"testing", b"initializing transcript for testing")?;
189            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
190
191            let poly_info = poly.aux_info.clone();
192            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
193            transcript.append_message(b"testing", b"initializing transcript for testing")?;
194
195            assert!(
196                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
197                    .is_err()
198            );
199        }
200
201        Ok(())
202    }
203
204    #[test]
205    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
206        let nv = 1;
207        let num_multiplicands_range = (4, 5);
208        let num_products = 1;
209
210        test_zerocheck(nv, num_multiplicands_range, num_products)
211    }
212    #[test]
213    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
214        let nv = 5;
215        let num_multiplicands_range = (4, 9);
216        let num_products = 5;
217
218        test_zerocheck(nv, num_multiplicands_range, num_products)
219    }
220
221    #[test]
222    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
223        let nv = 0;
224        let num_multiplicands_range = (4, 13);
225        let num_products = 5;
226
227        assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
228        Ok(())
229    }
230}