Blockchain Sharding

Halo semuanya, saya adalah salah satu pengembang Near Protocol, yang, antara lain, mengimplementasikan sharding, dan dalam artikel ini saya ingin memberi tahu secara terperinci apa sharding yang ada di blockchain secara umum, cara kerjanya, dan menyentuh sejumlah masalah yang muncul ketika mencoba membangunnya.

Diketahui bahwa Ethereum, platform dApps paling populer, memproses kurang dari 20 transaksi per detik. Karena pembatasan ini, harga transaksi dan waktu untuk mengonfirmasinya sangat tinggi: terlepas dari kenyataan bahwa sebuah blok diterbitkan di Ethereum setiap 10-12 detik sekali, menurut ETH Gas Station, waktu antara pengiriman transaksi dan bagaimana hal itu benar-benar jatuh ke dalam blok adalah rata-rata 1,2. menit. Bandwidth rendah, harga tinggi, dan konfirmasi transaksi panjang tidak memungkinkan untuk meluncurkan layanan berkinerja tinggi di Ethereum.

Alasan utama Ethereum tidak dapat memproses lebih dari 20 transaksi per detik adalah karena setiap node di Ethereum harus memeriksa setiap transaksi. Selama lima tahun sejak rilis Ethereum, banyak ide telah diusulkan untuk menyelesaikan masalah ini. Solusi ini dapat secara kasar dibagi menjadi dua kelompok: solusi yang menawarkan untuk mendelegasikan transaksi ke sekelompok kecil node dengan perangkat keras yang sangat baik, dan solusi yang menawarkan setiap node untuk memproses hanya sebagian dari semua transaksi. Contoh dari pendekatan pertama adalah Guntur , di mana blok dibuat hanya oleh satu simpul, yang memungkinkan, menurut pengembang, untuk menerima 1.200 transaksi per detik, yang 100 kali lebih banyak dari Ethereum. Contoh lain dari kategori pertama adalah Algorand , SpaceMesh , Solana . Semua protokol ini meningkatkan berbagai aspek protokol dan memungkinkan Anda untuk melakukan lebih banyak transaksi daripada di Ethereum, tetapi semua dibatasi oleh kecepatan satu mesin (walaupun sangat kuat).

Pendekatan kedua, di mana setiap node hanya memproses sebagian dari transaksi, disebut Sharding. Ini adalah bagaimana Yayasan Ethereum berencana untuk meningkatkan bandwidth Ethereum.

Dalam posting ini saya akan memberi tahu Anda bagaimana Sharding bekerja di Blockchain menggunakan contoh beberapa protokol yang saat ini sedang dikembangkan.

Pecahan termudah

Dalam implementasi yang paling sederhana, alih-alih mendukung satu blockchain, kami akan mendukung beberapa blockchain, dan kami akan menyebut setiap blockchain tersebut sebagai "beling". Setiap pecahan didukung oleh set node independen yang memverifikasi transaksi dan membuat blok. Selanjutnya, saya akan memanggil validator node tersebut.

Setiap pecahan bertanggung jawab atas sebagian kontrak dan akun. Asumsikan untuk saat ini bahwa transaksi selalu beroperasi hanya dengan kontrak dan akun dalam beling yang sama. Desain yang disederhanakan seperti ini sudah cukup untuk menunjukkan beberapa masalah menarik dan fitur sharding.

Pengangkatan Validator dan Central Blockchain

Masalah pertama dengan fakta bahwa setiap beling memiliki validator sendiri adalah bahwa jika kita memiliki 10 shadras, maka setiap beling sekarang 10 kali lebih tidak dapat diandalkan daripada satu blockchain. Jadi, jika blockchain dengan validator X memutuskan untuk membuat garpu sulit dalam sistem beling dengan 10 pecahan, dan memecah validator X antara 10 beling, sekarang hanya ada validator X / 10 di setiap beling, dan untuk mendapatkan kontrol atas beling memerlukan kontrol lebih dari 5,1% (51). % / 10) validator.

Yang mengarah ke pertanyaan menarik pertama: siapa yang menugaskan validator ke pecahan? Memiliki kendali atas 5,1% validator adalah masalah hanya jika semua 5,1% validator berada dalam beling yang sama. Jika validator sendiri tidak dapat memilih beling mana mereka ditugaskan, mendapatkan kendali atas 5,1% dari validator sebelum mereka ditugaskan ke beling tidak akan memungkinkan mereka untuk mendapatkan kontrol atas beling apa pun.

Hampir semua rancangan pecahan yang ada menggunakan beberapa sumber nomor acak untuk menetapkan validator ke pecahan. Memperoleh angka acak dalam sistem terdistribusi di mana peserta tidak percaya satu sama lain bukanlah masalah yang sepenuhnya diselesaikan hari ini, yang tidak akan kita bahas dalam artikel ini, dan anggap saja kita memiliki sumber angka acak seperti itu.

Baik penerimaan nomor acak dan penunjukan validator adalah perhitungan pada skala sistem yang tidak spesifik untuk pecahan tertentu. Untuk perhitungan seperti itu, desain blockchain shard modern memiliki blockchain khusus khusus yang ada hanya untuk melakukan perhitungan seluruh sistem. Selain nomor acak dan penunjukan validator, perhitungan seperti itu mungkin termasuk mendapatkan hash blok terakhir dari pecahan dan menyimpannya; memproses agunan dalam sistem Bukti-taruhan, dan mempelajari bukti perilaku yang tidak pantas dengan pemilihan agunan yang terkait; menyeimbangkan pecahan, jika fungsi tersebut disediakan. Blockchain semacam itu disebut rantai Beacon di Ethereum 2.0 dan Near Protocol, rantai Relay di PolkaDot, dan Cosmos Hub di Cosmos.

Dalam posting ini kita akan menyebut blockchain tersebut sebagai "central blockchain". Keberadaan blockchain pusat membawa kita ke topik menarik berikutnya - penguapan kuadratik.

Sharding kuadratik

Sharding sering disajikan sebagai solusi yang berskala tak terbatas dengan meningkatnya jumlah node. Mungkin, Anda benar-benar dapat membuat sistem dengan properti ini, tetapi sistem dengan blockchain pusat memiliki batas atas jumlah pecahan, dan akibatnya tidak memiliki skalabilitas yang tak terbatas. Sangat mudah untuk memahami alasannya: blockchain pusat melakukan beberapa perhitungan, seperti menetapkan validator dan mempertahankan status pecahan terbaru, kompleksitasnya sebanding dengan jumlah pecahan. Karena blockchain pusat itu sendiri tidak sharded, dan throughputnya dibatasi oleh throughput dari setiap node, jumlah pecahan yang dapat didukungnya terbatas.

Mari kita lihat bagaimana throughput seluruh sistem berubah jika kekuatan dari node yang mendukungnya meningkat k kali. Setiap pecahan akan dapat memproses k kali lebih banyak transaksi, dan blockchain pusat akan dapat mendukung k kali lebih banyak pecahan. Dengan demikian, throughput seluruh sistem akan bertambah 2 kali lipat. Oleh karena itu nama "sharding kuadratik".

Sulit untuk memprediksi berapa banyak pecahan yang dapat mendukung blockchain pusat hari ini, tetapi kemungkinan besar dalam waktu dekat kami tidak akan mendekati batas transaksi untuk blockchain yang terbelokkan dengan pecahan kuadratik. Kemungkinan besar, kami akan segera berlari ke batas berapa banyak node yang diperlukan untuk mendukung jumlah pecahan tersebut.

Sharding negara

Status adalah semua informasi tentang semua akun dan kontrak. Sejauh ini, kita telah berbicara tentang sharding secara umum, tanpa menentukan apa sebenarnya sharding. Node dalam blockchain melakukan tiga tugas berikut: 1) melakukan transaksi 2) meneruskan transaksi dan memblokir ke node lain dan 3) menyimpan status dan riwayat blockchain. Masing-masing dari ketiga tugas ini dikaitkan dengan beberapa peningkatan beban pada node:

1. Kebutuhan untuk melakukan transaksi membutuhkan daya komputasi yang lebih besar dengan peningkatan jumlah transaksi;
2. Kebutuhan untuk meneruskan transaksi memerlukan lebih banyak bandwidth jaringan seiring bertumbuhnya transaksi;
3. Kebutuhan untuk mempertahankan status dan riwayat memerlukan lebih banyak ruang disk saat ukuran status dan / atau sejarah meningkat. Penting untuk dicatat bahwa, tidak seperti dua poin pertama, jumlah ruang disk yang diperlukan tumbuh bahkan jika jumlah transaksi per unit waktu tidak berubah.

Dari daftar di atas, mungkin tampak bahwa ruang disk adalah masalah terbesar, karena hanya ruang disk tumbuh bahkan jika jumlah transaksi tidak bertambah, tetapi dalam praktiknya tidak. Saat ini, keadaan Ethereum menempati sekitar 100GB, yang dapat dengan mudah disimpan pada mesin modern mana pun, tetapi jumlah transaksi yang dapat diproses oleh Ethereum terbatas hingga beberapa puluh per detik, bergantung pada daya komputasi dan jaringan.

Zilliqa adalah proyek paling terkenal yang memanfaatkan komputasi dan jaringan tetapi tidak menyatakannya. Komputasi sharding lebih sederhana daripada keadaan sharding, karena semua node memiliki semua status, dan masih dapat dengan mudah menjalankan kontrak yang menyebabkan kontrak lain, atau memengaruhi akun pada pecahan yang berbeda. Dalam aspek-aspek ini, desain Zilliqa terlalu disederhanakan, kritik terhadap desain dalam bahasa Inggris dapat dibaca di sini .

Sementara negara sharding tanpa perhitungan shading diusulkan, saya tidak tahu ada proyek yang benar-benar melakukan ini, jadi kami akan menganggap bahwa negara sharding menyiratkan perhitungan sharding.

Dalam praktiknya, fakta bahwa negara terbelenggu dalam beberapa cara mengisolasi pecahan, memungkinkan mereka untuk menjadi blockchain independen, seperti yang kita definisikan di atas. Validator di pecahan hanya menyimpan negara yang khusus untuk beling mereka, dan hanya transaksi yang mempengaruhi keadaan ini yang dieksekusi dan diteruskan. Ini mengurangi beban pada prosesor, disk dan jaringan secara linear dengan jumlah pecahan, tetapi membawa masalah baru, seperti transaksi antar-pecahan.

Transaksi antar-beling

Sejauh ini, kami telah melihat pecahan sebagai blockchains independen dalam hal bagaimana mereka melakukan transaksi. Dengan desain ini, misalnya, tidak mungkin untuk menyelesaikan transaksi yang mentransfer uang antara dua akun di dua pecahan yang berbeda, atau menyebabkan kontak pada satu beling dari kontrak pada yang lain. Saya ingin mendukung kedua skenario.

Untuk kesederhanaan, kami hanya akan mempertimbangkan transaksi yang mentransfer uang, dan kami akan menganggap bahwa setiap peserta memiliki akun tepat pada satu beling. Jika peserta pada beberapa pecahan ingin mentransfer uang ke peserta pada pecahan yang sama, validator pecahan ini dapat memproses transaksi ini dan menerapkannya kepada negara. Tetapi jika, misalnya, Alice memiliki akun di shard # 1 dan dia ingin mengirim uang ke Bob dengan akun di shard # 2, tidak ada validator shard # 1 (yang tidak dapat menambahkan uang ke Bob) atau validator shard # 2 (yang tidak dapat mengambil uang Alice ) tidak dapat menyelesaikan transaksi dan memperbarui status.

Ada dua kelompok besar pendekatan untuk memecahkan masalah ini:

1. Sinkron : untuk setiap transaksi yang melibatkan beberapa pecahan, blok dalam pecahan yang berisi pembaruan keadaan untuk transaksi ini diproduksi secara bersamaan, dan validator dalam pecahan ini bekerja bersama untuk membuat blok tersebut. Desain yang paling rumit dari pendekatan ini, yang saya kenal, adalah Merge Blocks, yang dijelaskan (dalam bahasa Inggris) di sini .

   
   

2. Asynchronous : transaksi antar-beling dilakukan dalam pecahan yang memengaruhi, asynchronous: bagian dari transaksi yang menambahkan uang ke Bob dieksekusi di beling # 2 ketika validator di beling memiliki beberapa bukti bahwa bagian dari transaksi yang mengurangi uang dari Alice dieksekusi di beling # 1. Pendekatan ini lebih populer dalam sistem yang dikembangkan saat ini karena fakta bahwa itu tidak memerlukan sinkronisasi tambahan antara pecahan untuk produksi blok. Sistem seperti ini ditawarkan hari ini di Cosmos, Ethereum Serenity, Near Protocol, Kadena, dan lainnya. Masalah dengan pendekatan ini adalah bahwa jika blok diproduksi secara independen, ada kemungkinan bahwa salah satu blok yang berisi pembaruan negara untuk transaksi tidak akan berada dalam rantai kanonik di belingnya, dan dengan demikian transaksi hanya akan diselesaikan sebagian. Sebagai contoh, perhatikan gambar di bawah ini. Ini menunjukkan dua pecahan di mana garpu terjadi, dan transaksi antar-beling, pembaruan negara yang tercermin dalam blok A dan X ', masing-masing. Jika rantai AB dan V'-X'-Y'-Z 'berubah menjadi kanonik di pecahannya, maka transaksi sepenuhnya diselesaikan. Jika rantai A'-B'-C'-D 'dan VX adalah kanonik, maka transaksi sepenuhnya dibatalkan, yang dapat diterima. Tetapi jika, misalnya, AB dan VX menjadi kanonik, maka satu bagian dari transaksi diselesaikan, dan yang lainnya dibatalkan, dan transaksi tersebut sebagian selesai.

   
   

Skenario yang dijelaskan di atas adalah salah satu masalah besar dalam sharding, di mana semua solusi yang diusulkan tidak optimal. Kami akan menyentuhnya sedikit di bawah.

Perilaku buruk

Sekarang setelah kami mengetahui cara kerja blockard chard dan mempelajari konsep blockchain sentral, penunjukan validator, dan transaksi antar-beling, pada akhir artikel ini kita akan melihat topik menarik lainnya: apa yang dapat dilakukan oleh peserta yang mencoba menyerang sistem jika ia berhasil mendapatkan kontrol atas sejumlah besar validator dalam satu beling.

Garpu Bertarget

Jika peserta memiliki kontrol yang cukup terhadap beling, ia dapat dengan sengaja membuat garpu. Untuk membuat garpu, tidak masalah apa konsensus yang digunakan dalam pecahan, khususnya, tidak masalah apakah itu BFT atau tidak, jika sejumlah validator dikontrol oleh penyerang, ia dapat membuat garpu. Misalnya, tujuan garpu mungkin untuk memutar kembali transaksi yang membayar sesuatu di luar blockchain.

Dikatakan bahwa mendapatkan kontrol 50% dari beling lebih mudah daripada 50% dari seluruh jaringan (misalnya, karena seorang peserta dapat mencoba untuk meretas atau menyuap validator setelah mereka ditugaskan ke beling). Menurut definisi, transaksi antar-beling mengubah keadaan di beberapa pecahan. Perubahan tersebut akan jatuh ke beberapa blok di blockchains dari pecahan yang sesuai. Diperlukan agar semua blok tersebut difinalisasi (mis., Milik rantai kanonik di pecahannya masing-masing), atau semua tidak boleh difinalisasi (mis., Tidak termasuk dalam rantai kanonik dalam pecahannya). Karena kami menganggap bahwa beberapa peserta dengan niat buruk dapat, pada prinsipnya, mendapatkan kontrol atas beling, kami tidak dapat berasumsi bahwa garpu tidak akan terjadi bahkan jika konsensus Bizantium tercapai, atau sejumlah besar blok dibangun di atas blok dengan transaksi.

Masalah ini memiliki banyak solusi, yang paling sederhana adalah kadang-kadang untuk menyimpan hash dari blok terakhir di beling ke blockchain pusat. Algoritme pemilihan rantai kanonik dalam pecahan kemudian diubah sehingga tidak ada target yang berisi blok terakhir yang disimpan di kanonik blockchain pusat. Kemudian, untuk benar-benar menghindari situasi ketika transaksi sebagian diselesaikan karena fakta bahwa beberapa blok yang berisi pembaruan keadaan ternyata berada di luar rantai kanonik, Anda dapat mengubah algoritma untuk melakukan transaksi antar-beling sehingga pecahan A tidak menerima bukti transaksi di beling B sampai blok mengandung pembaruan negara untuk transaksi dalam pecahan B tidak disimpan di blockchain pusat.

Membuat blok tidak valid

Jika peserta dapat memperoleh kontrol atas sejumlah besar validator di beling, ia dapat mencoba membuat blok yang benar-benar tidak valid. Misalnya, anggap bahwa sebelum blok, negara adalah sedemikian rupa sehingga Alice memiliki 10 token, dan di Bob - 0, blok hanya berisi satu transaksi, yang mengirim 10 token dari akun Alice ke akun Bob, tetapi di negara baru itu mencerminkan 0 token dari Alice, dan 1000 dengan Bob.

Dalam blockchain klasik, non-sharded, membuat blok seperti itu tidak mungkin, karena semua peserta, seperti mereka yang membuat blok dan mereka yang hanya menggunakan blockchain, periksa semua blok dan segera buang semua blok yang mengandung kesalahan tersebut. Bahkan jika validator yang dikendalikan oleh penyerang dapat membangun rantai lebih cepat, ini tidak akan memungkinkan mereka untuk melewati rantai yang lebih panjang berisi blok yang tidak valid sebagai yang kanonik, karena semua peserta jaringan akan segera membuang blok yang tidak valid, dan setiap blok yang dibangun di atas. Validator yang jujur ​​akan terus membangun di atas blok valid terakhir, dan semua peserta jaringan akan melihat rantai mereka sebagai kanonik.

Gambar di atas menunjukkan lima validator, tiga di antaranya berada di bawah kendali penyerang. Mereka menciptakan blok A 'yang tidak valid, dan kemudian melanjutkan untuk membangun rantai di atas. Dua validator pribadi segera membuang blok A 'sebagai tidak sah dan terus membangun di atas blok valid terakhir yang mereka tahu, sehingga membuat garpu. Karena ada lebih sedikit validator dalam rantai yang jujur ​​daripada yang tidak jujur, rantai mereka lebih pendek. Namun, di blockchain unsharded klasik, semua peserta dalam sistem memvalidasi semua blok yang mereka lihat. Dengan demikian, setiap peserta yang menggunakan blockchain akan melihat bahwa A 'tidak valid, buang itu, dan karena itu buang B', C 'dan D' seperti yang dibangun di atas blok yang tidak valid, dan dengan demikian semua peserta akan melihat AB sebagai rantai kanonik.

Dalam desain beling, tidak ada peserta yang dapat memvalidasi semua blok di semua blockchain. - , , , - .

, , . , , ( ).

, :

1. - . , 2/3 . , , , . , , , - , . , .
2. - , , , , , . , zk-SNARKs ( zk, zero-knowledge, , non-zk SNARKs). , zk-SNARKs , .

, , , , . — .

Saya banyak menulis tentang blockchain dan sharding dalam bahasa Inggris. Kami juga secara berkala mewawancarai penulis protokol lain seperti Cosmos dan Solana, menggali lebih dalam rincian teknis. Jika Anda tertarik dengan topik ini, Anda dapat mengikuti posting dan video baru dengan berlangganan ke Twitter saya @AlexSkidanov .