Как построить минимальное доказательство проверки двух листьев данного Дерева Меркла? ⇐ Python

[Anonymous]

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

Предположим, мы создаем листья следующим образом:
s = f"AliceDoe-MerkleTree"

h = sha256(s.encode()).hexdigest()

fst = int(h[0], 16) # 3 = 0011
snd = (fst + 1) % 16 # 4 = 0100

leaves = [sha256("rest of the leaves do not matter".encode()).hexdigest()] * 16
leaves[fst] = sha256("Alice".encode()).hexdigest()
leaves[snd] = sha256("Doe".encode()).hexdigest()

В результате получится дерево Меркла (изображение дерева), в котором оранжевые узлы являются частью минимального доказательства.
Теперь мы построим дерево Tree = MerkleTree(leaves).
Теперь мы можем легко генерировать доказательства для отдельных листьев следующим образом:
proof_fst = tree.proof(fst)
"""
0010|04464ac8b96c1c536741ce95b25341ed1d68c57a580e587fef7cf2ba51023499
000|1168a34444bab6d815a05bbab5bb96dbfa36a1e0f00e323777c7cc4d670f54cc
01|221907783a1c78f8e4a9885e800ea1296f1508f110bd26491b227487a88cdb65
1|a3887a791bd931add8d9acc4083fdae3a9443673ec10488ecd5303d26578e356
"""

proof_snd = tree.proof(snd)
"""
0101|04464ac8b96c1c536741ce95b25341ed1d68c57a580e587fef7cf2ba51023499
011|1168a34444bab6d815a05bbab5bb96dbfa36a1e0f00e323777c7cc4d670f54cc
00|2add97fdc2b4fbf2c483f2f5647e133017ac574217291d29c06ee6457fb90eb6
1|a3887a791bd931add8d9acc4083fdae3a9443673ec10488ecd5303d26578e356
"""

Моя проблема заключается в том, что с учетомproof_fst иproof_snd (а также, возможно, fst и snd), я хочу создать список min_proof: List[Tuple[str,str]]. В этом случае такой список будет выглядеть так (оранжевые узлы на схеме выше):
0010|...
0101|...
000|...
011|...
1|...

ПРИМЕЧАНИЕ. В полученном минимальном доказательстве нет лишних узлов! В этом случае обратите внимание, что узлы «01» и «00» отсутствуют в конечном результате. Их можно получить из других.
Этот список вместе со знанием fst и snd (и их хешей) позволяет мне правильно регенерировать корень дерева Меркла и позволяет мне проверить существование обоих этих листьев в дереве, сравнивая восстановленный корень с сохраненным корнем.
Мне нужна помощь в создании списка min_proof.
Ниже приведен минимальный рабочий пример:
from hashlib import sha256

class MerkleTree:
def __init__(self, leaves):
self.leaves = leaves
self.root = self.build_tree(self.leaves)

def build_tree(self, leaves):
self.tree_levels = [leaves]
curr_lvl = leaves

level = 0
while len(curr_lvl) > 1:
next_level = []
for i in range(0, len(curr_lvl), 2):
left = curr_lvl
right = curr_lvl[i + 1]
parent_hash = sha256((left + right).encode()).hexdigest()
next_level.append(parent_hash)
curr_lvl = next_level
self.tree_levels.append(curr_lvl)
level += 1
root = curr_lvl[0]
return root

def proof(self, idx):
proof = []
# iterate over levels starting from leaves, and ignoring root
for level in self.tree_levels[:-1]:
sib_idx = idx + 1 if idx % 2 == 0 else idx - 1
sib_hash = level[sib_idx]
proof.append((sib_idx, sib_hash))
idx //= 2 # goto parent
return proof

@staticmethod
def verify(root_hash, proof, leaf_hash, idx):
current_hash = leaf_hash
for _, sibling_hash in proof:
if idx % 2 == 0:
current_hash = sha256((current_hash + sibling_hash).encode()).hexdigest()
else:
current_hash = sha256((sibling_hash + current_hash).encode()).hexdigest()
idx //= 2

return current_hash == root_hash

if __name__ == "__main__":
s = f"AliceDoe-MerkleTree"

h = sha256(s.encode()).hexdigest()

fst = int(h[0], 16)
fst_bin = format(fst, "04b")
fst_hash = sha256("Alice".encode()).hexdigest()

snd = (fst + 1) % 16
snd_bin = format(snd, "04b")
snd_hash = sha256("Doe".encode()).hexdigest()

leaves = [sha256("whatever".encode()).hexdigest()] * 16
leaves[fst] = fst_hash
leaves[snd] = snd_hash

tree = MerkleTree(leaves)

proof_fst = tree.proof(fst)
for lvl, (i, h) in enumerate(proof_fst):
bs = format(i, f"0{4 - lvl}b")
proof_fst[lvl] = (bs, h)

proof_snd = tree.proof(snd)
for lvl, (i, h) in enumerate(proof_snd):
bs = format(i, f"0{4 - lvl}b")
proof_snd[lvl] = (bs, h)

# TODO: generate min_proof: List[Tuple[str, str]]
min_proof = []

for bs, h in min_proof:
print(f"{bs}|{h}")



Подробнее здесь: https://stackoverflow.com/questions/791 ... -merkle-tr