要約

  • 1992年の価格関数は、解くには適度な負担があり、確かめるのは容易で、複数の要求に計算量をならして薄められないことを条件とした。
  • 価格を決める機関は近道を信頼先に渡せ、受信者は常連の送信者を免除できた。2003年のメモリ律速型研究は、機械性能の差が実際の負担を変える問題に踏み込んだ。

迷惑メールの強みは、一通目が完全に無料なことではない。二通目以降の複製がほとんど無料になることだ。文章を作る手間は一度で済み、同じソフトウェアが多数の受信箱へ展開する。一方、読む側の注意や処理資源は宛先ごとに消費される。

Cynthia DworkとMoni Naorは、CRYPTO ’92で予備版を発表したPricing via Processing or Combatting Junk Mailで、この複製の経済を狙った。課金対象は文字数でも通信量でもなく、資源への要求である。送信者が「ほどほどに難しい」関数を計算し、答えをメールに添える。受信側は配達前に、それよりはるかに安い計算で正しさを確かめる。

重要なのは消費したCPU時間の大きさだけではない。論文が求めたのは、計算量を償却できない性質だった。一つの入力を解いた経験や前処理によって、その後の大量の入力が安くなってはならない。一度の支払いで百万人に送れるなら、それは大量送信を抑える価格ではなく、固定費にすぎない。

要求から切り離せない証明

提案では、メッセージ、時刻、宛先を計算の入力に組み込める。宛先が変われば別の問題になり、本文が変わっても別になる。時刻を含めれば古い答えを失効させられる。複製したい行為そのものに、新しい計算を結び付ける構造である。

検証の安さにも運用上の理由がある。答えの確認が作成と同じほど高価なら、攻撃者は安い偽物を大量に送り、受信サーバーに高価な検査を強制できる。防御機構がDoSの増幅器になってしまう。要求者が重い作業を繰り返し、資源側は軽く判定するという非対称性が必要だった。

候補関数には、素数を法とする平方根、Fiat–Shamir署名の調整版、すでに破られたOng–Schnorr–Shamir方式の再利用などが並ぶ。秘密を守るために計算を事実上不可能にするのではない。「容易」と「困難」の間に、利用者には可能だが反復者には重い、調整可能な段差を置く試みだった。

著者らは、こうした「適度な困難さ」を扱う理論が乏しいとも指摘した。暗号は壁を越えられるかを問うことが多い。価格は、同時に何回越えられるか、前処理でまとめ払いできるか、機械の進歩でいつ段差が消えるかまで問う。数式の内部に運用経済が入っている。

例外が管理者を映し出す

大量送信のすべてが迷惑とは限らない。学会案内や専門家のメーリングリストは、望んでいる多数の相手に届く。各宛先に通常価格を課せば、害のある大量送信と有用な共同体通信を一緒に削ってしまう。

そこで論文は「近道」を用意した。価格を管理する機関は、計算を安くする情報を信頼する代理者に与えられる。承認された大量送信は、管理者が決めた条件で通常の価格を迂回する。受信者側には、証明なしで受け入れる常連送信者の一覧と、常に拒否する一覧がある。

この設計を見ると、計算の壁が中立ではないことが分かる。関数、難易度、近道の保持者を誰かが選ぶ。受信者も親しい関係の境界を選ぶ。計算は費用を払った証拠にはなるが、どの組織が免除に値するかを決定しない。

価格関数の安い解き方が見つかっても、暗号鍵の漏えいと同じ被害にはならない。大量に悪用されれば再び迷惑送信として観測でき、関数や鍵を変えられるというのが著者の見方だった。ただし、その修復には異常を見つけ、新価格を決め、移行を調整する主体が必要になる。

機械の差が請求額を変える

2003年、Dwork、Andrew Goldberg、NaorはOn Memory-Bound Functions for Fighting SpamでCPU律速型の弱点を再検討した。高速サーバーと古い端末では、同じ問題にかかる現実時間が違う。大規模送信者が新しい機械による割引を得て、一般利用者の方が長く待つ可能性がある。

後続研究は、試験機間でCPU速度ほど差が大きくなかったメモリ遅延に注目し、ばらばらなメモリアクセスを要求した。送信者は多くの無関係なアクセスを行い、受信者ははるかに少ないアクセス、場合によってはゼロで検証する。証明はメッセージ、送信者、受信者、日付に結び付き、期限切れと重複を排除する。

実験値には限界がある。具体的な実装は233MHzのセットトップボックスで、3.06GHzのワークステーションより約4倍遅かった。あらゆる端末での平等を示す値ではない。著者らは、完全な平等が望ましいかさえ問い直した。攻撃者に高価な設備を買わせる方が有効かもしれず、遅い端末は計算代行を使えるかもしれない。公平性そのものが設計判断になった。

影響の系譜と同一視を分ける

Harvardの論文記録、Dworkの研究略歴、Microsoft Researchの記録は、この研究を分散システム、暗号、差分プライバシー、アルゴリズムの公平性へ続く広い業績の中に置く。Harvardは暗号資産の基礎への影響も記している。

しかし影響は同一性ではない。1992年の論文はBitcoinの合意形成、発行、チェーン選択を記述していない。後世の仕組みを遡って発明したという話でもない。残ったのは、資源へのアクセス前に、意図的に負担し再利用できない費用の証拠を求めるという一般的な設計である。

ここから五つの問いが分かれる。何が希少資源なのか。作業はどの要求に結び付くのか。事前計算、転売、再生、償却は可能か。検証はいくらかかるか。価格と例外を誰が変えるのか。「プルーフ・オブ・ワーク」という名称だけでは、どれにも答えられない。