Khung Shoal: Làm thế nào để giảm độ trễ Bullshark trên Aptos?

Tổng quan

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

Shoal là một khung, thông qua đường ống và uy tín của người dẫn đầu để tăng cường giao thức đồng thuận dựa trên Narwhal ( như DAG-Rider, Tusk, Bullshark ). Đường ống 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, trong khi uy tín của người dẫn đầu cải thiện thêm vấn đề độ trễ bằng cách đảm bảo các điểm neo được liên kết với các nút xác minh nhanh nhất. Hơn nữa, uy tín của người dẫn đầu cho phép Shoal tận dụng cấu trúc DAG bất đồng bộ để loại bỏ tất cả các tình huống quá thời gian. Điều này cho phép Shoal cung cấp thuộc tính phản hồi phổ quát, bao gồm cả 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ự. Do đó, khi được khởi tạo bằng Bullshark, ta nhận được một nhóm "cá mập" đang tham gia một cuộc 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 giảm độ phức tạp của giao tiếp. Tuy nhiên, phương pháp này không dẫn đến việc tăng đáng kể thông lượng. Ví dụ, Hotstuff được triển khai trong 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.

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

Quorum Store đã được giới thiệu trước đó, 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 hiện tại là Jolteon. Jolteon là một giao thức dựa trên lãnh đạo, kết hợp con đường nhanh tuyến tính của Tendermint và thay đổi chế độ nhìn theo phong cách PBFT, giảm độ 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. Mặc dù đã tách biệt việc truyền dữ liệu và đồng thuận, nhưng với sự gia tăng thông lượng, lãnh đạo của Hotstuff/Jolteon vẫn bị hạn chế.

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

Bài viết này giới thiệu cách Shoal giảm đáng kể độ trễ của Bullshark.

Bối cảnh DAG-BFT

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

Một thuộc tính chính 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 cục bộ của DAG, thì chúng có cùng một lịch sử nguyên nhân v.

Tổng thứ tự

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í truyền thông bổ sung. Để làm điều này, các xác thực trong DAG-Rider, Tusk và Bullshark sẽ hiểu cấu trúc 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 của nhóm trên cấu trúc DAG là khác nhau, nhưng tất cả các giao thức đồng thuận hiện có dựa trên Narwhal đều có cấu trúc sau:

1. Điểm neo đã được định trước: cứ sau 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 xác thực quyết định một cách độc lập nhưng có tính xác định về việc đặt hàng hoặc bỏ qua những điểm neo nào.

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

Chìa khóa để đảm bảo 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ố. Trong Shoal, chúng tôi có những quan sát sau đối với tất cả các giao thức này:

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

Bullshark chậm 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ộ của Bullshark có độ trễ tốt hơn phiên bản không đồng bộ, nhưng vẫn chưa phải là tốt nhất.

Câu hỏi 1: Độ trễ khối trung bình. Trong Bullshark, mỗi vòng chẵn đều có điểm neo, đỉnh của vòng lẻ được hiểu là bỏ phiếu. Trong trường hợp thông thường, cần hai vòng DAG để đặt hàng 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 phải chờ thêm nhiều vòng để được sắp xế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ường hợp lỗi bị trễ. Phân tích độ trễ nêu trên áp dụng cho các tình huống không có lỗi, ngược lại, nếu một vòng lãnh đạo không thể phát sóng điểm neo đủ nhanh, thì không thể sắp xếp điểm neo ( do đó bị bỏ qua ), tất cả các đỉnh chưa 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ẽ giảm đáng kể hiệu suất của mạng sao chép địa lý, đặc biệt vì Bullshark sử dụng thời gian chờ cho lãnh đạo.

Khung Shoal

Shoal đã giải quyết hai vấn đề về độ 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ó các đ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, chọn lựa nghiêng về lãnh đạo nhanh.

Thách thức

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

1. Các nỗ lực trước đây để sửa đổi logic Bullshark cốt lõi dường như về bản chất là không thể.

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

Là bằng chứng về độ khó của vấn đề, việc triển khai Bullshark ( bao gồm những 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 giải pháp lại ẩn chứa trong sự đơ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 để lưu trữ và diễn giải lại thông tin từ các vòng trước. Với sự đồng thuận của tất cả các xác thực về cái nhìn cốt lõi của điểm neo thứ nhất có thứ tự, Shoal kết hợp theo thứ tự nhiều phiên bản Bullshark để xử lý theo chuỗi, khiến cho ( điểm neo thứ nhất có thứ tự trở thành điểm chuyển đổi của các phiên bản, ) lịch sử nguyên nhân của các điểm neo được sử dụng để tính toán danh tiếng của nhà lãnh đạo.

Dây chuyền sản xuất

V ánh xạ các vòng đến người lãnh đạo. Shoal lần lượt chạy các phiên bản Bullshark, mỗi phiên bản có một đ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, kích hoạt chuyển 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 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 xác thực viên đều đồng ý với điểm neo này. Do đó, tất cả các xác thực viên có thể chắc chắn đồng ý rằng bắt đầu từ vòng r+1 sẽ diễn giải 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 hàng một mỏ neo trong mỗi vòng. Điểm mỏ neo của vòng đầu tiên được sắp xếp theo thể thức của trường hợp đầu tiên. Sau đó, Shoal bắt đầu một trường hợp mới trong vòng thứ hai, trường hợp này có một điểm mỏ neo, điểm mỏ neo này được sắp xếp theo trường hợp đó, sau đó, một trường hợp mới khác sẽ đặt hàng điểm mỏ neo trong vòng thứ ba, quá trình này tiếp tục.

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

Trong quá trình sắp xếp Bullshark, khi bỏ qua các điểm neo, độ trễ sẽ tăng lên. Trong trường hợp này, công nghệ pipeline không có tác dụng, vì không thể khởi động một 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 ít có 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ế danh tiếng để phân phối điểm dựa trên lịch sử hoạt động gần đây của mỗi nút xác thực. 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, các nút xác thực sẽ bị phân phối điểm thấp, vì nó có thể bị sập, chậm hoặc có hành vi xấu.

Ý tưởng của nó là trong mỗi lần cập nhật điểm số, một cách xác định sẽ tính toán lại ánh xạ F đã được định nghĩa trước từ lượt đến người lãnh đạo, thiên về những người lãnh đạo có điểm cao hơn. Để cho các xác thực viên đạt được sự đồng thuận trên ánh xạ mới, họ cần phải đạ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 để phát sinh điểm số.

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

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

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

Thời gian chờ đóng vai trò rất quan trọng trong tất cả các triển khai BFT đồng bộ dựa trên 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 phải quản lý và theo dõi, đ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ẽ tăng đáng kể độ trễ, vì việc cấu hình phù hợp cho chúng rất quan trọng, thường cần điều chỉnh động, vì nó phụ thuộc rất cao vào môi trường ( mạng ). Trước khi chuyển sang lãnh đạo tiếp theo, giao thức sẽ trả toàn bộ hình phạt độ trễ thời gian chờ cho lãnh đạo bị lỗi. 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 lãnh đạo tốt. Ví dụ, chúng tôi quan sát thấy, trong các trường hợp tải cao, lãnh đạo trong Jolteon/Hotstuff bị quá tải, và thời gian chờ đã hết trước khi thúc đẩy tiến triển.

Thật không may, các giao thức của người lãnh đạo như Hotstuff và Jolteon ( về cơ bản yêu cầu 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ố. Nếu không có thời gian chờ, ngay cả người lãnh đạo bị sập cũng có thể ngừng giao thức mãi mãi. Vì không thể phân biệt giữa người lãnh đạo gặp sự cố và người lãnh đạo hoạt động chậm trong thời gian bất đồng bộ, thời gian chờ có thể khiến các nút xác thực xem xét việc thay đổi tất cả các người lãnh đạo mà không có sự đồng thuận.

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