Graphene-Using IBLTs & BloomFilter

Assumptions

Alice 블록을 갖고있고, Bob은 블록을 받아야하는 상황.(마이너끼리 혹은 마이닝풀 내에서 Peer에게 전송)

Alice의 블록에 이미 Bob의 pool에 있는 중복되는 트랜잭션이 많다고 가정하고, Bob에게 없는 Assumptions트랜잭션만을 받기 위함. 혹은 누락된 트랜잭션을 받기 위함.

데이터 전송에 최소 대역폭 사용을 목표로함.

(Graphene전에) IBLT만을 이용한 방법

Alic가 블록을 갖고있다는 사실을 알리면

Bob은 getdata메시지를 보낸다.

Alice는 모든 트랜잭션id로 IBLT를 생성해 블록 header와 함께 전송한다.

Bob은 자신의 pool에 있던 트랜잭션으로 IBLT를 생성하여, 받은 IBLT와 함께 디코딩을 수행(subtraction 연산)한다. (두 IBLT의 차이는 15%이상일 수 없다. 그렇지 않으면 IBLT를 더 크게 만들어야한다.)

결과 :

IBLT의 크기는 두 집합의 크기와 관계없고, subtraction후 디코딩 할 수 있다고 예상되는 차이, 즉 대칭차가 클수록 크기가 증가하므로,

pool이 작을때(대칭차가 비교적 작을때, 파란선, 노란선)는 효과가 좋지만 pool의 크기가 커지면(대칭차가 크면, 초록색 선) Compact Blocks(빨간 선) 보다도 전송할 데이터의 양이 매우 많아진다.

Graphene - IBLT와 Bloom Filter 사용

(*같은 이름의 댄 라리머가 만든 블록체인 엔진과 다름을 주의)

블록 헤더와 로컬노드의 Pool에 적용할 IBLT와 블룸필터를 함께 전송

PoW, PoS, DAG에 사용가능.

Bitcoin Cash의 풀노드인 Bitcoin unlimited 에서 사용중이며 ver.2를 개발중(아래에 최근 리포트와 ver2를 위한 확장paper[6] 참고)

기억!(BloomFilter와 IBLT 페이지를 참고)

FPR(False Positive Rate)은 블룸필터의 크기가 크고, 검색할 원소의 수가 작을수록 낮아진다.

IBLT의 크기는 두 집합의 크기와는 관련없고 두 집합간의 차이(대칭차)가 커질수록 크다.(subtraction후 디코딩할수있다고 예상되는 차이가 클수록 크다)

Problem

이전의 방법들을 이용한 결과에 따르면,

블록과 pool간의 symmetric difference(대칭차)가 크면 블룸필터 비용이 높아진다.(=크기가 커진다)

블록과 pool간의 대칭차가 크면 IBLT의 비용이 높아진다.(=크기가 커진다)

Solution (직접해봐야 무슨 뜻인지 안다..참고)

Bloom Filter를 사용하여 블록과 pool간의 대칭차를 줄임. (IBLT에서 디코드하기 전에 대칭차를 줄인다.)

IBLT를 이용하여 Bloom Filter의 error를 recover.

IBLT로 recover하기 때문에 블룸필터 사용시 큰 FPR(false positive rate)를 사용해도 됨(즉, 블룸필터 크기가 커도 됨)

블룸필터의 FPR = 1/m 으로 설정시, m개의 트랜잭션을 확인할때는 FPR = 1/m x m = 1 이므로 블록당 1개의 false positive를 예상

→ IBLT가 한개의 대칭차를 갖도록 한다. (IBLT의 크기가 작을 것)

두 IBLT의 차로부터 false positive인 트랜잭션ID를 정확히 알 수 있다.

결과 :

기존보다 블록 사이즈를 1/10배 줄임

one IP packet에 들어맞음

pool 크기 증가시에도 block size가 크게 증가하지 않음.

storage와 CPU를 적게 사용

uncle(orphan) 블록을 줄이고, 더 빠른 블록타임을 갖게됨

블록 릴레이에 적은 대역폭을 사용하게되어 더 많은 노드가 참여가능

Decode failure 확률이 1/1000

→ 매우 작은 확률이지만 IBLT의 디코드가 실패하는경우 sender는 IBLT를 다시 보내야함. (비용은 그리 크지않다)

Graphene ver.1

(Created: 2018-07-26으로, 나중에 쓰여진 스펙이라 Paper[1]나 발표자료[2]와 다르거나 실제와 더 정확할 수 있음. 아래는 flow만 적어놓은것이고, 다른자세한 내용은 [5]에서 확인)

receiver의 mempool과 orphan pool (m)에 있는 tx의 수와 함께 get_grblk메세지를 보냄

sender가 블록 헤더와, B, I, T, R를 grblk 메세지와 함께 전송

B : 블록의 모든 tx ID를 이용해 생성한 Bloom filter

I : 블록의 모든 tx ID의 cheap hash로 생성한 IBLT

T : coinbase 등 block에 포함된 tx Id 리스트

R : tx ID로 정렬된 tx list (블록체인 프롤토콜이 canonical transaction ordering이 아닐경우 필요)

receiver는 m과 받은 tx list(T)를 바탕으로 알고있는 모든 tx ID의 집합 M를 생성?

→ m만 필터링 해도 되는것 같다.

Bloom filter를 사용해 집합 M를 필터링하여 M'을 생성

M'을 기반으로 IBLT I' 생성

IBLT(I)와 I'의 substraction(I - I') 을 진행하여 두 집합의 symmetric differnce(대칭 차이)의 tx ID를 디코딩함

(substraction의 성공 여부에따라) 블록에 있지만 M에서 누락된 ID집합(B)나 잘못 통과한 false positive ID를 알수 있음

두가지 실패의 경우가 있는데, 복구를 위해 fall-back방식이 필요함.(version 2에서 개발)

디코딩에 실패하는 경우: Bob은 Alice에게 더 큰 크기의 IBLT를 다시 요청해야한다.(Bob이 많은 트랜잭션을 갖고 있지 않은것)
디코딩에는 성공하였으나, checksum 에러가 발생하는경우: 잘못된 txID로 get_gblktx을 요청하여 모든 트랜잭션을 받지 못하면 checksum에러라 판단하고 fail-over block을 요청함.

IBLT의 디코딩에 성공하고, 체크섬 에러가 일어나지 않는다면, receiver는 정렬되지않은 tx id 집합을 갖게되므로, 그걸토대로 get_grblktx요청하여 grblktx를 받음.

받은 tx를 머클트리에 배치하며 블록헤더 루트의 유효성을 검증. tx의 순서는 (프로토콜에서 정해지지 않았다면) R(canonical ordering)에 의해 결정됨.

*cheap hash: first 8 bytes of the hash interpreted as an unsigned little endian 64 bit integer

(충돌 확률이 거의 없으므로 대역폭을 줄이기위해 일부만 사용)

Graphene ver.2 (수정중)

paper2[6]의 graphene extended

M' = x+y (x: true positives, y: false positives, M' : pool의 트랜잭션을 sender의 블룸필터에 적용한 결과)

x와 y는 아직 구분 불가능하다.

receiver가 M'을 기반으로 블룸필터 R을 생성(f=b/n-x*, 여기서 x*<x 일때, n-x*는 블록에만 있고 pool에는 없는 트랜잭션 수(true negative), b는 bloom filter와 IBLT 크기를 작게할때의 값, 확률적인 false positives 개수)

receiver 가 R과 b를 sender에게 보냄

sender가 R에없는 트랜잭션을 receiver에게 모두 보냄

sender는 b+y* 항목을 복구하기위해 블록의 모든 트랜잭션에 대한 IBLTs J를 생성해 보낸다.

b: R에 있는 것으로 잘못 표시된 트랜잭션 수 및 S에 있는 것으로 잘못 표시된 트랜잭션 수를 설명합니다.

receiver는 Z에 있는 tx ID를 기반으로 IBLTJ'를 생성하고, J와 J'를 차연산하여 디코딩한다.

결과 : 집합 Z를 조정하고 Merkle 루트의 유효성을 검사하고 프로토콜이 종료됨.