DAG(유향 비순환 그래프)에 대해
[목차]
1. 개요
2. DAG의 구조를 이해하기
3. DAG의 장점과 단점
4. 정리
1. 개요
이 리포트에서는 DAG(Directed Acyclic Graph, 유향 비순환 그래프)에 대해서 알아봅시다. DAG를 이용하는 프로젝트로는 IOTA, Byteball, Hedera Hashgraph, Avalanche등이 있습니다. 블록체인에 다앙한 타입들이 있듯이, DAG에도 다양한 아키텍쳐가 있기 때문에 과도한 일반화는 하지 말아야 하지만, 여기서는 블록체의 차이에 주목하면서 낮아졌습니다.
DAG는 블록체인보다 새로운 구조이며, 어느정도 보안이 확보되어 있는지에 대해서는 알려지지 않았습니다. 또한 비트코인(Bitcoin)과 이더리움(Ethereum)처럼 Permissionless(비인가형 전체가 네트워크 운영측면으로 참여가능)인 DAG는 아직 실현되지 않은 것이고 공공등에서 실행되고 있는 Byteball과 Hashgraph도 실제로는 Permissionless로 부르기 어려운게 현실입니다.
2. DAG이 구조를 이해하기
이미지 출처: https://obyte.org/Byteball.pdf
DAG는 블록체인 기반으로 생각하면 이해가 잘 안되기 때문에 목표와 이를 위한 구조에 대해서 고민해 보고자 합니다.
이중지급 방지
비트코인(Bitcoin)은 Permissionless(모두 네트워크의 운영쪽에 참여)이면서 BTC의 이중지급을 방지할 수 있다는 장점이 있습니다. 블록체인의 경우, 거래내용이 확인된 블록에 저장됩니다. 보낸 사람의 잔액(UTXO 및 계정잔액)을 확인 후, 각 트랜잭션이 채굴자(마이너)와 검사기에 의해 확인되기 때문에 이중지불이 방지됩니다. (물론 실제로 공격방법이 있어 성공한 사례가 존재합니다) 또한, 블록생성을 위해서는 PoW는 블록 생성 전에 비용으로 인해 공격이 실패할 경우, 마이닝(채굴)비용이 낭비되고, PoS는 보증금이 몰수될 가능성이 있습니다.
Byteball의 경우는 블록없이 복수의 트랜잭션을 처리할 경우, 각 거래별 잔고와 순서를 확인해야 합니다. 잔액 확인은 소지하고 있는 금액이 마이너스가 되는 트랜잭션을 방지하기 위함입니다. 각 트랜잭션 순서는 어떻게 정해지는 것인지는 Hashgraph와 비슷한 구조를 채용하고 있습니다.
위 그림은 단위라는 기록입니다. G는 Genesis unit이며 최초의 거래 기록을 보여줍니다. 시간축은 왼쪽에서 오른쪽으로 흘러가고, 화살표와 반대방향인 것을 주의해야 합니다. 위 그림은 각 유닛의 순서를 정한 후, 결과를 보여줍니다.
결론부터 말하면, 유닛 순서는 다음과 같이 결정되며, 이중 지급을 피합니다.
- 기준이 되는 하나의 메인 체인(굵게 표시된 원)을 결정함
- 메인 체인의 참조관계를 축으로 G->1->2순서로 번호를 붙임
- 메인 체인의 숫자N이 참조하는 부모노드 숫자도 N임
메인체인의 결정 방법은 나중에 설명합니다. (메인체인으로 표기되어 있지만, 기본 경로로 변경되면 더 혼란이 적습니다. 이 리포트에서는 백서에 표기된 메인 체인 표기로 통일합니다.)
또한, 다음 규칙이 있습니다.
- 직관적인 참조관계에 있는 경우에는 피참조유닛(상위유닛)가 참조유닛(하위유닛)보다 우선 처리됨
- 참조관계가 없는 기기는 주어진 숫자가 작은 순서대로 처리됨
- 숫자가 같은 경우, 해시값이 나은 유닛이 우선 처리됨
DAG에 대한 정보는 위 그럼처럼 설명되는 경우가 많기 때문에 여러 트랜잭션이 동시에 처리되는 느낌이지만, 이런 절차로 되는 것으로 각각의 유닛번호 및 해쉬값으로 우선 순위를 줄 수 있어, 각각의 유닛을 순차적으로 처리할 수 있습니다.
메인 체인의 선택
각 유닛은 비참조유닛(상위유닛)을 선택해야 한다는 규칙이 있습니다. 그림처럼 여러 유닛을 볼 수 있습니다. 그러나, 메인체인을 형성하기 위해 각 유닛이 상위유닛 중에서 최고의 상위유닛을 선택하도록 요구됩니다.
1) 하위유닛이 상위유닛에서 최고의 상위를 선택함
2) 최고의 상위도 자신의 최고의 상위를 선택하기 때문에, 최고의 상위 제외
3) 위로 거슬러 올라가면 Genesis unit에 도달
이런 형태로 메인체인을 만들수 있습니다. 그러나 최상의 상위는 어떻게 각 유닛에 선정되는 것일까요? 이에 대해서는 Byteball의 Witness라는 주체를 이해야 합니다.
Witness는 한마디로 소문난 사용자입니다. 각 사용자는 자신의 자갑에서 자신이 선택한 Witness를 미리 설정해두고 있습니다. 당연히, 다른 사용자는 다른 Witness를 선택합니다. 그러나, 이는 Stellar의 Quorum slice라는 구조가 비슷합니다. Witness도 Quorum slice도 네트워크 실행의 핵심이라고 할 수 있는 기능이지만, 이 부분의 분산은 상당히 어렵고, 여기에 병목화가 되고 분산화 및 공용화가 낮아집니다.
메인체인으로 다시 돌리면, Witness는 총 12개입니다.
1) 유닛을 거슬러가면, Witness가 만든 유닛이 있으면 카운트를 +1이 됨(같은 Witness가 여러개 나타난 경우 카운트를 +1하지 않음)
2) 카운트가 Witness의 과반수에 이르는 시점에서 업데이트 중단
3) 이 시점에서 Genesus unit까지의 거리 측정
4) 해당 거리가 가장 긴(=현재 위치와의 거리가 짧은 것)을 메인체인으로 함
5) 그 메인체인을 형성하면 상위 유닛을 최상의 상위로 정의함
이렇게 메인체인이 결정됩니다.
3. DAG의 장점과 단점
DAG(유향 비순환 그래프)는 확장의 맥락에서 주목받고 있지만, Byteball이든 Hashgraph든 공공 블록체인은 보안과 트러스트레스와는 전혀 다르기 때문에, 단순한 TPS에서 비트코인(Bitcoin)과 이더리움(Ethereum)을 비교하는 것은 불가능합니다.
꼭 비교하겠다면, 컨소시엄 체인이지만, 컨소시엄 체인은 주로 기업에서 사용되므로, 안전성 테스트가 요구되고 더 위험한 DAG를 사용하려면, 컨소시엄 체인에는 없는 장점을 제공해야 합니다.
이처럼, Byteball에는 Witness의 선택 문제가 있어, Hashgraph는 당분간 Permissioned운영이 이루어집니다. 일반적으로 확장하는 것은 공개체인 기준에서 거론되는 것이 많기 때문에, 원래 공개체인이 아니라고 하면, 확장은 첫번째가 아닙니다.
4. 정리
이 리포트에서 DAG는 블록체인보다 더 새로운 방법이며, 앞으로도 개발이 계속발전하는 영역이라고 생각됩니다. 현재 공개하는 것이 조건입니다. 비트코인형 화폐와 이더리움형 DeFi을 사실상 컨소시엄 체인인 DAG에 만드는 장점은 적다고 보지만, Avalanche등 새로운 상냥도 제안되고 있으며, 앞으로 주목해야할 분야라고 봅니다.
