halo2_axiom/poly/ipa/
strategy.rs

Help
1use super::commitment::{IPACommitmentScheme, ParamsIPA};
2use super::msm::MSMIPA;
3use super::multiopen::VerifierIPA;
4use crate::{
5    arithmetic::best_multiexp,
6    plonk::Error,
7    poly::{
8        commitment::MSM,
9        strategy::{Guard, VerificationStrategy},
10    },
11};
12use ff::Field;
13use group::Curve;
14use halo2curves::CurveAffine;
15use rand_core::OsRng;
16
17/// Wrapper for verification accumulator
18#[derive(Debug, Clone)]
19pub struct GuardIPA<'params, C: CurveAffine> {
20    pub(crate) msm: MSMIPA<'params, C>,
21    pub(crate) neg_c: C::Scalar,
22    pub(crate) u: Vec<C::Scalar>,
23    pub(crate) u_packed: Vec<C::Scalar>,
24}
25
26/// An accumulator instance consisting of an evaluation claim and a proof.
27#[derive(Debug, Clone)]
28pub struct Accumulator<C: CurveAffine> {
29    /// The claimed output of the linear-time polycommit opening protocol
30    pub g: C,
31
32    /// A vector of challenges u_0, ..., u_{k - 1} sampled by the verifier, to
33    /// be used in computing G'_0.
34    pub u_packed: Vec<C::Scalar>,
35}
36
37/// Define accumulator type as `MSMIPA`
38impl<'params, C: CurveAffine> Guard<IPACommitmentScheme<C>> for GuardIPA<'params, C> {
39    type MSMAccumulator = MSMIPA<'params, C>;
40}
41
42/// IPA specific operations
43impl<'params, C: CurveAffine> GuardIPA<'params, C> {
44    /// Lets caller supply the challenges and obtain an MSM with updated
45    /// scalars and points.
46    pub fn use_challenges(mut self) -> MSMIPA<'params, C> {
47        let s = compute_s(&self.u, self.neg_c);
48        self.msm.add_to_g_scalars(&s);
49
50        self.msm
51    }
52
53    /// Lets caller supply the purported G point and simply appends
54    /// [-c] G to return an updated MSM.
55    pub fn use_g(mut self, g: C) -> (MSMIPA<'params, C>, Accumulator<C>) {
56        self.msm.append_term(self.neg_c, g.into());
57
58        let accumulator = Accumulator {
59            g,
60            u_packed: self.u_packed,
61        };
62
63        (self.msm, accumulator)
64    }
65
66    /// Computes G = ⟨s, params.g⟩
67    pub fn compute_g(&self) -> C {
68        let s = compute_s(&self.u, C::Scalar::ONE);
69
70        best_multiexp(&s, &self.msm.params.g).to_affine()
71    }
72}
73
74/// A verifier that checks multiple proofs in a batch.
75#[derive(Debug)]
76pub struct AccumulatorStrategy<'params, C: CurveAffine> {
77    msm: MSMIPA<'params, C>,
78}
79
80impl<'params, C: CurveAffine>
81    VerificationStrategy<'params, IPACommitmentScheme<C>, VerifierIPA<'params, C>>
82    for AccumulatorStrategy<'params, C>
83{
84    type Output = Self;
85
86    fn new(params: &'params ParamsIPA<C>) -> Self {
87        AccumulatorStrategy {
88            msm: MSMIPA::new(params),
89        }
90    }
91
92    fn process(
93        mut self,
94        f: impl FnOnce(MSMIPA<'params, C>) -> Result<GuardIPA<'params, C>, Error>,
95    ) -> Result<Self::Output, Error> {
96        self.msm.scale(C::Scalar::random(OsRng));
97        let guard = f(self.msm)?;
98
99        Ok(Self {
100            msm: guard.use_challenges(),
101        })
102    }
103
104    /// Finalizes the batch and checks its validity.
105    ///
106    /// Returns `false` if *some* proof was invalid. If the caller needs to identify
107    /// specific failing proofs, it must re-process the proofs separately.
108    #[must_use]
109    fn finalize(self) -> bool {
110        self.msm.check()
111    }
112}
113
114/// A verifier that checks single proof
115#[derive(Debug)]
116pub struct SingleStrategy<'params, C: CurveAffine> {
117    msm: MSMIPA<'params, C>,
118}
119
120impl<'params, C: CurveAffine>
121    VerificationStrategy<'params, IPACommitmentScheme<C>, VerifierIPA<'params, C>>
122    for SingleStrategy<'params, C>
123{
124    type Output = ();
125
126    fn new(params: &'params ParamsIPA<C>) -> Self {
127        SingleStrategy {
128            msm: MSMIPA::new(params),
129        }
130    }
131
132    fn process(
133        self,
134        f: impl FnOnce(MSMIPA<'params, C>) -> Result<GuardIPA<'params, C>, Error>,
135    ) -> Result<Self::Output, Error> {
136        let guard = f(self.msm)?;
137        let msm = guard.use_challenges();
138        if msm.check() {
139            Ok(())
140        } else {
141            Err(Error::ConstraintSystemFailure)
142        }
143    }
144
145    /// Finalizes the batch and checks its validity.
146    ///
147    /// Returns `false` if *some* proof was invalid. If the caller needs to identify
148    /// specific failing proofs, it must re-process the proofs separately.
149    #[must_use]
150    fn finalize(self) -> bool {
151        unreachable!()
152    }
153}
154
155/// Computes the coefficients of $g(X) = \prod\limits_{i=0}^{k-1} (1 + u_{k - 1 - i} X^{2^i})$.
156fn compute_s<F: Field>(u: &[F], init: F) -> Vec<F> {
157    assert!(!u.is_empty());
158    let mut v = vec![F::ZERO; 1 << u.len()];
159    v[0] = init;
160
161    for (len, u_j) in u.iter().rev().enumerate().map(|(i, u_j)| (1 << i, u_j)) {
162        let (left, right) = v.split_at_mut(len);
163        let right = &mut right[0..len];
164        right.copy_from_slice(left);
165        for v in right {
166            *v *= u_j;
167        }
168    }
169
170    v
171}
halo2_axiom/poly/ipa/strategy.rs

halo2_axiom/poly/ipa/
strategy.rs
