—— Phân loại Đồng thuận Part1 ——

Từ sự phát triển chậm chạp của các thuật toán đồng thuận phân tán ban đầu cho đến sự nở rộ của sự đồng thuận chuỗi khối ngày nay, sự phát triển của các thuật toán đồng thuận đã trải qua khoảng bốn mươi năm. Các thuật toán đồng thuận khác nhau có trọng tâm khác nhau, vì vậy các vấn đề và môi trường mà chúng gặp phải cũng khác nhau. Bài viết này sẽ phân loại các thuật toán đồng thuận theo các quan điểm khác nhau sau:

▲ Loại khả năng chịu lỗi

Theo việc liệu các lỗi Byzantine có được chấp nhận hay không, các thuật toán đồng thuận có thể được chia thành hai loại.

1) Thuật toán đồng thuận chịu lỗi Byzantine: PBFT, PoW, PoS, DPoS

2) Các thuật toán đồng thuận chịu lỗi không phải của Byzantine: Paxos, Raft

Việc chấp nhận Byzantium có đánh dấu liệu thuật toán có thể được áp dụng cho các mạng có độ tin cậy thấp hay không. Nói chung, thuật toán chịu lỗi Byzantine phải được sử dụng trong môi trường chuỗi công khai, trong khi trong chuỗi liên minh, nó có thể được chọn tùy theo mức độ tin cậy giữa những người tham gia liên minh.

▲ Thuật toán xác định

Theo tính chắc chắn của thuật toán, thuật toán đồng thuận có thể được chia thành hai loại.

1) Thuật toán đồng thuận tất định: Paxos, Raft, PBFT

2) Thuật toán đồng thuận xác suất: PoW, PoS một phần

Đồng thuận xác định có nghĩa là một khi đạt được quyết định đồng thuận, sẽ không có khả năng lùi lại. Danh mục này thường là thuật toán đồng thuận phân tán truyền thống và phiên bản cải tiến của nó. Xác suất có nghĩa là quyết định đồng thuận đã đạt được sẽ được lùi lại với một xác suất nhất định trong tương lai, mặc dù xác suất này sẽ có xu hướng bằng 0 theo thời gian nhưng loại blockchain này thường được áp dụng cho chuỗi công khai thuật toán đồng thuận.

▲Chiến lược lựa chọn chính

Theo chiến lược lựa chọn người lãnh đạo, các thuật toán đồng thuận có thể được chia thành hai loại.

1) Thuật toán đồng thuận bầu cử: Raft, PBFT

2) Các thuật toán đồng thuận bằng chứng: PoW, PoS

Đồng thuận kiểu bầu cử đề cập đến việc lựa chọn các nút tạo khối bằng cách bỏ phiếu. Cùng một nút có thể tồn tại dưới dạng nút tạo khối cho nhiều vòng liên tiếp. Danh mục này thường là thuật toán đồng thuận phân tán truyền thống và phiên bản cải tiến của nó. Thuật toán đồng thuận loại bằng chứng có nghĩa là các nút tạo khối cần chứng minh rằng chúng có khả năng nhất định theo một cách nhất định để có được quyền tạo khối. Loại thuật toán đồng thuận này thường có các nút tạo khối khác nhau trong mỗi vòng, do đó đảm bảo Tính công bằng của quyền khối thường được áp dụng cho các chuỗi công khai.

—— Phần 2 Thuật toán đồng thuận không chịu lỗi của Byzantine——

Paxos

Paxos là thuật toán đồng thuận đầu tiên có thể đảm bảo tính chính xác và khả năng chịu lỗi trong mô hình mạng không đồng bộ. Trước đó, FLP đã chỉ ra rõ ràng rằng trong mô hình mạng không đồng bộ, miễn là có lỗi nút, thì không thể có thuật toán đồng thuận có thể bị chấm dứt. Do đó, Paxos cũng đã hy sinh nhất định: Paxos đã hy sinh một lượng hoạt động nhất định để đảm bảo tính bảo mật của hệ thống, tức là khi hệ thống ở trạng thái không đồng bộ, tiến trình đồng thuận sẽ bị đình chỉ và miễn là hơn một nửa số nút trở lại trạng thái đồng bộ, chúng có thể Thúc đẩy sự đồng thuận và chấm dứt hoàn toàn.

Mô tả hình ảnh

Hình 1. Quy trình đồng thuận Paxos cơ bản

chữ

Raft

Paxos quả thực là một thuật toán đồng thuận có sức ảnh hưởng rất lớn, có thể nói nó đã đặt nền móng cho thuật toán đồng thuận phân tán, tuy nhiên do khó hiểu và khó triển khai nên rất khó triển khai một thuật toán Paxos hoàn chỉnh. Do đó, đã có nhiều biến thể của Paxos, trong đó nổi tiếng nhất là thuật toán đồng thuận Raft.

Raft là một thuật toán đồng thuận để quản lý sao chép nhật ký, được thiết kế dễ hiểu. Nó có khả năng chịu lỗi và hiệu năng của Paxos, điểm khác biệt là nó phân rã vấn đề nhất quán thành 3 vấn đề con tương đối độc lập, đó là bầu chọn lãnh đạo (leader Election), sao chép nhật ký (log replica) và bảo mật (safety). Điều này làm cho Raft được hiểu rõ hơn và dễ áp ​​dụng hơn vào việc thiết lập các hệ thống thực tế.

Trong Raft, mỗi node phải ở 1 trong 3 trạng thái sau: Leader (node ​​chủ), Candidate (nút ứng viên), Follower (node ​​nô lệ). Trong các trường hợp bình thường, chỉ có một nút là Người lãnh đạo và các nút còn lại là Người theo dõi. Người lãnh đạo chịu trách nhiệm xử lý tất cả các yêu cầu từ khách hàng (nếu khách hàng giao tiếp với Người theo dõi, Người theo dõi sẽ chuyển thông tin đến Người lãnh đạo), tạo dữ liệu nhật ký (tương ứng với việc đóng gói trong chuỗi khối) và phát nó đến nút Người theo dõi. Người theo dõi bị động: họ sẽ không chủ động gửi bất kỳ yêu cầu nào và chỉ có thể nhận dữ liệu nhật ký từ Người lãnh đạo theo một hướng. Ứng cử viên là trạng thái chuyển tiếp xảy ra trong quá trình bầu chọn Thủ lĩnh tiếp theo. Bất kỳ nút nào cũng có thể trở thành Ứng viên và trở thành Thủ lĩnh sau khi phát hiện ra lỗi của nút chính.

Thuật toán Raft chia thời gian thành các số hạng (terms) có độ dài bất kỳ. Điều khoản của văn phòng được thể hiện bằng các số liên tiếp. Mỗi nhiệm kỳ bắt đầu bằng một cuộc bầu cử. Nếu một ứng cử viên giành chiến thắng trong cuộc bầu cử, ứng cử viên đó sẽ giữ vai trò lãnh đạo trong phần còn lại của nhiệm kỳ. Trong một số trường hợp, các phiếu bầu sẽ bị chia rẽ và có thể không bầu được lãnh đạo nào, sau đó một nhiệm kỳ khác sẽ bắt đầu và cuộc bầu cử tiếp theo sẽ bắt đầu ngay lập tức.

Mô tả hình ảnh

chữ

tóm tắt

Cả Paxos và Raft đều là sự đồng thuận của Crash Fault Tolerance, đây là một công nghệ không chịu lỗi của Byzantine. Không phải Byzantine có nghĩa là có lỗi sự cố trong hệ thống phân tán, nhưng không có kịch bản nút độc hại (hỏng) (nghĩa là thông báo có thể bị mất hoặc lặp lại, nhưng không có thông báo lỗi) và đó là một hệ thống phân tán. trường đồng thuận.Câu hỏi phổ biến nhất. So với Paxos, Raft ngắn gọn hơn nhưng vẫn đảm bảo khả năng chịu lỗi và hiệu suất như nhau.

chữ

  PoW

Proof of Work (PoW) lần đầu tiên được đề cập trong một bài báo học thuật [3] bởi Cynthia Dwork và Moni Naor vào năm 1993, và khái niệm "Proof of Work" được chính thức đề xuất bởi Markus Jakobsson và Ari Juels trong cùng năm đó[4] . Lúc đầu, PoW chủ yếu được sử dụng để ngăn chặn thư rác. Năm 2008, PoW đã được áp dụng cho hệ thống Bitcoin dưới dạng thuật toán đồng thuận. PoW có ba thuộc tính cơ bản sau:

1) Câu đố toán học: Thuật toán đồng thuận PoW thiết kế một câu đố toán học (Câu đố toán học), yêu cầu các nút tiêu thụ một số tài nguyên máy tính nhất định để có được lời giải cho câu đố trước khi tạo một khối mới, từ đó phát khối đó lên mạng và các nút khác có thể dễ dàng xác minh tính hợp lệ của giải pháp này.

2) Thuật toán băm: Thuật toán băm (Hash Algorithm) là thuật toán có thể biến đổi đầu vào có độ dài bất kỳ thành đầu ra có độ dài cố định, có thể được ghi là y = hash(x) và đầu ra y thu được từ đầu vào x khác nhau thay đổi. Ngoài ra, y có thể được tính nhanh khi biết x, nhưng trong trường hợp y đã biết, x chỉ có thể được suy ra ngược lại bằng các phương pháp toàn diện. Do thuật toán băm có các đặc điểm chuyển tiếp nhanh và khó đảo ngược, nên thuật toán băm thường được sử dụng để thiết kế các vấn đề toán học của PoW.

3) Tạo khối: Trong một vòng tạo khối, hệ thống sẽ điều chỉnh giá trị độ khó của bài toán bằng cách đặt điều kiện cho giá trị đầu ra, sau khi nút giải thành công bài toán và vượt qua xác minh trên chuỗi sẽ nhận được phần thưởng tương ứng .

Trước khi tạo một khối mới, PoW sẽ đặt trước giá trị mục tiêu và yêu cầu giá trị băm được nút tạo khối tính toán phải nhỏ hơn giá trị mục tiêu để thể hiện độ khó của PoW. Để tạo khối và nhận phần thưởng, trước tiên, các nhà sản xuất khối sẽ thu thập một tập hợp các giao dịch và đóng gói chúng thành một khối, sau đó bắt đầu thử giải các bài toán để tạo khối.

Trong khoảng thời gian này, nút tạo khối cần tạo số ngẫu nhiên, thực hiện nhiều vòng hoạt động băm với dữ liệu khối hiện tại và hàm băm của khối trước đó, đồng thời tính toán giá trị băm của khối hiện tại:

Cho đến khi khối băm hiện tại đáp ứng các điều kiện:

Mô tả hình ảnh

chữ

PoS

Thuật toán đồng thuận bằng chứng công việc nói trên sử dụng sức mạnh tính toán để cạnh tranh tư cách của "người dẫn đầu". Tuy nhiên, một lượng lớn tài nguyên bị lãng phí trong quá trình bằng chứng công việc, điều này khiến nó khó được chấp nhận bởi ứng dụng quy mô lớn hơn. Về vấn đề này, một số người bắt đầu cố gắng trực tiếp sử dụng "Stake" làm tiêu chuẩn cho việc bầu chọn trình độ "Leader" và sau đó đã tạo ra thuật toán đồng thuận Proof of Stake (PoS).

Ý tưởng về PoS xuất phát từ xã hội: một người sở hữu càng nhiều cổ phiếu, cổ tức và cổ tức mà anh ta nhận được càng cao. Nếu hệ thống chuỗi khối cũng được duy trì theo cách này, thì nó không yêu cầu tiêu thụ tài nguyên quá mức và nó cũng có thể gây ra lạm phát tự nhiên đối với tài sản chuỗi khối. Các nút tham gia vào sự đồng thuận bằng cách đầu tư một số lượng mã thông báo nhất định và có quyền đóng gói các khối mới và nhận phần thưởng theo số lượng mã thông báo nắm giữ. Hiện tại, Ethereum cũng có kế hoạch Ethereum 2.0 để chuyển sang PoS.

Để mô tả trạng thái nắm giữ mã thông báo, thuật toán đồng thuận PoS đưa ra khái niệm "thời đại tiền xu". Tuổi xu cho biết thời gian một nút giữ một số mã thông báo. Khi một nút đầu tư các mã thông báo dưới dạng "cổ phần", phần này của mã thông báo sẽ bắt đầu tích lũy tuổi xu. Phương pháp tính toán tuổi tiền như sau:

Sau khi sử dụng phần này của thẻ, cho dù nó được sử dụng để tạo khối hay các giao dịch đơn giản, thời đại tiền tệ tương ứng với phần này của thẻ sẽ bị hủy. Trong thuật toán đồng thuận PoS ban đầu, tuổi đồng xu là một tiêu chí quan trọng để đánh giá. Tuổi đồng xu được sử dụng bởi các nút khi tạo khối càng cao thì càng dễ tạo khối, điều này có thể hạn chế đầu cơ ngắn hạn ở một mức độ nhất định.

Khi thuật toán đồng thuận PoS tạo khối, nó sẽ tính đến cả tuổi của đồng xu và độ khó của hoạt động băm, do đó các nút chỉ cần tiêu tốn rất ít tài nguyên máy tính để hoàn thành việc tạo khối.

DPoS

Trong thuật toán đồng thuận Delegated Proof of Stake (DPoS) [5], cử tri bầu chọn đại diện, những người trực tiếp tạo ra các khối và đại cử tri gián tiếp thực hiện quyền cạnh tranh các khối thông qua bầu chọn đại diện. Thuật toán đồng thuận bằng chứng cổ phần được ủy quyền thực sự hạn chế các ứng cử viên thông qua một loạt các quy tắc lựa chọn và xây dựng một bộ quy tắc bỏ phiếu. Những người tham gia thông thường chọn người ủy quyền từ các ứng cử viên thông qua bỏ phiếu và người ủy quyền sẽ tạo ra các khối. Những người ủy quyền không đáp ứng yêu cầu sẽ bị thu hồi và những người ủy quyền mới sẽ được bầu lại.

DPoS giữ lại một số tính năng tập trung nhất định, vì vậy nó có thể đảm bảo thông lượng giao dịch hiệu quả cao và tốc độ có thể được so sánh với các tổ chức tập trung phổ biến, chẳng hạn như Visa, Mastercard, v.v. Trong thuật toán này, đặc điểm phân quyền chủ yếu thể hiện ở khả năng kiểm soát quyền sinh khối. Nghĩa là, các cổ đông bỏ phiếu để chọn các nút đại diện đáng tin cậy của họ và các nút đại diện duy trì dữ liệu chuỗi khối.

——Phần 4 Tóm tắt——

Các thuật toán đồng thuận được đề cập ở trên hầu hết được sử dụng trong các kịch bản chuỗi công khai, chẳng hạn như Bitcoin, Ethereum, v.v. Do quy mô lớn của các nút trong các kịch bản chuỗi công khai, rất khó để áp dụng thuật toán đồng thuận phân tán xác định. So với PoW, PoS hy sinh một lượng bảo mật nhất định để giảm mức tiêu thụ năng lượng, trong khi DPoS sử dụng một cách triệt để hơn để chọn ít nút hơn để cải thiện hiệu quả đồng thuận.

Giới thiệu về tác giả

Giới thiệu về tác giả

người giới thiệu

Nhóm Nghiên cứu Thuật toán Đồng thuận của Phòng Nền tảng Cơ bản của Công nghệ FunChain

người giới thiệu

[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