Kadcast-NG: A Structured Broadcast Protocol for Blockchain Networks 논문 분석
요약
이번 논문은 기존의 체인이 가진 “unstructured peer-to-peer overlay networks” 에서는 블록의 전파가 복잡하고 오버헤드가 발생하여 비효율적이라는 점을 짚으며, 블록의 전파가 지연되는 문제를 다루고 있습니다. 논문에 설명된 카드캐스트 프로토콜은 “structured peer-to-peer overlay networks”로 효율적으로 블록을 전파한다고 한다고 하는데 이러한 카드캐스트 프로토콜의 우수성을 다루고 있습니다.
이해를 위한 사전지식
이 논문을 이해하기 위해서는 몇가지의 기본 개념들을 알아야 합니다.
Overlay Networks
오버레이 네트워크는 호스트 간의 연결을 의미하며, 오버레이 네트워크에는 구조화/비구조화 된 네트워크 2가지가 존재합니다. 이 2가지에 대해서 먼저 알아보고 넘어가도록 하겠습니다.
unstructured peer-to-peer overlay networks
비구조화된 오버레이 네트워크에서는 중앙서버가 없으며 슈퍼 피어가 있어서 인접 노드 간에 쿼리를 릴레이하는 허브 역할을 합니다. 위의 P2P 전송을 나타내는 그림이 “unstructured peer-to-peer overlay networks”입니다. 오버레이 링크가 임의적으로 생성되는 형태로 이러한 P2P 네트워크에서 피어가 네트워크에서 원하는 데이터를 찾으려면 네트워크를 통해 쿼리를 플러딩(flooding)이라는 기법을 사용하여 데이터를 공유하는 피어를 최대한 많이 찾아야 합니다. 그 결과 트래픽이 많아 검색 효율성이 떨어지게 되고 여러 피어와 연결된 인기 있는 콘텐츠는 찾기가 쉽지만 인기가 없는 몇개의 피어와 연결된 콘텐츠는 찾이가 어렵고 찾을 수 있다는 보장도 적습니다. 이를 블록체인에 적용하면 블록이 조금만 연결된 노드들은 검색이 어려우며 이렇게 검색이 되는 노드들 끼리 연결하다보면 트래픽이 많아져서 블록의 전파 속도가 느려지고 포크가 발생하게 된다고 볼 수 있습니다. 일반적으로 P2P에서 이러한 구조가 많이 쓰인다고 합니다.
structured peer-to-peer overlay networks
이러한 그림이 “structured peer-to-peer overlay networks”라고 볼 수 있습니다. 이렇게 구조화하여 안정성 , 효율성, 확장성을 확보 할 수 있다고 합니다. 반면 문제점으로는 소수의 악성 노드만으로도 시스템이 위험할 수 있다는 단점도 있다고 합니다.
Kadcast 프로토콜에 대하여
비트코인 이후 등장된 수많은 블록체인은 오버레이 네트워크에서 트랜잭션을 전파하여 트랜잭션을 발생 시킵니다. 검증자 노드가 트랜잭션을 수집 및 검증하고 주기적으로 블록으로 통합하며, 블록은 분산원장에 추가 됩니다. 블록은 네트워크에서도 전파되므로 모든 노드가 장부를 복제하여 로컬에서 정확한지 확인할 수 있습니다. 그러나 이러한 구조는 중복된 항목이 계속해서 발생하게 되고 결국 메세지 오버헤드가 높아집니다. 그 결과 블록 크기의 제한이나 트랜잭션 속도에 제한이 걸리게 됩니다.
논문에서 소개하는 kadcast는 kademlia 아키텍처를 기반으로 하는 구조화된 브로드캐스트 프로토콜로 조정 가능한 중복성과 오버헤드를 통해서 효율적으로 브로드캐스트 운영을 가능하게 합니다.
THE KADCAST PROTOCOL
A. 오버레이 구성 Overlay Construction
Kademlia는 노드가 구조화된 오버레이 네트워크를 형성하는 피어 투 피어 프로토콜입니다. 노드가 네트워크에 가입하면 ID가 생성되며, 아이디는 Kademlia 오버레이의 기초를 구축하는 이진 라우팅 트리에서 노드의 위치를 결정합니다.
그림 1에서 노드 ID0 = 1111의 4 버킷은 각각 1110, 110*, 10** 및 0** 범위의 노드를 보유합니다. 노드가 k개의 항목을 이미 보유하고 있는 지정된 버킷에 새 항목을 추가할 때 Least Recntly used 방식을 사용합니다. 또한 목록에서 항목을 삭제하기 전에 피어는 각 노드에 여전히 연결할 수 있는지 확인하고 그렇지 않은 경우에만 삭제합니다. 이러한 방식으로 프로토콜은 새로운 노드보다 더 오래되고 안정적인 노드에 먼저 연결을 하게 되고 이클립스 공격과 같은 보안 문제에 대해 네트워크를 강화시킬 수 있습니다.
노드가 네트워크에 처음 가입할 때 하나 이상의 부트스트래핑 노드의 주소를 알아야 합니다. 따라서 PING 메시지를 알려진 노드에 전송하여 실제로 온라인 상태인지 확인합니다. 또한, PING은 송신 노드의 라우팅 정보를 수신자에게 전송하여 네트워크에 그 존재를 분산 시킵니다. 프로토콜에서는 모든 메시지가 발신인 뿐만 아니라 수신인의 버킷도 업데이트합니다. 이러한 소프트 상태 프로토콜 설계를 통해 필요한 정보 기반의 설치 공간을 최소로 유지하는 매우 가벼운 오버레이 멤버십 관리를 할 수 있습니다.
초기 부트스트래핑 단계 이후, 각 카드캐스트 노드는 그것의 라우팅 정보를 업데이트하기 위해 네트워크를 발견하기 시작하는데, 이는 라이프사이클 동안 주기적으로 반복됩니다. 처음에 조인하는 노드는 자체 ID를 검색하여 자신의 네트워크 위치에 가깝게 배치된 노드 집합을 반환합니다. 또한 각 노드는 지난 한 시간 동안 일부 활동이 나타나지 않은 모든 버킷을 주기적으로 새로 고칩니다. 각 버킷에 대해 적절한 거리의 임의 ID를 선택하고 버킷을 새로운 라우팅 정보로 채우기 위해 조회 작업을 수행합니다. 이러한 조회 절차를 통해 노드는 주소 공간에서 특정 ID에 가장 가까운 k개 노드 집합을 검색할 수 있습니다.
B. 메시지 전달 Message propagation
대부분의 블록 체인 네트워크는 블록 및 트랜잭션 처리를 위한 TCP 기반 전송 프로토콜에 의존하며, 패킷 손실 시 누락된 세그먼트를 재전송하여 임의로 큰 데이터의 신뢰성 있는 전송을 보장합니다. 이 방법은 암시적으로 수명이 긴 연결을 가정하고 연결 관리 측면에서 확장성이 떨어집니다.
대조적으로, UDP 또는 QUIC와 같은 전송 프로토콜은 Kadcast의 설계를 보완하는 단시간 저비용 전송으로 더 확장 가능하고 동적 접근을 가능하게 합니다. 다시 위의 그림을 보겠습니다. 노드 ID0 = 1111은 네트워크에서 광대역 캐스트를 시작하고, 높이가 h = 0인 4개의 CHUNK 메시지를 보냅니다. 각 버킷에서 선택한 3 ~ 1개의 임의 노드 Bi , i = 0 . . 3. 수신 노드는 이 절차를 반복하여 할당된 높이보다 작은 버킷 번호에서 노드에 메시지를 다시 보냅니다. 따라서 브로드캐스트 작동은 하위 트리 크기를 감소시키면서 수행하게 되어 O(log n) 단계로 종료가 보장됩니다.
C. UDP 기반 메시지 전달의 신뢰성 Reliability of UDP-based Message Delivery
만약 중복 메세지가 없다는 가정을 한다면 아무런 문제가 없겠지만 실제로는 중복 메세지가 발생할 가능성이 높습니다. 따라서 패킷 손실뿐만 아니라 전송 문제가 발생하는 상황을 고려해야 합니다. 위의 이미지에서 노드 0000으로 이동하는 중 청크가 손상되었거나 이 노드가 청크 포워드를 거부하는 경우 전체 버킷 B3(즉, 트리의 오른쪽 절반)는 해당 메시지를 수신하지 못할 것입니다. 즉, 최악의 경우, 신뢰할 수 없는 UDP 전송 프로토콜에 의해 야기되는 단일 전송 장애는 50%의 커버리지만 가지게 됩니다. 따라서 브로드캐스트 알고리즘은 두 가지 접근법으로 이를 개선합니다.
1) 브로드캐스팅 안정성 및 성능 향상
첫째, 버킷당 단일 대리자(delegate)를 갖는 대신 다수의 대리자를 선택합니다. 이로 인해 선택한 여러 노드 중 하나 이상이 정직하고 도달할 수 있는 가능성이 크게 증가합니다. 또한 이 병렬 브로드캐스팅 방법은 지연 시간 측면에서 전파 성능을 향상시킵니다. 최상의 연결을 가진 노드가 전송된 메세지를 먼저 수신하고 버킷의 청크를 전파하기 시작합니다. 모든 홉에서 반복되고, 카드캐스트 노드는 중복 청크를 무시하므로, 메시지 전달이 가장 빠른 경로로 이루어집니다.
둘째, Kadcast는 prop-agation의 모든 홉에 패킷이 손상되거나 손실되는 경우를 대비합니다.
Kadcast는 RaptorQ 코드에 기반한 오류 수정 체계를 채택하여 재전송 없이 Cadcast 노드를 복구 할 수 있기 때문에 지연 시간 측면에서 프로토콜을 최적화하고 추가 오버헤드를 수용할 수 있습니다. 또한 메시지 전달이 완전히 실패하는 드문 경우로부터 노드를 복구할 수 있도록 하고 블록 체인의 초기 부트스트래핑을 활성화하기 위해, 카드캐스트 프로토콜은 노드가 특정 블록이나 트랜잭션에 대해 다른 사용자를 쿼리할 수 있도록 하는 간단한 REQUEST 메시지를 통합하고 이는 해당 CHUNK 메시지에 의해 응답됩니다.
2) 병렬 브로드캐스팅 분석
Kadcast는 알고리즘을 병렬화하여 브로드캐스트 하여 여러개의 브로드캐스트 중 하나라도 성공을 하면 되기 때문에 긍정적인 영향을 가져오지만 여전히 병렬 브로드 캐스팅 만으로는 공격으로 부터 안전하지는 않습니다. 그러나 아래의 표에서 볼 수 있듯이 병렬 진행을 하지 않는다면 아주 작은 packet loss에도 coverage가 급감하므로, 병렬 브로드캐스팅은 필요한 과정입니다.
3) FEC 기반 블록 전달 분석
앞서 언급된 병렬 브로드캐스팅과 함께 FEC를 도입하면 더 좋은 성능을 낼 수 있습니다. 그림 2는 15% 중복성을 가진 FEC(forward error correction) 을 도입함으로써 향상된 전송 신뢰도를 보여줍니다(f = 0.15) 이 접근법은 최대 9%에 대한 packet loss에 대하여 브로드 캐스팅되는 것을 보장합니다.
그러나 이는 더 높은 중복성(예: β > 1)과 FEC 접근방식을 결합함으로써 추가적으로 개선될 수 있습니다. 이 경우가 그림 2의 β = 3에 해당됩니다. FEC와 더 높은 병렬화전송을 통하여 평균 12%의 패킷이 손실되더라도 전체 네트워크 커버리지를 보장합니다. 이처럼 FEC는 상대적으로 작은 선형 오버헤드를 도입하면서 전파의 신뢰성을 크게 높일 수 있으나, 다수의 인자값인 β가 증가함에 따라 발생하는 오버헤드는 메시징 복잡성의 증가를 초래합니다.
종합해 보자면 KADCAST는 다수의 β를 사용하는 병렬 처리와 + FEC를 도입하여 악의적인 노드를 효과적으로 방지할 수 있게됩니다.
KADCAS의 보안 및 개인 정보 보호
KADCAST SECURITY AND PRIVACY
p2p 네트워크와 블록 전파 메커니즘은 보안과 프라이버시에 대한 공격의 대상이 될 수도 있습니다. 이를 고려하여카드캐스트 네트워크 프로토콜에서는 아래와 같은 특징들을 가지고 있습니다.
- 시빌 공격, 이클립스 공격, DOS 공격 : 더 안정적이고 오래된 노드를 찾아가며, 비트코인 처럼새로운 블록이 들어올 때마다 검증을 진행 하여 해결
- 트랜잭션 보안 : transport layer에 메세지의 암호화 기능 보유하여 해결
- 노드를 찾을 때 pseudo-randomized 하게 진행하여 예측이 어렵게 한다.
- worst case 를 가정하고 가장 성공적인 가능성을 계산하여 블록을 전송하기 때문에 10%의 네트워크 노드가 방해한다고 해도 99%의 전송이 보장되며 심지어 50%에 대한 네트워크 노드의 방해에도 96%의 전송이 보장된다.
- 규칙적이지 않는 random walk형태를 가정하며, 다양한 종류의 방해로부터 회복성을 갖는다.
이때, 노드의 수가 많아지면 그만큼 전파에 방해에 대한 공격을 받기 쉬우며, 너무 적은 노드는 검열에 대한 공격을 받을 수 있기 때문에 privacy와 reliablity는 trade 0ff 관계를 가지므로 적절한 조정이 필요하다고 합니다.
KADCAST를 보완한 KADCAST-NG
그러나 논문에서는 기존의 Kadcast 방법은 신뢰할 수 없는 UDP 전송 프로토콜 위에 구현될 때 혼잡도가 높은 문제가 있다는 사실을 실험으로 보여 줍니다. 따라서 Kadcast-NG를 새로 제안합니다.
Kadcast-NG는 신뢰가 가능한 QUIC 전송 프로토콜을 사용합니다. QUIC는 Kadcast의 디자인 철학과도 잘 어울립니다. QUIC는 다중 동시 스트리밍 방식으로 데이터를 전송하기 때문에 Kadcast의 병렬 처리를 통한 장점을 더 부각 시킬 수 있습니다. 또한 QUIC를 사용하면 1 또는 심지어 0에 해당하는 RTT (Round Trip Time)로 빠른 연결이 가능하며, 인증되고 암호화 된 전송 프로토콜로서 Kadcast의 보안성과 기밀성 또한 보완이 가능합니다. 논문에서는 이러한 Kadcast-NG가 다양한 시나리오에서 우수한 성능을 보이고 있음을 시사합니다.
해당 논문에서 제안한 Kadcast-ng-public은 아래 링크에서 확인가능합니다.
결론
KADCAST는 기존에 블록체인이 사용하는 비구조화 된 방식으로 블록을 전파하는 것이 아니라 구조화 된 방식으로 전파를 합니다. 또한 보안성에 대해서도 기존의 블록체인이 가져가는 장점과 더불어 privacy에 대한 기능도 지원하여보장해 줄 수 있는 장점을 가지고 있습니다. 논문에서는 더 나아가 QUIC 전송 프로토콜을 사용한 KADCAST-NG를 제안합니다.
블록체인의 트릴레마에 따라서 합의알고리즘에서 탈중앙화를 포기하고 체인을 개선하는 시도보다 이렇게 네트워크 전파 방식 등을 연구하여 기존의 문제를 개선해 나가려는 시도가 좋았다고 생각합니다.
이러한 연구를 바탕으로 탈중앙화의 핵심 가치를 해치지 않으며, 확장성과 보안성을 늘려 나가려는 시도가 이어진다면 언젠가 탈중앙화를 지키면서도 확장성과 보안성도 챙기는 블록체인이 나올 수 있을 것이라고 생각합니다.
- CURG(Crypto United Research Group)는 2018년 5월 대학(원), 기업, 스타트업 등 다양한 분야의 열정적인 블록체인-er들이 모인 연합 연구 그룹입니다. CURG는 2018년 5월 출범된 이후, ‘Trendy, Thoughtful, and Transdisciplinary’ 한 자세로 한 주도 빠짐없이 블록체인 연구를 지속해오고 있습니다.
- 디사이퍼(DECIPHER)는 “건강한 블록체인 생태계 조성에 기여한다” 라는 미션 아래 블록체인에 대해 연구하고 이를 실용적으로 응용하는 서울대 블록체인 연구 학회입니다. 2018년 3월에 처음 조직 되어 현재까지 블록체인 기술을 다방면에서 연구하고 산업계에 응용하고 있는 100명 이상의 회원들을 배출해왔습니다. 다양한 팀별 연구활동과 프로젝트, 컨퍼런스 개최, 서울대학교 블록체인 강의 개설, 유수 기업들과의 산학협력과 파트너십 체결을 해오며 국내 최고의 블록체인 학회로 자리 잡았습니다.
커그와 디사이퍼는 향후 적극적인 협력을 통해 블록체인 필드에서의 강력한 시너지를 구축하고자 합니다.
참고 문헌
[1]Rohrer, Elias, and Florian Tschorsch. “Kadcast-NG: A Structured Broadcast Protocol for Blockchain Networks.”
[2]오버레이 네트워크 https://slideplayer.com/slide/5701262/
[3]구조화, 비구조화 p2p 오버레이 네트워크https://www.researchgate.net/publication/261122904_UPDA_Uniform_Peer-to-Peer_Distribution_Algorithm_for_Mesh_Overlay_Paradigm
