mina_tree/proofs/
unfinalized.rs

1use ark_ff::fields::arithmetic::InvalidBigInt;
2use kimchi::proof::{PointEvaluations, ProofEvaluations};
3use mina_curves::pasta::{Fp, Fq};
4use mina_p2p_messages::v2;
5
6use crate::proofs::{
7    field::FieldWitness, public_input::plonk_checks::derive_plonk, step::FeatureFlags,
8    util::two_u64_to_field, verification::make_scalars_env, BACKEND_TICK_ROUNDS_N,
9};
10
11use super::{
12    public_input::{
13        plonk_checks::{PlonkMinimal, ShiftedValue},
14        prepared_statement::Plonk,
15        scalar_challenge::ScalarChallenge,
16    },
17    to_field_elements::ToFieldElements,
18    transaction::Check,
19    util::four_u64_to_field,
20    verification::prev_evals_from_p2p,
21    witness::Witness,
22    BACKEND_TOCK_ROUNDS_N,
23};
24
25pub mod ro {
26
27    use mina_curves::pasta::{Fp, Fq};
28
29    use crate::proofs::{
30        field::FieldWitness, public_input::scalar_challenge::ScalarChallenge,
31        transaction::legacy_input::BitsIterator,
32    };
33
34    fn of_bits<F: FieldWitness>(bs: [bool; 255]) -> F {
35        bs.iter().rev().fold(F::zero(), |acc, b| {
36            let acc = acc + acc;
37            if *b {
38                acc + F::one()
39            } else {
40                acc
41            }
42        })
43    }
44
45    pub fn bits_random_oracle<const N: usize>(s: &str) -> [bool; N] {
46        use blake2::{
47            digest::{Update, VariableOutput},
48            Blake2sVar,
49        };
50
51        let mut hasher = Blake2sVar::new(32).unwrap();
52        hasher.update(s.as_bytes());
53        let hash = hasher.finalize_boxed();
54
55        let mut bits = BitsIterator::<32> {
56            index: 0,
57            number: (&*hash).try_into().unwrap(),
58        }
59        .take(N);
60
61        std::array::from_fn(|_| bits.next().unwrap())
62    }
63
64    fn ro<T, F, const N: usize>(n: usize, label: &str, fun: F) -> T
65    where
66        F: FnOnce([bool; N]) -> T,
67    {
68        let s = format!("{}_{}", label, n);
69        fun(bits_random_oracle::<N>(&s))
70    }
71
72    pub fn tock(n: usize) -> Fq {
73        ro(n, "fq", of_bits::<Fq>)
74    }
75
76    pub fn tick(n: usize) -> Fp {
77        ro(n, "fq", of_bits::<Fp>)
78    }
79
80    pub fn chal(n: usize) -> ScalarChallenge {
81        fn of_bits(bits: [bool; 128]) -> [u64; 2] {
82            let mut limbs = bits.chunks(64).map(|chunk| {
83                chunk.iter().enumerate().fold(
84                    0u64,
85                    |acc, (i, b)| {
86                        if *b {
87                            acc | (1 << i)
88                        } else {
89                            acc
90                        }
91                    },
92                )
93            });
94            std::array::from_fn(|_| limbs.next().unwrap())
95        }
96
97        let [a, b] = ro(n, "chal", of_bits);
98        ScalarChallenge::new(a, b)
99    }
100}
101
102/// No `BranchData`
103#[derive(Clone, Debug)]
104pub struct DeferredValues {
105    pub plonk: Plonk<Fq>,
106    pub combined_inner_product: <Fq as FieldWitness>::Shifting,
107    pub b: <Fq as FieldWitness>::Shifting,
108    pub xi: [u64; 2],
109    pub bulletproof_challenges: Vec<[u64; 2]>,
110}
111
112#[derive(Clone, Debug)]
113pub struct Unfinalized {
114    pub deferred_values: DeferredValues,
115    pub should_finalize: bool,
116    pub sponge_digest_before_evaluations: [u64; 4],
117}
118
119#[derive(Clone, Debug)]
120pub struct EvalsWithPublicInput<F: FieldWitness> {
121    pub evals: ProofEvaluations<PointEvaluations<Vec<F>>>,
122    pub public_input: (Vec<F>, Vec<F>),
123}
124
125#[derive(Clone, Debug)]
126pub struct AllEvals<F: FieldWitness> {
127    pub ft_eval1: F,
128    pub evals: EvalsWithPublicInput<F>,
129}
130
131impl AllEvals<Fq> {
132    /// Dummy.evals
133    fn dummy_impl() -> Self {
134        let to_vec = |p: PointEvaluations<_>| p.map(&|v| vec![v]);
135        Self {
136            ft_eval1: ro::tock(89),
137            evals: EvalsWithPublicInput {
138                evals: dummy_evals().map(&to_vec),
139                public_input: (vec![ro::tock(88)], vec![ro::tock(87)]),
140            },
141        }
142    }
143
144    /// Dummy.evals
145    pub fn dummy() -> Self {
146        cache_one! { AllEvals<Fq>, Self::dummy_impl() }
147    }
148}
149
150impl<F: FieldWitness> TryFrom<&v2::PicklesProofProofsVerified2ReprStableV2PrevEvals>
151    for AllEvals<F>
152{
153    type Error = InvalidBigInt;
154
155    fn try_from(
156        value: &v2::PicklesProofProofsVerified2ReprStableV2PrevEvals,
157    ) -> Result<Self, Self::Error> {
158        let v2::PicklesProofProofsVerified2ReprStableV2PrevEvals {
159            evals:
160                v2::PicklesProofProofsVerified2ReprStableV2PrevEvalsEvals {
161                    public_input: (p0, p1),
162                    evals,
163                },
164            ft_eval1,
165        } = value;
166
167        Ok(Self {
168            ft_eval1: ft_eval1.to_field()?,
169            evals: EvalsWithPublicInput {
170                evals: prev_evals_from_p2p::<F>(evals)?,
171                public_input: (vec![p0.to_field()?], vec![p1.to_field()?]),
172            },
173        })
174    }
175}
176
177/// Equivalent of `to_kimchi` in OCaml
178pub fn evals_from_p2p<F: FieldWitness>(
179    e: &v2::PicklesWrapWireProofEvaluationsStableV1,
180) -> anyhow::Result<ProofEvaluations<PointEvaluations<Vec<F>>>> {
181    let v2::PicklesWrapWireProofEvaluationsStableV1 {
182        w,
183        coefficients,
184        z,
185        s,
186        generic_selector,
187        poseidon_selector,
188        complete_add_selector,
189        mul_selector,
190        emul_selector,
191        endomul_scalar_selector,
192    } = e;
193
194    use mina_p2p_messages::bigint::BigInt;
195
196    let of =
197        |(zeta, zeta_omega): &(BigInt, BigInt)| -> Result<PointEvaluations<Vec<F>>, InvalidBigInt> {
198            Ok(PointEvaluations {
199                zeta: vec![zeta.to_field()?],
200                zeta_omega: vec![zeta_omega.to_field()?],
201            })
202        };
203
204    use std::array;
205    Ok(ProofEvaluations {
206        w: crate::try_array_into_with(w, of)?,
207        z: of(z)?,
208        s: crate::try_array_into_with(s, of)?,
209        coefficients: crate::try_array_into_with(coefficients, of)?,
210        generic_selector: of(generic_selector)?,
211        poseidon_selector: of(poseidon_selector)?,
212        complete_add_selector: of(complete_add_selector)?,
213        mul_selector: of(mul_selector)?,
214        emul_selector: of(emul_selector)?,
215        endomul_scalar_selector: of(endomul_scalar_selector)?,
216        range_check0_selector: None,
217        range_check1_selector: None,
218        foreign_field_add_selector: None,
219        foreign_field_mul_selector: None,
220        xor_selector: None,
221        rot_selector: None,
222        lookup_aggregation: None,
223        lookup_table: None,
224        lookup_sorted: array::from_fn(|_| None),
225        runtime_lookup_table: None,
226        runtime_lookup_table_selector: None,
227        xor_lookup_selector: None,
228        lookup_gate_lookup_selector: None,
229        range_check_lookup_selector: None,
230        foreign_field_mul_lookup_selector: None,
231        public: None,
232    })
233}
234
235fn dummy_evals() -> ProofEvaluations<PointEvaluations<Fq>> {
236    type Evals = ProofEvaluations<PointEvaluations<Fq>>;
237    cache_one! {
238        Evals,
239        {
240            // TODO: Update this
241            let mut n = 86;
242
243            let mut iter = std::iter::from_fn(|| {
244                let res = ro::tock(n);
245                n = n.checked_sub(1)?;
246                Some(res)
247            });
248
249            let mut next = || PointEvaluations {
250                zeta: iter.next().unwrap(),
251                zeta_omega: iter.next().unwrap(),
252            };
253
254            ProofEvaluations {
255                public: None,
256                w: std::array::from_fn(|_| next()),
257                coefficients: std::array::from_fn(|_| next()),
258                z: next(),
259                s: std::array::from_fn(|_| next()),
260                generic_selector: next(),
261                poseidon_selector: next(),
262                complete_add_selector: next(),
263                mul_selector: next(),
264                emul_selector: next(),
265                endomul_scalar_selector: next(),
266                range_check0_selector: None,
267                range_check1_selector: None,
268                foreign_field_add_selector: None,
269                foreign_field_mul_selector: None,
270                xor_selector: None,
271                rot_selector: None,
272                lookup_aggregation: None,
273                lookup_table: None,
274                lookup_sorted: std::array::from_fn(|_| None),
275                runtime_lookup_table: None,
276                runtime_lookup_table_selector: None,
277                xor_lookup_selector: None,
278                lookup_gate_lookup_selector: None,
279                range_check_lookup_selector: None,
280                foreign_field_mul_lookup_selector: None
281            }
282        }
283    }
284}
285
286/// Value of `Dummy.Ipa.Wrap.challenges`
287pub fn dummy_ipa_wrap_challenges() -> [[u64; 2]; BACKEND_TOCK_ROUNDS_N] {
288    cache_one!([[u64; 2]; BACKEND_TOCK_ROUNDS_N], {
289        std::array::from_fn(|i| ro::chal(15 - i).inner)
290    })
291}
292
293/// Value of `Dummy.Ipa.Step.challenges`
294pub fn dummy_ipa_step_challenges() -> [[u64; 2]; BACKEND_TICK_ROUNDS_N] {
295    cache_one!([[u64; 2]; BACKEND_TICK_ROUNDS_N], {
296        std::array::from_fn(|i| ro::chal(31 - i).inner)
297    })
298}
299
300/// Dummy.Ipa.Step.challenges_computed
301pub fn dummy_ipa_step_challenges_computed() -> [Fp; BACKEND_TICK_ROUNDS_N] {
302    cache_one!([Fp; BACKEND_TICK_ROUNDS_N], {
303        let challenges = dummy_ipa_step_challenges();
304        challenges.each_ref().map(ScalarChallenge::limbs_to_field)
305    })
306}
307
308impl Unfinalized {
309    pub fn dummy() -> Unfinalized {
310        // TODO: They might change between mina release/version ? Not sure
311        let one_chal: [u64; 2] = [1, 1];
312        let alpha_bytes: [u64; 2] = [746390447645740837, -5643124118675291918i64 as u64];
313        let beta_bytes: [u64; 2] = [8345091427968288705, 8258453988658898844];
314        let gamma_bytes: [u64; 2] = [8902445049614368905, -5479804816757020655i64 as u64];
315        let zeta_bytes: [u64; 2] = [621834770194220300, -4327941673388439925i64 as u64];
316
317        let zeta: Fq = ScalarChallenge::limbs_to_field(&zeta_bytes);
318        let alpha: Fq = ScalarChallenge::limbs_to_field(&alpha_bytes);
319        let beta: Fq = two_u64_to_field(&beta_bytes);
320        let gamma: Fq = two_u64_to_field(&gamma_bytes);
321
322        let chals = PlonkMinimal {
323            alpha,
324            beta,
325            gamma,
326            zeta,
327            joint_combiner: None,
328            alpha_bytes,
329            beta_bytes,
330            gamma_bytes,
331            zeta_bytes,
332            joint_combiner_bytes: None,
333            feature_flags: FeatureFlags::empty_bool(),
334        };
335
336        let evals = dummy_evals();
337
338        const DOMAIN_LOG2: u8 = 15;
339        const SRS_LENGTH_LOG2: u64 = 15;
340        let env = make_scalars_env(&chals, DOMAIN_LOG2, SRS_LENGTH_LOG2, 3);
341        let plonk = derive_plonk(&env, &evals, &chals);
342
343        Unfinalized {
344            deferred_values: DeferredValues {
345                plonk: Plonk {
346                    alpha: alpha_bytes,
347                    beta: beta_bytes,
348                    gamma: gamma_bytes,
349                    zeta: zeta_bytes,
350                    zeta_to_srs_length: plonk.zeta_to_srs_length,
351                    zeta_to_domain_size: plonk.zeta_to_domain_size,
352                    // vbmul: plonk.vbmul,
353                    // complete_add: plonk.complete_add,
354                    // endomul: plonk.endomul,
355                    // endomul_scalar: plonk.endomul_scalar,
356                    perm: plonk.perm,
357                    lookup: None,
358                    feature_flags: FeatureFlags::empty_bool(),
359                },
360                combined_inner_product: ShiftedValue::new(ro::tock(91)),
361                b: ShiftedValue::new(ro::tock(90)),
362                xi: one_chal,
363                bulletproof_challenges: dummy_ipa_wrap_challenges().to_vec(),
364            },
365            should_finalize: false,
366            // dummy digest
367            sponge_digest_before_evaluations: [1, 1, 1, 1],
368        }
369    }
370}
371
372impl<F: FieldWitness> ToFieldElements<F> for Unfinalized {
373    fn to_field_elements(&self, fields: &mut Vec<F>) {
374        let Self {
375            deferred_values:
376                DeferredValues {
377                    plonk:
378                        Plonk {
379                            alpha,
380                            beta,
381                            gamma,
382                            zeta,
383                            zeta_to_srs_length,
384                            zeta_to_domain_size,
385                            perm,
386                            lookup: _,
387                            feature_flags: _,
388                        },
389                    combined_inner_product,
390                    b,
391                    xi,
392                    bulletproof_challenges,
393                },
394            should_finalize,
395            sponge_digest_before_evaluations,
396        } = self;
397
398        // Fq
399        {
400            combined_inner_product.shifted.to_field_elements(fields);
401            b.shifted.to_field_elements(fields);
402            zeta_to_srs_length.shifted.to_field_elements(fields);
403            zeta_to_domain_size.shifted.to_field_elements(fields);
404            perm.shifted.to_field_elements(fields);
405        }
406
407        // Digest
408        {
409            // Never fail, `sponge_digest_before_evaluations` was previously a `Fp`
410            fields.push(four_u64_to_field(sponge_digest_before_evaluations).unwrap());
411        }
412
413        // Challenge
414        {
415            fields.push(two_u64_to_field(beta));
416            fields.push(two_u64_to_field(gamma));
417        }
418
419        // Scalar challenge
420        {
421            fields.push(two_u64_to_field(alpha));
422            fields.push(two_u64_to_field(zeta));
423            fields.push(two_u64_to_field(xi));
424        }
425
426        fields.extend(
427            bulletproof_challenges
428                .iter()
429                .map(|c| two_u64_to_field::<F>(c)),
430        );
431
432        // Bool
433        {
434            fields.push(F::from(*should_finalize));
435        }
436    }
437}
438
439impl Check<Fp> for Unfinalized {
440    fn check(&self, w: &mut Witness<Fp>) {
441        let Self {
442            deferred_values:
443                DeferredValues {
444                    plonk:
445                        Plonk {
446                            alpha: _,
447                            beta: _,
448                            gamma: _,
449                            zeta: _,
450                            zeta_to_srs_length,
451                            zeta_to_domain_size,
452                            perm,
453                            lookup: _,
454                            feature_flags: _,
455                        },
456                    combined_inner_product,
457                    b,
458                    xi: _,
459                    bulletproof_challenges: _,
460                },
461            should_finalize: _,
462            sponge_digest_before_evaluations: _,
463        } = self;
464
465        combined_inner_product.check(w);
466        b.check(w);
467        zeta_to_srs_length.check(w);
468        zeta_to_domain_size.check(w);
469        perm.check(w);
470    }
471}
472
473#[cfg(test)]
474mod tests {
475    use super::*;
476
477    #[test]
478    fn test_unfinalized() {
479        let dummy: Vec<Fp> = Unfinalized::dummy().to_field_elements_owned();
480        dbg!(&dummy);
481        dbg!(&dummy.len());
482    }
483}
mina_tree/proofs/unfinalized.rs

mina_tree/proofs/
unfinalized.rs
