Published Date : 2021年7月21日5:40

009 Pythonで遊ぶ
009 Playing with Python


This blog has an English translation


ニコニコ動画にアップした動画のまとめ記事です。

This is a summary blog post about a video I uploaded to NicoNico.

細かい部分は動画を参考にしてください。

Please refer to the video for details.


目次

Table of Contents




① 動画の説明
① Video Description



前回の続きです。

Continued from last time.

以前のブログ[https://akasatanahama.com/posts/190]で成功する確率というものを紹介しました。

In my previous blog [https://akasatanahama.com/posts/190], I introduced the probability of success.

これで0.7%を計算すると約974回ほど試行するとほぼ100%成功するといえます。

If we calculate 0.7%, we can say that we will succeed almost 100% after about 974 attempts.

29/4096
0.007080078125

p = 29/4096
p
0.007080078125
n = 100
pOfS = (1-((1-p)**n)) * 100
print(f"{pOfS:.2f}%")

n = 1
pOfS = (1-((1-p)**n)) * 100
while pOfS < 99.9:
    pOfS = (1-((1-p)**n)) * 100
    n += 1
print(f"It takes {n} trials to raise the probability of {p*100:.2f}% to {pOfS:.2f}%.")

しかしsha256のハッシュ値の256ビット、16進数表記で[0000000000000000000000000000000000000000000000000000000000000000]から[ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff]までの、

However, 256 bits of the hash value of sha256, from [0000000000000000000000000000000000000000000000000000000000000000] to [ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff] in 16 notation,

115792089237316195423570985008687907853269984665640564039457584007913129639936通りを考えたらいかにノンスを見つけるのが難しいか想像できると思います。

If you think about 115792089237316195423570985008687907853269984665640564039457584007913129639936 ways, you can imagine how difficult it is to find Nonce.

>>> 2**256
115792089237316195423570985008687907853269984665640564039457584007913129639936

少し本題から話が逸れますが、この数がどれだけ大きいかを理解する為に日本の数の単位をこの値に当てはめてみました。

Let me get off the subject a little bit, but in order to understand how big this number is, I decided to apply the Japanese number unit to this value.

[さらば青春の光]のコントネタで有名な[阿僧祇(あそうぎ)]や[那由多(なゆた)]、[不可思議(ふかしぎ)]を越えて[10の72乗]付近まであります。

It goes over [阿僧祇(asougi)], [那由多(nayuta)], and [不可思議(fukashigi)] famous for sketch of [Saraba Seishun No Hikari (Japanese comedy duo)], and is near [10 to the 72 power].

"""
無量大数	むりょうたいすう	10の68乗
不可思議	ふかしぎ	10の64乗
那由多	なゆた	10の60乗
阿僧祇	あそうぎ	10の56乗
恒河沙	ごうがしゃ	10の52乗
極	ごく	10の48乗
載	さい	10の44乗
正	せい	10の40乗
潤	かん	10の36乗
溝	こう	10の32乗
穣	じょう	10の28乗
坙	し	10の24乗
垓	がい	10の20乗
京	けい/きょう	10の16乗
兆	ちょう	10の12乗
億	おく	10の8乗
万	まん	10の4乗
千	せん	10の3乗
百	ひゃく	10の2乗
十	じゅう	10の1乗
一	いち	10の0乗
"""
japanese_kurai = ['万', '億', '兆', '京', '垓', '坙', '穣', '溝', '潤', '正', '載', '極', '沙河恒', '祇僧阿', '多由那', '議思可不', '数大量無', ' ', ' ', ' ']
new_str = ""
counter = 0
for i,c in enumerate(reversed(str(2**256))):
    new_str += c
    if (i+1) % 4 == 0:
            new_str += japanese_kurai[counter]
            counter += 1

new_str[::-1]
'11 5792 0892無量大数3731不可思議6195那由多4235阿僧祇7098恒河沙5008極6879載0785正3269潤9846溝6564穣0564坙0394垓5758京4007兆9131億2963万9936'

話は戻り、例えば難易度が1の時の目標値は整数で[26959535291011309493156476344723991336010898738574164086137773096960]となります。

Back to the topic, for example, when the difficulty level is 1, the target value is an integer [26959535291011309493156476344723991336010898738574164086137773096960].

この値で先ほどの確率を計算する方法で試すと100億分の2となります。

If you try to calculate the probability with this value, you get 2 in 10 billion.

total_pattern = 2**256
diff1_pattern = 26959535291011309493156476344723991336010898738574164086137773096960 - 1

p = diff1_pattern / total_pattern

print(f"{p:.32f}")
0.00000000023282709094019082840532

計算の結果、このように100億回試してもまだ外れる可能性があるのです。

As you can see from the calculation, there is a 10% chance of still failing after 10 billion tries.

n = 1000000000
pOfS = (1-((1-p)**n)) * 100
print(f"It takes {n:,} trials to raise the probability of {p*100:.12f}% to {pOfS:.2f}%.")
It takes 1,000,000,000 trials to raise the probability of 0.000000023283% to 20.77%.

n = 5000000000
pOfS = (1-((1-p)**n)) * 100
print(f"It takes {n:,} trials to raise the probability of {p*100:.12f}% to {pOfS:.2f}%.")
It takes 5,000,000,000 trials to raise the probability of 0.000000023283% to 68.78%.

n = 10000000000
pOfS = (1-((1-p)**n)) * 100
print(f"It takes {n:,} trials to raise the probability of {p*100:.12f}% to {pOfS:.2f}%.")
It takes 10,000,000,000 trials to raise the probability of 0.000000023283% to 90.25%.

勿論ある種のくじ引きのようなものなので、運よく目標値を下回るハッシュ値を導くノンスが1秒で見つかるかもしれません。

Of course, it's kind of a lottery, so you might be lucky enough to find a nonce in a second or two that leads to a hash value below your target.

しかし平均的には膨大な計算量がかかることは容易に想像できると思います。

But it's easy to imagine that, on average, it takes a lot of computation.

ビットコインエクスプローラーのサイト を見てみましょう。

Let's look at the site of Bitcoin Explorer.

そして難易度とは難易度が1の時のビットから導いた目標値をその時のビットで導いた目標値で割った値になります。

And the difficulty is the value obtained by dividing the target value derived from the bits when the difficulty is 1 by the target value derived from the bits at that time.

難易度が1の時のビットは[0x1d00ffff]で目標値は[0x00000000FFFF0000000000000000000000000000000000000000000000000000]です。

When the difficulty is 1, the bits is [0x1d00ffff] and the target value is [0x00000000FFFF0000000000000000000000000000000000000000000000000000].

整数に直すと[26959535291011309493156476344723991336010898738574164086137773096960]です。

Converted to an integer, it is [26959535291011309493156476344723991336010898738574164086137773096960].

そして直近の[690000]ブロックのビットは[0x171398ce]で目標値は[0x0000000000000000001398ce0000000000000000000000000000000000000000]です。

And the bits of the recently created [690000] block is [0x171398ce] and the target value is [0x0000000000000000001398ce0000000000000000000000000000000000000000].

整数に直すと[1877009475827353279654828838027187714710153476809162752]です。

Converted to an integer, it is [1877009475827353279654828838027187714710153476809162752].

[26959535291011309493156476344723991336010898738574164086137773096960 / 1877009475827353279654828838027187714710153476809162752]が難易度となります。

In other words, [26959535291011309493156476344723991336010898738574164086137773096960 divided by 1877009475827353279654828838027187714710153476809162752] is the difficulty level.

値は[14363025673659.965]となるはずです。

Its value will be [14363025673659.965].

サイトによってはこの値を四捨五入していたり、小数点以下の桁数を調整していたりしています。

Some sites round this value or adjust the number of decimal places.

二つのビットコインエクスプローラーのサイトを見てみましょう。

Take a look at the two Bitcoin Explorers sites.

bitcoinexplorer.org, explorer.bitcoin.com

つまりこの値が大きいほど採掘にかかる時間がかかると言えます。

So the higher the value, the longer it takes to mine.

この難易度を直近の平均計算時間等を考慮して2週間毎に変更してノンスを見つける時間を調整しています。

This difficulty is changed every 2 weeks considering the latest average calculation time, etc., and the time to find Nonce is adjusted accordingly.

ビットコインウィキに書かれている事を参考にしてみましょう。

Let's refer to what is written on the bitcoin wiki.

難易度についても説明されているので、参考にしてください。

It also explains the difficulty, so please refer to it.

ビットの4バイト目をインデックス、3バイト目から1バイト目を係数とした方程式があります。

There is a equation in which the fourth byte of the bits is an index and the third to first bytes are coefficients.

Target = coefficient * 2 ^ ( 8 * (index — 3) )

この方程式を使ってビットから目標値を計算します。

This equation is used to calculate the target value from bits.

ではPythonを使ってビットから目標値と難易度を計算してみましょう。

Let's use Python to calculate the target and difficulty from bits.

690000番目のブロックで検証してみましょう。

Let's examine block 690000th.

690000番目のブロックのビット

Bits in the 690000th block

0x171398ce

そして、方程式は以下の通りでしたね。

And the equation was as follows.

Target = coefficient * 2 ^ ( 8 * (index — 3) )

690000番目のブロックのビットの値を式に当てはめると以下になります。

The value of the bits in the 690,000th block can be applied to the equation as follows.

0x1398ce * 2 ^ (0x08 * (0x17–0x03) )

まず690000番目のブロック(自分の好きな番号のブロックを選んで下さい。)のビットを変数に格納します。(pythonではint型になります。)

First, we store the bits of the 690,000th block (Choose the block number you like.) in a variable. (In python it is of type int.)

bits = 0x171398ce
bits
387160270
hex(bits)
'0x171398ce'

先ほどの方程式に倣ってこのビットの値をインデックスと係数に分けます。

Divide the value of this bits into an index and a coefficient as in the previous equation.

idx = hex(bits)[2:4]
idx
'17'
coef = hex(bits)[-6:]
coef
'1398ce'

二つの値を方程式に当てはめます。

Apply the two values to the equation.

target = int(coef, 16) * 2 ** (8 * (int(idx, 16) - 3))
target
1877009475827353279654828838027187714710153476809162752

せっかくなので、前回の動画で紹介したバイナリ操作で同じ計算を行いましょう。

Let's do the same calculation with the binary operation introduced in my previous video.

int(idx, 16)
23
idx = bits >> 24
idx
23

右シフトでどんなことが行われたかをPythonを使って確認してみてください。詳しい内容は前回の動画を参考にしてください。

Use Python to see what happens in the right shift. Please refer to my previous video for details.

16進数表記では2桁で1バイト(8ビット)なので、4バイトあるビットを右に24ビットシフトすると、上位の1バイトを残すことできます。

In hexadecimal notation, 2 digits are 1 byte (8 bits), so if you shift the bits that is 4 bytes to the right by 24 bits, you can leave the upper 1 byte.

test_bits = 0xff000000
print(f'{test_bits:08x}')
ff000000
int('0xff', 16)
255
int('0x100', 16)
256
2 ** 8
256
print(f'{test_bits >> 8:08x}')
00ff0000
print(f'{test_bits >> 16:08x}')
0000ff00
print(f'{test_bits >> 24:08x}')
000000ff

そして、4バイトのビットに対して3バイトのビットでアンド演算を行うことで3バイト目から1バイト目を残します。

Then, the third byte to the first byte are left by performing an AND operation on bits of the value of 3 bytes for bits of 4 bytes.

int(coef, 16)
1284302
coef = bits & 0xffffff
coef
1284302

この作業も前回の動画で紹介しているので、そちらを参考にしてください。

This task is also introduced in my previous video, so please refer to it.

こちらもAND演算でのマスクでどんなことが行われたかをPythonを使って確認してみてください。

Again, use Python to see what happens with masks using the AND operation.

test_bits = 0x00000001
mask = 0xffffffff
test_bits & mask
1
print(f'{test_bits & mask:08x}')
00000001
test_bits = 0x10101010
mask = 0x00ffffff
print(f'{test_bits & mask:08x}')
00101010
test_bits = 0x12345678
mask = 0xffffff
print(f'{mask:08x}')
00ffffff
print(f'{test_bits & mask:08x}')
00345678

そして、64桁の16進数表記で計算結果を表示させます。

The calculation result is displayed in 64 digit hexadecimal notation.

target_hexstr = '%064x' % (coef * (1 << (8*(idx - 3))))
target_hexstr
'0000000000000000001398ce0000000000000000000000000000000000000000'

因みに前回の動画でも説明しましたが、1ビットに対して左シフトをN回行えば、2のN乗になります。

By the way, as I explained in my previous video, if you shift 1 bit to the left N times, you get 2 raised to the power of N.

f'{(0b00000001 << 1):08b}'
'00000010'

int(f'{(0b00000001 << 1):08b}', 2)
2

f'{(0b00000001 << 2):08b}'
'00000100'

int(f'{(0b00000001 << 2):08b}', 2)
4

つまりインデックス側の計算(1 << (8*(idx - 3)))は2の(インデックス側の計算結果(8*(idx - 3)))乗となります。

That is, the calculation on the index side (1 << (8*(idx - 3))) is 2 raised to the power of (Calculation result of the index side (8*(idx - 3))).

1 << (8*(idx - 3))
1461501637330902918203684832716283019655932542976

2 ** (8*(idx - 3))
1461501637330902918203684832716283019655932542976

これでビットから目標値を算出できました。

The target value can now be calculated from the bits.

int(target_hexstr, 16)
1877009475827353279654828838027187714710153476809162752
target == int(target_hexstr, 16)
True

ノンスを見つける作業はバイナリ計算で行ったほうが効率が良いので、コーデックスモジュールをインポートして目標値をPythonのバイナリオブジェクトにしてみましょう。

Since it is more efficient to use binary computations to find the nonce, let's import a codecs module and make the target a Python binary object.

import codecs
target_bytes = codecs.decode(target_hexstr, "hex")
target_bytes
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x13\x98\xce\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

では690000番目のブロックの難易度を求めてみましょう。

Let's calculate the difficulty of block 690,000.

目標値を求める関数を作成しておきましょう。

Create a function that calculates the target value.

def calc_target(bits):
    idx = bits >> 24
    coef = bits & 0xffffff
    target_hexstr = '%064x' % (coef * (1 << (8*(idx - 3))))
    target_bytes = codecs.decode(target_hexstr, "hex")
    return (target_hexstr, target_bytes)


diff1_bits = 0x1d00ffff

diff1_target_hexstr, diff1_target_bytes = calc_target(diff1_bits)

diff1_target_hexstr
'00000000ffff0000000000000000000000000000000000000000000000000000'

diff1_target_bytes
b'\x00\x00\x00\x00\xff\xff\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

これで難易度を計算することができました。直観的に現在の目標値が小さくなれば難易度の値は大きくなることが理解できると思います。

Now you can calculate the difficulty. Then, you can intuitively understand that the difficulty increases when the current target value decreases.

int(diff1_target_hexstr, 16) / int(target_hexstr, 16)
14363025673659.965

では690000番目のブロックのヘッダーの値からノンスの値が正しいかどうかを確かめてみましょう。

Let's see if the nonce value is correct from the header value in block 690000th.

import codecs
import struct
from hashlib import sha256
version = 536870916
previousblockhash = "00000000000000000007f98ab827c3f8acb26be6349a43aca9d9b338290c29dc"
merkleroot = "9d467c7013651310f7215b170d706a5ba5220885a59a6722826174880b5f70ad"
time_stamp = 1625643787  
bits = 0x171398ce
nonce = 3902747927

structモジュールやcodecsモジュールを使用してバイト列を連結していきます。

Concatenate the bytes using the struct and codecs modules.

その際にはバイトオーダーをリトルエンディアンにしてください。

Make the byte order little-endian when concatenating bytes.

structのpackメソッドの[<]はリトルエンディアンを、[L]は4バイトのインテジャーを表しています。

In the struct's pack method, [<] stands for little-endian, and [L] stands for 4-byte integer.

何度も言いますが、バイト列のまま連結する時はバイトオーダーに気を付けて下さい。

As I have said many times, please be careful about the byte order when you concatenate the bytes.

大半の人達が使用しているPCのCPUはIntel製なので、リトルエンディアンで計算しましょう。

Most people use Intel CPUs, so let's do little-endian calculations.

他のCPUを使っていて、バイトオーダーが気になる人は各自で調べてください。

If you are using a different CPU and are concerned about the byte order, please check it by yourself.

header = (struct.pack("<L", version) + codecs.decode(previousblockhash, "hex")[::-1] +
            codecs.decode(merkleroot, "hex")[::-1] + struct.pack("<LLL", time_stamp, bits, nonce))
hash_value = sha256(sha256(header).digest()).digest()

print('%064x' % (int.from_bytes(hash_value, "little")))
00000000000000000002a23d6df20eecec15b21d32c75833cce28f113de888b7

計算されたハッシュ値が正しいものか確認してみましょう。

Let's see if the calculated hash value is correct.

https://bitcoinexplorer.org/block-height/690000

target_hexstr, target_bytes = calc_target(bits)

target_hexstr
'0000000000000000001398ce0000000000000000000000000000000000000000'
target_bytes
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x13\x98\xce\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'


hash_value[::-1] < target_bytes
True
print(f'nonce -> {nonce}\nhash  -> {int.from_bytes(hash_value, "little"):064x}')
nonce -> 3902747927
hash  -> 00000000000000000002a23d6df20eecec15b21d32c75833cce28f113de888b7


以上です。お疲れ様です。

That's all. Thank you for your hard work.