[Review] A design checklist for verifiable systems TODO

Algorithms · Day 96 / 100 · F. Cryptography & ZK (Day 82-96)

Concept

A verifiable system is designed so the other party can confirm the correctness of a result for themselves, instead of being asked to just trust it. The core axes are determinism (same input, same output), commitments (pinning state via a Merkle root or hash), the proof method (validity proof, Merkle proof, or fraud proof), and the trust assumptions plus data availability. Verifiability only has real meaning when verification cost is reliably lower than the cost of re-execution. Finally, the design isn't complete until the recovery path on failure is spelled out too — the challenge period, the escalation procedure, and who holds ultimate fallback authority.

Bolting on a proof system doesn't make you safe by itself; unless the trust assumptions and fallback path are pinned down in writing, nobody knows who can do what at the moment an incident actually happens.

Code & Formula

# [복습] 검증 가능한 시스템 체크리스트 — 결정성·커밋먼트·증명 방식·검증 비용을
# 머클 트리로 시연: 잎 하나의 값을 O(log n) 증명으로 검증(전체 재실행 O(n) 불필요).

import hashlib

def H(*parts) -> bytes:
    m = hashlib.sha256()
    for p in parts:
        m.update(p)
    return m.digest()

def build_tree(leaves):
    level = [H(b"leaf", x) for x in leaves]
    tree = [level]
    while len(level) > 1:
        if len(level) % 2:
            level = level + [level[-1]]
        level = [H(b"node", level[i], level[i + 1]) for i in range(0, len(level), 2)]
        tree.append(level)
    return tree  # tree[0]=leaf hashes ... tree[-1]=[root]

def merkle_proof(tree, index):
    proof = []
    for level in tree[:-1]:
        sibling = index ^ 1
        if sibling < len(level):
            proof.append(level[sibling])
        index //= 2
    return proof

def verify_proof(leaf, index, proof, root):
    h = H(b"leaf", leaf)
    for sib in proof:
        h = H(b"node", sib, h) if index % 2 else H(b"node", h, sib)
        index //= 2
    return h == root

leaves = [f"account-{i}:balance={i*10}".encode() for i in range(8)]
tree = build_tree(leaves)
root = tree[-1][0]

idx = 5
proof = merkle_proof(tree, idx)
print("커밋먼트(root):", root.hex()[:16], "...")
print(f"leaf[{idx}] 증명 크기: {len(proof)} 해시  (전체 잎 {len(leaves)}개 재실행 없이 검증)")
print("증명 검증 결과:", verify_proof(leaves[idx], idx, proof, root))

tampered_leaf = b"account-5:balance=9999"
print("변조된 leaf 는 같은 증명으로 거부됨:", not verify_proof(tampered_leaf, idx, proof, root))

# 체크리스트: 결정성(같은 입력->같은 root) / 커밋먼트(root) / 증명방식(머클 증명)
# / 검증 비용(O(log n) < 재실행 O(n)) / 폴백(불일치 시 이의제기 대상은 root 제공자)
print("\n[체크리스트] 결정성 O, 커밋먼트 O, 증명방식=머클, 검증<재실행 O, 폴백 주체=? (명시 필요)")

docs/code/algorithms/algorithms-96.py

Exercise

Pick one system you've built and fill in a one-page table covering trust assumptions, commitments, who verifies, the challenge period, and the final fallback — then find which cells are left blank.

Practical Connection

Verex's result-finalization path (oracle proposal → challenge period → final settlement) is a direct application of this checklist, and the trust assumptions and fallback authority at each step need to be written down explicitly to be able to respond during a dispute.

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/.

한국어

[복습] 검증 가능한 시스템 설계 체크리스트 TODO

Algorithms · Day 96 / 100 · F. 암호학·ZK (Day 82–96)

개념

검증 가능한 시스템은 결과를 믿어달라고 요구하는 대신 상대가 스스로 결과의 정당성을 확인할 수 있게 만드는 것을 설계 목표로 삼는다. 핵심 축은 결정성(같은 입력에 같은 출력), 커밋먼트(머클 루트나 해시로 상태를 고정), 증명 방식(유효성 증명, 머클 증명, 사기 증명 중 무엇인지), 그리고 신뢰 가정과 데이터 가용성이다. 검증 비용이 재실행 비용보다 확실히 작아야 검증 가능성이 실질적 의미를 가진다. 마지막으로 실패했을 때의 회복 경로 — 이의제기 기간, 에스컬레이션 절차, 최종 폴백 권한이 누구에게 있는지 — 까지 명시되어야 설계가 완결된다.

증명 시스템을 붙였다는 사실만으로 안전해지지 않으며, 신뢰 가정과 폴백 경로를 문서로 고정해두지 않으면 실제 사고 순간에 누가 무엇을 할 수 있는지 아무도 모른다.

코드 · 수식

# [복습] 검증 가능한 시스템 체크리스트 — 결정성·커밋먼트·증명 방식·검증 비용을
# 머클 트리로 시연: 잎 하나의 값을 O(log n) 증명으로 검증(전체 재실행 O(n) 불필요).

import hashlib

def H(*parts) -> bytes:
    m = hashlib.sha256()
    for p in parts:
        m.update(p)
    return m.digest()

def build_tree(leaves):
    level = [H(b"leaf", x) for x in leaves]
    tree = [level]
    while len(level) > 1:
        if len(level) % 2:
            level = level + [level[-1]]
        level = [H(b"node", level[i], level[i + 1]) for i in range(0, len(level), 2)]
        tree.append(level)
    return tree  # tree[0]=leaf hashes ... tree[-1]=[root]

def merkle_proof(tree, index):
    proof = []
    for level in tree[:-1]:
        sibling = index ^ 1
        if sibling < len(level):
            proof.append(level[sibling])
        index //= 2
    return proof

def verify_proof(leaf, index, proof, root):
    h = H(b"leaf", leaf)
    for sib in proof:
        h = H(b"node", sib, h) if index % 2 else H(b"node", h, sib)
        index //= 2
    return h == root

leaves = [f"account-{i}:balance={i*10}".encode() for i in range(8)]
tree = build_tree(leaves)
root = tree[-1][0]

idx = 5
proof = merkle_proof(tree, idx)
print("커밋먼트(root):", root.hex()[:16], "...")
print(f"leaf[{idx}] 증명 크기: {len(proof)} 해시  (전체 잎 {len(leaves)}개 재실행 없이 검증)")
print("증명 검증 결과:", verify_proof(leaves[idx], idx, proof, root))

tampered_leaf = b"account-5:balance=9999"
print("변조된 leaf 는 같은 증명으로 거부됨:", not verify_proof(tampered_leaf, idx, proof, root))

# 체크리스트: 결정성(같은 입력->같은 root) / 커밋먼트(root) / 증명방식(머클 증명)
# / 검증 비용(O(log n) < 재실행 O(n)) / 폴백(불일치 시 이의제기 대상은 root 제공자)
print("\n[체크리스트] 결정성 O, 커밋먼트 O, 증명방식=머클, 검증<재실행 O, 폴백 주체=? (명시 필요)")

docs/code/algorithms/algorithms-96.py

연습

자신이 만든 시스템 하나를 골라 신뢰 가정·커밋먼트·검증 주체·이의제기 기간·최종 폴백을 한 장짜리 표로 채우고 빈칸으로 남는 항목을 찾아라.

실무 · Verex 연결

Verex의 결과 확정 경로(오라클 제안 → 이의제기 → 최종 정산)가 이 체크리스트의 직접적인 적용 사례이며, 각 단계의 신뢰 가정과 폴백 권한을 명문화해야 분쟁 상황에서 대응이 가능하다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.