Merklix

• 0노드는 왼쪽 자식에만 올수있고, 1노드는 오른쪽 자식에만 올수 있다.

• 잎은 빈 잎이없는 집합의 값을 정확하게 포함

• 잎에 대한 경로는 잎에 포함 된 값의 비트 prefix

// T: set of transactions
// k: index of the bit used for partitioning
MerklixHash(T,k)
{
match (T) with
| { t } => SHA256(t) // single transaction
| (T0,T1) where { t ∈ T0 : t[k] == 0 } and { t ∈ T1 : t[k] == 1 }
=>
match (T0,T1) with
| (_,Ø) => MerklixHash(T0,k+1)
| (Ø,_) => MerklixHash(T1,k+1)
| _ => SHA256(MerklixHash(T0,k+1)::MerklixHash(T1,k+1))
}
// Root start at bit index zero
MerklixHashRoot(T) => MerklixHash(T, 0)

• 높이가 h인 포화 이진 트리(full binary tree)는 `2^h`−1개의 노드를 가진다

• 노드가 N개인 포화(full) 혹은 완전(complete) 이진 트리의 높이는 logN이다.
O(logN)

• 한쪽으로 쏠린경우 최악은 높이 N

references