MIP-10

## 초록

이 MIP는 RaptorCast 전파 계층을 위한 새로운 방송 모드인 Deterministic RaptorCast (v1)를 제안합니다. 이는 공개적으로 유도 가능한 시드를 통해 Raptor 인코딩을 수정하고, 각 라운드에 대해 처음으로 유효한 (Merkle 루트, 리더 서명) 쌍을 기록하여 라운드별 모순 탐지를 시행합니다. 이를 ``EncodingCommitment``라고 합니다.

이 변경은 세 가지 이점을 제공합니다: (1) 검증된 청크를 수신한 후 인코딩 없이 검증자들이 Merkle 루트 약속에 직접 투표할 수 있게 하여, 중요한 경로에서 메시지 지연을 하나 절약할 수 있습니다; (2) 비잔틴 리더가 특정 검증자에게 단일 Encoding Symbol Identifiers (ESIs)를 선택적으로 withholding하여 발생하는 비대칭 생존 공격을 차단합니다. 이로 인해 수백 밀리초의 재구성 지연이 발생할 수 있습니다; (3) 여러 개의 서로 다른 페이로드를 인코딩하는 청크로부터 단일 Merkle 루트를 구성하는 혼합 약속 모순을 차단합니다. 이점 (3)은 Merkle 루트 약속에 투표하도록 합의 프로토콜이 수정되는 것에 달려 있습니다. 그 변경이 없으면 모순 공격 표면이 처음부터 발생하지 않습니다.

## 동기

MonadBFT는 RaptorCast를 사용하여 검증자 집합에 블록 제안을 전파합니다. 현재 프로토콜(v0) (자세한 내용은 [RaptorCast: Designing a Messaging Layer](https://www.category.xyz/blogs/raptorcast-designing-a-messaging-layer))은 리더가 Merkle 트리의 어떤 위치에 어떤 ESI를 할당하는지에 대한 제약이 없으며, 어떤 ESI가 어떤 검증자에게 전달되는지에 대한 제약도 없습니다. 이러한 전달 자유는 Deterministic RaptorCast가 해결하는 세 가지 결과를 초래합니다.

- **지연** 자연스러운 최적화는 블록 전파와 합의 투표를 겹치는 것입니다. 블록을 완전히 재구성하기를 기다리는 대신, 청크를 수신하고 블록의 Merkle 루트에 대해 검증할 수 있는 검증자는 즉시 투표할 수 있습니다—합의 중요한 경로에서 메시지 지연을 하나 절약합니다. 그러나 v0에서는 이것이 안전하지 않습니다. 리더가 ESI 할당에 대한 자유를 가지므로, 동일한 Merkle 루트가 여러 개의 서로 다른 페이로드와 일치할 수 있습니다. 따라서 루트에 대한 투표는 단일 블록을 명확하게 인증하지 않습니다. 표준화된(결정론적) 인코딩은 이러한 모호성을 제거합니다: Merkle 루트가 이제 정확히 하나의 가능한 페이로드에 대한 약속을 하므로, 검증자들이 검증된 청크를 수신하는 즉시 루트에 투표할 수 있는 기회를 제공합니다.

- **공격 1: 비대칭 생존** Raptor 코드는 디코더가 최소한 일부 정도-1 ([단일](https://www.category.xyz/blogs/raptorcast-designing-a-messaging-layer#2-encoding-system)) ESI를 수신할 때 가장 효율적으로 디코딩됩니다. 이러한 ESI는 Belief Propagation peeling decoder의 진입점입니다. 단일 ESI가 없으면 디코더는 즉시 정지하고 가우시안 소거법으로 되돌아가야 하며, 이는 상당히 더 비쌉니다. 비잔틴 리더는 v0의 전달 자유를 이용하여 특정 검증자에게 단일 ESI를 선택적으로 박탈하면서 적대적으로 선택된 고도수 복구 청크를 제공하여 가우시안 소거 비용을 극대화할 수 있습니다. 그 결과, 특정 검증자는 나머지 집합보다 수백 밀리초 더 늦게 재구성하게 됩니다(소스 기호의 수에 따라 다름). 이는 현재 뷰에서 투표를 고갈시키기에 충분한 지연입니다. 이는 리더에게 미래 뷰 실패를 강요할 수 있는 재량을 제공합니다.

- **공격 2: 혼합 약속 모순** 인코딩된 청크의 Merkle 루트에 투표하여 지연을 줄이는 것은 인코딩이 유효한지 확인하기 위해 디코드-재인코드 일관성 검사를 포함합니다. 고정된 ESI-위치 매핑이 없으면, 디코드-재인코드 일관성 검사를 무작위 코드에 대해 올바르게 정의할 수 없습니다. 리더는 여러 개의 서로 다른 페이로드의 인코딩에서 추출된 잎을 가진 단일 Merkle 루트를 구성할 수 있습니다. 모든 청크는 Merkle 검증을 통과하지만, 서로 다른 하위 집합을 수집하는 검증자는 서로 다른 페이로드로 디코딩됩니다. 검증자가 디코딩 없이 루트에 투표하면, 그들은 동일한 블록을 인증하고 있다고 믿지만 서로 다른 블록을 인증하고 있습니다.

## 사양

### 시드 유도

표준 시드(인코딩 시드라고도 함)는 제안 시 리더에 의해 계산됩니다. 이는 (라운드 번호, 리더 신원, 제안 시간)의 해시로 구성됩니다. 청크 헤더에는 검증자가 이 시드를 결정론적으로 재계산하는 데 필요한 모든 데이터가 포함되어 있으며, 검증자는 청크를 수신할 때 이를 수행합니다. 검증자는 또한 시드를 유효한 것으로 수용하기 전에 제안 시간이 자신의 로컬 시계의 허용 가능한 범위 내에 있는지 확인합니다.

### 인코딩

리더는 페이로드 `B`를 다음과 같이 인코딩합니다:

```
(c_1, ..., c_n) = RaptorEnc(B, seed)
R               = MerkleRoot(c_1, ..., c_n)
```

v0에서는 청크가 각각 `32` 청크로 구성된 여러 Merkle 트리로 조직되었으며, 각 트리는 리더에 의해 독립적으로 서명되었습니다. v1은 이를 모든 `n` 청크에 대해 계산된 단일 글로벌 Merkle 루트 `R`로 대체하여, 모든 청크를 제안의 단일 표준화된 인코딩에 바인딩하는 통합 약속을 제공합니다. Merkle 트리 깊이는 청크 수에 따라 동적으로 계산되며, 최대 깊이는 15입니다. 각 Merkle 증명은 `20 × (merkle_tree_depth - 1)` 바이트로, v0의 `100` 바이트에 비해 최악의 경우 증명 크기는 `280` 바이트입니다.

위치 `i`는 반드시 시드 하에 `ESI = i`로 생성된 청크를 포함해야 합니다. 쌍 `(R, σ)`에서 `σ = Sign(round, timestamp, R)`는 이 제안의 ``EncodingCommitment``입니다.

### 청크 검증

검증자는 v1 청크 패킷 `(round, timestamp, R, σ, i, π_i, c_i)`를 수용합니다. 검증자는 다음 모든 조건이 충족될 때만 청크를 수용합니다:

- **시의성** 패킷의 라운드는 허용된 라운드 창 내에 있으며, 타임스탬프는 검증자의 로컬 시계의 허용 가능한 범위 내에 있습니다.

- **리더 진위** `σ`는 라운드, 타임스탬프 및 `R`에 대한 유효한 리더 서명입니다 (`σ = Sign(round, timestamp, R)`).

- **인코딩 약속 일관성** `(R, σ)`는 이미 이 라운드에 대해 기록된 인코딩 약속과 일치합니다. 만약 약속이 아직 기록되지 않았다면, 검증자는 이 약속을 기록합니다.

- **청크 무결성** Merkle 증명 `π_i`는 `R`에 대해 인덱스 `i`에서 `c_i`를 검증합니다.

어떤 검사라도 실패한 청크는 조용히 삭제됩니다. 충돌하는 약속(동일한 라운드, 다른 `R` 또는 `σ`)은 모순 증거로 기록되며, 충돌하는 약속을 가진 청크는 삭제됩니다.

### 인코딩 검증 (디코드-재인코드 검사)

충분한 청크를 수집하고 페이로드 B를 디코딩한 후, 검증자는 반드시 다음을 검증해야 합니다:

```
MerkleRoot(RaptorEnc(B, seed)) == R
```

시드는 청크 헤더에 제공된 값으로부터 결정론적으로 재계산됩니다. 위 검사가 실패하면 페이로드는 거부됩니다. 이 검사는 v1에서 잘 정의되어 있습니다. 왜냐하면 시드가 ESI-위치 매핑을 고정하기 때문입니다: `B`를 재인코딩하면 항상 기록된 ``EncodingCommitment``에 대해 검증할 수 있는 동일한 청크 세트를 생성합니다. v0에서는 이 검사를 신뢰성 있게 적용할 수 없습니다.

## 근거

Deterministic RaptorCast는 기존 RaptorCast 인프라에 최소한의 변경만을 요구합니다. 인코딩 방식, Merkle 약속, 청크 전달 및 재전파는 모두 변경되지 않습니다. 추가 사항은 기존 제안 메타데이터에서 유도된 표준화된 시드와 각 검증자에서의 라운드별 모순 탐지입니다. 이러한 변경은 두 공격 표면을 모두 차단하고, 디코딩 전에 Merkle 루트 약속에 대한 투표를 안전하게 만들기에 충분합니다. 합의 투표 프로토콜, 쿼럼 증명 형식 또는 실행 계층에 대한 변경 없이 말입니다. 결과적으로 이 프로토콜은 다음 속성을 만족합니다.

### 속성

Deterministic RaptorCast는 다음 세 가지 속성을 만족합니다.

- **가용성** Merkle 루트 `R`에 대한 쿼럼 증명이 존재하면, 모든 올바른 검증자는 결국 종료됩니다.

- **무결성** 리더가 올바르다면, 페이로드를 디코딩하는 모든 올바른 검증자는 리더에 의해 원래 분산된 페이로드를 정확히 복구합니다.

- **일관성** 청크에서 `R`과 일치하는 페이로드를 디코딩하는 두 올바른 검증자는 동일한 페이로드를 복구합니다. 만약 유효한 페이로드가 `R`과 일치하지 않으면, 모든 올바른 검증자는 `⊥`를 반환합니다.

일관성은 디코딩 전에 `R`에 대한 투표를 안전하게 만드는 요소입니다. `R`에 투표하는 검증자는 암묵적으로 고유한 페이로드를 보증합니다: 일관성은 이후 디코딩하는 모든 검증자가 동일한 페이로드에 도달하도록 보장합니다. 이 속성이 없으면, 두 검증자가 서로 다른 페이로드로 디코딩되는 청크를 보유하면서 동일한 `R`에 투표할 수 있어 합의 안전성을 위반할 수 있습니다.

표준화된 시드는 또한 이전에는 적용할 수 없었던 실행 계층에서의 합의 후 유효성 게이트를 열어줍니다. 디코드-재인코드 검사가 모든 올바른 검증자에서 동일한 결과를 생성하기 때문에, 이는 합의가 블록을 결정한 후에 적용될 수 있습니다: 디코딩된 페이로드가 검사를 실패하는 블록은 모든 올바른 검증자에 의해 독립적으로 거부되며, 분할의 위험이 없습니다. v0에서는 표준화된 시드 없이 이 게이트를 사용할 수 없었습니다; 서로 다른 검증자가 동일한 페이로드를 재인코딩하면 서로 다른 루트를 생성하고 동일한 블록에 대한 서로 다른 결론에 도달할 수 있었습니다.

이는 두 가지 상호 보완적인 메커니즘에 의해 시행됩니다. 첫째, 라운드별 모순 탐지: 각 검증자는 라운드에 대한 첫 번째 유효한 v1 청크를 수신하면 ``EncodingCommitment``—쌍 (global_merkle_root, signature)—를 기록하고, 다른 필드를 가진 이후의 청크는 거부합니다. 둘째, 표준화된 시드는 ESI-위치 매핑을 고정하여 디코드-재인코드 검사를 잘 정의합니다: 공개 시드 하에 디코딩된 페이로드를 재인코딩하면 항상 동일한 청크 세트를 생성하며, 이는 동일한 ``EncodingCommitment``에 대해 검증할 수 있습니다.

## 보안 고려사항

이 MIP를 유도하는 공격인 비대칭 생존 및 혼합 약속 모순은 표준화된 시드와 라운드별 모순 탐지에 의해 차단됩니다.

- **시드 그라인딩** 시드 구성은 비잔틴 리더의 페이로드 그라인딩 이점을 허용된 창 내에서 무시할 수 있는 수준으로 제한합니다: 리더는 시간 버킷 내에서 유리한 정도 분포를 생성하는 시드를 선택하는 데 있어 무작위 기회보다 더 나은 성과를 낼 수 없습니다.

- **라운드 창** 허용된 라운드 창 외부의 청크는 조용히 삭제됩니다. 이는 무한 버퍼링을 방지하지만, 현재 라운드에서 상당히 뒤처진 노드는 따라잡을 때까지 자신의 창 외부의 라운드에 대한 청크를 수신하지 못하게 됩니다.

## 참조 구현
참조 구현은 [https://github.com/category-labs/monad-bft/pull/2811](https://github.com/category-labs/monad-bft/pull/2811)에서 확인할 수 있습니다.