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

use crate::evm_circuit::util::{
    constraint_builder::{ConstrainBuilderCommon, EVMConstraintBuilder},
    from_bytes, CachedRegion, Cell,
};
use eth_types::Field;
use halo2_proofs::{
    circuit::Value,
    plonk::{Error, Expression},
};

/// Requires that the passed in value is within the specified range.
/// `N_BYTES` is required to be `<= MAX_N_BYTES_INTEGER`.
#[derive(Clone, Debug)]
pub struct RangeCheckGadget<F, const N_BYTES: usize> {
    parts: [Cell<F>; N_BYTES],
}

impl<F: Field, const N_BYTES: usize> RangeCheckGadget<F, N_BYTES> {
    pub(crate) fn construct(cb: &mut EVMConstraintBuilder<F>, value: Expression<F>) -> Self {
        let parts = cb.query_bytes();

        // Require that the reconstructed value from the parts equals the
        // original value
        cb.require_equal(
            "Constrain bytes recomposited to value",
            value,
            from_bytes::expr(&parts),
        );

        Self { parts }
    }

    pub(crate) fn assign(
        &self,
        region: &mut CachedRegion<'_, '_, F>,
        offset: usize,
        value: F,
    ) -> Result<(), Error> {
        let bytes = value.to_repr();
        for (idx, part) in self.parts.iter().enumerate() {
            part.assign(region, offset, Value::known(F::from(bytes[idx] as u64)))?;
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::{super::test_util::*, *};
    use eth_types::*;
    use gadgets::util::Expr;
    use halo2_proofs::{circuit::Value, halo2curves::bn256::Fr, plonk::Error};

    #[derive(Clone)]
    /// RangeCheckTestContainer: require(a in [0..1<<(8*N_BYTES)])
    struct RangeCheckTestContainer<F, const N_BYTES: usize> {
        range_check_gadget: RangeCheckGadget<F, N_BYTES>,
        a: Cell<F>,
    }

    impl<F: Field, const N_BYTES: usize> MathGadgetContainer<F>
        for RangeCheckTestContainer<F, N_BYTES>
    {
        fn configure_gadget_container(cb: &mut EVMConstraintBuilder<F>) -> Self {
            let a = cb.query_cell();
            let range_check_gadget = RangeCheckGadget::<F, N_BYTES>::construct(cb, a.expr());
            RangeCheckTestContainer {
                range_check_gadget,
                a,
            }
        }

        fn assign_gadget_container(
            &self,
            witnesses: &[Word],
            region: &mut CachedRegion<'_, '_, F>,
        ) -> Result<(), Error> {
            let a = witnesses[0].to_scalar().unwrap();
            let offset = 0;

            self.a.assign(region, offset, Value::known(a))?;
            self.range_check_gadget.assign(region, 0, a)?;

            Ok(())
        }
    }

    #[test]
    fn test_rangecheck_just_in_range() {
        try_test!(RangeCheckTestContainer<Fr, 4>,[Word::from(0)], true);

        try_test!(RangeCheckTestContainer<Fr, 4>,[Word::from(1)], true);
        // max - 1
        try_test!(
            RangeCheckTestContainer<Fr, 4>,
           [Word::from((1u64 << 32) - 1)],
            true,
        );
    }

    #[test]
    fn test_rangecheck_out_of_range() {
        try_test!(
            RangeCheckTestContainer<Fr, 4>,
            [Word::from(1u64 << 32)],
            false,
        );
    }
}