short-paper[1]를 참고함
블룸필터에서 x : array bit , y : item수, f : false positive rate 라할때,
Graphene에서 블룸필터를 가능한 작게하기위해서는 FPR을 최대한 높여야하므로 f= a/(m-n) 이라하였다. (m-n트랜잭션이 false positives)
(m: pool에 있는 트랜잭션의 수, n : 블록의 트랜잭션 수, a : I- I'의 예상되는 대칭차 수)
따라서 x 단위를 byte로 바꾸면
I가 I'에 의해 디코딩될수 있도록 정한 IBLT의 크기는 a(대칭차 수)의 d배이고
d = 1.5 (참고하란다. David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese. What’s the Difference?: Efficient Set Reconciliation Without Prior)
Graphene에서 IBLT의 데이터 크기는
- count : 2bytes
- value : txID의 마지막 5bytes
- hash : 4bytes
일때, 1.5(2+4+5) a = 16.5a bytes 이다.
블룸 필터와 IBLT의 Total cost는
블룸필터 상수 c =8ln^2(2), IBLT목록의 오버헤드 상수 τ =16.5
(블룸필터를 가능한 작게하기위해서는 FPR을 높여야하므로, μ = n 로 설정하여 m-n개 트랜잭션이 false positives 하도록하였다.)
a = n/cτ일때 위 Total cost가 가장 낮기때문에 시뮬레이션에서 brute-force로 얻은 식은 다음과 같다.
만약 I-I'의 디코딩이 실패하는 경우 더 큰 크기의 IBLT를 다시 전송 받아야하는데, 시뮬레이션에서는 2배의 크기로 failure를 커버하기에 충분했다.
*더 잘 이해하기 위해서는 d의 최적값을 얻는 방법을 알아봐야 할것 같다. [6](http://cryptoeconomics.cs.umass.edu/buip093/draft.pdf)도 참고