해시넷
"검증가능지연함수"의 두 판 사이의 차이
잔글 (→요소) |
|||
| 9번째 줄: | 9번째 줄: | ||
VDF는 setup, evaluation, verify라는 세 가지 요소로 이루어져 있다. 가장 핵심 요소는 evaluation 함수로, 주엊인 parameter 값과 입력값에 대해 적절한 출력값을 계산하며 부가적으로 출력값에 대한 proof도 함께 계산할 수 있다. Verify 함수는 주어진 출력값이 주어진 parameter와 입력값으로부터 계산되었는지 확인하는 함수이며, setup 함수는 사용자가 설정한 값에 대해 의도된 시간 범위 사이에 함수값이 계산되도록 하는 parameter 및 함수의 정의역과 공역에 대한 제약을 주게 된다. 각 함수에 대한 자세한 설명은 다음과 같다. | VDF는 setup, evaluation, verify라는 세 가지 요소로 이루어져 있다. 가장 핵심 요소는 evaluation 함수로, 주엊인 parameter 값과 입력값에 대해 적절한 출력값을 계산하며 부가적으로 출력값에 대한 proof도 함께 계산할 수 있다. Verify 함수는 주어진 출력값이 주어진 parameter와 입력값으로부터 계산되었는지 확인하는 함수이며, setup 함수는 사용자가 설정한 값에 대해 의도된 시간 범위 사이에 함수값이 계산되도록 하는 parameter 및 함수의 정의역과 공역에 대한 제약을 주게 된다. 각 함수에 대한 자세한 설명은 다음과 같다. | ||
*'''setup(lambad, t) → pp''' : lambda, t에 대한 parameter pp를 계산하고, evaluation 함수에 대한 도메인을 결정한다. | *'''setup(lambad, 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에 비례함에 따라 두 함수간의 계산 시간이 지수배가 차이나도록 구성하기 위함이다. | *'''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에 비례함에 따라 두 함수간의 계산 시간이 지수배가 차이나도록 구성하기 위함이다. | ||
| + | |||
==참고자료== | ==참고자료== | ||
2019년 10월 11일 (금) 09:33 판
검증가능 지연 함수(VDF; verifiable delay function)는 기존의 암호학 분야에 존재하는 문제들을 활용해서 계산시간이 매우 오래 걸리지만 입력값과 출력값이 주어졌을 경우그 두 값에 대해 적절한 함수인지 확인하는 시간이 매우 짧은 함수이다.
개요
성질
- 계산하는데 시간이 매우 오래걸린다. 입력값이 주어진 후에 출력값을 계산하는 데 있어서 최대한 병렬화가 불가능한 부분이 일정부분 이상 포함되어야 한다. 즉 순차적인 계산이 필수적으로 포함되어 병렬화된 기계로부터 쉽게 계산되어서는 안된다. VDF 함수 같은 경우에는 병렬화된 작업의 갯수 자체가 충분히 크더라도 필수적으로 수행해야 하는 순차적인 계산이 충분히 많은 작업을 의미한다. 그렇기 때문에 계산이 빠른 기계가 많더라도 순차적인 계산을 수행해야 하기 때문에 충분한 계산 시간을 필요로 하게한다.
- 짧은 시간 안에 확인이 가능하다. 주어진 입력값으로부터 계산된 출력값이 맞는지에 대한 여부가 매우 효율적인 방식으로 확인되어야 함을 의미한다. 입력값 x로부터 f(x)를 계산해서 출력값 y가 나온다고 할 때, x로부터 직접적으로 f(x)를 계산하여 y를 찾는데는 많은 계산이 요구되지만, 역함수를 사용해서 f-1 (y)를 계산하여 x=f-1 (y)임을 확인 하는것은 매우 쉬운 경우를 말한다. 빠른 시간안에 확인이 되어야 한다. 그리고 이때 일반적으로 이에 대한 간단한 증거를 포함하기도 한다.
- 일반적으로 확인이 가능해야 한다. 어떤 자격을 갖춘 사람이 아닌 확인을 원하는 모든 사람이 계산 결과에 대해 입력값과 출력값이 적절한지 확인할 수 있어야 한다.
- 변경이 가능해야 한다. 계산에 걸리는 총 시간을 함수를 설정하는 사람이 조절할 수 있어야 한다.
요소
VDF는 setup, evaluation, verify라는 세 가지 요소로 이루어져 있다. 가장 핵심 요소는 evaluation 함수로, 주엊인 parameter 값과 입력값에 대해 적절한 출력값을 계산하며 부가적으로 출력값에 대한 proof도 함께 계산할 수 있다. Verify 함수는 주어진 출력값이 주어진 parameter와 입력값으로부터 계산되었는지 확인하는 함수이며, setup 함수는 사용자가 설정한 값에 대해 의도된 시간 범위 사이에 함수값이 계산되도록 하는 parameter 및 함수의 정의역과 공역에 대한 제약을 주게 된다. 각 함수에 대한 자세한 설명은 다음과 같다.
- setup(lambad, 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에 비례함에 따라 두 함수간의 계산 시간이 지수배가 차이나도록 구성하기 위함이다.
참고자료
같이 보기
