First-class 자산

이더리움 블록체인 상에서 수많은 자산들이 발행되고 거래된다. 이더리움의 네이티브 토큰인 ETH, ICO를 통해 발행된 ERC-20 토큰들, 크림토키티로 대표되는 ERC-721 NFT 토큰들이 대표적이다.

그런데 이러한 자산들은 실제로 어디에 저장될까?

이더리움은 계정 모델(account model)을 채택하였기 때문에 모든 상태(state)는 계정에 저장된다. 이더리움 계정은 크게 EOA(Externally Owned Account)와 Contract Account로 나뉘는데, 각 계정은 nonce, balance, storageRoot, codeHash 네 개의 필드를 가진다. 이 중 balance 필드에 해당 계정의 ETH가 저장되어 있다. 즉, 계정 주소만 알면 이더리움의 상태 값을 읽어 ETH 잔고를 확인할 수 있다는 뜻이다.

그런데 왜 ETH만 확인 가능할까? 내 이더리움 지갑에는 OMG나 REP 같은 ERC-20 토큰들도 보이고, 내가 키우고 있는 크립토키티 고양이도 보이는데 말이다. 크립토키티 소스 코드인 KittyCore를 보면 보면 내 고양이가 어디에 있는지 확인할 수 있다.

/// @dev A mapping from cat IDs to the address that owns them. All cats have
/// some valid owner address, even gen0 cats are created with a non-zero owner.
mapping (uint256 => address) public kittyIndexToOwner;

kittyIndexToOwner은 고양이 ID를 키로 고양이 주인을 돌려주는 매핑이다. 지갑에서 보이는 것처럼 내 고양이가 내 계정에 있는 것이 아니라 크립트키티 스마트 컨트랙의 kittyIndexToOwner 매핑에만 존재함을 알 수 있다.

ETH와 다른 자산들 사이의 차이점은 이더리움 트랜잭션을 통해서도 확인할 수 있다. ETH를 보내거나 스마트 컨트랙을 호출하는 이더리움 트랜잭션에는 value 필드가 있다. value는 트랜잭션을 호출할 때 얼마 만큼의 ETH를 보낼 것인지를 결정한다. 스마트 컨트랙 내에서는 msg.value 값을 이용하여 트랜잭션을 통해 보내는 ETH 양을 확인할 수 있다.

내 고양이를 누군가한테 선물할 때는 어떨까? 아무리 찾아봐도 이더리움 트랜잭션에 고양이를 지정할 수 있는 필드는 없다. 고양이를 양도하기 위해서는 크립토키티의 transfer 함수를 호출해야 하는데, 크립토키티 소스 코드를 보면 고양이를 실제로 주고 받는 게 아니라 그저 kittyIndexToOwner 값을 바꿀 뿐이다.

/// @dev Assigns ownership of a specific Kitty to an address.
function _transfer(address _from, address _to, uint256 _tokenId) internal {
… // stuff
// transfer ownership
kittyIndexToOwner[_tokenId] = _to;
… // more stuff
}

이더리움은 오직 ETH만 자산으로 취급하고, 이더리움 위에서 발행된 다른 자산들은 단순히 스마트 컨트랙 스토리지에 저장된 값으로 취급한다. 이더리움 사용자들이 ERC-20이나 ERC-721 등의 인터페이스를 정의하고 이러한 값들을 자산으로 인정하고 있지만 스마트 컨트랙 개발자 입장에서 ERC-20 토큰이나 크립토키티 고양이는 그저 스마트 컨트랙 스토리지에 저장된 하나의 값일 뿐이다.

ETH와 같은 자산을 First-class 자산이라 부르는데, First-class 자산은 임의로 찍어내거나 삭제할 수 없는 등 여러 면에서 보호 장치를 제공받는다. 스마트 컨트랙을 잘못 짜더라도 ETH가 늘어나거나 줄어들게 만들 수 없는 이유도 여기에 있다. 이더리움은 ETH외에는 커스텀한 First-class 자산을 만들 수 없는 체인이라고 볼 수 있고, 이더리움의 스마트 컨트랙에서 발견되는 수많은 치명적인 버그들이 이더리움의 이러한 특성과 무관하지 않다.

이더리움 이후에 나온 대부분의 계정 모델 기반의 체인들이 이더리움과 비슷한 실수를 반복하고 있다. 물론 자산 발행과 거래가 주된 목적이 아닌 체인의 경우 First-class 자산을 지원하지 않는 것이 큰 결점이 아닐 수도 있지만, 블록체인의 가장 큰 어플리케이션 중 하나가 자산 발행이라는 점을 생각하면 이러한 실수가 반복되는 것은 안타깝다. 다행히 페이스북의 Libra 프로젝트는 이더리움의 이러한 문제를 인지하고 First-class 자산을 Libra 및  Move 언어의 장점으로 내세웠다.

참고로 코드체인은 UTXO 기반이라 코드체인 상에서 발행되는 모든 자산들이 First-class이다.

텐더민트 합의에 락이 필요한 이유

지난 글 “텐더민트 합의에 3단계가 필요한 이유”에서 텐더민트 합의 과정을 Propose-Vote 2단계로 줄일 경우 safety에 문제가 발생함을 확인하였다. 그렇다면 Propose-Prevote-Precommit 3단계로 진행하면 safety 문제가 해결될까? 이번에도 예시를 통해 살펴보자.

이번에도 다음과 같이 N1, N2, N3, N4 4개의 노드가 합의를 하는 상황을 가정해보자. 노드 N1이 라운드 R1에서 블록 B1을 제안하였다.

tendermint_without_lock_1

 

B1 블록이 네트워크에 전파되어 N3, N3, N4 노드도 B1 블록을 알게 되었다.

tendermint_without_lock_2

 

B1 블록은 정상적인 블록이므로 노드 모든 노드가 B1 블록에 대한 Prevote 메시지지를 만들어 보낸다.

tendermint_without_lock_3

 

N2 노드는 네트워크 오류로 다른 노드의 Prevote 메시지를 받지 못하였고, N1, N3, N4는 모든 노드로부터 Prevote 메시지를 받았다.

tendermint_without_lock_4

 

N1, N3, N4 노드는 ⅔ 이상의 Prevote를 모았기 때문에 Precommit 메시지를 만들어 보낸다.

tendermint_without_lock_5

 

N3, N4 노드는 네트워크 오류로 Precommit 메시지를 받지 못하였고, N1 노드만 N1, N3, N4 노드의 Precommit 메시지를 받았다.

tendermint_without_lock_6

 

N1 노드는 ⅔ 이상의 Precommit을 모았기 때문에 B1 블록을 커밋하였다.

tendermint_without_lock_7

 

타임아웃이 발생하여 라운드 R2가 시작되고 N2 노드가 블록 B2를 제안하였다.

tendermint_without_lock_8

 

블록 B2가 네트워크에 전파되어 모든 노드가 B2 블록을 받았다.

tendermint_without_lock_9

 

N3, N3, N4 노드는 N1에 B1 블록에 커밋했다는 사실을 모르므로 B2 노드에 대해 정상적으로 Prevote 메시지를 만들어서 보낸다.

tendermint_without_lock_10

 

N2, N3, N4 노드가 서로 Prevote 메시지를 교환하여 B2 블록에 대해 ⅔ 이상의 Prevote 메시지를 모았다.

tendermint_without_lock_11

 

N2, N3, N4 노드는 ⅔ 이상의 Prevote 메시지를 모았기 때문에 B2 블록에 대한 Precommit 메시지를 보낸다.

tendermint_without_lock_12

 

N2, N3, N4 노드가 서류 Precommit 메시지를 교환하여 B2 블록에 대해 ⅔ 이상의 Precommit 메시지를 모았다.

tendermint_without_lock_13

 

N2, N3, N4 노드는 ⅔ 이상의 Precommit 메시지를 모았기 때문에 B2 블록을 커밋한다.

tendermint_without_lock_14

 

N1 노드는 B1 블록을 커밋하고 N2, N3, N4 노드는 B2 블록을 하였기 때문에 safety가 깨졌다.

tendermint_without_lock_15
위에 예에서 볼 수 있듯이 Propose-Prevote-Precommit 3단계로 합의를 진행해도 여전히 safety가 깨지는 상황이 존재함을 알 수 있다. 이러한 상황이 발생하는 이유는 N3, N4가 이미 라운드 R1에서 B1 블록에 대해 ⅔ 이상의 Prevote를 보고 Precommit을 했음에도 불구하고 R2 라운드에서 마음을 바꿔 B1이 아닌 B2 블록에 대해 Prevote를 했기 때문이다.

노드가 Precommit을 하면 이 Precommit 메시지 때문에 다른 노드가 커밋을 했을 가능성을 생각해야 한다. safety를 보장하려면 노드가 한 번 Precommit을 하고 나면 이후 Precommit한 블록과 같은 블록에 대해서만 Prevote를 해야 하고, 리더가 되었을 때도 Precommit한 블록과 같은 블록을 제안해야 한다. 이러한 규칙을 텐더민트 락(lock)이라고 한다.

텐더민트 락을 적용해서 다시 한 번 합의를 진행해보자.

이전 시나리오와 마찬가지로 N1 노드가 B1에 커밋한 상황에서 N2가 블록 B2를 제안하였다. N2는 B1 블록에 대해 ⅔ 이상의 Prevote를 본 적이 없기 때문에 락을 잡지 않았다.

tendermint_with_lock_1

 

N2, N3, N4 노드에 B2 블록이 전파되었고, 각 노드는 B2 블록에 대한 Prevote 메시지를 만들려고 한다.

tendermint_with_lock_2

 

하지만 N3, N4 노드는 라운드 R1에 이미 B1 블록에 대해 ⅔ 이상의 Prevote를 보고 락을 잡은 상태이기 때문에 B2 블록에 대해서 Prevote 메세지를 보내지 않는다.

tendermint_with_lock_3

 

N2, N3, N4 노드가 B2 블록에 합의하지 못했기 때문에 다시 타임아웃이 발생하고 이번에는 N3 노드가 블록을 제안한다. N3는 R1 라운드에 B1 블록에 락을 잡았기 때문에 리더가 되었을 때도 B1 블록을 제안한다. 이후 N2, N4 노드가 B1 블록에 Prevote 및 Precommit을 하고 B1 블록으로 합의하게 된다. N1, N2, N3, N4가 모두 B1 블록에 커밋하였으므로 safety가 깨지지 않았다.

tendermint_with_lock_4

추가로 ⅔ 이상의 Prevote를 모았을 때 락을 잡기만 하고 풀지 않으면 더 이상 합의가 진행되지 않는 liveness 이슈가 생기게 된다. 따라서 라운드 R에서 ⅔ 이상의 Prevote를 보고 락을 잡았더라도 라운드 R’ (R’>R)에서 또 다시 ⅔ 이상의 Prevote를 보았다면 이전 락을 풀고 새로 락을 잡아야 한다. 이러한 특성 때문에 ⅔ 이상의 Prevote를 PoLC (Proof of Lock Change)라고 부른다.

 

TPS 비교 아이고 의미 없다

블록체인의 성능을 비교하기 위한 지표로 TPS(transaction per second)가 가장 많이 쓰인다. 덕분에 여러 블록체인들이 새로운 합의 프로토콜을 내놓으면서 경쟁적으로 높은 TPS를 주장하고 있는 상황이고, 대한민국 정부도 5500억의 국민 세금을 투여해 10 TPS 성능을 가지는 토종 블록체인 기술을 개발하겠다고 한다.

 

jjSR

 

하지만 스스로가 주장하는 TPS는 다음과 같은 이유로 큰 의미가 없다.

  1. TPS를 측정하는 네트워크 환경이 다르다. 1만 대 이상의 노드가 전세계에 흩어져 있는 네트워크 환경과, 1Gbit/s를 자랑하는 네트워크 환경에 20-30대의 노드만 높고 돌린 TPS를 비교하는 것 자체가 어불성설이다.
  2. 트랜잭션의 단위가 다르다. 계좌간 암호화폐를 전송하는 트랜잭션과 복잡한 스마트 컨트랙 로직을 실행하는 트랜잭션은 트랜잭션 하나를 실행하는 시간에 100배 이상의 차이가 날 수도 있다. 어떤 트랜잭션을 실행했는지 모르는 상태에서 단순 TPS 비교는 의미가 없다.
  3. 트랜잭션 확정 시간을 고려하지 않고 있다. 텐더민트나 LibraBFT BFT 계열의 합의 알고리즘은 보통 1000-2000 수준의 TPS가 나오고, 하나의 트랜잭션은 수 초 이내에 컨펌이 된다. 반면 10 TPS 이상을 주장하는 DAG 기반의 합의 방식은 순서를 제대로 보장하지 못할 뿐더러 트랜잭션 확정에 필요한 시간이 훨씬 길다.

모든 엔지니어링이 마찬가지지만 블록체인 네트워크 설계 또한 안정성, 검열 저항성, 성능 등 서로 상충하는 목표들 사이의 적절한 트레이드오프가 핵심이다. 비트코인, 이더리움 등 일부 블록체인 네트워크를 제외하고는 사실상 트랜잭션이 거의 없는 상황에서 높은 TPS만이 유일한 목표가 되어야 하는지는 생각해 볼 일이다.

 

VRF(Verifiable Random Function)와 블록체인

Micali , Rabin, Vadhan 99 논문에서 처음 소개된 VRF(Verifiable Random Function)  입력에 대해 검증 가능한 의사난수(pseudorandom) 값을 출력하는 함수이다.

VRF 특성

VRF Keygen, Evaluate, Verify 3개의 함수로 구성된다.

  • Keygen(r) -> (VK, SK): 생성 함수는 랜덤한 입력 r 대해 검증키 VK 비밀 SK 쌍을 생성한다.
  • Evaluate(SK, X) -> (Y, ): 실행 함수는 비밀키 SK 메시지 X 입력으로 받아 유사 난수 S 증명 ⍴를 리턴한다.
  • Verify(VK, X, Y, ) -> 0/1: 검증 함수는 입력으로 검증키 VK 메시지 X, 출력 Y, 증명 ⍴를 입력으로 받아 Y 실제로 SK X 의해 생성된 출력이 맞으면 1 리턴한다.

정리하면, VRF는 키쌍 VK, SK를 고정했을 때 입력 X에 대해 유일하고 검증 가능한 유사난수 Y를 출력하는 함수이다.

VRF 함수가 유용하려면 다음 조건을 만족시켜야 한다.

  1. 출력 Y는 유일해야 한다. (VK, SK) 키쌍과 입력 X에 대해 또 다른 출력을 찾는 게 불가능해야 한다.
  2. 출력 Y는 유사난수여야 한다.  증명 ⍴가 없는 3 입장에서 Y 예측이 불가능한 랜덤한 값이어야 한다.
  3. 1, 2 속성은 키쌍(SK, VK)가 신뢰할 수 없는 제3자에 의해 생성되었을 경우에 유효해야 한다.

별도의 검증키를 이용해 출력을 검증할 수 있다는 점에서 VRF는 디지털 서명 방식과도 유사하다. 하지만 디지털 서명의 경우 하나의 입력에 대해 여러 개의 유효한 서명이 존재하고, 출력값이 유사난수 조건을 만족시킬 만큼 충분히 랜덤하지 않다는 점에서 VRF 함수와는 차이가 있다.

VRF 함수와 블록체인

텐더민트 합의 알고리즘은 리더를 선출할 때 라운드 로빈(round robin) 방식을 사용한다.  이 방식은 고정된 순서대로 리더가 정해지기 때문에 공격자 입장에서는 쉽게 다음 리더 노드에 대한 DoS (Denial of Service) 공격이 가능하다는 약점이 있다.

VRF를 사용하면 이러한 문제를 완화시킬 수 있다. 일례로, 다음과 같이 현재의 리더가 자신의 비밀키와 이전 블록의 해시(메시지)를 VRF 함수에 입력하여 나온 출력을 다음 리더를 정할 때 사용하는 방식을 생각해보자.

Evaluate(SK_of_current_leader, prev_block_hash) = (Y, ⍴)

next_leader = Y % num_of_validators

여기서 Y는 현재의 리더만 계산할 수 있는 랜덤한 값이라 다른 노드들이 예측할 수 없다. 또한 다른 노드들은 Y 값이 리더가 마음대로 정한 값이 아니라 정해진 규칙에 의해 계산된 값임을 Verify 함수를 이용하여 검증할 수 있다.

하지만 이 방식은 문제를 완벽하게 해결하지 못한다. 모든 노드들이 거의 동시에 다음 리더가 누구인지 알게 되기 때문에 다음 리더가 블록을 제안하기 전에 DoS 공격을 할 수 있는 잠깐의 틈이 생긴다.  DoS 가능성을 완전히 차단하려면 다음 리더만 스스로 다음 리더라는 사실을 알 수 있고 다른 노드들은 다음 리더가 제안한 블록을 보고 나서야 다음 리더가 누구인지 알 수 있는 방식이어야 한다.  이러한 일을 가능케 하는 VRF를 이용한 암호학적 추첨(cryptographic sortition)에 대해서는 다음 글에서 자세히 설명하겠다.

텐더민트 합의에 3단계가 필요한 이유

텐더민트의 합의 프로세스는 Propose, Prevote, Precommit 3단계로 진행된다. 리더가 블록을 Propose하면 검증자(validator)들은 블록을 검증한 후 Prevote 투표를 한다. 전체 검증자의 2/3 이상이 Prevote 투표를 했으면 다음 단계인 Precommit으로 넘어간다. 여기서 다시 한 번 전체 검증자의 2/3 이상이 Precommit을 했으면 해당 블록을 Commit한다.

tendermint.png

텐더민트 합의 방식을 처음 접했을 때 든 의문이 있다. Prevote 투표 단계에서 이미 전체 검증자의 2/3 이상이 동의를 했음에도 불구하고 왜 다시 한 번 Precommit 투표를 진행하는 걸까? Prepose-Prevote-Precommit 3단계를 Propose-Vote 2단계로 줄이는 게 더 효율적이지 않을까?

이 질문에 대한 가장 확실한 답은 Propose-Vote 2단계로 합의를 진행했을 때 문제가 생기는 경우 (반례)를 찾는 것이다.

다음과 같이 N1, N2, N3, N4 4개의 노드가 합의를 하는 상황을 가정해보자. 라운드 R1에서 N1 노드가 B1 블록을 Propose하였다. 여기서 (B1, R1)은 라운드 R1에서 제안된 블록 B1을 의미한다.

t1

 

B1 블록이 네트워크 상에 전파되어 N2, N3, N4 노드도 B1 블록을 알게 되었다.

t2

 

B1 블록은 검증을 통과하여 N1, N2, N3, N4가 각각 B1 블록에 대해 투표를 진행하였다. 여기서 V(N1, B1)은 N1 노드가 B1 블록에 대해 투표를 했다는 뜻이다.

t3

 

각 노드의 투표가 네트워크 상에 전파되어 N1과 N2 노드는 각각 모든 노드의 투표를 전달 받았다. 하지만 N3, N4는 네트워크 상의 문제로 다른 노드의 투표를 전달받지 못했다.

t4

 

N1 노드는 2/3 이상의 투표를 모았기 때문에 R1 라운드에 B1 블록을 커밋한다. 그런데 알고 보니 N2 노드는 비잔틴 노드였다. N2 노드는 프로토콜 대로 B1 블록을 커밋하는 대신 R2 라운드로 넘어가서 새로운 블록 B2를 Propose하였다.

t5

 

N2 노드가 제안한 B2 블록이 N3와 N4 노드에 전파되었다.

t6

 

N2, N3, N4 노드는 N1 노드가 B1에 커밋했다는 사실을 알지 못하므로 B2 블록에 투표한다.

t7

 

N2, N3, N4 노드의 투표가 N2, N3, N4 노드에 모두 전파되었다.

t8

 

N2, N3, N4 노드 모두 B2 블록에 대해 2/3 이상의 투표를 모았기 때문에 B2에 커밋한다.

t9

 

위 시나리오에서 비잔틴 노드는 N2 하나이고, N1, N3, N4는 모두 정상적인 노드이다. 전체 노드의 1/3 이하만 비잔틴이기 때문에 BFT 합의 알고리즘에서는 정상적으로 합의가 진행되어야 한다.

하지만 결과적으로 1대의 비잔틴 노드 때문에 N1 노드는 B1에 커밋을 하고, N2, N3, N4 노드는 B2에 커밋을 하였다. 같은 높이에서 서로 다른 블록에 커밋이 발생했으므로 합의 알고리즘의 가장 중요한 속성 중 하나인 safety가 깨졌다. 이 예시를 통해 Propose-Vote 2단계로 구성된 합의 방식은 safety를 보장하지 못함을 알 수 있다.

텐더민트의 투표 단계를 두 번에서 한 번으로 줄여서 합의 알고리즘의 성능을 개선했다는 주장을 하는 프로젝트가 있는데, safety나 liveness에 대한 증명이 없으면 이 주장을 곧이곧대로 믿기는 어렵다. 위 사례에서 본 것처럼 다른 장치 없이 투표 단계를 1단계로 줄이면 합의 알고리즘의 safety를 보장하지 못하기 때문이다.

추가: Propose-Prevote-Precommit 3단계로 합의를 진행한다고 곧바로 safety가 보장되는 것은 아니다. 텐더민트 합의 알고리즘의 safety를 보장하기 위해서는 락이 필요한데, 이와 관련된 내용은 “텐더민트 합의에 락이 필요한 이유” 글을 참고하기 바란다.

CAP 정리와 블록체인 Finality

블록체인에서 finality의 의미는 블록이 한 번 블록체인에 포함(import)되고 나면 되돌릴 수 없음을 의미한다. finality 보장 방법은 합의 알고리즘 설계에서 가장 중요한 문제 중 하나이다.

finality는 크게 1) 확률적 finality와 2) 절대적 finality 두 종류로 분류한다.

확률적 finality는 블록을 되돌릴 수 없다는 것을 확률적으로만 보장한다. 비트코인 나카모토 합의 알고리즘이 사용하는 방식으로 블록이 추가로 생성될 수록 앞쪽에 있는 블록의 finality가 확률적으로 증가하는 방식이다. 오래된 블록을 되돌리기 위해서는 많은 컴퓨팅 파워가 필요하기 때문에 어느 정도 오래된 블록은 사실상 되돌리는 것이 불가능해진다. 거래소에 비트코인을 입금하면 6개의 블록 컨펌을 기다린 이후 거래가 가능한 이유도 거래소 입장에서 확률적으로 finality를 체크하기 때문이다.

반면, 절대적 finality는 한 번 블록이 블록체인에 포함되면 어떤 경우에도 해당 블록을 되돌릴 수 없음을 보장하는 방식이다. 주로 텐더민트와 같은 BFT 계열의 합의 알고리즘이 절대적 finality를 보장하는데, 텐더민트의 경우 블록이 전체 노드 voting power의 2/3 prevote와 2/3의 precommit을 받으면 해당 블록은 즉시 finalize가 된다.

확률적 finality와 절대적 finality의 속성을 비교하면 당연히 절대적 finality가 좋다. finality만 봤을 때는 모든 체인이 BFT 계열의 합의 알고리즘을 사용해야 한다고 생각할 수 있다. 하지만 모든 엔지니어링은 트레이드오프가 있고, 절대적 finality 역시 공짜로 얻어지는 것은 아니다.

이 문제를 이해하기 위해서는 Eric Brewer’s CAP 정리를 살펴볼 필요가 있다. CAP 정리에 따르면 모든 분산 컴퓨팅 시스템은 Consistency, Availability, Partition Tolerance 중 2가지만 달성 가능하다. 참여 노드가 전세계에 분산된 블록체인의 경우 네트워크 파티션을 피할 수 없으므로, 모든 체인은 Consistency와 Availability 둘 중 하나를 선택해야 한다는 뜻이기도 하다.

확률적 finality를 선택한 체인은 네트워크 파티션 상황에서 Availability를 보장한다. 비트코인의 경우 네트워크 파티션이 발생하면 각 파티션에 포크가 생기게 되고, 네트워크 파티션이 사라지면 longest-chain 규칙에 따라 다시 하나의 체인으로 합쳐지게 된다. 포크가 난 상황에서도 계속 합의를 진행할 수 있지만, finality는 보장하지 못한다.

반대로 절대적 finality를 선택한 체인은 네트워크 파티션 상황에서도 Consistency를 보장한다. 텐더민트의 경우 네트워크가 반으로 파티션되면 어느 한 쪽도 2/3의 투표를 받지 못하기 때문에 블록에 대한 합의를 진행하지 못한다. 이후 네트워크 파티션이 사라지면 다시 합의를 진행하게 된다. 파티션 상황에서 Availability를 보장하지 못하는 대신 절대적 finality를 보장할 수 있다.

하나의 체인이 모든 종류의 Dapp을 지원하기 어려운 이유도 여기에 있다. 어떤 Dapp은 Consistency가 중요하고 어떤 Dapp은 Availability가 중요할 수 있다. Dapp 개발자는 Finality 보장에 숨어 있는 트레이드오프를 이해하고 Dapp의 성격에 맞는 적절한 체인을 선택하는 것이 좋다.

부분 동기 모델 (Partial synchrony model)

합의 알고리즘을 설계할 때는 해당 합의 알고리즘이 어떠한 환경에서 합의를 이룰 수 있는지 엄밀한 정의가 선행되어야 한다. 특히, 블록체인 네트워크는 여러 대의 노드로 구성되기 때문에 각 노드가 주고 받는 메시지의 지연 시간(delay) 대한 고려가 필요하다.

분산 컴퓨팅에서는 전통적으로 크게 2가지 커뮤니케이션 모델을 이야기한다.

먼저, 동기 모델(synchronous model)에서는 time bound Δ가 있어서 모든 메시지가 Δ 안에 도착하는 것이 보장된다.

반대로 비동기 모델(asynchronous model)에서는 메시지가 정해진 시간 내에 도착한다는 보장이 없다. 하지만 메시지가 언젠가는 도착한다는 보장은 있다.

우리가 알고 있는 각각의 합의 알고리즘은 동기 혹은 비동기 모델을 가정하고 해당 합의 알고리즘이 safety와 liveness를 보장한다는 사실을 증명한다. 따라서 동기 모델을 가정하고 safety와 liveness를 증명한 합의 알고리즘의 경우 비동기 모델을 상정했을 때 이러한 속성이 유효하다는 보장이 없다.

동기 모델을 가정한 합의 알고리즘의 예로 비트코인의 작업증명(PoW) 합의 알고리즘이 있다. 비트코인은 10분 안에 비트코인 네트워크에 연결된 모든 노드에 메시지(블록/트랜잭션)이 도착한다는 전제 하에 합의 알고리즘을 설계하였다.

동기 모델을 가정한 합의 알고리즘은 메시지가 도착하는데 소요되는 시간 Δ만큼 타임아웃을 두어야 하므로 효율성이 떨어진다. Δ 값을 줄이면 효율성을 높일 수 있지만, 메시지가 Δ+ϵ 이후에 도착하기 시작하면 합의 알고리즘의 가장 중요한 속성인 safety와 liveness가 깨진다. 비트코인의 블록 생성 시간인 10분이 길다고 이 시간을 마냥 줄일 수는 없는 이유가 여기에 있다.

비동기 모델은 네트워크 지연에 대해 아무런 전제도 하지 않기 때문에 훨씬 더 견고한 합의 알고리즘을 설계할 수 있다. 고정된 타임아웃 값이 아닌 실제 네트워크의 속도에 비례해 합의를 진행할 수 있다는 점도 장점이다. 하지만 비동기 모델을 가정한 합의 알고리즘은 알고리즘이 복잡하고 속성을 증명하기도 어렵다는 단점이 있다.

또한, 비동기 모델을 가정하면 아예 합의 자체가 불가능한 경우도 생긴다. 대표적으로 Fischer, Lynch, Paterson이 1985년 발표한 논문은 비동기 모델에서는 단 하나의 노드라도 fail-stop (비잔틴 노드가 아닌 단순 크래시)하면 합의가 불가능하다는 사실을 증명하였다.

동기 모델과 비동기 모델 모두 합의 알고리즘을 설계하는데 있어 아쉬운 점이 있는데, 이러한 문제를 해결하고자 Dwork, Lynch, Stockmeyer가 1988년 논문에서 부분 동기 모델(partial synchrony model)을 제안하였다. 부분 동기 모델은 네트워크가 동기 상태와 비동기 상태를 번갈아 오간다고 가정한다.

부분 동기 모델은 조금 더 엄밀하게 정의하면 다음과 같다. 네트워크에 GST(Global Stabilization Time)라는 이벤트가 있는데, GST가 언제 일어날지는 알 수 없지만 일단 일어나고 나면 정해진 시간 Δ 내에 모든 메시지가 도착한다. 네트워크가 GST 이전에는 비동기 모드로 있다가 GST 이후에 동기 모드가 된다고 생각할 수 있다. 노드 입장에서 언제 GST가 일어났는지 알 수 있는 방법은 없다.

부분 동기 모델을 가정한 합의 알고리즘은 네트워크가 비동기인 상태에서도 항상 safety를 보장하고, GST가 발생하여 네트워크가 동기 모드가 되면 liveness를 보장하는 방식을 취한다. BFT 계열의 합의 알고리즘은 대부분 부분 동기 모델을 가정하고 있는데, 코드체인에서 사용하고 있는 텐더민트와 리브라 프로젝트에서 차용한 LibraBFT(HotStuff 기반)도 모두 부분 동기 모델을 가정하고 합의 알고리즘을 설계하였다.