로그인

검색

[17-08] 인사이드 아이콘 (2): 루프체인 합의 알고리즘

똥글왕김똥글

출처: https://brunch.co.kr/@helloiconworld/13

 

 

 

LFT

드디어 루프체인의 합의 알고리즘인 LFT를 소개하겠습니다. LFT 또한 철수, 영희, 동수의 마피아 게임(PBFT)과 같은 계열의 합의 알고리즘입니다. 자세한 기술백서는 아래 파일에서 보실 수 있습니다. 

 

Loopchain Fault Tolerance Algorithm.pdf

 

기존의 상태 머신 복제 프로토콜중 하나인 Raft를 비잔틴 노드의 공격을 극복할 수 있도록 개선한 알고리즘 입니다. LFT는 현재 loopchain에서 사용하는 합의 알고리즘입니다. 그러나 loopchain은 Pulgin형태로 합의 알고리즘이 구현되어있기 때문에 필요에 따라 PBFT와 같은 다른 합의 알고리즘을 사용할 수 있습니다. 

 

LFT 는 이번 블록의 투표 내역이나 메시지를 통합하여 전반적인 통신량을 감소시키는 Piggybacking 방법을 이용하였습니다. 또한 리더 노드(게임의 사회자) 를 매번 교체시키는 Spinning 기법을 이용하였습니다. 이로써 악의적인 노드(마피아 동수)가 투표에는 영향을 못미치지만 네트워크에 문제를 일으킬 수 있는 트랜잭션 거부 문제, 그리고 리더 노드(사회자)에 의한 네트워크 지연과 같은 문제를 해결하였습니다. 이로써 LFT는 기존 합의 알고리즘이 갖고 있던 복잡성(complexity)를 줄였습니다. 

 

1.png

LFT Normal Process

 

 

네트워크가 시작되면 검증 노드(검증을 통해 합의에 참여하는 노드)들은 사전에 결정되어 있는 리더 노드에게 처리를 원하는 트랜잭션을 전송합니다. 리더 노드는 수집한 트랜잭션을 이용하여 블록을 생성하고 자신의 서명과 함께 다른 모든 검증 노드에게 전송합니다.

 

 

각 검증 노드들은 블록을 받으면 

 

1. 현 리더가 블록을 생성했는지 확인하고  

2. 블록의 높이와 이전 블록 해시가 올바른지 확인한 후, 

3. 블록의 데이터가 올바른지 확인합니다. 

 

 

Vote 데이터를 전체 노드에게 전파하는 것은 매우 중요한데 이는 리더 노드가 비잔틴일 경우 정족 수 이상의 노드들에게만 블록을 전파하여 특정 노드들을 네트워크로 부터 분리하도록 시도할 수 있기 때문입니다. 이러한 문제를 방지하기 위해 모든 피어에게 Vote 데이터를 전파하며 이는 기존 Raft 알고리즘과의 다른 점입니다. 이 과정에서 블록을 못받은 노드는 블록이 생성되었는지에 대한 정보를 알 수 있고 다른 노드에게 블록을 요청할 수 있습니다.

 

 

 

 

다시 한번 마피아 게임의 예를 들어 볼까요? 

 

게임이 시작되면 철수, 영희, 동수는 자신이 보낼 메시지와 선물상자를 사회자에게 전달합니다. 철수가 영희에게 이번에도 500원을 보내고 싶어합니다. 동수는 철수의 500원을 받고 싶어합니다. 

 

 

2.png

 

 

이제 첫 날이 밝았습니다(Broadcast Vote). 사회자는 모든 쪽지를 받아서 500원이 든 3개의 선물상자를 만듭니다. 사회자는 선물상자에 자신의 이름을 적고(서명) 3명에게 다시 나누어 줍니다. 철수, 영희, 동수는 이제 다음과 확인 작업을 시작합니다.

 

4.png

 

 

1. 먼저 사회자의 글씨가 맞는지 확인하고(리더 서명 검증)

2. 선물상자의 크기와 번호가 올바른지 확인하고 기록합니다.(블록 높이와 해시 확인)

3. 철수, 영희, 동수는 안에 든 메시지도 다같이 꺼내 읽어 봅니다. (Verify Block)

4. 철수, 영희, 동수는 메시지를 복사해서 다른 사람 모두와 공유합니다. (Broadcast Vote)

 

 

‘철수가 영희에게 500원을 보낸다’라는 메시지가 정족수 즉 2/3 이상이라면 모두가 선물상자를 가질 수 있습니다(Count Vote). 또한 선물상자에는 모든 메시지와 선물 주고 받은 내역이 기록되어야만 합니다. 

 

 

게임 참여자들은 룰을 정해서 순서대로 공평하게 사회자를 맡기로 했습니다. 이제 철수가 사회자를 맡을 차례이네요. 철수는 모든 절차가 잘 진행되었는지 받은 선물 상자를 뜯어 보고 알 수 있습니다.(블록에 포함된 이전 블록 투표 검증 메시지들이 올바른지 검증). 이렇게 돌아가면서 사회자를 맡다 보면, 한 사람이 중간에 오류를 내거나 악의적인 메시지를 보낼 장애 요소를 줄일 수 있습니다. 

 

 

 

리더 장애 극복 시나리오 

 

그렇다면, 만약에라도 사회자가 나쁜 마음을 먹었다면 철수와 영희의 거래는 어떻게 되는 걸까요? 

 

다음과 같은 경우는 이번에는 사회자가 악의적으로 게임의 룰을 어긴 경우입니다. 사회자가 자신의 이름을 적은 0번 선물상자를 영희와 동수에게 주지 않아 버립니다. 그렇다면 철수만 선물상자를 영희와 동수에게 주고, 3명(2f+1)의 투표는 무효화 되어 버립니다. 

 

 

여기서 말하지 않은게 있었네요. 모든 게임은 타이머가 울리기 전에 진행되어야 한다는 것입니다. 이로써 이 마피아 게임은 더욱 많은 참여자가 자유롭게 게임에 들어올 수 있도록 설계되었습니다(많은 노드가 참여할 수 있는 블록체인 네트워크) 

댓글 0개