core_utils/circuit/latest/
preprocessing.rs

1use std::ops::{Index, IndexMut};
2
3use derive_more::derive::{Add, AddAssign, Sub, SubAssign};
4use primitives::correlated_randomness::bundler::BundleConsumer;
5use serde::{Deserialize, Serialize};
6
7use crate::{
8    circuit::{
9        AlgebraicType,
10        BitShareBinaryOp,
11        Circuit,
12        FieldShareBinaryOp,
13        FieldShareUnaryOp,
14        FieldType,
15        Gate,
16        GateExt,
17        Input,
18        PointShareBinaryOp,
19        PointShareUnaryOp,
20        ShareOrPlaintext,
21    },
22    config::MpcConfig,
23    preprocessing::iterator::PreprocessingIterator,
24};
25
26/// Number of network rounds needed to compute the AES S-box (currently using the algorithm of [Boyar and Peralta](https://eprint.iacr.org/2011/332.pdf)).
27/// The achievable minimum is 4 but this would require to concatenate columns in a way that we have
28/// to clone them first. In our batching, however, we try to minimize cloning and thus end up
29/// performing the 34 ANDs in 8 rounds.
30pub(crate) const AES_S_BOX_N_NETWORK_ROUNDS: usize = 8;
31
32/// Number of bit triples needed to compute the AES S-box (currently using the algorithm of [Boyar and Peralta](https://eprint.iacr.org/2011/332.pdf)).
33pub(crate) const AES_S_BOX_N_TRIPLES: usize = 34;
34
35/// Number of GF(2) lanes the semi-honest online-phase packs into one machine word for
36/// [`Gate::AesGcmKeyStream`]/[`Gate::GhashPowersOfH`] (`online_phase::tasks::field::packed_bit::
37/// PACKED_BIT_LEN`, duplicated here since `core-utils` doesn't depend on `online-phase`).
38pub(crate) const SEMI_HONEST_PACKED_LANES: usize = 64;
39
40/// Field specific preprocessing requirements for a circuit.
41#[derive(
42    Debug,
43    Copy,
44    Clone,
45    Default,
46    PartialEq,
47    Eq,
48    Add,
49    AddAssign,
50    Sub,
51    SubAssign,
52    Serialize,
53    Deserialize,
54)]
55#[repr(C)]
56pub struct FieldCircuitPreprocessing {
57    pub singlets: usize,
58    pub triples: usize,
59    pub dabits: usize,
60}
61
62impl FieldCircuitPreprocessing {
63    /// Component-wise maximum of two requirement/position vectors.
64    pub fn componentwise_max(self, other: Self) -> Self {
65        Self {
66            singlets: self.singlets.max(other.singlets),
67            triples: self.triples.max(other.triples),
68            dabits: self.dabits.max(other.dabits),
69        }
70    }
71}
72
73/// Preprocessing requirements for a circuit.
74#[derive(
75    Debug,
76    Copy,
77    Clone,
78    Default,
79    PartialEq,
80    Eq,
81    Add,
82    AddAssign,
83    Sub,
84    SubAssign,
85    Serialize,
86    Deserialize,
87)]
88#[repr(C)]
89pub struct CircuitPreprocessing {
90    pub bit_singlets: usize,
91    pub bit_triples: usize,
92    pub base_field: FieldCircuitPreprocessing,
93    pub scalar: FieldCircuitPreprocessing,
94    pub mpc_field: FieldCircuitPreprocessing,
95}
96
97impl CircuitPreprocessing {
98    /// Component-wise maximum of two position vectors — used to agree on a resync target across
99    /// parties: take the per-stream maximum of everyone's [`StreamBundler::positions`], then feed
100    /// it to [`StreamBundler::resync`].
101    ///
102    /// [`StreamBundler::positions`]: crate::preprocessing::bundler::StreamBundler::positions
103    /// [`StreamBundler::resync`]: crate::preprocessing::bundler::StreamBundler::resync
104    pub fn componentwise_max(self, other: Self) -> Self {
105        Self {
106            bit_singlets: self.bit_singlets.max(other.bit_singlets),
107            bit_triples: self.bit_triples.max(other.bit_triples),
108            base_field: self.base_field.componentwise_max(other.base_field),
109            scalar: self.scalar.componentwise_max(other.scalar),
110            mpc_field: self.mpc_field.componentwise_max(other.mpc_field),
111        }
112    }
113}
114
115impl Index<FieldType> for CircuitPreprocessing {
116    type Output = FieldCircuitPreprocessing;
117
118    fn index(&self, index: FieldType) -> &Self::Output {
119        match index {
120            FieldType::BaseField => &self.base_field,
121            FieldType::ScalarField => &self.scalar,
122            FieldType::MpcField => &self.mpc_field,
123        }
124    }
125}
126
127impl IndexMut<FieldType> for CircuitPreprocessing {
128    fn index_mut(&mut self, index: FieldType) -> &mut Self::Output {
129        match index {
130            FieldType::BaseField => &mut self.base_field,
131            FieldType::ScalarField => &mut self.scalar,
132            FieldType::MpcField => &mut self.mpc_field,
133        }
134    }
135}
136
137impl<C: MpcConfig> BundleConsumer for Circuit<C> {
138    type Iterator = PreprocessingIterator<C>;
139
140    fn required_preprocessing(&self) -> CircuitPreprocessing {
141        let mut circuit_preprocessing = CircuitPreprocessing::default();
142        for gate in self.iter_gates_ext() {
143            self.add_to_required_preprocessing(gate, &mut circuit_preprocessing);
144        }
145        circuit_preprocessing
146    }
147}
148
149impl<C: MpcConfig> Circuit<C> {
150    /// Updates the circuit preprocessing structure with the requirements of this gate.
151    pub fn add_to_required_preprocessing(
152        &self,
153        gate: &GateExt<C>,
154        circuit_preprocessing: &mut CircuitPreprocessing,
155    ) {
156        let batch_size = gate.output.get_batch_size() as usize;
157        match &gate.gate {
158            Gate::Input(Input::SecretPlaintext { algebraic_type, .. })
159            | Gate::Random { algebraic_type, .. } => match algebraic_type {
160                AlgebraicType::ScalarField | AlgebraicType::Point => {
161                    circuit_preprocessing.scalar.singlets += batch_size;
162                }
163                AlgebraicType::BaseField => {
164                    circuit_preprocessing.base_field.singlets += batch_size;
165                }
166                AlgebraicType::Bit => {
167                    circuit_preprocessing.bit_singlets += batch_size;
168                }
169                AlgebraicType::MpcField => {
170                    circuit_preprocessing.mpc_field.singlets += batch_size;
171                }
172            },
173            Gate::FieldShareUnaryOp { op, .. } => {
174                let field_type = gate.output.get_field_type_unchecked();
175                match op {
176                    FieldShareUnaryOp::MulInverse | FieldShareUnaryOp::IsZero => {
177                        circuit_preprocessing[field_type].triples += batch_size;
178                        circuit_preprocessing[field_type].singlets += batch_size;
179                    }
180                    FieldShareUnaryOp::Open | FieldShareUnaryOp::Neg => (),
181                }
182            }
183            Gate::FieldShareBinaryOp { op, y, .. } => match op {
184                FieldShareBinaryOp::Mul => {
185                    let field_type = gate.output.get_field_type_unchecked();
186                    if self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share {
187                        circuit_preprocessing[field_type].triples += batch_size;
188                    }
189                }
190                FieldShareBinaryOp::Add => (),
191            },
192            Gate::PointShareUnaryOp { op, .. } => match op {
193                PointShareUnaryOp::IsZero => {
194                    circuit_preprocessing.scalar.triples += batch_size;
195                    circuit_preprocessing.scalar.singlets += batch_size;
196                }
197                PointShareUnaryOp::Open | PointShareUnaryOp::Neg => (),
198            },
199            Gate::PointShareBinaryOp { op, p, y, .. } => match op {
200                PointShareBinaryOp::ScalarMul => {
201                    if self.gate_output_unchecked(*p).get_form() == ShareOrPlaintext::Share
202                        && self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share
203                    {
204                        circuit_preprocessing.scalar.triples += batch_size;
205                    }
206                }
207                PointShareBinaryOp::Add => (),
208            },
209            Gate::BitShareBinaryOp { op, y, .. } => match op {
210                BitShareBinaryOp::And | BitShareBinaryOp::Or => {
211                    if self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share {
212                        circuit_preprocessing.bit_triples += batch_size;
213                    }
214                }
215                BitShareBinaryOp::Xor => (),
216            },
217            Gate::BaseFieldPow { .. } => {
218                unimplemented!("Removed from the Bundler, need to choose exponent to set it back.")
219            }
220            Gate::DaBit { field_type, .. } => {
221                circuit_preprocessing[*field_type].dabits += batch_size
222            }
223
224            Gate::Input(_)
225            | Gate::Constant { .. }
226            | Gate::BatchSummation { .. }
227            | Gate::BitShareUnaryOp { .. }
228            | Gate::FieldPlaintextUnaryOp { .. }
229            | Gate::FieldPlaintextBinaryOp { .. }
230            | Gate::BitPlaintextUnaryOp { .. }
231            | Gate::BitPlaintextBinaryOp { .. }
232            | Gate::PointPlaintextUnaryOp { .. }
233            | Gate::PointPlaintextBinaryOp { .. }
234            | Gate::GetDaBitFieldShare { .. }
235            | Gate::GetDaBitSharedBit { .. }
236            | Gate::BitPlaintextToField { .. }
237            | Gate::FieldPlaintextToBit { .. }
238            | Gate::ExtractFromBatch { .. }
239            | Gate::CollectToBatch { .. }
240            | Gate::PointFromPlaintextCoordinates { .. }
241            | Gate::PlaintextPointToCoordinates { .. }
242            | Gate::PlaintextKeccakF1600 { .. }
243            | Gate::CompressPlaintextPoint { .. }
244            | Gate::KeyRecoveryPlaintextComputeErrors { .. }
245            | Gate::Ghash { .. } => (),
246            #[cfg(any(test, feature = "dev"))]
247            Gate::AesKeySchedule { key, .. } => {
248                let key_length = self.gate_ext_unchecked(*key).output.batch_size;
249                circuit_preprocessing.bit_triples += n_triples_aes_key_schedule(key_length as usize)
250                    .expect("Something went wrong with Circuit::add_to_required_preprocessing for Gate::AesKeySchedule")
251            }
252            Gate::AesGcmKeyStream {
253                round_keys,
254                n_ciphertext_blocks,
255                ..
256            } => {
257                let round_keys_length = self.gate_ext_unchecked(*round_keys).output.batch_size;
258                // No threat-model parameter here, so this must cover whichever model lowers the
259                // gate: the semi-honest packed task recomputes the IV's sub_bytes in every packed
260                // lane (a fixed surcharge), and the malicious task leaves that excess unconsumed.
261                circuit_preprocessing.bit_triples +=
262                    n_triples_aes_gcm_key_stream(round_keys_length as usize, *n_ciphertext_blocks)
263                        .map(|n| n + AES_S_BOX_N_TRIPLES * 12 * (SEMI_HONEST_PACKED_LANES - 1))
264                        .expect("Something went wrong with Circuit::add_to_required_preprocessing for Gate::AesGcmKeyStream")
265            }
266            Gate::GhashPowersOfH {
267                n_ciphertext_blocks,
268                ..
269            } => {
270                circuit_preprocessing.bit_triples +=
271                    (*n_ciphertext_blocks as usize - 1) * n_triples_gf2_128_multiply()
272            }
273        };
274    }
275}
276
277pub fn n_triples_aes_key_schedule(security_level: usize) -> Option<usize> {
278    let n_sub_bytes_calls = match security_level {
279        128 => Some(10),
280        192 => Some(8),
281        256 => Some(13),
282        _ => None,
283    };
284    // sub_bytes is called on vectors of 4 bytes
285    n_sub_bytes_calls.map(|n_calls| 4 * AES_S_BOX_N_TRIPLES * n_calls)
286}
287
288pub fn n_triples_aes_gcm_key_stream(
289    round_keys_length: usize,
290    n_ciphertext_blocks: u32,
291) -> Option<usize> {
292    // round keys length must be 11 * 128, 13 * 128 or 15 * 128
293    // for AES-128, AES-192 and AES-256 respectively
294    let n_rounds = match round_keys_length {
295        1408 => Some(10),
296        1664 => Some(12),
297        1920 => Some(14),
298        _ => None,
299    };
300    // For all but the first round, sub_bytes is computed on slices of length
301    // 1+n_ciphertext_blocks. In the first round, the first 12 S-boxes (inverses)
302    // are computed on slices of length 1.
303    n_rounds.map(|n| {
304        AES_S_BOX_N_TRIPLES
305            * (12
306                + 4 * (1 + n_ciphertext_blocks as usize)
307                + (n - 1) * 16 * (1 + n_ciphertext_blocks as usize))
308    })
309}
310
311pub fn n_triples_gf2_128_multiply() -> usize {
312    // 128 shift-and-add steps × 128 bitands
313    128 * 128
314}
315
316#[cfg(test)]
317mod tests {
318    use crate::circuit::preprocessing::{CircuitPreprocessing, FieldCircuitPreprocessing};
319
320    #[test]
321    fn test_circuit_preprocessing_add() {
322        let a = CircuitPreprocessing {
323            bit_singlets: 0,
324            bit_triples: 1,
325            base_field: FieldCircuitPreprocessing {
326                singlets: 3,
327                triples: 4,
328                dabits: 2,
329            },
330            scalar: FieldCircuitPreprocessing {
331                singlets: 1,
332                triples: 2,
333                dabits: 1,
334            },
335            mpc_field: FieldCircuitPreprocessing {
336                singlets: 0,
337                triples: 0,
338                dabits: 0,
339            },
340        };
341        let b = CircuitPreprocessing {
342            bit_singlets: 3,
343            bit_triples: 4,
344            base_field: FieldCircuitPreprocessing {
345                singlets: 0,
346                triples: 5,
347                dabits: 3,
348            },
349            scalar: FieldCircuitPreprocessing {
350                singlets: 2,
351                triples: 3,
352                dabits: 2,
353            },
354            mpc_field: FieldCircuitPreprocessing {
355                singlets: 3,
356                triples: 2,
357                dabits: 0,
358            },
359        };
360
361        let c = a + b;
362
363        assert_eq!(c.scalar.singlets, 3);
364        assert_eq!(c.scalar.triples, 5);
365        assert_eq!(c.base_field.singlets, 3);
366        assert_eq!(c.base_field.triples, 9);
367        assert_eq!(c.bit_singlets, 3);
368        assert_eq!(c.bit_triples, 5);
369        assert_eq!(c.mpc_field.dabits, 0);
370        assert_eq!(c.mpc_field.singlets, 3);
371        assert_eq!(c.mpc_field.triples, 2);
372        assert_eq!(c.scalar.dabits, 3);
373        assert_eq!(c.base_field.dabits, 5);
374    }
375}
core_utils/circuit/latest/preprocessing.rs

core_utils/circuit/latest/
preprocessing.rs
