V神的2019和2021

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

这些问题可以分为三类：

密码学，因此如果它们是可解的，那么就需要用纯粹的数学技术来解决。

共识理论，在很大程度上改进了工作证明和权益证明。

经济方面，必须创建涉及给予不同参与者激励的结构，并且其经常涉及应用层而不是协议层。

我们在所有领域都看到了显著的进步，在有些领域的进步要比其他的更大。

密码问题

区块链可扩展性

今天加密货币领域面临的最大问题之一是可扩展性问题……[超大区块链]的主要问题是信任：如果只有少数实体能够运行完整的节点,然后这些实体可以合谋,并同意给自己大量的额外的比特币,如果不自己处理整个区块，其他用户就无法亲眼看到一个区块是无效的。

问题：创建一个区块链设计，保持类似比特币的安全保障，但网络保持运行所需的最强大节点的最大大小在交易数量上基本上是次线性的。

现状：巨大的理论进展，等待更多的现实评估。

可扩展性是一个技术问题，我们已经在理论上取得了巨大的进展。五年前，几乎没有人考虑过分片;现在，分片设计很常见。除了以太坊2.0，我们还有OmniLedger、LazyLedger、Zilliqa，似乎每个月都有研究论文出来。在我看来，在这一点上的进一步发展是渐进的。从根本上说，我们已经有许多技术可以让验证者组在安全的情况下比单个验证者处理更多数据，在这一点上已经达成共识 ，以及允许客户间接验证区块的完全有效性和可用性的技术，即使在51% 攻击的条件下。

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

随机抽样，允许一个随机选择的小委员会在统计上代表完整的验证者集合：https：//github.com/ethereum/wiki/wiki/Sharding-FAQ#how-can-we-solve-the-single-shard-takeover-attack-in-an-uncoordinated-majority-model

欺诈证明，允许得知错误的单个节点向其他所有人传播其存在：https：//bitcoin.stackexchange.com/questions/49647/what-is-a-fraud-proof

保管证明，允许验证者概率性地证明他们单独下载并验证了一些数据：https：//ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236

数据可用性证明，允许客户端检测它们的标题所在的区块体是否不可用：https：//arxiv.org/abs/1809.09044。参见更新的默克尔树编码提案。

还有其他较小的发展，如通过收据进行跨分片通信，以及“常数因子”增强功能，如BLS签名聚合。

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

时间戳

问题：创建一个分布式激励兼容系统，无论它是一个叠加在区块链或它自己的区块链之上，都可以保持当前时间的高精度。所有合法用户的时钟都围绕某个“真实”时间呈正态分布，标准差为20秒。没有两个节点的间隔超过20秒。

解决方案允许依赖于现有的“N节点”概念;在实践中，这将通过权益证明或非女巫代币来实施。系统应该持续提供120秒以内（如果可能，可以更少），并且是需要在>99%的诚实参与节点的内部时钟里。外部系统可能最终依赖于这个系统；因此，无论动机如何，它都应该保持安全，防止攻击者控制小于25%的节点。

状态：取得一些进展。

以太坊实际上在13秒的区块时间和没有特别先进的时间戳技术下存活得很好；它使用了一种简单的技术，在这种技术中，客户端不接受声明的时间戳早于客户端本地时间的区块。尽管如此，这还没有在严重的攻击中得到验证。最近的网络调整时间戳提案试图最近的网络调整时间戳提案试图通过允许客户端在客户端无法高精度地知道当前时间的情况下确定时间的共识来改善现状；这还没有经过测试。

但总的来说，时间戳目前还不是感知到的研究挑战的前沿；也许这将再次改变权益证明链(包括以太坊2.0和其他)作为真实的实时系统上线，我们看到问题是什么。

计算的任意证明

问题：问题：创建程序 POC_PROVE(P,I) -> (O,Q) 和 POC_VERIFY(P,O,Q) -> { 0, 1 } 使得 POC_PROVE 在输入 I 上运行程序 P 并返回程序输出 O 和 a计算证明 Q 和 POC_VERIFY 获取 P、O 和 Q，并输出 Q 和 O 是否由 POC_PROVE 算法使用 P 合法生成。

现状：理论和实践都有很大进步。

这基本上是说，建立一个SNARK(或STARK，或SHARK，或…)。我们做到了! SNARK现在被越来越多的人理解，甚至已经在多个区块链中使用(包括以太坊上的 tornado.cash)。SNARK 非常有用，无论是作为隐私技术(见Zcash和tornado.cash)，还是作为可扩展性技术(见ZK Rollup, STARKDEX和STARKing纠删码数据根)。

在效率方面仍然存在挑战；创建对算法友好的哈希函数是一个大问题，有效地证明随机内存访问是另一个问题。此外，证明时间中的O(n * log(n))爆炸是否有一个基本的限制，或者是否有一种方法可以做出一个简洁的证明，只需要线性开销，就像在防弹(不幸的是，验证需要线性时间)。此外，现有方案存在缺陷的风险也一直存在。总的来说，问题在于细节而不是基础。

代码混淆

圣杯是创建一个混淆器 O，这样给定任何程序 P，混淆器可以生成第二个程序 O(P) = Q，这样，如果给定相同的输入，P 和 Q 将返回相同的输出，重要的是，Q 显示没有关于 P 内部的任何信息。可以在 Q 中隐藏密码、秘密加密密钥，或者可以简单地使用 Q 来隐藏算法本身的专有工作。

状态：进展缓慢。

简单地说，问题是我们想要找到一种方法来“加密”程序，这样经过加密的程序对于相同的输入仍然会给出相同的输出，但是程序的“内部”将被隐藏。混淆的一个示例用例是一个包含私钥的程序，其中该程序只允许私钥对某些消息进行签名。

代码混淆的解决方案对区块链协议非常有用。用例是很微妙的，因为必须处理链上混淆程序被复制并在与链本身不同的环境中运行的可能性，但是有很多可能性。我个人感兴趣的一个是通过把包含一些工作证明的混淆程序的操作者替换掉，进而将中心化的操作者从防共谋的小工具中移除，这使得使用不同的输入进行多次运行以确定单个参与者的行动的成本非常高。

不幸的是，这仍然是一个难题。解决这一问题的工作仍在继续，一方面建立结构，试图减少对我们不知道实际存在的数学对象的假设数量(例如:通用密码多线性映射)，另一方面试图使所需的数学对象的实际实现。然而，所有这些路径距离创建可行的和已知的安全的东西还很远。有关这个问题的更多概述，请参见https://eprint.iacr.org/2019/463.pdf。

基于哈希的密码学

问题：创建一个不依赖安全假设的签名算法，而是依赖哈希的随机预言属性，保持160位的安全对抗经典计算机的最佳尺寸和其他性质。

状态：一些进展。

自2014年以来，在这方面取得了两方面的进展。SPHINCS是一种“无状态”(意思是，意思是多次使用它不需要像随机数一样记住信息)签名方案，它在这个“难题”列表发布后不久就发布了，并提供了一个大小约为41 kB的纯粹基于哈希的签名方案。此外，STARK已经被开发出来，人们可以根据它们创建类似大小的签名。事实上，不仅仅是签名，还有通用的零知识证明，都可以通过哈希实现，五年前的我绝对是没有想到的；我很高兴。也就是说，大小仍然是一个问题，现在的进展是正在继续减少证明的大小(例如最近的DEEP FRI)，尽管看起来进一步的进展将是渐进的。

基于哈希的密码学尚未解决的主要问题是聚合签名，类似于 BLS 聚合使之成为可能。众所周知，我们可以在许多Lamport签名上创建一个STARK，但这是低效的；一个更有效的方案将是受欢迎的。(如果你想知道基于哈希的公钥加密是否可行，答案是，不，你不能做任何超过二次攻击成本的事情)。

共识理论问题

抗ASIC工作证明

解决这个问题的一种方法是基于一种很难专门化的计算类型创建一个工作证明算法……有关抗ASIC硬件的更深入讨论，请参见https：//blog.ethereum.org/2014/06/19/mining/。

现状：已尽我们所能。

在“难题”列表发布大约6个月后，以太坊确定了其抗ASIC的工作证明算法：Ethash。Ethash被认为是一种内存硬算法。其理论是，普通计算机中的随机存取存储器已经得到了很好的优化，因此很难在专门的应用程序中加以改进。Ethash的目标是通过使内存访问成为运行PoW计算的主要部分来实现ASIC抵抗。

Ethash不是第一个内存硬算法，但它确实增加了一个创新：它在一个两级DAG上使用伪随机查找，允许用两种方法来计算函数。首先，如果一个人有整个DAG(约2GB) ，就可以快速计算它；这就是内存困难的“快速路径”。其次，如果只有 DAG 的顶层，那么计算速度就会慢得多(但仍然能够快速地检查单个解决方案)；这用于区块验证。

事实证明，Ethash在抗ASIC方面非常成功；经过3年时间和数十亿美元的区块奖励，ASIC确实存在，但其性能和成本效益最多是GPU的2-5倍。ProgPoW已经被提议作为一种替代方案，但越来越多的共识是抗ASIC算法的生命周期是有限的，而且抗ASIC也有缺点，因为它使51%攻击成本更低(例如，参见以太坊经典的51%攻击)。

有用的工作证明

制作工作证明的同时使其有用；一个候选项目是Folding@home，这是一个现有的程序，用户可以将软件下载到电脑上，模拟蛋白质折叠，并为研究人员提供大量数据，帮助他们治疗疾病。

现状：可能不可行，但有一个例外。

有用的工作证明的挑战是工作证明算法需要很多属性：

很难计算

容易验证

不依赖于大量的外部数据

可以在小的“一口大小”的区块中有效地计算。

不幸的是，保留所有这些属性的有用计算并不多，而且大多数具有所有这些属性且“有用”的计算只是在太短的时间内“有用”，无法围绕它们构建加密货币。

然而，可能有一个例外：零知识证明一代。区块链有效性方面的零知识证明(例如，数据可用性根)很难计算，但易于验证。此外，它们一直难以计算;如果“高度结构化”计算的证明变得太容易了，人们可以简单地切换到验证区块链的整个状态转换，因为需要对虚拟机和随机内存访问建模,这将变得非常昂贵。

区块链有效性的零知识证明为区块链用户提供了极大的价值，它可以替代直接验证链的需要；Coda已经在这样做了，尽管使用了简化的区块链设计，为可证明性做了大量优化。这种证明可以显著地帮助提高区块链的安全性和可扩展性。也就是说，实际需要完成的计算总量仍然远远少于目前由工作证明矿工所完成的计算总量，所以这充其量只是权益证明区块链的一个附加部分，而不是一个完全的共识算法。

权益证明

解决挖矿中心化问题的另一种方法是完全取消挖矿，改用其他机制计算共识中每个节点的权重。迄今为止，讨论中最受欢迎的替代方案是“权益证明”——也就是说，不再将共识模型视为“一个单位的 CPU 算力，一票”，而是“一个货币单位，一票”。

现状：巨大的理论进展，等待更多的现实评估。

临近2014年底，权益证明社区清楚地表明，某种形式的“弱主体性”是不可避免的。为了维护经济安全，节点在第一次同步时需要获得最近的检查点额外协议，如果它们离线超过几个月，也需要再次获得检查点额外协议。这是一颗难以下咽的药丸;许多PoW倡导者仍然坚持使用PoW，因为在PoW链中，链的“头”可以被发现，而来自可信来源的唯一数据就是区块链客户端软件本身。然而，PoS的支持者却愿意吞下这颗药丸，因为他们认为增加的信任要求并不大。从那时起，通过长期保证金获得权益证明的途径变得清晰起来。

今天大多数有趣的共识算法基本上与PBFT相似，但将固定的验证者集替换为一个动态列表，任何人都可以通过将代币发送到一个系统级的智能合约(带有时间锁定提款)来加入这个动态列表。在某些情况下，提款可能需要4个月才能完成)。在许多情况下(包括以太坊2.0)，这些算法通过惩罚以某些方式执行违反协议的行为的验证者来实现“经济终结”。

到今天为止，我们有(在许多其他算法中)：

Casper FFG：https：//arxiv.org/abs/1710.09437

Tendermint：https：//tendermint.com/docs/spec/consensus/consensus.html

HotStuff：https：//arxiv.org/abs/1803.05069

Casper CBC：https：//vitalik.ca/general/2018/12/05/cbc_casper.html

继续进行改进中。Eth2的0阶段，将实现FFG的链，目前正在实施中，已经取得了巨大的进展。此外，Tendermint已经以Cosmos链的形式运行了几个月。在我看来，关于权益证明的其余争论，与优化经济激励，以及进一步规范应对51%攻击的策略有关。此外，Casper CBC规范仍然可以使用具体效率的改进。

存储证明

解决这个问题的第三种方法是使用计算能力或货币以外的稀缺计算资源。在这方面，已经提出的两个主要替代方案是存储和带宽。原则上没有办法提供带宽被给予或使用的事后加密证明，所以带宽证明应该最准确的被认为是社会证明的一个子集，在后面讨论的问题，但存储证明是肯定可以计算的。存储证明的一个优点是它完全抗ASIC；我们在硬盘驱动器中的存储已经接近最佳。

现状：许多理论有进展，尽管还有很多要做，以及需要更多的现实评估。

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

经济方面

稳定价值的加密资产

比特币的一个主要问题是价格波动。问题：构造一个价格稳定的加密资产。

状态：取得一些进展。

MakerDAO现在已经上线了，并且已经稳定运行了近两年。它在其基础抵押资产 (ETH) 价值下跌 93% 的情况下幸存下来，目前已发行的DAI超过1亿美元。它已经成为以太坊生态系统的中流砥柱，许多以太坊项目已经或正在与之集成。其他合成代币项目，如UMA，也在迅速获得支持。

然而，尽管MakerDAO系统在2019年艰难的经济环境中存活了下来，但这绝不是可能发生的最艰难的情况。过去，比特币在两天内下跌了75%；同样的事情将来也会发生在以太坊或任何其他抵押资产上。对基础区块链的攻击是一个更大的未经检验的风险，特别是如果在同一时间通过价格下跌进行了复合。

另一个主要的挑战，可以说是更大的挑战，是类似于MakerDAO系统的稳定性依赖于某些底层预言机方案。预言机系统确实存在不同的尝试，但它们在大的经济压力下能有多强的支撑能力仍有待商榷。到目前为止，由MakerDAO控制的抵押品已经低于MKR代币的价值；如果这种关系发生逆转，MKR持有者可能会有集体动机去“掠夺”MakerDAO系统。有一些方法可以防止这种攻击，但它们还没有在现实生活中得到验证。

去中心化公共物品激励

一般来说，经济体系面临的挑战之一是“公共物品”问题。例如，假设有一个科学研究项目，将花费100万美元来完成，而且据了解，如果它完成了，结果研究将为100万人每人节省5美元。总的来说，社会效益是明显的……[但是]从每个人的角度来看，贡献是没有意义的……

到目前为止，公共物品的大多数问题都涉及到中心化。附加假设和要求：存在一个完全可信的预言机来确定某个公共物品任务是否已经完成(实际上这是错误的，但这是另一个问题的领域)。

状态：取得一些进展。

公共物品的筹资问题一般被理解为分为两个问题：资金问题(公共物品从哪里获得资金)和偏好聚合问题(如何确定什么是真正的公共物品,而不是单个人的宠物项目)。这个问题特别关注前者，假设后者已经解决了(关于该问题的工作，请参阅“去中心化贡献度量”一节)。

总的来说，这方面还没有新的重大突破。有两种主要的解决方案。首先，我们可以尝试激发个人的贡献，给予人们这样做的社会奖励。我自己提出的通过边际价格歧视进行慈善的建议就是一个例子；另一个是Peepeth上的抗疟疾捐赠徽章。其次，我们可以从具有网络效应的应用程序中收集资金。在区块链范围内，有几个可以做到这一点：

发币

在协议层面收取一部分交易费用(例如通过 EIP 1559)

从某些layer2应用程序(例如，Uniswap，或一些可扩展的解决方案，甚至在以太坊2.0的执行环境中状态租金)

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

在区块链土地之外，这只是一个古老的问题，如果你是政府，如何征税，如果你是企业或其他组织，如何收费。

声誉系统

问题：设计一个正式的声誉系统，包括一个分数 rep(A,B) -> V ，其中 V 是从 A 的角度来看 B 的声誉，一种确定一方可以被另一方信任的概率的机制，以及在给定特定公开或最终交互的记录的情况下更新声誉的机制。

状态：进展缓慢。

自2014年以来，关于声誉系统的研究并不多。也许最好的方法是使用代币托管注册表来创建可信实体/对象的托管列表；Kleros ERC20 TCR(是的，这是一个合法ERC20代币的注册表)就是一个例子，甚至还有一个替代的接口，使用Uniswap (http：//uniswap.ninja)作为后端，从它获取代币、代币代码和标识的列表。

主观多样性的声誉系统还没有真正被尝试过，可能是因为关于人们彼此联系的“社交图”的信息还不够多，而这些信息已经以某种形式发布出来。如果这些信息因为其他原因而开始存在，那么主观声誉系统可能会变得更受欢迎。

卓越证明

对于代币分发问题，有一种有趣的、很大程度上尚未探索的解决方案(这是为什么它不能如此容易地用于挖矿的原因)，即使用对社会有用的任务，但需要原始的人类驱动的创造性努力和才能。例如，我们可以想出一种“证明证明”币，奖励提出某些定理的数学证明的玩家。

现状：没有进展，问题基本上被遗忘。

代币分发的主要替代方法是空投;通常情况下，令牌在发行时要么按比例分配其他令牌的现有持有，要么基于其他指标(例如。比如握手空投)。直接验证人类创造力还没有真正尝试过，而且随着人工智能最近取得的进展，创造一项只有人类可以完成、但计算机可以验证的任务可能太困难了。

反女巫系统

与声誉系统相关的一个问题是创建“唯一身份系统”的挑战——生成代币的系统，以证明一个身份不是女巫攻击的一部分……然而，我们希望有一个比“一美元一票”更好、更平等的系统；可以说，一人一票是理想的选择。

状态：取得一些进展。

已经有不少人试图解决这个独特的人类问题。想到的尝试包括(不完整的列表!)

HumanityDAO：https：//www.humanitydao.org/

Pseudonym parties：https：//bford.info/pub/net/sybil.pdf

POAP(“出席证明协议”)：https：//www.poap.xyz/

BrightID：https：//www.brightid.org/

随着人们对二次投票和二次赠款等技术的兴趣不断增长，对某种基于人类的反女巫系统的需求也在不断增长。希望这些技术和新技术的不断发展能够满足这一要求。

去中心化贡献指标

不幸的是，激励公共物品的生产并不是中心化解决的唯一问题。另一个问题是，首先，确定哪些公共物品是值得生产的，其次，确定某种努力在多大程度上实际完成了公共物品的生产。这一挑战涉及后一个问题。

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

最近关于确定公益贡献价值的工作并没有试图将确定任务和确定完成的质量分开；原因是这两者在实践中很难区分。由特定团队完成的工作往往是不可替代的和足够主观的，因此最合理的方法是将任务的相关性和性能质量作为一个单独的包，并使用相同的技术来评估两者。

幸运的是，这方面已经取得了很大的进展，特别是二次赠款的发现。二次赠款是指个人可以对项目进行捐赠，然后根据捐赠的人数和捐赠的金额，用一个公式来计算如果他们彼此完全协调(即，捐赠的金额是多少)，他们会捐赠多少。考虑了彼此的利益，没有成为公地悲剧的牺牲品)。

对于任何一个特定的项目，可能已经捐赠的金额和实际捐赠的金额之间的差额将作为某个中央资金池的补贴提供给该项目。需要注意的是，这种机制专注于满足某些社区的价值，而不是满足某些给定的目标，不管是否有人关心它。由于值问题的复杂性，这种方法可能对未知的未知数来说更稳。

在最近的Gitcoin二次赠款中，二次赠款甚至已经在现实生活中尝试过，并取得了相当大的成功。在改进二次赠款和类似机制方面也取得了一些进展；特别是成对有界的二次赠款，以减少共谋。在规范和实现反贿赂投票技术方面也做了一些工作，防止用户向第三方证明他们投票给了谁；这防止了多种勾结和贿赂攻击。

去中心化成功指标

问题：提出并实施一种去中心化的方法来测量真实世界的数值变量…该系统应该能够测量任何人类目前可以达成粗略共识的东西(例如，资产价格、温度、全球二氧化碳浓度)。

状态：取得一些进展。

这现在通常被称为“预言机问题”。已知的最大的去中心化预言机运行实例是Augur，它处理了数百万美元的质押结果。代币管理注册表(如代币的Kleros TCR)是另一个例子。然而，由于一个极具争议的问题或由于尝试 51% 攻击，这些系统仍然没有看到对分叉机制的真实世界测试。也有关于区块链空间之外发生的预言机问题的研究，以“对等预测”文献的形式出现。

另一个迫在眉睫的挑战是，人们希望依靠这些系统来指导大于系统原生代币经济价值的资产数量的转移。在这种情况下，理论上，代币持有者有动机串通给出错误答案以窃取资金。

在这种情况下，系统将分叉，原始的系统代币可能变得毫无价值，但原始的系统代币持有者仍然可以从他们错误引导的任何资产转移中获得回报。稳定币就是一个例子。解决这个问题的一种方法是建立一个系统，假定无私地诚实的数据提供者确实存在，创建了一个机制来识别它们，并且只允许它们缓慢地搅动，如果有恶意的在用户系统投票，依赖于预言机的用户可以先完成有序退出。无论如何，预言机技术的进一步发展是一个非常重要的问题。

新问题

如果我在2019年再写一遍难题列表，有些是上述问题的延续，但重点会有很大的变化，也会有很大的新问题。

以下是一些问题：

密码混淆：与上面第4条相同。

正在进行的后量子密码学的工作：基于哈希的和基于后量子安全的“结构化”数学对象，例如。椭圆曲线构体…

反共谋基础设施：正在进行的工作和完善https：//ethresear.ch/t/minimal-anti-collusion-infrastructure/5413，包括添加针对运营商的隐私，以最实用的方式添加多方计算等。

预言机：与上面的#16 相同，但不再强调“成功指标”，而专注于一般的“获取真实世界数据”问题。

唯一的人类身份(或者,更现实,半唯一的人类身份)：与上面#15 所写的相同，但强调的是一种不那么“绝对”的解决方案：获得两个身份应该比获得一个身份难得多，但使其不可获得多个身份也是既不可能，也可能有害，即使我们成功了。

同态加密和多方计算：为了实用性，仍需不断改进。

去中心化治理机制：DAO很酷，但当前的DAO仍然非常原始;我们可以做得更好。

充分形式化对PoS 51%攻击的响应：可见https：//ethresear.ch/t/responding-to-51-attacks-in-casper-ffg/6363。

更多的公共物品资金来源：理想的做法是对具有网络效应的系统内的拥挤资源收费（如交易费用)，但在去中心化系统中这样做需要公共合法性；因此，这既是一个社会问题，也是一个寻找可能来源的技术问题。

声誉系统:与上面的第12条相同。

一般来说，基础层的问题正在缓慢但肯定地减少，但应用层的问题才刚刚开始。