2026-07-06

Schnorr + PQC署名のハイブリッドで強偽造不可能性を保持するBird of Prey

Pieter Wuilleが情報共有としてDelving Bitcoinで紹介していたハイブリッド署名スキームにおけるマリアビリティの回避に関する取り組みが興味深かった↓

Bird of Prey 2: non-malleable Schnorr + PQ signatures - Protocol Design - Delving Bitcoin

ここで言うハイブリッド署名スキームというのは、例えばSchnorr署名のような既存のデジタル署名スキームに加えて、PQCの署名スキームを合わせて使用するスキームのこと。量子コンピューター対策としてPQCのデジタル署名スキームを採用する際のネックは、その歴史の浅さから見落とされている脆弱性が存在する可能性があることで、そういった点を既存の署名スキームでカバーし、かつ量子耐性を持たせる。

このようなハイブリッド方式で最も素朴なのは、両方のスキームでそれぞれ署名し単純に連結する構成。この場合、どちらか一方が破られない限り、署名の偽造は不可能（EUF-CMA）であることは保証される。しかし強偽造不可能性（SUF-CMA）は保証されず、署名の一部（破られた方の署名）を別の署名に差し替えることができる。たとえばSchnorr署名の場合、秘密鍵を計算できた攻撃者は、別のnonceを選択することで、正当なユーザーが作成した署名とは異なる署名（R, s）を作ることができる（マリアブルな署名になる）。逆にPQCのデジタル署名スキームが古典的に破られた場合も同じ問題が起こる。

ハイブリッド方式において、署名のマリアビリティを排除するための提案が上記のスレッドで紹介されているBird of Prey。

Bird of Prey 2

EuroCrypt 2026の論文では、Bird of Preyのクラスとして3つ（BoP-1、BoP-2、BoP-3）提示していて、Delving Bitcoinのスレッドはそのうち2番目の構成を取り上げている。

BoP-1：BLSなどの一意な署名スキーム（メッセージと公開鍵に対して検証を通る署名が一意に定まるスキーム。この場合、偽造不可能性と強偽造不可能性は等価）
BoP-2：SchnorrやEdDSAのようなFiat-Shamir変換ベースの署名スキーム
BoP-3：RSA系

通常のBIP-340の署名スキームは、

nonce kを選択し、
R = kGを計算し公開nonceとし、
e = H(R.x || P.x || m)を計算し（mは署名対象のメッセージ、Pは公開鍵）
s = k + e * dを計算し（dはPの秘密鍵）
(R.x, s)を署名とする。

という構成になっているけど、BoP-2ではチャレンジの作り方を変更することで、2つの署名をリンクする。具体的には、Schnorrの鍵ペアを ${(d_{schnorr}, P_{schnorr})}$ 、PQCスキームの鍵ペアを ${(d_{pqc}, P_{pqc})}$ とした場合、署名の作成手順を以下のように変更する

nonce kを選択し、
R = kGを計算し
e = H(R || P || m)を計算し（ここで ${P = P_{schnorr} || P_{pqc}}$ ）
PQCの秘密鍵 ${d_{pqc}}$ を使ってeに対してPQC署名 ${\sigma_{pqc}}$ を生成する
${s = k + H(\sigma_{pqc}) * d_{schnorr}}$ を計算し、
${\sigma = (s, \sigma_{pqc})}$ を署名とする。

検証手順も以下のように変更する

${R = s* G - H(\sigma_{pqc}) * P_{schnorr}}$ でRを復元し、
e = H(R || P || m)を計算し
${\sigma_{pqc}}$ を ${P_{pqc}}$ とeに対して検証する

つまり、

PQCの署名は、メッセージそのものではなくSchnorrのチャレンジeに署名し、
Schnorr側のsは通常のチャレンジeの代わりに ${H(\sigma_{pqc})}$ を係数として使用する

ことで両署名スキームをリンクする。この仕組みにより、片方の暗号を破って鍵を入手したとしても、そちら側の署名を差し替えることはできない。

sを変えると復元されるRが変わり、eが変わって ${\sigma_{pqc}}$ が無効になり、
${\sigma_{pqc}}$ を変えると、 ${H(\sigma_{pqc})}$ が変わってsが無効になる

という循環構造になる。

なお、この循環構造が機能するには、 ${\sigma_{pqc}}$ がeを一意に固定していること、つまり「同じ ${\sigma_{pqc}}$ が別のe値に対しても有効になる」ことがないという性質が必要で、しかもこの性質はPQCスキームが破られた後でも保たれる必要がある。PQC側が破られるケースでは攻撃者はPQCの秘密鍵を計算できる前提なので、そのスキームの困難性から来る性質はすべて失われる。もしこのとき複数のe値に対して同時に有効な ${\sigma_{pqc}}$ を作れてしまうと、Schnorr側の鍵に触れることなく ${\sigma_{pqc}}$ を差し替えられ、強偽造不可能性が破れる。ML-DSAなどでは、署名を固定したときにどのメッセージ（e）で検証が通るかはハッシュ関数のチェックで決まるため、格子仮定が崩壊してもこの性質は保たれる。

考慮事項

一方、以下のような考慮事項も挙げられている：

BoP-2スキームでは、sからRを復元するためSchnorr署名のバッチ検証ができなくなる。ただ、署名にRを含めなくてよくなるのでサイズ削減になる、PQCの署名の検証コストが支配的になるとSchnorrのバッチ検証を行うメリットは少ないという意見も。
Segwitの導入により署名のマリアビリティがTXIDに影響しなくなった状況で、このような特性は重要なのか？
- Pieter Wuille自身も重要性は大きく低下しており、あると良いねレベルという評価。
そもそもハイブリッド化が必要か？
- ハッシュベースであれば意義は薄く、格子ベースであれば賛成という意見が見られる。

2026-06-30

ゼロ知識セットメンバーシップ証明を可能にするCurve Treesの仕組み

zk Cryptography

最近、Moneroが計画しているメンバーシップ証明のアップグレードや、BitcoinのUTXOの所有をUTXOの情報を明らかにせずに証明する新しいスキームで見かけるようになったCurve Treesというスキームについて。

https://eprint.iacr.org/2022/756.pdf

Curve Treesは、要素が集合に含まれていることを、要素やマークルパスを明かさずに証明できるよう設計されたデータ構造および証明スキームである。通常のマークルツリーは証明時にマークルパスを公開する必要があるが、Curve Treesでは各ノードをPedersen Commitmentとして構成することで、パス全体をゼロ知識で証明できる。

Curve Treesの仕組み

Curve Treesでは、Shallow Merkle Treeと呼ばれる深さの浅いマークルツリーを使用する。l分木のツリー（l ≧ 2）で、lを大きく取って深さDを浅くする。これは各階層についてゼロ知識証明を行うため、深さDが小さいほど証明サイズや証明時間を抑えられるから。例えば、 ${N = 2^{32}, l = 256, D = 4}$ 。ツリーのリーフはセットの要素で、コミットされた値を表す楕円曲線上の点になる。

リーフの親ノードは、l個の子ノードを束ねたこれも１つの楕円曲線上の点になる。具体的には、

l個の子について、子の（x, y）座標に対して、2l個の独立した生成元 ${G_{x, j}, G_{y, j}}$ を割り当て、各座標値を対応する生成元に乗算した2l個の点と
ランダムなブラインドファクターrと点Hを使って求めたrH

を合算した点が親ノードを表すコミットメントになる。子ノード ${\hat{C}_j}$ の座標を ${\hat {C}_j = (x_j, y_j)}$ とすると、l = 256の場合、親ノードCは

${C = x_1 \cdot G_{x, 1} + x_2 \cdot G_{x, 2} + ... + x_{256} \cdot G_{x, 256} + y_1 \cdot G_{y, 1} + y_2 \cdot G_{y, 2} + ... + y_{256} \cdot G_{y, 256} + r\cdot H}$

となる。

2-cycle曲線

このリーフノードからツリーのルートまで親ノードを計算する際に、2-cycle曲線というものを採用している。

楕円曲線暗号では、

曲線そのものを定義する基礎体（base field）：曲線 ${E: y^{2} = x^{3} + ax + b (a, b \in \mathbb F_q)}$ の係数a, bおよび曲線上の点の座標(x, y)が存在する体 ${\mathbb F_q}$ と
スカラー体（scalar field）： ${k \cdot P}$ のように点をk倍する際のスカラー値kが存在する体。

という2つの異なる体が存在する。

先程リーフの親ノードCを計算した例では、

各 ${x_{j}, y_{j}}$ は基礎体の元だが、それらをPedersen Commitmentではスカラー値（スカラー体の元）として使用する
結果は曲線上の点なのでCの座標は基礎体の元

となる。

ここで、2つの楕円曲線 ${E_1, E_2}$ があり、

${E_1}$ は有限体 ${\mathbb F_p}$ 上に定義され、
${E_2}$ は有限体 ${\mathbb F_q}$ 上に定義され

さらに、

${E_1}$ の群の群位数がq（スカラー体が ${\mathbb F_q}$ ）
${E_2}$ の群の群位数がp（スカラー体が ${\mathbb F_p}$ ）

となる場合、この2つの曲線は2-cycleを形成する。ここでpとqはともに素数。

先程のリーフの計算に用いた各 ${x_{j}, y_{j}}$ を ${\mathbb F_q}$ とした場合、2l個の生成元は ${E_1}$ 上の点で、Pedersen Commitmentの結果Cも ${E_1}$ 上の点となる。しかし、Cを子としたさらにその親を計算する場合、Cのスカラー値(x, y)はpの元であり、 ${E_1}$ のスカラー体は ${\mathbb F_q}$ なので、 ${\mathbb F_p}$ の座標値をそのままスカラーとして利用できない。そのため、親の層では異なる2l個の生成元が必要になる。これに対応するために、2つの楕円曲線の2つの体が切り替わる2-cycle曲線を利用する。 ${\mathbb F_p}$ の元で、Cを計算したときとは異なる ${E_2}$ 上の2l個の生成元を使って同様の計算を行う。つまり、ツリーの階層毎に、ノードの楕円曲線 ${E_1, E_2}$ が入れ替わるような構造になる。このため、各層で得られたノードの座標を、そのまま親層のPedersen Commitmentの係数として利用できる。

Permissible Pointによる最適化

ツリー全体では、上記の2-cycle曲線により2l個×2の生成元を必要とするが、y座標を省略してx座標のみで処理するよう最適化するのがPermissible Pointのアプローチ。基本的に点P = (x, y)において、同じx座標を持つ点はもう1点-P = (x, -y)となる点。

Bitcoinなどでよく見られる点の圧縮では、

x座標とy座標が偶奇どちらを示すかを表す符号bitを付与することで点のエンコードサイズを約半分に圧縮表現や
Taprootのx-only公開鍵ではルールとしてyは偶数であることを強制することでx座標のみをエンコードする（一方の秘密鍵を持っていれば、もう一方の秘密鍵も計算可能なので）

といった手法が用いられている。

Permissible Pointは、少しx-only公開鍵と似ていて、ある述語を満たす点として定義し、その結果を満たすのが (x, y)および (x, -y)のいずれかになる。x座標のみを使用するため、コミットメント値は

${C = \sum\ x_{j} \cdot G_{x, j} + r \cdot H}$

となるが、このとき、x座標に対応するPedersen部分は固定されるため、述語を満たすようにブラインド値rのみを調整する。

述語はペアのちょうど一方だけが満たす判定式である必要がある。ただ、yが偶数とか数値的に小さい方といった整数ベースの判定は、有限体上で算術回路に落とすとビット分解が必要で高コストになるため、論文では平方剰余性に基づく判定を採用している。

メンバーシップ証明とゼロ知識性

任意の値にコミットしたリーフ（要素）を用いて上記の浅いツリーを代数的ハッシュ（Pedersen Commitment）で構築したら、そのツリー内に要素があるかどうかメンバーシップ証明を提供する。なお、以降は、Permissible Pointにより各ノードをx座標のみで表す。

一般的なマークルツリーでは、リーフとツリーのルートまでの兄弟ノードのリストをパスとして提供することでメンバーシップの証明が可能だが、これだとリーフの情報とルートまでのパスが明らかになってしまう。

Curve Treesは、リーフもそのメンバーシップ証明であるマークルパスも隠した状態でメンバーシップを証明するための仕組み。秘匿されないのはツリーのルートだけ。

まず、パス上の各ノードのコミットメント ${C_i}$ について、同じコミットメントをそのまま公開するとパス上のノードが特定されるため、層ごとに独立した新しい乱数 ${\rho'_i}$ を使って再ランダム化したコミットメント ${\hat{C}_i = C_i + \rho'_i \cdot H}$ を計算する。ここで各子 ${V_j}$ は層の曲線上の点で、そのx座標を ${x_j}$ とする。そしてツリーの各層iについて、以下の2つの関係をゼロ知識で証明する。

コミットメントの関係：親が子全体をコミットしていることを証明する。 ${\hat{C}_{i-1}}$ が子 ${V_1, ..., V_l}$ の再ランダム化したコミットメントであること。つまり、 ${\hat{C}_{i-1} = \sum x_j \cdot G_{x, j} + (r_{i-1} + \rho'_{i-1}) \cdot H}$ 。
選択の関係：自分が1の子の1つであることを証明する。ある隠れたインデックスjが存在し、 ${\hat{C}_i = V_j + \rho'_i \cdot H}$ を満たすこと。つまり、層iでパスが通るノードは、層i-1のノードが束ねるl個の子のうちj番目の子である（ ${C_i = V_j}$ である）。

この2つをルートから層Dまで繋ぐとルートからリーフへの一本のパスが、どのノードを通ったかを一切明かさずに証明される。これらの2つの関係は算術回路として表現し、Bulletproofsで証明する。実装によっては、回路内でPedersen Commitmentを直接扱えるよう拡張したGeneralized Bulletproofsが用いられる(Monero FCMP++など)模様。

1については、

再ランダム化された親のコミットメント ${\hat{C_{i-1}}}$ と公開パラメーターである生成元を公開入力とし、
l個の子のx座標と合算ブラインド値 ${r_{i-1} + \rho'_{i-1}}$ をwitnessとして

上記の等式が成立することを回路でチェックする。つまりl個の項からなるマルチスカラー倍算の検算処理。

2については、

層iの再ランダム化コミットメント ${\hat{C_{i}}}$ と公開パラメーターである生成元を公開入力とし、
インデックスj（j番めだけが1で他はすべて0のベクトル ${b_k \in \lbrace 0, 1 \rbrace}$ ）と選ばれた子のx座標と再ランダム化の乱数 ${\rho'_i}$ をwitnessとして

witnessのベクトルが1つだけ1で他はすべて0であることを強制し（ ${b_k(b_k - 1) = 0}$ かつ ${\sum b_k = 1}$ ）、選ばれたx座標を1のwitnessから取り出す（ ${x_j = \sum_{k=1}^{l} b_k \cdot x_k}$ ）。これで ${x_j}$ は確かに親が束ねた子の1つであることが回路内で保証される。選ばれた ${x_j}$ に対応する層iの曲線上の点を ${C_i}$ とすると、公開入力 ${\hat{C_{i}}}$ について ${\hat{C}_i = C_i + \rho'_i \cdot H}$ が成立するかチェックする。これは ${C_i}$ と ${\hat{C_{i}}}$ の差がHの ${\rho'_i}$ 倍であること、すなわち再ランダム化の整合の証明で、単一のスカラー倍算で済む。

この2つにより、l個の子から1つ選び、それを乱数で隠して次層に渡したことが、位置も値も伏せたまま証明される。

このようにCurve Treesでは、「親が子全体をコミットしていること」と、「その子のうち1つを選んで次の層へ渡したこと」を各層でゼロ知識証明することで、リーフやマークルパスを一切公開することなくメンバーシップを証明できる。

2026-06-23

GoogleのLongfellow-ZKのRubyバインディングを作ってmdocの選択的開示を試してみた

zk Cryptography Ruby

以前、Googleが公開したP-256のようなNTTに適していないNISTの曲線でも、LigeroとSumcheckを組み合わせてmdoc（mDL）の選択的開示をゼロ知識証明可能にする発表について書いた↓

techmedia-think.hatenablog.com

このスキームはGoogleがgoogle/longfellow-zk というC++ライブラリとして実装・公開している。今回はそのRubyバインディングをlongfellowというgemとして実装したので、実際にmdocから「18歳以上である」というプルーフを生成して検証するところまでを動かしてみた。

longfellow-zkのRubyバインディング

longfellow-zkはC++のライブラリで、mdoc/mDLの匿名認証のためにC ABI（run_mdoc_prover / run_mdoc_verifier / generate_circuit など）を公開している。今回のgemは、このC ABIをRuby-FFI 経由で呼び出すことで、Rubyからプルーフの生成・検証をできるようにしたもの。

バインディングしたlongfellow-zkは現時点の最新タグv0.9ベースで、公開しているZKシステムは longfellow-libzk-v1。mdoc/mDLのC ABI（circuits/mdoc/mdoc_zk.h）のみをラップしている（JWT/W3C VCについてはまだ開発・テスト中のようでCのABIが公開されていない）。

ネイティブライブラリはgemのインストール時にsubmoduleで同梱しているソースからビルドされる。ビルドにはC++17コンパイラ、CMake、OpenSSL（libcrypto）、zstdが必要↓

$ sudo apt-get install build-essential cmake clang libssl-dev libzstd-dev

$ git clone https://github.com/azuchi/longfellow.git
$ cd longfellow
$ git submodule update --init --recursive
$ bundle install
$ bundle exec rake compile

仕組みの全体像

実際にコードを見る前に、前回の論文の内容とAPIの対応を整理しておく。証明者と検証者がやり取りする流れはこうなる↓

zk_spec：どの回路フォーマット（開示する属性数やバージョン）を使うかを表す仕様。ライブラリにハードコードされている。
circuit：zk_spec から決定的に生成される算術回路のバイト列。論文でいう「ECDSA署名検証回路 + SHA-256回路 + CBORパース回路」を組み合わせたもの。決定的なのでキャッシュして証明者・検証者で共有できる。
公開入力：発行者の公開鍵 pkx/pky（x, y座標）、セッショントランスクリプト transcript、開示する属性 attributes、現在時刻 now。検証者も知っている値。
秘密入力（witness） ：mdoc全体とデバイス署名。証明者だけが持っていて、prove に渡すが verify には渡さない。

verify の引数には mdoc本体が出てこないのがポイント。証明者はmdocを開示せずに「age_over_18 = true を含む有効なmdocを持っている」ことだけを証明する。これが前回書いたリンク不能性を実現するための重要な要素。

ZkSpec を選ぶ

まずどの回路仕様を使うかを選ぶ。zk_spec はライブラリにハードコードされていて、Longfellow.zk_specs で一覧できる↓

require "longfellow"

Longfellow.zk_specs.each_with_index do |s, i|
  printf("[%2d] system=%s version=%d attrs=%d hash=%s...\n",
         i, s.system, s.version, s.num_attributes, s.circuit_hash[0, 16])
end

[ 0] system=longfellow-libzk-v1 version=7 attrs=1 hash=8d079211715200ff...
[ 1] system=longfellow-libzk-v1 version=7 attrs=2 hash=6a5810683e62b6d7...
[ 2] system=longfellow-libzk-v1 version=7 attrs=3 hash=8ee4849ae1293ae6...
[ 3] system=longfellow-libzk-v1 version=7 attrs=4 hash=5aebdaaafe17296a...
[ 4] system=longfellow-libzk-v1 version=6 attrs=1 hash=137e5a75ce72735a...
 ...
[11] system=longfellow-libzk-v1 version=5 attrs=4 hash=fa5fadfb2a916d3b...

v0.9 には全部で12個の仕様が入っていて、バージョン（7/6/5）*1× 一度に開示できる属性数（1〜4）の組み合わせになっている。circuit_hash はその回路の識別子（後述の circuit_id と一致する）。

今回は「18歳以上」を1つだけ開示したいので、属性数1の最新版 kZkSpecs[0] を使う↓

spec = Longfellow.zk_specs.first
# => #<Longfellow::ZkSpec longfellow-libzk-v1 v7 attrs=1 hash=8d079211...>

システム名と回路ハッシュから引くこともできる↓

spec = Longfellow.find_zk_spec("longfellow-libzk-v1",
                               "8d079211715200ff06c5109639245502bfe94aa869908d31176aae4016182121")

回路を生成する

選んだ zk_spec から算術回路を生成する。これは決定的な処理で、証明者・検証者の双方が同じ結果を得る。一度生成すればキャッシュして使い回せる↓

circuit = Longfellow.generate_circuit(spec)
circuit.bytesize
# => 299152

# 回路の識別子（SHA-256ベース）は spec.circuit_hash と一致する
Longfellow.circuit_id(circuit, spec).unpack1("H*")
# => "8d079211715200ff06c5109639245502bfe94aa869908d31176aae4016182121"
spec.circuit_hash
# => "8d079211715200ff06c5109639245502bfe94aa869908d31176aae4016182121"

circuit_id が spec.circuit_hash と一致することで、「自分が手元で生成した回路が、相手が想定している回路と同一である」ことを確認できる。改ざんされた回路を掴まされていないかのチェックになる。

自分の環境では generate_circuit に約9.5秒かかった。生成された回路は約299KB（299,152バイト）。これは内部的には2つの回路（後述する署名検証回路 sig 約5.8MBと、SHA-256回路 hash 約93MB）を1つのバッファに連結した約99MBを、まとめてzstd*2で圧縮した結果になっている。つまり circuit.bytesize の299,152バイトには 両方の回路が含まれている（circuit_id がこのバンドルを2つの回路に分けてパースするのもそのため）。回路生成はそれなりに重いので、実運用では生成済みの回路を配布・キャッシュする想定になると思われる。

開示する属性を指定する

開示する属性は Longfellow::Attribute で表す。前回触れたように、mdocの属性はCBORでエンコードされている。age_over_18 = true のCBOR表現は 0xf5（CBORの true）の1バイト↓

attribute = Longfellow::Attribute.new(
  namespace_id: "org.iso.18013.5.1", # mDLの名前空間
  id:           "age_over_18",       # 属性の識別子
  cbor_value:   "\xF5".b             # CBOR の true
)

namespace_id / id / cbor_value の3つは、前回の記事で出てきたmdocのハッシュ元データの elementIdentifier と elementValue に対応する。証明者は「この名前空間のこの属性が、この値（のCBORバイト列）を持つ」ことを回路の中で検証させる。ハッシュ値の元になっているランダムなナンスはmdoc側に入っていて、回路内で参照される。

ハッシュ・文字列の入る固定長バッファに合わせて namespace_id <= 64、id <= 32、cbor_value <= 64 バイトの上限がある。Hashで渡すこともできる↓

attributes: [{ namespace_id: "org.iso.18013.5.1", id: "age_over_18", cbor_value: "\xF5".b }]

プルーフを生成する（証明者側）

公開入力と秘密入力（mdoc）を揃えて prove を呼ぶ。今回はlongfellow-zkのテストベクター（後述）を使う↓

proof = Longfellow.prove(
  circuit:      circuit,
  mdoc:         mdoc_bytes,           # 秘密入力(witness): mdoc 全体
  public_key_x: issuer_pkx,           # 発行者公開鍵 x座標 (16進文字列)
  public_key_y: issuer_pky,           # 発行者公開鍵 y座標
  transcript:   session_transcript,   # セッショントランスクリプト
  attributes:   [attribute],          # 開示する属性
  now:          "2024-01-30T09:00:00Z", # 有効期限チェック用の現在時刻
  zk_spec:      spec
)
proof.bytesize
# => 360756

生成されたプルーフは約361KB（360,756バイト）。手元では約0.65秒で生成できた。

prove が失敗すると Longfellow::ProverError が送出される。たとえば指定した属性がmdocに含まれていない、now が有効期限の範囲外、mdocが壊れている、といったケース。エラーは#symbol とC ABIの戻り値 #code を持つ↓

begin
  Longfellow.prove(...)
rescue Longfellow::ProverError => e
  e.symbol  # => 例えば :attribute_not_found
  e.code    # => MdocProverErrorCode の整数値
end

プルーフを検証する（検証者側）

検証者側は mdocを持たずに プルーフを検証する（引数に mdoc は無い）↓

ok = Longfellow.verify(
  circuit:      circuit,
  public_key_x: issuer_pkx,
  public_key_y: issuer_pky,
  transcript:   session_transcript,
  attributes:   [attribute],
  now:          "2024-01-30T09:00:00Z",
  proof:        proof,
  doc_type:     Longfellow::DEFAULT_DOC_TYPE, # "org.iso.18013.5.1.mDL"
  zk_spec:      spec
)
# => true

検証は成功すると true を返す。手元では約0.31秒だった。失敗時は Longfellow::VerifierError を送出する。試しにプルーフの最後の1バイトを反転させてみると、ちゃんと検証に失敗する↓

tampered = proof.dup
tampered[-1] = (tampered[-1].ord ^ 0xFF).chr

Longfellow.verify(circuit:, ..., proof: tampered, ...)
# => Longfellow::VerifierError: run_mdoc_verifier failed: general_failure (code 5)

内部では何が起きているか

ネイティブライブラリは実行時に内部のログをstderrに吐くので、プルーフ生成中のログを見ると前回の論文の内容との対応が確認できる。prove 実行時の主要なログを抜粋すると↓

Compiled circuit: sig
  depth: 22 wires: 223876 in: 3739 out:90 ...
sig bytes: 5834530 id:2845210a...

Compiled circuit: hash
  depth: 18 wires: 3452075 in: 85118 out:2 ...
hash bytes:98932952 id:58248d20...    # ← sig+hash の累積サイズ
zstd from 98932952 --> 299152         # ← 両回路まとめて圧縮

ZK Commit start
ZK Commitment done
...
ZK sumcheck done
ZK hash proof done
...
ZK sumcheck done
ZK signature proof done

com:32, sc:18656, com_proof:142472 ...: 161160b
com:32, sc:36032, com_proof:163436 ...: 199500b
proof_len: 360756

ここから読み取れることは、

回路が sig（署名検証回路） と hash（SHA-256回路） の2つに分かれてコンパイルされている。これは前回書いた「ECDSA署名検証回路」と「SHA-256回路」に対応する。ここで「3つ目のCBORパース回路はどこに行った?」と思うけど、CBORパースは独立した回路ではなく hash 回路に吸収されている。hash 回路の実体（mdoc_hash.h）はCBORデコーダ（cbor_parser）を取り込んでいて、「MSOが正しいCBOR構造になっていること」と「その中のダイジェストがSHA-256と一致すること」を一体で検証する。だから hash 回路は純粋なSHA-256ではなく「SHA-256 + CBORパース」で、これが下で見るように巨大になる一因でもある
hash 回路がwires約345万・約93MB（sigの5.8MBに対して約16倍）と圧倒的に大きい。SHA-256のラウンド関数を回路化するとこれだけ巨大になる、というのが前回の「1ブロックで約13万要素」という話の実例になっている。なお hash bytes:98932952（≈99MB）は sig と hash を連結した累積サイズで、zstd from 98932952 --> 299152 はこの両回路をまとめて約299KBに圧縮したログ。circuit.bytesize の299,152バイトがこのバンドルにあたる。
ZK Commit（Ligeroのコミットメント）→ ZK sumcheck（Sumcheckプロトコル）→ proof という流れになっていて、これも前回の「実行トレースをLigeroでコミットし、回路の検証をSumcheckで行う」という構成そのもの。
最終的なプルーフ（360,756バイト）は [96バイトのMAC][hashサブプルーフ][sigサブプルーフ] という並びになっている。hashサブプルーフ（161,160バイト）+ sigサブプルーフ（199,500バイト）= 360,660バイトで、proof_lenとの差96バイトが先頭のMAC。この96バイトが、論文の「ECDSAとSHA-256の回路は異なる体で動作するため、各回路の入力整合性をMACで検証する」で言っていた、2つの回路を繋ぐMACそのもの。2回路が共有する入力は 3つ（署名対象 e とデバイス公開鍵の dpkx / dpky）で、いずれも P-256 の体 Fp256 の要素＝256ビット。一方 MAC は hash 回路側の体 ${ GF(2^{128})}$ で計算するため、128ビットの要素1個では256ビットの値を認証しきれず、1入力あたり ${ GF(2^{128})}$ 要素を2個使う（コードにも f_128::kBits * 2 >= Fp256Base::kBits のチェックがある）。結果、3入力 × 2要素 × 16バイト = 96バイト。
おもしろいのが、hash 回路は93MB・sig 回路は5.8MBと規模が約16倍違うのに、サブプルーフのサイズは hash 161KB < sig 199KB と逆転している点。これは2段階で効いている。まず Ligero+Sumcheck のプルーフサイズは回路のワイヤ数に対して劣線形なので、16倍というワイヤ数の差はプルーフの段階で大きく縮む。そのうえで効いてくるのが体の要素サイズで、sig 回路はP-256の体 Fp256（要素256ビット = 32バイト）、hash 回路は標数2の体 ${ GF(2^{128})}$ （要素128ビット = 16バイト）で動くため、要素1個あたり sig 側が2倍大きい。縮んだうえで要素サイズ差が乗ることで、ワイヤの多い hash より sig のプルーフが上回る。実際ログから、Sumcheck部分は sc が sig:36032 / hash:18656 ≈ 1.93倍 ≒ 要素サイズ比2倍、コミットメント開示も com_proof が 163436/142472 ≈ 1.15倍で、ワイヤ数で勝るはずの hash 側を sig 側が要素サイズで逆転しているのが数字から分かる。

論文を読んだだけだと抽象的だった「回路を層に分割してSumcheckで検証する」「2つの回路をMACで繋ぐ」あたりが、実際に動かしてログを見ると具体的なサイズ感を持って腑に落ちる。

テストベクターについて

上の例で使ったmdoc・トランスクリプト・公開鍵は、同梱したlongfellow-zkのテストベクター（lib/circuits/mdoc/mdoc_examples.h）から抽出したもの。gemのリポジトリでは spec/fixtures/mdoc_example_0.txt として持っていて、age_over_18 = true を含むGoogleのテスト用mDLになっている。

実際のプルーフ生成・検証のラウンドトリップは :slow タグ付きのintegration specとして用意してあるので、手元で動かす場合は↓

$ bundle exec rake compile          # ネイティブライブラリのビルド
$ bundle exec rspec --tag slow      # 実際の prove -> verify ラウンドトリップ

論文を読むだけだと掴みにくかった部分も、実装を叩いて動かすとサイズ感や処理の流れが具体的になってよかった。JWT/W3C VCも早く使えるようになるといいな。

*1:回路のフォーマットやその解釈に互換性を壊す変更が入るたびに、新しいバージョン番号が振られている

*2:Facebookが開発したデータ圧縮アルゴリズム/ライブラリ。可逆圧縮で、高速かつ高い圧縮率を両立しているのが特徴で、近年広く使われているみたい。

2026-06-06

Zcash Orchardプールの脆弱性

Zcash vulnerability zk

先日発見されたZcashの脆弱性について↓

zfnd.org

Zcash Orchardプールのバグ

脆弱性の原因は、Orchardプールのzk証明回路（Action circuit）の制約不足によるもので、これにより無効な状態遷移が可能になりシールドプール内での二重使用のリスクが存在した。

プール

OrchardというのはZcashの3世代めのシールドプール。プールというのは秘匿された金額と状態の集合で、Bitcoinで言うUTXOセットのようなもの。現在のZcashの秘匿コインのシールドプールは、以下の3種類が存在する。

Sprout（2016年）：最初のシールドプールで、libsnark系の証明システムを採用しBN254曲線上で動作。Trusted Setupを必要とし、シールドトランザクションの生成に3GBのRAMを必要とし生成に数十秒かかる。※ちなみにこのSproutの実装にも偽造脆弱性（CVE-2019-7167）が発見されており、この種のバグは今回が初めてではない。
Sapling（2018年）：Groth16ベースの証明システムを採用し、BLS12-381曲線に刷新。回路内の楕円曲線演算には埋め込み曲線 Jubjubを使い、コミットメントは効率の良いPedersen系へ移行。これによりプルーフの生成が数秒・低メモリになり、モバイルでのシールド送金が現実的に。
Orchard（2022年）：今回のバグが発見されたプールで、証明システムをHalo 2を採用し、Pasta曲線を採用しTrusted Setupを排除。コミットメントおよびハッシュには楕円曲線ベースで回路内でのコストが低いSinsemillaを採用。

各プールのコインは、新世代のプールへの移行が推奨されてきた（特にSproutは偽造バグがあったため）。ただ、新世代のプールが利用可能になっても、古いプールにもコインは残っており、コンセンサスルール上、今も3つのプールが並行して有効なまま。Bitcoinで言うと、Segwitが導入されてもレガシーなP2PKH/P2SHにコインが残っているようなもの。

なお、各プールはそれぞれ独立したノート形式・コミットメントツリー・nullifierセット・回路を持つ。Bitcoinなどでは透過的な世界でScriptと明示的な金額のチェックが担っていた検証を、シールドプールではまるごと回路（とそれを検証する証明システム）が肩代わりしている。検証者には金額もノート本体も見えず、見えるのは回路の検証鍵に対してそのプルーフが通るかどうかだけ。つまり回路はそのプールのコンセンサスルールそのもので、そのため今回の制約不足は致命的な影響があった。

今回の脆弱性

今回の脆弱性は、OrchardのHalo 2の回路の実装の問題。正確には、Halo 2の証明システム本体ではなく、回路実装をまとめた halo2_gadgets crateのecc::chip::mul（楕円曲線のスカラー乗算ガジェット）のなかにあった。本来弾くべき無効な入力が検証を通ってしまう種類のバグで、制約不足の典型例にあたる。

Zcashの開示によると、根本原因はecc::chip::mulで行われる楕円曲線上の点のバイナリ法を用いたスカラー倍算のチェック処理。バイナリ法は、ループ処理でスカラー値のビットを1 bitずつ見ながら、途中結果を2倍し、bitが立っていればそれを加算するという計算を繰り返す処理（詳細は以前の記事参照）。

問題となったのは、計算を始める際の基点となる点の固定処理。上記のバイナリ法ベースでざっくり言うと、スカラー値を5とした場合、5Gを計算するところ、ループ内で足し込む点が本当に基点Gであるという固定がなく、Gの代わりに別の点Hを使った5Hを計算してもパスしてしまう、というもの。このHが攻撃者の自由に選べる任意の点であるのが攻撃可能なポイント。

もう少し具体的には、Zcashの回路は制約の数を削減してコストを下げるために、バイナリ法のループの最初・最後と、ループ内の処理とで内容を切り替えるハイブリッドな構成をとっている。本来は各区間が参照する点を入力の基点Gに固定する必要があるが、このうちループ内区間の固定が欠けていた。

結果として、証明者は基点とは異なる自由な定数Hに対してループを走らせることができ、ガジェットの出力が本来のスカラー・Gではなく、a・G＋b・Hになり得る、つまり「x倍した」と称しながら、まったく別の点を混ぜ込めることができた。

これがOrchardの回路の値の検証（入力＝出力＋feeなど）の保証を崩し、攻撃者が偽の値で正当に見えるプルーフを生成できる状態となった。

総供給量のインフレーションは防止

ただし、この回路バグだけではZECの総供給量のインフレーションは起こせない。Zcashにはturnstileという仕組みがあって、各プール（Sprout / Sapling / Orchard / transparent*1 / lockbox*2）の境界で「これまでにそのプールへ入った価値 − 出た価値」を追跡し、プールから外へ出せる総量に上限をかけている。

そのためOrchardプール内部では偽造・二重使用の可能性はあるけど、プールから外へ持ち出せる総量（上限）は崩せない。

ただ、直近だとシールドされているコインの各プールの内訳は、

Orchard：約450万ZEC（シールド分の約88%）
Sapling：約59.2万ZEC（約12%）
Sprout：約2.5万ZEC（0.5%未満）

なので、影響は大きい。

対応

対応は2段階で行われた模様。直接パッチを最初に公開すると、更新後のコードから欠陥の性質が露見し、修正完了前に悪用される恐れがあるため、まずOrchardを止める→落ち着いてから回路を直すという順序が取られた。

悪用の可能性は？

バグ自体は修正されたけど、現状mainnetでの悪用の証拠はない一方、悪用が無かったことを暗号学的に証明する手段も存在しないとされている。過去のトランザクションについて修正後の回路でリプレイすれば、新しい制約に違反するtxがあるかは判定でき、見つかれば悪用は確定すると思ってるんだけど、暗号的に証明できないとされている理由がよく分かっていない。

turnstileによって供給量の上限は保たれるものの、シールド供給のほとんどを占めるOrchardプールにおける問題というのは重そう。強力なプライバシーと供給の検証可能性が原理的に両立しにくいので難しいよね。でもこういう事件を経て、プールに偽造が存在しないことを誰もが暗号的に検証できる会計機構を組み込むようなアプローチが進んでいくんだろう。

*1:シールドされていない＝秘匿されていないコインのプール

*2:2024年に導入された特殊なプールで、開発資金を一時的に保持しておくプロトコルレベルのプール

2026-05-30

ニーモニックを物語にするBIP-450 Formosaの仕組み

BIP Bitcoin

Bitcoin含め多くの暗号通貨では、HDウォレットで秘密鍵を管理することが多い。そのマスターシードを12個や24個のニーモニックと呼ばれる単語リストから導出する。マスターシードのような巨大な数値を覚えるよりは単語のリストの方が覚えやすいけど、なんの脈絡もない単語のリストも覚えやすいものではない。そこで、シードを物語を綴るようにピックアップして無関係な単語の羅列よりは記憶の手がかりが多く、転記もしやすい形にしようというのが最近BIP-450として定義されたFormosa↓

https://github.com/bitcoin/bips/blob/master/bip-0450.mediawiki

BIP-39のニーモニック

まず、前提としてBIP-39ニーモニックは、ランダムなエントロピーと人が読みやすい単語リストを相互変換する仕組み。

エントロピーから単語リストを導出するステップは↓

128〜256 bit（32の倍数）のエントロピーを生成し（ENTとする）、
そのSHA-256ハッシュ値の先頭ENT/32 bitをチェックサムとして、エントロピーの末尾に付与する
連結したビット列を11 bitずつに分割し、
各11 bit(0〜2047)を、2048個の単語リストのインデックスとして解釈して、単語のリストに変換する。

よくある128 bitのエントロピーの場合、チェックサムは4 bitで合計132 bit = 11 bit × 12＝12単語という対応になる。

そしてニーモニックからシードを導出するステップは↓

単語リストを半角スペースで区切って1つの文字列としてNFKDで正規化しパスワードとし、
mnemonicという文字列＋パスフレーズとしてNFKDで正規化しsaltとして、
1と2を使ってPBKDF2を実行する（反復回数：2048, 出力長：64 byte）
得られた512 bitがシード

Formosa

Formosaは上記のニーモニックの単語リストを構文的な役割（主語、動詞、形容詞、目的語、場所など）を持つ文章に編成する。このとき、各文は一貫した意味領域（中世のファンタジー、SF、自然、金融またはカスタムテーマ）から語彙が選ばれる。

まず、Formosaで使用される用語の定義は↓

単語（word）：あるカテゴリの単語リストから引かれた単一のトークン（例:dragon）
カテゴリ（category）：独自の単語リストと固定ビット幅を持つ構文的役割（例：主語、動詞、場所）
テーマ（theme）：（BIP-39の単語リストに相当する）1つのFormosa方言を定義するカテゴリ・単語リスト・ビット幅・順序ルール・制約の完全な集合。
文（sentence）：（BIP-39の3単語文に相当する）単一の33ビットエントロピーブロックを符号化することで1つのテーマから選択される単語群。
ニーモニック（mnemonic）：エントロピーとチェックサムをまとめて符号化するすべての文を順序付きで連結したもの。

BIP-39ではピックアップした単語リストをニーモニックと呼ぶのに対し、Formosaでは複数の文で構成されるものをニーモニックまたはニーモニックストーリーと呼ぶ。

簡単に説明すると、まず使用したいテーマを選択するとそのテーマにはカテゴリが定義されていて、エントロピーから生成したチェックサム付きのハッシュ値のデータを使って、各カテゴリーの中からルールに従って単語をピックアップして文章として完成させていくために上記の構成要素が使われる。

テーマの構造

テーマはJSONで定義され、以下を持つ

順序付きのカテゴリリスト。各カテゴリはそれぞれ以下を持つ
- 単語リスト
- BIT_LENGTH（このカテゴリが符号化するビット数、単語リストの方は2^BIT_LENGTH個のエントリーが必要）
- LED_BY（オプション）：あるカテゴリの単語リストを、別の先導カテゴリで選ばれた単語に依存させる仕組み
FILLING_ORDER：エントロピーからbitを消費していく順番
NATURAL_ORDER：選択された単語を実際に表記する順番

そしてテーマの全BIT_LENGTHの合計は必ず33 bitになる。

LED_BYが重要で、たとえば主語がkingなら目的語のリストは王様にふさわしい語彙だけというように、文脈に応じて単語リストを差し替えることができる。この仕組みによって意味がとおるような文章を作ることができる。

なぜ33 bitなのか？

BIP-39では、上述したようにエントロピーENTにENT/32のチェックサムが付くので、連結後のbit列は必ず33の倍数になる。Formosaが文のサイズを33 bitに揃えているのはこのため。どんなテーマであっても、BIP-39とまったく同じエントロピー＋チェックサムの境界に無損失で乗せられる。これにより後方互換性が保たれる。

標準テーマ

Formosaでは以下が標準テーマとして用意されている。

テーマ	意味領域	カテゴリ数	1文のbit数	備考
BIP39	(BIP-39そのもの)	1	11	2048語の英語の単語リスト。既存BIP-39ニーモニック互換
BIP39_french	(BIP-39仏語版)	1	11	`BIP39`のフランス語版
medieval_fantasy	中世ファンタジー	6	33	標準テーマ
medieval_fantasy_light	中世ファンタジー(軽量)	5	33	動詞なし・全カテゴリ独立(LED_BYなし)の簡易版」
sci-fi	SF	6	33	`medieval_fantasy`と同型
finances	金融	6	33	同上
copy_left	自由ソフトウェア文化系	6	33	同上
tourism	観光・旅行	6	33	形容詞が場所に従属する変則系
cute_pets	可愛いペット	6	33	目的語の代わりにワイルドカード系を使う文型
farm_animals	農場の動物	6	33	`cute_pets`と同型
nationalities	出身＋職業	5	33	文ではなく「出身×4＋職業」型。LED_BYなし
global	出身＋職業	6	33	「出身・職業のペア×2＋ワイルドカード＋場所」型

カテゴリ

文型の標準テーマのmedieval_fantasyに登場するカテゴリは↓

カテゴリ	日本語訳	BIT_LENGTH	LED_BY	先導LEADS
`VERB`	動詞	5	ルート	SUBJECT
`SUBJECT`	主語	6	VERB	OBJECT、WILDCARD
`OBJECT`	目的語	6	SUBJECT	ADJECTIVE
`ADJECTIVE`	形容詞	5	OBJECT	なし
`WILDCARD`	ワイルドカード（自由枠）	6	SUBJECT	PLACE
`PLACE`	場所	5	WILDCARD	なし

ビット幅の合計: 5 + 6 + 6 + 5 + 6 + 5 = 33。

FILLING_ORDER : [VERB, SUBJECT, OBJECT, ADJECTIVE, WILDCARD, PLACE]
NATURAL_ORDER : [SUBJECT, VERB, ADJECTIVE, OBJECT, WILDCARD, PLACE]

先導関係によりVERBをルートとするツリーが形成される。各非ルートカテゴリの単語リストは、その先導カテゴリで既に選択された単語によって選ばれるサブリストになる。

ニーモニックの生成

初期エントロピーの生成からチェックサムの計算まではBIP-39と同じ。その後連結したビット列を33 bitずつのグループに分割し、各グループが1つの文を符号化する。エントロピーが128 bitの場合、合計ビット数は132 bitなので文の数は4つ。

まず最初にどのテーマでニーモニックを作成するか決める。次に以下の処理で各グループのビット値から文を生成する。

テーマのカテゴリ数分のスロットを持つ空の配列を用意し、
FILLING_ORDERの順に、各カテゴリCに対して以下を行う。
1. ビット値の先頭C.BIT_LENGTH bitを読み取り、符号なしのビッグエンディアン整数iとして解釈する。
2. Cの単語リストを解決する：
  - LED_BYがなければ、Cのフラットな単語リストをそのまま使う。
  - LED_BY = Lがあれば、既に選択されているLの単語をキーにしてCのマッピングから対応するサブリストを取り出す。
3. 解決したリストのi番めの単語をCのスロットに入れる。
全てのカテゴリについて処理を終えたら、スロットをNATURAL_ORDERの順に並べ替えて出力する。これが1文。

どのビットがどのカテゴリになるかはFILLING_ORDERで決まり、読み上げ順NATURAL_ORDERとは異なる。

たとえば、テーマmedieval_fantasyでは、以下の33 bitの値は、

33 bitブロック: 11100 100000 111111 11011 101110 11101
               VERB SUBJECT OBJECT ADJ. WILDCARD PLACE
                (5)   (6)    (6)   (5)   (6)     (5)

のように割り当てられ、

VERBでは、インデックス11100 = 28のunveilを選択し、
SUBJECTでは、100000 = 32かつLED_BY VERBなのでunveilをキーとするサブリストを参照して、そのインデックス32であるkingを選択
OBJECTでは、111111 = 63かつLED_BY SUBJECTなのでkingをキーとするサブリストを参照して、そのインデックス63であるwineを選択
ADJECTIVEでは、11011 = 27かつLED_BY OBJECTなのでwineをキーとするサブリストを参照して、そのインデックス27であるsweetを選択
WILDCARDでは、101110 = 46かつLED_BY SUBJECTなのでkingをキーとするサブリストを参照して、そのインデックス46であるqueenを選択
PLACEでは、11101 = 29かつLED_BY WILDCARDなのでqueenをキーとするサブリストを参照して、そのインデックス29であるthrone_roomを選択する。

こうして選択された単語をNATURAL_ORDER順に並べると、

king unveil sweet wine queen throne_room
（王が玉座の間で女王に甘いワインを披露する）

となる。128 bitの場合、4つの33 bit値に対して上記を繰り返し、4つの文で構成されるニーモニックストーリーが生成される。

復号プロセス

ニーモニックストーリーからエントロピーを復元する手順は上記のプロセスを反転させたもの。

ニーモニックストーリーを単語に分割し、
単語列をテーマの1文あたりの単語数ごとにグループ分けし、
各文を33bitに復号する。
復号したすべての33 bitデータを順に連結して１つのビット列に戻す。
ビット列をエントロピー部分とチェックサム部分に分割し、
エントロピーのハッシュ値から計算したチェックサムと5のチェックサムが一致するか検証

シードの導出はBIP-39を利用

Formosaは、あくまでニーモニックを覚えやすい形にするだけで、シードの導出はこれまでどおりBIP-39を使用する。つまり、Formosaのニーモニックストーリーから直接シードは生成されない。上記で復号したエントロピーで、BIP-39のニーモニックワードに変換した上でBIP-39のルールに従ってシードを導出することになる。

これはシードをテーマとは関係なくエントロピーだけの関数にすることで、同じエントロピーを使ってどのテーマでニーモニックストーリーを作ったとしても、同じエントロピーなら必ず同じシード・同じ鍵・同じアドレスを導出することができるようにするため。なので、Formosaはニーモニックの見た目のレイヤーを改善するための技術とも言える。

安全性

Formosaを見て「単語数が12から24に倍増しているぶん、覚える情報が増えて大変なのでは？」あるいは逆に「文法で縛っているぶん、組み合わせが減って弱くなるのでは？」と思うかもしれないけど、安全性はBIP-39とまったく同じ。理由は以下↓

安全性の源泉はエントロピーであって単語数ではない

鍵の強度を決めるのは最初に生成した128〜256 bitのエントロピーで、これはBIP-39でもFormosaでも変わらない。128 bitなら、BIP-39の12単語もFormosaの24単語も、表しているのは同じ128 bit。単語数が倍なのは「無関係な12単語」を「意味の通る24単語の物語」に置き換えているからで、情報量が倍になったわけではない。だから総当たり攻撃に対する強度は同じ。

意味で縛っても情報量は1 bitも減らない

LED_BYで「主語がkingなら目的語は王様にふさわしい語彙だけ」というように候補を絞っても、各サブリストの要素数は必ず2^BIT_LENGTH個ぴったりに保たれる。主語が変わればサブリストの中身は入れ替わるけど、個数は固定なので、表現できる総パターンはすべてを漏れなくカバーされる。エントロピーと文は全単射なので、意味的なフィルタをかけているのに情報量は落ちない。

シード導出が同一なので鍵もアドレスも完全一致

前述のとおりFormosaはシード導出時に一度BIP-39へ再符号化してからPBKDF2にかける。シードはテーマではなくエントロピーだけの関数になるので、同じエントロピーから導かれる鍵・アドレスはBIP-39と1ビットも違わない。PBKDF2のパラメータ(HMAC-SHA512・2048回反復・salt構築)もそのまま流用されるため、BIP-39で確立された安全性の分析がそっくり引き継がれる。チェックサムの強度(ENT/32 bit)も同じ。

実際にやってみた

128 bitのエントロピーをa2b00c0ebf207d9455410278b594053dとした場合、BIP-39ベースのニーモニックは、

["pencil", "lesson", "admit", "layer", "amazing", "sketch", "fence", "cake", "judge", "protect", "access", "kite"]

同じエントロピーをFormosaのテーマmedieval_fantasyのニーモニックストーリーにすると、

1. engineer present cork kite actor tower
2. sage know voodoo antidote sage oracle
3. miner earn bamboo broom herbalist chicken_coop
4. lumberjack reach icy abacus hunter silo

1. 技師が塔で役者にコルクの凧を贈る
2. 賢者が神託所で(もう一人の)賢者に呪術の解毒剤を授ける
3. 鉱夫が鶏小屋で薬草師に竹のほうきを手に入れる
4. 木こりがサイロで狩人に氷の算盤を手渡す

というストーリーになる。4つの文で構成されるという意味的側面はあるかもしれないけど、無関係な単語のリストに比べると手がかりが多いくらいなのが現状かなー。

贅沢を言うと、文として成立させようとするのはわかるけど、複数の文との間の脈絡がないのよね。