我将简单介绍我们最近发表在 IEEE S&P(Oakland) 2025 上的文章 Check-Before-you-Solve: Verifiable Time-lock Puzzles。

时间锁谜题（Time-Lock Puzzle, TLP）是一种密码学算法，允许生成者快速地生成一个谜题，同时强制解谜者必须经过  次无法并行的连续计算后才可解开谜题，其中  是由生成者设置的参数。通过估算每次计算所用的时间（比如，使用最快的 CPU 计算每个步骤的时间为 ），就可以通过这个算法来保证这个谜题最快在  时间以后才能被解开。

TLP 算法的核心特点是计算的不对称性：生成者生成谜题的计算开销非常小，而解谜者解开谜题的计算开销线性增长。这使得 TLP 成为保证延迟信息披露、安全数据锁定以及分布式系统共识的关键工具。然而，TLP 在生成者和求解者之间计算时间的不对称性是一把「双刃剑」。这种不对称性促成了许多有趣的应用，但另一方面，它也带来了一个直观的限制：求解谜题需要付出计算资源，但解谜者在完成计算之前无法验证谜题的有效性，除非谜题生成者是完全可信的。例如，在区块链环境中，一个恶意的谜题生成者可能会滥用这一点，让其他参与者「浪费」他们的计算资源：其他参与者原本希望能从解谜中获益，但最终却发现得到的是「无效」的结果，进而导致计算资源的严重浪费。

为解决这一问题，我们提出了可验证时间锁谜题（Verifiable Time-Lock Puzzle, VTLP），它在传统 TLP 的基础上增强了功能性以及安全性。VTLP 结合了零知识证明（包括 SNARK）技术，使得解谜者可以在解谜之前验证谜题的解是否满足某些预定义的数学关系（例如签名的有效性、哈希原像等）。

比如，TLP 可以用来解决区块链去中心化交易所 (Decentralized Exchange， DEX) 系统中的三明治攻击（Sandwich Attack）。在去中心化交易所中，用户的交易会先提交到一个公开的交易池（mempool），等待矿工或验证者打包。这些交易信息是透明的，包括交易金额、代币类型等。攻击者可以监控这些交易，利用信息优势发起套利操作：假设 Alice 想在去中心化交易所用 10 Bitcoin 买代币 TokenA，她的交易会被放到公开的交易池中；攻击者 Bob 在交易池中看到 Alice 的交易，并知道这笔交易会推高 TokenA 的价格，Bob 抢先用自己的资金买入 TokenA，利用 Alice 的交易推高代币价格，Alice 的交易按计划完成，但由于价格被抬高，她用 10 ETH 买到的 TokenA 比预期少。Bob 在 Alice 的交易完成后立刻卖出之前买入的 TokenA，以更高的价格获利。

结果就是 Bob 通过前后夹击套利获利，而 Alice 则因价格被操纵而损失。这就像是在证券交易市场上，有人在你买股票以前，插队买入，抬高价格并转手卖给你。

为了解决这个问题，用户可以在提交交易的时候可以先使用 TLP 来隐藏自己的交易，让自己的交易先被锁定交易顺序，等  时间以后才被解密并执行。但是仅仅使用传统的 TLP 又会带来新问题：如果用户在 TLP 中隐藏的交易并不合法，甚至不包括任何有效信息，那么 TLP 只会大量的浪费矿工或验证者的计算资源，反而带来更多的资源浪费。

相反，VTLP 可以完美解决这个问题！在这一场景中，用户可以证明 VTLP 隐藏了一个有效的区块链交易签名，其中交易发送方是某个该节点，并且通过验证 Merkle path 来确定该节点有足够的余额来完成交易。这直接实现了无需依赖可信第三方或智能合约的延迟交易，既能解决三明治攻击，又不会带来潜在的无效 TLP。

接下来，本文将从技术角度简单探讨时间锁谜题的数学构造、它的可验证性，以及如何通过 SNARK 和密码学工具实现其安全性和高效性。

时间锁谜题的数学基础

经典的时间锁谜题由 Rivest， Shamir 以及 Wagner 在 1996 年提出，通常基于重复平方计算（Repeated Squaring）。下面我们介绍众多形式中的一种。

• 谜题生成者随机选择两个大素数   和 ，计算 。
• 公钥为 ，私钥为 ，其中  为欧拉函数，根据欧拉定理， 可以用于快速计算谜题。

• 输入：
• 想要隐藏的解 ;
• 在  范围中的均匀随机数 ;
• 难度系数 。
• 输出：
• 计算 
• 公开谜题 。

• 输入：
• 谜题  以及难度系数 。
• 解谜步骤：
• 通过重复平方计算 。
• 计算 。

这种设计依赖于两个核心难题：

• RSA 难题：在不知道  和  的情况下，无法高效计算  的欧拉函数 ； 生成者利用  快速计算 ，而求解者只能通过逐步幂运算完成，无法跳过或加速。
• 顺序计算不可并行性：重复平方计算必须逐步进行，每一步依赖于前一步的结果，无法通过多线程或分布式计算加速。

可验证时间锁谜题（VTLP）

在原有的 TLP 基础上，我们的定义了 VTLP 具有额外的可验证性：在求解谜题以前，求解者可以验证一个简短的证明来验证谜题  中所隐藏的谜题  符合某个 NP 关系。熟悉零知识证明的读者可能立刻想到，我们可以用 SNARK 来构造一个电路，来验证一个 TLP 是针对解  「正确」生成的，并且进而用 SNARK 来证明解  符合某个 NP 关系， 比如  是个有效签名。

然而这种方法在实践中有很严重的限制：绝大多数 SNARK 电路的原始域都在 256 bits 左右，而 RSA 的域一般在 2048 bits 左右，把 RSA 计算编码进 SNARK 电路会带来巨大的计算负担！根据 xjSNARK 的编码方法（目前将大数计算编码进 SNARK 的最优算法），在 SNARK 里验证一次 2048-bit 的模乘法需要 18,000 constrains，直接在电路里验证  大概需要 72,000,000 constrains！这对于绝大多数应用场景都是一个无法接受的计算开销。

为了解决这个问题，我们提出了一种针对 SNARK 大数计算的卸载（offloading）技术：这种技术允许 SNARK 证明者将部分复杂计算从 SNARK 电路中转移到电路外部并单独对其进行证明。经过理论以及实际的 Benchmark，我们的卸载算法可以把验证 TLP 的电路缩小 140 倍左右！

我们的 SNARK 卸载技术有以下两个技术基础：

1. 基于隐藏阶群的 Sigma protocol
2. 基于隐藏阶群的 SNARK Offload protocol

其中 SNARK Offload protocol 的核心在于把 SNARK 中的计算卸载到高效的 Sigma protocol 上，避免在 SNARK 电路中检查 RSA 相关的运算。

由于这两部分都高度依赖于隐藏阶群（Hidden Order Group），我们先对其进行简单的介绍。隐藏阶群是一种特殊的数学群结构，它的阶（order）对外界是隐藏的。因为阶是隐藏的，使得这个群具有很多特殊性质，其中一个核心特性是：它可以用一个有限大小的群表示几乎无限多的状态。基于 RSA 的 Hidden Order Group 是构造这种群的最常见方法。为了生成隐藏阶群，我们需要一个可信初始化（trusted setup）：一个可信的第三方随机选择两个大的安全素数（safe prime）  和 ，计算 ，公开  然后删除关于  和  的信息。在初始化结束以后，整数模  乘法群  就变成了一个隐藏阶群：群的阶  已经被遗忘，而通过  无法在多项式时间内计算出  和 （基于 RSA Assumption）。 有多个子群，我们使用二次剩余群（）作为我们的隐藏阶群，因为它在效率和安全性之间实现了良好的平衡。均匀随机选取 ，计算 ，则 。为了区分隐藏阶群与后面用到的 RSA 群，我们把通过  生成的隐藏阶群表示为 。

基于隐藏阶群，我们首先扩展了以下协议：  到一般情况。 协议是由 Boneh，Bünz，Fisch 三位学者在 2018 年提出的一种高效协议，其中  是基于隐藏阶群的承诺， 是群的生成元， 是所承诺的整数并且是协议的见证（witness），协议证明的是针对任意质数 ，，其中  是一个公开值。我们把该协议扩展到任意模数并提供了零知识（zero-knowledge）版本：，即证明给定某个整数 ，，其中  是一个公开值。

然后，我们构造了以下协议以及其零知识版本：，其中  是基于隐藏阶群的承诺， 是群的生成元， 是  所承诺的整数并且是协议的见证，协议证明的是给定某个整数 ， 承诺了 。换句话说， 所承诺整数是  所承诺整数的  次幂。值得注意的是，这里的幂运算是双重幂运算，直接计算  得到的是 ，而不是 。

最后，通过组合使用以上两个协议，我们构造出了以下双重模幂运算协议：，即对于一个承诺在  中的整数 ，对于给定整数 ，协议可以证明 。协议的证明大小为固定大小并且能够实现零知识的特性。

OffloadExp 协议解析

如果我们想在 SNAKR 中验证 TLP 的正确生成，核心在于我们如何在 SNARK 中高效证明如下关系：

其中  均为 2048 位大整数。这里的  表示的是 TLP 所使用的公钥，而不是隐藏阶群的模。

核心思想如下：

1. 使用隐藏阶群元素  以及任意向量承诺（Vector Commitment）分别承诺一组整数，在看到两个承诺以后，验证者可以生成一个随机质数挑战 （为了获得 128 比特安全  需要有 128 比特），如果这两组整数的乘积模  的结果相同，则这两组数极大概率相同（with overwholming prbability）。一个反例是，假如证明者承诺了两个不同的整数，那么这两个整数模  的结果相同的概率在  左右，即概率约为 。
2. 隐藏阶群元素  承诺一组整数的形式就是承诺这组整数的乘积，通过我们的  协议以及  协议可以直接对这个乘积进行高效的运算！
3. 大部分基于向量承诺的 SNARK 都支持高效的 Commit-and-prove SNARK（比如 Groth16, Bulletproof 等），即在生成证明之前，可以先将部分见证通过向量承诺进行承诺。进而结合上面描述的方法，使用向量承诺来承诺 SNARK 见证中的大数数组，并证明隐藏阶群元素  也承诺了相同的数组，就可以把 SNARK 中不好计算的大数乘法「卸载」到隐藏阶群中！
4. 根据模运算的分配律，计算 。因此，在 SNARK 里计算一组数的乘积模上  可以转化为计算每个数分别模 ，然后累计他们的余数。这样，就可以在 SNARK 电路以内高效的计算一组向量乘积模  的结果。

换句话说，我们可以将原问题（如证明 ）转化为隐藏阶群中的指数关系证明：SNARK 电路内部只验证简单的小域模运算（模 ）；SNARK 外部使用隐藏阶群的高效证明来验证大整数模  的关系。

根据以上观察以及模幂运算的结构，从 SNARK 电路卸载  运算的具体步骤如下：

步骤 1：预处理与指数分解

我们首先将幂指数  二进制分解：，其中 。

记 ，则原式可表示为：

步骤 2：隐藏阶群的承诺

使用隐藏阶群元素 ，承诺上述结果的整数值（未取模 (N)）：

令隐藏阶群承诺为：

根据上面的描述，我们为了证明  和 SNARK 承诺了相同的数组，需要分别使用隐藏阶群和向量承诺分别承诺。我们可以进一步观察到  的值取决于 ，而  是公开的固定结果，所以我们只需要使用 Commit-and-prove SNARK 来获得  的承诺，就会唯一对应  的结果。然后计算  所承诺的整数模随机质数  的结果，我们表示为 。

步骤 3：模素数一致性验证（SNARK 内部）

SNARK 电路输入： 和 witness ，并计算：

SNARK 电路内部只需验证原始小域的模运算：

• 验证  是否等于 。

通过这一步，我们在 SNARK 电路中减少了大整数模运算的复杂性，而在下一步中，我们将利用隐藏阶群的高效性，在电路外部完成相关验证。

步骤 4：大整数模 (N) 关系证明（SNARK 外部）

在 SNARK 外部，使用 PoKEModN 协议高效证明隐藏阶群元素  中承诺的整数  满足：。

步骤 5：组合两部分证明

最终，整个 OffloadExp 协议的证明为：

• SNARK 证明 ：证明步骤 3 中模素数一致性关系。在 SNARK 电路中，只需要检查  个原始域的模乘法即可。
• PoKEModN 证明 ：证明步骤 4 中模  关系。 若两部分证明均通过，则可确认：

OffloadExp 协议效率优势

通过上述卸载协议，OffloadExp 协议显著降低了 SNARK 电路规模：

通过这样的卸载技术，证明者的计算开销、内存占用、证明时间都得到了极大改善。

进一步扩展

我们在原文中进一步讨论了如何让上述协议实现 zero-knowledge，以及如何讨论了我们的协议是如何抵抗恶意的证明者的（即使 RSA key 是恶意生成的，我们的协议依旧有效）。我们还进一步的通过  协议来替代 SNARK，证明一个 VTLP 的原象是一个有效的 RSA signature/VRF。除此以外，根据以上思路，我们还设计了另一个 SNARK 卸载协议，可以高效的在 SNARK 电路中验证 RSA signature：验证单个 RSA 签名的消耗只需要 800 constraints 左右（其中 350constraints 用于检查 MiMC Hash），批处理同一个公钥的 RSA 签名，验证 1000 个签名， SNARK Prover 只需要 3.8 秒左右！更多证明 / 协议 / 实验细节请参考我们的在线版本^[1]

特别感谢 Sui Academic Research Award 对本研究的支持！

* 作者&联系方式：辛佳骏（https://jiajunxin.github.io/）