Kerangka Shoal: Bagaimana Drop latensi Bullshark Aptos

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

Shoal adalah sebuah kerangka kerja yang meningkatkan protokol konsensus berbasis Narwhal ( seperti DAG-Rider, Tusk, Bullshark ) melalui pemrosesan pipeline dan mekanisme reputasi pemimpin. Pipeline mengurangi latensi pengurutan DAG dengan memperkenalkan sebuah titik jangkar di setiap putaran, dan 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 dalam semua skenario. Ini memungkinkan Shoal untuk memberikan atribut yang kami sebut sebagai respons universal, yang mencakup respons optimistik yang biasanya diperlukan.

Teknologi kami sangat sederhana, yang melibatkan menjalankan beberapa instance dari protokol dasar secara berurutan satu demi satu. Oleh karena itu, ketika diinstansiasi dengan Bullshark, kami mendapatkan sekelompok "ikan hiu" yang sedang melakukan perlombaan estafet.

Motif

Dalam mengejar kinerja tinggi jaringan blockchain, orang-orang selalu memperhatikan Drop 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 kami yang lebih dari 100.000 TPS.

Tetapi terobosan terbaru berasal dari pemahaman bahwa penyebaran data adalah hambatan utama berdasarkan protokol pemimpin, dan dapat diuntungkan dari paralelisme. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, mengusulkan arsitektur di mana semua validator menyebarkan data secara bersamaan, sementara komponen konsensus hanya memesan sejumlah kecil metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.

Dalam artikel sebelumnya, kami memperkenalkan Quorum Store. Implementasi Narwhal kami memisahkan penyebaran data dari konsensus, serta bagaimana kami menggunakannya untuk memperluas protokol konsensus saat ini, Jolteon. Jolteon adalah protokol berbasis pemimpin yang menggabungkan jalur cepat linier 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 maksimal. Meskipun penyebaran data dipisahkan dari konsensus, pemimpin Hotstuff/Jolteon tetap terbatas seiring meningkatnya throughput.

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

Artikel ini akan memperkenalkan bagaimana Shoal dapat secara signifikan Drop latensi Bullshark.

Latar Belakang DAG-BFT

Mari kita pahami latar belakang yang relevan terlebih dahulu. Untuk deskripsi rinci tentang Narwhal dan Bullshark, silakan merujuk pada artikel DAG meets 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 harus merujuk setidaknya n-f simpul dari putaran sebelumnya. Karena asinkronisitas jaringan, validator yang berbeda mungkin mengamati pandangan lokal DAG yang berbeda pada waktu yang berbeda.

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

Urutan Lengkap

Dapat mencapai konsensus 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 sisi 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: setelah beberapa putaran ( seperti dua putaran dalam Bullshark ) akan ada seorang pemimpin yang telah ditentukan sebelumnya, puncak pemimpin disebut titik jangkar;

2. Titik jangkar urutan: validator secara independen tetapi pasti menentukan titik jangkar mana yang dipesan dan mana yang dilewati;

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

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

Semua validator setuju pada titik jangkar terurut pertama.

Bullshark latensi

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

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

Masalah 2: Kasus kegagalan latensi, analisis latensi di atas berlaku untuk situasi tanpa kegagalan, di sisi lain, jika pemimpin dalam satu putaran tidak cukup cepat untuk menyiarkan titik jangkar, maka tidak dapat mengurutkan titik jangkar ( sehingga dilewati ), sehingga semua simpul yang tidak terurut dalam beberapa putaran sebelumnya harus menunggu titik jangkar berikutnya diurutkan. Ini akan secara signifikan menurunkan kinerja jaringan replikasi geografis, terutama karena waktu tunggu Bullshark digunakan untuk menunggu pemimpin.

Kerangka Shoal

Shoal menyelesaikan dua masalah latensi ini, dengan meningkatkan Bullshark( atau protokol BFT berbasis Narwhal lainnya) melalui pipeline, memungkinkan ada satu titik jangkar di setiap ronde, dan mengurangi latensi semua simpul non-jangkar dalam DAG menjadi tiga ronde. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya dalam DAG, yang membuat pemilihan condong ke pemimpin yang cepat.

Tantangan

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

1. Upaya pemrosesan lini sebelumnya mencoba memodifikasi logika inti Bullshark, tetapi ini pada dasarnya tampaknya tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan diresmikan dalam Carousel, berdasarkan kinerja masa lalu validator untuk secara dinamis memilih pemimpin masa depan. Ide tentang jangkar dalam Bullshark adalah (. Meskipun adanya perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark, hal itu dapat menyebabkan urutan yang sama sekali berbeda, yang mengarah pada inti masalah, yaitu memilih jangkar roda secara dinamis dan deterministik adalah perlu untuk menyelesaikan konsensus, dan validator perlu mencapai kesepakatan tentang sejarah terurut untuk memilih jangkar masa depan.

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

) Protokol

Meskipun ada tantangan di atas, seperti yang dikatakan pepatah, fakta membuktikan bahwa solusinya tersembunyi dalam kesederhanaan.

Di Shoal, kami bergantung pada kemampuan untuk melakukan perhitungan lokal di atas DAG, dan mewujudkan kemampuan untuk menyimpan dan menafsirkan ulang informasi dari beberapa putaran sebelumnya. Dengan semua validator setuju pada wawasan inti dari titik jangkar terurut pertama, Shoal secara berurutan menggabungkan beberapa instansi Bullshark dan memprosesnya secara paralel, sehingga ### titik jangkar terurut pertama adalah titik switching dari instansi, serta ( sejarah kausal dari titik jangkar digunakan untuk menghitung reputasi pemimpin.

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

) pemrosesan aliran

V yang memetakan putaran ke pemimpin. Shoal menjalankan instance Bullshark satu per satu, sehingga untuk setiap instance, jangkar ditentukan sebelumnya oleh pemetaan F. Setiap instance memesan satu jangkar, yang akan memicu perpindahan ke instance berikutnya.

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

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

Reputasi Pemimpin

Selama pengurutan Bullshark, melompati titik jangkar akan meningkatkan latensi. Dalam kasus ini, teknik pemrosesan jalur tidak ada gunanya, karena instance baru tidak dapat dimulai sebelum instance sebelumnya memesan titik jangkar. Shoal memastikan bahwa pemimpin yang sesuai untuk menangani titik jangkar yang hilang tidak mungkin dipilih di masa depan dengan memberikan skor kepada setiap node validasi berdasarkan sejarah aktivitas terbaru masing-masing node validasi 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 berperilaku jahat.

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

Di Shoal, pipeline dan reputasi pemimpin dapat secara alami digabungkan, karena keduanya menggunakan teknologi inti yang sama, yaitu menafsirkan ulang DAG setelah mencapai konsensus pada titik jangkar berurutan 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 dari titik jangkar yang terurut di putaran ke-r. Kemudian, node validator mulai dari putaran ke-r+1 menggunakan fungsi pemilihan titik jangkar yang diperbarui F' untuk menjalankan instance baru Bullshark.

Tidak ada lagi waktu yang habis

Waktu habis memainkan peran penting dalam semua implementasi BFT sinkronisasi deterministik berbasis pemimpin. Namun, kompleksitas yang mereka perkenalkan meningkatkan jumlah status internal yang perlu dikelola dan diamati, yang menambah kompleksitas proses debug, dan memerlukan lebih banyak teknik observabilitas.

Waktu habis juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengkonfigurasi mereka dengan tepat, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar penalti latensi waktu habis penuh untuk pemimpin yang gagal. Oleh karena itu, pengaturan waktu habis tidak boleh terlalu konservatif, tetapi jika waktu habis terlalu pendek, protokol mungkin akan melewati pemimpin yang baik. Misalnya, kami mengamati bahwa, dalam kondisi beban tinggi, Jolt.