합의 알고리즘

adc0612·2022년 10월 11일
0

블록체인

목록 보기
9/11

합의 알고리즘 만족 조건

  • Safety
    시스템에 나쁜 일이 발생하지 않는다는 의미이며, 모든 정상적인 참여자는 같은 상태에 동의하여야 하고, 그 상태는 유효해야 한다.
    문제없는 노드는 잘못된 합의를 하지 않는다는 의미다.
  • Liveness
    시스템은 항상 살아 있어야 한다는 의미이며, 결국에는 어떤 상태에 동의하여야 하고, 모든 참여자는 동의한 상태에 도달해야 합니다.
    문제없는 노드는 반드시 합의한다는 의미다.

합의(Consensus)의 Safety

아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다.
다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다.
이러한 특성을 분산 시스템에서 합의의 Safety라고 말한다.

Liveness

합의는 언젠가 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다.
이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다.
모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 Liveness가 보장된다고 말합니다

FLP impossibility

Safety는 문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다는 것이고, Liveness는 문제없는 노드들은 반드시 합의 한다는 것이다.
문제는 Byzantine Failure가 아닌 Fail-Stop Failure가 하나만 있어도 Safety와 Liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다.
이를 FLP Impossibility 혹은 FLP Theorem이라고 한다.

합의 알고리즘을 선택한다는 것은 사실상 Safety와 Liveness 중 무엇을 선택하고 포기할지의 문제다.

Liveness over Safety

Nakamoto Consensus: 비트코인이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 Nakamoto Consensus(나카모토 컨센서스; 나카모토 합의)라고도 한다.

Nakamoto Consensus는 언제나 더 어려운 문제를 푼 체인이 있으면, 그 체인을 유효한 체인으로 판단한다.
즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면, 언제든지 현재 합의된 블록을 다른 블록으로 대체할 수 있다.
이런 방식을 블록체인에서는 Finality(완결성)가 보장되지 않는다고 말하고, FLP Impossibility에서는 Liveness를 위해서 Safety를 포기했다고 말한다.

Liveness를 중시하는 Nakamoto Consensus에서 출발한 합의 알고리즘들은 한정적인 상황에서 Safety를 보장할 방법을 추가하는 방식으로 발전했다.
이더리움에서 구현되고 있는 Casper, the Friendly Finality Gadget이 대표적이다.
Casper는 기존의 PoW로 Liveness를 보장하며 블록을 생성하지만, 50블록마다 투표하여 Safety가 보장되는 지점을 만든다.

Safety over Liveness

BFT: BFT(Byzantine Fault Tolerance; 비잔틴 결함) 알고리즘은 컴퓨터 시스템의 상태이며, 특히 분산 컴퓨팅 구성 요소가 실패할 수 시스템, 불완전한 거기 구성 요소가 실패했는지 여부에 대한 정보다.

Liveness보다 Safety를 중시하는 합의 알고리즘도 있다. 전
통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다.
Cosmos에서 사용하는 Tendermint가 대표적인 Safety를 보장하는 BFT 알고리즘입니다.

FLP Impossibility가 증명했듯이 Safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 Liveness를 보장할 수 없습니다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 Liveness가 보장됨을 증명한다.

Tendermint

Tendermint는 하나의 라운드가 Propose, Prevote, Precommit 3개의 단계로 나누어진다.
이 중 Prevote와 Precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어집니다. 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다.
하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있다.
따라서 Liveness는 보장되지 않는다.

0개의 댓글