기술 요약: 스플릿 탈리(Split Tallies): 동적 순서 집합의 감사를 위한 이산 증명 계산법

문제 정의

본 논문은 관리자(maintainer)가 유지하고 소비자(consumer)가 쿼리를 보내는 **동적 순서 집합(dynamic ordered sets)**의 검증 문제를 다룹니다. 현대의 많은 컴퓨팅 시나리오에서 데이터 구조는 신뢰할 수 없는 환경(예: 원격 서비스, 불투명한 하드웨어 가속기 또는 조달된 라이브러리)에 존재합니다. 소비자는 연산(삽입, 삭제, 멤버십 테스트, 전구체/후구체 쿼리, 극값 쿼리)을 수행하고 그 결과에 즉시 반응하며 지연 없이 동작합니다.

핵심 과제는 소비자가 데이터 구조 자체를 저장하거나 연산을 재실행하지 않고도 전체 연산 이력에 대한 **정확성 증명(certificate of correctness)**을 제공하는 것입니다. 감사자(auditor)는 오직 상수량의 상태(구체적으로 5개의 머신 워드와 1개의 플래그)만을 저장하는 수동적(passive) 상태여야 합니다. 관리자는 모든 연산마다 '탈리(tally)'라고 불리는 공공의 추가 가능(append-only) 시퀀스에 짧은 '노치(notch, 기록)'를 추가해야 합니다. 목표는 관리자가 무한한 계산 능력을 보유하고 가시적인 이력에 따라 전략을 조정하더라도, 관리자가 잘못된 답을 제공했을 가능성을 높은 확률로 탐지하는 것입니다.

방법론

제안된 솔루션인 **스플릿 탈리(Split Tallies)**는 역사적인 나무 탈리 스틱(wooden tally sticks)에서 영감을 얻었습니다. 과거에는 부채를 기록하기 위해 나무 막대에 홈(notch)을 판 뒤, 이를 길이 방향으로 쪼개어 기록했습니다. 채권자는 '스톡(stock)'을 갖고 채무자는 '포일(foil)'을 가졌으며, 결산 시 두 부분을 맞물려 진위 여부를 확인했습니다. 이 디지털 맥락에서는 다음과 같습니다:

• 탈리(The Tally): 관리자가 추가하는 공공의 노치 스트림.
• 스톡(The Stock): 감사자의 개인 상태(5개의 워드와 1개의 플래그).
• 포일(The Foil): 관리자의 내부 장부.
• 감사(The Audit): 세션 종료 시 스톡을 포일과 맞물려(mesh) 검증하는 과정.

갭 계산법 (The Gap Calculus)

이 제안된 솔루션의 기술적 핵심은 **이산 갭 계산법(discrete calculus of gaps)**입니다. 시스템은 집합 $S$를 직접 감사하는 대신, 전체 유니버스를 분할하는 **최대 빈 간격(maximal vacant intervals, gaps)**들의 가문을 감사합니다.

• 표현: 유니버스 $\{1, \dots, U\}$ 상의 집합 $S$는 $0$과$U+1$ 사이를 연결하는 **맞물린 체인(interlocking chain)**인 갭 $\langle a, b \rangle$들로 유일하게 표현됩니다.
• 정규형(Normal Form): 본 논문은 이 갭 가문이 구간 무방향 그래프(interval acyclic graph)에서 $0$에서$U+1$까지 이어지는 유일한 단위 경로(unit path)에 대응함을 증명합니다.
• 재작성(Rewrites): 연산은 이 경로의 국소적 재작성으로 모델링됩니다:
  • 삽입(Insertion): 하나의 갭 $\langle a, b \rangle$를 두 개의 갭 $\langle a, x \rangle, \langle x, b \rangle$로 분할합니다.
  • 삭제(Deletion): 인접한 두 갭 $\langle a, x \rangle, \langle x, b \rangle$를 하나의 갭 $\langle a, b \rangle$로 병합합니다.
  • 쿼리(Queries): 특정 갭(예: $x$를 포함하는 갭, 또는 $x$의 전구체가 되는 갭)을 제시함으로써 답변됩니다.

인덴처 규율 (The Indenture Discipline)

상태를 저장하지 않고 이러한 재작성을 감사하기 위해, 감사자는 유한체 $\mathbb{F}_p$ 상의 다항식 항등 검사(polynomial identity testing)에 기반한 핑거프린팅 메커니즘을 사용합니다.

1. 코드와 타임스탬프: 모든 갭의 탄생은 공용 카운터 $\kappa$를 통해 고유한 코드(타임스탬프)를 할당받습니다.
2. 인용(Citations): 모든 연산은 소비되는 갭(재작성되는 갭)의 코드를 반드시 인용해야 합니다.
3. 누산기(Accumulators): 감사자는 두 개의 누산기 $A$(탄생용)와 $R$(소비용)을 유지합니다. 갭의 코드 $c$와 양 끝점 $a, b$에 대해, 값 $\nu(a, b, c)$는 필드로 매핑됩니다.
   • 탄생 시: $A \leftarrow A \cdot (z - \nu(a, b, c))$
   • 소비 시: $R \leftarrow R \cdot (z - \nu(a, b, c))$
   • 여기서 $z$는 감사자가 세션 시작 전 선택하는 비밀 필드 요소입니다.
4. 검증: 감사 시, 관리자는 현재 갭들과 그 코드들을 공개합니다. 감사자는 공개된 갭들이 유효한 체인을 형성하는지 확인하고, $A = R$인지 검증합니다.

주요 메커니즘

• 시간적 규칙(Temporal Rule): 인용된 코드는 이벤트 시작 시점의 카운터 값보다 엄격히 작아야 합니다. 이는 관리자가 균형 잡힌 장부를 위조하기 위해 미래의 코드를 '빌려오는' 것을 방지합니다.
• 강제성(Forcing): 갭 경로의 유일성 덕분에, 어떤 쿼리에 대한 올바른 답은 인용된 갭의 속성에 의해 강제되는 함수입니다. 만약 관리자가 존재하지 않거나 활성화되지 않은 갭을 인용하면, 답이 갭의 속성과 일치하지 않거나 장부의 균형이 깨지게 됩니다.

주요 기여 및 결과

1. 감사 정리 (건전성 및 완전성)

본 논문은 이 체계가 완벽한 완전성(perfectly complete)(정직한 관리자는 항상 수용됨)과 **$\epsilon$-건전성($\epsilon$-soundness)**을 갖추었음을 입증합니다.

• 건전성 오류(Soundness Error): $T$번의 연산 중 관리자가 단 한 번이라도 잘못된 답을 제공할 경우, 수용될 확률은 최대 $(4T + 1)/p$입니다.
• 파라미터: 61비트 소수 $p$(예: $2^{61}-1$)를 사용할 때, 최대 100만 회의 연산이 있는 세션에서 오류 확률은 $2^{-38}$ 미만입니다.
• 가정: 무제한의 계산 능력을 가진 적대자에 대해서도 정보 이론적 보안을 제공하며, 별도의 계산적 어려움 가정(computational hardness assumptions)이 필요하지 않습니다.

2. 불가능성 및 필연성 결과

본 논문은 특정 설계 선택이 필수적임을 증명합니다:

• 결정론적 바닥(Deterministic Floor): 크기가 $n$인 집합에 대해 세션 종료 시 건전성을 보장하는 임의의 결정론적 감사자는 최소 $2n - \log_2(2n+1)$ 비트의 상태를 저장해야 합니다. 이는 무작위성(randomness)이 편의가 아닌 필수 요건임을 증명합니다.
• 비밀 무작위성(Secret Randomness): 감사자의 난수가 관리자에게 노출될 경우, 건전성 오류는 1이 됩니다(관리자가 항상 위조된 기록을 만들 수 있음). 따라서 평가 지점 $z$의 비밀 유지는 필수적입니다.
• 시간적 규칙의 필연성: 미래의 코드를 인용하는 것을 방지하는 규칙이 없다면, 정확한 균형을 맞추고 확률 1로 수용되는 명시적인 3단계 연산 위조가 가능해집니다.

3. 관리자 구현

본 논문은 리프 지향(leaf-oriented) (2, 4)-트리를 사용하는 구체적인 구현을 제공합니다.

• 복잡도: 연산은 최악의 경우 $O(\log n)$의 시간을 소요합니다.
• 오버헤드: 이 구조는 각 요소당 갭 코드를 저장하기 위한 단 하나의 추가 워드만을 필요로 합니다.
• 감사된 재구조화(Audited Rebalancing): 본 논문은 $m$번의 업데이트 동안 발생하는 구조적 이벤트(분할, 융합, 공유)의 수가 최대 $2m$임을 증명하는 **증명 envelopes(attestation envelope)**를 도입합니다. 이 경계는 관리자가 추가하는 1-워드 증명을 통해 감사자에 의해 인증되며, 이를 통해 분할 분석(amortized analysis)을 공공적으로 검증 가능한 주장으로 전환합니다.

4. 체크포인트 및 에포크(Epochs)

프로토콜은 임의의 체크포인트를 지원합니다. 감사는 언제든 수행될 수 있으며, 수용된 에포크는 가산적 오류 범위를 가지며 체이닝될 수 있습니다. 이를 통해 탐지 지연 시간을 조정할 수 있습니다(예: 높은 보안을 위해 매 연산 후 감사하거나, 효율성을 위해 더 드물게 감사함).

의의 및 범위

본 논문은 동적 순서 집합에 대한 상수 메모리 감사의 **종결된 계정(closed account)**을 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

• 패러다임의 전환: "고립된 테스트"에서 "실행과 함께 이동하는 인증"으로의 이동.
• 정보 이론적 보장: 머클 트리(Merkle trees)나 디지털 서명과 같은 암호학적 가정을 사용하지 않고, 다항식의 대수적 성질과 순서 집합의 조합론적 구조에 의존하여 검증을 달성합니다.
• 타이트한 하한선(Tight Lower Bounds): 결정론적 솔루션은 선형 공간을 요구하고 무작위성은 숨겨져야 함을 증명함으로써, 제안된 상수 메모리 솔루션이 최적에 가깝다는 것을 보여줍니다.
• 명시적 상수: 모든 파라미터(소수 크기, 워드 수, 오류 경계)는 명시적이며 실용적 사용(예: 64비트 워드에 적합하도록)을 위해 정밀하게 조정되었습니다.

범위는 엄격하게 7가지 연산 인터페이스(삽isaert, 삭제, 멤버십, 전구체, 후구체, 최솟값, 최댓값)로 제한됩니다. 본 논문은 갭 계산법이 배열(arrangement)(인접성, 브래케팅, 극값)은 인증하지만, 단일 갭에 국한되지 않는 랭크(rank)와 같은 집계 속성은 인증하지 못함을 명시합니다. 탐지는 **회고적(retrospective)**입니다. 본 논문은 이 정보 이론적 설정에서 온라인 탐지(답을 즉시 거부하는 것)가 일방향 함수의 존재와 연결된 알려진 프런티어임을 인정하며, 제안된 솔루션이 정의된 회고적 모델 내에서 최적임을 밝힙니다.