![]()
散列（hash）函数是区块链所利用的技术中的最为基础的部分了，也是非常重要的部分之一。一个好的散列函数在一个密码体系中的地位也十分重要。Filecoin作为新一代的区块链，在散列函数的采用上也十分大胆。其中Posaidon就是比较新的散列算法。
![]()
![]()
散列的基本概念
![]()
IT人士对于散列（Hash）再熟悉不过了。Hash表是一种基本的数据结构，而这种数据结构是依靠hash函数来进行索引和访问的。由于Hash函数在寻址上具有很高的效率上的优势，算法复杂度基本上是O(1)。因此，Hash函数被广泛应用与数据库和其他数据处理系统中。
简单来说，散列函数就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。通常输入的数据长度要大于运算得出的散列值，同时因为这个散列值一定程度上可以代表原数据，因此也被成为摘要。工程师比较熟悉的 md5 就是使用最为广泛的 hash 函数，一般用来验证数据的完整性。
因为散列值是一个固定长度，比如说md5sum的输出是128位，也就是16字节，那么这个散列值的所有可能性就是 2^128。这个范围和IPv6的地址范围差不多。
一个 hash 函数可以由以下特性来进行评估：
- 均匀度（Uniformity）：前面提到了一个散列值的空间，那么一个hash函数对于一个输入的运算结果落到这个散列值空间中的概率最好是均等的。这样可以降低碰撞率（不同的输入得出相同结果的比率）
- 效率（Efficiency）：hash函数本身的计算复杂度也是一个考量因素。在很多场合，要求快速响应，因此最好计算简单。但是太简单的hash函数在均匀性上可能不理想，因此这里需要考虑一些权衡
- 确定性（Deterministic）：对于固定的输入，输出固定。这也是一般函数的特征
![]()
用于密码学的散列函数
对于区块链从业者而言，很多时候使用hash函数的场合并不是用于索引或检索数据（尽管这种情况也很普遍），通常可以看见的是用来进行单向计算和验证。比如说在比特币中采用 SHA256 来进行选举运算获得出块权，以及采用SHA256 和 RIPEMD-160 来从私钥计算公钥和地址。
除了hash函数的一般性特性只要，用于密码学的 hash 函数有更严格的要求：
- 单向性：从数据求散列值很容易，但不能倒推。或者倒推十分困难，理论上不可行
- 无相关性：要求在输入有一点点改变的情况下，要产生完全不同的输出。这样，从散列值完全不能看出数据之间的相关性
- 唯一性：不能通过不同的数据产生相同的hash值。这里说的不能是基本上不能人为实现，也就是说概率极小；此特性也可以成为碰撞安全性。
前面提到的 md5 散列函数，在区块链系统中完全没有被采用，其主要原因就是在碰撞安全性不能满足要求，密码学界在2007年就发现了其碰撞破解的办法，而最新的发现其双块攻击在普通计算机上就可以很快实现。而广泛使用的SHA256函数的碰撞安全性是 md5 的 2^64 倍，
![]()
IPFS 中使用的散列函数
IPFS 与传统存储系统的一个重要区别在于采用内容寻址。所谓内容寻址就是对内容做hash运算，把散列值作为内容的索引。由于hash函数的确定性和唯一性，可以用散列值来代表数据。
IPFS的CID（内容标识，也就是散列之）在数据格式的定义上采用MultiHash，也就是说，是一个可扩展的数据格式和方案。用户可以根据需要随时支持新的协议。其格式大致如下：
![]()
大家常见的以 Qm 打头的CID是采用SHA256算法的，Qm是SHA256的base58编码后的结果。当前，IPFS支持的常见hash算法包括：
- SHA-1：160bits，
- SHA-2-256， SHA-2-512
- SHA-3-256
- blake2b-256
注1： SHA家族的算法，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布，是美国的政府标准。SHA-x表示第x代。
注2: BLAKE2的改进版本于2012年12月21日宣布推出。它由Jean-Philippe Aumasson、Samuel Neves、Zooko Wilcox-O'Hearn和Christian Winnerlein设计，用于取代广泛使用但已被攻破的MD5和SHA-1算法。Blake2的特点是计算更快，安全性高。
由于 Filecoin 的代码基于IPFS之上，因此IPFS中使用的hash算法，也就自然在Filecoin中被采用，包括使用于libp2p, IPLD, 以及存储市场和检索市场。
Filecoin采用的其他散列算法
除了IPFS中的散列算法之外，Filecoin作为区块链，在散列算法的应用上考虑更多。其中最为重要的两个方面需要考虑的就是：1）计算的高效性；2）安全性
这一点可以从Filecoin在选择 Blake-2b 和 SHA-3 上可以看出来，Blake算法曾被其发明人Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan 提交到NIST去竞争 SHA-3，但最终败给了 Keccak（以太坊目前使用，将来也可能替换）。但 Blake2 效率更高，在实践中安全性不输SHA-3。因此，blake2在Filecoin中被广泛采用。
在Filecoin中 blake2b 使用在以下一些地方：
- blake2b-256 ：IPLD，用于区块和消息
- blake2b-4 ：用于校验
- black2b-160：用于取代RIPEMD-160来生成 secp256k1 地址，也就是现在的 t1 地址，通常是客户端采用的地址
Filecoin区别于现有区块链的一个显著特点是它的证明系统，也就是其复制证明和时空证明机制。在这一套机制中，hash算法也被广泛用到。
Feistel算法
Feistel 算法本来是一个对称密码算法，采用数据块链式加密的方式。没有太高的复杂度。为什么会用来作为hash函数呢？在2005年，有人就发现采用Feistel算法可以实现一个完全散列均匀的分布，而且满足随机性。因此，这个刚好切合 SDR 中exp parents node的选取规则。
基于Feistel算法的hash函数，又成为F-Hash。Filecoin采用F-Hash来为SDR过程中的每一个节点计算找寻父节点，这些父节点随机分布，没有规律，同时，这些父节点又完全均匀地分布在整个sector的空间中。这简直就是使用F-Hash的最佳场合。
PedersenHash
区块链业界对零知识证明进行孜孜不倦的探索者就是令人尊敬的ZCash团队。ZCash团队一直在追寻如何更快更安全地进行零知识证明，
在ZCash中，PedersenHash 是为 PedersenCommitment服务，这在ZCash的交易中起到举足轻重的作用。Filecoin的复制证明和时空证明采用与ZCash类似的零知识证明，所以顺理成章地采用PedersenHash。
PoseidonHash
但是，技术在不断进步。随着ZCash的研究，2019年5月，一篇论文横空出世：Starkad and Poseidon: New Hash Functions for Zero-Knowledge Proof Systems。此论文号称，采用Poseidon，其约束复杂度相对Pedersen而言，减少8倍。因此电路复杂度大大减小。证明和验证也就更快了。
在这种情况下，Filecoin团队毅然决定，在Filecoin的证明系统中，与零知识证明相关的hash算法采用 PedersenPoseidon。
用得最多的还是 SHA256
尽管前面提到多种不同的Hash算法，但是，在Filecoin中，SHA256还是使用的最多的一种。特别是在SDR的第一个阶段，进行每一层的计算之中，所有的node计算全部采用SHA256。
这带来一个问题，那就是对SHA又特殊支持的芯片效率要高很多。这也就是为什么Filecoin团队最近一直在暗示AMD CPU效率更高的原因，因为AMD的多数芯片都支持 SHA-NI，而Intel目前并不支持。这个问题是的Intel设备非常尴尬，也使得市场处于一个不平衡的状态。
既然如此，为什么Filecoin团队不换一个Hash算法，来达成某种平衡，不同的设备都可以进入网络进行竞争对Filecoin网络来说不是更好吗？但是，我的判断是，并不会。因为这里又充分的理由采用SHA-256。具体原因是什么，留给读者自己思考。
参考：- Starkad and Poseidon: New Hash Functions for
Zero-Knowledge Proof Systems, Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy,
and Markus Schofnegger, May 2019
- https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html
- F-HASH: Securing Hash Functions Using Feistel
Chaining，Duo Lei, 2005
- 是什么让你如此卓尔不群：Filecoin的证明系统
- 【Filecoin】写在测试网上线之前
- Filecoin 存储证明 浅析
|
|
转播
