Tác giả gốc: Cỗ máy linh hồn
Tác giả gốc: Cỗ máy linh hồn
Tendermint là một dự án mã nguồn mở của Tendermint, là một biến thể của thuật toán pBFT. 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.
Quy trình cốt lõi của thuật toán
Luồng thuật toán cốt lõi của Tendermint được hiển thị trong hình bên dưới:
Trước tiên, thuật toán Tendermint chọn ngẫu nhiên một số nút làm Trình xác thực (cách chọn nút xác minh? Xem "Cách chọn nút xác minh" bên dưới), sau đó chọn một trong các trình xác thực làm nút đề xuất. Nút đề xuất bắt đầu theo dõi và thu thập tất cả các giao dịch trong toàn mạng. Sau vài phút, nó sẽ lắp ráp một khối mới và phát nó ra toàn mạng. Đây là khối đề xuất. Sau khi nhận được khối đề xuất này, tất cả các nút của trình xác thực trong toàn bộ mạng bắt đầu đọc tất cả các giao dịch trong khối này và xác minh từng giao dịch một. Nếu không có vấn đề gì, họ sẽ gửi một thông báo biểu quyết trước khi bỏ phiếu, bày tỏ sự đồng ý của họ với điều này chặn và bỏ phiếu khẳng định. Nếu phát hiện thấy có giao dịch bất hợp pháp trong khối, nó sẽ bỏ phiếu phủ định và các thông báo bỏ phiếu này sẽ được phát tới tất cả các nút của trình xác thực, vì vậy mỗi nút của trình xác thực sẽ không chỉ gửi đi một tin nhắn bỏ phiếu, mà còn thu thập tin nhắn bỏ phiếu của người khác. Khi số lượng phiếu bầu đồng ý vượt quá 2/3, một tin nhắn bỏ phiếu trước cam kết sẽ được gửi, đây là giai đoạn bỏ phiếu thứ hai và mỗi nút cũng đang theo dõi và thu thập trước cam kết tin nhắn bỏ phiếu. Khi số lượng phiếu bầu trước khi cam kết được thu thập bởi nút trình xác thực vượt quá 2/3, điều đó có nghĩa là khối đó đã được đa số người chấp thuận và bạn có thể viết khối này vào chuỗi khối cục bộ một cách an toàn và nối nó vào cuối hoàn thành cam kết. Đồng thời, chiều cao khối tăng thêm 1 và chỉ số nút của người đề xuất cũng tăng thêm 1, bước vào vòng (vòng) tiếp theo và bắt đầu đề xuất các khối mới.
Mô tả ở trên là quy trình bình thường trong 90% thời gian, nghĩa là chu kỳ lớn được biểu thị bằng mũi tên màu xanh lam. Tiếp theo, hãy nói về vòng lặp nhỏ được chỉ định bởi mũi tên màu đỏ ở vòng tròn bên trong. Trong hầu hết các trường hợp, một khối chỉ cần một vòng để hoàn thành xác nhận và đạt được sự đồng thuận, tuy nhiên, đôi khi trạng thái mạng không tốt và thường xảy ra thời gian chờ, lúc này nó sẽ bước vào quy trình màu đỏ ở vòng trong. Vì chỉ có một người đề xuất có quyền tạo khối trong mỗi vòng, chúng ta nên làm gì nếu người đề xuất gác máy hoặc mạng không tốt và hết thời gian chờ? Tất cả mọi người không thể chờ đợi người đề xuất này mãi mãi, thuật toán rõ ràng không được thiết kế ngu ngốc như vậy, và có một điểm thất bại rõ ràng. Trong giai đoạn đề xuất của nút đề xuất, tất cả các nút trình xác nhận sẽ bắt đầu hẹn giờ và đặt khoảng thời gian chờ thành T (giá trị của T được tính toán động theo các điều kiện mạng). Nếu không nhận được thông báo mới từ nút đề xuất trong giai đoạn này khối thời gian, coi như nút đề xuất bị treo, tất cả các nút trình xác thực sẽ không tiếp tục chờ đợi mà sẽ ngay lập tức tạo ra một khối trống có cấu trúc đặc biệt trên máy cục bộ, giả vờ rằng khối trống được nhận từ nút đề xuất , do đó, bất kể điều gì xảy ra, trong thời gian T, một khối đề xuất sẽ được nhận, khối bình thường hoặc khối trống. Sau đó tiến hành bỏ phiếu trước và bỏ phiếu trước cam kết trên khối này. Nếu người đề xuất gác máy, hầu hết những người xác thực sẽ thấy một khối trống, vì vậy khối trống sẽ nhận được đa số phiếu bầu và bước vào giai đoạn cam kết. Khi cam kết một khối trống, nó sẽ không thực sự ghi một khối trống vào chuỗi khối, nhưng sẽ không ghi bất cứ thứ gì và chiều cao khối sẽ không tự động tăng lên và sẽ không thay đổi, điều này tương đương với việc không làm gì. đang chạy không tải. Sau khi vòng này kết thúc, người xác thực tiếp theo sẽ được thay thế làm người đề xuất vào đầu vòng tiếp theo, để người đề xuất hiện tại bị treo sẽ không bị kẹt trong toàn bộ mạng.
Độ phức tạp của truyền thông mạng
Độ phức tạp giao tiếp mạng của Tendermint là O(n2), bởi vì trong hai giai đoạn bỏ phiếu, mỗi nút trình xác thực cần thu thập hơn 2/3 thông báo bỏ phiếu và số lượng gói dữ liệu được gửi bởi mạng là n2, do đó, độ phức tạp đồng tâm của mạng là Ô(n2). Trong giai đoạn Đề xuất, khối mới chỉ cần được nhận bởi tất cả những người xác thực và độ phức tạp của giao tiếp mạng là O(n). Nhìn chung, đó là O(n2). Độ phức tạp của giao tiếp mạng là O(n2), và số lượng nút trong Tendermint sẽ không quá nhiều, nếu có quá nhiều, giao tiếp mạng sẽ trở thành nút cổ chai, do đó, Tendermint phù hợp cho tư nhân và liên minh Điều này cũng được chỉ định trên trang 17 của bài báo Một điểm: Tendermint là giải pháp đó, được tối ưu hóa cho tập đoàn hoặc logic liên tổ chức. Tuy nhiên, nếu nó hợp tác với cơ chế bảo vệ tốt, nó vẫn có thể được sử dụng cho chuỗi công khai. Đó là một câu chuyện khác.
giả thuyết mạng
Yêu cầu của Tendermint đối với mạng là mạng cần bán đồng bộ. Tendermint có cơ chế hết thời gian chờ trong giai đoạn Đề xuất, tuy nhiên khoảng thời gian chờ này không cố định mà nó thay đổi linh hoạt nên ở giai đoạn này, mạng bắt buộc phải bán đồng bộ. Trong giai đoạn bỏ phiếu trước và bỏ phiếu trước, không có yêu cầu nào đối với mạng, nghĩa là mạng không đồng bộ. Do đó, các yêu cầu mạng của Tendermint là bán đồng bộ.
Vì mạng không đồng bộ trong giai đoạn bỏ phiếu trước và bỏ phiếu trước, nếu hơn 2/3 số phiếu không được thu thập, tất cả các nút của trình xác nhận sẽ chờ vô thời hạn, do đó toàn bộ hệ thống sẽ bị kẹt. Tendermint đã thỏa hiệp với Liveness để đổi lấy Finality mạnh hơn.
Ví dụ: nếu nút đề xuất phát một khối mới blockX trong một vòng nhất định và nút xác thực A không nhận được khối mới đúng hạn, thì nút A sẽ tạo một khối trống trên máy cục bộ, như thể nó đã nhận được từ nút đó. người đề xuất Đã đến, gửi một tin nhắn bỏ phiếu trước không bỏ phiếu và sau đó vào vòng bỏ phiếu trước và bắt đầu hẹn giờ hết thời gian chờ, sau đó vào vòng tròn bên trong màu đỏ, A bắt đầu giám sát mạng và thu thập thông tin bỏ phiếu,
Nếu số phiếu thu được, cho dù là block trống hay blockX, không vượt quá 2/3 trong thời gian quy định, hãy đợi vô thời hạn cho đến khi tổng số phiếu vượt quá 2/3
Sau khi thu thập được hơn 2/3 tổng số phiếu bầu, nếu số lượng phiếu bầu cho khối trống vượt quá 2/3, thì đưa ra con số không bầu chọn trước để bầu cho khối trống, và vẫn ở trong vòng tròn màu đỏ ; nếu số phiếu bầu cho blockX vượt quá 2/3 3. Gửi phiếu bầu trước cho blockX và chuyển sang vòng tròn bên ngoài màu xanh lam, nếu số phiếu bầu cho khối trống và blockX không vượt quá 2/3 thì gửi phiếu bầu pre-vote nil nhắn để bỏ phiếu cho khối trống và bước vào giai đoạn pre-commit, vẫn ở trong vòng tròn màu đỏ.
Sau khi A gửi thông báo bỏ phiếu không cam kết trước, A vẫn ở trong vòng tròn bên trong màu đỏ và quy trình cam kết trước tương tự như trên. Nói chung, quy trình trong vòng tròn bên trong màu đỏ cần giả định rằng mạng là bán đồng bộ.
Cuối cùng và Liveness
Tính hữu hạn của Tendermint là tính xác định, trong khi tính hữu hạn của Bitcoin là xác suất, Tendermint có tính hữu hạn mạnh hơn Bitcoin.
Nhưng về mặt Liveness, chẳng hạn, khi mạng phân tách, về mặt lý thuyết, Tendermint có thể bị kẹt và không thể ghi giao dịch mới, trong khi Bitcoin có thể được chia thành hai nhánh, mỗi nhánh hoạt động độc lập và các giao dịch mới có thể tiếp tục.
cơ chế khóa
Trong hình trên, thực sự có một cơ chế khóa hoàn toàn, cơ chế này không được hiển thị trong hình. Ví dụ: có bốn nút trình xác thực, A, B, C, D, trong một vòng R nhất định,
Trong giai đoạn đề xuất, nút đề xuất phát một khối mới blockX
A đã không nhận được khối mới trong khoảng thời gian chờ, phát phiếu bầu trước bằng 0 ra bên ngoài, B, C và D đều nhận được và phát phiếu bầu trước cho blockX
Bây giờ bốn nút đã bước vào giai đoạn tiền cam kết, A nằm trong vòng tròn bên trong màu đỏ, B, C, D nằm trong vòng tròn màu xanh bên ngoài
Giả sử rằng A có mạng kém và không nhận được hơn 2/3 phiếu bầu cho blockX trong thời gian quy định, nó chỉ có thể gửi thông báo bầu chọn không cam kết trước để bỏ phiếu cho một khối trống
D đã nhận được tin nhắn bỏ phiếu trước của B và C, cộng với tin nhắn của anh ấy, nó đã vượt quá 2/3, vì vậy D đã cam kết blockX trong chuỗi khối cục bộ
Đã xảy ra sự cố với mạng của B và C và D không thể nhận được thông báo xác nhận trước. Điều này là do B và C chỉ có thể thấy 2 phiếu bầu cho khối X và 1 phiếu bầu cho một khối trống, ít hơn 2/3 nên B và C C chỉ được commit block trống, chiều cao không đổi, vào vòng R+1, A chỉ được xem 2 vote cho blockX và 1 vote cho block trống, chỉ được commit block trống , chiều cao không đổi , vào vòng R+1
Trong vòng R+1, do một người đề xuất tình yêu mới đã đề xuất một khối mới, khối Y, A, B và C có thể đạt được sự đồng thuận và gửi khối Y, do đó, ở cùng một độ cao, có hai khối khối X và khối Y, dẫn đến một nhánh rẽ .
Tendermint đã thêm một cơ chế khóa, cụ thể là ở bước 7, ngay cả khi người đề xuất tạo một khối mới thì khối Y, A, B và C chỉ có thể bị khóa trên các khối trước khi cam kết của họ ở bước 6, tức là A đang ở trong bước 6 Nếu bạn vote cho block trống ở bước 1, bạn chỉ có thể tiếp tục vote cho block trống ở vòng R+1, và B vote cho blockX ở bước 6, thì ở vòng mới, bạn mãi mãi chỉ có thể vote cho blockX , và C tương tự. Theo cách này, trong vòng R+1, sẽ có 1 phiếu bầu cho khối trống và 2 phiếu bầu cho khốiX, và cuối cùng đạt được sự đồng thuận về khốiX, A, B và C đều sẽ cam kết khốiX, điều này phù hợp với D , và không có xung đột.
Tendermint so với pBFT
Tendermint và pBFT trông rất giống nhau, ví dụ:
Tất cả đều thuộc thuật toán loại BFT, chịu tối đa không quá 1/3 số node độc hại
Tất cả đều là đệ trình qua ba giai đoạn. Ba giai đoạn đề xuất->pre-vote->pre-commit của Tendermint tương ứng với ba giai đoạn của pBFT, chuẩn bị trước, chuẩn bị và cam kết.
Khi tất cả đã hết thời gian, hãy thay thế người đề xuất/chính
Không đủ Tendermint có hai điểm đơn giản hóa so với pBFT.
Tendermint không có giai đoạn View Change của pBFT, Tendermint khéo léo kết hợp tình trạng timeout với tình trạng bình thường thành một thể thống nhất, đều ở 3 giai đoạn đề xuất->pre-vote->pre-commit, và chỉ có block mới được tạo khi hết thời gian chờ, là một khối trống đặc biệt. Việc chuyển đổi người đề xuất được kích hoạt bằng cách gửi một khối cam kết trống, trong khi pBFT có quy trình thay đổi chế độ xem riêng để kích hoạt vòng quay chính.
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.
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. Bởi vì pBFT được đề xuất vào năm 1999, nên không có thứ gọi là chuỗi khối vào thời điểm đó (blockchain chỉ có sau khi Bitcoin xuất hiện vào năm 2009), vì vậy 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:
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 đầy đủ 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, điểm kiểm tra được giới thiệu.khái niệm, có rất nhiều bước rườm rà trong việc quản lý dữ liệu một mình.
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.
Cách chọn trình xác thực
Thứ nhất, trong khối genesis, một tập hợp các nút trình xác thực có thể được đặt tĩnh Thứ hai, khi chuỗi bắt đầu, một thông báo Trình xác thực có thể được gửi để cập nhật danh sách trình xác thực. Xem Cập nhật Trình xác thực
Trong tài liệu không nói nhiều về nơi này, và nó có vẻ tương đối nguyên thủy, không có thuật toán lấy mẫu ngẫu nhiên tương tự như xổ số mật mã của Algorand. Nhưng nơi này sẽ có thể mở rộng bất cứ lúc nào.
Cách thay đổi Proposer lần lượt
Sau khi một nhóm các nút trình xác thực được chọn, tất cả các nút trình xác thực trong toàn bộ mạng sẽ lưu một bản sao, chẳng hạn như trong một mảng hình tròn.
Nói chung, một khối chỉ có thể được tạo trong một vòng trong hầu hết các trường hợp, khi mạng không tốt, có thể mất nhiều vòng để tạo một khối. Trong mọi trường hợp, mỗi vòng sẽ có một trình xác thực mới làm người đề xuất và quy tắc xoay vòng đơn giản là tăng theo thứ tự. Trong vòng đầu tiên, trình xác thực thứ 0 trong mảng sẽ được chọn làm người đề xuất và trong vòng thứ hai, trình xác thực đầu tiên sẽ được chọn, v.v. , sau khi đến trình xác thực cuối cùng, trình xác nhận này được đặt lại về 0, lặp lại vô tận.
Sau đó, bắt đầu thuật toán đồng thuận. Trong vòng thứ 0, trình xác thực có vị trí là 0 được chọn làm nút đề xuất. Trong vòng đầu tiên, trình xác thực có vị trí là 1 được chọn. Trong vòng thứ hai, trình xác thực có vị trí là 2 được chọn được chọn làm người đề xuất.Sau khi đến người cuối cùng, nó được đặt lại thành 0. Vòng lặp vô hạn.
Chiến lược quay vòng này có thể bỏ qua nút đề xuất đã hết thời gian một cách hiệu quả. Nếu một nút đề xuất bị treo hoặc mạng kém, hầu hết các nút không thể nhận khối mới đúng hạn, do đó, sau khi hết thời gian, mỗi nút xác minh sẽ xây dựng một khối trống cục bộ và phát thông báo bỏ phiếu ra ngoài, sau hai vòng trước-Sau hai vòng biểu quyết, bỏ phiếu và cam kết trước, cuối cùng cam kết một khối trống, tương đương với việc không làm gì, với cùng chiều cao và bắt đầu một vòng mới. Vì mỗi vòng mới bắt đầu, nó sẽ được thay thế bởi người đề xuất tiếp theo theo thứ tự, do đó, nút người đề xuất được đề xuất bị treo sẽ bị bỏ qua một cách tự nhiên và thuật toán có thể tự động tiếp tục.
Chiến lược quay vòng quá đơn giản và kẻ xấu rất dễ dự đoán ai sẽ là người xác thực tiếp theo, vì vậy chúng có thể lên kế hoạch trước và khởi động các cuộc tấn công DDoS hoặc các cuộc tấn công khác vào trình xác thực. Chúng ta nên làm gì? Giải pháp của Tendermint là đặt tất cả các nút trình xác thực phía sau Nút Sentry mà không để lộ địa chỉ IP ra thế giới bên ngoài.
tiếp tục TODO
Người giới thiệu
Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
Tendermint: Consensus without mining
