Video
视频链接：https://www.youtube.com/watch?v=vHVZ2gD8Ie4&ab_channel=AllHackingCons
github：https://github.com/dedis/student_18_byzcoin
Motivation
进行分片时需要考虑的问题：
- 验证者如何被分配到不同分片中去
- 如何实现跨分片的交易
对于第一个问题，显然不能让验证者自己选择进去哪个分片，如果随机选择，需要保证分片大小足够大（失败概率为$10^{-6}$，分片大小在$10^3\to10^4$），符合leopard
在SimpleLedger的例子中，每轮有一个可信的random beacon，将验证者分到不同的分片中，且验证者能够验证哪些验证者跟自己在同一个分片
简单的设计，带来了很多问题
安全性方面：
- 依赖第三方可信的random beacon
- 重配置阶段不支持处理交易
- 不支持跨片交易
OmniLedger
主要有6部分工作，包括DRB 平稳的轮切换等，主要介绍三个
DRB
原子跨片交易
参考了数据库领域的工作，2阶段承诺
存在问题：2阶段承诺不是时间容忍的，敌手可以abort
将分片作为server，client将没有commit的交易输入锁定，等待对应输入分片的证明后解锁
延迟和吞吐量的trade-off
增大区块大小可以增加吞吐量，但是发送区块和验证区块的延迟会增加
Omniledger的思路是牺牲部分安全性来降低延迟
存在两层验证，一层处理数额较小的输入，安全性为90%，一层处理重要的交易
Evaluation
Go语言编写，https://github.com/dedis/student_18_byzcoin
采用了dedis实验室的代码 https://github.com/dedis
首先测试scale-out，增加节点数量
1120是分片大小为70，16个分片，考虑敌手比例最多为25%，低于BFT的容错
对于延迟，分别测试了2层验证的耗时
Conclusion
Q&A
Q: 网络分区的影响
A: 如果发生网络分区，协议停止，不违反比特币的安全性
Q: 和Algorand的区别
A: Algorand没有sharding，可以选择将Algorand作为片内共识算法，Omniledger在Algorand之上，可以得到更好的敌手容忍比例
Q: 交易如何分配到分片内
A: Omniledger片内共识是参考比特币的，因此节点本地有UTXO数据库。如果存在跨片交易，依赖于原子承诺的设计，输入分片会commit或者abort
Q: 表格中安全性仅考虑到了25-30%，失败概率$10^{-6}$，如何实现容忍$10^{-10}$的错误概率
A: 更大的分片大小，trade-off
Q: 因为目前矿池集中的算力超过了25%，可能达到30% 40% 45%，作者认为可能会如何
A: 片内如果用比特币的共识能容忍50%的敌手
Q: 最坏情况下的性能，如所有交易都是跨片交易
A: 当所有交易都是跨片交易，不再是线性增长的。采用单个共识算法的效率会比sharding更好
Q: 敌手能否让所有交易都成为跨片交易？
A: 交易是由client发起的，不是由敌手选择的，因为交易有手续费，跨片交易的手续费比普通交易更高，如果跨3个片交易费可能是片内交易的三倍