Shamir's Secret Sharing vs MPC

· 5분 읽기

2019년, 캐나다 최대 암호화폐 거래소 QuadrigaCX의 창업자 Gerald Cotten이 갑작스럽게 사망했다.

그의 죽음과 함께 1억 9천만 달러 상당의 고객 자산에 대한 접근 권한도 영원히 사라졌다.

콜드월렛의 개인키를 오직 그만이 관리하고 있었기 때문이다.

이 처럼 Single Point of Failure은 재앙적 결과를 초래할 수 있다.

블록체인 기술의 핵심은 탈중앙화와 보안이지만, 정작 가장 중요한 개인키 관리는 오랫동안 중앙화된 방식에 의존해왔다.

하나의 시스템(혹은 장소, 혹은 사람)에 모든 권한이 집중되는 구조는 다양한 위협에 취약하다.

이러한 문제를 해결하기 위해 암호학자들은 비밀을 여러 조각으로 나누는 ‘비밀 분산(Secret Sharing)’ 기술을 개발했다.

그러나 SSS는 근본적인 한계를 가지고 있다: 비밀을 사용하려면 반드시 복원해야 하며, 그 순간 다시 단일 장애점이 발생한다.

Multi-Party Computation(MPC)과 Threshold Signature Scheme(TSS)은 비밀을 복원하지 않고도 암호화 작업을 수행할 수 있는 혁신적인 기술이다.

키가 한 곳에 절대 존재하지 않는 구조를 통해, MPC는 보안성과 가용성을 동시에 달성한다.

물론 현업에서 항상 MPC 를 사용하는 것은 또 아니고, SSS 도 여전히 많이 사용된다. 차이점에 대해서 알아보자.

Shamir’s Secret Sharing (SSS)

SSS의 핵심 아이디어는 간단하지만 강력하다.

n개의 조각을 생성하고, 그 중 임의의 t개 조각만 있으면 비밀을 복원할 수 있다.

이를 “t-of-n 임계치 구조(threshold scheme)“라고 부른다.

예를 들어, 5개 조각 중 3개만 있으면 복원 가능한 3-of-5 구조를 만들 수 있다.

SSS는 다항식 보간법의 특성을 활용한다. 기본 원리는 다음과 같다:

보간법은 알고 있는 데이터 지점(점)들을 기반으로, 그 사이의 비어있는 데이터 값을 추정하여 채워 넣는 수치 해석 기법이다.

  • 기본 정리: 서로 다른 t개의 점이 주어지면, 차수가 t-1 이하인 다항식을 유일하게 결정할 수 있다

  • 역으로: t-1개 이하의 점으로는 다항식에 대한 어떠한 정보도 얻을 수 없다

이게 무슨 말이냐면, 2개의 점이 있으면 직선이 딱 하나로 정해지지만, 점이 1개뿐이면 그 점을 지나는 직선이 무한히 많아서 어떤 직선인지 전혀 알 수 없는 것과 같다.

SSS는 이 원리를 확장하여, 비밀을 직선 대신 더 복잡한 곡선(다항식)의 y절편에 숨기고, 곡선을 특정하는 데 필요한 점의 개수를 임계치(t)로 설정하는 것이다.

SSS의 비밀 분할 과정은 다음 단계로 이루어진다.

  1. 비밀 설정: 비밀 s를 다항식의 상수항(a₀)으로 설정

  2. 다항식 생성: 차수 t-1인 랜덤 다항식 f(x) 생성

    • f(x) = a₀ + a₁x + a₂x² + … + a_(t-1)x^(t-1)

    • a₀ = s (비밀)

    • a₁, a₂, …, a_(t-1)은 랜덤하게 선택

  3. 조각 생성: n개의 서로 다른 x 값에서 다항식을 평가

    • Share₁ = (x₁, f(x₁))

    • Share₂ = (x₂, f(x₂))

    • …

    • Shareₙ = (xₙ, f(xₙ))

  4. 분배: 각 조각을 서로 다른 참여자 또는 위치에 분배

비밀을 복원하려면 t 개 이상의 조각을 수집하여 라그랑주 보간법 이라는 것을 적용한다.

참고로 필자도 이에 대해서 자세히 알지 못하므로 라그랑주 보간법에 대해서는 다루지 않습니다.

SSS의 한계

SSS 는 충분히 강력하지만,

  1. 복원 시 단일 장애지점이 부활

  2. 조각 상태에서 서명이나 암호화같은 작업은 불가능 (매번 복원 → 서명 → 재분할)

  3. 한 번 생성된 조각은 변경되지 않음 → 키 로테이션이 어려움

이것이 바로 MPC 가 등장한 배경이다.

Multi-Party Computation (MPC)

Multi-Party Computation(MPC)은 여러 참여자가 각자의 입력을 비밀로 유지하면서 공동으로 함수를 계산하는 암호학적 프로토콜이다.

암호화폐 맥락에서 MPC의 가장 중요한 응용은 Threshold Signature Scheme(TSS)이다.

TSS는 개인키를 복원하지 않고도 유효한 디지털 서명을 생성할 수 있게 한다.

SSS 의 한계를 극복 가능하다!

TSS (Threshold Signature Scheme)

Threshold Signature Scheme(TSS)은 MPC의 가장 중요한 응용이다.

알아보니 원래 다른 곳에서도 많이 쓰이는 용어라고 하니 알아두자

TSS 를 이해하기 위한 핵심 개념은 다음과 같다.

분산 키 생성 (DKG, Distributed Key Generate)

  • n개 노드가 협력하여 공개키/개인키 쌍을 생성

  • 각 노드는 개인키의 조각만 보유

  • 완전한 개인키는 어느 시점에도 어느 곳에도 존재하지 않음

  • 공개키는 모든 참여자가 동일하게 계산 가능

임계치 서명 생성

  • t개 이상의 노드가 협력하여 유효한 서명 생성

  • 각 노드는 자신의 조각만 사용하여 부분 서명 생성

  • 부분 서명들을 결합하여 최종 서명 완성

  • 최종 서명은 완전한 개인키로 서명한 것과 구별 불가

블록체인 관점에서 이렇게 생성된 서명은 일반 서명과 완전히 동일하다.

일단 개인키가 절대 재구성되지 않는다는 점이 매우 훌륭하다고 볼 수 있다.

물론 그 만큼 SSS 에 비해서 구현 난이도가 매우 높고, 키 로테이션 등을 구현하기 위해서는 분산 시스템에 대한 이해가 매우 필요하다.

MPC vs Multisig

MPC를 논할 때 빼놓을 수 없는 비교 대상이 Multisig(다중 서명)이다.

둘 다 임계치 보안을 제공하지만 근본적으로 다른 방식이다.

Multisig: 온체인 임계값

  • 여러 개의 독립적인 개인키 생성

  • 각 키로 별도의 서명 생성

MPC: 오프체인 임계값

  • 하나의 공개키, 분산된 개인키 조각

  • t개 노드가 협력하여 단일 서명 생성

References