1use crate::{
2 loader::{native::NativeLoader, LoadedScalar, Loader},
3 pcs::{
4 ipa::{
5 h_coeffs, h_eval, Ipa, IpaAccumulator, IpaProof, IpaProvingKey, IpaSuccinctVerifyingKey,
6 },
7 AccumulationScheme, AccumulationSchemeProver,
8 },
9 util::{
10 arithmetic::{Curve, CurveAffine, Field},
11 msm::Msm,
12 poly::Polynomial,
13 transcript::{TranscriptRead, TranscriptWrite},
14 Itertools,
15 },
16 Error,
17};
18use rand::Rng;
19use std::{array, fmt::Debug, iter, marker::PhantomData};
20
21#[derive(Clone, Debug)]
24pub struct IpaAs<C, MOS>(PhantomData<(C, MOS)>);
25
26impl<C, L, MOS> AccumulationScheme<C, L> for IpaAs<C, MOS>
27where
28 C: CurveAffine,
29 L: Loader<C>,
30 MOS: Clone + Debug,
31{
32 type Accumulator = IpaAccumulator<C, L>;
33 type VerifyingKey = IpaSuccinctVerifyingKey<C>;
34 type Proof = IpaAsProof<C, L>;
35
36 fn read_proof<T>(
37 vk: &Self::VerifyingKey,
38 instances: &[Self::Accumulator],
39 transcript: &mut T,
40 ) -> Result<Self::Proof, Error>
41 where
42 T: TranscriptRead<C, L>,
43 {
44 IpaAsProof::read(vk, instances, transcript)
45 }
46
47 fn verify(
48 vk: &Self::VerifyingKey,
49 instances: &[Self::Accumulator],
50 proof: &Self::Proof,
51 ) -> Result<Self::Accumulator, Error> {
52 let loader = proof.z.loader();
53 let s = vk.s.as_ref().map(|s| loader.ec_point_load_const(s));
54
55 let (u, h) = instances
56 .iter()
57 .map(|IpaAccumulator { u, xi }| (u.clone(), h_eval(xi, &proof.z)))
58 .chain(proof.a_b_u.as_ref().map(|(a, b, u)| (u.clone(), a.clone() * &proof.z + b)))
59 .unzip::<_, _, Vec<_>, Vec<_>>();
60 let powers_of_alpha = proof.alpha.powers(u.len());
61
62 let mut c = powers_of_alpha
63 .iter()
64 .zip(u.iter())
65 .map(|(power_of_alpha, u)| Msm::<C, L>::base(u) * power_of_alpha)
66 .sum::<Msm<_, _>>();
67 if let Some(omega) = proof.omega.as_ref() {
68 c += Msm::base(s.as_ref().unwrap()) * omega;
69 }
70 let v = loader.sum_products(&powers_of_alpha.iter().zip(h.iter()).collect_vec());
71
72 Ipa::succinct_verify(vk, &c, &proof.z, &v, &proof.ipa)
73 }
74}
75
76#[derive(Clone, Debug)]
78pub struct IpaAsProof<C, L>
79where
80 C: CurveAffine,
81 L: Loader<C>,
82{
83 a_b_u: Option<(L::LoadedScalar, L::LoadedScalar, L::LoadedEcPoint)>,
84 omega: Option<L::LoadedScalar>,
85 alpha: L::LoadedScalar,
86 z: L::LoadedScalar,
87 ipa: IpaProof<C, L>,
88}
89
90impl<C, L> IpaAsProof<C, L>
91where
92 C: CurveAffine,
93 L: Loader<C>,
94{
95 fn read<T>(
96 vk: &IpaSuccinctVerifyingKey<C>,
97 instances: &[IpaAccumulator<C, L>],
98 transcript: &mut T,
99 ) -> Result<Self, Error>
100 where
101 T: TranscriptRead<C, L>,
102 {
103 assert!(instances.len() > 1);
104
105 let a_b_u = vk
106 .zk()
107 .then(|| {
108 let a = transcript.read_scalar()?;
109 let b = transcript.read_scalar()?;
110 let u = transcript.read_ec_point()?;
111 Ok((a, b, u))
112 })
113 .transpose()?;
114 let omega = vk
115 .zk()
116 .then(|| {
117 let omega = transcript.read_scalar()?;
118 Ok(omega)
119 })
120 .transpose()?;
121
122 for accumulator in instances {
123 for xi in accumulator.xi.iter() {
124 transcript.common_scalar(xi)?;
125 }
126 transcript.common_ec_point(&accumulator.u)?;
127 }
128
129 let alpha = transcript.squeeze_challenge();
130 let z = transcript.squeeze_challenge();
131
132 let ipa = IpaProof::read(vk, transcript)?;
133
134 Ok(Self { a_b_u, omega, alpha, z, ipa })
135 }
136}
137
138impl<C, MOS> AccumulationSchemeProver<C> for IpaAs<C, MOS>
139where
140 C: CurveAffine,
141 MOS: Clone + Debug,
142{
143 type ProvingKey = IpaProvingKey<C>;
144
145 fn create_proof<T, R>(
146 pk: &Self::ProvingKey,
147 instances: &[IpaAccumulator<C, NativeLoader>],
148 transcript: &mut T,
149 mut rng: R,
150 ) -> Result<IpaAccumulator<C, NativeLoader>, Error>
151 where
152 T: TranscriptWrite<C>,
153 R: Rng,
154 {
155 assert!(instances.len() > 1);
156
157 let a_b_u = pk
158 .zk()
159 .then(|| {
160 let [a, b] = array::from_fn(|_| C::Scalar::random(&mut rng));
161 let u = (pk.g[1] * a + pk.g[0] * b).to_affine();
162 transcript.write_scalar(a)?;
163 transcript.write_scalar(b)?;
164 transcript.write_ec_point(u)?;
165 Ok((a, b, u))
166 })
167 .transpose()?;
168 let omega = pk
169 .zk()
170 .then(|| {
171 let omega = C::Scalar::random(&mut rng);
172 transcript.write_scalar(omega)?;
173 Ok(omega)
174 })
175 .transpose()?;
176
177 for accumulator in instances {
178 for xi in accumulator.xi.iter() {
179 transcript.common_scalar(xi)?;
180 }
181 transcript.common_ec_point(&accumulator.u)?;
182 }
183
184 let alpha = transcript.squeeze_challenge();
185 let z = transcript.squeeze_challenge();
186
187 let (u, h) = instances
188 .iter()
189 .map(|IpaAccumulator { u, xi }| (*u, h_coeffs(&xi[..], C::Scalar::ONE)))
190 .chain(a_b_u.map(|(a, b, u)| {
191 (
192 u,
193 iter::empty()
194 .chain([b, a])
195 .chain(iter::repeat(C::Scalar::ZERO).take(pk.domain.n - 2))
196 .collect(),
197 )
198 }))
199 .unzip::<_, _, Vec<_>, Vec<_>>();
200 let powers_of_alpha = alpha.powers(u.len());
201
202 let h = powers_of_alpha
203 .into_iter()
204 .zip(h.into_iter().map(Polynomial::new))
205 .map(|(power_of_alpha, h)| h * power_of_alpha)
206 .sum::<Polynomial<_>>();
207
208 Ipa::create_proof(pk, &h.to_vec(), &z, omega.as_ref(), transcript, &mut rng)
209 }
210}
211
212#[cfg(test)]
213mod test {
214 use crate::halo2_curves::pasta::pallas;
215 use crate::halo2_proofs::transcript::{
216 Blake2bRead, Blake2bWrite, TranscriptReadBuffer, TranscriptWriterBuffer,
217 };
218 use crate::{
219 pcs::{
220 ipa::{self, IpaProvingKey},
221 AccumulationDecider, AccumulationScheme, AccumulationSchemeProver,
222 },
223 util::{arithmetic::Field, msm::Msm, poly::Polynomial, Itertools},
224 };
225 use rand::rngs::OsRng;
226 use std::iter;
227
228 #[test]
229 fn test_ipa_as() {
230 type Ipa = ipa::Ipa<pallas::Affine>;
231 type IpaAs = ipa::IpaAs<pallas::Affine, ()>;
232
233 let k = 10;
234 let zk = true;
235 let mut rng = OsRng;
236
237 let pk = IpaProvingKey::<pallas::Affine>::rand(k, zk, &mut rng);
238 let accumulators = iter::repeat_with(|| {
239 let (c, z, v, proof) = {
240 let p = Polynomial::<pallas::Scalar>::rand(pk.domain.n, &mut rng);
241 let omega = pk.zk().then(|| pallas::Scalar::random(&mut rng));
242 let c = pk.commit(&p, omega);
243 let z = pallas::Scalar::random(&mut rng);
244 let v = p.evaluate(z);
245 let mut transcript = Blake2bWrite::init(Vec::new());
246 Ipa::create_proof(&pk, &p[..], &z, omega.as_ref(), &mut transcript, &mut rng)
247 .unwrap();
248 (c, z, v, transcript.finalize())
249 };
250
251 let svk = pk.svk();
252 let accumulator = {
253 let mut transcript = Blake2bRead::init(proof.as_slice());
254 let proof = Ipa::read_proof(&svk, &mut transcript).unwrap();
255 Ipa::succinct_verify(&svk, &Msm::base(&c), &z, &v, &proof).unwrap()
256 };
257
258 accumulator
259 })
260 .take(10)
261 .collect_vec();
262
263 let proof = {
264 let apk = pk.clone();
265 let mut transcript = Blake2bWrite::init(Vec::new());
266 IpaAs::create_proof(&apk, &accumulators, &mut transcript, &mut rng).unwrap();
267 transcript.finalize()
268 };
269
270 let accumulator = {
271 let avk = pk.svk();
272 let mut transcript = Blake2bRead::init(proof.as_slice());
273 let proof = IpaAs::read_proof(&avk, &accumulators, &mut transcript).unwrap();
274 IpaAs::verify(&avk, &accumulators, &proof).unwrap()
275 };
276
277 let dk = pk.dk();
278 assert!(IpaAs::decide(&dk, accumulator).is_ok());
279 }
280}