Throne of ZK: SNARK vs. STARK

[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

  100명 이상의 풀타임 개발자를 보유한 에코시스템 중 Starknet의 이전 연도 대비 개발자 수 변화율이 +243%로 가장 빠르게 증가하고 있다. 출처: Electric Capital

아래는 Electric Capital의 2022년 개발자 보고서에서 Starknet이 언급된 헤드라인들을 취합한 것인데, 개발자들이 빠르게 온보딩하고 있는 모습을 살펴볼 수 있다.

• ecosystems with 100+ full-time developers: starknet +243%, Internet computer +94%, & Cardano +14% grew yoy while tezos stayed flat
• ecosystems with 300+ total devs: starknet +134%, icp +48%, near +41%, the graph +21%, Kusama +9%, Bitcoin +2%, cardano +2%, & Celo flat
• since 2018: Polygon, NEar, Tezos, BNB, internet computer, & starknet grew 20x+ to 120+ full-time devs
• Internet computer, starknet, tezos, the graph, avalanche, & celo had <50 devs and now have 300+ devs
• ecosystems under 2 years old: starknet, aptos, & sui have 60+ Full-Time developers; starknet has the most at almost 120 Full-Time developers
• Starknet, BNB, avalanche, Cardano, tezos, & icp took different paths to grow to 100+ full-time developers
• ecosystems under 2 years old: starknet, aptos, & sui have 100+ total developers; starknet has the most at almost 400 total devs

 

Trusted setup

Trusted setup은 여러 당사자가 참여해 증명 시스템의 표준 매개변수를 생성하는 프로세스이다. 이 프로세스의 참여자는 신뢰할 수 있어야 하므로 “Trusted”라는 용어를 사용한다. 여러 당사자가 아니라 단일 당사자로 설정할 수 있으나, 한 당사자에게 증명 시스템의 큰 부분을 할당하는 것이므로 위험이 따른다.

Trusted setup을 증명 시스템에 도입함으로써 여러 획기적인 효과를 가져왔지만(소요 시간 단축 등), Prover와 Verifier가 아닌 제3자를 신뢰해야하기 때문에 잠재적 신뢰 리스크로 작용할 수 있다는 단점이 있다.

그러나 최근 transparent한 (trusted setup을 제거한) 구조에 대한 논의가 매우 활발하게 진행되고 있다. (e.g, Halo, Halo2, etc)

Quantum Resistance

SNARK는 elliptic curve cryptography를 사용하는데, 이는 양자 컴퓨터의 공격에 취약하다. 반면에 STARK는 양자 컴퓨터 공격에 저항력이 있는 것으로 알려진 cryptographic hash functions를 사용한다. 보다 자세한 설명은 이 글에서 확인할 수 있다.

 

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

“History doesn’t repeat itself, but it often rhymes.” — Mark Twain

과거를 되짚어보면, 유사한 기술이 비슷한 시기에 등장하여 경쟁한 사례를 쉽게 찾아볼 수 있다. 경쟁에서 승리한 기술이 시장을 지배하는 경우가 일반적이지만, 두 기술이 확연히 구분되는 장점을 갖는 경우 종종 모두 살아남는 경우 또한 존재한다.

아래 표는 1970년부터 2010년까지 유사 기술 간의 경쟁 15건에 대해 승자, 승리 요인, 키워드로 요약한 표이다. 대부분의 경쟁에서 단일의 승자가 존재하며, 승리 후 시장을 독식하였다. 그러나 경쟁하는 두 기술의 장점이 명확하고, 상호 배타적일 때 두 기술 모두 살아남은 경우 또한 존재한다. (e.g., Wi-Fi vs. Bluetooth, MP3 vs. AAC)

   
SNARKs와 STARKs 또한 위에서 살펴본 것처럼 각자의 장점이 명확하게 구분된다. 영지식 증명 관련 시장이 매우 초기이기 때문에 같은 카테고리에 속한다는 이유로 자주 비교되지만, 시장이 성숙해지면서 영지식 증명을 활용하는 어플리케이션들의 수와 성격이 다양해진다면 SNARK와 STARK는 각자 독자적인 영역을 확보할 것으로 보인다. (예: 증명의 계산 복잡도가 크지 않은 컨슈머 앱 → SNARKs, 계산 복잡도가 큰 프로젝트를 구축하기 위한 경우 → STARKs)

   
Competition diminishes over time

 

3. So, what’s NEXT?

두 기술이 경쟁하다가 한 기술의 승리로 끝이 날 수도 (e.g., HD DVD vs. Blu-ray), 둘 다 각자의 방식으로 살아남을 수도 (e.g., Wi-Fi vs. Bluetooth), 두 기술 보다 뛰어난 새로운 기술이 나타자 두 기술 모두 사장될 수도 (e.g., 3G vs. 4G then 5G) 있을 것이다.

그러나 두 진영이 연구하는 성과들은 모두 영지식 증명의 발전에 필요한 양분이 되었으며, 될 것이기에 큰 의미를 갖는다. 영지식 증명의 next step이 궁금할 사람들을 위해 주목하면 좋을 몇 가지 주제들을 추천하면서 글을 마친다.

SNARK + STARK → SPARK!! 💥💥

SNARKs와 STARKs 각각의 장점이 명확하게 구분됨에 따라, 두 기술의 장점을 모두 취하려는 시도가 활발히 진행되고 있다. 아래 페이퍼들은 학계 또는 업계에 큰 영향을 미쳤거나, 최근 많은 주목을 받고 있는 자료들이다.

• HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
• HyperPlonk, a zk-proof system for ZKEVMs
• On the Size of Pairing-based Non-interactive Arguments?
• Transparent Polynomial Commitment Scheme with Polylogarithmic Communication Complexity
• Understanding PLONK
• PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

Labs focusing on zk

아래는 영지식 기술에 초점을 맞춰 투자/연구를 진행하는 Labs들이다. 이들이 올리는 게시글들을 참고하는 것도 업계에서 최근 고민하는 주제들을 빠르게 파악하는 데에 좋은 방법이 될 수 있다.

• https://personaelabs.org/
• https://delendum.xyz/
• https://0xparc.org/
• https://geometry.xyz/

 

다양하게 발전되고 있는 zkp systems

아래 표는 2013년도부터 2021년에 이르기까지 다양하게 발전되고 있는 zkp 시스템들을 Protocol, Transparent, Universal, Plausibly Post-Quantum Secure, Programming Paradigm으로 구분한 자료이다.

  출처: Wikipedia

-> 'Throne of ZK: SNARK vs. STARK' 보러가기