数値結果(Numeric Outcome)DLC作成の最適化
※この記事はThibaut Le Guilly氏による「Optimizing Numeric Outcome DLC creation」の投稿を和訳したものです
要約
数値結果(numeric outcomes)のアダプタ署名作成が大幅に高速化されました。
Introduction
先日、P2PDerivativesアプリケーションにいわゆる数値分解(numerical decomposition)を実装したことを発表しました。この手法により、同じ支払い値で結果の範囲をカバーするために必要なアダプター署名の数を減らすことが可能です（この文の意味がわからない場合は、最初のセクションが役に立ちます。理解した場合は、スキップできます。 ）。これは大きな改善ですが（DLCの2つのピア間で交換する署名が少なくなるため）Matthew Blackによりアダプタ署名の作成が以前より大幅に遅いという報告がありました。この記事では、この減速が発生した理由を説明する前に、最初に数値分解について復習し、次にどのようにして大幅に減速したかを説明します。
数値分解(Numerical Decomposition DLC)
数値分解を使用する前は、Oracle（BTC / USDレートを報告）は、特定の時点での価格を表す文字列に署名するだけでした。
以下でアリスとボブがBTC / USD価格に基づいて以下の条件でDLCを実施する場合を例に説明します。
- 価格が40000ドル未満の場合、ボブは担保を全て取得
- 価格が40000ドルから50000ドルの間の場合、両者の受取額は線形的に変動
- 価格が50000ドルを超える場合、アリスは担保を全て取得
彼らがビットコインの価格が0ドルから1000000ドルの間で適切に契約を結ぶことができることを確認したい場合は、100000の異なるアダプター署名を作成する必要があります。これは、これらの署名の生成、交換、および保存の観点から、非常に実用的ではありません。
数値分解により、オラクルは各桁に個別に署名するようになりました。たとえば、価格が45000ドルの場合（およびOracleが8桁でレポートするように設定されている場合）、それぞれ、0’ ‘0’ ‘0’ ‘4’ ‘5’ ‘0’ ‘0’ ‘0’の署名が発表されます。
これが何をもたらすか説明します。例えば、$ 10000未満の結果の範囲をカバーするために、頭4桁をゼロ（ ‘0’’0'’0'’0'）に設定してアダプターポイントを作成し、残りの4桁を無視することができます。 。したがって、$ 0〜 $ 9999の範囲をカバーするには、10000ではなく単一のアダプター署名で可能になります。
さらなる効率化としてオラクルは結果値のバイナリ表現に署名します（例のように基数10ではありません）。詳細については、過去のブログ投稿、もしくはDLC仕様リポジトリをご覧ください。
速度の減少
では、数値分解に切り替えた後、アダプター署名の作成が遅くなった原因は何でしょうか？これを理解するには、アダプタの署名がどのように作成されるかを少し詳しく説明する必要があります（加算と乗算以外の何物でもないので、心配無用です！）。
アダプター署名(Adaptor Signature)
ここでは、アダプター署名の概念を簡単に触れます。より詳細な説明については、それに関する以前の記事を参照してください。アダプター署名は、シークレットで暗号化された署名であり、復号化後（またはシークレットの知識がある場合）に、特定のメッセージの有効な署名を取得することを証明できます。ECDSAの下で、メッセージmに対するアダプタ署名S’は以下の通り作成されます。
秘密鍵x、秘密の値tに対して、tのパブリックイメージ（アダプターポイントとも呼ばれます）T、xの公開鍵Xを作成します。
※記載を簡潔にするための署名検証部分はスキップします（興味のある方は過去の投稿のアダプタシリーズをご覧ください）
秘密の値tを知っているユーザは、以下の様に有効な署名sを取得することができます。
メッセージmに対して有効なECDSA署名となっていることがわかります。
DLCの場合、オラクルの署名を秘密の値tとして使用して、アダプターの署名を作成します。秘密の値tは最初は契約者に知られていません。また、オラクルはイベントごとに1つの署名をリリースすることになっているため、DLC用に作成されたほとんどのアダプター署名の秘密の値tは（願わくば）決して明らかにされません。したがって、実際には、両方の当事者が、オラクルによってリリースされる可能性のあるすべての可能な署名のパブリックイメージ（署名ポイントとも呼ばれる）を計算し、それらを使用して、各支払いトランザクションへの署名を暗号化します。オラクルは、次のようになるBIP340Schnorr署名を使用することに注意してください。
したがって、可能なm（DLCの可能な結果の値を表す）ごとに、当事者は次のようにアダプターポイントSを作成します。
Sは、公に知られている値のみを使用して作成可能です（DLCオラクルはイベントごとに事前にR値をリリースする必要があることを思い出してください）。
数値分解を伴うアダプタ署名(Adaptor Signature with decomposition)
数値分解を行うとアダプタ署名の作成がはるかに遅くなる理由を理解するために、分解の前後で何が変わるかを見てみましょう。数値分解では、すべての署名画像の合計を暗号化シークレットとして使用します。したがって、署名s0、s1、s2、…、s7をリリースするオラクルがある場合は、次のように構築されたアダプタポイントSを使用します。
後に以下を使用してアダプター署名を復号化できます。
各Sxは前のチャプターで解説した通り作成されます。Schnorr署名の線形性のおかげでこれが機能します。
したがって、数値分解を伴うDLCと「通常の」DLCとの主な違いは、ポイントの合計であるアダプターポイントを計算する必要がある点です。
数値分解とマルチオラクルを使用したアダプタ署名(Adaptor Signature with decomposition and multi-Oracles)
数値分解と同様のアプローチを使用して、複数のオラクルからの署名ポイントを使用して暗号化されたアダプタ署名を作成することが可能です。これは、各オラクルの署名ポイントを単純に合計することによって行われます。オラクルA、B、Cと数値分解を想定すると、次のように各オラクルの署名ポイントを計算できます。
次に、署名ポイントを合計することにより、集計Sを計算できます。
楕円曲線(EC)演算
数値分解とマルチオラクルを使用するときにアダプター署名の作成が遅い理由を理解するには、楕円曲線（EC）の乗算が加算よりもはるかに計算量が多いことに注意する必要があります。これは、ECの乗算は、それ自体にポイントを連続して追加することによって実行されるためです。したがって、
を計算するためには、実際は以下の通り実行されます。
それらを計算するためのアルゴリズムの最適化（doubleやaddなど）が存在しますが、ECポイントの乗算は加算よりもはるかにコストがかかることは一般的に真実です。ここで、数値分解の場合の署名点を計算するための方程式をもう一度見てみましょう。
7つの乗算（またはナンスや数字と同じ数）があることがわかります。さらにマルチオラクルを使用する場合、この数はオラクルの数で乗算されます。したがって、アダプタポイントの計算における乗算の数のこの増加が、アダプタの署名計算の速度低下の原因であると仮定できます。これを確認するために、5つのオラクルと各オラクルに20のノンスを使用して、単一の分解された結果に対する単一のアダプター署名の作成をベンチマークしました。結果は次のとおりです。
署名ーポイントの計算
6,222,608 ns / iter（+/- 667,325）
署名ポイントからのアダプター署名の計算
280,801 ns / iter（+/- 62,948）
完全なアダプター署名の計算
6,444,640 ns / iter（+/- 628,459）
実際、ほとんどの時間が署名ポイントの計算に費やされていることがわかります。
最適化(Optimizing)
計算にコストがかかる理由がわかったので、状況を改善する方法を見てみましょう。
因数分解(Factoring out)
数値分解の場合の署名ポイント計算の方程式を思い出してください。
ここでも7つの乗算がありますが、それらはすべて公開鍵Pを含んでいることに注意してください。ですから、おそらくずっと前に学んだこと、因数分解を使用することができます！ありがたいことに、楕円曲線でも機能します。したがって、方程式を次のように書き直すことができます。
これで、単一のEC乗算演算ができました。
確認するために、この因数分解されたバージョンを「通常の」バージョンに対してベンチマークします。因数分解の最適化は、ナンスの数が増えるにつれて、元の最適化よりもますます優れたパフォーマンスを発揮することが期待されます。5つのオラクルを使用して、さまざまな数のナンスについて両方のベンチマークを行うことで、これを検証します。次のグラフは結果を示しています。
単一のナンスを使用する場合は元のバージョンの方がわずかに優れていますが、2つ以上ナンスを使用する場合は最適化されたバージョンの方がすでに高速であることがわかります。
これはすでにかなり良い改善のように見えますが、計算するアダプター署名の数と同じ数のEC乗算を実行する必要があります。
事前計算(Pre-computing)
多数の署名ポイントを作成するときにEC乗算の数をさらに減らすには、戦略を変更する必要があります。各「最終」結果の署名ポイントは、各桁の期待値を使用して計算された署名ポイントのセットの合計であることを思い出してください。各桁の可能な値ごとに署名ポイントのセットを事前に計算することにより、EC乗算の最大数はnb_nonces * nb_outcome_per_nonceになり、その後は加算を実行するだけで済みます。したがって、ノンスが2つあり、ノンスごとに結果が2つある場合は、事前に計算する必要があります。
次に、考えられるすべての結合された署名ポイントを次のように計算できます。
その例の場合、4つの署名ポイントを事前に計算し、合計で4つの可能な結果があるため、EC乗算の数を減らしませんでした。ただし、たとえば、ノンスが10の場合、2¹⁰=1024回、EC乗算を実行する代わりに、20を実行するだけで済みます。
この最適化の影響を確認するために、「元の」バージョン、因数分解されたバージョン、および事前計算バージョンについて、ノンス10個、オラクル3個、ノンスごとに2個の結果を使用した場合に、考えられるすべての結果の署名ポイントの作成をベンチマークしました。
元のバージョン
1,935,444,337 ns / iter（+/- 187,182,386）
因数分解
518,583,393 ns / iter（+/- 19,961,490）
事前計算
142,026,577 ns / iter（+/- 6,604,498）
予想どおり、事前計算バージョンの方がはるかに優れていることがわかります。
メモ化(Memoization)
さらに最適化するために、上記の場合、いくつかの追加を再計算することに注意する必要があります。たとえば、値が“0 0 0 0 0 0 0 0 0 0” および “0 0 0 0 0 0 0 0 0 1” の結果の署名ポイントを計算する場合、間の署名ポイント“0 0 0 0 0 0 0 0 0” は2回計算されます。中間値をキャッシュすることで、実行される加算の数を大幅に減らすことができます。大まかに言って、私たちが適用するメモ化アルゴリズムは次のように機能します。
- ナンスR0を使用して値 “0”の署名ポイントを計算
- ナンスR1を使用して署名ポイントを計算し、1.で作成したナンス”0" の署名ポイントを加算して“0 0” の署名ポイントを作成
- ナンスR2を使用して署名ポイントを計算し、2.で作成したナンス”0 0" の署名ポイントを加算して“0 0 0” の署名ポイントを作成
- 値「000」の署名ポイントを計算し、ナンスR2と値 “0 0 0”を使用して署名ポイントを前に取得した値に追加します。
- …
結果値“0 0 0 0 0 0 0 0 0 0”の署名ポイントを計算したら、値“0 0 0 0 0 0 0 0 0”に対して計算された署名ポイントをバックトラックして“0 0 0 0 0 0 0 0 0 1”の計算の際に再利用します。この様に考えられるすべての結果値の署名ポイントを計算するまで続けます。
上記と同じベンチマークを使用すると、次の結果が得られます。
メモ化
42,049,313 ns / iter（+/- 2,844,778）
これにより、アルゴリズムが3倍以上高速になります。ノンスの数が増えると、パフォーマンスも向上すると予想できます。
並列化(Parallelizing)
アルゴリズムのパフォーマンスを向上させるもう1つの一般的なトリックは、操作を並列化して、別々のコアで実行できるようにすることです。常に可能または実行する価値があるとは限りませんが、この場合、各オラクルの署名ポイントの計算とそれらの集計を簡単に並列化できます。
したがって、順次計算する代わりに、次のようにします（||は並列を意味します）
その後
そして最後に
（実際には、操作が実行される順序は決定論的ではないことに注意してください）
以前と同じベンチマークを使用すると、次の結果が得られます。
メモ化+並列化
24,089,747 ns / iter（+/- 5,290,419）
これは約2倍の改善です。オラクルの数を増やすと、改善も増えます。
結論と今後の作業
EC乗算の数を減らし、並列化を適用したおかげで、署名ポイントの計算を大幅に改善することができました。DLCはピアツーピアプロトコルであるため、アダプターの署名はエンドユーザーのデバイスによって計算されることが予想され、必要な計算リソースを削減することが重要になります。また、並列化を適用できるとは限らない場合もありますが、事前計算とメモ化のアプローチは、大きなメリットをもたらすことがすでに示されています。
近い将来、これらの最適化をP2PDerivativesアプリケーションに実装して、ユーザーエクスペリエンスをさらに向上させる予定です。
最後に、Nadav Kohenは、BIP340で言及されているバッチ検証アルゴリズムを採用することでさらに改善できると述べました。メッセージハッシュをインデックスに置き換えるというLloydFournierからの提案も、さらなる利益をもたらす可能性があります。フォローアップ記事で取り上げることを願っていますので、是非Twitterでフォローして通知を受けることを忘れないでください！
謝辞
この記事に記載されている様々な最適化につながる有用な提案や議論をしてくださったLloyd Fournier, Ichiro Kuwahara, Nadav Kohen and Matthew Blackに感謝します。
Thibaut Le Guilly
