ICMP 대기열 라우팅을 위한 간단한 가십 프로토콜

새로운 트리 구조(잎) B

노드(피어) k의 새로운 체인 블록 헤더 선언

모듈 t의 k가 켜져 있습니다 큐 메시지 m

〖허용〗_k(m)의 피어 레이어 노드(피어) k 정의

• 주기적으로

• 향후 개선

Polkadot 네트워크에서 일부 엔터티(엔티티)에 정보를 제출해야 합니다.먼저 이러한 엔터티의 유형을 간단히 정리하겠습니다: (1) 사용자, (2) 수집자, (3) 검증자

런타임 시 파라체인에 대한 모든 정보는

이 후보 소스는 파라체인 후보 블록을 검증하여 생성되며 릴레이 체인 블록에 포함됩니다. 후보자는 분야가 많습니다. 다음은 몇 가지 관련 항목입니다.

송신 루트:

릴레이 체인 블록 B가 파라체인 p에 포함될 때 고유한 파라체인 y와 쌍을 이루는 각 해시 값은 R(E_(p,y)^B)입니다.

수신된 데이터가 parachain p에 대한 것일 때, 새로운

값. 런타임은 가장 가까운 parachain의 후보 체인에서 받은 값을 현재 값으로 간주합니다. 후보를 포함하는 모든 블록에서 B의 원래 값은 최소한 워터마크 p의 이전 값만큼 높아야 합니다.

(rob: 빈 목록에서 비어 있지 않은 보류 중인 이그레스는 허용되지 않음)

검증자와 콜렉터 모두 블록 B에 대한 블록 큐 정보 수집을 시도하거나 검증자가 〖Ingress〗_(B,P)를 호출하여 전파 풀에서 관련 메시지를 검색하고 아직 릴리스되지 않은 메시지를 기다립니다. P에 대한 결합기의 목표는 P_INGRESS(B,P)의 접두사를 가능한 한 많이 얻기 위해 릴레이 체인 부모 B를 구축하는 것입니다.

R(P_INGRESS (B,가장 쉬운 방법은 를 사용하는 것입니다. 메시지는 한 파라체인 네트워크에서 다른 네트워크로 전달됩니다. 메시지를 브로드캐스팅하는 이 두 네트워크 사이에 공통 노드가 있는 경우 메시지는 메시지를 수신하는 병렬 링크가 메시지를 수신하도록 합니다. 그러나 대상 파라체인의 검증자가 메시지가 파라체인의 수신자에게 전파되지 않았다는 것을 알게 되면 메시지를 보낸 파라체인의 검증자 노드에서 메시지를 다시 요청한 다음 해당 메시지를 수신하게 됩니다. 전파하는 장치.

P))는 런타임에 모든 블록 B와 파라체인 p에서 사용할 수 있습니다.

파라체인 p와 블록 B의 가용성은 p와 B가 해당 블록에 대한 보류 중인 유입 루트의 유입 목록이고 각 목록과 루트가 먼저 라우팅된 블록 번호와 쌍을 이룬다는 사실에 기인합니다. Ingress 목록에서 R(∅)을 생략하고 빈 목록을 생략하고 블록 번호 오름차순으로 정렬합니다. 여기서 모든 블록 번호는 num(B)보다 작고 동일한 체인의 블록을 참조합니다.

RUST의 의사 코드(TODO: Transcribe to LaTeX)

지정된 B 및 p에 대한 송신 대기열의 데이터는 빈 목록의 순서 지정 및 생략과 같은 수신 목록과 동일한 제약 조건에 따라 런타임에 계속 사용할 수 있습니다. 여기서 ParaId는 수신 체인이고 진입(ingress) 기능에서는 송신 체인입니다.

트리 구조가 블록을 릴레이 체인의 최신 파라체인 블록으로 남겨둔다고 가정해 봅시다.

우리는 노드에 대해 다음과 같은 가정을 합니다.

1. 트리 구조의 끝에 있는 리프의 블록 상태는 가능하지만 이전 블록의 상태는 보장할 수 없습니다.

2. 파라체인의 콜레이터와 풀 노드는 파라체인에서 실행된 모든 블록을 유지할 것으로 예상할 수 있습니다.

3. 유효성 검사기는 블록을 유지할 필요가 없습니다. 또한 유효성 검사기가 저장한 삭제 코드 스니펫에서 정보를 복구할 수 있습니다.

이 장에서는 ICMP 메시지의 대기열을 전파하기 위한 제한된 가십 프로토콜을 설명합니다(정의는 개요 참조).

그리고

그리고

ingress가 블록 B에서 호출되었으므로 쉽게 넣을 수 있습니다.

변환하다

메시지는 비라우팅 상태에서 시작하여 라우팅 상태에서 끝납니다.

우리는 가십 전파 시스템을 정의할 것을 제안합니다.

이 모듈에 대한 메시지는 다음과 같은 형식입니다.

우리는 지역 정보를 다음과 같이 유지합니다.

1. 〖잎〗_k는 코드를 실행해야 하는 DAG 블록 트리 구조의 끝점(잎)에 대한 최고의 해시 함수 목록입니다.

2. 〖leaves〗_k, 각 피어 k에 대해 가장 최신 목록은 블록의 코드 MAX_CHAIN_HEADSDAG 해시 값을 실행해야 합니다(그들이 우리에게 보낸 내용에 따라)

3. leafTopics(l)→{queueTopic(h)}는 모든 트리 구조(리브)에서 트리 노드 l의 병렬 체인에 있는 확장되지 않은 루트 h를 의미합니다.

4. expectedQueues(t)→H는 모든 호출 모듈의 해당 해시 루트의 파생 과정을 나타내며, 모든 항목에서 t∈∪l_(∈leaves)leafTopics(l)

새로운 트리 구조(잎) B

1. 트리 구조(리프), 트리 모듈(leafTopics) 및 예상 대기열 업그레이드(벤치마크 테스트는 수행되지 않았지만 보수적인 추정은 실행 시간이 100ms임)

2. 같은 레이어의 새로운 트리 구조(잎) 보내기

3. 병렬 체인 p의 수집기가 egress(B,p) 온라인 코드를 실행하면 전파되지 않은 알려진 메시지 대기열 루트에 대해 해당 대기열 메시지를 전파 풀에 넣습니다.

노드(피어) k의 새로운 체인 블록 헤더 선언

1. 트리 구조(잎) 〖잎〗_k 업그레이드

2. ∀H∈leaves ∩ 〖leaves〗_k의 요구 사항을 충족하기 위해 broadcastTopic(k,t)의 각 t는 leafTopics(H)에 매핑됩니다.

모듈 t의 k가 켜져 있습니다 큐 메시지 m

우리는 기능을 정의

현지 현지 신뢰 표준(현지 승인 기준)으로.

메시지의 해시 루트

expectedQueues(t) 정의된 함수에서 주어진 메시지의 실제 루트는 루트와 같습니다.

함수 good(m)이 k가 양수임을 증명하면 m을 전파 풀에 넣고, 그렇지 않으면 m을 사용할 수 없음을 증명하여 동료 집합 배양에 유용합니다.

〖허용〗_k(m)의 피어 레이어 노드(peer) k 정의 및 모듈 t의 Queue 메시지 m

메시지 전송이 완료되기 전에 메시지 k가 전송되면 메시지 k는 거부되어야 합니다. 반대로 다음과 같은 경우

∃l∈leaves∩〖〖leaves〗_k|t∈leafTopics(l)∃l∈leaves∩〖leaves〗_k |t∈leafTopics(l)이면 메시지 k가 허용되고 다른 방법은 금지됩니다.

주기적으로

expectedQueues를 제외하고 모든 모듈을 만료된 모듈로 표시하고 전파 풀에서 지워야 합니다. 실제로 이러한 작업은 몇 초마다 수행됩니다. 이렇게 하면 전파 풀이 무한정 커지는 것을 방지할 수 있습니다.

라우팅되지 않은 메시지를 현재 모드와 동일한 보기를 공유하는 피어에게만 전파하기로 한 결정은 논란의 여지가 있을 수 있지만, 우리가 제시한 전제 조건 중 일부는 이 점을 아주 잘 설명합니다.

첫째, 우리는 노드가 무한한 수의 메시지를 처리해야 하는 것을 원하지 않습니다. 즉, queueTopic(H)의 H는 이러한 H가 무한하기 때문에 노드에 알려지지 않습니다. 둘째, 노드는 특정 피어에게 메시지를 전파할지 여부를 결정하기 위해 많은 작업을 수행할 필요가 없습니다. leaves∩〖leaves〗_k=∅라고 가정하고 〖leaves〗_k의 일부 항목은 leaf의 소스 코드입니다.

(선조). 우리는 증명하기 위해 O(n)에서 모든 l ∈ 〖leaves〗_k를 실행해야 합니다. 그런 다음 주어진 메시지가 이전 블록에서 언라우팅되었는지 여부를 파악해야 합니다. 우리는 메시지가 이전 체인에서 라우팅되는 대신 동일한 체인의 일부 나중 블록에서 여전히 라우팅되지 않는 경우 그럴 가능성은 없지만 체인 상태가 인간 노드에서 피싱 롤백일 수 있다고 순진하게 생각합니다.

가정된 체인 상태는 이전 블록에서 사용할 수 없기 때문에 이전 블록의 피어에 실제로 egress를 보낼지 여부를 결정할 좋은 방법이 없습니다. 향후 개선 섹션에서는 고정된 수의 원본(상위)으로 확장하여 이 제한을 완화하는 방법에 대해 논의할 것입니다.

그럼에도 불구하고 다음을 가정하여 동일한 체인에 동기화된 노드(피어)로 전파하는 것이 합리적입니다(일부는 경험적이지만 합리적이지만 과대 평가될 가능성도 있음).

1. 새로운 유효 블록은 최소 5초의 평균 간격으로 발행됩니다(우리의 목표는 실제로 10-15초입니다).

2. 가십 전파 구조의 "유용한" 부분에서 블록의 전파 시간은 2초 이내입니다.

3. 가십 전파 구조에서 인접한 주제는 500ms 이하의 지연이 있습니다.

4. DAG 헤드와 동기화하기 전에 메시지를 의미 있게 전파하는 것은 가치가 없을 수 있습니다.

실제 값은 거의 확실하게 더 나을 것입니다. 좋은 소식은 모든 블록이 한 블록 시간 내에 전파될 필요는 없다는 것입니다. 시간이 지남에 따라 참가자가 더 일찍 메시지를 받을 수 있게 됩니다. 모든 참가자가 모든 메시지를 볼 수 있는 체계입니다. 그것은 소수의 초기 체인 이상으로 확장되지 않을 것이 거의 확실하지만 대신 시작 프로토콜로 기능적으로 작동합니다.

보조 제목

XCMP 라우팅 개요

설정에 따라 하나의 파라체인(전송 파라체인)에서 다른 파라체인(수신 파라체인)으로 메시지를 보내려면 다음 단계를 수행합니다.

보내는 파라체인의 전체 노드가 받는 파라체인 도메인의 일부일 때 메시지가 충분합니다.

수신한 Parachain의 Parachain Validator는 메시지 전파 여부를 확인하지 못하고, 보내는 Parachain의 Parachain Validator에게 직접 메시지를 요청합니다(실시간 PV 전송). 보내는 파라체인의 PV는 메시지를 사용할 수 있도록 유지하는 역할을 합니다. 파라체인을 보내는 파라체인 검증자는 메시지를 받는 파라체인의 PoV로 직접 보내고, 최종적으로 받는 파라체인의 PV는 받는 파라체인 네트워크의 메시지에 가십(gossip)을 퍼뜨린다.

보조 제목

향후 개선

1. 위 섹션에서는 egress 큐를 피어 레이어까지 임의로 전파하는 것이 나쁜 생각인 이유를 설명하지만 일단 동기화하고 정상적인 블록 생성을 따르면 모든 트리를 합리적으로 추적할 수 있습니다. 최종 소스 코드(조상) α의 구조(나뭇잎). α의 초기 합리적인 값은 부모의 값과 일치해야 하며 1을 취합니다. 트리 세트 교차가 필요할 때 "stutter"가 발생하고 두 피어가 새 하위 키에 대한 정보로 서로를 업데이트해야 하기 때문에 필요한 이득의 90%를 얻을 수 있습니다.

2. E_(x,y)^B의 정의를 확장하면 체인 간 상호 검사가 가능합니다. 예를 들어 파라체인 y는 블록 B에서 x의 메시지를 라우팅하지 않도록 릴레이 체인에 지시할 수 있습니다(그리고 나서 블록 B'에서 다시 라우팅을 시작하도록 지시할 수 있습니다). B와 B' 사이의 모든 블록에 대해 CandidateReceipt에서 b의 x를 무시할 때 E_(x,y)^b=∅를 실행하는 실행 시간이 있습니다. 사실, 런타임은 해시 루트 해시만 처리하기 때문에 후보 영수증에서 R(E_(x,y)^b)를 무시하고 R(∅)로 설정합니다.

3. 모든 사람이 모든 것을 볼 수 없는 더 스마트한 토폴로지를 지원하도록 확장합니다. 어쩌면 두 종류의 주제 배열(주제), (B, (B,〖chain〗_from)) 기반 주제 배열(주제) 및 (B,〖chain〗_to) 기반 모드가 있으면 이 모드의 사용성이 향상될 것입니다.https://github.com/sipa/minisketch4. 일종의 스마트 설정 조정을 사용합니다(예: