第三届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom，IJTCS-FAW）由北京大学讲席教授邓小铁于2020年牵头发起，第三届于2022年8月15日-19日线上线下交互举行。大会由中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）、中国工业与应用数学学会（CSIAM）联合主办，香港城市大学（CityU）承办，北京大学前沿计算研究中心、北京大学人工智能研究院协办。

 

　　8月17日，大会“区块链中的博弈论”分论坛如期举行，由 Algorand 理论研究主管兼首席科学家陈婧和北京大学讲席教授邓小铁主持。小编为大家带来论坛精彩回顾。

 

How Crypto, Stablecoins, CBDCs and Web3 Will Reshape Competition

Christian Catalini, MIT Cryptoeconomics Lab

 

 

　　在加密货币快速发展的背景下，稳定币、CBDCs（Central Bank Digital Currencies）和 Web3 等概念的提出和逐步实现无疑改变了现有的市场结构。加密货币本身给用户行为带来了更大的自由度，进一步激励用户去尝试新事物和进行作品的创作；在一些现实货币本身就具有的功能上，加密货币提供了相对应的服务，并体现出许多不同的性质。

 

　　讲者指出，相比起现实中更不同质的货币，加密货币市场具有易于相互流通的性质，一定程度上打破了不同市场之间的壁垒，因此在区块链上/链下都带来更多的竞争，进而激发创新创造的不断涌现，并为用户提供更多的选择，这些都需要我们今后付出更多努力去为这些不同平台搭建互通的桥梁。

 

　　关于稳定币的作用，讲者指出目前稳定币虽然已经大大增加了支付的便利性和竞争，但与最初设想的稳定币的功能——作为基准，根据市场供需调节加密货币价格——仍有一定距离。未来我们仍然需要进一步完善、建立真正的稳定币。

 

　　讲者接下来介绍了 DeFi 当前的发展状况，现有的规范机制、智能合约和 ERC20 标准都保证了一定的安全性和互通性，DeFi 应用提供了资金管理、借贷等多种服务，为其使用者提供了极大便利，但我们还需要关注到其中仍存在的一些风险。报告最后部分提到 NFT 和 Web3 也是当下备受关注的议题，它们和以上这些数字经济的新技术新发展都为我们带来了很多新颖的经济形式，在未来持续的发展中必然会挖掘新的市场竞争与活力！

 

Token-Based Platform Finance

Ye Li, University of Washington

 

 

　　数字化的交易平台正在重塑经济，当下区块链的发展进一步推动了数字化交易平台的广泛使用。不论是传统的还是基于区块链的系统，都面临如何维持货币/代币价格和供求稳定性的问题。在讲者所介绍的工作中，他们为数字化平台建立了一个分析代币动态均衡的模型，由此为平台拥有者提供代币发行和回购的标准。

 

　　讲者首先将相关主体划分为三类：平台拥有者、用户和建设者，然后通过三者间代币的流通情况对当前的代币和数字平台进行了数学建模，他提到，代币价值的存在可以用传统经济学上对耐用品的供求分析来解释，尽管代币发行的边际成本几乎为0，发行者通过调节代币流通量使其在均衡条件下保持价值为正，二者的区别在于，代币的需求量比耐用品更不平稳；代币一旦被发行，就有可能面临通胀，在通胀极端严重的情况下，平台拥有者比用户面临更大的危机，他们需要大量的资金来回购代币才能解决该问题，因此对于用户和拥有者来说，平台建设带来的利弊对二者并不相同。

 

　　在报告最后，讲者指出，平台的建立需要平台拥有者对未来发展的预期和保证，因此区块链的出现对于数字化平台的发展起到了关键的作用。

　　

Markets for Crypto Tokens, and Security under Proof of Stake

Ravi Jagadeesan, Stanford

 

 

　　共识机制是加密货币的重要组成部分，在过去，很多代币都采用 PoW（Proof of Work）作为平台的共识机制，而在近年来，PoS（Proof of Stake）因其不需要浪费算力的特性获得了很多关注，伴随着其相对于 PoW 来说拥有的显著优势，PoS 也带来了新的攻击类型和风险——攻击者可能会购买大量的代币来操控区块链。这篇报告为大家介绍了在 PoS 背景下，攻击者成功实现攻击所需要的开销和代币需求的关系，并进一步指出什么样的系统相对于此种攻击而言是安全的。

 

　　讲者首先分析了攻击成本，由于获得一定量的代币的过程需要缓慢进行（否则很容易被系统监测到异常行为），因此可以认为认购过程是连续的，由此可以得到攻击者获取一定代币所需开销。讲者将开销划分为三个组成部分：基础开销、稀释开销和升值开销，分别表示在外界条件固定的固定开销、考虑新发行代币带来的持有代币贬值、代币升值的回购成本增加这三种情况。

 

　　在第二部分，讲者对代币的需求进行建模后，针对自由流通币、稳定币分别进行了具体的攻击成本的分析。最后，讲者总结道：采用 PoS 作为共识机制的系统稳定性和代币的供需紧密相关，对不同币种的攻击在三种开销上的成本分布不同，同时为了提高在代币更多作为流通手段时系统的安全性，需要实现代币更多的储值需求和更高的存储价值。

 

Eliciting Thinking Hierarchy without a Prior

孔雨晴， 北京大学

 

 

　　对于给定的问题，我们通常会认为更多人认同的答案是正确的，但有些时候，真理掌握在少数人手中，那么当这种情况发生时，怎么才能知道哪个答案是正确的呢？在这篇报告中，讲者介绍了他们的工作：在没有任何先验知识的情况下，即使大多数人是错误的，仍然能够选出所有选项中的正确答案的方案。首先，在问题的设计中，讲者采取“回答+预测”的形式，不仅询问被调查者自己对于问题的回答，还增设了他们对他人回答的预测——一个直观的想法是，在有多个 thinking / cognitive hierarchy 的情况下，在更高层次的人会知道他的思维层次以下的人的选择，而反之则不然，思维层次低者并不知道问题实际的答案（更高层次）。

 

　　讲者的工作中，使用了三个矩阵表示相关的量：是实际调查得到的选择每个答案的人数、以及选择这个答案的人预测其他人选择另一个答案的人数；则是调查者不知道的先验知识——每个被调查者选择每个选项的概率分布；表示不同思维层次的人选择回答时所在思维层次的概率。对研究者已知的只有结果以及是一个上三角矩阵，由此进行最优的分解（重排行列），最小化，由此得到重排后的，之后就可以根据行列代表的答案得到“正确答案”。

 

　　在实际的实验中，讲者表示，该方法尽管在缺少层次的问题上，并不能很好的得到答案，但在多数具有思维层次的类似难题上，都很好地选出了正确答案。讲者还提到，希望该方法能够在区块链上得到应用，例如根据人们在链上交互的信息的正确性给出相应的激励等。

 

Insightful Mining Equilibria

张梦倩，上海交通大学

 

 

　　自私挖矿，是区块链上博弈论相关的攻击方式，它表明了比特币的机制不是 IC（incentive-compatible）的。自私挖矿，是指矿工通过隐藏自己已挖到的块，之后再发布造成分叉，从而导致诚实矿工的算力被浪费，进而提高自私挖矿者得到区块奖励的比例。和其他进一步增加自私挖矿收益的研究不同，本篇报告针对如何防止自私挖矿，提出了一种叫 insightful mining 的策略来进行牵制。该策略通过让一个矿工潜入自私挖矿的矿池中，获得对方隐藏块的数量。同时，在由诚实挖矿者发布前一个块时，insightful mining 的策略会与诚实矿工竞争；当前一个块是自私挖矿者发布的时候，insightful miner 会和诚实矿工合作，选择诚实矿工所在的分叉继续挖矿；如果是自己发布的，则隐藏新的块，该研究表明在拥有同等算力的前提下，insightful mining 的矿池能够获得比自私挖矿的矿池更多的收益。

 

　　文章进一步分析了，在所有矿池可以自由选择诚实挖矿或 insightful 的情况下所能达到的均衡：其中当最大的矿池占至少1/3算力时，诚实挖矿是一个纳什均衡；此外，无论算力的分布如何，均衡情况下最多只能有两个采取 insightful mining 的矿池。

 

　　最后，讲者提出，在矿池中安插“间谍”的行为在很多场景下有更多新的用处和影响值得考虑，基于该方法，还有其他策略可以用来牵制自私挖矿，需要未来更多的工作去探索和研究。

　　

Equilibrium Analysis of Block withholding Attack: an Evolutionary Game Perspective

姚章豪 ，苏州科技大学

 

 

　　在区块链中，BWH（block withholding）是在矿池中可能出现的一种攻击方式。它表示，恶意的矿工在找到 FPoW（Full Proof of Work）后选择隐藏，而只提交 PPoW（Partial Proof of Work），始终提交 PPoW 的行为使得矿工并没有实际为矿池贡献算力，却可以分到矿池的收益。在这一报告中，讲者指出有两种 BWH 的方式，一种是在自己的矿池内，另一种则是矿池之间通过在对方的矿池中安插“间谍”，从而降低对方矿产的收益。讲者提出可以采用演化博弈对两个矿池之间是否采取 BWH 攻击的行为进行分析。

 

　　讲者通过求解演化博弈，得到结论：在初始选择 BWH 的概率超过50%的情况下，最终的演化稳定策略中，两个矿池都将采取 BWH 策略；而在初始选择 BWH 的概率低于50%时，二者的演化稳定策略是不采取 BWH。讲者进一步说明，初始概率趋于50%的情况比较复杂，是未来可以进一步展开工作的方向。

 

A Scalable and Reliable Protocol for Decentralized File Storage in Blockchain

陈宏崟，北京大学

 

 

　　在文件存储系统中始终存在的问题是，需要多少的副本才能够避免文件的损失。而在去中心化的文件存储系统的背景下，由于有更多潜在的不可靠的文件存储系统参与，者导致分布式文件系统显得更不可靠。讲者在本篇报告中介绍了 FileInsurer——一个供区块链上的可扩展、可靠的去中心化文件存储系统使用的协议——表明经济上的激励能够解决这一问题。

 

　　首先，为了弥补用户存储文件丢失所造成的损失，该协议需要能够为用户提供充足的补偿金来确保系统的可靠性，这一补偿金来源于存储服务提供者预先进行的存款。文中定义 deposit ratio 为存款总和与文件价值的比例，在 deposit ratio 比较高的时候，会让更少的存储服务提供者愿意提供服务，因此该协议同时应该在覆盖用户损失的同时，需要尽可能降低 deposit ratio。为了达到这一目标，讲者提出，可以让同一份文件在多个文件存储系统中有副本（分配过程应当是随机的），这些提供商可以共同分担潜在的赔偿金进行存款，从而降低 deposit ratio。

 

　　在达到较低的 deposit ratio 的目标后，讲者进一步对 FileInsurer 的安全性进行分析，可能存在的是女巫攻击，在保存了一份副本的情况下，提供商却声称自己存了多份副本；针对这一攻击，可行的方案是，要求其在限定时间内提供文件存储在该分区的证明，由于分区要求被密封，而这一封装过程需要耗费较长时间，因此这一方法（被称为 PoRep：Proof-of-replication）可以防止女巫攻击。讲者提出使用 DRep（Dynamic Replication）的方式，减少封装的次数，能够加快这一过程，如果发现文件损失，系统将自动锁定提供商的deposit支付给对应用户补偿金。

 

　　在具体实现上，讲者提到使用的共识机制是 Proof-of-Spacetime，在实际性能分析中，FileInsurer 具有很好的可扩展性、稳定可靠性、低 deposit ratio，未来的工作将会进一步降低 deposit ratio。

　　

EIP-1559: Chaos and Efficiency in Ethereum's Transaction Fee Market

Stefanos Leonardos, King's College London

 

 

　　EIP-1559 是以太坊在伦敦分叉后作出的重大变革之一，在这之后，以太坊上的出价方式从原来的第一价格拍卖（只提交出价）变为小费+最大支付意愿的形式，同时燃烧一部分“基础费”，基础费的变化将基于特定公式（交易数高于期望水平时，基础费增加，反之降低）来调节需求，同时区块的大小变为原本的两倍（目标大小即原区块大小），这些变化将使得以太坊上的交易费变得更可预测。

 

　　在这篇报告中，讲者对不同的参数进行了模拟，得出以下结论：在用户的出价区间更大时，区块大小更容易稳定在目标大小，基础费也更加稳定；相对的，当用户间的出价非常接近的时候，基础费和区块大小都会经历较大的抖动——更容易出现空块和满块交替出现的情况。讲者还对平均的基础费和区块大小进行分析，发现在 EIP-1559 的机制下，基础费比较稳定，区块大小接近目标大小，较少出现偏高的情况。

 

　　讲者进一步提出在 EIP-1559 的基础上可以进行的改进：选择可变的参数 d（基础费公式中的步长），使用 AIMD（加性增乘性减）的方式使得步长在交易需求多的情况下得到提高，反之减少。在与之前类似的性能分析中，该改进版本得到了类似或者更好的结果。

　　

A Rational Protocol Treatment of 51% Attacks

Vassilis Zikas, Purdue University

 

 

　　51%攻击指区块链中拥有超过50%算力的群体进行的攻击，在拥有50%以上算力的情况下，矿工可以很容易的进行双花攻击。在比特币交易中，我们通常默认大部分矿工是诚实的，但在现实生活中，却很难向公众证明大多数矿工是诚实的。在本篇报告中，讲者利用 RPD（Rational Protocol Design）框架进行比特币分析，在 RPD 对矿工效益分析的基础上增加了进行双花攻击的收益。讲者在其工作中证明了当双花攻击带来的收益是区块数量的多项式大小时，对于矿工而言，诚实挖矿是占优策略。

 

　　然而现实中，有部分区块链仍然遭受到51%攻击，其与理论的主要差别在于，现实中矿工的收益不可能会无限增加，在这种情况下，讲者表明当分叉的收益下界高于诚实挖矿收益的上界时，任何机制都无法保证诚实挖矿是占优策略。讲者进一步使用他们的研究结果对以太坊经典上的数据进行了模拟，得出在不同的算力价格下，经过多长时间的块可以认为是安全的（即对于51%攻击者而言在该块之前进行分叉不产生增益）。

 

　　在报告的最后，讲者指出，更复杂更接近实际的效用函数的分析、对更多其他区块链的分析都是未来值得进一步研究的方向。