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;
5
6use crate::{
7    circuit::{
8        AlgebraicType,
9        BitShareBinaryOp,
10        Circuit,
11        FieldShareBinaryOp,
12        FieldShareUnaryOp,
13        FieldType,
14        Gate,
15        GateExt,
16        Input,
17        PointShareBinaryOp,
18        PointShareUnaryOp,
19        ShareOrPlaintext,
20    },
21    config::MpcConfig,
22    preprocessing::iterator::PreprocessingIterator,
23};
24
25/// 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)).
26/// The achievable minimum is 4 but this would require to concatenate columns in a way that we have
27/// to clone them first. In our batching, however, we try to minimize cloning and thus end up
28/// performing the 34 ANDs in 8 rounds.
29pub(crate) const AES_S_BOX_N_NETWORK_ROUNDS: usize = 8;
30
31/// 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)).
32pub(crate) const AES_S_BOX_N_TRIPLES: usize = 34;
33
34/// Field specific preprocessing requirements for a circuit.
35#[derive(Debug, Copy, Clone, Default, PartialEq, Eq, Add, AddAssign, Sub, SubAssign)]
36pub struct FieldCircuitPreprocessing {
37    pub singlets: usize,
38    pub triples: usize,
39    pub dabits: usize,
40}
41
42/// Preprocessing requirements for a circuit.
43#[derive(Debug, Copy, Clone, Default, PartialEq, Eq, Add, AddAssign, Sub, SubAssign)]
44pub struct CircuitPreprocessing {
45    pub bit_singlets: usize,
46    pub bit_triples: usize,
47    pub base_field: FieldCircuitPreprocessing,
48    pub scalar: FieldCircuitPreprocessing,
49    pub mpc_field: FieldCircuitPreprocessing,
50}
51
52impl Index<FieldType> for CircuitPreprocessing {
53    type Output = FieldCircuitPreprocessing;
54
55    fn index(&self, index: FieldType) -> &Self::Output {
56        match index {
57            FieldType::BaseField => &self.base_field,
58            FieldType::ScalarField => &self.scalar,
59            FieldType::MpcField => &self.mpc_field,
60        }
61    }
62}
63
64impl IndexMut<FieldType> for CircuitPreprocessing {
65    fn index_mut(&mut self, index: FieldType) -> &mut Self::Output {
66        match index {
67            FieldType::BaseField => &mut self.base_field,
68            FieldType::ScalarField => &mut self.scalar,
69            FieldType::MpcField => &mut self.mpc_field,
70        }
71    }
72}
73
74impl<C: MpcConfig> BundleConsumer for Circuit<C> {
75    type Iterator = PreprocessingIterator<C>;
76
77    fn required_preprocessing(&self) -> CircuitPreprocessing {
78        let mut circuit_preprocessing = CircuitPreprocessing::default();
79        for gate in self.iter_gates_ext() {
80            self.add_to_required_preprocessing(gate, &mut circuit_preprocessing);
81        }
82        circuit_preprocessing
83    }
84}
85
86impl<C: MpcConfig> Circuit<C> {
87    /// Updates the circuit preprocessing structure with the requirements of this gate.
88    pub fn add_to_required_preprocessing(
89        &self,
90        gate: &GateExt<C>,
91        circuit_preprocessing: &mut CircuitPreprocessing,
92    ) {
93        let batch_size = gate.output.get_batch_size() as usize;
94        match &gate.gate {
95            Gate::Input(Input::SecretPlaintext { algebraic_type, .. })
96            | Gate::Random { algebraic_type, .. } => match algebraic_type {
97                AlgebraicType::ScalarField | AlgebraicType::Point => {
98                    circuit_preprocessing.scalar.singlets += batch_size;
99                }
100                AlgebraicType::BaseField => {
101                    circuit_preprocessing.base_field.singlets += batch_size;
102                }
103                AlgebraicType::Bit => {
104                    circuit_preprocessing.bit_singlets += batch_size;
105                }
106                AlgebraicType::MpcField => {
107                    circuit_preprocessing.mpc_field.singlets += batch_size;
108                }
109            },
110            Gate::FieldShareUnaryOp { op, .. } => {
111                let field_type = gate.output.get_field_type_unchecked();
112                match op {
113                    FieldShareUnaryOp::MulInverse | FieldShareUnaryOp::IsZero => {
114                        circuit_preprocessing[field_type].triples += batch_size;
115                        circuit_preprocessing[field_type].singlets += batch_size;
116                    }
117                    FieldShareUnaryOp::Open | FieldShareUnaryOp::Neg => (),
118                }
119            }
120            Gate::FieldShareBinaryOp { op, y, .. } => match op {
121                FieldShareBinaryOp::Mul => {
122                    let field_type = gate.output.get_field_type_unchecked();
123                    if self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share {
124                        circuit_preprocessing[field_type].triples += batch_size;
125                    }
126                }
127                FieldShareBinaryOp::Add => (),
128            },
129            Gate::PointShareUnaryOp { op, .. } => match op {
130                PointShareUnaryOp::IsZero => {
131                    circuit_preprocessing.scalar.triples += batch_size;
132                    circuit_preprocessing.scalar.singlets += batch_size;
133                }
134                PointShareUnaryOp::Open | PointShareUnaryOp::Neg => (),
135            },
136            Gate::PointShareBinaryOp { op, p, y, .. } => match op {
137                PointShareBinaryOp::ScalarMul => {
138                    if self.gate_output_unchecked(*p).get_form() == ShareOrPlaintext::Share
139                        && self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share
140                    {
141                        circuit_preprocessing.scalar.triples += batch_size;
142                    }
143                }
144                PointShareBinaryOp::Add => (),
145            },
146            Gate::BitShareBinaryOp { op, y, .. } => match op {
147                BitShareBinaryOp::And | BitShareBinaryOp::Or => {
148                    if self.gate_output_unchecked(*y).get_form() == ShareOrPlaintext::Share {
149                        circuit_preprocessing.bit_triples += batch_size;
150                    }
151                }
152                BitShareBinaryOp::Xor => (),
153            },
154            Gate::BaseFieldPow { .. } => {
155                unimplemented!("Removed from the Bundler, need to choose exponent to set it back.")
156            }
157            Gate::DaBit { field_type, .. } => {
158                circuit_preprocessing[*field_type].dabits += batch_size
159            }
160
161            Gate::Input(_)
162            | Gate::Constant { .. }
163            | Gate::BatchSummation { .. }
164            | Gate::BitShareUnaryOp { .. }
165            | Gate::FieldPlaintextUnaryOp { .. }
166            | Gate::FieldPlaintextBinaryOp { .. }
167            | Gate::BitPlaintextUnaryOp { .. }
168            | Gate::BitPlaintextBinaryOp { .. }
169            | Gate::PointPlaintextUnaryOp { .. }
170            | Gate::PointPlaintextBinaryOp { .. }
171            | Gate::GetDaBitFieldShare { .. }
172            | Gate::GetDaBitSharedBit { .. }
173            | Gate::BitPlaintextToField { .. }
174            | Gate::FieldPlaintextToBit { .. }
175            | Gate::ExtractFromBatch { .. }
176            | Gate::CollectToBatch { .. }
177            | Gate::PointFromPlaintextCoordinates { .. }
178            | Gate::PlaintextPointToCoordinates { .. }
179            | Gate::PlaintextKeccakF1600 { .. }
180            | Gate::CompressPlaintextPoint { .. }
181            | Gate::KeyRecoveryPlaintextComputeErrors { .. }
182            | Gate::Ghash { .. } => (),
183            #[cfg(any(test, feature = "dev"))]
184            Gate::AesKeySchedule { key, .. } => {
185                let key_length = self.gate_ext(*key).map(|g| g.output.batch_size).ok();
186                circuit_preprocessing.bit_triples += key_length
187                    .and_then(|len| n_triples_aes_key_schedule(len as usize))
188                    .expect("Something went wrong with Circuit::add_to_required_preprocessing for Gate::AesKeySchedule")
189            }
190            Gate::AesGcmKeyStream {
191                round_keys,
192                n_ciphertext_blocks,
193                ..
194            } => {
195                let round_keys_length =
196                    self.gate_ext(*round_keys).map(|g| g.output.batch_size).ok();
197                circuit_preprocessing.bit_triples += round_keys_length
198                    .and_then(|len| {
199                        n_triples_aes_gcm_key_stream(len as usize, *n_ciphertext_blocks)
200                    })
201                    .expect("Something went wrong with Circuit::add_to_required_preprocessing for Gate::AesGcmKeyStream")
202            }
203            Gate::GhashPowersOfH {
204                n_ciphertext_blocks,
205                ..
206            } => {
207                circuit_preprocessing.bit_triples +=
208                    (*n_ciphertext_blocks as usize - 1) * n_triples_gf2_128_multiply()
209            }
210        };
211    }
212}
213
214pub fn n_triples_aes_key_schedule(security_level: usize) -> Option<usize> {
215    let n_sub_bytes_calls = match security_level {
216        128 => Some(10),
217        192 => Some(8),
218        256 => Some(13),
219        _ => None,
220    };
221    // sub_bytes is called on vectors of 4 bytes
222    n_sub_bytes_calls.map(|n_calls| 4 * AES_S_BOX_N_TRIPLES * n_calls)
223}
224
225pub fn n_triples_aes_gcm_key_stream(
226    round_keys_length: usize,
227    n_ciphertext_blocks: u32,
228) -> Option<usize> {
229    // round keys length must be 11 * 128, 13 * 128 or 15 * 128
230    // for AES-128, AES-192 and AES-256 respectively
231    let n_rounds = match round_keys_length {
232        1408 => Some(10),
233        1664 => Some(12),
234        1920 => Some(14),
235        _ => None,
236    };
237    // For all but the first round, sub_bytes is computed on slices of length
238    // 1+n_ciphertext_blocks. In the first round, the first 12 S-boxes (inverses)
239    // are computed on slices of length 1.
240    n_rounds.map(|n| {
241        AES_S_BOX_N_TRIPLES
242            * (12
243                + 4 * (1 + n_ciphertext_blocks as usize)
244                + (n - 1) * 16 * (1 + n_ciphertext_blocks as usize))
245    })
246}
247
248pub fn n_triples_gf2_128_multiply() -> usize {
249    // 128 shift-and-add steps × 128 bitands
250    128 * 128
251}
252
253#[cfg(test)]
254mod tests {
255    use crate::circuit::preprocessing::{CircuitPreprocessing, FieldCircuitPreprocessing};
256
257    #[test]
258    fn test_circuit_preprocessing_add() {
259        let a = CircuitPreprocessing {
260            bit_singlets: 0,
261            bit_triples: 1,
262            base_field: FieldCircuitPreprocessing {
263                singlets: 3,
264                triples: 4,
265                dabits: 2,
266            },
267            scalar: FieldCircuitPreprocessing {
268                singlets: 1,
269                triples: 2,
270                dabits: 1,
271            },
272            mpc_field: FieldCircuitPreprocessing {
273                singlets: 0,
274                triples: 0,
275                dabits: 0,
276            },
277        };
278        let b = CircuitPreprocessing {
279            bit_singlets: 3,
280            bit_triples: 4,
281            base_field: FieldCircuitPreprocessing {
282                singlets: 0,
283                triples: 5,
284                dabits: 3,
285            },
286            scalar: FieldCircuitPreprocessing {
287                singlets: 2,
288                triples: 3,
289                dabits: 2,
290            },
291            mpc_field: FieldCircuitPreprocessing {
292                singlets: 3,
293                triples: 2,
294                dabits: 0,
295            },
296        };
297
298        let c = a + b;
299
300        assert_eq!(c.scalar.singlets, 3);
301        assert_eq!(c.scalar.triples, 5);
302        assert_eq!(c.base_field.singlets, 3);
303        assert_eq!(c.base_field.triples, 9);
304        assert_eq!(c.bit_singlets, 3);
305        assert_eq!(c.bit_triples, 5);
306        assert_eq!(c.mpc_field.dabits, 0);
307        assert_eq!(c.mpc_field.singlets, 3);
308        assert_eq!(c.mpc_field.triples, 2);
309        assert_eq!(c.scalar.dabits, 3);
310        assert_eq!(c.base_field.dabits, 5);
311    }
312}
core_utils/circuit/v2/preprocessing.rs

core_utils/circuit/v2/
preprocessing.rs
