1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  use super::*;
 20  
 21  impl<E: Environment> Elligator2<E> {
 22      /// Returns the encoded affine group element and sign, given a field element.
 23      pub fn encode(input: &Field<E>) -> Result<(Group<E>, bool)> {
 24          // Compute the encoding of the input field element.
 25          let (encoding, sign_high) = Self::encode_without_cofactor_clear(input)?;
 26  
 27          // Cofactor clear the twisted Edwards element (x, y).
 28          let group = encoding.mul_by_cofactor().to_affine();
 29          ensure!(group.is_on_curve(), "Elligator2 failed: element is not on curve");
 30          ensure!(group.is_in_correct_subgroup_assuming_on_curve(), "Elligator2 failed: element in incorrect subgroup");
 31  
 32          Ok((Group::new(group), sign_high))
 33      }
 34  
 35      /// Returns the encoded affine group element and sign, given a field element.
 36      pub(crate) fn encode_without_cofactor_clear(input: &Field<E>) -> Result<(Group<E>, bool)> {
 37          ensure!(
 38              Group::<E>::EDWARDS_D.legendre().is_qnr(),
 39              "D on the twisted Edwards curve must be a quadratic nonresidue"
 40          );
 41          ensure!(!input.is_zero(), "Inputs to Elligator2 must be nonzero (inverses will fail)");
 42  
 43          let one = Field::<E>::one();
 44  
 45          // Store the sign of the input, to be returned with the output.
 46          let sign_high = input > &input.neg();
 47  
 48          // Compute the mapping from Fq to E(Fq) as a Montgomery element (u, v).
 49          let (u, v) = {
 50              // Compute the coefficients for the Weierstrass form: y^2 == x^3 + A * x^2 + B * x.
 51              let (a, b) = match Group::<E>::MONTGOMERY_B.inverse() {
 52                  Ok(b_inverse) => (Group::MONTGOMERY_A * b_inverse, b_inverse.square()),
 53                  Err(_) => bail!("Montgomery B must be invertible in order to use Elligator2"),
 54              };
 55  
 56              // Let (u, r) = (D, input).
 57              let (u, r) = (Group::EDWARDS_D, input);
 58  
 59              // Let ur2 = u * r^2;
 60              let ur2 = u * r.square();
 61  
 62              // Ensure A^2 * ur^2 != B(1 + ur^2)^2.
 63              ensure!(a.square() * ur2 != b * (one + ur2).square(), "Elligator2 failed: A^2 * ur^2 == B(1 + ur^2)^2");
 64  
 65              // Let v = -A / (1 + ur^2).
 66              let v = -a * (one + ur2).inverse().map_err(|_| anyhow!("Elligator2 failed: (1 + ur^2) == 0"))?;
 67  
 68              // Ensure v is nonzero.
 69              ensure!(!v.is_zero(), "Elligator2 failed: v == 0");
 70  
 71              // Let e = legendre(v^3 + Av^2 + Bv).
 72              let v2 = v.square();
 73              let e = ((v2 * v) + (a * v2) + (b * v)).legendre();
 74  
 75              // Ensure e is nonzero.
 76              ensure!(!e.is_zero(), "Elligator2 failed: e == 0");
 77  
 78              // Let x = ev - ((1 - e) * A/2).
 79              let x = match e {
 80                  LegendreSymbol::Zero => -a * Field::<E>::half(),
 81                  LegendreSymbol::QuadraticResidue => v,
 82                  LegendreSymbol::QuadraticNonResidue => -v - a,
 83              };
 84  
 85              // Ensure x is nonzero.
 86              ensure!(!x.is_zero(), "Elligator2 failed: x == 0");
 87  
 88              // Let y = -e * sqrt(x^3 + Ax^2 + Bx).
 89              let x2 = x.square();
 90              let rhs = (x2 * x) + (a * x2) + (b * x);
 91              let value =
 92                  rhs.even_square_root().map_err(|_| anyhow!("Elligator2 failed: even_sqrt(x^3 + Ax^2 + Bx) failed"))?;
 93  
 94              let y = match e {
 95                  LegendreSymbol::Zero => Field::<E>::zero(),
 96                  LegendreSymbol::QuadraticResidue => -value,
 97                  LegendreSymbol::QuadraticNonResidue => value,
 98              };
 99  
100              // Ensure y is nonzero.
101              ensure!(!y.is_zero(), "Elligator2 failed: y == 0");
102  
103              // Ensure (x, y) is a valid Weierstrass element on: y^2 == x^3 + A * x^2 + B * x.
104              ensure!(y.square() == rhs, "Elligator2 failed: y^2 != x^3 + A * x^2 + B * x");
105  
106              // Convert the Weierstrass element (x, y) to Montgomery element (u, v).
107              let u = x * Group::MONTGOMERY_B;
108              let v = y * Group::MONTGOMERY_B;
109  
110              // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u
111              let u2 = u.square();
112              ensure!(
113                  Group::MONTGOMERY_B * v.square() == (u2 * u) + (Group::MONTGOMERY_A * u2) + u,
114                  "Elligator2 failed: B * v^2 != u^3 + A * u^2 + u"
115              );
116  
117              (u, v)
118          };
119  
120          // Convert the Montgomery element (u, v) to the twisted Edwards element (x, y).
121          let x = u * v.inverse().map_err(|_| anyhow!("Elligator2 failed: v == 0"))?;
122          let y = (u - one) * (u + one).inverse().map_err(|_| anyhow!("Elligator2 failed: (u + 1) == 0"))?;
123  
124          // Recover the point from the twisted Edwards element (x, y).
125          let point = Group::from_xy_coordinates_unchecked(x, y);
126          // Ensure the recovered point is on the curve.
127          ensure!(point.to_affine().is_on_curve(), "Elligator2 failed: point is not on the curve");
128          // Return the recovered point.
129          Ok((point, sign_high))
130      }
131  }