โพรโทคอล BFT: PBFT และ Tendermint

ปัญหานายพลไบแซนไทน์ซึ่ง Lamport, Shostak และ Pease ตั้งขึ้นในปี 1982 ตั้งคำถามว่า ระบบแบบกระจายจะบรรลุฉันทามติได้หรือไม่เมื่อผู้เข้าร่วมบางรายส่งข้อความขัดแย้งกัน ปัญหานี้ตั้งชื่อตามนายพลไบแซนไทน์ที่ต้องประสานงานกันเพื่อโจมตี แต่ในกลุ่มอาจมีผู้ทรยศที่ส่งคำสั่งขัดแย้งกัน ระบบจะทนต่อข้อผิดพลาดแบบไบแซนไทน์ (BFT) หากบรรลุฉันทามติที่ถูกต้องได้แม้มีโหนดประสงค์ร้ายมากถึง f โหนดจากทั้งหมด 3f+1 โหนด BFT ถือเป็นมาตรฐานสูงสุดสำหรับฉันทามติของบล็อกเชนที่ต้องรักษาความปลอดภัยภายใต้เงื่อนไขที่มีฝ่ายตรงข้าม

PBFT (Castro และ Liskov, 1999) เป็นโปรโตคอล BFT เชิงปฏิบัติชุดแรก ซึ่งแสดงให้เห็นว่า BFT สามารถทำงานได้อย่างมีประสิทธิภาพในระบบจริง PBFT ทำงานเป็นมุมมองหรือวาระ โดยแต่ละมุมมองมีโหนดหลักที่กำหนดไว้ การทำงานปกติมีสามระยะ ได้แก่ เตรียมล่วงหน้า โดยโหนดหลักกระจายคำขอจากไคลเอ็นต์และหมายเลขลำดับ เตรียมการ โดยโหนดจำลองกระจายความเห็นพ้องพร้อมลำดับ และยืนยัน โดยโหนดจำลองกระจายการยืนยันการยืนยัน คำขอจะถูกดำเนินการเมื่อโหนดจำลองรวบรวมข้อความยืนยันที่ตรงกันได้ 2f+1 ข้อความ PBFT ให้ทั้งความปลอดภัยและความมีชีวิต โดยมีเงื่อนไขว่าโหนดจำลองน้อยกว่า 1/3 เป็นไบแซนไทน์

ข้อจำกัดหลักของ PBFT คือความซับซ้อนของข้อความ O(n^2) ต่อคำขอ เนื่องจากโหนดจำลอง n โหนดแต่ละโหนดส่งข้อความไปยังโหนดอื่นทั้งหมดในระยะเตรียมการและยืนยัน สำหรับโหนดจำลอง 100 โหนด คำขอแต่ละรายการจะสร้างข้อความประมาณ 10,000 ข้อความ ทำให้ PBFT ไม่เหมาะกับชุดตัวตรวจสอบความถูกต้องขนาดใหญ่ ชุมชนวิจัย BFT ใช้เวลาสองทศวรรษในการปรับปรุงเรื่องนี้ โดย BFT-SMART ลดค่าคงที่ลง HotStuff ทำให้ความซับซ้อนของข้อความเป็นเชิงเส้นผ่านแบบจำลองที่ผู้นำเป็นตัวกลางส่งต่อ และ Tendermint ปรับแนวคิดของ PBFT ให้เหมาะกับการใช้งานบนบล็อกเชนสาธารณะ

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

Tendermint (2014, Kwon; ใช้งานจริงใน Cosmos ตั้งแต่ปี 2019) ปรับ PBFT ให้เหมาะกับสภาพแวดล้อมบล็อกเชนสาธารณะ Tendermint มีสามระยะต่อบล็อก ได้แก่ เสนอ โดยผู้นำกระจายบล็อกที่เสนอ ลงคะแนนเบื้องต้น โดยตัวตรวจสอบความถูกต้องลงคะแนนให้ข้อเสนอ และยืนยันล่วงหน้า โดยตัวตรวจสอบความถูกต้องลงคะแนนเพื่อยืนยันหลังเห็นคะแนนเบื้องต้น 2/3 บล็อกจะได้รับการยืนยันเมื่อตัวตรวจสอบความถูกต้องรวบรวมคะแนนยืนยันล่วงหน้าได้ 2/3 ซึ่งเป็นใบรับรององค์ประชุม ตัวตรวจสอบความถูกต้องจะผลัดกันเป็นผู้เสนอตามลำดับวนรอบ โดยถ่วงน้ำหนักด้วยเงินเดิมพัน หากรอบใดหมดเวลาโดยยังไม่มีการยืนยัน ตัวตรวจสอบความถูกต้องจะเลื่อนไปยังรอบถัดไปพร้อมลงคะแนนว่าง

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

กลไกสำคัญของ Tendermint คือการล็อกคะแนนเสียง เมื่อตัวตรวจสอบความถูกต้องส่งคะแนนยืนยันล่วงหน้าให้บล็อกหนึ่งในรอบ r ตัวตรวจสอบความถูกต้องนั้นจะถูกล็อกไว้กับบล็อกดังกล่าว ในรอบถัดมา ตัวตรวจสอบความถูกต้องที่ถูกล็อกจะลงคะแนนเบื้องต้นได้เฉพาะบล็อกที่ตนล็อกไว้ หรือใช้คะแนนว่างหากได้รับหลักฐานว่าบล็อกนั้นไม่ได้รับการยืนยัน กลไกนี้ป้องกันการยืนยันบล็อกที่ขัดแย้งกันในรอบต่าง ๆ ตัวตรวจสอบความถูกต้องจะปลดล็อกได้ก็ต่อเมื่อได้รับการรับรองแบบโพลกา ซึ่งคือคะแนนเบื้องต้น 2/3 สำหรับบล็อกอื่นในรอบถัดมา และหลักฐานนั้นแสดงว่าบล็อกเดิมไม่ได้รับการยืนยัน

การสื่อสารระหว่างบล็อกเชนของ Cosmos (IBC) อาศัยการยืนยันขั้นสุดท้ายทันทีของ Tendermint สำหรับการโอนข้ามบล็อกเชน ไคลเอ็นต์แบบเบาของ Tendermint ติดตามชุดตัวตรวจสอบความถูกต้องและการยืนยันล่าสุด ซึ่งประกอบด้วยส่วนหัวบล็อกพร้อมลายเซ็นยืนยันล่วงหน้า 2/3 หากต้องการตรวจสอบแพ็กเก็ตจากบล็อกเชน A โมดูล IBC ของบล็อกเชน B จะตรวจสอบใบรับรององค์ประชุมว่า ตัวตรวจสอบความถูกต้อง 2/3 ของบล็อกเชน A ได้ลงนามในส่วนหัวบล็อกที่เกี่ยวข้อง การรักษาความปลอดภัยของ IBC จึงขึ้นอยู่กับการรับประกัน BFT ของ Tendermint การโอนข้ามบล็อกเชนจะถือเป็นที่สิ้นสุดทันทีที่บล็อกต้นทางได้รับการยืนยัน

HotStuff (Yin และคณะ, 2018 เป็นพื้นฐานของ LibraBFT/DiemBFT ของ Facebook และปัจจุบันใช้ใน Aptos และ Sui) ทำให้ความซับซ้อนของข้อความต่อรอบฉันทามติเป็น O(n) โดยใช้โทโพโลยีรูปดาว ตัวตรวจสอบความถูกต้องทั้งหมดส่งคะแนนไปยังผู้นำ ผู้นำรวมคะแนนเป็นลายเซ็นตามเกณฑ์ (QC หรือใบรับรององค์ประชุม) แล้วกระจาย QC HotStuff ใช้การออกแบบการเชื่อมโยงสามระยะ โดยการพิสูจน์ความปลอดภัยครอบคลุม QC ที่ต่อเนื่องกันสามรายการ ทำให้ประมวลผลหลายระยะต่อเนื่องได้ ความซับซ้อนเชิงเส้นทำให้ HotStuff เหมาะกับตัวตรวจสอบความถูกต้อง 100–300 ราย ซึ่งมีการใช้งานใน Aptos และ Sui

บล็อกเชนสำหรับองค์กร เช่น Hyperledger Fabric, Besu และ Quorum ใช้ฉันทามติ BFT กับเครือข่ายที่มีสิทธิ์เข้าร่วม ซึ่งทราบตัวตนของตัวตรวจสอบความถูกต้อง บริการจัดลำดับของ Hyperledger Fabric ที่ใช้ Raft ให้ความทนทานต่อข้อผิดพลาดจากการหยุดทำงาน แต่ไม่ใช่ข้อผิดพลาดแบบไบแซนไทน์ สำหรับกลุ่มพันธมิตรที่เชื่อถือกัน Fabric มีเป้าหมายในระยะสำคัญด้าน BFT ที่จะนำ SmartBFT ซึ่งเป็นการใช้งานในรูปแบบคลังโปรแกรมมาใช้ R3 Corda ใช้กลุ่มโหนดรับรองร่วมกับ BFT-SMART เพื่อป้องกันการใช้จ่ายซ้ำ การเลือกระหว่าง CFT กับ BFT สะท้อนสมมติฐานด้านความไว้วางใจ หากตัวตรวจสอบความถูกต้องอาจเป็นฝ่ายตรงข้าม ก็จำเป็นต้องใช้ BFT แต่หากเพียงไม่น่าเชื่อถือและอาจหยุดทำงาน CFT ก็เพียงพอ

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

ในโปรโตคอล BFT มาตรฐาน ตัวตรวจสอบความถูกต้องสามารถเป็นไบแซนไทน์ได้มากที่สุดในสัดส่วนเท่าใด โดยที่ยังคงรักษาความปลอดภัยไว้ได้

โปรโตคอล BFT รับประกันฉันทามติได้แม้มีตัวตรวจสอบความถูกต้องประสงค์ร้ายมากถึง 1/3 PBFT (1999) พิสูจน์ว่า BFT ใช้งานได้จริง แต่มีความซับซ้อนของข้อความ O(n^2) Tendermint ปรับ PBFT ให้เหมาะกับบล็อกเชน โดยมีการยืนยันขั้นสุดท้ายทันทีและการล็อกคะแนนเสียง HotStuff ทำให้ความซับซ้อนเป็น O(n) ผ่านใบรับรององค์ประชุมที่ใช้ลายเซ็นตามเกณฑ์ และมีการใช้งานใน Aptos กับ Sui Cosmos IBC ใช้การยืนยันขั้นสุดท้ายทันทีของ Tendermint เพื่อการโอนข้ามบล็อกเชนที่ตรวจสอบแล้ว บล็อกเชนสำหรับองค์กรใช้ BFT-SMART หรือ Raft โดยขึ้นอยู่กับว่าคาดว่าจะเกิดข้อผิดพลาดแบบไบแซนไทน์หรือเพียงข้อผิดพลาดจากการหยุดทำงาน