Latar belakang dan motivasi

Sebelum kita mulai membahas tentang penyempurnaan MPT, mari kita bahas terlebih dahulu latar belakang dilakukannya penelitian ini.

Saya sedang belajar untuk gelar Ph.D. dan melakukan desain rantai publik. Selain peningkatan konsensus inti dari rantai publik ini: bukti kerja yang berguna, tugas penting lainnya adalah menerapkan sistem kontrak pintar yang kompatibel dengan ETH. Saat ini kami telah mengimplementasikan mesin virtual berdasarkan bytecode Python, mengintegrasikannya ke dalam sistem kontrak blockchain, dan secara mengejutkan membuatnya kompatibel dengan Ethereum RPC. Kami menggunakan Python untuk membuat kontrak pintar yang sesuai dengan standar ERC20 untuk pengujian. Tentu saja, kami perlu menerapkan mekanisme data KV yang dapat membawa puluhan juta pengguna pada tingkat eksekusi kontrak yang lebih rendah (mirip dengan Pemetaan dalam Soliditas, yang mana digunakan untuk menyimpan setiap Jumlah token di bawah akun, mungkin ada ratusan juta akun tersebut).

Selanjutnya, isi karya desain rantai publik secara alami menyentuh konsep-konsep seperti MPT dan trie. Kami mengacu pada desain Ethereum, Threetrees, trie, MPT, dll.

Temukan hambatan

Untungnya, sebelum kami siap menerapkan kontrak pintar untuk memanggil MPT, kami tiba-tiba menjalankan program Benchmark pohon MPT sederhana di server AWS. Setelah mencoba menggunakan Trie dan MPT untuk memasukkan volume data sebesar 100 juta KV, kami sangat terkejut mendapatkan hasil: kinerja pohon MPT sebenarnya sangat rendah.

Menjalankan kode berikut, kami mengamati bahwa: memasukkan 10 juta pasangan nilai kunci KV ke Rocksdb memerlukan waktu beberapa menit untuk Trie dan beberapa jam untuk MPT. Saat kami meningkatkan besaran data pengujian menjadi 100 juta, penyisip MPT memerlukan waktu beberapa hari untuk dijalankan. Ini berarti ketika blockchain menggunakan struktur data MPT untuk menjalankan kontrak pintar, kecepatannya juga akan sangat terbatas.

Eksperimen telah membuktikan bahwa overhead yang disebabkan oleh penggunaan struktur data MPT tidak hanya akan memperlambat kecepatan eksekusi kontrak pintar, namun juga mengurangi kecepatan sinkronisasi node blockchain (bahkan ketika bandwidth sangat mencukupi, mengunduh data dari node lain dan membangun kembali node, Ini juga harus memakan waktu beberapa hari). Namun, karena desain struktur data Ethereum sulit untuk dimodifikasi, meskipun kita menulis ulang atau mengoptimalkannya dengan bahasa pemrograman yang "lebih cepat", jika struktur data yang mendasarinya tidak diperbarui, blockchain akan sulit menembus batasan kinerja.

tes_mpt_write.py

tes_mpt_write.py

Saya masih ingat saat pertama kali belajar menulis kode, guru memberi tahu kami prinsip dasar, program = algoritma + struktur data. Jika kita membatasi struktur data, bahkan jika kita berusaha keras mengoptimalkan algoritme (yang sering kali memerlukan upaya akademis selama beberapa tahun, dan dalam banyak kasus hampir mustahil untuk ditingkatkan), akan sulit untuk menembus batasan kinerja saat ini. struktur data. Jadi rencana perbaikan yang sangat akademis, mencari algoritma penggantian MPT yang berkinerja lebih baik, penelitian mungkin memerlukan waktu beberapa tahun. Sebagai pendahulu yang bekerja dalam arah ini, Verkle Tree menggunakan metode polinomial untuk mengoptimalkan struktur data blockchain. Kami akan mencoba beberapa ide yang lebih unik dan sederhana.

Jika kita menggunakan pemikiran prinsip pertama, apakah kita tidak dapat menggunakan MPT? Jika kita dapat melewati MPT dan mengimplementasikan kontrak pintar langsung di Trie, tidak akan ada lagi overhead yang disebabkan oleh MPT (prinsip pertama Ma Yilong, sesuatu yang tidak ada tidak akan memiliki overhead kinerja).

Dari segi harga, solusi baru kami yang dirancang mungkin tidak secara langsung kompatibel dengan MPT yang ada, namun karena antarmuka Ethereum RPC tidak dimodifikasi, banyak infrastruktur Ethereum yang ada dapat digunakan kembali: seperti Etherjs dan MetaMask. Melewati MPT termasuk dalam optimasi struktur data internal, yang merupakan eksplorasi gratis atas kinerja blockchain.

pengetahuan prasyarat

Rocksdb dan Trie

Pohon kamus Trie adalah struktur data pohon tingkat lanjut yang disebutkan dalam buku teks perguruan tinggi. Dalam video Guru Xiao, MPT dibangun berdasarkan pohon kamus Trie. Kita mungkin berpikir bahwa lingkungan implementasi Trie ada di memori.

Namun, dalam rekayasa kami, kami tidak dapat langsung menggunakan Trie untuk mengimplementasikan produk secara langsung, karena kami juga perlu menyimpan data di hard disk. Langkah ini memerlukan banyak optimasi teknik, jadi kami biasanya mengimplementasikan pohon MPT berdasarkan Rocksdb.

Rocksdb adalah fork open source FB berdasarkan leveldb, dan menggunakan LSMT di bagian bawah (lihat makalah Pohon penggabungan terstruktur log). Dari sudut pandang abstrak, kita dapat menganggap Rocksdb sebagai pohon kamus yang dioptimalkan dan persisten.

Penggunaan dasar Rocksdb sangat sederhana. Ini terutama menggunakan tiga operasi dasar: Dapatkan put dan kueri dengan awalan Iterate.

mesin negara

Mesin negara adalah alat yang sering digunakan oleh orang-orang untuk memodelkan blockchain. Caranya sangat sederhana: tambahkan masukan ke keadaan asli untuk mendapatkan keadaan baru.

Keadaan global Ethereum dapat dipahami sebagai keadaan mesin negara. Misalnya, di blok 1, nilai KV dari semua kontrak pintar adalah keadaan global. Semua transaksi dalam satu blok dieksekusi oleh EVM dan dapat dipahami sebagai mesin negara. Input, seperti panggilan kontrak Mint, menyebabkan variabel Saldo dan Total kontrak pengguna berubah menjadi 1000 di blok 2.

Konsep mesin keadaan yang mudah diabaikan disebut fungsi transisi keadaan, yang mendefinisikan aturan masukan. Jika masukan tidak masuk akal, informasi masukan akan ditolak. Misalnya, ketika kita mencoba mentransfer jumlah negatif ke orang lain, transaksi tersebut tidak akan dieksekusi (tentu saja, kontrak pintar yang bermasalah dapat menerima transaksi tersebut. Di ETH, fungsi transisi status dapat secara otomatis mengeksekusinya melalui Turing -bahasa lengkap.

Pengantar MPT

Mungkin Anda pernah mendengar tentang tiga pohon di Ethereum, yaitu pohon transaksi, pohon status, dan pohon penerimaan. Semuanya adalah pohon MPT yang bernama lengkap Merkle Patricia Tries. Diantaranya, pohon status mungkin merupakan kasus penggunaan terbaik untuk menggunakan struktur data MPT. Untuk detailnya, silakan lihat video penjelasan Guru Xiao.

Pohon MPT didasarkan pada struktur data Trie dan dapat menghitung semua data status menjadi hash root seperti pohon Merkle dan menempatkannya di header blok Ethereum. Ada tiga hash akar pohon MPT di header blok Ethereum, yang biasa kita sebut tiga pohon.

Apakah mungkin untuk tidak menempatkan root dari status global di header blok? Ya, transaksi ditempatkan di blok Bitcoin, dan akar Merkle dari transaksi tersebut dimasukkan ke dalam header blok (pohon Merkle digunakan, tetapi MPT tidak digunakan). Namun Bitcoin tidak memiliki kontrak pintar seperti Ethereum, juga tidak memiliki konsep negara global. Ketika Ethereum awalnya merancang blockchain dengan kontrak pintar, ia meninggalkan desain blok 1 M Bitcoin dan UTXO, memilih struktur data MPT dan model akun, dan menggunakan Gas untuk menyelesaikan masalah waktu henti, memenuhi kebutuhan kontrak pintar selama operasi negara.

Jadi, apa tujuan penggunaan MPT di Ethereum?

  1. Temukan status blockchain yang sesuai melalui akar Merkle di header blok.

  2. Menghemat ruang yang ditempati oleh data duplikat.

  3. Status yang benar dapat diverifikasi melalui hash root.

Poin pertama adalah persyaratan yang ketat. Berbagai status perlu dibaca saat menjalankan EVM. Jika pola desain yang mirip dengan Bitcoin UTXO digunakan, banyak blok yang perlu ditelusuri kembali untuk mendapatkan status saldo akun pengguna tertentu. Menggunakan MPT memenuhi kebutuhan dengan sangat baik.

Poin 2, MPT menghemat ruang, dan status blockchain dapat dianggap sebagai kamus yang sangat besar. Di setiap blok, hanya sebagian kecil kunci yang diperbarui, dan sebagian besar kunci masih mempertahankan nilai aslinya. Dengan menggunakan pohon MPT, Anda hanya dapat memperbarui nilai kunci yang perlu diperbarui, tanpa menyalin status tidak berubah di setiap blok.

Butir 3: Keuntungan MPT adalah verifikasi status global telah selesai menggunakan nilai kunci status yang diakses oleh hash root. Ini juga merupakan alasan utama mengapa penulisan pohon MPT memakan waktu. Jika MPT tidak digunakan, node masih dapat memverifikasi konsistensi data selama sinkronisasi blok.

Dengan menyelesaikan poin 1 dan 2 tanpa menggunakan MPT, kita dapat mem-bypass overhead MPT. Jadi kita perlu merancang solusi berdasarkan Trie (dapat dipahami sebagai Rocksdb) untuk menyimpan data status blockchain.

desain

Kami terutama merancang solusi berbasis Trie untuk menyimpan status on-chain. Menurut prinsip pertama, jika tidak ada struktur data MPT, tidak ada overhead sistem yang diperlukan untuk menjalankan MPT. Selama sistem kontrak pintar berbasis Trie dapat diimplementasikan dan dijalankan dengan benar, berarti optimalisasi telah selesai. Dalam praktiknya, kita dapat menganggap Rocksdb sebagai Trie. Pemahaman yang lebih sederhana adalah bahwa ini adalah database KV berkinerja tinggi.

Gunakan [globalstate as prefix_contract address_variable name_block height_block hash] sebagai nilai kunci database KV, seperti format berikut. Diantaranya, 0x1 adalah alamat kontrak, Total adalah nama variabel, 1 adalah tinggi blok, dan ABC1234 adalah nilai hash blok (akan dihilangkan nanti)

globalstate_0x1_total_1_abc1234

Dalam Ethereum Solidity, variabel dapat didefinisikan sebagai Memori, Penyimpanan, dan Data Panggilan. Kami terutama fokus pada jenis Penyimpanan karena akan disimpan dalam keadaan global. Selain variabel sederhana, kami juga mempertimbangkan Pemetaan. Karena urutan besarnya pengguna di blockchain bersifat global, maka akan ada pemetaan KV yang sangat besar. Selain itu, kami akan memperlakukan tipe data seperti Array sebagai struktur data sederhana dan langsung menyimpannya di Json di Rocksdb. Saat kita membuat kode, secara alami kita harus memperkirakan besarnya data Nilai dalam struktur data KV untuk memilih metode penyimpanan yang sesuai.

Variabel status penyimpanan kontrak

Bagaimana kita bisa mencapai tujuan desain MPT yang pertama dan kedua tanpa menggunakan MPT?

Misalkan kita memiliki variabel Total dalam kontrak ERC20. Variabel ini hanya akan berubah ketika jumlah Token bertambah (Mint) atau berkurang (Burn), namun nilai Total tetap ketika pengguna A mentransfer uang (Transfer) ke pengguna B. konstan.

Demi kesederhanaan, asumsikan alamat kontrak adalah 0x1. Ketika tinggi blok adalah 1, pemilik kontrak melakukan Mint 2000. Pada blok dengan tinggi 2-8, pengguna melakukan beberapa transfer blok saat ini tingginya 9. .

Pada titik ini, kita hanya perlu menanyakan database untuk Kunci yang diawali dengan [globalstate_0x1_total_]. Meskipun blok terakhir kita saat ini adalah 9, karena variabel Total tidak berubah di blok 2-8, hasil pertama dari query di atas adalah nilai [globalstate_0x1_total_1], jadi kita menemukan nilai terbaru dari variabel Total, yaitu Total variabel yang berubah di blok 1.

Pada saat ini, blok baru dibuat. Asumsikan pengguna melakukan Mint dua kali lebih banyak di blok ke-9 dan ke-11. Di sini kita menemukan fitur Rocksdb. Jika kita memiliki Kunci berikut

globalstate_0x1_total_1  : 2000

globalstate_0x1_total_9  : 4000

globalstate_0x1_total_11 : 6000

Maka hasil pencarian pertama akan selalu blok 1, bukan blok 11 yang terbaru. Karena kami belum menemukan parameter untuk mengubah urutan hasil pencarian dari dokumentasi Rocksdb, kami menggunakan sedikit trik, menggunakan angka yang lebih besar seperti 100 untuk mengurangi tinggi blok (sebenarnya akan jauh lebih besar), dan pad itu dengan angka nol, sehingga blok terbaru akan menduduki peringkat pertama pada hasil pencarian.

globalstate_0x1_total_089 : 6000

globalstate_0x1_total_091 : 4000

globalstate_0x1_total_099 : 2000

Jenis Pemetaan Penyimpanan

Seperti yang kami sebutkan sebelumnya, besaran Kunci dari struktur data Pemetaan mungkin sangat besar, sehingga tidak mungkin bagi kami untuk mengubah kamus Json dari puluhan ribu Kunci dalam Pemetaan menjadi sebuah string , atau mengubah Nilai akan sangat menakutkan.

Dengan asumsi alamat pengguna adalah 0x2, kami sedikit memperluas format Kunci penyimpanan sebelumnya:

[globalstate_0x1_[saldo_0x2]_2] : 2000

[Nama variabel] sebelumnya di sini telah diperluas menjadi [nama variabel + Kunci kamus Pemetaan]

Data di atas menunjukkan bahwa saldo Saldo pengguna 0x2 di tinggi blok 2 adalah 2000. Jika tidak ada data yang diperbarui untuk menutupi saldo saat ini, maka data pengguna di blok 2 mewakili status terbaru.

globalstate_0x1_balance_0x2_098 : 2000

globalstate_0x1_total_0x1_099 : 2000

Verifikasi blok

Seperti akar pohon Merkle, akar pohon MPT juga mewakili verifikasi keadaan global. Selama kita dapat memastikan konsistensi data blok, apakah kita harus menggunakan MPT dan menulis Root ke dalam header blok adalah pilihan desain.

Kami telah melakukan beberapa perbaikan pada desain blok, sehingga header blok berisi dua isi, satu adalah blok data transaksi, dan yang lainnya adalah blok data pembaruan status.

Blok data transaksi berisi hash dari semua transaksi. Penambang atau node dapat memulai dari status global dengan ketinggian blok tertentu, mengeksekusi semua transaksi sesuai urutan yang diberikan dalam blok data transaksi, dan memperoleh status global dari blok berikutnya. Jika volume transaksi besar, eksekusi paralel tidak mungkin dilakukan (karena urutan transaksi akan terganggu), sehingga akan lebih memakan waktu jika memerlukan node di seluruh dunia untuk mengeksekusi semua transaksi.

Untuk tujuan ini, kami merancang blok data pembaruan status, yang mencakup nilai kunci status global yang diperbarui setelah menjalankan semua transaksi. Jika merupakan node yang tertinggal banyak blok, selain menjalankan mesin virtual untuk mengeksekusi semua transaksi, juga dapat mengupdate konten Body sesuai status dan langsung memasukkan nilai kunci ke dalam database untuk menghemat daya komputasi. dan mempersingkat waktu sinkronisasi.

Tentu saja, nilai kunci yang digunakan untuk melakukan semua pembaruan transaksi harus sama persis dengan Diff yang terdapat dalam blok pembaruan status, jika tidak, blok baru ini akan ilegal.

Asumsikan ada 10.000 node di dunia. Saat kita melempar dadu dan menetapkan probabilitas 1% untuk mengeksekusi transaksi, sekitar 100 node akan mengeksekusi transaksi lintas blok, dan node lain akan bergantung pada konten pembaruan status koneksi. blok data. Kemudian area ini Banyak node dalam sistem blockchain yang dapat menyimpan banyak operasi berulang.

menyelesaikan

Setelah menyelesaikan desain sebelumnya, kami segera mulai mengimplementasikan ide ini.

Pertama, kami mengintegrasikan VM Python ke dalam sistem blockchain. Ini adalah mesin virtual Python yang diimplementasikan dengan Python, yang saat ini kompatibel dengan bytecode PY 3.10. Kami berharap kontrak pintar dapat menggunakan sebagian sintaksis Python. Misalnya, kami hanya memerlukan fungsi dan tidak ingin pengembang menggunakan Kelas, jadi saat ini kami tidak sepenuhnya mendukung semua bytecode PY.

Mengenai kompiler, Solidity perlu mengembangkan kompiler khusus untuk mengubah kode sumber menjadi bytecode EVM. Dengan menggunakan Python, Anda dapat dengan mudah mengubah kode sumber Python menjadi bytecode PY dengan bantuan bahasa infrastruktur luar biasa ini dengan sejarah tiga puluh tahun. Pengguna tidak akan menyadari waktu kompilasi.

Repositori kode VM kami adalah sebagai berikut. Setiap orang dipersilakan untuk memberikan pendapat Anda dan memperbaiki potensi masalah keamanan:

Tautan: https://github.com/EcoPoW/python_stf_vm Pada langkah kedua, kami mengembangkan ERC20 versi Python, dan kodenya terus diperbarui. Tidak seperti Solidity, kami tidak menggunakan kata kunci untuk mengidentifikasi bagaimana variabel disimpan, semua variabel lokal ada di memori, dan kami menggunakan fungsi global _get dan _put untuk membaca dan menulis status. Tautan: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

https://github.com/EcoPoW/BitPoW/blob/master/state.py

Implementasi dan peningkatan

Kami membutuhkan waktu sekitar dua bulan mulai dari mengajukan pertanyaan, merancang, dan mengimplementasikan pengkodean.

Setelah sepanjang musim panas merancang + pengkodean aktual, sistem kontrak pintar baru, yang hanya menggunakan pohon kamus Trie tanpa bergantung pada struktur data MPT, siap dijalankan (Anda dapat mencoba menjalankan node pengujian secara lokal melalui klon Github). Melewati penyimpanan kontrak pintar berbasis MPT berarti bahwa dengan bandwidth yang memadai, waktu sinkronisasi node berukuran 100 juta KV dapat dikurangi dari beberapa hari menjadi beberapa menit. Efisiensi eksekusi kontrak pintar juga akan menjadi lebih cepat, dan lebih banyak perhitungan yang digunakan oleh CPU akan digunakan untuk mengeksekusi bytecode daripada operasi hash yang diperlukan untuk membangun pohon Merkle. Kami beruntung ketika mengimplementasikan kontrak pintar dalam proyek ini, kami tidak secara langsung mengikuti desain "standar industri". Sebaliknya, kami terlebih dahulu mencoba optimasi dan pengurangan, dan mendapatkan blockchain kontrak pintar dengan "struktur data" yang benar. Karena tidak seperti produk Web2, yang kami bandingkan dengan mengganti ban saat mengendarai mobil, blockchain Web3 lebih seperti peluncuran roket. Sulit untuk melakukan perbaikan struktural besar-besaran pada blockchain yang sedang berjalan, jadi kami hanya dapat meningkatkan sistem “berikutnya” dan bersiap sepenuhnya sebelum online.

Saat ini, jaringan pengujian Testnet 2 dari blockchain BitPoW yang kami rancang telah diterapkan. Setiap orang dapat menggunakan MetaMask untuk terhubung ke blockchain ini melalui RPC untuk pengujian dan mencoba transfer ERC20 berdasarkan VM Python. Pada saat yang sama, kami masih memiliki banyak pekerjaan yang harus diselesaikan, dan kami masih perlu bergantung pada komunitas untuk mempromosikan infrastruktur blockchain baru ini.

Kami menyambut semua orang untuk mempelajari dan benar-benar menguji penerapan teknologi berbasis konsep baru ini, termasuk pengujian kinerja setelah penghapusan MPT, dan pengujian keamanan kontrak pintar baru dan rantai baru.

Meringkaskan

Sejauh ini, kami telah melewati MPT dan merancang solusi penyimpanan kontrak cerdas berdasarkan langsung pada Trie. Saat ini kami menerapkan peningkatan ini pada blockchain berbasis Python vm sebagai bukti kelayakan. Kami membutuhkan waktu sekitar tiga bulan mulai dari menemukan masalah hingga mengusulkan solusi dan mengimplementasikannya dalam kode. Namun hal yang lebih penting dari penelitian ini adalah seperti kebanyakan orang biasa, setelah mempelajari pengetahuan MPT dari kelas, kami Tidak ada pemikiran lebih lanjut yang diberikan kepada kami. memperbaikinya. Solusinya tidak rumit, namun membutuhkan latihan dan tindakan. Solusinya tidak rumit, namun membutuhkan latihan dan tindakan. Hanya dengan berpikir aktif dalam praktik kita dapat menemukan inspirasi dan terus berinovasi. Saya sangat berterima kasih kepada LXDAO karena mendukung penelitian ini, dan saya berharap dapat bertemu lebih banyak teman di komunitas yang tertarik dengan lapisan terbawah dari blockchain. Industri ini masih sangat awal dan infrastrukturnya masih jauh dari matang. Kami berharap dapat mempromosikan mempopulerkan pengetahuan mendasar tentang blockchain sehingga lebih banyak orang dapat berpartisipasi di garis depan inovasi teknologi.