·1366 工程科学学报，第41卷，第11期 完之前不会显示) 5 共识算法 (3)Multi-Signature (MultiSig) a)scriptPubKey:M <pubkey 1>...<pubkey N>N 5.1共识算法分类 OP_CHECKMULTISI 共识算法(consensus algorithm)是指在多方协 b)scriptSig:OP_0<signature 1>..<signature M> 同环境下使所有参与方对任务执行结果达成一致 Multisig允许在几个地址之间共享数字资产 (共识)的算法)共识算法多应用于确保分布式 的控制.在创建脚本时，可以指定控制资产的公 系统数据一致，在区块链中引入共识算法最早是 钥，以及签署有效支出交易所需的密钥数量 为了解决新交易块加入哈希链表中可能出现的 (4)Pay-to-Script-Hash(P2SH) “块冲突”问题，也就是同时多个块被不同的 a)scriptPubKey:OP HASH160 <scriptHash> 块创建者加入到哈希链表中而引起的链表分叉 OP EQUAL (forking)问题回，它可能会导致双重花费(double b)scriptSig:<signatures><script> spending)与交易无效的风险 P2SH是一段包含了其他脚本哈希值的脚本， 区块链共识算法根据设计思想可分为以下 任何想要花费P2SH类型输出的交易需要提供匹 几类： 配该哈希值的脚本 (1)证明类：核心思想是建块节点需证明自己 (5)Data Output(OP_RETURN) 具有某种能力或完成了某种事情才能合法建块， a)scriptPubkey:OP RETURN <data> 通常共识方式是完成一些难以解决却易于验证的 b)NO scriptSig 难题去竞争建块的权利阿常见的有工作量证明 Data outputs常被用于向区块链中添加额外数 (proof of work,PoW)2,权益证明(proof of stake,. 据，一般数据大小不超过40字节 PoS)27等 (2)拜占庭类：以拜占庭协议为基础设计整个 4 区块链网络 算法，建块节点通常是由其他节点投票选举或从 区块链建立在非中心化的、对等点对点(P2P) 所有符合一定条件的节点中随机选举.常见的有实 网络基础上，可支持全球范围内任意人员自由接 用拜占庭容错算法(practical Byzantine fault tolerance,. 入退出四网络中的资源和服务分散在所有节点 PBFT)2,Algorand算法29等 上，信息的传输和服务的实现都直接在节点之间 (3)传统共识类：将传统分布式系统的一致性 进行，无需中间环节和服务器的介入，避免了可能 算法应用于区块链系统.通常算法共识效率较高， 的瓶颈 但不支持拜占庭容错，即不考虑恶意篡改和伪造 区块链按技术类型可分为公有链和联盟链. 数据的拜占庭节点.典型的有Rat算法B0 公有链在网络拓扑上服从小世界模型(small (4)混合类共识：使用多种共识算法的混合体 world model)2).该模型具有特征路径长度较小、 来选择建块节点.比如PoW和PoS混合的Casper 聚合系数较大的特点，在这样的网络中，数据只需 算法B),Raf与PBFT混合的Tangaroa算法B等 要经过较少节点(6度原则)就可达到目的节点，从 以下几小节简要阐述包括工作量证明，权益 而保证了交易信息在大规模区块链网络(10万以 证明，实用拜占庭容错和Algorand在内的几类代 上节点)中传播的高效性.公有链网络拓扑的“高 表性区块链共识算法， 聚集度”和“短链”特征使得区块链可以支撑世界 5.2工作量证明(PoW） 各地的海量用户进行大规模、并发地交易，及时地 PoW是比特币中使用的共识算法，其核心思 将交易数据通过记账节点生成区块的方式存储， 想是通过节点的计算能力，即“算力”来竞争建块 并实现全网内的数据同步，为保证区块链数据的 权和奖励.算法关键是在区块头中加入不同的随 健壮性、完整性和一致性奠定了网络基础 机值，计算区块头哈希值，直到此哈希值小于或等 联盟链基于全连通网络，所有节点都是互连 于目标值，解决此问题的过程称为挖矿(mining) 的.每个节点能够管理较大规模用户，包括，用户 挖矿可分为两个步骤，第一步为获取当前的目标 个人信息、权限、密钥（包括公私密钥）等.与公 值.目标值T是一个256位的二进制数字，图3中 有链任何人可随时加入和撤离不同，联盟链中节 nBits是T的32位紧凑表示，它可被8个16进制数 点通常数目固定、接入管理更加严格 0xhoh1h2h3h4 hshoh7编码，T的计算公式B为：完之前不会显示）. （3）Multi-Signature (MultiSig) a） scriptPubKey: M <pubkey 1>...<pubkey N> N OP_CHECKMULTISI b）scriptSig: OP_0 <signature 1>...<signature M> Multisig 允许在几个地址之间共享数字资产 的控制. 在创建脚本时，可以指定控制资产的公 钥，以及签署有效支出交易所需的密钥数量. （4）Pay-to-Script-Hash (P2SH) a） scriptPubKey:  OP_HASH160  <scriptHash> OP_EQUAL b）scriptSig: <signatures> <script> P2SH 是一段包含了其他脚本哈希值的脚本， 任何想要花费 P2SH 类型输出的交易需要提供匹 配该哈希值的脚本. (5) Data Output (OP_RETURN) a）scriptPubkey: OP_RETURN <data> b）NO scriptSig Data outputs 常被用于向区块链中添加额外数 据，一般数据大小不超过 40 字节. 4    区块链网络 区块链建立在非中心化的、对等点对点（P2P） 网络基础上，可支持全球范围内任意人员自由接 入退出[21] . 网络中的资源和服务分散在所有节点 上，信息的传输和服务的实现都直接在节点之间 进行，无需中间环节和服务器的介入，避免了可能 的瓶颈. 区块链按技术类型可分为公有链和联盟链. 公有链在网络拓扑上服从小世界模型（small world model） [22] . 该模型具有特征路径长度较小、 聚合系数较大的特点，在这样的网络中，数据只需 要经过较少节点（6 度原则）就可达到目的节点，从 而保证了交易信息在大规模区块链网络（10 万以 上节点）中传播的高效性. 公有链网络拓扑的“高 聚集度”和“短链”特征使得区块链可以支撑世界 各地的海量用户进行大规模、并发地交易，及时地 将交易数据通过记账节点生成区块的方式存储， 并实现全网内的数据同步，为保证区块链数据的 健壮性、完整性和一致性奠定了网络基础. 联盟链基于全连通网络，所有节点都是互连 的. 每个节点能够管理较大规模用户，包括，用户 个人信息、权限、密钥（包括公/私密钥）等. 与公 有链任何人可随时加入和撤离不同，联盟链中节 点通常数目固定、接入管理更加严格. 5    共识算法 5.1    共识算法分类 共识算法（consensus algorithm）是指在多方协 同环境下使所有参与方对任务执行结果达成一致 (共识) 的算法[23] . 共识算法多应用于确保分布式 系统数据一致，在区块链中引入共识算法最早是 为了解决新交易块加入哈希链表中可能出现的 “块冲突”问题[24] ，也就是同时多个块被不同的 块创建者加入到哈希链表中而引起的链表分叉 （ forking）问题[2] ，它可能会导致双重花费（ double spending）与交易无效的风险. 区块链共识算法根据设计思想可分为以下 几类： （1）证明类：核心思想是建块节点需证明自己 具有某种能力或完成了某种事情才能合法建块， 通常共识方式是完成一些难以解决却易于验证的 难题去竞争建块的权利[25] . 常见的有工作量证明 （ proof of work，PoW） [26] ，权益证明（ proof of stake， PoS） [27] 等. （2）拜占庭类：以拜占庭协议为基础设计整个 算法，建块节点通常是由其他节点投票选举或从 所有符合一定条件的节点中随机选举. 常见的有实 用拜占庭容错算法（practical Byzantine fault tolerance， PBFT） [28] ，Algorand 算法[29] 等. （3）传统共识类：将传统分布式系统的一致性 算法应用于区块链系统. 通常算法共识效率较高， 但不支持拜占庭容错，即不考虑恶意篡改和伪造 数据的拜占庭节点. 典型的有 Raft 算法[30] . （4）混合类共识：使用多种共识算法的混合体 来选择建块节点. 比如 PoW 和 PoS 混合的 Casper 算法[31] ，Raft 与 PBFT 混合的 Tangaroa 算法[32] 等. 以下几小节简要阐述包括工作量证明，权益 证明，实用拜占庭容错和 Algorand 在内的几类代 表性区块链共识算法. 5.2    工作量证明（PoW） T T 0xh0h1h2h3h4h5h6h7 T PoW 是比特币中使用的共识算法，其核心思 想是通过节点的计算能力，即“算力”来竞争建块 权和奖励. 算法关键是在区块头中加入不同的随 机值，计算区块头哈希值，直到此哈希值小于或等 于目标值，解决此问题的过程称为挖矿（mining）. 挖矿可分为两个步骤，第一步为获取当前的目标 值. 目标值 是一个 256 位的二进制数字，图 3 中 nBits 是 的 32 位紧凑表示，它可被 8 个 16 进制数 编码， 的计算公式[33] 为： · 1366 · 工程科学学报，第 41 卷，第 11 期