Merkle Tree

Merkle Proof

Merkle Tree的最大特点是：可以以一个很简短的方法来证明一棵树中存在某一个元素。即 Simplified Payment Verification，SPV

SPV 轻节点安全性分析

【问题】tx10、proof均为外部提供的信息，roothash又是公开信息，是否可以构造恶意数据对(tx,proof)骗过轻节点的验证，如果不能，为什么？
【回答】
这里本质上是对SPV节点的安全性问题的讨论：
（1）若全节点返回的是一条恶意的路径？试图为一个不存在于区块链中的交易伪造一条合法的merkle路径，使得最终的计算结果与区块头中的默克尔根哈希相同。
由于哈希的计算具有不可预测性，使得一个恶意的“全”节点想要为一条不存在的节点伪造一条“伪路径”使得最终计算的根哈希与轻节点所维护的根哈希相同是不可能的。
【补充】（个人观点不保证正确性，有误还请读者指出）我认为理论上通过查表（merkle根）来构造tx,proof是可行的，但很难实现对一个指定block的指向性攻击。此外，即使成功攻击了单个轻节点，还需要广播交易，全网共识，网络中全节点全部合谋攻击是不现实的。（以上是个人观点，不保证正确性）
（2）为什么不直接向全节点请求该交易是否存在于区块链中？
由于在公链的环境中，无法判断请求的全节点是否为恶意节点，因此直接向某一个或者多个全节点请求得到的结果是无法得到保证的。但是轻节点本地维护的区块头信息，是经过工作量证明验证的，也就是经过共识一定正确的，若利用全节点提供的默克尔路径，与待验证的节点进行哈希计算，若最终结果与本地维护的区块头中根哈希一致，则能够证明该节点一定存在于默克尔树中。（交叉二次验证）。
（3）SPV容易受到什么攻击？
SPV节点毫无疑问可以证实某个交易的存在性，但它不能验证某个交易（譬如同一个UTXO的双重支付）不存在。这个漏洞会被针对SPV节点的拒绝服务攻击或双重支付型攻击所利用。为了防御这些攻击，SPV节点需要随机连接到多个节点，以增加与至少一个可靠节点相连接的概率。这种随机连接的需求意味着SPV节点也容易受到网络分区攻击或Sybil攻击。在后者情况中，SPV节点被连接到虚假节点或虚假网络中，没有通向可靠节点或真正的比特币网络的连接。
完整的区块链节点是通过检查整个链中在它之下的数千个区块来保证这个UTXO没有被支付，从而验证交易。而SPV节点是通过检查在包含该交易的区块所收到的确认数目来验证交易。

（下图与上图是类似的含义，不同的画图方式）

通过提交merkle根是可以证明交易在区块中，但是还不够。因为区块链可能分叉，这个证明不能证明区块在最长链上。因此还需要后续6个区块对该区块的确认才能证明区块也在最长链上。

Bloom过滤器

SPV节点直接就向全节点请求某一交易的Merkle路径。SPV节点怎么样从网络中接收到与自己相关的交易，确定交易所在的区块呢？

SPV节点一般只需要的是和自己的地址相关的交易。最直接的做法就是SPV节点向全节点请求和自己地址相关的交易，也即在请求中附上自己的地址信息。如果全节点发现某个交易符合SPV节点时，就将以Merkleblock消息的形式发送该交易，Merkleblock消息包含区块头和Merkle路径。

SPV节点对特定数据的请求可能无意中透露了钱包里的地址信息。如果监控网络的第三方跟踪某个SPV节点上的钱包所请求的全部交易信息，就能利用这些交易信息把比特币地址和钱包的用户关联起来。

举例来说，如果在问路时，使用具体的地址，如“南京路188号”，那么可能得到具体的位置；但同时也泄露了目的地。如果问不同的人，188号在哪里？可能得到所有188号的信息；然后问南京路在哪里？可以得到一整条路的信息。那么虽然获得的答案中包括一些无关的信息；但是，相对应的，隐私得到了一定程度的保护。

因此，在引入SPV节点/轻量级节点后不久，比特币开发人员就添加了一个新功能：Bloom过滤器。这是在2012年的BIP37中引入的。

在比特币中，使用Bloom过滤器来加快钱包同步；以太坊使用Bloom过滤器用于快速查询以太坊区块链的日志。

布隆过滤器（Bloom Filter）是1970年由布隆提出的，用来判断某个元素是否在集合内，它具有运行速度快（时间效率），占用内存小的优点（空间效率），但是有一定的误识别率和删除困难的问题。它能够判断某个元素一定不在集合内或可能在集合内，也即Bloom Filter会造成一定的False Positive，但是不会造成False Negative。

Bloom过滤器的实现是由一个可变长度（N）的二进制数组（N位二进制数构成一个位域）和数量可变（M）的一组哈希函数组成。这些哈希函数的输出值始终在1和N之间，并且该函数为确定性函数，也即对特定输入总是得到同一个的结果。Bloom过滤器的准确性和私密性能通过改变长度（N）和哈希函数的数量（M）来调节。与其它数据结构相比较，Bloom filter的优点包括：空间效率和查找时间复杂性；不需要存储元素本身，在保护隐私方面具有优势。

工作原理

这里使用十六位数组（N=16）和三个哈希函数（M=3）来演示Bloom过滤器的应用原理。

Bloom过滤器数组里的每一个数的初始值为零。关键词被加到Bloom过滤器中之前，会依次通过每一个哈希函数运算一次。该输入经第一个哈希函数运算后得到了一个在1和N之间的数，它在该数组（编号依次为1至N）中所对应的位被置为1，从而把哈希函数的输出记录下来。接着再进行下一个哈希函数的运算，把另外一位置为1；以此类推。当全部M个哈希函数都运算过之后，一共有M个位的值从0变成了1，这个关键词也被“记录”在了Bloom过滤器里。
向上图中的简易Bloom过滤器添加关键词“A”：

增加第二个关键词就是简单地重复之前的步骤。关键词依次通过各个哈希函数运算之后，相应的位变为1，Bloom过滤器则记录下该关键词。需要注意的是，当Bloom过滤器里的关键词增加时，它对应的某个哈希函数的输出值的位可能已经是1了，这种情况下，该位不会再次改变。也就是说，随着更多的关键词指向了重复的位，Bloom过滤器随着位1的增加而饱和，准确性也因此降低了。该过滤器之所以是基于概率的数据结构，就是因为关键词的增加会导致准确性的降低。准确性取决于关键字的数量以及数组大小（N）和哈希函数的多少（M）。更大的数组和更多的哈希函数会记录更多的关键词以提高准确性。而小的数组及有限的哈希函数只能记录有限的关键词从而降低准确性。

如果N比较小，当添加关键词时，所有的位都成为1，意味着什么？
这意味着过滤器已经失去了意义，因为这时任何关键词的判断结果都是：可能已经被匹配。

为测试某一关键词是否被记录在某个Bloom过滤器中，则将该关键词逐一代入各哈希函数中运算，并将所得的结果与原数组进行对比。如果所有的结果对应的位都变为了1，则表示这个关键词有可能已被该过滤器记录。之所以这一结论并不确定，是因为这些字节1也有可能是其他关键词运算的重叠结果。简单来说，Bloom过滤器正匹配代表着“可能是”。

通过使用Bloom Filter，使得SPV节点只接收交易信息的子集，同时不会泄露哪些是它们感兴趣的地址。实际上，再对Bloom Filter进行设置时，如果带宽和硬件条件宽裕，SPV节点可以选择具有高FP（false positive）率的Bloom Filter，此时如果有第三方对SPV进行跟踪，看到的将是大量的数据中混杂着与节点相关的数据，从而隐私性得到了保护。相反，如果带宽和硬件条件不宽裕，则可以选择尽可能精确的设置从而过滤掉不相关的数据，但是第三方就有可能将交易和IP地址关联起来。

工作过程

首先，SPV节点会初始化一个不会匹配任何关键词的“空白”Bloom过滤器。接下来，SPV节点会创建一个包含钱包中所有地址信息的列表，并创建一个与每个地址相对应的交易输出相匹配的搜索模式。通常，这种搜索模式是一个向公钥付款的哈希脚本，该脚本是一个会出现在每一个向公钥哈希地址（P2PKH）付款的交易中的锁定脚本。如果SPV节点需要追踪P2SH地址余额，搜索模式就会变成P2SH脚本。然后，SPV节点会把每一个搜索模式添加至Bloom过滤器里，这样只要关键词出现在交易中就能够被过滤器识别出来。最后，对等节点会用收到的Bloom过滤器来匹配传送至SPV节点的交易。

Bloom Filter匹配算法

问题：哪些数据应该加入到filter中呢？

Bloom filter被广泛应用于各种领域，比如拼写检查、字符串匹配算法、网络
包分析工具、Web Cache、文件系统、存储系统等。

在重复数据删除应用中的空间和时间效率分析

重复数据删除技术的基本原理是对文件进行定长或变长分块，然后利用hash函数计算数据块指纹，如果两个数据块指纹相同则认为是重复数据块（存在数据碰撞问题），只保存一个数据块副本即可，其他相同数据块使用该副本索引号表示，从而实现数据缩减存储空间并提高存储效率。

为了查询一个数据块是否重复或者已经存在，需要计算数据块指纹并进行查找，并记录所有唯一数据块的指纹。举一个例子：32TB的数据，平均数据块大小为8KB，每个数据块使用MD5和SHA1计算两个指纹并用64位整数表示唯一块号则共占用44字节((128+160+64)/8），则总共最多需要176GB（32TB/8KB * 44 Byte）的存储空间来保存数据块信息。

现在的去重系统数据容量通常多达数十到数百TB，如果把数据块信息全部保存在内存中，显然对内存的需求量非常巨大。通常的做法是把数据块信息保存在磁盘或SSD上，使用一定内存量作Cache缓存数据块指纹，利用时间局部性和空间局部性来提高查找性能。这种方法的一个关键问题是，如果新的数据块是不重复的，查找时会出现Cache不命中，从而引起大量的磁盘读写操作。 由于磁盘或SSD性能要远远小于内存的，对查找性能影响非常大。

Bloom filter可以有效解决这个问题，DataDomain中的Summary Vector就是采用Bloom filter来实现的。对于前面的例子，一个数据块用3个hash函数计算指纹最多占用N位，则Bloom filter仅需要1.5GB = 32TB/8KB * N /8 bytes的内存空间。引入Bloom filter机制后，对于一个新数据块，首先查找Bloom filter，如果未命中则说明这是一个新的唯一数据块，直接保存数据块和并cache数据块信息即可；如果命中，则说明这有可能是一个重复数据块，需要通过进一步的hash或tree查找进行确认，此时需要Cache与Disk进行交互。受益于Bloom filter以及Cache，DataDomain系统可以减少99%的磁盘访问，从而利用少量的内存空间大幅提高了数据块查重性能。【即：解决了带来巨大代价的判空问题】
【说明：这里与参考资料Ref.4不同，我认为原资料此处表达和结论有误，原文是占用M=3位，实际上我认为这里应该占用的是N位】