darkfi_sdk/crypto/
mimc_vdf.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2025 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19//! <https://vitalik.eth.limo/general/2018/07/21/starks_part_3.html>
20
21use num_bigint::BigUint;
22use num_traits::Num;
23
24/// Modulus of prime field 2^256 - 2^32 * 351 + 1
25const MODULUS: &str =
26    "115792089237316195423570985008687907853269984665640564039457584006405596119041";
27
28/// An exponent to perform inverse of x^3 on prime field based on Fermat's Little Theorem
29const L_FERMAT_EXPONENT: &str =
30    "77194726158210796949047323339125271902179989777093709359638389337603730746027";
31
32/// Calculates set of round constants to perform MiMC-calculation on.
33fn calculate_round_constants() -> [BigUint; 64] {
34    let mut round_constants: Vec<BigUint> = vec![];
35    #[allow(clippy::needless_range_loop)]
36    for i in 0u64..64 {
37        round_constants.push(BigUint::from(i).pow(7) ^ BigUint::from(42u64));
38    }
39
40    round_constants.try_into().unwrap()
41}
42
43/// Executes `num_steps` of MiMC-calculation in forward direction for the given `input`
44fn forward_mimc(num_steps: u64, input: &BigUint) -> BigUint {
45    let modulus = BigUint::from_str_radix(MODULUS, 10).unwrap();
46    let round_constants = calculate_round_constants();
47
48    let mut result = input.clone();
49    let three = BigUint::from(3_u64);
50    for i in 1..num_steps {
51        result = (result.modpow(&three, &modulus) +
52            &round_constants[i as usize % round_constants.len()])
53            .modpow(&BigUint::from(1_u64), &modulus);
54    }
55
56    result
57}
58
59/// Executes `num_steps` of MiMC-calculation in backward direction for the given `input`.
60///
61/// The properties of MiMC-scheme guarantees that calculation in backward direction is
62/// always slower than in forward for correctly chosen parameters.
63fn backward_mimc(num_steps: u64, input: &BigUint) -> BigUint {
64    let modulus = BigUint::from_str_radix(MODULUS, 10).unwrap();
65    let l_fermat_exp = BigUint::from_str_radix(L_FERMAT_EXPONENT, 10).unwrap();
66    let round_constants = calculate_round_constants();
67
68    let mut result = input.clone();
69    for i in (1..num_steps).rev() {
70        let round_constant = &round_constants[i as usize % round_constants.len()];
71        result = (&result - round_constant).modpow(&l_fermat_exp, &modulus);
72    }
73
74    result
75}
76
77/// Performs an Eval() step of the MiMC-based VDF
78pub fn eval(seed: &BigUint, num_steps: u64) -> BigUint {
79    backward_mimc(num_steps, seed)
80}
81
82/// Performs a Verify() step for the MiMC-based VDF result
83pub fn verify(seed: &BigUint, num_steps: u64, witness: &BigUint) -> bool {
84    forward_mimc(num_steps, witness) == *seed
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90
91    #[test]
92    fn mimc_vdf_eval_and_verify() {
93        let steps = 1000;
94        let challenge = blake3::hash(b"69420").to_hex();
95        let challenge = BigUint::from_str_radix(&challenge, 16).unwrap();
96
97        let witness = eval(&challenge, steps);
98        assert!(verify(&challenge, steps, &witness));
99        assert!(!verify(&(&challenge - 1_u64), steps, &witness));
100        assert!(!verify(&challenge, steps - 1, &witness));
101        assert!(!verify(&challenge, steps, &(&witness - 1_u64)));
102    }
103}
darkfi_sdk/crypto/mimc_vdf.rs

darkfi_sdk/crypto/
mimc_vdf.rs
