winter_fri/
options.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use math::StarkField;
7
8// FRI OPTIONS
9// ================================================================================================
10
11/// FRI protocol config options for proof generation and verification.
12#[derive(Clone, PartialEq, Eq)]
13pub struct FriOptions {
14    folding_factor: usize,
15    remainder_max_degree: usize,
16    blowup_factor: usize,
17}
18
19impl FriOptions {
20    /// Returns a new [FriOptions] struct instantiated with the specified parameters.
21    ///
22    /// # Panics
23    /// Panics if:
24    /// - `blowup_factor` is not a power of two.
25    /// - `folding_factor` is not 2, 4, 8, or 16.
26    pub fn new(blowup_factor: usize, folding_factor: usize, remainder_max_degree: usize) -> Self {
27        // TODO: change panics to errors
28        assert!(
29            blowup_factor.is_power_of_two(),
30            "blowup factor must be a power of two, but was {blowup_factor}"
31        );
32        assert!(
33            folding_factor == 2
34                || folding_factor == 4
35                || folding_factor == 8
36                || folding_factor == 16,
37            "folding factor {folding_factor} is not supported"
38        );
39        FriOptions {
40            folding_factor,
41            remainder_max_degree,
42            blowup_factor,
43        }
44    }
45
46    /// Returns the offset by which the evaluation domain is shifted.
47    ///
48    /// The domain is shifted by multiplying every element in the domain by this offset.
49    ///
50    /// Currently, the offset is hard-coded to be the primitive element in the field specified by
51    /// type parameter `B`.
52    pub fn domain_offset<B: StarkField>(&self) -> B {
53        B::GENERATOR
54    }
55
56    /// Returns the factor by which the degree of a polynomial is reduced with each FRI layer.
57    ///
58    /// In combination with `remainder_max_degree_plus_1` this property defines how many FRI layers
59    /// are needed for an evaluation domain of a given size.
60    pub fn folding_factor(&self) -> usize {
61        self.folding_factor
62    }
63
64    /// Returns maximum allowed remainder polynomial degree.
65    ///
66    /// In combination with `folding_factor` this property defines how many FRI layers are needed
67    /// for an evaluation domain of a given size.
68    pub fn remainder_max_degree(&self) -> usize {
69        self.remainder_max_degree
70    }
71
72    /// Returns a blowup factor of the evaluation domain.
73    ///
74    /// Specifically, if the polynomial for which the FRI protocol is executed is of degree `d`
75    /// where `d` is one less than a power of two, then the evaluation domain size will be
76    /// equal to `(d + 1) * blowup_factor`.
77    pub fn blowup_factor(&self) -> usize {
78        self.blowup_factor
79    }
80
81    /// Computes and return the number of FRI layers required for a domain of the specified size.
82    ///
83    /// The number of layers for a given domain size is defined by the `folding_factor` and
84    /// `remainder_max_degree` and `blowup_factor` settings.
85    pub fn num_fri_layers(&self, mut domain_size: usize) -> usize {
86        let mut result = 0;
87        let max_remainder_size = (self.remainder_max_degree + 1) * self.blowup_factor;
88        while domain_size > max_remainder_size {
89            domain_size /= self.folding_factor;
90            result += 1;
91        }
92        result
93    }
94}
winter_fri/options.rs

winter_fri/
options.rs
