Upgrade to Pro — share decks privately, control downloads, hide ads and more …

ランポート署名

 ランポート署名

GBECの解説動画の資料です。
https://goblockchain.network/2024/07/lamport-signature/

shigeyuki azuchi

July 10, 2024
Tweet

More Decks by shigeyuki azuchi

Other Decks in Technology

Transcript

  1. ,
 2 ランポート署名
 署名対象のメッセージダイジェストのデータ長を k bitとする
 
 • 鍵生成
 ◦

    秘密鍵の生成
 2×k個の乱数を生成する(各乱数の長さも k bit)
 
 ◦ 公開鍵の生成
 2×k個の秘密鍵の各値をハッシュしたのが公開鍵( z = H(y))
 
 
 k = 256 bit (32 byte)の場合、公開鍵のサイズは 2×256×256bit = 16KB 
 ※ 鍵長が現在のECDSAやSchnorrと比べて巨大になる 
 y 1,0
 y 2,0
 y 3,0
 y k,0
 …
 y 1,1
 y 2,1
 y 3,1
 y k,1
 …
 ,
 z 1,0
 z 2,0
 z 3,0
 z k,0
 …
 z 1,1
 z 2,1
 z 3,1
 z k,1
 …

  2. 3 ランポート署名
 • 署名の生成
 a. 署名対象のメッセージのハッシュ値 mを計算(k bit)
 b. 計算したメッセージダイジェストmをバイナリ展開


                 (各  は、 0 or 1)
 c. 各m i に対応する秘密鍵y i,? をピックアップする
 例:        , 
 sig(m 1 , …, m k ) = (y 1, m1 , y 2, m2 , …, y k, mk ) 
 
 メッセージダイジェストの各bit値に対応するハッシュロックをアンロックする 
 m 1
 m 2 
 m 3 
 m k 
 …
 m i 
 m 1 = 0
 y 1,0
 m 1 = 1
 y 1,1

  3. 4 ランポート署名
 • 署名の検証
 a. 署名対象のメッセージのハッシュ値 mを計算
 b. 計算したメッセージダイジェストをバイナリ展開 


                 
 c. sig(m 1 , …, m k ) = (y 1, m1 , y 2, m2 , …, y k, mk ) に対応する公開鍵をピックアップし、 
 各署名値をハッシュした値と等しいかチェック 
 
 
 
 
 署名により秘密鍵の一部が明らかになるため、使えるのは一度きり 
 
 m 1
 m 2 
 m 3 
 m k 
 …
 y 1,m1
 …
 z 1,m1
 z 2,m2
 z 3,m3
 z k,mk
 y 2,m2
 y 3,m3
 y k,mk
 …
 ハッシュ

  4. 5 Bitcoinでランポート署名?
 単純に実装すると、
 
 
 
 
 
 
 


    最初の0はメッセージダイジェストを表す変数で、各行は、 
 • 提供されたi個めの署名(秘密鍵)を2つの公開鍵( z i,1 , z i,0 )と比較し、y i, 1 であれば
 IFブロック内の1 << i を変数に加算
 最終的に変数の値をメッセージダイジェストと比較 
 
 ※ Bitcoin Scriptは32bit整数しか扱えないため、4バイト単位で評価した結果をOP_CATで連結する必要がある。
  またTxサイズ的な課題あり。
 0
 SWAP SHA256 DUP <z 1,1 > EQUAL IF DROP <1> ADD ELSE <z 1, 0 > EQUALVERIFY ENDIF
 SWAP SHA256 DUP <z 2,1 > EQUAL IF DROP <1 << 1> ADD ELSE <z 2, 0 > EQUALVERIFY ENDIF
 SWAP SHA256 DUP <z 3,1 > EQUAL IF DROP <1 << 2> ADD ELSE <z 3, 0 > EQUALVERIFY ENDIF
 …
 SWAP SHA256 DUP <z k,1 > EQUAL IF DROP <1 << k> ADD ELSE <z k, 0 > EQUALVERIFY ENDIF

  5. 6 Bitcoinでランポート署名?
 OP_CATが不要な方式:メッセージではなく、ECDSAの署名サイズに対するランポート署名 
 https://groups.google.com/g/bitcoindev/c/mR53go5gHIk 
 
 
 
 


    署名者は、複数の鍵分の↑のスクリプトセットを使用し 
 • 署名に使用するPublic nonce rに短い固定値(21 byte)を採用する (例:k = 1/2) 
 • スクリプトセットの内いくつかの署名長が1 byte 短くなるような署名を作成する 
 攻撃者が1バイト短い署名を作成するためには、Txのハッシュによって決まるs値を短くする必要があり、所有者 が計算した署名を有効にしたままその計算をするのにコスト(2 84)がかかるようにする。 
 https://techmedia-think.hatenablog.com/entry/2024/06/05/180436 
 DUP <公開鍵> CHECKSIGVERIFY SIZE < 59> EQUAL
 IF
 # サイズが<59>バイトと等しい場合 
 SHA256 <ダイジェストx> CHECKEQUALVERIFY 
 ELSE
 # サイズが<59>バイトと等しくない場合 
 SHA256 <ダイジェストy> CHECKEQUALVERIFY 
 ENDIF
 
 ※ 前提
 • ECDSA署名(r, s)は長さが可変 
 • DERエンコードされており上位の0x00は省略される