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 decoded field element, given the encoded affine group element and sign.
 23      pub fn decode(group: &Group<E>, sign_high: bool) -> Result<Field<E>> {
 24          ensure!(
 25              Group::<E>::EDWARDS_D.legendre().is_qnr(),
 26              "D on the twisted Edwards curve must be a quadratic nonresidue"
 27          );
 28          ensure!(!group.is_zero(), "Inputs to Elligator2 must be nonzero (inverses will fail)");
 29          ensure!((**group).to_affine().is_on_curve(), "Inputs to Elligator2 must be on the twisted Edwards curve");
 30  
 31          // Compute the coefficients for the Weierstrass form: v^2 == u^3 + A * u^2 + B * u.
 32          let (montgomery_b_inverse, a, b) = match Group::<E>::MONTGOMERY_B.inverse() {
 33              Ok(b_inverse) => (b_inverse, Group::MONTGOMERY_A * b_inverse, b_inverse.square()),
 34              Err(_) => bail!("Montgomery B must be invertible in order to use Elligator2"),
 35          };
 36  
 37          let (x, y) = group.to_xy_coordinates();
 38  
 39          // Ensure that x != -A.
 40          ensure!(x != -a, "Elligator2 failed: x == -A");
 41  
 42          // Ensure that if y is 0, then x is 0.
 43          if y.is_zero() {
 44              ensure!(x.is_zero(), "Elligator2 failed: y == 0 but x != 0");
 45          }
 46  
 47          // Convert the twisted Edwards element (x, y) to the Weierstrass element (u, v)
 48          let (u, v) = {
 49              let one = Field::<E>::one();
 50  
 51              let numerator = one + y;
 52              let denominator = one - y;
 53  
 54              // Compute u = (1 + y) / (1 - y).
 55              let u = numerator * denominator.inverse().map_err(|_| anyhow!("Elligator2 failed: (1 - y) == 0"))?;
 56  
 57              // Compute v = (1 + y) / ((1 - y) * x).
 58              let v =
 59                  numerator * (denominator * x).inverse().map_err(|_| anyhow!("Elligator2 failed: x * (1 - y) == 0"))?;
 60  
 61              // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u
 62              let u2 = u.square();
 63              ensure!(
 64                  Group::MONTGOMERY_B * v.square() == (u2 * u) + (Group::MONTGOMERY_A * u2) + u,
 65                  "Elligator2 failed: B * v^2 != u^3 + A * u^2 + u"
 66              );
 67  
 68              let u = u * montgomery_b_inverse;
 69              let v = v * montgomery_b_inverse;
 70  
 71              // Ensure (u, v) is a valid Weierstrass element on: v^2 == u^3 + A * u^2 + B * u
 72              let u2 = u.square();
 73              ensure!(v.square() == (u2 * u) + (a * u2) + (b * u), "Elligator2 failed: v^2 != u^3 + A * u^2 + B * u");
 74  
 75              (u, v)
 76          };
 77  
 78          // Ensure -D * u * (u + A) is a residue.
 79          let du = Group::EDWARDS_D * u;
 80          let u_plus_a = u + a;
 81          ensure!((-du * u_plus_a).legendre().is_qr(), "Elligator2 failed: -D * u * (u + A) is not a quadratic residue");
 82  
 83          let v_reconstructed = v
 84              .square()
 85              .even_square_root()
 86              .map_err(|_| anyhow!("Elligator2 failed: cannot compute the even square root for v^2"))?;
 87          let exists_in_sqrt_fq2 = v_reconstructed == v;
 88  
 89          let element = match exists_in_sqrt_fq2 {
 90              // Let element = sqrt(-u / ((u + A) * D)).
 91              true => {
 92                  -u * (u_plus_a * Group::EDWARDS_D)
 93                      .inverse()
 94                      .map_err(|_| anyhow!("Elligator2 failed: (u+A) * D == 0"))?
 95              }
 96              // Let element = sqrt(-(u + A) / Du)).
 97              false => -u_plus_a * du.inverse().map_err(|_| anyhow!("Elligator2 failed: D * u == 0"))?,
 98          }
 99          .even_square_root()
100          .map_err(|_| anyhow!("Elligator2 failed: cannot compute the even square root for the element"))?;
101  
102          match sign_high {
103              true => Ok(cmp::max(element, -element)),
104              false => Ok(cmp::min(element, -element)),
105          }
106      }
107  }
108  
109  #[cfg(test)]
110  mod tests {
111      use super::*;
112      use alphavm_console_types::environment::Console;
113  
114      type CurrentEnvironment = Console;
115  
116      pub(crate) const ITERATIONS: usize = 10000;
117  
118      #[test]
119      fn test_encode_and_decode() -> Result<()> {
120          let rng = &mut TestRng::default();
121  
122          let mut high_ctr = 0usize;
123          let mut low_ctr = 0usize;
124  
125          for _ in 0..ITERATIONS {
126              let expected = Uniform::rand(rng);
127  
128              let (encoded, sign_high) = Elligator2::<CurrentEnvironment>::encode_without_cofactor_clear(&expected)?;
129              let decoded = Elligator2::<CurrentEnvironment>::decode(&encoded, sign_high)?;
130              assert_eq!(expected, decoded);
131  
132              match sign_high {
133                  true => high_ctr += 1,
134                  false => low_ctr += 1,
135              }
136          }
137  
138          println!("Sign high: {high_ctr}, sign low: {low_ctr}");
139          Ok(())
140      }
141  
142      #[test]
143      fn test_zero_fails() {
144          let encode = Elligator2::<CurrentEnvironment>::encode(&Zero::zero());
145          assert!(encode.is_err());
146  
147          let decode = Elligator2::<CurrentEnvironment>::decode(&Zero::zero(), true);
148          assert!(decode.is_err());
149          let decode = Elligator2::<CurrentEnvironment>::decode(&Zero::zero(), false);
150          assert!(decode.is_err());
151      }
152  }