DAG 알고리즘이란 무엇인가? DAG(Directed Acyclic Graph)는 과연 솔루션이 될 수 있을까?
안녕하세요, 암호화폐가 가져올 새로운 미래를 꿈꾸는 @Cryptodreamers 입니다.
언젠가는 꼭 다루고 싶었던 주제로 DAG(Directed Acyclic Graph) 알고리즘을 생각하고 있었는데, 그 동안 바쁜 일정으로 포스팅을 미루기만 했었네요. 큰 마음먹고 여유가 있는대로 바로 정리를 해버리고자 준비했습니다.
3세대 블록체인이라고도 불리는 DAG 알고리즘. 아직까지는 대중의 관심이 크게 없어 시장에서 큰 영향력을 끼치지 못하고 있는 상황이지만, 머지 않아 크게 그 이름을 떨쳐낼 것이라고 확신합니다. 언젠가는 시장의 주목을 크게 받고 부상할 수 있는 저력을 지닌 기술력입니다.
DAG알고리즘의 원리와 그 특성, 잠재적인 가능성과 DAG알고리즘이 적용된 코인들에 대해서 살펴보겠습니다.
DAG 알고리즘의 원리?
문제를 읽다보면, 멘사 회원들이나 풀 수 있을 것 같은 퀴즈라고 느끼실 수도 있습니다.
아래쪽의 그래프를 참고하시면 되니 넘어 가셔도 좋습니다.
그래프 알고리즘의 큰 범주에 DAG알고리즘이 있다고 생각하시면 됩니다.
순환 그래프란?
Example Question
현재 여러분께서 서있는 곳은 S입니다. 여러분께은 S에서 D로 가는 최단 경로를 구해야 합니다.
S는 A로 연결되어 있고, S에서 A로만 이동이 가능합니다.
A는 B로 연결되어 있고, A에서 B로만 이동이 가능합니다.
B는 C와 연결되어 있고, B에서 C로 이동 가능합니다.
B는 D와 연결되어 있고, B에서 D로 이동 가능합니다.
C는 A와 연결되어 있고, C에서 A로만 이동이 가능합니다.
이 상황을 간단한 그림으로 표현하면 다음과 같습니다.
이런 그래프를 Negative Graph라고 합니다. 그래프에서 볼 수 있듯, A-> B-> C->A 의 싸이클이 발생해서 계속적으로 반복될 수 있는 상황이 발생합니다(순환그래프의 특성). 이 경우에 처리에 있어서 두 가지 어려움이 생깁니다. 첫 번째는 오로지 긍정적인 위상(S,A,B,C,D 같은 위상)을 가져야 산출이 쉬워진다는 점, 두 번째는 A->B->C->A 같은 순환이 없어야 한다는 점입니다. 이런 어려움을 이겨내고 최단경로를 알아내기 위해 사용하는 방법으로 Dijkstra(다익스트라) 과 Bellman-Ford (벨만-포드) 알고리즘 등이 있습니다.
비순환 그래프란?
위의 그림은 앞서 설명드린 순환그래프와 큰 차이를 보이고 있습니다. 계속적으로 순환될 수 있는 구간이 없기 때문에, 순환그래프에서 발생하는 문제점들이 없다는 것이죠! 이를 위상정렬이라고 표현합니다(Topologically sorted). 이렇게 정렬이 되어있다면 몇몇 알고리즘을 통해서 문제를 손쉽게 해결할 수도 있습니다.
DAG(Directed Acyclic Graph)는 순환그래프가 아닌 비순환 그래프입니다. 즉, DAG알고리즘에서는 순환하는 싸이클이 존재하지 않고, 일방향성만 가진다는 것이죠.
비가역적 일방향성. 이 특성은 우리가 어디서 많이 보던 특징이 아닌가요?
그렇습니다. 비가역적 일방향성은 블록체인의 핵심적인 특성입니다.
결국 '알고리즘을 어떤 식으로 구현하는가'의 문제는 데이터들을 어떤 그릇에 담을 것인가 하는 문제이기 때문에, 일방향적인 블록체인이 아니라 다방향성의 비선순환적 그래프를 활용해도 된다는 것이죠. DAG알고리즘에서 활용하는 방식은 다음과 같습니다.
https://explorer.byteball.org/
DAG알고리즘을 활용하는 대표적인 바이트볼 코인. 바이트볼의 Explorer에 가보시면 실제로 지갑간에 전송된 거래가 기록되는 방식을 그래프로 볼 수 있습니다. (위 사진 역시 Explorer의 캡쳐 사진입니다)
DAG알고리즘을 더욱 더 난해하게 만드는 것은 이렇게 비순환적인 구조가 무작위로 생성되어 간다는 점입니다. 비트코인의 블록체인이 일방향적으로 블록이 형성되어 간다면, DAG알고리즘에서는 블록(유닛이라는 용어를 씁니다)들이 무작위의 형태를 갖고 비순환적으로 구성되어 갑니다.
블록체인에서는 직전의 블록의 거래기록을 온전히 가져와 이후에 생성되는 블록을 검증하게 되는데요, DAG알고리즘의 경우 하나의 유닛(블록)에서 여러개의 유닛(블록)의 검증을 하게 됩니다.
DAG 알고리즘의 특성
위에서 살펴보았던 DAG알고리즘의 몇 가지 특성으로 기존의 블록체인 알고리즘과는 차별화되는 DAG알고리즘의 장점이 발생하게 됩니다.
1) 높은 트랜잭션 처리 속도
DAG에서는 비트코인처럼 블록형성이라는 개념이 없습니다. 하나의 유닛(블록)이 이하의 다른 유닛(블록)을 검증하므로 트랜잭션의 처리속도가 기하급수적으로 빨라질 수 있습니다. 또, 비트코인처럼 하나의 블록이 생성된 이후에나 다른 블록이 생성될 수 있는 개념이 아니라, 시간의 제약없이 실시간으로, 병렬적으로 처리되기에 트랜잭션 처리가 빠를 수 밖에 없습니다.
2) 저렴한 수수료
비트코인의 높은 수수료는 블록체인 네트워크를 가동시키는 엔진, 채굴자들에 대한 보상으로서 존재하는 개념입니다. 트랜잭션이 늘어날 수록 채굴자들이 처리해야할 일은 많아지고, 그들의 힘은 커질 수 밖에 없었습니다. 자연스럽게 사용자들은 더 높은 수수료를 지불해야만 했죠. DAG알고리즘에서는 블록을 형성해주는 채굴자의 개념이 없습니다. 수수료가 거의 들지 않죠. 대표적으로 IOTA의 경우 DAG알고리즘을 채택하여 수수료가 0원에 가깝습니다.
3) 뛰어난 확장성
트랜잭션이 늘어날 수록 추후 생성되는 트랜잭션에 대해 검증을 해줄 수 있는 가능성이 늘어납니다. 네트워크의 가치가 사용자의 증가에 따라 기하급수적으로 늘어난다는 메칼프의 법칙(Metcalfe’s law)가 극명하게 드러나는 네트워크라 할 수 있습니다. 부가적인 예시로 설명을 붙이자면, DAG알고리즘을 활용하고 있는 바이트볼은 사용자수를 증가시키는 것을 1차적인 목표로 하고 있기에, 발행량의 대부분의 코인을 에어드롭으로 대중들에게 부여했습니다.
위의 특성들로 인하여 DAG알고리즘은 비트코인의 가장 큰 결함(?)이라 평가되는 스케일링의 문제를 해결 할 수 있습니다.
혁신 그 자체죠. 라이트닝 네트워크나 블록사이즈 증가를 위해 혈투를 벌이지 않아도 되는 시대가 도래할 수도 있습니다.
스케일링 문제와 관련된 포스팅을 몇 가지 소개해드리오니, 비트코인의 스케일링 문제에 대해서 궁금하시다면 참고하시면 됩니다 : )
*Bitcoin and Scailing - On chain & Off chain : 비트코인의 스케일링 문제
https://steemit.com/lightningnetwork/@cryptodreamers/bitcoin-and-scailing-on-chain-and-off-chain
*Lightning Network란 무엇인가? - 라이트닝 네트워크 (1부)
https://steemit.com/lightningnetwork/@cryptodreamers/lightning-network-1
*Lightning Network란 무엇인가? - 라이트닝 네트워크 (2부)
https://steemit.com/lightningnetwork/@cryptodreamers/lightning-network-2
*Lightning Network란 무엇인가? - 라이트닝 네트워크 (3부)
https://steemit.com/lightningnetwork/@cryptodreamers/lightning-network-3
*라이트닝 네트워크는 불가능한 스케일링 솔루션이다 : Limitation of lightning network(1부)
https://steemit.com/lightningnetwork/@cryptodreamers/limitation-of-lightning-network-1
DAG 알고리즘이 적용된 코인?
IOTA, BYTEBALL, RAIBLOCKS, DAGCOINS, HCASH, HYCON 등이 있습니다.
요 약
- DAG알고리즘은 일방향적 비순환 그래프 구조이다.
- 일방향적 비순환 그래프 구조로 인하여 뛰어난 트랜잭션 처리속도, 확장성, 저렴한 수수료의 장점을 가진다.
- 비트코인처럼 스케일링 문제가 없는 개선된 기능의 알고리즘으로 실생활에 적용하기 위해 활용될 수도 있다.
(비트코인의 라이트닝 네트워크나 블록사이즈 증가의 방법만을 고집하여 상용화를 하고자하는 것이 해결책인 것은 아니다.)
참 고
https://coindrift.io/best-dag-coins-iota-raiblocks-byteball/