hash_to_curve.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 use alphavm_console_types::prelude::AffineCurve; 18 19 impl Blake2Xs { 20 /// Runs hash-to-curve and returns the generator, message, and counter on success. 21 #[inline] 22 pub fn hash_to_curve<G: AffineCurve>(input: &str) -> (G, String, usize) { 23 // Attempt to increment counter `k` at most `8 * G::SERIALIZED_SIZE` times. 24 for k in 0..128 { 25 // Construct a new message. 26 let message = format!("{input} in {k}"); 27 28 // Output the generator if a valid generator was found. 29 if let Some(g) = Self::try_hash_to_curve::<G>(&message) { 30 return (g, message, k); 31 } 32 } 33 34 // Panic with probability 2^-128. 35 panic!("Unable to hash to curve on {input}") 36 } 37 38 /// Evaluates **one** round of hash-to-curve and returns a generator on success. 39 #[inline] 40 fn try_hash_to_curve<G: AffineCurve>(input: &str) -> Option<G> { 41 let serialized_size = G::prime_subgroup_generator().compressed_size(); 42 43 // Compute the digest for sampling the generator. 44 let digest = Self::evaluate(input.as_bytes(), u16::try_from(serialized_size).unwrap(), "AlpHtC00".as_bytes()); 45 debug_assert!(digest.len() == serialized_size); // Attempt to use the digest to derive a generator. 46 G::from_random_bytes(&digest).and_then(|g| { 47 debug_assert!(g.is_on_curve()); 48 49 let g = g.mul_by_cofactor(); 50 debug_assert!(g.is_on_curve()); 51 debug_assert!(g.is_in_correct_subgroup_assuming_on_curve()); 52 53 (!g.is_zero()).then_some(g) 54 }) 55 } 56 } 57 58 #[cfg(test)] 59 mod bls12_377_g1 { 60 use super::*; 61 use alphavm_curves::bls12_377::G1Affine; 62 use alphavm_fields::PrimeField; 63 use alphavm_utilities::{BigInteger384, CanonicalSerialize}; 64 65 #[test] 66 fn hash_bls12_377_g1() { 67 let g1 = Blake2Xs::try_hash_to_curve::<G1Affine>("Alpha BLS12-377 G1 in 0").unwrap(); 68 assert!(g1.is_on_curve()); 69 assert!(g1.is_in_correct_subgroup_assuming_on_curve()); 70 assert_eq!(g1.compressed_size(), 384 / 8); 71 assert_eq!( 72 Blake2Xs::hash_to_curve::<G1Affine>("Alpha BLS12-377 G1"), 73 (g1, "Alpha BLS12-377 G1 in 0".to_string(), 0) 74 ); 75 76 // String representation 77 assert_eq!( 78 g1.x.to_string(), 79 "89363714989903307245735717098563574705733591463163614225748337416674727625843187853442697973404985688481508350822", 80 ); 81 assert_eq!( 82 g1.y.to_string(), 83 "3702177272937190650578065972808860481433820514072818216637796320125658674906330993856598323293086021583822603349", 84 ); 85 86 // BigInteger representation 87 assert_eq!( 88 g1.x.to_bigint(), 89 BigInteger384::new([ 90 1089863619676461926, 91 2031922408020517912, 92 7605803015099675459, 93 5499508099818543095, 94 11627353473000952893, 95 41837199143568307 96 ]) 97 ); 98 assert_eq!( 99 g1.y.to_bigint(), 100 BigInteger384::new([ 101 8946822147630122069, 102 11486725844942458959, 103 17739430126876114892, 104 5672784675232650440, 105 942928816728936680, 106 1733239579958889 107 ]) 108 ); 109 110 // Montgomery BigInteger representation 111 assert_eq!( 112 g1.x.0, 113 BigInteger384::new([ 114 1171681672315280277, 115 6528257384425852712, 116 7514971432460253787, 117 2032708395764262463, 118 12876543207309632302, 119 107509843840671767 120 ]) 121 ); 122 assert_eq!( 123 g1.y.0, 124 BigInteger384::new([ 125 13572190014569192121, 126 15344828677741220784, 127 17067903700058808083, 128 10342263224753415805, 129 1083990386877464092, 130 21335464879237822 131 ]) 132 ); 133 134 // Check that G1Affine matches. 135 assert_eq!(G1Affine::prime_subgroup_generator(), g1); 136 } 137 } 138 139 #[cfg(test)] 140 mod bls12_377_g2 { 141 use super::*; 142 use alphavm_curves::bls12_377::G2Affine; 143 use alphavm_fields::PrimeField; 144 use alphavm_utilities::{BigInteger384, CanonicalSerialize}; 145 146 #[test] 147 fn hash_bls12_377_g2() { 148 let g2 = Blake2Xs::try_hash_to_curve::<G2Affine>("Alpha BLS12-377 G2 in 6").unwrap(); 149 assert!(g2.is_on_curve()); 150 assert!(g2.is_in_correct_subgroup_assuming_on_curve()); 151 assert_eq!(g2.compressed_size(), 2 * 384 / 8); 152 assert_eq!( 153 Blake2Xs::hash_to_curve::<G2Affine>("Alpha BLS12-377 G2"), 154 (g2, "Alpha BLS12-377 G2 in 6".to_string(), 6), 155 ); 156 157 // String representation 158 assert_eq!( 159 g2.x.to_string(), 160 "Fp2(170590608266080109581922461902299092015242589883741236963254737235977648828052995125541529645051927918098146183295 + 83407003718128594709087171351153471074446327721872642659202721143408712182996929763094113874399921859453255070254 * u)", 161 ); 162 assert_eq!( 163 g2.y.to_string(), 164 "Fp2(1843833842842620867708835993770650838640642469700861403869757682057607397502738488921663703124647238454792872005 + 33145532013610981697337930729788870077912093258611421158732879580766461459275194744385880708057348608045241477209 * u)", 165 ); 166 167 // BigInteger representation 168 assert_eq!( 169 g2.x.c0.to_bigint(), 170 BigInteger384::new([ 171 6285382596397680767, 172 15748827462709656851, 173 12106939604663586443, 174 15333984969116343459, 175 5478119782678835813, 176 79865001705186672 177 ]) 178 ); 179 assert_eq!( 180 g2.x.c1.to_bigint(), 181 BigInteger384::new([ 182 16087313950742852142, 183 593255854261604337, 184 1941199260866950545, 185 10849744434273544618, 186 2633370935305329371, 187 39048459712288691 188 ]) 189 ); 190 assert_eq!( 191 g2.y.c0.to_bigint(), 192 BigInteger384::new([ 193 7702421029866889285, 194 16004466681641276576, 195 106615717155384672, 196 763522394023763305, 197 16530696304726864408, 198 863223330401754 199 ]) 200 ); 201 assert_eq!( 202 g2.y.c1.to_bigint(), 203 BigInteger384::new([ 204 14642269910726223961, 205 418400088670236579, 206 13367772290999385514, 207 12034951455731096578, 208 1807164704891090155, 209 15517665349181582 210 ]) 211 ); 212 213 // Montgomery BigInteger representation 214 assert_eq!( 215 g2.x.c0.0, 216 BigInteger384::new([ 217 1394603105513884269, 218 11069732150289508451, 219 4261960060090787184, 220 13457254148541472797, 221 3177258746859163322, 222 82258727112085846 223 ]) 224 ); 225 assert_eq!( 226 g2.x.c1.0, 227 BigInteger384::new([ 228 12672065269715576738, 229 3451530808602826578, 230 9486610028138952262, 231 5031487885431614078, 232 9858745210421513581, 233 63301617551232910 234 ]) 235 ); 236 assert_eq!( 237 g2.y.c0.0, 238 BigInteger384::new([ 239 1855632670224768760, 240 2989378521406112342, 241 9748867374972564648, 242 3204895972998458874, 243 16520689795595505429, 244 61918742406142643 245 ]) 246 ); 247 assert_eq!( 248 g2.y.c1.0, 249 BigInteger384::new([ 250 1532128906028652860, 251 14539073382194201855, 252 10828918286556702479, 253 14664598863867299115, 254 483199896405477997, 255 73741830940675480 256 ]) 257 ); 258 259 // Check that G2Affine matches. 260 assert_eq!(G2Affine::prime_subgroup_generator(), g2); 261 } 262 } 263 264 #[cfg(test)] 265 mod edwards_bls12 { 266 use super::*; 267 use alphavm_curves::edwards_bls12::EdwardsAffine; 268 use alphavm_fields::PrimeField; 269 use alphavm_utilities::{BigInteger256, CanonicalSerialize}; 270 271 #[test] 272 fn hash_edwards_bls12() { 273 let group = Blake2Xs::try_hash_to_curve::<EdwardsAffine>("Alpha Edwards BLS12 in 4").unwrap(); 274 assert!(group.is_on_curve()); 275 assert!(group.is_in_correct_subgroup_assuming_on_curve()); 276 assert_eq!(group.compressed_size(), 256 / 8); 277 assert_eq!( 278 Blake2Xs::hash_to_curve::<EdwardsAffine>("Alpha Edwards BLS12"), 279 (group, "Alpha Edwards BLS12 in 4".to_string(), 4) 280 ); 281 282 // String representation 283 assert_eq!(group.x.to_string(), "1540945439182663264862696551825005342995406165131907382295858612069623286213",); 284 assert_eq!(group.y.to_string(), "8003546896475222703853313610036801932325312921786952001586936882361378122196",); 285 286 // BigInteger representation 287 assert_eq!( 288 group.x.to_bigint(), 289 BigInteger256::new([1404703638504229317, 16672475576000152563, 1635533132911366150, 245486771465834503]), 290 "\n\nExpected: {:?}\n\n", 291 group.x.to_bigint().0, 292 ); 293 assert_eq!( 294 group.y.to_bigint(), 295 BigInteger256::new([15352153743387634132, 9180404173643694677, 4017395716581932261, 1275038582114391971]), 296 "\n\nExpected: {:?}\n\n", 297 group.y.to_bigint().0, 298 ); 299 300 // Montgomery BigInteger representation 301 assert_eq!( 302 group.x.0, 303 BigInteger256::new([15976313411695170452, 17230178952810798400, 11626259175167078036, 678729006091608048]), 304 "\n\nExpected: {:?}\n\n", 305 group.x.0, 306 ); 307 assert_eq!( 308 group.y.0, 309 BigInteger256::new([926786653590077393, 18147000980977651608, 13077459464847727671, 1231472949076376191]), 310 "\n\nExpected: {:?}\n\n", 311 group.y.0, 312 ); 313 314 // Check that EdwardsAffine matches. 315 assert_eq!(EdwardsAffine::prime_subgroup_generator(), group); 316 } 317 }