• Stars
    star
    170
  • Rank 223,357 (Top 5 %)
  • Language
    Rust
  • License
    Apache License 2.0
  • Created about 6 years ago
  • Updated over 3 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

An implementation of Verifiable Delay Functions in Rust

Verifiable Delay Function (VDF) Implementation in Rust

What is a VDF?

A Verifiable Delay Function (VDF) is a function that requires substantial time to evaluate (even with a polynomial number of parallel processors) but can be very quickly verified as correct. VDFs can be used to construct randomness beacons with multiple applications in a distributed network environment. By introducing a time delay during evaluation, VDFs prevent malicious actors from influencing output. The output cannot be differentiated from a random number until the final result is computed. See https://eprint.iacr.org/2018/712.pdf for more details.

Description

This VDF implementation is written in Rust. The GMP library is used for arithmetic and greatest common divisor (GCD) calculations. We use class groups to implement the approaches described in the following papers:

  1. Simple Verifiable Delay Functions. Pietrzak, 2018
  2. Efficient Verifiable Delay Functions. Wesolowski, 2018

The chosen generator is (2, 1, c), where c is calculated from the provided discriminant. A form is represented internally (a, b, c), with the discriminant not being used in most omputations. This implementation performs reduction is performed after every multiplication and squaring, as not doing so did not give any gains in our benchmarks.

This repo includes three crates:

  • classgroup: a class group implementation, as well as a trait for class groups.
  • vdf: a Verifyable Delay Function (VDF) trait, as well as an implementation of that trait.
  • vdf-cli: a command-line interface to the vdf crate. It also includes additional commands, which are deprecated and will be replaced by a CLI to the classgroup crate.

Usage

  • Install Rust. We (POA Networks) have tested the code with the latest stable, beta, and nightly versions of Rust. It may work with older versions, but this is not guaranteed.

  • Install the GNU Multiple Precision Library

    • On Debian and derivatives (including Ubuntu):
      $ sudo apt-get install -y libgmp-dev
    • On Red Hat and derivatives (Fedora, CentOS)
      $ sudo dnf -y install gmp-devel
  • Download and prepare the repository

    $ git clone https://github.com/poanetwork/vdf.git
    $ cargo install --path=vdf-cli
    $ # or for the competition binary
    $ cargo install --path=vdf-competition

Command Line Interface

To initiate, use the vdf-cli command followed by 2 arguments:

  • challenge: byte string of arbitrary length
  • difficulty: number of iterations, each iteration requires more time to evaluate

This generates the Weslowski proof of time. To generate the Pietrzak proof of time, pass -tpietrzak. For detailed usage information, run vdf-cli --help.

Once complete you will see the output, returned as a Vec<u8>. The CLI tool hex-encodes its output.

Example

$ vdf-cli aa 100
005271e8f9ab2eb8a2906e851dfcb5542e4173f016b85e29d481a108dc82ed3b3f97937b7aa824801138d1771dea8dae2f6397e76a80613afda30f2c30a34b040baaafe76d5707d68689193e5d211833b372a6a4591abb88e2e7f2f5a5ec818b5707b86b8b2c495ca1581c179168509e3593f9a16879620a4dc4e907df452e8dd0ffc4f199825f54ec70472cc061f22eb54c48d6aa5af3ea375a392ac77294e2d955dde1d102ae2ace494293492d31cff21944a8bcb4608993065c9a00292e8d3f4604e7465b4eeefb494f5bea102db343bb61c5a15c7bdf288206885c130fa1f2d86bf5e4634fdc4216bc16ef7dac970b0ee46d69416f9a9acee651d158ac64915b

To verify, use the vdi-cli command with the same arguments and include the output.

Example

$ vdf-cli aa 100 005271e8f9ab2eb8a2906e851dfcb5542e4173f016b85e29d481a108dc82ed3b3f97937b7aa824801138d1771dea8dae2f6397e76a80613afda30f2c30a34b040baaafe76d5707d68689193e5d211833b372a6a4591abb88e2e7f2f5a5ec818b5707b86b8b2c495ca1581c179168509e3593f9a16879620a4dc4e907df452e8dd0ffc4f199825f54ec70472cc061f22eb54c48d6aa5af3ea375a392ac77294e2d955dde1d102ae2ace494293492d31cff21944a8bcb4608993065c9a00292e8d3f4604e7465b4eeefb494f5bea102db343bb61c5a15c7bdf288206885c130fa1f2d86bf5e4634fdc4216bc16ef7dac970b0ee46d69416f9a9acee651d158ac64915b
Proof is valid

VDF Library

extern crate vdf;
use vdf::{InvalidProof, PietrzakVDFParams, VDFParams, WesolowskiVDFParams, VDF};

/// The correct solution.
const CORRECT_SOLUTION: &[u8] =
  b"\x00\x52\x71\xe8\xf9\xab\x2e\xb8\xa2\x90\x6e\x85\x1d\xfc\xb5\x54\x2e\x41\x73\xf0\x16\
  \xb8\x5e\x29\xd4\x81\xa1\x08\xdc\x82\xed\x3b\x3f\x97\x93\x7b\x7a\xa8\x24\x80\x11\x38\
  \xd1\x77\x1d\xea\x8d\xae\x2f\x63\x97\xe7\x6a\x80\x61\x3a\xfd\xa3\x0f\x2c\x30\xa3\x4b\
  \x04\x0b\xaa\xaf\xe7\x6d\x57\x07\xd6\x86\x89\x19\x3e\x5d\x21\x18\x33\xb3\x72\xa6\xa4\
  \x59\x1a\xbb\x88\xe2\xe7\xf2\xf5\xa5\xec\x81\x8b\x57\x07\xb8\x6b\x8b\x2c\x49\x5c\xa1\
  \x58\x1c\x17\x91\x68\x50\x9e\x35\x93\xf9\xa1\x68\x79\x62\x0a\x4d\xc4\xe9\x07\xdf\x45\
  \x2e\x8d\xd0\xff\xc4\xf1\x99\x82\x5f\x54\xec\x70\x47\x2c\xc0\x61\xf2\x2e\xb5\x4c\x48\
  \xd6\xaa\x5a\xf3\xea\x37\x5a\x39\x2a\xc7\x72\x94\xe2\xd9\x55\xdd\xe1\xd1\x02\xae\x2a\
  \xce\x49\x42\x93\x49\x2d\x31\xcf\xf2\x19\x44\xa8\xbc\xb4\x60\x89\x93\x06\x5c\x9a\x00\
  \x29\x2e\x8d\x3f\x46\x04\xe7\x46\x5b\x4e\xee\xfb\x49\x4f\x5b\xea\x10\x2d\xb3\x43\xbb\
  \x61\xc5\xa1\x5c\x7b\xdf\x28\x82\x06\x88\x5c\x13\x0f\xa1\xf2\xd8\x6b\xf5\xe4\x63\x4f\
  \xdc\x42\x16\xbc\x16\xef\x7d\xac\x97\x0b\x0e\xe4\x6d\x69\x41\x6f\x9a\x9a\xce\xe6\x51\
  \xd1\x58\xac\x64\x91\x5b";
fn main() {
    // The length of the prime numbers generated, in bits.
    let num_bits: u16 = 2048;

    // An instance of the VDF.  Instances can be used arbitrarily many times.
    let pietrzak_vdf = PietrzakVDFParams(num_bits).new();

    // Solve for the correct answer.  This will take a minute or two.
    assert_eq!(
        &pietrzak_vdf.solve(b"\xaa", 10000).unwrap()[..],
        CORRECT_SOLUTION
    );

    // Verify the answer.  This should be far faster (less than a second).
    assert!(pietrzak_vdf.verify(b"\xaa", 10000, CORRECT_SOLUTION).is_ok());
}

Benchmarks

Benchmarks are provided for the classgroup operations. To run benchmarks:

$ ./bench.sh <your challenge here>

Additional benchmarks are under development.

Current Benchmarks

These were generated by ./bench.sh aadf. Outliers could be due to preemption by the OS and/or hypervisor. Changes are relative to the previous test run done on the same machine. Since the previous run was done with different settings and/or code than reported here, these changes are not meaningful.

Benchmarking square with seed aadf: 512: Collecting 100 samples in estimated 5.0439 s (374k iteratio                                                                                                    square with seed aadf: 512
                        time:   [13.301 us 13.333 us 13.372 us]
                        change: [-22.286% -21.745% -21.225%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 22 outliers among 100 measurements (22.00%)
  5 (5.00%) high mild
  17 (17.00%) high severe

Benchmarking multiply with seed aadf: 512: Collecting 100 samples in estimated 5.0452 s (293k iterat                                                                                                    multiply with seed aadf: 512
                        time:   [17.219 us 17.251 us 17.287 us]
                        change: [-24.323% -23.739% -23.149%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  4 (4.00%) high mild
  6 (6.00%) high severe

Benchmarking square with seed aadf: 1024: Collecting 100 samples in estimated 5.0822 s (177k iterati                                                                                                    square with seed aadf: 1024
                        time:   [28.672 us 28.716 us 28.767 us]
                        change: [-29.947% -29.339% -28.708%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  1 (1.00%) low mild
  1 (1.00%) high mild
  6 (6.00%) high severe

Benchmarking multiply with seed aadf: 1024: Collecting 100 samples in estimated 5.0886 s (136k itera                                                                                                    multiply with seed aadf: 1024
                        time:   [37.163 us 37.207 us 37.254 us]
                        change: [-21.403% -20.750% -20.170%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  1 (1.00%) low mild
  1 (1.00%) high mild
  6 (6.00%) high severe

Benchmarking square with seed aadf: 2048: Collecting 100 samples in estimated 5.2519 s (76k iteratio                                                                                                    square with seed aadf: 2048
                        time:   [69.115 us 69.254 us 69.430 us]
                        change: [-28.091% -27.738% -27.341%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  1 (1.00%) low mild
  1 (1.00%) high mild
  6 (6.00%) high severe

Benchmarking multiply with seed aadf: 2048: Collecting 100 samples in estimated 5.0554 s (56k iterat                                                                                                    multiply with seed aadf: 2048
                        time:   [90.922 us 91.057 us 91.201 us]
                        change: [-25.236% -24.794% -24.336%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 13 outliers among 100 measurements (13.00%)
  2 (2.00%) low mild
  5 (5.00%) high mild
  6 (6.00%) high severe

License

Copyright 2018 Chia Network Inc and 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.

More Repositories

1

token-wizard

(Discontinued) TokenWizard is an DApp to create and manage crowdsale and token contracts using a simple UI
JavaScript
384
star
2

hbbft

An implementation of the paper "Honey Badger of BFT Protocols" in Rust. This is a modular library of consensus.
Rust
356
star
3

solidity-flattener

Utility to combine Solidity project to a flat file
JavaScript
326
star
4

threshold_crypto

A pairing-based threshold cryptosystem for collaborative decryption and signatures used in HoneybadgerBFT implementation
Rust
185
star
5

posdao-contracts

Smart contracts for POSDAO (Proof of Stake Decentralized Autonomous Organization consensus), a DPOS consensus implemented in Solidity and running within EVM with swappable BFT consensus
JavaScript
105
star
6

wiki

POA Library: wiki, how-to, FAQ. Includes instructions how to set-up a new network, to run a full node, connect wallets,
81
star
7

poa-network-consensus-contracts

Main repository for POADAO consensus. Includes contracts for Initial Ceremony, Governance, Management of Validators
JavaScript
67
star
8

ex_abi

The Ethereum ABI Interface
Elixir
60
star
9

poa-faucet

POA Network faucet
SCSS
57
star
10

proofofphone

KYC oracle to link your phone number and Ethereum wallet in Oracles network
JavaScript
48
star
11

blockscout-terraform

An automation framework for spinning up cloud infrastructure to run BlockScout
HCL
46
star
12

poa-chain-spec

Spec files, bootnodes, governance contracts addresses for POA Network instances: Core (live), Sokol (test), xDai
33
star
13

poa-dapps-voting

POA Network Governance Dapp
JavaScript
26
star
14

deployment-playbooks

Ansible playbooks for deployment POA Network nodes on EC2 or any Linux (Ubuntu 16.04) hosting. Includes master of ceremony, validator, bootnode, explorer, netstat roles
Shell
25
star
15

poa-popa

DApp for proof of physical address (PoPA) attestation for validators of POA Network
JavaScript
24
star
16

hydrabadger

A simple, experimental, peer-to-peer network node using the hbbft consensus algorithm which can be run as a standalone client or used as a library
Rust
22
star
17

poa-dapps-validators

DApp for a list of validators with metadata for POA Network (Core/Sokol). Validators can update metadata using DApp.
JavaScript
13
star
18

chain-explorer

Blockchain explorer
JavaScript
13
star
19

poa-netstats-agent

Netstat agent for EVM based networks
Elixir
11
star
20

poa-devops

POA Network DevOps scripts
Shell
11
star
21

website

website and documentation home of poanetwork.com
11
star
22

parity-bridge-research

Reasarch of https://github.com/paritytech/parity-bridge/
Solidity
9
star
23

poa-test-setup

Deployment of POA network in one click and e2e tests of Ceremony/Governance DApps
JavaScript
9
star
24

deployment-terraform

Ansible and Terraform deployment automation of POA clones
JavaScript
9
star
25

poa-dapps-keys-generation

POA Network keys generation Dapp
JavaScript
9
star
26

hex_fmt

Formatting and shortening byte slices as hexadecimal strings
Rust
8
star
27

poa-ballot-stats

Read POA voting records and rank voters by how many ballots they missed.
Rust
7
star
28

deployment-azure

Azure Templates for deploying POA Network to on Azure Cloud
7
star
29

cross-chain-deploy

JavaScript
6
star
30

eth-netstats

Netstats dashboard
JavaScript
6
star
31

howey-test-wizard

Howey test for blockchain tokens and crypto assets
JavaScript
5
star
32

hydrabadger-android

Mobile messenger based on hbbft consensus
JavaScript
4
star
33

poa-netstats-warehouse

Storage and data-processing companion for the poa-netstats-agent
Elixir
4
star
34

poamania-contracts

Smart contracts for POA Mania
JavaScript
4
star
35

poa-poba

DApp for proof of bank account (PoBA) attestation
JavaScript
3
star
36

poa-scripts-moc

Scripts for Master of Ceremony (MoC) to generate initial keys, distribute tokens, and misc.
JavaScript
3
star
37

eth-net-props

Get properties of EVM compatible networks
JavaScript
3
star
38

RFC

Technical write-ups that describe modifications to the Protocol, DApps, or any significant topic.
3
star
39

tokensale-right

Treasury and token contracts (right side of the bridge)
2
star
40

poa-scripts-validator

Script for validator
JavaScript
2
star
41

auto-updater-setup

How to setup parity auto-updater
2
star
42

ethgasstation-gasPrice-estimate

Python
2
star
43

poa-network-monitor

Scripts for POA network monitoring
JavaScript
2
star
44

poa-governance-notifications

A CLI tool for monitoring a blockchain for POA Network governance ballots.
Rust
2
star
45

e2e-test-token-wizard

A tool for end-to-end test the Token wizard. Based Selenium Webdriver.
JavaScript
2
star
46

e2e-blockscout

End to end tests for BlockScout https://github.com/poanetwork/blockscout
JavaScript
1
star
47

validator-node-dockerized

How to launch validator node with Docker Compose
Shell
1
star
48

poa-contract-metadata

A mapping of POA contract addresses to broadly accepted icons for those addresses.
JavaScript
1
star
49

poamania-subgraph

TypeScript
1
star
50

eth-net-intelligence-api

Netstats service
JavaScript
1
star
51

wallet

MyEtherWallet with POA Network support
JavaScript
1
star