Deb 합의 알고리즘

Deb 합의 알고리즘의 전체 구성도

Deb 합의 알고리즘은 공정성을 핵심 가치로 둔 방식으로, 채굴을 원하는 노드는 조건 없이 채굴에 참여할 수 있게 하는 방식의 합의 알고리즘이다. 채굴에 참여한 채굴 노드들은 채굴 기회를 균등하게 얻을 수 있다.

개요

기존의 작업증명(PoW) 및 지분증명(PoS) 합의 알고리즘의 경우 채굴노드가 가지고 있는 컴퓨팅파워와 보유한 지분에 따라 채굴 노드의 채굴 확률이 비례하는 특성을 가지고 있으며, 이는 채굴 관점에서 블록체인에 참여를 원하는 채굴자들에게 공정하지 않다는 것을 의미한다. deb 합의 알고리즘은 바로 이러한 공정하지 못한 문제점을 해결하여 공정한 채굴 기회를 보장하기 위한 합의 알고리즘이다. 먼저 공정한 채굴 기회를 보장하기 위해서는 채굴을 원하는 모든 노드들에게 주어진 조건에 상관없이 공정한 채굴 기회를 주어야 한다.

이를 위해 deb 합의 알고리즘은 작업증명과 지분증명 방식과는 달리 공정한 노드라는 개념을 도입했다. 물론 P2P 기반의 deb 합의 알고리즘의 특성을 유지하기 위해 공정한 노드의 신뢰성을 가정하지는 않는다. 즉, 공정한 노드는 제3의 신뢰 기간은 아닌, 단지 P2P 네트워크의 노드들과 협력하여 합의 알고리즘을 지원하는 단순한 특별한 노드라고 생각하면 된다.

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

등장배경

deb 합의 알고리즘의 목적은 채굴 균등성이며, 컴퓨팅 파워 또는 보유지분 등과 상관없이 모든 노드에게 고정한 채굴 확률을 보장하면서 지속 가능한 탈중앙화 특성을 유지하는 것이 주된 목적이다. 여느 합의 알고리즘과는 달리 deb 합의 알고리즘은 채굴과 암호화폐 발행이 상호 무관한 최초의 퍼블릭 블록체인(public blockchain)을 개발하기 위한 합의 알고리즘이다. 해당 시스템은 복권과 같은 시스템이라 참가한 노드 중 채굴에 성공한 사람만이 참가비 일부와 거래 수수료로 보상을 받을 수 있다.

이더리움(ethereum)기반의 블록체인으로서, 기존의 작업증명 합의 알고리즘의 단점을 개선하기 위하여 동국대 블록체인연구센터에서 연구한 deb 합의 알고리즘을 적용하여 성능과 사용자 편의성 및 마이닝의 공정성을 강화한 퍼블릭 블록체인 시스템으로, 동국대학교 블록체인연구센터 박성준 센터장이 창안한 퍼블릭 블록체인 합의 알고리즘으로 기존 퍼블릭 블록체인 합의 알고리즘들의 중앙화 특성 문제를 해결하여 지속가능한 탈중앙화 특성을 갖는 공정한 합의 알고리즘이다.

특징

전체 프로세스

deb 합의 알고리즘의 전체 프로세스는 유료 채굴리그 구성, 블록 생성(채굴), 최종블록 합의 등 크게 3단계로 구성된다. 첫 번째, 유료 채굴리그 구성으로 채굴을 원하는 노드는 공정한 노드에게 자신의 접속 정보를 제공하고, 공정한 노드는 채굴리그 구성을 위해 모든 노드들에게 OTPRN을 배포한다. 채굴리그에 참여를 희망하는 노드는 공정한 노드가 배포한 OTPRN을 참조하여, 본인이 채굴리그 참여 대상자인지를 판단한다. 채굴리그 참여자로 선정된 채굴 노드는 채굴리그 구성을 위해 OTPRN을 포함한 JoinTx를 생성한다. 그리고, 모든 노드들에게 JoinTx를 브로드 캐스팅하고, 채굴리그 참여자로 선정된 채굴 노드들만 JoinTx를 참조한다.

두 번째, 블록생성(채굴)이다. 채굴리그에 참여한 채굴 노드는 최종 블록 선정의 기준이 되는 채굴 난이도(difficulty)를 생성한다.

$difficulty={0\leq n\leq JoinNonce|MAX(CSPRNG(n,OTPRN.rand,coinbase,P_{B}lockHash))}$

채굴 확률을 균등하게 하기 위해 채굴리그에 신청하였으나, 채굴자로 선정되지 못한 경우 선정되지 못한 경우만큼 복수의 채굴 난이도를 생성한다. 채굴 노드는 블록 헤더에 채굴 난이도를 포함하여 블록을 생성하고, 모든 노드에게 생성된 블록을 브로드캐스팅한다.

세 번째, 합의 알고리즘이다. 블록 합의의 기본 원칙은 가장 큰 수, 가장 큰 랜덤 넘버(MRNR) 규칙과 노드와 공정한 노드가 협력하여 다수결에 의한 최종블록 합의 절차이다. 우선 노드는 자신이 수신한 블록 중 채굴 난이도가 가장 높은 블록을 선택한 뒤 서명하여 공정한 노드에 전송하고, 공정한 노드는 다수결 원칙에 따라 전송받은 블록 중 가장 많은 선택된 블록을 최종 블록으로 결정하여 서명한 후 노드들에게 전송한다. 채굴 노드는 공정한 노드로부터 수신한 블록이 다수에 의해 선택된 블록인지 검증한 뒤 전체 노드들에게 브로드캐스팅하며, 각 노드들은 공정한 노드와 다수가 서명한 블록을 최종 블록으로 인지하고 블록체인에 추가한다.

유료 채굴리그 구성

enodeCoinbase 구조체
필드 명	설 명
enode	채굴 노드의 enode 값
Coinbase	채굴에 참여할 계정의 주소
port	공정한 노드와 통신할 포트 번호
transOTPRN 구조체
필드 명	설 명
OTPRN	채굴 노드들이 채굴시 참조하는 구조체
Sig	OTPRN에 대한 공정한 노드의 서명
OTPRN 구조체
필드 명	설 명
num	OTPRN 발행 번호
rand	공정한 노드가 주기적으로 배포하는 일회성 의사 난수
CMiners	채굴을 수행하기 위해 공정한 노드와 연결을 유지하고 있는 노드의 수
Timestamp	공정한 노드의 로컬 시간
JoinTx 구조체
필드 명	설 명
Tx	아래의 필드를 제외하고 이더리움 트랜잭션 구조체와 동일 to : Fairnode's address data : Join Tx Data
JoinTxData 구조체
필드 명	설 명
JoinNonce	계정의 JoinNonce에 1을 더한 값
OtprnHash	공정한 노드로부터 수신한 OTPRN의 해시 값
FairNodeSig	transOTPRN.sig
Timetamp	채굴 노드의 로컬 시간
NextBlockNum	채굴할 블록의 번호

유료 채굴 리그 구성 세부 프로세스으로, 안전성 및 효율성을 위해 유료 채굴리그를 구성하는 방법은 공정한 노드와 노드들의 자체적인 인원 조정과 채굴리그 참여 신청으로 진행된다. 유료 채굴리그 참여자 선정 방법으로 채굴을 원하는 노드는 공정한 노드에게 노드 정보를 제공한다. 공정한 노드는 블록생성 주기에 따라 transOTPRN 구조체를 모든 노드에게 배포한다. 채굴 후보 노드들은 공정한 노드가 배포한 OTPRN 구조체를 참조하여 자신이 참가할 수 있는지 파악한다.

1. 최대 채굴 참여 인원수를 정의한 시스템 설정 변수 MMiners를 제수로 설정
2. 채굴 노드는 공정한 노드가 전파한 OTPRN 구조체 중 채굴 의사를 밝힌 전체 채굴 노드 수를 나타내는 CMiners를 피제수로 설정
3. 두 값을 연산하여 얻은 몫을 Div로 설정

   $Div=CMiners\div MMiners$

4. enodeCoinbase.coinbase와 OPTRN.rand의 XOR 연산의 합을 랜덤 함수의 시드(Seed)로 사용하여 랜덤 값 도출, RAND는 랜덤 함수

   $rand=RAND(\sum _{i=0}^{19}(enodeCoinbase.coinbase[i]\oplus OPTRN.rand[i]))$

5. rand를 div와 모듈러 연산하여 다음과 같은 조건이 충족될 때 채굴 참여가 가능하다고 판단

   $rand\%div==0$ → 가능

유료 채굴 리그의 구성으로 채굴리그에 참가 가능한 채굴 노드는 OTPRN 구조체를 포함한 JoinTx를 생성하여 모든 노드들에게 브로드 캐스팅한다. JoinTx는 노드가 채굴리그에 참여하고자 할 때 발생시키는 채굴리그 참여 신청 트랜잭션 한다. 채굴 리그에 참여한 채굴노드들만JoinTx를 목록화하여 각자의 채굴리그를 구성한다.

채굴 프로세스

공정하고 효율적인 채굴을 위해 공정한 노드와 의사 난수 난이도를 활용한다. 채굴 난이도를 생성하는 방법으로, 채굴 노드는 참여자 선정 과정에서 공정한 노드로부터 받은 OPTRN 구조체를 참조하여 채굴 난이도를 생성한다.

$difficulty={0\leq n\leq JoinNonce|MAX(CSPRNG(n,OTPRN.rand,coinbase,P_{B}lockHash))}$

JoinNonce는 다른 목적으로, 채굴 노드가 채굴리그에 참여한 만큼 채굴 확률을 높여주는 기능을 수행한다. 이와 같은 목적을 달성하기 위해 JoinNonce 수만큼 다른 채굴 난이도를 생성할 수 있고, 그중 가장 큰 값을 블록 생성에 사용할 수 있다. OPTRN.rand는 공정한 노드가 배포한 일회성 의사 난수로 채굴 노드가 난이도를 생성함에 있어 채굴에 유리한 값을 임의로 생성할 수 없도록 하고, coinbase는채굴노드가 채굴할 때 사용하는 주소로 채굴 노드별로 난이도를 다르게 생성하게 하기 위함이다. 또한, P_BlockHash는 이전 블록의 해시값으로 공정한 노드가 특정 채굴 노드에게 유리한 OPTRN.rand를 배포할 때를 대비하고, 체굴노드가 특정 블록에 종속된 하나의 난이도를 생성하도록 하기 위함이다. 채굴 노드는 자신이 생성한 난이도 중 가장 큰 난이도를 선택하여 트랜잭션을 생성한다.

$difficulty=NAX({difficulty_{n}}0\leq n\leq JoinNonce)$

다음은 블록생성 및 브로드 캐스팅이다. 채굴 노드는 자신의 블록 헤더에 OPTRN.rand와 기타 데이터를 참조하여 난수를 생성한 뒤 해당 난수와 자신의 JoinNonce를 블록 헤더에 기록한다. 블록 내에 존재하는 FairNodeSig와 Voters는 향후 공정한 노드에 의해 기록된다. 블록 구조체는 아래 필드를 제외하고 이더리움과 동일 하다.

블록 구조체

구분	필드 명	설 명
Header	UncleHash	제거
	JoinTxHash	JoinTx 리스트 해시 값
	GenTxHash	Tx 리스트 해시 값
	JoinReceiptHash	JoinTx의 receipt 해시 값
	GenReceiptHash	Tx의 receipt 해시 값
	Difficulty	채굴 노드가 공정한 노드로부터 수신한 OPTRN.rand을 활용하여 생성한 난수 값
	nonce	채굴노드의 JoinNonce 값
	FairNodeSig	공정한 노드가 다수의 채굴 노드들이 선택한 블록과 증명 데이터를 포함하여 서명한 값
	VoterHash	Voters 해시 값
Body	JoinTxs	Tx 목록
	GenTxs	JoinTx 목록
	Voters	해당 블록에 투표한 노드들의 주소와 서명(복수)

Voters 구조체

필드 명	설 명
addr	해당 블록에 투표한 채굴 노드의 주소
sig	채굴 노드의 서명
difficulty	채굴 노드 자신이 생성한 difficulty 값으로 향후 다수결에 의해 선택된 difficulty가 올바른지 검증할 때 사용

채굴 노드가 수집한 각종 트랜잭션을 블록에 포함한 뒤 블록 생성한다. 그 후, 채굴 노드는 생성된 블록을 다른 채굴 노드들에게 브로드캐스팅한다.

합의 방식

블록 합의는 기본적으로 블록선택과 다수결 원칙에 기반한다. 즉, 최초에 채굴 노드들끼리 각자 생성한 블록을 브로드캐스팅한 뒤, 자신에게 수신된 블록 중 가장 난이도가 지정된 블록을 선택한 뒤 서명하여 공정한 노드에게 전송한다. 공정한 노드는 자신이 수신한 블록 중 다수의 채굴 노드들이 선택한 블록을 선정하여 채굴 노드들의 주소와 서명을 블록 내에 포함시킨 뒤 자체 서명한다. 그리고 공정한 노드가 해당 블록을 채굴 노드들에게 전파하면 채굴 노드들은 해당 블록이 다수결 원칙에 부합하는지, 공정한 노드가 서명했는지 등을 검증한 뒤 원장에 추가한다. 이로써 해당 블록은 최종 블록으로 결정되고, 채굴 노드들은 해당 블록을 네트워크에 전파한다.

• 유효성 검증 단계

1. OTPRN 전파 주기와 블록 생성 주기가 일치하는지 확인한다
2. OTPRN 무결성 및 공정한 노드의 서명을 검증한다.
3. 채굴한 노드가 채굴 리그 참가 가능 대상자인지 확인한다.
4. 채굴 노드가 채굴 리그 참가비를 지불할 수 있는지 확인한다.
5. 채굴 난이도가 올바르게 생성되었는지 확인한다.

• 블록 합의

1. 채굴 노드는 수신한 블록 중 채굴 난이도가 가장 높은 블록을 선택하여 서명한 뒤 공정한 노드에 전송한다.
2. 공정한 노드는 전송받은 블록 중 다수결 원칙에 따라 다수에 의해 선택된 블록을 최종 블록으로 결정하여 서명한 후 노드들에게 전송한다. 향후 검증을 위해 공정한 노드는 해당 블록에 투표한 채굴 노드들의 주소와 서명을 블록에 포함시킨 뒤 서명한다.
3. 공정한 노드는 해당 블록을 채굴 노드들에게 브로드캐스팅한다. 채굴 노드들은 수신한 블록이 다수결 원칙에 부합하는지, 공정한 노드의 서명이 포함되었는지를 검증한 뒤 자신의 원장에 추가하고 해당 블록을 브로드캐스팅한다.
4. 마찬가지로, 위 블록을 수신한 일반 노드들(채굴에 참여하지 않은 노드들)도 채굴 노드들이 수행한 방식과 동일한 검증 절차를 거친 뒤 해당 블록을 원장에 추가한다.
5. 채굴자는 아래와 같이 인센티브를 제공받는다. (인센티브 = 트랜잭션 수수료 + 채굴리그 참가자 전체 참가비)
6. 채굴리그 참가자들의 채굴 확률을 조정한다.

공정한 노드의 역할

비트코인 및 이더리움의 합의 알고리즘은 공정한 노드 개념을 사용하지 않는다. 그러나 deb 합의 알고리즘의 경우 지속가능한 탈중앙화 특성을 유지하기 위해 공정한 노드 개념을 도입하였다. 물론 deb 합의 알고리즘이 동작하기 위해서 공정한 노드의 신뢰성을 가정하지 않는다. 공정한 노드는 유료 채굴리그 구성의 효율성, 블록 합의 및 최종성 협력을 위한 역할만을 담당한다.

• 공정한 노드의 역할

1. 유료 채굴리그 참여자의 랜덤한 선정
2. 노드들과의 상호 견제를 통한 최종 블록 합의 협력

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

성능

	deb 합의 알고리즘
블록크기	4.5MB ~ 9MB
TPS	1000 TPS
생성주기	10초 ~ 1분

deb 합의 알고리즘의 성능은 유료 채굴리그 구성 수와 블록생성 주기 등에 따라 동적으로 결정될 수 있다. 예를 들어, 채굴 리그 인원수가 100명인 경우 예상되는 성능은 표와 같다. 특히, 블록 생성 시간을 줄이기 위해 공정한 노드와 유료 채굴 리그 노드들 간의 네트워크 접속 부하를 줄이면 블록 생성 시간을 더욱 단축할 수 있다. 일례로 한번 구성된 유료 채굴 리그의 블록 생성 숫자를 10개로 한다면 블록 생성 시간은 10초 이내로 단축할 수 있을 것이다.

장점

deb 합의 알고리즘의 목적은 현재의 합의 알고리즘의 불공정성으로 인해 발생할 수 있는 블록체인 합의 알고리즘의 중앙화 문제를 해결하는 것이다. 즉, 기존의 합의 알고리즘인 작업증명 방식, 지분증명 방식과 deb 합의 알고리즘의 가장 큰 차이점은 지속가능한 탈중앙화를 유지할 수 있다는 것이다. 이는 채굴을 원하는 노드들의 조건들에 의존하지 않는 공정한 합의 알고리즘이라는 것을 의미한다. 또한 기존의 퍼블릭 블록체인의 합의 알고리즘의 경우 블록을 생성하는 채굴과 암호화폐 발행이 연계되어 있으나, deb 합의 알고리즘의 경우 채굴과 암호화폐 발행이 무관하다는 것이다. 즉, 초기 발행한 암호화폐 발행량이 바로 총통화량이 된다는 것을 의미한다. 이는 암호화폐 발행 권한을 독점하면서도 퍼블릭 블록체인을 구성할 수 있게 하는 최초의 합의 알고리즘이다. 한편으로 deb 합의 알고리즘의 장점으로는 포크가 일어나지 않아 최종성이 1블록이면 달성되는 장점이 있다.

참고자료

• 이승윤 기자, 〈(Tech Report)공정한 합의 알고리즘, deb 합의 알고리즘〉, 《CCTV뉴스》, 2018-09-04
• 앤드어스체인 백서 - https://www.anduschain.io/githubData/%EC%95%A4%EB%93%9C%EC%96%B4%EC%8A%A4%EC%B2%B4%EC%9D%B8_%EB%B0%B1%EC%84%9Cver0.71.pdf
• 팔색조, 〈앤드어스체인/다온코인 daon 블록체인 비트코인〉, 《네이버 블로그》, 2019-09-04
• 아타클럽 백서 - http://www.ataclub.io/whitepaper/whitepaper_ATAclub(kr)_v0.8.1.pdf

같이 보기

• 앤드어스체인
• 정용협
• 박성준

이 Deb 합의 알고리즘 문서는 합의 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘 □■⊕, 암호 알고리즘, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 작업증명 경과시간증명(PoET) • 균형작업증명(ePoW) • 뻐꾸기 사이클 • 스펙터 • 온라인증명(PoO) • 유용한 작업증명(PoUW) • 이중작업증명(DPoW) • 작업증명(PoW) • 지연작업증명(DPoW) • 캐스퍼 알고리즘 • 프로그작업증명(ProgPoW) • 활동증명(PoA) 지분증명 담보지분증명(BPoS) • 리스지분증명(LPoS) • 무작위 지분증명(rPoS) • 복제증명(PoRep) • 시간소각 지분증명(ABPoS) • 우로보로스 지분증명(OPoS) • 유동지분증명(LPoS) • 익명지분증명 • 지분속도증명(PoSV) • 지분시간증명(PoST) • 지분작업증명(PoSW) • 지분증명(PoS) • 확률적 지분증명(SPoS) 위임지분증명 마스터노드 지분증명(MPoS) • 번앤언 위임지분증명(B&E DPoS) • 슈퍼노드 지분증명(SPoS) • 위임지분서비스증명(DPoSS) • 위임지분증명(DPoS) • 이중위임지분증명(DDPoS) • 인공지능 위임지분증명(AI DPoS) • 포뮬레이션증명(PoF) • 포크능력증명(PoF) • 하이퍼 위임지분증명(Hyper-DPoS) 비잔틴 장애 허용 간단한 비잔틴 장애 허용 • 경량 비잔틴 장애 허용(LBFT) • 라케시스 • 루프 장애 허용 • 미네르바 • 비잔틴 장애 허용(BFT) • 수정 연합 비잔틴 동의(mFBA) • 심센서스 • 아이작(ISAAC) • 연합 비잔틴 동의(FBA) • 우로보로스 비잔틴 장애 허용(OBFT) • 위임 프랙티컬 비잔틴 장애 허용(dPBFT) • 프랙티컬 비잔틴 장애 허용(PBFT) • 프랙티컬 비잔틴 장애 허용 플러스(PBFT+) • 텐더민트 비잔틴 장애 허용(TBFT) • 프리즘 기타 deb 합의 알고리즘 • 권위증명(PoA) • 기여도증명(PoD) • 네트워크증명(PoN) • 대역폭증명 • 두뇌증명(PoB) • 람다 합의 알고리즘 • 명성보증금증명 • 서비스증명(PoS) • 성능증명(PoP) • 소각증명(PoB) • 시공간증명(PoSt) • 시청증명(PoV) • 신뢰성증명(PoB) • 역사증명(PoH) • 오벨리스크 • 용량증명(PoC) • 저장증명(PoS) • 전문성증명(PoE) • 중요도증명(PoI) • 지지증명(PoS) • 참여증명(PoE) • 탄소감축증명(PoCR) • 트레이딩증명(PoT) • 흐름증명(PoF) 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반