이 기사는 온체인 네트워크 확장성, 블록 프로파간다 및 기타 관련 주제에 관한 기술적 개념을 설명하는 기사 시리즈의 두 번째 기사 입니다.

 

지난 주, 우리는 집합을 식별하는 데 도움을 주는 데이터 구조로서 블룸 필터를 살펴보았다. 이에 관련된 데이터 구조는 가역 블룸 조회 테이블(Invertible Bloom Lookup Table) 또는 IBLT이다. IBLT는 유사한 기능을 수행하며 누락된 멤버를 식별할 수 있는 이점을 가지고 있다. 이 기사를 통해 우리는 IBLT에 관한 간략한 정보를 확인할 수 있을 것이다.

 

IBLT는 어떻게 작동하나?

 

IBLT는 많은 셀을 가지고 있다. 집합 내 대상은 각 셀에 압축될 수 있다. IBLT와 집합 내의 항목을 가진 사용자라면 셀에서 항목의 압축을 해제할 수 있다. 또한 각 셀은 셀 내의 항목 숫자를 추적한다.  IBLT는 수신자가 해당 집합 내의 많은 항목에 대해 알 수 있지만 항목 전체를 아는 것은 아니라고 예상되는 경우에 이 컴퓨터와 집합을 교신할 때 가장 유용하다. IBLT는 누락된 항목을 식별하는 데 사용할 수 있다.

 

예컨대, 8개의 셀로 구성된 IBLT를 떠올려보자. 그리고 여기에는 10개의 항목 a,b,c,t,u,v,w,x,y,z가 있다. 블룸 필터로 비트가 선택되었던 것과 마찬가지로, 각 항목은 우리의 IBLT을 채우도록 선택된다. a가 셀 1과 3에, b가 셀 3과 6에, c가 6과 8에 압축되어 있다고 가정해보자. 이들 세 아이템을 IBLT에 압축하면 다음과 같은 결과를 얻게 된다:

모든 항목을 IBLT에 압축하면 우리는 다음과 같은 결과를 얻게 된다:

이제, 이 IBLT는 수신자에게 전송될 수 있다. 만일 수신자가 이미 t.u.v.w.x.y.z가 목록에 있다는 점을 알고 있다면, 수신자는 IBLT에서 이들 항목을 압축 해제하여 다음과 같은 양식으로 복원할 수 있다:

이제 압축을 해제하면 수신자는 이 IBLT를 디코드할 수 있다. 이 디코드 작업은 첫 번째와 여덟 번째 셀에서 각각 a와 c를 생성할 것이다. 그러나, 과압축된 셀 3과 6은 아무것도 반환하지 않을 것이다. 수신자가 이들 두 항목을 복원한 후에, 수신자는 이들을 다시 압축 해제할 수 있다. 이처럼 a와 c를 압축 해제 하는 경우 IBLT는 다음과 같이 보이게 될 것이다:

이제 수신자는 이 IBLT를 디코딩하여 b를 복원할 수 있다. B를 복원한 후, 이 IBLT는 비게 될 것이며 수신자 역시 작업이 완료되었음을 알 수 있다. 이 집합에는 a,b,c,t,u,v,w,x,y,z 항목이 있다는 것이다.

 

IBLT는 어디에 사용할 수 있는가?

 

IBLT는 이미 집합의 일부 항목을 알고 있는 누군가와 집합이 교신해야 하는 경우에 매우 유용하다. IBLT의 주요 장점 중 하나는 IBLT에 압축될 수 있는 것에 제한이 없다는 것이다. 수신자는 항목을 압축 해제 하고 디코드 작업은 여전히 작동할 수 있다. IBLT의 단점은 수신자가 어떤 정보라도 얻기 위해서는 일부 항목을 압축 해제 해야 할 수 있다는 것이다. 위의 예에서, 만일 수신자가 집합 내의 어떤 항목도 모른다면, IBLT는 그를 도울 수 없다.

 

일부 응용 프로그램에서는 누락된 항목의 수를 예측할 수 있다. 그러한 경우에, IBLT를 디코딩 할 확률을 계산할 수 있다. 실질적으로, 셀의 수와 같은 IBLT의 측면은 디코딩의 확률을 최대화하도록 조정될 수 있다. 더 큰 IBLT가 일반적으로 더 큰 디코딩의 기회를 가지게 되므로 트레이드 오프가 있다고 할 수 있다. 이는 곧 IBLT가 더욱 소형화 되거나 적은 가능성을 가질 수 있으며 그렇지 않으면 더 많은 대역폭이 필요해지므로 디코딩의 가능성이 높아질 수 있다는 것이다.

 

이 기사는 몇 가지 사항을 단순화하였다. IBLT는 무결성 검사를 제공하는 추가 데이터를 더한다. 또한, IBLT의 항목은 너무 많은 공간을 차지해서는 안 된다. 실제로는 아이템 자체보다 식별자가 사용된다. 수신자 역시 IBLT에 없는 항목의 압축을 해제할 수 있으며, 이 수신자는 여전히 이 집합을 복원할 수 있다는 것이다. 이 경우에 카운트는 음수일 수 있다.

 

IBLT와 블룸필터는 블록 전파를 향상시키기 위한 것이다

 

블룸 필터와 IBLT는 개빈 안드레슨(Gavin Andresen)이 그래픈 블록 전파 프로토콜의 전신이었던 논문에서 사용한 두 개의 주요 도구이다.  IBLT에 관해 더욱 자세히 알아보고 싶다면 이 논문에서 시작하는 것도 괜찮을 것이다.