sp1_hypercube/lookup/
interaction.rs

1use core::fmt::{Debug, Display};
2use std::ops::Mul;
3
4use serde::{Deserialize, Serialize};
5use slop_air::{PairCol, VirtualPairCol};
6use slop_algebra::{AbstractField, Field};
7use slop_multilinear::MleEval;
8
9use crate::air::InteractionScope;
10
11/// An interaction for a lookup or a permutation argument.
12#[derive(Clone)]
13pub struct Interaction<F: Field> {
14    /// The values of the interaction.
15    pub values: Vec<VirtualPairCol<F>>,
16    /// The multiplicity of the interaction.
17    pub multiplicity: VirtualPairCol<F>,
18    /// The kind of interaction.
19    pub kind: InteractionKind,
20    /// The scope of the interaction.
21    pub scope: InteractionScope,
22}
23
24/// The type of interaction for a lookup argument.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
26pub enum InteractionKind {
27    /// Interaction with the memory table, such as read and write.
28    Memory = 1,
29
30    /// Interaction with the program table, loading an instruction at a given pc address.
31    Program = 2,
32
33    /// Interaction with the byte lookup table for byte operations.
34    Byte = 5,
35
36    /// Interaction with the current CPU state.
37    State = 7,
38
39    /// Interaction with a syscall.
40    Syscall = 8,
41
42    /// Interaction with the global table.
43    Global = 9,
44
45    /// Interaction with the `ShaExtend` chip.
46    ShaExtend = 10,
47
48    /// Interaction with the `ShaCompress` chip.
49    ShaCompress = 11,
50
51    /// Interaction with the `Keccak` chip.
52    Keccak = 12,
53
54    /// Interaction to accumulate the global interaction digests.
55    GlobalAccumulation = 13,
56
57    /// Interaction with the `MemoryGlobalInit` chip.
58    MemoryGlobalInitControl = 14,
59
60    /// Interaction with the `MemoryGlobalFinalize` chip.
61    MemoryGlobalFinalizeControl = 15,
62
63    /// Interaction with the instruction fetch table.
64    InstructionFetch = 16,
65
66    /// Interaction with the instruction decode table.
67    InstructionDecode = 17,
68
69    /// Interaction with the page prot chip.
70    PageProt = 18,
71
72    /// Interaction with the page prot chip.
73    PageProtAccess = 19,
74
75    /// Interaction with the `PageProtGlobalInit` chip.
76    PageProtGlobalInitControl = 20,
77
78    /// Interaction with the `PageProtGlobalFinalize` chip.
79    PageProtGlobalFinalizeControl = 21,
80}
81
82impl InteractionKind {
83    /// Returns all kinds of interactions.
84    #[must_use]
85    pub fn all_kinds() -> Vec<InteractionKind> {
86        vec![
87            InteractionKind::Memory,
88            InteractionKind::Program,
89            InteractionKind::Byte,
90            InteractionKind::State,
91            InteractionKind::Syscall,
92            InteractionKind::Global,
93            InteractionKind::ShaExtend,
94            InteractionKind::ShaCompress,
95            InteractionKind::Keccak,
96            InteractionKind::GlobalAccumulation,
97            InteractionKind::MemoryGlobalInitControl,
98            InteractionKind::MemoryGlobalFinalizeControl,
99            InteractionKind::InstructionFetch,
100            InteractionKind::InstructionDecode,
101            InteractionKind::PageProtAccess,
102            InteractionKind::PageProtGlobalInitControl,
103            InteractionKind::PageProtGlobalFinalizeControl,
104            InteractionKind::PageProt,
105        ]
106    }
107
108    #[must_use]
109    /// The number of `values` sent and received for each interaction kind.
110    pub fn num_values(&self) -> usize {
111        match self {
112            InteractionKind::Memory | InteractionKind::Syscall => 9,
113            InteractionKind::Program => 16,
114            InteractionKind::Byte => 4,
115            InteractionKind::Global => 11,
116
117            InteractionKind::ShaCompress => 25,
118            InteractionKind::Keccak => 106,
119            InteractionKind::GlobalAccumulation => 15,
120
121            InteractionKind::InstructionFetch => 22,
122            InteractionKind::InstructionDecode => 19,
123            InteractionKind::ShaExtend
124            | InteractionKind::PageProt
125            | InteractionKind::PageProtAccess => 6,
126            InteractionKind::State
127            | InteractionKind::PageProtGlobalInitControl
128            | InteractionKind::PageProtGlobalFinalizeControl
129            | InteractionKind::MemoryGlobalInitControl
130            | InteractionKind::MemoryGlobalFinalizeControl => 5,
131        }
132    }
133
134    #[must_use]
135    /// Whether this interaction kind gets used in `eval_public_values`.
136    pub fn appears_in_eval_public_values(&self) -> bool {
137        matches!(
138            self,
139            InteractionKind::Byte
140                | InteractionKind::State
141                | InteractionKind::MemoryGlobalFinalizeControl
142                | InteractionKind::MemoryGlobalInitControl
143                | InteractionKind::PageProtGlobalFinalizeControl
144                | InteractionKind::PageProtGlobalInitControl
145                | InteractionKind::GlobalAccumulation
146        )
147    }
148}
149
150impl<F: Field> Interaction<F> {
151    /// Create a new interaction.
152    pub const fn new(
153        values: Vec<VirtualPairCol<F>>,
154        multiplicity: VirtualPairCol<F>,
155        kind: InteractionKind,
156        scope: InteractionScope,
157    ) -> Self {
158        Self { values, multiplicity, kind, scope }
159    }
160
161    /// The index of the argument in the lookup table.
162    pub const fn argument_index(&self) -> usize {
163        self.kind as usize
164    }
165
166    /// Calculate the interactions evaluation.
167    pub fn eval<Expr, Var>(
168        &self,
169        preprocessed: Option<&MleEval<Var>>,
170        main: &MleEval<Var>,
171        alpha: Expr,
172        betas: &[Expr],
173    ) -> (Expr, Expr)
174    where
175        F: Into<Expr>,
176        Expr: AbstractField + Mul<F, Output = Expr>,
177        Var: Into<Expr> + Copy,
178    {
179        let mut multiplicity_eval = self.multiplicity.constant.into();
180        for (column, weight) in self.multiplicity.column_weights.iter() {
181            let weight: Expr = (*weight).into();
182            match column {
183                PairCol::Preprocessed(i) => {
184                    multiplicity_eval += preprocessed.as_ref().unwrap()[*i].into() * weight;
185                }
186                PairCol::Main(i) => multiplicity_eval += main[*i].into() * weight,
187            }
188        }
189
190        let mut betas = betas.iter().cloned();
191        let mut fingerprint_eval =
192            alpha + betas.next().unwrap() * Expr::from_canonical_usize(self.argument_index());
193        for (element, beta) in self.values.iter().zip(betas) {
194            let evaluation = if let Some(preprocessed) = preprocessed {
195                element.apply::<Expr, Var>(preprocessed, main)
196            } else {
197                element.apply::<Expr, Var>(&[], main)
198            };
199            fingerprint_eval += evaluation * beta;
200        }
201
202        (multiplicity_eval, fingerprint_eval)
203    }
204}
205
206impl<F: Field> Debug for Interaction<F> {
207    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
208        f.debug_struct("Interaction")
209            .field("kind", &self.kind)
210            .field("scope", &self.scope)
211            .finish_non_exhaustive()
212    }
213}
214
215impl Display for InteractionKind {
216    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
217        match self {
218            InteractionKind::Memory => write!(f, "Memory"),
219            InteractionKind::Program => write!(f, "Program"),
220            InteractionKind::Byte => write!(f, "Byte"),
221            InteractionKind::State => write!(f, "State"),
222            InteractionKind::Syscall => write!(f, "Syscall"),
223            InteractionKind::Global => write!(f, "Global"),
224            InteractionKind::ShaExtend => write!(f, "ShaExtend"),
225            InteractionKind::ShaCompress => write!(f, "ShaCompress"),
226            InteractionKind::Keccak => write!(f, "Keccak"),
227            InteractionKind::GlobalAccumulation => write!(f, "GlobalAccumulation"),
228            InteractionKind::MemoryGlobalInitControl => write!(f, "MemoryGlobalInitControl"),
229            InteractionKind::MemoryGlobalFinalizeControl => {
230                write!(f, "MemoryGlobalFinalizeControl")
231            }
232            InteractionKind::InstructionFetch => write!(f, "InstructionFetch"),
233            InteractionKind::InstructionDecode => write!(f, "InstructionDecode"),
234            InteractionKind::PageProt => write!(f, "PageProt"),
235            InteractionKind::PageProtAccess => write!(f, "PageProtAccess"),
236            InteractionKind::PageProtGlobalInitControl => write!(f, "PageProtGlobalInitControl"),
237            InteractionKind::PageProtGlobalFinalizeControl => {
238                write!(f, "PageProtGlobalFinalizeControl")
239            }
240        }
241    }
242}
sp1_hypercube/lookup/interaction.rs

sp1_hypercube/lookup/
interaction.rs
