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