Merkle trees vs Verkle trees

1. • 什么是默克尔树，它们是如何工作的？

使用加密哈希算法的二叉树称为 Merkle 树。

哈希树也称为 Merkle 树，用数据块的加密哈希标记叶节点。此外，它还使用其子节点标签的加密散列来标记非叶节点。

每个节点都会生成一个摘要(Hash)，该摘要递归地依赖于其子树中的所有characteristics，并且一个或多个属性被添加到叶子中。在 Merkle 树结构中，叶子j节点计算自己属性的散列(Hash)，父节点计算其子节点从左到右串联的摘要的摘要。

Ralph Merkle 于 1988 年开发了 Merkle 树以创建更强大的数字签名。 Merkle 树有效地验证了数据的正确性和完整性，同时减少了验证的内存需求。此外，与其他数据结构相比，默克尔树占用的磁盘空间更少，这是默克尔树的显着优势之一。

那么，以太坊是默克尔树吗？以太坊区块链使用称为 Merkle Patricia trie 的 Merkle 树，它提供了一种数据结构，可用于存储所有（key, value）绑定并通过密码进行身份验证。

此外，以太坊执行层中的所有 Merkle 尝试都使用 Merkle Patricia Trie。状态特里树随着时间更新，因为只有一个全局状态特里树。所有合同数据都保存在存储树中。每个块都有自己的存储（key, value）对的事务树。每个块都包含一个永远不会更新的单独的 Receipts trie。

1. • 什么是 Verkle 树，它们是如何工作的？

与 Merkle 树类似，Verkle 树允许您组织大量数据并为每个数据项或一组相关片段创建一个简短的“witness”，可以由有权访问树根的人确认。

然而，Verkle 树最重要的特征是它们的证明大小效率。与典型的二叉 Merkle 树大约 1 KB 相比，Verkle 树需要不到 150 bytes来为具有十亿个数据点的树生成证明。 Verkle 树利用称为多项式承诺的证明系统，依靠多项式函数来描述数据。

2018 年，John Kuszmaul 引入了 Verkle 树，但与许多其他重要的新密码结构相比，它仍不为人所知。 Verkle 树结构类似于以太坊当前的 Merkle Patricia 树。本质上，每个节点都具有以下三个属性之一：

1. 它是空的。

1. 它是一个带有键和值的叶节点。

1. 它是一个具有定义数量的子节点（树的“宽度”）的中间节点。

节点的子节点值的散列(Hash)用于计算中间节点的值。然而，Verkle 树比 Merkle Patricia 树更广阔，这是 Verkle 树的显着优势之一，也是它们结构组件之间唯一的实质性区别。唯一的限制是，如果宽度增加太多，校样的制作时间就会过长。结果，证明随着宽度的增加而变得越来越短。

1. • Merkle 和 Verkle 树在区块链中的重要性是什么？

Merkle 树用于比特币 ( BTC ) 和其他加密货币，以更有效和安全地加密区块链数据。 Verkle 树允许更小的证明大小，这对于以太坊即将到来的 扩展升级 尤为重要。

如何识别默克尔树呢？叶节点、非叶节点和 Merkle 根是区块链上下文中 Merkle 树的三个基本部分。交易哈希或交易 ID (TXID) 位于叶节点中，可以在区块浏览器上查看。然后，在叶节点之上，一层非叶节点成对散列在一起。非叶节点将它们代表的两个叶节点的散列保存在它们下面。

Related: What is blockchain technology? How does it work?

随着树在上升时变窄，当非叶节点级别继续成对散列在一起时，每层形成的节点数量减少一半。最后的非叶子节点层会出现两个节点，该层建立 Merkle 根（用于验证叶子节点），是 Merkle 树中最后一次哈希的位置。

存储在块数据部分的 Merkle 根可以与存储在块头中的 Merkle 根进行比较，从而使矿工能够快速识别任何操纵。 Merkle 证明结合了被证明的价值和恢复 Merkle 根所需的散列值。此外，它们还支持简单的支付验证 (SPV)，无需下载完整的区块或区块链即可用于验证交易。这允许使用加密钱包或轻客户端节点来发送和接收交易。

与 Merkel 树相比，Verkle 树可以显着减少大量数据的证明大小。证明长度（通常与状态大小成对数）会影响网络通信。但是，什么是 Verkle 证明？ Verkle 证明是存储大量数据的证据，任何拥有树根的人都可以轻松验证。

证明者必须提供单一证明，证明从每个叶节点到根的路径上的所有承诺之间的所有父子链接，而不是在 Verkle 树的每一层都呈现所有“sister nodes”。与理想的 Merkle 树相比，证明大小可以与以太坊目前的六叉帕特里夏树相比，减少了 6-8 倍，超过 20-30 倍。

1. • Merkle trees vs. Verkle trees

两种类型的树之间有很多差异，特别是在提供 Merkle 证明和 Verkle 证明方面。

Merkle 树中的整个姐妹节点集，包括 Merkle Patricia 树，构成了一个值的证据。证明必须包括树中的所有节点以及与您试图证明的节点相同的任何父节点。另一方面，在 Verkle 树中，您只需要提供路径加上一点点额外的证据——您甚至不需要添加姐妹节点。

Verkle 树的主要思想是可以通过用向量承诺代替加密哈希函数来创建 Merkle 树。 Verkle 树的用途与 Merkle 树相同。但是，它们在字节大小方面明显更有效，这是主要区别。

由于它们的树状结构，Merkle 证明很容易部分更新，而 Verkle 树中的多项式承诺要求完全改变整个曲线，需要再次计算证明是一个不小的挑战。

世界各地的人们都可以使用可以在个人计算机或智能手机上高效、简单地运行的加密钱包发送、接收和验证交易，这是重要的默克尔树用例，可能是由于默克尔树形成的默克尔根。相反，Verkle 树的一个关键用例包括用向量承诺代替 Merkle 树中的哈希值，从而提高更广泛分支因子的有效性。

参考

https://cointelegraph.com/explained/merkle-trees-vs-verkle-trees-explained