Transformasi Fiat–Shamir

Apa Itu Transformasi Fiat–Shamir?

Transformasi Fiat–Shamir adalah teknik kriptografi yang mengubah protokol pembuktian interaktif tertentu menjadi bukti non-interaktif atau tanda tangan digital.Teknik ini menghilangkan kebutuhan verifier untuk mengirim tantangan acak baru secara langsung kepada prover.Sebagai gantinya, prover menghitung tantangan dengan melakukan hashing terhadap transkrip protokol, pernyataan publik, komitmen, pesan, dan konteks lain yang diperlukan.Bukti yang dihasilkan dapat dibuat satu kali dan diverifikasi kemudian oleh siapa pun yang memiliki informasi publik yang sama.Teknik ini juga disebut heuristik Fiat–Shamir karena keamanannya biasanya bergantung pada pemodelan fungsi hash kriptografi sebagai random oracle.

Amos Fiat dan Adi Shamir memperkenalkan pendekatan ini dalam karya mereka pada 1986, How to Prove Yourself: Practical Solutions to Identification and Signature Problems.

Transformasi ini penting dalam mata uang kripto karena sistem blockchain tidak selalu dapat mendukung komunikasi privat berulang antara setiap prover dan verifier.Bukti non-interaktif dapat dimasukkan ke dalam transaksi, blok, pemanggilan smart contract, bukti rollup, tanda tangan, dan pesan lintas blockchain.

Masalah Apa yang Diselesaikan Transformasi Fiat–Shamir?

Banyak protokol proof-of-knowledge awalnya dirancang sebagai percakapan antara prover dan verifier.Prover terlebih dahulu membuat komitmen terhadap keacakan tersembunyi atau informasi yang berkaitan dengan rahasia.Verifier kemudian mengirim tantangan acak yang tidak dapat diprediksi prover sebelum membuat komitmen.Prover merespons dengan menggunakan witness rahasia dan tantangan tersebut.Verifier memeriksa apakah komitmen, tantangan, respons, dan pernyataan publik memenuhi persamaan protokol.Interaksi ini dapat merepotkan di jaringan terdesentralisasi karena prover dan verifier harus online secara bersamaan dan bertukar beberapa pesan.Transaksi blockchain mungkin kemudian diperiksa secara terpisah oleh ribuan node yang tidak terlibat saat bukti dibuat.Transformasi Fiat–Shamir mengganti tantangan acak langsung dari verifier dengan tantangan hash deterministik yang dapat dihitung ulang oleh semua verifier.Hasilnya adalah transkrip bukti portabel yang dapat disimpan, dikirim, dan diverifikasi tanpa menghubungi prover aslinya.

Bagaimana Bukti Interaktif Bekerja?

Protokol interaktif tiga pesan yang umum terdiri atas komitmen, tantangan, dan respons.Prover mengetahui nilai rahasia yang disebut witness.Pernyataan publik menjelaskan hal yang diklaim diketahui prover atau komputasi yang diklaim telah diselesaikan dengan benar.Pada langkah pertama, prover mengambil keacakan privat dan menghasilkan komitmen.Pada langkah kedua, verifier menghasilkan tantangan acak yang tidak dapat diprediksi.Pada langkah ketiga, prover menggabungkan witness, keacakan privat, dan tantangan untuk menghitung respons.Verifier hanya menerima bukti jika respons konsisten dengan komitmen, tantangan, dan pernyataan publik.Tantangan harus sulit diprediksi saat komitmen dibuat.Jika tidak, prover yang tidak jujur dapat membuat komitmen yang hanya berlaku untuk tantangan yang sudah dipilih sebelumnya.

Bagaimana Transformasi Fiat–Shamir Bekerja?

Transformasi ini menghilangkan pesan kedua dari verifier dan menggantinya dengan perhitungan hash kriptografi.Prover terlebih dahulu membuat komitmen yang sama seperti dalam protokol interaktif.Kemudian prover melakukan hashing terhadap pernyataan publik, komitmen, pesan, pengenal protokol, dan data transkrip lain yang diperlukan.Output hash diubah menjadi tantangan dari ruang tantangan yang valid untuk protokol tersebut.Prover menghitung respons dengan menggunakan tantangan itu dan witness rahasia.Bukti non-interaktif akhir biasanya memuat komitmen dan respons, sementara verifier dapat menghitung ulang tantangannya.Verifier menyusun kembali transkrip, menghitung tantangan hash yang sama, lalu menjalankan persamaan verifikasi awal.Transformasi sederhananya dapat ditulis sebagai:

Input dan aturan encoding yang tepat sangat penting bagi keamanan.

Contoh Protokol Schnorr

Protokol identifikasi Schnorr memberikan contoh transformasi Fiat–Shamir yang mudah dipahami.

Misalkan sebuah grup siklik memiliki generator

dan orde .

Prover memiliki private key

dan public key .

Prover ingin menunjukkan bahwa ia mengetahui

tanpa mengungkapkannya.

Dalam protokol interaktif, prover memilih nilai acak

dan mengirim komitmen .

Verifier merespons dengan tantangan acak

.

Prover menghitung

.

Verifier memeriksa apakah

.

Respons yang valid menunjukkan bahwa prover dapat memenuhi persamaan untuk tantangan yang tidak dapat diprediksi.

Menerapkan Fiat–Shamir pada Protokol Schnorr

Versi non-interaktif mengganti tantangan yang dibuat verifier dengan hash.

Prover menghitung tantangan seperti

.

Prover kemudian menghitung

.

Bukti atau tanda tangan memuat komitmen

dan respons .

Verifier menghitung ulang tantangan dari public key, komitmen, konteks, dan pesan yang sama.Verifier menerima bukti jika persamaan verifikasi Schnorr terpenuhi.

RFC 8235 menetapkan bukti zero-knowledge non-interaktif Schnorr yang dibuat dari skema identifikasi Schnorr tiga tahap melalui transformasi Fiat–Shamir.

Bagaimana Transformasi Ini Membuat Tanda Tangan Digital

Bukti identifikasi menunjukkan bahwa prover mengetahui rahasia yang terkait dengan identitas publik.Untuk membuat tanda tangan digital, tantangan juga mengikat bukti pada pesan tertentu.Perubahan pesan akan mengubah output hash sehingga tantangannya juga berubah.Bukti yang dibuat untuk satu transaksi biasanya tidak dapat digunakan kembali sebagai tanda tangan valid untuk transaksi lain.Respons penanda tangan menunjukkan bahwa ia mengetahui private key dan mengikat pengetahuan tersebut pada pesan yang ditandatangani.Pola pengubahan identifikasi menjadi tanda tangan ini merupakan salah satu penggunaan transformasi Fiat–Shamir yang paling penting.

Fiat–Shamir dan Tanda Tangan Schnorr Bitcoin

BIP 340 Bitcoin menetapkan tanda tangan Schnorr untuk kurva eliptik secp256k1.Tantangan tanda tangan diperoleh dengan melakukan hashing terhadap komitmen nonce, public key, dan pesan.Hal ini mengikuti pola tanda tangan Schnorr non-interaktif yang dikaitkan dengan transformasi Fiat–Shamir.

BIP 340 juga menggunakan tagged hash untuk memisahkan perhitungan hash-nya dari penggunaan protokol lain.

Tagged hashing mengawali input dengan nilai yang diturunkan dari label khusus protokol.Hal ini mengurangi risiko fungsi hash dan format input yang sama ditafsirkan sebagai dua operasi kriptografi yang berbeda.Tanda tangan BIP 340 digunakan dalam aturan transaksi Taproot Bitcoin.Transformasi ini lebih luas daripada Bitcoin dan dapat digunakan dengan banyak sistem bukti, grup aljabar, dan asumsi kriptografi.

Fiat–Shamir dalam Sistem Bukti Zero-Knowledge

Sistem bukti zero-knowledge modern sering dimulai dari protokol yang lebih mudah dijelaskan sebagai interaksi antara prover dan verifier.Prover mengirim komitmen polinomial, Merkle root, elemen grup, atau pesan lainnya.Verifier merespons dengan elemen medan acak atau posisi kueri.Fiat–Shamir memperoleh tantangan tersebut dari transkrip, alih-alih mengharuskan adanya verifier langsung.Dengan demikian, bukti dapat dibuat off-chain dan diverifikasi kemudian oleh node blockchain atau smart contract.Transformasi ini digunakan dalam sistem yang mendukung transaksi privat, bukti validitas, rollup skalabel, komputasi yang dapat diverifikasi, dan interoperabilitas blockchain.

Fiat–Shamir dalam Halo2

Halo2 menjelaskan protokol buktinya secara interaktif untuk keperluan analisis, tetapi mewujudkannya secara non-interaktif melalui transformasi Fiat–Shamir.Transkrip memuat komitmen dan pesan prover lainnya.Output hash kriptografi diubah menjadi tantangan verifier yang digunakan untuk evaluasi polinomial dan pemeriksaan bukti.

Dokumentasi protokol Halo2 menjelaskan bahwa argumen interaktif public-coin menjadi non-interaktif dengan mengganti verifier menggunakan fungsi hash yang kuat secara kriptografi.

Halo2 juga menganalisis sifat keamanan dengan memperhitungkan kemampuan prover untuk membuat dan meninjau kembali keadaan transkrip.Hal ini menunjukkan bahwa penerapan Fiat–Shamir secara aman memerlukan lebih dari sekadar mengganti pembangkit angka acak dengan satu pemanggilan hash.

Fiat–Shamir dalam Bukti STARK

Sistem pembuktian STARK menggunakan beberapa putaran komitmen dan tantangan verifier.Tantangan dapat menentukan koefisien acak, titik evaluasi polinomial, dan kueri pengujian derajat rendah.Fiat–Shamir channel memperoleh keacakan non-interaktif ini dari transkrip bukti yang terus berkembang.Prover memasukkan komitmen ke dalam channel sebelum meminta tantangan berikutnya.Verifier mengulangi operasi transkrip yang sama dan memperoleh tantangan yang sama.

Dokumentasi prover STARK menjelaskan Fiat–Shamir channel yang digunakan untuk menghasilkan keacakan non-interaktif selama pembuatan bukti.

Jika komitmen atau input publik berubah, tantangan berikutnya seharusnya ikut berubah.

Apa Itu Random Oracle Model?

Random oracle model adalah model keamanan yang memperlakukan fungsi hash sebagai fungsi acak publik yang ideal.Setiap input unik memperoleh output acak yang saling independen.Penggunaan ulang input yang sama selalu menghasilkan output yang sama.Siapa pun dapat meminta nilai dari oracle, tetapi tidak ada yang dapat memprediksi output baru tanpa mengirimkan kueri terkait.Fungsi hash nyata adalah algoritma deterministik, bukan random oracle ideal.Bukti keamanan Fiat–Shamir dalam random oracle model menunjukkan keamanan berdasarkan asumsi ideal tersebut.Implementer kemudian menggunakan fungsi hash kriptografi nyata sebagai pengganti oracle, dengan keyakinan bahwa perilakunya cukup menyerupai model untuk protokol tersebut.Random oracle model berguna, tetapi bukti dalam model tersebut bukan bukti tanpa syarat tentang setiap implementasi hash yang mungkin.

Mengapa Hash Harus Mencakup Seluruh Transkrip?

Setiap tantangan harus terikat pada seluruh informasi protokol sebelumnya yang memengaruhi maknanya.Informasi ini dapat mencakup parameter publik, public key, pernyataan, komitmen, pesan, tantangan sebelumnya, pengenal chain, dan versi protokol.Menghilangkan nilai penting dapat memungkinkan bukti dipindahkan ke konteks lain.Bukti mungkin berlaku untuk dua public key, dua aplikasi, dua jaringan blockchain, atau dua tahap protokol, padahal seharusnya hanya berlaku untuk salah satunya.Dalam bukti multi-putaran, setiap tantangan harus bergantung pada transkrip yang telah terkumpul sebelum tantangan tersebut.Prover harus berkomitmen pada data sebelumnya sebelum mengetahui tantangan yang diturunkan.Melakukan hashing hanya pada pesan terakhir dapat merusak jaminan urutan yang dibutuhkan protokol interaktif.

Apa Itu Pemisahan Domain?

Pemisahan domain memastikan satu operasi hash tidak tertukar dengan operasi hash lain yang menggunakan fungsi dasar yang sama.Protokol dapat menambahkan label unik seperti nama, versi, jaringan, tahap bukti, atau jenis operasi.Label ini mengubah input hash meskipun data lainnya sama.Tanpa pemisahan domain, nilai yang dibuat sebagai tantangan dalam satu protokol dapat ditafsirkan sebagai nonce, komitmen, atau tantangan dalam protokol lain.Pemisahan domain sangat penting dalam perangkat lunak mata uang kripto, tempat satu fungsi hash dapat digunakan kembali untuk ID transaksi, tanda tangan, Merkle tree, derivasi kunci, dan transkrip bukti.

Tagged hashing khusus protokol dalam BIP 340 merupakan contoh praktis perlindungan ini.

Mengapa Encoding Kanonis Penting?

Prover dan verifier harus melakukan hashing terhadap rangkaian byte yang persis sama.Nilai matematis terkadang memiliki beberapa representasi byte yang valid.Bilangan bulat dapat di-encode dengan panjang, urutan byte, atau nol di depan yang berbeda.Titik kurva eliptik dapat memiliki encoding terkompresi, tidak terkompresi, atau alternatif yang tidak valid.Daftar dapat menjadi ambigu jika panjang dan batas elemennya tidak di-encode dengan jelas.Serialisasi kanonis menetapkan satu representasi yang diterima untuk setiap nilai transkrip yang valid.Awalan panjang, label tipe, kolom lebar tetap, dan aturan decoding yang ketat dapat mencegah ambiguitas.Implementasi sebaiknya menolak nilai nonkanonis, bukan menormalisasikannya secara berbeda dari verifier lain.

Panjang Tantangan dan Soundness

Ruang tantangan memengaruhi kemungkinan prover yang tidak jujur berhasil tanpa mengetahui witness yang valid.Tantangan satu bit memberi prover yang curang peluang relatif besar untuk menebak dengan benar dalam satu putaran.Mengulang protokol atau menggunakan tantangan yang lebih besar dapat mengurangi kesalahan soundness.Output hash harus diubah menjadi tantangan dengan ukuran yang memadai untuk tingkat keamanan yang diperlukan.Pemotongan tantangan yang terlalu agresif dapat melemahkan bukti.Pemetaan output hash ke medan atau orde grup juga harus menghindari bias statistik yang tidak dapat diterima.Protokol dapat menggunakan rejection sampling, reduksi lebar, atau metode lain yang terdokumentasi untuk menurunkan tantangan dengan benar.

Apa Itu Fiat–Shamir Grinding?

Grinding terjadi ketika prover berulang kali mengubah keacakan komitmen yang diizinkan dan melakukan hashing terhadap setiap transkrip yang dihasilkan sampai memperoleh tantangan yang menguntungkan.Prover dapat melakukan pencarian ini karena tantangan dibuat secara lokal, bukan oleh verifier langsung yang independen.Analisis keamanan harus memperhitungkan jumlah kueri hash dan ukuran ruang tantangan.Ruang tantangan yang cukup besar membuat grinding yang berguna tidak praktis secara komputasi berdasarkan asumsi protokol.Aplikasi sebaiknya tidak menambahkan nilai yang tidak perlu dan dikendalikan prover ke transkrip jika nilai tersebut membuat grinding lebih murah atau menimbulkan bias.Sistem bukti yang menggunakan Fiat–Shamir harus menganalisis perilaku ini, bukan menganggap prover hanya melakukan satu kueri hash secara jujur.

Risiko Replay dan Pengikatan Konteks

Bukti non-interaktif dapat disalin karena merupakan objek data publik.Penyalinan tidak berbahaya jika bukti hanya menunjukkan pernyataan publik yang tidak terikat waktu.Penyalinan menjadi berbahaya ketika aplikasi keliru menganggap kepemilikan bukti sebagai bukti tindakan baru atau otorisasi yang masih berlaku.Transkrip dapat memuat ID transaksi, penerima, jaringan, nilai sesi, alamat kontrak, masa berlaku, atau nonce khusus aplikasi.Hal ini mengikat bukti pada konteks yang dimaksud.Penambahan nilai konteks tidak membantu jika verifier tidak memeriksa kecocokan nilai tersebut dengan permintaan saat ini.Persyaratan kesegaran berlaku pada protokol aplikasi secara keseluruhan, bukan hanya pada persamaan bukti.

Apakah Fiat–Shamir Otomatis Memberikan Zero-Knowledge?

Tidak. Transformasi ini tidak otomatis menjadikan setiap protokol bersifat zero-knowledge.Protokol interaktif awal harus memiliki sifat zero-knowledge atau honest-verifier zero-knowledge yang sesuai.Protokol hasil transformasi juga harus dianalisis berdasarkan model keamanan yang dipilih.Komitmen mungkin memerlukan keacakan blinding untuk mencegah pengungkapan witness.Tantangan transkrip mungkin memerlukan pembatasan agar tidak menghasilkan nilai khusus yang membocorkan informasi privat.Sebuah bukti dapat bersifat non-interaktif tanpa bersifat zero-knowledge.Non-interaktif hanya berarti prover dapat membuat bukti tanpa menerima pesan langsung dari verifier.

Apakah Fiat–Shamir Otomatis Memberikan Soundness?

Tidak. Transformasi yang aman pada satu protokol tidak membuktikan bahwa semua protokol serupa aman.Protokol interaktif awal harus memiliki soundness, special soundness, atau proof-of-knowledge yang diperlukan.Input hash dan pemetaan tantangan harus mempertahankan urutan yang dimaksud: komitmen dibuat sebelum tantangan.Sejumlah protokol memerlukan asumsi yang lebih kuat atau bukti khusus setelah transformasi.Konstruksi dapat aman dalam random oracle model klasik, tetapi tidak memiliki bukti memadai terhadap penyerang kuantum.Developer sebaiknya mengandalkan konstruksi yang telah ditinjau dan memiliki bukti keamanan, bukan menerapkan Fiat–Shamir secara informal pada protokol baru.

Fiat–Shamir dan Kriptografi Pascakuantum

Pola desain Fiat–Shamir juga digunakan dalam riset tanda tangan pascakuantum.Skema identifikasi berbasis lattice, kode, dan komputasi multipihak dapat menggunakan tantangan yang diturunkan dari hash untuk membuat tanda tangan.Sejumlah tanda tangan berbasis lattice menggunakan variasi yang dikenal sebagai Fiat–Shamir with aborts.Penanda tangan dapat mengulang sebagian proses penandatanganan ketika respons perantara berpotensi membocorkan informasi atau tidak sesuai distribusi yang diterima.

NIST FIPS 204 menstandarkan ML-DSA, algoritma tanda tangan digital berbasis module lattice yang diturunkan dari desain Dilithium.

Adanya standar tanda tangan pascakuantum tidak berarti setiap bukti Fiat–Shamir klasik tetap aman terhadap komputer kuantum.

Fiat–Shamir dalam Quantum Random Oracle Model

Penyerang kuantum dapat meminta nilai random oracle dalam superposisi banyak input.Hal ini berbeda dari penyerang klasik yang mengirimkan satu kueri biasa setiap kali.Bukti random-oracle klasik tidak otomatis tetap valid dalam quantum random-oracle model, yang biasa disingkat QROM.Peneliti kriptografi telah mengembangkan teknik pembuktian dan persyaratan protokol tambahan untuk menganalisis konstruksi Fiat–Shamir terhadap penyerang kuantum.Karena itu, klaim keamanan pascakuantum harus didukung analisis yang mencakup QROM atau model keamanan kuantum lain yang sesuai.Mengganti grup klasik dengan masalah lattice saja tidak cukup.

Fiat–Shamir dan Tanda Tangan Ambang Batas

Tanda tangan ambang batas membagi kewenangan penandatanganan di antara beberapa peserta.Sejumlah peserta yang memenuhi ambang batas bekerja sama membuat satu tanda tangan valid tanpa merekonstruksi seluruh private key di satu tempat.Protokol threshold Schnorr harus mengoordinasikan komitmen nonce dan perhitungan tantangan dengan cermat.Tantangan harus mengikat public key gabungan, komitmen nonce gabungan, pesan, konteks peserta, dan aturan protokol.Pembuatan transkrip yang keliru dapat memungkinkan manipulasi nonce, perilaku rogue-key, atau serangan lintas sesi.

RFC 9591 menetapkan protokol penandatanganan threshold Schnorr FROST dan operasi ciphersuite berbasis hash-nya.

Keunggulan Transformasi Fiat–Shamir

Transformasi ini menghilangkan interaksi langsung dengan verifier dari sistem bukti yang kompatibel.Bukti dapat dibuat satu kali dan diverifikasi secara terpisah oleh banyak node blockchain.Transformasi ini mengurangi putaran komunikasi dan menyederhanakan verifikasi asinkron.Bukti dapat dimasukkan ke dalam transaksi, blok, smart contract, dan penyimpanan terdistribusi.Bukti yang sama dapat diperiksa tanpa memberikan keacakan privat kepada verifier atau mempertahankan sesi interaktif.Transformasi ini juga memberikan cara praktis untuk mengubah protokol identifikasi menjadi skema tanda tangan digital.Sifat-sifat tersebut membuatnya berguna bagi jaringan terdesentralisasi yang pesertanya mungkin tidak pernah berkomunikasi secara langsung.

Keterbatasan Transformasi Fiat–Shamir

Transformasi ini biasanya bergantung pada random oracle model.Transformasi ini tidak mengubah setiap bukti interaktif menjadi bukti yang aman.Penghilangan data transkrip dan inkonsistensi encoding dapat menimbulkan kerentanan serius.Prover dapat menghitung hash berulang kali, sehingga perilaku grinding harus masuk dalam analisis keamanan.Bukti non-interaktif dapat diputar ulang kecuali aplikasi mengikatnya pada konteks yang sesuai.Keamanan kuantum memerlukan analisis terpisah.Transformasi ini tidak melindungi implementasi dari kebocoran side-channel, keacakan yang lemah, korupsi memori, atau private key yang dicuri.Pembuatan bukti juga tetap dapat memerlukan komputasi intensif meskipun interaksi telah dihilangkan.

Transformasi Fiat–Shamir vs. Bukti Interaktif

Bukti interaktif mengharuskan pesan dipertukarkan antara prover dan verifier.Verifier memberikan tantangan acak baru selama interaksi.Bukti Fiat–Shamir memperoleh tantangan tersebut dari hash transkrip.Bukti non-interaktif lebih mudah didistribusikan dan diverifikasi secara asinkron.Protokol interaktif dapat mengandalkan keacakan verifier yang sesungguhnya, sedangkan protokol hasil transformasi bergantung pada perilaku hash yang menyerupai random oracle.

Transformasi Fiat–Shamir vs. Bukti Zero-Knowledge Non-Interaktif

Transformasi Fiat–Shamir adalah salah satu metode untuk membuat bukti non-interaktif.Bukti zero-knowledge non-interaktif, atau NIZK, adalah kategori bukti yang lebih luas: tidak memerlukan interaksi langsung dengan verifier dan tidak mengungkap informasi witness yang dilindungi.Sejumlah NIZK menggunakan Fiat–Shamir, sedangkan yang lain menggunakan common reference string, trusted setup, transparent setup, atau teknik kriptografi berbeda.Menyebut bukti sebagai non-interaktif tidak menjelaskan metode yang digunakan untuk membuatnya.

Transformasi Fiat–Shamir vs. Tanda Tangan Digital

Tanda tangan digital mengautentikasi pesan menggunakan private key dan public key untuk verifikasi.Transformasi Fiat–Shamir adalah teknik konstruksi yang dapat mengubah protokol identifikasi tertentu menjadi skema tanda tangan.Tidak semua tanda tangan digital dibuat melalui Fiat–Shamir.Tidak semua bukti Fiat–Shamir dimaksudkan untuk berfungsi sebagai tanda tangan digital.Bukti dapat menunjukkan pengetahuan atas witness atau kebenaran suatu komputasi tanpa mengautentikasi seseorang atau wallet.

Transformasi Fiat–Shamir vs. Hash-to-Curve

Hash-to-curve mengubah data input sembarang menjadi titik valid pada kurva eliptik.Fiat–Shamir mengubah data transkrip menjadi tantangan verifier.Sistem bukti dapat menggunakan kedua operasi tersebut.Tantangan dapat berupa skalar, sementara komponen protokol lain mungkin memerlukan titik kurva yang diturunkan dari hash.Kedua proses tersebut memerlukan aturan pemisahan domain dan encoding tersendiri.

Transformasi Fiat–Shamir vs. Commit-Reveal

Protokol commit-reveal mengharuskan peserta memublikasikan komitmen, lalu mengungkap nilai tersembunyi setelahnya.Protokol ini dapat digunakan untuk mengurangi pengetahuan sebelumnya atau manipulasi keacakan bersama.Fiat–Shamir tidak menunggu pengungkapan keacakan publik di kemudian waktu.Fiat–Shamir membuat tantangan deterministik dari transkrip yang ada.Commit-reveal dan Fiat–Shamir menyelesaikan masalah koordinasi yang berbeda, meskipun keduanya menggunakan komitmen dan hash kriptografi.

Praktik Terbaik Implementasi

Developer sebaiknya menggunakan sistem bukti yang memiliki analisis keamanan Fiat–Shamir yang dipublikasikan dan telah ditinjau.Transkrip harus mencakup setiap nilai publik yang menentukan pernyataan dan konteks.Setiap protokol dan tahap bukti harus memiliki pemisahan domain yang unik.Semua nilai harus menggunakan serialisasi kanonis dengan batas tipe dan panjang yang jelas.Komitmen harus dimasukkan sebelum tantangan yang bergantung padanya dibuat.Output tantangan harus dipetakan ke medan atau grup menggunakan metode tanpa bias yang terdokumentasi.Titik yang tidak valid, skalar nonkanonis, nilai medan yang dilarang, dan transkrip cacat harus ditolak.Keacakan prover dan nonce penandatanganan harus dibuat secara aman atau diturunkan menggunakan metode deterministik yang disetujui.Implementasi sebaiknya menguji bahwa perubahan apa pun pada pernyataan, komitmen, pesan, pengenal jaringan, atau versi protokol akan mengubah tantangan yang dihasilkan.Vektor pengujian sebaiknya mencakup urutan transkrip, encoding, tag domain, nilai kosong, nilai batas, dan bukti cacat.

Kesalahan Umum Implementasi Fiat–Shamir

Salah satu kesalahan adalah melakukan hashing terhadap komitmen tanpa menyertakan pernyataan publik.Kesalahan lain adalah tidak menyertakan pesan ketika bukti dimaksudkan untuk berfungsi sebagai tanda tangan.Penggabungan data yang ambigu dapat menyebabkan dua transkrip berbeda menghasilkan rangkaian byte yang sama.Penggunaan label domain yang sama pada protokol yang tidak terkait dapat menimbulkan kebingungan lintas protokol.Membuat tantangan berikutnya sebelum memasukkan semua pesan prover sebelumnya akan merusak urutan transkrip.Mengurangi hash pendek secara langsung ke medan besar dapat menghasilkan entropi tantangan yang lemah.Menerima titik kurva atau skalar nonkanonis dapat menyebabkan implementasi berbeda melakukan hashing terhadap representasi yang berbeda.Penggunaan ulang keacakan prover dapat mengungkap witness rahasia dalam protokol mirip Schnorr.Menganggap bukti klasik otomatis memberikan keamanan pascakuantum merupakan kesalahan serius lainnya.

Mengapa Transformasi Fiat–Shamir Penting bagi Mata Uang Kripto?

Jaringan mata uang kripto memerlukan bukti yang dapat diverifikasi secara terpisah oleh peserta di seluruh dunia.Transaksi blockchain tidak dapat bergantung pada percakapan privat dengan setiap node di masa mendatang yang mungkin memverifikasinya.Fiat–Shamir memungkinkan penalaran kriptografi interaktif dikemas menjadi objek bukti statis.Hal ini mendukung tanda tangan ringkas, sistem privasi, rollup zero-knowledge, eksekusi smart contract yang dapat diverifikasi, wallet ambang batas, dan aplikasi blockchain lainnya.Transformasi ini juga menunjukkan prinsip desain kripto yang penting.Fungsi hash dapat melakukan lebih dari sekadar membuat ID transaksi, karena fungsi ini dapat menghasilkan tantangan yang tampak tidak dapat diprediksi dan mengikat seluruh transkrip protokol.Kemampuan tersebut bergantung pada konstruksi yang cermat, serialisasi yang presisi, pemisahan domain yang kuat, dan bukti keamanan yang sesuai.

Pertanyaan Umum

Apa fungsi transformasi Fiat–Shamir?

Transformasi ini mengganti tantangan acak verifier dalam protokol interaktif tertentu dengan tantangan yang diturunkan dari hash kriptografi atas transkrip.

Mengapa Fiat–Shamir berguna dalam mata uang kripto?

Teknik ini memungkinkan bukti dan tanda tangan diverifikasi kemudian oleh node blockchain tanpa percakapan langsung dengan prover.

Siapa yang menciptakan transformasi Fiat–Shamir?

Amos Fiat dan Adi Shamir memperkenalkan teknik ini dalam karya yang dipresentasikan pada 1986.

Apakah transformasi Fiat–Shamir sama dengan fungsi hash?

Tidak. Ini adalah transformasi protokol yang menggunakan fungsi hash untuk menghasilkan tantangan verifier.

Apa itu bukti interaktif?

Bukti interaktif adalah protokol ketika prover dan verifier bertukar komitmen, tantangan, dan respons.

Apa itu protokol public-coin?

Protokol public-coin adalah protokol interaktif yang pesan verifiernya terdiri atas tantangan acak yang terlihat publik.

Apa itu transkrip Fiat–Shamir?

Transkrip Fiat–Shamir adalah kumpulan berurutan yang memuat parameter publik, pernyataan, komitmen, tantangan, respons, pesan, dan konteks yang digunakan oleh bukti.

Apa itu random oracle model?

Random oracle model adalah model keamanan ideal yang memperlakukan fungsi hash sebagai fungsi acak publik dengan output yang konsisten.

Apakah fungsi hash nyata merupakan random oracle?

Bukan. Fungsi hash nyata bersifat deterministik, meskipun protokol dapat menganalisisnya seolah-olah berperilaku seperti random oracle ideal.

Apakah Fiat–Shamir otomatis menghasilkan zero-knowledge?

Tidak. Protokol awal dan konstruksi hasil transformasi harus memenuhi persyaratan zero-knowledge yang diperlukan.

Apakah Fiat–Shamir membuat tanda tangan digital?

Teknik ini dapat mengubah protokol identifikasi tertentu menjadi tanda tangan jika pesan disertakan dalam hash tantangan.

Apakah Bitcoin menggunakan pola Fiat–Shamir?

Tanda tangan Schnorr BIP 340 Bitcoin menggunakan tantangan yang diturunkan dari hash dan mengikat komitmen nonce, public key, serta pesan.

Apakah Fiat–Shamir digunakan dalam rollup zero-knowledge?

Banyak sistem bukti rollup menggunakan tantangan transkrip ala Fiat–Shamir untuk menjadikan protokol bukti interaktif bersifat non-interaktif.

Apakah Fiat–Shamir digunakan dalam STARK?

Ya. Prover dan verifier STARK dapat menggunakan Fiat–Shamir channel untuk memperoleh tantangan non-interaktif dari komitmen.

Apakah Fiat–Shamir digunakan dalam Halo2?

Ya. Halo2 mewujudkan uraian bukti interaktifnya sebagai argumen non-interaktif melalui Fiat–Shamir.

Apa itu pemisahan domain?

Pemisahan domain menambahkan label khusus protokol pada input hash agar output dari operasi kriptografi berbeda tidak tertukar.

Mengapa public key harus di-hash?

Hashing public key mengikat bukti atau tanda tangan pada identitas yang dimaksud dan dapat mencegah serangan substitusi kunci atau lintas kunci.

Mengapa pesan harus di-hash?

Menyertakan pesan memastikan tanda tangan untuk satu pesan tidak dapat digunakan kembali untuk pesan lain.

Apa itu challenge grinding?

Challenge grinding adalah pembuatan komitmen berulang kali sampai hash transkrip menghasilkan tantangan yang menguntungkan prover.

Bisakah bukti Fiat–Shamir diputar ulang?

Bukti publik dapat disalin, sehingga protokol yang memerlukan kesegaran harus menyertakan dan memverifikasi konteks sesi atau transaksi yang sesuai.

Apa itu serialisasi kanonis?

Serialisasi kanonis menetapkan satu representasi byte yang diterima untuk setiap nilai transkrip.

Mengapa urutan transkrip penting?

Setiap tantangan harus bergantung pada semua pesan sebelumnya agar prover tidak dapat mengubah komitmen setelah mengetahui tantangan.

Bisakah Fiat–Shamir digunakan dengan kurva eliptik?

Ya. Bukti dan tanda tangan Schnorr umumnya menerapkannya dalam grup kurva eliptik.

Bisakah Fiat–Shamir digunakan dalam kriptografi pascakuantum?

Ya. Konstruksi terkait digunakan dalam tanda tangan pascakuantum, tetapi keamanannya memerlukan analisis kuantum yang sesuai.

Apa itu quantum random oracle model?

Quantum random oracle model adalah model ketika penyerang kuantum dapat meminta nilai random oracle menggunakan superposisi kuantum.

Apakah bukti keamanan klasik tetap berlaku terhadap penyerang kuantum?

Tidak otomatis, karena bukti tersebut mungkin tidak memperhitungkan kueri oracle kuantum atau batas ekstraksi kuantum.

Apa itu Fiat–Shamir with aborts?

Ini adalah variasi ketika penanda tangan dapat mengulang proses jika respons tidak memenuhi persyaratan distribusi atau ukuran.

Apakah Fiat–Shamir memerlukan trusted setup?

Tidak. Transformasi ini sendiri tidak memerlukan trusted setup, meskipun sistem bukti yang mendasarinya mungkin memiliki persyaratan setup tersendiri.

Bisakah smart contract memverifikasi bukti Fiat–Shamir?

Ya, jika kontrak dapat menghitung ulang hash transkrip dan memeriksa persamaan bukti secara efisien.

Apa risiko implementasi terbesar?

Risiko utama yang umum mencakup pengikatan transkrip yang tidak lengkap, encoding ambigu, pemisahan domain yang buruk, pembuatan nonce yang lemah, dan asumsi keamanan yang tidak didukung.

Kesimpulan

Transformasi Fiat–Shamir mengubah protokol interaktif public-coin yang kompatibel menjadi bukti non-interaktif atau tanda tangan digital.Transformasi ini mengganti tantangan tak terduga dari verifier langsung dengan tantangan yang diturunkan dari hash kriptografi atas transkrip bukti.Dengan demikian, bukti dapat dibuat satu kali dan diverifikasi secara terpisah oleh node blockchain, wallet, smart contract, dan aplikasi kripto lainnya.Transformasi ini mendukung tanda tangan Schnorr, sistem bukti zero-knowledge, STARK, protokol bergaya Halo2, tanda tangan ambang batas, dan riset tanda tangan pascakuantum.Keamanannya bergantung pada sifat protokol interaktif awal dan asumsi yang digunakan untuk memodelkan fungsi hash.Implementasi yang benar harus mengikat seluruh pernyataan, komitmen, pesan, parameter publik, konteks, dan versi protokol ke dalam transkrip kanonis.Implementasi juga harus menggunakan pemisahan domain yang kuat, ukuran tantangan yang memadai, pembuatan nonce yang aman, dan aturan pemetaan tantangan yang telah ditinjau dengan cermat.Transformasi Fiat–Shamir bukan peningkatan keamanan otomatis untuk setiap protokol bukti.Transformasi ini merupakan konstruksi yang kuat, tetapi keamanannya bergantung pada desain protokol yang ketat, disiplin implementasi, serta analisis keamanan terhadap penyerang klasik maupun kuantum.