Brief Overview of Verifiable Delay Function
Writer: 장희수(Huisu Jang)
Reviewed by 김종호(Jason Kim), 오영택(Youngtaek (Robbie) OH), 최지혁(Jihyeok Choy)
서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’의 VDF(Verifiable Delay Function)에 대한 글입니다.
이 글은 (Dan Boneh et al., 2018) 논문에서 제시된 verifiable delay function (VDF) 이라는 새로운 함수 형태에 관한 설명 및 응용의 축약된 형태의 요약이며 다음의 VDF에 대한 설명 영상을 주로 참조하였다. VDF는 기존의 암호학 분야에 존재하는 문제들을 활용해서 계산시간이 매우 오래 걸리지만 입력값과 출력값이 주어졌을 경우 그 두 값에 대해 적절한 함수인지 확인하는 시간이 매우 짧은 함수를 말한다. 다음의 예시를 통해 어떤 상황에서 응용이 적합한지 생각해보도록 하자.
예를 들어, 주식 시장을 상상해보자. HFT(High-frequency trading) 거래를 하는 경우 시장이 마감되기 바로 전 순간에 많은 양의 특정 주식을 매수하거나 매도하여 해당 주식의 가격을 조작하는 것이 가능하다. 즉, 이 경우 나의 구매행위가 즉각적으로 시장에 반영되기 때문에 이러한 조작을 행할 수 있다. 나의 구매 행위가 언제 시장에 반영될 지 알 수 없다면 이러한 의도적인 가격 조작은 불가능할 것이다.
블록체인 상에서 random beacon을 활용하는 경우 또한 위의 예시와 매우 유사한 상황이 벌어지게 된다. 블록체인 상에서random beacon이란 블록체인으로부터 형성되는 해시값을 활용해서 임의의 수를 만드는 응용을 말한다. 특정 시점에서 다음 블록을 형성하는 데에 현재 블록의 헤더가 영향을 미치는 경우 현재 블록을 생성한 마이너는 현재 블록을 공개하거나 공개하지 않음으로써 다음 블록의 생성에 자신의 특정한 의도를 반영할 수 있게 된다. 이러한 현상은 마이너가 블록의 생성에 성공하면 블록에 대한 해시값의 계산이 매우 빠르기 때문에 일어나게 된다.
정리해서 말하자면, 어떤 행위의 결과가 한 시스템에 영향을 미친다는 것을 가정할 때 그 행위의 결과가 도출되는 시간이 매우 짧다면 그 행위를 행사하는 행위자는 결과의 공개여부를 결정하여 시스템에 의도적인 영향을 미칠 수 있다.
이러한 상황에서 VDF라는 개념은 특정 행위의 결과가 도출되는 시간을 매우 지연시켜, 행위자가 자신의 결과를 조작하여 시스템에 의도적인 영향을 미치는 것을 최대한 방지 한다.
지금부터는 VDF 함수가 만족해야 하는 성질에 대해서 설명하고자 한다.
- 계산하는데 시간이 매우 오래걸린다(물리적인 시간): 입력값이 주어진 후에 출력값을 계산하는 데 있어서 최대한 병렬화가 불가능한 부분이 일정부분 이상 포함되어야 한다. 즉 순차적인 계산이 필수적으로 포함되어 병렬화된 기계로부터 쉽게 계산되어서는 안된다. 일반적으로 컴퓨터가 하는 계산은 속도를 향상시키기 위해 위와 같이 마스터 스레드로부터 병렬처리가 가능한 경우에는 병렬화 작업을 추가하여 병렬화된 계산의 연속적인 구성으로 전체 마스터 스레드를 구성한다. 본 글에서 논의하고자하는 VDF함수 같은 경우에는 병렬화된 작업(parallel task)의 갯수 자체가 충분히 크더라도 필수적으로 수행해야 하는 순차적인 계산이 충분히 많은 작업을 의미한다. 그렇기 때문에 계산이 빠른 기계가 많더라도 순차적인 계산을 수행해야 하기 때문에 충분한 계산 시간을 필요로 하게 한다.
- 짧은 시간 안에 확인이 가능해야 한다: 주어진 입력값으로부터 계산된 출력값이 맞는지에 대한 여부가 매우 효율적인 방식으로 확인되어야 함을 의미한다. 입력값 x로부터 함수 f(x)를 계산해서 출력값 y가 나온다고 할 때, x로부터 직접적으로 f(x)를 계산하여 y를 찾는데는 많은 계산이 요구되지만, 역함수를 사용해서 f-1 (y)를 계산하여 x=f-1 (y)임을 확인하는 것은 매우 쉬운 경우를 말한다. 빠른 시간안에 확인이 되어야 한다. 그리고 이때 일반적으로 이에 대한 간단한 증거를 포함하기도 한다.
- 일반적으로 확인이 가능해야 한다: 어떤 자격을 갖춘 사람이 아닌 확인을 원하는 모든 사람이 계산 결과에 대해 입력값과 출력값이 적절한지 확인할 수 있어야 한다.
- 변경이 가능해야 한다: 계산에 걸리는 총 시간을 함수를 설정하는 사람이 조절할 수 있어야 한다.
지금부터는 암호학에서 사용되는 비슷한 개념을 통해 VDF와의 공통점 및 차이점을 알아보고, 이를 통해 VDF에 대한 이해를 높이도록 해보자. VDF와 비슷한 개념으로는 Time-lock puzzles과 proofs of sequential work (Mahmoody et al) 을 들 수 있다. Time-lock puzzles란 문제를 풀기까지에 시간이 소요되는 문제로 VDF와는 달리 문제 갱신 시 마다 문제에 대한 재설정을 해야한다. 즉, 어떤 약속된 제출자가 한 번의 퍼즐에만 유효한 비밀키와 공개키를 준비한다. 이처럼 제출자에게 적절한 비밀키와 공개키를 생성하는 책임이 부과하는 것을 신뢰가 형성된 상태 (trusted-setup)을 구성한다고 한다. 이러한 형태의 개념에서는 신뢰가 형성된 상태를 만든 이후에만 퀴즈의 정답에 대한 일반적인 확인이 가능하게 된다. 만약 새로운 퀴즈를 풀기 위해서는 다시 문제 제출자가 해당하는 비밀키와 공개키를 생성하여 다음 문제를 위한 새로운 셋업을 진행해야 한다. 이러한 형태의 문제에서는 물리적인 시간이 매 퀴즈가 새로 제출될 때마다 다시 시작한다는 점에서 VDF와는 차이점을 가진다. VDF같은 경우에는 문제를 제출하고, 확인하기 위한 신뢰가능한 셋업 설정의 단계를 생략한다.
두 번째 비슷한 개념인 proofs of sequential work은 일반적으로 연속된 해쉬함수를 푸는 것과 비슷한 개념이다. 이 경우에는, VDF처럼 신뢰가능한 셋업이 필요하지 않고 누구나 일반적으로 입력값과 출력값이 옳은지에 대해서 확인할 수 있다. 하지만 이러한 문제의 경우는 함수가 될 수 없다는 특징을 가지고 있다. 결국 VDF와 같이 입력값에 대해 유일한 출력값을 가지지 않기 때문에 입력값에 대한 유일성을 확인하는 것이 불가능하다.
다시 블록체인에 관한 응용으로 돌아와보자. 앞에서 말한 것처럼 비트코인과 이더리움의 블록들은 random beacon에서 종종 활용되고있다. 이 때 현재 블록체인의 해시값을 기반으로 전체 체인의 의사결정에 영향을 미치는 임의의 숫자를 형성하는 random beacon이 있다고 생각해보자. 이 경우에 가장 최근 블록을 만들어 낸 마이너는 random beacon의 결과에 영향을 행사하기 위해 현재 찾아낸 블록을 공개하지 않을 수 있다. 이러한 문제 (어떤 행동의 결과가 즉각적으로 체인의 의사결정에 반영되는 경우 생성되는 문제)를 해결하기 위한 솔루션의 하나로 VDF를 활용하여 블록이 random beacon에 미치는 영향을 지연시키는 방법을 생각해 볼 수 있다. 마이너는 자신의 블록이 random beacon에 어떤 영향을 미칠지 예측을 할 수가 없기 때문에 블록을 드러내지 않고 가지고 있을 유인이 매우 적어지게 된다. 이외에도 PoW나 PoS를 대신해서 Proof of Resource라는 새로운 방식의 consensus를 제안해 볼 수 있는데 이 개념에 대해서는 추후에 설명하도록 하고 지금부터는 VDF의 개념에 대한 구체적인 설명 및 VDF로 활용가능한 다양한 예시들을 제시하도록 하겠다.
VDF는 다음과 같이 setup, evaluation, verify라는 세 가지 요소로 이루어져 있다. 가장 핵심 요소는 evaluation 함수로, 주어진 parameter 값과 입력값에 대해 적절한 출력값을 계산하며 부가적으로 출력값에 대한 proof도 함께 계산할 수 있다. verify 함수는 주어진 출력값이 주어진 parameter와 입력값으로부터 계산되었는지 확인하는 함수이며, setup 함수는 사용자가 설정한 값에 대해 의도된 시간 범위 사이에 함수값이 계산되도록하는 parameter 및 함수의 정의역과 공역에 대한 제약을 주게 된다. 각 함수에 대한 자세한 설명은 다음과 같다.
- setup(lambda ,t) → pp
: lambda,t 에 대한 parameter pp를 계산하고, evaluation 함수에 대한 도메인을 결정한다. - Eval(pp,x) → y,pi
: pp로부터 얻어진 도메인으로부터 입력값 x를 취한 뒤에 해당하는 출력값 y와 해당하는 proof pi를 계산한다. - Verify(pp,x,y, pi) → {Accept, Reject}
: 입력값 x, 출력값 y, proof pi , parameter pp가 주어지면 해당 출력값이 해당 입력값 및 parameter로부터 얻어진 값인지 확인한다. 이 때, 이 verfiy함수의 계산시간은 1번의 setup 함수에서 parameter pp를 찾기 위한 입력변수 t에 대해 의존하며, 총 소요시간은 O(polylog(t))가 되도록 하는 함수 Eval 과 Verify를 설정한다. 이는 Eval의 계산시간이 t에 비례함에 따라 두 함수간의 계산 시간이 지수배가 차이나도록 구성하기 위함이다.
앞서 언급했듯이, VDF는 1. 계산을 위해 충분한 순차적 단계를 요구하는 반면, 2. 역함수의 계산은 매우 효율적으로 이루어져야 하고, 3. 일반적인 확인 및 4. 구성의 변경이 가능해야 한다. 이러한 VDF가 갖추어야 하는 주요 특징은 크게 유일성 (함수의 입력값에 대하여 출력값이 유일하게 결정되는 것) 및 순차성 (주어진 작업 x를 달성하기 위해서는 x1,x2,…,xn과 같은 작업이 순차적으로 이루어져야 하는 것) 으로 압축할 수 있다. 먼저 VDF의 Evaluation 함수는 setup 함수로부터 결정되는 도메인 C에 대해 정의되는 ‘함수’로서 입력값에 대한 출력값의 유일성을 만족한다. 두 번째 특징은 VDF의 정의로부터 확보되지는 않지만 일반적으로 받아들일 수 있는 가정 및 VDF를 구성하는 함수를 ‘적절하게’ 정의하여 (물론, 적절하게 정의하는 부분이 가장 중요하고 어려운 지점이다.) 얻을 수 있는 순차성으로, 다항함수에 비례하는 병렬적인 처리장치가 랜덤하게 출력값을 예측하기 어렵게 한다. 실제로 본 논문에서는 다음과 같은 가상의 게임을 정의하고 이 때 이 가상의 게임에서 악의적인 의도를 가진 상대가 이길 확률이 0에 수렴한다는 것을 가정하여 이러한 순차성을 확보한다. 가상의 게임의 설정은 다음과 같다.
악의적인 의도를 가진 상대는 다음과 같은 두 개의 함수, A0 와 A1를 가지고 있다. 이 때 VDF와 동일한 setup함수로 부터 임의의 파라미터 pp를 추출하여 전처리 한 후에 L을 얻는다. 그 후, 정의역에 해당하는 임의의 x에 대해 함수 A1를 통한 가상의 출력값 yA를 계산하고, 이 때 이 가상의 출력 값이 Evaluation함수에 대해서 accept를 얻는다면 이 악의적인 참여자가 게임에서 이기게 된다고 가정한다. 이러한 정의역에 속해있는 임의의 x에 대해 가상의 출력값을 계산하는 방법은 병렬화하는 것이 가능하다. 본 논문에서는 이렇게 병렬화된 계산을 활용하는 악의적인 사용자가 VDF를 활용하는 사용자를 이길 확률이 거의 0에 가깝다는 것을 가정하고 있다. 실제 작업에서 이러한 순차성은 병렬 처리장치가 랜덤하게 출력값을 예측하는 속도와 VDF로부터 순차적으로 계산되는 속도 간에 매우 큰 차이가 나게 함으로써 실험적으로 이러한 가정을 확보하고자 하며 이를 위해 적절한 VDF를 정의하는 것이 전체 과정에서 가장 어렵고 중요한 작업이 되는 것이다.
지금부터는 이 작업에 관한 설명을 진행하기에 앞서 하나의 예시를 통해 어떠한 과정을 통해 순차성을 확보하는지 설명하고자 한다.
위 수식 2는 입력값에 대해 연속적인 해시함수를 사용해서 출력값을 얻어내는 과정을 나타낸다. 위 수식은 순차성을 확보하고 있지만, 얻어진 출력값이 주어진 입력값으로부터 도출된 것임을 확인하기 위해서는 모든 해시함수를 다시 수행해야 한다. 즉, 함수의 Verfication과정이 Evaluation 과정만큼 소요되며 이러한 형태의 해시체인은 VDF가 될 수 없다.
수식 3와 같이 SNARKs (Succinct Non-interactive Argument of Knowledges)를 활용한 해시체인을 고려해보자. SNARK란 non-interactive한 방식으로 어떠한 사실에 대한 확인(verify)를 함에 있어서 간결한 형태의 proof를 달성하는 것을 말한다. 일반적인 SNARK는 다음과 같은 방식으로 이루어진다: 1. 먼저 검증자(verifier)가 keygen을 사용하여 비밀키와 공개키를 생성한다. 2. 만들어진 비밀키와 증명하고자 하는 witness, witness의 해시값을 사용해서 증명자(prover)는 간결한 형태의 proof pi를 다시 검증자에게 보낸다. 3. 검증자는 이 전달받은 proof와 공개키를 사용해서 검증자가 witness를 가지고 있음을 확인한다.
이 때 수식 2의 연속된 해시함수와의 가장 큰 차이점은 ‘간결한 형태의 proof’가 함께 검증자에게 주어진다는 사실이다. 이 증거품으로 인해서 검증자는 검증을 위해 수식 2에서와 같이 연속된 해시함수를 다시 계산할 필요가 없다. 수식2에서의 경우에는 검증자와 증명자가 모두 연속된 해시함수를 적용시킴으로써 확인 및 증명을 수행하였다면, SNARK 개념을 활용하는 경우에는 연속된 해시함수의 역함수를 검증자가 가지고 있어서 역함수에 출력값과 함께 넣을 입력값으로써 증명자로부터 받은 간결한 proof를 사용한다는 점이 가장 큰 차이점이다. 즉 역함수를 알고 있기 때문에 증명자로부터 간결한 proof를 받기만 한다면 일반적으로 확인가능(generic verifiable)하게 된다. 하지만 이러한 SNARK를 활용한 체인을 계산하기 위해서는 수식 2의 해시체인의 경우와는 달리 keygen 함수, proof pi생성을 위한 증명 알고리즘 함수, 마지막으로 verify를 위한 역함수를 계산해야 한다. 이러한 함수들의 경우 고도로 병렬화하는 것이 가능하기 때문에 순차성을 확보하는 것이 일반적으로 어렵다고 알려져있다. 더 자세한 설명은 다음 사이트를 참조하기 바란다.
SNARK를 활용해 VDF를 만들 때 생기는 문제를 해결하기 위해 본 논문에서는 “incrementally verifiable”이라는 개념을 도입하여 수식 3과 같이 새로운 형태의 해시체인을 형성한다.
수식 2의 proof가 해시체인 전체에 대한 proof를 제공하는 것과 달리 수식 3에서는 매번 해시 체인이 확장될 때 마다 새로운 proof를 형성한다. Proof i 는 i번째 스텝의 해시함수가 제대로 계산되었다는 사실 및 i-1번째 스텝에 대한 proof i -1이 제대로 이루어졌다는 사실을 보장하게 된다. 각 스텝들이 맞물려 proof되도록 함으로써 순차성을 확보하였다. 이러한 incrementally verifiable 한 계산에 대한 구체적인 내용은 다음의 논문을 참고하길 바란다 (Valiant 08 , BCCT 12 ). 특히, 위와 같이 설정을 하게 되면 verification을 위한 신뢰성 확보(trusted-setup)이 신뢰할 수 있는 참여자에 의존하는 것이 아니기 때문에 효율적으로 이루어질 수 있으며 어떤 누구라도 잘못된 proof를 잡아내기 위해 위의 확인작업을 수행할 수 있다.
지금부터는 논문에서 제시된 VDF 함수 중 하나의 형태에 대해 논의하고 그러한 형태의 VDF 함수를 구체적으로 살펴보도록 하겠다. Zp의 원소인 challenge c와 소수 p를 설정한 뒤에 x^2 = c mod p를 만족하는 x를 찾는 문제를 푼다고 생각해보자. (여기서는 논의의 간결함을 위해 c가 제곱잉여(quadratic residual) 라고 가정하자. 정수 n에 대한 제곱잉여란 제곱수의 n에 대한 동치류를 뜻한다. 예를 들어, 정수 7에 대해, 1^2 = 1, 3^2 = 2, 2^2 = 4 (mod 7)이므로, 1,2,4는 7에 대한 제곱잉여이며 3,5,6은 7에 대한 제곱잉여가 아니다. [전체 논의에서는 이 가정에 대해서 고려하지 않아도 된다.]) 만약 매우 큰 소수 p를 설정한다면 이 소수에 대해서 c와 합동인 x를 찾는 것은 간단한 작업은 아니다. 하지만 x값을 찾고난 뒤에는 합동식에 대입함을 통해서 간단하게 주어진 x가 합동식을 만족하는지 빠른 시간 안에 확인하는 것이 가능하다. 이 경우 해 x를 찾기위한 과정(Evaluation)에 긴 시간을 소비하는 반면 찾은 해 x가 합동식의 해가 맞는 지 확인하는 과정(Verification)에는 매우 짧은 시간을 소비함으로써 VDF에 적용하기 적절한 예시가 될 수 있다. 하지만 일반적인 합동식을 해결하기 위한 문제는 고도로 병렬화 하는 것이 가능하기 때문에 Evaluation 과정과 Verification 과정 간의 소요되는 시간의 간극을 줄이기가 쉽다. 다음은 일반적인 소수 p에 대한 합동식을 풀기 위해서 걸리는 계산 시간은 다음과 같다.
- (Non-optimized) Evaluation time : O((logp)^3)
이 때 이미 알려진 해가 하나 존재하게 되는데, 그 것은 x=c^((p+1)/4) mod p이며 이 것을 계산하기 위해서는 c 에 대해 logp만큼의 연속적인 곱셈 연산을 필요로 한다. (쉽게 생각하면 2의 8승을 계산하기 위해서는 2의 4승만 알면되고, 2의 4승 계산을 알기 위해서는 2의 제곱승만 알면된다.) 이 때 각 수가 logp bit로 표현되어 있다. - (Optimized(병렬화 과정을 최대한 추가한 버전)) Evaluation time : O((logp)^2)
이 경우에는 곱셈에 대한 병렬화를 통하여 logp만큼 속도를 증가시켜 다음과 같이 향상된 속도를 얻을 수 있다. - Verification time : O((logp)^2)
이 때는 lop bit로 이루어진 두 숫자에 대해 한 번의 곱셈 operation이 필요하다. - Output size: logp bit
위의 합동식에 관한 문제에서는 병렬화를 통해서 Evaluation 함수와 Verfiy함수의 계산시간에 큰 차이가 없게 된다. 하지만 VDF의 근본적인 목적은 이 두 함수의 계산 시간의 차이를 벌리는 것이고, 이러한 목적을 달성하기 위해서 저자들은 일반화된 형태의 다항식 역상화 (Polynomial inversion)이라는 문제를 생각하게 된다. 이러한 문제는 기본적으로 f(x)=c를 만족하는 유일한 해 x를 가지는 f를 만들어내는 것이다. 이러한 조건의 f를 찾는다면 유일해 x를 찾기 위한 계산 시간은 매우 길면서 동시에 그 해가 맞음을 확인하는 것은 매우 간단한 작업이 될 것 이기 때문이다. 이러한 함수에 적용하기 위해 다음과 같은 Permutation polynomials를 생각해볼 수 있다.
Permutation polynomials on finite field Fq:
• 𝑓: Fq →Fq is a permutation
• 𝑓 = a0*x^d+a1*x^(d-1)++ad
• deg 𝑓 = 𝑑, 𝑓 is “sparse” if many ai = 0
• Evaluation: each degree d “term” is O(log(d)) multiplications, e.g. (ax+b)^d
이 문제에서는 f와 같이 생긴 다항 함수의 출력값이 c와 q에 대해서 합동인 입력값 x를 찾는 것을 목표로 한다. 결국 이러한 문제의 유일한 해를 찾는 방법은 x^q-x 와 f(x)-c간의 최대공약수를 찾음으로써 가능하게 되며 이 최대공약수를 찾는 방법에는 연속적인 d 단계가 포함되어 있으며 각 스텝 마다 d번의 연산 (병렬화가 가능한)을 포함하게 된다. 그렇기 때문에 Generalize polynomial inversion function으로부터 얻어진 이상적인 permutation polynomial의 각 함수의 계산 시간은 다음과 같다.
- (Non-optimized) Evaluation time : O(d^2)
- (Optimized) Evaluation time : O(d)
- Verification time : O(logd)
- Output size: logq = 256 bit
이를 통해서 일반적인 합동식에서는 두 함수의 계산 시간에 차이가 생기지 않는 반면 polynomial inversion을 사용하는 경우 Eval time과 Verify time사이에 exponential한 차이를 만들 수 있다는 것을 확인할 수 있다. 이로부터 두 방법의 계산 시간의 비교를 다음과 같이 실험적으로 제시하는 것이 가능하다.
지금까지 합동식과 관련된 문제들로부터 VDF의 하나의 예시를 만드는 과정에 대하여 논의하였다. 궁극적으로 VDF가 추구하는 목적은 verify 함수와 evaluation 함수의 계산 시간 간에 큰 차이를 만들어내는 것이며 본 논문에서는 Permutation polynomial로 부터 만들어낸 하나의 예시함수를 다음과 같이 제시하고 있다.
추후에는 Incrementally verifiable SNARK를 활용한 VDF형성에 대해 논의하고, 실제로 블록체인 상에서 어떤 형태로 VDF가 활용되는지 논의하도록 하겠다.
