Byzantine Generals Problem

कल्पना कीजिए कि किसी शहर के चारों ओर सैनिक टुकड़ियाँ हैं। उन्हें साथ हमला करना है या साथ पीछे हटना है; बिखरी कार्रवाई विनाशकारी हो सकती है। कमांडर आदेश भेजता है, लेकिन कोई विश्वासघात करके अलग-अलग लोगों को अलग बात बता सकता है। भरोसेमंद भागीदार आखिर एक जैसा कदम कैसे उठाएँ? यह किसी असली ऐतिहासिक युद्ध का वर्णन नहीं, बल्कि एक जैसे रिकॉर्ड रखने वाले कंप्यूटरों को समझाने का उदाहरण है। मसलन, कई सर्वरों, यानी साझा सेवा चलाने वाले कंप्यूटरों को, समान रूप से तय करना है कि कोई भुगतान पहले ही संसाधित हुआ है या नहीं। कोई जवाब मिल जाना पर्याप्त नहीं: जवाबों को एक साझा निर्णय तक पहुँचाना होगा। [1] [9]

Leslie Lamport, Robert Shostak और Marshall Pease ने विफलताओं के बीच सहमति पर अपने 1980 के काम के बाद जुलाई 1982 में यह प्रसिद्ध रूप प्रस्तुत किया। कहानी का गद्दार ऐसे घटक का प्रतीक है जिसका व्यवहार अब अनुमान के योग्य नहीं है। कंप्यूटर सिर्फ बंद ही नहीं होता। वह एक पड़ोसी को सही और दूसरे को गलत जवाब दे सकता है, संदेश छोड़ सकता है या कुछ और देखने का दावा कर सकता है। कारण हमला या प्रोग्राम की गलती हो सकता है। बाइज़ेंटाइन विफलता दूसरों को दिखने वाला व्यवहार बताती है, मशीन की मंशा नहीं। BFT (Byzantine Fault Tolerance) का अर्थ तय शर्तों में इस तरह के व्यवहार को सहने की क्षमता है। [1] [2]

मूल समस्या की दो शर्तें हैं। IC1 कहती है कि सभी भरोसेमंद अधीनस्थ एक ही आदेश स्वीकार करें। IC2 जोड़ती है कि अगर कमांडर भी भरोसेमंद है, तो वे उसी का वास्तविक आदेश स्वीकार करें। दूसरी शर्त न हो तो ‘हमेशा पीछे हटो’ समाधान लगेगा, लेकिन वह ईमानदार कमांडर की अनदेखी करेगा। कंप्यूटर प्रणालियाँ सुरक्षा, यानी विरोधी नतीजे रोकना, और प्रगति की क्षमता, यानी किसी नतीजे तक पहुँचना, अलग मानती हैं। अन्य नियम बताते हैं कि कौन-से नतीजे मान्य हैं। रिकॉर्ड एक जैसा होना अपने आप में इस बात का प्रमाण नहीं कि दर्ज किया गया दावा बाहरी दुनिया में सच था। [1] [9]

कमांडर को A और अधीनस्थों को B तथा C कहें। C को A से हमले का आदेश मिलता है, पर B कहता है कि कमांडर ने पीछे हटने को कहा। क्या B झूठ बोल रहा है या A ने दोनों को अलग आदेश दिए? आगे भेजे जाने पर भी जाँचे जा सकने वाले हस्ताक्षर के बिना C शायद दोनों स्थितियाँ अलग न कर पाए। B को भी यही अनिश्चितता हो सकती है। दोनों हमेशा कमांडर की मानें तो बेईमान A उन्हें बाँट सकता है; हमेशा अनदेखी करें तो ईमानदार कमांडर वाली शर्त टूटती है। इसलिए तीन भागीदारों और एक संभावित गद्दार वाली इस समस्या में बिना हस्ताक्षर हमेशा सफल होने वाली प्रक्रिया नहीं है। कमी स्थितियाँ अलग करने वाली जानकारी की है, तेज कंप्यूटरों की नहीं। [1] [9]

बिना हस्ताक्षर वाले पारंपरिक मॉडल में अधिकतम m गद्दारों को सहने के लिए कम से कम n ≥ 3m+1 भागीदार चाहिए: एक के लिए चार। यहाँ n भागीदारों की कुल संख्या है और m गद्दारों की वह अधिकतम संख्या, जिसे प्रणाली को सहना है। इसका मतलब सिर्फ एक वोट जोड़कर एक बार बहुमत गिनना नहीं है। OM(m) में भागीदार बार-बार सुनी हुई बात आगे भेजते और साझा नियमों से संदेश परखते हैं; आधार OM(0) कमांडर का मान या पहले से तय वैकल्पिक मान अपनाता है। मॉडल ज्ञात भागीदारों, सीधे संपर्क, भेजे संदेश की सही डिलीवरी, तत्काल भेजने वाले की पहचान और गायब संदेश पहचानने की क्षमता मानता है। इसलिए ‘बिना हस्ताक्षर’ का मतलब ‘स्रोत की कोई पुष्टि नहीं’ नहीं है। इन मान्यताओं के बिना चार की संख्या कुछ नहीं सुनिश्चित करती। [1] [9]

जाँचे जा सकने वाले डिजिटल हस्ताक्षर, Digital Signature, से B दिखा सकता है कि कमांडर ने वास्तव में क्या हस्ताक्षरित किया था। प्रोग्राम निजी कुंजी, यानी एक गुप्त संख्यात्मक मान, से यह हस्ताक्षर बनाता है। बाकी लोग निजी कुंजी जाने बिना उससे जुड़ी सार्वजनिक कुंजी से हस्ताक्षर जाँच सकते हैं। गद्दार भरोसेमंद भागीदार का आदेश चुपके से बदल या उसका हस्ताक्षर बना नहीं सकता। हस्ताक्षरित संदेशों का एल्गोरिदम हस्ताक्षरित मान फैलाता और एक साझा चयन नियम अपनाता है। इस मॉडल में ऊपर बताई ईमानदार बहुमत की जरूरत हटती है, लेकिन हस्ताक्षर नकल न किए जा सकने, डिलीवरी और दौरों के समय की शर्तें रहती हैं। Dolev और Strong का 1983 का काम जरूरी दौरों की संख्या को आगे जाँचता है। मान्य हस्ताक्षर भी सामग्री सच होने या संदेश समय पर पहुँचने की गारंटी नहीं देता। वह यह भी साबित नहीं करता कि निजी कुंजी चोरी नहीं हुई है। हस्ताक्षर किसी संदेश का स्रोत बताता है, भेजने वाले की हर बात पर भरोसे का प्रमाण नहीं देता। [1] [3]

सर्वर जवाब न दे तो बाकी नहीं जानते कि वह बंद हो गया या उसका संपर्क बहुत धीमा है। Michael Fischer, Nancy Lynch और Michael Paterson द्वारा 1985 में प्रकाशित FLP परिणाम इस अनिश्चितता को सटीक करता है। यहाँ प्रक्रिया से मतलब चल रहे प्रोग्राम से है। निर्धारक तरीका एक जैसी अवस्था और इनपुट पर वही अगला कदम उठाता है; वह कदम को बेतरतीब ढंग से नहीं चुनता। पूरी तरह असमकालिक प्रणाली में, जहाँ विलंब की कोई ज्ञात ऊपरी सीमा नहीं है, निर्धारक प्रक्रिया हर अनुमत निष्पादन में सहमति पूरी होने की गारंटी नहीं दे सकती, अगर एक प्रक्रिया भी रुककर विफल हो सकती हो। विश्वसनीय डिलीवरी लेकिन असीमित विलंब की स्थिति में भी यह सही है। इसका मतलब यह नहीं कि सहमति कभी बनती ही नहीं। व्यावहारिक प्रणालियाँ समय की मान्यताएँ, उपयुक्त विफलता पहचानकर्ता या यादृच्छिकता जोड़ती हैं। नेटवर्क बँट जाए तो विरोधी नतीजों की पुष्टि से बेहतर इंतजार करना हो सकता है। [4] [13] [8]

Miguel Castro और Barbara Liskov ने 1999 में कई ज्ञात प्रतियों पर चलने वाली सेवा के लिए Practical Byzantine Fault Tolerance, PBFT, बताया। ये प्रतियाँ अलग-अलग सर्वरों पर वही सेवा चलाती हैं और लगातार उन्हीं अनुरोधों को संसाधित करती हैं। ये बाद में काम आने के लिए रखी बैकअप फ़ाइलें नहीं हैं। आधार विन्यास n = 3f+1 में f खराब प्रतियाँ सहन होती हैं। चार सर्वरों में एक बाइज़ेंटाइन हो सकता है; तीन-तीन के दो समूहों में कम से कम दो सर्वर साझा होंगे, जिनमें कम से कम एक भरोसेमंद होगा। जरूरी अनुमोदनों के इस समूह को कोरम कहते हैं। सिर्फ साझा सदस्य काफी नहीं: चरणों और नेतृत्व बदलने के नियम भी जरूरी हैं। अधिक सटीक रूप से prepared स्थिति के लिए अनुरोध, pre-prepare संदेश और मुख्य प्रति के अलावा अलग-अलग प्रतियों से आए 2f मेल खाते prepare चाहिए। स्थानीय पुष्टि के लिए 2f+1 commit संदेश भी चाहिए, जिनमें अपना संदेश शामिल हो सकता है। स्रोत की पुष्टि, क्रम संख्या और जाँच-बिंदु जालसाजी, दोहराव और रिकॉर्ड के अनियंत्रित विस्तार से निपटते हैं। सुरक्षा समय सीमा पर निर्भर नहीं करती, लेकिन काम आगे बढ़ने के लिए विलंब पर अतिरिक्त शर्तें चाहिए। [5] [10] [11] [12]

Bitcoin के पास सर्वरों की पहले से बंद सूची नहीं है। हर नए खाते को एक वोट मिले तो हमलावर बहुमत बना सकता है: यह Sybil Attack है। इसलिए Proof of Work ब्लॉक बनाने को गणनात्मक काम से जोड़ता है। ब्लॉक लेनदेन का एक समूह है, जिसे साझा इतिहास में जोड़ा जाता है। Full Node, यानी नियमों की स्वतंत्र जाँच करने वाला प्रोग्राम चलाता कंप्यूटर, पहले अमान्य ब्लॉक अस्वीकार करता और फिर मान्य शाखाओं में सबसे अधिक संचित काम वाली शाखा अपनाता है। Bitcoin OM या PBFT नहीं चलाता; अस्थायी शाखाएँ उसके काम का हिस्सा हैं। पर्याप्त ईमानदार गणना शक्ति और उचित संचार शर्तों में अतिरिक्त पुष्टियाँ इतिहास बदलने का जोखिम घटाती हैं, लेकिन पूर्ण अपरिवर्तनीयता नहीं देतीं। Bitcoin Backbone शोध इन्हीं शर्तों को जाँचता है: इतिहास का मेल, श्रृंखला का बढ़ना और ईमानदार भागीदारों द्वारा बनाए जा सकने वाले ब्लॉकों का हिस्सा। [6] [7]

‘नेटवर्क सहमति बनाता है’ सुनें तो ठोस सवाल पूछें: कौन भाग ले सकता है, हमलावर क्या नियंत्रित कर सकता है, संदेश कितनी देर से पहुँच सकते हैं और फैसला कब बदल सकता है? Proof of Work भी हर समस्या नहीं हटाता। Eclipse Attack नोड को ईमानदार साथियों से अलग करता है, सेंसरशिप लेनदेन छोड़ती है और Selfish Mining में निकाले हुए ब्लॉक रोककर रखे जाते हैं। सॉफ्टवेयर त्रुटियाँ और पर्याप्त हमलावर शक्ति से इतिहास का हिस्सा बदलने की संभावना भी रहती है। फिर भी बहुमत गणना शक्ति सही चल रहे Full Node को उसके नियम तोड़ने वाला ब्लॉक मानने पर मजबूर नहीं करती। जनरलों की कहानी तकनीक के नाम पर भरोसा करने के बजाय सहमति की शर्तें पूछना सिखाती है। [6] [7] [8]