ZK में डिफ़ॉल्ट डेटाटाइप फील्ड एलिमेंट (field element) है, जहां सभी अरिथमेटिक (arithmetic) एक बड़ी प्राइम संख्या (prime number) के मॉड्यूलो (modulo) किए जाते हैं। हालांकि, वर्चुअल मशीन (virtual machine) या एग्जीक्यूशन एनवायरनमेंट (execution environment) के आधार पर अधिकांश “वास्तविक” (real) गणना 32, 64, या 256-बिट संख्याओं का उपयोग करके की जाती है।

हमें 32-Bit एम्यूलेशन की आवश्यकता क्यों है?

कई क्रिप्टोग्राफ़िक हैश फ़ंक्शंस (cryptographic hash functions) 32-बिट वर्ड्स (words) पर काम करते हैं क्योंकि ऐतिहासिक रूप से 32 बिट्स कई CPUs का डिफ़ॉल्ट वर्ड साइज़ था। बाद में इसे बढ़ाकर 64 बिट्स कर दिया गया। EVM 256 बिट्स का उपयोग करता है ताकि यह keccak256 हैश को आसानी से समायोजित (accommodate) कर सके।

यदि हम किसी पारंपरिक हैश फ़ंक्शन या किसी ऐसी वर्चुअल मशीन के सही एग्जीक्यूशन (execution) को साबित करने के लिए ZK का उपयोग करना चाहते हैं जो फाइनाइट फील्ड्स (finite fields) का उपयोग नहीं करती है (ज्यादातर नहीं करती हैं), तो हमें एक फील्ड एलिमेंट के साथ पारंपरिक डेटाटाइप्स को “मॉडल” (model) करने की आवश्यकता है। इसलिए, हम Circom में एक फील्ड एलिमेंट (signal) का उपयोग उस संख्या को रखने के लिए करते हैं जो 32-बिट संख्या की क्षमता से अधिक नहीं हो सकती, भले ही signal 32 बिट्स से बहुत बड़े मानों (values) को धारण कर सकता हो।

32-bit वर्ड्स बनाम फाइनाइट फील्ड एलिमेंट्स (finite field elements)

एक 32-बिट वर्ड और एक फाइनाइट फील्ड एलिमेंट के बीच मुख्य अंतर वह बिंदु है जिस पर वे ओवरफ्लो (overflow) होते हैं। Circom, या bn128 कर्व (curve) का उपयोग करने वाली किसी भी भाषा में, ओवरफ्लो $p$ पर होता है जहाँ $p$ = 21888242871839275222246405745257275088548364400416034343698204186575808495617 है। 32-बिट मशीन में, ओवरफ्लो 4294967296 पर या सामान्य तौर पर $2^n$ पर होता है, जहाँ $n$ वर्चुअल मशीन में बिट्स की संख्या है।

कोई भी यह मान सकता है कि एक 32-बिट वर्चुअल मशीन सभी अरिथमेटिक मॉड्यूलो (arithmetic modulo) $2^{32}$ करती है। एक सामान्य वर्चुअल मशीन डिफ़ॉल्ट रूप से उस संख्या पर ओवरफ्लो हो जाती है। हालांकि, जब एक फाइनाइट फील्ड में मॉड्यूलर अरिथमेटिक (modular arithmetic) किया जाता है, तो मॉड्यूलो $2^{32}$ की गणना करने पर काफी सारे कंस्ट्रेंट्स (constraints) जुड़ जाएंगे (जैसा कि हम बाद में देखेंगे), लेकिन सौभाग्य से, इसे कुशलतापूर्वक करने के लिए एक उपयोगी गणितीय ट्रिक मौजूद है।

निम्नलिखित दो फ़ंक्शंस मॉड्यूलो $2^{32}$ की गणना करने में समान (equivalent) हैं:

Copy
contract DemoMod32 {
  function mod32(uint256 x) public pure returns (uint256) {
    return x % (2**32);
  }

  function mod32e(uint256 x) public pure returns (uint256) {
    // only keep the 32 least significant bits
    return uint256(uint32(x)); 
  }
}

हम केवल 32 लीस्ट सिग्निफिकेंट बिट्स (least significant bits) को रखकर आसानी से $\mod 2^{32}$ की गणना कर सकते हैं। इसका एक औपचारिक सत्यापन (formal verification) परिशिष्ट (appendix) में दिया गया है। 32-बिट संख्या वाले किसी signal पर कोई भी अरिथमेटिक ऑपरेशन करने से पहले, हमें यह पूरी तरह से सुनिश्चित करने की आवश्यकता है कि signal द्वारा धारण की गई संख्या वास्तव में 32 बिट्स में फिट होती है।

32-बिट रेंज चेक (range check)

यदि हम एक ऐसा ZK सर्किट बना रहे हैं जो 32-बिट वर्ड्स का उपयोग करके किसी गणना को सिमुलेट (simulate) करता है, तो हमें यह सुनिश्चित करना होगा कि कोई भी सिग्नल कभी भी $2^{32}$ से अधिक या उसके बराबर मान धारण न करे। ऐसा करने का एक सहज तरीका LessThan टेम्प्लेट (template) का उपयोग इस प्रकार करना है:

Copy
signal safe;
safe <== LessThan(252)([x, 2**32]);
safe === 1;

हालाँकि, यह सर्किट आवश्यकता से अधिक कंस्ट्रेंट्स (constraints) उत्पन्न करता है।

एक अधिक कुशल तरीका बाइनरी रिप्रेजेंटेशन (binary representation) का लाभ उठाना होगा। मुख्य विचार यह है कि एक संख्या को 32 बिट्स के साथ एनकोड (encode) किया जाए, और यदि यह 32 बिट्स में फिट हो जाती है, तो सर्किट सामान्य रूप से काम करता है। इसके विपरीत, यदि संख्या 32 बिट्स में फिट नहीं होती है, तो कंस्ट्रेंट्स संतुष्ट नहीं हो सकते। इसलिए, नीचे दिया गया सर्किट यह सुनिश्चित करता है कि in का मान $2^{32}-1$ या उससे कम हो।

Copy
include "circomlib/comparators.circom";

// 8 bit range check
template RangeCheck() {
  signal input in;
  component n2b = Num2Bits(32);
  n2b.in <== in;
}

component main = RangeCheck();

// if in = 2**32 - 1, it will accept
// if in = 2**32 it will reject

LessThan की तरह Num2Bits के आउटपुट को कंस्ट्रेंट (constrain) करना आवश्यक नहीं है, क्योंकि आंतरिक रूप से, यह पहले से ही out को शून्य या एक होने के लिए कंस्ट्रेंट करता है, और बाइनरी रिप्रेजेंटेशन को इनपुट के बराबर (lc1 === in के माध्यम से) कंस्ट्रेंट करता है, जैसा कि नीचे Num2Bits टेम्प्लेट में देखा जा सकता है:

Copy
template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0; // CONSTRAINT HAPPENS HERE
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }

    lc1 === in;
}

32-Bit एडिशन (Addition)

मान लें कि हम दो फील्ड एलिमेंट्स x और y को एक साथ जोड़ना चाहते हैं, जो 32-बिट संख्याओं का प्रतिनिधित्व करते हैं।

32-बिट एडिशन का एक साधारण (naïve) इम्प्लीमेंटेशन यह है कि फील्ड एलिमेंट को 32-बिट्स में बदला जाए, फिर एक “एडिशन सर्किट (addition circuit)” बनाया जाए जो प्रत्येक बिट को जोड़ता है और ओवरफ्लो को कैरी (carry) करता है। हालाँकि, यह आवश्यकता से बड़ा सर्किट बनाता है।

इसके बजाय, हम निम्नलिखित कार्य कर सकते हैं:

1. ऊपर बताई गई रणनीति का उपयोग करके x और y का रेंज चेक (range check) करें।
2. x और y को फील्ड एलिमेंट्स के रूप में एक साथ जोड़ें, अर्थात, z <== x + y।
3. z को 33-बिट संख्या में बदलें।
4. 33-बिट संख्या के 32 लीस्ट सिग्निफिकेंट बिट्स (least significant bits) को फील्ड एलिमेंट में बदलें।

इसे इस प्रकार देखा जा सकता है:

x + y अधिक से अधिक एक 33-बिट संख्या तक ओवरफ्लो हो सकता है। विचार करें कि x और y का अधिकतम मान $2^{32}-1$ हो सकता है। यदि हम उस मान को स्वयं में जोड़ते हैं, तो हमें प्राप्त होता है:

अंतिम संख्या को होल्ड करने के लिए 33 बिट्स की आवश्यकता होती है। (याद रखें कि 33 बिट्स द्वारा होल्ड की जा सकने वाली अधिकतम संख्या $2^{33} - 1$ है। इसलिए, उपरोक्त संख्या दूसरी सबसे बड़ी संख्या है जिसे 33 बिट्स होल्ड कर सकते हैं।) इस प्रकार, 33वें बिट को हटाने से पहले योग (sum) को होल्ड करने के लिए हमें केवल 33 बिट्स की आवश्यकता होती है।

Circom का उपयोग करके 32-बिट एडिशन को एम्यूलेट (emulate) और सत्यापित (verify) करने का कोड नीचे दिया गया है:

Copy
include "circomlib/comparators.circom";
include "circomlib/bitify.circom";

template Add32(n) {
  signal input x;
  signal input y;
  signal output out;

  // range check x and y
  component rCheckX = Num2Bits(32);
  component rCheckY = Num2Bits(32);
  rCheckX.in <== x;
  rCheckY.in <== y;
  
  // convert the sum to 33 bits
  component n2b33 = Num2Bits(33);
  n2b33.in <== x + y;

  // convert the least significant 32 bits
  // to the final result
  component b2n = Bits2Num(32);
  for (var i = 0; i < 32; i++) {
    b2n.in[i] <== n2b33.out[i];
  }

  b2n.out ==> out;
}

32-Bit मल्टीप्लीकेशन (Multiplication)

32-बिट मल्टीप्लीकेशन का लॉजिक काफी हद तक 32-बिट एडिशन के समान है, सिवाय इसके कि हमें केवल अंतिम 32 बिट्स को सेव करने से पहले 32-बिट मल्टीप्लीकेशन के लिए अस्थायी रूप से 64 बिट्स तक की अनुमति देनी होगी:

अंतिम संख्या को होल्ड करने के लिए 64 बिट्स की आवश्यकता होती है।

इस सर्किट का इम्प्लीमेंटेशन पाठक के लिए एक अभ्यास के रूप में छोड़ दिया गया है।

32-Bit डिवीज़न (Division) और मॉड्यूलो (Modulo)

ZK में इंटीजर डिवीज़न (integer division) सबसे समस्याग्रस्त बग्स (bugs) में से एक है, क्योंकि इसे ठीक से कंस्ट्रेंट (constrain) करना एडिशन और मल्टीप्लीकेशन के उदाहरणों की तुलना में बहुत कठिन है। यहाँ वास्तविक दुनिया में अंडरकंस्ट्रेंट (underconstrained) डिवीज़न के कुछ उदाहरण दिए गए हैं:

• https://code4rena.com/reports/2023-10-zksync#h-01-missing-range-constraint-on-remainder-check-in-div-opcode-implementation
• https://github.com/succinctlabs/sp1/issues/746

इंटीजर डिवीज़न में न्यूमरेटर (numerator), डिनॉमिनेटर (denominator), कोशेंट (quotient) और रिमाइंडर (remainder) के बीच का संबंध है:

हालाँकि, केवल वह कंस्ट्रेंट (constraint) यह सुनिश्चित करने के लिए पर्याप्त नहीं है कि डिवीज़न ठीक से किया गया था।

उदाहरण के लिए, मान लें कि हम यह साबित करने का प्रयास कर रहे हैं कि हमने 12 / 7 = 1 की गणना की है। हमारे सर्किट में ये मान होंगे:

हालाँकि, निम्नलिखित विटनेस (witness) भी इस कंस्ट्रेंट को संतुष्ट करता है:

हम एक कंस्ट्रेंट जोड़कर इससे बचाव कर सकते हैं कि रिमाइंडर स्पष्ट रूप से डिनॉमिनेटर से कम होना चाहिए।

इसके अलावा, हमें निम्नलिखित संभावित बग्स के बारे में पता होना चाहिए:

• 254-बिट फील्ड में 32 बिट्स के लिए यह चिंता का विषय नहीं है (जो कि डिफ़ॉल्ट रूप से Circom उपयोग करता है), लेकिन हम यह सुनिश्चित करना चाहते हैं कि गणना $\text{denominator}\times\text{quotient}$ अंतर्निहित (underlying) फाइनाइट फील्ड को ओवरफ्लो न करे।
• अधिक सामान्यतः, हम नहीं चाहते कि गणना $\text{denominator}\times\text{quotient}+\text{remainder}$ ओवरफ्लो हो। यदि denominator और quotient को 32 बिट्स पर रेंज-चेक (range-check) किया गया है, तो प्रोडक्ट (product) $\text{denominator}\times\text{quotient}$ द्वारा धारण किए जा सकने वाले बिट्स की अधिकतम संख्या 64 बिट्स है, और यदि remainder को 32 बिट्स पर रेंज-चेक किया गया है, तो $\text{denominator}\times\text{quotient}+\text{remainder}$ के लिए आवश्यक बिट्स की अधिकतम मात्रा 65 बिट्स हो सकती है। इसलिए, 32 बिट्स के VM बिट साइज़ के साथ काम करना Circom के डिफ़ॉल्ट फील्ड के लिए चिंता का विषय नहीं है, लेकिन अन्य VM बिट साइज़, जैसे 128 बिट्स के लिए, एक ओवरफ्लो संभव है।
• आप किस ZKVM पर विचार कर रहे हैं, उसके आधार पर शून्य से विभाजन (Division by zero) का अप्रत्याशित व्यवहार हो सकता है। उदाहरण के लिए, शून्य से विभाजन होने पर EVM पैनिक (panic) नहीं करता, बल्कि शून्य लौटाता है। RISC-V आर्किटेक्चर में, शून्य से विभाजन एक ऐसा वर्ड लौटाता है जिसके सभी बिट्स 1 पर सेट होते हैं।

केवल एडिशन और मल्टीप्लीकेशन का उपयोग करके सीधे इंटीजर डिवीज़न की गणना करना अव्यावहारिक (impractical) है (मल्टीप्लीकेशन के लिए Karatsuba’s method या efficient integer division जैसे कुशल एल्गोरिदम for-loops या रिकर्सन (recursion) का उपयोग करते हैं, जो एडिशन और मल्टीप्लीकेशन पर अच्छी तरह से मैप नहीं होते हैं), इसलिए इंटीजर डिवीज़न के परिणाम की गणना कंस्ट्रेंट्स के बाहर करना बेहतर है।

Circom में, / ऑपरेटर मॉड्यूलर डिवीज़न (मल्टीप्लिकेटिव इनवर्स द्वारा गुणा) को संदर्भित करता है और \ ऑपरेटर इंटीजर डिवीज़न को संदर्भित करता है। निम्नलिखित कोड दिखाता है कि हम कैसे साबित कर सकते हैं कि हमने कोशेंट और रिमाइंडर की सही गणना की है। हम रिमाइंडर की गणना को भी शामिल करते हैं क्योंकि जब हम यह साबित करते हैं कि हमने इंटीजर डिवीज़न की सही गणना की है तो यह हमें मुफ्त में मिल जाता है।

Copy
include "circomlib/comparators.circom";
include "circomlib/bitify.circom";

template DivMod(wordSize) {
  // a wordSize over this could overflow 252
  assert(wordSize < 125);

  signal input numerator;
  signal input denominator;

  signal output quotient;
  signal output remainder;

  quotient <-- numerator \ denominator;
  remainder <-- numerator % denominator;
  
  // quotient and remainder still need
  // to be range checked because the
  // prover can supply any value
  
  // range check all the signals
  component n2bN = Num2Bits(wordSize);
  component n2bD = Num2Bits(wordSize);
  component n2bQ = Num2Bits(wordSize);
  component n2bR = Num2Bits(wordSize);
  n2bN.in <== numerator;
  n2bD.in <== denominator;
  n2bQ.in <== quotient;
  n2bR.in <== remainder;

  // core constraint
  numerator === quotient * denominator  + remainder;

  // remainder must be less than the denominator
  signal remLtDen;
  
  // depending on the application, we might be able
  // to use fewer than 252 bits
  remLtDen <== LessThan(wordSize)([remainder, denominator]);
  remLtDen === 1;

  // denominator is not zero
  signal isZero;
  isZero <== IsZero()(denominator);
  isZero === 0;
}

component main = DivMod(32);

32-Bit बिटशिफ्ट (Bitshift)

मान लें कि हम निम्नलिखित कोड को एम्यूलेट करना चाहते हैं:

Copy
uint32 x;
uint32 s;
x << s;

s द्वारा एक लेफ्ट-शिफ्ट (left-shift) $2^s$ से गुणा करने के बराबर है जहाँ $s$ शिफ्ट का आकार है, और s द्वारा एक राइट-शिफ्ट (right-shift) $2^s$ से विभाजन के बराबर है। जैसा कि पिछले अध्याय में देखा गया था, पावर (powers) की गणना कंस्ट्रेंट्स का एक काफी बड़ा सेट बना सकती है। इसलिए, वर्ड साइज़ माइनस 1 तक 2 की हर पावर को पहले से कैलकुलेट (precompute) करना आमतौर पर अधिक कुशल होता है। इस प्रकार, 32-बिट संख्या के लेफ्ट शिफ्ट के लिए, हम 31 (वर्ड साइज़ (32) - 1) तक 2 की हर पावर को पहले से कैलकुलेट करते हैं: 1, 2, 4, 8, …, $2^{31}$ और पहले चर्चा की गई कंडीशनल सेलेक्शन (conditional selection) तकनीकों का उपयोग करके x को उपयुक्त चयन से गुणा करते हैं। यदि शिफ्ट की मात्रा 32 या अधिक है, तो हम शून्य से गुणा करते हैं।

इसका इम्प्लीमेंटेशन पाठक के लिए एक अभ्यास के रूप में छोड़ दिया गया है।

32-Bit AND, NOT, OR, XOR, और NOT

Circomlib gates library में इनमें से प्रत्येक सर्किट के लिए इम्प्लीमेंटेशन मौजूद हैं और वे स्वतः स्पष्ट (self-explanatory) हैं, इसलिए हम पाठक को वहां कोड पढ़ने के लिए प्रोत्साहित करते हैं। हम नीचे टेम्प्लेट दिखाते हैं कि निम्नलिखित के लिए ऑपरेशन को कैसे एम्यूलेट किया जाए:

बिटवाइज़ AND (Bitwise AND)

Copy
uint32 a;
uint32 b;
a & b;

बिटवाइज़ NOT (Bitwise NOT)

Copy
uint32 x;
~x; // flip all the bits

a और b के बिटवाइज़ AND की गणना करने और कंस्ट्रेंट करने का कोड नीचे दिया गया है।

Copy
include "circomlib/gates.circom";
include "circomlib/bitify.circom";

template BitwiseAnd32() {
  signal input a;
  signal input b;
  signal output out;

  // range check
  component n2ba = Num2Bits(32);
  component n2bb = Num2Bits(32);
  n2ba.in <== a;
  n2bb.in <== b;

  component b2n = Bits2Num(32);
  component Ands[32];
  for (var i = 0; i < 32; i++) {
    Ands[i] = AND();
    Ands[i].a <== n2ba.out[i];
    Ands[i].b <== n2bb.out[i];
    Ands[i].out ==> b2n.in[i];
  }

  b2n.out ==> out;
}

component main = BitwiseAnd32();

NOT, OR, और XOR के शेष ऑपरेशंस पाठक के लिए एक अभ्यास के रूप में छोड़ दिए गए हैं।

ZK EVMs 256-बिट संख्याओं को कैसे हैंडल करते हैं

डिफ़ॉल्ट Circom फील्ड 256-बिट संख्याओं को होल्ड नहीं कर सकता। इसके बजाय, EVM में प्रत्येक वर्ड को छोटे वर्ड साइज़ की एक सूची (list) के साथ मॉडल किया जाना चाहिए, बिल्कुल उसी तरह जैसे एक 64-बिट कंप्यूटर EVM को एम्यूलेट कर सकता है।

उदाहरण के लिए, 256-बिट संख्या को चार 64-बिट वर्ड्स के साथ मॉडल किया जा सकता है। जोड़ते समय, हम ओवरफ्लो को कम महत्वपूर्ण (less significant) वर्ड्स से अगले महत्वपूर्ण (next significant) वर्ड में कैरी (carry) करते हैं। यदि सबसे महत्वपूर्ण (most significant) वर्ड ओवरफ्लो हो जाता है, तो हम बस ओवरफ्लो को हटा (discard) देते हैं।

परिशिष्ट A (Appendix A): समानता के प्रमाण (Proofs of Equivalence)

हमने निम्नलिखित फ़ंक्शंस की समानता (equivalence) प्रदर्शित करने के लिए Certora प्रूवर (prover) का उपयोग किया:

Copy
contract DemoMod32 {
    function mod32(uint256 x) public pure returns (uint256) {
        return x % (2**32);
    }

    function mod32e(uint256 x) public pure returns (uint256) {
        // only keep the 32 least significant bits
        return uint256(uint32(x)); 
    }
}

यहाँ Certora वेरिफिकेशन लैंग्वेज रूल (verification language rule) है:

Copy
methods {
  function mod32(uint256) external returns (uint256) envfree;
  function mod32e(uint256) external returns (uint256) envfree;
}

rule test_Mod32AndMod32E_Equivalence() {
  uint256 x;
  assert mod32(x) == mod32e(x);
}

यहाँ Certora रिपोर्ट है:

https://prover.certora.com/output/541734/6cd3303cb5f5441e8773adb5c79787d7?anonymousKey=0b945ee1440cd67efed3efba3162b0f924e8cf8f