[Tech Report]공정한 합의 알고리즘, deb 합의 알고리즘
상태바
[Tech Report]공정한 합의 알고리즘, deb 합의 알고리즘
  • 이승윤 기자
  • 승인 2018.09.04 10:28
  • 댓글 0
이 기사를 공유합니다

지속가능한 탈중앙화 추구하는 블록체인 기술

지난 8월 6일 박성준 동국대학교 국제정보보호대학원 블록체인연구센터 센터장은 기존의 퍼블릭 블록체인(Public Blockchain)들이 갖고 있는 중앙화 문제를 해결한 지속 가능한 탈중앙화 P2P 합의 알고리즘인 ‘deb 합의 알고리즘(이하’deb’)’을 발표했다. 페어넥스트 이더리움(Fair Next Etherium)을 핵심으로 하는 ‘deb’은 누구든 채굴이 가능한 공정함을 무기로 퍼블릭 블록체인의 대명사인 이더리움을 능가하는 것을 목표로 하고 있다. 박교수가 발표한 지속가능한 탈중앙화 합의 알고리즘인 ‘deb 합의 알고리즘’의 특징을 살펴보자.

2008년 분산원장(Distributed ledger) 개념과 합의 알고리즘인 작업증명(PoW: Proof of Work)을 사용하여 사토시 나까모도가 탈중앙화된(Decentralized) P2P 암호화폐 시스템인 비트코인(Bitcoin)을 개발하였다. 이후, 2014년 비탈릭 부테린(Vitalik Buterin)은 비트코인의 한계를 극복한 “글로벌 신뢰컴퓨터(A trust world computer)”인 이더리움(Ethereum)을 개발했다.

블록체인(Blockchain)의 가장 중요한 핵심 기술은 상호 신뢰하지 않는 노드(Node)들 간의 합의(Consensus) 알고리즘이다. 비트코인과 이더리움 모두 합의 알고리즘으로 작업증명 방식을 사용한다. 그러나 작업증명 방식을 사용하는 합의 알고리즘의 경우 노드가 보유한 컴퓨팅 파워(Computing power)에 의해 채굴(Mining) 확률이 결정된다. 이러한 특성으로 인해 블록체인이 추구하고자 하는 탈중앙화 특성이 약화되는 단점을 가지고 되고, 비트코인의 중앙화 문제가 현실적으로 대두되고 있다.

또한 이러한 연유로 이더리움은 현재 합의 알고리즘을 작업증명에서 지분증명(PoS: Proof of Satake)방식으로 전환하고 있는 실정이다. 그러나 지분증명 방식의 경우에도 노드들의 보유한 지분에 의한 탈중앙화 특성이 지속가능한지에 대한 원천적인 질문을 던지고 있다. 지분증명 방식에 대해 자본주의 문제점을 원천적으로 가지게 될 것이라는 논쟁도 이러한 이유에서 출발한다.

공정성 극대화한 ‘앤드어스’ 블록체인 제안할 예정

우리는 먼저 블록체인의 핵심 원천기술인 합의 알고리즘에 대한탈중앙화 특성을 공정성(fairness) 개념으로 정의하여 설명하자면, 공정성은 채굴을 원하는 노드들의 조건(컴퓨팅 파워, 보유 지분 등)에 따른 채굴 확률의 비례성을 의미한다.

deb 합의 알고리즘은 이런 공정성을 극대화한 것으로, 향후 이를 기반으로 지속가능한 탈중앙화 특성이 유지되는 퍼블릭 블록체인인 '앤드어스(AndUs)' 블록체인을 제안할 예정이다.

앤드어스 블록체인은 기본적으로 이더리움에 기반한다. 즉, 앤드어스 블록체인은 이더리움의 구조를 유지하면서, 지속가능한 탈중앙화를 유지하고 속도를 대폭 향상시킨 퍼블릭 블록체인이다. 이더리움에 기반한 이유는 이더리움이 블록체인의 근본 취지에 가장 가까운 철학을 유지하고 있으며, 특히, 이더리움의 기본 목적인 탈중앙화 P2P 비즈니스 생태계(Ecosystem)를 창출하는 인프라로서의 역할이 가장 중요하고 본질적인 블록체인의 철학이기 때문이다.

한편으로는 deb 합의 알고리즘과 기존의 퍼블릭 블록체인에서 사용하는 작업증명이나 지분증명 방식과의 차별성으로 채굴과 암호화폐(Cryptocurrency) 발행과의 연관성이 있다. 기존의 합의 알고리즘들은 노드의 채굴 참여를 지속적으로 유지하기 위하여 채굴에 성공한 노드들에게 보상으로 암호화폐 발행 권한을 주는 방식을 취하고 있다.

그러나 deb 합의 알고리즘의 경우, 채굴과 암호화폐 발행과는 연관성이 없다. 즉, 채굴과 암호화폐 발행이 상호 무관한 퍼블릭 블록체인을 개발하기 위한 합의 알고리즘이다. 채굴자들에게 필요한 보상금을 암호화폐 발행 권한으로 주는 것이 아닌, 채굴에 참여하고자 하는 노드로 구성될 유료 채굴리그의 참가비의 일부와 거래수수료로 보상해주는 방식이다.

이렇게 구성해야 하는 본질적인 이유는 지속가능한 탈중앙화를 위해, 노드들의 채굴 조건과 무관하게 만드는 것과도 연계 된다. 즉, 채굴작업의 공정성을 확보하기 위하여 채굴과정이 모든 노드들에게 공정할 수 있도록 매우 저비용이기 때문에 고액의 보상체계가 필요하지 않다는 것이다.

특히, deb 합의 알고리즘의 경우 기존의 퍼블릭 블록체인과는 달리 포크(Fork)가 발생하지 않는 장점 또한 지니고 있다. 이는 블록 생성이 바로 블록의 최종성(Finality)을 보장하기 때문이다.

합의 알고리즘의 공정성

deb 합의 알고리즘의 목적은 채굴을 원하는 노드들의 조건(컴퓨팅파워, 보유 지분 등)과 상관 없이 모든 노드들에게 공정한 채굴 확률을 보장함으로서 지속가능한 탈중앙화 특성을 유지하는 것이다. 이를 위해 먼저 합의 알고리즘의 공정성(fairness)을 정의하고 기존 퍼블릭 블록체인들의 공정성을 분석해야 한다.

합의 알고리즘의 공정성이란 노드들의 채굴 확률과 노드들이 가지고 있는 조건(컴퓨팅 파워, 지분 등)들과의 상관 관계로 정의 한다. 예를 들어 비트코인과 이더리움에서 사용하는 작업증명 방식의 경우, 노드들의 채굴 확률은 노드가 보유한 컴퓨팅파워에 위해 결정된다.

작업증명 방식을 채택하고 있는 비트코인의 경우, 채굴공장이나 그룹의 탄생 등에 따라 일반적인 노드가 채굴에 성공할 확률은 거의0에 가깝다. 이로 인해 비트코인은 중앙화되고 있다는 논쟁이 일고 있다. 그리고 이더리움에서 사용하게 될 지분증명 방식의 경우, 노드들의 채굴 확률은 노드가 보유한 지분에 의해 결정된다.

지분증명 방식의 경우는 보유지분에 따른 채굴 확률이 결정됨으로 전형적인 자본의 논리가 적용된다는 문제점이 지적되고 있는 실정이다.

deb 합의 알고리즘의 특징

기존의 작업증명 및 지분증명 합의 알고리즘의 경우 채굴 노드가 가지고 있는 컴퓨팅 파워와 보유한 지분에 따라 채굴 노드의 채굴확률이 비례하는 특성을 가지고 있으며, 이는 채굴 관점에서 블록체인에 참여를 원하는 채굴자들에게 공정하지 않다는 것을 말해주고 있다.

deb 합의 알고리즘은 바로 문제를 해결하고 공정한 채굴 기회를보장하기 위한 합의 알고리즘이다. 먼저 공정한 채굴 기회를 보장하기 위해서는 채굴을 원하는 모든 노드들에게 주어진 조건(컴퓨팅파워, 보유 지분 등)에 상관 없이 공정한 채굴 기회를 주어야 한다. 이를 위해 deb 합의 알고리즘은 작업증명과 지분증명 방식과는 달리 공정한 노드(Fair node)라는 개념을 도입했다. 물론 P2P 기반의 deb 합의 알고리즘의 특성을 유지하기 위해 공정한 노드의 신뢰성

을 가정하지는 않는다. 즉, 공정한 노드는 제3의 신뢰기관(TTP:Trusted Third Party)은 아닌, 단지 P2P 네트워크의 노들들과 협력하여 합의 알고리즘을 지원하는 특별한 노드라고 생각하면 된다.

deb 합의 알고리즘은 유료 채굴 리그, 최대 난수 규칙(MRNR:Maximum Random Number Rule, 가장 큰 랜덤 넘버)과 다수결 원칙 등 3가지 기본 원리로 작동된다. 유료 채굴 리그란 채굴을 원하는 노드들 중 특정 수(예, 100명)의 노드들로 구성된 채굴 노드의 그룹이다. 물론 채굴 리그에 참여를 원하는 노드들은 채굴 리그에 참여하기 위해 현실적으로 충분히 가능한 적은 금액(예, 100원)인 참가비를 지불해야 한다. 그리고 유료 채굴 리그에 참여한 노드로 구성된 그룹에서 각 노드가 블록을 생성하는 규칙이 최대 난수 규칙이다. 그리고 최종 채굴자를 결정하는 방식, 즉 최종 블록을 결정하는 방식은 공정한 노드와 채굴리그에 참여한 노드들간의 협력을 통한 다수결 원칙으로 이루어진다.

deb 합의 알고리즘의 전체 구성도는 [그림 1]과 같다.

[그림 1] deb 합의 알고리즘의 전체 구성 개념

3단계로 구성되는 deb 합의 알고리즘

deb 합의 알고리즘의 전체 프로세스는 유료 채굴리그 구성, 블록 생성(채굴), 최종 블록 합의 등 크게 3단계로 구성된다.

▲ 유료 채굴리그 구성

① 공정한 노드는 채굴리그 구성을 위해 모든 노드들에게 OTPRN 을 배포한다.

② 채굴리그에 참여를 희망하는 노드는 공정한 노드가 배포한 OTPRN을 참조하여 본인이 채굴리그 참여 대상자인지를 판단한다.

③ 채굴리그 참여자로 선정된 채굴노드는 채굴리그 구성을 위해 OTPRN을 포함한 JoinTx를 생성한다.

④ 모든 노드들에게 JoinTx를 브로드캐스팅한다.

⑤ 채굴리그 참여자로 선정된 채굴노드들만 JoinTx를 참조한다.

▲ 블록 생성(채굴)

① 채굴리그에 참여한 채굴 노드는 최종 블록 선정의 기준이 되는 RAND를 생성한다. 채굴 확률을 동등하기 위해 채굴리그에 신청하였으나, 채굴자로 선정되지 못한 경우 선정되지 못한

경우만큼 복수의 RAND를 생성한다.

RAND = CSPRNG(OTPRN, Address, PreBlockHash)

② 채굴 노드는 블록 헤더에 RAND를 포함하여 블록을 생성한다.

③ 모든 노드에게 생성된 블록을 브로드캐스팅한다.

▲ 합의 알고리즘

블록 합의의 기본 원칙은 MRNR 규칙과 노드와 공정한 노드가 협

력하여 다수결에 의한 최종 블록 합의 절차이다.

① 노드는 RAND가 가장 큰 블록을 선택하여 공정한 노드에 전송

② 공정한 노드는 전송 받은 블록 중 다수결 원칙에 따라 가장 많은 블록을 최종 블록으로 결정하여 서명한 후 노드들에게 전송

③ 채굴 노드는 자신이 생성한 블록과 공정한 노드가 보내준 블록과 비교하여 동일한 블록의 경우만 전체 노드에 브로딩캐스팅.

④ 각 노드들은 자신이 받은 블록 중 다수결에 의해 최종 블록으로 인지하고 블록체인에 추가

유료 채굴 리그 구성 세부 프로세스

안전성과 효율성을 위해 유료 채굴리그를 구성하는 방법은 공정한 노드와 노드들의 자체적인 인원 조정과 채굴리그 참여 신청으로 진행된다.

▲유료 채굴리그 참여자 선정

① 공정한 노드는 블록 생성 주기에 따라 OTPRN 구조체를 모든 노드에게 배포

※ OTPRN 구조체(i는 OTPRN 발행 번호)

② 채굴 후보 노드들은 공정한 노드가 배포한 OTPRN 구조체를 참조하여 자신이 참가할 수 있는지 파악

(가) 최대 채굴 참여 인원수를 정의한 시스템 설정 변수 ‘MMiners’를 제수로 설정

(나) 채굴 노드는 공정한 노드가 전파한 OTPRN 구조체 중 채굴 의사를 밝힌 전체 채굴 노드 수를 나타내는 C“Miners”를 피제수로 설정

(다) 두 값을 연산하여 얻은 몫을 Div로 설정 Div = CMiners ÷MMiners

(라) 트랜잭션 구조체의 Join_Nonce(Tx ·Join_Nonce )와 채굴 노드의 주소 일부 값을 더하여 Div와 모듈러 연산

Tx ·Join_Nonce +The Last 1 Byte of Address )%Div =0 → 가능

※ Tx·Join_Nonce: 채굴노드가 채굴리그에 참가할 때마다 증가하는 값으로, 채굴리그를 구성함에 있어 공정한 노드가 채굴리그 구성원을 조작하기 어렵게 하고 채굴노드가 사전에 조작하기 어려운 값을 설정함으로써 부당하게 채굴리그에 참여하는 것을 방지하기 위한 값

※ The Last 1 Byte of Address: Tx ·Join_Nonce 가 고르게 분포되어 있지 않을 경우 채굴리그 참여자 인원수 조정이 동작하지 않기 때문에 사용되는 보조 값

▲ 유료 채굴 리그 구성

① 채굴리그에 참가 가능한 채굴노드는 OTPRN 구조체를 포함한 ‘JoinTx ’를 생성하여 모든 노드들에게 브로드캐스팅 함 (JoinTx : 노드가 채굴리그에 참여하고자 할 때 발생시키는 채굴리그 참여 신청 트랜잭션)

아래의 필드를 제외하고 이더리움 트랜잭션과 동일

② 채굴리그에 참여한 채굴노드들만 JoinTx 를 수집

③ 채굴노드는 수집한 JoinTx 를 목록화하여 각자의 채굴리그를 구성 블록 생성 프로세스 : 채굴 프로세스 공정하고 효율적인 채굴을 위해 공정한 노드와 의사난수(RAND)를 활용한다.

▲ RAND 생성

① 채굴 노드는 참여자 선정 과정에서 공정한 노드로부터 받은

OTPRN 구조체를 참조하여 RAND 생성

RAND = {0≤n ≤Tx ·Join_Nonce | CSPRNG (n , OTPRNi , Address , P_BlockHash ) }

※ Tx ·Join_Nonce : Tx ·Join_Nonce 의 다른 목적으로, 채굴노드가 채굴리그에 참여한 만큼 채굴 확률을 높여주는 기능을 수행함. 이와 같은 목적을 달성하기 위해 수만큼 다른 RAND를 생성할 수 있고 그 중 가장 큰 값을 블록 생성에 사용할 수 있음.

※ OTPRNi : 공정한 노드가 배포한 일회성 의사난수로 채굴노드가 RAND를 생성함에 있어 채굴에 유리한 값을 생성할 수 없도록 함

※ Address : 채굴노드가 채굴할 때 사용하는 주소로 채굴노드별로 RAND를 다르게 생성하게 하기 위함

※ P_BlockHash : 이전 블록의 해시 값으로 공정한 노드가 특정 채굴노드에게 유리한 OTPRNi를 배포할 때를 대비하고 채굴 노드가 특정 블록에 종속된 하나의 RAND를 생성하도록 하기 위함

② 채굴노드는 자신이 생성한 RAND 중 가장 큰 RAND를 선택

RAND =MA X( {RANDn }0≤n≤ Tx·Join_Nonce

 

▲ 블록 생성과 브로드캐스팅

① 채굴노드는 블록이 올바르게 생성되었다는 것을 증명하기 위해

블록헤더에 OTPRN 구조체를 포함함

※ 블록 구조체 (아래의 필드를 제외하고 이더리움 블록과 동일)

② “RAND 생성” 단계에서 생성한 RAND와 n을 블록헤더에 포함

③ 채굴노드가 수집한 각종 트랜잭션을 블록에 포함한 뒤 블록 생성

④ 채굴노드는 생성된 블록을 공정한 노드와 노드에게 브로드캐스팅함

합의 알고리즘

블록 합의의 기본 원칙은 공정한 노드가 자신에게 전송된 블록 중 다수결 원칙에 따라 최종 블록을 선정하고, 공정한 노드는 선정한 최종블록에 서명하여 노드들에게 배포한다. 각 노드들은 자신이 공정한 노드에게 보낸 블록과 공정한 노드가 서명한 최종 블록이 동일한 경우에만 최종 블록을 브로드캐스팅한다. 각 노드는 최종적으로 다수결 원칙에 의해 최종 블록을 결정하고 체인에 연결한다.

▲ 유효성 검증 단계

① 블록을 구성하고 있는 모든 필드들의 유효성을 검증함

※ 프로그래밍 관점 : 데이터 타입, 입력 값 범위 등

② OTPRN 전파 주기와 블록 생성 주기가 일치한지 확인

③ OTPRN 무결성 및 공정한 노드의 서명 검증

④ 채굴한 노드가 채굴리그 참가 가능 대상자인지 확인

⑤ 채굴노드가 채굴리그 참가비를 지불할 수 있는 지 확인

⑥ RAND가 올바르게 생성되었는지 확인

▲ 블록 합의

① 노드는 RAND가 가장 큰 블록을 선택하여 공정한 노드에 전송

② 공정한 노드는 전송 받은 블록 중 다수결 원칙에 따라 가장 많은 블록을 최종 블록으로 결정하여 서명한 후 노드들에게 전송함

③ 채굴 노드는 자신이 생성한 블록과 공정한 노드가 보내준 블록과 비교하여 동일한 블록의 경우만 전체 노드에 브로딩캐스팅.

④ 각 노드들은 자신이 받은 블록 중 다수결에 의해 최종 블록으로 인지하고 블록체인에 추가

⑤ 채굴자 인센티브 제공

인센티브 = 트랜잭션 수수료 + 채굴리그 참가자 전체 참가비의 일부

⑥ 채굴리그 참가자 채굴 확률 조정

- 채굴 성공 노드 : Tx ·Join_Nonce = 0

- 채굴 실패 노드 : Tx ·Join_Nonce = Tx ·Join_Nonce + 1

공정한 노드의 역할과 신뢰성 문제

비트코인과 이더리움의 합의 알고리즘은 공정한 노드 개념을 사용하지 않는다. 그러나 deb 합의 알고리즘의 경우 지속가능한 탈중앙화 특성을 유지하기 위해 공정한 노드 개념을 도입했다. 물론 deb 합의 알고리즘이 동작하기 위해서 공정한 노드의 신뢰성을 가정하지 않는다.

공정한 노드는 유료 채굴리그 구성의 효율성과 블록 합의, 최종성 협력을 위한 역할만을 담당한다.

▲ 공정한 노드의 역할

① 유료 채굴리그 참여자의 랜덤한 선정

② 노드들과의 상호 견제를 통한 최종 블록 합의 협력

가장 중요한 것은 deb 합의 알고리즘은 공정한 노드의 신뢰성에 의존하지 않는다. 공정한 노드와 블록체인 노드들간의 상호 견제를통해 공정한 노드의 신뢰성 보장 없이도 블록체인의 안전성을 확보 할 수 있다.

유료 채굴 리그의 구성에 따라 동적으로 결정되는 성능

deb 합의 알고리즘의 성능은 유료 채굴리그 구성 수와 블록생성주기 등에 따라 동적으로 결정될 수 있다. 예를 들어, 채굴 리그 인원 수 100명인 경우 예상되는 성능은 [표 1]과 같다.

[표 1] deb 합의 알고리즘의 성능

특히, 블록 생성 시간을 줄이기 위해 공정한 노드와 유료 채굴 리그 노드들 간의 네트워크 접속부하를 줄이면 블록 생성 시간을 더욱단축할 수 있다. 일례로 한번 구성된 유료 채굴 리그의 블록 생성

숫자를 10개로 한다면 블록 생성 시간은 10초 이내로 단축할 수 있을 것이다.

deb 합의 알고리즘 특징

deb 합의 알고리즘의 목적은 현재의 합의 알고리즘의 불공정성으로 인해 발생할 수 있는 블록체인 합의 알고리즘의 중앙화 문제를 해결하는 것이다. 또한 기존의 퍼블릭 블록체인의 합의 알고리즘의 경우 블록을 생성하는 채굴과 암호화폐 발행이 연계되어 있으나, deb 합의 알고리즘의 경우 채굴과 암호화폐 발행이 무관하다는 것이다. 즉, 초기 발행한 암호화폐 발행량이 바로 총 통화량이 된다는 것을 의미한다.

이는 암호화폐 발행 권한을 독점하면서도 퍼블릭 블록체인을 구성할 수 있게 하는 합의 알고리즘이다. 또한 deb 합의 알고리즘은 포크가 일어나지 않아 최종성이 1블록이면 달성되는 장점이 있다.

deb 합의 알고리즘의 주요 특징은 다음과 같다.

① 지속가능한 탈중앙화 특성 유지(공정성)

② 채굴과 암호화폐 발행 무관(암호화폐 발행 독점 가능)

③ 포크 없는 1블록의 최종성 보증

④ 1,000 TPS 이상의 고속 성능

지속가능한 탈중앙화 위한 핵심 원천기술

deb 합의 알고리즘은 기존의 합의알고리즘인 작업증명이나 지분증명 방식의 특성(노드들의 조건)으로 인한 중앙화 문제를 해결한 합의 알고리즘이다. 이는 블록체인의 원래 목적인 지속가능한 탈중앙화를 달성할 수 있는 핵심적인 개념이다.

또한, 퍼블릭 블록체인이 작동하기 위한 보상체계로 새로운 암호화폐 발행과 연계하지 않는 특징을 갖고 있다. 이는 채굴자의 채굴 비용을 최소화함으로서 지속가능한 탈중앙화 특성과 연계되어 있다.

특히, deb 합의 알고리즘은 현재까지 제안된 퍼블릭 블록체인 중 지속가능한 탈중앙화를 유지하면서도 성능이 우수한 퍼블릭 블록체인인 앤드어스 블록체인(AndUs blockchain)을 실현할 수 있게 하는 핵심 원천기술이다.

글 동국대학교 박성준 블록체인연구센터장



댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
0 / 400
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.