Bonjour, chers utilisateurs Habr! Cet article concerne le Web 3.0 - l'Internet décentralisé. Le Web 3.0 introduit le concept de décentralisation comme fondement de l'Internet moderne. De nombreux systèmes et réseaux informatiques nécessitent des fonctionnalités de sécurité et de décentralisation pour répondre à leurs besoins. Un registre distribué utilisant la technologie blockchain fournit des solutions efficaces pour la décentralisation.
Blockchain est un registre distribué. Vous pouvez le considérer comme une énorme base de données qui dure éternellement, sans jamais changer au fil du temps. La blockchain fournit la base d'applications et de services Web décentralisés.
Cependant, la blockchain est plus qu'une simple base de données. Il sert à accroître la sécurité et la confiance entre les membres du réseau, améliorant les transactions commerciales en ligne.
Le consensus byzantin augmente la fiabilité du réseau et résout le problème de cohérence.
L'évolutivité fournie par DLT modifie les réseaux d'entreprise existants.
La blockchain offre de nouveaux avantages très importants:
- Empêche les erreurs coûteuses.
- Assure des transactions transparentes.
- Numérise les biens réels.
- Applique les contrats intelligents.
- Augmente la vitesse et la sécurité des paiements.
Nous avons développé un PoE spécial pour rechercher des protocoles cryptographiques et améliorer les solutions DLT et blockchain existantes.
La plupart des systèmes de registres publics n'ont pas la propriété de l'évolutivité, ce qui rend leur débit plutôt faible. Par exemple, Ethereum ne traite que ~ 20 tx / s.
De nombreuses solutions ont été développées pour augmenter l'évolutivité tout en maintenant la décentralisation. Cependant, seuls 2 avantages sur 3 - évolutivité, sécurité et décentralisation - peuvent être obtenus simultanément.
L'utilisation de sidechains fournit l'une des solutions les plus efficaces.
Le concept plasma
Le concept Plasma se résume à l'idée qu'une chaîne racine traite un petit nombre de validations à partir de chaînes enfants, agissant ainsi comme la couche la plus sûre et finale pour stocker tous les états intermédiaires. Chaque chaîne enfant fonctionne comme sa propre blockchain avec son propre algorithme de consensus, mais il y a quelques mises en garde importantes.
- Les contrats intelligents sont créés dans une chaîne racine et agissent comme des points de contrôle pour les chaînes enfants au sein de la chaîne racine.
- Une chaîne enfant est créée et fonctionne comme sa propre blockchain avec son propre consensus. Tous les États de la chaîne enfant sont protégés par des preuves de fraude qui garantissent que toutes les transitions entre États sont valides et appliquent un protocole de retrait.
- Les contrats intelligents spécifiques à DApp ou à la logique d'application de la chaîne enfant peuvent être déployés dans la chaîne enfant.
- Les fonds peuvent être transférés de la chaîne racine à la chaîne enfant.
Les validateurs reçoivent des incitations économiques pour agir honnêtement et envoyer des engagements à la chaîne racine - la couche finale de règlement des transactions.
Par conséquent, les utilisateurs DApp travaillant dans la chaîne enfant n'ont pas du tout à interagir avec la chaîne racine. De plus, ils peuvent placer leur argent dans la chaîne racine quand ils le souhaitent, même si la chaîne enfant est piratée. Ces sorties de la chaîne enfant permettent aux utilisateurs de stocker en toute sécurité leurs fonds avec des preuves Merkle, confirmant la propriété d'un certain montant de fonds.
Les principaux avantages du plasma sont liés à sa capacité à faciliter considérablement les calculs qui surchargent la chaîne principale. De plus, la blockchain Ethereum peut gérer des ensembles de données plus étendus et parallèles. Le temps retiré de la chaîne racine est également transféré aux nœuds Ethereum, qui ont des exigences de traitement et de stockage plus faibles.
Plasma Cash attribue des numéros de série uniques aux jetons en ligne. Les avantages de ce système incluent pas besoin de confirmations, une prise en charge plus simple pour tous les types de jetons (y compris les jetons non fongibles) et l'atténuation contre les sorties massives d'une chaîne enfant.
Le concept de «sorties massives» d'une chaîne enfant est un problème rencontré par Plasma. Dans ce scénario, des retraits simultanés coordonnés d'une chaîne enfant pourraient potentiellement conduire à une puissance de calcul insuffisante pour retirer tous les fonds. En conséquence, les utilisateurs peuvent perdre des fonds.
Options pour implémenter Plasma
Basic Plasma a beaucoup d'options d'implémentation.
Les principales différences concernent:
- l'archivage des informations sur les méthodes de stockage et de présentation de l'état;
- types de jetons (divisibles, indivisibles);
- sécurité des transactions;
- type d'algorithme de consensus.
Les principales variations du plasma comprennent:
- Plasma basé sur UTXO - chaque transaction se compose d'entrées et de sorties. Une transaction peut être effectuée et dépensée. La liste des transactions non dépensées est l'état d'une chaîne enfant elle-même.
- Plasma basé sur les comptes - cette structure contient la réflexion et le solde de chaque compte. Il est utilisé dans Ethereum, car chaque compte peut être de deux types: un compte d'utilisateur et un compte de contrat intelligent. La simplicité est un avantage important du Plasma basé sur les comptes. Dans le même temps, le manque d'évolutivité est un inconvénient. Une propriété spéciale, "nonce", est utilisée pour empêcher l'exécution d'une transaction deux fois.
Afin de comprendre les structures de données utilisées dans la blockchain Plasma Cash et le fonctionnement des engagements, il est nécessaire de clarifier le concept de Merkle Tree.
Les arbres Merkle et leur utilisation dans le plasma
Merkle Tree est une structure de données extrêmement importante dans le monde de la blockchain. Il nous permet de capturer un certain ensemble de données et de masquer les données, tout en prouvant que certaines informations étaient dans l'ensemble. Par exemple, si nous avons dix nombres, nous pourrions créer une preuve pour ces nombres, puis prouver qu'un certain nombre était dans cet ensemble. Cette preuve aurait une petite taille constante, ce qui la rend peu coûteuse à publier dans Ethereum.
Vous pouvez utiliser ce principe pour un ensemble de transactions et prouver qu'une transaction particulière se trouve dans cet ensemble. C'est précisément ce que fait un opérateur. Chaque bloc se compose d'un ensemble de transactions qui se transforme en arbre Merkle. La racine de cet arbre est une preuve publiée dans Ethereum avec chaque bloc de plasma.
Les utilisateurs devraient pouvoir retirer leurs fonds de la chaîne Plasma. Pour cela, ils envoient une transaction de «sortie» à Ethereum.
Plasma Cash utilise un arbre Merkle spécial qui élimine la nécessité de valider un bloc entier. Il suffit de valider uniquement les branches qui correspondent au jeton de l'utilisateur.
Pour transférer un jeton, il est nécessaire d'analyser son historique et d'analyser uniquement les jetons dont un certain utilisateur a besoin. Lors du transfert d'un jeton, l'utilisateur envoie simplement tout l'historique à un autre utilisateur, qui peut ensuite authentifier tout l'historique et, surtout, le faire très rapidement.
Structures de données Plasma Cash pour le stockage de l'état et de l'historique
Il est conseillé d'utiliser uniquement des arbres Merkle sélectionnés, car il est nécessaire d'obtenir des preuves d'inclusion et de non-inclusion pour une transaction dans un bloc. Par exemple:
- Arbre de merkle clairsemé
- Arbre de Patricia
Nous avons développé nos propres implémentations Sparse Merkle Tree et Patricia Tree pour notre client.
Un arbre Merkle clairsemé est similaire à un arbre Merkle standard, sauf que ses données sont indexées et que chaque point de données est placé sur une feuille qui correspond à l'index de ce point de données.
Supposons que nous ayons un arbre Merkle à quatre feuilles. Remplissons cet arbre avec les lettres A et D, pour démonstration. La lettre A est la première lettre de l'alphabet, nous allons donc la placer sur la première feuille. De même, nous placerons D sur la quatrième feuille.
Que se passe-t-il donc sur les deuxième et troisième feuilles? Ils doivent être laissés vides. Plus précisément, une valeur spéciale (par exemple, zéro) est utilisée à la place d'une lettre.
L'arbre ressemble finalement à ceci:
La preuve d'inclusion fonctionne de la même manière que dans un arbre Merkle normal. Que se passe-t-il si nous voulons prouver que C ne fait pas partie de cet arbre de Merkle? Élémentaire! Nous savons que si C fait partie d'un arbre, ce serait sur la troisième feuille. Si C ne fait pas partie de l'arbre, alors la troisième feuille doit être nulle.
Tout ce qui est nécessaire est une preuve d'inclusion de Merkle standard montrant que la troisième feuille est nulle.
La meilleure caractéristique d'un arbre Merkle clairsemé est qu'il fournit des référentiels pour les valeurs-clés à l'intérieur de l'arbre Merkle!
Une partie du code du protocole PoE construit un arbre de Merkle clairsemé:
class SparseTree { //... buildTree() { if (Object.keys(this.leaves).length > 0) { this.levels = [] this.levels.unshift(this.leaves) for (let level = 0; level < this.depth; level++) { let currentLevel = this.levels[0] let nextLevel = {} Object.keys(currentLevel).forEach((leafKey) => { let leafHash = currentLevel[leafKey] let isEvenLeaf = this.isEvenLeaf(leafKey) let parentLeafKey = leafKey.slice(0, -1) let neighborLeafKey = parentLeafKey + (isEvenLeaf ? '1' : '0') let neighborLeafHash = currentLevel[neighborLeafKey] if (!neighborLeafHash) { neighborLeafHash = this.defaultHashes[level] } if (!nextLevel[parentLeafKey]) { let parentLeafHash = isEvenLeaf ? ethUtil.sha3(Buffer.concat([leafHash, neighborLeafHash])) : ethUtil.sha3(Buffer.concat([neighborLeafHash, leafHash])) if (level == this.depth - 1) { nextLevel['merkleRoot'] = parentLeafHash } else { nextLevel[parentLeafKey] = parentLeafHash } } }) this.levels.unshift(nextLevel) } } } }
Ce code est assez trivial. Nous avons un référentiel de valeurs-clés avec une preuve d'inclusion / non-inclusion.
À chaque itération, un niveau spécifique d'un arbre final est rempli, en commençant par le dernier. Selon que la clé de la feuille courante est paire ou impaire, nous prenons deux feuilles adjacentes et comptons le hachage du niveau actuel. Si nous atteignons la fin, nous écririons un seul merkleRoot - un hachage commun.
Vous devez comprendre que cet arbre est rempli de valeurs initialement vides. Si nous stockions une énorme quantité d'ID de jeton, nous aurions une taille d'arbre énorme, et ce serait long!
Il existe de nombreux remèdes à cette non-optimisation, mais nous avons décidé de changer cet arbre en arbre Patricia.
Un arbre Patricia est une combinaison de Radix Tree et Merkle Tree.
Une clé de données Radix Tree stocke le chemin d'accès aux données elles-mêmes, ce qui nous permet de créer une structure de données optimisée pour la mémoire.
Voici une implémentation développée pour notre client:
buildNode(childNodes, key = '', level = 0) { let node = {key} this.iterations++ if (childNodes.length == 1) { let nodeKey = level == 0 ? childNodes[0].key : childNodes[0].key.slice(level - 1) node.key = nodeKey let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(nodeKey)), childNodes[0].hash]) node.hash = ethUtil.sha3(nodeHashes) return node } let leftChilds = [] let rightChilds = [] childNodes.forEach((node) => { if (node.key[level] == '1') { rightChilds.push(node) } else { leftChilds.push(node) } }) if (leftChilds.length && rightChilds.length) { node.leftChild = this.buildNode(leftChilds, '0', level + 1) node.rightChild = this.buildNode(rightChilds, '1', level + 1) let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(node.key)), node.leftChild.hash, node.rightChild.hash]) node.hash = ethUtil.sha3(nodeHashes) } else if (leftChilds.length && !rightChilds.length) { node = this.buildNode(leftChilds, key + '0', level + 1) } else if (!leftChilds.length && rightChilds.length) { node = this.buildNode(rightChilds, key + '1', level + 1) } else if (!leftChilds.length && !rightChilds.length) { throw new Error('invalid tree') } return node }
Nous nous sommes déplacés récursivement et avons construit les sous-arbres gauche et droit séparés. Une clé a été créée comme chemin dans cet arbre.
Cette solution est encore plus banale. Il est bien optimisé et fonctionne plus rapidement. En fait, un arbre Patricia peut être optimisé encore plus en introduisant de nouveaux types de nœuds - nœud d'extension, nœud de branche, etc., comme cela est fait dans le protocole Ethereum. Mais l'implémentation actuelle répond à toutes nos exigences - nous avons une structure de données rapide et optimisée en mémoire.
En mettant en œuvre ces structures de données dans le projet de notre client, nous avons rendu possible la mise à l'échelle de Plasma Cash. Cela nous permet de vérifier l'historique d'un jeton et l'inclusion / non-inclusion du jeton dans un arbre, accélérant considérablement la validation des blocs et de la chaîne enfant plasma elle-même.
Liens:
- Plasma papier blanc
- Git hub
- Cas d'utilisation et description de l'architecture
- Papier réseau Lightning