Kerangka Shoal: Mengoptimalkan latensi konsensus Bullshark di Aptos

Aptos Labs baru-baru ini menyelesaikan dua masalah terbuka penting dalam DAG BFT, secara signifikan mengurangi latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan timeout dalam protokol nyata yang deterministik. Secara keseluruhan, dalam keadaan tanpa kegagalan, latensi Bullshark ditingkatkan sebesar 40%, dan dalam keadaan kegagalan ditingkatkan sebesar 80%.

Shoal adalah sebuah framework yang meningkatkan protokol konsensus berbasis Narwhal ( melalui pemrosesan pipeline dan mekanisme reputasi pemimpin seperti DAG-Rider, Tusk, Bullshark ). Pipeline mengurangi latensi pengurutan DAG dengan memperkenalkan satu titik jangkar setiap putaran, sementara reputasi pemimpin lebih jauh memperbaiki masalah latensi dengan memastikan bahwa titik jangkar terkait dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal untuk memanfaatkan konstruksi DAG asinkron untuk menghilangkan semua skenario timeout. Ini memungkinkan Shoal untuk memberikan karakteristik respons universal, termasuk respons optimis yang biasanya diperlukan.

Teknologi Shoal relatif sederhana, terutama menjalankan beberapa instance protokol dasar satu per satu secara berurutan. Ketika diinstansiasi dengan Bullshark, terbentuklah sekelompok "ikan hiu" yang sedang berlomba estafet.

Latar Belakang dan Motivasi

Dalam upaya mengejar kinerja tinggi jaringan blockchain, mengurangi kompleksitas komunikasi selalu menjadi fokus perhatian. Namun, metode ini tidak memberikan peningkatan throughput yang signifikan. Misalnya, Hotstuff yang diimplementasikan dalam versi awal Diem hanya mencapai 3500 TPS, jauh di bawah target 100k+ TPS.

Terobosan baru-baru ini berasal dari pemahaman bahwa penyebaran data adalah kendala utama yang didasarkan pada protokol pemimpin, dan dapat memperoleh manfaat dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, mengusulkan arsitektur di mana semua validator menyebarkan data secara bersamaan, sementara komponen konsensus hanya mengurutkan sejumlah kecil metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.

Aptos sebelumnya memperkenalkan Quorum Store, yaitu implementasi Narwhal, yang memisahkan penyebaran data dan Konsensus, serta bagaimana menggunakannya untuk memperluas protokol Konsensus saat ini, Jolteon. Jolteon adalah protokol berbasis pemimpin yang menggabungkan jalur cepat linier dari Tendermint dan perubahan tampilan gaya PBFT, yang dapat mengurangi latensi Hotstuff sebesar 33%. Namun, jelas bahwa protokol Konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara optimal. Meskipun penyebaran data dan Konsensus dipisahkan, dengan meningkatnya throughput, pemimpin Hotstuff/Jolteon tetap terbatas.

Oleh karena itu, Aptos memutuskan untuk menerapkan Bullshark di atas Narwhal DAG, sebuah protokol konsensus tanpa biaya komunikasi. Sayangnya, dibandingkan dengan Jolteon, struktur DAG yang mendukung Bullshark dengan throughput tinggi membawa biaya latensi sebesar 50%.

Latar Belakang DAG-BFT

Setiap simpul dalam Narwhal DAG terkait dengan satu putaran. Untuk memasuki putaran ke-r, validator harus terlebih dahulu memperoleh n-f simpul yang termasuk dalam putaran ke-r-1. Setiap validator dapat menyiarkan satu simpul per putaran, dan setiap simpul setidaknya merujuk pada n-f simpul dari putaran sebelumnya. Karena asinkronisitas jaringan, validator yang berbeda mungkin mengamati tampilan lokal DAG yang berbeda pada saat yang berbeda.

Salah satu atribut kunci dari DAG adalah non-ambiguity: jika dua node validasi memiliki vertex v yang sama dalam pandangan lokal DAG mereka, maka mereka memiliki sejarah kausal v yang sepenuhnya sama.

Pengantar

Dapat mencapai kesepakatan tentang urutan total semua simpul di DAG tanpa biaya komunikasi tambahan. Untuk ini, validator di DAG-Rider, Tusk, dan Bullshark menginterpretasikan struktur DAG sebagai protokol konsensus, di mana simpul mewakili proposal dan tepi mewakili suara.

Meskipun logika interseksi kelompok pada struktur DAG berbeda, semua protokol konsensus berbasis Narwhal yang ada memiliki struktur berikut:

1. Titik jangkar yang dijadwalkan: Setiap beberapa putaran (, misalnya, dalam Bullshark, setiap dua putaran ) akan ada seorang pemimpin yang telah ditentukan sebelumnya, puncak pemimpin tersebut disebut titik jangkar.

2. Titik jangkar urutan: validator secara independen tetapi deterministik memutuskan titik jangkar mana yang diurutkan dan mana yang dilewati.

3. Urutan sejarah kausal: validator menangani daftar titik jangkar yang terurut satu per satu, untuk setiap titik jangkar, mengurutkan semua simpul tidak terurut sebelumnya dalam sejarah kausalnya melalui aturan deterministik.

Kunci untuk memenuhi keamanan adalah memastikan bahwa pada langkah 2, semua node validator yang jujur membuat daftar titik jangkar yang terurut, sehingga semua daftar berbagi awalan yang sama. Dalam Shoal, ada pengamatan berikut terhadap semua protokol di atas: semua validator setuju pada titik jangkar yang terurut pertama.

Bullshark latensi

Latensi Bullshark tergantung pada jumlah putaran antara titik jangkar terurut di dalam DAG. Meskipun versi sinkronisasi Bullshark yang paling praktis memiliki latensi yang lebih baik dibandingkan versi asinkron, namun tetap jauh dari yang terbaik.

Ada dua masalah utama:

1. Rata-rata latensi blok: Dalam Bullshark, setiap putaran genap memiliki satu titik jangkar, dan setiap puncak putaran ganjil diartikan sebagai suara. Dalam kasus umum, diperlukan dua putaran DAG untuk mengurutkan titik jangkar, namun, puncak dalam sejarah kausal titik jangkar memerlukan lebih banyak putaran untuk menunggu titik jangkar diurutkan. Dalam kasus umum, puncak dalam putaran ganjil memerlukan tiga putaran, sementara puncak non-titik jangkar dalam putaran genap memerlukan empat putaran.

2. Kasus Kegagalan latensi: Jika seorang pemimpin dalam satu putaran gagal untuk menyiarkan titik jangkar dengan cukup cepat, maka titik jangkar tidak dapat diurutkan ( sehingga dilewati ), semua simpul yang belum diurutkan dalam beberapa putaran sebelumnya harus menunggu titik jangkar berikutnya diurutkan. Ini akan secara signifikan mengurangi kinerja jaringan replikasi geografis, terutama karena Bullshark menggunakan waktu tunggu untuk menunggu pemimpin.

Kerangka Shoal

Shoal meningkatkan Bullshark( atau protokol BFT berbasis Narwhal lainnya melalui pemrosesan lini, memungkinkan adanya satu titik jangkar di setiap putaran, dan mengurangi latensi semua simpul non-jangkar di DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya di DAG, sehingga pemilihan cenderung berpihak pada pemimpin yang cepat.

Tantangan

Dalam konteks protokol DAG, pemrosesan paralel dan reputasi pemimpin dianggap sebagai masalah yang sulit, alasannya adalah sebagai berikut:

1. Upaya pengolahan jalur sebelumnya mencoba mengubah logika inti Bullshark, tetapi tampaknya ini secara esensial tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan dipformalkan dalam Carousel, berdasarkan kinerja masa lalu validator untuk secara dinamis memilih pemimpin masa depan. Ide ini berkaitan dengan jangkar di Bullshark. Meskipun perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark, hal itu dapat menyebabkan urutan yang sangat berbeda. Ini mengarah pada inti masalah, yaitu memilih jangkar secara dinamis dan deterministik adalah hal yang diperlukan untuk menyelesaikan Konsensus, dan validator perlu mencapai kesepakatan tentang sejarah terurut untuk memilih jangkar masa depan.

Protokol

Meskipun ada tantangan di atas, solusi tersembunyi dalam kesederhanaan. Di Shoal, kemampuan untuk melakukan perhitungan lokal di atas DAG dimanfaatkan, memungkinkan penyimpanan dan reinterpretasi informasi dari beberapa putaran sebelumnya. Dengan semua validator setuju pada wawasan inti dari titik jangkar terurut pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk pemrosesan pipeline, sehingga:

1. Titik jangkar berurutan pertama adalah titik peralihan contoh.
2. Sejarah kausal dari titik jangkar digunakan untuk menghitung reputasi pemimpin

) Pemrosesan aliran

V yang memetakan putaran ke pemimpin. Shoal menjalankan contoh Bullshark satu per satu, sehingga untuk setiap contoh, anchor ditentukan sebelumnya oleh pemetaan F. Setiap contoh mengurutkan satu anchor, yang akan memicu peralihan ke contoh berikutnya.

Pada awalnya, Shoal memulai instance pertama Bullshark pada putaran pertama DAG dan menjalankannya sampai titik jangkar terurut pertama ditentukan, seperti pada putaran r. Semua validator setuju dengan titik jangkar ini. Oleh karena itu, semua validator dapat dengan pasti setuju untuk menafsirkan ulang DAG mulai dari putaran r+1. Shoal hanya memulai instance Bullshark baru pada putaran r+1.

Dalam skenario terbaik, ini memungkinkan Shoal untuk mengurutkan satu jangkar di setiap putaran. Jangkar putaran pertama diurutkan berdasarkan instance pertama. Kemudian, Shoal memulai instance baru di putaran kedua, yang sendiri memiliki jangkar, dan jangkar tersebut diurutkan oleh instance tersebut, lalu instance baru lainnya mengurutkan jangkar di putaran ketiga, dan proses ini terus berlanjut.

reputasi pemimpin

Selama periode pengurutan Bullshark, melompati titik jangkar akan meningkatkan latensi. Dalam hal ini, teknologi pemrosesan pipeline tidak berdaya, karena tidak mungkin memulai instance baru sebelum titik jangkar instance sebelumnya diurutkan. Shoal memastikan bahwa pemimpin yang sesuai tidak mungkin dipilih di masa depan untuk menangani titik jangkar yang hilang dengan memberikan skor kepada setiap node validasi berdasarkan sejarah aktivitas terbaru mereka menggunakan mekanisme reputasi. Validator yang merespons dan berpartisipasi dalam protokol akan mendapatkan skor tinggi, jika tidak, node validasi akan diberikan skor rendah, karena mungkin mengalami kegagalan, lambat, atau berbuat jahat.

Ideanya adalah untuk secara deterministik menghitung kembali pemetaan F yang telah ditentukan dari putaran ke pemimpin setiap kali pembaruan skor dilakukan, dengan kecenderungan pada pemimpin dengan skor lebih tinggi. Agar para validator dapat mencapai konsensus pada pemetaan baru, mereka harus mencapai konsensus pada skor, sehingga mencapai konsensus dalam sejarah yang digunakan untuk menurunkan skor.

Di Shoal, pemrosesan alur dan kepemimpinan reputasi dapat digabungkan secara alami, karena keduanya menggunakan teknologi inti yang sama, yaitu menafsirkan ulang DAG setelah mencapai konsensus pada titik jangkar terurut pertama.

Sebenarnya, satu-satunya perbedaan adalah, setelah mengurutkan titik jangkar di putaran ke-r, validator hanya perlu menghitung pemetaan baru F' mulai dari putaran ke-r+1 berdasarkan sejarah kausal titik jangkar yang terurut di putaran ke-r. Kemudian, node validator mulai menggunakan fungsi pemilihan titik jangkar yang diperbarui F' untuk menjalankan instance baru Bullshark mulai dari putaran ke-r+1.

Tidak perlu keterlambatan

Timeout memainkan peran penting dalam semua implementasi BFT berbasis pemimpin yang deterministik. Namun, kompleksitas yang diperkenalkan meningkatkan jumlah status internal yang perlu dikelola dan diamati, yang meningkatkan kompleksitas proses debugging, dan memerlukan lebih banyak teknik observabilitas.

Keterlambatan yang signifikan akan meningkat karena waktu habis, karena sangat penting untuk mengkonfigurasinya dengan benar dan seringkali perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar penalti keterlambatan penuh untuk pemimpin yang gagal. Oleh karena itu, pengaturan waktu habis tidak boleh terlalu konservatif, tetapi jika waktu habis terlalu pendek, protokol mungkin akan melewatkan pemimpin yang baik.

Sayangnya, protokol berbasis pemimpin ### seperti Hotstuff dan Jolteon ( pada dasarnya memerlukan latensi, untuk memastikan bahwa protokol dapat melanjutkan setiap kali pemimpin mengalami kegagalan. Tanpa latensi, bahkan pemimpin yang gagal dapat menghentikan protokol selamanya. Karena tidak mungkin untuk membedakan antara pemimpin yang gagal dan pemimpin yang lambat selama periode asinkron, latensi dapat menyebabkan node validasi melihat perubahan semua pemimpin tanpa aktifitas konsensus.

Dalam Bullshark, waktu habis digunakan untuk konstruksi DAG, untuk memastikan bahwa pemimpin yang jujur menambahkan titik jangkar ke DA selama periode sinkronisasi.