"""Synthetic Merkle-branch exercise. Not a Core proof parser or block validator."""
import hashlib,json,struct
def double(data):return hashlib.sha256(hashlib.sha256(data).digest()).digest()
def root(leaves):
 if not leaves or any(len(x)!=32 for x in leaves):raise ValueError("32-byte leaves required")
 level=list(leaves);mutated=False
 while len(level)>1:
  if any(level[i]==level[i+1] for i in range(0,len(level)-1,2)):mutated=True
  if len(level)%2:level.append(level[-1])
  level=[double(level[i]+level[i+1]) for i in range(0,len(level),2)]
 return level[0],mutated
def branch(leaves,index):
 if index<0 or index>=len(leaves):raise ValueError("index outside leaves")
 root(leaves);result=[];level=list(leaves)
 while len(level)>1:
  if len(level)%2:level.append(level[-1])
  result.append(dict(side="left" if index%2 else "right",sibling_internal_hex=level[index^1].hex()))
  level=[double(level[i]+level[i+1]) for i in range(0,len(level),2)]
  index//=2
 return result
def fold(leaf,path):
 if len(leaf)!=32:raise ValueError("bad leaf")
 value=leaf
 for step in path:
  sibling=bytes.fromhex(step["sibling_internal_hex"])
  if len(sibling)!=32 or step["side"] not in ["left","right"]:raise ValueError("invalid branch")
  value=double(sibling+value) if step["side"]=="left" else double(value+sibling)
 return value
def calculate():
 leaves=[double(("tutorial-"+c).encode("ascii")) for c in "ABC"]
 merkle,mutated=root(leaves);path=branch(leaves,1)
 assert fold(leaves[1],path)==merkle and not mutated
 # Synthetic header has no established proof of work, accepted block or valid transactions.
 header=struct.pack("<I",2)+bytes(32)+merkle+struct.pack("<III",1700000000,0x1e0ffff0,0)
 assert len(header)==80 and header[36:68]==merkle
 accepted=0;tampered=0
 for n in range(1,10):
  cases=[double(("case-"+str(i)).encode()) for i in range(n)];expected,_=root(cases)
  for i,leaf in enumerate(cases):
   p=branch(cases,i);assert fold(leaf,p)==expected;accepted+=1
   bad=bytes([leaf[0]^1])+leaf[1:];assert fold(bad,p)!=expected;tampered+=1
 original,flag1=root(leaves);duplicated,flag2=root(leaves+[leaves[-1]])
 assert original==duplicated and not flag1 and flag2
 for bad,index in [([],0),(leaves,-1),(leaves,3)]:
  try:branch(bad,index)
  except ValueError:pass
  else:raise AssertionError("bad branch request accepted")
 return dict(scope="Synthetic leaf hashes, not transaction IDs; standalone branch exercise, no Core RPC, no Scrypt or block validation, no real payment.",leaves=[dict(label=c,internal_hex=h.hex(),display_id=h[::-1].hex()) for c,h in zip("ABC",leaves)],selected_label="B",selected_index=1,path=path,root_internal_hex=merkle.hex(),root_display_id=merkle[::-1].hex(),synthetic_header_hex=header.hex(),synthetic_header_id=double(header)[::-1].hex(),duplicate_example=dict(same_root=True,three_leaf_mutated=flag1,four_leaf_mutated=flag2),checks=dict(branches_checked=accepted,changed_leaf_rejections=tampered,invalid_requests_rejected=3,duplicate_root_example_checked=True))
if __name__=="__main__":print(json.dumps(calculate(),indent=2))