अधिकांश काम की computations आमतौर पर “stateful” होती हैं — यानी, उन्हें अंतिम परिणाम देने के लिए चरणों (steps) की एक श्रृंखला से गुजरना पड़ता है।

कभी-कभी, हमें यह दिखाने की आवश्यकता नहीं होती है कि हमने computation को execute किया है, बल्कि केवल परिणाम दिखाना होता है। उदाहरण के लिए, यदि A एक लिस्ट है, तो हम यह सिद्ध कर सकते हैं कि B, लिस्ट A का sorted वर्ज़न है, यह दिखाकर कि B, A का एक permutation है, और B के सभी elements क्रम (order) में हैं। यह दिखाने की कोई आवश्यकता नहीं है कि हमने sorting algorithm के प्रत्येक चरण को सही ढंग से execute किया है। हम पहले ही दिखा चुके हैं कि किसी लिस्ट के elements के क्रम में होने को कैसे सिद्ध किया जाए, लेकिन कुशलतापूर्वक यह सिद्ध करना कि एक लिस्ट दूसरी की permutation है, आश्चर्यजनक रूप से कठिन (tricky) है, इसलिए हम उस तकनीक को बाद में पेश करेंगे।

सामान्य तौर पर, कई वास्तविक computations ऐसी होती हैं जो केवल यह सिद्ध करने की अनुमति नहीं देती हैं कि परिणाम सही है। विशेष रूप से, यह सिद्ध करने के लिए कि हमने sha256("RareSkills") को सही ढंग से execute किया है, वास्तव में hash function के हर चरण को सही ढंग से execute करने की आवश्यकता होती है।

चूंकि hash functions थोड़े जटिल होते हैं, इसलिए हम यह दिखाकर stateful computation का कांसेप्ट पेश करते हैं कि किसी लिस्ट पर Selection Sort को सही ढंग से निष्पादित (carry out) करने को कैसे सिद्ध किया जाए। जैसा कि ऊपर बताया गया है, यह दृष्टिकोण “overkill” (अनावश्यक रूप से जटिल) है क्योंकि यह सिद्ध करना अधिक सरल है कि आउटपुट लिस्ट इनपुट का एक sorted permutation है — इससे कोई फर्क नहीं पड़ता कि हमने लिस्ट को सॉर्ट करने के लिए किस algorithm का उपयोग किया है।

हालाँकि, हम फिर भी Selection Sort algorithm दिखाते हैं क्योंकि हम इसे stateful computation के लिए एक आसान शुरुआत (gentle introduction) मानते हैं।

Selection Sort इस तरह काम करता है:

• लिस्ट के माध्यम से iterate करके
• प्रत्येक इंडेक्स i पर, i पर मौजूद वैल्यू की तुलना उस सबलिस्ट (sublist) से करके जिसमें i और उसके आगे के सभी आइटम (i..n-1 inclusive) शामिल हैं
• i पर मौजूद आइटम को सबलिस्ट i..n-1 के न्यूनतम (minimum) आइटम के साथ swap करके

Selection Sort को नीचे दिए गए एनीमेशन में दर्शाया गया है:

चूंकि ZK circuits में signals अपरिवर्तनीय (immutable) होते हैं, इसलिए हर बार जब हम swap करते हैं, तो हमें एक नई लिस्ट बनानी होती है। उदाहरण के लिए, यदि हमने [5,2,3,4] को सॉर्ट किया, तो state transitions का क्रम यह होगा:

1. i = 0, [5,2,3,4] —> swap —> [2,5,3,4]
2. i = 1, [2,5,3,4] —> swap —> [2,3,5,4]
3. i = 2, [2,3,5,4] —> swap —> [2,3,4,5]

यह सिद्ध करने के लिए कि हमने Selection Sort को ठीक से execute किया है, हमें यह सिद्ध करना होगा कि इटरेशन i पर, हमने i पर मौजूद आइटम को सबलिस्ट i…n - 1 के न्यूनतम आइटम के साथ swap किया है। हमने पिछले अध्यायों में इसके लिए अधिकांश आवश्यक components पहले ही बना लिए हैं:

• हम यह सिद्ध कर सकते हैं कि एक निश्चित आइटम किसी लिस्ट का न्यूनतम (minimum) है, और यह एक निश्चित इंडेक्स पर है।
• हम यह सिद्ध कर सकते हैं कि हमने एक लिस्ट में दो आइटम्स को swap किया है।

इस अध्याय में, हम बस इन components को एक साथ जोड़ते हैं। शुरू करने के लिए, हम एक टेम्पलेट (template) बनाते हैं जो यह सिद्ध करता है कि हमने एक सबलिस्ट में न्यूनतम वैल्यू के इंडेक्स को सही ढंग से पहचाना है:

Copy
template GetMinAtIdx(n) {
  signal input in[n];
  
  // compute and constrain min and idx
  // to be the min value in the list
  // and the index of the minimum value
  signal output min;
  signal output idx;

  // compute the minimum and its index
  // outside of the constraints
  var minv = in[0];
  var idxv = 0;
  for (var i = 1; i < n; i++) {
    if (in[i] < minv) {
      minv = in[i];
      idxv = i;
    }
  }
  min <-- minv;
  idx <-- idxv;

  // constrain that min is ≤ all others
  component lte[n];
  for (var i = 0 ; i < n; i++) {
    lte[i] = LessEqThan(252);
    lte[i].in[0] <== min;
    lte[i].in[1] <== in[i];
    lte[i].out === 1;
  }
  
  // assert min is really at in[idx]
  component qs = QuinSelector(n);
  qs.index <== idx;
  for (var i = 0; i < n; i++) {
    qs.in[i] <== in[i];
  }
  qs.out === min;
}

Sorting algorithm का एक इटरेशन

Selection Sort का पहला चरण इंडेक्स 0 पर मौजूद आइटम को पूरी लिस्ट के न्यूनतम आइटम (जो इंडेक्स 0 पर मौजूद आइटम भी हो सकता है) के साथ swap करना है। नीचे किसी विशेष इंडेक्स पर मौजूद संख्या को उसके आगे के न्यूनतम आइटम के साथ swap करने का कोड दिया गया है।

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.index <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.index <== 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++) {
    dxEqS[i] = IsEqual();
    dxEqS[i].in[0] <== i;
    dxEqS[i].in[1] <== s;

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

    / if IdxEqS[i].out + IdxEqT[i].out
    / equals 0, then it is not i ≠ s and i ≠ t
    dxNorST[i] = IsZero();
    dxNorST[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]
    ranchS[i] <== IdxEqS[i].out * qst.out;
    ranchT[i] <== IdxEqT[i].out * qss.out;
    ranchNorST[i] <== IdxNorST[i].out * in[i];
    
    / multiply branchS by zero if s equals t
    ut[i] <==  (1-sEqT) * (branchS[i]) + branchT[i] + branchNorST[i];
  }
}

template Select(n, start) {
  // unsorted list
  signal input in[n];
  
  // index start swapped with the min
  signal output out[n];

  // we will define GetMinAtIdxStartingAt in the next codeblock
  component minIdx0 = GetMinAtIdxStartingAt(n, start);
  for (var i = 0; i < n; i++) {
      minIdx0.in[i] <== in[i];
  }

  component Swap0 = Swap(n);
  Swap0.s <== start; // swap 0 with the min
  Swap0.t <== minIdx0.idx; // with the min (could be idx 0)
  for (var i = 0; i < n; i++) {
      Swap0.in[i] <== in[i];
  }

  // copy to out
  for (var i = 0; i < n; i++) {
      out[i] <== Swap0.out[i];
  }
}

बेशक, हमें इसे parameterize करना चाहिए क्योंकि हम इंडेक्स 0…n - 2 के लिए इस प्रक्रिया को दोहराने जा रहे हैं। ऐसा करने के लिए, हम GetMinAtIdx को संशोधित (modify) करेंगे ताकि यह केवल एक start इंडेक्स के बाद की वैल्यूज़ पर विचार करे:

Copy
// formerly GetMinAtIdx
template GetMinAtIdxStartingAt(n, start) {
  signal input in[n];
  signal output min;
  signal output idx;

  // only look for values start and later
  var minv = in[start];
  var idxv = start;
  for (var i = start + 1; i < n; i++) {
    if (in[i] < minv) {
      minv = in[i];
      idxv = i;
    }
  }
  min <-- minv;
  idx <-- idxv;

  // only compare to values start and later
  component lt[n];
  
  // CHANGES HERE: LOOP FROM START TO N-1
  for (var i = start ; i < n; i++) {
    lt[i] = LessEqThan(252);
    lt[i].in[0] <== min;
    lt[i].in[1] <== in[i];
    lt[i].out === 1;
  }

  // Quin Selector -- ensure that
  // assert min is really at in[idx]
  component qs = QuinSelector(n);
  qs.index <== idx;
  for (var i = 0; i < n; i++) {
    qs.in[i] <== in[i];
  }
  qs.out === min;
}

Final Algorithm

यह सिद्ध करने के लिए कि हमने Selection Sort को ठीक से निष्पादित (carry out) किया है, हम बस ऊपर दिए गए टेम्पलेट को n - 2 बार दोहराते हैं।

Copy
include "circomlib/comparators.circom";

// ----QUIN SELECTOR ----
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];
}

// from https://github.com/darkforest-eth/circuits/blob/master/perlin/QuinSelector.circom
template QuinSelector(choices) {
  signal input in[choices];
  signal input index;
  signal output out;
  
  // Ensure that index < choices
  component lessThan = LessThan(4);
  lessThan.in[0] <== index;
  lessThan.in[1] <== choices;
  lessThan.out === 1;

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

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

    // eqs[i].out is 1 if the index 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;
}

// Given array in[n]
// swap the items at index
// s and t
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.index <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.index <== 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];
  }
}

// Find the smallest element starting
// at index start
template GetMinAtIdxStartingAt(n, start) {
  signal input in[n];
  signal output min;
  signal output idx;

  // only look for values start and later
  var minv = in[start];
  var idxv = start;
  for (var i = start + 1; i < n; i++) {
    if (in[i] < minv) {
      minv = in[i];
      idxv = i;
    }
  }
  min <-- minv;
  idx <-- idxv;

  // only compare to values start and later
  component lt[n];
  
  // CHANGES HERE: LOOP FROM START TO N-1
  for (var i = start ; i < n; i++) {
    lt[i] = LessEqThan(252);
    lt[i].in[0] <== min;
    lt[i].in[1] <== in[i];
    lt[i].out === 1;
  }

  // Quin Selector -- ensure that
  // assert min is really at in[idx]
  component qs = QuinSelector(n);
  qs.index <== idx;
  for (var i = 0; i < n; i++) {
    qs.in[i] <== in[i];
  }
  qs.out === min;
}

// Given an array in, swap
// start with the smallest element
// in front of it
template Select(n, start) {
  // unsorted list
  signal input in[n];
  
  // index 0 swapped with the min
  signal output out[n];

  component minIdx0 = GetMinAtIdxStartingAt(n, start);
  for (var i = 0; i < n; i++) {
    minIdx0.in[i] <== in[i];
  }

  component Swap0 = Swap(n);
  Swap0.s <== start; // swap 0 with the min
  Swap0.t <== minIdx0.idx; // with the min (could be idx 0)
  for (var i = 0; i < n; i++) {
    Swap0.in[i] <== in[i];
  }

  // copy to out
  for (var i = 0; i < n; i++) {
    out[i] <== Swap0.out[i];
  }
}

// ---- CORE ALGORITHM ----
template SelectionSort(n) {
  assert(n > 0);

  signal input in[n];
  signal output out[n];

  signal intermediateStates[n][n];

  component SSort[n - 1];
  for (var i = 0; i < n; i++) {
    // copy the input to the first row of
    // intermediateStates. Note that we can do
    // if(i == 0) because i is not a signal
    // and i is known at compile time
    if (i == 0) {
      for (var j = 0; j < n; j++) {
        intermediateStates[0][j] <== in[j];
      }
    }

    else {
      // select sort n items starting at i - 1
      // for i = 1, we compare item at 0 to
      // the rest of the list
      SSort[i - 1] = Select(n, i - 1);
      
      // load in the intermediate state i -1
      for (var j = 0; j < n; j++) {
        SSort[i - 1].in[j] <== intermediateStates[i - 1][j];
      }
      // write the sorted result to row i
      for (var j = 0; j < n; j++) {
        SSort[i - 1].out[j] ==> intermediateStates[i][j];
      }
    }
  }

  // write the final state to the ouput
  for (var i = 0; i < n; i++) {
    intermediateStates[n-1][i] ==> out[i];
  }
}

component main = SelectionSort(9);

/* INPUT = {"in": [3,1,8,2,4,0,1,2,4]} */

निष्कर्ष

“Intermediate state” (मध्यवर्ती अवस्था) का कांसेप्ट और यह सिद्ध करना कि हम intermediate states के बीच सही ढंग से आगे बढ़े हैं, व्यवहार में सिद्ध किए गए अधिकांश ZK algorithms, विशेष रूप से hash functions और ZK Virtual Machines के verification का मूल (core) है। इस अध्याय में प्रस्तुत किया गया Selection Sort algorithm, stateful computation के लिए एक आसान शुरुआत (gentle introduction) प्रदान करता है।