zk-SPARQL について

検証者（ Verifier ）による要求の表現について。例えば、検疫所（ Verifier ）があなた（ Holder ）に『2022年4月以降に当局認可済ワクチンを接種していたらその接種日だけを教えてください』といったデータ要求の表現手段を考えたい。

Verifier は Holder が保有する複数 VC から必要なデータだけを要求して検証したい。また、super cookie になり得る署名値を隠したまま検証できるのがベスト。

現時点では、Verifier がこうした一定の条件で Holder が保有する複数 VC の必要なデータだけをクエリするこれといった方法が決まっていない。今回の山本さんの提案は、JSON-LD 型の VC を RDF グラフとして SPARQL クエリできるようにしたよというもの。

DID / VC を活用したソリューションを実装している関係者にとっては将来のアーキテクチャーに影響を与えるかもしれない重要な技術。RDF データを検索可能暗号化できると、Wallet と分離された PDS（VCs） を構築できるかも。ワクワクする発表でした。

ご興味のある方はぜひ添付資料をご覧ください。
山本暖さんの連絡先: dan@iij.ad.jp

発表資料

前提知識

SPARQL
RDF 用クエリ言語

SELECT 変数1 変数2 ... 変数j
WHERE
{
  RDFトリプル文.
  ～中略～
  RDFトリプル文m.
}
結果修飾語句

RDF
メタデータについて記述するデータフォーマット。主語、述語、目的語で構成。RSS や FOAF で活用されてるよ。

VC のデータフォーマット

BBS+ 署名
BBS+ 署名は BBS グループ署名を拡張したマルチメッセージ型のデジタル署名のこと。楕円曲線暗号の一種で、ペアリングという演算を活用。一般的に使われている RSA 署名や ECDSA 署名とは異なり、 複数のデータを並べたリストに署名を付けることが可能。また、ゼロ知識証明と組み合わせやすい構造を備えており、署名したデータのリストから一部の要素を隠したまま署名の有効性を検証できたり、一部の要素を隠したままそれがある条件を満たすことだけを証明することが可能。
JSON-LD ZKP with BBS+ では、JSON-LD で書かれたクレデンシャルを LD Canonicalization という方法で statement と呼ばれるデータに分解。そして statement のリストに対してBBS+署名の生成や検証を行う。BBS+ 署名を使って statement のリストに署名を付けることで、statement 単位で見せる/見せないの制御が可能。ただし、statement の中に含まれる値（氏名や生年月日など）を隠したまま、それらがある条件（例えば生年月日がある範囲に収まることなど）を満たすような高度な証明はまだ実現できない。

NIZKP
Non-interactive Zero-Knowledge Proof のこと。特に Schnorr 型と呼ばれるNIZKP は、証明者が離散対数（ A = g^a mod p ）の知識を検証者にその知識を明かすことなく証明可能なプロトコル。
証明者が離散対数（ A = g^a mod p ）の知識を検証者にその知識を明かすことなく証明するプロトコルがゼロ知識証明。対話式では検証者がチャレンジcを選択し、証明者に送る。非対話式ではこのチャレンジ c を証明者が決定論的に計算 ( c = H（g || V || A || UserID || OtherInfo）こんな感じで結合してハッシュ計算）することで、チャレンジのやり取りを省略。

解決したい課題

• 既存手法（Presentation Exchange）では VC 単位・ツリー単位のクエリしか表現できない（やろうとしているけどまだ複雑なリクエストは表現できない）

• 例えば、次のような Verifier からの要求『22年4月以降に当局認可済みワクチンを接種していたらその接種日を教えてください』に対して、グラフパターンを使った応答が実現できない

• 提案：RDF グラフに対するクエリ言語 SPARQL を使って Verifier の要求を表現する（グラフパターンを要求として表現するために SPARQL 言語を利用するということ）

Q&A

Q: データストア側で計算するFILTERの条件となる情報（例だと接種日）は、検証者に公開せざるおえないですか？どのようなアプローチがありますか？A: BBS+署名だけだとできないが、zk-SNARK, Bulletproofs等のより汎用的なゼロ知識証明技術を併せて使えば解決できる. Bulletproofsを併用することで単純な整数の範囲証明ができることは実装で確認済み.

Q: VP, zk-SPARQL, bbs+あたりってどれくらいエコシステム育ってるの？実装に必要なライブラリ、実装言語など.
A: Frontend側はTypeScript、Backend側はRustでの実装が多い印象. ニュージーランドのMATTR社や、Hyperledger ursaのライブラリをforkして実装.

Q: zk-SPARQLの計算量ってどうですか？
A: 通常のSPARQLの定数倍. 現在はWHERE節に列挙されるトリプルの数だけ, 内部で個別にSPARQLを発行しているため, 定数倍の計算時間が発生している. もっと賢い処理方法がありそうだが検討中.

Q: 昨年の発表からの差分？
A: 昨年の発表では、複数のVCを結合して選択的開示やゼロ知識証明を行い、プライバシー保護されたVPを生成するところまでお見せした. 今回は、VerifierからのVP提示要求をSPARQLクエリとして書けるようにしたり、そのクエリに回答するためのVCの組合せをHolderが自動的に探索するあたりを工夫したもの.

Q: 悪意のあるクエリが来た場合どうするの？
A: どんなクエリでも受け付けて回答してしまうと、DB中身をすべて簡単に取得されてしまう. クエリに回答すべきかどうかをHolderが判断するためのUIであったり、判断の自動化のような仕組みも必要になる。そうした仕組みや、さらには安全性の定式化や構成の安全性証明も今後の課題.  

DIF Japan について

DIF Japan とは 分散型ID の国際標準化を推進する DIF: Decentralized Identity Foundation の Japan SIG です。現在 DIF Japan を運営する仲間を募集しています。詳細はこちらからご覧ください。
DIF Japan では毎月第四金曜日9:00-10:00 ( JST ) に Monthly Call を開催しています。

Monthly Call Schedule (2023.02.03時点）

• 2月3日（金）9:00-10:00 / zk-SPARQL: SPARQLクエリに対して検証とプライバシ保護が可能な結果を返すパーソナルRDFデータストア / Dan Yamamoto

• 2月24日（金）9:00-10:00 / M2MコミュニケーションにおけるDIDCommの実装と技術優位性 / Masayoshi Mitsui

• 3月31日（金）9:00-10:00 / Selective Disclosure JWT (SD-JWT) の実装 / Kazuhide Yasukata / Yumin Haku

ご関心のある方はぜひ気軽にご参加ください。
DIF Japan SIG のメーリスか、三井（ mitsui@collabogate.com ）までご連絡いただけると幸いです。