miden_processor/fast/
fri_ops.rs

1// CONSTANTS
2// ================================================================================================
3
4use vm_core::{ExtensionOf, Felt, FieldElement, ONE, StarkField, ZERO};
5
6use super::FastProcessor;
7use crate::{ExecutionError, QuadFelt};
8
9const EIGHT: Felt = Felt::new(8);
10const TWO_INV: Felt = Felt::new(9223372034707292161);
11
12const DOMAIN_OFFSET: Felt = Felt::GENERATOR;
13
14// Pre-computed powers of 1/tau, where tau is the generator of multiplicative subgroup of size 4
15// (i.e., tau is the 4th root of unity). Correctness of these constants is checked in the test at
16// the end of this module.
17const TAU_INV: Felt = Felt::new(18446462594437873665); // tau^{-1}
18const TAU2_INV: Felt = Felt::new(18446744069414584320); // tau^{-2}
19const TAU3_INV: Felt = Felt::new(281474976710656); // tau^{-3}
20
21impl FastProcessor {
22    /// Analogous to `Process::op_fri_ext2fold4`.
23    pub fn op_fri_ext2fold4(&mut self) -> Result<(), ExecutionError> {
24        // --- read all relevant variables from the stack ---------------------
25        let query_values = self.get_query_values();
26        let folded_pos = self.stack_get(8);
27        // the segment identifier of the position in the source domain
28        let domain_segment = self.stack_get(9).as_int();
29        // the power of the domain generator which can be used to determine current domain value x
30        let poe = self.stack_get(10);
31        // the result of the previous layer folding
32        let prev_value = {
33            let pe1 = self.stack_get(11);
34            let pe0 = self.stack_get(12);
35            QuadFelt::new(pe0, pe1)
36        };
37        // the verifier challenge for the current layer
38        let alpha = {
39            let a1 = self.stack_get(13);
40            let a0 = self.stack_get(14);
41            QuadFelt::new(a0, a1)
42        };
43        // the memory address of the current layer
44        let layer_ptr = self.stack_get(15);
45
46        // --- make sure the previous folding was done correctly --------------
47        if domain_segment > 3 {
48            return Err(ExecutionError::InvalidFriDomainSegment(domain_segment));
49        }
50
51        let d_seg = domain_segment as usize;
52        if query_values[d_seg] != prev_value {
53            return Err(ExecutionError::InvalidFriLayerFolding(prev_value, query_values[d_seg]));
54        }
55
56        // --- fold query values ----------------------------------------------
57        let f_tau = get_tau_factor(d_seg);
58        let x = poe * f_tau * DOMAIN_OFFSET;
59        let x_inv = x.inv();
60
61        let (ev, es) = compute_evaluation_points(alpha, x_inv);
62        let (folded_value, tmp0, tmp1) = fold4(query_values, ev, es);
63
64        // --- write the relevant values into the next state of the stack -----
65        let tmp0 = tmp0.to_base_elements();
66        let tmp1 = tmp1.to_base_elements();
67        let ds = get_domain_segment_flags(d_seg);
68        let folded_value = folded_value.to_base_elements();
69
70        let poe2 = poe.square();
71        let poe4 = poe2.square();
72
73        self.decrement_stack_size();
74
75        self.stack_write(0, tmp0[1]);
76        self.stack_write(1, tmp0[0]);
77        self.stack_write(2, tmp1[1]);
78        self.stack_write(3, tmp1[0]);
79        self.stack_write_word(4, &ds);
80        self.stack_write(8, poe2);
81        self.stack_write(9, f_tau);
82        self.stack_write(10, layer_ptr + EIGHT);
83        self.stack_write(11, poe4);
84        self.stack_write(12, folded_pos);
85        self.stack_write(13, folded_value[1]);
86        self.stack_write(14, folded_value[0]);
87
88        Ok(())
89    }
90
91    // HELPER METHODS
92    // --------------------------------------------------------------------------------------------
93
94    /// Returns 4 query values in the source domain. These values are to be folded into a single
95    /// value in the folded domain.
96    fn get_query_values(&self) -> [QuadFelt; 4] {
97        let [v4, v5, v6, v7] = self.stack_get_word(0);
98        let [v0, v1, v2, v3] = self.stack_get_word(4);
99
100        [
101            QuadFelt::new(v0, v1),
102            QuadFelt::new(v2, v3),
103            QuadFelt::new(v4, v5),
104            QuadFelt::new(v6, v7),
105        ]
106    }
107}
108
109// HELPER FUNCTIONS
110// ================================================================================================
111
112/// Determines tau factor (needed to compute x value) for the specified domain segment.
113fn get_tau_factor(domain_segment: usize) -> Felt {
114    match domain_segment {
115        0 => ONE,
116        1 => TAU_INV,
117        2 => TAU2_INV,
118        3 => TAU3_INV,
119        _ => panic!("invalid domain segment {domain_segment}"),
120    }
121}
122
123/// Determines a set of binary flags needed to describe the specified domain segment.
124fn get_domain_segment_flags(domain_segment: usize) -> [Felt; 4] {
125    match domain_segment {
126        0 => [ONE, ZERO, ZERO, ZERO],
127        1 => [ZERO, ONE, ZERO, ZERO],
128        2 => [ZERO, ZERO, ONE, ZERO],
129        3 => [ZERO, ZERO, ZERO, ONE],
130        _ => panic!("invalid domain segment {domain_segment}"),
131    }
132}
133
134/// Computes 2 evaluation points needed for [fold4] function.
135fn compute_evaluation_points(alpha: QuadFelt, x_inv: Felt) -> (QuadFelt, QuadFelt) {
136    let ev = alpha.mul_base(x_inv);
137    let es = ev.square();
138    (ev, es)
139}
140
141/// Performs folding by a factor of 4. ev and es are values computed based on x and
142/// verifier challenge alpha as follows:
143/// - ev = alpha / x
144/// - es = (alpha / x)^2
145fn fold4(values: [QuadFelt; 4], ev: QuadFelt, es: QuadFelt) -> (QuadFelt, QuadFelt, QuadFelt) {
146    let tmp0 = fold2(values[0], values[2], ev);
147    let tmp1 = fold2(values[1], values[3], ev.mul_base(TAU_INV));
148    let folded_value = fold2(tmp0, tmp1, es);
149    (folded_value, tmp0, tmp1)
150}
151
152/// Performs folding by a factor of 2. ep is a value computed based on x and verifier challenge
153/// alpha.
154fn fold2(f_x: QuadFelt, f_neg_x: QuadFelt, ep: QuadFelt) -> QuadFelt {
155    (f_x + f_neg_x + ((f_x - f_neg_x) * ep)).mul_base(TWO_INV)
156}
miden_processor/fast/fri_ops.rs

miden_processor/fast/
fri_ops.rs
