cuprate_helper/
crypto.rs

1//! Crypto related functions and runtime initialized constants
2
3//---------------------------------------------------------------------------------------------------- Use
4use std::sync::LazyLock;
5
6use curve25519_dalek::{
7    constants::{ED25519_BASEPOINT_COMPRESSED, ED25519_BASEPOINT_POINT},
8    edwards::CompressedEdwardsY,
9    edwards::VartimeEdwardsPrecomputation,
10    traits::VartimePrecomputedMultiscalarMul,
11    Scalar,
12};
13use monero_serai::generators::H;
14
15//---------------------------------------------------------------------------------------------------- Pre-computation
16
17/// This is the decomposed amount table containing the mandatory Pre-RCT amounts. It is used to pre-compute 
18/// zero commitments at runtime.
19/// 
20/// Defined at:
21/// - <https://github.com/monero-project/monero/blob/893916ad091a92e765ce3241b94e706ad012b62a/src/ringct/rctOps.cpp#L44>
22#[rustfmt::skip]
23pub const ZERO_COMMITMENT_DECOMPOSED_AMOUNT: [u64; 172] = [
24    1,                   2,                   3,                   4,                   5,                   6,                   7,                   8,                   9,
25    10,                  20,                  30,                  40,                  50,                  60,                  70,                  80,                  90,
26    100,                 200,                 300,                 400,                 500,                 600,                 700,                 800,                 900,
27    1000,                2000,                3000,                4000,                5000,                6000,                7000,                8000,                9000,
28    10000,               20000,               30000,               40000,               50000,               60000,               70000,               80000,               90000,
29    100000,              200000,              300000,              400000,              500000,              600000,              700000,              800000,              900000,
30    1000000,             2000000,             3000000,             4000000,             5000000,             6000000,             7000000,             8000000,             9000000,
31    10000000,            20000000,            30000000,            40000000,            50000000,            60000000,            70000000,            80000000,            90000000,
32    100000000,           200000000,           300000000,           400000000,           500000000,           600000000,           700000000,           800000000,           900000000,
33    1000000000,          2000000000,          3000000000,          4000000000,          5000000000,          6000000000,          7000000000,          8000000000,          9000000000,
34    10000000000,         20000000000,         30000000000,         40000000000,         50000000000,         60000000000,         70000000000,         80000000000,         90000000000,
35    100000000000,        200000000000,        300000000000,        400000000000,        500000000000,        600000000000,        700000000000,        800000000000,        900000000000,
36    1000000000000,       2000000000000,       3000000000000,       4000000000000,       5000000000000,       6000000000000,       7000000000000,       8000000000000,       9000000000000,
37    10000000000000,      20000000000000,      30000000000000,      40000000000000,      50000000000000,      60000000000000,      70000000000000,      80000000000000,      90000000000000,
38    100000000000000,     200000000000000,     300000000000000,     400000000000000,     500000000000000,     600000000000000,     700000000000000,     800000000000000,     900000000000000,
39    1000000000000000,    2000000000000000,    3000000000000000,    4000000000000000,    5000000000000000,    6000000000000000,    7000000000000000,    8000000000000000,    9000000000000000,
40    10000000000000000,   20000000000000000,   30000000000000000,   40000000000000000,   50000000000000000,   60000000000000000,   70000000000000000,   80000000000000000,   90000000000000000,
41    100000000000000000,  200000000000000000,  300000000000000000,  400000000000000000,  500000000000000000,  600000000000000000,  700000000000000000,  800000000000000000,  900000000000000000,
42    1000000000000000000, 2000000000000000000, 3000000000000000000, 4000000000000000000, 5000000000000000000, 6000000000000000000, 7000000000000000000, 8000000000000000000, 9000000000000000000,
43    10000000000000000000
44];
45
46/// Runtime initialized [`H`] generator.
47static H_PRECOMP: LazyLock<VartimeEdwardsPrecomputation> =
48    LazyLock::new(|| VartimeEdwardsPrecomputation::new([*H, ED25519_BASEPOINT_POINT]));
49
50/// Runtime initialized zero commitment lookup table
51///
52/// # Invariant
53/// This function assumes that the [`ZERO_COMMITMENT_DECOMPOSED_AMOUNT`]
54/// table is sorted.
55pub static ZERO_COMMITMENT_LOOKUP_TABLE: LazyLock<[CompressedEdwardsY; 172]> =
56    LazyLock::new(|| {
57        let mut lookup_table: [CompressedEdwardsY; 172] = [ED25519_BASEPOINT_COMPRESSED; 172];
58
59        for (i, amount) in ZERO_COMMITMENT_DECOMPOSED_AMOUNT.into_iter().enumerate() {
60            lookup_table[i] = (ED25519_BASEPOINT_POINT + *H * Scalar::from(amount)).compress();
61        }
62
63        lookup_table
64    });
65
66//---------------------------------------------------------------------------------------------------- Free functions
67
68/// This function computes the zero commitment given a specific amount.
69///
70/// It will first attempt to lookup into the table of known Pre-RCT value.
71/// Compute it otherwise.
72#[expect(clippy::cast_possible_truncation)]
73pub fn compute_zero_commitment(amount: u64) -> CompressedEdwardsY {
74    // OPTIMIZATION: Unlike monerod which execute a linear search across its lookup
75    // table (O(n)). Cuprate is making use of an arithmetic based constant time
76    // version (O(1)). It has been benchmarked in both hit and miss scenarios against
77    // a binary search lookup (O(log2(n))). To understand the following algorithm it
78    // is important to observe the pattern that follows the values of
79    // [`ZERO_COMMITMENT_DECOMPOSED_AMOUNT`].
80
81    // First obtain the logarithm base 10 of the amount. and extend it back to obtain
82    // the amount without its most significant digit.
83    let Some(log) = amount.checked_ilog10() else {
84        // amount = 0 so H component is 0.
85        return ED25519_BASEPOINT_COMPRESSED;
86    };
87    let div = 10_u64.pow(log);
88
89    // Extract the most significant digit.
90    let most_significant_digit = amount / div;
91
92    // If the *rounded* version is different than the exact amount. Then
93    // there aren't only trailing zeroes behind the most significant digit.
94    // The amount is not part of the table and can calculated apart.
95    if most_significant_digit * div != amount {
96        return H_PRECOMP
97            .vartime_multiscalar_mul([Scalar::from(amount), Scalar::ONE])
98            .compress();
99    }
100
101    // Calculating the index back by progressing within the powers of 10.
102    // The index of the first value in the cached amount's row.
103    let row_start = u64::from(log) * 9;
104    // The index of the cached amount
105    let index = (most_significant_digit - 1 + row_start) as usize;
106
107    ZERO_COMMITMENT_LOOKUP_TABLE[index]
108}
109
110//---------------------------------------------------------------------------------------------------- Tests
111#[cfg(test)]
112mod test {
113    use curve25519_dalek::{traits::VartimePrecomputedMultiscalarMul, Scalar};
114
115    use crate::crypto::{compute_zero_commitment, H_PRECOMP, ZERO_COMMITMENT_DECOMPOSED_AMOUNT};
116
117    #[test]
118    /// Compare the output of `compute_zero_commitment` for all
119    /// preRCT decomposed amounts against their actual computation.
120    ///
121    /// Assert that the lookup table returns the correct commitments
122    fn compare_lookup_with_computation() {
123        for amount in ZERO_COMMITMENT_DECOMPOSED_AMOUNT {
124            let commitment = H_PRECOMP.vartime_multiscalar_mul([Scalar::from(amount), Scalar::ONE]);
125            assert_eq!(
126                commitment,
127                compute_zero_commitment(amount).decompress().unwrap()
128            );
129        }
130    }
131}
cuprate_helper/crypto.rs

cuprate_helper/
crypto.rs
