Sharding

※ 원글 작성 : 22년 5월 2일

 

Vitalik Buterin의 블로그 상에서 샤딩이 좋은 이유에 대한 설명을 참고한다.

vitalik.ca

Sharding

샤딩은 데이터 저장기법 중 하나로 여러개의 작은 조각으로 나누어 분산 저장하여 관리하는 것을 말한다. 블록체인에서 샤딩을 적용 시에는 네트워크를 분할한 뒤 트랜잭션들을 별도로 저장하고 이를 병렬적으로 처리하여 블록체인 확장성을 부여하는 개념이다. 예를 들어, 20만큼의 데이터와 10개의 노드가 참여했을 시 기존의 블록체인은 10개의 노드가 20의 데이터를 모두 들고 있어야 되지만, 샤딩은 20을 조각내서 각 노드가 2개의 데이터만 보관하여 가벼워지고, 거래처리 속도가 향상될 수 있다. 각 샤드별로 MPT를 만들고 해당 샤드의 root들로 만들어진 MTP의 root만 블록체인에 올리는 것으로 모든 miner가 모든 트랜잭션을 실행할 필요 없이 샤드별로 miner를 분산시킬 수 있다.

Trilemma

블록체인은 Scalable(확장성)/Decentralized(탈중앙성)/Secure(보안) 3가지의 속성 중 2가지만 획득할 수 있고 3가지를 모두 충족하는 것은 어렵다. 이를 블록체인 트릴레마라고 하며 많은 블록체인 플랫폼 프로젝트들이 트릴레마를 모두 충족 가능하도록 만들기 위해 노력하고 있다.
비탈릭 부테린 블로그에서는, 샤딩을 이용한 이더리움은 트릴레마 3가지를 모두 얻을 수 있다고 한다.

• 확장성 : Single node보다 더 많은 트랜잭션들을 처리 가능
• 탈중앙성 : 일반 사용자의 laptop/mobile phone 등에서 노드 운영이 가능해, 탈중앙화 가능
• 보안 : 공격자는 작은 리소스만으로 시스템의 작은 part를 타게팅할 수 없다(공격자는 전체 시스템에 대해서만 공격 가능)

샤딩을 적용함으로써 위 3가지를 어떻게 충족시키는지 확인해본다.

Beacon chain

개념적 샤딩 설명에 앞서 위 그림에서 명시되어 있는 비콘체인부터 알아본다. 비콘체인은 다음과 같은 역할을 맡는다.

• 거래 검증인과 투표를 위한 토큰 관리
• 제안된 블록을 투표에 부쳐 검증인에게 전달
• 합의 기준 적용
• 투표에 참여한 검증인에게 보상과 처벌을 진행

비콘체인은 종합적으로 이더리움의 PoS 도입시 필요한 중요한 역할을 맡는다.
추가적으로 비콘체인은 샤딩에서도 큰 역할을 부여 받았는데, 기존 이더리움 노드들을 샤드에 배정할 때 무작위로 배정하여 담합, 공격을 방지하는것이 바로 해당 역할이다.

Sharding through Random Sampling

랜덤 샘플링을 통한 샤딩은 간략하게 말해 검증자 set을 무작위로 나누는 것이다.

vitalik.ca

위 그림처럼 검증자를 무작위로 섞고 commitee를 구성하여 각 commitee 별로 블록을 검증하는 방식이다. 검증된 블록에 검증 완료되었다는 서명을 게시하여 블록체인 참여자들은 각 블록이 유효함을 확인하는 작업을 거치는 대신 검증자의 서명만 확인하여 검증 과정에서 더 적은양의 resource만 투입하여 확장성을 가질 수 있게된다.
샤딩을 적용 시킨 버전에서, 각 노드가 블록체인에 참여할 시 기존 P2P 네트워크에서 전체 블록을 broadcast하는 대신 자신이 담당하는 서브 블록체인에 참여하기만 하면된다.

Commitee 100 Vs. Chain 100

제안된 샤딩 방식처럼 검증인 모임을 100개로 나누는것과, 체인을 100개의 개별 체인으로 나누는것에 대한 차이는 아래와 같다.

• 공격자 리소스 분산

랜덤 샘플링은 공격자가 하나의 샤드에 힘을 집중하는 것을 막는다. 공격자는 100개의 멀티체인 환경에서 혼란시킬 때(wreak havoc)는 지분의 0.5%만을 사용하여서, 나뉘어진 하나의 체인 공격에 51%를 집중시킬 수 있다. 반면에 샤딩된 체인에서는 공격자는 지분의 30~40% 정도가 되어야 동일한 작업을 수행할 수 있다. (즉 체인이 shared secure를 가짐) 공격자가 전체 지분의 50%미만에도 단일 샤드에서 51% 공격을 할 수 있겠지만 51% 미만의 공격자에게 exponential로 어려워지고, 30% 미만은 사실상 불가능하다.

• 긴밀한 결합

어떤 샤드에 불량 블록(bad block)이 발생하면 전체 체인은 이를 피하기 위해 재구성된다. 샤드 내의 social contract는 단 하나의 불량 블록이 발생하더라도 해당 체인은 허용되지 않으며 발견 즉시 폐기되는 원칙을 들고 있다. 이를 통해 체인 내 어플리케이션 관점의 보안이 보장된다. 예를 들어, contract_A가 contract_B에 의존이 되어있을 시 contract_B가 체인에 대한 공격 때문에 잘못된 행동을 하면 이 때문에 contract_A의 transactions를 포함하여 전체 히스토리가 revert된다.

Improving sharding with better security models

비트코인이나 이더리움의 경우 51% 공격이 있을 시 공격자가 트랜잭션의 reverting or censoring을 진행할 수 있지만 잘못된 Tx를 블록에 삽입할 수는 없다. 그리고 revert(잘못된 상태로 돌리는것), censor(검열)과 같은 공격을 진행해도 일반 노드들은 해당 동작들을 쉽게 감지 가능해 fork를 통해 공격을 해결하는 등 대응이 신속하게 가능하다.
이런 추가적인 보안이 없는 것은 보다 centralized된 높은 TPS를 보유한 체인들의 약점이 된다. 주요 노드와 생태계 참여자는 훨씬 쉽게 전체 커뮤니티가 싫어하는 프로토콜로 변경이 가능해지며 일반 노드들은 기본적으로 변경된 프로토콜을 수락한다. 일정 시간이 지나서 일반 노드들도 확인이 가능하지만 정상적으로 돌리기 위해서는 시간과 리소스가 추가적으로 필요하며, 그때는 이미 공격이 끝나있을 것이다.

Scalable verification of computaion

이더리움은 샤딩을 진행해도 위와 같은 보안 방어벽 유지를 원하기 때문에 확장 가능한 유효성 검사에 대해 연구 중이다.
블록 검증 시에 아래 2가지를 모두 확인해야 한다.

• 계산 유효성 검증(Validating computaion) : 계산에 대한 모든 input을 소유하고 있는 가정하에 일부 계산이 올바르게 수행되었는지 확인
• 데이터 가용성 검증(Validating data availability) : 계산 자체에 대한 input이 필요한 경우 다운로드할 수 있는 형식으로 저장되어 있는지 확인, 해당 검사는 실제로 다운로드 하지 않고 수행되어야 함(block data가 너무 큼)

이 과정에서 블록의 트랜잭션이 유효하고 블록에서 청구된 새로운 state root hash가 트랜잭션을 실행한 올바른 결과인지를 신뢰해야 하며, 데이터를 다운받는 사용자가 state를 계산하고 블록 처리를 할 수 있도록 충분한 데이터가 존재해야됨을 확신해야 한다.
해당 조건들을 충족시키며 확장 가능하게 검증하는 것은 두가지 방식이 있다.

• Fraud proof
• zk-SNARK

각 기술들은 roll up시에도 사용되는 기술이며 Fraud proof는 optimistic roll up시에, zk-SNARK(or STARK)는 zk roll up 시에 사용된다. (각 기술들에 대한 설명은 추후 roll up과 관련된 게시물을 작성할 시 업데이트 할 예정임)
결론적으로, Fraud proof는 transaction 등 데이터에 대해 신뢰를 가정하여 일단 블록에 저장 시키고 추후 문제가 발생시 되돌리는 방법을 취하여 zk-SNARK는 크기가 작은 증명을 검증함으로써 동작한다.

Shard와 확장 가능한 증명의 관계

결론적으로, 이더리움에서의 샤딩의 경우 샤딩된
블록을 data의 저장공간으로만 만드는 것이며, 보안성 유지와 높은 트랜잭션 처리량을 사용하기 위해 앞서 언급한 확장가능한 계산 증명을 사용하는 것이다. 샤드는 오로지 'data availability engine'이며 fraud proof와 zk-SNARK와 함께 사용하여 블록 검증 계산 리소스와 보안 데이터 공간을 활용함으로써 layer2 roll up을 통해 메인체인에 확장성을 부여할 수 있는것이다.

여러 기술들을 혼합하여 기존의 블록체인의 탈중앙화와 보안을 유지하며 확장성을 보완해서 샤딩으로 이더리움의 블록체인 트릴레마를 해결하자는 것이 이 글의 주된 의견인 것이다.

Sharding의 장단점

기존 블록체인은

• 유효하지 않은 블록(invalid block)은 노드가 유효하지 않음을 인식하여 무시되고,
• 사용할 수 없는 블록(unavailable)은 검증 노드가 다운로드 하지 못하고 무시

하기 때문에 증명을 통과할 수 없다.
마찬가지로 샤딩된 블록체인은

• 유효하지 않은 블록이 무시되는 2개의 방법과
  • Fraud proof는 신속하게 잘못된 블록을 확인해서 네트워크에 블록의 부정확성을 알리고 생성자에게 무거운 처벌을 내림
  • 정확성을 증명하여 유효하지 않은 블록에 대해 유효한 zk-SNARK를 만들 수 없음
• 2가지의 사유로 사용할 수 없는 블록을 무시함으로써
  • 블록 데이터 50% 미만을 사용 가능한 경우 각 클라이언트가 적어도 하나의 data available 검사가 확실히 실패하여 클라이언트가 블록을 거부
  • 블록 데이터 50% 이상을 사용 가능한 경우 나머지 블록을 재구성하는데 정직한 노드가 하나만 있으면 되어 전체 블록 사용 가능

기존 블록체인이 가지고 있는 보안 속성을 복제하여 보안성을 갖추고 각 트랜잭션을 개인 노드가 확인할 필요가 없도록 해서 확장성을 높일 수 있다.

샤딩이 없는 기존의 높은 TPS 보유 체인들은 이러한 보안성을 제공할 수 없다. 멀티체인/사이드체인은 공격자가 하나의 체인을 공격하고 쉽게 악의적으로 변화시키는데에 방어할 능력이 없다. 이더리움 샤딩이 TPS를 높이기 위해 validator를 제한적으로 두는, DPoS 등의 consensus 알고리즘을 사용하는 다른 블록체인에 비해 보안적 측면에서 유리할 수 있다.

단점도 역시 존재한다.

• commitee에만 의존하는 샤딩된 체인은 적응형 공격자(adaptive adversaries)에게 취약하다. 공격자가 commitee 집합을 실시간으로 해킹 할 능력이 있는 경우 소수 노드만 공격하여 commitee를 파괴하면되기 때문이다. 이를 fraud proof/zk-snark와 함께 데이터 가용성 샘플링이 랜덤 샘플링을 보완하는 중요한 이유이다.
• 데이터 가용성 샘플링은 충분한 수의 온라인 클라이언트가 있는 경우만 안전하다.
• 샤딩된 체인이 fraud proof에 의존하는 경우 네트워크가 너무 느리면 노드가 블록이 잘못되었음을 보여주기 전에 블록을 승인할 수 있다.
• 전달 raw data가 많아서 극단적인 네트워크 환경에서 fail될 가능성이 높아진다.
• 샤딩된 블록체인은 P2P 네트워크에 의존하고, 각 개별 P2P 서브 체인은 노드 수가 적기 때문에 공격하기 쉽다.

참고
https://vitalik.ca/general/2021/04/07/sharding.html
http://wiki.hash.kr/index.php/%EC%83%A4%EB%94%A9