Reed-Solomon(RS) 부호는 QR코드, 위성통신, SSD, CD 등 수많은 시스템에서 쓰이는 오류 정정 코드다.
이 글에서는 RS 부호가 어떻게 데이터를 보내고, 오류를 복원하며, ZK에서의 사용에 대해 다룬다.
리드-솔로몬의 기본 아이디어
RS 부호는 원래 메시지 데이터를 다항식으로 본다. 이 다항식을 여러 개의 x값에 대해 계산한 결과를 전송하며, 이 과정에서 여분의 정보(패리티)가 포함된다. 그 결과 일부 데이터가 손상돼도 복원이 가능하다.
메시지를 다항식으로 바꾸는 법
예를 들어, 원래 메시지가 [3, 1, 4]라는 3개의 숫자라고 하자.
RS 부호는 이것을 다음과 같은 2차 다항식으로 바꾼다.
M(x) = 3 + 1x + 4x²메시지의 각 숫자는 다항식의 계수가 된다.
전송 시에는 특정 x값을 넣어 계산한 y값들만 보낸다.
부호화 과정 (RS(7,3) 예시)
- 메시지 길이 (k): 3
- 코드워드 길이 (n): 7
- 정정 가능 오류 수 (t): (n - k)/2 = 2
원래 메시지
[3, 1, 4]다항식 정의
M(x) = 3 + 1x + 4x²x = 0 ~ 6 에 대해 평가 (mod 7)
| x | M(x) 계산 | 결과 (mod 7) |
|---|---|---|
| 0 | 3 + 0 + 0 = 3 | 3 |
| 1 | 3 + 1 + 4 = 8 → 1 | 1 |
| 2 | 3 + 2 + 4×4 = 21 → 0 | 0 |
| 3 | 3 + 3 + 4×9 = 42 → 0 | 0 |
| 4 | 3 + 4 + 4×16 = 71 → 1 | 1 |
| 5 | 3 + 5 + 4×25 = 108 → 3 | 3 |
| 6 | 3 + 6 + 4×36 = 153 → 6 | 6 |
최종 전송 코드워드:
[3, 1, 0, 0, 1, 3, 6]오류 발생 예시
통신 중 일부가 손상될 수 있다.
예:
[3, 6, 0, 0, 1, 0, 6] ← 원래 [3, 1, 0, 0, 1, 3, 6]여기서 2번째와 6번째 값이 바뀌었지만, RS(7,3)는 2개까지 오류를 정정할 수 있기 때문에 원래 메시지 [3,1,4]를 복원할 수 있다.
왜 메시지를 직접 안 보내는가?
| 방법 | 특징 | 오류 정정 가능? |
|---|---|---|
| 메시지 직접 전송 | 간단하지만 오류에 취약 | 불가능 |
| 다항식 기반 전송 | 일부 손실에도 복원 가능 | 가능 |
RS 부호는 메시지를 다항식으로 바꾼 뒤, 그 함수의 결과값들만 전송한다.
즉, 원래 메시지는 직접 전송되지 않는다. 일부 값이 손상돼도 수신자는 다항식 보간을 통해 원래 메시지를 복원할 수 있다.
복원 과정
복원은 수신된 y값 중 일부가 오류라고 가정하고, 이를 기반으로 원래의 다항식을 추정하는 것이다.
복원 방식 1: 보간 기반 복원
- 어떤 x값에 해당하는 y값이 정확한지 알고 있는 경우, 정상적인 k개 이상의 (x, y) 점을 가지고 라그랑주 보간법을 통해 다항식을 복원할 수 있다.
- 이 방법은 오류 위치를 알고 있는 경우(즉, erasure 복원)에 적합하다.
복원 방식 2: 신드롬 기반 복원 (실제 시스템 사용)
오류 위치를 모를 경우, 다음 절차를 따른다:
- 신드롬 계산: 수신된 값을 이용해 S₀, S₁, ..., S_{2t-1}까지의 신드롬 벡터를 계산한다.
- Berlekamp-Massey 알고리즘: 오류 위치 다항식(Locator Polynomial)을 계산한다.
- Chien Search: 오류 위치 다항식의 근을 찾아 실제 오류 위치를 찾는다.
- Forney 알고리즘: 오류 위치가 확인되면 해당 위치의 오류 값을 계산한다.
- 오류 보정: 계산된 오류 값을 원래 수신된 데이터에서 빼서 수정한다.
이 과정을 거치면 원래의 다항식을 정확히 복원할 수 있고, 다시 계수를 추출하여 메시지를 얻는다.
결론 요약
- 메시지를 다항식으로 변환하고, 그 다항식을 여러 x에 대해 평가한 y값을 전송한다.
- 수신자가 이 y값 중 일부만 올바르게 받으면, 다항식 보간 또는 신드롬 기반 알고리즘으로 원래 다항식을 복원할 수 있다.
- 통신 도중 오류가 발생하더라도, 이론적으로 (n - k)/2개까지 정정이 가능하다.
ZK에서의 사용
Reed-Solomon 부호는 Zero-Knowledge Proof(ZKP) 시스템, 특히 STARK에서 매우 중요한 역할을 한다. 이때 RS 부호는 오류 정정용이 아니라, 증명자가 보낸 정보가 저차수 다항식의 평가값으로 구성되었는지를 검증하기 위한 수학적 도구로 활용된다.
핵심 개념: Low-degree Test
ZK 시스템에서 증명자는 어떤 다항식의 성질(예: 회로의 계산이 맞았는지)을 증명하고자 한다. 이때 그 다항식이 정해진 최대 차수 이하인지를 확인하는 것이 중요한데, 바로 여기에 Reed-Solomon 코드가 쓰인다.
- 평가 벡터가 RS 코드워드와 일치할 경우 ->
해당 벡터는 저차수 다항식의 평가값이라는 뜻. - 즉, 증명자가 보낸 데이터가 RS 코드에 "가깝다"면 ->
저차수 다항식에서 유래했을 가능성이 높다는 것을 기반으로 한다.
** 근데 왜 해당차수 이해인지를 검증하는지는 잘 이해를 못했음. 차수가 높으면 거짓증명을 만들 수 있다는데 잘 이해가안감.
-> 차수제한이 없으면 아무점이든 통과하는 다항식을 만들 수 있다는게 이유라네
흠.
FRI와의 연결
FRI(Fast Reed-Solomon IOP of Proximity)는 STARK에서 Reed-Solomon 코드 기반의 low-degree proximity test를 수행하는 프로토콜이다. 여기서:
- Prover는 어떤 다항식의 평가값을 Merkle 트리에 커밋하고,
- Verifier는 무작위 위치를 추출해, 그것들이 RS 코드의 구조에 맞는지 검증한다.
이 과정을 통해 Prover가 거짓된 고차 다항식을 제시했을 가능성을 매우 낮게 만든다.
요약
| 전통적 RS 사용 | ZK에서의 RS 사용 |
|---|---|
| 통신 중 오류 복원 | 다항식이 낮은 차수임을 검증 |
| 손상된 데이터를 복구 | 증명자가 보낸 벡터가 RS 코드에 "가까운지" 검사 |
참고 용어
- 유한체 (Galois Field, GF): 유한한 원소만 가진 체. RS 부호는 주로 GF(2⁸)이나 GF(7) 위에서 동작한다.
- 다항식 보간: 여러 점을 지나는 다항식을 계산하는 기법. (예: 라그랑주 보간법)
- 신드롬 기반 복원: 오류 위치와 값을 신드롬을 통해 추정하는 복구 방법.
참고링크
Reed–Solomon error correction
Reed-Solomon 이란?
FRI-based Polynomial Commitments
and Fiat-Shamir.pdf
