합의 알고리즘

합의 알고리즘은 블록체인과 같은 p2p 시스템에서 각 노드간 정보 도달의 시간차이가 있을 때 참가자들의 하나의 결과에 대한 합의를 얻기 위한 알고리즘입니다. 블록체인에서는 생성된 블록의 정당성을 검토하고 그 불록을 전체 블록체인에 반영하기 위해서 합의 알고리즘을 사용합니다.

작업 증명(PoW, Proof of Work)

PoW는 풀기 어려운 문제를 가장 빨리 해결한 사람에게 블록을 생성할 수 있는 권한을 주고 그 보상으로 코인을 제공하는 방식입니다. 비트코인의 경우는 무작위로 생성된 난수를 맞추는 문제를 제공하고 있으며, 약 10분 정도에 풀리도록 난이도 조절을 하고 있습니다. 난이도 조절은 이전 문제를 푸는데 걸리는 시간을 참고하여 너무 빨리 푼 경우는 난수의 자릿수를 늘리고, 너무 오래 걸린 경우는 난수의 자릿수를 줄이는 식으로 조절합니다.

또한 각 노드들의 데이터 전송 시간 차이로 인해 체인이 분기되는 경우가 발생할 수 있으며, 그런 경우 몇 번의 블록을 더 생성한 다음 가장 긴 체인을 올바른 것으로 판단하고 있습니다. 이 경우 짧은 체인에 있던 블록의 내용은 없던 일이 되기 때문에 계좌의 잔액이 바뀌거나 거래 자체가 없어지는 경우도 발생할 수 있습니다. 비트코인에서는 이런 경우를 방지하기 위해 거래가 확정되더라도 6블럭 정도를 추가로 기다리지 않으면 다음 거래를 할 수 없도록 제한을 두는 등의 방법을 적용하고 있으며, 이를 결제 완전성(Settlement Finality) 또는 파이널리티 불확실성(Finality Uncertainty)이라고 부릅니다. 파이널리티 불확실성은 금융 시스템에 도입되기 어려운 이유 중 하나가 되고 있습니다.

PoW는 다수결로 결정을 내리는 알고리즘이기 때문에 ‘51% 문제’가 발생할 수 있습니다. 블록체인은 해시 코드들의 체인이기 때문에 기존 내역을 변경하는 것은 상당히 어렵고, 특히 비트코인의 경우 모드 노드가 풀 가동시 약 10분에 하나의 해시값을 찾을 수 있을 정도이기 때문에 기존 내역을 변경하는 것은 불가능에 가깝습니다. 하지만, 51% 공격의 문제는 새로 생성하는 블록을 공격하는 점에 있습니다. 51퍼센트 공격을 하는 구체적인 방법은 다음과 같습니다.

• 해시 파워의 절반 이상을 가진 노드가 마이닝을 통해 해시값을 찾더라도 이웃 노드들에게 전파를 하지 않음
• 그리고 그 다음 블록을 계속해서 생성(과반수 이상의 해시 파워를 갖고 있기 때문에 다른 마이너들보다 긴 블록체인을 만들 수 있는 가능성이 높습니다.)
• 비트코인에서는 체인 분기시 짧은 체인은 파기하며, 가장 긴 체인을 올바른 체인으로 선정하기 때문에 해커들의 체인이 올바른 체인이 될 가능성이 높음

또한 PoW는 반복적인 연산을 계속해서 특정 값을 찾아내기 때문에 불필요한 연산을 많이 하게 되며 그로 인한 리소스 낭비(대표적으로 전기비)가 심하다는 단점이 있습니다. 또한 성능적인 제한도 있어 실시간성이 필요한 업무에는 적합하지 않습니다.

PoW는 모든 노드들이 트랜잭션 실행 결과를 검토해야 하기 때문에 각 노드들은 모든 블록 정보를 보유해야 합니다. 2016년 12월 기준으로 비트코인의 전체 블록들의 용량은 약 90기가 이상이었고 꾸준히 증가하고 있습니다. 향후에도 블록을 쌓을 때마다 용량이 증가해야 하고 1 블록의 용량 제한이 풀리거나 합의 시간이 단축되는 경우에는 전체 용량 증가 속도도 더 증가할 가능성이 있습니다.

이와 같이 PoW는 많은 단점들을 갖고 있는 합의 알고리즘이기 때문에 그 한계가 명확하며, 새로운 대안을 찾는 시도가 계속되고 있습니다.

지분 증명(PoS, Proof of Stake)

PoS는 PoW의 단점을 극복하기 위해서 나온 대안 중 하나이며, 블록을 생성할 수 있는 확률을 각 노드가 갖고 있는 토큰의 지분에 비례하도록 하는 알고리즘입니다. 합의에 필요한 리소스가 PoW에 비해 비약적으로 적으며, 속도 문제도 훨씬 개선이 된 알고리즘입니다. 하지만 PoS도 다음과 같은 문제점들을 갖고 있습니다.

PoS는 지분이 많을 수록 더 유리해지는 방식이므로, 각 노드들이 토큰을 수집하기만 하고 사용하지 않으려는 경향이 나타날 수 있습니다. 그래서 사용하지 않는 오래된 토큰에 대해서는 지분 평가를 떨어뜨리는 ‘Proof of Stake Velocity’라는 방식이 제안되고 있습니다.

또한 필요한 리소스 코스트가 너무 저렴하여 ‘아무 것도 수행하지 않는 문제(Nothing at Stake)’가 발생할 수 있습니다. 만약 체인이 분기되는 상황이 발생하게 되면, 각 노드들은 양쪽 체인 모두에서 같은 양의 지분을 갖고 있게 됩니다. 즉, 양쪽 분기 모두 대등한 체인이 되기 때문에 굳이 누군가 나서서 사태를 수습할 이유가 없습니다. 또한 양쪽 체인에 베팅이 가능하기 때문에 체인 분기를 고의로 노리고 계속 시도할 수 있다는 단점도 있습니다.

그리고 블록체인의 첫 번째 블록에 해당하는 제네시스 블록 시점에서 지분이 100%에 달하기 때문에 시스템을 개시한 사람은 몇 번이고 전체 블록을 다시 만들어낼 수 있다는 치명적인 문제가 있습니다. 그 외의 각 노드들도 지분만 갖고 있으면 그 시점부터 다시 시작하는 것이 가능하기 때문에 PoS만으로는 위변조를 막을 수 없습니다. 블록을 생성하는 코스트가 너무 낮기 때문에 이전 블록들로 거슬러 올라가서 현재까지의 모든 체인을 위변조할 가능성도 있습니다.

PBFT(Practical Byzantine Fault Tolerance)

PoW나 PoS와 마찬가지로 비잔틴 문제 해결로부터 시작되었지만, PoW나 PoS와는 달리 결제 완결성과 성능 문제를 해결한 합의 알고리즘입니다. 다만 모든 참가자를 알아야 하기 때문에 퍼블릭 블록체인에서 적용하기는 어렵습니다. 하이퍼레저(Hyperledger)나 Eris 등의 프라이빗 블록체인에서는 PBFT 알고리즘을 많이 채택하고 있습니다.

PBFT는 모든 노드를 알고 있어야 합니다. 노드 중 하나가 리더(Primary)가 되며, 자신을 포함해서 모든 노드들에게 요청을 보냅니다. 그리고 그 요청에 대한 응답을 집계한 다음 다수결을 이용해 블록을 확정합니다. PoW나 PoS와는 달리 의사 결정을 먼저 한 다음 블록을 생성하기 때문에 블록체인의 분기가 발생하지 않습니다. 따라서 결제 완결성을 지원하며, PoW처럼 해답을 찾기 위한 반복적인 연산 과정이 없기 때문에 필요한 리소스 코스트가 낮으며 훨씬 더 좋은 성능으로 동작합니다.

악의적인 사용을 하려고 해도 과반수 획득을 해야 하며, 누구나 노드로 참여할 수 있는게 아니라 허가된 노드만 참여하기 때문에 과반수 획득이 쉽지 않습니다. 또한 리더가 악의적인 행동을 했다고 판단이 되면 다수결을 통해 리더를 교체할 수도 있기 때문에 매우 강력한 보안을 갖고 있습니다.

하지만, 모든 노드를 알고 있어야 하고 전원의 의사 소통이 필요하기 때문에 노드가 증가할 수록 성능은 감소합니다. PoW나 PoS는 수천 개의 노드를 운영할 수 있지만 PBFT는 수십 개의 노드가 한계입니다.

Sieve

Sieve는 IBM에서 고안한 PBFT를 확장한 알고리즘입니다. 하이퍼레저에도 채택되어 있었으나 2016년 7월 대상에서 제외되었습니다.

실행 결과 전송과 집계 결과 전송으로 흐름을 나눈 것이 특징이며 합의를 형성하기 전 단계에서 실행 결과를 검토해 결과가 다른 경우 취소(Abort) 시킵니다. 각 노드들의 실행 결과가 다른 것을 초기에 탐지하고 싶을 때 유용한 알고리즘입니다. 집계 결과 전송에는 PBFT를 사용하는 경우가 많습니다.

Paxos

가장 유명한 합의 알고리즘 중 하나입니다. 단순하지만 합의 형성에 특화되어 있어 실제로 구현하기에는 어려움이 많습니다.

Paxos의 특징은 과반수의 동의를 얻었다면 그 동의 내용이 나중에라도 변경되는 일이 없다는 점입니다. 리더에 의해 합의 형성을 수행하지만 비잔틴 장애 허용 모델은 아니기 때문에 리더가 악의적인 행동을 하거나 멤버가 거짓으로 신고한 경우 정상적인 동작을 하지 않기 때문에 악의를 가진 참가자가 존재할 수 있는 환경에서는 적합하지 않은 알고리즘입니다.