ICON (ICX)을 공부하는 중 합의 알고리즘 (Consensus algorithm)인 LFT를 이해하기 위해 정리해봅니다.
아래 그림은 PBFT 합의 알고리즘의 도식도입니다. PBFT 기반 합의 알고리즘은 비잔틴 장애를 극복하기 위해 합의 결과를 네트워크의 모든 노드에 2번에 걸쳐 전파하기 때문에 많은 통신량으로 인한 성능 저하가 일어날 수 있습니다.
LFT는 비잔틴 문제를 해결하기 위한 Raft 알고리즘인 Tangaroa를 블록체인에 적합하게 개선한 합의 알고리즘으로 PBFT의 많은 통신량 문제를 개선하였고 기존 알고리즘의 복잡한 리더 선정 알고리즘을 단순화하고 리더의 요청 무시 문제를 최소한 경량화된 고성능 합의 알고리즘입니다.
리더 노드와 검증 노드로 구성되는데, 리더 노드는 새로운 블록을 생성하고 검증 노드는 리더가 생성한 블록을 검증하고 검증 결과를 투표하는 임무를 수행합니다.
네트워크에 참여하는 각 노드는 비잔틴 노드에 의한 메시지 조작을 방지하기 위하여 공개키 기반 구조를 가집니다. 모든 노드는 네트워크에 참여하는 노드들의 공개키와 각 노드의 리더 순번을 알고 있습니다.
네트워크의 정상적인 노드는 리더가 보낸 생성될 예비 블록에 대하여 유효 투표와 실패 투표 단 한 번만 수행하며 비잔틴 노드는 네트워크 분기와 정지를 위해 악의적인 메시지를 횟수에 상관없이 전송할 수 있습니다.
LFT 알고리즘은 2단계 합의 알고리즘입니다. 1번째 단계에서 리더가 블록을 만들어 다른 모든 검증 노드들에게 전달하면 2번째 단계에서 각 검증 노드들은 블록과 그에 대한 투표 결과를 다른 모든 노드에게 전파합니다. LFT 알고리즘은 f가 비잔틴 노드의 갯수라고 할 때 3f+1 이상의 노드가 존재하는 상황에서 비잔틴 장애를 극복할 수 있으며 ,정족수 n-f인 합의 알고리즘입니다. 또한 각 노드는 Local Timer를 가지고 있어 리더의 통신 장애를 감지합니다.
LFT 알고리즘은 Tangaroa 알고리즘과 유사하지만, 리더 실패에 대한 해결 방안이 다르고 투표 메시지를 충분히 받지 못한 노드를 방지하기 위한 대응 방안을 추가했다는 점이 다릅니다.
위 그림은 LFT 합의 알고리즘의 도식도입니다. 각 순서에 따른 내용들은 다음과 같습니다.
합의가 시작되면 검증 노드들은 리더 노드에 처리하기 원하는 트랜잭션을 전송합니다. 리더 노드는 수집한 트랜잭션을 이용하여 블록을 생성하고 자신의 서명과 함께 다른 모든 검증 노드에 전송합니다. (Broadcast Block)
각 검증 노드들은 블록을 받으면 1) 현 리더가 블록을 생성했는지 확인, 2) 블록의 높이와 이전 블록 해시가 올바른지 확인, 3) 블록의 메시지가 올바른지 확인합니다. (Verify Block)
검증 노드는 검증 결과에 따라 투표 메시지를 모든 노드들에게 보냅니다. (Broadcast Vote)
투표 메시지를 모든 노드들에게 전파하는 것은 중요합니다. 리더 노드가 비잔틴 노드일 경우 정족수 이상의 노드들에게만 블록을 전파하여 특정 노드들을 네트워크로부터 분리하도록 시도할 수 있습니다. 이러한 문제를 방지하기 위해 모든 노드들에게 투표 메시지를 전파합니다.
각 노드가 정족수 이상의 투표를 받게 되면 해당 높이의 블록을 자신의 블록체인에 추가할 수 있습니다. (Count Vote)
다음 리더 노드는 정족수 이상의 투표를 받으면 해당 높이의 블록생성을 성공으로 취급하고 다른 노드에서 받은 트랜잭션을 모아 새로운 높이의 블록을 생성하고 다른 모든 노드에 새로운 높이의 블록 메시지를 보냅니다. 생성된 블록이 제니시스 블록이 아닌 경우 검증 노드들은 앞서 검증한 1)~3) 외에 블록에 포함된 이전 블록 투표 검증 메시지들이 올바른지 검증합니다. 투표 메시지 공유 시 정족수 이상의 투표를 받지 못한 노드도 이전 블록을 자신의 블록체인에 추가할 수 있습니다. (Broadcast New Block & Commit Prev Block)
기존 PBFT처럼 모든 state machine에 응답을 보장하는 것이 아닌 각 노드가 서비스를 제공하고 트랜잭션을 생성하기 때문에 리더 노드가 블록 생성 시 특정 노드의 트랜잭션을 거부할 경우 문제가 생길 수 있습니다.
LFT는 이를 최소화하기 위해 Spinning 기법을 이용해 매 블록 생성 시마다 리더를 교체하여 비잔틴 리더에 의해 발생할 수 있는 서비스 장애 요소를 줄였습니다.
- 개인적으로 내용을 정리하기 위한 포스팅입니다.
포스팅 내용은 LFT 백서 내용을 토대로 작성되었습니다.
LFT 백서
https://loopchain.files.wordpress.com/2017/07/lft-e18487e185a2e186a8e18489e185a5.pdf
[스팀잇을 건강하게 하는 캠페인]
#ourselves 캠페인
셀프보팅을 하지 않고 글을 올리시고
ourselves 태그를 달아 주시면
많은 분들이 관심 가져줄꺼에요.