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

arcis_compiler/utils/zkp/range_proof/
mod.rs
