core_utils/circuit/v2/
preprocessing.rs

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

core_utils/circuit/v2/
preprocessing.rs
