ข้ามไปยังเนื้อหา
Financial Context Wiki

ปัญหานายพลไบแซนไทน์: การตกลงเมื่อได้รับข้อความขัดแย้งกัน

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

อัปเดต

จัดทำขึ้นเพื่อการศึกษาเท่านั้น ไม่ใช่คำแนะนำการลงทุน การลงทุนอาจทำให้สูญเสียเงินลงทุนได้

คำตอบโดยตรง

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

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

ในแบบจำลอง “ข้อความปากเปล่า” ของบทความ เมื่อมีผู้ทรยศได้ไม่เกิน m คน จะมีคำตอบก็ต่อเมื่อ n>3m ซึ่งเทียบเท่ากับ n>=3m+1 สำหรับจำนวนผู้เข้าร่วมที่เป็นจำนวนเต็ม แบบจำลองนี้สมมติว่าข้อความจากผู้ซื่อสัตย์ถูกส่งถึงอย่างถูกต้อง ผู้รับรู้ว่าใครส่งแต่ละข้อความ และตรวจพบการขาดหายของข้อความที่คาดไว้ได้ คำว่า “ปากเปล่า” หมายถึงเนื้อหาที่ไม่ผ่านการยืนยันสามารถถูกปลอมเป็นรายงานของผู้อื่นได้ ไม่ได้หมายความว่าผู้ส่งสารที่ไม่น่าเชื่อถือจะหายไปตลอดกาลโดยไม่มีใครตรวจพบ

แบบจำลอง “ข้อความลงลายมือชื่อ” เพิ่มลายมือชื่อที่ปลอมไม่ได้และตรวจสอบได้โดยสาธารณะ จึงเปลี่ยนผลด้านความทนทาน แต่ไม่ได้ทำให้เนื้อหาที่ลงนามเป็นความจริง รับประกันการส่ง แก้การยุติงานในระบบอะซิงโครนัสเต็มรูปแบบ ปกป้องกุญแจที่ถูกขโมย หรือพิสูจน์ความปลอดภัยของโปรโตคอลสมัยใหม่ ปัญหานายพลไบแซนไทน์ ปัญหานายพลสองคนหรือการโจมตีแบบประสานงาน FLP โปรโตคอล BFT Proof of Work และ Proof of Stake เกี่ยวข้องกันแต่เป็นคนละแบบจำลองหรือกลไก

วิธีวิเคราะห์

  1. กำหนดโจทย์การตกลง ระบุผู้เข้าร่วม อินพุต เอาต์พุต และคุณสมบัติการตกลง ความถูกต้อง และการยุติงานอย่างแม่นยำ สำหรับรูปแบบผู้บัญชาการให้เขียน IC1 และ IC2 โดยตรง แทนที่จะกล่าวเพียงว่า “บรรลุฉันทามติ”
  2. กำหนดตัวตนและช่องทาง ระบุว่าข้อความแบบจุดต่อจุดผ่านการยืนยันตัวตน ส่งถึงอย่างเชื่อถือได้ มีลำดับ ป้องกันการเล่นซ้ำ และระบุผู้ส่งได้หรือไม่ ตรวจพบการละเว้นได้หรือไม่ และการกระจายข้อความเป็นคำสั่งพื้นฐานหรือทำด้วยการส่งซ้ำหลายครั้ง
  3. กำหนดเวลา แยกความซิงโครนัสที่มีขอบเขตความล่าช้า ความซิงโครนัสบางส่วนหลังเวลาคงตัวที่ไม่ทราบล่วงหน้า และความอะซิงโครนัสเต็มรูปแบบ อย่าเพิ่มผู้ส่งสารที่หายไปในแบบจำลองหนึ่งแล้วใช้ทฤษฎีบทที่พิสูจน์ไว้สำหรับอีกแบบจำลอง
  4. กำหนดงบประมาณความขัดข้อง บันทึกจำนวนผู้เข้าร่วมทั้งหมด n จำนวนผู้เข้าร่วมแบบไบแซนไทน์สูงสุด m การยึดครองเป็นแบบคงที่หรือปรับตัว และความขัดข้องรวมการละเว้น การส่งข้อความขัดแย้ง การสมคบ การขโมยกุญแจ หรือช่องทางบกพร่องหรือไม่
  5. ติดตามข้อมูลแบบเวียนเกิด สำหรับผู้ซื่อสัตย์แต่ละคน ให้แจกแจงคำกล่าวอ้างโดยตรงและที่ส่งต่อ รวมถึงเส้นทางผู้ส่ง ค่าเริ่มต้นเมื่อข้อความหาย และกฎตัดสินกรณีเสมอที่แน่นอน เปรียบเทียบว่าสองคนแยกแยะอะไรได้จากมุมมองเฉพาะที่ของตน
  6. ตรวจทฤษฎีบทกับอัลกอริทึมร่วมกัน จับคู่ขอบเขตล่างและเงื่อนไขเพียงพอกับแบบจำลองปากเปล่าหรือลงลายมือชื่อ การเชื่อมต่อ และงบประมาณความขัดข้องที่ตรงกัน อสมการเกณฑ์เพียงอย่างเดียวไม่ใช่การติดตั้งหรือบทพิสูจน์
  7. จับคู่แบบจำลองกับการใช้งานจริง ตรวจกลไก OM(m) SM(m) หรือกลไกอื่นของโปรโตคอลที่ใช้งานจริง รวมถึงโดเมนข้อความ รอบ ล็อก ใบรับรอง การเปลี่ยนสมาชิก การหมดเวลา พฤติกรรมไคลเอนต์ กฎ finality และนโยบายยืนยันของแอปพลิเคชัน

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

ตัวอย่างพร้อมวิธีคิด

1. เหตุใดนายพลสามคนที่ใช้ข้อความปากเปล่าจึงทนผู้ทรยศหนึ่งคนไม่ได้

กำหนด n=3 และ m=1 เงื่อนไข n>3m กลายเป็น 3>3 ซึ่งเป็นเท็จ สมมติว่าผู้บัญชาการ A บอกนายทหาร B ว่า ATTACK และบอก C ว่า RETREAT ทาง B แยกไม่ได้ว่า A เป็นผู้ทรยศที่ออกคำสั่งขัดแย้ง หรือ C เป็นผู้ทรยศที่รายงานเท็จว่า A พูดอะไร ส่วน C ก็มีความไม่แน่นอนแบบสมมาตร

ตัวเลือกแบบแน่นอนใดที่รักษาคำสั่งของผู้บัญชาการซื่อสัตย์ในการทำงานคู่เทียบที่ A ซื่อสัตย์ อาจบังคับให้ B กับ C เลือกต่างกันในการทำงานที่ A ทรยศ การส่งต่อข้อความไม่ได้สร้างแหล่งอิสระที่สี่ จึงรับประกันทั้ง IC1 และ IC2 พร้อมกันไม่ได้

2. นายพลสี่คนที่ใช้ข้อความปากเปล่ากับผู้ทรยศหนึ่งคน

เมื่อใช้ OM(1) มี n=4 และ m=1 ผู้บัญชาการส่งคำสั่งให้นายทหารสามคน แต่ละคนส่งต่อค่าที่ได้รับให้อีกสองคน และผู้ซื่อสัตย์ทุกคนใช้กฎเสียงข้างมากกับค่าเริ่มต้นแบบเดียวกัน หากผู้บัญชาการซื่อสัตย์และส่ง v นายทหารซื่อสัตย์จะเห็นค่าอย่าง v v และ x ที่อาจมาจากผู้ทรยศ จึงเลือก v

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

3. ขอบเขตล่างทั่วไปของข้อความปากเปล่า

สำหรับ n=7 และ m=2 เงื่อนไข 7>6 เป็นจริง จึงผ่านข้อกำหนดด้านจำนวนผู้เข้าร่วม และโครงสร้างข้อความปากเปล่าแบบเวียนเกิดทนผู้ทรยศได้ไม่เกินสองคนภายใต้สมมติฐานของมัน สำหรับ n=6 ข้อความ 6>6 เป็นเท็จ สำหรับ n=10 และ m=3 เงื่อนไข 10>9 เป็นจริง การผ่านอสมการเป็นสิ่งจำเป็น แต่ยังต้องมีรอบ การส่งต่อ เสียงข้างมาก ค่าเริ่มต้น และช่องทางที่ถูกต้อง

4. ลายมือชื่อเปลี่ยนอะไร

ในตัวอย่างนายพลสามคนที่ใช้ SM(1) ผู้บัญชาการผู้ทรยศลงนาม ATTACK ให้ B และ RETREAT ให้ C นายทหารที่ซื่อสัตย์ส่งต่อคำสั่งลงนามทั้งสอง จึงได้ชุดเดียวกันคือ {ATTACK, RETREAT} และใช้ค่าเริ่มต้นที่กำหนดเหมือนกัน เช่น RETREAT การส่งข้อความขัดแย้งของผู้บัญชาการจึงมีหลักฐานระบุตัว

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

ความเสี่ยงและข้อผิดพลาดในการตรวจทาน

ปัญหาและแบบจำลอง

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

อัลกอริทึมและการติดตั้ง

  • ตรวจเพียงเสียงข้างมากสุดท้ายโดยไม่ติดตามเส้นทางผู้ส่งแบบเวียนเกิดและมุมมองเฉพาะที่ของผู้ซื่อสัตย์แต่ละคน
  • ใช้ค่าเริ่มต้นเมื่อข้อความหาย กฎตัดสินกรณีเสมอ ภาพสมาชิก หรือการเรียงข้อความต่างกันในแต่ละการติดตั้ง
  • รับข้อความโดยไม่ผูกกับโปรโตคอล เชน งาน ความสูง รอบ ค่า ผู้ส่ง และยุคสมาชิก
  • เล่นซ้ำหรือประกอบข้อความข้ามการทำงาน รอบ ฟอร์ก เครือข่าย หรือการเปลี่ยนสมาชิก
  • สมมติว่าลายมือชื่อพิสูจน์ความจริง ความใหม่ บริบทอำนาจ การส่ง ความพร้อมใช้ หรือการดูแลกุญแจอย่างซื่อสัตย์
  • อ้าง OM(m) หรือ SM(m) โดยไม่ติดตั้งรอบ การส่งต่อ การตรวจสอบ และการเชื่อมต่อที่กำหนด
  • ทดสอบตำแหน่งผู้ทรยศเพียงแบบเดียวแทนกรณีผู้บัญชาการ นายทหาร การสมคบ การละเว้น และการส่งข้อความขัดแย้ง

การใช้งานและการตีความ

  • อ้างว่าโปรโตคอลฉันทามติ “แก้ปัญหาไบแซนไทน์” โดยไม่ระบุสมมติฐานด้าน safety, liveness และเครือข่ายให้ชัด
  • ถือว่าการตกลงบนไบต์เป็นหลักฐานว่าการทำงานของแอปพลิเคชันหรือข้อเท็จจริงนอกเชนถูกต้อง
  • มองข้ามไคลเอนต์ ผู้ให้บริการ คลาวด์ ระบบกุญแจ หรือธรรมาภิบาลร่วมที่ทำให้ผู้เข้าร่วมซึ่งดูแยกกันมีความเสี่ยงสัมพันธ์กัน
  • ให้เครดิตเงินฝาก สร้างสินทรัพย์บริดจ์ หรือชำระการกระทำที่ย้อนกลับไม่ได้ก่อนผ่านเงื่อนไข finality
  • สรุปการกระจายศูนย์ ความปลอดภัยของสินทรัพย์ ความจริงทางกฎหมาย หรือมูลค่าโทเค็นจากป้ายกำกับความทนทานต่อความขัดข้อง

ความเข้าใจผิดที่พบบ่อย

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

หัวข้อที่เกี่ยวข้อง

แหล่งข้อมูล

การนำทาง

ค้นหาในวิกิ...