Byzantine Generals Problem

Lamport, Shostak और Pease ने प्रतिकृत कंप्यूटर प्रणाली की पारस्परिक संगति समझाने के लिए जुलाई 1982 में ACM TOPLAS में सैन्य रूपक प्रकाशित किया। अलग-अलग जनरलों को एक योजना चुननी है, जबकि एक या अधिक गद्दार अलग प्राप्तकर्ताओं को अलग बातें बता सकते हैं। बाइज़ैन्टाइन दोष प्रक्रिया के बंद होने से व्यापक है: दोषपूर्ण घटक झूठ बोल सकता है, विरोधी मान भेज सकता है, संदेश रोक सकता है या प्रणाली के केवल कुछ हिस्सों को सही दिखाई दे सकता है। [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

लेख दो आवश्यकताएँ अलग करता है। IC1: सभी वफादार सहायक सेनापति एक ही आदेश का पालन करें। IC2: यदि प्रधान सेनापति वफादार है, तो हर वफादार सहायक उसके भेजे आदेश का पालन करे। आधुनिक सहमति में संबंधित गुणों को सहमति या सुरक्षा, वैधता और समाप्ति या प्रगति कहा जाता है। इनके अर्थ के लिए नेटवर्क मॉडल, प्रमाणीकरण और अधिकतम दोष संख्या स्पष्ट करना आवश्यक है। [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

मौखिक संदेश मॉडल में प्राप्तकर्ता सीधे प्रेषक को पहचानता है, संदेश की अनुपस्थिति पहचानी जा सकती है और हर प्रक्रिया-जोड़ी संवाद कर सकती है; फिर भी गद्दार अलग लोगों को अलग मान भेज सकता है। OM(m) अन्य सहायकों के माध्यम से मानों को पुनरावर्ती ढंग से आगे भेजता है और नियतात्मक बहुमत लगाता है। बिना हस्ताक्षरों के m बाइज़ैन्टाइन प्रक्रियाएँ सहने के लिए कम से कम 3m+1 प्रतिभागी चाहिए, अर्थात दो-तिहाई से अधिक वफादार हों। तीन प्रक्रियाएँ एक गद्दार नहीं सह सकतीं, क्योंकि वफादार प्राप्तकर्ता झूठे प्रधान और झूठे साथी में अंतर नहीं कर सकता। [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]

अजाली हस्ताक्षर विरोधी मानों का प्रसार उजागर करता है और गद्दार किसी वफादार प्रतिभागी का हस्ताक्षरित आदेश बदल नहीं सकता। Lamport का हस्ताक्षरित संदेश एल्गोरिदम पहले न देखे गए हस्ताक्षरित मान आगे भेजता है और संकलित समुच्चय पर समान नियतात्मक निर्णय करता है। लेख की आदर्श धारणाओं में गद्दारों की किसी भी संख्या को सहा जा सकता है। लेकिन हस्ताक्षर स्रोत प्रमाणित करता है, सामग्री की सत्यता, समय पर वितरण या चोरी हुई कुंजी की ईमानदारी नहीं। Dolev और Strong ने बाद में प्रमाणित सहमति और चरण संख्या की सीमाएँ अधिक सटीक कीं। [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]

प्रगति की गारंटी समय संबंधी धारणाओं पर निर्भर करती है। 1985 का Fischer–Lynch–Paterson परिणाम बताता है कि पूरी तरह अतुल्यकालिक नियतात्मक संदेश प्रणाली में केवल एक प्रक्रिया के बंद हो सकने पर भी ऐसा अनुमत निष्पादन मौजूद होता है जिसमें सहमति पूरी नहीं होती। FLP यह नहीं कहता कि वास्तविक प्रणालियाँ कभी सहमत नहीं होतीं। प्रगति की गारंटी के लिए अतिरिक्त धारणाएँ चाहिए, जैसे अंततः लागू होने वाली समय सीमाएँ या निश्चित गुणों वाला दोष पहचान तंत्र, अथवा यादृच्छिक प्रोटोकॉल अपनाना। केवल नेता नियुक्त करना पर्याप्त नहीं है। नेटवर्क के लंबे विभाजन में सुरक्षित प्रोटोकॉल कार्यों को पूरा करना रोक सकता है। [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]

Miguel Castro और Barbara Liskov का 1999 का PBFT बाइज़ैन्टाइन सहमति को प्रतिकृत अवस्था मशीन में बदलता है। मूल विन्यास n = 3f+1 में यह f बाइज़ैन्टाइन प्रतिकृतियों को सहता है। तैयार अवस्था में प्राथमिक प्रतिकृति का pre-prepare और उससे मेल खाते 2f prepare संदेश शामिल होते हैं; स्थानीय पुष्टि के लिए तैयार अवस्था और मेल खाते 2f+1 commit संदेश चाहिए। गणपूर्तियों के प्रतिच्छेद और दृश्य परिवर्तन के नियम विरोधी पुष्टियों को रोकते हैं। प्रमाणीकरण, क्रम संख्याएँ, जाँच बिंदु और दृश्य परिवर्तन जालसाजी, पुनर्प्रेषण, अभिलेख वृद्धि और दोषपूर्ण नेता से निपटते हैं। ज्ञात प्रतिकृति समूह और नियतात्मक अंतिमता खुली Proof of Work प्रणाली से अलग हैं। [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]

Bitcoin OM या PBFT नहीं चलाता और नामित नोडों की गिनती नहीं करता। Sybil हमलों का प्रतिरोध करने वाला Proof of Work प्रतिस्पर्धी इतिहासों को संचित कार्य से भार देता है। प्रत्येक Full Node सहमति नियम तोड़ने वाले ब्लॉक स्वतंत्र रूप से अस्वीकार करता है और सबसे अधिक संचित कार्य वाली वैध शृंखला अपनाता है। अस्थायी शाखाएँ अपेक्षित हैं। ईमानदार कार्य की प्रधानता और संचार की धारणाओं के अंतर्गत पुष्टि की गहराई के साथ पुनर्लेखन की संभावना घटती है, लेकिन यह गणितीय अपरिवर्तनीयता नहीं है। Bitcoin Backbone मॉडल हमलावर के कार्य अनुपात और नेटवर्क परिस्थितियों को स्पष्ट करके साझा उपसर्ग, शृंखला वृद्धि और शृंखला गुणवत्ता को औपचारिक बनाता है। [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]

यह कहना कि Bitcoin ने बाइज़ैन्टाइन जनरलों की समस्या हल कर दी, मॉडल में बदलाव छिपाने वाला संक्षेप है। शास्त्रीय सहमति ज्ञात पहचानों के स्थिर समूह और दोष सीमा f से शुरू होती है; Bitcoin बदलते छद्मनाम वाले प्रतिभागियों और बाहरी दुर्लभ संसाधन को स्वीकार करता है। इसकी गारंटियों को फिर भी संदेश वितरण की ठोस धारणाएँ चाहिए। Proof of Work Sybil पहचानों का प्रभाव सीमित करता है, लेकिन एक्लिप्स हमले, सेंसरशिप, स्वार्थी खनन, सॉफ़्टवेयर त्रुटियाँ या बहुमत हैशरेट द्वारा पुनर्गठन नहीं रोकता। खतरे के मॉडल में हमलावर, समय, सदस्यता और अंतिमता तय होने चाहिए; केवल BFT नाम पर्याप्त नहीं है। [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]