기술 요약: 단조 소거 코드

1. 문제 제기

전통적인 소거 코드 (예: 리드 - 솔로몬 (MDS) 코드) 는 임계값 실패 가정 하에 작동합니다. 이러한 시스템에서는 데이터를 $k$개의 조각으로 나누어 $n$개의 프래그먼트로 인코딩하며, 임의의 $k$개 프래그먼트만으로도 복구가 가능하도록 설계됩니다. 이 모델은 노드의 특정 신원 (identity) 에 관계없이 임의의 $k$개 노드 집합이 모두 동등하게 사용 가능하거나 실패할 것이라고 가정합니다.

그러나 현대의 분산 시스템, 특히 블록체인 및 암호화폐 (예: Stellar, XRP Ledger) 에서는 일반화된 실패 가정 또는 비잔틴 쿼럼 시스템을 활용합니다. 이러한 맥락에서 신뢰는 균일하지 않으며, 일부 노드는 다른 노드보다 더 신뢰할 수 있고, 실패 패턴은 완전히 무작위적인 것이 아니라 특정 노드 하위 집합에 의존합니다. 기존의 임계값 기반 코드는 상당한 오버헤드나 구조적 불일치 없이 이러한 임의의 신뢰 가정을 효율적으로 수용할 수 없습니다. 본 논문은 특정 노드 하위 집합 (접근 집합) 이 데이터 복구를 보장받되 다른 집합은 그렇지 않은 **임의의 단조 접근 구조 (arbitrary monotone access structures)**를 존중하는 소거 코드의 필요성을 다룹니다.

2. 방법론

본 논문은 노드 집합 $\mathcal{P}$에 대한 임의의 접근 구조 $\mathcal{A} \subseteq 2^{\mathcal{P}}$와 함께 작동하도록 설계된 고전적 소거 코드의 일반화인 **단조 소거 코드 (Monotone Erasure Codes)**를 소개합니다.

2.1 정의 및 형식화

• 단조 소거 코드: Encode 및 Decode 알고리즘으로 구성된 방식입니다. Encode는 파일 $f$를 프래그먼트 벡터 $(g_1, \dots, g_n)$로 매핑하며, 여기서 프래그먼트는 서로 다른 크기를 가질 수 있습니다. Decode는 접근 집합 $A \in \mathcal{A}$에 해당하는 임의의 프래그먼트 하위 집합으로부터 $f$를 복구합니다.
• 효율성: 오버헤드 $\beta = (\mu - \kappa) / \kappa$로 측정되며, 여기서 $\kappa$는 입력 파일 크기이고 $\mu$는 모든 프래그먼트의 총 크기입니다. 목표는 $\beta$를 최소화하는 것입니다.
• 선형 단조 소거 코드: 인코딩 및 디코딩이 유한체 $\mathbb{F}_q$ 위의 선형 연산인 특정 클래스입니다. 인코딩은 생성 행렬 $G$와 $G$의 열을 노드에 매핑하는 라벨링 함수 $\phi$로 정의됩니다. 해당 노드 집합에 대응하는 $G$의 부분 행렬이 풀 랭크 ($k$) 를 가지면 그 노드 집합은 충분합니다.

2.2 구성 접근법

본 논문은 이러한 코드를 구성하기 위한 세 가지 구별된 방법을 제시합니다.

1. 기본 구성 (비최적):

   • 접근 구조를 나타내는 단조 부울 공식 (Monotone Boolean Formula, MBF) 을 기반으로 합니다.
   • 알고리즘은 접근 트리를 재귀적으로 탐색합니다. AND 노드의 경우 파일을 청크로 분할하고, OR 노드의 경우 파일을 복제합니다.
   • 결과: 완전성을 보장하지만, 트리 구조 내의 중복 복제로 인해 종종 높은 오버헤드가 발생합니다.

2. 효율적인 선형 구성 (부분 최적):

   • 블록 단위 MDS 행렬을 구축하는 재귀 알고리즘을 사용합니다.
   • 크로네커 곱과 단위 행렬을 사용하여 차원을 정렬하면서, 임계값 연산자를 위한 반데르몽드 행렬들을 결합하여 인코딩 행렬을 구성합니다.
   • 결과: 계산적으로 효율적 (접근 트리의 크기에 대해 다항식) 이지만 최소 오버헤드를 보장하지는 않습니다.

3. 최적 선형 구성 (선형 프로그래밍을 통한):

   • 일반 사례: 노드에 할당된 프래그먼트 가중치의 합을 최소화하는 것을 목표로 하는 **선형 프로그래밍 문제 (LPP)**로 최적 프래그먼트 분포 찾기를 공식화합니다. 여기서 제약 조건은 모든 접근 집합이 기본 MDS 코드에서 유도된 최소 $k$개의 '기본' 프래그먼트를 보유해야 한다는 것입니다.
   • 분할 접근 구조: 특정 클래스의 구조 (계층적이며 각 노드가 MBF 에 정확히 한 번 나타나는 경우, 예: Stellar 의 신뢰 모델) 의 경우, 논문은 LPP 를 효율적으로 ($O(n^2)$) 해결하는 전용 재귀 알고리즘 (알고리즘 2) 을 제공합니다. 이 알고리즘은 오버헤드를 최소화하기 위해 포함하거나 제외할 하위 트리를 식별함으로써 기본 프래그먼트의 최적 할당을 효과적으로 결정합니다.

2.3 프로토콜 적용: GAVID

본 논문은 이러한 코드를 **일반 비동기 검증 가능 정보 분산 (General Asynchronous Verifiable Information Dispersal, GAVID)**이라는 분산 프로토콜에 통합합니다.

• 일반화: 임계값 시스템에서 일반 비잔틴 쿼럼 시스템으로 기존 AVID 프로토콜 (Cachin 및 Tessaro) 을 확장합니다.
• 메커니즘: 쿼럼 시스템의 커널 시스템을 단조 소거 코드의 접근 구조로 사용합니다.
• 핵심 개념: 비동기 환경에서 가용성과 일관성을 보장하기 위해 결함 있는 집합과 겹치지 않는 커널을 포함하는 집합인 **신뢰할 수 있는 집합 (Reliable Sets)**을 도입합니다.
• 최적화: 전체 검증 벡터를 Merkle 트리 루트로 대체하여 통신 복잡도를 줄이는 GAVID-H를 제안합니다.

3. 주요 기여

1. 단조 소거 코드의 정의: 임의의 단조 접근 구조로 고전적 소거 코드를 일반화하여 비균일 신뢰 가정을 허용하는 새로운 코딩 원시 (primitive) 를 공식적으로 정의합니다.
2. 구성 알고리즘:
   • 임의의 접근 구조에 대해 선형 단조 소거 코드를 구축하는 계산적으로 효율적인 방법을 제공합니다 (항상 오버헤드 측면에서 최적은 아님).
   • 접근 구조에서 유도된 선형 프로그래밍 문제를 해결함으로써 최적인 선형 단조 소거 코드를 구축하는 방법을 제공합니다.
3. 분할 접근 구조: 실제에서 흔히 발생하는 분할 접근 구조의 특정 사례를 분석하고, 이에 대한 최적 코드를 구축하는 효율적인 알고리즘을 제시하며 그 오버헤드를 특성화합니다.
4. GAVID 프로토콜: 임의의 쿼럼 시스템에 대해 통신 효율적인 비잔틴 신뢰 브로드캐스트를 달성하기 위해 단조 소거 코드를 활용하는 일반 비동기 검증 가능 정보 분산 프로토콜 (GAVID) 을 공식화합니다.

4. 결과 및 분석

• 오버헤드 상한: 최소 접근 집합 크기가 $\tau$인 일반 접근 구조의 경우, 최적 선형 단조 소거 코드의 오버헤드 $\beta$는 큰 $k$에 대해 $\beta \le (n - \tau)/\tau$로 제한됩니다. 이는 가장 작은 접근 집합이 전체 노드 수에 가까울 경우 오버헤드가 0 에 수렴함을 의미합니다.
• 분할 구성의 효율성: 분할 접근 구조를 위한 전용 알고리즘은 $O(n^2)$ 시간에 실행되며, 접근 집합의 수가 지수적일 때 일반적인 LPP 를 직접 해결하는 것보다 훨씬 빠릅니다.
• 프로토콜 복잡도:
  • GAVID Disperse: 메시지 복잡도 $O(n^2)$; 통신 복잡도 $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Merkle 최적화): 통신 복잡도를 $O(n(1+\beta)|f| + n^2(\log n)|H|)$로, 저장 복잡도를 $O((1+\beta)|f| + n(\log n)|H|)$로 줄입니다.
• 정확성: 단조 소거 코드가 시스템의 커널 구조에 대해 존재한다는 전제 하에, GAVID 가 임의의 비잔틴 쿼럼 시스템에 대해 종료성, 합의, 가용성 및 정확성 속성을 만족함을 논문에서 증명합니다.

5. 중요성 및 주장

본 논문은 단조 소거 코드가 신뢰 인식 분산 시스템을 위한 핵심 촉진제라고 주장합니다. 경직된 "임의의 $n$개 중 $k$개" 임계값 모델을 넘어선 이러한 코드는 시스템이 다음과 같은 것을 가능하게 합니다:

• 중복성 감소: 모든 노드를 동일하게 취급하는 대신 신뢰할 수 있는 노드에는 더 많은 데이터를, 위험한 노드에는 더 적은 데이터를 할당함으로써 저장 및 통신 오버헤드를 최적화합니다.
• 복잡한 신뢰 모델 지원: 신뢰가 계층적이고 비균일한 실제 블록체인 네트워크 (Stellar 등) 에서 발견되는 신뢰 가정을 직접 구현합니다.
• 프로토콜 일반화: 단순 임계값 모델뿐만 아니라 일반 비잔틴 쿼럼 시스템 하에서도 기존 효율적인 브로드캐스트 및 합의 프로토콜이 작동할 수 있도록 하는 기초 원시 (GAVID) 를 제공합니다.

저자들은 분할 구조에 대한 효율적인 구성을 제공하지만, 지수적으로 많은 집합을 가진 MBF 로 주어진 임의의 접근 구조에 대한 최적 단조 소거 코드 구성 문제는 여전히 열린 질문이라고 지적합니다. 또한 동적 코드 및 다른 코딩 이론 기법 (예: 레이트리스 코드) 의 적용에 대한 향후 연구를 제안합니다.