filecoin-存储证明子系统(rust-fil-proofs)[翻译]

什么是rust-fil-proofs

官网： https://github.com/filecoin-project/rust-fil-proofs

The Filecoin Proving Subsystem provides the storage proofs required by the Filecoin protocol. It is implemented entirely in Rust,
Filecoin证明子系统提供Filecoin协议所需的存储证明。它完全Rust实现，

storage-proofs is intended to serve as a reference implementation for Proof-of-Replication (PoRep), while also performing the heavy lifting for filecoin-proofs.
存储证明旨在用作复制证明（PoRep）的参考实现，同时还执行filecoin证明的繁重工作。

主要组件：

PoR（可检索性证明：Merkle包含证明）

DrgPoRep（复制的深度健壮图证明）

StackedDrgPoRep

PoSt（时空证明）

Filecoin Proofs (filecoin-proofs) A wrapper around storage-proofs, providing an FFI-exported API callable from C (and in practice called by go-filecoin via cgo). Filecoin-specific values of setup parameters are included here, and circuit parameters generated by Filecoin’s (future) trusted setup will also live here.

Filecoin Proofs（Filecoin Proofs）存储证明的包装器，提供一个可从C调用的FFI导出的API（在实践中由go Filecoin通过cgo调用）。这里包括特定于Filecoin的设置参数值，由Filecoin（将来）受信任的设置生成的电路参数也将存在于此。

Earlier in the design process, we considered implementing what has become the FPS in Go – as a wrapper around potentially multiple SNARK circuit libraries. We eventually decided to use bellman – a library developed by Zcash, which supports efficient pedersen hashing inside of SNARKs. Having made that decision, it was natural and efficient to implement the entire subsystem in Rust. We considered the benefits (self-contained codebase, ability to rely on static typing across layers) and costs (developer ramp-up, sometimes unwieldiness of borrow-checker) as part of that larger decision and determined that the overall project benefits (in particular ability to build on Zcash’s work) outweighed the costs.

在设计过程的早期，我们考虑在Go中实现FPS，作为潜在多个SNARK电路库的包装。**我们最终决定使用bellman——Zcash开发的一个库，它支持SNARKs内部高效的pedersen散列。**做了这个决定之后，在Rust中实现整个子系统是自然而有效的。我们认为这些好处（独立的代码库、跨层依赖静态类型的能力）和成本（开发人员的快速增长，有时是借阅检查器的笨拙）是这个更大决策的一部分，并确定整个项目的好处（特别是在Zcash工作基础上构建的能力）超过了成本。

We also considered whether the FPS should be implemented as a standalone binary accessed from go-filecoin either as a single-invocation CLI or as a long-running daemon process. Bundling the FPS as an FFI dependency was chosen for both the simplicity of having a Filecoin node deliverable as a single monolithic binary, and for the (perceived) relative development simplicity of the API implementation.

我们还考虑了FPS是否应该实现为一个独立的二进制文件，可以通过go filecoin进行访问，既可以作为单个调用CLI，也可以作为一个长时间运行的守护进程。选择将FPS捆绑为FFI依赖项，是因为将Filecoin节点作为单个单片二进制文件交付的简单性，以及API实现的（感知的）相对开发简单性。

However, the majority of technical problems associated with calling from Go into Rust are now solved, even while allowing for a high degree of runtime configurability.
然而，与从Go-into-Rust调用相关的大多数技术问题现在已经解决，即使允许高度的运行时可配置。

构建
NOTE: rust-fil-proofs can only be built for and run on 64-bit platforms; building will panic if the target architecture is not 64-bits.
注意：rust fil proof只能为64位平台构建和运行；如果目标架构不是64位，则构建将报错。

Optimizing for either speed or memory during replication
在复制期间优化速度或内存

While replicating and generating the Merkle Trees (MT) for the proof at the same time there will always be a time-memory trade-off to consider, we present here strategies to optimize one at the cost of the other.
在复制和生成Merkle树（MT）作为证明的同时，总是要考虑时间-内存的权衡，我们在这里提出了以牺牲另一个为代价来优化一个的策略。

• Speed 速度

One of the most computational expensive operations during replication (besides the encoding itself) is the generation of the indexes of the (expansion) parents in the Stacked graph, implemented through a Feistel cipher (used as a pseudorandom permutation). To reduce that time we provide a caching mechanism to generate them only once and reuse them throughout replication (across the different layers). Already built into the system it can be activated with the environmental variable
One of the most computational expensive operations during replication (besides the encoding itself) is the generation of the indexes of the (expansion) parents in the Stacked graph, implemented through a Feistel cipher (used as a pseudorandom permutation). To reduce that time we provide a caching mechanism to generate them only once and reuse them throughout replication (across the different layers). Already built into the system it can be activated with the environmental variable

复制过程中（除了编码本身之外）计算开销最大的操作之一是生成父级索引堆栈图（扩展），该索引是通过Feistel密码（用作伪随机置换）实现的。为了减少这一时间，我们提供了一种缓存机制，只生成一次并在复制过程中重用它们（跨不同层）。已经内置在系统中，可以使用环境变量**

FIL_PROOFS_MAXIMIZE_CACHING=1

To check that it’s working you can inspect the replication log to find using parents cache of unlimited size. As the log indicates, we don’t have a fine grain control at the moment so it either stores all parents or none. This cache can add almost an entire sector size to the memory used during replication, if you can spare it though this setting is very recommended as it has a considerable impact on replication time.
要检查它是否正常工作，可以检查复制日志以使用大小不受限制的父缓存查找。如日志所示，我们目前没有一个精细的控制，所以它要么存储所有的父，要么没有。此缓存可以将几乎整个扇区大小添加到复制过程中使用的内存中，如果您可以将其释放出来，尽管建议使用此设置，因为它对复制时间有相当大的影响。

(You can also verify if the cache is working by inspecting the time each layer takes to encode, encoding, layer: in the log, where the first two layers, forward and reverse, will take more time than the rest to populate the cache while the remaining 8 should see a considerable time drop.)
（您还可以通过检查每一层编码、编码、层所需的时间来验证缓存是否工作：在日志中，前两层正向和反向填充缓存所需的时间比其余两层要长，而其余8层则会出现相当长的时间下降。）

Speed Optimized Pedersen Hashing - we use Pedersen hashing to generate Merkle Trees and verify Merkle proofs. Batched Pedersen hashing has the property that we can pre-compute known intermediary values intrinsic to the Pedersen hashing process that will be reused across hashes in the batch. By pre-computing and cacheing these intermediary values, we decrease the runtime per Pedersen hash at the cost of increasing memory usage. We optimize for this speed-memory trade-off by varying the cache size via a Pedersen Hash parameter known as the “window-size”. This window-size parameter is configured via the pedersen_hash_exp_window_size setting in storage-proofs. By default, Bellman has a cache size of 256 values (a window-size of 8 bits), we increase the cache size to 65,536 values (a window-size of 16 bits) which results in a roughly 40% decrease in Pedersen Hash runtime at the cost of a 9% increase in memory usage. See the Pedersen cache issue for more benchmarks and expected performance
Pedersen hash 性能优化-我们使用Pedersen散列生成Merkle树并验证Merkle证明。批处理的Pedersen散列具有这样的属性：我们可以预先计算Pedersen散列过程的内部已知中介值，这些值将在批处理中的散列之间重用。通过预计算和缓存这些中间值，我们减少了每个佩德森散列的运行时，同时增加了内存使用量。我们通过一个称为“窗口大小”的Pedersen散列参数来改变缓存大小，从而优化这种速度内存权衡。此窗口大小参数是通过存储证明中的 pedersen_hash_exp_window_size 设置配置的。默认情况下，Bellman的缓存大小为256个值（窗口大小为8位），我们将缓存大小增加到65536个值（窗口大小为16位），这将导致Pedersen哈希运行时减少大约40%，而内存使用量增加了9%。请参阅Pedersen缓存问题以获取更多基准和预期的性能效果。

• 内存
  At the moment the default configuration is set to reduce memory consumption as much as possible so there’s not much to do from the user side. (We are now storing MTs on disk, which were the main source of memory consumption.) You should expect a maximum RSS between 1-2 sector sizes, if you experience peaks beyond that range please report an issue (you can check the max RSS with the /usr/bin/time -v command).
  目前，默认配置被设置为尽可能减少内存消耗，因此用户端没有太多工作要做。（我们现在正在磁盘上存储MTs，这是内存消耗的主要来源。）您应该期望最大RSS在1-2个扇区大小之间，如果您遇到超出该范围的峰值，请报告一个问题（您可以使用/usr/bin/time -v命令检查最大RSS）。

Memory Optimized Pedersen Hashing - for consumers of storage-proofs concerned with memory usage, the memory usage of Pedersen hashing can be reduced by lowering the Pederen Hash window-size parameter (i.e. its cache size). Reducing the cache size will reduce memory usage while increasing the runtime per Pedersen hash. The Pedersen Hash window-size can be changed via the setting pedersen_hash_exp_window_size in settings.rs. See the Pedersen cache issue for more benchmarks and expected performance effects.
内存优化的Pedersen哈希-对于关注内存使用的存储证明的使用者，可以通过降低Pederen哈希窗口大小参数（即其缓存大小）来减少Pedersen哈希的内存使用。减少缓存大小将减少内存使用，同时增加每个Pedersen哈希的运行时数。Pedersen Hash窗口大小可以通过设置Pedersen_Hash_exp_window_size来更改设置.rs。有关更多基准和预期性能影响，请参阅Pedersen缓存问题。

The following benchmarks were observed when running replication on 1MiB (1024 kibibytes) of data on a new m5a.2xlarge EC2 instance with 32GB of RAM for Pedersen Hash window-sizes of 16 (the current default) and 8 bits:
在一个新的m5a.2xlarge EC2实例上对1MiB（1024 kibibytes）的数据运行复制时，观察到了以下基准，对于Pedersen哈希窗口大小为16（当前默认值）和8位的32GB RAM：

$ cargo build --bin benchy --release
$ env time -v cargo run --bin benchy --release -- stacked --size=1024

window-size: 16
User time (seconds): 87.82
Maximum resident set size (kbytes): 1712320

window-size: 8
User time (seconds): 128.85
Maximum resident set size (kbytes): 1061564

Note that for a window-size of 16 bits the runtime for replication is 30% faster while the maximum RSS is about 40% higher compared to a window-size of 8 bits.
请注意，对于16位的窗口大小，复制的运行时比8位的窗口大小快30%，而最大RSS大约高40%。

Feistel

Feistel密码原理与实现
原文链接：https://blog.csdn.net/android_jiangjun/article/details/79378137

Feistel 密码结构是用于分组密码中的一种对称结构。以它的发明者 Horst Feistel 为名，而Horst Feistel 本人是一位物理学家兼密码学家，在他为 IBM 工作的时候，为Feistel 密码结构的研究奠定了基础。很多密码标准都采用了Feistel 结构，其中包括DES。

大多数分组密码的结构本质上都是基于Feistel网络结构，因此，了解Feistel密码结构对于学习分组密码算法是非常有帮助的。

分组密码（Feistel密码结构）

分组密码是将明文消息编码后的数字序列划分成长为N的分组（长为N的矢量），分别在**k=（k0,k1,…kt-1)的控制下变换成等长的输出数字序列（这个序列是长为M的向量，即输入和输出分组的长度可以不同）。它与流密码的不同在于输出的每一位数字不仅与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。分组密码的本质实际上是字长为n的数字序列的代换密码。

为保证安全性，设计的算法应当满足以下要求：

1.分组长度n要足够大，防止明文穷举攻击奏效。

2.**量要足够大（即向量k要足够长），并且尽可能消除弱的**，使所有**同等的好，防止**穷举攻击奏效。但**本身又不能过长，否则难以管理。

3.由**确定置换的算法要足够复杂，以抵抗差分攻击和线性攻击。

4.加解密运算简单且易于实现。

5.数据扩展和差错传播尽可能小。

什么是Pedersen Hash？

2019年过去了一半，它会是未来最好的一年么？
参考URL: https://www.tuoluocaijing.cn/article/detail-49313.html
Zcash - 深入浅出 Pedersen Hash/Commitment 计算
参考URL: https://www.chainnews.com/articles/179526099055.htm
什么是Pedersen Hash？
原文链接：https://blog.csdn.net/mutourend/article/details/93508243

ZCash 用 Pedersen Hash 替换掉了 SHA256。
从传统上看，Pedersen Hash 是一个存在了很多很多年的古老算法，一直被认为非常低效而已经被人遗忘。但是在 零知识证明技术 zkSNARK 中，Pedersen Hash 的构造电路却可以非常精简，性能居然出奇地好。电路规模大概只有 SHA256 的 三十分之一。