智能合约的分段同态加密研究*

王沛然 李加福 雷志伟 张桂刚 张 勇 邢春晓

（1.清华大学行业可信区块链应用技术联合研究中心，计算机系，信息技术研究院 北京 100084）（2.中国科学院自动化研究所 北京 100190）（3.清华大学北京信息科学与技术国家研究中心，计算机系，信息技术研究院，互联网产业研究院 北京 100084）

1 引言

区块链技术从Bitcoin发展到Ethereum之后，支持图灵完备的编程语言的智能合约的引入［1］，使得Ethereum成为可以支持开发和运行DApp的系统。而Ethereum的智能合约被调用并形成交易后，需要网络上其他节点对其正确性进行验证［2］。智能合约调用及验证的过程如图1所示。

图1 Ethereum智能合约调用及验证过程

在图1中，智能合约调用者即交易发起者，其调用合约时使用的参数全集，必须是明文且公开的，如此，网络上的其他节点即智能合约验证者才能根据这个参数全集来验证该智能合约执行结果是否正确。

显然，这样的验证方式，对于智能合约调用者节点来说，没有任何隐私保护可言［3］。对此，Ethereum技术团队也曾坦言，由于同态加密技术远不能够支持图灵完备的智能合约语言，所以只好放弃了智能合约调用过程中的加密功能。

与技术上的障碍相对应的，是一些应用场景对于智能合约加密的迫切需求。事实上，有很多可以运行在Ethereum或类似区块链上的应用场景，都是需要保护隐私的。例如：需要多方参与的竞拍竞价、竞选投票之类的应用［4］，各方调用智能合约的输入都是需要被保密的。再如：医疗健康数据会涉及到个人隐私，因此信息持有者在通过调用智能合约来分享相关信息的时候也会有顾虑。

由于全同态加密技术距离支持图灵完备的智能合约语言还有很长的路要走，所以业界目前普遍采用一些折衷的办法，例如Commit-Reveal办法［5］：通常是将智能合约的输入参数中加入盐，从而在保护原参数的前提下，让其他节点可以验证合约的调用情况，并在未来通过提供具体的盐的方式，来证明调用者知晓相关的调用参数。

2 同态加密

同态加密是基于数学难题的计算复杂性理论的密码学技术，其概念可以简单理解为：对经过同态加密的密文数据进行运算所得到的结果，与对数据原文进行同样运算后得到的结果再进行同态加密的结果，恰好是一样的［6］。正如如下公式所示：

其中，f（）为数据处理方法，E（）为同态加密算法。

同态加密概念来自于代数学，通常分为加法同态和乘法同态。而如果同时满足加法同态和乘法同态，则称该同态加密算法满足全同态。自1978年同态加密概念被提出以来，寻找满足全同态的加密算法成为了开放性的密码学难题。直到2009年，IBM的Craig Gentry才突破了这一难题［7～8］。

同态机密技术首先被应用于云计算中，而对于区块链技术，同态加密同样是很好的支撑技术。在实际的行业应用里，同态加密更多被用作普通交易数据的保护，特别是对交易金额和账户余额等信息进行保密。例如：华为区块链提供了同态加密库，可以将用户账户和账本数据以密文形式保护，并且交易也采用密文运算［9］；趣链（Hyperchain）同样采用同态加密的办法来保护账户及交易的隐私性，同时保留其在网络中的可验证性［10］。

值得一提的是，行业中选择同态加密的区块链，更倾向于使用满足加法同态的Paillier算法［11］。该算法于1999年被Paillier发明，基于复合剩余类的困难问题，其原理此处不再赘述。由于该算法必然会产生密钥，所以其在工程领域应用的时候，需要有配套的密钥管理机制，包括创建、保存、颁发、撤销等。除了Paillier算法外，满足乘法同态的El-Gamal算法［12］也常被业界使用。它是除RSA外最具代表性的公开密钥密码之一，其安全性建立在离散对数问题的困难性之上，其原理此处亦不再赘述。

值得注意的是，业界尚未出现直接将全同态加密方案直接运用于智能合约加密的相关思路及具体实现。究其原因在于：行业对于智能合约的一个默认的基本要求是具备图灵完备性，尽管业界也承认无法提供无限存储能力供图灵完备的智能合约使用［13］。而图灵完备意味着，合约语言必须支持跳转。而跳转则意味着，合约语言必须能够对计算的中间结果进行判断或比较。换言之，同态加密方案要保证计算过程中的单调性，而这是不可能做到的，因为单调性是对破解非常有帮助的特性。

为了解决图灵完备特性对全同态加密方案的不切实际的要求，我们寄希望于通过将智能合约的执行过程分段，从而在不涉及比较和判断的地方使用全同态加密技术。

3 分段加密原理

为了对智能合约分段进行同态加密，我们首先要了解智能合约的编译和执行过程。从Ethereum引入智能合约开始，到Fabric中基于Golang语言编译器及docker模拟器的强大的智能合约［14］，智能合约的编写语言从定制走向通用，相应的模拟器也从定制走向通用，但智能合约的编译和执行过程一直都是相似的。如图2所示。

图2 智能合约的编译和执行过程

首先，智能合约的编写者需要使用图灵完备的高级语言编写合约/链码，然后使用相应的编译器将其编译为字节码，并存储于区块链中［15］。而智能合约调用者则需要提供相应的输入参数，将区块链上的智能合约运行于模拟器上，并将结果以交易的形式提交到区块链，供其他节点验证。验证节点同样是根据交易中提供的输入参数，将智能合约再次放到模拟器上运行，以验证交易结果的正确性［16］。

所以，我们可以将智能合约理解为一个程序的源代码，是用高级语言编写的，可读的文本。而当智能合约被提交到区块链上的时候，它首先需要被编译，形成类似汇编语言的指令序列，并被存储到区块链上。此时，该智能合约就类似于通用计算机上的“可执行程序”，可以被区块链网络中的其他节点调用，并且在调用的时候可以接受不同的输入参数，从而得到不尽相同的结果。也就是说，当某个节点调用智能合约时，就类似于一台个人电脑调用了网络上的一个程序来进行计算，并将计算结果存储到网络中。所不同的是，所有被存储到网络上的智能合约计算结果，都需要被网络上的其他节点进行验证。而验证的过程，就是各个节点利用该合约被调用时所传入的参数，在节点本地利用模拟器再次进行计算，来验证网络上的结果与自己本地是否一致。

这一过程中，最值得我们注意的是：可被调用的智能合约，是以一种可被模拟器执行的指令流的方式存储到区块链中的，这样才好被不同的节点反复执行并验证。而这个指令流中的指令，一定属于一个指令集，而且该指令集最好是图灵完备的［17］，才有可能被业界接受。

显然，我们需要一个相对精简的，图灵完备指令集。我们知道，如果巧妙地选取一条指令来构成一个指令集（One Instruction Set Computer，OISC）［18］，并给予它无限的资源，是可以构成一个图灵机的。这样的OISC的大致可以分为三类：位操纵机、传输触发架构（Transport Triggered Architecture）机器［19］和基于算数运算的图灵完备机器［20］。

最简单的图灵完备的单一指令集的思路是：“SBNZ abcd”指令，其中a、b、c、d都是地址指针。该指令的功能是：如果a中的内容与b中的内容不相等，则将b中的内容减去a中的内容，并将结果存储到c地址中，然后将控制转移到地址d；否则按顺序执行下一条指令。

显然，满足图灵完备的充要条件是：该指令集支持算数运算和“判断+跳转”。算数运算可以由加法和乘法指令组合完成，并且加法与乘法是可以被全同态加密方案支持的。“判断+跳转”的关键是判断，即判断两个数字的大小。如果全同态加密方案在对明文和密文运算的时候，可以保证单调性，就可以认为能够支持判断。例如：明文的x1小于x2，那么密文的x1也要小于密文的x2。但这对于同态加密技术来说不切实际。试想，如果我们现在得到了E（x）的值，想反求x的值，此时如果同态加密能够保证单调性的话，那么我们很容易找到x1，x2，使得E（x1）

所以，我们只有让同态加密绕过全部判断指令，这也正是本文所要着重说明的“分段加密”的原因。所谓分段，指的不是对指令流字节码分段，而是在该指令流字节码被虚拟机执行过程中的指令执行序列进行分段。指令流字节码是编译结果，而指令执行序列是运行时才能确定的序列。图3可以说明指令流字节码和指令执行序列之间的区别。

如图3所示，指令流字节码，类似于一个可执行程序；而指令执行序列，则类似于程序运行时，调度到CPU上运行的指令的顺序列表。一个智能合约，可以一一映射到一个指令流字节码，且后者一定要先被存储到区块链上，才能被调用。而智能合约的每次调用，都可以一一映射到一个指令执行序列。需要指出的是，节点在对智能合约调用进行验证的时候，其所对应的指令执行序列，必然与原调用者调用智能合约时所对应的指令执行序列完全一致。所以我们可以说，同一个智能合约，在输入参数相同的情况下，其执行过程中的指令执行序列也一定相同，所以合约执行结果也一定相同。

图3 指令流字节码与指令执行序列

显然，由于智能合约调用者掌握着输入参数的明文，其合约执行过程中也是进行明文计算，所以合约调用者可以在现有的虚拟机上运行现有的指令流字节码，而且可以在执行的过程中获得每次遇到判断指令时的判断结果。

而智能合约验证者由于只掌握了输入参数的密文，其合约执行过程中也只能进行密文计算，而同态加密是不能保证单调性的，所以合约执行者在现有虚拟机上运行现有指令流字节码的时候，势必会在判断指令上于明文运算存在一定概率的不一致，而这个概率可能会逼近0.5，即密文的大小关系是随机的，与明文大小关系无关。

既然我们现在缺少且仅缺少针对判断的同态加密方案，那么我们可以考虑通过图3中的判断结果序列来绕开判断指令的同态加密：这就是本文的核心思路：利用判断结果序列来辅助同态加密方案，构成针对图灵完备的智能合约的同态加密方案。

为了解决合约验证者在执行判断指令的时候存在不一致的问题，我们可以要求智能合约调用者在用明文参数执行完合约的同时，将这一过程中遇到的所有判断指令的结果（即一个Y/N序列，或二进制串）保存下来，并以判断序列的方式作为辅助参数，一并发布到区块链上。与此同时，智能合约验证者在得到输入参数密文，以及判断序列后，同样可以在虚拟机上再次执行该合约，并在遇到判断指令的时候，不对其进行判断，而是直接使用判断序列里的值，从而避开同态加密所不支持的判断。流程参考图4。

这一方案的实现，需要考虑智能合约的调用者和验证者在执行智能合约时所使用的不同的参数即不同的执行过程，即我们需要对模拟器进行一次升级，才能验证这一方案。

首先，智能合约调用者节点，在其本地使用明文参数执行智能合约时，模拟器需要知道这是明文参数，可以按照智能合约指令流字节码来执行，并且每次遇到判断指令的时候，记录下判断的结果（Y/N或1/0）。当该合约执行完成后，模拟器不仅需要记录下合约执行结果，同时还要将执行过程中所生成的判断结果序列保留下来，因为这将是其他节点对该次合约执行结果进行验证的必须的参数。

图4 分段加密的执行过程

在合约执行完毕后，支持同态加密的区块链节点需要对输入参数和执行结果进行同态加密，并且连同判断结果序列的明文，一并提交，存储到区块链上。

与此同时，其他节点需要对合约执行结果进行验证，而它们所得到的参数将是密文形式，以及一串明文的判断结果序列。此时，不仅需要模拟器进行密文计算，并且在遇到判断指令的时候，不去执行指令，而是顺序使用判断结果序列中的值。如此，模拟器的整个执行过程，等价于一连串的针对密文的算数运算。由于判断结果序列是唯一的，所以这个一连串的算数运算，每条指令都与明文计算时的算数运算指令保持一致，其结果作为密文计算的结果，应该与明文计算的结果加密后是一致的。

综上，我们需要对模拟器进行升级，使其既可以生成判断结果序列，也可以根据判断结果序列对智能合约进行密文计算。

4 分段加密实践

Ethereum是第一个承载智能合约的区块链，其模拟器（EVM）是最经典也最简单的能够运行智能合约的虚拟机。EVM是一个准图灵机，可以运行包含复杂的随机的算法的智能合约字节码，其运行原理入图5。

我们构造一个非常简单的智能合约，并通过如图6的合约编译界面来生成字节码，从而在EVM上运行该智能合约。

从图6中可以看到，简单的智能合约中所出现的判断语句“if（b==1）”，在编译结果中有“ISZERO”指令与之相对应，而这样的判断指令正是智能合约分段加密工作的研究对象。

图5 EVM结构

图6 Remix-Ethereum IDE

最终在EVM上执行的智能合约字节码，其执行逻辑便是将图6右侧的类汇编指令逐条地利用图5中的EVM的内存和堆栈来执行，并将结果写入图5中的状态数据库。

基于上述实验，我们可以更加明确以Ethereum智能合约为代表的区块链智能合约的执行原理和细节。而我们接下来的工作，则集中在针对模拟器的重构，使之能够分别以明文和密文的模式来运行智能合约，其部署原理及流程如图7所示。

图7 EVM的执行模式与验证模式

5 尚需解决的问题

5.1 算术运算的规模

智能合约所涉及到的算数运算通常具有一定的规模，例如Ethereum上标准发币合约会被官方编译器编译为约1500条类汇编指令。而目前不能确定同态加密方案对于复杂运算的支持程度，所以这方面需要进一步的调研和试验。

5.2 判断序列的真实性

由于判断序列是由合约调用者通过明文运算后给出的，所以存在该调用者恶意造假的可能性。因为参数明文是该调用者唯一持有的，所以其他节点无法再次参数明文来执行智能合约，也就无法直接验证该判断序列的正确性。

5.3 判断序列的隐私性

由于智能合约本身是公开的，而判断序列同样是公开的，所以不能排除有人可能会根据判断序列来反推出调用者明文参数的一些特征。不过判断序列所带有的隐私信息是非常有限的，并且可以在合约头部代码中加入一些干扰代码来增加这种“破译”难度。

6 结语

本文通过对智能合约执行过程的介绍、对全同态加密领域的调研以及对“图灵完备”指令集的分析，论证了难以寻找到适用于图灵完备的智能合约的全同态加密方案的原因，进而提出了利用判断结果序列的方法来讲智能合约简化为算数运算，从而使用全同态加密方案进行加密。接下来的验证工作，需要升级模拟器，为全同态加密在智能合约中的应用提供基础设施。