arkworks_small_values_ops/
ops.rs

1use std::ops::Mul;
2
3use ark_ff::PrimeField;
4use ark_r1cs_std::{eq::EqGadget, fields::fp::FpVar};
5use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
6
7use crate::{
8    common::{enforce_zero, get_slack},
9    enforce_in_binary_bound,
10};
11
12/// Computes the minimum of two field elements `a` and `b` using slack variables to ensure that the
13/// result is correct without directly comparing the two values.
14///
15/// `a` and `b` must be in the range [0, 1 << `BITS`). `BITS` must be strictly less than the floor
16/// of log2 of the field's modulus.
17pub fn min<F: PrimeField, const BITS: usize>(
18    cs: ConstraintSystemRef<F>,
19    a: &FpVar<F>,
20    b: &FpVar<F>,
21) -> Result<FpVar<F>, SynthesisError> {
22    assert!(BITS < (F::MODULUS_BIT_SIZE - 1) as usize);
23    let (_undr, over) = get_under_and_over_checked::<F, BITS>(cs, a, b)?;
24    Ok(a - over)
25}
26
27/// Computes the maximum of two field elements `a` and `b` using slack variables to ensure that the
28/// result is correct without directly comparing the two values.
29///
30/// `a` and `b` must be in the range [0, 1 << `BITS`). `BITS` must be strictly less than the floor
31/// of log2 of the field's modulus.
32pub fn max<F: PrimeField, const BITS: usize>(
33    cs: ConstraintSystemRef<F>,
34    a: &FpVar<F>,
35    b: &FpVar<F>,
36) -> Result<FpVar<F>, SynthesisError> {
37    assert!(BITS < (F::MODULUS_BIT_SIZE - 1) as usize);
38    let (undr, _over) = get_under_and_over_checked::<F, BITS>(cs, a, b)?;
39    Ok(a + undr)
40}
41
42/// Computes the absolute difference between two field elements `a` and `b` using slack variables
43/// to ensure that the result is correct without directly comparing the two values.
44///
45/// `a` and `b` must be in the range [0, 1 << `BITS`). `BITS` must be strictly less than the floor
46/// of log2 of the field's modulus.
47pub fn abs_diff<F: PrimeField, const BITS: usize>(
48    cs: ConstraintSystemRef<F>,
49    a: &FpVar<F>,
50    b: &FpVar<F>,
51) -> Result<FpVar<F>, SynthesisError> {
52    assert!(BITS < (F::MODULUS_BIT_SIZE - 1) as usize);
53    let (undr, over) = get_under_and_over_checked::<F, BITS>(cs, a, b)?;
54    Ok(undr + over)
55}
56
57fn get_under_and_over_checked<F: PrimeField, const BITS: usize>(
58    cs: ConstraintSystemRef<F>,
59    a: &FpVar<F>,
60    b: &FpVar<F>,
61) -> Result<(FpVar<F>, FpVar<F>), SynthesisError> {
62    let over = get_slack(cs.clone(), b, a)?;
63    let undr = get_slack(cs.clone(), a, b)?;
64
65    // (1) Ensure that `over` and `undr` are within [0, 1 << BITS)
66    enforce_in_binary_bound::<_, BITS>(&over)?;
67    enforce_in_binary_bound::<_, BITS>(&undr)?;
68
69    // (2) Ensure that `over` and `undr` are mutually exclusive
70    enforce_zero(&over.clone().mul(&undr))?;
71
72    // (3) Check the balance condition
73    (a + &undr).enforce_equal(&(b + &over))?;
74
75    Ok((undr, over))
76}
77
78#[cfg(test)]
79mod tests {
80    use ark_bn254::Fr;
81    use ark_r1cs_std::{R1CSVar, alloc::AllocVar, fields::fp::FpVar};
82    use ark_relations::r1cs::ConstraintSystem;
83
84    use super::*;
85
86    fn run<const BITS: usize>(a: u64, b: u64) -> Result<(), SynthesisError> {
87        let cs = ConstraintSystem::<Fr>::new_ref();
88        let a_var = FpVar::new_witness(cs.clone(), || Ok(Fr::from(a)))?;
89        let b_var = FpVar::new_witness(cs.clone(), || Ok(Fr::from(b)))?;
90
91        let min_result = min::<_, BITS>(cs.clone(), &a_var, &b_var)?;
92        assert_eq!(min_result.value()?, Fr::from(a.min(b)));
93
94        let max_result = max::<_, BITS>(cs.clone(), &a_var, &b_var)?;
95        assert_eq!(max_result.value()?, Fr::from(a.max(b)));
96
97        let abs_diff_result = abs_diff::<_, BITS>(cs.clone(), &a_var, &b_var)?;
98        assert_eq!(abs_diff_result.value()?, Fr::from(a.abs_diff(b)));
99
100        Ok(())
101    }
102
103    #[test]
104    fn test() -> Result<(), SynthesisError> {
105        // Small values
106        run::<3>(3, 5)?;
107        run::<3>(5, 3)?;
108
109        // Equal values
110        run::<3>(5, 5)?;
111
112        // Zero values
113        run::<3>(0, 5)?;
114        run::<3>(5, 0)?;
115        run::<3>(0, 0)?;
116
117        // Larger values
118        run::<64>(123456789, 234567890)?;
119
120        Ok(())
121    }
122}
arkworks_small_values_ops/ops.rs

arkworks_small_values_ops/
ops.rs
