Ditulis oleh: Blockstream Team
Diterjemahkan oleh: Saoirse, Foresight News
Blockstream Research telah menerbitkan laporan penelitian lengkap tentang tanda tangan berbasis lattice untuk Bitcoin. Artikel ini merangkum isi penelitian, temuan inti, dan rekomendasi terkait,laporan lengkap dapat diakses dengan mengklik di sini.
Tanda tangan digital adalah mekanisme inti untuk mengotorisasi transaksi Bitcoin, yang saat ini dilakukan oleh tanda tangan Schnorr dan ECDSA dengan biaya yang sangat rendah. Pada tahun 1994, Shor membuktikan bahwa komputer kuantum yang cukup kuat dapat memecahkan kedua jenis tanda tangan ini. Meskipun kapan mesin seperti itu akan tersedia masih diperdebatkan secara luas, kita perlu merancang rencana penyebaran tanda tangan pasca-kuantum yang layak sebelum masalah itu benar-benar terjadi.
Skema tanda tangan berbasis lattice adalah kandidat populer untuk menggantikan tanda tangan yang ada. Kriptografi lattice telah diteliti selama lebih dari satu abad, dan aplikasi kriptografinya juga telah berkembang selama hampir tiga puluh tahun. Dalam sistem kriptografi pasca-kuantum, tanda tangan berbasis lattice memiliki banyak keunggulan: ukuran total kunci publik dan tanda tangan dapat kurang dari 1,6 kilobyte, sementara struktur aljabarnya di masa depan berpotensi mendukung tanda tangan multisig, tanda tangan ambang batas, dan bukti ringkas.
Laporan ini meneliti tiga skema: Dilithium, Falcon, dan Hawk. Untuk pembaca yang belum mengenal kriptografi lattice, kami menjelaskan desain setiap skema, memperkenalkan secara lengkap alur algoritmanya, dan menganalisis dari dimensi keamanan, kinerja, dan penyebaran praktis (misalnya, penurunan kunci dompet). Di antara ketiganya, skema mana yang benar-benar dapat disebarkan di rantai Bitcoin?
Dimensi Evaluasi
Pemilihan skema tanda tangan untuk Bitcoin memiliki kendala tersendiri. Evaluasi ini berfokus pada empat standar inti:
- Biaya On-Chain: Salah satu indikator terpenting adalah ukuran total kunci publik dan tanda tangan. Saat output dibelanjakan, kunci publik dan tanda tangan dicatat di rantai, dan node penuh perlu mengunduh dan menyimpan setiap byte. Biaya verifikasi juga krusial: setiap tanda tangan harus diverifikasi oleh seluruh node jaringan, kecepatan verifikasi yang lambat akan membebani seluruh jaringan.
- Kompleksitas Implementasi: Kemampuan untuk mengimplementasikan skema dengan aman sangat penting. Jika desain memerlukan operasi floating-point atau sampling Gaussian yang presisi, kesalahan implementasi atau serangan saluran samping seperti analisis waktu dapat membocorkan kunci pribadi. Untuk migrasi yang mulus, kompleksitas implementasi adalah faktor yang tidak dapat diabaikan.
- Risiko Penyebaran: Integrasi praktis Bitcoin juga akan menghadapi berbagai hambatan nyata: pilihan fungsi hash pada tingkat konsensus (kebanyakan kandidat menggunakan SHAKE, Bitcoin menggunakan SHA‐256), kemampuan reproduksi hasil tanda tangan lintas platform, dan apakah program tanda tangan sesuai dengan batasan memori dompet perangkat keras.
- Potensi Pengembangan: Sebagian besar dompet Bitcoin menggunakan mekanisme penurunan deterministik hierarkis BIP‐32: melalui satu kunci publik induk, tanpa menyentuh kunci pribadi, dapat diturunkan tak terbatas kunci publik anak. Skema tanda tangan pasca-kuantum yang terstandarisasi saat ini tidak mendukung kemampuan ini secara native, oleh karena itu kami meneliti biaya untuk melengkapinya; kami juga memeriksa berbagai varian skema non-standar yang mungkin membawa lebih banyak manfaat.
Tingkat Keamanan Apa yang Harus Dipilih?
Sebelum membandingkan ukuran, pertama-tama perlu menentukan tingkat keamanan target. Pilihan ini tidak sesederhana kelihatannya. NIST membagi tingkat keamanan menjadi level 1‐5; semakin tinggi levelnya, semakin kuat keamanannya, tetapi ukuran kunci dan tanda tangan yang sesuai juga akan lebih besar.
Kami percaya Bitcoin setidaknya harus menggunakan standar keamanan Level 3. Output Bitcoin mungkin tidak dibelanjakan selama beberapa dekade. Jika kemajuan dalam kriptanalisis menyebabkan tingkat keamanan efektif skema menurun, aset akan dikunci dengan kunci yang melemah, terekspos risiko dalam jangka panjang. Asumsi kriptografi lattice telah melewati kriptanalisis publik selama hampir tiga puluh tahun, lebih lama dari riset kurva elips saat diadopsi Bitcoin. Namun, struktur aljabar lattice yang kompleks masih memiliki banyak celah yang dapat dieksploitasi oleh serangan di masa depan. Kita tidak boleh mempertaruhkan semua keamanan masa depan yang jauh di atasnya.
Produk-produk utama juga membuat penilaian yang sama. Protokol PQ3 iMessage Apple langsung mengabaikan parameter lattice Level 1, menggunakan parameter Level 3 dan 5 sepanjang waktu; Cloudflare dalam penyebaran TLS pasca-kuantum menggunakan ML‐KEM‐768 (Level 3), menyatakan bahwa meskipun Level 1 tampak aman saat ini, perlu ada margin keamanan untuk kriptanalisis beberapa dekade ke depan. Rentang waktu keamanan Bitcoin bahkan lebih panjang dari keduanya.
Meningkatkan tingkat keamanan memerlukan pengorbanan. Sebagai contoh, meningkatkan Dilithium dari Level 2 ke Level 3 akan menambah ukuran total sekitar 1,5 kilobyte. Laporan membandingkan seluruh set parameter di semua tingkat keamanan, pembaca dapat menimbang sendiri. Nasib Hawk membuktikan bahwa pertimbangan keamanan yang konservatif bukanlah sekadar teori.
Detail Kandidat Skema
Dilithium: Skema dengan Desain Sederhana
Dilithium distandarisasi oleh NIST sebagai ML‐DSA dalam standar FIPS 204. Ini memigrasikan paradigma tanda tangan Schnorr (komitmen-tantangan-respons) ke aritmatika lattice modular.
Fitur terbesarnya adalah kesederhanaan. Semua operasi Dilithium adalah operasi bilangan bulat: operasi ring, perkalian matriks-vektor, hashing, pembulatan, tanpa operasi floating-point, juga tidak memerlukan sampling Gaussian diskrit. Lebih mudah menulis implementasi yang aman dan waktu-konstan. Ini juga kandidat yang paling banyak diadopsi, telah terintegrasi ke dalam OpenSSL, BoringSSL, AWS‐LC, dan Apple CryptoKit.
Pengorbanannya adalah ukurannya yang relatif besar. ML‐DSA‐65 Level 3 aman, kunci publik 1952 byte, tanda tangan 3309 byte, total 5261 byte, sekitar 55 kali ukuran total kunci pribadi/publik dan tanda tangan native Bitcoin, menjadikannya yang terbesar di antara tiga skema dengan tingkat keamanan yang sama.
Satu hal paling berharga dari Dilithium untuk Bitcoin: Ini adalah satu-satunya dari ketiganya yang mendekati implementasi penurunan kunci gaya BIP‐32. Konstruksi kunci yang dapat diacak ulang, DilithiumRK, dapat menghasilkan kunci anak dari kunci induk hanya dengan informasi publik. Laporan menganalisis tiga varian, termasuk DilithiumRKS yang kami usulkan, di mana logika penurunan sepenuhnya berada di dalam perangkat lunak dompet, rantai hanya memerlukan verifier standar untuk menangani tanda tangan ML‐DSA biasa. Namun, ketiganya belum mencapai standar produksi: dua varian memerlukan modifikasi verifier, DilithiumRKS sendiri masih kekurangan bukti keaslian lengkap; semua skema bergantung pada matriks yang dibagikan secara global, yang meskipun aman secara formal di bawah asumsi Module‐LWE, mengikat keamanan semua kunci ke instance yang sama. Kami percaya saat ini penurunan kunci publik berbasis Dilithium hanyalah proof-of-concept dan tidak dapat disebarkan secara praktis.
Falcon: Skema dengan Ukuran Kompak
Falcon dipilih oleh NIST, nama standarisasinya adalah FN‐DSA. Dari ketiganya, ini yang paling kompak. Falcon‐512 Level 1 aman, kunci publik ditambah tanda tangan total 1563 byte; Falcon‐1024 Level 5 aman total 3073 byte. Falcon‐1024 dengan margin keamanan lebih tinggi, ukurannya bahkan lebih kecil dari Dilithium Level 3.
Falcon menggunakan pendekatan berbeda dari Dilithium: mode hash-and-sign berbasis lattice NTRU. Kunci pribadi penandatangan adalah basis pendek dari lattice; pesan di-hash ke sebuah titik dalam ruang, penandatangan menggunakan basis pendek untuk menemukan vektor dalam lattice yang sangat dekat dengan titik tersebut. Titik dan vektor tetangga ini bersama-sama membentuk tanda tangan; verifikasi hanya memeriksa bahwa vektor termasuk dalam lattice tersebut dan jaraknya cukup dekat. Kesulitan implementasinya adalah menemukan vektor tanpa membocorkan informasi basis. Skema awal GGH, NTRUSign langsung mengambil titik lattice terdekat, setiap tanda tangan membocorkan sebagian informasi geometri. Falcon menggunakan kerangka GPV, mengambil sampel vektor tetangga dari distribusi Gaussian, yang secara terbukti membuat output sampling independen dari basis, menghilangkan risiko kebocoran, tetapi kesulitan implementasi sampler meningkat drastis.
Sampler adalah kelemahan teknis Falcon. Ia beroperasi di domain Fourier kompleks dan memerlukan komputasi floating-point. Prosesor, compiler, dan opsi optimasi kompilasi yang berbeda akan menghasilkan output floating-point yang tidak konsisten. Ini bukan hanya masalah kompatibilitas, tetapi juga risiko keamanan: bukti keamanan GPV mengharuskan penandatangan tidak pernah menghasilkan dua set vektor pendek berbeda untuk digest yang sama; begitu tanda tangan menjadi deterministik, perbedaan pembulatan floating-point antar platform akan merusak kondisi ini. Ada solusi yang layak: Falcon deterministik dapat mensimulasikan integer sebagai pengganti floating-point perangkat keras, menghasilkan tanda tangan yang persis sama di semua platform. Pengorbanannya adalah kecepatan tanda tangan turun sekitar 15 kali, kecepatan pembuatan kunci turun sekitar 2 kali.
Yang penting, bagian verifikasi tidak terpengaruh: Verifikasi Falcon sepenuhnya operasi integer, hasil deterministik, dan juga merupakan kandidat dengan kecepatan verifikasi tercepat. Karakteristik asimetris ini sangat ramah untuk Bitcoin: penandatanganan dilakukan oleh dompet sekali saat membelanjakan transaksi, sementara setiap tanda tangan harus diverifikasi oleh seluruh node penuh jaringan. Penandatanganan 15 kali lebih lambat merupakan biaya frekuensi rendah, dan sebagai gantinya mendapatkan kemampuan reproduksi lintas platform dan operasi integer, menurut kami adalah pertukaran yang masuk akal. Oleh karena itu, masalah floating-point adalah hambatan yang dapat diatasi dengan solusi teknis, bukan cacat fatal.
Dua catatan: Karena kendala struktural, Falcon tidak memiliki parameter Level 3, hanya dapat memilih Level 1 atau Level 5. Berdasarkan pertimbangan margin keamanan, kami merekomendasikan Falcon‐1024. Kedua, penandatanganan mengonsumsi banyak memori: sampler parameter set 1024 bergantung pada pohon pra-komputasi, memakan sekitar 90 kilobyte memori. Dompet perangkat keras dapat membangun kembali pohon ini secara dinamis cabang per cabang, mengurangi penggunaan memori hingga 16 kilobyte, tetapi waktu penandatanganan akan berlipat ganda. Penandatanganan yang lebih lambat pada perangkat keras adalah biaya nyata, tetapi masih dapat diterima.
Hawk: Skema yang Dinyatakan Gagal
Tujuan Hawk adalah menggabungkan keunggulan dua skema lainnya: Tanda tangan Hawk‐512 hanya 555 byte, lebih kecil dari Falcon; sisi penandatanganan sepenuhnya operasi integer, penggunaan memori minimum hanya 6 kilobyte. Ini juga satu-satunya kandidat berbasis lattice yang tersisa di babak ketiga kompetisi tanda tangan tambahan NIST, laporan membahas skema ini secara panjang lebar.
Pengorbanannya terletak pada asumsi keamanan. Ia tidak menggunakan masalah NTRU atau SIS yang telah diuji kriptanalisis selama beberapa dekade, melainkan bergantung pada masalah isomorfisme lattice dan asumsi one‐more‐SVP, yang memiliki sejarah penelitian yang relatif lebih singkat.
Tepat sebelum laporan ini diselesaikan, Straznickas dan Weis dari Anthropic menemukan cacat struktural dalam konstruksi lattice Hawk: dimensi masalah SVP yang sebenarnya diperlukan untuk pemulihan kunci hanya setengah dari yang dibayangkan oleh perancang. Tingkat keamanan pemulihan kunci dari set parameter kandidat sangat melemah. Para peneliti menyelesaikan serangan pemulihan kunci end-to-end lengkap terhadap parameter tantangan HAWK‐256 yang digunakan untuk kriptanalisis; meskipun diserang, proposal formal HAWK‐512 dan HAWK‐1024 tetap tidak dapat dibobol secara realistis. Tim Hawk mengonfirmasi serangan itu efektif dan menarik skema dari proses NIST; tim menyatakan bahwa jika memperbaiki kerentanan dengan menggandakan parameter, keunggulan ukuran yang menjadi kebanggaan Hawk akan hilang sama sekali.
Laporan tetap mempertahankan bagian tentang Hawk karena serangan ini menargetkan properti aljabar domain bilangan tertentu, tidak sepenuhnya menyangkal paradigma desain ini. Apakah desain ulang dapat menghindari kerentanan masih belum pasti. Peristiwa Hawk juga secara langsung membenarkan alasan kami mempertahankan margin keamanan yang konservatif: sebuah skema, bahkan dengan ukuran, kecepatan, dan telah melalui beberapa babak standardisasi, dapat mengalami penurunan drastis dalam tingkat keamanan yang diperkirakan oleh satu makalah.
Tabel Perbandingan Skema
Tabel di atas mencakup semua skema (termasuk SPHINCS+) sebagai tanda tangan stateless: penandatangan tidak perlu mencatat tanda tangan sebelumnya. Tanda tangan berbasis hash stateful seperti XMSS dapat mencapai ukuran tanda tangan lebih kecil tetapi memerlukan pemeliharaan status penandatanganan; lihatlaporan khusus tanda tangan berbasis hashuntuk perbandingan.
Banyak Kendala dalam Implementasi Praktis
Falcon tidak memiliki skema penurunan kunci yang dapat digunakan. Satu-satunya skema penurunan Falcon gaya BIP‐32 yang tersedia secara publik saat ini melakukan re-randomisasi pada basis kunci pribadi, batas atas norma tanda tangan membengkak drastis, dan tanda tangan on-chain membengkak menjadi sekitar 23,7 kilobyte. Selain itu, parameter skema ini tidak memenuhi kondisi keamanannya sendiri, dan jika diperbaiki, ukurannya akan semakin meledak. Saat ini tidak ada implementasi penurunan kunci publik Falcon yang layak, dan ini adalah masalah terbuka yang paling berharga yang diajukan dalam laporan.
Standar Falcon belum final. Meskipun NIST telah memilih Falcon, draf FN‐DSA belum dirilis secara resmi. Setelah standardisasi selesai, barulah akan muncul implementasi yang diaudit, vektor uji, dan dukungan tingkat perangkat keras. Adopsi luas dapat mengurangi risiko dan kesulitan integrasi pada lapisan konsensus Bitcoin. Kami menyarankan untuk menunggu hingga FN‐DSA dirilis secara resmi, sebelum itu Falcon masih dalam status berubah.
Varian Falcon‐WS: Varian ini melonggarkan parameter internal, mengkompensasinya dengan rejection sampling, ukuran total Level 1 dikompresi menjadi 1114 byte, Level 5 menjadi 2387 byte, lebih kecil dari Falcon versi asli. Arah ini memiliki nilai penelitian, tetapi tidak akan dimasukkan dalam standar resmi, memerlukan lebih banyak validasi kriptanalisis. Penelitian telah menemukan celah dalam bukti unforgeability kuat dari skema turunannya (unforgeability biasa tidak terpengaruh).
Akankah muncul skema yang lebih baik di masa depan? Selain skema di atas, seri Fiat‐Shamir berasal dari BLISS 2013, hasil terbaru yang diusulkan Gärtner di konferensi CRYPTO 2025, berdasarkan asumsi matang, ukuran di atas kertas dapat menyamai Falcon. Akar kesulitan implementasi praktis seri ini adalah masalah keamanan implementasi: BLISS pernah dibobol melalui serangan saluran samping karena sampling Gaussian non-waktu-konstan; skema selanjutnya belum sepenuhnya menyelesaikan masalah ini, hasil terbaru juga menunjukkan kesulitan perlindungan yang lebih tinggi pada tahap sampling. Sebelum masalah ini diselesaikan, skema semacam ini hanya menarik secara teoritis dan tidak cocok untuk penyebaran.
Tanda tangan berbasis lattice dan tanda tangan berbasis hash dapat saling melengkapi. Tanda tangan berbasis lattice dapat menjadi komponen dalam skema hybrid. Misalnya, dalam SHRINCS, jalur pemulihan stateless saat ini menggunakan tanda tangan SPHINCS+ berukuran beberapa KB; menggantinya dengan tanda tangan Falcon (atau Falcon‐WS) menghasilkan ukuran lebih kecil, verifikasi lebih cepat, biaya jalur pemulihan frekuensi rendah berkurang drastis, dan jalur penggunaan sehari-hari tidak terpengaruh.
Kesimpulan Penelitian
Urutan keunggulan dan kekurangan kandidat berbasis lattice sangat jelas: Hawk keluar dari persaingan setelah diserang tim Anthropic; Dilithium memiliki tingkat kesulitan implementasi terendah dan satu-satunya yang memiliki dasar penelitian terkait penurunan kunci, tetapi ukurannya tidak ramah untuk biaya on-chain Bitcoin; Falcon menggabungkan ukuran kompak, verifikasi cepat, dan asumsi keamanan matang; kelemahan utamanya — operasi floating-point di sisi penandatanganan — sudah memiliki solusi teknis yang layak. Jika sekarang harus memilih skema tanda tangan berbasis lattice untuk Bitcoin, kami akan memilih Falcon‐1024.
Untuk saat ini, pandangan kami konsisten dengan laporan tanda tangan berbasis hash: jalur konservatif jangka pendek tetap adalah tanda tangan berbasis hash, asumsi keamanan paling matang, risiko terendah, cocok sebagai skema transisi. Setelah FN‐DSA difinalisasi secara resmi, memiliki spesifikasi stabil, basis kode yang diaudit, dan dukungan dompet perangkat keras, Falcon akan memberikan peningkatan signifikan dibandingkan tanda tangan berbasis hash murni; penyebaran hybrid juga dapat digunakan, memungkinkan kedua sistem tanda tangan saling melengkapi.
