जब हम पावर्स (powers), फैक्टोरियल्स (factorials), या फिबोनाची (Fibonacci) सीक्वेंस की गणना जैसे इटरेटिव कंप्यूटेशंस (iterative computations) करते हैं, तो हमें एक निश्चित बिंदु के बाद “कंप्यूटेशन को रोकना” होता है।

उदाहरण के लिए, यदि हम $x^7$ की गणना कर रहे हैं, तो हम $x$ को स्वयं से सात बार गुणा करेंगे। हालाँकि, एक अरिथमेटिक सर्किट (arithmetic circuit) में कंडीशनल स्टॉपिंग (conditional stopping) संभव नहीं है। चूंकि सर्किट एक निश्चित आकार के होते हैं (अंतर्निहित R1CS में पंक्तियों की एक निश्चित संख्या होती है और आप इसे बदल नहीं सकते हैं), इसलिए उन्हें इतना बड़ा होना चाहिए कि वे हर उस घातांक (exponent) को कवर कर सकें जिसकी हम गणना करना चाहते हैं।

इसलिए, इसका समाधान यह है कि हम व्यवहार में जो गणना करने की उम्मीद करते हैं, उससे बड़ी किसी सीमा तक हर संभव वैल्यू की गणना करें। फिर हम वांछित वैल्यू चुनने के लिए एक Quin selector का उपयोग करते हैं।

यह अध्याय फैक्टोरियल (factorial) और फिबोनाची (Fibonacci) सीक्वेंस के साथ ऐसा करने का एक उदाहरण दिखाता है, और पावर (power) की गणना को एक अभ्यास (exercise) के रूप में छोड़ देता है।

हम इनमें से प्रत्येक कंप्यूटेशन को एक स्टेट मशीन (state machine) के रूप में सोच सकते हैं जो एक निश्चित संख्या में एक फिक्स्ड स्टेट-ट्रांज़िशन (fixed state-transition) से गुजरती है (जहां इटरेशंस की संख्या प्रूविंग टाइम पर निर्धारित होती है और सर्किट में पहले से ही बेक (baked into) नहीं होती है)।

इन सीक्वेंसेस में प्रत्येक चरण पर केवल एक ही संभावित कंप्यूटेशन होता है (जैसे कि पिछली दो स्टेट्स को जोड़ना या पिछली स्टेट को किसी संख्या से गुणा करना)। हालाँकि, यदि हम प्रत्येक स्टेट पर कंडीशनल ब्रांचिंग (conditional branching) जोड़ते हैं, तो हमारे पास स्टेटफुल कंप्यूटेशन के लिए आवश्यक सभी कंपोनेंट्स होते हैं।

इस अध्याय में हम केवल वे उदाहरण दिखाएंगे जहां केवल एक ही संभावित स्टेट-चेंज (state-change) होता है और स्टेट-चेंजेस की संख्या वेरिएबल (variable) होती है। आने वाले अध्यायों में हम दिखाएंगे कि कैसे स्टेट ट्रांज़िशन (state transition) को ही कंडीशनल (conditional) बनाया जाए, यानी कई संभावित स्टेट ट्रांज़िशंस रखे जाएं।

Factorial का उदाहरण

अब हम दिखाते हैं कि एक सर्किट कैसे लिखा जाए जो यह साबित करे कि हमने सही ढंग से इसकी गणना की है:

जहाँ $!$ फैक्टोरियल है और $p$ डिफ़ॉल्ट फील्ड मॉड्यूलस (default field modulus) है।

Python जैसी किसी पारंपरिक प्रोग्रामिंग भाषा में फैक्टोरियल की गणना करने के लिए, कोड कुछ इस प्रकार होगा:

Copy
def factorial_mod_p(x, p):
  if x == 0:
    return 1
    
  acc = 1
  for i in range(1, x+1):
    acc = (acc * i) % p
  
  return acc

हालाँकि, यदि उपरोक्त कोड का सीधे Circom में अनुवाद किया जाता है, तो इसमें कुछ समस्याएँ होंगी:

• Circom if स्टेटमेंट्स का समर्थन नहीं करता है, इसलिए if x == 0: return 0 लाइन कंपाइल (compile) नहीं होगी।
• Circom अज्ञात संख्या में इटरेशंस (iterations) वाले लूप्स (loops) का समर्थन नहीं करता है। चूँकि x लूप की वैल्यू निर्धारित करता है, इसलिए यह भी कंपाइल नहीं होगा। Circom बैकग्राउंड (under the hood) में एक R1CS में कंपाइल होता है, और अंतर्निहित R1CS का एक निश्चित आकार होना चाहिए और यह इनपुट्स की वैल्यू के आधार पर आकार नहीं बदल सकता है।

कोड को R1CS जैसे अरिथमेटाइजेशन (arithmetization) रिप्रेजेंटेशन के अनुकूल बनाने के लिए, हमें शून्य से लेकर कुछ अपर बाउंड (upper bound) तक फैक्टोरियल की गणना करने की आवश्यकता है जिसका हम समर्थन करना चाहते हैं।

उदाहरण के लिए, यदि हम जानते हैं कि हमें कभी भी 99 फैक्टोरियल से अधिक की गणना करने की आवश्यकता नहीं होगी, तो हमें 0 से 99 (इन्क्लूसिव) तक के हर फैक्टोरियल की गणना करनी होगी। यदि हम 80 फैक्टोरियल के लिए एक प्रूफ (proof) बनाना चाहते हैं, तो भी हमें 0 से 99 तक के फैक्टोरियल्स की गणना करने की आवश्यकता है, लेकिन हम 80 का रिज़ल्ट प्राप्त करने के लिए Quin selector का उपयोग करते हैं।

यहाँ एक Python उदाहरण दिया गया है जिसमें कोई if-स्टेटमेंट नहीं है और एक फिक्स्ड-लेंथ लूप (fixed-length loop) है:

Copy
def factorial_mod_p(x, p):

  assert x < 100
  # allocate the array
  ans = [0] * 100
  ans[0] = 1 # 0! = 1
  
  for i in range(1, 100):
      ans[i] = (ans[i-1] * i) % p
  
  return ans[x]

एक तरह से, हम 100 की लंबाई (length) का एक ऐरे (array) बना रहे हैं और वैल्यूज़ को उस इंडेक्स के फैक्टोरियल के साथ पॉप्युलेट (populate) कर रहे हैं। फिर हम Quin Selector का उपयोग करके उस फैक्टोरियल को “सेलेक्ट (select)” करेंगे जो हमें चाहिए।

इसका Circom में अनुवाद बिल्कुल सीधा (straightforward) है:

Copy
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";

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

  // precompute factorials from 0 to n
  signal factorials[n+1];

  // compute the factorials
  factorials[0] <== 1;
  for (var i = 1; i <= n; i++) {
    factorials[i] <== factorials[i - 1] * i;
  }

  // ensure that in < n
  signal inLTn;
  inLTn <== LessThan(252)([in, n]);
  inLTn === 1;
  
  // select the factorial of interest
  component mux = Multiplexer(1, n);
  mux.sel <== in;

  // assign factorials into the multiplexer
  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== factorials[i];
  }

  out <== mux.out[0];
}

component main = factorial(100);

/*
  INPUT = { "in": "3" }
*/

एक असुरक्षित इम्प्लीमेंटेशन

Circom में नए आए कई इंजीनियर्स अक्सर एक ऐसे “सहज (intuitive)” समाधान का उपयोग करते हैं जो क्वाड्रैटिक कंस्ट्रेंट्स (quadratic constraints) के साथ किसी भी समस्या से बचाता है और निम्नलिखित जैसा कोड बनाता है:

Copy
pragma circom 2.1.8;

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

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

  signal factorials[n + 1];

  // compute the factorials
  var acc = 1;
  for (var i = 1; i < n; i++) {
    acc = acc * i;
  }
  
  out <-- acc;
}

component main = factorial(100);

यद्यपि out का उत्तर सही होगा, लेकिन <== या === ऑपरेटर्स की पूरी तरह से अनुपस्थिति का मतलब है कि सर्किट में कोई कंस्ट्रेंट्स (constraints) नहीं हैं।

उपरोक्त कोड में, प्रोग्रामर ने फैक्टोरियल की सही गणना करने के लिए कोड बनाया है, लेकिन इसे कंस्ट्रेंट (constrain) करने के लिए नहीं।

Fibonacci Modulo p का उदाहरण

फैक्टोरियल के उदाहरण में, हमें factorials की 0-वीं एंट्री को 1 के रूप में “हार्डकोड (hardcode)” करना पड़ा था, क्योंकि 0! = 1। फिबोनाची (Fibonacci) सीक्वेंस में, पहले दो नंबर 1 होते हैं, और उसके बाद का सब कुछ सीक्वेंस में पिछले दो नंबरों का योग होता है। इसलिए, Fibonacci कोड के लिए, हम पहली दो वैल्यूज़ को हार्डकोड करते हैं और फिर बाकी की गणना करते हैं।

नीचे दिया गया सर्किट n-वें नंबर modulo p तक Fibonacci सीक्वेंस की गणना करता है, फिर वांछित “in” Fibonacci नंबर आउटपुट करता है।

Copy

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

template Fibonacci(n) {
  assert(n >= 2); // so we don't break the hardcoding

  signal input in; // compute the kth Fibonacci number
  signal output out;

  // precompute Fibonacci sequence from
  // 0 to n
  signal fib[n + 1];

  // compute the factorials
  fib[0] <== 1;
  fib[1] <== 1;
  
  for (var i = 2; i < n; i++) {
    fib[i] <== fib[i - 1] + fib[i - 2];
  }

  // ensure that in < n
  signal inLTn;
  inLTn <== LessThan(252)([in, n]);
  inLTn === 1;

  // select the fibonacci number 
  // of interest
  component mux = Multiplexer(1, n);
  mux.sel <== in;

  // assign Fibonacci into
  // the Quin Selector
  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== fib[i];
  }

  out <== mux.out[0];
}

component main = Fibonacci(99);

/*
  INPUT = {"in": 5}
*/

हमेशा की तरह, Fibonacci सीक्वेंस के प्रत्येक अपडेट को स्पष्ट रूप से कंस्ट्रेंट (constrain) करना महत्वपूर्ण है, न कि केवल एक अनकंस्ट्रेंट लूप (unconstrained loop) में परिणाम की गणना करना।

अभ्यास (Exercise):

Circom Puzzles में pow exercise को पूरा करें।