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