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