텐더민트 합의에 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를 보장하기 위해서는 락이 필요한데, 이와 관련된 내용은 “텐더민트 합의에 락이 필요한 이유” 글을 참고하기 바란다.

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

  1. 잘 읽었습니다. 한가지 의문점은 합의 프로세스가 Propose, Prevote, Precommit 3단계로 진행된다 하더라도 기술하신 시나리오대로 진행된다면 Safety가 보장될지 의문입니다. 즉, Phase 5/9에서 N1은 정상적으로 (Precommit R1, B1) 메세지를 braodcast한 다음 (wait for precommits from +2/3) 상태가 될테지만, N2는 비잔틴 노드이므로 (R2, B2)를 propose한다면, 설명하신 시나리오와 유사하게 N2, N3, N4는 majority를 형성하므로 (Prevote R2, B2)를 합의하고 다음 단계로 N2는 (Precommit R2, B2) 메세지를 broadcast하면 결국 N2, N3, N4는 (Precommit R2, B2)를 합의하게 될것입니다. 따라서 N2, N3, N4들은 (R2, B2)를 커밋할테고, N1은 결국 (Precommit R1, B1)에 대한 합의가 되지 않아서 커밋은 실패하고, 따라서 Safety가 보장이 안될거 같으네요. 의견 주시면 감사하겠습니다.

    1. 맞습니다. Propose Prevote, Precommit 3단계로 진행해도 여전히 safety가 깨지는 상황이 있고, 텐더민트는 이 문제를 해결하기 위해 lock을 도입하였습니다. 관련 내용은 다음 글에서 자세히 설명드리겠습니다 🙂

  2. Pingback: 텐더민트 합의에 락이 필요한 이유 | Kwang Yul Seo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s