Circomlib中的AliasCheck和Num2Bits strict

在 Circom（或任何 ZK circuit 语言）中的别名错误发生在信号的二进制数组编码的数字大于场元素可以容纳的值时。我们在本文中将信号和场元素交替使用。我们将场的特征称为 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 位二进制值可以容纳的值，但场元素无法。

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

[21888242871839275222246405745257275088548364400416034343698204186575808495617, 28948022309329048855892746252171976963317496166410141009864396001978282409983]

为了获取规模的感觉，如果我们计算 $p / 2^{254}$，结果是 0.7561，这意味着一个 p 大约可以容纳 254 位数字可表示的四分之三的数字。

当二进制表示约束溢出时静默失败

为了约束一个二进制数字 $b₀, b₁, …, bₙ$ 等于一个字段元素 v，我们写出以下 算术电路:

$$ b₀ + 2b₁ + … + nbₙ === v $$

同时约束每个 $bᵢ$ 的值为 $0$ 或 $1$。

但是，计算 $v = b_0 + 2 b_1 + … + n b_n$ 是按模 p 进行的。因此，如果计算 $b_0 + 2b_1 + … + nb_n$ 溢出 p，那么我们可以呈现一个二进制数 $b_0, b_1, …, b_n$，其值不是 v ，并创建一个错误的证明。例如，如果我们的模数是 11，那么 2 和 13 被认为是“相等”的，因为 13 模 11 等于 2。

小示例

假设 $p = 11$ 并且我们使用四位表示一个字段元素。这些位可以编码最大为 15 的数字。如果我们将 12 编码为二进制 (1100)，这将在模 11 下评估为 12 mod 11 = 1。所以我们可以声称 1100 是 1 的二进制表示。

具体来说：

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

在 Python 中演示

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

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

## 复制 Num2Bits 和 Bits2Num 使用的约束
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

    # 二进制转换必须是正确的
    assert num == acc

## 这不能在 Circom 中完成，因为 `value` 需要大于 p
## 但小于 $2^{254} - 1$
def malicious_witness_generator(nbits, value):
    bits = []
    for i in range(nbits):
        bit = va...