Legion ZK Auth 🛡️

ハードウェアにバインドされたデバイスリング署名による真のゼロ知識認証

🎯 Legionとは？

Legionは、自分が誰であるかを明かすことなく、承認されていることを証明するパスワードレスなゼロ知識認証システムです。

指紋 + 24語のリカバリフレーズ（MetaMaskのような）だけで認証できます。ユーザー名もパスワードもサーバー側の秘密も不要です。

主な機能

✅ パスワードレス認証: BIP-39リカバリフレーズ + 指紋（ユーザー名/パスワード不要）
✅ 真のゼロ知識: サーバーはあなたの身元を知ることはありません（100万人のうちの1人）
✅ デバイスの匿名性: リング署名によるハードウェア結合（1,000台のうちの1台）
✅ トラステッドセットアップ不要: Halo2 PLONK（透過的セットアップ）
✅ ハードウェアセキュリティ: WebAuthn TPM/Secure Enclaveバインド
✅ リプレイ保護: Nullifiers + タイムスタンプ
✅ セッションセキュリティ: リンカビリティタグによる盗難防止
✅ マルチデバイス対応: 同じアカウントを2台のデバイス（ノートPC + スマートフォン）で使用可能
✅ レート制限: 1時間あたり5回の試行（一般的なエラーにより列挙を防止）
✅ デバイス失効: 盗難デバイスを即座にブロック

🔒 セキュリティ保証 (v1.3.0)

🚀 クイックスタート (ワンコマンド!)

前提条件

Docker (Docker Composeを含む)

インストールと実行```bash

Clone and run

git clone https://github.com/deadends/legion.git cd legion

Linux/macOS

chmod +x scripts/install.sh && ./scripts/install.sh

Windows

scripts\install.bat

**これで完了です！** ブラウザで http://localhost を開いてください。

### インストールされるもの
- ✅ Redis（セッションストレージ）
- ✅ Legion Server（ZKプルーフ検証器）
- ✅ Frontend（WASMクライアント）
- ✅ Nginx（リバースプロキシ）

**パフォーマンス**：登録 約5秒、認証 約2分（k=14 プルーフ生成）

---

### 手動セットアップ（Docker不使用）

<details>
<summary>クリックして手動インストールを展開</summary>```bash
# 1. Install Redis
# macOS: brew install redis && redis-server
# Ubuntu: sudo apt install redis && redis-server
# Windows: https://redis.io/docs/install/install-redis/install-redis-on-windows/

# 2. Run server (terminal 1)
cd legion-server
cargo run --release --features redis

# 3. Build frontend (terminal 2)
cd wasm-client
wasm-pack build --target web --release
python3 -m http.server 8000

# 4. Open http://localhost:8000

本番環境へのデプロイについては、DEPLOYMENT.md を参照してください

📊 パフォーマンス

検証ベンチマーク

テストハードウェア: Lenovo IdeaPad 3 - Intel Core i3 11th Gen
注記: パフォーマンスはハードウェアの仕様によって異なる場合があります。

k=12 (開発/テスト)

内訳:

🔥 コールドスタート（初回検証）: ~8.4s（パラメータ＋鍵生成＋検証を含む）
⚡ 後続の検証（キャッシュあり）: ~108ms（パラメータ/鍵生成はキャッシュ済み）
💾 証明オーバーヘッド: 公開入力あたり ~326バイト
🔐 回路の複雑さ: ユーザーツリー（20レベル）＋デバイスツリー（10レベル）＋バインディング

k=14 (本番 - 推奨)

内訳:

🔥 コールドスタート（初回検証）: ~115s（パラメータ＋鍵生成＋検証を含む）
⚡ 後続の検証（キャッシュあり）: ~967ms（パラメータ/鍵生成はキャッシュ済み）
💾 証明オーバーヘッド: 公開入力あたり ~339バイト
🔐 回路の複雑さ: ユーザーツリー（20レベル）＋デバイスツリー（10レベル）＋バインディング

重要: パラメータ生成と鍵生成は一回限りのコストであり、キャッシュ可能です。キャッシュされると、検証は k 値に応じて約108〜967msしかかかりません。現在の実装ではパラメータはまだキャッシュされていません。

以前のベンチマークより遅いのはなぜか？ パスワードレス回路は、1つの代わりに2つのMerkleツリー（ユーザー＋デバイス）を検証するようになり、真のデバイスレベルの匿名性（ユーザーごとに1024台中1台のデバイス）を提供します。

🏗️ アーキテクチャ

📖 暗号技術の詳細を含むステップバイステップの認証フローについては、ARCHITECTURE_FLOW.md を参照してください

システムコンポーネント```

┌─────────────────────────────────────────────────────────────────────────┐ │ CLIENT (Browser + WASM) │ ├─────────────────────────────────────────────────────────────────────────┤ │ ┌────────────────┐ ┌─────────────────┐ ┌──────────────────────────┐ │ │ │ UI Layer │ │ WASM Prover │ │ Local Storage │ │ │ │ (Vanilla JS) │ │ (Rust→WASM) │ │ (IndexedDB) │ │ │ ├────────────────┤ ├─────────────────┤ ├──────────────────────────┤ │ │ │ • Registration │ │ • Blake3 Hash │ │ • Full Merkle Tree │ │ │ │ • Login Form │ │ • BIP-39 Derive │ │ • Device Trees │ │ │ │ • Session UI │ │ • Halo2 Prover │ │ • WebAuthn Credentials │ │ │ │ • Tree Sync │ │ • Merkle Proof │ │ • Tree Version Cache │ │ │ └────────────────┘ │ • Ring Sigs │ └──────────────────────────┘ │ │ └─────────────────┘ │ │ ┌──────────────────────────────────────────────────────────────────┐ │ │ │ Hardware Security (WebAuthn Level 2) │ │ │ ├──────────────────────────────────────────────────────────────────┤ │ │ │ • TPM 2.0 / Secure Enclave • FIDO2 Authenticator │ │ │ │ • Device Private Key (ECDSA) • Biometric/Touch Required │ │ │ └──────────────────────────────────────────────────────────────────┘ │ └────────────────────────────────┬────────────────────────────────────────┘ │ HTTPS/TLS 1.3 │ (Encrypted Channel) ▼ ┌──────────────────────────────────────────────────────────────────────────┐ │ LEGION SERVER (Rust/Axum) │ ├──────────────────────────────────────────────────────────────────────────┤ │ ┌─────────────────────────────────────────────────────────────────┐ │ │ │ API Layer (Axum) │ │ │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ POST /api/register-blind │ Blind registration │ │ │ │ GET /api/download-tree │ Download full Merkle tree │ │ │ │ POST /api/verify-anonymous-proof │ Verify ZK proof │ │ │ │ POST /api/verify-session │ Session validation │ │ │ │ POST /api/webauthn/* │ WebAuthn endpoints │ │ │ │ GET /health │ Health check │ │ │ └─────────────────────────────────────────────────────────────────┘ │ │ │ │ │ ┌─────────────────────────────────────────────────────────────────┐ │ │ │ Business Logic Layer │ │ │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ • Blind Registration │ • Tree Synchronization │ │ │ │ • ZK Proof Verifier │ • Nullifier Tracker (replay) │ │ │ │ • Session Manager │ • Linkability Tag Validator │ │ │ │ • WebAuthn Service │ • Timestamp Validator (±10min) │ │ │ │ • Device Revocation │ • Rate Limiter (5/hour) │ │ │ └─────────────────────────────────────────────────────────────────┘ │ │ │ │ │ ┌─────────────────────────────────────────────────────────────────┐ │ │ │ Cryptographic Layer │ │ │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ • Halo2 Verifier (PLONK) │ • Poseidon Hash (ZK-friendly) │ │ │ │ • Blake3 (credential) │ • BIP-39 (recovery phrase) │ │ │ │ • Merkle Tree (2^20) │ • Device Trees (2^10 per user) │ │ │ │ • Ring Signature Verify │ • WebAuthn Signature Verify │ │ │ └─────────────────────────────────────────────────────────────────┘ │ └────────────────────────┬──────────────────────┬──────────────────────────┘ │ │ ▼ ▼ ┌────────────────────────┐ ┌───────────────────────────┐ │ Redis (In-Memory) │ │ RocksDB (Persistent) │ ├────────────────────────┤ ├───────────────────────────┤ │ • Session Tokens │ │ • Merkle Tree Leaves │ │ • Linkability Tags │ │ • Device Trees │ │ • Spent Nullifiers │ │ • Nullifier History │ │ • Rate Limit Counters │ │ • WebAuthn Credentials │ │ TTL: 1 hour │ │ • Revoked Devices │ └────────────────────────┘ └───────────────────────────┘

### 認証フロー（簡略版）```
┌─────────────┐                                                ┌──────────────┐
│   Client    │                                                │    Server    │
│  (Browser)  │                                                │  (Verifier)  │
└──────┬──────┘                                                └──────┬───────┘
       │                                                              │
       │ 1. Generate 24-word recovery phrase (BIP-39)                 │
       │    → 256-bit entropy (like MetaMask)                         │
       │    → User writes down on paper                               │
       │                                                              │
       │ 2. Derive account_id from phrase (Blake3)                    │
       │    account_id = Blake3("LEGION_ACCOUNT_V2" || bip39_seed)    │
       │    → Deterministic, no server interaction                    │
       │                                                              │
       │ 3. Hash account_id for tree leaf (Poseidon)                  │
       │    credential_hash = Poseidon(account_id)                    │
       │                                                              │
       │ 4. Blind registration (TRUE zero-knowledge)             ────►│
       │    → Sends ONLY credential_hash (no phrase/identity)         │
       │    → Server adds to tree, returns tree_index                 │
       │                                                         ◄────│ {tree_index: 114}
       │                                                              │
       │ 5. Download full Merkle tree (one-time sync)            ────►│
       │    → Client stores entire tree in IndexedDB                  │
       │    → Enables TRUE zero-knowledge (no server queries)         │
       │                                                         ◄────│ {tree_data: [all leaves],
       │                                                              │  merkle_root, version}
       │                                                              │
       │ 6. Generate WebAuthn key (TPM/Secure Enclave)                │
       │    → Fingerprint prompt creates hardware-bound key           │
       │    → device_pubkey (ECDSA P-256, non-exportable)             │
       │    → Stored in TPM 2.0 / Secure Enclave                      │
       │                                                              │
       │ 7. Register device in device tree                       ────►│
       │    → device_commitment = Blake3(credential_id)               │
       │    → Server converts to valid field element if needed        │
       │    → Server adds to user's device tree (1 of 1024 slots)     │
       │                                                         ◄────│ {device_position: 0,
       │                                                              │  device_tree_root}
       │                                                              │
       │ 8. LOGIN: Touch fingerprint to authenticate                  │
       │    → WebAuthn verifies hardware-bound key                    │
       │    → Decrypts recovery phrase from local storage             │
       │    → Re-derives account_id from phrase                       │
       │                                                              │
       │ 9. Fetch device Merkle proof                            ────►│
       │    → Sends account_id (derived from phrase)                  │
       │    → Server returns device tree path                         │
       │                                                         ◄────│ {device_path: [siblings],
       │                                                              │  device_root}
       │                                                              │
       │ 10. Compute user Merkle proof CLIENT-SIDE                    │
       │    → Uses local tree from IndexedDB                          │
       │    → Computes path for tree_index                            │
       │    → Server NEVER learns which user!                         │
       │                                                              │
       │ 11. Compute nullifier (replay protection)                    │
       │    nullifier = Poseidon(account_id || challenge)             │
       │    → ONE-TIME USE: Different every login                     │
       │    → Prevents proof replay attacks                           │
       │                                                              │
       │ 12. Compute linkability tag (session binding)                │
       │    linkability_tag = Blake3(device_pubkey || nullifier)      │
       │    ⚠️  Binds session to specific device+user                 │        
       │                                                              │
       │ 13. Generate ZK proof (Halo2 PLONK, ~2min for k=14)          │
       │    Proves in zero-knowledge:                                 │
       │    ✓ User exists in Merkle tree (1 of 2^20)                  │
       │    ✓ Device exists in device tree (1 of 2^10)                │
       │    ✓ account_id hashes to credential_hash                    │
       │    ✓ Nullifier computed correctly                            │
       │    ✓ Timestamp is fresh                                      │
       │    WITHOUT revealing which user or device                    │
       │                                                              │
       │ 14. Submit proof                                        ────►│
       │    {proof, public_inputs, linkability_tag, k=14}             │
       │                                                              │ • Check device not revoked
       │                                                              │ • Verify timestamp (±10min)
       │                                                              │ • Rate limit check (5/hour)
       │                                                              │ • Check nullifier (replay?)
       │                                                              │ • Verify ZK proof (~115s)
       │                                                              │ • Mark nullifier as used
       │                                                              │
       │                                                         ◄────│ {session_token, expires_at}
       │                                                              │
       │ 15. Verify session (every request)                      ────►│
       │    {session_token, linkability_tag}                          │
       │                                                              │ • Lookup in Redis
       │                                                              │ • Verify linkability_tag
       │                                                              │   (prevents session theft)
       │                                                              │ • Check not spent
       │                                                         ◄────│ {valid: true}
       │                                                              │

🔍 詳細を知りたいですか？ ARCHITECTURE_FLOW.md を参照してください：

暗号操作のステップバイステップ解説
回路制約の詳細
セキュリティ特性の説明
攻撃耐性のメカニズム

セッションセキュリティの詳細```

┌─────────────────────────────────────────────────────────────────────────┐ │ SESSION SECURITY MECHANISMS │ ├─────────────────────────────────────────────────────────────────────────┤ │ │ │ 1. LINKABILITY TAG (Zero-Knowledge Device Binding) │ │ ═══════════════════════════════════════════════════════ │ │ │ │ linkability_tag = Blake3(device_pubkey || nullifier) │ │ │ │ • Computed client-side using hardware-bound device key │ │ • Sent with every session validation request │ │ • Server verifies: stored_tag == provided_tag │ │ │ │ ✅ PREVENTS: Session token theft/replay on different device │ │ ✅ ENSURES: Same user + same device for entire session │ │ ✅ MAINTAINS: Zero-knowledge (server doesn't learn identity) │ │ │ │ ───────────────────────────────────────────────────────────────── │ │ │ │ 2. SESSION TOKEN (Cryptographic Binding) │ │ ═══════════════════════════════════════════════════════ │ │ │ │ session_token = Poseidon(nullifier || timestamp || linkability_tag) │ │ │ │ • Generated server-side after proof verification │ │ • Stored in Redis with linkability_tag as value │ │ • Cannot be forged without knowing nullifier │ │ │ │ ✅ PREVENTS: Token forgery │ │ ✅ ENSURES: Cryptographic binding to proof │ │ │ │ ───────────────────────────────────────────────────────────────── │ │ │ │ 3. NULLIFIER (Replay Protection) │ │ ═══════════════════════════════════════════════════════ │ │ │ │ nullifier = Poseidon(credential_hash || challenge) │ │ │ │ • Unique per authentication attempt │ │ • Tracked in RocksDB (permanent) and Redis (cache) │ │ • Server rejects if nullifier seen before │ │ │ │ ✅ PREVENTS: Proof replay attacks │ │ ✅ ENSURES: One-time use per challenge │ │ │ │ ───────────────────────────────────────────────────────────────── │ │ │ │ 4. TIMESTAMP VALIDATION (Time-Bound Security) │ │ ═══════════════════════════════════════════════════════ │ │ │ │ • Proof includes timestamp (Unix epoch) │ │ • Server validates: |proof_time - server_time| < 5 minutes │ │ • Session TTL: 1 hour (sliding window) │ │ │ │ ✅ PREVENTS: Old proof replay │ │ ✅ ENSURES: Fresh authentication │ │ │ │ ───────────────────────────────────────────────────────────────── │ │ │ │ 5. CHALLENGE-RESPONSE (Freshness Guarantee) │ │ ═══════════════════════════════════════════════════════ │ │ │ │ • Server generates random 32-byte challenge │ │ • Stored in Redis with 5-minute TTL │ │ • Client must include in proof │ │ • Server verifies challenge matches and deletes │ │ │ │ ✅ PREVENTS: Pre-computed proof attacks │ │ ✅ ENSURES: Proof generated for this specific session │ │ │ └─────────────────────────────────────────────────────────────────────────┘

## 🔐 ゼロ知識特性

### サーバーが把握できること
- ✅ 匿名性セット内の誰かが認証済み
- ✅ 証明が暗号学的に有効
- ✅ リンカビリティタグによる同一ユーザー＋デバイス
- ✅ レート制限ステータス（残り試行回数）
- ✅ デバイス失効ステータス
- ✅ 登録ユーザー総数
- ✅ マークルツリールート（公開）

### サーバーが把握できないこと
- ❌ 特定のユーザーが誰か（100万分の1）
- ❌ 特定のデバイスがどれか（ユーザーごとに1000分の1）
- ❌ リカバリーフレーズ（BIP-39シード）
- ❌ account_id（フレーズから派生）
- ❌ デバイス秘密鍵（TPM/Secure Enclave内）
- ❌ どのツリーリーフがどのユーザーに属するか
- ❌ ユーザーのマークルパス（クライアント側で計算）
- ❌ ユーザーのtree_indexの位置

## 📦 デプロイ

詳細な本番デプロイガイドについては [DEPLOYMENT.md](https://github.com/deadends/legion/blob/HEAD/docs/DEPLOYMENT.md) を参照してください。

### Dockerによるクイックデプロイ```bash
# Production build
docker-compose -f deployment/docker-compose.yml up -d

# Check logs
docker-compose -f deployment/docker-compose.yml logs -f legion-server

# Check health
curl http://localhost/health

環境変数```env

RUST_LOG=info LEGION_DATA_PATH=/var/lib/legion/data REDIS_URL=redis://127.0.0.1:6379

## 🧪 テスト```bash
# Run all tests
cargo test --workspace

# Run with Redis features
cargo test --workspace --features redis

# Benchmark
cargo bench

📚 ドキュメント

Architecture Flow - 詳細な認証フロー
Security Fixes - v1.1.0 セキュリティ改善
Deployment Guide - 本番環境へのデプロイ
Security Policy - セキュリティ保証と報告
Contributing - コントリビューションガイドライン

🛠️ 技術スタック

ZK Proofs: Halo2 (PLONK) - 透過的なセットアップ、トラステッドセレモニー不要
Curves: Pasta (Pallas/Vesta) - 再帰のための曲線のサイクル
Hash: Blake3 (認証情報の導出), Poseidon (ZK フレンドリー)
Key Derivation: BIP-39 (24語のニーモニック)
ハードウェア: WebAuthn Level 2 (TPM 2.0, Secure Enclave)
バックエンド: Rust, Axum, Redis (セッション), RocksDB (永続化)
フロントエンド: Rust→WASM (prover), Vanilla JS (UI), IndexedDB (ストレージ)
デプロイ: Docker, Nginx, systemd

🤝 コントリビューション

コントリビューション歓迎！最初に CONTRIBUTING.md をお読みください。

リポジトリをフォークする
フィーチャーブランチを作成する (git checkout -b feature/amazing)
変更をコミットする (git commit -m 'Add amazing feature')
ブランチにプッシュする (git push origin feature/amazing)
プルリクエストを開く

🔒 セキュリティ

セキュリティの問題を発見しましたか？責任ある開示については SECURITY.md を参照してください。

絶対に 脆弱性について公開の issue を開かないでください。

📄 ライセンス

MIT ライセンス - 詳細は LICENSE ファイルを参照してください。

🔄 変更履歴

v1.3.0 - パスワードレス認証 (2024)

主な変更点:

✅ パスワードレス認証 - BIP-39 リカバリーフレーズ + 指紋
✅ 単一フィールド回路 - BIP-39 シードから導出される account_id
✅ デバイスリング署名 - ユーザーごとに 1-of-1024 のデバイス匿名性
✅ マルチデバイス対応 - 2 台のデバイスで同じアカウントを使用
✅ ハードウェアバインド鍵 - WebAuthn TPM/Secure Enclave 統合
✅ Blake3 フィールド要素の処理 - デバイスコミットメントの自動変換

アーキテクチャ:

🏗️ ユーザー名/パスワードなし - リカバリーフレーズ + 指紋のみ
🏗️ クライアント側の account_id 導出 (Blake3 + BIP-39)
🏗️ デバイスツリーをサーバー側に保存 (ユーザーごとの分離)
🏗️ 二重マークルツリー検証 (ユーザーツリー + デバイスツリー)
🏗️ 堅牢なフィールド要素変換 (Blake3 出力がフィールドの法以上の場合も処理)

v1.2.0 - クライアント側証明アーキテクチャ (2024)