비트코인 마이너가 블록 생성에 성공하고 나면 네트워크에 빠르게 전파해야 합니다. 블록의 크기가 커질수록 블록 전파에 걸리는 시간도 늘어나기 때문에, 블록 전파 시간을 줄이는 최적화가 중요해집니다. 블록 전파 시간을 줄이는 방법 중에 하나로 비트코인 코어 개발자인 Gavin Andresen이 제안한 O(1) Block Propagation이 있습니다.

마이너가 채굴해서 전파하는 블록에는 트랜잭션들이 포함되어 있습니다. 그런데 블록을 전파 받는 노드들도 사실은 트랜잭션 풀에 마이닝된 트랜잭션을 이미 대부분 가지고 있음에도 불구하고, 정확히 어떤 트랜잭션이 마이닝되었는지 알 수 없기 때문에 블록에 포함된 트랜잭션들을 다시 다운로드 받아야 합니다.

그런데 새로 생성된 블록에 들어있는 트랜잭션의 목록과 트랜잭션 풀에 들어 있는 트랜잭션의 목록의 차이를 바로 알 수 있는 데이터 구조가 있다면, 노드 입장에서 이미 가지고 있는 트랜잭션은 굳이 다시 다운로드 받지 않아도 됩니다.

이러한 문제를 Set reconciliation이라고 하는데, IBLT(Invertible Bloom Lookup Tables)라는 데이터 구조가 이에 대한 해법을 제공합니다. Gavin Andresen의 O(1) Block Propagation 제안은 IBLT를 이용하여 이미 트랜잭션 풀에 있는 트랜잭션을 전파하지 않고도 다른 노드에게 블록을 전파하는 방법을 제안하고 있습니다.

현재 비트코인 마이너들은 별도의 고속 블록 릴레이 네트워크를 사용하고 있기 때문에 O(1) Block Propagation는 받아들여지지 않은 것 같은데, 블록체인 새로 설계하는 분들에게는 재미있는 시도일 수 있을 것 같습니다.

자세한 내용이 궁금하신 분은 원글을 읽어보세요.