Vitalik: 조각화 + 데이터 가용성 샘플링

저자 | 비탈릭 부테린

저자 | 비탈릭 부테린"지분 증명 외에도 eth2 설계의 또 다른 중요한 변화는 샤딩입니다. 이 제안은 제한된 형태의 샤딩인 "데이터 샤딩"을 소개합니다."롤업 중심 로드맵

노드가 모든 데이터 자체를 다운로드하는 부담을 피하기 위해 이 두 가지 기술을 서로 중첩하여 대량의 데이터 가용성을 확인할 수 있습니다. 샘플링, DAS) .

첫 번째 레벨 제목

속담 "무작위 샘플링 위원회"

예를 들어 16MB와 같은 많은 데이터가 있다고 가정해 보겠습니다. 이것은 eth2 체인(적어도 처음에는)이 슬롯당 처리할 수 있는 양입니다. 우리는 이 데이터를 각각 크기가 256kB인 64개의 얼룩으로 나타냅니다. 약 6400명의 유효성 검사기가 있는 PoS 시스템도 있다고 가정합니다. 1) 누구에게나 모든 데이터를 다운로드하도록 요구하지 않고 2) 소수의 유효성 검사기를 실행하는 공격자에게 기회를 주지 않고 어떻게 이 데이터를 검증할 수 있습니까?

첫 번째 문제는 분업으로 해결할 수 있습니다. 검증자 1-100은 첫 번째 Blob을 다운로드하고 확인해야 하고, 검증자 101-200은 두 번째 Blob을 다운로드하고 확인해야 합니다. 각 하위 집합(위원회)의 유효성 검사기는 해당 blob을 검증했음을 증명하기 위해 서명하기만 하면 되며, 전체 네트워크는 해당 위원회의 유효성 검사기 대다수의 서명을 받은 후 blob을 수락할 수 있습니다.

그러나 이것은 문제로 이어집니다. 공격자가 연속적인 검증자 집합(예: 1971-2070)을 제어하면 어떻게 될까요? 이 경우 공격자가 전체 검증자 집합의 약 1.5%만 제어하더라도 단일 위원회를 제어할 수 있으므로(위의 경우 위원회 20에서 검증자 2001-2100의 70%를 제어할 수 있음) 공격 운영자는 유효하지 않거나 사용할 수 없는 얼룩을 체인에 추가할 수 있습니다.

RNG(Random Number Generator)는 검증인이 입금한 후 시딩되며 각 검증인의 인덱스는 고정되어 있으므로 공격자는 모든 검증인을 동일한 위원회에 포함시키려고 할 수 없습니다. 공격자는 운이 좋을 수 있지만 모든 유효성 검사기의 1/3 이상을 제어하는 ​​경우에만 가능합니다.

첫 번째 레벨 제목

Vernacular "데이터 가용성 샘플링"

어떤 면에서 데이터 가용성 샘플링은 무작위 샘플링 위원회의 미러 이미지입니다. 샘플링은 각 노드가 전체 데이터의 일부만 다운로드하기 때문에 여전히 발생하지만 샘플링은 클라이언트에서 그리고 Blob 전체가 아닌 Blob별로 발생합니다.

각 노드(스테이킹에 참여하지 않는 클라이언트 노드 포함)는 전체 Blob을 다운로드하는 대신 각 Blob을 확인하고 개인적으로 N개의 임의 인덱스를 선택한 다음 해당 위치에서 데이터 다운로드를 시도합니다.

이 메커니즘은 클라이언트가 가용성을 확인하기 위해 각 BLOB에서 데이터의 작은 부분만 다운로드하면 되기 때문에 효율적입니다. 이 메커니즘은 51%의 공격자도 클라이언트가 사용할 수 없는 blob을 수락하도록 속일 수 없기 때문에 매우 안전합니다.

삭제 코딩

텍스트

공격자가 사용 가능한 데이터의 50-99%를 제공하는 상황(일부 클라이언트가 Blob을 거부한 다음 다른 클라이언트에서 허용할 수 있음)을 피하기 위해 삭제 코딩이라는 기술을 사용합니다. . 삭제 코딩을 사용하면 Blob 데이터의 절반 이상이 게시된 경우 네트워크의 모든 사용자가 나머지 데이터를 재구성하고 게시할 수 있는 방식으로 Blob을 인코딩할 수 있습니다.

다시 게시된 데이터가 브로드캐스트되면 처음에 blob을 거부한 클라이언트가 수렴하여 수락합니다(blob 수락에는 시간 제한이 없으며 클라이언트가 샘플링된 모든 인덱스에 대한 응답을 받을 때마다 사용 가능한 blob을 수락함). .

이레이저 코딩을 이해하기 위한 가장 쉬운 수학적 유추는 "항상 두 개의 점이 라인을 복구하기에 충분합니다"입니다. ((1, 4), (2, 7), (3, 10), (4 , 13)) "파일"을 생성하기 위해 각 포인트는 선에 있고 두 포인트의 좌표가 있는 한 라인을 재구성하고 나머지 두 포인트를 계산할 수 있습니다( x- 좌표 1, 2, 3, 4는 파일 작성자의 선택이 아니라 시스템의 고정 매개변수입니다.

고차 다항식을 사용하여 이 아이디어를 확장하여 6개 파일 중 3개, 8개 파일 중 4개를 생성하거나 일반적으로 n개 파일 중 n개 파일 포인트가 있는 경우 2n개 중 나머지 포인트를 계산할 수 있습니다.

다항식 약정, 특히 Merkle 루트가 아닌 Kate 약정을 데이터 블롭의 프린터로 사용합니다. 다항식 약정을 사용하면 주어진 값이 실제로 특정 차수 n까지 다항식임을 쉽게 증명할 수 있기 때문입니다. 좌표에서의 정확한 추정이 필요합니다. 그렇지 않으면 Merkle 루트가 저차 다항식을 인코딩한다는 것을 증명하거나(예: SNARK 사용) 인코딩이 잘못된 경우 브로드캐스트하기 위해 사기 증명에 의존해야 합니다(높은 복잡성과 더 많은 동시성 가정 추가).

첫 번째 레벨 제목

데이터 가용성 샘플링은 여전히 ​​위원회 메커니즘과 함께 필요합니까?

위원회에만 의존하는 경우 다음과 같은 단점이 있을 수 있습니다.

➤ 51% 공격 시 방어력이 약해집니다. 현재(확장 불가능) 블록체인에서 51% 공격은 트랜잭션을 롤백하거나 검열만 할 수 있으며 유효하지 않은 블록을 체인에 추가할 수 없습니다. 위원회 기반 시스템은 이러한 보장을 상실합니다.

더군다나 51% 공격자들은 악의적인 행동과 관련이 있다고 입증되고 그에 따라 처벌될 수 있는 예치금(해당 위원회에 참여하는 예치금)이 매우 적기 때문에 효과적으로 처벌하기가 매우 어려울 것입니다.

➤ DAS는 양자 공격에 저항하는 위원회 메커니즘보다 약간 더 쉽습니다(양자 후 집계 서명이 필요할 수 있음).

첫 번째 레벨 제목

데이터 가용성 샘플링이 있는 위원회 메커니즘이 여전히 필요합니까?

DAS만 사용하는 경우 다음과 같은 문제가 발생할 수 있습니다.

➤ DAS는 검증되지 않은 신기술로, 그 핵심(여기 참조)은 실제로 작년에야 개발되었습니다. 따라서 DAS 충돌이나 예기치 않은 개발 시간 연장에 대비하여 위원회를 활용하여 보호하는 것이 좋습니다.

➤ DAS는 위원회보다 대기 시간이 더 깁니다.

➤ DAS에는 위원회에서 지원할 수 있는 엣지 케이스가 더 많습니다. 한 가지 예는 DAS 전용 시스템에서 Blob 가용성을 확인하기 위해 DAS 요청을 처음 시작하는 비컨 블록 제안자를 피하기가 어렵다는 것입니다.

이로 인해 공격자가 사용할 수 없는 Blob을 게시하고 제안자의 요청에만 응답할 위험이 높아집니다. 이로 인해 네트워크의 다른 노드가 사용할 수 없는 블롭을 수락하지는 않지만 다른 공격을 더 쉽게 만들어 정직한 제안자가 구축한 비콘 블록이 거부되고 메인 체인에서 분기될 수 있습니다. 위원회는 이를 해결할 수 있습니다.

➤ 위원회 메커니즘의 상위 호환성이 강화되어 향후 샤드에 실행 기능을 추가할 수 있습니다.

데이터 가용성의 중요성? 도전 과제는 무엇입니까?

이것은 다른 곳에서 논의되었으므로 여기에 게시하지는 않겠지 만 다음을 읽는 것이 좋습니다.

➤ 데이터 가용성 및 삭제 코딩에 대한 참고 사항(데이터 가용성에 대한 초기 소개)

➤ Alberto Sonnino, Mustafa Al-Bassam 및 Vitalik Buterin이 개념을 확장한 논문

➤ The Dawn of Hybrid Layer 2 Protocols는 데이터 가용성의 게임 이론에 대해 논의합니다.

➤ Base Layers 및 Functionality Escape Velocity, 위의 개념을 바탕으로 Data Scalability 부분을 기술

➤ 데이터 가용성 문제(Ethereum Silicon Valley Meetup), 데이터 가용성 문제에 대한 비디오 토론

명확히 말하면 BitTorrent와 IPFS 및 이와 유사한 시스템은 데이터 가용성 문제를 해결하지 못합니다. BitTorrent는 확장성이 뛰어난 데이터 배포 기술이지만 데이터 사용 여부에 대한 합의에 도달할 수 없기 때문에 "극단적인 경우" 공격의 가능성이 있습니다. 2 프로토콜이 비효율적입니다. 데이터 가용성에 대한 합의에 도달하려면 이 문서에 설명된 보다 강력한 기술을 사용해야 합니다.

샤딩은 P2P 계층에서 어떻게 작동합니까?

샤딩의 확장성 목적을 달성하기 위해서는 모든 노드가 모든 데이터를 다운로드할 필요가 없도록 P2P 시스템이 필요합니다. 다행스럽게도 우리는 이미 Phase 0에서 일종의 P2P 레이어 샤딩을 가지고 있습니다. 구체적으로 집계를 설명하기 위해 64개의 하위 집합이 사용되었습니다. 각 유효성 검사기는 다른 63개의 집계 증명 하위 집합에서 데이터를 가져오지 않고 기본 "글로벌 서브넷"과 자체 증명 집계 서브넷에만 존재하면 됩니다.

위원회 + DAS 유형 샤딩에서 2048개의 수평 서브넷(horizontal subnets)이 있는 "그리드" 아키텍처로 확장합니다. 서브넷), 즉 각 blob에 각 인덱스의 하위 집합이 있습니다.

각 슬롯에서 샤드당 제안자를 선출합니다. 각 제안자는 blob을 제안할 권리가 있습니다. 최대 512kB의 임의 데이터 블록(약 512바이트의 "샘플" 모음으로 이해할 수 있음), 삭제 코딩 확장 및 추가 증명 포함 blob의 각 부분 독립적으로 확인됩니다.

Blob의 구조 Blob의 구조

blob의 "본문" 구조는 원본 데이터, 확장 데이터 및 증명으로 구성됩니다(원하는 경우 데이터 효율성을 위해 확장 데이터를 생략할 수 있습니다. blob을 수신하는 각 노드는 blob을 비교적 빠르게 재구성할 수 있기 때문입니다).

Blob의 "헤더"에는 다른 데이터(슬롯, 샤드 및 길이 증명) 및 제안자의 서명과 함께 해당하는 Kate 약속이 포함됩니다.

Blob 브로드캐스팅 프로세스

Blob이 브로드캐스트되면 해당 헤더는 글로벌 서브넷으로 브로드캐스트되고 본문은 슬롯 및 샤드 ID에 해당하는 수평 서브넷으로 브로드캐스트됩니다.

실제로는 2048개의 수평 서브넷이 있으므로 각 시대의 각 샤드-슬롯 쌍에 대해 하나의 수평 서브넷이 있습니다. 이는 각 유효성 검사기가 수평 서브넷에 참여할 수 있도록 하기 위해 수행되며 위원회에 해당하는 Blob만 수신합니다(샘플링에 참여하는 소수의 수직 서브넷 제외).

각 유효성 검사기는 다음 서브넷에 가입해야 합니다.

➤ 글로벌 서브넷

➤ 할당된 인덱스에 해당하는 수직 서브넷(검증자당 프라이빗 시드를 사용하여 계산됨)

브로드캐스트 블록

텍스트

Blob 제안자는 모든 서브넷에 샘플을 배포할 수 있지만 서브넷의 일부일 필요는 없습니다. 프로세스는 다음과 같습니다.

➤ 게시: 제안자는 올바른 수평 서브네트워크에 Blob을 게시합니다. 각 샘플에는 증명이 함께 제공됩니다.

➤ 직접 샘플 배포: 수평 서브넷의 다른 참가자는 자신이 속한 각 수직 서브넷에 블록을 게시합니다.

➤ 간접 샘플 배포: 제안자는 자신이 속한 여러 수직 서브넷을 동료에게 알립니다. 따라서 수평적 서브네트워크의 각 참가자는 피어가 있는 수직적 서브네트워크를 볼 수 있고 해당 블록을 해당 피어에게 브로드캐스트할 수 있습니다.

데이터 블록 크기가 512바이트이고 최대 데이터 블롭이 512kB(이레이저 코딩 제외)라고 가정하면(이레이저 코딩 포함 시 약 1MB) 수직 서브넷이 2048개 있습니다. 각 노드가 15개의 프라이빗 수직 서브넷, 5개의 퍼블릭 수직 서브넷에 존재하고 50개의 피어가 있는 경우 최악의 경우 각 수평 서브넷(위원회만 해당)의 구성원이 128이라고 가정하면 서브넷 구성원만 128 * 20 = 2560 서브넷(약 . 1461 중복 게시 제거 후), 피어 노드가 추가되면 128 * 4 * 50 = 25600 서브넷으로 증가합니다.

이론적으로 악의적인 블록 제안자가 전체 블록을 게시하지 않고 수직 서브넷에 샘플을 게시할 수 있습니다. 이 상황을 해결하기 위해 우리는 불완전하게 게시된 블록(50% 이상을 사용할 수 있지만 100%는 사용할 수 없음을 의미)이 "자가 치유"할 수 있는 프로세스를 추가했습니다. 프로세스는 세 가지 기본 단계로 구성됩니다.

1. 역 배포: 수직 서브넷의 피어가 해당 수직 서브넷에서 샘플이 속한 blob에 해당하는 수평 서브넷으로 샘플을 전파하는 경우를 제외하고는 위와 동일한 배포 프로세스입니다.

3. 배포: 위의 배포 단계를 반복합니다.

첫 번째 레벨 제목

비콘 체인은 어떻게 작동합니까?

각 슬롯에서 64개의 샤드 각각에 대해 제안자를 무작위로 선택합니다. 제안자는 shard blob을 생성하고 위의 과정을 통해 브로드캐스트하고 blob의 ShardHeader를 글로벌 서브넷에 브로드캐스트할 수 있는 권한이 있습니다. ShardHeader는 비콘 체인의 동일한 슬롯에 패키징할 수 있으며 동일/다음 에포크의 모든 후속 슬롯에 포함될 수도 있습니다.

비콘 체인은 PendingShardHeader 객체 목록을 추적합니다. PendingShardHeader는 다음을 저장합니다. 1) ShardHeader의 주요 정보(샤드 및 슬롯, blob의 약정 및 길이), 2) 임의로 선택된 위원회에서 blob에 서명한 유효성 검사기를 추적하는 비트 필드(실제로는 0단계에서 이미 위원회를 도입했습니다) . AttestationData 구조는 검증자가 투표하도록 선택된 ShardHeader의 루트 해시인 shard_header_root를 포함하도록 확장됩니다. 증명자는 샤드-슬롯 쌍에 할당된 유효하고 사용 가능한 샤드 블롭이 보이지 않는 경우 빈 루트 해시에 투표할 수도 있습니다.

ShardHeader가 위원회 검증인의 2/3에 의해 증명되면 즉시 확정됩니다. 다음 에포크가 끝날 때 샤드헤더가 다른 샤드헤더보다 위원회에서 더 많은 지원을 받는 경우 해당 에포크가 끝날 때 확인됩니다.

포크 선택 규칙

분기 선택 규칙이 변경되어 모든 Blob 또는 해당 조상이 해당 블록에서 가용성 검사를 통과한 것으로 확인된 경우에만 블록이 유효합니다. 이를 긴밀한 결합이라고 합니다. 체인이 유효하지 않은 블롭을 가리키면(확인되면) 전체 체인이 유효하지 않은 것으로 간주됩니다. 이것이 "사이드체인" 구조와의 주요 차이점입니다. 사이드체인에서는 메인체인이 유효한 동안 사이드체인이 실패할 수 있습니다.

다음은 긴밀한 결합과 이것이 왜 중요한지에 대한 추가 탐색입니다.

검증인의 수가 적을 때

검증자가 262144개 미만인 경우(슬롯 32개 * 샤드 64개 * 최소 위원회 크기 128개) 모든 샤드에 대한 제안자를 선택하는 대신 제한된 하위 집합에 대한 제안자를 선택하고 샤드를 반복합니다. 예를 들어 32 * 128 * 50개의 검증자가 있고 슬롯 N의 시작 샤드가 0인 경우 슬롯 N은 샤드 0-49에 제안자를 할당하고 슬롯 N+1은 제안자를 샤드 50-샤드에 할당합니다. 63 및 0-35는 제안자를 할당하고 슬롯 N+2는 제안자를 샤드 36-63 및 0-21에 할당하는 식입니다. 이는 참여율이 낮더라도 위원회의 규모가 적절하게 유지되도록 하기 위한 것입니다.

EIP-1559와 유사한 메커니즘을 추가하여 샤드 데이터를 바이트 단위로 청구하고 가격을 조정했습니다. 블록의 평균 용량이 50%를 초과하면 수수료가 인상되고 그 반대의 경우도 마찬가지입니다. 따라서 지표는 평균 블록 크기의 50%입니다.

첫 번째 레벨 제목

보안 가정

데이터 Blob 전용 샤딩은 다른 샤딩 체계보다 안전 가정에 덜 의존하기 때문에 강력합니다. 특히 정직한 다수 가정(DAS는 다수가 발행한 사용 불가능한 블롭을 감지할 수 있기 때문에) 및 타이밍 가정(이전 DAS 메커니즘과 달리 사기 증명이 아닌 Kate 약속을 사용하므로 사기 증명이 필요하다는 가정에 의존하지 않음)을 피합니다. 매우 빠르게 방송됩니다).

새로운 주요 가정은 "정직한 소수 DAS 가정"입니다. 공격자가 블록의 절반 이상을 게시해야 하는 충분히 큰 노드 샘플이 있습니다. Blob에 2048개의 샘플이 있고 1024개의 샘플을 복구해야 하고(일부 클라이언트가 동일한 포인트를 샘플링하므로 2048 * ln(2) ~= 1419) 각 클라이언트가 20개의 샘플을 수행하는 경우 시스템을 고려할 수 있습니다. 샤드당 약 70개 이상의 클라이언트가 샘플링되는 경우 안전합니다.

첫 번째 레벨 제목

데이터 Blob만 지원하는 샤딩 설계는 향후 샤딩에 실행을 추가하는 많은 시나리오와 호환됩니다. 특히 blob에 사전 및 사후 상태 루트가 포함되도록 체계를 수정할 수 있으며 사기 증명 또는 ZK-SNARK를 사용하여 blob의 상태 전환이 올바른지 확인할 수도 있습니다. 어떤 접근 방식을 선택하든 샤딩 실행의 정확성을 보장하는 것은 정직한 다수의 가정에 의존하지 않습니다.

텍스트

https://github.com/ethereum/eth2.0-specs/pull/2146

공식 계정: ETH 차이니즈 스테이션

Protolambda’s work-in-progress implementation

원본 링크:https://hackmd.io/@HWeNw8hNRimMm2m2GH56Cw/sharding_proposal

ECN의 번역 작업은 중국 이더리움 커뮤니티에 양질의 정보와 학습 자료를 전달하는 것을 목표로 하고 있으며, 기사의 저작권은 원저자에게 있으며, 전재 시 원문의 출처와 ETH 중국 웹사이트를 명시해야 합니다. 장기 재인쇄의 경우 승인을 위해 eth@ecn.co에 문의하십시오.

공식 계정: ETH 차이니즈 스테이션

홈페이지: ethereum.cn