[이더리움2.0 깊이보기 시리즈]CBC Casper Explained (1/2)[4편]

Published in

Tokamak Network

28 min readDec 16, 2019

Carl Park (4000D)

이더리움2.0 깊이보기 시리즈는 개발이 진행되고 있는 이더리움2.0에 관한 스펙과 작동원리에 대해서 이해의 저변을 넓히고자 하는 목적으로 온더에서 기획되었습니다. 연재는 다음 순서로 이어집니다.

[1편] — ETH 2.0 Explained: Phase 0
[2편] — Cross Shard Communication -1- 비동기 커뮤니케이션
[3편] — Cross Shard Communication -2- 동기 커뮤니케이션
[4편] — CBC casper explained (1/2)
[5편] — CBC casper explained (2/2)
[6편] — ETH 2.0 Explained: Phase 1
[7편] — 스태이트리스 클라이언트(Stateless Client)
[8편] — ETH 2.0 Explained: Phase 2
[9편] — Execution Environment

LaTex를 미디엄이 올바르게 지원하지 않기 때문에 이 문서에서 동일한 내용을 더욱 편하게 보실 수 있습니다.

CBC(correct-by-construction) Capser는 consensus safety를 달성할 수 있는 프로토콜의 추상적인 구조입니다. 본 포스트에서는 AbstractCBC, CasperTFG 두 페이퍼의 내용을 다룰 것입니다.

AbstractCBC는 “프로토콜 상태”와 “프로토콜 상태 전이”(protocol execution, morphism), “estimator”를 정의한 이후 estimate safety와 conosensus safety를 만족할 수 있는 프로토콜을 수학적으로 증명합니다. 추상적인 Casper CBC 구조를 상속하여 합의가 필요한 대상에 적용하기 때문에 CBC Casper family of protocol이라고 부릅니다.

CasperTFG(Casper the Friendly Ghost)는 binary consensus와 blockchain consensus(fork choice)를 consensus safe하도록 스펙을 정의하고 estimate safety를 만족할 수 있음을 보입니다. 또한 estimate safety를 올바르게 판별할 수 있는 clique oracle을 간략하게 소개합니다.

Symbols & Terminology

“consensus (value), 𝐶”:
- binary consensus: {0, 1}
- blockchain consensus: fork choice
“estimate (or proposition), 𝑝”: “guesses” about the value of the consensus
“logic of consensus with proposition, 𝐿𝐶LC”:
“set of propositions, 𝑃𝑟𝑜𝑝𝑠(𝐿𝐶)Props(LC)”: map all possible consensus values to “True” or “False”
- 𝑝∈𝑃𝑟𝑜𝑝𝑠(𝐿𝐶),𝑝:𝐶→{𝑇𝑟𝑢𝑒,𝐹𝑎𝑙𝑠𝑒}p∈Props(LC),p:C→{True,False}
“protocol state, 𝜎”
- 𝜎∈Σ
“protocol execution (or morphism), 𝑚𝑜(Σ)”: transition from 𝜎1σ1 to 𝜎2σ2
- 𝜏∈𝑚𝑜(Σ),𝜏:Σ→Σ
- ∃𝜏∈𝑚𝑜(Σ),𝜎→𝜏𝜎′⇔𝜎→𝜎′
- closed under composition:
𝜏1,𝜏2∈𝑚𝑜(Σ)⟹𝜏1∘𝜏2∈𝑚𝑜(Σ)
“estimator, E”: maps protocol states to propositions
- E:Σ→𝑃𝑟𝑜𝑝𝑠(𝐿_𝐶)
- consistency: ∀𝑝∈𝑃𝑟𝑜𝑝𝑠(𝐿_𝐶),∀𝜎∈Σ, if E(𝜎)⇒𝑝, then ¬(E(𝜎)⇒¬𝑝)
“estimate safety, 𝑆(𝑝,𝜎)”
- 𝑆(𝑝,𝜎)⇔∀𝜎′:𝜎→𝜎1, E(𝜎′)⇒𝑝
“common future state, 𝜎1∼𝜎2”
-∃𝜎3: 𝜎1→𝜎3∧𝜎2→𝜎3
“consensus safety, 𝜎1∼𝜎2⟹¬(𝑆(𝑝,𝜎1)∧𝑆(¬𝑝,𝜎2))”
“non-triviality”: the protocol is able to choose between mutually exclusive values.
- ∃𝑝∈𝑃𝑟𝑜𝑝𝑠(𝐿_𝐶),∃𝜎0,𝜎1,𝜎2∈Σ:(𝜎0→𝜎1∧𝜎0→𝜎2)∧(𝑆(𝑝,𝜎1)∧𝑆(¬𝑝,𝜎2))
“validator, 𝑣”
- 𝑣∈𝑉
“protocol message, 𝑀”
- 𝑀=𝑃𝑟𝑜𝑝𝑠(𝐿_𝐶)×𝑉×P(Σ)
“justification of a message, 𝐽(𝑚)”: 메시지의 유효성을 확인하기 위한 프로토콜 상태
“dependency of two messages, 𝑚1≺𝑚2”:
- 동치: 𝑚2가 𝑚1이후에 생성되었다.
“latest message from a validator: 𝐿(𝑣,𝑀)”: 검증자가 가장 마지막에 보낸 메시지
“weight”: 검증자가 예치한 토큰의 수량
“score”: 블록의 점수
“equivocation”: 의존성을 가지지 않는 두 메시지 쌍의 관계. 정직한 노드는 equivocation하지 않는다.
“weight of byzantine faults, faulty weight”: byzantine 노드의 weight의 합

1. Estimate Safety Consensus Protocols

Estimate Safety Consensus Protocols는 (𝐶,𝐿_𝐶,Σ,E) 로 이루어져있습니다.

Binary consensus는 {0, 1}에 대한 합의를, blockchain consensus는 올바른 블록체인에 대한 합의를 결정합니다. 합의의 대상이 되는 것들을 consensus value(𝐶)라고 표현합니다.

estimate(혹은 proposition, 𝑝)은 consensus value가 올바른지 아닌지에 대한 명제입니다. 따라서 estimate는 C 에서 {True, False}로 가는 map이라고 표현할 수 있습니다.

합의에 사용된 logic(𝐿_𝐶)은 다르게 표현하자면 estimate의 집합(𝑝𝑟𝑜𝑝𝑠(𝐿_𝐶))입니다. 어느 estimates를 이용하여 합의를 이루어 냈는가를 의미합니다.

프로토콜 상태(protocol states, Σ)는 합의를 이루는 노드들의 상태입니다. 노드가 합의를 결정하는 기준은 검증자들이 보낸 프로토콜 메시지에 따라 결정됩니다. 따라서 프로토콜 상태(𝜎,𝜎∈Σ)은 프로토콜 메시지의 집합과 동일합니다.

마지막으로 estimator(E)는 프로토콜 상태들에서 estimate로 가는 map입니다. 즉, 𝜎1에 있는 노드가 estimator를 이용하여 자신의 True인 proposition를 식별할 수 있으며 또한 𝜎2에 있는 다른 노드의 estimate를 식별할 수 있습니다. 이러한 정보를 바탕으로 각 노드는 개별적으로 consensus safe가 보장되는 estimates를 추측할 수 있습니다.

estimator는 어느 𝜎에서 𝑝가 True라면 ¬𝑝에 대해서는 False라는 점에서 일관성을 가집니다. (if E(𝜎)⇒𝑝 then ¬(E(𝜎)⇒¬𝑝))

consensus value 𝐶는 특징되지 않았으며, estimator 또한 단순한 a map from state to proposition 이기 때문에 추상적으로 정의됩니다. 해당 페이퍼 제목에 abstract가 들어가는 이유 또한 그 때문입니다. binary consensus, blockchain consensus는 그에 맞는 estimator를 정의하고 있습니다.

반면 프로토콜 상태는 검증자들의 프로토콜 메시지의 집합으로 정의됩니다. 프로토콜 메시지는 consensus values, 검증자, 그리고 프로토콜 상태들의 tuple입니다. (𝑀:=𝐶×𝑉×Σ) 이에 대한 자세한 설명은 2. Casper the Friendly Binary Consensus에서 다루겠습니다.

1.1 Estimate Safety (𝑆(𝑝,𝜎)S(p,σ))

Estimate safety는 proposition 𝑝가 프로토콜 상태 𝜎에서 safe하다는 의미이며, 𝑆(𝑝,𝜎)로 나타냅니다. 𝜎의 모든 future state 𝜎′에 대해 estimator는 동일한 𝑝를 반환해야 합니다.

노드들은 오직 proposition p가 estimate safety할 경우에만 의사결정을 합니다.

1.2 Consensus Safety (𝜎1∼𝜎2⟹¬(𝑆(𝑝,𝜎1)∧𝑆(¬𝑝,𝜎2)))

Consensus safety는 각 노드들이 estimate safety를 가지는 common future 프로토콜 상태를 개별적으로 판단할 수 있음을 의미합니다. 즉, 두 노드가 각각 𝜎1,𝜎2에 있을 때 각 노드가 내린 결정들은 서로 일관성이 존재하기 때문에 safety가 보장됩니다.

common future protocol state는 다음과 같이 정의됩니다.

Consensus safety를 증명하기 위한 3개의 보조정리를 먼저 살펴봅시다.

Lemma 1: Forwards Safety

이 보조정리는 estimate safety가 모든 future state를 포함한다는 사실로부터 증명할 수 있습니다. “𝜎의 모든 future state 𝜎′”에 대해 E(𝜎′)=𝑝이기 때문에, 𝜎′의 future state(𝜎″) 또한 E(𝜎″)=𝑝라는 사실이 “estimate safety at 𝜎”에 내포되어 있습니다.

Lemma 2: Current Consistency

이 보조정리는 상반되는 두 propositions (𝑝,¬𝑝)가 동시에 safe할 수 없다는 의미를 가집니다. estimator의 일관성 (if E(𝜎)⇒𝑝 then ¬(E(𝜎)⇒¬𝑝))을 이용하여 증명할 수 있습니다.

Lemma 3: Backwards Consistency

이 보조정리는 프로토콜 상태 𝜎′에서 safe한 estimate 𝑝의 반대(¬𝑝)가 previous state 𝜎에서 safe하지 않음을 의미합니다.

Theoreom 1: Consensus Safety

Consensus safety 정리는 common future state를 가지는 두 프로토콜 상태들(𝜎1,𝜎2)는 1) ¬𝑆(𝑝,𝜎1) 혹은 2) ¬𝑆(¬𝑝,𝜎2) 임을 보장합니다.

1번 경우에는 estimate safety가 없기 때문에 𝑝에 대해 의사결정을 하지 않을 것입니다.
2번 경우에는 Lemma 2에 의해 ¬𝑆(¬𝑝,𝜎2)⇔𝑆(𝑝,𝜎2)와 동일한 의미를 가집니다.

위 증명의 (4)번 주장이 지금까지 논의한 “합의의 일관성”을 가장 명확히 보여줍니다. 이는 별도의 Lemma 4로 따로 정의합니다.

Lemma 4: Distributed Consistency

이 보조정리는 Lemma 1, Lemma 3로 부터 유도되었으며, “노드가 safe estimate를 기반으로 내린 개별적인 결정(decision)는 다른 노드가 내린 결정와 일관성을 가지는 것”을 의미합니다. 즉, 다른 프로토콜 상태에 있는 노드와 common future state 𝜎3를 가지기만 하면, 다른 노드 또한 𝜎3에 대해 estimate safety를 가질 것이고, 이는 해당 노드가 consensys safety가 보장된 의사결정을 할 수 있음을 보장합니다.

지금까지는 common future state를 기반으로 내린 결정의 safety를 논의했습니다. 하지만 실제 상황에선 common future state가 존재하지 않는 경우가 더 많을 것입니다. 가령 blockchain fork가 발생하거나 byzantin 노드가 내린 결정에 따르지 않는 상황들일 것입니다. 이런 특성을 non-triviality라 부르며, 상호 배재하는 두 프로토콜 상태들에 대해서도 safety를 보장할 수 있어야 합니다.

non-triviality는 다음과 같이 정의됩니다.

Lemma 5: Maintaining a shared future is non-trivial

이 보조정리는 non-triviality 때문에 common future state가 항상 존재하는것은 아님(∃𝜎1,𝜎2∈Σ:𝜎1≁𝜎2)을 의미합니다.

위 증명의 3번이 consensus safety theorem의 대우입니다. 이는 consensus failure를 의미하며, non-triviality가 발생할 수 있는 조건을 보여줍니다.

Lemma 6: Consensus Failure

아래 그림은 non-triviality로 인해 common futre state를 가지지 않는 상황을 보여줍니다. 두 개의 분기가 존재하며, 각 분기별로 두 개의 future states로 나눠지는 모습입니다.

지금까지 Estimate safe consensus protocol을 살펴보았습니다. 위 내용을 다시한번 정리하면,

𝜎1에 있는 노드 A는 𝑝에 대해 𝑆(𝑝,𝜎1)인지 알 수 있습니다. 또한 𝜎2에 있는 다른 노드 B와 common future state(𝜎3)를 가진다는 것을 확인한다면, A는 내부적으로 𝜎3에 대해 합의를 결정할 수 있습니다. 이는 B또한 마찬가지로 𝑆(𝑝,𝜎1)을 확인한다면 내부적으로 𝜎3에 대해 합의를 결정할 수 있습니다. A와 B이 내린 의사결정은 (byzantine fault하지 않다는 가정하에) consensus safety theorem에 의해 일관성이 보장됩니다.
또한 common future state가 존재하지 않는 non-trivial한 상황도 발생할 수 있으며 (Lemma 6), 이 경우 합의는 진행될 수 없을 것입니다.

프로토콜이 어떻게 byzantine fault tolerant할 수 있는지는 binary consensus와 blockchain consensus 예시들을 살펴보며 논하겠습니다.

2. Casper the Friendly Binary Consensus

이제 consensus safety proof를 위한 프로토콜 상태, estimator 및 기타 개념들을 Binary Consensus를 예제로 순차적으로 살펴봅시다.

프로토콜 상태는 t이하의 byzantine fault를 보이는 프로토콜 메시지들의 집합입니다. – as sets of messages that exhibit up to t Byzantine faults –
프로토콜 메시지들(protocol messages, M)는 (estimate, sender, justification)으로 이루어집니다. estimate(𝑝)는 {0,1} 중 하나이고, sender는 validator(𝑣∈𝑉) 입니다. 그리고 justification(J(M))은 프로토콜 상태(프로토콜 메시지들)입니다. 프로토콜 메시지의 ‘estimator를 justification에 적용한 결과가 estimate와 동일’ 할 때 유효합니다. 즉 메시지 m∈M:𝑚=(𝑝,𝑣,𝑗)은 E(𝑗)=𝑝 일 때 유효합니다.
프로토콜 메시지의 justification은 특정 검증자의 프로토콜 상태를 확인하는 용도로 사용됩니다. 따라서 프로토콜 메시지를 받은 노드는 해당 검증자의 프로토콜 상태를 justification으로 파악한 이후 common future state를 찾을 수 있습니다. 이는 곧 consensus safety 정리를 적용할 수 있는지 각 노드가 개별적으로 파악 가능하다는 의미이기도 합니다.
프로토콜 메시지의 정확한 정의는 다음과 같습니다.

P는 멱급수(powerset)를 의미하며, 모든 부분집합들의 집합입니다. 위 정의를 통해 프로토콜 메시지는 𝑃𝑟𝑜𝑝𝑠(L_C)×𝑉×P(Σ) 공간에 있음을 확인할 수 있습니다

estimator(E)는 프로토콜 메시지들(프로토콜 상태)를 0, 1, 혹은 ∅ 중 하나의 값으로 보내는 map입니다.

프로토콜 메시지 M의 estimate, validator, justification를 반환하는 helper function 𝐸,𝑉,𝐽을 다음과 같이 정의합니다.

따라서 프로토콜 메시지은 E(𝐽(𝑚))=∅ 이거나 E(𝐽(𝑚))=𝐸(𝑚)일 때 유효합니다.

메시지 𝑚2가 𝑚1에 의존성(dependency)를 가지는 것을 𝑚1≺𝑚2로 표기합니다.
𝑚1≺𝑚2⟺𝑚1=𝑚2 or ∃𝑚′∈𝐽(𝑚2).𝑚1≺𝑚′
Justification이 프로토콜 메시지들(프로토콜 상태)를 의미하기 때문에, 의존성를 통해 ∃𝜏∈𝑚𝑜(Σ):𝐽(𝑚1)→𝐽(𝑚2) 를 확인할 수 있습니다.
마찬가지로 검증자 𝑣가 보낸 메시지 𝑚에서 의존성를 반환하는 helper function D은 다음과같이 정의될 수 있습니다.

두 메시지의 선후관계를 의존성을 통해 파악할 수 있습니다. 따라서 이제 검증자의 최신 메시지(latest message)를 다음과같이 정의할 수 있습니다.

즉 latest message 𝑚 from validator 𝑣는 “𝑣가 𝑚에 의존하는 다른 메시지를 보내지 않음”, 혹은 “𝑚 이후에 다른 메시지를 보내지 않음”으로 말할 수 있습니다.
estimator를 정의하기 앞서 우선 검증자의 weight 𝑊과 메시지의 집합 𝑀에서 estimate의 점수(score)를 다음과 같이 정의합니다.

드디어 메시지 집합 𝑀에 대하여 binary consensus estimator를 가장 높은 점수를 가진 estimate를 반환하도록 다음과같이 정의할 수 있습니다. 만일 가장 높은 점수가 유일하지 않다면, ∅을 반환합니다.

지금까지 프로토콜 상태, 프로토콜 메시지, estimator를 정의했습니다. 이제 byzantine fault t를 계산하는 방법을 정의하고, t 이하의 프로토콜 상태에대해서 binary consensus가 estimate safety를 가지는지, consensus safety 정리를 만족 하는지 살펴봅시다.

한 검증자가 생성한 두 메시지가 의존성을 가지지 않을 때, 해당 메시지 쌍을 equivocation하다고 정의합니다. equivocation인지 아닌지 판별하는 함수 𝐸𝑞는 다음과 같습니다.

non-triviality 관점에서 생각해보면, common future state를 가지지 않는 𝜎1,𝜎2를 justification으로 사용하는 프로토콜 메시지 𝑚1,𝑚2는 항상 equivocation일 수 밖에 없습니다. equivocation은 합의할 수 없는 두 프로토콜 상태들을 판별하고 최종적으로 byzantine validator의 메시지를 검열하는데 사용할 수 있습니다.
equivocate한 검증자 𝑣를 byzantine하다고 부르거나 집합 𝑀에서 byantine fault를 보였다고 합니다. 따라서 메시지 집합 𝑀에서 검증자 𝑣가 byzantine faulty한지 반환하는 함수𝐵(𝑣,𝑀)를 다음과같이 정의합니다.

또한 메시지 집합 𝑀에서 byzantine nodes를 반환하는𝐵(𝑀)은 다음과 같습니다.

메시지 집합 𝑀에서 weight of byzantine faults를 계산하는 함수 faulty weights 𝐹(𝑀)를 다음과 같이 정의할 수 있습니다.

이제 프로토콜 상태를 t 이하의 byzantine faults를 포함하도록 재정의합니다. Σ𝑡로 표기하며, 메시지의 집합들이기 때문에 Σ𝑡⊂P(M)입니다.

프로토콜 상태전이(protocol executions)은 𝜎,𝜎′∈Σ𝑡 간의 transition입니다. 𝜎,𝜎′는 각각 프로토콜 메시지의 집합이기 때문에, 프로토콜 상태전이는 𝜎,𝜎′가 improper subset 관계를 가진다와 동치입니다.

앞서 논의했던 “프로토콜 상태전이는 composition에 대해 닫혀있다”는 주장도 improper subset 관게 또한 composition에 대해 닫혀있기 때문에 동일하게 성립합니다.
온전히 정의된 프로토콜 상태, 프로토콜 상태전이, estimator를 이용하면 추상적으로 정의했던 estimate safety가 binary consensus에도 동일하게 적용될 수 있습니다. 따라서 binary estimate safety를 다음과 같이 정의합니다.

Binary estimate safety는 앞서 논의한 consensus safety proof를 만족하기 때문에, byzantine fault가 t 이하의 safe estimate에 대해 내린 노드의 개별적인 결정들은 consensus safe합니다.

3. Casper the Friendly GHOST

Casper the Friendly GHOST는 fork choice에 consensus safety를 부여하는 프로토콜입니다.

이제 binary consensus에서 사용한 개념들을 이용해 blockchain consensus를 정의해봅시다. 프로토콜 상태, 상태 전이, estimate를 제외한 나머지 개념들은 binary consensus와 동일하게 사용합니다.

프로토콜 메시지는 새로운 블록을 제안하는 것입니다. 마찬가지로 3개의 요소(estimate, sender, justificatoin)를 가지는데, estimate는 부모 블록이고 justification은 해당 메시지의 유효성을 검증하는데 등 사용되는 프로토콜 상태 입니다. 메시지(새로운 블록)는 부모 블록(estimate)이 블록체인(justification)의 head일 때 유효합니다.
프로토콜 메시지s M은 다음과같이 정의됩니다.

fork choice rule을 정의하기 앞서 두 블록의 포함관계를 먼저 정의해야 합니다. 블록 𝑏1이 블록 𝑏2의 블록체인에 포함되었을 때 𝑏1↓𝑏2라고 표기합니다. 이는 앞서 봤던 𝜎′⊆𝜎′의 improper subset 관계와 동일한 정의입니다.

따라서 블록 𝑏의 점수 정의또한 변경된 포함관계를 이용하여 약간 달라지게 됩니다.

그리고 마지막으로 메시지 집합 𝑀에 대하여 블록 𝑏의 “자식 블록”들을 반환하는 helper function 𝐶(𝑏,𝑀)을 다음과같이 정의합니다.

드디어 blockchain consensus의 estimator를 정의할 수 있는 모든 개념들이 정리되었습니다. 다시한번 말하자면, 해당 estimator는 fork choice rule을 구현합니다.

이제 Consensus safety 정리를 적용하기 위하여 blockchain estimate safety를 다음과같이 정의합니다.

Blockchain estimate safety는 앞서 논의한 consensus safety proof를 만족하기 때문에, byzantine fault가 t 이하의 safe estimate에 대해 내린 노드의 개별적인 결정들은 consensus safe합니다.

4. Simple Safe Oracle

estimate safety는 모든 future state에 대한 논의였습니다. 하지만 노드가 내리는 결정은 유한한 시간 안에서 내려져야 합니다. Estimate safety를 판별하는 candidate estimate에 대한 safety가 올바른지 모델링하기 위하여 “ideal adversary”를 생각해봅시다. ideal adversary는 𝜎,𝜎′∈Σ𝑡:𝜎→𝜎′,E(𝜎′)≠E(𝜎)인 𝜎′을 검색하여 공격합니다. 즉, adversary는 estimate safety가 존재하지 않는 future state를 발견할 수 있습니다. 그리고 “ideal safety oracle”은 ideal adversary가 공격에 실패할 경우 True를 반환합니다.

만약 ideal oracle이 공격에 실패하는 “특정 상황”을 발견할 수 있다면, safety oracle을 구성하여 estimate safety가 보장되는 estimates를 선별할 수 있습니다. (물론 실제 구현으로 들어가면 완전히 ideal하기는 힘듭니다.)

앞서 말한 “특정 상황”을 일반화 해 봅시다. 먼저 두 estimate 𝑒,𝑒′간의 agreement를 𝑒≡𝑒′로 표기합니다. 이는 binary consensus의 𝑒=𝑒′, blockchain consensus의 𝑒↓𝑒′에 대응합니다. disagreement는 𝑒≢𝑒′로 표기합니다.

프로토콜 메시지들의 집합 𝑀에서 validator 𝑣𝑖는 validator 𝑣𝑗가 estimate 𝑒에 대해 동의(agreeing)함을 확인함”을 다음으로 정의합니다.
𝑣𝑖 는 유일한 최신 메시지를 𝑀 에서 가집니다. (𝐿(𝑣𝑖,𝑀))
𝑣𝑗 는 유일한 최신 메시지를 𝐽(𝐿(𝑣𝑖,𝑀)) 에서 가집니다. ( 𝐿(𝑣𝑗,𝐽(𝐿(𝑣𝑖,𝑀))))
두 메시지의 estimate가 𝑒로 같습니다. (𝐸(𝐿(𝑣𝑗,𝐽(𝐿(𝑣𝑖,𝑀))))≡𝑒)

이는 다음과 동일한 의미를 가집니다.

agreement에 대한 정의는 명확합니다. 두 검증자 모두 유일한 최신𝑚𝑖=𝐿(𝑣𝑖,𝑀),𝑚𝑗=𝐿(𝑣𝑗,𝐽(𝑚𝑖))를 보낸 것으로, 두 메시지 𝑚𝑖,𝑚𝑗의 justification은 포함관계에 있습니다. 𝑣𝑖가 알고 있는 프로토콜 상태에 대한 프로토콜 메시지이기 때문에 “𝑣𝑖는 𝑣𝑗가 estimate 𝑒에 동의하는 것을 확인할 수 있다”고 말할 수 있습니다.

반대로 “프로토콜 메시지의 집합 𝑀에서 validator 𝑣𝑗는 validator 𝑣𝑗가 estimate 𝑒에 대해 반대(disagreeing)함을 확인함”을 다음으로 정의합니다.

𝑣𝑖 는 유일한 최신 메시지를 𝑀 에서 가집니다. (𝐿(𝑣𝑖,𝑀))
𝑣𝑗 는 유일한 최신 메시지를 𝐽(𝐿(𝑣𝑖,𝑀)) 에서 가집니다. ( 𝐿(𝑣𝑗,𝐽(𝐿(𝑣𝑖,𝑀))))
𝑣𝑗가 아래 조건을 만족하는 𝑣𝑖에게 전달하지않은 메시지 𝑚∈𝑀 을 가집니다: 𝑚≻𝐿(𝑣𝑗,𝐽(𝐿(𝑣𝑖,𝑀)))

이는 다음과 동일한 의미를 가집니다.

disagreement의 경우엔 𝑣𝑗가 𝑣𝑖에게 전달한 최신 메시지 𝑚𝑗이외에 전달하지 않은 메시지 𝑚이 하나 더 존재합니다. 𝑚은 𝑚𝑗에 의존(𝑚𝑗≺𝑚)하며 𝐸(𝑚)≢𝑒입니다.

두 검증자 𝑣𝑖,𝑣𝑗가 서로 estiamte 𝑒에 대해 동의함을 확인했다는 것은, 두 검증자가 보낸 최신 메시지 𝑚𝑖,𝑚𝑗는 𝐸(𝑚𝑖)=𝐸(𝑚𝑗)=𝑒,𝐽(𝑚𝑖)=𝐽(𝑚𝑗)일 것입니다. 하지만 한가지 주목할 점은 정직한 노드들(non-equivocating nodes)은 특정 프로토콜 상태(𝑀)에서 서로 estimate e에 대해 동의하는지, 반대하는지 확인할 수 있습니다. 이러한 노드의 집합을 𝑒-clique in 𝑀 이라고 부릅니다.

4.1 Clique Oracle

(위에서 대룬 내용들은 다음 포스트에서 보다 자세하게 증명합니다.)

Clique oracle은 아래 알고리즘을 이용해 구현할 수 있습니다.

4.2 Subjective Fault Tolerance Thresholds

Tolerance threshold 𝑡를 프로토콜이 아닌 개별 노드들이 관리한다는 점에서 공격자가 target threshold를 정확히 알 수 없는 장점이 있습니다. clique에 속한 노드가 전체 노드의 1/2 이상일 때 clique oracle에 의해 보장되는 estiamte safety는 각 정직한 노드들이 설정한 tolerance thresold 𝑡의 최소값에 의존합니다. 따라서 정직한 노드 대부분이 𝑡를 낮게 설정할 경우 clique oracle의 safety는 더욱 높아질 수 있습니다. 정직한 노드들이 𝑡를 0에 가깝게 설정하면, 전체 프로토콜의 성능을 희생하고 safety를 높일 수 있습니다.

5. 결론

AbstractCBC와 CasperTFG를 통해 estimate safety protocol을 수학적으로 정의하고, 이를 binary consensus와 blockchain consensus에 적용하는 방법을 살펴보았습니다. CBC Casper는 두 노드가 common future state를 가지는 한, 한 노드가 내린 의사결정은 다른 노드 또한 동일하게 내릴 수 있음을 consensus safety 정리를 통해 증명하였습니다. 이에대해 Vlad Zamfir는 “전통적인 PBFT와 같은 합의 알고리즘과 질적으로 다르다”는 평가를 했습니다.

두 페이퍼에서 생략한 safety oracle, liveness, synchrony assumption, 다자간의 consensus safety를 다음 포스트에서 다루도록 하겠습니다.