论文记录-分片相关

关于区块链分片的几篇论文。

1. RapidChain: Scaling Blockchain via Full Sharding

Abstract

1. 分片目的：解除区块链性能和扩展性的限制
2. 分片定义：将处理事务的开销分配给多个更小的节点组，这些组并行工作以最大限度地提高性能，同时显著地减少每个节点的通信、计算和存储，从而允许系统扩展到大型网络。
3. 现有分片协议的问题：扩展性受限制、安全性
4. 本文RapidChain：公链分片

Method

1. 节点分到不同的committees，区块和账本并行

2. 系统中一共n个节点，则每个committee的大小为$m=c logn$，一共有$k=n/m$个committees，c是一个和安全有关的常数

3. 优点：

   1. 次线性通信：每个事务线性复杂度
   2. 高弹性：可以接受1/3的恶意节点
   3. 减少每个committee的开销和延迟
   4. 安全性：拜占庭容错
   5. 跨分片验证：committees通过路由机制发现其他committees
   6. 去中心化引导：新加入节点的设计

4. RapidChain按固定时间周期推进，称为epoch，每个epoch结束时由被选中的reference committee（$C_R$)生成下一轮的随机数，该随机数让每个节点在下一轮开始时有新身份，并避免恶意节点的集中和节点共谋

5. 对等发现和committee间的路由，存交易事务$t_x$的committee记作$C_{out}$

6. 跨分片验证：$C_{out}$在生成区块记账之前会和input committee验证交易合法性

7. 分片内共识：

   1. 分片内成员用当前epoch的随机数选一个临时leader
   2. leader用流言协议把区块发布给分片内所有节点
   3. 使用拜占庭协议（基于某论文的同步协议）确保所有节点同意同一个区块

8. 重新配置区块：每个epoch结束时由$C_R$产生，包含内容：

   1. 下一轮的随机数
   2. 参与者列表和committee成员

   想参加下一轮的节点要在一定时间内解题PoW

9. 这篇的related work部分之后可以参考

2. A Secure Sharding Protocol For Open Blockchains

Abstract

1. 区块链有安全性，但规模很小，每秒处理3-7笔交易
2. ELASTICO：1/4拜占庭攻击，分为多个committees，每个处理自己的事务集合（称作分片）

Mehtod

1. 按算力分片
2. 每个epoch流程：
   1. 建立自己的公钥、IP并进行PoW，按公钥ID分为不同Committees
   2. 节点互相确认身份，记录自己committee有谁
   3. committee内的共识：PBFT，带多数成员签名广播
   4. 最终共识广播：有一个final committee来进行合并（PBFT然后把接收的分片区块在committee内实现共识，然后全网广播）
   5. 产生下一轮的随机数，大家开始PoW，开始新的一轮

3. A Proof of Stake Sharding Protocol for Scalable Blockchains

1. c组，每组n个，一共nc个节点
2. 普通节点组产生中间区块，发送给最终验证节点组
3. 最终验证节点组产生最终区块，全网广播
4. 每个epoch分为4步：
   1. 分组，组内随机选leader，组内节点把身份信息发给leader，leader向其他组的leader广播
   2. 组内共识：一个交易随机分到某组，组内节点PoS，产生新的中间区块
   3. 最终验证组合并区块，组内PoS，产生最终区块并广播
   4. t轮之后，刷新重组

4. Ostraka: Secure Blockchain Scaling by Node Sharding

1. 采用UTXO、PoS
2. 矿池、UTXO、区块链存储在被称为分片（shard）的几个机器上，机器可以扩展，每个分片的节点数量不一定一样
3. 有一个机器称为 coordinator跟踪区块链并协调节点间的通信，可以要求某分片回滚到某区块链状态或开始新的链
4. 分片有一个ID，由coordinator分配，决定该分片处理哪些事务
5. 女巫分片：节点相同的分片
6. 事务切分存储在对应分片上
7. 总的来说就是有个类似路由器一样的机器来协调处理跨片事务，这篇基本上没看懂，以后有需要再看看

5. OptChain: Optimal Transactions Placement for Scalable Blockchain Sharding

1. 新分片方式，最小化跨分片事务，动态事务分配，把相关和即将相关的事务分组到同一分片
2. 对事务分片的依据：
   1. 这样分是否减少了跨片事务
   2. 分片间的负载平衡
3. TaN结构：UTXO模型的事务网络图结构
4. 跨分片事务处理流程：
   1. 用户创建跨分片事务，流言广播
   2. 几个UTXO所在的分片锁定UTXO并流言广播许可（或不许可）
   3. 接收事务的分片解锁UTXO并记账
5. 对事务分片的算法：
   1. TaN：把UTXO事务看做图里的节点，然后按图的拓扑结构分析出度和入度
   2. T2S：用PageRank评分，判断节点加入哪个分片——>尽可能减少跨分片事务
   3. L2S：确认延迟，网络结构决定事务得到确认所需的时间——>尽可能加快事务确认速度
   4. T2S和L2S结合选择事务分片

6. Poster: A Proof-of-Stake(PoS) Blockchain Protocol using Fair and Dynamic Sharding Management

1. 每个epoch会重新分片并选择每个分片的block producers
2. 在上一个epoch中，users用自己的信息和一部分资产注册成为validator（验证器），这个epoch开始以后，validator和事务被分成k个分片，分片规则为：
   1. 验证器的地址和上一个区块的哈希值一起哈希然后对分片个数取余，即可得到验证器的分片
   2. 事务地址和…，即可得到事务的分片
3. 使用BFT-DPoS算法，在每个分片内选block producers：
   1. 股权最大的成为该分片的producer
   2. 所有producers按顺序循环选总的producer
   3. 矿工可以投出与他们所持股份的平方根成比例的选票，而不是与所持股份成线性比例的选票。
   4. 根据BFT算法，分片的producer产生自己分片的区块，并由总producer合并广播

7. SSChain: A full sharding protocol for public blockchain without data migration overhead

1. 公链，拜占庭弹性，对事务分片和对状态分片，节点无需定期切换分片（避免数据冗余），使用UTXO

2. 节点可以自由加入分片而无需刷新，为避免随之而来的51%攻击问题，本文提出了一个双层结构：

   1. 根链验证分片的区块，避免恶意节点攻击，激励机制保证矿工愿意加入
   2. 分片维护不相交的分类帐并独立处理不相交的交易子集。
   3. SSChain背后的关键思想是根链维护系统的安全性，而切分提高了吞吐量并减少了存储需求。

3. 同一分片内的交易有更低的确认延迟和更少的交易费用，进而鼓励用户片内交易

4. 解耦事务验证和状态更新，拆分跨分片事务

5. 激励机制：动态调节根链和分片的算力分配，根据参数可得到不同的吞吐量和安全性

6. 跨分片事务：切分成分片内事务，或者由根链处理

7. 根链：PoW，分类帐修剪机制

8. 事务分片：

   1. 事务地址包含比特币地址和分片ID
   2. 交易分类：
      1. inputs和outputs在一个分片内
      2. inputs在一个分片内，outputs在不同分片
      3. 都在不同分片
   3. 跨分片事务：
      1. 交给根链——>随分片增长会很难处理
      2. 鼓励用户在同一分片内创建新地址——>跨分片变成同一分片
      3. A+B——>C的事务拆分成A——>C和B——>C（个人感觉这没用啊）

9. 状态分片：一些节点储存整个区块链的状态而不是只存分片状态

10. 市场激励机制：动态地调整切分和根链之间的哈希功率分配。在激励机制下，矿商可以自由选择最赚钱的碎片，从而避免了周期性的网络重组。有两个目的：

    1. 为了维护系统安全，根链占用了整个网络的很大一部分算力。由于切分块是由根链网络验证的，恶意对手至少需要根链哈希能力的一半才能进行双倍开销攻击。
    2. 算力被鼓励平均分配到碎片中，这样每个碎片都可以正常工作。

8. Trust-Based Shard Distribution Scheme for Fault-Tolerant Shard Blockchain Networks

1. TBSD：把恶意节点放到不同的分片，使用信任管理系统和遗传算法
2. 定量衡量节点的信任度，对恶意节点进行信用惩罚
3. 遗传算法找到最优分片方法，使得每个分片的信用度都差不多
4. 总的来说信用系统分为5步：
   1. 每一轮开始时，PoS选一个leader出块
   2. 全网广播验证区块，少数服从多数
   3. SCO：节点信用表，由验证节点产生，上一步的验证结果作为信用评分的依据
   4. LCR：根据SCO计算得到的相对信用分布矩阵
   5. 最终信用评估
5. 攻击模型：
   1. 恶意节点成为leader
   2. 节点共谋
   3. 恶意节点行为不一致，一会儿诚实一会儿恶意
6. 分片过程：用GA

9. Two-Phase Cooperative Bargaining Game Approach for Shard-Based Blockchain Consensus Scheme

1. 分片后，进行议价博弈，事务总的来说平分给每个分片处理
2. 有一个adjust shard负责确认，其他分片进行普通的挖矿
3. 随机数分片，分片内共识：标准拜占庭一致协议，看起来是对节点分片
4. 节点验证事务和参与共识的过程可看做两阶段博弈：
   1. 事务分配问题
   2. 基于分片的共识机制
5. 讨价还价博弈这里没完全看懂，感觉就是分片和节点根据奖励和支出决定是否处理事务，上面的4.1里博弈方是分片，4.2的博弈方是区块链节点

A Node Rating Based Sharding Scheme for Blockchain