以太坊扩容终极解决方案 - Danksharding （一）

在Sharding1.0的设计中，每个区块有64个分片，每个分片有单独的提议者和委员会，轮流通过节集合选举出来。每个提议者和为委员会负责验证自己的分片数据（1/64)。而在Sharding1.0中，以太坊并没有采用数据可见采样，而是通过每个分片验证集合大多数诚实节点假设下载全部数据实现。

这个设计显得冗余和复杂，同时存在攻击者风险，通过分片来分配节点的方式也不妥。同时，因为信标链上的验证者需要收集所有的委员会投票，这需要时间，所以保证在一个时隙内（Slot）完成投票也非常困难，除非引入额外假设（比如同步假设）。

而相比于Sharding1.0的设计，Danksharding的设计则引入了大区块的设计，大区块将信标区块和所有分片数据结合并且实现同步确认，大区块由专门的创建者（Builder)创建，而验证节点通过数据可见采样确保所有数据都是可见的。

数据可见采样

数据可见采样我们之前在多篇文章中已经介绍过，由于资源和成本限制，大部分节点无法下载全部的数据，如何在不下载全部数据的情况下验证数据/交易呢？我们需要通过数据可见采样确保数据的可见性，所以节点（即使是轻节点）可以轻松安全的在无需下载全部数据的情况下验证数据。 

而数据可用采样是根据长期存在的数据保护技术删除码（erasure coding)，就是利用这个技术本身可以让原本的数据实现扩展，比如双倍大小, 那么原本的数据可以恢复，比如通过这些扩展数据的50%。Reed-Solomon可以将原有数据进行拓展，而拓展的数据和原有的数据则通过拉格朗日插值公式（Lagrange interpolation formula）形成多项式。多项式式中的次数是其最高指数。比如x³+x²+2x-4的次数为3.  而多项式的一个核心特征就是任何次数为N的多项式都可以通过其上任意的N+1项恢复。比如原有数据为a₀,a₁,a₂,a₃。那么通过多项式对应的价值分别为f(0),f(1),f(2),f(3)，所以f(0)=a₀,f(1)=a₁,f(2)=a₂,f(3)=a₃因而我们可以找到其对应的次数为3的多项式。同时，我们可以通过删除码技术，将原有数据拓展额外四项数值，我们将其记录为c₀,c₁,c₂,c₃。f(4)) =c₀,f(5)=c₁,f(6)=c₂,f(7)=c₃因此，我们可以利用多项式的特征，通过其上的任意四个数据样本恢复多项式，也就是50%（4/8)的数据。比如我们采样了30次，那么当可见的数据小于50%的时候，就会受到攻击。而这个概率只有（½)³º。

KZG 多项式承诺

那么我们通过数据可见采样实现了数据可见性（DAS)，基于数据可见性，全节点可以生成欺诈证明，轻节点可以在无需下载全部数据的情况下，验证全部数据，我们又是如何确保数据被正确的采用了删码技术呢？如果被额外拓展的数据是一个空集，或者是垃圾数据，那么我们如何恢复数据呢？

通常情况下，我们通过默克尔根证明某些集合中数据的存在性，而且适用于大量的数据。但是原有数据和通过删码技术得到的拓展数据，我们如何保证他们在同一个多项式上呢？那么我们就需要其他方法。而默克尔根无法证明。目前主要有两个方向：

1）Celestia通过欺诈证明实现。当见证人发现数据没有被正确采用删码技术，那么这个人就会将欺诈证明提交提醒其他人。但是这里需要最少诚实假设和同步假设（当有人给我发送欺诈证明的时候，我需要确保我能在一定时间内收到通知）。

2）以太坊和Polygon Avail则采用了KZG多项式承诺（KZG commitments) 的方法。这里免去了欺诈证明中的包括少数诚实假设和同步假设等的安全假设。当然，在数据恢复和重建的时候，我们不可避免地都需要引入这两个假设（无论是Celestia还是以太坊，还是Polygon Avail)。

其他的解决方案比如Zk-proofs。但是其现有的计算瓶颈, 使得其目前并被推崇为一个可行方案，我们期待未来的技术进步，而以太坊也可能在之后引入其STARKs的技术，因为KZG多项式承诺本质并不防量子计算，而STARKs可以。 KZG多项式承诺我们可以理解为一种通过加密方式承诺价值的多项式承诺方案。

而KZG根（多项式承诺）可以理解为类似于默克尔根（向量承诺）的承诺。而我们上文也提到了原有的数据通过多项式匹配到为f(0),f(1),f(2),f(3)), 而我们将拓展的数据匹配为f(4),f(5), f(6),f(7)。而f(0)到f(7)将确保在同一个多项式上。

KZG 多项式承诺和欺诈证明

KZG 多项式承诺并不能保证后量子安全，同时需要可信设置-- 必须生成具有一定关系的椭圆曲线点，但不允许任何人知道它们之间的实际关系-但可以通过分发信任，允许许多人参与设置，设计为只要一个人是诚实的，它就有效；而STARKs提供了后量子安全，而且其可信设置只需要一个诚实参与者， 但是相比于欺诈证明，其无需引入同步假设和最小诚实假设，可以确保删码技术被正确使用，延迟性也较低。注意，这个延迟性体现在当采用数据可见采样的时候，不同节点间需要欺诈证明实现信息互通，而这里欺诈证明会大大提升区块间隔，而验证者投票给错误编码块的风险性也会上升，而KZG则减少了这类问题的发生。

但是在区块数据恢复的过程中，我们仍然需要用到上述两个假设：

1）我们需要足够多的节点（轻节点或者全节点）去采集足够多的数据样本，从而恢复数据，这里需要最小诚实假设，一个全节点可以通过数据可见，生成欺诈证明。

2）当数据可见后，不同节点需要在某时间段内沟通并且将数据重新组合，比如当区块数据不完整，部分可见的时候，全节点必须其他节点沟通，将数据拼起来。

协议内提议者创建者分离 (PBS)

POW中的矿工以及合并后的验证者都承担着类似的角色，他们负责提议，投票和出块。POW中矿工通过哈希算法计算的形式参与，而合并后，验证节点直接在区块链上投票。而PBS创建了全新的创建者角色，负责生成包含信标链和分片数据的大区块，同时以向验证者竞价的形式，提交区块。和Vitalik中endgame的愿景相一致，在PBS中，一个诚实的创建者就可以保证网络的安全以及抗审查性， 而验证节点则需要大多数诚实假设。 

创建者的收益主要来自于优先小费（来自于searcher）以及可提取的矿工价值（MEV)。在充分竞争的市场中，创建者竞价的价值会等同于其可见利润（其可提取的MEV总价值-硬件成本等费用）(这等同于只有一个最高利润的创建者能够胜出，而其他创建者最终的竞价都是一个收支平衡点）而所有的价值都会给到验证节点集合，因为验证者将无条件获得竞价金额。

首先，创建者提交区块头信息，这里包含执行区块哈希，竞价以及签名；之后信标链提议者选出获胜区块头，并且无条件获得全部竞价金额（不管是否顺利出块，如果没有出块，创建者仍然需要支付这些金额），而这个无条件支付方式解决了提议者对于创建者的信任问题；委员会成员确定获胜区块头并且签名，创建者展现区块身，以及其他相关证明，剩余的委员会将认证获胜区块身。

这里我们为什么需要先提交区块头，确认之后再展现区块身体？这里采用了承诺—揭示机制。如果一开始提交大量区块身体，会造成大量的带宽拥堵，同时其他的创建者也可以发现其策略，进行MEV攻击，即使对于一些提议者来说，他们也可以复制这些策略，而并不给创建者任何奖励和激励，而MEV攻击会逐步让创建者和提议者的角色逐步融合，给整个生态带来巨大伤害。

当然这里的问题是一个双时隙的延迟问题，在PBS中整个区块时间为2个时隙。比如合并后的出块时间为12秒，而这里在不引入其他假设的情况下应该为24秒。当然我们最终采用8秒/16秒的折中算法。

PBS的设计在一定程度上解决了验证节点去中心化的问题，同时虽然大区块需要消耗相当多的资源，比较难创建，但是验证相对容易，这也和Endgame的理念相一致。所以将创建者和提议者分开，本质上是处理大量资源，数据，难度的机构可以参与搭建，而提议者可以是验证者。这种设计本质上让MEV扩展到数以万计的验证者身上。

防审查列表（crlist)

当然这里和MEV问题中一样，创建者和验证者一样，会利用自己的权利进行交易的审查，比如优先自己的交易，比如屏蔽其他人的交易等等。这里我们是如何解决的呢？以太坊采用了防审查的列表，提议者将他看到的所有交易都放在这个列表中，所以创建者必须将所有的交易都包含进去（除非区块已满）。这里的过程类似于PBS的过程，创建者首先需要提交包含所有交易的列表及概述，而后创建者创建区块身，竞价，并且包含交易列表的相应哈希，提议者选择获胜的竞价和区块头。之后创建者展示区块身并且证明他们已经囊括了所有列表上的交易，或者证明区块已满。委员会证明区块身的有效性。

2D KZG 方案

在以太坊中，一个KZG多项式承诺并不能解决所有数据问题，通常一个区块有很多KZG承诺。在恢复区块的过程中，我们需要很多低能源消耗的节点参与，所以相对应的KZG承诺也需要进行相应划分。而为了让恢复过程更为简单，这里每个区块中在m个KZG承诺中编码m个数据碎片, 而这个需要在每个数据碎片上进行数据可见采样。因此，以太坊再次利用Reed-Solomon技术，将m个承诺扩展至2m。

在Danksharding中，每个区块中最多有256个数据碎片（目标为128个）。KZG承诺0代表的是数据碎片0相对应的原有数据和拓展数据。而和之前1D的承诺一样，我们能确保0-511的承诺都在同一个多项式上。而至此，我们可以基于此进行数据可见采样，确保所有分片中的数据可见性。

在1D方案中，我们需要50%的数据恢复所有数据，而在2D中，我们需要75%的数据才可以恢复，因此我们需要采集更多的样本数据。这里需要强调的是，在1D的方案中，我们得出结论，我们需要采集30个样本，而数据不可见的概率为（½)³º,  而要达到相同的概率, 在2D的方案中我们需要采集75个样本。让我们通过带宽理解2D方案是如何提升效率的：

在Sharding1.0方案中（1D）30个采集样本，需要采集64个分片，所以如果需要检查所有数据可见性，需要512B*64分片*30样本/16秒 = 60KB/秒 带宽 （基于一个数据碎片容量为1bytes假设）。而在2D方案中，我们可以将其考虑为一个区块，所以需要512B*1*75样本/16秒=2.5KB/秒带宽

Danksharding (DS)

DS设计基于PBS，其中在特定时间由一个创建者，一个提议者以及一个投票委员会组成。一般的验证节点无法处理这么大量的带宽，所以需要引入PBS。在DS中，每个区块的数据存储量有多少呢？我们可以计算下，每个数据碎片字段元素*32字节*256数据碎片=32MB。在DS的设计中，由于我们引入了大区块的概念，尽管数据仍然需要分片，但是整体上你可以理解为一个统一区块，并且在上进行数据可见采样。

大多数诚实验证

在DS中，每个时段都被分为32个时隙，因此每个时隙将匹配1/32节点进行验证。每个节点在制定时隙验证相应的2行2列，同时需要下载其他时隙区块上的该行该列。比如，我需要认证时段2时隙26上对应的2行2列，因此我要确保从上一次我认证的区块开始（时段1时隙26）到现在，所有时隙（区块）上，我需要认证的行列信息都可见。所以DS中需要基于大多数诚实节点假设，确保数据可见性以及负责数据恢复。这个和上文提到的低能源消耗的采集75个样本的轻节点（个人节点）不是一个概念。上文可以称为私人随机抽样。

恢复/重建

恢复/重建过程中我们需要再此引入最小诚实假设和同步假设。而通过测算，我们需要64,000节点。但是实际情况下，这个数据会大大减少。64, 000的节点数量是基于同样的验证节点不同时运行多个节点的假设，但这显然与现实不符，因为以太坊单个节点的质押数量限制为32个，所以很多大户将仓位分散到多个节点上。如果你采集的数据超过2行2列，那么你会大大提升概率，因为这里面会有很多交集，因此64, 000数量要求将会大幅减少。

恶意多数安全的私人随机抽样

一旦采用了私人随机抽样，任何节点可以采集任意的数据样本，即使当有恶意多数提醒数据可见（当数据不可见）的情况下，可以通过私人随机抽样高概率的证明数据可见，而上文提到验证节点的行列数据采样是基于多数诚实验证节点的假设

这里私人很重要，如果攻击者攻击了匿名性，他们可以贿赂少部分采样节点，根据你的请求提交数据并且隐瞒其他数据，因为根据你的采样数据，你无法证明数据可见。

总结：

相比于Sharding1.0 我们看到了Danksharding的极大进展，1）委员会的功能被弱化了，他们只需要投票，这个减少了受贿的风险。原来的分片设计中，验证者每个时间段需要投票，但是每个分片都有自己的提议者和委员会会，所以每个时隙需要1/32*64=1/2-0-4-8的节点集合。而在DS中，验证者也同样每个时间段需要投票，而每个时隙需要1/32的节点集合投票。

2）数据碎片的确认不再是单独的，而是和主链同步确认，这确保了rollups和以太坊执行环境中的同步互操作性，我们知道波卡等设计都一定程度上牺牲了可扩展性，而实现同步互操作性，而以太坊的这个设计，在实现分片（可扩展）的同时，确保数据碎片的交易可以立即被确认，同时上传至L1。这个也将衍生出更多的类似于Cosmos上的互操作性设计，比如共享流动性，比如Superfliod 质押，跨链安全性和跨链账户等设计，我们将持续关注。

3）同时我们也在上文提到了带宽的提升，通过大区块的设计以及2D KZG承诺，我们发现Sharding1.0中60KB/S的带宽要求，而在DS中只需要2.5KB/S。

而在可扩展性层面，在模块化的设计理念中，比如Celestia的设计理念，当轻节点数量越来越多时，我们可以发现区块容量也越来越大，数据吞吐量也越来越高（TPS/秒），所以本质上去中心化促使了扩展性。当然尽管我们看到了扩展性的提高，但是仍然会有一些trade off。除了安全可扩展的，允许更多生态搭建的底层以外，我们需要在数据存储和带宽上进行提升。 

数据存储主要包含数据可见和数据可检索性，而公式层需要保证在足够的时间段内，任何人在满足安全假设的基础上，可以下载相应的数据，之后再存储至任何地方（这是基于1/N信任假设，只要有一个诚实者存储数据就可以）。当吞吐量指数级上升时，这些假设可能就不成立了。

数据可见采样中需要足够的节点数据足够多的数据，当然如果有恶意节点存在，数据样本不够的情况下，就无法恢复原有数据。因此当吞吐量指数级上升时，我们需要越来越多的数据样本采集节点加入，同时也需要提高带宽要求。所以对于32MB的KZG 证明，需要较好的GPU，CPU，同时至少2.5GBit/s带宽。

所以我们看到DS是一种简化为数据分片的新型分片形式，ETH提供了不可扩展的数据，而Rollups将其转为可扩展的计算，其设计更为简单，减少了协议本身需要完成的事情，而更专注于与L2s的协作。同时也为EVM的执行分片埋下了伏笔，但是即使在EVM没有执行分片的情况下，以太坊也是可扩展的。