jf_relation/
constants.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! Crate wide constants.
8
9use ark_ff::{FftField, PrimeField};
10use ark_std::{rand::SeedableRng, vec, vec::Vec};
11use rand_chacha::ChaChaRng;
12
13// ==========================
14// Circuit-related constants.
15// ==========================
16
17/// The number of input wires.
18pub const GATE_WIDTH: usize = 4;
19/// The number of multiplication selectors.
20pub const N_MUL_SELECTORS: usize = 2;
21/// The number of TurboPlonk selectors.
22pub const N_TURBO_PLONK_SELECTORS: usize = 13;
23
24/// Compute constants K0, K1, ..., K_{`num_wire_types`-1} so that cosets {Ki *
25/// H} are disjoint, each coset |Ki * H| = `coset_size`.
26/// `coset_size` is optional, when provided, will accelerate constants
27/// searching.
28#[inline]
29#[allow(non_snake_case)]
30pub fn compute_coset_representatives<F: PrimeField>(
31    num_wire_types: usize,
32    coset_size: Option<usize>,
33) -> Vec<F> {
34    // check if two cosets `aH == bH` where `a, b` are cosets representations
35    fn is_equal_coset<F: PrimeField>(pow_a_N: F, pow_b_N: F) -> bool {
36        // check (a^-1 * b)^`N` = 1
37        pow_a_N
38            .inverse()
39            .expect("Unreachable: all elements in a prime field should have inverse")
40            * pow_b_N
41            == F::one()
42    }
43
44    // check if a new k is valid: i.e. doesn't represent the same coset as any
45    // previous values `prev`.
46    fn is_valid_k<F: PrimeField>(pow_k_N: F, pow_prev_N: &[F]) -> bool {
47        !pow_prev_N
48            .iter()
49            .any(|&pow_k_prev_N| is_equal_coset(pow_k_N, pow_k_prev_N))
50    }
51
52    // storing cached `Ki -> Ki^coset_size` values.
53    let mut pow_k_N_vec = vec![];
54    let mut k_vec = vec![];
55    let mut rng = ChaChaRng::from_seed([0u8; 32]); // empty bytes as seed
56
57    // the exponent N for checking membership of domain H
58    let N = match coset_size {
59        Some(size) => size,
60        None => {
61            // let `2^s * t` be the size of the multiplicative group defined by the field
62            // `F`, for some odd integer `t`, `s` is the 2-adicity of `F*`.
63            // `2^s` is a guaranteed to be multiple of |H|.
64            2usize.pow(<F as FftField>::TWO_ADICITY)
65        },
66    };
67    for i in 0..num_wire_types {
68        if i == 0 {
69            // set first K0 = 1, namely the H itself
70            k_vec.push(F::one());
71            pow_k_N_vec.push(F::one());
72        } else {
73            let mut next = F::rand(&mut rng);
74            let mut pow_next_N = next.pow([N as u64]);
75            while !is_valid_k(pow_next_N, &pow_k_N_vec) {
76                next = F::rand(&mut rng);
77                pow_next_N = next.pow([N as u64]);
78            }
79            k_vec.push(next);
80            pow_k_N_vec.push(pow_next_N);
81        }
82    }
83    k_vec
84}
jf_relation/constants.rs

jf_relation/
constants.rs
