Zero-Knowledge Proof: Apa Itu zk-STARK dan Bagaimana Cara Kerjanya?

1. Apa itu zk-STARK?

Sistem Proof of Reserves (PoR) zk-STARK memanfaatkan teori STARK, yaitu sebuah solusi matematis yang kompleks. zk-STARK adalah singkatan dari: Zero-Knowledge Transparent Argument of Knowledge, yaitu teknologi bukti kriptografi yang didasarkan pada ide Vitalik untuk menegakkan integritas dan privasi komputasi pada blockchain. Di sini kami akan memperkenalkan cara kerja dan menjelaskan konsep matematikanya secara umum. Jika Anda tertarik untuk lebih mendalaminya, silakan kunjungi halaman ini atau di sini.

Bagaimana cara kerjanya?

Gambar 1. Tabel jejak eksekusi dan Merkle tree dibangun untuk PoR zk-STARK

Langkah 1: batasan pembangunan

Untuk membuktikan tanggung jawab bursa kami, kami menyatakan tiga klaim:

Klaim 1: Kami mengakumulasi nilai setiap pengguna dengan benar, termasuk nilai setiap kripto dan nilai bersih setiap pengguna

Klaim 2: Bursa tidak memalsukan pengguna virtual yang nilai bersihnya negatif untuk mengurangi total kewajiban bursa (Pengguna individu yang memiliki saldo negatif hanya dapat diterima jika nilai bersihnya di atas 0)

Klaim 3: Total nilai yang diklaim oleh bursa diperhitungkan untuk setiap pengguna tunggal, sehingga setiap pengguna dapat memverifikasi nilai bersih yang didapat dari total nilai

Untuk menguji dan memverifikasi klaim di atas, kami perlu membuat batasan seperti:

Klaim 1: Batasan Total Saldo (Batasan total saldo yang benar)

uts: besaran jejak pengguna (user trace size), yaitu jumlah baris jejak yang disertakan dalam setiap data pengguna.

jumlah: total saldo pengguna

N: jumlah pengguna

Klaim 2: Batasan Non-negatif (Batasan ekuitas bersih positif)

Klaim 3: Batasan Penyertaan (Batasan penyertaan seluruh saldo rekening nasabah)

Berdasarkan batasan di atas, kami membuat tabel jejak untuk melakukan komitmen dan memverifikasi total saldo dan non-negativitas melalui inspeksi pengambilan sampel. Sebagai contoh sederhana, berikut simulasi jika ada 3 pengguna dengan nilai USD maksimum kurang dari 4^6 = 4096:

1）Kami menginisialisasi tabel dengan 32 baris dan 5 kolom, lalu kami mengisi nilai dan ID pengguna ke baris dengan keterangan k % 8 = 6 dan . Setiap 8 baris adalah satu blok dan info aset pengguna kini ke belakang dari setiap blok. Pengguna pertama diberikan saldo virtual 0, sehingga kami dapat mempublikasikannya untuk membuktikan bahwa akumulasi nilai tidak dimulai dari nilai negatif.

2）Kami mengumpulkan nilai aset pengguna satu per satu, lalu mengisi hasilnya ke baris dengan keterangan k % 8 = 7 dan yang merupakan baris terakhir dari setiap blok

3）Kami terus membagi total nilai setiap pengguna dengan 4, baris demi baris, dari ke belakang dari setiap blok. Kami melakukannya untuk menjaga agar nilai bersih pengguna tetap non-negatif dengan memeriksa apakah baris pertama adalah nol untuk setiap blok. Jika seseorang memiliki nilai bersih negatif, baris pertama bloknya tidak akan menjadi nol karena nilai negatif (-x) akan berubah menjadi (p - x) dalam bidang terbatas yang merupakan nilai positif yang sangat besar.

4）Kami memasukkan nomor acak untuk setiap pengguna dan mengisi ruang kosong di tabel dengan 0

Langkah 2: Perpanjangan polinomial berderajat rendah Dengan menggunakan batasan polinomial di atas, kami dapat memperoleh polinomial jejak komputasi dengan panjang *uts N. Demi keamanan, kami melakukan komitmen terhadap polinomial pada domain evaluasi yang lebih besar dengan faktor amplifikasi domain sebagai faktor_ekstensi.

Dalam kasus di atas, kami dapat menghitung polinomial p(x) dari I(x). Saat menggunakan faktor_ekstensi 8, kami akan menghitung lagi titik 32(8-1)* pada p(x).

Karena dua polinomial berbeda dengan D derajat akan berbagi titik D paling banyak, contoh pasangan polinomial dengan polinomial yang valid (yang memenuhi batasan di atas) dan polinomial palsu dengan D derajat (yang tidak memenuhi batasan di atas ) akan berbagi titik D paling banyak. Artinya, polinomial palsu memiliki peluang untuk lulus inspeksi pengambilan sampel acak. Jika kami melakukan inspeksi pengambilan sampel n kali, peluangnya akan berkurang menjadi .

Kami menerapkan faktor_ekstensi default sebesar 16 dan waktu default inspeksi pengambilan sampel sebesar 16, sehingga tingkat keamanannya akan menjadi 80 bit.

Langkah 3: Komitmen polinomial Kami menghitung nilai hash dari jejak komputasi dan saldo pengguna yang sesuai, ID pengguna, dan nilai polinomial batasan yang sesuai untuk setiap baris, lalu menghasilkan Merkle tree. Merkle root adalah nilai komitmen polinomial.

Langkah 4: Menghasilkan bukti sampel Dengan menggunakan Merkle root sebagai sumber acak, kami mengambil sampel data. Untuk menghindari bocornya data jejak komputasi, kami menghindari data dengan indeks faktor_ekstensi* k selama pengambilan sampel dan menghasilkan jalur bukti Merkle yang sesuai dengan indeks pengambilan sampel.

Kami melakukan inspeksi pengambilan sampel untuk memeriksa apakah polinomial yang dilakukan adalah polinomial yang valid yang memenuhi batasan yang tercantum pada Langkah 1. Sebagaimana ditentukan dalam Langkah 2, waktu inspeksi pengambilan sampel akan memengaruhi kemungkinan keberhasilan perusakan atau manipulasi.

Langkah 5: Menghasilkan bukti tingkat rendah

Kami dapat mengontrol kemungkinan keberhasilan perusakan atau manipulasi melalui inspeksi pengambilan sampel. Namun, ada syarat seperti yang disebutkan pada Langkah 2 bahwa kita perlu memastikan derajat polinomial yang diverifikasi tidak lebih dari derajat polinomial yang valid. Untuk meningkatkan efisiensi pembuktian, kami menggabungkan semua polinomial batasan secara linier menjadi satu polinomial dan menghasilkan pembuktian tingkat rendah untuknya. Koefisien kombinasi juga dihasilkan menggunakan Merkle root sebagai sumber acak.

Misalnya, jika kita ingin membuktikan bahwa p0(x), p1(x), dan p2(x) tidak lebih dari D derajat, kita dapat menghasilkan 2 koefisien acak dari Merkle root yang dihasilkan pada Langkah 3, lalu menghitung polinomial linier l(x) sebagai berikut:

k0 = hash(root "0")
k1 = hash(root "1")
l(x) = k0 * p0(x) k1 * p1(x) p2(x)

Jika l(x) dapat dibuktikan tidak lebih dari D derajat, maka peluang derajat sembarang dari p0(x), p1(x), dan p2(x) bernilai lebih dari D akan mendekati 0

Langkah 6: Verifikasi total saldo Pertama, kami memverifikasi bukti tingkat rendah yang dihasilkan pada Langkah 5.

Kemudian, verifikasi terbuka lebih lanjut dilakukan pada data sampel yang dihasilkan pada Langkah 4. Pertama untuk memverifikasi bahwa data konsisten dengan komitmen polinomial dan kedua untuk memverifikasi bahwa data sesuai dengan batasan yang ditetapkan pada Langkah 1. Akhirnya, koefisien kombinasi polinomial uji tingkat rendah diverifikasi.

Langkah 7: Buat bukti penyertaan pengguna Untuk membuktikan bahwa pengguna tertentu disertakan dalam jumlah total yang diklaim oleh bursa, kami memberikan jejak pengguna yang dihitung, saldo pengguna, ID pengguna, dan nomor acak yang sesuai dengan indeks pengguna. Kami juga menyediakan jalur Merkle yang sesuai dengan data ini.

Langkah 8: Verifikasi pengguna atas bukti penyertaan Pengguna memeriksa saldo, ID, menghitung nilai hash dari data yang sesuai dengan indeksnya, dan memverifikasi nilai hash pada node daun Merkle tree menggunakan jalur Merkle yang disediakan.

2. Bagaimana cara melakukan verifikasi mandiri terhadap Proof of Reserves (PoR)?

2.1 Verifikasi batasan Penyertaan zk-STARK

Teori Verifikasi

Berdasarkan prosedur STARK, kami akan menghitung tabel jejak eksekusi dari semua aset pengguna seperti di bawah ini, melakukan hashing terhadap setiap informasi pengguna sebagai tabel jejak yang menjadi daun Merkle tree, lalu mengalokasikan daun tersebut ke Merkle root yang akan diterbitkan selama setiap putaran audit PoR.

Untuk memverifikasi apakah aset Anda termasuk dalam root, kami akan memberi Anda jalur Merkle untuk verifikasi. Pertama-tama, Anda dapat menghitung daun Anda dengan hashing informasi aset Anda, lalu memverifikasi apakah daun Anda adalah daun yang valid di Merkle tree dan root yang kami publikasikan.

Misalnya, pada Gambar 1, pengguna dengan id id_k akan menghitung hashk = hash("20" "15" "5" "id_k" "99821"), lalu data lain dalam bingkai kotak merah akan menjadi verifikasi jalur Merkle. Alat sumber terbuka disediakan bagi pengguna untuk melakukan verifikasi ini.

Karena daun Merkle tree merupakan hash, tidak ada informasi pribadi Anda yang akan dibocorkan kepada orang lain.

Cara memverifikasi:

1）Untuk memverifikasi apakah saldo aset akun Anda telah dimasukkan sebagai daun Merkle zk-STARK, masuk ke akun OKX Anda, kunjungi "Audit" untuk melihat audit terkini, lalu klik "Detail" untuk melihat data audit Anda.

2）Dapatkan data yang Anda perlukan untuk verifikasi manual dengan mengeklik "Salin data".

3）Setelah mengeklik "Salin data", buka editor teks (misalnya, menggunakan notebook), lalu tempel dan simpan string JSON sebagai file. File harus diakhiri dengan nama "_inclusion_proof.json." String JSON berisi saldo akun Anda dan snapshot jalur Merkle, lalu menyimpan file di folder baru.

Teks JSON ditampilkan seperti di bawah ini：

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
“bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43”
]
}
}

4）Unduh instrumen verifikasi sumber terbuka OKXzk-STARKValidator

5）Simpan instrumen verifikasi sumber terbuka OKX zk-STARKValidatordan file string JSON bersamaan di folder baru dari langkah 3. Dalam kasus kami, kami menaruh instrumen serta file data di folder "Unduhan" bernama "proof-of-reserves" sebagaimana ditunjukkan di bawah ini:

6）Membuka zk-STARKValidator akan otomatis menjalankan file string JSON yang Anda simpan di folder.

7） Periksa hasilnya

• Jika lolos verifikasi, hasil "Inclusion constraint validation passed” (Lolos validasi batasan penyertaan) akan ditampilkan:

  

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

  

2.2 Verifikasi Total Saldo zk-STARK dan Batasan Non-negatif

Cara memverifikasi:

Untuk memverifikasi dan membuktikan bahwa aset yang kami klaim benar dan tidak ada pengguna yang memiliki ekuitas bersih negatif, kunjungi "[file Audit] kami(https://www.okx.com/proof-of-reserves/download?tab=liabilities)", lalu unduh file "zk-STARK" dalam laporan Liabilitas, lalu simpan di folder baru.

Buka zip file yang diunduh, lalu akan ada folder "sum proof data" yang mencakup ribuan folder cabang dan satu folder trunk. Setiap folder berisi dua file JSON bernama "sum_proof.json" dan 'sum_value.json'.

Unduh alat verifikasi sumber terbuka OKXzk-STARKValidator

Simpan instrumen verifikasi sumber terbuka OKXzk-STARKValidator dan folder "sum proof data" bersamaan di folder yang baru dibuat dari langkah 1. Dalam kasus kami, kami menaruh instrumen dan file data di folder "Unduhan" bernama "proof-of-reserves” sebagaimana ditunjukkan di bawah:

Membuka zk-STARKValidator akan otomatis menjalankan "sum proof data" yang Anda simpan di folder.

Cek hasilnya

Jika lolos verifikasi, hasil "Total sum and non-negative constraint validation passed” (Lolos validasi batasan jumlah total dan non-negatif) akan ditampilkan:

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