🍚 blog

Beam Chainのためのポスト量子署名「XMSS」のSNARKによる署名集約

JP
cryptography

XMSS (Extended Merkle-tree Signature Scheme) の仕組み

ワンタイム署名(OTS)とマークルツリーを用いる

複数個の秘密鍵をあらかじめ用意しておき、それらのハッシュを葉としたマークルツリーのルートハッシュを公開鍵とすることで、未使用の秘密鍵で署名できる

Sign [1]

input: rng, sk, epoch, message

  1. skをもとにMerkle Treeの認証パス path を取得する
  2. 乱数rhoを計算し、sk, message, rho, epochをWinternitz/TargetSumのどちらかでエンコーディングする
    1. エンコードには何回か挑戦し、成功したときに使用した乱数を rho とする
  3. sk, epochをもとに公開鍵ハッシュチェーン hashes の計算を行う
  4. (path, rho, hashes) を署名sigとして出力

Verify [1]

input: pk, epoch, message, sig

  1. pk, message, sig.rho, epochからエンコーディング x を計算し、エンコードが正しいことを検証する
  2. sig.hashesから、ワンタイム公開鍵を復元する
  3. ワンタイム公開鍵がmerkle treeの正しい葉であることを検証する

Encode (TargetSum) [2]

  1. message, rho, epochに基づいてメッセージをチャンクに分割する
  2. 分割したチャンクの総和を計算する
  3. 総和がTARGET_SUMとマッチしたらok

SNARKによる署名集約

Verifyのうち2と3はマークルツリーを並列につなぎ合わせることでかんたんに達成できる

1は以下のエンコーディング計算xにパスする必要がある

        // first get back the codeword and make sure
        // encoding succeeded with the given randomness.
        let x = IE::encode(&pk.parameter.into(), message, &sig.rho, epoch);
        if x.is_err() {
            return false;
        }
        let x = x.unwrap();

My署名集約アイデア:

input: (rho1, … , rhot), (pk1, … , pkt), message, epoch

  1. rho_agg = rho1 + rho2 + … + rhot + rho_new
    1. encodingを満たすrho_newをトライして計算
    2. ↑このrho_newの探索がどれだけ大変かにかかっている
  2. pk_agg = pk1 + pk2 + … + pkt
  3. そうすれば(rho_agg, pk, message, epoch)が通常のXMSS署名検証にパスする

SNARK回路の内容:

witness: rho_new, XMSS Signatures

public inputs: (pk1, …, pkt), epoch, message

  1. rho_agg, pk_aggを計算
  2. TargetSumエンコーディングを計算
  3. TargetSumエンコーディングを検証
  4. merkleTreeを再構築して検証

Reference

  1. https://github.com/b-wagn/hash-sig/blob/main/src/signature/generalized_xmss.rs
  2. https://github.com/b-wagn/hash-sig/blob/main/src/inc_encoding/target_sum.rs
  3. https://www.youtube.com/watch?v=N7O4qpt6FW0
  4. https://docs.google.com/presentation/d/11KWlbK-MffAYx4kKoZfFecGNPs-O2q-1WAa7ewbfsRw/edit#slide=id.p
← Go home