net-kotoba ｜ Part 2 — 大規模クエリ・multihop・書込・CACAO・Signal
CACAO × X3DH/Double-Ratchet × Pregel[BSP] × t-of-N custody
EXPLAINER ─ PART 2
複雑/大規模クエリ・multihop・書き込み
CACAO 認可 ・ Signal E2E はどう動くか
Part 1（Datomic × IPFS × Prolly Tree）の続き
▶ 自動再生中 … 下のバーで一時停止・シーン移動
① 複雑/大規模クエリ — join と増分MV
BGP は subject 集合の積で結合する
execute_sparql_graph_pattern（quad_store.rs:1673〜）
?s :role "admin" .
?s :score ?n
triple1 → AVET{e3,e7,e9…}
∩
triple2 → AEVT{e1,e3,e9…}
HashSet 積{e3,e9}
各 triple を最適索引で引いて subject 集合を作り、HashSet で O(1) 交差。線形スキャン無し（JOIN 223→73ms / 10K）。
対応する代数（algebra）
BGP 三つ組結合
FILTER 数値/文字列述語
UNION 併合 + dedupe
OPTIONAL 左外部結合
GROUP BY COUNT/SUM/AVG…
DISTINCT (s,p,o) で重複除去
繰り返しクエリは MaterializedView で“作り直さない”
commit Δassert/retract
program.evaluate_deltaDatalog rules
MvRegistry.maintainderived facts ⊕=
commit ごとの差分だけをルールに流し、結果 Arrangement に畳み込む（mv.rs:7-93）。次回読取は再評価ゼロ。
② multihop — property path と N-hop DESCRIBE
<pred>+ は索引上の BFS（最大64ホップ）
eval_property_path / sparql_describe_n_hop（quad_store.rs:1441〜,2200〜）
?x knows+ ?y を frontier 展開で辿る
各ラウンド AEVT スキャンで次フロンティアを得て、(s,p,o) を HashSet で dedupe。
path 演算子
p+ OneOrMore（BFS）
p* ZeroOrMore
^p reverse（VAET 逆参照）
p1/p2 sequence（連結）
MAX_HOPS = 64
N-hop DESCRIBE は層ごとに
try_join_all で並列 fetch（438→149ms）
「友達の友達の…」も「参照を逆に辿る」も、結局 4 索引への BFS に落ちる。
③ multihop の重い計算 — Pregel BSP
頂点プログラム × superstep × メッセージ伝播
kotoba-vm/src/pregel.rs ・ distributed.rs（libp2p gossip）
superstep k 各頂点が inbox を読む
compute() state 更新 → 隣へ Message 送信
barrier 全頂点同期（BSP）
halt active 頂点ゼロで終了
Vertex{id,state,active} / Message{src,dst,payload=CBOR Delta}（pregel.rs:30-72）。PageRank・最短路・連結成分などをグラフ全体で。
分散 Pregel
node A頂点 1..n
gossipmsg route
node B頂点 n+1..
DistributedPregelRunner が node 跨ぎの Message を async channel + KotobaSwarm gossip でルーティング（QUIC/Noise/GossipSub）。
④ 大きいクエリ — federation で graph を跨ぐ
SERVICE <cid:remote> / GRAPH ?g
GraphPattern::Service / ::Graph（quad_store.rs:2062〜）
local graphhot Arrangement
+ CommitDag head
SERVICE <cid:mb>
→ multibase 解析 → KotobaCid
DistributedBlockStore
→ remote IPFS peer から block 取得
GRAPH ?g
→ all_graph_cids() を fan-out 列挙
content-address された別グラフを、その CID を service IRI にして横断クエリ。silent=true なら未知サービスは無視。
⑤ 書き込み — transact は graph に縛られる
CACAO 検証 → assert_datom → commit
xrpc transact handler → quad_store.rs commit（:3071〜）
edge が target graph を強制束縛
書込先は呼び手自身の名前空間 kotobase/db/<tenant_did>/<db> に固定。client が graph を指定しても上書き不可 → 自分のDBにしか書けない。
commit パイプライン
pending 収集 → 4索引 ProllyTree 並列ビルド →
tx_cid=blake3(datoms) → DistributedDatomCommit{index_roots, prev, author_sig} →
CAR 1束 PUT → CommitDag.add → head-ref 原子更新
許可された operator DID だけは任意 graph に書ける。pod は JWT 署名を検証せず（edge が信頼境界）、CACAO は暗号検証する。
⑥ CACAO 認証/認可 — 主権鍵のケイパビリティ
Cacao{h,p,s} を5段で検証する
kotoba-auth: cacao.rs / delegation.rs（verify）
1時間: iat/exp（exp無しは 最大7日）
2能力: datom:read / datom:transact / kotobase:pin
3graph scope: kotoba://graph/<cid> に含まれるか（multi-graph 可）
4署名: Ed25519(did:key) または EIP-191(secp256k1)
5audience: aud == node operator DID（使い回し防止）+ nonce
depth-2 委譲チェーン
root grantdelegator → service
leaf.iss == root.aud で橋渡し ↓
leaf invocationservice → agent
減衰のみ: leaf 能力 ⊆ root 能力、graph ⊆ root graph。depth-3+ は拒否。
Private既定。CACAO + graph 一致が必須
AuthenticatedBearer 必要・scope は不問
⑦ Signal E2E — X3DH → Double Ratchet
鍵共有 → メッセージごとに鍵が前進
kotoba-signal: x3dh.rs / ratchet.rs ・ kotoba-crypto: AES-256-GCM
X3DH 初期鍵共有
DH1=ECDH(IK_A, SPK_B)
DH2=ECDH(EK_A, IK_B)
DH3=ECDH(EK_A, SPK_B)
DH4=ECDH(EK_A, OPK_B) 任意
SS = HKDF(DH1‖DH2‖DH3‖DH4)
送受信の双方が同じ shared secret を導出。SPK 署名は IK で検証、OPK は使い捨て。
Double Ratchet（前方秘匿）
root keyDH rotation
chain keyKDF 連鎖
message key毎回使い捨て
各メッセージ mk で AES-256-GCM 暗号化。使用後 mk は zero化、順序ズレは MKSKIPPED にキャッシュ（MAX_SKIP=1000）。鍵漏洩しても過去/未来は守られる。
暗号化 datom（Enveloped value）
値を "signal:v1:{base64url}" で包んで格納（keycodec の Encrypted/Enveloped tag）。暗号文のまま複製、復号は subject==self か許可された agent だけ。
⑧ X-Road 流アカウンタビリティ — 説明可能な秘匿
暗号文複製 ＋ レシート ＋ t-of-N 鍵分散
docs/SECURITY-ARCHITECTURE.md（R0–R3）・kotoba-custody
R1
全読取で access datom
(who/purpose/ts)
R2
Base L2 anchor
署名 CommitDag
鍵リリースは「レシートを書いてから」
agentkey.requestShare
custodian 検証CACAO+purpose+nonce
レシート記帳→HPKE share 解放
clientt 個で復元
⚠レシート無しの解放は検知され、custodian は証明可能に有責（slashable）。epoch/deal_id 混在の定足数は拒否。
まとめ — Part 2
重いことは全部「索引 / BSP / CID / 鍵」に落ちる
①複雑query: BGP は subject 集合の HashSet 積、FILTER/UNION/OPTIONAL/GROUP。繰返しは MaterializedView が Δ 増分維持。
②multihop: property path p+ / p* / ^p は索引上 BFS（≤64hop）、N-hop DESCRIBE は層ごと並列 fetch。
③重い計算: Pregel BSP（superstep+message+barrier）、分散は libp2p gossip でルーティング。
④federation: SERVICE <cid:remote> / GRAPH ?g で content-address グラフを横断。
⑤書込: edge が db/<did>/<name> に束縛 → 自分のDBのみ。commit→CommitDag head 原子更新。
⑥CACAO: 時間/能力/scope/署名/audience の5段、depth-2 減衰委譲、Private/Authenticated/Public。
⑦⑧Signal: X3DH→Double Ratchet で毎メッセージ鍵前進・AES-256-GCM。暗号文複製＋レシート＋t-of-N custody で“説明可能な秘匿”。
主要コード: quad_store.rs / mv.rs / pregel.rs / delegation.rs / x3dh.rs / ratchet.rs / shares.rs
net-kotobase/docs/explainer
1.0×
0 / 0