Khung Shoal: Thả đáng kể độ trễ Bullshark trên Aptos

Aptos Labs gần đây đã giải quyết hai vấn đề mở quan trọng trong DAG BFT, Thả đáng kể độ trễ, và lần đầu tiên loại bỏ nhu cầu về thời gian chờ trong giao thức thực sự xác định. Tổng thể, trong trường hợp không có sự cố, độ trễ của Bullshark đã cải thiện 40%, trong trường hợp có sự cố đã cải thiện 80%.

Shoal là một khung, thông qua quy trình và uy tín của người lãnh đạo để tăng cường bất kỳ giao thức đồng thuận nào dựa trên Narwhal ( như DAG-Rider, Tusk, Bullshark ). Quy trình giảm thiểu độ trễ sắp xếp DAG bằng cách đưa vào một điểm neo mỗi vòng, uy tín của người lãnh đạo cải thiện thêm độ trễ bằng cách đảm bảo rằng các điểm neo liên kết với các nút xác thực nhanh nhất. Hơn nữa, uy tín của người lãnh đạo cho phép Shoal tận dụng cấu trúc DAG bất đồng bộ để loại bỏ mọi trường hợp thời gian chờ. Điều này cho phép Shoal cung cấp thuộc tính mà chúng tôi gọi là phản hồi phổ quát, nó chứa đựng phản hồi lạc quan thường cần thiết.

Công nghệ của chúng tôi rất đơn giản, liên quan đến việc chạy nhiều phiên bản của giao thức cơ sở theo thứ tự một cách tuần tự. Do đó, khi sử dụng Bullshark để khởi tạo, chúng tôi có một nhóm "cá mập" đang tham gia vào một cuộc đua tiếp sức.

Động cơ

Trong việc theo đuổi hiệu suất cao của mạng blockchain, mọi người luôn chú ý đến việc thả độ phức tạp trong giao tiếp. Tuy nhiên, phương pháp này không dẫn đến việc tăng thông lượng một cách đáng kể. Ví dụ, Hotstuff được triển khai trong các phiên bản đầu tiên của Diem chỉ đạt 3500 TPS, thấp hơn nhiều so với mục tiêu 100k+ TPS mà chúng tôi đạt được.

Tuy nhiên, đột phá gần đây xuất phát từ việc nhận ra rằng việc truyền dữ liệu là điểm nghẽn chính dựa trên giao thức lãnh đạo và có thể hưởng lợi từ việc song song hóa. Hệ thống Narwhal tách rời việc truyền dữ liệu khỏi logic đồng thuận cốt lõi và đề xuất một kiến trúc trong đó tất cả các xác thực viên đồng thời truyền dữ liệu, trong khi thành phần đồng thuận chỉ sắp xếp một lượng nhỏ siêu dữ liệu. Bài báo Narwhal báo cáo khả năng thông lượng 160,000 TPS.

Trong bài viết trước, chúng tôi đã giới thiệu về Quorum Store. Triển khai Narwhal của chúng tôi tách biệt việc phát tán dữ liệu và đồng thuận, cũng như cách chúng tôi sử dụng nó để mở rộng giao thức đồng thuận hiện tại Jolteon. Jolteon là một giao thức dựa trên người lãnh đạo, kết hợp đường dẫn nhanh tuyến tính của Tendermint và thay đổi chế độ xem theo phong cách PBFT, có thể giảm thiểu độ trễ của Hotstuff xuống 33%. Tuy nhiên, rõ ràng là các giao thức đồng thuận dựa trên người lãnh đạo không thể tận dụng đầy đủ tiềm năng thông lượng của Narwhal. Mặc dù việc phát tán dữ liệu và đồng thuận đã được tách biệt, nhưng khi thông lượng tăng lên, người lãnh đạo của Hotstuff/Jolteon vẫn bị hạn chế.

Do đó, chúng tôi quyết định triển khai Bullshark, một giao thức đồng thuận không tốn chi phí truyền thông, trên Narwhal DAG. Thật không may, so với Jolteon, cấu trúc DAG hỗ trợ Bullshark có khả năng thông lượng cao đã mang lại chi phí trễ 50%.

Trong bài viết này, chúng tôi giới thiệu cách Shoal thực hiện việc Thả đáng kể Bullshark.

Bối cảnh DAG-BFT

Hãy bắt đầu từ việc hiểu bối cảnh liên quan của bài viết này.

Mỗi đỉnh trong Narwhal DAG đều liên quan đến một vòng. Để vào vòng thứ r, người xác thực phải trước tiên có được n-f đỉnh thuộc vòng thứ r-1. Mỗi người xác thực có thể phát sóng một đỉnh mỗi vòng, và mỗi đỉnh ít nhất phải tham chiếu đến n-f đỉnh của vòng trước. Do tính không đồng bộ của mạng, các người xác thực khác nhau có thể quan sát các cái nhìn cục bộ khác nhau của DAG tại bất kỳ thời điểm nào.

Một thuộc tính then chốt của DAG không phải là mơ hồ: nếu hai nút xác thực có cùng đỉnh v trong cái nhìn địa phương DAG của chúng, thì chúng có lịch sử nguyên nhân v hoàn toàn giống nhau.

Tổng sắp xếp

Có thể đạt được sự đồng thuận về thứ tự tổng thể của tất cả các đỉnh trong DAG mà không cần chi phí giao tiếp bổ sung. Để làm điều này, các xác nhận viên trong DAG-Rider, Tusk và Bullshark sẽ giải thích cấu trúc của DAG như một giao thức đồng thuận, trong đó các đỉnh đại diện cho các đề xuất và các cạnh đại diện cho các phiếu bầu.

Mặc dù logic giao thoa nhóm trên cấu trúc DAG khác nhau, nhưng tất cả các giao thức đồng thuận dựa trên Narwhal hiện có đều có cấu trúc sau:

1. Điểm neo đã được đặt trước: Mỗi vài vòng ( ví dụ, trong Bullshark, sẽ có một nhà lãnh đạo đã được xác định trước sau mỗi hai vòng ), đỉnh của nhà lãnh đạo được gọi là điểm neo;

2. Điểm neo sắp xếp: người xác thực độc lập nhưng quyết định một cách chắc chắn điểm neo nào được đặt hàng và điểm neo nào sẽ bị bỏ qua;

3. Sắp xếp lịch sử nguyên nhân: Các xác thực viên xử lý một cách tuần tự danh sách các điểm neo của họ, và đối với mỗi điểm neo, sắp xếp tất cả các đỉnh chưa có thứ tự trước đó trong lịch sử nguyên nhân của nó thông qua một số quy tắc xác định.

Điều quan trọng để đảm bảo tính an toàn là đảm bảo rằng trong các bước trên (2), tất cả các nút xác thực trung thực tạo ra một danh sách điểm neo có thứ tự, để tất cả các danh sách chia sẻ cùng một tiền tố. Tại Shoal, chúng tôi có những quan sát sau về tất cả các giao thức trên:

Tất cả các xác thực viên đều đồng ý với điểm neo có thứ tự đầu tiên.

Bullshark Trễ

Độ trễ của Bullshark phụ thuộc vào số vòng giữa các điểm neo có thứ tự trong DAG. Mặc dù phiên bản đồng bộ phần Bullshark hữu dụng hơn phiên bản không đồng bộ về độ trễ, nhưng nó vẫn chưa phải là tốt nhất.

Vấn đề 1: Độ trễ khối trung bình. Trong Bullshark, mỗi vòng chẵn đều có một điểm neo, trong khi đỉnh của mỗi vòng lẻ được hiểu là một phiếu bầu. Trong trường hợp thông thường, cần hai vòng DAG để sắp xếp các điểm neo, tuy nhiên, các đỉnh trong lịch sử nguyên nhân của điểm neo cần nhiều vòng hơn để chờ điểm neo được sắp xếp. Trong trường hợp thông thường, các đỉnh trong vòng lẻ cần ba vòng, trong khi các đỉnh không phải điểm neo trong vòng chẵn cần bốn vòng.

Câu hỏi 2: Trễ trong trường hợp lỗi, phân tích trễ ở trên áp dụng cho trường hợp không có lỗi, mặt khác, nếu nhà lãnh đạo của một vòng không truyền phát điểm neo đủ nhanh, thì không thể sắp xếp các điểm neo ( do đó bị bỏ qua ), vì vậy tất cả các đỉnh chưa được sắp xếp trong các vòng trước phải chờ điểm neo tiếp theo được sắp xếp. Điều này sẽ làm giảm đáng kể hiệu suất của mạng sao chép địa lý, đặc biệt là vì thời gian chờ Bullshark được sử dụng để chờ nhà lãnh đạo.

Khung Shoal

Shoal đã giải quyết được hai vấn đề trễ này, nó đã tăng cường Bullshark( hoặc bất kỳ giao thức BFT nào dựa trên Narwhal) thông qua pipeline, cho phép có một điểm neo trong mỗi vòng và giảm độ trễ của tất cả các đỉnh không phải điểm neo trong DAG xuống còn ba vòng. Shoal cũng đã giới thiệu cơ chế danh tiếng lãnh đạo không tốn kém trong DAG, điều này khiến việc lựa chọn nghiêng về các lãnh đạo nhanh.

Thách thức

Trong bối cảnh giao thức DAG, độ trễ và danh tiếng của người lãnh đạo được coi là những vấn đề khó khăn, lý do như sau:

1. Dòng chảy trước đây đã cố gắng sửa đổi logic Bullshark cốt lõi, nhưng về bản chất điều này dường như là không thể.

2. Danh tiếng của người lãnh đạo được giới thiệu trong DiemBFT và chính thức hóa trong Carousel, là việc lựa chọn động các lãnh đạo tương lai dựa trên hiệu suất trong quá khứ của các xác nhận viên trong (Bullshark, ý tưởng của việc chọn neo trong ). Mặc dù có sự khác biệt về danh tính lãnh đạo không vi phạm tính bảo mật trong các giao thức này, nhưng trong Bullshark, nó có thể dẫn đến thứ tự hoàn toàn khác, điều này dẫn đến cốt lõi của vấn đề, tức là việc chọn neo vòng một cách động và xác định là cần thiết để giải quyết sự đồng thuận, trong khi các xác nhận viên cần đạt được sự đồng thuận về lịch sử có thứ tự để chọn neo tương lai.

Với bằng chứng về độ khó của vấn đề, chúng tôi nhận thấy rằng việc triển khai Bullshark, bao gồm cả việc triển khai hiện tại trong môi trường sản xuất, đều không hỗ trợ những tính năng này.

Thỏa thuận

Mặc dù có những thách thức nêu trên, nhưng như người ta thường nói, sự thật là giải pháp ẩn chứa đằng sau những điều đơn giản.

Trong Shoal, chúng tôi dựa vào khả năng thực hiện tính toán cục bộ trên DAG và đạt được khả năng lưu trữ và giải thích lại thông tin của các vòng trước. Với tất cả các xác thực viên đều đồng ý về cái nhìn cốt lõi của điểm neo có thứ tự đầu tiên, Shoal kết hợp tuần tự nhiều phiên bản Bullshark để xử lý chúng theo dạng ống, khiến cho ( điểm neo có thứ tự đầu tiên là điểm chuyển đổi của các phiên bản, cũng như ) lịch sử nguyên nhân của điểm neo được sử dụng để tính toán uy tín của những người lãnh đạo.

Dòng chảy

V ánh xạ vòng đến người lãnh đạo. Shoal chạy lần lượt các phiên bản của Bullshark, như vậy đối với mỗi phiên bản, điểm neo được xác định trước bởi ánh xạ F. Mỗi phiên bản đều đặt hàng một điểm neo, điều này sẽ kích hoạt chuyển đổi sang phiên bản tiếp theo.

Ban đầu, Shoal đã khởi động phiên bản đầu tiên của Bullshark trong vòng đầu tiên của DAG và chạy nó cho đến khi xác định được điểm neo có thứ tự đầu tiên, chẳng hạn như trong vòng r. Tất cả các trình xác thực đều đồng ý với điểm neo này. Do đó, tất cả các trình xác thực có thể chắc chắn đồng ý rằng bắt đầu từ vòng r+1, sẽ giải thích lại DAG. Shoal chỉ khởi động một phiên bản Bullshark mới trong vòng r+1.

Trong trường hợp tốt nhất, điều này cho phép Shoal đặt một mỏ neo trong mỗi vòng. Điểm neo trong vòng đầu tiên được sắp xếp theo thể thức của thể hiện đầu tiên. Sau đó, Shoal bắt đầu một thể hiện mới ở vòng thứ hai, nó có một điểm neo, điểm neo đó được sắp xếp bởi thể hiện đó, rồi một thể hiện mới khác đặt điểm neo trong vòng thứ ba, và quá trình này tiếp tục.

Danh tiếng của nhà lãnh đạo

Khi bỏ qua điểm neo trong quá trình sắp xếp Bullshark, độ trễ sẽ tăng lên. Trong trường hợp này, công nghệ pipeline sẽ không có tác dụng, vì không thể khởi động phiên bản mới trước khi đặt hàng điểm neo của phiên bản trước đó. Shoal đảm bảo rằng các nhà lãnh đạo tương ứng sẽ ít khả năng được chọn trong tương lai để xử lý các điểm neo bị mất bằng cách sử dụng cơ chế tín nhiệm để phân bổ một điểm số cho mỗi nút xác thực dựa trên lịch sử hoạt động gần đây của họ. Các nhà xác thực phản hồi và tham gia vào giao thức sẽ nhận được điểm số cao, nếu không, các nút xác thực sẽ được phân bổ điểm số thấp, vì chúng có thể bị sập, chậm hoặc ác ý.

Ý tưởng của nó là khi điểm số được cập nhật, tính toán lại một cách xác định ánh xạ F đã được định nghĩa từ vòng đến người dẫn đầu, thiên về những người dẫn đầu có điểm số cao hơn. Để các xác thực đạt được sự đồng thuận trên ánh xạ mới, họ nên đồng thuận về điểm số, từ đó đạt được sự đồng thuận trong lịch sử được sử dụng để suy diễn điểm số.

Trong Shoal, quy trình và danh tiếng lãnh đạo có thể kết hợp một cách tự nhiên, vì chúng đều sử dụng cùng một công nghệ cốt lõi, đó là giải thích lại DAG sau khi đạt được sự đồng thuận về điểm neo có thứ tự đầu tiên.

Thật ra, sự khác biệt duy nhất là, sau khi sắp xếp các điểm neo trong vòng thứ r, các xác thực chỉ cần tính toán ánh xạ mới F' từ vòng thứ r+1 dựa trên lịch sử nguyên nhân của các điểm neo đã sắp xếp trong vòng thứ r. Sau đó, các nút xác thực sẽ bắt đầu từ vòng thứ r+1 sử dụng hàm lựa chọn điểm neo được cập nhật F' để thực hiện một实例 mới của Bullshark.

Không còn quá thời gian nữa

Thời gian vượt quá đóng vai trò quan trọng trong tất cả các triển khai BFT đồng bộ phần dựa trên người lãnh đạo. Tuy nhiên, sự phức tạp mà chúng mang lại làm tăng số lượng trạng thái nội bộ cần quản lý và quan sát, điều này làm tăng độ phức tạp của quá trình gỡ lỗi và cần nhiều kỹ thuật quan sát hơn.

Thời gian chờ cũng sẽ làm tăng đáng kể Trễ, vì việc cấu hình chúng một cách thích hợp là rất quan trọng và thường cần điều chỉnh động, vì nó phụ thuộc nhiều vào môi trường ( mạng ). Trước khi chuyển sang nhà lãnh đạo tiếp theo, giao thức sẽ trả toàn bộ hình phạt trễ cho nhà lãnh đạo gặp sự cố. Do đó, cài đặt thời gian chờ không thể quá bảo thủ, nhưng nếu thời gian chờ quá ngắn, giao thức có thể bỏ qua những nhà lãnh đạo tốt. Ví dụ, chúng tôi quan