[PYTHON] Ich habe versucht, mich eingehender mit Sicherheit zu befassen, während ich die probabilistische Endgültigkeit von Proof of Work berechnet habe

Die öffentliche Blockchain wird als öffentliche Kette bezeichnet. Viele Blockchains dieses Typs verwenden den "Proof of Work" als den Prozess der eindeutigen Bestimmung der richtigen Daten. Und dieser Mechanismus hat die Eigenschaft, dass es keine Endgültigkeit gibt (Abschluss der Abrechnung). Kurz gesagt, dies ist die Art, einen Vermögenswert an jemanden zu senden und nicht zuzugeben, dass er sicher hinterlegt wurde. Es kann sich die Frage stellen: "Nun, kann es als Geld verwendet werden?", Aber das Konzept der "probabilistischen Endgültigkeit" wurde als Lösung eingeführt. Dieses Mal werden wir tiefer graben, während wir tatsächlich die stochastische Endgültigkeit berechnen.

Was ist Endgültigkeit (Zahlungsabschluss)?

Endgültigkeit bedeutet "es kann davon ausgegangen werden, dass der Vergleich bestätigt wurde". Wenn Sie mit dem Geld, das Sie normalerweise ausgeben, den 100-Yen-Ball an die Kasse übergeben, wird das Eigentum an dem 100-Yen-Ball zu diesem Zeitpunkt übertragen, sodass Sie davon ausgehen können, dass die Abrechnung dort bestätigt wurde. Auch im Falle einer Überweisung wird die Abrechnung abgeschlossen, solange die Bank, die das Konto verwaltet, die Überweisung genehmigt.

In der öffentlichen Kette ist ihre Endgültigkeit jedoch ** wahrscheinlich ** festgelegt. Mit anderen Worten, es ist in Ordnung zuzugeben, dass die Zahlung nach dieser Zeit (nach dem Fortschritt des Bergbaus) bestätigt wurde. Wenn der Bergbau erfolgreich ist, ist er daher nicht sicher und es besteht immer die Möglichkeit, dass er umgeworfen wird.

Hash-Leistung ≒ Rechenleistung

Schauen wir uns das Konzept der "Hash-Power" an, bevor wir die probabilistische Endgültigkeit betrachten. Die Hash-Leistung repräsentiert die Rechenleistung der am Mining beteiligten Maschinen im Sinne der Rechenleistung. Je höher die Rechenleistung, desto schneller wird der Mining-Vorgang erfolgreich abgeschlossen, da Sie mehr Berechnungen durchführen können.

Wenn Sie gleichzeitig mit dem Mining auf zwei Maschinen mit unterschiedlichen Hash-Leistungen beginnen, kann die Maschine mit der größeren Hash-Leistung schneller abbauen und die Konkurrenz gewinnen.

Satoshinakamotos Denkweise

Probabilistische Endgültigkeit auch in der Veröffentlichung "Bitcoin: Ein Peer-to-Peer-E-Cash-System", die als Originaltext die Kernideen von Bitcoin zusammenfasst. Wird indirekt erwähnt.

In Kapitel 11, "Berechnungen", gibt es einen Teil, der die Wahrscheinlichkeit tatsächlich berechnet und überprüft, wie stark der Proof of Work gegen böswillige Angriffe ist. Ein Angriff ist hier ein Angriff, bei dem ein erfolgreich abgebauter Block durch eine längere Kette widerrufen wird. Der Proof of Work hat die Regel, dass die längste Kette die richtige Information ist. Selbst wenn Sie denken, dass sie im Moment die längste ist, wenn eine längere Kette herauskommt, ist das "Gerechtigkeit". Dies ist einer der wichtigen Teile, da das häufige Auftreten von Blöcken, die ablaufen und Transaktionen ungültig machen, sie als Währung völlig unbrauchbar machen würde, geschweige denn als endgültig.

Übrigens berechnen wir in Satoshina Kamotos Artikel anhand der Poisson-Verteilung der Statistiken Folgendes. (Wenn Sie allergisch gegen mathematische Formeln sind, fahren Sie mit dem nächsten Kapitel fort ...)

Die Bedeutung jeder Variablen ist wie folgt.

Variablen / Konstanten	Bedeutung
p	Wahrscheinlichkeit, dass ein wohlmeinender Bergmann erfolgreich Bergbau betreibt
q	Wahrscheinlichkeit, dass ein böswilliger Bergmann erfolgreich Bergbau betreibt
z	Die Anzahl der Blöcke nach einer Transaktion wird in einem Block gespeichert
λ
e	Napierzahl (Basis des natürlichen Logarithmus)

Übrigens ist Bergbau für gute oder schlechte Bergleute immer erfolgreich, also ist $ p + q = 1. Es ist kompliziert mit der Fallklassifizierung, aber es ist ungefähr wie folgt. Erstens ist die Wahrscheinlichkeit, dass ein Angreifer, der durch z-Blöcke verzögert wird, erfolgreich abbaut und die richtige Blockchain einholt, * $ (q / p) ^ z $ *. $ (q / p) $ ist die Wahrscheinlichkeit, dass nur ein Block abgebaut werden kann, und wenn q = 0,1 ist, ist es 1/9. Es dauert z-mal (z-Blöcke), also dauert es z-mal, um z zu erhöhen.

• $ \ frac {λ ^ ke ^ {-λ}} {k!} Der $ * -Teil ist die Wahrscheinlichkeitsdichtefunktion der Poisson-Verteilung, die berechnet, wie wahrscheinlich es ist, dass sie auftritt. Übrigens wird die Poisson-Verteilung häufig bei zufällig auftretenden Ereignissen und bei der Berechnung der Qualitätskontrolle und der Unfallraten verwendet.

Die Wahrscheinlichkeit, dass beide der beiden oben genannten Ereignisse auftreten, kann durch Multiplikation mit * $ \ frac {λ ^ ke ^ {-λ}} {k!} (\ Frac {q} {p}) ^ z $ * berechnet werden. ..

Dann wird die obige Formel in Sigma unterteilt, wenn der Wert von z größer als k ist und wenn er kleiner als k ist. Danach wird es ausgedrückt, indem die Wahrscheinlichkeit, dass ein Ereignis nicht auftritt, von der Gesamtwahrscheinlichkeit (1) subtrahiert wird, wie auf der rechten Seite gezeigt. Diese Denkweise wird als zusätzliches Ereignis bezeichnet. Auf diese Weise verschwindet die Unendlichkeit und Sie können an Sigmen von 0 bis z denken.

Wenn Sie danach die rechte Seite der obigen Formel wie die rechte Seite der unteren Formel anordnen ...

Die folgende Formel ist vervollständigt. Diese Formel erscheint auch in Satoshina Kamotos Artikel, ist jedoch im Programm einfacher zu handhaben, da es keine Unendlichkeit und nur ein Sigma gibt.

In diesem Artikel wird diese Formel auch zur Berechnung in den Code (Sprache C) aufgenommen.

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;
}

Ich habe es mit Python berechnet

Es ist möglich, in C-Sprache zu rechnen, wie es in der Arbeit steht, aber (persönlich) bin ich besser in der wissenschaftlichen Berechnung, also konvertieren wir es in Python und berechnen.

Wahrscheinlichkeit eines erfolgreichen Angreifers

In Python sieht es so aus:

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

Die Verwendung von Variablen und das Berechnungsverfahren werden fast unverändert verwendet. Wenn Sie den folgenden Code ausführen, besteht eine Wahrscheinlichkeit von q = 0,1, z = 10, dh ein böswilliger Miner hat eine 10% ige Chance auf erfolgreiches Mining, und Blöcke sind 10 Blöcke länger verbunden als ein guter Miner. Sie können die Wahrscheinlichkeit berechnen.

probability.py

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

Ausgabeergebnis

0.00000124140217479795642434325410319306826067986549

Berechnen wir die Wahrscheinlichkeit mit verschiedenen Mustern etwas mehr! Berechnen Sie in der for-Anweisung die Wahrscheinlichkeit, wenn der Wert von z 0 bis 10 beträgt, und geben Sie ihn aus.

probability.py

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

Ausgabeergebnis

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

Wenn Sie es mit der Wahrscheinlichkeit in Satoshina Kamotos Artikel vergleichen, können Sie sehen, dass es übereinstimmt.

• Auszug aus N.Satoshi (2008)

Ich habe versucht, ein Diagramm zu erstellen

Bisher haben wir die Wahrscheinlichkeit berechnet, aber zeichnen wir sie in ein Diagramm und visualisieren sie. Während wir den Code bisher geerbt haben, schreiben wir den Code wie folgt.

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()

Zeichnen wir einen Graphen mit q = 0,1 und z = 10, für den die Wahrscheinlichkeit früher berechnet wurde. Es ist in Ordnung, wenn Sie es im Argument wie folgt angeben.

plot.py

attcker_plot(0.1, 10)

Das Ausgabediagramm ist wie folgt. Die horizontale Achse ist z und die vertikale Achse ist die Erfolgsrate böswilliger Bergleute. Sie können sehen, dass je größer der Wert von z ist, desto näher die Wahrscheinlichkeit an 0 liegt und ab etwa ** 4 ** so nahe wie möglich an 0 liegt.

Von hier aus zeichnen wir ein Diagramm mit etwas mehr Mustern. Schreiben wir den Code wie folgt um und betrachten insgesamt 5 Muster mit q-Werten in Schritten von 0,05 von 0,1 bis 0,25. Auch der Wert von z wurde auf 20 erhöht. Die Grafiken werden überlagert. Die obige Grafik war sehr einfach, also verwenden wir Seaborn, um es ein wenig "wunderschön" zu machen.

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)

Das durch Ausführen dieses Codes gezeichnete Diagramm sieht wie folgt aus.

Sie können sehen, dass die Änderung im Diagramm umso langsamer ist, je höher der Wert von q (die Erfolgsrate des Angreifers) ist. Auf diese Weise können je höher die Hash-Kraft des Angreifers und je höher die Erfolgsrate des Bergbaus ist, desto mehr Blöcke nacheinander verbunden werden, um eine eindeutige Kette zu erstellen.

Wie lange soll ich am Ende warten?

Bisher haben wir darüber nachgedacht, wie wahrscheinlich böswillige Bergleute erfolgreich sein werden. Ein wichtiger Punkt bei der Prüfung der Endgültigkeit ist die Überzeugung, dass eine einmal getätigte Transaktion nicht umgestürzt wird. Wenn wir auf die bisherige Diskussion zurückblicken, müssen wir darüber nachdenken, wie wahrscheinlich es ist, dass ein böswilliger Bergmann die Blockchain stört. In diesem Sinne ist es notwendig, die Endgültigkeit probabilistisch zu bestimmen, aber wie Sie aus dem Diagramm sehen können, ist die Wahrscheinlichkeit eines exponentiellen Umkippens umso geringer, je größer z ist. Selbst wenn der Wert von q (Erfolgsrate des Angreifers) bis zu einem gewissen Grad hoch ist und z ein bestimmtes Niveau überschreitet, nähert sich die Wahrscheinlichkeit daher unendlich 0.

** Wenn es sich so weit wie möglich 0 nähert, kann gesagt werden, dass es realistisch ist, die Transaktion zu bestätigen und zu berücksichtigen, dass die Abwicklung abgeschlossen ist **, was die Grundlage für die probabilistische Endgültigkeit ist. Ich bin.

Tatsächlich wird im Fall von Bitcoin die Transaktion erst nach Abschluss von 6 Blöcken als abgeschlossen betrachtet. Im Fall von Bitcoin wird ein Block in durchschnittlich 10 Minuten abgebaut, sodass etwa 1 Stunde gewartet werden muss, um die Zahlung abzuschließen. In der obigen Grafik liegt die Möglichkeit, die Kette umzudrehen, wenn 6 Blöcke verbunden sind, nahe bei 0. (Obwohl es nicht 0 ist ...)

Darüber hinaus können Sie eine Mining-Belohnung erhalten, wenn ein Miner erfolgreich Mining abbaut. Diese ist jedoch nur verfügbar, wenn Sie 100 Blöcke aus dem vom Miner abgebauten Block verbinden.

Zusammenfassung

Dieses Mal habe ich versucht, die stochastische Endgültigkeit statistisch zu bestätigen. In der öffentlichen Kette wissen wir nicht, wer am Netzwerk teilnimmt und wie viele Personen. Daher versuchen wir, Betrug durch Nutzung der Rechenleistung der Maschine zu verhindern. Wie hier vorgestellt, können Sie, wenn Sie wahrscheinlich denken, die Richtigkeit auch in einem System ohne Administrator garantieren.

Wenn die Bedingungen jedoch bis zu einem gewissen Grad erfüllt sind, kann betrogen werden, z. B. ein erfolgreicher Angriff und eine nicht vorhandene Transaktion oder eine nicht vorhandene Transaktion. Ich werde darüber in einem anderen Artikel sprechen.

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