MEERDAG의 과거와 현재

머리말

한때 블록체인 3.0의 발전 전망이 뜨겁게 논의됐는데, 그 중 DAG는 비트코인과 이더리움 다음으로 가장 유망한 차세대 블록체인 기술로 꼽힌다. 그렇다면 DAG 블록체인의 기원은 무엇일까요? 기술 개념은 무엇입니까?

DAG와 블록체인은 원래 서로 다른 두 가지 기술이었지만, 이 두 가지의 결합, 즉 "DAG 블록체인"의 개념과 처음 각광을 받은 것은 이 선구적인 개념의 선구자인 두 명의 이스라엘인 Yonatan Sompolinsky와 Aviv Zohar에 의해 가능해졌습니다. .

Aviv Zohar가 제안한 GHOST 프로토콜은 초기 단계에서 Ethereum에 의해 채택되었습니다. 이 프로토콜은 체인 포크로 인한 보안 문제를 해결합니다. 분기된 블록체인의 데이터 구조는 단일 체인에서 트리 체인으로 진화합니다. 나중에 Aviv Zohar는 포괄적인 프로토콜을 제안했습니다. Inclusive 프로토콜의 규칙에 따라 블록체인의 데이터 구조는 방향성 비순환 그래프(DAG)로 진화합니다. DAGlabs의 지속적인 DAG 탐색으로 BlockDAG 프레임워크 개념과 기술 아키텍처가 점차 확립되었으며, 그 동안 SPECTER 프로토콜, PHANTOM 프로토콜 및 GHOSTDAG 프로토콜이 연속적으로 출시되었습니다.

Qitmeer는 프로젝트 초기에 분산화(분할 내결함성) 및 보안(일관성)을 희생하지 않고 확장성(가용성)을 다루는 합의 프로토콜을 탐색하고 있었고 이것이 BlockDAG의 설계 철학과 일치한다는 것을 발견했습니다.

좁은 의미에서 BlockDAG는 합의 프로토콜의 기술적 프레임워크로 이해될 수 있으며, 탈중앙화 및 보안을 보장한다는 전제하에 높은 동시성 성능으로 DAG 기술을 더욱 향상시키는 것을 목표로 합니다. 작업 증명 기반의 PoW 합의 메커니즘은 블록체인 네트워크가 충분히 분산되어 있음을 보장할 수 있으므로 블록을 생성하기 위한 블록 채굴이 중요한 기술적 특징이 되었기 때문에 BlockDAG라고 합니다.

Qitmeer 팀은 GHOSTDAG 및 SPECTRE의 합의 알고리즘에 대해 많은 엔지니어링 수준의 최적화를 수행했으며 두 프로토콜의 장점을 유지하여 고유한 특성을 가진 MeerDAG 프로토콜을 만들었습니다.

1. DAG의 기본 구조

1.1 DAG는 어떻게 생겼습니까?

우리 모두는 Merkle 트리의 데이터 구조에 매우 익숙합니다. Bitcoin의 각 블록 내에서 Merkle 트리는 트랜잭션 정보를 기록하는 데 사용됩니다. 아래 이미지를 참조하십시오.

Merkle 트리는 지시된 트리 구조에 속하고 트리의 각 정점은 하나의 이전 정점만 가리킬 수 있으며 전체 데이터는 명확한 흐름 방향을 가짐을 알 수 있습니다. DAG 구조는 각 정점이 여러 이전 정점을 가리킬 수 있도록 하며 전체 데이터 흐름에도 명확한 방향이 있습니다. 또 다른 데이터 구조는 유향 그래프입니다. DAG와 달리 유향 그래프는 데이터가 역류할 수 있으며 전체 구조의 데이터 흐름이 명확하지 않습니다. 세 가지의 차이점은 이미지 2를 참조하십시오.

1.2 블록체인은 특별한 DAG 구조입니다.

DAG 구조를 직관적으로 이해한 후 블록체인이 특별한 DAG 구조로 간주되는 이유를 정리해 볼까요?

블록체인 포크가 블록 생성 속도 및 방송 속도와 관련이 있는지 여부. 블록 생성 속도가 브로드캐스트 속도를 초과하면 여러 블록이 동시에 브로드캐스트되고 포크가 발생합니다. 포크가 많을수록 보안이 나빠집니다. 포크를 줄이기 위해 Bitcoin은 성능과 보안 사이의 균형을 찾습니다. 블록은 10분마다 생성됩니다. 이제 각 블록의 시간이 충분히 길어 이전 블록이 브로드캐스트되기 전에 새 블록이 채굴되지 않는다고 가정해 보겠습니다. 그러면 이 블록체인의 구조는 단일 체인입니다(이미지 3 참조).

사실 네트워크 지연 등의 이유로 분기가 불가피하게 발생하기 때문에 실제 블록체인 구조는 이미지 4와 같을 것이며, 가장 긴 체인 원칙을 통해 유효한 메인 체인(흰색) 중 하나만 선택하게 됩니다. 원장 합의. 나머지 블록(빨간색)의 트랜잭션 정보는 유효하지 않으며 채택되지 않습니다.

이제 원장 합의를 제쳐두고 효과적인 메인 체인을 선택하는 방법을 무시하십시오. 기본 네트워크 구조의 관점에서 일반적인 블록체인 구조는 이미지 5에 표시되고 일반적인 DAG 구조는 이미지 6에 표시됩니다.

두 구조의 유일한 차이점은 DAG 블록이 여러 이전 블록을 가리킬 수 있는 반면 블록체인은 이전 블록만 가리킬 수 있다는 것입니다. 특히, 블록체인의 블록 헤더는 유일한 상위 블록을 가리키는 한 블록의 해시 값만 포함할 수 있습니다. 반면 DAG 구조 아래 블록의 블록 헤더는 이전의 다른 블록을 가리키는 여러 블록의 해시 값을 포함할 수 있습니다. 이미지 7과 같이.

이제 네트워크가 허용할 수 있는 포크 수를 나타내는 포크 계수 K를 소개합니다.

K=0이면 전체 네트워크는 이미지 3과 같이 분기를 허용하지 않습니다.

포크를 허용하지 않는 이 네트워크가 바로 블록체인입니다.

비트코인은 이 정의를 충족합니다. Ethereum에는 삼촌 블록의 포크가 있지만 이러한 삼촌 블록은 메인 체인의 무게를 판단하는 데만 사용되며 결국 메인 체인에 추가되지 않습니다 (엉클 블록 기록 트랜잭션 정보는 메인 체인에 포함되지 않음) ), 따라서 이더리움도 이 정의를 충족합니다.

DAG 네트워크의 K 값은 0보다 큰 정수여야 합니다. 따라서 구조적 관점에서 DAG는 블록체인 구조의 확장이며 블록체인은 특별하고 단순화된 DAG입니다.

1.3 DAG 구조가 성능에 미치는 영향

간단히 말해서 DAG는 포크를 허용하는 네트워크 구조라고 볼 수 있으며 허용되는 포크의 수는 포크 계수 K에 의해 결정됩니다.

그렇다면 포크를 허용하는 네트워크는 정확히 무엇을 의미할까요? 이는 블록 생성 속도가 브로드캐스트 속도를 초과할 수 있음을 의미합니다. 한편으로 이는 단위 시간당 더 많은 트랜잭션이 패키지되도록 합니다. 반면에 블록 A가 전체 네트워크에 의해 브로드캐스트될 때 또 다른 분기된 블록 B도 전체 네트워크에 의해 브로드캐스트되고 결국 일부 노드는 A만 확인하고 다른 노드는 B만 확인하므로 DAG는 노드를 허용합니다. 네트워크에서 동시에 다른 정보를 기록합니다. 이 두 가지 측면의 조합으로 인해 DAG는 높은 동시성과 약한 동기화의 특성을 나타냅니다.

DAG는 비동기 부기의 일종으로 네트워크 처리 정보, 즉 TPS의 속도를 크게 향상시킬 수 있습니다.

블록체인은 네트워크의 각 노드가 동시에 동일한 정보를 기록해야 하는 강력한 동기 부기 네트워크입니다. 그러나 이 요구 사항은 종종 정보를 처리하는 블록체인 네트워크의 기능을 제한하여 TPS를 상대적으로 낮춥니다.

따라서 질문은 포크를 허용하는 이 비동기 부기 네트워크에 어떤 종류의 합의를 사용해야 하느냐입니다. 이전 기사에서 DAG 기반 합의 메커니즘에 대해 자세히 언급했습니다. 합의 메커니즘은 블록 합의와 원장 합의로 나뉩니다. DAG의 블록 합의는 블록체인과 동일할 수 있습니다. 예를 들어 POW도 사용됩니다. 포크가 허용되기 때문에 블록 생성 시간을 매우 짧게 설정할 수 있습니다. 블록 합의는 블록체인과 다를 수도 있습니다. 예를 들어, IOTA 프로젝트는 패키징 및 블록 생성 프로세스를 직접 취소합니다. 트랜잭션이 발생하는 한 즉시 네트워크에 기록됩니다(DAG 다이어그램의 각 블록은 블록이 아니라 펜 트랜잭션입니다). 따라서 초고속 트랜잭션 처리 능력을 얻습니다.

DAG 원장 합의는 블록체인보다 훨씬 더 복잡합니다. 노드가 악을 행하는 것을 방지하는 방법은 무엇입니까? 두 개의 모순된 거래가 있을 때 어떻게 선별합니까? "이중 지출"을 방지하는 방법은 무엇입니까? 기본 네트워크 구조의 복잡성으로 인해 원장 합의에도 더 높은 요구 사항이 부여됩니다. 후속 기사에서 강조 표시됩니다.

1.4 TXDAG 및 BlockDAG

일반화된 BlockDAG(블록 그래프)와 TxDAG(트랜잭션 DAG, 트랜잭션 DAG)의 차이점. 대체로 또는 데이터 구조 측면에서 BlockDAG와 TxDAG는 서로 다른 두 가지 데이터 구조입니다. 차이점은 전자는 여러 트랜잭션을 블록으로 패키징하고 원장은 블록별로 구성된다는 것입니다. 반면 후자는 블록의 개념이 없고 원장은 트랜잭션으로 구성되는데, 이는 블록에서 하나의 트랜잭션으로만 이해될 수도 있습니다. 트랜잭션에는 많은 일반적인 트랜잭션 설명 정보, 즉 헤더 정보가 있으므로 이 부분의 정보는 블록에 저장할 수 있으며 트랜잭션은 트랜잭션의 다른 부분만 저장하면 되므로 HASH 프로세스(채굴) 건너뛰고 체인을 직접 업로드합니다. BlockDAG는 DAG의 높은 동시성을 유지할 뿐만 아니라

1.5 DAG의 장점

블록체인과 비교할 때 DAG는 실제로 그래프와 체인의 차이입니다. 체인의 경우 체인의 In-Degree와 Out-Degree가 하나뿐이고 체인의 노드를 여러 노드로 분할하여 처리할 수 없기 때문에 한 부분만 처리할 수는 없지만 그래프의 경우에는 가능합니다. 그래프는 여러 개의 out-degrees를 가질 수 있기 때문에 여러 개의 out-degrees로 연결된 노드를 동시에 처리할 수 있습니다.

체인 네트워크의 경우 노드의 처리 능력이 강하지 않은 것이 아니라 체인 구조를 병렬로 계산할 수 없으며 낭비되는 시간은 주로 대기 시간입니다. 하나는 동기화가 필요한 트랜잭션을 시작하는 것입니다. 모든 노드와 함께; 다른 하나는 전체 네트워크에 동기화해야 하는 노드 확인이 있는 확인 시간입니다. DAG의 경우 이러한 문제가 없습니다. 지갑이 트랜잭션을 시작할 때 이전에 얼마나 많은 트랜잭션이 있었는지 기다릴 필요가 없습니다. 부분 검증, 네트워크 브로드캐스트 및 기타 부분 검증만 거치면 되며, 이는 거래 확인을 탈중앙화하는 것과 같습니다. 노드는 퍼즐과 유사한 작업을 수행하며 다른 사람이 확인한 트랜잭션과 자신의 트랜잭션을 연결합니다.

따라서 DAG는 다음과 같은 장점이 있다고 결론지었습니다.

(1). 빠른 트랜잭션 속도

비트코인 및 이더리움과 동일한 수준의 분산 및 보안을 달성하는 동시에 DAG 로컬 처리 및 병렬 결제는 트랜잭션 속도를 크게 증가시켜 트랜잭션 처리량(TPS) 및 최종 지연을 두 배 이상 촉진할 수 있습니다.

(2). 강력한 확장성

DAG는 비동기 부기를 지원하기 때문에 네트워크의 노드는 다른 노드의 데이터 동기화를 기다리지 않고 병렬로 새로운 트랜잭션을 처리할 수 있어 시간 낭비를 피하고 트랜잭션 효율성을 향상시키며 부기에 참여하는 각 노드가 빠르게 크게 확장될 수 있습니다. 따라서 DAG는 Qitmeer 팀이 옹호하는 국경 간 소액 결제 및 포괄적인 금융 비즈니스 시나리오와 같은 결제 프로젝트에 매우 적합합니다.

(삼). 악의적으로 수정하기가 더 어렵습니다.

체인 구조에 비해 DAG는 out-degree와 in-degree가 많기 때문에 DAG에서 악의적으로 수정하기가 훨씬 어렵고 노드가 수정되면 해당 in-degree도 수정해야 합니다.

2. MEERDAG의 과거와 현재

2.1 DAG 기술의 기원

2013년 블록체인의 유명한 발상지인 bitcointalk.org에서 ID Avivz78을 가진 이스라엘 히브리 대학교 학자가 합의 알고리즘으로 DAG 개념을 블록체인 구조에 도입할 것을 제안하고 GHOST 프로토콜을 만들었습니다.

GHOST 프로토콜이 제안된 후 Yonatan Sompolinsky는 새로 생성된 블록이 알려진 모든 분기된 끝 블록을 가리키는 또 다른 새로운 아이디어를 제안했습니다.

블록체인은 하나의 체인에서 여러 갈래의 체인으로 구성된 구조로 바뀌는데, 이러한 체인 구조를 DAG(directed acyclic graph)라고 합니다.

2016년에는 기술 아키텍처의 세부 사항을 더욱 개선하고 1세대 blockDAG 프로토콜의 프로토타입을 형성하고 매개변수화(또는 지연 매개변수 적응) 없는 네트워크 지연이라는 대대적인 아이디어를 제안한 SPECTER 기술 프로토콜 문서가 발표되었습니다.

2018년 DAGlabs는 PHANTOM 프로토콜을 출시했습니다. SPECTER 프로토콜이 선형 정렬을 거래할 수 없는 문제를 해결하고 이를 최적화하여 최초의 산업 등급 BlockDAG 프로토콜이자 BlockDAG의 성숙도를 표시하는 GHOSTDAG 프로토콜을 형성했습니다.

GHOSTDAG 프로토콜 문서의 끝에서 Yonatan Sompolinsky는 GHOSTDAG + SPECTRE를 결합한 가능한 프로토콜을 구상했지만 자세히 소개하지는 않았습니다.

3. MEERDAG의 기술 선택에 대한 생각

3.1 MEERDAG 기술 선택에 대한 생각

Qitmeer 네트워크의 첫 번째 단계인 Mecca Network에서 확장 기술 탐색의 급증과 동시에 온체인 및 오프체인의 많은 주류 확장 솔루션에 직면했으며 Qitmeer 퍼블릭 체인 기술을 선택할 때 어려운 선택에 직면했습니다.

확장 기술 선택 측면에서 업계는 일반적으로 불가능한 삼각형 문제에 직면해 있습니다. 확장성(Scalability), 탈중앙화(Decentralization), 보안성(Security)을 동시에 달성하는 것은 불가능하며, 세 가지 중 두 가지만 달성할 수 있다. 당시 Qitmeer 팀도 이러한 문제에 직면했습니다. 많은 확장 솔루션을 연구한 후, BlockDAG라는 기술이 마침내 팀에서 선호되었습니다.

3.2 SPECTER 프로토콜에 대한 간략한 소개

SPECTER는 빠른 확인을 지원하는 blockDAG 프로토콜입니다. SPECTRE의 합의 알고리즘은 투표 알고리즘입니다. 충돌 트랜잭션이 발견되면 충돌 트랜잭션이 포함된 블록이 모든 블록의 투표를 수락하는 후보로 사용되며 각 블록에 대해 하나의 투표가 있습니다. SPECTRE의 투표는 증폭 효과가 있습니다. 예를 들어, 블록은 과거에 집중했던 다수의 투표를 따르게 되므로 수렴 속도가 매우 빠르고, 투표 수의 약간의 차이가 승자에게 큰 이점이 될 수 있습니다. 정직한 블록이 정직한 블록에 투표하도록 하면 나중에 정직한 블록이 이전 스태킹 권한을 부여하여 악의적인 공격이 실패하고 네트워크의 보안이 보장됩니다.

SPECTER는 정직한 블록의 빠른 확인만 보장할 수 있습니다. 릴리스 시간이 가까운 두 개의 충돌하는 블록의 경우 SPECTER의 확인 시간이 불확실합니다. 이것은 SPECTRE가 제안한 약한 활동의 ​​개념입니다. 즉, 모든 블록이 합리적인 시간 내에 최종 확인될 수 있다고 보장할 수 없습니다.

SPECTER는 트랜잭션 시스템을 기반으로 하는 합의 프로토콜입니다. 거래 시스템에서는 악인만이 이중 지급 거래를 생성할 수 있습니다. 즉, 이중 지출 거래는 정직한 블록에 큰 영향을 미치지 않습니다. 또한 이중 지출 거래를 하는 것은 시간 통제가 매우 엄격하여 정상적인 상황에서 공격을 일으키기 어렵습니다. 따라서 Qitmeer 팀은 SPECTER의 약한 활동 문제가 실제 프로젝트에서 수용 가능하다고 생각합니다.

3.3 GHOSTDAG 프로토콜에 대한 간략한 소개

위의 SPECTER 프로필에서 볼 수 있듯이 SPECTER는 충돌하는 트랜잭션을 해결하고 공격을 방어하는 데 매우 능숙합니다. 프로젝트가 Bitcoin과 같이 결제 목적으로만 사용되는 경우 SPECTER 프로토콜의 빠른 확인으로 충분합니다. 그러나 스마트 계약을 통합하려는 경우 SPECTER는 할 수 없습니다.

SPECTER는 충돌하는 트랜잭션의 상대적인 정렬(충돌하는 트랜잭션의 순서 판단)만 수행할 수 있지만 모든 블록에 대한 절대 정렬은 수행할 수 없기 때문입니다. 스마트 계약의 언어는 튜링 완전해야 하기 때문에 우리가 컴퓨터 프로그램을 작성하는 것처럼 다양한 작업을 엄격한 순서로 수행해야 하므로 스마트 계약 기능이 있는 네트워크는 특징이 있습니다. 순차적으로 선형 정렬(연대순)을 수행합니다.

이에 대해 Yonatan Sompolinsky는 DAG 블록에 대한 선형 순서를 형성하기 위해 GHOSTDAG 프로토콜을 새로 설계했습니다. SPECTER와 GHOSTDAG는 두 개의 완전하고 독립적인 프로토콜이며 서로를 보완하는 것이 아닙니다.

GHOSTDAG의 채굴 메커니즘은 동일한 유형의 DAG 구조를 생성하는 SPECTRE의 채굴 메커니즘과 동일합니다. 차이점은 GHOSTDAG는 블록 연결성을 분석하여 블록이 정직한지 악의적인지 판단하고 분류에 따라 블록을 정렬하고 엄격한 DAG 블록을 생성한다는 것입니다. 충돌하는 트랜잭션의 선형 순서는 선형 순서로 판단됩니다.

GHOSTDAG 프로토콜은 DAG가 트랜잭션 선형 주문 기능을 얻을 수 있도록 할 뿐만 아니라 SPECTER 프로토콜의 취약한 활동 문제도 해결합니다. GHOSTDAG 프로토콜은 트랜잭션의 선형 순서를 지원하는 최초의 blockDAG 프로토콜이기도 합니다.

3.4 MEERDAG 프로토콜

GHOSTDAG 프로토콜 문서의 끝에서 Yonatan Sompolinsky가 구상한 GHOSTDAG+SPECTRE를 결합한 가능한 프로토콜은 아이디어 측면에서 지침을 제공하는 데 더 가깝습니다. 실제 상황을 기반으로 합니다. 상황은 지속적으로 연습되고 테스트되며 가장 일반적인 문제 중 하나는 성능입니다. 원문의 참조 알고리즘에 따라 직접 구현하면 성능이 거의 용납되지 않습니다.

Qitmeer 팀은 퍼블릭 체인의 기본 애플리케이션 시나리오가 주로 포괄적인 금융, 디지털 자산 거래 및 공급망 관리라고 생각합니다.

선형 정렬 기능에 대한 블록 보상 메커니즘 및 원장 합의 요구 사항을 고려하는 동시에 가치 교환 경험에 더 중요한 트랜잭션 확인 속도를 고려합니다.

GHOSTDAG의 파란색 세트(정직한 블록)는 안정화하기가 더 어렵고 확인 시간이 SPECTRE보다 훨씬 길 것입니다. 그러나 블록 보상은 높은 확인 시간이 필요하지 않기 때문에 네트워크에 영향을 미치지 않습니다. GHOSTDAG 프로토콜은 기본 합의 프로토콜로 선택되고 SPECTER 프로토콜은 보조 합의 프로토콜로 선택됩니다.

SPECTER와 GHOSTDAG를 결합한 하이브리드 컨센서스 솔루션인 MeerDAG는 기존 블록체인 설정(개방성, 공정성, 보안성, 확장성)을 준수하고 기존 블록체인 모델 UTXO와 가장 호환되는 BlockDAG 스케일링 솔루션입니다. 클래식 블록체인이 가장 긴 체인 외부의 모든 블록을 폐기하는 반면, MeerDAG는 SPECTER 프로토콜을 유지하고 모든 블록을 유지하는 협력 모델이므로 높은 처리량을 달성하고 실제 트랜잭션 수준의 높은 처리량을 제공할 뿐만 아니라 블록체인 트랜잭션의 빠른 확인을 제공할 수 있습니다. 서비스. 둘째, BlockDAG는 가장 무거운 체인 규칙을 기반으로 하며 비트코인에 필적하는 51% 내결함성을 달성할 수 있습니다. 또한 BlockDAG 네트워크에는 특별한 노드가 없으며 노드가 온라인 상태인지 여부가 필요하지 않습니다. 채굴에서는

Qitmeer Network Medina 기간 동안 네트워크는 실제 컴퓨팅 성능 환경 테스트를 도입했습니다. 팀은 PoW 알고리즘을 지속적으로 반복하고 알고리즘의 효율성을 개선했으며 GHOSTDAG+SPECTRE 프로토콜의 장점을 완전히 유지하고 엔지니어링 구현에서 프로토콜 구현의 어려움을 지속적으로 줄였습니다. 예를 들어, GHOSTDAG 알고리즘 논문의 첫 번째 버전에 따르면 역원뿔 계산은 철저해야 하며 알고리즘 복잡도는 O(n^3)입니다. 많은 수의 엔지니어링 수준 테스트 후 복잡성이 O(n)으로 두 자릿수 감소하여 유용성 요구 사항을 크게 충족합니다. 보안, 분산화 및 공정성을 보장하는 기본 요구 사항에 따라 TPS 성능이 극대화됩니다.

Qitmeer 팀은 GHOSTDAG+SPECTRE 프로토콜을 혁신적으로 결합하여 고유한 MeerDAG 프로토콜을 형성했으며, 이는 차세대 BlockDAG의 기술 프로토타입이 되었습니다. Qitmeer의 BlockDAG 기본 네트워크의 핵심 포지셔닝은 가치 순환 네트워크 역할을 하는 것입니다. 레이어 2 레이어에서 MeerEVM 기반 플러그형 가상 머신 시스템을 결합하여 풍부한 블록체인 애플리케이션을 구축하고 전체 블록체인 생태계를 수용합니다.

참조：
[1] 블록체인에서 DAG까지 (2) -- DAG의 기본 구조,https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg
[2] 블록체인에서 blockDAG로,https://www.youtube.com/watch?v=tk38AAV_whw
[3] Jeff Zhou：DAG 고속 비동기 블록체인 기술,https://www.jianshu.com/p/45d73e0e74ec
[4]GHOST, SPECTRE, PHANTOM 기술 이론,https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q
[5]Qitmeer 팀 – "Qitmeer 백서"