1 个不稳定版本

0.1.0	2019年1月11日

#1343 in 密码学

Apache-2.0

205KB
3.5K SLoC

Rust 语言中可验证延迟函数 (VDF) 的实现

什么是 VDF？

可验证延迟函数 (VDF) 是一种需要大量时间来评估（即使使用多项式数量的并行处理器）但可以非常快速地验证为正确的函数。VDF 可以用于构建具有多种应用场景的分布式网络环境中的随机信标。通过在评估期间引入时间延迟，VDF 防止恶意行为者影响输出。直到最终结果计算出来，输出不能与随机数区分。有关更多详情，请参阅 https://eprint.iacr.org/2018/712.pdf。

描述

此 VDF 实现是用 Rust 编写的。使用 GMP 库进行算术和最大公约数 (GCD) 计算。我们使用类群来实现以下论文中描述的方法

简单可验证延迟函数. Pietrzak, 2018
高效可验证延迟函数. Wesolowski, 2018

选定的生成器是 (2, 1, c)，其中 c 由提供的判别式计算得出。内部表示形式为 (a, b, c)，其中判别式在大多数计算中未使用。此实现在每个乘法和平方操作后执行约简，因为在我们的基准测试中没有这样做并没有带来任何优势。

此仓库包含三个 crate

classgroup: 类群实现，以及类群 trait。
vdf: 可验证延迟函数 (VDF) trait，以及该 trait 的实现。
vdf-cli: vdf crate 的命令行界面。它还包括额外的命令，这些命令已弃用，将被 classgroup crate 的 CLI 替换。

用法

安装 Rust。我们（POA 网络）已使用 Rust 的最新稳定版、测试版和夜间版进行了代码测试。它可能与旧版本兼容，但这不能保证。
安装 GNU 多精度库
- 在 Debian 和其衍生版本（包括 Ubuntu）上
```
$ sudo apt-get install -y libgmp-dev
```
- 在 Red Hat 和其衍生版本（包括 Fedora、CentOS）上
```
$ sudo dnf -y install gmp-devel
```

下载并准备仓库

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

命令行界面

要启动，请使用 vdf-cli 命令并跟随 2 个参数

challenge: 任意长度的字节字符串
难度：迭代次数，每次迭代需要更多时间来评估

这生成了Weslowski时间证明。要生成Pietrzak时间证明，传递-tpietrzak。有关详细使用信息，请运行vdf-cli --help。

完成之后，您将看到输出，以Vec<u8>的形式返回。CLI工具会对其进行十六进制编码。

示例

$ vdf-cli aa 100
005271e8f9ab2eb8a2906e851dfcb5542e4173f016b85e29d481a108dc82ed3b3f97937b7aa824801138d1771dea8dae2f6397e76a80613afda30f2c30a34b040baaafe76d5707d68689193e5d211833b372a6a4591abb88e2e7f2f5a5ec818b5707b86b8b2c495ca1581c179168509e3593f9a16879620a4dc4e907df452e8dd0ffc4f199825f54ec70472cc061f22eb54c48d6aa5af3ea375a392ac77294e2d955dde1d102ae2ace494293492d31cff21944a8bcb4608993065c9a00292e8d3f4604e7465b4eeefb494f5bea102db343bb61c5a15c7bdf288206885c130fa1f2d86bf5e4634fdc4216bc16ef7dac970b0ee46d69416f9a9acee651d158ac64915b

要验证，请使用具有相同参数的vdi-cli命令，并包含输出。

示例

$ vdf-cli aa 100 005271e8f9ab2eb8a2906e851dfcb5542e4173f016b85e29d481a108dc82ed3b3f97937b7aa824801138d1771dea8dae2f6397e76a80613afda30f2c30a34b040baaafe76d5707d68689193e5d211833b372a6a4591abb88e2e7f2f5a5ec818b5707b86b8b2c495ca1581c179168509e3593f9a16879620a4dc4e907df452e8dd0ffc4f199825f54ec70472cc061f22eb54c48d6aa5af3ea375a392ac77294e2d955dde1d102ae2ace494293492d31cff21944a8bcb4608993065c9a00292e8d3f4604e7465b4eeefb494f5bea102db343bb61c5a15c7bdf288206885c130fa1f2d86bf5e4634fdc4216bc16ef7dac970b0ee46d69416f9a9acee651d158ac64915b
Proof is valid

VDF库

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());
}

基准测试

提供classgroup操作的基准测试。要运行基准测试

$ ./bench.sh <your challenge here>

还在开发额外的基准测试。

当前基准测试

这些是通过以下命令生成的：./bench.sh aadf。异常可能是由于操作系统和/或虚拟机管理程序的中断。更改与同一台机器上先前测试运行的结果相比较。由于之前的运行使用了与本报告不同的设置和/或代码，因此这些更改没有意义。

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

许可协议

根据Apache License，版本2.0（“许可协议”）；除非遵守许可协议，否则不得使用此文件。您可以在以下位置获得许可协议的副本：

https://apache.ac.cn/licenses/LICENSE-2.0

除非适用法律要求或书面同意，否则在许可协议下分发的软件按“原样”基础分发，不提供任何明示或暗示的保证或条件。有关许可协议的具体语言，请参阅许可协议。

依赖项

~1.5MB
~23K SLoC