The Three Properties of Zero-Knowledge Proofs (Completeness, Soundness, Zero-Knowledge) TODO
Concept
An interactive proof system is a procedure by which a prover convinces a verifier that some statement is true, and a zero-knowledge proof requires three properties on top of that. Completeness means that if the statement is true and both parties honestly follow the protocol, the verifier accepts with overwhelming probability. Soundness means that if the statement is false, no prover can convince the verifier except with negligible probability; when this guarantee holds against every prover it's called a proof, and when it holds only against provers with bounded computational power it's called an argument. The zero-knowledge property means the verifier learns nothing beyond the fact that the statement is true, formalized as the existence of a simulator — one that doesn't know the witness — able to produce something indistinguishable from a real transcript. Depending on the strength of that indistinguishability, zero-knowledge is classified as perfect, statistical, or computational, and applications often require knowledge soundness — a guarantee that the prover actually knows the witness — rather than plain soundness.
In practice, what breaks is usually not the three properties themselves but the assumptions they rest on — the integrity of a trusted setup, or the assumptions made when converting an interactive protocol into a non-interactive one.
Code & Formula
# 영지식 증명의 3성질(완전성·건전성·영지식) — 그래프 3색칠 문제의 대화형 ZK 프로토콜을
# 여러 라운드 시뮬레이션해, "거짓 증명이 계속 통과할 확률이 지수적으로 줄어드는 것"을 본다.
import random
# 삼각형 하나(간선 3개) — 진짜 3색칠 가능한 그래프
edges = [(0, 1), (1, 2), (2, 0)]
coloring = {0: "R", 1: "G", 2: "B"} # 증명자만 아는 비밀
def prover_commit(coloring, perm):
# 색을 무작위로 재배치(퍼뮤테이션)해서 커밋 — 매 라운드 다른 색 배정처럼 보이게.
return {v: perm[c] for v, c in coloring.items()}
def round_trip(coloring, edges, cheat=False):
perm = {"R": "G", "G": "B", "B": "R"} # 색 재배치(진짜 증명자는 이런 순열을 매번 새로 고름)
committed = prover_commit(coloring, perm) if not cheat else {0: "R", 1: "R", 2: "B"} # 부정직: 두 정점 같은 색
u, v = random.choice(edges) # 검증자가 무작위로 간선 하나 선택
return committed[u] != committed[v] # 그 간선의 두 끝점 색이 다른지만 공개
N = 20
honest_ok = sum(round_trip(coloring, edges) for _ in range(N))
cheat_ok = sum(round_trip(coloring, edges, cheat=True) for _ in range(N))
print(f"정직한 증명자: {honest_ok}/{N} 라운드 통과 (완전성 — 항상 통과해야 함)")
print(f"부정직한 증명자: {cheat_ok}/{N} 라운드 통과 (매 라운드 들킬 확률 >= 1/|E| — 반복할수록 사기 확률이 지수적으로 감소)")
print("영지식성: 검증자는 매 라운드 '두 끝점 색이 다르다'만 보고, 실제 색은 절대 못 봄")
Exercise
Pick a classic sigma protocol, such as graph three-coloring or proof of knowledge of a discrete log, write out completeness, soundness, and the simulator construction by hand, and reproduce the interactive process in simple code.
Practical Connection
When reviewing a rollup's validity proof or a privacy feature, the starting point for accurately assessing its trust assumptions is distinguishing whether the system is a proof or an argument, whether it has knowledge soundness, and what setup assumptions it relies on.
Where it lands in Jayverse
- OFA/Devnet: before trusting any validity-proof rollup or ZK privacy feature, write down proof-vs-argument, knowledge soundness, and setup assumptions. Treating "it's ZK" as a security claim skips exactly the three questions this concept forces — none of them are optional once a real proof system is integrated.
- Auditor: add "is the zero-knowledge simulator computational, statistical, or perfect" to the standing review template. That classification is what marketing language for a ZK feature usually omits, and it's the difference between a claim and a guarantee.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| on top of that | 그에 더해서, 추가로 · 기본 요건 외에 추가 조건이 붙을 때. "requires three properties on top of that" |
| overwhelming probability | 압도적인 확률(거의 확실히) · 거의 100%에 가까운 확률을 수학적으로 표현할 때. "the verifier accepts with overwhelming probability" |
| negligible probability | 무시할 수 있을 정도로 작은 확률 · 사실상 0에 가까운 확률을 말할 때. "except with negligible probability" |
| bounded | (범위가) 제한된, 유한한 · 계산 능력 등에 한계가 있음을 표현할 때. "provers with bounded computational power" |
| indistinguishable from | ~와 구별할 수 없는 · 두 대상이 통계적으로 같아 보일 때. "indistinguishable from a real transcript" |
| rest on | ~에 기반하다/근거를 두다 · 결론이나 안전성이 무엇에 의존하는지 말할 때. "the assumptions they rest on" |
| the witness | 증인, 증명자가 실제로 아는 비밀값 · 영지식 증명에서 증명자가 아는 답을 가리킬 때. "a guarantee that the prover actually knows the witness" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.