mina_tree/proofs/numbers/
currency.rs

1use crate::{
2    proofs::field::CircuitVar,
3    scan_state::currency::{self, Amount, Balance, Fee, Magnitude, MinMax, Sgn, Signed},
4};
5use std::{cell::Cell, cmp::Ordering::Less};
6
7use crate::{
8    proofs::{
9        field::{field, Boolean, FieldWitness},
10        to_field_elements::ToFieldElements,
11        transaction::Check,
12        witness::Witness,
13    },
14    ToInputs,
15};
16
17use super::common::{range_check, ForZkappCheck};
18
19#[derive(Debug)]
20pub enum RangeCheckFlaggedKind {
21    Add,
22    Sub,
23    AddOrSub,
24}
25
26fn modulus_as_field_64_bits<F: FieldWitness>() -> F {
27    fn modulus_as_field_impl<F: FieldWitness>() -> F {
28        let mut one = F::one();
29        let two: F = 2u64.into();
30
31        for _ in 0..64 {
32            one *= two;
33        }
34
35        one
36    }
37    cache!(F, modulus_as_field_impl::<F>())
38}
39
40fn double_modulus_as_field_64_bits<F: FieldWitness>() -> F {
41    cache!(F, modulus_as_field_64_bits::<F>().double())
42}
43
44#[derive(Clone)]
45pub struct CheckedSigned<F, T>
46where
47    F: FieldWitness,
48    T: CheckedCurrency<F>,
49{
50    pub magnitude: T,
51    pub sgn: CircuitVar<Sgn>,
52    pub value: Cell<Option<F>>,
53}
54
55impl<F: std::fmt::Debug, T: std::fmt::Debug> std::fmt::Debug for CheckedSigned<F, T>
56where
57    F: FieldWitness,
58    T: CheckedCurrency<F>,
59{
60    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
61        f.debug_struct("CheckedSigned")
62            .field("magnitude", &self.magnitude)
63            .field("sgn", &self.sgn)
64            .field("value", &self.value)
65            .finish()
66    }
67}
68
69impl<F, T> CheckedSigned<F, T>
70where
71    F: FieldWitness + std::fmt::Debug,
72    T: CheckedCurrency<F> + std::fmt::Debug,
73{
74    pub fn create(magnitude: T, sgn: CircuitVar<Sgn>, value: Option<F>) -> Self {
75        Self {
76            magnitude,
77            sgn,
78            value: Cell::new(value),
79        }
80    }
81
82    pub fn of_unsigned(magnitude: T) -> Self {
83        let value = magnitude.to_field();
84        Self {
85            magnitude,
86            sgn: CircuitVar::Constant(Sgn::Pos),
87            value: Cell::new(Some(value)),
88        }
89    }
90
91    pub fn zero() -> Self {
92        Self {
93            magnitude: T::zero(),
94            sgn: CircuitVar::Constant(Sgn::Pos),
95            value: Cell::new(None),
96        }
97    }
98
99    // <https://github.com/MinaProtocol/mina/blob/ca9c8c86aa21d3c346d28ea0be7ad4cb0c22bf7f/src/lib/transaction_snark/transaction_snark.ml#L1891-L1892>
100    // <https://github.com/MinaProtocol/mina/blob/ca9c8c86aa21d3c346d28ea0be7ad4cb0c22bf7f/src/lib/currency/currency.ml#L579>
101    pub fn constant_zero() -> Self {
102        Self {
103            magnitude: T::zero(),
104            sgn: CircuitVar::Constant(Sgn::Pos),
105            value: Cell::new(Some(T::zero().to_field())),
106        }
107    }
108
109    pub fn negate(self) -> Self {
110        Self {
111            magnitude: self.magnitude,
112            sgn: self.sgn.map(|sgn| sgn.negate()),
113            value: Cell::new(self.value.get().map(|f| f.neg())),
114        }
115    }
116
117    pub fn is_neg(&self) -> Boolean {
118        match self.sgn.value() {
119            Sgn::Pos => Boolean::False,
120            Sgn::Neg => Boolean::True,
121        }
122    }
123
124    pub fn is_pos(&self) -> Boolean {
125        match self.sgn.value() {
126            Sgn::Pos => Boolean::True,
127            Sgn::Neg => Boolean::False,
128        }
129    }
130
131    pub fn value(&self, w: &mut Witness<F>) -> F {
132        match self.value.get() {
133            Some(x) => x,
134            None => {
135                let sgn: F = self.sgn.value().to_field();
136                let magnitude: F = self.magnitude.to_field();
137                let value = w.exists_no_check(magnitude * sgn);
138                self.value.replace(Some(value));
139                value
140            }
141        }
142    }
143
144    pub fn force_value(&self) -> F {
145        match self.value.get() {
146            Some(x) => x,
147            None => {
148                let sgn: F = self.sgn.value().to_field();
149                let magnitude: F = self.magnitude.to_field();
150                magnitude * sgn
151            }
152        }
153    }
154
155    pub fn set_value(&self) {
156        match self.value.get() {
157            Some(_) => {}
158            None => {
159                let sgn: F = self.sgn.value().to_field();
160                let magnitude: F = self.magnitude.to_field();
161                self.value.replace(Some(magnitude * sgn));
162            }
163        }
164    }
165
166    pub fn try_get_value(&self) -> Option<F> {
167        self.value.get()
168    }
169
170    fn unchecked(&self) -> currency::Signed<T::Inner> {
171        currency::Signed {
172            magnitude: self.magnitude.to_inner(),
173            sgn: *self.sgn.value(),
174        }
175    }
176
177    pub fn add_flagged(&self, y: &Self, w: &mut Witness<F>) -> (Self, Boolean)
178    where
179        T::Inner: Ord,
180    {
181        let x = self;
182
183        let xv = x.value(w);
184        let yv = y.value(w);
185
186        let sgn = w.exists({
187            let x = x.unchecked();
188            let y = y.unchecked();
189            match x.add(&y) {
190                Some(r) => r.sgn,
191                None => match (x.sgn, y.sgn) {
192                    (Sgn::Neg, Sgn::Neg) => Sgn::Neg,
193                    _ => Sgn::Pos,
194                },
195            }
196        });
197
198        let value = xv + yv;
199        let magnitude = field::mul(sgn.to_field(), value, w);
200
201        let (res_magnitude, overflow) =
202            T::range_check_flagged(RangeCheckFlaggedKind::AddOrSub, magnitude, w);
203
204        let res_value = field::mul(sgn.to_field(), magnitude, w);
205
206        let res = Self {
207            magnitude: res_magnitude,
208            sgn: CircuitVar::Var(sgn),
209            value: Cell::new(Some(res_value)),
210        };
211        (res, overflow)
212    }
213
214    pub fn add(&self, y: &Self, w: &mut Witness<F>) -> Self
215    where
216        T::Inner: Ord,
217    {
218        let x = self;
219
220        let xv: F = x.value(w);
221        let yv: F = y.value(w);
222
223        let sgn = w.exists({
224            let x = x.unchecked();
225            let y = y.unchecked();
226            x.add(&y).map(|r| r.sgn).unwrap_or(Sgn::Pos)
227        });
228
229        let res_value = w.exists(xv + yv);
230        let magnitude = w.exists(sgn.to_field::<F>() * res_value);
231
232        range_check::<F, CURRENCY_NBITS>(magnitude, w);
233
234        Self::create(
235            T::from_field(magnitude),
236            CircuitVar::Var(sgn),
237            Some(res_value),
238        )
239    }
240
241    pub fn equal(&self, other: &Self, w: &mut Witness<F>) -> Boolean {
242        let t1 = self.value(w);
243        let t2 = other.value(w);
244        field::equal(t1, t2, w)
245    }
246
247    pub fn const_equal(&self, other: &Self, w: &mut Witness<F>) -> Boolean {
248        let t1 = self.value(w);
249        let t2 = other.value(w);
250        field::equal(t1, t2, w)
251    }
252}
253
254const CURRENCY_NBITS: usize = 64;
255
256pub trait CheckedCurrency<F: FieldWitness>:
257    Sized + ToFieldElements<F> + Check<F> + std::fmt::Debug
258{
259    type Inner: MinMax + Magnitude + std::fmt::Debug;
260
261    fn to_field(&self) -> F;
262    fn from_field(field: F) -> Self;
263
264    fn zero() -> Self {
265        Self::from_field(F::zero())
266    }
267
268    fn to_inner(&self) -> Self::Inner {
269        Self::Inner::of_field(self.to_field())
270    }
271
272    fn from_inner(inner: Self::Inner) -> Self {
273        Self::from_field(inner.to_field())
274    }
275
276    fn min() -> Self {
277        Self::from_inner(Self::Inner::min())
278    }
279    fn max() -> Self {
280        Self::from_inner(Self::Inner::max())
281    }
282
283    fn modulus_as_field() -> F {
284        modulus_as_field_64_bits::<F>()
285    }
286
287    fn double_modulus_as_field() -> F {
288        double_modulus_as_field_64_bits::<F>()
289    }
290
291    fn equal(&self, other: &Self, w: &mut Witness<F>) -> Boolean {
292        field::equal(self.to_field(), other.to_field(), w)
293    }
294
295    fn sub_flagged(&self, y: &Self, w: &mut Witness<F>) -> (Self, Boolean) {
296        let (x, y) = (self.to_field(), y.to_field());
297        let z = w.exists(x - y);
298        Self::range_check_flagged(RangeCheckFlaggedKind::Sub, z, w)
299    }
300
301    fn sub_or_zero(&self, y: &Self, w: &mut Witness<F>) -> Self {
302        let (res, underflow) = self.sub_flagged(y, w);
303        w.exists_no_check(match underflow {
304            Boolean::True => Self::zero(),
305            Boolean::False => res,
306        })
307    }
308
309    fn range_check_flagged(
310        kind: RangeCheckFlaggedKind,
311        t: F,
312        w: &mut Witness<F>,
313    ) -> (Self, Boolean) {
314        use RangeCheckFlaggedKind::{Add, AddOrSub, Sub};
315
316        let adjustment_factor = w.exists(match &kind {
317            Add => {
318                if let Less = t.cmp(&Self::modulus_as_field()) {
319                    F::zero()
320                } else {
321                    F::one().neg()
322                }
323            }
324            Sub => {
325                if let Less = t.cmp(&Self::modulus_as_field()) {
326                    F::zero()
327                } else {
328                    F::one()
329                }
330            }
331            AddOrSub => {
332                if let Less = t.cmp(&Self::modulus_as_field()) {
333                    F::zero()
334                } else if let Less = t.cmp(&Self::double_modulus_as_field()) {
335                    F::one().neg()
336                } else {
337                    F::one()
338                }
339            }
340        });
341
342        let out_of_range = match kind {
343            Add => Boolean::of_field(adjustment_factor.neg()),
344            Sub => Boolean::of_field(adjustment_factor),
345            AddOrSub => Boolean::of_field(field::mul(adjustment_factor, adjustment_factor, w)),
346        };
347        let t_ajusted: F = t + (adjustment_factor * Self::modulus_as_field());
348        w.exists(t_ajusted);
349        range_check::<F, CURRENCY_NBITS>(t_ajusted, w);
350        (Self::from_field(t_ajusted), out_of_range)
351    }
352
353    /// <
354    /// less than
355    fn lt(&self, y: &Self, w: &mut Witness<F>) -> Boolean {
356        let diff: F = w.exists(self.to_field() - y.to_field());
357        let (_res, lt) = Self::range_check_flagged(RangeCheckFlaggedKind::Sub, diff, w);
358        lt
359    }
360
361    /// <=
362    /// less than or equal
363    fn lte(&self, y: &Self, w: &mut Witness<F>) -> Boolean {
364        let y_lt_x = y.lt(self, w);
365        y_lt_x.neg()
366    }
367
368    /// >=
369    /// > greater than or equal
370    fn gte(&self, y: &Self, w: &mut Witness<F>) -> Boolean {
371        y.lte(self, w)
372    }
373
374    /// >
375    /// greater than
376    fn gt(&self, y: &Self, w: &mut Witness<F>) -> Boolean {
377        y.lt(self, w)
378    }
379
380    fn add_signed(&self, d: CheckedSigned<F, Self>, w: &mut Witness<F>) -> Self {
381        let t = self.to_field();
382        let d = d.value(w);
383        let res = w.exists(t + d);
384        range_check::<F, CURRENCY_NBITS>(res, w);
385        Self::from_field(res)
386    }
387
388    fn add_signed_flagged(&self, d: CheckedSigned<F, Self>, w: &mut Witness<F>) -> (Self, Boolean) {
389        let t = self.to_field();
390        let d = d.value(w);
391        let res = w.exists(t + d);
392        let (res, overflow) = Self::range_check_flagged(RangeCheckFlaggedKind::AddOrSub, res, w);
393        (res, overflow)
394    }
395
396    /// Returns (F, is_overflow)
397    fn const_add_flagged(&self, y: &Self, w: &mut Witness<F>) -> (Self, Boolean) {
398        let x = self;
399        let z: F = x.to_field() + y.to_field();
400        Self::range_check_flagged(RangeCheckFlaggedKind::Add, z, w)
401    }
402
403    /// Returns (F, is_overflow)
404    fn add_flagged(&self, y: &Self, w: &mut Witness<F>) -> (Self, Boolean) {
405        let x = self;
406        let z: F = w.exists(x.to_field() + y.to_field());
407        Self::range_check_flagged(RangeCheckFlaggedKind::Add, z, w)
408    }
409
410    fn sub(&self, y: &Self, w: &mut Witness<F>) -> Self {
411        let x = self.to_field();
412        let y = y.to_field();
413
414        let res = w.exists(x - y);
415        range_check::<F, { CURRENCY_NBITS }>(res, w);
416
417        Self::from_field(res)
418    }
419}
420
421#[derive(Copy, Clone, Debug)]
422pub struct CheckedAmount<F: FieldWitness>(F);
423#[derive(Copy, Clone, Debug)]
424pub struct CheckedFee<F: FieldWitness>(F);
425#[derive(Copy, Clone, Debug)]
426pub struct CheckedBalance<F: FieldWitness>(F);
427
428impl<F: FieldWitness> CheckedBalance<F> {
429    pub fn add_signed_amount(
430        &self,
431        d: CheckedSigned<F, CheckedAmount<F>>,
432        w: &mut Witness<F>,
433    ) -> Self {
434        let d = CheckedSigned::<F, Self>::create(Self(d.magnitude.0), d.sgn, d.value.get());
435        self.add_signed(d, w)
436    }
437
438    pub fn add_amount_flagged(&self, y: &CheckedAmount<F>, w: &mut Witness<F>) -> (Self, Boolean) {
439        let y = Self(y.0);
440        self.add_flagged(&y, w)
441    }
442
443    pub fn sub_amount_or_zero(&self, y: &CheckedAmount<F>, w: &mut Witness<F>) -> Self {
444        let y = Self(y.0);
445        self.sub_or_zero(&y, w)
446    }
447
448    pub fn sub_amount_flagged(&self, y: &CheckedAmount<F>, w: &mut Witness<F>) -> (Self, Boolean) {
449        let y = Self(y.0);
450        self.sub_flagged(&y, w)
451    }
452
453    pub fn add_signed_amount_flagged(
454        &self,
455        amount: CheckedSigned<F, CheckedAmount<F>>,
456        w: &mut Witness<F>,
457    ) -> (Self, Boolean) {
458        let amount = CheckedSigned::<F, Self>::create(
459            Self(amount.magnitude.0),
460            amount.sgn,
461            amount.value.get(),
462        );
463        self.add_signed_flagged(amount, w)
464    }
465}
466
467impl<F: FieldWitness> CheckedAmount<F> {
468    pub fn of_fee(fee: &CheckedFee<F>) -> Self {
469        Self(fee.0)
470    }
471}
472
473impl<F: FieldWitness> CheckedSigned<F, CheckedAmount<F>> {
474    pub fn to_fee(&self) -> CheckedSigned<F, CheckedFee<F>> {
475        CheckedSigned {
476            magnitude: CheckedFee(self.magnitude.0),
477            sgn: self.sgn,
478            value: self.value.clone(),
479        }
480    }
481}
482
483macro_rules! impl_currency {
484    ($({$name:tt, $unchecked:tt}),*) => ($(
485        impl<F: FieldWitness> CheckedCurrency<F> for $name::<F> {
486            type Inner = $unchecked;
487            fn to_field(&self) -> F {
488                self.0
489            }
490            fn from_field(field: F) -> Self {
491                Self(field)
492            }
493        }
494
495        impl<F: FieldWitness> ToFieldElements<F> for $name::<F> {
496            fn to_field_elements(&self, fields: &mut Vec<F>) {
497                self.0.to_field_elements(fields)
498            }
499        }
500
501        impl<F: FieldWitness> Check<F> for $name::<F> {
502            fn check(&self, w: &mut Witness<F>) {
503                range_check::<F, { CURRENCY_NBITS }>(self.0, w);
504            }
505        }
506
507        impl<F: FieldWitness> ToInputs for $name<F> {
508            fn to_inputs(&self, inputs: &mut poseidon::hash::Inputs) {
509                self.to_inner().to_inputs(inputs)
510            }
511        }
512
513        impl $unchecked {
514            pub fn to_checked<F: FieldWitness>(&self) -> $name<F> {
515                $name::from_inner(*self)
516            }
517        }
518
519        impl Signed<$unchecked> {
520            pub fn to_checked<F: FieldWitness>(&self) -> CheckedSigned<F, $name<F>> {
521                CheckedSigned {
522                    magnitude: self.magnitude.to_checked(),
523                    sgn: CircuitVar::Var(self.sgn),
524                    value: Cell::new(None),
525                }
526            }
527        }
528
529        impl<F: FieldWitness> ForZkappCheck<F> for $unchecked {
530            type CheckedType = $name<F>;
531            fn checked_from_field(field: F) -> Self::CheckedType {
532                Self::CheckedType::from_field(field)
533            }
534            fn lte(this: &Self::CheckedType, other: &Self::CheckedType, w: &mut Witness<F>) -> Boolean {
535                Self::CheckedType::lte(this, other, w)
536            }
537        }
538    )*)
539}
540
541impl_currency!(
542    {CheckedAmount, Amount},
543    {CheckedFee, Fee},
544    {CheckedBalance, Balance}
545);
mina_tree/proofs/numbers/currency.rs

mina_tree/proofs/numbers/
currency.rs
