// Copyright 2018 POA Networks Ltd. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. use super::proof_of_time::{iterate_squarings, serialize}; use classgroup::{gmp_classgroup::GmpClassGroup, BigNum, BigNumExt, ClassGroup}; use sha2::{digest::FixedOutput, Digest, Sha256}; use std::{cmp::Eq, collections::HashMap, hash::Hash, mem, u64, usize}; use std::convert::TryInto; #[derive(Debug, Clone)] pub struct WesolowskiVDF { int_size_bits: u16, } use super::InvalidIterations as Bad; #[derive(Clone, Copy, Eq, PartialEq, PartialOrd, Ord, Hash, Debug)] pub struct WesolowskiVDFParams(pub u16); impl super::VDFParams for WesolowskiVDFParams { type VDF = WesolowskiVDF; fn new(self) -> Self::VDF { WesolowskiVDF { int_size_bits: self.0, } } } impl super::VDF for WesolowskiVDF { fn check_difficulty(&self, _difficulty: u64) -> Result<(), Bad> { Ok(()) } fn solve(&self, challenge: &[u8], difficulty: u64) -> Result<Vec<u8>, Bad> { if difficulty > usize::MAX as u64 { Err(Bad("Cannot have more that usize::MAX iterations".to_owned())) } else { Ok(create_proof_of_time_wesolowski::< <GmpClassGroup as ClassGroup>::BigNum, GmpClassGroup, >( challenge, difficulty as usize, self.int_size_bits )) } } fn verify( &self, challenge: &[u8], difficulty: u64, alleged_solution: &[u8], ) -> Result<(), super::InvalidProof> { check_proof_of_time_wesolowski::<<GmpClassGroup as ClassGroup>::BigNum, GmpClassGroup>( challenge, alleged_solution, difficulty, self.int_size_bits, ) .map_err(|()| super::InvalidProof) } } /// To quote the original Python code: /// /// > Create `L` and `k` parameters from papers, based on how many iterations /// > need to be performed, and how much memory should be used. pub fn approximate_parameters(t: f64) -> (usize, u8, u64) { let log_memory = (10_000_000.0f64).log2(); let log_t = (t as f64).log2(); let l = if log_t - log_memory > 0. { 2.0f64.powf(log_memory - 20.).ceil() } else { 1. }; let intermediate = t * (2.0f64).ln() / (2.0 * l); let k = (intermediate.ln() - intermediate.ln().ln() + 0.25) .round() .max(1.); let w = (t / (t / k + l * (2.0f64).powf(k + 1.0)) - 2.0).floor(); (l as _, k as _, w as _) } fn u64_to_bytes(q: u64) -> [u8; 8] { if false { // This use of `std::mem::transumte` is correct, but still not justified. unsafe { std::mem::transmute(q.to_be()) } } else { [ (q >> 56) as u8, (q >> 48) as u8, (q >> 40) as u8, (q >> 32) as u8, (q >> 24) as u8, (q >> 16) as u8, (q >> 8) as u8, q as u8, ] } } /// Quote: /// /// > Creates a random prime based on input s. fn hash_prime<T: BigNum>(seed: &[&[u8]], t: u32) -> T { let mut j = 0u64; loop { let mut hasher = Sha256::new(); hasher.input(b"prime"); hasher.input(u64_to_bytes(j)); for i in seed { hasher.input(i); } hasher.input(t.to_be_bytes()); let n = T::from(&hasher.fixed_result()[..16]); if n.probab_prime(1) { break n; } j += 1; } } /// Quote: /// /// > Get“s the ith block of `2^T // B`, such that `sum(get_block(i) * 2^(k*i)) /// > = t^T // B` fn get_block<T: BigNumExt>(i: u64, k: u8, t: u64, b: &T) -> T { let mut res = T::from(0); let two = T::from(2); res.mod_powm(&two, &T::from(t - u64::from(k) * (i + 1)), b); res *= &((two >> 1) << (k as usize)); res / b } fn eval_optimized<T, U: BigNumExt, L: ClassGroup<BigNum = U> + Eq + Hash>( h: &L, b: &U, t: usize, k: u8, l: usize, powers: &T, ) -> L where T: for<'a> std::ops::Index<&'a u64, Output = L>, { assert!(k > 0, "k cannot be zero"); assert!(l > 0, "l cannot be zero"); let kl = (k as usize) .checked_mul(l) .expect("computing k*l overflowed a u64"); assert!(kl <= u64::MAX as _); assert!((kl as u64) < (1u64 << 53), "k*l overflowed an f64"); assert!((t as u64) < (1u64 << 53), "t overflows an f64"); assert!( k < (mem::size_of::<usize>() << 3) as u8, "k must be less than the number of bits in a usize" ); let k1 = k >> 1; let k0 = k - k1; let mut x = h.identity(); let identity = h.identity(); let k_exp = 1usize << k; let k0_exp = 1usize << k0; let k1_exp = 1usize << k1; for j in (0..l).rev() { x.pow(U::from(k_exp as u64)); let mut ys: HashMap<U, L> = HashMap::new(); for b in 0..1usize << k { ys.entry(U::from(b as u64)) .or_insert_with(|| identity.clone()); } let end_of_loop = ((t as f64) / kl as f64).ceil() as usize; assert!(end_of_loop == 0 || (end_of_loop as u64 - 1).checked_mul(l as u64).is_some()); for i in 0..end_of_loop { if t < k as usize * (i * l + j + 1) { continue; } let b = get_block((i as u64) * (l as u64), k, t as _, b); *ys.get_mut(&b).unwrap() *= &powers[&((i * kl) as _)]; } for b1 in 0..k1_exp { let mut z = identity.clone(); for b0 in 0..k0_exp { z *= &ys[&U::from((b1 * k0_exp + b0) as u64)] } z.pow(U::from((b1 as u64) * (k0_exp as u64))); x *= &z; } for b0 in 0..k0_exp { let mut z = identity.clone(); for b1 in 0..k1_exp { z *= &ys[&U::from((b1 * k0_exp + b0) as u64)]; } z.pow(U::from(b0 as u64)); x *= &z; } } x } pub fn generate_proof<U, T: BigNumExt, V: ClassGroup<BigNum = T> + Eq + Hash>( x: &V, iterations: u64, k: u8, l: usize, powers: &U, int_size_bits: usize, ) -> V where U: for<'a> std::ops::Index<&'a u64, Output = V>, { let element_len = 2 * ((int_size_bits + 16) >> 4); let mut x_buf = vec![0; element_len]; x.serialize(&mut x_buf[..]) .expect(super::INCORRECT_BUFFER_SIZE); let mut y_buf = vec![0; element_len]; powers[&iterations] .serialize(&mut y_buf[..]) .expect(super::INCORRECT_BUFFER_SIZE); let b = hash_prime( &[&x_buf[..], &y_buf[..]], iterations.try_into().expect("iterations fit into u32") ); eval_optimized(&x, &b, iterations as _, k, l, powers) } /// Verify a proof, according to the Wesolowski paper. pub fn verify_proof<T: BigNum, V: ClassGroup<BigNum = T>>( mut x: V, y: &V, mut proof: V, t: u64, int_size_bits: usize, ) -> Result<(), ()> { let element_len = 2 * ((int_size_bits + 16) >> 4); let mut x_buf = vec![0; element_len]; x.serialize(&mut x_buf[..]) .expect(super::INCORRECT_BUFFER_SIZE); let mut y_buf = vec![0; element_len]; y.serialize(&mut y_buf[..]) .expect(super::INCORRECT_BUFFER_SIZE); let b = hash_prime( &[&x_buf[..], &y_buf[..]], t.try_into().expect("iterations fit into u32") ); let mut r = T::from(0); r.mod_powm(&T::from(2u64), &T::from(t), &b); proof.pow(b); x.pow(r); proof *= &x; if &proof == y { Ok(()) } else { Err(()) } } pub fn create_proof_of_time_wesolowski<T: BigNumExt, V: ClassGroup<BigNum = T> + Eq + Hash>( challenge: &[u8], iterations: usize, int_size_bits: u16, ) -> Vec<u8> where for<'a, 'b> &'a V: std::ops::Mul<&'b V, Output = V>, for<'a, 'b> &'a V::BigNum: std::ops::Mul<&'b V::BigNum, Output = V::BigNum>, { let discriminant = super::create_discriminant::create_discriminant(&challenge, int_size_bits); let x = V::from_ab_discriminant(2.into(), 1.into(), discriminant); assert!((iterations as u128) < (1u128 << 53)); let (l, k, _) = approximate_parameters(iterations as f64); let q = l.checked_mul(k as _).expect("bug"); let powers = iterate_squarings( x.clone(), (0..=iterations / q + 1) .map(|i| i * q) .chain(Some(iterations)) .map(|x| x as _), ); let proof = generate_proof(&x, iterations as _, k, l, &powers, int_size_bits.into()); serialize(&[proof], &powers[&(iterations as _)], int_size_bits.into()) } pub fn check_proof_of_time_wesolowski<T: BigNum, V: ClassGroup<BigNum = T>>( challenge: &[u8], proof_blob: &[u8], iterations: u64, int_size_bits: u16, ) -> Result<(), ()> where T: BigNumExt, { let discriminant: T = super::create_discriminant::create_discriminant(challenge, int_size_bits); let x = V::from_ab_discriminant(2.into(), 1.into(), discriminant.clone()); if (usize::MAX - 16) < int_size_bits.into() { return Err(()); } let int_size = (usize::from(int_size_bits) + 16) >> 4; if int_size * 4 != proof_blob.len() { return Err(()); } let (result_bytes, proof_bytes) = proof_blob.split_at(2 * int_size); let proof = ClassGroup::from_bytes(proof_bytes, discriminant.clone()); let y = ClassGroup::from_bytes(result_bytes, discriminant); verify_proof(x, &y, proof, iterations, int_size_bits.into()) }