ZKP-7. 다항식 약정 - 설정(Setup) 단계 상세 설명

영지식 증명, 특히 zk-SNARKs와 같은 시스템에서 설정(Setup) 단계는 전체 시스템의 보안과 신뢰성을 좌우하는 가장 중요한 첫 단추입니다. 이 단계의 주된 목적은 증명 생성(Proving)과 검증(Verifying) 과정에서 공통적으로 사용될 공개된 파라미터(Public Parameters)를 생성하는 것입니다. 이 파라미터를 CRS(Common Reference String) 또는 SRS(Structured Reference String)라고 부릅니다.

설정 단계의 핵심 목표

설정 단계의 목표는 명확합니다. 증명자와 검증자가 다항식에 대한 약속(Commitment)을 만들고, 특정 지점에서의 다항식 값을 공개하지 않으면서도 그 값이 올바르다는 것을 증명하고 검증할 수 있는 '암호학적 기반'을 마련하는 것입니다.

설정 단계의 세부 과정

설정 단계는 크게 두 가지 핵심 과정으로 나눌 수 있습니다.

1. 암호학적 기본 요소 선택

먼저, 다항식 약정 스킴에 사용할 기본적인 암호학적 환경을 결정합니다.

• 유한체(Finite Field) 선택: 다항식의 계수와 변수가 속할 숫자 체계를 정의합니다. 보통 매우 큰 소수 p를 사용하여 Fp​와 같은 유한체를 사용합니다.
• 타원 곡선 그룹(Elliptic Curve Group) 선택: 약속(Commitment)을 생성하기 위해 타원 곡선 암호(ECC)를 사용합니다. 특정 타원 곡선과 그 위의 생성점(Generator Point) G를 선택합니다. 이 그룹 연산은 이산 로그 문제(Discrete Logarithm Problem)의 어려움에 기반하여 보안성을 가집니다.

2. CRS(Common Reference String) 생성

이것이 설정 단계의 가장 핵심적인 부분입니다. CRS는 비밀 값(Secret Value)으로부터 파생된 일련의 암호화된 정보이며, 한번 생성되면 증명자와 검증자 모두가 사용하게 됩니다.

• 비밀 값(Toxic Waste) 생성: 아무도 알아서는 안 되는 비밀 값, τ (타우)를 무작위로 선택합니다. 이 값은 "독성 폐기물(Toxic Waste)"이라고도 불리는데, 만약 이 값이 노출되면 전체 증명 시스템의 보안이 깨지기 때문입니다. 즉, 이 비밀 값을 아는 사람은 누구나 거짓 증명을 만들어낼 수 있습니다.
• CRS 계산: 선택된 비밀 값 τ와 생성점 G를 사용하여 CRS를 계산합니다. 다항식의 최대 차수(degree)를 d라고 할 때, CRS는 다음과 같은 형태로 구성됩니다.
• $CRS={G,τG,τ^2G,…,τ^dG}$
• 여기서 각 요소($τ^iG$)는 타원 곡선 위의 한 점입니다. 이산 로그 문제의 어려움 때문에, 누군가 CRS 값들($τG,τ^2G,…$)을 보더라도 원래의 비밀 값 τ를 역산해내는 것은 계산적으로 불가능합니다.
• 비밀 값 폐기: CRS 생성이 완료되면, 비밀 값 τ는 반드시 안전하게 폐기되어야 합니다.

신뢰된 설정(Trusted Setup)의 중요성

위 과정에서 볼 수 있듯이, 비밀 값 τ를 생성하고 폐기하는 과정은 단 한 주체에 의해 수행될 경우 그 주체를 전적으로 신뢰해야만 합니다. 이를 신뢰된 설정(Trusted Setup)이라고 부릅니다. 만약 이 주체가 악의를 품고 τ를 보관한다면, 전체 시스템의 보안은 무너지게 됩니다.

이 '중앙화된 신뢰' 문제를 해결하기 위해 다자간 계산(Multi-Party Computation, MPC)을 이용한 '설정 의식'을 진행합니다.

1. 첫 번째 참가자가 자신의 비밀값 τ1을 생성하여 CRS를 계산합니다.
2. 첫 번째 참가자는 계산된 CRS를 두 번째 참가자에게 넘기고, 자신의 비밀값 τ1은 즉시 영구적으로 파기합니다.
3. 두 번째 참가자는 전달받은 CRS에 자신의 비밀값 τ2를 이용해 추가적인 계산을 합니다. (결과적으로 최종 비밀값의 일부가 τ1*τ2가 됩니다.) 그리고 자신의 τ2를 파기합니다.
4. 이 과정을 수십, 수백, 수천 명의 참가자가 릴레이처럼 이어서 반복합니다.

최종적으로 만들어진 CRS의 기반이 되는 전체 비밀값 τ는 τ1 * τ2 * τ3 * ... * τn이 됩니다. 이 최종 τ를 알기 위해서는 모든 참가자가 공모하여 자신의 비밀 조각을 공유해야만 합니다. 따라서 단 한 명의 참가자라도 정직하게 자신의 비밀 조각을 파기했다면, 최종 비밀값 τ는 그 누구도 알 수 없게 됩니다. 이것이 바로 신뢰를 분산시켜 시스템 전체의 보안을 확보하는 방법입니다.

따라서 참여자가 많을수록 신뢰 가정이 훨씬 약화되어 보안성이 높아집니다. 이더리움의 zk-SNARKs 도입 과정에서 진행된 "Powers of Tau" 세레모니가 바로 이러한 MPC 방식의 대표적인 예시입니다.

요약

다항식 약정의 설정(Setup) 단계는 다음과 같은 역할을 합니다.

1. 공통의 기반 마련: 증명자와 검증자가 공유할 공개 파라미터(CRS)를 생성합니다.
2. 보안의 초석: 아무도 모르는 비밀 값(τ)을 기반으로 CRS를 생성하여, 이 비밀 값을 아는 사람만이 증명을 위조할 수 있도록 만듭니다.
3. 신뢰성 확보: 신뢰된 설정 세레모니(특히 MPC 방식)를 통해 비밀 값이 안전하게 생성되고 폐기되었음을 보장하여 전체 시스템의 신뢰를 구축합니다.

이처럼 설정 단계는 한 번만 수행되지만, 그 결과물인 CRS는 해당 영지식 증명 시스템이 사용되는 내내 계속해서 활용되므로, 매우 신중하고 투명하게 진행되어야 하는 과정입니다.