Sibuna技術ガイド 1.0.0-beta.3 ドキュメント
言語: 日本語
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
このページの内容

第III部:暗号研究からの基礎

Sibunaの二つの作業証明の層を支えるコストモデルを導き、Cohen-Pietrzakの逐次作業証明をその安全性の議論とともに示し、チャレンジとセッションに鍵付きハッシュによる認証を使う根拠を説明します。前提と参考文献はSID 0006に記録しています。

Hashcash:第一層の数学

定義とコスト

チャレンジ文字列\(C\)と難易度\(b\)ビットに対するSibunaの第一層のパズルは、\(\text{SHA-256}(C \parallel \text{":"} \parallel \mathrm{dec}(N))\)が先頭に\(b\)個のゼロビットを持つような\(N \in \mathbb{N}\)を見つけることです。nonceを十進数で表すのは意図的です。これにより、バイナリへのエンコード手順なしに、WebAssemblyソルバー、JavaScriptによる代替手段、ネイティブの検証器の間でワイヤーフォーマットが同一に保たれます。

難易度の単位は期待されるハッシュ試行であり、圧縮関数の呼び出しではありません。一つの入力が複数のSHA-256ブロックにわたることがあります。接頭辞の事前計算によって、nonceあたりの作業量が変わることもあります。ワイヤー上の規則はあくまでダイジェストに関する述語です。実装が一致させるべきなのはステートメントとnonceのエンコーディングであり、推定したCPUコストではありません。

独立で理想的なダイジェストでは、試行回数\(X\)は\(p = 2^{-b}\)の幾何分布に従います。その中央値は\(\left\lceil \ln(1/2) / \ln(1-p) \right\rceil\)で、\(p\)が小さいときはおよそ\(2^b \ln 2\)です。分散は\((1-p)/p^2\)です。検証者は探索を行うのではなく、候補のダイジェストを一つ確認します。パース、チャレンジの認証、フィンガープリントの確認、使用済み状態への挿入、応答は追加の作業です。プリミティブの所要時間を逆算して、サーバーが耐えられる大量アクセスの量を求めることはできません。

逐次作業証明:第二層

なぜ逐次作業か

逐次作業の構成は計算の間に依存関係を持ち込みます。後のラベルには、先に作られた値が必要です。これは総作業量とは別の量、つまり計算の深さを扱います。独立したパズルは依然として並列に実行でき、ハードウェアのハッシュのレイテンシーも依然として影響します。

SibunaはCohenとPietrzakが示したハッシュに基づく構成に従います。そのグラフは深さ\(n\)で\(2^{n+1}-1\)個のラベルを持ちますが、ラベルの数が決まっていても、ブラウザーでのレイテンシーが決まるわけではありません。ラベルは複数の圧縮ブロックにわたることがあり、開示では部分木を再計算することがあり、スケジューリングもばらつきを加えます。オラクルモデルでの解析から得た安全性の主張を、具体的なすべての実装や敵対者についての無条件の主張に変えてはなりません。

構成

\(n\)を深さとし、長さ\(n\)以下の二進文字列で名前を付けたノードを持つ完全二分木を考えます(根は\(\varepsilon\)、子は\(v0\)と\(v1\)、葉は長さ\(n\))。各ノード\(v\)は32バイトのラベル\(\ell_v = H(\chi, v, \mathrm{parents}(v))\)を持ちます。ここで\(\chi\)はチャレンジのステートメント、\(H\)は\(\chi\)を一度だけ吸収したSHA-256です(Hashcashソルバーと同じ接頭辞の工夫です)。

  • 内部ノードは二つの子をハッシュします:\(\ell_v = H(\chi, v, \ell_{v0}, \ell_{v1})\)。
  • 葉\(u = u_1 \dots u_n\)は、根からの経路が右に曲がったところすべてについて、祖先の左の兄弟をハッシュします:\(\ell_u = H(\chi, u, \{\ell_{u_1 \dots u_{i-1} 0} : u_i = 1\})\)。
ノードをdepth.indexで名付けた深さ3の完全二分木です。葉3.5の根からの経路(ノード0.0、1.1、2.2、3.5)は琥珀色、その開示で送る兄弟1.0、2.3、3.4は緑色で、赤い破線の矢印が1.0と3.4から葉3.5へ伸びています。葉の下の矢印は、葉を左から右の順にラベル付けすることを示します。
図 3 深さ3の木。葉3.5の開示では、葉のラベルと三つの兄弟のラベルを送ります。破線の辺は、ラベル付けを逐次的にする左の兄弟への依存です。

計算を逐次的にするのは左の兄弟の辺です。葉\(u\)は、その左にあるすべての部分木が完成するまでラベルを付けられません。そのため深さ優先の帰りがけ順の走査が強制され、根のラベル\(\varphi = \ell_\varepsilon\)は\(2^{n+1} - 1\)個すべてのラベルに順に依存します。

開示。\(\varphi\)を計算した後、証明者はFiat-Shamirによって\(t\)個の葉\(\gamma_i = H(\chi \parallel \varphi \parallel i) \bmod 2^n\)を導き、それぞれについて葉のラベルと、根への経路上の\(n\)個の兄弟のラベルを送ります。検証者は、親である兄弟から葉を再計算し、経路に沿って上へハッシュし、\(\varphi\)に到達することを確認します。検証者のコストは、有界な作業領域での\(O(tn)\)回のラベル計算です。一回のラベル計算は複数のハッシュブロックにわたることがあります。ラベルを数えることは、圧縮関数の呼び出しを数えることではありません。

fn verify_opening(base: &Sha256, n: u8, phi: &Label, gamma: u32, opening: &[Label]) -> bool {
    let Some((leaf, siblings)) = opening.split_first() else {
        return false;
    };
    // `siblings`は深さnから深さ1へ並ぶ。逆順にすると深さ1..=nと対応する。
    let mut hasher = node_hasher(base, n, gamma);
    for (d, sibling) in (1..=n).zip(siblings.iter().rev()) {
        if turns_right(gamma, n, d) {
            hasher.update(sibling);
        }
    }
    if hasher.finalize() != *leaf {
        return false;
    }
    let mut current = *leaf;
    for (d, sibling) in (1..=n).rev().zip(siblings) {
        let mut parent = node_hasher(base, d - 1, gamma >> (n - d + 1));
        if turns_right(gamma, n, d) {
            parent.update(sibling);
            parent.update(&current);
        } else {
            parent.update(&current);
            parent.update(sibling);
        }
        current = parent.finalize();
    }
    current == *phi
}

サンプリング、健全性、その限界

独立に検出できる不正な割合\(\alpha\)を持つ固定したコミットメントを考えます。各開示が一様かつ独立にサンプリングするなら、\(t\)回の開示で不正な位置をすべて見逃す確率は\((1-\alpha)^t\)です。この初等的な計算は、開示が多いほど役立つ理由を説明します。しかし、これだけでは逐次作業プロトコルの安全性の証明にはなりません。

参照した逐次作業の構成には、オラクルモデルでの安全性の解析があります。Sibunaのドメイン分離、パラメーターの対応付け、切り詰め、実装は、それでもなお構成の前提に照らして確認しなければなりません。Fiat-Shamirによるサンプリングは、コミットメントから開示を再現可能にします。再現可能であるだけでは、総当たりによる試行への耐性は証明されません。不正が決して安くならないという無条件の主張はしません。

証明者のメモリ

素朴な証明者はすべてのラベル(\(2^{n+1} - 1\)個)を保存します。Sibunaの証明者は、最初の走査の間は現在の経路の左の兄弟のラベルのスタック(\(n + 1\)個のラベル)を持ち、上位\(m = \min(n, 10)\)段(\(2^{m+1} - 1\)個のラベル、最大64 KB)だけを保持します。葉を開示するときは、その葉の深さ\(m\)の祖先の部分木を\(2^{n-m+1} - 1\)回のハッシュで再計算し、保持した段からスタックを初期化します。証明者の総コストは\(2^{n+1} - 1 + t\,(2^{n-m+1} - 1)\)回のハッシュで、出力する証明を含む作業領域全体は100 KB未満です。ブラウザーのタブとネイティブのテストは同じWorkspace型(sibuna_pow::posw::Workspace)を共有します。

パラメーターは所要時間ではない

Sibunaは\(n = b - 3\)を使って作業ビットを深さに対応付け、サポートする区間\([4, 24]\)に収めます。これは作業の尺度に関する取り決めであり、アルゴリズム間で実時間が等しいことを保証するものではありません。葉は複数の親のラベルをハッシュすることがあり、Hashcashはnonceを繰り返し試します。コンパイラー、ブラウザー、プロセッサー、パラメーターの選択はすべて、両者の相対的なコストに影響します。コミット済みのプリミティブのベンチマークは検証を測るもので、ブラウザーでの解答のレイテンシーを示すものではありません。

証明のサイズは\(32(1 + t(n+1))\)バイトです。深さ13で開示が16回なら、\(32(1 + 16 \times 14) = 7200\)バイトです。開示の回数を増やすと、木を構築する主要なコストが同じでも、証明と検証者の作業の両方が増えます。

構成の選び方

比べるべきはアルゴリズムの評判ではなく、資源の予算です。証明者のメモリ、検証者の最悪時の作業量、証明のバイト数、主張する性質に必要な前提を記録してください。メモリハードな探索は役立つことがありますが、高価な作業を繰り返さなければならない検証器は、攻撃者にサーバーの資源を消費させる別の場所を与えます。公開検証可能な遅延の構成は、秘密を共有するゲートとは別の信頼モデルに向いています。

Sibunaは、安価なハッシュによる検証と、ハッシュに基づく逐次作業の選択肢を保持しています。後者は証明のバイト数が多く、パラメーターをより慎重に解析する必要があります。どちらを選んでも、高価な検証に入る前に不正な形式の証明を拒否する必要はなくなりません。

対称鍵による認証:チャレンジとセッション

発行者と検証者は同じ

デジタル署名では、公開鍵を持つ誰でも検証できます。検証者に発行させてはならない場合には、これが正しい道具です。Sibunaの検証者は発行者そのものです(または一つのシードを共有するクラスターです)。擬似ランダム関数から作るメッセージ認証コードは、その信頼ドメインの中での認証を提供します。公開検証は提供しません。MAC鍵を持つ者は誰でもトークンを発行できます。ベンチマークの章では、実装したトークンの操作を比較します。

長期的にはもう一つの帰結が重要です。Ed25519は楕円曲線群の離散対数に依拠しており、これはShorのアルゴリズムで破られます。鍵付きハッシュはハッシュ関数だけに依拠しており、量子アルゴリズムによる高速化は高々二次です。Sibunaは、発行能力を持たない検証者を必要とするデプロイのために、Ed25519を選択肢(--token-scheme ed25519)として残しています。

鍵スケジュール

32バイトのマスターシード一つ(--secret-file、SIBUNA_SECRET、または新たに生成した乱数値から得ます)から、鍵付きBLAKE3とドメイン文字列によって用途ごとの鍵をすべて導きます。トークン鍵、チャレンジ鍵、Ed25519鍵、フィンガープリント鍵、そして要件チケットを封印する要件鍵です(第IV部)。

pub fn derive(seed: &Seed) -> Keys {
    Keys {
        token: subkey(seed, "sibuna/token/v1"),
        challenge: subkey(seed, "sibuna/challenge/v1"),
        ed25519_seed: subkey(seed, "sibuna/ed25519/v1"),
        fingerprint: subkey(seed, "sibuna/fingerprint/v1"),
        requirement: subkey(seed, "sibuna/requirement/v1"),
    }
}

fn subkey(seed: &Seed, purpose: &str) -> [u8; 32] {
    blake3::keyed_hash(seed.as_bytes(), purpose.as_bytes())
}

クラスターでは、Keys::bind_nodeがチャレンジ鍵を、その鍵の下でsibuna/challenge-node/v1とノードIDに対して計算した鍵付きBLAKE3で置き換えます。これにより、チャレンジは発行したノードに戻らなければなりません。一方、セッショントークンと要件チケットはすべてのメンバーで有効なままです。

ドメイン分離は、用途をまたぐ偶発的な再利用を防ぎます。マスターシードが漏れれば、導出したすべての鍵が漏れます。クラスターが合意すべきなのはシード一つだけです。

状態を持たないチャレンジ

二つのバイト配置です。チャレンジ識別子では、1バイトずつのver、alg、diff、tと、8バイトずつのissued_at、fingerprint、nonce、rule_hashからなる36バイトのペイロードに、16バイトのBLAKE3タグが続きます。合計52バイトで、URL安全なbase64の70文字として送ります。セッショントークンでは、1バイトずつのver、alg、bits、5バイトのres、8バイトずつのtimestamp、expiry、rule_hash、fingerprintからなる40バイトのペイロードに、16バイトのBLAKE3タグが続きます。合計56バイトで、URL安全なbase64の75文字として送ります。
図 4 チャレンジ識別子とセッショントークンのワイヤーフォーマット。各レコードの上の数字はバイトオフセットです。

チャレンジ識別子は自己認証するレコードです。バージョン、アルゴリズム、難易度、開示数、発行時刻、クライアントの鍵付きフィンガープリント、PRFで導いたnonce、チャレンジを要求したポリシールールのハッシュを持ち、その後にチャレンジ鍵による16バイトのタグが続きます。発行しても何も書き込みません。検証ではレコードをデコードし、タグを定数時間で確認し、経過時間をチャレンジのTTLと照合し、フィンガープリントを送信元のクライアントと照合し、その後で初めて証明を調べます。

使用済み集合は、16バイトのタグに対するRobin Hoodオープンアドレス法の16個のシャードです(第V部)。フィンガープリントはクライアントのアドレスとUser-Agentの鍵付きハッシュです。連結によって二つの入力が衝突しないように長さで区切り、他のクライアントのフィンガープリントをオフラインで計算できないように鍵を付けています。