Kerangka Shoal: Bagaimana mengurangi latensi 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, latensi Bullshark ditingkatkan sebesar 40% dalam kondisi tanpa kesalahan, dan meningkat sebesar 80% dalam kondisi dengan kesalahan.

Shoal adalah sebuah kerangka kerja yang meningkatkan protokol konsensus berbasis Narwhal ( melalui pipelining dan reputasi pemimpin seperti DAG-Rider, Tusk, Bullshark ). Pipelining mengurangi latensi pengurutan DAG dengan memperkenalkan titik jangkar di setiap putaran, sementara reputasi pemimpin lebih lanjut memperbaiki masalah latensi dengan memastikan bahwa titik jangkar terkait dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal untuk memanfaatkan konstruksi DAG asinkron untuk menghilangkan timeouts di semua skenario. Ini memungkinkan Shoal untuk memberikan atribut respons yang universal, yang mencakup respons optimis yang biasanya dibutuhkan.

Teknologi ini sangat sederhana, melibatkan menjalankan beberapa instance dari protokol dasar secara berurutan. Oleh karena itu, ketika diinstansiasi dengan Bullshark, yang didapat adalah sekelompok "ikan hiu" yang sedang berlari estafet.

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.

Peningkatan 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.

Quorum Store yang diperkenalkan sebelumnya telah mewujudkan pemisahan antara penyebaran data dan konsensus untuk memperluas protokol konsensus saat ini, Jolteon. Jolteon adalah protokol berbasis pemimpin yang menggabungkan jalur cepat linier dari Tendermint dan perubahan tampilan gaya PBFT, mengurangi latensi Hotstuff sebesar 33%. Namun, protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal. Meskipun penyebaran data dan konsensus dipisahkan, seiring dengan peningkatan throughput, pemimpin Hotstuff/Jolteon tetap terbatasi.

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

Artikel ini memperkenalkan bagaimana Shoal secara signifikan mengurangi latensi Bullshark.

Latar Belakang DAG-BFT

Setiap simpul di Narwhal DAG terkait dengan putaran. Ketika memasuki putaran ke-r, validator harus terlebih dahulu memperoleh n-f simpul dari 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 titik waktu mana pun.

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

Urutan Total

Kesepakatan dapat dicapai mengenai urutan total semua simpul dalam DAG tanpa biaya komunikasi tambahan. Untuk ini, validator dalam 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 yang berbasis Narwhal memiliki struktur berikut:

1. Titik jangkar yang telah ditentukan: Setiap beberapa putaran, ada pemimpin yang ditentukan sebelumnya, yang puncaknya disebut titik jangkar.

2. Titik jangkar urutan: Validator secara independen tetapi dengan kepastian menentukan urutan atau melewatkan titik jangkar mana.

3. Riwayat kausal terurut: validator memproses daftar titik jangkar yang terurut satu per satu, mengurutkan titik puncak tidak terurut sebelumnya dalam riwayat kausal setiap titik jangkar.

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

Semua validator setuju pada titik jangkar yang terurut pertama.

Bullshark Penundaan

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

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

Pertanyaan 2: Keterlambatan Kasus Kerusakan. Analisis keterlambatan di atas berlaku untuk kondisi tanpa kerusakan; di sisi lain, jika seorang pemimpin putaran gagal untuk menyebarkan titik jangkar dengan cukup cepat, maka tidak mungkin untuk mengurutkan titik jangkar ( yang sehingga dilewati ), semua simpul yang belum diurutkan di 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 pemimpin.

Kerangka Shoal

Shoal menyelesaikan dua masalah keterlambatan ini, meningkatkan Bullshark( atau protokol BFT berbasis Narwhal lainnya) melalui pipa, memungkinkan setiap putaran memiliki titik jangkar, dan mengurangi keterlambatan semua simpul non-jangkar dalam DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya dalam DAG, yang memilih untuk memihak pemimpin yang cepat.

Tantangan

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

1. Upaya sebelumnya untuk memodifikasi logika inti Bullshark tampaknya secara esensial tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan secara resmi di Carousel, memilih pemimpin masa depan secara dinamis berdasarkan kinerja masa lalu validator ( jangkar di Bullshark ). Meskipun ada perbedaan dalam identitas pemimpin yang tidak melanggar keamanan protokol ini, hal ini dapat mengakibatkan urutan yang sangat berbeda di Bullshark, yang menimbulkan inti permasalahan: memilih jangkar putaran secara dinamis dan deterministik adalah yang diperlukan untuk menyelesaikan konsensus, validator perlu mencapai kesepakatan mengenai sejarah terurut untuk memilih jangkar masa depan.

Sebagai bukti tingkat kesulitan masalah, implementasi Bullshark ( termasuk dalam implementasi saat ini di lingkungan produksi ) tidak mendukung fitur-fitur ini.

Protokol

Meskipun ada tantangan di atas, solusinya tersembunyi dalam kesederhanaan.

Di Shoal, kami mengandalkan kemampuan untuk melakukan komputasi lokal di atas DAG, yang memungkinkan kami untuk menyimpan dan menginterpretasikan ulang informasi dari beberapa putaran sebelumnya. Dengan semua validator sepakat pada wawasan inti dari titik jangkar terurut pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk pemrosesan pipeline, menjadikan ( titik peralihan untuk instance, ) dan sejarah kausal dari titik jangkar digunakan untuk menghitung reputasi pemimpin.

Jalur Produksi

V yang memetakan putaran ke pemimpin. Shoal menjalankan instansi Bullshark satu per satu, setiap instansi jangkar ditentukan sebelumnya oleh pemetaan F. Setiap instansi memesan sebuah jangkar, memicu peralihan ke instansi berikutnya.

Pada awalnya, Shoal meluncurkan contoh pertama Bullshark pada putaran pertama DAG dan berjalan hingga titik jangkar terurut pertama ditentukan, seperti pada putaran ke-r. Semua validator setuju dengan titik jangkar ini. Oleh karena itu, semua validator dapat dengan pasti setuju untuk menafsirkan ulang DAG mulai dari putaran ke-r+1. Shoal hanya meluncurkan contoh Bullshark baru pada putaran ke-r+1.

Dalam kasus 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 sendiri, yang diurutkan oleh contoh tersebut, kemudian, contoh baru lainnya memesan titik jangkar di putaran ketiga, proses berlanjut.

Reputasi Pemimpin

Selama periode pengurutan Bullshark, melewati titik jangkar akan meningkatkan latensi. Dalam situasi ini, teknik pipeline tidak dapat berbuat banyak, karena tidak mungkin memulai instance baru sebelum titik jangkar pada instance sebelumnya dipesan. Shoal memastikan bahwa pemimpin yang sesuai untuk menangani titik jangkar yang hilang kemungkinan besar tidak akan dipilih di masa depan dengan menggunakan mekanisme reputasi untuk memberikan skor berdasarkan riwayat aktivitas terbaru setiap node validasi. Validator yang merespons dan berpartisipasi dalam protokol akan mendapatkan skor tinggi, jika tidak, node validasi akan diberikan skor rendah, karena mungkin mengalami keruntuhan, lambat, atau berbuat jahat.

Ideanya adalah untuk secara deterministik menghitung kembali pemetaan yang telah ditentukan F dari giliran ke pemimpin setiap kali pembaruan skor, yang menguntungkan pemimpin dengan skor lebih tinggi. Agar para validator dapat mencapai kesepakatan pada pemetaan baru, mereka harus mencapai kesepakatan pada skor, sehingga mencapai kesepakatan pada sejarah yang digunakan untuk menghasilkan skor.

Di Shoal, jalur aliran dan reputasi pemimpin dapat secara alami digabungkan, 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 pengurutan 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 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 berperan penting dalam semua implementasi BFT deterministik berbasis pemimpin. Namun, kompleksitas yang diperkenalkan 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 mengkonfigurasi mereka dengan benar, biasanya memerlukan penyesuaian dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar denda latensi timeout penuh untuk pemimpin yang gagal. Oleh karena itu, pengaturan timeout tidak boleh terlalu konservatif, tetapi jika waktu timeout terlalu pendek, protokol dapat melewatkan pemimpin yang baik. Sebagai contoh, kami mengamati bahwa dalam situasi beban tinggi, pemimpin dalam Jolteon/Hotstuff terbebani, dan timeout telah tercapai sebelum kemajuan dapat didorong.

Sayangnya, protokol yang didasarkan pada pemimpin ( seperti Hotstuff dan Jolteon) pada dasarnya memerlukan timeout, untuk memastikan bahwa protokol dapat melanjutkan setiap kali pemimpin mengalami kegagalan. Tanpa timeout, bahkan pemimpin yang mengalami kegagalan dapat menghentikan protokol selamanya. Karena selama periode asinkron tidak dapat membedakan antara pemimpin yang gagal dan pemimpin yang lambat, timeout dapat menyebabkan node validasi melihat semua pemimpin diubah tanpa adanya aktivitas konsensus.

Dalam Bullshark, waktu habis digunakan untuk konstruksi DAG, untuk memastikan bahwa pemimpin yang jujur menambahkan titik jangkar ke dalam DAG selama proses sinkronisasi.