यदि हम यह कहना चाहते हैं कि “x 5 या 6 के बराबर हो सकता है” तो हम आसानी से निम्नलिखित constraint का उपयोग कर सकते हैं:
(x - 6) * (x - 5) === 0
हालाँकि, मान लीजिए कि हम यह कहना चाहते हैं कि “x 5 से कम है या x 17 से बड़ा है।” इस मामले में, हम दोनों स्थितियों को सीधे नहीं मिला सकते हैं, क्योंकि यदि x 5 से कम है, तो यह उस constraint का उल्लंघन करेगा कि x 17 से बड़ा है और इसके विपरीत (vice versa)।
इसका समाधान विभिन्न स्थितियों (उदा., x का 5 से कम होना, या 17 से बड़ा होना) के indicator signals बनाना है, और फिर उन indicators पर constraints लागू करना है।
Circomlib Comparator Library
Circomlib comparator library में एक LessThan कम्पोनेंट होता है जो यह indicate करने के लिए 0 या 1 रिटर्न करता है कि क्या in[0], in[1] से कम है। यह कम्पोनेंट कैसे काम करता है, इसका वर्णन Arithmetic Circuit अध्याय में किया गया है। लेकिन संक्षेप में, मान लीजिए कि x और y अधिकतम 3 बिट्स (bits) बड़े हैं। यदि हम z = 2^3 + (x - y) की गणना करते हैं, तो यदि x, y से कम है, तो z, 2^3 से कम होगा और इसके विपरीत (2^3 = 8)। चूँकि z एक 4-बिट संख्या है, हम केवल most significant bit (सबसे महत्वपूर्ण बिट) को देखकर कुशलतापूर्वक जांच सकते हैं कि क्या z, 2^3 से कम है। बाइनरी (binary) में 2^3 1000₂ होता है। 2^3 से बड़ी या उसके बराबर हर 4-बिट संख्या का most significant bit 1 के बराबर होता है, और 2^3 से कम हर 4-बिट संख्या का most significant bit 0 के बराबर होता है।
| संख्या | बाइनरी प्रतिनिधित्व | क्या 2^3 से बड़ा या बराबर है |
|---|---|---|
| 15 | 1111 | हाँ |
| 14 | 1110 | हाँ |
| 13 | 1101 | हाँ |
| … | ||
| 10 | 1010 | हाँ |
| 9 | 1001 | हाँ |
| 8 (2^3) | 1000 | हाँ |
| 7 | 0111 | नहीं |
| 6 | 0110 | नहीं |
| … | ||
| 2 | 0010 | नहीं |
| 1 | 0001 | नहीं |
| 0 | 0000 | नहीं |
सामान्य n-बिट संख्याओं के लिए, हम यह जांच सकते हैं कि क्या x, 2^n से बड़ा या उसके बराबर है, यह देखकर कि क्या most significant bit सेट है (1 है)। इसलिए, हम इसे सामान्यीकृत (generalize) कर सकते हैं कि यदि x और y, n-1 बिट संख्याएँ हैं, तो हम यह पता लगा सकते हैं कि क्या x < y है, यह जांच कर कि 2^(n-1) + (x - y) का most significant bit सेट है या नहीं।
यहाँ LessThan टेम्पलेट का उपयोग करने का एक न्यूनतम (minimal) उदाहरण दिया गया है:
include "circomlib/comparators.circom";
template Example () {
signal input a;
signal input b;
signal output out;
// 252 will be explained in the next section
out <== LessThan(252)([a, b]);
}
component main = Example();
/* INPUT = {
"a": "9",
"b": "10"
} */
252 कहाँ से आता है
एक finite field (जिसका उपयोग Circom करता है) में संख्याओं की एक-दूसरे से “कम (less than)” या “अधिक (greater)” के रूप में तुलना नहीं की जा सकती है क्योंकि असमानताओं (inequalities) के विशिष्ट बीजगणितीय (algebraic) नियम यहां लागू नहीं होते हैं।
उदाहरण के लिए, यदि है, तो यदि सकारात्मक (positive) है, तो यह हमेशा सत्य होना चाहिए कि । हालाँकि, एक finite field में यह सच नहीं है। हम को इस प्रकार चुन सकते हैं कि यह का additive inverse (योज्य प्रतिलोम) हो, यानी । तब हमें एक बेतुका (nonsensical) कथन मिलेगा कि 0 एक गैर-शून्य (non-zero) संख्या से बड़ा है। उदाहरण के लिए, यदि और और है, तो हमारे पास है। हालाँकि, यदि हम और दोनों में जोड़ते हैं, तो हमारे पास हो जाता है।
252 LessThan कम्पोनेंट में बिट्स की संख्या निर्दिष्ट (specify) करता है ताकि यह सीमित किया जा सके कि x और y कितने बड़े हो सकते हैं, जिससे एक सार्थक तुलना की जा सके (ऊपर दिए गए अनुभाग में उदाहरण के रूप में 4 बिट्स का उपयोग किया गया था)।
Circom finite field में 253 बिट्स तक की बड़ी संख्याएँ रख सकता है। Alias Check अध्याय में चर्चा किए गए सुरक्षा कारणों (security reasons) से, हमें किसी फ़ील्ड एलिमेंट को ऐसे बाइनरी प्रतिनिधित्व में परिवर्तित नहीं करना चाहिए जो फ़ील्ड से बड़ी संख्याओं को एन्कोड (encode) कर सके। इसलिए, Circom तुलना (comparison) टेम्प्लेट को 252 बिट्स से अधिक के साथ instantiate करने की अनुमति नहीं देता है (source code)।
हालाँकि, याद रखें कि LessThan(n) के लिए हमें z = 2^n + (x - y) की गणना करने की आवश्यकता होती है, और 2^n को x या y से एक बिट बड़ा होना चाहिए। इसलिए, x और y अधिकतम बिट्स बड़े होने चाहिए। चूँकि Circom 253 बिट्स तक की बड़ी संख्याओं का समर्थन करता है, इसलिए x और y अधिकतम 252 बिट्स बड़े होने चाहिए।
x, 5 से कम है या x, 17 से बड़ा है
शुक्र है, Circomlib लाइब्रेरी हमारे लिए अधिकांश काम कर देगी। हम यह indicate करने के लिए LessThan और GreaterThan कम्पोनेंट्स के आउटपुट सिग्नल्स (output signals) का उपयोग करेंगे कि क्या x 5 से कम है या 17 से बड़ा है।
फिर, हम OR कम्पोनेंट का उपयोग करके यह constrain करते हैं कि उनमें से कम से कम एक 1 हो (जो कि under the hood केवल out <== a + b - a * b है)।
pragma circom 2.1.6;
include "circomlib/comparators.circom";
include "circomlib/gates.circom";
template DisjointExample1() {
signal input x;
signal indicator1;
signal indicator2;
indicator1 <== LessThan(252)([x, 5]);
indicator2 <== GreaterThan(252)([x, 17]);
component or = OR();
or.a <== indicator1;
or.b <== indicator2;
or.out === 1;
}
component main = DisjointExample1();
/* INPUT = {
"x": "18"
} */
or.out === 1; constraint को शामिल करना बहुत महत्वपूर्ण है, अन्यथा सर्किट indicator1 और indicator2 दोनों सिग्नल्स के शून्य (zero) होने को भी स्वीकार कर लेगा। हम इस अध्याय के अंत में इस पर अधिक विस्तार से चर्चा करेंगे।
कोड को सरल बनाना
ऊपर दिए गए कोड को implicitly (निहित रूप से) indicator सिग्नल्स का उपयोग करके सरल बनाया जा सकता है, जैसा कि आगे प्रदर्शित किया गया है:
pragma circom 2.1.6;
include "circomlib/comparators.circom";
include "circomlib/gates.circom";
template DisjointExample1() {
signal input x;
component or = OR();
or.a <== LessThan(252)([x, 5]);
or.b <== GreaterThan(252)([x, 17]);
or.out === 1;
}
component main = DisjointExample1();
/* INPUT = {
"x": "18"
} */
ऐसा नहीं है कि x < 100 और y < 100 दोनों हों
उपरोक्त स्थिति को व्यक्त करने के लिए जहां "x < 100 और y < 100 दोनों हों”, हम एक NAND गेट का उपयोग कर सकते हैं। NAND गेट उन सभी संयोजनों (combinations) के लिए 1 रिटर्न करता है, सिवाय तब जब दोनों इनपुट 1 हों, जिसकी truth table (सत्यता सारणी) निम्नलिखित है:
| a | b | out |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
इसलिए, हम एक indicator सिग्नल बना सकते हैं कि x, 100 से कम है और एक indicator सिग्नल बना सकते हैं कि y, 100 से कम है, और उनके बीच एक NAND संबंध (relationship) को constrain कर सकते हैं।
pragma circom 2.1.6;
include "circomlib/comparators.circom";
include "circomlib/gates.circom";
template DisjointExample2() {
signal input x;
signal input y;
component nand = NAND();
nand.a <== LessThan(252)([x, 100]);
nand.b <== LessThan(252)([y, 100]);
nand.out === 1;
}
component main = DisjointExample2();
/* INPUT = {
"x": "18",
"y": "100"
} */
k; x, y, या z में से कम से कम 2 से बड़ा है
इस उदाहरण में, हम यह व्यक्त करने का प्रयास कर रहे हैं कि k, x और y से बड़ा है या k, x और z से बड़ा है, या k, y और z से बड़ा है। k; x, y और z तीनों से बड़ा हो सकता है, लेकिन इसकी आवश्यकता नहीं है।
चूँकि ऊपर दी गई ऐसी जटिल लॉजिक (logic) अभिव्यक्ति को व्यक्त करना बहुत लंबा (verbose) है, इसलिए उन सिग्नल्स की संख्या को जोड़ना अधिक सरल है जिनसे k बड़ा है, और फिर यह जांचना कि यह संख्या 2 या उससे अधिक है।
pragma circom 2.1.6;
include "circomlib/comparators.circom";
include "circomlib/gates.circom";
template DisjointExample3(n) {
signal input k;
signal input x;
signal input y;
signal input z;
signal totalGreaterThan;
signal greaterThanX;
signal greaterThanY;
signal greaterThanZ;
greaterThanX <== GreaterThan(252)([k, x]);
greaterThanY <== GreaterThan(252)([k, y]);
greaterThanZ <== GreaterThan(252)([k, z]);
totalGreaterThan = greaterThanX + greaterThanY + greaterThanZ;
signal atLeastTwo;
atLeastTwo <== GreaterEqThan(252)([totalGreaterThan, 2]);
atLeastTwo === 1;
}
component main = DisjointExample3();
/* INPUT = {
"k": 20
"x": 18,
"y": 100,
"z": 10
} */
कम्पोनेंट्स के आउटपुट को Constrain करना न भूलें!
कभी-कभी, डेवलपर्स कम्पोनेंट्स के आउटपुट को constrain करना भूल सकते हैं, जिससे गंभीर सुरक्षा कमजोरियां (security vulnerabilities) पैदा हो सकती हैं! उदाहरण के लिए, निम्नलिखित कोड ऐसा लग सकता है कि यह यह सुनिश्चित (enforce) करता है कि x और y दोनों 1 के बराबर हों, लेकिन ऐसा नहीं है। x और y शून्य (zero) (या कोई अन्य यादृच्छिक मान/arbitrary value) हो सकते हैं। यदि x और y शून्य हैं तो AND गेट का आउटपुट शून्य होगा, लेकिन आउटपुट को कुछ भी होने के लिए constrain नहीं किया गया है।
template MissingConstraint1() {
signal input x;
signal input y;
component and = AND();
and.a <== x;
and.b <== y;
// and.out is not constrained, so x and y can have any values!
}
इसी तरह, निम्नलिखित सर्किट x को 100 से कम होने के लिए बाध्य (force) नहीं करता है। यदि x, 100 से कम है तो LessThan का आउटपुट 1 होता है, लेकिन कोड यह सुनिश्चित करने के लिए आउटपुट को constrain नहीं करता है कि यह वास्तव में सच है।
template MissingConstraint2() {
signal input x;
component lt = LessThan(252);
lt.in[0] <== x;
lt.in[1] <== 100;
// x could be ≥ 100 since lt.out is allowed to be 0 or any other arbitrary value
}