합의 알고리즘이란?
다수의 참여자들이 통일된 의사결정을 하기 위해 사용하는 알고리즘.
블록체인의 경우 통일된 의사결정을 내릴 수 있는 권위있는 중앙(Center)가 존재하지 않기 때문에, 이러한 상황에서 합리적이고 효율적인 의사결정을 내릴 수 있는 알고리즘이 필요함.

합의 알고리즘에서 고려해야 할 세 가지
1. Finality Problem (완결성 문제)
2. 51% Attack/BTF (51% 공격과 비잔틴 결함)
3. Transaction Cost (트랜잭션 수수료)

🔗 합의 알고리즘의 2가지 속성

1) Safety

문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다. 모든 정상적인 참여자는 같은 상태에 동의하여야 하고, 그 상태는 유효해야 한다.

2) Liveness

문제없는 노드들은 반드시 합의를 한다. 시스템은 항상 살아 있어야 한다. 결국 어떤 상태에 동의해야 하고, 모든 참여자는 동의된 상태에 도달해야 한다.

그렇다면,
비동기 네트워크 내에서 Safety와 Liveness를 모두 완벽히 충족하는 합의 알고리즘이 있는가?

→ 없다 = FLP Impossibility (=FLP Theorem, Fischer, Lynch, and Paterson Impossibility)

• 합의 알고리즘을 선택한다는 것은 Safety와 Liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다.

  💬 블록체인이 구동되는 네트워크는 '비동기 네트워크'다. 그렇다면 비동기 네트워크란?
  네트워크는, 메시지 교환 시 발생하는 대기 시간 여부에 따라 세 가지로 나뉜다.
  - 동기 네트워크(Synchronous Network): 어떤 메시지를 보내면, 정해진 시간 안에 반드시 응답이 도착하는 네트워크. 네트워크 사이에 데이터 통신이 ‘반드시’ 이루어져야 하는 경우 사용 (예: 비행기, 우주선의 통신)
  - 비동기 네트워크(Asynchronous Network): 메시지가 수신 노드에 제대로 도착했는지 여부, 수신 노드가 응답하는데 걸리는 시간을 알 수 없는 네트워크. 특정 노드가 임의로 메시지를 전송하지 않거나 거짓 데이터를 전송하는 배신행위가 가능함. (예: 인터넷, 블록체인 네트워크)
  - 부분 동기 네트워크(Partial synchronous Network): 노드와 노드 사이에 메시지가 도달하는 것은 보증하지만, 언제 도달할지는 알 수 없는 네트워크.

Liveness over Safety (PoW)

잘못된 합의가 이루어질 수 있지만 어떻게든 합의는 한다.

(=나카모토 합의, Nakamoto Consensus)

• 언제나 더 어려운 문제를 푼 체인이 있으면, 그 체인을 유효한 체인으로 판단한다.
• 지금 체인보다 더 긴 체인을 만들 해시 파워가 있다? 이미 합의된 블록이라도 언제든지 다른 블록으로 대체할 수 있음. = Finality(완결성) 보장 X *완결성: 거래는 절대 되돌려질 수 없고 수정될 수 없는 성질
  
• 즉 Liveness를 위해서 Safety를 포기한 것임.
• 점점 Safety도 보장할 방법을 추가하는 방식으로 발전함 →예: Casper, the Friendly Finality Gadget

Safety over Liveness (BFT 계열)

합의가 잘못된 가능성이 있다면 블록을 만들지 않는다.

• PBFT에 기반한 BFT 계열 합의 알고리즘들이 주로 속함. → 예: 텐더민트(Tendermint, Cosmos에서 사용)
• 텐더민트는 Partial Synchronous Network Model (정해진 시간 안에 메시지가 도달하는 것을 보장하지만 그 정해진 시간을 알 수 없음)을 사용
• 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일이 없음.
• But, 비동기 네트워크(전송한 메시지가 시간 안에 도달 보장 X)에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있음. Liveness는 보장되지 않음.

🔗 완결성 (Finality)

블록체인의 기본 속성인 비가역성을 표현하는 말로, 거래는 절대 되돌려질 수 없고 수정될 수 없는 성질을 의미 (신용카드로 결제하면 바로 결제가 되는 것.)

• 확률적 완결성 (Probabilistic Finality) - PoW, PoS : 기록이 바로 성립되지 않음. 어느 정도의 시간을 기다려야 트랜잭션이 완결성을 갖춰 비가역적인 상태가 된다.
  
• 절대적 완결성 (Absolute Finality) - PBFT 기반 프로토콜 (텐터민트) : 트랜잭션에 블록이 포함되고 블록체인에 추가되면 즉시 완료된 것으로 간주한다. 이 경우 리더가 블록을 제안하고 검증인 위원회의 충분한 비율이 블록을 승인해야 커민된다.
  
• 경제적 완결성 (Economic Finality) : 이 블록을 되돌리는 경우에 대한 금전적 비용이 많이 드는지를 판단함.

🔗 CAP 정리 (CAP Theorem)

확률적 완결성과 절대적 완결성 간의 절충에 대해서 생각해보자.

💬 CAP 정리
“Cheap, Fast, and Good: Pick Two”
분산 컴퓨터 시스템에서, Consistency(일관성), Availability(가용성), Partition Tolerance(파티션 허용) 세 가지 조건을 모두 만족하는 것이 불가능하다는 것을 증명한 정리.

• 일관성: 모든 클라이언트가 동시에 동일한 데이터를 볼 수 있음. 데이터가 하나의 노드에 기록될 때마다 이 데이터가 ‘성공’으로 간주되기 전에 시스템의 다른 모든 노드로 즉시 전달되거나 복제되어야 함.
• 가용성: 하나 이상의 노드가 작동 중지된 경우에도 데이터를 요청하는 클라이언트가 응답을 받음. 모든 작업 중인 노드는 예외 없이 모든 요청에 대해 유효한 응답을 리턴함.
• 파티션 허용: 파티션(= 분산 시스템 내 통신 단절 = 두 노드 간의 연결 유실) 시스템 내 노드 간에 다수의 통신 단절에도 불구하고 클러스터가 계속해서 작동해야 함.

• 일관성 선호: 부정확한 트랜잭션 진행 < 전체 애플리케이션 중단. 절대적인 최종 체인을 선호한다. (절대적 완결성)
• 가용성 선호: 부정확한 트랜잭션 진행 > 전체 애플리케이션 중단. 확률적으로 최종 체인을 선호한다. (확률적 완결성)
• 완결성은 사용자 경험에 근본적으로 영향을 미친다.

🔗 CFT vs BFT

CFT (Crash Fault Tolerance) : 분산시스템에서 노드가 비정상적인 충돌에 의해 문제가 생기더라도, 나머지 시스템에서 서비스를 할 수 있게 작동하는 작동방식

BFT (Byzantine Fault Tolerance): 더욱 복잡하고 악의적인 공격이 있을 수 있는 시스템에 적용된다. 비트코인의 경우 CFT, BFT 보다 높은 수준의 신뢰작업을 필요로 한다. 이것이 바로 PoW이다.

🔗 BFT (Byzantine Fault Tolerance)

💬 비잔티움 장군 문제
배신자가 있는 상황에서는 여러 장군들이 받은 명령을 진실이라고 확정하기 어렵다는 것을 비유한 말. 분산 컴퓨터 시스템에서 일부 노드의 장애와 해킹 공격이 있으면 시스템을 안정적으로 운영하기 어렵다는 원리를 설명한다. (1982년 논문에서 처음 등장)

• 1982년 논문에서 제안된 방식이지만, 2009년 사토시 나카모토의 비트코인에서 처음으로 구현됨.
• ‘Tolerance’는 견딘다라는 뜻으로, ‘배신자가 있어도 견딘다’, ‘해킹이 있어도 견딘다’라는 의미.
  

✔️ 처리절차

1. 클라이언트가 모든 노드에 요청을 Broadcast
2. 리더가 먼저 순차적으로 명령을 다른 노드에 전달
3. 각 노드는 Broadcast 된 명령을 리더를 포함한 모든 노드에게 회신
4. 전달된 총 명령이 일정 수 (2n개)가 되면 리더를 포함한 모든 노드에게 재 전송
5. 명령을 실행하고 블록을 등록해 클라이언트에 메시지 반환

✔️ 장점

• PoW, PoS와 달리 다수결로 의사결정을 하고 블록을 만들기 때문에 분기가 발생하지 않음.
• 한 번 확정된 블록은 변경되지 않기 때문에 완결성을 확보함
• PoW와 같이 조건을 만족시킬 때까지 계산을 반복하지 않아도 되기 때문에 고속으로 동작
• 부정 사용을 하고자 해도 과반수를 획득해야 하기 때문에 장애에 매우 강력한 내성을 지님
• 모든 참가자가 리더의 움직임을 감시해 거짓말로 판단되면 다수결로 리더 교체 가능

✔️ 단점

• 참가자 전원과 의사소통해야 하기 때문에 참가자 증가, 통신량 증가하면 처리량 저하됨.
  
  

🔗 PBFT(Practical Byzantine Fault Tolerance)

기존의 BFT: 동기식 네트워크에서만 합의가 가능
PBFT: 비동기 네트워크에서 합의를 이룰 수 있게 한 합의 알고리즘

✔️ 처리절차

1. 리더가 클라이언트의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에게 전파
2. 리더의 메시지를 받은 노드들은 나머지 노드들에게 전파
3. 모든 노드는 자신이 다른 노드에서 가장 많이 받은 메시지가 무엇인지 다른 노드들에게 전파
4. 위 과정이 끝나면 모든 노드들은 정족수 이상이 동의한 같은 데이터를 가지게 됨.

✔️ 장점

• 트랜잭션 완결성과 빠른 거래 확정: PBFT는 다음 블록 합의가 이루어진다면 제안된 블록의 합의 내용이 확정되어 한번 확인(1 Confirmation)으로 거래가 완결되므로 거래 확정시간이 짧다.
• 저에너지로 비용 감소: PBFT는 PoW가 아니고, PoS를 기본으로 하기 때문에 에너지 사용량이 적고 거래 비용이 작음.

✔️ 한계

• 합의 그룹 크기가 커짐에 따라 합의 속도가 느려짐: 100개 노드로 운영하면 거래 확정에 약 6초가 걸림
• 합의 그룹의 각 노드는 모든 다른 노드들과 두번씩 메시지를 주고받아야 하므로 전체 노드 N의 제곱 수준의 커뮤니케이션 교환이 필요함 —> 100개 - 16,434번, 49개 - 3,888번

🔗 Tendermint

• Cosmos에서 사용하는 합의 알고리즘
• PBFT 개념+ DPoS 개념 → 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘.
  Tendermint 합의 프로세스: Propose - Prevote - Precommit
• PBFT 합의 프로세스: Pre-Pare - Prepare - Commit
• PBFT : 하나의 노드가 하나의 투표를 하는 방식, 가장 많은 투표를 받은 블록 승인
• Tendermint(PBFT + DPoS): 지분을 기반으로 투표하는 방식, 투표 노드 수<지분!!

✔️ 장점

• 블록을 노드들에게 전파하는 방식을 단순화하고 노드의 수를 늘릴 수 있게 함.
• 블록제안자를 수시로 교체할 수 있게 하여 안정성을 높임.
• 비잔티움 노드를 쉽게 발견하여 지분을 빼앗는 방법으로 처벌함. (기존엔 처벌 못했음)