Kerangka Shoal: Bagaimana Drop latensi Bullshark di Aptos?

Ringkasan

1. Aptos labs telah menyelesaikan dua masalah terbuka penting dalam DAG BFT, secara signifikan mengurangi latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan timeout dalam protokol nyata deterministik. Secara keseluruhan, dalam keadaan tanpa kegagalan, latensi Bullshark diperbaiki sebesar 40%, dan dalam keadaan kegagalan diperbaiki sebesar 80%.

2. 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 satu anchor point setiap putaran, sementara reputasi pemimpin lebih lanjut memperbaiki masalah latensi dengan memastikan anchor point terhubung dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan konstruksi DAG asinkron untuk menghilangkan timeout di semua skenario. Ini memungkinkan Shoal menyediakan sifat respons yang universal, termasuk respons optimis yang biasanya diperlukan.

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

Motivasi

Dalam mengejar kinerja tinggi jaringan blockchain, perhatian selalu diberikan pada 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.

Pecahan baru-baru ini berasal dari pemahaman bahwa penyebaran data adalah hambatan utama yang didasarkan pada protokol pemimpin, dan dapat diuntungkan 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.

Sebelumnya telah diperkenalkan Quorum Store, yang memisahkan penyebaran data dari konsensus, serta cara menggunakannya untuk memperluas protokol konsensus saat ini Jolteon. Jolteon adalah protokol berbasis pemimpin, yang menggabungkan jalur cepat linier Tendermint dan perubahan tampilan gaya PBFT, dapat mengurangi latensi Hotstuff sebesar 33%. Namun, protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal. Meskipun penyebaran data dipisahkan dari konsensus, dengan meningkatnya throughput, pemimpin Hotstuff/Jolteon tetap terbatas.

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 menjelaskan bagaimana Shoal dapat secara signifikan mengurangi latensi Bullshark.

Latar Belakang DAG-BFT

Setiap simpul dalam Narwhal DAG terkait dengan 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 DAG adalah tidak ambigu: jika dua node validasi memiliki simpul yang sama v dalam pandangan lokal DAG, maka mereka memiliki sejarah kausal v yang sepenuhnya sama.

Urutan Total

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 ( seperti dua putaran dalam Bullshark ) akan ada pemimpin yang telah ditentukan sebelumnya, dan puncaknya disebut titik jangkar.

2. Titik urut: Validator secara independen tetapi deterministik memutuskan titik mana yang akan dipesan dan mana yang akan dilewati.

3. Urutan sejarah kausal: Validator memproses 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 verifikasi yang jujur membuat daftar titik jangkar terurut, sehingga semua daftar berbagi awalan yang sama. Dalam Shoal, berikut adalah pengamatan terhadap 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 daripada versi asinkron, itu masih jauh dari yang terbaik.

Masalah 1: Rata-rata latensi blok. Di Bullshark, setiap putaran genap memiliki titik jangkar, sedangkan puncak pada 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 pada putaran ganjil memerlukan tiga putaran, dan puncak bukan titik jangkar pada putaran genap memerlukan empat putaran.

Masalah 2: Keterlambatan kasus kegagalan, analisis keterlambatan di atas berlaku untuk situasi tanpa kegagalan, di sisi lain, jika satu putaran pemimpin gagal untuk menyebarkan titik jangkar dengan cukup cepat, maka tidak dapat mengurutkan titik jangkar ( sehingga dilewati ), semua simpul yang belum terurut dari beberapa putaran sebelumnya harus menunggu titik jangkar berikutnya diurutkan. Ini secara signifikan menurunkan kinerja jaringan replikasi geografis, terutama karena Bullshark menggunakan waktu tunggu untuk pemimpin.

Kerangka Shoal

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

Tantangan

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

1. Jalur produksi sebelumnya mencoba untuk memodifikasi logika inti Bullshark, tetapi pada dasarnya tampaknya tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan diformalisasi dalam Carousel, berdasarkan kinerja masa lalu validator untuk memilih pemimpin masa depan secara dinamis, ide tentang jangkar di Bullshark. Meskipun ada perbedaan dalam status pemimpin tidak melanggar keamanan protokol ini, itu bisa menyebabkan urutan yang sama sekali berbeda di Bullshark, yang menimbulkan inti masalah, yaitu memilih jangkar secara dinamis dan deterministik diperlukan untuk mencapai konsensus, dan validator perlu mencapai kesepakatan tentang 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, kami bergantung pada 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 setuju pada wawasan inti dari titik jangkar berurutan pertama, Shoal secara berurutan menggabungkan beberapa instance Bullshark untuk memprosesnya secara paralel, sehingga ( titik jangkar berurutan pertama adalah titik peralihan instance, serta ) sejarah kausal dari titik jangkar digunakan untuk menghitung reputasi pemimpin.

Jalur 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 sebuah jangkar, yang akan memicu peralihan ke instance berikutnya.

Pada awalnya, Shoal memulai instansi 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 menginterpretasikan ulang DAG mulai dari putaran r+1. Shoal hanya memulai instansi 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 di putaran kedua, yang memiliki titik jangkar itu sendiri, jangkar tersebut diurutkan oleh contoh tersebut, dan kemudian, contoh baru lainnya memesan titik jangkar di putaran ketiga, dan proses ini berlanjut.

Reputasi Pemimpin

Selama pengurutan Bullshark, melewatkan titik jangkar akan meningkatkan latensi. Dalam kasus ini, teknologi pipeline tidak berdaya, karena instance baru tidak dapat diluncurkan 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 melalui 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.

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

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

Faktanya, satu-satunya perbedaan adalah, setelah pengurutan 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 lebih banyak waktu habis

Timeout 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 meningkatkan kompleksitas proses debugging dan memerlukan lebih banyak teknik observabilitas.

Timeout juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengonfigurasi mereka dengan benar, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar penalti latensi timeout penuh untuk pemimpin yang mengalami kegagalan. Oleh karena itu, pengaturan timeout tidak boleh terlalu konservatif, tetapi jika waktu timeout terlalu pendek, protokol mungkin akan melewatkan pemimpin yang baik. Sebagai contoh, kami mengamati bahwa dalam kondisi beban tinggi, pemimpin dalam Jolteon/Hotstuff kewalahan, dan timeout telah berakhir sebelum mereka dapat mendorong kemajuan.

Sayangnya, protokol yang berbasis pada pemimpin ( seperti Hotstuff dan Jolteon) pada dasarnya memerlukan latensi, untuk memastikan bahwa protokol dapat maju setiap kali pemimpin mengalami kegagalan. Tanpa latensi, bahkan pemimpin yang terhenti dapat menghentikan protokol selamanya. Karena tidak dapat membedakan antara yang baik dan yang buruk selama periode asinkron.