Kerangka Shoal: Mengurangi latensi Bullshark di Aptos secara signifikan

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 praktis yang deterministik. Secara keseluruhan, dalam situasi tanpa kesalahan, latensi Bullshark meningkat 40%, dan dalam situasi dengan kesalahan meningkat 80%.

Shoal adalah sebuah kerangka kerja yang memperkuat protokol konsensus berbasis Narwhal ( seperti DAG-Rider, Tusk, Bullshark ) melalui pipeline dan mekanisme reputasi pemimpin. Pipeline mengurangi latensi pengurutan DAG dengan memperkenalkan satu titik jangkar di setiap putaran, sedangkan reputasi pemimpin lebih lanjut memperbaiki masalah latensi dengan memastikan titik jangkar terkait dengan node verifikasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan konstruksi DAG asinkron untuk menghilangkan timeout di semua skenario. Hal ini memungkinkan Shoal untuk memberikan sifat respons universal, yang mencakup respons optimis yang biasanya diperlukan.

Teknologi ini sangat sederhana, melibatkan menjalankan beberapa instance protokol dasar satu per satu secara berurutan. Oleh karena itu, ketika menginstansiasi Bullshark, kita mendapatkan sekelompok "ikan hiu" yang sedang melakukan balapan estafet.

Latar Belakang

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 100.000+ TPS.

Terobosan terbaru berasal dari pemahaman bahwa penyebaran data adalah hambatan utama yang berbasis pada protokol pemimpin, dan dapat diuntungkan dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, mengusulkan sebuah 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 kami memperkenalkan Quorum Store, yaitu implementasi Narwhal kami 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 Tendermint dan perubahan tampilan gaya PBFT, 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 masih terbatas seiring dengan peningkatan throughput.

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

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

Latar Belakang DAG-BFT

Setiap simpul di Narwhal DAG terkait dengan satu putaran. Untuk masuk ke putaran ke-r, validator harus terlebih dahulu mendapatkan 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 saat yang berbeda.

Salah satu atribut kunci dari 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 sepenuhnya sama.

Pengantar

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 tepi mewakili suara.

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

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

2. Titik jangkar urutan: Validator secara independen tetapi secara deterministik memutuskan urutan titik jangkar mana yang akan diurutkan 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 yang tidak terurut sebelumnya dalam sejarah kausalnya berdasarkan beberapa aturan deterministik.

Kunci untuk memenuhi keamanan adalah memastikan bahwa dalam langkah (2), semua daftar titik jangkar terurut yang dibuat oleh node verifikasi yang jujur berbagi awalan yang sama. Di Shoal, kami membuat pengamatan berikut tentang semua protokol ini:

Semua validator setuju pada titik jangkar berurutan pertama.

Bullsharklatensi

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

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

Pertanyaan 2: Situasi kegagalan latensi. Analisis latensi di atas berlaku untuk situasi tanpa kegagalan, di sisi lain, jika pemimpin pada suatu putaran tidak cukup cepat untuk menyiarkan titik jangkar, maka titik jangkar tersebut 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 mengurangi kinerja jaringan replikasi geografis, terutama karena Bullshark menggunakan waktu tunggu untuk menunggu pemimpin.

Kerangka Shoal

Shoal menyelesaikan dua masalah latensi ini, dengan meningkatkan Bullshark( atau protokol BFT berbasis Narwhal lainnya) melalui pipa, memungkinkan adanya satu titik jangkar di setiap putaran, 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 kepada pemimpin yang cepat.

Tantangan

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

1. Upaya jalur produksi sebelumnya berusaha mengubah logika inti Bullshark, tetapi pada dasarnya tampaknya tidak mungkin.

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

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

Protokol

Meskipun ada tantangan di atas, ternyata solusinya tersembunyi dalam kesederhanaan.

Dalam Shoal, kami mengandalkan kemampuan untuk melakukan perhitungan lokal pada DAG, dan mewujudkan kemampuan untuk menyimpan dan menafsirkan kembali informasi dari beberapa putaran sebelumnya. Dengan semua validator setuju pada pemahaman inti dari titik jangkar berurutan pertama, Shoal secara berurutan menggabungkan beberapa instance Bullshark untuk memprosesnya secara pipelining, menjadikan ( titik transisi dari instance jangkar berurutan pertama, serta ) sejarah kausal dari titik jangkar 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 mengurutkan sebuah jangkar, yang akan memicu perpindahan ke instance berikutnya.

Pada awalnya, Shoal meluncurkan 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 menafsirkan ulang DAG mulai dari putaran r+1. Shoal hanya meluncurkan instansi Bullshark baru pada putaran r+1.

Dalam kasus terbaik, ini memungkinkan Shoal untuk mengurutkan sebuah jangkar di setiap putaran. Jangkar titik pertama diurutkan berdasarkan contoh pertama. Kemudian, Shoal memulai sebuah contoh baru di putaran kedua, yang memiliki jangkar, jangkar tersebut diurutkan oleh contoh itu sendiri, kemudian, contoh baru lainnya mengurutkan jangkar di putaran ketiga, dan proses tersebut berlanjut.

Reputasi Pemimpin

Selama pengurutan Bullshark, melewatkan titik jangkar akan meningkatkan latensi. Dalam kasus ini, teknik pipeline tidak dapat berfungsi, karena instansi baru tidak dapat dimulai sebelum titik jangkar dari instansi sebelumnya diurutkan. Shoal memastikan bahwa pemimpin yang sesuai untuk menangani titik jangkar yang hilang tidak mungkin dipilih di masa depan dengan menggunakan mekanisme reputasi untuk memberikan skor kepada setiap node verifikasi berdasarkan riwayat aktivitas terbaru masing-masing node verifikasi. Validator yang merespons dan berpartisipasi dalam protokol akan mendapatkan skor tinggi, jika tidak, node verifikasi akan diberikan skor rendah, karena mungkin mengalami kegagalan, lambat, atau berperilaku jahat.

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

Di Shoal, pipeline dan reputasi pemimpin 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 dari 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 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 diamati, yang menambah kompleksitas proses debugging, serta memerlukan lebih banyak teknik observabilitas.

Waktu habis juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengkonfigurasi mereka dengan benar, dan biasanya memerlukan penyesuaian dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar sanksi waktu habis penuh untuk pemimpin yang mengalami kegagalan.