블록 DAG의 실제 완결성

머리말

머리말

첫 번째 레벨 제목

완결성의 중요성

오늘날 대부분의 블록체인 토폴로지의 최종성은 확률을 기반으로 합니다. 즉, 트랜잭션이 실제로 완료되었는지 100% 확신할 수 없습니다. 예를 들어 비트코인 ​​네트워크에서 시간이 지남에 따라(또는 비트코인 ​​세계의 언어에서는 블록 수가 증가함에 따라) 공격자가 네트워크의 나머지 부분을 따라잡고 블록을 재구성할 확률은 기하급수적으로 감소합니다. 이 기하급수적인 위험 감소는 "6블록" 경험론을 불러일으켰습니다. 즉, 트랜잭션이 포함된 블록에 5개의 블록이 더 추가되면 트랜잭션이 "6 블록 깊이"이고 통계적으로 트랜잭션이 그다지 재정렬 공격을 받을 수 있습니다.

대부분의 경우 확률론적 마무리가 좋습니다. 그러나 각 트랜잭션이 이전 트랜잭션의 출력에 따라 달라지는 많은 수의 트랜잭션을 실행하거나 대규모 트랜잭션을 실행하고 이 트랜잭션이 절대 취소되지 않도록 해야 하는 경우 완결성은 꽤 중요합니다.

첫 번째 레벨 제목

DAG 최종성은 무엇을 의미합니까?

초기 주문 메커니즘의 재배열 위험은 주로 앵커 체인이 변경될 때 발생했음을 상기하십시오.

따라서 앵커 체인이 정기적으로 고정되도록 보장할 수 있는 한 앵커 체인의 블록 순서는 무슨 일이 있어도 완전히 결정할 수 있습니다.

어떻게 하죠? 네트워크는 DAG 경계 근처의 특정 블록에 무한 가중치를 적용하기 위해 블록 DAG 구성과 동기화된 정기적인 투표를 개최합니다.

블록에 무한 가중치가 주어진다는 것은 고스트 포인터(ghost pointer)를 통해 자신이 직간접적으로 가리키는 모든 블록이 무한 가중치를 갖는다는 것을 의미하며, 이제 이 순서를 공격으로 전복시킬 수 없다는 의미입니다.

위의 그림에서 우리는 주황색 블록을 선택하여 무한한 가중치를 부여했으며, 이 무한대가 블록 DAG(그림에서 진한 회색으로 표시됨)를 다시 가리킴으로써 앵커 체인의 모든 블록에 무한한 가중치를 부여했음을 알 수 있습니다. . 우리는 이제 이 앵커 체인의 순서와 자체 시대의 모든 블록을 효과적으로 결정했습니다.

첫 번째 레벨 제목

PBFT 유사 알고리즘에 의한 주기적인 블록 선택

최종화를 위해 DAG 내에서 블록을 선택하기 위해 PBFT(Practical Byzantine Fault Tolerance) 알고리즘과 유사한 프로세스를 사용합니다. PBFT가 잘 개발되고 널리 배포되는 알고리즘이라는 점을 고려하여 이 문서에서 다룰 세부 정보 및 잠재적 오류(결함)는 여기서 반복하지 않습니다.

PBFT의 기간 블록 마무리 프로세스는 아래의 매우 단순화된 다이어그램과 같이 대략 네 단계로 나뉩니다.

보조 제목

1. 새로운 블록 제안

• VRF(SK, previous_PBFT_block_hash, current_vote_type, current_round_number, current_step_number) = (e, π)를 통해 적격성을 계산합니다. 여기서 e는 적격성 값이고 π는 VRF가 올바르게 계산되었다는 증거입니다.

• "e < 임계값이면 이번 라운드에서 PBFT 블록을 제안할 자격이 있습니다."

• 최종 확정을 위해 경계에 있지만 경계에 있지 않은 DAG 블록 후보, 즉 현재 주기(Period)의 블록 후보 Pt를 선택

• Pt와 P(t-1) 사이에 주기를 만들고(자세한 내용은 아래 참조) 이 주기에 포함된 모든 블록을 찾습니다.

• 동시 스케줄러 CS 만들기

• (Pt, CS) 및 타임스탬프, 서명, 수혜자와 같은 기타 정보를 포함하는 PBFT 블록 후보(Pc) 생성

• Pc(해시)의 해시 계산

• 보조 제목

2. 리더 투표

• 다른 (e, π)를 생성하기 위해 VRF(current_round_number + 1 및 현재 투표 유형 가져오기)를 통해 자격을 다시 계산합니다.

• "e < 임계값이면 이번 라운드에 적합"을 결정합니다.

• 2λ를 기다리십시오. 여기서 λ는 네트워크 직경입니다. 즉, 네트워크에서 가장 먼 두 노드 사이의 최단 거리(시간)입니다.

• π도 정확하고 생성자가 최소값일 때 관찰된 e의 최소값을 계산합니다. e가 "리더"일 때 생성자입니다. 이 노드는 다음 PBFT 블록 후보를 제안하는 노드입니다.

• 보조 제목

3. 블록 투표

• 다른 (e, π)를 생성하기 위해 VRF(current_round_number + 1 및 현재 투표 유형 가져오기)를 통해 자격을 다시 계산합니다.

• "e < 임계값이면 이번 라운드에 적합"을 결정합니다.

• 2 람다 대기

• 주어진 e_min 시간 내에 2T+1 표를 받았는지 계산합니다(여기서 T는 지난 라운드에서 자격을 갖춘 투표 노드의 1/3입니다).

• 아직 PBFT 블록이 없으면 e_min에 해당하는 Pc 및 관련 해시(Pc)에 대해 P2P 폴링을 수행합니다.

• PC가 올바르게 생성되었는지 확인

• 보조 제목

4. 투표하여 다음 단계로 이동

• 다른 (e, π)를 생성하기 위해 VRF(current_round_number + 1 및 현재 투표 유형 가져오기)를 통해 자격을 다시 계산합니다.

• "e < 임계값이면 이번 라운드에 적합"을 결정합니다.

• 2 람다 대기

• 주어진 PC가 2T+1표를 받았는지 계산

• 우승한 PC가 올바르게 생성되었는지 확인

• 가장 최근에 검증된 PC를 계산하고 그 결과를 영구 저장소에 커밋

• 첫 번째 레벨 제목

PBFT에 대한 추가 소개

위에 쓰여진 것은 매우 간단한 설명입니다.

텍스트

이 PBFT 프로세스는 매우 안전하고 확장 가능합니다.

노드가 말하기를 원할 때마다 VRF 적격성 값을 계산하여 해당 라운드에서 말할 자격이 있는지 확인합니다. 다음 두 가지를 보장하기 위해 적격성 임계값이 설정되고 동적으로 조정됩니다.

각 라운드에 참여하는 노드는 무작위이며 잠재적으로 다릅니다. 즉, 공격자가 노드를 참여자로 관찰하고 대상으로 지정하면 다음 라운드에서 실격될 수 있습니다. 이것은 참가자(또는 위원회 구성원)를 장기간 유지하여 공격의 주요 대상으로 만드는 다른 많은 알고리즘과 다릅니다.

주어진 라운드에서 적격 노드의 일부만 참여하므로 이 PBFT 프로세스의 확장성이 뛰어납니다. 즉, 네트워크 용량이 확장되고 자격을 갖춘 참가자 수가 증가하더라도 네트워크 용량과 관련된 이러한 PBFT 라운드의 실제 참가자(위원회 규모)를 쉽게 설정하여 부선형 확장을 달성할 수 있습니다. 참가자 수가 적을수록 투표 프로세스가 빨라집니다.

첫 번째 레벨 제목

병렬 PBFT 체인

Taraxa의 PBFT 프로세스는 기존 블록의 DAG와 함께 PBFT 블록의 선형 체인을 생성합니다.

모든 PBFT 블록에는 두 가지 주요 목표가 있습니다.

• 주기적 블록에서 DAG 블록의 마무리 완료

• 첫 번째 레벨 제목

DAG 블록의 완전한 마무리

이 PBFT 프로세스는 블록 DAG 내의 단일 블록을 확인합니다. 따라서 PBFT 프로세스를 활용하는 대부분의 다른 네트워크와 달리 전체 블록체인 프로세스를 확인하는 주요 합의 알고리즘 역할을 하지 않습니다. 이것이 바로 Taraxa의 PBFT 프로세스가 블록 DAG 생성 프로세스와 병렬적이고 대체로 비동기적인 이유입니다.

새 DAG 블록이 완료될 때마다 앵커 체인에 확정된 앵커 체인과 관련 블록 세트를 생성합니다(각 앵커 블록의 에포크를 따라 구현됨). 전체 블록의 집합을 기간이라고 하며 최종 정렬된 블록 클러스터의 스냅샷으로도 볼 수 있습니다.

첫 번째 레벨 제목

동시 스케줄링

동시 스케줄링은 다음과 같은 방식으로 순서를 결정합니다.

• 블록의 순서는 주기에 많은 블록이 있기 때문에 순서 지정 메커니즘에 의해 정의됩니다.

• 블록 간 중복 트랜잭션을 필터링합니다. 우리는 DAG 데이터 구조를 사용하기 때문에 여러 블록 제안자가 동일한 트랜잭션 세트를 다른 DAG 블록으로 패키징하여 어느 정도 트랜잭션이 겹칠 가능성이 매우 높습니다. Taraxa는 이 중첩을 조정하는 데 도움이 되도록 트랜잭션 중재 메커니즘(이후 기사에서 자세히 소개됨)을 설계했습니다. 우리는 이 상황을 최소화하기를 희망하지만 0이 되지는 않습니다. 그렇지 않으면 트랜잭션이 과도하게 격리될 것입니다.

• 트랜잭션을 동시 집합과 순차 집합으로 나눕니다.

• 이것은 트랜잭션을 병렬로 안전하게 실행할 수 있는 트랜잭션과 순차적으로 실행해야 하는 트랜잭션으로 나누는 일련의 추측 실행 알고리즘을 사용하는 동시 EVM 설계(이후 기사에서 소개됨)의 핵심 부분입니다. .

  모든 개별 DAG 블록을 단일 블록으로 결합하고 각 PBFT 블록을 내장한 결과로 동시 스케줄링을 생각할 수도 있습니다.

컨센서스 외에도 더 흥미로운 기술들을 계속해서 공유하고 연구 및 구현 과정에서 공개할 예정입니다.

계속 지켜봐!