About Bloom Filter, Merkle Tree, MPT

• Bloom Filter
• Bloom Filter 특징
• Merkle tree
• Merkle tree 특징
• Merkle Patricia Trie (MPT)
• 특징
• 타입
• hex Prefix Encoding
• 📝 Example

Bloom Filter

특정 집합에 속하는 데이터의 존재 여부를 빠르게 확인할 수 있는 확률적 자료구조입니다.

Bloom Filter 특징

• N bit 배열과 M개의 해시 함수로 구성되어 있으며, 해시 함수들은 저장하려는 각 요소를 배열의 다른 위치에 매핑합니다.

• 데이터가 추가될 때, M개의 해시 함수는 각각 이 요소에 대해 하나의 인덱스를 생성하며, 생성된 모든 인덱스에 해당하는 비트는 1로 설정됩니다.

• 특정 패턴을 사용한 해시 함수를 이용하여 배열중 하나를 가르키게 되는데, 이 때 모두 1을 가르키는 경우 있을 가능성이 있는 것을 의미하고, 한 개라도 0을 가르키면 확실하게 존재하지 않는 것을 의미합니다..

• 블룸 필터의 한계는 거짓 양성이 발생할 수 있다는 것인데, 즉 데이터가 실제로는 집합에 없지만, 블룸 필터에 의해 존재하는 것으로 잘못 인식될 가능성이 있습니다. 그러나. 거짓 음성(false negatives)은 발생하지 않으므로 데이터가 블룸 필터에 있다고 표시되면 그 데이터는 확실히 집합에 포함되어 있습니다.

✓ N = 18, M = 3인 Bloom Filter

Merkle tree

머클 트리는 데이터 무결성 검증에 널리 사용되는 이진 해시 트리 구조이며, 블록체인 기술에서 이 자료구조는 주로 트랜잭션 데이터의 무결성을 보장하는 데 사용됩니다.

Merkle tree 특징

• Binary Hash Tree구조를 갖고 있으며 이 구조 덕분에 계산이 단순하고 빠르다는 장점을 갖고 있습니다.

• Merkle Path를 이용해 트랜잭션이 블록에 포함되어 있는지를 쉽게 파악 가능하며, 트랜잭션의 무결성을 증명하기 위해 필요한 데이터의 양을 크게 줄일 수 있습니다.

• 리프노드들을 concatenate operator를 통해 결합 후 해싱하여 상위노드를 생성하며 최종적으로 단일 루트 노드를 생성합니다.

  ⤷ ✓ 트랜잭션 수가 홀수일 경우에는 마지막 트랜잭션의 해시값을 중복으로 계산하여 노드의 수를 짝수로 맞춥니다.

---

✓ Merkle tree

---

Merkle Patricia Trie (MPT)

Merkle Patricia Trie란 이더리움에서 사용하는 자료구조이며 Merkle trie를 변형해서 사용합니다.

특징

• 각각의 노드는 sha3을 이용해서 Hashing 합니다.

• MPT는 key-value DB라고 볼 수 있으며 다양한 클라이언트에서 사용되는 데이터베이스와 호환됩니다..

  ⤷ level DB은 Go, C++, Python client에서 사용되고, rocks DB은 Parity client에서 사용됩니다.

  ⤷ key는 각 Node의 hash이고 value는 각 Node의 값을 의미합니다.

• Merkle Tree처럼 하나의 Node라도 변경될 경우 Root Hash에 영향을 주게 되어 값의 무결성을 보장할 수 있습니다.

타입

• NULL : NULL은 빈 문자열값을 의미 합니다.

• branch : 16 ~ 17개의 요소로 구성되어 있는 배열입니다. 0 ~ 15번 Index는 hashing된 주소값이 들어갈 수 있으며 value가 있는경우에는 마지막 index로 value의 값이 들어갑니다.

  ⤷ hashing된 주소값은 index에 맞춰 들어갑니다.

• leaf : 2개의 요소로 구성되어 있는 배열이며 encodedPath와 value값이 들어가 있습니다.

• extension : 2개의 요소로 구성되어 있는 배열이며 encodedPath와 key값이 들어가 있습ㄴ;다.

hex Prefix Encoding

extension Node 와 leaf Node를 구별하기 위해 사용

✓ Merkle Patricia Trie는 nibble 단위로 저장됩니다. nibble은 4bit 즉 0.5byte이며 hex char역시도 4bit이며 1byte로 떨어지지 않을 경우 1byte를 맞추기 위해 0을 이용하여 padding합니다.

hex char	node tpye	path length
0	extension	even
1	extension	odd
2	terminating (leaf)	even
3	terminating (leaf)	odd

📝 Example

✅ 가상의 path 예시

✅ 가상의 key-value 기준 trie 예시

✏️ Example hash 특징

hashA : branch Node이며 value가 존재지 않기 때문에 16개의 hashing된 주소값이 들어갈 수 있는 index로만 이루어져 있습니다.

hashB, hashE : extension Node이므로 encodedPath와 key로만 이루어져 있습니다.

hashC, hashG : leaf Node이므로 encodedPath와 value로만 이루어져 있습니다.

hashD, hashF : branch Node이며 value가 존재하므로 16개의 hashing된 주소값이 들어갈 수 있는 index와 value로 이루어져 있습니다.