2025-11-21T20:28:23.433071

OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

Chen
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ with expected $O(n |\boldsymbol{w}|\log n + n^2 \log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\log n)$ rounds, and expected $O(\log n)$ common coins, under optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.
academic

OciorMVBA : Accord Byzantin Asynchrone Multi-Valeurs Quasi-Optimal et Sans Erreur

Informations de Base

  • ID de l'article : 2501.00214
  • Titre : OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
  • Auteur : Jinyuan Chen
  • Classification : cs.CR (Cryptographie et Sécurité), cs.DC (Informatique Distribuée), cs.IT (Théorie de l'Information), math.IT (Théorie de l'Information)
  • Date de publication : 31 décembre 2024 (prépublication arXiv)
  • Lien de l'article : https://arxiv.org/abs/2501.00214

Résumé

Cet article propose le protocole OciorMVBA, un protocole d'accord byzantin asynchrone multi-valeurs (MVBA) sans erreur et sécurisé au sens de la théorie de l'information. Le protocole atteint un consensus MVBA sur un message w dans un réseau de n nœuds avec une tolérance aux pannes optimale n ≥ 3t + 1, avec une complexité de communication espérée de O(n|w|log n + n²log q) bits, un nombre de messages espéré de O(n²), un nombre de tours espéré de O(log n) et une complexité de pièce commune espérée de O(log n). De plus, deux protocoles variantes sont proposés : OciorMVBArr réalisant une complexité en tours O(1) sous une tolérance aux pannes relâchée n ≥ 5t + 1, et OciorMVBAh basé sur le hachage réalisant une complexité en tours O(1) sous la tolérance aux pannes optimale.

Contexte et Motivation de la Recherche

Définition du Problème

L'accord byzantin asynchrone multi-valeurs (MVBA) est un élément fondamental des systèmes distribués et de la cryptographie, introduit par Cachin et al. en 2001. Dans le MVBA, les nœuds distribués proposent leurs propres valeurs d'entrée et cherchent à atteindre un consensus sur l'une des valeurs satisfaisant une fonction de prédicat prédéfinie (validité externe).

Importance de la Recherche

  1. Fondements théoriques : Les travaux fondateurs de Fischer, Lynch et Paterson démontrent qu'aucun protocole MVBA déterministe n'existe dans un environnement asynchrone, par conséquent tout protocole MVBA asynchrone doit introduire de l'aléatoire
  2. Besoins pratiques : Les systèmes distribués nécessitent d'atteindre un consensus fiable dans des réseaux asynchrones en présence de défaillances byzantines
  3. Exigences de sécurité : Garantir la sécurité au sens de la théorie de l'information sans dépendre d'hypothèses cryptographiques (à l'exception de la pièce commune)

Limitations des Approches Existantes

Comme le montre le tableau I de comparaison, les protocoles MVBA existants présentent les problèmes suivants :

  • La plupart dépendent d'hypothèses cryptographiques telles que les signatures de seuil ou le hachage
  • La complexité de communication est élevée, particulièrement sans hypothèses cryptographiques
  • L'efficacité de la complexité en tours et de l'utilisation de la pièce commune peut être améliorée

Contributions Principales

  1. Proposition du protocole OciorMVBA : Premier protocole MVBA asynchrone sans erreur et sécurisé au sens de la théorie de l'information réalisant une complexité de communication quasi-optimale O(n|w|log n + n²log q) sous la tolérance aux pannes optimale n ≥ 3t + 1
  2. Conception du protocole OciorMVBArr : Protocole réalisant une complexité de communication O(n|w| + n²log n) et une complexité en tours O(1) sous une tolérance aux pannes relâchée n ≥ 5t + 1
  3. Construction du protocole OciorMVBAh : Protocole basé sur le hachage réalisant une complexité de communication O(n|w| + n³) et une complexité en tours O(1) sous la tolérance aux pannes optimale
  4. Introduction de nouvelles primitives : Proposition de l'accord byzantin asynchrone binaire biaisé (ABBBA) et de la dispersion d'information asynchrone complète (ACID) comme nouveaux éléments de construction

Détails de la Méthode

Définition de la Tâche

Entrée : Chaque nœud honnête propose une valeur d'entrée w satisfaisant la fonction de prédicat Predicate(w) = true Sortie : Tous les nœuds honnêtes produisent finalement la même valeur w', et Predicate(w') = true Contraintes : Satisfaire les trois propriétés de cohérence, de terminaison et de validité externe

Architecture du Protocole OciorMVBA

Conception Globale

OciorMVBA est un protocole récursif dont les composants principaux incluent :

  • RMVBA(ID, p) : Protocole MVBA récursif
  • SHMDM : Multicast distribué à majorité honnête forte
  • OciorRBA : Accord byzantin fiable
  • ABBBA : Accord byzantin asynchrone binaire biaisé
  • ABBA : Accord byzantin asynchrone binaire

Flux d'Algorithme Principal

  1. Partitionnement du réseau : Diviser le réseau Sp en deux sous-ensembles disjoints S2p et S2p+1
  2. Appels récursifs : Exécuter en parallèle les sous-protocoles RMVBA sur les sous-réseaux
  3. Propagation de messages : Propager les sorties des sous-protocoles via le protocole SHMDM
  4. Vérification de cohérence : Vérifier la fiabilité des messages en utilisant OciorRBA
  5. Mécanisme d'élection : Déterminer la sortie finale via l'élection ordonnée et les protocoles ABBBA/ABBA

Détails Techniques Clés

Processus Ready-Finish-Confirm :

Étape 1 : Sortie du sous-protocole → Propagation SHMDM
Étape 2 : Sortie SHMDM → Vérification OciorRBA
Étape 3 : Sortie OciorRBA vi=1 → Définir Iready[θ]=1, envoyer message READY
Étape 4 : Recevoir suffisamment de messages READY → Définir Ifinish[θ]=1, envoyer message FINISH
Étape 5 : Recevoir suffisamment de messages FINISH → Définir Iconfirm[θ]=1

Protocole ABBBA :

  • Entrée : Paire binaire (a1, a2)
  • Validité biaisée : Si t+1 nœuds honnêtes entrent a2=1, alors sortir 1
  • Intégrité biaisée : Si la sortie est 1, alors au moins un nœud honnête a entré a1=1 ou a2=1

Conception du Protocole OciorRBA

Basée sur l'extension des protocoles COOL et OciorCOOL, comprenant trois phases :

  1. Phase 1 : Échange de symboles et mise à jour des indicateurs de lien
  2. Phase 2 : Traitement des indicateurs de succès
  3. Phase 3 : Correction d'erreur en ligne et reconstruction de messages

Points d'Innovation Technique

  1. Architecture récursive : Réaliser une complexité en tours logarithmique via partitionnement du réseau et appels récursifs
  2. Accord biaisé : Le protocole ABBBA fournit une terminaison rapide sous certaines conditions
  3. Correction d'erreur en ligne : Utiliser les codes Reed-Solomon ou Expander pour une correction d'erreur efficace
  4. Absence d'hypothèses cryptographiques : Ne dépendre d'aucune primitive cryptographique à l'exception de la pièce commune

Configuration Expérimentale

Cadre d'Analyse Théorique

L'article procède principalement à une analyse théorique, vérifiant les propriétés du protocole par les moyens suivants :

Analyse de complexité :

  • Complexité de communication : Analyse par relations de récurrence
  • Complexité en tours : Analyse par profondeur d'arbre du réseau
  • Complexité en messages : Statistiques du nombre d'interactions du protocole

Preuve de sécurité :

  • Cohérence : Preuve via Lemme 3
  • Terminaison : Analyse par chaînes de réseau (Lemmes 2, 4)
  • Validité externe : Garantie par vérification de prédicat

Références de Comparaison

Comparaison avec les protocoles MVBA existants, incluant :

  • Cachin et al. 1 - Travail fondateur sur MVBA
  • Abraham et al. 8 - Schéma de signature de seuil optimisé
  • Dumbo-MVBA 9 - Protocole de signature de seuil efficace
  • Duan et al. 10 - Protocole basé sur le hachage et sans hypothèses cryptographiques

Résultats Expérimentaux

Résultats Théoriques Principaux

Performance d'OciorMVBA :

  • Complexité de communication : O(n|w|log n + n²log q) bits
  • Complexité en messages : O(n²)
  • Complexité en tours : O(log n)
  • Pièce commune : O(log n)

Performance d'OciorMVBArr (n ≥ 5t + 1) :

  • Complexité de communication : O(n|w| + n²log n) bits
  • Complexité en tours : O(1)
  • Pièce commune : O(1)

Performance d'OciorMVBAh :

  • Complexité de communication : O(n|w| + n³) bits
  • Complexité en tours : O(1)
  • Pièce commune : O(1)

Analyse de Complexité

Via la relation de récurrence :

fTB(ñp) = β1ñp|w| + β2ñp²log q + fTB(⌊ñp/2⌋) + fTB(⌈ñp/2⌉)

La complexité de communication totale est prouvée être O(n|w|log n + n²log q).

Correction du Protocole

La correction du protocole est prouvée par une série de lemmes démontrant qu'il satisfait les trois propriétés fondamentales du MVBA :

  • Théorème 1 : Cohérence et terminaison
  • Théorème 2 : Validité externe
  • Théorème 3 : Complexité de communication et en tours

Travaux Connexes

Évolution des Protocoles MVBA

  1. Travaux antérieurs : Cachin et al. ont d'abord introduit le concept de MVBA
  2. Méthodes basées sur les signatures : Abraham et al., Dumbo-MVBA et autres ont optimisé les protocoles basés sur les signatures de seuil
  3. Méthodes sans signatures : Duan et al. ont proposé des protocoles sans signatures basés sur le hachage
  4. Sécurité au sens de la théorie de l'information : Cet article est le premier à réaliser une performance quasi-optimale sécurisée au sens de la théorie de l'information sous la tolérance aux pannes optimale

Fondements Techniques

  • Protocoles COOL/OciorCOOL : Fournissent les primitives UA et HMDM
  • Théorie des codes correcteurs d'erreur : Application des codes Reed-Solomon et Expander
  • Accord byzantin : Développement à partir des travaux classiques de Pease, Shostak et Lamport

Conclusion et Discussion

Conclusions Principales

  1. Sous la tolérance aux pannes optimale n ≥ 3t + 1, réalisation du premier protocole MVBA asynchrone sans erreur et sécurisé au sens de la théorie de l'information avec une performance quasi-optimale
  2. En relâchant la tolérance aux pannes ou en introduisant des hypothèses de hachage, une complexité en tours constante peut être réalisée
  3. La conception récursive et le mécanisme d'accord biaisé sont essentiels pour réaliser une performance efficace

Limitations

  1. Facteurs constants : Bien que la complexité asymptotique soit optimale, les facteurs constants peuvent être importants
  2. Dépendance à la pièce commune : Nécessite toujours O(log n) pièces communes
  3. Partitionnement du réseau : La division récursive peut introduire des surcharges supplémentaires dans les réseaux réels
  4. Choix du code correcteur : Les performances dépendent de la taille de l'alphabet q du code correcteur

Directions Futures

  1. Optimisation des constantes : Réduire les facteurs constants du protocole
  2. Efficacité de la pièce commune : Réduire davantage l'utilisation de la pièce commune
  3. Implémentation pratique : Développer une implémentation efficace et effectuer une évaluation des performances
  4. Extension d'application : Appliquer le protocole à des systèmes distribués concrets

Évaluation Approfondie

Avantages

  1. Percée théorique : Réalisation d'une complexité de communication quasi-optimale dans le cadre sécurisé au sens de la théorie de l'information
  2. Conception ingénieuse : La combinaison de l'architecture récursive et de l'accord biaisé est très innovante
  3. Analyse rigoureuse : Fourniture de preuves de correction complètes et d'analyses de complexité
  4. Valeur pratique : Fourniture de multiples variantes pour s'adapter à différents scénarios d'application

Insuffisances

  1. Absence de vérification expérimentale : L'article est principalement une analyse théorique, manquant d'implémentation pratique et de tests de performance
  2. Complexité constante : Bien que asymptotiquement optimale, les constantes réelles peuvent affecter l'applicabilité pratique
  3. Conditions d'hypothèse : L'hypothèse de pièce commune peut être difficile à réaliser dans les systèmes réels
  4. Lisibilité : La description du protocole est relativement complexe, rendant la compréhension et l'implémentation difficiles

Impact

  1. Contribution théorique : Fournit une nouvelle référence théorique pour le domaine du MVBA
  2. Inspiration technique : L'approche de conception récursive peut inspirer la conception d'autres protocoles distribués
  3. Potentiel pratique : Possède une valeur d'application dans les scénarios exigeant des garanties de sécurité extrêmes
  4. Direction de recherche : Fournit de nouvelles perspectives pour l'optimisation ultérieure des protocoles MVBA

Scénarios d'Application

  1. Exigences de sécurité élevées : Systèmes critiques nécessitant des garanties de sécurité au sens de la théorie de l'information
  2. Réseaux à grande échelle : Systèmes distribués avec un nombre important de nœuds
  3. Environnement asynchrone : Environnements où les délais réseau sont imprévisibles
  4. Systèmes tolérants aux pannes : Systèmes nécessitant de tolérer les défaillances byzantines

Références

L'article cite 17 références connexes, incluant principalement :

  • 1 Cachin et al. - Travail fondateur sur MVBA
  • 5-7 Chen - Série de protocoles COOL et OciorCOOL
  • 8-12 Progrès importants récents dans les protocoles MVBA
  • 13-15 Fondements de la théorie des codes correcteurs d'erreur
  • 17 Protocole d'accord byzantin asynchrone de Li-Chen