การเปรียบเทียบขั้นสุดท้ายและความมีชีวิตชีวาของอัลกอริทึมที่สอดคล้องกันต่างๆ

BFTF技术社区联盟

特邀专栏作者

2018-10-19 03:13

บทความนี้มีประมาณ 4814 คำ การอ่านทั้งหมดใช้เวลาประมาณ 7 นาที

อย่าเสียเวลาไปกับการออกแบบอัลกอริทึมที่สอดคล้องกันสำหรับเครือข่ายแบบอะซิงโครนัสอย่าง

ผู้เขียนต้นฉบับ: Soul Machine

เนื่องจากหลักการ FLP Imposibility

No completely asynchronous consensus protocol can tolerate even a single unannounced process death

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

ตารางที่ 1 การเปรียบเทียบอัลกอริธึมฉันทามติต่างๆ

เนื้อหาของตารางด้านบนมีรายละเอียดอธิบายด้านล่าง

Finality

Finality ดูคล้ายกับ Safety, Consistency แต่ดูเหมือนว่าจะต่างกันซึ่งสร้างความสับสนอย่างมาก

เพื่อความเข้าใจง่ายๆ คุณสามารถคิดได้ว่า Finality, Safety, and Consistency เป็นคำพ้องความหมาย นั่นคือ Finality=Safety=Consistency

เพื่อความเข้าใจที่ลึกซึ้งยิ่งขึ้น ฉันคิดว่า Finality นั้นซับซ้อน Finality>Safety>Consistency ความสอดคล้องใช้ได้กับระบบแบบกระจายทั้งหมด รวมถึงสภาพแวดล้อมที่เชื่อถือได้ เช่น Hadoop และสภาพแวดล้อมที่ไม่น่าเชื่อถือ เช่น Bitcoin ความปลอดภัยใช้ได้กับสภาพแวดล้อมไบแซนไทน์ Finality เป็นคำในสถานการณ์บล็อกเชน และบล็อกเชนเป็นชุดย่อยของสถานการณ์ไบแซนไทน์ (ปัญหาไบแซนไทน์ไม่มี -โซลูชั่นบล็อกเชนนอกเหนือจากบล็อกเชน) ความสอดคล้องคือ C ในทฤษฎี CAP ซึ่งกว้างกว่าและต้องการข้อกำหนดน้อยกว่า Finality ตอนจบมีความหมายมากกว่าความสอดคล้อง Finality มีความหมายทั้งหมดดังต่อไปนี้:

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

โดยสรุป Finality=Consistency + Safety + Immutability

Liveness

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

ตัวอย่างเช่น Tendermint เป็นประเภทนี้ เสียสละความมีชีวิตชีวาเพื่อแสวงหาจุดสิ้นสุดที่กำหนด สมมติว่าสายเคเบิลใต้น้ำขาดและเครือข่ายถูกแบ่งออกเป็นสองฝ่าย แต่ละฝ่ายมีผู้ตรวจสอบความถูกต้องครึ่งหนึ่ง ดังนั้นในขั้นตอนการลงคะแนนและส่งมอบ ผู้ตรวจสอบความถูกต้องทั้งหมดในแต่ละด้านจะลงคะแนนให้กับข้อเสนอหนึ่งๆ ที่ปิดกั้น 100% และสามารถรับได้เท่านั้น สูงสุด 50% ของการบล็อกข้อเสนอ การลงคะแนนไม่สามารถไปถึง 2/3 ได้ ดังนั้นเครือข่ายบล็อกเชนทั้งหมดจะรอไปเรื่อย ๆ จนกว่าจะรวบรวมคะแนนเสียง 2/3 ในช่วงเวลารอนี้ บล็อกถัดไปจะไม่สามารถสร้างได้ และไม่สามารถเขียนธุรกรรมใหม่ได้ และเครือข่ายทั้งหมดจะเป็นอัมพาต

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

ก่อนที่สายเคเบิลออปติคอลใต้น้ำจะขาด สถานะของโหนดทั้งหมดในโลกจะสอดคล้องกัน ดังแสดงในรูปต่อไปนี้:

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

ทางซ้ายและขวา แม้ว่าบล็อกใหม่ยังคงถูกขุดทุกๆ 10 นาที แฮชของบล็อกของ block07 ทางซ้ายและ block07 ทางขวาจะไม่เท่ากัน ในขณะนี้ เครือข่าย Bitcoin ยังคงใช้งานได้ แต่ Finality ถูกทำลาย

เมื่อสายเคเบิลออปติคอลใต้น้ำได้รับการซ่อมแซม ในเวลานี้ทั้งสองฝ่ายประสานบล็อกเข้าด้วยกันและพวกเขาจะรู้ว่ามีทางแยกดังแสดงในรูปต่อไปนี้:

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

ในความเป็นจริง แม้ว่าสายเคเบิลออปติคัลใต้น้ำจะต่อเนื่องและเครือข่ายไม่มีพาร์ติชัน แต่ก็มักจะเกิดขึ้นที่นักขุดสองคนขุดบล็อกใหม่พร้อมกัน ในเวลานี้ มันเป็นการแข่งขันเพื่อดูว่าใครโชคดี และอะไรก็ตามที่แยกการสืบทอดบล็อกใหม่ถัดไปจะชนะ กล่าวอีกนัยหนึ่ง Bitcoin จะไม่มีสถานะที่สอดคล้องตามที่กำหนดในทางทฤษฎี และ Fork จะปรากฏขึ้นเมื่อใดก็ได้ที่ระดับความสูงใด ๆ ดังนั้น Bitcoin จึงเสียสละ Finality เพียงเล็กน้อยเพื่อแลกกับ Liveness ที่แข็งแกร่งขึ้น

Network Assumption

อัลกอริธึมฉันทามติแบบกระจายทั้งหมดมีข้อสันนิษฐานโดยนัยเกี่ยวกับเครือข่าย
ให้ฉันพูดถึงการจัดประเภทของเครือข่ายก่อน:

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

กึ่งซิงโครนัส: ต้องส่งข้อความภายในระยะเวลาหนึ่ง T แต่ค่าของ T ไม่ใช่ค่าคงที่ แต่เปลี่ยนแปลงแบบไดนามิก เช่น คำนวณแบบไดนามิกตามสถานะเครือข่าย โหนดทั้งหมด

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

สมมติฐานของ Bitcoin บนเครือข่ายคือเครือข่ายเป็นแบบซิงโครนัสและเวลาจำกัดคือประมาณ 10 นาที หลังจากนักขุดขุดบล็อกหนึ่งบล็อกก็จะออกอากาศไปยังเครือข่ายทั้งหมด ในเวลานี้ ระบบ Bitcoin ทั้งหมดคาดว่าบล็อกนี้ จะหมดภายใน 10 นาที โหนดเต็มออนไลน์ได้รับแล้ว หมายความว่า ทุก 10 นาที โหนดเต็มทั้งหมดจะก้าวไปข้างหน้าอย่างเรียบร้อย นั่นคือ เพิ่มบล็อกที่ส่วนท้ายของบล็อกเชนของตัวเอง แม้ว่าความเร็วของเครือข่ายจะเร็วมาก ตัวอย่างเช่น ในเวลาน้อยกว่า 3 นาที โหนดทั้งหมดได้รับบล็อกใหม่นี้แล้ว และ Bitcoin จะยังคงเดินหน้าต่อไปทุก ๆ 10 นาที (บล็อกใหม่ถูกสร้างขึ้น) Ethereum นั้นคล้ายกัน แต่จำกัดเวลาไว้ที่ 15 วินาที

Tendermint สันนิษฐานว่าเครือข่ายเป็นแบบกึ่งซิงโครนัสในขั้นตอนการเสนอ เนื่องจากจะมีช่วงหมดเวลาในขั้นตอนนี้ หากไม่ได้รับบล็อกข้อเสนอใหม่หลังจากหมดเวลา ผู้ตรวจสอบความถูกต้องคนอื่นๆ จะคิดว่าโหนดผู้เสนอวางสายแล้ว จึงจะเกิดเป็นบล็อกว่าง จนกว่าจะถึง Round-robin ถึงผู้เสนอรายต่อไป Tendermint จำเป็นต้องรวบรวมคะแนนเสียงมากกว่า 2/3 ทั้งใน prevote และ precommit ซึ่งรออย่างไม่มีที่สิ้นสุด นั่นคือในสองขั้นตอนนี้ จะถือว่าเครือข่ายเป็นแบบอะซิงโครนัส ท้ายที่สุด ข้อกำหนดของ Tendermint สำหรับเครือข่ายเป็นแบบกึ่งซิงโครนัส

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

ที่นี่คุณสามารถชื่นชมความเรียบง่ายของ Tendermint เมื่อเทียบกับ pBFT Tendermint ย้ายกลไกการหมดเวลาไปที่ขั้นตอนการเสนอ (เทียบเท่ากับระยะเตรียมการของ pBFT) หากผู้เสนอออกอากาศการบล็อกข้อเสนอภายในเวลาที่กำหนด ก็จะดำเนินการขั้นตอนต่อไป หากหมดเวลา ก็จะดำเนินการต่อ สู่ขั้นตอนต่อไป แต่นี่คือ block ข้อเสนอเป็น block ว่าง (กระบวนการ pre-vote และ pre-commit จะหมดไปเมื่อ block ว่าง แต่ความสูงของ block จะไม่เพิ่มขึ้น 1 ซึ่งเท่ากับ ไปยังเครือข่ายที่ไม่ได้ใช้งานจนกว่าจะมีการวนรอบไปยังโหนดผู้เสนอใหม่จะออกอากาศบล็อกข้อเสนอใหม่อีกครั้ง) กล่าวคือไม่ว่าในกรณีใดขั้นตอนการเสนอจะก้าวไปสู่ขั้นตอนต่อไป แต่การเตรียมตัวล่วงหน้าของ Tendermint เป็นแบบอะซิงโครนัส และอาจติดขัดตลอดไป pBFT ย้ายกลไกการหมดเวลาไปยังส่วน View Change ดังนั้น pBFT จึงมีขั้นตอน View Change เพิ่มเติม ซึ่งซับซ้อนกว่า Tendermint เล็กน้อย Tendermint แทนที่โหนดผู้เสนอโดยส่งบล็อกเปล่าและปัดเศษ ในขณะที่ pBFT แทนที่โหนดหลักผ่าน View Change Tendermint ขจัดขั้นตอน View Change ที่ซับซ้อนออกไป

นอกเหนือจากการกำจัด View Change แล้ว Tendermint ยังทำให้ง่ายขึ้นในที่อื่นอีกด้วย ข้อมูล Tendermint ทั้งหมดจะถูกจัดเก็บไว้ในบล็อกเชน อย่างไรก็ตาม pBFT ถูกเสนอในปี 1999 ในเวลานั้น ยังไม่มีสิ่งที่เรียกว่า blockchain ดังนั้น แม้ว่าโหนดทั้งหมดของ pBFT จะมีข้อมูลที่สอดคล้องกัน ข้อมูลของแต่ละโหนดของ pBFT ประกอบด้วย:

The state of each replica includes the state of the service, a message log containing messages the replica has accepted, and an integer denoting the replica’s current view.

Blockchain เป็นฐานข้อมูลแบบกระจาย ตัวอย่างเช่น ก่อนที่ฐานข้อมูล DBMS เช่น MySQL จะปรากฏขึ้น ผู้คนเขียนข้อมูลลงในไฟล์และจัดเก็บไว้ในฮาร์ดดิสก์ ด้วย MySQL การจัดการข้อมูลจะสะดวกกว่ามาก ในทำนองเดียวกัน Tendermint เก็บข้อมูลทั้งหมดไว้ในบล็อกเชน pBFT ไม่มีฐานข้อมูลแบบกระจาย เช่น บล็อกเชน และโหนดทั้งหมดจำเป็นต้องจัดการข้อมูลบนฮาร์ดดิสก์ด้วยตัวเอง ตัวอย่างเช่น เพื่อบีบอัดบันทึกข้อความ ละทิ้งข้อความเก่า และ ประหยัดเนื้อที่ฮาร์ดดิสก์ แนวคิดของ Checkpoint ถูกนำมาใช้

ความสัมพันธ์ระหว่าง Tendermint และ pBFT นั้นคล้ายคลึงกับความสัมพันธ์ระหว่าง Raft และ Paxos Tendermint เป็นเวอร์ชันที่เรียบง่ายของ pBFT ซึ่งเป็นเวอร์ชันที่เรียบง่ายของ pBFT สำหรับสถานการณ์บล็อกเชน

รูปต่อไปนี้เป็นผังงานอัลกอริทึมของ Tendermint:

รูปต่อไปนี้เป็นผังงานอัลกอริทึมของ pBFT:

อ้างอิง