Zk-SNARKs：엔진 덮개 아래

저자: Vitalik Buterin

원제목: 《Zk-SNARKs: Under the Hood》

발표 시간: 2017년 2월 1일

이 글은 zk-SNARKs 뒤에 있는 기술이 어떻게 작동하는지를 설명하는 일련의 글 중 세 번째 부분입니다. 이전의 이차 산술 프로그램 및 타원 곡선 쌍에 대한 글은 필독이며, 본문은 이 두 개념에 대한 지식을 전제로 합니다. 또한 zk-SNARK가 무엇인지 및 그것들이 무엇을 하는지에 대한 기본 지식도 전제합니다. 추가로, 기술 소개를 위해 Christian Reitwiessner의 글도 참조하시기 바랍니다.

이전 글에서는 이차 산술 프로그램을 소개했습니다. 이는 다항식 방정식을 사용하여 모든 계산 문제를 표현하는 방법으로, 다양한 형태의 수학적 기법에 더 적합합니다. 또한, 우리는 타원 곡선 쌍을 소개했으며, 이는 매우 제한된 단방향 동형 암호화 형태를 허용하여 동등성 검사를 수행할 수 있게 합니다. 이제 우리는 지난 번 중단한 지점에서 시작하여 타원 곡선 쌍 및 기타 몇 가지 수학적 기법을 사용하여 증명자가 특정 QAP의 해결책을 알고 있음을 증명할 수 있도록 하면서 실제 해결책에 대한 어떤 정보도 공개하지 않도록 하겠습니다.

이 글에서는 Parno, Gentry, Howell 및 Raykova가 2013년부터 시작한 Pinocchio 프로토콜 (일반적으로 PGHR13이라고 불림)에 중점을 두겠습니다. 기본 메커니즘에는 몇 가지 변화가 있으므로 실제로 구현된 zk-SNARK 스킴은 약간 다를 수 있지만, 기본 원리는 일반적으로 변하지 않습니다.

먼저, 우리가 사용할 메커니즘의 보안 뒤에 있는 핵심 암호 가정인 지수 지식 가정을 살펴보겠습니다.

기본적으로, P와 Q라는 점 쌍을 얻었고, 여기서 P * k = Q이며, 점 C를 얻었다고 가정해 보겠습니다. 그러면 C가 어떤 방식으로든 P에서 "파생"되지 않는 한, C * k를 아는 것은 불가능합니다. 이것은 직관적으로 보일 수 있지만, 이 가정은 실제로 우리가 일반적으로 타원 곡선 기반 프로토콜의 보안을 증명할 때 사용하는 다른 어떤 가정(예: 이산 로그의 난이도)에서도 유도될 수 없습니다. 따라서 zk-SNARK는 실제로 타원 곡선 암호학보다 더 일반적이고 불안정한 기초에 의존합니다. 그럼에도 불구하고, 그것은 여전히 대부분의 암호학자들이 수용할 수 있을 만큼 충분히 강력합니다.

이제 이를 사용하는 방법을 살펴보겠습니다. P와 Q라는 점 쌍이 하늘에서 떨어졌고, 여기서 P * k = Q이며, 아무도 k의 값이 무엇인지 모른다고 가정해 보겠습니다. 이제 내가 R와 S라는 점 쌍을 제시한다고 가정해 보겠습니다. 여기서 R * k = S입니다. 그러면 KoE 가정은 내가 이 점 쌍을 얻는 유일한 방법은 P와 Q를 가져와서 내가 개인적으로 알고 있는 어떤 인자 r로 두 점을 곱하는 것임을 의미합니다. 또한, 타원 곡선 쌍의 마법 덕분에 R = k * S를 확인하는 것은 실제로 k를 알 필요가 없습니다. 반대로, e(R, Q) = e(P, S)를 간단히 확인할 수 있습니다.

좀 더 흥미로운 일을 해봅시다. 하늘에서 떨어진 열 쌍의 점이 있다고 가정해 보겠습니다: (P1, Q1), (P2, Q2)… (P10, Q10). 모든 경우에 Pi * k = Qi입니다. 내가 이후에 R와 S라는 점 쌍을 제공한다고 가정해 보겠습니다. 여기서 R * k = S입니다. 당신은 지금 무엇을 알고 있습니까? 당신은 R이 어떤 선형 조합 P1 * i1 + P2 * i2 + … + P10 * i10이라는 것을 알고 있습니다. 여기서 나는 계수 i1, i2 … i10을 알고 있습니다. 즉, 이렇게 점 쌍 (R, S)를 얻는 유일한 방법은 P1, P2…P10의 어떤 배수를 취하고 그것들을 더한 다음 Q1, Q2…Q_10에 대해 동일한 계산을 수행하는 것입니다.

특정 P1…P10 점 집합에 대해 선형 조합을 확인하고자 할 때, k가 무엇인지 모르는 상태에서 Q1…Q10 점을 생성할 수 없다는 점에 유의하십시오. 만약 k가 무엇인지 알고 있다면, 당신은 원하는 어떤 R에 대해서도 R * k = S인 점 쌍 (R, S)를 생성할 수 있으며, 선형 조합을 생성할 필요가 없습니다. 따라서 이를 작동시키기 위해서는 이러한 점을 생성하는 사람이 신뢰할 수 있어야 하며, 열 개의 점을 생성한 후 실제로 k를 삭제해야 합니다. 이것이 "신뢰할 수 있는 설정" 개념의 출처입니다.

QAP의 해는 다음과 같은 다항식 집합 (A, B, C)입니다: A(x) * B(x) - C(x) = H(x) * Z(x), 여기서:

• A는 다항식 집합 {A1…Am}의 선형 조합입니다.
• B는 동일한 계수를 가진 {B1…Bm}의 선형 조합입니다.
• C는 동일한 계수를 가진 {C1…Cm}의 선형 조합입니다.

집합 {A1…Am}, {B1…Bm} 및 {C1…Cm}과 다항식 Z는 문제 진술의 일부입니다.

그러나 대부분의 실제 경우에 A, B 및 C는 매우 큽니다. 해시 함수와 같은 수천 개의 회로 게이트를 가진 경우, 다항식(및 선형 조합의 인자)은 수천 개의 항을 가질 수 있습니다. 따라서 우리는 증명자가 선형 조합을 직접 제공하도록 하지 않고, 위에서 소개한 기법을 사용하여 증명자가 제공한 것이 선형 조합임을 증명하게 하되, 다른 어떤 것도 공개하지 않도록 합니다.

당신은 아마도 위의 기법이 다항식이 아니라 타원 곡선 점에 적용된다는 것을 주목했을 것입니다. 따라서 실제로 발생하는 것은 우리가 신뢰할 수 있는 설정에 다음 값을 추가하는 것입니다:

G * A1(t), G * A1(t) * ka G * A2(t), G * A2(t) * ka
…
G * B1(t), G * B1(t) * kb G * B2(t), G * B2(t) * kb
…
G * C1(t), G * C1(t) * kc G * C2(t), G * C2(t) * kc
…
t를 다항식을 계산하는 "비밀 점"으로 볼 수 있습니다. G는 "생성기"입니다(프로토콜의 일부로 지정된 일부 임의의 타원 곡선 점)이며, t, ka, kb 및 kc는 "유독한 폐기물"로, 반드시 어떤 대가를 치르더라도 삭제해야 하는 숫자입니다. 이 숫자를 가진 사람은 가짜 증명을 만들 수 있습니다. 이제 누군가 P, Q 점 쌍을 제공하여 P * ka = Q가 성립한다면(상기: 우리는 이를 확인하기 위해 ka를 알 필요가 없습니다. 우리는 쌍 검사를 수행할 수 있습니다), 그러면 당신은 그들이 제공한 것이 t에서 평가된 Ai 다항식의 선형 조합이라는 것을 알 수 있습니다.

따라서 지금까지 증명자는 다음을 제공해야 합니다:

πa = G * A(t), π'a = G * A(t) * ka πb = G * B(t), π'b = G * B(t) * kb
πc = G * C(t), π'c = G * C(t) * k_c

증명자는 실제로 (또는 알아서는 안 됩니다!) t, ka, kb 또는 k_c를 알고 있지 않아도 이러한 값을 계산할 수 있어야 합니다. 반대로, 증명자는 우리가 신뢰할 수 있는 설정에 추가한 점만을 기반으로 이러한 값을 계산할 수 있어야 합니다.

다음 단계는 모든 세 개의 선형 조합이 동일한 계수를 가지도록 하는 것입니다. 우리는 신뢰할 수 있는 설정에 또 다른 값 집합을 추가하여 이를 수행할 수 있습니다: G * (Ai(t) + Bi(t) + C_i(t)) * b, 여기서 b는 또 다른 "유독한 폐기물"로 간주되어야 하는 숫자이며, 신뢰할 수 있는 설정이 완료된 후 즉시 폐기됩니다. 그런 다음 우리는 증명자가 동일한 계수를 가진 이러한 값으로 선형 조합을 생성하고, 위와 동일한 쌍 검사를 사용하여 해당 값이 제공된 A + B + C와 일치하는지 확인하도록 할 수 있습니다.

마지막으로, 우리는 A * B - C = H * Z를 증명해야 합니다. 우리는 쌍 검사를 통해 다시 이 작업을 수행합니다:

e(πa, πb) / e(πc, G) ?= e(πh, G * Z(t))

여기서 π_h = G * H(t)입니다. 이 방정식과 A * B - C = H * Z 간의 관계가 당신에게 의미가 없다면, 쌍에 대한 글을 다시 읽어보시기 바랍니다.

우리는 위에서 A, B 및 C를 타원 곡선 점으로 변환하는 방법을 보았습니다. G는 단순히 생성기입니다(즉, 타원 곡선 점은 숫자 1에 해당합니다). 우리는 G * Z(t)를 신뢰할 수 있는 설정에 추가할 수 있습니다. H는 더 어렵습니다. H는 단순한 다항식이며, 우리는 각 개별 QAP 해결책의 계수를 미리 예측하는 경우가 드뭅니다. 따라서 우리는 신뢰할 수 있는 설정에 더 많은 데이터를 추가해야 합니다. 구체적인 순서는 다음과 같습니다:

G, G * t, G * t², G * t³, G * t⁴ …。

Zcash 신뢰할 수 있는 설정에서는 이 시퀀스가 약 200만에 달합니다. 이는 H(t)를 항상 계산할 수 있도록 보장하기 위해 필요한 거듭제곱의 수입니다. 적어도 그들이 관심 있는 특정 QAP 인스턴스에 대해 말입니다. 이렇게 하면 증명자는 검증자가 최종 검사를 수행하는 데 필요한 모든 정보를 제공할 수 있습니다.

우리가 논의해야 할 또 다른 세부 사항이 있습니다. 대부분의 경우, 우리는 단순히 특정 문제의 해결책이 존재한다는 것을 추상적으로 증명하고자 하는 것이 아닙니다. 반대로, 우리는 특정 해결책의 정확성을 증명하고자 합니다(예: "cow"라는 단어를 사용하고 이를 SHA3 해시로 백만 번 처리했을 때 최종 결과가 0x73064fe5로 시작함을 증명하거나, 해결책이 특정 매개변수를 가지고 존재함을 증명하는 것입니다). 예를 들어, 거래 금액과 계좌 잔액이 암호화된 암호화폐 인스턴스에서, 당신은 어떤 해독 키 k를 알고 있음을 증명하고 싶습니다. 이렇게:

암호화된 oldbalance, txvalue 및 new_balance는 공개적으로 지정되어야 합니다. 이는 우리가 특정 시점에 검증하고자 하는 특정 값이기 때문입니다. 오직 해독 키만 숨겨져야 합니다. 특정 입력의 제한에 해당하는 "사용자 정의 검증 키"를 생성하기 위해 프로토콜에 약간의 수정이 필요합니다.

이제 한 걸음 물러나 보겠습니다. 먼저, 여기 ben Sasson, Tromer, Virza 및 Chiesa가 제공한 전체 검증 알고리즘이 있습니다:

첫 번째 줄은 매개변수를 처리합니다. 본질적으로, 이는 특정 매개변수가 지정된 문제의 특정 인스턴스를 위한 "사용자 정의 검증 키"를 생성하는 기능으로 볼 수 있습니다. 두 번째 줄은 A, B, C의 선형 조합 검사를 수행합니다. 세 번째 줄은 선형 조합이 동일한 계수를 가지는지 확인합니다. 네 번째 줄은 A * B - C = H * Z의 곱셈 검사를 수행합니다.

결론적으로, 검증 과정은 몇 개의 타원 곡선 곱셈(각 "공공" 입력 변수마다 하나)과 다섯 번의 쌍 검사로 구성되며, 그 중 하나는 추가 쌍 곱셈을 포함합니다. 증명에는 여덟 개의 타원 곡선 점이 포함됩니다: A(t), B(t) 및 C(t) 각각에 대해 점 쌍이 하나씩 있으며, b * (A(t) + B(t) + C(t))에 대해 점 πk가 하나 있습니다. 또한 H(t)의 점 πh가 있습니다. 이 중 일곱 개의 점은 Fp 곡선에 있으며(각각 32바이트, y 좌표를 비트로 압축할 수 있기 때문입니다), Zcash 구현에서는 점 (πb)가 F_p²의 왜곡 곡선에 위치해 있습니다(64바이트). 따라서 증명의 총 크기는 약 288바이트입니다.

증명을 생성하는 두 가지 계산적으로 가장 어려운 부분은:

(A * B - C) / Z를 나누어 H를 얻는 것입니다(빠른 푸리에 변환 기반 알고리즘을 사용하면 이 작업을 이차 시간 내에 수행할 수 있지만, 여전히 계산량이 많습니다)
타원 곡선 곱셈 및 덧셈 연산을 수행하여 A(t), B(t), C(t) 및 H(t) 값과 해당 쌍을 생성하는 것입니다
증명이 이렇게 어려운 기본 이유는, 우리가 제로 지식 증명을 만들기 위해 원래 계산의 단일 이진 논리 게이트가 타원 곡선 작업을 통해 암호화 처리되어야 하기 때문입니다. 이 사실과 빠른 푸리에 변환의 초선형성 덕분에 Zcash 거래의 증명 생성에는 약 20-40초가 소요됩니다.

또 다른 매우 중요한 질문은: 우리는 신뢰할 수 있는 설정을 조금 더…… 신뢰할 필요가 없도록 만들 수 있을까요? 불행히도, 우리는 그것을 완전히 신뢰하지 않도록 만들 수는 없습니다. KoE 가정 자체가 k가 무엇인지 모르는 상태에서 독립적인 쌍 (Pi, Pi * k)을 만드는 것을 배제합니다. 그러나 우리는 N-of-N 다자간 계산을 사용하여 보안을 크게 향상시킬 수 있습니다. 즉, N 당사자 간에 신뢰할 수 있는 설정을 구축하여, 최소한 한 명의 참여자가 그들의 유독한 폐기물을 삭제하면 안전하게 만들 수 있습니다.

이 작업을 수행하는 방법에 대한 간단한 알고리즘이 있습니다. 기존 집합(G, G * t, G * t², G * t³…)을 가져와서 "당신의 비밀"을 추가하여, 당신의 비밀과 이전의 비밀(또는 이전의 비밀 집합)이 필요하도록 만드는 것입니다.

출력 집합은 간단합니다:

G, (G * t) * s, (G * t²) * s², (G * t³) * s³…

당신은 원래 집합과 s만 알고 있어도 이 집합을 생성할 수 있으며, 새로운 집합의 기능은 이전 집합과 동일합니다. 단지 이제 t*s를 "유독한 폐기물"로 사용하고 t를 사용하지 않습니다. 당신과 이전 집합을 생성한 사람(또는 여러 사람)이 당신의 유독한 폐기물을 삭제하지 않고 공모하지 않는 한, 해당 집합은 "안전합니다".

신뢰할 수 있는 설정을 위해 이를 수행하는 것은 훨씬 더 어렵습니다. 여러 값이 포함되며, 알고리즘을 여러 라운드에 걸쳐 당사자 간에 완료해야 합니다. 이는 활발히 연구되고 있는 분야로, 다자간 계산 알고리즘을 더욱 간소화하고 더 적은 라운드 또는 더 병렬화할 수 있도록 하는 방법을 모색하고 있습니다. 당신이 할 수 있는 일이 많을수록 신뢰할 수 있는 설정 과정에 참여하는 당사자가 많아집니다. 서로 알고 함께 일하는 여섯 명의 참여자 간의 신뢰 설정이 일부에게 불편하게 느껴질 수 있는 이유를 이해할 수 있습니다. 그러나 수천 명의 참여자가 있는 신뢰 설정은 완전히 신뢰하지 않는 것과 거의 차이가 없습니다. 그리고 만약 당신이 정말로 편집증적이라면, 당신은 직접 설정 과정에 참여하고 당신의 값을 직접 삭제할 수 있습니다.

또 다른 활발한 연구 분야는 쌍을 사용하지 않고도 동일한 목표를 달성하기 위한 다른 방법과 동일한 신뢰할 수 있는 설정 예제를 사용하는 것입니다. Eli ben Sasson의 최근 발표를 참조하여 또 다른 선택지를 확인하시기 바랍니다(단, 수학적으로 SNARK와 동일하게 복잡하다는 점에 유의하십시오!).

Ariel Gabizon과 Christian Reitwiessner의 검토에 특별히 감사드립니다.