—— การจำแนกประเภทของฉันทามติส่วนที่ 1 ——

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

▲ประเภทความทนทานต่อความผิดพลาด

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

1) อัลกอริธึมฉันทามติที่ยอมรับความผิดพลาดของไบแซนไทน์: PBFT, PoW, PoS, DPoS

2) อัลกอริธึมฉันทามติที่ยอมรับความผิดพลาดที่ไม่ใช่ไบแซนไทน์: Paxos, Raft

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

▲ การกำหนดอัลกอริทึม

ตามความแน่นอนของอัลกอริทึม อัลกอริทึมฉันทามติสามารถแบ่งออกเป็นสองประเภท

1) อัลกอริทึมฉันทามติที่กำหนดขึ้น: Paxos, Raft, PBFT

2) อัลกอริธึมฉันทามติที่น่าจะเป็น: PoW, PoS บางส่วน

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

▲กลยุทธ์การเลือกหลัก

ตามกลยุทธ์การเลือกผู้นำ อัลกอริทึมฉันทามติสามารถแบ่งออกเป็นสองประเภท

1) อัลกอริทึมฉันทามติการเลือกตั้ง: Raft, PBFT

2) อัลกอริธึมการพิสูจน์ฉันทามติ: PoW, PoS

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

—— ส่วนที่ 2 อัลกอริทึมฉันทามติที่ไม่ใช่ไบแซนไทน์ Fault Tolerant ——

Paxos

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

คำอธิบายภาพ

รูปที่ 1 กระบวนการฉันทามติ Paxos ขั้นพื้นฐาน

ข้อความ

Raft

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

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

ใน Raft แต่ละโหนดต้องอยู่ในหนึ่งในสามสถานะต่อไปนี้: Leader (โหนดหลัก), Candidate (โหนดผู้สมัคร), Follower (โหนดสเลฟ) ภายใต้สถานการณ์ปกติ โหนดเดียวเท่านั้นคือผู้นำ และโหนดที่เหลือคือผู้ติดตาม ผู้นำมีหน้าที่รับผิดชอบในการประมวลผลคำขอทั้งหมดจากลูกค้า (หากลูกค้าสื่อสารกับผู้ติดตาม ผู้ติดตามจะส่งต่อข้อมูลไปยังผู้นำ) สร้างข้อมูลบันทึก (สอดคล้องกับบรรจุภัณฑ์ในบล็อกเชน) และเผยแพร่ไปยังโหนดผู้ติดตาม ผู้ติดตามจะไม่โต้ตอบ: พวกเขาจะไม่ส่งคำขอใด ๆ และสามารถรับข้อมูลบันทึกจากผู้นำในทิศทางเดียวเท่านั้น ผู้สมัครเป็นสถานะเปลี่ยนผ่านที่เกิดขึ้นระหว่างกระบวนการเลือกผู้นำคนต่อไป โหนดใดๆ สามารถกลายเป็นผู้สมัครและกลายเป็นผู้นำได้หลังจากค้นพบความล้มเหลวของโหนดหลัก

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

คำอธิบายภาพ

ข้อความ

สรุป

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

ข้อความ

  PoW

Proof of Work (PoW) ถูกกล่าวถึงเป็นครั้งแรกในเอกสารวิชาการ [3] โดย Cynthia Dwork และ Moni Naor ในปี 1993 และแนวคิดของ "Proof of Work" ถูกเสนออย่างเป็นทางการโดย Markus Jakobsson และ Ari Juels ในปีเดียวกัน[4] . ในตอนแรก PoW ถูกใช้เพื่อป้องกันสแปมเป็นหลัก ในปี 2551 PoW ถูกนำไปใช้กับระบบ Bitcoin เป็นอัลกอริทึมที่สอดคล้องกัน PoW มีคุณสมบัติพื้นฐานสามประการดังต่อไปนี้:

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

2) อัลกอริทึมแฮช: อัลกอริทึมแฮช (Hash Algorithm) เป็นอัลกอริทึมที่สามารถเปลี่ยนอินพุตที่มีความยาวเท่าใดก็ได้ให้เป็นเอาต์พุตที่มีความยาวคงที่ ซึ่งสามารถบันทึกเป็น y = แฮช (x) และเอาต์พุต y ที่ได้จากอินพุต x ที่แตกต่างกัน ต่างกันไป. นอกจากนี้ y สามารถคำนวณได้อย่างรวดเร็วเมื่อทราบค่า x แต่ในกรณีของค่า y ที่ทราบ ค่า x สามารถอนุมานแบบผกผันได้ด้วยวิธีละเอียดถี่ถ้วนเท่านั้น เนื่องจากอัลกอริทึมแฮชมีลักษณะของการกรอไปข้างหน้าอย่างรวดเร็วและการย้อนกลับที่ยาก อัลกอริทึมแฮชจึงมักใช้ในการออกแบบปัญหาทางคณิตศาสตร์ของ PoW

3) การสร้างบล็อก: ในรอบของการสร้างบล็อก ระบบจะปรับค่าความยากของปัญหาทางคณิตศาสตร์โดยการตั้งค่าเงื่อนไขของค่าเอาต์พุต หลังจากที่โหนดแก้ปัญหาสำเร็จและผ่านการตรวจสอบในห่วงโซ่ ก็จะได้รับรางวัลที่เกี่ยวข้อง .

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

ในช่วงเวลานี้ โหนดที่ผลิตบล็อกจำเป็นต้องสร้างตัวเลขสุ่ม ดำเนินการแฮชหลายรอบด้วยข้อมูลบล็อกปัจจุบันและแฮชของบล็อกก่อนหน้า และคำนวณค่าแฮชของบล็อกปัจจุบัน:

จนกว่าแฮชบล็อกปัจจุบันจะตรงตามเงื่อนไข:

คำอธิบายภาพ

ข้อความ

PoS

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

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

เพื่ออธิบายสถานะของการถือครองโทเค็น อัลกอริทึมฉันทามติของ PoS แนะนำแนวคิดของ "coin age" Coin-age ระบุระยะเวลาที่โหนดถือส่วนหนึ่งของ pass เมื่อ node ลงทุน pass เป็น "share" ส่วนนี้ของ pass จะเริ่มสะสม coin-age วิธีคำนวณ coin-age มีดังนี้ ดังนี้:

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

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

DPoS

ในอัลกอริธึมฉันทามติ Delegated Proof of Stake (DPoS) [5] ผู้มีสิทธิเลือกตั้งจะเลือกผู้แทนซึ่งสร้างบล็อกโดยตรง และผู้มีสิทธิเลือกตั้งใช้สิทธิ์โดยอ้อมเพื่อแข่งขันเพื่อแย่งชิงบล็อกผ่านการเลือกผู้แทน อัลกอริธึมฉันทามติที่พิสูจน์การมีส่วนได้ส่วนเสียที่ได้รับมอบหมายจริง ๆ แล้ว จำกัด ผู้สมัครผ่านชุดกฎการคัดเลือกและกำหนดกฎการลงคะแนนชุดหนึ่ง ผู้เข้าร่วมทั่วไปจะเลือกผู้แทนจากผู้สมัครผ่านการลงคะแนนเสียง และผู้แทนจะผลิตบล็อค ผู้มอบหมายที่ไม่ตรงตามข้อกำหนดจะถูกเพิกถอนและผู้แทนใหม่จะได้รับการเลือกตั้งใหม่

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

——บทสรุปตอนที่ 4——

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

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

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

อ้างอิง

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

อ้างอิง

[1]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.

[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.

[5]Delegated Proof of Stakehttps://github.com/dacplayproject/cpp-play/wiki/Delegated-Proof-of-Stake