bp_pp/range_proof/
reciprocal.rs

1#![allow(non_snake_case)]
2
3//! Definition and implementation of the reciprocal range-proof protocol based on arithmetic circuits protocol.
4
5use std::ops::{Add, Mul};
6use k256::{AffinePoint, ProjectivePoint, Scalar};
7use k256::elliptic_curve::ops::Invert;
8use k256::elliptic_curve::rand_core::{CryptoRng, RngCore};
9use merlin::Transcript;
10use serde::{Deserialize, Serialize};
11use crate::util::*;
12use crate::{circuit, transcript};
13use crate::circuit::{ArithmeticCircuit, PartitionType};
14
15/// Represents reciprocal range-proof protocol witness.
16#[derive(Clone, Debug)]
17pub struct Witness {
18    /// Private value in range [0..dim_np^dim_nd).
19    pub x: Scalar,
20    /// Blinding value
21    pub s: Scalar,
22    /// Witness vector: value multiplicities: i-th element corresponds to the 'i-digit' multiplicity
23    pub m: Vec<Scalar>,
24    /// Witness vector: value digits.
25    pub digits: Vec<Scalar>,
26}
27
28/// Represents reciprocal range-proof: zk-proof that committed value lies in [0..dim_np^dim_nd) range.
29#[derive(Clone, Debug)]
30pub struct Proof {
31    pub circuit_proof: circuit::Proof,
32    pub r: ProjectivePoint,
33}
34
35/// Represent serializable version of reciprocal proof (uses AffinePoint instead of ProjectivePoint
36/// and serialized version of circuit proof).
37#[derive(Serialize, Deserialize, Clone, Debug)]
38pub struct SerializableProof {
39    pub circuit_proof: circuit::SerializableProof,
40    pub r: AffinePoint,
41}
42
43impl From<&SerializableProof> for Proof {
44    fn from(value: &SerializableProof) -> Self {
45        Proof {
46            circuit_proof: circuit::Proof::from(&value.circuit_proof),
47            r: ProjectivePoint::from(value.r),
48        }
49    }
50}
51
52impl From<&Proof> for SerializableProof {
53    fn from(value: &Proof) -> Self {
54        SerializableProof {
55            circuit_proof: circuit::SerializableProof::from(&value.circuit_proof),
56            r: value.r.to_affine(),
57        }
58    }
59}
60
61/// Represents public reciprocal range proof protocol information. Using this information and challenge
62/// both prover and verifier can derive the arithmetic circuit.
63#[derive(Clone, Debug)]
64pub struct ReciprocalRangeProofProtocol {
65    /// Count of private proles (size of committed value). Equals to: `dim_nm`. Also, `dim_nv = 1 + dim_nd`.
66    pub dim_nd: usize,
67    /// Count of public poles (number system base). Equals to: `dim_no`.
68    pub dim_np: usize,
69
70    /// Will be used for the value commitment: `commitment = x*g + s*h_vec[0]`
71    pub g: ProjectivePoint,
72
73    /// Dimension: `dim_nm`
74    pub g_vec: Vec<ProjectivePoint>,
75    /// Will be used for the value commitment: `commitment = x*g + s*h_vec[0]`
76    /// Dimension: `dim_nv+9`
77    pub h_vec: Vec<ProjectivePoint>,
78
79    /// Additional points to be used in WNLA.
80    /// Dimension: `2^n - dim_nm`
81    pub g_vec_: Vec<ProjectivePoint>,
82    /// Dimension: `2^n - (dim_nv+9)`
83    pub h_vec_: Vec<ProjectivePoint>,
84}
85
86impl ReciprocalRangeProofProtocol {
87    /// Creates commitment for the private value and blinding: `commitment = x*g + s*h_vec[0]`
88    pub fn commit_value(&self, x: &Scalar, s: &Scalar) -> ProjectivePoint {
89        self.g.mul(x).add(&self.h_vec[0].mul(s))
90    }
91
92    /// Creates commitment for the reciprocals and blinding: `commitment = s*h_vec[0] + <r, h_vec[9:]>`
93    pub fn commit_poles(&self, r: &[Scalar], s: &Scalar) -> ProjectivePoint {
94        self.h_vec[0].mul(s).add(&vector_mul(&self.h_vec[9..], r))
95    }
96
97    /// Verifies zk-proof that committed value lies in [0..dim_np^dim_nd) range.
98    pub fn verify(&self, commitment: &ProjectivePoint, proof: Proof, t: &mut Transcript) -> bool {
99        transcript::app_point(b"reciprocal_commitment", commitment, t);
100        let e = transcript::get_challenge(b"reciprocal_challenge", t);
101
102        let circuit = self.make_circuit(e);
103
104        let circuit_commitment = commitment.add(&proof.r);
105
106        circuit.verify(&[circuit_commitment], t, proof.circuit_proof)
107    }
108
109    /// Creates zk-proof that committed value lies in [0..dim_np^dim_nd) range.
110    pub fn prove<R>(&self, commitment: &ProjectivePoint, witness: Witness, t: &mut Transcript, rng: &mut R) -> Proof
111        where
112            R: RngCore + CryptoRng
113    {
114        transcript::app_point(b"reciprocal_commitment", commitment, t);
115        let e = transcript::get_challenge(b"reciprocal_challenge", t);
116
117        let r = (0..self.dim_nd).map(|i|
118            witness.digits[i].add(&e).invert().unwrap()
119        ).collect::<Vec<Scalar>>();
120
121        let r_blind = Scalar::generate_biased(rng);
122        let r_com = self.commit_poles(&r, &r_blind);
123
124        let mut v = vec![witness.x];
125        r.iter().for_each(|r_val| v.push(*r_val));
126
127        let w_l = witness.digits;
128        let w_r = r;
129        let w_o = witness.m;
130
131        let circuit = self.make_circuit(e);
132
133        let circuit_witness = circuit::Witness {
134            v: vec![v],
135            s_v: vec![witness.s.add(r_blind)],
136            w_l,
137            w_r,
138            w_o,
139        };
140
141        let circuit_commitment = circuit.commit(&circuit_witness.v[0], &circuit_witness.s_v[0]);
142        Proof {
143            circuit_proof: circuit.prove::<R>(&[circuit_commitment], circuit_witness, t, rng),
144            r: r_com,
145        }
146    }
147
148    /// Creates circuit parameters based on provided challenge. For the same challenge will generate same parameters.
149    #[inline(always)]
150    pub fn make_circuit(&self, e: Scalar) -> ArithmeticCircuit<impl Fn(PartitionType, usize) -> Option<usize> + '_>
151    {
152        let dim_nm = self.dim_nd;
153        let dim_no = self.dim_np;
154
155        let dim_nv = self.dim_nd + 1;
156        let dim_nl = dim_nv;
157        let dim_nw = self.dim_nd * 2 + self.dim_np;
158
159        let a_m = vec![Scalar::ONE; dim_nm];
160
161        let mut W_m = vec![vec![Scalar::ZERO; dim_nw]; dim_nm];
162        (0..dim_nm).for_each(|i| W_m[i][i + dim_nm] = minus(&e));
163
164        let a_l = vec![Scalar::ZERO; dim_nl];
165        let base = Scalar::from(self.dim_np as u32);
166
167        let mut W_l = vec![vec![Scalar::ZERO; dim_nw]; dim_nl];
168
169        // fill for v-part in w vector
170        (0..dim_nm).for_each(|i| W_l[0][i] = minus(&pow(&base, i)));
171
172        // fill for r-part in w vector
173        (0..dim_nm).for_each(|i|
174            (0..dim_nm).for_each(|j| W_l[i + 1][j + dim_nm] = Scalar::ONE)
175        );
176
177        (0..dim_nm).for_each(|i| W_l[i + 1][i + dim_nm] = Scalar::ZERO);
178
179        (0..dim_nm).for_each(|i|
180            (0..dim_no).for_each(|j|
181                W_l[i + 1][j + 2 * dim_nm] = minus(&(e.add(Scalar::from(j as u32)).invert_vartime().unwrap()))
182            )
183        );
184
185        // partition function -> map all to ll
186        let partition = |typ: PartitionType, index: usize| -> Option<usize>{
187            if typ == PartitionType::LL && index < self.dim_np {
188                Some(index)
189            } else {
190                None
191            }
192        };
193
194        ArithmeticCircuit {
195            dim_nm,
196            dim_no,
197            k: 1,
198            dim_nl,
199            dim_nv,
200            dim_nw,
201            g: self.g,
202            g_vec: self.g_vec.clone(),
203            h_vec: self.h_vec.clone(),
204            W_m,
205            W_l,
206            a_m,
207            a_l,
208            f_l: true,
209            f_m: false,
210            g_vec_: self.g_vec_.clone(),
211            h_vec_: self.h_vec_.clone(),
212            partition,
213        }
214    }
215}
216
217
bp_pp/range_proof/reciprocal.rs

bp_pp/range_proof/
reciprocal.rs
