Kerangka Shoal: Bagaimana mengurangi keterlambatan Bullshark di Aptos?

Ringkasan

Aptos labs telah menyelesaikan dua masalah terbuka penting dalam DAG BFT, secara signifikan mengurangi latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan jeda dalam protokol nyata yang deterministik. Secara keseluruhan, telah memperbaiki latensi Bullshark sebesar 40% dalam kondisi tanpa kesalahan, dan 80% dalam kondisi dengan kesalahan.

Shoal adalah sebuah kerangka kerja yang meningkatkan protokol konsensus berbasis Narwhal seperti DAG-Rider, Tusk, Bullshark ( melalui pipeline dan reputasi pemimpin. Pipeline mengurangi latensi pengurutan DAG dengan memperkenalkan sebuah titik jangkar di setiap putaran, sedangkan reputasi pemimpin lebih lanjut memperbaiki masalah latensi dengan memastikan titik jangkar terkait dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal untuk memanfaatkan konstruksi DAG asinkron untuk menghilangkan timeout di semua skenario. Ini memungkinkan Shoal untuk memberikan apa yang kami sebut sebagai atribut respons universal, yang mencakup respons optimis yang biasanya diperlukan.

Teknologi ini sangat sederhana, di mana melibatkan menjalankan beberapa instance dari protokol dasar satu per satu secara berurutan. Oleh karena itu, ketika diinstansikan dengan Bullshark, kita mendapatkan sekelompok "ikan hiu" yang sedang melakukan perlombaan estafet.

![Penjelasan detail Shoal framework: Bagaimana mengurangi latensi Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-8d6acd885bad7b8f911bdce15a7c884f.webp(

Motivasi

Dalam mengejar kinerja tinggi jaringan blockchain, orang-orang selalu memperhatikan pengurangan kompleksitas komunikasi. Namun, pendekatan ini tidak menghasilkan peningkatan throughput yang signifikan. Misalnya, Hotstuff yang diimplementasikan dalam versi awal Diem hanya mencapai 3500 TPS, jauh di bawah target 100k+ TPS.

Terobosan terbaru berasal dari pemahaman bahwa penyebaran data merupakan kendala utama yang didasarkan pada kesepakatan para pemimpin, dan bahwa hal ini dapat diuntungkan dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, dan mengusulkan suatu arsitektur di mana semua validator secara bersamaan menyebarkan data, sementara komponen konsensus hanya mengurutkan sejumlah kecil metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.

Sebelumnya diperkenalkan Quorum Store - Narwhal yang mengimplementasikan pemisahan 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 hingga 33%. Namun, jelas bahwa protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal. Meskipun pemisahan penyebaran data dan konsensus terjadi, pemimpin Hotstuff/Jolteon tetap terbatas seiring dengan meningkatnya throughput.

Oleh karena itu, diputuskan 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%.

Artikel ini memperkenalkan bagaimana Shoal berhasil mengurangi latensi Bullshark secara signifikan.

![Penjelasan mendalam tentang kerangka Shoal: Bagaimana mengurangi latensi Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-f6b6281c928e3fa7a2412a480c9c1806.webp(

Latar Belakang DAG-BFT

Setiap simpul dalam Narwhal DAG terkait dengan sebuah 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 harus merujuk setidaknya n-f simpul dari putaran sebelumnya. Karena asinkronitas jaringan, validator yang berbeda mungkin mengamati pandangan lokal DAG yang berbeda pada waktu yang berbeda.

Salah satu atribut kunci DAG tidak ambigu: jika dua node verifikasi memiliki simpul yang sama v dalam pandangan lokal DAG mereka, maka mereka memiliki sejarah kausal v yang sepenuhnya sama.

![Penjelasan Detail Shoal Framework: Bagaimana Mengurangi Latensi Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-b7ed8888da112bae8d34c0fdb338b138.webp(

Urutan Lengkap

Dapat mencapai konsensus mengenai urutan total semua simpul dalam DAG tanpa biaya komunikasi tambahan. Untuk ini, validator dalam DAG-Rider, Tusk, dan Bullshark mengartikan struktur DAG sebagai suatu 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 telah ditentukan: Setiap beberapa putaran akan ada seorang pemimpin yang telah ditentukan sebelumnya, puncak pemimpin tersebut disebut sebagai titik jangkar;

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

3. Urutan sejarah kausal: Verifier memproses satu per satu daftar titik jangkar terurut mereka, dan untuk setiap titik jangkar, mereka mengurutkan semua simpul sebelumnya yang tidak terurut dalam sejarah kausal mereka menggunakan beberapa aturan deterministik.

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

Semua validator setuju pada titik jangkar terurut pertama.

![Penjelasan Lengkap Shoal Framework: Bagaimana Mengurangi Keterlambatan Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-46d37add0d9e81b2f295edf8eddd907f.webp(

Bullshark Tertunda

Keterlambatan Bullshark tergantung pada jumlah putaran antara titik jangkar yang terurut di dalam DAG. Meskipun versi sinkron Bullshark yang paling praktis memiliki keterlambatan yang lebih baik dibandingkan versi asinkron, itu masih jauh dari yang terbaik.

Pertanyaan 1: Rata-rata penundaan blok. Dalam Bullshark, setiap putaran genap memiliki satu titik jangkar, dan puncak setiap putaran ganjil diinterpretasikan sebagai suara. Dalam kasus umum, dibutuhkan 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, sedangkan puncak non-titik jangkar dalam putaran genap memerlukan empat putaran.

Pertanyaan 2: Kasus kegagalan yang tertunda, analisis keterlambatan di atas berlaku untuk situasi tanpa kegagalan, di sisi lain, jika pemimpin dari satu putaran tidak cukup cepat untuk menyiarkan titik jangkar, maka titik jangkar tersebut tidak dapat diurutkan ) sehingga dilewati (, sehingga semua titik yang tidak terurut dari beberapa putaran sebelumnya harus menunggu titik jangkar berikutnya diurutkan. Ini akan secara signifikan mengurangi kinerja jaringan replikasi geografis, terutama karena Bullshark timeout digunakan untuk menunggu pemimpin.

![Penjelasan Rinci tentang Kerangka Shoal: Bagaimana Mengurangi Keterlambatan Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-0b0928cb6240e994c1514c75e080a4b2.webp(

Kerangka Shoal

Shoal telah menyelesaikan dua masalah keterlambatan ini, dengan meningkatkan Bullshark) atau protokol BFT berbasis Narwhal lainnya( melalui pipa, memungkinkan adanya satu titik jangkar di setiap putaran, dan mengurangi keterlambatan semua titik non-jangkar di DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya di DAG, yang membuat pemilihan cenderung pada pemimpin yang cepat.

Tantangan

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

1. Jalur produksi sebelumnya mencoba mengubah logika Bullshark inti, tetapi secara esensial tampaknya itu tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan diformalisasi dalam Carousel, berdasarkan kinerja masa lalu validator untuk secara dinamis memilih pemimpin masa depan dari ide jangkar di Bullshark ). Meskipun adanya perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark, hal ini dapat menghasilkan urutan yang sangat berbeda, yang mengarah pada inti masalah, yaitu memilih jangkar roda secara dinamis dan deterministik adalah hal yang diperlukan untuk menyelesaikan konsensus, dan validator perlu mencapai kesepakatan mengenai sejarah terurut untuk memilih jangkar masa depan.

Sebagai bukti tingkat kesulitan masalah, implementasi Bullshark, termasuk implementasi yang saat ini ada di lingkungan produksi, tidak mendukung fitur-fitur ini.

Protokol

Meskipun ada tantangan di atas, solusi tersembunyi di balik kesederhanaan.

Di Shoal, bergantung pada kemampuan untuk melakukan komputasi lokal di atas DAG, dan mewujudkan kemampuan untuk menyimpan dan menginterpretasikan kembali informasi dari beberapa putaran sebelumnya. Dengan semua validator yang setuju pada wawasan inti dari titik jangkar berurutan pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk memprosesnya secara pipeline, sehingga ( titik jangkar berurutan pertama adalah titik peralihan dari instance, serta ) sejarah kausal dari titik jangkar digunakan untuk menghitung reputasi pemimpin.

Jalur Produksi

V yang memetakan putaran ke pemimpin. Shoal menjalankan instance Bullshark satu per satu, sehingga untuk setiap instance, anchor ditentukan terlebih dahulu oleh pemetaan F. Setiap instance memesan satu anchor, yang akan memicu peralihan ke instance berikutnya.

Pada awalnya, Shoal meluncurkan instance pertama Bullshark pada putaran pertama DAG dan menjalankannya sampai titik jangkar terurut pertama ditentukan, seperti di 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 meluncurkan instance Bullshark baru pada putaran r+1.

Dalam skenario terbaik, ini memungkinkan Shoal untuk memesan satu jangkar di setiap putaran. Titik jangkar putaran pertama diurutkan berdasarkan contoh pertama. Kemudian, Shoal memulai contoh baru pada putaran kedua, yang memiliki titik jangkar sendiri, yang diurutkan oleh contoh tersebut, lalu, contoh baru lainnya memesan titik jangkar pada putaran ketiga, dan proses tersebut berlanjut.

Reputasi Pemimpin

Selama periode pengurutan Bullshark, melewati titik jangkar akan meningkatkan latensi. Dalam kasus ini, teknik pipeline tidak berdaya, karena tidak mungkin untuk memulai instance baru sebelum memesan titik jangkar dari instance sebelumnya. Shoal memastikan bahwa pemimpin yang sesuai untuk menangani titik jangkar yang hilang tidak mungkin dipilih di masa depan dengan memberikan skor kepada setiap node validator berdasarkan sejarah aktivitas terkini masing-masing node validator menggunakan mekanisme reputasi. Validator yang merespons dan berpartisipasi dalam protokol akan mendapatkan skor tinggi, jika tidak, node validator akan diberikan skor rendah, karena mungkin mengalami keruntuhan, lambat, atau berbuat jahat.

Ide dasarnya adalah untuk menghitung kembali pemetaan F yang telah ditentukan dari putaran ke pemimpin secara deterministik setiap kali skor diperbarui, yang mengarah pada pemimpin dengan skor yang lebih tinggi. Agar para validator dapat mencapai konsensus pada pemetaan baru, mereka harus mencapai konsensus pada skor, sehingga mencapai konsensus pada sejarah yang digunakan untuk menghasilkan skor.

Di Shoal, jalur produksi dan reputasi pemimpin dapat digabungkan secara alami, karena keduanya menggunakan teknologi inti yang sama, yaitu menafsirkan kembali 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 validasi mulai dari putaran ke-r+1 menggunakan fungsi pemilihan titik jangkar yang diperbarui F' untuk menjalankan instance baru Bullshark.

Tidak ada lagi waktu habis

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

Waktu tunggu juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengkonfigurasi mereka dengan tepat, dan biasanya perlu disesuaikan secara dinamis, karena sangat tergantung pada lingkungan ( jaringan ). Sebelum berpindah ke pemimpin berikutnya, protokol ini