Tác giả gốc: Cỗ máy linh hồn

Do nguyên tắc Bất khả thi của FLP,

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

Vì vậy, đừng lãng phí thời gian để thiết kế một thuật toán đồng thuận cho một mạng hoàn toàn không đồng bộ. Giải pháp là tăng cường các yêu cầu đối với mạng và yêu cầu mạng phải đồng bộ hoặc đồng bộ một phần (từ không đồng bộ sang đồng bộ hoặc bán đồng bộ, trạng thái mạng trở nên tốt hơn) hoặc nới lỏng các yêu cầu về tính hữu hạn, không yêu cầu tính hữu hạn xác định , chỉ yêu cầu Probabilistic Finality là được. Cũng có thể làm cả hai cùng một lúc.

Bảng 1 So sánh các thuật toán đồng thuận khác nhau

Nội dung của bảng trên được giải thích chi tiết dưới đây.

Finality

Finality trông giống với Safety, Consistency, nhưng nó có vẻ khác, điều này rất khó hiểu.

Hiểu một cách đơn giản, bạn có thể nghĩ rằng Finality, Safety và Consistency là những từ đồng nghĩa, tức là Finality=Safety=Consistency.

Để hiểu sâu hơn, tôi nghĩ Finality là một phức hợp, Finality>Safe>Consistency. Tính nhất quán được áp dụng cho tất cả các hệ thống phân tán, bao gồm các môi trường đáng tin cậy như Hadoop và các môi trường không đáng tin cậy như Bitcoin; An toàn được áp dụng cho các môi trường Byzantine; Finality là một thuật ngữ trong kịch bản chuỗi khối và chuỗi khối là một Tập hợp con kịch bản Byzantine (vấn đề Byzantine không có -các giải pháp chuỗi khối ngoài chuỗi khối). Tính nhất quán là chữ C trong lý thuyết CAP, nó tổng quát hơn và đòi hỏi ít yêu cầu hơn Finality. Finality hàm chứa nhiều ý nghĩa mạnh mẽ hơn Consistency. Cuối cùng bao gồm tất cả các ý nghĩa sau đây:

• Dữ liệu của tất cả các nút phải nhất quán. Máy khách gửi thao tác đọc tới bất kỳ nút nào và kết quả sẽ giống nhau. Đây là Tính nhất quán được đề cập trong CAP. Thuật ngữ này được áp dụng cho tất cả các hệ thống phân tán, bao gồm các môi trường đáng tin cậy như Hadoop và các môi trường không đáng tin cậy như Bitcoin.
  

• Tất cả các nút phải đảm bảo rằng chúng không rơi vào trạng thái xung đột và chia rẽ lẫn nhau, nghĩa là an toàn. Thuật ngữ này được áp dụng cho lĩnh vực khả năng chịu lỗi của Byzantine, trong môi trường mở như Byzantine, một nút độc hại sẽ phát hai thông báo trái ngược nhau (chẳng hạn như giao dịch chi tiêu gấp đôi), khiến tất cả các nút trong toàn bộ mạng rơi vào trạng thái chia tách , không thể đạt được sự nhất quán, điều này phá hủy bản chất của An toàn. Tất cả các thuật toán đồng thuận Byzantine cần xử lý vấn đề về các nút độc hại để đảm bảo an toàn cho toàn bộ mạng.
  

• Khi một giao dịch đi vào một khối, giao dịch đó sẽ không thể hủy ngang, tức là Tính không thay đổi. Trong kịch bản chuỗi khối, để đảm bảo An toàn, không chỉ cần xử lý vấn đề giao dịch chi tiêu gấp đôi do các nút độc hại phát hành mà còn phải ngăn chặn các nút độc hại thu hồi các giao dịch đã được đóng gói thành các khối. Bởi vì chuỗi khối là một danh sách liên kết đơn và cấu trúc tuyến tính, các nút độc hại về mặt lý thuyết có thể bắt đầu từ một khối cũ, rẽ nhánh một chuỗi mới dài hơn, hủy bỏ tất cả các giao dịch mà chúng đã gửi và đặt lại tiền của chúng (một dạng khác của chi tiêu gấp đôi)
  

Tóm lại, Finality = Nhất quán + An toàn + Bất biến.

Liveness

Liveness có thể coi là tương đương với Availability trong CAP. Khi một phân vùng xảy ra trên mạng, chẳng hạn như đứt cáp quang biển và Internet toàn cầu được chia thành hai phần, liệu toàn bộ hệ thống chuỗi khối có thể ghi các giao dịch mới một cách bình thường không? Tôi thích thuật toán đồng thuận của Finality, lúc này tôi sẽ chọn chờ đợi vô thời hạn, giao dịch mới không thể được ghi cho đến khi cáp quang biển được sửa chữa và Internet hai bên có thể tương tác với nhau. Tôi thích thuật toán đồng thuận của Availability, tại thời điểm này, cả hai các mạng sẽ hoạt động độc lập và dữ liệu sẽ được tách biệt. Dữ liệu trong các nút đầy đủ trở nên không nhất quán.

Ví dụ, Tendermint là loại này, hy sinh Liveness để theo đuổi Deterministic Finality. Giả sử rằng cáp quang biển bị đứt và mạng được chia thành hai bên, mỗi bên có một nửa số người xác nhận, vì vậy trong giai đoạn bỏ phiếu và cam kết, tất cả người xác nhận ở mỗi bên bỏ phiếu cho một khối đề xuất nhất định 100% và chỉ có thể nhận Tối đa 50% khối đề xuất. Việc bỏ phiếu không thể đạt được 2/3, vì vậy toàn bộ mạng blockchain sẽ đợi vô thời hạn cho đến khi 2/3 phiếu được thu thập. Trong khoảng thời gian chờ đợi này, khối tiếp theo không thể được tạo và các giao dịch mới không thể được ghi và toàn bộ mạng bị tê liệt.

Khi Bitcoin gặp phải kiểu phân đoạn mạng này, hai phần của hệ thống Bitcoin sẽ tiếp tục di chuyển về phía trước và các giao dịch mới vẫn có thể được viết để tạo các khối mới. Khi cáp ngầm được sửa chữa và Internet ở cả hai bên được kết nối, thì Chọn Hợp nhất.

Trước khi cáp quang biển bị đứt, trạng thái của tất cả các nút đầy đủ trên thế giới là nhất quán, như thể hiện trong hình dưới đây:

Khi cáp quang biển bị đứt, mạng toàn cầu được chia thành hai phần và hai phần sẽ tạo ra các khối độc lập, lúc này hai bên không nhất quán nhưng không thể nhận thức được nhau, cho rằng mình vẫn là một chuỗi khối tuyến tính , như sau hình ảnh:

Ở bên trái và bên phải, mặc dù một khối mới vẫn được khai thác cứ sau 10 phút, nhưng giá trị băm của khối 07 ở bên trái và khối 07 ở bên phải không bằng nhau. Tại thời điểm này, mạng Bitcoin vẫn khả dụng nhưng Finality đã bị phá hủy.

Khi sửa xong cáp quang biển, lúc này 2 bên đồng bộ block với nhau sẽ nhận ra có 1 fork như hình sau:

Bây giờ trạng thái của tất cả các nút đầy đủ trên thế giới trở thành hình trên và có một ngã ba. Vì chiều cao của cả hai bên là 8 nên không thể quyết định ngã ba nào là đúng. Lúc này, nó phụ thuộc vào bên nào hỗ trợ thợ mỏ và bên nào được tính. Ligao, bên nào tạo khối mới trước sẽ thắng và chuỗi ngắn hơn sẽ bị loại bỏ. Ví dụ: nếu bên phải tạo khối mới trước thì bên phải sẽ thắng và bên trái fork sẽ bị loại bỏ. Tất cả các nút đầy đủ Dữ liệu trong lại trở thành một chuỗi khối tuyến tính, đạt được sự đồng thuận, như thể hiện trong hình bên dưới:

Trên thực tế, ngay cả khi cáp quang biển liên tục và mạng không có phân vùng, việc hai thợ mỏ đào một khối mới cùng một lúc sẽ thường xảy ra, lúc này là một cuộc thi xem ai là người may mắn. và bất kỳ ngã ba nào kế thừa khối mới sẽ giành chiến thắng. Điều đó có nghĩa là, Bitcoin sẽ không bao giờ có trạng thái nhất quán xác định về mặt lý thuyết và các nhánh sẽ xuất hiện bất cứ lúc nào ở bất kỳ độ cao nào, vì vậy Bitcoin hy sinh một chút Finality để đổi lấy Liveness mạnh hơn.

Network Assumption

Tất cả các thuật toán đồng thuận phân tán đều có một giả định ngầm định về mạng.
Hãy để tôi nói về việc phân loại mạng trước:

Đồng bộ hóa: Tin nhắn phải được gửi trong một khoảng thời gian T nhất định. Giá trị T của giới hạn trên là một hằng số đã biết và tất cả các nút đều biết điều đó. Nếu tin nhắn không được gửi trong thời gian T, nó sẽ không được tính vào tin nhắn và nút sẽ nghĩ rằng tin nhắn đã bị mất và sẽ không tiếp tục chờ đợi nó. Tất cả các nút đều có trật tự và mỗi khi T đi qua, chúng sẽ tiến lên một bước, rất gọn gàng.

Bán đồng bộ: Tin nhắn phải được gửi trong một khoảng thời gian T nhất định, nhưng giá trị của T không phải là một giá trị cố định mà thay đổi linh hoạt, ví dụ, nó được tính toán động theo các điều kiện mạng. tất cả các nút

Không đồng bộ: Tin nhắn sẽ đến bất cứ lúc nào, có thể rất nhanh, cũng có thể rất chậm, tóm lại là không có giới hạn trên (upper bound) rõ ràng, thậm chí có độ trễ vô thời hạn, dù có đến muộn thế nào thì nút phải chấp nhận và xử lý tin nhắn, không thể đơn giản là Hủy bỏ tin nhắn do hết thời gian chờ

Giả định của Bitcoin trên mạng là mạng đồng bộ và giới hạn thời gian là khoảng 10 phút. Sau khi Người khai thác đào ra một khối, nó sẽ phát sóng cho toàn bộ mạng. Lúc này, toàn bộ hệ thống Bitcoin mong đợi rằng khối này sẽ là tất cả trong vòng 10 phút Nút đầy đủ trực tuyến đã nhận được nó, có nghĩa là cứ sau 10 phút, tất cả các nút đầy đủ sẽ tiến một bước gọn gàng, tức là thêm một khối vào cuối chuỗi khối của chính họ. Ngay cả khi tốc độ mạng rất nhanh, chẳng hạn như trong vòng chưa đầy 3 phút, tất cả các nút đầy đủ đã nhận được khối mới này và Bitcoin vẫn sẽ tiếp tục tăng sau mỗi 10 phút (một khối mới được tạo ra). Ethereum cũng tương tự, nhưng giới hạn thời gian là 15 giây.

Tendermint giả định rằng mạng là bán đồng bộ trong giai đoạn đề xuất, bởi vì sẽ có một khoảng thời gian chờ trong bước này. một khối trống sẽ được tạo ra. Cho đến khi vòng tròn tính điểm cho người đề xuất tiếp theo. Tendermint cần thu thập hơn 2/3 số phiếu bầu ở cả prevote và precommit, điều này đang chờ đợi vô hạn, tức là trong hai giai đoạn này, người ta cho rằng mạng không đồng bộ. Cuối cùng, các yêu cầu của Tendermint đối với mạng là bán đồng bộ.

pBFT không đồng bộ trong ba giai đoạn chuẩn bị trước, chuẩn bị và cam kết.Vì nó không đồng bộ và không có cơ chế hết thời gian, làm sao nó có thể tiến lên? Nếu bạn thu thập được hơn 2/3, bạn có thể đi tiếp. Tuy nhiên, khi tất cả các nút nhận được yêu cầu từ máy khách, chúng sẽ bắt đầu hẹn giờ, nếu yêu cầu không được hoàn thành trong một khoảng thời gian nhất định, Chế độ xem thay đổi sẽ được kích hoạt. Phần Thay đổi Chế độ xem là bán đồng bộ.

Ở đây bạn có thể đánh giá cao sự đơn giản hóa của Tendermint so với pBFT. Tendermint đã chuyển cơ chế hết thời gian chờ sang giai đoạn đề xuất (tương đương với giai đoạn chuẩn bị trước của pBFT). Nếu người đề xuất phát khối đề xuất trong thời gian quy định, nó sẽ chuyển sang bước tiếp theo. Nếu hết thời gian, nó cũng sẽ tiếp tục sang bước tiếp theo. Nhưng đây là khối đề xuất là một khối trống (quá trình bỏ phiếu trước và cam kết trước sẽ hoàn tất khi khối trống, nhưng chiều cao khối sẽ không tăng thêm 1, điều này tương đương đến mạng không hoạt động cho đến khi quay vòng sang nút tiếp theo Nút đề xuất mới phát lại khối đề xuất mới). Điều đó có nghĩa là, trong mọi trường hợp, giai đoạn đề xuất sẽ chuyển sang bước tiếp theo. Nhưng quá trình chuẩn bị trước của Tendermint không đồng bộ và nó có thể bị kẹt mãi mãi. pBFT đã chuyển cơ chế hết thời gian chờ sang phần Thay đổi chế độ xem, vì vậy pBFT có thêm bước Thay đổi chế độ xem, phức tạp hơn một chút so với Tendermint. Tendermint thay thế nút đề xuất bằng cách gửi các khối trống và quay vòng, trong khi pBFT thay thế nút chính thông qua Thay đổi Chế độ xem. Tendermint loại bỏ bước Thay đổi chế độ xem phức tạp.

Ngoài việc loại bỏ Thay đổi Chế độ xem, Tendermint còn được đơn giản hóa ở một nơi khác, đó là tất cả thông tin về Tendermint đều được lưu trữ trong chuỗi khối. Tuy nhiên, pBFT đã được đề xuất vào năm 1999. Vào thời điểm đó, không có thứ gọi là chuỗi khối, do đó, mặc dù tất cả các nút của pBFT đều có dữ liệu nhất quán nhưng dữ liệu được lưu trữ theo cách phi tập trung. Dữ liệu của từng nút của pBFT bao gồm:

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 là cơ sở dữ liệu phân tán, ví dụ trước khi cơ sở dữ liệu DBMS như MySQL xuất hiện, người ta ghi dữ liệu vào tệp và lưu trữ trên đĩa cứng, phát minh ra nhiều định dạng tệp lạ và phương pháp tổ chức. Với MySQL, việc quản lý dữ liệu thuận tiện hơn rất nhiều. Tương tự, Tendermint lưu trữ tất cả dữ liệu trong chuỗi khối, pBFT không có cơ sở dữ liệu phân tán như chuỗi khối và tất cả các nút cần tự quản lý dữ liệu trên đĩa cứng. Ví dụ: để nén nhật ký tin nhắn, loại bỏ tin nhắn cũ và tiết kiệm dung lượng đĩa cứng, khái niệm điểm kiểm tra được giới thiệu.

Mối quan hệ giữa Tendermint và pBFT tương tự như mối quan hệ giữa Raft và Paxos. Tendermint là phiên bản đơn giản hóa của pBFT, đây là phiên bản đơn giản hóa của pBFT cho kịch bản chuỗi khối.

Hình dưới đây là lưu đồ thuật toán của Tendermint:

Hình dưới đây là lưu đồ thuật toán của pBFT:

Người giới thiệu

Người giới thiệu

1. 1999.Castro.  Practical Byzantine Fault Tolerance

2. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains

3. Consensus Compare: Casper vs. Tendermint

4. A Proof of Stake overview

5. Compared with traditional PBFT, what advantage does Tendermint algorithm has?

6. Synchronous, partially synchronous and asynchronous consensus algorithms

7. GRANDPA Block Finality in Polkadot: An Introduction (Part 1)

8. Finality in Blockchain Consensus