Merkle root

Merkle root (Меркъл корен) е 32-байтов хеш, който представя всички трансакции в блока. Майнърът го записва в заглавието. Ако се промени някоя трансакция в блока, коренът вече не съвпада и блокът е невалиден. По този начин Merkle root свързва заглавието с трансакциите, които описва.

Как се строи Merkle root?

Коренът се строи от идентификаторите на трансакциите, тоест от txid-тата. Хешират се по двойки, ред по ред, докато остане един хеш:

1. Вземете txid-тата в реда им в блока.
2. Съединете всяка двойка и прекарайте съединените байтове през HASH256, тоест SHA-256, приложен два пъти.
3. Ако остане елемент без двойка, хеширайте го с него самия.
4. Повторете стъпки 2 и 3 върху новия списък, докато остане един хеш.

Как изглежда пример с четири трансакции?

Блок 100,000 има четири трансакции, което го прави удобен пример за проверка. Txid-тата му, в реда на explorer, са:

8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87
fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4
6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4
e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d

Съединете първите две и последните две. Хешът на първата двойка е ccdafb73d8dcd0173d5d5c3c9a0770d0b3953db889dab99ef05b1907518cb815. Хешът на втората двойка е 8e30899078ca1813be036a073bbf80b86cdddde1c96e9e9c99e9e3782df4ae49. Хеширайте тези два хеша заедно и Merkle root е f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766, което съвпада със заглавието на блок 100,000. И двата хеша на двойките са показани тук в реда на explorer.

Кодът по-долу прави същите стъпки за всеки списък от txid-та:

import hashlib

def hash256(data: bytes) -> bytes:
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def merkle_root(txids: list[str]) -> str:
    # На вход: ред на explorer. При хеширане: естествен ред на байтовете. На изход: ред на explorer.
    level = [bytes.fromhex(t)[::-1] for t in txids]
    while len(level) > 1:
        if len(level) % 2:              # нечетен брой: последният елемент се хешира сам със себе си
            level.append(level[-1])
        level = [hash256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
    return level[0][::-1].hex()

txids = [
    "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
    "fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
    "6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
    "e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
]
print(merkle_root(txids))  # f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

Тук има два реда на байтовете, а най-честата грешка е да ги смесите. Txid-тата се показват в реда на explorer, но преди хеширане трябва да се обърнат в естествения ред. Коренът излиза в естествен ред, а за да го сравните с explorer, го обръщате отново. Страницата за реда на байтовете обяснява правилото.

Блок с една единствена трансакция има Merkle root, равен на txid-то на тази трансакция. Не се налага сдвояване.

Защо да не се хешират всички трансакции наведнъж?

Може да се хешират всички txid-та в един дълъг низ. Това дава отпечатък, но без останалите не доказва нищо за една трансакция. За да проверите, че дадена трансакция е в блока, ви трябват всички други txid-та.

Дървото решава проблема. За да докажете, че дадена трансакция е в блока, ви трябват само съседните хешове по пътя ѝ до корена. Този път се нарича Merkle доказателство (merkle proof). На всяка стъпка текущият хеш се съчетава с един съсед, отляво или отдясно, и двата се хешират заедно.

Блок 562,943 има 2,352 трансакции. Ето Merkle доказателството, че трансакция f66f6ab609d242edf266782139ddd6214777c4e5080f017d15cb9aa431dda351 е в него. Страницата на трансакцията в нашия explorer показва в кой блок е. Съседните хешове по-долу са в естествения ред на байтовете, както излизат от хеш функцията:

50ba87bdd484f07c8c55f76a22982f987c0465fdc345381b4634a70dc0ea0b38 left
96b8787b1e3abed802cff132c891c2e511edd200b08baa9eb7d8942d7c5423c6 right
65e5a4862b807c83b588e0f4122d4ca2d46691d17a1ec1ebce4485dccc3380d4 left
1ee9441ddde02f8ffb910613cd509adbc21282c6e34728599f3ae75e972fb815 left
ec950fc02f71fc06ed71afa4d2c49fcba04777f353a001b0bba9924c63cfe712 left
5d874040a77de7182f7a68bf47c02898f519cb3b58092b79fa2cff614a0f4d50 left
0a1c958af3e30ad07f659f44f708f8648452d1427463637b9039e5b721699615 left
d94d24d2dcaac111f5f638983122b0e55a91aeb999e0e4d58e0952fa346a1711 left
c4709bc9f860e5dff01b5fc7b53fb9deecc622214aba710d495bccc7f860af4a left
d4ed5f5e4334c0a4ccce6f706f3c9139ac0f6d2af3343ad3fae5a02fee8df542 left
b5aed07505677c8b1c6703742f4558e993d7984dc03d2121d3712d81ee067351 left
f9a14bf211c857f61ff9a1de95fc902faebff67c5d4898da8f48c9d306f1f80f left

Започнете от txid-то, обърнато в естествения ред, и го хеширайте с всеки съсед по ред. Всеки ред казва дали съседът е вляво или вдясно, така че двата байтови низа се съединяват в този ред. След дванадесетата стъпка трябва да стигнете до Merkle root на блока, 17663ab10c2e13d92dccb4514b05b18815f5f38af1f21e06931c71d62b36d8af, в реда на explorer.

Дванадесет съседа покриват 2,352 трансакции, защото 2 на степен 12 е 4,096. Доказването на една трансакция отнема 12 × 32 = 384 байта. Изброяването на всичките 2,352 txid-та би отнело 2,352 × 32 = 75,264 байта.

Защо това помага на леките портфейли?

Пълният нод пази всеки блок. Лекият портфейл пази само 80-байтовите заглавия и пита пълен нод за Merkle доказателството на всяка трансакция, която го интересува. Проверява го спрямо корена в заглавието. Така се потвърждава, че едно плащане е в блок, без да се изтегля самият блок. За какво точно пази пълният нод, вижте страницата за нода.

Защитава ли коренът от промени?

Да. Коренът е обвързан с точния списък от трансакции. Променете една трансакция, добавете една или пренаредете списъка и коренът се променя. Заглавието тогава посочва различен корен, а с него се променя и хешът на блока.

Тъй като нечетният елемент се хешира сам със себе си, два различни списъка могат да дадат един и същ корен. Списък, който завършва с копие на последната си трансакция, прилича на списъка без това копие. Тази слабост е известна като CVE-2012-2459. Bitcoin Core я проверява и отхвърля блок, с този модел, като причината е bad-txns-duplicate (validation.cpp).

Какво следва?

Следва времето, полето, в което майнърът записва текущото време.