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 timeout dalam protokol praktis yang deterministik. Secara keseluruhan, dalam kondisi tanpa kesalahan, latensi Bullshark meningkat 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 jalur dan reputasi pemimpin. Jalur mengurangi latensi pengurutan DAG dengan memperkenalkan titik jangkar setiap putaran, sementara reputasi pemimpin lebih lanjut memperbaiki latensi dengan memastikan titik jangkar terkait dengan node verifikasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal untuk memanfaatkan konstruksi DAG asinkron untuk menghilangkan waktu habis di semua skenario. Ini memungkinkan Shoal untuk memberikan atribut yang kami sebut sebagai respons universal, yang mencakup respons optimis yang biasanya diperlukan.

Teknologi kami sangat sederhana, melibatkan beberapa instance protokol dasar yang dijalankan secara berurutan. Oleh karena itu, ketika diinstansiasi dengan Bullshark, kami mendapatkan sekelompok "hiu" yang sedang melakukan 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.

Terobosan terbaru berasal dari pemahaman bahwa penyebaran data adalah kendala utama yang bergantung pada protokol pemimpin, yang 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 sedikit metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.

Sebelumnya kami memperkenalkan Quorum Store, yaitu bagaimana implementasi Narwhal kami 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, protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal. Meskipun penyebaran data dan konsensus dipisahkan, dengan meningkatnya throughput, pemimpin Hotstuff/Jolteon masih terbatas.

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

Artikel ini memperkenalkan bagaimana Shoal secara signifikan mengurangi latensi Bullshark.

Latar Belakang DAG-BFT

Setiap simpul di 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 adanya ambiguitas: jika dua node validasi memiliki titik v yang sama dalam pandangan lokal DAG, maka mereka memiliki sejarah kausal v yang sepenuhnya sama.

Urutan Lengkap

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 interaksi 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 seorang pemimpin yang telah ditentukan sebelumnya, puncak pemimpin disebut titik jangkar;

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

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

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

Semua validator setuju pada titik jangkar yang terurut pertama.

Bullsharklatensi

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

Pertanyaan 1: Rata-rata latensi blok. Dalam Bullshark, setiap putaran genap memiliki satu titik jangkar, dan puncak setiap putaran ganjil dianggap 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. Dalam kasus umum, puncak dalam putaran ganjil membutuhkan tiga putaran, sedangkan puncak non-titik jangkar dalam putaran genap membutuhkan 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 dapat cukup cepat menyiarkan titik jangkar, maka titik jangkar tidak dapat diurutkan ( sehingga dilewati ), oleh karena itu 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 mengatasi dua masalah latensi ini, dengan meningkatkan Bullshark( atau protokol BFT berbasis Narwhal lainnya) melalui pipeline, memungkinkan adanya titik jangkar di setiap putaran, dan mengurangi latensi semua vertex non-titik 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, reputasi jalur dan pemimpin dianggap sebagai masalah yang sulit, dengan alasan sebagai berikut:

1. Sebelumnya, jalur aliran mencoba mengubah logika inti Bullshark, tetapi ini tampaknya pada dasarnya tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan secara resmi diformalkan di Carousel, berdasarkan pemilihan dinamis pemimpin masa depan menurut kinerja masa lalu validator ( ide titik jangkar di Bullshark ). Meskipun ada perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark, itu dapat menyebabkan urutan yang sangat berbeda, yang mengarah pada inti masalah, yaitu pemilihan titik jangkar dengan cara dinamis dan deterministik diperlukan untuk menyelesaikan konsensus, dan validator perlu mencapai kesepakatan tentang sejarah berurutan untuk memilih titik jangkar di 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, solusi tersembunyi dalam kesederhanaan.

Di Shoal, kami mengandalkan kemampuan untuk melakukan komputasi lokal di atas DAG, dan mewujudkan kemampuan untuk menyimpan dan menafsirkan kembali informasi dari beberapa putaran sebelumnya. Dengan semua validator setuju pada wawasan inti dari titik jangkar terurut pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk memprosesnya dalam aliran, sehingga ( titik jangkar terurut pertama adalah titik peralihan dari instance, 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, anchor point sudah ditentukan sebelumnya oleh pemetaan F. Setiap instance mengurutkan satu anchor point, yang memicu transisi ke instance berikutnya.

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

Dalam kasus terbaik, ini memungkinkan Shoal untuk mengurutkan satu titik 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, yang diurutkan oleh instance tersebut, kemudian, instance baru lainnya mengurutkan titik jangkar di putaran ketiga, dan proses tersebut berlanjut.

Reputasi Pemimpin

Saat melewati titik jangkar selama pengurutan Bullshark, latensi akan meningkat. Dalam kasus ini, teknologi pipeline tidak dapat membantu, karena tidak mungkin memulai instansi baru sebelum mengurutkan titik jangkar dari instansi sebelumnya. 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 kepada setiap node validasi berdasarkan sejarah aktivitas terbaru masing-masing node validasi. 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 berbuat jahat.

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

Di Shoal, jalur 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 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 instansi baru Bullshark.

Tidak ada lagi waktu habis

Timeout memainkan peran krusial dalam semua implementasi BFT sinkronisasi berbasis pemimpin yang deterministik. Namun, kompleksitas yang mereka perkenalkan meningkatkan jumlah status internal yang perlu dikelola dan dipantau, yang menambah kompleksitas proses debugging dan memerlukan lebih banyak teknik observabilitas.

Waktu tunggu juga akan secara signifikan meningkatkan latensi, karena penting untuk mengonfigurasinya dengan tepat, dan sering kali perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar penalti latensi waktu tunggu penuh untuk pemimpin yang mengalami kegagalan. Oleh karena itu,