mina_tree/proofs/
unfinalized.rs

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

mina_tree/proofs/
unfinalized.rs
