자료 : SoK: Sharding on Blockchain
지난 포스트 - SoK: Sharding on Blockchain 4
3 SHARDING OVERVIEW 본문
3 SHARDING OVERVIEW
3.1 Problem Definition
Assume that there exist n participating nodes having the same computational power, a fraction f of which is con- trolled by a Byzantine adversary. The network accepts trans- actions per block, e.g., a transaction i in block j is repre- sented by an integer xij ∈ ZN , where ZN [38] is the ring of integers modulo N . All nodes have access to an externally- specified constraint function C : ZN → {0, 1} to determine the validity of each transaction. The sharding protocol is to seek a protocol Π running between nodes which out- puts a set X which contains k separate “shards" or subsets Xi = {xij }(1 ≤ j ≤ |Xi |) such that the following conditions hold: • Agreement. Honest nodes agree on X with a probability of at least 1 − 2−λ , for a given security parameter λ. • Validity. The agreed shard X satisfies the specified con- straintfunctionC,e.g.,∀i∈{1...k},∀xij ∈Xi,C(xij)=1. • Scalability. The value of k grows almost linearly with the size of the network. The goal of sharding is to split the network into multiple committees, each processing a separate set of transactions (e.g., Xi ) called a shard, and the number of shards k grows near linearly on the size of a network. Each shard needs to get an agreement localized within a small committee, which makes the consensus procedure more efficient. Typically, the computation and bandwidth used per node stay constant regardless of n and k. For instance, in blockchain, once the network agrees on the set X , it can create a cryptographic digest of X and form a hash-chain with previously agreed sets in the previous runs of Π, which serve as a distributed ledger of transactions.
3.2 Sharding Overview
Typically, the sharding protocol proceeds in epochs, each of which decides on a set of values X = 2s X where 2s i=1 i is the number of subsets Xi . The key idea is to automati- cally parallelize the available computation power, dividing it into several smaller committees, each processing a disjoint set of transactions or shards. We take Elastico [100] as an example. The number of committees grows proportionally to the total computation power in the network. All com- mittees, each of which has a small constant number c of members, run a classical BFT consensus protocol internally to agree on one block. For a decentralized system, it needs first to define the membership, and there exist several ways to resolve a membership, e.g., proof-of-work (PoW) [62], proof-of-stake (PoS) [87], proof-of-storage [142], and proof- of-personhood [24]. A permissionless sharding protocol typ- ically consists of five critical components in each consensus round.
1). Identity establishment and committee formation. To join in the protocol, each node needs to establish an identi- tye.g., an identity consisting of a public key, an IP address and a proof-of-work (PoW) solution. Each node then is assigned to a committee corresponding to its established identity. In this process, the system needs to prevent the Sybil iden- tity [60]. However, for a permissioned blockchain, it does not require this process. 2). Overlay setup for committees. Once the committees are formed, each node communicates to discover the identities of other nodes in its committee. For a blockchain, an overlay of a committee is a fully connected subgraph containing all the committee members. Typically, this process can be done with a gossip protocol [70]. 3). Intra-committee consensus. Each node within a com- mittee runs a standard consensus protocol to agree on a single set of transactions. In this process, all honest members must agree on the proposed block within its committee. 4). Cross-shard transaction processing. The transaction should be atomically committed in the whole system. For cross-shard transactions, the related shards need to get con- sistency. Typically, this process requires a kind of “relay" transaction to synchronize among related shards. 5). Epoch reconfiguration. To guarantee the security of the shards, the shards need to be reconfigured, requiring a randomness. This randomness will be used for the next epoch. The above five points are the most critical components for a permissionless blockchain sharding.
To design a sharding protocol, it needs to deal with several key challenges. The first challenge is how to uniformly split all nodes into several committees so that each committee has the majority honest with high probability. Good randomness is a critical component to partially address this challenge, which provides high-entropy output [49]. However, achiev- ing good randomness in a distributed network is a known hard problem. Section 5 will provide a detailed discussion on epoch randomness. The state-of-the-art solution can only tolerate a small fraction of maliciousness (e.g., 1/6), with excessive message complexity [7]. Typically, the adversary is not static and can adaptively observe all the protocol runs. The second challenge is how to guarantee that the adversary does not gain a significant advantage in biasing its opera- tions or creating Sybil identities (if in public blockchain). Thus, due to the Byzantine faults and network delays in real networks, the sharding protocol must tolerate a varied rate of nodes creation and inconsistency in views of committee members. For a permissionless blockchain, the protocol also needs to deal with one more challenge since the nodes have no inherent identities or external PKI to trust. A malicious node can simulate many virtual nodes, thereby creating a large set of sybils [108]. Thus, the protocol must provide an effective mechanism to establish their identities to limit the number of Sybil identities created by malicious nodes.
3 SHARDING OVERVIEW
Sharding은 원래 데이터베이스에서 사용되었던 기술이었다.
- 샤딩은 원래 대규모 데이터베이스를 관리하기 쉽고 효율적인 작은 데이터 조각인 데이터 샤드로 분할하는 데이터베이스 파티셔닝 기술.
- 데이터베이스의 수평 분할로서 대용량 데이터베이스를 더 관리 가능한 단위로 분할하여 처리.
블록체인의 발전과 함께 등장하여 확장성을 해결하기 위한 Sharding(ex. 이더리움)
- 블록체인에서의 샤딩은 네트워크를 작은 위원회로 분할하는 핵심 아이디어.
- 각 위원회는 겹치지 않는 일련의 거래 또는 “샤드”를 처리.
- 이때 위원회의 수는 전체 네트워크의 계산 능력에 선형적으로 증가.
- 각 위원회는 상대적으로 적은 수의 구성원을 가지므로, 클래식한 비잔틴 합의 프로토콜을 실행하여 병렬로 합의된 거래 집합을 결정할 수 있다.
이를 통해 샤딩은 블록체인의 처리량을 향상시키는 방법으로 작동. 대규모 데이터베이스를 작은 조각으로 분할하여 각각을 독립적으로 처리함으로써 병렬성을 증가시키고, 네트워크를 작은 위원회로 분할하여 합의 과정을 병렬화할 수 있다. 이를 통해 블록체인은 더 많은 거래를 동시에 처리할 수 있으며, 전체 시스템의 확장성이 향상.
3.1 Problem Definition
샤딩이 필요한 이유를 설명하기 위해 어떠한 블록체인을 가정해보자.
블록체인 가정
- 참여 노드의 수가
n,동일한 계산 능력,- 이 중 일부인
f는 악의적인 노드.블록체인은 각 블록당 허용되는 트랜잭션을 수락하며, 이 때 네트워크는 블록당 일정 수의 트랜잭션만 허용한다.
특정 시간에 발생한 트랜잭션들을 하나의 블록에 묶는다는 말.
- 예를 들어, 블록 j의 트랜잭션 i는 정수 xij로 표현되며, 여기서 ZN은 N의 나머지 정수의 집합이다.
  - 블록체인에서 트랜잭션은 고유한 번호로 식별된다. 이 번호는 정수 xij로 표현되고, xij는 N의 나머지 정수의 집합인 ZN에 속하게 된다. - 즉, `xij는 0에서 N-1 사이의 정수`이다. - 블록체인은 수백만 개의 트랜잭션을 포함할 수 있으므로 효율적인 저장 방법이 필요하다. 정수 xij를 사용하여 트랜잭션을 저장하면 블록체인에서 트랜잭션을 빠르게 검색할 수 있다.모든 노드는 거래의 유효성을 결정하기 위해(합의) 외부에서 지정된 제약 함수에 액세스.
- 위 규칙은 제약 함수 C로 지정되며, 이 함수는 각 트랜잭션의 입력과 출력을 확인하여 유효한지 여부를 결정한다.
- 즉, 블록체인 네트워크에서 모든 노드가 각 트랜잭션의 유효성을 검사하기 위해 동일한 규칙을 사용한다는 것을 의미.
이 때, 샤딩 프로토콜은 규칙이나 절차를 이용해 여러 개의 샤드로 구성된 집합 X를 생성한다.
집합 X 생성 순서
- 노드 간에 실행되는 프로토콜 Π를 찾는다.
이 프로토콜 Π은 k개의 샤드(아래 이미지의 하위 집합) 집합을 출력한다.
- 집합 X를 생성하기 위한 조건
- 합의: 정직한 노드는 주어진 보안 매개변수 λ에 대해 1 − 2−λ 의 최소 확률로 X에 동의합니다.
- 유효성: 합의된 샤드 X는 지정된 제약 함수 C를 만족합니다.
1
2
3
4
5
6
7
8
9
> 예를 들어, `∀i∈{1...k},∀xij ∈Xi,C(xij)=1`.
>
> - 위 공식은 샤딩에서 유효성 조건을 나타낸다.
> - ∀ (for all): 모든 요소에 대해 참인지 확인하는 양자화된 양화기호입니다.
> - i ∈ {1...k}: i는 1부터 k까지의 정수입니다. 이는 샤드의 번호를 나타냅니다.
> - xij ∈ Xi: xij는 샤드 Xi 내의 거래 집합에 속하는 거래를 나타냅니다. 여기서 j는 해당 거래의 인덱스를 의미합니다.
> - C(xij) = 1: 함수 C에 거래 xij를 입력했을 때, 결과값이 1인지를 나타냅니다. 이는 거래의 유효성을 확인하는 제약 함수의 조건입니다.
> - 모든 샤드 Xi 내의 거래 xij에 대해 제약 함수 C를 적용했을 때, 결과값이 1(참)인지를 확인하는 것을 의미.
- **확장성**: k의 값은 네트워크의 크기에 따라 거의 선형적으로 증가합니다.
즉, 샤딩의 목표는 네트워크를 여러 위원회로 분할하여 각각 별도의 트랜잭션 집합(Xi와 같은)을 처리하게 하는 것이며, 여기서 트랜잭션 집합(Xi와 같은) 을 샤드라고 한다.
3.2 Sharding Overview(샤딩 동작방식)
샤딩 프로토콜은 여러 epoch(에포크) 로 진행된다.
epoch(에포크)
- 샤딩 프로토콜에서 시간적으로 구분된 단위.
- 각 에포크는 일련의 작업을 수행하고 결과를 도출하는 주기를 나타낸다.
각 에포크에서는 아래 수식에 따라 X라는 값의 집합을 결정한다.
샤딩의 핵심 원리: 사용 가능한 계산 능력을 자동으로 병렬화하여 작은 위원회로 나누는 것
- 여기서 X는 전체 집합을 나타내며, 2^s는 Xi의 부분집합의 개수를 나타낸다.
- 여러 개의 서로 다른 부분집합 Xi로 구성되며, 각 부분집합은 개별적인 샤드이다.
- 2^s는 샤드의 개수를 결정하는 요소로, s는 샤드의 개수에 대한 지수.
- 따라서 s의 값에 따라 샤드의 수가 증가하게 된다.
각 위원회는 서로 다른 거래 집합 또는 샤드를 처리한다.
에를 들어, Elastico 프로토콜에서는..
- 위원회의 수는 네트워크의 계산 능력에 비례하여 증가
- 각 위원회는 일정한 구성원 수를 가지며, 내부적으로 전통적인 BFT 합의 프로토콜을 사용하여 한 블록에 대해 합의
각각의 샤드를 처리하기 위한 합의 프로토콜
탈중앙화된 시스템에서는 먼저 멤버십을 정의해야하며, 멤버십을 결정하기 위해 작업 증명 (PoW), 지분 증명 (PoS), 저장 증명, 개인 신원 증명과 같은 여러 가지 방법이 있다.
탈중앙화된 시스템에서 멤버십을 결정하는 것이 중요하다. 멤버십은 네트워크에 참여하는 노드나 사용자의 그룹을 지정하는 것을 의미
이러한 허가 없는 샤딩 프로토콜(탈중앙화. 누구나 네트워크에 참여할 수 있는 샤딩 프로토콜)은 일반적으로 각 합의 라운드에서 다섯 가지 중요한 구성 요소로 이루어져 있다.
Identity establishment and committee formation(신원 설정과 위원회 구성):프로토콜에 참여하려면 각 노드는 공개 키, IP 주소, 작업 증명(PoW) 솔루션으로 구성된 신원(ID)을 설정해야 합니다. 그런 다음 각 노드는 설정된 신원에 해당하는 위원회에 할당됩니다. 이 과정에서 시스템은 Sybil identity를 방지해야 합니다. (허가형 블록체인의 경우 이 과정이 필요하지 않습니다.)
Sybil identity: 한 개체가 여러 가짜 신원을 생성하여 다중 참여자로 가장하는 것을 의미
Overlay setup for committees(위원회를 위한 오버레이 설정):위원회가 형성되면,
- 각 노드는 자신의 위원회에 속한 다른 노드의 신원을 알아내기 위해 통신한다.
- 블록체인의 경우, 위원회의 오버레이는 모든 위원회 구성원을 연결한 네트워크를 의미한다.
- 일반적으로 이 과정은 gossip protocol을 사용
Intra-committee consensus(위원회 내 합의):각 위원회 내의 노드는 단일한 거래 집합에 대해 표준 합의 프로토콜을 실행합니다. 이 과정에서 정직한 구성원들은 해당 위원회 내에서 제안된 블록에 대해 합의해야 합니다.”
Cross-shard transaction processing(샤드 간 트랜잭션 처리):트랜잭션은 전체 시스템에서 원자적(atomically)으로 커밋되어야 한다. 샤드 간 트랜잭션의 경우, 관련된 샤드들은 일관성을 유지해야 한다. 일반적으로, 이 과정은 관련된 샤드 간에 동기화를 위해 ‘릴레이(relay)’ 트랜잭션 형태를 필요로 합니다.
atomically : 시스템 전체에 대해 완전히 실행되거나 실행되지 않는 것을 의미
relay transaction : 샤드 간에 동기화를 위해 사용되는 특정 유형의 거래
- 한 샤드에서 다른 샤드로 거래를 전달하고 해당 거래의 상태를 확인하며, 관련 샤드 간의 일관성을 확립하는 역할을 수행
Epoch reconfiguration(에포크 재구성):샤드는 보안을 보장하기 위해 정기적으로 재구성되어야 한다. 재구성은 샤드의 구성원이나 조건을 변경하여 보안을 강화하는 과정이다. 이를 위해 무작위성이 필요한 한데, 재구성에 사용되는 매개 변수나 결정 사항을 예측하기 어렵게 만들기 위해서이다.
샤딩 프로토콜을 설계하기 위한 두 가지 중요한 과제
모든 노드를 균일하게 여러 위원회로 분할하여 각 위원회가 대부분의 정직한 노드를 높은 확률로 보유하도록 하는 것 - 이를 위한 좋은 무작위성이 필요하다.
좋은 무작위성은 이 도전 과제를 부분적으로 해결하기 위한 중요한 구성 요소로서, 고엔트로피(high-entropy) 출력을 제공한다. 그러나 분산 네트워크에서 좋은 무작위성을 얻는 것은 어려운 문제이다.
이에 대해서 5장에 에포크 무작위성에 대한 자세한 논의를 제공
악의적인 주체가 작업을 편향시키거나 Sybil identity(공개 블록체인의 경우)를 생성하는 데서 상당한 이점을 얻지 못하도록 보장하는 것
실제 네트워크에서는 바이잔틴 결함과 네트워크 지연과 같은 문제들이 발생할 수 있다. 이로 인해 샤딩 프로토콜은 노드 생성 속도의 다양성과 위원회 구성원들이 서로 다른 시점에서 정보를 받아들이는 것을 허용해야 한다.
허가 없는 블록체인에서는 추가적인 도전 과제가 있습니다. 왜냐하면 노드들은 본질적인 신원이나 외부 신뢰 인증 기관을 가지고 있지 않기 때문이다. 악의적인 노드들은 가상 노드를 많이 생성하여 가짜 신원을 만들 수 있다. 그래서 프로토콜은 악의적인 노드들이 만드는 가짜 신원의 수를 제한하기 위해 신원을 확인하는 효과적인 방법을 제공해야 한다.
다음에 계속…