Celestia:如何确保消息检索结果的完整性
W3.Hitchhiker
2022-07-04 22:27
行业洞察
阅读本文需 5 分钟
存储节点不可能隐藏消息而不被发现。
原文标题:《Celestia 如何确保消息检索结果的完整性》
原文作者: Hoyt,W3.Hitchhiker


写作本文的原因:


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


问题的由来:


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


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


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


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


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


生成带命名空间的默克尔树:


前面我们说了,跟通用的默克尔树逻辑相比,只有生成节点的哈希的函数不同。具体来说,就是在原哈希函数之上,又包裹了一层,使得节点哈希变成形如『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 或者说其它『区块链模块』结合起来,做到实用的功能,并提高链上容量,我们将拭目以待。


原文邻居
默克尔树
行业洞察
从现象看到本质,寻求加密真相
相关文章
5小时前
行业洞察
Curve生态热度再起,这个DAO开发的项目一定要关注
关于Curve生态的讨论热烈,而价格大涨的Concentrator、CLever和Conic Finance中,有两个都由AladdinDAO开发。
21小时前
行业洞察
即将空投?从数据看看Lens生态发展的怎么样
Nostr应用Damus上架仅一天后,Lens Protocol创始人便发布了疑似空投快照相关的推文,社交赛道的爆发或已箭在弦上。
22小时前
行业洞察
热门文章
试试Nostr的首个客户端Damus,推特创始人认可的Web3新社交
试试Nostr的首个客户端Damus,推特创始人认可的Web3新社交
即将空投?从数据看看Lens生态发展的怎么样
即将空投?从数据看看Lens生态发展的怎么样
一个月市值翻倍,Gains Network凭什么单日营收打败GMX?
一个月市值翻倍,Gains Network凭什么单日营收打败GMX?
基于SudoSwap的Launch平台:不会代码也能一键发售NFT
基于SudoSwap的Launch平台:不会代码也能一键发售NFT
Binance新链BNB Greenfield究竟是什么?
Binance新链BNB Greenfield究竟是什么?
下载 BlockBeats APP
商务联系
商务联系
我要投稿爆料
投稿