Analisis Kerangka Shoal: Mengurangi latensi Bullshark di Aptos secara signifikan

Aptos Labs baru-baru ini menyelesaikan dua masalah kunci dalam DAG BFT, secara signifikan Drop latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan timeout dalam protokol waktu nyata 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 ( melalui mekanisme jalur aliran dan reputasi pemimpin seperti DAG-Rider, Tusk, Bullshark ). Jalur aliran mengurangi latensi pengurutan DAG dengan memperkenalkan titik jangkar setiap putaran, sementara reputasi pemimpin lebih lanjut meningkatkan latensi dengan memastikan titik jangkar terhubung dengan node validasi tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan pembangunan DAG asinkron untuk menghilangkan semua skenario timeout. Ini memberi Shoal responsivitas umum, termasuk responsivitas optimis yang biasanya diperlukan.

Teknologi ini sangat sederhana, melibatkan menjalankan beberapa instance dari protokol dasar secara berurutan. Menggunakan Bullshark untuk menginstansiasi setara dengan sekelompok "ikan hiu" yang sedang melakukan estafet.

Latar Belakang dan Motivasi

Dalam mengejar kinerja tinggi jaringan blockchain, mengurangi kompleksitas komunikasi selalu menjadi fokus perhatian. Namun, pendekatan ini tidak membawa peningkatan throughput yang signifikan. Misalnya, Hotstuff yang diimplementasikan di Diem awal hanya mencapai 3500 TPS, jauh di bawah target 100.000+ TPS.

Pecahan terbaru berasal dari pemahaman bahwa penyebaran data adalah hambatan utama yang didasarkan pada protokol pemimpin, yang dapat mendapatkan manfaat dari paralelisasi. Sistem Narwhal memisahkan penyebaran data dari logika konsensus inti, mengusulkan arsitektur di mana semua validator secara bersamaan menyebarkan data, dan komponen konsensus hanya menyortir sejumlah kecil metadata. Makalah Narwhal melaporkan throughput mencapai 160.000 TPS.

Aptos sebelumnya memperkenalkan Quorum Store, yaitu implementasi Narwhal, yang memisahkan penyebaran data dan konsensus, untuk memperluas protokol konsensus Jolteon saat ini. Jolteon menggabungkan jalur cepat linier Tendermint dan perubahan tampilan gaya PBFT, yang dapat menurunkan latensi Hotstuff sebesar 33%. Namun, protokol konsensus berbasis pemimpin tidak dapat memanfaatkan potensi throughput Narwhal secara maksimal.

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

Kerangka Shoal dirancang untuk secara signifikan menurunkan latensi Bullshark.

Latar Belakang DAG-BFT

Setiap simpul dalam Narwhal DAG terkait dengan suatu putaran. Masuk ke putaran ke-r, validator harus terlebih dahulu memperoleh n-f simpul dari putaran ke-r-1. Setiap validator dapat menyiarkan satu simpul setiap putaran, dan setiap simpul harus merujuk setidaknya n-f simpul dari putaran sebelumnya. Karena asinkronisitas jaringan, validator yang berbeda mungkin melihat pandangan lokal DAG yang berbeda pada waktu yang berbeda.

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

Urutan Total

Konsensus tentang total urutan semua simpul dalam DAG dapat dicapai tanpa biaya komunikasi tambahan. Untuk ini, validator di DAG-Rider, Tusk, dan Bullshark menginterpretasikan struktur DAG sebagai protokol konsensus, di mana simpul mewakili usulan dan tepi mewakili suara.

Semua protokol konsensus berbasis Narwhal memiliki struktur berikut:

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

2. Titik urut: Validator secara independen namun deterministik memutuskan titik urut mana yang akan dipilih, dan titik urut mana yang akan dilewati.

3. Urutkan sejarah kausal: validator secara berurutan memproses daftar titik jangkar yang terurut, mengurutkan simpul tidak terurut sebelumnya dalam sejarah kausal setiap titik jangkar.

Kunci keamanan adalah memastikan bahwa dalam langkah (2), semua daftar titik jangkar terurut yang dibuat oleh node validasi yang jujur berbagi awalan yang sama. Shoal mengamati: semua validator setuju pada titik jangkar terurut pertama.

Bullshark latensi

Latensi Bullshark tergantung pada jumlah putaran antara titik jangkar terurut dalam DAG. Meskipun beberapa versi sinkron Bullshark memiliki latensi yang lebih baik dibandingkan versi asinkron, tetapi masih jauh dari yang terbaik.

Ada dua masalah utama:

1. Rata-rata latensi blok: Dalam situasi umum, vertex puncak putaran ganjil membutuhkan tiga putaran, sedangkan vertex non-penyangga putaran genap membutuhkan empat putaran untuk diurutkan.

2. Situasi gangguan latensi: Jika pemimpin pada putaran tertentu gagal untuk segera menyiarkan titik jangkar, yang menyebabkan titik jangkar tidak dapat diurutkan dan dilewati, maka simpul yang belum diurutkan pada beberapa putaran sebelumnya harus menunggu urutan titik jangkar berikutnya. Ini secara signifikan menurunkan kinerja jaringan replikasi geografis.

Kerangka Shoal

Shoal meningkatkan Bullshark( atau protokol BFT berbasis Narwhal) melalui pipeline, memungkinkan ada satu titik jangkar setiap putaran, mengurangi latensi semua simpul non-jangkar di dalam DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin tanpa biaya di dalam DAG, yang cenderung memilih pemimpin yang cepat.

Tantangan

Dalam konteks protokol DAG, pipa dan reputasi pemimpin dianggap sebagai masalah yang sulit:

1. Upaya sebelumnya untuk memodifikasi logika inti Bullshark tampaknya pada dasarnya tidak mungkin.

2. Reputasi pemimpin diperkenalkan dalam DiemBFT, dan secara resmi diformalkan dalam Carousel, memilih pemimpin masa depan secara dinamis berdasarkan kinerja masa lalu validator ( titik jangkar dalam Bullshark ). Meskipun perbedaan identitas pemimpin tidak melanggar keamanan, itu dapat menyebabkan urutan yang benar-benar berbeda dalam Bullshark.

Tantangan ini menyebabkan implementasi Bullshark saat ini di lingkungan produksi tidak mendukung fitur-fitur ini.

Protokol

Shoal mengandalkan kemampuan untuk melakukan perhitungan lokal di atas DAG, untuk mencapai kemampuan menyimpan dan menginterpretasikan kembali informasi dari beberapa putaran sebelumnya. Berdasarkan pandangan bahwa semua validator setuju dengan titik jangkar terurut pertama, Shoal menggabungkan beberapa instance Bullshark secara berurutan untuk pemrosesan pipeline, sehingga:

1. Titik jangkar berurutan pertama adalah titik peralihan dari instansi.
2. Sejarah kausal dari anchor digunakan untuk menghitung reputasi pemimpin

Jalur Produksi

V yang memetakan putaran ke pemimpin. Shoal menjalankan instance Bullshark secara berurutan, di mana titik jangkar setiap instance ditentukan sebelumnya oleh pemetaan F. Setiap instance mengurutkan satu titik jangkar, memicu peralihan ke instance berikutnya.

Shoal awalnya memulai instansi pertama Bullshark di putaran pertama DAG, berjalan hingga menentukan titik jangkar berurutan pertama ( yang diasumsikan di putaran r ). Semua validator setuju dengan titik jangkar ini, sehingga dapat secara deterministik setuju untuk menafsirkan ulang DAG mulai dari putaran r+1. Shoal memulai instansi Bullshark baru di putaran r+1.

Dalam kondisi ideal, ini memungkinkan Shoal untuk menyortir satu titik jangkar setiap putaran. Titik jangkar putaran pertama disortir oleh instansi pertama, kemudian Shoal memulai instansi baru di putaran kedua, menyortir titik jangkar putaran tersebut, dan seterusnya.

Reputasi Pemimpin

Ketika proses pengurutan Bullshark melewati titik jangkar, latensi akan meningkat. Dalam hal ini, teknologi pipeline tidak dapat berfungsi, karena tidak mungkin memulai instance baru sebelum instance sebelumnya menyortir titik jangkar. Shoal memberikan skor untuk setiap node validasi melalui mekanisme reputasi, memastikan bahwa pemimpin lambat yang sesuai kemungkinan besar tidak akan dipilih di masa depan berdasarkan sejarah aktivitas terbaru. Validator yang merespons dan berpartisipasi dalam protokol mendapatkan skor tinggi, jika tidak, mereka diberikan skor rendah.

Setiap kali skor diperbarui, secara deterministik menghitung ulang pemetaan F yang telah ditentukan dari putaran ke pemimpin, dengan preferensi pada pemimpin dengan skor tinggi. Agar validator dapat mencapai konsensus pada pemetaan baru, mereka perlu mencapai konsensus pada skor, sehingga mencapai konsensus pada sejarah yang digunakan untuk menurunkan skor.

Dalam Shoal, alur kerja dan reputasi pemimpin secara alami terintegrasi, karena keduanya menggunakan teknologi inti yang sama: menafsirkan ulang DAG setelah mencapai kesepakatan pada titik jangkar berurutan pertama.

Satu-satunya perbedaan adalah, setelah titik jangkar urutan putaran ke-r, validator hanya menghitung pemetaan baru F' mulai dari putaran ke-r+1 berdasarkan sejarah kausal dari titik jangkar berurutan putaran ke-r. Kemudian, node validator mulai menggunakan fungsi pemilihan titik jangkar yang diperbarui F' untuk menjalankan instance Bullshark baru mulai dari putaran ke-r+1.

Menghapus latensi

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

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

Sayangnya, protokol 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 mengalami keruntuhan pun dapat menghentikan protokol selamanya. Karena selama periode asinkron tidak dapat membedakan antara pemimpin yang mengalami kegagalan dan yang lambat, latensi dapat menyebabkan node verifikasi merotasi semua pemimpin tanpa adanya aktivitas konsensus.

Dalam Bullshark, timeout digunakan untuk konstruksi DAG, untuk memastikan bahwa pemimpin yang jujur dapat dengan cukup cepat menambahkan titik jangkar ke DAG selama periode sinkronisasi untuk pengurutan.

Shoal mengamati bahwa konstruksi DAG menyediakan "jam" untuk memperkirakan kecepatan jaringan. Dalam keadaan tanpa jeda, selama n-f validator yang jujur terus menambahkan simpul ke DAG, putaran akan terus bergerak maju. Meskipun Bullshark mungkin tidak dapat mengurutkan ( dengan kecepatan jaringan karena masalah pemimpin ), DAG masih tumbuh dengan kecepatan jaringan, meskipun beberapa pemimpin bermasalah atau jaringan tidak sinkron. Akhirnya, ketika pemimpin tanpa kesalahan cukup cepat untuk menyiarkan titik jangkar, seluruh sejarah kausal titik jangkar akan diurutkan.

Di Shoal, menghindari timeout sangat terkait dengan reputasi pemimpin. Menunggu pemimpin yang lambat berulang kali akan meningkatkan latensi, dan mekanisme reputasi pemimpin mengecualikan validator yang lambat untuk dipilih sebagai pemimpin. Dengan cara ini, sistem memanfaatkan node validasi cepat untuk beroperasi dengan kecepatan jaringan di semua skenario nyata.

Perlu dicatat bahwa hasil ketidakmungkinan FLP menunjukkan bahwa tidak ada protokol konsensus deterministik yang dapat menghindari latensi. Shoal tidak dapat menghindari hasil ini, karena ada jadwal kejadian antagonis secara teoretis yang dapat mencegah semua jangkar diurutkan. Sebaliknya, setelah jumlah jangkar yang dapat dikonfigurasi dilompati secara berkelanjutan, Shoal akan kembali ke latensi. Sebenarnya, kemungkinan situasi ini terjadi sangat kecil.

Responsif Umum

Makalah Hotstuff mempopulerkan konsep respons optimis, meskipun belum didefinisikan secara resmi, tetapi secara intuitif berarti bahwa protokol dapat berjalan pada kecepatan jaringan di bawah pemimpin yang baik ( dan jaringan sinkron ).

Shoal menawarkan atribut yang lebih baik, yang disebut responsif universal. Secara spesifik, dibandingkan dengan Hotstuff, Shoal akan terus beroperasi pada kecepatan jaringan bahkan jika pemimpin gagal dalam sejumlah putaran berkelanjutan yang dapat dikonfigurasi atau jaringan mengalami periode asinkron.

Responsivitas umum memberikan jaminan kemajuan yang jauh lebih baik selama periode asinkron dan ketika pemimpin mengalami kegagalan. Selama sinkronisasi dengan pemimpin yang lambat, atribut ini tidak dapat dibandingkan, karena bergantung pada seberapa lambat pemimpin tersebut. Namun, mengingat reputasi pemimpin, pemimpin lambat di Shoal seharusnya jarang terjadi.

Evaluasi

Aptos di atas Quorum Store yang diimplementasikan oleh Narwhal telah mengimplementasikan Bullshark dan Shoal. Berikut adalah beberapa sorotan evaluasi:

Pertama, untuk pertunjukan