Gate Ventures研究院:FHE,披上哈利波特的隐身衣


什么是 FHE

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

FHE 流程,图源:Data Privacy Made Easy

FHE(Fully homomorphic encryption)是一项先进的加密技术,可以支持在加密的数据上进行直接计算。这意味着可以在保护隐私的同时对数据进行处理。FHE 有多个可落地的场景,特别是在隐私保护下的数据处理与分析,如金融、医疗健康、云计算、机器学习、投票系统、物联网、区块链隐私保护等领域。但是商业化仍然需要一定的时间,主要问题在于其算法带来的计算与内存开销极为庞大,可拓展性较差。接下来我们将简要 walk through 整个算法基本原理以及着重讲述该密码学算法面临的问题。

基本原理

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

同态加密图示

首先,我们要实现加密的数据进行计算然后还能得到相同的结果,我们可视化如上图所示。这是我们的基本目标。在密码学中,通常使用多项式,来隐藏原文的信息,因为多项式能够转换为线性代数的问题,也可以转换为向量的计算问题,这便于为向量进行高度优化的现代计算机进行运算(如并行计算),例如, 3 x 2 + 2 x + 1 可以表示为向量 [ 1, 2, 3 ]。

假设,我们要加密 2 ,在一个简化的 HE 系统中,我们可能会:

  • 选择一个密钥多项式,比如 s(x) = 3 x 2 + 2 x + 1 

  • 生成一个随机多项式,比如 a(x) = 2 x 2 + 5 x + 3 

  • 生成一个小的“错误”多项式,比如 e(x) = -1 x + 2 

  • 加密 2 -> c(x) = 2 + a(x)*s(x) + e(x)

我们讲一下为什么需要这样做,我们现在假设拿到了密文 c(x),如果想要得到明文 m,则公式为 c(x) – e(x) – a(x)*s(x) = 2 ,这里我们随机多项式假设 a(x)是公开的,那么只要保证我们的密钥 s(x)是保密的即可,我们如果知道了 s(x),再加上 c(x)作为一个很小的误差,那么理论上可以忽略,就能得到明文 m。

这里有第一个问题,多项式那么多,如何选择多项式呢?多项式的度多大比较好呢?实际上多项式的度是由实现 HE 的算法决定的。通常是 2 的幂次,如 1024 / 2048 等。多项式的系数由一个有限域 q 中随机选择,如 mod 10000 ,则在 0-9999 中随机选择,系数随机选择有很多算法遵循,如均匀分布、离散高斯分布等等。不同的方案也有不同的系数选择要求,通常是为了满足该方案下的快速求解原则。

第二个问题,噪声是什么?噪声是用来迷惑攻击者的,因为假设我们的所有数字都是采用 s(x),并且随机多项式处于一个有域中,那么就存在一定的规律,只要输入足够多次的明文 m,根据输出的 c(x),就能判断这两个 s(x)与 c(x)的信息。如果引入了噪声 e(x),就能保证无法通过简单的重复列举获得 s(x)与 c(x),因为这有一个完全随机的小误差存在。这个参数也被称为噪声预算(Noise Budget)。假设 q = 2 ^ 32 ,初始噪声可能在 2 ^ 3 左右。经过一些操作后,噪声可能增长到 2 ^ 20 。此时仍有足够空间进行解密,因为 2 ^ 20 << 2 ^ 32 。

我们获得了多项式以后,我们现在要把 c(x) * d(x)操作转化为“电路”,这个在 ZKP 中也经常出现,主要是因为电路这个抽象概念提供了一个通用的计算模型表示任何计算,并且电路模型允许精确跟踪和管理每个操作引入的噪声,也方便后续引入到专业硬件中如 ASIC、FPGA 进行加速计算,如 SIMD 模型。任何复杂的操作都可以映射成简单的模块化的电路元素,如加法和乘法。

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

算术电路表示

加法和乘法就能够表达减法以及除法,因此就能够表达任意计算。多项式的系数用二进制表示,称为电路的输入。每个电路的节点代表了执行一次加法或者乘法。每个(*)代表乘法门,每个(+)代表加法门。这个就是算法电路。

这里就引申出一个问题,我们为了语义信息上不泄漏,因此引入了 e(x),这被称为噪声。我们的计算中,加法会让两个 e(x)多项式变成,同度的多项式。在乘法中,两个噪声多项式相乘,会让 e(x)的度以及文本大小指数级增加,如果噪声过大,就会导致结果计算的过程中,噪声无法忽略,进而导致原文 m 无法恢复。这是一个限制 HE 算法表达任意计算的主要原因,因为噪声会指数级增长,导致很快就达到了不可用的阈值。在电路中,这个被称为电路的深度,乘法运算的次数也就是电路的深度数值。

同态加密 HE 的基本原理如上图所示,为了解决制约着同态加密的噪声问题,因此提出了多项解决方案:

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

这里面 LHE 是一个很适合的一个算法,因为在这个算法下,只要深度确定了就能在深度内执行任意函数,但是 PHE 以及 SHE 无法实现图灵完备。因此在这个基础上,密码学家进行研究,提出了三个技术来构建 FHE 全同态加密,期望实现在无限深度执行任意函数的愿景。

  • Key switching(密钥切换):我们在乘法后,密文的大小会指数级增长,这会让后续的操作内存和计算资源提出极大的要求,因此在每次乘法后实施 Key switching 就能压缩密文,但是会引入一点噪声。

  • Modulus Switching(模数切换):无论是乘法还是 key switching 都会让噪声指数级增加,模数 q 是我们前面讲过的 Mod 10000 ,只能在[ 0, 9999 ]里面取参数,q 越大则噪声经过多次计算后最后噪声仍然在 q 内,则可以解密。因此在多次操作后,为了避免噪声指数级增大超过阈值,那么就需要使用 Modulus Switching,来减小噪声预算,这样就可以压低噪声。我们这里就可以得到一个基本的原理,如果我们的计算很复杂,电路深度很大,那么就需要更大的模数 q 噪声预算来容纳多次指数级增长后的可用性。

  • Bootstrap:但是想要实现无限深度的计算,Modulus 只能限制噪声的增长,但是每次切换都会让 q 范围变小,我们知道一旦减小,意味着计算的复杂度就需要降低。Bootstrap 是一项刷新技术,就是将噪声重置到原始水平,而不是减小噪声,bootstrap 不需要减小模数,因此可以维持系统的计算能力。但是其弊端就是需要消耗大量的算力资源。

总的来说,针对有限步骤下的计算,使用 Modulus Switching 能够降低噪声,但是同时也会降低模数,也就是噪声预算,导致压缩计算能力。因此这仅仅针对有限步骤下的计算。对于 Bootstrap 能够实现噪声重置,因此在基于 LHE 算法之上,能够实现真正意义上的 FHE,也就是任意函数的无限计算,而这也是 FHE 的 Fully 的含义。

但是缺点也很明显就是需要消耗大量的算力资源,因此一般情况下,这两种降噪技术会结合使用,Modulus switching 用于日常的噪声管理,延迟需要 bootstrap 的时间。当 modulus switching 无法进一步有效控制噪声时,才使用计算成本更高的 bootstrap。

目前 FHE 的方案有以下具体的实现,都使用的 Bootstrap 核心技术:

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

这里也就引出了我们一直未谈及的电路类型,在上面我们介绍的主要是算术电路。但是还有另外一个电路类型——布尔电路。算术电路是 1+ 1 这种比较抽象的,节点也是加法或者除法,而布尔电路所有的数字转化为 01 进制,所有的节点是 bool 运算,包括 NOT、OR、AND 运算,类似于我们的计算机的电路实现。而算术电路更是一个抽象上的电路。

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

因此,我们可以非常粗略的将布尔运算视为没有那么数据密集的灵活的处理,而算术运算是针对数据密集型应用的方案。

FHE 面临的问题

由于我们的计算需要加密然后转换为“电路”,并且由于单纯的计算仅仅计算 2+ 4 ,但是在加密后,引入了大量的密码学间接的计算过程,以及一些前沿技术如 Bootstrap 来解决噪声问题,进而导致了其计算开销是普通计算的 N 个数量级。

我们以一个现实世界的列子来让读者感受这些额外的密码学过程对计算资源的开销。假设普通计算在一个 3 GHz 的处理器上需要 200 个时钟周期,那么一次普通的 AES-128 解密大约需要 67 纳秒( 200/3 GHz)。FHE 版本需要 35 秒,是普通版本的大约 522, 388, 060 倍( 35/67 e-9)。也就是,使用相同的计算资源,同一个普通算法和 FHE 计算下的算法,其对计算资源的要求大概是 5 亿倍。

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

DARPA dprive 计划,图源:

美国的 DARPA 为了数据安全,因此在 2021 年专门构建了一个 Dprive 计划,邀请了多个研究团队包括微软、Intel 等,他们的目标是创建一个 FHE 加速器以及配套的软件堆栈,使 FHE 计算速度更符合未加密数据的类似操作,实现 FHE 计算速度大约为普通计算的 1/10 的目标。DARPA 项目经理 Tom Rondeau 指出:“估计,在 FHE 世界中,我们的计算速度比在纯文本世界中慢大约一百万倍。

而 Dprive 主要从以下几个方面着手:

  • 增大处理器字长:现代计算机系统使用 64 位的字长,也就是一个数字最多 64 位,但是实际上 q 往往 1024 位,如果想要实现就要拆分我们的 q,这样会对内存资源和速度有损耗。因此为了实现更大的 q,需要构建一个 1024 位或者更大字长的处理器。有限域 q 非常重要,就像我们前面提到的,越大,那么可计算的步骤就越多,对于 bootstrap 的操作就可以尽可能的往后推迟,这样整体的计算资源消耗就会减小。q 在 FHE 中扮演着核心角色,它影响了方案的几乎所有方面,包括安全性、性能、能够进行的计算量以及所需的内存资源。

  • 构建一个 ASIC 处理器:我们前面讲到过由于便于并行化以及其它原因,我们构建了多项式,通过多项式构建了电路,这个和 ZK 是相似的。目前的 CPU、GPU 不具备这个能力(算力资源以及内存资源)来运行电路,需要构建专门的 ASIC 处理器来允许 FHE 算法。

  • 构建并行化架构 MIMD,与 SIMD 并行架构不同,SIMD 只能在多个数据上执行单一指令,也就是数据的拆分与并行处理,但是 MIMD 可以拆分数据使用不同的指令进行计算。SIMD 主要用于数据并行,这也是大多数区块链项目对交易并行处理的主要架构。而 MIMD 能够处理各种类型的并行任务。MIMD 在技术上更复杂,需要着重处理同步与通信问题。

距离 DARPA 的 DEPRIVE 计划仅仅剩下一个月的时间就到期了,原本计划 Dprvie 是从 2021 年开始, 2024 年 9 月份三个阶段的计划结束,但是似乎其进展缓慢,目前仍然未达到预期的相比于普通计算 1/10 效率的目标。

虽然攻破 FHE 技术进展缓慢,类似于 ZK 技术一样,面临这硬件落地是技术落地的前提这一严峻问题。但是,我们仍然认为从长期来看,FHE 技术仍然有其独特的意义,特别是我们第一部分罗列的保护部分安全数据的隐私上。对于 DARPA 国防部来说,其掌握了大量的敏感数据,如果想要将 AI 泛型能力释放到军事上,就需要以数据安全的形式训练 AI。不仅如此,对于医疗、金融等关键敏感数据也同样适用,实际上 FHE 并不适用于所有的普通计算,更加面向于敏感数据下的计算需求,这种安全性对于后量子时代尤为重要。

对于这种前沿技术,必须要考虑投资周期与商业化落地的时间差。因此,我们需要非常谨慎的看待 FHE 的落地时间。

区块链的结合

在区块链中,FHE 也主要用于保护数据的私密性,应用领域包括链上隐私、AI 训练数据的隐私、链上投票隐私、链上隐私交易审查等方向。其中 FHE 也被称作链上 MEV 方案的潜在解决方向之一。根据我们的 MEV 的文章所述,当前的许多 MEV 方案仅仅是重新构建 MEV 架构的方式,并不是解决的方式,实际上三明治攻击带来的 UX 问题仍然没有解决。我们一开始想到的方案也是,直接对交易加密,同时保持状态的公开。

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

MEV PBS 流程

但是也有一个问题就是如果我们对交易进行完全的加密,就会让 MEV bots 带来的正外部性也同时消失,验证者 Builder 需要运行在虚拟机的基础上进行 FHE,验证者也需要验证交易以确定最后的状态正确性,那么就会显著提高运行节点的要求,让整个网络的吞吐量放慢百万倍。

主要项目

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

FHE Landscape

FHE 是一项较新的技术,目前大部分的项目使用的 FHE 技术都来自于 Zama 构建的,如 Fhenix、Privasea、Inco Network、Mind Network。Zama 的 FHE 工程实现能力获得了这些项目的认可。以上几个项目大部分都基于 Zama 提供的库进行构建,主要区别在于商业模式。Fhenix 希望构建一个隐私优先的 Optimism Layer 2 ,Privasea 希望运用 FHE 的能力来进行 LLM 的数据运算,但是这是一项非常重数据的操作,对 FHE 的技术与硬件要求都特别高,然后 Zama 基于的 TFHE 可能不是最优的选择。Inco Network 与 Fhenix 都使用 fhEVM,但是一个是构建 Layer 1 一个是 Layer 2 。Arcium 是构建了多种密码学技术的融合,包括了 FHE、MPC 和 ZK。Mind Network 的商业模式比较另辟蹊径,选择了 Restaking 赛道,通过提供流动安全性和基于 FHE 的子网架构来解决共识层的经济安全与投票信任的问题。

Zama

Zama 是基于 TFHE 的方案,其特点是使用了 Bootstrap 技术,其着重于处理布尔运算和低字长的整数运算,虽然在我们实现了 FHE 的方案中是一个较快的技术实现,但是其相比与普通计算仍然有非常大的差距,其次也无法去实现任意计算,在面对数据密集型的任务时,这些运算会导致电路的深度过大而无法处理。其不是数据密集型的方案,其只适用于某些关键步骤的加密处理。

TFHE 目前已经有了现成的实现代码,Zama 的主要工作是使用 Rust 语言重写了 TFHE,也就是其 rs-TFHE crates。同时为了降低用户使用 Rust 的门槛,其也构建了一个转编译的工具 Concrate,能够把 Python 转化为 rs-TFHE 等效的。使用这个工具,就能把基于的 Python 的大模型语言转译到基于 TFHE-rs 的 rust 语言。这样就能运行基于同态加密的大模型,但是这时数据密集型的任务,其实并不适合 TFHE 的场景。Zama 的产品 fhEVM 是一种使用完全同态加密(FHE)在 EVM 上实现机密智能合约的技术,能够支持基于 Solidity 语言编译端到端加密的智能合约。

总的来说,Zama 作为一个 To B 的产品,其构建了较为完善的基于 TFHE 的区块链+AI 开发堆栈。能够帮助web3的项目简单的构建 FHE 的基础设施和应用。

Octra

Octra 比较特殊的一点是,使用了另辟蹊径的技术来实现 FHE。其使用了一个称为 hypergraphs 的技术来实现 bootstrap。也是基于布尔电路,但是 Octra 认为基于 hypergraphs 的技术,能实现更高效的 FHE。这个是 Octra 实现 FHE 的原创技术,团队具备非常强的工程、密码学能力。

Octra 构建了新的智能合约语言,其使用 OCaml、AST、ReasonML(一种专门用于与 Octra 区块链网络交互的智能合约和应用程序的语言)等代码库和 C++ 进行开发。其构建的 Hyperghraph FHE 库,能够与任何项目兼容。

其架构也是类似于 Mind Network、Bittensor、Allora 等项目,其构建了一个主网,然后其它项目成为 subnets,构建了一个相互隔离的运行环境。同时,与这些项目类似,都构建了更适合架构本身的新兴共识协议,Octra 构建了一个基于机器学习的共识协议 ML-consensus,其本质是基于 DAG(有向无环图)的。

该共识的技术原理目前还未披露,但是我们可以大致的推测。大概就是交易被提交到网络中,然后使用 SVM(支持向量机)算法来决定最佳的处理节点,主要是通过目前各个节点的网络负载情况选择。系统会基于历史数据(ML 算法学习)来判断最好的父节点共识达成的路径。只要满足 1/2 的节点就可以达成该不断增长的数据库的共识。

期待

Gate Ventures研究院:FHE,披上哈利波特的隐身衣

前沿密码学技术发展现状,图源:

FHE 技术是一种面向于未来的技术,其发展现状仍然不及 ZK 技术,缺乏资本的投入,因为隐私保护带来的低效率以及高成本对大部分商业机构来来说都动力不足。ZK 技术的发展因为 Crypto VC 的投入变得更加快速。FHE 仍然处于非常早期,即使是现在,市面上的项目仍然较少,因为其成本高昂、工程难度高、商业化落地前景仍然不明朗的等原因导致。2021 年 DAPRA 联合多家公司如 Intel、Microsoft 等开启了长达 42 个月的 FHE 攻克计划,虽然取得一定进展,但是距离实现的性能目标仍然较远。随着 Crypto VC 对该方向的注意力到来,会有更多的资金涌入这个行业,预计业内会有更多的 FHE 项目出现,也会有更多类似 Zama、Octra 等具备很强工程与研究能力的团队站在舞台中央,FHE 技术对于区块链的商业化和发展现状的结合仍然值得探索,目前应用较好的就是验证节点投票的匿名化,但是应用范围仍然狭小。

与 ZK 一样,FHE 芯片的落地是 FHE 商业化落地前提条件之一,目前有多个厂商如 Intel、Chain Reaction、Optalysys 等在探索这一方面。即使 FHE 面临许多的技术阻力,但是伴随着 FHE 芯片的落地 ,全同态加密作为一项极具前景和确切需求的技术,其对于如国防、金融、医疗等行业会带来深刻的变革,释放这些隐私数据与未来量子算法等技术结合的潜力,也会迎来其爆发时刻。

我们愿意探索这一早期的前沿技术,如果你正在构建真正得以商业化落地的 FHE 产品,或者有更具前沿眼光的技术创新,欢迎与我们接触!

ayu

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注