Apa yang Anda perlukan:
- latar belakang ilmu komputer
- dasar-dasar Ethereum
- dasar-dasar kalkulus (kendala optimasi)
Apa yang akan Anda dapatkan:
- dasar-dasar SNARK tanpa pengetahuan
- dasar-dasar pohon Merkle
- bagaimana Ethereum dapat menskalakan hingga ribuan transaksi per detik berkat SNARKs
SNARK memungkinkan Prover untuk membuktikan kepada Verifier bahwa dia memiliki solusi W untuk masalah F dengan input X yang dibagikan / diketahui, tanpa mengungkapkan W.
Menemukan solusi untuk masalah ini mungkin memerlukan sejumlah besar daya komputasi dan memori.
Jadi Verifier pada dasarnya dapat 100% yakin bahwa Prover telah berfungsi dengan baik (dan menemukan solusi), dengan tidak melakukan kembali pekerjaan sendiri untuk memeriksa solusinya atau mengetahui solusinya sama sekali. Itu ajaib!
Prosesnya memiliki 3 langkah:
- SETUP - Masalah F (yang perlu dinyatakan sebagai program aritmatika kuadrat, lihat di bawah) disiapkan untuk SNARKs. Proses ini adalah memori yang sangat tinggi dan komputasi intensif tergantung pada kompleksitas masalah (→ Jumlah input dan kendala → Dimensi matriks masalah kepuasan kendala). Pemain yang melakukan Pengaturan (bisa menjadi Verifier itu sendiri) harus dipercaya oleh semua pihak, karena output dari Pengaturan digunakan pada fase berikutnya. Pengaturan biasanya dilakukan menggunakan libsnark, pustaka C ++ yang merupakan implementasi paling populer untuk zkSNARKs.
- MENYEDIAKAN - The Prover, yang memiliki solusi W untuk masalah F dengan input bersama X (mungkin dia menghabiskan banyak CPU dan memori untuk menemukannya!), Menggunakan libsnark dan output dari Pengaturan fase untuk membuat bukti 𝚷. Proses ini pasti membutuhkan banyak memori dan komputasi (tergantung pada kompleksitas masalahnya, seperti di atas). Ukuran output (yaitu bukti 𝚷) bukannya ringkas dan konstan terlepas dari kerumitan masalah. Prover perlu memercayai siapa yang telah melakukan fase Pengaturan, karena dia menggunakan outputnya ...
- MEMVERIFIKASI - Sebuah Verifier - memberikan sebagai input output dari fase Setup, input bersama X dan bukti 𝚷 - memeriksa buktinya. Jika verifikasi berhasil, Prover berhasil membuktikan kepada Verifier bahwa dia telah menemukan solusi W untuk masalah F ... tanpa mengungkapkan W! Bagian yang menyenangkan adalah bahwa tidak hanya Bukti yang ringkas dan selalu panjang .., proses verifikasi cepat dan tidak intensif memori / komputasi sama sekali. Berbeda dengan dua fase sebelumnya ... verifikasi dapat dengan mudah dilakukan dengan smartphone dalam milidetik!
Rekap yang baik (sumber):
Bagaimana ini bisa terjadi? Yah, itu sihir Merlin! Jika Anda ingin mendapatkan matematika di balik ini, mulai dari sini.
Bagaimana saya bisa mengubah perangkat lunak saya menjadi program aritmatika kuadratik?
Seperti disebutkan di atas, masalah tahap Penyiapan F harus berupa program aritmatika kuadratik. Aturan mainnya sulit:
- Input perangkat lunak Anda harus berupa angka. Ubah barang-barang Anda (array, string, dll) menjadi angka. Itu sepele.
- "Sistem persamaan kuadratik dibatasi" berarti:
di mana x adalah vektor n-dimensi dari input Anda, m adalah jumlah kendala (yaitu jumlah persamaan sistem Anda), C adalah koefisien n-by-n Matriks dan q adalah vektor koefisien n-dimensi. Jika Anda tidak menyukai matriks dan vektor, berikut adalah n = 3 dan m = 2 case (3 input, 2 kendala):
- Implementasinya adalah rangkaian aritmatika, yang artinya hasilnya Masalah dipecahkan (sistem diselesaikan, yaitu semua polinomial sama dengan 0) atau Masalah tidak terpecahkan (semua kasus lainnya). Dengan kata lain: "input ini adalah / bukan salah satu solusi untuk Masalah ini".
- Koefisien C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 adalah kendala sistem. Inilah yang pada dasarnya mendefinisikan perangkat lunak Anda. Ubah mereka ... dan Anda akan mendapatkan perangkat lunak lain! Kembali ke cara kerja SNARK: C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 adalah input dari fase Pengaturan. Oleh karena itu, output dari fase Penyetelan (yang Anda perlukan untuk Pembuktian dan Verifikasi) sangat terkait dengan C₁, C₂,…, C𝚖, q₁, q₂, q₂,…, q𝚖 dan hanya berfungsi untuk Masalah itu. Jika Anda mengubahnya, Anda mendefinisikan perangkat lunak / masalah lain dan Anda perlu menjalankan kembali tahap Pengaturan! x₁, x₂, ..., x𝗇 adalah variabel (yaitu apa yang Anda harus tebak untuk mendapatkan solusi sistem). Jadi ketika kita mengatakan "Prover yang terhormat, dapatkah Anda menemukan solusi rahasia W untuk masalah F dengan input bersama / publik X" yang kami maksudkan misalnya "Prover yang terhormat, dapatkah Anda menemukan nilai x₁, x₂, ..., x𝗇 yang menyelesaikan sistem dengan, misalnya, x₇ = 2393, x₅₂₆ = 5647? ” Anda dapat melakukan apa yang Anda inginkan dengan semua x𝗇, kecuali untuk x₇ dan x₅₂₆, yang dibatasi pada input bersama / publik.
Ini adalah kehidupan yang sulit tetapi Anda dapat bertahan hidup ... Jika Anda membutuhkan loop Anda dapat membuka lipatannya mengulangi operasi yang sama berkali-kali. Atau jika Anda perlu misalnya x₁⁴ x₂⁵, Anda menentukan input baru x₃ = x₁⁴ x₂⁵ dan menggunakan x₃ dalam batasan Anda. Ini semua tentang menambahkan variabel dan batasan ... Bahkan untuk perangkat lunak yang cukup sederhana, mudah untuk mencapai ratusan juta atau milyaran input dan kendala!
Ingin tahu lebih banyak? Baca di sini. Dan lihat juga dasar ini kode_to_r1cs.py dari ethereum / penelitian.
Apa itu pohon Merkle?
Fungsi hash adalah aturan yang memetakan input ukuran sewenang-wenang ke output ukuran tetap. Kita bisa menciptakan fungsi hash yang sangat tidak berguna "Menggabungkan dua yang pertama dengan dua huruf terakhir" yang mengubah "Woody Allen" menjadi "Woen" dan "Paul McCartney" menjadi "Paey".
Pohon Merkle adalah struktur data di mana setiap orang tua adalah hash dari dua putranya. Di bagian atas Anda menemukan Root, yang merupakan hash dari dua putra level 1. Di bagian bawah, setiap daun adalah hash dari input eksternal.
Menggunakan fictionary kami "Woody Allen" → "Fungsi hash" Woen:
Ketika daun berubah, modifikasi disebarkan ke Root. Jika ANTHONY berubah, juga ANNY (daun), CENY dan CECO (Root) berubah. Apapun daun yang berubah, Root juga berubah.
Anda tidak perlu seluruh pohon untuk menghitung ulang Root. Dalam contoh kami, jika ANTHONY berubah dan Anda tahu JACO dan CECILY, Anda dapat dengan mudah menghitung ulang Root meskipun Anda benar-benar mengabaikan JAMES, MARCO, JAES, dan MACO. Untuk pohon besar ini menghemat banyak waktu!
Jadi apa?
Pohon merkle sangat bagus untuk pemeriksaan integritas data. Biasanya: Anda tahu yang merupakan Root yang valid, dan Anda memeriksa bahwa data yang diterima cocok dengan Root itu. Misalnya: pihak tepercaya yang tidak bisa memberi Anda seluruh kumpulan data nama depan orang-orang di Bumi (tidak ada waktu, tidak ada bandwidth atau mungkin dia tidak memiliki data sama sekali) memberi Anda hanya Root (mis. "CECO"). Kata penutup: Anda menerima jutaan nama depan, dengan mengacu pada nomor daun, oleh ribuan pihak yang tidak dipercaya. Nah, karena Anda memiliki Root yang benar, Anda dapat memeriksa siapa yang dapat Anda andalkan, siapa yang memberi Anda data palsu ...
Pohon merkle juga bagian dari hidup Anda! Saat Anda mengunduh file Torrent 3GB, file Anda dibagi dalam jutaan potongan kecil. Hash setiap potongan disimpan dalam daun. Karena Anda tahu yang merupakan Root pohon yang valid, setiap kali Anda menerima sepotong file oleh seseorang, Anda dapat memeriksa apakah itu benar. Jika tidak, Anda dapat meminta potongan yang sama kepada orang lain.
Anda dapat melakukannya bahkan jika Anda belum mengunduh seluruh pohon / semua daun: jika Anda tahu bahwa Root adalah CECO dan Anda mempercayai JACO ... ketika Anda menerima bungkusan ANTHONY Anda dapat memverifikasinya bahkan jika Anda belum mengunduh namun potongan MARCO dan JAMES.
Mengapa pohon Merkle berguna dalam teknologi buku besar terdistribusi sangat mudah: Anda menggunakan protokol konsensus (lambat, mahal) hanya untuk mencapai konsensus pada Root. Kemudian node jaringan yang tidak dipercaya dapat secara efisien dan langsung berbagi data ... dan dapat tidur dengan aman dan sehat berkat pemeriksaan integritas dengan Root.
Ketika Tuhan meminta Ethereum untuk memilih 2 negara adidaya di antara Keamanan, Skalabilitas dan Desentralisasi ... Ethereum mengorbankan Skalabilitas. Sebenarnya tidak ada batasan yang kuat pada "transaksi per detik": batas tersebut menyangkut jumlah gas dari setiap blok - yang, menyederhanakan, jumlah operasi yang dapat saya lakukan di setiap blok. Batas ini adalah 8 juta gas. Itu bisa berarti banyak transaksi "kecil" (tidak ada data yang melekat pada transaksi, tidak ada operasi yang dijalankan pada data itu) atau beberapa transaksi besar. Terserah node Ethereum, yang mengirimkan transaksi, dan kepada penambang Ethereum, yang termasuk dalam blok transaksi yang membayar lebih.
Sebuah blok ditambang setiap ~ 15 detik. Itu berarti ~ 32 juta gas per menit, yang jelas tidak cukup jika kita ingin aplikasi Ethereum menjadi arus utama.
Ngomong-ngomong: berhenti dengan perbandingan membosankan antara Ethereum dan Visa. Sistem terpusat akan selalu lebih cepat dari Ethereum ... dengan desain! Mereka melakukan hal yang berbeda dan Anda membutuhkannya dalam situasi yang berbeda. Jika Anda tidak membutuhkan desentralisasi dan lingkungan tanpa kepercayaan ... tentu saja Anda harus memilih Visa. Pendeknya: fakta bahwa blender Anda berputar lebih cepat dari mesin cuci Anda tidak berarti Anda akan membersihkan celana Anda dalam blender!
Mari kita menyusun puzzle! Bayangkan Anda bisa "memampatkan" banyak transaksi kecil dalam satu transaksi besar berkat SNARKs. Jika gas yang dikeluarkan oleh transaksi besar ini kurang dari jumlah gas yang dikeluarkan oleh transaksi kecil, itu berarti Anda menghemat gas.
Dan menghemat gas berarti:
- Pengguna menghabiskan lebih sedikit untuk transaksi secara keseluruhan → Ini akan menjadi dorongan untuk seluruh ekosistem
- Mampu menaruh lebih banyak barang di blok → Ethereum berputar lebih cepat dari blender Anda!
Bagaimana cara kerjanya?
Ada pengguna, relayer (atau lebih banyak relayer) yang mengagregasi transaksi dan kontrak pintar.
- Pengguna yang mau memainkan game ini mengirimkan Ether (atau token) mereka ke kontrak pintar yang diaudit secara publik. Untuk setiap pemain baru, daun baru di pohon Merkle dibuat. Leaf mencakup informasi tentang pemilik Ether (alamatnya, yang juga merupakan kunci publik), jumlah Ether dan nonce (penghitung transaksi dari akun itu, yaitu 0 ketika daun ditambahkan)
- Ketika A ingin mengirim Eter ke B (keduanya harus memiliki daun / akun dalam kontrak pintar), A mengemas transaksi, yang mencakup alamat dariakun, akun untuk akun, akun duta paus dari dari akun, jumlah Eter yang akan ditransfer dan tanda tangan transaksi (ditandatangani dengan kunci pribadi dari akun "dari", jelas). Dia kemudian mengirim transaksi yang sudah dikemas ke relayer.
- Relayer mengumpulkan semua transaksi yang diterima dalam rentang waktu tertentu (misalnya satu jam), memperbarui pohon Merkle dengan jumlah saldo baru dan menciptakan bukti SNARK yang membuktikan bahwa semua tanda tangan dan akar pohon Merkle baru valid. Relayer akhirnya mengirim negara baru dan bukti ke kontrak pintar.
- Kontrak pintar memvalidasi Bukti on-chain. Jika valid, ia akan menyimpan akar pohon Merkle dari negara baru di memori internal kontrak.
Pada dasarnya, akar pohon Merkle menggambarkan seluruh negara bagian dari semua akun. Dan Anda tidak dapat mengubahnya (= mencuri uang) kecuali Anda dapat membuktikan validitas tanda tangan yang transaksinya mengarah ke negara baru yang dirangkum oleh root baru yang Anda kirim.
Singkatnya: pengguna memiliki transaksi super cepat dan hampir gratis, seperti di Coinbase, tanpa perlu mempercayai relayer, yang tidak bisa melakukan apa pun, tidak seperti di Coinbase, tanpa tanda tangan Anda.
Ini adalah rantai samping non-penahanan yang keadaannya dirangkum oleh akar pohon Merkle.
Mari kita hubungkan apa yang kita pelajari di atas tentang SNARK dengan apa yang baru saja kita diskusikan tentang penskalaan. Ada berbagai cara untuk melakukan itu. Saya akan membandingkan 2 resep: Vitalik versi dan barryWhiteHat versi.
SETUP dilakukan oleh ...
Orang yang memulai proyek, yang juga menciptakan kontrak pintar. Semakin diaudit, semakin baik. Anda harus percaya padanya ... itu a pengaturan tepercaya!
Kontrak pintar menghemat ...
2 Merkle root (nilai bytes32): pohon pertama berisi alamat akun (tanda tangan publik), saldo dan nonces akun kedua
PROVING dilakukan oleh ...
Relayer
Relayer mengirimkan ke kontrak pintar ...
- akar 2 Merkle dari negara baru (address tree and balances + nonces tree)
- daftar transaksi, tanpa tanda tangan. “Setiap transaksi menghabiskan biaya 68 gas per byte. Oleh karena itu, untuk transfer reguler, kita dapat mengharapkan biaya marjinal menjadi 68 * 3 (dari) + 68 * 3 (ke) + 68 * 1 (biaya) + 68 * 4 + 4 * 2 (jumlah) + 68 * 2 (nonce), atau 892 gas ”
Input yang diketahui dari proses PROVING adalah ...
- 2 akar Merkle negara lama
- 2 akar Merkle negara baru
- daftar transaksi
Proses MEMBERIKAN membuktikan bahwa ...
Mengingat
- 2 akar Merkle negara lama (sudah disimpan dalam kontrak)
- 2 akar Merkle New state (dikirim dalam transaksi aggr.)
- daftar transaksi (dikirim dalam transaksi aggr.)
... relayer memiliki tanda tangan yang valid untuk pindah dari negara dengan 2 akar tua ke negara dengan 2 akar baru dengan transaksi tersebut.
VERIFIKASI dilakukan oleh ...
Kontrak pintar (kode dalam soliditas, vyper, sesuka Anda!)
Masukan yang diketahui untuk proses VERIFIKASI adalah ...
Proses input yang diketahui diketahui, jelas ...!
Batas skalabilitas
Setiap transaksi agregat menggunakan gas 650k untuk verifikasi SNARK (biaya tetap) ditambah ~ 900 gas dari biaya marjinal per transaksi (Biayanya mengirim data!). Jadi menggunakan seluruh blok relayer dapat mengumpulkan paling banyak:
yang berarti ~ 544 tx per detik
barryWhiteHat's versi
SETUP dilakukan oleh ...
Orang yang memulai proyek.
Kontrak pintar menghemat ...
1 Merkle root dengan Negara saat ini. Setiap daun adalah status hash dari akun.
Ingin membuat sebuah akun?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
PROVING dilakukan oleh ...
Relayer
Relayer mengirimkan ke kontrak pintar ...
- bukti 𝚷
- akar Merkle negara baru
- bukti 𝚷
Input yang diketahui dari proses PROVING adalah ...
- akar Merkle negara lama
- akar Merkle negara baru
Proses MEMBERIKAN membuktikan bahwa ...
Mengingat
- akar Old Merkle (sudah disimpan dalam kontrak)
- root New Merkle (senti dalam transaksi aggr.)
... relayer memiliki daftar transaksi dengan tanda tangan yang valid untuk berpindah dari keadaan dengan root lama ke state dengan root baru
VERIFIKASI dilakukan oleh ...
Kontrak pintar (kode dalam soliditas, vyper, sesuka Anda!)
Masukan yang diketahui untuk proses VERIFIKASI adalah ...
Proses input yang diketahui diketahui, jelas ...!
Batas skalabilitas
Relayer tidak mengirimkan data transaksi ke kontrak pintar (yang mahal), jadi batasnya sebenarnya adalah jumlah gas untuk memverifikasi bukti SNARK.
Menyebutkan Howard Wu kerja tentang menjalankan fase PROVING SNARK pada sistem terdistribusi, barryWhiteHat optimis menyatakan bahwa adalah mungkin untuk mengkonfirmasi 16666 transaksi dalam SNARK besar (1 miliar kendala!).
barryWhiteHat juga berpikir dimungkinkan untuk memverifikasi bukti 𝚷 pada rantai dengan gas 500 k, yang berarti Anda dapat menempatkan 16 SNARK (8 juta / 500 k) per blok, yang merupakan ~ 1.07 SNARKs per detik ... yang berarti ~ 17,832 tx per detik (16,666 * 1.07).
Menuju tak terbatas dan melampauinya
- Semua yang berkilau bukanlah emas / 1. Jumlah daya komputasi dan memori yang Anda butuhkan pada fase Proving dapat benar-benar mengejutkan. Terutama dalam versi barryWhiteHat, di mana bagian dari kompleksitas dipindahkan off-chain. Barry menulis “Pada laptop dengan 7 GB ram dan 20 GB ruang swap, ia berjuang untuk mengumpulkan 20 transaksi per detik”. Nah, jika tujuannya adalah 17,832 tx per detik ... LOL. Ini memperkenalkan tantangan komputasi paralel yang tidak sepele. Tetapi jika biaya $ rata-rata per transaksi jauh lebih murah daripada opsi no-SNARKs biasa ... gim ini sepadan dengan lilin.
- Semua yang berkilau bukanlah emas / 2. Ada masalah ketersediaan data yang relevan! Karena hanya root pohon yang disimpan dalam kontrak, Anda harus yakin bahwa seluruh versi pohon (atau, itu sama, seluruh riwayat transaksi) selalu tersedia. Jika data tidak tersedia relayer, bahkan dengan transaksi yang ditandatangani yang sah, tidak dapat melakukan apa-apa karena dia tidak dapat membuktikan Negara Lama → Transaksi → Negara Baru.
- Agar relayer tidak dapat dipercaya dan Eter dalam kontrak memiliki nilai Eter yang sama di luar (masalah likuiditas) ... pengguna harus dapat menarik uang dari kontrak pintar saat mereka inginkan, tanpa bergantung pada relayer (spesifik). Bagaimana? Ini bukan dalam lingkup 101 posting ini, tetapi Anda dapat membaca tentang ini di tautan terlampir.
- Ingin memahami lebih lanjut tentang bagaimana Negara saat ini (alamat, saldo dan nonces) dapat ditangani dengan pohon Merkle? Menambahkan daun, memperbarui daun, dll? Periksa perpustakaan ini (file uji di sini) yang menggunakan dasar ini modul. Terima kasih, HarryR!
- Ingin mengatur lingkungan Ethereum-SNARK pribadi Anda? Mari kita mulai dari rantai dengan C ++ (Setup, Proving, Verifying) di sini. Kemudian Anda dapat pindah ke Ethereum (jangan lupa, hanya Verifikasi dilakukan secara on-chain!) Dengan Zokrates (repo, yang dokumentasi untuk memulai).
- Bagaimana kalau menggunakan akumulator RSA alih-alih pohon Merkle? Google “Rsa akumulator ethereum” untuk memulai…
Menikmati!
Twitter @tokopedia
- 7
- Akun
- Semua
- antara
- tersedianya
- Dasar-dasar
- Milyar
- kasus
- perubahan
- Cek
- coinbase
- komputasi
- Konsensus
- kontrak
- Biaya
- terbaru
- Kondisi saat ini
- DApps
- data
- kumpulan data
- Desentralisasi
- Dimensi
- Buku Besar Terdistribusi
- teknologi ledger terdistribusi
- Lingkungan Hidup
- Eter
- ethereum
- EU
- EV
- gadungan
- Akhirnya
- Pertama
- Gratis
- fungsi
- permainan
- GAS
- GitHub
- Pemberian
- Gold
- baik
- besar
- membimbing
- hash
- di sini
- High
- sejarah
- Seterpercayaapakah Olymp Trade? Kesimpulan
- hr
- HTTPS
- besar
- Ratusan
- ia
- indeks
- informasi
- IP
- IT
- Pekerjaan
- kunci
- laptop
- besar
- memimpin
- Buku besar
- Tingkat
- LG
- Perpustakaan
- Likuiditas
- Daftar
- Arus utama
- Peta
- medium
- juta
- penambang
- uang
- bulan
- Paling Populer
- pindah
- nama
- jaringan
- node
- nomor
- Operasi
- urutan
- Lainnya
- pemilik
- Membayar
- Konsultan Ahli
- pemain
- Populer
- kekuasaan
- swasta
- Key pribadi
- program
- proyek
- bukti
- membuktikan
- publik
- Key publik
- rekap
- RSA
- aturan
- berjalan
- aman
- penghematan
- Skalabilitas
- Skala
- skala
- Ilmu
- keamanan
- set
- Share
- berbagi
- Pendek
- Sederhana
- Ukuran
- tidur
- pintar
- kontrak pintar
- smartphone
- So
- Perangkat lunak
- soliditas
- Solusi
- MEMECAHKAN
- Space
- Pengeluaran
- awal
- mulai
- Negara
- Negara
- sukses
- sistem
- sistem
- Teknologi
- uji
- waktu
- Token
- puncak
- semburan
- .
- Transaksi
- Kepercayaan
- Pembaruan
- Pengguna
- nilai
- Verifikasi
- Visa
- W
- SIAPA
- kata
- Kerja
- bekerja
- bernilai
- X