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