# SNARK {% hint style="warning" %} [**Decipher ZK Session**](https://youtube.com/playlist?list=PLe1sXaxIkSC1sz0fVE2Hr_Diu1_qtG5Ea\&si=mWq6Jzsh3hTuMHBi)**를 참조하여 ZK와 SNARK에 대한 기본적인 개념, ZK-SNARK의 과정에 대해 설명하겠습니다.** {% endhint %} ### ZK가 만족해야 하는 세 가지 성질 영지식증명 프로토콜은 보통 다음 세 가지 성질을 만족해야 한다. 1. Completeness * 명제가 참이고 Prover와 Verifier가 모두 정직하게 프로토콜을 따른다면,\ Verifier는 항상 Prover의 주장을 받아들여야 한다. 2. Soundness * 명제가 거짓일 때, 아무리 교묘하게 속이려는 Prover라도\ “우연히 맞춘다” 수준 이상의 확률로 Verifier를 속일 수 없어야 한다. 3. Zero-knowledgeness * Verifier는 “명제가 참이다”라는 사실 외에, 비밀에 대한 추가 정보를 얻지 못해야 한다. * 즉, Verifier가 나중에 비밀 없이도 비슷한 대화(transcript)를 시뮬레이션(가짜 생성)할 수 있다면,\ 실제 대화와 시뮬레이션된 대화를 구분할 수 없어야 한다. 이 세 가지가 동시에 성립할 때, 해당 프로토콜을 영지식증명이라고 부른다. ## SNARK: Succinct Non-Interactive Argument of Knowledge SNARK는 “Succinct Non-Interactive Argument of Knowledge”의 약자이다.\ 각 단어가 의미하는 바는 다음과 같다. 1. Succinct (간결성) * 증명(Proof)의 길이가 매우 짧다. * 원래 계산이 아무리 크더라도, Verifier는 작은 증명 데이터만 보고 빠르게 검증할 수 있다. 2. Non-Interactive (비대화형) * Prover와 Verifier가 여러 번 메시지를 주고받지 않고,\ Prover가 한 번에 “증명 한 덩어리”를 만들어 보내고 Verifier가 그것만 검증하는 구조이다. * 블록체인에서는 Verifier(스마트 컨트랙트)가 Prover와 왕복 대화를 하기 어렵기 때문에, 비대화형 구조가 중요하다. 3. Argument (논증) * “수학적으로 절대 속일 수 없다”는 의미의 증명(proof) 대신,\ **계산 능력이 제한된 Prover**에 대해서만 soundness를 보장하는 개념이다. * 실제 암호 시스템에서는 대부분 이 의미의 “Argument”를 사용한다. 4. Proof of Knowledge (지식에 대한 논증)이다. * Prover가 주어진 명제를 증명하기 위해,\ 실제 어떤 비밀(위트니스, witness)을 알고 있어야만 증명을 만들 수 있도록 설계된 구조이다. * 예를 들어, “나는 해시 $$h$$ 의 preimage $$x$$ 를 알고 있습니다”라는 명제에서,\ $$x$$ 를 실제로 알고 있는 사람만 해당 proof를 생성할 수 있어야 한다. 정리하면, SNARK는 다음과 같은 시스템이다. > “어떤 계산이 올바르게 수행되었다”는 사실을 > > * 간결한 크기의 증명으로, > * 비대화형으로, > * 실제로 해당 계산에 필요한 비밀을 알고 있는 사람만 생성할 수 있도록\ > 증명하게 해 주는 구조이다. ### 왜 SNARK가 필요한가 블록체인 환경에서 SNARK가 필요한 이유는 다음과 같다. * 온체인(Ethereum L1 등)에서 복잡한 계산을 직접 수행하면 가스 비용이 매우 많이 든다. * 따라서 계산은 오프체인(롤업 노드, 별도의 프로버 서버 등)에서 수행하고, * 온체인에는 “이 계산들이 모두 올바르게 수행되었다”는 짧은 증명만 올리는 방식이 필요하다. 이때 SNARK의 역할은 다음과 같이 정리할 수 있다. > 신뢰할 수 없는(믿을 수 없는) 강력한 컴퓨터가 수행한 복잡한 계산을, 신뢰할 수 있는 작은 검증자(스마트 컨트랙트 등)에게 “이 계산은 정말로 올바르게 수행되었습니다”라는 짧은 증명으로 설득하는 구조이다. ## ZK + SNARK = ZK-SNARK ### 정의와 활용 예시 이제 Zero-Knowledge(프라이버시)와 SNARK(간결·비대화형·지식증명)를 결합하면 **ZK-SNARK**가 된다. > ZK-SNARK는 > > * SNARK의 간결하고 비대화형인 증명 구조에, > * 영지식(Zero-Knowledge) 성질을 결합한\ > 구체적인 영지식증명 시스템이다. 대표적인 활용 예시는 다음과 같다. * **Tornado Cash** * “어떤 입금과 출금이 연결되어 있다”는 사실만 증명하고,\ 실제 어느 주소에서 어느 주소로 이동했는지는 숨기는 mixer 프로토콜이다. * **Semaphore** * “나는 이 그룹의 멤버입니다”라는 사실만 증명하고,\ 내가 그룹 내의 정확히 어떤 멤버인지는 숨기는 프라이버시 레이어이다. * **ZK-Rollup** * 여러 거래를 모아서 오프체인에서 실행하고,\ “이 거래 배치 전체가 규칙에 맞게 처리되었습니다”라는 ZK-SNARK 증명 하나만 L1에 올려\ 스케일링을 달성하는 방식이다. 요약하면, ZK-SNARK는 > “올바른 계산이 수행되었고, 그 계산에 필요한 비밀을 실제로 알고 있습니다”라는 사실을 짧고 비대화형이며, 비밀은 노출하지 않는 방식으로 증명하는 기술이다. ## ZK-SNARK의 전체 흐름 ZK-SNARK는 보통 다음과 같은 형태의 명제를 다룬다. > “나는 입력 $$x$$ 를 알고 있고, 어떤 프로그램 $$f$$ 에 대해 $$y=f(x)$$ 를 만족한다." 이를 ZK-SNARK로 증명하기 위해서는, 프로그램을 다음과 같은 단계로 변환한다. 1. **프로그램(함수) → 산술 회로(Arithmetic Circuit)** 2. **산술 회로 → R1CS (Rank-1 Constraint System)** 3. **R1CS → QAP (Quadratic Arithmetic Program)** 4. **QAP → 다항식 커밋(Polynomial Commitment, 예: KZG)** 단계이다. 5. 그 다음, 이 구조를 이용해 짧은 Proof를 생성하고 검증한다. 아래에서는 예시로 다음 명제를 사용한다. > “나는\ > $$x^3+x+5=35$$를 만족시키는 $$x$$ 를 알고 있다.” 이 명제에 대해 각 단계를 따라가면서 설명한다. ### 1단계: Function → Arithmetic Circuit 명제는 다음과 같다. > “나는 어떤 값 $$x$$ 를 알고 있고, $$x^3 + x + 5 = 35$$ 를 만족한다.” 이 식 전체를 한 번에 다루기보다는,\ 이를 **덧셈/곱셈 게이트**로 쪼개서 산술 회로 형태로 표현하는 것이 목표이다. #### 중간값을 도입해 계산을 나누는 방식 중간 변수들을 도입하여 다음과 같이 식을 나눈다. $$x \cdot x = sym\_1$$\ $$sym\_1 \cdot x = y$$ \ $$(x+y)⋅1=sym\_2$$\ $$(sym\_2+5)\cdot1=out$$ 여기서 * $$sym\_1 , y, sym\_2$$는 중간 계산 결과이다. * 최종적으로 $$out=35$$ 가 되어야 한다. 즉, 원래 식 $$x^3 + x + 5 = 35$$를 네 개의 작은 연산(게이트)로 분할한 것이다.\ 각 연산은 곱하기나 더하기 + 상수 곱으로만 이루어져 있으므로,\ 전체 구조를 산술 회로(Arithmetic Circuit) 로 볼 수 있다.
### 2단계: Arithmetic Circuit → R1CS R1CS(Rank-1 Constraint System)의 핵심 아이디어는,\ 회로에서 사용되는 모든 변수들을 하나의 벡터로 모으고,\ 각 게이트를 다음과 같은 형태의 제약으로 표현하는 것이다. 변수 벡터 $$s$$ 의 예시는 다음과 같다. $$s=\[1,x,out,sym\_1,y,sym\_2]$$ (맨 앞의 1 은 상수항을 표현하기 위한 자리이다.) \ 이 벡터는 숨겨야 하는 값 $$x$$와 계산 과정에서 나온 값을 합친 것이다. 각 제약은 다음과 같은 형태의 식으로 표현한다. $$(s \cdot a),(s \cdot b) = (s \cdot c)$$ 여기서 $$a,b,c$$ 는 각 제약에 맞게 정의한 계수 벡터이다.\ $$(s \cdot a)$$ 는 $$s$$ 와 $$a$$ 의 내적(inner product)이다. 예를 들어 첫 번째 제약 $$x \cdot x = sym\_1$$ 에 대해, * 벡터 $$a$$ 가 $$x$$ 를 뽑도록, * 벡터 $$b$$ 도 $$x$$ 를 뽑도록, * 벡터 $$c$$ 는 $$sym\_1$$ 을 뽑도록, 계수를 배치하면, 다음이 된다. $$a\_0=\[0, 1, 0, 0, 0, 0], ;b\_0=\[0, 1, 0, 0, 0, 0], ;c\_0=\[0, 0, 0, 1, 0, 0]$$ 따라서 제약은 $$x \cdot x = sym\_1$$ 과 동일한 형태가 된다. 이 작업을 네 개의 제약 모두에 대해 진행하면,\ 각 제약마다 하나의 $$(a\_i,b\_i,c\_i)$$ 벡터가 생긴다.
#### 행렬 A, B, C로 묶기 모든 제약에 대해 정의한 $$a\_i,b\_i,c\_i$$ 를 각각 행렬 $$A, B, C$$의 행(row)으로 쌓는다. 그렇게 되면 전체 제약은 한 줄로 다음과 같이 정리할 수 있다. $$(s \cdot A) \times (s \cdot B) - (s \cdot C) = 0$$ 결과적으로, R1CS는 다음 내용을 표현하는 형식이다. > “어떤 벡터 $$s$$ 를 알고 있고,\ > 이 $$s$$ 가 모든 제약을 동시에 만족하도록 하는 행렬 $$A,B,C$$ 가존재한다.” 이제 “프로그램을 올바르게 계산했다”는 뜻은\ “어떤 벡터 $$s$$ 가 존재해 R1CS 제약을 모두 만족한다”는 말로 바뀐다.
### 3단계: R1CS → QAP (Quadratic Arithmetic Program) #### 여러 제약을 하나의 다항식으로 압축 R1CS는 행렬·벡터 기반 표현이기 때문에,\ 이를 그대로 SNARK에 사용하기보다는 **다항식(Polynomial)** 형태로 변환하는 편이 좋다. QAP(Quadratic Arithmetic Program)는\ “여러 개의 R1CS 제약을 하나의 다항식 나눗셈 관계로 압축하는 방법”이다. #### 각 제약을 평가점으로 보고 다항식을 만들기 아이디어는 다음과 같다. 1. 각 제약(행)을 서로 다른 평가점에 대응시킨다.\ 예를 들어, 4개의 제약이 있다면\ $$x = 1, 2, 3, 4$$\ 에 각각 대응시킨다. 2. 행렬 $$A,B,C$$ 의 각 **열(column)** 을 기준으로,\ 각 제약 위치에서의 계수들을 이용하여\ 라그랑주 보간을 통해 $$A\_i(x),B\_i(x),C\_i(x)$$ 같은 다항식을 만든다. 예시로\ $$A\_1(x)$$ 는 (1, 0), (2, 0), (3, 0), (4, 5)를 지난다는 것을 알 수 있습니다. 그래서 이 네점을 지나는 하나의 삼차 방정식을 구한다. 이렇게 하면, 변수 벡터 s 에 대해 다음과 같은 다항식이 정의된다. $$A(x) = \sum\_i A\_i(x),s\_i,\quad B(x) = \sum\_i B\_i(x),s\_i,\quad C(x) = \sum\_i C\_i(x),s\_i$$ 제약이 제대로 구성되어 있다면, 모든 제약 위치 $$x = 1, 2, 3, 4$$에서 $$A(x) \cdot  B(x)−C(x)=0$$ 이 되어야 한다. 즉, 다항식 $$A(x) \cdot  B(x)−C(x)$$는 타깃 다항식 $$Z(x)=(x−1)(x−2)(x−3)(x−4)$$ 를 인수로 가져야 한다. 이를 한 줄로 쓰면 다음과 같다. \ $$A(x)\cdot  B(x)−C(x)=Z(x) T(x)$$
여기서 * $$Z(x)$$ 는 위와 같은 타깃 다항식이다. * $$T(x)$$는 어떤 몫 다항식이다. 따라서 명제는 다음처럼 바뀐다. > “나는 어떤 함수 $$f$$를 만족하는 $$x$$ 값이 있는 벡터 $$s$$ 를 알고 있고, \ > 이에 해당하는 다항식 $$A(x),B(x),C(x)$$를 구성하면\ > $$A(x) B(x)−C(x)$$가 $$Z(x)$$ 로 나누어 떨어지는 $$T(x)$$ 를 갖는다.” Prover는 “이런 $$T(x)$$ 를 알고 있다”는 사실을 증명하게 된다.
### 4단계: KZG Polynomial Commitment 이제 QAP 단계까지 오면,\ “어떤 다항식 $$T(x)$$ 를 알고 있다”는 사실을 증명해야 한다.\ 이를 위해 널리 사용되는 구조 중 하나가 **KZG Polynomial Commitment**이다. #### Polynomial Commitment의 역할 Polynomial Commitment Scheme은 다음 두 가지를 동시에 만족해야 한다. 1. 숨김(Hiding)이다. * 다항식의 계수 $$p\_i$$ 를 직접 공개하지 않고도,\ “이 다항식에 commit했다”라는 사실만 보여준다. 2. 결속성(Binding)이다. * 한 번 어떤 다항식에 commit한 뒤에는,\ 나중에 슬그머니 다른 다항식으로 바꾸는 것이 불가능해야 한다. KZG는 타원곡선 위의 군과 쌍선형 pairing 연산을 이용해\ 이러한 Polynomial Commitment를 구현한다. #### Setup (Trusted Setup / Powers of Tau) Commitment에 사용되는 Secret Key(SK)와 Public Key(PK)를 만든다. KZG Commitment은 타원 곡선의 Pairing 특성을 사용하기 때문에 $$G$$에서 generator를 고르고, 랜덤한 값으로 $$a$$를 고릅니다. 타원곡선 pairing 특성을 통해 $$G$$를 확장하면 $$G\_2$$ 가 등장한다. $$PK= G, aG, a^2G, \dots, a^tG, a^0G\_2, aG\_2$$ PK는 generator에 SK를 곱하면서 만든다. 이후 개인키는 사용하지 않기 때문에 폐기한다.\ 이렇게 만든 PK를 혼자서 만드면 Prover가 가짜 증명을 만들 수 있기 때문에 여러 사람이 참여하여 PK를 만든다. 다른 사람이 $$a\_1$$ 을 랜덤으로 뽑아 PK 만드는 절차를 반복한다. $$SK = \$$ $$PK= a\_0^0a\_1^0G, a\_0^1a\_1^1G, a\_0^2a\_1^2G, \dots, a\_0^ta\_1^tG, a^0\_0a\_1^0G\_2, a^1\_0a\_1^1G\_2$$ 여기서 $$SK$$ 값을 Power of tau를 이용하여 정리하면 $$\tau^i = a\_k^ia\_{k-1}^i \dots a\_0^i$$\ $$SK = <\tau^0, \tau^1, \dots, \tau^t>$$\ $$PK = <\tau^0G, \tau^1G, \cdots, \tau^tG, \tau^0G\_2, \tau^1G\_2>$$ 로 만들 수 있다. 여러 사람이 순차적으로 $$\tau$$ 에 기여하고,\ 각 사람은 자신의 기여분을 로컬에서 지운 뒤,\ 마지막 결과만 남기는 구조를 **Powers of Tau ceremony**라고 부른다. 정상적으로 진행된다면, 모든 참여자의 비밀을 합친 전체 $$\tau$$ 를 아는 사람은 존재하지 않는다.
#### Commit 단계이다 다항식 $$P(x) = p\_0 + p\_1 x + \dots + p\_t x^t$$ 에 대해, Prover는 다음과 같은 값을 계산한다. $$P(\tau),G\_1 = \sum\_{i=0}^t p\_i,\tau^i,G\_1$$ 이 값이 $$P(x)$$ 에 대한 **commit 값**입니다. 이를 보통 $$P\_{\text{com}}$$같은 기호로 표기한다. 검증자는 $$P\_{\text{com}}$$을 보고 * “어떤 다항식 $$P(x)$$ 에 대한 commit이 있구나”라는 것만 알 수 있고, * 실제 계수 $$p\_i$$ 는 알 수 없다. 또한 Prover는 한 번 $$P\_{\text{com}}$$ 을 공개하고 나면, 다른 다항식으로 바꾸기가 매우 어렵다(결속성).
#### Challenge & Proof: “P(u) = v” 를 증명 이제 Verifier가 Prover에게 다음과 같이 질문한다고 가정한다. > “정말로 $$P(x)$$ 를 알고 있습니까?\ > 그렇다면 제가 정한 점 $$u$$ 에서의 값 $$P(u)$$ 가 무엇인지 알려 주십시오.” 이때 Prover는 1. $$v=P(u)$$ 를 계산한다. 2. 그리고 $$P(x) - v$$가 $$(x−u)$$ 로 나누어 떨어지도록, 몫 다항식 $$Q(x)$$ 를 계산한다.\ 즉, $$P(x)−v=(x−u) Q(x)$$ 를 만족하게 $$Q(x)$$ 를 찾는다. 3. Prover는 $$v$$ 와 $$Q(x)$$ 에 대한 commit $$Q\_{\text{com}}$$을 Proof로 함께 보낸다. Fiat–Shamir 변환을 사용하면,\ Challenge $$u$$ 를 Verifier가 직접 보내는 대신, $$u = H(P\_{\text{com}}, \dots)$$처럼 해시로 정하게 만들어\ 전체 과정을 **비대화형(Non-Interactive)** 으로 바꿀 수 있다.
#### Verifier 검증 Verifier는 $$P(u)=v$$ 가 성립하는지를 확인함으로 Prover가 $$P(x)$$를 알고 있는지 검증을 한다. 검증 과정은 $$P(u)=v$$ 가 성립한다는 것은 $$P(x)−v=(x−u)Q(x)$$의 식이 성립하고, Commit에 사용된 값 τ 를 넣어주면 $$P(τ)−v=(τ−u)Q(τ)$$ 다음과 같은 식이 된다. 이것을 검증하기 위해 타원곡선의 Pairing 성질을 활용해 $$e(G\_1,G\_2)^{P(τ)−v}=e(G\_1,G\_2)^{Q(τ)(τ−u)}$$ 가 성립하는지 확인한다. 타원곡선의 Pairing은 다음과 같은 성질을 가진다.\ $$e(aP,bQ)=e(P,bQ)^a=e(P,aQ)^b=e(P,Q)^{ab}$$ 따라서 $$e((P(τ)−v)G\_1,G\_2)=e(Q(τ)G\_1,(τ−u)G\_2)$$ 이런 식이 되고 \ Prover가 전달한 값인 $$P(τ)G\_1,vG\_1,Q(τ)G\_1$$ 과 공개 검증키를 통해 계산이 가능해진다.
### ZK-SNARK 요약 지금까지의 내용을 한 번에 정리하면,\ 일반적인 ZK-SNARK는 다음 단계를 거쳐 동작한다. 1. 프로그램 $$f$$ 와 명제 설정 * “나는 입력 $$x$$ 를 알고 있고,\ $$y=f(x)$$ 를 만족합니다.”라는 명제를 증명하고자 한다. 2. **Function → Arithmetic Circuit 단계** * 프로그램을 덧셈·곱셈 게이트로 쪼개어 산술 회로로 표현한다. 3. **Circuit → R1CS 단계** * 회로의 각 게이트를\ $$(s \cdot a\_i),(s \cdot b\_i) = (s \cdot c\_i)$$\ 형태의 제약으로 만들고, 이를 행렬 $$A, B, C$$로 묶어 R1CS로 표현한다. * “어떤 벡터 $$s$$ 가 존재해 R1CS를 만족한다”는 말이\ “프로그램 실행이 올바르다”는 의미가 된다. 4. **R1CS → QAP 단계이다.** * 각 제약을 서로 다른 평가점(예: $$x=1,2,3,…$$)에 대응시킨 뒤,\ 다항식 $$A(x), B(x), C(x)$$를 구성한다. * 이때 $$A(x) B(x)−C(x)$$ 가 타깃 다항식 $$Z(x)$$ 로 나누어 떨어지는지 여부가\ “모든 제약을 만족하는지”를 나타낸다. 5. **다항식 → Polynomial Commitment (예: KZG) 단계이다.** * Prover는 해당 다항식에 commit하고, * Verifier는 임의의 점 $$u$$에서 $$P(u)$$ 가 맞는지\ pairing 기반 검증으로 확인한다. * 이때 Zero-Knowledge용 블라인딩을 추가하면,\ 비밀 값들은 그대로 숨기면서 검증이 가능하다. 6. **최종적으로 ZK-SNARK가 된다.** * Fiat–Shamir를 이용해 비대화형으로 만들고, * 증명 크기는 작게 유지하면서, * 영지식성과 soundness를 함께 만족하는 구조가 된다. 이 구조 덕분에, 블록체인에서는 * 오프체인에서 복잡한 계산을 수행하고, * 온체인에서는 **짧은 증명 하나**만 검증함으로써 * 프라이버시(Zero-Knowledge)와 스케일링(SNARK의 간결성)을 동시에 달성할 수 있다. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-1/groth16/snark.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.