Artikel Terkait: Safe and Sound — Selami Lebih Dalam Keamanan STARK

Terjemahan dan koreksi: "Komunitas Cina Starknet"

Fakta Singkat Unggulan

• STARK non-interaktif berasal dari Interactive Oracle Proofs (IOPs), yang disusun menjadi bukti non-interaktif dalam model oracle stokastik.

• Artikel ini menjelaskan pembaruan terkini pada dokumentasi ethSTARK dan memberikan analisis komprehensif dan mendetail tentang keamanan protokol ethSTARK dalam model oracle acak.

Penjelasan rinci tentang keamanan STARK

Sistem bukti STARK, atau argumen pengetahuan transparan yang dapat diskalakan, adalah alat yang ampuh untuk integritas komputasi: sistem ini memungkinkan verifikasi yang tidak dapat dipercaya atas kebenaran komputasi yang dilakukan pada data publik. Dalam artikel ini, kita akan mendalami keamanan yang diberikan oleh bukti STARK, mendefinisikannya, dan mengeksplorasi teknik untuk membuktikan keamanan skema.

(Lihat bagian 6 dari dokumentasi ethSTARK (versi 1.2) untuk detailnya, serta karya independen yang penting dan komprehensif mengenai topik ini oleh Block et al.).

Apa yang ingin kita capai dengan analisis keamanan? Kami ingin mencegah “serangan yang berhasil” pada sistem STARK yang diakibatkan oleh pernyataan palsu dan bukti STARK yang diterima oleh validator STARK untuk pernyataan (palsu) tersebut. Karena pernyataan palsu itu berbahaya, dan karena pernyataan palsu bisa datang dalam berbagai bentuk dan ukuran, kita ingin terhindar dari semua pernyataan palsu. Pernyataan salah apa pun, bahkan pernyataan sepele 1+1=3, dikombinasikan dengan bukti STARK yang diterima oleh validator STARK akan dianggap sebagai serangan yang berhasil pada sistem. (Mereka yang memiliki latar belakang kriptografi mungkin tertarik untuk mengetahui bahwa STARK juga dapat memenuhi gagasan keamanan yang lebih kuat seperti keandalan pengetahuan, tetapi demi kesederhanaan, postingan ini akan berfokus pada kasus keandalan yang sederhana).

Bagaimana kita secara formal mendefinisikan keamanan sistem STARK? Kami menentukan hal ini dengan menganalisis “kesalahan keandalan”. “Kesalahan keandalan” secara kasar mengukur “biaya” yang diharapkan harus dikeluarkan penyerang untuk berhasil meluncurkan serangan (misalnya menemukan bukti STARK untuk pernyataan salah yang diterima oleh validator STARK). Secara matematis, kesalahan kemantapan adalah suatu fungsi (t) yang masukannya adalah parameter waktu t, yang menyatakan waktu komputasi yang bersedia dihabiskan penyerang untuk melancarkan serangan, dan keluarannya adalah probabilitas bahwa serangan penyerang akan berhasil (temukan bukti yang meyakinkan untuk pernyataan yang salah). Semakin besar "biaya" yang bersedia dikeluarkan penyerang, semakin tinggi kemungkinan keberhasilannya.

Sejauh ini, kami telah mendefinisikan keamanan STARK sebagai fungsi (t), yang berbeda dari bagaimana keamanan dibahas di Twitter kripto. Di Twitter, Anda mungkin mendengar pernyataan seperti “Skema ini memiliki 96 bit keamanan.” Bagaimana hal ini diterjemahkan ke dalam definisi keamanan kita? Tidak ada jawaban universal untuk pertanyaan ini, karena orang-orang memiliki ide yang sedikit berbeda tentang apa arti “x bit keamanan”:

• Jika ditafsirkan secara ketat, ini berarti bahwa untuk setiap t antara 1 dan 2⁹⁶, kesalahan keandalannya adalah (t) 2⁹⁶. Penyerang yang waktu berjalannya tidak melebihi 2⁹⁶ memiliki kemungkinan keberhasilan yang sangat kecil, kurang dari 2⁹⁶, atau kurang dari satu dalam satu miliar dikalikan satu dalam satu miliar.

• Penafsiran yang lebih longgar dan mungkin lebih umum adalah bahwa 96 bit keamanan berarti bahwa untuk setiap t, ada t/(t) 2⁹⁶. Artinya, kemungkinan keberhasilan berbanding terbalik dengan lamanya waktu berjalan. Jika waktu proses penyerang adalah 2⁸⁶, maka kemungkinan keberhasilannya paling banyak 2¹⁰.

Dalam artikel ini, kita akan membahas pilihan kedua.

Dari IOPs ke STARKs dengan Keamanan 96-bit

Jadi, bagaimana kita membuktikan bahwa suatu skema memiliki keamanan 96 bit? Untuk menjawab pertanyaan ini, kita perlu memahami struktur tingkat tinggi yang menjadi dasar STARK dibangun. STARK terdiri dari tiga bagian utama: IOP (Interactive Oracle Proofs), Merkle Trees, dan Fiat-Shamir Hashing; fokus utama yang akan kita fokuskan adalah IOP. Setelah komponen-komponen ini ditetapkan, kita dapat mengompilasinya untuk menghasilkan STARK. Kita akan melihat lebih dekat pada masing-masing komponen ini, termasuk apa saja komponen itu dan bagaimana mereka saling terkait.

Komponen pertama yang akan kami ulas adalah IOP: IOP serupa dengan bukti interaktif standar, di mana pembuktian dan verifikasi berinteraksi dalam beberapa putaran (kami terbatas pada protokol koin publik, yaitu verifikasi hanya mengirimkan tantangan acak ke pembuktian). Dalam IOP, pemeriksa tidak membaca pesan pembuktian secara keseluruhan, melainkan mengambil sampel sejumlah kecil bit dari setiap pesan pembuktian. Inilah sebabnya mengapa STARK yang disusun selanjutnya mampu mencapai kesederhanaan.

Sekarang setelah kita memiliki IOP, bagaimana kita membangun STARK darinya? Pesan pembuktian bisa sangat panjang (bahkan bisa lebih panjang dari perhitungan itu sendiri). Untuk mengompresi informasi ini, kami menggunakan pohon Merkle. Pohon Merkle adalah pohon hash biner yang tiap simpul daunnya merepresentasikan pertanyaan atau jawaban dalam IOP. Akar pohon adalah janji dari keseluruhan pesan. Ketika pemeriksa ingin membaca lokasi tertentu dalam pesan, pembuktian memberikan nilai lokasi tersebut dan jalur verifikasi. Validator kemudian dapat menggunakan jalur ini untuk memverifikasi bahwa nilainya benar. IOP Verifier hanya membaca sejumlah kecil informasi lokasi dari informasi Prover. Oleh karena itu, penggunaan pohon Merkle dapat mencapai protokol yang ringkas (protokol dengan volume komunikasi rendah).

Putaran kompresi

Kita dapat memilih STARK interaktif, tetapi untuk menyederhanakan proses pembuatan STARK, kita biasanya memilih STARK non-interaktif sehingga validator tidak perlu menunggu informasi eksternal saat membangun STARK. Faktanya, beginilah cara semua sistem STARK diterapkan saat ini, dan beginilah cara protokol ethSTARK dibangun. STARK non-interaktif juga merupakan kasus khusus dari SNARK Transparan (transparan berarti tidak diperlukan pengaturan tepercaya untuk mewujudkannya; “Protokol Arthur Merlin” atau “IOP Koin Publik”). Untuk melakukan ini, langkah terakhir adalah menerapkan algoritma Fiat-Shamir untuk memadatkan beberapa putaran interaksi menjadi satu pesan, yang kami sebut bukti STARK. Transformasi Fiat-Shamir adalah metode untuk mengubah protokol interaktif menjadi protokol non-interaktif. Pembuktian mensimulasikan protokol interaktif saat berbicara dengan fungsi hash. Untuk menghasilkan tantangan acak pada ronde i, pembuktian membuat hash ke rekaman parsial ronde i dan menginterpretasikan output sebagai tantangan selanjutnya.

Ini memastikan bahwa pembuktian tidak dapat mengubah jawabannya setelah tantangan dibuat. Namun, pembuktian curang memiliki beberapa jalan strategis baru yang tidak tersedia dalam IOP interaktif. Pembuktian dapat menghasilkan kembali tantangan pemeriksa dengan memodifikasi pesan pembuktian terakhir, yang akan menghasilkan rekaman baru dan dengan demikian tantangan baru. Ternyata konsep keandalan standar IOP tidak cukup untuk membuktikan keamanan transformasi Fiat-Shamir.

Misalnya, miliki IOP sebanyak 96 putaran, dan tambahkan peretasan berikut ke validator: jika bit pertama keacakan validator adalah 0 di setiap putaran 96, maka validator akan menerimanya (tanpa melihat bukti apa pun). Kita dapat melihat bahwa menambahkan peretasan ini ke validator hanya menambahkan istilah 2⁹⁶ ke kesalahan keandalan IOP. Namun, setelah transformasi Fiat-Shamir, penyerang dapat dengan mudah mengubah informasi pembuktian untuk memastikan bahwa setiap nilai hash dimulai dengan 0, sehingga merusak sistem dalam waktu yang sangat singkat. Yakinlah, skenario mengerikan ini hanyalah contoh teoritis dan tidak berlaku bagi STARK yang dikerahkan. Jadi, mari kita lihat mengapa STARK kita aman. Singkatnya, kami akan menunjukkan bahwa penyerang dapat mengeksekusi paling banyak t langkah dan serangan berhasil dengan probabilitas paling banyak (t) t 2⁹⁶.

IOP dan keandalan putaran demi putaran

Keamanan STARK bergantung pada IOP yang mendasarinya. Tetapi apa artinya bagi IOP untuk memiliki keamanan 96 bit? Menurut definisi standar, IOP memiliki kesalahan keandalan sebesar 2⁹⁶: ini berarti bahwa kemungkinan penyerang mana pun (tanpa mempedulikan waktu berjalan) dapat menipu validator paling banyak adalah 2-96. Namun, sebagaimana telah kita bahas, keandalan IOP hanya salah satu dari tiga bagian, yang tidak cukup untuk memperoleh keamanan 96 bit untuk STARK yang dikompilasi dari seluruh tiga langkah. Sebaliknya, dengan asumsi bahwa STARK memiliki kesalahan keandalan putaran demi putaran sebesar 96-bit (definisi serupa yang disebut keandalan pemulihan status terkadang digunakan), keamanan STARK yang dikompilasi terbukti.

Secara intuitif, keandalan putaran demi putaran menunjukkan bahwa setiap putaran memiliki 96 bit keamanan, bukan hanya keseluruhan protokol. Untuk lebih spesifik, keandalan putaran demi putaran berarti bahwa ada predikat yang mengambil sebagian rekaman protokol dan memberi tahu kita apakah rekaman itu "penipuan": rekaman yang kosong bukanlah "penipuan", dan rekaman yang lengkap adalah "penipuan" jika dan hanya jika validator menerimanya. Terakhir, untuk setiap catatan parsial yang bukan validator “curang”, kemungkinan catatan tersebut akan menjadi “curang” di babak berikutnya paling banyak 2⁹⁶. Bila predikat dengan properti ini ada, kita katakan bahwa protokol tersebut memiliki keandalan 96-bit putaran demi putaran (predikat ini tidak perlu dihitung secara efisien).

Dalam banyak kasus, orang hanya menganalisis keandalan IOP tetapi tidak keandalan putaran-ke-putarannya. Harus diakui, sulit untuk memikirkan contoh (kecuali yang buatan) di mana IOP memiliki keandalan standar tetapi tidak keandalan putaran-ke-putaran. Akan tetapi, saat menentukan margin keamanan tertentu, perbedaan antara keduanya dapat muncul dan setiap bit diperhitungkan. Oleh karena itu, untuk memperoleh batasan yang ketat dan spesifik, analisis yang ketat terhadap keandalan IOP putaran demi putaran diperlukan. Inilah yang sedang kami lakukan dengan protokol FRI dan ethSTARK IOP yang menjadi dasar untuk STARK IOP. Analisis itu sendiri jauh dari kata remeh dan berada di luar cakupan artikel ini. Dengan menggunakan analisis baru, kita dapat menetapkan parameter yang tepat untuk pembuktian kita.

Keandalan roda-ke-roda benar-benar memberi kami kepastian yang kami butuhkan. Pembuktian dapat menghasilkan kembali tantangan beberapa kali, tetapi kita tahu bahwa dalam setiap putaran, kemungkinan menghasilkan "catatan palsu" adalah 2⁹⁶. Oleh karena itu, jika pembuktian memiliki waktu t (diukur dalam panggilan hash), maka ia dapat mencoba paling banyak t kali untuk mendapatkan catatan palsu, yang membatasi kemungkinan keberhasilannya menjadi (t) t 2⁹⁶.

Tambahkan semua kesalahan

Akhirnya, agar semua ini berfungsi, kita perlu memastikan bahwa pembuktian tidak dapat merusak pohon Merkle. Kita dapat menunjukkan bahwa selama pembuktian tidak menemukan tabrakan dalam fungsi hash, ia tidak dapat berbuat curang dalam pohon Merkle. Probabilitas penyerang akan menemukan tabrakan dengan t panggilan (ke fungsi hash acak) paling banyak t2/2, yang merupakan panjang keluaran fungsi hash (karena paradoks ulang tahun). Inilah sebabnya kita perlu mengatur panjang fungsi hash menjadi dua kali lipat keamanan yang dibutuhkan. Jadi, jika kita memiliki fungsi hash dengan panjang keluaran 192 dan IOP dengan keandalan 96 bit per putaran, kita mendapatkan STARK yang dikompilasi dengan kesalahan keandalan (t)=t2-⁹⁶ + t2 2¹⁹⁶. Karena t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, skema ini memiliki 95 bit keamanan.

Meringkaskan

Singkatnya, STARK menyediakan metode yang ampuh untuk memverifikasi kebenaran perhitungan yang dilakukan pada data publik dengan cara tanpa kepercayaan. Keamanan STARK sering diukur berdasarkan “kesalahan keandalan”, yang menunjukkan kemungkinan penyerang berhasil memberikan pernyataan palsu dan meyakinkan validator dengan suatu bukti. Untuk mencapai tingkat keamanan yang diperlukan, misalnya 96 bit, IOP yang mendasarinya harus memenuhi keandalan putaran demi putaran untuk memastikan bahwa tingkat keamanan tinggi dipertahankan pada setiap putaran. Kami menganalisis keandalan IOP putaran demi putaran yang menjadi dasar STARK kami, dan memperoleh batasan keamanan yang konkret.