यादृच्छिक रैखिक संयोजनों के माध्यम से समानता जाँचों (प्रतिबंधों) की संख्या कम करना

Last updated on Nov 13, 2024

ज़ीरो नॉलेज प्रूफ (zero knowledge proof) एल्गोरिदम में यादृच्छिक रैखिक संयोजन (random linear combinations) एक सामान्य ट्रिक है, जो $m$ समानता जाँचों को संभावित रूप से एक ही समानता जाँच के साथ जाँचने में सक्षम बनाती है। मान लीजिए कि हमारे पास $m$ आंतरिक गुणनफल (inner products) हैं जिन्हें हम साबित करने का प्रयास कर रहे हैं। $m$ प्रमाण (proofs) बनाने के बजाय, हम समानताओं का एक यादृच्छिक रैखिक संयोजन बनाते हैं और उसे साबित करते हैं।

Pedersen Commitments की समानता

सबसे पहले, आइए विचार करें कि हम कई Pedersen commitments की समानता को कैसे साबित कर सकते हैं।

यदि हमारे पास अज्ञात डिस्क्रीट लॉग (discrete logs) वाले एलिप्टिक कर्व बिंदु (elliptic curve points) $G$ और $B$ हैं, और ब्लाइंडिंग टर्म्स (blinding terms) $\alpha$ और $\beta$ हैं, तो हम Pedersen committments $L$ और $R$ का निर्माण कर सकते हैं जहाँ

$L = aG + \alpha B$
$R = bG + \beta B$

यदि प्रमाणकर्ता (prover) ब्लाइंडिंग टर्म्स का अंतर प्रदान करता है, तो सत्यापनकर्ता (verifier) यह जाँच सकता है कि $a = b$ है या नहीं। सत्यापनकर्ता केवल $L = R$ की जाँच नहीं कर सकता क्योंकि ब्लाइंडिंग टर्म्स आम तौर पर एक-दूसरे के बराबर नहीं होंगे, अर्थात $\alpha \neq \beta$ ।

यदि प्रमाणकर्ता सत्यापनकर्ता को यह विश्वास दिलाना चाहता है कि $a$ और $b$ क्रमशः $L$ और $R$ के लिए कमिट किए गए हैं, लेकिन $a$ और $b$ को प्रकट किए बिना, तो प्रमाणकर्ता यह गणना कर सकता है:

$\pi = \alpha - \beta$

और $\pi$ सत्यापनकर्ता को दे देता है। सत्यापनकर्ता गणना करता है:

$L \stackrel{?}{=} R + \pi B$

आंतरिक रूप से, यह इस प्रकार विस्तारित होता है:

$(aG + \alpha B) = (bG + \beta B) + (\alpha - \beta) B$

सभी ब्लाइंडिंग टर्म्स कट जाएंगे और केवल $aG \stackrel{?}{=} bG$ बचेगा।

लेकिन मान लीजिए कि प्रमाणकर्ता कई कमिटमेंट्स के लिए समानता स्थापित करना चाहता है, अर्थात $L_1 = L_2, L_2 = R_2, ..., L_m = R_m$ । इसका एक सीधा (naïve) उपाय यह है कि $m$ ब्लाइंडिंग टर्म्स $\pi_1,...,\pi_m$ भेजे जाएं और सत्यापनकर्ता $m$ समानता जाँच चलाएगा। इसके लिए $m$ फील्ड तत्वों (field elements) ( $\pi_1,...,\pi_m$ ) को भेजने की आवश्यकता होगी और सत्यापनकर्ता का एल्गोरिदम $\mathcal{O}(m)$ समय में चलेगा।

प्रमाणकर्ता केवल सभी कमिटमेंट्स को क्यों नहीं जोड़ सकता

मान लीजिए कि हमारे पास क्रमशः $L_1, L_2, R_1, R_2$ कमिटमेंट्स के साथ $l_1, l_2, r_1, r_2$ हैं। यह भी मान लीजिए कि प्रमाणकर्ता उन्हें प्रकट किए बिना यह दिखाना चाहता है कि $l_1 = r_1$ और $l_2 = r_2$ है।

निम्नलिखित जाँच सुरक्षित नहीं है:

L_1 + L_2 = R_1 + R_2 + \pi B

जहाँ $\pi$ ब्लाइंडिंग टर्म्स का अंतर है। एक प्रति-उदाहरण (counterexample) के रूप में, उस स्थिति पर विचार करें जहाँ $l_1 = 1, r_1 = 2, l_2 = 2, r_2 = 1$ है। इनके योग (sums) तो संतुलित हैं, लेकिन मूल दावा गलत है।

यादृच्छिक रैखिक संयोजन (Random linear combinations)

हालाँकि, यदि प्रमाणकर्ता को यह दिखाने की आवश्यकता हो कि

L_1 + L_2z = R_1 + R_2z + \pi B

एक यादृच्छिक (random) मान $z$ के लिए जिसकी वे भविष्यवाणी नहीं कर सकते, तो यह योजना सुरक्षित है।

विशेष रूप से, प्रमाणकर्ता और सत्यापनकर्ता निम्नलिखित एल्गोरिदम का पालन करते हैं:

समानता का यादृच्छिक प्रमाण

सेटअप (Setup)

प्रमाणकर्ता और सत्यापनकर्ता एलिप्टिक कर्व बिंदु $G$ और $B$ पर सहमत होते हैं, जहाँ डिस्क्रीट लॉग अज्ञात होते हैं।

प्रमाणकर्ता कमिटमेंट्स भेजता है

प्रमाणकर्ता ब्लाइंडिंग टर्म्स $\alpha_1, \alpha_2, \beta_1, \beta_2$ उत्पन्न करता है और Pedersen commitments बनाता है:

$L_1 = l_{1}G + \alpha_1 B$
$R_1 = r_{1}G + \beta_1 B$
$L_2 = l_{2}G + \alpha_2 B$
$R_2 = r_{2}G + \beta_2 B$

और $(L_1, L_2, R_1, R_2)$ सत्यापनकर्ता को भेज देता है।

सत्यापनकर्ता एक यादृच्छिक $z$ चुनता है

सत्यापनकर्ता एक यादृच्छिक फील्ड तत्व $z$ चुनता है और इसे प्रमाणकर्ता को भेजता है।

प्रमाणकर्ता ब्लाइंडिंग टर्म्स में अंतर की गणना करता है

प्रमाणकर्ता $\pi = \alpha_1+\alpha_2\cdot z-\beta_1-\beta_2\cdot z$ की गणना करता है और $\pi$ को सत्यापनकर्ता के पास भेज देता है।

अंतिम सत्यापन जाँच

सत्यापनकर्ता जाँच करता है कि

L_1+L_2z\stackrel{?}=R_1+R_2z+\pi B

सुरक्षा विश्लेषण (Security analysis)

यदि $l_1 = r_1$ और $l_2 = r_2$ है, तो $z$ के चुनाव की परवाह किए बिना समीकरण संतुलित होगा, यह मानते हुए कि प्रमाणकर्ता ने $\pi$ की सही गणना की है।

अब मान लीजिए कि $l_1\neq r_1$ या $l_2 \neq r_2$ है। फिर भी प्रमाणकर्ता एक वैध $\pi$ उत्पन्न करने में सक्षम नहीं होगा क्योंकि ऐसा करने के लिए $G$ और $B$ के डिस्क्रीट लॉग को हल करने की आवश्यकता होगी।

$m$ जाँचों तक सामान्यीकरण

यदि हमारे पास $m$ समानता जाँचें हैं, $L_1 = R_1, L_2 = R_2, ..., L_m = R_m$ , तो सत्यापनकर्ता $m$ यादृच्छिक तत्व $z_1,\dots,z_m$ भेज सकता है और प्रमाणकर्ता $\pi$ प्रदान कर सकता है ताकि

$L_1 + L_2z_1 + L_3z_2 + ... L_mz_{m-1} \stackrel{?}{=}R_1 + R_2z_1+R_3z_2+\dots+R_mz_{m-1} + \pi B$

हालाँकि, इसके लिए सत्यापनकर्ता को $m$ तत्व भेजने की आवश्यकता होती है, जिससे लीनियर संचार ओवरहेड (linear communication overhead) बढ़ जाता है। यदि सत्यापनकर्ता केवल $z$ भेजता है और प्रमाणकर्ता और सत्यापनकर्ता कमिटमेंट्स को $z$ की क्रमिक घातों (successive powers) से अलग करते हैं, तो संचार ओवरहेड को स्थिरांक (constant) तक कम किया जा सकता है:

$L_1 + L_2z + L_3z^2 + ... L_mz^{m-1} \stackrel{?}{=}R_1+R_2z+R_3z^2\dots+R_mz^{m-1} + \pi B$

सुरक्षा विश्लेषण

बायाँ पक्ष और दायाँ पक्ष दोनों $m-1$ घात के बहुपद (polynomials) हैं। यदि वे एक-दूसरे के असमान हैं, तो Schwartz Zippel Lemma के अनुसार वे अधिकतम $m-1$ बिंदुओं पर प्रतिच्छेद करते हैं। यदि $m\ll p$ जहाँ $p$ परिमित क्षेत्र (finite field) का क्रम (order) है, तो फिर से $z$ के एक प्रतिच्छेदन बिंदु होने की संभावना नगण्य है।

आंतरिक गुणनफलों (inner products) के यादृच्छिक रैखिक संयोजन

हम कई आंतरिक गुणनफलों को एक साथ मिलाने के लिए उपरोक्त तकनीक को सामान्यीकृत कर सकते हैं।

मान लीजिए कि हमारे पास दो आंतरिक गुणनफल हैं:

$\langle \mathbf{a}_L, \mathbf{a}_R\rangle = v_1$ और $\langle \mathbf{a}_L, \mathbf{a}_W\rangle=v_2$

क्योंकि दोनों आंतरिक गुणनफलों में एक सामान्य पद साझा है, इसलिए बीजगणितीय रूप से उन्हें निम्नानुसार संयोजित करना संभव है:

$\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$

हालाँकि, सुदृढ़ता (soundness) के दृष्टिकोण से यह सुरक्षित नहीं है क्योंकि यह संभव है कि $\langle \mathbf{a}_L, \mathbf{a}_R\rangle \neq v_1$ और $\langle \mathbf{a}_L, \mathbf{a}_W\rangle\neq v_2$ हो, लेकिन $\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$ हो।

जैसा कि अपेक्षित था, हम एक यादृच्छिक रैखिक संयोजन का उपयोग करके इसे हल कर सकते हैं।

\begin{align*} &\langle \mathbf{a}_L, \mathbf{a}_R\rangle = v_1 &&\text{ // first inner product}\\ &z\langle \mathbf{a}_L, \mathbf{a}_W\rangle=z\cdot v_2 &&\text{ // second inner product}\\ &\langle \mathbf{a}_L, z\cdot\mathbf{a}_W\rangle=z\cdot v_2 &&\text{ // bring } z \text{ inside}\\ &\langle\mathbf{a}_L, \mathbf{a}_R + z\cdot\mathbf{a}_W\rangle = v_1 + z\cdot v_2&&\text{ // combine into one inner product} \end{align*}

हमें दो के बजाय केवल एक ही आंतरिक गुणनफल के लिए एक आंतरिक गुणनफल प्रमाण (inner product proof) बनाने की आवश्यकता है। यह महत्वपूर्ण है कि प्रमाणकर्ता को प्रासंगिक कमिटमेंट्स भेजने के बाद ही $z$ प्राप्त हो, लेकिन हम इसके सटीक विवरण को अगले अध्याय के लिए छोड़ देते हैं जब हम इस तकनीक का उपयोग करने वाले एल्गोरिदम का एक उदाहरण देखेंगे: रेंज प्रूफ्स (range proofs)।

यह ट्यूटोरियल ZK Bulletproofs पर एक श्रृंखला का हिस्सा है।