Graphene 과정을 잘 이해하기 위해서 공통원소를 갖는 집합A, B에 대해 A-B(A차집합B)를 구하는 과정을 직접 간단하게 해보면서
IBLT가 어떻게 bloomfilter의 false positive를 recover할수있는지 이해하게 되었다.
1. 블룸필터 과정
A: sender, B: receiver
x,y,z,a는 트랜잭션(key)
h1, h2는 해시함수. (실제 해시함수 값이 아닌 임의로 정한 값임)
Graphene과정을 통해 우리가 구하고 싶은 것은 주황색으로 색칠 된 부분이다.(A-B)
위 과정은 A를 기반으로 블룸필터 S를 만든후, S에서 B의 원소들을 찾는 과정인데, 자세한 내용은 Bloomfilter설명 페이지를 참고하길.
멤버쉽쿼리 결과, m’=A∩B={y,z,a}
이 중 a는 실제로는 B에만 포함된 원소이므로, false positive인데, 사실 우리는 블룸필터 쿼리결과를 보고 어떤것이 true positive이고 false positive인지 구별할 수 없고, 후에 IBLT로 true positives만을 골라낼 것이므로 이 단계에서 false positive가 포함되는것은 상관 없다.
그러므로 여기서는 FPR와 상관없이 블룸필터의 크기를 최대한 줄이는 것이 더 중요.
2. IBLT 생성 및 차연산(subtraction)
A와 이전에 구한 m'을 바탕으로 각각 IBLT를 생성한다.
아래의 insert 연산을 이용하여 각 원소를 차례대로 삽입한다.
GetKeyIndices(key) = [h1(key), h2(key)]
즉, 각 key의 인덱스는 해시함수 h1와 h2와의 결과값이다.
i는 각 원소(key)의 인덱스의 위치를 의미하며, IBLT를 나타낸 테이블의 각 열 이라고 생각하면 된다.
(index=1 이면, 1열) 각 열을 T[index]로 나타낼수 있는데, 편의상 T의 인덱스는 1부터 시작한다고 가정하겠다.
⊕는 XOR 연산을 의미한다. 각 keysum과 hashsm에 대해 key와 H(key)를 xor 연산하고, count를 1씩 추가 한다고 생각하면 된다.
count는 십 진수로 표시하고, key_sum과 hash_sum은 4자리의 2진수로 표시했다.
여기서 hash_sum은 fault tolerance 방지를 위해 추가한 것으로, 아래의 Listing과정에서 설명할 것이다. hash_sum을 위한 해시함수(H)는 h1를 사용했다. (H=h1)
연산 시작 전에 각 테이블의 값을 모두 0으로 초기화 한다.
I=IBLT(A) 생성
A = {x,y,z} 이므로,
insert x(=1011) :
GetKeyIndices(x) = [1,2] ,
i = 1,
T[i].keysum = 0 ⊕ 1011,
T[i].hashsum = 0 ⊕ H(1011)(=0001),
T[i].count = 0 + 1,
i =2,
T[i].keysum = 0 ⊕ 1011,
T[i].hashsum = 0 ⊕ H(1011),
T[i].count = 0 + 1,
insert y(=1001) :
GetKeyIndices(y) = [2,3] ,
i = 2,
T[i].keysum = 1011 ⊕ 1001,
T[i].hashsum = 0001 ⊕ H(1001)(=0010),
T[i].count = 1 + 1,
i = 3,
T[i].keysum = 0 ⊕ 1001,
T[i].hashsum = 0 ⊕ H(1001),
T[i].count = 0 + 1,
insert z(=0111) :
GetKeyIndices(y) = [3,4]
i = 3,
T[i].keysum = 1001 ⊕ 0111,
T[i].hashsum = 0010 ⊕ H(0111)(=0011),
T[i].count = 1 + 1,
i = 4,
T[i].keysum = 0 ⊕ 0111,
T[i].hashsum = 0 ⊕ H(0111),
T[i].count = 0 + 1,
I'=IBLT(m') 생성
m’={y,z,a}이므로,
위와 똑같은 방법으로 진행.
I와 I'의 차 연산 (I''=I-I')
I는 A를 바탕으로 생성한 IBLT이고 (A가 B에게 생성해서 보냄) I'는 m'를 바탕으로 B가 생성한 IBLT이다.
우리가 최종으로 원하는 것은 A-B(A/B) 즉 I-I' 이므로, I에서 I'를 차 연산(subtraction) 해야 한다.
IBLT끼리 차 연산한 결과로 얻은 IBLT를 I''라 하겠다. (I'' = I-I')
IBLT끼리의 차 연산 방법은 간단하다.
같은 자리의 수끼리 연산을 하여, 결과 역시도 IBLT이다.
count는 I에서 I'의 각 값의 차를 구하고,
keysum과 hashsum은 각 자리의 수 끼리 XOR 연산을 해주면 된다.
결과인 I''에서는 우리가 목표로 하는 영역과 같은 왼쪽 그림에서 색칠 된 영역의 원소(I-I') 뿐만 아니라 I'-I역시 포함한 I와 I'의 대칭차(symmetric difference)인 (I-I')U(I'-I), 즉 (A/B)U(B/A)의 원소를 함께 나타내고 있다.
I와 I'의 대칭차는 Sub연산 후 Listing과정을통해 구할 수 있다.
Listing
IBLT는 Listing 과정을 통해 IBLT가 가진 원소들을 나열할 수 있다. 따라서 우리는 Listing 과정을 통해 차연산을 통해 얻은 오른쪽 그림 영역의 원소들을 얻을 것 이다.
Listing은 다음과 같다.
