Blockchain Sharding

Bonjour à tous, je suis l'un des développeurs de Near Protocol, qui, entre autres, implémente le partage, et dans cet article, je veux dire en détail ce qu'est le partage dans la blockchain, comment cela fonctionne, et aborder un certain nombre de problèmes qui surviennent lorsque vous essayez de le construire.

Il est bien connu qu'Ethereum, la plate-forme dApps la plus populaire, traite moins de 20 transactions par seconde. En raison de cette restriction, le prix des transactions et le temps pour les confirmer sont très élevés: malgré le fait qu'un bloc soit publié dans Ethereum une fois toutes les 10 à 12 secondes, selon ETH Gas Station, le temps entre l'envoi d'une transaction et la façon dont elle tombe réellement dans le bloc est en moyenne de 1,2 minutes. La faible bande passante, les prix élevés et la longue confirmation de transaction ne permettent pas de lancer des services haute performance sur Ethereum.

La principale raison pour laquelle Ethereum ne peut pas traiter plus de 20 transactions par seconde est que chaque nœud dans Ethereum doit vérifier chaque transaction. Au cours des cinq années qui ont suivi la sortie d'Ethereum, de nombreuses idées ont été proposées pour résoudre ce problème. Ces solutions peuvent être grossièrement divisées en deux groupes: celles qui proposent de déléguer des transactions à un petit groupe de nœuds avec un très bon matériel, et celles qui proposent à chaque nœud de ne traiter qu'un sous-ensemble de toutes les transactions. Un exemple de la première approche est Thunder , dans lequel les blocs sont créés par un seul nœud, ce qui permet, selon les développeurs, de recevoir 1200 transactions par seconde, soit 100 fois plus qu'Ethereum. D'autres exemples de la première catégorie sont Algorand , SpaceMesh , Solana . Tous ces protocoles améliorent divers aspects du protocole et vous permettent d'effectuer plus de transactions que dans Ethereum, mais tous sont limités par la vitesse d'une machine (bien que très puissante).

La deuxième approche, dans laquelle chaque nœud ne traite qu'un sous-ensemble de transactions, est appelée Sharding. C'est ainsi que la Fondation Ethereum prévoit d'augmenter la bande passante Ethereum.

Dans cet article, je vais vous expliquer comment fonctionne Sharding dans Blockchain en utilisant l'exemple de plusieurs protocoles en cours de développement.

Le partage le plus simple

Dans la mise en œuvre la plus simple, au lieu de prendre en charge une chaîne de blocs, nous en prendrons en charge plusieurs, et nous appellerons chacune de ces chaînes de blocs un «fragment». Chaque fragment est pris en charge par un ensemble indépendant de nœuds qui vérifient les transactions et créent des blocs. Ci-après, j'appellerai de tels validateurs de nœuds.

Chaque fragment est responsable d'un sous-ensemble de contrats et de comptes. Supposons pour l'instant que les transactions ne fonctionnent toujours qu'avec des contrats et des comptes au sein du même fragment. Une telle conception simplifiée est suffisante pour montrer certains problèmes et caractéristiques intéressants du partage.

Nomination des validateurs et Blockchain centrale

Le premier problème avec le fait que chaque fragment a ses propres validateurs est que si nous avons 10 shadras, chaque fragment est maintenant 10 fois moins fiable qu'une chaîne de blocs. Donc, si une blockchain avec X validateurs décide de faire un hard fork dans un système de fragments avec 10 fragments, et casse les X validateurs entre 10 fragments, maintenant il n'y a plus que X / 10 validateurs dans chaque fragment, et gagner le contrôle sur le fragment nécessite de contrôler 5,1% (51 % / 10) validateurs.

Ce qui conduit à la première question intéressante: qui attribue les validateurs aux fragments? Le contrôle de 5,1% des validateurs n'est un problème que si tous les 5,1% des validateurs sont dans le même fragment. Si les validateurs eux-mêmes ne peuvent pas choisir le fragment auquel ils sont affectés, le contrôle de 5,1% des validateurs avant leur affectation ne leur permettra pas de contrôler les fragments.

Presque toutes les conceptions de partage proposées proposent une source de nombres aléatoires pour attribuer des validateurs aux fragments. L'obtention de nombres aléatoires dans un système distribué dans lequel les participants ne se font pas confiance n'est pas un problème complètement résolu aujourd'hui, que nous n'aborderons pas dans cet article, et supposons simplement que nous avons une telle source de nombres aléatoires.

La réception de nombres aléatoires et la nomination de validateurs sont des calculs à l'échelle du système qui ne sont spécifiques à aucun fragment particulier. Pour de tels calculs, les conceptions modernes de blockchain de fragments ont une blockchain supplémentaire dédiée qui existe uniquement pour effectuer des calculs à l'échelle du système. En plus des nombres aléatoires et de la nomination de validateurs, ces calculs peuvent inclure l'obtention de hachages des derniers blocs à partir d'éclats et leur stockage; le traitement des garanties dans les systèmes de preuve de participation et l'étude des preuves d'un comportement inapproprié avec la sélection associée de telles garanties; rééquilibrer les fragments, si une telle fonction est fournie. Une telle blockchain est appelée la chaîne Beacon dans Ethereum 2.0 et Near Protocol, la chaîne Relay dans PolkaDot et le Cosmos Hub dans Cosmos.

Dans ce post, nous appellerons une telle blockchain la «blockchain centrale». L'existence d'une blockchain centrale nous amène au prochain sujet intéressant - le partage quadratique.

Partage quadratique

Le sharding est souvent présenté comme une solution qui évolue à l'infini avec le nombre croissant de nœuds. Probablement, vous pouvez vraiment créer un système avec cette propriété, mais les systèmes avec une blockchain centrale ont une limite supérieure sur le nombre de fragments, et par conséquent n'ont pas une évolutivité infinie. Il est facile de comprendre pourquoi: la blockchain centrale effectue certains calculs, tels que l'attribution de validateurs et la préservation des derniers états de fragments, dont la complexité est proportionnelle au nombre de fragments. Étant donné que la blockchain centrale elle-même n'est pas fragmentée et que son débit est limité par le débit de chaque nœud, le nombre de fragments qu'elle peut prendre en charge est limité.

Voyons comment le débit de l'ensemble du système change si la puissance des nœuds qui le supportent augmente k fois. Chaque fragment pourra traiter k fois plus de transactions, et la blockchain centrale pourra supporter k fois plus de fragments. Ainsi, le débit de l'ensemble du système augmentera k ^ 2 fois. D'où le nom de «sharding quadratique».

Il est difficile de prédire combien de fragments peuvent prendre en charge la blockchain centrale aujourd'hui, mais très probablement dans un proche avenir, nous ne nous rapprocherons pas de la limite de transaction pour une blockchain fragmentée avec un partage quadratique. Très probablement, nous allons bientôt nous heurter à la limite du nombre de nœuds nécessaires pour prendre en charge un tel nombre de fragments.

Partage d'état

Le statut est toutes les informations sur tous les comptes et contrats. Jusqu'à présent, nous avons parlé du sharding en général, sans préciser ce qu'est exactement le sharding. Les nœuds de la blockchain effectuent les trois tâches suivantes: 1) effectuer des transactions 2) transmettre des transactions et des blocs à d'autres nœuds et 3) stocker l'état et l'historique de la blockchain. Chacune de ces trois tâches est associée à une charge sans cesse croissante sur les nœuds:

1. La nécessité d'effectuer des transactions nécessite plus de puissance de calcul avec une augmentation du nombre de transactions;
2. La nécessité de transférer les transactions nécessite plus de bande passante réseau à mesure que les transactions augmentent;
3. La nécessité de maintenir l'état et l'historique nécessite plus d'espace disque à mesure que la taille de l'état et / ou de l'historique augmente. Il est important de noter que, contrairement aux deux premiers points, la quantité d'espace disque requis augmente même si le nombre de transactions par unité de temps ne change pas.

D'après la liste ci-dessus, il peut sembler que l'espace disque est le plus gros problème, car seul l'espace disque augmente même si le nombre de transactions n'augmente pas, mais en pratique ce n'est pas le cas. Aujourd'hui, l'état d'Ethereum occupe environ 100 Go, ce qui peut facilement être enregistré sur n'importe quelle machine moderne, mais le nombre de transactions qu'Ethereum peut traiter est limité à plusieurs dizaines par seconde, reposant sur la puissance de calcul et le réseau.

Zilliqa est le projet le plus célèbre qui répartit l'informatique et le réseau mais pas l'État. Le calcul du partage est plus simple que le partage, car tous les nœuds ont tous un état et peuvent toujours exécuter facilement des contrats qui provoquent d'autres contrats ou affectent les comptes sur différents fragments. Sous ces aspects, le design de Zilliqa est trop simplifié, la critique du design en anglais peut être lue ici .

Bien que le partage d'état sans calculs d'ombrage ait été proposé, je ne connais aucun projet qui le fasse vraiment, nous supposerons donc que le partage d'état implique des calculs de partage.

En pratique, le fait que l'état soit fragmenté isole en quelque sorte les fragments, ce qui leur permet d'être des chaînes de blocs indépendantes, comme nous l'avons défini ci-dessus. Les validateurs dans les fragments stockent uniquement un état spécifique à leur fragment, et seules les transactions qui affectent cet état sont exécutées et transmises. Cela réduit la charge sur le processeur, le disque et le réseau de manière linéaire avec le nombre de fragments, mais pose de nouveaux problèmes, tels que les transactions entre les fragments.

Transactions inter-fragments

Jusqu'à présent, nous avons vu les fragments comme des chaînes de blocs indépendantes en termes de la façon dont ils exécutent les transactions. Avec cette conception, par exemple, il est impossible de réaliser une transaction qui transfère de l'argent entre deux comptes sur deux fragments différents, ou de provoquer le contact sur un fragment d'un contrat à l'autre. Je voudrais soutenir les deux scénarios.

Par souci de simplicité, nous ne considérerons que les transactions qui transfèrent de l'argent, et nous supposerons que chaque participant possède un compte sur exactement un fragment. Si un participant sur un fragment souhaite transférer de l'argent à un participant sur le même fragment, les validateurs de ce fragment peuvent traiter cette transaction et l'appliquer à l'État. Mais si, par exemple, Alice a un compte sur le fragment # 1 et qu'elle veut envoyer de l'argent à Bob avec un compte sur le fragment # 2, ni les validateurs de partition # 1 (qui ne peut pas ajouter d'argent à Bob) ni les validateurs de partition # 2 (qui ne peuvent pas obtenir l'argent d'Alice ) ne peut pas terminer la transaction et mettre à jour l'état.

Il existe deux grands groupes d'approches pour résoudre ce problème:

1. Synchrone : pour toute transaction impliquant plusieurs fragments, les blocs des fragments contenant des mises à jour d'état pour cette transaction sont produits simultanément et les valideurs de ces fragments travaillent ensemble pour créer de tels blocs. La conception la plus élaborée de cette approche, à ma connaissance, est Merge Blocks, décrite (en anglais) ici .

   
   

2. Asynchrone : une transaction inter-fragments est exécutée en fragments qu'elle affecte, de manière asynchrone: la partie de la transaction qui ajoute de l'argent à Bob est exécutée dans le fragment # 2 lorsque les validateurs du fragment ont des preuves que la partie de la transaction qui soustrait l'argent d'Alice a été exécutée dans tesson # 1. Cette approche est plus populaire dans les systèmes développés aujourd'hui car elle ne nécessite pas de synchronisation supplémentaire entre les fragments pour la production de blocs. De tels systèmes sont proposés aujourd'hui dans Cosmos, Ethereum Serenity, Near Protocol, Kadena et autres. Le problème avec cette approche est que si les blocs sont produits indépendamment, il est probable que l'un des blocs contenant la mise à jour d'état de la transaction ne soit pas dans la chaîne canonique dans son fragment, et donc la transaction ne sera que partiellement terminée. Par exemple, considérez la figure ci-dessous. Il montre deux fragments dans lesquels les fourches se sont produites et une transaction inter-fragments, dont la mise à jour d'état est reflétée dans les blocs A et X ', respectivement. Si les chaînes AB et V'-X'-Y'-Z 's'avèrent être canoniques dans leurs fragments, alors la transaction est entièrement finalisée. Si les chaînes A'-B'-C'-D 'et VX sont canoniques, alors la transaction est complètement annulée, ce qui est acceptable. Mais si, par exemple, AB et VX deviennent canoniques, une partie de la transaction est finalisée, l'autre est annulée et la transaction est partiellement terminée.

   
   

Le scénario décrit ci-dessus est l'un des gros problèmes de partage, dans lequel toutes les solutions proposées ne sont pas optimales. Nous y reviendrons un peu plus loin.

Mauvais comportement

Maintenant que nous avons compris comment fonctionnent les chaînes de blocs de fragments et étudié les concepts de la blockchain centrale, la nomination de validateurs et les transactions entre fragments, à la fin de cet article, nous allons examiner un autre sujet intéressant: que peut faire un participant essayant d'attaquer le système s'il parvient à obtenir contrôle sur un nombre suffisamment important de validateurs dans un seul fragment.

Fourches ciblées

Si le participant a un contrôle suffisant sur le fragment, il peut délibérément créer des fourches. Pour créer des fourches, peu importe le consensus utilisé dans les fragments, en particulier, peu importe qu'il s'agisse de BFT ou non, si un nombre suffisant de validateurs sont contrôlés par l'attaquant, il peut créer un fork. Par exemple, l'objectif du fork pourrait être d'annuler une transaction qui a payé quelque chose en dehors de la blockchain.

On prétend que gagner le contrôle de 50% du fragment est plus facile que 50% de l'ensemble du réseau (par exemple, parce qu'un participant peut essayer de pirater ou de corrompre les validateurs après qu'ils ont été affectés au fragment). Par définition, les transactions entre fragments changent d'état dans plusieurs fragments. De tels changements tomberont dans certains blocs dans les chaînes de blocs des fragments correspondants. Il est nécessaire que tous ces blocs soient finalisés (c'est-à-dire qu'ils appartiennent à la chaîne canonique dans leurs fragments respectifs) ou qu'ils ne soient pas tous finalisés (c'est-à-dire qu'ils n'appartiennent pas à la chaîne canonique dans leurs fragments). Étant donné que nous supposons que certains participants avec de mauvaises intentions peuvent, en principe, prendre le contrôle du fragment, nous ne pouvons pas supposer que les fourches ne se produiront pas même si le consensus byzantin a été atteint, ou qu'un grand nombre de blocs ont été construits au-dessus du bloc avec la transaction.

Ce problème a de nombreuses solutions, dont la plus simple consiste parfois à enregistrer le hachage du dernier bloc du fragment dans la blockchain centrale. L'algorithme de sélection de chaîne canonique dans les fragments est ensuite modifié de sorte qu'aucune cible contenant le dernier bloc stocké sur la chaîne de blocs centrale canonique. Ensuite, afin d'éviter complètement les situations où la transaction a été partiellement terminée en raison du fait que certains des blocs contenant sa mise à jour d'état se sont révélés être en dehors des chaînes canoniques, vous pouvez modifier l'algorithme pour exécuter les transactions entre les fragments de sorte que le fragment A n'accepte pas la preuve de la transaction dans le fragment B jusqu'au bloc. contenant la mise à jour de l'état de la transaction dans le fragment B n'a pas été enregistré dans la blockchain centrale.

Création de blocs invalides

Si le participant a pu prendre le contrôle d'un nombre suffisamment important de validateurs dans le fragment, il peut essayer de créer un bloc complètement invalide. Par exemple, supposons qu'avant le bloc, l'état était tel qu'Alice avait 10 jetons, et dans Bob - 0, le bloc ne contient qu'une seule transaction, qui envoie 10 jetons du compte d'Alice au compte de Bob, mais dans le nouvel état, il reflète 0 jetons d'Alice et 1000 avec Bob.

Dans une blockchain classique sans partition, la création d'un tel bloc est impossible, car tous les participants, comme ceux qui créent des blocs et ceux qui utilisent simplement la blockchain, vérifient tous les blocs et éliminent immédiatement tout bloc contenant de telles erreurs. Même si les validateurs contrôlés par l'attaquant peuvent construire la chaîne plus rapidement, cela ne leur permettra pas de passer la chaîne plus longue contenant le bloc invalide comme canonique, car tous les participants au réseau rejetteront immédiatement le bloc invalide et tout bloc qui a été construit par-dessus. Les validateurs honnêtes continueront de s'appuyer sur le dernier bloc valide, et tous les participants au réseau verront leur chaîne comme canonique.

La figure ci-dessus montre cinq validateurs, dont trois sont sous le contrôle de l'attaquant. Ils ont créé le bloc invalide A ', puis ont continué à construire la chaîne sur le dessus. Deux validateurs privés ont immédiatement rejeté le bloc A 'comme non valide et ont continué à construire au-dessus du dernier bloc valide qu'ils connaissaient, créant ainsi une fourchette. Puisqu'il y a moins de validateurs dans une chaîne honnête que dans une chaîne malhonnête, leur chaîne est plus courte. Cependant, dans la blockchain classique non fragmentée, tous les participants au système valident tous les blocs qu'ils voient. Ainsi, tout participant utilisant la blockchain verra que A 'est invalide, la rejetera, et donc supprimera B', C 'et D' comme construit au-dessus du bloc invalide, et donc tous les participants verront AB comme une chaîne canonique.

Dans une conception de fragment, aucun participant ne peut valider tous les blocs dans toutes les chaînes de blocs. - , , , - .

, , . , , ( ).

, :

1. - . , 2/3 . , , , . , , , - , . , .
2. - , , , , , . , zk-SNARKs ( zk, zero-knowledge, , non-zk SNARKs). , zk-SNARKs , .

, , , , . — .

J'écris beaucoup sur la blockchain et le sharding en anglais. Nous interrogeons également périodiquement les auteurs d'autres protocoles tels que Cosmos et Solana, approfondissant les détails techniques. Si vous êtes intéressé par le sujet, vous pouvez suivre les nouveaux messages et vidéos en vous abonnant à mon Twitter @AlexSkidanov .