1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the alphavm library.
  3  
  4  // Licensed under the Apache License, Version 2.0 (the "License");
  5  // you may not use this file except in compliance with the License.
  6  // You may obtain a copy of the License at:
  7  
  8  // http://www.apache.org/licenses/LICENSE-2.0
  9  
 10  // Unless required by applicable law or agreed to in writing, software
 11  // distributed under the License is distributed on an "AS IS" BASIS,
 12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  // See the License for the specific language governing permissions and
 14  // limitations under the License.
 15  
 16  use super::*;
 17  
 18  impl<E: Environment> Add<Self> for Group<E> {
 19      type Output = Self;
 20  
 21      fn add(self, other: Self) -> Self::Output {
 22          self + &other
 23      }
 24  }
 25  
 26  impl<E: Environment> Add<&Self> for Group<E> {
 27      type Output = Self;
 28  
 29      fn add(self, other: &Self) -> Self::Output {
 30          // If `self` is constant *and* `self` is zero, then return `other`.
 31          if self.is_constant() && self.eject_value().is_zero() {
 32              other.clone()
 33          }
 34          // If `other` is constant *and* `other` is zero, then return `self`.
 35          else if other.is_constant() && other.eject_value().is_zero() {
 36              self
 37          }
 38          // Otherwise, compute the sum of `self` and `other`.
 39          else {
 40              // This swap reduces the number of constants by one.
 41              let (this, that) = match other.is_constant() {
 42                  true => (&self, other),
 43                  false => (other, &self),
 44              };
 45  
 46              let a = Field::constant(console::Field::new(E::EDWARDS_A));
 47              let d = Field::constant(console::Field::new(E::EDWARDS_D));
 48  
 49              // Compute U = (-A * x1 + y1) * (x2 + y2)
 50              let u1 = (&this.x * &-&a) + &this.y;
 51              let u2 = &that.x + &that.y;
 52              let u = u1 * u2;
 53  
 54              // Compute v0 = x1 * y2
 55              let v0 = &this.x * &that.y;
 56  
 57              // Compute v1 = x2 * y1
 58              let v1 = &that.x * &this.y;
 59  
 60              // Compute v2 = d * v0 * v1
 61              let v2 = (&v0 * &v1) * d;
 62  
 63              // Compute x3 and y3.
 64              let (x3, y3) = witness!(|a, u, v0, v1, v2| {
 65                  // Assign x3 = (v0 + v1) / (v2 + 1).
 66                  let x3 = (v0 + v1) / (v2 + console::Field::one());
 67                  // Assign y3 = (U + a * v0 - v1) / (1 - v2).
 68                  let y3 = (u + (v0 * a) - v1) / (console::Field::one() - v2);
 69                  // Return (x3, y3).
 70                  (x3, y3)
 71              });
 72  
 73              // Ensure x3 is well-formed.
 74              // x3 * (v2 + 1) = v0 + v1
 75              let v2_plus_one = &v2 + &Field::one();
 76              let v0_plus_v1 = &v0 + &v1;
 77              E::enforce(|| (&x3, v2_plus_one, v0_plus_v1));
 78  
 79              // Ensure y3 is well-formed.
 80              // y3 * (1 - v2) = u + (a * v0) - v1
 81              let one_minus_v2 = Field::one() - v2;
 82              let a_v0 = v0 * a;
 83              let u_plus_a_v0_minus_v1 = u + a_v0 - v1;
 84              E::enforce(|| (&y3, one_minus_v2, u_plus_a_v0_minus_v1));
 85  
 86              Self { x: x3, y: y3 }
 87          }
 88      }
 89  }
 90  
 91  impl<E: Environment> Add<&Group<E>> for &Group<E> {
 92      type Output = Group<E>;
 93  
 94      fn add(self, other: &Group<E>) -> Self::Output {
 95          (*self).clone() + other
 96      }
 97  }
 98  
 99  impl<E: Environment> AddAssign<Self> for Group<E> {
100      fn add_assign(&mut self, other: Self) {
101          *self += &other;
102      }
103  }
104  
105  impl<E: Environment> AddAssign<&Self> for Group<E> {
106      fn add_assign(&mut self, other: &Self) {
107          *self = self.clone() + other;
108      }
109  }
110  
111  impl<E: Environment> Metrics<dyn Add<Group<E>, Output = Group<E>>> for Group<E> {
112      type Case = (Mode, Mode);
113  
114      fn count(case: &Self::Case) -> Count {
115          match (case.0, case.1) {
116              (Mode::Constant, Mode::Constant) => Count::less_than(4, 0, 0, 0),
117              (Mode::Constant, _) | (_, Mode::Constant) => Count::is(2, 0, 3, 3),
118              (_, _) => Count::is(2, 0, 6, 6),
119          }
120      }
121  }
122  
123  impl<E: Environment> OutputMode<dyn Add<Group<E>, Output = Group<E>>> for Group<E> {
124      type Case = (Mode, Mode);
125  
126      // TODO: This implementation is incorrect. In the case where one operand is a constant and is equal to zero, then the output mode
127      //  is that of the other operand.
128      fn output_mode(case: &Self::Case) -> Mode {
129          match (case.0, case.1) {
130              (Mode::Constant, Mode::Constant) => Mode::Constant,
131              (_, _) => Mode::Private,
132          }
133      }
134  }
135  
136  #[cfg(test)]
137  mod tests {
138      use super::*;
139      use alphavm_circuit_environment::Circuit;
140  
141      const ITERATIONS: u64 = 100;
142  
143      fn check_add(
144          name: &str,
145          expected: &console::Group<<Circuit as Environment>::Network>,
146          a: &Group<Circuit>,
147          b: &Group<Circuit>,
148      ) {
149          Circuit::scope(name, || {
150              let candidate = a + b;
151              assert_eq!(*expected, candidate.eject_value(), "({} + {})", a.eject_value(), b.eject_value());
152              assert_count!(Add(Group, Group) => Group, &(a.eject_mode(), b.eject_mode()));
153              assert_output_mode!(Add(Group, Group) => Group, &(a.eject_mode(), b.eject_mode()), candidate);
154          });
155      }
156  
157      fn check_add_assign(
158          name: &str,
159          expected: &console::Group<<Circuit as Environment>::Network>,
160          a: &Group<Circuit>,
161          b: &Group<Circuit>,
162      ) {
163          Circuit::scope(name, || {
164              let mut candidate = a.clone();
165              candidate += b;
166              assert_eq!(*expected, candidate.eject_value(), "({} + {})", a.eject_value(), b.eject_value());
167              assert_count!(Add(Group, Group) => Group, &(a.eject_mode(), b.eject_mode()));
168              assert_output_mode!(Add(Group, Group) => Group, &(a.eject_mode(), b.eject_mode()), candidate);
169          });
170      }
171  
172      fn run_test(mode_a: Mode, mode_b: Mode) {
173          let mut rng = TestRng::default();
174  
175          for i in 0..ITERATIONS {
176              let first = Uniform::rand(&mut rng);
177              let second = Uniform::rand(&mut rng);
178  
179              let a = Group::<Circuit>::new(mode_a, first);
180              let b = Group::<Circuit>::new(mode_b, second);
181  
182              let expected = first + second;
183  
184              let name = format!("Add: a + b {i}");
185              check_add(&name, &expected, &a, &b);
186              let name = format!("AddAssign: a + b {i}");
187              check_add_assign(&name, &expected, &a, &b);
188          }
189      }
190  
191      #[test]
192      fn test_constant_plus_constant() {
193          run_test(Mode::Constant, Mode::Constant);
194      }
195  
196      #[test]
197      fn test_constant_plus_public() {
198          run_test(Mode::Constant, Mode::Public);
199      }
200  
201      #[test]
202      fn test_public_plus_constant() {
203          run_test(Mode::Public, Mode::Constant);
204      }
205  
206      #[test]
207      fn test_constant_plus_private() {
208          run_test(Mode::Constant, Mode::Private);
209      }
210  
211      #[test]
212      fn test_private_plus_constant() {
213          run_test(Mode::Private, Mode::Constant);
214      }
215  
216      #[test]
217      fn test_public_plus_public() {
218          run_test(Mode::Public, Mode::Public);
219      }
220  
221      #[test]
222      fn test_public_plus_private() {
223          run_test(Mode::Public, Mode::Private);
224      }
225  
226      #[test]
227      fn test_private_plus_public() {
228          run_test(Mode::Private, Mode::Public);
229      }
230  
231      #[test]
232      fn test_private_plus_private() {
233          run_test(Mode::Private, Mode::Private);
234      }
235  
236      #[test]
237      fn test_add_matches() {
238          let mut rng = TestRng::default();
239  
240          // Sample two random elements.
241          let a = Uniform::rand(&mut rng);
242          let b = Uniform::rand(&mut rng);
243          let expected = a + b;
244  
245          // Constant
246          let first = Group::<Circuit>::new(Mode::Constant, a);
247          let second = Group::<Circuit>::new(Mode::Constant, b);
248          let candidate_a = first + second;
249          assert_eq!(expected, candidate_a.eject_value());
250  
251          // Private
252          let first = Group::<Circuit>::new(Mode::Private, a);
253          let second = Group::<Circuit>::new(Mode::Private, b);
254          let candidate_b = first + second;
255          assert_eq!(expected, candidate_b.eject_value());
256      }
257  }