解读图灵奖得主姚期智最新论文，如何用理论计算机科学来优化比特币费率市场？
浪花财经《比特币费率设计的激励分析》（An Incentive Analysis of some Bitcoin Fee Designs），以比特币交易费机制为主题，从数学的角度为近期学界提出的创新机制，提供了支持与佐证。
挪威科技大学信息与通信技术与自然科学系副教授王皓亦对本文提供了专业意见
前段时间，一笔在比特币网络上的交易，在区块链行业引发了大量关注。一名用户仅花费 0.1 美元，就完成了一笔价值 1.94 亿美元的比特币转帐交易。这在传统金融行业的标准来看，简直是天方夜谭。
这笔交易在 10 月 15 日被添加到区块 545911 中，价值高达约 1.94 亿美元（当时币价约 6466 美元）的 3 万枚比特币，分别被转到两个地址，而手续费仅 0.00001464 BTC，约 0.1 美元。相较之下，一般传统银行假设是跨境汇款，需要按汇款金额约 0.10% 收取手续费，还不计其它电报费与中转行手续费。
比特币转帐的低成本固然诱人，但却反映出了整个费率市场其实并不健全，缺乏诱因吸引矿工加入，投入设备、电力等资源来协助维持整个比特币系统的运作。在当前币价低迷，区块奖励跌破挖矿成本，导致矿工大量退出之际，更凸显出建立交易手续费机制，对维系整个比特币生态健全有多重要。
著名计算机学家、图灵奖唯一华人得主姚期智也注意到了这个问题。他的最新发表论文《比特币费率设计的激励分析》（An Incentive Analysis of some Bitcoin Fee Designs），就以比特币交易费机制为主题，从数学的角度为近期学界提出的创新机制，提供了支持与佐证。
他更指出，这是一个令人兴奋的研究领域，有着许多吸引人的问题等待解决，对于理论科学家与系统设计者都是如此。
(来源：arXiv)
姚期智的研究方向包括计算理论及其在密码学和量子计算中的应用。他是研究量子计算与通讯的国际前驱，于 1993 年最先提出量子通信复杂性，基本上完成了量子计算机的理论基础。1995 年提出分布式量子计算模式，后来成为分布式量子算法和量子通讯协议安全性的基础。
尤其是在现代密码学领域，他的研究在基于复杂性的密码学和安全形式化方法方面有根本性贡献。
正如日前他曾在公开演讲中指出的，计算机科学正在迎来一个前所未有的黄金时代，正在打破边界，带来新的变革。姚期智也将自己的研究触角延伸到了加密货币与区块链的领域。
根据姚期智个人页面来看，《比特币费率设计的激励分析》这篇论文，应是他首度以个人独立挂名的加密货币或区块链主题论文。过去他所发表的这类主题论文，多半是与团队或研究伙伴合作，如 2018 年 5 月曾与团队共同发表《将中本聪共识扩容至每秒数千计次交易》（Scaling Nakamoto Consensus to Thousands of Transactions per Second）一文，提出快速、高性能且去中心化的区块链系统 Conflux。
而姚期智在这篇论文中，主要是为 Ron Lavi、Or Sattath、Aviv Zohar 等 3 位以色列学者，在 2017 年所提出的“垄断价格机制”（Monopolistic Price Mechanism）和“随机取样最优价格机制”（Random Sampling Optimal Price Mechanism, RSOP），提供了更多数学上的佐证和支持。
比特币系统的现况与问题
在比特币的世界里，矿工如何通过挖矿得到奖励，驱动起整个分布式帐本的交易验证执行，是这个去中心化体系赖以运转的最根本基础。
而当今比特币系统中的两个主要问题就是：
（i）随着区块奖励逐渐减少，矿工要如何获得足够的收入；
（ii）区块容量上限而导致的吞吐量限制。
更具体的说，目前矿工挖矿的主要动机仍是取得区块奖励，也就是比特币。
这真正暴露出的问题是，截至目前为止，比特币仍然远未实现其成为世界货币的使命，在这一公开帐本上，真正的经济交易活动少之又少，无法产生足够的手续费来奖励矿工。所有矿工挖矿的目的都只是为了获取区块奖励，因此当币价下跌，整个系统就随之崩溃。
但区块奖励机制是每 4 年会减少一半。因此，长远来说，交易费机制才是矿工收入的主要来源，并是整个比特币世界是否稳定安全的决定性因素。
(来源：arXiv)
重构比特币的费率市场：MP 和 RSOP 制
也就是说，比特币的未来要走下去，一定要发展出手续费取代挖矿奖励的稳定机制。
为此，Ron Lavi 等人在 2017 年《重构比特币的费率市场》（Redesigning Bitcoin’s fee market）一文中，提出了两项创新的比特币费率机制设计构想，希望能够改善矿工的收益。
(来源：arXiv)
首先，我们需要了解的是，在比特币交易市场中有两种参与者：
（1）需要在比特币系统中进行认证和注册交易记录的用户；
（2）创建新区块以打包交易并进行认证的矿工。
每个用户会提出其交易愿意所支付的最大金额，而矿工则使用一种机制来决定要打包哪些交易并向每个用户收取多少费用。
比特币系统的安全性来自于大批诚实矿工所提供的算力。Ron Lavi 等人认为，现有的比特币费率机制是采用“竞价”（pay your bid）拍卖制，以此现有的交易手续费市场来看，除非区块堵塞，否则矿工并不能得到很好的收益。
而这一点与区块链扩展性（scalability）的议题也有关联，因为如果区块容量变大，可能导致交易费收入进一步下降，这限制了区块链系统设计者在区块容量上可以调整的空间。
因此，Ron Lavi 等人提出了两个替代性的拍卖制：“垄断价格机制”（Monopolistic Price Mechanism）和“随机取样最优价格机制”（Random Sampling Optimal Price Mechanism, RSOP）。
垄断价格机制（Monopolistic Price Mechanism）根据以下规则运作：
每项交易明确定出愿意支付的最高手续费金额
矿工可以选择在其区块中打包进哪些交易
区块中的所有交易都支付相同费率，此费率按区块内的最低出价金额而定
矿工理应选择可以将其收益极大化的交易，也就是交易数量与最低出价金额相乘后的最大数字。
以垄断价格机制来说，矿工选择区块中被接受交易的数量。而在这些被纳入区块中的交易中，哪一笔交易所提出的手续费金额最低，那么所有交易都一律支付这一金额。这个机制让区块的容量可以动态调整。
垄断价格（MP）机制是一种自然而实用的机制，尽管并非严格意义上的激励相容。他们的广泛模拟结果显示，这个机制在多数独立同分布的情况下，都不会太过偏离激励相容。也对某种有限大小下离散分布的特殊情况进行了分析。
Ron Lavi 等人认为，MP 制可能是“竞价”（pay your bid）拍卖制以外的一个很好选择，因为后者有着出价低与收益低的问题。他们也推测，MP 制在一般独立同分布的情况下，应该是接近激励相容的。
“随机取样最优价格机制”（Random Sampling Optimal Price Mechanism, RSOP）根据以下规则运作：
将每个区块中的交易随机分派为两组
运算出每一组的垄断价格
将每一组算出的价格用于相对的另一组（亦即，只有在对应组中出价高于垄断价格的交易才会被接受，并一律支付相同价格）
这一做法的诉求仍然是要取得某个接近垄断价格的金额，但主要区别在于这（通过设计）消除了单一交易对手续费支付价格的影响，因为使用者需支付多少手续费都是由对应组来决定的。尽管这仍然无法完全避免任何价格操纵的可能性，但推测情况应该并不严重。
Ron Lavi 等人的贡献是，他们在这篇论文中提出了一个概念架构，用拍卖理论去决定哪个交易可以被打包进各个区块。其主要贡献是提案与分析这两种以拍卖为基础的手续费市场机制。这两种机制从根本上将手续费与区块容量的问题脱钩开来，让我们可以更自由地根据其它安全性考量来决定区块大小。
这两种机制同时有以下三个好处：
（1）从系统用户手中收取到高收益（这也意味着这一协定拥有高安全性）；
（2）激励矿工扮演卖家的角色，遵循协定；
（3）简化交易发行。
同时，两种机制都鼓励参与者直接地表达出他们真实意愿——在这个情况下来说，就是直接表明他们愿意为交易支付多少手续费。今日的比特币钱包，其费率估算机制必须衡量当下的堵塞程度来采用不同的交易手续费。而若是根据 Ron Lavi 等人提出的机制，则钱包程式可以不受外在情况或其他人行为因素的影响独立运作。
运用理论计算机科学证明 MP 制接近激励相容
不过，Ron Lavi 等人所提出的只是一个概念架构，尽管 3 人在研究中进行了模拟和分析，仍不足以展现出其所提出的创新机制是确实可用的。
事实上，他们 3 人继 2017 年 9 月发表这篇论文、11 月并在美国斯坦福大学举行的 Scaling Bitcoin 第四届研讨会上发表研究成果后，似乎仍未引起太多关注。学术界并没有太多后续讨论该如何进一步完善并应用这两种创新机制。根据 arXiv.org1 线上预印本资料库网站显示，至今仅有 2 笔引用纪录。
然而，在《部分比特币费率设计的激励分析》一文中，姚期智却特地对上述两个机制进行研究，并通过理论计算机科学的分析，为期提供了数学上的支持与佐证。
(来源：arXiv)
姚期智首先指出，尽管 MP 不是严格的激励相容，但 Ron Lavi 等人研究了这个机制在独立同分布（Independent and identically distributed, IID）的情况下能够多接近激励相容。而他们基于广泛模拟和一些分析工作，猜测这一机制是接近激励相容的。
激励相容（incentive compatible, IC）在比特币费率机制中是一个很重要的概念。在机制设计理论中，激励相容系指若所有的参与者都能依机制诚实揭示任何被要求的私有资讯时，那么就会得到最好的成果。
因此，如何设计出一个比特币的费率机制，让矿工可以从系统使用者身上更好地获得收益，且是接近激励相容的，而用户也可以诚实地将每笔交易手续费价格设定在自己愿意支付的金额。这就是让手续费可以逐步取代区块奖励，推动比特币（乃至于所有加密货币）提升流通性的极大关键。
(来源：arXiv)
姚期智及其研究团队通过数学分析，进一步证明了 MP 制确实是接近激励相容，并且在任何随着使用者数量增长下的独立同分布情况下都是如此。
典型的激励相容标准只能处理一种攻击，也就是不诚实的竞价。但比特币用户还可能进行“多重策略竞价”（multiple strategic bids）等其它类型攻击。也就是一名用户可能会将他的交易拆分成几个不同交易，分开竞价。这个方式甚至可以让一个原本失败的交易被纳入区块。
而这篇论文中也证明了 MP 制即使是在面临多重策略竞价等其它攻击出现的情况下，依然是激励相容的。
同时，姚期智也探讨了 RSOP 制。他与研究团队证明了，正如 Ron Lavi 等人所推测的，RSOP 收益必然会依照 MP 收益而定。
这些结果，为 MP 制作为比特币交易费制度的一个方案，提供了佐证与支持。
姚期智：理论计算机科学可以成为区块链系统设计的有用工具
姚期智一文的贡献可以分为两个层面。第一，这篇论文证明了垄断价格机制是接近激励相容的。且在多重策略竞价（MSB）攻击下依然如此。同时，该文结果也显示出，垄断价格可以决定随机取样最优价格式拍卖的收益价格。这些结果为垄断价格作为比特币费率设计的一种方案，提供了支持。
第二，姚期智研究团队在证明中所采用的研究方法，运用了精密的数学分析。他特别强调，这展现出理论计算机科学（theoretical computer science）可以成为区块链系统设计的一个有用工具。
最后，姚期智研究团队也认为，激励相容区块链设计这个新兴领域，是一个令人兴奋的研究领域，有着许多吸引人的问题等待解决，对于理论科学家，对于系统设计者来说都是如此。
参考：
[1] Andrew Chi-Chih Yao,“An Incentive Analysis of some Bitcoin Fee Designs”, Nov 11, 2018, https://arxiv.org/abs/1811.02351
[2] Ron Lavi, Or Sattath, Aviv Zohar,“Redesigning Bitcoin's fee market”Sep 26, 2017, https://arxiv.org/abs/1709.08881
