干货 | 分片的理念与挑战:区块链分片悬而未决的问题

干货 | 分片的理念与挑战:区块链分片悬而未决的问题

以太坊爱好者 发布在 链圈子 64841

在连载中的第一部分,我们讨论了为什么要做区块链分片及其他的重要概念。在本文中,我们从更前沿的角度来看分片,包含分片尚未解决的两大挑战:数据有效性和数据可用性。

简介

区块链分片的核心是,大部分操作或使用网络的参与者,无法验证每一个分片中的区块;同样的,无论什么时候,参与者与特定分片进行交互,他们一般无法下载和验证该分片的整个历史记录。

然而分片的这一侧面有着极大的隐患:如果参与者无法下载和验证整个分片的历史纪录,就不能确保他们与之交互的结果是否已经被写入区块,同时这样的连续区块在分片中是否合法(这些问题在未分片的区块链中是不存在的)。

关于上述问题,我们先重温一个已经被许多协议提过的简易解决办法,接着分析这个办法的缺陷,及相关补救措施。

基于假设的简易解决办法

 

关于数据有效性问题的解决办法最初如下:我们假设整个系统有数千个验证者,其中少于 20% 的验证者是恶意的或者会宕机(比如无法联机出块)。接着我们抽样出 200 个验证者,为了吻合实际意义,可以假设不可能超过 1/3 样本是恶意的。

1/3 是个重要的阈值。属于拜占庭共识( BFT )的一系列共识协议,都能保证只要少于 1/3 的参与者公识进程出错,不论发生节点崩溃或其他违反协议的情况,共识仍能完成。

假设诚实验证者占一定比例,如果分片中的验证者们提出某个区块,在验证开始前我们视该区块有效,并认为该区块建立在验证者认为当选的区块链(canonical chain,直译为“正统链”)上。当前验证者们会向上一阶段的验证者请求当选区块链(上一阶段出块过程符合假设,也接续当选区块链的头部、也就是最新的区块来出块)。经过递归查询整个区块链的有效性,而且没有任何验证者集合在过程中制造分叉的话,这种简易解决办法就能确定,目前的链在分片中的唯一性

假设验证者能够在一定程度上被腐化(如,接受贿赂),这种简易解决办法就失效了。这并非是个无厘头的想法(想知道更多关于高效腐化验证者的方法,可见此处)。破坏 1000 个分片中的一个分片,明显比破坏整个系统成本小很多。因此,随着分片的数量增加,协议的安全性也跟着线性下降。为了确定某个区块的有效性,我们必须知道到在任何时间节点、任何分片中,大部分的验证者都没有彼此勾结;因此一旦存在灵活型敌手(adaptive adversaries),我们就无法确定区块的有效性。如同我们先前讨论的,验证者如果相互勾结,会造成两种恶意行为:产生分叉和生成无效区快。

恶意分叉的问题能够通过和信标链的交互连接(crossl-link)来解决,因为一般来说 Beacon chain 具有比分片更高的安全性。但是,无效区块问题处理起来就非常棘手了。

数据有效性

在下图所示的情形中,分片 #1 被攻陷,恶意角色生成了无效区块 B (假设区块 B 中,Alice 的账户凭空多出 1000 个代币)。接下来,恶意节点紧接着区块 B 生成有效区块 C (换句话说,区块 C 中的交易被正确接受),借此掩盖无效区块 B;然后发起跨分片交易,将多出的 1000 代币发送到分片 #2 上 Bob 的账户。从此时此刻起,恶意创建的 1000 代币在分片 #2 中变得完全合法有效。

有些简单的方法处理这个问题:

  1. 要求分片 #2 的验证者,对发起跨分片交易的区块进行验证。这似乎无法解决上述问题,因为区块 C 貌似是完全正确的。
  2. 要求分片 #2 的验证者,验证发起跨分片交易的区块之前的若干( N )个区块。然而,对于任何要接受分片验证的 N 个区块 ,恶意验证者都可以在无效区块后面创建 N+1 个有效区块。
要解决这个问题,比较有谱的办法是:将分片放入无向图,其中每个分片都与若干分片连接,并且只允许与相邻分片发起跨分片交易( e.g. 这就是 Vlad Zamfir’s sharding 的大致内容,也与 Kadena’s Chainweb 的想法类似)。如果非互邻的分片需要发起跨分片交易,则这笔交易会通过多个分片进行路由。在这种设计下,分片中的验证者需要验证自身分片和相邻分片中的所有区块。下图中有 10 个分片,每个分片又有 4 个相邻分片,因而跨分片通信的中转次数必定不超过两次:

分片 #2 不只验证自己的区块链,也验证所有相邻分片的区块链(包括分片 #1 )。如果分片 #1 中的恶意角色创建无效区块 B ,并在其上添加有效区块 C 试图发起跨分片交易,分片 #2 也不会接受该交易。因为分片 #2 会验证分片 #1 的历史纪录,进而发现区块 B 是无效的。

虽然破坏单分片不再是可行的攻击方式,但如果数个分片遭到破坏就成了问题。下图中,攻击者破坏了分片 #1 和 #2,并成功向分片 #3 发起跨分片交易,其中包含无效区块 B :

分片 #3 会验证分片 #2 的所有区块而非分片 #1 的,所以无法察觉恶意区块的存在。正确解决数据有效性问题有两个主要方向:渔夫( fisherman )和密码学计算证明。

渔夫

渔夫方法的核心思想是:无论何时、出于什么目的,只要在跨分片之间传递区块头信息(例如和 beacon chain 交互连接,或是发生跨分片交易),都设置一段时间间隔让诚实的验证者提供无效区块证明。有数种简明的结构能证明区块是无效的,因此接收这种证明的通信开销远小于接收整个区块。

只要分片中存在至少一个诚实的验证者,则系统就是安全的。

这是当今提出的协议中采用的主要方法(除了假装问题不存在的其他协议)。不过,这个方法存在两个缺点:

  1. 这个挑战窗口期必须足够长,使得诚实验证者能够察觉、下载、验证新产生的区块,并准备好在识别出无效区块时提出挑战。引入这样的挑战期会大大地降低跨分片交易速度
  2. 挑战的存在会给攻击者带来新的武器,如发起无效挑战攻击。一个简单的解决办法是,让挑战者交一点押金,如挑战有效则退回。这只是个不成熟的办法,比如为了阻止诚实验证者提交有效挑战时,攻击者仍然乐于提交无效挑战(即使失去押金);这种攻击又被称之为 Griefing Attack(损人不利己)
在阻止无效区块方面,渔夫方法的两个缺陷都还未有令人满意的解决,不过仍聊胜于无。

简易的非交互知识论证

关于多分片崩坏的第二个解决办法是使用特定的密码学结构,使得人们有办法证明某种计算被确切执行(比如通过一组交易来计算区块)。这种结构确实存在,比如 zk-SNARKs 、 zk-STARKs 等等,它们也被广泛用于今日的区块链协议中,像是我们熟知的 ZCash 。这类结构最令人诟病的是计算速度慢的令人发指,像是使用 zk-SNARKs 来证明所有链上区块有效性的 Coda 协议 ,据说每笔交易需要花 30 秒来创建一个证明(这个数字现在应该小了点)。

有意思的是,除了对计算的有效性作证,这种证明还能自证自己的有效性,不需要通过可信第三方。因此产生这种证明的计算量能够在一组参与者中进行分配,其冗余明显小于某些免信任型计算。 zk-SNARKs 允许参与者在特殊硬件上进行计算,不会降低系统的去中心化程度。

zk-SNARKs 除了性能方面的挑战,还包含:

  • 其依赖的加密技术较少被研究及测试。
  • “冗余计算( Toxic waste )”——  zk-SNARKs 基于一种可信设置,要求一群人进行计算并舍弃中间值。如果所有参与者进行勾结并保留了中间值,则可能伪造证明。
  • 在系统设计中加入额外的复杂性。
  • zk-SNARKs 仅适用于一部分计算,因此具有图灵完备智能合约语言的协议无法使用 SNARKs 方法来证明其链上区块的有效性。
虽然许多协议都考虑在将来使用 zk-SNARKs ,但除了 Coda 之外,我不知道还有没有其他的实行计划。

数据可用性

我们在最初提到的第二个问题,是数据可用性问题。一般来说,操作某区块链的节点被分为两类:全节点,这种节点下载所有区块并验证每一笔交易;轻节点,这种节点只下载区块头,并只针对部分感兴趣的状态或交易使用 Merkle 证明。

如果大多数全节点勾结在一块儿,它们可以随意生成有效 or 无效的区块,并发送其哈希值给轻节点,而且不揭露该区块的内容。这些全节点能够以这种方式受益,如下图所示:

有三个区块:前一个区块 A 由诚实验证者产生;当前区块 B 由勾结的验证者产生;下一个区块 C 仍然由诚实验证者产生(右下角描绘了区块链的样子)。

假设你是个商人。当前区块 B 的验证者从前面的验证者处收到区块 A ,并计算出你应收到的钱,接着向你发送该区块头,其中包含你拥有这笔钱的状态(或“将钱发给你”的有效交易)的 Merkle 证明。你以为这笔交易无误,然后交付了服务或货品。

然而,验证者不会将区块 B 的内容发送给任何人。因此生成区块 C 的诚实的验证者收不到区块 B ,从而被迫继续接着区块 A 出块,这就变相夺走你作为商家所收到的钱。

当我们将同样的场景转移到分片,全节点和轻节点的定义仍然适用:每个分片中的验证者会下载并验证所处分片中的所有区块和交易,但系统中的其他节点(包含将分片状态快照到 beacon chain 的节点)只会下载区块头。因此对于某一条分片链来说,它的验证者就是全节点,其他系统参与者就是轻节点

我们前面提到的渔夫方法,要求诚实验证者能够下载与 beacon chain 交互的区块。如果恶意验证者交互连接无效的区块头(或是使用无效区块头发起跨分片交易),然后不揭露区块内容,则诚实验证者就无法发起挑战。

关于这个问题,我们将介绍两个解决思路,它们是相辅相成的。

监管证明(Proof of Custody)

我们要做的是避免区块一经发布就立即被使用。一种想法是让所谓的 “公证人(Notary)” 在分片之间轮转,它们唯一的工作就是下载区块,并 “证明这些区块能被下载”。公证人能够更快地在分片间进行轮转,因为相较于验证者,公证人不需要下载某个分片的完整状态。

这个方法天真之处在于,无法检查公证人是否真的尝试下载区块,所以公证人可以始终表明区块是可以下载的,却不进行尝试。其中的解决办法是要求公证人提出证明,或是抵押一些代币作为区块能下载的保证金,更多讨论详见此处。

修正码

当特定轻节点收到区块哈希时,为了增加区块可用性的可信度,轻节点可以随机下载该区块的片段。这不是个圆满的解决办法,因为除非轻节点下载整个区块,不然恶意节点仍然能够选择部分未公开的区块内容提供给该轻节点,最后区块数据仍是不可用的。

解决办法是引入叫做“修正码”的结构,使得即便只有部分区块内容可用,也能还原出整个区块:

Polkadot 和以太坊 Serenity 都围绕这个想法进行设计,希望为轻节点提供一种方法,让他们能够确信这些区块是可用的。以太坊 Serenity 的设计详见此处 。两方提出的办法都是基于挑战时间所设计的,因此唯一的潜在问题就是 griefing attack 。

长期可用性和结论

提醒一下,上述方法都只能证明区块已经发布,且当前可用。可能出现以下情况使得区块在稍后的时间里变为不可用:节点掉线,节点故意抹去历史数据,等等。

关于这个议题, Polyshard 白皮书值得一看;即使出现数个分片丢失数据的情况, Polyshard 的修正码方案仍能保证分片之间的区块可用性。不过可惜的是,这个方法要求分片间要下载彼此的所有区块,使得成本非常高昂。

还好长期可用性并不是个迫在眉睫的事。因为系统中的参与者不被预期能够验证所有的分片链,所以分片协议应该按照这个思路设计:即使某些分片中的部分旧区块变得完全不可用,系统仍然能保证安全

在设计安全协议时,数据有效性和数据可用性问题仍然没有完满的解决办法。我们会继续研究这些问题,请继续关注和更新我们的消息。

 

感谢 以太坊基金会的 Justin Drake 、 Polkadot 的 Alistair Stewart 、Cosmos Protocol 的 Zaki Manian 、Kadena Protocol 的 Monica Quaintance 及 Interstellar 的 Dan Robinson对本文的审稿及反馈。


原文链接: 

https://medium.com/nearprotocol/unsolved-problems-in-blockchain-sharding-2327d6517f43

作者: Alexander Skidanov

翻译&校对: IAN LIU & 阿剑

本文由作者授权 EthFans 翻译及再出版。

文章标签: 以太坊 分片
评论
登录 账号发表你的看法,还没有账号?立即免费 注册