Zero-Knowledge Proof: Apa Itu zk-STARK Dan Bagaimana Cara Kerjanya? (zk-Stark V2)

Apa Itu Proof-of-Reserves Dan Zero Knowledge Proof?

Proof-of-Reserves (PoR)

PoR adalah proses bagi bursa mata uang kripto untuk menunjukkan bahwa mereka memiliki aset yang cukup untuk menutup semua saldo pelanggan. Hal ini membangun kepercayaan dengan membuktikan bahwa bursa tidak menyembunyikan kewajiban apa pun. Cara termudah untuk menunjukkannya adalah dengan menerbitkan jumlah aset bursa dan daftar saldo pengguna sehingga semua orang dapat mengonfirmasinya:

• Total kepemilikan aset pengguna yang diklaim oleh OKX adalah jumlah dari total saldo aset setiap pengguna.

• Setiap total saldo pengguna berjumlah lebih dari nol, lalu aset mereka diperhitungkan untuk menutup kewajiban mereka dan memastikan bahwa setiap pengguna memiliki ekuitas bersih yang positif.

• Total nilai yang diklaim oleh bursa diperhitungkan untuk setiap pengguna tunggal, sehingga setiap pengguna harus dapat memverifikasi penyertaan nilai bersih mereka dalam total nilai

Namun, mengungkapkan saldo ini dapat membahayakan privasi pengguna. Untuk menyelesaikannya, kami menggunakan metode yang disebut Zero Knowledge Proof (ZKP) untuk melindungi privasi pengguna.

Zero Knowledge Proof (ZKP)

ZKP adalah teknik keamanan yang memungkinkan bursa mata uang kripto membuktikan bahwa suatu pernyataan adalah benar tanpa mengungkapkan informasi tambahan.

Dalam kasus kami, kami ingin membuktikan bahwa kami memiliki dana yang cukup tanpa membagikan detail pengguna tertentu. Sebagian besar ZKP termasuk dalam dua kategori:

• zk-SNARK

• zk-STARK

Kami menggunakan zk-STARK karena lebih aman dan memiliki asumsi keamanan minimum. Dalam artikel ini, kami akan menjelaskan cara kami menggunakan zk-STARK untuk melindungi privasi pengguna sambil membuktikan solvabilitas kami.Sebelum melanjutkan, penting untuk memahami beberapa istilah dasar ZKP, seperti Sirkuit, Pohon Merkle, dan Komitmen.

Ada banyak sumber daya yang tersedia untuk membantu pemula memulai. Pengguna tingkat lanjut dapat merujuk ke Kursus MOOC dan monograf akademik.

Bagaimana Cara Kerja zk-STARK?

Kami membuat pohon Merkle menggunakan hash dari akun setiap pengguna sebagai daun. Setiap akun menunjukkan saldo dalam USD untuk berbagai token (mis., BTC, ETH). Untuk menangani saldo ini, kami memisahkan saldonya menjadi ekuitas non-negatif dan utang untuk setiap token. Dengan cara ini, kami hanya menangani angka positif, sehingga memudahkan penghitungan dan menghindari kesalahan.

Misalnya:

• Jika saldo token BTC pengguna adalah A, maka ekuitas BTC-nya adalah A dan utang BTC adalah 0

• Jika saldo token ETH pengguna adalah -B, maka ekuitas yang sesuai adalah 0 dan utangnya adalah B

Berikutnya, kami membangun pohon Merkle dengan nilai akun ini sebagai daun. Akar pohon berfungsi sebagai nilai tunggal yang mewakili semua saldo pengguna. Setiap pengguna dapat membuktikan bahwa akun mereka adalah bagian dari pohon ini dengan menggunakan Jalur Merkle yang menunjukkan cara akun mereka terhubung ke akar.

Kami juga menerbitkan total ekuitas dan utang yang dijumlahkan dari seluruh token dan pengguna. Kemudian, kami membuat Zero Knowledge Proof (ZKP) untuk menunjukkan dua hal:

• Bukti Jumlah: Nilai ekuitas dan utang dalam pohon Merkle terakumulasi dengan benar

• Bukti Non-negatif: Total ekuitas setiap pengguna lebih besar dari total utang mereka

Verifikasi pohon Merkle untuk akun dalam jumlah besar menjadi terlalu sulit untuk ditangani sekaligus. Untuk mengatasi tantangan ini, kami membagi akun menjadi beberapa kelompok kecil yang disebut batch. Setiap batch diproses secara terpisah menggunakan sirkuit batch yang memeriksa bagian bawah dari pohon Merkle.

Selain memungkinkan pengelolaan akun, pembuatan batch juga memungkinkan kita untuk menjalankan pemeriksaan ini secara bersamaan (pemrosesan paralel). Setelah mendapatkan hasil dari setiap batch, kami menggunakan lapisan sirkuit lain yang disebut sirkuit rekursif untuk menggabungkan dan memverifikasi semua batch hingga kami telah membuktikan seluruh pohon Merkle.

Apa Itu Sirkuit Batch?

Sirkuit batch menerima 1024 akun (acc₀, acc₁,..., acc₁₀₂₃) sebagai input, lalu menghasilkan 3 output utama: Sebuah hash (h_batch), total nilai ekuitas (e_batch), dan total nilai utang (d_batch). Sirkuit ini memeriksa bahwa:

• Total ekuitas dalam USD dari setiap akun lebih besar daripada total utangnya.

• e_batch adalah jumlah dari semua nilai ekuitas dalam USD di seluruh akun ini

• d_batch adalah jumlah dari semua nilai utang dalam USD di seluruh akun ini

• h_batch adalah akar dari pohon Merkle yang dibuat menggunakan hash akun

• Tidak ada luapan selama penjumlahan untuk e_batch dan d_batch

Apa Itu Sirkuit Rekursif?

Sirkuit rekursif mengambil 64 macam bukti (π₀, ..., π₆₃), hash (h₀, ..., h₆₃), ekuitas (e₀, ..., e₆₃₎, dan utang (d₀, ..., d₆₃) dari sirkuit lapisan bawah sebagai input. Sirkuit ini menggabungkan input tersebut, lalu menghasilkan 3 output: Hash baru (h_recursive), total ekuitas (e_recursive), dan total utang (d_recursive). Sirkuit ini memeriksa bahwa:

• Masing-masing dari 64 bukti tersebut valid

• Setiap bukti π₀, ..., π₆₃ dari sirkuit lapisan bawah valid

• e_recursive adalah jumlah dari e₀, ..., e₆₃

• d_recursive adalah jumlah dari d₀, ..., d₆₃

• h_recursive adalah hash dari penggabungan h₀, ..., h₆₃, i.e.

  • h_recursive = Hash (h₀ || h₁ || ... || h₆₃₎

• Tidak ada luapan selama penjumlahan untuk e_recursive dan d_recursive

Apa Hubungan Antara Sirkuit Batch Dan Sirkuit Rekursif?

Diagram di bawah ini menggambarkan cara sirkuit batch dan sirkuit rekursif saling terhubung dan mentransfer data. Perlu diingat bahwa dalam diagram ini, kami menduplikasi sirkuit untuk tujuan ilustrasi. Namun, dalam implementasi kami, hanya satu sirkuit yang digunakan untuk setiap lapisan.

Struktur pohon Merkle kami sedikit berbeda. Di 10 level terendah, setiap node induk memiliki 2 anak, sedangkan di level atas, setiap induk memiliki 64 anak. Hal ini dikarenakan sirkuit batch menangani bagian bawah, sedangkan sirkuit rekursif mengelola bagian atas. Diagram di bawah ini menggunakan contoh "Alice" untuk menunjukkan pohon Merkle dan bukti Merkle-nya (berwarna hijau).

Untuk detail teknis selengkapnya, seperti cara kami menyesuaikan nomor akun dengan ukuran batch atau memilih algoritma hash yang tepat, lihat halaman ini.

Kemajuan dalam zk-PoR Versi 2

zk-PoR Versi 2 kami telah menghasilkan beberapa kemajuan dari versi sebelumnya:

• Efisiensi yang lebih besar: Versi ini 50 kali lebih cepat daripada versi sebelumnya. Versi ini membutuhkan waktu 3 jam pada satu mesin 10-core dibandingkan dengan versi sebelumnya yang membutuhkan waktu 36 jam menggunakan sembilan mesin 64-core. Percepatan ini dihasilkan oleh penggunaan kerangka kerja Plonky2 yang mengompilasi sirkuit yang ditulis dengan Rust menjadi bahasa mesin yang efisien daripada menggunakan skrip Python yang lebih lambat. Kami juga meningkatkan Plonky2 untuk menjalankan beberapa komputasi di GPU, sehingga mengurangi waktu hingga 30%.

• Keterauditan yang lebih baik: Dengan Versi 2, kami menggunakan kerangka kerja tingkat tinggi yang menangani detail kriptografi kompleks untuk kami. Hal ini membuat kode kami lebih jelas, lebih mudah dibaca, dan lebih terhindar dari kesalahan.

• Bukti yang ringkas: Ukuran bukti V2 (~500 KB) hanyalah 0,05% dari V1 (~1,2 GB). Berkat metode rekursif, bukti dapat diakumulasikan dan dipadatkan berulang kali menjadi satu bukti.

Bagaimana Cara Melakukan Verifikasi Mandiri Terhadap Proof of Reserves (PoR)?

Berikut adalah cara untuk memeriksa apakah saldo aset Anda termasuk sebagai daun Merkle zk-STARK:

1. Masuk ke akun OKX Anda, buka Aset, lalu pilih Laporan PoR

2. Pilih Detail untuk melihat data audit Anda

   

3. Dapatkan data yang Anda perlukan untuk verifikasi manual dengan memilih Salin Data

   

4. Setelah memilih Salin Data, buka editor teks (mis. , menggunakan notebook), lalu tempel dan simpan string JSON sebagai file. Nama file harus diakhiri dengan "_inclusion_proof.json." String JSON berisi saldo akun Anda dan snapshot dari jalur Merkle, lalu simpan file di folder baru

5. Buka editor teks (mis., Notebook), lalu tempel dan simpan string JSON sebagai file. Nama file harus diakhiri dengan "_inclusion_proof.json." Simpan file di folder baru.

   • String JSON berisi saldo akun Anda dan snapshot dari jalur Merkle.

   • Teks JSON ditunjukkan di bawah ini:

     {"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}}

6. Unduh alat verifikasi sumber terbuka OKX: zk-STARKValidator

7. Simpan alat verifikasi sumber terbuka OKX, yaitu zk-STARKValidator, dan file string JSON secara bersamaan di folder baru yang dibuat di Langkah 5. Dalam kasus kami, kami menaruh alat serta file data di folder Unduhan bernama "proof-of-reserves" sebagaimana ditunjukkan di bawah ini:

   

8. Buka zk-STARKValidator. Alat ini akan otomatis menjalankan file string JSON yang Anda simpan di folder

9. Cek hasilnya:

   • Jika lulus verifikasi, hasil Inclusion constraint validation passed (Validasi batasan inklusi lulus) akan ditampilkan:

     

   • Jika verifikasi gagal, hasil Inclusion constraint validation failed (Validasi batasan penyertaan gagal) akan ditampilkan:

     

Bagaimana Cara Memverifikasi Total Saldo Dan Batasan Non-negatif zk-STARK?

Berikut adalah cara untuk memverifikasi bahwa klaim kepemilikan aset kami adalah benar dan bahwa tidak ada pengguna yang memiliki ekuitas bersih negatif:

1. Buka halaman Proof of Reserves kami, lalu pilih Laporan Kewajiban

2. Unduh file zk-STARK, lalu simpan di folder baru

   

3. Buka zip file untuk mengekstrak file "sum_proof_data.json"

   

4. Unduh alat verifikasi sumber terbuka OKX: zk-STARKValidator

5. Simpan alat verifikasi sumber terbuka OKX, yaitu zk-STARKValidator, dan file "sum_proof_data.json" secara bersamaan dalam folder baru yang dibuat di Langkah 2. Dalam kasus kami, kami menaruh alat serta file data di folder Unduhan bernama "proof-of-reserves" sebagaimana ditunjukkan di bawah ini:

   

6. Buka zk-STARKValidator. Alat ini akan otomatis menjalankan data bukti jumlah yang disimpan di folder

7. Cek hasilnya

   • Jika lulus verifikasi, hasil Total sum and non-negative constraint validation passed (Validasi jumlah total dan batasan non-negatif lulus) akan ditampilkan:

     

   • Jika verifikasi gagal, hasil Total sum and non-negative constraint validation failed (Validasi jumlah total dan batasan non-negatif gagal) akan ditampilkan:

     

Untuk menelusuri detail teknis selengkapnya, sistem Proof of Reserves kami memiliki sumber terbuka serta dapat ditinjau dan digunakan di github.