Analisis mendalam tentang keamanan lengkap STARK

原文：Aman dan Sehat — Mendalami Keamanan STARK

Terjemahan dan koreksi: “Komunitas Cina Starknet”

Fakta Singkat Unggulan

• STARK non-interaktif berasal dari Interactive Oracle Proof (IOP), dikompilasi menjadi bukti non-interaktif dalam model oracle acak.
• Artikel ini menjelaskan pembaruan terkini pada dokumentasi ethSTARK dan memberikan analisis komprehensif dan mendetail tentang keamanan protokol ethSTARK dalam model oracle acak.

Penjelasan detail 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 mempelajari keamanan yang diberikan oleh bukti STARK, mendefinisikannya, dan mengeksplorasi teknik untuk membuktikan keamanan skema.

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

Apa yang ingin kami capai dengan analisis keamanan? Kami ingin mencegah “serangan yang berhasil” pada sistem STARK yang disebabkan oleh pernyataan yang salah dan bukti STARK yang diterima oleh validator STARK sebagai respons terhadap pernyataan (salah) tersebut. Karena penafsiran yang keliru itu berbahaya dan bisa terjadi dalam berbagai bentuk dan ukuran, kami ingin aman dari semua itu. Pernyataan salah apa pun, meskipun sepele seperti 1+1=3, jika 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 konsep keamanan yang lebih kuat seperti keandalan pengetahuan, namun demi kesederhanaan, artikel ini akan fokus pada kasus sederhana tentang keandalan).

Bagaimana kita secara formal mendefinisikan keamanan sistem STARK? Kami menentukan ini dengan menganalisis “kesalahan keandalan”. “Kesalahan keandalan” secara kasar mengukur “biaya” yang diharapkan yang akan dikeluarkan penyerang untuk meluncurkan serangan yang berhasil (yaitu, menemukan bukti STARK untuk pernyataan yang salah, namun bukti tersebut diterima oleh validator STARK). Secara matematis, kesalahan reliabilitas adalah fungsi (t) yang inputnya adalah parameter waktu t, mewakili waktu komputasi yang ingin dihabiskan penyerang untuk melancarkan serangan, dan outputnya adalah probabilitas serangan penyerang akan berhasil (ditemukan untuk pernyataan palsu bukti yang meyakinkan). Semakin besar “biaya” yang bersedia dikeluarkan oleh penyerang, semakin tinggi kemungkinan keberhasilannya.

Sejauh ini, kami telah mendefinisikan keamanan STARK sebagai fungsi (t), yang berbeda dari cara semua orang mendiskusikan keamanan di Twitter kripto setiap hari. Di Twitter, Anda mungkin mendengar sesuatu seperti ini: “Solusi ini memiliki keamanan 96 bit.” Bagaimana hal ini diterjemahkan ke dalam definisi keamanan kita? Tidak ada jawaban pasti untuk pertanyaan ini, karena orang-orang memahami “x bit keamanan” dengan cara yang sedikit berbeda:

• Ditafsirkan secara ketat, ini berarti bahwa untuk setiap t antara 1 dan 2⁹⁶, kesalahan reliabilitasnya adalah (t) 2⁹⁶. Seorang penyerang dengan waktu berjalan 2⁹⁶ atau kurang memiliki kemungkinan sukses yang sangat kecil, kurang dari 2⁹⁶, yaitu kurang dari 1 dalam satu miliar kali 1 dalam satu miliar.
• Penafsiran yang lebih longgar, dan mungkin lebih umum, adalah bahwa keamanan 96-bit berarti bahwa untuk t apa pun, terdapat situasi di mana t/(t) 2⁹⁶. Artinya probabilitas keberhasilannya (berbanding terbalik) linier dengan waktu berjalan. Jika penyerang mempunyai waktu lari 2⁸⁶, maka peluang suksesnya paling banyak adalah 2¹⁰.

Pada artikel ini kita akan membahas opsi kedua.

Dari IOP ke STARK dengan keamanan 96-bit

Jadi, bagaimana kita membuktikan bahwa suatu solusi memiliki keamanan 96 bit? Untuk menjawab pertanyaan ini, kita perlu memahami struktur tingkat tinggi di mana STARK dibangun. STARK terdiri dari tiga bagian utama: IOP (Interactive Oracle Proof), pohon Merkle, dan hash Fiat-Shamir; fokus utama kami adalah IOP. Setelah bagian-bagian komponen ini ditentukan, kita dapat mengkompilasinya untuk menghasilkan STARK. Kami akan membahas komponen-komponen ini secara mendetail, termasuk apa saja komponen-komponen tersebut dan bagaimana kesesuaiannya.

Komponen pertama yang akan kami ulas adalah IOP: IOP mirip dengan bukti interaktif standar, di mana pembukti dan validator berinteraksi selama beberapa putaran (kami terbatas pada protokol koin publik, di mana validator hanya mengirimkan tantangan acak ke pembukti). Dalam IOP, verifikator tidak sepenuhnya membaca pesan peribahasa, melainkan mengambil sampel sebagian kecil bit dari setiap pesan peribahasa. Inilah sebabnya mengapa STARK yang dikompilasi kemudian mencapai kesederhanaan.

Mengingat IOP, bagaimana cara membuat STARK darinya? Pesan dari peribahasa bisa sangat panjang (pada kenyataannya, pesan tersebut lebih panjang dari perhitungannya sendiri). Untuk mengompres informasi ini, kami menggunakan pohon Merkle. Pohon Merkle adalah pohon hash biner di mana setiap simpul daun mewakili kueri atau balasan di IOP. Akarnya adalah janji dari keseluruhan pesan. Saat validator ingin membaca lokasi tertentu dalam pesan, pembukti memberikan nilai lokasi tersebut dan jalur verifikasi. Validator kemudian dapat menggunakan jalur ini untuk memverifikasi bahwa nilainya benar. Validator IOP hanya membaca sejumlah kecil informasi lokasi dari informasi pembukti. Oleh karena itu, protokol ringkas (protokol dengan volume komunikasi rendah) dapat diimplementasikan menggunakan pohon Merkle.

Putaran kompresi

Kita bisa memilih STARK interaktif, namun untuk mempermudah proses pembangkitan STARK, biasanya kita memilih STARK non-interaktif, sehingga validator tidak perlu menunggu informasi eksternal saat membangun STARK. Faktanya, ini adalah bagaimana semua sistem STARK saat ini diterapkan dan bagaimana protokol ethSTARK dibangun. STARK non-interaktif juga merupakan kasus khusus dari SNARK transparan (transparan berarti tidak diperlukan pengaturan tepercaya untuk membuat instance mereka; “Protokol Arthur Merlin” atau “IOP Koin Publik”). Untuk melakukan hal ini, langkah terakhir adalah menerapkan algoritma Fiat-Shamir untuk mengompresi beberapa putaran interaksi menjadi satu pesan, yang kami sebut sebagai bukti STARK. Transformasi Fiat-Shamir adalah metode mengubah protokol interaktif menjadi protokol non-interaktif. Pepatah mensimulasikan protokol interaktif saat berbicara dengan fungsi hash. Untuk mendapatkan tantangan acak pada putaran i, pembuktian melakukan hash pada sebagian catatan untuk putaran i dan menafsirkan keluarannya sebagai tantangan berikutnya.

Hal ini memastikan bahwa pembuktian tidak dapat mengubah jawabannya setelah tantangan dibuat. Namun, pembuktian kecurangan memiliki beberapa cara strategis baru yang tidak tersedia di IOP interaktif. Pembukti dapat membuat ulang tantangan validator dengan memodifikasi informasi pembukti terakhir, sehingga akan mendapatkan rekor baru dan tantangan baru. Ternyata konsep keandalan standar IOP tidak cukup untuk membuktikan keamanan konversi Fiat-Shamir.

Misalnya, punya IOP 96 putaran dan tambahkan peretasan berikut ke validator: jika bit pertama keacakan validator adalah 0 di masing-masing 96 putaran, maka validator akan menerimanya (tanpa melihat bukti apa pun). Kita dapat melihat bahwa menambahkan peretasan ini ke validator hanya menambah istilah 2⁹⁶ pada 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 membobol sistem dalam waktu yang sangat singkat. Yakinlah, skenario mengerikan ini hanyalah contoh teoritis dan tidak berlaku untuk STARK yang dikerahkan. Jadi, mari kita lihat mengapa STARK kita aman. Singkatnya, kita akan menunjukkan bahwa penyerang berlari paling banyak t langkah, dan probabilitas keberhasilan serangan paling banyak (t) t 2⁹⁶.

IOP dan keandalan putaran demi putaran

Keamanan STARK bergantung pada IOP yang mendasarinya. Namun apa artinya IOP memiliki keamanan 96 bit? Berdasarkan definisi standar, kesalahan keandalan IOP adalah 2⁹⁶: ini berarti kemungkinan penyerang mana pun (terlepas dari waktu berjalannya) dapat menipu validator paling banyak adalah 2-96. Namun, seperti yang telah kita diskusikan, keandalan IOP hanyalah salah satu dari tiga komponen tersebut, yang tidak cukup untuk memperoleh keamanan 96 bit dari STARK yang dikompilasi dari ketiga langkah tersebut. Sebaliknya, keamanan STARK yang dikompilasi terbukti dengan asumsi bahwa STARK memiliki kesalahan keandalan putaran demi putaran sebesar 96 bit (definisi serupa yang disebut keandalan pemulihan keadaan kadang-kadang digunakan).

Secara intuitif, “kesehatan putaran demi putaran” berarti bahwa setiap putaran memiliki keamanan 96 bit, bukan hanya keseluruhan protokol. Untuk lebih spesifiknya, keandalan putaran demi putaran mengacu pada keberadaan predikat yang dapat memperoleh bagian dari catatan protokol dan memberi tahu kita apakah catatan ini “menipu”: “catatan kosong” tidak “menipu”, dan kapan Dan catatan lengkapnya “menipu” hanya jika diterima oleh validator. Terakhir, untuk sebagian record yang tidak “memalsukan” validator, kemungkinan bahwa record tersebut menjadi “spoofing” di putaran berikutnya paling banyak 2⁹⁶. Jika ada predikat dengan properti ini, kita katakan bahwa protokol tersebut memiliki keandalan round-to-round 96 bit (predikat ini tidak memerlukan komputasi yang efisien).

Dalam banyak kasus, orang hanya menganalisis keandalan TIO dan bukan keandalan keseluruhannya. Memang benar, sulit untuk memikirkan contoh (kecuali untuk contoh yang diproduksi) dari IOP yang memiliki keandalan standar tetapi tidak memiliki keandalan menyeluruh. Namun, saat menentukan batas keamanan tertentu, perbedaan antara keduanya mungkin timbul dan setiap bit diperhitungkan. Oleh karena itu, untuk mendapatkan batasan yang ketat dan spesifik, diperlukan analisis yang cermat terhadap keandalan IOP setiap putaran. Inilah yang kami lakukan dengan protokol FRI dan ethSTARK IOP yang menjadi dasar STARK IOP. Analisisnya sendiri bukanlah hal yang sepele dan berada di luar cakupan artikel ini. Dengan menggunakan analisis baru, kami dapat menetapkan parameter yang tepat untuk pembuktian kami.

Keandalan menyeluruh benar-benar memberi kami jaminan yang kami perlukan. Pembukti dapat membuat ulang tantangan beberapa kali, tetapi kita tahu bahwa dalam putaran mana pun, kemungkinan menghasilkan catatan palsu adalah 2⁹⁶. Oleh karena itu, jika pembukti memiliki t kali (diukur dalam jumlah panggilan hash), maka Pembukti dapat mencoba di paling banyak t kali untuk mendapatkan catatan yang menipu, yang membatasi probabilitas keberhasilannya hingga (t) t 2⁹⁶.

Tambahkan semua item kesalahan

Yang terakhir, agar semua ini benar, 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 di pohon Merkle. Kemungkinan penyerang menemukan tabrakan menggunakan t panggilan (fungsi hash acak) paling banyak adalah t2/2, yang merupakan panjang keluaran dari fungsi hash (disebabkan oleh “Paradoks Ulang Tahun”). Inilah mengapa kita perlu menyetel fungsi hash Panjangnya dua kali lipat dari keamanan yang dibutuhkan. Jadi jika kita memiliki fungsi hash dengan panjang keluaran 192 dan IOP dengan keandalan putaran demi putaran 96 bit, kita mendapatkan STARK terkompilasi yang dapat diandalkan Kesalahan seksual (t )=t2-⁹⁶ + t2 2¹⁹⁶. Karena t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, skema ini memiliki 95 bit seks keamanan.

Ringkaslah

Secara keseluruhan, STARK menyediakan metode yang ampuh untuk memverifikasi kebenaran perhitungan yang dilakukan pada data publik tanpa kepercayaan. Keamanan STARK biasanya diukur dengan “kesalahan keandalan”, yang mewakili kemungkinan penyerang berhasil memberikan pernyataan palsu dan meyakinkan validator dengan bukti. Untuk mencapai tingkat keamanan yang diperlukan, seperti 96 bit, IOP yang mendasarinya harus memenuhi keandalan setiap putaran untuk memastikan bahwa tingkat keamanan yang tinggi dipertahankan di setiap putaran. Kami menganalisis keandalan IOP yang menjadi dasar STARK kami secara menyeluruh untuk mendapatkan batasan keamanan tertentu.