fullcodec_plonk/constraint_system/ecc/curve_addition/
variable_base_gate.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4//
5// Copyright (c) DUSK NETWORK. All rights reserved.
6
7use crate::constraint_system::ecc::WitnessPoint;
8use crate::constraint_system::TurboComposer;
9use dusk_bls12_381::BlsScalar;
10use dusk_jubjub::{JubJubAffine, JubJubExtended};
11
12impl TurboComposer {
13    /// Adds two curve points by consuming 2 gates.
14    pub fn component_add_point(
15        &mut self,
16        a: WitnessPoint,
17        b: WitnessPoint,
18    ) -> WitnessPoint {
19        // In order to verify that two points were correctly added
20        // without going over a degree 4 polynomial, we will need
21        // x_1, y_1, x_2, y_2
22        // x_3, y_3, x_1 * y_2
23
24        let x_1 = a.x;
25        let y_1 = a.y;
26        let x_2 = b.x;
27        let y_2 = b.y;
28
29        let p1 = JubJubAffine::from_raw_unchecked(
30            self.witnesses[&x_1],
31            self.witnesses[&y_1],
32        );
33
34        let p2 = JubJubAffine::from_raw_unchecked(
35            self.witnesses[&x_2],
36            self.witnesses[&y_2],
37        );
38
39        let point: JubJubAffine = (JubJubExtended::from(p1) + p2).into();
40        let x_3 = point.get_x();
41        let y_3 = point.get_y();
42
43        let x1_y2 = self.witnesses[&x_1] * self.witnesses[&y_2];
44
45        // Add the rest of the prepared points into the composer
46        let x_1_y_2 = self.append_witness(x1_y2);
47        let x_3 = self.append_witness(x_3);
48        let y_3 = self.append_witness(y_3);
49
50        // TODO encapsulate this gate addition into a generic `append` method
51        // The function must be a special case of `append_gate` because of
52        // `q_arith` and `q_variable_group_add`
53
54        self.w_l.extend(&[x_1, x_3]);
55        self.w_r.extend(&[y_1, y_3]);
56        self.w_o.extend(&[x_2, Self::constant_zero()]);
57        self.w_4.extend(&[y_2, x_1_y_2]);
58        let zeros = [BlsScalar::zero(), BlsScalar::zero()];
59
60        self.q_l.extend(&zeros);
61        self.q_r.extend(&zeros);
62        self.q_c.extend(&zeros);
63        self.q_o.extend(&zeros);
64        self.q_m.extend(&zeros);
65        self.q_4.extend(&zeros);
66        self.q_arith.extend(&zeros);
67        self.q_range.extend(&zeros);
68        self.q_logic.extend(&zeros);
69        self.q_fixed_group_add.extend(&zeros);
70        self.q_lookup.extend(&zeros);
71
72        self.q_variable_group_add.push(BlsScalar::one());
73        self.q_variable_group_add.push(BlsScalar::zero());
74
75        self.perm
76            .add_variables_to_map(x_1, y_1, x_2, y_2, self.n as usize);
77        self.n += 1;
78
79        self.perm.add_variables_to_map(
80            x_3,
81            y_3,
82            Self::constant_zero(),
83            x_1_y_2,
84            self.n as usize,
85        );
86
87        self.n += 1;
88
89        WitnessPoint { x: x_3, y: y_3 }
90    }
91}
92
93#[cfg(feature = "std")]
94#[cfg(test)]
95mod test {
96    use super::*;
97    use crate::constraint_system::helper::*;
98    use crate::constraint_system::Constraint;
99    use dusk_jubjub::{EDWARDS_D, GENERATOR, GENERATOR_EXTENDED};
100
101    /// Adds two curve points together using the classical point addition
102    /// algorithm. This method is slower than WNaf and is just meant to be the
103    /// source of truth to test the WNaf method.
104    pub fn classical_point_addition(
105        composer: &mut TurboComposer,
106        a: WitnessPoint,
107        b: WitnessPoint,
108    ) -> WitnessPoint {
109        let x1 = a.x;
110        let y1 = a.y;
111
112        let x2 = b.x;
113        let y2 = b.y;
114
115        // x1 * y2
116        let constraint = Constraint::new().mult(1).a(x1).b(y2);
117        let x1_y2 = composer.gate_mul(constraint);
118
119        // y1 * x2
120        let constraint = Constraint::new().mult(1).a(y1).b(x2);
121        let y1_x2 = composer.gate_mul(constraint);
122
123        // y1 * y2
124        let constraint = Constraint::new().mult(1).a(y1).b(y2);
125        let y1_y2 = composer.gate_mul(constraint);
126
127        // x1 * x2
128        let constraint = Constraint::new().mult(1).a(x1).b(x2);
129        let x1_x2 = composer.gate_mul(constraint);
130
131        // d x1x2 * y1y2
132        let constraint = Constraint::new().mult(EDWARDS_D).a(x1_x2).b(y1_y2);
133        let d_x1_x2_y1_y2 = composer.gate_mul(constraint);
134
135        // x1y2 + y1x2
136        let constraint = Constraint::new().left(1).right(1).a(x1_y2).b(y1_x2);
137        let x_numerator = composer.gate_add(constraint);
138
139        // y1y2 - a * x1x2 (a=-1) => y1y2 + x1x2
140        let constraint = Constraint::new().left(1).right(1).a(y1_y2).b(x1_x2);
141        let y_numerator = composer.gate_add(constraint);
142
143        // 1 + dx1x2y1y2
144        let constraint = Constraint::new().left(1).constant(1).a(d_x1_x2_y1_y2);
145        let x_denominator = composer.gate_add(constraint);
146
147        // Compute the inverse
148        let inv_x_denom = unsafe {
149            composer.evaluate_witness(&x_denominator).invert().unwrap()
150        };
151        let inv_x_denom = composer.append_witness(inv_x_denom);
152
153        // Assert that we actually have the inverse
154        // inv_x * x = 1
155        let constraint = Constraint::new()
156            .mult(1)
157            .constant(-BlsScalar::one())
158            .a(x_denominator)
159            .b(inv_x_denom);
160        composer.append_gate(constraint);
161
162        // 1 - dx1x2y1y2
163        let constraint = Constraint::new()
164            .left(-BlsScalar::one())
165            .constant(1)
166            .a(d_x1_x2_y1_y2);
167        let y_denominator = composer.gate_add(constraint);
168
169        let inv_y_denom = unsafe {
170            composer.evaluate_witness(&y_denominator).invert().unwrap()
171        };
172        let inv_y_denom = composer.append_witness(inv_y_denom);
173
174        // Assert that we actually have the inverse
175        // inv_y * y = 1
176        let constraint = Constraint::new()
177            .mult(1)
178            .constant(-BlsScalar::one())
179            .a(y_denominator)
180            .b(inv_y_denom);
181        composer.append_gate(constraint);
182
183        // We can now use the inverses
184        let constraint =
185            Constraint::new().mult(1).a(inv_x_denom).b(x_numerator);
186        let x_3 = composer.gate_mul(constraint);
187
188        let constraint =
189            Constraint::new().mult(1).a(inv_y_denom).b(y_numerator);
190        let y_3 = composer.gate_mul(constraint);
191
192        WitnessPoint { x: x_3, y: y_3 }
193    }
194
195    #[test]
196    fn test_curve_addition() {
197        gadget_tester(
198            |composer| {
199                let expected = GENERATOR_EXTENDED + GENERATOR_EXTENDED;
200
201                let point_a = composer.append_point(GENERATOR);
202                let point_b = composer.append_point(GENERATOR);
203
204                let point = composer.component_add_point(point_a, point_b);
205
206                let point2 =
207                    classical_point_addition(composer, point_a, point_b);
208
209                composer.assert_equal_point(point, point2);
210                composer.assert_equal_public_point(point, expected);
211            },
212            2000,
213        )
214        .expect("Curve addition failed");
215    }
216}
fullcodec_plonk/constraint_system/ecc/curve_addition/variable_base_gate.rs

fullcodec_plonk/constraint_system/ecc/curve_addition/
variable_base_gate.rs
