सांत क्षेत्र: वह संख्या-प्रणाली जिसमें क्रिप्टोग्राफी रहती है

Annkkitaaa का मूल शोध

"चक्कर लगाकर वापस आना" Zcash की गुप्त नींव क्यों है

श्रृंखला: Zcash First Principles से . लेख 1 . Finite Fields पाठक-वर्ग: नए पाठक। हम केवल सामान्य स्कूली अंकगणित (जोड़ना, गुणा करना, भाग देना) मानकर चलते हैं। क्रिप्टोग्राफी या उच्च गणित का कोई पूर्वज्ञान आवश्यक नहीं है। आप यहाँ से क्या लेकर जाएँगे: finite fields की सहज और सही समझ, cryptographers उनका उपयोग क्यों करते हैं, और Zcash के भीतर वे कहाँ दिखाई देते हैं।

लेख 0 में हमने पाँच पात्रों से मुलाकात की थी: note, commitment, note commitment tree, nullifier, और zero-knowledge proof। वहाँ हमने एक खुला सिरा छोड़ दिया था: ये सारी keys और गुप्त विधियाँ आखिर आती कहाँ से हैं? वे संख्याओं से आती हैं। लेकिन उन सामान्य संख्याओं से नहीं जिनके साथ आप बड़े हुए हैं। वे एक विशेष, आत्म-निहित संख्या-प्रणाली से आती हैं जिसे finite field कहा जाता है, और Zcash की लगभग हर cryptography उसी के ऊपर बनाई गई है।

यह लेख उस विचार तक धीरे-धीरे पहुँचता है। जैसा वादा था, पहले intuition। सूत्र तभी, जब वे सचमुच काम आएँ।

1. आपको इसकी परवाह क्यों करनी चाहिए?

सामान्य संख्याओं में cryptography के लिए एक समस्या है: उनकी संख्या अनंत होती है, और वे जानकारी लीक करती हैं।

सोचिए, जब कोई संख्या बड़ी होती जाती है तो क्या होता है। अगर मैं आपको बताऊँ कि किसी गुप्त गणना का परिणाम 8,142,067 निकला, तो आप पहले ही बहुत कुछ जान लेते हैं: यह सात अंकों की संख्या है, विषम है, और "काफी बड़ी" है। आकार अपने-आप में एक संकेत है। और संकेत वही चीज़ हैं जिन्हें कोई privacy system बिल्कुल भी बाहर नहीं जाने दे सकता।

क्रिप्टोग्राफी को ऐसी संख्या-प्रणाली चाहिए जिसमें:

• सीमित संख्या में मान हों, ताकि कंप्यूटर उनमें से किसी भी मान को बिना rounding और overflow के ठीक-ठीक संग्रहित कर सके,
• मान अपना आकार प्रकट न करें, क्योंकि उस प्रणाली में "बड़ा" होने की कोई वास्तविक धारणा ही न हो,
• आप फिर भी जोड़, घटा, गुणा और भाग स्वतंत्र रूप से और उलटने योग्य तरीके से कर सकें, क्योंकि cryptographic recipes को काम करने के लिए वास्तविक बीजगणित चाहिए, और
• वह स्थान खगोलीय रूप से विशाल बनाया जा सके, ताकि अनुमान लगाना निराशाजनक हो जाए।

इस पूरी इच्छासूची का एक नाम है। उसे finite field कहते हैं। एक भी चिन्ह लिखने से पहले उसकी intuition बना लेते हैं।

2. सहज समझ: एक घड़ी

आप finite field का उपयोग पहले से ही हर दिन करते हैं। वह है आपकी दीवार पर लगी घड़ी।

12-घंटे की घड़ी पर संख्याएँ फिर से शुरू हो जाती हैं। 10 बजे से शुरू कीजिए, 5 घंटे जोड़िए, और आप "15 बजे" पर नहीं पहुँचते, बल्कि 3 बजे पर पहुँचते हैं। घड़ी में केवल बारह स्थान होते हैं, और ऊपर से आगे गिनने पर गिनती बस वापस शुरुआत पर लौट आती है।

अभी तीन चीज़ें हुईं, और यही इस पूरे लेख का सार है:

1. दुनिया सीमित है। चाहे आप कितनी भी देर गिनें, कुल मिलाकर ठीक बारह ही स्थान हैं।
2. जोड़ फिर भी काम करता है। आप पूरे दिन घंटे जोड़ते रहिए; आप हमेशा घड़ी के किसी वैध स्थान पर ही उतरेंगे।
3. आकार का महत्व खत्म हो गया। "3 बजे" यह नहीं बताता कि आपने 3 घंटे गिने, या 15, या 27। यह wrap-around आकार की जानकारी मिटा देता है। वही मिटाना ठीक वही privacy-friendly गुण है जिसकी हमें तलाश थी।

इस wrap-around अंकगणित का एक औपचारिक नाम है: modular arithmetic। घड़ी "modulo 12" पर काम करती है, जिसे mod 12 लिखा जाता है। गणितज्ञ स्थानों की गिनती 0 से शुरू करना पसंद करते हैं, इसलिए "mod 12 की घड़ी" में वास्तव में 0, 1, 2, ..., 11 स्थान होते हैं। mod 7 की घड़ी में 0 से 6 तक स्थान होंगे।

एकमात्र नियम: "mod p" में कुछ भी निकालने के लिए सामान्य अंकगणित कीजिए, फिर p से भाग देकर केवल शेषफल रख लीजिए। mod 7 का उदाहरण: 5 + 4 = 9, और 9 को 7 से भाग देने पर शेष 2 बचता है, इसलिए 5 + 4 = 2 (mod 7)।

3. घड़ी से field तक

घड़ी हमें जोड़ने देती है। Field उसका उन्नत रूप है: ऐसी संख्या-प्रणाली जिसमें चारों क्रियाएँ ठीक से चलती हैं, यहाँ तक कि कठिन वाली—भाग—भी।

अनौपचारिक रूप से, field ऐसी किसी भी "संख्या" का संग्रह है जिसमें आप जोड़, घटा, गुणा और भाग कर सकें (शून्य से छोड़कर), और परिचित नियम अब भी लागू हों: जोड़ और गुणा में क्रम बदलने से फर्क न पड़े, कोष्ठकों को फिर से समूहित किया जा सके, एक 0 और एक 1 हो, और हर संख्या का एक ऋणात्मक तथा (0 को छोड़कर) एक reciprocal हो।

परिमेय संख्याएँ एक field हैं। वास्तविक संख्याएँ एक field हैं। हमें चाहिए इनका एक सीमित रूप।

अब मुख्य परिणाम, और यह बहुत सुंदर है:

पूरी संख्याएँ 0, 1, ..., p-1 लीजिए और उन पर सारी गणना mod p कीजिए। यदि p एक prime संख्या है, तो परिणाम एक finite field होता है। इसे हम F_p लिखते हैं (पढ़ें "F sub p")।

तो mod 7 की घड़ी-जैसी अंकगणित के साथ F_7 = {0, 1, 2, 3, 4, 5, 6} सचमुच एक finite field है। आइए इसे काम करते हुए देखें।

F_7 में गुणा (सत्यापित)

तालिका की हर प्रविष्टि (row x column) mod 7 है:

1 से 6 तक की पंक्तियों को देखिए: हर पंक्ति में 1..6 का हर nonzero मान ठीक एक बार आता है। यह "न दोहराव, न कुछ गायब" वाला पैटर्न field का दिखाई देने वाला fingerprint है।

भाग: वह जादू जिसके लिए prime चाहिए

भाग वास्तव में "reciprocal से गुणा" ही है। F_7 में किसी संख्या a का reciprocal (या inverse) वह मान a^(-1) है जिसके लिए a x a^(-1) = 1। इन्हें सीधे तालिका से पढ़ते हैं:

एक जाँच: 2 x 4 = 8 = 1 (mod 7)। तो F_7 में "2 से भाग" का मतलब है "4 से गुणा"। हर nonzero तत्व का एक साथी है। यही चीज़ F_7 को field बनाती है।

4. modulus का prime होना क्यों ज़रूरी है

यह इस लेख का सबसे महत्वपूर्ण विचार है, इसलिए इसे अमूर्त रखने के बजाय ठोस रूप में देखते हैं।

देखिए क्या टूटता है यदि हम सीधे-सीधे mod 6 पर एक "field" बनाने की कोशिश करें (और 6 prime नहीं है):

क्या कोई x है जिसके लिए 2 x x = 1 (mod 6) हो? सब जाँच लें: 2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4। उत्तर 1 कभी आता ही नहीं। इसलिए mod 6 में 2 का कोई reciprocal नहीं है। इससे भी बुरा, 2 x 3 = 6 = 0 (mod 6) है: दो nonzero संख्याओं का गुणनफल शून्य निकल आया।

दूसरी बात अंकगणित के लिए विनाशकारी है। दो nonzero चीज़ों का गुणा शून्य देना (जिसे zero divisor कहते हैं) मतलब भाग की व्यवस्था टूट गई, और जिसकी division टूटी हो वह प्रणाली field नहीं हो सकती। यह ठीक इसलिए होता है क्योंकि 6 के गुणनखंड 2 x 3 हैं।

परिभाषा के अनुसार prime में ऐसे गुणनखंड नहीं होते। इसलिए किसी prime के mod में zero divisors नहीं आते, हर nonzero तत्व का साफ reciprocal मिलता है, और संरचना एक सही field बनती है।

आपके लेखों के लिए याद रखने लायक एक पंक्ति: prime modulus डालो, साफ division पाओ।

5. मिलने लायक एकमात्र सूत्र: कंप्यूटर inverse कैसे निकालते हैं

हमने F_7 के लिए inverses तालिका से पढ़ लिए, लेकिन Zcash का prime सैकड़ों अंकों का होता है; वहाँ कोई तालिका संभव नहीं। इसके लिए एक क्लासिक shortcut है, और यही इस लेख का एकमात्र सूत्र है।

Fermat's Little Theorem कहती है कि किसी prime p और किसी भी nonzero a के लिए:

a^(p-1) = 1   (mod p)

इसे थोड़ा पुनर्व्यवस्थित कीजिए (यानी a का एक गुणक अलग कीजिए) और inverse मुफ्त में मिल जाता है:

a^(-1) = a^(p-2)   (mod p)

इसे F_7 में जाँचें (p = 7, तो p - 2 = 5): 2 का inverse 2^5 = 32 = 4 (mod 7) होना चाहिए। और हमारी तालिका ने सचमुच यही कहा था कि 2^(-1) = 4। कंप्यूटर बहुत बड़ी घातों को भी बेहद तेज़ी से निकाल लेते हैं, इसलिए यह "reciprocal खोजो" को विशाल primes के लिए भी एक तेज़, सटीक गणना में बदल देता है।

आपको इसे कंठस्थ करने की आवश्यकता नहीं है। आपको यह जानना है कि finite field में division एक तेज़ और सटीक क्रिया है, और यही कारण है कि cryptographers उसके ऊपर निर्माण करने में प्रसन्न रहते हैं।

6. cryptography finite fields की दीवानी क्यों हो गई

अब तक की intuition को एक साथ रखें, तो पूरी बात एक ही पृष्ठ पर यह है।

एक वाक्य में finite field है: अंकगणित के लिए एक पूरी तरह बंद, पूरी तरह सटीक, और पूरी तरह विशाल खेल का मैदान। Zcash में बाकी सब कुछ उसी के भीतर खेलते हुए बनाया जाता है।

7. Zcash में यह कहाँ रहता है

आपको "Zcash finite fields का उपयोग करता है" यह बात मानकर चलने की ज़रूरत नहीं है। यह उसका ठोस नक्शा है (गहरी मशीनरी बाद के लेखों में आएगी; अभी सिर्फ इतना दिखाना है कि fingerprint सचमुच मौजूद हैं)।

• Sapling (एक पुराना shielded design) अपने proofs एक curve पर बनाता है जिसे BLS12-381 कहा जाता है, जिसकी base field में एक 381 bits लंबा prime उपयोग होता है। हर coordinate, key, और proof element उस prime पर बने finite field का तत्व है।
• Orchard (वर्तमान shielded design) Pallas और Vesta (यानी "Pasta" curves) नाम की curves की एक जोड़ी का उपयोग करता है, जिनकी fields में लगभग 255 bits लंबे primes उपयोग होते हैं।
• लेख 0 का note commitment, nullifier, और zero-knowledge proof के भीतर की संख्याएँ, मूलतः, इन्हीं finite fields में से किसी एक के तत्व हैं। जब protocol कहता है "यह commitment निकालो", तो उसका अर्थ होता है "उस prime के mod में यह अंकगणित करो"।

तो लेख 0 के खुले प्रश्न, "ये गुप्त recipes आती कहाँ से हैं?", का उत्तर यहीं से शुरू होता है: सब कुछ finite field में अंकगणित से शुरू होता है। अगले लेख में हम इसी field से वास्तविक वस्तुएँ बनाएँगे—elliptic curve पर बिंदु—जो आगे चलकर keys और commitments बनते हैं।

8. एक ईमानदार अस्वीकरण

नए पाठकों के लिए इसे अनुकूल बनाए रखने के लिए हमने कुछ सच बातों को सरल किया है। Finite fields केवल F_p रूप में नहीं आते; आप p^n तत्वों वाले fields भी बना सकते हैं (जिन्हें extension fields कहा जाता है), और Sapling की proof system जिन "pairings" पर निर्भर करती है, उनमें इनका महत्व है। हमने field axioms की पूरी सूची भी छोड़ दी, और यह भी नहीं बताया कि इतने बड़े primes चुने और सत्यापित कैसे किए जाते हैं। इससे आपकी अभी की intuition बदलती नहीं; बस और परिष्कृत होती है। जब किसी बाद के लेख को उसकी ज़रूरत होगी, तब हम सावधानी से वह सटीकता वापस जोड़ देंगे।

9. सारांश

• क्रिप्टोग्राफी को ऐसी संख्या-प्रणाली चाहिए जो सीमित, सटीक, आकार-अंधी, पूरी तरह उलटने योग्य, और विशाल हो। वही प्रणाली finite field है।
• इसकी intuition एक घड़ी है: ऐसा अंकगणित जो चक्कर लगाकर वापस आता है (modular arithmetic), और इसी प्रक्रिया में किसी संख्या का "आकार" मिटा देता है।
• 0..p-1 संख्याओं पर किसी prime p के mod में अंकगणित करने से एक वास्तविक field F_p मिलता है, जिसमें आप भाग भी कर सकते हैं क्योंकि हर nonzero तत्व का inverse होता है।
• modulus का prime होना अनिवार्य है: composite modulus zero divisors पैदा करता है (जैसे 2 x 3 = 0 mod 6) और division तोड़ देता है।
• कंप्यूटर Fermat's Little Theorem (a^(-1) = a^(p-2)) के माध्यम से inverses तेज़ी से निकालते हैं।
• Zcash में हर key, commitment, nullifier, और proof element अंततः किसी बड़े finite field का तत्व होता है (Orchard के लिए 255-bit Pasta fields, Sapling के BLS12-381 के लिए 381-bit field)।

शब्दावली

FAQ

सामान्य integers या decimals का ही उपयोग क्यों न करें? Decimals में rounding और drift आती है; integers बिना सीमा के बढ़ते जाते हैं और अपना आकार प्रकट करते हैं। Finite fields सटीक, सीमित, और आकार-अंधे होते हैं, और cryptography को यही चाहिए।

क्या "चक्कर लगाकर वापस आना" जानकारी खो देता है? हाँ, जानबूझकर। मध्यवर्ती मानों के आकार को मिटा देना privacy के लिए bug नहीं, feature है।

क्या बड़ा prime हमेशा अधिक सुरक्षित होता है? ढीले अर्थ में, बड़ा field अधिक संभावित मान देता है और अनुमान लगाना कठिन बनाता है, लेकिन सुरक्षा केवल field के आकार पर नहीं, पूरी construction पर निर्भर करती है। आगे के लेख इसे सटीक बनाएँगे।

Zcash में यही विशेष primes (255-bit, 381-bit) क्यों हैं? उन्हें इसलिए चुना जाता है ताकि उन पर बनी curves में proof system के लिए सही संरचना और दक्षता हो। यही "सही संरचना" अगले दो लेखों का विषय है।

अपनी intuition जाँचें

F_7 में 5 - 6 क्या होगा? (याद रखें: wrap-around करके {0,...,6} के भीतर ही रहना है।) (उत्तर नीचे है।)

आगे क्या

लेख 2 . Elliptic curves: अभी जो finite field हमने बनाया है, अगले लेख में हम उसी का उपयोग एक अजीब तरह की curve बनाने के लिए करेंगे जिसके बिंदुओं को आपस में "जोड़ा" जा सकता है। वही बिंदु Zcash की keys और commitments बनते हैं, और उनमें एक one-way trapdoor छिपा होता है जो पूरी privacy system को संभव बनाता है। हमेशा की तरह, पहले intuition।

यह Zcash First Principles से श्रृंखला का हिस्सा है, ZecHub के लिए। Licensed CC BY-SA 4.0.