最近工作上事情比较少，摸鱼的时候看了很多有意思的东西，找 VDF 相关资料的时候讲到一个问题：如何设计一个只能在指定的时间 $$ T $$ 后才能解出来的 puzzle 我先想了一下但是没想明白，怎么把时间这种抽象的概念在一个 puzzle 里面给量化出来。🤔

然后就翻到了这篇引用的论文 Time-lock puzzles and timed-release Crypto

看了文章才发现实际上这个问题可以等效于：设计一个算法，只有在经过 $$ P $$ 次计算后才能够得到正确的结果，且这个算法的计算过程不能被并行计算加速。这样只能使用一台机器解密，假设其每秒最高算力为 $$ S $$ 则一定要经过 $$ T = P / S $$ 秒后才能解出正确的结果，达到了 time-lock 的目的。

文章里介绍了两种 time-lock puzzle 的实现方式。

第一种 time-lock puzzle 设计

假设 Alice 有一个信息 $$ M $$ 要传递给 Bob 但是需要加密(锁定) $$ T $$ 秒钟的时间。(这里有一个前提是 Alice 需要事先知道 Bob 的算力情况)

加密

第一步，随机选择两个大质数 $$ p $$ 和 $$ q $$ 将他们相乘得到 $$ n = pq $$ 同时计算 $$ \phi(n) = (p-1)(q-1) $$

第二步，计算 $$ t = T*S $$ 其中 $$ S $$ 是 Bob 单机每秒能够进行的对 $$ n $$ 平方取模的次数(也就是所谓算力)

第三步，随机生成一个足够安全的，用于加密的密钥 $$ K $$ 和一个加密算法比如 RC5

第四步，使用密钥和加密算法加原始信息得到 $$ C_m = RC5(K, M) $$

第五步，选择一个随机数 $$ a\ (1 < a < n) $$ 然后加密 $$ K $$ 得到 $$ C_k = a^{2^{t}}\ (mod\ n) $$

这一步可以通过以下步骤进行加速：首先计算 $$ e = 2^{t}\ (mod\ \phi(n) ) $$ 然后计算 $$ b = a^{e}\ (mod\ n) $$

最后 Alice 将 $$ (n, a, t, C_k, C_m) $$ 公布给 Bob

解密

对于 Bob 来说获取 $$ M $$ 需要用密钥 $$ K $$ 解密 $$ C_m $$ 但是加密时已经保证 $$ K $$ 本身是足够安全的 Bob 只能通过 $$ C_k $$ 计算得到 $$ K = C_k - a^{2^{t}}\ (mod\ n) $$

这里只剩下 $$ t $$ 一个未知数，对于 Bob 来说除了暴力遍历所有 $$ t $$ 没有其他更好的办法 。

这样则需要经过 $$ a^{2}, a^{4}, a^{8},a^{16},...a^{x} (t = 1,2,3,...)$$ 这样一个序列的计算，可以观察到在这个序列里，每一项的计算都依赖前一项的计算结果 $$ a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ... $$ 即无法提前计算后面的值，也不能并行加速计算。只能通过 $$ t $$ 次计算得到结果，而根据之前设定的 $$ t = T*S $$ 所需要计算的时间就是 $$ T = t/S $$ 也即达了 Alice 将消息锁定 $$ T $$ 时间的目的。

（至于 Bob 如何判断自己找到了正确的 $$ K $$ 就不属于这个算法里面的问题了。一种方式是加密者可以给出 $$ sha256(K) $$ 让 Bob 自己校验。）

第二种 time-lock puzzle 设计

第二部分没仔细看，直接在 Claude2 上面上传论文让后让 AI 帮忙总结的(没有 GPT-4 可以用的情况下非常推荐用 Claude2)

ME: 介绍下第二种方法如何实现

文章提出的第二种使用受信任代理的方法大致如下:

1. 设置多个受信任的代理,每个代理定期公布一个密钥。
2. 用户将消息用一个随机密钥加密,得到密文。
3. 用户将该随机密钥通过密钥分享方案分成多个份,分别给不同的代理。
4. 每个代理使用在未来时间t公布的密钥,加密自己持有的那一份子密钥。
5. 在时间t,足够多的代理公布了他们在t时刻的密钥。
6. 用户可以用这些密钥解密出子密钥份,然后重构出原始的随机密钥。
7. 最后用这个随机密钥解密出原始消息。

这种方法的安全性依赖于受信任代理不提前泄露未来的密钥。同时设置多个代理,可以通过密钥分享和阈值检验来实现一定的容错性。即使个别代理被攻破或失效,只要有足够的代理仍正常工作,信息仍能在预定时间解密出来。