ข้อความ

Practical Byzantine Fault Tolerance (PBFT) เป็นวิธีการที่ใช้ได้จริงในการแก้ปัญหา Byzantine Generals เมื่อ Channel มีความน่าเชื่อถือ ปัญหาแม่ทัพไบแซนไทน์ถูกเสนอครั้งแรกโดยเลสลี่ แลมพอร์ต และคณะ ในบทความ [1] ที่ตีพิมพ์ในปี 1982 ในบทความ ได้รับการพิสูจน์ว่าเมื่อจำนวนนายพลทั้งหมด n มากกว่า 3f และจำนวนผู้แปรพักตร์เท่ากับ f หรือ น้อยกว่า นายพลที่ภักดีสามารถบรรลุฉันทามติในคำสั่ง กล่าวคือ 3f+1<=n ความซับซ้อนของอัลกอริทึมคือ O(n^(f+1)) ต่อจากนั้น Miguel Castro และ Barbara Liskov ได้เสนออัลกอริทึม PBFT เป็นครั้งแรกในบทความ [2] ที่ตีพิมพ์ในปี 1999 จำนวนของความผิดพลาดที่ยอมรับได้ของอัลกอริทึมยังเป็นไปตาม 3f+1<=n และความซับซ้อนของอัลกอริทึมจะลดลงเหลือ O(n^ 2).

หากคุณเข้าใจอัลกอริธึมฉันทามติของ PBFT คุณอาจคุ้นเคยกับความสัมพันธ์ระหว่างจำนวนโหนดทั้งหมด n และขีดจำกัดบนของความทนทานต่อข้อผิดพลาด f: ภายใต้สมมติฐานว่ามีโหนดที่ผิดพลาดมากที่สุดในระบบ จำนวนโหนดทั้งหมด n ในระบบควรเป็นไปตาม n>3f ในกระบวนการเลื่อนฉันทามติจำเป็นต้องรวบรวมคะแนนเสียงจำนวนหนึ่งเพื่อให้กระบวนการรับรองเสร็จสมบูรณ์ ในหัวข้อนี้ เราจะพูดถึงความสัมพันธ์ระหว่างค่าเหล่านี้ก่อน

--กลไกองค์ประชุม--

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

เพื่อให้เข้าใจกลไกองค์ประชุมได้ดียิ่งขึ้น ก่อนอื่นมาทำความเข้าใจกลไกการลงคะแนนเสียงที่คล้ายกันแต่รุนแรงกว่า นั่นคือกลไก WARO (เขียนทั้งหมดอ่านหนึ่งรายการ) เมื่อใช้กลไก WARO เพื่อรักษาคลัสเตอร์ด้วยจำนวนโหนดทั้งหมด n ค่า "โหวต" สำหรับโหนดเพื่อดำเนินการเขียนควรเป็น n ในขณะที่ "โหวต" สำหรับการอ่านสามารถตั้งค่าเป็น 1 กล่าวคือ เมื่อดำเนินการเขียน จำเป็นต้องตรวจสอบให้แน่ใจว่าโหนดทั้งหมดเสร็จสิ้นการดำเนินการเขียนก่อนที่จะถือว่าการดำเนินการเสร็จสมบูรณ์ มิฉะนั้น การดำเนินการเขียนจะล้มเหลว เช่นเดียวกัน เมื่อดำเนินการอ่าน สถานะเท่านั้น ของหนึ่งโหนดจำเป็นต้องอ่าน คุณสามารถตรวจสอบสถานะของระบบได้ จะเห็นได้ว่าในคลัสเตอร์ที่ใช้กลไก WARO การดำเนินการเขียนนั้นเปราะบางมาก: ตราบใดที่โหนดหนึ่งล้มเหลวในการดำเนินการเขียน การดำเนินการจะไม่สามารถเสร็จสมบูรณ์ได้ อย่างไรก็ตาม แม้ว่าความทนทานของการดำเนินการเขียนจะลดลง แต่ภายใต้กลไก WARO การดำเนินการอ่านบนคลัสเตอร์ทำได้ง่ายมาก

• กลไก Quorum [3] เป็นการพิจารณาที่ประนีประนอมสำหรับการดำเนินการอ่านและเขียน สำหรับแต่ละสำเนาของออบเจกต์ข้อมูลเดียวกัน จะอ่านและเขียนออบเจกต์การเข้าถึงไม่เกิน 2 รายการ และมีการชั่งน้ำหนักข้อกำหนดด้านขนาดที่ตั้งไว้สำหรับการอ่านและเขียน ในคลัสเตอร์แบบกระจาย แต่ละออบเจกต์การคัดลอกข้อมูลจะได้รับการโหวต สมมติฐาน:

• มีตั๋ว V ในระบบ ซึ่งหมายความว่าอ็อบเจ็กต์ข้อมูลมีสำเนาสำรอง V;

• สำหรับการดำเนินการอ่านแต่ละครั้ง จำนวนคะแนนเสียงที่ได้รับจะต้องไม่น้อยกว่าจำนวนขั้นต่ำของคะแนนเสียงการอ่าน R (องค์ประชุมการอ่าน) จึงจะอ่านได้สำเร็จ

สำหรับการดำเนินการเขียนแต่ละครั้ง จำนวนคะแนนเสียงที่ได้รับจะต้องไม่น้อยกว่าจำนวนคะแนนขั้นต่ำของการเขียน W (องค์ประชุมการเขียน) จึงจะเขียนได้สำเร็จ

สำหรับโหนดที่สอดคล้องกันในคลัสเตอร์ เมื่อพัฒนาอัลกอริธึมที่สอดคล้องกัน โหนดที่เข้าร่วมในฉันทามติจะดำเนินการอ่านและเขียนพร้อมกันบนคลัสเตอร์ เพื่อให้ข้อกำหนดของการดำเนินการอ่านและเขียนสมดุลกับขนาดของคอลเล็กชัน R และ W ของแต่ละโหนดจะมีขนาดเท่ากัน ซึ่งแสดงเป็น Q เมื่อมีทั้งหมด n โหนดในคลัสเตอร์ และมีโหนดข้อผิดพลาด f มากที่สุด เราจะคำนวณความสัมพันธ์ระหว่าง n, f และ Q ได้อย่างไร ต่อไป เราจะเริ่มจากสถานการณ์จำลอง CFT ที่ง่ายที่สุด และค่อยๆ สำรวจวิธีรับความสัมพันธ์ระหว่างค่าตัวเลขเหล่านี้ในสถานการณ์จำลอง BFT

▲CFT

ข้อความ

CFT (Crash Fault Tolerance) หมายความว่าโหนดในระบบจะพบเฉพาะลักษณะการทำงานผิดพลาดของการขัดข้อง (Crash) และไม่มีโหนดใดที่จะส่งข้อความแสดงข้อผิดพลาด เมื่อเราพูดถึงความน่าเชื่อถือของอัลกอริทึมที่สอดคล้องกัน เรามักจะเน้นไปที่คุณสมบัติพื้นฐานสองประการของอัลกอริทึม: ความมีชีวิตชีวาและความปลอดภัย เมื่อคำนวณขนาดของ Q ก็สามารถพิจารณาจากสองมุมนี้ได้เช่นกัน

• สำหรับกิจกรรมและความปลอดภัย มีวิธีที่ง่ายกว่าในการอธิบาย:

• ในที่สุดบางสิ่งก็เกิดขึ้น[4] เหตุการณ์ก็จะเกิดขึ้นในที่สุด

ในที่สุดสิ่งดี ๆ ก็เกิดขึ้น[4] เหตุการณ์ที่จะเกิดขึ้นในที่สุดก็สมเหตุสมผล

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

• ดังนั้นในสถานการณ์ CFT การกำหนดค่า Q จะง่ายและชัดเจน:<=n-f。

• กิจกรรม: เนื่องจากเราจำเป็นต้องตรวจสอบให้แน่ใจว่าคลัสเตอร์สามารถทำงานต่อไปได้ เราจึงต้องตรวจสอบให้แน่ใจว่ามีความเป็นไปได้ที่จะได้รับตั๋ว Q ในทุกสถานการณ์ เพื่อที่จะอ่านและเขียนข้อมูลสำหรับการรวบรวม เนื่องจากโหนด f ส่วนใหญ่ในคลัสเตอร์จะหยุดทำงาน เพื่อให้แน่ใจว่าสามารถรับตั๋ว Q ได้ ขนาดของค่านี้จึงต้องเป็นไปตาม: Q

▲BFT

ความปลอดภัย: เนื่องจากเราต้องแน่ใจว่าคลัสเตอร์ไม่แยกออกจากกัน ตามข้อกำหนดพื้นฐานของกลไก Quorum ความไม่เท่าเทียมกันสองอย่างที่กล่าวถึงในส่วนก่อนหน้าจึงจำเป็นต้องตรงกัน และ Q จะถูกนำเข้าสู่ชุดของความไม่เท่าเทียมกันนี้เป็นค่าต่ำสุดที่อ่านได้ ชุดและชุดการเขียนขั้นต่ำ ในขณะนี้ Q เป็นไปตามความสัมพันธ์อสมการ Q+Q>n และ Q>n/2 ดังนั้น ขนาดของค่านี้จำเป็นต้องตอบสนอง: Q>n/2

• BFT (Byzantine Fault Tolerance) หมายความว่าโหนดที่ไม่ถูกต้องในคลัสเตอร์อาจไม่เพียงหยุดทำงานเท่านั้น แต่ยังอาจมีพฤติกรรมที่เป็นอันตรายอีกด้วย นั่นคือพฤติกรรมของไบแซนไทน์ เช่น การส้อมสถานะที่ใช้งานอยู่ ในกรณีนี้ สำหรับคลัสเตอร์โดยรวม เฉพาะโหนด nf เท่านั้นที่อยู่ในสถานะที่เชื่อถือได้ และเมื่อเรารวบรวมการโหวต Q เฉพาะการโหวต Qf เท่านั้นที่มาจากโหนดที่เชื่อถือได้ ดังนั้น ในแง่ของความปลอดภัย ในสถานการณ์ BFT จึงจำเป็นต้องตรวจสอบให้แน่ใจว่าจะไม่มีความแตกต่างระหว่างโหนดที่มีสถานะที่เชื่อถือได้ ดังนั้นจึงได้รับความสัมพันธ์สองรายการต่อไปนี้:<=n-f。

• กิจกรรม: ยังคงมีความจำเป็นเพียงเพื่อให้มั่นใจว่ามีโอกาสได้รับตั๋ว Q ตลอดเวลา ดังนั้น Q

▲จำนวนโหนดทั้งหมดและขีดจำกัดบนของความทนทานต่อข้อผิดพลาด

ข้อความ

สำหรับจำนวนโหนดทั้งหมด n และขีดจำกัดบนของค่าความคลาดเคลื่อน f คำอธิบายที่ให้ไว้ในกระดาษ PBFT [1]: เนื่องจากมีโหนด f ที่อาจหยุดทำงาน เราจำเป็นต้องตอบสนองเมื่อเราได้รับข้อความ nf เป็นอย่างน้อย และ เพื่อให้เราได้รับข้อความจากโหนด nf เนื่องจากอาจมีข้อความได้มากที่สุด f จากโหนดไบแซนไทน์ที่ไม่น่าเชื่อถือ จึงจำเป็นต้องตอบสนอง nff>f ดังนั้น n>3fกล่าวอย่างง่ายๆ ผู้เขียน PBFT ได้รับความสัมพันธ์ระหว่างจำนวนโหนดทั้งหมดและขีดจำกัดบนของการยอมรับข้อผิดพลาดจากมุมมองของกิจกรรมคลัสเตอร์และความปลอดภัย ในส่วนก่อนหน้านี้ เรายังได้รับความสัมพันธ์ระหว่าง n, f และ Q จากมุมมองของกิจกรรมและความปลอดภัย ซึ่งสามารถใช้เพื่อหาความสัมพันธ์ระหว่าง n และ f ได้ที่นี่: เพื่อให้เป็นไปตามข้อกำหนดของกิจกรรมและความปลอดภัยที่ ในขณะเดียวกัน Q จำเป็นต้องตอบสนองความสัมพันธ์ของอสมการ Q<=nf และ Q>(n+f)/2 ดังนั้นจึงสามารถหาความสัมพันธ์อสมการระหว่าง n และ f ได้ (n+f)/2

3f

(ในทำนองเดียวกัน สามารถรับความสัมพันธ์ระหว่าง n และ f ในฉาก CFT ได้ด้วย n>2f)

--PBFT และ RBFT--

หลังจากเข้าใจความสัมพันธ์ระหว่าง n, f และ Q ในสถานการณ์สมมติ BFT แล้ว เรามาทำความรู้จักกับ PBFT กัน ก่อนหน้านั้น กล่าวถึงเครื่องสถานะการจำลองแบบ SMR (State Machine Replication) สั้นๆ [5] ในโมเดลนี้ สำหรับเครื่องที่มีสถานะต่างกัน หากเริ่มต้นจากสถานะเริ่มต้นเดียวกันและป้อนชุดคำสั่งเดียวกันในลำดับเดียวกัน ก็จะได้ผลลัพธ์สุดท้ายที่เหมือนกันเสมอ สำหรับอัลกอริทึมที่เป็นเอกฉันท์ จำเป็นต้องตรวจสอบให้แน่ใจว่า "คำสั่งเดียวกันถูกป้อนในลำดับเดียวกัน" เพื่อให้ได้สถานะเดียวกันในแต่ละเครื่องสถานะ PBFT เป็นเอกฉันท์ในคำสั่งของการดำเนินการคำสั่ง

▲ ฉันทามติสองขั้นตอน

ข้อความ

เมื่อเปรียบเทียบกับแนวคิด "สามขั้นตอน" ทั่วไป (ก่อนเตรียม เตรียม ยืนยัน) การมองว่า PBFT เป็นโปรโตคอลฉันทามติสองขั้นตอนอาจสะท้อนถึงวัตถุประสงค์ของแต่ละขั้นตอนได้ดีกว่า: ขั้นตอนการเสนอ (เตรียมและเตรียมการล่วงหน้า) และกระทำ ขั้นตอน (กระทำ) ในแต่ละด่าน แต่ละโหนดจำเป็นต้องรวบรวมคะแนนเสียงเป็นเอกฉันท์จากโหนด Q ก่อนเข้าสู่สเตจถัดไป ในที่นี้เราจะพูดถึงสถานการณ์เมื่อจำนวนโหนดทั้งหมดคือ 3f+1 ในขณะนี้ จำนวนตั๋วการอ่านและการเขียน Q คือ 2f+1

1) ขั้นตอนข้อเสนอ

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

• v คือมุมมองปัจจุบัน

• n หมายเลขลำดับคำขอที่กำหนดโดยโหนดหลัก

• D(m) คือข้อความย่อย

m คือข้อความนั้นเอง，

• หลังจากได้รับข้อความเตรียมการล่วงหน้า โหนดทาสจะตรวจสอบความถูกต้องของข้อความ หากการตรวจสอบผ่าน โหนดจะเข้าสู่สถานะเตรียมการล่วงหน้า ซึ่งบ่งชี้ว่าคำขอผ่านการตรวจสอบความถูกต้องตามกฎหมายที่โหนดสเลฟแล้ว มิฉะนั้น โหนดสเลฟจะปฏิเสธคำขอและทริกเกอร์กระบวนการเปลี่ยนมุมมอง เมื่อโหนดสเลฟเข้าสู่สถานะเตรียมการล่วงหน้า มันจะออกอากาศข้อความเตรียมการไปยังโหนดอื่นๆ

i คือหมายเลขประจำตัวโหนดปัจจุบัน

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

2) ขั้นตอนการส่งเมื่อคำขอเข้าสู่สถานะเตรียมพร้อมบนโหนดปัจจุบัน โหนดจะออกอากาศข้อความยืนยันไปยังโหนดอื่น

▲กลไกด่านตรวจ

ข้อความ

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

• Checkpoint คือจุดตรวจสอบซึ่งเป็นกระบวนการตรวจสอบว่าคลัสเตอร์เข้าสู่สถานะคงที่หรือไม่ เมื่อทำการตรวจสอบ โหนดจะออกอากาศข้อความจุดตรวจสอบ

• n คือหมายเลขลำดับคำขอปัจจุบัน

• d คือไดเจสต์ที่ได้รับหลังจากดำเนินการข้อความ

ฉันเป็นตัวแทนของโหนดปัจจุบันเมื่อโหนดได้รับ 2f+1 รายการจากโหนดที่แตกต่างกันด้วยเหมือนกัน

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

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

▲ดูการเปลี่ยนแปลง

ข้อความ

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

• เมื่อมีการเปลี่ยนแปลงมุมมอง โหนดจะเข้าสู่มุมมองใหม่ v+1 และเผยแพร่ข้อความเปลี่ยนมุมมอง โดยขอให้เปลี่ยนโหนดหลัก ณ จุดนี้ Consensus Cluster จำเป็นต้องตรวจสอบให้แน่ใจว่าคำขอที่ได้รับฉันทามติที่เสร็จสิ้นแล้วในมุมมองเก่าสามารถเก็บไว้ในมุมมองใหม่ได้ ดังนั้น ในคำขอเปลี่ยนมุมมอง โดยทั่วไปจำเป็นต้องเพิ่มส่วนหนึ่งของบันทึกฉันทามติในมุมมองเก่า และคำขอที่ออกอากาศโดยโหนดคือ

• ฉันคือตัวตนของโหนดผู้ส่ง

• v+1 ระบุมุมมองใหม่ที่คำขอเข้ามา

• h คือความสูงของจุดตรวจสอบที่เสถียรล่าสุดของโหนดปัจจุบันC: คอลเลกชันของจุดตรวจสอบที่โหนดปัจจุบันได้ดำเนินการ และข้อมูลเป็นไปตาม

• จัดเก็บด้วยวิธีเดียวกัน หมายความว่าโหนดปัจจุบันได้ดำเนินการตรวจสอบจุดตรวจสอบด้วยหมายเลขลำดับ n และไดเจสต์ d และส่งข้อความที่สอดคล้องกันP: ชุดของคำขอที่ถึงสถานะเตรียมพร้อมที่โหนดปัจจุบัน นั่นคือ โหนดปัจจุบันได้รับข้อความเตรียมล่วงหน้า 1 ข้อความ และ 2f เตรียมข้อความสำหรับคำขอ ในชุด P ข้อมูลตาม

• จัดเก็บด้วยวิธีเดียวกัน หมายความว่าในมุมมอง v คำขอที่มีข้อมูลสรุปคือ d และหมายเลขลำดับเป็น n ได้เข้าสู่สถานะเตรียมพร้อมแล้ว เนื่องจากคำขอมาถึงสถานะเตรียมพร้อมแล้ว หมายความว่า โหนดอย่างน้อย 2f+1 เป็นเจ้าของและอนุมัติคำขอ และ การยืนยันความสอดคล้องสามารถทำได้ในขั้นตอนการคอมมิตเท่านั้น ดังนั้น ในมุมมองใหม่ ข้อความส่วนนี้สามารถ ใช้หมายเลขลำดับเดิมโดยตรง โดยไม่ต้องกำหนดหมายเลขลำดับใหม่ถาม: ชุดคำขอที่ถึงสถานะเตรียมการล่วงหน้าที่โหนดปัจจุบัน นั่นคือ โหนดปัจจุบันได้ส่งข้อความเตรียมล่วงหน้าหรือเตรียมการที่เกี่ยวข้องสำหรับคำขอ ในชุด Q ข้อมูลยังเป็นไปตาม

วิธีการจัดเก็บ เนื่องจากคำขอได้เข้าสู่สถานะเตรียมการล่วงหน้า หมายความว่าคำขอได้รับการอนุมัติโดยโหนดปัจจุบัน

อย่างไรก็ตาม หลังจากได้รับข้อความเปลี่ยนมุมมองที่ส่งโดยโหนดอื่น โหนดหลักใหม่ที่สอดคล้องกับมุมมอง v+1 ไม่สามารถยืนยันได้ว่าข้อความเปลี่ยนมุมมองถูกส่งโดยโหนดไบแซนไทน์หรือไม่ และไม่สามารถรับประกันได้ว่าจะต้องใช้ข้อความที่ถูกต้อง เพื่อประกอบการตัดสินใจ PBFT อนุญาตให้ทุกโหนดตรวจสอบและยืนยันข้อความเปลี่ยนมุมมองทั้งหมดที่ได้รับผ่านข้อความเปลี่ยนมุมมอง จากนั้นจึงส่งผลการยืนยันไปยัง P Master node P นับข้อความ view-change-ack และสามารถระบุได้ว่า view-changes ใดถูกต้องและข้อความใดที่ส่งโดย Byzantine node

• เมื่อโหนดยืนยันข้อความเปลี่ยนมุมมอง ก็จะตรวจสอบชุด P และ Q ในนั้น และข้อความร้องขอในชุดจะต้องน้อยกว่าหรือเท่ากับมุมมอง v หากตรงตามข้อกำหนด การเปลี่ยนแปลงมุมมอง ข้อความ -ack จะถูกส่ง

• ฉันคือ ID โหนดที่ส่งข้อความตอบรับ

• j คือ ID ผู้ส่งของข้อความเปลี่ยนมุมมองที่ต้องยืนยัน

d คือส่วนสรุปของข้อความเปลี่ยนมุมมองที่ต้องรับทราบ

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

• โหนดหลักใหม่ P รักษาชุด S เพื่อจัดเก็บข้อความเปลี่ยนมุมมองที่ถูกต้องซึ่งได้รับการยืนยัน เมื่อ P ได้รับข้อความเปลี่ยนมุมมองและข้อความเปลี่ยนมุมมองที่สอดคล้องกันทั้งหมด 2f-1 ข้อความจะเพิ่มข้อความเปลี่ยนมุมมองนี้ให้กับชุด S เมื่อขนาดของชุด S ถึง 2f+1 แสดงว่ามีโหนดที่ไม่ใช่ไบแซนไทน์มากพอที่จะเริ่มต้นการเปลี่ยนแปลงมุมมอง โหนดหลัก P จะสร้างข้อความมุมมองใหม่และเผยแพร่ตามข้อความเปลี่ยนมุมมองที่ได้รับV: ดูชุดการตรวจสอบการเปลี่ยนแปลงตาม

• หมายความว่าไดเจสต์ของข้อความเปลี่ยนมุมมองที่ส่งโดยโหนด i คือ d ซึ่งสอดคล้องกับข้อความในชุด S และโหนดอื่นๆ สามารถใช้ไดเจสต์และโหนด ID ในชุดเพื่อยืนยันความถูกต้องของการเปลี่ยนแปลงมุมมอง

X: มีจุดตรวจสอบที่เสถียรและคำขอให้เลือกมุมมองใหม่ โหนดหลัก P ใหม่จะคำนวณตามข้อความเปลี่ยนมุมมองของ S ในชุด กำหนดจุดตรวจสอบความเสถียรสูงสุดและคำขอที่ต้องเก็บไว้ในมุมมองใหม่ตามชุด C P และ Q และ เขียนลงในชุด X ในหมู่พวกเขา กระบวนการคัดเลือกที่เฉพาะเจาะจงนั้นค่อนข้างยุ่งยาก หากคุณสนใจ ผู้อ่านสามารถดูเอกสารต้นฉบับได้ [6]

▲การปรับปรุงพื้นที่และ RBFT

RBFT (Robust Byzantine Fault Tolerance) เป็นอัลกอริธึมฉันทามติที่แข็งแกร่งซึ่งพัฒนาโดย Qulian Technology โดยใช้ PBFT สำหรับแพลตฟอร์มเครือข่ายพันธมิตรระดับองค์กร เมื่อเทียบกับ PBFT เราได้ปรับและปรับปรุงการประมวลผลข้อความฉันทามติ การกู้คืนสถานะโหนด การบำรุงรักษาไดนามิกของคลัสเตอร์ และด้านอื่นๆ เพื่อให้อัลกอริทึมฉันทามติของ RBFT สามารถรับมือกับสถานการณ์จริงที่ซับซ้อนและหลากหลายมากขึ้น

1) กลุ่มการซื้อขาย

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

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

2) การกู้คืนที่ใช้งานอยู่

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

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

3) การบำรุงรักษาแบบไดนามิกของคลัสเตอร์

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

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

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

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

เกี่ยวกับผู้เขียน

เกี่ยวกับผู้เขียน

กลุ่มวิจัยอัลกอริทึมที่สอดคล้องกันของแผนกแพลตฟอร์มพื้นฐานของเทคโนโลยี FunChain

อ้างอิง

[1] Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.

[2] Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI.1999, 99(1999): 173-186.

[3] https://en.wikipedia.org/wiki/Quorum _ (distributed_computing)

[4] Owicki S, Lamport L. Proving liveness properties of concurrent programs[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 455-495.

[5] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319, 1990.

[6] Castro M, Liskov B. Practical Byzantine fault tolerance andproactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002,20(4): 398-461.