Livenss / Safety

xlwdn·2023년 10월 14일

Liveness / Safety

blockchain 블록의 생성 과정은 safety와 liveness를 동시에 만족시킬 수 없다.

이는 1985년에 발표된 FLP Impossibility를 통해 증명되었다.

FLP Impossibility

위 논문에서는 ‘비동기 네트워크 환경에서는 Safety와 Liveness를 동시에 만족시키는 분산된 합의 알고리즘은 존재할 수 없다.’를 수학적으로 증명하였는데, 이는 곧 분산 시스템 기반의 Blockchain 환경에서 Liveness와 Safety를 모두 만족하며 합의하는 것은 불가능하다는 것을 의미한다.

때문에 블록체인에서는 이를 극복하기 위해 다음 방법들을 사용한다.

합의를 재정의한다.
비동기성을 포기한다.

Liveness over Safety

Liveness를 기본적으로 지키되, Safety를 보장하기 위해 노력하는 방식이라고할 수 있다.

이는 사토시 나카모토가 제안하여 bitcoin에서 사용되는 합의 알고리즘( = 나카모토 합의)에서의 방식이며 FLP 에서는 Liveness를 위해 Safety를 포기했다고 말한다.

나카모토 합의

나카모토 합의는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다.

때문에 이는 현재 존재하는 체인보다 더 긴 체인을 만들 해시 파워가 존재한다면 블록이 대체될 수 있음을 나타내며 이러한 방식을 Finality(완결성)이 보장되지 않는다고 한다.

Liveness를 확보하고 Safety를 포기하되, Safety를 깨기 위한 조건으로 현실적으로 불가능한 수준의 컴퓨팅 파워를 요구함으로써 극복하였다고 볼 수 있다.

Safety over Liveness

전통적으로 분산 시스템에서 연구되던 PBFT(Practical BFT) 기반 BFT 계열 합의 알고리즘들이 속한다.

Untitled

위 내용은 PBFT이며 BFT 계열의 합의에서는 리더 선출과 backup 노드들이 존재하는 구조를 가진다.

Safety over liveness 합의 알고리즘에서는 Liveness over Safety를 채택한 bitcoin 등과 달리 두 가지의 특징을 가진다.

light client
- 기존 blockchain에서는 fork가 발생할 것을 우려하여 blockchain network 참가자들이 모든 데이터를 저장해야했다. 다만 BFT 계열에서는 선 합의, 후 블록 생성을 통해 반드시 합의된 블록만 추가되므로 가장 최근의 블록만 저장하여도 문제가 발생하지 않는다.
선 합의, 후 블록 생성
- 기존 blockchain에서는 99.9%의 안전성이 99.99%가 되는 방식이었지만, bft에서는 100%의 안전성을 가진다고할 수 있다. 때문에 포크가 발생하지 않는다.

BFT 알고리즘에는 Tendermint 등이 있다.

Finalization

finality는 생성된 블록들이 fork되지 않음을 보장하는 것이다. 즉, 거래는 절대 되돌릴 수 없고 수정될 수 없음을 의미한다. 다만 bitcoin 등에서 사용하는 알고리즘에서는 기존에 존재하는 블록들의 연산을 뛰어넘는 컴퓨팅 파워를 가질 경우, 충분히 기록들을 되돌릴 수 있다.

PoS 합의 알고리즘에서는 검증인이라는 개념을 도입해서 특정 시점마다 블록체인을 점검하는데, 2/3 이상이 특정 블록 승인 시 그 블록들은 finalized 되고 조작되지 않음을 인정받게된다.

Bitcoin, Ethereum, Cosmos 비교

liveness / safety
- bitcoin
  - 컴퓨팅 연산을 통해 블록을 생성한다. 때문에 기존에 존재하던 블록을 능가하는 컴퓨팅 파워를 통해 블록이 재정의될 수 있다. liveness를 지키고 safety를 희생했다고 평가한다.
- Ethereum
  - bitcoin과 같이 컴퓨팅 연산을 통해 블록을 생성하되 특정 시점마다 validator가 검증하여 확정시킨다. fork가 발생할 수는 있지만, validator를 통해 finality를 일부 보장하여 safety와 liveness를 둘 다 지키려 한다.
- Cosmos
  - 블록 생성 시에 합의를 완료한 후 블록을 추가하는 방식으로, 포크가 발생하지 않는다. 때문에 safety를 지키고 liveness를 희생했다고 평가한다.
Finalization
- bitcoin
  - 비트코인의 합의 알고리즘 특성상 99.9%가 99.99%로 변하게 되는 방식이므로 finality를 완전히 보장할 수 없다.
- ethereum
  - 비트코인과 유사하지만 특정 시점마다 finality를 보장하므로 어느정도 보장한다.
- Cosmos
  - 합의가 완전히 종료된 이후 블록을 생성하므로 finality를 100% 보장한다.