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

Tóm tắt

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 về thời gian chờ trong giao thức thực tế 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 cải thiện 80%.

Shoal là một khung, tăng cường giao thức đồng thuận dựa trên Narwhal ( thông qua đường ống và danh tiếng của người lãnh đạo như DAG-Rider, Tusk, Bullshark ). Đường ống giảm thiểu Trễ sắp xếp DAG bằng cách giới thiệu các điểm neo trong mỗi vòng, danh tiếng của người lãnh đạo cải thiện thêm Trễ bằng cách đảm bảo các điểm neo liên kết với các nút xác minh nhanh nhất. Hơn nữa, danh tiếng của người lãnh đạo cho phép Shoal khai thác cấu trúc DAG bất đồng bộ để loại bỏ thời gian chờ trong tất cả các kịch bản. Đ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, bao gồm 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ự. Do đó, khi khởi tạo bằng Bullshark, chúng tôi có một nhóm "cá mập" đang tham gia một cuộc tiếp sức.

Động cơ

Khi 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 sự cải thiện đáng kể về 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á đến 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 của các nhà lãnh đạo, có thể hưởng lợi từ sự song song. 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, đưa ra một kiến trúc trong đó tất cả các xác thực viên cùng lúc 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.

Trước đây, chúng tôi đã giới thiệu Quorum Store, tức là cách mà 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 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 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 độ 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 phát tán dữ liệu và đồng thuận, nhưng khi thông lượng tăng lên, 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, cấu trúc DAG hỗ trợ thông lượng cao của Bullshark đã mang lại chi phí Trễ 50%.

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

Bối cảnh DAG-BFT

Mỗi đỉnh trong Narwhal DAG đều liên quan đến một vòng. Để vào vòng thứ r, các xác thực viên phải đầu tiên có được n-f đỉnh thuộc vòng thứ r-1. Mỗi xác thực viên có thể phát sóng một đỉnh mỗi vòng, và mỗi đỉnh phải tham chiếu ít nhất 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 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 quan trọng của DAG là tính không mơ hồ: nếu hai nút xác minh có cùng đỉnh v trong cái nhìn địa phương của DAG, thì chúng có cùng lịch sử nguyên nhân v hoàn toàn.

Hoán vị toàn phần

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ó chi phí truyền thông 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 đề xuất và các cạnh đại diện cho 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 hiện có dựa trên Narwhal đều có cấu trúc sau:

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

2. Điểm neo sắp xếp: các validator độc lập nhưng xác định cách sắp xếp các điểm neo nào và 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 nhận viên xử lý danh sách các điểm neo có thứ tự một cách lần lượt, đối với mỗi điểm neo, thông qua một số quy tắc xác định, sắp xếp tất cả các đỉnh không có thứ tự trước đó trong lịch sử nguyên nhân của nó.

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

Tất cả các validator đề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ộ của Bullshark thực dụng hơn có độ trễ tốt hơn so với phiên bản không đồng bộ, nhưng nó vẫn còn xa mới đạt tối ưu.

Câu hỏi 1: Độ trễ trung bình của khối. Trong Bullshark, mỗi vòng chẵn đều có một điểm neo, và đỉnh của mỗi vòng lẻ được giải thích là để bỏ phiếu. Trong trường hợp phổ biến, cần hai vòng DAG để sắp xếp điểm neo, tuy nhiên, đỉ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 phổ biến, đỉnh trong vòng lẻ cần ba vòng, trong khi đỉnh không phải điểm neo trong vòng chẵn cần bốn vòng.

Vấn đề 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 người lãnh đạo trong một vòng không đủ nhanh để phát sóng điểm neo, thì không thể sắp xếp điểm neo ( vì vậy bị bỏ qua ), do đó tất cả các đỉnh chưa được sắp xếp trong các vòng trước phải chờ đợi điểm neo tiếp theo được sắp xếp. Điều này sẽ làm giảm hiệu suất của mạng sao chép địa lý một cách đáng kể, đặc biệt là vì Bullshark sử dụng thời gian chờ để chờ người lãnh đạo.

Khung Shoal

Shoal đã giải quyết 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 cho 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, vấn đề về đường ống và uy tín của người lãnh đạo được coi là khó khăn, lý do như sau:

1. Các dây chuyền trước đây đã cố gắng sửa đổi logic chính của Bullshark, nhưng điều này về bản chất 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 quá khứ của các xác thực viên, ý tưởng của các điểm neo trong Bullshark (. Mặc dù có sự khác biệt trong danh tính người lãnh đạo không vi phạm sự an toàn trong các giao thức này, nhưng trong Bullshark, điều này có thể dẫn đến thứ tự hoàn toàn khác nhau, điều này dẫn đến cốt lõi của vấn đề, tức là việc lựa chọn động và xác định các điểm neo vòng là cần thiết để giải quyết sự đồng thuận, trong khi các xác thực viên cần đạt được sự đồng thuận về lịch sử có thứ tự để chọn các điểm neo trong tương lai.

Là bằng chứng về độ khó của vấn đề, chúng tôi nhận thấy việc thực hiện của Bullshark, bao gồm cả việc thực hiện 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.

![Giải thích chi tiết về khung Shoal: Làm thế nào để giảm Trễ Bullshark trên Aptos?])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(

Giao thức

Mặc dù có những thách thức như đã đề cập ở trên, nhưng giải pháp ẩ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 và đạt được khả năng lưu trữ và giải thích 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 viên 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实例 Bullshark để xử lý chúng theo chuỗi, khiến cho ) điểm neo có thứ tự đầu tiên trở thành điểm chuyển giao của các实例, cũng như ( lịch sử nguyên nhân của các điểm neo được sử dụng để tính toán uy tín của 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 cho 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 sắp xếp một điểm neo, điều này sẽ 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à vận hành 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 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 đều có thể chắc chắn đồng ý rằng từ vòng r+1 trở đi 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 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 theo thể hiện đầu tiên. Sau đó, Shoal bắt đầu một thể hiện mới trong vòng thứ hai, nó có một điểm neo mà được sắp xếp bởi thể hiện đó, sau đó, một thể hiện mới khác sắp xếp điểm neo trong vòng thứ ba, và quá trình này tiếp tục.

![Giải thích chi tiết về khung Shoal: Làm thế nào để giảm Trễ Bullshark trên Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Danh tiếng lãnh đạo

Trong quá trình sắp xếp Bullshark, khi bỏ qua điểm neo, Trễ sẽ tăng lên. Trong trường hợp này, công nghệ ống dẫn không thể làm gì, vì không thể khởi động một phiên bản mới trước khi sắp xếp đ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 có khả năng được chọn để xử lý các điểm neo bị mất trong tương lai bằng cách sử dụng cơ chế uy tín để gán 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 chúng. Các nút xác thực 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ẽ được gán điểm thấp, vì chúng có thể bị sập, chậm hoặc phạm tội.

Ý tưởng của nó là vào 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 từ vòng đến người lãnh đạo, nghiêng về phía những người lãnh đạo 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 đạt được sự đồng thuận về điểm số, từ đó đạt được sự đồng thuận trên lịch sử được dùng để phát sinh điểm số.

Trong Shoal, chuỗi công việc 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à việc 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.

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 thứ r, các xác thực viên 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 bắt đầu từ vòng thứ 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 lựa chọn điểm neo đã cập nhật F'.

![Giải thích chi tiết về khung Shoal: Làm thế nào để giảm Trễ Bullshark trên Aptos?])https://img-cdn.gateio.im/webp-social/moments-1baf540693f376d93cb18ef3193593cc.webp(

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ộ phần xác định 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 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 vượt quá 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ả một hình phạt thời gian vượt quá đầy đủ cho nhà lãnh đạo bị lỗi. Do đó,