Kerangka Shoal: Bagaimana cara Drop latensi Bullshark di Aptos?

Ringkasan

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 praktis deterministik. Secara keseluruhan, dalam kondisi tanpa kegagalan, latensi Bullshark ditingkatkan sebesar 40%, dan dalam kondisi kegagalan ditingkatkan sebesar 80%.

Shoal adalah sebuah protokol konsensus yang didukung oleh Narwhal yang diperkuat melalui pipeline dan reputasi pemimpin ( seperti kerangka DAG-Rider, Tusk, Bullshark ). Pipeline mengurangi latensi pengurutan DAG dengan memperkenalkan sebuah anchor point di setiap putaran, reputasi pemimpin lebih lanjut memperbaiki masalah latensi dengan memastikan anchor point 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 menyediakan atribut yang disebut respons universal, yang mencakup respons optimis yang biasanya dibutuhkan.

Teknologi ini sangat sederhana, melibatkan menjalankan beberapa instance dari protokol yang mendasarinya secara berurutan. Oleh karena itu, ketika diinstansiasi dengan Bullshark, kita mendapatkan sekelompok "ikan hiu" yang sedang melakukan lomba estafet.

Motivasi

Dalam upaya untuk mencapai 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 100k+ TPS.

Terobosan terbaru berasal dari pemahaman bahwa penyebaran data adalah kendala utama dari protokol pemimpin, dan dapat mengambil manfaat dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, memperkenalkan arsitektur di mana semua validator secara bersamaan menyebarkan data, sementara komponen konsensus hanya mengurutkan 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 dengan baik. Meskipun penyebaran data dipisahkan dari konsensus, pemimpin Hotstuff/Jolteon tetap terbatas seiring dengan 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 menjelaskan bagaimana Shoal dapat secara signifikan mengurangi latensi Bullshark.

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 setiap putaran, dan setiap simpul harus merujuk setidaknya pada n-f simpul dari putaran sebelumnya. Karena asinkronisitas jaringan, validator yang berbeda mungkin mengamati pandangan lokal DAG yang berbeda pada titik waktu mana pun.

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

Peringkat Umum

Dapat mencapai konsensus tentang urutan total semua simpul dalam 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 akan dipesan dan mana yang akan dilewati;

3. urutan sejarah kausal: validator satu per satu memproses daftar titik jangkar terurut mereka, dan untuk setiap titik jangkar, mengurutkan semua simpul tidak terurut sebelumnya dalam sejarah kausal mereka melalui beberapa aturan deterministik.

Kunci untuk memenuhi keamanan adalah memastikan bahwa pada langkah (2), semua node validator yang jujur membuat daftar jangkar yang terurut, sehingga semua daftar berbagi awalan yang sama. Di Shoal, kami memberikan pengamatan berikut tentang 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 dalam DAG. Meskipun versi sinkronisasi Bullshark yang paling praktis memiliki latensi yang lebih baik dibandingkan dengan versi asinkron, namun itu jauh dari yang terbaik.

Pertanyaan 1: Rata-rata latensi blok. Di Bullshark, setiap putaran genap memiliki sebuah anchor, sementara setiap putaran ganjil puncaknya 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 dalam putaran ganjil memerlukan tiga putaran, sedangkan puncak non-anchor dalam putaran genap memerlukan empat putaran.

Masalah 2: Kasus kerusakan latensi, analisis latensi di atas berlaku untuk situasi tanpa kerusakan, di sisi lain, jika pemimpin dalam satu putaran tidak cukup cepat untuk menyiarkan titik jangkar, maka titik jangkar tidak dapat diurutkan ( 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 Bullshark timeout digunakan untuk menunggu pemimpin.

Kerangka Shoal

Shoal menyelesaikan kedua masalah latensi ini, dengan meningkatkan Bullshark( atau protokol BFT lainnya yang berbasis Narwhal) melalui pipeline, memungkinkan adanya satu anchor point di setiap putaran, dan mengurangi latensi semua vertex non-anchor dalam DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya dalam DAG, yang membuat pemilihan lebih condong kepada pemimpin yang cepat.

Tantangan

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

1. Sebelumnya, jalur alur mencoba memodifikasi logika inti Bullshark, tetapi pada dasarnya tampaknya hal ini tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan diformalkan dalam Carousel, berdasarkan performa masa lalu dari validator untuk secara dinamis memilih pemimpin masa depan, ide tentang jangkar di Bullshark (. Meskipun terdapat perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark, itu dapat menyebabkan urutan yang sangat berbeda, yang mengangkat inti masalah, yaitu bahwa pemilihan jangkar secara dinamis dan deterministik diperlukan untuk menyelesaikan konsensus, dan validator perlu mencapai kesepakatan tentang sejarah terurut untuk memilih jangkar masa depan.

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

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

Protokol

Meskipun ada tantangan di atas, seperti pepatah mengatakan, ternyata solusi tersembunyi dalam kesederhanaan.

Di Shoal, kami mengandalkan kemampuan untuk melakukan komputasi lokal di atas DAG, dan telah mewujudkan kemampuan untuk menyimpan dan menafsirkan kembali informasi dari beberapa putaran sebelumnya. Dengan semua validator menyetujui wawasan inti dari titik jangkar berurutan pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk memprosesnya secara berurutan, menjadikan ) titik peralihan instance dari titik jangkar berurutan pertama, 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, jangkar ditentukan sebelumnya oleh pemetaan F. Setiap instance memesan sebuah jangkar, yang akan memicu peralihan ke instance berikutnya.

Pada awalnya, Shoal meluncurkan instance pertama Bullshark di putaran pertama DAG dan menjalankannya sampai menentukan titik jangkar terurut pertama, misalnya di putaran r. Semua validator setuju dengan titik jangkar ini. Oleh karena itu, semua validator dapat dengan pasti setuju untuk menafsirkan kembali DAG mulai dari putaran r+1. Shoal hanya meluncurkan instance Bullshark baru di putaran r+1.

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

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

Reputasi Pemimpin

Selama periode penyortiran Bullshark, melompati titik jangkar akan meningkatkan latensi. Dalam hal ini, teknologi pipeline tidak dapat berfungsi, karena tidak mungkin memulai instance baru 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 validator berdasarkan sejarah aktivitas terbaru mereka 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 kegagalan, lambat, atau berbuat jahat.

Ide dasarnya adalah untuk secara deterministik menghitung ulang pemetaan F yang telah ditentukan dari putaran ke pemimpin setiap kali pembaruan skor, yang menguntungkan pemimpin dengan skor 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.

Dalam Shoal, jalur aliran dan reputasi pemimpin dapat secara alami digabungkan, 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 pada putaran ke-r, validator hanya perlu menghitung pemetaan baru F' mulai dari putaran ke-r+1 berdasarkan sejarah kausal dari titik jangkar yang terurut pada putaran ke-r. Kemudian, node validator mulai dari putaran ke-r+1 menggunakan fungsi pemilihan titik jangkar yang diperbarui F' untuk menjalankan contoh baru Bullshark.

![Penjelasan Detail Shoal Framework: Bagaimana Menurunkan latensi Bullshark di Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Tidak ada lagi waktu habis

Timeout berperan penting dalam semua implementasi BFT sinkronisasi bagian deterministik berbasis pemimpin. Namun, kompleksitas yang mereka perkenalkan meningkatkan jumlah keadaan internal yang perlu dikelola dan diamati, yang meningkatkan kompleksitas proses debugging dan memerlukan lebih banyak teknik observabilitas.

Timeout juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengonfigurasinya dengan benar, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ) jaringan (. Sebelum berpindah ke pemimpin berikutnya, protokol akan membayar penalti latensi timeout penuh untuk pemimpin yang gagal. Oleh karena itu, pengaturan timeout tidak boleh terlalu konservatif, tetapi jika