ความทนทานต่อความผิดพร่องแบบไบแซนไทน์

ความทนทานต่อความผิดพร่องแบบไบแซนไทน์คือการศึกษาเกี่ยวกับการบรรลุข้อตกลงเมื่อกระบวนการบางอย่างอาจล้มเหลวโดยพลการ รวมถึงการส่งข้อความที่ขัดแย้งกันหรือข้อความที่เป็นอันตราย

Definition

ความผิดพร่องแบบไบแซนไทน์คือการเบี่ยงเบนโดยพลการจากข้อกำหนดของส่วนประกอบ รวมถึงพฤติกรรมที่เป็นอันตราย ความทนทานต่อความผิดพร่องแบบไบแซนไทน์คือความสามารถของโปรโตคอลแบบกระจายในการตอบสนองเงื่อนไขความถูกต้อง แม้จะมีผู้เข้าร่วมที่ผิดพลาดจำนวนจำกัด

Scope

หัวข้อนี้ครอบคลุมปัญหาแม่ทัพไบแซนไทน์และขอบเขตความยืดหยุ่นที่กำหนดไว้ (อย่างน้อย 3f+1 กระบวนการ หรือข้อความที่ลงนาม เพื่อทนทานต่อความผิดพร่องโดยพลการ f ครั้ง) อัลกอริทึมข้อตกลงข้อความแบบปากเปล่าและแบบลงนามที่ซิงโครนัส และโปรโตคอลความทนทานต่อความผิดพร่องแบบไบแซนไทน์แบบอะซิงโครนัสที่ใช้งานได้จริง เช่น PBFT และโปรโตคอลที่พัฒนาต่อยอดจาก PBFT ซึ่งเป็นพื้นฐานของแบบจำลองความน่าเชื่อถือของบล็อกเชนแบบอนุญาต (permissioned blockchains) และบริการจำลองแบบที่มีความสมบูรณ์สูง

Core questions

• ต้องมีกระบวนการที่ถูกต้องกี่กระบวนการจึงจะสามารถทนทานต่อความผิดพร่องโดยพลการที่กำหนดได้?
• ลายเซ็นดิจิทัลเปลี่ยนแปลงขอบเขตความยืดหยุ่นสำหรับข้อตกลงแบบไบแซนไทน์อย่างไร?
• จะทำให้ข้อตกลงแบบไบแซนไทน์มีประสิทธิภาพเพียงพอสำหรับระบบอะซิงโครนัสที่ใช้งานได้จริงได้อย่างไร?

Key theories

ขอบเขตแม่ทัพไบแซนไทน์

ด้วยข้อความที่ไม่ได้ตรวจสอบสิทธิ์ (แบบปากเปล่า) ข้อตกลงแบบไบแซนไทน์สามารถแก้ไขได้ก็ต่อเมื่อกระบวนการมากกว่าสองในสามถูกต้อง (n > 3f) ข้อความที่ตรวจสอบสิทธิ์ด้วยลายเซ็นที่ไม่สามารถปลอมแปลงได้จะช่วยผ่อนคลายข้อกำหนดนี้

การจำลองแบบ BFT ที่ใช้งานได้จริง

PBFT แสดงให้เห็นว่าข้อตกลงแบบไบแซนไทน์สามารถทำงานในระบบกึ่งซิงโครนัส (partially synchronous system) ด้วยการจำลองแบบสถานะเครื่อง (state-machine replication) โดยใช้ตัวหลัก (primary) และโปรโตคอลสามขั้นตอน ซึ่งทำให้ได้ประสิทธิภาพที่ใช้งานได้จริงในขณะที่ทนทานต่อการจำลองแบบที่ผิดพลาดได้ถึงหนึ่งในสาม

อัลกอริทึมข้อตกลงแบบซิงโครนัส

ในแบบจำลองซิงโครนัส อัลกอริทึมข้อความแบบปากเปล่าและข้อความแบบลงนามแบบวนซ้ำสามารถบรรลุข้อตกลงได้ใน f+1 รอบ ซึ่งแสดงให้เห็นถึงต้นทุนความซับซ้อนของรอบในการทนทานต่อความผิดพร่องโดยพลการ

Clinical relevance

ความทนทานต่อความผิดพร่องแบบไบแซนไทน์เป็นรากฐานของระบบที่ต้องทนทานต่อการล่มเหลว การถูกบุกรุก หรือพฤติกรรมที่เป็นอันตราย รวมถึงบล็อกเชนแบบอนุญาต บริการจำลองแบบที่มีความมั่นใจสูง และการควบคุมการบินและอวกาศที่ไม่อาจตัดความเป็นไปได้ของการล้มเหลวของส่วนประกอบโดยพลการได้

History

Pease, Shostak และ Lamport ได้กำหนดขอบเขตข้อตกลงในปี 1980 และนำเสนอในรูปแบบที่น่าสนใจเป็นปัญหาแม่ทัพไบแซนไทน์ในปี 1982 เป็นเวลาเกือบสองทศวรรษที่ข้อตกลงแบบไบแซนไทน์ถูกมองว่ามีค่าใช้จ่ายสูงเกินไปสำหรับการใช้งานจริง จนกระทั่ง Castro และ Liskov ได้แสดงให้เห็นถึงการจำลองแบบไบแซนไทน์แบบอะซิงโครนัสที่มีประสิทธิภาพด้วย PBFT ในปี 1999 ซึ่งเป็นการฟื้นฟูสาขาวิชานี้และต่อมาได้เป็นข้อมูลในการพัฒนาฉันทามติของบล็อกเชน

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

เหตุใดการทนทานต่อความผิดพร่องแบบไบแซนไทน์ f ครั้งจึงต้องใช้กระบวนการ 3f+1?

กระบวนการที่ถูกต้องจะต้องบรรลุการตัดสินใจด้วยเสียงข้างมาก แม้ว่ากระบวนการที่ผิดพลาด f กระบวนการจะโกหก และอีก f กระบวนการอาจทำงานช้าหรือไม่สามารถเข้าถึงได้ เฉพาะเมื่อมีจำนวนกระบวนการมากกว่าสามเท่าของกระบวนการที่ผิดพลาดเท่านั้น เสียงข้างมากที่ถูกต้องจึงจะสามารถเอาชนะการรวมกันของผู้เข้าร่วมที่ผิดพลาดและล่าช้าได้เสมอ