यह अध्याय दिखाता है कि signals की एक list में दो signals को कैसे swap किया जाए। यह एक sorting algorithm के लिए एक महत्वपूर्ण subroutine है। अधिक सामान्य रूप से, lists अधिक रोचक functions जैसे कि hash functions या CPU में memory की modeling के लिए एक मूलभूत building block हैं, इसलिए हमें यह सीखना चाहिए कि उनके values को कैसे update किया जाए।

किसी list में दो items को swap करना उन पहली चीज़ों में से एक है जो programmers सीखते हैं, एक सामान्य solution कुछ इस तरह दिखता है:

Copy
# s and t are indexes of array arr
def swap(arr, s, t):
  temp = arr[s];
  arr[s] = arr[t];
  arr[t] = temp;
  return arr

हालाँकि, एक ZK circuit में, यह operation आश्चर्यजनक रूप से tricky हो सकता है।

• पहला, हम signals के एक array को सीधे index नहीं कर सकते हैं। इसके लिए, हमें एक Quin selector का उपयोग करने की आवश्यकता है।
• दूसरा, हम signals के एक array में किसी signal पर “write” नहीं कर सकते क्योंकि signals immutable होते हैं।

इसके बजाय, हमें एक नया array बनाना होगा और पुरानी values को नए array में copy करना होगा, जो निम्नलिखित conditions के अधीन होगा:

• यदि हम index s पर हैं, तो arr[t] की value लिखें
• यदि हम index t पर हैं, तो arr[s] की value लिखें
• अन्यथा, original value लिखें

नए array में हम जो भी write करते हैं, वह एक conditional operation होता है।

Quin selector को पिछले अध्याय में समझाया गया था — space बचाने के लिए हम उस code को यहाँ दोहराएंगे नहीं।

Circom में Swap

नीचे दिया गया component index s के item को index t के item के साथ swap करेगा और एक नया array return करेगा। (निम्नलिखित code में एक bug है, इसे खोजने का प्रयास करें! उत्तर बाद में दिया गया है।)

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];
  
  // we do not check that
  // s < n or t < n
  // because the Quin selector
  // does that

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }
  
  // qss.out holds in[s]
  // qst.out holds in[t]

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s,
    // write in[t]
    // if we are at index t,
    // write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    out[i] <==  branchS[i] + branchT[i] + branchNorST[i];
  }
}

ध्यान दें कि अंतिम conditional statement

Copy
branchS[i] <== IdxEqS[i].out * qst.out;
branchT[i] <== IdxEqT[i].out * qss.out;
branchNorST[i] <== IdxNorST[i].out * in[i];
out[i] <==  branchS[i] + branchT[i] + branchNorST[i];

को इस प्रकार नहीं लिखा जा सकता है

Copy
out[i] <==  IdxEqS[i].out * qst.out + IdxEqT[i].out * qss.out + IdxNorST[i].out * in[i]

क्योंकि यह एक non-quadratic constraints error उत्पन्न करेगा (constraint में एक से अधिक multiplication हैं)।

Bug को पकड़ें

ऊपर दिए गए code में एक bug है — क्या आप नीचे scroll करने से पहले इसे पकड़ सकते हैं?

Code में Bug

ऊपर दिए गए code के साथ समस्या यह है कि यह इस तथ्य को ध्यान में नहीं रखता है कि s की value t की value के बराबर हो सकती है (s == t)। उस परिस्थिति में, index पर लिखी गई value उस index की value होगी जिसे स्वयं में जोड़ा गया है।

समस्या को Fix करना

इसे रोकने के लिए, हमें explicitly यह detect करने की आवश्यकता है कि क्या s == t है और value को दोगुना होने से बचाने के लिए branchS या branchT में से किसी एक को zero से multiply करना होगा। दूसरे शब्दों में, यदि s और t दोनों के switches active हैं, तो परिणामी value s + t होगी। लेकिन हम ऐसा नहीं चाहते हैं, हम चाहते हैं कि value प्रभावी रूप से branchS या branchT को arbitrarily चुनकर अपरिवर्तित रहे (उनके पास समान value होगी):

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];

  // NEW CODE to detect if s == t
  signal sEqT;
  sEqT <== IsEqual()([s, t]);

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s, write in[t]
    // if we are at index t, write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    
    // multiply branchS by zero if s equals T
    out[i] <==  (1-sEqT) * (branchS[i]) + branchT[i] + branchNorST[i];
  }
}

निष्कर्ष

Circom में किसी भी array manipulation के लिए एक नया array बनाने और पुरानी values को नए में copy करने की आवश्यकता होती है, सिवाय उस जगह के जहाँ update होता है।

एक loop में इस pattern का उपयोग करके, हम किसी list को sort करने, stacks और queues जैसे data structures को model करने, और यहाँ तक कि किसी CPU या VM की state को बदलने जैसे काम कर सकते हैं। हम अगले अध्यायों में इनके उदाहरण देखेंगे।