1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

use alloc::vec::Vec;

use serde::Serialize;

use crate::fri::reduction_strategies::FriReductionStrategy;

mod challenges;
pub mod oracle;
pub mod proof;
pub mod prover;
pub mod recursive_verifier;
pub mod reduction_strategies;
pub mod structure;
mod validate_shape;
pub mod verifier;
pub mod witness_util;

#[derive(Debug, Clone, Eq, PartialEq, Serialize)]
pub struct FriConfig {
    /// `rate = 2^{-rate_bits}`.
    pub rate_bits: usize,

    /// Height of Merkle tree caps.
    pub cap_height: usize,

    pub proof_of_work_bits: u32,

    pub reduction_strategy: FriReductionStrategy,

    /// Number of query rounds to perform.
    pub num_query_rounds: usize,
}

impl FriConfig {
    pub fn rate(&self) -> f64 {
        1.0 / ((1 << self.rate_bits) as f64)
    }

    pub fn fri_params(&self, degree_bits: usize, hiding: bool) -> FriParams {
        let reduction_arity_bits = self.reduction_strategy.reduction_arity_bits(
            degree_bits,
            self.rate_bits,
            self.cap_height,
            self.num_query_rounds,
        );
        FriParams {
            config: self.clone(),
            hiding,
            degree_bits,
            reduction_arity_bits,
        }
    }

    pub fn num_cap_elements(&self) -> usize {
        1 << self.cap_height
    }
}

/// FRI parameters, including generated parameters which are specific to an instance size, in
/// contrast to `FriConfig` which is user-specified and independent of instance size.
#[derive(Debug, Clone, Eq, PartialEq, Serialize)]
pub struct FriParams {
    /// User-specified FRI configuration.
    pub config: FriConfig,

    /// Whether to use a hiding variant of Merkle trees (where random salts are added to leaves).
    pub hiding: bool,

    /// The degree of the purported codeword, measured in bits.
    pub degree_bits: usize,

    /// The arity of each FRI reduction step, expressed as the log2 of the actual arity.
    /// For example, `[3, 2, 1]` would describe a FRI reduction tree with 8-to-1 reduction, then
    /// a 4-to-1 reduction, then a 2-to-1 reduction. After these reductions, the reduced polynomial
    /// is sent directly.
    pub reduction_arity_bits: Vec<usize>,
}

impl FriParams {
    pub fn total_arities(&self) -> usize {
        self.reduction_arity_bits.iter().sum()
    }

    pub(crate) fn max_arity_bits(&self) -> Option<usize> {
        self.reduction_arity_bits.iter().copied().max()
    }

    pub fn lde_bits(&self) -> usize {
        self.degree_bits + self.config.rate_bits
    }

    pub fn lde_size(&self) -> usize {
        1 << self.lde_bits()
    }

    pub fn final_poly_bits(&self) -> usize {
        self.degree_bits - self.total_arities()
    }

    pub fn final_poly_len(&self) -> usize {
        1 << self.final_poly_bits()
    }
}