제III부: 암호학 연구의 기초¶
Sibuna의 두 작업 증명 계층에 깔린 비용 모델을 유도하고, Cohen-Pietrzak 순차 작업 증명과 그 보안 논증을 제시하며, 챌린지와 세션에 키 기반 해시 인증을 쓰는 근거를 밝힙니다. 가정과 참고 문헌은 SID 0006에 기록되어 있습니다.
Hashcash: 첫 번째 계층의 수학¶
정의와 비용¶
챌린지 문자열 \(C\)와 난이도 \(b\)비트에 대한 Sibuna의 첫 번째 계층 퍼즐은 다음과 같습니다. \(\text{SHA-256}(C \parallel \text{":"} \parallel \mathrm{dec}(N))\)의 선행 0비트가 \(b\)개가 되는 \(N \in \mathbb{N}\)을 찾습니다. nonce를 십진수로 표기한 것은 의도적인 선택입니다. 그러면 이진 인코딩 단계 없이도 WebAssembly 솔버, JavaScript 대체 솔버, 네이티브 검증자 사이에서 전송 형식이 똑같이 유지됩니다.
난이도의 단위는 압축 함수 호출이 아니라 기대 해시 시행입니다. 입력 하나가 SHA-256 블록 여러 개를 차지할 수 있습니다. 접두사를 미리 계산하면 nonce당 작업량이 달라질 수도 있습니다. 전송 규칙은 여전히 다이제스트에 대한 술어입니다. 구현 사이에서 일치해야 하는 것은 추정한 CPU 비용이 아니라 명제와 nonce 인코딩입니다.
독립적인 이상적 다이제스트에서 시행 횟수 \(X\)는 \(p = 2^{-b}\)인 기하 분포를 따릅니다. 중앙값은 \(\left\lceil \ln(1/2) / \ln(1-p) \right\rceil\)로, 작은 \(p\)에서는 약 \(2^b \ln 2\)이고, 분산은 \((1-p)/p^2\)입니다. 검증자는 탐색을 수행하지 않고 후보 다이제스트 하나를 확인합니다. 파싱, 챌린지 인증, 지문 확인, 사용 완료 상태 삽입, 응답은 추가 작업입니다. 기본 연산 하나의 측정 시간을 역산해 서버가 견딜 수 있는 폭주 트래픽 용량을 구할 수는 없습니다.
탐색의 두 가지 한계¶
첫째는 분산입니다. 탐색이 오래 걸린다고 워커가 고장 난 것은 아닙니다. 둘째는 병렬성입니다. 독립적인 nonce 시행은 동시에 실행할 수 있습니다. 기대 총 시행 횟수가 같아도 코어가 많으면 탐색의 경과 시간이 줄어듭니다. 그래서 요청 허용 정책에서는 하드웨어 처리량이 중요합니다. 누군가 내세우는 해시율이나 벤치마크 하나로는 모든 요청자의 이점에 상한을 둘 수 없습니다.
순차 작업 증명: 두 번째 계층¶
순차 작업을 쓰는 이유¶
순차 작업 구성은 계산 사이에 의존성을 둡니다. 나중 라벨을 계산하려면 앞서 만든 값이 필요합니다. 이 구성이 다루는 양은 총 작업량이 아니라 계산의 깊이입니다. 독립적인 퍼즐은 여전히 병렬로 실행할 수 있고, 하드웨어의 해시 지연 시간도 여전히 중요합니다.
Sibuna는 Cohen과 Pietrzak가 설명한 해시 기반 구성을 따릅니다. 깊이 \(n\)에서 그래프에는 라벨이 \(2^{n+1}-1\)개 있지만, 라벨 수가 고정되었다고 브라우저 지연 시간이 결정되는 것은 아닙니다. 라벨은 압축 블록 여러 개에 걸칠 수 있고, 개방은 부분 트리를 다시 계산할 수 있으며, 스케줄링은 변동을 더합니다. 오라클 모델 분석에서 얻은 보안 명제를 모든 구체적인 구현이나 공격자에 대한 무조건적인 주장으로 바꾸어서는 안 됩니다.
구성¶
깊이를 \(n\)이라 하고, 길이가 \(n\) 이하인 이진 문자열로 이름 붙인 노드로 이루어진 완전 이진 트리를 생각해 봅시다(루트 \(\varepsilon\), 자식 \(v0\)와 \(v1\), 길이 \(n\)의 잎). 각 노드 \(v\)에는 32바이트 라벨 \(\ell_v = H(\chi, v, \mathrm{parents}(v))\)가 붙습니다. 여기서 \(\chi\)는 챌린지 명제이고, \(H\)는 \(\chi\)를 한 번 흡수한 SHA-256입니다(Hashcash 솔버와 같은 접두사 기법).
- 내부 노드는 두 자식을 해시합니다: \(\ell_v = H(\chi, v, \ell_{v0}, \ell_{v1})\).
- 잎 \(u = u_1 \dots u_n\)은 루트 경로가 오른쪽으로 꺾인 곳마다 조상의 왼쪽 형제를 해시합니다: \(\ell_u = H(\chi, u, \{\ell_{u_1 \dots u_{i-1} 0} : u_i = 1\})\).
계산을 순차적으로 만드는 것은 왼쪽 형제 간선입니다. 잎 \(u\)는 그 왼쪽의 모든 부분 트리가 완성되기 전까지 라벨을 붙일 수 없으므로, 깊이 우선 후위 순회가 강제되고 루트 라벨 \(\varphi = \ell_\varepsilon\)은 \(2^{n+1} - 1\)개의 라벨 전체에 순서대로 의존합니다.
개방. \(\varphi\)를 계산한 뒤 증명자는 Fiat-Shamir로 잎 \(t\)개 \(\gamma_i = H(\chi \parallel \varphi \parallel i) \bmod 2^n\)을 도출하고, 각 잎에 대해 잎 라벨과 루트 경로를 따라 놓인 형제 라벨 \(n\)개를 보냅니다. 검증자는 잎의 부모인 형제들로 잎을 다시 계산하고, 경로를 따라 위로 해시하며, \(\varphi\)에 도달하는지 확인합니다. 검증자의 비용은 제한된 작업 공간에서 라벨 계산 \(O(tn)\)번입니다. 라벨 계산 하나가 해시 블록 여러 개에 걸칠 수 있으므로, 라벨 수를 세는 것은 압축 호출 수를 세는 것과 다릅니다.
fn verify_opening(base: &Sha256, n: u8, phi: &Label, gamma: u32, opening: &[Label]) -> bool {
let Some((leaf, siblings)) = opening.split_first() else {
return false;
};
// `siblings`는 깊이 n에서 깊이 1 순서이므로, 뒤집으면 깊이 1..=n과 짝이 맞습니다.
let mut hasher = node_hasher(base, n, gamma);
for (d, sibling) in (1..=n).zip(siblings.iter().rev()) {
if turns_right(gamma, n, d) {
hasher.update(sibling);
}
}
if hasher.finalize() != *leaf {
return false;
}
let mut current = *leaf;
for (d, sibling) in (1..=n).rev().zip(siblings) {
let mut parent = node_hasher(base, d - 1, gamma >> (n - d + 1));
if turns_right(gamma, n, d) {
parent.update(sibling);
parent.update(¤t);
} else {
parent.update(¤t);
parent.update(sibling);
}
current = parent.finalize();
}
current == *phi
}
표본 추출, 건전성, 그 한계¶
독립적으로 탐지할 수 있는 나쁜 비율 \(\alpha\)를 가진 고정된 커밋먼트를 생각합니다. 각 개방이 균등하고 독립적으로 표본을 뽑는다면, 개방 \(t\)번에서 나쁜 위치를 모두 놓칠 확률은 \((1-\alpha)^t\)입니다. 이 기초 계산은 개방이 많을수록 도움이 되는 이유를 설명합니다. 그러나 이것만으로는 순차 작업 프로토콜의 보안 증명이 되지 않습니다.
참고한 순차 작업 구성에는 오라클 모델에서의 보안 분석이 있습니다. Sibuna의 도메인 분리, 매개변수 대응, 절단, 구현은 여전히 그 구성의 가정에 비추어 확인해야 합니다. Fiat-Shamir 표본 추출은 개방을 커밋먼트로부터 재현할 수 있게 합니다. 재현 가능성만으로는 그라인딩(grinding) 공격에 대한 저항이 증명되지 않습니다. 우리는 속임수가 결코 더 싸지 않다고 무조건 주장하지는 않습니다.
증명자의 메모리¶
단순한 증명자는 모든 라벨(\(2^{n+1} - 1\)개)을 저장합니다. Sibuna의 증명자는 첫 번째 패스 동안 현재 경로의 왼쪽 형제 라벨 스택(라벨 \(n + 1\)개)을 유지하고, 상위 \(m = \min(n, 10)\)개 레벨(라벨 \(2^{m+1} - 1\)개, 최대 64 KB)만 보관합니다. 잎을 개방하려면 그 잎의 깊이 \(m\) 조상의 부분 트리를 다시 계산하는데, 이는 해시 \(2^{n-m+1} - 1\)번이며 보관한 레벨로 스택을 채워 시작합니다. 증명자의 총비용은 해시 \(2^{n+1} - 1 + t\,(2^{n-m+1} - 1)\)번이고, 출력 증명을 포함한 작업 공간 전체가 100 KB 미만입니다. 브라우저 탭과 네이티브 테스트는 같은 Workspace 타입(sibuna_pow::posw::Workspace)을 공유합니다.
매개변수는 시간이 아닙니다¶
Sibuna는 작업 비트를 \(n = b - 3\)으로 깊이에 대응시키고, 지원 구간 \([4, 24]\)로 제한합니다. 이는 작업 규모에 관한 관례이며, 알고리즘 사이에 실제 경과 시간이 같다는 보장이 아닙니다. 잎 하나는 부모 라벨 여러 개를 해시할 수 있지만, Hashcash는 nonce를 반복해서 시험합니다. 컴파일러, 브라우저, 프로세서, 매개변수 선택이 모두 상대 비용에 영향을 줍니다. 커밋된 기본 연산 벤치마크는 검증을 측정하며, 브라우저 풀이 지연 시간을 입증하지는 않습니다.
증명 크기는 \(32(1 + t(n+1))\)바이트입니다. 깊이 13에 개방 16개이면 \(32(1 + 16 \times 14) = 7200\)바이트입니다. 트리를 만드는 주된 비용이 그대로여도, 개방 수를 늘리면 증명과 검증자의 작업이 모두 늘어납니다.
구성 선택하기¶
의미 있는 비교는 알고리즘의 평판이 아니라 자원 예산입니다. 증명자의 메모리, 검증자의 최악의 경우 작업량, 증명 바이트 수, 주장하는 속성에 필요한 가정을 기록하세요. 메모리 하드 탐색은 쓸모가 있을 수 있지만, 비싼 작업을 반복해야 하는 검증자는 공격자에게 서버 자원을 소모시킬 또 다른 지점을 줍니다. 공개 검증 가능한 지연 구성은 공유 비밀 기반 게이트와는 다른 신뢰 모델에 쓰입니다.
Sibuna는 값싼 해시 검증과 해시 기반 순차 작업 선택지를 유지합니다. 후자는 증명 바이트가 더 많고 매개변수 분석도 더 신중해야 합니다. 어느 쪽을 택하든, 비싼 검증에 들어가기 전에 형식이 잘못된 증명을 거부해야 한다는 점은 변하지 않습니다.
대칭 인증: 챌린지와 세션¶
발급자가 곧 검증자¶
디지털 서명은 공개 키를 가진 누구나 검증할 수 있게 하므로, 검증자가 토큰을 발급할 수 없어야 할 때 알맞은 도구입니다. Sibuna의 검증자는 발급자 자신입니다(또는 시드 하나를 공유하는 클러스터입니다). 의사 난수 함수로 만든 메시지 인증 코드는 그 신뢰 도메인 안에서 인증을 제공합니다. 공개 검증은 제공하지 않습니다. MAC 키를 가진 사람은 누구나 토큰을 발급할 수도 있습니다. 벤치마크 장은 구현된 토큰 연산을 비교합니다.
장기적으로는 두 번째 결과가 중요합니다. Ed25519는 타원 곡선 군의 이산 로그에 기대는데, Shor 알고리즘이 이를 깨뜨립니다. 키 기반 해시는 해시 함수에만 기대며, 양자 알고리즘은 해시 함수에 대해 기껏해야 이차 속도 향상만 줍니다. Sibuna는 토큰을 발급할 수 없는 검증자가 필요한 배포를 위해 Ed25519를 선택지(--token-scheme ed25519)로 유지합니다.
키 스케줄¶
32바이트 마스터 시드 하나(--secret-file, SIBUNA_SECRET, 또는 새로 만든 무작위 값)에서 키 기반 BLAKE3와 도메인 문자열로 모든 용도별 키를 도출합니다. 토큰 키, 챌린지 키, Ed25519 키, 지문 키, 그리고 요구 티켓을 봉인하는 요구 키입니다(제IV부).
pub fn derive(seed: &Seed) -> Keys {
Keys {
token: subkey(seed, "sibuna/token/v1"),
challenge: subkey(seed, "sibuna/challenge/v1"),
ed25519_seed: subkey(seed, "sibuna/ed25519/v1"),
fingerprint: subkey(seed, "sibuna/fingerprint/v1"),
requirement: subkey(seed, "sibuna/requirement/v1"),
}
}
fn subkey(seed: &Seed, purpose: &str) -> [u8; 32] {
blake3::keyed_hash(seed.as_bytes(), purpose.as_bytes())
}
클러스터에서는 Keys::bind_node가 챌린지 키를 바꿉니다. 새 키는 기존 챌린지 키로 sibuna/challenge-node/v1과 노드 id를 키 기반 BLAKE3로 해시한 값입니다. 그래서 챌린지는 발급한 노드로 돌아와야 하지만, 세션 토큰과 요구 티켓은 모든 구성원에서 유효합니다.
도메인 분리는 한 키가 실수로 여러 용도에 재사용되는 일을 막습니다. 마스터 시드가 노출되면 도출된 모든 키가 노출됩니다. 클러스터는 시드 하나에만 합의하면 됩니다.
상태 없는 챌린지¶
챌린지 식별자는 스스로를 인증하는 레코드입니다. 버전, 알고리즘, 난이도, 개방 수, 발급 시각, 클라이언트의 키 기반 지문, PRF로 도출한 nonce, 챌린지를 요구한 정책 규칙의 해시가 차례로 오고, 그 뒤에 챌린지 키로 만든 16바이트 태그가 붙습니다. 발급할 때는 아무것도 쓰지 않습니다. 검증은 레코드를 디코딩하고, 태그를 상수 시간에 확인하고, 경과 시간을 챌린지 TTL과 비교하고, 지문을 제출한 클라이언트와 비교한 다음에야 증명을 살펴봅니다.
사용 완료 집합은 16바이트 태그를 담는 Robin Hood 개방 주소법 샤드 16개입니다(제V부). 지문은 클라이언트 주소와 User-Agent의 키 기반 해시입니다. 길이를 붙여 구분하므로 이어 붙여도 서로 다른 두 입력이 충돌하지 않으며, 키를 쓰므로 다른 클라이언트의 지문을 오프라인으로 계산할 수 없습니다.