논문 분석 01 초안) 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가지에 대해서 먼저 알아보고 넘어가도록 하겠습니다.

https://slideplayer.com/slide/5701262/

​

unstructured peer-to-peer overlay networks

​

​

https://en.wikipedia.org/wiki/File:Unstructured_peer-to-peer_network_diagram.png

비구조화된 오버레이 네트워크에서는 중앙서버가 없으며 슈퍼 피어가 있어서 인접 노드 간에 쿼리를 릴레이하는 허브 역할을 합니다. 위의 P2P 전송을 나타내는 그림이 "unstructured peer-to-peer overlay networks"입니다. 오버레이 링크가 임의적으로 생성되는 형태로 이러한 P2P 네트워크에서 피어가 네트워크에서 원하는 데이터를 찾으려면 네트워크를 통해 쿼리를 플러딩이라는 기법을 사용하여 데이터를 공유하는 피어를 최대한 많이 찾아야 합니다. 그 결과 트래픽이 많아 검색 효율성이 떨어지게 되고 여러 피어와 연결된 인기 있는 콘텐츠는 찾기가 쉽지만 인기가 없는 몇개의 피어와 연결된 콘텐츠는 찾이가 어렵고 찾을 수 있다는 보장도 적습니다. 이를 블록체인에 적용하면 블록이 조금만 연결된 노드들은 검색이 어려우며 이렇게 검색이 되는 노드들 끼리 연결하다보면 트래픽이 많아져서 블록의 전파 속도가 느려지고 포크가 발생하게 된다고 볼 수 있습니다. 일반적으로 P2P에서 이러한 구조가 많이 쓰인다고 합니다.

​

​

structured peer-to-peer overlay networks

https://www.researchgate.net/figure/Structured-DHT-peer-to-peer-network-B-UNSTRUCTYRED-P2P-An-unstructured-P2P-network-is_fig1_261122904

이러한 그림이 "structured peer-to-peer overlay networks"라고 볼 수 있습니다. 이렇게 구조화하여 안정성 , 효율성, 확장성을 확보 할 수 있다고 합니다. 반면 문제점으로는 소수의 악성 노드만으로도 시스템이 위험할 수 있다는 단점도 있다고 합니다.

​

서론

비트코인 이후 등장된 수많은 블록체인은 오버레이 네트워크에서 트랜잭션을 브로드캐스트하여 트랜잭션을 발생 시킵니다. 검증자 노드가 트랜잭션을 수집 및 검증하고 주기적으로 블록으로 통합하며, 블록은 분산원장에 추가 됩니다. 블록은 네트워크에서도 브로드캐스트되므로 모든 노드가 장부를 복제하여 로컬에서 정확한지 확인할 수 있습니다. 그러나 이러한 구조는 중복된 항목이 계속해서 발생하게 되고 결국 메세지 오버헤드가 높아집니다. 그 결과 블록 크기의 제한이나 트랜잭션 속도에 제한이 걸리게 됩니다.

​

논문에서 소개하는 kadcast는 kademlia 아키텍처를 기반으로 하는 구조화된 브로드캐스트 프로토콜로 조정 가능한 중복성과 오버헤드를 통해서 효율적으로 브로드캐스트 운영을 가능하게 하며 논문에서는 이를 아래 5가지 포인트로 설명합니다.

​

(i) Kademlia의 구조화된 아키텍처를 활용하는 블록 체인 네트워크를 위한 효율적인 브로드캐스트 프로토콜을 제시한다. (ii) 알고리즘의 신뢰성과 복원력을 완전히 조정 가능하고 예측 가능한 방식으로 개선하기 위해 병렬화를 도입한다.

(iii) 공격 벡터에 대해 논의하고 Sybil 및 Eclipse 공격에 대한 완화 전략을 제공하며, 블록 전달을 방해하거나 전이 발생자를 익명화하려는 적대적 노드에 대한 네트워크의 복원력을 분석한다.

(iv) 포괄적인 시뮬레이션 연구를 수행하고 성능, 신뢰성, 효율성 및 분석을 수행한다. 현재 널리 퍼져 있는 네트워킹 패러다임을 일반화하는 바닐라 블록 체인 프로토콜과 비교하여 카드캐스트의 우수성을 알린다.

(v) 프로토타입 구현인 Kadcast-NG를 제공하고 글로벌 테스트베드의 비교 실제 구축을 통해 그 이점을 확인한다.

​

THE KADCAST PROTOCOL

​

A. 오버레이 구성 Overlay Construction

​

Kademlia는 노드가 구조화된 오버레이 네트워크를 형성하는 피어 투 피어 프로토콜입니다. 노드가 네트워크에 가입하면 ID가 생성되며, 아이디는 Kademlia 오버레이의 기초를 구축하는 이진 라우팅 트리에서 노드의 위치를 결정합니다.

노드는 로컬 뷰를 사용하여 네트워크 구조를 횡단하여 O(log N )의 복잡도를 가진 메시지를 생성합니다. 이를 위해, 노드는 라우팅 상태를 유지하고 알려진 노드를 소위 k-버킷으로 구성하여 삼중항(ip_addr, 포트, ID)을 저장합니다. 각 버킷은 노드 식별자 ID와 관련하여 특정 거리를 가진 가장 최근에 발견된 노드 k개의 목록이며, k는 곧 라우팅 상태와 조회의 복잡성을 결정하는 시스템의 매개변수 입니다.

​

그림 1

 

그림 1에 표시된 완전히 채워진 트리가 주어졌을 때, 노드 ID0 = 1111의 4 버킷은 각각 1110, 110*, 10** 및 0** 범위의 노드를 보유합니다. 노드가 k개의 항목을 이미 보유하고 있는 지정된 버킷에 새 항목을 추가하려면 최근에 사용한 LRU(Drop) 정책을 사용합니다. 목록에서 항목을 삭제하기 전에 피어는 각 노드에 여전히 연결할 수 있는지 확인하고 그렇지 않은 경우에만 삭제합니다. 이러한 방식으로 프로토콜은 새로운 노드보다 더 오래되고 안정적인 노드를 선호합니다. 따라서 이클립스 공격과 같은 보안 문제에 대해 네트워크를 강화시킬 수 있습니다.

​

노드가 네트워크에 처음 가입할 때 하나 이상의 부트스트래핑 노드의 주소를 알아야 합니다. 따라서 PING 메시지를 알려진 노드에 전송하여 실제로 온라인 상태인지 확인합니다. 또한, PING은 송신 노드의 라우팅 정보를 수신자에게 전송하여 네트워크에 그 존재를 분산시킵니다. 실제로 프로토콜 전체에서 유사한 패턴을 찾을 수 있습니다. 프로토콜에서는 모든 메시지가 발신인뿐만 아니라 수신인의 버킷도 업데이트합니다. 이러한 소프트 상태 프로토콜 설계를 통해 필요한 정보 기반의 설치 공간을 최소로 유지하는 매우 가벼운 오버레이 멤버십 관리를 할 수 있습니다.

​

초기 부트스트래핑 단계 이후, 각 카드캐스트 노드는 그것의 라우팅 정보를 업데이트하기 위해 네트워크를 발견하기 시작하는데, 이는 라이프사이클 동안 주기적으로 반복됩니다. 처음에 조인하는 노드는 자체 ID를 검색하여 자신의 네트워크 위치에 가깝게 배치된 노드 집합을 반환합니다. 또한 각 노드는 지난 한 시간 동안 일부 활동이 나타나지 않은 모든 버킷을 주기적으로 새로 고칩니다. 각 버킷에 대해 적절한 거리의 임의 ID를 선택하고 버킷을 새로운 라우팅 정보로 채우기 위해 조회 작업을 수행합니다.

​

조회 절차를 통해 노드는 주소 공간에서 특정 ID에 가장 가까운 k개 노드 집합을 검색할 수 있습니다. k개의 가장 가까운 노드를 찾는 방법은 검색 공간을 반복적으로 좁히고 ID에 더 가까운 노드에 FIND_NODE 메시지를 발행함으로써 수행됩니다.

(1) 노드는 자체 버킷에서 XOR 메트릭과 관련하여 α 가장 가까운 노드를 찾는다.

(2) 이 α 노드는 FIND_NODE 메시지를 전송하여 ID에 대해 쿼리한다.

(3) 쿼리된 노드는 획득된 정보에 기초하여 ID에 가장 가깝다고 믿는 k 노드 집합으로 응답한다.

(4) 노드는 새로운 노드 집합을 구축한다.

​

반복이 이미 알려진 노드보다 더 가까운 노드를 생성하지 않을 때까지 (1)–(3)단계를 반복적으로 반복합니다.

​

​

B. 메시지 전달 Message propagation

​

대부분의 블록 체인 네트워크는 블록 및 트랜잭션 처리를 위한 TCP 기반 전송 프로토콜에 의존하며, 패킷 손실 시 누락된 세그먼트를 재전송하여 임의로 큰 데이터의 신뢰성 있는 전송을 보장합니다. 이 방법은 암시적으로 수명이 긴 연결을 가정하고 연결 관리 측면에서 확장성이 떨어집니다.

​

대조적으로, UDP 또는 QUIC와 같은 전송 프로토콜은 Cadcast의 설계를 보완하는 단시간 저비용 전송으로 더 확장 가능하고 동적 접근을 가능하게 합니다. 다시 위의 그림을 보겠습니다. 노드 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는 알고리즘을 병렬화하여 브로드캐스트 중복화를 구현합니다. 이를 위해 버킷당 몇 개의 고유한 위임자(따라서 버킷당 몇 개의 노드)를 선택해야 하는지는 시스템 매개 변수 β입니다. 고장 확률 β와 β = 1이 주어지면, 단일 브로드캐스트 청크는 확률 p = 1 - β로 다음 홉에 도달할 것입니다. 따라서 이 청크를 수신하는 예상 노드 수는 노드 식별자의 균일한 무작위 분포로 인해 매우 그럴듯하게 높이 L의 균형 분포 트리를 가정하여 M = (1 + p)L로 나타낼 수 있습니다. 커버된 노드의 비율은 다음과 같습니다.

이를 더 확장시키기 위하여 알고리즘의 병렬 실행을 중복 전송 청크 중 적어도 하나가 성공적으로 전달될 확률(예: pβ=1−εβ)로 모델링 하겠습니다. 또한 X를 수신 청크의 수를 나타내는 랜덤 변수가 되게 하겠습니다. 따라서 블록 또는 트랜잭션의 모든 s 청크를 수신할 확률은 pb=P(X=s)=ps이며, 이는 µb=1-pb의 잘못될 확률을 유발합니다. 따라서 중복성 β로 메시지를 전달할 확률은 pb,β=1-ββb가 됩니다. 따라서 다음과 같은 기대 범위 비율이 산출됩니다.

​

​

그림2

그러나 위의 표처럼 최소한의 패킷 손실이라도 중복성이 없으면 블록 드롭을 즉시 제공할 가능성이 높아져 전체 네트워크를 커버할 가능성이 사실상 불가능합니다.

​

3) FEC 기반 블록 전달 분석

​

블록 전송 신뢰성을 더욱 높이기 위해 RaptorQ forward error correction을 사용하는 카드캐스트 노드는 이항 분포에 의해 모델링될 수 있는 이벤트인 전체 블록을 복구하기 위해 전송된 n개 이상의 임의 기호를 성공적으로 수신해야 합니다. 그림 2는 15% 중복성을 가진 FEC(forward error correction) 을 도입함으로써 향상된 전송 신뢰도를 보여줍니다(f = 0.15) 이 접근법은 최대 9%에 대한 packet loss에 대하여 브로드 캐스팅되는 것을 보장합니다.

​

그러나 이는 여전히 중복성(예: β > 1)과 FEC 접근방식을 결합함으로써 개선될 수 있습니다. 이 경우는 그림 2의 β = 3에도 나타나 있습니다. FEC와 병렬화의 조합은 전송 중에 평균 12%의 패킷이 손실되더라도 전체 네트워크 커버리지를 보장합니다.

​

분석 결과는 FEC가 신뢰할 수 없는 네트워크 인프라를 통해 신뢰할 수 있는 UDP 기반 데이터 전송을 보장하는것이 유리한 방법임을 보여줍니다. FEC는 상대적으로 작은 선형 오버헤드를 도입하면서 전파의 신뢰성을 크게 높일 수 있으며, 이와는 대조적으로 다수의 인자값인 β가 증가함에 따라 발생하는 오버헤드는 메시징 복잡성의 증가를 초래합니다.

​

하지만 악의적인 노드를 방지하기 위하여서도 이러한 중복성은 필요하기 때문에 종합해 보자면 다수의 β를 사용하는 병렬 처리와 + FEC를 도입하여 악의적인 노드를 효과적으로 방지할 수 있게됩니다.

​

KADCAST 보안 및 개인 정보 보호

KADCAST SECURITY AND PRIVACY

​

빠르고 공정한 블록 전파는 블록 체인 기반 시스템의 합의 계층에 있어 보안이 매우 중요한 것으로 간주됩니다. 그러나, p2p 네트워크와 블록 전파 메커니즘은 보안과 프라이버시에 대한 공격의 대상이 될 수도 있습니다. 따라서 카드캐스트 네트워크 프로토콜의 보안 및 개인 정보 속성에 대해 알아보겠습다.

​

A. 공격자 및 위협 모델

피어 투 피어 네트워크에 가입하는 적극적인 공격자를 가정해봅시다. 좀 더 구체적으로 말하면, 상대방은 다수의 노드를 실행하고 유지관리할 수 있는 수단과 자원을 가지고 있습니다. 적의 의도는 네트워크 전체를 공격하거나 네트워크의 전략적 위치를 점유하여 특정 노드를 격리하는 것이고 여기에는 네트워크 및 네트워크 사용자의 개인 정보뿐만 아니라 보안에 대한 공격도 포함된다고 가정하겠습니다.

​

1) 시빌 공격: 시빌 공격의 개념은 추가 신원을 위조하여 네트워크 실체의 대규모 숫자를 구체화하는 단일 공격자의 가능성을 가정합니다. 이를 통해 공격자의 노드는 분산 시스템에 참여하는 정직한 노드 수보다 많아져 시스템에서 악성 노드의 점유율을 효과적으로 증가시키는 것을 목표로 합니다. Kademlia 오버레이를 기반으로 하는 시스템에서 시빌 공격을 사용하여 공격 대상자의 버킷을 채울 수 있는 많은 ID를 생성할 수 있습니다. 이러한 종류의 공격을 실행할 수 있는 능력은 종종 Kademlia 기반 시스템에서 Eclipse 공격을 실행할 수 있는 전제 조건입니다. 카드캐스트의 경우, 공격자가 임의의 ID를 위조하고 가까운 위치에 위치할 수 있다면 공격자는 타겟으로 삼은 노드로부터 룩업과 브로드캐스트를 받을 가능성을 높일 수 있을 것입니다. 이를 통해 상대방이 블록 전달을 거부하여 블록 전파를 방해할 수 있습니다. 따라서 네트워크의 임의 위치에서 유효한 노드 식별자를 만드는 기능은 시스템의 보안에 해롭다고 볼 수 있습니다.

 

 

​

​

​

참고 문헌

​

오버레이 네트워크

https://slideplayer.com/slide/5701262/

​

구조화, 비구조화 p2p 오버레이 네트워크

https://www.researchgate.net/publication/261122904_UPDA_Uniform_Peer-to-Peer_Distribution_Algorithm_for_Mesh_Overlay_Paradigm

[출처] 논문 분석 01 초안) Kadcast-NG: A Structured Broadcast Protocol for Blockchain Networks|작성자 체인의정석