Laboratorium Aptos telah memecahkan dua masalah terbuka yang penting di DAG BFT, sangat mengurangi latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan jeda dalam protokol praktis deterministik. Secara keseluruhan, ini meningkatkan latensi Bullshark sebesar 40% dalam kasus tanpa kegagalan dan 80% dalam kasus kesalahan.
Shoal adalah kerangka kerja yang meningkatkan protokol konsensus berbasis Narwhal (misalnya, DAG-Rider, Tusk, Bullshark) melalui perpipaan dan reputasi pemimpin. Pipelining mengurangi latensi pengurutan DAG dengan memperkenalkan jangkar per putaran, dan reputasi pemimpin semakin meningkatkan latensi dengan memastikan bahwa jangkar dikaitkan dengan validator tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan konstruksi DAG asinkron untuk menghilangkan waktu tunggu di semua skenario. Ini memungkinkan Shoal untuk menyediakan properti yang kami beri nama Respons Universal, yang berisi Respons Optimis yang biasanya diperlukan.
Teknik kami sangat sederhana, melibatkan menjalankan beberapa contoh dari protokol yang mendasari secara berurutan satu demi satu. Jadi, saat dipakai dengan Bullshark, kita mendapatkan sekelompok "hiu" yang sedang melakukan lari estafet.
Motivasi
Dalam mengejar kinerja tinggi dalam jaringan blockchain, selalu ada fokus untuk mengurangi kompleksitas komunikasi. Namun, pendekatan ini tidak menghasilkan peningkatan throughput yang signifikan. Misalnya, implementasi Hotstuff di Diem versi awal hanya mencapai 3500 TPS, jauh di bawah tujuan kami untuk mencapai 100k+ TPS.
Namun, terobosan baru-baru ini berasal dari kesadaran bahwa propagasi data adalah hambatan utama dari protokol berbasis pemimpin, dan dapat mengambil manfaat dari paralelisasi. Sistem Narwhal memisahkan propagasi data dari logika konsensus inti dan mengusulkan sebuah arsitektur di mana semua validator menyebarkan data secara bersamaan, sementara komponen konsensus hanya memesan sejumlah kecil metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.
Di artikel sebelumnya, kami memperkenalkan Toko Kuorum. Implementasi Narwhal kami memisahkan propagasi data dari konsensus, dan bagaimana kami menggunakannya untuk memperluas protokol konsensus kami saat ini, Jolteon. Jolteon adalah protokol berbasis pemimpin yang menggabungkan jalur cepat linier Tendermint dengan perubahan tampilan gaya PBFT untuk mengurangi latensi Hotstuff sebesar 33%. Namun, jelas bahwa protokol konsensus berbasis pemimpin tidak dapat sepenuhnya mengeksploitasi potensi throughput Narwhal. Meskipun memisahkan propagasi data dari konsensus, pemimpin Hotstuff/Jolteon masih terbatas karena peningkatan throughput.
Oleh karena itu, kami memutuskan untuk menggunakan Bullshark, sebuah protokol konsensus dengan overhead komunikasi nol, di atas Narwhal DAG. Sayangnya, struktur DAG yang mendukung throughput tinggi Bullshark hadir dengan penalti latensi 50% dibandingkan dengan Jolteon.
Dalam postingan ini, kami menjelaskan bagaimana Shoal mencapai pengurangan dramatis dalam latensi Bullshark.
Latar belakang DAG-BFT
Mari kita mulai dengan memahami latar belakang yang relevan dari artikel ini. Untuk deskripsi mendetail tentang Narwhal dan Bullshark, silakan lihat postingan DAG bertemu BFT.
Setiap simpul dalam DAG Narwhal dikaitkan dengan angka bulat. Untuk masuk ke putaran r, verifikator harus terlebih dahulu mendapatkan simpul nf yang termasuk dalam putaran r-1. Setiap verifier dapat menyiarkan satu simpul per putaran, dan setiap simpul mengacu pada setidaknya nf simpul di putaran sebelumnya. Karena asinkron jaringan, validator yang berbeda dapat mengamati tampilan lokal DAG yang berbeda kapan saja. Berikut adalah ilustrasi kemungkinan tampilan sebagian:
Gambar 1: Sejarah kausal simpul yang diidentifikasi oleh simpul validasi putaran 2 2 disorot dalam warna hijau
Properti utama DAG bukanlah ambiguitas: dua validator memiliki riwayat sebab akibat yang persis sama dari v jika mereka memiliki simpul v yang sama dalam tampilan DAG lokal mereka.
Jumlah Pesanan
Dimungkinkan untuk menyepakati urutan total semua simpul dalam DAG tanpa biaya komunikasi tambahan. Untuk tujuan ini, validator di DAG-Rider, Tusk, dan Bullshark menginterpretasikan struktur DAG sebagai protokol konsensus, di mana simpul mewakili proposal dan ujung mewakili suara.
Meskipun logika persimpangan grup berbeda pada struktur DAG, semua protokol konsensus berbasis Narwhal yang ada memiliki struktur berikut:
Jangkar yang ditentukan sebelumnya, akan ada pemimpin yang ditentukan sebelumnya setiap beberapa putaran (misalnya, dua putaran di Bullshark), dan puncak pemimpin disebut jangkar;
Memesan jangkar, pemverifikasi secara mandiri tetapi secara deterministik memutuskan jangkar mana yang akan dipesan dan jangkar mana yang akan dilewati;
Urutkan sejarah kausal, di mana validator memproses daftar urutan jangkar mereka satu per satu, dan untuk setiap jangkar, urutkan semua simpul yang sebelumnya tidak terurut dalam sejarah kausalnya dengan beberapa aturan deterministik.
Gambar 2: Ilustrasi kemungkinan tampilan parsial DAG dalam protokol Bullshark. Dalam contoh ini, jangkar merah dan kuning diurutkan, sedangkan hijau (bukan di DAG) dilewati. Oleh karena itu, untuk mengurutkan DAG, validator secara deterministik mengurutkan sejarah kausal jangkar merah terlebih dahulu, diikuti oleh jangkar kuning.
Kunci untuk memuaskan keamanan adalah memastikan bahwa pada langkah (2) di atas, semua validator yang jujur membuat daftar jangkar yang terurut sehingga semua daftar memiliki awalan yang sama. Di Shoal, kami melakukan pengamatan berikut untuk semua protokol di atas:
** Semua validator menyetujui jangkar yang dipesan pertama. **
Latensi Bullshark
Latensi Bullshark bergantung pada jumlah putaran antara jangkar yang dipesan di DAG. Meskipun versi Bullshark sebagian sinkron yang paling berguna memiliki latensi yang lebih baik daripada versi asinkron, versi ini jauh dari optimal.
Masalah 1: Latensi blok rata-rata. Di Bullshark, setiap putaran genap memiliki jangkar, dan simpul setiap putaran ganjil ditafsirkan sebagai suara. Biasanya, dibutuhkan dua putaran DAG untuk mengurutkan jangkar, namun, simpul dalam sejarah kausal jangkar memerlukan lebih banyak putaran untuk menunggu jangkar dipesan. Dalam kasus umum, simpul dalam putaran ganjil membutuhkan tiga putaran, sedangkan simpul non-anchor dalam putaran genap membutuhkan empat putaran (lihat Gambar 3).
Gambar 3: Dalam kasus umum, jangkar di putaran i+1 perlu disortir untuk dua putaran. Simpul pada putaran i diurutkan secara bersamaan, sehingga latensinya adalah tiga putaran. Namun, simpul di putaran i+1 harus menunggu jangkar berikutnya diurutkan (yang ada di putaran i+3), sehingga penundaan pengurutannya adalah empat putaran.
Masalah 2: Latensi kasus kegagalan, analisis latensi di atas berlaku untuk kasus tanpa kegagalan, di sisi lain, jika pemimpin putaran gagal menyiarkan jangkar dengan cukup cepat, jangkar tidak dapat dipesan (dan dengan demikian dilewati), jadi Semua simpul yang tidak disortir di putaran sebelumnya harus menunggu jangkar berikutnya diurutkan. Ini dapat secara signifikan mengurangi kinerja jaringan yang direplikasi secara geografis, terutama karena Bullshark menggunakan waktu tunggu menunggu pemimpin.
Kerangka Shoal
Shoal menyelesaikan kedua masalah latensi ini dengan meningkatkan Bullshark (atau protokol BFT berbasis Narwhal lainnya) dengan melakukan pipelining, memungkinkan jangkar di setiap putaran, dan mengurangi latensi semua simpul non-jangkar di DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin zero-overhead di DAG, yang mencondongkan pemilihan untuk mendukung pemimpin yang cepat.
tantangan
Dalam konteks protokol DAG, perpipaan dan reputasi pemimpin dianggap sebagai masalah yang sulit karena alasan berikut:
Upaya perpipaan sebelumnya untuk mengubah logika inti Bullshark, tetapi ini tampaknya mustahil
Reputasi Pemimpin, diperkenalkan di DiemBFT dan diformalkan di Carousel, adalah gagasan untuk secara dinamis memilih pemimpin masa depan (jangkar di Bullshark) berdasarkan kinerja validator di masa lalu. Sementara ketidaksepakatan atas identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark hal itu dapat menyebabkan urutan yang sama sekali berbeda, yang sampai ke inti pertanyaan, yaitu bahwa pemilihan jangkar roda yang dinamis dan deterministik adalah kunci untuk menyelesaikan konsensus yang diperlukan. , sementara validator perlu menyepakati urutan riwayat untuk memilih jangkar di masa mendatang.
Sebagai bukti kesulitan masalah, kami mencatat bahwa implementasi Bullshark, termasuk implementasi saat ini dalam produksi, tidak mendukung fitur ini.
protokol ###
Terlepas dari tantangan yang disebutkan di atas, ternyata solusinya, seperti kata pepatah, ada di balik kesederhanaan.
Di Shoal, kami mengandalkan kemampuan untuk melakukan komputasi lokal pada DAG dan mengimplementasikan kemampuan untuk menyimpan dan menafsirkan kembali informasi dari putaran sebelumnya. Dengan wawasan inti bahwa semua validator setuju pada jangkar yang dipesan pertama, Shoal menyalurkannya dengan menyusun beberapa instance Bullshark secara berurutan sedemikian rupa sehingga (1) jangkar yang dipesan pertama adalah titik peralihan untuk instance, dan (2) Sejarah kausal dari jangkar digunakan untuk menghitung reputasi pemimpin.
Pipanisasi
Mirip dengan Bullshark, validator menyetujui secara apriori tentang jangkar potensial, yaitu, ada pemetaan yang diketahui F: R -> V pemetaan putaran ke pemimpin. Shoal menjalankan instance Bullshark satu demi satu sehingga untuk setiap instance jangkar ditentukan sebelumnya oleh peta F. Setiap instance memerintahkan sebuah jangkar, yang memicu peralihan ke instance berikutnya.
Awalnya, Shoal meluncurkan instance Bullshark pertama di putaran pertama DAG dan menjalankannya hingga jangkar pesanan pertama diidentifikasi, katakanlah di putaran r. Semua validator menyetujui jangkar ini. Oleh karena itu, semua validator dapat menyetujui secara deterministik untuk menginterpretasikan kembali DAG mulai dari putaran r+1. Shoal baru saja memulai instance baru Bullshark pada putaran r+1.
Dalam skenario kasus terbaik, ini memungkinkan Shoal memesan jangkar setiap putaran. Jangkar untuk putaran pertama diurutkan berdasarkan kejadian pertama. Kemudian, Shoal memulai instance baru di babak kedua, yang dengan sendirinya memiliki jangkar yang diurutkan oleh instance, kemudian instance baru lainnya memerintahkan jangkar di babak ketiga, dan proses berlanjut. Silakan lihat ilustrasi di bawah ini:
Gambar 4: Verteks yang sesuai dengan pemimpin yang ditentukan oleh F ditandai dengan mahkota. Contoh pertama Bullshark pertama-tama menginterpretasikan DAG dengan jangkar pada putaran 1, 3, dan 5. Bullshark menentukan jangkar pada putaran 1 (dalam tanda centang hijau mark) adalah yang pertama diurutkan pada contoh pertama. (Perhatikan bahwa dalam kasus umum, jangkar ini dapat dilewati, sementara beberapa jangkar lainnya akan diurutkan terlebih dahulu.) Kemudian, contoh pertama lainnya diabaikan, dan contoh baru Bullshark dimulai dari putaran 2, titik Jangkar ditandai pada putaran 2 dan 4.
Reputasi pemimpin
Peningkatan latensi saat melewatkan jangkar selama penyortiran Bullshark. Dalam hal ini, teknik Pipelining tidak berdaya karena instance baru tidak dapat dimulai sampai instance sebelumnya memesan jangkar. Shoal memastikan bahwa pemimpin yang tepat kemungkinan kecil akan dipilih di masa depan untuk menangani jangkar yang hilang dengan menggunakan mekanisme reputasi untuk memberikan skor kepada setiap validator berdasarkan riwayat aktivitasnya baru-baru ini. Validator yang merespons dan berpartisipasi dalam protokol akan diberi skor tinggi, jika tidak, validator akan diberi skor rendah karena dapat macet, lambat, atau berbahaya.
Idenya adalah untuk secara deterministik menghitung ulang pemetaan F yang telah ditentukan dari putaran ke pemimpin di setiap pembaruan skor, memilih pemimpin dengan skor lebih tinggi. Agar validator menyepakati pemetaan baru, mereka harus menyepakati skor dan dengan demikian sejarah digunakan untuk mendapatkan skor.
Di Shoal, pipelining dan reputasi kepemimpinan dapat digabungkan secara alami karena keduanya menggunakan teknik inti yang sama dalam menafsirkan kembali DAG setelah menyepakati jangkar pesanan pertama.
Nyatanya, satu-satunya perbedaan adalah, setelah menyortir jangkar di putaran r, validator hanya perlu menghitung pemetaan baru F' dari putaran r+1 berdasarkan riwayat kausal dari jangkar yang dipesan di putaran r . Kemudian, validator mengeksekusi instance baru Bullshark mulai dari putaran r+1 menggunakan fungsi pemilihan jangkar yang diperbarui F'. Lihat gambar di bawah ini:
Gambar 5. Simpul yang sesuai dengan pemimpin yang diidentifikasi oleh F ditandai dengan mahkota transparan. Contoh pertama Bullshark memesan jangkar di babak 1, ditandai dengan tanda centang hijau, dan kemudian menghitung pemetaan baru F 'berdasarkan informasi dalam sejarah kausal jangkar. Pemimpin yang ditentukan oleh F' ditandai dengan mahkota berwarna.
Tidak ada lagi batas waktu
Timeout memainkan peran penting dalam semua implementasi BFT deterministik sebagian sinkron berbasis pemimpin. Namun, kerumitan yang mereka perkenalkan meningkatkan jumlah keadaan internal yang perlu dikelola dan diamati, yang memperumit proses debug dan memerlukan lebih banyak teknik pengamatan.
Waktu tunggu juga dapat menambah latensi secara signifikan, karena penting untuk mengonfigurasinya dengan tepat, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan (jaringan). Protokol membayar pemimpin yang salah penalti penundaan waktu tunggu penuh sebelum pindah ke pemimpin berikutnya. Oleh karena itu, pengaturan batas waktu tidak boleh terlalu konservatif, tetapi jika batas waktu terlalu singkat, protokol dapat melewatkan pemimpin yang baik. Misalnya, kami mengamati bahwa di bawah beban tinggi, pemimpin di Jolteon/Hotstuff kewalahan dan waktu tunggu habis sebelum mereka dapat mendorong kemajuan.
Sayangnya, protokol berbasis pemimpin seperti Hotstuff dan Jolteon pada dasarnya memerlukan waktu tunggu untuk memastikan bahwa protokol dapat membuat kemajuan setiap kali pemimpin gagal. Tanpa batas waktu, bahkan pemimpin yang jatuh dapat menghentikan protokol selamanya. Karena ketidakmampuan untuk membedakan antara pemimpin yang salah dan pemimpin yang lambat selama asinkron, waktu tunggu dapat menyebabkan validator melihat perubahan pada semua pemimpin tanpa keaktifan konsensus.
Di Bullshark, batas waktu digunakan dalam konstruksi DAG untuk memastikan bahwa selama sinkronisasi, pemimpin yang jujur menambahkan jangkar ke DAG dengan cukup cepat agar dapat dipesan.
Kami mengamati bahwa konstruksi DAG menyediakan "jam" untuk memperkirakan kecepatan jaringan. Dengan tidak adanya jeda, putaran terus berlanjut selama validator yang jujur terus menambahkan simpul ke DAG. Meskipun Bullshark mungkin tidak dapat mengurutkan pada kecepatan jaringan (karena pemimpin bermasalah), DAG masih tumbuh pada kecepatan jaringan meskipun beberapa masalah pemimpin atau jaringan tidak sinkron. Akhirnya, ketika seorang pemimpin bebas kesalahan menyiarkan jangkar dengan cukup cepat, seluruh riwayat sebab-akibat jangkar akan tertata.
Dalam evaluasi kami, kami membandingkan Bullshark dengan dan tanpa batas waktu dalam kasus berikut:
Fast leader, artinya paling tidak lebih cepat dari validator lainnya. Dalam hal ini, kedua metode memberikan latensi yang sama karena jangkar diurutkan dan batas waktu tidak digunakan.
Pemimpin palsu, dalam hal ini Bullshark tanpa jeda memberikan latensi yang lebih baik karena validator akan segera melewati jangkarnya, sedangkan validator dengan jeda akan menunggu kedatangannya sebelum melanjutkan Harapkan.
Pemimpin lambat, ini adalah satu-satunya kasus di mana Bullshark memiliki kinerja batas waktu yang lebih baik. Sebab, tanpa jeda, jangkar dapat dilewati karena pemimpin tidak dapat menyiarkannya dengan cukup cepat, sedangkan dengan jeda, validator akan menunggu jangkar.
Di Shoal, menghindari timeout dan reputasi kepemimpinan berjalan beriringan. Berulang kali menunggu pemimpin lambat meningkatkan latensi, dan mekanisme reputasi pemimpin menghalangi validator lambat terpilih sebagai pemimpin. Dengan cara ini, sistem menggunakan node validasi cepat untuk berjalan dengan kecepatan jaringan di semua skenario dunia nyata.
Perhatikan bahwa hasil ketidakmungkinan FLP menunjukkan bahwa tidak ada protokol konsensus deterministik yang dapat menghindari waktu tunggu. Shoal tidak dapat menghindari hasil ini karena ada jadwal teoretis dari peristiwa permusuhan yang akan mencegah semua jangkar diperintahkan. Alih-alih, Shoal jatuh kembali ke batas waktu setelah sejumlah jangkar yang dapat dikonfigurasi dilewati secara berurutan. Dalam praktiknya, ini sangat tidak mungkin terjadi.
Tanggapan Umum
Makalah Hotstuff mempopulerkan konsep respons optimis, yang, meskipun tidak didefinisikan secara formal, secara intuitif berarti bahwa protokol dapat berjalan pada kecepatan jaringan dalam kondisi yang baik termasuk pemimpin yang cepat dan jaringan yang sinkron.
Shoal menyediakan properti yang lebih baik lagi, yang kami sebut Respons Universal. Secara khusus, berbeda dengan Hotstuff, Shoal terus berjalan dengan kecepatan jaringan bahkan jika pemimpin gagal untuk sejumlah putaran berurutan atau siklus asinkron yang dapat dikonfigurasi yang dilalui jaringan. Lihat perbandingan yang lebih rinci dalam tabel di bawah ini.
Perhatikan bahwa daya tanggap universal memberikan jaminan kemajuan yang lebih baik selama periode asinkron dan ketika pemimpin gagal. Selama sinkronisasi dengan slow leader, properti ini tidak sebanding karena bergantung pada seberapa lambat leader tersebut. Namun, mengingat reputasi pemimpinnya, pemimpin yang bergerak lambat seharusnya jarang muncul di Shoal.
Evaluasi
Kami menerapkan Bullshark dan Shoal di atas Toko Kuorum implementasi Narwhal kami. Perbandingan mendetail antara Shoal, Bullshark, dan Jolteon dapat ditemukan di bagian evaluasi makalah Shoal, di mana kami memberikan beberapa sorotan.
Pertama, untuk mendemonstrasikan kekuatan konstruksi DAG asinkron, kami membandingkan Bullshark dengan dan tanpa jeda. Makalah Bullshark lengkap mengasumsikan jaringan asinkron, tetapi menyediakan mode jalur cepat, sehingga membutuhkan jeda selama semua putaran. Kami menyebut versi ini Vanilla Bullshark. Kami mengamati bahwa untuk versi hipotetis jaringan sinkron sebagian independen, tidak diperlukan jeda dalam putaran pemungutan suara. Kami menyebut versi ini Vanilla Bullshark tanpa batas waktu Vote tanpa batas waktu pemungutan suara, Baseline Bullshark adalah versi tanpa batas waktu.
Grafik di bawah membandingkan dampak waktu tunggu pada latensi Bullshark dengan dan tanpa kegagalan. Tampaknya, Baseline Bullshark (tanpa batas waktu) bekerja paling baik jika terjadi kegagalan. Tanpa kegagalan, Baseline Bullshark sebanding dengan Vanilla Bullshark tanpa penangguhan pemungutan suara. Hal ini karena, seperti yang disebutkan sebelumnya, tanpa mekanisme reputasi pemimpin, timeout mungkin menguntungkan dalam situasi di mana pemimpinnya baik tetapi lamban.
Gambar 6.: Dampak waktu tunggu pada latensi Bullshark tanpa kegagalan (kiri) dan dengan kegagalan (kanan), dengan 50 validator dalam kasus kegagalan
Selanjutnya, kami membuat instance Shoal menggunakan Baseline Bullshark (tanpa batas waktu) dan mendemonstrasikan peningkatan latensi pipelining dan mekanisme reputasi pemimpin dengan dan tanpa kegagalan, dan untuk kelengkapan kami juga membandingkannya dengan Jolteon dengan dan tanpa perbandingan kegagalan.
Gambar 7 di bawah menunjukkan kasus tanpa kegagalan, dan meskipun pipeline dan reputasi pemimpin dapat mengurangi latensi satu per satu, menggabungkan keduanya akan menghasilkan latensi terbaik.
Adapun Jolteon, itu tidak dapat menskalakan ke lebih dari 20 validator, dan bahkan jika berjalan di Quorum Store, itu hanya dapat mencapai sekitar setengah dari throughput Bullshark/Shoal, yang menghilangkan hambatan propagasi data.
Hasilnya menunjukkan bahwa Shoal sangat meningkatkan latensi Bullshark. Adapun Jolteon, penting untuk dicatat bahwa meskipun kami hanya mengukur latensi konsensus. Karena Jolteon tidak dapat berjalan secara native di atas DAG, diperlukan latensi tambahan untuk memisahkan propagasi data, yang tidak kami ukur. Oleh karena itu, di bawah beban tinggi, Shoal harus sesuai dengan latensi end-to-end Jolteon.
Gambar 7: Throughput dan latensi tanpa kegagalan, Shoal PL dan Shaol LR masing-masing hanya mendukung perpipaan dan reputasi pemimpin.
Gambar 8 di bawah menunjukkan kasus kegagalan dengan 50 validator, di mana mekanisme reputasi pemimpin meningkatkan latensi secara signifikan dengan mengurangi kemungkinan validator yang gagal terpilih sebagai pemimpin. Perhatikan bahwa dengan 16 kegagalan dari 50, latensi Shoal 65% lebih rendah daripada Baseline Bullshark.
Lihat Asli
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
4D Shoal Framework Dijelaskan: Bagaimana Cara Mengurangi Latensi Bullshark di Aptos?
Asli: Lab Aptos
Kompilasi: Aptos Global
Ringkasan
Laboratorium Aptos telah memecahkan dua masalah terbuka yang penting di DAG BFT, sangat mengurangi latensi, dan untuk pertama kalinya menghilangkan kebutuhan akan jeda dalam protokol praktis deterministik. Secara keseluruhan, ini meningkatkan latensi Bullshark sebesar 40% dalam kasus tanpa kegagalan dan 80% dalam kasus kesalahan.
Shoal adalah kerangka kerja yang meningkatkan protokol konsensus berbasis Narwhal (misalnya, DAG-Rider, Tusk, Bullshark) melalui perpipaan dan reputasi pemimpin. Pipelining mengurangi latensi pengurutan DAG dengan memperkenalkan jangkar per putaran, dan reputasi pemimpin semakin meningkatkan latensi dengan memastikan bahwa jangkar dikaitkan dengan validator tercepat. Selain itu, reputasi pemimpin memungkinkan Shoal memanfaatkan konstruksi DAG asinkron untuk menghilangkan waktu tunggu di semua skenario. Ini memungkinkan Shoal untuk menyediakan properti yang kami beri nama Respons Universal, yang berisi Respons Optimis yang biasanya diperlukan.
Teknik kami sangat sederhana, melibatkan menjalankan beberapa contoh dari protokol yang mendasari secara berurutan satu demi satu. Jadi, saat dipakai dengan Bullshark, kita mendapatkan sekelompok "hiu" yang sedang melakukan lari estafet.
Motivasi
Dalam mengejar kinerja tinggi dalam jaringan blockchain, selalu ada fokus untuk mengurangi kompleksitas komunikasi. Namun, pendekatan ini tidak menghasilkan peningkatan throughput yang signifikan. Misalnya, implementasi Hotstuff di Diem versi awal hanya mencapai 3500 TPS, jauh di bawah tujuan kami untuk mencapai 100k+ TPS.
Namun, terobosan baru-baru ini berasal dari kesadaran bahwa propagasi data adalah hambatan utama dari protokol berbasis pemimpin, dan dapat mengambil manfaat dari paralelisasi. Sistem Narwhal memisahkan propagasi data dari logika konsensus inti dan mengusulkan sebuah arsitektur di mana semua validator menyebarkan data secara bersamaan, sementara komponen konsensus hanya memesan sejumlah kecil metadata. Makalah Narwhal melaporkan throughput 160.000 TPS.
Di artikel sebelumnya, kami memperkenalkan Toko Kuorum. Implementasi Narwhal kami memisahkan propagasi data dari konsensus, dan bagaimana kami menggunakannya untuk memperluas protokol konsensus kami saat ini, Jolteon. Jolteon adalah protokol berbasis pemimpin yang menggabungkan jalur cepat linier Tendermint dengan perubahan tampilan gaya PBFT untuk mengurangi latensi Hotstuff sebesar 33%. Namun, jelas bahwa protokol konsensus berbasis pemimpin tidak dapat sepenuhnya mengeksploitasi potensi throughput Narwhal. Meskipun memisahkan propagasi data dari konsensus, pemimpin Hotstuff/Jolteon masih terbatas karena peningkatan throughput.
Oleh karena itu, kami memutuskan untuk menggunakan Bullshark, sebuah protokol konsensus dengan overhead komunikasi nol, di atas Narwhal DAG. Sayangnya, struktur DAG yang mendukung throughput tinggi Bullshark hadir dengan penalti latensi 50% dibandingkan dengan Jolteon.
Dalam postingan ini, kami menjelaskan bagaimana Shoal mencapai pengurangan dramatis dalam latensi Bullshark.
Latar belakang DAG-BFT
Mari kita mulai dengan memahami latar belakang yang relevan dari artikel ini. Untuk deskripsi mendetail tentang Narwhal dan Bullshark, silakan lihat postingan DAG bertemu BFT.
Setiap simpul dalam DAG Narwhal dikaitkan dengan angka bulat. Untuk masuk ke putaran r, verifikator harus terlebih dahulu mendapatkan simpul nf yang termasuk dalam putaran r-1. Setiap verifier dapat menyiarkan satu simpul per putaran, dan setiap simpul mengacu pada setidaknya nf simpul di putaran sebelumnya. Karena asinkron jaringan, validator yang berbeda dapat mengamati tampilan lokal DAG yang berbeda kapan saja. Berikut adalah ilustrasi kemungkinan tampilan sebagian:
Gambar 1: Sejarah kausal simpul yang diidentifikasi oleh simpul validasi putaran 2 2 disorot dalam warna hijau
Properti utama DAG bukanlah ambiguitas: dua validator memiliki riwayat sebab akibat yang persis sama dari v jika mereka memiliki simpul v yang sama dalam tampilan DAG lokal mereka.
Jumlah Pesanan
Dimungkinkan untuk menyepakati urutan total semua simpul dalam DAG tanpa biaya komunikasi tambahan. Untuk tujuan ini, validator di DAG-Rider, Tusk, dan Bullshark menginterpretasikan struktur DAG sebagai protokol konsensus, di mana simpul mewakili proposal dan ujung mewakili suara.
Meskipun logika persimpangan grup berbeda pada struktur DAG, semua protokol konsensus berbasis Narwhal yang ada memiliki struktur berikut:
Jangkar yang ditentukan sebelumnya, akan ada pemimpin yang ditentukan sebelumnya setiap beberapa putaran (misalnya, dua putaran di Bullshark), dan puncak pemimpin disebut jangkar;
Memesan jangkar, pemverifikasi secara mandiri tetapi secara deterministik memutuskan jangkar mana yang akan dipesan dan jangkar mana yang akan dilewati;
Urutkan sejarah kausal, di mana validator memproses daftar urutan jangkar mereka satu per satu, dan untuk setiap jangkar, urutkan semua simpul yang sebelumnya tidak terurut dalam sejarah kausalnya dengan beberapa aturan deterministik.
Gambar 2: Ilustrasi kemungkinan tampilan parsial DAG dalam protokol Bullshark. Dalam contoh ini, jangkar merah dan kuning diurutkan, sedangkan hijau (bukan di DAG) dilewati. Oleh karena itu, untuk mengurutkan DAG, validator secara deterministik mengurutkan sejarah kausal jangkar merah terlebih dahulu, diikuti oleh jangkar kuning.
Kunci untuk memuaskan keamanan adalah memastikan bahwa pada langkah (2) di atas, semua validator yang jujur membuat daftar jangkar yang terurut sehingga semua daftar memiliki awalan yang sama. Di Shoal, kami melakukan pengamatan berikut untuk semua protokol di atas:
** Semua validator menyetujui jangkar yang dipesan pertama. **
Latensi Bullshark
Latensi Bullshark bergantung pada jumlah putaran antara jangkar yang dipesan di DAG. Meskipun versi Bullshark sebagian sinkron yang paling berguna memiliki latensi yang lebih baik daripada versi asinkron, versi ini jauh dari optimal.
Masalah 1: Latensi blok rata-rata. Di Bullshark, setiap putaran genap memiliki jangkar, dan simpul setiap putaran ganjil ditafsirkan sebagai suara. Biasanya, dibutuhkan dua putaran DAG untuk mengurutkan jangkar, namun, simpul dalam sejarah kausal jangkar memerlukan lebih banyak putaran untuk menunggu jangkar dipesan. Dalam kasus umum, simpul dalam putaran ganjil membutuhkan tiga putaran, sedangkan simpul non-anchor dalam putaran genap membutuhkan empat putaran (lihat Gambar 3).
Gambar 3: Dalam kasus umum, jangkar di putaran i+1 perlu disortir untuk dua putaran. Simpul pada putaran i diurutkan secara bersamaan, sehingga latensinya adalah tiga putaran. Namun, simpul di putaran i+1 harus menunggu jangkar berikutnya diurutkan (yang ada di putaran i+3), sehingga penundaan pengurutannya adalah empat putaran.
Masalah 2: Latensi kasus kegagalan, analisis latensi di atas berlaku untuk kasus tanpa kegagalan, di sisi lain, jika pemimpin putaran gagal menyiarkan jangkar dengan cukup cepat, jangkar tidak dapat dipesan (dan dengan demikian dilewati), jadi Semua simpul yang tidak disortir di putaran sebelumnya harus menunggu jangkar berikutnya diurutkan. Ini dapat secara signifikan mengurangi kinerja jaringan yang direplikasi secara geografis, terutama karena Bullshark menggunakan waktu tunggu menunggu pemimpin.
Kerangka Shoal
Shoal menyelesaikan kedua masalah latensi ini dengan meningkatkan Bullshark (atau protokol BFT berbasis Narwhal lainnya) dengan melakukan pipelining, memungkinkan jangkar di setiap putaran, dan mengurangi latensi semua simpul non-jangkar di DAG menjadi tiga putaran. Shoal juga memperkenalkan mekanisme reputasi pemimpin zero-overhead di DAG, yang mencondongkan pemilihan untuk mendukung pemimpin yang cepat.
tantangan
Dalam konteks protokol DAG, perpipaan dan reputasi pemimpin dianggap sebagai masalah yang sulit karena alasan berikut:
Upaya perpipaan sebelumnya untuk mengubah logika inti Bullshark, tetapi ini tampaknya mustahil
Reputasi Pemimpin, diperkenalkan di DiemBFT dan diformalkan di Carousel, adalah gagasan untuk secara dinamis memilih pemimpin masa depan (jangkar di Bullshark) berdasarkan kinerja validator di masa lalu. Sementara ketidaksepakatan atas identitas pemimpin tidak melanggar keamanan dalam protokol ini, di Bullshark hal itu dapat menyebabkan urutan yang sama sekali berbeda, yang sampai ke inti pertanyaan, yaitu bahwa pemilihan jangkar roda yang dinamis dan deterministik adalah kunci untuk menyelesaikan konsensus yang diperlukan. , sementara validator perlu menyepakati urutan riwayat untuk memilih jangkar di masa mendatang.
Sebagai bukti kesulitan masalah, kami mencatat bahwa implementasi Bullshark, termasuk implementasi saat ini dalam produksi, tidak mendukung fitur ini.
protokol ###
Terlepas dari tantangan yang disebutkan di atas, ternyata solusinya, seperti kata pepatah, ada di balik kesederhanaan.
Di Shoal, kami mengandalkan kemampuan untuk melakukan komputasi lokal pada DAG dan mengimplementasikan kemampuan untuk menyimpan dan menafsirkan kembali informasi dari putaran sebelumnya. Dengan wawasan inti bahwa semua validator setuju pada jangkar yang dipesan pertama, Shoal menyalurkannya dengan menyusun beberapa instance Bullshark secara berurutan sedemikian rupa sehingga (1) jangkar yang dipesan pertama adalah titik peralihan untuk instance, dan (2) Sejarah kausal dari jangkar digunakan untuk menghitung reputasi pemimpin.
Pipanisasi
Mirip dengan Bullshark, validator menyetujui secara apriori tentang jangkar potensial, yaitu, ada pemetaan yang diketahui F: R -> V pemetaan putaran ke pemimpin. Shoal menjalankan instance Bullshark satu demi satu sehingga untuk setiap instance jangkar ditentukan sebelumnya oleh peta F. Setiap instance memerintahkan sebuah jangkar, yang memicu peralihan ke instance berikutnya.
Awalnya, Shoal meluncurkan instance Bullshark pertama di putaran pertama DAG dan menjalankannya hingga jangkar pesanan pertama diidentifikasi, katakanlah di putaran r. Semua validator menyetujui jangkar ini. Oleh karena itu, semua validator dapat menyetujui secara deterministik untuk menginterpretasikan kembali DAG mulai dari putaran r+1. Shoal baru saja memulai instance baru Bullshark pada putaran r+1.
Dalam skenario kasus terbaik, ini memungkinkan Shoal memesan jangkar setiap putaran. Jangkar untuk putaran pertama diurutkan berdasarkan kejadian pertama. Kemudian, Shoal memulai instance baru di babak kedua, yang dengan sendirinya memiliki jangkar yang diurutkan oleh instance, kemudian instance baru lainnya memerintahkan jangkar di babak ketiga, dan proses berlanjut. Silakan lihat ilustrasi di bawah ini:
Gambar 4: Verteks yang sesuai dengan pemimpin yang ditentukan oleh F ditandai dengan mahkota. Contoh pertama Bullshark pertama-tama menginterpretasikan DAG dengan jangkar pada putaran 1, 3, dan 5. Bullshark menentukan jangkar pada putaran 1 (dalam tanda centang hijau mark) adalah yang pertama diurutkan pada contoh pertama. (Perhatikan bahwa dalam kasus umum, jangkar ini dapat dilewati, sementara beberapa jangkar lainnya akan diurutkan terlebih dahulu.) Kemudian, contoh pertama lainnya diabaikan, dan contoh baru Bullshark dimulai dari putaran 2, titik Jangkar ditandai pada putaran 2 dan 4.
Reputasi pemimpin
Peningkatan latensi saat melewatkan jangkar selama penyortiran Bullshark. Dalam hal ini, teknik Pipelining tidak berdaya karena instance baru tidak dapat dimulai sampai instance sebelumnya memesan jangkar. Shoal memastikan bahwa pemimpin yang tepat kemungkinan kecil akan dipilih di masa depan untuk menangani jangkar yang hilang dengan menggunakan mekanisme reputasi untuk memberikan skor kepada setiap validator berdasarkan riwayat aktivitasnya baru-baru ini. Validator yang merespons dan berpartisipasi dalam protokol akan diberi skor tinggi, jika tidak, validator akan diberi skor rendah karena dapat macet, lambat, atau berbahaya.
Idenya adalah untuk secara deterministik menghitung ulang pemetaan F yang telah ditentukan dari putaran ke pemimpin di setiap pembaruan skor, memilih pemimpin dengan skor lebih tinggi. Agar validator menyepakati pemetaan baru, mereka harus menyepakati skor dan dengan demikian sejarah digunakan untuk mendapatkan skor.
Di Shoal, pipelining dan reputasi kepemimpinan dapat digabungkan secara alami karena keduanya menggunakan teknik inti yang sama dalam menafsirkan kembali DAG setelah menyepakati jangkar pesanan pertama.
Nyatanya, satu-satunya perbedaan adalah, setelah menyortir jangkar di putaran r, validator hanya perlu menghitung pemetaan baru F' dari putaran r+1 berdasarkan riwayat kausal dari jangkar yang dipesan di putaran r . Kemudian, validator mengeksekusi instance baru Bullshark mulai dari putaran r+1 menggunakan fungsi pemilihan jangkar yang diperbarui F'. Lihat gambar di bawah ini:
Gambar 5. Simpul yang sesuai dengan pemimpin yang diidentifikasi oleh F ditandai dengan mahkota transparan. Contoh pertama Bullshark memesan jangkar di babak 1, ditandai dengan tanda centang hijau, dan kemudian menghitung pemetaan baru F 'berdasarkan informasi dalam sejarah kausal jangkar. Pemimpin yang ditentukan oleh F' ditandai dengan mahkota berwarna.
Tidak ada lagi batas waktu
Timeout memainkan peran penting dalam semua implementasi BFT deterministik sebagian sinkron berbasis pemimpin. Namun, kerumitan yang mereka perkenalkan meningkatkan jumlah keadaan internal yang perlu dikelola dan diamati, yang memperumit proses debug dan memerlukan lebih banyak teknik pengamatan.
Waktu tunggu juga dapat menambah latensi secara signifikan, karena penting untuk mengonfigurasinya dengan tepat, dan biasanya perlu disesuaikan secara dinamis, karena sangat bergantung pada lingkungan (jaringan). Protokol membayar pemimpin yang salah penalti penundaan waktu tunggu penuh sebelum pindah ke pemimpin berikutnya. Oleh karena itu, pengaturan batas waktu tidak boleh terlalu konservatif, tetapi jika batas waktu terlalu singkat, protokol dapat melewatkan pemimpin yang baik. Misalnya, kami mengamati bahwa di bawah beban tinggi, pemimpin di Jolteon/Hotstuff kewalahan dan waktu tunggu habis sebelum mereka dapat mendorong kemajuan.
Sayangnya, protokol berbasis pemimpin seperti Hotstuff dan Jolteon pada dasarnya memerlukan waktu tunggu untuk memastikan bahwa protokol dapat membuat kemajuan setiap kali pemimpin gagal. Tanpa batas waktu, bahkan pemimpin yang jatuh dapat menghentikan protokol selamanya. Karena ketidakmampuan untuk membedakan antara pemimpin yang salah dan pemimpin yang lambat selama asinkron, waktu tunggu dapat menyebabkan validator melihat perubahan pada semua pemimpin tanpa keaktifan konsensus.
Di Bullshark, batas waktu digunakan dalam konstruksi DAG untuk memastikan bahwa selama sinkronisasi, pemimpin yang jujur menambahkan jangkar ke DAG dengan cukup cepat agar dapat dipesan.
Kami mengamati bahwa konstruksi DAG menyediakan "jam" untuk memperkirakan kecepatan jaringan. Dengan tidak adanya jeda, putaran terus berlanjut selama validator yang jujur terus menambahkan simpul ke DAG. Meskipun Bullshark mungkin tidak dapat mengurutkan pada kecepatan jaringan (karena pemimpin bermasalah), DAG masih tumbuh pada kecepatan jaringan meskipun beberapa masalah pemimpin atau jaringan tidak sinkron. Akhirnya, ketika seorang pemimpin bebas kesalahan menyiarkan jangkar dengan cukup cepat, seluruh riwayat sebab-akibat jangkar akan tertata.
Dalam evaluasi kami, kami membandingkan Bullshark dengan dan tanpa batas waktu dalam kasus berikut:
Fast leader, artinya paling tidak lebih cepat dari validator lainnya. Dalam hal ini, kedua metode memberikan latensi yang sama karena jangkar diurutkan dan batas waktu tidak digunakan.
Pemimpin palsu, dalam hal ini Bullshark tanpa jeda memberikan latensi yang lebih baik karena validator akan segera melewati jangkarnya, sedangkan validator dengan jeda akan menunggu kedatangannya sebelum melanjutkan Harapkan.
Pemimpin lambat, ini adalah satu-satunya kasus di mana Bullshark memiliki kinerja batas waktu yang lebih baik. Sebab, tanpa jeda, jangkar dapat dilewati karena pemimpin tidak dapat menyiarkannya dengan cukup cepat, sedangkan dengan jeda, validator akan menunggu jangkar.
Di Shoal, menghindari timeout dan reputasi kepemimpinan berjalan beriringan. Berulang kali menunggu pemimpin lambat meningkatkan latensi, dan mekanisme reputasi pemimpin menghalangi validator lambat terpilih sebagai pemimpin. Dengan cara ini, sistem menggunakan node validasi cepat untuk berjalan dengan kecepatan jaringan di semua skenario dunia nyata.
Perhatikan bahwa hasil ketidakmungkinan FLP menunjukkan bahwa tidak ada protokol konsensus deterministik yang dapat menghindari waktu tunggu. Shoal tidak dapat menghindari hasil ini karena ada jadwal teoretis dari peristiwa permusuhan yang akan mencegah semua jangkar diperintahkan. Alih-alih, Shoal jatuh kembali ke batas waktu setelah sejumlah jangkar yang dapat dikonfigurasi dilewati secara berurutan. Dalam praktiknya, ini sangat tidak mungkin terjadi.
Tanggapan Umum
Makalah Hotstuff mempopulerkan konsep respons optimis, yang, meskipun tidak didefinisikan secara formal, secara intuitif berarti bahwa protokol dapat berjalan pada kecepatan jaringan dalam kondisi yang baik termasuk pemimpin yang cepat dan jaringan yang sinkron.
Shoal menyediakan properti yang lebih baik lagi, yang kami sebut Respons Universal. Secara khusus, berbeda dengan Hotstuff, Shoal terus berjalan dengan kecepatan jaringan bahkan jika pemimpin gagal untuk sejumlah putaran berurutan atau siklus asinkron yang dapat dikonfigurasi yang dilalui jaringan. Lihat perbandingan yang lebih rinci dalam tabel di bawah ini.
Perhatikan bahwa daya tanggap universal memberikan jaminan kemajuan yang lebih baik selama periode asinkron dan ketika pemimpin gagal. Selama sinkronisasi dengan slow leader, properti ini tidak sebanding karena bergantung pada seberapa lambat leader tersebut. Namun, mengingat reputasi pemimpinnya, pemimpin yang bergerak lambat seharusnya jarang muncul di Shoal.
Evaluasi
Kami menerapkan Bullshark dan Shoal di atas Toko Kuorum implementasi Narwhal kami. Perbandingan mendetail antara Shoal, Bullshark, dan Jolteon dapat ditemukan di bagian evaluasi makalah Shoal, di mana kami memberikan beberapa sorotan.
Pertama, untuk mendemonstrasikan kekuatan konstruksi DAG asinkron, kami membandingkan Bullshark dengan dan tanpa jeda. Makalah Bullshark lengkap mengasumsikan jaringan asinkron, tetapi menyediakan mode jalur cepat, sehingga membutuhkan jeda selama semua putaran. Kami menyebut versi ini Vanilla Bullshark. Kami mengamati bahwa untuk versi hipotetis jaringan sinkron sebagian independen, tidak diperlukan jeda dalam putaran pemungutan suara. Kami menyebut versi ini Vanilla Bullshark tanpa batas waktu Vote tanpa batas waktu pemungutan suara, Baseline Bullshark adalah versi tanpa batas waktu.
Grafik di bawah membandingkan dampak waktu tunggu pada latensi Bullshark dengan dan tanpa kegagalan. Tampaknya, Baseline Bullshark (tanpa batas waktu) bekerja paling baik jika terjadi kegagalan. Tanpa kegagalan, Baseline Bullshark sebanding dengan Vanilla Bullshark tanpa penangguhan pemungutan suara. Hal ini karena, seperti yang disebutkan sebelumnya, tanpa mekanisme reputasi pemimpin, timeout mungkin menguntungkan dalam situasi di mana pemimpinnya baik tetapi lamban.
Gambar 6.: Dampak waktu tunggu pada latensi Bullshark tanpa kegagalan (kiri) dan dengan kegagalan (kanan), dengan 50 validator dalam kasus kegagalan
Selanjutnya, kami membuat instance Shoal menggunakan Baseline Bullshark (tanpa batas waktu) dan mendemonstrasikan peningkatan latensi pipelining dan mekanisme reputasi pemimpin dengan dan tanpa kegagalan, dan untuk kelengkapan kami juga membandingkannya dengan Jolteon dengan dan tanpa perbandingan kegagalan.
Gambar 7 di bawah menunjukkan kasus tanpa kegagalan, dan meskipun pipeline dan reputasi pemimpin dapat mengurangi latensi satu per satu, menggabungkan keduanya akan menghasilkan latensi terbaik.
Adapun Jolteon, itu tidak dapat menskalakan ke lebih dari 20 validator, dan bahkan jika berjalan di Quorum Store, itu hanya dapat mencapai sekitar setengah dari throughput Bullshark/Shoal, yang menghilangkan hambatan propagasi data.
Hasilnya menunjukkan bahwa Shoal sangat meningkatkan latensi Bullshark. Adapun Jolteon, penting untuk dicatat bahwa meskipun kami hanya mengukur latensi konsensus. Karena Jolteon tidak dapat berjalan secara native di atas DAG, diperlukan latensi tambahan untuk memisahkan propagasi data, yang tidak kami ukur. Oleh karena itu, di bawah beban tinggi, Shoal harus sesuai dengan latensi end-to-end Jolteon.
Gambar 7: Throughput dan latensi tanpa kegagalan, Shoal PL dan Shaol LR masing-masing hanya mendukung perpipaan dan reputasi pemimpin.
Gambar 8 di bawah menunjukkan kasus kegagalan dengan 50 validator, di mana mekanisme reputasi pemimpin meningkatkan latensi secara signifikan dengan mengurangi kemungkinan validator yang gagal terpilih sebagai pemimpin. Perhatikan bahwa dengan 16 kegagalan dari 50, latensi Shoal 65% lebih rendah daripada Baseline Bullshark.