ZK Whiteboard Sessions - Module One 정리

본 문서는 ZK Whiteboard Sessions - Module One을 보고 정리한 문서입니다. zk에 대한 이해가 완벽하지 않아서 잘못 이해하고 작성한 부분이 있을 수 있습니다.

youtube

Google Slide

Definition: SNARK

SNARK: 어떤 명제가 참임을 간결하게 증명 하는 것

zk-SNARK: 어떤 명제가 참인것에 대해 정보를 공개하지 않고 간결하게 증명할 수 있는 것

Applications of SNARKs

• Private Transaction on Public Blockchain
  • Tornado cash, Zash …
• Private Dapps
  • Aleo
• Scalability: 유효성을 갖춘 Rollup 시스템

Arithmetic circuits

• Fix a finite field F = {0, … p-1} for some prime p > 2
• Arithmetic circuit
  • Circuit \(C: F^n \rightarrow F\)
  • 그래프에서 노드가 +, -, x 이며 입력이 1, \(x_1\),…,\(x_n\) 인 directed acyclic graph (DAG)
  • 이는 n차 다항식을 정의 합니다.
  • $|C|=$ number of gates in \(C\)
• Example
  • $C_{hash}(h,m)$: Output 0 if SHA256(\(m\)) = \(h\), and \(\neq 0\) otherwise
  • $C_{hash}(h,m)=$ (\(h\) - SHA256(\(m\))), \(\|C_{hash}\| =\) 20K gates

Argument Systems

• Public arithmetic circuit: \(C:(x,w) \rightarrow F\)
  • $x$: public statement in \(F^n\)
  • $w$: secret witness in \(F^m\)

Non-interactive Preprocessing Argument Systems

• Preprocessing(setup): \(S(c)\) → public parameters \((S_p, S_v)\)

Preprocessing Argument System

• A preprocessing argument system is a triple \((S,P, V)\)
• $S(C)$ → public parameters\((S_p, S_v)\) for prover and verifier
• $P(S_p,x,w)$ → proof \(\pi\)
• $V(S_{v} ,x, \pi)$ → Accept or Reject

Argument System Requirements

Complete: 모든 \(C(x,w) = 0\)을 만족 시키는 \(x,w\)에 대하여 \(V(S_v,x, P(S_p,x,w))\) = accept 일 확률은 1이다.

Knowledge Sound: Verifier가 Proof를 Accepts 했다면 Prover는 \(C(x,w) = 0\) 을 만족시키는 \(w\)을 알고 있다고 할 수 있다.

→ \(P\)가 \(w\)를 모를 때 $V(S_v, x, \pi$)$ = Accept 일 확률은 무시할만큼 낮다

Optional: Zero Knowledge: \((C, S_p, S_v, x, \pi)\) 는 \(w\)에 대한 어떠한 정보도 노출하지 않는다.

Succintness

• SNARK: a Succinct ARgument of Knowledge a succint preprocessing argument system is a triple \((S, P, V)\)
• $S(C)$ → public parameters \((S_p, S_v)\) for prover and verifier
• $P(S_p, x,w)$ → short proof $\pi; |\pi|=0(log(|C|,\lambda)$
• $V(S_v, x, \pi)$ → **fast to verify : $time(V) =0(|x|, log(|C|), \lambda)$

SNARK: \((S, P, V)\) is complete, knowledge sound, succint

zk-SNARK: \((S, P, V)\) is a SNARK and is zero knowledge

Not a SNARK: Trivial Argument System

• Prover sends w to verifier
• Verifier checks if \(C(x,w) = 0\) and accpets if so

Problems with this

• $w$ might be secret: prover는 \(w\)를 공개하길 원하지 않음
• $w$ might be long: 간결한 proof를 원함
• computing \(C(x,w)\) may be hard: 빠르게 검증하기를 원함

Motivating Question: how is \(O(log n)\) Possible?

Types of Setup

$S(C;r)$ → public parameters \((S_p, S_v)\)

$r$: random bits

Types of setup

trusted setup per circuit.: $S(C;r)$ random $r$ must be kept secret from prover

prover learns $r$ → 잘못된 statement에 대해서도 검증 할 수 있게 됨

trusted but universal (updatable) setup: secret \(r\) is independent of \(C\)

transparent setup : \(S(C)\) does not use secret data ( trusted setup 없음 )

SNARK Landscape

SNARK Software Ecosystem

Definition of Knowledge Sound

Goal: If \(V\) accepts then \(P\) knows \(w\) s.t. \(C(x,w) = 0\)

$w$를 안다는것이 무슨 의미일까

Formally: $(S, P, V)$ is knowledge sound for a circuit $C$ if

for event poly. time adversary $A = (A_0, A_1)$ such that

\[ S(C) \rightarrow (S_p, S_v), \] \[ (x,state) \leftarrow A_1(S_p), \] \[ pi \leftarrow A_1(S_p, x, state) : \] \[ Pr[V(S_v,x,\pi) = accept] > 1 / 10^6 (non-negligible) \]

there is an efficient extractor \(E\) (that uses \(A_1\) as a block box) s.t.

\[ S(C) \rightarrow (S_p, S_v), \] \[ (x,state) \leftarrow A_0(S_p), \] \[ w \leftarrow E^{A_1}(S_p,x,state)(S_p, x) : \] \[ Pr[C(x,w)=0] > 1 / 10^6 - \epsilon \] (for a negligible \(\epsilon\))

⇒ Poly. time adversary \(A\)가 정상적으로 state로 부터 proof \(\pi\)를 생성할 수 있다면 \(C(x,w) = 0\)을 만들 수 있는 유효한 witness를 추출할 수 있는 extractor를 갖고 있다고 할 수 있다.

Definition of Zero Knowledge

$(S, P, V)$ is zero knowledge if for every \(x \in F^n\), proof \(\pi\) reveals nothing about \(w\), other than its existence

$(S, P, V)$ is zero knowledge if there is an efficient alg, Sim such that $(S_p, S_v, \pi) ← Sim(C,x)$ look like the real $S_p, S_v$ and $\pi$

Formally: \((S, P, V)\) is zero knowledge for a circuit \(C\)

if there is an efficient simulator Sim such that for all \(x \in F^n\) s.t \(∃ w: C(x,w) =0\) the distribution :

$(C, S_p, S_v, x, \pi):$ where \((S_p, S_v) ← S(C)\), \(\pi ← P(S_p, x, w)\)

is indistinguishable form the distribution :

$(C, S_p, S_v, x, \pi):$ where \((S_p, S_v, \pi) ← Sim(C,x)\)

spin SDK language에 따른 성능 차이 비교

이전에 spin이라고 하는 프레임워크에 대해서 소개해 드린적이 있었습니다.

Spin은 WebAssembly를 이용하여 Microservice를 구현할 수 있는 오픈소스 프레임워크인데 Rust, Go, Javascript/Typescript 등 많은 언어로 SDK가 제작되어 있습니다. 어떠한 언어를 사용하더라도 결국엔 wasm 형식으로 빌드웨어 실행하게 되는데 언어별로 성능에 차이가 있는지 궁금해 졌습니다.

관련해서 discord에 글을 남겨봤는데 아래와 같은 답변을 얻었습니다.

간단하게 JS/TS와 spin사이에 quickjs-wasm 이라고 하는 추가 계층이 존재해서 그 부분에서 성능차이가 날 수 있다고 합니다.

그래서 실제로 차이가 있는지 확인해 보기 위하여 실험을 해 보았습니다.

Performance difference between Rust SDK and Typescript SDK

Rust

Rust는 아래와 같은 코드를 사용하였습니다.

use anyhow::Result;
use spin_sdk::{
    http::{Request, Response},
    http_component,
};

/// A simple Spin HTTP component.
#[http_component]
fn handle_hello_rust(req: Request) -> Result<Response> {
    println!("{:?}", req.headers());
    Ok(http::Response::builder()
        .status(200)
        .header("foo", "bar")
        .body(Some("Hello, Fermyon".into()))?)
}

Typescript

Typescript는 아래와 같은 코드를 사용하였습니다.

import { HandleRequest, HttpRequest, HttpResponse } from "@fermyon/spin-sdk";

const encoder = new TextEncoder();

export const handleRequest: HandleRequest = async function (
  request: HttpRequest
): Promise<HttpResponse> {
  return {
    status: 200,
    headers: { foo: "bar" },
    body: encoder.encode("Hello from TS-SDK").buffer,
  };
};

Benchmark

벤치마킹 툴로는 plow를 사용하였으며 spin application은 로컬 기기인 M1 맥미니에서 구동하였습니다.

아래는 Rust SDK로 빌드한 spin application의 벤치마킹 결과입니다.

아래는 Typescript SDK로 빌드한 spin application의 벤치마킹 결과입니다.

결과적으로 Latency나 RPS(Request Per Second)와 같은 수치가 Rust SDK로 빌드한 spin application이 Typescript SDK를 사용한 그것보다 약 2배 가량의 성능의 차이가 있었습니다.

간단한 Hello world만 출력하는 API에 대해서도 이정도의 차이를 보이게 된다면 더 복잡한 프로젝트에 대해서는 더더욱 차이가 벌어지지 않을까 생각 합니다.

Advent-of-spin 마무리

advent-of-spin이 마무리 되었습니다.

저도 제 블로그에 advent-of-spin Challenge를 진행하면서 수행했던 방법이나 내용들을 공유하고자 블로그에 포스팅을 하였는데요

• Challenge 1
• Challenge 2
• Challenge 3
• Challenge 4
• Challenge 5

이런 것들이 Fermyon 쪽에도 노출이 된건지 Fermyon의 블로그 포스팅에 제 블로그가 실렸습니다.

이제 막 시작한 프로젝트라 크진 않지만 이렇게 공식 블로그에 실리니 기분이 좋네요

소정의 선물도 준다고 하니 선물을 받게 된다면 리뷰도 포스팅 할 예정입니다.

감사합니다 :)

Polkadot 개념 정리 advanced

본 문서는 Polkadot wiki를 읽고 나름대로 정리한 문서입니다. Polkadot에 대한 기본 이해가 부족한 상태에서 읽고 작성한 문서이기 때문에 본문에 오류가 있을 수 있습니다. 실제 문서는 Learn 부터 시작되는 Advanced 부분을 참고하세요.

Accounts

Address Format

Substrate 기반 체인에서는 SS58 기반의 address format을 사용하고 있습니다.

SS58 은 Bitcoin의 Base-58-check를 일부 수정한 버전입니다. 이 형식에는 특정 네트워크에 접속했다는 내용을 포함한 prefix가 포함되어 있습니다.

예를 들어

• Polkadot 주소는 항상 숫자 1로 시작합니다.
• Kusama 주소는 항상 영어 대문자 C, D, F, G, H, J 로 시작합니다.
• 일반적인 Substrate 주소는 항상 숫자 5로 시작합니다.

이러한 주소의 형태는 PublicKey-PrivateKey 쌍을 다르게 표현한 것입니다.

Derivation Paths

동일한 Seed를 사용하여 네트워크에서 여러 계정을 만들고 관리하려는 경우 derivation path를 사용할 수 있습니다. 이는 니모닉 문구를 사용하여 생성된 루트 계정의 하위 계정으로 생각할 수 있습니다.

Polkadot 체인에서 사용할 계정을 만드려는 경우 니모닉 문구 뒤에 //를 사용하여 hard key  child account를 만들 수 있습니다.

'caution juice atom organ advance problem want pledge someone senior holiday very//0'

혹은 / 를 붙여 soft key child account를 만들 수 있습니다.

'caution juice atom organ advance problem want pledge someone senior holiday very/0'

derivation path에 문자나 숫자를 사용할 수 있습니다. 위 예시에는 //0 이나 /0 등 숫자를 사용하였지만 //polkadot 이나 //cute/wisp 등 문자를 사용하거나 여러 path를 결합할 수 있습니다. derivation path를 사용하는 경우 니모닉 문구와 path를 모두 알고있어야 합니다.

니모닉 문구 뒤에 ///를 붙여 password key account를 파생할 수 있습니다.

'caution juice atom organ advance problem want pledge someone senior holiday very///0'

이러한 파생 방식에서는 니모닉 문구가 유출되는 경우 초기 암호 없이 계정을 파생시킬 수 없습니다.

soft, hard derivated account 에서는 니모닉 구문과 path만 알고있으면 계정에 접근할 수 있습니다.

password key account에서는 다른 파생 방법과는 달리 path당 하나의 암호만을 지정해야 합니다.

Soft vs. Hard Derivation

soft derivation을 통해서 파생된 계정의 개인키를 알고 있는 경우 이를 가지고 역추적 하는 경우 초기 계정의 개인키를 알아낼 수 있습니다. 동일한 Seed에서 생성된 다른 계정이 해당 시드에 연결되어 있는지도 확인이 가능합니다.

hard derivation의 경우 파생된 계정의 개인키를 알고있다 하더라도 초기 계정의 개인키를 알아내는것은 불가능합니다.

Advanced Staking Concepts

Staking Proxies

Stash is also Controller

Polkadot에서는 Proxy 계정을 별도로 설정할 수 있습니다. 그 중 스테이킹 관련 액션만 할 수 있도록 권한을 주어 Proxy를 설정할 수도 있습니다.

Staking Proxy가 있는 경우 Stash도 Controller의 역할을 수행할 수 있습니다. Staking Proxy를 변경하기 위해서는 Stash의 서명이 필요합니다.

이 경우에서 Staking Proxy는 모든 스테이킹 관련 액션을 호출할 수 있지만 Balance 관련 Pallet은 호출할 수 없습니다. 이는 Staking Proxy는 Balance를 transfer할 수 없음을 의미합니다.

Stash is not Controller

만약 Stash와 Controller가 다른 계정이라면 Staking Proxy는 추가 스테이킹 및 Controller 변경을 위해 사용됩니다. 따라서 Staking Proxy는 많이 사용되지 않습니다.

이런 구조에서는 스테이킹 작업을 완전히 제어하려면 Staking Proxy, Controller 2개의 계정에 모두 접근할 수 있어야 합니다.

Bags List (voterList)

Polkadot NPoS에서 Nomination 후보들은 bags-list 라고 하는 리스트에 포함됩니다.

Bags List 는 Bags와 Node 2가지의 요소로 구성되어 있습니다. Bags 에는 일정 범위의 스테이킹 된 잔액이 있는 노드가 포함되어 있습니다.

Bags는 Nomination 후보들이 자동으로 투입되지만 지분이 아닌 시간순으로 정렬됩니다.

각 Bag의 아래에서 위로 올라가기 위해서 voterList Pallet에 있는 putInFrontOf 액션을 수행할 수 있다.

위 그림에서 Bag에 아래에 있던 19 DOT 노드에 2개가 추가된다면 1번째 Bag의 맨 위로 이동할 수 있습니다.

만약 스테이킹 보상을 Stash보상으로 보내고 자동으로 스테이킹하기로 결정했다면 Bag내 위치는 자동으로 변하지 않습니다. 이는 Slashing이 발생했을때도 동일하게 적용됩니다. 예를들어 Nominator가 해임되었을 경우에 Bag에서 위치는 변하지 않습니다. 이로인해 Bag에 위치한 노드가 올바른 Bag으로 이동해야 하는 경우가 있을 수 있습니다. 이런 문제를 해결하기 위해 온체인 계정은 voterList Pallet에 rebag 을 호출하여 Bag에 속하지 않은 노드 위치를 업데이트하여 올바른 Bag에 위치시키게 끔 할 수 있습니다.

즉 Token Bonding / Unbonding 같은 액션은 자동으로 rebag 을 실행하지만 스테이킹 보상이나 Slashing 같은 액션은 자동으로 rebag 을 실행하지 않습니다.

Bag List는 체인의 런타임 스토리지에 따라서 무제한의 노드를 포함할 수 있습니다.

Rewards Distribution

Validators 보상은 Staking 양과 관계 없이 동일하게 지급됩니다. 이는 소수의 Validators에게 권한이 집중되는것을 막을 수 있습니다. 장기적으로 보면 Validators는 비슷한 수준의 지분을 가지게 될 것이며 이는 비중이 낮은 Validators를 지원한 Nominator은 더 많은 위험을 감수한 만큼 더 많은 보상을 받을 수 있게 됩니다.

Nominator에게 보상을 분배하기 전에 Validator는 Nominator와 분배되지 않는 보상인 커미션을 생성할 수 있습니다. 이는 블록 보상의 백분율 입니다.(일정 퍼센트 지정 가능) 커미션이 공제된 후 나머지 금액은 Staking에 따라 Nominator와 Validator에게 분배됩니다.

Validator가 가질 수 있는 Nominator수 에는 제한이 없지만 보상을 받을 수 있는 Nominator수는 제한이 있습니다. 이는 현재 256개로 되어 있지만 런타임 업그레이드를 통해 수정될 수 있습니다. Nominator들 중 Staking에 따라 상위 256명 까지만 보상을 받습니다.

Slashing

Unresponsiveness

모든 세션에 대해서 validators는 heartbeat를 보내 온라인임을 나타내야 합니다. validators가 epoch동안 블록을 생성하지 않고 heartbeat가 실패한다면 응답하지 않는것으로 간주합니다. 이런 행동이 반복되면 Slashing 처리가 될 수 있습니다.

Equivocation

GRANDPA: validators가 다른 체인의 동일한 2라운드에서 2개 이상의 vote에 서명한 경우

BABE: validators가 Relay chain의 동일 slot에서 2개 이상의 블록을 생성한 경우

이 경우 Slashing이 될 수 있습니다.

Slashing Across Eras

nominator는 여러 validator에 지원을 할 수 있으며 이들로 인해 Slashing 될 수 있습니다. Slashing 될 떄 일정 기간동안 받을 수 있는 Slashing중 가장 큰 건에 대해서만 Slashing 됩니다

Simple Payouts

Polkadot에서 이전 era의 보상을 받기 위해서 트랜잭션을 제출하여야 합니다. 이는 모든 Staker 들이 단일 블록에서 보상을 받는것이 아닌 다른 시간에 트랜잭션을 날리게 하여 자연스럽게 보상을 분배하기 위함힙니다.

Polkadot은 최근 84 era를 저장하고 있습니다. 보상은 이 84 era가 지나면 청구할 수 없습니다. 즉 모든 보상은 이 기간 이내에 청구하여야 합니다. validator가 자신의 stash를 죽이면 보상을 더이상 수령할 수 없습니다. 이를 수행하기 전에 먼저 validating을 중지한 다음 stash에 있는 자금을 언스테이킹 해야 합니다.

거래 수수료를 지불할 의향이 있는 누구나 Vaildator에 대한 보상 트랜잭션을 날릴 수 있습니다.

Inflation

DOT은 인플레이션이 발생합니다. DOT은 발행 상한이 존재하지 않습니다. 인플레이션은 매년 10%입니다. Vaildator 보상 이외의 자금은 Treasury로 이동합니다.

네트워크가 유지하고자 하는 이상적인 스테이킹 비율이 있습니다. 시스템은 이상적인 스테이킹 비율을 유지하고자 합니다. 이상적인 스테이킹 비율은 Parachain의 수에 따라 다릅니다.

스테이킹된 토큰 양이 이상적인 비율보다 낮아지면 Nominator에 대한 스테이킹 보상이 증가하여 더 많은 스테이킹을 유도하고 반대로 이상적인 비율을 초과한다면 스테이킹 보상이 떨어집니다.

Availability and Validity

Phases of the AnV protocol

Availability 과 Vaildity 프로토콜에는 5단계가 있습니다.

1. Parachain phase.
2. Relay Chain submission phase.
3. Availability and unavailability subprotocols.
4. Secondary GRANDPA approval validity checks.
5. Invocation of a Byzantine fault tolerant finality gadget to cement the chain.

Parachain phase

AnV의 Parachain phase는 collator가 Validator에게 블록 후보를 제안하는 단계입니다.

Relay Chain submission phase

validators는 블록 후보를 확인합니다. 확인이 완료되었으면 validators는 후보 블록을 다른 validators에게 전달합니다. 검증에 실패하였다면 그 후보 블록은 즉시 거부됩니다.

validators는 각각의 Parachain에 대한 할당을 결정하고 후보 블록에 대한 승인을 결정하고 무효 후보 블록에 대해서 처리를 해야합니다. 각각의 모든 validator가 모든 parachain 후보를 검증할 수 없기 때문에 parachain 후보를 선택하기 위해서 정직한 validator가 선택되도록 해야합니다.

정직한 validator가 승인된 유효하지 않은 블록을 발견한다면 악의적인 validator에게 처벌을 유발하는 dispute를 제시해야 합니다.

validators의 절반이상이 블록 후보에 대해서 승인한다면 candidate receipt를 발행합니다. 이는 결국 Relay Chain State에 포함될 것입니다. 이는 아래와 같은 내용을 포함하고 있습니다.

• The parachain ID.
• The collator’s ID and signature.
• A hash of the parent block’s candidate receipt.
• A Merkle root of the block’s erasure-coded pieces.
• A Merkle root of any outgoing messages.
• A hash of the block.
• The state root of the parachain before block execution.
• The state root of the parachain after block execution.

Availability and unavailability subprotocols

validators는 erasure coded pieces를 네트워크에 퍼뜨립니다. 적어도 validators중 1/3 + 1은 자신의 code word를 소유하고 있음을 알려야 합니다.

Erasure Codes

Erasure coding은 메시지를 더 긴 코드로 변환하여 코드의 하위집합에서 원본 메시지를 복구할 수 있도록 합니다

Code는 복구할 수 있도록 원문 메시지에 패딩값을 추가한 메시지 입니다. Polkadot의 availability scheme에서 사용되는 Erasure code 유형은 Reed-Solomon codes로 이는 많은곳에서 사용되고 있습니다.

Polkadot에서 erasure codes는 모든 Validator가 모든 Parachain에 대해서 항상 검증하지 않아도 Parachain State를 시스템에 서 사용할 수 있도록 유지하는 역할을 합니다. 대신 validators는 더 작은 code 조각을 공유하고 validators중 1/3 +1 이 이를 제공할 수 있다 전체 데이터를 구성할 수 있게 됩니다.

Cross-Consensus Message Format (XCM)

XCM(Cross-Consensus Message Format)은 consensus systems간 통신을 목표로 합니다.

Polkadot은 상호운용성을 지향하고 있으며 XCM은 이를 구현하기 위한 수단입니다.

아래의 수단들을 가능하게 하는 VM과 함께 제공됩니다.

1. Asynchronous: XCM 메시지는 보낸 사람이 메시지 전송을 완료했을때 차단할 것이라 가정하지 않습니다.
2. Absolute: XCM 메시지는 순서대로 전달됨을 보장합니다.
3. Asymmetric: XCM 메시지에는 보낸 사람에게 메시지를 정상적으로 수신했다는 알람을 줄 수 없습니다. 이 같은 행동을 구현하려면 별도로 메시지를 보내주어야 합니다.
4. Agnostic: XCM은 메시지가 전달되는 시스템의 Consensus에 상관없이 동작합니다.

A Format, Not a Protocol

XCM은 실제 시스템간 메시지를 보낼 수 없습니다.

UDP와 비슷하게 응답으로 설계된 XCM 메시지가 없다면 XCM은 자동으로 응답을 보내주지 않습니다.

Asset Teleportation

1. InitiateTeleport

   Source는 전송하려는 계정에서 자산을 빼냅니다.

2. ReceiveTeleportedAsset

   Source는 ReceiveTeleportedAsset 라는 XCM 메시지를 자산의 양과 수신 계정을 포함하여 생성합니다. 이 메시지를 Destination으로 보내면 새 자산이 Destination에 투입됩니다.

3. DepositAsset

   Destination은 수신 계정에 자산을 예치합니다.

Reserve Asset Transfer

Consensus System에 자산을 전송할 수 있는 계층이 없는경우 신뢰할 수 있는 다른 엔티티를 선택할 수 있습니다.

1. InitiateReserveWithdraw

   Source는 송금 계정에서 이체할 자산을 모아서 소각하고 이를 기록합니다

2. WithdrawAsset

   Source는 예약을 위해 WithdrawAsset 명령을 보내고 sovereign account에서 소각한 양만큼을 예약합니다.

3. DepositReserveAsset

   Reserve는 이전에 이체된 양만큼 Destination의 sovereign account에 예치를 예약합니다.

4. ReserveAssetReposited

   Reserve는 ReserveAssetDeposited 명령을 정해진 자산 만큼을 포함해서 보냅니다. Destination 은 이를 받아서 처리합니다. 이는 Destination 쪽에서 신규 발행이 될 것 입니다.

5. DepositAsset

   Destinationdms 신규 발행된 양을 수금 계정에서 수신합니다.

XCM Tech Stack

XCVM (Cross-Consensus Virtual Machine)

XCM의 핵심에는 XCVM이 존재합니다. XCM의 메시지는 XCVM의 프로그램 입니다. XCVM은 state machine이며 state는 레지스터에서 추적됩니다.

Cross-Consensus Protocols (XCMP, VMP, HRMP)

XCM 형식이 설정되면 메시지의 프로토콜에 대한 공통 패턴이 필요합니다. Polkadot은 Parachain간에 XCM 메시지를 작용하기위한 2가지 메시지 전달 프로토콜을 사용합니다.

XCMP (Cross-Chain Message Passing)

REST - RESTful 관계처럼 XCM - XCMP 관계가 이루어집니다.

Cross-chain Message Passing은 두 Parachain간 안전한 메시지 전송을 가능하게 합니다.

이는 2가지 방법이 있습니다

• Direct: 메시지가 Parachain간 다이렉트로 전송됨
• Relayed: 메시지가 Relay Chain을 통해서 전송됨

VMP (Vertical Message Passing)

Relay Chain과 Parachain간 메시지 전송에서는 두 경우 모두 Relay chain에 메시지가 존재하게 됩니다.

• UMP (Upward Message Passing) Parachain에서 Relay Chain으로 메시지 전송
• DMP (Downward Message Passing) Relay Chain에서 Parachain으로 메시지 전송

HRMP (XCMP-Lite)

XCMP가 구현되는동안 HRMP라고 하는 임시 프로토콜을 사용합니다.

XCMP와 동일한 인터페이스와 기능을 가지고 있지만 Relay Chain Storage에 모든 메시지를 저장하기 떄문에 더 많은 리소스를 요구합니다.

Cryptography

Hashing Algorithm

Polkadot은 Hash 알고리즘으로 Blake2b를 사용하고 있습니다.

Keypairs and Signing

Polkadot은 Key derivation 및 signing 알고리즘으로 x25519(sr25519)를 사용하고 있습니다.

Sr25519는 Ed25519와 동일한 커브인 Curve25519를 기반으로 하고 있습니다. 하지만 EdDSA대신 Schnorr 서명을 사용하고 있습니다.

Keys

Account Keys

계정 키는 아래 중 하나일 수 있습니다.

• Ed25519
• sr25519
• secp256k1

“Controller” and “Stash” Keys

Controller 키는 사용자가 직접 제어할 수 있는 키이며 트랜잭션을 제출하는데 사용됩니다. 이는 Controller 키를 이용하여 Validating 혹은 Nomination을 시작하거나 정지함을 의미합니다. Controller 키는 수수료를 지불하기 위해 약간의 DOT을 보유해야 하며, 대량의 금액을 보유하고 있기에 적합하지 않습니다.

Stash 키는 콜드 월렛이 되는 키 입니다. 인터넷에 노출되거나 트랜잭션을 제출하는데 사용되지 않습니다. Stash 키는 오프라인 상태로 유지되므로 자산이 특정 Controller에 Bond 되도록 설정 해야합니다.

Session Keys

Session 키는 Validator가 네트워크 작업을 수행하기 위해 온라인 상태로 유지해야하는 키 입니다. Session 키는 자산을 통제하기 위한것이 아니며 의도된 목적으로만 사용하여야 합니다. Controller는 Session 공개키에 서명하여 인증서를 만들고 외부에 이 인증서를 전파하면 됩니다.

Polkadot은 6개의 Session 키를 사용하고 있습니다.

• Authority Discovery: sr25519
• GRANDPA: ed25519
• BABE: sr25519
• I’m Online: sr25519
• Parachain Assignment: sr25519
• Parachain Validator: ed25519

NPoS Election Algorithms

Validator의 보상이 각 era 마다 거의 균등하게 지급되기 때문에 각 Validator의 지분이 균일하게 분산되는것이 중요합니다. NPoS 알고리즘은 아래 값을 최적화 하려고 시도합니다.

• 총 스테이킹 양을 극대화
• 최저 스테이킹 Validator의 값을 극대화
• 스테이킹의 Variance를 최소화

What is the sequential Phragmén method?

Validator Elections

sequential Phragmén은 NPoS에서 Validator을 선출하는데 사용됩니다. 이는 각 투표시마다 Validator의 비중을 균등하게 합니다.

Council Elections

sequential Phragmén은 Council 선출에도 사용됩니다.

Understanding Phragmén

Basic Phragmén

Rationale

기본적인 Phragmén을 알아야 합니다.

후보자그룹, 경쟁자그룹, 투표자그룹이 있어야 합니다. 또한 모든 투표자는 동일한 투표권이 있다고 가정합니다.

Algorithm

기본적인 Phragmén은 다음 규칙을 반복하면서 한 자리씩 선택합니다.

1. 유권자는 본인이 지지하는 후보자에게 투표합니다.
2. 각 투표마다 초기 로드를 0으로 설정합니다.
3. 다음 자리를 차지할 후보는 투표의 평균 로드가 가장 작은 후보입니다.
4. 당선 후보를 선택한 n개의 투표용지에 로드를 1/n을 추가합니다.
5. 이번 라운드의 승자를 지지한 모든 투표용지의 평균을 내어 균등하게 합니다.
6. 선택해야 할 자리가 더 있으면 3번으로 돌아가 이를 반복합니다.

Weighted Phragmén

Rationale

Polkadot 에서 Validator, Council 투표는 모두 유권자가 보유한 토큰 지분에 따라 가중치가 부여됩니다.

Algorithm

1. 후보자는 한 라운드당 한명씩 선출되어 successful candidate에 추가됩니다.

2. 후보자가 선출이 되면 가중치 맵핑이 구축되어 각 Nominator가 선택한 Validator의 가중치를 정의합니다.

3. 모든 투표자는 자신의 스테이킹 금액, Validator의 목록을 작성합니다.
4. 유권자 → 후보자의 초기 edge-weighted 그래프를 생성합니다. 여기서 edge 가중치는 유권자가 보유하고 있는 투표의 가중치입니다. 후보에 대한 모든 잠재적 가중치의 합을 approval_stake라고 합니다.
5. 후보 선출을 시작합니다. 선출되지 않은 모든 후보는 1/approval_stake 를 획득합니다.

6. 각 유권자에 대해 유권자의 자산에 로드율을 곱한다음 후보의 approval_stake 로 나누어 각 후보의 점수를 업데이트합니다.

   (voter_budget * voter_load / candidate_approval_stake).

7. 점수가 가장 낮은 후보를 결정하고 그 후보를 선출합니다.
8. 선출된 후보에 연결되는 각 edge의 가중치는 후보 점수에서 유권자의 가중치를 뺀 값으로 설정된 edge 가중치로 업데이트 하고 유권자의 가중치는 후보 점수로 설정됩니다.
9. 선출할 후보가 더 있으면 3단계 / 아니면 8단계로 이동합니다.
10. 이제 stake는 적어도 한명의 선출된 후보를 지지한 Nominator에게 분배됩니다. 각 후보에 대한 지지 지분은 유권자의 예싼에 edge 부하를 곱한다음 후보 부하로 나누어 계산합니다. (voter_budget * edge_load / candidate_load).

Randomness

Polkadot은 VRF를 사용합니다.

VRF

VRF는 제출자가 난수를 생성했다는 진위 증명과 함께 일부 입력을 받아 난수를 생성하는 연산입니다. 난수 생성이 유효한지 확인하기 위해 모든 도전자가 증명을 확인할 수 있습니다.

슬롯은 길이가 6초인 시간 단위입니다. 각 슬롯에는 블록이 포함될 수도 있고 아닐 수도 있습니다. 슬롯은 epoch를 구성합니다. Polkadot에서는 2400개의 슬롯이 하나의 epoch를 만들고 4시간동안 Epoch를 만듭니다.

모든 슬롯에서 각 Validator는 주사위를 굴리고 그 아래를 입력으로 하는 VRF를 실행합니다.

• 주사위를 굴릴 때 사용한 Secret Key
• epoch randomness value
• slot number

으로 RESULT 와 PROOF 가 출력됩니다. 그러나음 프로토콜 구현에서 정의된 임계값과 비교 합니다. 값이 임계값보다 작으면 주사위를 굴린 Validator가 블록 생성 후보가 됩니다.

그 다음 Validator는 블록 생성을 시도하고 이전에 얻은 RESULT, PROOF 를 네트워크에 제출합니다. VRF에서 모든 Validator는 스스로 주사위를 굴리고 임계값과 비교하여 임계값 미만인경우 블록을 생성합니다.

RANDAO

온 체인에서 Randomness를 얻는 다른 방법은 이더리움의 RANDAO 입니다.

RANDAO는 각 Validator가 seed에 대해서 해시를 수천번 계산하여 획득합니다.

Validator는 마지막 해시값을 가져다가 난수로 사용합니다.

SPREE

Shared Protected Runtime Execution Enclaves (SPREE) 는 “Trust wormhole” 이라고 불리는 Substrate의 런타임 모듈과 유사한 logic fragments입니다.

하지만 이는 Polkadot Relay Chain에 상주하여 Parachain에 의해 선택될 수 있습ㄴ디ㅏ.

• Parachain은 스마트 컨트랙트와 같이 특별한 runtime logic fragments을 선택할 수 있습니다.
• 이러한 fragments 는 자기 자신의 스토리지와 XCM endpoint를 가지고 있습니다
• Parachain의 모든 인스턴스는 동일한 Logic을 갖습니다.
• 이는 Parachain Login과 함께 실행됩니다.
• 저장소는 Parachain logic으로 변경될 수 없습니다. 메시지는 Parachain에 의해 변경될 수 없습니다.

Origin

처음에는 SmartProtocol 이라고 하는 아이디어로 시작 하였습니다. 이 개념의 핵심은 XCMP가 신뢰 없이 Parachain에서 실행되었음을 증명하기 어려움을 해결하고자 각 Parachain과의 인터페이스를 통해서만 변경할 수 있는 인스턴스당 자체 저장소가 있는 Relay Chain에 SmartProtocol을 설치하는 것 이었습니다.

What is a SPREE module?

SPREE 모듈은 커버넌스 메커니즘이나 Parachain을 통해 Polkadot에 업로드되는 논리 조각입니다. (정확하게는 blobs fo WebAssembly Code) Blob이 Polkadot에 업로드 되면 다른 모든 Parachain 이 로직을 적용하도록 결정할 수 있습니다. SPREE 모듈은 Parachain과 독립적인 자체 스토리지를 가지고 있지만 Parachain과의 인터페이스를 통해서 호출할 수 있습니다.

SPREE 모듈은 대상이 되는 Parachain에서 실행될 코드를 보장하기 때문에 XCMP 아키텍쳐에서 중요합니다. XCMP는 메시지 전달을 보장하지만 어떤 코드가 실행되는지, 즉 받는 쪽에서 어떻게 이를 이해하는지 보장하지 않습니다.

Why

XCMP에서 Parachain을 통해 메시지를 보내는것은 메시지가 전달 되는것을 보장할 뿐 실행되는 코드나 받는 Parachain에서 메시지를 해석하는 방법을 지정하지 않습니다.

SPREE는 SPREE 모듈과 Parachain간 동일한 logic이 공유되는데 도움이 되도록 합니다.

Staking Miner

Polkadot 에서 각 era가 끝날때 NPoS를 사용하여 Nominator의 투표에 따라 새로운 Validator 세트를 선출해야 합니다. 이 솔루션을 계산하기 위해서 mining 이라는 용어를 사용합니다.

Validator는 off-chain worker를 사용하여 결과를 계산하고 트랜잭션을 제출합니다. 이런 역할도 off-chain의 다른 프로그램에서 작업을 위임할 수 있습니다.

Staking miner들은 해당 Validator set에 대하여 지분 분배 및 솔루션이 얼마나 최적인지를 나타내는 점수로 구성된 선거 솔루션을 생산하기 위해 서로 경쟁합니다.

Staking miner들은 주어진 스테이킹 알고리즘을 실행하여 생성한 결과를 Relay Chain에 트랜잭션으로 전송합니다. 여기서 수수료를 가장 적게 사용하는 솔루션이 최상의 솔루션으로 책정되어 보상이 주어집니다.

WebAssembly

Polkadot 및 Substrate에서는 WASM을 사용함으로써 하드포크 없이 런타임 로직을 업그레이드 할 수 있습니다.

Polkadot 개념 정리 basics

본 문서는 Polkadot wiki를 읽고 나름대로 정리한 문서입니다. Polkadot에 대한 기본 이해가 부족한 상태에서 읽고 작성한 문서이기 때문에 본문에 오류가 있을 수 있습니다. 실제 문서는 Learn 부터 시작되는 Basics 부분을 참고하세요.

Introduction

Polkadot은 최초의 Fully-sharded Blockchain 입니다.

Polkadot은 sharded model 이라고 하는 네트워크 모델을 사용하고 있습니다.

Polkadot에는 시스템의 메인 체인처럼 동작하는 Relay Chain 이 있으며 WASM으로 컴파일 되고 Relay Chain API를 지원한다면 Polkadot에 Parachain 으로 붙어 동작할 수 있습니다.

Polkadot은 Bitcoin, Ethereum 등 체인과 양방향 상호작용을 위한 Bridge Parachain도 존재합니다. 이는 다른 Parachain간 트랜잭션 전송을 가능하게 합니다.

XCM (Cross-Consensus Messaging Format) 을 사용하여 서로 다른 Parachain간 메시지를 보낼 수 있습니다.

Accounts

Polkadot Accounts

Account는 Public, Private 부분으로 나누어져 있다.

Address는 Public한 부분이며 Key는 Private한 부분이다.

Polkadot은 Ed25519 Sr25519 secp256k1 커브를 지원한다.

Polkadot은 Multisig-account / anonymous proxy를 지원한다.

대부분의 Wallet은 니모닉 구문을 지원하며 아래와 같은 모습을 보인다.

'caution juice atom organ advance problem want pledge someone senior holiday very'

Secret seed (Private key): 0x056a6a4e203766ffbea3146967ef25e9daf677b14dc6f6ed8919b1983c9bebbc
Public key (SS58): 5F3sa2TJAWMqDhXG6jhV4N8ko9SxwGy8TpaNS1repo5EYjQX

Polkadot 기본 Address format은 MultiAddress 타입으로 이는 같은 니모닉구문으로 다른 Parachain에서 키를 생성할 수 있음을 의미합니다.

Polkadot은 여러 유형의 Balance가 있다.

• transferrable: 자유롭게 송금할 수 있는 잔액
• vested: 특정 시간에 정해진 일정에 따라 릴리즈 되는 토큰, 즉 잠겨있지만 특정 블록 수 이후에 해금됨
• locked: bonded,democracy, vested 중 가장 큰 잔액
• reserved: bonded,democracy, vested 이외의 목적으로 동결된 토큰 수
• bonded: 스테이킹을 위해 잠겨진 토큰
• redeemable: 잠금 해제가 가능하도록 준비된 토큰
• democracy: 온체인 참여를 위해 잠겨진 토큰

계정을 생성할 때 처음엔 오직 키만 생성하며 온체인에 등록되지 않습니다. 온체인에 등록하기 위해서 1 DOT을 예치하여야 합니다.

만약 예치금이 1 DOT 이하로 떨어지면 게정은 체인에서 삭제되지만 다시 해당 금액 이상으로 예치한다면 계정을 다시 사용할 수 있습니다.

Polkadot에 내장된 Identities Pallet 을 사용하면 계정에 대한 메타데이터를 등록할 수 있습니다.

Account Generation

-

Balance Transfers

Transfer를 수행할 수 있는 2가지 옵션이 존재

• transfer keep-alive : 예치금 (1 DOT) 미만 으로 송금하는걸 허용하지 않음
• transfer : 무시하고 보낼 수 있지만 예치금 미만으로 잔액이 떨어지면 계정이 회수됨

Extrinsics

Polkadot은 Substrate 를 이용하여 구축되었습니다.

Substrate는 Pallets라고 하는 모듈과 기타 라이브러리등을 제공합니다.

pallet에 권한이 있는경우 그 안에 포함된 기능을 호출하고 실행할 수 있습니다.

Extrinsics 은 3가지 타입이 존재합니다.

• signed transactions: 요청 보내는 계정의 서명이 포함된 트랜잭션
• unsigned transactions: 서명이 없기때문에 제출한 유저에 대한 정보가 없음
• inherents: 블록을 구축하는데 필요한 정보를 전달하는 블록 작성자가 만든 서명되지 않은 트랜잭션

Multi-signature Accounts

Substrate 기반 체인에서는 Multisig 계정을 생성할 수 있습니다. 이러한 Multisig는 하나 이상의 주소와 threshold로 구성됩니다.

Multi-signature accounts는 생성 된 이후에 수정될 수 없습니다. 구성원이나 임계값을 변경하기 위해서는 다중 서명을 해체하고 새로운 다중 서명을 생성해야 합니다.

Multisig로 수행할 수 있는 작업은 3가지가 있습니다.

• asMulti: 다중서명 트랜잭션을 시작하거나 종료
• approveAsMulti: 트랜잭션을 승인하고 다음 서명자에게 넘김
• cancleAsMulti: 취소함

Proxy Accounts

Proxy Account는 다른 계정을 대신해서 기능을 수행할 수 있습니다.

Proxy account는 proxy pallet를 통해서 설정할 수 있습니다. proxy type은 다음과 같습니다.

• Any: 모든 거래 수행 가능
• Non-transfer: transfer를 제외한 모든 기능 수행 가능
• Governance: governance 관련 트랜잭션만 수행할 수 있도록 허용
• Staking: staking 관련 트랜잭션만 수행할 수 있도록 허용
• Identity Judgement: 계정 생성을 위한 신원에 대해 판단만 가능
• Auction: Parachain 경매 및 기타 트랜잭션만 허용

Proxy를 생성하기 위해서 토큰을 예치해야 합니다. (모든 peer에 복제되어야 하기때문에 스토리지를 사용하게 되므로 보증금 필요)

Time-delay를 제공하여 보안을 높일 수 있습니다. 이 시간 안에 프록시가 수행한 작업을 취소할 수 있습니다.

Anonymous proxy는 기본 계정에 의해서 생성되었지만 할당되진 않은 새 계정 입니다. 그리고 기본 계정은 Anonymous proxy를 대신하여 프록시의 역할을 합니다. 여기서 Anonymous proxy와 기본계정간 관계가 끊어지면 더이상 Anonymous proxy에 접근할 수 없습니다.

Tokens and Assets

Assets

Statemint Parachain은 Polkadot 네트워크에서 자산의 생성, 관리, 사용을 전문으로 하는 데이터 구조를 포함하고 있습니다.

Fungible Assets

10 DOT을 예치할 수 있다면 누구나 Statemint parachain에서 자산을 생성할 수 있습니다. 자산을 생성할 때 생성자는 자산을 식별하기 위해 unique한 u32 타입은 AssetId를 지정 해야 합니다.

Asset에는 여러가지 권한을 포함하고 있는데 아래와 같다

• Owner: 다른 세 가지 역할을 하는 계정을 설정하고 자산에 대한 메타데이터를 설정할 수 있다.
• Issuer: 토큰을 발행 및 소각할 수 있다.
• Admin: 강제 이체 및 계정을 동결 및 동결해제 할 수 있다.
• Freezer: 자산을 동결할 수 있다.

Statemint는 approve_transfer, transfer_approved, cancel_approval 인터페이스를 제공합니다. 이 인터페이스를 사용하여 사용자가 계정을 대신해서 transfer를 할 수 있도록 권한을 줄 수 있습니다.

Statemint는 reserve-backed 시스템을 이용하여 다른 Parachain간 자산 전송을 관리한다.

Non-Fungible Assets

Statemint의 Uniques pallet는 NFT를 나타냅니다.

100 DOT을 예치할 수 있다면 누구나 자산을 생성할 수 있습니다. 거버넌스가 free holding 으로 거버넌스를 설정하지 않으면 예치금이 필요합니다.

생성자는 자산을 식별하기 위해 위의 AssetId 와 유사한 역할을 하는ClassId 를 설정하여야 합니다.

또한 Fungible Assets과 마찬가지로 owner, Issuer, admin, freezer 권한을 설정할 수 있습니다.

NFT 자산에서는 메타데이터를 가질 수 있는데 이 메타데이터에는 IPFS 해시값 등의 메타데이터를 설정할 수 있습니다.

NFT 에서도 FT와 마찬가지로 approve_transfer, transfer_approved, cancel_approval 인터페이스를 사용하여 권한을 위임할 수 있습니다.

DOT

DOT은 Polkadot 네트워크에서 사용되는 Native Token 입니다.

가장 작은 단위를 Planck라고 하며 0.0000000001 DOT 입니다.

DOT은 크게 3가지의 사용처를 가집니다.

• 네트워크의 거버넌스에 참여하기 위함
• 네트워크 운영을 위한 스테이킹
• parachain으로 polkadot에 체인을 연결하기 위해

Statemint

Statemint는 일반적인 자산(FT, NFT)에 대한 기능을 제공하는 Parachain 입니다.

Teleporting Assets

asset teleportation이란 자산을 다른 체인(Parachain) 간 이동하는 프로세스를 의미합니다.

• Initiate Teleport 보내는 계정에서 teleport할 자산을 기록하여 꺼냅니다.

• Receive Teleported Assets 보내는 쪽은 XCM의 ReceivedTeleportedAssets 을 통해 보내는 양 및 받는 계정을 포함하는 파라미터를 생성합니다.

• Deposit Assets 받는 쪽에서 받는 계정으로 자산을 예치시킵니다.

Compoments

Architecture

Components

• Relay Chain
  • Polkadot의 중앙 체인
  • 모든 Validator는 Relay Chain에 DOT을 스테이킹을 필요로 한다.
  • 거버넌스 매커니즘, Parachain 경매, NPoS에 참여하는 등 적은수의 트랜잭션으로 구성되어 있다.
  • Relay chain은 최소한의 기능만 가지고 있습니다.
  • Smart Contract는 지원하지 않고 있으며 이는 다른 Parachain에 위임하고 있다.
• Parachain and Parathread Slots
  • Polkadot은 Parachain, Parathread 의 2가지 모델을 사용하고 있다.
  • Parachain에는 체인 전용 슬롯이 있어 지속적으로 실행되는 프로세스와 같으며
  • Parathread는 그룹간 슬롯을 공유하여 잠깐 실행되는 프로세스와 비슷합니다.
  • Parachain은 validators가 검증할 수 있는 Proof를 생성해야한다는 제약 이외에 다른제약은 없다.
  • 이 Proof은 Parachain의 State Transition을 검증합니다.
  • Parathread는 Parachain과 동일한 API를 사용합니다.
  • Parachain은 DOT을 스테이킹 해놓아야 하고, parathread는 블록 당 사용료를 지불해야 합니다.
  • Parachain은 Parathread가 될 수 있으며 역도 가능합니다.
• Shared Security
  • Relay chain에 붙는 모든 Parachain은 Relay chain의 Security를 공유합니다.
  • Polkadot은 Relay chain 및 모든 연결된 Parachain에 대해서 shared state를 가집니다.
  • Relay chain을 이전으로 되돌린다면 붙어있는 Parachain 또한 되돌아갑니다. 이는 전체 시스템에 대한 유효성이 지속되고 개별 부분이 손상되지 않도록 하기 위함입니다.

Interoperability

• XCM
  • Cross-Consensus Message
  • Protocol이 아닌 Format
  • 메시지의 구조화만 정의하고 있음
  • XCM 형식은 Parachain이 서로 통신할 수 있게 하는 메시지 포맷
  • XCMP는 이를 전달하는 매커니즘
• Bridges
  • 임의의 데이터를 네트워크에서 다른 네트워크로 전송할 수 있는 통로
  • 브릿지를 통해서 다른 네트위크는 상호 운용 가능하지만 각각 규칙이나 거버넌스를 독립적으로 가져갈 수 있습니다.
  • Polkadot 에서 Bridge는 Relay Chain에 연결되어 Collator가 유지관리하는 Polkadot 컨센서스에 의해서 관리됩니다.

Main Actors

• Validators
  • Validator가 Validator set으로 선출되면 Relay chain에서 블록을 생성합니다.
  • Collator로 부터 Proof를 승인 받으면 보상을 받습니다.
• Nominators
  • 특정 Validator에게 스테이킹 지분을 지원하여 Validator가 받는 보상을 일부 받습니다.
• Collators
  • Relay Chain, Parachain 양쪽 모드에서 Full node이다.
  • Parachain의 트랜잭션을 수집하여 Relay chain의 Validator을 위한 Proof를 생성합니다.
  • parachain 블록은 Collator가 생성하지만 Relay chain에서 Validator은 유효성 검증만 한다

Collator

Collator는 Parachain 트랜잭션을 수집하고 State Transition Proof를 만들어 Relay chain validators에게 전달합니다.

Collator는 Parachain의 트랜잭션을 통해서 Parachain 블록을 구성하고 이 블럭을 기반으로 State Transition Proof을 만들어 Validator에게 제공함으로써 Parachain을 유지합니다.

Collator는 Parachain과 Relay Chain에 대해서 Full node를 유지해야 합니다.

Collator는 네트워크를 보호하지 않습니다. Parachain Block이 Invalid 하다면 그것은 Validator에 의해 거부될 것입니다.

State Transition Proof 가 2/3 이상의 Validator에 의해서 승인되었다면 그것은 backable 한것으로 간주합니다.

Validators는 아래 순서대로 검증을 수행해야 합니다.

• Candidate(State Transition Proof)는 persisted validation data의 매개변수를 초과하면 안된다.
• Collator의 서명이 검증되어야 한다.
• Parachain Runtime을 실행함으로써 Candidate를 검증한다.

Candidate 가 위의 조건을 충족한다면 선택된 Relay Chain block author가 각 Parachain의 backed Candidate 를 골라 Relay Chain Block에 포함시킨다.

XCM

Collator은 XCM의 핵심 요소 입니다.

Collator는 모든 프로세스가 끝날때 까지의 모든 트랜잭션을 수집합니다. 그 이후 Collator는 Parachain Block Candidate에 서명하고 State Transition Proofs를 생성합니다. Collator는 Candidate Block + State Transition Proofs 를 validators에 전달하고 validators는 Candidate Block 내 트랜잭션들을 검증합니다. 검증이 완료되면 Candidate Block를 Relay chain에 전송합니다.

Consensus

Nominated Proof of Stake

Pool을 온체인으로 구현하여 토큰 보유자가 자신을 대표할 수 있는 Validator에게 투표할 수 있도록 합니다.

Polkadot은 이러한 Validator set을 선택하는 매커니즘으로 NPoS(Nominated Proof-of Stake)를 사용합니다. Validators는 BABE에서 새로운 블록을 생성하고 Parachain을 검증하는 역할을 수행합니다.

Polkadot의 컨센서스 프로토콜에는 2가지 프로토콜이 사용됩니다. (GRANDPA, BABE)

Polkadot은 하이브리드 컨센서스를 사용하는데 하이브리드 컨센서스에서는 블록 생성 프로세스에서finality 부분을 분리합니다.

BABE(Blind Assignment for Blockchain Extension)

BABE는 validator와 새로운 블록의 author 사이에서 동작하는 블록 생성 메커니즘 입니다.

BABE는 지분에 따라서 validator에게 블록 생성 슬롯을 할당합니다.

BABE의 실행은 epoch라고 하는 단계에서 이루어 집니다. 각 epoch는 미리 정의된 수의 슬롯으로 나뉘어 각 epoch의 모든 슬롯은 0부터 순차적으로 인덱싱 됩니다. 각 epoch가 시작될 때 BABE 노드는 Block-Production-Lottery 알고리즘을 실행하여 어느 슬롯에서 블록을 생성할지 결정하고 다른 블록 생성자에게 알립니다.

Validators는 모든 슬롯에 대한 추첨에 참여하며 각 슬롯에 대해 블록 생성자 후보 여부를 알려줍니다.

슬롯은 길이가 대략 6초인 개별 시간 단위입니다. Validators에게 슬롯을 할당하는 메커니즘은 랜덤을 기반으로 하기 때문에 여러 Validators가 동일한 slot의 후보가 될 수 있으며 slot이 비어있을 수 있어 블록시간이 항상 일정하지 않을 수 있습니다.

• Multiple Validators per Slot 특정 슬롯에서 여러 Validators가 블록 생성자 후보로 있는 경우 모두가 블록을 생성하고 이를 네트워크에 브로드캐스팅 합니다. 여기서 먼저 네트워크에 도달한 Validators가 최종적으로 선정됩니다.
• No Validators in Slot 슬롯에 Validators가 없는경우 백그라운드에서 RR Validators Selection 알고리즘이 실행되어 Validators가 선정되어 블록을 생성합니다.

GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement)

GRANDPA는 Polkadot Relay Chain에 구현되는 finality gadget 입니다.

Polkadot 호스트는 GRANDPA를 사용하여 블록을 Finality 합니다. Finality는 Validator 노드의 투표에 의해 부여되며 Validator는 블록 생성과 이를 병행하여 실행합니다.

2/3 이상의 Validator가 특정 블록을 포함하는 체인을 검증하는 순간 해당 블록까지의 모든 블록이 한번에 Finalize 됩니다.

BEEFY (Bridge Efficiency Enabling Finality Yielder)

Polkadot 네트워크와 다른 블록체인 (Ethereum과 같은) 간 효율적인 브릿지를 지원히기 위한 GRANDPA의 보조 프로토콜 입니다. 이 프로토콜을 통해서 다른 네트워크에 있는 참여자들이 Polkadot Relay Chain의 Validator가 생성한 Finality Proof를 검증할 수 있습니다.

Governance

Referenda

Referenda는 간단한 Stake 기반의 투표 방식입니다. 각각의 referendum는 런타임에서 함수 호출의 형태를 하는 제안을 가지고 있습니다.

Referenda는 투표를 할 수 있는 정해진 기간이 있으며 투표가 승인되면 해당 함수의 호출이 이루어 집니다. 투표시 선택할 수 있는 옵션은 찬성, 반대, 기권입니다.

Referenda는 여러 방식으로 시작할 수 있습니다.

• 공개적으로 제출된 제안
• 과반수 이상의 동의로 Council에서 제출된 제안
• prior referendum 제정의 일환으로 제출된 제안
• Technical Committee가 제출하고 Councli이 승인한 긴급제안

누구나 최소한의 토큰을 예치 하는것으로 referendum를 제안할 수 있습니다. 누군가 제안에 동의한다면 동일한 양의 토큰을 예치할 수 있습니다. 예치금액이 높은 제안이 다음 투표에 안건으로 선정됩니다.

예치된 금액은 제안이 표결에 부쳐지면 락이 해제됩니다. 제안 대기열에는 최대 100개의 공개 제안이 있을 수 있습니다.

Unanimous Council - Council의 모든 멤버가 제안에 동의하면 전체투표로 옮길 수 있습니다.

Majority Council - Council의 과반수가 동의하는 경우 전체투표로 옮길 수 있습니다.

긴급 투표가 진행 중인 경우를 제외하고 활성화된 전체투표는 하나만 존재할 수 있습니다.

대기열에 제안이 존재하는 한 28일마다 새로운 Referenda가 활성화 됩니다. 대기열은 Council에서 승인된 제안을 위한 대기열이있고 공개적으로 제출된 제안에 대한 대기열 2가지가 존재합니다. Referenda는 두 대기열의 최우선순위가 번갈아 가면서 진행됩니다.

상위 제안은 Stake 양에 따라서 정해집니다. 두 대기열중 최상위 제안 중 Stake가 많이 되어있는 제안이 우선순위로 선정됩니다.

Referenda에 투표하기 위해서 voter는 투표 종료시 까지 토큰에 대해 Lock을 걸어야 합니다.

Example:

Peter: Votes No with 10 DOT for a 128 week lock period => 10 x 6 = 60 Votes

Logan: Votes Yes with 20 DOT for a 4 week lock period => 20 x 1 = 20 Votes

Kevin: Votes Yes with 15 DOT for a 8 week lock period => 15 x 2 = 30 Votes

집계 방식은 총 3가지 시나리오가 있을 수 있습니다.

• Public - Positive Turnout Bias (Super-Majority Approve)
• Council ( Complete ) - Negative Turnout Bias (Super-Majority Against)
• Council ( Majority ) - Simple Majority

투표 결과를 적용하기위해 아래 공식중 하나를 적용합니다.

Super-Majority Approve

Super-Majority Against

Simple Majority

approve - the number of aye votes

against - the number of nay votes

turnout - the total number of voting tokens (does not include conviction)

electorate - the total number of tokens issued in the network

Polkadot은 Holder가 자발적으로 토큰을 잠글 수 있는 기간을 선언하여 투표권을 높일 수 있습니다.

총 6단계로 설정되며 각 기간은 28일입니다.

Adaptive Quorum Biasing 라는 개념을 도입하여 명확한 다수가 없는경우에 제안이 통과되는것을 더 쉽게 혹은 더 어렵게 만드는데 효과적인 절대 다수를 변경하는데 사용할 수 있는 레버 역할을 합니다.

이미지를 예시로 들면 Turnout 25%의 경우 투표율이 25%이며 Positive Turnout Bias를 적용했을 경우 66%의 찬성을 받아야 합니다. 반대로 투표율이 75%일 경우 54%의 찬성을 획득하면 됩니다.

Negative Turnout Bias를 적용할 경우 투표율이 25%일때 찬성이 34%를 획득하면 되고 투표율이 75%일 경우 46%의 찬성을 받으면 됩니다.

Council

Council은 온체인 계정으로 구성된 엔티티입니다. Council는 13명의 구성원으로 구성되어 있습니다.

Council은 합리적인 투표를 제안하는것, 악의적인 제안으 취소하는것, 기술위원회 선출등의 임무룰 수행합니다.

기술위원회가 만장일치로 승인하거나, Roo가 Cancel을 트리거하는경우 제안은 취소될 수 있습니다. 취소된 제안의 보증금은 소각됩니다.

또한 Council의 2/3 이상의 찬성으로 referendum을 취소할 수 있습니다.

제안은 Root에 의해서 블랙리스트에 오를 수 있습니다. 블랙리스트와 관련된 제안은 즉시 취소됩니다. 또한 블랙리스트에 오른 제안의 해시는 대기열에 다시 등록할 수 없습니다.

모든 Holder는 Council 후보에 자유롭게 등록할 수 있습니다. Council 선거는 Validator를 선정하는 로직과 동일한 로직으로 처리됩니다. Council의 임기는 1주일간 지속됩니다.

매 임기 말에 선거 알고리즘이 실행되고 모든 Voter들은 새로운 councillors를 투표합니다.

Technical Committee

Technical Committee는 악의적인 referendum으로 부터 보호하고 버그 수정을 구현하고 잘못된 업데이트를 되돌리거나 새로운 기능을 추가하는 역할을 합니다.

Technical Committee의 멤버는 Council에서 과반수의 투표로 구성원을 더하거나 제할 수 있습니다.

Technical Committee는 Democracy Pallet를 사용하여 제안을 빠르게 추적할 수 있는 권한이 있습니다.

Governance V2

v2에서 변경사항은 아래와 같습니다.

• Council의 역할을 democracy vote를 통해 토큰 홀더들에게 이전
• Council 해산
• 사용자가 투표를 위임할 수 있는 더 많은 방법을 허용

v2에서 누구나 언제든지 referendum를 원하는만큼 여러번 수행할 수 있습니다. v2에서는 Origins 및 Tracks 라는 새로운 개념이 도입되었습니다.

Origin은 각 referendum class와 연결되고 각 클래스는 Track과 연결됩니다. Track은 해당 제안의 lifecycle을 표시하며 다른 클래스의 Track과 독립적입니다.

v2에서 referendum이 생성되면 커뮤니티에서 즉시 투표할 수 있습니다. 그러나 referendum이 종료할 수 있는 상태에 있지 않을 떄 약식으로 제정됩니다. 여러 기준을 충족하기 전까지 미정 상태로 남아 있습니다.

• lead-in period - 결정을 하기 전 경과해야 하는 시간입니다.
• 결정을 위한 공간이 있어야합니다.
• Decision Deposit이 지불되어야 합니다.

v2에서는 제안이 승인될 수 있는 28일이 주어집니다. 이 기간 동안 승인되지 않으면 제안은 자동으로 거부됩니다.

v2에서는 adaptive quorum biasing이 사라집니다.

Approval은 승인 투표 가중치 / 총 투표 가중치 로 정의됩니다.

Support는 승인 투표 수 / 시스템 총 투표수 로 정의됩니다.

확인 기간동안 최소한의 기준을 충족하여야 합니다. 다른 Track는 다른 확인 기간 및 다른 Approval, Support 기준을 가지고 있습니다.

v2에서는 Cancelation 이라고 하는 특수한 액션이 있습니다. 이는 이미 투표중인 제안에 대해서 즉시 거부할 수 있습니다.

v2에서는 Technical Committee를 대체하기위해 Polkadot Fellowship가 도입되었습니다.

Polkadot Fellowship은 기존 Technical Committee와 달리 훨씬 광범위하고 진입장벽이 낮게 설계되었습니다. Polkadot Fellowship의 후보가 되기 위해 소액의 토큰을 예치할 수 있습니다. Polkadot Fellowship 구성원은 Polkadot Fellowship의 제안에 대해 투표할 수 있습니다. Polkadot Fellowship내에 사용되는 제안에 대한 메커니즘은 referendum에 사용되는 매커니즘과 동일합니다.

Identity

Polkadot은 온체인에 개인정보를 추가할 수 있고 이를 등록기관에 확인을 요청할 수 있는 naming system을 제공합니다.

사용자는 이름, Website 등 사용자 지정 필드를 등록하여 Identity를 설정할 수 있습니다.

사용자는 자신의 정보를 온체인에 저장하기위해 자금을 예치해야 합니다. 이는 항목이 삭제되면 반환됩니다.

사용자는 자신의 정보를 온체인에 등록한뒤 등록기관에 판단을 요청할 수 있습니다. 사용자는 판단에 대해 지불할 용의가 있는 최대 수수료를 설정하고 등록기관은 판단을 해줄 수 있는 최소금액을 지정합니다.

등록기관은 판단을 내릴때 최대 6단계의 신뢰도를 선택할 수 있습니다.

등록기관이 되기 위해서 Democracy에 제안을 제출한 다음 투표를 기다려야 합니다.

Nominator

Nominators는 Relay Chain의 validators를 선택합니다.

validators를 선택하면 validators가 받는 보상을 일부 나눠 받을 수 있습니다.

Polkadot Host

Polkadot의 아키텍쳐는 Runtime과 Host 두 부분으로 나눌 수 있습니다.

Polkadot Runtime은 체인의 코어 로직이 포함되어 있으며 하드포크 없이 업그레이드 할 수 있습니다.

Polkadot Host는 Runtime을 실행하기 위한 환경입니다.

Polkadot Host는

• Libp2p와 같은 네트워크 컴포넌트
• State Storage
• Consensus Engine ( GRANDPA, BABE )
• WASM Interperter and VM
• Low Level Primitives ( Such as Crypto )

로 구성되어 있습니다.

Runtime Upgrades

Polkadot 온체인에 저장된 로직을 업그레이드 하여 런타임을 업그레이드할 수 있습니다.

Transaction Fees

Relay Chain의 수수료는 3가지 변수에 의해서 지정됩니다.

• Weight Fee
• Length Fee
• Tip

수수료의 일부는 블록 생성자에게 전달되고 나머지는 Treasury로 전달됩니다.

Polkadot의 블록은 Maximum Weight, Maxinmum Length가 지정되어 있습니다. 블록 생성자는 트랜잭션들을 블록에 해당 제한을 초과히지 않도록 채워야 합니다. 블록 생성자는 블록에 최대 75%만 채우며 25%는 체인 운영과 관련된 트랜잭션을 위해 예약되어 있습니다.

Polkadot의 수수료는 3가지로 구성됩니다.

• Base Fee: Runtime에 의해 고정된 매 트랜잭션에 대해 발생하는 수수료
• Length Fee: 트랜잭션의 길이에 따라 부과되는 수수료
• Weight Fee: runtime function의 가중치마다 부과되는 수수료

fee = base_fee + length_of_transaction_in_bytes * length_fee + weight_fee

Polkadot은 네트워크가 너무 바쁘면 트랜잭션에 추가 수수료를 부과할 수 있습니다.

final_fee = fee * fee_multiplier

Polkadot의 샤드 (Parachain, Parathread) 내에서 발생되는 거래에 대해서는 Relay Chain 수수료가 발생하지 않습니다.

Treasury

Treasury는 block production rewards, transaction fees, slashing, staking inefficiencies 등 자금을 모아둔 버켓입니다.

Treasury에 보관된 자금은 Council에서 승인한 경우 대기기간에 들어가는 지출 제안을 작성하여 사용할 수 있습니다. 이 대기 기간을 지출 기간이라고 하며 거버넌스에 따라 다르지만 현재 24일로 설정되어 있습니다. Treasury는 자금이 부족하지 않은 상태를 유지하면서 대기열에 있는 최대한 많은 제안을 시도하려 합니다.

Treasury가 자금이 고갈 된 상태에서 승인된 제안이 남아있다면 이는 승인된 대기열에 저장되며 다음 지출 기간에 자금 집행이 이루어 집니다.

StakeHolder가 Treasury 에서 지출을 제안하려는 경우 지출의 최소 5%를 예치해야 합니다.

Treasury는 아래의 방법으로 자금을 조달합니다

• Slashing: validator가 어떤 이유로든 Slashing 되었다면 제보자에게 보상과 함께 해당 자금은 Treasury로 보내집니다.
• Transaction Fee: 수수료중 일부는 Treasury에 들어오며 일부는 블록 생성자에게 보상으로 주어집니다.
• Staking inefficiency: 인플레이션은 첫해 10%로 설계되었으며 이상적인 스테이킹 비율은 50%입니다. 즉 모든 토큰의 절반이 스테이킹 되어야 합니다. 이 비율에서 벗어나게 되면 이에 비례하는 인플레이션 비율이 Treasury에 전송됩니다.
• Parathread: Parathread는 블록에 포함되기 위하여 경매에 참여합니다. 입찰금액의 일부는 Validator로 전달되며 나머지는 Treasury에 전송됩니다.

Creating a Treasury Proposal

제안자는 스팸 방지로 최소 100 DOT 혹은 요청 금액의 5%를 예치하여야 하며 최대 한도는 500 DOT입니다. 이 금액은 제안이 거부되면 소각되거나 환불됩니다.

제안이 제출된 이후에 사용자는 이를 철회할 수 없습니다.

Bounties Spending proposals은 큐레이터라고 하는 전문가에게 버그 또는 취약점 수정, 전략 개발, 모니터링 등을 목표로 하는 제안입니다.

제안자는 Council에서 통과할 수 있도록 제안을 제출할 수 있으며, 이후 큐레이터를 지정할 수 있으며 제안이 통과되면 큐레이터는 예치금을 일부 예치해야하며 이는 큐레이터가 악의적으로 행동할 경우 처벌이 될 수 있습니다. 바운티 작업을 성공적으로 완료하였다면 예치금과 바운티 보상의 일부를 받을 수 있습니다.

Validator

Validator는 Collator의 Proof을 검증하고 다른 Validators와 합의에 참여하여 Relay Chain을 보호하는 역할을 수행합니다.

Validators는 Relay chain에 새로운 블록을 추가하는 역할을 합니다.

Staking

Introduction to Staking

Nominated Proof-of-Stake (NPoS)

Polkadot은 Nominated Proof-of-Stake (NPoS)을 구현하였습니다. 모든 유저는 validators 후보가 될 수 있습니다. validators 후보는 Nominator에 공개되며 Nominator는 차례로 최대 16명의 후보를 선택하여 제출할 수 이습니다.

Polkadot에서 사용하는 선거 알고리즘은 Phragmen와 같은 Proportional Justified Representation에 기반을 두고 있습니다.

active set of validators가 활동하는 24시간의 기간을 ear라고 합니다.

각 ear는 6개의 epoch로 나뉘며 각 epoch동안 validators는 특정 슬롯에 블록 생성자로 할당됩니다.

블록을 생성하는 validators는 토큰을 보상을 받을 수 있고 이를 nominator와 나눌 수 있습니다.

validators와 nominators 모두 ear가 끝날 떄 스테이킹 보상을 받을 수 있습니다. 이는 스테이킹 수량에 관계없이 균등하게 지급됩니다.

Slashing

Slashing은 validator가 네트워크 상에서 잘못된 행동을 했을때 발생합니다. validator와 그의 nominators 이 같이 Slashed 되며 Staking한 DOT은 모두 손실됩니다. 여기서 손실된 DOT은 Treasury로 귀속됩니다.

Chilling

Chilling은 validator이나 nominator가 사임하는 행위입니다. 이는 validator이나 nominator 양쪽 모두 수행할 수 있으며 다음 era부터 적용됩니다.

validator가 Chilling을 수행했을 경우 nominator를 잃지 않습니다.

Polkadot은 현재 297개의 Validator가 있습니다. 상한은 아직 정해져있지 않지만 네트워크 대역폭 등에 부담이 될 수 있어 제한 되어야 합니다.

안정기에는 약 1000개의 Validator가 될 것으로 예측 됩니다.

Nomination Pools

Key Compoments

• Bonded Pool: actively staked funds의 분배를 추적
• Reward Pool: actively staked funds로 획득한 보상을 추적
• Unbonding Sub Pools: 각각 다른 phases의 lifecycle에서의 풀의 모음
• Members: Pool에 Nominate된 계정
• Point: Pool에 대한 각 멤버들의 비중

Pool Member Lifecycle

Join a pool

Pool에 들어가기 위한 최소 예치금은 1 DOT입니다. 사용자는 한번에 하나의 Pool에만 속할 수 있습니다.

Claim rewards

사용자는 이전 보상 청구한 시점부터 누적된 보상을 청구할 수 있습니다.

Unbond and withdraw funds

Pool에 가입한 후 언제든지 예치금을 빼는것으로 Pool에서 탈퇴할 수 있습니다.