Comments (4)
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.
from class.
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)
}
}
from class.
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
- currently I use M13 prime as modulus
- currently I use Sha256
from class.
Very cool.
- RSA group should have a modulus
N=p*q
wherep,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?
from class.
Related Issues (20)
- Test results are causing errors HOT 4
- add multithreading for the ZK prover and verifcation HOT 2
- optimize compose and reduce
- Expend supported OSs and distributions
- implement Accumulator primitive
- build error HOT 12
- Implement supersonic
- Implement VDF
- benchmarks for VDF HOT 3
- Memory management : pari_init HOT 8
- Test for better VDF proof generation protocol
- Implement homomorphic time lock puzzles
- Adjust for configurable security
- implement compression technique from https://eprint.iacr.org/2020/196.pdf HOT 1
- remove redundant computation from Jacobi test
- map new relevant protocols from https://eprint.iacr.org/2020/1617.pdf
- DARK polynomial commitment upgrade
- Missing License HOT 2
- Putting class into dependencies HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from class.