해시넷
영지식 스나크 편집하기
편집을 되돌릴 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 저장해주세요.
| 최신판 | 당신의 편집 | ||
| 24번째 줄: | 24번째 줄: | ||
간결함은 영지식 스나크의 핵심 키워드이다. 상호작용 증명 시스템(interactive proof system)은 검증자가 한정된 계산 자원을 가지고 있음을 전제로 한다. 증명자가 특정한 지식을 알고 있다는 증거로 제출한 증명이 상당히 많은 양의 데이터를 포함하고 있다면, 이 증명은 굉장히 비효율적이다. 따라서 영지식 스나크에서는 비상호작용 영지식 증명의 크기를 줄이고 빠른 시간 내에 검증을 수행할 수 있도록 하여 비상호작용 영지식 증명의 실용성을 극대화하였다. 영지식 스나크는 다음과 같은 세 과정으로 이루어지며 이를 통해서 검증자는 증명자의 지식를 직접 확인하지 않고도 빠른 시간 내에 이를 검증 할 수 있게 된다.<ref name="Jungwoo Pyo"></ref> | 간결함은 영지식 스나크의 핵심 키워드이다. 상호작용 증명 시스템(interactive proof system)은 검증자가 한정된 계산 자원을 가지고 있음을 전제로 한다. 증명자가 특정한 지식을 알고 있다는 증거로 제출한 증명이 상당히 많은 양의 데이터를 포함하고 있다면, 이 증명은 굉장히 비효율적이다. 따라서 영지식 스나크에서는 비상호작용 영지식 증명의 크기를 줄이고 빠른 시간 내에 검증을 수행할 수 있도록 하여 비상호작용 영지식 증명의 실용성을 극대화하였다. 영지식 스나크는 다음과 같은 세 과정으로 이루어지며 이를 통해서 검증자는 증명자의 지식를 직접 확인하지 않고도 빠른 시간 내에 이를 검증 할 수 있게 된다.<ref name="Jungwoo Pyo"></ref> | ||
| − | * '''Keygen : key generator G를 이용해 key pair (pk, vk)를 생성하는 과정''' | + | * '''Keygen: key generator G를 이용해 key pair (pk, vk)를 생성하는 과정''' |
: 증명자가 알고 있다고 주장하는 값인 witness(w)가 있다. 이때 이를 매개변수로 받는 특정 프로그램 C가 있다고 하자. 프로그램 C는 다음과 같다고 가정한다. | : 증명자가 알고 있다고 주장하는 값인 witness(w)가 있다. 이때 이를 매개변수로 받는 특정 프로그램 C가 있다고 하자. 프로그램 C는 다음과 같다고 가정한다. | ||
| 41번째 줄: | 41번째 줄: | ||
O (1 + n + T) · log(1 + n + T) | O (1 + n + T) · log(1 + n + T) | ||
| − | * '''Prove : prover가 proof(prf)를 생성하는 과정''' | + | * '''Prove: prover가 proof(prf)를 생성하는 과정''' |
: 증명 알고리즘을 P, 증명하고자 하는 증인인 w, w의 해시를 x라고 할 때, 증명을 구하는 방법은 다음과 같다. 증명자는 prf를 계산한 후, 검증자에게 prf만을 전달한다. prf을 계산하는 데 걸리는 시간은 입력값 x와 w의 크기에 비례하여 길어진다. prf가 계산된 이후에는 당연히 prf로부터 w값을 유추할 수 없으며, prf의 길이는 매우 짧다. 이는 기존의 영지식 증명이 가지고 있지 않은 간결함의 특성을 갖게 해주는 요소이다.<ref name="Jungwoo Pyo"></ref> | : 증명 알고리즘을 P, 증명하고자 하는 증인인 w, w의 해시를 x라고 할 때, 증명을 구하는 방법은 다음과 같다. 증명자는 prf를 계산한 후, 검증자에게 prf만을 전달한다. prf을 계산하는 데 걸리는 시간은 입력값 x와 w의 크기에 비례하여 길어진다. prf가 계산된 이후에는 당연히 prf로부터 w값을 유추할 수 없으며, prf의 길이는 매우 짧다. 이는 기존의 영지식 증명이 가지고 있지 않은 간결함의 특성을 갖게 해주는 요소이다.<ref name="Jungwoo Pyo"></ref> | ||
prf = P(pk, w, x) | prf = P(pk, w, x) | ||
| − | * '''Verify : verifier가 prf를 verifying하는 과정''' | + | * '''Verify: verifier가 prf를 verifying하는 과정''' |
: 검증자는 증명자로부터 prf를 전달받은 후, 검증 알고리즘 V(verifying algorithm V)를 수행하여 prf의 진위 여부를 판단한다. 검증에 걸리는 시간은 매우 짧은데, 이 역시 영지식 스나크가 간결함의 특성을 가지는 요소 중 하나이다. 아래 값이 TRUE이면 증명자는 w값을 정말 알고 있다고 할 수 있고, FALSE이면 증명자는 w값을 속였다고 판단할 수 있다.<ref name="Jungwoo Pyo"></ref> | : 검증자는 증명자로부터 prf를 전달받은 후, 검증 알고리즘 V(verifying algorithm V)를 수행하여 prf의 진위 여부를 판단한다. 검증에 걸리는 시간은 매우 짧은데, 이 역시 영지식 스나크가 간결함의 특성을 가지는 요소 중 하나이다. 아래 값이 TRUE이면 증명자는 w값을 정말 알고 있다고 할 수 있고, FALSE이면 증명자는 w값을 속였다고 판단할 수 있다.<ref name="Jungwoo Pyo"></ref> | ||
