验证者困境：比特币分叉六周年纪念与区块链的可信计算

作者: Truebit

编译: ChainCatcher

在本系列；已验证中，我们会见了验证者困境论文的合著者 Raghav Kulkarni，该论文是与 Loi Luu、Prateek Saxena 和 Jason Teutsch 共同撰写的，该论文是在作者任职期间撰写的新加坡国立大学。这次采访是为了纪念 2015 年 7 月 4 日发生的比特币分叉六周年，当时该论文正在 CCS 安全会议上接受审查。在此事件中，大约一半的比特币矿工在进行 SPV 挖矿。虽然矿工未能验证区块，但他们确实充分验证了验证者的困境，从而使论文被科学会议接受。该团队的发现使 Truebit 成为人们关注的焦点，作为解决 Nakamoto 共识计算限制的实用解决方案。

我是一名计算机科学家，喜欢探索、理解和解决计算机科学各个领域的问题。我毕业于芝加哥大学，获得博士学位。此后，我在一个名为 LIAFA（巴黎第七大学）的实验室继续我的博士后研究。随后，在我在巴黎共事的教授搬家并邀请我加入他在新加坡国立大学的实验室后，我搬到了新加坡的量子技术中心。在此期间，我有机会学习和发表计算机科学一些新兴领域的研究成果，例如量子计算、机器学习和区块链技术。在我完成博士后工作后，我能够在 LinkedIn 的生产中大规模应用我的一些算法和机器学习技能。从那时起，我就热衷于使用尖端技术构建现实世界的解决方案。

我在芝加哥大学认识了杰森。他是逻辑和递归理论领域最聪明、知识最渊博的人之一。我们就算法、复杂性和组合学等主题进行了几次激动人心的讨论，这些讨论为我们的合作奠定了一些基础。后来，当我在量子技术中心工作时，Jason 正在访问新加坡，在那里他与 Prateek Saxena 一起工作。他向我介绍了令人兴奋的区块链技术领域，我们构想出我正在研究的布尔函数的属性测试可能与他在区块链研究中的可验证计算有一定关联。此后，我们得出了一些有趣的例子，这些例子导致了更多有趣的问题和想法，例如我们在本文第 6 节中看到的最开始的问题和想法。 Jason 带头将这些想法提升到一个新的水平，我们与 Prateek Saxena 和 Loi Luu 一起做出了两个激动人心的发现；首先，区块链容易受到某些类型的攻击，其次，通过正确的激励和结构，区块链有可能被用作强大的可信计算源。有趣的是，2015 年 7 月发生在比特币上的事件为我们的理论提供了支持证据——理性矿工被激励不诚实并忽视区块的有效性。这个理论现在被称为验证者困境。

我喜欢这个过程，因为它的协作性质收集了计算机科学领域不同研究人员的见解。 Jason 除了在他的领域具有很强的严谨和诚实外，还热衷于努力理解来自不同领域的想法并将它们联系在一起。我推测他知道如何享受工作之外的生活，并且最了解如何在需要的时候用笑声打破沉默。

正如我之前提到的，本文的一些想法（不是全部）似乎与非常经典的属性测试设置有一些相似之处，这在集中计算中也非常有意义。然而，验证者困境解决了"类以太坊"区块链的一些独特之处。这些区块链的"智能合约"脚本被称为"图灵完备"，即它们具有更强的表达能力。因此，验证者困境对这些类型的系统进行了具体观察——允许复杂计算的以太坊区块链或允许大型交易集的比特币区块链。人们仍然可以争辩说，以它们的抽象形式，这些想法可以应用于理解其他计算模型的局限性（例如，在经典和分布式设置甚至量子环境中的随机和近似算法背景下的证明者验证者游戏计算模型）并提供解决这些限制的算法。

大致思路如下。由于"类似以太坊"的区块链允许表现力强的"智能合约"，因此在某些情况下，理性矿工会因不验证计算并跳过验证区块而受到激励而变得不诚实。本文确定了两种可能的攻击：1）问题提供者的资源耗尽攻击和 2）证明者的错误交易攻击。这些攻击会影响区块链共识的完整性，我们的重点是强调激励机制如何在允许此类攻击中发挥作用。我的兴趣始于探索区块链上的属性测试和可验证计算之间的可能联系。特别是，了解新兴的基于共识的计算模型的力量和局限性，并提供从属性测试文献中获得灵感的算法。当我开始探索时，我意识到还有更多令人兴奋的分支和应用，例如如何在有限信任下实现鲁棒计算，理解多方博弈中的激励兼容性，区块链上的零知识证明等。

由于以太坊脚本具有很强的表现力，因此它们容易受到称为拒绝服务 (DoS) 攻击的某些类型的攻击，这种攻击会耗尽诚实矿工的资源。此外，在此类攻击中，繁重的交易最终可能导致区块链无法支持额外的交易，从而陷入停顿。引入"gas limit"是希望减轻这种风险。笼统地说，它让区块的创建者为昂贵的验证付出代价。目的是使 DoS 攻击对攻击者来说代价高昂。然而，正如我们在论文中所讨论的那样，这种机制并没有完全解决 DoS 攻击问题。

潜在的攻击者可以免费耗尽其他矿工的资源。主要原因是交易费——gas——仅由区块创建者收取。潜在的攻击者可以自由地将他自己已经知道其有效性的交易添加到他自己的区块中。攻击者不需要花费计算力来验证他自己的交易，但诚实的矿工需要这样做。以太坊奖励比赛的获胜者——最快验证下一个区块的人。攻击者可以利用他未使用的计算资源来获得竞争优势，从而赢得与诚实矿工的竞争。由于 Verifier's Dilemma，理性的矿工不知道是否要验证重块。如果充满未经验证的区块，这可能会影响整个区块链的健康。

在 2015 年比特币事件的背景下，人们发现大约一半的网络在未经验证的情况下在无效区块（相对于 BIP66）之上进行挖掘。由于验证无效块的计算/时间成本，可能会跳过验证。由于先前存在的激励结构，跳过步骤和不诚实行为会在无意中得到回报，而区块链的健康仍处于风险之中。

从广义上讲，我们提出了一种模型，通过限制验证区块内交易所需的工作量来激励理性矿工正确验证。这意味着偏离诚实行为不会带来太多竞争优势。这个新框架以多种方式实现。我们在本文中描述了其中的几个：一个对有限类别的问题有精确的共识，另一个支持对更广泛的问题类别的近似共识。

共识计算机是一个框架。实施它存在挑战，并且有克服这些挑战的技术。与经典计算机相反，共识计算机处理去中心化。这赋予了它一些独特的能力（例如无需信任的计算）和局限性（例如我们 2015 年模型中的明显限制，即只能正确解决易于验证的问题）。仍在发展的区块链技术看起来有可能以某种形式实现共识计算机。例如，Truebit 类似于一台共识计算机，但在白皮书中介绍的一种新颖且可扩展的验证游戏机制的帮助下，它在某种程度上超越并取代了它。

早在 2015 年，我们开始使用的共识计算机似乎要求问题具有\"易于验证\"的解决方案。这需要一些巧妙的数学论证。作为一个简单的例子，考虑计算两个整数 m 和 n 的 GCD 的问题。典型解决方案的复杂性是表示整数所需位数的三次方。然而，可以以验证的复杂性低得多的方式对解决方案进行编码。例如，如果我们要求证明者提供 5 个整数 a、b、x、y、z，使得 (i) ay + bz = 1，(ii) x 同时除 a 和 b，以及 (iii) |y| < b 和 |z| < a 然后使用 Bezout 的身份可以验证 x 确实是 m 和 n 的正确 GCD，仅使用 10 个算术运算，其复杂度仅是位数的二次方。 2015 年的共识计算机利用这些特殊的数学结构来提出可验证的问题。

另一方面，Truebit 将这些概念提升到了一个新的水平，问题提出者不必明确地担心他提出的问题的数学结构。几乎任何代码都可以编译成 Truebit 任务。因此，这种共识计算机的概念已经演变，Truebit 可能已经取而代之。

可验证计算的思想是能够将问题外包，并在验证他们的工作后以公平的方式奖励问题解决者。为了在区块链等去中心化系统上实现这种可验证的计算，一个可能的方向是设计正确的激励结构和计算约束，以确保正确执行。例如，Truebit 是朝着这个方向迈出的有希望的一步，它将论文的思想提升到一个新的水平，并以具体的方式具体化了其中的部分内容。作为区块链技术在现实世界中的应用，这可能会开辟全新的可能性。

Truebit 绝对是领导者。在某种程度上，Truebit 试图通过引入一种可扩展的验证机制——交互式验证游戏——来绕过验证者的困境，该机制基于简单的二进制搜索算法。 Truebit 中的交互式验证游戏有效地解决了 Solver（为计算任务提供了解决方案）和 Challenger（不同意该解决方案）之间的争议。正如 Truebit 白皮书中所解释的那样，这种额外的机制克服了验证者困境造成的瓶颈。通过成功缓解验证者困境，Truebit 为区块链技术创造了一个机会，使其更加可靠和可扩展。