五分钟速览波卡关键机制新论述：NPoS、时间共识与 GRANDPA

Web3 基金会网站更新波卡研究进展，涵盖提名权益证明（NPoS）、时间共识和 GRANDPA。

原文标题：《波卡（Polkadot）研究进展》
撰文：PolkaWorld

最近有几篇文章添加到了 Web3 基金会研究网页中，涵盖了 Polkadot 去中心化区块链平台的各个子目录：提名权益证明（NPoS）、时间共识和 GRANDPA （为中继链实现的区块最终性工具）。在这里，我们对每一篇文章都做了简要介绍，并提供了相关的链接。

提名权益证明中的验证人选举

Polkadot 实现了提名权益证明（NPoS），这是对权益证明（PoS）的一种改编，在这种情况下，全部的代币持有者可以作为提名人参与网络，支持一个大型但数量有限验证人节点池（在创世中预计为数百个）。这个方案允许大量的质押（ stake ）来支持验证人，远远高于任何单个用户的持有量，从而使网络更加安全。

提名人与他们支持的验证人分享经济奖励以及可能的 slash 惩罚，在经济上给予系统安全性，因此在经济上激励他们监督验证人的性能。

因此，NPoS 不仅比工作量证明更有效率，而且比没有 stake 委托的 PoS 机制更安全和去中心化，因为 PoS 只有少数「巨鲸」（拥有大量代币的人）可以成为验证人。

根据提名人的偏好，系统在每个 era （大致相当于一天）都会选择一组新的验证人，根据选举规则，该规则会选择 stake 比例尽可能高且分布尽可能均匀的一组验证人。

这个范例同时实现了高度的安全性和可扩展性，以及前所未有的去中心化，通过提供一个正式的数学保证，验证人委员会实现了比例代表（proportional representation）。

非正式地说，这意味着所有提名人中的每一个少数派（即提名别人没有提名的验证人）都可以按照他们所持的 stake 比例选举出一些验证人，而不存在少数派代表不足的问题。

我们强调，无论是出于安全、政治、地理或经济方面的原因，网络用户自然会产生不同的偏好和派系。在一个去中心化的社区中，这种观点的多样性是值得期待和欢迎的，我们的目标是确保所有少数群体都有代表并参与决策进程。

摘要：Polkadot 是一个将于 2020 年推出的去中心化区块链平台。它将实现提名权益证明（NPoS），这是一种基于权益证明的机制，其中 k 个节点被网络选择为验证人，根据担任提名人角色的代币持有者表达的偏好来参与共识协议。这种设置实现了一个基于批准的多赢选举问题，即每个提名人提交一份可信候选人名单，并且拥有与其 stake 成比例的投票权力。一个解决方案包括一个由 k 个验证人组成的委员会，以及在他们之中每个提名人投票的比例分布。我们考虑两个目标，都是最近在社会选择文献中研究学习到的。第一个问题是保证比例公平表示的性质。第二个目标，称为 maximin 支持，是最大化分配给任何选举的验证人的最小投票支持量。我们认为，前者的目标符合去中心化的概念，而后者符合共识协议的安全级别。

我们证明了 maximin 支持问题是常数因子近似的，并给出了几个近似算法，证明了一个匹配的硬度结果。此外，我们还提出了一种有效的后计算方法，当它与支持最大值的近似算法配对时，返回一个新的解，即 a）保留近似保证，b）满足 PJR 属性，c）可以由不可信的第三方有效地验证满足公平比例代表（ PJR：proportional justified representation ）。除了具有独立的理论意义外，我们的结果使网络能够运行一个有效的验证人选择协议，同时实现 PJR 属性和最大值支持的常数因子近似，从而为去中心化和安全性提供了强有力的理论保证。

要阅读更多关于 NPoS 和我们使用的验证人选举规则的信息，请阅读完整论文或 Medium 文章 《NPoS 如何在 Polkadot 中运行》 。

完整论文

时钟共识的网络时间

在日常生活中，我们通常不考虑测量时间的机制。现在，它通常是通过时钟中晶体振荡器的振动次数来测量的。当这些振动的频率因温度、压力和湿度等因素而变化时，一天内可能会出现几秒钟的误差。

与晶体振荡器不同，连接到互联网的计算机时钟通常使用额外的机制，如网络时间协议（NTP）或全球定位系统（GPS）来提高精度。然而，在过去，NTP 服务器被破坏或 GPS 信号被愚弄的事件时有发生。如果这种攻击发生在权益证明的区块链中，诚实的全节点将停止生成块，因为它们不知道该到它们了，而恶意的全节点将继续生成块并控制区块链。

为了防止这种可能性，Polkadot 使用相对时间协议（relative time protocol），这是一种在区块链协议之上工作的通用同步协议。这在中继链中尤为重要，因为每个验证人都有自己的时钟（不通过任何协议，如 NTP 或 GPS，进行校正）。验证人使用相对时间协议来解释最终块的到达时间，以确定在去中心化网络中当前要对齐的正确时钟。因此，可以更精确地定义验证人之间的时间同步。

摘要：需要同步通信的去中心化协议通常是借助计算机时钟显示的时间来实现的。这些时钟大多由诸如网络时间协议（NTP）的中心化系统进行调整，因为这些调整对于减少随机误差对时钟的影响是必不可少的。另一方面，对这些系统的攻击（过去曾发生过）会导致依赖于它们提供的时间数据来保持同步性的协议损坏。因此，我们面临着这样的两难境地：要么依赖一个中心化的解决方案来调整我们的计时器，要么冒着去中心化协议的安全风险。本文通过对时钟共识（consensus on clocks）概念的建模，提出了去中心化系统中物理时钟同步问题的全局通用可组合（GUC）模型。时钟共识应考虑到协议各方的本地时钟可能会存在的误差。通过这种方式，我们对 NTP 以去中心化的方式提供的功能进行建模。最后，我们给出了一个简单但有用的协议，该协议依赖于实现我们模型的区块链网络。我们的协议可以被现实世界中需要同步时钟的区块链全节点使用，以保持区块链协议的正确性和安全性。我们的协议的一个优点是它不会在底层区块链协议上造成任何额外的通信成本。

要阅读更多内容， 请参阅此处的全文 。

拜占庭区块最终工具

Polkadot 有一个混合共识协议，将 区块最终工具（GRANDPA）与区块生产机制（BABE） 分开。

这是一种实现概率最终性（在一定时间后，块将以接近 1 的概率最终确定）和可证明的、确定性最终性（意味着最终确定的块永远保持最终状态）的方法。

混合机制避免了在不知情的情况下跟随错误分叉（概率终结性的危险）的情况，并允许快速生成块，因为较慢的最终性机制单独完成块，而不会导致较慢的交易处理或暂停。

本文提出了 GRANDPA 协议。（GHOST-based Recursive ANcestor Deriving Prefix Agreement)）

GRANDPA 达成的是链协议而不是区块协议：它试图最终确定 2/3 的选民同意的链前缀，无论是一个还是数千个区块。这里有 完整的文档 。或者查看 Medium 文章 《 波卡共识第二部分：GRANDPA 》

来源链接： mp.weixin.qq.com