Quin Selector एक डिज़ाइन पैटर्न है जो हमें सिग्नल्स के एक ऐरे के लिए एक सिग्नल को इंडेक्स के रूप में उपयोग करने की अनुमति देता है।

एक पूर्व-आवश्यकता के रूप में, हम यह मानकर चलते हैं कि पाठक ने Circom में कंडीशनल स्टेटमेंट्स (Conditional Statements) पर अध्याय पढ़ लिया है।

निम्नलिखित कोड कंपाइल नहीं होता है, लेकिन यह दर्शाता है कि हम क्या हासिल करने की कोशिश कर रहे हैं:

Copy
template ArraySelect(n) {

  signal input in[n];
  signal input index;
  
  signal output out;
  
  // won't compile -- non-quadratic constraints
  out <== in[index];
}

Circom में कुछ कंडीशनल व्यक्त करने के लिए, हम वांछित ब्रांच को एक से और अन्य को शून्य से गुणा करते हैं, और फिर सभी ब्रांचों का योग करते हैं। शून्य की गई ब्रांचों का योग पर कोई प्रभाव नहीं पड़ेगा। Quin Selector भी इसी लॉजिक का पालन करता है: हम वांछित इंडेक्स को 1 से और बाकी को शून्य से गुणा करते हैं, और फिर परिणाम का योग करते हैं।

उदाहरण के लिए, मान लें कि हमारा इनपुट ऐरे in = [5,9,14,20] है। इंडेक्स 2 पर आइटम को चुनने का मतलब है कि हम यह गणना करते हैं:

दूसरे शब्दों में, हम [5,9,14,20] और [0,0,1,0] के बीच एक इनर प्रोडक्ट (inner product) की गणना करते हैं, जिसका परिणाम 14 होता है।

यदि index वांछित इंडेक्स के बराबर है, तो प्रत्येक “स्विच” 0 या 1 हो जाता है।

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

template ArraySelect(n) {

  signal input in[n];
  signal input index;
  signal output out;
  
  component eqs[n];
  
  // prod keeps a running product
  signal prod[n];
  
  // prod = 1 * in[i] if i == index else 0
  for (var i = 0; i < n; i++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== index;
    
    prod[i] <== eqs[i].out * in[i];
  }
  
  // sum the result
  var sum;
  for (var i = 0; i < n; i++) {
    sum += prod[i];
  }
  
  out <== sum;
}

उपरोक्त कोड इंडेक्स को ऐरे के आकार से कम होने के लिए कंस्ट्रैन (constrain) नहीं करता है। यदि इंडेक्स सीमा से बाहर (out of bounds) है, तो कोड परिणाम के रूप में 0 रिटर्न करेगा। DarkForest में Quin Selector इम्प्लीमेंटेशन में index पर एक रेंज चेक शामिल है, इसलिए हम पाठक को उस टेम्पलेट को देखने का सुझाव देते हैं, जिस पर उपरोक्त उदाहरण आधारित थे:

Copy
// out is the sum of in
template CalculateTotal(n) {
  signal input in[n];
  signal output out;

  signal sums[n];

  sums[0] <== in[0];

  for (var i = 1; i < n; i++) {
      sums[i] <== sums[i-1] + in[i];
  }

  out <== sums[n-1];
}

template QuinSelector(choices) {
  signal input in[choices];
  signal input idx;
  signal output out;
  
  // Ensure that idx < choices
  component lessThan = LessThan(252);
  lessThan.in[0] <== idx;
  lessThan.in[1] <== choices;
  lessThan.out === 1;

  component calcTotal = CalculateTotal(choices);
  component eqs[choices];

  // For each item, check whether its index equals the input idx.
  for (var i = 0; i < choices; i ++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== idx;

    // eqs[i].out is 1 if the idx matches. As such, at most one input to
    // calcTotal is not 0.
    calcTotal.in[i] <== eqs[i].out * in[i];
  }

  // Returns 0 + 0 + 0 + item
  out <== calcTotal.out;
}

एक ऑप्टिमाइज़ेशन के रूप में, component lessThan = LessThan(252); स्टेप को यह सुनिश्चित करने के लिए 252 बिट्स की आवश्यकता नहीं है कि idx, choices से कम है। हमारे एप्लिकेशन के आधार पर, हम तुलना करने के लिए बहुत कम संख्या में बिट्स का उपयोग कर सकते हैं और अंदरूनी तौर (under the hood) पर उत्पन्न होने वाले कंस्ट्रैंट्स की संख्या को बचा सकते हैं।

Quin Selector का Circomlib इम्प्लीमेंटेशन

Circomlib लाइब्रेरी में मल्टीप्लेक्सर (multiplexer) वही काम पूरा करता है जो Quin Selector करता है। हालाँकि, यह एक 2-डायमेंशनल ऐरे को इंडेक्स करता है और एक 1-डायमेंशनल ऐरे रिटर्न करता है। उदाहरण के लिए, यदि ऐरे in = [[5,5],[6,6],[7,7]] और idx = 1 दिया गया है, तो यह [6, 6] रिटर्न करेगा।

इस कंपोनेंट के निम्नलिखित इनपुट्स और आउटपुट्स हैं:

Copy
template Multiplexer(wIn, nIn) {
  signal input inp[nIn][wIn];
  signal input sel;
  signal output out[wIn];

  // ...
}

in = [[5,5],[6,6],[7,7]] उदाहरण का उपयोग करते हुए, wIn 2 होगा और nIn 3 होगा। sel सिग्नल वह इंडेक्स है जिसे चुनना है; उदाहरण के लिए यदि sel = 1 है तो out = [6,6] होगा।

ऐरे पर लूप चलाने और यह जाँचने के बजाय कि क्या इंडेक्स sel वैल्यू के IsEqual है, Multiplexer सभी शून्यों का एक “मास्क (mask)” उत्पन्न करता है जिसमें वांछित इंडेक्स पर 1 होता है और उस मास्क को इनपुट के साथ गुणा करता है। उदाहरण के लिए, यदि sel = 1 है तो यह [0,1,0] मास्क उत्पन्न करता है और इनपुट को उस मास्क से गुणा करता है।

यहाँ Circomlib के मल्टीप्लेक्सर का उपयोग करने का एक उदाहरण दिया गया है:

Copy
include "circomlib/multiplexer.circom";

template MultiplexerExample(n) {
  signal input in[n];
  signal input k;
  signal output out;

  component mux = Multiplexer(1, n);

  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== in[i];
  }
  mux.sel <== k;

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

component main = MultiplexerExample(4);

/* INPUT = {
  "in": [3, 7, 9, 11],
  "k": "1"
} */

ऐतिहासिक नोट (Historical Note)

इस एल्गोरिदम को xjsnark पेपर में “Linear Scan” के रूप में संदर्भित किया गया था, जो कि eth Dark Forest इम्प्लीमेंटेशन से भी पुराना है। इसे बताने के लिए 0xerhant को धन्यवाद।