clock_bigint/
gas.rs

1//! Gas metering for BigInt operations.
2//!
3//! This module provides deterministic gas cost calculation functions
4//! that depend only on public parameters (limb length, exponent length).
5
6/// Gas type (u64).
7pub type Gas = u64;
8
9/// Baseline dispatch cost unit.
10pub const G_BASE: Gas = 10;
11
12/// Maximum number of limbs allowed (prevents DoS).
13pub const MAX_LIMBS: usize = 512;
14
15/// Calculate gas cost for addition.
16///
17/// Formula: `G_add(n) = 3n`
18pub fn cost_add(n: usize) -> Gas {
19    G_BASE + (3 * n as Gas)
20}
21
22/// Calculate gas cost for subtraction.
23///
24/// Formula: `G_sub(n) = 3n`
25pub fn cost_sub(n: usize) -> Gas {
26    G_BASE + (3 * n as Gas)
27}
28
29/// Calculate gas cost for negation.
30///
31/// Formula: `G_neg(n) = 2n`
32pub fn cost_neg(n: usize) -> Gas {
33    G_BASE + (2 * n as Gas)
34}
35
36/// Calculate gas cost for comparison.
37///
38/// Formula: `G_cmp(n) = 2n`
39pub fn cost_cmp(n: usize) -> Gas {
40    G_BASE + (2 * n as Gas)
41}
42
43/// Calculate gas cost for bit shift.
44///
45/// Formula: `G_shift(n) = 2n`
46pub fn cost_shift(n: usize) -> Gas {
47    G_BASE + (2 * n as Gas)
48}
49
50/// Calculate gas cost for multiplication.
51///
52/// Formula: `G_mul(n) = 2n²`
53pub fn cost_mul(n: usize) -> Gas {
54    G_BASE + (2 * (n as Gas) * (n as Gas))
55}
56
57/// Calculate gas cost for squaring.
58///
59/// Formula: `G_sqr(n) = 1.6n²`
60pub fn cost_sqr(n: usize) -> Gas {
61    G_BASE + ((16 * (n as Gas) * (n as Gas)) / 10)
62}
63
64/// Calculate gas cost for multiply-accumulate.
65///
66/// Formula: `G_mac(n) = 2n²`
67pub fn cost_mac(n: usize) -> Gas {
68    cost_mul(n)
69}
70
71/// Calculate gas cost for division.
72///
73/// Formula: `G_div(n) = 4n²`
74pub fn cost_div(n: usize) -> Gas {
75    G_BASE + (4 * (n as Gas) * (n as Gas))
76}
77
78/// Calculate gas cost for modulo.
79///
80/// Formula: `G_mod(n) = 4n²`
81pub fn cost_mod(n: usize) -> Gas {
82    cost_div(n)
83}
84
85/// Calculate gas cost for division with remainder.
86///
87/// Formula: `G_divmod(n) = 4n²`
88pub fn cost_divmod(n: usize) -> Gas {
89    cost_div(n)
90}
91
92/// Calculate gas cost for Montgomery reduction.
93///
94/// Formula: `G_mred(n) = n²`
95pub fn cost_mont_reduce(n: usize) -> Gas {
96    G_BASE + ((n as Gas) * (n as Gas))
97}
98
99/// Calculate gas cost for Montgomery multiplication.
100///
101/// Formula: `G_mmul(n) = 2n²`
102pub fn cost_mont_mul(n: usize) -> Gas {
103    G_BASE + (2 * (n as Gas) * (n as Gas))
104}
105
106/// Calculate gas cost for Montgomery addition/subtraction.
107///
108/// Formula: `G_madd(n) = 3n`
109pub fn cost_mont_add(n: usize) -> Gas {
110    G_BASE + (3 * n as Gas)
111}
112
113/// Calculate gas cost for conversion to Montgomery form.
114///
115/// Formula: `G_tomont(n) = G_mmul(n)`
116pub fn cost_tomont(n: usize) -> Gas {
117    cost_mont_mul(n)
118}
119
120/// Calculate gas cost for conversion from Montgomery form.
121///
122/// Formula: `G_frommont(n) = G_mred(n)`
123pub fn cost_frommont(n: usize) -> Gas {
124    cost_mont_reduce(n)
125}
126
127/// Calculate gas cost for modular exponentiation.
128///
129/// Formula: `G_modexp(n, k) = k × 4n² + 20n²`
130/// where `k` is the exponent bit length.
131pub fn cost_modexp(n: usize, k: usize) -> Gas {
132    let n_gas = n as Gas;
133    let k_gas = k as Gas;
134    G_BASE + (k_gas * 4 * n_gas * n_gas) + (20 * n_gas * n_gas)
135}
136
137/// Calculate gas cost for modular inversion via exponentiation.
138///
139/// Same as `cost_modexp`.
140pub fn cost_inv_modexp(n: usize, k: usize) -> Gas {
141    cost_modexp(n, k)
142}
143
144/// Calculate gas cost for modular inversion via Binary GCD.
145///
146/// Formula: `G_inv(n) = 6n²`
147pub fn cost_inv_gcd(n: usize) -> Gas {
148    G_BASE + (6 * (n as Gas) * (n as Gas))
149}
150
151/// Calculate gas cost for canonicalization.
152///
153/// Formula: `G_canon(n) = n`
154pub fn cost_canonicalize(n: usize) -> Gas {
155    G_BASE + (n as Gas)
156}
157
158/// Calculate gas cost for encoding.
159///
160/// Formula: `G_enc(n) = n`
161pub fn cost_encode(n: usize) -> Gas {
162    G_BASE + (n as Gas)
163}
164
165/// Calculate gas cost for decoding.
166///
167/// Formula: `G_dec(n) = n`
168pub fn cost_decode(n: usize) -> Gas {
169    G_BASE + (n as Gas)
170}
171
172/// Validate that the number of limbs does not exceed MAX_LIMBS.
173pub fn validate_limb_count(n: usize) -> Result<(), ()> {
174    if n > MAX_LIMBS { Err(()) } else { Ok(()) }
175}
176
177#[cfg(test)]
178mod tests {
179    use super::*;
180
181    #[test]
182    fn test_cost_add() {
183        assert_eq!(cost_add(4), 10 + 12); // G_BASE + 3*4
184        assert_eq!(cost_add(32), 10 + 96); // G_BASE + 3*32
185    }
186
187    #[test]
188    fn test_cost_mul() {
189        assert_eq!(cost_mul(4), 10 + 32); // G_BASE + 2*4*4
190        assert_eq!(cost_mul(32), 10 + 2048); // G_BASE + 2*32*32
191    }
192
193    #[test]
194    fn test_cost_modexp() {
195        // 256-bit exponent with 256-bit modulus (n=4, k=256)
196        let cost = cost_modexp(4, 256);
197        // k × 4n² + 20n² = 256 × 4×16 + 20×16 = 256×64 + 320 = 16384 + 320 = 16704
198        assert_eq!(cost, 10 + 16704);
199    }
200
201    #[test]
202    fn test_max_limbs() {
203        assert!(validate_limb_count(512).is_ok());
204        assert!(validate_limb_count(513).is_err());
205    }
206
207    #[test]
208    fn test_cost_sub() {
209        assert_eq!(cost_sub(4), 10 + 12); // G_BASE + 3*4
210        assert_eq!(cost_sub(32), 10 + 96); // G_BASE + 3*32
211    }
212
213    #[test]
214    fn test_cost_neg() {
215        assert_eq!(cost_neg(4), 10 + 8); // G_BASE + 2*4
216        assert_eq!(cost_neg(32), 10 + 64); // G_BASE + 2*32
217    }
218
219    #[test]
220    fn test_cost_cmp() {
221        assert_eq!(cost_cmp(4), 10 + 8); // G_BASE + 2*4
222        assert_eq!(cost_cmp(32), 10 + 64); // G_BASE + 2*32
223    }
224
225    #[test]
226    fn test_cost_shift() {
227        assert_eq!(cost_shift(4), 10 + 8); // G_BASE + 2*4
228        assert_eq!(cost_shift(32), 10 + 64); // G_BASE + 2*32
229    }
230
231    #[test]
232    fn test_cost_sqr() {
233        assert_eq!(cost_sqr(4), 10 + 25); // G_BASE + (16*16)/10 = 10 + 25.6 = 35.6, truncated to 35
234        assert_eq!(cost_sqr(32), 10 + 1638); // G_BASE + (16*1024)/10 = 10 + 16384/10 = 10 + 1638.4 = 1648.4, truncated to 1648
235    }
236
237    #[test]
238    fn test_cost_mac() {
239        assert_eq!(cost_mac(4), 10 + 32); // Same as cost_mul = G_BASE + 2*4*4
240        assert_eq!(cost_mac(32), 10 + 2048); // Same as cost_mul = G_BASE + 2*32*32
241    }
242
243    #[test]
244    fn test_cost_div() {
245        assert_eq!(cost_div(4), 10 + 64); // G_BASE + 4*4*4
246        assert_eq!(cost_div(32), 10 + 4096); // G_BASE + 4*32*32
247    }
248
249    #[test]
250    fn test_cost_mod() {
251        assert_eq!(cost_mod(4), 10 + 64); // Same as cost_div = G_BASE + 4*4*4
252        assert_eq!(cost_mod(32), 10 + 4096); // Same as cost_div = G_BASE + 4*32*32
253    }
254
255    #[test]
256    fn test_cost_divmod() {
257        assert_eq!(cost_divmod(4), 10 + 64); // Same as cost_div = G_BASE + 4*4*4
258        assert_eq!(cost_divmod(32), 10 + 4096); // Same as cost_div = G_BASE + 4*32*32
259    }
260
261    #[test]
262    fn test_cost_mont_reduce() {
263        assert_eq!(cost_mont_reduce(4), 10 + 16); // G_BASE + 4*4
264        assert_eq!(cost_mont_reduce(32), 10 + 1024); // G_BASE + 32*32
265    }
266
267    #[test]
268    fn test_cost_mont_mul() {
269        assert_eq!(cost_mont_mul(4), 10 + 32); // G_BASE + 2*4*4 (same as regular mul)
270        assert_eq!(cost_mont_mul(32), 10 + 2048); // G_BASE + 2*32*32 (same as regular mul)
271    }
272
273    #[test]
274    fn test_cost_mont_add() {
275        assert_eq!(cost_mont_add(4), 10 + 12); // G_BASE + 3*4
276        assert_eq!(cost_mont_add(32), 10 + 96); // G_BASE + 3*32
277    }
278
279    #[test]
280    fn test_cost_tomont() {
281        assert_eq!(cost_tomont(4), 10 + 32); // Same as cost_mont_mul = G_BASE + 2*4*4
282        assert_eq!(cost_tomont(32), 10 + 2048); // Same as cost_mont_mul = G_BASE + 2*32*32
283    }
284
285    #[test]
286    fn test_cost_frommont() {
287        assert_eq!(cost_frommont(4), 10 + 16); // Same as cost_mont_reduce = G_BASE + 4*4
288        assert_eq!(cost_frommont(32), 10 + 1024); // Same as cost_mont_reduce = G_BASE + 32*32
289    }
290
291    #[test]
292    fn test_cost_inv_modexp() {
293        // 256-bit modulus with 256-bit exponent (n=4, k=256)
294        let cost = cost_inv_modexp(4, 256);
295        // Same as modexp cost
296        assert_eq!(cost, cost_modexp(4, 256));
297    }
298
299    #[test]
300    fn test_cost_inv_gcd() {
301        assert_eq!(cost_inv_gcd(4), 10 + 96); // G_BASE + 6*4*4
302        assert_eq!(cost_inv_gcd(32), 10 + 6144); // G_BASE + 6*32*32
303    }
304
305    #[test]
306    fn test_cost_canonicalize() {
307        assert_eq!(cost_canonicalize(4), 10 + 4); // G_BASE + 1*4
308        assert_eq!(cost_canonicalize(32), 10 + 32); // G_BASE + 1*32
309    }
310
311    #[test]
312    fn test_cost_encode() {
313        assert_eq!(cost_encode(4), 10 + 4); // G_BASE + 1*4
314        assert_eq!(cost_encode(32), 10 + 32); // G_BASE + 1*32
315    }
316
317    #[test]
318    fn test_cost_decode() {
319        assert_eq!(cost_decode(4), 10 + 4); // G_BASE + 1*4
320        assert_eq!(cost_decode(32), 10 + 32); // G_BASE + 1*32
321    }
322
323    #[test]
324    fn test_gas_costs_are_positive() {
325        // All gas costs should be positive
326        assert!(cost_add(1) > 0);
327        assert!(cost_sub(1) > 0);
328        assert!(cost_mul(1) > 0);
329        assert!(cost_div(1) > 0);
330        assert!(cost_modexp(1, 1) > 0);
331    }
332
333    #[test]
334    fn test_gas_costs_increase_with_size() {
335        // Gas costs should generally increase with operand size
336        assert!(cost_add(8) > cost_add(4));
337        assert!(cost_mul(8) > cost_mul(4));
338        assert!(cost_modexp(8, 64) > cost_modexp(4, 32));
339    }
340
341    #[test]
342    fn test_gas_constants() {
343        assert_eq!(G_BASE, 10);
344        assert_eq!(MAX_LIMBS, 512);
345    }
346}
clock_bigint/gas.rs

clock_bigint/
gas.rs
