杭州女密码学家提出新区块链共识算法

共识机制是区块链和分布式计算的基础。 例如，比特币采用的PoW（Proof of Work）是一种竞争机制，让最好的节点完成计算工作以获得系统的数字货币奖励。 近年来，PoW共识机制逐渐暴露出资源消耗大、运行成本高的问题。 问题，一些替代方案如 PoS 也被提出并引起了学术界的极大兴趣。 例如，康奈尔大学 IC3（Initiative for Cryptocurrency and Contracts，虚拟货币和合约倡议）项目联合主任 Elaine Shi 教授在 2017 年提出了基于 SleepyModel 的 PoS 共识并将其形式化。 和安全分析。

与我们所熟悉的各种加密货币的共识机制不同，Sleepy Model的提出旨在解决在当今互联网规模达百万甚至数百万的情况下，如何在保持系统效率的同时保持系统的健壮性的问题更多节点。 问题。 史润亭教授认为，虽然区块链技术已经在虚拟货币上得到成功应用，但目前普遍的共识机制并不适合推广到互联网级别的规模。 互联网规模的分布式系统需要一个新的理论框架和可验证的安全性。 协议和实施方案，这也是区块链技术从虚拟货币走向更广泛应用的关键点。

背景

在计算机科学中，为了解决单台计算机性能不足以及某些应用中需要更大存储和更强计算能力的问题，一些研究人员将一组计算机连接起来并相互交互以实现一个共同的目标。 通过网络互连来传递消息和通信，并协调它们的行为，这也是“分布式计算”的起源。

随着摩尔定律遇到瓶颈，越来越多的系统依赖于分布式集群架构来实现海量数据处理和可扩展的计算能力。 区块链的产生是为了解决各个节点之间的互不信任和协同工作的需要。 与一般的分布式系统不同，一般的分布式系统通过一个共同的中心实现相互信任，而区块链链中的各个节点通过共识机制实现相互信任。 可以说，共识机制是区块链和分布式计算的基础。

关于分布式计算的文献，以及关于密码学的文献，通常考虑两种类型的参与者：诚实的和不诚实的。 然后分析上述弹性属性，假设诚实玩家的比例有一个下限。 对于通常部署共识协议的传统环境，如谷歌钱包等应用，节点数量在十几个左右，而在大规模共识协议（注：如区块链协议）中，不仅用户数量有显着增加，但达成共识也更加复杂，现有的共识机制不能很好地满足鲁棒性的要求。

在Real World Crypto 2017 Security Conference上，史润亭教授首次对基于Sleepy Model的PoS共识机制进行了阐述，雷锋网根据该论文进行了缩略改编：

“互联网规模”共识机制

我是来和大家一起探讨互联网规模的共识机制的。 有些人可能还记得，去年 8 月的一天，达美航空的系统完全崩溃，您无法预订机票，而且由于达美航空的计算基础设施出现故障，所有航班都被取消。 类似的情况也出现在国科会，去年7月份就出现过系统宕机，还得继续等。 好吧，如果我不能飞，我可以忍受它，但如果我不能做科学研究，那么我会说这让我很难过。

我们关注两点：可复制性和稳健性。 在计算机科学中，这被称为分布式系统，这个领域已经研究了将近 30 年。 分布式系统中有一个非常重要的抽象，我们称之为“状态机复制”，也称为“线性”或“共识机制”。

那么什么是状态机复制呢？ 下面是一个应用场景：以谷歌钱包为例，谷歌可能会考虑备份其服务器。 您肯定不想损失在 Google 上存的钱，因此备份是个好主意。 当一台服务器出现问题时，所有这些服务器上都会有线性排序的日志。 我们将关注两个安全属性：一致性和活跃性。 一致性是指所有诚实的服务器节点都同意这些交易日志，而活跃性是指如果一个客户端提交了一个交易，这个交易需要被迅速记录在所有的服务器上。

问题是：如果某些服务器遭到破坏怎么办？ 有问题的服务器背叛其他服务器的问题非常重要。 当我们讨论共识问题时，一般来说，这些服务器属于一个群体，我们可以认为这些服务器是相互信任的。 我们今天之所以认为比特币令人兴奋，是因为比特币开启了分布式计算的新篇章。 它提出的分布式共识是惊人的，也让互联网规模的共识成为可能。

但是，我们知道互联网上有数百万甚至更多的节点。 这些节点不一定在线，有的在线，有的不在线。 有很多不可预知的情况才能形成共识。 同时，每个节点都是自私的，因此彼此不信任，这也对“互联网规模”的共识机制提出了新的挑战。

我在虚拟货币圈子里和很多人交流过。 他们或多或少认为目前的共识机制或多或少无法适应互联网层面的规模，因为这些共识机制在互联网层面的大规模复杂状态下是健壮的。 性不好。 关于互联网规模共识的健壮性，这是一个很大的话题，我这里不展开，但是我们会从一些基本的问题入手，来解释什么是健壮性。

我们刚刚经历了美国总统大选。 一共3亿人（节点），1.6亿人出现（投票），如果我们想，如果这些出现（投票的人）中有51%是诚实的，否则我们无法正确预测选举结果，这是共识的例子。

这里我们假设一些节点在线，一些节点正在休眠。 在线意味着这些节点将积极参与共识协议，而睡眠节点可能会从睡眠中恢复并继续加入共识协议。 这是一个“困模型”。 我们对这个模型有额外的假设：

作恶节点不能任意行动（不能背离基本协议规则）；

作恶节点可以延迟和修改消息；

在线诚实节点可以快速接收消息，否则将被视为休眠节点；

在这种环境下，我们很自然地会问一个问题：

当只有 51% 的在线节点是诚实的时，我们能达成共识吗？

这有3个难点：

1）协议对在线节点的比例没有任何先验知识。 在线节点可能是30%或1%；

2）你不能做出假设。 你可以假设30%的在线节点参与了协议，但实际上只有1%的人参与了协议，而这99%的休眠节点不会影响1%的在线节点的共识结果；

3）另一种情况是，在这个过程中，会有“沉睡”的节点苏醒，它们会收到之前所有未决的信息，参与共识投票，这会导致安全问题。

经典共识协议的失败

我们的研究结论可能会让你大吃一惊：即使99%的在线节点是诚实的，目前所有的经典共识协议都无法在这种情况下顺利运行。 我简单说明一下，经典的共识协议可以分为两类，即同步共识协议和异步共识协议。 在同步协议中，可以立即接收到信息，而在非同步协议中，攻击者可以随意修改信息并延迟发送出去。 为什么它在同步协议中失败？ 原因很简单，因为一直在线的节点是顺序接收信息的，而在“Sleep Model”中比特币采用了pow共识算法，我们让休眠的节点在醒来后接收信息。 而且信息的延迟存在不确定性。

那么，为什么异步协议也会失败呢？ 原因是在异步协议中，休眠节点会被视为恶意节点。 假设某个协议在已知数量的情况下可以允许1/3的作恶者存在，但是如果99%的节点都是休眠节点，那么这些节点就被认为是作恶节点，那么就无法获得足够的票数来达成共识。

我们说比特币的中本区块链（PoW模式）健壮，有两层意思：优点是中本区块链可以在大多数在线节点诚实的情况下达成共识； 但缺点是：能耗太高。 今天，1.5GW 的电力用于比特币挖矿，这比美国最大的核电站或美国太阳能发电的 10% 还多。

我们能否在不付出高昂代价的情况下实现中本聪区块链的健壮性？ 解决方案是：保留中本聪的区块链结构，但去掉PoW共识； 挑战是在保持安全的同时实现这一点？

我简单介绍一下区块链的机制。 中本聪区块链对之前的区块数据和交易进行哈希处理。 为什么 PoW 会消耗资源？ 由于哈希函数的随机性，为了找到合适的解，必须尝试各种随机数来求解，而诚实节点只相信“最长链”。 如果作恶节点想要拒绝一笔交易双花，他需要获得大部分算力来保证其提交的区块结果被接受。

我们可以将 PoW 视为“领导者选举”。 如果您提出正确的解决方案，您有权产生下一个区块并提交交易。 我们的想法是：能否限制解决方案的范围，从而减少资源的浪费？

基于Sleepy Model的PoS共识机制

让我们考虑一个简单的“许可协议”，这意味着我们知道哪些节点参与了协议，每个节点都知道其他节点的公钥，稍后我将展示如何在 PoS 下实现无需许可的共识。 假设所有节点都有一周的同步周期。 在每个时间段，Dan 将哈希值与他的名字和当前时间结果一起计算。 如果小于难度系数，那么 Dan 将被选为出块人，并收集信息 当区块被生产出来时，其他人可以检查 Dan 是否是正确的出块人，并通过公众验证该区块是否由 Dan 签名钥匙。

问题是：这个协议足够安全吗？ 在这种模式下，作恶者有更大的收益：当一个诚实节点被选出时，他将生产一个区块，而当坏人被选出时，他将生产许多块并挖掘未来的区块。 所以我们做了进一步的修正：

1）每个区块的时间戳严格递增；

2）诚实节点将拒绝“未来时间块”。

这样，不诚实的节点就不能随心所欲地出块了。 从某种意义上说，该协议的安全性得到了保证，但实际上通常并非如此，因为不诚实的节点仍然可以使用已经选出的节点及其区块创建分叉。

为了证明我们的“沉睡共识”机制是有效的，我们还需要更多的证据。 由于时间关系，这里就不展开了，具体可以看我们最新的论文。 在论文中，我们介绍了：1）更详细的证明； 2）较弱的假设； 3) 更强的安全模型结果。 我觉得这个研究对银行这样的联盟链很有吸引力。 各家银行成为一个节点，去中心化管理自己的票据，从而实现更快的跨行结算； 至于健壮性，银行可以随时重启机器进行维护，无需与其他银行协调。

关于互联网层面的共识机制比特币采用了pow共识算法，我们意识到有太多比我们理解的更难理解的问题。 我们需要一个新的理论框架来分析和推理这些协议。 同时，我们可能还需要安全的协议设计和实现，这对于加密社区来说也是非常重要的，无论是新的加密协议还是分布式计算。 另一方面，从理论研究到实际影响，这也需要可验证的安全协议和实施方案。 谢谢。

相关论文：共识摘要的困倦模型

分布式计算和相关密码学文献通常考虑两类玩家：诚实玩家和作弊玩家，然后分析弹性属性以假设诚实玩家比例的下限。

根据假设，诚实的玩家不仅被假定遵循规定的协议，而且还被假定在整个协议的执行过程中在线。 在可能存在具有数百万玩家的“大规模”共识协议（例如区块链协议）的现实场景中，这种假设是不现实的。 在这项研究中，我们研究了分布式协议，其中玩家的状态可以是在线（警报）或离线（睡眠），并且他们的在线状态可能在协议期间随时更改。 我们希望解决的主要问题是：

我们能否设计出仅对零星用户参与具有弹性的共识协议？ 也就是说，在任何给定时间点，只有很小一部分用户真正在线参与？

据我们所知，即使我们假设 99% 的在线玩家都是诚实的，当前的共识协议也会在这种零星参与的状态下崩溃。

本研究发现了在上述零星参与情况下形成共识的可能性。 我们提出了一种基于“休眠模式”的共识协议，该协议弹性地假设只有大多数在线玩家是诚实的。 我们的协议依赖于公钥基础设施 (PKI)、公共随机字符串 (CRS)，并且在 Dwork-Naor-Sahai (STOC'98) 的时间模型中被证明是安全的。 在这个模型中，假设所有玩家都具有弱同步时钟（所有时钟都在与实时偏差的Δ范围内），并且网络上发送的所有消息都在Δ时间内传递，并且具有亚指数安全的抗碰撞哈希函数和增强的陷门排列。

一个令人惊讶的发现是，我们的协议明显偏离了分布式共识的标准方法，而我们依赖于中本聪区块链协议背后的关键思想（同时不需要工作量证明）。 最后我们终于观察到，如果大多数在线玩家不诚实，就无法实现“沉睡的共识”。