path: root/docs/research/099-link-epochs.md

# 099 — 링크의 에폭: 나중에 키가 새도 지난 기록은 풀리지 않는다

2026-09-29. [설계 011](../design/011-pure-transport.md) 4단계의 에폭 바꿈이다. [098](098-link-security.md)은 보안 검사를
통과했지만, 전방 비밀성이 없다는 것을 인터넷에 켜기 전의 첫 과제로 남겼다.

착수 기준:

- **바꿀 결정.** 링크를 인터넷 쪽에 켤 수 있는가. 098의 남은 첫 과제다.
- **최소 확인.**
  - 나중에 두 노드의 개인 키를 모두 얻은 자가, 녹화한 패킷 가운데 에폭 1부터는 하나도 열지 못한다. 에폭이 시작된 run에서는
    그 뒤로 정적 키로 봉인한 기록이 없다.
  - 손실, 재정렬, 양쪽 재시작, 쉼, 재전송 공격 아래에서, 그리고 메모를 잃은 재시작에서도 모든 기록이 한 번씩 적용된다.
  - M2(기기 1만 개, 받는 쪽 kill -9)의 보낸 패킷 수, 꼬리 지연, CPU가 에폭 전과 같은 수준이다.
- **중단 기준.** M2가 에폭 전보다 눈에 띄게 나빠지고 되돌릴 수 없으면, 에폭을 켜지 않고 설계를 다시 본다.

## 쉬운 말로

- 알아낸 것:
  - 링크에 에폭을 넣었다. 두 노드의 개인 키가 나중에 새도, run의 첫 에폭이 시작된 뒤에 오간 것은 풀 수 없다. 보통은 첫 답과
    함께 시작한다. 결정적 검사로 확인한다.
  - 처음 재 보니 M2의 p99가 4.7 ms에서 34–45 ms로 나빠졌다. 이 Pi의 OpenSSL에서 X25519 합의 한 번이 164 µs다(날 개인 키를
    가져오면 220 µs). 1만 대가 깨어날 때 이것을 초당 2,000번, 패킷과 그 답 사이에서 했다.
  - 수락을 초당 256번(한 번에 8번까지)으로 묶고, X25519를 답을 보낸 뒤로 옮겼다. 첫 1초의 꼬리가 사라졌다.
  - 되짚다가 M6와 보안 검사가 M2에 남긴 것도 찾았다. 경로 MTU 탐침이 기기마다 패킷 하나(+10k), 주소 확인의 답이 또 하나(+38k)를
    더 보냈다. 둘 다 없앴다. 보낸 패킷은 M6 전과 같은 16만이다(80초).
  - 에폭에 든 뒤와 받는 쪽을 kill -9 하고 다시 띄운 뒤는 에폭 전과 같다. 저장까지 p50 0.4–0.5 ms, p99 0.8–1.0 ms, CPU도 같다. 다시
    뜬 받는 쪽은 메모에서 에폭을 읽으므로 X25519가 0번이다.
  - 값은 둘에 든다. 처음 만나는 5초에 p50이 0.7–1.0 ms 늘고, 수락이 이어지는 약 40초 동안 p50이 0.7 ms 는다.
  - 메모를 잃은 받는 쪽은 비싸졌다. 에폭 비밀을 잃었으니 보내는 이 1만 개가 모두 에폭을 다시 연다. 저장이 0.8초 멈추고, 따라잡는
    데 7.7초 걸린다. 에폭 전에는 멈춤이 없고 0.2–0.7초였다. 전방 비밀성을 지키는 한 피할 수 없는 값이다.
  - 부하 생성기가 기기 1만 개의 타이머를 5 ms마다 모두 물어, CPU의 83 %를 거기에 썼다. 기록의 시각을 그 순회의 시작으로 찍었으므로
    순회 시간(0.75–0.94 ms)이 지연의 바닥이 됐다. 기기마다 제 타이머를 기억하게 고치자 세 판 모두 p50이 0.4 ms로 내려왔다.
- 아직 모르는 것:
  - 1만 대가 한꺼번에 깨어나면 모두 에폭 1에 들기까지 약 40초 걸린다. 그동안 그 run들의 기록은 정적 키로만 보호된다.
  - 메모를 잃은 재시작을 더 빠르게 할 수 있는지. 받는 쪽이 에폭을 모른다고 알리거나, 더 빠른 X25519를 쓰는 길이 있다.
- 사용 경험의 차이: 기기와 앱은 달라지는 것이 없다. 인터넷에 켜기 전에 막고 있던 첫 과제가 풀렸다.

## 한 것

### 에폭

- 패킷의 첫 바이트 아래 네 비트가 그 패킷을 봉인한 에폭(16으로 나눈 나머지)이다. 나머지 머리는 그대로다.
- 에폭 0의 비밀은 두 노드의 정적 비밀(X25519)이다. 지금까지의 키가 그대로 에폭 0이다.
- 보내는 쪽은 다음 에폭을 위한 키 쌍을 만들어 공개 반쪽을 OFFER 프레임(에폭 번호, 공개 키 37 B)에 싣는다. 수락될 때까지
  패킷마다 싣는다.
- 받는 쪽은 자기 쌍의 공개 반쪽을 ACCEPT 프레임에 실어 답한다. 둘의 X25519와 지금 에폭의 비밀에서 HKDF로 다음 에폭의 비밀이
  나온다("pure link 0 epoch", 번호). 개인 반쪽은 합의하자마자 지운다. 그래서 지난 에폭의 키는 두 노드의 키로 다시 만들 수 없다.
- 보내는 쪽은 ACCEPT를 받자마자 새 에폭으로 봉인한다. 받는 쪽은 새 에폭의 패킷이 열리면 그것을 run의 에폭으로 삼는다. 늦게 온
  지난 에폭의 패킷도 연다.
- 보내는 쪽은 run의 첫 패킷부터 에폭 1을 제안한다. 받는 쪽이 곧바로 수락하면 첫 답과 함께 시작한다(바쁘면 늦어진다. 아래). 그
  뒤 한 시간이나 1 GiB마다 바꾼다(`pure_link_sender_epochs`).
- 받는 쪽은 수락한 에폭을 메모([095](095-restart-and-first-contact.md))의 보내는 이 자리에 적는다. 그래서 다시 떠도 보내는 쪽의
  에폭으로 곧바로 이어 간다. 비대칭 연산은 들지 않는다. 메모의 한 자리는 64 B에서 256 B가 됐다.
- 메모를 잃은 받는 쪽은 보내는 쪽의 패킷을 열지 못한다. 보내는 쪽은 2초 동안 아무것도 듣지 못하고 탐침 네 번이 답을 받지
  못하면 에폭을 잃은 것으로 본다. 그러면 에폭 0에서 제안만 보낸다. 기록은 싣지 않는다. 새 에폭이 시작되면 기록을 다시 보낸다.
  경로 위의 공격자가 답을 막아 이 길로 몰아도, 정적 키로 봉인되는 기록은 없다.

### 수락은 값이 든다

수락 한 번에 양쪽이 X25519를 한 번씩 한다. 이 Pi의 OpenSSL 3.5.7에서 잰 값이다
([x25519.c](../../research/experiments/019-idle-links/x25519.c)).

| | µs |
|---|---:|
| 키 쌍 만들기 | 57 |
| 날 개인 키 가져오기(OpenSSL이 공개 반쪽을 다시 계산한다) | 56 |
| 합의 | 164 |

보내는 쪽은 제안한 쌍을 오래 들고 있을 수 있고, 노드 하나가 보내는 쪽을 많이 가질 수 있다. 그래서 쌍을 OpenSSL의 보안 힙이 아니라
날 바이트로 들고, 합의할 때 가져온다. 보안 힙(16 KiB)에 두면 부하 생성기의 보내는 이 1만 개가 쌍을 만들지 못했다. 합의 한 번은
그래서 220 µs다.

받는 쪽은 수락을 이렇게 다룬다.

- 받는 쪽의 쌍은 1초 동안 그 초의 제안 모두가 함께 쓴다. 키 만들기는 초에 한 번이다.
- 기록을 싣고 온 제안은 토큰을 하나 쓴다. 토큰은 초당 256개, 한 번에 8개까지 찬다. 토큰이 없으면 받지 않는다. 보내는 쪽은
  다음 패킷에 다시 제안한다.
- 기록 없이 온 제안(에폭을 잃고 기다리는 보내는 쪽)은 토큰을 기다리지 않는다. 대신 보내는 이마다 초에 한 번이다. 허용된
  보내는 이가 run을 바꿔 가며 X25519를 끝없이 시키지 못한다.
- X25519는 패킷을 받는 자리에서 하지 않는다. 그 turn의 답을 모두 보낸 뒤에 하고, ACCEPT를 곧바로 이어 보낸다.

### 만들면서 찾아 고친 것

1. **네 비트가 겹침.** 체인을 에폭 0부터 다시 시작하면, 수락한 에폭과 지금 에폭의 네 비트가 같을 수 있다. 받는 쪽은 후보 키를
   차례로 시도한다. 수락한 것, 지금 것, 하나 전 것, 에폭 0의 것이다.
2. **다시 시작하는 동안 답이 열리지 않음.** 보내는 쪽은 에폭 0으로 돌아갔는데 받는 쪽은 옛 에폭으로 답했다. 체인이 에폭 0부터
   다시 시작하면 받는 쪽도 에폭 0으로 돌아가고, 옛 에폭은 하나 전 것으로 남긴다.
3. **손실에 에폭을 잃었다고 봄.** 10 % 손실에서 2초 동안 답을 못 듣는 일이 있었다. 탐침 네 번이 모두 답을 받지 못해야 한다는
   조건을 더했다.
4. **M2의 보낸 패킷이 늘어남.** 아래 "M2"에 적었다.

## 결과

### 결정적 검사

[test-link.c](../../link/test-link.c)에 두 경우를 더했다. 모두 `make check`에 들어 있다.

- 모든 경우의 끝에서, 두 노드의 개인 키를 가진 자가 보내는 쪽이 보낸 모든 패킷을 정적 키로 열어 본다.
  - 에폭 1 이상의 패킷이 하나라도 열리면 실패다.
  - run의 첫 에폭 1 이상 패킷보다 뒤에 보낸 에폭 0 패킷에 기록이 있으면 실패다.
- **에폭**: 에폭 0.2초(받는 쪽이 보내는 이마다 초에 한 번 받으므로 실제로는 약 1초), 손실 5 %, 재정렬, 양쪽 재시작, 쉼, 재전송
  공격 10 %.
- **잊는 받는 쪽**: 메모 없이 재시작한다. 보내는 쪽이 에폭을 다시 시작해야 한다.

| 경우 | 기록 | 가상 시간 | 에폭 | 정적 키로 열린 패킷 | 결과 |
|---|---:|---:|---:|---:|---|
| 깨끗함 | 3,000 | 0.1초 | 1 | 2 | 모두 에폭 0, 첫 에폭 전 |
| 에폭 | 3,000 | 16.2초 | 16 | 226 | 모두 에폭 0. 에폭이 시작된 run에서 그 뒤 기록 0. 재전송 941개, 공격자에게 간 바이트 0 |
| 잊는 받는 쪽 | 3,000 | 16.5초 | 2 | 5 | 다시 시작한 에폭으로 모든 기록 전달 |

"정적 키로 열린 패킷"은 모두 run이 시작해 첫 에폭이 시작되기 전의 패킷과, 에폭을 다시 여는 제안이다. 에폭 경우에는 보내는 쪽이
다시 시작할 때마다 새 run이 생기고, 받는 쪽이 보내는 이마다 초에 한 번만 수락하므로 이런 패킷이 많다.

### M2

[095](095-restart-and-first-contact.md)의 M2다. 기기 1만 개가 5초마다 주문 하나를 보낸다(초당 2,000건). 받는 쪽을 kill -9 하고
곧바로 다시 띄운다. 원시 결과는 `research/experiments/019-idle-links/`의 `2026-09-29-epochs-*.jsonl`에 있다.

**처음 잰 것.** 에폭을 넣고 40초 M2를 돌리니 p99가 34–45 ms였다. 커밋마다 두 번씩 돌려 어디서 무엇이 늘었는지 찾았다(아래 표의
옛 생성기).

| 판 | 보낸 패킷 | p99 |
|---|---:|---:|
| a70cf07 (M6 전) | 80.0k | 4.3 ms |
| 41e170e (늦은 패킷, CUBIC) | 80.0k | 4.4 ms |
| cc6dad4 (부분으로 자르기) | 80.0k | 4.6 ms |
| 34df292 (경로 MTU) | **90.0k** | 4.8–5.1 ms |
| 4f6a1a4 (페이싱) | 90.0k | 4.8 ms |
| 6152bd8 (보안 검사) | **117.9–118.7k** | 4.7 ms |
| 에폭 첫 판 | 85.4–85.9k | **34–45 ms** |

- **경로 MTU 탐침(+10k).** 작은 기록을 하나씩 보내는 링크는 패킷이 가득 찬 적이 없다. 그래도 1,452 B 탐침을 보냈다. 이제 가득 찬
  패킷이 있었던 링크만 탐침한다. 더 큰 패킷이 실어 줄 것이 없으면 찾을 까닭이 없다.
- **주소 확인의 답(+38k).** 보내는 쪽은 CHALLENGE를 받으면 RESPONSE만 담은 패킷을 따로 보냈다. 기기마다, 받는 쪽이 다시 뜰 때마다
  하나씩이다. 이제 RESPONSE는 나갈 패킷(기록이나 탐침)에만 싣는다. 확인 전의 답은 받은 바이트의 3배까지다. 패킷 하나에 대한
  답(ACK와 저장했다는 말)은 그보다 작다. 답이 그 한도에 막히면, 답을 기다리는 보내는 쪽의 탐침이나 다시 보내는 기록이 RESPONSE를
  실어 간다.
- **에폭의 꼬리.** 첫 1초에 저장이 뭉쳤다. 1만 대가 5초 안에 깨어나면 노드는 초당 2,000번, 정적 비밀(164 µs)과 수락(220 µs)을
  패킷과 답 사이에서 했다. 부하 생성기의 한 스레드도 수락마다 220 µs를 썼다. 수락에 토큰을 두었다(위). 처음에는 통이 256개 가득
  찬 채 시작해, 첫 1초에 X25519를 256번 연달아 했다(56 ms, 첫 1초 p99 44–54 ms). 한 번에 8개로 줄이자 사라졌다.

**부하 생성기.** 수락이 끝난 뒤에도 p50이 에폭 전보다 0.15 ms 높았다. gprof로 보니 생성기 CPU의 83 %가 `pure_link_sender_due`였다.
5 ms마다 기기 1만 개의 타이머를 모두 물었고(한 번 47 ns, 대부분 캐시 미스), 기록의 시각은 그 순회의 시작으로 찍었다. 그래서 순회
시간이 지연의 바닥이었다. 순회는 6152bd8에서 0.75 ms, 에폭에서 0.87–0.94 ms였다. 보내는 쪽 구조체가 912 B에서 1,120 B가 되면서
길어졌다. 타이머가 읽는 필드의 자리는 같게 했지만(에폭의 필드를 끝으로 옮겼다) 순회는 줄지 않았다. 생성기를 고쳤다. 기기마다 제
보내는 쪽의 다음 타이머를 기억하고, 보내는 쪽을 건드렸을 때만 다시 묻는다. 타이머는 보내는 쪽을 건드릴 때만 바뀌므로 결과는 같다.
아래는 모두 고친 생성기로 잰 것이다.

**최종.** 80초, 60초에 kill -9, 두 라운드다. 초마다 만든 기록의 p50과 p99를 구간별로 평균했다.

| | a70cf07 (M6 전) | 6152bd8 (에폭 전) | 에폭 |
|---|---|---|---|
| 보낸 패킷 | 160,050 · 160,056 | 198,470 · 200,528 | 160,075 · 160,044 |
| 처음 만남(0–5초) p50 / p99 | 3.7 / 4.1–5.1 ms | 3.9–4.0 / 4.7–4.8 ms | 4.7 / 5.8–6.0 ms |
| 수락이 이어짐(5–40초) p50 / p99 | 0.37–0.38 / 0.86–0.94 ms | 0.39 / 0.81–1.03 ms | 1.05–1.13 / 1.70–1.79 ms |
| 에폭에 든 뒤(45–60초) p50 / p99 | 0.39–0.40 / 0.79–0.81 ms | 0.35–0.40 / 0.74–0.88 ms | 0.38–0.40 / 0.77 ms |
| 다시 뜬 뒤(62–80초) p50 / p99 | 0.41–0.46 / 1.10–1.21 ms | 0.47 / 0.86–0.91 ms | 0.46–0.47 / 0.86–0.95 ms |
| 전체 p99 / 최대 | 3.8–3.9 / 35–38 ms | 4.2 / 37–85 ms | 5.1 / 36–39 ms |
| 저장이 멈춘 100 ms 칸, 따라잡기 | 0, 0.2초 | 0, 0.2초 | 0, 0.2초 |
| 60초의 CPU, 노드 / 생성기 | 90–110 / 60–70 ms/s | 110 / 70 ms/s | 100–120 / 60–70 ms/s |

- 에폭에 든 뒤와 다시 뜬 뒤는 에폭 전과 같다. 다시 뜬 노드는 메모에서 에폭을 읽는다. run마다 키를 한 번 만들고, X25519는 0번이다.
- 값은 두 구간에 든다.
  - 처음 만남: p50이 0.7–1.0 ms 는다.
  - 수락이 이어지는 약 40초: p50과 p99가 0.7–0.9 ms 는다. 수락 한 번에 양쪽이 220 µs씩 쓴다. 생성기는 5 ms마다 기기 10대를
    한꺼번에 보내고, 수락은 5 ms에 1.3번꼴이라 거의 모든 묶음에 끼어든다. 노드는 X25519를 그 turn의 답을 보낸 뒤에 한다. 하지만
    저장했다는 답은 저장이 끝난 다음 turn에 나가므로 그 앞에 걸린다.
  - 가르는 검사를 둘 했다(옛 생성기). 수락을 막아 모두가 계속 제안만 하게 하면, 이 구간의 p50은 에폭 전과 순회 차이만큼만
    달랐다(0.93 대 0.75–0.78 ms). 에폭에 든 기기와 아직 제안하는 기기의 p50은 같았다(1.36 대 1.40 ms). 값은 기기의 상태가 아니라
    수락하는 일에 있다.

**메모 없이 다시 뜬 받는 쪽.** 두 라운드 모두 거의 같았다.

| | 6152bd8 (에폭 전) | 에폭 |
|---|---|---|
| 저장이 멈춘 100 ms 칸 | 0 | 8 |
| 따라잡기 | 0.2–0.7초 | 7.7–7.8초 |
| 저장까지 p99 / 최대 | 4.2–4.3 ms / 46–61 ms | 4.1–4.2초 / 7.7–7.8초 |
| 노드의 X25519 | 10,000 | 20,007 |
| 다시 뜬 뒤 10초의 CPU, 노드 / 생성기 | 2.8 / 0.8–0.9초 | 5.4–5.6 / 4.7–4.8초 |

- 메모가 없으면 받는 쪽은 에폭 비밀도 잃는다. 보내는 쪽의 에폭 1 패킷을 열 수 없다. 보내는 쪽은 탐침 네 번에 답이 없으면(약
  0.8초) 에폭 0에서 제안만 보낸다. 받는 쪽은 정적 비밀(X25519)을 만들고 수락한다(X25519). 보내는 쪽도 수락마다 X25519를 한다.
- 따라잡기는 CPU에 묶였다. 노드의 링크 스레드가 X25519 2만 번(약 3.8초)을 하고, 생성기의 한 스레드가 보내는 이 1만 개의 키 쌍과
  합의(약 2.8초)를 한다. 실제 기기는 저마다 CPU가 있으니 생성기 쪽 몫은 이 하네스의 값이다.
- 잃거나 겹친 기록은 없다. quinn의 보통 재시작(095: 멈춘 칸 10, 따라잡기 10.9초)보다는 여전히 짧다.

**M1.** 쉬는 보내는 이 1만 개일 때 노드의 익명 메모리는 같다(21,216 대 21,360 kB). 메모 파일은 보내는 이마다 256 B가 됐다(1만
개에 2.5 MB). 파일에 매핑된 페이지라 RSS에는 그만큼 더 잡힌다. 처음 보내는 기록 하나에 노드 CPU가 0.263에서 0.307 ms가 됐다.
수락의 값이다.

## 판정

- 098이 남긴 전방 비밀성은 검사한 범위에서 풀렸다. 두 노드의 개인 키가 나중에 새도, run의 첫 에폭이 시작된 뒤에 오간 것은
  열리지 않는다.
- M2의 중단 기준(눈에 띄게 나빠지고 되돌릴 수 없으면 켜지 않는다)은 넘지 않았다. 정상 상태와 다시 뜬 뒤는 에폭 전과 같다. 값은
  대량으로 처음 만난 뒤 약 40초의 지연(p50 +0.7 ms)과, 메모를 잃은 재시작의 7.7초다. 앞의 것은 토큰으로 조절된다. 뒤의 것은 전방
  비밀성의 정의에서 나온다. 받는 쪽이 에폭 비밀을 잃으면 에폭은 다시 열어야 한다.
- 에폭은 켜 둔다. 끌 스위치도 두지 않는다.

## 한계와 다음

- **run의 첫 패킷.** 첫 에폭이 시작되기 전의 패킷은 정적 키로만 보호된다. QUIC 0-RTT와 같은 한계다. 보내는 쪽이 다시
  시작하면 새 run이 에폭 0부터 시작한다.
- **KCI는 그대로다.** 받는 쪽의 개인 키를 가진 자는 자기 run을 에폭 0부터 열어 어떤 보내는 이로도 행세할 수 있다. 에폭이 막는
  것은 이미 오가는 남의 run에 끼어드는 것이다. 098의 판정 가운데 이 부분을 바로잡았다.
- **메모에 지금 에폭의 비밀이 있다.** 메모 파일과 두 노드의 키를 함께 가진 자는 지금 에폭과 그 하나 전을 연다. 메모는 노드 키 옆의
  0600 파일이다. 메모를 쓰지 않으면 이 창은 없지만, 받는 쪽이 다시 뜰 때마다 위의 7.7초가 든다.
- **네 비트.** 머리에는 에폭의 아래 네 비트만 싣는다. 받는 쪽은 수락한 것, 지금 것, 하나 전 것, 에폭 0의 것만 시도한다. 그보다
  오래된 에폭의 패킷은 열리지 않고, 보내는 쪽이 다시 보낸다.
- **X25519가 느리다.** 이 Pi의 OpenSSL에서 합의가 164 µs다. 양쪽 모두 쌍을 날 바이트로 들어 합의마다 56 µs를 더 쓴다. 더 빠른
  구현은 수락과 메모 없는 재시작을 모두 줄이지만, 암호 구현은 직접 쓰지 않는다.
- **메모를 잃은 재시작.** 받는 쪽이 에폭을 모른다고 알리면(정적 키로 봉인한 답) 0.8초의 멈춤이 한 RTT로 준다. 답할 수 없는
  패킷에 답하는 일이라 증폭과 강제 재협상을 따져야 한다. 아직 하지 않았다.
- **M6의 값.** 옛 생성기로 잰 이분 탐색에서는 M6 뒤 정상 상태 CPU가 양쪽 모두 올라 보였다. 새 생성기로는 세 판이 잡음(±20 ms/s)
  안에서 같다. 올라 보인 것의 대부분은 생성기의 순회였다.
- 다음은 011 4단계의 나머지다. 경로 바뀜의 실제 측정(주소가 바뀌는 동안 끊긴 시간)과 저장소 옮기기(M3)다.