一种基于argon2id算法与shamir算法的内存PoW（工作量证明）解密游戏

前言

其实一个月前就设计了这个游戏，今天正式整理发布。

算法采用

通过利用argon2id算法的内存硬度来对抗GPU运算，实现基于内存的PoW，拉低硬件差距。

通过利用shamir算法门限方案，增加游戏乐趣。

游戏整体流程图

flowchart TD
    Enumerate(Enumerate Nonce) --> |枚举 Nonce| Target[Target Nonce]
    M[Memory Cost] --> Parameters[Parameters]
    T[Time Cost] --> Parameters[Parameters]
    Parallelism[Parallelism] -->  Parameters[Parameters]
    Length[Output Length] --> Parameters[Parameters]
    Salt[Salt] --> Parameters[Parameters]
    Parameters[Parameters] --> |参与计算| Argon2id[Argon2id PoW]
    Target[Target Nonce] --> |参与计算| Argon2id[Argon2id PoW]
    Argon2id[Argon2id PoW] --> |派生内容| Secret[Secret]
    Secret[Secret] --> |转换| AES1Key[AES Key]
    AES1Key[AES Key] --> |参与计算| AES1[AES Algorithm]
    EncryptedShamirContent[Encrypted Shamir Key] --> |参与计算| AES1[AES Algorithm]
    AES1[AES Algorithm] --> |解密内容| TagShamirKey[Tag + Shamir Key] 
    TagShamirKey[Tag + Shamir Key] --> |匹配 Tag| CorrectTag{Correct Tag}
    CorrectTag{Correct Tag} --> |No| Enumerate(Enumerate Nonce)
    CorrectTag{Correct Tag} --> |Yes| ShamirKey[Shamir Key]
    ShamirKey[Shamir Key 1] --> |参与计算| Shamir[Shamir Algorithm]
    ShamirKey2[Shamir Key 2] --> |参与计算| Shamir[Shamir Algorithm]
    ShamirKey3[Shamir Key 3] --> |参与计算| Shamir[Shamir Algorithm]
    MoreShamirKey[...] --> |参与计算| Shamir[Shamir Algorithm]
    Shamir[Shamir Algorithm] --> |合成 AES Master Key| MasterAESKey[AES Master Key]
    MasterAESKey[Master AES Key] --> |参与计算| AES2[AES Algorithm]
    EncryptedContent[Encrypted Content] --> |参与计算| AES2[AES Algorithm]
    AES2[AES Algorithm] --> |得到解密密文| DecryptedContent(Decrypted Content)

玩法讲解

公开参数

首先，出题者会给出本次游戏难度（Argon2id算法）参数：

Memory Cost(m) - 内存开销：指定算法在计算过程中需要使用的内存总量
Time Cost / Iterations (t) - 时间开销 / 迭代次数：指定算法的执行轮数。
Parallelism / Lanes (p) - 并发度 / 线程数：指定计算时可以同时使用的独立计算通道（lanes）或线程数量。
Salt (S) - 盐值：随机数据。
Output Length / Hash Length (l) - 输出长度：最终哈希结果的字节长度，一般为32用于匹配AES256密钥长度

下方为可选的公开数据：

Range - Nonce范围：Nonce的范围，可用于降低游戏难度。

然后，出题者会公开本次游戏奖池数与最少碎片数（Shamir算法）：

Total shares(n) - 总份额数 / 碎片总数：指定总奖池数量。
Threshold(k) - 阈值 / 门限值：拼凑出最终Key所需的最少碎片数。

公开密文

接着，出题者会公开本次游戏所有的被加密的密文以及标识：

所有被加密的Shamir Key（奖池）的密文
最终需要解密的密文
正确解密的内容所包含的Tag

开始计算

首先，解题者需要从挑选一个奖池，确定奖池的密文。

然后找出一个Nonce（随机数），将公开的游戏难度参数与Nonce通过argon2id算法进行计算，计算时间由出题者设置的难度决定。

如果出题者公开了Nonce范围，则在范围内寻找。

计算完成后会得到一个派生内容。

接着解题者需要将派生内容转换为 AES Key（具体转换规则由出题者公布），通过AES算法将奖池密文解密出来。

解密出内容后，可以通过Tag进行匹配（其实也可以不用匹配，AES-CGM模式下自带MAC校验），如果能成功匹配，则说明是正确的Nonce，成功得到一枚碎片；如果不能匹配成功，则说明是错误的Nonce，需要重新寻找。

当集齐出题者所设置的最少数量的碎片时，即可通过Shamir算法将碎片合成一个AES Master Key。

最后，通过这个AES Master Key，解密得到最终的奖品。

计算优化

寻找Nonce

如果出题者给出Nonce范围，则可以尝试采用随机+HashMap去重的方式，将一部分期望压在你的lucky上。

你可能计算一次就中，也可能计算完整个奖池才中😄。

当然，你也可以一个一个算。

并行计算

虽然出题者可以限制argon2id算法的并行数，但解题者可以并行的寻找Nonce并计算，只要解题者愿意付出额外的资源与成本😄。

算法讲解

argon2算法

argon2有些复杂，不讲（

Shamir算法

以下内容参考于Gemini

Shamir算法全名叫Shamir 秘密共享算法 (Shamir's Secret Sharing)。

Shamir算法的数学基础是多项式插值。

首先构造一个多项式

假设要隐藏的密钥是数值 $S$ 。随机生成一个 $m-1$ 次的多项式：

$f(x) = a_0 + a_1x + a_2x^2 + \dots + a_{m-1}x^{m-1}$

在这个多项式中，常数项 $a_0$ 为要隐藏的密钥 $S$ （即 $f(0) = S$ ），而其他的系数 $a_1, a_2, \dots, a_{m-1}$ 为随机生成。

然后，在这个多项式的曲线上取 $n$ 个不同的点 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ 。

在数学上，要唯一确定一个 $m-1$ 次的多项式，刚好需要 $m$ 个点。

只要任意 $m$ 个点，就可以通过拉格朗日插值法计算出完整的原多项式，从而求出 $a_0$ ，也就是还原出了真正的密钥 $S$ 。

如果凑齐点数少于 $m$ 个，即使拥有 $m-1$ 个点，也无法推导出常数项 $a_0$ 。

示例

例如典型的 (3, 5) 门限方案

门限 $m=3$ ，因此需要一个 $3-1=2$ 次的多项式。

二次多项式也就是一元二次方程，它的图像是一条抛物线 (Parabola)。
方程的形式为：

$f(x) = a_2x^2 + a_1x + S$

在这条抛物线上，随机切下 5 个不同的点（比如 $x=1, 2, 3, 4, 5$ 对应的坐标）。
5 个坐标点 $(x_1, y_1)$ 到 $(x_5, y_5)$ 。

在几何学中，任意三个不在一条直线上的点，可以唯一确定一条抛物线。只要有 3 个坐标点，通过方程计算，就能还原出这条抛物线，找到它与 Y 轴的交点（即 $x=0$ 时的值），即可把 $S$ 算出来。

如果只有 2 个点，两点只能确定一条直线。经过这两个点的抛物线有无数条，无法知道哪一条是真正的抛物线， $S$ 的可能性为无限大。

下面为具体数值演示

隐藏的密钥： $S = 42$ （也就是抛物线与 Y 轴交点的值，即 $x=0$ 时的 $y$ 值）。

方程： $f(x) = -2x^2 + 5x + 42$ （对还原者隐藏）。

生成的 5 个坐标点：

$(1, 45)$
$(2, 44)$
$(3, 39)$
$(4, 30)$
$(5, 17)$

假设已知的坐标分别是 $(1, 45)$ 、 $(3, 39)$ 和 $(4, 30)$

拉格朗日插值法 (Lagrange Interpolation)

拉格朗日插值法的核心思想是“加权”。对于每一个点的 $y$ 值，乘以一个特定的“权重系数”（通常用 $l$ 表示），然后相加即可得到 $x=0$ 时的密钥 $S$ 。

公式如下：

$S = y_1 \cdot l_1 + y_2 \cdot l_2 + y_3 \cdot l_3$

权重 $l$ 它只和的 $x$ 坐标 有关。

计算规则是：用其他的 $x$ 坐标除以“其他的 $x$ 坐标减去自己的 $x$ 坐标”，然后相乘。

把选出的三个点的 $x$ 坐标分别记为： $x_1=1$ ， $x_2=3$ ， $x_3=4$ 。

计算 $(1, 45)$ 的权重 $l_1$ ： 提取另外两个的 $x$ 坐标（ $3$ 和 $4$ ），与 $x$ 坐标（ $1$ ）进行计算：

$l_1 = \frac{x_2}{x_2 - x_1} \cdot \frac{x_3}{x_3 - x_1}$

$l_1 = \frac{3}{3 - 1} \cdot \frac{4}{4 - 1} = \frac{3}{2} \cdot \frac{4}{3} = \frac{12}{6} = 2$

计算 $(3, 39)$ 的权重 $l_2$ ： 提取另外两个的 $x$ 坐标（ $1$ 和 $4$ ），与 $x$ 坐标（ $3$ ）进行计算：

$l_2 = \frac{x_1}{x_1 - x_2} \cdot \frac{x_3}{x_3 - x_2}$

$l_2 = \frac{1}{1 - 3} \cdot \frac{4}{4 - 3} = \frac{1}{-2} \cdot \frac{4}{1} = -2$

计算 $(4, 30)$ 的权重 $l_3$ ： 提取另外两个的 $x$ 坐标（ $1$ 和 $3$ ），与 $x$ 坐标（ $4$ ）进行计算：

$l_3 = \frac{x_1}{x_1 - x_3} \cdot \frac{x_2}{x_2 - x_3}$

$l_3 = \frac{1}{1 - 4} \cdot \frac{3}{3 - 4} = \frac{1}{-3} \cdot \frac{3}{-1} = \frac{3}{3} = 1$

现在，将三个点的 $y$ 值与各自算出的权重相乘，然后相加：

$S = (y_1 \cdot l_1) + (y_2 \cdot l_2) + (y_3 \cdot l_3)$

$S = (45 \cdot 2) + (39 \cdot -2) + (30 \cdot 1)$

$S = 90 - 78 + 30$

$S = 42$

最后还原出了最初设定的密钥 42。

原始的解方程

依然使用上文 3 个坐标点： $(1, 45)$ 、 $(3, 39)$ 和 $(4, 30)$ 。

3 个点确定的抛物线，它的标准方程形式则为：

$y = ax^2 + bx + c$

目标是求出未知的系数 $a$ 、 $b$ 和 $c$ 。

注意： 当 $x = 0$ 时， $y = c$ 。因此，因此需要寻找的 $S$ 其实就是常数项 $c$ 。

将 3 个 $(x, y)$ 坐标分别代入标准方程中：

代入点 $(1, 45)$ ：

$a(1)^2 + b(1) + c = 45$

化简得： $a + b + c = 45$ (方程 ①)

代入点 $(3, 39)$ ：

$a(3)^2 + b(3) + c = 39$

化简得： $9a + 3b + c = 39$ (方程 ②)

代入点 $(4, 30)$ ：

$a(4)^2 + b(4) + c = 30$

化简得： $16a + 4b + c = 30$ (方程 ③)

现在，得到了一个包含三个未知数 ( $a, b, c$ ) 的三元一次方程组。

为了解开它，可以通过两个方程相减，先消去常数项 $c$ ：

1. 用方程 ② 减去方程 ①：

$(9a + 3b + c) - (a + b + c) = 39 - 45$

$8a + 2b = -6$

两边同除以 2，化简得： $4a + b = -3$ (方程 ④)

2. 用方程 ③ 减去方程 ②：

$(16a + 4b + c) - (9a + 3b + c) = 30 - 39$

$7a + b = -9$ (方程 ⑤)

3. 用方程 ⑤ 减去方程 ④，消去 $b$ ：

$(7a + b) - (4a + b) = -9 - (-3)$

$3a = -6$

解得： $a = -2$

4. 把 $a = -2$ 代回方程 ④，求 $b$ ：

$4(-2) + b = -3$

$-8 + b = -3$

解得： $b = 5$

现在已知 $a = -2$ 和 $b = 5$ 。将其代入方程 ① 中：

$a + b + c = 45$

$-2 + 5 + c = 45$

$3 + c = 45$

解得： $c = 42$

后记

其实这个游戏不仅可以用argon2id算法，也可以用RSW时间锁谜题这类算法。