Trusted setup은 어떻게 작동하는가?
이 글은 비탈릭의 “How do trusted setups work?” 글을 참고하여 작성하였습니다. (https://www.vitalik.ca/general/2022/03/14/trustedsetup.html)
Trusted setup 연구의 중요성
암호학은 계속해서 빠르게 발전하는 분야이며 그만큼 Trusted setup의 중요성도 커지고 있다. 물론 trusted setup이 필요하지 않은 암호 프로토콜이 있다면 문제는 간단해지겠지만, 현재 ZK-SNARKs나 DAS(data availability sampling)같은 대표적인 암호 프로토콜에서는 trusted setup이 필수적이다. Trusted setup은 말 그대로 신뢰할 수 있는 초기 설정인데, 한번 생성되면 이것을 바탕으로 각 프로토콜이 매번 실행될 수 있고 더 이상 초기 설정에 대한 추가적인 작업이 이루어지지 않아도 된다. 타원 곡선에서 랜덤한 s를 바탕으로 점들을 생성해 나갈 때 이 랜덤한 s를 정하는 것 역시 (trusted) setup의 일종이다. 현재 이더리움에서는 KZG 커밋을 주로 사용하고 있지만, 더 좋은 성능을 가지는 trusted setup이 있다면 프로토콜은 언제든지 변경될 수 있다.
Generating Setup
Trusted setup은 어떻게 만들어질까? 아래 그림처럼 셋업 데이터는 참여자들 각각이 비밀 정보(s1~s4)를 토대로 만들어지며, 공개 후 비밀 정보는 잊혀져야 한다. 그래야 신뢰할 수 있는 초기 설정이 구현될 수 있다. 최종 아웃풋으로 trusted setup 데이터가 만들어지면 더 이상의 비밀 정보를 가진 참여자의 관여는 필요없어지게 된다.
trusted setup에는 여러 종류가 있는데, 시초는 2016년 Zcash에서 사용했던 프로토콜에 적용된 셋업이다. 셋업 자체가 복잡하고 소통이 많이 필요했기 때문에 6명의 참여자만 관여되었으며, 이들 중 적어도 한명은 정직하다는 가정만으로 충분했다.
최근의 trusted setup으로는 powers-of-tau 셋업이 있다. KZG commitment에서도 powers-of-tau 셋업 방식이 사용된다. 이는 수백명의 사람들이 데이터를 만들기 위해 참여하고 마찬가지로 참여자들 중 한명만 정직해도 잘 작동되는 셋업이다. 여기서 ‘정직’하다는 의미는 아웃풋 데이터가 공개되기 전까지 비밀 정보를 누설하지 않음을 의미한다. 수백명 중 한명만 정직한 것은 1-of-N trust model이라고도 하는데, 이처럼 충분히 무신뢰에 가까운 모델을 “Well-executed model”이라 한다.
Commitment
커밋은 x를 밝히지 않으면서 x가 참인 것을 보이기 위한 일종의 ‘확인’ 작업이다. 대표적으로 SHA-256같은 해시 함수가 단방향 함수를 사용하여 H(x) 값을 통해 x가 참인지를 판단하는 커밋의 한 종류이다.
커밋에는 hiding과 binding이라는 두 가지 속성이 있다. Hiding은 커밋 값을 드러내지 않고 숨기는 특성이다. 예를 들어, 커밋하고자 하는 대상 v가 있을 때 C(v)를 계산하는 대신에 랜덤한 숫자 r을 같이 포함시켜 C(v, r)을 계산하는 것이다. Binding은 커밋하려는 대상이 다르면 커밋 값도 달라야한다는 특성이다. 즉 v가 아닌 v’에 대해 C(v)와 C(v’)는 다르다는 의미다.
커밋과 관련된 내용은 이 글을 참고하여 작성하였다. 커밋을 이해하는데 좋은 예시가 있어 아래에 첨부한다.
Powers-of-tau setup
이 셋업은 타원 곡선 시리즈 두 개가 필요하다. 타원 곡선은 생성자(generator)라고 하는 48 또는 96 bytes 길이의 점에다가 비밀 정보 s의 거듭제곱을 곱한 값들의 집합으로 이루어져있다. 아래 수식에서 G1의 경우 첫번째 타원 곡선의 생성자이며 크기는 48 bytes, G2는 96 bytes의 생성자이다. n1, n2는 각 타원곡선으로부터 만든 셋업들의 길이가 되겠다. 프로토콜에 따라 n2를 2로 고정하기도하고, n1과 n2를 모두 크게 설정하기도 하는데 참고로 이더리움의 DAS(data availibility sampling) 프로토콜의 경우 n1=4096, n2=16으로 설정한다. 그리고 s는 비밀 정보로, 타원 곡선 상의 점들을 생성하기 위해 사용되며 ‘trusted’를 위해 잊혀져야 되는 값이다.
다항식 P(x)에 대한 KZG 커밋은 위의 타원곡선 시리즈 중 첫번째 시리즈(G1)의 선형 조합으로 정의된다. G2 점들은 이렇게 만들어진 커밋이 맞는지 검증하기 위해 사용된다. 복잡하게 설명했지만 정리하면 다음과 같다.
- commit = Series 원소들의 선형조합 (=sigma(c_i * S_i))
- KZG commit에서는 S_i = G*(s^i) ← powers-of-tau setup
Trusted setup 값들은 어떤 의미를 가질까?
다항식 커밋(polynomial commitment)이란 크기 N 데이터(다항식)를 O(1) 객체(여기서는 타원 곡선 시리즈)로 확인하는 것을 의미한다. 커밋의 한 종류인 Pedersen 커밋의 경우, 위의 S_i를 타원 곡선 상의 서로 아무 관련이 없는 랜덤한 N개의 점으로 정의한다. 이는 실제로 IPA proof에서 사용하는 방식이다. 이렇게 랜덤한 점들의 선형 조합으로 커밋을 정의하면 제출된 증명에 대한 검증 시간은 O(N)이 걸린다. N가지 베이스 집합(S_i들을 원소로 갖는 집합)에 대해 서로 다른 다항식에 대한 커밋 값이 같도록 만들 수 있어서 각 S_i에 대한 고려를 일일이 해주어야 하기 때문이다. 예를 들어, 아래 그림에서처럼 특정 S_i를 2배로 잡아버리면 그 위치에 해당하는 계수가 1/2 줄어든 다항식에 대해 커밋 값이 같게 된다.
그러나 trusted setup에서는 S_i들 간에 비밀 정보 s만큼의 배수 관계가 있다. 위의 예시처럼 랜덤한 N개의 점들이 아니라 생성자로 부터 s의 거듭제곱 만큼 곱해져서 생성된 점들이기 때문에 어떤 [S_0, …, S_n-1]이 유효한 셋업이라면 위의 예시처럼 특정 S_i가 2배가 된 [S_0, …, 2*S_i, …, S_n-1]은 동시에 유효한 셋업이 될 수 없다. 따라서 trusted setup을 이용하면 O(n)만큼의 검증 시간이 필요하지 않고 O(c) (c는 상수)만큼의 시간이 필요하게 된다. 즉, 커밋 증명에 대한 검증 시간이 데이터 사이즈와 무관하게 된다.
그러나 만약 비밀 정보 s가 알려지게 되면, 누구나 다항식이 달라도 같은 커밋값이 나오게끔 할 수 있다. P(x)에 대한 커밋이 c일때, 이 커밋은 정의에 의해 P(x)*x/s, P(x)-x+s 등의 다항식의 커밋이기도 하기 때문이다. 따라서, 비밀 정보 s는 절대 공개되어서는 않되고, 생성 이후에 반드시 관여자들로부터 잊혀져야한다.
다수 참여자 셋업은 어떻게 가능할까?
한 명의 참여자가 셋업을 만드는 걸 보이는건 쉽다. 그냥 랜덤한 s를 선택해서 s로부터 타원 곡선 상 점들을 만들면 된다. 그러나 trusted setup을 만들기 위해 한 명만 관여되는 single-participant 상황은 안전하지 않다. 한 사람을 온전히 믿어야한다는 리스크가 있기 때문이다.
trusted setup을 만들기 위해서는 여러명이 참여하는 것이 좋은데, 보통 100명 이상이 일반적이다. powers-of-tau 셋업의 경우 아래 그림과 같이 데이터 생성이 이루어진다.
앞 사람이 자신의 비밀 정보를 이용해서 첫번째 셋업을 만들어 다음 사람에게 전달한다. 다음 사람은 그 셋업에다가 자신의 비밀 정보를 첨가하여 두번째 셋업을 만들게 된다. 즉, 두번째 셋업은 첫번째 셋업의 연장선이라 할 수 있다. 첫번째 셋업 리스트에서 element-wise하게 자신의 비밀 정보의 거듭제곱을 곱해나가는 방식으로 연장은 이루어진다. 즉, 이는 생성자에다가 이전 참여자들의 비밀 정보 곱의 거듭제곱을 곱한 형태이다.
참여자들은 서로 소통이 필요없다. 자신의 비밀 정보에 대해서 다른 참여자에게 전혀 알려줄 필요가 없기 때문이다. 따라서 참여자들 중 한명만 정직하더라도(자신의 비밀 정보를 누설하지 않음) 결합된 비밀정보는 절대 공개되지 않는다. s는 아는데, t는 모르는 경우 st에 대해서 알 길이 없기 때문이다.
셋업 검증하기
각 참여자가 실제로 셋업 데이터를 만드는데 참여했다는 것을 확인하기 위해, 각 참여자(Bob)는 그들이 받은 점들(G1*s)과 그들의 비밀정보(G2*t)로 이루어진 증명을 제출해야 한다. 아래 그림에서 같은 색으로 표시된 점들이 같은 참여자에 의해 제공된 점들이다.
누군가 자신의 참여여부에 대해 거짓말을 할 수도 있지 않을까? 그러나 이 점은 별로 문제가 되지 않는다. 적어도 한명이 본인의 참여 사실에 대해 정직하게 밝힌다면 시스템 전체는 안전하기 때문이다. powers-of-tau에서는 수백명의 참여자가 trusted setup 데이터 생성에 관여하기 때문에 확률적으로 모두가 거짓말을 할 가능성은 극히 드물다.
참여 사실에 대한 검증에 더해서, 각 참여자들에 의해 순차적으로 데이터가 잘 만들어지는지에 대한 확인도 필요하다. 이를 위해 모든 참여자에 의해 증명이 제출되면, 짝을 이루어 세 개씩 pairing check가 이루어진다. 아래 식에서 T1 = G2*s이다. pairing check 식에서 함수 안에 들어있는 파라미터들이 서로 비밀 정보 s만큼의 배수 관계에 있는지 체크하는 것이다.
그러나 참여자가 많아지게 되면 pairing check 횟수도 많아지게 될 것이고 그에 따라 비용도 비싸진다. 간단한 수학적 트릭을 사용하면 참여자 수가 많아짐에 따른 pairing check 빈도를 낮출 수 있는데, 자세한 내용은 원문을 참고하길 바란다.
Lagrange form의 셋업
일반적으로 다항식을 coefficient 형태로 전개해서 사용하는 것보다 evaluation 형태로 사용하는 것이 편하다. evaluation 형태는 x와 그에 대응하는 p(x)를 나열하는 형태이다.
- coefficient form: p(x) = 3x³+8x²+2x+6
- evaluation form: [19, 146, 9, 187] on [1, 189, 336, 148] (mod 337)
evaluation 형태의 장점은 다항식들을 곱하고 나누는 것을 O(N) 안에 할 수 있고, 특정 도메인에 대한 값이 맞는지 확인하는 evaluate 과정 역시 O(N) 안에 할 수 있다는 점이다. 여기서 N은 다항식의 차수를 의미한다. 참고로 샤딩과 관련된 DAS에서는 블롭 데이터들을 evaluation 형태로 나타낼 계획이라고 한다.
이러한 evaluation form의 장점으로 미루어 보아 trusted setup도 evaluation 형태로 바꾸어 사용한다면 다항식 커밋에 걸리는 시간이 훨씬 줄어들 것이다. 고속 푸리에 변환(FFT)을 이용하면 trusted setup을 evaluation 형태로 바꾸는 것이 훨씬 쉬워진다고 한다.
Future of trusted setups
하나의 잘 만들어진 trusted setup을 통해 광범위한 프로토콜이 실행 가능해지면, 이는 좋은 셋업이다. 이러한 보편성이 trusted setup이 가져야할 특성이며, 보다 안전하고 신뢰할 수 있는 환경을 구축하기 위해 보편적인 trusted setup에 대한 지속적인 연구가 필요하다.
Opinion
비탈릭이 쓴 글에서는 비밀 정보 s를 사용하여 셋업 데이터가 어떻게 만들어지는지에 대한 내용은 자세히 설명되어 있었으나, 셋업이 신뢰를 얻기 위해 비밀 정보 s가 어떻게 잊혀지는가에 대해서는 언급이 없었다. 셋업 데이터가 다 만들어진 이후일지라도 생성에 관여한 참여자들이 s에 대해 누설하게 되면 프로토콜 자체가 의미가 없어지는 것이기 때문에 꽤 중요한 부분인 것 같은데 아직 이 부분에 대한 연구가 많이 이루어지지 않은 것 같다. 좀 더 알아보아야겠다 :)
