Деревья Меркла

Деревья Меркла представляют собой древовидную структуру, в которой каждый узел дерева представлен значением, являющимся результатом криптографической хеш-функции. Такие деревья имеют 3 типа узлов:
1. Листовые узлы (листья) - данные узлы находятся в самом низу и их значения это результат хеширования исходных данных. Количество листовых узлов ровняется количеству значений исходных данных.
2. Родительские узлы (ветви) - результат выполнения хеш-функции над двумя узлами ниже, это может быть как листовые узлы, так и родительские, в зависимости от размера дерева.
3. Корневой узел (корень) - находится в самом верху дерева и получается из хеша конкатенированных хешей двух родительских узлов, которые находятся под ним.

Применение

Деревья Меркла используются в разных сферах, если говорить про блокчейн, то яркий пример это сеть Bitcoin, в ней все хешируется в SHA-256. И применяется для проверки упрощенной верификации платежей, ведь для проверки не нужно вычислять все хеши, достаточно получить хеш корневого узла включающего все узлы до нужной транзакции. Такой подход значительно увеличивает производительность и пропускную способность сети.

Как использовать в Solidity ?

Если наш смарт-контракт подразумевает хранение большого кол-ва данных, которые необходимо будет валидировать, то использовать деревья Меркла не плохая мысль. К примеру в нашем проекте предусмотрен вайтлист, хранить тысячи адресов в смарт-контракте не самая оптимальная идея. Мы могли бы хранить корневой хеш всего в контракте, в контракт передавать только адрес и необходимые родительские узлы для вычислений, смарт-контракт сам будет высчитывать рут из переданных данных и сравнивать его с сохраненным корневым. Таким образом мы могли бы реализовать проверку валидности адреса кошелька на предмет минта в нужный момент. Давайте напишем на python функционал генерации такой структуры для вайтлиста.

По идее, для правильного формирования корневого дерева у нас должно быть 2ⁿ входящих параметров. Потому для корректной работы, недостающие узлы мы будем просто дублировать.

import json
import os
import secrets
from coincurve import PublicKey
from pprint import pprint as pp
from sha3 import keccak_256
os.system("clear")

def getPK() -> None:
    return PublicKey.from_valid_secret(keccak_256(secrets.token_bytes(32)).digest()).format(compressed=False)[1:]

def addressGenerate(total: int) -> None:
    address_list = dict()
    address_list = {
        "addresses": list("0x" + keccak_256(getPK()).digest()[-20:].hex() for x in range(0,total)),
        "hashes": []
    } 
    with open("./address_list.json", "w") as fp:
        json.dump(address_list, fp,indent=4)
    print(f"\nADDRESS LIST:\n" + "\n".join(address_list['addresses']))

def getAddressList() -> None:
    with open("./address_list.json", "r", encoding='utf-8') as fp:
        return json.load(fp)

def keccak256(hc: list) -> str:
    hs = keccak_256()
    hs.update("".join(hc).encode('utf-8'))
    return hs.hexdigest()

def merkleTreeEncode(al: list) -> list:
    al = al['addresses']
    hash_candidate, hash_tree, loop = list(), list(), 0

    while(True):
        if loop == len(hash_tree):
            hash_tree.append(list())
        hash_candidate.append(al.pop())
        if (len(hash_candidate) == 1 and loop == 0) or (len(hash_candidate) == 2 and loop > 0):
            hash_tree[loop].append(keccak256(hash_candidate))
            hash_candidate = list()
        elif len(hash_candidate) == 1 and len(al) == 0 and loop > 0:
            hash_candidate.append(hash_candidate[0])
            hash_tree[loop].append(keccak256(hash_candidate))
        if len(al) == 0:
            if len(hash_tree[loop]) > 1:
                al = list(hash_tree[loop])
                hash_candidate = list()
                loop += 1
            else:
                break
    
    data = json.load(open("address_list.json", "r"))
    data['hashes'] = hash_tree
    json.dump(data, open("address_list.json", "w"), indent=4)
    return hash_tree

def merkleTreeDependens(address: str)-> dict:
    address_list = getAddressList()
    try:
        index = address_list['addresses'].index(address)
    except Exception as e:
        print('invalid address')
        return []

    data = {}
    data['index'] = index
    data['hash'] = address_list['hashes'][0][index]
    data['root'] = address_list['hashes'][len(address_list['hashes'])-1]

    out = []
    first = True
    total = len(address_list['hashes'][0])

    for level in address_list['hashes']:
        if len(level) == 1:
            break
        if len(level) % 2 != 0:
            level.append(level[len(level)-1])
        if first:
            if (index+1) % 2 == 0:    
                out.append(level[index-1])
            else:
                out.append(level[index+1])
            first = False
        else:
            if (index+1) % 2 == 0:    
                out.append(level[index-1])
            else:
                out.append(level[index+1])
        index = int((index) / 2)
        total = total/2
    data['proof'] = out
    return data



len_address = 15
try:
    adress_list = getAddressList()
    hashes = merkleTreeEncode(adress_list)
except Exception as e:
    print(e)
    addressGenerate(len_address)
    adress_list = getAddressList()
    hashes = merkleTreeEncode(adress_list)

hash_root = hashes[len(hashes)-1][0]
print(f"root hash: {hash_root} \n")


dep = merkleTreeDependens("0xcc28d2781aff9db54861f4a29624eefdfff0d6ec")
pp(dep)

Данный пример сформирует json файл со структурой дерева Меркла, который можно использовать для тестирования валидации на стороне смарт-контракта. По сути все что нам остается это отправить из сформированного дерева лишь проверяемый адрес и узлы необходимые для вычислений корневого хеша.

github