[译]以太坊 2.0 信标链详解

1

分配:蓝图

为了深入理解信标链,我们需要先介绍分片。目标的以太坊网络中,每一个节点都要验证所有交易,这大大限制了以太坊的扩容性。

在计算机科学里,扩容主要有两种途径:

  • 纵向扩容:使每一个节点的算力更加强大
  • 横向扩容:增加更多的节点

为了符合去中心化的目标,区块链需要横向扩容。以太坊 2.0 的目标就是让节点可以运行在消费级电脑中。分片的目的就是横向切割当前的数据库。

总体来说,一条分片链上有自己的子节点。虚拟矿工,验证者被分配到分片上,并且只执行和验证当前分片(链)上的交易。

每个以太坊的分片拥有的节点,都是动态的,并且会按照顺序执行区块。

分配的一个主要挑战是安全性。由于验证者被分散开来了,恶意的节点们可能就会有控制分片的可能。

解决这个问题的关键在于:随机分配验证者,确保每个分片上都会存在一个通过伪随机算法选取的一个验证者委员会(committee)。在数学概率上,保证攻击者要控制超过分片上的 ⅓ 节点是困难的。

欺诈证明(fraud proofs),数据托管证明(ustody proofs)以及数据可用性检查(data availability checks)也都是确保安全的机制。

目前的以太坊 2.0 计划存在 64 个分片。尽管分片与信标链是分离的,但是我们还是会阐述分片机制中的一些关键元素。

通过上文对分片的描述,已经暗示了不少以太坊信标链该做的以及需要做的事。我们将在下文阐述信标链在传统区块链结构下,又会新增哪些新组件。

以太坊 2.0 阶段图

简单来说,以太坊 2.0 会有三个阶段:
阶段 0 - 信标链
阶段 1 - 分片
阶段 2 - 执行智能合约

如果使用人体来做一个类比的话:
阶段 0 - 心脏
阶段 1 - 四肢
阶段 2 - 大脑

如果使用乐团来做一个类比的话:
阶段 0 - 指挥
阶段 1 - 乐器
阶段 2 - 乐手

每一个阶段对于系统来说都是必要的。阶段 0 是以太坊 2020 年计划的一部分。阶段一的升级会让新系统开始稳定。阶段二的升级则会让新系统能够开始执行逻辑。

插槽(Slots)和轮回(Epochs)

以太坊 2.0 的核心是信标链,它提供了“心跳”。信标链决定了系统中共识的节奏。每一隔 12 秒出一个插槽,每个轮回包含 32 个插槽,即每隔 6.4 分钟产生一个轮回。

2

在每个插槽中,信标链和分片中都有机会可以添加区块。你可以想象,信标链和分片链是步调一致的。系统在理想状态运行时,每间隔 12 秒,就有一个信标链区块和 64 个分片链区块产生。验证者需要大致同步它们的本地时间。

所以从另一个角度,由于间隔固定,插槽也可以被视作区块时间,虽然插槽可以是空。信标链和分片链的创始区块都会在第 0 个插槽的位置。分片链将会在信标链的第 0 个轮回之后的下一个轮回开始启动。不过分片链自己的第 0 个轮回会包含它们自己的创世块。

验证者(Validators),证明(Attestations)和信标链介绍

对标工作量证明公式中的矿工,在以太坊 2.0 的权益证明共识下,也会有“虚拟矿工”。由于存在下文将会讨论的权益奖惩,验证者会积极地参与到共识中来。

当要构建区块时,验证者中将会被伪随机地选出一个区块提议者(block proposer)。

大多数时候,验证者会对信标链和分片链上的区块进行投票,充当一份份证明。这些投票会决定信标链和分片链上的最新区块,并且投票本身也会被记录在信标链中。

3

在每个轮回中,验证者都会被伪随机地洗牌进入不同的分片中。验证者通过投票来决定分片的最新区块,以这种方式加入到共识中。验证者随后会将分片链中的区块头,以一个插槽的形式,链接(link)到信标链的最新区块中。

一个验证者的一次投票,即是一份证明,由验证者所质押的以太币比例来决定权重。证明会在出块时一同被广播。

当有验证者给出不正确的投票或者构建超过一个区块时,其他验证者都可以互相举报。

所以信标链上主要存储的内容有:验证者的地址,验证者的状态,证明以及分片链接(links to shards)。信标链有能力激活验证者,并且改变它们的状态,下文将会详细阐述。

有质押的验证者(Staking validators)

验证者是虚拟的,通过质押者激活而来。在工作量证明的场景里,用户通过购买矿机来成为矿工。在以太坊 2.0 中,用户通过质押以太币来激活和管理验证者。

让我们进一步理解有质押的质押者和有余额的验证者之间的关系。每一个验证者最多可以有 32 个以太币的余额,但是质押者可以质押他们身上所有的以太币(可以超过 32 个)。每有 32 个以太币被质押,就会激活一个验证者。

验证者通过验证者客户端来运行,同时需要与信标链保持配合。每一个信标节点都拥有追踪和读取信标链的功能。每一个验证者客户端也可以作为信标节点使用,并且与其他信标节点通信。一个验证者客户端可以同时包含多个验证者的职能。

交联(Crosslinks)

交联(Crosslinks)是信标链中对分片区块的一个引用。交联用于让信标链能够追踪上分片链的最新块。由于存在 64 个分片链,所以一个信标链区块最多可以包含 64 个交联。如果在一个插槽里,有 63 个分片都没有提交块,那么那个信标链块可能就只包含一个交联。交联计划在阶段 1 实现,用于将分片链扎根于信标链上。为分片链提供分叉选择,确认最终确定性和跨分片通信。所有的分片链都时刻会于信标链保持相连。

委员会(Committees):简介

一个委员会由若干验证者组成。为了安全起见,在信标链和分片链中,每一个插槽都必须有一个至少拥有 128 个验证者的委员会。攻击者控制委员会中 ⅔ 节点的概率,低于万亿分之一

以太坊信标链的名称,由来于随机信标(randomness beacon)这一概念(向公众提供随机数)。信标链通过一个成为 RANDAO 的伪随机流程来确认共识。

4

RANDAO 会以验证者的余额为权重,选择区块的提议者。在同一个插槽内,一个验证者可以同时是提议者和委员会成员,但这不常见,发生的概率大概是 1/32 ,所以我们大约在每一个轮回中可以看到一次。上图的场景中验证者数量少于 8192 个,否则一个插槽里至少会有两个委员会。

这里重点讲一下信标链中的委员会:为信标链服务的验证者们。一个信标链委员会被伪随机得分配到一个分片上,用于将该分片交联至信标链。信标链委员会并不是固定的,会随着每一个区块而改变。

仅仅只构造分片区块的分片链委员会将会在后面再讨论。分片链验证者只构建区块而不与信标链通信是可以的。但是,如果要与其他分片链通信,那么必须依赖于信标链委员会来进行交联。

5

上图描述了三个插槽中发生的状况。在第一个插槽里,一个被提议的区块由委员会 A 中的两个验证者投票,其中的一个掉线。然后第一个插槽中的证明和区块会被广播,其他的验证者将会接收。在第二个插槽里,一个区块被提议出来,但是委员会 B 中的一个验证者并没有看到,因此它对第一个插槽中的区块投出了一票证明。注意,这里的行为与刚才委员会 A 的掉线验证者是不同的。向投标链的区块头投出证明的过程被称为 LMD GHOST 投票。在第三个插槽里,委员会 C 中的所有的验证者都遵循 LMD GHOST 分叉选择规则,独立地为同一个提议区块投出了证明。

在一次轮回中,一个验证者只能在一个委员会中。如果全网有超过 8192 个验证者,那么意味着每个插槽将会拥有超过一个委员会。所有的委员会大小都相同,并且至少有 128 个验证者。当全网验证者数量少于 4096 时,由于每一个委员会中分配到的验证者数量会少于 128 ,网络的完全性可能会下降。

委员会:关键

在每个轮回中,验证者会被均分到各个插槽中,然后组成合适数量的委员会。
该插槽中的所有验证者都要向信标链头投出证明。插槽中的每一个委员会,都会尝试将改分片交联。洗牌算法(shuffling algorithm)会根据验证者调整每个委员会能分配到的验证者,且最少有 128 个。

举例来说,假设全网有 16384 个验证者。那么每个插槽都会被伪随机得分配到 512 个验证者。第一个插槽中的 512 个验证者会被分成 4 个委员会,然后伪随机地派往各个分片,假设这 4 个委员会被派到了 33,55,22,11 这四个分片上。这 512 个验证者都会向第一个插槽执行一次 LMD GHOST 投票。某个委员会中的 128 个验证者尝试交联分片 33 。另一个委员会尝试交联 55,另一个尝试交联 22,最后一个尝试交联 11。

对于第二个插槽,也重复同样的流程。512 个验证者分成 4 组被伪随机得派到 4 个分片上。假设是分配 41,20,17,15。这 512 个验证者都会向第二个插槽执行一次 LMD GHOST 投票,投出它们认为的信标头。各自尝试交联 41,20,17,15。

这个轮回中,剩下的插槽也是不断重复这个过程。在轮回结束时,每一个验证者都已经有过一次投票和交联的机会。目前为止,所有的验证者投票都是基于插槽的,而不是基于轮回。这更像是本地政府的投票,而不是国家级的选举。接下来,所有的验证者还需要为轮回的检查点(checkpoint)投票。

信标链检查点

每个轮回中的第一个插槽的区块即是检查点。如果这个插槽中没有区块,那么最向前比邻的区块就会成为检查点。所以每一个轮回总会有一个检查点。且一个区块可能会成为多个轮回的检查点。

6

由于第 65 个插槽到第 128 个插槽之间是空的。第二个轮回的检查点本应是第 128 个插槽上的区块。由于该插槽是空的,所以检查点成了第 64 个插槽上的区块。第三个轮回的情况也类似,由于第 192 个插槽为空,第 180 个插槽上的区块成为了第三个轮回的检查点。

在一些文献中,会将检查点成为轮回边界区块(Epoch boundary blocks),它们是同义词。

当一个验证者进行 LMD GHOST 投票时,它也同时会对当前的轮回的检查点进行投票,该检查点也成为目标(target)。这个投票被成为是一个 Caper FFG 投票,而且投票中还会包含再包含之前的一个检查点,成为源头(source)。在上图中,第一个轮回中的验证者会将创世块作为源头,将第 64 个插槽做的区块作为目标。第二个轮回中,同样的验证者会作出同样的投票。只有在被分配到某个插槽上的验证者,会对该插槽投出一个 LMD GHOST 投票,但是,所有的验证者都会对同一个轮回投出 FFG 投票。

绝大多数(Supermajority)

当一个投票背后的所支持的验证者的余额超过总余额的 ⅔ 时,这意味着已经产生绝大多数(supermajority)。简单来说,有三个活跃的验证者,两个验证者有 8 个以太币的余额,另一个验证者有 32 个以太币的余额。那么当那个有 32 个以太币余额的验证者投出票后,已经产生了绝大多数,剩下两个验证者的意见已经不再需要。

最终确定性

当一个轮回结束时,它的检查点投票产生了 ⅔ 绝大多数,那么该检查点就已经是证明(justified)了的。

如果一个检查点 B 被证明,然后它的下一个检查点也被证明,那么检查点 B 就已经被最终确定(finalized)。所以,一个检查点在两个轮回后被最终确认,即 12.8 分钟。

平均来讲,一个用户的交易会在一个轮回中的某个靠近中间的区块。这意味着还有半个轮回才会达到下一个检查点,所以这个交易的最终确定时间为 2.5 个轮回:16 分钟。理想情况下,超过 ⅔ 的交易会在下下轮回的 22 个插槽被投票证明。所以,交易的最终确认时间平均在 14 分钟(16 + 32 + 22 插槽)。客户端需自行确认自己是否需要最终最终确认性。

7

为了简单起见,我们假设所有的验证者都有相同的余额。

在信标链头发生了什么

在第 96 个插槽,最后一个边界区块被提议,该区块中还包含了对轮回 2 的检查点证明。当轮回 2 的检查点证明投票达到绝大多数一致时,该轮回的检查点得到证明,同时意味着轮回 1 检查点得到了最终性确认,并且第 32 个插槽之前的所有区块也同时有了最终确认性。当在每个边界区块里提议最终确认性,能被确认最终确认性的区块数量,理论上无限的,可以从创世块一直到当前头。

在信标区块第 1 个插槽到第 32 个插槽间的所有交联,也使得分片链得到了最终一致性。换句话说,当在信标区块中交联的插槽得到最终确认时,分片上的对应区块也得到了最终确认。交联本身不足以使一个分片被最终确定,但是对分片的分叉选择有帮助。

从创世区块到信标链头发生了什么

同样以上图为例,我们看看从创世区块开始会发生什么。所有的提议者一共为第 1 个插槽到第 63 个插槽提议了区块,然后它们出现在了链上。对于在轮回 1 中的所有区块,它们的检查点(第 32 个插槽中的区块)累积了来自 55% 的验证者的证明投票。然后,第 64 个插槽上的区块被提议,并且它包含了轮回 1 的检查点的证明。现在,有 70% 的验证者投票证明了轮回 1 的检查点:因此轮回 1 已经被证明(justified)。然后轮回 2 检查点 (第 64 个插槽)上的区块为轮回 2 没有累积到 ⅔ 绝大多数。所以在第 96 个插槽的区块会包含第 2 个轮回的检查点的投票证明。这会导致第 2 个轮回的检查点达到 ⅔ 绝大多数,并且该轮回被证明。第 2 个轮回被证明意味着包含第 1 个轮回以及之前的区块都有了最终确认性。

现在是另一种可能的场景,只考虑到轮回 1 之前的情况。在第 2 个轮回的检查点被提议之前,第 1 个轮回检查点已经包含了 ⅔ 绝大多数。例如,在第 54 个插槽的区块被提议时,第 32 个插槽上的检查点已经达到了 ⅔ 绝大多数。这这种情况下,轮回 1 的检查点是可以在轮回 2 之前被证明的。检查点可以在当前轮回被证明,但是必须至少在之后的下一个轮回才能被最终确定。

当网络拥堵,网络分裂或者存在网络攻击时,一个证明可以会最终确定多个之前轮回的区块。这些场景在 Gasper 论文有讨论。

对于分片和用户来说,能够获取以太坊区块链上的交易的最终确认性是必要的。最终确认性减少了跨分片通信的复杂度。如果没有最终确认性,分片内和跨分片通信时的频繁区块重组,体验将是非常不好的。

证明:深入了解

一次证明包含了一个 LMD GHOST 投票和一个 FFG 投票。理想情况下,每次轮回所有的验证者都会投出一次证明。每次轮回中验证者有 32 个插槽的时机可以投票上链。在单个轮回中,可能会存在单个验证者的两个投票(译者注:此处应该是包含了对前一个轮回的投票)。当验证在这被分配给它的插槽上投票时,它会被奖励最多。另外,对于秘密领导选举的研究,也旨在降低攻击和贿赂提议者的风险。

在技术实现优化上,一个单独的聚合签名(aggregate signature)可以包含委员会内所有投票的签名。当委员会中一部分投票者的 LMD GHOST 和 FFG 投票相同时,这些投票签名可以被聚合起来。

质押奖惩

我们将简单讨论验证者激励相关的六个话题:

  1. 证明者奖励
  2. 证明者惩罚
  3. 质押者独有的风险
  4. 罚没(slashings)和吹哨者奖励
  5. 提议区块奖励
  6. 不作为(inactivity)惩罚

  7. 如果验证者投出了绝大多数其他验证者都同意的证明(LGM GHOST 和 FFG 投票),那么它就会得到奖励。在阶段 1 时,验证者也可以通过交联区块获得奖励。奖励会在最终性被确认时随之确定。

  8. 另一方面,如果验证者没有投票,或者投票的区块不是最终性确认的那个,就会有惩罚。

  9. 在阐述其他一些不常见的奖惩场景之前,你也许也想了解成为质押者的风险。作为一个质押者,同时会有接受奖励和收到惩罚的风险,它们是对应的。例如,例如一名验证者可以通过投票得到 10% 的收益,另一个(诚实)验证者在最差的表现下,也可能受到 7.5% 的惩罚。一个经常掉线,并且经常为没有最终确认的区块投票的验证者,可能会损失 ¾ 的质押金。对于一年 365 天来说,有几天或几周离线并不会有特别大的惩罚:离线 36 天目前大约会损失 0.75% 。

  10. 罚没是至少 0.5 个以太币,至多可以没收验证者所有质押金的惩罚。一个诚实的,安全的验证者不会因其他恶意验证者的行为而受到罚没。当验证者受到一次罚没时,至少会损失余额的 1/32 ,并且会被停止参与工作。当一个验证者在 8192 个轮回中保持离线时,就会受到罚没惩罚。基于当时被罚没的验证者数量,还会受到额外的惩罚,公式是:验证者余额 * 3 * 同时被罚没的验证者数量。也就是说,如果 1/3 的验证者同时受到罚没,那么验证者们会失去所有质押。对罚没行为举报成功的验证者,将会受到吹哨者奖励。

  11. 当提议者提出的区块被最终确认时,提议者会收到客观的奖励。一个总是在线且稳定完成工作的验证者,可以得到大约 1/8 的额外奖励(基于总奖励)。当一个罚没出现时,提议者可以通过将罚没证据打包进区块来得到小奖励。在以太坊 2.0 的阶段 0 ,所有的吹哨者奖励都会给予证据区块的提议者。

  12. 以太坊 2.0 是一个有着许多机制的系统,并且机制之间有其联系。奖励和惩罚机制联系起来,就肯能会导致不活跃泄露(inactivity leak)惩罚。和上文第三条的惩罚相比,这种惩罚是罕见的。理论上,如果有超过 4 个轮回没有产生最终确定性,那么验证者的不活跃惩罚将会指数级增长,指导下一个检查点被最终确认为止。不活跃惩罚保证了以下收益:如果 50% 的验证者掉线了,区块会在 18 天重新开始最终确认。这种泄露机制确保了有问题的验证者加速退出。在不活跃泄露期间,投票奖励为零,但是提议和吹哨奖励照旧。

罚没

有三种验证者可能会被罚没的条件。重复提议(double proposal),FFG 环绕投票(FFG surround vote),FFG 重复投票(FFG double vote)。

重复提议是指一个提议者在它被分配到插槽中提议了超过一个区块。

FFG 环绕投票是指当 FFG 投票包含或被包含在验证者自己之前已经投出的票中。以下两个例子中,验证者都先在轮回 5 中,以第 32 个插槽为源头,已第 128 个插槽为目标,作出了投票:

  • 该验证者若在轮回 6 中提出的 FFG 投票是以第 64 个插槽为源头,第 96 个插槽为目标,那么就是被包含
  • 该验证者若在轮回 6 中提出的 FFG 投票是以第 0 个插槽为源头,第 160 个插槽为目标,那么就是包含

FFG 重复投票是指,同一个验证者的两次 FFG 投票都包含了同一个插槽为目标/源头。这在链分叉时存在可能。

8

上图中的蓝色箭头表示两次 FFG 投票,左侧以第 128 个插槽为目标,右侧也一样。这样一来,该验证者就进行了一次 FFG 重复投票,这是一次罚没行为。

以下例子为源头相同:

9

在上方箭头中,轮回 1 的检查点是”第 64 个区块“。下方箭头在轮回 1 的检查点是“第 63 个区块”(因为在下面的箭头那边,第 64 个插槽是空的)。所以对于在轮回 0 角度来看,它们的源头是一样的。

这类罚没的初心是希望验证者尽量不要进行链分叉。

一个吹哨验证者,需要提供另一个问题验证者冲突投票的证明。在大量的投票中寻找到冲突投票,对于算法和数据结构来说,都是一种挑战。

完全受掌控的验证者是可以避免被罚没的:它仅需记住它投出过的票。一个诚实的验证者不会因其他验证者的行为而受罚没。只要一个验证者没有签署冲突的证明和提议,它就不会被罚没。

一个验证者可以同时连接多个信标链,用于降低掉线率,增强信任以及抵御 DOS 攻击。如果设置了多个信标链,验证者客户端需要注意不要重复签发消息。

信标链验证者的激活和生命周期

每一个验证者需要 32 个以太币来进行激活。当一个用户向以太坊主网质押合约质押了 32 个以太币后,将会激活一个验证者。

当验证者的余额少于 16 个以太币时,信标链会让这个验证者停止工作。在以太坊 2.0 阶段 0 之后,停止工作后剩余的质押可以被提现。

验证者在服务了 2048 个轮回(大约 9 天)后,也可以“自愿退出”。

当验证者退出时(不论自愿还是被强制停止),都会有 4 个轮回的延迟,质押金之后才可以提现。在这 4 个轮候中,这些验证者如果作恶也会被惩罚。一个诚实节点的盈利余额可以在 27 小时左右后提现,而被罚没过的节点需要等待 8192 个轮回(大约 36 天)。

Further technical details are described in A note on Ethereum 2.0 phase 0 validator lifecycle including this flowchart:
以太坊 2.0 阶段 0 验证者生命周期备忘中,包含了更多细节:

10

上述这些机制限制了一个轮回中能够激活和退出的验证者的数量上限,以防止大量的验证者在短时间内更替。这样可以防止短时间内加入大量恶意验证者。

另外,信标链上还有一个有效余额的概念,它的变化会比验证者余额慢,并且支持技术上的优化。

总结

在每个轮回,验证者被均分到每个插槽中,并且别分为数量合适的委员会。一个验证者只会被分配到一个插槽和一个委员会中,然后:

  • 在每个轮回,所有的验证者都会尝试给同一个检查点做最终确认:FFG 投票
  • 所有被分配到插槽里的验证者都会尝试对同一个信标链头投票:LMD GHOST 投票
  • 所有被分配到委员会的验证者,都会尝试交联某个特定的分片

采取最优的行为的验证者会收到最多的奖励。

激活信标链至少需要 16384 个创世验证者。验证者的数量可能会因为罚没或者自愿退出而减少,但是同时也可能会进入更多的新质押者。在以太坊 2.0 的阶段 1 之后,预期会有越来越多的验证者进入到网络中。信标链需要至少 262144 个验证者(大约质押 800 万以太币)来使 64 分片不断交联。

目前世界上还没有一个去中心化的系统如此扩容过。如果你对以太坊 2.0 有深入了解的兴趣,可以参阅这个文档。文档中包含了对信标链的详述,关键参考资源的链接,以及可能会遇到的一些边际情况和问题。目前,最亟待完善的部分是 P2P 网络。有志之士欢迎到 ethresear.ch 或 Ethereum Magician 论坛参与建设和挑战

原文链接

https://ethos.dev/beacon-chain/

[译]对于 zk-SNARKs 运行的简介

在过去十年中,普适的简洁零知识证明或许是密码学领域最有影响力的发展方向之一,通常简称为 zk-SNARKs(zero knowledge succinct arguments of knowledge)。zk-SNARKs 可以让你为执行的计算生成一些证明(proof),虽然这些证明的生成可能会耗费非常多的算力,但是却可以被很快地验证。并且这些证明还拥有“零知识”的特性,即证明中会隐藏计算中的输入信息。

举个例子,你可以给出一个关于你确实知道某个密码数字的证明:你会把这个数字加到字符 cow 后面,然后执行 100 万次 SHA256 哈希,最终结果会以 0x57d00485aa 开头。在 zk-SNARKs 的应用场景里,验证者可以以远比执行 100 万次哈希快的时间验证你是否确实知道你所说的密码数字,并且该数字不会暴露给验证者。

在区块链中,zk-SNARKs 有两个非常有用的应用场景:

  • 可扩展性(scalability):如果一个区块需要花很多时间才能被验证,那么某人可以预先为其生成证明,然后其他人只需要快速地验证生成的证明即可
  • 隐私性(Privacy):你可以在隐藏具体收到资产的收款路径的情况下,声明你的确拥有某些资产

不过 zk-SNARKs 是非常复杂的。在 2014 - 2017 年间,它还仅仅只是被称为“魔法数学(moon math)”。不过好消息是,此后随着人们的研究越来越深,它的协议也被优化得越来越简单。这篇文章将会在只要求读者拥有中等水平的数学知识的前提下,简单叙述 zk-SNARKs 是如何工作的。

我们将重点关注可扩展性方便。在解决了可扩展性的问题后,隐私性的问题也会跟着迎刃而解,我们将会在文章的最后再讨论隐私性。

为什么 zk-SNARKs “必须”是复杂的

让我们回到刚才的例子:我们有一个密码(cow + 密码数字),我们将其执行一次 SHA256 ,然后将哈希结果再哈希 99,999,999 次,得到了最终结果,记录下起始的哈希。计算量非常之大。

一个“简洁的(succinct)”证明意味着:随着生成证明的计算量不断增大,验证这个证明所需的计算量只会相对缓慢增大。所以,如果我们想要生成一个“简洁的“证明,那么我们肯定不能要求验证者去做上述同样次数的哈希。所以验证者应该只需要窥探到完整计算的一部分,而不是所有步骤。

一个能自然而然想到的方法就是随机抽样验证:我们从 100 万次哈希中抽样出 500 次,然后验证哈希结果,如果都是正确的话,那么我就假设其余的计算都是正确的。

通过 Fiat-Shamir 变换,上述过程可以变成一个非交互式(non-interactive)的证明:验证者提供计算结果的默克尔树根,基于这颗默克尔树,伪随机地(pseudorandomly)选择 500 个索引值(抽样出其中 500 次计算),然后要求提供结果默克尔树中,这 500 个索引值对应的默克尔证明。其中的关键点是,证明者在给出默克尔树根前,不能够预先知道抽样的索引值。如果证明者在给出默克尔树根后还想要进行欺诈,那么改变默克尔树中的叶子值的话,提交的默克尔树根就会对应不上。

不幸的是,这样简单的进行随机抽样检查计算过程,有一个致命的缺陷:这样的计算本质上是脆弱的。如果欺诈者在证明的计算过程中修改了一个比特,那么一开始就会生成一个完全不同的结果(译者注:在上述例子中,就是一开始就会给出一个完全不同的默克尔树根)。随机抽样的验证者是大概率验证不出的(译者注:例如欺诈者只修改一百万步哈希计算中的一步的计算结果,那么随机抽样 500 次将很难命中,如下图所示)。

1

这正是 zk-SNARKs 协议需要解决的问题之一:如何让一个验证者在不验证所有计算步骤的前提下,验证每一步计算都是正确的。

多项式

多项式是拥有如下格式的一种特殊代数表达式:

2

是有限个 c * x^k 的累加。

多项式包含许多特性。不过此处我们仅关心其中一种:多项式可以在一个数学表达式中包含无限的信息(因为多项式中的累加项是无限的)。例如上述的第四个多项式例子中,包含了 816 个 tau) ,并且如果需要包含更多,也是能很轻松做到的。

更进一步,一个多项式之间的等式,可以代表无限多个对应数字的等式。例如,等式:A(x) + B(x) = C(x) 。如果这个多项式等式成立,那么以下等式也同样成立:

3

同样也可以带入到坐标系中。你可以把所有待检查的数字都组装进一个多项式中。举个例子,你想要检查:

  • 12 + 1 = 13
  • 10 + 8 = 18
  • 15 + 8 = 23
  • 15 + 13 = 28

你可以使用拉格朗日插值法将一个点值表示的多项式,例如 A(x) 在 (0, 1, 2, 3) 处值为 (12, 10, 15, 15) ,B(x) 在 (0, 1, 2, 3) 处值为 (1, 8, 8, 13) ,转换为系数形式,具体表示如下:

4

这三个多项式等式是完全符合上述图(3)等式的。

多项式之间的比较

你可以使用同一个多项式,来检查多项式在连续输入值之间输出结果的关系。例如,你想检查的是:对于一个多项式 F ,x 取值范围在整数 {0,1,…98} ,多项式满足 F(x + 2) = F(x + 1) + F(x) (所以如果 F(0) = F(1) = 1 ,那么 F(100) 就是第 100 个斐波那契数)。

对于给出的多项式来说,由于 x 的取值可能不在 {0,1,…98} 之间,那么 F(x + 2) - F(x + 1) - F(x) 可能也就不一定为零。所以,我们需要更进一步。一般来说,如果一个多项式 P 在 S = {x1, x2, … xn} 处等于零,那么它就可以被表示为 P(x) = Z(x) H(x) ,其中 Z(x) = (x - x1) (x - x2) …. (x - xn) ,并且 H(x) 也是一个多项式。换句话说,这个多项式可以表示成,在于其为零值的点的 (x - xn) 的乘法累计结果与另一个多项式的乘积。

对于多项式长除法(long division)有一个很好的推论:因式定理。我们知道,当我们将 P(x) 除以 Z(x) 时,我们会得到一个商 Q(x) 和一个余数 R(x),即 P(x) = Z(x) * Q(x) + R(x),此处的 R(x)(由于是余数)一定是比 Z(x)(由于是被除数)小的。由于我们知道 P 在取值范围 S 上等于 0 ,所以在取值范围 S 上,R(x) 也必须等于 0 。所以在取值范围 S 处,Q(x) = H(x) 。

回到我们上述的满足斐波那契数的多项式 F 上,那么我可以说服你,我提供的 F 确实是满足的条件的,如果在 P(x) = F(x + 2) - F(x + 1) - F(x) ,在我提供的以下 H(x) 和 Z(x) 等式下,为零:

5

至此为止,我们把一个有 100 步的计算(即需要计算出第 100 个斐波那契数)组装进入了一个多项式等式。所以基于这个技术,你可以将包含任意大数字的任意步骤计算放入多项式中。

所以,有比逐个检查因子更快的验证方法吗?

多项式承诺

答案就是:多项式承诺。我们可以将多项式承诺理解为多项式的“哈希”。你可以通过检查它们“哈希”间的等式,来检查两个多项式是否相等。不同的多项式承诺类型,会提供不同的可检查等式类型。

对于大多数多项式承诺类型,你都可以通过它们进行如下检查(com(P) 即指多项式 P 的承诺):

  • 相加:给定 com(P),com(Q),和 com(R),检查是否 P + Q = R
  • 相乘:给定 com(P),com(Q),和 com(R),检查是否 P * Q = R
  • 某一点的值:给定 com(P),w,z,和一个补充证明 Q,验证 P(w) = z

我们需要将上述这些等式特性糅合在一起使用。如果你可以验证相加或相乘,那么你就可以验证给定点的值:P(w) = z ,你可以构造 Q(x) = (P(x) - z) / (x - w) ,然后检查 Q(x) (x - w) + z = P(x) 。如果 Q(x) 存在,那么 P(x) - z = Q(x) (x - w) ,这就意味着 P(x) 在 w 处 等于 z 。

Schwartz-Zippel 引理表示, 如果一些多项式等式在某些随机点验证结果都是真,那么几乎在所有点都会是真。所以,我们可以使用如下的交互来验证 P(x + 2) - P(x + 1) - P(x) = Z(x) * H(x) :

6

根据上文所表述的,我们可以通过 Fiat-Shamir 变换来让上述过程变成非交互式:证明者自己通过 r = hash(com(P), com(H)) 计算出 r (hash 可以是任意哈希函数),所以当证明者在选择 PH 时,他并不知道 r (即是通过哈希生成的“随机值”),所以也没办法通过“挑选” PH 使之符合某个 r

小结

  • zk-SNARKs 是困难的,因为它允许验证者无需重放计算的每一步,而可以验证一个拥有百万次步骤的计算结果
  • 我们将计算编码入了一个多项式
  • 一个多项式可以包含任意多的信息,并且一个多项式表达式(例如 P(x + 2) - P(x + 1) - P(x) = Z(x) * H(x))可以表示任意数量的等式
  • 如果你验证了多项式之间的等式,那么你就隐式地验证了所有数字的等式(将其带入 x 坐标系)
  • 我们使用多项式承诺,来作为多项式的一种特殊“哈希”,这样一来,即使原本的多项式很大,我们也可以在很短的时间内验证它们之间的等式

多项式承诺是如何工作的

目前主要有三种多项式承诺的主流方式:bulletproofs, Kate 和 FRI。

简单描述多项式承诺的工作方式

在我观念中,其中最完全容易理解的是 FRI (如果你把椭圆曲线对当作“黑盒”的话,Kate 也会相对比较容易理解)。

以下是 FRI 是如何工作的简化版本(真实的协议中,会有许多技巧和优化,此处都会省去)。假设有一个阶数小于 n 的多项式 P 。P 的多项式承诺,就是其在一系列点上(例如 {0, 1, 2…8n-1},尽管这些并不是最优系数)计算结果作为叶子的默克尔树的树根。现在,我们需要添加一些额外的东西来证明这一系列叶子计算结果的确来自于一个阶数小于 n 的多项式。

我们假设多项式 Q 只包含多项式 P 中的偶数位因子,多项式 R 只包含多项式 P 中的奇数位因子。那么如果 P(x) = x^4 + 4 x^3 + 6 x^2 + 4 x + 1,那么 Q(x) = x^2 + 6 x + 1 ,R(x) = 4 * x + 4 (注意分解的多项式中,只有因子被继承了,阶数会被重新更新,范围是 (0…n/2])。

所以 P(x) = Q(x^2) + x * R(x^2)。

我们会要求证明者提供 Q(x) 与 R(x) 的默克尔证明。然后生成一个随机数 r ,并且要求证明者提供一个“随机线性组合(random linear combination)”:S(x) = Q(x) + r * R(x) 。

基于之前提供的默克尔树根作为种子,我们伪随机地生成一个大的索引集合。然后要求证明者提供这些索引在 P,Q,R 和 S 中值得默克尔证明。对于这些索引坐标,我们检查:

  • P(x) 实际等于 Q(x^2) + x * R(x^2)
  • S(x) 实际等于 Q(x) + r * R(x)

如果我们做足够多次的检查,那么我们会相信,可能就最多 1% 的概率,S(x) 的提供值可能会和“预期”值不同。

值得注意的是,Q 与 R 的最高阶都小于 n/2 。由于多项式 S 是 Q 和 R 的一个线性组合,所以 S 的阶数也小于 n/2 。反过来说,如果我们能证明 S 的阶数小于 n/2 ,并且随机选择的 r 阻止了证明者可以选择 Q 和 R 来隐藏最高阶的因子。所以 Q 和 R 的最高阶也必须小于 n/2 ,然后由于 P(x) = Q(x^2) + x * R(x^2) ,所以 P 的最高阶也小于 n 。

所以,我们使用 S 继续重复上文的交互式游戏,不断的“减小”我们关心的多项式的阶数,直至它的阶数能被直接检查:

7

在上述例子中,Bob 仅仅是一个“抽象”,用于演示协议。现实中,Alice 会仅靠自己生成完整的证明,并且我们使用 Fiat-Shamir 变换来防止她欺诈:我们根据截至该点为止生成的证明的哈希,来随机选择采样点。

所以一个简化版的 FRI 承诺将会包含:

  • P 执行结果的默克尔树根
  • Q,R,S1 执行结果的默克尔树根
  • 随机选择 P,Q,R,S1 的计算过程默克尔树中的分支,用以检查 S1 确实是从 P 衍生而来
  • 重复前两步,直至得到的 Sk 阶数足够小
  • 直接检查 Sk 的完整默克尔树

上述过程的每一步,都会产生一点“误差”,但是当你把这些步骤放在一起时,误差已经足够低到你可以证明 P(x) 与另一个阶数小于 n 的多项式存在 80% 的相似。这在我们的使用场景中,已经足够了:如果你想在 zk-SNARKs 中作弊,你需要使用一个伪造值生成多项式承诺,经过上述过程后,最终的记过将会很不同。

另外,你可以在对数时间内检查 FRI 承诺中的所有数字,对于很大的多项式来说,承诺的大小会比本体小很多。

在检查多项式承诺之间的等式时(例如,A(x) + B(x) = C(x) ,并且对 A,B,C 进行多项式承诺),仅需随机选择一系列的索引,然后要求验证者提供默克尔证明。

上述的简化协议,在执行效率上是低下的,有一系列的代数技巧可以用于提高效百倍效率,如果你想要在区块链交易验证中使用,那么你应该去了解它们。例如,当你使用某些技巧来选择运算点时,Q 和 R 都不是必要的,你可以从 P 的计算过程中重组出 Q 和 R 的计算过程。

有限域

在前文中,有一个隐藏的假设:一个多项式的每一步独立的“计算”都是小的。如果我们面对一个很大的多项式,这个假设显然就不成立了。例如我们最早的一个多项式例子之一:628 x^271 + 318 x^270 + 530 * x^269 +…69x + 381,然后计算 x = 1000 处的值,计算量是非常大的。在实际的实现中,这些计算都不会是这些真实的数字进行“常规”的运算。而是会使用取模运算。

We redefine all of our arithmetic operations as follows. We pick some prime “modulus” p. The % operator means “take the remainder of”: , , etc (note that the answer is always non-negative, so for example ). We redefine
我们将我们需要进行的所有计算重新按如下定义。我们取一些素数“模” P ,% 符号表示取模:15 % 7 = 1,53 % 10 = 3 等等。注意,结果一定是非负的(-1 % 10 = 9)。我们重新定义:

8

如果 p = 7 ,那么:

9

分配率也依然有效:(2 + 4) 3 与 2 3 + 4 3 结果都为 4 。甚至 (a^2 - b^2) = (a - b) (a + b) 也依然为真。

除法是最复杂的。由于我们想要取模的结果是整数,而整数之间相除的结果经常不为整数。我们使用了费马小定理来绕过这个问题:对于任何非零的 x < p ,x^(p - 1) % p = 1。这意味着,对于 x^(p - 2),再乘以一次 x ,那么取模结果就会为 1 。所以我们可以说 x^(p-2) (该数是一个整数)的取模结果为 1/x 。你也可以通过扩展欧几里得算法来实现一个更快的除法取模操作,这里有这个算法的 python 实现

10

通过取模运算,我们创建一套新的计算系统。并且这与传统数学一样,都是自洽(self-consistent)的。所以我们可以像讨论传统数学中的多项式计算一样,讨论这套新系统中的计算。加密学领域的人喜欢使用基于取模运算的数学(更广泛的说,“有限域”),因为任何取模运算的结果值,都是有上限的。无论你做什么,结果都不会“逃出”一定的集合。在有限域中,即使运算一个 100 万阶的多项式,结果同样也不会超出上限。

结合到多项式运算中

我们想证明:对于多项式 P ,0 <= P(n) <= 2^64 ,同时不泄露 P(n) 的具体值。这种场景在区块链交易中很常见,比如你想证明经过一笔交易后,你的余额是非负的,但是你不想透露具体的余额。

我们可以构建一个包含如下声明的证明(简单起见假设 n = 64):

  • P(0) = 0
  • P(x + 1) = P(x) * 2 + R(x) ,在 x 属于 {0…63} 中
  • R(x) 属于 {0,1} ,在 x 属于 {0…63} 中

后两个声明可以通过“纯”多项式来表示:

11

随着 P(i) 的执行,结果集合将不会不断增大。如果 P(4) = 13 ,那么到 4 时,结果集合就是 {0, 1, 3, 6, 13}。在二进制中,1 是 1,3 是 11,6 是 110,13 是 1101。所以,P(x + 1) = P(x) * 2 + R(x) 中,只要 R(x) 属于 {0, 1},结果就会不断地往最后添加 1 比特。任何在 0 <= x <= 2^64 的数通过上述的 64 步构建出来,超过这个范围则不行。

隐私

一个问题是,为什么我们知道 P(x) 和 R(x) 的多项式承诺,不会“泄露”有关 P(64) 的信息呢?

好消息是:这些证明都是小型的证明,但是都对应着一些大数据量和复杂的计算。通常,这些证明的体量都没有大到能够泄露任何有用的数据。但是我们有办法把泄露的可能减低为 0 吗?幸运的是,我们可以。

一个常用的技巧是在多项式中加入一些“软糖因子(fudge factors)”。当我们选择 P 时,会在多项式加入一些小的 Z(x) :P’(x) = P(x) + Z(x) * E(x) ,E(x) 是一些随机值。这么做并不会影响声明的正确性,但是这会为多项式承诺添加一些额外的噪音。在 FRI 中,上述选取的随机值,不能在计算将要发生的点上(例如 {0…64})。

总结

  • 三个最常见的多项式承诺类型有:FRI,Kate 和 bulletproofs
  • 如果将椭圆曲线对视为黑盒的话,Kate 是其中概念最简单的
  • FRI 依赖于哈希,所以也很酷。它通过不断地给多项式降维,然后给出一些抽样值,用以检查各计算步骤结果中的默克尔证明
  • 通过在有限域中的计算,控制了计算结果的上限
  • 多项式承诺会天然的保护多项式中的信息,因为生产的证明比实际的多项式小得多,所以并不会泄露任何有价值的信息。我们甚至还可以通过添加一些随机噪音,将信息泄露的风险降低为 0

原文链接

https://vitalik.ca/general/2021/01/26/snarks.html

[译]理解 PLONK

最近,Ariel Gabizon,Zac Williamson 和 Oana Ciobotaru 公布了一个新的普遍用途的零知识证明算法 PLONK ,全称为普遍用途的非交互式知识论证的拉格朗日基排列(Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge)。虽然普遍用途的零知识证明协议的进步与研究已经进行持续许多年,PLONK(以及早先更复杂 SONIC 和最近的 Marlin)为这类证明带来了在可用性上的可观进步。

第一个进步是,PLONK 虽然像 Zcash 的 SNARKs 一样,也要求一个类似的初始可信设置(trusted setup),但是 PLONK 的设置是普适且可更新(universal and updateable)的。这意味着两点,首先,无需再为每一个程序单独配置初始可信设置,对于任意程序都可以使用同一个设置(在设置时会有最大上限)。其次是允许多方一同参与可信设置,只要其中有任意一方是诚实的,那么可信设置就是安全的。这个过程是连续的:第一方参与,然后第二方,第三方…总共的参与方不需要提前预知,新的参与方仅需把自己添加到末尾。在实践环境中,这使得拥有大量参与者的初始可行设置过程变得更加安全。

第二个进步依赖于“奇特的密码学”,即多项式承诺。PLONK 使用了基于椭圆曲线对的 Kate 承诺。承诺是可替换的,你也可以替换为例如 FRI 承诺(会将 PLONK 变成某一种 STARK)或者 DARK 承诺(基于隐阶组(hidden-order groups))。这意味着,基于不同的承诺选择,PLONK 可以在证明大小与安全性上进行调整。

1

这意味着,对于不同的证明大小与安全性假设(或者是对于问题有不同立场的开发者),都仍可以共享大部分相同的“算术”工具(即把一个程序转换成一组多项式,然后通过多项式承诺检验它们)。如果这项被广泛接受,那么由于上述共享大量“算术”工具的特征,我们可以预期 PLONK 将会快速优化与发展。

PLONK 是如何工作的

让我们开始解释 PLONK 是如何工作的,我们先聚焦于多项式等式的形式,随后再解释这些等式是如何被验证的。PLONK 的一个关键组成部分(正如 QAPs 被运用在 SNARKs 一样),就是需要一个过程,将“有一个特定的程序 P,给我一个输入值 X,会输出一个特定的输出值 Y”,转化为一个“给我一组值,满足一组数学等式”问题。程序 P 可以有很多表示。例如,可以是“输出一个数独的答案”,你可以将 P 设置为一个数独验证器,并放上一些初始化值,然后将 Y 设置为 1 ,然后 X 就是解决这个数独的一个合法输入。这可以通过将 P 表示为一个包含加法门与乘法门,然后线都是值,并且每一个门都是等式的电路来实现(例如,乘法是 x6 = x4 * x7,加法是 x8 = x5 + x9)。

以下是 P(x) = x^3 + x + 5 = 35 (答案为 3) 的电路例子:

2

我们可以为电路标上门与线:

3

在门与线上,我们有两种约束:门约束(连接到相同门的线所对应的等式,例如 a1 * b1 = c1)和复制约束(电路中连接到同一位置的线都相等,例如 a0 = a1 = b1= b2 = a3 或 c0 = a1)。我们将会构建一个基于少量多项式等式的结构化系统,来表示上述两种约束。

在 PLONK 中,这些等式会以如下形式构建(L = 左,R = 右,O = 输出,M = 乘,C = 常量):

4

每一个 Q 值都是一个常量。对于不同的程序,常量和等式的数量都是不同的。所有的小写字母,都是由用户提供的变量:ai 是第 i 个门的左输入,bi 是右输入,ci 是输出。如果是一个加法门,我们设置:

5

将输入常量带入等式,我们可得 ai + bi - ci = 0(即 ai + bi = ci)。如果是一个乘法门,我们设置:

6

如果是一个将 ai 设置为某个常量 x ,我们设置:

7

你也许已经注意到,线的两端,值都是相同的(例如 x),即都等于一个独立的变量。目前为止,我们还没有提出一个门的输出需要等于另一个门的输入(我们称之为“复制约束”),PLONK 当然也实现了复制约束,我们会在稍后提及。现在,我们的问题转变为了:证明者拥有一系列 Xai,Xbi 与 Xci ,它们都可以满足一系列相同形式的等式。所以相比于“为这个程序找到合适的输入”,我们已经有了一个更具象的问题,并且我们随后可以使用数学工具继续“压缩”它。

从线性系统到多项式

如果你阅读过 STARKs 或 QAPs 相关的文章,那么这个章节你或许会觉得比较熟悉,如果你还没阅读过的话,也没有关系。核心观点是,以多项式为一种数学工具,将大量的值封装到一个单一对象中。通常,我们以“系数形式”来表达一个多项式,例如:

8

我们也可以通过“点值形式”来表示一个多项式,例如,上述多项式也可以描述为是一个在 x 为 (0, 1, 2, 3) 处, y 值为 (-2, 1, 0, 1),且度数小于 4 的多项式:

9

下一步,一个拥有多个同样形式方程组的系统,可以被重新解释为一个单一的多项式等式。例如我们有一个方程组系统:

10

让我们定义 4 个多项式等式:L(x) 是一个度数小于 3 ,且在 x 为 (0, 1, 2) 处,y 值为 (2, 1, 8) 的多项式。同样的 x 值,M(x) 的 y 值为 (-1, 4, -1),R(x) 的 y 值为 (3, -5, -1),O(x) 的 y 值为 (8, 5, -2)。这么定义多项式也是完全可以的,后续可以通过拉格朗日插值法将多项式从点值形式转换为系数形式。现在,考虑下面这个等式:

11

在上述公式中,Z(x) 是 (x - 0) (x - 1) (x - 2) 的缩写,是一个在 x 为 (0, 1, 2) 时,y 值为 0 的最简多项式。这个等式的一个解(例如 x1 = 1,x2 = 6,x3 = 4,H(x) = 0)(译者注:带入上述等式后,可得 L(x) + 6 M(x) + 4 R(x) - O(x) = 0 ,这个等式在 L(x),M(x),R(x),O(x) 在 x 为 (0, 1, 2) 处都成立),同样也是上述方程组系统的一个解。有一点值得注意,在上述等式中,H(x) 恰好很方便地为 0 ,但在更复杂的例子中,H(x) 可能为非零。

所以我们知道了我们可以将一组很大的输入数据限制在一个多项式中。不过上述我们用来描述门线约束的例子中, x1, x2 与 x3 ,其实都是变量,在不同的等式中都是不同的,我们可以将变量也转换为多项式:

12

和之前一样,Q 多项式都是从程序生成的已验证参数,a,b,c 多项式都是用户提供的参数。

复制约束

现在,让我们回到电路中线的“连接”问题。目前为止,我们有了一组不同的值来满足一组不同的等式。常量门可以通过将值设置为常量来满足,加法和乘法门可以通过设置所有的非必要线为 0 来满足。为了让问题更具挑战性(并且能更贴切地表达我们最初的电路),我们需要验证“复制约束”:例如 a(5) = c(7),c(10) = c(12) 。这需要一些巧妙的设计。

我们的策略是实现一个“坐标对聚合器(coordinate pair accumulator)”,一个多项式 p(x) 有如下工作原理:首先,假设 X(x) 与 Y(x) 是两个代表了 x 与 y 坐标上一系列点的多项式(例如对于 ((0, -2), (1, 1), (2, 0), (3, 1)),你可以设 X(x) = x,Y(x) = x^3 - 5x^2 + 7x -2)。我们的目标是让 p(x) 代表上述坐标中的所有点。所以,从 p(0) 从 1 开始,p(1) 代表第一个点,p(2) 代表第一、第二个点,以此类推。我们会随机选择两个常量 v1 和 v2,至少在 (0, 1, 2, 3) 域内使用 p(0) = 1 和 p(x + 1) = p(x) (v1 + X(x) + v2 Y(x)) 来构造 p(x) 。

例如,若 v1 = 3,v2 = 2,我们可以得到:

13

我们关心的结果是 p(4) = -240 。现在,我们把 X(x) = x 替换成 X(x) = (2/3) x^3 - 4 x^2 + (19/3) * x (这个多项式在 x 值在 (0, 1, 2, 3) 处的 y 值为 (0, 3, 2, 1))。如果你用这个 X(x) 再次运行上述公式,那么你还是会得到 p(4) = -240 ,这不是巧合(事实上,你可以尝试在一个很大的域里随机选取 v1,v2,这几乎不会发生)。这是因为 Y(1) = Y(3)(译者注:都为 1),所以你将 (1, 1) 和 (3, 1) 的 x 坐标交换后,得到的还是这两个点,并没有改变预设点的集合。所以,我们的聚合器最后得到的结果一致(由于乘法交换律)。

现在,我们学习到了一些用于证明复制约束的基础知识。首先,先考虑一条线的两个值的复制约束(例如 a(1) = a(3))。我们将创造两个坐标对聚合器:在第一个中, X(x) = x,并且 Y(x) = a(x) ,第二个中,依然是 Y(x) = a(x) ,不过其中 X‘(x) 的值为第一个聚合器中 X(x) 值的重新排列。第一个聚合器将会压缩点集合 ((0, a(0)), (1, a(1)), (2, a(2)), (3, a(3)), (4, a(4)) …,第二个聚合器将会压缩点集合 ((0,A(0)), (3, A(1)), (2, A(2)),(1,A(3)), (4,A(4)) …。只有当 a(1) = a(3) 时,聚合器才会输出相同的结果。

为了证明 a,b 与 c 之间的约束,我们采用同样的流程,只不过我们会将三个多项式的所有点都进行“聚合”。我们为 a,b 和 c 都提供 x 坐标中的一段值(例如 Xa(x) = x,Xb(x) = n + x,Xc(x) = 2n + x)。为了证明电路中线两端的复制约束,“新的 X 坐标“可以理解成是上述三个点集切片的组合。如果我们想要证明当 n = 5 时 a(2) = b(4) ,那么 X’(a) 会有定值 01934 ,X‘(b) 会有定值 56782 (注意 9 和 2 的位置调换了,因为 9 表示 b(4) 线)(译者注:索引从 0 开始)。

我们将不会像之前那样仅检查一个方程的聚合器(如之前检查 p(4) = p’(4)),我们将检查三个聚合器的乘积:

14

两侧的三个 p(n) 的乘积,将会聚合 a,b 和 c 中的所有坐标点,这使得我们可以不仅三条线 a,b 和 c 内部的一对复制约束。同样也可以用于检查一线与另一线之间的复制约束(例如 a(2) = b(4))。

汇总

现实中,这些数学计算都不是通过整数的,而是通过素数域。可以参阅这篇文章中的模块化数学部分来了解素数域。此外,出于数学上的原因,最好是用快速傅里叶变换(FFT)来阅读和理解这篇文章。我们将会使用 ω:1,ω,ω^2…ω^n-1 的幂来表示线的索引(其中 ω 是域中的一个高阶单元根(high-order root-of-unity)),而不是整数 x = 0 … n-1 。这些不会在数学层面有什么变化,仅仅是将坐标对聚合器的等式从 p(x + 1) = p(x) (v1 + X(x) + v2 Y(x)) 变为了 p(ω x) = p(x) (v1 + X(x) + v2 Y(x)) ,并且将 x 坐标索引从 0..n-1, n..2n-1, 2n..3n-1 变为了 ω^i,g ω^i 和 g^2 * ω^i (g 为域中一些随机高阶值)。

现在让我们来写些所有需要检验的等式。首先,主体的门约束检查:

15

然后是多项式聚合器状态转化约束(可以将“Z(x) * H(x)”理解为“仅在我们关心的坐标上等于零,在其他坐标上,等于零是非必要的”):

16

随后是多项式聚合器开始、结束约束(复制约束):

17

用户提供的多项式是:

  • 电路线赋值(wire assignments):a(x)、b(x)、c(x)
  • 坐标对聚合器:Pa(x), Pb(x), Pc(x), Pa’(x), Pb’(x), Pc’(x)
  • 商:H(x) 和 H1(x)…H6(x)

证明者和验证者需要提前计算的多项式有:

  • QL(x), QR(x), QO(x), QM(x), QC(x),它们共同代表了电路中的各种门(注意 QC(x) 编码为公共输入,所以它可能在运行时有所变化)
  • 排列多项式 σa(x), σb(x) 和 σc(x) ,它们编码 a,b 和 c 线之间的复制约束

注意,验证者只需要存储这些多项式的多项式承诺(commitments)。之前的等式中,仅需的实际多项式是 Z(x) = (x - 1) (x - ω) … * (x - ω^(n-1)) ,用于表达在这些点上为零。并且幸运的是,ω 通过一些取值,可以让这个多项式变得非常容易计算:一个常用的取值是取一个满足 ω^n = 1 的 ω 。这种情况下,Z(x) = x^n - 1 。

这里有一个细微差别:Pa(ω^(i+1)) 与 Pa(ω^i) 之间的约束,不能够在 ω 的全部幂的取值环上都为真。当当前坐标为 ω^(n-1) 且下一个坐标为 ω^n = 1 时(即回到了聚合器的起始位置),总是为假。为了修复这个问题,我们将约束修改为,要么约束为真,要么 x = ω^(n-1) 。我们可以通过把 x - ω^(n-1) 放进 Z(x) 约束中来做到,这样一来,在这个点的值就为零。

v1,v2 唯一的限制是:用户必须不能在知道 v1,v2 之后,再去选择 a(x)、b(x) 和 c(x) 。我们可以通过从 a(x)、b(x) 和 c(x) 的多项式承诺的哈希来计算 v1,v2,做到这个限制。

目前为止,我们已经把一个程序问题,转化为了一个多项式等式满足问题。PLONK 中还有许多优化,能够允许我们再去掉上述的一部分多项式,但是为了简单起见,这里不再讨论。但是多项式本身(不论是代表程序还是用户输入),目前来说都是很大的。下一个问题是,我们如果绕过这个问题,使得证明变得简短。

多项式承诺

多项式承诺是一个对应多项式的简短“代表”,通过它,不必知晓多项式中的所有数据,也可以验证对应多项式的计算。这意味着,如果有个人给了你一个多项式 P(x) 的承诺 c ,那么就等于能够说服你,对于特定的 z ,P(z) 计算所得出的具体结果。用更数学的表达来说,在一个足够大的域中,如果随机数 z 在某个多项式(于 z 已知前已经确定)上为真,那么整个多项式也是真。例如,如果 P(z) Q(z) + R(z) = S(z) + 5 为真,那么我们就能知道更广义的 P(x) Q(x) + R(x) = S(x) + 5 也是极其可能为真的。所以,我们可以使用多项式承诺来轻松检查上文所有的那些多项式,使用这些多项式对应的承诺,作为输入来生产 z ,代入每个多项式计算出一个新结果,我们边可以用这个新结果来替换原来的多项式了。那么,多项式承诺是如何运作的呢?

上述过程包含了两个部分,首先是一个多项式承诺 P(X) -> c ,和多项式的任意一个点 z(P(z))进行的打开(opening)。目前有很多算法可以用于构建一个多项式承诺,例如 FRI ,还有下面将会提到的 Kate 。为了证明一个打开,有一个简单而通用的减除(subtract-and-divide)技巧:为了证明 P(z) = a,你需证明:

18

也是一个多项式(使用另一个多项式承诺)。这是因为如果商是一个多项式(即除法的结果不是分数),那么 (x - z) 就是 P(x) - a 的一个因子,所以 (P(x) - a)(z) = 0,所以 P(z) = a。还有一个值得注意的普适优化:为了在同一时间证明多个多项式的打开,在提交输出后,对多项式和输出的随机线性组合可以执行减除技巧。

所以,承诺本身是如何工作的?幸运的是,Kate 承诺的算法比 FRI 简单许多。通过初始可信设置,会生成一组椭圆曲线点 G, G s, G s^2 … G s^n 以及 G2 s。其中 G 和 G2 是两个椭圆曲线生成器(generators),s 是一个计算后就会被遗忘的密码(如果是多方生成,只要有一方遗忘了密码,那么这个过程就是安全的)。这些椭圆曲线点会被公开,然后被认为是“证明秘钥(the proving key)”。任何想要创建多项式承诺的人,都需要用到这些点。通过将椭圆曲线点钟的前 d + 1 个点乘以多项式中的响应系数,并将结果累加,就可以得到一个 d 阶多项式的承诺。

注意,这里在无需知道 s (已被遗忘)的情况下,得出了一个有关 s 信息的多项式。例如,x^3 + 2x^2 + 5 将会由 (G s^3) + 2 (G s^2) + 5 G 来表示。我们可以用符号 [P] 来表示以这种方式(即 G P(s))编码的多项式 P 。在使用减除技巧时,你可以通过椭圆曲线配对来验证两个多项式是否符合关系要求:将检查 e([P] - G a, G2) = e([Q], [x] - G2 z) 来作为 P(x) - a = Q(x) (x - z) 的代理检查。

最近也出现来一些其他的多项式承诺算法。一个新的方案成为 DARK (丢番图知识论证(Diophantine arguments of knowledge)),使用了例如类组(class groups)的隐阶组(hidden order groups)来实现了多项式承诺。隐藏组是唯一的,通过使用它们,将会允许你压缩任意大的数字压入组中的元素中,即使数字比组中的元素大得多。从 VDFs 到聚合器再到多项式承诺,都可以基于此来进行构造,另一种算法是子弹证明(bulletproofs),它使用常规的椭圆曲线组,代价是验证所需的时间要长得多。因为多项式承诺比完全零知识证明方案要简单得多,我们可以期望将来会有更多这样的方案被创建出来。

总结

让我们来总结一下。给定一个程序 P ,将其转换为电路后,生产一组如下形式的等式:

19

然后将这组等式转化为单个多项式:

20

然后还需要从电路中生成复制约束,你会生成三个多项式 σa(x),σb(x),σc(x) 用于表示置换线(permuted wire)上的索引。为了生成一个证明,你计算了线上的所有值,然后将它们转换为了三个多项式 a(x),b(x),c(x)。作为置换检查参数的一部分,你还需要计算六个坐标对聚合器(coordinate pair accumulator)多项式。最后,计算辅因子 Hi(x) 。

在多项式之间,还有一组方程需要被检查。你可以通过创建这些多项式的多项式承诺,在一些随机点 z 进行打开,然后在这些打开结果上运行方程,而不是在原始的多项式上。所以证明本身就是一些能被一组方程检查的多项式承诺和打开。

原文链接

https://vitalik.ca/general/2019/09/22/plonk.html

从源码解析为何冷兔预售没有 Gas War

昨日冷兔预售,在成为国产 NFT 之光冲上 OpenSea 时段榜一之外,不知大家是否察觉,整个预售过程,Gas 费并没有明显暴涨:

2022/1/16 Gas

可以看到,整个下午的 Gas Price 在图中并没有明显尖刺。在项目如此之热的情况下,冷兔是如何做到的呢?让我们从它的合约代码来看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// XRC.sol
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/access/Ownable.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";
import "@openzeppelin/contracts/utils/cryptography/ECDSA.sol";
import "./ERC721A.sol";

contract XRC is ERC721A, Ownable, ReentrancyGuard {
using ECDSA for bytes32;

// ...

function presaleMint(
uint256 amount,
string calldata salt,
bytes calldata token
) external payable {
require(status == Status.PreSale, "XRC: Presale is not active.");
require(
tx.origin == msg.sender,
"XRC: contract is not allowed to mint."
);
require(_verify(_hash(salt, msg.sender), token), "XRC: Invalid token.");
require(
numberMinted(msg.sender) + amount <= maxMint,
"XRC: Max mint amount per wallet exceeded."
);
require(
totalSupply() + amount + reserveAmount - tokensReserved <=
collectionSize,
"XRC: Max supply exceeded."
);

_safeMint(msg.sender, amount);
refundIfOver(PRICE * amount);

emit Minted(msg.sender, amount);
}

// ...
}

可以看到,整个合约多重继承了 Ownable,ReentrancyGuard 和 ERC721A 。前两个合约都是来自大家常用的OpenZeppelin,分别用于控制部分关键函数的调用权限和防止重入攻击,而第三个继承的合约: ERC721A ,即是 presaleMint 函数的关键部分 _safeMint(msg.sender, amount); 的实现之处。

其实,ERC721A 也是对 @openzeppelin/IERC721 的一个实现,相比于 OpenZeppelin 自带的实现,优化了单次 mint 时的 Gas 开销。在 5 天前的 Azuki 项目 mint 时,首次使用。我们在 Azuki 的合约中也能看到它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Azuki.sol
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/access/Ownable.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";
import "./ERC721A.sol";
import "@openzeppelin/contracts/utils/Strings.sol";

contract Azuki is Ownable, ERC721A, ReentrancyGuard {
// ...
function publicSaleMint(uint256 quantity, uint256 callerPublicSaleKey)
external
payable
callerIsUser
{
// ...
_safeMint(msg.sender, quantity);
refundIfOver(publicPrice * quantity);
}
}

那么 ERC721A 相比大家常用的 @openzeppelin/ERC721Enumerable ,具体在哪里做了优化呢?让我们对比它们的源码来一探究竟。

Storage 存储空间的优化

我们知道,以太坊中的 storage 存储是昂贵的,并且,在以太坊中,调用不修改合约状态的只读函数(view / pure)是免费的。而在 @openzeppelin/ERC721Enumerable 实现中,为了方便读取 NFT 的所有者信息,做了许多冗余的元数据存储,作为代价,在 mint 函数内,则需要额外的开销来存储这些信息。而 ERC721A 实现则相反,将所占的必须存储压缩到了最小,这样虽然增加了读取时的复杂度,但是读取是免费的。

1
2
3
4
5
6
7
8
9
10
11
abstract contract ERC721Enumerable is ERC721, IERC721Enumerable {
mapping(address => mapping(uint256 => uint256)) private _ownedTokens;

mapping(uint256 => uint256) private _ownedTokensIndex;

uint256[] private _allTokens;

mapping(uint256 => uint256) private _allTokensIndex;

// ...
}
  • _ownedTokens 是钱包地址到另一个 map 的映射,另一个 map 表示用户拥有的第 N 个该 NFT 的 ID 。即 _ownedTokens['addr1'][0] = 201 表示,addr1 这个钱包地址,拥有的第一个该 NFT 的 ID 是 201 。
  • _ownedTokensIndex 保存了该 NFT ID 到用户拥有索引的映射。即 _ownedTokensIndex[201] = 0 表示 ID 为 201 的该 NFT 是所属用户的拥有列表中的第一个。
  • _allTokens 表示了所以被 mint 出来的该 NFT 的 ID 列表。
  • _allTokensIndex 表示了具体某个 ID 的 NFT 在 _allTokens 列表中的位置。

我们可以看到上面四个存储的数据中,有两个(Index)数据都是另两个数据的索引,若读取开销为免费的话,则它们(Index)是冗余的,可以通过遍历来实现同样的效果。

而在 ERC721A 的实现中,的确去除了那两个冗余索引:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
contract ERC721A is
Context,
ERC165,
IERC721,
IERC721Metadata,
IERC721Enumerable
{
struct TokenOwnership {
address addr;
uint64 startTimestamp;
}

struct AddressData {
uint128 balance;
uint128 numberMinted;
}

mapping(uint256 => TokenOwnership) private _ownerships;

mapping(address => AddressData) private _addressData;

// ...
}

可以看到,仅做了 ID => 钱包地址,钱包地址 => 所有数量,这两个映射。

批量 Mint

在 @openzeppelin/ERC721Enumerable 实现中 mint 只支持单个,一次 mint 多个需要 NFT 合约自行通过多次调用来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// ERC721Enumerable 使用过的是 @openzeppelin/ERC721 中的 _safeMint
contract ERC721 is Context, ERC165, IERC721, IERC721Metadata {
// ...
function _safeMint(
address to,
uint256 tokenId,
bytes memory _data
) internal virtual {
_mint(to, tokenId);
require(
_checkOnERC721Received(address(0), to, tokenId, _data),
"ERC721: transfer to non ERC721Receiver implementer"
);
}
// ...
}

这就意味着,如果一次 mint N 个,合约中的元数据会被进行 N 次改写,举个例子,上文中的 _allTokens 会被在尾部进行 N 次 push。而 ERC721A ,则支持批量 Mint ,并且通过其特制的数据结构(后文会细述),只需要对元数据进行一次修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
contract ERC721A is
Context,
ERC165,
IERC721,
IERC721Metadata,
IERC721Enumerable
{
function _safeMint(
address to,
uint256 quantity, // 支持批量 mint
bytes memory _data
) internal {
// ...
}
}

批量 Mint 仅需对元数据进行一次修改

ERC721A 使用的数据结构假设每个用户所 mint 的 ID 是连续的。所以每次批量 mint ,都只会记录一下用户的第一个 mint 出来的该 NFT ID ,以及当前使用的 NFT 计数即可。举个例子:有 A, B,C 三个地址分别进了 mint 后,A 拥有 101,102,103 号 NFT,B 用户 104,105号 NFT,C 只拥有 106 号 NFT,那么储存的数据便是

#101 #102 #103 #104 #105 #106
A B C

当前已使用 NFT 计数为 106 。

位置 102,103,并不会存储任何数据,但是之前的前提,用户的 mint 是连续的,我们也可以知道它们的所有者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
contract ERC721A is
Context,
ERC165,
IERC721,
IERC721Metadata,
IERC721Enumerable
{
function _safeMint(
address to,
uint256 quantity, // 支持批量 mint
bytes memory _data
) internal {
uint256 startTokenId = currentIndex;
// ...

// 1)这里仅记录了第一个 ID
_ownerships[startTokenId] = TokenOwnership(to, uint64(block.timestamp));

uint256 updatedIndex = startTokenId;

for (uint256 i = 0; i < quantity; i++) {
emit Transfer(address(0), to, updatedIndex);
// ...
updatedIndex++;
}

// 2)更新了计数
currentIndex = updatedIndex;
}
}

这样一来,ERC721A 做到了就把对 storage 的写入从 O(N) 优化到了 O(1) 。单次 mint 的数量越多,优化效果则越明显。

实验效果

根据 Azuki 官方给出的试验效果,同样印证了我们刚才得出的“把对 storage 的写入从 O(N) 优化到了 O(1)”的结论:

Gas Statistics

以太坊黄皮书公式解析(下)

前言与版本

笔者最近在结合以太坊黄皮书以太坊源码,结合自己的理解解析下黄皮书内的公式,与大家共同学习进步,若大家在阅读以太坊黄皮书时,对公式产生理解上的困惑,可以参阅本文一起看。文章基于当前(2022/1/10)的黄皮书,版本号为 BERLIN VERSION fabef25 ,若有不准确之处,欢迎指出。由于该黄皮书内除附录外有 183 个公式,为了让文章篇幅不过长,该解析会由三部分组成一个系列,每个系列解析约 60 个公式,本文为下篇。

公式解析

(130)

  • 此处 Ξ 为 EVM 指令执行函数。
  • σ 为执行前世界状态。
  • σ’ 为执行后世界状态。
  • g 为执行前 Gas 剩余。
  • g’ 为计算后 Gas 剩余。
  • I 所包含的字段参阅公式 (91) - (99)。
  • A 为执行后子状态。
  • o 为执行输出内容(output)。

公式 (130) 给出了 EVM 执行函数的输入输出定义。

(144)

  • u 为机器状态(machine state),包含:
    • ug: 剩余可用 Gas 。
    • upc:当前执行程序计数器。
    • um:内存的内容。
    • ui:内存中激活的字节数。
    • us:栈的内容。

公式 (144) 定义了当前待执行指令 w ,即为待执行指令集位于索引 upc 中的指令,或者为 STOP 。

(145) (146)

  • Z 为异常检查函数。

公式 (146) 定义了指令 W 函数,当 w 的指令在 CREATE, CREATE2, SSTORE, SELFDESTRUCT 之一,在 LOG0 - LOG4 之一,或是 CALL 且对应栈索引上的数据不为空时。
公式 (145) 定义异常状态的可能情况:Gas 费不足、非法指令(指令 w 的 δw 未定义,详细后文会阐述)、栈中参数不足、JUMP\JUMPI 的目的地非法、新的栈大小超过 1024、企图在 static 调用中修改状态。

(150)

公式 (150) 定义了正常停止函数 H 。当指令会 RETURN 或 REVERT 时,会返回一个特殊函数 HRETURN 。若是 STOP 或 SELFDESTRUCT,则返回空序列,或者则返回空集合(表示返回不正常)。

(131) - (143)

公式 (140) 定义了 o 为正常停止函数 H 对当前机器状态和入参 I 的输出。
公式 (141) 定义了 · 操作会将其之后的项放入集合中。
公式 (142) (143) 表示机器状态的更新会伴随 Gas 的消耗。
公式 (139) 定义了指令执行函数 X ,它会被递归调用(公式中第 4 种情况),除非检测到异常(通过异常检查函数 Z 检查)、操作为 REVERT 或正常停止(通过正常停止函数 H 检查)。
公式 (133) - (138) 定义了机器状态 u 的初始状态。
公式 (131) - (132) 表示 Ξ EVM 执行函数的具体逻辑为对入参进行 X 函数(即公式(139))的调用。

(149)

公式 (149) 定义了 N 函数,接受当前指令索引以及指令,返回下一个有效指令在代码中的位置。会区分给定的指定入参是否为 PUSH1, PUSH2 。

(147) (148)

公式 (147) 的 D 函数返回正在运行的代码所给定的有效跳转地址集合。如果位置越界,则返回空集合。如果指令为 JUMPDSET ,则会递归调用 N 函数保存到一个位置集合,否则直接调用 N 函数返回下一个位置。

(151) - (154)

公式 (151) - (154) 描述了指令的栈执行模型,栈变化大小由入栈指令个数减去出栈指令个数(公式(152))。公式 (153) 表示栈是低位索引(lower-indexed)的,即栈顶索引为 0 。公式 (154) 则表示在指令从索引 0 开始往栈内推入后,会从栈顶开始一条条执行指令,索引也会逐渐变小。

(155) (156)

公式 (155) 表示,随着不同计算的执行,ug 会被相应的消耗。公式 (156) 则表示,upc 会根据是否是 JUMP/JUMPI 来判断,或者是调用公式 (149) 定义的 N 函数。

(157) - (160)

公式 (157) - (160) 则表示,假定在执行中,机器状态内的,内存(m, i),子状态(A)和世界状态(σ)不会改变。

(161) - (162)

  • Bt 为链上的总难度。
  • Bd 为当前区块难度。

公式 (162) 定义了 B’ 为当前区块的父区块。公式 (161) 则表达了链上的总难度是累计的。

(165)

公式 (165) 定义了如何判断两个区块是否是兄妹(sibling):即两个区块的父区块相同,两个区块自身是不同区块,相互不为叔块。

(164)

公式 (164) 定义了如果判断两个区块是否是亲属(kin):如果 n 代之内是兄妹(sibling),则为亲属。

(163)

  • V 为区块头验证函数,参阅公式 (52) 。

公式 (163) 表示,当前区块最多可以引用两个叔块,叔块都验证有效,且叔块都与当前区块在 6 代以内。

(164)

公式 (164) 表示,区块头中记录的总累计 Gas 使用量,必须为区块中最后一个区块执行后的累计 Gas 使用量相同。

(165) - (171)

  • Rblock 为当前挖出一个区块所能获得的奖励。

公式 (171) 定义了当初挖出这个叔块的矿工的收益,从公式可以看出,该叔块离当前区块越亲,则奖励越高,并且会把奖励加入到账户状态中(公式(170)),前提是收益账户不是空账户(公式(169))。公式 (168) 定义了挖出当前区块的矿工收益,除了固定的挖出区块所得收益之外,也与其引用的叔块的数量相关。公式 (167) 则将上述这些行为,统一定义为区块奖励函数 Ω 。

(172)

公式 (172) 定义了不同以太坊版本中,挖出区块的固定收益。

(173)

  • LS 为世界状态函数,具体定义参阅公式 (10) 。

公式 (173) 定义了函数 Γ ,映射区块 B 至它的初始世界状态。若区块 B 没有父区块(即它就是创世区块),那么为创世状态。否则就是它的初始世界状态就是其父区块的 storageRoot 。

(182)

公式 (182) 定义了区块状态转换函数 Π ,定义是从最新的世界状态,再加上接收过 Ω 函数奖励后的区块的状态。

(174) - (177)

公式 (174) - (177) 定义了区块状态转换函数 Φ :首先更新当前区块的 storageRoot 为父区块的世界加上区块中所有交易对状态的改变(公式(177));将矿工挖矿算出的最终结果记录在区块的 mixHash 中(公式(176));更新区块的 nonce (公式(175)),且最大值由区块的 difficulty 限定。

(179)

  • Υg 为区块交易 Gas 花销状态计算函数。

公式 (179) 表达了区块的 Gas 花销,会随着一个个交易的处理而累积。

(180)

  • Υl 为区块交易日志状态计算函数。

公式 (180) 表达了区块的日志,会随着一个个交易的处理而累积。

(181)

  • Υz 为区块交易状态码计算函数。

公式 (181) 表达了区块的状态码,会随着一个个交易的处理而更新。

(178)

  • Υ 为区块交易整体状态计算函数。

公式 (178) 是公式 (179) - (181) 定义了 σ[n] 为基于区块内的第 N 个交易后所产生的状态。表示区块状态会从区块的初始状态开始,通过一个个交易来累积更新状态。

(183)

公式 (183) 描述了工作量证明函数 PoW ,接受三个参数,第一个为不包含 nonce 和 mixHash 的新区块头状态,第二个参数为当前区块头 nonce,第三个参数为当前 DAG (用来计算 mixHash 的大型数据集合),输出 mixHash 和 nonce 。nonce 的最大值由区块的 difficulty 限定。

以太坊黄皮书公式解析(中)

前言与版本

笔者最近在结合以太坊黄皮书以太坊源码,结合自己的理解解析下黄皮书内的公式,与大家共同学习进步,若大家在阅读以太坊黄皮书时,对公式产生理解上的困惑,可以参阅本文一起看。文章基于当前(2022/1/10)的黄皮书,版本号为 BERLIN VERSION fabef25 ,若有不准确之处,欢迎指出。由于该黄皮书内除附录外有 183 个公式,为了让文章篇幅不过长,该解析会由三部分组成一个系列,每个系列解析约 60 个公式,本文为中篇。

公式解析

(61) (62) (63)

  • S(T)b 为交易发送者账户余额。
  • S(T)n 为交易发送者账户 nonce 。
  • TgTp 为 GasPrice * GasLimit ,即交易预付款。

公式 (61) 定义了一个交易的起始状态,即会被扣除预付款(公式(62)),并且 nonce + 1 (公式(63))。

(66)

  • g0 为需要支付执行合约的基本费用。

公式 (66) 定义了 g 为交易的 GasLimit 减去执行交易的基本 Gas 数量。

(64) (65)

  • σp 是交易执行后的账户临时状态。
  • g’ 是交易后剩余 Gas 。
  • A 是交易子状态。
  • z 是状态代码。
  • To 是交易的原始发起人,若是合约间交易调用,那么该值就是发起调用的合约地址。
  • g 在公式 (66) 已定义。
  • Λ4 是合约创建函数(Tt,即接收者地址为空),该函数定义后文会详细阐述,下标的 4 表示只取原函数返回值的前四个值。
  • Θ4 表示普通交易、发送调用消息函数,该函数定义后文会详细阐述,下标的 4 表示只取原函数返回值的前四个值。
  • T 为一个布尔值,表示对状态进行修改的许可。在后文对 Λ 和 Θ 的入参定义中,通常记作 w 。

公式 (64) 表达了交易后的临时状态 σp,根据是合约创建还是普通交易,而会有不同的入参。公式 (65) 定义当前入参子状态是公式 (55) 中定义的空子状态中各值与当前交易子状态中各值的与集(and)。

(67)

  • Ar 交易应返还的 Gas 数量。

公式 (67) 表示,在交易过程中,调用者若有通过调用 selfdestruct(addr); 将合约自毁,则合约内的以太币会累计到应退还 Gas 参数 Ar 中,Ar 会在随后参与最终应退还 Gas 的计算。

(68)

  • g* 为总计退还 Gas 数量。

公式 (68) 定义了总退还 Gas 数量的计算,与执行交易后剩余 Gas 数量 g’ ,执行合约花费的 Gas 数量 (Tg - g’)和包含了销毁合约退还数量的累积计数 A’r 相关。

(69) - (72)

  • σ* 为交易预备最终状态。
  • σp 为交易临时中间状态。
  • BHc 为区块的 beneficiary 值。

公式 (69) - (72) 定义了从交易临时中间状态到预备最终状态的转换。首先在交易者的余额中加上应退还的数量(公式(70))。在矿工的余额中加上消耗的以太币数量(公式(71))。并将矿工收益记录在区块的 beneficiary 值上(公式(72))。

(73) - (75)

  • σ’ 为交易最终状态。

公式 (73) - (75) 定义了交易从预备最终状态到最终状态的转换。会先删除需要自毁的合约(公式(74)),再删除接触到的死合约(公式(75)),死合约的定义在公式 (15)。

(76) - (78)

  • Υg 为交易总共使用的 Gas 。
  • Υl 为交易所创建的所有日志。
  • Υz 为交易状态码。

公式 (76) - (78) 给出了三个交易相关状态的定义。

(79)

  • ζ 为合约创建时可选的一个参数,salt ,用于创建可预见的地址。使用场景可参阅这篇文章

公式 (79) 定义了创建合约时的参数 salt 是可选的,若提供 slat,需要是一个长度为 32 的字节。

(80)

  • Λ 为创建合约函数。
  • σ, A, s, o, g, p, v, i, e, ζ, w 为创建合约函数的参数,分别是:状态,子状态,发送者,原始发送者(考虑通过合约创建的情况),GasLimit,GasPrice,EVM 初始代码化代码,创建合约的调用所处的当前栈深度,salt 和 对状态进行修改的许可。
  • σ’, g’, A’, z, o 为函数返回值,分别是:新的状态,剩余 Gas ,新的子状态,状态码,输出(output)内容。

公式 (80) 给出了创建合约函数的定义(输入,输出)。

(81) - (83)\

  • s 为交易发起者(sender)地址。
  • n 为发起交易的 nonce 。
  • ζ 已在公式 (79) 定义。
  • i 为 EVM 初始化代码。

公式 (81) - (83) 为合约地址的产生规则。首先定义了函数 LA ,若未提供 salt ,则输出 n 与 s 的 RLP 编码结果,否则输出 (255) · s · ζ · KEC(i)(公式(83)),这也意味着同一个账户,对于同一个合约代码,可以创建可预见的合约地址。然后将 LA 的输出结果经过 Keccak-256 哈希后,取右边 160 位(公式(82))即可得到地址(公式(82))。公式 (81) 则是描述了需带入的实际参数。

(84)

公式 (84) 则表示新创建的合约地址,会被存入 Aa 交易子状态中(于公式 (54) 中定义)。

(89)

公式 (89) 定义了 v’ ,若地址在之前就有余额,则会继承。

(85) - (88)

公式 (85) 定义了新的世界状态,在创建的地址上会出现一个新的合约,nonce 为 1, 余额为 v’ 加上创建交易传入的以太币,以及空的 storageRoot 和 codeHash (公式(86))。创建者的地址上会扣除发送的以太币(公式(88)),然后保存其状态(公式(87))。

(90)

  • Ξ 为执行初始化 EVM 代码的代码执行函数。
  • σ** 合约初始化后的状态。
  • g** 为初始化后可用的剩余 Gas 。
  • A 为累计子状态。
  • o 为账户代码。
  • I 为一系列输入参数变量,会在后文阐述。

公式 (90) 定义了初始化代码执行函数的输入与输出。

(91) - (99)

  • I 为 Ξ 的其中一个参数,包含一系列变量。
  • Ia 为新创建合约的地址。
  • Io 为交易的原始发起人。
  • Ip 为交易的 Gas Price 。
  • Id 函数调用参数,这里为空,这个交易不可能会有具体函数调用参数 Input 。
  • Is 交易发送者(sender)地址。
  • Iv 发送给合约的初始以太币。
  • Ie 当前调用栈深度。
  • Iw 对状态进行修改的许可。

公式 (91) - (99) 定义了参数 I 所包含的项。

(100)

公式 (100) 表示合约创建开销,与合约代码大小成正比。

(101) - (105)

公式 (105) 定义了创建失败的一些场景:原地址不为空,且有 codeHash 或有 nonce;创建合约代码为空;gas 费不足;代码过大;

公式 (104) 定义了状态码 z ,如果创建失败,则为 0 ,成功则为 1 。

公式 (102) (103) 定义了,若创建失败,则不更新状态和子状态。

公式 (101) 定义了若创建失败,则不会收取代码创建开销。

(106)

  • Θ 为消息调用函数
  • σ, A, s, o, r, c, g, p, v, v˜ d, e, w 为消息调用函数参数,分别为:执行当前世界状态,子状态,发送人(sender)地址,原始发送者(考虑通过合约创建的情况),接收地址,执行代码位置(通常与 r 一致),GasLimit,GasPrice,发送的以太币数量(msg.value),通过 DELEGATECALL 而出现在新的执行上下文中的以太币数量,调用入参 input data 数据,当前堆栈深度和对状态进行修改的许可。
  • σ’, g’, A’, z, o 为函数返回值,分别是:新的状态,剩余 Gas ,新的子状态,状态码,输出(output)内容。

(107)

公式 (107) 定义了 a1 这个交易中的第一个临时状态:除非发送者和接收者是同一个地址,否则跟随交易发送的以太币(msg.value)会被发送。

(108) - (113)

公式 (108) - (113) 描述的是公式 (107) 的具体流程。如果账户 a1[r] 是一个新地址,则会对账户进行状态初始化(公式(112)),并且在余额中加上交易转入的以太币(公式(113)),然后更新到临时状态(公式(111))。相应地,在发送人那边也减少对应的以太币(公式(110)),更新临时状态(公式(108))。

(114) - (128)

  • I 中各参数的定义可以参阅公式 (91) - (99) 。

公式 (118) 定义了执行消息调用函数 Ξ ,将会输出 σ (执行后世界状态),g(执行后剩余 Gas),A(执行后子状态码)和 o (调用结果输出(output))。公式 (127) 描述了定义在地址 1 - 8 上的预留函数(参阅黄皮书附录 E),以及常规执行函数。公式 (120) 表达了客户端在部署完合约后,会在本地存储交易调用代码的地址及其哈希。公式 (114) - (117) 则表达了会根据 Ξ 函数输出的 σ (执行后世界状态)是否为空来判断是否要用 Ξ 函数的其他输出来更新自身对应状态。

(129)

公式 (129) 定义了公式 (127) 中的地址集合为 π 。

以太坊黄皮书公式解析(上)

前言与版本

笔者最近在结合以太坊黄皮书以太坊源码,结合自己的理解解析下黄皮书内的公式,与大家共同学习进步,若大家在阅读以太坊黄皮书时,对公式产生理解上的困惑,可以参阅本文一起看。文章基于当前(2022/1/10)的黄皮书,版本号为 BERLIN VERSION fabef25 ,若有不准确之处,欢迎指出。由于该黄皮书内除附录外有 183 个公式,为了让文章篇幅不过长,该解析会由三部分组成一个系列,每个系列解析约 60 个公式,本文为上篇。

公式解析

(1)

  • σ 为以太坊世界状态。
  • Υ 为以太坊状态转换函数。
  • T 为一个交易。

上述公式阐述的是,以太坊是一个基于交易而改变状态的状态机。即每进来一个交易,都会改变一次以太坊的旧世界状态,从而进入一个新世界状态。

(3)

  • B 为一个区块。
  • T0, T1, … 为一组交易。

在实际运作时,基于效率考量,以太坊是批量处理交易的,一个批次的交易,会被打包在一个区块中,这就是 (3) 公式的含义。

(2)

  • Π 表示区块层面上的状态转换函数。

上述公式即是 (1) 的批量处理版本,以太坊的世界状态通过区块(即一组交易)批量更新。

(4)

  • Ω 为区块确定性状态转换函数,会奖励挖到区块的节点。

这个公式看似有点复杂,让我们逐步解析。等式的左边 Π(σ, B) 即是公式 (2) 的 σt+1,就是以太坊的下一个世界状态。等式右边的 Υ(Υ(σ, T0), T1)... 表示的是,交易会被逐个执行,每一个交易的结束状态,都会是下一个交易的开始状态。故 Ω(B, Υ(Υ(σ, T0), T1)...) 表达的是,逐个执行完区块内的所有交易后,以太坊还会给与挖到区块的节点奖励,这就意味着,以太坊的世界状态,完成了一次基于区块的状态更新。

(5)

  • β 为以太坊的 chain_id

公式 (5) 表达的是以太坊主网的 chain_id 是 1 。目前以太坊除了使用 network_id 来区分环境外,还使用 chain_id 来区分同一环境内的不同分叉。例如,以太坊和经典以太坊的 network_id 都是 1 ,但是 chain_id 分别是 161

(6)

  • l 函数表示取一个序列内的最后一项。

公式 (6) 就是对 l 函数的定义,比较直观,直接取 l(x) 就是取 x 序列的最后一项。

(8) (9)

公式 (8) 中的 LI 函数定义一个对键值对的变换,即将键(k)进行 Keccak-256 哈希,对值进行 RLP 编码。公式 (9) 则对键值的类型和范围做了限定。由于 Keccak-256 哈希和 RLP 编码的特性,键只会是长度为 32 的字节序列,值只会是正整数(在很多文章和代码示例中我们通常看到的是其十六进制表示)。

(7)

  • σ[a]s 为以太坊账户的 storageRoot ,是一个 256 位的哈希值,表示保存该账户存储数据的 Merkle Patricia 树 的根节点哈希值。由于这种树的特性,其根节点就相当于其所有叶子数据的状态快照,任意一个叶子状态的改变,都会改变根节点的哈希值。

公式 (7) 表达的就是,以太坊的 storageRoot 值保存的是对账号数据(键值对)进行 LI 函数转换后,存入 Merkle Patricia 树之后的,根节点哈希值。

(11)

  • KEC(a) 为账号地址(公钥)。
  • σ[a]n 为账户的 nonce 值,当账户是合约账户时,该值表示该合约部署的合约数,当时外部账户时,该值表示历史交易次数。
  • σ[a]b 为账户的 balance 值,即账户余额,以 wei 为单位。1^18 wei = 1 ETH。
  • σ[a]s 为账户的 storageRoot ,上文已经阐述。
  • σ[a]c 为账户的 codeHash 值,若账户是外部账号,则该值为空,若是合约账户,则是编译后的 EVM 执行代码的 Keccak-256 哈希值。

公式 (11) 表示,一个账号在以太坊内,由一个账号地址,和 4 个状态值(存储时会被 RLP 编码)组成。

(10)

  • Ls(σ) 为以太坊世界状态函数。

公式 (10) 表示,以太坊世界状态,由所有的非空账号组成(若一个账号创建后,还未执行过交易,那么是不会被以太坊记录的)。

(13)

  • v 为以太坊的账号有效性函数。

公式 (13) 表示,一个有效的以太坊账号,nonce 和 balance 都是比 2^256 小的正整数,storageRoot 和 codeHash 都是长度为 32 的字节序列。

(12)

倒写的 “A” 此处的含义为“对于任意”,即意思是,对于在以太坊内的所有账号,要么是空账号,要么是有一个 20 字节长度地址并且符合公式 (13) 有效性函数的账号。

(14)

公式 (14) 给“空账号”下了定义,即 codeHash 为空字符串的 Keccak-256 哈希值,且 nonce 和 balance 都是 0 的账号。

(15))

公式 (15) 给“死账号”下了定义,当一个账号状态不存在或为空时,那么就是“死账号”。

(17)
(18)

  • Tn 为交易的 nonce 值,为交易发送者发出过的交易数量。
  • Tv 为交易者发送的以太币数量,以 Wei 为单位。
  • Tp 为交易的 gasPrice 值,指交易者愿意给矿工付出的 gas 单价,以 wei 为单位。
  • Tg 为执行这个交易允许消耗的最大以太币数量,以 wei 为单位。
  • Tw,Tr,Ts 是与交易者签名相关的 v,r,s 值,用于验证交易者。
  • Td 为交易的 data 字段,若交易是执行合约函数,那么 data 值里存储的就是合约函数的入参。
  • Ti 为交易的 EVM 执行码,仅交易是创建合约时,会执行一次。

公式 (17) (18) 对交易中各字段进行了约定,必须符合约定,才是合法交易。即 Tn,Tv,Tp,Tg,Tw,Tr,Ts 是比 2^256 小的正整数,Td,Ti 都是字节(bytes)类型。

(16)

公式 (16) 表示,若交易要么是一个创建合约交易,会包含 init 字段,若不是,则会包含 data 字段。

(19)

  • Tt 为交易的 to 值,即合约地址。

公式 (19) 对 to 值进行了定义,当时创建合约时,to 值为空,否则会是一个长度为 20 的字节。

(20)

  • Bu 为区块头。
  • Bt 为区块内打包的交易。
  • Bu 为叔块列表。

公式 (20) 即表示一个区块由上述三部分组成。

(21)
(22)
(23)

  • Ru 为区块中所有交易执行完后,使用的 Gas 数量。
  • Rl 为交易过程中创建的日志集合。
  • Rb 为日志信息所构成的布隆过滤器。
  • Rz 为交易的状态码,1表示成功,0表示失败。

公式 (21) 即表示一个交易收据由上述四部分组成。公式 (22) (23) 限定了这些值的类型,状态码 Rz 和 Gas 开销 Ru,需为正整数,布隆过滤器 Rb 是个长度为 256 的字节。

(24) (25)

  • O 表示一个日志。
  • Oa 为创建日志的账户。
  • O0,O1… 为具体日志。
  • Od 为相关日志数据(在 solidity 中表现为未被标注 indexed 的参数)。

公式 (24) (25) 定义了以太坊日志的结构,一个以太坊日志集合 Rl 由一系列日志项 O 组成,每一个日志项由上述三部分组成。且 Oa 为长度为 20 的字节,任意 O0,O1 … 都是长度为 32 的字节,Od 为字节类型。

(27) (28) (29) (30)

这组公式,是一个布隆过滤器的定义,简单来说就是一种以 O(1) 时间复杂度来查询一个元素是否存在于一个集合中的方法,查询时可以保证一个元素 100% 不存在,但不可保证一个元素 100% 存在。宏观定义如公式 (27) ,以太坊的布隆过滤器,会将任意输入字节经过 Keccak-256 哈希后得到的长度为 2048 的比特经过计算获取三个数,然后将一个空的长度为 2048 的比特(256 字节)在索引为那三个数的地方,置 1 ,即结果 y。公式 (28) 表示了 y 值初始时为一个空的长度为 2048 的比特(256 字节)。公式 (29) (30) 表示,在把输入经过 Keccak-256 哈希后,取 0,2,4 这三位,并将他们分别于 1,3,5 三位拼接成 uint64,然后与 2048 取余,这三个数即是要将 y 这个 bit map 中置 1 的索引位置。

(26)

  • Ot 为日志主题。

公式 (26) 在宏观上定义了以太坊收据的布隆过滤器函数,查询时首先会判断日志生产者的地址,然后会根据公式 (27) 查询日志主题。

(32)

公式 (32) 定义了一个 p 函数,对于输入的键值对,分别会对其进行 RLP 编码。

(33)

  • P(BH) 为父区块的状态。
  • Hr 为当前区块最终状态标识。

公式 (33) 表达的是,当前区块的世界状态,是由父区块的状态累加上当前区块的最终状态后,储存为 Merkle Patricia 树的根节点哈希。

(34)

公式 (34) 定义了 LH 函数,用于序列化,即是取所有的区块状态字段,并且定义了顺序。

(31)

  • Hr 为当前区块最终状态标识。
  • Ho 为叔块列表。
  • Ht 为所有块内交易所组成的 Merkle Patricia 树的根节点哈希。
  • He 为所有块内交易收据所组成的 Merkle Patricia 树的根节点哈希。
  • Hb 为日志的布隆过滤器。
  • TT 为区块状态累进函数,后续公式会有详解。

公式 (31) 给出了区块最终状态标识的合法性定义:首先将当前状态与累积上区块内所有的交易修改,并将状态储存为 Merkle Patricia 树的根节点哈希(Hr);将叔块状态列表进行 RLP 编码(Ho);将区块中所有索引 i 的交易数据进行公式 (32) 编码,并将状态储存为 Merkle Patricia 树的根节点哈希(Ht);将区块中所有索引 i 的收据数据进行公式 (32) 编码,并将状态储存为 Merkle Patricia 树的根节点哈希(He);对于任意存在日志,布隆过滤器结果都为真(Hb)。

(35)

公式 (35) 定义了 LB 函数,用于序列化,并定义了顺序,LT,LH 函数上文已有阐述。

(36) (37) (38)

公式 (36) (37) (38) 定义了各种包含在 LH,LT 函数中的字段的类型限制,很直观,就不一一阐述了。

(40)

  • P(H) 为父区块。

公式 (40) 即表达了当前区块的区块号为父区块的区块号 +1 。

(39)

  • Hp 为父区块头的 Keccak-256 哈希。

公式 (39) 表述了父区块头字段 Hp 的定义,将父区块的状态进行 RLP 编码后,再进行 Keccak-256 哈希。

(41) - (48)

  • Hd 为区块的 difficulty 值。

上述公式 (41) 区块描述了 difficulty 的定义,当区块为创始块时,Hd 默认为 2^34 。若不是创始块的话,则会取 2^17 (公式(42))与 P(H)Hd + x * s2 + E 的最大值。其中 s2 为 homestead 难度参数,用于动态平衡区块间的出块时间,当前区块的 timestamp 与父区块的 timestamp 间隔很近,则该值会变调整为 -99 (公式(44))。x 为一个与父区块难度值正相关的参数(公式(43))。E 是一个每间隔十万个区块,就会指数级增长的值,故当区块越来越多时,该值会变大得越来越快,也就是俗称的“难度炸弹”,当这个值非常大时,也就进入了俗称的“冰河时期”,用于激励以太坊切换为 POS 。在 EIP-649 之后,为了减缓“冰河时期”的到来,防止链被“冻结”,让目前的区块数 Hi 减去人为定义的一个 k (公式(47))值。k 值因不同以太坊版本而不同(公式(48))。

(49)

  • Hl 为区块的 Gas Limit 值。

公式 (49) 对一个区块 Gas Limit 大小进行了范围限定,与上一个区块的 Gas Limit 相关。

(50)

公式 (50) 限制了当前区块的 timestamp 必须大于父区块的 timestamp 。

(51)

公式 (51) 限定了以太坊工作量证明函数 PoW (会于后面详细展开)的两个输出值 n,m 的范围。PoW 函数接受三个参数,第一个为不包含 nonce 和 mixHash 的新区块头状态,第二个参数为当前区块头 nonce,第三个参数为当前 DAG (用来计算 mixHash 的大型数据集合)。函数会输出一个数组,第一个元素即是 mixHash ,用于证明使用了正确的 DAG 。第二个元素是基于 DAG 和区块头状态的密码学伪随机数。求解时间和难度 Hd 是成正比的。

(52)

公式 (52) 定义了区块头验证函数 V(H)。当各字段同时符合条件时,验证为有效。各内部函数上文已有阐述。

(53)

  • Υ 为账户状态转移函数。
  • T 为交易。
  • σ 为账户状态。

公式 (53) 定义了账户的状态转移,即根据交易而更新状态。

(54)

  • A 为交易子状态。
  • A1 为交易日志。
  • At 交易所接触过的账户集合。
  • Ar 是交易的累计退还 Gas 余额参数,会参与最终退还 Gas 的计算。
  • Aa 是交易所访问的账户地址。
  • Ak 是交易所以访问的存储键。

公式 (54) 定义了交易子状态的组成部分。

(55)

公式 (55) 定义了交易的空子状态。π 为一个预编译地址集合(后文会详细阐述)。

(56) (57) (58)

  • Ti 是交易附带的关联数据。
  • Td 初始化的 EVM 字节码序列。

公式 (55) 定义了交易的预付 Gas 单价,会根据交易的类型不同而不同。G 的完整定义见黄皮书附录。

(59)

公式 (59) 定义了交易的预付费数量,即愿支付的 Gas 单价 * Gas 最大数量,加上转账的数量。

(60)

  • S(T) 为发送者账户。
  • B(H)l 为该区块能够使用的 Gas 上限。
  • l(BR)u 为截止到当前交易,区块内之前的交易已经使用的 Gas 数量。

公式 (60) 定义了交易合法性的验证,很直观,公式已在上文阐述。

百万富翁问题

最近在看零知识证明,了解到了一个很有意思的问题,即《姚氏百万富翁问题》,该问题由图灵奖得主姚期智老师提出。算是对开始解零知识证明的朋友起到抛砖引玉作用的经典问题。下面展开一下问题的描述,以及姚期智老师给出的一个答案。

问题

假设有两个富翁甲,乙,他们的财产数量分别为 a, b ,且 1 ≤ a, b ≤ N 。甲,乙两者想知道他们两者的财产数量谁多,但是又不能透露他们具体的财产数量。

解答

乙先生产自己的一对非对称加密(如 RSA))秘钥对,即公钥 E,私钥 C 。并像 TLS 通信中一样将公钥 E 发送给甲,然后是自己保留 C 。

第一步

甲再取一个大于 a 的数字 X(尽量取大),将 X 通过乙的公钥加密后得到 E(X) ,然后将 E(X) - a 发送给乙。

第二步

乙取得 E(X) - a 后,由于不知道 X 的具体值,所以也更无从知晓 a 。他将进行一组计算来对 E(X) 进行枚举(对所有 a 的可能范围,即1 到 N),然后使用私钥解密,使得枚举结果中有一项为 X:

  • C(E(X) - a + 1)
  • C(E(X) - a + 2)
  • C(E(X) - a + a) => 即 X
  • C(E(X) - a + N)

由于 1 ≤ a, b ≤ N 的前提,所以其中必有一项为 C(E(X) - a + a) ,即 X 。

第三步

乙取一个素数 P ,P 尽量比 X 小几个数量级(甲透露 X 的数量级并不会有问题),且 P 尽量大于且不要太接近 N。这时,将上述计算取得的一组结果全部与 P 取余,得:

  • C(E(X) - a + 1) mod P
  • C(E(X) - a + 2) mod P
  • C(E(X) - a + a) mod P => 即 X mod P
  • C(E(X) - a + N) mod P

第四步

在上述取余结果计算中,前 b 项不变,后 N 项全部 +1 ,即:

  • C(E(X) - a + 1) mod P
  • C(E(X) - a + 2) mod P
  • C(E(X) - a + b) mod P
  • C(E(X) - a + (b + 1)) mod P + 1
  • C(E(X) - a + N) mod P + 1

然后将这组结果与 P 全部给甲。由于第 a 项为:C(E(X) - a + a) mod P 即 X mod P,若 a < b,则第 a 项就不会被 +1 。

第五步

甲取得数据后,计算 X mod P ,若 X mod P 存在于乙发送的数据中,则 a < b ,否则 a ≥ b 。由于乙传输的结果经过了取余操作,且 P 比 X 小几个数量级,所以甲无法对原式子进行 100% 正确的还原。

小结

所以这个解答的关键步骤就是第三步,即取余,是进行了一次同态加密(Homomorphic encryption),隐藏了原数据,但保持了结果正确。若不进行取余,而是单纯的通过 X 是否在乙发送的结果中来判断的话,不管 a < b 还是 a ≥ b ,由于甲知道 X,P,a 和 N 的,甲可以将乙的结果通过公钥再次加密,然后枚举试出乙是在哪一个位置开始进行 +1 操作的。

从 Uniswap V3 源码中学习 Solidity 编程技巧

笔者前两日学习了 Uniswap白皮书以及源码,具体学习笔记可看这篇博客。在阅读其源码的过程中,学习到了一些 Solidity 编程技巧,在此文记录分享。

MLOAD vs SLOAD

在源码更新头寸(position)函数中,在从 storage 载入合约状态时,有如下额外注释(// SLOAD for gas optimization):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function _modifyPosition(ModifyPositionParams memory params) {
// ...

Slot0 memory _slot0 = slot0; // SLOAD for gas optimization

position = _updatePosition(
params.owner,
params.tickLower,
params.tickUpper,
params.liquidityDelta,
_slot0.tick // 1
);

if (params.liquidityDelta != 0) {
if (_slot0.tick < params.tickLower) { // 2
// ...
} else if (_slot0.tick < params.tickUpper) { // 3
(slot0.observationIndex, slot0.observationCardinality) = observations.write( // 4
_slot0.observationIndex, // 5
_blockTimestamp(),
_slot0.tick, // 6
liquidityBefore,
_slot0.observationCardinality, // 7
_slot0.observationCardinalityNext // 8
);

amount0 = SqrtPriceMath.getAmount0Delta(
_slot0.sqrtPriceX96, // 9
TickMath.getSqrtRatioAtTick(params.tickUpper),
params.liquidityDelta
);
amount1 = SqrtPriceMath.getAmount1Delta(
TickMath.getSqrtRatioAtTick(params.tickLower),
_slot0.sqrtPriceX96, // 10
params.liquidityDelta
);
// ...
} else {
// ...
}
}
}

从代码中可见,由于函数内有 10 处需要引用 slot0 storage 变量内的字段。而访问 storage 变量(SLOAD)的成本是比访问 memory 变量(MLOAD)昂贵不少的。所以源码在函数最上方先使用一次 SLOAD 将变量 slot0 载入到内存中,以节省 Gas 开销。我们可以使用如下代码试验一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
contract TestSaveToMem {
struct Slot {
uint256 a;
uint256 b;
}

Slot public slot;

constructor() {
slot = Slot({ a: 100, b: 200 });
}

function notSaveToMem() public returns (uint256 gasUsed) {
uint256 startGas = gasleft();

for (int i = 0; i < 10; i++) {
readProp(slot.a);
readProp(slot.b);
}

gasUsed = startGas - gasleft();
}

function saveToMem() public returns (uint256 gasUsed) {
uint256 startGas = gasleft();

Slot memory _slot = slot;
for (int i = 0; i < 10; i++) {
readProp(_slot.a);
readProp(_slot.b);
}

gasUsed = startGas - gasleft();
}

function readProp(uint256 prop) private pure {
require(prop > 0);
}
}

测试结果为:

1
2
3
4
notSaveToMem gasUsed: 18989
✓ notSaveToMem
saveToMem gasUsed: 4736
✓ saveToMem

可见函数如果单纯同样次数读取 storage 内的变量,先存入 memory 的话,开销大约只有 1/4 左右。

可预知的合约地址

在源码创建代币交易对池的地方,我们可以看到:

1
2
3
4
5
6
7
8
9
10
11
function deploy(
address factory,
address token0,
address token1,
uint24 fee,
int24 tickSpacing
) internal returns (address pool) {
// ...
pool = address(new UniswapV3Pool{salt: keccak256(abi.encode(token0, token1, fee))}());
// ...
}

代码在创建合约时,先将可预知的交易对池的元信息,通过 abi.encode 编码后,然后作为 slat 参数,在合约的创建中使用。在官方文档的解释中,若合约的创建中,指定了 salt 参数,则会使用 create2 机制创建合约,即若指定的 salt 不变,则创建的合约地址不变,只需使用 bytes1(0xff),工厂合约的地址,salt,合约代码的哈希以及初始化参数,就可还原。

官方的例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
contract D {
uint public x;
constructor(uint a) {
x = a;
}
}

contract C {
function createDSalted(bytes32 salt, uint arg) public {
address predictedAddress = address(uint160(uint(keccak256(abi.encodePacked(
bytes1(0xff),
address(this),
salt,
keccak256(abi.encodePacked(
type(D).creationCode,
arg
))
)))));

D d = new D{salt: salt}(arg);
require(address(d) == predictedAddress);
}
}

Uniswap 源码中,还原地址的逻辑也是类似的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function computeAddress(address factory, PoolKey memory key) internal pure returns (address pool) {
require(key.token0 < key.token1);
pool = address(
uint256(
keccak256(
abi.encodePacked(
hex'ff',
factory,
keccak256(abi.encode(key.token0, key.token1, key.fee)),
POOL_INIT_CODE_HASH
)
)
)
);
}

如此一来,合约的地址就不需再上链进行抓取,一方面方便了部署,另一方也节省了存储与抓取的 Gas 开销。

不一致的 ERC20 接口定义

由于一些争论,目前 ERC20 接口,对 transfer 等发送代币的函数的返回值定义有两种,一种为若发送失败,则会返回 false ,如 openzeppelin 就是这么定义的,还有一种为若发送失败,则直接在函数中进行 revert() ,函数没有返回值。面对这种同一函数,同样参数,不同返回值的情况,Uniswap V3 源码是这么处理的:

1
2
3
4
5
6
7
8
9
function safeTransfer(
address token,
address to,
uint256 value
) internal {
(bool success, bytes memory data) =
token.call(abi.encodeWithSelector(IERC20Minimal.transfer.selector, to, value));
require(success && (data.length == 0 || abi.decode(data, (bool))), 'TF');
}

首先,由于 Solidity 的 Function Selector 定义中可知,Function Selector 是函数原型(prototype)哈希的前 4 字节,而函数原型是由函数名和它的所有参数类型决定的。所以 abi.encodeWithSelector 可以允许代码在未知函数返回类型的情况下,调用函数。在调用之后,代码通过第二个返回值 data 来判断返回布尔版本的 transfer 是否调用成功,第一个返回值 bool success 来判断 revert() 版本的调用成功(若调用成功就无返回值即 data.length == 0)与否。

预计算”白嫖”算力

由于在 Uniswap V3 中,同一种代币对的交换,可能同时存在许许多多不同价格区间的流动性池,所以,在查询当前给定的 A 代币能交换多少 B 代币(即代币的价格)时,并不能像 V2 那样,抓取一下两边代币在流动性池中的数量(仅需要调用一下 view 级别的函数),客户端利用核心公式 x * y = (x + Δx) * (y − Δy) = k 一推导,就能够知道。所以在 V3 中,只能像实际交换代币那样,从当前价格开始,一个个头寸池流过去,才能计算出最终可以得到的 B 代币数量。而在 V3 源码种,交换代币函数是一个接近 200 行的大函数,且会改变合约的状态,若用户刚想知道一下代币间的汇率,就要支付 Gas 费,也是不合理的。在这种情况下, Uniswap V3 利用了 solidity 中,revert(string reason) 函数可以终止当前函数调用,并向调用者退还剩余 Gas 费的机制,做了一个实现,首先我们看一下交换代币函数的具体代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function swap(
address recipient,
bool zeroForOne,
int256 amountSpecified,
uint160 sqrtPriceLimitX96,
bytes calldata data
) external override noDelegateCall returns (int256 amount0, int256 amount1) {
// 计算出可交换出的另一种代币的数量
// ...

IUniswapV3SwapCallback(msg.sender).uniswapV3SwapCallback(amount0, amount1, data);

// ...
}

我们可以看到,swap 函数会要求请求它的合约,自身实现一个 IUniswapV3SwapCallback 的接口。函数在计算出可交换出的另一种代币的数量后,在返回之前,会先调用一下请求合约自身实现的 IUniswapV3SwapCallback(msg.sender).uniswapV3SwapCallback 作为回调,并且最终可交换的 B 代币数会作为参数。而在抓取代币价格的合约 Quoter 中的具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function quoteExactInputSingle(
address tokenIn,
address tokenOut,
uint24 fee,
uint256 amountIn,
uint160 sqrtPriceLimitX96
) public override returns (uint256 amountOut) {
// ...

// 调用 swap 时,使用 try-catch 捕获 revert 信息
// 并从 parseRevertReason(reason) 中读取 reason 信息
try
getPool(tokenIn, tokenOut, fee).swap(
// ...
)
{} catch (bytes memory reason) {
return parseRevertReason(reason);
}
}

/// @inheritdoc IUniswapV3SwapCallback
function uniswapV3SwapCallback(
int256 amount0Delta,
int256 amount1Delta,
bytes memory path
) external view override {
// ...
// 将结果 amountReceived 存入 0x40 位置,然后作为 revert reason
assembly {
let ptr := mload(0x40)
mstore(ptr, amountReceived)
revert(ptr, 32)
}
// ...
}

function parseRevertReason(bytes memory reason) private pure returns (uint256) {
// ...
return abi.decode(reason, (uint256));
}

从代码中可见,首先使用了 try-catch 捕获 revert ,然后使用 assembly 读取 free memory pointer ,将汇率信息读出来。具体 assembly 的运用,可以参阅这篇文档

所以说,虽然 quoteExactInputSinglepublic 修饰的,但是其本质是一个 view

或许你还会问,虽然 revert() 函数的确能取消调用,并且退还 Gas 费,那也只是退还剩余部分,已被计算花销了的 Gas 并不会退还,那客户端不是还是要为了抓取一个汇率而付费吗?其实,在客户端(如 ethers)中,会使用 contract.callStatic.quoteExactInputSingle(…) 的方式,让节点以“假装”不会有状态变化的方式来尝试调用一个 public 函数,来达到没有 Gas 花费而又抓取了汇率的效果。

正如 ehters 的 callStatic 函数文档 中所描述的:

1
2
3
4
5
6
// Rather than executing the state-change of a transaction, it is possible to ask a node to
// pretend that a call is not state-changing and return the result.

// This does not actually change any state, but is free. This in some cases can be used
// to determine if a transaction will fail or succeed.
contract.callStatic.METHOD_NAME( ...args [ , overrides ] ) ⇒ Promise< any >

浅析 Uniswap V3

参考

V2 的实现与问题

Uniswap V2 作为老牌的基于自动化做市的 DEX ,其核心公式十分简单优雅,即是:

1
x * y = k

x * y = k

我们假设 x 轴为 x 代币的数量,y 轴为 y 代币的数量。所以当我们使用 x 代币去交换 y 代币时,流动性池中 x,y 代币的数量将会从 A 点移至 B 点。由于双曲线的特性,所以所有做市商所注入的流动性,做市区间都为 (0, ∞)。正由于所有的流动性都被摊在这个一整个广阔的开区间内,所以就导致了一个问题,即每次交换时,实际流动性的资金利用率较低,最后提取收益时,也被摊薄得厉害。

x * y = k (2)

如上图例子所示,在 x,y 货币数量通过交换从 A 点移动至 B 点的过程中,区间内可用的流动性为黑色区域。而实际利用的流动性,仅有红色区域。

V3 的实现

所以为了解决上述问题,在 Uniswap V3 中,开始允许用户在提供流动性时,可以自定义该流动性所支持的价格区间,仅当交易价格处于指定的交易区间内时,提供的头寸(position)才会被激活。

但同时,又为了维持公式的一致性,所以 V3 中提出了“虚拟流动性”(x_virtual, y_virtual)的概念,即是:

1
(x + x_virtual) * (y + y_virtual) = L^2

注:由于后面的相关交易公式推导涉及到了开根号,所以为了方便计算,V3 使用了 L^2 来替代 k ,实质上两者是一样的(L^2 = k)。

(x + x_virtual) * (y + y_virtual) = L^2

如上图所示,当用户的头寸被激活进行交换时,V3 会注入虚拟流动性来保持公式的计算一致性,使曲线从橙色曲线拉抬成了青色曲线。但是, x_virtual, y_virtual 并不会参与真实的交易。

如此一来,理想状态下,由于每个用户对币价的预期不同,大家都会选择自认为流动性较大的区间做市,从而自高了头寸的资金利用率,获得更多的手续费收益。但是,在得到收益的机会变大的同时,其实风险也增加了。举个例子,某用户在一个 USDC/山寨币 交换池里,往 1 USDC 换 150 - 200 枚个山寨币的流动性区间,即(150, 200)中注入了流动性头寸进行做市。若此时,与用户期望的正好相反,USDC 对山寨币升值,变成 1 USDC 换 220 枚山寨币,根据曲线,此时价格点就会离开用户的流动性区间,这时,用户提供的头寸池内构成,就会全变成了山寨币。而相比 V2 ,由于流动性区间是 (0, ∞) ,所以用户的头寸池中仍会有 USDC,相当于所有人均摊了风险。

所以,V3 的改变,相当于是给用户提供了一种高风险高回报的收益模式。当然,如果用户对市场趋势判断的信心不足,愿意降低收益的同时降低风险,也可以将提供头寸的流动性区间手动设置为 (0, ∞) (V3 的前端 UI 中也是支持这么做的),如此一来,风险收益模型就和 V2 没有区别了。

V2 的交换公式

为了更方便的理解 V3 交换公式的推导,我们先来推导下更直观的 V2 公式。

交换的公式与其实现代码,其实是在解决如下题目:在一个流动性池中,有 X,Y 两种代币,已知 X 代币的数量为 x ,Y 代币的数量为 y ,现有用户提供了 Δx 个 X 代币,求能交换出多少 Y 代币(Δy)?

我们根据核心公式:

1
x * y = (x + Δx) * (y − Δy) = k

通过左右变换与带入,可得:

1
Δy = y − (xy / x + Δx) = Δxy / (x + Δx)

并且,由于 V2 每组代币对只有一个流动性池,且手续费在每个代币对的池子里都是固定的 0.3% (V3 是允许多种手续费的,细节后文会提到),故 V2 代码直接对交易数量进行抽成。

1
2
3
4
5
6
7
8
9
10
// https://github.com/Uniswap/v2-core/blob/master/contracts/UniswapV2Pair.sol

function swap(uint amount0Out, uint amount1Out, address to, bytes calldata data) external lock {
// ...

uint balance0Adjusted = balance0.mul(1000).sub(amount0In.mul(3));
uint balance1Adjusted = balance1.mul(1000).sub(amount1In.mul(3));

// ...
}

V3 的交换公式

v3 pool

V3 的流动性池中,由于用户可以单独指定提供流动性的价格区间,故上图的整体流动性池例子中,相比 V2 是一条平滑的横线(图一),V3 更多情况下,在不同的区间,深度都不同(图三),图中的完全正态分布只是特殊情况。

例如,以下是 MATIC/ETH (手续费为 0.3%)池的头寸分布,可以看出许多头寸都在比当前价格更高的位置,或许可理解为当前市场内的做市商未来看涨 MATIC:

MATIC/ETH Liquidty

所以,我们可知,在 V3 中,一个交易是可能横跨多个用户的不同头寸的,故实际执行的,是横跨多个头寸的聚合交易。

我们先将目光限定在交易只影响一个单独头寸的情况,已知代币 X,Y 的数量为 x , y , x * y = L^2 ,以及价格 P = y / x (即可以用 P 个 X 代币,交换到 1 个 Y 代币)。可得:

v3 L P

通过带入,我们又可得:

v3 x y

即:

v3 Δx Δy

这样一来,我们仅只需知道 L 与 P ,就可知道包含了虚拟流动性的 x 和 y,不用再关心其他变量。并且有一个好处是,在同一段头寸中 L 是不变的,在切换头寸区间池的瞬间,P 是不变的。

所以当我们在使用 Δx 枚 X 代币去交换 Y 代币时时,会先用上图第一行的公式,先计算出消耗完当前所在池流动性后,新的价格 P ,然后再使用第二行公式,计算出具体在池内可交换出的 Δy 。若第一个公式中的 ΔP 已经跨过了当前池的价格区间(意味着即使当前流动性区间池的流动性被消耗完毕,依然不足以消化掉所有的 Δx ),那么就进入下一个池,继续重复上述逻辑。直到能消耗完所有的 Δx ,此时累计的 Δy 即是可交换到的 Y 代币数量。

在 V3 代码实现中,用户提供的流动性头寸的价格区间的两头,被称为两个 Tick ,上述计算,是跨一个个 Tick 来进行。

既然 Tick 是用于表示价格区间中的某个具体价格的,理论上在 (0, ∞) 这个范围内,可以有无穷多个 Tick 点。但是显然,在 Solidity 编程中,一个无限膨胀的 storage 变量是昂贵且难以接受的。

所以 V3 中,为 Tick 提供了固定的可选值,即 1.0001^i ,所以 Tick 其实是一个等幂数列。这是基于,当价格很低,用户对细小的价格变化更敏感,反之,在价格很高时,用户很大概率并不在意汇率里小数点最后面几位的区别。每一个 Tick 之间,V3 还提供一个最小间隔 i 的限制(Tickspacing),例如当 Tickspacing 为 10 时,第一个可用 Tick 是 1.0001^1 的话,那么往大第二个可用 Tick 就是 1.0001^11 。

并且,目前 V3 中只设定了三个可选费率(更多费率可经由社区治理投票在未来给出),且为三个费率设定了固定 Tickspacing ,进一步规范化计算消耗:

费率 Tickspacing 建议的使用范围
0.05% 10 稳定币交易对
0.3% 60 适用大多数交易对
1% 200 波动极大的交易对

手续费提现

关于手续费提现的问题,在 V2 中处理的比较直观。在 V2 中,由于只存在一个总流动性池,当用户注入流动性时,合约会同时给予 ERC20 代币作为凭证,当用户提现时,合约根据所持代币所占比例,给予用户总手续费收益中的提成。

但是当使用 V3 版本的自定区间实现时,如果还使用 V2 的办法,就会遇到问题。每当一比交易穿过多个 Tick 时,包含着每个 Tick 上的各头寸都要作单独记录且按比例分配。这不仅会产生大量额外的 Gas 费。且这个费用会让交换代币的用户而不是提现者承担,也是不公平的。

所以 V3 的解决方案是,在做市商每一次提供区间头寸的时候,都会给与一个 ERC721 代币,即 NFT ,里面包含了价格区间以及提供的具体流动性数量。而当用户进行代币交换时,合约会维护一个全局的手续费收入并且追踪每个 Tick 参与收集到的手续费数量。在用户提现时,先获取到头寸所有包含的 Tick 收集的总费用以及总流动性,然后根据用户 NFT 中的流动性数量占比,给与用户收益。

最后

本文为个人学习 Uniswap V3 白皮书的学习笔记,若有不准确之处,欢迎指出。:)

以太坊上或许会出现的 23 种创新

1,跨链账号

目前已经有不少 POS 链的开发者正在努力让跨链通信变得简单。

如果跨链账号成为了现实,那么不同的链都将可以轻易地调用以太坊上的只能合约。

这将释放数十亿的资本…

Interchain Accounts

2,智能合约钱包

对与去中心化金融的广泛推广来说,去中心化钱包是 100% 必要的。

这些钱包由智能合约所控制,而不是一个私钥。

这能使私钥遗失后的社交恢复,更低的 Gas 费及等等其他相关功能成为现实。

Smart Contracts Wallets

3,AI DAOs

想象一下,区块链可以和人工只能融合,一个有能力自我改进的智能合约。

无论你是否相信,已经有一些先驱开始了实验

AI DAOs 1
AI DAOs 2

4,Web 3.0

当事物都进入了数码时代后,人们将会完全改变他们对物品所有权的看法。

Web 3.0 是一个由内容的创作者驱动的开放网络。

在这个系统中没有边界,没有孤岛,也意味着平台对用户隐私的不可知。

Web 3.0

5,自动化

如果你开始在以太坊上编程,你很快就会发现一件事情…

你无法硬编码在某个时间点发生某件事情,任何事件都是由一些外部行为/因素所触发的,例如:

  • 获得
  • 清算
  • 支付

所以机器人网络是以太坊的重要基建。

Automation

6,资本效率

目前的以太坊是资本低效的。

资本流动性池被不同的协议所瓜分,例如 Uniswap,Aave 和 Sushiswap 。

第一个打开边界的平台,将会成为那个破局者,永久改变人们使用他们资本的方式。

Capital Efficiency

7,抵押衍生品

如果跨链账号和抵押(staking)衍生品在以太坊上成熟,那么将会有数十亿美元的资本从其他的 POS 链上被释放。

这些链都可以通过抵押衍生品互相在智能合约上交互。

Staking Derivatives

8,所有权切分

目前,这种模式已在 NFT 交易中出现了。

这种所有权切分使得 NFT 更能让普通投资者消费得起。

普通的投资者不再需要一大笔前期资金,当得到 NFT 时,每个人根据他们的出资获取对应比例的股份。

Fractionalization

9,创作者代币

当越来越多的人接受创作者经济(creator economies)时,我们将会看到越来越多的创作者浮现出来。

目前的以太坊中,已经有很多能够让创作货币化的应用。从这些应用中得到的收入,甚至开始超越了传统的途径。

Creator Tokens

10,边玩边赚(Play To Earn)

以太坊和 NFT 在游戏行业中的作用是毋庸置疑的。

通过加密货币经济和游戏的结合,厂商和玩家,都可以使自己的利益最大化。

并且这有着强大的网络效应。

Play To Earn

11,公平启动

在去中心化金融中,能够公平启动且公平发放代币的项目,往往更具吸引力。

不论是通过流动性挖矿,治理代币空投或其他公平启动的方式,这些项目成功的概率会更高。

Fair Launches

12,以太坊域名系统(ENS)

在以太坊 dApps 中使用 ENS ,会大大优化用户体验。

许多人仍没有意识到,他们已经具备了不通过银行,近乎实时地而向世界任何地方发送任何价值流。就如同发送电子邮件办简单。

a.eth => b.eth

ENS

13,零知识证明(zkproofs)

零知识证明可以借助加密学技术,成为一场科技界的革命。

通过零知识证明,证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。

证明者向验证者证明并使其相信自己知道或拥有某一消息,但证明过程能不向验证者泄漏任何关于被证明消息的信息。

它将把以太坊扩展成一个更大的平台。

ZK

14,合成资产

合成资产(例如 USDT)的总量,总计可以有万亿美元的级别。

基于抗审查网络的市场总量,不应被低估。

在比去中心化金融更大的生态中,这些资产也可发挥作用。

Synthetic

15,最小化治理(Ungovernance)

目标在组织中,将治理(governance)的成分降到越小越好。

最早的例子是 FLX 代币,代币将最大程度的减少对代码中PID控制器的治理。

它的这种最小化信任设计模式,非常吸引人。

Ungovernance1
Ungovernance2

16,信用代理

信用代理(credit delegation)指的是将信用在一段时间授予某人的过程。

在智能合约平台上,可以通过编程来执行这些预定义函数,而不需要互相信任。

这是去中心化金融协议在不需要借款方抵押的情况下获取流动性的一种方式。

Credit Delegation

17,资产管理工具

资产管理工具(asset managers)本质上一个被授权的,在去中心化金融平台间运行工具。

任何类型的流动性池都可被资产管理工具存入代币,在代币闲置时产生流动性价值。

这对自动化做市商来说,意味着很多…

Asset Managers

18,去中心化自治组织(DAO)

DAO 由一群任意数量的人组成,可以分布在世界各地,来进行决策的组织。

每个人根据自身持有的代币数量,来投票或提出建议。

目前已经很多大组织,已经在以这个方式运作。

DAO

19,NFT 市场

尽管 NFT 生态在去年得到了极大拓展,目前市面上仍缺少一个去中心化的,体验友好的 NFT 市场…

当有一个 dApp 能使交易 NFT 的体验就如使用 Uniswap 般方便时,NFT 市场又会迎来一波爆发。

NFT Market

20,教育

目前仍缺少正式的如何与区块链世界打交道的教育。

那些以好奇心尝试进入以太坊的用户,将是巨大的市场。

education

21,链上分析(On-chain Analysis)

在区块链中的原始数据,是很不用户友好的。

但是通过链上分析网站,即使是查看区块链大鳄的动向,也变得异常简单。

你甚至可以在链上找到未来的合作伙伴。

on-chain analysis

22,去中心化借贷协议

一个基于区块链,无偏见,非侵入式(non-intrusive),近乎实时的贷款方,将是对传统金融的一记重拳。

有了类似 Reflexer, $MKR 这样的平台和代币后,在以太坊上实现这些似乎变得越来越可行。

这不仅是加密世界的一大进步,亦是现实世界的一大进步。

decentralized lending protocols

23,L2 互操作性

当越来越多的用户开始使用 L2 roolups 方案后,互操作性变得越来越重要。

那些让以太坊得益的东西,也会存在于乐观 roolups 和零知识 roolups 平台中。

L2 interoperability

最后

在不久的将来,我相信,这些创新,在各个领域,都会成为普遍的常态。

当我们处于牛市时,牢记所有这些是非常重要的。

该文是基于推文:https://twitter.com/CroissantEth/status/1430293254684151808 的翻译,并添加了相关额外中文注解。

交易所模式总结

交易所是市场的 DNA 。交易所的内部运行模式,决定了它下面所有的交易动态。

目前交易所提供流动性(liquidity)的方式,主要有四种:

  • 中央限价订单簿(CLOB, 即 central limit order books)
  • 联合曲线自动化做市(bonding curve automated market maker)
  • 询价单(RFQ,即 requests for quote)
  • 拍卖(auction)

每种模式各有自己的优缺点,它们需要在以下这些特性优先级中做出权衡:

  • 价格发现(price discovery,匹配的买卖双方发现对方的难易程度)
  • 流动性(liquidity,资产买入和卖出的方便程度)
  • 滑点(slippage,订单请求水平和订单实际执行价格的差额)
  • 对价格波动的反应(responsiveness to volatility,对资产价格波动的响应速度)
  • 做市商的资本效率(capital efficiency for market makers,做市商的资本可否被最优化配置)
  • 可操作性(manipulability,影响资产价格的能力)
  • 可组合性(composability,组合资产的能力)
  • 防御性(defensibility,抵御外部因素攻击的能力)

订单簿模式(最常见的模式)

中央限价订单簿(CLOB)就是一本由出价和报价组成的权限透明账本,从最好价开始依次排序(两边分别是参与者愿意买/卖的价格)。

所有的参与者都能看到所有的报价和出价,他们也可以参与其中。

订单簿中两边的第一行,即是最好的报价/出价。

CLOB1

订单匹配

举个例子,如下图,是一个包含了前三行的中央限价订单簿(CLOB)。

  • 订单簿中所有的订单,都是“剩余订单”(即还没人买的报价单和还没人卖的出价单)。
  • 买卖数量(qty)即是这个价位所有订单的数量总和。

CLOB2

这时,Alice 创建了一个买入订单:BUY 2@9652 (以 9652 的价格买入 2 份)。

她的买入订单价格“越过(crosses)”了第一行的最好价卖单:OFFER 1@9651 (以 9651 的价格卖出 1 份)。

所以,Alice “拿下(takes)”了 OFFER 1@9651。

但是如果她想要两份,剩余的买单不足以匹配她的价格。

所以剩余的一份买单被继续留在了订单簿中。

CLOB3

一个多份订单如果“越过”了多行,就可以“拿下”这些行,从而让这个账本簿变得更薄。

举个例子,如果 Bob 给出了一个:OFFER 4@9649 的卖单,那么前三行买单都会被满足:
1@9652
2@9650
1@9649

所以订单簿变成了这个样子:

CLOB4

滑点

至此为止,给出的都是限价(limit)单。

现在我们假设,在图二的状态中,Bob 给出了一个 OFFER 4x 卖单(不限价卖出四份)。

对比最高价 9652,Bob 的平均收入是 (19652+29650+1*9649)/4 = 9650.25 。

这种情况下,由于订单簿太薄导致了滑点,Bob 每单损失了 1.75 。

一些使用订单簿模式的交易所

传统金融:

  • 纽交所
  • 纳斯达克
  • 芝加哥商业交易所
  • 芝加哥期权交易所
  • 伦敦证券交易所
  • 港交所

CEX(中心化加密货币交易所):

  • FTX
  • Coinbase
  • 币安
  • 欧易
  • 火币

DEX(去中心化加密货币交易所):

  • Serum
  • Raydium
  • Dexlab
  • Slope
  • dydx(链下账本簿)

订单簿模式的权衡

优势:

  • 透明的流动性
  • 市场是不对称的
  • 做市商可自由出入
  • 做市商可以自由决定价格与数量

劣势:

  • 冷启动问题(很难给出初始流动性)
  • 对非流动性资产不利
  • 如果是链上交易所,则对链的 TPS 的要求很高

为什么以太坊上的订单簿交易所很少

以太坊的 TPS 对于支撑链上订单簿的实时更新来说,太低了(故大多数的 DEX 使用的都是自动化做市商模式)。

一个例外是,dydx,它使用了链下订单簿(所以向订单簿发单和价格更新都是链下的,仅在链上处理最终交易)。

反面例子是,Solana 链由于其 60K 的 TPS,导致了其上有许多订单簿模式的交易所。

自动化做市

针对去中心化交易所的 TPS 问题,自动化做市模式孕育而生。

自动化做市模式,可以想象成是一系列的货币交换机器(例如 ETH/USDT,MATIC/USDT,ETH/MATIC 等等)。

交易所里没有订单簿。只有一系列预设的函数,为各类货币的互相交换来定价。

这些预设的函数(例如 x*y=k)基于两头货币在各自流动性池中的供给变化率,来设定价格。在某个货币的流动性池内,任何人都能够提供该种货币以增加其流动性,从而获得收益。

更多流动性池详情可参阅:https://youtube.com/watch?v=cizLhxSKrAc

AMM1

一些使用自动化做市模式的交易所

传统金融:

CEX(中心化加密货币交易所):

DEX(去中心化加密货币交易所):
— 以太坊 —

  • Uniswap
  • Curve
  • Bancor
  • Balancer
    — Solana —
  • Saber
  • Orca
  • Raydium (自动化做市与订单簿皆有)

自动化做市模式的权衡

优势:

  • 对于新的代币,可以很方便的冷启动
  • 去中心化
  • 代币交换可组合性很高

劣势:

  • 强制性的市场对称
  • 所有价格点的统一流动性(在 Uniswap V3 中已解决)
  • 滑点频繁
  • 波动性大,经常有很大的临时亏损(流动性提供者在平均表现上是盈利的)

询价单模式

询价单(RFQ)模式通常被用于流动性更低的交易市场中(例如,固定收益产品,金融衍生品,开放式指数基金)。

该模式让交易者基于产品和数量,向交易方(特定交易所内的参与做市商)“提出一个报价”。

所以询价单模式是非对称的:

  • 交易者之间不能自由报价,因此他们之间不可互相交易,交易者仅能和交易所内的参与做市商进行交易
  • 没有公开的订单簿
  • 有腐败风险

所有场外交易市场(OTC)都是以询价单模式运行的。

一些使用询价单模式的交易所

传统金融:

  • Tradeweb
  • 任意大型银行的结构性产品柜台(花旗,美林等等)

CEX(中心化加密货币交易所)

DEX(去中心化加密货币交易所)
— 以太坊 —

  • 0x
  • Hashflow
    — Solana —
  • 无?

询价单模式的权衡

优势:

  • 对交易频率低的非流动性资产有利
  • 在去中心化金融社群中,由于很少有人知道它,所以社交性接受度(socially acceptable)很好

劣势:

  • 缺乏透明度
  • 非真正的去中心化(订单的保存和匹配都是链下的,仅完成交易是链上的)

拍卖模式,又名”主要工作都在拍卖前“(it’s all about the pre-auction)

纳斯达克如何在每天早晨,设定股票定价:

9 点 - 9 点 30 分:纳斯达克向交易者传输历史订单数据,让交易者调整报价。

如果有迟到的突发新闻,纳斯达克会让指定的做市商调整报价。

一个指定做市商(designated MM)会被给与指定证券的特殊权限:

  • 做出价格调整
  • 对指定的证券延迟交易的开始时间
  • 获得第一批证券(如果需要“维持市场的平稳运行”)

指定做市商也会得到补充流动性做市商(supplemental liquidity providers)的帮助。补充性流动性做市商,是纳斯达克通过高回扣和红酒以说服它们向市场注入流动性的高频交易商户。

下图是纳斯达克目前的补充流动性做市商:

AUCTION1

9 点 30 分之后:

市场终于开放。任何人其他的 MOOs 和 LOOs (市场开始时交易 & 限制取消时交易)得以机会可以被执行。

拍卖模式的权衡

优势:

  • 激动人心(所以对 NFT 很有效)

劣势:

  • 高度可操控性
  • 可以轻易的给与特定的机构特权和激励
  • 低效,可扩展性低

结尾

各类交易所得设计模式,都有各自的权衡。我们能做的,就是根据资产的特征,挑选最合适的交易所模式进行交易。模式是至关重要的,因为它塑造了生态中的所有后续交易行为。

该文是基于推文:https://twitter.com/FabiusMercurius/status/1452349285865984000 的翻译,并添加了相关额外中文注解。

[译] NTF 和 1000 个真粉丝

在一篇 2008 年的经典文章 “1000 个真粉丝” 中,Kevin Kelly 预言,互联网将会改变创意活动的经济运行规则。

在互联网时代,如果你想成为一个成功的内容创造者,你不需要有 100 万美元,不需要有 100 万客户,也不需要有 100 万粉丝。想在互联网时代成为一名手艺人,摄影师,音乐家,设计师,作家,开发者,企业家或者投资人,你仅需要有 1000 个真粉丝。

真粉丝的定义是:他会购买一切你生产的内容。这些硬核粉丝会开车 200 公里来看你唱歌;他们会购买你的书的纸质版,电子版和语音版;他们会预定你尚未完成的雕像;他们会购买你免费 YouTube 频道中视频的“精选集”;他们会每月定期来你掌勺的饭店消费。

Kelly 的愿景是互联网将是 21 世纪终极的“媒人”。无论是多小的创作者,都能通过它找到自己的真粉丝。这些真粉丝会实实在在的在经济上支持他。

但是当前的互联网并非如此。中心化的社交媒体平台,成为了创作者和粉丝之间的主要连接平台。这些平台成为了中间人 - 使用广告和推荐算法,将粉丝对创作者的经济支持中的很大一部分,变成了他们自己的利润。

好消息是,当前互联网正在朝 Kelly 的愿景发展。例如,很多顶级作家在 Substack 网站里的收入,远远超过他们在本职工作中的收入。“薄利多销”正在发挥着作用。在 Substack,1000 个 10 美元/月的订阅者,成就了一个 10000 美元/月收入的创作者。

加密资产,特别是 NFT(非同质化代币),也正在加速这一趋势。社交媒体平台将继续发挥吸引粉丝的作用(尽管这也很可能会被更好的去中心化方案所替代),但是创作者们可以使用像 NFT 这样的去中心化方式来直接赚钱。

NTF 是基于区块链的一个具有唯一独特性的数码资料。这些数码资料可以是任意的,包含艺术创作,视频,音乐,GIF,游戏,文字,表情包和代码。NFT 中包含了高度可信的来源标识,并且可以包含任意可执行的操作代码(例如保证创作者每月可以获得指定的收入)。NFT 和比特币具有相同级别的安全性与可靠性。

在过去 30 天里,产生了超过 30 亿美元的 NFT 交易:

sales

正如加密货币的发展,有着起起伏伏。NFT 的发展,可能也会伴随着兴衰。

笔者认为,有三个原因,导致了 NTF 将会为创作者提供更好的经济收益。第一个原因,正如之前所述的,就是移除了逐利的中间人。一旦你购买了一个 NFT ,你就拥有了它的完全控制权,就像你在现实世界里购买了一本书,一个滑板一样。当前的中间人市场和 NFT 市场都会继续并行存在,但是消费者可以货比三家,来促使中间人减少提成费用。

第二个原因是,NFT 可以提供任意精度的价格分层。在传统的基于广告的中间人平台里,不论粉丝的热情如何,产生的收入都是一致的。在 Substack 中,创作者可以为付费更多的用户,提供更多的“专属福利”。NFT 可以比传统的非加密产品方案走的更远,它可以提供任意精度的定价层级。例如,如果你拥有比特币,且想购买 NBA Top Shot 卡片,根据你的热情程度,你想买多少就可以买多少,不同的卡片,价格可以精确到小数点后六位。数字加密货币的细粒度,可以让创作者拥有更大的自由来捕获各色需求。

curve

第三个且笔者认为最重要的原因是,NFT 让创作者的获客成本大大降低,甚至能做到接近于零。打开任何的技术 S-1 文件,你都会看到大量的获客成本,通常是基于广告和销售人员的。反观加密货币,总市值已经超过了一万亿美元,而它们的背后,没有任何的组织给出过任何的营销预算。

当前最火的 NFT 项目,NBA Top Shot,仅仅只花了一点点市场营销费用,在上个月就产生了 20 亿美元的销售收入。它之所以会发展的如此迅速,正是因为用户感受了到他们就是卡片的主人。这是一个真实的端对端的市场,由社区,热爱和自主性所驱动。

twitter

NFT 目前仍处于一个早起阶段,它还将不断发展。未来更多的产品将会围绕它而构建,例如市场,社交网络,展览,游戏,虚拟世界等。未来某一天,每个互联网社区都可能拥有自己的微观经济,其中包含了用户可以使用,收集和交易的 NFT。

1000 个真实粉丝理论建立在一个互联网理想之上:全球的创作者和用户自由连接,不受中介平台的约束。现有的社交媒体平台将两边都放进在了中心化和货币化的枷锁之中。因此,相应的,有两种方式可以来解放这种枷锁:解放用户,或者解放货币。加密货币和 NFT 为我们提供一种解放货币的新方式,希望它能成为主流,成为现实。

原文链接:https://future.a16z.com/nfts-thousand-true-fans/

足球阵型探讨

前言

足球阵形,是指在一场足球比赛中球队如何将球员布署在球场上,是主教练为球队获胜而制定的比赛战术的主要体现。本文会分别探讨主流阵型的一些个人理解。

4-4-2

4-4-2

一个拥有双前锋,边锋的四后卫体系阵型。该阵型主打攻守转换,中场控制力稍弱,由于双前锋的存在,会让该阵型在反击中非常犀利。不过双前锋的代价为仅有两个中场,所以在阵地战阶段,还是以主打边路为主。

4-3-3

4-3-3

一个单前锋,三中场的四后卫体系阵型。由于仅有单前锋,故无法在反击中打得像 4-4-2 那么直接。不过三中场优势体现在了出球阶段,与阵地战阶段。在出球阶段,较易产生中场的人数优势,从而将球顺利过渡到对手的防守三区。在阵地战时,可以双边后卫套边压上,也可双中前卫肋步压上,形成 2-3-5 压制体系,主打边路进攻与肋步进攻。

4-2-3-1

4-2-3-1

同样也是一个单前锋,三中场的四后卫体系阵型。不过于 4-3-3 不同的是,4-2-3-1 为双后腰体系。在保持中场控制力的同时,增强了中场后腰的防守屏障,但同时也损失了一名进攻的中前卫。阵地战中由于只有单前腰,所以对于前腰的能力要求更强,需要其有更强的持球能力,并且有更好的体能做串联与肋步的压上。

3-4-3

3-4-3

单前锋,有边锋的三中卫体系阵型。相较于 4-3-3 ,少了个中场,多了个中后卫。在阵地战阶段,可以形成 3-2-5 的压制体系,防守时,可以回到 5-4-1 体系,对于中场的能力要求更高,但是由于拥有三中卫,被直接反击到锋线的风险会更小。

3-5-2

3-5-2

同时拥有双前锋,三中场的三中卫体系阵型。若拥有合格的翼卫,则在进攻时可以比 4-4-2 多一名中场。相较于 3-4-3 ,打法上更为侧重中路,防守时则由于存在双前锋,中场对于宽度的保护压力比较大。

所理解的经济

是什么,为什么

按照维基百科的定义:经济一词用于统称一定范围(国家、区域等)内,组织生产、分配、流通、消费活动和关系的系统,通常以货币为媒介,以商品或服务为结果。根据定义就可以理解到,只要生活在现代社会,经济就与每个人的生活息息相关,上学、工作、衣食住行、精神满足,都与我们所处国家/区域内的经济的体量、质量、发展方式息息相关。

为什么发展经济很重要?以现代国家的角度来看,对外的综合国力,对内的民生,都依赖于经济的强大。

从国家角度来看,对外,若生产力,生产效率低下,则会导致经济发展缓慢,经济体量萎靡,在国际社会中无法提供任何其他国家所需的各方面筹码,视如无关紧要的弃儿。从国内社会的角度来看,历史的进程屡次表明,经济发展是社会稳定的一大基础,若经济出现问题,则民生就会出现问题,那么就会导致社会动荡,文化倒退,国内政权被颠覆于内部革命或外族侵略。

以个人角度,经济体量的发展带来更多人参与进入有利可图的、结果非零和的社会协作中,通过良性竞争,带来了社会整体文化素质的提高,生活愈发安全稳定,生活质量的理想上限提高,进一步促进个人奋斗的意愿,从而进入社会发展风气的良性循环。

运行

以基本的供需模型为视角来分析。运行的第一阶段,以满足存量的未满足供需为主,特征为各行各业创业者百舸争流,总体入行门槛相对低,生产效率要求相对低。等到了绝大多数存量需求已被满足后,则进入了运行的第二阶段,以提高生产效率为主,特征为行业格局基本形成,市场内对数量的满足已经足够,转而对质量开始有了更高的要求,此时行业进入门槛增高,生产效率要求愈发高,促使行业中的实体不断精益求精。

经济体中的各行各业为满足其市场的需求不断以此运行轨迹,进入,竞争,强者生存、弱者淘汰。

那么如果各行各业的需求,存量需求都已满足,效率提升经过充分发展增速陷入瓶颈时,会如何?此时整体经济发展便会失去了增长空间,陷入停滞。这时,社会中便可能会在整体奋斗欲,治安,年龄结构等方面出现问题。

但是科技在这个循环中起到了不断拓展横向和纵向边界的作用。依赖科技的进步,不断使原本无法做到的事情,变为可能,从而拓宽了需求的边界,从而产生更多的行业。新技术同时亦有可能为现有的生产方式提供更高效,稳定,安全的生产方式方法与工具,从而突破已有生产力的瓶颈。

理想情况下,若在已有行业的横向与纵向边界都被探索完全之前,引入新科技所带来的横向纵向边界的拓展,则经济运行发展的车轮趋势上便能不停歇的滚滚向前。反之则可能会引发社会问题,使经济陷入衰退,待社会再次稳定后,进入重新一轮的发展,重新补充衰退的存量,同时在存量探索完全之前,期待边界的拓展,避免进入又一次社会动荡循环。

工具

货币是媒介,金融是其润滑剂。

作为交换媒介,经济体中的货币理想中应等同于经济中现存的价值总量,一个人所获得的货币收入,理想中应等同于其在经济体中创造的价值总量。国内经济体量在壮大时,央行应根据每年预测的发展幅度,发出对应的货币以满足价值交换的需求。若由于各种内外部因素,预测失准,多发了,则导致通货膨胀,少发了则导致通货紧缩。当然,在如此复杂的一个系统中,要做到完全精准匹配是不可能完成的任务,加之有理论认为,温和的通胀有利于拉动需求侧,从而促进供给,故主流做法是将通胀控制在 2% 左右。

金融的主要体现方式为借贷。为有能力而没资本的人提供资本,并以商议的利息作为补偿,因而产生了润滑剂的作用。理想情况,它使资金不足,能力有余的人,通过杠杆的力量,承担一定的风险,来完成意图的经济活动。

指标

GDP即国内生产总值,为主流的用于衡量国内经济体量的指标,通过国际间的横向对比,基本可知国家间的竞争力水平。

CPI即消费者物价指数,为主要通过一些与民生息息相关的产品的价格变幅来指示出当前的通货膨胀率的一个指标。若长期偏高(如 >5%),则有通货膨胀风险。今年来,除了政治因素以外,为了对抗经济发展的波动性,以及相应产生的金融危机,政府也通常愿意采用量化宽松(即打开印钞机)的方式来刺激经济,这也是导致 CPI 指数偏高的一大原因。为了应对这种情况,在这种情况下,意图降低 CPI ,让民生相关的产品物价稳定,从而维持社会基本面稳定,则需要将钱导流至对应的蓄水池中,目前,美国的水池是股市,中国的水池是楼市。

另有一个重要理论与经济的稳定性比较相关,就是蒙代尔三角:资本的自由流动、汇率的稳定、独立的货币政策,三者在政治实体中,只能同时保证二者。目前中国通过央行购汇,选择了汇率的稳定以及独立的货币政策,放弃了资本的自由流动,个人浅解主要考虑还是,若放弃了独立的货币政策,则丧失了对经济波动周期的调控能力,是不可接受的,若放弃了汇率的稳定,则有可能被境外大额资本大进大出,导致汇率市场不稳定,也不利于出口导向的贸易国策。

方法论

主流上有两种方法论,资本主义、民本主义,各有优劣。主要体现在政府与企业在经济中所发挥的作用大小对比不同。

资本主义方法论下,企业法人唱主角,一切的经济活动,以企业法人为主,同时保护产权,激励回馈上,关注企业为股东带来的收益。政府在经济中所扮演的角色则相对“小”。优点也很明显,通过纯粹的竞争,能够最大化发挥人的主观能动性,精益求精,从而把经济蛋糕做大。缺点也比较明显,在自由竞争中,总会出现强者越强,弱者越弱,导致社会发展两极分化。

民本主义,虽也以自由竞争为土壤,收益回报为激励,但都不会凌驾于政府对于经济的宏观把控之上。由于调控的存在,对于人们主观能动性,积极性的调动会有所削弱,但是优点在于能够制衡人性的利己,进一步促进全社会整体均衡发展,在上下限中,能尽量做到更平衡。

最后

作为普通人,最好的策略,还是选择能到达的,且自己价值观最认可的方法论环境中,结合个人情况,以及行业的发展进程所需的能力,科技进步带来的边际拓展,经济各周期所释放机会,做出最好的选择。