63 lines
2.3 KiB
Python
63 lines
2.3 KiB
Python
import hashlib
|
|
from typing import List, Tuple, Any
|
|
|
|
|
|
class MerkleLedger:
|
|
def __init__(self):
|
|
self._leaves: List[bytes] = []
|
|
|
|
def add_entry(self, data: Any) -> int:
|
|
b = str(data).encode("utf-8")
|
|
self._leaves.append(b)
|
|
return len(self._leaves) - 1
|
|
|
|
def _hash(self, data: bytes) -> bytes:
|
|
return hashlib.sha256(data).digest()
|
|
|
|
def root(self) -> bytes:
|
|
if not self._leaves:
|
|
return b""
|
|
nodes = [self._hash(l) for l in self._leaves]
|
|
while len(nodes) > 1:
|
|
new_nodes: List[bytes] = []
|
|
for i in range(0, len(nodes), 2):
|
|
left = nodes[i]
|
|
right = nodes[i + 1] if i + 1 < len(nodes) else left
|
|
new_nodes.append(self._hash(left + right))
|
|
nodes = new_nodes
|
|
return nodes[0]
|
|
|
|
def get_proof(self, index: int) -> List[Tuple[str, str]]:
|
|
# Return a simple list of (hash_hex, side) for verification
|
|
if index < 0 or index >= len(self._leaves):
|
|
return []
|
|
path: List[Tuple[str, str]] = []
|
|
# Build a simple merkle tree on the fly for proof generation
|
|
level = [self._hash(l) for l in self._leaves]
|
|
idx = index
|
|
while len(level) > 1:
|
|
next_level: List[bytes] = []
|
|
for i in range(0, len(level), 2):
|
|
left = level[i]
|
|
right = level[i + 1] if i + 1 < len(level) else left
|
|
combined = self._hash(left + right)
|
|
next_level.append(combined)
|
|
if i == idx or i + 1 == idx:
|
|
sibling = right if i == idx else left
|
|
side = "right" if i == idx else "left"
|
|
path.append((sibling.hex(), side))
|
|
idx = len(next_level) - 1
|
|
level = next_level
|
|
return path
|
|
|
|
def verify_proof(self, leaf_index: int, data: Any, proof: List[Tuple[str, str]], root: bytes) -> bool:
|
|
current = hashlib.sha256(str(data).encode("utf-8")).digest()
|
|
idx = leaf_index
|
|
for p_hash_hex, side in proof:
|
|
sibling = bytes.fromhex(p_hash_hex)
|
|
if side == "right":
|
|
current = hashlib.sha256(current + sibling).digest()
|
|
else:
|
|
current = hashlib.sha256(sibling + current).digest()
|
|
return current == root
|