ZKP-3. 유한체 산술 회로와 영지식 증명에서의 활용

논리 회로부터 시작해서 어떻게 유한체 산술 회로가 영지식 증명에 활용되는지 차근차근 알아보겠습니다.

1. 논리 회로 (Logic Circuit)

논리 회로는 컴퓨터 과학의 가장 기본적인 개념으로, 참(True/1)과 거짓(False/0)이라는 두 가지 상태(비트)를 입력받아 논리 연산을 수행하고 결과를 출력하는 전자 회로입니다. 컴퓨터의 모든 연산은 근본적으로 이 논리 회로의 조합으로 이루어집니다.

• 기본 구성 요소: 논리 게이트(Logic Gate)라고 불리는 작은 연산 단위들로 구성됩니다.
• AND: 두 입력이 모두 참(1)일 때만 참(1)을 출력합니다.
• OR: 두 입력 중 하나라도 참(1)이면 참(1)을 출력합니다.
• NOT: 입력을 반대로 뒤집습니다. 참(1)은 거짓(0)으로, 거짓(0)은 참(1)으로 바꿉니다.
• 이 외에도 NAND, NOR, XOR 등의 게이트가 있습니다.
• 표현: 주로 불리언(Boolean) 함수를 표현하는 데 사용됩니다. 예를 들어, f(x, y) = x AND y 와 같은 함수를 회로로 나타낼 수 있습니다.
• 특징: 모든 계산을 0과 1의 이진법(binary)으로 처리하는 데 최적화되어 있습니다. 

2. 산술 회로 (Arithmetic Circuit)

산술 회로는 논리 회로와 유사하지만, 0과 1 대신 일반적인 숫자(정수, 유리수 등)를 입력받아 산술 연산을 수행하는 회로입니다.

• 기본 구성 요소: 산술 게이트(Arithmetic Gate)로 구성됩니다.
• 덧셈(+) 게이트: 두 숫자를 더합니다.
• 곱셈(×) 게이트: 두 숫자를 곱합니다.
• 표현: 주로 다항식(Polynomial)을 표현하는 데 사용됩니다. 예를 들어, f(x, y) = x*y + x + 5 와 같은 계산 과정을 덧셈과 곱셈 게이트의 연결로 나타낼 수 있습니다.
• 차이점: 논리 회로가 비트 단위의 논리 연산에 중점을 둔다면, 산술 회로는 숫자 단위의 덧셈과 곱셈 연산에 중점을 둡니다. 영지식 증명에서는 증명하려는 계산 과정을 다항식으로 변환해야 하는데, 이때 산술 회로가 매우 유용하게 사용됩니다.

3. 유한체 산술 회로 (Finite Field Arithmetic Circuit)

이제 산술 회로를 특별한 수학적 공간인 유한체(Finite Field) 위에서 생각해보겠습니다. 이것이 바로 유한체 산술 회로입니다.

• 유한체(Finite Field)란?
• 이름 그대로 원소의 개수가 유한한 숫자 집합입니다.
• 이 집합 안에서 덧셈, 뺄셈, 곱셈, 나눗셈(0으로 나누는 것 제외)이 모두 가능하며, 그 결과값 또한 항상 집합 안에 포함됩니다.
• 가장 흔한 예는 '나머지 연산(modular arithmetic)'입니다. 예를 들어, '소수 p로 나눈 나머지의 집합'은 유한체가 됩니다. 이 유한체는 $F_p$ 또는 $GF(p)$라고 표기합니다.
• 예시: $F_7$ = {0, 1, 2, 3, 4, 5, 6}. 이 안에서 4 + 5 = 9는 7로 나눈 나머지인 2가 됩니다. 3 * 6 = 18은 7로 나눈 나머지인 4가 됩니다.
• 왜 유한체를 사용할까?
• 범위 제한: 컴퓨터에서 무한히 큰 숫자를 다룰 수는 없습니다. 유한체를 사용하면 모든 계산 결과가 정해진 범위(예: 0부터 p-1까지) 안에 머무르게 되어 오버플로우(overflow) 문제를 방지하고 계산을 효율적으로 만듭니다.
• 암호학적 특성: 유한체, 특히 타원 곡선과 결합된 유한체는 이산 로그 문제(DLP)와 같은 어려운 수학적 문제를 기반으로 하므로 암호학적으로 매우 안전한 환경을 제공합니다.

유한체 산술 회로는 바로 이 유한체 위에서 덧셈과 곱셈 연산을 수행하는 산술 회로입니다. 모든 계산의 중간값과 최종 결과는 정해진 유한체의 원소 중 하나가 됩니다.

4. 영지식 증명에서의 유한체 산술 회로 활용

영지식 증명(ZKP)의 핵심은 "어떤 계산을 올바르게 수행했다는 사실"을 계산의 입력값(비밀 정보)을 노출하지 않고 증명하는 것입니다. 이 과정에서 유한체 산술 회로가 결정적인 역할을 합니다.

증명 과정:

1. 문제의 산술 회로화 (Arithmetization)
• 증명하려는 모든 계산 문제(Computation)를 먼저 유한체 산술 회로로 변환합니다.
• 예를 들어, "나는 해시 함수 H(x)의 결과가 y가 되게 하는 비밀값 x를 알고 있다"를 증명하고 싶다고 가정해 봅시다.
• 이 해시 함수(예: SHA-256)의 복잡한 계산 과정을 수많은 덧셈과 곱셈 게이트로 이루어진 거대한 유한체 산술 회로로 표현합니다.
2. 다항식으로 변환
• 이렇게 만들어진 산술 회로는 하나의 거대한 다항식 또는 여러 다항식 제약 조건(polynomial constraints)의 집합으로 변환될 수 있습니다.​
• 회로의 각 게이트는 입력1 * 입력2 = 출력 (곱셈 게이트) 또는 입력1 + 입력2 = 출력 (덧셈 게이트)과 같은 간단한 다항식 관계로 표현됩니다.
• 결국, "원래 계산을 올바르게 수행했다"는 주장은 "이 다항식들을 모두 만족시키는 해(solution)를 알고 있다"는 주장과 수학적으로 동일해집니다.
3. 영지식 증명 생성
• 증명자(Prover)는 이 다항식들의 해(자신이 아는 비밀값 x를 회로에 넣었을 때 각 연결선(wire)을 따라 계산되는 값들)를 알고 있음을 증명하는 암호학적 증거(proof)를 생성합니다.
• zk-SNARKs, zk-STARKs와 같은 여러 영지식 증명 시스템들은 바로 이 다항식 관계를 효율적이고 간결하게, 그리고 영지식으로(비밀값 노출 없이) 증명하는 기술들입니다.

정리하자면, 유한체 산술 회로는 다음과 같은 역할을 합니다.

• 복잡하고 다양한 형태의 계산 문제를 영지식 증명 시스템이 이해할 수 있는 표준화된 형태, 즉 '다항식 문제'로 변환해주는 다리(bridge) 역할을 합니다. 이 변환 과정 덕분에 우리는 거의 모든 종류의 디지털 계산에 대해 영지식 증명을 생성하고 검증할 수 있게 됩니다.