영지식 증명: 두 판 사이의 차이

IT위키
편집 요약 없음
편집 요약 없음
 
(사용자 2명의 중간 판 3개는 보이지 않습니다)
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" |없음
|}

2021년 5월 9일 (일) 21:17 기준 최신판


ZKP; Zero-Knowledge Proof
prover가 자신이 알고 있는 지식을 공개하지 않으면서, 그 지식을 알고 있다는 사실을 verifier에게 증명하는 proof system
  • 1980년대 MIT의 Shafi Goldwasser, Silvio Micali and Charles Rackoff가 처음 제시

조건[편집 | 원본 편집]

  • 완전성(completeness)
    • 어떤 조건이 참이라면 신뢰할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다.
  • 건전성(soundness)
    • 어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에게 조건이 참임을 절대 납득시킬 수 없다.
  • 영지식성(zero-knowledge)
    • 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다.

활용[편집 | 원본 편집]

활용 예 설명
Z-cash 블록체인상의 거래내역 추적을 막는 익명성 부과
Zk roll up Layer2의 상태를 Layer1에서 검증할 수 있도록 증명
Zokrates Off-chain에서 생성한 증명을 검증 가능한 스마트 컨트랙트 생성
zkvm 컨트랙트 실행 환경 VM의 상태 증명
Oracle 오프체인의 개인 데이터를 온체인에서 검증 가능하도록 구현
Interoperability Chain간 블록 및 상태 전이에 관한 증명 및 검증
Selective Disclosure DID의 Claim을 Verifier에게 선택적으로 증명

분류[편집 | 원본 편집]

분류 기술
Interactive
  • Graph Isomorphism
  • zk-stick(2018)
Non-Interactive TTP 사용
TTP 미사용
  • Ligero(2017)
  • zk-STARKs(2018)
  • Bulletproof(2018)
  • Supersonic(2019)

Interactive ZKP[편집 | 원본 편집]

Non-interactive ZKP[편집 | 원본 편집]

Prover와 Verifier가 온라인 상태가 아니더라도 영지식 증명 가능

TTP 사용[편집 | 원본 편집]

  • zk-SNARKs : Non-interactive ZKP의 proof size를 줄인 실용 모델
    • 지캐시에서 도입

TTP 미사용[편집 | 원본 편집]

  • zk-STARKs
  • BulletProofs

비교[편집 | 원본 편집]

구분 zk-SNARKs zk-STARKs 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 필요 필요 없음 필요 없음
양자 내성 없음 있음 없음
원본 주소 "https://itwiki.kr/index.php?title=영지식_증명&oldid=26500"