ब्लॉकचेन की मूल बातें समझना: बीजान्टिन जनरलों की चुनौती। भाग 1

लेख का अनुवाद विशेष रूप से "हाई लोड आर्किटेक्ट" पाठ्यक्रम के छात्रों के लिए तैयार किया गया था, जो इस महीने शुरू होता है।

---

ब्लॉकचेन एक विकेन्द्रीकृत प्रणाली है जिसमें विभिन्न इकाइयाँ शामिल होती हैं जो उनके प्रोत्साहन और उनके पास मौजूद जानकारी के आधार पर काम करती हैं।

जब भी कोई नया लेन-देन नेटवर्क पर प्रसारित होता है, नोड्स इस लेन-देन को उनके बहीखाता की प्रतिलिपि में शामिल कर सकते हैं या इसे अनदेखा कर सकते हैं। जब अधिकांश नेटवर्क प्रतिभागी एक निश्चित राज्य को स्वीकार करने का निर्णय लेते हैं, तो सहमति बन जाती है।

वितरित कंप्यूटिंग और मल्टी-एजेंट सिस्टम में एक बुनियादी समस्या कई निष्क्रिय प्रक्रियाओं की उपस्थिति में समग्र प्रणाली की विश्वसनीयता हासिल करना है। अक्सर, इसके लिए यह आवश्यक होता है कि गणना के दौरान आवश्यक कुछ मूल्य आपस में समन्वयित हों।

इन प्रक्रियाओं को आम सहमति के रूप में वर्णित किया गया है।

• क्या होता है जब एक प्रतिभागी नियमों का पालन नहीं करने का निर्णय लेता है और उसके नेतृत्व में राज्य में हस्तक्षेप करता है?
• क्या होता है जब नेटवर्क में बहुत सारे ऐसे प्रतिभागी होते हैं, लेकिन बहुमत नहीं?

सर्वसम्मति प्रोटोकॉल सुरक्षित होने के लिए, यह दोष सहिष्णु होना चाहिए।

सबसे पहले, हम संक्षेप में दो जनरलों की अघुलनशील समस्या के बारे में बात करते हैं। फिर, बीजान्टिन जनरलों की समस्या पर विचार करें और वितरित और विकेंद्रीकृत प्रणालियों में बीजान्टिन दोष सहिष्णुता पर चर्चा करें। और सबसे अंत में, आइए बात करते हैं कि यह सब ब्लॉकचेन तकनीक से कैसे संबंधित है।

दो सेनापतियों का कार्य

यह कार्य, जो पहली बार 1975 में प्रकाशित हुआ और 1978 में नाम दिया गया, एक परिदृश्य का वर्णन करता है जिसमें दो सेनापति एक आम दुश्मन पर हमला करते हैं। पहले जनरल को नेता माना जाता है, और दूसरा अनुयायी है। अकेले प्रत्येक सेना की सेना दुश्मन सेना को हराने के लिए पर्याप्त नहीं है, इसलिए उन्हें एक ही समय में सहयोग करने और हमला करने की आवश्यकता है। यह परिदृश्य सरल दिखता है, लेकिन एक चेतावनी है:

उन्हें एक समय पर संवाद करने और सहमत होने के लिए, पहले जनरल को दुश्मन के शिविर के माध्यम से एक संदेशवाहक को भेजना होगा, उसे हमले की शुरुआत के समय के साथ एक संदेश दूसरे जनरल तक पहुंचाना होगा। हालांकि, यह संभावना है कि दूत विरोधियों द्वारा कब्जा कर लिया जाएगा, और संदेश वितरित नहीं किया गया है। यह इस तथ्य को जन्म देगा कि पहले जनरल की सेना हमले पर जाएगी, और दूसरा स्थान पर रहेगा।

यहां तक ​​कि अगर पहला संदेश दिया जाता है, तो दूसरे सामान्य की पुष्टि होनी चाहिए (ACK (स्वीकार करें), टीसीपी में तीन-तरफा हैंडशेक की समानता पर ध्यान दें) कि उसे संदेश प्राप्त हुआ, इसलिए वह मैसेंजर को वापस भेजता है, जिससे पिछले परिदृश्य को पुन: पेश किया जा सके जहां संदेशवाहक को पकड़ा जा सके। । यह अंतहीन ACKs में बहता है, और इस वजह से, जनरल्स समझौते तक नहीं पहुंच पाते हैं।

दूसरी शर्त की गारंटी देने का कोई तरीका नहीं है, अर्थात्, प्रत्येक सामान्य पूरी तरह से आश्वस्त है कि अन्य हमले की योजना से सहमत है। दोनों सेनापति हमेशा इस बात से अनभिज्ञ होंगे कि क्या दूत अपने साथी के पास पहुँच गया है।



यह साबित हो गया कि दो जनरलों का कार्य अस्वीकार्य है।

बीजान्टिन जनरलों का कार्य

लैम्पपोर्ट, शोस्टक और पिज़ द्वारा 1982 में वर्णित, इस समस्या का संस्करण एक आकर्षण बन गया। वह उसी परिदृश्य का वर्णन करती है, जहां दो जनरलों के बजाय, अधिक जनरलों को हमले के समय सहमत होना चाहिए। एक अतिरिक्त जटिलता यह है कि एक या एक से अधिक जनक गद्दार हो सकते हैं, अर्थात, वे अपने इरादों के बारे में झूठ बोल सकते हैं (उदाहरण के लिए, सामान्य कहता है कि वह 09:00 पर हमला करने के लिए सहमत है, लेकिन नहीं करता है)।

दो जनरलों के कार्य में वर्णित नेता-अनुयायी का प्रतिमान एक कमांडर-अधीनस्थ स्थापना में बदल जाता है। यहां सर्वसम्मति प्राप्त करने के लिए, कमांडर और प्रत्येक अधीनस्थ को एक ही समाधान (हमले या पीछे हटने) पर सहमत होना होगा।

चित्र अनुवाद:

बीजान्टिन जनरलों का कार्य। कमांडर जनरल को अपने n-1 अधीनस्थों को एक आदेश भेजना होगा, जैसे:

• सभी वफादार अधीनस्थ जनरलों ने एक आदेश का पालन किया।
• यदि कमांडर जनरल वफादार होता है, तो उसके सभी वफादार अधीनस्थ उसके आदेशों का पालन करते हैं।

दूसरे बिंदु के अलावा, एक दिलचस्प तथ्य को इंगित किया जाना चाहिए: यदि कमांडर एक गद्दार है, तो आम सहमति अभी भी पहुंचनी चाहिए। नतीजतन, सभी लेफ्टिनेंटों के पास बहुमत वाला वोट होता है।

इस मामले में सर्वसम्मति का एल्गोरिथ्म अधिकांश निर्णयों के अर्थ पर आधारित है जो अधीनस्थों को देखते हैं।

प्रमेय: किसी भी मी के लिए , ओएम (एम) एल्गोरिथ्म 3 मी से अधिक जनरलों और अधिकतम एम गद्दारों के साथ आम सहमति तक पहुंचता है।

इसका मतलब यह है कि एल्गोरिथ्म आम सहमति तक पहुंच सकता है जबकि प्रतिभागियों के 2/3 ईमानदार हैं। यदि देशद्रोही 1/3 से अधिक हैं, तो आम सहमति नहीं हुई है, सेनाएं अपने हमलों का समन्वय नहीं कर सकती हैं, और दुश्मन जीत जाता है।

ओम एल्गोरिथ्म (0)

1. कमांडर अपने मूल्य को प्रत्येक अधीनस्थ को भेजता है।
2. प्रत्येक अधीनस्थ उस मूल्य का उपयोग करता है जो वह कमांडर से प्राप्त करता है, या यदि वह कोई मूल्य प्राप्त नहीं करता है तो DELAY का उपयोग करता है।

ओम एल्गोरिथ्म (एम), एम> 0

1. कमांडर प्रत्येक मातहत को अपने महत्व के साथ भेजता है।
2. प्रत्येक i के लिए, vi को वह मान होना चाहिए जो ith अधीनस्थ कमांडर से प्राप्त करता है, या RESET मूल्य का उपयोग किया जाएगा यदि अधीनस्थ को कोई मूल्य नहीं मिलता है। I-th अधीनस्थ, OM Algorithm (m-1) में एक कमांडर के रूप में कार्य करता है और शेष n-2 में से प्रत्येक के लिए एक मूल्य भेजता है।
3. प्रत्येक i के लिए, बशर्ते कि jii, vj को मान दें कि ith अधीनस्थ को jth अधीनस्थ से प्राप्त किया गया चरण (2) (OM Algorithm (m-1) का उपयोग करके), या मान का उपयोग करता है कोई मतलब नहीं है। Ith गुलाम बहुमत मूल्य (v1, ..., vn-1) का उपयोग करता है।

जब एम = 0 कोई गद्दार नहीं होते हैं, तो प्रत्येक अधीनस्थ आदेश का पालन करता है। एम> 0 के लिए, सभी अधीनस्थों के चुनाव के प्रमुख भाग से एक अधीनस्थ आय का प्रत्येक अंतिम विकल्प।
यदि आप दूसरे अधीनस्थ के दृष्टिकोण से स्थिति को देखते हैं तो यह स्पष्ट हो जाएगा - चलो C कमांडर हो, और L {i} i-th अधीनस्थ है।



OM (1): अधीनस्थ 3 एक देशद्रोही है। दूसरे अधीनस्थ के दृष्टिकोण से स्थिति।

कदम:

1. कमांडर सभी अधीनस्थों को वी भेजता है।
2. L1, L2 को v का मान भेजता है या L3, L2 को x का मान भेजता है।
3. L2 ← बहुमत (v, v, x) == v

अंतिम निर्णय L1, L2 और L3 के अधिकांश मतों से किया जाता है और परिणामस्वरूप आम सहमति बन जाती है।

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

आइए मामले को देखें जब कमांडर एक गद्दार हो।



OM (1): कमांडर एक गद्दार होता है।

कदम:

1. कमांडर क्रमशः L1, L2, L3 को x, y, z, के मान भेजता है;
2. L1 दास के लिए x का मान भेजता है L2, L3 | L2, L1, L3 को y का मान भेजता है L3 L1, L2 को z का मान भेजता है;
3. L1 ← बहुमत (x, y, z) | L2। सबसे (x, y, z) | L3 ← बहुमत (x, y, z)

इन सभी का मूल्य समान है, इसलिए आम सहमति है। ध्यान दें कि भले ही x, y, z के मान सभी भिन्न हों, बहुमत मान (x, y, z) सभी तीनों अधीनस्थों के लिए समान है। यदि x, y, z पूरी तरह से अलग आदेश हैं, तो हम मान सकते हैं कि वे डिफ़ॉल्ट योजना के अनुसार कार्य करेंगे - RESET।

7 जनरलों और 3 गद्दारों के साथ एक अधिक जटिल उदाहरण के लिए एक व्यावहारिक दृष्टिकोण को देखने के लिए, मेरा सुझाव है कि आप इस लेख को पढ़ें।

बीजान्टिन गलती सहिष्णुता

बीजान्टिन गलती सहिष्णुता एक विशेषता है जो एक प्रणाली को परिभाषित करती है जो असफलताओं के एक वर्ग को अनुमति देती है जो बीजान्टिन पीढ़ी कार्य से संबंधित है। बीजान्टिन विफलता विफलता के प्रकारों का सबसे जटिल वर्ग है। यह कोई प्रतिबंध नहीं लगाता है और एक नोड के पास किस तरह का व्यवहार हो सकता है, इसके बारे में कोई धारणा नहीं है (उदाहरण के लिए, एक नोड किसी भी मनमानी डेटा को उत्पन्न कर सकता है, एक ईमानदार भागीदार के रूप में प्रस्तुत करता है)।

बीजान्टिन त्रुटियों को ठीक करने के लिए सबसे कठिन हैं। विमान के इंजन सिस्टम में, परमाणु ऊर्जा संयंत्रों में और वस्तुतः किसी भी प्रणाली में बायज़ैन्टिन गलती की सहिष्णुता की आवश्यकता थी, जिनकी क्रियाएं बड़ी संख्या में सेंसर के परिणामों पर निर्भर करती हैं। यहां तक ​​कि स्पेसएक्स इसे अपने सिस्टम के लिए संभावित आवश्यकता के रूप में देखता है।

पिछले अनुभाग में उल्लिखित एल्गोरिथ्म बीजान्टिन गलती सहिष्णुता से मेल खाती है जब तक कि गद्दारों की संख्या सभी जनरलों के एक तिहाई से अधिक न हो। इस कार्य को सुविधाजनक बनाने के लिए अन्य विकल्प हैं, जिसमें डिजिटल हस्ताक्षर का उपयोग या साथियों के बीच संचार पर प्रतिबंधों की शुरूआत शामिल है।

यह सब ब्लॉकचेन से कैसे संबंधित है?

ब्लॉकचेन विकेंद्रीकृत एलईडीर हैं, जो परिभाषा के अनुसार, केंद्रीय प्राधिकरण द्वारा नियंत्रित नहीं हैं। उनमें संग्रहीत मूल्यों के कारण, हमलावरों के पास एक गलती की कोशिश करने और आरंभ करने के लिए एक अच्छा आर्थिक प्रोत्साहन है। फिर भी, बीजान्टिन गलती सहिष्णुता और, इसलिए, ब्लॉकचैन के लिए बीजान्टिन सामान्य समस्या का समाधान बस आवश्यक है।

बीजान्टिन दोष सहिष्णुता की अनुपस्थिति में, एक सहकर्मी ब्लॉकचेन की विश्वसनीयता को पूरी तरह से समाप्त करते हुए, झूठे लेनदेन को प्रसारित और प्रकाशित कर सकता है। मामलों को बदतर बनाने के लिए, कोई केंद्रीय प्राधिकरण नहीं है जो जिम्मेदारी ले सकता है और क्षति की मरम्मत कर सकता है।

जब बिटकॉइन का आविष्कार किया गया था, तो एक बड़ी सफलता बीजान्टिन जनरलों की समस्या के संभावित समाधान के साक्ष्य का उपयोग थी। इस ईमेल में सातोशी नाकामोतो द्वारा इसका विस्तार से वर्णन किया गया है।

निष्कर्ष

इस लेख में, हमने वितरित प्रणालियों में सर्वसम्मति की कुछ बुनियादी अवधारणाओं की जांच की।