密码学工具入门：哈希函数与默克尔树详解
本文讲什么？
区块链让人们无需中介即可就事务达成共识。区块链不依赖信任，而是依赖密码学证明。这些证明由密码学原语提供。但密码学原语究竟是什么？
本文将介绍两种对区块链密码学证明至关重要的密码学原语：哈希函数和默克尔树。我们将探索哈希函数的核心机制，了解它们对区块链的重要性，并学习哈希指针。随后，我们将研究传统默克尔树和并发默克尔树，说明它们对 Solana 的重要意义。
什么是密码学原语？
密码学原语是构建密码学协议和系统所必需的基础操作或算法。密码学原语之于密码学协议，就像原子之于分子——它们是构建更复杂解决方案的基本组件。随机数生成器、承诺方案和公钥密码学都是密码学原语的例子。
单独使用时，密码学原语的能力十分有限。组合使用时，它们可以提供身份验证、机密性和完整性等基本安全功能。组合密码学原语是一个极其精细的过程，需要周密规划，并深入理解每种原语之间的交互方式。在此过程中，你必须根据希望实现的安全目标，谨慎考虑安全问题。组合密码学原语的方法大致可分为：
- 顺序组合：依次应用不同原语（例如哈希链）
- 并行组合：同时且相互独立地使用不同原语（例如同时加密和哈希数据）
- 分层组合：在一种密码学原语内部使用另一种原语（例如默克尔树）
了解什么是密码学原语、它们如何运作，以及组合它们时涉及的细微差别，有助于你理解并设计安全高效的系统。哈希函数是最常用、也最常与其他原语组合的密码学原语之一。
什么是哈希函数？
哈希函数是一种密码学函数，它接收任意大小的数据并返回固定大小的值。该函数返回的值称为摘要或哈希。常见的哈希算法包括：SHA-1、SHA-2、SHA-3、MD5 和 Argon2。哈希函数在区块链中无处不在，因此理解它们是什么以及如何运作至关重要。
一个简单的类比
想象一下，你正在烘焙一款精美的巧克力蛋糕。蛋糕有多层，每层使用不同的配料。烘焙过程中，朋友发消息问你在做什么。如果详细解释蛋糕的制作方式和用到的所有配料，会非常麻烦。于是，你决定给朋友发送一张巧克力蛋糕的照片。
在这里，蛋糕的照片相当于哈希——它是对一个复杂得多的事物所做的简单、紧凑表示。你的朋友不会知道制作蛋糕用到的每一种配料，但能大致了解你刚刚烤了什么。假设巧克力蛋糕顶部放着树莓。如果你取下树莓或将其换成草莓，蛋糕的照片就会与最终成品完全不同。同理，对被哈希数据进行任何更改，都会产生新的哈希值。
优秀密码学哈希函数的特性
严格来说，前面对哈希函数的定义具有误导性。哈希函数可以返回大小不固定的哈希，也可以对两个不同输入返回相同的哈希。甚至有人可能轻易逆向哈希并找到原始输入。前面的定义实际描述的是一个优秀的密码学哈希函数。那么，怎样才算优秀的密码学哈希函数？
优秀的哈希函数具有确定性——相同输入始终会产生相同输出。如果我对输入“baseball”进行哈希，那么无论使用什么系统，该哈希函数每次都会输出相同的哈希。这也部分意味着，无论输入大小如何，哈希的大小都保持不变。这对处理效率和数据存储非常重要。确定唯一输入始终产生唯一输出，且这些输出始终具有固定大小，是优秀密码学哈希函数的明确标志。
优秀的哈希函数具有原像抗性。这意味着，根据哈希逆向推导输入值在计算上不可行。因此，如果有人给你一个哈希，你不应能够推断出产生该哈希的数据。这也引出了另一个要求：两组不同的数据不应产生相同的哈希。如果任意两个输入都绝不会产生相同的哈希，就可以说这个优秀的哈希函数具有抗碰撞性。
优秀的哈希函数遵循雪崩效应——输入的细微变化应导致哈希发生巨大变化。即使只更改一个字符，也应产生完全不同的哈希。因此，哈希输出不应泄露任何输入信息，也不应具有任何可识别的模式。请注意上图中哈希的差异。红狐狸“奔跑”与红狐狸“行走”产生的哈希截然不同。此外，也没有任何迹象表明这两个哈希包含几乎相同的信息。
优秀的哈希函数应当能够快速计算。速度慢的哈希函数不适用于交易验证等实时或近实时计算场景。它可能成为严重瓶颈，同时限制吞吐量和网络性能。要让区块链高效、安全地运行，快速的哈希函数必不可少。
为什么这对区块链很重要？
区块链是一种去中心化的分布式账本，用于记录整个网络中的交易。这些交易被分组放入区块，并通过一个优秀的哈希函数安全连接。每个区块都包含交易数据、时间戳和前一个区块的哈希。由于每个区块的哈希都依赖前一个区块的哈希，对区块内容的任何更改都会改变其哈希，并使所有后续区块失效。这种在生成新哈希时使用先前哈希的过程称为哈希链。
向区块链添加新区块称为确认。一次确认会验证并保护新区块中的所有交易，以及之前所有区块中的交易。这是因为每增加一次确认，修改之前区块的难度就会增加。要修改之前的区块，攻击者必须重新计算之前的所有哈希。因此，当一个区块获得相当数量的确认后，哈希链可确保修改区块链在实践中不可行。
简而言之，区块链就是由哈希函数保护的区块链条。但我们究竟如何从一个区块指向另一个区块？没错，密码学哈希函数用于将区块连接起来，但我们如何查看之前区块中的数据？我原以为优秀的密码学哈希函数具有原像抗性。
什么是哈希指针？
指针是一种变量，用于保存特定数据在内存中的存储位置。由于指针“指向”数据所在的位置，因此可以轻松访问该内存地址中的数据。哈希指针是一种与指针类似的数据结构，但它还包含所引用数据的密码学哈希。因此，哈希指针既能告诉你从哪里访问特定数据，也能让你检查所访问数据的完整性。
更准确地说，区块链的结构是一种使用哈希指针的链表。前一个区块的哈希就是一个哈希指针，它指向一组交易以及所有这些交易的哈希。哈希指针有助于连接区块、保障每个区块的完整性，并验证新添加的区块是否正确衔接之前的区块。
哈希指针用于高效地将区块连接起来。但区块中的交易怎么办？如果一个区块包含一千笔交易，逐笔验证这些交易岂不是成本很高？
什么是默克尔树？
默克尔树是一种用于组织和验证大型数据集的数据结构。数据以树状结构组织，每个叶子或节点都标有一组数据的哈希。每个非叶节点都是其子节点的哈希。默克尔树用于验证传播到区块链上的特定区块中所包含的交易。那么，它是如何运作的？
多笔交易会批量放入一个列表中，形成区块。列表中的每笔交易都使用优秀的哈希函数进行哈希。这些哈希作为叶节点。叶节点两两组合进行哈希，从而创建新一层哈希。这个过程不断迭代，直到只剩下一个哈希，即默克尔根。默克尔根存储在区块头中，相当于该区块内所有交易的数字指纹。我们也可以将默克尔根称为区块的哈希。因此，当我们说新区块使用前一个区块的 blockhash 与其连接时，实际是说该区块将前一个区块的默克尔根作为新区块哈希的一部分。
默克尔树可以高效验证区块中的单笔交易。传统方法需要验证每笔交易才能验证某笔特定交易，成本高且耗时。默克尔树提供了一种名为默克尔证明的密码学“捷径”，用于辅助验证。默克尔证明是一条从交易的叶节点一直延伸到默克尔根的路径。以上图为例，可以将它理解为从 Data A 到默克尔根的路径。该路径还包含其兄弟节点，即与路径上各节点相邻、但本身不属于该路径的叶子。验证者可以使用证明路径计算哈希，并检查计算出的哈希是否与默克尔根匹配。如果结果匹配，验证者就能确信该交易合法且未被篡改。
要更改叶子，可以对新叶子的数据进行哈希并重新计算默克尔根。这个新的默克尔根用于验证新的更改，并使之前的证明失效。在 Solana 这样的高吞吐量网络中，验证者可能连续快速收到对链上默克尔树的更改请求（例如在同一个 slot 内）。每次数据更改都需要按顺序重新计算，否则，slot 内前一个更改请求会导致后续每个更改请求失效。更改叶子数据并计算新的默克尔根在区块链中非常常见。那么，如何处理快速连续发生的更改？
什么是并发默克尔树？
并发默克尔树是一种针对并发读写进行优化的默克尔树。它会安全地存储最近更改的变更日志、这些更改的根哈希，以及推导该根哈希所需的证明。该变更日志存储在链上一个专属于该树的账户中，其中规定了在默克尔根仍然有效的情况下可发生的最大更改次数。这个最大更改次数称为 maxBufferSize。因此，当验证者连续快速收到对链上默克尔树的更改请求时，可以将该变更日志作为事实来源，从而允许在同一个 slot 内对树执行最多 maxBufferSize 次更改。
并发默克尔树改进了传统默克尔树，使其适用于 Solana 等高吞吐量环境。要在 Solana 上创建链上并发默克尔树，有三个属性会影响树的大小、创建树的成本，以及树可承受的并发更改次数：
- 最大深度
- 最大缓冲区大小
- 树冠深度
最大深度是指从任意叶子到达默克尔根所需的最大跳数。maxDepth 用于确定树中最多可存储的节点数。可使用以下公式计算：numberOfNodes = 2 ^ maxDepth。树的深度必须在创建时设定，因此必须使用该公式确定希望树存储多少份数据。
如前所述，最大缓冲区大小是指在默克尔根仍然有效的情况下，可以对树执行的最大更改次数。
树冠深度是指存储在链上的默克尔树子集。这些缓存的证明用于根据链上默克尔根检查哈希。对叶子执行写入时，必须使用完整的证明路径来验证叶子的原始所有权。例如，转移 NFT 时就需要写入树。树冠可以缩小证明大小，避免使用大小为 maxDepth 的证明来验证树。maxDepth 为 20 的树需要大小为 20 的证明。如果树冠深度为 15，则每笔写入交易只需提交大小为 5 的证明。因此，树冠深度越大，前期支付的成本就越高，但以后可以提交更小的证明。
树冠深度是影响树创建成本的主要因素之一。这是因为树冠深度越大，所需的账户也越大。开发者可以使用 @solana/spl-account-compression 软件包，计算给定树大小所需的空间，以及在链上为该树分配所需空间的成本。开发者可以使用 getConcurrentMerkleTreeAccountSize 函数，根据给定账户的参数计算所需空间，再对所需空间使用 getMinimumBalanceForRentExemption，得出以 Lamports 计价的最终成本。
Solana 使用并发默克尔树进行状态压缩。状态压缩是一种为链下数据创建哈希并将其存储在链上以便安全验证的方法。状态压缩最常见的用例是压缩 NFT，因为它能显著降低铸造成本。例如，在 Solana 上铸造十亿个 NFT 的成本为 507 $SOL，而使用“普通”NFT 则需要 12 000 000 $SOL。现在，你已经充分理解了哈希和默克尔树。我们将在后续文章中深入探讨压缩 NFT！
总结
恭喜！本文分析了哈希函数和默克尔树这两种对区块链至关重要的密码学原语。理解区块链绝非易事——它们是复杂的分布式系统，需要广泛的技术知识。人们通常默认普通开发者、用户或投资者已经掌握这些知识。本文并不假设你事先了解密码学原语，而是从基础知识入手，再逐步深入探讨传统默克尔树和并发默克尔树。在准备研究压缩 NFT 等更复杂的主题时，掌握这些基础知识至关重要。有了这些新知识，你将能更好地理解涉及密码学原语和更复杂密码学解决方案的代码库或讨论。
匿名朋友，如果你读到了这里，谢谢你！
补充资源 / 延伸阅读
订阅 Helius
及时了解 Solana 开发的最新动态，并在我们发布新内容时收到更新