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