Hard Core: Tìm hiểu nguồn gốc, phân loại và bảo mật của các thuật toán đồng thuận trong một bài viết

Tiêu đề gốc: "<Phân tích chuyên sâu về thuật toán đồng thuận> Chuỗi hoạt động chia sẻ - 'Giới thiệu về thuật toán đồng thuận'"
Nguồn gốc: Algorand Official

Tối nay lúc 8 giờ (ghi chú của biên tập viên BlockBeats: ngày 27 tháng 2 năm 2020), chia sẻ loạt bài "Phân tích chuyên sâu về thuật toán đồng thuận" Giai đoạn đầu tiên của sự kiện chính thức mở cửa cho tất cả mọi người. Zhu Haichao, phó giám đốc Algorand Foundation, lần đầu tiên đưa ra bài chia sẻ trực tuyến có tiêu đề "Giới thiệu về thuật toán đồng thuận", giới thiệu các chủ đề như nguồn gốc, phân loại và bảo mật của thuật toán đồng thuận một cách đơn giản và dễ hiểu.

Kiến thức nền tảng

Hệ thống phân tán

Những người đầu tiên sử dụng thuật ngữ thuật toán đồng thuận thực ra là các nhà khoa học trong lĩnh vực hệ thống phân tán, vì vậy ở đây trước tiên chúng ta cần hiểu khái niệm về hệ thống phân tán.

Nói một cách đơn giản, hệ thống phân tán dùng để chỉ một nhóm máy tính làm việc cùng một lúc và liên lạc với nhau để hoàn thành mục đích tính toán tương tự. Mặc dù đây sẽ là một hệ thống bao gồm nhiều máy tính nhưng đối với người dùng sử dụng nó, nó sẽ giống như một máy tính. Một ví dụ điển hình là hệ thống máy bay, trong một chiếc máy bay có nhiều hệ thống máy tính, chúng giao tiếp và phối hợp với nhau để hoàn thành mục tiêu lớn lao là đưa bạn đi khắp nơi.

Trong hệ thống phân tán, chúng ta thường gọi mỗi máy tính là một nút. Các nút giao tiếp với nhau bằng cách gửi tin nhắn (tin nhắn). Các tin nhắn sẽ chứa các giao dịch (sự kiện) cần được các nút thực hiện. Sau khi nhận được giao dịch, các nút sẽ thực hiện độc lập các phép tính cần thiết và cập nhật kết quả được lưu cục bộ hoặc Kết quả được gửi đến máy khách (Client), tạo thành một hệ thống phân tán.

Máy trạng thái được sao chép

Rõ ràng, hệ thống blockchain cũng là một hệ thống phân tán.

Và mô hình được chính hệ thống blockchain sử dụng cũng là mô hình điển hình nhất trong các hệ thống phân tán - Replicad State Machine. Đầu tiên, hãy để tôi giải thích ngắn gọn cho những người bạn không có nền tảng về khoa học máy tính máy trạng thái là gì.

Máy trạng thái là một mô hình máy tính trừu tượng, dùng để chỉ một máy tính có thể lưu trữ một tập hợp các trạng thái (Trạng thái) Khi một máy tính nhận đầu vào (Input) hoặc sự kiện (Event) từ bên ngoài, nó sẽ trải qua quá trình chuyển trạng thái (StateTransition), như thể hiện trong hình trên.

Hãy lấy blockchain làm ví dụ. Mỗi nút blockchain về cơ bản là một máy trạng thái. Nó lưu số dư hiện tại của tất cả tài khoản và thông tin khác và thông tin này có thể được coi là trạng thái; khi nút nhận được giao dịch (Giao dịch) từ thế giới bên ngoài, nó sẽ tính toán số dư mới của mỗi tài khoản dựa trên thông tin giao dịch; Sau khi tính toán hoàn tất, nút sẽ lưu trữ số dư tài khoản mới và trở thành trạng thái mới, đồng thời hoàn tất quá trình chuyển đổi trạng thái.

Một mạng bao gồm nhiều nút như vậy được kết nối với nhau được gọi là bộ sao chép trạng thái. Trong trường hợp bình thường, khi nhận được giao dịch từ thế giới bên ngoài, tất cả các nút trong mạng sao chép trạng thái sẽ tính toán độc lập theo thông tin giao dịch và lưu trữ trạng thái mới; và trạng thái cuối cùng của nhiều nút sẽ vẫn nhất quán và được cung cấp cho bên ngoài world cùng một lúc. Cùng một đầu ra; mặc dù có nhiều máy trạng thái trong mạng, nhưng nhìn từ bên ngoài có vẻ như một máy trạng thái duy nhất đang được sử dụng. Thuật toán được sử dụng để giữ cho mạng sao chép trạng thái hoạt động bình thường và đáng tin cậy được gọi là Thuật toán đồng thuận.

Định nghĩa thuật toán đồng thuận

Bây giờ kiến thức nền tảng đã được giới thiệu, chúng ta có thể xác định thuật toán đồng thuận. Thuật toán đồng thuận cần cho phép mạng sao chép trạng thái đạt được các trạng thái sau:
(1) Tính nhất quán/Bảo mật (Thỏa thuận/Tính nhất quán): Tất cả Không -các nút bị lỗi có thể đạt được sự đồng thuận về chuỗi sự kiện (giao dịch) và cung cấp đầu ra trạng thái tương tự cho thế giới bên ngoài;
(2) Khả năng chấm dứt / Liveness (Chấm dứt/Liveness): Tất cả các nút không có lỗi cuối cùng đều có thể hoàn thành các phép tính và xuất ra một giá trị.
Có vẻ như việc triển khai một thuật toán như vậy không quá khó nhưng trên thực tế chúng ta cần phải vượt qua con đường đi đến sự đồng thuận. Ba ngọn núi lớn: đồng hồ, khả năng chịu lỗi và mạng.

Đồng hồ

Các sự kiện trong bộ sao chép trạng thái là tuần tự và vấn đề đầu tiên chúng ta cần giải quyết là làm thế nào để biết trình tự của các sự kiện này. Giải pháp đơn giản nhất cho vấn đề này là tìm một đồng hồ toàn cầu thống nhất và để tất cả các nút đánh dấu thời gian xảy ra sự kiện theo đồng hồ này. Tuy nhiên, đồng hồ như vậy không tồn tại trong hệ thống phân tán. Ngay cả khi chúng ta chọn đồng hồ ở đâu đó trên thế giới làm nguồn thời gian, thời gian cần thiết để các nút khác nhau truy cập vào đồng hồ sẽ khác nhau, điều này vẫn sẽ khiến mỗi nút chuỗi sự kiện tạo ra những quan sát khác nhau.

Trong bài báo năm 1978, Leslie Lamport, một nhà khoa học tính toán trong lĩnh vực hệ thống phân tán, đã đề xuất một phương pháp xác định thứ tự của các sự kiện dựa trên thứ tự trong đó tin nhắn đến. Tuy nhiên, phương pháp này vẫn dựa trên tiền đề là mỗi nút có đồng hồ vật lý "tương đối nhất quán". Trên thực tế, giả định này không ổn định, do sự khác biệt nhỏ giữa các đồng hồ vật lý nên sau một thời gian hoạt động chắc chắn sẽ có một số sai lệch giữa các đồng hồ và việc điều chỉnh thời gian ban đầu cũng là một nhiệm vụ tương đối khó khăn trong vấn đề kỹ thuật xã hội.

Vì vậy, đóng góp chính trong công việc của Lamport là chỉ ra rõ ràng cho chúng ta mô hình cơ chế sao chép trạng thái. , việc thiếu đồng hồ thống nhất là một bài toán lớn và cũng là một trong những bài toán cần có thuật toán đồng thuận để giải quyết.

Khả năng chịu lỗi

Mỗi nút trong bộ sao chép trạng thái là độc lập và xác suất xảy ra lỗi nút cũng độc lập. Nguyên nhân của các lỗi này có thể là do mạng của nút có vấn đề, sự cố phần cứng hoặc do mất điện, động đất, v.v., có thể gây ra lỗi nút.

Có một định nghĩa thống nhất về lỗi trong lĩnh vực hệ thống phân tán: miễn là một nút không thể hoạt động theo thỏa thuận đã định trước, tính toán bình thường và gửi nhận tin nhắn thì coi là lỗi (Fault).

Một mục đích thiết kế khác của thuật toán đồng thuận là khả năng chịu lỗi (Dung sai lỗi): nghĩa là cho phép một bộ sao chép trạng thái hệ thống Ngay cả khi một nút gặp lỗi, nó vẫn có thể đạt được sự đồng thuận về trạng thái và cung cấp đầu ra thống nhất cho thế giới bên ngoài.

Mạng

Mỗi nút trong bộ sao chép trạng thái cần dựa vào mạng để liên lạc với nhau và gửi tin nhắn; chúng có thể chọn dựa vào các giao thức hiện có như HTTP hoặc RPC để liên lạc hoặc có thể chọn giao thức tùy chỉnh. Nhưng bất kể giao thức mạng nào được chọn, mạng trong thế giới thực không phải lúc nào cũng đáng tin cậy. Tin nhắn gửi đi có thể bị trì hoãn, bị mất và việc truyền tải có thể bị gián đoạn.

Định nghĩa về điều kiện mạng trong hệ thống phân tán có thể được chia đơn giản thành hai loại: đồng bộ và không đồng bộ. Đồng bộ hóa có nghĩa là các tin nhắn trong mạng luôn có thể được truyền trong một khoảng thời gian không đổi nhất định t; không đồng bộ có nghĩa là độ trễ truyền trong mạng không có giới hạn trên như vậy. (Điều quan trọng là phải hiểu các khái niệm về đồng bộ hóa và không đồng bộ. Chúng ta sẽ sử dụng nó thường xuyên ở phần tiếp theo.) Đây cũng là một vấn đề mà thuật toán đồng thuận cần giải quyết, nó cần tính đến tính không ổn định của mạng và đảm bảo rằng hệ thống vẫn có thể đạt được sự đồng thuận của nhà nước.

Tóm tắt ngắn gọn, thuật toán đồng thuận cho phép mỗi nút không có lỗi trong mạng sao chép trạng thái đồng ý về thứ tự Một thuật toán đạt được sự đồng thuận (tính nhất quán) và luôn có thể cung cấp đầu ra (khả năng kết thúc) trong một thời gian xác định và cần có khả năng giữ cho hệ thống hoạt động bình thường và đáng tin cậy trong các điều kiện sau:

Không có đồng hồ thống nhất toàn cầu
Mỗi nút có thể bị lỗi độc lập
Tin nhắn được gửi qua mạng không phải lúc nào cũng đáng tin cậy

Định lý không thể giải được FLP

Hiểu thuật toán đồng thuận là gì và thuật toán đồng thuận cần những gì để giải quyết câu hỏi . Chúng ta cũng cần biết một định lý rất quan trọng trong lĩnh vực thuật toán đồng thuận: định lý không thể giải quyết được FLP. Định lý này lần đầu tiên được đề xuất trong bài báo “Không thể có sự đồng thuận phân tán với một quy trình bị lỗi” xuất bản năm 1985. Tác giả của nó là Fischer, Lynch và Paterson nên còn được gọi là định lý FLP.

Định lý này thực ra rất đơn giản:

　Trong bài viết này, chúng tôi chỉ ra rằng ngay cả khi chỉ có một nút bị lỗi thì không thể có bất kỳ thuật toán đồng thuận nào đạt được khả năng kết thúc trong điều kiện mạng không đồng bộ.》

Đây là kết luận đã được chứng minh và bình duyệt một cách nghiêm ngặt. Trên thực tế, nhiều nỗ lực cho đến nay đã chứng minh rằng lý thuyết này là không thể phá vỡ. Từ “bất kỳ” trong câu này tưởng như đã đặt dấu chấm hết cho kỷ nguyên vĩ đại của các thuật toán đồng thuận, nhưng rõ ràng các nhà khoa học ngoan cường không hề có ý định thừa nhận thất bại.

Trên thực tế, lý thuyết này có thể được hiểu theo một góc độ khác: nếu muốn triển khai thuật toán đồng thuận, chúng tôi chỉ Bạn có thể cân bằng giữa "điều kiện mạng không đồng bộ" và "khả năng kết thúc" và chọn một trong hai. Vì vậy, định lý này đã chỉ ra hướng đi cho nhiều thuật toán đồng thuận xuất hiện sau này, trong đó thuật toán ra đời sớm nhất và cổ điển nhất là Paxos.

Thuật toán đồng thuận Paxos

Bài báo đầu tiên về thuật toán đồng thuận Paxos được xuất bản vào năm 1989 và người đóng góp chính là Leslie Lamport. Thuật toán Paxos đã rút ra nhiều phiên bản cải tiến khác nhau trong quá trình phát triển tiếp theo và trở thành một họ giao thức, Raft quen thuộc cũng là một trong số đó. Trên thực tế, loại thuật toán này vẫn được sử dụng trong hệ thống của Google và Amazon cho đến ngày nay.

Hãy tập trung tìm hiểu cách Paxos phá vỡ định lý bất khả thi FLP nêu trên. Đối với hầu hết các hệ thống, khả năng kết thúc là không thể thương lượng được, nếu không thì toàn bộ hệ thống không thể thực hiện đầy đủ chức năng của nó cho người dùng. Do đó, việc lựa chọn Paxos trong bài viết giả định rằng điều kiện mạng là mạng đồng bộ, nghĩa là điều kiện của mạng không đồng bộ bị loại bỏ để đảm bảo khả năng kết thúc. Điều này có nghĩa là nó sẽ chỉ định một khoảng thời gian chờ trong quá trình thực hiện thuật toán. Khi không nhận được tin nhắn nào sau thời gian này, hãy tiếp tục chuyển sang bước tiếp theo.

Trên thực tế, giống như Paxos, tất cả các thuật toán đồng thuận tiếp theo về cơ bản đều chọn cách thỏa hiệp các điều kiện mạng trong khi vẫn duy trì độ tin cậy. Tuy nhiên, cần lưu ý rằng thuật toán đồng thuận Paxos không thể được sử dụng trong blockchain và lý do chính xác là vì trong blockchain, chúng ta cũng cần xem xét Bài toán tướng Byzantine nổi tiếng.

Khả năng chịu lỗi của Byzantine và thuật toán đồng thuận BFT

Khả năng chịu lỗi đã được đề cập ở trên khi giới thiệu các vấn đề mà thuật toán đồng thuận cần giải quyết. Nó đề cập đến hai loại nút: các nút có thể gửi và nhận tin nhắn bình thường và các nút lỗi không thể gửi tin nhắn bình thường . Nhưng trong môi trường thực tế hơn, đặc biệt là trong blockchain, một nút có thể làm điều gì đó nghiêm trọng hơn ngoại tuyến: nó có thể cố tình vi phạm các quy tắc của thuật toán đồng thuận bằng cách gửi một tin nhắn không chính xác.

Các nút như vậy có thể gửi các tin nhắn khác nhau đến các nút khác nhau hoặc một số nút có thể hợp lực để gửi thông tin sai nhằm đánh lừa các nút bình thường. . Trong các hệ thống phân tán, bài toán này được gọi là Bài toán tướng Byzantine và được chính thức đề xuất vào năm 1982. Công việc học tập này vẫn có sự tham gia của Leslie Lamport. Trong bài viết này, các nút ác này được gọi là Nút Byzantine. Một thuật toán đồng thuận vẫn có thể đảm bảo rằng mạng có thể đạt được sự đồng thuận trong mạng có các nút Byzantine được gọi là Thuật toán đồng thuận dung sai lỗi Byzantine, còn được gọi là Thuật toán đồng thuận BFT (Thuật toán đồng thuận dung sai lỗi Byzantine).

Paxos được đề cập ở trên không phải là thuật toán đồng thuận BFT, nghĩa là nó chỉ có thể hoạt động bình thường trong môi trường không phải Byzantine mạng; Nhưng điều cần thiết trong blockchain rõ ràng phải là thuật toán đồng thuận BFT. Tiếp theo, chúng ta có thể kết thúc chương câu chuyện cơ bản và chính thức bắt đầu giới thiệu một số thuật toán đồng thuận BFT.

Các giả định mạng về thuật toán đồng thuận

Như đã đề cập ở trên, hầu hết các thuật toán đồng thuận đều bỏ qua định lý FLP bằng cách xâm phạm các điều kiện mạng và giả định các điều kiện mạng khác nhau. Các giả định mạng này có thể được chia đại khái thành ba loại:
Mô hình không đồng bộ (AsynchronousModel) - nghĩa là độ trễ của tin nhắn trong mạng có thể là vô hạn
SynchronousModel - nghĩa là độ trễ của tin nhắn trong mạng nhỏ hơn một giá trị nhất định
Mô hình không đồng bộ một phần - Nghĩa là mạng đồng bộ vào "ngày tốt" và không đồng bộ vào "ngày xấu".

Mô hình không đồng bộ

Công việc tiêu biểu sử dụng mô hình không đồng bộ là HoneyBadgerBFT, được đề xuất vào năm 1983.
Sử dụng mô hình không đồng bộ có nghĩa là nó sẽ cần phải thỏa hiệp về khả năng kết thúc, nghĩa là nó sẽ không thể kết thúc trong một thời gian nhất định, nhưng Có một thời điểm kết thúc xác suất, tức là nó sẽ hội tụ dần dần và kết thúc theo thời gian. Thuật toán này khả thi về mặt lý thuyết, nhưng về mặt lý thuyết, thời gian kết thúc của nó là theo cấp số nhân và độ phức tạp của thông báo là o(n^3), nghĩa là mỗi vòng của quy trình đồng thuận cần gửi các giao dịch có khối lượng bằng số nút. Điều này có nghĩa là nó sẽ tiêu tốn rất nhiều tài nguyên băng thông và thời gian kết thúc có thể rất dài. Vì vậy, bản thân mô hình không đồng bộ mang tính lý thuyết nhiều hơn, có đóng góp về mặt học thuật nhưng về cơ bản khó áp dụng vào thực chiến.

Mô hình đồng bộ hóa

Đại diện cho việc sử dụng mô hình đồng bộ là LSP, cũng được Lamport đề xuất vào năm 1983.

Có giới hạn trên về độ trễ tin nhắn tối đa t trong mạng của mô hình đồng bộ. Bằng cách tận dụng triệt để t này, nó có thể đạt được khả năng chịu lỗi Byzantine trong khi đạt được tính có thể chấm dứt của sự đồng thuận. Sự đồng thuận Nakamoto được sử dụng trong Bitcoin về cơ bản là một mô hình mạng đồng bộ, nó giới hạn thời gian của mỗi sự đồng thuận thông qua bằng chứng công việc và có thể chấp nhận ít nhất một nửa số nút Byzantine.
Mô hình đồng bộ hóa cũng có một số hạn chế. Vì mỗi vòng đồng bộ hóa yêu cầu một độ trễ cố định nên khả năng phản hồi sẽ tương đối thấp: tức là tốc độ đồng thuận sẽ không điều chỉnh khi trạng thái mạng tốt hơn hoặc kém hơn, nhưng có thời gian đồng thuận cố định.

Mô hình không đồng bộ một phần

Mô hình không đồng bộ một phần là mô hình giả thuyết mạng thực tế nhất. Hầu hết các thuật toán đồng thuận mà chúng tôi sử dụng hiện nay đều dựa trên mô hình này, bao gồm PBFT, Tendermint, Hotstuf, v.v. Một đặc điểm của mô hình không đồng bộ một phần là nó thường có người đề xuất (Người lãnh đạo), người đề xuất một giá trị vào đầu mỗi vòng đồng thuận và sau đó các nút khác sẽ đồng thuận về giá trị này.

Các thuật toán sử dụng một số mô hình không đồng bộ phức tạp hơn và yêu cầu bằng chứng toán học nghiêm ngặt để chứng minh các thuật toán đồng thuận của chúng. và khả năng chấm dứt). Chính vì lý do này mà hầu hết các thuật toán đồng thuận trên thị trường thực sự có thể bị coi là giả mạo khi nhìn thoáng qua: chúng không có bằng chứng toán học nghiêm ngặt hoặc chúng không giải quyết được các vấn đề mà thuật toán đồng thuận lẽ ra phải giải quyết, và đơn giản được rút gọn thành các thuật toán rải rác.

BFCác giả định bảo mật của thuật toán đồng thuận T

Một giả định khác cần được đưa ra khi thiết kế thuật toán đồng thuận BFT là giả định về bảo mật.

Tất cả các thuật toán đồng thuận BFT sẽ đưa ra các giả định về số lượng nút Byzantine, tức là số lượng nút Byzantine là bắt buộc phải tính đến tổng số nút, số lượng cần phải thấp hơn một giá trị nhất định, nếu không thuật toán không thể đạt được chức năng của nó. Phổ biến nhất là khả năng chịu lỗi Byzantine 1/3, trong đó thuật toán có thể chịu đựng không quá một phần ba số nút Byzantine. PBFT, Hotstuff và Algorand, trong số những người khác, đều áp dụng giả định bảo mật này. Phân tích này được giới hạn ở các thuật toán đồng thuận sử dụng biểu quyết (Dựa trên đại biểu). Có một số thuật toán đặc biệt không thể sử dụng phương pháp này để mô tả tính bảo mật, chẳng hạn như sự đồng thuận của Satoshi Nakamoto trong Bitcoin.

Cần lưu ý rằng những gì được thảo luận ở đây chỉ là khả năng chịu đựng của chính thuật toán đồng thuận BFT đối với các nút xấu và không thể hiện tính bảo mật của hệ thống chuỗi khối. . Để đạt được tính bảo mật của hệ thống blockchain, chúng ta cũng cần một cơ chế khác mà chúng ta sẽ thảo luận ở chương trước.

Một số thuật toán đồng thuận BFT cổ điển

DLS

DLS Bài viết này là bài viết đầu tiên sử dụng mạng không đồng bộ một phần BFT giả thuyết thuật toán đồng thuận. Dưới đây là giải thích sơ bộ về cách hoạt động của thuật toán này để mọi người cùng nắm ý kiến:

(1) Mỗi cái vòng phải có Người đứng đầu. Sau khi mỗi vòng bắt đầu, mỗi nút trước tiên sẽ tiến hành một vòng giao tiếp và công bố giá trị mà nó cho là đúng.
(2) Nếu Người lãnh đạo nhận được các giá trị giống hệt n-f, nó sẽ phát lại giá trị đó cho tất cả các nút.
(3) Lúc này, khi mỗi nút nhận được giá trị này, nó sẽ "khóa" giá trị này rồi trao cho tất cả các nút khác. Phát sóng lại.
(4) Khi Người lãnh đạo nhận được giá trị bị khóa từ các nút f+1, nó sẽ sử dụng giá trị này làm giá trị cuối cùng.

Từ quá trình này, chúng ta vẫn có thể thấy một cách trực quan hơn cách nó thỏa mãn điều kiện nhất quán, tức là ít nhất là n-f các nút có thể đồng ý về giá trị cuối cùng. Ngoài ra, thuật toán đồng thuận cũng cần phải đáp ứng khả năng kết thúc, yêu cầu sử dụng các giả định mạng: nghĩa là có độ trễ tối đa (vào một ngày tốt) trong một số mạng không đồng bộ và nếu một nút có độ trễ này. trả lời trong thời gian đó, chúng tôi có thể coi nó là ngoại tuyến, do đó đảm bảo khả năng kết thúc của toàn bộ mạng.

PBFT và SBFT

PBFT Bài viết này tin rằng công việc trước đây quá lý thuyết để có thể áp dụng vào thực tế, do đó, một thuật toán mới và thực tế hơn dựa trên giả định về các mạng không đồng bộ một phần đã được đề xuất. PBFT có thể đồng thời đạt được sự an toàn và hoạt động với điều kiện tối đa (n-1)/3 nút là các nút bị lỗi (bao gồm cả các nút Byzantine). Đây đại khái là cách nó hoạt động:

(1) Đầu tiên cần có Người lãnh đạo và Người lãnh đạo sẽ nhận được giá trị từ khách hàng
(2) Trưởng nhóm truyền giá trị này tới tất cả các nút khác
(3) Mỗi nút nhận được Sau đó xác nhận giá trị này, sau đó phát giá trị này tới tất cả các nút khác và đợi ít nhất 2f nút khác phát tin nhắn
(4) Khi tin nhắn từ at nhận được ít nhất 2f nút khác, các giá trị được xác minh, sau đó phát lại và đợi tin nhắn từ ít nhất 2f nút khác được phát
(5) Nếu nhận lại tin nhắn từ 2f nút khác và các giá trị là chính xác, hãy xác nhận rằng giá trị đó là giá trị cuối cùng
Trong quy trình trên, độ phức tạp của thông báo là O(n^2) khi không có vấn đề gì với Người lãnh đạo, nhưng khi cần thay đổi thì cần phải gửi thông báo O(n^3). Tương tự, thuật toán PBFT cũng có thể chứng minh bằng chứng toán học rằng sau khi quá trình đồng thuận hoàn tất, ít nhất các nút n-f có thể đạt được sự đồng thuận về một giá trị, tức là đạt được tính nhất quán của sự đồng thuận.

SBFT chủ yếu thực hiện một số tối ưu hóa dựa trên PBFT: chủ yếu thông qua việc sử dụng chữ ký ngưỡng (Chữ ký ngưỡng) để giảm lớp phức tạp của thông điệp.

Tendermint

Tendermint là một thuật toán đồng thuận BFT do Cosmos đề xuất. Đặc điểm của nó là độ phức tạp của thông báo vẫn là O(n^2) trong trường hợp Leader Fail. Điều này là do Tendermint sử dụng chính xác quy trình đồng thuận giống nhau trong các trường hợp thông thường và trong các trường hợp thay đổi, do đó độ phức tạp cũng như nhau.

Nội dung hấp dẫn

Hotstuff là thuật toán đồng thuận BFT mới nhất được đề xuất trong những năm gần đây. Công trình này tóm tắt quy trình bỏ phiếu trong thuật toán đồng thuận BFT trước đó, dẫn đến thuật toán đồng thuận hợp lý hơn.

Hotstuff sử dụng một khái niệm gọi là Chứng chỉ đại biểu (QC). Sau khi một khối nhất định có đủ số lượng QC, khối đó sẽ có thể được đánh giá là cuối cùng đồng thời, thuật toán chỉ định logic để chọn QC, từ đó đảm bảo tính nhất quán của thuật toán đồng thuận; ngoài ra, mô-đun Máy tạo nhịp tim được thiết kế để đảm bảo tính kết thúc của thuật toán.

Cũng có thể thấy từ bảng trên rằng thuật toán này có độ phức tạp của thông điệp là nhỏ nhất; đồng thời, các đặc tính hợp lý của nó cũng làm cho việc triển khai kỹ thuật của nó trở nên rất đơn giản. Điều đáng nói là Libra của Facebook cũng sử dụng Hotstuff làm thuật toán đồng thuận.

Thuật toán

Sự đổi mới của Algorand là nó áp dụng phương pháp lấy mẫu mật mã cho thuật toán đồng thuận BFT, cho phép đạt được sự đồng thuận nhanh chóng trong một mạng có số lượng lớn các nút tham gia. Algorand sử dụng công cụ VRF (Chức năng ngẫu nhiên có thể xác minh) để chọn ngẫu nhiên một tập hợp con các nút từ tất cả các nút để tham gia vào quá trình đồng thuận, do đó làm giảm đáng kể số lượng nút thực sự tham gia vào quá trình đồng thuận.

Quy trình đồng thuận của nó được chia thành hai vòng: đầu tiên, mỗi nút sẽ tính toán xem nó có thành công hay không bằng cách chạy VRF Bạn có thể trở thành người dẫn đầu vòng đồng thuận này, sau đó chọn một ủy ban đồng thuận (Commetee) theo cách tương tự, chạy thuật toán đồng thuận BA (Thỏa thuận Byzatine) nhanh, bỏ phiếu cho sự đồng thuận về khối do người lãnh đạo đề xuất và phát kết quả cuối cùng tới tất cả các nút trong mạng.

Thuật toán đồng thuận Algorand có một số tính năng rất hay:

Tốc độ đồng thuận nhanh: Ngay cả với số lượng nút lớn (lên tới 10.000), nó có thể có tốc độ đồng thuận cực nhanh và hiệu quả xử lý giao dịch cực cao.

Không phân nhánh: Trong số các thuật toán đồng thuận được đề cập ở trên, chỉ có thể sử dụng đồng thuận Nakamoto trong môi trường có số lượng nút lớn. Tuy nhiên, đồng thuận Nakamoto chắc chắn sẽ tạo ra các fork, điều này sẽ ảnh hưởng đến tốc độ xác nhận giao dịch (nói chung bạn cần đợi sáu khối để xác nhận), trong khi Algorand sẽ không tạo ra các fork, điều đó có nghĩa là tất cả các giao dịch có thể được thực hiện trong một khối xác nhận.

Chống phân mảnh mạng: Khi các nút trong mạng nhận được các cuộc tấn công cấp mạng (chẳng hạn như tấn công từ chối DDoS tấn công dịch vụ ), có thể dẫn đến phân mảnh mạng và thuật toán đồng thuận chung không tính đến cuộc tấn công này trong mô hình bảo mật của nó; phiên bản mới nhất của thuật toán Algorand đã tính đến tình huống này và đạt được ngay cả trong trường hợp phân mảnh mạng , có thể đạt được sự đồng thuận và có thể đạt được sự phục hồi nhanh chóng.

Đây là những tính năng rất cần thiết trong các hệ thống phân tán thực tế, đặc biệt là hệ thống blockchain. Như vậy có thể thấy Algorand là một thuật toán đồng thuận rất thiết thực và rất phù hợp cho blockchain.

Bảo mật chuỗi khối

Ở đây chúng ta đã tìm hiểu thuật toán đồng thuận BFT là gì, các giả định về mạng và giả định bảo mật của nó, đồng thời chúng ta cũng đã tìm hiểu về một số thuật toán cổ điển. Tuy nhiên, blockchain vẫn cần giải quyết một vấn đề: hầu hết các giao thức đồng thuận BFT ở trên chỉ có thể đảm bảo hoạt động bình thường khi số lượng nút Byzantine nhỏ hơn 1/3, nhưng một blockchain, đặc biệt là một blockchain không được phép (tức là bất kỳ ai cũng có thể tham gia và trở thành một nút) và số lượng nút độc hại có thể lớn hơn nhiều so với tỷ lệ này. Trong trường hợp này, làm cách nào chúng ta có thể đảm bảo tính bảo mật của giao thức đồng thuận và blockchain?

Tại thời điểm này, cần có một số cơ chế truy cập nút. Cơ chế truy cập nút chung sẽ sử dụng các biện pháp khuyến khích kinh tế để khuyến khích các nút tốt tham gia vào quá trình đồng thuận và ngăn cản những người làm điều xấu, từ đó đảm bảo rằng các nút trong mạng blockchain đáp ứng các giả định bảo mật mà thuật toán đồng thuận BFT yêu cầu. .

Bây giờ chúng tôi sẽ giới thiệu ngắn gọn ba cơ chế tiếp nhận phổ biến nhất: PoW, PoC và PoS. Cần lưu ý rằng cuộc thảo luận sau đây về cơ chế tiếp nhận không còn nằm trong phạm vi của thuật toán đồng thuận. Chúng là những cơ chế phải phối hợp với thuật toán đồng thuận trong hệ thống blockchain để đảm bảo an ninh hệ thống. Đây là lý do tại sao về bản chất PoW và PoS không phải là thuật toán đồng thuận.

Bằng chứng công việc

Cơ chế chứng minh khối lượng công việc yêu cầu các nút thực hiện các hoạt động tập trung để tính toán một giá trị (được gọi là giá trị băm) đáp ứng các yêu cầu cụ thể và có thể suy luận đại khái rằng nút đó sẽ sử dụng để tính toán giá trị này. Tài nguyên máy tính là bao nhiêu đã sử dụng. Cơ chế này lần đầu tiên được sử dụng trong ứng dụng ngăn chặn thư rác, nhưng ứng dụng nổi tiếng nhất của nó có lẽ là Bitcoin. Dưới đây chúng tôi sẽ lấy Bitcoin làm ví dụ để giải thích cách PoW đảm bảo tính bảo mật của blockchain.

Giao thức Bitcoin yêu cầu rằng nếu một nút muốn tham gia vào sự đồng thuận với tư cách là một nút thì nút đó phải gửi chứng chỉ PoW đủ điều kiện. Giao thức Bitcoin đảm bảo rằng mỗi phép tính PoW mất khoảng 10 phút, do đó đáp ứng các giả định mạng đồng bộ theo yêu cầu đồng thuận của Satoshi. Theo cách này, khi một nút muốn tham gia đồng thuận, nó phải tiêu tốn đủ tài nguyên tính toán, trong Bitcoin, những tài nguyên này còn được gọi là sức mạnh tính toán. Đối với một đối thủ (Đối thủ), nếu anh ta muốn tấn công thành công mạng Bitcoin và buộc mọi người phải đồng ý thành công về thông tin độc hại mà anh ta gửi theo các hạn chế của sự đồng thuận của Satoshi Nakamoto, anh ta sẽ cần phải tiếp tục dành rất nhiều nguồn lực để Kiểm soát một lượng lớn sức mạnh tính toán thường được gọi là cuộc tấn công 51%.

Bảo mật về cơ bản là tỷ lệ giữa chi phí tấn công và lợi ích tấn công. Trong trường hợp Bitcoin, dựa trên giá sức mạnh tính toán trên thị trường khai thác và giá trị thị trường của Bitcoin, chúng ta có thể ước tính đại khái chi phí của một cuộc tấn công 51% và lợi ích có thể thu được nếu nó thành công. So sánh cả hai, chúng ta có thể thấy rằng chi phí tấn công quá cao và lợi ích tấn công không tương xứng là đủ để tạo thành một bức tường ngăn cản những kẻ tấn công. Chính vì điều này mà PoW thực sự có thể đảm bảo tính bảo mật của hệ thống Bitcoin.

Bằng chứng về năng lực

Chứng minh không gian PoC là một cơ chế truy cập nút tương đối phổ biến trong thời gian gần đây. Ý tưởng chung là sử dụng dung lượng ổ cứng để thay thế tài nguyên máy tính trong PoW. Các nút có thể cung cấp bằng chứng để chứng minh họ có bao nhiêu dung lượng lưu trữ và các nút có không gian lớn hơn có thể có nhiều quyền tham gia đồng thuận hơn.

PoC về cơ bản tương tự như PoW, ngoại trừ chi phí tính toán liên tục được thay thế bằng việc mua dung lượng ổ cứng . chi phí một lần. Ưu điểm của cơ chế này là thiết bị phần cứng không yêu cầu thiết bị làm mát mạnh như vậy nên tiếng ồn phát ra sẽ nhỏ hơn rất nhiều, đồng thời chi phí chính đã thay đổi từ giá điện sang giá đơn vị không gian lưu trữ, cho phép những người không có nguồn lực để tham gia.

Tuy nhiên, điều này không có nghĩa là các dự án sử dụng PoC có cùng mức độ bảo mật như PoW. Chúng ta cũng cần xem xét khác Liệu thuật toán đồng thuận có đáng tin cậy hay không, v.v.

Bằng chứng về cổ phần

PoS Proof of Stake là một cơ chế tiếp nhận nút cổ điển khác. Đó là một sự trừu tượng hơn nữa của hai phương pháp trên, tính toán trực tiếp khả năng của nút tham gia trọng số đồng thuận dựa trên số lượng tiền điện tử được sở hữu hoặc thế chấp bởi nút.

Các trường hợp nổi tiếng hơn bao gồm PoS được ủy quyền và PoS liên kết. Trường hợp trước cho phép tất cả những người nắm giữ tiền tệ thế chấp tiền của họ vào một nút nhất định, do đó khiến nó trở thành một trong những 21 nút đồng thuận; nút sau cho phép tất cả các nút thế chấp mã thông báo cho chính chúng và tính toán trọng số của việc tham gia đồng thuận dựa trên số lượng mã thông báo được thế chấp.

Algorand cũng sử dụng PoS làm cơ chế tiếp nhận nút. Phương pháp này rất đơn giản và trực quan. Số lượng token sở hữu bởi mỗi nút được sử dụng trực tiếp làm trọng số lựa chọn của nó bằng thuật toán VRF: nghĩa là, càng có nhiều xu trong tài khoản thì càng dễ được chọn. tham gia thống nhất. Giáo sư Silivo Micali, người sáng lập Algorand, gọi cơ chế này là Pure PoS vì nó không yêu cầu bất kỳ ai phải thế chấp token và tất cả các token đều được lưu hành bất cứ lúc nào.

Là người lý trí, người dùng luôn ưu tiên tính thanh khoản nên đối với một cơ chế như Bonding PoS thì không có nhiều người sẽ lấy tiền xu để thế chấp, điều này cũng làm giảm chi phí tấn công mạng blockchain và gây ra mối đe dọa cho tính bảo mật của blockchain và tài sản trên đó.

Cơ chế của Pure PoS không yêu cầu người dùng thế chấp token. Tất cả các token lưu hành trong mạng về cơ bản là Tất cả những điều này sẽ tạo thành chi phí tấn công, làm tăng đáng kể ngưỡng tấn công, do đó cải thiện tính bảo mật của nền tảng Algorand và tài sản trên đó.

Tóm tắt

Chúng tôi bắt đầu từ khái niệm cơ bản nhất về hệ thống phân tán, giới thiệu định nghĩa về thuật toán đồng thuận và các vấn đề mà nó cần giải quyết, đồng thời mở rộng nó sang lĩnh vực thuật toán đồng thuận BFT; đồng thời, chúng tôi đã giải thích đại khái một số vấn đề thuật toán đồng thuận BFT cổ điển nhất và cuối cùng là chủ đề bảo mật blockchain sẽ được thảo luận.
Sau phần này, chúng tôi sẽ giải thích sâu hơn về thuật toán đồng thuận công nghệ đen Algorand để giúp mọi người hiểu rõ hơn về chủ đề đồng thuận thuật toán. .

Liên kết nguồn: mp.weixin.qq.com

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia