core_utils/circuit/v2/
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};
6use wincode::{SchemaRead, SchemaWrite};
7
8use crate::{
9    circuit::{
10        AlgebraicType,
11        BitShareBinaryOp,
12        Circuit,
13        FieldShareBinaryOp,
14        FieldShareUnaryOp,
15        FieldType,
16        Gate,
17        GateExt,
18        Input,
19        PointShareBinaryOp,
20        PointShareUnaryOp,
21        ShareOrPlaintext,
22    },
23    config::MpcConfig,
24    preprocessing::iterator::PreprocessingIterator,
25};
26
27/// 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)).
28/// The achievable minimum is 4 but this would require to concatenate columns in a way that we have
29/// to clone them first. In our batching, however, we try to minimize cloning and thus end up
30/// performing the 34 ANDs in 8 rounds.
31pub(crate) const AES_S_BOX_N_NETWORK_ROUNDS: usize = 8;
32
33/// 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)).
34pub(crate) const AES_S_BOX_N_TRIPLES: usize = 34;
35
36/// Field specific preprocessing requirements for a circuit.
37#[derive(
38    Debug,
39    Copy,
40    Clone,
41    Default,
42    PartialEq,
43    Eq,
44    Add,
45    AddAssign,
46    Sub,
47    SubAssign,
48    Serialize,
49    Deserialize,
50    SchemaRead,
51    SchemaWrite,
52)]
53#[repr(C)]
54pub struct FieldCircuitPreprocessing {
55    pub singlets: usize,
56    pub triples: usize,
57    pub dabits: usize,
58}
59
60impl FieldCircuitPreprocessing {
61    /// Component-wise maximum of two requirement/position vectors.
62    pub fn componentwise_max(self, other: Self) -> Self {
63        Self {
64            singlets: self.singlets.max(other.singlets),
65            triples: self.triples.max(other.triples),
66            dabits: self.dabits.max(other.dabits),
67        }
68    }
69}
70
71/// Preprocessing requirements for a circuit.
72#[derive(
73    Debug,
74    Copy,
75    Clone,
76    Default,
77    PartialEq,
78    Eq,
79    Add,
80    AddAssign,
81    Sub,
82    SubAssign,
83    Serialize,
84    Deserialize,
85    SchemaRead,
86    SchemaWrite,
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(*key).map(|g| g.output.batch_size).ok();
249                circuit_preprocessing.bit_triples += key_length
250                    .and_then(|len| n_triples_aes_key_schedule(len as usize))
251                    .expect("Something went wrong with Circuit::add_to_required_preprocessing for Gate::AesKeySchedule")
252            }
253            Gate::AesGcmKeyStream {
254                round_keys,
255                n_ciphertext_blocks,
256                ..
257            } => {
258                let round_keys_length =
259                    self.gate_ext(*round_keys).map(|g| g.output.batch_size).ok();
260                circuit_preprocessing.bit_triples += round_keys_length
261                    .and_then(|len| {
262                        n_triples_aes_gcm_key_stream(len as usize, *n_ciphertext_blocks)
263                    })
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/v2/preprocessing.rs

core_utils/circuit/v2/
preprocessing.rs
