Cryptographie pour la blockchain

La cryptographie est le socle invisible sur lequel repose toute blockchain. Sans elle, aucune des promesses fondamentales — intégrité des données, authenticité des transactions, résistance à la falsification — ne pourrait tenir. Ce chapitre présente les primitives cryptographiques essentielles à la compréhension de Solana et, plus largement, de tout système distribué décentralisé.

Nous commencerons par les fonctions de hachage, qui permettent de condenser une quantité arbitraire de données en une empreinte de taille fixe. Nous verrons ensuite comment ces empreintes s’organisent en arbres de Merkle pour vérifier efficacement l’intégrité d’un ensemble de transactions. La cryptographie asymétrique et les signatures numériques fourniront le mécanisme d’authentification, et nous terminerons par les adresses et portefeuilles, qui sont la couche visible pour l’utilisateur final.

Le lecteur familier avec Rust et la programmation n’aura aucune difficulté a suivre les demonstrations en Python proposées ici. Elles servent uniquement à illustrer les concepts ; les implémentations de production utilisent des bibliothèques optimisées et auditées. L’objectif est de comprendre pourquoi ces primitives fonctionnent, pas de réimplementer une bibliothèque cryptographique.

Fonctions de hachage

Définition 12 (Fonction de hachage cryptographique)

Une fonction de hachage cryptographique est une fonction \(H : \{0,1\}^* \to \{0,1\}^n\) qui transforme une entrée de taille arbitraire en une sortie de taille fixe \(n\) (le condensat ou hash). Elle satisfait les propriétés suivantes :

1. Déterminisme. Pour une entrée \(m\) donnée, \(H(m)\) produit toujours la même sortie.

2. Effet avalanche. Une modification minime de l’entrée (un seul bit) entraine un changement radical et imprévisible de la sortie.

3. Résistance a la préimage. Etant donne un hash \(h\), il est calculatoirement infaisable de trouver \(m\) tel que \(H(m) = h\).

4. Résistance aux collisions. Il est calculatoirement infaisable de trouver deux entrées distinctes \(m_1 \neq m_2\) telles que \(H(m_1) = H(m_2)\).

Dans le contexte de la blockchain, les fonctions de hachage servent à identifier de manière unique les blocs, les transactions et les comptes. SHA-256 produit un condensat de 256 bits (32 octets), soit \(2^{256}\) valeurs possibles — un nombre superieur au nombre d’atomes dans l’univers observable.

SHA-256 en pratique

La bibliotheque standard Python fournit hashlib, qui donne accès à SHA-256 sans dépendance externe.

import hashlib

message = "Solana est rapide"
h = hashlib.sha256(message.encode()).hexdigest()

print(f"Message : {message}")
print(f"SHA-256 : {h}")
print(f"Longueur du hash (hex) : {len(h)} caractères = {len(h)*4} bits")

Message : Solana est rapide
SHA-256 : 43ad8b967cb036962138ce88a92798cbcfac5f542d0f64ba1fa29c9e709e9f32
Longueur du hash (hex) : 64 caractères = 256 bits

Le hash hexadecimal fait toujours 64 caractères, soit 256 bits, quelle que soit la taille de l’entrée. Un roman entier ou un seul caractère produisent un hash de la même longueur.

Effet avalanche

L’effet avalanche est une propriété cruciale : deux entrées quasi identiques doivent produire des hashs radicalement différents. Mesurons cela en comparant les représentations binaires bit à bit.

Show code cell source

Hide code cell source

import hashlib
import matplotlib.pyplot as plt
import seaborn as sns

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

def sha256_bits(text: str) -> list[int]:
    """Retourne la liste des 256 bits du hash SHA-256."""
    h = hashlib.sha256(text.encode()).digest()
    bits = []
    for byte in h:
        for i in range(7, -1, -1):
            bits.append((byte >> i) & 1)
    return bits

msg_a = "Solana"
msg_b = "Solsna"  # une seule lettre changee

bits_a = sha256_bits(msg_a)
bits_b = sha256_bits(msg_b)

differences = [a ^ b for a, b in zip(bits_a, bits_b)]
nb_diff = sum(differences)

print(f"Message A : {msg_a!r}")
print(f"Message B : {msg_b!r}")
print(f"Bits differents : {nb_diff} / 256 ({nb_diff/256*100:.1f} %)")

fig, ax = plt.subplots(figsize=(12, 2.5))
colors = ["#2196F3" if d == 0 else "#F44336" for d in differences]
ax.bar(range(256), [1]*256, color=colors, width=1.0, edgecolor="none")
ax.set_xlim(0, 255)
ax.set_xlabel("Position du bit")
ax.set_title(
    f"Effet avalanche : bits identiques (bleu) vs differents (rouge) — "
    f"{nb_diff}/256 bits modifies"
)
ax.set_yticks([])
plt.show()

Message A : 'Solana'
Message B : 'Solsna'
Bits differents : 134 / 256 (52.3 %)

On observe qu’environ la moitié des bits changent, ce qui est exactement le comportement attendu d’une bonne fonction de hachage. Un attaquant ne peut pas prédire quels bits vont changer ni dans quelle direction.

Remarque 6 (SHA-256, Keccak et SHA-3)

Les différentes blockchains n’utilisent pas toutes la même fonction de hachage :

• Bitcoin et Solana utilisent SHA-256, une fonction de la famille SHA-2 conçue par la NSA et standardisée par le NIST en 2001.

• Ethereum utilise Keccak-256, le candidat qui a remporté le concours SHA-3 du NIST. Attention : le Keccak utilisé par Ethereum diffère légèrement du standard SHA-3 final (padding différent).

• SHA-3 (FIPS 202) est la version standardisée de Keccak, avec un padding modifié.

Le choix de SHA-256 par Solana s’explique par sa maturité, sa large disponibilité en matériel (instructions CPU dediées sur les processeurs modernes), et sa compatibilité avec le mécanisme de Proof of History qui requiert un hachage sequentiel rapide.

Arbres de Merkle

Définition 13 (Arbre de Merkle)

Un arbre de Merkle est un arbre binaire complêt dans lequel :

• Chaque feuille contient le hash d’un bloc de données (par exemple, une transaction).

• Chaque noeud interne contient le hash de la concaténation de ses deux enfants : \(H(\text{gauche} \| \text{droite})\).

• La racine de Merkle (Merkle root) est le hash unique au sommet de l’arbre.

Cette structure permet de vérifier l’intégrité d’un ensemble de données de taille \(n\) en ne fournissant que \(\lceil \log_2 n \rceil\) hashs (la preuve de Merkle ou preuve d’inclusion). Modifier une seule transaction invalide la racine, car le changement se propage à travers tous les noeuds parents.

Construction d’un arbre de Merkle

Construisons un arbre de Merkle à partir de quatre transactions fictives.

Show code cell source

Hide code cell source

import hashlib

def sha256(data: str) -> str:
    """Hash SHA-256, retourne l'hexadecimal."""
    return hashlib.sha256(data.encode()).hexdigest()

# Quatre transactions fictives
transactions = [
    "Alice -> Bob : 5 SOL",
    "Bob -> Charlie : 2 SOL",
    "Charlie -> Diana : 1 SOL",
    "Diana -> Alice : 3 SOL",
]

# Niveau 0 : feuilles
feuilles = [sha256(tx) for tx in transactions]
print("=== Feuilles ===")
for i, (tx, h) in enumerate(zip(transactions, feuilles)):
    print(f"  H{i} = {h[:16]}...  <- {tx}")

# Niveau 1 : noeuds internes
n1_gauche = sha256(feuilles[0] + feuilles[1])
n1_droite = sha256(feuilles[2] + feuilles[3])
print("\n=== Niveau 1 ===")
print(f"  N1_G = {n1_gauche[:16]}...  <- H0 + H1")
print(f"  N1_D = {n1_droite[:16]}...  <- H2 + H3")

# Niveau 2 : racine
racine = sha256(n1_gauche + n1_droite)
print(f"\n=== Racine de Merkle ===")
print(f"  Root = {racine[:16]}...  <- N1_G + N1_D")

=== Feuilles ===
  H0 = 95f0ff77c81320db...  <- Alice -> Bob : 5 SOL
  H1 = b06a71fb73285f54...  <- Bob -> Charlie : 2 SOL
  H2 = da334eeece3cd23b...  <- Charlie -> Diana : 1 SOL
  H3 = 85c208b456d076ff...  <- Diana -> Alice : 3 SOL

=== Niveau 1 ===
  N1_G = 8f07e08ad8d10f9c...  <- H0 + H1
  N1_D = 1d841b1e838a4ff7...  <- H2 + H3

=== Racine de Merkle ===
  Root = 0d78e54ae6e17ae0...  <- N1_G + N1_D

Visualisation de l’arbre

Show code cell source

Hide code cell source

import networkx as nx
import matplotlib.pyplot as plt
import seaborn as sns

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

G = nx.DiGraph()

labels = {}
# Feuilles (niveau 0)
for i, h in enumerate(feuilles):
    node_id = f"H{i}"
    G.add_node(node_id)
    labels[node_id] = f"H{i}\n{h[:8]}..."

# Noeuds internes (niveau 1)
G.add_node("N1_G")
labels["N1_G"] = f"N1_G\n{n1_gauche[:8]}..."
G.add_node("N1_D")
labels["N1_D"] = f"N1_D\n{n1_droite[:8]}..."

# Racine (niveau 2)
G.add_node("Root")
labels["Root"] = f"Root\n{racine[:8]}..."

# Aretes
G.add_edges_from([
    ("Root", "N1_G"), ("Root", "N1_D"),
    ("N1_G", "H0"), ("N1_G", "H1"),
    ("N1_D", "H2"), ("N1_D", "H3"),
])

# Positions manuelles (arbre de haut en bas)
pos = {
    "Root": (3, 3),
    "N1_G": (1.5, 2), "N1_D": (4.5, 2),
    "H0": (0.5, 1), "H1": (2.5, 1),
    "H2": (3.5, 1), "H3": (5.5, 1),
}

fig, ax = plt.subplots(figsize=(10, 5))
node_colors = ["#FF7043" if n == "Root" else "#42A5F5" if n.startswith("N") else "#66BB6A" for n in G.nodes()]
nx.draw(
    G, pos, labels=labels, with_labels=True, ax=ax,
    node_color=node_colors, node_size=3000, font_size=8,
    font_weight="bold", arrows=True, arrowsize=15,
    edge_color="#999999", node_shape="s",
)
ax.set_title("Arbre de Merkle — 4 transactions")
plt.show()

Exemple 5 (Preuve d’inclusion)

Supposons qu’un noeud léger du réseau veuille vérifier que la transaction "Bob -> Charlie : 2 SOL" (feuille \(H_1\)) appartient bien à l’arbre dont la racine est connue. Il n’a pas besoin de connaitre toutes les transactions : il lui suffit de recevoir la preuve de Merkle, composée des hashs complémentaires sur le chemin vers la racine.

Pour vérifier \(H_1\) :

1. On reçoit \(H_0\) (le frère de \(H_1\)).

2. On calcule \(N_{1,G} = H(H_0 \| H_1)\).

3. On reçoit \(N_{1,D}\) (le frère de \(N_{1,G}\)).

4. On calcule \(\text{Root} = H(N_{1,G} \| N_{1,D})\).

5. On compare avec la racine connue.

Deux hashs supplémentaires suffisent pour vérifier une transaction parmi quatre. La preuve est de taille \(O(\log_2 n)\).

Remarque 7 (Efficacité logarithmique)

Pour un arbre contenant \(n\) transactions, la preuve d’inclusion nécessite exactement \(\lceil \log_2 n \rceil\) hashs. Cela signifie que :

Transactions (\(n\))	Hashs nécessaires
1 000	10
1 000 000	20
1 000 000 000	30

Cette efficacité logarithmique est la raison pour laquelle les noeuds légers (light clients) peuvent vérifier des transactions sans télécharger l’intégralité de la blockchain. Dans Solana, les arbres de Merkle sont utilisés pour vérifier l’état des comptes via les state proofs.

Cryptographie asymétrique

Définition 14 (Cryptographie asymétrique)

La cryptographie asymétrique (ou cryptographie à clé publique) repose sur une paire de clés mathématiquement liées :

• La clé privée \(sk\) (secret key) : un nombre aléatoire que le propriétaire garde secret.

• La clé publique \(pk\) (public key) : derivée de la cle privée par une fonction à sens unique \(pk = f(sk)\).

La propriété fondamentale est qu’il est facile de calculer \(pk\) à partir de \(sk\), mais calculatoirement infaisable de retrouver \(sk\) à partir de \(pk\). Cette asymétrie permet deux operations :

1. Chiffrement. N’importe qui peut chiffrer un message avec \(pk\) ; seul le détenteur de \(sk\) peut le déchiffrer.

2. Signature. Le détenteur de \(sk\) signe un message ; n’importe qui peut vérifier la signature avec \(pk\).

En blockchain, c’est principalement la signature qui est utilisée : elle prouve que l’auteur d’une transaction possède la clé privée associée au compte, sans jamais révéler cette clé.

Définition 15 (Courbe elliptique)

Une courbe elliptique sur un corps fini \(\mathbb{F}_p\) est l’ensemble des points \((x, y)\) satisfaisant une équation de la forme :

\[y^2 = x^3 + ax + b \pmod{p}\]

avec un point à l’infini \(\mathcal{O}\) servant d’élément neutre pour une loi de groupe. La cryptographie sur courbes elliptiques (ECC) exploite le problème du logarithme discret sur ce groupe : étant donné un point générateur \(G\) et un point \(Q = k \cdot G\) (addition répétée de \(G\) avec lui-même \(k\) fois), retrouver \(k\) est calculatoirement infaisable pour des paramètres de taille suffisante.

La clé privée est un scalaire \(k\), et la clé publique est le point \(Q = k \cdot G\) sur la courbe.

Remarque 8 (Ed25519 vs secp256k1)

Les blockchains majeures n’utilisent pas toutes la même courbe :

• Bitcoin et Ethereum utilisent secp256k1, une courbe de Koblitz définie par \(y^2 = x^3 + 7\) sur \(\mathbb{F}_p\). Le choix historique de Satoshi Nakamoto s’explique par la disponibilité de paramètres publics non suspectes de contenir des portes dérobées.

• Solana utilise Ed25519, une courbe d’Edwards tordue définie sur \(\mathbb{F}_p\) avec \(p = 2^{255} - 19\). Ed25519 offre plusieurs avantages :

  • Performance. La vérification de signature est plus rapide (facteur 2x à 3x selon les implémentations).

  • Déterminisme. La génération de signature est déterministe (pas besoin de nonce aléatoire), ce qui élimine une classe entière de vulnérabilités (cf. la faille de la PlayStation 3).

  • Résistance aux attaques par canaux auxiliaires. Les opérations sur la courbe d’Edwards sont à temps constant par conception.

Le choix d’Ed25519 par Solana est cohérent avec sa philosophie de performance maximale.

Remarque 9 (Taille des clés)

Avec Ed25519, la cle privée fait 32 octets (256 bits) et la clé publique fait egalement 32 octets (un point compressé sur la courbe). Cela donne un niveau de sécurité d’environ 128 bits, c’est-a-dire qu’une attaque par force brute nécessite de l’ordre de \(2^{128}\) operations — bien au-dela des capacités de calcul mondiales actuelles et prévisibles.

Signatures numériques

Définition 16 (Signature numérique)

Un schéma de signature numérique est un triplet d’algorithmes :

1. Génération de clés \(\text{KeyGen}() \to (sk, pk)\) : produit une paire clé privée / clé publique.

2. Signature \(\text{Sign}(sk, m) \to \sigma\) : à partir de la clé privée et d’un message \(m\), produit une signature \(\sigma\).

3. Vérification \(\text{Verify}(pk, m, \sigma) \to \{\text{vrai}, \text{faux}\}\) : à partir de la clé publique, du message et de la signature, détermine si la signature est valide.

Les propriétés requises sont :

• Correction. Une signature produite avec \(sk\) est toujours acceptée par \(\text{Verify}\) avec le \(pk\) correspondant.

• Infalsifiabilité. Sans connaitre \(sk\), il est calculatoirement infaisable de produire une signature valide pour un message quelconque.

Exemple 6 (Schéma de signature simplifie)

Pour illustrer le principe de la signature sans recourir à une bibliothèque de courbes elliptiques, voici un schéma simplifié basé sur le hachage. Ce schéma n’est pas cryptographiquement sûr — il sert uniquement à montrer le flux signer/vérifier.

L’idée : la signature est un hash qui combine la clé privée et le message. La vérification recalcule ce hash et compare.

import hashlib
import secrets

def keygen():
    """Génère une paire (cle_privee, cle_publique) simplifiée."""
    sk = secrets.token_hex(32)             # 256 bits aleatoires
    pk = hashlib.sha256(sk.encode()).hexdigest()  # la clé publique dérive de la privée
    return sk, pk

def sign(sk, message):
    """Signe un message avec la clé privée."""
    return hashlib.sha256((sk + message).encode()).hexdigest()

def verify(pk, message, signature, sk):
    """Vérifie la signature (schéma simplifié, nécessite sk en pratique
    car notre schema est trop simple --- en vrai, seule pk suffit)."""
    expected = hashlib.sha256((sk + message).encode()).hexdigest()
    return signature == expected

Dans un vrai schéma comme Ed25519, la vérification n’utilise que la clé publique grâce aux propriétés mathématiques de la courbe elliptique. Le principe reste le même : seul le détenteur de la clé privée peut produire une signature que tout le monde peut vérifier.

Flux de signature dans une transaction Solana

Show code cell source

Hide code cell source

import hashlib
import secrets

# --- Simulation pédagogique ---

# 1. Génération des clés
cle_privee = secrets.token_hex(32)
cle_publique = hashlib.sha256(cle_privee.encode()).hexdigest()

# 2. Message à signer (une transaction simplifiée)
transaction = "Transferer 5 SOL de Alice a Bob"

# 3. Signature
signature = hashlib.sha256((cle_privee + transaction).encode()).hexdigest()

# 4. Vérification (simulée)
hash_verif = hashlib.sha256((cle_privee + transaction).encode()).hexdigest()
est_valide = signature == hash_verif

print(f"Clé publique : {cle_publique[:32]}...")
print(f"Transaction  : {transaction}")
print(f"Signature    : {signature[:32]}...")
print(f"Valide       : {est_valide}")

# 5. Tentative de falsification
fausse_tx = "Transférer 5000 SOL de Alice à Mallory"
fausse_sig = hashlib.sha256(("cle_inconnue" + fausse_tx).encode()).hexdigest()
est_valide_fausse = fausse_sig == hashlib.sha256((cle_privee + fausse_tx).encode()).hexdigest()

print(f"\n--- Tentative de falsification ---")
print(f"Transaction  : {fausse_tx}")
print(f"Valide       : {est_valide_fausse}")

Clé publique : 537220621372bd93d2ff69fc4250428a...
Transaction  : Transferer 5 SOL de Alice a Bob
Signature    : 1160128c712e089385b6db4201022871...
Valide       : True

--- Tentative de falsification ---
Transaction  : Transférer 5000 SOL de Alice à Mallory
Valide       : False

Remarque 10 (Non-répudiation)

La propriété de non-répudiation signifie que l’auteur d’une signature ne peut pas nier l’avoir produite. En blockchain, cela à une consequence directe : si une transaction est signée avec votre clé privée, vous en êtes l’auteur. Il n’existe aucun mécanisme de contestation ni d’annulation.

C’est pourquoi la sécurité de la clé privée est absolument critique. Quiconque obtient votre cle privée peut signer des transactions en votre nom, et ces transactions seront considérées comme légitimement les vôtres par le réseau.

Remarque 11 (Signatures multiples dans Solana)

Une transaction Solana peut contenir plusieurs signatures. Chaque compte qui doit autoriser la transaction (marque comme signer dans l’instruction) doit fournir sa signature. Cela permet des schémas comme :

• Les comptes multisig (plusieurs clés doivent signer).

• Les frais payés par un tiers (le payeur de frais signe en plus de l’initiateur).

• Les cross-program invocations ou un programme signé au nom d’un PDA (Program Derived Address).

Adresses et portefeuilles

Définition 17 (Portefeuille)

Un portefeuille (wallet) est un logiciel ou un dispositif matériel qui stocke une ou plusieurs clés privées et permet de signer des transactions. Le portefeuille ne « contient » pas de crypto-monnaie à proprement parler : les soldes sont enregistrés sur la blockchain. Le portefeuille détient uniquement la capacité de prouver la propriété d’un compte via la signature.

Définition 18 (Adresse Solana)

Une adresse Solana est l’encodage en Base58 de la clé publique Ed25519 (32 octets). L’alphabet Base58 exclut les caractères ambigüs (0, O, I, l) pour éviter les erreurs de transcription :

\[\text{Base58} = \{1, 2, \ldots, 9, A, B, \ldots, H, J, \ldots, N, P, \ldots, Z, a, \ldots, k, m, \ldots, z\}\]

Une adresse Solana typique ressemble a : 7xKXtg2CW87d97TXJSDpbD5jBkheTqA83TZRuJosgAsU.

Encodage Base58

Show code cell source

Hide code cell source

BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

def base58_encode(data: bytes) -> str:
    """Encode des octets en Base58 (version simplifiée)."""
    # Compter les octets nuls en tete
    leading_zeros = 0
    for byte in data:
        if byte == 0:
            leading_zeros += 1
        else:
            break

    # Convertir les octets en un grand entier
    n = int.from_bytes(data, byteorder="big")

    # Convertir en Base58 par divisions successives
    result = []
    while n > 0:
        n, remainder = divmod(n, 58)
        result.append(BASE58_ALPHABET[remainder])

    # Ajouter les '1' pour les octets nuls en tête
    result.extend("1" * leading_zeros)

    return "".join(reversed(result))

# Simuler une clé publique Ed25519 (32 octets aleatoires)
import secrets
fake_pubkey = secrets.token_bytes(32)

adresse = base58_encode(fake_pubkey)
print(f"Cle publique (hex)  : {fake_pubkey.hex()}")
print(f"Adresse (Base58)    : {adresse}")
print(f"Longueur de l'adresse : {len(adresse)} caracteres")

Cle publique (hex)  : 03dd70787cb312ea334b98c842a717e7933ee6da38dfae821afe73b39fa48dc6
Adresse (Base58)    : G64nDprbqGHHbonX9V8o2pvtnZePmFqem9Bm16Ao7mP
Longueur de l'adresse : 43 caracteres

Remarque 12 (Comparaison des formats d’adresse)

Blockchain	Format	Exemple
Solana	Base58 (clé publique brute)	7xKXtg2CW87d97TXJSDpbD5jBkheTqA83TZRuJosgAsU
Ethereum	Héxadecimal avec préfixe 0x, checksum EIP-55	0xd8dA6BF26964aF9D7eEd9e03E53415D37aA96045
Bitcoin	Base58Check (hash de la clé publique + checksum)	1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa

Solana utilise directement la clé publique comme adresse (32 octets encodes en Base58), sans hachage intermediaire. Cela simplifie la derivation mais signifie que la cle publique est toujours exposée. Ethereum hache la clé publique avec Keccak-256, puis tronque a 20 octets. Bitcoin ajoute un checksum de 4 octets pour détecter les erreurs de saisie.

Exemple 7 (Dérivation d’adresse sur Solana)

Le processus complet de création d’une adresse Solana est remarquablement simple :

1. Générer 32 octets aléatoires cryptographiquement sûrs : c’est la clé privée.

2. Calculer le point correspondant sur la courbe Ed25519 : c’est la clé publique (32 octets).

3. Encoder la clé publique en Base58 : c’est l”adresse.

Il n’y a pas de hachage intermédiaire ni de checksum ajoute. La simplicité de ce processus contribue a la performance de Solana : chaque vérification de signature est une opération sur Ed25519, sans étape supplémentaire de décodage d’adresse.

Remarque 13 (Seed phrases et HD wallets)

En pratique, les utilisateurs ne manipulent pas directement les clés privées. Les portefeuilles modernes utilisent une phrase mnémonique (seed phrase) de 12 ou 24 mots (standard BIP-39) à partir de laquelle un arbre hiérarchique de clés est dérivé (standard BIP-44). Cela permet de :

• Sauvegarder l’ensemble de ses clés avec une seule phrase.

• Générer un nombre illimité de paires de clés de manière déterministe.

• Restaurer un portefeuille sur un autre appareil.

Solana utilise le chemin de dérivation m/44'/501'/0'/0' dans la hiérarchie BIP-44, ou 501 est le numéro de coin enregistré pour Solana.

Paradoxe des anniversaires et sécurité

Définition 19 (Paradoxe des anniversaires)

Le paradoxe des anniversaires énonce que dans un ensemble de \(n\) valeurs aléatoires prises uniformément parmi \(N\) possibilités, la probabilité d’observer au moins une collision (deux valeurs identiques) dépasse 50 % dès que \(n \approx \sqrt{N}\).

Pour une fonction de hachage produisant des condensats de \(b\) bits (\(N = 2^b\)), une attaque par anniversaire peut trouver une collision en environ \(2^{b/2}\) tentatives au lieu de \(2^b\). C’est pourquoi un hash de 256 bits offre une securité de 128 bits contre les collisions, et un hash de 128 bits n’offre que 64 bits de securité — insuffisant face aux capacités de calcul modernes.

Exemple 8 (Calcul de la probabilité de collision)

La probabilité qu’il n’y ait aucune collision après \(k\) tirages dans un espace de taille \(N\) est :

\[P(\text{pas de collision}) = \prod_{i=0}^{k-1} \left(1 - \frac{i}{N}\right) \approx e^{-k(k-1)/(2N)}\]

Pour \(k = 2^{b/2}\), cette probabilité tombe à environ \(e^{-1/2} \approx 0.607\), soit environ 39.3 % de chance de n’avoir aucune collision, ou 60.7 % de chance d’en avoir au moins une. En securité, on considère qu’une attaque est réalisable dès que la probabilité de succès dépasse quelques pourcents.

Show code cell source

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

def collision_probability(k: np.ndarray, b: int) -> np.ndarray:
    """Probabilite de collision apres k tentatives pour un hash de b bits.
    Utilise l'approximation P(collision) ≈ 1 - exp(-k^2 / (2 * 2^b))."""
    return 1.0 - np.exp(-k**2 / (2.0 * 2**b))

fig, ax = plt.subplots(figsize=(10, 6))

hash_sizes = [
    (64, "$2^{64}$ (64 bits)", "#F44336"),
    (128, "$2^{128}$ (128 bits)", "#FF9800"),
    (256, "$2^{256}$ (256 bits)", "#4CAF50"),
]

for b, label, color in hash_sizes:
    # On trace de 1 a 2^(b/2 + 4) tentatives, en échelle log
    exponents = np.linspace(0, b/2 + 4, 500)
    k = np.power(2.0, exponents)
    prob = collision_probability(k, b)
    ax.plot(exponents, prob, label=label, color=color, linewidth=2)
    # Marquer le seuil 50%
    ax.axvline(x=b/2, color=color, linestyle="--", alpha=0.4)

ax.axhline(y=0.5, color="gray", linestyle=":", alpha=0.5, label="Seuil 50 %")
ax.set_xlabel("Nombre de tentatives ($\\log_2 k$)")
ax.set_ylabel("Probabilite de collision")
ax.set_title("Paradoxe des anniversaires : probabilite de collision\nselon la taille du hash")
ax.set_ylim(0, 1.05)
ax.legend(loc="upper left")
plt.show()

Remarque 14 (Implications pour la sécurité des blockchains)

Le paradoxe des anniversaires explique pourquoi les fonctions de hachage utilisées en blockchain doivent avoir des condensats d’au moins 256 bits. Avec SHA-256 :

• Une attaque par préimage nécessite \(\sim 2^{256}\) operations.

• Une attaque par collision nécessite \(\sim 2^{128}\) operations.

A titre de comparaison, le réseau Bitcoin realise environ \(10^{20}\) hashs par seconde. Même a cette puissance, il faudrait \(2^{128} / 10^{20} \approx 10^{18}\) secondes, soit environ 30 milliards d’années, pour espérer trouver une collision.

Remarque 15 (Menace quantique)

L’algorithme de Grover (informatique quantique) permet de réduire la compléxité d’une recherche par force brute de \(2^n\) a \(2^{n/2}\). Pour SHA-256, cela ramenerait la résistance à la préimage de \(2^{256}\) a \(2^{128}\) opérations quantiques — ce qui reste hors de portée. En revanche, l’algorithme de Shor pourrait casser la cryptographie sur courbes elliptiques en temps polynomial. C’est pourquoi la recherche en cryptographie post-quantique est active, et les blockchains devront éventuellement migrer vers des schémas de signature résistants aux ordinateurs quantiques.

Résumé

Le tableau suivant récapitule les primitives cryptographiques abordées dans ce chapitre et leur rôle dans la blockchain Solana.

Primitive	Rôle dans Solana	Propriété clé
SHA-256	Hachage des blocs, Proof of History	Résistance aux collisions (\(2^{128}\))
Arbre de Merkle	Vérification d’état, preuves d’inclusion	Vérification en \(O(\log n)\)
Ed25519	Paires de clés, signatures de transactions	Vérification rapide, déterministe
Signature numérique	Authentification des transactions	Non-répudiation
Base58	Encodage des adresses	Lisibilité, pas de caracteres ambigüs
Paradoxe des anniversaires	Dimensionnement de la securité	Securité = taille du hash / 2

Chacune de ces briques s’emboite dans la suivante : les fonctions de hachage alimentent les arbres de Merkle, la cryptographie asymétrique permet les signatures, et les signatures protègent les transactions que l’on envoie depuis son portefeuille. Le chapitre suivant montrera comment ces primitives s’assemblent dans un protocole de consensus pour garantir l’accord entre les noeuds du réseau.