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.

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 식별자가 입력값의 해시로 결정되는 것도 같은 원리다.

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