[블록체인] 이더리움-consensus

Consensus

consensus 메커니즘으로 proof-of-work, proof-of-stack, proof-of-history등이 존재고 이는 sybil attack을 막기 위한 consensus 메커니즘의 일부이다.
즉 이외에도 다른 여러 consensus 메커니즘이 존재한다.

이더리움 블록체인에서는 consensus에 도달한다는 것은 2/3의 노드가 상태에 동의했음을 의미한다.
# 참고로 sybil attack이란 하나의 사용자가 여러 사람역할을 하는 것. 즉 ip를 바꿔가며 공격하기 등이다.

Consensus Mechanusm

이더리움은 pos메커니즘을 사용하고,
이를 이용하여, stacker에게 validator가 입장비를 내어, 나쁜 일을 하면 돈을 slash하고 착한 일을 하면 reword를 준다.
또한 pos를 통해 네트워크를 공격하기 위해서는 극도로 높은 cost를 지불하게 만든다.

참고로 pow에서는 명시적인 패널티가 없지만, pos에서는 존재한다.

pos에는 다양한 블록이 경쟁할 때, fork-choice mechanism을 사용한다.
이는 heaviest한 블록을 여러 블록중에 선택하는 것이다.
heaviest하다는 것은 validator가 그 블록에 투표를 많이 했다는 것이다.

참고로 비트코인에서는 logest chain mechanism을 사용한다.

Gasper

이더리움은 LMD ghost fork choice rule+ casper 즉 gasper라는 consensus mechanism을 사용한다.

• Casper란 특정 블럭을 finalized하여 참여자들이 canonical한 체인에 잘 따라가고 있구나 확신을 준다.
• fork choice algorithm은 투표를 통해 올바른 노드를 쉽게 찾게 해준다.

gasper의 핵심은 ether를 deposit한 상태에서 게으르거나 못된 짓을 하는 유저의 예치금을 삭감하는 것이다.

Finality

블록은 finalized되기 위해 두가지 upgrade를 거친다.

1. 전체 구성원의 3분의 2 이상이 특정 블록이 canonical chain에 포함되었다고 투표를 하면 justified된다.
2. justified된 블록 위에 다른 블록이 justified되면 그 블록은 finalized된다. 이렇게 finalized된 블록은 뒤집을 수는 있지만 매우 큰 금액이 필요하다.
3. 이 과정은 모든 블록에 적용되는 것이 아니라 checkpoint라고 불리는 epoch-boundary block에만 적용된다. 즉 checkpoint들간에 justified되고 finalized된다. 이런 링크를 supermajority link라고 한다.
   # 여기서 3분의 2를 super majority라고 한다.

여기서 epoch란 32개의 slot을 묶은 것이다. 이렇게 묶은 이유는 블록은 12초마다 생성되는데 12초만에 모든 노드가 통신이 된다는 보장이 없기에 시간적 여유로움을 위해 epoch단위로 묶어 checkpoint에 대해서만 finalized하는 것이다.

만약 특정 공격자가 finalized된 블록을 바꾸려면

• 적어도 3분의 2에 해당하는 staked ether를 가지고 있어, power를 통해 블록을 결정한다.
• 혹은 3분의 1의 표로, fork되어 3분의 1씩 투표된 블록 두개에, double vote를 통해 둘다 3분의 2로 만들어 justified되게 만들어 혼동을 준다. 이런 경우 evm은 사기친 validator를 파악할 수 있어 3분의 1이상의 staked block가 없어지는 것을 받아들여야 한다.Inactivity leakGasper는 plausible liveness를 제공하는데, 이는 3분의 2가 정직하게 행동한다면 나머지와 무관하게 블록이 계속 생성된다는 것이다.
  그럼 나머지 3분의 1은 사기를 쳤다는 것을 의미하는데, 이들은 아무것도 할 수 없다.

참고로 gasper에는 추가적인 liveness 실패에 대한 대책이 존재한다.
이는 inactivity leak라고 불리며, 4개의 epoch동안 justified되지 않으면 5epoch부터 다수의 chain에 투표하지 않은 validator의 stake을 slashing시키는 것이다.
그럼 궁극적으로 finalized 안된 게 해소된다.

Fork Choice: LMD-GHOST

이는 latest message-driven greedy heaviest observed subtree를 의미한다.

• latest message-driven이란 여러 매세지가 도착했을 때, 오직 최신의 것만 고려한다는 뜻.
  일반적인 상황에서는 fork choice가 필요없다.
  다만 네트워크가 비동기적이거나, 나쁜 블록 생성자가 존재할 때는 fork choice algorithm이 이로 부터 보호한다.
  이 알고리즘은 여러 fork중 heaviest subtree를 선택하며, validator로 부터 여러 메세지가 수신 된 경우 최신의 메세지만을 고려한다.

따라서 각 validator는 이 규칙을 통해 블록을 평가하고 canonical한 상태를 유지한다.

PoS Validator

validator가 되기 위해서는 32ether를 예치해야 하며
바로 투표를 할 수 있는 게 아니라 활성화 큐에서 대기한다.
대기를 하는 이유는 전체 validator 수를 조절하기 위해서이다.
이러면 알고리즘이 투표를 하는 commitee를 랜덤하게 선택한다.
이렇게 활성화가 된다면 주변 노드들로부터 새로운 블록에 대한 정보를 받게 된다.
정보를 받은 validator는 블록의 트랜잭션들을 다시 실행하여 타당한지 확인하고, 이와 더불어 블록에 대한 signature도 확인한다.
확인을 마친 validator는 블록에 대한 투표를 네트워크에 뿌린다.

참고로 매 epoch마다 32개의 블록이 존재하고 알고리즘은 validator가 매 epoch마다 commitee에 들어가 투표를 하게 하지만, 매 slot마다 투표를 하게 하지 않는다.

다만 컴퓨터는 매 슬롯마다 이에 참여하는 validator가 보낸 vote에 대해 signature를 확인해야 한다.
근데 모든 signature를 확인하는 것은 무리가 있으므로 BLS라는 기법을 사용한다.

How do validators selected

이것은 RANDAO로는 슈도랜덤 프로세스를 사용한다.
이를 통해 모든 validator는 commitee로 참여될 동등한 확률을 보장한다.

How a transaction gets executed in ethereum pos

트랜잭션이 타당하다고 판단되면 , 노드는 그것을 자신의 mempool에 넣는다.
또한 다른 노드들에게 알린다.

만약 블록 proposer가 된다면 mempool에서 블록을 꺼내 execution payload에 넣고, 내부에서 실행을 하여 상태를 변화시킨다.
이런 변화는 block의 부분으로 포장된다.

Finality

finalizeded된 블록은 못 바꿀까?
그렇지 않다. 버리게 될 아주 많은 ether를 가지고 있다면 바꿀 수 있다.
각 validator는 체크포인트 쌍(finalized될 블록, justified될 블록)에 투표를 한다.
최종화된 블록을 되돌리기 위해서는 3분의 1에 해당하는 투표권의 ether를 잃을 생각을 해야 한다.
예를 들면 finalized된 블럭은, 다음에 justified된 블럭이 있다는 뜻이다. 이 justified된 블럭을 double vote를 통해서 무효화 시키면 이전 블럭은 justified로 돌아간다.
다만 double vote를 했으므로 이에 소모된 3분의1에 해당하는 ether는 모두 없어질 감수를 해야 한다.
즉 inactivity leak에 따라 다시 finalized될 때까지 약한 쪽을 slashing한다.
만약 공격자가 더 적은 쪽에 해당하는 블록에 투표했다면, 이제 투표한 3분의 1이 날라간다.

GHOST & CASPER

비트코인의 logest rule에 따르면 attacker의 chain이 주가 되지만.
이게 없다고 했을 때는 5B가 최신 블록이 된다.
만약 GHOST를 따르면.
1B와 1A중에서는 11개의 블록을 가진 1B가 5개의 블럭을 가진 1A보다 heavy하므로 1B를 선택하고 이런식으로 4B가 된다.

Algorithm LMD GHOST Fork Choice Rule

일단 Block을 처음 발생한 블록으로 두고
Message는 가장 최근의 메세지를 받는다.
B가 leaf, 즉 가장 최신 블록이 아닐때까지
B를 선택하는 데 가장 weight가 큰 블럭을 선택하면서 반복한다.

투표 기준에서 봤을 때
B기준 위는 2표, 아래는 5표이므로 C를 선택
K,H,E중 E가 3표고 2표보다 많으므로 E가 가장 최신노드가 된다.

즉 노드 별로 가장 최신의 노드라고 생각하는 블럭이 다른 상태에서 서로 투표를 했을 경우
이중 stake of sum이 가장 큰 것을 선택한다.

Gasper ffg

epoch는 32개의 slot을 포함하고 매 slot은 12초마다 발생하므로 epoch는 6.4분 만에 발생한다.
epoch의 첫번째 slot을 checkpoint 혹은 epoch boundary block이라고 한다.
attestation을 만드는 블록은 여기에 block을 넣고 source에다가 마지막으로 justified 된 checkpoint 블록을 넣고, target에 local에서의 최신 checkpoint를 넣는다.

참고로 attestation이란 Proof-of-Stake 프로토콜에서 검증자가 특정 블록에 대한 의견이나 지지를 표명하는 행위를 가리킨다.

block과 attestation의 차이

Finalized와 justified

finality는 일단 canonical 체인에 포함되면 없어지거나, 삭제되거나, 바뀌지 않는다를 의미

Vote

Vote는 pair쌍에 투표하는 것
(S, T)로 쌍이 존재하며 s는 source block, t는 target block을 의미
참고로 반드시 T가 최신이다.
S는 validator가 가지고 있는 최근 justified된 블록이다.
T는 validator가 로컬 뷰에서 가장 최신이의 체크포인트라고 판단하는 블럭이다.

justified

블록 b가justified 되었다는 것은 둘 중 하나이다.

1. b가 genesis block이다.
2. vote(A,B), 즉 b가 target인 vote가 super majority(2/3)을 달성하였다.finalizedb가 finalize되었다는 것은 둘 중 하나이다.
3. b가 genesis block이다.
4. vote(b, c)인 vote가 super majority를 달성하여 c가 justified된 상태에서 source가 b인 경우에 b가 finalized 되었다.

Casper FFG rules

validator는 다음과 같은 일을 하면 안된다.
(s1, t1), (s2, t2)에 대하여

1. double vote, 즉 height(t1) = heigh(t2)인 경우
2. surround vote, 즉 height(s1) < height(s2) < height(t2) < height(t1) 즉 (s1, t1)이 (s2, t2)를 감싸는 형태의 투표가 있으면 안된다

safety & liveness

• accountable safety: 두개의 conflicting block이 존재한다면 이 때 rule을 위반한 1/3의 validator가 식별될 수 있다.
• plausible liveness:끊어지지않고 진전된다. 어떤 상태이든 규정을 위반하지 않고 새로운 블럭을 finalized 할 수 있다.

safety proof

만약 conflicting한 두 block이 모두 finalized 되었을 때
위반 행위를 찾아, slashing을 하여 벌칙을 내린다.
참고로 둘 다 finalized되었다는 것은 전체의 3분의 2를 찬성을 받아야 하는데
합쳐서 3분의 4이므로 3분의 1이 double vote가 있었다는 것이다.

case1: 충돌하는 두 블록이 height가 같을 경우 ->double vote
그럼 금지 조항을 어긴 자가 반드시 존재한다. 그러므로 처벌가능
case2: height(a) < height(b)

B라는 chain에 a,c가 surround vote 되므로 위반

Liveness proof

P0이 justified된 블록이라고 할 때 justified만 된, P0이 있고, 그 다음에 finalized된 Q가 있다. 그럼 P0은 finalized 못할까?
된다
(P0, P1)을 통해 어떤 casper FFG rule을 위반하지 않고 vote할 수 있다.
즉 당장 다음 것만 투표할 수 있는 게 아니라, 후계자에 대해서는 투표할 수 있다.
그러면 P0이 finalized될 수 있다.

Slashing

stake된 ether를 삭감하는 것.

• offline으로 갔다: 규칙을 위반한거기보다는 그냥 끈거이므로 약간만 삭감
• contradictory vote를 했다: 위반한 validator 수에 비례하게 더 심하게 삭감한다.