alias_bug.py

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)