Consensus sur les crypto-monnaies avec l'exploitation minière hybride et multi-PoW

Il m'est arrivé de participer au développement d'un mécanisme d'exploration de données pour la crypto-monnaie, vous permettant d'utiliser différents algorithmes de hachage pour créer une blockchain. L'objectif est de permettre aux mineurs disposant de n'importe quel équipement (ASIC, GPU, CPU) de prendre en charge le réseau, couvrant tout le public possible des participants au réseau. Dans l'article, je vais vous dire quels résultats nous sommes arrivés, à propos de l'exploitation minière en bitcoin et d'autres crypto-monnaies utilisant l'exploitation minière hybride.



Outre le fait que l'exploitation minière est récompensée et que la récompense est la principale source d'émission de pièces dans la plupart des crypto-monnaies, la fonction la plus importante de ce mécanisme est de parvenir à un consensus parmi les participants au réseau. Le consensus est assuré par une loi simple - lors de la ramification d'une blockchain (fourche), la chaîne est considérée comme vraie, au cours de la construction de laquelle le plus grand nombre de hachages (travaux) a été effectué.

Pour construire une exploration multi-hybride, deux tâches doivent être résolues - le calcul de la cible pour chacun des algorithmes et la recherche d'un mécanisme de comparaison qui vous permet de faire la chose la plus difficile - pour comparer des chaînes composées de blocs avec différents algorithmes et, par conséquent, d'une ampleur de travail très différente.


L'exploration multihybride est un terme indéfini, dans l'article, il est utilisé pour désigner la preuve d'extraction (POW) sur plusieurs algorithmes. Dans les crypto-communautés anglophones et russophones, le nom généralement accepté est Multi-PoW. Il sera considéré sur l'exemple de la crypto-monnaie Verge avec cinq algorithmes . L'exploitation hybride est un terme couramment accepté appliqué aux crypto-monnaies utilisant POW et le stockage de preuve de dépôt / équité (POS). Nous le considérerons sur l'exemple de l'un des pionniers d'une telle solution - Novacoin.

Pour comprendre le mécanisme d'exploration de données, vous devez comprendre les concepts fondamentaux suivants dans les crypto-monnaies - travail et objectif (cible). L'objectif est une valeur numérique définissant la limite supérieure des hachages appropriée pour créer un bloc dans une chaîne. Travail - statistiquement, le nombre moyen de recherches nécessaires pour trouver un hachage d'une cible plus petite ou égale.

$$

$$work = \ frac {2 ^ {256}} {target + 1}$$

Bitcoin l'utilise exactement et le code utilisant cette formule est ici . Et ici, le travail est utilisé pour atteindre un consensus - comparer les fourches blockchain et choisir la meilleure chaîne.

L'objectif principal de la cible est d'être fixé à une valeur telle que le temps de libération du bloc se produit dans un intervalle de temps donné. Pour le bitcoin, l'intervalle est de 10 minutes. Le recomptage cible en bitcoin se produit tous les blocs de 2016. Pour définir une nouvelle cible, Bitcoin détermine le taux de hachage moyen - la quantité de travail réseau par unité de temps pour les blocs 2016 précédents. Calcule le travail attendu en 10 minutes et en se fixant un objectif, définit sa valeur pour les prochains blocs 2016. Pour le bitcoin, le calcul de la cible, compte tenu de l'égalité de la cible (et donc du travail) des blocs 2016 précédents, après réductions et approximations, est donné dans une formule assez simple.

$$

$$target_ {new} = \ frac {2 ^ {256}} {work_ {next}} - 1 = \ frac {2 ^ {256}} {{10min} \ cdot {hashrate_ {aver}}} - 1 = \ frac {2 ^ {256}} {\ frac {{10min} \ cdot {work_ {2016}}} {time_ {2016}}} - 1 =$$

$$

$$= \ frac {{2 ^ {256}} \ cdot {time_ {2016}}} {{{10min} \ cdot {2016} \ cdot {\ frac {2 ^ {256}} {{target_ {prev}} + 1}}}} - 1 = \ frac {{time_ {2016}} \ cdot \ left ({{target_ {prev}} + 1} \ right)} {{{10min} \ cdot {2016}}} - 1 \ approx \ frac {{time_ {2016}} \ cdot {target_ {prev}}} {{10min} \ cdot {2016}}$$

En plus des crypto-monnaies, la tâche de cible, de travail et de taux de hachage (vitesse de génération de hachage) est résolue par des pools . La piscine ne connaît pas la valeur de hachage directe d'un mineur individuel. Obtenir tous les hachages est impossible en raison des limitations de la bande passante et inutile - les vérifier pour les coûts équivaut à l'exploitation minière. Le pool reçoit des réponses des mineurs avec un objectif insuffisant pour former un bloc, détermine la part du mineur dans le pool, hashrate et définit un tel objectif pour chaque mineur afin que les réponses d'eux n'occupent pas tout le trafic.


Graphique de lancement de 12 dés à facettes par un joueur avec un hashrate de 1 lancer / sec en 100 secondes. Chaque point est la valeur de la face dessinée, l'axe Y droit est le nombre de valeurs tombées dans la cible. On peut voir que 20 tirs tombent dans la cible 2 - les lancers avec une valeur de 1 et 2. L'évaluation du travail sera de 20 * 12/2 = 120 tirs, avec la cible 6 le travail est de 53 * 12/2 = 106. La propriété principale utilisée est pour tout Cible dans l'état de statistiques suffisantes recevoir proche de la valeur exacte du travail et du hashrate du participant.

Une crypto-monnaie avec plusieurs algorithmes, comme un pool, devrait évaluer le hachage de l'algorithme participant et sélectionner une cible qui fournirait l'intervalle de temps souhaité entre les blocs. Le mécanisme de calcul de cible correct, en plus de l'intervalle, devrait fournir les parts appropriées des différents blocs dans la blockchain.

Il vaut la peine de faire une digression dans l'histoire pour comprendre les caractéristiques du calcul de la cible dans les crypto-monnaies lancées après le bitcoin. Dans l'ancien temps du fringant, les courageux pionniers de l'altcoinstruction ont pris le code Bitcoin, ont apporté des modifications minimes et ont lancé le «Bitcoin killer». Il y avait même des générateurs en ligne de nouveaux dépôts de code altcoin. Cette approche a entraîné un certain nombre de problèmes, dont l'un concernait le calcul de la cible et s'est posé dans le scénario suivant. Un mineur dont le taux de hachage était considérablement plus élevé que les autres participants était connecté à l'extraction de crypto-monnaie. Étant donné que la cible a été rarement recomptée, un tel mineur a créé des blocs avec un intervalle très court et a réussi à créer un nombre hebdomadaire de blocs en quelques heures et, en conséquence, à collecter une récompense hebdomadaire. En atteignant le bloc sur lequel la cible a été recalculée, le mineur est allé vers un autre altcoin avec un taux de hachage approprié. Avec l'augmentation de la cible, les mineurs restants ne pouvaient pas générer un bloc à un temps raisonnable, sans parler de la génération de tous les blocs avant le nouveau recalcul de la cible et quitté l'altcoin. Les pièces de la blockchain se sont finalement arrêtées. La principale solution à ce problème était de recalculer la cible de chaque bloc.

À première vue, le calcul de la cible dans Novacoin n'est pas très différent du calcul dans Bitcoin. Novacoin a correctement séparé le calcul du POS et du POW. La formule finale pour calculer la cible des blocs POS dans Novacoin est la suivante

$$

$$target_ {new} = target_ {last} \ cdot \ frac {7day - 10min + 2 \ cdot {time_ {pos \ _intrerval}}} {7day + 10min}$$

ce qui n'a aucun sens par rapport au calcul du hachage moyen en bitcoin et des prévisions à ce sujet. Toutes les statistiques de cette formule sont impliquées indirectement - tout de même, la valeur cible précédente est calculée comme le résultat des résultats précédents dans la blockchain. Le mécanisme dans son ensemble est similaire au maintien d'une distance par une voiture, l'intervalle est inférieur à 10 minutes - on relâche la pédale d'accélérateur, plus - on appuie.

Le calcul du POW est presque le même, sauf que Novacoin revendique une fréquence différente pour les blocs POW et POS et elle est calculée à des intervalles de 10 minutes à 30 en fonction de la position dans la blockchain. Vous pouvez voir que si le réseau perd fortement son hachage POW ou POS, la cible restera valide jusqu'à ce qu'un nouveau bloc apparaisse sur le mécanisme de minage qui a perdu de la puissance.

Le calcul de la cible dans Verge utilise le mécanisme Dark Gravity Wave, qui est un développement des idées avancées par Kimoto Gravity Well. Sans entrer dans les mathématiques de toutes ces méthodes, l'objectif de ces mécanismes, sans doute nommés de manière poétique, est l'un - d'assurer la conversion de la cible assez rapidement pour répondre aux changements du taux de hachage du réseau. Malgré une certaine ingéniosité du code , ses mathématiques se résument à des formules assez simples. Verge calcule la cible moyenne de 12 blocs de l'algorithme sélectionné, dans laquelle le dernier bloc est compté deux fois:

$$

$$target_ {aver} = \ frac {2 \ cdot {target_ {last}} + {target_ {last-1}} + {...} + {target_ {last-11}}} {13}$$

La question qui se pose immédiatement quant à la légitimité de l'ajout de la cible a cependant une justification mathématique. La cible résultante est une cible pour le travail moyen harmonique.

$$

$$\ frac {13 \ cdot ({target_ {aver} + 1)}} {2 ^ {256}} = \ frac {2 \ cdot ({target_ {last} + 1)}} {2 ^ {256}} + \ frac {target_ {last-1} + 1} {2 ^ {256}} + {...} + \ frac {target_ {last-11} + 1} {2 ^ {256}}$$

Le reste des calculs coïncident exactement avec le calcul via le taux de hachage moyen pour le bitcoin.

$$

$$target_ {new} \ approx \ frac {{time_ {12}} \ cdot {target_ {aver}}} {{0.5min} \ cdot {5} \ cdot {12}}$$

Il convient de noter que le hashrate dans Verge est calculé à partir du travail harmonique moyen et du temps moyen arithmétique, et par conséquent, l' inégalité des moyennes aurait une valeur inférieure si le temps et le travail étaient pris avec les mêmes moyens.

Les mathématiques du calcul de la cible dans les projets avec des preuves / algorithmes mixtes diffèrent sensiblement de l'original en bitcoin. Le deuxième côté de la médaille du mécanisme cible et du travail est la solution du problème du consensus - la définition de la branche blockchain qui est considérée comme la vraie en cas de litige. Le problème fondamental pour les blockchains mixtes est l'impossibilité de choix lors de l'utilisation de la comparaison des sommes du travail des blocs pour tous les algorithmes / preuves. De toute évidence, les algorithmes / preuves ayant intrinsèquement un hashrate supérieur avec une telle logique primitive domineront la blockchain.

À Novacoin, malgré l'utilisation d'un certain score de confiance dans les commentaires et la dénomination des variables, une analyse détaillée de la logique se révèle être rien de plus qu'un travail. Le calcul pour POS coïncide exactement avec la formule de travail, et le calcul pour POW peut être considéré comme fonctionnant avec une sorte de coefficient constant décroissant. Le reste des calculs supplémentaires ressemble à un ordre d'équilibrage supplémentaire des blocs par rapport au mécanisme cible. Il convient de noter que ce n'est pas la meilleure solution. Comme nous le verrons plus loin, seule une cible est suffisante pour équilibrer les blocs. De plus, les blocs POS et POW avec un parent commun peuvent être inégaux, bien que le fait d'apparaître des blocs valides avec un parent commun doit être défini comme leur égalité.

Avant d'examiner l'état actuel du mécanisme de consensus, Verge sera informatif pour se pencher sur son passé. Au printemps 2018, Verge a survécu à plusieurs attaques. Sans entrer dans les détails de la mécanique d'attaque, le code de l'époque , responsable du choix d'une fourchette, contient une logique douteuse. Si nous supposons que la fonction IsProofOfStake () dans la crypto-monnaie POW peut retourner la vraie valeur, alors l'ajout de différents algorithmes, comme indiqué ci-dessus, conduira à la domination d'un algorithme avec un hashrate plus élevé. Sinon, le choix se fait simplement par la longueur de la chaîne, qui avec une cible correctement calculée (dont le but est l'apparence uniforme des blocs) peut conduire à l'égalité des branches avec des travaux vraiment très différents.

Dans le code actuel, Verge utilise des coefficients constants pour la comparaison. En supposant que ces coefficients prennent en compte une certaine pertinence des capacités des équipements miniers, la faiblesse évidente de ce choix est la perte de pertinence lors de l'apparition de nouveaux équipements.

Les propriétés natives des mathématiques et du travail cibles nous permettent de construire des modèles de calcul plus simples et plus compréhensibles sur la blockchain. Considérons un modèle et un code émulant un calcul cible pour une blockchain avec quatre algorithmes. Laissez deux d'entre eux occuper un tiers des blocs. Pour simplifier la modélisation, nous pouvons supposer que le bloc avec le plus petit intervalle du précédent est le meilleur pour construire un circuit. Dans les crypto-monnaies réelles, un tel choix correspond au scénario le plus courant. Le modèle teste également l'augmentation et la diminution du taux de hachage de l'un des algorithmes.

Le calcul de la cible sera calculé à partir de la moyenne arithmétique du travail et du temps sur les statistiques des 300 derniers blocs. La formule de calcul finale:

$$

$$target = \ frac {2 ^ {256}} {k \ cdot {60} \ cdot {hashrate_ {aver}}} - 1$$

où k est le nombre d'intervalles pour lesquels un bloc de l'algorithme doit être pour lequel la cible est calculée.

Résumons dans le tableau les valeurs initiales et calculées pour 10 000 blocs.Je veux noter que la valeur calculée du circuit est calculée par la formule:

$$

$$work_ {algo} = hashrate_ {algo} \ cdot {time_ {all block}}$$

Le calcul des hachages dans le réseau se produit au cours du temps des blocs de tous les algorithmes, et pas seulement aux intervalles des algorithmes individuels. Comme dans l'exemple avec un cube à vingt faces - quelle que soit la cible sélectionnée, l'évaluation du travail sera égale. Pour les calculs, il faut en tenir compte, par un coefficient k pour calculer la cible d'un nouveau bloc à travers un taux de hachage, et prendre tout le temps pour calculer le travail.Comme vous pouvez le voir, les résultats de l'émulation coïncident assez bien avec le calcul en fonction des données source.

<sup>Graphique à blocs 3850-4650

Graphique à blocs 5599-6399</sup>

Sur les graphiques de l'évolution du travail au fil du temps, on voit comment la densité des blocs augmente et diminue lorsque le taux de hachage change. En principe, c'est un comportement logique et logique, mais il est également tout à fait approprié de le réguler en utilisant des techniques comme la Dark Gravity Wave - augmentant l'influence des derniers blocs, et d'autres.

En ce qui concerne la question de déterminer le consensus des fourches à partir de blocs avec différents algorithmes, il convient de noter la propriété de base suivante - les blocs avec un bloc précédent commun sont équivalents les uns aux autres. Leurs objectifs et leur évaluation des performances donnent des droits égaux à occuper une place dans la chaîne. Cette observation conduit immédiatement à l'idée d'utiliser l'équivalence - en utilisant la quantité de travail, des coefficients variant du rapport des cibles, etc. En omettant de prendre en compte les lacunes de toutes ces idées, nous passerons à la méthode qui répond le mieux aux exigences de la blockchain.

Si nous considérons les prédictions géométriques moyennes du travail de tous les algorithmes de blocs, la somme de ces travaux équivalents est la meilleure caractéristique pour comparer les fourches.

$$

$$work_ {equal} = \ sqrt [k_1] {work_ {algo_1}} \ cdot \ sqrt [k_2] {work_ {algo_2}} \ cdot ... \ cdot \ sqrt [k_n] {work_ {algo_n}}$$

Où k est le nombre d'intervalles sur lesquels un bloc de l'algorithme doit tomber, pour lequel la cible est calculée.

Un tel travail équivalent a les propriétés suivantes:

• lorsque le taux de hachage de tous les algorithmes est modifié n fois, l'estimation du consensus de chaîne changera également n fois
• en augmentant le hashrate de l'un des algorithmes et en diminuant les n autres fois avec des parts égales dans le minage, l'estimation consensuelle de la chaîne sera égale
• avec des proportions égales d'algorithmes et des taux de hachage égaux de ces algorithmes, le fonctionnement équivalent et le fonctionnement de tout algorithme seront égaux
  

Le mécanisme de fonctionnement équivalent complique considérablement l'attaque 51 sur la blockchain. La formule de travail équivalent, exprimée par un taux de hachage, vous permet d'estimer la puissance nécessaire à une attaque.

$$

$$work_ {equal} = \ sqrt [k_1] {{k_1} \ cdot {t} \ cdot {hashrate_ {algo_1}}} \ cdot \ sqrt [k_2] {{k_2} \ cdot {t} \ cdot {hashrate_ { algo_2}}} \ cdot ... \ cdot \ sqrt [k_n] {{k_n} \ cdot {t} \ cdot {hashrate_ {algo_n}}}$$

Si l'attaquant décide de mener l'attaque selon l'un des algorithmes et ne sera pas en mesure de calculer le reste, le hashrate nécessaire devra dépasser considérablement le hashrate du réseau.
Par exemple, une table d'attaque, le temps entre les blocs est de 60. Supposons qu'un attaquant ne peut fournir que 50% du hashrate dans trois algorithmes.
Pour atteindre l'égalité avec le réseau, il devra avoir un hashrate 4 fois plus élevé que le hashrate du réseau selon le premier algorithme.

Le graphique suivant montre le résultat de l' émulation d'une attaque sur une blockchain.



L'attaque commence au bloc 1000. La somme des emplois équivalents en émulation pour les deux branches diffère légèrement et montre l'égalité des branches.

En résumé, on peut noter que les mécanismes de consensus dans les crypto-monnaies avec des algorithmes / preuves mixtes peuvent être mathématiquement justifiés et que ces crypto-monnaies sont plus difficiles à attaquer 51.

Bonne blockchain à tous et merci pour votre attention sur le sujet.