2 août 2019
Le consensus entre un ensemble de n processus est un problème fondamental de l’algorithmique distribuée, il est intimement lié aux machines à états répliquées (SMR) qui permettent de partager de manière décentralisée et résiliente une vision du monde cohérente. Néanmoins, sous certaines conditions (communication non-synchrone, grande coalition de t > n/3 agents malveillants) l’accord censé être garanti entre 2 partis peut être rompu. Dans le cadre d’une application blockchain de consortium, il s’agit d’une brèche pour réaliser une double-dépense. On se demande donc quelle propriété peut-on garantir dans le cas dégradé où les hypothèses pour garantir l’accord ne sont pas vérifiées. Polygraph répond à cette question en garantissant l’accountability : si désaccord il y a, alors n/3 coupables au moins seront détectés ultimement. Cette propriété pourrait être potentiellement utilisée dans un cadre de théorie des jeux pour obtenir un résultat encore plus fort.
Supposons que Alice, Bob et Charlie veuillent établir un consensus binaire (décider 0 ou 1) de manière résiliente à une panne (t=1) et sans hypothèse sur le temps d’arrivée des messages (asynchronie). Alice initie le protocole avec 0, Bob avec 1 et Charlie est malveillant. La connexion est rompue entre Alice et Bob pendant un temps indéterminé. Charlie communique parallèlement avec les 2 parties corrects. Alice ne sait pas si elle doit faire confiance à Bob ou Charlie, mais puisqu’elle veut décider même en cas d’une panne et que Bob semble ne pas donner de nouvelle, elle conjecture que Bob est en panne et décide 0 conformément aux messages de Charlie. Bob fait le même raisonnement et décide 1. Finalement Charlie a su tirer parti de de l’asynchronie pour créer un désaccord entre 2 corrects.
Supposons que Charlie ait dû signer cryptographiquement ses messages pour convaincre les corrects de décider. Une fois la connexion rétablie, Alice et Bob vont pouvoir rassembler ces messages mutants pour établir a posteriori une preuve indéniable de culpabilité. L’attaque de Charlie est observable. Néanmoins, lorsque le nombre de participants n augmente, il est possible de créer une attaque non-observable. Polygraph demande donc de rajouter des justifications pour rendre ces attaques observables. Si une solution naïve est possible, elle nécessite des justifications de trop grande tailles qui ralentissent le protocole. Le défi est donc de borner au maximum ce surcoût. Polygraph multiplie par n la taille des messages échangés, contre n² pour une solution naïve. Une question subsiste, peut-on faire mieux ?
Dans un cadre de théorie des jeux, les processus malveillants sont des agents rationnels qui souhaite maximiser leurs gains. On souhaite alors les inciter à suivre le protocole par des arguments financiers. On peut par exemple demander aux membres du consortium de bloquer une caution sur un dépôt le temps du consensus et débiter cette caution en cas de fraude avérée. On peut ensuite récompenser un agent qui diffuse la preuve de culpabilité avec l’argent des cautions pour construire un dilemme du prisonnier qui incitera tout membre d’une coalition malveillante à trahir ses acolytes plutôt qu’à continuer la tentative d’attaque. Aussi, si la coalition a des doutes sur le temps de rétablissement du réseau (synchronie probabiliste), l’espérance de gain peut être à son désavantage. Une multitude de jeux plus sophistiqués peuvent être imaginés pour que suivre le protocole soit plus intéressant que participer à une tentative d’attaque et ainsi renforcer la sécurité de la blockchain de consortium.
Envie de rentrer dans les détails du sujet ? Son papier de recherche est disponible ici >> https://eprint.iacr.org/2019/587.pdf
Ajouter un commentaire