2025年9月19日 / 最終更新日 : 2025年9月18日 APPSWINGBY ITピックアップ・ITトレンド

ゼロ知識証明（ゼロナレッジ証明）～zk-STARKsの技術的基盤

ゼロ知識証明（ゼロナレッジ証明）～zk-STARKsの技術的基盤

前回は「ゼロ知識証明（ゼロナレッジ証明）のコミュニケーション方式」と題して、２つあるゼロ知識証明のコミュニケーション方式についてご紹介しました。zk-SNARKsとzk-STARKs、ぱっと見、同じワードのように見えるので間違いやすかったりするのですが、目を凝らして読み進めると意外と面白かったりもします。

　第一回目の記事「ゼロ知識証明（ゼロナレッジ証明）とは？」

今回は、zk-STARKsの技術的基盤についての解説です。技術よりの解説になりますので、経営的な観点やビジネス的な観点はまったくありません^^;

それでは、さっそくはじめていきましょう！

目次

zk-STARKsの技術的基盤

zk-STARKsは以下の3つの重要な技術要素を組み合わせて実現されています。

  1. Reed-Solomon符号（リード・ソロモン符号）
  2. Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI)
  3. Algebraic Intermediate Representation (AIR)

ひとつひとつ、できるだけ簡単に解説していきます。

1. Reed-Solomon符号（リード・ソロモン符号）

Reed-Solomon符号（リード・ソロモン符号）は、エラー訂正符号の一種で、zk-STARKsでは計算の正確性を検証するために使用されます。

  • 役割: 計算結果を冗長な形で符号化し、部分的にサンプリングするだけで全体の正確性を検証可能にする
  • 利点: わずかなデータポイントをチェックするだけで、大量の計算の正確性を高い確率で検証できる
  • 例: 1000個の計算結果のうち、ランダムに50個だけをチェックして、残り950個も正しいことを99.9%の確率で保証

2. Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI)

FRIは、Reed-Solomon符号が正しく構成されているかを効率的に証明するプロトコルです。

  • 問題設定: 「この多項式は本当にReed-Solomon符号になっているか？」を検証したい
  • FRIの解決法:
  元の多項式: f(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ
  検証プロセス:
  1. f(x)を2つの部分に分割: f(x) = f_even(x²) + x·f_odd(x²)
  2. ランダムな値αでテスト: g(x) = f_even(x) + α·f_odd(x)
  3. g(x)についても同様の分割を再帰的に実行
  4. 最終的に定数になるまで繰り返し
  • 効率性: 対数回数の繰り返しで完了（例：100万次の多項式→20回の繰り返し）

3. Algebraic Intermediate Representation (AIR)

ARIは、複雑な計算を代数的制約として表現する方法です。

  • 目的: 「プログラムが正しく実行された」ことを数学的制約で表現
  • 具体例:

pythonの例

  # フィボナッチ数列の計算
  # F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2)
  
  # AIRでの表現：
  制約1: first_row = 1        # 初期値
  制約2: second_row = 1       # 初期値  
  制約3: 各行について: row[i] = row[i-1] + row[i-2]  # 漸化式
  • 利点: どんな複雑な計算でも、このような制約の組み合わせで表現可能
  • 検証: 制約がすべて満たされていれば、計算が正しく実行されたことが保証される

3つの技術を連携して正確性を証明する

zk-STARKsは、Reed-Solomon符号、FRI、AIRを連携させて、正確性を証明します。

  1. AIRで計算を制約として表現
  2. Reed-Solomon符号で制約の満足度を効率的に符号化
  3. FRIで符号化が正しいことを検証

この組み合わせにより、巨大な計算でもコンパクトな証明でその正確性を証明するのです。

実装における技術的課題

次に、実装における技術的な課題について、まとめておきます。

回路設計と制約システム

ゼロ知識証明では、証明したい計算を算術回路として表現する必要があります。これが実装における最も重要な課題の一つです。

なぜ算術回路が必要なのか

従来のプログラムは条件分岐（if文）、ループ、動的メモリアクセスなどを含みますが、ゼロ知識証明システムはこれらを直接扱えません。代わりに、すべての計算を「加算」と「乗算」の組み合わせで表現する必要があります。

課題1: プログラムから回路への変換　#以下はrustの例です。

// 通常のプログラム（if文を含む）
fn max(a: u32, b: u32) -> u32 {
    if a > b { a } else { b }
}

// これを以下の算術回路に変換する必要がある：
// result = a * (a >= b) + b * (a < b)
// ここで (a >= b) は 0 または 1 の値を返す制約

Circom言語での回路例とその解決法

// Circom言語での回路例
template MultiplyAndAdd() {
    signal input a;      // 入力信号：秘密の値 a
    signal input b;      // 入力信号：秘密の値 b
    signal input c;      // 入力信号：秘密の値 c
    signal output out;   // 出力信号：計算結果
    
    component mult = Multiplier();  // 乗算コンポーネントを使用
    mult.a <== a;                   // 信号を接続
    mult.b <== b;
    
    out <== mult.out + c;           // 最終的な制約: out = a*b + c
}

この回路が解決している問題は以下の通りです。

  1. 計算の証明: 「私は秘密の値a, b, cを知っており、a*b + c = outという計算を正しく実行した」ことを証明
  2. 秘密の保護: a, b, cの実際の値を開示することなく、計算結果outのみを公開
  3. 検証可能性: 第三者がa, b, cを知らなくても、計算が正しく実行されたかを検証可能

実用例での応用

実用例での応用についても考えてみましょう。

// より実用的な例：年齢証明回路
template AgeVerification() {
    signal input birth_year;     // 秘密：実際の出生年
    signal input current_year;   // 公開：現在の年
    signal input min_age;        // 公開：最低年齢（例：18）
    signal output is_valid;      // 出力：年齢条件を満たすか
    
    // 制約：current_year - birth_year >= min_age
    component geq = GreaterEqThan(8);
    geq.in[0] <== current_year - birth_year;
    geq.in[1] <== min_age;
    
    is_valid <== geq.out;
}

算術回路での表現は、元のプログラムよりもはるかに複雑になることが多いのです。

よくある課題を簡単にまとめてみます。

  1. if文1つ → 数十の算術制約に展開される場合がある
  2. ループ → 展開されてすべてのイテレーションが明示的に記述
  3. 配列アクセス → すべての要素への条件付きアクセスに変換

制約の最適化

ゼロ知識証明では、計算の複雑さが証明のコストに直接影響します。

そこで課題となるのが、制約の最適化です。

実用的なアプリケーションで発生するよくある問題についても見てみましょう。

  1. 証明生成時間: 複雑な回路では数分〜数時間かかる場合がある
  2. メモリ使用量: 大きな回路は数GB〜数十GBのRAMを必要とする
  3. ユーザビリティ: 遅い証明生成はユーザー体験を著しく悪化させる

これらの問題を実用アプリでは、なんとかしていかなければなりません。

回路のゲート

これらの問題を解決するために注目されるのが、回路の”ゲート”です。

ゲートとは、算術回路の基本演算単位のことです。

つまり、回路のゲート数を最小化することが証明生成時間とサイズに直結するということです。

基本的なゲートと複合的な例を以下の挙げておきます。

基本的なゲート：
- 加算ゲート: a + b = c （制約：c - a - b = 0）
- 乗算ゲート: a × b = c （制約：c - a × b = 0）
- 定数ゲート: a = 5    （制約：a - 5 = 0）

複合的な例：
x² + 3x + 2 = y の場合：
ゲート1: x × x = temp1     (乗算ゲート)
ゲート2: 3 × x = temp2     (乗算ゲート) 
ゲート3: temp1 + temp2 = temp3  (加算ゲート)
ゲート4: temp3 + 2 = y     (加算ゲート)
合計：4つのゲート

ゲート数最小化と性能の直結関係

証明生成時間への影響の例もあげておきます。

証明生成の主要ステップ：
1. 制約満足度の計算: O(ゲート数)
2. FFT計算: O(ゲート数 × log(ゲート数))
3. 楕円曲線演算: O(ゲート数)

実際の例：
- 1000ゲート → 証明生成: 100ms
- 10000ゲート → 証明生成: 2秒  
- 100000ゲート → 証明生成: 3分
証明サイズへの影響

証明書サイズへの影響も、参考用のメモとして以下に挙げておきます。

zk-SNARKs (Groth16): 固定サイズ（〜200バイト）
zk-STARKs: 証明サイズ = O(log²(ゲート数))

例：
- 1000ゲート → STARK証明: 45KB
- 10000ゲート → STARK証明: 60KB
- 100000ゲート → STARK証明: 80KB
メモリ使用量への影響

データがあれば、メモリへの影響についても考慮しなければなりません。

Setup Phase: O(ゲート数²) のメモリが必要
Proving Phase: O(ゲート数) のメモリが必要

実測例：
- 100万ゲート → Setup: 32GB RAM
- 100万ゲート → Proving: 8GB RAM

セットアップの信頼性

ゼロ知識証明システムの多く（特にzk-SNARKs）は、証明と検証を行う前に「Trusted Setup」と呼ばれる初期設定段階を必要とします。このセットアップで生成される暗号学的パラメータが、システム全体のセキュリティを決定します。

Trusted Setup

Trusted Setupでは、秘密の乱数（通常τ（タウ）と呼ばれる）を使って、証明鍵と検証鍵のペアを生成します。

セキュリティを保つため、この秘密乱数は生成後に完全に破棄する必要があります（これが「Toxic Waste」と呼ばれる理由です）。

なぜセットアップの信頼性が重要なのか

もしτが漏洩すれば、偽の証明を作成することが可能になります。

当然、セットアップが正しく行われたことを参加者は「信頼」する必要があり、この信頼の前提が、システム全体のセキュリティ基盤となるのです。

Universal Setup vs Circuit-Specific Setup

セットアップ方式は、その適用範囲によって大きく2つに分類されます。簡単な例を以下に挙げます。

class UniversalSetup
    """回路に依存しないユニバーサルセットアップ"""
    def __init__(self, max_degree):
        self.srs = self.generate_structured_reference_string(max_degree)
        
    def generate_proving_key(self, circuit):
        """特定の回路用の証明鍵を生成"""
        return self.srs.specialize(circuit)
class CircuitSpecificSetup
    """回路固有のセットアップ（Groth16など）"""
    def setup(self, circuit):
        """回路ごとに新しいトラステッドセットアップが必要"""
        tau = self.generate_toxic_waste()
        pk, vk = self.generate_keys(circuit, tau)
        self.destroy(tau)  # 重要：トクシックウェイストを破棄
        return pk, vk

大分長くなってしまいましたので、実用的な応用事例については、次回の記事でご紹介します。

解説記事「ゼロ知識証明（ゼロナレッジ証明）～zk-STARKsの技術的基盤」の続きは

現在準備中です。

公開までお待ちください。

APPSWINGBYは、最先端の技術の活用と、お客様のビジネスに最適な形で実装する専門知識を有しております。システム刷新（モダナイゼーション）やシステムリプレース、新規サービスの設計・開発、既存システムの改修（リファクタリング、リアーキテクチャ）、DevOps環境の構築、ハイブリッドクラウド環境の構築、技術サポートなど提供しています。サイト、システムの一新をお考えでしたら、弊社お問い合わせフォームよりお気軽にご相談ください。

お問い合わせはこちら

システム開発にお困りではありませんか？

もしも今現在、

  • どのように開発を依頼したらよいかわからない
  • どのように開発を依頼したらよいかわからない
  • 企画や要件定義の段階から依頼できるのか知りたい
  • システム開発費用がどれくらいかかるのか知りたい
  • 見積りがほしい

など、システム開発に関するご相談・ご依頼がございましたら、お気軽にご相談ください。APPSWINGBYでは、「アプリでお客様のビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること」をミッションとしています。大手SIerやＲ＆Ｄ部門で培った経験やノウハウ、高度な技術力でお客様の「やりたい」を実現します。

今すぐ相談

まずはお気軽にご相談ください

この記事を書いた人
株式会社APPSWINGBY
株式会社APPSWINGBY マーケティング

APPSWINGBY（アップスイングバイ）は、アプリケーション開発事業を通して、お客様のビジネスの加速に貢献することを目指すITソリューションを提供する会社です。

ご支援業種

情報・通信、医療、製造、金融（銀行・証券・保険・決済）、メディア、流通・EC・運輸 など多数

株式会社APPSWINGBY
株式会社APPSWINGBY マーケティング

APPSWINGBY（アップスイングバイ）は、アプリケーション開発事業を通して、お客様のビジネスの加速に貢献することを目指すITソリューションを提供する会社です。

ご支援業種

情報・通信、医療、製造、金融（銀行・証券・保険・決済）、メディア、流通・EC・運輸 など多数

監修
APPSWINGBY CTO川嶋秀一
株式会社APPSWINGBY 　CTO 川嶋秀一

動画系スタートアップ、東証プライム R&D部門を経験した後に2019年5月に株式会社APPSWINGBY 取締役兼CTOに就任。
Webシステム開発からアプリ開発、AI、リアーキテクチャ、リファクタリングプロジェクトを担当。C,C++,C#,JavaScript,TypeScript,Go,Python,PHP,Vue.js,React,Angular,Flutter,Ember,Backboneを中心に開発。お気に入りはGo。

APPSWINGBY CTO川嶋秀一
株式会社APPSWINGBY 　CTO 川嶋秀一

動画系スタートアップ、東証プライム R&D部門を経験した後に2019年5月に株式会社APPSWINGBY 取締役兼CTOに就任。
Webシステム開発からアプリ開発、AI、リアーキテクチャ、リファクタリングプロジェクトを担当。C,C++,C#,JavaScript,TypeScript,Go,Python,PHP,Vue.js,React,Angular,Flutter,Ember,Backboneを中心に開発。お気に入りはGo。

カテゴリー
ITピックアップ・ITトレンド、お役立ち資料
タグ
ITピックアップ・ITトレンド
ゼロ知識証明（ゼロナレッジ証明）のコミュニケーション方式

前の記事

ゼロ知識証明（ゼロナレッジ証明）のコミュニケーション方式New!!
2025年9月18日