zkevm_circuits 0.153.12

ZKsync Era circuits for EraVM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//! 32-byte implementation of the modular exponentiation algorithm.

use boojum::{
    cs::traits::cs::ConstraintSystem,
    ethereum_types::U256,
    field::SmallField,
    gadgets::{traits::selectable::Selectable, u256::UInt256},
};

const U256_MAX_BITS: usize = 256;
const U512_MAX_BITS: usize = 512;
const U256_MAX_LIMBS: usize = 8;
const U512_MAX_LIMBS: usize = 16;

const MAX_BINARY_SEARCH_ITERATIONS: usize = 33;

/// Finds the result of exponentiating `base` to the power of `exponent` modulo `modulus`.
/// Input parameters format is done according to EIP-198:
/// https://eips.ethereum.org/EIPS/eip-198.
///
/// Implementation is based on _Algorithm 1_ from the paper
/// https://cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf.
///
/// This implementation works with 32-byte `base`, `exponent`, and `modulus`.
pub fn modexp_32_32_32<F, CS>(
    cs: &mut CS,
    base: &UInt256<F>,
    exponent: &UInt256<F>,
    modulus: &UInt256<F>,
) -> UInt256<F>
where
    F: SmallField,
    CS: ConstraintSystem<F>,
{
    let mut a = UInt256::allocated_constant(cs, U256::one());
    let binary_expansion = exponent
        .to_le_bytes(cs)
        .into_iter()
        .map(|x| x.into_num().spread_into_bits::<CS, 8>(cs))
        .flatten()
        .collect::<Vec<_>>();
    let mod_is_zero = modulus.is_zero(cs);
    for e in binary_expansion.into_iter().rev() {
        // a <- a^2 mod (modulus)
        let a_squared = a.modmul(cs, &a, modulus);

        // a <- a^2 * (base) mod (modulus)
        let a_base = a_squared.modmul(cs, base, modulus);

        // If the i-th bit of the exponent is 1, then a <- a^2 * (base) mod (modulus)
        // Otherwise, we just set a <- a^2 mod (modulus)
        a = UInt256::conditionally_select(cs, e, &a_base, &a_squared);
    }

    // See EIP-198; if exponent is zero, we shall return zero.

    let res = a.mask_negated(cs, mod_is_zero);

    res
}