[有故事的NPC]Paradigm：构建“无领导拍卖”协议来解决去中心化加密货币拍卖偏差

无领导拍卖查看视频演示无领导拍卖是去中心化的拍卖,没有拍卖师。它们解决了当一个参与者被允许在所有其他参与者之后采取行动时可能出现的“最后看”问题。在无领导的拍卖中,所有参与者必须同时承诺他们的出价。任何违反这一承诺的行为都将导致可归因的过错。出价是阈值加密的,以避免信息泄露。拍卖可以通过将结果提交给区块链来完成,在区块链中,它们可以通过签名聚合进行有效验证。出于本文的目的,我们将使用以太坊。该协议与拜占庭容错共识协议类似,假设一个预先确定的参与者集,其中超过三分之二的参与者是诚实的。它还要求参与者能够在一段固定的时间内(比如,两秒钟)可靠地相互传递消息。如果违反了后一种假设,例如网络分区,一些诚实的各方可能会收到错误但是,假设此类违规行为很少见,我们可以设计故障惩罚,以便将此问题的影响降至最低。这个设计没有解决几个问题。特别是,参与者仍然可以比其他人晚提交投标,因为他们的延迟较低。此外,在这个版本的协议中,为了简单起见,来自公众的出价是未加密的。这意味着不诚实的拍卖参与者与信任他们的公众有最后的联系。动机拍卖在加密货币中无处不在。计时游戏、最后检查和短期审查开始出现,而这个协议至少是为了抵制其中的一些。我们正在探索如何将其整合到Angstrom的顶部区块和批量拍卖中,该拍卖通过以共同价格执行订单,使用单独的共识机制来保护MEV。此拍卖的变体可能适用于其他设置,例如:•如Mike Neuder和Justin Drake所提议的那样,将PBS拍卖纳入像以太坊这样的L1•强制执行 UniswapX 或 MEV-share 等订单流拍卖的公平性•强化链上批量拍卖,就像dYdX讨论的那样•去中心化排序器到像 Optimism 这样的 L2 中之前的工作最近在加密拍卖方面有很多出色的工作。例如,请参阅:• 链上拍卖中的审查阻力(2023),作者:Elijah Fox, Mallesh M. Pai和Max Resnick• 通过区块链进行可信、最优的拍卖(2023),作者:Tarun Chitra, Matheus V. X. Ferreira和Kshitij Kulkarni• 缓解 MEV 的新架构 (2023) 作者:dYdX• 多重性 (2023)作者:二元性• 蝉 (2024) 作者:Noemi Glaeser、István András Seres、Loránd Eötvös、Michael Zhu 和 Joseph Bonneau虽然这方面的大部分工作都解决了审查问题——领导者排除他人交易或出价的能力——但我们还没有发现任何工作直接解决了最后一次审查的问题——提议者比其他参与者晚很长一段时间插入或取消自己出价的能力。问题背景Zed想每12秒拍卖一个ETH。他成立了一个由他的朋友Alice, Bob, Charlie, 和Dan组成的委员会来管理拍卖。这些参与者将从公众中收集出价,然后,他们将一起决定他们所见过的最高出价。Zed相信整个团队,但他认为他们中最多有一个人可能不诚实。第一次尝试一种可能性是在像Tendermint这样的去中心化共识协议中使用单区块拍卖。每个参与者将从公众中收集出价,并提交最高的出价以纳入该区块。然而,Tendermint的特点是一个对区块内容有完全控制权的区块提议者。这意味着一个不诚实的投标者可以简单地审查其他人的出价,并以0的出价赢得拍卖。为了解决这个问题,我们可以将每次拍卖的持续时间从一个区块改为两个区块。然后,两个不同的提议者会一个接一个地提出一个包含他们见过的最高出价的区块。拍卖的最终赢家将是这两个街区中出价最高者。因为最多有一个提议者是不诚实的,所以这些区块中至少有一个包含诚实的出价。这是一个很大的进步!“最后查看”问题然而,想象一下,假设不诚实的提议者,比如Bob,是第二个区块的提议者。第一个提议者Alice在她的第一个区块中提交了1万美元的以太币出价。鲍勃现在有几秒钟的时间来决定他想做什么。他查看了以太币的价格,发现它刚刚飙升至1.1万美元。他自己出价10,001美元,并赢得了拍卖,净赚999美元。作为一个不诚实的参与者,只要有利可图,Bob就会这样做——也就是说,只要以太币的价格大于Alice区块中当前的中标价。这意味着任何向Alice发送出价的人,只有在以太币的当前价格小于或等于他们的出价时才会得到成交——换句话说,如果交易对他们来说是无利可图的。即使Bob无法看到其他竞标者的出价,由于他能够比其他人晚几秒钟提交自己的出价,他仍然具有信息优势。如果他们是理性的,并且知道发生了什么,当Bob是第二个提议者时,除了Bob以外的其他竞标者将停止竞标。在边际上,这将压低整体出价,导致Zed的资金减少。这就是所谓的“最后查看”问题,它是MEV的一种形式。因为它与目前其他可容忍的MEV形式非常相似,甚至像Alice, Charlie和Dan这样的“诚实”参与者也可能受到足够的诱惑而参与其中,这使得Zed和任何诚实的投标人都处于不利地位。我们想阻止这种事发生。解决方案问题总结该协议专门用于解决去中心化拍卖中的“最后查看”问题——即一个参与者可以比其他人有意义地晚点出价或取消他们的出价,而不需要他们自己付出任何代价,从而给他们带来不公平的优势。特别是,我们希望确保所有出价都是在给定的挂钟时间(例如,12:00 PM)提交的,而不管谁提交的。大多数区块链共识协议都有一个领导者或提议者提出一个区块,供其他参与者同意。因为所有其他参与者必须及时将他们的报价发送给领导者,以便领导者将他们包括在内,因此领导者有更长的时间来决定他们自己的报价,给他们最后一次免费的机会。协议概述无领导拍卖分三轮得出拍卖结果,并在第四轮中创建一个易于验证的聚合签名来验证它们。任何人都可以将这些签名结果提交给以太坊以完成拍卖。该协议还指定了一组易于证明的故障条件。任何人都可以在任何时候提交错误证明,并对负责的参与者进行处罚。性能正如我们将在下面证明的那样,该协议通过满足以下两个属性来解决最后一次查看问题:1.没有迟到者:没有参与者可以在第一轮结束的挂钟时间之后进行出价。2.没有免费选项:任何保留在第一轮后取消选项的参与者都必须提前支付该选项的费用。有效的惩罚措施应该会使这种做法在经济上不可行。值得注意的是,一些参与者可能比其他人有更低的延迟,因此在第一轮中能够比其他人晚采取行动。假设我们假设在3f+1个参与者中,2f+1是“诚实的”(与拜占庭容错共识协议要求的阈值相同)。我们的同步假设是,所有诚实的参与者都能够相互发送消息,这些消息保证在某个固定的时间内到达,比如 1 秒。这个假设不需要为了整体安全或活跃性而成立(确保我们不会产生相互冲突的拍卖结果,并且拍卖最终会发生),因为我们依赖以太坊来获得这些属性。我们将在下面讨论当违反此假设时会发生什么。我们还假设参与者有同步的时钟,就像在以太坊中一样。拍卖第一轮-发送出价每个参与者发送一个签名出价给其他参与者。这些出价是阈值加密的,这意味着它们是使用公钥加密的,该公钥可以由任何 f+1 或更多参与者的集合解密(这将在第 3 轮中发生)。这意味着没有参与者能够在提交自己的出价之前看到任何其他参与者的出价值,因此无法利用该出价的知识。有几种方法可以实现这种加密,但细节超出了本文的范围-参见例子vetKeys。诚实的参与者必须提交他们从公众那里收到的最高出价。然而,由于来自公众的出价在这种设计中没有被加密,一个不诚实的参与者可以选择出价比他们从公众那里收到的出价高出一小部分。公众可以通过将他们的出价只发送给一个他们信任的参与者来解决这个问题。加密解决方案是可行的,但会增加复杂性。第2轮-发送出价集每个参与者都将他们在第一轮收到的所有加密出价的签名集(一个“出价集”),包括他们自己的,传给所有其他参与者。所有参与者现在都有一个“出价视图”,或者从其他参与者那里收到的一组出价集。诚实的参与者只有在第一轮出价结束之前到达时,才会将另一个参与者的出价包含在他们的出价集中,由参与者的同步时钟决定。因此,如果一个出价包含在诚实参与者的出价集中,则它必须在第一轮结束时发送。由于最多有 f 个不诚实的参与者,如果一个出价出现在 f+1 个或多个出价集中,其中至少有一个来自诚实的参与者,并且该出价必须在第一轮结束时发出。任何诚实的参与者都可以使用这些信息来解决拍卖问题。但是,该协议无法知道哪些参与者是诚实的。所以,我们需要再来一轮。第3轮-发送出价视图和阈值解密信息每个参与者都将他们在第二轮中收到的所有出价集(他们的“出价视图”),包括他们自己的出价集,告诉所有其他参与者。除了它们的出价视图外,它们还发送了它们在上面讨论的阈值加密方案中使用的解密信息。其中f+1的任何集合都足以解密所有加密的出价。就带宽而言,这是最昂贵的步骤:每个参与者必须向O(n)个参与者发送O(n)个出价集,其中包含O(n)个出价,在最坏的情况下,总带宽为O(n^3)。然而,每个人都应该从其他参与者那里获得相同的实际出价(在没有代价高昂的模棱两可错误的情况下,下面将讨论),并且给定集合中的存在或不存在或出价只是单个位。此外,如果每个人都是诚实的,并且网络正常运行,那么所有参与者都应该在他们的出价集中拥有每个出价,并且每个参与者都应该拥有其他参与者的出价集。因此,如果参与者只发送消息表明他们丢失了哪些出价或出价集,那么在理想情况下,他们只需发送一个 (“一切都在这里”)或几个bit (“集合3丢失了出价13,其他一切都好”)。此时,每个参与者都应该从诚实的参与者那里获得 2f+1 的出价视图,并能够对其进行解密。如果有f+1个这样的人,他们就可以证明他们至少有一个诚实参与者的出价视图,足以解决竞价问题。理论上,该协议可以在此结束,任何参与者都可以向区块链提交f+1出价视图以进行最终确定。然而,由于空间复杂性和验证成本,将2f+1出价视图提交给以太坊并进行验证是不切实际的(也许在自定义链上更可行)。因此,我们需要再进行一轮,以便参与者能够以一种易于在链上验证的方式验证拍卖结果。第4轮-验证出价视图为了保证我们想要的性能,我们想要轻松地验证拍卖的中标价是至少一个有效出价视图的中标价,并且它大于或等于至少一个诚实参与者视图的中标价。第4轮的设计就是为了实现这一点。每个参与者都会检查其所有解密的出价视图。如果出价至少存在于构成出价的出价集中的 f+1 个出价集中,则该出价_valid _in在出价视图中是有效的。视图的中标是该视图中的最高有效出价。如果给定出价视图中的出价大于或等于该参与者自己的出价视图中的出价,则该参与者提名该出价。每个参与者为他们提名的每个出价构建一个阈值签名,并将所有这些出价和签名的集合传递给其他参与者。注意,这在空间复杂度(每个视图最多一个签名)和带宽复杂度上仅为O(n^2)。事实上,如果所有参与者都是诚实的,并且没有网络困难,相同的出价将赢得每个出价视图,因此每个参与者将只提名单个出价。结算任何至少有f+1个参与者以这种方式签名的出价都被确认。请注意,在某些情况下,可能会确认两个或更多不同的出价(尽管这意味着至少有一个参与者在第一轮中失败,因此没有获得免费选项)。任何确认的出价都可以提交到以太坊区块链,在那里可以通过简单的签名验证进行验证。提交者可能会从协议中收到一笔小额付款,以偿还他们的gas费用。在以太坊上只接受一个已确认的出价,如果存在多个已确认的出价,则允许所有参与者就中标达成共识。以太坊区块提议者可能会审查拍卖,而不将其包含在区块中。这甚至可能连续发生几个区块。在这种情况下,提交当前区块拍卖结果的参与者也必须提交所有缺失区块的拍卖结果。我们将在下面讨论这如何改变错误惩罚。错误基本只要有证据,任何人都可以异步提交错误证明,这很可能导致违规参与者的质押全部或部分被削减。报告错误证明的参与者可能会收到一部分被削减的质押,作为报告的奖励。当参与者在不同的出价集中出现冲突的出价或在不同的出价视图中出现不同的出价集时,就会出现歧义错误。因为这种含糊其辞要么是故意的,要么至少是由于客户端问题而不是网络问题造成的,因此对它的惩罚可能相当严厉,包括全面削减。当参与者的出价在某些 f+1 出价集集合中不存在时,就会发生缺席错误。这可能意味着参与者不诚实,试图退出他们在第一轮发出的出价,或者,希望很少,参与者是诚实的,并且网络被分区了。缺席错误的处罚应设置为高于能够取消出价的选择权。这需要与真正的网络故障频率相平衡,并且最终是一个定量问题。在最坏的情况下,有一个不断升级的惩罚系统可以限制重复犯罪的频率,并将这种行为保持在最低限度。使用此协议的任何系统都可以监控这些类型的故障相对于已验证的网络故障发生的频率,并相应地调整惩罚。审查拍卖的缺陷正如我们将在下面进一步讨论的那样,拍卖参与者可以通过在第一轮中犯错误来保留在下一轮中取消出价的选择权。任何这样做的参与者都可以通过贿赂以太坊区块提议者来审查以太坊区块拍卖的拍卖结果,从而为自己创造更多的可选性,可能会连续几次,然后最终提交如上所述的“结算”。为了保持“无自由选择权”的性质,我们在每次审查给定拍卖时线性增加错误惩罚,以便原始错误者必须为每个错过的区块的期权值付费。如果一个诚实的参与者由于网络问题而无意中犯了错误,有人可以使用这些不断增加的惩罚来破坏他们,但破坏者必须支付审查区块的费用。减轻意外故障如果任何参与者的出价集中缺少f+1个或更多的出价,我们通过假设知道他们至少缺少一个诚实参与者的出价,因为最多f个参与者是不诚实的。因此,为了计算缺席错误,我们可以忽略这个参与者的出价集,因为他们要么是不诚实的,要么是发生了网络分区。这应该可以减少主要网络分区产生的故障数量。证明i. 没有迟到者:任何参与者都必须在第 1 轮中将他们的出价发送给至少一名诚实的参与者,以便它在任何出价视图中都有效,从而有机会获胜假设在第一轮中,一些参与者没有将他们的出价发送给任何诚实的参与者。因为有2f+1个诚实的参与者,这个出价在第二轮中最多出现在(3f+1)-(2f+1)=f个出价集合中,这不足以使它在任何出价视图中都有效。如果在任何出价视图中无效,它就不能成为任何出价视图中的中标,并且没有诚实的参与者会提名它。由于f+1个参与者必须为它提名一个出价才能赢得拍卖,这些参与者中至少有一个必须是诚实的,并且这个出价无法获胜。ii. 在没有网络分区的情况下,在第一轮中向所有参与者发送出价的参与者不会产生错误假设诚实的参与者是Alice。她将她的出价发送给第一轮的所有3f+1参与者。因为其中2f+1人是诚实的,每个诚实的参与者都会把自己的出价发给其他诚实的参与者。这意味着每个诚实的参与者都会在他们收到的出价集(包括他们自己的出价集)中看到她的出价。由于最多有3f+1个出价集,她的出价将在最多(3f+1)-(2f+1)=f个出价集中缺席,因此不会产生错误。iii. 在没有网络分区的情况下,如果参与者在第 1 轮中向 f+1 或更多诚实的参与者发送出价,则该参与者将赢得拍卖,前提是这是在第 1 轮中提交给任何诚实参与者的最高出价假设Alice在第1轮中向f+1个诚实的参与者发送了她的出价。然后,这些诚实的参与者将把她的出价包含在他们的出价集中,并将其发送给其他参与者。这意味着2f+1个诚实的参与者中的每一个都在f+1个出价集合中看到了Alice的出价,因此认为她的出价在他们的出价视图中是有效的。根据假设,Alice的出价是第1轮中所有诚实参与者的最高出价。所以她的出价在每个诚实的参与者眼中都是赢家,每个诚实的参与者都会提名她。此外,根据上述证明(i),没有更高的出价在任何出价视图中都是有效的,因此没有诚实的参与者会提名它。这意味着Alice的出价是唯一获得至少f+1项提名的出价,并且必须赢得拍卖。请注意,如果两个这样的投标人与最高出价并列,则存在边缘情况。我们可以根据阈值解密的随机性来判定。iv. 任何参与者必须在第1轮中向至少f+1名诚实的参与者发送他们的出价,以避免产生错误假设参与者将其出价发送给第1轮诚实参与者中的k<=f(可能包括他们自己)。然后,这个出价将出现在诚实的参与者发送的k个出价集中。每个诚实的参与者将从其他诚实的参与者(包括他们自己)那里获得2f+1个出价集,其中只有k个包含有问题的出价,因此2f+1-k>=2f+1-f=f+1个出价集将不包含有问题的出价,这足以产生故障。请注意,即使网络被分割,如果诚实的参与者确保所有其他参与者都收到了他们的出价集,并重新发送出价集,直到收到确认,一旦网络恢复,就会产生故障。v. 没有免费选项通过(iii),任何在第1轮中向f+1或更多诚实参与者发出出价的参与者将赢得拍卖,如果它是第1轮中向任何诚实参与者发出的最高出价,无论他们后来做了什么。在第(iv)条中,任何在第1轮中向少于f+1个参与者发送出价的参与者将被判错误(因此将被处罚)。因此,任何希望保留取消选择权的人都必须为此付费。结论去中心化拍卖直到最近才开始得到广泛应用,带来了许多新问题。本文针对的是一个我们在其他地方没有看到解决的问题。我们希望并期待会出现更多更好的解决方案——理想情况下是那些更简单,更少的回合,或者对同步或诚实参与者数量等问题的假设更少的解决方案。尽管这种设计并不能解决所有问题,但它确实解决了去中心化拍卖中固有的一些常见的“最后查看”问题。我们希望它本身可以有一些用处,帮助其他人解决类似的问题,甚至可以改进或重新混合成更好的东西。