vrf/
threshold.rs

1use ark_ff::{BigInteger, BigInteger256, One, Zero};
2use itertools::unfold;
3use num::{rational::Ratio, BigInt, FromPrimitive, Signed};
4
5use crate::{BigInt2048, BigInt256, BigInt4096, BigRational2048, BigRational4096};
6
7#[allow(dead_code)]
8#[derive(Clone, Debug)]
9pub struct Threshold {
10    pub total_currency: BigInt256,
11    pub delegated_stake: BigInt256,
12    pub threshold_rational: BigRational2048,
13}
14
15impl Threshold {
16    const SIZE_IN_BITS: usize = 255;
17
18    /// Creates a new Threshold struct
19    pub fn new(delegated_stake: BigInt256, total_currency: BigInt256) -> Self {
20        // 1. set up parameters to calculate threshold
21        // Note: IMO all these parameters can be represented as constants. They do not change. The calculation is most likely in the
22        //       code to adjust them in the future. We could create an utility that generates these params using f and log terms
23        let f = BigRational2048::new(BigInt::from_u8(3).unwrap(), BigInt::from_u8(4).unwrap());
24
25        let base = BigRational2048::one() - f;
26
27        let abs_log_base = Self::log(100, base).abs();
28
29        let (per_term_precission, terms_needed, _) = Self::bit_params(&abs_log_base);
30
31        let terms_needed: i32 = terms_needed.try_into().unwrap();
32        let mut linear_term_integer_part = BigInt::zero();
33
34        let abs_log_base: BigRational4096 = abs_log_base.to_nlimbs::<64>();
35
36        let coefficients = (1..terms_needed).map(|x| {
37            let c = abs_log_base.pow(x) / Self::factorial(x.into());
38            let c_frac = if x == 1 {
39                let c_whole = c.to_integer();
40                let c_frac = c - bigint_to_bigrational(&c_whole);
41                linear_term_integer_part = c_whole;
42                c_frac
43            } else {
44                c
45            };
46            if x % 2 == 0 {
47                -bigrational_as_fixed_point(c_frac, per_term_precission)
48            } else {
49                bigrational_as_fixed_point(c_frac, per_term_precission)
50            }
51        });
52
53        let two_tpo_per_term_precission = BigInt2048::one() << per_term_precission;
54
55        // one_minus_exp to calculate the threshold rational
56        let numer = BigRational2048::new(
57            &two_tpo_per_term_precission * &delegated_stake.to_nlimbs(),
58            total_currency.to_nlimbs(),
59        )
60        .floor()
61        .to_integer();
62        let input =
63            BigRational4096::new(numer.to_nlimbs(), two_tpo_per_term_precission.to_nlimbs());
64
65        let denom = BigInt::one() << per_term_precission;
66
67        let (res, _) = coefficients.into_iter().fold(
68            (BigRational4096::zero(), BigRational4096::one()),
69            |(acc, x_i), coef| {
70                let x_i = &input * &x_i;
71                let c = Ratio::new(coef, denom.clone());
72                (acc + (&x_i * &c), x_i)
73            },
74        );
75
76        let threshold_rational = res + input * bigint_to_bigrational(&linear_term_integer_part);
77
78        Self {
79            delegated_stake,
80            total_currency,
81            threshold_rational: threshold_rational.to_nlimbs::<32>(),
82        }
83    }
84
85    /// Compares the vrf output to the threshold. If vrf output <= threshold the vrf prover has the rights to
86    /// produce a block at the desired slot
87    pub fn threshold_met(&self, vrf_out: BigInteger256) -> bool {
88        let vrf_out = get_fractional(vrf_out);
89        vrf_out <= self.threshold_rational
90    }
91
92    fn terms_needed(log_base: &BigRational2048, bits_of_precission: u32) -> i32 {
93        let two = BigInt4096::one() + BigInt::one();
94        let lower_bound = bigint_to_bigrational(&two.pow(bits_of_precission));
95
96        let mut n = 0;
97        let log_base: BigRational4096 = log_base.to_nlimbs();
98
99        loop {
100            let d: BigRational4096 = log_base.pow(n + 1);
101            let a: BigRational4096 = BigRational4096::new(Self::factorial(n.into()), BigInt::one());
102
103            if a / d > lower_bound {
104                return n;
105            }
106            n += 1;
107        }
108    }
109
110    fn factorial<const N: usize>(n: BigInt<N>) -> BigInt<N> {
111        if n == BigInt::<N>::zero() {
112            return BigInt::<N>::one();
113        }
114        let mut res = n.clone();
115        let mut i = n - BigInt::<N>::one();
116        while i != BigInt::<N>::zero() {
117            res *= i.clone();
118            i -= BigInt::<N>::one();
119        }
120
121        res
122    }
123
124    fn log(terms: usize, x: BigRational2048) -> BigRational2048 {
125        let two = BigInt2048::one() + BigInt2048::one();
126        let a = x - BigRational2048::one();
127        let i0 = BigRational2048::one();
128        let seq = unfold((a.clone(), i0), |(ai, i)| {
129            let t = ai.to_owned() / i.to_owned();
130            let res = if &i.to_integer() % &two == BigInt2048::zero() {
131                -t
132            } else {
133                t
134            };
135
136            *ai = ai.to_owned() * &a;
137            *i = i.to_owned() + &BigRational2048::one();
138            Some(res)
139        });
140
141        seq.take(terms).sum()
142    }
143
144    fn ciel_log2(n: &BigInt2048) -> BigInt2048 {
145        let two = BigInt2048::one() + BigInt2048::one();
146
147        let mut i = 0;
148
149        loop {
150            if &two.pow(i) >= n {
151                return i.into();
152            }
153            i += 1;
154        }
155    }
156
157    fn bit_params(log_base: &BigRational2048) -> (usize, BigInt2048, BigInt2048) {
158        let mut k = 0;
159
160        let greatest = |k| -> Option<(usize, BigInt2048, BigInt2048)> {
161            let mut n: BigInt2048 = Self::terms_needed(log_base, k).into();
162            n += BigInt2048::one();
163
164            let per_term_precision = Self::ciel_log2(&n) + k;
165            // println!("[k = {k}] terms_needed = {n} per_term_precision = {}", per_term_precision);
166
167            if (&n * &per_term_precision) + &per_term_precision < Self::SIZE_IN_BITS.into() {
168                Some((per_term_precision.try_into().unwrap(), n, k.into()))
169            } else {
170                None
171            }
172        };
173
174        let mut best = (0, BigInt2048::zero(), BigInt2048::zero());
175        while let Some(better) = greatest(k) {
176            best = better;
177            k += 1;
178        }
179
180        best
181    }
182}
183
184/// Converts an integer to a rational
185pub fn get_fractional(vrf_out: BigInteger256) -> Ratio<BigInt2048> {
186    // ocaml:   Bignum_bigint.(shift_left one length_in_bits))
187    //          where: length_in_bits = Int.min 256 (Field.size_in_bits - 2)
188    //                 Field.size_in_bits = 255
189    let two_tpo_256 = BigInt2048::one() << 253u32;
190
191    let vrf_out = BigInt2048::from_bytes_be(num::bigint::Sign::Plus, &vrf_out.to_bytes_be());
192
193    Ratio::new(vrf_out, two_tpo_256)
194}
195
196// TODO: is there a fn like this?
197pub fn bigint_to_bigrational<const N: usize>(x: &BigInt<N>) -> Ratio<BigInt<N>> {
198    Ratio::new(x.clone(), BigInt::one())
199}
200
201pub fn bigrational_as_fixed_point<const N: usize>(
202    c: Ratio<BigInt<N>>,
203    per_term_precission: usize,
204) -> BigInt<N> {
205    let numer = c.numer();
206    let denom = c.denom();
207
208    (numer << per_term_precission) / denom
209}
210
211// pub fn can_produce_block(
212//     vrf_out: BigInteger256,
213//     delegated_stake: BigInt,
214//     total_currency: BigInt,
215// ) -> bool {
216//     Threshold::new(delegated_stake, total_currency).threshold_met(vrf_out)
217// }
218
219#[cfg(test)]
220mod test {
221    use std::str::FromStr;
222
223    use ark_ff::{One, Zero};
224    use num::{BigInt, BigRational, ToPrimitive};
225
226    use super::*;
227
228    // TODO: move to regular fns, rework step
229    fn first_non_zero(stake: BigInt, total_currency: BigInt, step: BigInt) -> BigInt {
230        let ten = BigInt::from_str("10").unwrap();
231        let mut stake = stake;
232        if step == BigInt::zero() {
233            stake + BigInt::one()
234        } else {
235            loop {
236                let thrs = Threshold::new(stake.clone(), total_currency.clone());
237
238                if thrs.threshold_rational != BigRational::zero() {
239                    println!("stake: {stake} nanoMINA");
240                    return first_non_zero(stake - step.clone(), total_currency, step / ten);
241                }
242                stake += step.clone();
243            }
244        }
245    }
246
247    #[test]
248    #[ignore]
249    fn test_threshold_nonzero() {
250        // let total_currency = BigInt::from_str("1157953132840039233").unwrap();
251        // let initial_stake = BigInt::zero();
252        // let initial_step = BigInt::from_str("10000000000000000000").unwrap();
253
254        let total_currency = BigInt::from_str("1025422352000001000").unwrap();
255        let initial_stake = BigInt::zero();
256        let initial_step = BigInt::from_str("10000000000000000000").unwrap();
257
258        let first_non_zero_nanomina =
259            first_non_zero(initial_stake, total_currency.clone(), initial_step);
260
261        let last_zero = first_non_zero_nanomina.clone() - BigInt::one();
262
263        let thrs_zero = Threshold::new(last_zero, total_currency.clone());
264        assert_eq!(thrs_zero.threshold_rational, BigRational::zero());
265
266        let thrs_first = Threshold::new(first_non_zero_nanomina.clone(), total_currency);
267        assert!(thrs_first.threshold_rational > BigRational::zero());
268
269        let first_non_zero_mina = first_non_zero_nanomina.to_f64().unwrap() / 1_000_000_000.0;
270
271        println!("First non zero stake: {first_non_zero_mina} MINA");
272        println!(
273            "First non zero threshold: {}",
274            thrs_first.threshold_rational.to_f64().unwrap()
275        );
276    }
277
278    #[test]
279    #[ignore]
280    fn test_threshold_increase() {
281        // let total_currency = BigInt::from_str("1157953132840039233").unwrap();
282        // let mut stake_nanomina = BigInt::from_str("1104310162392").unwrap();
283        // let mut step = BigInt::from_str("1000000000000").unwrap();
284
285        let total_currency = BigInt::from_str("1025422352000001000").unwrap();
286        let mut stake_nanomina = BigInt::from_str("2000000000000000").unwrap();
287        let mut step = BigInt::from_str("1000000000000").unwrap();
288
289        loop {
290            if stake_nanomina > total_currency {
291                break;
292            }
293            let thrs = Threshold::new(stake_nanomina.clone(), total_currency.clone());
294            let stake_mina = stake_nanomina.to_f64().unwrap() / 1_000_000_000.0;
295            println!(
296                "stake: {stake_mina} MINA - threshold: {}",
297                thrs.threshold_rational.to_f64().unwrap()
298            );
299
300            stake_nanomina += step.clone();
301            step *= 2;
302        }
303    }
304}
vrf/threshold.rs

vrf/
threshold.rs
