Solana高级概念: 状态压缩

有效地利用Solana分类账的安全性来安全验证链下数据，确保其未被篡改。

这是通过使用一种特殊的二叉树结构（称为并发默克尔树）来实现的，

什么是状态压缩？

这些树是在这种“确定性”过程中创建的：

1. 取任意数据片段
2. 创建该数据的哈希值
3. 将此哈希值作为树底部的叶子(leaf)存储
4. 然后将每对叶子(leaf)哈希在一起，创建一个分支(branch)
5. 然后将每个分支(branch)哈希在一起
6. 不断向上攀登树并将相邻的分支哈希在一起
7. 一旦到达树顶，生成最终的根哈希(root hash)

这个根哈希(root hash)然后存储在链上，作为所有叶子数据的可验证证明。 允许任何人加密验证树内的所有链下数据，同时实际上只在链上存储最少量的数据。

默克尔树和并发默克尔树

允许对任何给定树进行多次更改，

同时仍保持树的完整性和有效性。

什么是默克尔树？

其中每个叶节点表示其内部数据的加密哈希值。

而每个非叶节点（称为分支）表示其子叶哈希的哈希值。

一旦计算出最终的根哈希(root hash)， 存储在叶节点中的任何数据片段都可以通过重新哈希特定叶的数据和攀登树的每个相邻分支的 哈希标签（称为证明或证明路径）来验证。

如果它们匹配，则数据被验证为准确。

如果不匹配，则叶数据已更改。

然后，使用此新根哈希来验证任何数据，并有效地使先前的根哈希和先前的证明失效。

因此，对这些传统 Merkle 树进行的每次更改都必须按顺序执行。

什么是并发默克尔树？

在高吞吐量应用中，例如在Solana运行时环境中， 验证者可能会相对快速地接收到更改链上传统默克尔树的请求（例如，在同一个插槽中）。

导致每个后续更改请求失败，因为根哈希和证明已被插槽中的先前更改请求无效化。

引入并发默克尔树。

有效地允许同一棵树在同一插槽中进行最多最大缓冲区大小次更改。显著提高吞吐量。

并发默克尔树大小调整

• 最大深度
• 最大缓冲区大小
• 树冠深度

最大深度

树的最大深度是从任何数据叶到树根的最大跳数。

由于默克尔树是二叉树，每个叶子仅连接到另一个叶子；作为一个叶子对存在。

因此，最大深度用于确定使用简单计算存储在树中的最大节点数（即数据片段或叶子）：

nodes_count = 2 ^ maxDepth

然后使用上述简单计算，您可以确定存储数据所需的最低最大深度(maxDepth)。

示例1：铸造100个NFT

如果您希望创建一棵树来存储100个压缩NFT，我们需要至少100个叶子或100个节点。

// maxDepth=6 -> 64 nodes
2^6 = 64
 
// maxDepth=7 -> 128 nodes
2^7 = 128

我们必须使用最大深度(maxDepth)7以确保我们可以存储所有数据。

示例2：铸造15000个NFT

如果您希望创建一棵树来存储15000个压缩NFT，我们需要至少15000个叶子或15000个节点。

// maxDepth=13 -> 8192 nodes
2^13 = 8192
 
// maxDepth=14 -> 16384 nodes
2^14 = 16384

我们必须使用最大深度14以确保我们可以存储所有数据。

更高的最大深度意味着更高的成本

最大深度越高，可以存储的数据指纹（即哈希）越多，成本越高。

最大缓冲区大小

最大缓冲区大小实际上是指在根哈希仍然有效的情况下，树上可以发生的最大更改次数。

由于根哈希实际上是所有叶数据的单一哈希， 更改任何单个叶会使常规树所有后续尝试更改任何叶所需的证明无效。

但对于并发树，有效地存在这些证明更新的变更日志。 此变更日志缓冲区在创建时通过此maxBufferSize值设置和调整大小。

树冠深度

在对叶子(leaf)执行更新操作时，如转移所有权（例如销售压缩NFT）， 必须使用完整证明路径来验证叶子的原始所有权，从而允许更新操作。

树的最大深度越大，执行此验证所需的证明节点越多。

例如，如果您的最大深度为14，则需要14个总证明节点来进行验证。

随着树变大，完整证明路径变长。

通常，每个这些证明节点都需要包含在每次更新交易中。

由于每个证明节点值占用32字节交易空间（类似于提供公钥）， 较大的树很快就会超过最大交易大小限制。

引入了树冠。

从而减少每次更新交易中需要包含的证明节点数量，因此保持整体交易大小低于限制。

例如，最大深度为14的树需要14个总证明节点。 具有10个树冠，仅需4个证明节点提交每次更新交易。

树冠深度值越大，成本越高

canopyDepth 值也是创建树时成本的主要因素， 因为您将在树创建时支付此成本。

较小的树冠限制组合性

尽管树木的创建成本随着树冠高度的提高而增加，但较低的树冠深度将要求在每个更新事务中包含更多的证明节点。

要求提交更多节点，事务大小就越大，因此很容易超出事务大小限制。

这也将适用于任何其他尝试与您的树/叶子进行交互的 Solana 程序或 dApp。 如果您的树需要太多的证明节点（因为树的深度较低），那么任何其他的链上程序可能提供的额外操作， 将受到其特定指令大小加上您的证明节点列表大小的限制。

这将限制可组合性，并为您的特定树提供潜在的附加效用。

例如，如果您的树用于压缩NFT并且具有非常低的树冠深度， NFT市场可能只能支持简单的NFT转移，而不能支持链上竞标系统。

创建树的成本

• maxDepth
• maxBufferSize
• canopyDepth。

这些值都用于计算在链上存储（以字节为单位）所需的树存在的空间。

并使用 getMinimumBalanceForRentExemption RPC 方法，

请求分配这些字节所需的费用（以 lamports 为单位）到链上。

在JavaScript中计算树成本

// 计算树所需的空间
const requiredSpace = getConcurrentMerkleTreeAccountSize(
  maxDepth,
  maxBufferSize,
  canopyDepth,
);
 
// 获取在链上存储树的成本（以 `lamports` 计）
const storageCost =
  await connection.getMinimumBalanceForRentExemption(requiredSpace);

示例成本

下面列出了几个示例成本，涵盖不同树大小，以及每个树可能有多少叶节点:

示例 #1：16,384个节点，费用为0.222 SOL

• 最大深度为14,最大缓冲区大小为64
• 最大叶节点数量：16,384
• 0层树冠创建成本约为0.222 SOL。

示例＃2：16384个节点成本为1.134 SOL

• 最大深度为14，最大缓冲区大小为64
• 叶节点的最大数量为16384
• 层高为11的树冠大约需要花费1.134 SOL来创建。

示例＃3：1,048,576个节点，成本为1.673 SOL

• 最大深度为20，最大缓冲区大小为256
• 最大叶子节点数：1,048,576
• 树冠深度为10，大约要花费1.673 SOL来创建。

示例＃4：拥有1,048,576个节点，成本为15.814 SOL

• 最大深度为20，最大缓冲区大小为256
• 叶子节点的最大数量为1,048,576
• 15个树冠深度创建大约需要15.814 SOL

压缩的NFTs

压缩的NFTs是Solana上状态压缩的最受欢迎的用例之一。

如果您有兴趣自己创建压缩的NFTs，请阅读我们的开发者指南，了解如何铸造和转移压缩的NFTs。

总结

以下是本文中的要点总结：

状态压缩

• 定义：状态压缩在Solana上是一种通过创建链下数据的指纹（哈希值）并将其存储在链上进行安全验证的方法。
• 目的：利用Solana分类账的安全性来验证链下数据，确保其未被篡改，同时节省区块链分类账空间。
• 实现方式：使用并发默克尔树结构，将每个数据片段（叶子）创建哈希值，最终生成一个根哈希并存储在链上。

什么是状态压缩？

• 过程：
  1. 取任意数据片段
  2. 创建该数据的哈希值
  3. 将哈希值作为叶子存储
  4. 将每对叶子哈希在一起生成分支
  5. 不断向上攀登树，直到生成最终的根哈希
• 优势：显著降低存储和证明大量数据的成本。

默克尔树和并发默克尔树

• 默克尔树：
  • 基于哈希的二叉树结构，每个叶节点表示其数据的哈希值，每个分支节点表示其子叶哈希的哈希值。
  • 最终生成一个根哈希，用于验证存储在叶节点中的数据。
• 并发默克尔树：
  • 允许对同一棵树进行多次更改，保持树的完整性和有效性。
  • 在链上保留变更日志，允许在同一插槽中进行多次快速更改，提高吞吐量。

并发默克尔树大小调整

• 决定因素：
  • 最大深度：从叶子到树根的最大跳数，决定存储的数据片段数量。
  • 最大缓冲区大小：变更日志缓冲区的最大记录数。
  • 树冠深度：影响树的创建成本和并发更改数量。

示例

• 铸造100个NFT：需要至少100个叶子或节点，计算出所需的最小最大深度。

通过这些要点总结，可以更好地理解Solana上的状态压缩技术及其实现方式和优势。