Circom（或任何 ZK 电路语言）中的别名 Bug（alias bug）发生在信号的二进制数组编码的数字大于域元素（field element）所能容纳的值时。在本文中，我们将交替使用信号（signals）和域元素（field elements）这两个词。我们将域的特征（characteristic）称为 p。通俗来讲，p 是信号发生“溢出”的值。它是所有算术运算中隐式取模的值。

默认情况下，Circom 将 p 设置为 21888242871839275222246405745257275088548364400416034343698204186575808495617，这需要 254 位来存储。然而，$2^{254} - 1 (\sim2.89\times10^{76})$ 大于默认的 p ($\sim2.18\times10^{76}$)。也就是说，254 位可以编码比 Circom 信号所能存储的值更大的数字。

下面我们在数轴上绘制了这些值，比例近似实际情况：

0 到 $p - 1$（绿色线段）是 Circom 域元素可以容纳的区间，而 p 到 $2^{254} - 1$（红色线段）是 254 位二进制值可以容纳但域元素无法容纳的值。

“危险区域（danger zone）”是指大于 p - 1 的 254 位二进制值。这些是位于区间 $[p, 2^{254} − 1]$ 内的数字。在 Circom（默认）的情况下，范围 $[p, 2^{254} − 1]$ 是

[21888242871839275222246405745257275088548364400416034343698204186575808495617, 28948022309329048855892746252171976963317496166410141009864396001978282409983]

为了让你有个直观的感受，如果我们计算 $p / 2^{254}$，我们会得到 0.7561，这意味着一个 p 可以容纳大约 3/4 的由 254 位数字所能表示的数字。

二进制表示的约束在溢出时会静默失效

为了将二进制数 $b₀, b₁, ..., bₙ$ 约束为等于域元素 v，我们编写了以下算术电路：

并且还约束每个 $bᵢ$ 必须为 $0$ 或 $1$。

然而，计算 $v = b_0 + 2 * b_1 + … + n * b_n$ 是在模 p 的情况下完成的。因此，如果计算 $b_0 + 2b_1 + … + nb_n$ 溢出了 p，那么我们就可以提供一个值不为 v 的二进制数 $b_0, b_1, ..., b_n$，并创建一个伪造的证明。例如，如果我们的模数是 11，那么 2 和 13 就是彼此“相等”的，因为 13 取模 11 的结果是 2。

一个简单的例子

假设 $p = 11$，并且我们使用四位二进制来表示一个域元素。这些位可以编码最大为 15 的数字。如果我们将 12 编码为二进制数 (1100)，它的求值结果将是 12 模 11 = 1。因此，我们可以声称 1100 是 1 的二进制表示。

具体来说：

$8(1) + 4(1) + 2(0) + (0) == 1 (\mod 11 )$

Python 演示

为了查看攻击者使用的值，下面我们在 Python 中重新实现了 Circomlib 的 Bits2Num 和 Num2Bits 所使用的约束，以便可以轻松地打印出这些值：

Copy
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# replicates the constraints Num2Bits and Bits2Num use
def constrain_modulo_p(bits, num, p):
    multiplier = 1
    acc = 0
    for i in range(len(bits)):
        assert bits[i] == 0 or bits[i] == 1
        acc = (acc + multiplier * bits[i]) % p
        multiplier = (multiplier * 2) % p

    # binary conversion must be correct
    assert num == acc

# this cannot be done in Circom because `value` needs to be higher than p
# but less than 2^254 - 1
def malicious_witness_generator(nbits, value):
    bits = []
    for i in range(nbits):
        bit = value >> i & 1

        bits.append(bit)

    return bits

# "normal" case -- constraints pass
constrain_modulo_p([1,1], 3, p)

# adversary case -- constraints pass, but the binary number is not 3
adversary_bits = malicious_witness_generator(254, 3 + p)
print(adversary_bits)

# no asserts are triggered although adversary_bits ≠ 3
constrain_modulo_p(adversary_bits, 3, p)

这里的重点是，constrain_modulo_p 接受 3 的两种二进制表示：3 的“正确”二进制表示（11），以及它的别名 $3 + p$——该别名可以被编码为 254 位的数字。

使用 AliasCheck、Num2Bits_strict 和 Bits2Num_strict 预防 Bug

Circomlib 的 bitify 库 中位转换模板的“strict”版本通过将二进制数组传递给 AliasCheck 模板来防止别名 bug。

AliasCheck 模板 接收一个二进制数组，并断言所编码的值小于域元素能够容纳的最大值

Copy
pragma circom 2.0.0;

include "compconstant.circom";

template AliasCheck() {

    signal input in[254];

    component compConstant = CompConstant(-1);

    for (var i=0; i<254; i++) in[i] ==> compConstant.in[i];
    // compConstant returns 1 if the binary
    // input is greater than the supplied constant
    compConstant.out === 0;
}

AliasCheck 使用 -1 来表示 p - 1。compConstant 接受一个二进制输入（它可能编码一个大于域元素所能容纳的值），如果该值小于或等于特定阈值，则返回 0，如果二进制值大于该阈值，则返回 1。

通过将 compConstant 的输出约束为 0，并将用于比较的常数设置为 -1，AliasCheck 会拒绝大于 p 的二进制数。

如果二进制数组包含的位数少于域可编码的位数，则不存在别名 bug 的危险

将 Num2Bits 应用于域元素时，也会对该数字进行范围检查，确保其小于 $2^n$，其中 n 是位数。例如，如果 n = 4，p 是默认值，并且我们将输入信号设置为 17，结果将不会静默溢出到二进制 1 (0001)——该电路将不会被满足。

这就是为什么 Circomlib 中的 Num2Bits_strict 和 Bits2Num_strict 将位数硬编码为 254——正是在这个值上可能会出现别名。

这也正是 LessThan 模板不允许开发者构建位数超过 252 位的比较器的原因。这避免了因为别名 bug 而引发的安全隐患（footgun）。

Copy
template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0] + (1<<n) - in[1];

    out <== 1-n2b.out[n];
}

如果你在 Circom 编译器中更改了默认的 p （使用 -p 选项），请务必检查 Num2Bits_strict、Bits2Num_strict、AliasCheck 和 CompConstant 是否仍然能够保护你免受别名 bug 的影响，因为它们被硬编码为了使用 254 位。

找 Bug 挑战

这是我们在 X（原 Twitter）上发布的一个 CTF 题目，它包含了本文描述的 bug：

Copy
pragma circom 2.1.8;

include ".node_modules/circomlib/circuits/comparators.circom";
include ".node_modules/circomlib/circuits/poseidon.circom";

template UnsafePoseidon(n) {
    signal input in;
    signal output out;

    component n2b = Num2Bits(n);
    component b2n = Bits2Num(n);
    component phash = Poseidon(1);

    n2b.in <== in;
    for (var i = 0; i < n; i++) {
        b2n.in[i] <== n2b.out[i];
    }

    phash.inputs[0] <== b2n.out;
    phash.out ==> out;
}

component main = UnsafePoseidon(254);

上述代码的问题在于存在多个不同的见证（witnesses）会导致相同的哈希值，这是因为允许使用 254 位数据而导致了溢出。

请记住，算术电路的输入不仅仅是那些被标记为 input 的信号，而是电路中的 每一个 信号。Circom 为我们提供了一种类似 C 语言的友好编程语言，以基于 input 信号提供的值来“填充”某些信号，但这些代码并不是最终约束系统的一部分。

在上述代码中，这个 254 位二进制数组保存在 Num2Bits 的输出信号和 Bits2Num 的输入信号中。

为了将错误的值注入到用于编码二进制数组的信号中，我们需要使用在攻击约束不足的 Circom 电路教程中所描述的技术。要为上述代码生成概念验证，我们需要采取以下步骤：

1. 使用一个足够小的数字 u 生成一个哈希值，使得该数字在此范围内（即 $[p, 2^{254} − 1]$）存在一个别名。
2. 使用应用于 input in 的相同数字来生成恶意见证，但将二进制数组重新赋值为保存 u + p 的值。
3. 这两种信号赋值所生成的哈希值将是相同的，但见证是不同的。

总之，挑战中的代码容易受到利用别名 bug 发起的第二原像攻击。

原载于 7 月 13 日