최신판 |
당신의 편집 |
1번째 줄: |
1번째 줄: |
| [[분류:보안]] | | [[분류:보안]] |
|
| |
| ;ZKP; Zero-Knowledge Proof | | ;ZKP; Zero-Knowledge Proof |
| ;prover가 자신이 알고 있는 지식을 공개하지 않으면서, 그 지식을 알고 있다는 사실을 verifier에게 증명하는 proof system | | ;prover가 자신이 알고 있는 지식을 공개하지 않으면서, 그 지식을 알고 있다는 사실을 verifier에게 증명하는 proof system |
|
| |
|
| *1980년대 MIT의 Shafi Goldwasser, Silvio Micali and Charles Rackoff가 처음 제시 | | * 1980년대 MIT의 Shafi Goldwasser, Silvio Micali and Charles Rackoff가 처음 제시 |
| | |
| ==조건==
| |
| | |
| *'''완전성(completeness)'''
| |
| **어떤 조건이 참이라면 신뢰할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다.
| |
| *'''건전성(soundness)'''
| |
| **어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에게 조건이 참임을 절대 납득시킬 수 없다.
| |
| *'''영지식성(zero-knowledge)'''
| |
| **어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다.
| |
| | |
| ==활용==
| |
| {| class="wikitable"
| |
| !활용 예
| |
| !설명
| |
| |-
| |
| |Z-cash
| |
| |블록체인상의 거래내역 추적을 막는 익명성 부과
| |
| |-
| |
| |Zk roll up
| |
| |Layer2의 상태를 Layer1에서 검증할 수 있도록 증명
| |
| |-
| |
| |Zokrates
| |
| |Off-chain에서 생성한 증명을 검증 가능한 스마트 컨트랙트 생성
| |
| |-
| |
| |zkvm
| |
| |컨트랙트 실행 환경 VM의 상태 증명
| |
| |-
| |
| |Oracle
| |
| |오프체인의 개인 데이터를 온체인에서 검증 가능하도록 구현
| |
| |-
| |
| |Interoperability
| |
| |Chain간 블록 및 상태 전이에 관한 증명 및 검증
| |
| |-
| |
| |Selective Disclosure
| |
| |DID의 Claim을 Verifier에게 선택적으로 증명
| |
| |}
| |
| | |
| ==분류==
| |
| {| class="wikitable"
| |
| ! colspan="2" |분류
| |
| !기술
| |
| |-
| |
| | colspan="2" |Interactive
| |
| |
| |
| *Graph Isomorphism
| |
| *zk-stick(2018)
| |
| |-
| |
| | rowspan="2" |Non-Interactive
| |
| |TTP 사용
| |
| |
| |
| *[[Zk-SNARKs|zk-SNARKs(2013)]]
| |
| *Libra(2019)
| |
| |-
| |
| |TTP 미사용
| |
| |
| |
| *Ligero(2017)
| |
| *zk-STARKs(2018)
| |
| *Bulletproof(2018)
| |
| *Supersonic(2019)
| |
| |}
| |
| | |
| ===Interactive ZKP===
| |
|
| |
|
| ===Non-interactive ZKP=== | | == 조건 == |
| | * '''완전성(completeness)''' |
| | ** 어떤 조건이 참이라면 신뢰할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다. |
| | * '''건전성(soundness)''' |
| | ** 어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에게 조건이 참임을 절대 납득시킬 수 없다. |
| | * '''영지식성(zero-knowledge)''' |
| | ** 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다. |
|
| |
|
| | == Non-interactive ZKP == |
| ;Prover와 Verifier가 온라인 상태가 아니더라도 영지식 증명 가능 | | ;Prover와 Verifier가 온라인 상태가 아니더라도 영지식 증명 가능 |
|
| |
|
| ====TTP 사용==== | | == 사례 == |
| | | * 지캐시 |
| *[[zk-SNARKs]] : Non-interactive ZKP의 proof size를 줄인 실용 모델
| |
| **지캐시에서 도입
| |
| | |
| ====TTP 미사용====
| |
| | |
| * zk-STARKs
| |
| * BulletProofs
| |
| | |
| == 비교 ==
| |
| {| class="wikitable"
| |
| !구분
| |
| ! colspan="2" |[[zk-SNARKs]]
| |
| ! colspan="2" |zk-STARKs
| |
| ! colspan="2" |BulletProofs
| |
| |-
| |
| !증명자 연산 복잡도
| |
| |O(N * log(N))
| |
| |2.3s
| |
| |O(N * poly-log(N))
| |
| |~1.6s
| |
| |O(N * log(N))
| |
| |~30s
| |
| |-
| |
| !검증자 연산 복잡도
| |
| |~O(1)
| |
| |10ms
| |
| |O(poly-log(N))
| |
| |~16ms
| |
| |O(N)
| |
| |~1100ms
| |
| |-
| |
| !증명 크기
| |
| |~O(1)
| |
| |~200Byte
| |
| |O(poly-log(N))
| |
| |45~200KB
| |
| |O(log(N))
| |
| |~1.3KB
| |
| |-
| |
| !TTP
| |
| | colspan="2" |필요
| |
| | colspan="2" |필요 없음
| |
| | colspan="2" |필요 없음
| |
| |-
| |
| !양자 내성
| |
| | colspan="2" |없음
| |
| | colspan="2" |있음
| |
| | colspan="2" |없음
| |
| |}
| |