SVM默克尔树

一个SVM优化的默克尔树，底层使用Solana系统调用。它有以下特性

• 比特币默克尔树奇偶性
• Sha256/Sha256D/Keccak/Keccakd
• 一个命令行界面来生成有效的默克尔树/根/证明
• 一个WASM包
• 全面测试覆盖
• Anchor序列化
• 截断哈希
• 默认对叶子进行双重哈希，以防止截断哈希中的长度扩展攻击

注意事项

在使用SVM-merkle树时有一些需要注意的事项

截断哈希

由于Solana的交易大小限制，具有更大默克尔树的更复杂程序通常会倾向于使用截断分支哈希。考虑这样做时的安全权衡是很重要的。您使哈希越短，暴露于长度扩展攻击的风险就越大，攻击者能够挖掘出一个兼容的哈希，因为截断哈希的位安全性相对较低。

添加叶子

SVM Merkle Tree旨在通过在添加叶子时强制执行双重哈希来防止长度扩展攻击，无论是否选择双重哈希算法。相反，如果在选择双重哈希算法的情况下，它还防止了四重哈希。

例如，使用具有hash_size为20的叶子的sha256哈希的伪代码如下

let leaf1_hash = sha256(sha256(leaf1_bytes))[..20].to_vec();
let leaf2_hash = sha256(sha256(leaf2_bytes))[..20].to_vec();

分支哈希如下

sha256([leaf1_hash, leaf2_hash].concat())[..20]

如您所见，叶子的第一个sha256哈希没有被截断以提供对第二个哈希预像的更高安全性。这是一个众所周知的防止长度扩展攻击的安全措施。然后第二个哈希被截断以与它的分支哈希配对。

分支简单地配对，单哈希和截断。如果您不想截断分支哈希，只需将哈希大小设置为0或32。

添加哈希

如果您希望将预哈希的叶子添加到树中，这是可能的，但是除了检查hash_size之外，SVM Merkle Tree无法知道叶子是否已进行双重哈希。如果您希望以这种方式使用树，请注意，数据清洗和标准化将取决于您。

奇数树

如果哈希的数量是奇数，建议您实现以下之一

• 在预像中包含每个叶子的索引编号，
• 添加一个额外的假最终叶子进行填充，或
• 在树外跟踪叶子的总数

原因在于，如果您使用兼容比特币的默克尔树来实现某种单次使用的白名单功能，奇数树的最末叶子节点将与自身配对。这意味着最末叶子节点在奇数长度的树中实际上有两个有效的位置。