영지식 증명: 기본 원리 소개

소개

영지식 증명은 암호학자들이 고안한 가장 강력한 도구 중 하나입니다. 하지만 일반인에게는 잘 알려져 있지 않습니다. 이 글은 영지식 증명을 기본 원리부터 종합적으로 설명해 이러한 간극을 해소합니다. 영지식 증명의 이론, 수학, 암호학을 다루며 누구나 Solana의 최신 발전, 특히 ZK Compression과 상호운용성의 미래를 이해할 수 있도록 돕습니다.

이 글은 Solana의 프로그래밍 모델과 블록체인 시스템에 내재된 암호학적 기본 요소(예: 해시 함수, 해시 포인터, 머클 트리, 동시성 머클 트리)를 알고 있다고 가정합니다. 이러한 개념이 생소하다면 먼저 다음 블로그 글을 읽어보세요.

• 암호학 도구 101 — 해시 함수와 머클 트리 설명
• Solana 프로그래밍 모델: Solana 개발 입문

이 글은 모듈식으로 구성되었습니다. 이 주제를 처음 접한다면 각 섹션과 하위 섹션을 순서대로 읽는 것이 좋습니다. 특정 주제에 익숙하거나 원하는 주제만 알아보고 싶다면 해당 섹션으로 바로 이동해도 무방합니다.

또한 이 글은 영지식 증명을 다루는 2부작 시리즈의 첫 번째 글입니다. 영지식 증명: Solana에서의 활용로 넘어가기 전에 이 글을 먼저 읽어보시길 강력히 권합니다.

영지식 증명의 이론

1989년 MIT 연구원 Shafi Goldwasser, Silvio Micali(Algorand 창립자), Charles Rackoff는 상호작용형 증명 시스템의 지식 복잡도를 발표했습니다. 이들은 한 당사자, 즉 증명자가 다른 당사자, 즉 검증자와 메시지를 주고받으며 어떤 수학적 명제가 참임을 납득시키는 시스템을 연구했습니다. 이들은 최초로 “증명자와 검증자가 서로를 신뢰하지 않는다면 어떻게 될까?”라는 질문을 던졌습니다. 여기서 중요한 문제는 메시지를 주고받는 동안 검증자가 해당 명제가 참이라는 사실 외에 얼마나 많은 정보를 알게 되는가입니다. 예를 들어 증명자는 복잡한 퍼즐의 해답 자체를 공개하지 않고도 자신이 해답을 알고 있음을 검증자에게 증명하고 싶을 수 있습니다.

애초에 어떤 문제를 해결하려는 것일까요?

그래프 3색 칠하기

그래프 3색 칠하기는 컴퓨터 과학과 그래프 이론의 고전적인 문제입니다. 인접한 꼭짓점끼리 같은 색을 공유하지 않도록 세 가지 색으로 그래프의 꼭짓점을 칠합니다. 꼭짓점이 세 개인 그래프에서는 간단합니다. 하지만 꼭짓점 수가 늘어날수록 난도가 급격히 높아집니다.

실제 활용 사례로 대학 시간표 편성을 들 수 있습니다. 대규모 대학에서는 어떤 학생도 수업 시간이 겹치지 않도록 시간표를 만들어야 합니다. 각 수업은 그래프의 꼭짓점으로 나타내고, 간선은 두 수업을 함께 듣는 학생이 있음을 나타냅니다. 이를 통해 같은 학생이 듣는 두 수업이 동시에 배정되지 않도록 할 수 있습니다. 이 밖에도 강의실 수용 인원, 교수의 선호 시간, 일주일 동안 수업을 고르게 분산하는 조건 등을 고려해야 합니다. 따라서 인접한 두 수업이 같은 시간대를 공유하지 않도록 수업에 시간대와 강의실을 배정해야 합니다. 그래프 3색 칠하기로 이를 해결할 수 있습니다.

이제 외부 감사 기관이 최종 시간표를 검증해야 한다고 가정해 보겠습니다. 특정 개인정보 보호 규정 때문에 대학은 상세한 학생 수강 정보를 감사 기관과 공유할 수 없습니다. 대신 어떤 학생이 어떤 수업에 등록했는지 공개하지 않으면서 최종 시간표가 필요한 제약 조건을 충족한다는 사실을 증명해야 합니다. 

이를 위해 대학은 각 꼭짓점이 하나의 수업을 나타내는 그래프를 만들어야 합니다. 해당 수업에 공통으로 등록한 학생이 한 명 이상이면 두 꼭짓점 사이에 간선을 그립니다. 대학은 인접한 두 수업이 동시에 진행되지 않도록 각 수업에 시간대를 배정합니다. 그런 다음 암호학적 커밋먼트 방식을 사용해 완성된 시간표를 커밋합니다. 각 수업에 배정된 시간대의 암호학적 해시를 생성하고, 시간대 자체는 공개하지 않은 채 검증자와 해시를 공유합니다. 이후 외부 감사 기관은 인접한 수업 쌍을 무작위로 선택해 배정된 시간대에 이의를 제기합니다. 대학은 선택된 인접 수업 쌍에 대해 커밋된 시간대를 공개하고 원래 커밋먼트, 즉 해시를 제공하여 외부 감사 기관이 공개된 값을 검증할 수 있게 합니다. 외부 감사 기관이 겹치는 수업이 없다고 확신할 때까지 이의 제기, 공개, 검증의 마지막 단계를 반복합니다. 이러한 과정을 실시간으로 확인하려면 MIT의 상호작용형 영지식 3색 칠하기 데모를 적극 권합니다.

대학은 올바른 시간표를 알고 있다는 사실을 외부 감사 기관에 증명하려 합니다. 즉, 어떤 사실을 알고 있음을 다른 당사자에게 증명하려는 것입니다. 이 문제의 장점은 NP-완전이라는 데 있습니다.

NP-완전

계산 복잡도 이론에서 문제는 다음 조건을 충족할 때 NP-완전입니다.

• 문제의 어떤 입력에 대해서도 출력은 “예” 또는 “아니요”입니다
• 답이 “예”라면 짧은 해답으로 이를 입증할 수 있습니다
• 각 해답의 정확성을 빠르게 검증할 수 있어야 하며, 무차별 대입 알고리즘은 가능한 모든 해답을 시도해 답을 찾을 수 있습니다

NP-완전 문제는 NP 클래스에서 가장 어려운 문제를 대표하므로 중요합니다. 즉, 추측한 해답을 다항 시간 내에 검증하기는 쉽지만 해답을 찾기는 매우 어려운 퍼즐의 집합입니다. 이러한 문제는 보편적으로 시뮬레이션할 수 있다는 특징이 있습니다. 즉, 하나의 NP-완전 문제를 빠르게 풀 수 있다면 어떤 NP 문제든 NP-완전 문제로 환원하거나 변환하여 다항 시간 내에 해답을 찾을 수 있습니다. NP-완전 문제의 해답을 검증하는 것도 쉽습니다. 

따라서 영지식 증명으로 효율적으로 증명할 수 있는 전체 문제 클래스가 존재합니다. 예를 들면 다음과 같습니다.

• 외판원 문제 — 도시 목록과 각 도시 쌍 사이의 거리가 주어졌을 때, 모든 도시를 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾습니다. 물류, 경로 계획, 제조, 공급망 관리 등 다양한 분야에 활용됩니다
• 배낭 문제 — 물품 집합이 주어졌을 때, 총무게가 주어진 한도 이하이면서 총가치가 최대가 되도록 모음에 포함할 각 물품의 수를 결정합니다. 금융과 자원 배분 분야에서 흔히 다루는 문제입니다
• 작업 스케줄링 — 정해진 소요 시간과 마감 기한이 있는 작업 집합을 하나의 기계에 배정하여 지연 작업에 따른 총페널티를 최소화합니다. 컴퓨팅, 제조, 프로젝트 관리에 폭넓게 활용됩니다

또한 쿡-레빈 정리는 불리언 충족 가능성 문제가 NP-완전이라고 말합니다. 즉, 변수에 참 또는 거짓 값을 대입해 최종적으로 참이 되도록 할 수 있는 모든 문제는 NP-완전 문제로 변환할 수 있습니다. 이는 참과 거짓으로 이루어진 일련의 질문으로 환원할 수 있는 모든 문제를 영지식 증명으로 효율적으로 증명할 수 있음을 뜻합니다.

영지식 증명의 속성

NP-완전 문제의 복잡성과 중요성을 고려하면 이 문제 클래스의 해답을 효율적이고 안전하게 증명하는 것이 매우 중요합니다. 영지식 증명을 사용하면 관련 정보의 개인정보 보호를 훼손하지 않고 이를 수행할 수 있습니다. Goldwasser, Micali, Rackoff는 모든 영지식 증명이 다음 속성을 충족해야 한다고 제안했습니다.

• 완전성 — 증명자가 정직하다면 결국 검증자를 납득시킵니다
• 건전성 — 부정한 증명자는 거짓 명제로 검증자를 절대 납득시키지 못합니다
• 영지식성 — 증명자와 검증자의 상호작용은 명제가 참인지 여부만 드러내며 그 밖의 정보는 공개하지 않습니다

영지식 증명의 강력한 속성을 활용하면 다양한 상황에서 특정 사실이나 정보에 대한 지식을 개인정보를 보호하면서도 정확하게 증명할 수 있습니다. 이후 섹션에서는 블록체인처럼 높은 수준의 보안과 효율성이 필요한 애플리케이션에서 이것이 왜 중요한지 살펴봅니다.

상호작용형과 비상호작용형

영지식 증명은 대체로 동일한 3단계 구조를 따릅니다.

• 증명자가 계산의 해답, 즉 증인을 생성한 뒤 증인의 답에 대한 커밋먼트를 전송합니다
• 검증자가 무작위로 생성한 도전 값으로 응답합니다
• 증명자가 커밋먼트와 도전을 바탕으로 최종 증명을 계산합니다

이 구조는 본질적으로 상호작용형입니다. 증명자는 무언가를 알고 있다고 말하고, 검증자는 증명자가 자신을 속일 가능성이 무시할 수 있을 정도로 작아질 때까지 계속 도전합니다. 증명자가 완성된 증명을 생성하기 전에 하나 이상의 응답을 받아야 하므로 대부분의 애플리케이션에는 적합하지 않습니다. 이 구성에는 본질적으로 다음과 같은 문제가 있습니다.

• 검증자가 증명자와 결탁하여 가짜 증명을 만들도록 허용할 수 있습니다
• 검증자가 가짜 증명을 만들 수 있습니다
• 검증자는 비밀 값을 어딘가에 저장해야 하며, 이 값은 유출이나 공격에 취약할 수 있습니다

피아트-샤미르 휴리스틱은 상호작용형 지식 증명을 바탕으로 디지털 서명을 만드는 기법입니다. 이를 사용하면 기저 정보를 공개하지 않고 어떤 사실을 공개적으로 증명할 수 있습니다. 검증자가 증명자에게 무작위 도전 값을 보내는 대신, 증명자가 좋은 암호학적 해시 함수 같은 무작위 함수를 사용해 이 디지털 서명을 직접 계산하는 방식입니다. 따라서 검증자가 계산의 서로 다른 500개 지점을 들여다보며 모두 정확한지 확인하는 대신, 증명자가 계산의 머클 루트를 구하고 이를 사용해 500개의 인덱스를 의사 난수 방식으로 선택한 뒤 이에 해당하는 500개의 데이터 머클 브랜치를 제공합니다. 핵심은 데이터가 커밋된 후에야 증명자가 어떤 브랜치를 공개해야 하는지 알 수 있다는 점입니다.

예리한 독자라면 계산을 표본 검사하기 위해 무작위 샘플링을 적용하는 방식에 치명적인 결함이 있음을 알아차릴 수 있습니다. 계산은 본질적으로 취약합니다. 악의적인 증명자가 계산 중간에서 비트 하나만 뒤집어도 검증자는 이를 영원히 발견하지 못할 수 있습니다. 검증자가 계산의 각 부분을 개별적으로 살펴보지 않고 어떻게 모든 부분을 확인할 수 있을까요? 바로 다항식입니다.

하지만 다항식을 논하기 전에 이해해야 할 수학이 제법 많습니다.

영지식 증명의 수학

다음 수학 분야를 폭넓게 소개하려는 것은 아닙니다. 각 섹션만으로도 하나의 글이 될 수 있습니다. 여기서는 영지식 증명의 수학적 기본 원리와 높은 수준에서 실제로 작동하는 방식을 이해할 수 있도록 간략히 소개합니다.

이 글에서는 올바른 수학 표기법도 소개합니다. 예를 들어 집합론에 관한 다음 하위 섹션에서는 ∈, ∉, ⊆ 기호를 소개합니다. 결국 이 기호들은 모두 다른 무언가를 나타내는 자리표시자입니다. 영지식 증명은 초보자를 위한 주제가 아닙니다. 따라서 이 주제를 다루는 글 대부분은 초보자에게 친절하지 않습니다. 이 기호가 무엇을 뜻하는지 자세히 설명하지 않으며, 독자가 해당 표기법을 이해한다고 가정합니다. 지금 이 표기법을 소개하는 것은 영지식 증명을 더 깊이 탐구하려는 독자가 이를 덜 어렵게 느끼도록 하는 데 중요합니다. 표기법에 매몰되지 마세요. 계속 나아가다 보면 언젠가는 이 기호를 보고 그리스 문자가 아닌 기저 개념을 떠올리게 됩니다.

집합론

집합론은 객체의 모음을 연구하는 수학의 한 분야입니다. 집합은 서로 다른 객체의 모음입니다. 이러한 객체를 집합의 원소 또는 구성원이라고 합니다. 과일 모음을 예로 들어보겠습니다.

집합 표기법에서는 원소의 모음을 중괄호로 감싸 집합을 나타냅니다. 이를 통해 apple, orange, pear, banana는 집합에 속하지만 “potato” 같은 것은 속하지 않음을 알 수 있습니다. 기호 ∈은 집합의 원소임을 나타내며 “~의 원소이다”라고 읽습니다. 마찬가지로 ∉은 원소가 특정 집합에 속하지 않음을 나타냅니다. 따라서 다음과 같이 쓸 수 있습니다.

이는 “apple은 Fruit 집합의 원소이고 potato는 Fruit 집합의 원소가 아니다”라고 읽습니다.

부분집합

다른 집합으로 구성된 집합도 만들 수 있습니다. 부분집합은 다른 집합에 있는 원소만 포함하는 집합입니다. 예를 들어 다음과 같은 집합이 있다고 가정하겠습니다.

Citrus 집합은 더 큰 AllFruits 집합의 부분집합이라고 할 수 있습니다. 앞서 살펴본 Fruit 집합도 더 큰 AllFruit 집합의 부분집합이라고 할 수 있습니다. 이를 집합 표기법으로 다음과 같이 씁니다.

왜 알아야 할까요?

집합론은 범위와 제약 조건의 개념을 이해하는 데 매우 중요합니다. 다음 수론과 모듈러 산술 섹션에서는 숫자가 특정 범위 안에 있다는 개념을 살펴봅니다. 예를 들어 암호학적 키에 사용할 수 있는 값의 집합이 있을 수 있습니다.

여기서 K는 가능한 모든 키의 범위를 정의합니다. 특정 값만 유효하도록 이 집합에 특정 제약 조건을 적용해 영지식 증명을 구성할 수 있습니다. 예를 들어 키는 1에서 5 사이의 숫자여야 한다고 정할 수 있습니다. 

따라서 집합론은 암호학 프로토콜에서 가능한 입력, 출력, 상태의 집합을 정의하고 분석하는 기초 언어, 도구, 표기법을 제공합니다. 영지식 증명에서는 원소 자체를 공개하지 않으면서 해당 원소가 특정 집합이나 범위에 속한다는 사실을 증명해야 하는 경우가 많습니다.

Khan Academy의 기본 집합 표기법 연습 문제를 풀어보시길 권합니다.

수론

수론은 정수와 산술 함수를 연구하는 수학의 한 분야입니다. 정수는 양수, 음수, 0을 포함하는 온전한 수, 즉 분수가 아닌 수의 집합으로 정의할 수 있습니다. 정수 집합을 더 형식적으로 정의하면 다음과 같습니다.

여기서 ℤ는 정수 집합을 나타내며, 말줄임표는 정수가 음의 무한대부터 양의 무한대까지 이어진다는 것을 보여줍니다. 예를 들어 12는 정수이며 -1978649832794275도 정수입니다.

유리수

유리수는 분모, 즉 일반 분수에서 선 아래에 있는 수이자 제수가 0이 아닌 분수로 표현할 수 있는 수입니다. 예를 들어 $(\frac{1}{2}), 74, (\frac{2}{3})$는 모두 유리수입니다. 유리수를 더 형식적으로 정의하면, p는 분자이고 q는 분모이며 q가 0이 아닐 때 분수 pq로 표현할 수 있는 수의 집합입니다. 기호 ℚ는 유리수를 나타냅니다. 집합 표기법으로는 다음과 같이 씁니다.‍

‍처음에는 어렵게 보일 수 있지만 앞 문장의 설명을 그대로 나타낸 것입니다. 이 낯선 수학 표기법은 “Q는 p와 q가 정수이고 q가 0이 아닐 때, q분의 p로 이루어진 모든 분수의 집합이다”라고 읽습니다. 

실수

실수는 유리수와 무리수를 모두 포함합니다. 무리수는 단순한 분수로 표현할 수 없으며 소수점 아래 숫자가 반복되지 않고 끝없이 이어지는 수입니다. 예를 들어 원주율, 즉 π와 $\sqrt{2}$, 즉 1.4.1421…는 무리수입니다. 지금은 집합 표기법을 생략하겠지만, 실수는 기호 ℝ로 나타낸다는 점을 기억하세요.

왜 알아야 할까요?

수론은 특정 수의 집합, 예를 들어 유리수를 연구하므로 집합론과 밀접하게 연결됩니다. 이러한 집합은 수학 및 암호학 문제에서 범위와 제약 조건을 정의하는 토대가 되는 경우가 많습니다. 

수론과 집합론이 어떻게 연결되는지도 알 수 있습니다. 예를 들어 모든 정수의 집합 ℤ는 유리수 ℚ의 부분집합이라고 할 수 있습니다. 위에서 집합 표기법으로 실수를 정의할 때 분자와 분모가 정수라고 명시한 부분에서 이를 확인할 수 있습니다.

모듈러 산술

시계 산술이라고도 하는 모듈러 산술은 정수가 법이라고 하는 특정 값에 도달하면 처음으로 “순환”하는 수치 연산 체계입니다. 무한한 수의 집합 대신 처음 n개의 양수를 대상으로 연산한다는 개념입니다.

시계

1부터 12까지 숫자가 있는 아날로그 시계를 생각해 보세요. 요즘 시대에 바늘이 있고 디지털 방식이 아니라고 명시해야 한다는 사실이 안타깝습니다. 현재가 11시이고 두 시간 뒤의 시간을 알고 싶다면 13시가 되지는 않습니다. 대신 한 바퀴 돌아 1시가 됩니다. 이는 $11 + 2 \equiv 1 \pmod{12}$로 표현할 수 있습니다. 올바른 수학식은 $13 \bmod 12 = 1$입니다. 프로그래머에게는 $13 \% 12 = 1$ 형식의 모듈로 연산이 익숙할 것입니다.

모듈로 연산

n mod k라고 쓰면 n을 k로 나눈 나머지를 구한다는 뜻입니다. 이를 모듈로 연산이라고 합니다. 예를 들면 다음과 같습니다.

• 25 mod 3은 25를 3으로 나누는 것을 뜻하며, $25 = 8 \times 3 + 1$이므로 나머지는 1입니다
• 15 mod 4는 15를 4로 나누는 것을 뜻하며, $15 = 3 \times 4 + 3$이므로 나머지는 3입니다

모듈러 산술에서 나머지는 항상 음수가 아닙니다.

왜 알아야 할까요?

모듈러 산술은 제약 조건 아래에서 숫자가 작동하는 방식을 이해하게 해주므로 매우 중요하며, 이는 암호학에서 유용합니다. 모듈러 산술은 여러 암호학 알고리즘의 토대이며 컴퓨터 과학, 공학을 비롯해 데이터를 안전하게 처리하고 암호화해야 하는 모든 분야에서 사용됩니다.

계산 x + y = z를 생각해 보겠습니다. 소수 p = 17로 정의된 유한체에서 작업한다고 가정합니다. 유한체는 곧 다루겠지만, 지금은 0부터 16까지 모든 정수로 이루어지며 17에서 순환하는 집합이라고 생각하면 됩니다. 이 체에서 계산은 (x + y) mod p = z가 됩니다. x = 12이고 y = 15라면 계산은 다음과 같습니다.‍

여기서 모듈러 산술을 사용하면 소수 p로 정의된 관리 가능한 값의 범위 안에서 계산을 수행할 수 있습니다. 컴퓨터와 프로세서의 공간은 제한되어 있으므로 일반적으로 u32나 u64 같은 고정 크기 정수를 사용합니다. 모듈러 산술은 값이 이 범위 안에 머물도록 보장합니다. 또한 소수를 사용하면 복잡성이 한층 높아집니다. 보안을 강화하고 특정 수학적 속성을 더 예측 가능하고 신뢰할 수 있게 하므로 암호학 관점에서 중요합니다.

예를 들어 zk-SNARKs에서는 모듈러 산술을 사용하여 계산된 값이 관리 가능한 특정 범위 안에 머물도록 합니다. 또한 주어진 수의 집합 위에서 산술 회로를 만드는 데도 사용합니다. 이를 통해 계산을 표현하면서 효율적으로 검증할 수 있습니다. 여기서 증명자는 x, y, z의 값을 공개하지 않고 이 계산을 수행했음을 증명해야 합니다.

모듈러 산술 문제를 직접 풀어보려면 Art of Problem Solving의 문제 모음과 Joseph Zoller의 모듈러 산술 연습 문제를 적극 권합니다. 

군론

군론은 군이라고 하는 대수 구조를 연구하는 수학의 한 분야입니다. 군은 군 공리라고 하는 다음 조건을 충족하는 연산과 원소의 집합입니다.

• 닫힘성 — 모든 산술 계산의 결과가 집합 안의 또 다른 원소가 됩니다
• 결합법칙 — 세 개 이상의 원소에 같은 연산을 수행할 때 원소를 묶는 순서는 중요하지 않으며 결과가 같습니다
• 항등원 — 다른 어떤 원소와 연산해도 그 값이 변하지 않게 하는 원소가 있습니다
• 역원 — 다른 원소와 연산했을 때 항등원이 되게 하는 원소가 있습니다

형식적으로는 다음과 같이 정의합니다.

• 닫힘성 — a와 b가 군의 원소라면 연산 결과(흔히 $a \times b$, $ab$, $a \circ b$, 또는 $ab$로 표기)도 군의 원소입니다. 형식적으로는 $\forall a, b \in G \mid a \circ b \in G$라고 씁니다. 이는 “집합 G에 있는 원소 a와 b의 모든 값에 대해, a와 b 사이의 연산 결과는 G에 속한다”라고 읽을 수 있습니다
• 결합법칙 — a, b, c가 군의 원소라면 (ab)c = a(cb)입니다. 형식적으로는 $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$라고 씁니다. 이는 “집합 G에 있는 원소 a, b, c의 모든 값에 대해, a와 b를 연산한 뒤 c와 연산한 결과는 b와 c를 연산한 뒤 a와 연산한 결과와 같다”라고 읽을 수 있습니다
• 항등원 — 군의 모든 원소 a에 대해 $e \circ a = a \circ e = a$를 충족하는 원소 e가 군에 존재합니다. 형식적으로는 $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$라고 씁니다. 이는 “집합 G에 원소 e가 존재하며, 집합 G에 있는 모든 원소 a에 대해 e와 a의 연산은 a와 e의 연산과 같고, 이는 a와 같다”라고 읽을 수 있습니다
• 역원 — 군의 각 원소 a에 대해 $a \circ b = b \circ a = e$를 충족하는 원소 b가 군에 존재합니다. 여기서 e는 항등원입니다. 형식적으로는 $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$라고 씁니다. 이는 “집합 G에 있는 원소 a의 모든 값에 대해 집합 G에 원소 b가 존재하며, a와 b의 연산은 b와 a의 연산과 같고, 이는 항등원과 같다”라고 읽을 수 있습니다

예시를 통해 이 모든 수학적 표현을 더 쉽게 풀어볼 수 있습니다. 덧셈 연산을 사용하는 정수 집합을 생각해 보세요. 이 집합은 네 가지 군 공리를 모두 충족하므로 군을 이룬다고 할 수 있습니다.

• 닫힘성 — 두 정수를 더하면 또 다른 정수가 됩니다
• 결합법칙 — $(5 + 4) + 3 = 5 + (4 + 3)$
• 항등원 — 어떤 정수에 0을 더해도 값이 변하지 않으므로 0은 항등원입니다. 예를 들어 $7 + 0 = 0 + 7 = 7$입니다
• 역원 — 어떤 정수의 역원은 부호를 반대로 바꾼 수입니다. 두 수를 더하면 항등원이 되기 때문입니다. 예를 들어 $5 + (-5) = 0$입니다. 이를 $n + (-n) = 0$으로 일반화할 수 있습니다

곱셈 연산을 사용하는 0이 아닌 유리수의 집합 $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$처럼 더 어려운 예시로 확장할 수도 있습니다. 이 역시 집합을 이룹니다.

• 닫힘성 — 0이 아닌 두 유리수를 곱하면 0이 아닌 유리수가 됩니다
• 결합법칙 — $ab \times cd \times ef = ab \times (cd \times ef)$
• 항등원 — 0이 아닌 어떤 유리수에 1을 곱해도 값이 변하지 않으므로 1은 항등원입니다. 예를 들어 $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$입니다
• 역원 — 0이 아닌 유리수의 역원은 그 역수, 즉 분자와 분모를 뒤집은 수입니다. 이를 곱하면 항등원인 1이 되기 때문입니다. 예를 들어 $\frac{3}{5} \times \frac{5}{3} = 1$입니다

부분군

부분군은 군 안에 있는 군입니다. 군 G의 부분군 H가 G의 부분집합이라고 말하려면 다음 군 공리를 충족해야 합니다.

• 닫힘성 — a와 b가 H에 있다면 두 원소의 연산 결과도 H에 있어야 합니다
• 결합법칙 — 더 큰 군 G에서 이 공리를 상속합니다 
• 항등원 — G의 항등원이 H에도 있어야 합니다 
• 역원 — H의 모든 원소 a에 대해 ab와 ba가 모두 항등원과 같아지는 원소 b가 H에 있어야 합니다

대표적인 예시는 덧셈 연산을 사용하는 짝수 정수 집합이 덧셈 연산을 사용하는 정수 집합의 부분군이라는 것입니다.

• 닫힘성 — 두 짝수 정수를 더하면 또 다른 짝수 정수가 됩니다
• 결합법칙 — 정수에서 이 공리를 상속합니다. 예를 들어 $2 + (4 + 6) = (2 + 4) + 6$입니다
• 항등원 — 어떤 짝수 정수에 0을 더해도 값이 변하지 않으므로 0은 항등원입니다. 0은 정수 집합에도 속합니다
• 역원 — 모든 짝수의 역원도 짝수입니다. 예를 들어 4의 역원은 -4입니다. $4 + (-4) = 0$이고, 0은 항등원이기 때문입니다

이를 더 어려운 예시에 적용할 수도 있습니다. 곱셈 연산을 사용하는 0이 아닌 모든 유리수의 집합, 즉 ℚ*를 생각해 보세요. ℚ*가 곱셈 연산을 사용하는 0이 아닌 실수의 집합, 즉 ℝ*의 부분군임을 증명할 수 있습니다.

• 닫힘성 — a와 b가 0이 아닌 유리수라면 그 곱 ab도 0이 아닌 수입니다. 예를 들어 $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$이며, 이는 0이 아닌 유리수입니다
• 결합법칙 — 유리수의 곱셈은 결합법칙을 따릅니다. 예를 들어 $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$입니다
• 항등원 — 0이 아닌 어떤 유리수에 1을 곱해도 값이 변하지 않으므로 1은 항등원입니다. 예를 들어 $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$입니다
• 역원 — 0이 아닌 모든 유리수 $a = \frac{p}{q}$에는 곱셈 역원 $a^{-1} = \frac{q}{p}$가 있습니다. 이 역시 0이 아닌 유리수이며 두 수의 곱은 항등원과 같습니다. 예를 들어 a = $\frac{2}{3}$라고 하겠습니다. $\frac{2}{3} \times \frac{3}{2} = 1$이므로 역원은 $\frac{3}{2}$입니다

ℚ*는 모든 군 공리를 충족하므로 군을 이룹니다. 또한 ℚ*는 ℝ*의 부분집합이며 그 속성을 상속하므로 ℚ*가 ℝ*의 부분군이라고 할 수 있습니다.

왜 알아야 할까요?

군은 다양한 수학 및 암호학 개념과 구조의 토대입니다. 예를 들어 RSA와 타원 곡선 암호학 같은 암호 시스템은 군과 그 연산의 속성에 크게 의존합니다. 부분군을 이해하면 더 작고 다루기 쉬운 부분집합을 살펴보며 더 큰 군의 구조를 이해할 수 있습니다. 군은 대칭, 연산, 변환을 이해하는 기본 프레임워크를 제공합니다. 이는 다음 섹션에서 다룰 체를 이해하는 데 매우 중요합니다.

체

체는 덧셈과 곱셈에 대한 체 공리를 충족하며 가환 나눗셈 대수, 즉 0으로 나누는 경우를 제외하면 항상 나눗셈이 가능한 원소의 집합입니다. 체 공리는 일반적으로 덧셈과 곱셈의 쌍으로 작성합니다.

• 덧셈
  • 결합법칙: $(a + b) + c = a + (b + c)$
  • 교환법칙: $a + b = b + a$
  • 분배법칙: $a(b + c) = ab + ac$
  • 항등원: $a + 0 = 0 + a = a$
  • 역원: $a + (-a) = 0$
• 곱셈
  • 결합법칙: $(ab)c = a(bc)$
  • 교환법칙: $ab = ba$
  • 분배법칙: $(a + b)c = ac + bc$
  • 항등원: $(a + b)c = ac + bc$
  • 역원: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

유한체와 생성원

유한체는 한정된 원소 집합을 가진 체입니다. 유한체는 갈루아 체라고도 합니다. 원소의 수를 체의 위수 또는 기수라고 합니다. 원소의 수는 항상 소수의 거듭제곱입니다. 유한체의 장점은 체 안의 원소에 어떤 산술 연산을 수행해도 결과가 체 안에 머문다는 것입니다. 모든 연산이 체의 위수를 법으로 수행되어 값이 순환하기 때문입니다.

모든 유한체에는 생성원이 있습니다. 생성원은 거듭제곱을 통해 체의 모든 원소를 생성할 수 있습니다. 즉, 체의 모든 원소를 얻을 때까지 생성원의 지수를 1씩 늘릴 수 있습니다. 따라서 생성원은 자신의 거듭제곱을 통해 체의 0이 아닌 모든 원소를 만들어낼 수 있는 체의 원소입니다.

예를 들어 p = 7을 법으로 하는 정수 집합을 사용하여 $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$이라는 체가 있다고 가정하겠습니다. $\mathbb{Z}_7^*$의 생성원 g, 즉 $\mathbb{Z}_7$에서 0이 아닌 원소의 곱셈군을 찾으려면 g1, g2, g3 등이 체의 0이 아닌 모든 원소를 생성할 수 있는지 확인해야 합니다.

3이 생성원인지 확인해 보겠습니다.

3의 거듭제곱은 $\mathbb{Z}_7$의 0이 아닌 모든 원소를 생성합니다. 따라서 3은 곱셈군 $\mathbb{Z}_7^*$의 생성원입니다.

왜 알아야 할까요?

암호학은 유한 집합을 다루는 과학입니다. 이는 이산 로그 문제, 암호화, 디피-헬먼 교환, 타원 곡선 같은 주제를 다루는 데 필수적인 기초를 형성합니다. 생성원을 사용하면 암호화된 다항식을 복호화하지 않고 산술 연산을 수행할 수 있습니다. 이를 동형 암호화라고 합니다. 즉, 기저 값의 개인정보를 보호하면서 암호화된 데이터를 계산할 수 있습니다. 이 섹션을 이해하는 것은 영지식 증명의 영지식 부분을 이해하는 데 매우 중요합니다.

특정 매개변수로 유한체를 생성하는 상호작용형 예시와 Python으로 구현한 기저 이론을 제공하는 Bill’s Security Site를 방문해 보시길 권합니다. 

함수

함수는 독립 변수와 종속 변수라는 두 변수의 관계를 정의하는 식, 규칙 또는 법칙입니다. 이 두 변수는 각각 원인과 결과로 설명되는 경우가 많습니다. 이 관계는 흔히 *y = f(x)*로 나타내며 “x의 f”라고 읽습니다. 모든 x 값에는 고유한 y 값이 있으므로 동일한 x에 대해 *f(x)*가 둘 이상의 값을 가질 수 없습니다.

함수는 일대일 또는 다대일일 수 있으며, 이를 흔히 기수라고 합니다. 즉, 하나의 x 값이 고유한 y 값에 대응하거나 여러 x 값이 동일한 y 값에 대응할 수 있습니다

$y = 3x + 4$로 정의된 직선을 생각해 보세요. 이는 x 값을 대입하면 그에 해당하는 y 값을 반환하는 일차 함수입니다. 이 두 값은 함께 직선 위의 한 점을 이룹니다. 예를 들어 식을 $f(x) = 3x + 4$로 다시 쓰고 x = 1일 때 계산하면 $f(1) = 7$이 됩니다. 함수는 여러 변수를 가질 수도 있습니다. 예를 들어 삼각형의 넓이 공식 $A = \frac{bh}{2}$를 살펴보겠습니다. 여기서 A, 즉 넓이는 b, 즉 밑변과 h, 즉 높이 모두의 함수로 정의됩니다.

정의역과 치역

함수의 정의역은 함수가 받을 수 있는 모든 입력값, 즉 독립 변수의 집합입니다. 함수의 치역은 함수가 만들어낼 수 있는 모든 출력값, 즉 종속 변수의 집합입니다.

함수 $y = 2x + 2$의 경우는 다음과 같습니다.

• 음의 무한대부터 양의 무한대까지 어떤 수도 사용할 수 있으므로 정의역은 모든 실수입니다. 예를 들면 다음과 같습니다.
  • x = 2.5이면 $y = 2(2.5) + 2 = 7$입니다 
  • x = -9234525이면 $y = 2(-9234525) + 2 = -18469048$입니다
• 음의 무한대부터 양의 무한대까지 어떤 수도 결과로 만들 수 있으므로 치역도 모든 실수입니다. 예를 들면 다음과 같습니다.
  • y = -50을 구하기 위해 -50 = 2x + 2를 풀면 x = -26입니다. 
  • y = 0을 구하기 위해 0 = 2x + 2를 풀면 x = 0입니다

왜 알아야 할까요?

함수는 다항식을 이해하는 데 매우 중요합니다. 다항식은 여러 거듭제곱을 한 변수와 그 계수를 포함하는 특수한 함수입니다. 다항식은 암호학 프로토콜을 구성하는 토대가 되는 기본적인 대수 구조입니다. 다음 섹션에서는 다항식의 속성과 영지식 증명에서의 중요성을 자세히 살펴봅니다.

함수를 더 잘 이해하려면 Paul’s Online Notes의 연습 문제를 풀어보시길 권합니다.

다항식

다항식은 여러 변수와 계수로 이루어지며 덧셈, 뺄셈, 곱셈, 변수의 음수가 아닌 정수 거듭제곱 연산만 포함하는 함수입니다. 다항식은 일반적으로 다음 형식으로 씁니다.‍

여기서 $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$는 계수이고 x는 변수입니다. 계수가 0이 아닌 변수 x의 가장 높은 거듭제곱을 다항식의 차수라고 합니다.

다항식은 단일 변수를 사용하는 일변수 다항식(위에 작성한 형식)과 여러 변수를 사용하는 다변수 다항식(예: $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$)으로 분류할 수 있습니다. Sum-Check는 다변수 다항식을 사용하는 프로토콜의 예입니다. 하지만 영지식 증명에는 대부분 단일 변수만 필요합니다.

다항식의 차수에 따라 일반적으로 사용하는 이름은 다음과 같습니다.

• 0차 — 0이 아닌 상수(예: $P(x) = 6$)
• 1차 — 일차식(예: $P(x) = 2x - 7$)
• 2차 — 이차식(예: $P(x) = 8x^2 - 3x + 1$)
• 3차 — 삼차식(예: $P(x) = 3x^3 - 4x$)

차수가 최대 $d$인 서로 다른 두 다항식은 최대 $d$개의 점에서 교차할 수 있습니다. 예를 들어 일차 함수와 삼차 함수를 같다고 놓으면 최대 세 번 교차할 수 있습니다. 이 성질은 공통점을 찾는 방식에서 비롯됩니다. 두 다항식이 교차하는 지점을 찾으려면 두 식을 같다고 놓습니다. 다음 하위 섹션에서는 주어진 다항식이 x축과 교차하는 지점, 즉 다항식의 근을 구하는 방법을 연습합니다. 대수학의 기본 정리에 따르면 차수가 $d$인 다항식은 해를 최대 $d$개 가질 수 있으므로 공통점도 최대 $d$개입니다.

다항식의 근 

다항식의 근 또는 영점은 다항식의 값이 0이 되는 x 값입니다. 다시 말해 $P(x)$가 다항식이라면 근 $r$은 방정식 $P(r) = 0$의 해입니다. 근을 구하려면 다항식의 인수분해에 익숙해야 합니다. 인수분해는 어떤 값이 나오도록 무엇을 곱해야 하는지 구하는 과정입니다. 예를 들어 12를 인수분해하는 방법은 여러 가지입니다.

일반적인 인수분해 방법은 수를 양의 소인수로 완전히 분해하는 것입니다. 인수분해할 때는 항상 모든 항이 공통으로 갖는 최대공약수(GCF)부터 찾는 것이 좋습니다. 예를 들면 다음과 같습니다.

위 예시에서 두 항, 즉 6x와 3은 모두 3으로 나누어지므로 최대공약수는 3입니다. 따라서 인수는 3과 $2x + 1$입니다. 이는 분배법칙을 거꾸로 적용한 것입니다. 즉, $3 \times 2x$와 $3 \times 1$입니다. 근을 구한다는 것은 $P(x) = 0$일 때의 x를 구하는 것입니다.

항이 두 개인 다항식은 쉽게 인수분해할 수 있습니다. 그래프가 주어진 경우에는 근이 다항식과 x축이 교차하는 지점이므로 더 간단합니다. 하지만 차수가 3 이상이면 더 복잡해질 수 있습니다. 자세한 설명은 다항식 인수분해 설명 문서를 읽어보시기를 권합니다. 

다양한 다항식의 인수분해에 관한 세부 사항을 정확히 아는 것은 이 글의 나머지 내용을 읽는 데 중요하지 않습니다. 여기서는 다항식이 다른 값과 같아지는 경우에 관심이 있습니다. 이 경우에는 다항식이 0이 되는 때를 살펴봅니다. 이후에는 한 다항식이 다른 다항식과 같아지거나 두 다항식의 차가 항등적으로 0이 되는 경우, 즉 모든 계수가 0이 되는 경우를 다룹니다. 이는 주어진 다항식이 특정 근을 갖는지 확인하는 과정입니다.

Schwartz-Zippel 보조정리 

Schwartz-Zippel 보조정리는 다항식 방정식이 항상 참인지 확인하는 확률적 도구입니다. 임의의 점에서 다항식을 계산하고 결과가 0인지 확인합니다.

변수 $x_1, x_2, \ldots, x_n$이 포함된 복잡한 방정식을 생각해 보세요. 이 방정식이 단순히 항을 무작위로 모아 놓은 것이 아니라 다항식이라면 Schwartz_Zippel 보조정리를 사용해 이 변수들의 가능한 모든 값에서 방정식이 성립하는지 검증할 수 있습니다.

작동 방식은 다음과 같습니다.

• $P(x_1, x_2, \ldots, x_n)$를 총차수가 d인 다항식이라고 합니다. 총차수는 각 항에서 지수 합의 최댓값입니다
• 체에서 유한 집합 S를 선택합니다. 이는 숫자 집합을 고르는 것과 같습니다
• 집합 S에서 각 변수 $x_1, x_2, \ldots, x_n$의 값을 무작위로 선택합니다

이 보조정리에 따르면 무작위로 선택한 점에서 P가 0일 확률은 최대 $\frac{d}{S}$입니다. 즉, 다항식이 0이 아니라면 우연히 0처럼 나타날 가능성이 매우 낮습니다. 이는 다항식 항등식을 효율적으로 검증해야 하는 영지식 증명에서 특히 유용합니다.

라그랑주 보간법

라그랑주 보간법은 주어진 점들을 통과하는 다항식을 구성하는 방법입니다. 라그랑주 다항식은 주어진 모든 점을 통과하는 최소 차수의 다항식입니다. n개의 점이 있으면 모든 점을 통과하는 n-1차 다항식을 만들 수 있습니다. 예를 들어 평면에 두 점이 있으면 두 점을 모두 통과하는 직선을 정의할 수 있습니다. 평면에 세 점이 있으면 모든 점을 통과하는 이차 다항식, 즉 $y = ax^2 + bx + c$를 정의할 수 있습니다. 이후도 같은 방식입니다.

왜 중요한가요?

다항식은 제한 없이 많은 정보를 담을 수 있는 하나의 수학적 객체입니다. 다항식을 정수 목록으로 생각하면 이를 쉽게 이해할 수 있습니다. 따라서 다항식 사이의 방정식 하나로 수 사이의 방정식을 무한히 많이 나타낼 수 있습니다. 누군가 주어진 다항식 사이의 방정식을 검증할 수 있다면 가능한 모든 방정식을 동시에 검증하는 셈입니다. 이러한 방식으로 악의적인 증명자의 위험을 방지하고, 주어진 계산을 무작위로 표본 검사하는 데 의존하지 않으면서 비대화형 증명을 안전하게 보호합니다. 

다항식에는 증명을 만드는 데 유용한 여러 성질도 있습니다.

• 주어진 다항식에 대해 충분한 수의 점이 있으면 전체 다항식을 복원할 수 있습니다
• 다항식의 입력이 조금만 바뀌어도 출력이 크게 달라질 수 있어 오류를 더 쉽게 감지할 수 있습니다
• 소거 코딩이 데이터에 내결함성을 부여하는 것처럼 다항식은 계산 오류를 감지하고 수정할 수 있습니다. 이는 Turbine의 작동 방식에 매우 중요합니다

영지식 증명은 특정 계산이 올바름을 증명합니다. 다항식은 원하는 특성에 맞게 구성할 수 있어 이 과정에서 매우 유용합니다. 증명하려는 계산이나 데이터 점 집합이 있다고 가정해 보겠습니다. 가장 쉬운 방법은 이를 다항식으로 인코딩하고 다항식의 성질을 사용해 증명을 만드는 것입니다.

• 특정 점에서 $P(x)$를 계산하면 원본 데이터나 주어진 계산 결과가 나오도록 데이터를 다항식 $P(x)$로 인코딩합니다
• 다항식이 주어진 기준을 충족하는지 확인하기 위해, 예를 들어 모든 값이 특정 범위 안에 있도록 제약 다항식 $C(x)$를 만듭니다. 예를 들어 $C(x) = (P(x) - 0)(P(x) - 1)$은 $P(x)$가 0 또는 1임을 보장합니다
• 문제를 $P(x)$가 데이터 세트나 계산에 필요한 특정 조건을 충족함을 증명하는 형태로 변환합니다
• 이러한 조건을 인코딩하며 $P(x)$의 배수인 알려진 다항식 $H(x)$를 만듭니다
• 증명자는 $P(x)$와 관련 다항식의 계산값으로 Merkle 트리를 만들어 값에 커밋하고, 루트 해시를 검증자에게 보냅니다
• 검증자는 몇 개의 점을 무작위로 선택하고, 해당 점에서 $P(x)$와 $C(x)$의 값을 제시하도록 증명자에게 요청합니다
• 검증자는 제시된 값을 커밋된 루트 해시 및 예상되는 다항식 관계와 대조합니다

다항식의 크기는 중요하지 않습니다. 다항식 커밋을 사용하면 다항식 사이의 방정식을 짧은 시간 안에 검증할 수 있습니다. 이는 매우 간결하고 효율적으로 증명을 만드는 방법입니다. 모든 오류가 증폭되며, Fiat-Shamir 휴리스틱과 같은 기법을 사용하면 이 증명을 비대화형으로 만들 수 있습니다. 그러면 추가 상호작용 없이 누구나 검증할 수 있습니다. 

더 깊이 이해하려면 다음 연습 문제를 풀어보시기를 권합니다.

• 다항식 연습 문제
• 다항식의 영점 구하기 연습 문제
• 다항식 인수분해: 풀이가 포함된 고난도 문제

Khan Academy에도 다항식의 표현식, 방정식, 함수에 관한 방대한 단원이 있습니다.

이제 다항식 커밋을 더 잘 이해하려면 영지식 증명의 기반이 되는 암호학을 살펴봐야 합니다.

영지식 증명의 기반이 되는 암호학

대칭 암호화와 비대칭 암호화를 살펴보겠습니다.

대칭 암호화

대칭 암호화는 같은 키를 사용해 평문을 암호화하고 암호문을 복호화하는 기법입니다. 하나의 키를 사용하려면 이 키를 비밀로 유지해야 하므로 흔히 비밀 키 또는 개인 키라고 부릅니다. 하지만 이는 두 당사자가 안전하게 통신하기 전에 비밀 키를 공유해야 한다는 의미이기도 합니다. 따라서 비밀 키를 안전하게 관리하고 배포하기가 어려울 수 있으며, 제대로 처리하지 않으면 유출될 위험이 있습니다. 이러한 단점에도 불구하고 대칭 암호화는 빠르고 효율적이며 다른 암호화 방식보다 필요한 연산 능력과 메모리가 적습니다.

일반적인 대칭 암호화 알고리즘은 다음과 같습니다.

고급 암호화 표준(AES)

고급 암호화 표준(AES)은 데이터를 보호하기 위해 전 세계에서 널리 사용하는 Rijndael 블록 암호의 변형입니다. 128비트, 192비트, 256비트 키 크기를 지원합니다.

ChaCha20

ChaCha20은 Daniel J. Bernstein이 개발한 현대적이고 효율적인 스트림 암호입니다. 덧셈-회전-XOR(ARX) 연산을 활용하는 Salsa20 스트림 암호의 변형입니다. 256비트 키, 64비트 nonce, 64비트 카운터를 512비트 키스트림 블록에 매핑합니다. 따라서 사용자는 상수 시간 안에 키스트림의 원하는 위치를 효율적으로 찾을 수 있습니다.

대칭 암호화는 강력하고 효율적이지만 키를 교환할 안전한 방법이 필요합니다. 그중 하나인 Diffie-Hellman 키 교환을 사용하면 두 당사자가 안전하지 않은 채널에서도 비밀 키를 안전하게 공유할 수 있습니다. 다만 이 방법은 비대칭 암호화 원리를 기반으로 하며, 다음 섹션에서 이를 다룹니다.

비대칭 암호화

공개 키 암호화라고도 하는 비대칭 암호화는 서로 연관된 키 쌍, 즉 공개 키와 개인 키를 사용해 정보를 암호화하고 복호화하는 방법입니다. 공개 키는 공개적으로 공유하고 개인 키는 비밀로 유지합니다. 송신자는 메시지를 암호화할 때 수신자의 공개 키를 사용합니다. 수신자는 메시지를 받으면 이에 대응하는 개인 키로 복호화합니다. 공개 키로 암호화한 데이터는 개인 키로만 복호화할 수 있습니다. 따라서 복호화 키를 공유하지 않고도 안전하지 않은 채널에서 안전하게 통신할 수 있습니다.

비대칭 암호화는 개인 키를 공유하지 않으므로 높은 수준의 보안을 제공합니다. 공개 키를 자유롭게 공유할 수 있어 키 배포가 간단해지고 디지털 서명도 사용할 수 있습니다. 그러나 비대칭 암호화는 대칭 암호화보다 더 많은 연산이 필요하고 느립니다. 키 쌍이 직관적이지 않거나 사용자가 많은 시스템에서는 키 쌍 관리도 복잡해질 수 있습니다. 

일반적인 비대칭 암호화 알고리즘은 다음과 같습니다.

• Rivest-Shamir-Adleman(RSA) — 안전한 데이터 전송을 위한 가장 오래되고 널리 사용되는 공개 키 암호 시스템 중 하나입니다. 1970년대에 개발되었으며 두 큰 소수의 곱을 인수분해하기가 현실적으로 어렵다는 점에 의존합니다
• 타원 곡선 암호학(ECC) — 유한체 위 타원 곡선의 대수적 구조를 기반으로 하는 공개 키 암호학 방식입니다. RSA와 비슷한 보안 수준을 더 작은 키로 제공하므로 연산 속도가 빨라지고 저장 공간 요구 사항이 줄어듭니다. Solana는 키 쌍 생성에 Ed25519 타원 곡선을 사용합니다

디지털 서명

디지털 서명은 공개 키 암호학의 핵심 요소로, 메시지나 소프트웨어, 디지털 문서의 진위와 무결성을 검증하는 방법을 제공합니다. 디지털 서명은 송신자의 개인 키로 생성하며, 대응하는 공개 키에 접근할 수 있는 누구나 검증할 수 있습니다. 이를 통해 메시지가 적법한 송신자에게서 전송되었고 변조되지 않았음을 보장합니다.

디지털 서명에 사용하는 일반적인 알고리즘은 다음과 같습니다.

• 디지털 서명 알고리즘(DSA) — 모듈러 거듭제곱, 즉 법을 기준으로 수행하는 거듭제곱과 이산 로그 문제를 기반으로 하는 방식입니다
• 타원 곡선 디지털 서명 알고리즘(ECDSA) — 타원 곡선 암호학을 사용해 더 작은 키 크기로 더 높은 수준의 보안을 제공하는 DSA의 변형입니다

이산 로그 문제

이산 로그 문제는 방정식 $g^k \equiv h \pmod{p}$에서 지수 k를 찾는 문제입니다. 각 항의 의미는 다음과 같습니다.

• g는 알려진 밑, 즉 생성자입니다
• h는 알려진 결과, 즉 군의 원소입니다
• p는 소수, 즉 군의 위수입니다
• k는 알 수 없는 지수, 즉 밑이 g인 h의 이산 로그입니다

쉽게 말해 g, h, p의 값을 알 때 이산 로그 문제의 목표는 k를 찾는 것입니다. 예를 들어 방정식 $2^k \equiv 9 \pmod{23}$이 주어졌다면 목표는 k를 찾는 것입니다.

이산 로그 문제는 특히 큰 수에서 효율적으로 풀기 어렵다고 알려져 있습니다. 이러한 난해성은 Solana, ElGamal 암호화, 디지털 서명 알고리즘, 즉 DSA와 ECDSA, 그리고 Diffie-Hellman 키 교환을 비롯한 여러 암호 시스템의 보안 기반입니다.

Diffie-Hellman 키 교환

Diffie-Hellman 키 교환은 공개 채널을 통해 암호화 키를 안전하게 교환하는 방법입니다.  가장 단순한 최초 구현 방식인 유한체 Diffie-Hellman은 다음과 같습니다.

• Alice와 Bob은 큰 소수 p, 즉 법과 밑 g, 즉 생성자라는 두 수에 공개적으로 합의합니다. g는 p를 법으로 하는 원시근입니다 
• Alice는 비밀 정수 a를 선택한 다음 Bob에게 $A \equiv g^a \pmod{p}$를 보냅니다
• Bob은 비밀 정수 b를 선택한 다음 Alice에게 $B \equiv g^b \pmod{p}$를 보냅니다
• Alice는 $s \equiv B^a \pmod{p}$를 계산합니다 
• Bob은 $s = A^b \pmod{p}$를 계산합니다 

이제 Alice와 Bob은 동일한 비밀 값을 갖습니다. 두 계산 모두 다음과 같이 동일한 비밀 s를 산출하기 때문입니다.

이 공유 비밀 s를 대칭 암호화 키로 사용하면 Alice와 Bob이 안전하게 통신할 수 있습니다. Diffie-Hellman 키 교환의 보안은 이산 로그 문제의 난해성에 의존합니다. 비밀 값 a와 b를 모르면 도청자가 공유 비밀을 알아내는 것은 계산상 불가능합니다. 이를 일방향 함수라고 합니다. 계산하기는 비교적 쉽지만 역으로 구하기는 극도로 어렵습니다.

유한체 Diffie-Helman 키 교환은 안전하고 널리 사용되지만, 보안을 확보하려면 큰 키가 필요합니다. 예를 들어 Alice와 Bob이 법으로 23을 공개적으로 선택했다면 n mod 23의 가능한 결과가 23개뿐이므로 훨씬 쉽게 해독할 수 있습니다. 따라서 연산량이 많고 효율이 떨어질 수 있습니다. 타원 곡선 암호학(ECC)은 훨씬 작은 키와 더 빠른 연산으로 동일한 수준의 보안을 제공해 이러한 문제를 해결하는 효율적인 대안입니다.

타원 곡선

타원 곡선은 방정식 $y^2 = x^3 + ax + b$로 정의되며, 여기서 a와 b는 상수입니다. 타원 곡선 암호학은 주어진 타원 곡선 위의 점을 다루는 것입니다. 이러한 곡선에는 암호학에 유용한 여러 고유한 성질이 있습니다. 예를 들면 다음과 같습니다.

• 점의 덧셈 — 주어진 타원 곡선 위의 두 점 P와 Q가 있을 때 두 점의 합 R = P + Q도 곡선 위의 점입니다. Preethi Kasireddy의 글 영지식 증명을 위한 쉬운 암호학 가이드에는 타원 곡선 위의 점을 더하는 방법이 잘 설명되어 있습니다
• 스칼라 곱셈 — 주어진 타원 곡선 위의 점 P와 정수 k가 있을 때 스칼라 곱셈은 점 P를 자기 자신과 k번 더하는 과정입니다. 그 결과 곡선 위의 또 다른 점, 즉 kP가 생성됩니다. 이는 개인 키에서 공개 키를 생성하는 데 사용됩니다
• 이산 로그 문제 — 타원 곡선의 이산 로그 문제는 정수에서의 이산 로그 문제보다 훨씬 풀기 어렵습니다. 점 P와 q = kP가 주어졌을 때 곡선 매개변수를 올바르게 선택하면 k를 알아내는 것은 계산상 불가능합니다. 따라서 타원 곡선은 훨씬 작은 키로 기존 시스템과 같은 보안을 제공하므로 더 효율적입니다

앞에서 배운 군론을 바탕으로 특정 타원 곡선 방정식이 다음 군 공리를 충족한다고 말할 수 있습니다.

• 임의의 두 점을 더하면 세 번째 점을 얻을 수 있습니다
• 두 점을 더하는 순서는 중요하지 않습니다
• 더할 점이 두 개보다 많아도 더하는 순서는 중요하지 않습니다
• 항등원이 있습니다. 즉, 곡선 위의 임의의 점에 0을 더하면 같은 점이 나옵니다

이 군 구조를 더 깊이 알아보려면 Georgie Bumpus의 타원 곡선 암호학을 읽어보시기를 적극 권합니다. 

타원 곡선은 RSA와 같은 기존 암호 시스템과 동일한 수준의 보안을 훨씬 작은 키로 제공합니다. 예를 들어 ECC의 256비트 키는 RSA의 3072비트 키와 비슷한 수준의 보안을 제공합니다. 장점은 다음과 같습니다.

• 키가 작으면 암호화와 복호화가 빨라집니다
• 키와 인증서에 필요한 공간이 줄어듭니다
• 키가 작으면 전송하는 데이터 양이 줄어들어 블록체인처럼 대역폭이 제한된 환경에 유리합니다

Montgomery 곡선

Montgomery 곡선은 유한체 위에서 방정식 $By^2 = x^3 + Ax^2 + x$로 정의되는 타원 곡선입니다. 여기서 A와 B는 상수이고, B는 0이 아니며 A는 -2도 2도 아닙니다. 이 곡선은 Montgomery 사다리를 사용해 타원 곡선 곱셈을 더 효율적으로 구현할 수 있다는 점에서 특별합니다. 

Montgomery 사다리는 기본적으로 Montgomery 곡선 위의 점 P와 스칼라 k를 받아 두 점을 무한원점과 P로 초기화하고, 스칼라 k의 각 비트를 최상위 비트부터 최하위 비트까지 갱신합니다. 핵심은 두 점을 유지하면서 스칼라 k의 비트와 관계없이 일정한 연산 순서로 갱신하는 것입니다.

이는 다음과 같은 이유로 중요합니다.

• 부채널 공격에 강합니다. 부채널 공격은 주어진 프로토콜이나 알고리즘의 구현 또는 설계로 인해 수집할 수 있는 추가 정보를 활용하는 모든 공격을 뜻합니다. 매우, 매우 전문적인 주제지만 깊이 파고들어 보시기를 권합니다. 이러한 공격은 연산 중 하드웨어의 전력 소비 변화를 이용하는 방식부터 누출된 전자기 복사를 이용하는 방식까지 다양합니다
• y좌표가 필요하지 않습니다. x좌표만으로 스칼라 곱셈을 수행할 수 있기 때문입니다
• 상수 시간으로 작동합니다. 즉, 주어진 계산에 걸리는 시간이 입력값과 무관합니다

Montgomery 곡선은 키 교환을 위한 X25519 알고리즘과 같은 암호화 프로토콜에서 널리 사용됩니다. 이 알고리즘은 Curve25519 곡선의 Montgomery 형식을 사용합니다. 이 알고리즘은 TLS와 같은 널리 쓰이는 프로토콜의 구현을 포함해 현대 보안 통신의 기반입니다. 

Edwards 곡선

Edwards 곡선은 방정식 $x^2 + y^2 = 1 + d x^2 y^2$로 정의되는 타원 곡선의 한 유형입니다. 여기서 d는 0이 아니고 1과도 다른 상수입니다.  

이 곡선이 중요한 이유는 다음과 같습니다.

• 점 연산의 효율성 — Edwards 곡선에서 두 점을 더하는 연산은 다른 형태의 타원 곡선보다 효율적입니다. 점 덧셈과 두 배 연산 공식이 더 간단하고 필요한 체 연산도 적어 계산이 빠릅니다
• 통합 덧셈 공식 — Edwards 곡선은 통합 덧셈 공식을 사용하므로 점 덧셈과 점 두 배 연산에 같은 공식을 사용할 수 있습니다. 이를 통해 구현 오류 가능성을 줄이고 보안을 강화합니다
• 완전성 — 특정 d 값에서 Edwards 곡선은 완전합니다. 즉, 덧셈 법칙이 예외 없이 가능한 모든 입력을 처리합니다.
• 부채널 공격 내성 — Montgomery 곡선과 마찬가지로 Edwards 곡선은 균일하고 예측 가능한 연산 패턴 덕분에 부채널 공격에 강합니다.

널리 사용되는 Edwards 곡선으로는 방정식 $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$로 정의되는 Edwards25519가 있습니다. 이 곡선은 효율적인 산술 연산과 256비트 키 크기로 잘 알려져 있습니다. 이 곡선의 서명 방식은 Solana, OpenSSH, Tor를 비롯한 여러 보안 프로토콜과 시스템에 구현되어 있습니다. Monero는 키 쌍 생성의 기반으로 Edwards25519를 사용합니다.

왜 중요한가요?

타원 곡선은 효율적이고 보안을 강화하는 성질 덕분에 영지식 증명에서 매우 중요합니다. 타원 곡선을 사용하면 더 작고 빠른 증명을 만들 수 있으며, 이는 실제 구현에 필수적입니다. 영지식 관련 기술을 다룰 때 더 자세히 분석하겠지만, 다양한 계정 및 트랜잭션 제약이 있는 고연산 환경에서는 작고 빠른 증명이 매우 중요합니다. 이 때문에 영지식 증명은 롤업 구축에 적합합니다. L2의 모든 연산이 유효하다는 간결한 증명을 생성하고 L1에서 검증할 수 있기 때문입니다.

결론적으로 타원 곡선을 모듈러 산술의 대체재로 생각하면 됩니다. 타원 곡선에서는 특정 점을 구하기가 훨씬 어렵습니다. 기존 모듈러 산술에서 $g^a \bmod n$을 사용한다고 가정해 보겠습니다. 여기서 g는 생성자이고, n은 큰 소수이며, a는 비밀 키입니다. 앞서 이산 로그 문제에서 살펴봤듯이 비밀 키를 보호하려면 매우 큰 소수가 필요합니다. 타원 곡선은 더 작은 키로 동일한 수준의 보안을 제공하면서 성능을 크게 높이는 효율적인 대안입니다.

무작위성

암호학의 기본 요소인 무작위성이 없다면 이 글의 다른 모든 내용은 의미가 없습니다. 값이 예측 가능하고 편향되어 있다면 어떻게 시스템의 보안을 기대할 수 있을까요? 진정한 무작위성을 확보하기는 어렵지만, 다음과 같은 이유로 반드시 필요합니다.

• 키 생성 — 암호화 키는 예측할 수 없고 안전하도록 무작위로 생성해야 합니다
• Nonce와 솔트 — Nonce, 즉 한 번만 사용하는 숫자와 솔트, 즉 해싱 전에 데이터에 추가하는 무작위 값은 각각 재전송 공격을 방지하고 사전 계산 공격으로부터 보호합니다
• 보안 프로토콜 — 무작위성은 공정성과 보안을 보장하고, 공격자가 악용할 수 있는 예측 가능성과 패턴을 차단하는 데 사용됩니다

대부분의 난수 생성기는 암호학적으로 검증 가능한 난수를 만들지 못합니다. 이로 인해 조작에 취약하고 사용 사례도 제한됩니다. 하지만 검증 가능한 랜덤 함수가 이 문제를 해결합니다.

검증 가능한 랜덤 함수

검증 가능한 랜덤 함수(VRF)는 무작위 출력과 함께 주어진 입력에서 해당 출력이 올바르게 생성되었다는 증명을 만드는 암호학적 기본 요소입니다. VRF는 예측 불가능해야 합니다. 즉, 비밀 입력을 모르는 사람은 그 출력을 무작위 값과 구별할 수 없어야 합니다. 보안은 비밀 지수 d를 모르면 $y = h^d \bmod n$을 계산하기 어렵다는 RSA 가정과 해시 함수 H의 보안에 의존합니다. 

VRF의 주요 단계는 다음과 같습니다.

• 키 생성 — 사용자는 공개 키로 RSA 키 쌍 (e, n)을 생성하고 개인 키로 (d, n)을 생성합니다. 공개 키 e는 지수이고 n은 법입니다. 개인 키 d는 비밀 지수입니다
• 계산 — 입력 x가 주어지면 사용자는 VRF 출력 y와 증명 π를 계산합니다. 먼저 H가 암호학적 해시 함수일 때 *h = H(x)*의 해시를 계산합니다. 그런 다음 해시의 RSA 서명인 $y = h^d \bmod n$을 계산합니다. 마지막으로 증명 *π = (h, y)*를 계산합니다
• 검증 — 공개 키 (e, n), 입력 x, 출력 y, 증명 *π = (h, y)*가 주어지면 누구나 해시 h가 $H(x)$와 같은지 확인하고 RSA 방정식을 검증하기 위해 $y^e \equiv h \pmod{n}$을 확인하여 VRF 출력의 정확성을 검증할 수 있습니다‍

VRF는 무작위성이 예측 불가능하면서도 검증 가능해야 하는 합의 프로토콜에서 자주 사용됩니다. Algorand, Cardano, Internet Computer, Polkadot을 비롯한 L1은 합의 메커니즘에서 VRF를 사용해 블록 생성자를 무작위로 선택합니다. Chainlink는 공정할 가능성이 높고 검증 가능한 값을 생성하기 위해 사용자와 블록체인 사이의 추상화 계층으로 Chainlink VRF를 제공합니다. Pyth Entropy도 신뢰할 수 있고 안전한 무작위성 소스를 제공합니다.

세리머니와 신뢰 설정

암호학적 세리머니는 중요한 암호학적 계산을 안전하고 통제된 환경에서 수행하는 프로토콜 또는 행사입니다. 암호학적 세리머니에는 다음과 같은 여러 유형이 있습니다.

• 키 생성 세리머니 — 단일 주체가 키 생성 과정을 통제하지 못하도록 암호화 키를 생성합니다
• 매개변수 생성 세리머니 — 여러 당사자가 사용할 암호학적 매개변수를 생성합니다
• 다자간 연산(MPC) 세리머니 — 단일 당사자가 과정을 훼손하지 못하도록 여러 당사자가 함께 암호학적 계산을 수행합니다

신뢰 설정 세리머니는 암호화 프로토콜을 실행하는 데 필요한 암호학적 매개변수 집합을 생성하기 위한 특별한 행사 또는 과정입니다. 대화형 및 비대화형 영지식 증명 섹션에서는 증명의 첫 단계로 증명자와 검증자가 사용할 특정 값에 합의해야 한다고 설명했습니다. 신뢰 설정 세리머니에서는 단일 참여자가 과정을 통제하지 못하도록 여러 참여자가 설정에 무작위성을 기여합니다. 각 참여자는 다른 참여자가 제공한 값과 결합할 무작위 값을 생성합니다. 결합한 출력은 모두가 신뢰할 수 있는 매개변수 집합이 됩니다. 

모든 참여자가 공모하면 유효하지 않은 주장에 대한 증명을 생성해 시스템을 무너뜨릴 수 있으므로 이 과정은 매우 중요합니다. 하지만 정직한 참여자가 단 한 명만 있어도 매개변수의 보안을 보장할 수 있습니다. 

Zcash는 체인의 개인정보 보호 기능을 시작하기 위해 신뢰 세리머니를 사용한 것으로 유명합니다. Ethereum도 확장성 개선 노력의 암호학적 기반을 마련하기 위해 대중이 함께 참여하는 KZG 세리머니를 진행했습니다. 예로 EIP-4844와 proto-danksharding이 있습니다. 

zk-STARKs와 같은 일부 영지식 증명 시스템은 신뢰 설정이 필요하지 않습니다. 두 번째 글에서 이를 더 자세히 살펴보겠습니다.

결론

이 글에서는 영지식 증명을 뒷받침하는 이론과 수학, 암호학을 살펴봤습니다. 영지식 증명이 무엇인지 이해하는 데 필요한 핵심 내용을 모두 다뤘습니다. 이제 이러한 지식을 Solana와 같은 네트워크에 적용해 영지식 증명에 관한 전반적인 논의와 발전에 기여할 수 있습니다.

영지식 증명을 다루는 2부작 시리즈의 두 번째이자 마지막 글인 영지식 증명: Solana에서의 활용에서 분석을 이어갑니다. 

여기까지 읽어주셔서 감사합니다, anon님! 아래에 이메일 주소를 입력하고 Solana의 새로운 소식을 빠짐없이 받아보세요. 더 깊이 알아볼 준비가 되셨나요? 지금 바로 Helius 블로그의 최신 글을 살펴보고 Solana 여정을 계속하세요.

추가 자료

• 진정한 무작위성은 존재하는가?
• 타원 곡선 — Computerphile
• NP-완전 복잡도 클래스 소개
• 키 교환 문제 — Computerphile
• Khan Academy 암호학 강좌
• 공개 키 암호화 — Computerphile
• 대화형 증명 시스템의 지식 복잡도