Open omershlo opened 4 years ago
Following https://github.com/KZen-networks/class/blob/master/src/primitives/vdf.rs, I implement Wes19 using RSA group. And can try to open a PR.
/// Wes19(https://eprint.iacr.org/2018/623.pdf)-based Verifiable Delay Function (VDF) implementation,
/// adapted from https://github.com/KZen-networks/class/blob/master/src/primitives/vdf.rs
pub mod wes19 {
use rug::Integer;
use sha2::{Digest, Sha256};
/// algo_2 from the paper
pub fn verify(modulus: &Integer, seed: &Integer, t: u64, y: &Integer, pi: &Integer) -> bool {
let modulus = modulus.clone();
// g <- H_G(x)
let g = h_g(&modulus, &seed);
let l = hash_to_prime(&modulus, &g, &y);
let r = Integer::from(2).pow_mod(&Integer::from(t), &l).unwrap();
let pi_l = pi.clone().pow_mod(&l, &modulus).unwrap();
let g_r = g.clone().pow_mod(&r, &modulus).unwrap();
let pi_l_g_r = pi_l * g_r;
Integer::from(pi_l_g_r.div_rem_floor(modulus.clone()).1) == y.clone()
}
/// algo_3 from the paper
pub fn eval(modulus: &Integer, seed: &Integer, t: u64) -> (Integer, Integer) {
let modulus = modulus.clone();
// g <- H_G(x)
let g = h_g(&modulus, &seed);
// y <- (g^2)^t
let mut y = g.clone();
for _ in 0..t {
y = y.clone() * y.clone();
y = y.div_rem_floor(modulus.clone()).1;
}
let l = hash_to_prime(&modulus, &g, &y);
// algo_4 from the paper, long division
// TODO: consider algo_5 instead
let mut b: Integer;
let mut r = Integer::from(1);
let mut r2: Integer;
let two = Integer::from(2);
let mut pi = Integer::from(1);
for _ in 0..t {
r2 = r.clone() * two.clone();
b = r2.clone().div_rem_floor(l.clone()).0;
r = r2.clone().div_rem_floor(l.clone()).1;
let pi_2 = pi.clone().pow_mod(&Integer::from(2), &modulus).unwrap();
let g_b = g.clone().pow_mod(&b, &modulus).unwrap();
pi = pi_2 * g_b;
pi = Integer::from(pi.div_rem_floor(modulus.clone()).1)
}
(y, pi)
}
/// int(H("residue"||x)) mod N
fn h_g(modulus: &Integer, seed: &Integer) -> Integer {
let modulus = modulus.clone();
let mut hasher = Sha256::new();
let mut hash_input = String::from("residue");
hash_input.push_str(&seed.clone().to_string_radix(16));
hasher.update(hash_input.as_bytes());
let result_hex = hasher.finalize();
let result_hex_str = format!("{:#x}", result_hex);
let result_int = Integer::from_str_radix(&result_hex_str, 16).unwrap();
Integer::from(result_int.div_rem_floor(modulus.clone()).1)
}
// TODO: refactor to similar style in https://github.com/poanetwork/vdf/blob/master/vdf/src/proof_wesolowski.rs style
fn hash_to_prime(modulus: &Integer, x: &Integer, y: &Integer) -> Integer {
// hashing
let mut hasher = Sha256::new();
let mut hash_input: String = x.clone().to_string_radix(16);
hash_input.push_str(&y.clone().to_string_radix(16));
hasher.update(hash_input.as_bytes());
let hashed_hex = hasher.finalize();
let hashed_hex_str = format!("{:#x}", hashed_hex);
let hashed_int = Integer::from_str_radix(&hashed_hex_str, 16).unwrap();
Integer::from(hashed_int.next_prime().div_rem_floor(modulus.clone()).1)
}
}
And can try to open a PR.
Maybe after adding all alternatives using RSA group? And seems I need to add an option to make group choice configurable.
BTW, I am not sure whether my following choices suffice all the use cases
Very cool.
N=p*q
where p,q
are 1024bit primes. The library supports generating such primes (see https://github.com/KZen-networks/class/blob/2a8fa3bb58a2c177ccb1a429887d680988580b68/src/primitives/cl_dl_public_setup.rs#L309) so it should be easy. The hash (I assume you mean hash to group? )- its an interesting question, what other implementations are doing?
I suggest you start a benches folder, put the code there, build a test to compare the two VDFs and make a PR. Is that doable?
I suggest you start a benches folder, put the code there, build a test to compare the two VDFs and make a PR. Is that doable?
I was struggling on the code structures and how to support configurable types. You suggestion makes things easier. No problem! I will work on it.
use https://github.com/KZen-networks/rust-paillier for Paillier or use a standard crypto library for RSA.