पिछले अध्याय में, हमने दिखाया था कि वेक्टर्स और के तत्वों के योग को गुणा करने पर आउटर प्रोडक्ट (outer product) के पदों का योग प्राप्त होता है, अर्थात । हमने यह भी दिखाया था कि आउटर प्रोडक्ट के मुख्य विकर्ण (main diagonal) के साथ इनर प्रोडक्ट (inner product) “निहित” होता है।
इनर प्रोडक्ट को “निकालने” (extract) के लिए, आउटर प्रोडक्ट से उन सभी पदों को घटाना होगा जो इनर प्रोडक्ट का हिस्सा नहीं हैं, यानी नीचे दिया गया बैंगनी रंग का छायांकित क्षेत्र:

ऐसे पद हैं, इसलिए इसे सीधे करना कुशल (efficient) नहीं है।
हालाँकि, ध्यान दें कि हम नीचे दिए गए एनीमेशन में दिखाए गए तरीके से “आउटर प्रोडक्ट को भर” सकते हैं:
ऊपर दिए गए एनीमेशन में, प्रूवर (prover) द्वारा ऑफ-डायगोनल (off-diagonal) पदों को भेजने के बाद, प्रूवर और दोनों को फोल्ड (fold) करता है, जिससे उनकी लंबाई आधी हो जाती है।
अंत में, जब हम और को बार फोल्ड कर लेते हैं, तो वेक्टर्स का आकार 1 हो जाता है। जब होता है, तो आउटर प्रोडक्ट इनर प्रोडक्ट के बराबर हो जाता है और हम केवल दोनों वेक्टर्स को प्रकट (reveal) करते हैं, जो निरंतर आकार (constant size) के होंगे।
पुनरावृत्ति (Recap) – और यह पिछले अध्याय के एल्गोरिथम से कैसे संबंधित है
पहले, हमने दिखाया था कि यह कैसे साबित किया जाए कि हम के बजाय तत्व भेजते हुए कमिटमेंट की ओपनिंग (opening) जानते हैं। पुनरावृत्ति के रूप में:
प्रूवर वेक्टर को में के रूप में कमिट करता है। फिर प्रूवर ऑफ-डायगोनल पदों और को भेजता है। वेरिफायर (verifier) के साथ प्रतिक्रिया देता है और प्रूवर वेक्टर को पर के रूप में फोल्ड करता है और वेरिफायर को भेजता है। चूँकि की लंबाई है, इसलिए हमने प्रेषित (transmitted) किए जाने वाले डेटा का आकार आधा कर दिया है।
वेरिफायर फिर यह जांचता है कि
इस एल्गोरिथम का मूल उद्देश्य यह साबित करना था कि हम का कमिटमेंट जानते हैं, यह दिखाकर कि हम जानते हैं कि इनर प्रोडक्ट और ऑफ-डायगोनल पदों और का योग और के पेयरवाइज पार्टीशन (pairwise partitions) के आउटर प्रोडक्ट के तत्वों के योग के बराबर होता है।
यदि हम इस एल्गोरिथम को पुनरावर्ती (recursively) रूप से लागू करते हैं, तो हमें इस अध्याय के शुरुआत में वर्णित एल्गोरिथम प्राप्त होता है।
हालाँकि, हम इस प्रक्रिया की व्याख्या इस रूप में भी कर सकते हैं कि हम साबित कर रहे हैं कि हम लंबाई के आधार वेक्टर (basis vector) के संबंध में कमिटमेंट की ओपनिंग जानते हैं जहाँ है। हम सीधे तौर पर यह साबित कर सकते हैं कि हम भेजकर की ओपनिंग जानते हैं और वेरिफायर यह जांचता है कि ।
लेकिन भेजकर की ओपनिंग जानने को साबित करने के बजाय, हम आकार का एक वेक्टर भेजकर की ओपनिंग जानने को साबित करने के लिए एल्गोरिथम को पुनरावर्ती रूप से लागू कर सकते हैं। वास्तव में, हम तब तक पुनरावृत्ति (recurse) कर सकते हैं जब तक कि का आकार न हो जाए।
नीचे दिया गया एनीमेशन इस बात का आभास (intuition) देता है कि क्या हो रहा है। अगला खंड एनीमेशन का विस्तार से वर्णन करता है।

इस एल्गोरिथम के काम करने के लिए, वेक्टर्स की लंबाई दो की घात (power of two) होनी चाहिए। हालाँकि, यदि लंबाई दो की घात नहीं है, तो हम वेक्टर्स में तब तक शून्य (zeros) पैड (pad) कर सकते हैं जब तक कि लंबाई दो की घात न हो जाए।
यह साबित करना कि हम डेटा के साथ की ओपनिंग जानते हैं
एल्गोरिथम
प्रूवर और वेरिफायर लंबाई के आधार वेक्टर पर सहमत होते हैं। प्रूवर वेरिफायर को भेजता है जो है। प्रूवर वेरिफायर को यह विश्वास दिलाना चाहता है कि वे की ओपनिंग जानते हैं जबकि केवल लॉगरिदमिक आकार का डेटा भेजते हैं।
प्रूवर और वेरिफायर तब नीचे दिए गए एल्गोरिथम में संलग्न होते हैं। | के बाद के तर्कों (arguments) का अर्थ है कि वे केवल प्रूवर को ज्ञात हैं।
नीचे दिए गए एल्गोरिथम विवरण में इनपुट में वेक्टर्स की लंबाई है, जो सभी समान लंबाई के हैं।
\texttt{prove_commitments_log}(P, \mathbf{G}, | \mathbf{a})
स्थिति 1 (Case 1):
- प्रूवर भेजता है और वेरिफायर जांचता है कि और एल्गोरिथम समाप्त हो जाता है।
स्थिति 2 (Case 2):
- प्रूवर की गणना करता है और वेरिफायर को भेजता है जहाँ
- वेरिफायर रैंडमनेस (randomness) भेजता है
- प्रूवर और वेरिफायर दोनों गणना करते हैं:
- प्रूवर गणना करता है
- \texttt{prove_commitments_log}(P', \mathbf{G}', \mathbf{a}')
एल्गोरिथम पर टिप्पणी
प्रूवर पुनरावर्ती रूप से यह साबित कर रहा है कि, दिए गए मानों और के साथ, वे को जानते हैं जिससे हो। दोनों पक्ष पुनरावर्ती रूप से को तब तक फोल्ड करते हैं जब तक कि यह एक बिंदु न बन जाए, और प्रूवर पुनरावर्ती रूप से को तब तक फोल्ड करता है जब तक कि यह एक बिंदु न बन जाए।
प्रूवर प्रत्येक पुनरावृत्ति (iteration) पर एक निश्चित (constant) मात्रा में डेटा प्रेषित करता है, और रिकर्सन (recursion) अधिकतम बार चलेगा, इसलिए प्रूवर डेटा भेजता है।
हम इस बात पर जोर देते हैं कि यह एल्गोरिथम ज़ीरो नॉलेज (zero knowledge) नहीं है क्योंकि की स्थिति में, वेरिफायर पूरा वेक्टर जान लेता है। वेरिफायर के बारे में कुछ जानने का प्रयास करने के लिए के लिए गैर-यादृच्छिक (non-random) मान भी भेज सकता है।
हालाँकि, याद रखें कि इस एल्गोरिथम के लिए हमारी प्रेरणा चेक के आकार को कम करना है, और और शुरुआत से ही गुप्त (secret) नहीं थे।
वास्तव में, हमने यह नहीं दिखाया है कि यह कैसे साबित किया जाए कि हम लॉगरिदमिक आकार के डेटा के साथ इनर प्रोडक्ट को जानते हैं, हमने केवल यह दिखाया है कि हम लॉगरिदमिक आकार के डेटा के साथ कमिटमेंट की ओपनिंग को जानते हैं। हालाँकि, यह दिखाने के लिए कि हम दो वेक्टर्स के इनर प्रोडक्ट को जानते हैं, हमारे एल्गोरिथम को अपडेट करना सीधा (straightforward) है, जैसा कि हम इस लेख में बाद में करेंगे।
रनटाइम (Runtime)
वेरिफायर की गणना बार करता है, और पहले में समय लगता है। पहली नज़र में, ऐसा लगता है कि वेरिफायर का रनटाइम है। हालाँकि, ध्यान दें कि प्रत्येक पुनरावृत्ति के साथ, आधा हो जाता है, जिसके परिणामस्वरूप रनटाइम होता है, जिससे वेरिफायर के लिए कुल रनटाइम हो जाता है।
यह साबित करना कि हम इनर प्रोडक्ट जानते हैं
अब हम यह साबित करने के लिए उपरोक्त एल्गोरिथम को समायोजित (adjust) करते हैं कि हमने फ़ील्ड तत्वों के वेक्टर और एलिप्टिक कर्व बिंदुओं (elliptic curve points) के वेक्टर के बजाय दो स्केलर (scalar) वेक्टर्स के बीच इनर प्रोडक्ट किया है।
विशेष रूप से, हमें यह साबित करना होगा कि इनर प्रोडक्ट के लिए एक कमिटमेंट रखता है। यह इनर प्रोडक्ट एक स्केलर है, इसलिए हम वेक्टर कमिटमेंट के बजाय एक सामान्य पेडरसन कमिटमेंट (Pedersen commitment) करते हैं। इसके लिए हम (अज्ञात डिस्क्रीट लॉग (unknown discrete log) के साथ) एक यादृच्छिक एलिप्टिक कर्व बिंदु का उपयोग करते हैं। इस प्रकार, ।
हालाँकि, हम बस अपने पिछले एल्गोरिथम का पुन: उपयोग नहीं कर सकते क्योंकि प्रूवर के लिए कई ओपनिंग प्रदान कर सकता है। उदाहरण के लिए, यदि और , तो प्रूवर वेक्टर्स और के साथ भी ओपन कर सकता है।
एक इनर प्रोडक्ट के ज्ञान का सुरक्षित (secure) प्रूफ बनाने के लिए, प्रूवर को और के लिए भी एक कमिटमेंट की गणना करनी होगी और उसे भेजना होगा।
इसका सीधा उपाय (naive solution) कमिटमेंट एल्गोरिथम को दो बार चलाना है। पहली दो बार यह साबित करने के लिए कि और को और में ठीक से कमिट किया गया है और तीसरी बार यह दिखाने के लिए कि की ठीक से गणना की गई थी। अगले भाग में, हम दिखाते हैं कि जब दोनों वेक्टर्स फ़ील्ड तत्व (field elements) हों तो इनर प्रोडक्ट की गणना करने के लिए अपने एल्गोरिथम को कैसे संशोधित किया जाए।
स्केलर इनर प्रोडक्ट को स्केलर-पॉइंट इनर प्रोडक्ट में बदलना
मान लीजिए बिंदु की प्रतियों (copies) से युक्त एक वेक्टर है, अर्थात
इस प्रकार,
ध्यान दें कि , के बराबर है।
अर्थात्, हम की प्रत्येक प्रविष्टि (entry) को से गुणा कर सकते हैं और उस वेक्टर का के साथ इनर प्रोडक्ट ले सकते हैं और परिणाम के समान होगा। उदाहरण के लिए, यदि और , तो ।
वहां से, हम निम्नलिखित साबित कर सकते हैं:
तीन के बजाय एक प्रूफ
हम तीन कमिटमेंट्स भेजने और एल्गोरिथम को तीन बार चलाने की तुलना में बेहतर कर सकते हैं।
चूँकि , और बिंदुओं का अज्ञात डिस्क्रीट लॉग संबंध है, इसलिए उन्हें एक ही कमिटमेंट के रूप में जोड़ा जा सकता है।
हम अगली ट्रिक (trick) को अधिक स्पष्ट बनाने के लिए कमिटमेंट को के रूप में थोड़ा पुनर्व्यवस्थित (re-arrange) करेंगे।
तीन इनर प्रोडक्ट के बजाय इस पूरे कमिटमेंट को एक ही बार में साबित करने के लिए, ध्यान दें कि
जहाँ का अर्थ वेक्टर कॉनकैटेनेशन (vector concatenation) है।
प्रभावी रूप से, हम यह साबित कर रहे हैं कि हमने एलिप्टिक कर्व वेक्टर आधार (basis) के लिए वेक्टर को कमिट किया है।
व्यवहार में, हम वास्तव में वेक्टर्स को कॉनकैटिनेट नहीं करते हैं क्योंकि कुल लंबाई आम तौर पर दो की घात नहीं होगी। इसके बजाय, हम , , और घटकों (components) की अलग-अलग गणना करते हैं, लेकिन और की गणना इस तरह करते हैं जैसे कि वे कॉनकैटिनेट किए गए हों।
हम नीचे दिए गए एनीमेशन में एल्गोरिथम दिखाते हैं:
एल्गोरिथम
दिए गए और कमिटमेंट के साथ हम यह साबित करना चाहते हैं कि उसी तरह कमिट किया गया है जैसा दावा किया गया है। अर्थात्, , , और , में कमिट किए गए हैं और है।
\texttt{prove_commitments_log}(P, \mathbf{G}, \mathbf{H},Q, |\mathbf{a}, \mathbf{b})
स्थिति 1:
- प्रूवर भेजता है और वेरिफायर जांचता है कि । एल्गोरिथम समाप्त हो जाता है।
स्थिति 2:
- प्रूवर की गणना करता है और वेरिफायर को भेजता है जो केवल एक साथ कॉनकैटिनेट किए गए सभी वेक्टर्स के ऑफ-डायगोनल पद हैं (ऊपर दिया गया एनीमेशन देखें):
- वेरिफायर रैंडमनेस भेजता है।
- प्रूवर और वेरिफायर दोनों गणना करते हैं:
- प्रूवर गणना करता है:
- \texttt{prove_commitments_log}(P', G', H', \mathbf{a}', \mathbf{b}')
निम्नलिखित अभ्यास (exercises) हमारे ZK Bulletproofs GitHub Repo में पाए जा सकते हैं:
अभ्यास 1 (Exercise 1): यह साबित करने के लिए एल्गोरिथम लागू करने हेतु नीचे दिए गए छूटे हुए कोड को भरें कि बिंदु बनाने के लिए को में कमिट किया गया है:
from py_ecc.bn128 import G1, multiply, add, FQ, eq, Z1
from py_ecc.bn128 import curve_order as p
import numpy as np
from functools import reduce
import random
def random_element():
return random.randint(0, p)
def add_points(*points):
return reduce(add, points, Z1)
# if points = G1, G2, G3, G4 and scalars = a,b,c,d vector_commit returns
# aG1 + bG2 + cG3 + dG4
def vector_commit(points, scalars):
return reduce(add, [multiply(P, i) for P, i in zip(points, scalars)], Z1)
# these EC points have unknown discrete logs:
G_vec = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
(FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
(FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
(FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]
# return a folded vector of length n/2 for scalars
def fold(scalar_vec, u):
pass
# return a folded vector of length n/2 for points
def fold_points(point_vec, u):
pass
# return (L, R)
def compute_secondary_diagonal(G_vec, a):
pass
a = [4,2,42,420]
P = vector_commit(G_vec, a)
L1, R1 = compute_secondary_diagonal(G_vec, a)
u1 = random_element()
aprime = fold(a, u1)
Gprime = fold_points(G_vec, pow(u1, -1, p))
L2, R2 = compute_secondary_diagonal(Gprime, aprime)
u2 = random_element()
aprimeprime = fold(aprime, u2)
Gprimeprime = fold_points(Gprime, pow(u2, -1, p))
assert len(Gprimeprime) == 1 and len(aprimeprime) == 1, "final vector must be len 1"
assert eq(vector_commit(Gprimeprime, aprimeprime), add_points(multiply(L2, pow(u2, 2, p)), multiply(L1, pow(u1, 2, p)), P, multiply(R1, pow(u1, -2, p)), multiply(R2, pow(u2, -2, p)))), "invalid proof"
अभ्यास 2 (Exercise 2): उस एल्गोरिथम को लागू करने के लिए उपरोक्त कोड को संशोधित करें जो यह साबित करता है कि , , और का कमिटमेंट रखता है, और यह कि है। और EC बिंदु के लिए निम्नलिखित आधार वेक्टर (basis vector) का उपयोग करें:
H = [(FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919)),
(FQ(17471368056527239558513938898018115153923978020864896155502359766132274520000), FQ(4119036649831316606545646423655922855925839689145200049841234351186746829602)),
(FQ(8730867317615040501447514540731627986093652356953339319572790273814347116534), FQ(14893717982647482203420298569283769907955720318948910457352917488298566832491)),
(FQ(419294495583131907906527833396935901898733653748716080944177732964425683442), FQ(14467906227467164575975695599962977164932514254303603096093942297417329342836))]
Q = (FQ(11573005146564785208103371178835230411907837176583832948426162169859927052980), FQ(895714868375763218941449355207566659176623507506487912740163487331762446439))
यह ट्यूटोरियल Bulletproof ZKP पर एक सीरीज़ का हिस्सा है।