V神：加密货币的难题-五年之后的回顾

2014年，我发表了一篇文章和一个演讲，列出了数学、计算机科学和经济学中的一系列难题，我认为这些问题对于（我当时称之为的）加密货币领域能够走向成熟非常重要。在过去的五年里，很多事情都发生了变化。但是，在我们当时认为重要的问题上究竟取得了多少进展呢？我们在哪里取得了成功，又在哪里失败了？在什么重要的方面我们的想法被改变了？在这篇文章中，我将逐一回顾2014年以来的16个问题，看看我们今天在每个问题上的进展情况。最后，还将包括我对2019年面临的难题要作出的新选择。

这些问题可分为三类：

密码学，如果它们根本是可解决的，那么预计可以用纯数学技术解决；
共识理论，主要改进PoW（Proof of Work，工作量证明）和PoS（Proof of Stake, 权益证明）；
经济学，涉及创建给予不同参与者激励的结构，并且经常涉及应用层而不是协议层。

我们看到所有类别都取得了重大进展，尽管有些进展比另一些更大。

密码问题

1、区块链可扩展性（Scalability）

当今加密货币领域面临的最大问题之一是可扩展性问题。大规模区块链的主要问题是信任：如果只有几个实体能够运行完整的节点，那么这些实体可以合谋并同意给自己提供大量额外的加密货币；并且，在没有自己处理整个区块链的情况下，其他用户将无法自己看到一个区块是非法的。

问题：创建一种区块链设计，保持类似于比特币的安全保障，但网络保持运行所需的最强节点的最高性能在交易数量上基本上是次线性的。
现状：巨大的理论进步，期待更多来自现实世界的评价。

可扩展性是一个技术性问题，我们在理论上已经取得了巨大的进展。五年前，几乎没有人考虑分片；现在，分片设计司空见惯。除了以太坊2.0 ，我们还有 OmniLedger ， LazyLedger ， Zilliqa ，和似乎每个月都会出来的研究论文。在我自己看来，在这一点上的进一步进展是渐进的。从根本上说，我们已经有许多技术，允许验证者组安全地就单个验证者无法处理的更多数据达成共识，与此同时，这些技术还可以允许用户间接验证区块的全部有效性和可用性，即使低于51％攻击条件。

这些可能是最重要的技术：

另请参阅较新的编码Merkle树建议。

还有其他一些较小的进展，如通过收据的跨分片通信 ,以及“恒定因子”增强，如BLS签名聚合。

也就是说，完全分片的区块链仍未在实时运行中出现(部分分片的Zilliqa最近开始运行)。在理论方面，主要是关于细节的争议，以及与分片网络的稳定性、开发人员体验和降低集中化风险有关的挑战；基本的技术可能性似乎不再有疑问。但是仍然存在的挑战是不能通过仅仅考虑它们就能解决的挑战；只有开发系统并看到以太坊2.0或类似的链运行就足够了。

2、时间戳（Timestamping）

问题：创建分布式激励相容的系统，无论是在区块链顶部还是其自身的区块链上的覆盖图，无论它是在区块链之上的重叠还是其区块链本身，其保持当前时间的高精确度。所有合法用户的时钟都在一些“实时”时间的正态分布中，标准偏差为20秒，两个节点之间的间隔不超过20秒。该解决方案允许依赖于“N个节点”的现有概念；实际上，这将通过权益证明或非Sybil令牌来实施(参见)。系统应持续地提供时间，该时间应在>99%参与的诚实节点的内部时钟的120s内(如果可能，则更短)。外部系统可能最终依赖于此系统；因此，无论动机如何，它都应保持安全，保证攻击者控制不超过25%的节点。
现状：有些进展

实际上，以太坊在13秒的出块时间和没有特别先进的时间戳技术的情况下运行得很好；它使用一种简单的技术，其客户端不接受声明的时间戳早于客户端本地时间的块。这就是说，这还没有在严重的攻击下进行测试。

最近的网络调整时间戳建议试图通过允许客户端在客户端不在本地知道高准确度的当前时间的情况下确定关于时间的共识来改善现状；但这尚未被测试。总的来说，时间戳并不是当前研究挑战的重点。也许一旦PoS链（包括以太坊2.0以及其他）作为真实的实时系统在线出现后，这种情况就会改变，我们将看到问题的重要性。

3、任意计算证明

问题描述：创建程序 POC_PROVE(P, I) -> (O, Q) 和 POC_VERIFY(P, O, Q) -> {0, 1} 。其中 POC_PROVE 执行程序 P，I 是程序 P 的输入， POC_PROVE 返回程序 P 的执行结果 O 和一个基于计算的 Q ； POC_VERIFY 对 P，O，Q ，验证 Q 和 O 是否是由 POC_PROVE 使用 P 得到的合法运行结果。
状态：有重大的理论和实践进展

这基本上说的是要建立一个SNARK（或STARK，SHARK，以及其他名称）。我们已经做到了！（链接1 ，链接2 ，链接3 ）SNARK现在已经被越来越多的人理解，甚至已经在多个区块链中使用（包括以太坊上的tornado.cash）。SNARK非常有用，既可以作为一种隐私技术（参见Zcash和 tornado.cash ），也可以作为一种可扩展性技术（参见 ZK Rollup 、 STARKDEX 和 STARKing erasure coded data roots ）。

但是在效率方面仍然存在挑战；设计算术友好的哈希函数是一个很大的挑战（链接1 ，链接2 ），而高效的证明随机内存访问是另一个挑战。此外，还存在一个尚未解决的问题，证明时间以O(n log n)的增长是否是基本限制，或者是否有某种仅使用线性开销的方法进行简洁的证明，类似防弹技术（bulletproofs，不幸的是，它需要花费线性的时间做验证）。现有方案还存在风险。通常来说，问题出在细节而不是基础上。

4、代码混淆

问题：主要追求的目标是创建混淆函数O，给定任意程序P，混淆函数能够产生第二个程序O(P)=Q，其中P，Q在给定输入的情况下返回相同结果，重要的是，Q没有显示程序P内部的任何信息。人们可以在程序Q中隐藏密码、经过加密的私钥或者新发明创造的算法本身。
状态：进展缓慢

通常来说，这个问题想表达的是如何去寻找一种对程序加密的方法，使得加密后的程序在相同输入下输出相同的结果，但源程序内部的信息会被隐藏起来。代码混淆的示例用例是一个包含私钥的程序，其仅允许私钥对某些消息进行签名。

代码混淆的解决方案对于区块链协议极其有用，其应用场景是非常微妙的。因为必须处理链上的混淆程序被拷贝复制并运行在另一个异于链本身的环境的可能性，除此之外还有很多其他情况。一个令我个人非常感兴趣的应用场景是使用混淆后的程序来替代原先包含一些工作量证明的操作，从而能够在抗冲突的小工具中删除掉集中化的操作，使得尝试采用运行不同的输入多次运行来确定参与者私人行为的操作是非常昂贵的。

不幸的是这是一个非常难的问题，解决这个问题的道路上还有许多工作要做。一方面是进行构造来减少我们不知是否实际不知道的数学对象的假设数量（比如说通用密码多线性映射），另一方面则是尝试去对需要的数学对象做实际的实现。然而，所有这些路径都离创建可行和已知的安全性还很遥远。参考该问题更一般的概述。

5、基于哈希的密码学

问题：创建一个不依赖安全性假设而是基于哈希值随机预言机属性的签名算法，其可保持和具有最佳尺寸和其他属性的经典计算机（例如，由Grover算法设计的量子计算机等同于80位比特）等同的160位比特大小安全性。
状态：有些进度

自2014年以来，这方面已取得了两大进展。 SPHINCS 是一种“无状态”签名方案（意味着多次使用不需要像随机数一样记住信息），它在此“难题”列表发布后不久就发布了，并提供大小约为41 kB的纯基于哈希的签名方案。另外， STARK 也被开发出来，可以基于它们创建相似大小的签名。我五年前没有想到哈希不仅可以用来签名，还可以用于通用目的上的零知识证明。对于这种情况，我感到非常高兴。这意味着，尺寸仍然是一个问题，并且持续不断的进展正在继续减小证明的规模（例如，请参阅最新的 DEEP FRI ），尽管看起来这进展也很缓慢。

基于哈希的加密技术尚未解决的主要问题是聚合签名，类似于 BLS聚合做的那样。众所周知，我们可以对许多Lamport签名进行STARK，但这效率低下，一个更有效率的方案将会很受欢迎。（如果您想知道是否可以使用基于哈希的公钥加密，答案是不，你不能以平方次攻击或者更严重的代价进行任何操作）。

共识理论问题

6、抗ASIC的工作量证明（PoW）

解决方案是创建一种解决特殊问题的难度极高的算法，深层讨论ASIC的请看这里
现状：是我们已经尽力去解决的问题。

在“困难问题”列表发布大约六个月之后，以太坊决定采用其抗ASIC的工作证明算法： Ethash 。 Ethash被称为硬性内存算法。从理论上讲，常规计算机中的随机存取存储器已经得到了很好的优化，因此很难针对特殊应用进行改进。 Ethash旨在通过使内存访问成为运行PoW计算的重要环节来实现抗ASIC。 Ethash并不是第一个硬性内存要求的算法，但它确实增加了一项创新：它在两层DAG上使用伪随机查找，从而提供了两种评估函数的方式。首先，如果一个人拥有整个（~2 GB）DAG，则可以快速计算出它；这是满足硬性内存要求的“快速路径”。其次，如果只有DAG的顶层，则需要缓慢地计算（仍然可以快速验证结果）。用于区块验证。

Ethash在抗ASIC方面被证明非常成功。经过三年和数十亿美元的区块奖励后，ASIC确实存在，但其功能和成本充其量最多比GPU 高2-5倍。已经提出了 ProgPoW 作为替代方案，但是越来越多的共识认为，抗ASIC的算法将不可避免地具有有限的生命周期，并且ASIC抗性有缺点，因为它使51％的攻击更加便宜（例如，参见对以太坊经典的51％攻击）。

我相信可以创建提供中等级别的抗ASIC的PoW算法，但是这种抵抗力是有限的，并且ASIC和非ASIC PoW都有缺点。从长远来看，区块链共识的更好选择是股权证明。

7、有用的工作量证明（PoW）

使工作量证明同时有证明之外的作用；常见的候选人是Folding@home之类的东西，Folding@home是一个现有程序，用户可以将软件下载到计算机上以模拟蛋白质折叠，并为研究人员提供大量数据，以帮助他们治愈疾病。
现状：可能不可行，只有这一个例外。

有用的工作量证明所面临的挑战是，工作量证明算法需要许多属性：

难于计算，易于证明
不依赖大量外部数据
可以高效的分块计算

不幸的是，没有很多有用的计算可以保留所有这些属性，并且大多数具有所有这些属性并且“有用”的计算只是“有用”的时间太短，无法基于它们构建加密货币。

但是，有一个可能的例外：就是零知识证明。区块链方面的零知识证明（例如，一个简单示例的数据的可用性）难以计算且易于验证。此外，它们计算难度很高。如果“高度结构化”计算的证明变得太容易了，则可以简单地切换到验证整个区块链状态的变化，由于需要对虚拟机和随机内存访问进行建模，因此变得非常昂贵。

区块链有效性的零知识证明为区块链用户提供了巨大的价值，因为他们可以代替直接验证链的需求； Coda 已经在做这件事，尽管它的区块链设计非常简单，并针对可证明性进行了优化。这些证明可以极大地帮助改善区块链的安全性和可扩展性。也就是说，实际需要完成的计算总量仍然远远小于工作量证明矿工当前完成的计算量，因此，充其量充其量不过是权益证明区块链证明的附加内容，而不是完整的关于共识算法。

8、权益证明

解决挖掘集中化问题的另一种方法是完全取消挖掘，并转向其他机制来计算共识中每个节点的权重。迄今为止，讨论中最流行的替代方法是“股权证明”-也就是说，与其将共识模型视为将一cpu一票变为一币一票。
现状：重大的理论进展，需要更多的实践评估。

在2014年底之前，权益社区的证据清楚表明，某种形式的“弱主观性”是不可避免的。为了维护经济安全，节点在首次同步时需要获取最近的检查点协议，如果节点离线超过几个月则需要再次获取。这是个很大的风险。许多PoW拥护者仍然坚持使用PoW，因为在PoW链中，可以发现链的“头”，作为唯一的数据来自可信来源，即区块链客户端软件本身。但是，PoS倡导者愿意承担这种风险，因为增加的信任要求并不大，通过长期的保证金证明股权的途径变得很明确。

如今，最有趣的共识算法从根本上类似于 PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错算法），但是用一个动态列表替换了固定的验证器集，任何人都可以通过将令牌发送到具有锁定时间的系统级智能合约中来加入任何人都可以加入的动态列表（例如，在某些情况下，提取可能最多需要4个月才能完成）。在许多情况下（包括以太坊2.0），这些算法通过对验证者进行处罚，从而发现他们以某些方式违反协议的行为而实现了“经济最终性”（有关权益证明的完成之处，请参见此处的哲学观点）如下：

这些也在继续进行细化( 1 ， 2 )。以太坊2.0（将实施FFG的链）目前正在实施中，并已取得了巨大进展。另外，Tendermint以 Cosmos链的形式运行了几个月。我认为，关于股权证明的其余论点与优化激励措施和进一步规范应对 51％攻击的策略有关。此外， Casper CBC规范仍可以用来作为具体的效率改进。

9、储存证明

解决该问题的第三种方法是使用计算能力或货币以外的稀缺计算资源。在这方面，已提出的两个主要替代方案是存储和带宽。原则上，没有办法提供给定或使用带宽的事后加密证明，因此，带宽证明应最准确地视为社会证明的一个子集，在后面的问题中进行讨论，但是存储证明是当然可以通过计算完成。存储证明的一个优点是它完全可以抵抗ASIC的攻击。硬盘驱动器中的存储类型已经接近最佳。
现状：已经取得一些理论进展，但仍有很多路要走，同时需要更多的实际评估。

有许多计划使用存储协议证明的区块链，包括 Chia 和 Filecoin 。也就是说，这些算法尚未经过野外测试。我自己的主要关注点是集中化：这些算法实际上是由使用备用存储容量的较小用户主导，还是由大型采矿场主导？

经济学

10、稳定币

比特币的主要问题之一是对法币价格的波动。

问题：合成对法币对价稳定的加密资产。
状态：有些进展。

MakerDAO 现在已经投入使用，并且稳定运行了将近两年。它的基本抵押资产ETH的价值下跌了93％，幸免于难，现在发行的合成稳定代币DAI超过1亿美元。它已经成为以太坊生态系统的支柱，许多以太坊项目已经或正在与之集成。其他合成代币项目，例如 UMA ，也正在迅速获得发展。

但是，尽管MakerDAO的系统在2019年经历了严峻的经济形势，但情况绝不是最艰难的。过去，比特币在两天内下跌了75％；同样的情况有一天也可能发生在以太坊或任何其他抵押资产上。同此同时，对区块链底层的恶意攻击是更大的未经检验的风险，这种风险预期会带来的价格下跌更加加剧了风险本身；另一个可能更大的重大挑战是，类似于MakerDAO的系统的稳定性取决于非公开的预言机。目前，确实存在针对预言机的不同尝试（请参阅），但对于在巨大的经济压力下它们能否承受得住的问题，尚无定论。

到目前为止，由MakerDAO控制的抵押品低于MKR代币的价值；如果这种关系发生逆转，那么MKR持有者有动机集体试图“掠夺” MakerDAO系统。有多种方法可以防止此类攻击，但尚未在现实世界中进行过测试。

11、去中心化公共物品激励

通常，经济体系中的挑战之一是“公共物品”问题。例如，假设有一个科学研究项目将花费100万美元来完成，并且已知，如果这项研究完成，则所产生的研究将为100万人节省5美元。总体而言，公共物品的社会收益是明确的，然而，从每个人的贡献的角度来看都是没有道理的。到目前为止，大多数公共物品问题的解决都涉及中心化。

附加假设和要求：存在用于确定某个公共物品任务是否已经完成的完全可信赖的预言机（实际上这是错误的，但这是另一个问题的领域）

状态：有些进展。

一般认为，为公共物品提供资金的问题可以分为两个问题：资金问题（从何处获得公共物品的资金）和倾向聚合问题（如何确定什么是真正的公共物品，而非某些个人的私人项目）。这里假设后者已解决，此问题专门针对前者，即资金问题（有关该问题的工作，请参见下面的“”部分）。

总的来说，这里没有重大的新突破。解决方案有两类。首先，我们可以尝试引出个人的贡献，从而为人们提供社会奖励。我自己关于通过边际价格歧视进行慈善的提议就是一个例子；另一个是 Peepeth 的抗疟疾捐赠徽章。其次，我们可以从具有网络效应的应用程序中收集资金。在区块链领域内，有几种选择可以做到这一点：

发行代币

在协议级别收取交易费用（例如， EIP 1559 ）

从某些Layer-2的应用程序中收取交易费用（例如Uniswap或某些可伸缩解决方案，甚至在以太坊2.0的执行环境中收取租借费用）

收取其他费用（例如ENS注册）

在区块链领域之外，这只是一个传统的问题：政府可以收税；企业或其他组织则可以收费。

网络效应，又称网络外部性或需求方规模经济，指在经济学或商业中，消费者选用某项商品或服务，其所获得的效用与「使用该商品或服务的其他用户人数」具有相关性时，此商品或服务即被称为具有网络效应。

12、信誉系统

问题：设计一个形式化的信誉体系，包括：一个信誉分数，rep（A，B）-> V，其中 V 表示从 A 的角度来衡量 B 的信誉；一种确定一方可以信任另一方的概率机制；以及在有某进行中或结束的交互纪录状态下，更新信誉的机制。
状态：缓慢进展

自 2014 年以来，在信誉体系方面还没有过大量工作。也许最好的例子是使用可信任实体/对象创建一个规划好的列表作为代币注册表； Kleros ERC20 TCR （是的，这是合法ERC20代币的注册表）就是一个例子，还有另外的界面接口 Uniswap ，它就是用Kleros作为后端，从中获得代币和代号符号和徽标的列表。具有主观多样性的信誉体系还没有真正尝试过，也许是因为交易者相互联系的”社会关联图”以某种形式上链的信息不充足。如果由于某些其他原因，此类（主观评判）信息开始出现，那么这类信誉系统可能会变得更加流行。

13、优秀的（工作量/贡献度）证明

一个有趣的，而且尚未被大力探索的问题，就是解决[代币]分配问题（这就是为何不能那么简单地适用于挖矿场景-注解：加密哈希的耗费电力运算），（分配遵循）对社会有用的任务，但（设计这个分配）这需要人来驱动的创造性尝试和天赋。例如，人们可以想出一个”证明”货币，奖励那些给出某些数学定理证明的玩家。

状态：无进展，问题几乎被遗忘

代币分发的主要替代方法是空投的流行；通常，代币在启动（初期原始）配时，要么与某些其他代币的现有持有量成比例分配，要么基于其他指标（例如，握手空投，注解：通过某种验证的去中心化空投方式）。直接验证人类的创造力还没有被真正尝试过，随着最近在AI上的进展，创建一个只有人类可以做，但用计算机可以验证的任务，这可能太难了。

14、去中心化贡献度

不幸的是，激励公益物的产出并不是中心化解决的唯一问题。中心化解决的另一个问题是：首先要明确应该产出哪些公益物，然后确定付出多大的工作量才能完成公益物的产出。这一挑战涉及后一个问题。

现状：有些进展，重点有所改变。

近年来在确定公益物贡献度的价值方面的的最新进展并没有将”1.确定任务”和”2.确定完成度”这两个方面分开，原因是在实践中这二者很难分得开。某些团队所做的工作往往是不可替代和主观的，因此最合理的方法是将任务和绩效质量的相关性视为一个整体，并使用相同的技术对它们进行评估。

幸运的是，在这方面已经取得了很大的进步，尤其是发现了“ 二次筹资 ”后。“二次筹资”是一种机制，在这个机制下，个人可以向项目捐款。在捐赠者完美协调条件下，基于捐赠的人数和捐赠的数量，使用公式计算捐赠量。（这里的完美下调指：即考虑到了每个捐赠者的利益，也不会导致所有捐赠集体悲剧）。在给项目捐赠时，本应捐赠的金额与实际捐赠的金额之间的差额将从某个中央资金池中作为补贴提供给项目方（有关中央资金池的来源，请参阅）。请注意，此机制侧重于满足某些社区的价值，而不是满足某些给定的目标，而不管是否有人在乎它。由于价值问题的复杂性，这种方法对于未知的未知数可能更健壮。

在现实中，二次融资机制已经在最近的gitcoin二次融资取得了相当大的成功。在改进二次融资机制和类似机制方面也取得了一些进展；例如，成对有界的二次融资可以减少共谋和串通现象。人们还在关于反贿赂投票技术的规范化和实施方面，做了大量工作，防止用户向第三方证明他们投票给了谁；这防止了多种共谋、串通和贿赂攻击。

15、抗女巫攻击系统

这个问题有点与信誉系统相关，它是创建“唯一身份系统”的挑战。抗女巫攻击系统是一种生成令牌的系统，该令牌证明其身份不属于女巫攻击的一部分。然而，我们希望具有比“一元一票”更好，更平等的系统；可以说，一人一票将是理想的选择。

状态：有些进展。已经进行了许多尝试来解决人类独特的问题。

能够想到的尝试包括（不完整的列表！）：

随着对二次投票和二次融资等技术的兴趣日益浓厚，对某种基于人的反女巫系统的需求也在不断增长。希望这些技术的不断发展和新技术能够满足这些需求。

16、分布式现实测量

问题：提出并实施一种分布式的方法来测量真实世界的数值变量。该系统应该能够测量人类目前可以达成大致共识的任何数值属性（例如，资产价格，温度，全球二氧化碳浓度）。
状态：有些进展。

现在通常将其称为“预言机问题”。分布式预言机运行的最大已知实例是Augur，它已经处理了数百万美元的下注结果；代币管理的注册中心（例如 Kleros TCR ）是另一个示例。然而，这些系统仍然没有看到在分叉机制下的现实世界测试（在这里搜索“ 主观主义 ”），要么是出于一个极具争议性的问题，要么是出于试图进行51%攻击。也有关于发生在区块链空间之外的预言机问题的研究，形式是“ 同行预测 ”；参见这里了解该领域的最新进展。

另一个迫在眉睫的挑战是，人们希望依靠这些预言机系统来指导资产的转移，该资产的数量要大于系统代币的经济价值。在这种情况下，代币持有者理论上有动机合谋提供错误答案以窃取资金。在这种情况下，系统将分叉，原始系统的代币可能会变得毫无价值，但原始系统代币持有者仍然可以从他们误导的任何资产转移中获得回报。稳定币（参见前面的）是一个特别糟糕的例子。解决这个问题的一种方法是建立一个系统，该系统假设利他诚实的数据提供者确实存在，并创建一种机制来识别它们，并且只允许它们缓慢地运转，以便如果恶意数据提供者开始在依赖预言机的系统中获得投票，那么依赖预言机的系统的用户可以首先完成有序的退出。无论如何，预言机技术的进一步发展是一个非常重要的问题。

新问题

如果我要在2019年再次编写难题清单，则上述问题将继续存在，但重点将发生重大变化，同时还将出现新的重大问题。以下是一些精选：

加密混淆

与上面的相同

正在进行的有关后量子密码的工作：既基于哈希，又基于对量子算法安全的“结构化”数学对象，包括椭圆曲线等值线，点阵等。

反共谋基础设施

正在进行的工作和 Minimal anti-collusion infrastructure 的完善，包括增加针对运营商的隐私，以最大程度的实际方式增加多方计算等。

预言机

与上面的相同，但不再强调“现实测量”，而侧重于一般的“获取实际数据”问题

唯一人类身份（或更实际地说，是半唯一人类身份）：与上面的相同，但强调的是“绝对”的解决方案：与获得两个身份相比，要难得多一种，但是即使我们成功了，也无法获得多个身份既是不可能的，而且也有潜在的危害。

同态加密和多方计算

实用性仍需要不断改进。

去中心化治理机制

DAO很酷，但是当前的DAO仍然很原始，我们可以做得更好。

完全形式化对PoS 51％攻击的响应

正在进行的工作和完善的 Responding to 51% attacks in Casper FFG