Kerangka Shoal: Menurunkan latensi Bullshark di Aptos secara signifikan

Aptos Labs baru-baru ini menyelesaikan dua masalah terbuka penting dalam DAG BFT, secara signifikan menurunkan latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan timeout dalam protokol nyata deterministik. Secara keseluruhan, dalam kondisi tanpa gangguan, latensi Bullshark meningkat sebesar 40%, dan dalam kondisi gangguan meningkat sebesar 80%.

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 di setiap putaran, sementara reputasi pemimpin lebih lanjut memperbaiki latensi dengan memastikan anchor point terkait dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan konstruk DAG asinkron untuk menghilangkan timeouts di semua skenario. Ini memungkinkan Shoal untuk menyediakan apa yang kami sebut sebagai atribut respons universal, yang mencakup respons optimis yang biasanya diperlukan.

Teknologi kami sangat sederhana, melibatkan beberapa instance dari protokol dasar yang dijalankan secara berurutan satu per satu. Oleh karena itu, ketika menggunakan Bullshark untuk menginstansiasi, kami mendapatkan sekelompok "ikan hiu" yang sedang melakukan balapan estafet.

Motivasi

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

Namun, terobosan terbaru berasal dari pemahaman bahwa penyebaran data merupakan hambatan utama yang didasarkan pada protokol pemimpin, dan dapat mengambil manfaat dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, dan 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.

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 menurunkan latensi Hotstuff sebesar 33%. Namun, jelas bahwa protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal. Meskipun pemisahan penyebaran data dari konsensus, dengan meningkatnya throughput, pemimpin Hotstuff/Jolteon masih terbatas.

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

Dalam artikel ini, kami memperkenalkan bagaimana Shoal berhasil melakukan Drop latensi Bullshark secara signifikan.

Latar Belakang DAG-BFT

Mari kita mulai dengan memahami latar belakang yang relevan dari artikel ini.

Setiap simpul dalam Narwhal DAG terkait dengan satu putaran. Untuk memasuki putaran ke-r, validator harus terlebih dahulu mendapatkan n-f simpul yang termasuk dalam putaran ke-r-1. Setiap validator dapat membroadcast satu simpul per putaran, dan setiap simpul harus merujuk setidaknya n-f simpul dari putaran sebelumnya. Karena asinkronisitas jaringan, validator yang berbeda mungkin mengamati tampilan lokal DAG yang berbeda pada waktu yang berbeda.

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

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

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

1. Titik jangkar yang dijadwalkan: Setiap beberapa putaran (, misalnya, dalam Bullshark, setiap dua putaran ) akan ada pemimpin yang ditentukan sebelumnya, puncak pemimpin disebut titik jangkar;

2. Titik urut: Validator secara independen tetapi dengan kepastian menentukan urutan titik mana yang akan dipesan dan titik mana yang akan dilewati;

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

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

Semua validator setuju dengan 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, itu masih jauh dari yang terbaik.

Pertanyaan 1: Rata-rata latensi blok. Dalam Bullshark, setiap putaran genap memiliki satu titik jangkar, sedangkan puncak pada 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. Dalam kasus umum, puncak pada putaran ganjil membutuhkan tiga putaran, sedangkan puncak non-titik jangkar pada 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 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 waktu habis Bullshark digunakan untuk menunggu pemimpin.

Kerangka Shoal

Shoal menyelesaikan dua masalah latensi ini, ia memperkuat Bullshark( atau protokol BFT berbasis Narwhal lainnya ) melalui pipa, memungkinkan adanya satu titik jangkar di setiap putaran, dan mengurangi latensi semua vertex non-jangkar di DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya di DAG, yang membuat pemilihan 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 memodifikasi logika inti Bullshark, tetapi pada dasarnya tampaknya tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT dan formalized dalam Carousel, adalah pemilihan pemimpin masa depan secara dinamis berdasarkan kinerja masa lalu dari validator dalam (Bullshark dengan ide bahwa jangkar dalam ). Meskipun ada perbedaan dalam identitas pemimpin tidak melanggar keamanan dalam protokol ini, namun dalam Bullshark, itu dapat menyebabkan urutan yang sangat berbeda, yang mengarah pada inti masalah, yaitu memilih jangkar putaran secara dinamis dan deterministik diperlukan untuk menyelesaikan konsensus, dan validator perlu mencapai konsensus tentang sejarah terurut untuk memilih jangkar masa depan.

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

Protokol

Meskipun ada tantangan di atas, seperti kata pepatah, solusi terbukti tersembunyi di balik kesederhanaan.

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

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

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

Reputasi Pemimpin

Saat melewati titik jangkar selama pengurutan Bullshark, latensi akan meningkat. Dalam kasus ini, teknik pipeline tidak berdaya, karena tidak mungkin memulai instansi baru sebelum memesan titik jangkar dari instansi sebelumnya. Shoal memastikan bahwa pemimpin yang sesuai kemungkinan besar tidak akan dipilih di masa depan untuk menangani titik jangkar yang hilang dengan menggunakan mekanisme reputasi untuk memberikan skor kepada setiap node validasi berdasarkan riwayat aktivitas terbaru mereka. Validator yang merespon dan berpartisipasi dalam protokol akan mendapatkan skor tinggi, jika tidak, node validasi akan diberikan skor rendah, karena mungkin mengalami kegagalan, lambat, atau berbuat jahat.

Filosofinya adalah pada setiap pembaruan skor, secara deterministik menghitung kembali pemetaan F yang telah ditentukan dari putaran ke pemimpin, yang memihak kepada pemimpin dengan skor lebih tinggi. Agar para validator dapat mencapai konsensus pada pemetaan baru, mereka harus mencapai kesepakatan pada skor, sehingga mencapai kesepakatan pada sejarah yang digunakan untuk menurunkan skor.

Di Shoal, pipeline 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 acuan di putaran ke-r, validator hanya perlu menghitung pemetaan baru F' mulai dari putaran ke-r+1 berdasarkan sejarah kausal dari titik acuan yang terurut di putaran ke-r. Kemudian, node validator mulai dari putaran ke-r+1 menggunakan fungsi pemilihan titik acuan yang diperbarui F' untuk menjalankan instance baru Bullshark.

Tidak ada lebih banyak waktu habis

Timeout memainkan peran penting dalam semua implementasi BFT deterministik berbasis pemimpin. Namun, kompleksitas yang diperkenalkan oleh mereka meningkatkan jumlah status internal yang perlu dikelola dan diamati, yang menambah kompleksitas proses debugging, dan memerlukan lebih banyak teknik observabilitas.

Waktu habis juga akan secara signifikan meningkatkan latensi, karena sangat penting untuk mengonfigurasinya dengan tepat, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan ( jaringan ). Sebelum beralih ke pemimpin berikutnya, protokol akan membayar penalti latensi waktu habis penuh untuk pemimpin yang mengalami kegagalan. Oleh karena itu, pengaturan waktu habis tidak boleh terlalu konservatif, tetapi jika waktu habis terlalu pendek, protokol mungkin akan melewatkan pemimpin yang baik. Sebagai contoh, kami melihat