Recursive proofs and proof aggregation TODO
Concept
A recursive proof proves the very fact that some other proof passed verification, by expressing the proof-verification algorithm as a circuit and then proving the execution of that circuit. This lets you fold an arbitrarily long computation, or the state transitions across many blocks, into a single small proof, so verification cost becomes independent of the length of the original computation. Proof aggregation bundles multiple independent proofs to cut verification cost overall; it's sometimes implemented via recursion, and sometimes via cheaper techniques like batch verification or linear combinations of commitments. The key practical constraint is how cheaply that proof system's verifier can be expressed inside a circuit, which is why curve choice and proof-friendly hash function choice matter so much. The essence of the technique is an asymmetry of cost: the prover gets heavier while the verifier becomes extremely light.
This structure is exactly why a rollup can settle enormous numbers of transactions with a single verification on L1, and why a light client can catch up on a long history at low cost.
Code & Formula
# 재귀 증명과 증명 집계 — 여러 스텝의 증명을 접어 "이전까지 전부 유효했음"을
# 상수 크기 하나로 압축하는 폴딩(재귀 검증)을 해시 체인으로 단순화해 시연.
# (실제 SNARK 재귀와 달리 여기선 검증도 재실행하지만, 접힘/집계의 구조만 보여주는 예시)
import hashlib
def h(*parts: bytes) -> bytes:
m = hashlib.sha256()
for p in parts:
m.update(p)
return m.digest()
def step_proof(prev_proof: bytes, statement: bytes) -> bytes:
# "이 스텝이 유효하다"는 증명을 이전 증명과 접어(fold) 하나의 값으로 만든다
return h(prev_proof, statement)
def verify_chain(genesis: bytes, statements: list, final_proof: bytes) -> bool:
# 재귀 증명이라면 검증자는 final_proof 하나만 확인하면 되지만,
# 여기서는 폴딩 구조 설명을 위해 재실행으로 대신 확인한다.
acc = genesis
for s in statements:
acc = step_proof(acc, s)
return acc == final_proof
genesis = h(b"genesis")
statements = [f"tx-{i}".encode() for i in range(5)]
# 증명자: 각 스텝을 순서대로 접어 하나의 집계 증명(final_proof)을 만든다
acc = genesis
individual_sizes = 0
for s in statements:
acc = step_proof(acc, s)
individual_sizes += len(acc)
final_proof = acc
print("스텝 수:", len(statements))
print("집계 전 개별 증명 총 크기(byte):", individual_sizes)
print("집계된 최종 증명 크기(byte):", len(final_proof), "← 스텝 수와 무관하게 일정")
print("최종 증명 검증 결과:", verify_chain(genesis, statements, final_proof))
tampered = statements.copy()
tampered[2] = b"tx-2-tampered"
print("중간 statement 조작 시 검증 실패:", not verify_chain(genesis, tampered, final_proof))
docs/code/algorithms/algorithms-93.py
Exercise
Pick one ZK framework, generate a proof for a tiny circuit, then write a circuit that verifies that proof to run one round of recursion — measure how proof size and proving time each change.
Practical Connection
When Verex runs on an L2 or trusts an L2's settlement, the user's basis for trusting finality ultimately comes down to this one act of proof verification, and the proof-generation cycle directly shows up as withdrawal/settlement latency.
Where it lands in Jayverse
- Verex: surface withdrawal/settlement latency as "waiting on proof generation," not a generic pending state. On any future L2, that latency is bounded by proof-generation time, not block time — this is also the fourth clock from pocs-l2-finality-three-clocks, so wire the UI to that clock explicitly.
- Devnet: track prover cost as an infra line item once Devnet moves off Anvil to an OP-Stack L2. Whatever proof system that L2 uses, Jayverse inherits its recursion/aggregation cost — budget for it rather than discovering it in withdrawal latency later.
- Auditor: record which proof system and circuit each settlement path relies on. Since verification cost is exactly what the Auditor's methodology should state, write down curve/hash choices per path before a consumer asks why a withdrawal took as long as it did.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| fold ... into | ~을 ~로 접어 넣다, 압축해 담다 · 긴 연산 과정을 작은 하나의 증명으로 압축할 때. "lets you fold an arbitrarily long computation" |
| independent of | ~와 무관한, ~에 좌우되지 않는 · 검증 비용이 원본 연산의 길이와 상관없이 일정할 때. "verification cost becomes independent of the length" |
| cut (verification) cost | (검증) 비용을 줄이다 · 여러 증명을 묶어서 전체 검증 부담을 낮출 때. "bundles multiple independent proofs to cut verification cost" |
| asymmetry of cost | 비용의 비대칭 · 한쪽(증명자)은 무거워지고 다른 쪽(검증자)은 가벼워지는 구조. "The essence of the technique is an asymmetry of cost" |
| catch up on | (밀린 것을) 따라잡다 · 오래된 이력을 처음부터 다 안 봐도 빠르게 따라잡을 때. "a light client can catch up on a long history" |
| show up as | ~로 나타나다, ~의 형태로 드러나다 · 기술적 요인이 실제 사용자 경험의 지연으로 나타날 때. "directly shows up as withdrawal/settlement latency" |
| come down to | 결국 ~에 달려 있다 · 신뢰의 근거가 결국 한 가지 행위로 좁혀질 때. "ultimately comes down to this one act of proof verification" |
| ZK | 영지식(Zero-Knowledge) · 원본 정보를 공개하지 않고 계산이 올바름을 증명하는 암호 기법, 재귀 증명·증명 집계가 다루는 대상 시스템. "Pick one ZK framework, generate a proof for a tiny circuit" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-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/.