作者：Hoyt

有感于 Celestia 白皮书中，关于使用‘带命名空间的默克尔树’的相关章节，原文写得比较复杂，我们花了大量的时间去阅读，查看开源的示例代码，并和作者反复沟通才最终达成一致。而作为翻译，我们不能对原文的结构有太大改动，因此，为了使大家理解起来更容易，我们考虑单独发文，以更简明的方式向大家介绍相关内容。

为了实现链的容量扩展，Celestia 承诺主权应用将只需下载与其有关的消息（消息和交易的区别是，交易专指改变应用状态的消息），而不用下载全部消息，但同时，不同应用的消息是打包在同一个区块里面的，以实现平等的安全性。那么，如何保证当某个应用的执行节点向 Celestia 的存储节点查询消息时，存储节点仅返回所有的相关消息，而且恶意存储节点无法隐藏特定消息呢（注意这里跟数据可用性是不同的概念，那个是指不下载所有数据的轻客户端，如何确信数据可以被验证节点下载到）。

Celestia 选择的方案是，将称为命名空间的应用标识符，插入到消息构成的默克尔树的节点信息中。这样做的好处是，可以处理存储节点隐藏全部相关消息的情况，可以定位被隐藏的消息。另外，无需大幅度修改默克尔树的生成逻辑，以确保存在一个节点，它的底层叶节点，包含且仅包含某个命名空间的全部消息，且能定位此节点。而只需要做三件相对简单的事情，就可以确保默克尔树的基本特性，不发生变化：

1. 首先，生成消息的默克尔树之前，先按命名空间将消息分组归并在一起，确保不同命名空间的消息没有穿插，且命名空间是排好序的。

2. 其次，修改生成默克尔树时使用的哈希函数，以便命名空间信息被包含进节点信息（因为非叶节点，就只有哈希这唯一信息）。

3. 检查默克尔树时，额外检查排序是否无误。

前面我们说了，跟通用的默克尔树逻辑相比，只有生成节点的哈希的函数不同。具体来说，就是在原哈希函数之上，又包裹了一层，使得节点哈希变成形如‘minNs|maxNs|原哈希’的形式，minNs 和 maxNs 分别是此节点所有子节点中，最小和最大的命名空间。容易看出，对叶节点有 minNs = maxNs，因为它只包含一条消息，只能有一个命名空间。默克尔树是二叉树，且我们已对消息做了排序，所以对非叶节点有 minNs 等于左子节点的 minNs，maxNs 等于右子节点的 maxNs。另外，请注意原哈希函数会把子节点的整个哈希作为输入，也就是说命名空间也参与哈希计算，因此不能随意写，否则树根哈希会跟区块里的记录不一致，就很容易看出数据无效。下图是一个带命名空间的默克尔树的示意图（已经按层级优先方式对节点进行了编号 R1、H2...H15）：

首先，需要证明返回的某条消息，确实是在消息树中，这个就是普通默克尔包含证明所作的事情。因此，当存储节点返回一条消息时，它同时返回此消息的默克尔包含证明。假定返回消息 M0 到 Mn，那会同时返回对应的默克尔包含证明P0到Pn。我们需要说明，存储节点可以不返回某条消息，但无法对消息构成的默克尔树进行变动，因为那会导致树根哈希变化，数据失效。

现在我们来看漏消息的情况，首先我们的消息是按命名空间归并在一起的，所以如果某个命名空间，在它所有消息的中间漏了消息，那任何一个默克尔证明都可以看出，消息不连续，就没必要进一步讨论了。

我们看开头或者结尾漏消息的情况，两种情况类似，我们以开头为例。比如 N.2 的第一条消息 M.2 漏了，那它对应的 P.0 也不会发出来，那么这时候，从查询者的角度看，原来的 P.1（即M.3的默克尔证明），现在是第一个证明，它反正就检查第一个证明。下图，我画出了 P.0 和 P.1 的具体内容，我们比较它们的差别，就发现 M.2 左侧的节点，命名空间都小于 M.2 的命名空间，而 M.3 左侧有一个节点 H.4，它的 maxNs 是 A.2 等于 M.3 的命名空间 N.2，这个 A.2 的来源，就是存储节点隐藏起来的 M.2（参考 P.0 的图）。这样一来，执行节点就发现异常了。

那如果某个命名空间全部的消息都被隐藏呢。我们规定，当指定命名空间的消息不存在时，返回一个叶节点的默克尔证明，这个叶节点有 minNs 大于目标命名空间，但它左侧所有节点的 maxNs 都小于目标命名空间（按照上图，如果我们假定 N.2 是空的，那么应该返回 M.5 的默克尔证明）。那么，当存储节点隐藏了整个命名空间时，必然，根据具体返回的节点的位置（比如它返回 M.5 的话，其实相当于开头漏消息。那么它也可能返回 M.8 的默克尔证明），它或者左侧会出现一个 maxNs 大于等于目标命名空间的节点（H.14），或者（比如返回M.1的默克尔证明）右侧会出现一个 minNs 小于等于目标命名空间的情况（H.9）。这样执行节点也能发现问题。综上所述，存储节点不可能隐藏消息而不被发现。

本文复述了 Celestia 白皮书中，关于多应用场景下（类似分片或侧链），对抗恶意存储节点的部分内容。现在 Celestia 测试网已经上线，但目前更多是展示了对轻节点的支持，以及对消息分组的可行性。白皮书里面，第三章、第四章都有提到更多关于应用主权或者分片的内容，比较偏概念，针对真实公网环境来说，具体是怎么实现的，目前还看得不是很清楚。而扩容问题，显然是整个区块链领域近期最关注的目标。所以，我们之后也会特别关注 Celestia 在支持独立应用方面的进展，究竟怎么跟 L2 或者说其它‘区块链模块’结合起来，做到实用的功能，并提高链上容量，我们将拭目以待。

声明：本文内容仅供参考、交流，不构成任何投资建议。若存在明显的理解或数据的错误，欢迎反馈。

本文内容系 W3.Hitchhiker 原创，如需转载请标明出处。

商务合作：hello@w3hitchhiker.com

https://w3hitchhiker.com/

W3.Hitchhiker 官方推特：

https://twitter.com/HitchhikerW3

作者：Hoyt

有感于 Celestia 白皮书中，关于使用‘带命名空间的默克尔树’的相关章节，原文写得比较复杂，我们花了大量的时间去阅读，查看开源的示例代码，并和作者反复沟通才最终达成一致。而作为翻译，我们不能对原文的结构有太大改动，因此，为了使大家理解起来更容易，我们考虑单独发文，以更简明的方式向大家介绍相关内容。

为了实现链的容量扩展，Celestia 承诺主权应用将只需下载与其有关的消息（消息和交易的区别是，交易专指改变应用状态的消息），而不用下载全部消息，但同时，不同应用的消息是打包在同一个区块里面的，以实现平等的安全性。那么，如何保证当某个应用的执行节点向 Celestia 的存储节点查询消息时，存储节点仅返回所有的相关消息，而且恶意存储节点无法隐藏特定消息呢（注意这里跟数据可用性是不同的概念，那个是指不下载所有数据的轻客户端，如何确信数据可以被验证节点下载到）。

Celestia 选择的方案是，将称为命名空间的应用标识符，插入到消息构成的默克尔树的节点信息中。这样做的好处是，可以处理存储节点隐藏全部相关消息的情况，可以定位被隐藏的消息。另外，无需大幅度修改默克尔树的生成逻辑，以确保存在一个节点，它的底层叶节点，包含且仅包含某个命名空间的全部消息，且能定位此节点。而只需要做三件相对简单的事情，就可以确保默克尔树的基本特性，不发生变化：

1. 首先，生成消息的默克尔树之前，先按命名空间将消息分组归并在一起，确保不同命名空间的消息没有穿插，且命名空间是排好序的。

2. 其次，修改生成默克尔树时使用的哈希函数，以便命名空间信息被包含进节点信息（因为非叶节点，就只有哈希这唯一信息）。

3. 检查默克尔树时，额外检查排序是否无误。

前面我们说了，跟通用的默克尔树逻辑相比，只有生成节点的哈希的函数不同。具体来说，就是在原哈希函数之上，又包裹了一层，使得节点哈希变成形如‘minNs|maxNs|原哈希’的形式，minNs 和 maxNs 分别是此节点所有子节点中，最小和最大的命名空间。容易看出，对叶节点有 minNs = maxNs，因为它只包含一条消息，只能有一个命名空间。默克尔树是二叉树，且我们已对消息做了排序，所以对非叶节点有 minNs 等于左子节点的 minNs，maxNs 等于右子节点的 maxNs。另外，请注意原哈希函数会把子节点的整个哈希作为输入，也就是说命名空间也参与哈希计算，因此不能随意写，否则树根哈希会跟区块里的记录不一致，就很容易看出数据无效。下图是一个带命名空间的默克尔树的示意图（已经按层级优先方式对节点进行了编号 R1、H2...H15）：

首先，需要证明返回的某条消息，确实是在消息树中，这个就是普通默克尔包含证明所作的事情。因此，当存储节点返回一条消息时，它同时返回此消息的默克尔包含证明。假定返回消息 M0 到 Mn，那会同时返回对应的默克尔包含证明P0到Pn。我们需要说明，存储节点可以不返回某条消息，但无法对消息构成的默克尔树进行变动，因为那会导致树根哈希变化，数据失效。

现在我们来看漏消息的情况，首先我们的消息是按命名空间归并在一起的，所以如果某个命名空间，在它所有消息的中间漏了消息，那任何一个默克尔证明都可以看出，消息不连续，就没必要进一步讨论了。

我们看开头或者结尾漏消息的情况，两种情况类似，我们以开头为例。比如 N.2 的第一条消息 M.2 漏了，那它对应的 P.0 也不会发出来，那么这时候，从查询者的角度看，原来的 P.1（即M.3的默克尔证明），现在是第一个证明，它反正就检查第一个证明。下图，我画出了 P.0 和 P.1 的具体内容，我们比较它们的差别，就发现 M.2 左侧的节点，命名空间都小于 M.2 的命名空间，而 M.3 左侧有一个节点 H.4，它的 maxNs 是 A.2 等于 M.3 的命名空间 N.2，这个 A.2 的来源，就是存储节点隐藏起来的 M.2（参考 P.0 的图）。这样一来，执行节点就发现异常了。

那如果某个命名空间全部的消息都被隐藏呢。我们规定，当指定命名空间的消息不存在时，返回一个叶节点的默克尔证明，这个叶节点有 minNs 大于目标命名空间，但它左侧所有节点的 maxNs 都小于目标命名空间（按照上图，如果我们假定 N.2 是空的，那么应该返回 M.5 的默克尔证明）。那么，当存储节点隐藏了整个命名空间时，必然，根据具体返回的节点的位置（比如它返回 M.5 的话，其实相当于开头漏消息。那么它也可能返回 M.8 的默克尔证明），它或者左侧会出现一个 maxNs 大于等于目标命名空间的节点（H.14），或者（比如返回M.1的默克尔证明）右侧会出现一个 minNs 小于等于目标命名空间的情况（H.9）。这样执行节点也能发现问题。综上所述，存储节点不可能隐藏消息而不被发现。

本文复述了 Celestia 白皮书中，关于多应用场景下（类似分片或侧链），对抗恶意存储节点的部分内容。现在 Celestia 测试网已经上线，但目前更多是展示了对轻节点的支持，以及对消息分组的可行性。白皮书里面，第三章、第四章都有提到更多关于应用主权或者分片的内容，比较偏概念，针对真实公网环境来说，具体是怎么实现的，目前还看得不是很清楚。而扩容问题，显然是整个区块链领域近期最关注的目标。所以，我们之后也会特别关注 Celestia 在支持独立应用方面的进展，究竟怎么跟 L2 或者说其它‘区块链模块’结合起来，做到实用的功能，并提高链上容量，我们将拭目以待。

声明：本文内容仅供参考、交流，不构成任何投资建议。若存在明显的理解或数据的错误，欢迎反馈。

本文内容系 W3.Hitchhiker 原创，如需转载请标明出处。

商务合作：hello@w3hitchhiker.com

https://w3hitchhiker.com/

W3.Hitchhiker 官方推特：

https://twitter.com/HitchhikerW3