J'ai essayé d'approfondir la sécurité tout en calculant la finalité probabiliste de la preuve de travail

La blockchain publique s'appelle la chaîne publique. De nombreuses blockchains de ce type utilisent la «preuve de travail» comme processus de détermination unique des données correctes. Et ce mécanisme a la propriété qu'il n'y a pas de finalité (achèvement du règlement). En bref, c'est la nature d'envoyer un bien à quelqu'un et de ne pas admettre qu'il a certainement été déposé. La question peut se poser: «Eh bien, peut-elle être utilisée comme monnaie?», Mais le concept de «finalité probabiliste» a été introduit comme solution. Cette fois, nous allons creuser plus profondément tout en calculant la finalité stochastique.

Qu'est-ce que la finalité (achèvement du paiement)?

La finalité signifie "on peut considérer que le règlement a été confirmé". Si vous utilisez l'argent que vous dépensez normalement, si vous remettez la balle de 100 yens à la caisse, la propriété de la balle de 100 yens sera transférée à ce moment-là, vous pouvez donc considérer que le règlement y a été confirmé. Même en cas de virement bancaire, le règlement sera effectué tant que la banque qui gère le compte approuve le virement.

Cependant, dans la chaîne publique, sa finalité est ** probabilistiquement ** fixée. En d'autres termes, il est normal d'admettre que le paiement a été confirmé après ce laps de temps (après la progression de l'exploitation minière). Par conséquent, si l'exploitation minière réussit, elle n'est pas sûre et il y a toujours la possibilité qu'elle soit annulée.

Puissance de hachage ≒ puissance de calcul

Jetons un coup d'œil au concept de "puissance de hachage" avant de considérer la finalité probabiliste. La puissance de hachage représente la puissance de calcul des machines participant à l'exploitation minière au sens de puissance de calcul. Bien sûr, plus la puissance de calcul est élevée, plus vite vous réussirez à miner car vous pouvez faire plus de calculs.

De plus, si vous commencez à miner sur deux machines avec des puissances de hachage différentes en même temps, la machine avec la plus grande puissance de hachage pourra réussir à miner plus rapidement et gagner la concurrence.

La façon de penser de Satoshinakamoto

Finalité probabiliste même dans le papier "Bitcoin: A Peer-to-Peer Electronic Cash System", qui serait le texte original qui résume les idées de base de Bitcoin. Est indirectement mentionné.

Dans le chapitre 11, «Calculs», il y a une partie qui calcule et vérifie la force de la preuve de travail contre les attaques malveillantes. Une attaque ici est une attaque dans laquelle un bloc qui a été miné avec succès une fois est révoqué par une chaîne plus longue que cela. La preuve de travail a une règle selon laquelle la plus longue chaîne est l'information correcte, donc même si vous pensez que c'est la plus longue pour le moment, si une chaîne plus longue sort, c'est «justice». C'est l'une des parties importantes, car l'apparition fréquente de blocs expirant et d'invalidation des transactions les rendrait complètement inutiles en tant que monnaie, sans parler de la finalité.

En passant, dans l'article de Satoshina Kamoto, nous calculons comme suit en utilisant la distribution statistique de Poisson. (Si vous êtes allergique aux formules mathématiques, passez au chapitre suivant ...)

CodeCogsEqn (2).png

La signification de chaque variable est la suivante.

Variables / constantes sens
p Probabilité qu'un mineur bien intentionné réussisse dans l'exploitation minière
q Probabilité qu'un mineur malveillant réussisse dans l'exploitation minière
z Le nombre de blocs après qu'une transaction est stocké dans un bloc
λ CodeCogsEqn (1).png
e Nombre de Napier (base du logarithme naturel)

À propos, l'extraction est toujours réussie pour les bons ou les mauvais mineurs, donc $ p + q = 1. C'est compliqué avec la classification des cas, mais c'est à peu près comme suit. Premièrement, la probabilité qu'un attaquant retardé par z blocs réussisse à miner et rattrape la bonne blockchain est de * $ (q / p) ^ z $ *. $ (q / p) $ est la probabilité qu'un seul bloc puisse être exploité, et si q = 0,1, ce sera 1/9. Il dure z fois (z blocs), il faut donc z fois pour élever z.

La probabilité que les deux événements ci-dessus se produisent peut être calculée en multipliant par * $ \ frac {λ ^ ke ^ {-λ}} {k!} (\ Frac {q} {p}) ^ z $ *. ..

Ensuite, la formule ci-dessus est divisée en sigma lorsque la valeur de z est supérieure à k et lorsqu'elle est inférieure à k. Après cela, il est exprimé en soustrayant la probabilité qu'un événement ne se produise pas de la probabilité totale (1) comme indiqué sur le côté droit. Cette façon de penser s'appelle un événement supplémentaire. En faisant cela, l'infini disparaît et vous pouvez penser aux sigmas de 0 à z.

CodeCogsEqn (3).png

Après cela, si vous disposez le côté droit de la formule ci-dessus comme le côté droit de la formule inférieure ...

CodeCogsEqn (4).png

La formule ci-dessous est complétée. Cette formule apparaît également dans l'article de Satoshina Kamoto, mais elle est plus facile à manipuler dans le programme car il n'y a pas d'infini et il n'y a qu'un seul sigma.

CodeCogsEqn.png

Aussi, dans cet article, cette formule est incorporée dans le code (langage C) pour le calcul.

probability.c


#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
  double p = 1.0 - q;
  double lambda = z * (q / p);
  double sum = 1.0;
  int i, k;
  for (k = 0; k <= z; k++)
    {
      double poisson = exp(-lambda);
      for (i = 1; i <= k; i++)
        poisson *= lambda / i;
      sum -= poisson * (1 - pow(q / p, z - k));
    }
    return sum;
}

Je l'ai calculé avec Python

Il est possible de calculer en langage C comme dans l'article, mais (personnellement) je suis meilleur en calcul scientifique, alors convertissons-le en Python et calculons.

Probabilité d'attaquant réussi

En Python, cela ressemble à ceci:

probability.py


import numpy as np

def attcker_success(q, z):    
    p = 1.0 - q
    l = z * (q/p)
    sum = 1.0

    for k in range(0, z+1):
        poisson = np.exp(-l)
        for i in range(1, k+1):
            poisson *= l / i
        sum -= poisson * (1 - np.power(q/p, z-k))
    return sum

L'utilisation des variables et la procédure de calcul sont utilisées presque telles quelles. Si vous exécutez le code suivant, il y a une probabilité de q = 0,1, z = 10, c'est-à-dire si un mineur malveillant réussit à exploiter avec succès avec une chance de 10% et que les blocs sont connectés 10 blocs de plus qu'un bon mineur. Vous pouvez calculer la probabilité.

probability.py


print('{:.50f}'.format(attcker_success(0.1, 10)))

Résultat de sortie


0.00000124140217479795642434325410319306826067986549

Calculons un peu plus la probabilité avec divers modèles! Dans l'instruction for, calculez la probabilité lorsque la valeur de z est comprise entre 0 et 10 et sortez-la.

probability.py


for z_i in range(0,11):
    print("z=",z_i,'  {:.50f}'.format(attcker_success(0.1, z_i)),sep='')

Résultat de sortie


z=0  1.00000000000000000000000000000000000000000000000000
z=1  0.20458727394278242162073411236633546650409698486328
z=2  0.05097789283933862325426389361382462084293365478516
z=3  0.01317224167889648189788687204782036133110523223877
z=4  0.00345524346648517360902630457530904095619916915894
z=5  0.00091368218792791224339144839916571072535589337349
z=6  0.00024280274536281863662079416599226533435285091400
z=7  0.00006473531692709972641154581030065173763432539999
z=8  0.00001729980418716505960723822665769944251223932952
z=9  0.00000463116397250268184871292015403199116008181591
z=10  0.00000124140217479795642434325410319306826067986549

Si vous le comparez avec la probabilité dans l'article de Satoshina Kamoto, vous pouvez voir que cela correspond. satoshinakamoto-report.png

J'ai essayé de faire un graphique

Jusqu'à présent, nous avons calculé la probabilité, mais dessinons-la sur un graphique et visualisons-la. En héritant du code jusqu'à présent, écrivons le code comme suit.

plot.py


import numpy as np
import matplotlib.pyplot as plt

def attcker_success(q, z):    
    p = 1.0 - q
    l = z * (q/p)
    sum = 1.0
    for k in range(0, z+1):
        poisson = np.exp(-l)
        for i in range(1, k+1):
            poisson *= l / i
        sum -= poisson * (1 - np.power(q/p, z-k))
    return sum

def attcker_plot(q, z):
    probability = []
    progress = []
    for z_prg in range(z+1):
        progress.append(z_prg)
        probability.append(attcker_success(q, z_prg))
    plt.plot(progress, probability)
    plt.show()

Trouvons un graphique lorsque q = 0,1 et z = 10 pour lequel la probabilité a été calculée plus tôt. Ce n'est pas grave si vous le spécifiez dans l'argument comme suit.

plot.py


attcker_plot(0.1, 10)

Le graphique de sortie est le suivant. L'axe horizontal est z et l'axe vertical est le taux de réussite des mineurs malveillants. Vous pouvez voir que plus la valeur de z est élevée, plus la probabilité est proche de 0, et à partir d'environ ** 4, elle est ** aussi proche de 0 que possible. download.png

À partir de là, dessinons un graphique avec un peu plus de motifs. Réécrivons le code comme suit et considérons un total de 5 modèles avec des valeurs q par incréments de 0,05 de 0,1 à 0,25. De plus, la valeur de z a été augmentée à 20. Les graphiques sont superposés. Le graphique ci-dessus était très simple, alors utilisons seaborn pour le rendre un peu "magnifique".

comparison.py


import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd

def attcker_success(q, z):    
    p = 1.0 - q
    l = z * (q/p)
    sum = 1.0
    for k in range(0, z+1):
        poisson = np.exp(-l)
        for i in range(1, k+1):
            poisson *= l / i
        sum -= poisson * (1 - np.power(q/p, z-k))
    return sum

def attcker_data(q, z):
    probability = []
    for z_prg in range(z+1):
        probability.append(attcker_success(q, z_prg))
    return probability

probability_list = []
q_value_list = np.arange(0.05, 0.3, 0.05)

for q_value in q_value_list:
    probability_list.append(attcker_data(q_value, 20))
df = pd.DataFrame(probability_list, index=["q=0.05","q=0.10","q=0.15","q=0.20","q=0.25"])
df = df.T

sns.set(style="darkgrid")
sns.set_context("talk")
plt.figure(figsize=(15, 10))
plt.xlabel('z')
plt.ylabel('probability')
plt.xticks( np.arange(0, 22, 1) )
plt.yticks( np.arange(0, 1.1, 0.1) )
sns.lineplot(data=df)

Le graphique dessiné en exécutant ce code est le suivant. figure-comparison.jpg

Vous pouvez voir que plus la valeur de q (le taux de réussite de l'attaquant) est élevée, plus le changement dans le graphique est lent. De cette façon, plus la puissance de hachage de l'attaquant est élevée et plus le taux de réussite de l'exploitation minière est élevé, plus il est possible de connecter de blocs successivement pour créer une chaîne unique.

En fin de compte, combien de temps dois-je attendre?

Jusqu'à présent, nous avons réfléchi à la façon dont les mineurs probabilistes malveillants réussiront. Un point important lors de l'examen de la finalité est la conviction qu'une transaction une fois effectuée ne sera pas annulée. En repensant à la discussion jusqu'à présent, nous devons réfléchir à la probabilité qu'un mineur malveillant perturbe la blockchain. En ce sens, il est nécessaire de déterminer la finalité de manière probabiliste, mais comme vous pouvez le voir sur le graphique, plus z est grand, plus la probabilité de basculement exponentiel est faible. Par conséquent, même si la valeur de q (taux de réussite de l'attaquant) est élevée dans une certaine mesure, si z dépasse un certain niveau, la probabilité s'approche de 0 à l'infini.

** S'il s'approche le plus possible de 0, on peut dire qu'il est réaliste de confirmer la transaction et de considérer que le règlement est terminé **, ce qui est à la base de la finalité probabiliste. Je suis.

En fait, dans le cas de Bitcoin, la transaction n'est considérée comme terminée qu'après 6 blocs passés. Dans le cas du Bitcoin, un bloc est extrait en 10 minutes en moyenne, il faut donc attendre environ 1 heure pour terminer le paiement. En regardant le graphique ci-dessus, la possibilité de retourner la chaîne lorsque 6 blocs sont connectés est proche de 0. (Bien que ce ne soit pas 0 ...)

De plus, vous pouvez recevoir une récompense minière lorsqu'un mineur réussit à miner, mais celle-ci n'est disponible que si vous connectez 100 blocs du bloc exploité par le mineur.

Résumé

Cette fois, j'ai essayé de confirmer statistiquement la finalité stochastique. Dans la chaîne publique, nous ne savons pas qui participe au réseau et combien de personnes, nous essayons donc de prévenir la fraude en utilisant la puissance de calcul de la machine. Comme présenté ici, si vous pensez de manière probabiliste, il semble que vous puissiez garantir l'exactitude même dans un système sans administrateur.

Cependant, si les conditions sont remplies dans une certaine mesure, il sera possible de tricher, comme une attaque réussie et une transaction inexistante, ou une transaction inexistante. J'en parlerai dans un autre article.

Références </ b> N.Satoshi(2008)"Bitcoin: A Peer-to-Peer Electronic Cash System"

Recommended Posts

J'ai essayé d'approfondir la sécurité tout en calculant la finalité probabiliste de la preuve de travail
J'ai essayé d'améliorer l'efficacité du travail quotidien avec Python
J'ai essayé de résumer la manière logique de penser l'orientation objet.
J'ai essayé de corriger la forme trapézoïdale de l'image
J'ai essayé de vectoriser les paroles de Hinatazaka 46!
J'ai essayé d'automatiser le travail de masquage du visage de l'image de coordination pour l'usure
J'ai essayé de résumer la forme de base de GPLVM
J'ai essayé de visualiser les informations spacha de VTuber
J'ai essayé d'effacer la partie négative de Meros
J'ai essayé d'implémenter le calcul automatique de la preuve de séquence
J'ai essayé de classer les voix des acteurs de la voix
J'ai essayé de résumer les opérations de chaîne de Python
J'ai essayé de trouver l'entropie de l'image avec python
J'ai essayé de découvrir les grandes lignes de Big Gorilla
J'ai essayé d'obtenir les informations de localisation du bus Odakyu
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
[Python] J'ai essayé de visualiser la relation de suivi de Twitter
[Apprentissage automatique] J'ai essayé de résumer la théorie d'Adaboost
J'ai essayé de combattre le minimum local de la fonction Goldstein-Price
[Linux] J'ai essayé de résumer les commandes de confirmation des ressources
J'ai essayé d'obtenir l'index de la liste en utilisant la fonction énumérer
J'ai essayé d'automatiser l'arrosage du pot avec Raspberry Pi
J'ai essayé de corriger "J'ai essayé la simulation probabiliste du jeu de bingo avec Python"
J'ai essayé d'agrandir la taille du volume logique avec LVM
J'ai essayé de résumer la méthode de mise en œuvre fréquemment utilisée de pytest-mock
J'ai essayé de visualiser la condition commune des téléspectateurs de la chaîne VTuber
J'ai essayé de calculer l'intégrale de probabilité (I à l'intégrale)
J'ai essayé de m'organiser à propos de MCMC.
J'ai essayé de déplacer le ballon
J'ai essayé d'estimer la section.
J'ai essayé de faire la différence de Config avant et après le travail avec le script pyATS / Genie self-made
Quand j'ai essayé d'écrire sur la régression logistique, j'ai fini par trouver la moyenne et la variance de la distribution logistique.
J'ai essayé de transformer l'image du visage en utilisant sparse_image_warp de TensorFlow Addons
J'ai essayé de visualiser la tranche d'âge et la distribution des taux d'Atcoder
J'ai essayé de transcrire les actualités de l'exemple d'intégration commerciale sur Amazon Transcribe
zoom J'ai essayé de quantifier le degré d'excitation de l'histoire lors de la conférence
J'ai essayé d'estimer la similitude de l'intention de la question en utilisant Doc2Vec de gensim
Je voulais faire attention au comportement des arguments par défaut de Python
J'ai essayé d'améliorer la précision de mon propre réseau neuronal
J'ai essayé de résoudre 100 traitements linguistiques Knock version 2020 [Chapitre 3: Expressions régulières 25-29]
J'ai essayé d'obtenir le code d'authentification de l'API Qiita avec Python.
J'ai essayé d'extraire automatiquement les mouvements des joueurs Wiire avec un logiciel
(Python) J'ai essayé d'analyser 1 million de mains ~ J'ai essayé d'estimer le nombre d'AA ~
J'ai essayé de trouver l'itinéraire optimal du pays des rêves par recuit (quantique)
J'ai essayé d'extraire et d'illustrer l'étape de l'histoire à l'aide de COTOHA
J'ai essayé de vérifier et d'analyser l'accélération de Python par Cython
J'ai essayé d'analyser la négativité de Nono Morikubo. [Comparer avec Posipa]
J'ai essayé de rationaliser le rôle standard des nouveaux employés avec Python
J'ai essayé de visualiser le texte du roman "Weather Child" avec Word Cloud
[Linux] J'ai essayé de vérifier la méthode de confirmation sécurisée du FQDN (CentOS7)
J'ai essayé d'obtenir automatiquement le RSS de la chanson la plus populaire de l'iTunes Store
J'ai essayé d'obtenir les informations sur le film de l'API TMDb avec Python
J'ai essayé d'afficher la valeur d'altitude du DTM dans un graphique
J'ai essayé l'histoire courante de l'utilisation du Deep Learning pour prédire la moyenne Nikkei
En utilisant COTOHA, j'ai essayé de suivre le cours émotionnel de la course aux meros.
J'ai essayé de vérifier le résultat du test A / B avec le test du chi carré
J'ai essayé de prédire le comportement du nouveau virus corona avec le modèle SEIR.
J'ai essayé le serveur asynchrone de Django 3.0
J'ai essayé de résumer la commande umask