Graph Basics: DAGs, Trees, and Hash Links TODO

Math · Day 5 / 52 · July — Discrete Math & Logic (Day 3-10)

Concept

A graph is a pair of a vertex set and an edge set, and its properties diverge sharply depending on whether edges are directed and whether cycles exist. A DAG has only directed edges and no cycles, so a topological sort is always possible, and that ordering is the basis for dependency resolution and sequential processing. A tree is a connected, acyclic graph; with n vertices it has exactly n-1 edges, and once you pick a root, the path from any vertex to the root is unique. A hash link is an edge that points to the target node's content hash rather than a memory address, so changing a node's content changes its hash, which cascades up through every ancestor node that pointed to it — making the whole structure tamper-evident. Because a structure built from hash links can never point ahead to a hash that doesn't exist yet, it can never contain a cycle by construction and is always a DAG; Merkle trees and blockchains are the special case.

Blockchain structure, Merkle proofs, build dependencies, and transaction dependency graphs are all described in this same language of DAGs and hash links.

Code & Formula

# 그래프 기초(DAG·트리·해시 링크) — 해시 링크로 만든 체인은 원리상 사이클이 생길 수 없어 항상 DAG.
# 노드 하나(payload)를 바꾸면 그 해시가 바뀌고, 상위 노드가 가리키던 해시도 전부 달라진다.

import hashlib

def h(data: bytes) -> str:
    return hashlib.sha256(data).hexdigest()[:12]

class HashNode:
    def __init__(self, payload, prev_hash=""):
        self.payload = payload
        self.prev_hash = prev_hash
        self.hash = h(f"{payload}|{prev_hash}".encode())

def build_chain(payloads):
    chain = []
    prev = ""
    for p in payloads:
        node = HashNode(p, prev)
        chain.append(node)
        prev = node.hash
    return chain

def verify_chain(chain):
    prev = ""
    for node in chain:
        if node.prev_hash != prev:
            return False
        if h(f"{node.payload}|{node.prev_hash}".encode()) != node.hash:
            return False
        prev = node.hash
    return True

chain = build_chain(["genesis", "tx1", "tx2", "tx3"])
print("원본 체인 유효?", verify_chain(chain))
for n in chain:
    print(f"  {n.payload:10} prev={n.prev_hash or '(none)':14} hash={n.hash}")

# tx2 의 내용을 변조하면 → 그 노드의 해시가 바뀌고, tx3.prev_hash 와 불일치 → 검증 실패.
chain[2].payload = "tx2-tampered"
chain[2].hash = h(f"{chain[2].payload}|{chain[2].prev_hash}".encode())
print("\ntx2 변조 후 체인 유효?", verify_chain(chain))

docs/code/math/math-5.py

Exercise

Implement a Merkle tree that reads a directory tree and computes each node's hash from its children's hashes, then verify that changing one byte of a file changes the root, while only the nodes on the changed path need to be recomputed.

Practical Connection

Ethereum's state tree and block linkage are both hash-linked DAGs, and the same principle underlies how Gnosis Conditional Tokens derive condition and position identifiers as hashes of their inputs.

Where it lands in Jayverse

Verex: since it's a ctf-exchange fork, verify condition-ID and position-ID derivation follows the exact hash scheme, and add a test that changing one input (oracle, questionId, outcome count) changes only that ID. A silent collision in the hash-link derivation would corrupt the whole condition tree.
gitboard: model service dependency (token before bridge before wallet, etc.) as an explicit DAG with a topological order. Deploy and migration order should be derived from the graph, not remembered by whoever runs it.
Bridge: use a hash-linked snapshot (a Merkle root of locked balances) as the thing the relayer commits to. Tampering with one locked deposit becomes detectable by a root mismatch alone, without walking the whole ledger.

Key expressions

Words and phrases from this page worth keeping, with the Korean meaning and the sentence they come from.

Expression	뜻 · 쓰이는 자리
diverge sharply	크게 갈라지다/차이 나다 · 조건에 따라 성질이 확연히 달라질 때. "diverge sharply depending on whether edges are directed"
cascade up	(변화가) 위로 연쇄적으로 퍼지다 · 하나의 변경이 상위 노드까지 줄줄이 영향을 줄 때. "cascades up through every ancestor node"
tamper-evident	조작하면 티가 나는(변조 감지 가능한) · 데이터가 변경되면 바로 드러나는 구조를 말할 때. "making the whole structure tamper-evident"
by construction	구조상 원천적으로, 설계 자체에 의해 · 별도 증명 없이 구조만으로 성립하는 성질을 말할 때. "can never contain a cycle by construction"
point ahead to	아직 존재하지 않는 대상을 미리 가리키다 · 해시 링크가 미래 값을 참조할 수 없다는 제약. "can never point ahead to a hash that doesn't exist"
the basis for	~의 토대/근거가 되다 · 어떤 개념이 다른 응용의 기반이 될 때. "the basis for dependency resolution"
connected, acyclic	연결되어 있고 순환이 없는 · 트리의 정의를 이루는 두 성질을 가리킬 때. "A tree is a connected, acyclic graph"
DAG	방향성 비순환 그래프(Directed Acyclic Graph) · 사이클 없는 방향 그래프, 위상정렬이 가능한 구조. "A DAG has only directed edges and no cycles"
Gnosis Conditional Tokens	Gnosis가 만든 조건부 토큰 프레임워크(예측시장용 포지션 토큰 표준) · 조건·포지션 식별자를 해시로 만드는 예로 언급. "Gnosis Conditional Tokens derive condition and position identifiers as hashes"

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

한국어

그래프 기초(DAG·트리·해시 링크) TODO

Math · Day 5 / 52 · 7월 — 이산수학·논리 (Day 3–10)

개념

그래프는 정점 집합과 간선 집합의 쌍이고, 간선에 방향이 있는지와 사이클이 있는지에 따라 성질이 크게 갈린다. DAG는 방향 간선만 있고 사이클이 없는 그래프로, 위상 정렬이 항상 가능하며 그 순서가 의존성 해결과 순차 처리의 기준이 된다. 트리는 연결되어 있으면서 사이클이 없는 그래프로 정점이 n개면 간선이 정확히 n-1개이고, 루트를 정하면 각 정점에서 루트까지의 경로가 유일하다. 해시 링크는 간선을 메모리 주소가 아니라 대상 노드 내용의 해시로 두는 방식으로, 노드 내용을 바꾸면 해시가 달라져 그 노드를 가리키던 상위 노드까지 전부 달라지므로 구조 전체가 변조 감지 가능해진다. 해시 링크로 이어진 구조는 아직 존재하지 않는 해시를 미리 가리킬 수 없으므로 원리적으로 사이클이 생길 수 없고 항상 DAG가 되며, 머클 트리와 블록 체인이 그 특수한 경우다.

블록체인 구조, 머클 증명, 빌드 의존성, 트랜잭션 의존 그래프가 전부 같은 DAG와 해시 링크 언어로 설명되기 때문이다.

코드 · 수식

# 그래프 기초(DAG·트리·해시 링크) — 해시 링크로 만든 체인은 원리상 사이클이 생길 수 없어 항상 DAG.
# 노드 하나(payload)를 바꾸면 그 해시가 바뀌고, 상위 노드가 가리키던 해시도 전부 달라진다.

import hashlib

def h(data: bytes) -> str:
    return hashlib.sha256(data).hexdigest()[:12]

class HashNode:
    def __init__(self, payload, prev_hash=""):
        self.payload = payload
        self.prev_hash = prev_hash
        self.hash = h(f"{payload}|{prev_hash}".encode())

def build_chain(payloads):
    chain = []
    prev = ""
    for p in payloads:
        node = HashNode(p, prev)
        chain.append(node)
        prev = node.hash
    return chain

def verify_chain(chain):
    prev = ""
    for node in chain:
        if node.prev_hash != prev:
            return False
        if h(f"{node.payload}|{node.prev_hash}".encode()) != node.hash:
            return False
        prev = node.hash
    return True

chain = build_chain(["genesis", "tx1", "tx2", "tx3"])
print("원본 체인 유효?", verify_chain(chain))
for n in chain:
    print(f"  {n.payload:10} prev={n.prev_hash or '(none)':14} hash={n.hash}")

# tx2 의 내용을 변조하면 → 그 노드의 해시가 바뀌고, tx3.prev_hash 와 불일치 → 검증 실패.
chain[2].payload = "tx2-tampered"
chain[2].hash = h(f"{chain[2].payload}|{chain[2].prev_hash}".encode())
print("\ntx2 변조 후 체인 유효?", verify_chain(chain))

docs/code/math/math-5.py

연습

디렉터리 트리를 읽어 각 노드의 해시를 자식 해시들로부터 계산하는 머클 트리를 구현하고, 파일 한 바이트를 바꿨을 때 루트가 바뀌는 것과 변경 경로 위의 노드만 다시 계산하면 되는 것을 확인하기.

실무 · Verex 연결

이더리움의 상태 트리와 블록 연결이 모두 해시 링크 DAG이며, Gnosis Conditional Tokens에서 condition과 position 식별자가 입력값의 해시로 결정되는 것도 같은 원리다.

Jayverse에서의 위치

Verex: ctf-exchange 포크이므로, condition ID와 position ID 도출이 정확히 같은 해시 방식을 따르는지 확인하고 하나의 입력(오라클, questionId, outcome 수)을 바꾸면 그 ID만 바뀌는지 테스트를 추가한다. 해시 링크 도출에서 조용한 충돌이 나면 condition 트리 전체가 손상된다.
gitboard: 서비스 의존관계(token 다음 bridge, 그다음 wallet 등)를 위상 정렬이 있는 명시적 DAG로 모델링한다. 배포와 마이그레이션 순서는 운영자가 기억하는 것이 아니라 그래프에서 도출돼야 한다.
Bridge: 릴레이어가 커밋하는 대상으로 해시 링크된 스냅샷(잠긴 잔액의 머클 루트)을 사용한다. 잠긴 예치금 하나를 조작하면 전체 원장을 훑지 않고도 루트 불일치만으로 감지할 수 있다.

핵심 표현

이 페이지의 영어 본문에서 배울 만한 단어와 표현, 뜻과 나온 자리.

Expression	뜻 · 쓰이는 자리
diverge sharply	크게 갈라지다/차이 나다 · 조건에 따라 성질이 확연히 달라질 때. "diverge sharply depending on whether edges are directed"
cascade up	(변화가) 위로 연쇄적으로 퍼지다 · 하나의 변경이 상위 노드까지 줄줄이 영향을 줄 때. "cascades up through every ancestor node"
tamper-evident	조작하면 티가 나는(변조 감지 가능한) · 데이터가 변경되면 바로 드러나는 구조를 말할 때. "making the whole structure tamper-evident"
by construction	구조상 원천적으로, 설계 자체에 의해 · 별도 증명 없이 구조만으로 성립하는 성질을 말할 때. "can never contain a cycle by construction"
point ahead to	아직 존재하지 않는 대상을 미리 가리키다 · 해시 링크가 미래 값을 참조할 수 없다는 제약. "can never point ahead to a hash that doesn't exist"
the basis for	~의 토대/근거가 되다 · 어떤 개념이 다른 응용의 기반이 될 때. "the basis for dependency resolution"
connected, acyclic	연결되어 있고 순환이 없는 · 트리의 정의를 이루는 두 성질을 가리킬 때. "A tree is a connected, acyclic graph"
DAG	방향성 비순환 그래프(Directed Acyclic Graph) · 사이클 없는 방향 그래프, 위상정렬이 가능한 구조. "A DAG has only directed edges and no cycles"
Gnosis Conditional Tokens	Gnosis가 만든 조건부 토큰 프레임워크(예측시장용 포지션 토큰 표준) · 조건·포지션 식별자를 해시로 만드는 예로 언급. "Gnosis Conditional Tokens derive condition and position identifiers as hashes"

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