diff options
| -rw-r--r-- | README.md | 5 | ||||
| -rw-r--r-- | docs/design/006-native-protocol.md | 7 | ||||
| -rw-r--r-- | docs/design/009-layout.md | 2 | ||||
| -rw-r--r-- | docs/design/011-pure-transport.md | 22 | ||||
| -rw-r--r-- | docs/design/012-link-protocol.md | 324 |
5 files changed, 354 insertions, 6 deletions
@@ -36,7 +36,7 @@ The source follows the principle below, a small core with the rest selected arou |---|---|---| | `core/` | execution, ownership, limits and completion (`runtime.c`); the app model: modules verified before they run, events as transactions, states as drafts (`module*.c`); what the core asks of storage (`state.h`, `store.h`) | `build/libpure.a` (with the store) | | `store/` | the tree store: one file, a commit is one contiguous write and one sync (formats `PURETRE3`, `PUREREC1`) | in `libpure.a` | -| `link/` | links without connections: saved sends over UDP, sealed with the two nodes' keys, no handshake ([011](docs/design/011-pure-transport.md)); the crypto they and sealed sends use, OpenSSL's part apart, mapped only by a process that uses one | `build/libpure-link.a`, `build/pure-crypto.so` | +| `link/` | links without connections, the default between Pure nodes: saved sends over UDP, sealed with the two nodes' keys, no handshake ([011](docs/design/011-pure-transport.md), specified in [012](docs/design/012-link-protocol.md)); the crypto they and sealed sends use, OpenSSL's part apart, mapped only by a process that uses one | `build/libpure-link.a`, `build/pure-crypto.so` | | `serve/` | `pure-serve`: the HTTP host, outbound delivery, JSON read in place, surfaces for people run in the node ([010](docs/design/010-surfaces.md)) | `build/pure-serve` | | `cli/` | command-line hosts | `build/pure-run`, `build/pure-edit-module` | | `prototypes/` | the earlier document runtime (000-077), built against `core/` and `store/` | `make -C prototypes/connections` | @@ -256,7 +256,8 @@ from the default on this host. A 70-edit run exposes the page rebuild and occasional long delays, so the page format remains optional. HTTP is a compatibility boundary, not the required model for Pure-to-Pure -communication. Selected scalar and document apps now use bounded binary peer +communication: between nodes, saved sends go over links without connections +([specification](docs/design/012-link-protocol.md)). Selected scalar and document apps now use bounded binary peer protocols over mutually authenticated TLS 1.3/TCP. The document peer shares `editor.pure` work and storage with the CLI, HTTP adapter, and GTK window; its request can omit an output body that the caller will not consume. The diff --git a/docs/design/006-native-protocol.md b/docs/design/006-native-protocol.md index 09c4075..27a1b37 100644 --- a/docs/design/006-native-protocol.md +++ b/docs/design/006-native-protocol.md @@ -12,12 +12,15 @@ TLS 1.3/TCP 위에 실은 피어 호스트를 검증했다. [026 — scalar 피� 상태를 앱 상태와 한 커밋에 두어 연결 개념을 없앤다. 아래 "새 UDP 전송은 … 별도 연구 후보로 연다"는 조건은 그 가설과 중단 기준이 판정한다. +2026-09-29: 011의 가설과 검사가 모두 서서, 노드 사이 전달의 기본을 연결 없는 링크로 정했다. 명세는 +[012 — 링크 프로토콜](012-link-protocol.md)이다. HTTP 전달은 웹, 기존 도구, 제3자와 잇는 경계로 남는다. + ## 결정 Pure 간 통신은 HTTP 메서드·URL·문자열 헤더를 필수 실행 모델로 삼지 않는다. 앱이 작성한 연결과 데이터 형식에서 자체 바이너리 통신 형식을 준비하는 방향으로 진행한다. -HTTP는 웹·기존 도구와 연결하는 호환 경계로 유지한다. 첫 검증 전송은 TLS 1.3/TCP이며, -최종 범용 전송 정책은 아직 선택하지 않았다. +HTTP는 웹·기존 도구와 연결하는 호환 경계로 유지한다. 첫 검증 전송은 TLS 1.3/TCP였다. +노드 사이의 전송은 2026-09-29에 연결 없는 링크로 정했다(위). 외부 런타임·서비스·프로그램과의 통신도 핵심 요구사항이다. Pure끼리의 자체 형식과 별도로 상대가 사용하는 프로토콜·형식으로 요청을 받고 보낼 수 있어야 한다. 외부에 Pure 사용을 diff --git a/docs/design/009-layout.md b/docs/design/009-layout.md index 3c36194..5339c5b 100644 --- a/docs/design/009-layout.md +++ b/docs/design/009-layout.md @@ -92,7 +92,7 @@ git 저장소로는 떼지 않았다. 저장소를 나눈 비용은 경계를 � 링크가 33 %, Vega가 6 %다. - Vega는 C 3만 3천 줄 가운데 Pure 헤더를 쓰는 곳이 3개 파일(4.7 %)이다. 따로 두는 편이 싸다. -- 링크의 전선 형식은 011의 남은 단계(에폭, 경로, 보안, M6)에서 더 바뀐다. +- 링크의 전선 형식은 이제 명세다([012](012-link-protocol.md), 판 0). 다음 판은 판 번호와 키 유도 문자열을 함께 바꾼다. - 명세를 쓰고 Pure 밖의 구현이 생기면 `git subtree split`으로 그대로 뗀다. ## 비용 diff --git a/docs/design/011-pure-transport.md b/docs/design/011-pure-transport.md index 034321e..5513476 100644 --- a/docs/design/011-pure-transport.md +++ b/docs/design/011-pure-transport.md @@ -1,6 +1,7 @@ # 011 — 연결 없는 전송: 전송의 상태를 앱의 데이터로 -작성일: 2026-09-28(같은 날 첫 판을 버리고 다시 씀). 상태: 설계. 1단계를 구현했고 M1, M2, M4, M5, M6를 쟀다. +작성일: 2026-09-28(같은 날 첫 판을 버리고 다시 씀). 상태: 채택(2026-09-29). Pure 노드 사이 전달의 기본이다. 명세는 +[012](012-link-protocol.md)다. [외부 피드백 002](../outside-feedback/feedback-002.md)의 "QUIC을 능가할 자체 raw socket 프로토콜"에서 시작한다. 1단계(링크 시제품과 kill -9 검사)는 [093](../research/093-connectionless-link.md)에 있다. 어느 쪽을 죽여도 핸드셰이크 없이 @@ -49,6 +50,25 @@ M3(저장소 옮기기, H3)는 [100](../research/100-moved-receiver.md)에 있� - M5를 ngtcp2와도 쟀다. 1 KiB 이상에서 Pure가 두 QUIC 모두보다 25 % 넘게 가볍고, 61 B에서는 ngtcp2의 1.04배, quinn의 0.90배다. - 패킷마다의 스트림 이름은 비용이 아니었다. 빼 보니 잡음 안이라 되돌렸다. +5단계(채택과 명세)는 2026-09-29에 했다. 중단 기준표의 마지막 줄대로다. + +- H1–H4가 모두 섰다. +- 잃음·겹침 검사, 논스 검사, 보안 검사를 모두 통과한다. +- 전달당 CPU는 1 KiB 이상에서 두 QUIC보다 25 % 넘게 가볍다. 61 B에서는 ngtcp2의 1.04배로 10 % 안이다. +- TCP와의 몫은 ±25 % 안이다. +- 전송 코드는 C 3,097줄이다. + +그래서 연결 없는 링크를 노드 사이 전달의 기본으로 삼는다(`--send OUTPUT=pure://host:port/INPUT`). HTTP 전달은 제3자와 +브라우저를 잇는 경계로 남고, 중계를 지나는 봉인한 전달([088](../research/088-sealed-sessions.md))도 그대로다. M6를 ngtcp2와 +재지는 않았다. 가드레일은 quinn과 TCP로 쟀다. + +명세 [012](012-link-protocol.md)를 쓰면서 구현의 구멍 셋을 찾아 고쳤다. +- 받는 쪽이 받지 않는 스트림을 보내는 쪽은 아무 말도 듣지 못해 매초 다시 보냈다. 이제 REFUSED로 이유를 듣고 드물게 다시 시도한다. +- 받는 쪽이 쥘 수 없는 16–64 MiB 기록이 영원히 다시 갔다. +- 한 노드의 출력 셋 이상이 같은 노드로 가면 run들이 받는 쪽의 두 자리를 서로 밀어냈다. + +명세만 보고 파이썬으로 따로 쓴 받는 쪽이 `pure-serve` 노드와 에폭 바꿈까지 맞붙는다. + 2026-09-29에 링크를 `link/`로 뗐다([009](009-layout.md)). 프로토콜은 이제 소켓, 스레드, 시계가 없는 상태이고 (`link/link-protocol.h`), UDP와 스레드는 그 위의 층이다. 그래서 한 스레드가 링크 여럿을 들 수 있다. M2를 이 보내는 쪽으로 다시 돌렸더니 결과가 같았다. 다만 재시작 뒤 가장 늦은 저장이 1초였다. 받았다고 했지만 저장 소식이 없는 기록을 1초 기다리기 diff --git a/docs/design/012-link-protocol.md b/docs/design/012-link-protocol.md new file mode 100644 index 0000000..359dfbe --- /dev/null +++ b/docs/design/012-link-protocol.md @@ -0,0 +1,324 @@ +# 012 — 링크 프로토콜 명세, 판 0 + +작성일: 2026-09-29. 상태: 명세 판 0. + +- 구현은 `link/link-protocol.c`이고, 호스트 API는 `link/link-protocol.h`다. +- 설계와 측정은 [011](011-pure-transport.md)과 연구 093–101에 있다. +- 이 문서만 보고 파이썬으로 따로 쓴 받는 쪽이 `pure-serve` 노드와 맞붙는다(`tests/check.py`의 + `server_links_independent`). 그 받는 쪽은 `cryptography` 패키지만 쓰고 `link/`의 코드는 쓰지 않는다. 노드가 보낸 주문 + 200건이 모두 저장되고, 첫 패킷 하나 뒤로는 두 쪽이 따로 셈한 에폭 1로 봉인된다. + +이 문서는 Pure 노드 사이의 연결 없는 링크가 선 위에서 하는 일을 정한다. 다른 구현이 이 문서만 보고 Pure 노드와 주고받을 수 있게 +하는 것이 목표다. 그래서 바이트 배치, 키 유도, 그리고 상대가 알아야 하는 규칙을 모두 적는다. 혼잡 제어처럼 한쪽이 혼자 정해도 +되는 것은 "지역 선택"으로 따로 표시한다. + +## 용어 + +- **노드**: X25519 키 쌍을 가진다. 공개 키는 32 B다. +- **보내는 쪽**: 한 노드의 출력 하나가 저장한 보내기를 다른 노드의 입력 하나로 보낸다. 시작할 때마다 **run**을 새로 뽑는다. + run은 0이 아닌 무작위 u64다. +- **받는 쪽**: 받아들일 보내는 쪽을 (source 이름, 공개 키) 목록으로 가진다. +- **스트림**: source 이름과 input 이름의 쌍이다. 각 이름은 1–64 B다. 메시지의 shape(u32)가 함께 간다. +- **기록**: 스트림 안에서 1부터 연속된 번호(u64)를 가진 바이트열이다. 0–16 MiB다. +- **들은 번호**: 받는 쪽 앱이 적용하고 저장한 마지막 기록 번호다. +- **답**: 받는 쪽이 보내는 쪽의 run에 보내는 패킷이다. + +정수는 모두 little-endian이다. 논스를 만들 때 패킷 번호만 big-endian으로 넣는다(QUIC과 같다). + +## 전송 + +링크는 UDP 위에 있다. 데이터그램 하나가 패킷 하나다. 받는 쪽의 주소와 포트, 입력 이름은 배선이 준다 +(`pure://host:port/INPUT`). 받는 쪽의 공개 키도 배선이 준다(`--seal OUTPUT=KEY`). + +- 패킷은 37–1,452 B다. 머리 21 B, 봉인한 몸 0 B 이상, 태그 16 B다. +- 보내는 쪽은 처음에 1,200 B 이하로 보낸다. 경로가 1,452 B를 나른다고 확인한 뒤에만 그만큼 보낸다(아래 "경로 MTU"). +- 답은 1,200 B 이하다. +- 이 범위를 벗어난 데이터그램은 답 없이 버린다. + +## 패킷 + +| 위치 | 크기 | 내용 | +|---:|---:|---| +| 0 | 1 | `0x70 \| (에폭 & 0x0f)`: 높은 4비트는 판(0x7이 판 0), 낮은 4비트는 봉인한 에폭 번호의 아래 4비트 | +| 1 | 4 | 봉인한 노드의 키 id(u32): 그 노드 공개 키 32 B의 FNV-1a 32비트(시작값 2166136261, 곱수 16777619) | +| 5 | 8 | run(u64): 보내는 쪽 패킷은 보내는 쪽의 run, 답은 받는 쪽이 그 run에 쓰는 답 run | +| 13 | 8 | 패킷 번호(u64): run 안에서 0부터 하나씩 는다 | +| 21 | n | 프레임들을 AES-128-GCM으로 봉인한 것. 추가 인증 데이터는 머리 21 B 전부다 | +| 21+n | 16 | GCM 태그 | + +키 id는 찾기 위한 힌트일 뿐이다. 두 키가 같은 id를 가질 수 있으므로, 받는 쪽은 그 id를 가진 허용된 키를 차례로 시도한다. + +## 판 + +첫 바이트의 높은 4비트가 판이다. 이 문서는 판 0(0x7)을 정한다. 다른 판의 패킷은 답 없이 버린다. + +판 협상은 선 위에 없다. 받는 쪽이 말하는 판은 키와 함께 배선에서 온다. 인증되지 않은 판 협상 패킷은 위조와 증폭의 길이 되고, +두 노드는 어차피 서로의 키를 미리 알아야 한다. 다음 판은 첫 바이트의 높은 4비트와 키 유도 문자열의 `0`을 함께 바꾼다. 그래서 +판이 다른 두 구현은 서로의 패킷을 열 수 없고, 한 판의 키가 다른 판에서 다시 쓰이지 않는다. + +## 키 + +**정적 비밀.** `S = X25519(자기 개인 키, 상대 공개 키)`의 32 B 그대로다. 양쪽에서 같다. 모두 0이면(작은 차수의 키) 링크를 +만들지 않는다. + +**HKDF.** HKDF-SHA256(RFC 5869)의 Extract와 Expand를 쓴다. salt는 ASCII `pure link 0`(11 B)이고, IKM은 32 B 비밀이다. + +**패킷 키.** `HKDF(비밀, info, 28)`의 앞 16 B가 AES-128 키, 뒤 12 B가 논스 기반이다. + +``` +info = "pure link 0 keys" (16 B) ‖ from 공개 키 (32) ‖ to 공개 키 (32) ‖ from_run (u64) ‖ to_run (u64) +``` + +| 패킷 | 비밀 | from | to | from_run | to_run | +|---|---|---|---|---|---| +| 보내는 쪽 → 받는 쪽 | 보내는 쪽이 봉인하는 에폭의 비밀 | 보내는 쪽 | 받는 쪽 | 보내는 쪽 run | 0 | +| 답 | 그 run이 지금 있는 에폭의 비밀 | 받는 쪽 | 보내는 쪽 | 답 run | 보내는 쪽 run | +| LOST | 에폭 0의 비밀(S) | 받는 쪽 | 보내는 쪽 | 새로 뽑은 답 run | 보내는 쪽 run | + +**논스.** 논스 기반 12 B의 4–11번째 바이트에 패킷 번호를 big-endian으로 XOR한다. run이 키에 들어가므로, 노드가 다시 시작해도 +한 키 아래 논스가 겹치지 않는다. 받는 쪽은 보내는 쪽 run마다 답 run을 새로 뽑는다. 쉬던 보내는 쪽이 돌아와 자리를 다시 만들 +때에도 새로 뽑는다. + +**에폭.** 에폭 0의 비밀은 S다. 에폭 n(≥ 1)의 비밀은 다음과 같다. + +``` +E(n) = HKDF(IKM = X25519(보내는 쪽 에폭 n 개인 키, 받는 쪽 에폭 n 공개 키), + info = "pure link 0 epoch" (17 B) ‖ n (u32) ‖ E(n-1) (32 B), 32) +``` + +두 개인 키는 합의한 뒤 곧 지운다. 그래서 두 노드의 정적 키가 나중에 새어도 에폭 1부터의 패킷은 열리지 않는다. 사슬을 +처음부터 다시 시작할 때(아래 "에폭을 잃음")에는 E(1)을 다시 E(0) = S에서 만든다. + +## 프레임 + +봉인한 몸은 프레임의 연속이다. 각 프레임은 1 B 종류로 시작한다. 읽는 쪽이 모르는 종류를 만나면 그 패킷의 나머지를 읽지 않는다. +PADDING도 그렇게 끝을 채운다. 이름은 u8 길이(1–64)와 그 바이트다. `names`는 source 이름 다음에 input 이름이다. + +| 종류 | 이름 | 방향 | 배치 | +|---:|---|---|---| +| 0x00 | PADDING | 모두 | 패킷 끝까지 0 | +| 0x01 | STREAM | 보냄 | names, u32 shape | +| 0x02 | RECORD | 보냄 | u64 번호, u32 기록 크기, u32 오프셋, u16 길이, 바이트[길이] | +| 0x03 | ACK | 답 | u64 가장 큰 번호, u32 지연(µs), u8 구간 수, 구간마다 u64 처음과 u64 끝(새것부터) | +| 0x04 | STORED | 답 | names, u64 들은 번호, u8 깃발(1: 틈 뒤의 기록을 받지 않았다), u32 허가 | +| 0x05 | PING | 보냄 | 없음 | +| 0x06 | RECORDS | 보냄 | u64 첫 번호, u8 개수, 기록마다 크기(LEB128)와 바이트 | +| 0x07 | CHALLENGE | 답 | u64 | +| 0x08 | RESPONSE | 보냄 | u64 | +| 0x09 | OFFER | 보냄 | u32 에폭, 공개 키 32 B | +| 0x0a | ACCEPT | 답 | u32 에폭, 공개 키 32 B, 답하는 OFFER 공개 키의 앞 4 B | +| 0x0b | LOST | 답 | u64 패킷 번호 | +| 0x0c | REFUSED | 답 | names, u8 이유(1: 그 이름의 메시지 입력이 없다, 2: 입력의 shape가 다르다, 3: 이 키는 그 source로 보낼 수 없다) | + +- RECORD와 RECORDS는 그 앞의 가장 가까운 STREAM의 스트림에 속한다. 앞에 STREAM이 없으면 버린다. +- RECORDS는 번호가 이어진 온전한 기록들이다. LEB128은 7비트씩, 낮은 것부터, 10 B까지다. 기록 하나가 패킷 끝을 넘으면 그 + 기록과 나머지 패킷을 읽지 않는다. +- RECORD는 기록의 한 조각이다. 받는 쪽은 `오프셋 > 크기`, `길이 > 크기 - 오프셋`, `길이 0이면서 오프셋 > 0`, `크기 > 16 MiB`인 + 것을 버린다. +- 답에서 REFUSED는 같은 패킷의 ACK 뒤에 둔다. 보내는 쪽은 한 답 패킷을 끝까지 읽은 뒤 거절이 끝났는지 판단한다. +- 보내는 쪽 패킷은 모두 확인을 부른다. STREAM이나 PING이 늘 있기 때문이다. 답은 확인을 부르지 않는다. + +## 보내는 쪽 + +**시작.** + +1. run을 뽑는다. +2. S를 만들고 에폭 0의 키로 봉인한다. +3. 에폭 1의 키 쌍을 만들어 OFFER로 낸다. + +첫 패킷부터 기록을 싣는다. 핸드셰이크는 없다. + +**패킷.** + +- 패킷 번호는 run 안에서 다시 쓰지 않는다. 봉인했지만 보내지 못한 패킷의 번호도 다시 쓰지 않는다. +- 탐침(PING뿐인 패킷)을 빼면 모든 패킷은 STREAM으로 시작한다. 다음에 받아 둔 CHALLENGE에 대한 RESPONSE(최근 4개)를 + 넣는다. 그다음 OFFER(받아들여질 때까지), 그다음 기록을 넣는다. +- 보낸 적 없는 온전한 기록은 남은 자리에 들어가면 RECORDS에 넣는다. 번호가 이어지면 한 RECORDS에 모은다. 그 밖에는 RECORD + 조각으로 보낸다. 남은 자리가 64 B 이상이면 조각을 잘라서라도 채운다. +- 번호가 한도 이하인 기록만 보낸다. 한도는 STORED마다 `들은 번호 + min(허가, 65536)`(허가가 0이면 1)으로 계산하고, 그 가운데 + 가장 큰 값이다. STORED를 듣기 전에는 저장되지 않은 가장 오래된 기록 번호 - 1 + 1024다. + +**다시 보내기.** 패킷을 다시 보내지는 않는다. 그 패킷이 나른 기록 조각을 새 패킷에 싣는다. 다음 경우에 다시 보낸다. + +- 패킷을 잃었다고 판단할 때. 판단은 RFC 9002를 따른다(지역 선택). +- ACK로 받았다고 들은 조각이 1초 안에 저장되지 않을 때. 받는 쪽이 다시 시작했을 수 있다. +- STORED에 틈 깃발이 올 때. + +STORED의 들은 번호 이하인 기록은 덜어 낸다. 보내는 앱은 그때 그 보내기를 outbox에서 지운다. + +**답 받기.** 답은 머리의 키 id가 받는 쪽 키의 id인 것만 본다. 머리의 에폭 비트가 가리키는 키로 연다. 후보는 지금 에폭, 그 앞 +에폭, 에폭 0이다. 답 run이 무엇이든 받는다. + +- ACK와 STORED는 가장 큰 값으로만 받는다. 다시 보낸 옛 답은 아무것도 되돌리지 못한다. +- CHALLENGE는 다음에 나가는 패킷에서 RESPONSE로 되돌려 준다. 그것만을 위한 패킷은 만들지 않는다. + +**에폭 바꿈.** + +- 한 시간 또는 1 GiB마다 다음 에폭 n+1의 키 쌍을 OFFER로 낸다. 이 주기는 지역 선택이며 이보다 길면 안 된다. +- ACCEPT의 에폭이 낸 에폭과 같고 끝 4 B가 낸 공개 키의 앞 4 B와 같으면 E(n)을 만든다. 그 다음부터 에폭 n으로 봉인한다. +- 앞 에폭의 키는 늦게 오는 답을 열 때까지만 둔다. + +**에폭을 잃음.** + +- 아직 날고 있는 패킷을 가리키는 LOST를 들으면, 에폭 0으로 돌아가 에폭 1을 다시 낸다. 저장되지 않은 기록은 모두 다시 보낸다. + 날고 있던 패킷은 혼잡으로 세지 않는다. 에폭 1 이상에 있거나 사슬을 다시 시작하던 중일 때만 이렇게 한다. +- 에폭 1 이상에서 확인을 부르는 패킷이 나가 있는데 2초 동안 아무 답도 없고 탐침 4번이 연달아 답을 받지 못하면, 에폭 0으로 + 돌아가 에폭 1을 다시 낸다. 이때는 받는 쪽이 받아들일 때까지 기록을 싣지 않고, OFFER만 RTT(100 ms 이상)마다 보낸다. 받은 + 것이 없으니 공격자가 답을 막고 있을 수도 있어, 정적 키 아래로 기록을 다시 보내지 않는다. + +**거절.** 자기 스트림에 대한 REFUSED를 들으면 기록을 보내지 않는다. + +- 기다린 뒤 기록을 실은 패킷 하나로 다시 시도한다. +- 기다림은 1초에서 시작해 거절될 때마다 두 배로 늘고, 64초에서 멈춘다. +- 시도한 패킷을 확인한 답에 REFUSED가 없으면 거절이 끝난다. +- STORED를 들어도 끝나며, 이때 기다림도 처음으로 돌아간다. +- 시도한 패킷보다 앞선 패킷들에 대한 REFUSED는 무시한다. + +**경로 MTU**(DPLPMTUD, RFC 8899). + +- 패킷이 가득 찬 적이 있고 RTT를 한 번 잰 뒤, 1,452 B짜리 PING(나머지는 PADDING)을 탐침으로 보낸다. +- 탐침이 확인되면 그 크기로 보낸다. +- 탐침을 잃으면 1초 뒤에 다시 보낸다. 세 번 잃으면 그다음은 10분 뒤다. +- 다음 둘 가운데 하나가 되면 1,200 B로 돌아가 1초 뒤에 다시 탐침한다. + - 작은 패킷만 확인되는 동안 큰 패킷을 연달아 3개 잃는다. + - 탐침 시간 초과(PTO)가 2번 연달아 난다. + +## 받는 쪽 + +**여는 순서.** + +1. 크기와 판을 본다. +2. 키 id가 같은 허용된 키 가운데 그 run을 아는 것부터, 다음에 모르는 것을 차례로 시도한다. +3. run마다 다음 에폭, 지금 에폭, 앞 에폭의 키를 머리의 에폭 비트가 맞을 때 시도한다. 그 run이 에폭 1 이상에 있고 에폭 + 비트가 0이면, 사슬을 다시 시작한 것일 수 있으니 에폭 0의 키도 시도한다. + +- 처음 보는 run은 에폭 0에서 시작한다. 그 run의 에폭을 기억해 두었다면 그 에폭에서 시작한다(아래 "메모"). +- 처음 보는 run의 키는 토큰이 있을 때만 만든다. 그 키로 열리지 않으면 토큰 하나를 쓴다. 토큰은 초당 256개 차고 256개까지 + 쌓인다(지역 선택). 그래서 꾸며 낸 패킷 폭주에 드는 HKDF에 상한이 있고, 열리는 보내는 쪽 천 개가 한꺼번에 깨어나도 토큰을 + 쓰지 않는다. +- run의 자리는 패킷이 열린 뒤에만 만든다. 위조한 패킷은 아무 자리도 밀어내지 못한다. +- 이미 받은 패킷 번호(구간 32개까지 기억)의 패킷은 ACK만 다시 하고 프레임은 처리하지 않는다. 그보다 오래된 번호는 기록의 + 들은 번호와 STORED의 "가장 큰 값" 규칙이 막는다. + +**주소.** + +- 답은 그 run에서 번호가 가장 큰 패킷이 온 곳으로 보낸다. 받은 주소(원격)와 도착한 자기 주소(로컬)에서 보낸다. +- 새 주소로는 CHALLENGE를 보낸다. 같은 값이 RESPONSE로 돌아오기 전까지, 그 주소로 보내는 답은 그 주소에서 받은 바이트의 3배를 + 넘지 않는다(RFC 9000 §8). +- 옛 패킷을 다시 보내도 주소는 움직이지 않는다. + +**답.** + +- 확인을 부르는 패킷을 받은 뒤의 다음 차례에 답 패킷 하나에 다음을 넣는다. + - CHALLENGE(확인 전) + - ACCEPT(다음 에폭이 쓰이기 전) + - ACK: 가장 큰 번호를 받은 뒤 지난 시간과 구간들 + - 그 run이 마지막으로 보낸 스트림마다 STORED + - REFUSED +- STORED는 저장이 끝났을 때에도 보낸다. + - 허가는 1024다. 받는 쪽이 그 스트림에서 16 MiB를 쥐고 있으면 1이다. + - 들은 번호 + 1024보다 큰 기록은 버린다. + - 들은 번호 이하의 기록이 다시 오면 STORED를 다시 보낸다. +- 받는 쪽은 들은 번호 다음부터 번호 순서로 온전한 기록을 앱에 넘긴다. 앱이 적용하고 저장한 뒤에만 STORED의 들은 번호를 올린다. + 틈에서 멈추고, 틈 뒤의 기록을 버렸으면 깃발 1을 세운다. + +**OFFER를 받아들임.** 다음 둘 가운데 하나일 때만 받아들인다. + +- 에폭 0의 패킷에 실린 에폭 1(사슬의 시작 또는 다시 시작) +- 지금 에폭 n의 패킷에 실린 n+1 + +받아들이는 방법과 제한은 다음과 같다. + +- 받는 쪽은 에폭 n의 키 쌍을 만들어 E(n)을 셈하고 ACCEPT를 보낸다. 그 에폭의 패킷이 처음 열릴 때까지 답마다 다시 넣는다. +- 같은 OFFER가 다시 오면 같은 ACCEPT를 보낸다. +- 한 피어에 새 에폭은 초당 한 번까지다. +- 지역 선택으로 다음 제한을 둔다. + - 기록과 함께 온 OFFER는 초당 256번(한꺼번에 8번)까지만 받아들인다. + - 받는 쪽 키 쌍은 1초 동안 그 초의 ACCEPT들이 함께 쓴다. + - X25519는 답을 보낸 뒤에 한다. +- 사슬을 다시 시작한 run에는 답도 에폭 0으로 돌아가 보낸다. + +**LOST.** 다음 조건을 모두 만족하면 LOST를 보낸다. + +- 처음 보는 run이다. +- 에폭 비트가 0이 아니다. +- 그 에폭을 모른다. 다시 시작하면서 메모를 잃었거나, 메모가 그 피어의 다른 run을 들고 있을 때다. +- 패킷이 46 B보다 크다. +- 초당 4,096번 이하다. + +LOST는 그 패킷의 번호를 담아 에폭 0의 키로 봉인한다. 답 run은 새로 뽑고, 패킷 번호는 0이다. 크기는 46 B로, 그것을 부른 +패킷보다 작다. QUIC의 stateless reset(RFC 9000 §10.3)과 같은 자리이지만, LOST는 두 노드의 정적 키로 봉인되어 경로 위의 +공격자가 만들 수 없다. + +**REFUSED.** STREAM을 받아들이지 않으면, 그 run의 다음 답에 그 스트림에 대한 REFUSED를 한 번 넣는다. + +**쉬는 피어.** 30초 동안 조용하고 쥔 것이 없는 피어는 run, 주소, 스트림을 놓는다(지역 선택). 다음 패킷이 다시 만든다. + +**메모.** 선 위의 일은 아니지만 재시작에 관계된다. 받는 쪽은 피어마다 S와, 그 피어의 run 하나에 대해 받아들인 에폭을 파일에 +적어 둘 수 있다. 다시 떠도 그 run은 비대칭 연산 없이 이어진다. 메모에 없는 run은 LOST를 받고 에폭을 다시 시작한다. + +## 수와 지역 선택 + +| 이름 | 값 | 성격 | +|---|---:|---| +| 판 0의 첫 바이트 | 0x70–0x7f | 명세 | +| 머리 / 태그 | 21 B / 16 B | 명세 | +| 첫 데이터그램 / 가장 큰 데이터그램 | 1,200 B / 1,452 B | 명세 | +| 이름 | 1–64 B | 명세 | +| 기록 | 16 MiB 이하 | 명세 | +| 허가의 상한(보내는 쪽이 따르는) | 65,536 | 명세 | +| ACCEPT의 되풀이 | 4 B | 명세 | +| 첫 허가(STORED 전) | 1,024 | 명세 | +| 새 주소의 증폭 한도 | 받은 바이트의 3배 | 명세 | +| LOST 크기 조건 | 부른 패킷 > 46 B | 명세 | +| 에폭 주기 | 1시간 또는 1 GiB 이하 | 상한만 명세 | +| 거절 뒤 기다림 | 1초부터 두 배, 64초까지 | 지역 선택 | +| 에폭을 잃었다고 볼 때 | 2초와 PTO 4번 | 지역 선택 | +| 받은 뒤 저장을 기다리는 시간 | 1초 | 지역 선택 | +| RTT 첫값, ACK 지연 상한, PTO 상한 | 100 ms, 25 ms, 1초 | 지역 선택 | +| 혼잡 제어 | CUBIC(RFC 9438, C 0.4, β 0.7), 첫 창 10 데이터그램, 페이싱, 잘못 본 손실은 되돌림 | 지역 선택(표준 알고리즘만) | +| 재정렬 인내 | 패킷 3–256개, 시간 RTT/8부터 최소 RTT의 1/4씩 RTT까지 | 지역 선택 | +| 키 만들기 / 에폭 수락 / LOST | 초당 256 / 256(한꺼번에 8) / 4,096 | 지역 선택 | +| 쉬는 피어 | 30초 | 지역 선택 | +| 피어당 run 자리 | 64까지 | 지역 선택 | + +## 오류와 알림 + +선 위의 알림은 둘이다. 둘 다 인증된다. + +- **LOST**: 받는 쪽이 그 run의 에폭을 모른다. +- **REFUSED**: 받는 쪽이 그 스트림을 받지 않는다. 이유 부호는 위와 같다. `link/link.c`는 이유를 운영자에게 한 줄로 알린다. + HTTP 전달이 받는 쪽의 거절을 알리는 것과 같은 모양이다. + +그 밖의 실패(열리지 않는 패킷, 허용되지 않은 키, 모르는 판)에는 답하지 않는다. 답하면 공격자에게 신호와 증폭을 준다. + +## 보안 성질 + +경로 위의 공격자에 대해서는 [098](../research/098-link-security.md)과 [099](../research/099-link-epochs.md)의 검사가 +`link/test-link.c`에 있다. + +- **바꾼 패킷**: 열리지 않는다. 그 run을 모르는 받는 쪽이 에폭 1 이상의 패킷에 보내는 LOST(그보다 작다) 말고는 답이 없다. +- **다시 보낸 패킷**: 기록은 한 번만 적용된다. ACK와 STORED는 가장 큰 값으로만 받는다. 주소는 움직이지 않는다. +- **위장**: 허용되지 않은 키나 source로는 아무것도 열리거나 전달되지 않는다. +- **폭주**: 모르는 run의 HKDF는 초당 256번, X25519는 피어마다 한 번(메모)이다. +- **나중에 두 노드의 키를 얻음**: 에폭 0의 패킷만 열린다. run의 첫 왕복과, LOST 뒤 다음 에폭이 받아들여지기 전까지가 에폭 0이다. + QUIC 0-RTT와 같은 한계다. + +알려진 한계: + +- 받는 쪽의 개인 키를 가진 이는 그 받는 쪽에게 어느 보내는 쪽으로든 봉인할 수 있다(Noise KK의 첫 메시지와 같은 KCI). 에폭은 + 이것을 바꾸지 않는다. 다만 다른 run의 에폭 안으로는 들어오지 못한다. +- 메모는 피어마다 run 하나의 에폭만 든다. 한 노드의 출력 여럿이 같은 노드로 가면, 받는 쪽이 다시 뜬 뒤나 30초 넘게 쉰 뒤에 + 나머지 run은 LOST를 받고 에폭 0에서 다시 시작한다. +- NAT 뒤에서 쉬는 기기에 먼저 보내는 일은 풀지 않는다. + +## 이 명세와 구현 + +- 구현은 `link/link-protocol.c`(상태, 소켓 없음)와 `link/link.c`(UDP, GSO/GRO, 스레드)다. +- 전송 코드는 C 3,097줄이다(프로토콜 2,510, UDP 587). 011의 한도는 5,000줄이다. +- 이 명세를 쓰면서 구현의 구멍 셋을 찾아 고쳤다. 셋 다 `link/test-link.c`에 검사가 있다. + - 받는 쪽이 스트림을 받지 않을 때 보내는 쪽이 아무 말도 듣지 못해 매초 기록을 다시 보냈다. REFUSED를 더했다. + - 보내는 쪽은 64 MiB까지의 기록을 받아 두었지만 받는 쪽은 16 MiB까지만 쥘 수 있었다. 그 사이 크기의 기록은 영원히 다시 + 갔다. 기록의 상한을 16 MiB로 맞췄다. + - 받는 쪽은 피어마다 run 자리를 둘만 두었다. 한 노드의 출력 셋 이상이 같은 노드로 가면 run들이 서로 자리를 밀어내어, 답이 + 다른 run으로 갔다. 살아 있는 run이 더 오면 자리를 늘린다. |