[PYTHON] 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 ...)

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
λ
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.

• $ \ frac {λ ^ ke ^ {-λ}} {k!} La partie $ * est la fonction de densité de probabilité de la distribution de Poisson, qui calcule sa probabilité de se produire. À propos, la distribution de Poisson est souvent utilisée pour traiter des événements aléatoires et est souvent utilisée pour calculer le contrôle de la qualité et les taux d'accidents.

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.

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 ...

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.

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.

• Extrait de N.Satoshi (2008)

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.

À 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.

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"