p3_security/
deep.rs

1//! DEEP-ALI out-of-domain sampling error.
2//!
3//! ε_DEEP = L⁺ · factor / |F|, with k = trace domain size and
4//!
5//! factor = max(max_deg · (k + max_combo − 1) + (k − 1), (c + 1) · k + max_combo − 1).
6//!
7//! The first term is ethSTARK's `X^i · h_i(X^d)` quotient split, matching
8//! `soundcalc/circuits/deep_ali.py`. The second is Plonky3's own quotient split into
9//! `c` committed power-of-two chunks, which the first term only
10//! dominates when `c ≤ max_deg`. `soundcalc` divides by `|F| − k − D`; the difference is
11//! negligible.
12//!
13//! The caller supplies the exact chunk count. For degree `d` and `z = is_zk`, this is
14//! `c = 2^z · next_power_of_two(max(d + z, 2) − 1)`, including both ZK adjustments.
15//!
16//! The list size `L⁺` enters linearly here, following `soundcalc`.
17//! [2024/1553] Theorem 2 (`eps_2`) instead uses `L² ≈ (m/ρ)²`, which is
18//! a few bits more conservative in the list-decoding regime; ALI/DEEP
19//! don't bind at the LDR optimum in practice (see `fri::best_ldr_m`), so
20//! the difference does not currently affect reported bounds.
21
22use libm::log2;
23
24use crate::error::ErrorBits;
25use crate::shape::{InstanceShape, StarkAirParams};
26
27/// `-log2(ε_DEEP)` in bits. Returns 0 bits if inputs are degenerate or the trace size
28/// cannot be represented by `u64`.
29pub fn deep_ali_error(air: &StarkAirParams, shape: &InstanceShape, list_size: f64) -> ErrorBits {
30    if shape.modulus_bits == 0
31        || !air.num_quotient_chunks.is_power_of_two()
32        || shape.log_trace_length >= u64::BITS as usize
33        || !list_size.is_finite()
34        || list_size <= 0.0
35    {
36        return ErrorBits::from_log2(0.0);
37    }
38    let k = (1u64 << shape.log_trace_length) as f64;
39    let max_deg = air.max_constraint_degree.max(1) as f64;
40    let combo = air.max_combo as f64;
41    let ethstark = max_deg * (k + combo - 1.0) + (k - 1.0);
42    let chunks = air.num_quotient_chunks as f64;
43    let chunked = (chunks + 1.0) * k + combo - 1.0;
44    let factor = ethstark.max(chunked).max(1.0);
45    let bits = shape.modulus_bits as f64 - log2(list_size) - log2(factor);
46    ErrorBits::from_log2(bits.max(0.0))
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn trace_length_shift_boundary_is_conservative() {
55        let air = StarkAirParams {
56            num_constraints: 1,
57            max_constraint_degree: 2,
58            num_quotient_chunks: 1,
59            max_combo: 2,
60        };
61        let mut shape = InstanceShape {
62            log_trace_length: 63,
63            modulus_bits: 128,
64            collision_resistance: 128,
65            num_batched_functions: 1,
66        };
67        // 2^63 fits in u64; the DEEP factor is 3 * 2^63 + 1.
68        let expected = 128.0 - 63.0 - log2(3.0);
69        assert!((deep_ali_error(&air, &shape, 1.0).bits() - expected).abs() < 1e-12);
70
71        // These exponents must not panic or wrap back to a small trace.
72        for log_trace_length in [64, 65, usize::MAX] {
73            shape.log_trace_length = log_trace_length;
74            assert_eq!(deep_ali_error(&air, &shape, 1.0).bits(), 0.0);
75        }
76    }
77}
p3_security/deep.rs

p3_security/
deep.rs
