영지식 스나크 편집하기

'''영지식 스나크'''(zk-SNARKs)는 '''zero-knowledge Succinct Non-interactive Argument of Knowledge'''의 약자로, 기존의  [[영지식 증명]]을 좀 더 간결하고(Succinct) 비 간섭적인 환경(Non-interactive)에서 적용 가능하도록 변형한 형태이다.

==개요==
영지식 스나크는  그 특성들로 인하여 [[블록체인]] 환경에서 영지식 증명을 구현할 수 있게 되었다. 영지식 스나크를 활용한 블록체인 [[트랜잭션]]의 경우 수신자, 송신자, 전송금액 등의 정보를 노출하지 않고도 해당 트랜잭션의 유효성을 송수신 [[노드]] 외의 다른 노드들에게 알릴 수 있다.<ref>공수래공수거, 〈[https://blog.naver.com/qlmto631/221438158473 제트캐시(Zcash) : 익명성을 보장하는 다크코인]〉, 《네이버 블로그》, 2019-01-09</ref> 영지식 스나크를 최초로 적용한 [[암호화폐]]는 [[지캐시]]가 있으며, 이외에 [[이더리움]]의 비잔틴 [[하드포크]]에도 관련 내용이 적용되었다.<ref>Seonghwa Yun, 〈[https://medium.com/ai-networkkr/%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8%EC%97%90%EC%84%9C%EC%9D%98-%EA%B0%9C%EC%9D%B8%EC%A0%95%EB%B3%B4%EB%B3%B4%ED%98%B8-%EA%B8%B0%EC%88%A0-zk-snark-1-de5804e9b50e 블록체인에서의 개인정보보호 기술, zk-SNARK (1)]〉, 《미디엄》, 2018-10-08</ref>

SNARK라는 약어 내에서 간결한(Succinct)은 증명의 크기가 작고 신속하게 확인할 수 있음을 나타낸다. 비 상호작용(Non-interactive)은 증명자와 검증자 사이의 상호작용이 거의 없거나 전혀 없다는 것을 뜻한다. 영지식 스나크가 개발되기 이전의 영지식 증명은 일반적으로 증명자와 검증자가 서로 통신을 주고받는 것을 요구하므로 간접적 영지식 프로토콜으로 간주된다. 반면에 비 상호작용 구조에서는 증명자와 검증자가 하나의 증거만 주고받아도 된다. 영지식 스나크는 증명자와 검증자 사이의 신뢰할 수 있는 초기 설정에 의존한다. 즉 영지식 증명 및 개인거래를 구축하기 위하여 일련의 고객 매개 변수가 필요한 것이다. 이 매개 변수는 게임의 규칙과 거의 상응하며 프로토콜에 인코딩되어 트랜잭션이 유효하다는 것을 증명하기 위해 필요한 요소이다. 그러나 매개 변수가 매우 작은 그룹에 의하여 공식화 되는 경우가 있기 때문에 잠재적으로 중앙 집중화 문제가 존재한다.<ref name="바이낸스">〈[https://www.binance.vision/ko/blockchain/zk-snarks-and-zk-starks-explained zk-SNARKs 와 zk-STARKs 설명]〉, 《바이낸스 아카데미》, 2019-02-26</ref>

초기 공개 설정은 지금의 영지식 스나크가 구현되기 위한 밑바탕이지만 개발자들은 프로세스에 필요한 신뢰과정을 최소화하기 위한 다른 대안을 찾기 위해 많은 노력을 기울이고 있다. 초기 설정 단계는 위조 지출을 막기 위해 매우 중요하다. 악의를 품은 누군가가 매개 변수를 생성하는 무작위성에 접근하여 검증자에게 유효할 것이라 판단되는 거짓 증명을 만들 수 있기 때문이다. 지캐시에서 초기 설정 단계는 매개 변수 생성 의식으로 알려져 있다.</ref><ref>coinsight, 〈[https://steemit.com/kr/@coinsight/zcash (코인리포트) 익명성 화폐의 선두주자, Zcash(지캐시, 제트캐시)]〉, 《스팀잇》</ref> SNARK의 논쟁(Argument)에 대해 설명해보자면, 영지식 스나크는 계산적으로 확실한 것으로 간주된다. 따라서 증명자의 컴퓨팅 능력이 제한적이라고 가정했을 때, 정직하지 않은 증명자는 시스템을 속일 확률이 매우 낮다. 이러한 속성은 건전성으로 알려져 있지만, 이론적으로는 충분한 컴퓨팅 능력을 가지고 있는 증명자는 가짜 증명을 만들 수 있다. 이것이 많은 사람들이 양자 컴퓨터를 영지식 스나크 및 블록체인 시스템에 대한 위협 중 하나로 간주하는 이유이다. 약어의 마지막 부분인 K는 지식(Knowledge)이다. 이는 증명자가 실제로 자신의 진술을 뒷받침할 수 있는 지식이 없는 증거는 만들 수 없다는 것을 의미한다. 영지식 증명은 매우 신속한 검증이 가능하며 [[비트코인]] 트랜잭션보다 더 적은 [[데이터]]를 차지한다. 이것이 영지식 스나크 기술이 프라이버시 및 [[확장성]]에 대한 솔루션으로 사용되는 이유 중 하나이다.<ref name="바이낸스"></ref>

==특징==
* '''확장성'''
: 영지식 스나크를 이용하여 블록체인의 확장성을 해결하고자 하는 움직임이 많이 늘어나고 있다. 실제로 블록체인 참여자가 [[블록]]의 내용을 알지 못하더라도 전체 노드 중 증명 및 보고의 역할을 수행하는 노드가 블록의 내용이 위변조 되지 않았음을 빠르게 검증할 수 있다. 이는 참여자들의 [[블록 싱크]](block sync) 속도를 급격하게 높여주어 새로운 참여자들이 빠르게 네트워크에 참여할 수 있게 해준다.

: 블록체인의 추가 전용(append-only)의 속성으로 블록체인의 용량은 시간이 지날수록 계속해서 커진다. 특히 이더리움에서는 trie 형태의 여러 글로벌 자료 구조(Global Data Structure : state trie, transaction trie, receipt trie 등)가 쌓여가고 있다는 문제점이 있다. 이 trie 구조에는 각종 [[스마트 계약]] 코드와 저장소 등 수많은 데이터들이 자리를 차지하고 있는데, 영지식 스나크를 통해 실제 데이터를 가지치기(pruning)하고 오직 데이터에 대한 증명만 남기는 방식으로 데이터를 압축시켜 계약이 차지하는 공간을 절약할 수 있다. 스마트 계약의 코드와 저장소를 체인 위에 공개하지 않고도 state change를 증명하는 것이 가능하기 때문이다.<ref name="Jungwoo Pyo">Jungwoo Pyo, 〈[https://medium.com/decipher-media/zero-knowledge-proof-chapter-1-introduction-to-zero-knowledge-proof-zk-snarks-6475f5e9b17b Zero-Knowledge proof :: chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs]〉, 《미디엄》, 2018-07-26</ref>

* '''타원곡선 암호화'''
: 영지식 스나크는 주어진 문제를 변형하고 간결함을 더했지만 아직 정보를 숨기는 것, 즉 Zero-Knowledge를 구현해내지 못했다. 이를 위해 영지식 스나크는 Elliptic Curve, [[타원곡선암호]] 알고리즘을 이용했다. 이는 큰 의미에서 ‘일반적인 계산을 타원 곡선 세계 위로 가져온다’라고 할 수 있다. 타원곡선의 세상에는 정보는 숨기고 등식만 증명하는 것이 가능하기 때문이다. 즉, 증명하고자 하는 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) 등식을 타원 곡선 위에서 증명하는 것이다.<ref name="Jungwoo Pyo"></ref>

==과정==
기존의 비 상호작용 구조에서는 증명자가 항상 [[온라인]] 상태일 필요가 없다는 장점이 있지만 증명을 완료하는데 까지 상당한 시간이 걸린다는 치명적인 약점이 있다. [[암호학]]에서 사용되는 숫자의 크기는 상상할 수 없을 만큼 크기 때문에, 보기에 매우 간단한 연산도 상당히 많은 횟수의 명령(instruction)을 수행한 후에야 결과를 도출할 수 있다.

간결함은 영지식 스나크의 핵심 키워드이다. 상호작용 증명 시스템(interactive proof system)은 검증자가 한정된 계산 자원을 가지고 있음을 전제로 한다. 증명자가 특정한 지식을 알고 있다는 증거로 제출한 증명이 상당히 많은 양의 데이터를 포함하고 있다면, 이 증명은 굉장히 비효율적이다. 따라서 영지식 스나크에서는 비 상호작용 영지식 증명의 크기를 줄이고 빠른 시간 내에 검증을 수행할 수 있도록 하여 비 상호작용 영지식 증명의 실용성을 극대화하였다. 영지식 스나크는 다음과 같은 세 과정으로 이루어지며 이를 통해서 검증자는 증명자의 지식를 직접 확인하지 않고도 빠른 시간 내에 이를 검증 할 수 있게 된다.<ref name="Jungwoo Pyo"></ref>

* '''Keygen : key generator G를 이용해 key pair (pk, vk)를 생성하는 과정'''
: 증명자가 알고 있다고 주장하는 값인 witness(w)가 있다. 이때 이를 매개변수로 받는 특정 프로그램 C가 있다고 하자. 프로그램 C는 다음과 같다고 가정한다.

 function C(x, w) {
 return ( hash(w) == x) ;
 }

: 이와 같이 내가 w를 알고 있음을 증명할 수 있는 프로그램 C와 무작위표본추출 시드(random sampling seed)인 람다(lambda)를 제네레이터에 매개변수로 집어넣음으로써 키 쌍를 생성할 수 있다. 여기서 람다는 증명자 및 외부에 노출되어서는 안 된다. 왜냐하면 이 값을 알고 있는 증명자가 거짓 증명를 생성할 수 있기 때문이다. 그렇기 때문에 키 생성은 검증자가 수행하게 된다.

: * G(C, lambda) = (pk, vk)
: * pk = proving key
: * vk = verifying key

: C의 program size bound를 1, input(x) size의 bound를 n, execution time bound를 T라고 할 때, 키 생성의 시간 복잡도는 아래와 같다. 즉, 프로그램이 길고, 투입 사이즈가 크고, 실행 시간이 길수록 키 생성에 소요되는 시간이 길다.<ref name="Jungwoo Pyo"></ref>

 O (1 + n + T) · log(1 + n + T)

* '''Prove : prover가 proof(prf)를 생성하는 과정'''
: 증명 알고리즘을 P, 증명하고자 하는 증인인 w, w의 해시를 x라고 할 때, 증명을 구하는 방법은 다음과 같다. 증명자는 prf를 계산한 후, 검증자에게 prf만을 전달한다. prf을 계산하는 데 걸리는 시간은 입력값 x와 w의 크기에 비례하여 길어진다. prf가 계산된 이후에는 당연히 prf로부터 w값을 유추할 수 없으며, prf의 길이는 매우 짧다. 이는 기존의 영지식 증명이 가지고 있지 않은 간결함의 특성을 갖게 해주는 요소이다.<ref name="Jungwoo Pyo"></ref>

 prf = P(pk, w, x)

* '''Verify : verifier가 prf를 verifying하는 과정'''

: 검증자는 증명자로부터 prf를 전달받은 후, 검증 알고리즘 V(verifying algorithm V)를 수행하여 prf의 진위 여부를 판단한다. 검증에 걸리는 시간은 매우 짧은데, 이 역시 영지식 스나크가 간결함의 특성을 가지는 요소 중 하나이다. 아래 값이 TRUE이면 증명자는 w값을 정말 알고 있다고 할 수 있고, FALSE이면 증명자는 w값을 속였다고 판단할 수 있다.<ref name="Jungwoo Pyo"></ref>

 boolean : v(vk, x, prf)

==활용==
===지캐시===
[[지캐시]](Zcash)는 영지식 스나크를 개발하였으며, 영지식 스나크를 기반으로 작동하고 있는 [[애플리케이션]] 중 가장 큰 규모이다. 지캐시는 영지식 증명을 바탕으로 완전한 [[익명성]]이 보장된 트랜잭션의 전송을 가능하게 한다. 기본적인 작동방식은 비트코인과 상당히 유사하나, 지캐시는 두 가지 종류의 [[주소]]를 가지고 있다는 것이 비트코인과 지캐시의 차이이다.

사용자들은 Shielded address와 Transparent address의 두 주소를 사용하여 지캐시의 화폐인 [[ZEC]] 거래를 공개적으로 할지, 사적으로 할지 선택하게 된다. Shielded address에서 Transparent address로 송금을 하면 거래된 ZEC는 공개가 되며 반대의 경우는 숨겨진다. 지캐시는 두 주소 체계의 공존을 통해 자금의 흐름을 추적하는 것을 거의 불가능하게 만들었다. 이는 지캐시가 [[익명]] [[코인]]이라고 불리는 대표적인 이유 중 하나이다.<ref name="Jungwoo Pyo"></ref> {{자세히|지캐시}}

===이더리움===
[[이더리움]](Ethereum)의 [[플라즈마]] [[사이드체인]]과 관련된 연구 중에서도 영지식 스나크를 활용한 사례가 등장하고 있다.<ref>강민승 기자, 〈[https://news.naver.com/main/read.nhn?mode=LS2D&mid=shm&sid1=101&sid2=261&oid=009&aid=0004318771 “영지식증명, 플라즈마와 ‘꿀케미’”]〉, 《매일경제》, 2019-03-12</ref> 그동안 일반 상태 플라즈마 체인의 가장 큰 문제점은 사이드체인의 정합성을 [[온체인]]에서 간결하게 증명하는 데 큰 어려움이 따른다는 것이었다. 영지식 스나크는 이를 해결하기 위한 힌트를 제공해준 셈이다. [[비탈릭 부테린]]이 제안한 이더리움의 온체인 스케일링 솔루션 중 하나인 [[롤업]](roll up) 또한 영지식 스나크를 활용하여 이론적으로 하드포크 없이 이더리움의 [[TPS]]를 10~30배까지 확장하는 기술이다. 그는 영지식 스나크를 통해 [[네트워크]]가 개별보다 무리로 더 많은 트랜잭션을 처리하여 속도를 증가시킬 수 있게 하여 가까운 미래에 이더리움이 500TPS를 발생할 수 있을 것이라 예측했다.<ref>욜로욜로, 〈[https://blog.naver.com/denpojan/221395700233 이더리움, 확장성 솔루션인 플라즈마의 대안으로 영지식 증명(zk-SNARKs) 검토]〉, 《네이버 블로그》, 2018-11-10</ref>

또한 영지식 스나크를 이용하여 이더리움에서 [[ETH]]를 송금하는 트랜잭션을 발생시킬 때, 샌더(sender)와 리시버(receiver)에게 트랜잭션을 보낸 사실만을 공개하고, 그들의 잔고(balance)와 송금액(transfer amount)에 대한 상세 내용을 숨기는 전송 방식이 가능하다.<ref name="Jungwoo Pyo"></ref> {{자세히|이더리움}}

===코다===
[[코다]](Corda)는 영지식 스나크를 블록체인의 확장성에 활용한 예시이다. 코다 프로토콜은 영지식 스나크를 기반으로 한 레이어2의 확장과 개인 정보 보호의 도입을 알린 바 있다.<ref>김용영 기자, 〈[https://news.naver.com/main/read.nhn?mode=LSD&mid=sec&sid1=101&oid=009&aid=0004237835 샌프란시스코 블록체인 위크 2018에서 부상한 4가지 트렌드]〉, 《매일경제》, 2018-10-19</ref> 영지식 스나크에서 검증자는 간결한 증명만으로 원본을 검증할 수 있게 되어 원본을 직접 검증할 필요가 없다. 코다는 일반적인 블록체인과는 달리 [[채굴자]]들이 트랜잭션의 원본 데이터 대신 자신들이 올바른 블록을 생성했다는 증명만을 블록에 담아 확장성 문제를 해결하고자 한다.<ref>Jihyeok Choy, 〈[https://medium.com/decipher-media/zero-knowledge-proof-chapter-2-deep-dive-into-zk-snarks-f8b16e1b7b4c Zero-Knowledge proof :: chapter 2. Deep Dive into zk-SNARKs]〉, 《미디엄》, 2019-03-18</ref> {{자세히|코다}}

{{각주}}

==참고자료==
* Jungwoo Pyo, 〈[https://medium.com/decipher-media/zero-knowledge-proof-chapter-1-introduction-to-zero-knowledge-proof-zk-snarks-6475f5e9b17b Zero-Knowledge proof :: chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs]〉, 《미디엄》, 2018-07-26
* Seonghwa Yun, 〈[https://medium.com/ai-networkkr/%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8%EC%97%90%EC%84%9C%EC%9D%98-%EA%B0%9C%EC%9D%B8%EC%A0%95%EB%B3%B4%EB%B3%B4%ED%98%B8-%EA%B8%B0%EC%88%A0-zk-snark-1-de5804e9b50e 블록체인에서의 개인정보보호 기술, zk-SNARK (1)]〉, 《미디엄》, 2018-10-08
* 〈[https://www.binance.vision/ko/blockchain/zk-snarks-and-zk-starks-explained zk-SNARKs 와 zk-STARKs 설명]〉, 《바이낸스 아카데미》, 2019-02-26
* Jihyeok Choy, 〈[https://medium.com/decipher-media/zero-knowledge-proof-chapter-2-deep-dive-into-zk-snarks-f8b16e1b7b4c Zero-Knowledge proof :: chapter 2. Deep Dive into zk-SNARKs]〉, 《미디엄》, 2019-03-18

==같이 보기==
* [[영지식 증명]]
* [[지캐시]]
* [[이더리움]]
* [[코다]]

{{블록체인 기술|검토 필요}}