sonobe_primitives/transcripts/poseidon/
mod.rs

1//! Poseidon-based transcript configurations and implementations.
2
3use ark_crypto_primitives::sponge::poseidon::{PoseidonConfig, find_poseidon_ark_and_mds};
4use ark_ff::{One, PrimeField};
5use num_bigint::BigUint;
6use num_integer::Integer;
7
8pub mod sponge;
9
10fn log2_order<F: PrimeField>() -> f64 {
11    let x = F::MODULUS.into();
12    let bits = x.bits(); // bit length
13    if bits <= 53 {
14        // Fits in f64 mantissa exactly
15        let val: u64 = x.try_into().unwrap();
16        return (val as f64).log2();
17    }
18    // Shift right so only top ~53 bits remain
19    let shift = bits - 53;
20    let top = x >> shift;
21    let top_u64: u64 = top.try_into().unwrap();
22    (top_u64 as f64).log2() + shift as f64
23}
24
25fn sat_inequiv_alpha<F: PrimeField>(t: usize, r_f: u64, r_p: u64, alpha: u64, m: usize) -> bool {
26    let log2_p = log2_order::<F>();
27    let n = log2_p.ceil() as usize;
28    let m_f = m as f64;
29    let n_f = n as f64;
30    let t_f = t as f64;
31    let r_p_f = r_p as f64;
32    let r_f_f = r_f as f64;
33    let alpha_f = alpha as f64;
34    let log2_alpha = 2.0f64.ln() / alpha_f.ln();
35
36    let r_f_1: f64 = if m_f <= (log2_p - (alpha_f - 1.0) / 2.0).floor() * (t_f + 1.0) {
37        6.0
38    } else {
39        10.0
40    };
41
42    let r_f_2 = 1.0 + log2_alpha * m_f.min(n_f) + (t_f.ln() / alpha_f.ln()).ceil() - r_p_f;
43
44    let r_f_3 = 1.0 + log2_alpha * (m_f / 3.0).min(log2_p / 2.0) - r_p_f;
45
46    let r_f_4 = t_f - 1.0 + (log2_alpha * m_f / (t_f + 1.0)).min(log2_alpha * log2_p / 2.0) - r_p_f;
47
48    let r_f_max = r_f_1
49        .ceil()
50        .max(r_f_2.ceil())
51        .max(r_f_3.ceil())
52        .max(r_f_4.ceil());
53
54    r_f_f >= r_f_max
55}
56
57fn get_sbox_cost(r_f: u64, r_p: u64, _n: usize, t: usize) -> usize {
58    t * r_f as usize + r_p as usize
59}
60
61fn find_fd_round_numbers<F: PrimeField>(
62    t: usize,
63    alpha: u64,
64    m: usize,
65    cost_function: fn(u64, u64, usize, usize) -> usize,
66    security_margin: bool,
67) -> (u64, u64) {
68    let n = log2_order::<F>().ceil() as usize;
69    let n_total = n * t;
70
71    let mut r_p: u64 = 0;
72    let mut r_f: u64 = 0;
73    let mut min_cost = usize::MAX;
74    let mut max_cost_rf: u64 = 0;
75
76    for r_p_t in 1u64..500 {
77        for r_f_t in (4u64..100).step_by(2) {
78            if !sat_inequiv_alpha::<F>(t, r_f_t, r_p_t, alpha, m) {
79                continue;
80            }
81
82            let (r_f_eff, r_p_eff) = if security_margin {
83                (r_f_t + 2, (r_p_t as f64 * 1.075).ceil() as u64)
84            } else {
85                (r_f_t, r_p_t)
86            };
87
88            let cost = cost_function(r_f_eff, r_p_eff, n_total, t);
89            if cost < min_cost || (cost == min_cost && r_f_eff < max_cost_rf) {
90                r_p = r_p_eff;
91                r_f = r_f_eff;
92                min_cost = cost;
93                max_cost_rf = r_f;
94            }
95        }
96    }
97
98    assert_ne!(min_cost, usize::MAX);
99
100    (r_f, r_p)
101}
102
103/// [`poseidon_paper_config`] produces a Poseidon configuration which agrees
104/// with the paper's reference implementation.
105///
106/// TODO(@winderica): alpha = -1 is not supported yet.
107pub fn poseidon_paper_config<F: PrimeField, const SECURITY_BITS: usize>(
108    alpha: u64,
109    rate: usize,
110) -> PoseidonConfig<F> {
111    assert_ne!(alpha, 1);
112    assert_eq!(
113        BigUint::from(alpha).gcd(&(-F::one()).into()),
114        BigUint::one()
115    );
116    let (full_rounds, partial_rounds) =
117        find_fd_round_numbers::<F>(rate + 1, alpha, SECURITY_BITS, get_sbox_cost, true);
118    let (ark, mds) = find_poseidon_ark_and_mds(
119        F::MODULUS_BIT_SIZE as u64,
120        rate,
121        full_rounds,
122        partial_rounds,
123        0,
124    );
125
126    PoseidonConfig::new(
127        full_rounds as usize,
128        partial_rounds as usize,
129        alpha,
130        mds,
131        ark,
132        rate,
133        1,
134    )
135}
136
137/// [`poseidon_circom_config`] produces a Poseidon configuration for BN254's
138/// scalar field that agrees with Circom's Poseidon(4).
139pub fn poseidon_circom_config() -> PoseidonConfig<ark_bn254::Fr> {
140    // 120 bit security target as in
141    // https://eprint.iacr.org/2019/458.pdf
142    // t = rate + 1
143
144    let full_rounds = 8;
145    let partial_rounds = 60;
146    let alpha = 5;
147    let rate = 4;
148
149    let (ark, mds) = find_poseidon_ark_and_mds(
150        ark_bn254::Fr::MODULUS_BIT_SIZE as u64,
151        rate,
152        full_rounds as u64,
153        partial_rounds as u64,
154        0,
155    );
156
157    PoseidonConfig::new(full_rounds, partial_rounds, alpha, mds, ark, rate, 1)
158}
sonobe_primitives/transcripts/poseidon/mod.rs

sonobe_primitives/transcripts/poseidon/
mod.rs
