1个不稳定版本

0.1.0	2019年1月11日

#680 在数学

103 每月下载次数
用于 2 工具

Apache-2.0

120KB
2.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：类群实现，以及类群特质。
vdf：可验证延迟函数（VDF）特质，以及该特质的实现。
vdf-cli：vdf crate的命令行界面。它还包括其他命令，这些命令已被弃用，并将被classgroup crate的CLI替换。

用法

安装 Rust。我们（POA Networks）已经使用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：任意长度的字节字符串
difficulty：迭代次数，每次迭代需要更多时间来评估

这会生成 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());
}

基准测试

提供了类群操作的基准测试。要运行基准测试

$ ./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 许可证 2.0 版（“许可证”）；除非您遵守许可证规定，否则不得使用此文件。您可以在以下位置获取许可证副本：

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

除非适用法律要求或经书面同意，否则在许可证下分发的软件按“原样”基础分发，不提供任何明示或暗示的保证或条件。有关许可证中规定的特定语言的权限和限制，请参阅许可证。