開発者向け rin

集計・閾値・マルチシグ・マルチシグネチャー

はじめに

ブロックチェーン技術ではすべての取引に署名が必要なため、デジタル署名が中心的な役割を担っています。正確には、デジタル署名はブロックチェーンプロトコルにおいて3つの目的を持っています。

  1. 所有権を証明し、資金を使用する権限を与えるものです。
  2. 否認防止を証明する。つまり、認可の証明が否定できないことを意味する。
  3. トランザクションが変更されていないこと、および変更できないことを証明します。

一人のユーザーがメッセージに対して署名を発行する現在の署名方式は、悪意のあるユーザーが秘密鍵をコントロールした場合に、方式を台無しにする単一障害点を意味するため、潜在的な脅威に悩まされる可能性があります。

上記の問題は、マルチシグネチャ方式または閾値署名のいずれかを導入することで回避することができる。どちらの方式も、マルチパーティプロトコルであり、ファイルの真正性を証明するためにn人中最低m人のユーザの署名を必要とするという意味で、非常によく似ています。しかしながら、両者の間には、わずかではあるが重要な相違点があり、本報告では高い視点から両者の署名方式を比較することを目的とする。

MuSig2やFROSTなど、いくつかの提案がなされ、この分野が活発化している今、ブロックチェーン環境において、共通点や相違点があり、混乱しがちな3つの技術の紹介と比較をする良い機会だと思います。目標は、マルチシグネチャ、閾値署名、集約署名を紹介し、専門用語をできるだけ避けながら、MuSig2とFROSTの初歩的な紹介をすることです。

デジタル署名方式

以下は、ブロックチェーン内の多くの場面で融合・結合する概念であるマルチシグネチャ、閾値署名、集約署名などの混乱を取り除くことが目的の一つであるため、極論になるかもしれませんが、ご了承ください。

マルチシグネチャー

マルチシグネチャの素朴なアプローチでは、n人のユーザーがそれぞれ公開鍵と秘密鍵のペアを持つ。この状況で有効な署名は、n人のユーザーの署名の集合体である。署名の検証には、各署名者の公開鍵を用いて最終的な署名を検証する必要がある。

参加者それぞれに鍵ペアを持たせることで、多署名認証はより多くのスペースを占有することになります。n個の署名の定足数を要求する構成では、n個の署名すべてだけでなく、 n個の公開鍵も含まなければならない。このため、マルチシグネチャーのトランザクションはよりコストがかかり、スペースと処理コストはnに線形に増加する。

一方、個人鍵ペアを持つユーザーは、各プレイヤーが署名の一部を発行する共有秘密鍵を持つ閾値署名で起こることとは逆に、複数の署名処理に並行して参加する機会を持つことができるのです。これらの共有鍵は有効な最終署名を生成するために結合されなければならない。これらの共有鍵は、それ自体では別の署名処理に使用できないことに注意。

マルチシグネチャ方式では鍵はオンチェーンに保存されるが、閾値方式では計算と秘密の共有はオフチェーンで行われ、オンチェーンには1つの公開鍵のみが保存される。このため、検証に必要なスペースや計算量の点で、閾値方式はマルチシグネチャ方式よりもはるかに安価になります。

ナイーブなマルチシグネチャは非効率的であるため、ブロックチェーンにとって最適な解決策とは言えないかもしれません。この問題を克服するために、いくつかのソリューションでは、プロセスに関与するすべての参加者が自分の秘密鍵でメッセージに署名し、その後、出力は結合された公開鍵を使って検証される単一のメッセージに結合されます。これは、例えば後述するMuSig2を用いた仕組みです。

シグネチャーの集計

集約署名は、証明書チェーンのサイズ縮小やルーティングプロトコルのメッセージサイズ縮小などの用途に使用されます。

集計署名は、マルチ署名（すべてのユーザーが同じメッセージに署名する）の自明ではない一般化である。集約署名は、m人の異なる署名者からm個のメッセージに対するm個の署名から、単一のコンパクトな署名を作成することができます。これにより、検証の高速化、ストレージや帯域幅の削減が可能となります。

署名集約の主な仕組みは、一般的な集約と逐次的な集約の2つである。これらの機構を説明するために、それぞれ鍵の公開鍵と秘密鍵のペアを持つm人のユーザの集合を想定し、ユーザiがメッセージMiに署名することを望むとします。

  1. 一般的な署名集約方式では、各ユーザーi（m人のユーザーグループから）は、自分のメッセージMiに署名iを作成する。集約署名を生成するために、誰でも公開集約アルゴリズムを実行して、すべてのm個の署名（σ1、σ2、…、σk）を取り、それらを単一の署名σに圧縮することができる。
  2. 逐次署名集約方式では、ユーザ1はM1に署名してσ1を得て、ユーザ2はσ1とM2を組み合わせてσ2を得て、…といった具合になる。最終的な署名σは、Mkと署名σk-1を結合したユーザkによって生成される。逐次署名の集約は、署名プロセス中にのみ行うことができる。


署名を集約する技術は、Schnorr方式、格子方式、ペアリング方式など、様々な署名方式で知られている。ペアリングベースの集約署名に関しては、DfinityやAlgorandなどのブロックチェーン提案で利用されているBLS方式（Boneh et al.） しかし、これらの提案は同じメッセージに署名しているため、これらのソリューションは適切な集約署名方式ではなく、マルチシグネチャの一例と考えるべきでしょう。

最後に、多くの提案ではメッセージに署名する際に特定の順序を要求しているが、この要求が不要になった方式もあります（Lu et al.）

集約署名方式は、敵対者が自分自身で有効な集約署名を作成することを制限する必要があります。

閾値署名

(m,n)閾値署名方式は、n人の署名者のグループから任意のm人以上の署名者がグループを代表して署名を作成できる電子署名方式です。この署名は、参加者の公開鍵を組み合わせて生成されるグループ公開鍵で後で検証することができ、一般に、閾値署名は、それを生成するために協力した実際のグループメンバーを明らかにしません。

閾値署名方式の目的は、署名能力の制御を強制すること（m>1の場合）、単一障害点を排除すること（n>1の場合）、またはその両方です。

署名者の各グループは、信頼できるグループ権限者によって管理され、グループへの参加と離脱を監督することができます。多くのグループは、同じ信頼できるグループ権限によって管理されるか、またはグループは、すべてのメンバーがすべての管理操作に関与するように、そのメンバー間でグループ管理を完全に分散することを選択することができます。

グループGのn人中m人以上のメンバーの任意の部分集合が署名を生成でき、そのために、各メンバーは指定された結合器に部分署名を提供し、結合器は部分署名から意図された閾値署名を導出します。

グループGの公開グループ鍵にアクセスできる人なら誰でも閾値署名を検証することができます。指定された結合器は、信頼されたグループ権威のような実在の実体であってもよく、その演算がすべてのグループメンバー間で分散的に計算される仮想の実体であってもよいのです。指定された結合器が、閾値署名の入力として受け入れる前に、それぞれの部分署名の有効性を検証できる場合、閾値署名方式は堅牢であります。

比較検討

現時点では、これらの間で非常に類似した4つの技術を説明しました。以下では、調査したいくつかの手法の比較について述べます。


(*) この場合、メッセージは最大n個まで区別できる。
(**) (m,n)閾値方式と仮定。

MuSig2、FROSTの紹介

ブロックチェーンプラットフォームにマルチシグネチャや閾値署名を導入することが検討されている提案の中に、MuSig2やFROSTがあります。以下の章では、この2つの方式について技術的なことではなく簡単に紹介することを目的としています。詳細や数学的バックボーンに興味のある方は、(Nick et al.) や (Komlo and Goldberg) を読むと楽しいと思います。

MuSig2について簡単にご紹介

MuSig2 (Nick et al.) の提案は、集約署名の提案と類似している部分があるため、素朴な多重署名方式とはみなせません。

その中でも、特に注目したいのが、このスキームです。

  • 並列署名セッションの下でも安全です。
  • 鍵の集約が可能であること。
  • 通常のSchnorr署名を出力する。
  • 通信ラウンドが3回必要な先行提案のMuSigに対して、2回に削減できる。
  • 署名者の複雑さが通常のSchnorr署名と同等である。

MuSig2では、各参加者が秘密鍵と公開鍵のペアを持つ。鍵はx∈ℤをランダムに取り、gを環状群Gの生成子とみなしてX = g^xを計算することによって生成されます。

この方式では、2回の署名ラウンドを経て、m人のユーザーに対してm個の中間署名を生成し、これらの署名を最終的に組み合わせて1つの最終署名を生成します。

この署名は、利用者の公開鍵の組み合わせで生成された公開鍵で検証されます。

この方式をブロックチェーン取引の認証に利用した場合、チェーン上で公開されるデータは公開鍵1つと署名1つだけで、通常のSchnorr署名と区別がつかないため、コストはマルチ署名よりもはるかに低く、閾値メカニズムで生成されるものと同等になります。さらに、MuSig2における鍵生成は、閾値方式における鍵生成よりも単純である。あらゆる閾値署名方式と比較した場合のMuSig2の主な欠点は、m人の署名者が参加する必要がある（m = n）ため、MuSig2が硬直的なソリューションとなっていることです。

マルチシグネチャの閾値化

マルチシグネチャをより柔軟にするために、アルゴリズムを修正して閾値方式にすることが考えられる。このオプションでは、許容されるすべての署名者のキーを含むMerkleツリーを定義することが必要である。このMerkleツリーは、署名者候補のグループを走査することで、有効か否かを チェックすることを可能にします。


nを参加者数、mを閾値とする。上記のMerkleツリーに含まれる要素の数を組合せ数C(n,m)とする。この木の空間複雑度O(n^(n-m))は閾値に対して指数関数的であり、閾値mが小さいほどC(n,m)は大きくなるという、分かりやすい事実があります。

Merkleツリーにおける要素の探索、走査、挿入、削除の時間計算量はO(log(C(n, m)))<O(log(n^m))=O(m – log(n))です。

許容署名者のグループにMerkleツリーを含めるというアイデアは、MuSig2やBLS、その他のマルチシグネチャースキームで使用することができます。この機能はTaprootではMAST（merkelized abstract syntax tree）の下に含まれています。MASTは、暗号化されたビットコインを使用するために満たさなければならない、ユーザーが選択したさまざまな条件を保存するために、Merkleツリーを使用する方法です。

FROSTの簡単な紹介

閾値提案FROST（Komlo and Goldberg）は、半信頼の署名集約者（SA）を用い、その役割により署名者がネットワークのオーバーヘッドを削減することを可能にする。アグリゲーターは調整のために使用され、特権的な情報へのアクセスは持たない。SA の役割は、プロトコルの参加者または外部のサードパーティが担うことができます。SAは不作法な参加者を特定するために信頼され、またプロトコルの最後にグループの署名を公表する責任を負います。SAが誤動作した場合でも、プロトコルは適応的CCAに対して安全であります。悪意のあるSAは、DDoS攻撃を行ったり、悪意のある参加者を誤って報告する力はあるが、秘密鍵を知ることや不適切なメッセージに署名させることはできません。

FROSTの鍵生成は2ラウンドで行われ、Pedersenの分散鍵生成アルゴリズムに依存し、アルゴリズムは加法的秘密共有に基づいて構築されています。

さらに署名操作では、偽造攻撃を避けるためにバインド技術を利用する。署名処理は、前処理段階と単一ラウンド署名段階の2つの部分からなるが、これらを組み合わせて単一ラウンド署名段階とすることもできる。

最後に

これまで研究されてきたさまざまな技術には、すべて利点と欠点があります。Naiveマルチシグネチャは、異なる署名を検証する必要があるため、非効率的であると考えられる。しかしながら、これは最も単純な解決策であり、参加者の数によっては、興味深い選択肢となり得ます。

MuSig2やBLSのような集約特性を持つマルチシグネチャ方式は、上記の効率性の懸念を克服しているため、参加者数が増加した場合のもっともな解決策として考えることができます。とはいえ、マルチシグネチャ（ナイーブまたは非ナイーブ）は、操作に関与するすべての参加者が存在する必要があるため、厳密にはまだ少し堅いです。

より柔軟な解決策は、FROSTやStinsonとStrobl（Stinson and Strobl）による提案のような分散鍵生成に基づく方式を実装するか、許容署名者を含むMerkle木をMuSig2やBLSなどの任意のマルチ署名提案と組み合わせて、閾値方式を検討することです。

原文：https://medium.com/iovlabs-innovation-stories/aggregate-threshold-multisig-and-multisignatures-c45ffc0aecef By iovlabs medium

参考文献

RECOMMENDこちらの記事も人気です。