Исследование статистической вероятности значения бита в нонсе bitcoin

Считается, что функция sha256( sha256( BlockHeader ) ), которая используется в алгоритме хэширования bitcoin весьма надежна. Надежна настолько, что существует только один единственный способ подобрать голден нонсе для очередного блока в блокчейне — путем перебора в процессе майнинга.

В настоящее время в блокчейне биткоина уже более 530 тысяч блоков. Этого вполне достаточно, чтобы провести статистический анализ и ответить на вопрос: «действительно ли значения битов в ранее найденных нонсе равновероятно?».

Самый простой статистический анализ можно сделать не на всем блокчейне, а только на последних нескольких тысячах блоков. Для этого потребуется взять эту информацию, например, с сайта btc.com. Этот блокчейн эксплорер имеет достаточно развитое апи, которым и воспользуемся. Напишем вот такой простой скрипт, который с помощью библиотеки requests скачает информацию о последних 2000 блоков. Меня интересует только одно значение — nonce, его я и буду записывать в текстовый файл вместе с номером блока.

import requests

target_blk_num=538800
num_block_for_study=2000

txt=open("bitcoin/nonces.txt","w")

blk_num=target_blk_num-num_block_for_study
print("Fetching blocks from "+str(blk_num) +" to "+str(target_blk_num) )
while blk_num<target_blk_num:
    blk_num_=format(blk_num,'d')
    url_hash="https://chain.api.btc.com/v3/block/"+blk_num_
    block=requests.get(url_hash)
    j=block.json()
    data=j['data']
    nonce=data['nonce']
    print(blk_num,format(nonce,'x'))
    txt.write("%d " % blk_num)
    txt.write("0x%08X " % nonce)
    txt.write("%d" % nonce)
    txt.write("n")
    blk_num=blk_num+1

txt.close()

Нужно запустить скрипт и подождать окончания его работы. Получим вот такой файл с 2-мя тысячами строк:

Теперь разобьем эту выборку на группы по сто значений и произведем статистический анализ по каждой группе. Нонсе — это 32х битное число. По здравому рассуждению каждый бит нонсе равновероятно принимает значение единица или ноль. Как раз это я и собираюсь проверить. напишу вот такой скрипт, который считает количество единиц в каждой позиции бита по группе из 100 нонсе.

import sys
import os

folder=""
stat_N=0
stat=[]
def init_stat():
    global stat
    global stat_N
    stat_N=0
    i=0
    while i<64:
       stat.append(0.0)
       i=i+1

def clear_stat():
    global stat
    global stat_N
    stat_N=0
    i=0
    while i<64:
       stat[i]=0.0
       i=i+1

def add_stat(nonce):
    global stat
    global stat_N
    stat_N=stat_N+1
    i=0
    while i<64:
        if nonce & (1<<i):
            stat[i]=stat[i]+1
        i=i+1

def nonce_num_bits():
    i=32
    while i<64:
        if stat[i]:
            return 64
        i=i+1
    return 32

def print_stat():
    global stat
    global stat_N
    i=0
    sz = nonce_num_bits()
    while i<sz:
        print(i," ",stat[i]/stat_N)
        i=i+1

def init_stat_file():
    global folder
    txt=open(folder+"/stat.txt","w")
    txt.close()

def write_stat():
    global folder
    global stat
    global stat_N
    txt=open(folder+"/stat.txt","a")
    i=0
    sz = nonce_num_bits()
    while i<sz:
        s=stat[i]/stat_N
        txt.write("%.2f " % s )
        i=i+1
    txt.write("n")
    txt.close()

#--------------------------------
args = sys.argv
if len(args)<2:
    print("Error: need argument name of folder with list of nonces")
    exit()

folder=args[1]
print( "Working on "" + folder +""" )
if os.path.isdir(folder)==False:
    print("Error: folder ""+folder+"" does not exist")
    exit()

init_stat()
init_stat_file()

f = open(folder+"/nonces.txt","r")
content = f.read().split("n")
for line in content:
    word = line.split(" ")
    if len(word)<2:
        break
    nonce=int(word[1],16)
    add_stat(nonce)
    if stat_N==100:
        write_stat()
        clear_stat()

f.close

Этот скрипт читает файл bitcoin/nonces.txt и создает новый файл bitcoin/stst.txt примерно вот такого вида:

0.49 0.50 0.45 0.39 0.44 0.40 0.54 0.43 0.47 0.55 0.50 0.54 0.53 0.50 0.54 0.51 0.56 0.47 0.48 0.44 0.44 0.51 0.41 0.52 0.50 0.54 0.42 0.47 0.39 0.52 0.61 0.48
0.40 0.61 0.52 0.48 0.49 0.55 0.45 0.43 0.55 0.56 0.54 0.55 0.56 0.60 0.52 0.42 0.52 0.46 0.61 0.54 0.52 0.52 0.55 0.49 0.46 0.48 0.41 0.42 0.45 0.42 0.47 0.47
0.39 0.50 0.43 0.45 0.46 0.47 0.40 0.51 0.48 0.44 0.52 0.51 0.46 0.45 0.51 0.45 0.45 0.53 0.59 0.51 0.53 0.44 0.52 0.55 0.53 0.47 0.49 0.47 0.41 0.51 0.52 0.52
0.51 0.43 0.39 0.49 0.46 0.53 0.40 0.50 0.49 0.42 0.47 0.56 0.49 0.51 0.57 0.44 0.58 0.52 0.50 0.54 0.48 0.50 0.43 0.53 0.52 0.49 0.48 0.56 0.43 0.42 0.49 0.49
0.44 0.33 0.43 0.57 0.52 0.52 0.44 0.45 0.53 0.45 0.43 0.50 0.52 0.59 0.44 0.47 0.49 0.40 0.50 0.58 0.55 0.55 0.47 0.51 0.45 0.48 0.44 0.42 0.41 0.47 0.50 0.48
0.49 0.46 0.51 0.42 0.57 0.45 0.45 0.35 0.53 0.42 0.51 0.52 0.47 0.51 0.47 0.45 0.48 0.49 0.54 0.48 0.50 0.49 0.46 0.56 0.44 0.48 0.47 0.55 0.46 0.45 0.51 0.50
0.51 0.45 0.52 0.50 0.59 0.41 0.50 0.34 0.47 0.54 0.56 0.48 0.54 0.49 0.54 0.44 0.49 0.48 0.50 0.58 0.44 0.48 0.51 0.47 0.37 0.45 0.47 0.47 0.50 0.52 0.46 0.43
0.51 0.43 0.52 0.57 0.58 0.51 0.47 0.36 0.51 0.44 0.47 0.47 0.49 0.47 0.43 0.39 0.47 0.50 0.56 0.46 0.47 0.47 0.46 0.63 0.48 0.43 0.44 0.46 0.43 0.51 0.45 0.49
0.49 0.49 0.40 0.49 0.53 0.53 0.49 0.50 0.47 0.50 0.41 0.55 0.48 0.48 0.49 0.46 0.54 0.51 0.49 0.55 0.53 0.48 0.50 0.53 0.50 0.41 0.45 0.42 0.41 0.47 0.44 0.51
0.47 0.47 0.47 0.58 0.52 0.42 0.53 0.53 0.59 0.55 0.43 0.48 0.50 0.42 0.46 0.50 0.52 0.53 0.43 0.48 0.58 0.44 0.43 0.42 0.54 0.42 0.58 0.42 0.39 0.45 0.46 0.56
0.51 0.47 0.45 0.38 0.48 0.51 0.39 0.48 0.50 0.57 0.52 0.54 0.54 0.46 0.67 0.47 0.53 0.54 0.48 0.53 0.57 0.55 0.46 0.54 0.43 0.53 0.49 0.37 0.60 0.46 0.50 0.49
0.45 0.46 0.47 0.46 0.47 0.51 0.41 0.53 0.59 0.45 0.51 0.43 0.49 0.46 0.46 0.55 0.52 0.51 0.56 0.51 0.49 0.46 0.45 0.49 0.50 0.55 0.48 0.54 0.44 0.49 0.59 0.49
0.39 0.46 0.53 0.43 0.42 0.54 0.49 0.46 0.52 0.56 0.38 0.46 0.47 0.56 0.60 0.46 0.50 0.59 0.39 0.57 0.50 0.55 0.44 0.54 0.45 0.47 0.52 0.53 0.45 0.41 0.47 0.42
0.48 0.46 0.49 0.45 0.52 0.43 0.43 0.46 0.43 0.52 0.53 0.50 0.52 0.61 0.43 0.51 0.56 0.51 0.57 0.48 0.51 0.48 0.61 0.52 0.52 0.54 0.42 0.45 0.48 0.49 0.46 0.48
0.55 0.46 0.50 0.47 0.42 0.40 0.34 0.58 0.52 0.50 0.45 0.45 0.55 0.48 0.41 0.47 0.47 0.46 0.49 0.53 0.50 0.57 0.41 0.58 0.38 0.55 0.47 0.43 0.43 0.43 0.51 0.51
0.39 0.49 0.56 0.45 0.45 0.51 0.42 0.49 0.45 0.51 0.48 0.44 0.48 0.45 0.53 0.47 0.53 0.45 0.48 0.42 0.54 0.51 0.47 0.59 0.49 0.37 0.48 0.47 0.43 0.44 0.47 0.40
0.42 0.38 0.56 0.45 0.61 0.42 0.49 0.45 0.52 0.49 0.55 0.44 0.46 0.43 0.50 0.47 0.51 0.47 0.58 0.51 0.55 0.45 0.56 0.47 0.52 0.53 0.42 0.47 0.49 0.47 0.50 0.51
0.49 0.49 0.49 0.57 0.52 0.48 0.44 0.38 0.50 0.48 0.50 0.52 0.44 0.48 0.46 0.43 0.51 0.52 0.53 0.50 0.44 0.46 0.46 0.46 0.39 0.49 0.52 0.38 0.42 0.53 0.52 0.49
0.48 0.42 0.44 0.51 0.54 0.49 0.48 0.43 0.50 0.44 0.41 0.45 0.54 0.54 0.49 0.42 0.52 0.45 0.44 0.55 0.51 0.54 0.46 0.59 0.51 0.49 0.51 0.41 0.44 0.42 0.49 0.52
0.42 0.41 0.45 0.48 0.45 0.50 0.36 0.50 0.51 0.48 0.45 0.61 0.45 0.52 0.49 0.52 0.45 0.47 0.47 0.57 0.48 0.52 0.54 0.46 0.54 0.54 0.56 0.51 0.39 0.41 0.59 0.55

Здесь каждая колонка — это вероятность появления единицы в соответствующей позиции бита нонсе.

Теперь остается как-то отобразить получившуюся статистику в виде графиков. Для этого у меня есть другой скрипт plot.py

import sys
import os
import numpy as np
import matplotlib.mlab as mlab
import matplotlib.pyplot as plt

folder=""

#--------------------------------
args = sys.argv
if len(args)<2:
    print("Error: need argument name of folder with list of nonces")
    exit()

folder=args[1]
print( "Working on "" + folder +""" )
if os.path.isdir(folder)==False:
    print("Error: folder ""+folder+"" does not exist")
    exit()


stat_N=0
stat=[]
def init_stat():
    global stat
    global stat_N
    stat_N=0
    i=0
    while i<64:
       stat.append([])
       i=i+1

def draw_stat(start_bit,ax=None):
    print("draw_stat ",start_bit)
    save_single=0
    if ax is None:
        fig = plt.figure( figsize=(16,9))
        ax = fig.gca()
        save_single=1
    ax.set_yticks( np.arange( 0.0, 1.0, 0.1 ) )
    plt.title("Probability of specific bit in nonce")
    plt.ylabel("Probability")
    plt.xlabel("Every X-point presents group nonces averaged")
    plt.ylim(0.0,1.0)
    plt.grid()
    i=0
    while i<8:
        color="#"
        if i&1:
            color=color+"FF"
        else:
            color=color+"00"
        if i&2:
            color=color+"FF"
        else:
            color=color+"00"
        if i&4:
            color=color+"FF"
        else:
            color=color+"00"
        if i==7:
            color="#A0A0A0"
        ax.plot(stat[start_bit+i],color,label="bit"+str(start_bit+i) )
        i=i+1
    ax.legend(loc="upper left",ncol=2)
    #plt.show()
    if save_single :
        plt.savefig(folder+"/bit"+str(start_bit)+"-"+str(start_bit+7)+".png",dpi=300)

def draw_hist(start_bit,ax=None):
    print("draw_hist ",start_bit)
    save_single=0
    if ax is None:
        fig = plt.figure( figsize=(16,9))
        ax = fig.gca()
        save_single=1
    ax.set_xticks( np.arange( 0.0, 1.0, 0.1 ) )
    x=np.arange( 0.0, 1.0, 0.05 )
    plt.title("Probability Density of specific bit in nonce")
    plt.ylabel("Density")
    plt.xlabel("Probability")
    plt.grid()
    i=0
    max_val=0
    while i<8:
        histogram=[0]*20
        k=0
        stat_column=stat[start_bit+i]
        n=len(stat_column)
        while k<n:
            val=stat_column[k]
            idx=int(round(val*20))
            histogram[idx]=histogram[idx]+1
            if max_val<histogram[idx]:
                max_val=histogram[idx];
            k=k+1
        color="#"
        if i&1:
            color=color+"FF"
        else:
            color=color+"00"
        if i&2:
            color=color+"FF"
        else:
            color=color+"00"
        if i&4:
            color=color+"FF"
        else:
            color=color+"00"
        if i==7:
            color="#A0A0A0"
        ax.plot(x,histogram,color,label="bit"+str(start_bit+i) )
        i=i+1
    plt.ylim(0.0,max_val*1.2)
    ax.set_yticks( np.arange( 0.0, max_val*1.2, 1.0 ) )
    ax.legend(loc="upper right")
    #plt.show()
    if save_single :
        plt.savefig(folder+"/density"+str(start_bit)+"-"+str(start_bit+7)+".png",dpi=300)

num_bits=32
init_stat()
f = open(folder+"/stat.txt","r")
content = f.read().split("n")
for line in content:
    word = line.split(" ")
    nb=len(word)-1
    if nb==32 or nb==64:
        num_bits=nb
    else:
        break
    i=0
    while i<num_bits:
        stat[i].append( float(word[i]) )
        i=i+1
f.close

print("Num Bits in Nonce:",num_bits)
draw_hist(0)
draw_hist(8)
draw_hist(16)
draw_hist(24)
add_subplots = 0

fig = plt.figure( figsize=(16,9*num_bits/32))
ax1 = plt.subplot(221+add_subplots)
draw_hist(0,ax1)
ax2 = plt.subplot(222+add_subplots)
draw_hist(8,ax2)
ax3 = plt.subplot(223+add_subplots)
draw_hist(16,ax3)
ax4 = plt.subplot(224+add_subplots)
draw_hist(24,ax4)
plt.savefig(folder+"/density_all.png",dpi=300)

draw_stat(0)
draw_stat(8)
draw_stat(16)
draw_stat(24)
fig = plt.figure( figsize=(16,9*num_bits/32))
ax1 = plt.subplot(221+add_subplots)
draw_stat(0,ax1)
ax2 = plt.subplot(222+add_subplots)
draw_stat(8,ax2)
ax3 = plt.subplot(223+add_subplots)
draw_stat(16,ax3)
ax4 = plt.subplot(224+add_subplots)
draw_stat(24,ax4)
plt.savefig(folder+"/bits_all.png",dpi=300)

Теперь настало время рассмотреть эти графики. Если отобразить их все 32 на одной странице получится малопонятная каша. Поэтому скрипт строит 4 графика и каждый отображает статистику 8 бит. Так будет удобнее рассмотреть.

Приведу здесь всё:

Видно, что некоторые биты в нонсе биткоина не равновероятны в своем значении и графики смещены вниз. Значит значение бита все же немного более вероятно ноль, чем единица. Ниже графики распределения вероятности.

Здесь видно все то же — в среднем вероятность значения некоторых битов в найденых голден нонсе биткоина не равно 0.5, как я ожидал, но скорее смещено в сторону нуля. Особенно выделяются биты 1, 15, 22. С чем это связано, к сожалению не могу сказать. Тем не менее этот факт позволяет задуматься о перераспределении мощности майнеров по диапазонам значений более вероятных. Например, вот так: есть сто аппаратных майнеров (видеокарт или асиков), 65 майнеров отправляем на поиск нонсе со значениями бита 22 равному нулю и 35 майнеров майнят в диапазонах со значением бита 22 равным единице. Далее каждый выделенный диапазон можно разбить на более мелкие поддиапазоны согласно вероятности бита 15… и так далее. Идея в том, чтобы искать голден нонсе в более вероятных диапазонах сообразно последней накопленной статистике.

Далее возникла идея посмотреть статистику глубже, не только по 2000 последним блокам, но по всей истории блокчейна биткоина. Весь блокчейн уже почти 200Гигабайт, так что тут уже присутствуют все набившие оскомину термины «биткоин, блокчейн, бигдата».

Установил кошелек биткоина и выкачал весь блокчейн.

Далее использовал такой проект ^[1].
Этот проект позволяет скрипту на питоне пройтись по всему блокчейну и извлечь интересующие нас данные.

Немного изменил скрипт из примера, чтобы он писал статистику в текстовый файл. Теперь весь диапазон блоков около 530 тысяч разбит на группы по 1000 блоков. В каждом блоке смотрю среднюю вероятность значения бита нонсе.

import sys
sys.path.append('..')
from blockchain_parser.blockchain import Blockchain

stat_N=0
stat=[]
def init_stat():
    global stat
    global stat_N
    stat_N=0
    i=0
    while i<32:
       stat.append(0)
       i=i+1

def clear_stat():
    global stat
    global stat_N
    stat_N=0
    i=0
    while i<32:
       stat[i]=0
       i=i+1

def add_stat(nonce):
    global stat
    global stat_N
    stat_N=stat_N+1
    i=0
    while i<32:
        if nonce & (1<<i):
            stat[i]=stat[i]+1
        i=i+1

def print_stat():
    global stat
    global stat_N
    i=0
    while i<32:
        print(i," ",stat[i]/stat_N)
        i=i+1

def init_stat_file():
    txt=open("stat.txt","w")
    txt.close()

def write_stat():
    global stat
    global stat_N
    txt=open("stat.txt","a")
    i=0
    while i<32:
        s=stat[i]/stat_N
        txt.write("%.4f " % s )
        i=i+1
    txt.write("n")
    txt.close()

init_stat()
init_stat_file()

# Instantiate the Blockchain by giving the path to the directory 
# containing the .blk files created by bitcoind
blockchain = Blockchain(sys.argv[1])

height=0
# To get the blocks ordered by height, you need to provide the path of the
# `index` directory (LevelDB index) being maintained by bitcoind. It contains
# .ldb files and is present inside the `blocks` directory
for block in blockchain.get_ordered_blocks(sys.argv[1] + '/index', end=538000):
    print("")
    height=block.height
    print("height=%d" % (block.height) )
    print("header=",end='')
    arr=block.hex[:80]
    for a in arr:
        print(format(a,'02X'),end='')
    print("")
    print("hash  =%s" %  (block.hash) )
    hdr=block.header
    nonce=hdr.nonce
    print("nonce =", format(nonce,'08X'))
    add_stat(nonce)
    if stat_N==1000:
        write_stat()
        clear_stat()
    print("")

Этот скрипт так же генерирует файл статистики вероятности бита нонсе по всей истории блокчейна биткоин. Получается довольно интересная картина.

Вот как менялась со временем вероятность битов нонсе с нулевого по пятнадцатый:

А вот с шестнадцатого по тридцать первый бит нонсе:

Здесь каждая точка по горизонтали — это одна тысяча блоков в блокчейне и по этой тысяче считается средняя вероятность появления единицы в битовой позиции нонсе.

Честно говоря даже не знаю, как это можно прокомментировать. Временами биты в нонсе ой как не равновероятны. А если это так, то почему майнеры до сих пор просто перебирают нонсе? Возможно ли распределять мощности майнеров согласно найденой закономерности?

Если Вам интересны подобные изыскания, то можно еще почитать другие мои статьи:

1. Вероятностный метод майнинга Bitcoin ^[2]
2. Можно ли вычислять биткоины быстрее, проще или легче? ^[3]
3. Майнер Bitcoin на плате Марсоход3 ^[4]

Автор: nckma

Источник ^[5]