ECDSA Ambang: Penandatanganan Multipihak

Tanda tangan ECDSA memerlukan perhitungan nilai acak yang hanya digunakan sekali k, titik kurva R = k*G, serta tanda tangan s = k^{-1}(h + r*x) mod n, dengan x sebagai kunci privat dan r sebagai koordinat x dari R. Pembalikan k dan perkalian dengan kunci privat membuat ECDSA secara inheren nonlinear, berbeda dari tanda tangan Schnorr yang responsnya merupakan kombinasi linear sederhana. Nonlinearitas ini membuat pendistribusian perhitungan di antara pihak-pihak sangat menantang.

Protokol GG18 karya Gennaro dan Goldfeder (2018) merupakan konstruksi ECDSA dua pihak dan ambang praktis pertama yang aman tanpa pihak pembagi tepercaya. Gagasan utamanya adalah menggunakan enkripsi homomorfik Paillier untuk melakukan konversi perkalian-ke-penjumlahan (MtA) yang diperlukan dalam perhitungan ECDSA nonlinear. GG18 menyediakan keamanan berbasis simulasi terhadap penyerang statis semi-jujur.

GG20 (Gennaro dan Goldfeder 2020) meningkatkan GG18 dengan membuktikan keamanan terhadap penyerang berbahaya tanpa pengaturan tepercaya. GG20 menambahkan bukti tanpa pengetahuan untuk memastikan setiap pihak mengikuti protokol dengan benar. Bukti-bukti ini mencegah pihak berbahaya memengaruhi nilai sekali pakai atau tanda tangan untuk mendapatkan informasi tentang bagian kunci pihak lain. GG20 menjadi landasan bagi banyak implementasi dompet MPC untuk produksi.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) adalah protokol ECDSA ambang yang paling mutakhir saat ini. Protokol ini mencapai penghentian yang dapat diidentifikasi, artinya jika protokol penandatanganan gagal akibat perilaku berbahaya, protokol dapat mengidentifikasi pihak yang bertanggung jawab. Hal ini sangat penting untuk penerapan di perusahaan yang mengutamakan akuntabilitas. CGGMP21 diimplementasikan dalam pustaka MPC populer, termasuk tss-lib dan multi-party-sig.

Tantangan utama dalam ECDSA ambang adalah menghitung hasil kali bagian rahasia tanpa membukanya. Konversi MtA (multiplikatif ke aditif) mengubah hasil kali a*b dari bagian dua pihak menjadi bagian aditif: pihak 1 memperoleh alpha, pihak 2 memperoleh beta, sedemikian rupa sehingga alpha + beta = a*b. Hal ini dilakukan menggunakan enkripsi Paillier: pihak 1 mengenkripsi a, pihak 2 melakukan perkalian homomorfik dengan b dan menambahkan keacakan, lalu hasilnya didekripsi oleh pihak 1 untuk memperoleh bagian aditif.

Enkripsi Paillier adalah skema enkripsi homomorfik parsial yang mendukung penjumlahan dan perkalian dengan teks biasa. Dengan enkripsi Enc(a), siapa pun dapat menghitung Enc(a*b) untuk b yang diketahui tanpa melakukan dekripsi. Sifat ini memungkinkan protokol MtA: pihak 1 menghasilkan pasangan kunci Paillier dan mengirimkan Enc(k1) serta Enc(x1) (bagian dari nilai sekali pakai dan kunci privat). Pihak 2 menggunakan operasi homomorfik untuk menghitung kontribusinya tanpa mengetahui k1 atau x1.

Penandatanganan ECDSA ambang biasanya melibatkan beberapa putaran komunikasi. Dalam GG20, terdapat tahap prapemrosesan (2 putaran) yang menghitung komitmen atas nilai sekali pakai dan nilai pengaburan acak, serta tahap penandatanganan daring (1 putaran) yang menggabungkan tanda tangan parsial. Prapemrosesan dapat dilakukan sebelum pesan diketahui, sehingga latensi daring berkurang menjadi satu putaran. CGGMP21 mengoptimalkan proses ini lebih lanjut.

Penghentian yang dapat diidentifikasi berarti jika protokol penandatanganan ambang gagal karena suatu pihak mengirim pesan yang formatnya salah atau tidak mengikuti protokol, pihak-pihak yang jujur dapat menentukan secara kriptografis pihak yang berperilaku buruk. Hal ini memerlukan bukti tanpa pengetahuan atas komputasi yang benar pada setiap langkah. Tanpa penghentian yang dapat diidentifikasi, pihak berbahaya dapat menyebabkan penolakan layanan dengan menolak menyelesaikan protokol tanpa dapat diidentifikasi.

EdDSA (tanda tangan berbasis Schnorr atas Ed25519) jauh lebih mudah diterapkan sebagai skema ambang daripada ECDSA karena tanda tangan Schnorr bersifat linear: respons z = r + c*x merupakan jumlah bagian aditif. FROST (Schnorr Ambang yang Fleksibel dan Dioptimalkan untuk Putaran) oleh Komlo dan Goldberg (2020) mencapai penandatanganan Schnorr ambang dalam dua putaran tanpa pengaturan tepercaya. FROST sedang distandardisasi oleh IETF (draf RFC) untuk digunakan dalam protokol yang menjaga privasi dan dompet mata uang kripto.

ECDSA ambang lebih mahal secara komputasi daripada ECDSA satu pihak karena protokol MtA dan bukti tanpa pengetahuan. Penandatanganan dua pihak GG20 memerlukan sekitar 1–2 detik pada perangkat keras modern; penandatanganan ambang dengan n yang lebih besar memerlukan waktu lebih lama karena lebih banyak eksekusi MtA berpasangan. Pengoptimalan CGGMP21 mengurangi waktu ini menjadi ratusan milidetik. Untuk transaksi mata uang kripto yang mementingkan latensi penandatanganan, kinerja ini dapat diterima, tetapi tetap cukup signifikan.

ECDSA ambang telah diterapkan secara luas dalam keuangan institusional. Fireblocks menggunakan ECDSA ambang berbasis GG20 untuk mengamankan volume transaksi lebih dari $4 triliun. Coinbase Prime menggunakan kustodi MPC berbasis tanda tangan ambang. Qredo dan Copper.co menawarkan ECDSA ambang untuk pengelolaan aset institusional. Pustaka Go tss-lib (yang digunakan oleh Binance) dan multi-party-sig (yang digunakan oleh Coinbase) adalah implementasi sumber terbuka utama.

Peran apa yang dimainkan enkripsi homomorfik Paillier dalam ECDSA ambang?

ECDSA ambang memungkinkan t pihak menandatangani tanpa satu pun pihak mengetahui kunci lengkap. Struktur nonlinier ECDSA memerlukan konversi MtA menggunakan enkripsi homomorfik Paillier. GG18 memelopori pendekatan ini, GG20 menambahkan keamanan terhadap pihak berbahaya, dan CGGMP21 menambahkan penghentian yang dapat diidentifikasi. EdDSA/Schnorr lebih mudah diterapkan sebagai skema ambang melalui FROST (2 putaran, tanpa pengaturan tepercaya). Penerapan produksi di Fireblocks dan Coinbase mengamankan aset senilai triliunan.