arcis_compiler/utils/zkp/range_proof/
mod.rs

1//! Arcis implementation of https://github.com/solana-program/zk-elgamal-proof/blob/main/zk-sdk/src/range_proof/mod.rs
2
3use crate::{
4    core::{
5        circuits::boolean::{boolean_value::BooleanValue, byte::Byte},
6        global_value::{
7            curve_value::{CompressedCurveValue, CurveValue},
8            value::FieldValue,
9        },
10    },
11    traits::{GetBit, Invert, Reveal, Select, ToLeBytes},
12    utils::{
13        field::ScalarField,
14        zkp::{
15            generators::RangeProofGens,
16            inner_product::InnerProductProof,
17            pedersen::{Pedersen, PedersenOpening},
18            transcript::Transcript,
19            util::{self, UNIT_LEN},
20        },
21    },
22};
23use std::{iter, sync::LazyLock};
24use zk_elgamal_proof::encryption::pedersen::H;
25
26pub mod batched_range_proof;
27pub mod batched_range_proof_u128;
28pub mod batched_range_proof_u64;
29
30#[allow(non_snake_case, dead_code)]
31#[derive(Debug, Clone)]
32pub struct RangeProof {
33    /// A commitment to the bit-vectors `a_L` and `a_R`.
34    pub(crate) A: CompressedCurveValue, // 32 bytes
35    /// A commitment to the blinding vectors `s_L` and `s_R`.
36    pub(crate) S: CompressedCurveValue, // 32 bytes
37    /// A commitment to the `t_1` coefficient of the polynomial `t(x)`.
38    pub(crate) T_1: CompressedCurveValue, // 32 bytes
39    /// A commitment to the `t_2` coefficient of the polynomial `t(x)`.
40    pub(crate) T_2: CompressedCurveValue, // 32 bytes
41    /// The evaluation of the polynomial `t(x)` at the challenge point `x`.
42    pub(crate) t_x: FieldValue<ScalarField>, // 32 bytes
43    /// The blinding factor for the `t_x` value.
44    pub(crate) t_x_blinding: FieldValue<ScalarField>, // 32 bytes
45    /// The blinding factor for the synthetic commitment to `l(x)` and `r(x)`.
46    pub(crate) e_blinding: FieldValue<ScalarField>, // 32 bytes
47    /// The inner product proof.
48    pub(crate) ipp_proof: InnerProductProof, // 448 bytes for withdraw; 512 for transfer
49}
50
51#[allow(non_snake_case)]
52impl RangeProof {
53    /// Creates an aggregated range proof for a set of values that are committed to a set of
54    /// Pedersen commitments.
55    ///
56    /// This function implements the aggregated proof generation logic from Section 4.3
57    /// of the Bulletproofs paper. It allows proving that multiple values are in their
58    /// respective ranges, creating one proof that is much smaller than the sum of
59    /// individual proofs.
60    ///
61    /// # Panics
62    /// This function will panic if the `openings` vector does not contain the same number
63    /// of elements as the `amounts` and `bit_lengths` vectors.
64    pub fn new(
65        amounts: Vec<FieldValue<ScalarField>>,
66        bit_lengths: Vec<usize>,
67        openings: Vec<&PedersenOpening>,
68        transcript: &mut Transcript<BooleanValue>,
69    ) -> Self {
70        // 1. Validate inputs
71        let m = amounts.len();
72        assert!(bit_lengths.len() == m && openings.len() == m);
73
74        // each bit length must be greater than 0 for the proof to make sense
75        assert!(bit_lengths
76            .iter()
77            .all(|bit_length| { *bit_length > 0 && *bit_length <= u64::BITS as usize }));
78
79        // total vector dimension to compute the ultimate inner product proof for
80        let nm: usize = bit_lengths.iter().sum();
81        assert!(nm.is_power_of_two());
82
83        let bp_gens = RangeProofGens::new(nm);
84
85        transcript.range_proof_domain_separator(nm as u64);
86
87        // 2. Create commitments A and S.
88        // A is a commitment to the bit-vectors a_L and a_R
89        let a_blinding = FieldValue::<ScalarField>::random();
90        let arcis_H = CurveValue::from(*LazyLock::force(&H));
91        let mut A = a_blinding * arcis_H;
92
93        let mut gens_iter = bp_gens.G(nm).zip(bp_gens.H(nm));
94        for (amount_i, n_i) in amounts.iter().zip(bit_lengths.iter()) {
95            for j in 0..(*n_i) {
96                let (G_ij, H_ij) = gens_iter.next().unwrap();
97                let v_ij = amount_i.get_bit(j, false);
98                let mut point = -*H_ij;
99                // Add G_ij if bit is 1, else do nothing (since a_R = a_L - 1)
100                point = v_ij.select(*G_ij, point);
101                A += point;
102            }
103        }
104        let A = A.reveal().compress();
105
106        // generate blinding factors and generate their Pedersen vector commitment
107        let s_L = (0..nm)
108            .map(|_| FieldValue::<ScalarField>::random())
109            .collect::<Vec<FieldValue<ScalarField>>>();
110        let s_R = (0..nm)
111            .map(|_| FieldValue::<ScalarField>::random())
112            .collect::<Vec<FieldValue<ScalarField>>>();
113
114        // generate blinding factor for Pedersen commitment; `s_blinding` should not to be confused
115        // with blinding factors for the actual inner product vector
116        let s_blinding = FieldValue::<ScalarField>::random();
117
118        let S = CurveValue::multiscalar_mul(
119            iter::once(&s_blinding)
120                .chain(s_L.iter())
121                .chain(s_R.iter())
122                .copied()
123                .collect::<Vec<FieldValue<ScalarField>>>(),
124            iter::once(&arcis_H)
125                .chain(bp_gens.G(nm))
126                .chain(bp_gens.H(nm))
127                .copied()
128                .collect::<Vec<CurveValue>>(),
129        )
130        .reveal()
131        .compress();
132
133        // 3. Derive challenges y and z.
134        transcript.append_point(b"A", &A);
135        transcript.append_point(b"S", &S);
136
137        let y = transcript.challenge_scalar(b"y");
138        let z = transcript.challenge_scalar(b"z");
139
140        // 4. Construct the blinded vector polynomials l(x) and r(x). l(x) = (a_L - z*1) + s_L*x
141        //    r(x) = y^nm o (a_R + z*1 + s_R*x) + (z^2*2^n_1 || ... || z^{m+1}*2^n_m) where `o` is
142        //    the Hadamard product and `||` is vector concatenation.
143        let mut l_poly = util::VecPoly1::zero(nm);
144        let mut r_poly = util::VecPoly1::zero(nm);
145
146        let mut i = 0;
147        let mut exp_z = z * z;
148        let mut exp_y = FieldValue::<ScalarField>::from(1);
149
150        for (amount_i, n_i) in amounts.iter().zip(bit_lengths.iter()) {
151            let mut exp_2 = FieldValue::<ScalarField>::from(1);
152
153            for j in 0..(*n_i) {
154                let a_L_j = FieldValue::<ScalarField>::from(amount_i.get_bit(j, false));
155                let a_R_j = a_L_j - FieldValue::<ScalarField>::from(1);
156
157                l_poly.0[i] = a_L_j - z;
158                l_poly.1[i] = s_L[i];
159                r_poly.0[i] = exp_y * (a_R_j + z) + exp_z * exp_2;
160                r_poly.1[i] = exp_y * s_R[i];
161
162                exp_y *= y;
163                exp_2 = exp_2 + exp_2;
164
165                // `i` is capped by the sum of vectors in `bit_lengths`
166                i = i.checked_add(1).unwrap();
167            }
168            exp_z *= z;
169        }
170
171        // 5. Compute the inner product polynomial t(x) = <l(x), r(x)>.
172        let t_poly = l_poly.inner_product(&r_poly).unwrap();
173
174        // 6. Commit to the t_1 and t_2 coefficients of t(x).
175        let (T_1, t_1_blinding) = Pedersen::new(t_poly.1);
176        let (T_2, t_2_blinding) = Pedersen::new(t_poly.2);
177
178        let T_1 = T_1.get_point().reveal().compress();
179        let T_2 = T_2.get_point().reveal().compress();
180
181        transcript.append_point(b"T_1", &T_1);
182        transcript.append_point(b"T_2", &T_2);
183
184        // 7. Derive challenge x and compute openings.
185        let x = transcript.challenge_scalar(b"x");
186
187        // Compute the aggregated blinding factor for all value commitments.
188        let mut agg_opening = FieldValue::<ScalarField>::from(0);
189        let mut exp_z = z;
190        for opening in openings {
191            exp_z *= z;
192            agg_opening += exp_z * *opening.get_scalar();
193        }
194
195        let t_blinding_poly = util::Poly2(
196            agg_opening,
197            *t_1_blinding.get_scalar(),
198            *t_2_blinding.get_scalar(),
199        );
200
201        let t_x = t_poly.eval(x).reveal();
202        let t_x_blinding = t_blinding_poly.eval(x).reveal();
203
204        transcript.append_scalar(b"t_x", &t_x);
205        transcript.append_scalar(b"t_x_blinding", &t_x_blinding);
206
207        // homomorphically compuate the openings for A + x*S
208        let e_blinding = (a_blinding + s_blinding * x).reveal();
209
210        // 8. Finally, create the inner product proof.
211        let l_vec = l_poly.eval(x);
212        let r_vec = r_poly.eval(x);
213
214        transcript.append_scalar(b"e_blinding", &e_blinding);
215
216        // compute the inner product argument on the commitment:
217        // P = <l(x), G> + <r(x), H'> + <l(x), r(x)>*Q
218        let w = transcript.challenge_scalar(b"w");
219        let Q = w * CurveValue::generator();
220
221        let G_factors = iter::repeat_n(FieldValue::<ScalarField>::from(1), nm)
222            .collect::<Vec<FieldValue<ScalarField>>>();
223        // on plaintext values we simply set is_expected_non_zero = true
224        let H_factors = util::exp_iter(y.invert(true))
225            .take(nm)
226            .collect::<Vec<FieldValue<ScalarField>>>();
227
228        // this variable exists for backwards compatibility
229        let _c = transcript.challenge_scalar(b"c");
230
231        let ipp_proof = InnerProductProof::new(
232            &Q,
233            &G_factors,
234            &H_factors,
235            bp_gens.G(nm).cloned().collect(),
236            bp_gens.H(nm).cloned().collect(),
237            l_vec,
238            r_vec,
239            transcript,
240        );
241
242        // compute challenge `d` for consistency with the verifier
243        transcript.append_scalar(b"ipp_a", &ipp_proof.a);
244        transcript.append_scalar(b"ipp_b", &ipp_proof.b);
245        let _d = transcript.challenge_scalar(b"d");
246
247        RangeProof {
248            A,
249            S,
250            T_1,
251            T_2,
252            t_x,
253            t_x_blinding,
254            e_blinding,
255            ipp_proof,
256        }
257    }
258
259    pub fn to_bytes(&self) -> Vec<Byte<BooleanValue>> {
260        let mut buf = Vec::with_capacity(7 * UNIT_LEN + self.ipp_proof.serialized_size());
261        buf.extend_from_slice(&self.A.to_bytes());
262        buf.extend_from_slice(&self.S.to_bytes());
263        buf.extend_from_slice(&self.T_1.to_bytes());
264        buf.extend_from_slice(&self.T_2.to_bytes());
265        buf.extend_from_slice(&self.t_x.to_le_bytes());
266        buf.extend_from_slice(&self.t_x_blinding.to_le_bytes());
267        buf.extend_from_slice(&self.e_blinding.to_le_bytes());
268        buf.extend_from_slice(&self.ipp_proof.to_bytes());
269        buf
270    }
271}
arcis_compiler/utils/zkp/range_proof/mod.rs

arcis_compiler/utils/zkp/range_proof/
mod.rs
