"""Original RFC9162-shaped finite tree and separate iterative verifier."""
import hashlib,json
def H(x):return hashlib.sha256(x).digest()
def leaf(x):return H(b'\x00'+x)
def node(l,r):return H(b'\x01'+l+r)
def split(n):return 1<<((n-1).bit_length()-1)
def root(data):
 if not data:return H(b'')
 if len(data)==1:return leaf(data[0])
 k=split(len(data));return node(root(data[:k]),root(data[k:]))
def proof(data,index):
 if type(index) is not int or not 0<=index<len(data):raise ValueError('valid leaf index')
 if len(data)==1:return []
 k=split(len(data))
 return proof(data[:k],index)+[root(data[k:])] if index<k else proof(data[k:],index-k)+[root(data[:k])]
def verify(payload,index,size,path,trusted):
 if type(payload) is not bytes or type(index) is not int or type(size) is not int or not 0<=index<size<=16 or type(path) is not list or any(type(p) is not bytes or len(p)!=32 for p in path) or type(trusted) is not bytes or len(trusted)!=32:return False
 fn=index;sn=size-1;r=leaf(payload)
 for p in path:
  if sn==0:return False
  if fn&1 or fn==sn:
   r=node(p,r)
   if not fn&1:
    while fn and not fn&1:fn>>=1;sn>>=1
  else:r=node(r,p)
  fn>>=1;sn>>=1
 return sn==0 and r==trusted
def demo():
 data=[b'alpha',b'beta',b'gamma',b'delta',b'epsilon'];r=root(data);rows=[]
 for i,x in enumerate(data):
  p=proof(data,i);assert verify(x,i,5,p,r);rows.append({'index':i,'payload_ascii':x.decode(),'siblings_leaf_to_root':[s.hex() for s in p],'verified':True})
 p=proof(data,0)
 mutations={'changed_leaf':verify(b'ALPHA',0,5,p,r),'wrong_index_orientation':verify(data[0],1,5,p,r),'outside_index':verify(data[0],5,5,p,r),'wrong_size':verify(data[0],0,4,p,r),'missing_sibling':verify(data[0],0,5,p[:-1],r),'extra_sibling':verify(data[0],0,5,p+[H(b'extra')],r),'reversed_path':verify(data[0],0,5,list(reversed(p)),r),'changed_sibling':verify(data[0],0,5,[H(b'changed')]+p[1:],r),'wrong_root':verify(data[0],0,5,p,H(b'wrong'))}
 assert not any(mutations.values())
 assert proof([b'only'],0)==[] and verify(b'only',0,1,[],root([b'only']))
 checks=0
 for n in range(1,10):
  a=[bytes([i]) for i in range(n)];rr=root(a)
  # independent stack construction of root from leaf merges
  stack=[]
  for i,x in enumerate(a):
   stack.append(leaf(x));j=i
   while j&1:
    right=stack.pop();left=stack.pop();stack.append(node(left,right));j>>=1
  acc=stack.pop()
  while stack:acc=node(stack.pop(),acc)
  assert acc==rr
  for i,x in enumerate(a):assert verify(x,i,n,proof(a,i),rr);checks+=1
 return {'tree_size':5,'root_sha256':r.hex(),'definition':'leaf HASH(00||data); node HASH(01||left||right); split largest power2<n, no odd-leaf duplication','all_five_proofs':rows,'mutation_verification_results_all_false':mutations,'singleton_empty_proof_verified':True,'sizes1_to9_leaf_verifications':checks,'independent_stack_roots_equal':True,'trust_limit':'root must already be trusted; presence is not publisher identity, content quality or append-only consistency','real_TLS_or_certificate_operation':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))