halo2_base/safe_types/
mod.rs

1use std::{
2    borrow::Borrow,
3    cmp::{max, min},
4};
5
6use crate::{
7    gates::{
8        flex_gate::GateInstructions,
9        range::{RangeChip, RangeInstructions},
10    },
11    utils::ScalarField,
12    AssignedValue, Context,
13    QuantumCell::Constant,
14};
15
16use itertools::Itertools;
17
18mod bytes;
19mod primitives;
20
21pub use bytes::*;
22pub use primitives::*;
23
24/// Unit Tests
25#[cfg(test)]
26pub mod tests;
27
28type RawAssignedValues<F> = Vec<AssignedValue<F>>;
29
30const BITS_PER_BYTE: usize = 8;
31
32/// [`SafeType`]'s goal is to avoid out-of-range undefined behavior.
33/// When building circuits, it's common to use multiple [`AssignedValue<F>`]s to represent
34/// a logical variable. For example, we might want to represent a hash with 32 [`AssignedValue<F>`]
35/// where each [`AssignedValue`] represents 1 byte. However, the range of [`AssignedValue<F>`] is much
36/// larger than 1 byte(0~255). If a circuit takes 32 [`AssignedValue<F>`] as inputs and some of them
37/// are actually greater than 255, there could be some undefined behaviors.
38/// [`SafeType`] gurantees the value range of its owned [`AssignedValue<F>`]. So circuits don't need to
39/// do any extra value checking if they take SafeType as inputs.
40/// - `TOTAL_BITS` is the number of total bits of this type.
41/// - `BYTES_PER_ELE` is the number of bytes of each element.
42#[derive(Clone, Debug)]
43pub struct SafeType<F: ScalarField, const BYTES_PER_ELE: usize, const TOTAL_BITS: usize> {
44    // value is stored in little-endian.
45    value: RawAssignedValues<F>,
46}
47
48impl<F: ScalarField, const BYTES_PER_ELE: usize, const TOTAL_BITS: usize>
49    SafeType<F, BYTES_PER_ELE, TOTAL_BITS>
50{
51    /// Number of bytes of each element.
52    pub const BYTES_PER_ELE: usize = BYTES_PER_ELE;
53    /// Total bits of this type.
54    pub const TOTAL_BITS: usize = TOTAL_BITS;
55    /// Number of elements of this type.
56    pub const VALUE_LENGTH: usize = TOTAL_BITS.div_ceil(BYTES_PER_ELE * BITS_PER_BYTE);
57
58    /// Number of bits of each element.
59    pub fn bits_per_ele() -> usize {
60        min(TOTAL_BITS, BYTES_PER_ELE * BITS_PER_BYTE)
61    }
62
63    // new is private so Safetype can only be constructed by this crate.
64    fn new(raw_values: RawAssignedValues<F>) -> Self {
65        assert!(raw_values.len() == Self::VALUE_LENGTH, "Invalid raw values length");
66        Self { value: raw_values }
67    }
68
69    /// Return values in little-endian.
70    pub fn value(&self) -> &[AssignedValue<F>] {
71        &self.value
72    }
73}
74
75impl<F: ScalarField, const BYTES_PER_ELE: usize, const TOTAL_BITS: usize> AsRef<[AssignedValue<F>]>
76    for SafeType<F, BYTES_PER_ELE, TOTAL_BITS>
77{
78    fn as_ref(&self) -> &[AssignedValue<F>] {
79        self.value()
80    }
81}
82
83impl<F: ScalarField, const TOTAL_BITS: usize> TryFrom<Vec<SafeByte<F>>>
84    for SafeType<F, 1, TOTAL_BITS>
85{
86    type Error = String;
87
88    fn try_from(value: Vec<SafeByte<F>>) -> Result<Self, Self::Error> {
89        if value.len() * 8 != TOTAL_BITS {
90            return Err("Invalid length".to_owned());
91        }
92        Ok(Self::new(value.into_iter().map(|b| b.0).collect::<Vec<_>>()))
93    }
94}
95
96/// SafeType for Address.
97pub type SafeAddress<F> = SafeType<F, 1, 160>;
98/// SafeType for bytes32.
99pub type SafeBytes32<F> = SafeType<F, 1, 256>;
100
101/// Chip for SafeType
102pub struct SafeTypeChip<'a, F: ScalarField> {
103    range_chip: &'a RangeChip<F>,
104}
105
106impl<'a, F: ScalarField> SafeTypeChip<'a, F> {
107    /// Construct a SafeTypeChip.
108    pub fn new(range_chip: &'a RangeChip<F>) -> Self {
109        Self { range_chip }
110    }
111
112    /// Convert a vector of AssignedValue (treated as little-endian) to a SafeType.
113    /// The number of bytes of inputs must equal to the number of bytes of outputs.
114    /// This function also add contraints that a AssignedValue in inputs must be in the range of a byte.
115    pub fn raw_bytes_to<const BYTES_PER_ELE: usize, const TOTAL_BITS: usize>(
116        &self,
117        ctx: &mut Context<F>,
118        inputs: RawAssignedValues<F>,
119    ) -> SafeType<F, BYTES_PER_ELE, TOTAL_BITS> {
120        let element_bits = SafeType::<F, BYTES_PER_ELE, TOTAL_BITS>::bits_per_ele();
121        let bits = TOTAL_BITS;
122        assert!(
123            inputs.len() * BITS_PER_BYTE == max(bits, BITS_PER_BYTE),
124            "number of bits doesn't match"
125        );
126        self.add_bytes_constraints(ctx, &inputs, bits);
127        // inputs is a bool or uint8.
128        if bits == 1 || element_bits == BITS_PER_BYTE {
129            return SafeType::<F, BYTES_PER_ELE, TOTAL_BITS>::new(inputs);
130        };
131        assert!(
132            element_bits <= F::CAPACITY as usize,
133            "packed SafeType element exceeds native field capacity"
134        );
135
136        let byte_base = (0..BYTES_PER_ELE)
137            .map(|i| Constant(self.range_chip.gate.pow_of_two[i * BITS_PER_BYTE]))
138            .collect::<Vec<_>>();
139        let value = inputs
140            .chunks(BYTES_PER_ELE)
141            .map(|chunk| {
142                self.range_chip.gate.inner_product(
143                    ctx,
144                    chunk.to_vec(),
145                    byte_base[..chunk.len()].to_vec(),
146                )
147            })
148            .collect::<Vec<_>>();
149        SafeType::<F, BYTES_PER_ELE, TOTAL_BITS>::new(value)
150    }
151
152    /// Unsafe method that directly converts `input` to [`SafeType`] **without any checks**.
153    /// This should **only** be used if an external library needs to convert their types to [`SafeType`].
154    pub fn unsafe_to_safe_type<const BYTES_PER_ELE: usize, const TOTAL_BITS: usize>(
155        inputs: RawAssignedValues<F>,
156    ) -> SafeType<F, BYTES_PER_ELE, TOTAL_BITS> {
157        assert_eq!(inputs.len(), SafeType::<F, BYTES_PER_ELE, TOTAL_BITS>::VALUE_LENGTH);
158        SafeType::<F, BYTES_PER_ELE, TOTAL_BITS>::new(inputs)
159    }
160
161    /// Constrains that the `input` is a boolean value (either 0 or 1) and wraps it in [`SafeBool`].
162    pub fn assert_bool(&self, ctx: &mut Context<F>, input: AssignedValue<F>) -> SafeBool<F> {
163        self.range_chip.gate().assert_bit(ctx, input);
164        SafeBool(input)
165    }
166
167    /// Load a boolean value as witness and constrain it is either 0 or 1.
168    pub fn load_bool(&self, ctx: &mut Context<F>, input: bool) -> SafeBool<F> {
169        let input = ctx.load_witness(F::from(input));
170        self.assert_bool(ctx, input)
171    }
172
173    /// Unsafe method that directly converts `input` to [`SafeBool`] **without any checks**.
174    /// This should **only** be used if an external library needs to convert their types to [`SafeBool`].
175    pub fn unsafe_to_bool(input: AssignedValue<F>) -> SafeBool<F> {
176        SafeBool(input)
177    }
178
179    /// Constrains that the `input` is a byte value and wraps it in [`SafeByte`].
180    pub fn assert_byte(&self, ctx: &mut Context<F>, input: AssignedValue<F>) -> SafeByte<F> {
181        self.range_chip.range_check(ctx, input, BITS_PER_BYTE);
182        SafeByte(input)
183    }
184
185    /// Load a boolean value as witness and constrain it is either 0 or 1.
186    pub fn load_byte(&self, ctx: &mut Context<F>, input: u8) -> SafeByte<F> {
187        let input = ctx.load_witness(F::from(input as u64));
188        self.assert_byte(ctx, input)
189    }
190
191    /// Unsafe method that directly converts `input` to [`SafeByte`] **without any checks**.
192    /// This should **only** be used if an external library needs to convert their types to [`SafeByte`].
193    pub fn unsafe_to_byte(input: AssignedValue<F>) -> SafeByte<F> {
194        SafeByte(input)
195    }
196
197    /// Unsafe method that directly converts `inputs` to [`VarLenBytes`] **without any checks**.
198    /// This should **only** be used if an external library needs to convert their types to [`SafeByte`].
199    pub fn unsafe_to_var_len_bytes<const MAX_LEN: usize>(
200        inputs: [AssignedValue<F>; MAX_LEN],
201        len: AssignedValue<F>,
202    ) -> VarLenBytes<F, MAX_LEN> {
203        VarLenBytes::<F, MAX_LEN>::new(inputs.map(|input| Self::unsafe_to_byte(input)), len)
204    }
205
206    /// Unsafe method that directly converts `inputs` to [`VarLenBytesVec`] **without any checks**.
207    /// This should **only** be used if an external library needs to convert their types to [`SafeByte`].
208    pub fn unsafe_to_var_len_bytes_vec(
209        inputs: RawAssignedValues<F>,
210        len: AssignedValue<F>,
211        max_len: usize,
212    ) -> VarLenBytesVec<F> {
213        VarLenBytesVec::<F>::new(
214            inputs.iter().map(|input| Self::unsafe_to_byte(*input)).collect_vec(),
215            len,
216            max_len,
217        )
218    }
219
220    /// Unsafe method that directly converts `inputs` to [`FixLenBytes`] **without any checks**.
221    /// This should **only** be used if an external library needs to convert their types to [`SafeByte`].
222    pub fn unsafe_to_fix_len_bytes<const MAX_LEN: usize>(
223        inputs: [AssignedValue<F>; MAX_LEN],
224    ) -> FixLenBytes<F, MAX_LEN> {
225        FixLenBytes::<F, MAX_LEN>::new(inputs.map(|input| Self::unsafe_to_byte(input)))
226    }
227
228    /// Unsafe method that directly converts `inputs` to [`FixLenBytesVec`] **without any checks**.
229    /// This should **only** be used if an external library needs to convert their types to [`SafeByte`].
230    pub fn unsafe_to_fix_len_bytes_vec(
231        inputs: RawAssignedValues<F>,
232        len: usize,
233    ) -> FixLenBytesVec<F> {
234        FixLenBytesVec::<F>::new(
235            inputs.into_iter().map(|input| Self::unsafe_to_byte(input)).collect_vec(),
236            len,
237        )
238    }
239
240    /// Converts a slice of AssignedValue(treated as little-endian) to VarLenBytes.
241    ///
242    /// * inputs: Slice representing the byte array.
243    /// * len: [`AssignedValue<F>`] witness representing the variable length of the byte array. Constrained to be `<= MAX_LEN`.
244    /// * MAX_LEN: [usize] representing the maximum length of the byte array and the number of elements it must contain.
245    ///
246    /// ## Assumptions
247    /// * `MAX_LEN < u64::MAX` to prevent overflow (but you should never make an array this large)
248    /// * `ceil((MAX_LEN + 1).bits() / lookup_bits) * lookup_bits < F::CAPACITY` where `lookup_bits = self.range_chip.lookup_bits`
249    pub fn raw_to_var_len_bytes<const MAX_LEN: usize>(
250        &self,
251        ctx: &mut Context<F>,
252        inputs: [AssignedValue<F>; MAX_LEN],
253        len: AssignedValue<F>,
254    ) -> VarLenBytes<F, MAX_LEN> {
255        self.range_chip.check_less_than_safe(ctx, len, MAX_LEN as u64 + 1);
256        VarLenBytes::<F, MAX_LEN>::new(inputs.map(|input| self.assert_byte(ctx, input)), len)
257    }
258
259    /// Converts a vector of AssignedValue to [VarLenBytesVec]. Not encouraged to use because `MAX_LEN` cannot be verified at compile time.
260    ///
261    /// * inputs: Vector representing the byte array, right padded to `max_len`. See [VarLenBytesVec] for details about padding.
262    /// * len: [`AssignedValue<F>`] witness representing the variable length of the byte array. Constrained to be `<= max_len`.
263    /// * max_len: [usize] representing the maximum length of the byte array and the number of elements it must contain. We enforce this to be provided explictly to make sure length of `inputs` is determinstic.
264    ///
265    /// ## Assumptions
266    /// * `max_len < u64::MAX` to prevent overflow (but you should never make an array this large)
267    /// * `ceil((max_len + 1).bits() / lookup_bits) * lookup_bits < F::CAPACITY` where `lookup_bits = self.range_chip.lookup_bits`
268    pub fn raw_to_var_len_bytes_vec(
269        &self,
270        ctx: &mut Context<F>,
271        inputs: RawAssignedValues<F>,
272        len: AssignedValue<F>,
273        max_len: usize,
274    ) -> VarLenBytesVec<F> {
275        self.range_chip.check_less_than_safe(ctx, len, max_len as u64 + 1);
276        VarLenBytesVec::<F>::new(
277            inputs.iter().map(|input| self.assert_byte(ctx, *input)).collect_vec(),
278            len,
279            max_len,
280        )
281    }
282
283    /// Converts a slice of AssignedValue(treated as little-endian) to FixLenBytes.
284    ///
285    /// * inputs: Slice representing the byte array.
286    /// * LEN: length of the byte array.
287    pub fn raw_to_fix_len_bytes<const LEN: usize>(
288        &self,
289        ctx: &mut Context<F>,
290        inputs: [AssignedValue<F>; LEN],
291    ) -> FixLenBytes<F, LEN> {
292        FixLenBytes::<F, LEN>::new(inputs.map(|input| self.assert_byte(ctx, input)))
293    }
294
295    /// Converts a slice of AssignedValue(treated as little-endian) to FixLenBytesVec.
296    ///
297    /// * inputs: Slice representing the byte array.
298    /// * len: length of the byte array. We enforce this to be provided explictly to make sure length of `inputs` is determinstic.
299    pub fn raw_to_fix_len_bytes_vec(
300        &self,
301        ctx: &mut Context<F>,
302        inputs: RawAssignedValues<F>,
303        len: usize,
304    ) -> FixLenBytesVec<F> {
305        FixLenBytesVec::<F>::new(
306            inputs.into_iter().map(|input| self.assert_byte(ctx, input)).collect_vec(),
307            len,
308        )
309    }
310
311    /// Assumes that `bits <= inputs.len() * 8`.
312    fn add_bytes_constraints(
313        &self,
314        ctx: &mut Context<F>,
315        inputs: &RawAssignedValues<F>,
316        bits: usize,
317    ) {
318        let mut bits_left = bits;
319        for input in inputs {
320            let num_bit = min(bits_left, BITS_PER_BYTE);
321            self.range_chip.range_check(ctx, *input, num_bit);
322            bits_left -= num_bit;
323        }
324    }
325
326    // TODO: Add comparison. e.g. is_less_than(SafeUint8, SafeUint8) -> SafeBool
327    // TODO: Add type castings. e.g. uint256 -> bytes32/uint32 -> uint64
328}
halo2_base/safe_types/mod.rs

halo2_base/safe_types/
mod.rs
