franklin_crypto/plonk/circuit/bigint_new/
mod.rs

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
use bellman::plonk::better_better_cs::cs::LookupTableApplication;

use super::allocated_num::*;
use super::boolean::*;
use crate::bellman::pairing::ff::{BitIterator, Field, PrimeField, PrimeFieldRepr};
use crate::bellman::pairing::Engine;
use crate::bellman::plonk::better_better_cs::cs::{
    ArithmeticTerm, Coefficient, ConstraintSystem, Gate, GateInternal, LinearCombinationOfTerms, MainGate, MainGateTerm, PlonkConstraintSystemParams, PlonkCsWidth4WithNextStepParams,
    PolynomialInConstraint, PolynomialMultiplicativeTerm, TimeDilation, TrivialAssembly, Variable, Width4MainGateWithDNext,
};
use crate::bellman::SynthesisError;
use crate::plonk::circuit::utils::u64_to_fe;
use crate::plonk::circuit::Assignment;
use bellman::plonk::better_better_cs::data_structures::*;
use std::iter::FromIterator;
use std::sync::Arc;

pub mod bigint;
pub mod range_check_custom_gate2;
pub mod range_check_table2;
pub mod range_checks;

pub use self::bigint::*;
pub use self::range_check_custom_gate2::*;
pub use self::range_check_table2::*;
pub use self::range_checks::*;

pub mod amplified_linear_combination;
pub mod field;
pub use self::amplified_linear_combination::*;
pub use self::field::*;

pub const BITWISE_LOGICAL_OPS_TABLE_NAME: &'static str = "Table for bitwise logical ops";
pub const DEFAULT_RANGE_TABLE_GRANULARITY: usize = 8;

// splits an element into slices of fixed bit widths in LE order
#[track_caller]
pub fn split_into_slices<F: PrimeField>(el: &F, slice_width: usize, num_slices: usize) -> Vec<F> {
    let mut repr = el.into_repr();
    assert!(repr.num_bits() as usize <= slice_width * num_slices);
    let mut slices = Vec::with_capacity(num_slices);
    if slice_width < 64 {
        let mask = (1u64 << slice_width) - 1u64;
        for _ in 0..num_slices {
            let slice = repr.as_ref()[0] & mask;

            let mut r = F::Repr::default();
            r.as_mut()[0] = slice;

            let slice = F::from_repr(r).unwrap();
            slices.push(slice);

            repr.shr(slice_width as u32);
        }
    } else {
        let it = repr.as_ref().iter().map(|x| u64_to_fe::<F>(*x)).take(num_slices);
        slices.extend(it);
    };

    slices
}

#[track_caller]
pub fn split_some_into_slices<F: PrimeField>(el: Option<F>, slice_width: usize, num_slices: usize) -> Vec<Option<F>> {
    if let Some(v) = el.as_ref() {
        split_into_slices(v, slice_width, num_slices).into_iter().map(|el| Some(el)).collect()
    } else {
        vec![None; num_slices]
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum RangeConstraintStrategy {
    NaiveSingleBit,
    CustomTwoBitGate,
    WithBitwiseOpTable(usize), // parameter here is the chunk width
}

impl RangeConstraintStrategy {
    pub fn get_range_check_granularity(&self) -> usize {
        match self {
            RangeConstraintStrategy::NaiveSingleBit => 1,
            RangeConstraintStrategy::CustomTwoBitGate => 2,
            RangeConstraintStrategy::WithBitwiseOpTable(n) => *n,
        }
    }
}

pub fn get_optimal_strategy<E: Engine, CS: ConstraintSystem<E>>(cs: &CS) -> RangeConstraintStrategy {
    if let Ok(table) = cs.get_table(BITWISE_LOGICAL_OPS_TABLE_NAME) {
        let width = crate::log2_floor(table.size()) / 2;
        return RangeConstraintStrategy::WithBitwiseOpTable(width as usize);
    }
    if CS::Params::STATE_WIDTH == 4 && CS::Params::HAS_CUSTOM_GATES {
        return RangeConstraintStrategy::CustomTwoBitGate;
    }
    RangeConstraintStrategy::NaiveSingleBit
}

pub fn inscribe_default_bitop_range_table<E, CS>(cs: &mut CS) -> Result<Arc<LookupTableApplication<E>>, SynthesisError>
where
    E: Engine,
    CS: ConstraintSystem<E>,
{
    use crate::plonk::circuit::hashes_with_tables::get_or_create_table;

    let columns3 = vec![PolyIdentifier::VariablesPolynomial(0), PolyIdentifier::VariablesPolynomial(1), PolyIdentifier::VariablesPolynomial(2)];

    get_or_create_table(cs, BITWISE_LOGICAL_OPS_TABLE_NAME, || {
        LookupTableApplication::new(
            BITWISE_LOGICAL_OPS_TABLE_NAME,
            CombinedBitwiseLogicRangeTable::new(BITWISE_LOGICAL_OPS_TABLE_NAME, DEFAULT_RANGE_TABLE_GRANULARITY),
            columns3,
            None,
            true,
        )
    })
}

pub(crate) fn compute_shifts<F: PrimeField>() -> Vec<F> {
    let mut result = Vec::with_capacity(F::CAPACITY as usize);
    let mut el = F::one();
    result.push(el);
    for _ in 1..F::CAPACITY {
        el.double();
        result.push(el);
    }

    result
}

pub(crate) fn round_up(x: usize, granularity: usize) -> usize {
    let rem = x % granularity;
    let to_add = if rem == 0 { 0 } else { granularity - rem };
    x + to_add
}