Safety and Liveness
분산 시스템의 딜레마
DSRV Research는 더 많은 사람이 Web3를 이해하고 참여하는 데 기여하기 위해, 블록체인과 관련된 지식을 연재합니다.
Disclaimer: 이 글은 정보 전달을 위한 목적으로 작성되었으며, 특정 프로젝트에 대한 투자 권고, 법률적 자문 등을 목적으로 하지 않습니다. 모든 투자의 책임은 개인에게 있으며, 이로 발생된 결과에 대해 어떤 부분에서도 DSRV는 책임을 지지 않습니다. 본문이 포괄하는 내용들은 특정 자산에 대한 투자를 추천하는 것이 아니며, 언제나 본문의 내용만을 통한 의사결정은 지양하시길 바랍니다.
Safety와 Liveness: 분산 시스템의 딜레마
DSRV Research는 합의 알고리즘을 둘러싼 논의를 살펴보면서 블록체인들이 왜 각자 다른 합의 알고리즘을 채택했는지, 각각 어떤 특성이 있는지 알아보기 위한 이론적인 틀을 잡고자 합니다. 또한 이후에 이더리움 2.0 시리즈에서 ‘캐스퍼’를 이해하기 위한 배경지식으로 본문이 사용될 예정입니다.
[이더리움 2.0 시리즈]
0. Safety and Liveness
1. Casper, the Friendly Finality Gadget
2. LMD Ghost
3. Gasper
4. Ethereum Beacon Chain
5. Horizontal Scaling Solution: Sharding
분산된 시스템에서의 합의
블록체인이란 무엇일까요? 허공에서 ‘블록’이라는 것이 찍히고, 그 블록 다음에 철수의 블록을 연결하고, 그다음은 영희의 블록을 연결해서 하나의 체인을 만드는 것을 저희는 ‘블록체인’이라 이해합니다.
그러나 물론, 블록은 허공에서 뚝 떨어지지 않습니다. 철수와 영희의 컴퓨터가 블록을 만들어내고, 이전에 존재하던 체인에 이어 붙입니다. 이때 철수와 영희는 각자의 컴퓨터에 블록체인을 다운로드받아 가지고 있습니다. 그렇게 다운로드받은 블록체인이 동일한 내용을 포함하고 있어야 하나의 블록체인을 운영한다고 할 수 있을 것입니다. 그렇지만 철수가 새로 붙이는 블록과 영희가 새로 붙이는 블록을 서로에게 비밀로 한다면 어떻게 될까요? 철수의 블록체인과 영희의 블록체인이 서로 다른 것이 될 것입니다.
블록체인은 허공에 이어붙이는 블록들이 아닙니다. 출처: DSRV Research.블록체인에서 말하는 ‘합의’란, 이러한 일을 방지하기 위한 메커니즘입니다. 블록을 생성하고 블록체인을 유지하는 채굴자, 혹은 검증인들이 기존의 체인에 새롭게 철수의 블록을 더할 것인지, 영희의 블록을 더할 것인지를 ‘합의’하고, 철수가 만든 블록을 더하기로 결정했다면 모두의 컴퓨터(이하 노드)에 철수가 만든 블록을 새롭게 업데이트하여 모두 같은 내용의 블록체인을 유지하도록 규칙을 정하는 것이 바로 합의 알고리즘입니다. 만약, 블록체인을 단 하나의 주체가 운영한다면 어떨까요? 혼자서만 사용하는 기철이의 블록체인은 합의할 필요도 없이 블록을 계속 연결해나갈 수 있을 것입니다. 그러나 위에서 말했던 철수와 영희, 그리고 다른 많은 주체들이 하나의 블록체인을 운영하는 ‘분산된’ 환경에서는 위에서 말했던 합의의 과정이 필수적입니다.
동기성(Synchronicity)과 비동기성(Asynchronicity)
우리가 아는 비트코인, 이더리움, 코스모스 그리고 여타 다른 체인들은 각자의 고유한 합의 알고리즘을 가지고 있습니다. 합의 알고리즘은 분산된 환경에서 ‘어떻게’ 합의에 이를 것인가에 대한 구현이기 때문에 여러 방식이 존재할 수 있습니다. 어려운 수학 문제를 내고, 가장 빨리 푸는 채굴자가 제안한 블록을 체인에 연결하자는 방식이 될 수도 있고, 아니면 검증인들이 가지고 있는 지분량에 비례하여 더 많은 지분을 가진 사람이 더 높은 확률로 블록을 제안할 수 있도록 하자는 방식이 될 수도 있습니다.
각 노드 간 어떤 블록을 연결할 것인지 합의하기 위해서는 통신이 필요합니다. 누가 어떤 블록을 생성했는지 알아야 하고, 또 여러 채굴자들이 제안한 여러 개의 후보 블록들이 있다면 그중 어떤 것을 최종적으로 선택하여 체인에 연결해야 할지를 알아야 하기 때문입니다. 이때, 노드 간 통신을 ‘메시지(message)를 주고받는다’[1]라고 표현합니다. 분산된 환경에서 ‘어떻게’ 합의에 이를 것인가를 결정하는 합의 알고리즘에서 중요하게 고려되는 부분 중 하나가 바로 ‘어떻게 메시지를 주고받을 것인가’에 대한 것입니다.
메시지를 주고받는 방법은 크게 두 가지로 나누어 볼 수 있는데, 결국 시스템을 구성하는 요소들끼리 얼마나 조직화되었는가를 기준으로 나누는 것입니다.[2]
동기 네트워크(Synchronous Network)
동기 네트워크는 메시지가 무한히 지연되지 않는 네트워크를 말합니다.
현재 작업의 응답과 다음 작업 요청의 타이밍을 일치시키는 것이 바로 동기성입니다. 즉, 동기성은 현재 작업이 끝나면 다음 작업이 시작되는 식으로 ‘작업의 순서가 보장되는 것’으로 이해할 수 있습니다. 예시를 통해 동기 네트워크를 이해해보겠습니다. 어떤 동기 네트워크에서 특정 노드는 10초간의 1라운드에서 다른 노드들에게 메시지를 전송하고 다시 10초간의 2라운드에서는 다른 노드들로부터 메시지를 전달받아 연산을 처리합니다. 이렇게 시간이 정해진 라운드별로 노드 간 어떤 메시지를 주고받을 것인가가 정해져 있는 동기 네트워크는 메시지를 보내고, 응답이 오면 다음 작업을 시작하는 식으로 작업의 순서가 보장되기 때문에 조직화 정도가 높다고 말할 수 있습니다.
메시지가 다른 노드에게 전송되었을 때는 지연이 발생하기도 합니다. 하지만 동기 네트워크 환경에서는 메시지 지연의 Timeout, 즉 시간적인 제한이 존재하기 때문에 무한히 메시지가 지연될 수 없습니다.[1] 동기 네트워크에서는 작업의 순서가 보장되기 때문에 메시지가 무한히 지연되어 응답되지 않는다면 영원히 다음 작업을 실행할 수 없기 때문입니다.
분산된 합의 알고리즘에서 동기성은 종종 하나의 중앙화된 시간 동기화 서비스에 의존하게 됩니다. 한국에 사는 철수와 미국에 사는 엘리스 모두 시간이 얼마나 흘렀는지 동일하게 이해하고 있어야 하기 때문입니다. 만약 철수와 엘리스가 이해하는 시간이 5초가 차이 난다면, 철수는 아직 1라운드인데 엘리스는 2라운드에 이미 들어가는 등의 치명적인 문제가 발생할 수 있기 때문입니다. 이렇게 만약 단일한 시간 동기화 서비스가 조작된다면 합의 알고리즘이 정상적으로 작동할 수 없다는 위험이 존재하기 때문에, 분산된 합의 알고리즘을 설계하는 데에 있어서는 동기성을 최소화하고자 합니다.
비동기 네트워크(Asynchronous Network)
비동기 네트워크는 메시지가 무한히 지연될 수 있는 네트워크를 말합니다.
동기성과는 반대로 비동기성은 현재 작업의 응답이 오지 않아도 다음 작업으로 넘어갈 수 있음을 의미합니다. 즉, 현재 작업이 끝나지 않아도 다음 작업이 시작될 수 있기 때문에 ‘작업의 순서가 보장될 필요가 없음’으로 이해할 수 있습니다.
따라서 비동기 네트워크는 동기 네트워크와 반대로 조직화 정도가 굉장히 낮습니다. 비동기 네트워크를 구성하는 노드들은 라운드 별로 정해진 행동을 하는 것과 같은 조직화 법칙에 따르지 않습니다. 마찬가지로 비동기 네트워크 환경에서는 동기 네트워크와는 달리 메시지를 전송했을 때 지연의 시간적인 제한이 존재하지 않아 무한히 메시지가 지연될 수 있습니다.
간단하게 이해하자면, 동기 네트워크와 비동기 네트워크의 차이는 바로 동기화된 시계(synchronized clocks)에 대한 접근이 반드시 필요한가 혹은 필요하지 않은가, 메시지가 무한히 지연될 수 없는가, 혹은 있는가에 있습니다.
M. Fisher, N. Lynch, 그리고 M. Paterson의 논문 ”Impossibility of Distributed Consensus With One Faulty Process”[1]는 여기서 굉장히 중요한 문제를 제기합니다. 비동기 네트워크에서 작동하는 합의 알고리즘을 만드려고 했지만, 바로 ‘비동기 네트워크 환경에서는 Safety와 Liveness를 동시에 만족시키는 분산된 합의 알고리즘이 존재할 수 없다’를 수학적으로 증명했기 때문인데요. [4] Safety와 Liveness가 도대체 무엇인지 더 자세히 알아보겠습니다.
Safety와 Liveness
Safety와 Liveness, 직관적으로는 어떤 의미인지 잘 와닿지 않는 것 같은데요, 조금은 풀어서 알아보겠습니다.
Safety
만약 합의가 이루어졌다면, 모든 정상적인 노드는 동일한 값에 접근 가능합니다. 즉, 철수와 영희가 정직하게 노드를 운영한다면, 서로 다른 블록체인이 아닌 하나의 같은 블록체인을 각각 유지할 수 있습니다. 우리가 아는 블록체인을 기준으로 말한다면 Safety가 보장되지 않을 경우, 같은 블록 높이에 두 개의 블록이 생성될 수 있습니다. 즉, 포크가 발생할 수 있습니다.
Liveness
모든 정상적인 노드는 결국 합의에 도달합니다. 만약 Liveness가 보장되지 않을 경우 분산된 시스템을 구성하는 노드들이 무한히 합의에 도달하지 못하는, 즉 새로운 블록이 계속해서 만들어지지 않는 상태가 유지될 수 있습니다.
비동기 네트워크 환경에서 Safety와 Liveness를 동시에 만족시키지 못한다는 것은, 결국 둘 중 하나를 어느 정도 포기해야 한다는 것을 의미합니다.
Liveness를 보장하는 대신 Safety를 어느 정도 포기한다는 것
모든 정상적인 노드가 동일한 값으로 (블록체인에서는 모든 노드가 하나의 블록으로) 합의하지 못하는 경우가 생기더라도 우선 부분적인 합의를 하여 체인을 멈추지 않게 하는 것(즉, 서로 다른 두 개의 블록이라도 블록을 우선 생성하는 것)을 더 중요하게 생각합니다. 네트워크 지연으로 인하여 포크가 발생할 수 있는 비트코인의 나카모토 컨센서스가 대표적인 예시입니다.
Safety를 보장하는 대신 Liveness를 어느 정도 포기한다는 것
모든 정상적인 노드가 동일한 값(하나의 블록)으로 합의하지 못한다면, 합의가 이루어지지 않은 것(블록을 생성하지 않는 것)으로 합니다. 모든 검증인들이 하나의 블록에 합의하고, 다음 블록을 생성하는 단계로 넘어가는 코스모스 계열의 블록체인이 대표적인 예시입니다.
Liveness: 나카모토 컨센서스와 체인 기반 지분 증명
나카모토 컨센서스
DSRV Research에서 다루었던 나카모토 컨센서스를 기억하시나요? 비트코인에서는 네트워크 지연 등의 이유로 동시에 두 블록이 생성되어 체인이 두 갈래로 나뉠 수 있다는 것을 알아보았습니다.
나카모토 컨센서스에서의 포크 발생. 출처: DSRV Research.비트코인 채굴자들은 세계 곳곳에서 노드를 운영하고 있기 때문에 노드 간 통신에 있어 약간의 시차가 발생할 수밖에 없습니다. 만약 서울의 채굴자와 뉴욕의 채굴자가 거의 동시에 논스값을 찾아내는 데 성공한다면 동시에 두 블록이 생기는 현상, 즉 포크(fork)가 발생합니다. 이렇게 포크가 발생하는 이유는 포크를 허용하도록 나카모토 컨센서스가 설계되었기 때문인데요, 바로 여기서 Safety보다 Liveness를 우선시하는 의도를 찾아볼 수 있습니다. 비트코인 네트워크에 참여하는 모든 정상적인 노드들이 그림에서 위의 블록과 아래의 블록 중 어떤 것을 선택할지 합의하지는 못했지만 그럼에도 불구하고 우선 두 개의 블록이 모두 생성되고 그 뒤로 체인이 연결됩니다.
물론, 포크가 지속되는 상황은 이중지불을 가능하게 만든다는 점에서 비정상적인 상황입니다. 따라서 나카모토 컨센서스에서는 이후 ‘어떤 포크가 더 많은 연산을 실행한 결과인가’에 따라 둘 중 하나의 포크를 선택합니다. 위의 그림에서 만약 아래의 포크가 선택된다면, 위의 포크에는 포함되었지만 아래의 포크에는 포함되지 않았던 트랜잭션들은 취소되는 상황이 발생할 수 있습니다. 이러한 상황이 바로 Safety를 어느 정도 포기하기 때문에 발생하는 문제라고 할 수 있습니다. 그러나 시간이 지나면서 둘 중 하나의 포크가 선택될 확률이 100%에 수렴하게 되고 모든 정상적인 채굴자들 사이에 ‘어떤 체인이 정본인가’(즉, 어떤 체인이 Canonical Chain인가)에 대한 합의가 이루어진다고 볼 수 있기 때문에 Safety 또한 부분적으로는 만족된다고 볼 수 있습니다. (Fork Choice Rule에 대한 자세한 내용은 DSRV Research의 나카모토 컨센서스 아티클에서 읽어보실 수 있습니다.)
체인 기반 지분증명, 피어코인(Peercoin)
지분증명에 대한 연구가 이루어지던 초기에 개발되었던 블록체인인 피어코인(Peercoin) 또한 나카모토 컨센서스와 같이 Safety보다 Liveness를 우선으로 하는 합의 알고리즘을 사용합니다. 피어코인의 합의 알고리즘은 나카모토 컨센서스와 매우 유사하지만, 결정적으로 새로운 블록을 생성하는 방식이 약간 다릅니다.[5][6]
피어코인의 체인 기반 지분증명. 출처: DSRV Research.피어코인은 “coin-age”라는 개념을 도입합니다. 만약 철수가 10개의 코인을 5일 동안 가지고 있었다면 철수는 10 * 5, 즉 50 coin-days를 축적하게 됩니다. 철수가 가지고 있는 coin-age가 시간이 지남에 따라, 혹은 더 많은 코인을 구매함에 따라 늘어나게 되면 철수는 축적된 coin-age를 소모함으로써 점점 더 적은 양의 작업증명 연산으로 더 쉽게 블록을 생성할 수 있게 됩니다. 즉, Liveness를 우선시하는 나카모토 컨센서스와 매우 비슷한 방식을 사용하지만, 각자 얼마만큼의 지분을 얼마 동안 가지고 있었는지에 따라 채굴자별로 블록을 채굴하기 위한 문제의 난이도를 조절하는 방식입니다. 이러한 방식을 ‘체인 기반 지분증명’이라고 합니다.
피어코인에서의 포크 선정 메커니즘. 출처: DSRV Research.피어코인 또한 Liveness를 우선시하기 때문에 비트코인처럼 포크가 발생할 수 있습니다. 따라서 피어코인에도 또한 둘 중 하나의 포크를 선택하는 메커니즘, 즉 Fork Choice Rule이 존재합니다. 비트코인에서의 Fork Choice Rule이 ‘어떤 포크가 더 많은 연산을 실행한 결과인가’였다면 피어코인은 ‘어떤 포크가 더 많은 coin-age를 사용한 결과인가’에 따라 둘 중 하나의 포크를 선택합니다.
Fork Choice Rule은 Liveness를 우선시하는 합의 알고리즘에서도 Safety를 어느 정도는 보장하기 위해 필요합니다. Liveness를 Safety보다 우선시하기 때문에 포크가 발생하지만, 블록 생성 이후에라도 여러 포크 중 하나의 포크만을 선정하는 Fork Choice Rule에 의하여 이후 모든 노드들이 하나의 포크에 접근할 수 있도록 하기 때문입니다. 그러나 Fork Choice Rule이 제대로 작동하지 않을 경우, Safety를 보장하는 것이 어려워질 수 있습니다. 피어코인이 바로 그 예시입니다.
피어코인은 포크가 발생했을 때, 이후 채굴자들이 두 개의 포크 중 하나를 선택하여 그 위에 블록을 생성할 필요 없이 두 포크 위에 모두 블록을 생성하도록 경제적인 유인이 작용하는 ‘Nothing-at-stake’ 문제를 발생시킵니다.[7] Noting-at-stake는 말 그대로 채굴자가 두 개의 포크 중 굳이 하나를 선택하여 블록을 생성하지 않아도 ‘잃을 것이 없는’ 상황을 말합니다.
작업증명 기반의 나카모토 컨센서스에서 채굴자는 블록을 생성하기 위하여 엄청난 양의 연산을 수행해야 합니다. 이 과정에서 노드 운영비용, 전기 사용료 등 상당한 비용이 발생하게 되는데, 만약 그러한 자원을 사용하여 생성한 블록이 이후 Fork Choice Rule에 의하여 선택되지 않은 포크에 포함된다면 블록 보상을 받을 수 없게 됩니다.[8] 따라서 채굴자는 이후 Fork Choice Rule에 의하여 선택될 포크 위에만 블록을 생성하도록 경제적 유인이 발생합니다. 두 포크 위에 블록을 각각 생성할 수도 있지만, 그렇게 하기 위해서는 블록을 하나만 생성할 때보다 두 배의 자원을 소비해야 합니다. 즉, 이러한 경우는 Fork Choice Rule에 의하여 하나의 포크가 선택될 경우 선택되지 않은 다른 포크에서 ‘잃을 것이 있는’ 상황이 됩니다.
피어코인의 “Nothing-at-Stake” 문제. 출처: DSRV Research.반대로 피어코인의 경우, 나카모토 컨센서스처럼 자원 소비를 통한 연산으로 블록을 생성하는 것이 아닌, coin-age를 소비하여 블록을 생성합니다. coin-age를 사용하면, 모든 포크에서 추가적으로 블록을 생성할 수 있습니다. 따라서 하나의 블록을 생성하는데 필요한 coin-age를 사용하여 다른 포크에 각각 하나의 블록을 생성할 수 있습니다. 이후에 Fork Choice Rule에 의하여 어떤 포크가 선택되더라도 블록 생성자는 두 포크 모두에 블록을 생성했기 때문에 블록 보상을 받을 수 있게 됩니다. 문제는 모든 블록 생성자가 둘 중 하나의 포크를 선택하여 해당 포크에서만 블록을 생성하는 것이 아니라 계속해서 모든 포크에 블록을 동시에 생성할 경우, 더 많은 coin-age를 소비한 포크를 선택하는 Fork Choice Rule에 의해서는 둘 중 하나의 포크가 영원히 선택되지 않는 문제가 발생합니다. 계속해서 포크가 두 갈래로 존재한다면 단 하나의 포크로 합의되지 않은 상태, 즉 Safety가 만족되지 않은 상태로 포크가 계속해서 존재하게 되는, 즉 포크를 장려하는 문제가 발생합니다.
Safety: PBFT 합의 알고리즘
PBFT는 Practical Byzantine Fault Tolerance의 약자로 Liveness보다 Safety를 우선시하는 대표적인 합의 알고리즘입니다. 코스모스 SDK의 텐더민트 합의 알고리즘과 유사한데, 본문에서는 텐더민트가 아닌 PBFT를 기준으로 설명하겠습니다.
정상적인 상황에서의 PBFT 작동 방식. 출처: M. Castro and B. Liskov. Practical Byzantine Fault Tolerance.위의 그림은 PBFT 합의 알고리즘이 작동하는 방식입니다. 왼쪽에 있는 C는 블록체인을 구성하는 노드들에게 최초로 요청을 전송하는 사용자인 클라이언트, 0, 1, 2, 3은 각각 노드를 뜻합니다. 위의 그림만 보았을 때는 헷갈리기 쉽지만, 클라이언트는 블록체인 네트워크를 구성하는 노드가 아닌, 트랜잭션을 발생시키는 사용자입니다. PBFT 합의 알고리즘에서는 Request, Pre-prepare, Prepare, Commit, Reply 총 다섯 단계를 거쳐 합의가 이루어지고, 이것의 결과로 블록체인의 맥락에서는 하나의 블록을 생성하게 되는데, 각 단계는 DSRV’s Tip에서 설명합니다. (설명된 내용을 건너뛰더라도 본문의 내용을 이해하는 데에는 지장이 없습니다.)
� DSRV’s Tip; PBFT 작동 방식 설명
1. Request: 클라이언트 C가 이번 합의 과정을 리드하는 노드인 0번 노드(Primary 노드라고 합니다)에게 요청을 전송하고, 0번 노드는 요청을 받아 기록합니다.
2. Pre-prepare: Primary 노드인 0번 노드가 나머지 노드인 1, 2, 3번 노드에게 (Backup 노드라고 합니다) 메시지를 전송합니다. Backup 노드들은 Primary가 전송한 메시지가 유효한지 검증한 후, 유효하다면 메시지를 수신합니다.
3. Prepare: Backup 노드들은 다시 다른 모든 노드들에게 메시지를 전송합니다. 그리고 다른 노드들로부터 수신받은 메시지가 Pre-prepare 단계에서 수신한 메시지와 같은 정보를 담고 있으며 또한 유효하다면 메시지를 기록합니다. 그리고 Primary 노드를 제외한 노드 수의 2/3만큼의 메시지들이 Pre-prepare 단계에서 수신한 메시지와 매치되는지 체크합니다. 모두 성공적이었다면 Prepare 단계가 종료됩니다.
4. Commit: 모든 노드들은 다시 다른 모든 노드들에게 메시지를 전송합니다. 역시 Pre-prepare 단계에서 수신한 메시지와 새롭게 수신받은 메시지가 매치하면 메시지를 기록하는데, 이때는 전체 노드 수의 2/3보다 많은 수의 메시지가 Pre-prepare 단계에서 수신한 메시지와 매치되는지 체크합니다. 성공적이었다면 클라이언트 C의 요청을 처리합니다.
5. Reply: 모든 노드들은 클라이언트 C에게 요청을 처리한 결과를 메시지로 전달합니다. 클라이언트 C는 전체 노드 수의 1/3보다 많은 유효한 메시지를 받았는지 체크하고, 요청의 처리 결과를 받아들입니다.
PBFT 합의 알고리즘에 대한 더 자세한 내용은 9번 주석에서 확인할 수 있습니다.[9]
간단하게 블록체인의 맥락에서 이해해보자면 PBFT에서는 선정된 단 하나의 노드가 블록을 제안하고, 그 블록에 대하여 다섯 단계를 거쳐 다른 노드들이 합의를 이루어 기존의 체인에 새로운 블록을 더하게 됩니다. 이러한 방식은 ‘누가 가장 빠르게 수학 문제를 해결하느냐’에 따라 블록을 생성하고, 만약 거의 동시에 블록을 생성하면 포크가 발생하는 나카모토 컨센서스와는 확연히 다릅니다. PBFT에서는 만약 모든 단계가 성공적으로 마쳐진다면 모든 정상적인 노드들은 단 하나의 블록에 합의한 이후, 다시 다음 블록을 합의하게 됩니다. 즉, Safety가 완전히 보장됩니다.
PBFT에서는 각 단계마다 어떤 정보를 담은 메시지를 누구에게, 어떠한 방식으로 전송하고 수신할지가 정해져 있습니다. 그러나 각 단계별로 제한 시간이 정해져 있지 않기 때문에 비동기 네트워크 환경이라고 할 수 있습니다. 그렇기에 중간에 메시지가 무한히 지연되면서 특정 단계에서 합의가 멈추는 경우가 있는데 이러한 경우 Liveness를 보장하지 못하게 됩니다. 예를 들어, 블록을 제안하는 단 하나의 노드가 멈추게 된다면 다음 단계로 나아가지 못하는 경우가 발생합니다. 즉, PBFT에서는 합의가 이루어진다면 모든 정상적인 노드가 단 하나의 블록에 합의할 수 있기 때문에 Safety는 보장되지만, 합의가 기약 없이 지연될 수도 있기 때문에 Liveness는 보장되지 않을 수 있습니다.
따라서 PBFT는 Liveness를 어느 정도 보장하기 위해서 동기 네트워크를 일부 도입합니다. 즉, 최초에 블록을 제안하는 단 하나의 노드가 멈추어 제한 시간 안에 합의의 과정이 진행되지 못하는 경우, ‘view-change’라는 기능을 통해 다른 블록 제안자를 선정, 네트워크에 참여하는 멤버를 추가 및 탈퇴함으로써 변경하여 강제로 다음 블록 생성 단계로 넘어가게 됩니다. 바로 여기서 ‘제한 시간을 둔다’라는 부분이 동기 네트워크를 도입하는 부분입니다. (제한 시간에 대해서는 아래 DSRV’s TIP에서 보다 자세히 설명합니다.) 여기서 다시 한번 ‘비동기 네트워크 환경에서는 Safety와 Liveness를 동시에 만족하는 합의 알고리즘이 존재할 수 없다’는 사실을 확인할 수 있습니다.
� DSRV’s Tip; 부분 동기 모델(Partial Synchrony Model)[3][10]
PBFT처럼 비동기 네트워크에 동기 네트워크의 속성을 일부분 더한 것을 부분 동기 모델(Partial Synchrony Model)이라고 합니다. 쉽게 말해, 네트워크를 구성하는 노드들이 GST(Global Stabilization Time)라는 이름의 특정 이벤트를 발생시키기 이전에는 비동기 네트워크, 발생시킨 이후에는 동기 네트워크로 작동하는 모델입니다. PBFT의 경우, 각각의 노드들은 '각자의 타이머'가 만료되면 'view-change'라는 메시지를 다른 노드들에게 전달하여 강제로 다음 블록 생성 단계로 넘어갑니다(동기적 속성). 여기서 'view-change' 이벤트가 바로 GST라고 할 수 있습니다. 'view-change' 이전에는 비동기 네트워크였다가 'view-change' 이후로는 동기적인 네트워크로 전환되기 때문입니다.각각의 노드들의 타이머가 만료되면 특정 이벤트가 발생한다는 점에서 view-change 이전에도 동기 네트워크가 아니냐는 의문점이 생길 수 있습니다. 그러나 악의적인 노드는 자신의 타이머를 조작하여 메시지를 무제한적으로 지연시킬 수 있기 때문에 'view-change' 이전의 이러한 환경은 비동기 네트워크 환경입니다.
마무리: 이더리움 캐스퍼
지금까지, 블록체인과 합의 알고리즘을 Safety와 Liveness로 보다 고수준에서 분류하여 해당 특성이 갖는 의미와 그에 따른 각 블록체인의 동작 방식을 이해해보았습니다. 본문을 통해서만 바라보면 Safety와 Liveness는 이것 아니면 저것의 이분법적인 관점으로 보여지기 쉽지만 사실 연속된 스펙트럼으로 존재하기 때문에, Safety와 Liveness의 양극단이 아니라 그 중간 지점을 구현한 블록체인 또한 존재합니다. 바로 우리에게 가장 친숙한 블록체인 중 하나인 이더리움인데요, 이더리움은 나카모토 컨센서스와 유사한 작업증명 합의 알고리즘을 사용하는 동시에 캐스퍼(Casper)라는 PBFT와 유사한 지분 증명 기반 블록 확정 메커니즘을 통하여 32블록마다[11] 어떤 포크를 정본(Canonical Chain)으로 할 것인지 합의하는 구조를 가지고 있습니다. DSRV Research에서는 본문의 배경지식을 바탕으로 앞으로 이더리움과 이더리움 2.0을 이해하기 위한 시리즈를 연재해나갈 예정입니다. 귀중한 시간을 들여 여기까지 읽어주신 독자분들께 감사드리며, DSRV Research는 다음 글로 다시 찾아뵙겠습니다.
Author
Seokjoong Yoon, DSRV Researcher (Twitter @imlearning_eth)
Reviewed by
Owen Hwang, DSRV Research Manager (Twitter @journeywith_eth)
Youngbin Park, DSRV Researcher (Twitter @bin0_0bin)
Illustrations by
Heeyoung Moon, DSRV Brand Designer
✅ Key Takeaways
분산 네트워크에는 작업의 순서 보장 여부에 따라 동기 네트워크 및 비동기 네트워크 두 종류로 분류할 수 있습니다. 동기 네트워크에는 메시지 전송과 수신에 제한 시간이 있지만 비동기 네트워크는 그렇지 않습니다.
비동기적 합의를 이루어야 하는 분산 시스템에서는 Safety와 Liveness 사이의 딜레마가 있습니다. Safety는 모든 정상적인 노드가 하나의 값으로 합의하는 속성을 말하며, Liveness는 모든 정상적인 노드가 종국에는 합의에 도달하게 됨을 말합니다.
나카모토 컨센서스 및 피어코인의 합의 알고리즘은 Safety보다 Liveness를 우선시하는 합의 알고리즘의 구현입니다.
PBFT는 Liveness보다 Safety를 우선시하는 합의 알고리즘의 구현입니다.
References
[1] M. Fisher, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus With One Faulty Process. In Journal of the ACM, 1985.
[2] Y. Xiao, N. Zhang, J. Li, W. Lou, Y. Hou. Distributed Consensus Protocols and Algorithms.
[3] M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, 1999.
[4] imlearning.eth — Understanding “Impossibility of Distributed Consensus with One Faulty Process”.
[5] S. King, S. Nadal. PPCoin: Peer-to-Peer Crypto-Currency with Proof-of-Stake. 2012
[6] imlearning.eth — The Very Beginning of the Proof of Stake.
[8] Bitcoinsv — Orphan Block
[9] imlearning.eth — “Practical Byzantine Fault Tolerance, PBFT” Explained.
[10] Ittai Abraham — Synchrony, Asynchrony and Partial Synchrony
[11] Github — Ethereum Beacon Chain Consensus Specs, SLOTS_PER_EPOCH
