brunch

You can make anything
by writing

C.S.Lewis

by CURG in Seoul Feb 11. 2019

OmniLedger

A Secure,Scale-Out, Decentralized Ledger

블록체인은 결제를 관리하는 제 3자가 없는 분산원장이다. 그러나 대표적인 퍼블릭 블록체인인 비트코인, 이더리움의 경우 Visa에 비하면 매우 낮은 TPS를 보인다. 따라서, 본 글은 블록체인의 확장성 문제를 해결하는 방법중 하나인 Sharding에 대하여 다루고, 비트코인 기반의 블록체인에서 Sharding의 구현법을 제시한다.

앞서 게시된 “블록체인의 확장성 문제와 솔루션 소개 - 2”를 통해 블록체인은 확장성에 대한 문제 겪고 있고, 이에 대한 해결책을 몇가지 제시하였다. 본 글에서는 해결책중 하나인 샤딩(Sharding)에 대하여 다루려고 한다.

본 게시글은 OmniLedger: A secure, scale-out, decentralized ledger via sharding 을 기반으로 작성되었다.

트릴레마(Trillema)

최근 여러 신생 블록체인의 경우, PBFT와 같은 합의 알고리즘을 적용하여 트랜잭션의 처리시간을 줄이는 방법으로 확장성 문제를 해결하고있다. 그러나 여전히 합의 과정에서는 트랜잭션을 중복으로 검증하는 과정이 생기기 마련이다. 블록체인과 같은 분산 원장에서는 트랜잭션의 처리와 참여자의 인원수가 증가함에 따라 확장성이 고려되며, 이와함께 보안문제 또한 동반된다. 이를 잘 나타낸 그림이 트릴레마(Trillema)이다.

Trillema

탈중앙화, 확장성, 보안성은 서로간의 의존성이 존재하여 한 부분을 높이게 되면 Trade-off가 발생하게 된다. 예를 들면, 네트워크를 쪼개어 확장성을 높이는 방법인 샤딩(Sharding)은 쪼개진 네트워크의 개수 만큼 확장성이 늘어나지만, 그 만큼 각 네트워크의 규모가 작아지므로 공격을 당할 가능성이 커지게 된다.

샤드의 크기에 따른 신뢰도를 나타낸 그래프

위 그래프는 샤드의 크기, 즉 네트워크의 크기에 따른 네트워크의 신뢰도를 나타낸 것이다. 네트워크를 쪼갤수록 네트워크의 크기는 작아지지만 그만큼 신뢰도가 낮아짐을 볼 수 있다.

따라서, 비트코인 환경에서 보안과 확장, 탈중앙화에 trade-off가 생기지 않고, Visa와 같은 중앙 결제 시스템과 유사한 트랜잭션을 제공하는 아키텍쳐인 OmniLedger가 좋은 방법이 될 수 있다.

OmniLedger란?

Omniledger의 구조

Omniledger는 비트코인 기반의 UTXO를 사용하는 블록체인에서 확장성 문제를 해결하기 위한 샤딩(Sharding)프로토콜이다. Omniledger에서는 다음 6가지 요소를 목표로 삼고있다.

1. 완벽한 탈 중앙화 : 신뢰되지 않은 제 3자 혹은 개인에 의해 네트워크가 무너지지 않아야 한다.

2. 샤드별 할당된 트랜잭션의 안전한 처리 : 각 샤드에 주기적으로 할당되는 트랜잭션을 정확하고 연속적으로 처리해야 한다.

3. 샤드간의 원자적인(atomic) 트랜잭션 처리 : 각 샤드는 할당된 트랜잭션을 원자적으로 처리한다.

4. 참여자의 수가 증가함에 따라 네트워크의 확장성이 증가함(scale-out) : 네트워크 참여자가 늘어날수록 샤드의 갯수를 늘려 확장성을 이어나간다.

5. 스토리지 오버헤드(storage overhead)를 줄인다 : 검증자들이 모든 트랜잭션을 저장하지 않아도 되도록 한다.

6. 트랜잭션 처리속도의 향상 : 트랜잭션을 처리하는 과정을 절감시켜 처리속도의 향상을 추구한다.

RandHound 프로토콜

RandHound 프로토콜은 비잔티움 환경에서 편향되지 않은 분산 랜덤성을 제공하는 프로토콜이다. 블록체인 기술에서는 랜덤 변수를 생성하는 것이 굉장히 어렵다. 랜덤 변수는 어떠한 변수를 기반으로 만들어 져야 하는데, 블록체인은 모든 정보가 공개되므로 랜덤 변수를 예측할 수 있게되는 상황이 발생한다. RandHound 프로토콜은 이를 해결하기 위하여 BFT 기반으로 서로 다른 그룹의 서버의 output을 받아 결합하여 난수를 만들어 낸다. OmniLedger에서는 이러한 난수 생성이 특정 epoch(주기) 마다 일어나게 된다.

RandHound protocol

RandHound로 얻어진 랜덤 변수는 여러 부분에 사용될 수 있다.

- 각 샤드에 임의로 트랜잭션을 할당.

- 대표자 선출시 임의로 선출 가능.

- 검증자를 임의의 샤드에 배치.

Omniledger에서는 Sybil-attack 저항성을 위해 POW나 POS와 같은 합의 알고리즘을 사용하지만, 블록 생성에는 PBFT 알고리즘을 사용한다.

PBFT는 미리 선정된 21명의 검증자에 대하여 과반수의 동의만 얻으면 합의에 성공했다고 간주하는 합의 알고리즘이다. 이는 선택된 검증자들 간의 합의만 거치면 되기 때문에 빠른 속도로 트랜잭션을 처리할 수 있다는 장점이 있다. 다음은 PBFT 합의가 일어나는 과정이다.

PBFT 합의

1. 클라이언트가 트랜잭션이 담긴 블록을 시작노드(0)에게 전송한다. (request)

2. 시작노드는 나머지 n-1개의 노드에게 블록을 보낸다. (pre-prepare)

3. n-1 개의 노드는 블록을 받고, 다시 다른 노드들에게 자신이 블록을 받았다는 사실을 전송한다. (prepare)

4. 각 노드는 다른 노드들에게서 받은 결과에 대해 유효성 검사 후 자신의 최종상태를 다른 n-1개의 노드에게 알림. (commit)

5. 최종적으로 각 노드의 상태를 바탕으로 2 / 3이상 합의 되었을 경우 블록이 생성되고 트랜잭션이 수행됨. (reply)

2/3 이상의 노드가 합의해야 하기에 PBFT 네트워크는 (n-1)/3개 까지의 노드가 악의적인 공격 일 경우를 막을 수 있습니다.

Cross - Shard Transaction with Atomix

비트코인의 경우 각 트랜잭션은 블록에 UTXO(Unspent Transaction Output)형태로 저장되고, Causal+Consistency 모델 형태, 즉 이중지불을 방지하며 거래의 충돌이 없게한다.

그러나 OmniLedger에서는 Sharding이 구현되어 있는 형태이므로, 각 샤드별로 트랜잭션을 atomic(원자적)하게 처리할 필요가 있다. 따라서 Byzantine Shard Atomic Commit protocol인 Atomix를 통해 해결한다.

Atomix 프로토콜은 트랜잭션에 대하여 lock - unlock 프로토콜을 사용하는 방법으로 트랜잭션을 원자적으로 처리한다. 이는 BFT 합의를 제공하는 클라이언트 기반으로 다음 3단계로 진행된다.

Cross Shard Transaction with Atomix

1. 클라이언트가 소비할 UTXO가 포함된 input 샤드에 트랜잭션을 발생시키고, 트랜잭션의 결과물은 임의의 output 샤드에 생성된다. 발생한 트랜잭션은 네트워크에 broadcast된다.

2. Lock-phase 에서는 모든 input 샤드에 대해 트랜잭션이 소비될 수 있는지를 먼저 검증한다. 검증이 완료되면 샤드의 블록에 기록되고, 해당 트랜잭션이 Accept 되었음을 proof-of-acceptance 라는 메시지를 broadcast하여 전파한다. 만약 트랜잭션이 Reject된다면 proof-of-rejection을 배포한다. (gossip)

메시지를 받은 시점부터 해당 트랜잭션은 lock이 걸리게 된다. 트랜잭션은 아직 처리되지 않은 상황이고, 클라이언트는 lock 상태의 트랜잭션을 확인할 수 있지만 철회하는 것은 불가능하다.

3. Unlock-phase 에서는 모든 input 샤드에 대하여 accept된 트랜잭션을 output샤드에 commit 하고, unlock-to-commit 메시지을 배포하여 unlock한다. 만약 트랜잭션이 reject된 경우 unlock-to-abort 메시지를 배포하여 unlock한다.

간혹 Unlock-phase에 도달하지 못하거나 클라이언트가 충돌 혹은 클라이언트가 private key를 잃어버리는 경우, input 샤드의 검증자들이 unlock 메시지를 생성하도록 할 수 있다.

그러나, 위의 각 phase 과정에 의하면 대부분의 invalid한 트랜잭션의 경우 reject되거나, 다음 phase 로 넘어가지 않는 일은 발생하지 않는다.

Scalable BFT-consensus with Omnicon

Omniledger는 ByzCoin이라는 비잔티움 합의 구조를 사용한다. 이는 PBFT를 기반으로 확장성을 고려한 집약적 서명(collective signing, CoSi) 방법으로, 기존의 all-to-all 방식으로 검증 그룹이 커뮤니케이션했던 방식을 개선하였다.

검증상황에서 랜덤으로 선정된 리더가 트리형태의 검증 그룹을 생성하고, 하위 노드의 마이너들에게 검증을 요청한다. 이때 PBFT 를 사용하게 되고, 기존의 all-to-all 방식이 N개의 노드에 대하여 N번의 커뮤니케이션이 일어나야 한다면, ByzCoin의 경우 트리구조이므로 N*log(N) 만큼의 커뮤니케이션만 하면 되므로 기존의 방식에 비하여 신속한 합의가 가능하다.

Low latency Transactions

트랜잭션의 처리속도는 해당 트랜잭션이 검증되는 시간에 따라 달라진다. 따라서, OmniLedger는 트랜잭션 처리의 경량화를 위해 “Trust but Verify” 모델을 지원한다. 이는 검증자를 낙관적 검증자(Optimistic validator)와 핵심 검증자(Core validator)로 나눈다.

낙관적 검증자는 low-value (저가) 의 트랜잭션의 경우 검증 절차를 복잡하게 거치지 않고 바로 블록에 포함시킨다. 그리고 이렇게 생성된 블록에 대하여 핵심 검증자가 정확하게 검증하여 Finalize를 제공한다.

이는 결과적으로, 일부 잘못된 거래가 생길 수 있지만, 궁극적으로 핵심 검증자가 다시 검증하기 때문에 안전하고, 잘못된 거래에 대한 벌금 등으로 피해 보상책을 마려할 수 있다.

Ledger Pruning

새로운 검증자가 추가될 때 각 검증자들이 모든 블록체인을 다운로드하는 것은 굉장히 어려운 일이다. 실제로 Visa와 같은 거래 시스템의 경우 약 4000tps를 제공하는데, 이는 하루에 약 150GB 정도의 트랜잭션을 만들어낸다.

따라서, Ledger pruning 을 통해 일정 epoch(주기)마다 finalize가 보장된 블록에 대하여 체크포인트를 부여하고, 해당 블록을 다음 epoch의 genesis block으로 하게 한다.

마치며

블록체인의 확산이 진행되면서 확장성의 문제는 여전하다. 여러 해결책이 제시되고 있지만 아직은 합의 알고리즘 단계에서 해결하는 것으로 머물고 있고 대부분 대표자 선출을 하므로 탈 중앙화에 어긋난다고 볼 수 있다. 샤딩의 경우 블록체인 네트워크의 형태를 변화하는 방법이므로 이러한 탈중앙화 문제를 해결하며 확장성을 높일 수 있는 방법이라 생각한다.

본 글에서는 비트코인 기반 블록체인에서의 샤딩에 대하여 다루었다. 그러나 스마트 컨트랙트가 포함된 이더리움 기반 블록체인의 경우 현재 샤딩을 구현중이지만 어려운 단계이다. 이더리움 재단에서는 Ethereum 2.0 에서 샤딩이 구현된 블록체인을 내놓을 것이라고 한다.