# Data Availability Problem
文章未对外公开，其中内容参考了诸多文章/论文/白皮书，暂时没有一一列举，完稿后会附上相关信息。感谢。
<font size=5.5 >**0.**</font>
区块链作为分布式数据库，其数据层（Data Layer）是根据不同公链使用场景的差异，采用不同的数据结构和密码学技术进行数据编码存储的场所。而数据可用性（Data Availability）描述的是，存储在数据层的数据必须是可用的，即分布式节点接收到的数据首先必须是完整的（不存在被矿工扣押了一部分数据的情况）其后基于可用的数据，块中交易有效性就是可被查验的（欺诈证明的需要）或是零知识证明场景下用于重建链上状态或公示交易细节的需要，并根据后续的验证结果在结算层完成结算。进而数据可用性问题（Data Availability Problem）是指，如以欺诈证明为例，我们如何确定矿工完整的释放出了全部的交易数据并供全节点查验。这里的问题在于，如果一个验证者接收到了某个全节点发现数据不可用时的警告，但在某段网络延迟后，那些丢失的数据又出现了，这里便出现了对之前数据部分丢失可能的两种归因，一种是虚假警报，一种是恶意的矿工。因此在这种情况下，无法判定是惩罚矿工或是发出警报的验证者，但如果什么都不做，那么广播欺诈证明本身就提供了一个发起DOS攻击或者无风险盈利的渠道。数据可用性问题是一切单片式区块链（耦合DA层、安全层、执行层）在区块链不可能三角的约束下，实现扩容的基础问题。后文我们通过描述基于数据抽样和纠删码技术来解决数据可用问题的一个方案，同时我们也实现了更强威胁模型下的安全共识的实现。

<font size=4>**目录**</font>
[toc]

### 1.通用区块链架构
#### 数据层：借助merkle tree和密码学技术以链式结构存储数据
#### 网络层：节点组网，数据广播，数据验证
#### 共识层：定义节点如何对区块链数据账本达成一致

### 2.数据层
#### 2.1链式结构
#### 2.2通用Merkle Tree
#### 2.3密码学技术
##### 2.3.1a）对称加密算法
F(x)=key*x +b 加密密钥和解密密钥本质相同
##### 2.3.1b）非对称加密算法 RSA -> DSA -> ECDSA
i)在1到N之间随机选取一个数字d作为私钥
ii)计算公钥P=G（椭圆曲线乘法）* d
iii)Address = HASH（P）
允许路径：d -> P -> Address(√)
拒绝路径：Address -> P -> d (x)
##### 2.3.2 哈希函数（SHA-0/1/2-256/2）
i)将任意长度消息映射为固定长度消息
ii)抗碰撞性（随意找到的x和y的哈希值一样）-> 第二原像稳固（对给定的x求出h（x）的另一个原像x’是困难的）-> 单向性
##### 2.3.3 数字签名
以RSA为例，公开的公钥为（e，n），私钥为d，原始信息为h(m)，加密后信息为h(m’)
加密：h(m’) = h(m) ^ e mod n
签名：signature (h(m’)) = h(m) ^ d mod n
验证：若h(m’) = s^e mod n，验证通过
解密：h(m) = c^d mod n

ECDSA是数字签名算法DSA在椭圆曲线上的平移。具体略。
:::success
通过数字签名,消息接收人可以确认消息是特定发送人发的；区块链中的交易确认和验证，数据存储，就是通过p2p网络，非对称的加密算法和数字签名，结合哈希函数实现的。
:::

#### 2.4比特币&以太坊的数据层结构
不同的数据结构适配于不同的区块链应用场景,我们将在BTC/ETH和后文专用的DA层Celestia中看到这一点。
##### 2.4.1BTC区块内结构（Merkle Tree + Block header）
有n 个叶子的树的Merkle Proof的大小和验证时间是O（log（n））
为了可以高效检测数据是否被篡改以及使轻节点不用下载全部历史的交易数据便可验证最近一个区块内的交易是否有效，比特币引入了Merkle Tree结构。

//bitcoin block structure
"size":43560,
"version":2,
"previousblockhash":"00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249",
"merkleroot":"5e049f4030e0ab2debb92378f53c0a6e09548aea083f3ab25e1d94ea1155e29d",
"time":1388185038,
"difficulty":1180923195.25802612,
"nonce":4215469401,
"tx":["257e7497fb8bc68421eb2c7b699dbab234831600e7352f0d9e6522c7cf3f6c77",
#[...many more transactions omitted...]
"05cfd38f6ae6aa83674cc99e4d75a1458c165b7ab84725eda41d018a09176634"

##### 2.4.2ETH区块内结构（Merkle Patricia Tree + Block header）
由于基于账本的结构和状态根的引入，为了高效的检索数据，ETH使用了MPT的数据结构

### 3.区块公链的历史和以太坊的扩容之路
<font size=3 >**我们将从以太坊历史扩容方案中具体引出数据可用性问题**</font>

#### 3.1区块公链的历史
**Bitcoin -> Ethereum -> The explosion of monolithic blockchains -> Modular blockchains**

#### 3.1.1**Bitcoin**
Taproot升级后的比特币依旧受制于其功能有限的脚本和历史包袱，无法承载众多Dapps在其上运作。过往BCH的硬分叉选择了大区块，但也带来了去中心化和安全性上的牺牲。

#### 3.1.2**Ethereum**
然后我们有了图灵完备的以太坊虚拟机和众多在其上运行的智能合约，但随着21年爆发的Defi生态，高昂的gas价格和每单位gas下的低吞吐量成为了在其上运行的Dapps发展的瓶颈。

#### 3.1.3**Alt-chains**
随着Defi生态的爆发，对高性能公链需求的提高Bsc,Solana,Near,Matic,Terra,Fantom在牺牲了一些安全性和去中心化下通过众多与高吞吐量适配的Dapps吸引了一些用户。BTC和ETH选择了安全和去中心化，Altchains则牺牲了这些获得了更低的gas和每单位gas更高吞吐量。

#### 3.1.4**跨链桥**
多链世界的出现带来了跨链通讯的需要。跨链桥是其中一种技术路线，但受他们的安全性往往是脆弱的。（修改稿件时，恰逢Ronin桥6亿资金被盗，以及受layerzero漏洞影响到的35亿资金的安全）

#### 3.1.5**Modular blockchains**
另外一种技术路线就是类似Cosmos和Polkadot这种带有原生跨链协议的可定制化的公链，例如上面所提及的基于Cosmos SDK开发的Bsc和Terra链。对Cosmos链来说，在其上的应用链的开发可以使用已有的Tendermint Core架构，省去了独立开发通信和共识层复杂的工作，通过ABCI连接上层应用，并通过Cosmos SDK搭建。

#### 3.2以太坊的扩容之路
**对于传统的以太链来讲，扩容问题在多年前已被提及，相比于一再延期的链上分片方案，我们依次有了**

#### 3.2.1**State channel**
这一最出名的应用是现在没什么人使用的比特币闪电网络，他只需在一条状态通道的开始和结束端通过以太链进行结算，另外在开启状态通道的双方退出时，如果某方如Alice拒绝关闭通道（从而变相扣押了另一方如Bob的资金），那么Bob可以发起一个退出期限的请求，如7天，7天内，如果Alice无法提供Bob的支付签名，那么Bob将在7天后取回自己所有的钱。在State channel中，7天的退出期和Alice能否提供Bob的支付签名有些类似于我们后面所介绍到的欺诈证明。但State channel这一在流支付或小额多次支付的场景下适用的技术，却需要预先存入大量资金用于通道的维持，这在资金利用率上是低效的，另外它不能用于未参与通道的人进行交易申请，也不能用于无预设逻辑的行为，比如进行类uniswap上的交易。

#### 3.2.2**Plasma**
针对这些问题，我们有了Plasma，准确的说是Plasma式的技术哲学，在这里作为主链之外的Operator（可能是一个中心化的角色，或者是一个多签，或者是更加复杂的PoS/DPoS等）定期（例如15秒）发送链下交易执行后的状态树（而不发送具体的交易信息）至主链进行结算，同时他们会发送某个资产拥有者全部的资产变化的Merkle branch。当映射进入Plasma链上的资金跨链回至主链前，发起人将发布有关他的资产交易的Merkle branch用于在例如在7-14天以内的时间里供任何人使用其他的Merkle branches来验证在Plasma链上资金转移的有效性。在Plasma这里，我们获得了比State channel更强的特性，例如我可以将资产发送给系统中的其他人，也不需要锁定资产，但是他和State channel一样，我们依然需要一个可以以指定逻辑推理运行的所有者，uniswap依然不能再Plasma上运行，我们也无法在Plasma链中模拟出一个以太坊虚拟机环境。不过在Plasma这里，我们就正式引入了欺诈证明和潜在的数据可用性问题。

:::success
首先，欺诈证明得以提出并可被合约验证的前提是，Plasma层中所有的交易数据是全部可用的，这意味着Operator或者想要提出欺诈证明的人必须保留Plasma中全部的数据，而保存这些数据所需的成本是巨大的。其次由于Operator只提供状态根，不提供任何的交易数据（否则就和我们的初衷背道而驰了）那么对于主链（例如以太坊）的节点来说，在他们无法获取这些交易的具体数据并进一步执行验证的情况下（数据不可用），也就不能使Plasma链共享主链的安全性了。
:::

#### 3.2.3**Rollup**
如果我们并不向主链提交全部的数据，而只把这些数据进行特定编码下的压缩，并借由Layer 2本身的一些特性删减一部分内容，将这些被缩短了的数据传递给主链，同时保证这些数据可供主链验证，这样我们就来到了Rollup的技术路线。与Plasma相比，Rollup方案多向主链提交了一次打包并压缩后的交易数据。例如在以太坊发起一笔eth交易需要110字节，而在Rollup上通过一些高级编码手段可以大幅压缩消息至12字节。

:::success
例如在二层交易中，Nonce可以在交易中被省略；Gas相关的Gasprice和Gas也不必出现在每笔二层交易中；To和From地址不需要使用以太坊的地址，而是使用其在状态树中的索引；Value可以使用科学技术法存储节省位数；对于签名，可以将一个批次中的交易签名进行聚合，降低每个交易的签名存储消耗。同时，这些交易数据会被存储在链上gas成本比较低的字段Calldata中，借由EIP-4488提案，calldata每字节数据的gas还会被从16降至3个单位。

另外除了压缩交易占用字节数以外，Rollup中交易的计算量也会比直接在一层上执行要少，因为交易不必在一层上重新执行，只需要验证二层运营者提交的状态转换是否正确。对于ZK来说，主要来自于验证状态转换证明(零知识证明)是否合法；而对于Op来说，主要来自于欺诈交易的挑战消耗。
:::

#### 3.2.4**更进一步**
值得注意的是，如果把以太坊作为Layer 1（这是从现有大部分的Layer 2仍需以以太坊作为其数据可用层或其主要是服务于以太坊来说的），即使众多的Rollup项目可以以更低廉的吞吐量/gas费用和更高的速度执行交易，但以太坊自身的gas limit依然是有上限的，而且rollup本身依然需要与原生以太坊上的应用争夺区块空间。在这其中交易数据的存储是gas消耗最大的部分（EIP4488和EIP4884以及以太坊自身的链上分片实施后的影响我们稍后再介绍），而现有的以太坊链并不是专业服务于数据可用性共识后的存储和高速读写的。那么为了更高的吞吐量/gas，我们能否不将原始交易数据回传至以太坊主链而存储到链下；或者是我们干脆抽离出数据层，重新设计一个只用作数据可用层的“数据库链”；再或者我们能否在Layer2的基础上再搭建Layer3和Layer4，实现递归证明的乘法效应下成本的极度压缩。（当然这里数据可用性问题又出现了）

#### 3.2.5**Validium**
对于第一种技术路线的项目，也就是data off-chain方案，我们有了StarkWare的StarEx（基于STARK零知识证明方案），其提出的Layer2底层的技术为Validium，后又进一步推出了Volition。
上面这张图向我们展示了这一技术路线下的Volition（hybrid on-chain/off-chain data）和Validium（data off-chain）方案。

Starkware的Validium方案将数据保存在链下的同时结合了ZK的思想对状态转换做有效性证明。具体来说，数据在链下的有效性由链下的公证人保证，同时公证人会将链下交易的状态转换生成STARK证明上传到链上。STARK证明避免了公证人上传错误的状态转换到链上。但由于数据存储在链下，公证人可以合谋不提交数据，将用户的资产冻结。因此，其实Validium方案并不是Rollup系的技术，但是在Validium方案中用户资产也被冻结的问题被讨论之后，Starkware推出了一个新的方案，Volition。Volition其实是ZK Rollup方案和Validium方案的结合，用户可以根据自己的需求选择将数据可用性的保证放在链上还是链下。其中dYdX（Rollup）、DeversiFi和NFT交易市场Immutable均上线支持了StarkEx方案（Validium）。

StarkNet这种多层的堆叠的架构同样也实现了我们上文提到的第三种解决方案，即实现乘法效应下成本的极度压缩。但是递归结构下的数据可用性问题更为复杂。

#### 3.2.6**Volition**
这一方案的项目我们有zkSync，2.0版本将使用ZK Rollup和zkPorter混合账户架构，其中zkporter（PoS共识，验证人无法转移用户钱包里的资产，只能暂时冻结zkPorter）作为数据可用层。ZkSync允许用户选择将数据存至链上还是zkPort链中。而且zkPorter和zkRollup享有同一个状态根。
zkPorter将数据存放在链下以绕开gas limit导致的吞吐量上限，同时，对于所有交易，其状态转换的证明仍旧会提交到链上，由链下验证者进行验证。zkPorter中还有一个重要的点是引进了分片，ZK Rollup所在的分片是基础分片，其余所有的分片可以由用户自行决定数据可用性方案，这些分片的可用性可以由zkSync的守护者来维护，也可以由该分片上的协议自行维护。zkPorter的引入进一步缩减了gas费用的消耗。如图Guardians shard一栏。

### 4.模块化区块链——celestia
最后对于第二种技术路线，即单独将数据可用层从共识层（安全层）和执行层抽出，其只负责数据可用和共识，而不负责其他所有的事务。在这条技术路线上我们有Polygon Avail（和以太坊分片方案类似，使用KZG零知识证明的方法验证数据是否可用）和Celestia（使用基于数据可用的欺诈证明方案，同时做出了对更强威胁模型下达成安全共识的模型）。我们以Celestia为例进行较为细节性的介绍。

数据在以太坊上的Rollup和celestia之间的生命周期


#### 4.1概述
以以太坊为例，节点分为负责存储所有数据、执行并验证block body中的每一笔交易的全节点和基于【α】一般只下载block header并验证其是否有效的轻节点。我们想要做的正是中本聪最初所提到的那样，令轻节点享有与全节点一样的安全性。

:::success
假设【α】：共识算法下所有区块都是有效的即区块生产者大都是诚实的假设（而不是交易有效性规则）
:::

通过一个基于概率抽样技术的数据可用性的证明系统（这样轻客户端就能保证全节点生成欺诈证明所需的区块数据是可用的）和欺诈证明，我们就可以消除对区块有效性的诚实多数假设【α】，而对重新广播数据的诚实节点的最低数量做出更弱的假设【β】。并在保证去中心化的同时实现对区块链的扩容。

:::success
假设【β】为：1.至少有一个诚实的全节点——用于提供在最大网络延迟内传播的欺诈证；2.最少数量的轻节点——用于可能的区块数据的重建（数据可用性证明）
:::

#### 4.2 Celestia使用到的技术介绍
分为两部分，第一部分是Celestia的数据结构；第二部分是Reed-Solomon Codes纠删码

##### 4.2.1 Celestia的数据结构 ：Sparse Merkle Tree

为了适配Celestia的应用场景我们需要对交易进行排序，所以Celestia选择了稀疏Merkle Tree，稀疏Merkle Tree是一棵有n 个叶子的Merkle 树，其中n非常大（例如n=2^256），也因此几乎全部的叶子默认值相同（例如为0）。稀疏Merkle Tree中的数据是有序的，且搜寻的数据在网络最大延迟o（log（n））时间内。

##### 4.2.2 纠删码
纠错码将长度为k 的信息转化为长度为n>k 的较长信息，从而使原始信息可以从n 个符号的子集中恢复出来。

Celestia使用的Reed-Solomon 编码可以检测和纠正（n-1）/2 错误的组合。这些纠删码和原始数据可以重新组成一棵稀疏Merkle Tree，这样对于恶意节点来说，他们必须扣押50%以上的区块数据才可以使得该区块数据不能被恢复。

#### 4.3 假设和威胁模型
##### 4.3.1 预先定义一些参数
1.Hash256（x） //对x进行哈希运算并返回值
2.root（List） //返回一个项目列表的Merkle根
3.{e->r} //表merkle-proof，即e是根r承诺的Merkle树中的一员
4.VerifyMerkleProof(e, { e->r },r, n, i) ∈{true, false}
//n：底层树叶数;i：e在树r中的索引；如果true，证明e在i处且在r树中
5.{k, v->r}//表merkle-proof，key-value(k,v) 是根r承诺的Merkle树中的一员

##### 4.3.2 通用区块链模型
全部区块链头=All_Block_Header(header_0->header_n))
valid(T,S)∈{true, false} //T是交易列表；S-State表区块链状态。
transition(S, ti) ∈ { post-Si , err }

##### 4.3.3 网络模型
**全节点**：下载储存并验证所有交易，广播从别人那里接收到的有效区块，并将有效区块头广播给轻节点，其中有些节点可以通过pow取得记账权并广播自己打包的出块。

**轻节点**：受制于计算能力和网络带宽，无法下载和验证整个区块链数据。他们从全节点接受区块头，并通过接收来自其他节点广播的branch的Merkle值Merkle证明一些它接收到的交易或者状态是区块头的一部分。

**节点拓扑图**：
1. 全节点间相互通信，spv与全节点通信，但轻客户端之间不通信。
2. 假设一个最大的网络延迟δ
如果一个诚实的节点可以连接到网络，并在时间T下载一个区块，那么它保证任何其他诚实的节点将能够在时间 T’≤ T + δ做同样的事情。

##### 4.3.4威胁模型
**区块和共识**：区块头无效，假设【β】成立

**全节点**：全节点可能是不诚实的，他们可能不广播欺诈证明或广播无效的区块。然而，我们假设至少有一个诚实的全节点是与网络相连的，即它是在线且愿意生成并广播欺诈证明的，且没有受到日食攻击。

**轻节点**：我们假设每个轻客户端都至少与一个诚实的全节点相连。对于数据的可用性证明，我们假设最小数量的诚实的轻客户端，以允许一个区块被重建。

#### 4.4 欺诈证明
##### 4.4.1 区块结构
为了实现高效的欺诈证明，我们设计了以下的区块头的数据结构（扩展自3.2中的hi）
prevHash i 链中前一个区块头的哈希值。
dataRoot i 数据（包含交易数据和中间状态根）Merkle根。
dataLength i 数据树中叶子的数量。
stateRoot i 稀疏 Merkle Tree的状态根。
additionalData i 额外数据（如，nonce 和目标难度阈值）。

##### 4.4.2 状态根和执行轨迹的建设
为了匹配基于状态的区块链模型，我们使用了稀疏Merkle树，并且将状态描述为一个key-value图。基于UTXO的区块链模型也可以与此模型匹配。

<details>
<summary>基于UTXO</summary>
The keys in the map are transaction output identifiers e.g., hash(hash(d) || i) where d is the data of the transaction and i is the index of the output being referred to in d. </p>
The value of each key is the state of each transaction output identifier: either unspent (1) or nonexistent (0, the default value).
</details>

<details>
<summary>基于账户</summary>
This is already a key-value map</p>
The key is the account or storage variable.</p>
The value is the balance of the account or the value of the variable.
</details>

定义rootTransition函数
performs transitions without requiring the whole state tree, but only the state root and Merkle proofs of parts of the state tree that the transaction reads or modifies (which we call “state witness”, or w for short).

这些merkle proofs就是同样状态树的一个子树，他们享有同一个状态根。
rootTransition (stateRoot, t, w) ∈ {stateRoot ′, err}

##### 4.4.3数据根和周期
定义函数parseShares，解析shares并输出一个有序的消息列表，其中有些是交易，有些事中间状态根
定义函数parsePeriod，我们设定一个周期使得中间状态根定期被加入至区块数据中，例如每p此转账交易后。
##### 4.4.4 无效状态转换的证明
恶意矿工可能提供一个错误的stateRoot，我们可以使用dataRoot中提供的执行追踪证明执行追踪的某些部分是无效的。

定义函数VerifyTransitionFraudProof，用于验证从全节点收到的欺诈证明。我们把d(ij)表示为区块i中编号为j的份额（shares）
满足以下条件返回True

#### 4.5 数据可用性证明
恶意的区块生产者可以扣留数据并重新计算 dataRoot从而阻止全节点发现问题并发出欺诈证明，只向网络广播区块头。然后，恶意区块的生产者可以在区块发布后释放数据——其中可能包含无效的交易或状态转换，使得区块无效并回滚。因此，我们需要保证区块生产者发布了全部的数据。

借由使用Reed-Solomon 纠错编码的数据可用性方案，轻节点将请求随机的数据份额，确保与Merkle 树的根相关的所有数据都是可用的。该方案假设有足够数量的诚实的轻客户端提出相同的请求，这样网络就可以恢复数据，如果一个没有完整数据的全节点请求它，因那么轻客户端就会将这些份额上传到全节点供其验证。

##### 4.5.1 定义数据可用性模型
定义 1（健全性 Soundness）。如果一个诚实的轻节点接受一个区块是可用的，那么至少有一个诚实的全节点拥有完整的区块数据，或将在某个已知的最大延迟δ内拥有完整的区块数据，其中δ是最大网络延迟。
定义 2（一致性 Agreement）。 如果一个诚实的轻节点接受一个区块是可用的，那么所有其他诚实的轻节点将在某个已知的最大延迟δ内接受该区块，其中δ是最大的网络延迟。

##### 4.5.2 1D Reed-Solomon
一个区块生产者编译一个由 k 个份额组成的区块，并使用 Reed-Solomon 编码将数据扩展到 2k 个份额，并合并计算一个Merkle 根（dataRoot），其中每个叶子对应一个份额。

当轻节点收到带有dataRoot的区块头时，他们从该dataRoot所代表的 Merkle Tree中随机抽取份额，并且只有在收到所有请求的份额后才接受一个区块。如果一个敌对性的区块生产者使 50%以上的份额不可用，从而使全部数据无法恢复，轻节点会有50%以上的机会在第一次抽签时随机抽到一个不可用的份额，两次抽签后有25%的机会，三次抽签后有 12.5%的机会，以此类推。

为使这一方案发挥作用，网络中必须有足够的轻节点对份额进行随机采样，这样区块生产者就需要释放50%以上的份额，以通过所有轻节点的采样挑战，从而使整个区块能够被恢复。

问题
一个恶意矿工可能会错误地构建扩展数据，因此，即使超过50%的数据是可用的，不完整的区块也无法从扩展数据中恢复。
对于这种类型的恶意矿工，如果使用标准的Reed-Solomon编码，证明扩展数据无效的欺诈证明需要原始数据本身，因此节点必须在本地将所有数据重新编码，来验证其与给定的扩展数据的不匹配，因此，相对于区块大小，它需要 O（n）的数据。

由此
我们转而使用多维编码，因此，错误生成的代码的证明仅限于特定的轴（axis）——而不是整个数据，这回将证明大小减少到 O（ d √n），其中 d 是编码的维数。为了简单起见，我们以二维的 Reed-Solomon 编码为例，但该方案可以推广到更高维度。

##### 4.5.3 2D Reed-Solomon
1. 将原始数据分割成每一个大小为 shareSize 的份额，并将其排列成 k x k 矩阵。
2. 在 k x k 矩阵的每一行和每一列上应用 Reed-Solomon 编码，并将数据在水平和垂直方向上扩展，创建一个 2k x 2k 的矩阵。
3. 计算 2k x 2k 矩阵中每一行和每一列的 Merkle 树的根。

##### 4.5.4 随机抽样和区块恢复
轻节点和它所连接的全节点之间的协议工作如下：

1.轻节点从它所连接的一个全节点那里收到一个新的块头区hi，以及一组行根和列根R，检查root（R）是否等于hi中的dataRoot。

2.轻节点随机选择一组特定的（x，y）坐标 S={（x 0 ，y 0 ）（x 1 ，y 1 ）,...，(x n ，y n ）}并将它们发送到它所连接的一个或多个全节点上。

4.对于轻客户端收到的每一份Mi(xa,yb)，轻节点调用VerifyMerkleProof函数
5.轻节点广播收到的每个份额和有效的 Merkle 证明，如果轻节点连接的全节点没有收到的话，这些全节点会进一步广播给它们所连接的所有全节点。

6.如果第 4 步中返回true，并且在第 2 步的抽样中没有丢失任何份额，那么如果在2 ×δ内没有收到该区块的欺诈证明，则该区块被接受为可用的。

##### 4.5.5 错误生成的扩展数据的欺诈性证明

如果一个全节点有足够的份额来恢复某一行或某一列，并且在这样做之后检测到恢复的数据与其各自的行根或列根不匹配，那么它必须分发一个由该行或该列的足够多的份额组成的欺诈证明，以便能够恢复它，并为每个份额提供一个 Merkle 证明。

定义验证该欺诈证明的函数 VerifyCodecFraudProof，该函数将欺诈证明作为输入，并检查(i)验证者给出的所有份额都在同一行或列中，以及(ii)恢复的行或列与区块中的行根或列根不匹配。如果这两个条件都是真的，那么欺诈证明是有效的，欺诈证明所在的区块应该被客户端永久拒绝。
定义recover函数， 该函数接收一个份额列表及其在行或列中的位置以及原始行或列的长度k，该函数输出完整的恢复的份额（sh0，sh1，sh2k），如果份额无法恢复则输出err。
如果满足以下所有条件，VerifyCodecFraudProof 将返回 true，那么该区块头将被轻节点禁止。
#### 4.6 抽样安全分析(Sampling Security Analysis)

##### 4.6.1 不可恢复性的最小不可用份额
定理 1。如图 ，给定一个 2k × 2k 矩阵 E,如果至少有 k+1 列或行各有至少 k+1个不可用的份额，则数据是不可恢复的。在这 2 种情况下，不可恢复的最小份额数是（k+1）^2。

##### 4.6.2 不可恢复区块检测
定理 2. 给出一个 2k x 2k 矩阵 E，如图所示 4，其中(k+1)^2 个份额是不可用的。如果一个玩家从E中随机抽出 0 < s < (k + 1) 2 个 份额，则抽出至少一个不可用份额的概率为：
上图显示了在k=32 和k=256 的情况下，这个概率是如何随s 采样而变化的。
对于大k值，概率和k值几乎无关

##### 4.6.3 多个轻节点不可恢复区块检测
定理 3。给定一个2k x 2k矩阵E ，其中 (k+1)^2 个份额是不可用的。如果 c 个玩家从E中随机抽取 0 < s < (k + 1)^2 份额，那么超过Ĉ个玩家至少抽取一个不可用股的概率是：
恢复和选择性的份额披露
如果轻节点集体采样，除了(k+1)^2个不同的份额，区块矿工不能再释放任何份额而不允许网络恢复整个矩阵。那么轻客户至少需要收集：
不同的份额（随机抽取的）才有把握恢复2k ×2k 的矩阵。因此，我们好奇的是轻客户端——每个采样s个不同的份额——集体采样至少γ个不同份额的概率。

##### 4.6.4 定理4。从一个由n个元素组成的集合中抽出的不同元素的数量，经过c次抽签后每次抽选s个后，至少收集到λ个不同元素的概率。
推论1。给出一个2k x 2k 的矩阵E，如图所示4，其中每c 个玩家从E 中随机抽取s 个不同的份额，玩家集体抽取至少γ = k(3k-2)个不同份额的概率为p
在不同的k 和s 值下，达到pe (Z ≥ γ) > 0.99 所需的最小轻客户端数(c)

基于此我们完成了有关数据可用性证明的阐述。

#### 4.7 额外的
单独就技术方案来讲，Celestia为证明数据可用而选取的稀疏Merkle Tree和二维的Reed-Solomon擦除码并不是最优的。

其他代替性方案例如Code Merkel tree（及其改良版）等，可以实现更加简洁和高效的数据可用性证明。

但是作为单独抽取出来的数据层，celestia可能在另一方面更加吸引人。如果说传统的单片式区块链耦合了数据可用层，安全层和执行层，那么对于一个单独的共识后的数据可用层，我们可以在其上建立更高效且更细分化的虚拟机环境以适应其上领域细分化的Dapps（这些Dapps也可以主动选择适合自己运行的环境），另外也实现了Dpps更加便捷的升级（合约更新）。

对于以太坊上zk-Rollup来说，他们使用一种更加先进的密码学运算构建自己的产品，却仍需花费巨大的努力使自己原生的虚拟机环境，例如Zkevm兼容evm。

在这点上以太坊2.0除了通过改变共识机制降低了gas消耗，但不能改变evm本身的中心化。在这方面，以太坊原生的Layer 2似乎是再用更好技术适配一个古老且中心化的执行环境，这可能对于以太坊原生应用的迁移有利，也能收获一定的流量，但是对与合约层的进化，并没有做出什么贡献。

通过一个可插拔的数据可用层，Celestia，Polygon Avail，为区块链开启了乐高时代。

**Team**

Mustafa Al-Bassam, CEO, 伦敦大学博士，博士论文写的就是celestia的原型Lazy Ledger，和Vitalk合作写过最早的欺诈证明相关的论文，最早进行欺诈证明和扩容研究的人之一。

John Adler, CRO, 之前在ConsenSys工作,是第一个optimistic rollup框架规范的提出人。

Nick White, COO, Celestia Labs, 斯坦福毕业，Harmony的联合创始人

**融资背景**
种子轮融资，融资金额为150万美元，参与者有Maven 11 Capital、Interchain、Signature Venture、Cryptium Labs和Dokia Capital。咱无代币经济模型。

### 5.以太坊原生分片方案

我们将以太坊分片方案的变化大致划分为两个阶段进行阐述，另外由于以太坊取消了执行分片而只保留了数据可用性分片，实际上和上文中提到的Celestia的数据可用性的解决方案有极大的相似。

#### 5.1 首先是以太坊传统的分片方案。
由于众多Rollups的出现，在其专业化环境中的执行速度相比原生以太坊上高了百倍，因此执行分片不再被需要，以太坊现有的共识层中的全节点们将只负责保证数据可用，并为rollups和其他扩容方案提供数据可用层。

和Celestia类似的是，以太坊数据分片中可用性的证明也是基于了纠删码的技术，但于Celestia不同的是，Celestia使用了欺诈证明的方式来证明数据是否可用的，而以太坊的数据分片则使用了KZG零知识证明的方法。KZG可以不完全贴切的类比为一种类似Merkle根的东西，但与Merkle根不同的是，如果一个KZG根生成了，则直接代表了其下的所有叶子都必然被包含在相同的KZG根下了，也就证明了数据可用。
上图是传统的数据分片方案。

#### 5.2 Danksharding
一种新的分片方案，Danksharding不久前被提出，这种方案主要涉及到一些新的技术，有些甚至和Celestia看起来相似。这些新技术主要有PBS、crList、KZG 2D scheme。

PBS即Proposer-Builder Separation，目的是为了防止MEV带来的中心化倾向，事实上对于大矿池来说，他们更有可能获取更高的MEV收益，相比于一个在家用电脑上跑的节点来说。

crList即Censorship resistance，在PBS的设计中，一个高效的builder可以永久检查一些交易以获得更高的MEV。crLists 通过允许提议者指定构建者必须包括的交易列表来恢复旧的平衡。


KZG 2D scheme & reed-solomon code


将上述三种技术结合起来，我们就有了一个全新的Danksharding方案


#### 5.3与Rollup有关的EIPs
最后我们简单介绍一下与calldata费用有关的EIP4488提案，和Danksharding真正实现前的预备工作EIP4844：Proto-Danksharding提案。

##### 5.3.1 EIP4488
降低calldata gas费用，并辅助增加一个区块中总交易calldata大小的限制。

Rollups式扩容方案将长期存在。借由L1高昂的交易费，我们需要促进整个生态系统向Rollups迁移。虽然Rollups显着降低了许多以太坊用户的费用——Optimism 和 Arbitrum 经常提供比以太坊本身低约3-8 倍的费用，而具有更好的数据压缩编码并且可以避免包含签名的ZK rollups的费用约比以太坊本身低100倍左右。

但这些费用对许多用户来说依然太贵了。长期的解决方案一直是数据分片，这将为链中的rollups增添约 1-2 MB/秒的专用数据空间。然而，数据分片仍然需要相当长的时间来完成实施和部署。因此，需要一种短期解决方案来进一步降低rollups成本，并激励整个生态系统向以Rollup为中心的以太坊过渡。该EIP提供了一种快速实施的短期解决方案，同时也降低了安全风险。

| Parameter | Value |
|:-------- |:--------:|
| NEW_CALLDATA_GAS_COST |3 |
| BASE_MAX_CALLDATA_PER_BLOCK|1048576|
| CALLDATA_PER_TX_STIPEND |300 |

##### 5.3.2 EIP4844
这是一个为Danksharding的实施做预先准备的一个提案，提案主要是引入了一个新的交易类型，带有一种blob的交易。带有blob的交易与常规交易类似，不同之处在于它还携带称为blob的额外数据。Blob非常大（~125 kB），并且比类似数量的calldata便宜得多。依然是为rollups降低费用和适配以太坊自身的分片。

该提案还将实现Danksharding中分片所需的所有执行层的逻辑;所有执行/共识交叉验证的逻辑;BeaconBlock验证和blobs数据可用性采样层的分离和分片所需的大部分BeaconBlock逻辑等。