ZK-Proof 기초 커리큘럼

ZK의 개념 및 P/NP/IPS와의 구분

ZK-proof: 내가 어떤 계산을 올바르게 수행했다는 사실을, 그 계산의 내용은 공개하지 않고 증명하는 기술

이를 위해 필요한 것:

1. 계산을 수학적으로 표현
2. 그 계산이 맞다는 것에 대한 설득
3. 아무 정보도 새지 않게 하는 장치

P vs NP, IPS 등의 개념은 1번을 극단까지 밀어붙인 이론적 정당화 과정에서 나오는 개념.

ZK-Proof 기초 커리큘럼

0단계 - ZK가 왜 필요한가?

• 목표: ZK가 '증명기술'이라는 것에 대한 감각 잡기, '비밀을 숨긴다'가 정확히 무슨 의미인지 이해하기
• 핵심 개념:
  • 증명 vs 계산
  • 신뢰 vs 검증
  • 말로 주장 vs 수학적으로 증명
• 필수 키워드:
  • Prover / Verifier
  • Statement vs Witness
  • Soundness / Completeness / Zero-Knowledge (이 세 가지는 암기 수준으로)

1단계 - 가장 원초적인 ZK: Interactive Proof

• 목표: ZK의 뼈대를 이해하기, "검증자는 직접 계산하지 않지만, 속이기 어렵다"는 것을 이해하기
• 배우는 개념:
  • Interactive Proof
  • Challenge-Response
  • Randomness의 역할
• 대표 예제:
  • 동전 색깔 문제
  • Graph Isomorphism ZK Proof
  • Ali Baba cave

2단계 - ZK Proof의 정의를 정확히 이해

• 목표: ZK의 철학적 핵심 이해하기
• 핵심 성질 3가지:
  • Completeness → 참이면 정직한 증명자가 항상 통과
  • Soundness → 거짓이면 거의 확률적으로 속일 수 없음
  • Zero-Knowledge → 증명 과정이 아무 정보도 안 줌

3단계 - NP, 하지만 가볍게

• 목표: 왜 NP가 나오는지 이해하기, 최소한의 NP 지식 갖추기
• 최소한의 지식:
  • NP의 정의 (비결정성 말고 증명 검증 관점)
  • witness의 의미
  • "검증은 빠르다"의 정확한 뜻
• 이때 필요 없는 것:
  • P vs NP 문제 ❌
  • NP-완전성 증명 ❌

4단계 - Non-Interactive ZK (Fiat-Shamir)

• 목표: 현대 ZK의 출발점 이해하기, 블록체인에서 쓰겠다는 감각 느끼기
• 핵심 아이디어:
  • 대화형 ZK → 한 번의 증명으로
  • 랜덤 챌린지를 해시 함수로 대체
• 배우는 개념:
  • Random Oracle Model
  • Fiat–Shamir Transform
  • Proof size / Verification time

5단계 - 계산을 증명하려면? (Circuit / R1CS)

• 목표: ZK의 실질적인 관문 넘어서기, 계산을 수학구조로 바꾸는 법 이해하기, "프로그램→회로→제약식→증명" 흐름 느끼기
• 배우는 순서:
  1. Boolean circuit
  2. Arithmetic circuit
  3. R1CS (Rank-1 Constraint System)

6단계 - SNARK / STARK 맛보기

• 목표: 개념적 분류 이해하기
• 핵심 개념:
  • SNARK vs STARK
  • Trusted setup 유무
  • Pairing 기반 vs Hash 기반