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

cuprate_helper/
crypto.rs
