Circom (या किसी भी ZK सर्किट भाषा) में एक alias bug तब होता है जब सिग्नल्स का एक बाइनरी एरे किसी ऐसे नंबर को एन्कोड करता है जो field element की क्षमता से बड़ा होता है। इस लेख में हम सिग्नल्स (signals) और फील्ड एलिमेंट्स (field elements) का उपयोग एक-दूसरे के स्थान पर (interchangeably) करेंगे। हम field की विशेषता (characteristic) को p के रूप में संदर्भित करते हैं। मोटे तौर पर कहें तो, p वह मान है जिस पर सिग्नल “overflow” करता है। यह सभी अरिथमेटिक ऑपरेशन्स (arithmetic operations) में निहित मॉड्यूलो (implicit modulo) का मान है।

डिफ़ॉल्ट रूप से, Circom p को 21888242871839275222246405745257275088548364400416034343698204186575808495617 पर सेट करता है, जिसे स्टोर करने के लिए 254 बिट्स की आवश्यकता होती है। हालाँकि, $2^{254} - 1 (\sim2.89\times10^{76})$ डिफ़ॉल्ट p ($\sim2.18\times10^{76}$) से बड़ा है। अर्थात्, 254 बिट्स उन नंबर्स को एन्कोड कर सकते हैं जो Circom सिग्नल्स की स्टोर करने की क्षमता से बड़े होते हैं।

नीचे हम इन मानों को दर्शाने वाली एक नंबर लाइन प्लॉट कर रहे हैं, जो लगभग स्केल के अनुसार है:

0 से $p - 1$ (हरी रेखा का खंड) वह अंतराल है जिसे एक Circom field element होल्ड कर सकता है, और p से $2^{254} - 1$ (लाल खंड) वे मान हैं जिन्हें 254 बिट का बाइनरी मान होल्ड कर सकता है, लेकिन एक field element नहीं कर सकता।

“डेंजर ज़ोन (danger zone)” वे 254 बिट बाइनरी मान हैं जो p - 1 से बड़े हैं। ये अंतराल $[p, 2^{254} − 1]$ में आने वाले नंबर हैं। Circom के (डिफ़ॉल्ट) मामले में, यह रेंज $[p, 2^{254} − 1]$ इस प्रकार है:

[21888242871839275222246405745257275088548364400416034343698204186575808495617, 28948022309329048855892746252171976963317496166410141009864396001978282409983]

पैमाने (scale) का अंदाज़ा लगाने के लिए, यदि हम $p / 2^{254}$ को विभाजित करते हैं तो हमें 0.7561 मिलता है, जिसका अर्थ है कि p 254 बिट नंबर द्वारा दर्शाए जा सकने वाले नंबर्स का लगभग 3/4 हिस्सा होल्ड कर सकता है।

जब Binary representation constraints ओवरफ़्लो होते हैं तो वे चुपचाप (silently) विफल हो जाते हैं

एक बाइनरी नंबर $b₀, b₁, ..., bₙ$ को एक field element v के बराबर constrain करने के लिए, हम निम्नलिखित arithmetic circuit लिखते हैं:

और साथ ही प्रत्येक $bᵢ$ को $0$ या $1$ होने के लिए constrain करते हैं।

हालाँकि, गणना $v = b_0 + 2 * b_1 + … + n * b_n$ मॉड्यूलो (modulo) p के साथ की जाती है। इसलिए, यदि गणना $b_0 + 2b_1 + … + nb_n$, p को ओवरफ़्लो कर जाती है, तो हम एक ऐसा बाइनरी नंबर $b_0, b_1, ..., b_n$ प्रस्तुत कर सकते हैं जिसका मान v नहीं है और एक झूठा प्रूफ (false proof) बना सकते हैं। उदाहरण के लिए, यदि हमारा मॉड्यूलो 11 है, तो 2 और 13 एक-दूसरे के “बराबर” हैं क्योंकि 13 mod 11 का मान 2 होता है।

छोटा उदाहरण

मान लीजिए $p = 11$ है और हम एक field element का प्रतिनिधित्व (represent) करने के लिए चार बिट्स का उपयोग कर रहे हैं। ये बिट्स 15 तक के बड़े नंबर्स को एन्कोड कर सकते हैं। यदि हम 12 को बाइनरी में (1100) के रूप में एन्कोड करते हैं, तो इसका मूल्यांकन 12 modulo 11 = 1 के रूप में होगा। इसलिए हम यह दावा कर सकते हैं कि 1100, 1 का बाइनरी प्रतिनिधित्व है।

विशेष रूप से:

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

Python में प्रदर्शन (Demonstration)

हमलावर (attacker) द्वारा उपयोग किए जा रहे मानों को देखने के लिए, नीचे हम Python में Circomlib के Bits2Num और Num2Bits द्वारा उपयोग किए जाने वाले constraint को फिर से बना रहे हैं ताकि मानों को आसानी से प्रिंट किया जा सके:

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), और इसका alias $3 + p$ — जिसे 254 बिट नंबर के रूप में एन्कोड किया जा सकता है।

AliasCheck और Num2Bits_strict तथा Bits2Num_strict के साथ बग की रोकथाम (Bug prevention)

Circomlib’s bitify library में बिट कन्वर्ज़न टेम्प्लेट्स के “strict” संस्करण बाइनरी एरे को AliasCheck टेम्प्लेट में पास करके alias bug को रोकते हैं।

AliasCheck template एक बाइनरी एरे लेता है और यह assert करता है कि एन्कोड किया गया मान उस अधिकतम मान से कम है जिसे field element होल्ड कर सकता है:

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, p - 1 को संदर्भित करने के लिए -1 का उपयोग करता है। compConstant एक बाइनरी इनपुट लेता है (जो field element की होल्ड करने की क्षमता से बड़े मान को एन्कोड कर सकता है) और यदि यह एक निश्चित थ्रेशोल्ड (threshold) से कम या उसके बराबर है तो 0 लौटाता है, और यदि बाइनरी मान थ्रेशोल्ड से अधिक है तो 1 लौटाता है।

compConstant के आउटपुट को 0 तक constrain करके, और तुलना (comparison) के लिए कॉन्स्टेंट (constant) को -1 पर सेट करके, AliasCheck उन बाइनरी नंबर्स को अस्वीकार कर देता है जो p से बड़े होते हैं।

यदि बाइनरी एरे में फ़ील्ड द्वारा एन्कोड किए जा सकने वाले बिट्स से कम बिट्स हैं, तो alias bugs का कोई ख़तरा नहीं है

किसी field element पर Num2Bits लागू करने से उस नंबर पर एक रेंज चेक (range check) भी लागू होता है ताकि वह $2^n$ से कम हो, जहाँ n बिट्स की संख्या है। उदाहरण के लिए, यदि n = 4 है और p डिफ़ॉल्ट मान है, और हम इनपुट सिग्नल को 17 पर सेट करते हैं, तो परिणाम चुपचाप बाइनरी 1 (0001) में ओवरफ़्लो नहीं होगा — सर्किट संतुष्ट (satisfied) नहीं होगा।

यही कारण है कि Circomlib में Num2Bits_strict और Bits2Num_strict में बिट्स की संख्या को 254 पर हार्डकोड (hardcode) किया गया है — यह वह मान है जिस पर aliases प्रकट हो सकते हैं।

यही कारण है कि LessThan टेम्प्लेट डेवलपर्स को 252 बिट्स से अधिक का तुलनित्र (comparator) बनाने की अनुमति नहीं देता है। यह alias 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 option), तो यह जाँचना सुनिश्चित करें कि Num2Bits_strict, Bits2Num_strict, AliasCheck, और CompConstant अभी भी आपको alias bugs से बचाते हैं क्योंकि वे 254 बिट्स का उपयोग करने के लिए हार्डकोडेड हैं।

बग ढूँढने की चुनौती (Spot the bug challenge)

यहाँ एक CTF जिसे हमने X पर पोस्ट किया था (पूर्व में Twitter) दिया गया है, जिसमें इस लेख में वर्णित बग मौजूद है:

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);

उपरोक्त कोड के साथ समस्या यह है कि 254 बिट्स की अनुमति देने के कारण ओवरफ़्लो होता है, जिससे कई witnesses बन जाते हैं जो एक ही हैश (hash) की ओर ले जाते हैं।

याद रखें, एक arithmetic circuit का इनपुट केवल input लेबल किए गए सिग्नल्स ही नहीं होते हैं, बल्कि सर्किट में मौजूद इसका प्रत्येक सिग्नल होता है। Circom हमें input सिग्नल्स में दिए गए मानों के आधार पर कुछ सिग्नल्स को “भरने (fill in)” के लिए एक बेहतरीन C-जैसी प्रोग्रामिंग भाषा प्रदान करता है, लेकिन यह कोड अंतिम constraint system का हिस्सा नहीं होता है।

उपरोक्त कोड में, 254 बिट का बाइनरी एरे Num2Bits के आउटपुट सिग्नल्स और Bits2Num के इनपुट सिग्नल्स में रखा जाता है।

बाइनरी एरे को एन्कोड करने के लिए उपयोग किए जाने वाले सिग्नल्स में गलत मान डालने (inject) के लिए, हमें hacking underconstrained Circom circuits पर हमारे ट्यूटोरियल में वर्णित तकनीक का उपयोग करने की आवश्यकता है। उपरोक्त कोड के लिए एक proof of concept (PoC) जनरेट करने के लिए, हम निम्नलिखित कदम उठाते हैं:

1. एक नंबर u का उपयोग करके एक हैश (hash) जनरेट करें जो इतना छोटा हो कि उस रेंज में उसका एक alias हो, यानी $[p, 2^{254} − 1]$।
2. input in पर लागू उसी नंबर का उपयोग करके एक malicious witness जनरेट करें, लेकिन बाइनरी एरे को फिर से असाइन करें ताकि वह u + p मान होल्ड कर सके।
3. इन दोनों सिग्नल असाइनमेंट द्वारा जनरेट किया गया हैश समान होगा, लेकिन witness अलग होगा।

संक्षेप में, चुनौती (challenge) में दिया गया कोड एक alias bug के माध्यम से second preimage attack के प्रति संवेदनशील (vulnerable) है।

मूल रूप से 13 जुलाई को प्रकाशित