[Blockchain] 블록체인과 합의 알고리즘

위 글은 ETRI의 '블록체인과 합의 알고리즘' 문서를 읽고 정리한 내용입니다.

참고 문서 : ETRI_블록체인과 합의알고리즘.pdf

 서론

블록체인 시스템

• 수많은 노드가 P2P 네트워크로 연결되어 사용자의 트랜잭션을 처리하는 시스템으로서, 트랜잭션에 대한 기록을 순차적으로 저장하는 일종의 분산 장부(DB로 생각하여도 무방) 시스템.
• 한 번 기록된 내용은 변경이 거의 불가능함
• 모든 노드가 동일한 트랜잭션에 대한 처리 기록을 가지도록 하여야 함 -> 합의 알고리즘

비트코인

• 최초의 블록체인 기술이 적용된 시스템
• 합의 알고리즘으로 작업 증명(Proof of Work: PoW)과 가장 긴 체인(Longest Chain)을 선택하는 방법 사용
• 최대 7 TPS밖에 처리할 수 없는 성능의 한계
• 작업 증명으로 인해 많은 에너지 낭비

이더리움

• 가장 많은 서브 트리를 가지는 체인을 메인 체인으로 보는 GHOST(Greedy Heaviest Observed Subtree)를 응용한 합의 알고리즘을 도입

비허가형(Permissionless) 블록체인 : 퍼블릭(Public) 블록체인

• 블록체인에 참여하는 노드의 참여가 제한되지 않음
• 대부분 작업 증명(PoW) 기반의 합의 알고리즘 사용

허가형(Permissioned) 블록체인 : 프라이빗(Private) 블록체인 / 컨소시움 블록체인

• 운영 방법에 따라 프라이빗 블록체인 또는 컨소시움 블록체인으로 나뉠 수 있음

• 완전히 다른 형태의 합의 알고리즘 사용 가능
• 참여하는 노드가 제한되므로 그 점을 활용할 수 있는 알고리즘의 적용이 가능
• 대표적인 알고리즘 : PBFT(Practical Byzantine Fault Tolerant)

블록체인 및 합의 알고리즘 개요

블록체인

• 트랜잭션 정보를 기록한 일종의 분산 원장(Ledger)
• 각 노드가 각각 자신의 원장(Ledger)을 가지고 있음
• 각 원장(Ledger)의 내용은 합의 알고리즘에 의해 동일하게 유지
• 하나의 엔트리는 트랜잭션으로 표현될 수 있음
• 원장(Ledger)에 기록을 원하는 사용자가 트랜잭션을 생성하여 P2P 네트워크에 전달하면 블록체인 처리 노드들이 이를 모아 블록을 생성
• 블록이 서로 체인으로 연결되어 있기 때문에, 트랜잭션의 순서화된 기록이 가능

분산 원장(Ledger)의 일관성/동일성

• 각 노느가 가지고 있는 블록체인 이미지의 동일성에서 비롯
• 블록체인 기술의 핵심은 특정 노드를 신뢰하지 않으면서 신뢰를 제공한다는 것
• 중앙집중적 방식이 아닌 개별 노드들이 자율적으로 블록을 생성하되 일종의 합의 과정을 거쳐 결국에는 모든 노드가 같은 블록체인 이미지를 가지도록 하는 방식을 사용

블록체인 시스템의 블록 생성 과정

• 한 부모에 대해 자식 블록이 여러 개가 생기는 상황 : 'fork'
• 'fork'가 된 상황은 노드 간 블록체인으로 구성된 분산 원장이 일치하지 않는 상태를 유발
• 이를 해결하는 대표적인 방법이 비트코인에서 쓰이는 가장 긴 체인을 선택하는 방법
• 각 노드 중에서 일종의 리더 노드를 선택하여 그 노드로 하여금 블록을 만들도록 하여야 하며, 그 리더 노드를 경정짓는 방법이 바로 작업 증명(PoW)이라고 할 수 있음
• 랜덤하게 하나 또는 소수의 블록을 생성할 리더를 선택하는 작업 증명(PoW)과 리더 간 다른 블록을 생성하였을 경우 이를 해결하는 정책(예: Longest chanin)으로 이루어짐

비허가형 블록체인(퍼블릭 블록체인)

• 퍼블릭 블록체인에서는 블록 생성에 성공하는 인센티브를 받을 수 있기 때문에 다수의 노드가 블록을 생성하기 위해 서로 경쟁.
• 마이닝(Mining) : 블록을 만드는 것
• 마이너(Miner) : 블록을 마이닝하는 노드
• 작업 증명(PoW)은 비허가형 블록체인에서 필수 불가결하지만, 성능 문제와 에너지 낭비 문제를 가지고 있음
• 이를 극복하기 위해 지분 증명(Proof of Stake)이나 경과 시간 증명(Proof of Elapsed Time) 등의 알고리즘이 개발되고 있으며, 샤딩(Sharding) 기법을 적용하는 연구 또한 진행 중

허가형 블록체인

• 블록체인 노드를 일정 부분 신뢰할 수 있음
• 블록을 생성할 수 있는 자격을 가진 노드를 미리 정하여 놓고, 그 노드들로 구성된 위원회(Committee)를 구성하여 그 위원회에서 멤버들 간 합의를 통해 하나의 합의된 블록을 생성하고, 이를 다른 노드들에게 전파하는 방식을 사용

합의 알고리즘

작업 증명(PoW : Proof of Work)

• 블록 생성을 하고자 하는 노드들이 특정한 해시(hash) 값을 찾는 연산을 수행하여 특정한 난이도의 작업을 수행했음을 증명하는 것
• 마이너들은 해시 값을 찾기 위해 경쟁하고, 특정 마이너가 목표 값에 해당하는 해시 값을 찾는 데 성공하면 블록이 생성
• 높은 컴퓨팅 파워를 가질수록 빠른 속도로 해시 값 계산 가능

비트코인

• 비트코인의 경우 평균 10분이 소요되도록 설계(해시 난이도를 주기적으로 조절하여 블록 생성 주기를 일정하게 유지)
• 비트코인에서는 가장 긴 체인이 최종적으로 승자가 되도록 함으로써, 'fork' 문제를 해결
• 메인에 붙지 못하고 버려지는 블록 : 고아 블록

이더리움

• 이더리움 홈스테드(Homestead) 버전은 비트코인보다 빠른 블록 생성 주기를 가짐
• 이로 인해 블록이 동시에 생성될 확률이 높아지게 되어 fork가 발생할 확률 또한 높아지게 됨
• 메인에 붙지 못하고 버려지는 블록 : 엉클 블록
• 엉클 블록을 메인 체인에 포함시키는 GHOST 계열의 알고리즘 사용
• 이더리움 GHOST의 행심은 메인 체인이 가장 긴 체인이 아니라 가장 무거운(heaviest) 체인이 된다는 것
• 엉클 블록을 카운트하여 메인 체인의 무게에 포함시켜 계산함으로서, 가장 무거운 체인을 선택하는 메커니즘으로 마이닝 후에 버려지는 블록을 줄이는 효과를 가짐
• 최대 7세대까지만 엉클 블록을 포함하도록 한정(제한이 없으면 특정 블록에 대해 유효한 엉클 블록 계산이 복잡해지기 때문)

지분 증명(PoS: Proof of Stake)

작업 증명(PoW) 방식의 과도한 에너지 소비 문제 해결을 위한 대안으로 제시

참여자의 소유 지분이 블록 생성권 지분에 반영이 되는 합의 알고리즘

마이너가 보유하고 있는 화폐의 양에 비례하여 블록을 생성(많은 지분 소유자가 쉬운 난이도의 문제를 풀게 됨)

리소스 관점에서는 효율적이나, 초기 코인 분배 문제(Initial Distribution Problem)와 Nothing at Stake 문제가 발생할 수 있음

초기 코인 분배 문제(Initial Distribution Problem)

PoS 방식에서 블록 생성 지분이 소유 지분을 기반으로 하기 때문에 초기에 코인을 많이 보유한 참여자가 블록 생성에 유리하다는 점에 의한 공정성 문제

이를 해결하기 위해, 보유한 코인의 양과 코인 보유 일수를 기반으로 참여자에게 블록 생성권을 주고, 블록 생성에 대한 보상으로 코인을 주는 방식이 고안됨(대표적 예: Peercoin)

Peercoin은 보유 코인이 적어도 코인 보유 일수가 길면 블록 생성 가능성이 커지므로, 보다 균등하게 블록 생성 기회를 줄 수 있다는 장점이 있음

적은 양의 코인이라도 장기간 보유하여 코인 보유 일수를 늘린 다음, 연속적으로 블록을 생성하는 형태의 공격을 할 수 있음

이를 극복하기 위해 Novacoin에서는 코인 보유 일수에 가중치(Weight)를 두는 방법을 도입

Nothing at Stake 문제

• 유효한 블록체인이 두 개 이상 존재하는 fork 상황에서 참여자들이 보상받을 확률을 높이기 위해 두 개 이상의 블록체인 상에서 블록을 생성함으로써, 하나의 블록체인으로 수렴해 가는 것을 어렵게 하는 것
• 이러한 상황에 공격자가 뇌물을 주고 유효한 블록체인을 임의로 바꿀수 있으며, 유효한 블록체인에 대한 합의를 빨리 이루지 못하는 문제 발생
• 최근에는 이를 보완한 위임된 지분 증명(DPoS: Delegated Proof of Stake) 방식이 제안되어 이용

DPoS

• PoS 방식이 일정한 지분을 가진 모든 노드에게 블록 생성 권한을 주었던 반면, DPoS는 지분 보유자들은 지분에 비례한 투표로 대표자를 선출하고, 대표자들에게 블록 생성과 검증에 대한 권한을 부여하여 합의에 대한 권리를 위임
• 합의에 걸리는 시간과 비용이 적게 소요
• PoW와 PoS에 비해 상대적으로 단위 시간 동안 생성되는 블록의 개수도 많음
• Tendermint, Slasher, BitShares, Ethereum Casper 등에서 사용

Tendermint

• 블록체인 어플리케이션 개발 및 블록체인 간 통신을 위한 코스모스(Cosmos) 플랫폼을 제공
• PBFT 계열 합의 알고리즘을 사용하여 대표자인 검증인들(validators)의 투표를 통해 합의가 이루어짐
• 블록체인의 각 높이에서 블록을 결정
• 라운드를 기반으로 제안자의 블록에 대해 2단계의 투표(Prevote와 Precommit)를 하여, 2/3 이상의 합의가 있으면 다음 단계로 진행
• 잠금(lock) 매커니즘을 사용(검증인이 특정 블록에 투표를 하면 투표권을 잠가서 동일 높이의 다른 블록에 투표를 못하게 함으로써 악의적인 행동을 방지)

BitShares

• 엔터프라이즈용 스마트 컨트랙트 플랫폼인 Shares 2.0을 제공
• 컬러드 코인과 같이 다양한 디지털 자산을 생성하여 이용 가능
• 블록 생성은 증인(witness)이 수행하고, 대표자(delegate)는 네트워크 정보 변경 권한이 있음
• 지분 보유자들로부터 선출된 대표자들은 증인에 대한 보상, 트랜잭션 비용, 블록 크기, 블록 주기를 포함하는 네트워크 파라미터를 변경할 권한을 가짐
• 네트워크 정보가 변경되면, 대표자들은 특별한 계정(genesis account)에 공동 서명하여 승인 절차를 거침
• 증인들은 블록 생성에 대한 보상을 받지만, 대표자들은 노력에 대한 보상이 없음

Ethereum Casper

• 사전에 선택된 검증인들이 블록 생성 및 합의 결정 권한을 가짐
• 블록 합의 결정을 위해 검증인들은 특정 블록에 대해서 보증금을 예치하고 베팅을 진행
• 특정 높이에서 하나의 블록을 결정하기 위해 2/3 이상의 검증인들이 베팅을 하여 합의를 이룰 때까지 베팅 라운드를 수행
• 검증인들은 자신이 베팅한 블록이 최종 블록으로 선택되면 보상을 받음
• 이러한 베팅은 캐스퍼 컨트랜트로 구현이 되며 베팅 생성, 베팅 라운드 참가 및 철회 기능을 제공

Bitcoin-NG

• 작업 증명(PoW)과 가장 긴 체인 선택은 유지하면서도 약간의 프로토콜 구조 변경을 통해 TPS 관점에서의 성능 향상을 도모한 프로토콜
• 'key block'과 'micro block'이라는 두 가지의 블록 유형 사용
• key block : 일종의 블록을 만들 자격을 얻는 과정
• micro block : 자격을 획득한 노드(즉, key block을 생성한 노드 -> 일종의 리더 노드)가 트랜잭션을 처리하기 위해 생성하는 블록
• key block을 생성한 노드는 다수의 micro block을 작업 증명 과정 없이 보다 빠른 주기로 생성 가능 -> TPS 향상
• 일련의 micro block이 합법적인 리더에 의해 생성되었음을 보증하기 위해 리더 노드의 디지털 서명이 포함됨
• 리더 노드는 다른 노드가 key block 마이닝에 성공하게 되면 해당 노드에 의해 대체됨
• 새로운 key block을 생성한 노드가 보다 많은 트랜잭션을 처리하여 그 수수료를 챙김으로써 이득을 얻기 위해 이전 key block을 생성한 노드가 생성한 micro block을 일부러 배제하는 것이 가능
• 이를 막기 위해 새로운 key block을 마이닝한 노드에 이전 micro block의 트랜잭션 수수료 중 일부를 나누어 주는 전략을 취함
• 리더 노드가 악의적이라면 이중 지불 공격을 하는 것이 가능함

BFT 계열

• 블록체인 시스템인 전통적인 state machine replication 시스템과 매우 유사한 특징을 가짐
• 리플리카 시스템은 싱글 호스트 시스템에게 고가용성을 제공할 수 있지만, 리플리카 간의 네트워크 오류, 리플리카 자체의 고장 등의 문제로 정상 동작되지 않을 수 있음
• 합의 프로토콜은 이러한 문제들을 다룰 수 있어야 함
• Safety : 시스템에 나쁜 일이 발생하지 않는 다는 의미. 모든 정상적인 리플리카는 같은 상태에 동의하여야 하고, 그 상태는 유효해야 함
• Liveness : 시스템은 항상 살아있어야 한다는 의미. 결국에는 어떤 상태에 동이하여야 하고, 모든 리플리카는 동의된 상태에 도달해야 함

리플리카의 비정상적인 상황

• Fail-stop : 단순히 노드가 고장이 나서 멈추는 형태의 오동작(예: Paxos, Raft)
• 비잔틴 폴트 : 리플리카가 악의적인 행동을 포함하여 임의의 동작을 할 수 있는 것(예: PBFT)

Paxos

• 고장 감내 분산 시스템에서 여러 프로세스 간에 하나의 값에 동의하기 위한 프로토콜
• 동시에 여러 개의 값이 제안되지만, 결국에는 이 중 하나의 값이 선택되도록 하는 것
• 각각의 프로세스는 값을 제안하는 제안자(proposer), 제안된 값에 투표하는 수용자(accepter), 제안된 값을 배워가는 학습자(learner)의 역할 수행 가능
• 여러 제안자에 의해 동시에 여러 값의 후보가 제안될 수 있다는 점 때문에 프로토콜의 동작이 복잡함

Raft

• Paxos를 보다 이해하기 쉽게 만들기 위해 고안
• 기본적으로 복제된 state machine 구조를 가짐
• 클라이언트 요청을 하나의 리더 노드가 처리하여 로그를 업데이트하고, 해당 로그가 다른 리플리카에도 반영되도록 하는 형태로 동작
• 리더가 문제가 있을 경우, 리더 선출 프로토콜에 따라 리더를 새롭게 선출
• Viewstamped Replication, Zab(ZooKeeper Atomic Broadcast) 프로토콜도 같은 계열의 프로토콜로 볼 수 있음

PBFT

• 비잔틴 장군 문제를 해결하기 위한 실질적인 프로토콜
• 비잔틴 장군 문제 : 장군이 악의적인 행동을 할 수 있다는 점을 가정
• 단순 고장난 노드 뿐만 아니라 악의적인 노드가 있음에도 불구하고 전체 시스템이 안정적으로 동작하도록 하는 프로토콜
• BFT 계열 프로토콜 중 실용적으로 쓰일 수 있는 가장 대표적인 프로토콜
• 리플리카 중 의사결정의 리더 역할을 하는 primary 노드가 있으며, primary 노드의 주도하에 순차적으로 명령이 수행됨
• primary 노드가 고장이 나거나 악의적인 행동을 하게 될 경우 'view change'라는 절차를 통해 primary 노드를 바꿈

허가형 블록체인 시스템에의 적용

• 하이퍼레저 패브릭(Fabric) : 0.6 버전에서는 PBFT 프로토콜을 합의 알고리즘으로 사용. 1.0의 경우, Kafka 기반의 Ordering Service에 기반한 합의 알고리즘을 사용. (Kafka는 Zab 프로토콜을 사용하는 ZooKeeper 기반으로 동작)
• Tendermint : 변형된 PBFT 프로토콜 사용
• R3 Corda : 트랜잭션 처리시 서기 서비스(Notary Service)에 의존. Raft나 PBFT 프로토콜에 의해 고장 감내적으로 동작

경과 시간 증명(PoET: Proof of Elapsed Time)

• 작업 증명(PoW) 방식의 경쟁적 해싱 연산으로 낭비되는 에너지를 줄이면서 작업 증명(PoW)과 유사한 Security를 보장하기 위해 최근에 제시된 방식
• 하이퍼레저 쏘투스 레이크(Sawtooth Lake)에서 제안된 합의 알고리즘
• 신뢰할 수 있는 보안 모듈(Intel SGX)을 기반으로 블록을 생성하는 리더를 랜덤하게 선정
• 가능한 다수의 노드가 합의에 참여하여 공정하게 리더를 선정하도록 함
• 보안 CPU 명령을 사용하여 리더를 선정함으로써 안정성과 무작위성(Randomness)을 보장
• 마이너의 동작을 시스템 보안 모듈인 enclave에서 수행되도록 함으로써, 원천적으로 악의적인 노드의 개입을 막음
• 장점 : 리더 선정 참가 비용이 낮아 다수의 검증인들이 참여할 수 있으므로 합의 알고리즘의 견고성이 증가
• 단점 : Intel SGX에 의존

Sharding 기법

• 일반적으로 데이터베이스에서 효율적으로 확장성을 확보하기 위해 사용하는 기법
• 전체 DB를 조각내어 각 조각이 다수의 각기 다른 사이트에 의해 처리되도록 하는 기법
• 블록체인에 샤딩 기법을 적용함에 있어서 어떤 노드가 어떤 샤드를 담당하게 할 것인가, 각 샤드에서 어떤 트랜잭션을 담당하게 할 것인가의 문제가 있음
• 샤드는 트랜잭션을 병렬 처리할 수 있다는 점에서 성능 향상을 기대
• 여러 샤드에 걸쳐서 처리해야 하는 크로스 샤드 트랜잭션이 존재하고, 상황에 따라 각 샤드에서 처리한 트랜잭션에 대해 전역적인 관점에서 conflict가 없는지를 검사해야 하기 때문에 일반적으로 성능이 샤드 갯수에 따라 선형적으로 증가하지 않음
• Elastico : 마이닝 노드들을 로컬 위원회(Committee)라고 불리는 소규모 그룹들로 분할하여 각 로컬 위원회가 서로 다른 트랜잭션 집합을 병렬 처리하도록 하는 방법을 제서
• 이더리움 : 무작위로 선택된 네트워크 노드 집합을 구성하여 특정 계정의 접두사와 관련된 트랜잭션만을 검증하는 구조. 여러 조각으로 분리된 블록체인 상태가 네트워크의 다른 노드들에 분산되어 저장.

결론

• 블록체인 시스템을 특징짓는 것 중 하나는 합의 알고리즘임
• 비트코인 이후의 시스템들은 성능과 에너지 문제를 해결하기 위해 다양한 다른 특성을 가진 독특한 방식의 합의 알고리즘을 도입
• 합의 알고리즘은 성능, 에너지, 보안, 개방성이라는 가치 중 어디에 중점을 두는가에 따라 다양한 형태로 개발될 수 있음