| name | zero-knowledge-proofs |
| description | Guide complet des preuves à divulgation nulle de connaissance — zk-SNARKs, zk-STARKs, Bulletproofs, Groth16, PLONK, FRI, circom, applications privacy, et implémentations. |
| category | cybersecurite |
| tags | ["zero-knowledge","zk-snark","zk-stark","bulletproofs","groth16","plonk","circom","privacy","cryptography"] |
Zero-Knowledge Proofs (ZKP) — Guide Approfondi
Sommaire
- Fondements Théoriques
- zk-SNARKs (Groth16)
- PLONK — Universal SNARK
- Bulletproofs — Sans Trusted Setup
- zk-STARKs — Scalable Transparent
- FRI — Fast Reed-Solomon IOPP
- circom — ZK Circuit Language
- Applications Blockchains
- Applications Privacy
- Implémentations
1. Fondements Théoriques
1.1 Définition Formelle
Un protocole ZK implique deux parties :
- Prouveur (Prover) : veut prouver une affirmation sans révéler d'information
- Vérifieur (Verifier) : vérifie la preuve
Propriétés requises :
1. Complétude (Completeness) : Si l'affirmation est vraie, le vérifieur accepte (prob. ≥ 1 - negl)
2. Solidité (Soundness) : Si l'affirmation est fausse, le vérifieur rejette (prob. ≥ 1 - negl)
3. Zéro-Connaissance (ZK) : Le vérifieur n'apprend rien sauf que l'affirmation est vraie
Sécurité prouvée : dans le modèle de l'oracle aléatoire (Random Oracle Model) ou le modèle de référence commun (CRS, Common Reference String).
1.2 Taxonomie des Preuves ZK
| Type | Taille Preuve | Temps Prouveur | Temps Vérifieur | Trusted Setup | Quantum-Resistant |
|---|
| Groth16 (SNARK) | ~200 B | O(n log n) | O(1) | Oui (circuit) | Non |
| PLONK (SNARK) | ~1 KB | O(n log n) | O(1) | Oui (universel) | Non |
| Bulletproofs | ~1.3 KB | O(n log n) | O(n) | Non | Non |
| STARK (FRI) | ~100-500 KB | O(n log n) | O(n) | Non | Oui |
| MPC-in-the-Head | ~100 KB | O(n²) | O(n) | Non | Oui |
| ZKBoo | ~100 KB | O(n) | O(n) | Non | Oui |
1.3 Circuits Algébriques
Toute affirmation vérifiable peut être représentée par un circuit arithmétique (addition, multiplication dans un corps fini F_p) :
Exemple : Prouver qu'on connaît x tel que f(x) = y
Circuit :
w₁ = x (témoin privé)
w₂ = x × x (multiplication)
w₃ = w₂ + 42 (addition)
output w₃ == y
Contraintes R1CS (Rank-1 Constraint System) :
A·w ∘ B·w = C·w
où w = (1, x, w₂, w₃, y) est le vecteur de témoins
et ∘ est la multiplication élément par élément
2. zk-SNARKs (Groth16)
2.1 Architecture
zk-SNARK = Zero-Knowledge Succinct Non-interactive ARgument of Knowledge.
Processus en 3 phases :
- Trusted Setup (une fois par circuit) : génération des paramètres
- Prove : génération de la preuve
- Verify : vérification
Taille de preuve : constante (3 éléments de G₁ + 1 de G₂ ≈ 200 octets pour BLS12-381).
2.2 La Construction Groth16
Groth16 (2016) est le SNARK le plus efficace en taille de preuve.
Trusted Setup :
def setup_phase1(curve, n):
"""
Génération de [τ¹G₁, τ²G₁, ..., τⁿG₁] et [τ¹G₂, ..., τⁿG₂]
via MPC (Multi-Party Computation).
τ : secret aléatoire, connu de personne (si MPC correctement fait)
"""
tau = sample_secret()
return {
'pk_vk': [(tau**i * G1) for i in range(n)],
'pk_wk': [(tau**i * G2) for i in range(n)],
}
def setup_phase2(circuit, pk_phase1):
"""
Génération des paramètres de preuve spécifiques au circuit.
δ est un secret aléatoire de phase 2.
"""
delta = sample_secret()
return proving_key, verification_key
Preuve (3 éléments G₁, 1 G₂) :
def groth16_prove(circuit, witness, pk):
"""
Génération d'une preuve Groth16.
Témoin : valeurs secrètes satisfaisant les contraintes.
"""
a_poly = interpolate(witness, 'A')
b_poly = interpolate(witness, 'B')
c_poly = interpolate(witness, 'C')
A = commit(a_poly, pk)
B = commit(b_poly, pk)
C = commit(c_poly, pk)
proof = (A, B, C)
public_inputs = witness.public()
return proof, public_inputs
Vérification :
def groth16_verify(proof, public_inputs, vk):
"""
Vérification : une seule équation de pairings.
e(A, B) = e(public_inputs, γ) · e(C, δ)
"""
A, B, C = proof
pairing_lhs = pairing(A, B)
pairing_rhs = pairing(public_commit, gamma) * pairing(C, delta)
return pairing_lhs == pairing_rhs
2.3 Avantages et Limitations
Avantages :
- Preuves les plus compactes (~200-300 octets)
- Vérification O(1) — une équation de pairing
- Très adapté aux blockchains (stockage minimal)
Limitations :
- Trusted Setup : nécessite une cérémonie pour chaque circuit
- Menace des « toxic waste » : si τ est connu, on peut forger des preuves
- Pas quantum-resistant
3. PLONK
3.1 PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive Arguments of Knowledge)
Proposé par Gabizon, Williamson, Ciobotaru (2019).
Innovation clé : un seul trusted setup universel pour tous les circuits de taille ≤ n.
3.2 Architecture
Setup universel (une fois pour toutes) :
┌─────────────────────────────────┐
│ Structured Reference String │
│ [q¹G₁, q²G₁, ..., qⁿG₁] │
│ [q¹G₂, q²G₂, ..., qⁿG₂] │
└─────────────────────────────────┘
Circuit → Preuve (5 étapes) :
-
Réduction du circuit à des contraintes polynomiales
- Gate constraints (add/mul) :
L(x)·q_L(x) + R(x)·q_R(x) + O(x)·q_O(x) + M(x)·q_M(x) + q_C(x) = 0
- Wiring constraints (permutations) :
σ(L(x)) = σ(R(x)) = σ(O(x))
-
Polynôme d'argument : f(x) = (W_L(x) + β·σ_L(x) + γ)·(W_R(x) + β·σ_R(x) + γ)·(W_O(x) + β·σ_O(x) + γ)
-
Division polynomiale : prouver que t(x) divise le polynôme quotient
def plonk_prove(circuit, witness, srs):
"""Génération d'une preuve PLONK"""
w_L = commit(witness.left, srs)
w_R = commit(witness.right, srs)
w_O = commit(witness.output, srs)
q(x) = quotient_polynomial(circuit, witness)
t_x = commit(q, srs)
z_x = commit(permutation_polynomial, srs)
return proof
Vérification PLONK : O(n) (n = nombre de gates). Plus lourde que Groth16 mais plus flexible.
3.3 Comparaison Groth16 vs PLONK
| Critère | Groth16 | PLONK |
|---|
| Taille setup | Spécifique au circuit | Universel (une fois) |
| Taille preuve | 3 éléments (G₁, G₂, G₁) | ~10 éléments |
| Temps vérif | O(1) (1 pairing) | O(n) (plusieurs pairings) |
| Temps prover | O(n log n) | O(n log n) |
| Trusted setup | Cérémonie par circuit | Ceremony Power of Tau |
| Flexibilité | Nouveau circuit = nouveau setup | Même setup pour tous |
4. Bulletproofs
4.1 Principe
Preuves courtes sans trusted setup, basées sur les engagements de Pedersen.
Caractéristiques :
- Taille de preuve :
O(log n) (environ 1.3 KB pour n = 2^64)
- Vérification :
O(n) mais avec log-factor constant
- Pas besoin de pairing — fonctionne sur n'importe quelle courbe
4.2 Range Proof (Inner Product Argument)
def bulletproof_range_prove(v, n, G, H, g):
"""
Prouve que v ∈ [0, 2^n - 1] sans révéler v.
Utilise un Inner Product Argument (IPA).
"""
a_L = bits_of(v, n)
a_R = [b - 1 for b in a_L]
A = commit(a_L, a_R, g)
y = hash(A, ...)
z = hash(y, ...)
proof = ipa_prove(a_L, a_R, y, z)
return proof, commitment_A
def bulletproof_verify(proof, commitment_A, V, n):
"""Vérification du range proof"""
return valid
4.3 Application : Confidential Transactions
Utilisé dans Monero (Bulletproofs depuis 2018) :
5. zk-STARKs
5.1 Scalable Transparent Arguments of Knowledge
Proposé par Eli Ben-Sasson et al. (2018) — StarkWare.
Propriétés :
- Transparent : pas de trusted setup
- Scalable : temps prover O(n log n), vérif O(poly(log n))
- Quantum-resistant : basé seulement sur les hash (pas sur ECDLP)
- Post-quantum : sûr contre l'algorithme de Shor
Taille de preuve : ~100-500 KB (selon paramètres de sécurité et taille du circuit).
5.2 Architecture
┌──────────────────────────────────────────┐
│ zk-STARK Architecture │
│ │
│ 1. Circuit → Exécution Trace (ALGEBRA) │
│ (list of states: rows = steps, │
│ columns = registers) │
│ │
│ 2. Trace → Polynomial (IOPP) │
│ Interpolation polynomiale sur le │
│ domaine évalué (Reed-Solomon code) │
│ │
│ 3. Constraint Checking (AIR) │
│ Algebraic Intermediate Representation│
│ Vérification que le polynôme │
│ satisfait les contraintes │
│ │
│ 4. FRI — Low Degree Test │
│ Vérifier que le polynôme est de │
│ degré limité (pas de triche) │
│ │
│ 5. Merkle Tree Commitment │
│ Engager sur les valeurs évaluées │
└──────────────────────────────────────────┘
5.2 AIR (Algebraic Intermediate Representation)
Contrainte : à chaque pas, next_state est fonction de prev_state
f(x, y) = 0 pour tout état valide
Exemple (Fibonacci) :
a₀ = 1, a₁ = 1
a_{i+2} = a_{i+1} + a_i
Polynomial constraints :
P(x, next_x, next2_x) = next2_x - next_x - x = 0
6. FRI — Fast Reed-Solomon IOPP
6.1 Principe
Fast Reed-Solomon Interactive Oracle Proof of Proximity.
Objectif : vérifier qu'une fonction polynomiale f est proche d'un polynôme de degré < d (test de faible degré).
Étape 1 : Engager f via Merkle Tree (évaluations sur un domaine)
Étape 2 : Vérifieur envoie un défi aléatoire α
Étape 3 : Prouveur répond avec la moitié des évaluations (pliage)
Étape 4 : Récursion sur la moitié — log₂(n) rounds
Étape 5 : Vérification de la dernière paire d'évaluations
6.2 Complexité
| Taille circuit | Taille preuve STARK | Temps prover | Temps vérif |
|---|
| 2¹⁶ (~65K) | ~150 KB | ~2s | ~0.1s |
| 2²⁰ (1M) | ~250 KB | ~30s | ~0.5s |
| 2²⁵ (33M) | ~500 KB | ~15min | ~2s |
6.3 Comparaison SNARK vs STARK
| Propriété | SNARK (Groth16) | STARK (FRI) |
|---|
| Trusted setup | Oui (spécifique) | Non (transparent) |
| Taille preuve | ~200 B | ~150-500 KB |
| Vérification | O(1) (pairing) | O(poly(log n)) |
| Quantum-safe | Non (pairing) | Oui (hash) |
| Courbe | BN128, BLS12-381 | N'importe quel champ |
| Preuve récursive | Facile (taille constante) | Possible (plus cher) |
7. Circom — ZK Circuit Language
7.1 Langage de circuits ZK
Circom permet de décrire des circuits arithmétiques de manière déclarative.
// Exemple : circuit de vérification de hash SHA-256
pragma circom 2.1.0;
template IsEqual() {
signal input a;
signal input b;
signal output out;
// a == b → (a - b) * inv = 1
signal inv;
inv <-- 1 / (a - b + 1);
// Contrainte : (a - b) * out = 0
0 === (a - b) * (out);
}
template SimpleVote() {
signal input vote; // 0 ou 1
signal input secret; // preuve de connaissance
signal output commitment; // Hash(secret)
// vote est un bit
signal bit_check;
bit_check <== vote * (1 - vote);
bit_check === 0;
// Engagement sur le secret
component hasher = SHA256();
hasher.input <== secret;
commitment <== hasher.out;
}
component main = SimpleVote();
7.2 Workflow Circom
circom circuit.circom --r1cs --wasm --sym -o build/
node build/circuit_js/generate_witness.js build/circuit_js/circuit.wasm input.json witness.wtns
snarkjs powersoftau new bn128 12 pot12.ptau -v
snarkjs powersoftau contribute pot12.ptau pot12_final.ptau --name="First contribution" -v
snarkjs groth16 setup build/circuit.r1cs pot12_final.ptau circuit_0000.zkey
snarkjs zkey contribute circuit_0000.zkey circuit_final.zkey --name="1st Contributor" -v
snarkjs zkey export verificationkey circuit_final.zkey verification_key.json
snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json
snarkjs groth16 verify verification_key.json public.json proof.json
7.3 Exemple complet en Python (via snarkjs wrapper)
import subprocess
import json
def prove_age_over_18(birth_year, current_year, circuit_dir):
"""
Circuit : prouver age >= 18 sans révéler l'âge exact.
age = current_year - birth_year
age - 18 >= 0
"""
with open(f"{circuit_dir}/input.json", 'w') as f:
json.dump({"birth_year": birth_year, "current_year": current_year}, f)
subprocess.run([
"snarkjs", "groth16", "prove",
f"{circuit_dir}/circuit_final.zkey",
f"{circuit_dir}/witness.wtns",
f"{circuit_dir}/proof.json",
f"{circuit_dir}/public.json"
], check=True)
return json.load(open(f"{circuit_dir}/proof.json"))
8. Applications Blockchains
8.1 zk-Rollups
Couche 2 Ethereum : des milliers de transactions sont compressées en une seule preuve ZK.
Exemple (zkSync Era) :
def zkrollup_submit_batch(batch_txs, old_state_root, new_state_root):
"""Soumet un lot de transactions en layer 1"""
proof = generate_batch_proof(batch_txs, old_state_root, new_state_root)
rollup_contract.submitBatch(
new_state_root,
batch_hash,
proof
)
Comparaison zk-Rollups vs Optimistic :
| Critère | zk-Rollup | Optimistic |
|---|
| Finalité | Immédiate | ~7 jours |
| Garantie | Mathématique (ZK) | Économique (fraud proof) |
| Coût vérif | ~5000 gas | ~60000 gas (en conflit) |
| TPS | ~2000-20000 | ~100-300 |
8.2 Tornado Cash (Protocol Privacy)
Utilisation de zk-SNARKs pour cacher la provenance des transactions Ethereum :
def withdraw_proof(deposit_nullifier, secret, merkle_root, merkle_proof):
"""
Preuve ZK qu'on connaît un dépôt valide (nullifier, secret)
inclus dans l'arbre de Merkle, sans révéler lequel.
"""
leaf_hash = hash(deposit_nullifier, secret)
assert merkle_verify(merkle_root, leaf_hash, merkle_proof)
return proof
9. Applications Privacy
9.1 zk-SNARK pour l'Identité
def prove_age_zk(birth_date_encrypted, proof_authority_sig, min_age):
"""
Circuit ZK :
1. Vérifier que birth_date_encrypted est signé par une autorité
2. Prouver que current_date - birth_date >= min_age
3. Ne pas révéler la date exacte
"""
return snark_proof
verify_zk_proof(proof, {
'authority_pk': authority_public_key,
'min_age': 18
})
9.2 zk-SNARK pour l'Identité Décentralisée (DID)
9.3 zk-Email
Vérification d'un email sans révéler son contenu :
def verify_email_zk(email_sig, domain="example.com"):
"""
Preuve ZK sur une signature DKIM :
1. Vérifier la signature DKIM de l'email
2. Extraire le domaine de l'en-tête From
3. Prouver que domine == "example.com"
4. Ne pas révéler le reste de l'email
"""
10. Implémentations
Bibliothèques ZK
cargo add bellman
cargo add ark-groth16
cargo add plonky2
cargo add winterfell
npm install snarkjs
npm install circomlib
npm install @noir-lang/noir_wasm
pip install py_ecc
pip install lambdaworks
Outils CLI
circom circuit.circom --r1cs --wasm --sym
snarkjs groth16 prove zkey witness proof.json public.json
snarkjs groth16 verify vk public.json proof.json
nargo compile
nargo prove
nargo verify
cargo risczero build
cargo risczzero prove
Exemple Noir (langage ZK)
// Noir — langage ZK natif pour Aztec Network
fn main(x: Field, y: Field) {
// Prouver qu'on connaît x et y tels que x * y == 10
let constraint = x * y;
constrain constraint == 10;
}
Références
