💻 computer science

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

本論文は、離散的な証明計算を通じて最大ギャップを追跡することにより、信頼できない当事者によって維持される動的な順序集合を検証する定数メモリ・オーディティング・スキームである「Split Tallies」を導入し、隠れた乱数やタイムスタンプなしではこのような効率性は不可能であることを証明しつつ、計算能力に制限のない敵対者に対する高確率なセキュリティを実現するものである。

原著者： Faruk Alpay, Levent Sarioglu

公開日 2026-06-12

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Faruk Alpay, Levent Sarioglu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

非常に賢いが、嘘をつく可能性もある司書（メンテナー／管理者）を想像してください。その司書は、完璧な順序で並べられた本の図書室を管理しています。あなた（ユーザー）は、「本Xはここにありますか？」や「Yの直前にある本は何ですか？」といった質問を投げかけます。司書は即座に回答します。しかし、あなたは司書の内部メモリを信頼しておらず、質問のたびに棚をチェックすることもできません。なぜなら、それでは時間がかかりすぎるからです。

あなたは、後で司書が行ったすべての回答が実際に正しかったことを検証する方法を必要としています。ただし、図書室のすべてを自分で記憶する必要はありません。

この論文は、この問題を解決するために「スプリット・タリー（Split Tallies）」と呼ばれるシステムを紹介しています。これは、古代の会計の歴史と現代数学を巧みに組み合わせた手法を用いて、あなたのメモリ消費をほとんど増やすことなく、司書が真実を述べていることを証明する「証明書（サーティフィケート）」を作成します。

仕組みをシンプルな概念ごとに分解して説明します：

1. 古代の比喩：割られた棒（Split Stick）

このアイデアは、600年前のイギリスの「タリー・スティック（刻み目棒）」から着想を得ています。

物語： 商人が農家に金を貸す際、金額を表す切り込みを木の棒に刻みました。その後、その棒を縦方向に真っ二つに割りました。商人は片方の半分（ストック）を持ち、農家はもう一方の半分（フォイル）を持ちました。
魔法： 返済の時期が来たら、二つの半分を合わせます。本物の棒であれば、木目や切り込みが完璧に一致するため、ぴったりと合います。偽物の棒では、決して一致することはありません。
この論文において：
- 司書は「フォイル（図書室の内部メモリ）」を保持しています。
- **監査人（あなた）**は「ストック（5つの数字からなる秘密のリスト）」を保持しています。
- **パブリック・タリー（公開された刻み目）**は、司書がすべての操作の後に書き留めなければならない「切り込み」のリストです。
- 監査とは、司書の語るストーリーがあなたの秘密のリストと一致するかどうかを、あなたがチェックする瞬間のことです。

2. コアとなるトリック：「隙間」を追跡する

多くの人は、図書室を「本のリスト」として考えます。しかし、この論文はこう言います。「いいえ、本の間の**空のスペース（隙間）**について考えなさい」と。

図書棚には始まり（0）と終わり（U）があると想像してください。
もし棚が空であれば、始まりから終わりまで一つの巨大な隙間があります。
本を追加すると、その大きな隙間を二つの小さな隙間に**分割（split）**します。
本を削除すると、二つの隙間を一つの隙間に**統合（merge）**します。

この論文は、もし隙間がどのように接続されているかを正確に知っていれば、すべての本の場所を特定できることを証明しています。司書は単に「本Xはここにあります」と言うだけでは不十分です。彼らは、その存在を証明する特定の隙間のIDを指し示さなければなりません。

3. ゲームのルール（インデンチャー／契約）

司書が嘘をつくのを防ぐために、このシステムは、厳格なタイミング設定のある「椅子取りゲーム」のように、厳格なルールを強制します。

パブリック・クロック（公開された時計）： 新しい隙間が作成されるたびに（本が追加されるたびに）、それには一意の連続したID番号（タイムスタンプのようなもの）が付与されます。
引用ルール： 司書が質問に答える際、使用している隙間のID番号を引用しなければなりません。
- 重要なルール： あなたは、今この瞬間よりも前に作成された隙間IDしか引用できません。「未来」のIDを引用することはできません。
秘密の数学： 監査人（あなた）は秘密の数字を持っています。隙間が誕生したり使用されたりするたびに、監査人は自分の秘密の数字に、その隙間のIDを含む数学的な公式を掛け合わせます。
- もし司書が正直であれば、最終的な計算は完璧に成立します。
- もし司書が嘘をついた場合（例：本がないのに「ある」と言った場合）、彼らは隙間のIDを捏造しなければなりません。しかし、彼らはあなたの秘密の数字を知らないため、数学的な計算はほぼ確実に失敗します。

4. なぜこれほど効率的なのか

この論文は、このシステムが驚くほど軽量であることを主張しています。

あなた（監査人）にとって： あなたは5つの数字と「フラグ（Yes/Noのスイッチ）」を覚えておくだけで済みます。図書室や本、あるいはその履歴を保存する必要はありません。ただ、刻み目の流れを見守るだけです。
司書にとって： 本一冊につき、一つ余分な数字（隙間のIDを保存するため）を保持するだけで済みます。
コスト： もし司書が不正を働こうとした場合、それをやり過ごせる確率は天文学的に低くなります（100万回の操作に対して1兆分の1未満）。

5. 「不可能」な部分

著者たちは、これを簡略化しようとするとシステムが壊れてしまうことを証明しました。

ランダム性なし？ もし秘密の乱数を使用しなければ、巧妙な嘘つきは常にあなたを欺くことができます。
秘匿性なし？ もし司書があなたの秘密の数字を知っていれば、彼らは数学的な計算を偽装できてしまいます。
時間制限なし？ もし司書が「未来」のIDを引用することを許された場合（タイムトラベル）、彼らは本物に見える完璧な偽の図書室を作り出すことができます。「時計」のルールは、これを阻止するために不可欠です。

6. 「再編成」のボーナス

図書室では、棚の整理（満杯になった棚を二つに分割したり、二つの空の棚を統合したりすること）が必要になることがあります。この論文は、こうした複雑な再編成ステップであっても監査が可能であることを示しています。彼らは、司書がどれほど多くの「再編成」を行っても、総移動回数は予測可能であることを証明しました。監査人は、司書の「領収書」をカウントすることで、彼らが隠蔽のために余計な作業を行っていないかを確実に確認できます。

まとめ

この論文は、動的なリストに対する数学的な嘘発見器を構築しています。

司書が作業を行います。
監査人はほとんど何もしません（わずか5つの数字だけ）。
**タリー（刻み目）**は、刻み目の公開記録です。
結果： 司書がたとえあなたを騙そうとするスーパーコンピュータであったとしても、またあなたにデータを保存するためのメモリがほとんどなかったとしても、すべての回答が正しかったことを、ほぼ100%の確信を持って検証できます。

それは、金庫の中の硬貨を一つ一つ数えるのではなく、計算が正しいことを証明するたった一枚のレシートを見て、銀行口座の残高を確認するようなものです。

技術要約：スプリット・タリー（Split Tallies）：動的な順序集合を定数メモリで監査するための離散的証明書計算

問題提起

本論文は、悪意のある当事者（「維持者」）によって管理され、消費者によってクエリされる動的な順序集合の検証について取り組んでいる。現代のコンピューティングにおける多くのシナリオでは、データ構造は信頼できない環境（リモートサービス、不透明なハードウェアアクセラレータ、あるいは調達されたライブラリなど）に存在している。消費者は操作（挿入、削除、メンバーシップテスト、前駆者/後続者クエリ、および極値クエリ）を発行し、遅延なくその回答を受け取り、それに基づいて即座に行動する。

核心となる課題は、消費者（「監査者」）がデータ構造自体を保存したり、操作を再実行したりする必要なく、操作の全履歴に対する正当性の証明書を提供することである。監査者は、定量の状態（具体的には5つのマシンワードと1つのフラグ）のみを保持する受動的な存在でなければならない。一方で、維持者は、公開された追加専用のシーケンスである**タリー（tally）**に対して、すべての操作ごとに短い「ノッチ（刻み目）」を付加しなければならない。目標は、維持者がいくら強力な計算能力を持ち、可視化された履歴に基づいて戦略を適応させたとしても、維持者が誤った回答を提供したことを高い確率で検出することである。

手法

提案されている解決策である**スプリット・タリー（Split Tallies）**は、負債を記録するために棒に刻み目を入れ、それを縦に割るという歴史的な木製のタリー・スティック（計数棒）から着想を得ている。債権者は「ストック（stock）」を保持し、債務者は「フォイル（foil）」を保持する。決済時には、両方の半分を噛み合わせることで真正性を検証した。このデジタルな文脈においては以下の通りである：

タリー（The Tally）： 維持者によって付加される、公開されたノッチのストリーム。
ストック（The Stock）： 監査者のプライベートな状態（5つのワードと1つのフラグ）。
フォイル（The Foil）： 維持者の内部的な帳簿管理。
監査（The Audit）： セッション終了時に、ストックをフォイルに対して「噛み合わせる（mesh）」プロセス。

ギャップ計算（The Gap Calculus）

本論文の技術的中核は、ギャップの離散計算である。システムは集合 $S$ を直接監査するのではなく、順序付けられた宇宙を分割する**極大空隙（maximal vacant intervals）**の族（ギャップ）を監査する。

表現： 宇宙 $\{1, \dots, U\}$ 上の集合 $S$ は、センチネル（番兵）$0 $と$ U+1 $をつなぐ**連鎖的な間隔**であるギャップ$ \langle a, b \rangle$ によって一意に表現される。
標準形： 本論文は、このギャップの族が、区間非巡回グラフにおける $0 $から$ U+1$ への一意な単位パスに対応することを証明している。
書き換え（Rewrites）： 操作は、このパスの局所的な書き換えとしてモデル化される：
- 挿入： 1つのギャップ $\langle a, b \rangle$ を2つの $\langle a, x \rangle, \langle x, b \rangle$ に分割する。
- 削除： 隣接する2つのギャップ $\langle a, x \rangle, \langle x, b \rangle$ を1つの $\langle a, b \rangle$ に結合する。
- クエリ： 特定のギャップ（例： $x$ を含むギャップ、または $x$ から始まるギャップ）を提示することで回答される。

インデンチャー・ディシプリン（The Indenture Discipline）

これらの書き換えを状態を保存せずに監査するために、監査者は有限体 $\mathbb{F}_p$ 上の多項式恒等式テストに基づくフィンガープリント（指紋）メカニメントを採用する。

コードとタイムスタンプ： すべてのギャップの誕生には、公開カウンタ $\kappa$ を通じて一意のコード（タイムスタンプ）が割り当てられる。
引用（Citations）： すべての操作は、消費される（書き換えられる）ギャップのコードを引用しなければならない。
アキュムレータ（蓄積器）： 監査者は2つのアキュムレータ、 $A$ $A$ （誕生用）と $R$ $R$ （消費用）を保持する。コード $c$ $c$ と端点 $a, b$ $a, b$ を持つギャップに対し、値 $\nu(a, b, c)$ $ν (a, b, c)$ は体へと写像される。
- 誕生時： $A \leftarrow A \cdot (z - \nu(a, b, c))$
- 消費時： $R \leftarrow R \cdot (z - \nu(a, b, c))$
- ここで、 $z$ はセッション開始前に監査者が選択する秘密の体要素である。
検証： 監査時、維持者は現在のギャップとそのコードを開示する。監査者は、開示されたギャップが適切に噛み合っている（有効な連鎖を形成している）かを確認し、 $A = R$ であることを検証する。

主要なメカニズム

時間的規則（Temporal Rule）： 引用されたコードは、イベント開始時のカウンタ値よりも厳密に小さくなければならない。これにより、維持者が将来のコードを「借りて」バランスの取れた台帳を偽造することを防ぐ。
強制（Forcing）： ギャップのパスの一意性により、任意のクエリに対する正しい回答は、引用されたギャップの関数として強制的に決定される。もし維持者が存在しない、あるいは生存していないギャップを引用した場合、その回答はギャップの特性と矛盾するか、あるいは台帳のバランスが崩れることになる。

主要な貢献と結果

1. 監査定理（健全性と完全性）

本論文は、本スキームが完全な完全性（perfectly complete）（誠実な維持者は常に受理される）と $\epsilon$ -健全性（ $\epsilon$ -sound） を備えていることを確立している。

健全性誤差： 維持者が $T$ 回の操作の中で一度でも誤った回答を提供した場合、受理される確率は最大で $(4T + 1)/p$ である。
パラメータ： 61ビットの素数 $p$ （例： $2^{61}-1$ ）を用いる場合、100万操作までのセッションにおいて誤差確率は $2^{-38}$ を下回る。
仮定： 計算量的な困難性の仮定は必要とせず、そのセキュリティは情報理論的であり、無制限の計算能力を持つ敵対者に対しても有効である。

2. 不可能性と必要性の結果

本論文は、特定の設計上の選択が不可欠であることを証明している：

決定論的フロア： サイズ $n$ の集合に対して、終了時に健全性を保証する決定論的な監査者は、少なくとも $2n - \log_2(2n+1)$ ビットの状態を保持しなければならない。これは、ランダム性が要件である（単なる便宜ではない）ことを証明しており、決定論的な解決策は線形空間を必要とすることを意味する。
秘密のランダム性： 監査者の乱数が維持者に可視である場合、健全性誤差は1となり（維持者は常に台帳を偽造できる）、評価点 $z$ の秘匿性は不可欠である。
時間的規則の必要性： 将来のコードの引用を禁止する規則がない場合、正確なバランスを実現し、確率1で受理される明示的な3操作の偽造が可能となる。

3. 維持者の実装

本論文は、リーフ指向（leaf-oriented）(2, 4)-ツリーを用いた具体的な実装を提供している：

計算量： 操作は最悪の場合 $O(\log n)$ 時間で実行される。
オーバーヘッド： この構造は、要素ごとに1つの追加ワード（ギャップコードを格納するため）のみを必要とする。
監査された再構成（Rebalancing）： 本論文は、 $m$ 回の更新における構造的イベント（分割、融合、共有）の数が最大 $2m$ であることを証明する**アテステーション・エンベロープ（証跡包）**を導入している。この境界は、維持者が付加する1ワードのアテステーションを監査者がカウントすることによって証明され、償却解析を公開検証可能な主張へと転換している。

4. チェックポイントとエポック

本プロトコルは任意のチェックポイントをサポートしている。監査はいつでも実行可能であり、受理されたエポックは加算誤差範囲とともに連鎖させることができる。これにより、検出のレイテンシを調整することが可能である（例：高いセキュリティのために毎操作ごとに監査を行うか、効率のためにより頻度を低くするか）。

重要性と範囲

本論文は、動的な順序集合に対する定数メモリ監査の**「クローズド・アカウント（閉じた勘定）」**を提供していると主張している。その重要性は以下の点にある：

パラダイムの転換： 「孤立したテスト」から「実行と共に移動する証明」への移行。
情報理論的保証： メルクルツリーやデジタル署名のような暗号学的仮定（ハッシュ関数など）に依存せず、多項式の代数的性質と順序集合の組合せ論的構造に依拠して検証を実現している。
タイトな下界： 決定論的な解決策がいかに線形空間を必要とし、ランダム性が隠蔽されなければならないかを証明することで、提案された定数メモリの解決策が最適に近いことを示している。
明示的な定数： すべてのパラメータ（素数のサイズ、ワード数、誤差範囲）は明示的であり、実用的な使用（例：64ビットワードへの適合）に合わせて調整されている。

範囲は、7つの操作インターフェース（挿入、削除、メンバーシップ、前駆者、後続者、最小値、最大値）に厳密に限定されている。本論文は、ギャップ計算が配置（隣接性、括弧付け、極値性）を証明するものであることを明記しており、ランクのような集計的な特性（これらは単一のギャップには局所的ではない）には拡張されない。検出は**遡及的（retrospective）**である。本論文は、この情報理論的設定におけるオンライン検出（回答を即座に拒否すること）は、一方向関数の存在に関連する既知の未解決領域であることを認め、提案された解決策はその定義された遡及的モデル内において最適であるとしている。