encode.rs
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 encoded affine group element, given a field element. 20 /// Note: Unlike the console implementation, this function does not return the sign bit. 21 pub fn encode(input: &Field<E>) -> Group<E> { 22 // Ensure D on the twisted Edwards curve is a quadratic nonresidue. 23 debug_assert!(console::Group::<E::Network>::EDWARDS_D.legendre().is_qnr()); 24 25 // Ensure the input is nonzero. 26 E::assert_neq(input, Field::<E>::zero()); 27 28 // Define `1` as a constant. 29 let one = Field::one(); 30 31 // Define the Montgomery curve coefficients A and B. 32 let montgomery_a = Field::constant(console::Group::<E::Network>::MONTGOMERY_A); 33 let montgomery_b = Field::constant(console::Group::<E::Network>::MONTGOMERY_B); 34 let montgomery_b_inverse = montgomery_b.inverse(); 35 let montgomery_b2 = montgomery_b.square(); 36 let montgomery_b3 = &montgomery_b2 * &montgomery_b; 37 38 // Define the twisted Edwards curve coefficient D. 39 let edwards_d = Field::constant(console::Group::<E::Network>::EDWARDS_D); 40 41 // Define the coefficients for the Weierstrass form: y^2 == x^3 + A * x^2 + B * x. 42 let a = &montgomery_a * &montgomery_b_inverse; 43 let a_half = &a * Field::constant(console::Field::half()); 44 let b = montgomery_b_inverse.square(); 45 46 // Define the MODULUS_MINUS_ONE_DIV_TWO as a constant. 47 let modulus_minus_one_div_two = match E::BaseField::from_bigint(E::BaseField::modulus_minus_one_div_two()) { 48 Some(modulus_minus_one_div_two) => Field::constant(console::Field::new(modulus_minus_one_div_two)), 49 None => E::halt("Failed to initialize MODULUS_MINUS_ONE_DIV_TWO as a constant"), 50 }; 51 52 // Compute the mapping from Fq to E(Fq) as a Montgomery element (u, v). 53 let (u, v) = { 54 // Let ur2 = D * input^2; 55 let ur2 = edwards_d * input.square(); 56 let one_plus_ur2 = &one + &ur2; 57 // Verify A^2 * ur^2 != B(1 + ur^2)^2. 58 E::assert_neq(a.square() * &ur2, &b * one_plus_ur2.square()); 59 60 // Let v = -A / (1 + ur^2). 61 let v = -&a / one_plus_ur2; 62 63 // Let e = legendre(v^3 + Av^2 + Bv). 64 let v2 = v.square(); 65 let e = ((&v2 * &v) + (&a * &v2) + (&b * &v)).pow(modulus_minus_one_div_two); 66 67 // Let x = ev - ((1 - e) * A/2). 68 let x = (&e * &v) - ((&one - &e) * a_half); 69 70 // Let y = -e * sqrt(x^3 + Ax^2 + Bx). 71 let x2 = x.square(); 72 let x3 = &x2 * &x; 73 let rhs = &x3 + (&a * &x2) + (&b * &x); 74 75 // Witness the even square root of `rhs`. 76 let rhs_square_root: Field<E> = witness!(|rhs| { 77 match rhs.square_root() { 78 Ok(sqrt) => { 79 // Get the least significant bit of the square root. 80 // Note that the unwrap is safe since the number of bits is always greater than zero. 81 match *sqrt.to_bits_be().last().unwrap() { 82 // If the lsb is set, return the negated square root. 83 true => -sqrt, 84 // Otherwise, return the square root. 85 false => sqrt, 86 } 87 } 88 Err(_) => console::Field::zero(), 89 } 90 }); 91 // Verify that the square root is even. 92 // Note that the unwrap is safe since the number of bits is always greater than zero, 93 E::assert(!rhs_square_root.to_bits_be().last().unwrap()); 94 95 let y = -&e * rhs_square_root; 96 97 // Ensure v * e * x * y != 0. 98 E::assert_neq(&v * &e * &x * &y, Field::<E>::zero()); 99 100 // Ensure (x, y) is a valid Weierstrass element on: y^2 == x^3 + A * x^2 + B * x. 101 let y2 = y.square(); 102 E::assert_eq(&y2, rhs); 103 104 // Convert the Weierstrass element (x, y) to Montgomery element (u, v). 105 let u = x * &montgomery_b; 106 let v = y * &montgomery_b; 107 108 // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u 109 let u2 = &x2 * &montgomery_b2; 110 let u3 = &x3 * &montgomery_b3; 111 let v2 = &y2 * &montgomery_b3; 112 E::assert_eq(v2, u3 + (montgomery_a * u2) + &u); 113 114 (u, v) 115 }; 116 117 // Convert the Montgomery element (u, v) to the twisted Edwards element (x, y). 118 let x = &u / v; 119 let y = (&u - &one) / (u + &one); 120 121 // Recover the point and check that it is 1) on the curve, and 2) in the correct subgroup. 122 let encoding = Group::from_xy_coordinates_unchecked(x, y); 123 // Ensure the encoding is on the curve. 124 encoding.enforce_on_curve(); 125 // Cofactor clear the twisted Edwards element (x, y). 126 encoding.mul_by_cofactor() 127 } 128 } 129 130 #[cfg(test)] 131 mod tests { 132 use super::*; 133 use alphavm_circuit_types::environment::Circuit; 134 use alphavm_utilities::{TestRng, Uniform}; 135 136 const ITERATIONS: u64 = 1_000; 137 138 fn check_encode(mode: Mode, num_constants: u64, num_public: u64, num_private: u64, num_constraints: u64) { 139 let mut rng = TestRng::default(); 140 141 for _ in 0..ITERATIONS { 142 // Sample a random element. 143 let given = Uniform::rand(&mut rng); 144 145 // Compute the expected native result. 146 let (expected, _sign) = console::Elligator2::<<Circuit as Environment>::Network>::encode(&given).unwrap(); 147 148 // Initialize the input field element. 149 let input = Field::<Circuit>::new(mode, given); 150 151 // Encode the input. 152 Circuit::scope("Elligator2::encode", || { 153 let candidate = Elligator2::encode(&input); 154 assert_eq!(expected, candidate.eject_value()); 155 assert_scope!(num_constants, num_public, num_private, num_constraints); 156 }); 157 Circuit::reset(); 158 } 159 } 160 161 #[test] 162 fn test_encode_constant() { 163 check_encode(Mode::Constant, 527, 0, 0, 0); 164 } 165 166 #[test] 167 fn test_encode_public() { 168 check_encode(Mode::Public, 263, 0, 875, 880); 169 } 170 171 #[test] 172 fn test_encode_private() { 173 check_encode(Mode::Private, 263, 0, 875, 880); 174 } 175 }