Penulisan: Tim Blockstream
Kompilasi: Saoirse, Foresight News
Blockstream Research telah merilis laporan penelitian lengkap tentang tanda tangan berbasis lattice untuk Bitcoin. Artikel ini merangkum isi penelitian, temuan inti, dan rekomendasi terkait. Laporan lengkapnya dapat diakses dengan mengklik tautan.
Tanda tangan digital adalah mekanisme inti yang mengotorisasi transaksi Bitcoin, saat ini fungsi ini dijalankan oleh tanda tangan Schnorr dan ECDSA yang biayanya sangat rendah. Pada tahun 1994, Shor membuktikan bahwa komputer kuantum yang cukup kuat dapat memecahkan kedua jenis tanda tangan ini. Meskipun kapan mesin semacam itu akan tersedia masih diperdebatkan secara luas, kita perlu merancang rencana penerapan tanda tangan pasca-kuantum yang layak sebelum masalah itu benar-benar muncul.
Skema tanda tangan berbasis lattice adalah kandidat populer untuk menggantikan tanda tangan yang ada. Kriptografi lattice telah dipelajari selama lebih dari satu abad, dan penerapannya dalam kriptografi juga telah berkembang selama hampir tiga dekade. Dalam sistem kriptografi pasca-kuantum, tanda tangan berbasis lattice memiliki banyak keunggulan: total ukuran kunci publik dan tanda tangan dapat mencapai kurang dari 1,6 kilobyte, sementara struktur aljabarnya berpotensi mendukung tanda tangan multi, tanda tangan ambang batas, dan bukti ringkas di masa depan.
Laporan ini meneliti tiga skema: Dilithium, Falcon, dan Hawk. Untuk pembaca yang belum akrab dengan kriptografi lattice, kami menjelaskan konsep desain setiap skema, memperkenalkan algoritma secara lengkap, dan menganalisis dari dimensi keamanan, kinerja, dan penerapan praktis (misalnya, penurunan kunci dompet). Di antara ketiganya, skema mana yang benar-benar dapat diterapkan di blockchain Bitcoin?
Dimensi Evaluasi
Pemilihan skema tanda tangan untuk Bitcoin memiliki kendala tersendiri. Evaluasi kali ini berfokus pada empat standar inti:
- Biaya On-Chain: Salah satu metrik terpenting adalah total ukuran kunci publik dan tanda tangan. Saat output dibelanjakan, kunci publik dan tanda tangan akan direkam di chain, dan semua node perlu mengunduh serta menyimpan setiap byte. Biaya verifikasi juga kritis: setiap tanda tangan perlu diverifikasi oleh semua node di jaringan, dan kecepatan verifikasi yang lambat akan membebani seluruh jaringan.
- Kompleksitas Implementasi: Kemampuan untuk mengimplementasikan skema dengan aman sangat penting. Jika desain memerlukan komputasi floating-point atau pengambilan sampel Gaussian yang presisi, kesalahan implementasi atau serangan saluran samping seperti analisis waktu dapat membocorkan kunci. Kompleksitas implementasi adalah faktor yang tidak dapat diabaikan untuk migrasi yang mulus.
- Risiko Penerapan: Integrasi praktis Bitcoin juga akan menghadapi berbagai hambatan dunia nyata: pemilihan fungsi hash pada tingkat konsensus (kebanyakan kandidat menggunakan SHAKE, Bitcoin menggunakan SHA‐256), reproduktifitas hasil tanda tangan lintas platform, dan apakah program tanda tangan sesuai dengan batasan memori dompet keras.
- Potensi Pengembangan: Sebagian besar dompet Bitcoin menggunakan mekanisme deterministik hierarkis BIP‐32: dari satu kunci publik induk, dapat diturunkan banyak kunci publik turunan tanpa perlu menyentuh kunci privat. Skema tanda tangan pasca-kuantum yang terstandarisasi saat ini tidak secara native mendukung fitur ini, jadi kami meneliti biaya yang diperlukan untuk menambahkannya; juga memeriksa varian skema non-standar yang mungkin memberikan manfaat lebih.
Tingkat Keamanan Apa yang Harus Dipilih?
Sebelum membandingkan ukuran, kita harus menentukan tingkat keamanan target. Pilihan ini tidak sesederhana kelihatannya. NIST membagi tingkat keamanan menjadi level 1-5; semakin tinggi level, semakin kuat keamanannya, tetapi ukuran kunci dan tanda tangan yang sesuai juga akan lebih besar.
Kami berpendapat Bitcoin setidaknya harus mengadopsi standar keamanan level 3. Output Bitcoin mungkin tidak dibelanjakan selama beberapa dekade, jika kemajuan kriptanalisis menyebabkan tingkat keamanan praktis skema menurun, aset akan terkunci oleh kunci yang melemah, terpapar risiko dalam jangka panjang. Asumsi kriptografi lattice telah menghadapi kriptanalisis publik selama hampir tiga puluh tahun, lebih lama dari penelitian kriptografi kurva elips saat Bitcoin mengadopsinya. Namun, struktur aljabar kompleks dari lattice masih memiliki banyak celah yang dapat dieksploitasi oleh serangan di masa depan, kita tidak boleh mempertaruhkan semua keamanan di 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 sepenuhnya; Cloudflare menggunakan ML‐KEM‐768 (level 3) dalam penerapan TLS pasca-kuantum, menyatakan bahwa meskipun level 1 tampak aman saat ini, ruang aman perlu disediakan untuk kriptanalisis puluhan tahun ke depan. Dan rentang waktu keamanan Bitcoin bahkan lebih panjang dari kedua contoh di atas.
Meningkatkan tingkat keamanan memerlukan pengorbanan. Sebagai contoh, meningkatkan Dilithium dari level 2 ke level 3 akan menambah total ukuran sekitar 1,5 kilobyte. Laporan membandingkan semua set parameter di setiap tingkat keamanan, pembaca dapat mempertimbangkan sendiri. Pengalaman Hawk membuktikan bahwa pertimbangan keamanan konservatif bukan hanya teori.
Penjelasan Rinci Kandidat Skema
Dilithium: Skema dengan Desain Sederhana
Dilithium distandarisasi oleh NIST sebagai ML‐DSA dalam standar FIPS 204. Skema ini memindahkan paradigma tanda tangan Schnorr (commit‐challenge‐response) ke aritmatika lattice modular.
Ciri terbesarnya adalah kesederhanaan. Semua komputasi Dilithium adalah operasi bilangan bulat: operasi ring, perkalian matriks-vektor, hash, pembulatan, tanpa operasi floating-point, juga tidak perlu pengambilan sampel Gaussian diskrit. Lebih mudah menulis implementasi yang aman dan waktu konstan. Ini juga kandidat yang paling luas diadopsi, telah terintegrasi ke OpenSSL, BoringSSL, AWS‐LC, dan Apple CryptoKit.
Harganya adalah volume yang relatif besar. ML‐DSA‐65 level 3, kunci publik 1952 byte, tanda tangan 3309 byte, total 5261 byte, sekitar 55 kali ukuran total kunci publik+privat dan tanda tangan native Bitcoin. Ini adalah yang terbesar di antara tiga skema dengan tingkat keamanan yang sama.
Salah satu hal paling berharga dari Dilithium untuk Bitcoin: ini adalah satu-satunya dari ketiganya yang mendekati implementasi penurunan kunci ala BIP‐32. Konstruksi kunci yang dapat diacak ulang, DilithiumRK, dapat menghasilkan kunci turunan dari kunci induk hanya dengan informasi publik. Laporan menganalisis tiga varian, termasuk DilithiumRKS yang kami usulkan, di mana logika turunan ditempatkan sepenuhnya di dalam perangkat lunak dompet, dan di chain hanya membutuhkan verifier standar untuk memproses tanda tangan ML‐DSA biasa. Namun, ketiganya belum mencapai standar produksi: dua varian perlu memodifikasi verifier, DilithiumRKS sendiri masih kekurangan bukti keaslian lengkap; semua skema bergantung pada matriks yang dibagikan di seluruh jaringan, meskipun secara formal aman berdasarkan asumsi Module‐LWE, ini mengikat keamanan semua kunci ke instans yang sama. Kami berpendapat bahwa saat ini, penurunan kunci publik berbasis Dilithium hanya merupakan bukti konsep, belum dapat diterapkan.
Falcon: Skema dengan Volume Ringkas
Falcon dipilih oleh NIST, nama standarnya adalah FN‐DSA, dari ketiganya ini adalah yang paling ringkas. Falcon‐512 level 1 memiliki total gabungan kunci publik dan tanda tangan 1563 byte; Falcon‐1024 level 5 total 3073 byte. Falcon‐1024 dengan margin keamanan yang lebih tinggi, volumenya bahkan lebih kecil dari Dilithium level 3.
Falcon menggunakan pendekatan berbeda dari Dilithium: pola hash‐and‐sign berdasarkan lattice NTRU. Kunci privat penanda adalah basis pendek dari lattice; pesan di-hash ke sebuah titik di ruang, penanda menggunakan basis pendek untuk menemukan vektor di lattice yang sangat dekat dengan titik tersebut. Titik dan vektor terdekat ini bersama-sama membentuk tanda tangan; verifikasi hanya memeriksa apakah vektor termasuk dalam lattice tersebut, dan apakah jaraknya cukup dekat. Kesulitan implementasinya terletak pada menemukan vektor tanpa membocorkan informasi basis. Skema awal seperti GGH, NTRUSign langsung mengambil titik lattice terdekat, setiap penandatanganan membocorkan sebagian informasi geometri. Falcon menggunakan kerangka GPV, mengambil sampel vektor terdekat dari distribusi Gaussian, yang dapat dibuktikan bahwa output sampel independen dari basis, menghilangkan risiko kebocoran, tetapi kesulitan implementasi sampler meningkat drastis.
Sampler adalah kelemahan teknis Falcon. Ia beroperasi di domain Fourier kompleks, memerlukan komputasi floating-point. Prosesor, compiler, opsi optimasi kompilasi yang berbeda, semuanya dapat menyebabkan hasil floating-point tidak konsisten. Ini bukan hanya masalah kompatibilitas, tetapi juga masalah keamanan: bukti keamanan GPV mengharuskan bahwa untuk digest yang sama, penanda tidak pernah menghasilkan dua set vektor pendek yang berbeda; begitu tanda tangan menjadi deterministik, perbedaan pembulatan floating-point yang disebabkan oleh platform akan merusak kondisi ini. Ada solusi yang memungkinkan: Falcon deterministik dapat menggunakan simulasi integer sebagai pengganti floating-point perangkat keras, menghasilkan tanda tangan yang sepenuhnya konsisten di semua platform. Harganya adalah kecepatan penandatanganan turun sekitar 15 kali, dan kecepatan pembangkitan kunci turun sekitar 2 kali.
Yang penting, proses verifikasi tidak terpengaruh: Verifikasi Falcon sepenuhnya operasi integer, hasil deterministik, dan juga yang tercepat di antara kandidat. Karakteristik asimetris ini sangat ramah untuk Bitcoin: penandatanganan dilakukan oleh dompet sekali saat membelanjakan transaksi, sementara setiap tanda tangan harus diverifikasi oleh semua node penuh di jaringan. Penandatanganan yang 15 kali lebih lambat adalah biaya frekuensi rendah, yang ditukar dengan hasil yang dapat direproduksi lintas platform dan operasi integer, menurut kami adalah pertukaran yang masuk akal. Oleh karena itu, masalah floating-point adalah hambatan yang dapat diselesaikan secara teknis, bukan cacat fatal.
Dua hal yang perlu diperhatikan: Karena batasan struktural, Falcon tidak memiliki parameter level 3, hanya dapat memilih level 1 atau 5. Berdasarkan pertimbangan margin keamanan, kami merekomendasikan Falcon‐1024. Kedua, penandatanganan akan mengonsumsi banyak memori: Sampler untuk parameter set 1024 bergantung pada pohon pra-komputasi, memakan sekitar 90 kilobyte memori. Dompet keras dapat membangun kembali pohon ini secara dinamis cabang per cabang, memampatkan penggunaan memori hingga 16 kilobyte, tetapi waktu penandatanganan akan berlipat ganda. Penandatanganan yang lebih lambat di 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 ini menggunakan banyak ruang untuk memperkenalkan skema ini.
Harganya adalah asumsi keamanan. Ia tidak menggunakan masalah NTRU dan SIS yang telah diuji kriptanalisis selama beberapa dekade, tetapi bergantung pada masalah isomorfisme lattice dan asumsi one‐more‐SVP, yang sejarah penelitiannya 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 perlu diselesaikan untuk pemulihan kunci hanya setengah dari yang dibayangkan oleh perancang. Tingkat keamanan pemulihan kunci untuk set parameter kandidat sangat dilemahkan. Peneliti menyelesaikan serangan pemulihan kunci end‐to‐end lengkap terhadap parameter tantangan HAWK‐256 yang digunakan untuk kriptanalisis; meskipun diserang, proposal formal HAWK‐512, HAWK‐1024 tetap tidak dapat diretas secara praktis. Tim Hawk mengonfirmasi serangan tersebut efektif, dan menarik skema dari proses NIST; tim menyatakan bahwa jika memperbaiki kerentanan dengan menggandakan parameter, keunggulan volume yang dibanggakan Hawk akan hilang sepenuhnya.
Laporan tetap mempertahankan bagian terkait Hawk, karena serangan ini menargetkan karakteristik aljabar domain bilangan tertentu, tidak sepenuhnya menyangkal paradigma desain ini. Apakah desain ulang dapat menghindari kerentanan, masih belum pasti. Peristiwa Hawk juga secara langsung mengonfirmasi alasan kami untuk tetap mempertahankan margin keamanan konservatif: sebuah skema, meskipun unggul dalam volume, kecepatan, dan telah menyelesaikan banyak putaran standarisasi, dapat mengalami penurunan signifikan dalam tingkat keamanan yang diperkirakan hanya dengan satu makalah penelitian.
Tabel Perbandingan Skema
Semua skema dalam tabel di atas (termasuk SPHINCS+) adalah tanda tangan tanpa status: penanda tidak perlu mencatat tanda tangan sebelumnya. Tanda tangan berbasis hash berstatus seperti XMSS dapat memiliki ukuran tanda tangan yang lebih kecil, tetapi perlu mempertahankan status penandatanganan; lihat laporan khusus tentang tanda tangan berbasis hash untuk perbandingan.
Masih Banyak Hambatan untuk Implementasi
Falcon kekurangan skema penurunan kunci yang dapat digunakan. Satu-satunya skema penurunan ala BIP‐32 untuk Falcon yang saat ini tersedia secara publik, akan melakukan re-randomisasi pada basis kunci privat, batas atas norma tanda tangan melonjak drastis, dan tanda tangan on-chain membengkak menjadi sekitar 23,7 kilobyte. Selain itu, parameter skema ini tidak memenuhi kondisi keamanannya sendiri, dan jika masalah ini diperbaiki, volume akan meledak lebih jauh. Saat ini tidak ada implementasi penurunan kunci publik Falcon yang layak, ini juga 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 standarisasi selesai, barulah akan membawa implementasi yang diaudit, vektor pengujian, dan dukungan tingkat perangkat keras. Adopsi yang 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, mengandalkan penolakan sampel sebagai kompensasi, total ukuran level 1 dikompresi menjadi 1114 byte, level 5 menjadi 2387 byte, lebih rendah dari Falcon versi asli. Arah ini memiliki nilai penelitian, tetapi tidak akan dimasukkan dalam standar resmi, memerlukan lebih banyak validasi kriptanalisis. Penelitian telah menemukan kelemahan dalam bukti keaslian kuat dari skema turunannya (keaslian biasa tidak terpengaruh).
Apakah akan muncul skema yang lebih baik di masa depan? Selain skema di atas, seri Fiat‐Shamir paling awal berasal dari BLISS tahun 2013, hasil terbaru yang diusulkan oleh Gärtner dalam konferensi CRYPTO 2025, berdasarkan asumsi matang, ukuran di atas kertas dapat menyamai Falcon. Akar kesulitan implementasi teknis seri ini adalah masalah keamanan implementasi: BLISS pernah diretas melalui saluran samping karena pengambilan sampel Gaussian non-waktu konstan; skema berikutnya tidak sepenuhnya menyelesaikan masalah ini, hasil terbaru juga menunjukkan bahwa kesulitan perlindungan pada tahap pengambilan sampel lebih tinggi. Sebelum masalah diselesaikan, skema semacam ini hanya menarik secara teoritis, tidak cocok untuk diterapkan.
Tanda tangan berbasis lattice dan tanda tangan berbasis hash dapat saling melengkapi. Tanda tangan berbasis lattice dapat menjadi komponen dalam skema hibrid. Misalnya, dalam SHRINCS, jalur pemulihan tanpa status saat ini menggunakan tanda tangan SPHINCS+ berukuran beberapa KB; menggantinya dengan tanda tangan Falcon (atau Falcon‐WS) yang lebih kecil dan verifikasi lebih cepat, biaya jalur pemulihan frekuensi rendah turun drastis, jalur penggunaan sehari-hari tidak terpengaruh.
Kesimpulan Penelitian
Urutan keunggulan dan kelemahan kandidat berbasis lattice sangat jelas: Hawk keluar dari persaingan setelah diserang tim Anthropic; Dilithium paling mudah diimplementasikan, juga satu-satunya yang memiliki dasar penelitian terkait penurunan kunci, tetapi volumenya tidak ramah untuk biaya on-chain Bitcoin; Falcon menyeimbangkan volume ringkas, verifikasi cepat, dan asumsi keamanan matang; kelemahan utamanya — komputasi 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 masih merupakan tanda tangan berbasis hash, dengan asumsi keamanan paling matang, risiko terendah, cocok sebagai skema transisi. Setelah FN‐DSA difinalisasi secara resmi, memiliki spesifikasi stabil, basis kode yang diaudit, dukungan dompet keras, Falcon akan memberikan peningkatan signifikan dibandingkan tanda tangan berbasis hash murni; juga dapat menggunakan penerapan hibrid, membiarkan kedua sistem tanda tangan saling melengkapi.
