Les codes de vérification de la parité de faible densité (LDPC) sont depuis longtemps la pierre angulaire des communications numériques modernes, offrant une correction d'erreur quasi-shannon-limite avec des algorithmes de décodage efficaces.Dans le contexte de la technologie de la chaîne de blocs, où l'intégrité des données est primordiale mais souvent mise en cause par la demande croissante de stockage et l'évolutivité du réseau, les codes LDPC présentent un outil supplémentaire convaincant.

Principes fondamentaux des codes LDPC

Les codes LDPC sont des codes de blocs linéaires définis par une matrice de vérification par parité clairsemée, une matrice qui contient un très petit nombre d'entrées non nulles par rapport à ses dimensions. Cette sparté est la clé de leur décodage itératif efficace, généralement effectué en utilisant la propagation de croyances (algorithme de produit-somme) sur le graphique Tanner associé. Inventé à l'origine par Robert Gallager dans sa thèse de doctorat de 1963, les codes LDPC ont été largement négligés jusqu'à la fin des années 1990 quand ils ont été redécouverts indépendamment et montrés pour approcher la limite Shannon.

Le principal avantage des codes LDPC par rapport aux codes correcteurs d'erreurs antérieurs comme Reed–Solomon ou les codes convolutionnels est leur capacité à atteindre des taux d'erreur très faibles avec une complexité modérée. Le décodage est parallélisant, ce qui les rend adaptés aux applications à haut débit. La capacité de correction est fonction de la variation du taux de code (rapport des bits d'information avec les bits totaux) et de la conception de la matrice de vérification de parité.

Vérification de l'intégrité des données dans les Blockchains

Mécanismes traditionnels

Les systèmes Blockchain assurent l'intégrité des données principalement par le hachage cryptographique. Chaque bloc contient un hachage du bloc précédent, formant une chaîne immuable. Les arbres de mercelle, une structure où les noeuds foliaires sont des blocs de données et les noeuds non foliaires sont des hachages de leurs enfants, permettent une vérification efficace des gros ensembles de données avec seulement la mémoire O(log n) pour les preuves. Bitcoin et Ethereum utilisent les hachages SHA-256 ou Keccak-256. Bien que ces mécanismes fournissent des preuves de manipulations solides, ils ne corrigent pas intrinsèquement les erreurs.

De plus, comme les chaînes de blocs s'échellent pour gérer les téraoctets de données (par exemple, dans les réseaux de stockage décentralisés comme Filecoin ou Arweave, ou dans les propositions de sharding de disponibilité des données comme Danksharding d'Ethereum), le coût de stockage de toutes les données sur chaque noeud devient prohibitif. Les clients légers comptent sur l'échantillonnage aléatoire de morceaux et la vérification contre les racines Merkle, mais cette approche ne peut garantir la récupération complète des données si les morceaux manquants ou corrompus dépassent le budget d'échantillonnage du client.

Le rôle des codes LDPC dans l'intégrité des données de la chaîne de blocs

Amélioration de l'effacement et de la correction d'erreurs

L'intégration des codes LDPC dans un système de blockchain implique l'encodage des blocs de données dans des mots de code plus longs avant qu'ils ne soient engagés dans la chaîne. Le module de données original peut être divisé en k symboles d'information, puis étendu en n symboles (taux de code k/n) à l'aide d'un encodeur LDPC. Les symboles de parité sont stockés comme données auxiliaires, soit dans la même transaction, soit dans une couche de disponibilité des données séparée. Lorsqu'un client de noeud ou de lumière reçoit un sous-ensemble de symboles, il peut tenter de décoder.

Cette capacité est particulièrement utile dans les protocoles qui reposent sur l'échantillonnage de la disponibilité des données (DAS).Dans DAS, un client léger échantillonne aléatoirement un petit nombre de morceaux d'un bloc. En utilisant un code LDPC, le client peut vérifier avec une forte probabilité que le bloc est entièrement disponible, parce que si un adversaire cache trop de morceaux, le client léger ne pourra probablement pas décoder. La sparsité de la matrice de vérification de parité signifie également que le décodage peut être effectué en temps linéaire par rapport à la longueur du bloc, ce qui le rend possible même pour les appareils qui ne sont pas dotés de ressources.

Comparaison avec d'autres codes

Les codes Reed–Solomon, le choix traditionnel pour l'effacement du codage dans les systèmes blockchain (p. ex., dans BIP152 original de Bitcoin ou dans les propositions de disponibilité des données d'Ethereum), exigent un codage/décodage O(n log n) et ne sont pas aussi efficaces pour les grandes tailles de blocs. Les codes LDPC offrent O(n) décodage de la complexité avec des garanties plus graves qui sont nettement meilleures pour les taux de code élevés.

Cependant, les codes LDPC ont des inconvénients. Ils ne sont pas universellement optimaux pour toutes les tailles de blocs; la meilleure performance de décodage nécessite souvent de grandes longueurs de blocs (1000 à 10000 bits), ce qui peut ajouter de la latence. La conception d'une bonne matrice de contrôle de parité pour une application de blockchain spécifique est non-triviale et peut nécessiter un cycle-évitement (par exemple, éviter les courts cycles dans le graphique Tanner) pour empêcher les planchers d'erreur.

Considérations relatives à la mise en œuvre

Architecture de codage et de décodage

Pour l'intégration à la chaîne ou à la couche de consensus, le codeur et le décodeur LDPC doivent être soit mis en œuvre dans l'environnement d'exécution (par exemple, comme précompilateur dans la machine virtuelle Ethereum) soit exécutés hors chaîne par des validateurs. Ce dernier est plus courant, car le coût de la mise en oeuvre du décodage LDPC est modéré mais reste important pour les calculs de gaz à l'intérieur de la transaction.

La consommation de mémoire est préoccupante : bien que la matrice de contrôle de parité soit clairsemée, elle est stockée comme une matrice complète pour les grandes n peut être invraisemblable. Les implémentations utilisent des codes structurés tels que les codes LDPC quasi cycliques (QC), où la matrice est composée de sous- matrices de permutation circulante. Les codes QC-LDPC réduisent considérablement les exigences de stockage (déterministe à partir d'une graine) et permettent un encodeur efficace à l'aide de registres de changement.

Incidences sur la sécurité

Les codes LDPC ne fournissent pas de sécurité cryptographique par eux-mêmes. Un attaquant ayant la capacité de corrompre des symboles ne peut pas être empêché de le faire, mais le code peut corriger jusqu'à un certain nombre d'erreurs. Si le taux d'erreur dépasse la capacité de correction du code, les données deviennent inrécupérables. Dans un réglage blockchain, cela pourrait conduire à des échecs de la vivacité ou des attaques de renversement.

Pour contrer cela, les paramètres de code (description de la matrice, taux de code, graine pour structure) doivent être engagés dans l'en-tête de bloc, et tous les noeuds honnêtes doivent utiliser la même matrice. Cette exigence s'harmonise avec les propriétés de transparence de la chaîne de blocs : chaque noeud peut vérifier l'encodage indépendamment. Cependant, cela signifie aussi que la matrice doit être déterministe et contrôlable efficacement, ce qui est possible pour les codes QC-LDPC.

Scalabilité et débit

Les codes LDPC excellent dans les scénarios à haut débit car le décodage est très parallélisant à l'aide de GPU ou de circuits intégrés spécifiques à une application. Pour les réseaux de blockchain traitant des centaines de transactions par seconde, le latence d'encodage/decoding doit rester en dessous de l'intervalle de blocs.

Pour les clients légers, la possibilité de décoder à partir d'un sous-ensemble aléatoire de symboles signifie qu'ils peuvent obtenir des probabilités élevées de disponibilité des données avec seulement quelques centaines de kilooctets de données téléchargées par bloc. Cela contraste avec la vérification du nœud complet qui nécessite le téléchargement de l'ensemble du bloc.

Applications pratiques et projets

Couches de disponibilité des données

Plusieurs projets de blockchain explorent déjà le codage par effacement pour la disponibilité des données. Celestia, une blockchain modulaire axée sur la disponibilité des données, initialement considérée à l'aide de 2D Reed–Solomon, mais a depuis étudié les codes LDPC pour ses prochaines mises à jour. De même, la proposition Danksharding d'Ethereum utilise un schéma de codage par effacement 2D avec Reed–Solomon le long des lignes et des colonnes, mais les variantes LDPC sont à l'étude pour obtenir des gains d'efficacité potentiels.

Une étude notable du Ethereum Research team[ a analysé les compromis entre différents codes d'effacement pour l'échantillonnage de la disponibilité des données.

Réseaux décentralisés de stockage

Le codage par effacement de Filecoin et Arweave (Reed–Solomon) permet d'assurer la durabilité des données. Le remplacement ou le complément des codes LDPC pourraient permettre à ces réseaux de réduire le rapport de frais généraux de stockage (moins de réplication) tout en maintenant le même niveau de récupération. Pour Filecoin, où les mineurs de stockage prouvent la possession par l'intermédiaire de Preuves de la récupération (PdPR), les codes LDPC peuvent servir de code sous-jacent pour générer des protocoles de contestation-réponse.

Dans les applications de chaîne d'approvisionnement et de chaîne de soins de santé, où l'immutabilité des données est combinée avec le stockage blob hors chaîne, les codes LDPC peuvent protéger contre la pourriture bit dans les dépôts de cloud. Les symboles de parité dispersés peuvent être stockés dans plusieurs fournisseurs de cloud, et la chaîne de blocs agit comme une racine de métadonnées assurant que toute combinaison légitime de symboles peut reconstruire les données originales — même si certains fournisseurs perdent des données ou deviennent compromis.

Défis et problèmes ouverts

Malgré les attributs prometteurs, plusieurs défis restent à relever avant que les codes LDPC puissent être largement adoptés dans les systèmes blockchain.

  • Conception du code: Concevoir une matrice de vérification de parité clairsemée qui réalise des planchers à faible erreur pour les longueurs de blocs typiques de la chaîne de blocs (plusieurs kilooctets à mégaoctets) n'est pas trivial. Les codes aléatoires peuvent avoir des problèmes de convergence; les codes QC-LDPC structurés doivent être soigneusement optimisés pour éviter la dégradation des performances.
  • Consensus Overhead:[ L'introduction du codage par effacement au niveau du consensus peut compliquer le protocole de propagation des blocs. Les validateurs doivent attendre suffisamment de durs avant de s'engager — un processus qui augmente la latence. L'interaction entre le temps de reconstruction du LDPC et les temps de dégagement du consensus doit être soigneusement étalonnée.
  • Sécurité pour les clients légers: Bien que les codes LDPC permettent aux clients légers de vérifier la disponibilité des données avec un petit nombre d'échantillons, la preuve de sécurité repose sur l'hypothèse que le code a de bonnes propriétés d'expansion (c.-à-d. que tout ensemble suffisamment grand de symboles manquants sera détecté). Toutes les familles LDPC ne garantissent pas cette propriété; les codes aléatoires sont vulnérables à la sélection contradictoire de symboles manquants.
  • L'intégration avec l'infrastructure existante de blockchain. De nombreuses blockchains de couche‐1 ont des structures de blocs fixes et une vérification native des épreuves de Merkle. L'ajout de la vérification LDPC nécessite des fourches durs ou des composants hors chaîne.
  • Efficacité énergétique : Le décodage LDPC est itératif et peut consommer une puissance importante sur les appareils mobiles ou IoT agissant comme clients légers. Pour ces appareils, le nombre d'itérations de décodage doit être réduit au minimum.

Orientations futures

La recherche à l'intersection de la théorie du codage et de la chaîne de blocs continue d'évoluer. Une direction prometteuse est l'utilisation de codes LDPC (SC-LDPC), qui ont une structure régulière et présentent des propriétés de saturation de seuil, ce qui signifie qu'ils approchent la limite Shannon plus étroitement que la limite classique LDPC. Les codes SC-LDPC pourraient être particulièrement bien adaptés pour les données en streaming dans les chaînes de blocs où les blocs arrivent séquentiellement, car la fenêtre de décodage coulissant permet un traitement à faible latence sans attendre que le bloc entier soit encodé.

Un autre domaine est la combinaison de codes LDPC avec des preuves de connaissance zéro (ZKPs). Par exemple, un prover pourrait démontrer qu'ils détiennent suffisamment de symboles de mots de code valides sans révéler les données originales, en utilisant un circuit zk-SNARK sur les équations de vérification de parité LDPC. Cela permettrait des vérifications de disponibilité de données privées ou la récupération de données privées sur les chaînes de blocs publiques.

Enfin, le développement de décodeurs LDPC accélérés pour les nœuds blockchains — peut-être à l'aide de FPGA — pourrait ramener le temps de décodage pour les blocs téraoctets à quelques secondes, permettant la vision de blockchains massivement évolutives avec une intégrité des données vérifiable.

Conclusion

En permettant une correction rapide des erreurs, un échantillonnage évolutif de la disponibilité des données et une réduction de la redondance de stockage, les codes LDPC traitent de plusieurs goulots d'étranglement fondamentaux auxquels les architectures actuelles de la chaîne de blocs font face. Bien que les défis pratiques de mise en œuvre - en particulier la conception de code, l'intégration consensuelle et la sécurité des clients légers - demeurent des sujets de recherche actifs, l'élan acquis par les projets explorant le codage par effacement pour DAS et le stockage décentralisé suggère que les codes LDPC joueront un rôle de plus en plus important dans la prochaine génération de protocoles de la chaîne de blocs.