영 지식 증명의 쉬운 예와, zk-s{nt}ark

비대칭 키 시스템에서는 지식은 증명가능하나 프라이버시가 노출됨
① 정우성이 자신의 공개키를 공개하고 '나는 정우성이다' 라는 메세지를 개인키로 잠궈서 인터넷상에 뿌렸을 때 정우성의 공개키로 열린다면 그 메세지는 정우성이 작성한 것이 증명됨
② 프라이버시가 공개(정우성의 공개키)

===A. zero knowledge proof ===
영지식증명: 어떤 statement가 참이라는 것을 증명할 때 거짓 여부를 제외한 어떤 것도 노출되지 않는 interactive verification, 상대에 대해 어떤 것도 알 수 없지만 상대가 가진 정보를 신뢰할 수 있음
① 검증자는 정우성이 있을거라 생각되는 동굴에 정우성 팬을 보냄 잠시후 동굴에서 정우성 팬이 활짝 웃으며 나온다면 일단 확률이 높으므로 다시 한명 더 보냅니다.
② 또 보내고 이런식으로 10명을 보냈는데 모두가 활짝 웃으며 나온다면 정우성이 맞음
③ 즉, 상대방이 가지고 있는 정보가 진짜인지 해당 정보로 증명가능성이 높은 것을 여러번 보내서 한번도 틀리지 않는 반응이 나오면 상대가 진짜 정보를 가졌다고 확률상 확신

===B. zk SNARK (Succinct Non-interactive ARgument of Knowledge)===
http://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
① Succinct(간결한): 실제 연산의 길이에 비해 메시지들의 크기가 작다
② Non-interactive(상호작용이 없는): 상호작용이 아예 없거나, 아주 작음. zk SNARKs는 setup단계를 가지며, 그 후 단일메시지가 증명자로부터 검증자에게 전달된다. SNARKs는 누구든 상호작용없이 검증이 가능한 공통 검증자 속성을 가짐.
③ Arguments(논증): 검증자는 연산능력이 제한된 증명자에 대해서만 보호되어진다 (50%)
④ of Knowledge(지식): 증명자는 증명/논증을 증인을 모르는 상태에서 생성하는 것은 불가능하다. (증인: 소비를 원하는 주소의 해시 함수의 입력이나 특정 머클트리 노드에 대한 주소)

Limitation: 신뢰가능한 제3자의 도움으로 프로그램별 키를 생성해야한다.
① Non-interactive를 위해 신뢰된 한번의 공통파라미터 셋업이 필요함
② 키 생성자는 증명을 생성하는데 사용할 증명키와 증명을 체크할 검증키를 샘플링한다.
③ 현재 구현은 hard-coded in the keys.

===C. zk STARK(Scalable Transparent ARgument of Knowledge)===
https://eprint.iacr.org/2018/046.pdf (eli ben sasson)
http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf

Preserve privacy: zero knowledge
Universal: can apply any computation
Scalable: poof generation and verification(computation time with network scale)
Transparent: public randomness, no trust setup

=>영지식증명: 프라이버시를 보호하기 위해 증명 오버헤드가 발생
=>SNARK: setup과정을 통해 서로간 통신을 단 한번으로 줄임
=>STARK: setup을 아예없에고 확장성을 보강

여러분의 up vote 가 큰 도움이 됩니다.
후원: 0x62467Ca1b449c854c4720395Dd9a7c6Ed5df47B7(ethereum)