पर्म्यूटेशन आर्ग्युमेंट एक ऐसा प्रमाण (proof) है जो यह दर्शाता है कि दो सूचियों (lists) में समान तत्व (elements) हैं, लेकिन संभवतः उनका क्रम (order) अलग हो सकता है। उदाहरण के लिए, [2,3,1], [1,2,3] का एक पर्म्यूटेशन है और इसके विपरीत भी।

पर्म्यूटेशन आर्ग्युमेंट यह साबित करने के लिए उपयोगी है कि एक सूची दूसरी सूची का सॉर्टेड (sorted) संस्करण है। यानी, यदि सूची B में सूची A के ही तत्व हैं और B के तत्व सॉर्ट किए गए हैं, तो हम जानते हैं कि प्रूवर (prover) ने A को सही ढंग से सॉर्ट किया है।

यह निर्धारित करने के लिए कि क्या दो सूचियां समान हैं, हम आमतौर पर उन्हें सॉर्ट करते हैं और तत्व-दर-तत्व (element-wise) उनकी तुलना करते हैं।

हालाँकि, यह जानने के लिए कि एक सूची सॉर्ट की गई है, हमें यह जांचना होगा कि 1) तत्व क्रम में हैं और 2) सॉर्टिंग एल्गोरिदम के आउटपुट में इनपुट के समान ही तत्व मौजूद हैं।

यह एक सर्कुलर डिपेंडेंसी (circular dependency) बनाता है – यह जानने के लिए कि एक सूची दूसरी की पर्म्यूटेशन है, हमें यह जानना होगा कि उनके सॉर्ट किए गए संस्करण समान हैं। लेकिन यह जानने के लिए कि सॉर्टिंग एल्गोरिदम ठीक से निष्पादित (executed) हुए थे, हमें यह जानना होगा कि सॉर्ट का आउटपुट इनपुट का एक पर्म्यूटेशन है।

यह नियमित कोड में कोई समस्या नहीं है, लेकिन ZK में हमें गणना (computation) के हर चरण को कंस्ट्रेन (constrain) करना होता है।

हम पहले ही दिखा चुके हैं कि किसी सूची को सॉर्ट किया हुआ कैसे साबित किया जाए। यह अध्याय यह साबित करने पर केंद्रित है कि दो सूचियां एक-दूसरे की पर्म्यूटेशन हैं।

विकल्प 1: सॉर्टिंग एल्गोरिदम के लिए कंस्ट्रेंट्स (constraints) लिखना

पिछले अध्याय में, हमने दिखाया था कि Selection Sort एल्गोरिदम के लिए कंस्ट्रेंट्स कैसे लिखें। Selection Sort एल्गोरिदम $\mathcal{O}(n^2)$ समय में चलता है, इसलिए इसमें $\mathcal{O}(n^2)$ कंस्ट्रेंट्स होंगे। हम इसी काम को $\mathcal{O}(n \log n)$ कंस्ट्रेंट्स में पूरा करने के लिए merge sort जैसे अधिक कुशल एल्गोरिदम का उपयोग कर सकते हैं, लेकिन इससे बेहतर समाधान मौजूद हैं जैसा कि हम जल्द ही देखेंगे।

विकल्प 2: सीधे 1-टू-1 मैपिंग को कंस्ट्रेन करने का प्रयास

कोई सीधे एक ऐसा सर्किट लिखने का प्रयास कर सकता है जो केवल और केवल तभी संतुष्ट (satisfied) होता है जब एक सूची दूसरी की पर्म्यूटेशन हो। दूसरे शब्दों में, एक सूची के प्रत्येक तत्व का दूसरी सूची में एक मैचिंग तत्व होता है और इसके विपरीत भी।

उदाहरण के लिए, यह साबित करने के लिए कि [a1, a2, a3], [b1, b2, b3] का एक पर्म्यूटेशन है, हमें दोनों के बीच एक मैपिंग दिखानी होगी, यह साबित करना पर्याप्त है कि प्रत्येक a_i, b सूची के किसी तत्व से मैप होता है और प्रत्येक b_i, a सूची के किसी तत्व से मैप होता है।

दोहरी मैपिंग (dual mapping) को साबित करने के लिए एक सर्किट बनाने हेतु, हम s सिग्नल्स का एक मैट्रिक्स बनाते हैं जिसे इस प्रकार परिभाषित किया गया है:

Copy

               b1             b2             b3
    --------------------------------------------
a1 | s11 = (a1-b1)  s12 = (a1-b2)  s12 = (a1-b3)
a2 | s21 = (a2-b1)  s22 = (a2-b2)  s23 = (a2-b3)
a3 | s31 = (a3-b1)  s32 = (a3-b2)  s33 = (a3-b3)

ध्यान दें कि यदि एक s सिग्नल 0 है, तो संबंधित a तत्व और b तत्व समान हैं। उदाहरण के लिए, यदि a3 == b1 है, तो s31, 0 होगा।

यदि हम फिर s सिग्नल्स को पंक्ति-वार (row-wise) और स्तंभ-वार (column-wise) गुणा करते हैं और उनके गुणनफल (products) को नीचे दिखाए गए अनुसार o सिग्नल्स होने के लिए कंस्ट्रेन करते हैं, तो कम से कम एक मैचिंग तत्व होने पर o सिग्नल्स शून्य होंगे।

Copy
     b1      b2      b3
a1  s11  ×  s12  ×  s13   =  o_row1
     ×       ×       ×
a2  s21  ×  s22  ×  s23   =  o_row2
     ×       ×       ×
a3  s31  ×  s32  ×  s33   =  o_row3
    ||      ||       ||
    o_col1  o_col2   o_col3

यदि हम प्रत्येक o सिग्नल को शून्य होने के लिए कंस्ट्रेन करते हैं, तो यह यह भी कंस्ट्रेन करता है कि a के प्रत्येक तत्व का b में कम से कम एक मैचिंग तत्व है और इसके विपरीत भी। आउटपुट सिग्नल्स की व्याख्या पर विचार करें:

• o_row1 शून्य है यदि और केवल यदि a1, b के किसी तत्व से मेल खाता है।
• o_row2 शून्य है यदि और केवल यदि a2, b के किसी तत्व से मेल खाता है।
• o_row3 शून्य है यदि और केवल यदि a3, b के किसी तत्व से मेल खाता है।
• o_col1 शून्य है यदि और केवल यदि b1, a के किसी तत्व से मेल खाता है।
• o_col2 शून्य है यदि और केवल यदि b2, a के किसी तत्व से मेल खाता है।
• o_col3 शून्य है यदि और केवल यदि b3, a के किसी तत्व से मेल खाता है।

इसलिए, यदि सभी o सिग्नल्स शून्य हैं, तो प्रत्येक सूची के प्रत्येक तत्व का दूसरी सूची में एक मैचिंग तत्व होता है।

इस दृष्टिकोण की कमी यह है कि सूची की लंबाई के साथ कंस्ट्रेंट्स की संख्या क्वाड्रैटिकली (quadratically) बढ़ती है।

इसके बजाय, हम एक सूची को दूसरी की पर्म्यूटेशन साबित करने की एक ऐसी विधि दिखाते हैं जो सूची की लंबाई के लीनियर (linear) समय में काम करती है।

क्रेडिट: इस लेख का शेष भाग काफी हद तक Triton VM के इस documentation of the Triton VM पर आधारित है, हम केवल एक Circom कार्यान्वयन (implementation) दिखाते हैं और कुछ अधिक शुरुआती-अनुकूल स्पष्टीकरण जोड़ते हैं।

पर्म्यूटेशन आर्ग्युमेंट कैसे काम करता है

इस रूप में लिखे गए एक पॉलीनोमियल (polynomial) पर विचार करें:

यदि गुणन (multiplication) का क्रम बदल जाता है तो इसका मान नहीं बदलता है:

दूसरे शब्दों में, पॉलीनोमियल के linear factors के गुणन को पर्म्यूट करने से पॉलीनोमियल का मान नहीं बदलता है। (एक लीनियर फैक्टर $(x - a)$ के रूप का एक पद होता है)।

हम यह जांचने के लिए कि क्या पॉलीनोमियल्स समतुल्य (equivalent) हैं, पदों को बीजगणितीय (algebraically) रूप से गुणा नहीं करते हैं। इसके बजाय, हम एक अधिक कुशल पॉलीनोमियल समानता परीक्षण का उपयोग कर सकते हैं जिसे Schwartz-Zippel lemma कहा जाता है।

यह परीक्षण $x$ के लिए एक रैंडम बिंदु (random point) का नमूना लेता है और इसे दोनों पॉलीनोमियल्स में रखता है। यदि उनका मूल्यांकन (evaluation) समान है, तो अत्यंत उच्च प्रायिकता (extremely high probability) के साथ, वे समान पॉलीनोमियल हैं (यह परीक्षण सुरक्षित क्यों है, यह समझने के लिए कृपया ऊपर लिंक किया गया लेख देखें)।

इस तकनीक का उपयोग यह साबित करने के लिए किया जा सकता है कि एरे (arrays) $[a,b,c]$ और $[b,c,a]$ एक-दूसरे के पर्म्यूटेशन हैं। हम एक सर्किट बनाते हैं जो दो एरे $c_1,c_2,c_3,...,c_n$ और $d_1,d_2,d_3,...,d_n$ को इनपुट के रूप में लेता है और फिर पॉलीनोमियल्स का निर्माण करता है:

अंत में, यह $x$ के लिए एक रैंडम बिंदु चुनता है, दोनों पॉलीनोमियल्स का मूल्यांकन करता है, और उनके गुणनफलों को समान होने के लिए कंस्ट्रेन करता है।

रैंडम बिंदु उत्पन्न करने के लिए, मान लीजिए हम इसे $r$ कहते हैं, हम इनपुट के हैश (hash) का उपयोग करते हैं, अर्थात, एरे के कॉनकेटिनेशन (concatenation) को हैश करते हैं:

इस तरह, प्रूवर (prover) $r$ के लिए ऐसा मान चुनकर “धोखा” देने की कोशिश नहीं कर सकता जहां पॉलीनोमियल्स एक-दूसरे को काटते (intersect) हों। एक बार जब प्रूवर पॉलीनोमियल्स प्रदान कर देता है, तो वे उस $r$ मान को नियंत्रित नहीं कर सकते जिस पर इन पॉलीनोमियल्स का मूल्यांकन किया जाता है।

यदि प्रूवर पॉलीनोमियल्स को बदलता है, तो वह $r$ मान भी बदल जाएगा जिस पर उनका परीक्षण किया जाता है।

नीचे दिया गया सर्किट दो सूचियों को लेता है और जांचता है कि क्या वे एक-दूसरे के पर्म्यूटेशन हैं। एरे सिग्नल prodA में निम्नलिखित पद होते हैं:

• $\texttt{prodA[0] = } r - a_0$
• $\texttt{prodA[1] = prodA[0]} \cdot(r - a_1)$
• $\texttt{prodA[2] = prodA[1]} \cdot(r - a_2)$
• $\texttt{prodA[n - 1] = prodA[n - 2]}\cdot(r -a_{n-1})$

इस प्रकार, अंतिम प्रविष्टि (entry) prodA[n - 1], r पर पॉलीनोमियल का मूल्यांकन रखती है। यहाँ, r, hash.out है, जो एरे a और b की सभी प्रविष्टियों का Poseidon हैश है।

Copy

include "circomlib/poseidon.circom";

template IsPermutation(n) {
  signal input a[n];
  signal input b[n];

  // the random point will be the hash
  // of the concatenation of the arrays
  component hash = Poseidon(2 * n);
  for (var i = 0; i < n; i++) {
    hash.inputs[i] <== a[i];
    hash.inputs[i + n] <== b[i];
  }

  signal prodA[n];
  signal prodB[n];

  prodA[0] <== hash.out - a[0];
  prodB[0] <== hash.out - b[0];

  for (var i = 1; i < n; i++) {
    prodA[i] <== (hash.out - a[i]) * prodA[i - 1];
    prodB[i] <== (hash.out - b[i]) * prodB[i - 1];
  }

  // the evaluation of the polynomials at r = hash.out
  prodA[n - 1] === prodB[n - 1];
}

component main = IsPermutation(3);

/* INPUT = {
  "a": [1,2,3,4,5,6],
  "b": [1,2,3,4,6,5]
}
*/

भेद्यता (Vulnerability): सभी तत्वों को हैश न करना

इस तरीके से रैंडम बिंदु उत्पन्न करते समय, हैश को गणना (computation) के सभी इनपुट्स पर निर्भर होना चाहिए। अन्यथा, एक दुर्भावनापूर्ण (malicious) प्रूवर हैश मान को स्थिर रख सकता है, और आउटपुट एरे के मानों में तब तक बदलाव कर सकता है जब तक कि उन्हें पॉलीनोमियल का एक प्रतिच्छेदन बिंदु (intersection point) नहीं मिल जाता।

सुरक्षा के बारे में एक नोट

यह एल्गोरिदम इस बात पर निर्भर करता है कि असमान पॉलीनोमियल्स अधिक से अधिक $d$ बिंदुओं पर ही एक-दूसरे को काटते हैं जहां $d$ दोनों पॉलीनोमियल्स की अधिकतम डिग्री (maximum degree) है। यदि परिमित क्षेत्र (finite field) का आकार $d$ से बहुत बड़ा है, तो हम मान सकते हैं कि व्यवहार में, $p(r)\neq q(r)$ होगा यदि $p$ और $q$ असमान पॉलीनोमियल्स हैं और $r$ एक रैंडम बिंदु है। Circom एक परिमित क्षेत्र के आकार का उपयोग करता है जो $2^{253}$ से थोड़ा बड़ा है। यदि पॉलीनोमियल्स की डिग्री एक मिलियन है, तो इस बात की प्रायिकता कि $r$ एक प्रतिच्छेदन बिंदु है, लगभग $2^{20}/2^{253}$ या $1/2^{233}$ या $10^{70}$ में से $1$ है। यह परिमाण (magnitude) लगभग ब्रह्मांड में मौजूद परमाणुओं की संख्या के समान स्तर पर है।

हालाँकि, यदि हम बहुत छोटे परिमित क्षेत्र का उपयोग करते हैं, मान लीजिए 31 बिट्स के क्रम का, तो एक रैंडम $r$ के लिए $p(r)=q(r), q \ne p$ होने की प्रायिकता नगण्य (negligible) नहीं होगी।