Giải thích khung Shoal: Thả đáng kể độ trễ của Bullshark trên Aptos

Aptos Labs gần đây đã giải quyết hai vấn đề then chốt 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ời gian thực xác định. Tổng thể, trong trường hợp không có lỗi, độ trễ của Bullshark đã được cải thiện 40%, trong trường hợp có lỗi đã cải thiện 80%.

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

Công nghệ này 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ự. Khi sử dụng Bullshark để khởi tạo, tương đương với một nhóm "cá mập" đang tham gia một cuộc tiếp sức.

Bối cảnh và động lực

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

Gần đây, sự đột phá xuất phát từ việc nhận ra rằng sự truyền dữ liệu là nút thắt 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 biệt việc truyền dữ liệu với logic đồng thuận cốt lõi, đề xuất kiến trúc mà tất cả các xác thực viên đồng thời truyền dữ liệu, còn 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 thông lượng đạt 160.000 TPS.

Aptos đã giới thiệu Quorum Store, tức là việc triển khai Narwhal, tách biệt việc truyền dữ liệu và đồng thuận, nhằm mở rộng giao thức đồng thuận Jolteon hiện tại. Jolteon kết hợp con đường nhanh tuyến tính của Tendermint và thay đổi tầm nhìn theo phong cách PBFT, có thể Thả độ trễ của Hotstuff xuống 33%. Tuy nhiên, giao thức đồng thuận dựa trên lãnh đạo không thể tận dụng đầy đủ tiềm năng thông lượng của Narwhal.

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

Khung Shoal nhằm mục đích giảm đáng kể Trễ của Bullshark.

Bối cảnh DAG-BFT

Trong Narwhal DAG, mỗi đỉnh đều liên kết với một vòng. Để vào vòng thứ r, các xác thực viên phải trước tiên thu được n-f đỉnh của vòng thứ r-1. Mỗi xác thực viên có thể phát sóng một đỉnh trong 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 bất đồng bộ của mạng, các xác thực viên khác nhau có thể quan sát các góc nhìn địa phương khác nhau của DAG tại bất kỳ thời điểm nào.

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

Tổng tự 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 thực trong DAG-Rider, Tusk và Bullshark giải thích cấu trúc DAG như một giao thức đồng thuận, trong đó các đỉnh đại diện cho đề xuất và các cạnh đại diện cho phiếu bầu.

Tất cả các giao thức đồng thuận dựa trên Narwhal đều có cấu trúc sau:

1. Điểm neo đã đặt: sau mỗi vài vòng sẽ có một lãnh đạo được xác định trước, đỉnh của nó được gọi là điểm neo.

2. Điểm neo sắp xếp: Các nhà xác thực độc lập nhưng xác định các điểm neo nào sẽ được sắp xếp, bỏ qua các điểm neo nào.

3. Sắp xếp lịch sử nguyên nhân: Các xác thực viên lần lượt xử lý danh sách điểm neo có thứ tự, sắp xếp các đỉnh không có thứ tự trước đó trong lịch sử nguyên nhân của mỗi điểm neo.

Chìa khóa của sự an toàn là đảm bảo rằng trong bước (2), danh sách các điểm neo có thứ tự được tạo ra bởi tất cả các nút xác thực trung thực chia sẻ cùng một tiền tố. Shoal quan sát thấy: 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ù một số phiên bản đồng bộ của Bullshark có độ trễ tốt hơn so với phiên bản không đồng bộ, nhưng vẫn còn xa mới đạt được tối ưu.

Chủ yếu có hai vấn đề:

1. Thời gian trễ khối trung bình: Trong các trường hợp phổ biến, đỉnh lẻ cần ba vòng, đỉnh chẵn không phải là đỉnh neo cần bốn vòng để sắp xếp.

2. Tình huống lỗi trễ: Nếu một nhà lãnh đạo trong vòng nào đó không thể phát sóng điểm neo kịp thời, dẫn đến việc điểm neo không thể sắp xếp và bị bỏ qua, các đỉnh chưa được sắp xếp trong vài vòng trước phải chờ đợi điểm neo tiếp theo được sắp xếp. Điều này làm giảm đáng kể hiệu suất của mạng sao chép địa lý.

Khung Shoal

Shoal thông qua dây chuyền nâng cao Bullshark( hoặc bất kỳ giao thức BFT nào dựa trên Narwhal), cho phép mỗi vòng có một điểm neo, 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 phí trong DAG, thiên về việc chọn lãnh đạo nhanh.

Thách thức

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

1. Trước đây, việc thử nghiệm dây chuyền sản xuất đã cố gắng sửa đổi logic cốt lõi của Bullshark, nhưng điều này về cơ bản 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, chính thức hóa trong Carousel, chọn lựa người lãnh đạo tương lai một cách linh hoạt dựa trên hiệu suất trong quá khứ của các xác thực viên (Điểm neo trong Bullshark ). Mặc dù sự khác biệt về danh tính lãnh đạo không vi phạm tính an toàn, nhưng có thể dẫn đến thứ tự hoàn toàn khác nhau trong Bullshark.

Những thách thức này dẫn đến việc các triển khai Bullshark hiện tại trong môi trường sản xuất không hỗ trợ những tính năng này.

Giao thức

Shoal dựa vào khả năng thực hiện tính toán cục bộ trên DAG, để lưu trữ và giải thích lại thông tin của các vòng trước. Dựa trên sự đồng thuận của tất cả các xác thực về cái nhìn của điểm neo đầu tiên có thứ tự, Shoal kết hợp theo thứ tự nhiều phiên bản Bullshark để thực hiện xử lý theo luồng, khiến cho:

1. Điểm neo có thứ tự đầu tiên là điểm chuyển đổi của phiên bản.
2. Lịch sử nguyên nhân của điểm neo được sử dụng để tính toán danh tiếng của người lãnh đạo

Dòng chảy

V ánh xạ các vòng đến người lãnh đạo. Shoal lần lượt chạy các instance Bullshark, mỗi instance có điểm neo được xác định trước bởi ánh xạ F. Mỗi instance sắp xếp một điểm neo, kích hoạt chuyển sang instance tiếp theo.

Shoal ban đầu khởi động Bullshark phiên bản đầu tiên trong vòng đầu tiên của DAG, hoạt động để xác định điểm neo có thứ tự đầu tiên ( giả định trong vòng r ). Tất cả các xác nhận viên đồng ý với điểm neo này, do đó có thể đồng ý một cách xác định để giải thích lại DAG bắt đầu từ vòng r+1. Shoal khởi động phiên bản Bullshark mới trong vòng r+1.

Trong điều kiện lý tưởng, điều này cho phép Shoal sắp xếp một điểm neo trong mỗi vòng. Điểm neo của vòng đầu tiên được sắp xếp bởi phiên bản đầu tiên, sau đó Shoal bắt đầu phiên bản mới trong vòng thứ hai, sắp xếp điểm neo của vòng đó, và cứ tiếp tục như vậy.

Danh tiếng lãnh đạo

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

Mỗi khi điểm số được cập nhật, xác định lại một cách chắc chắn ánh xạ định trước F từ vòng chơi đến người lãnh đạo, thiên về người lãnh đạo có điểm cao. Để các xác thực đạt được sự đồng thuận trên ánh xạ mới, họ cần đạt được sự đồ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à uy tín lãnh đạo tự nhiên kết hợp với nhau, vì cả hai đều sử dụng cùng một công nghệ cốt lõi: 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.

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

Xóa bỏ trễ

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 đoạn xác định dựa trên lãnh đạo. Tuy nhiên, độ 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, tăng độ phức tạp trong việc gỡ lỗi, và yêu cầu nhiều kỹ thuật quan sát hơn.

Thời gian chờ cũng tăng đáng kể trễ, vì việc cấu hình thời gian chờ thích hợp rất quan trọng, thường cần điều chỉnh động, 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ễ thời gian cho nhà lãnh đạo gặp sự cố. Do đó, việc thiết lập thời gian chờ không thể quá bảo thủ, nhưng nếu quá ngắn, giao thức có thể bỏ qua nhà lãnh đạo tốt.

Thật không may, các giao thức dựa trên người lãnh đạo ( như Hotstuff và Jolteon ) về cơ bản cần có thời gian chờ, để đảm bảo rằng giao thức có thể tiến triển mỗi khi người lãnh đạo gặp sự cố. Không có thời gian chờ, ngay cả những người lãnh đạo gặp sự cố cũng có thể ngừng giao thức mãi mãi. Do không thể phân biệt giữa người lãnh đạo gặp sự cố và người lãnh đạo chậm trong thời gian bất đồng bộ, thời gian chờ có thể dẫn đến việc các nút xác thực luân phiên tất cả các người lãnh đạo mà không có hoạt động đồng thuận.

Trong Bullshark, thời gian chờ được sử dụng cho việc xây dựng DAG, để đảm bảo rằng trong suốt quá trình đồng bộ, các nhà lãnh đạo trung thực đủ nhanh để thêm các điểm neo vào DAG để sắp xếp.

Shoal quan sát thấy rằng cấu trúc DAG cung cấp một "chiếc đồng hồ" ước lượng tốc độ mạng. Trong trường hợp không có sự tạm dừng, miễn là n-f người xác thực trung thực tiếp tục thêm đỉnh vào DAG, vòng sẽ tiếp tục tiến lên. Mặc dù Bullshark có thể không sắp xếp ( theo tốc độ mạng do vấn đề lãnh đạo ), nhưng DAG vẫn phát triển với tốc độ mạng, mặc dù một số lãnh đạo gặp vấn đề hoặc mạng không đồng bộ. Cuối cùng, khi các lãnh đạo không bị lỗi phát sóng các điểm neo đủ nhanh, toàn bộ lịch sử nguyên nhân của các điểm neo sẽ được sắp xếp.

Trong Shoal, việc tránh thời gian chờ lâu có liên quan chặt chẽ đến danh tiếng của người lãnh đạo. Việc chờ đợi các lãnh đạo chậm chạp sẽ làm tăng Trễ, cơ chế danh tiếng của lãnh đạo loại trừ các xác thực viên chậm chạp khỏi việc được chọn làm lãnh đạo. Bằng cách này, hệ thống sử dụng các nút xác thực nhanh để hoạt động với tốc độ mạng trong tất cả các tình huống thực tế.

Cần lưu ý, kết quả không thể của FLP cho thấy không có giao thức đồng thuận xác định nào có thể tránh được thời gian trễ. Shoal không thể tránh khỏi kết quả này, vì có lịch trình sự kiện đối kháng lý thuyết có thể ngăn cản tất cả các neo được sắp xếp. Ngược lại, sau một số lượng neo liên tục có thể cấu hình được bỏ qua, Shoal sẽ quay lại trạng thái quá thời gian. Trên thực tế, tình huống này rất khó xảy ra.

Phản hồi tổng quát

Bài báo Hotstuff đã phổ biến khái niệm phản hồi lạc quan, mặc dù chưa được định nghĩa chính thức, nhưng trực quan có nghĩa là giao thức có thể hoạt động với tốc độ mạng dưới điều kiện tốt với các nhà lãnh đạo nhanh chóng và mạng đồng bộ (.

Shoal cung cấp các thuộc tính tốt hơn, được gọi là khả năng phản hồi tổng quát. Cụ thể, so với Hotstuff, ngay cả khi người lãnh đạo thất bại trong một số vòng liên tục có thể cấu hình hoặc mạng trải qua các chu kỳ bất đồng bộ, Shoal vẫn sẽ tiếp tục hoạt động với tốc độ của mạng.

Tính phản hồi chung cung cấp đảm bảo tiến độ nghiêm ngặt hơn trong thời gian bất đồng bộ và khi nhà lãnh đạo gặp sự cố. Trong thời gian đồng bộ với nhà lãnh đạo chậm, những thuộc tính này không thể so sánh được, vì nó phụ thuộc vào tốc độ của nhà lãnh đạo. Tuy nhiên, với sự xem xét đến danh tiếng của nhà lãnh đạo, nhà lãnh đạo chậm trong Shoal nên hiếm khi xuất hiện.

Đánh giá

Aptos đã triển khai Bullshark và Shoal trên Quorum Store được thực hiện bởi Narwhal. Dưới đây là một số điểm nổi bật trong đánh giá:

Đầu tiên, để diễn