기술 공유: 안전하고 공정한 블록 Dag Sorting

Taraxa

特邀专栏作者

2020-01-17 18:26 (UTC+8)

이 기사는 약 4879자로, 전체를 읽는 데 약 7분이 소요됩니다

Block DAG에서 정렬을 보장하고 정렬 프로세스의 보안 및 공정성을 보장하는 방법.

AI 요약

Block DAG에서 정렬을 보장하고 정렬 프로세스의 보안 및 공정성을 보장하는 방법.

머리말

앞선 글에서 DAG 토폴로지에서 발생할 수 있는 문제는 블록과 전송의 순서를 정의하는 것이라고 보았다. 이 게시물에서는 Block DAG에서 주문을 보장할 뿐만 아니라 주문 프로세스가 안전하고 공정하도록 보장하는 Taraxa의 메커니즘에 대해 설명합니다.

정렬이 어려운 이유는 무엇입니까?

Block DAG에서 정렬이 어려운 이유는 무엇입니까?

DAG 데이터 구조만 보면 부분 순서만 설정할 수 있습니다. 즉, 모든 블록이 아니라 일부 블록 간의 순서 관계만 결정할 수 있습니다. 다음은 예입니다.

위의 이미지에서 우리는 파란색 블록이 분명히 정렬에서 녹색 및 주황색 블록보다 먼저 나온다고 100% 확실하게 말할 수 있습니다. 왜? 녹색 및 주황색 블록이 파란색 블록을 가리키므로 주황색 및 녹색 블록이 생성될 때 파란색 블록이 이미 존재하고 그렇지 않으면 주황색 및 녹색 블록이 자신을 가리킬지 모릅니다.

그러나 녹색 블록과 주황색 블록 사이의 순서 관계를 어떻게 알 수 있습니까? 이 질문에 대한 확실한 대답은 없으며 대답은 사용된 정렬 알고리즘 유형에 따라 다르며 순서는 알고리즘마다 완전히 다를 수 있습니다.

순위 지정 프로세스에서 우리는 1개의 자유도를 유지해야 할 뿐만 아니라 순위 지정 알고리즘이 공정하고 안전하도록 보장하기 위해 많은 선택을 해야 합니다. 정직한 네트워크 참가자 또는 공격.

이제 Taraxa가 설계한 Block DAG의 정렬 알고리즘을 살펴보고 이러한 문제를 어떻게 해결할 수 있는지 살펴보겠습니다.

이제 각 블록의 인기도를 측정해 보겠습니다.

무게 - 인기 점수

각 이웃의 인기도를 측정하기 위해 Zohar와 Sompolinsky가 제안한 GHOST 프로토콜을 채택합니다. GHOST는 Block DAG에 포함된 포인터를 기반으로 각 블록의 가중치(각 블록의 "인기")를 계산하는 데 도움이 됩니다.

"무게"란 무엇입니까? Block DAG가 옆으로 회전하면 각 자식 블록과 그 자손이 부모 블록에서 분리되어 있다고 생각할 수 있으므로 GHOST 아래의 모든 블록의 가중치는 블록과 모든 자손의 가중치의 합입니다.

가중치는 해당 블록 위에 다른 블록을 점진적으로 구축하려는 모든 시도의 집합적인 노력을 나타냅니다. 이러한 노력이 조정되지 않고 여러 하위 항목에 분산되는 경우에도 마찬가지입니다.

>GHOST 프로토콜은 매우 간단합니다.

>각 블록 자체는 자연스럽게 가중치가 1입니다.

>각 블록의 가중치는 자체 가중치(1)에 해당 블록을 가리키는 모든 블록의 가중치를 더한 값입니다.

DAG 블록의 경계에서 시작하여 역방향으로 측정

다음은 예입니다.

경계 블록부터 시작하여 각 블록에 가중치를 할당할 수 있습니다. 파란색 블록은 DAG의 경계에 있으며 이를 가리키는 블록이 없으므로 가중치는 1입니다. 녹색 블록에는 자신을 가리키는 블록(파란색 블록)이 하나만 있으므로 녹색 블록의 자체 블록 가중치(1)와 가중치를 가리키는 블록(1)을 더하면 2가 됩니다. 이는 녹색에 대한 새로운 가중치입니다. 블록. 더 나아가 주황색 블록은 3개의 블록을 가리키므로 그 가중치는 3개의 블록의 가중치와 자체 가중치 1의 합입니다: 5+20+12+1=38.

좋아 보이는데 왜 이제 무게순으로 정렬할 수 없나요? 글쎄요. 이 간단한 전략에는 몇 가지 매우 미묘한 문제가 있습니다. 자세히 조사해 보겠습니다.

순서를 혼동하는 방법

정렬 메커니즘의 논리적 기반으로 가중치 값을 사용하는 것만으로는 충분하지 않은 이유를 이해하기 위해 간단한 예를 살펴보겠습니다.

위 이미지에서 시나리오 (a)부터 시작합니다.

(a) 두 개의 주황색 블록이 있고 둘 다 가중치가 1이므로 순서가 모호합니다.

(b) 이전 두 블록을 가리키는 또 다른 블록이 추가되었지만 이제 둘 다 가중치 값이 2이고 여전히 모호한 순서를 갖습니다.

위의 예에서 우리는 모든 사람이 정직하다고 가정하지만 여전히 문제에 부딪힐 수 있습니다. 악의적인 플레이어를 도입하면 해당 플레이어는 블록 DAG 구조의 순서를 적극적으로 난독화할 수 있습니다. 아래의 예를 보자.

이 예에서는 (b)부터 시작합니다.

(b) 순서가 모호한 2개의 주황색 블록이 있습니다.

(d) 다른 블록이 와서 문제를 해결합니다. 이제 명확한 순서가 있습니다. 오랫동안 살다!

(e) 그러나 오래 가지 않습니다... 악의적인 플레이어는 모호한 순서를 유지하기 위해 적극적으로 찾고 경계 블록과 가중치를 이전 위치로 되돌리는 블록(빨간색)을 생성합니다. 문제는 두 개의 주황색 블록이 다시 나타납니다. 잘 주문하지 않았습니다.

이 공격의 또 다른 의미는 악의적인 플레이어가 퍼지 순서를 유지할 수 있을 뿐만 아니라 블록을 추가하기 전과 후에 순서를 전환하여 네트워크를 지속적인 혼란 상태에 빠뜨릴 수 있다는 것입니다.

이들은 매우 간단한 예이지만 이러한 문제는 전체 블록 클러스터가 불확실한 순서 상태로 남아 있는 더 큰 규모에서 발생할 수 있습니다.

그렇다면 이 문제를 어떻게 해결해야 할까요?다음에 앵커 체인과 고스트 포인터의 개념을 소개하겠습니다.

Anchor Chain - 가장 인기 있는 경로

가중치 계산 후 다음 단계는 Block DAG에서 앵커 체인을 결정하는 것입니다. 가중치가 각 블록의 인기 점수라면 앵커 체인은 Block DAG를 통해 가장 많이 사용되는 경로입니다. 경로를 횡단(보행)하는 동안 관찰되는 블록도 네트워크에서 광범위하게 관찰됩니다(매우 일반적임).

앵커 체인을 구축하는 방법은 간단합니다! 시작점을 선택하거나 Taraxa의 경우 실시간 최종성이 있는 이전 블록(실시간 최종성에 대한 기사가 곧 제공될 예정임)을 선택하고 앞으로 걸어가십시오. 의 블록, 각 단계는 가중치가 가장 높은 블록을 선택합니다. 다음은 예입니다.

위의 그림에서 블록 G에서 시작하여 앞으로 이동하면 3개의 가중 블록(381, 765, 381) 중에서 선택할 수 있으며 그 중 가장 무거운 블록은 765입니다. 이 논리에 따라 이 방향으로 계속 이동하면 G 블록에서 끝점까지의 경로가 구성된 앵커 체인(녹색)입니다.

이것은 우리가 이제 정렬 알고리즘을 구축할 수 있는 경로에 블록 DAG를 "앵커"하는 앵커 체인이 생성되는 방식입니다.

앵커 체인을 계산하는 이 방법은 각 뾰족한 블록에 대해 동일한 가중치를 갖는 문제를 해결하지만 공격자가 여전히 앵커 체인을 계속 변경할 수 있기 때문에(매우 빠르게 수렴하지 않음) 또 다른 문제를 야기합니다. 그래서 우리는 고스트 포인터를 도입하여 네트워크가 고정된 앵커 체인으로 더 빨리 수렴되도록 도와 결정론적 순서를 달성합니다.

모든 포인터가 동일하게 생성되는 것은 아닙니다.

네트워크가 무질서해지는 것을 방지하기 위해 고스트 포인터라는 특수 포인터를 도입합니다. 기본 아이디어는 각 블록이 생성될 때 합법적인 것으로 보고 검증된 경계의 모든 블록을 가리키지만 이러한 블록은 특별합니다.

특수 블록은 앵커 체인의 종료 블록입니다.Block DAG 경계에 다른 합법적인 블록의 존재를 인정하는 것 외에도 새로 추가된 각 블록은 종료 블록의 고스트 포인터를 가리킵니다. 여기서 중요한 변화는 블록 가중치 계산에서 고스트 포인터가 가리키는 블록만 고려하고 다른 포인터가 가리키는 블록은 고려하지 않는다는 점이다.

상위 블록은 자신을 가리키는 특수 고스트 포인터만 있는 블록이 됩니다. Taraxa Block DAG 구조에서 각 블록은 하나의 상위 블록만 가리킵니다. 다른 블록은 단순히 블록 트리의 다른 블록을 관찰하거나(원본 텍스트는 나뭇잎을 블록으로 이해할 수 있음) 또는 "조상" - Ethereum에서는 "삼촌" 또는 "ommers"라고 합니다. 이것은 앞서 언급했거나 블록이 가질 수 있는 부모 수에 대해 매우 명시적일 수 있습니다.

이는 DAG 그래프로 표현되는 암시적 투표 과정에서 경계의 모든 블록이 모호한 형태로 표시되지 않도록 하는 근본적인 문제를 해결합니다.

>예를 들어 간단히 살펴보겠습니다.

>두꺼운 화살표는 고스트 포인터입니다(계산된 가중치).

가는 화살표는 확인 포인터입니다(가중치 없음).

(a) 두 개의 블록(1.1 및 1.2)은 첫 번째 제네시스 블록(0)을 가리키며, 두꺼운 선은 하나의 부모 블록만 존재하고 두 블록 모두 이를 가리키기 때문에 고스트 포인터입니다. 현재 순서는 모호하지만 (1.1)이 이기고 향후 블록의 고스트 포인터 후보로 간주된다고 가정하여 비교를 위해 가장 낮은 해시를 사용할 수 있습니다.

(b) 3개의 블록이 추가되지만 네트워크 지연으로 인해 이러한 모든 블록이 동시에 모든 새 블록을 볼 수는 없습니다. 이는 일부 노드가 일부 블록을 더 빠르게 볼 수 있음을 의미합니다. 예를 들어 물리적 거리가 가까워 네트워크 홉이 줄어들면 노드가 블록을 보는 속도가 빨라집니다. 블록(2.1)과 블록(2.2) 모두 이전 두 블록(1.1 및 1.2)을 보았으므로 둘 다 이 두 블록에 대한 고스트 포인터를 가리키고 정직하게 (1.1)이 종료 블록의 앵커 체인에 있는 것으로 식별합니다. 그러나 (2.3)은 (1.1)을 보지 못하므로 (1.2)를 가리키는 고스트 포인터만 사용할 수 있으며 다른 작업을 수행할 수 없습니다. 규칙에 따라 블록의 가중치가 업데이트되었지만 고스트 포인터를 사용하여 이를 가리키는 하위 블록의 일부만 계산됩니다.

(c) 다음 레이어의 블록이 나타났고, (3.1) 블록은 (2.1)과 (2.2) 블록을 동시에 보았고, (3.2) 블록은 (2.1)과 (2.3) 블록을 동시에 보았다. 시간, 블록(3.3)은 블록(2.1, 2.2, 2.3)을 동시에 보았다. 시작할 때 각 블록은 보이는 앵커 체인에서 종료 블록을 선택하고 고스트 포인터를 가리키고 진행합니다.

앵커 체인과 함께 고스트 포인터는 네트워크가 앵커 체인으로 수렴하도록 도와 전체 순서를 안정화합니다. 다음으로 앵커 체인을 기반으로 블록이 궁극적으로 정렬되는 방법을 설명합니다.

앵커로 정렬

고스트 포인터를 사용하여 이전 블록 DAG 예제의 가중치를 다시 계산해 보겠습니다. 고스트 포인터가 가리키는 블록만 가중치를 부모 블록으로 계산한다는 점에 유의하십시오.

앵커 체인이 그려지면 앵커 체인의 각 블록(앵커 블록) 주위에 에포크를 구성합니다. epoch는 앵커 블록이 관찰할 수 있는 블록의 수 또는 앵커 블록이 직간접적으로 가리키는 블록입니다. 슈퍼 인기 앵커 블록의 친구라고 생각하십시오.

위의 그림에서 빨간색 점선을 사용하여 각 앵커 블록 에포크를 플로팅합니다. 불행히도 가중치가 25인 첫 번째 앵커 블록은 에포크 그 자체일 뿐입니다. 가중치 21의 다음 앵커 블록은 자신과 관찰할 수 있는 가중치 1의 다른 두 블록을 포함하여 epoc을 갖습니다. 세 번째 앵커 블록의 가중치는 18이며 하나의 앵커 블록만 관찰할 수 있습니다. 다음 블록의 가중치는 17이고 epoch는 3이며 직접 관찰할 수 있는 가중치 1의 블록과 간접적으로 관찰할 수 있는 가중치 2의 블록을 포함합니다. 이러한 방식으로 각 앵커 블록의 시대가 그려질 때까지 계속 미분합니다.

이제 우리는 블록을 정렬할 준비가 되었습니다! 각 epoch에서 가중치 값은 어떤 블록이 어떤 블록을 가리키는지 보고 어떤 블록이 먼저 오는지 결정하는 데 사용됩니다. 또는 이 방법이 실패하면 앵커 블록과 같은 거리에 있는 블록의 판단 방법으로 블록 해시를 사용합니다.

에포크 그래프를 보면 G가 첫번째(1)입니다. 다음 시대에는 하나의 블록만 있을 것이므로 가중치가 25인 이 블록은 두 번째 블록(2)입니다. 다음 시대로 이동하면 가중치가 1인 두 블록이 가중치가 21인 앵커 블록 앞에 있습니다(가중치가 21인 블록을 가리키기 때문). 이 두 블록을 비교하는 방법은 누구의 해시를 비교하는 것입니다. (3)과 (4)를 결정하고, 다섯 번째 블록(5)은 가중치가 21인 블록이다. 모든 시대의 모든 블록이 정렬될 때까지 계속 진행합니다.

아래와 같이 각 블록의 숫자는 가중치가 아니라 순서를 나타냅니다.

드디어 끝났습니다!

하지만 정말 끝난 걸까요, 정렬되지 않은 블록은 어떻게 될까요?epoch앵커 체인에 속하지 않는 블록 DAG 구조의 경계 근처에는 항상 일부 블록이 있습니다.

의 일부. 그러나 걱정하지 마십시오. 경계에 더 많은 블록이 추가되면 결국 포함됩니다.

앵커 체인(및 결과 순서)이 시간이 지남에 따라 변경되지 않습니까?예, Block DAG 구조 내에서 재정렬의 위험이 있습니다. 이 위험은 시간이 지남에 따라 기하급수적으로 감소하지만 실제로 제거되지는 않습니다. 이것이 Taraxa가 실시간 최종 프로세스를 구현해야 하는 이유입니다(기사 예정).

재정렬의 위험 없이 블록 DAG 구조에 진정한 실시간 완결성이 도입되어 네트워크에서 DApp을 구축하기 위한 기반이 됩니다.

公链

Odaily 공식 커뮤니티에 가입하세요