ark_r1cs_std/
select.rs

1use crate::prelude::*;
2use ark_ff::Field;
3use ark_relations::r1cs::SynthesisError;
4use ark_std::vec::Vec;
5/// Generates constraints for selecting between one of two values.
6pub trait CondSelectGadget<ConstraintF: Field>: Sized + Clone {
7    /// If `cond == &Boolean::TRUE`, then this returns `true_value`; else,
8    /// returns `false_value`.
9    ///
10    /// # Note
11    /// `Self::conditionally_select(cond, true_value, false_value)?` can be more
12    /// succinctly written as `cond.select(&true_value, &false_value)?`.
13    fn conditionally_select(
14        cond: &Boolean<ConstraintF>,
15        true_value: &Self,
16        false_value: &Self,
17    ) -> Result<Self, SynthesisError>;
18
19    /// Returns an element of `values` whose index in represented by `position`.
20    /// `position` is an array of boolean that represents an unsigned integer in
21    /// big endian order.
22    ///
23    /// # Example
24    /// To get the 6th element of `values`, convert unsigned integer 6 (`0b110`)
25    /// to `position = [True, True, False]`,
26    /// and call `conditionally_select_power_of_two_vector(position, values)`.
27    fn conditionally_select_power_of_two_vector(
28        position: &[Boolean<ConstraintF>],
29        values: &[Self],
30    ) -> Result<Self, SynthesisError> {
31        let m = values.len();
32        let n = position.len();
33
34        // Assert m is a power of 2, and n = log(m)
35        assert!(m.is_power_of_two());
36        assert_eq!(1 << n, m);
37
38        let mut cur_mux_values = values.to_vec();
39
40        // Traverse the evaluation tree from bottom to top in level order traversal.
41        // This is method 5.1 from https://github.com/mir-protocol/r1cs-workshop/blob/master/workshop.pdf
42        // TODO: Add method 5.2/5.3
43        for i in 0..n {
44            // Size of current layer.
45            let cur_size = 1 << (n - i);
46            assert_eq!(cur_mux_values.len(), cur_size);
47
48            let mut next_mux_values = Vec::new();
49            for j in (0..cur_size).step_by(2) {
50                let cur = Self::conditionally_select(
51                    &position[n - 1 - i],
52                    // true case
53                    &cur_mux_values[j + 1],
54                    // false case
55                    &cur_mux_values[j],
56                )?;
57                next_mux_values.push(cur);
58            }
59            cur_mux_values = next_mux_values;
60        }
61
62        Ok(cur_mux_values[0].clone())
63    }
64}
65
66/// Performs a lookup in a 4-element table using two bits.
67pub trait TwoBitLookupGadget<ConstraintF: Field>: Sized {
68    /// The type of values being looked up.
69    type TableConstant;
70
71    /// Interprets the slice `bits` as a two-bit integer `b = bits[0] + (bits[1]
72    /// << 1)`, and then outputs `constants[b]`.
73    ///
74    /// For example, if `bits == [0, 1]`, and `constants == [0, 1, 2, 3]`, this
75    /// method should output a variable corresponding to `2`.
76    ///
77    /// # Panics
78    ///
79    /// This method panics if `bits.len() != 2` or `constants.len() != 4`.
80    fn two_bit_lookup(
81        bits: &[Boolean<ConstraintF>],
82        constants: &[Self::TableConstant],
83    ) -> Result<Self, SynthesisError>;
84}
85
86/// Uses three bits to perform a lookup into a table, where the last bit
87/// conditionally negates the looked-up value.
88pub trait ThreeBitCondNegLookupGadget<ConstraintF: Field>: Sized {
89    /// The type of values being looked up.
90    type TableConstant;
91
92    /// Interprets the slice `bits` as a two-bit integer `b = bits[0] + (bits[1]
93    /// << 1)`, and then outputs `constants[b] * c`, where `c = if bits[2] {
94    /// -1 } else { 1 };`.
95    ///
96    /// That is, `bits[2]` conditionally negates the looked-up value.
97    ///
98    /// For example, if `bits == [1, 0, 1]`, and `constants == [0, 1, 2, 3]`,
99    /// this method should output a variable corresponding to `-1`.
100    ///
101    /// # Panics
102    ///
103    /// This method panics if `bits.len() != 3` or `constants.len() != 4`.
104    fn three_bit_cond_neg_lookup(
105        bits: &[Boolean<ConstraintF>],
106        b0b1: &Boolean<ConstraintF>,
107        constants: &[Self::TableConstant],
108    ) -> Result<Self, SynthesisError>;
109}
ark_r1cs_std/select.rs

ark_r1cs_std/
select.rs
