对分片的技术分析及时织者分片idea

作者:@香橙

尽管CKB最初并未考虑分片,因为分片设计过于困难,同时有可能影响Layer1的安全性,但是回顾分片带来的经验对于模块化区块链的设计是有益的,因为它们面对的核心问题是一样的,而CKB如果想采用分片技术的话,有多种路径可以在模块化区块链网络Nervos中加入分片设计,一是直接升级CKB主链并在其之上实现分片,这很难并且会带来非常多的问题,包括网络层、经济模型等,二是设计一个由CKB为锚定结算层的侧链,并在侧链上实现分片。

1. Sharding与扩容困境

1.1 扩容困境

如何让抗审查且无准入的公共区块链可扩展,是一个微妙而又困难重重的问题,但又因其重要性,对扩容的问题的种种答案形成了区块链底层技术发展的核心脉络,从大区块与隔离见证之争引发的BTC分叉大战,到EOS超级节点争抢,再到Rollup以及各种零知识证明方案的提出,扩容贯穿区块链发展史,如今虽已曙光初现,但还尚未完美解决。

区块链领域存在一个广为人知但并未有过多证明的论断,即区块链扩容的不可能三角,公链无法同时达到可扩展(Scalability)去中心化(Decentralization)安全(Security)

  • Scalability: 链可以处理超过单节点可验证的交易。
  • Decentralization: 链的运行不依赖对任何中心化节点的信任,通常意味着大部分人可以用自己的设备运行全节点验证交易。
  • Security: 链能抵抗多高成本的攻击。

此论断一定程度上揭示了区块链扩容面临的问题权衡。比如说,通过简单的提高验证节点门槛可以大大增加TPS,但却极大降低了去中心化,如Solana,EOS。

但仔细分析,这个论断又非常含混不清,以现有的Layer2技术(如zkRollup)为例,其简单复用了主链的安全性并将状态与计算搬至链下实现扩容,以最简单的转账为例,zkRollup只需要定期的状态验证以及每笔交易约20Byte的链上吞吐占用,假设链提供32KB/s的吞吐,即可将TPS提高到1600,在得到这样的扩展性同时,我们付出了什么呢?

在区块链的语境下,去中心化和安全性这两个词总显得有些含混不清,它们像是在描述同一件事,又似乎有点不一样,什么样的区块链是足够去中心化但不安全的呢?貌似Bittorrent系统这类非区块链系统才符合定义,而且很多PoS链非常简单地把质押金额作为其攻击成本的评价标准,仿佛这只是个资本问题而不是技术问题。

通过分片或者Layer2,逻辑上是可以同时达到可扩展、去中心化和安全的,Vitalik的文章在Why sharding is great: demystifying the technical properties (vitalik.ca)中也认为合理的分片技术可以同时满足不可能三角(虽然目前并未出现这样的系统)。一边说这是个不可能三角,一边又有一堆人说可以同时满足,是不是以往的不可能三角并未触及本质呢?

当我们把状态从主链切割一部分到Layer2或者分片链以后,虽然我们得到了扩容,但是状态的切割不可避免地影响了可组合性,不同的状态之间的交互以及资产都被割裂,互相独立的状态层越多,其割裂就越甚。但是从分层区块链的角度来说,切割成多个状态是能在扩容的同时增加去中心化的,因为每个节点只需要验证主链交易以及自己资产牵涉的相关分割状态的交易即可保证安全,这使得不同状态层之间达到了某种共享安全性。

如果我们把去中心化并入安全性,再将不可能三角的权衡改成,可扩展(Scalability)可组合性(Composability)安全(Security),这三个角的权衡相比原有的就更清晰一点,并且无论是分片还是Layer2,都很难真正打破这个不可能三角。可能无论是采用分层还是分片的设计,最终可能面对的问题都是类似的,但是分层路线的实现难度要远低于分片。

当通过分片或者Layer2得到更高的性能后,我们想在交易时使用更强假设的可组合性,那么原本获得的性能提升就会更多的还回去,因为在多个分割状态上组合的成本必然高于单链内部的组合。并且由于阿姆达尔定律,如果有许多需要强组合的交易的话,状态分割就不会带来太多性能提升,这个瓶颈会到来地非常之快。如果我们需要完全同步的可组合性,且大部分交易都涉及多个分片状态的同步组合,那总体的性能甚至低于单链。

但新不可能三角虽难以打破,但却有弥补的手段,因为可组合性的权衡可能没有明显的分界,这是一个可以交易的维度。好在这个世界其实并不需要那么多的同步组合,比如异步跨分片转账,只涉及两个分片里两个状态碎片的异步组合,绝大多数的应用都不需要全局组合所有状态的潜力,我们可以让渡这部分不需要的可组合的潜力,去换取更高的性能。并且可以存在许多非原生的可组合性方案,它们不会影响安全性。

跨状态层的资产互换,只要有人愿意提供流动性,通过哈希锁,可以实现既安全又去中心化的资产流动,但是这个成本并没有摊给底层的基础设施设计,而是因为流动性提供者为了赚取手续费提供的。比如对于两个OptimisticRollup之间的资产互换,按照既定规则需要很长的挑战期,但是服务商如果运营了自己的节点并检查了所有的状态转换,则可以放心地提供互换服务以赚取手续费。此外,应用自身可以利用密码学等方式实现逻辑上的组合,如dAMM。

1.2 分片简述

接下来要回答的问题是,什么是分片?最直接的解释是,分片就是由一条单链变成多条链并行处理交易,从而使得整体的处理能力超出单机。

根据分片的特点,可以将其分为三类分片,网络分片、状态分片和计算分片,分别对应了验证交易需要的网络成本、内存成本以及计算成本。

  • 网络分片

实现网络分片后,网络将根据分片划分为多个子网,交易数据传输无需广播全网,大部分的片内交易只应该在片内广播,可以大大降低跑一个节点的带宽需求。

  • 状态分片

实现状态分片后,任何一个节点都无需存储全网状态即可参与验证,只需要保存自己片内的状态即可,可以大大降低跑一个节点的内存需求。

  • 计算分片

实现状态分片后,任何一个节点都无需验证全网所有的交易,只需要验证自己片内的交易即可,可以大大降低跑一个节点的CPU需求。

如此说来,Layer2已经是事实上的分片了,如Rollup方案已经相当于分片里的状态分片与计算分片,通过Godwoken,CKB的TPS理论上可以超出CKB单链的处理能力,从而做到可扩展。通过对比现今的分片和Rollup使用的技术,可以发现它们在很多方面是类似的,如欺诈证明、有效性证明、数据可用性保证等等。

相比最理想的分片,Rollup缺少网络分片,这在Layer2的语境里被称为数据可用性问题,即使交易被压缩,Rollup的交易依然要和主链争夺网络资源,在同一个队列里排队按序进行。而这限制了某条链依赖Layer2扩容的上限,在Rollup的基础上,我们所说的Sharding其实只要再多解决网络分片这一个问题即可。以太坊的最新路线,通过发展zkEVM,继而实现数据分片而非执行分片,在某种程度上是他们给出的答案,zkEVM的零知识证明可以在执行层得到验证,而压缩的交易只提交到数据分片中,相当于给Rollup打了一个网络分片的补丁,通过此般曲折的方式,同时实现计算、网络、状态三种分片。

虽然本文继续使用了Layer1、Layer2以及Sharding之类的术语,但顺着这条路径往下走的时候,这些区分似乎过于严格,当把瓶颈逐个击破再像乐高积木办拼起来的时候,这种分层且模块化的架构,很难说某个是Layer2或是分片,事实上,我们只是用各种方式去突破最核心的问题,即谁检验状态转换的有效性,谁保证数据可用性,谁提供可组合性服务,这些服务事实上可以不由同一个基础设施来保证。

1.3 分片的核心问题

从最开始提出分片之梦,到对Plasma的蓄势待发,再到Rollup对Plasma的妥协,分片最重要的问题慢慢明晰,可以分成三点,即状态有效性验证,数据可用性保证以及跨片通信机制。在早期的分片设计中如Omniledger和Rapidchain之类的方案,往往注重设计跨片通信机制,而几乎不关注前两个问题。

1.3.1 状态有效性验证

状态有效性验证的问题,在最早的分片设计中,往往只是用随机数把全网节点随机分组来验证状态,从而保证恶意节点分到一组的概率足够低。但是为了性能,其轮替的时间可能长达几小时甚至一天,这种设计的安全保证并不能达到公链的需求,因其只保证分组的时候以极大概率不把作恶节点分到一组,只能抵抗Slow Adaptively的攻击者,无法解决在分组后的委员会腐化问题。

这个问题的初步解决是有效性证明和欺诈证明的提出,从而使得一小部分节点验证交易,其他节点仅作为近似轻节点的存在,就可以使得所有交易得到近似全网的安全保证。

1.3.2 数据可用性保证

数据可用性问题在早期的分片设计也较少考虑,而Plasma路线的碰壁所带来的讨论,使得数据可用性成为了扩容的核心问题,这自然也是分片需要去面对的。Elrond的方案使用邻居分片互相备份来保证数据可用性,但这种方案并没有做到全网共享安全性,因为同时攻击两个分片。

目前最主流的方案是使用编码冗余同时结合随机采样来保证数据可用性,使得出块节点无法不公布区块内容以错误出块。

1.3.3 可组合性/跨状态通信机制

早期的分片设计讨论最多的就是跨片通信机制,以及如何随机分组以防止合谋,但即便如此,目前跨片通信机制依然很难解决的问题。这不难理解,因为分片本身就是先放弃了可组合性,再反过来重新索取,自然很难。

大部分跨片机制都是异步收据的或者两阶段锁,如Ominiledger通过对资源加锁再执行交易,而Rapidchain通过将资源通过多个异步操作,最后汇聚到某条单链处理。

但也许基础设施本身可以只提供有限的可组合性,同时将更多组合性需求放置上层实现,毕竟计算机领域的任何问题都可以通过增加一个间接的中间层来解决,模块化区块链内部的分片或者Layer2之间的组合,一定是比多条单链的组合要简单很多的。

所谓的“火车与旅馆”问题,在现实世界也是一个无法解决的问题,只有两个服务处于同一个运营商的运营范围才能做到,类比到分片,即只有处于同一个分片下才能保证,追求在全球任何一个地方与另一个地方的服务可以做到完全同步,必然是极其低效的,这会让我们花更长的时间等待时间光锥覆盖全部范围,想在去中心化且安全的同时达到可扩展,还能保持这样的可组合性是不可能的。

2. 准入机制之分

目前公链最主流的准入机制是PoW与PoS,而PoS更适合分片貌似已成定论,因为PoS可以在每个Epoch提供一组准确的验证人列表用于随机抽样,可以非常简单地实现节点的分组。

但直觉未必正确,PoW和PoS作为准入机制,并没有限制分片或者其他的设计,重要的是找准不同准入机制的限制然后去解决。

下面略分析下二者的存在的问题。

2.1 算力分散

PoW的一个很重要的问题是算力分散,直觉来看,如果将链分成1024个分片,那么一个分片的算力只有原来的0.1%,只需要全网0.051%的算力,即可攻击某个分片。

而对于PoS来说,只要存在无偏随机数源,即可以在概率上保证一定比例的恶意节点聚集在一个分片的概率非常小。PoW也可以设计委员会型分片,Rapidchain是一个用PoW准入的委员会型分片,通过随机数算法进行委员会分组。

但委员会形式并不适合PoW准入机制的分片,因为不同节点算力分布是非常不均匀,很难调整出合适的门槛难度,Rapidchain假设所有节点拥有均等的单元算力,与现实算力分布完全不符合。

2.2 区块重组

假如某分片接受了另一个分片的跨片交易,而交易的对应源区块被重组,这将导致跨片交易失效,从而产生连锁反应,影响到其他分片的状态。对于概率性收敛的中本聪共识来说,区块重组是不可忽略的,尽管可以通过延迟跨片交易来缓解影响。

但这个问题并非PoW准入共识独有,在PoS分片链中,如果有分片被挑战而检查出作恶行为,涉及到的其他分片一样会受影响,如Near在夜影中描述的欺诈证明举报成功后,涉及的分片段会作废。

2.3 随机数源

由于担心有恶意验证人接管某分片,所以PoS的分片往往都需要有一个随机数生成算法,以随机在所有验证人中采样,从而确保恶意验证人无法分在一组。但理想的伪随机数生成并不简单,包括Dfinity的阈值中继、Randshare以及Randhound,需要借助PVSS(Publicly Verifiable Secret Sharing)或者纠删码,这些方案都涉及多轮通信交互,其通信复杂度为O(n^2)甚至O(n^3),难以支撑大量节点,而有些链使用VRF甚至简单地使用链上区块作为随机源,这些算法并没有理想的无偏特性,从而使得后面的概率分析都不再可靠。

Near最早决定RandShare的改进版本,见Randomness in blockchain protocols - NEAR Protocol,后来又提出要使用类似Dfinity的基于DKG的随机数生成,Randomness Beacons based on Threshold Signatures (near.org),但目前Near使用的随机数依然只是当前出块人对上一轮随机数进行VRF得来,而波卡使用最近的一些区块,都不具备完美的无偏性。

当然,对于Rapidchain这类PoW准入的分片链来说,在随机数源也面临同样的问题,因为需要给委员会分组。

2.4 轮替与状态切换

随机采样并不只进行一次,因为委员会会腐化,而为了缓解这个问题,委员会需要定期轮替,由此带来的问题是定期的重网络开销和状态切换,由于每次轮替都会有一些节点被切换到其他分片,它需要提前同步对应分片的状态,以验证对应分片的交易。

让分片在当前分片就能知道自己所属的下一个分片,可以让其提前准备好状态,否则在轮替后要立刻同步状态会导致服务暂停,但如果能验证人的置换序列可以提前得出,就可能影响链的安全性。

波卡在这个问题上使用了更激进的方案,即中继链不存储平行链的状态,而只作为轻节点存在,平行链的收集人提交区块不仅包含交易也包括状态转换的有效性证明,这种设计也带来了新的问题,如网络负载高(因为区块内包含合约字节码和有效性证明),以及必须依赖平行链存在足够可信的收集人,这个模式更类似Rollup。

2.5 长期数据可用性

目前的许多基于委员会的分片算法,为了保证数据可用性都是直接将数据纠删码处理后发送给验证人,由于验证人的变换,可能导致中间某个区块的数据可用性达不到最低保证,从而使得无法从头检查某个分片的历史。当然,在归档交易占据磁盘的空间过大以后,正常的链节点都可能扔掉早期的链数据而只存储当前状态。数据可用性采样分片以及Polyshard,可以使用编码缓解这个问题,但长期来说,可能不得不采取检查点之类方案。

2.6 PoW与PoS的其他问题

由于大部分的PoS系统都依靠对作恶验证人的罚没来限制其作恶,所以PoS的运行在币本位是有可能受损的,很有可能因为开发原因,导致一部分验证人不自觉做出了违反协议的操作,从而导致无辜的验证人质押被罚没,这对于整个系统的稳定性是重大打击,而再考虑分片的话,在设计以及节点运维上难度更大,由此带来可能的问题也更多,相比之下,无论出现任何问题,PoW并不会导致矿工在币本位无辜受罚,仅有得不到出块奖励的风险。

当然,PoW最为人诟病的其需要通过能源输入来保护链的安全性,这一点孰优孰劣在不同的人看来是完全不同的,有些人认为这和开汽车烧油费电一样是取舍,而另一些人则认为这是纯粹的能源浪费。

3. Extended UTXO模型与Account模型

除了PoW与PoS之分,在编程模型上,也存在UTXO和Account两种,虽然目前账户模型几乎可以说占据压倒性优势。以往在对UTXO的批评中,最主要的批评是难以支持复杂的智能合约,但在对UTXO进行改进后,ExtendedUTXO也可以支持复杂的智能合约,如Nervos使用的Cell模型。

3.1 处理区块重组

在分片中,如果跨分片交易的源交易所在的区块重组,导致这笔交易无效,最简单的做法可以是让所有涉及的区块全部作废,但这无疑是很浪费资源的一件事。

能不能从当前的状态撇清所有无效交易的影响,而不是简单的丢弃呢?对于账户模型,如果想要撇清失效交易的影响,只能通过在失效交易之前的检查点重放所有正常交易才行,这是一件十分耗费资源的事,所以对于采用账户模型的分片链如Near,如果跨链交易失效,打包了对应交易的区块也是要作废的。

而对于EUTXO来说,可以追溯并标记失效交易的整条路径,从而将其影响的状态碎片全部恢复原状,而不影响其他的正常交易。

3.2 处理手续费

在分片里另一件棘手的事,是处理手续费,当一个交易涉及到多个分片时,如何支付手续费?

对于账户模型,这是一件比较棘手的事,因为两条公链的负载并不一样,如果采用收据模式,怎么能合理得给目的分片付手续费呢?账户模型下可以采取预留Gas等方案,但是由于EUTXO是隔离的资产单元,在跨链过程中,可以自己支付自己的跨链手续费。当然,这是最粗略的设计,因为用户可以和分片节点合谋欺骗,导致交易作废,浪费另一个分片的资源,但EUTXO在这类问题上可能确实有优势。

3.3 其他特点

EUTXO与账户模型相比,可以实现更好的并行化以及无状态性,但由于缺乏共享状态,导致某些强依赖共享状态的应用(如Uniswap)在EUTXO上开发非常困难。

EUTXO只有结合Layer2才能更好地释放潜力,把共享状态放在链下后,可以在Layer1规避状态存储问题,而使Layer1更注重资产与价值存储,EUTXO天然的资源分割也使得不同Layer2的状态转换推进互不影响,相比账户模型无疑更贴切Layer1,服务于Layer2,可参照另一篇文章:Idea: 以CKB为Kernel的模块化区块链网络Nervos

4. 实例简析

虽然可以把Rollup也认定为是一种分片,但依照惯例将Layer2单独归为一类。并且不会描述细节,而只勾勒该路线的大致特征。

4.1 Shardings

4.1.1 OmniLedger

Omniledger,使用Randhound算法生成随机数,然后进行委员会分组,组内使用byzcoin的共识算法,跨分片交易是由用户端驱动的,即先对涉及的状态都加锁再执行,类似两阶段提交。

简单的随机委员会分组解决不了委员会腐化的问题,对于其他分片的数据可用性以及状态转换的正确性未做检查,并且状态轮换也存在前所述的问题。

4.1.2 RapidChain

使用PoW作为准入机制,通过计算一个PoW获得参与共识的资格,需要在初始选出C_R来生成初始随机数,然后连续使用随机数驱动后续的委员会轮替。跨片通信使用由委员会端驱动的算法,即将涉及多个分片的UTXO交易拆分成多笔交易,先将所有涉及的UTXO跨到一个分片,再做执行。同时在传输的时候还使用了Information Disperse Algorithms加速传输,我理解就是用纠删码传输可以减少开销。

问题与OmniLedger类似,并没有解决Omniledger最本质的一些难题。

4.1.3 Monoxide

Monixide是一篇投中NSDI的论文,初看令人惊喜,仔细琢磨后则感觉Monoxide并没有解决问题,只是用各种机制回避问题。

Monoxide定位了一些问题比如最终一致性、PoW的算力分散等,首先Monoxide提出使用收据机制来实现最终的原子性,这是一个比较常见的设计,而对于算力分散,Monoxide提出了连弩挖矿,其本质和联合挖矿差不多,就是让矿工可以同时挖多个编号连续的分片链,另外由于论文使用了PoW算法,所以可能会区块重组影响跨链交易,Monoxide论文以账户模型为例,采用了检查点+重放所有正常交易的机制。

当我们从最核心的状态转换有效性、数据可用性、跨片通信等方面来分析Monoxide时,就能发现它的很多问题。首先Monoxide分片链的状态转换有效性没有任何由其他分片链进行核验,数据可用性也没有,跨片通信机制仅使用了简单的收据模式,同时由于没有对分片收敛做额外限制,发动区块重组的难度总是低于全网难度的。

论文中声称连弩挖矿可以让每个分片链的攻击难度达到与全网算力保护下类似,这只有在全网所有节点都进行连弩挖矿才行,而这就变成了简单的单链,另一点是连弩挖矿总是能在分片上均摊放大自己的算力,理性的矿工会同时挖所有分片,即使他们没有足够的内存和计算能力,也可以通过出空块来获得区块奖励,这同样会使得分片无意义。而Monoxide的检查点重放交易的机制,实现起来也过于复杂。

总而言之,Monoxide作为一个分片链,没有解决分片的核心问题,推导过程也有许多不合理的地方。

4.1.4 Near

参见jjy的摘要总结,Nightshade - Near 协议分片设计 (justjjy.com)

4.1.5 Polkadot

按波卡的说法,其设计为异构分片链的架构,波卡中最重要的组件的中继链和平行链,中继链负责给所有平行链提供共享安全验证平行链区块,平行链作为承载应用状态与计算的地方,同时平行链之间可以通过波卡设计的通信机制通信。

但与其他分片不同的是,中继链并不存储平行链的状态,仅只相当于平行链的轻节点,这使得波卡的架构更像是Layer1与一堆Layer2的关系。

在波卡的设计中,首先平行链会出块,然后由收集人(通常只有一个,类似Rollup的定序器)将区块传送给中继链的验证人,中继链被挑中的验证人验证区块后,该区块就会成为候选收据,最后打包进中继链的区块中。平行链打包的区块中不仅包括交易,还包括交易引用的合约码以及交易执行所引起的状态转换的有效性证明。中继链会用VRF给每个平行链随机挑一些验证人执行验证任务,如果验证通过,则将该区块用纠删码进行编码,并将碎片分发给所有的验证人,然后作为候选收据放入交易池。

这种模式在一定程度可以保证状态转换验证、数据可用性和跨片通信的安全性。但平行链区块除了交易外还需要挺多额外数据,这限制了平行链数量的上限,同时由于只抽10个节点验证一个平行链区块,1000个节点里就算只控制100个节点都有极大概率控制某个平行链区块的验证。并且波卡并未实现渔夫机制,每个平行链仅抽取约十个节点验证平行链,再在中继链出块的时候再挑选一些验证人对所有平行链区块做二次验证,这使得其很难称得上有全网的安全性保证。另外,按照波卡的设想,平行链运行不同的应用,然后再在基础层设计非常全面的跨片通信机制,但按逻辑来说,如果基础层的跨片通信非常多的话,它对性能的影响也是极大的。

4.2 Rollups

4.2.1 Optimistic Rollup

Optimistic Rollup基于欺诈证明,并将所有交易数据放在链上,任何节点可以在挑战期内对错误交易发起挑战,以威慑提交L2区块者不作恶。

但是Optimistic Rollup也有一些问题,比如说可能遭受L1的审查攻击,强行让错误交易通过,另一点是Optimistic Rollup越安全,第三方的核验可能就会变弱,也会影响其安全性,在使用上Optimistic Rollup会带来非常长的资金提取延迟。

从分片的核心问题去考虑,Optimistic Rollup数据可用性由Layer1保证,状态转换由Layer1仲裁,可组合性除了官方桥之外,还有许多第三方的资金桥。

4.2.2 ZK Rollup

ZK Rollup是基于有效性证明的Rollup,相比Op,ZK Rollup没有那么长的提取资金延迟,并且其交易理论上可以压缩得比Op小很多,但是zkRollup电路设计比较复杂,基于zkSNARKs设计的链下证明耗时过长。总的来说,zk Rollup在安全性假设以及可扩展性的想象力上都要优于Op Rollup,但通用Layer2的工程实现慢于Op Rollup。

SNARK-based: appliedzkp/zkevm-circuits
STARK-based: maticnetwork/miden: STARK-based virtual machine

5. 时织者分片_TimeWeaver Sharding(idea阶段)

5.1 概述

Rollup技术已日臻成熟,分片也可以从中得到很多经验,时织者就是一个按照Layer2的思路去设计的分片协议。

时织者的设计旨在兼容PoW和PoS等共识算法,同时可以采用账户模型,也可以采取UTXO等编程模型。目标是在状态转换的有效性验证上能做到接近全网算力/权益的保证,并且数据可用性也有接近全网的保证,在此基础上,只实现最基础的跨片通信机制。

时织者源于一个朴素的想法,在不考虑随机信标,不考虑委员会轮替,不以验证人为单位而是以分片为单位作为处理单元,同时放弃所谓的「最终确定性」,在去除这些惯性思维后,去重新思考如何设计一个新的分片方案。

  • 存在一个主链,用于一些全局同步的信息(如Stake分配等),每个分片链都同时联合挖矿自己选的分片链和主链,所以主链的可靠性是由全网保证的,但是不允许矿工同时挖多个分片链。以一个PoW作为主链,同时将所有的分片链的stake锚定在PoW主链上也许也是可行的。
  • 数据可用性保证,每个分片的数据除了本分片存储全部以外,还需要通过纠删码将其分散到每一个分片来保证可用性,同时分片会对其他分片的某个区块头进行可用性投票。简单举例,128个分片,采用(43,85)的纠删码,每个分片都需要额外存储1/43的其他链数据,所以账本存储上,需要存储1/43 * 128 + 1 = 4倍的账本数据,即本链全交易历史+其他分片碎片,由于任意1/3的分片都可以恢复出完整的历史,可以认为每一条分片链都具有全网保证的数据可用性,同时可以设置有1/2以上的分片认可某区块头的可用性,该分片链区块就被锁定。数据可用性投票可以用累加器,或者随机采样等方式减少通信开销。
  • 状态有效性保证,由于每个分片链都持有其他所有分片的区块头,从而作为一个轻节点可以检查关于任何一个分片在任意区块高度的欺诈证明。假设有人提交了关于某分片链区块有效的欺诈证明,那么该区块的锁定状态将被取消,同时丢弃该区块及其后面所有的区块,欺诈证明有两种,一种是错误的纠删码编码,另一种是错误的状态转换。由于前所述的数据可用性保证,任何全节点总是可以构造这样的欺诈证明。
  • 分叉收敛保证,如果没有轮替,无论是PoW还是PoS,他们的小算力/权益可以一直出块但不收敛,或者在分片内以极低成本进行审查攻击,从而影响可用性。可以用DAG计算分片链之间的投票关系,只要满足一定阈值的分片(如1/2n+1)给某个区块头指代的数据可用性投票,那么它就处于锁定状态,除非有人成功提交了该区块头的欺诈证明,否则分片不再接收不在这个区块后面出块的区块。但某些时候仍可能导致不收敛,可以辅助使用Avalanche之类的概率抽样来加速收敛。
  • 轻节点,处于“钉住”状态的区块在经过一些时间后,可以将所有分片的区块头内的交易根求一个MerkleRoot,提交在一条由全网所有节点联合挖矿的主链上,从而使得其他节点只需要监控这条主链的区块头,即可以作为全网的轻节点而存在,避免了分片和DAG很难构造轻节点的问题。
  • 恶意节点占据分片问题,对于PoW挖矿来说,只用同步状态,任意算力总是可以在分片间随意迁移,这使得恶意算力盯上的分片可以很快被算力稀释,同时对于PoS,由于存在一条联合挖矿的主链,其Stake信息由主链记录,则也可以在主链将自己的份额在分片间自由转移。

该设计秉持着这样一种观念,在真正去中心化的公链中,出块人只是给用户提供服务的服务者,同时赚取服务费,而公链真正的安全性是由海量的全节点保证的,所以分片设计必须将全节点的运行成本降得非常低,同时让全节点拥有获得任意一个分片的区块与状态的能力,以监督分片出块节点,而不是完全将安全性依托在验证人不合谋、矿工算力之类的问题上。

TODO:本来想逐一扩充描述方案细节,但缺少时间深入分析,同时觉得想法本身也有挺多细节问题并未解决。比如分片对其他分片的可用性进行投票(即接收到对应的纠删码碎片)时,投票该如何设计,如果直接每次出块都包含别的区块头,那么每个分片都需要打包所有分片的区块头,并广播给所有分片,这会造成O(n^3)的网络开销,经过调研,使用某些密码学累加器可以将这种投票压缩成固定长度,但是在检查分片区块头在投票中的成员证明时,又会引入很大的计算开销,除此之外,还有别的问题,所以细节补充就先搁置了,只放一个最简单的想法描述在这里。

7 Likes

你是NERVOS技术团队的嘛?

不是,只是以社区成员的身份发一些资料和想法。