[Cryptography] Bloom Filter & Merkle tree

Bloom Filter

특정 집합에 포함되지 않은 데이터를 구분하기 용이한 자료구조

• N bit 배열과 M개의 해시 함수로 구성되어 있다.

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

✓ N = 18, M = 3인 Bloom Filter

Merkle tree

트랜잭션이 저장된 블록의 무결성을 보장하기 위해 사용하는 자료구조

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

• Merkle Path를 이용해 트랜잭션이 블록에 포함되어 있는지를 쉽게 파악 가능하다

• 리프노드들을 concatenate operator를 통해 단순 더한 후 해싱하여 루트노드를 생성한다
  ↪ 🖋 트랜잭션 수가 홀수일 경우에는 마지막 트랜잭션의 해시값을 중복으로 계산한다

✓ Merkle tree