Polkadot - ELVES

ELVES (Endorsing Light Validity Evaluator System) 即轻量级背书有效性评估系统。它是 JAM 可扩展且自适应的区块审计协议，即是JAM用于finalise区块的协议, 确保只有有效区块才能最终确定。

论文 – 2024-961 : Jeff Burdges、Cevallos 等人在2024年提出的 ELVES 方案。该方案采用非冗余验证者分配策略，并将其与验证者参与的提议与审计博弈相结合。这一机制旨在清除和惩罚无效计算，同时确保一个网络的最终性状态依赖于所有因果相关的网络。

(1)加密经济机制-ELVES的作用

该协议的总体思路是随机选择一小部分初始参与方（例如，使用 VRF）来重建和审计区块。如果存在相互矛盾的声明，或审计员缺席，则会为该区块分配更多审计员。

ELVES 确保验证者在区块成为平行链状态的一部分之前共同确认其有效性。

验证者通过质押获得激励，并因恶意或错误操作而受到惩罚，以确保其遵守协议。这种方法最大限度地降低了无效状态在网络中传播的可能性，从而为平行链提供了强大的安全性。

(2)ELVES 的运⾏分为⼏个阶段

在第⼀个“⽀持”阶段，⼀些称为“⽀持者”的初始审计员接收区块，检查区块，然后签署声明，声明该区块有效。
在第⼆个“可⽤性”阶段，⽀持者分发区块，以便任何审计者都可以选择检查该区块。我们通过为每个审计者分配⼀个区块 Reed-Solomon 编码的符号来保持此分发过程的带宽效率。验证者同意，该区块的分发⽅式确保了其在拜占庭假设下能够重建。
在第三个“批准”阶段，我们随机指派⼀组初始审计员来检查, 每当指定的审计员没有及时做出反应时，该块就会随机增⻓ (⽤⾜够多的随机审计员替换所有缺席的审计员)
第四阶段，如果任何审计员声称该区块⽆效，则所有审计员将进⼊“争议”阶段进⾏核查，并通过常规拜占庭投票解决。
第五阶段, 最终确定区块

投票结果: 如果发现某个区块⽆效，那么我们将永久地弹出其⽀持审计员（在权益证明协议中，⽀持这些审计员的权益应被没收，例如在 Polkadot 中进⾏ 100％削减）。

(3)基于Gearbox的审计员选举协议

重点：

任何遵循非负预期利润策略的理性对手都无法使协议接受无效区块
如果接收有效区块作为输入的初始审计方是诚实的，则所有验证者都同意该区块有效。
每个验证区块所需的审计验证者数量为 $O(logn)O(log\ n)$

Gearbox协议

Gearbox [DMM+22]协议利⽤安全性与活性⼆分法优化了分⽚规模。具体⽽⾔，该协议最初选择规模较⼩的委员会以确保安全性（但可能牺牲活性），但之后逐渐选择规模更⼤的委员会以实现活性。该协议在部分同步模型下运⾏，并考虑了静态腐败。我们的协议 ELVES 在此基本理念的基础上更进⼀步，并在两个⽅⾯有所不同：

Gearbox ⽆法对抗⾃适应崩溃对⼿，因为对⼿可以轻易地让分⽚中的所有参与⽅崩溃；我们的协议以⼀种直接的⽅式解决了这个问题，即在未收到⾜够多的有效响应时，尽可能地向所有参与⽅扩展分⽚规模；
更重要的是，我们的协议实现了更⼩的委员会规模。具体⽽⾔，对于 $2^{-60}$ 的错误率和 1/3 的腐败率，我们的委员会规模约为 400，⽽ Gearbox 需要 1000 个参与⽅。

怎么成为审计员?

⾸先乐观地选择⼀个规模较⼩的委员会来检查区块，其中⾄少有⼀名诚实⽅当选的概率很⾼。如果没有达成⼀致意⻅，我们将回到稻草⼈⽅法，选择⼀个规模更⼤的委员会，并获得三分之⼆多数票。这样做，在乐观条件下，只会部署规模较⼩(约数十人)的委员会。我们可以进⼀步发展这个想法，通过分⼏个步骤添加参与⽅：不是直接回到稻草⼈⽅法，⽽是可以逐渐添加参与⽅，直到委员会规模达到稻草⼈⽅法的规模。

验证区块所需的审计验证者数量为 $O(logn)O(log\ n)$ , ⼀个区块中的审计员数量服从⼆项分布 Binom(n,sδ /n)

区块分发后，我们使⽤ VRF 选举初始审计委员会C0，各⽅以固定概率独⽴分配到该委员会，因此C0的预期规模较⼩，约为数⼗⼈。

区块⽀持者
- 审计员轮流担任新区块的⽀持者
- 一个区块一个支持者; 同⼀时间处理的两个区块由不同的⽀持者分发
- 向全体审计员发送RS编码分片与Merkle路径证明
使⽤ VRF 从全体审计员中选举出初始审计委员会(约数十个)
- 重建区块
- 验证
- 投票
全体审计员约400个, 作为候选
- 有审计员未及时响应时,自动选一个新的替换.
- 如果发现区块无效, 则全员进行拜占庭投票 (估计是一轮2/3投票,如果两轮的话,网络压力巨大为 $O(n^2)$ )

怎么审计?

(一个或多个)⽀持者验证通过后, 广播签名和区块给初始审计员验证. 如果初始审计员是诚实的，则所有初始审计员都同意该区块有效; 如果发现区块无效, 则进行常规拜占庭投票解决, 如果投票结果确实无效, 支持它的初始审计员将被剔除和罚没

委员会选举与检查：C0 中的每⼀⽅发布其分配证明，依次接收来⾃ S 中各⽅的代码字，重建并审计区块 B，并发布其结果。此时有三种情况：

1）某些⽅声称该区块⽆效；

检查会升级到所有参与⽅，并进⾏多数投票来决定区块是否有效，少数⽅会被罚没，⽀持者则被纳⼊⽀持该区块的⼀⽅

2）所有宣布其任务分配的各⽅声称该区块有效

该区块会被接受。

3）有⼀些未出现的各⽅宣布了其任务分配但未按时公布其审计结果。

对于每个缺席的参与⽅，都会选举出⼀个新的、预期规模恒定的参与⽅（⼦集），并将其添加到审计委员会，规则 1 ⾄ 3 将再次应⽤于新当选的参与⽅。

(4)基于RS纠删码的分发方案

可⽤性分发：⽀持者将初始区块 B 分发给所有参与⽅。更准确地说，⽀持者使⽤重建阈值为参与⽅ 1/3 ⽐例的纠删码，获得码字 $s_1, ..., s_n$ ，并将其编码到 Merkle 树中，为每个码字 $s_i$ 获取⼀个证明 $π_i$ 。每对 $s_i , π_i)$ 都会以双边⽅式发送给参与⽅Pi ，Pi随后会发布投票，表明收到的对 $s_i , π_i)$ 是否正确。当 2/3 参与⽅的集合 S 发布投票时，此阶段结束。
可⽤性⽅案由⼀对 (Dist, Rec) 分布式协议组成。在协议 Dist 中，指定⽅ P（经销商）持有要分发的输⼊消息 m。在协议结束时，所有参与⽅就协议是否成功达成⼀致，如果成功，则每⼀⽅ Pi输出⼀个==编码数据⽚段 (si , πi)==和⼀个正确性证明。在协议 Rec 中，每⼀⽅Pi向接收者 R发布其对 (si , πi) ，接收者 R 应⽤⼀个函数来重建原始消息 m。

引理 1. 协议 (Πt Dist, Πt Rec) 是一种安全可用性方案，在存在总计 γ < 1/3 的损坏（可能是静态主动或自适应崩溃）的情况下。

证明。我们首先论证正确性。如果庄家 P 是诚实的，则 P 计算出 m 的正确 Reed-Solomon 编码，且根出现在 F ∆ smr 中。此外，每个诚实方在最多 ∆ 时间后都会收到一个有效对 (si , πi)，并在 F ∆ smr 中发布签名投票。因此，在 ∆ 时间后，至少出现 (1 − γ)n 个签名投票，则 ΠDist 被视为成功。

(5)基于Merkle证明和拉格朗日插值法的批准方案

引理 2. 设 Q 为 Merkle 树诱导的输入谓词。也就是说，每一方都有一个对应于叶子节点的私有输入 (si,πi)，以及一个关于公共输入 Com（即 Merkle 根）的 Merkle 树证明，所有参与方都接收该公共输入。进一步设 VerifyData 表示有效性谓词。则协议 ΠAppr 是一种安全的批准方案，当存在最多 γ < 1/3 的损坏时，这些损坏可能是静态主动或自适应崩溃。

(6)ELVES协议

将各⽅分为两种⻆⾊：

初始审计者（称为“⽀持者”），他们获得区块作为输⼊（以及有效性证明）；
以及“验证者”，他们将区块提供给其他⽅并检查其有效性。

缺点

然而，实施 ELVES 方案需要更为复杂的逻辑设计，并且由于网络间的因果纠缠，可能会对网络的可扩展性，即可以添加的网络数量，构成一定的限制。

附录

名词

$F ^∆ _{smr}$ : 各方可以访问资源（又名主链）
- smri = (smri [1],smri [2], . . .): 状态机复制资源, 每一方 Pi 输入一条消息，并跟踪一系列消息, 每个索引一个，即输出给 Pi 方
- com: 承诺, 即 Merkle Root
$F ^∆ _{p2p}$ : 各方可以访问完整的网络
- $F ^∆ _{flood}$ : 扩散网络功能
$^p _{ce}$ : 委员会选举预言机功能
Πid: 作弊识别
ΠAppr: 容错1/3的安全批准方案

数字签名

数字签名⽅案由三个算法（KGen、Sign、Ver）组成，定义如下：

KGen(κ) 是密钥⽣成算法，它采⽤安全参数并输出验证/签名密钥对 (vk,sk)。
Sign(sk, m) 是⼀种签名算法，它以签名密钥和消息作为输⼊，并输出签名 σ
Ver(vk, m, σ) 是⼀种验证算法，其输⼊是验证密钥、消息和签名。如果 σ 是验证密钥 vk 下 m 上的有效签名，则算法输出 1，否则输出 0。

RS纠删码⽅案 (ECCS)

能够容忍⼀定次数擦除的纠删码⽅案. 设 n 为共享数，t 为可容忍的擦除次数。(t, n) 擦除编码, 即重建阈值为t. (用到拉格朗日插件法)

编码⽅案（ECCS）由两种算法组成：

Enc 接收消息 m 并⽣成⼀系列份额 $s_1, ..., s_n$ 。
Dec 取一系列份额 $s′_1 , . . . , s′_n$ ，使得对于至少 n − t 个份额 $s′_i = s_i$ ，对于剩余的份额 $s′_i = ⊥$ ，(⊥表示已被腐蚀, 即作恶) , 则输出原始消息 m
我们使⽤标准 Reed-Solomon 码 [RS60] 来有效地实例化 (t, n)-ECCS，其中每个份额的⼤⼩为 $O (ℓ / (n - t))$ ,对于⼤⼩为ℓ位的消息