Qtum 研究院：预编译合约及其在隐私资产中的应用

来源 | Qtum 量子链

背景知识

1、智能合约
以太坊中存在外部账户和合约账户两种，外部账户（Externally Owned Account, EOA）是被私钥控制且没有任何代码与之关联的账户。而合约账户 (Contract Account, CA) 是给智能合约分配的账户，被合约代码控制且有代码与之关联。外部账户可以发送交易，这个交易可以是转账交易，也可以是和智能合约有关的交易，用于创建智能合约或者触发智能合约。
以太坊的每笔交易 Transaction 会被转换成一个 Message 对象，传入 EVM 中执行，随后 EVM 将 Message 对象转换成 Contract 对象。如果是一笔普通转账交易，那么直接修改 StateDB 中对应的账户余额即可。如果是智能合约的创建或者调用，则通过 EVM 中的解释器加载和执行字节码，执行过程中可能会查询或者修改 StateDB。从图中可以看出，Contract 对象会根据合约的地址，从数据库中加载相应的合约代码，然后送入解释器中进行执行。

生成 Message 对象

生成 Contract 对象

EVM 解释器是一个基于栈式的机器，它有自己的 PC、堆栈、内存和 Gas 池。一份合约代码会被解释为一条条 OPCode，然后执行。在执行 OPCode 之前会检查该命令所需要的 Gas 和当前所剩 Gas，如果 Gas 不足，则会返回 ErrOutOfGas 错误。因为 EVM 是基于栈的虚拟机，没有寄存器之类的中间存储，所有的操作都要通过一个栈来进行维护，所以它的运行效率比较低，完成一个复杂操作可能需要较长的时间。更复杂的操作可能无法在有效时间执行完毕。

EVM interpreter 内部逻辑

2、隐私资产
区块链是公开的分布式交易账本，链上的数据都是公开可见的，虽然一笔交易的发送方和接收方无法和现实生活中买卖双方进行关联，但是可以通过对链上的数据进行地址聚簇分析，从而得出一些地址和身份的关联信息。交易的金额在链上也是公开的，可见，尽管数据的公开透明保证了账本真实和不可篡改的特点，但是这也使得很多需要隐私的场景无法在区块链上进行运用。
在此背景下，隐私资产的概念被提出。通过使用密码学等技术手段将交易的发送方、接收方和交易金额进行隐藏，而矿工 (验证交易者) 可以在不需要知道具体数据的情况对一笔交易的合法性进行验证。常用的隐私资产实现的方法有 Mimble-Wimble、ZK-SNARK 等。
由于合约模式的广泛使用，一些项目方想到可以通过使用智能合约来实现隐私交易，如 Nightfall、Zether、AZTEC 等，通过部署和隐私交易有关的智能合约来达到在链上发行隐私资产的目的。

*预编译合约*

1、预编译合约的概念
因为 EVM 是基于栈的虚拟机，它根据操作的内容来计算 gas，所以如果牵涉到十分复杂的计算，把运算过程放在 EVM 中执行就可能十分的低效，同时消耗非常多的 gas。比如在 zk-snark 中，需要进行椭圆曲线的加减和配对运算，这个过程十分复杂，放在 EVM 中执行是不现实的。这就是以太坊提出预编译合约的初衷。
预编译合约是 EVM 中为了提供一些不适合写成 opcode 的较为复杂的库函数（多用于加密、哈希等复杂运算）而采用的一种折中方案，适用于合约逻辑简单但调用频繁，或者合约逻辑固定而计算量大的场景。预编译合约通常是在客户端用客户端代码实现，由于不需要使用 EVM，所以运行速度快。对于开发者来说比直接使用运行在 EVM 上的函数消耗更低。
现在以太坊已经实现的预编译合约如下：

从代码层面来看，所谓的地址其实就是合约数组的下标，一个下标标识了一个预编译合约。其中和隐私算法有关的三个预编译合约是 bn256Add()、bn256ScalarMul()、bn256Pairing()。
2、预编译合约的实现
在 evm.go 文件中，封装着 evm 的操作逻辑，里面有 4 个函数用于调用智能合约，Call()、CallCode()、DelegateCall()、StaticCall()。这四个函数做的工作都是生成一个 contract 对象，但是具体的细节如参数等会有一些差异。contract 实例化之后，都是调用 evm.go 中的 run 函数来运行智能合约。该函数对预编译合约和非预编译合约调用两种情况均有考虑。下面的代码中，第一个分支是当该合约是一个预编译合约的时候，通过指定 precompiles 这个数组变量的下标来指定某一个预编译合约，从而实例化 p 参数。此处数组的下标其实就对应了预编译合约数组声明时地址的概念。之后调用 RunPrecompiledContract 函数来执行预编译合约。而如果是非预编译合约，从代码中可以看到是调用了 evm 的解释器进行执行。
go-ethereum/core/vm/evm.go
在 RunPrecompiledContract 函数中，可以看到 p 变量实现接收器进行 bn256 曲线加的操作，然后将结果进行返回。可以很明显地看到这部分操作是在客户端语言的执行过程中进行计算的。

go-ethereum/core/vm/contracts.gogo-ethereum/core/vm/contracts.go
3、预编译合约的使用
在智能合约代码中，预编译合约也像普通的合约一样，可以直接在合约文件中进行调用，但调用方式有一些不同。通过在 .sol 文件中注明一个 assembly 代码块进行预编译合约的调用。调用规范和调用的参数如下所示。

一个实现椭圆曲线加法的实例如下

*预编译合约在隐私资产中的应用*

1、椭圆曲线的预编译合约

以太坊现在处理隐私的解决方案是使用 zk-snark，但是 zk-snark 是一个极其复杂的数学过程，里面牵涉到很多椭圆曲线的计算。经过前面的分析，这个过程放在 EVM 里面执行是十分不现实的，所以为了支持 zk-snark 的相关运算，以太坊分别在 EIP-196 和 EIP-197 里增加了三个与 zk-snark 运算有关的预编译合约，可以供开发者调用。
EIP-196 增加了在 alt_bn128 曲线上的 ECADD() 和 ECMUL() 两个预编译合约，其中 ECADD() 消耗 500gas，ECMUL() 消耗 40000gas。
EIP-197 增加了在 alt_bn128 曲线上的配对 Pairing 函数，消耗 gas 为 80000k+100000(k 和点对个数有关)。
椭圆曲线上的加和乘比较好理解，pairing 的出现是因为 zk-snark 中有 KCA(Knowledge of Coefficient Test and Assumption) 认证过程，需要用到双线性映射来进行证明，具体可参见 V 神 medium。Pairing 就是证明过程中会用到的公式。Pairing 函数的输入是一个不定长的列表，因为不同的 zk-snark 算法可能数据量是不同的，并且 pairing 函数所消耗的 gas 也与输入的点对个数有关。
现在许多利用预编译合约实现隐私的算法都使用到了 pairing 过程，例如 EYBlockchain、AZTEC 等。pairing 是 ZK-snark 所必须要求的一个步骤，耗费的 gas 巨大，当然官方也在做优化。实现 pairing 的过程一般要在 pairing-friendly 曲线上来进行，这是一类具有特殊属性的曲线，主要表现在计算 pairing 速度很快。所以如果要用 pairing 这个过程，那么常用的 secp256k1 这样的曲线显然是不适合的，就需要增加对 pairing-friendly 曲线的支持。
现在主流的 pairing-friendly 曲线有 Barreto-Naehrig(BN) 系列和 Barreto-Lynn-Scott(BLS) 系列，以太坊使用的就是 BN 系列，ZCASH 使用的是 BLS 系列，以太坊后续也会加上对 BLS 曲线的支持。BLS 的曲线综合表现会好很多，计算量也相对较小。但是不管怎么样，选择曲线都有安全和效率之间进行平衡的一个取舍。
值得一提的是，如果不需要用到 pairing 过程，也就不需要 pairing-friendly 曲线。另外一种方案是增加对 secp256k1 曲线的预编译合约的支持。例如 PGC 团队虽然使用了 bn256ADD 和 bn256MUL 两个预编译合约，即使用了 bn 系列的曲线，但是他们的算法是不需要 pairing 的，如果换成对 secp256k1 的预编译合约支持会对算法效率有提高。
针对于 C++版本实现的问题，现在主要有两个外部库对这些操作进行了封装和实现。首先是 Libff，这也是现在以太坊正在 使用的库，源码中 LibSnark.cpp 调用了 libff 库的相关计算函数。还有一个是 MCL 库，这是 EIP-1108 所推荐的库。
2、隐私资产项目*
现在在业内比较流行的四个隐私解决方案是 EYBlockchain、PGC、Zether、AZTEC。
EYBlockchain 是基于以太坊 zk-snark 零知识证明实现的隐私资产。它通过移植以太坊推荐的 ZoKrates 工具包进行线下的零知识证明的生成。算法需要用 bn256 曲线的 add、multiply、pairing 过程。一笔转账 Gas 消耗在 2.7M 左右。
Zether 是一个以太坊上的匿名支付协议，以智能合约 Zether Smart Contract （ZSC）的形式部署在以太坊上，并且具有称为 Zether 令牌（ZTH）的代币，其可作为 ElGamal 公钥的 Zether 账户之间传输的载体，并支持匿名的智能合约交互。算法需要用到 bn256 曲线的 add、multiply 算法。
PGC 是改进版的 Zether 算法，PGC 使用原版的 Elgamal 和原版的 bulletproof 零知识证明算法。PGC 使用了 bn256 曲线的 add、multiply 算法，但是，如果 secp256k1 椭圆曲线的预编译合约可以实现，那么 PGC 算法可以不使用 bn 系列的曲线。
AZTEC 结合同态证明和 range proof 提供零知识证明，以在以太坊上提供隐私资产。AZTEC 需要使用 bn256 曲线上的 add、multiply、pairing 操作，具体操作量为 (3n+m-1)add+(2n+2m-2)multiply+1pairing(n 和 m 分别是交易票据的数量)。
3、gas 问题
EIP-196 和 EIP-197 的提出，使得很多零知识证明的算法可以在以太坊上运行。但还是有一个问题，尽管把这些复杂的数学过程通过预编译合约的方式来实现，它所消耗的 gas 还是十分巨大，不夸张地说，在某些场景下，转账一笔隐私资产所消耗的 Gas 可能比转账的金额还要高。以太坊每个 block 的最多 gas 消耗为 8M，这就使得很多隐私的项目无法真正地落地。

为了降低预编译合约的 gas，AZTEC 的员工提出了 EIP-1108 的改进。
EIP-1108 是对 add、mul、pairing 这三个预编译合约所做的一个优化，通过对调用库的底层算法进行优化，提高了代码的运行效率，从而降低了 gas。Golang 版本的预编译合约名也变成了 bn256。bn256 就是 alt_bn128，只是更换了一个说法。256 是指公式中 p 的长度，而 128 是指曲线的安全等级。这是一条曲线的两个不同的属性描述。所以 EIP-1108 并不是更换了曲线降低了 gas，而是对实现的算法进行了优化。更新后的 gas 对比图如下。EIP-1108 目前处于 draft 的状态，代码中算法部分已经进行改进，但是 gas 的值还没有进行更新。

若使用 EIP-1108 的改进方法，许多隐私资产的算法可以得到大大的优化。Zether 一笔转账交易 gas 消耗可从 7188000 减少到 1700000。PGC 一笔转账交易 gas 消耗可从 6563000 减少到 1100000。AZTEC 则从 121000n+41000m+219000 降低到 12200n+6200m+85930。
如果要部署预编译合约，如何确定预编译合约的 Gas 值是一个严峻的问题。预编译合约 gas 的设置是和操作的计算量有关的，例如 EIP-1108 中介绍了 Pairing gas 的计算方法。它是根据 ecrecover 的效率和既定 gas 来决定的。一次 ecrecover 调用需要花费 116ms，它的 gas 被设置成了 3000，这样得到了 1ms 运行花费 25.86gas 的事实。因为 pairing 计算花费的时间分为两个部分，一个是基时间 base_tim，可以理解为运算的启动时间，还有一个是浮动时间 per_pair_time，它和输入的计算量有关。计算 1 个 pairing 需要耗费 3037ms，计算 10 个 pairing 耗费 14663ms。得出 base_time 和 per_pair_time，乘以既定好的 25.86gas，得出 pairing 过程的 gas 消耗。如此，则可以根据具体的环境做相关的 benchmark 以规范 gas 的设置。

Qtum 与隐私资产

Qtum 每个 block 的最多 gas 消耗为 40M，每个 transaction 的最多 gas 消耗为 20M，因此隐私资产在 Qtum 上运行基本不会受到 gas 的限制。但是使用 EVM 去运行一些计算量大的隐私算法是非常低效的。所以，未来将会把一些基础的、通用的隐私算法做成预编译合约的形式，让隐私资产能够更加高效地运行在 Qtum 上，也节省了合约的开发工作。
对于椭圆曲线而言，下一步可以考虑增加 BLS 和 secp256k1 椭圆曲线的预编译合约。BLS 的性能和安全性都优于 bn256，且是 pairing-friendly，所以可以用于代替 bn256。并且如果要部署 pairing 预编译合约，也可以找一个已经定好 gas 的预编译合约进行参照，分别 benchmark，进行类似的 gas 设定。secp256k1 虽然不是 pairing-friendly，但其性能更好，且通用性更强，广泛用于区块链的签名、加密算法中。
对于零知识证明而言，未来可以考虑增加 Bulletproof 算法作为预编译合约。Bulletproof 是目前区块链中广泛使用的范围证明算法，主要用于证明 MimbleWimble 中隐藏的交易金额是一个正数。Bulletproof 已经在 Grin 和 Beam 项目中实现并稳定运行。Bulletproof 的验证过程计算量大，因此使用预编译合约实现是更为合适的选择。有了 Bulletproof 预编译合约之后，MimbleWimble 就能以合约的方式高效地运行于 Qtum 上。

Qtum 量子链 作者

Sonny Sun 编辑

   Roy   **排版******

内容仅供参考 不作为投资建议 风险自担

版权所有 未经允许 严禁转载

本文转自公众号“Qtum 量子链”

原标题为《Qtum 研究院：预编译合约及其在隐私资产中的应用》

☟☟☟