Throne of ZK: SNARK vs. STARK

user-image
Kido Kim
Researcher/
Nonce Classic
2023.04.05

[Xangle Digest]

※해당 컨텐츠는 3월 23일 외부에서 기발간 된 컨텐츠입니다. 컨텐츠에 대한 추가적인 주의사항은 본문 하단에서 확인해주세요.

목차

1. SNARK and STARK

2. 과거 사례를 통해 예측해보는 SNARKs vs. STARKs

3. So, what’s NEXT?

 

 

 

 

Intro

기술의 발전 역사를 살펴보면 유사한 기술들이 비슷한 시기에 등장하여 시장의 패권을 두고 경쟁했던 사례를 쉽게 찾아볼 수 있다. 최근 시장에서 많은 관심을 받고 있는 zero-knowledge 시장에서도 이런 사례를 찾아볼 수 있는데, zk-snark (이하 SNARK) 와 zk-stark (이하 STARK) 가 그것이다. 이 글에서는 SNARK와 STARK 각각의 특징을 살펴보고 비교해본 뒤, 과거 사례들을 통해 이 경쟁이 앞으로 어떻게 전개될 것인지 예측해볼 것이다.

 

1. SNARK and STARK

WHAT IS zk-SNARK?

  • zk-SNARK = zero-knowledge Succint Non-interactive ARgument of Knowledge

zk-SNARK는 2012년 1월, UC 버클리의 Alessandro Chiesa (co-inventor of Zerocash, co-founder of Zcash, and co-founder of StarkWare Industries) 교수와 집필진에 의해 탄생하였다.

2012년 1월, UC 버클리의 Alessandro Chiesa (co-inventor of Zerocash, co-founder of Zcash and StarkWare Industries) 교수와 집필진이 이 논문에서 처음 zk-SNARK 라는 개념을 소개하였다. 우리는 SNARK를 구성하는 네개의 단어 중에서 ‘Succint’와 ‘Non-interactive’에 집중할 필요가 있다.

  • Succint: 증명의 크기가 작기 때문에 쉽고 빠르게 검증할 수 있음을 의미한다. ‘쉽고 빠르게’라는 의미는 곧 연산을 적게 요구한다는 뜻이며, 이는 블록체인에서 곧 소요 시간과 가스피를 적게 소모한다는 이점으로 이어진다.
  • Non-interactive: Non-Interactive zkp는 Interactive zkp의 한계*를 극복하기 위해 암호학적 방법론을 통해 Interaction 없이 Prover가 본인이 특정 정보를 알고 있음을 증명할 수 있는 시스템이다. 오늘날 우리가 영지식 증명 기술이라고 부르는 대부분의 기술이 Non-interactive zkp이다.(Interactive zkp의 한계: 증명을 확률에 의존하며, 여러 번의 Interaction을 요구하기 때문에 소요 시간과 연산 측면에서 비효율적인 부분이 존재함          (참고: 이 글에서는 두 기술의 명확한 대비를 위해 원시적인 모델의 SNARKs를 기준으로 비교를 진행하였다.)

WHAT IS zk-STARK?

  • zk-STARK = zero-knowledge Scalable Transparent ARgument of Knowledge

zk-STARK는 2018년 Eli Ben-Sasson과 집필진에 의해 탄생하였다. 우리는 STARK를 구성하는 네개의 단어 중에서 ‘Scalable’과 ‘Transparent’라는 단어에 집중할 필요가 있다.

  • Scalable: STARK가 얼마나 블록체인의 확장성 향상에 초점을 맞춘 기술인지 알 수 있다. STARK는 증명의 복잡성이 증가하더라도 연산처리능력의 변동이 SNARK에 비해 작기 때문에 보다 높은 확장성을 가졌다고 볼 수 있다. 아래 그래프는 STARK를 소개한 논문에 나와있는 데이터를 토대로 계산 복잡도가 증가함에 따라 SNARK와 STARK의 소요 시간 변화를 시각화한 것이다. STARK는 증명의 복잡도가 증가할 때 상대적으로 크지 않은 변동을 보인다.
      
    As the computational complexity increases, the time required for Snark increases significantly compared to Stark (출처)
  • Transparent: STARK는 trusted setup을 필요로 하지 않는다. 따라서 증명에 사용되는 매개변수가 투명하게 공개된다고 볼 수 있다. 

 

SNARK ↔ STARK

  
Proof size

영지식 증명은 한 당사자(증명자)가 다른 당사자(검증자)에게 특정 진술이 참이라는 것을 보유한 정보를 공개하지 않고 증명할 수 있는 기술이다. Proof size는 이 증명을 위해 필요한 데이터의 양을 의미한다.

영지식 증명에서 Proof size는 매우 중요한데, Proof size가 클수록 증명을 생성하고 전송하는 데 더 많은 연산과 통신이 필요하기 때문이다.

Trusted setup이 완료된 SNARK를 기준으로 했을 때 Proof size는 STARKs에 비해 현저히 작다. 이로 인해 SNARK를 사용했을 때 발생하는 가스피와 소요 시간은 STARK와 비교했을 때 현저히 작으며, 이것이 여러 프로젝트들이 SNARK를 채택하는 이유 중 하나이다.

출처: Beanstalk


Resources to refer to

여기서 참고할 수 있는 리소스란 프로젝트의 수, 개발자의 수, 공개된 코드 및 라이브러리의 수, 의견을 공유할 수 있는 커뮤니티의 사이즈 등을 의미한다. SNARK가 STARK보다 풍부한 리소스를 가지고 있다는 의견이 지배적이다. 그러나 최근 Electric Capital에서 발표한 2022 Developer Report에 의하면 StarkNet에 진입하는 개발자의 수가 눈에 띄게 증가하고 있으며, 이를 통해 STARK의 약점인 참고 자료 부족이 보완될 것이라고도 예측해볼 수 있겠다.

   신생 에코시스템인 Aptos, Sui, Starknet 중에서 Starknet의 풀타임 개발자의 수가 약 120명으로 가장 많다.
출처: Electric Capital