Brevet FR3127304A1 — publié le 20230324

La présente invention concerne une méthode de formation d’une chaine de blocs permettant d’assurer que toute transaction émise par un client soit incorporée dans la chaine de blocs. Cette méthode fait intervenir de nœuds validateurs du réseau, dont au plus nœuds défaillants avec et met en œuvre un mécanisme de consensus tolérant aux fautes byzantines (BFT). Chaque nœud validateur forme un bloc de transactions reçues des clients en les sélectionnant selon leur ordre d’arrivée et diffuse ce bloc aux autres nœuds validateurs. Le nœud validateur concatène le bloc qu’il a formé avec une pluralité de blocs reçus des autres nœuds pour former un bloc composite de blocs. Chaque nœud validateur détermine si les blocs composites qu’il reçoit des autres nœuds validateurs sont valides et s’il reçoit messages d’approbation pour le même bloc composite, valide ce dernier sous forme de bloc composite décidé en lui adjoignant un certificat de quorum. Un nœud validateur observant un bloc composite décidé l’incorpore dans la copie locale de la chaine de blocs. La phase de formation des blocs composites et celle de consensus sont pipelinées pour réduire le délai d’incorporation des transactions dans la chaine de blocs. Fig. 8 MÉTHODE DE FORMATION PIPELINÉE D’UNE CHAINE DE BLOCS GARANTISSANT LA VIVACITÉ DES TRANSACTIONS La présente invention concerne le domaine général des chaines de blocs et plus particulièrement celles fonctionnant sur un consensus tolérant aux fautes byzantines, encore dénommé BFT ( Byzantine Fault Tolerance ). Etat de la technique antérieure Le terme de chaine de blocs ( blockchain ) désigne à la fois un réseau pair à pair ( peer-to-peer ) sans autorité centrale, gérant un registre distribué ( distributed ledger ) et une structure de données constituée de blocs consécutifs chainés les uns aux autres, chaque bloc comprenant des transactions émises par des clients (nœuds du réseau). Nous considérerons ici le terme de chaine de blocs selon la seconde acception et utiliserons l’acronyme BC pour désigner la première. Certaines BCs (notamment Ethereum) permettent d’exécuter des applications décentralisées (DAPP) ou des contrats intelligents. Les clients souhaitant accéder à une telle application interagissent avec elle en lui transmettant des transactions. D’autres BCs (par exemple Bitcoin) n’autorisent que des transactions assez limitées, typiquement un transfert de montant en cryptomonnaie entre un UTXO ( Unspent Transaction Output ) émetteur et un UTXO récepteur. Quelle que soit le type de BC, les transactions sont concaténées dans des blocs, eux-mêmes stockés dans la chaine de blocs après qu’ils aient été validés par un mécanisme de consensus entre nœuds validateurs. Dans certaines BCs, n’importe quel nœud peut théoriquement être un nœud validateur ( public BCs ), dans d’autres cette fonction ne peut être exercée qu’après autorisation ( commissioned BCs ) ou bien à des nœuds dédiés ( private BCs ). Chacun des nœuds validateurs reçoit de manière asynchrone, généralement selon un mécanisme de propagation point à point dans le réseau, les transactions émises par les clients. Après avoir vérifié les transactions reçues, chaque nœud validateur les concatène et forme un bloc qu’il propose à ses pairs pour l’intégrer dans la chaine. Un grand nombre de mécanismes de validation sont connus de la technique (PoW, PoS, etc .) , le plus connu étant celui basé sur la preuve de travail ( PoW ) , utilisé par exemple dans les chaines de blocs Bitcoin et Ethereum. Toutefois, ce mécanisme de validation, basé sur la résolution d’un problème cryptographique, est particulièrement consommateur d’énergie et ne prémunit pas contre l’apparition de fourches ( forks ), c’est à dire de situations de divergence où des nœuds validateurs intègrent de manière concurrente des blocs à la chaine. Les mécanismes de validation les plus prometteurs sont actuellement ceux basés sur des mécanismes de consensus de type BFT ( Byzantine Fault Tolerant ). On pourra trouver une description détaillée de ce type de consensus dans l’article de M. Castro et B. Liskov intitulé « Practical Byzantine fault tolerance and proactive recovery » publié dans ACM Transactions on Computer Systems, Vol. 20, No. 4, Nov. 2002, pp. 398-460. Un mécanisme de consensus de type BFT assure que si, parmi les nœuds validateurs au plus un tiers ( ) sont défaillants (ou byzantins selon la terminologie convenue), les blocs de transactions issus du consensus sont bien valides et donc composés de transactions elles-mêmes valides. Un mécanisme de consensus de type BFT a été représenté schématiquement en Fig. 1, avec nœuds validateurs, chacun exécutant un processus de validation. Les processus de validation , fournissent des résultats de validation, par exemple des résultats de primitives cryptographiques sur le bloc à valider. On a supposé ici que le nœud 1 était byzantin et que par conséquent le processus pouvait fournir des valeurs erronées. En revanche, par hypothèse, deux nœuds validateurs intègres ne décident jamais de manière différente. Les nœuds validateurs déterminent le prochain bloc à ajouter à la chaine de blocs. Pour une même position dans la chaine de blocs, les nœuds validateurs prennent une décision sur le même bloc. Dans le cas illustré, les nœuds calculent respectivement les résultats de validation relatifs sur les blocs et décident de choisir le bloc sur la base d’un mécanisme de consensus. Le détail du mécanisme de consensus est illustré en , il comprend généralement une pluralité d’itérations successives, chaque itération comprenant une étape de proposition ( propose ), une étape de concertation (prevote) comportant des calculs ainsi que des échanges de messages et, enfin, une étape d’approbation (endorse). L’étape de proposition est effectuée par les différents nœuds à tour de rôle, en tourniquet (round-robin). Lors de l’étape d’approbation, chaque nœud validateur indique aux autres nœuds, au moyen d’un message d’approbation, s’il approuve les résultats de validation fournis par les autres nœuds. Lorsqu’au moins nœuds validateurs approuvent un même résultat de validation au cours d’une même itération, le bloc correspondant est considéré comme valide et un certificat de quorum ( quorum certificate ) est généré. Plus précisément, un bloc (où est le rang du bloc dans la chaine) comprend un pointeur vers le bloc précédent (par exemple le hash de ce bloc), le certificat de quorum du bloc précédent, et l’ensemble des transactions concaténées dans le bloc. Lors de chaque instance de consensus, les messages échangés entre les nœuds validateurs comprennent le rang du bloc dans la chaine, le numéro de l’itération, la référence de l’étape dans l’itération, le résultat de validation obtenu par le nœud validateur, le tout étant signé par le nœud validateur émettant le message. Les messages transmettant les résultats de validation sont dénommés messages de validation. Lorsqu’un nœud validateur approuve un résultat de validation pour un bloc, il transmet un message d’approbation ( endorse ) aux autres nœuds Enfin, le certificat de quorum, , relatif à un bloc comprend pour chaque nœud validateur ayant approuvé la valeur de consensus, le rang du bloc dans la chaine, ladite valeur de consensus et l’index de l’itération au cours de laquelle cette valeur a été approuvée. Le certificat de quorum contient les au moins messages d’approbation des nœuds validateurs qui ont approuvé la valeur de consensus. Pour un nœud validateur, la sortie du mécanisme de consensus est composée, d’une part, d’un bloc dont les résultats de validation ont été approuvés par au moins nœuds validateurs et, d’autre part, du certificat de quorum correspondant. Lorsque le bloc est associé à un certificat de quorum, il est désigné comme bloc « décidé » c’est-à-dire bloc validé par consensus. Ainsi dans le cas illustré et est le bloc décidé fourni par le troisième nœud validateur. La représente les étapes effectuées par un nœud validateur participant au mécanisme de consensus de type BFT. Chaque nœud validateur reçoit les transactions émises par les clients (propagation de proche en proche dans le réseau selon une diffusion de type Best Effort ) et dispose de sa propre copie de la chaine de blocs, stockée localement. Les transactions incorporées dans la chaine de blocs peuvent être ensuite exécutées par une couche applicative au-dessus de la chaine de blocs par exemple par une DAPP (application décentralisée). Chaque nœud validateur dispose en outre d’une mémoire dans laquelle les transactions qu’il reçoit sont stockées La gestion des transactions par le nœud validateur est effectuée au moyen d’une boucle itérative. Lorsque le nœud validateur observe en 310 qu’un nouveau bloc est validé par consensus, autrement dit qu’un nouveau bloc de rang avec son certificat de quorum, , est disponible, il ajoute ce nouveau bloc à sa copie locale de la chaine de blocs. Un nœud validateur n’ajoute un nouveau bloc à sa copie locale de la chaine de blocs que dans la mesure où le pointeur de ce nouveau bloc pointe vers le dernier bloc de la copie en question. Dès lors qu’un nouveau bloc est incorporé dans la chaine de blocs, plus précisément dans sa copie locale, le nœud validateur supprime de la file d’attente toutes les transactions présentes dans ce nouveau bloc, 320. Le nœud validateur prépare ensuite en 330 un bloc candidat en sélectionnant les premières transactions disponibles dans la file d’attente, c’est-à-dire en dépilant le buffer FIFO, et propose le bloc ainsi constitué à l’ensemble des autres nœuds validateurs après y avoir incorporé le certificat de quorum du bloc précédent, . En 340, le bloc candidat ainsi obtenu est soumis au mécanisme de consensus entre nœuds validateurs représenté en . Le processus de gestion des transactions par le nœud validateur se poursuit ensuite en retournant à l’étape 310. Si les mécanismes de consensus de type BFT permettent d’assurer que les blocs de transactions intégrés dans la chaine de blocs sont bien composés de transactions valides, ils ne garantissent toutefois pas qu’une transaction valide sera à terme incorporée dans la chaine de blocs. En effet, un nœud validateur malhonnête peut systématiquement censurer une transaction et ne pas l’intégrer dans les blocs qu’il propose, de manière à retarder indéfiniment son incorporation dans la chaine. La propriété selon laquelle une transaction transmise par un client sera bien incorporée à terme dans la chaine de blocs, c’est-à-dire dans un délai respectant une contrainte de latence (délai borné), est dénommée vivacité des transactions ( transaction liveness ). Si les transactions d’un client sont systématiquement censurées, autrement dit si ses transactions ne sont jamais incorporées dans la chaine de blocs, on dit que la chaine de blocs manque d’équité entre utilisateurs ( user fairness ). Une méthode de formation de chaine de blocs assurant la vivacité des transaction et l’équité entre utilisateurs a été décrite dans l’article de S. Bonomi et al. intitulé « SoK : Achieving state machine replication in blockchains based on repeated consensus », 28 mai 2021, disponible sur arXiv.org. Toutefois, cette méthode de formation de chaine de blocs comporte une latence importante dans la mesure où chaque itération nécessite une étape de proposition, de concertation puis d’approbation d’un ensemble de blocs. La présente invention a ainsi pour objet de proposer une méthode de formation d’une chaine de blocs garantissant la vivacité des transactions et l’équité entre utilisateurs tout en présentant une latence réduite et un débit élevé. Présentation de l’invention La présente invention est définie par une méthode de formation d’une chaine de blocs faisant intervenir une pluralité de nœuds validateurs dont au plus nœuds défaillants avec , chaque nœud validateur disposant d’une copie locale de la chaine de blocs et recevant les transactions émises par des clients, chaque nœud validateur stockant en outre ces transactions selon leur ordre d’arrivée dans une file d’attente et créant un bloc de transactions en dépilant la file d’attente à partir de la transaction la plus ancienne, ladite méthode étant originale en ce que chaque nœud validateur : - pendant une phase de consensus de type BFT, détermine si des blocs composites, formé d’un nombre de blocs avec , proposés par les autres nœuds validateurs lors de l’instance de validation en cours sont valides et, dans d’affirmative, renvoie à ces nœuds un message d’approbation étendu, ledit message d’approbation étendu comprenant le bloc composite validé pendant l’instance de validation en cours ainsi qu’un nouveau bloc de transactions destiné à former un nouveau bloc composite lors de l’instance de validation suivante ; - lorsqu’il dispose d’au moins messages d’approbation d’un même bloc composite, crée un bloc décidé comprenant ledit bloc composite et un certificat de quorum étendu, le certificat de quorum étendu étant composé desdits au moins messages d’approbation étendus relatifs à ce bloc composite ; - lorsqu’il dispose d’un bloc décidé, ajoute le bloc composite en question à la copie locale de la chaine de blocs ; - forme ledit nouveau bloc composite à partir des nouveaux blocs de transactions contenus dans les messages d’approbation étendus du certificat de quorum étendu. Avantageusement, chaque nœud validateur transmet les transactions reçues des clients aux autres nœuds validateurs selon un service de type Best Effort. Selon un exemple d’implémentation, le nombre de nœuds validateurs comprend exactement défaillants et . De préférence, après avoir formé le nouveau bloc composite, le nœud validateur lui adjoint le certificat de quorum du bloc composite précédent ainsi qu’un pointeur vers le bloc composite précédent. Lorsqu’un bloc composite est incorporé dans la chaine de blocs, le nœud validateur supprime avantageusement de sa file d’attente toutes les transactions présentes dans ce bloc composite. La phase de consensus comprend typiquement une pluralité d’itérations successives, chaque itération comprenant une étape de proposition dans laquelle chaque nœud validateur propose un bloc de transactions, une étape de concertation entre les nœuds validateurs, et une étape d’approbation dans laquelle chaque nœud validateur indique aux autres, le bloc composite qu’il a validé au moyen d’un message d’approbation étendu qu’il leur transmet. Avantageusement, un message d’approbation étendu émis par un nœud validateur comprend le bloc composite validé par ce nœud, l’indice de l’itération et l’étape de l’itération au cours de laquelle il l’a validé, le nouveau bloc de transactions destiné à former un nouveau bloc composite lors de l’instance de validation suivante, le ledit message d’approbation étant signé par une clé privée du nœud validateur. Brève description des figures D’autres caractéristiques et avantages de l’invention apparaîtront à la lecture d’un mode de réalisation préférentiel de l’invention, décrit en référence aux figures jointes parmi lesquelles : , déjà décrite, représente de manière schématique un mécanisme de consensus de type BFT utilisé pour valider un bloc dans une chaine de blocs ; , déjà décrite, représente différentes itérations intervenant dans l’exécution du mécanisme de consensus de la ; , déjà décrite, représente sous forme d’un ordinogramme, les étapes effectuées par un nœud validateur dans une méthode de formation d’une chaine de blocs utilisant un mécanisme connu de consensus de type BFT ; représente de manière schématique un mécanisme de consensus de type BFT utilisé dans une méthode de formation de chaine de blocs, selon un mode de réalisation utile à la compréhension de l’invention ; et représentent de manière schématique une phase de certification de blocs composites et une phase de consensus de type BFT portant sur ces blocs composites, mises en œuvre dans le mécanisme de consensus de la ; représente sous forme d’un ordinogramme, les étapes effectuées par un nœud validateur dans une méthode de formation d’une chaine de blocs utilisant un mécanisme de consensus de la ; représente schématiquement un mécanisme de consensus de type BFT utilisé dans une méthode de formation de chaine de blocs selon un mode de réalisation de la présente invention ; représente sous forme d’un ordinogramme, les étapes effectuées par un nœud validateur dans une méthode de formation d’une chaine de blocs utilisant un mécanisme de consensus de type BFT, selon le mode de réalisation de la . Méthode de formation d’une chaine de blocs faisant intervenir une pluralité de nœuds validateurs dont au plus nœuds défaillants avec , chaque nœud validateur disposant d’une copie locale de la chaine de blocs et recevant les transactions émises par des clients, chaque nœud validateur stockant en outre ces transactions selon leur ordre d’arrivée dans une file d’attente et créant un bloc de transactions en dépilant la file d’attente à partir de la transaction la plus ancienne, caractérisée en ce que chaque nœud validateur : - pendant une phase de consensus de type BFT, détermine si des blocs composites, formé d’un nombre de blocs avec , proposés par les autres nœuds validateurs lors de l’instance de validation en cours sont valides et, dans d’affirmative, renvoie à ces nœuds un message d’approbation étendu, ledit message d’approbation étendu comprenant le bloc composite validé pendant l’instance de validation en cours ainsi qu’un nouveau bloc de transactions destiné à former un nouveau bloc composite lors de l’instance de validation suivante ; - lorsqu’il dispose d’au moins messages d’approbation d’un même bloc composite, crée un bloc décidé comprenant ledit bloc composite et un certificat de quorum étendu, le certificat de quorum étendu étant composé desdits au moins messages d’approbation étendus relatifs à ce bloc composite ; - lorsqu’il dispose d’un bloc décidé, ajoute le bloc composite en question à la copie locale de la chaine de blocs ; - forme ledit nouveau bloc composite à partir des nouveaux blocs de transactions contenus dans les messages d’approbation étendus du certificat de quorum étendu. Méthode de formation d’une chaine de blocs selon la revendication 1, caractérisée en ce que chaque nœud validateur transmet les transactions reçues des clients aux autres nœuds validateurs selon un service de type Best Effort. Méthode de formation d’une chaine de blocs selon la revendication 1 ou 2, caractérisée en ce que nombre de nœuds validateurs comprend exactement défaillants et que . Méthode de formation d’une chaine de blocs selon l’une des revendications précédentes, caractérisée en ce qu’après avoir formé le nouveau bloc composite, le nœud validateur lui adjoint le certificat de quorum du bloc composite précédent ainsi qu’un pointeur vers le bloc composite précédent. Méthode de formation d’une chaine de blocs selon l’une des revendications précédentes, caractérisée en ce que lorsqu’un bloc composite est incorporé dans la chaine de blocs, le nœud validateur supprime de sa file d’attente toutes les transactions présentes dans ce bloc composite. Méthode de formation d’une chaine de blocs selon l’une des revendications précédentes, caractérisée en ce que la phase de consensus comprend une pluralité d’itérations successives, chaque itération comprenant une étape de proposition dans laquelle chaque nœud validateur propose un bloc de transactions, une étape de concertation entre les nœuds validateurs, et une étape d’approbation dans laquelle chaque nœud validateur indique aux autres, le bloc composite qu’il a validé au moyen d’un message d’approbation étendu qu’il leur transmet. Méthode de formation d’une chaine de blocs selon la revendication 5, caractérisée en ce qu’un message d’approbation étendu émis par un nœud validateur comprend le bloc composite validé par ce nœud, l’indice de l’itération et l’étape de l’itération au cours de laquelle il l’a validé, le nouveau bloc de transactions destiné à former un nouveau bloc composite lors de l’instance de validation suivante, le ledit message d’approbation étant signé par une clé privée du nœud validateur.