💻 computer science

Secret Quorums: Protecting Byzantine Protocols Against Adaptive Adversaries

이 논문은 새로운 StealthDust 결제 프로토콜을 통해 입증된 바와 같이, 통신 오버헤드를 증가시키지 않으면서도 적응형 공격자(adaptive adversaries)에 대해 회복력을 유지하는 작고 익명화된 검증자 서브셋을 위원회 기반 프로토콜이 활용할 수 있도록 링 검증 가능한 랜덤 함수(ring verifiable random functions)를 활용한 새로운 추상화인 "Secret Quorums"를 소개한다.

원저자: Maxence Perion, Sara Tucci-Piergiovanni, Rida Bazzi

게시일 2026-07-23

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Maxence Perion, Sara Tucci-Piergiovanni, Rida Bazzi

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

돈이 주머니 속의 물리적인 동전이 아니라, 모두가 동의하는 공유된 마법 같은 장부인 디지털 세상을 상상해 보세요. 이것은 분산 시스템과 블록체인의 영역으로, 컴퓨터(노드라고 불림)들이 협력하여 누가 무엇을 소유하고 있는지 기록합니다. 아무도 속임수(예: 같은 코인을 두 번 사용하는 것)를 쓰지 못하게 하기 위해, 이 컴퓨터들은 '쿼럼(quorum)'이라는 안전망을 사용합니다. 쿼럼을 비밀스러운 악수 클럽이라고 생각해 보세요. 만약 충분한 수의 멤버(보통 2명 중 2명처럼 특정 숫자)가 거래가 진짜라고 동의하면, 그 거래는 공식화됩니다. 클럽의 규모가 커질수록, 사기꾼이 그들 모두를 속이기는 더 어려워집니다. 하지만 여기에는 함정이 있습니다. 만약 클럽이 너무 크면, 모두의 합의를 끌어내는 데 시간이 너무 오래 걸려 전체 시스템이 느려집니다. 그래서 엔지니어들은 속도를 높이기 위해 더 작은 클럽을 사용하기 시작했습니다. 그러나 이는 새로운 문제를 낳았습니다. 만약 교활한 해커가 작은 클럽에 정확히 누가 속해 있는지 안다면, 클럽이 업무를 마치기도 전에 즉시 그 특정 멤버들을 매수하거나 해킹할 수 있습니다. 이는 마치 경비원이 누구인지 정확히 알고, 알람이 울리기도 전에 그 경비원들을 뚫고 지나가는 도둑과 같습니다.

"Secret Quorums: Protecting Byzantine Protocols Against Adaptive Adversaries"라는 제목의 이 논문은 바로 그 문제를 다룹니다. 저자인 Maxence Perion, Sara Tucci-Piergiovanni, Rida Bazzi는 이 작은 클럽들을 운영하는 영리한 새로운 방법을 제안하며, 이를 통해 가장 교활하고 빠른 해커조차 누가 책임을 맡고 있는지 알아낼 수 없게 만듭니다. 그들은 '시크릿 쿼럼(Secret Quorums)'이라는 개념을 도입했는데, 여기서 클럽 멤버들은 업무를 마친 후에도 익명성을 유지합니다. 승인 서류에 이름을 서명하는 대신, 그들은 (링 서명과 무작위 함수를 포함한) 특별한 암호학적 마법 기술을 사용하여 자신이 누구인지는 밝히지 않으면서도 클럽의 일원임을 증명합니다. 논문은 'StealthDust'라는 새로운 결제 시스템을 통해 이를 입증하며, 검증자들의 신원을 숨김으로써 시스템이 훨씬 빨라지고 거래를 확정하는 데 필요한 통신량이 크게 줄어드는 동시에, 실시간으로 타겟을 바꾸는 해커로부터도 안전함을 보여줍니다.

문제점: "러싱(Rushing)" 도둑

당신이 친구 몇 명을 뽑아 거래가 공정한지 결정하게 하는 게임을 하고 있다고 상상해 보세요. 기존 방식에서는 친구가 뽑히면 손을 들고 "나 여기 있어!"라고 외칩니다. 그러면 모든 사람이 누가 의사 결정권자인지 알게 됩니다. 이제, 매우 빠르고 교활한 도둑이 있다고 상상해 보세요. 이 도둑은 게임을 지켜보다가 누가 손을 드는지 보고, 결정이 끝나기도 전에 즉시 그 친구를 배신자로 만들어 버릴 수 있습니다. 컴퓨터 세계에서는 이를 '적응형 및 러싱 공격자(adaptive and rushing adversary)'라고 부릅니다. 그들은 컴퓨터가 참여하는 것을 보는 즉시 해당 컴퓨터를 타락시키거나, 마음을 바꾸게 하거나, 전체 프로세스를 중단시킬 수 있습니다.

논문은 우리가 처음에 비밀스럽게 친구들을 뽑는 방법(암호학적 선출/sortition이라 불리는 것)을 가지고 있지만, 일단 그들이 자신을 증명하려고 하는 순간, 실수로 자신의 정체를 드러내게 된다고 지적합니다. 이는 파티에 가면을 쓰고 갔다가, 인사를 하는 순간 가면을 벗어버리는 것과 같습니다. 가면을 벗는 순간, 도둑은 누구를 공격해야 할지 정확히 알게 됩니다.

해결책: 보이지 않는 클럽

저자들은 **시크릿 쿼럼(Secret Quorum)**이라는 해결책을 제안합니다. 이 새로운 시스템에서 친구들은 비밀리에 선택되지만, 클럽의 일원임을 증명할 때 가면을 벗지 않습니다. 대신, 그들은 특별한 '링 서명(Ring Signature)'을 사용합니다.

링 서명을 손을 잡고 원을 그리며 서 있는 사람들의 모임이라고 생각해 보세요. 만약 원 안에 있는 누군가가 문서에 서명하고 싶다면, 그는 자신이 원 안의 누군가라는 것은 증명하되, 정확히 누구인지는 알 수 없는 방식으로 서명할 수 있습니다. 마치 서명이 "나는 이 원 안에 있는 100명 중 한 명이며, 권한이 있다"라고 말하지만, 특정 인물을 지목하지는 않는 것과 같습니다.

논문은 이를 **링 검증 가능한 무작위 함수(rVRF)**라는 도구를 사용하여 구축하는 방법을 보여줍니다. 이 도구는 두 가지 일을 동시에 수행합니다:

누가 클럽에 들어올지 무작위로 선택합니다 (따라서 도둑은 누가 선택될지 예측할 수 없습니다).
선택된 멤버들이 자신의 이름을 밝히지 않고도 클럽의 일원임을 증명할 수 있게 합니다.

저자들은 설령 도둑이 매우 빠르고 즉각적으로 컴퓨터를 타락시킬 수 있다 하더라도, 어떤 컴퓨터가 실제로 작업을 수행하고 있는지 알아낼 수 없음을 수학적으로 증명합니다. 도둑은 어둠 속에서 추측만 할 뿐, 거래를 막기 위해 적절한 대상을 공격할 수 없습니다.

결과: StealthDust

이 아이디어가 실제 세상에서 어떻게 작동하는지 보여주기 위해, 저자들은 StealthDust라는 새로운 결제 시스템을 구축했습니다. 이 시스템은 돈을 여러 번의 작은 결제로 나누어 처리하고자 할 때 발생하는 '분할 지출(fractional spending)'이라는 까다로운 문제를 해결합니다.

기존 버전의 이 시스템에서는 "러싱 도둑"으로부터 안전을 유지하기 위해, 컴퓨터들이 '비밀 공유(secret sharing)'라는 매우 느리고 복잡한 방법을 사용해야 했습니다. 이는 마치 사람들이 체인을 형성하여 비밀 쪽지를 전달하는 것과 같아서, 모든 사람이 복사본을 작성하고 전달해야 했습니다. 이로 인해 시스템이 느려졌고 컴퓨터 간의 엄청난 양의 대화(통신)가 필요했습니다.

StealthDust를 통해 저자들은 이 느린 비밀 공유 방식을 시크릿 쿼럼으로 대체했습니다. 검증자(업무를 수행하는 컴퓨터)들이 익명성을 유지하기 때문에, 복잡한 비밀 공유 기술로 신원을 숨길 필요가 없습니다. 그들은 그저 익명의 증명을 직접 보낼 수 있습니다.

논문은 이 변화가 엄청난 차이를 만든다는 것을 발견했습니다:

속도: 결제를 처리하는 데 걸리는 시간을 **5번의 메시지 지연(message delays)**에서 3번의 메시지 지연으로 단축했습니다.
효율성: 계좌를 정산하는 데 필요한 대화량을 줄였습니다. 기존 시스템은 인원이 늘어남에 따라 매우 빠르게 증가하는 **O(n³)**의 복잡도를 요구했지만, StealthDust는 이를 **O(n²)**로 낮추었습니다. 자금을 환급(redeeming)할 때는 **O(n²)**에서 **O(n)**으로 떨어졌습니다.

이것이 의미하는 바

이 논문이 세상의 모든 문제를 해결했다고 주장하는 것은 아닙니다. 만약 네트워크 트래픽 자체가 단서(예: 메시지가 도착하는 속도)를 제공한다면, 매우 똑똑한 도둑은 여전히 힌트를 얻을 수 있다는 점을 인정합니다. 또한, 이 시스템은 숨을 수 있는 후보 그룹이 충분히 커야 한다는 점에 의존합니다. 만약 거의 모든 사람이 도둑이라면, 숨을 곳이 사라지기 때문입니다.

그러나 저자들은 작은 규모의 컴퓨터 그룹이 매우 빠른 해커, 즉 타겟을 즉시 바꿀 수 있는 해커에 맞서서도 빠르고 안전하게 결정을 내릴 수 있는 시스템을 만드는 것이 가능하다는 것을 성공적으로 보여주었습니다. 의사 결정자의 신원을 결정이 끝난 후에도 비밀로 유지함으로써, 그들은 분산 시스템을 더 빠르고 안전하게 만드는 방법을 찾아냈습니다. 이것은 디지털 시대를 위한 새로운 종류의 마법 주문입니다. 즉, 얼굴을 보여주지 않고도 당신이 신뢰할 수 있는 사람임을 증명하는 것입니다.

기술 요약: 시크릿 쿼럼(Secret Quorums): 적응형 공격자로부터 비잔틴 프로토콜 보호하기

1. 문제 정의

현대의 위원회 기반 결제 프로토콜과 분산 시스템은 확장성을 높이고 지연 시간을 줄이기 위해 종종 참가자의 작은 부분 집합(쿼럼)에 의존합니다. 그러나 이러한 설계는 **적응형 공격자(adaptive adversaries)**에 대한 치명적인 취약점을 유발합니다. 표준적인 확률적 쿼럼 시스템에서는 검증자 선택이 무작위로 이루어지지만, 일반적인 검증 과정에서는 선택된 노드들이 암호학적 서명을 통해 자신의 신원을 드러내야 합니다.

노드를 즉각적으로 타락시키고, "러싱(rushing)"(콘텐츠를 관찰하고 행동하기 위해 올바른 메시지보다 먼저 타락한 노드에 메시지를 전달하는 행위)을 수행할 수 있는 적응형 공격자는 이러한 신원 노출을 악용할 수 있습니다. 특정 검증자가 투표나 증명을 통해 신원을 드러내는 순간, 공격자는 해당 노드를 즉시 타락시키고 로컬 상태를 삭제하여 검증을 지원하지 못하게 만들 수 있습니다. 만약 쿼럼의 크기가 작다면, 공격자는 이 과정을 충분한 수의 검증자에게 반복하여 프로토콜의 진행을 중단시키거나 안전성을 해칠 수 있습니다.

암호학적 소티션(cryptographic sortition, 비밀 선거)과 같은 기존 솔루션들은 노드가 발언하기 전에는 노드를 보호하지만, 선택 증명을 통해 드러난 후의 노드는 보호하지 못합니다. 블라인드 서명(blind signatures)이나 분할 지불 프로토콜에서 사용되는 비밀 공유(secret sharing)와 같은 다른 접근 방식들은 이러한 위험을 완화하지만, 상당한 통신 오버헤드와 지연 시간을 초래합니다.

2. 방법론: 시크릿 쿼럼(Secret Quorums)

본 논문은 암호학적 소티션을 확장하여 검증 과정 전체 동안 검증자의 익명성을 유지하는 새로운 추상화인 **시크릿 쿼럼(Secret Quorum)**을 제안합니다.

핵심 추상화

시크릿 쿼럼은 $n$ 개의 노드 집단에서 $k$ 개의 검증자를 선택하는 집합 $S$ 로서 다음의 속성을 가집니다:

예측 불가능성(Unpredictability): 공격자는 특정 노드가 $S$ 에 포함되어 있는지 여부를 무작위 추측 확률( $k/(n-f)$ )보다 높은 확률로 맞출 수 없습니다.
익명성(Anonymity): 멤버십 증명은 해당 검증자가 정당하다는 것을 드러내지만, 어떤 검증자가 그 증명을 생성했는지는 드러내지 않습니다.
공정성(Fairness): 선택은 균등하며, 공격자는 특정 노드를 쿼럼에 강제로 포함시킬 수 없습니다.
검증 가능성(Verifiability): 어떤 노드라도 쿼럼의 구성 성분을 알지 못한 채, $k$ 크기의 유효한 증명이 생성되었음을 검증할 수 있습니다.

rVRF(Ring Verifiable Random Functions)를 통한 구현

저자들은 **링 검증 가능한 랜덤 함수(rVRF)**를 사용하여 시크릿 쿼럼을 구축합니다. 이는 검증 가능한 랜덤 함수(VRF)와 링 서명(ring signatures)을 결합한 암호학적 프리미티브입니다.

후보 집합(Candidate Set): 쿼리에 대해 결정론적인 후보 검증자 집합 $V_k$ 가 도출됩니다.
사적 자기 선택(Private Self-Selection): 각 후보는 쿼리 데이터에서 유도된 시드(seed)를 사용하여 rVRF를 사적으로 평가합니다. 출력값이 특정 임계값 미만이면, 해당 노드는 자신이 유효한 쿼럼의 일부라고 판단합니다.
익명 증명(Anonymous Proof): 선택된 노드들은 후보 집합에 대해 링 서명을 생성합니다. 이 서명은 집합 내의 누군가가 선택되었고 유효한 랜덤 출력을 생성했음을 증명하지만, 구체적인 서명자는 암호학적으로 숨깁니다.
검증(Verification): 클라이언트는 이러한 링 서명들을 수집합니다. 검증자는 서명이 유효한 링 서명인지, 그리고 기저의 랜덤 출력이 선택 임계값을 만족하는지 확인합니다. 동일한 서명자로부터 나온 중복 출력은 인플레이션을 방지하기 위해 거부됩니다.

이 구조는 비동기 네트워크에서 작동하며, 표준 쿼럼 프로토콜에 비해 추가적인 통신 단계를 더하지 않지만, 선택된 부분 집합 대신 전체 후보 집합( $V_k$ )에 연락해야 합니다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 합니다:

시크릿 쿼럼 추상화: 익명 쿼럼 검증을 가능하게 하는 새로운 추상화의 정의입니다. 표준적인 비밀 선거가 행동 시 멤버를 드러내는 것과 달리, 시크릿 쿼럼은 검증 증명이 검증된 후에도 검증자가 익명성을 유지하도록 보장합니다.
실용적 구현: rVRF를 사용하여 비동기 네트워크에서의 시크릿 쿼럼에 대한 구체적인 구성을 제공합니다. 이는 모든 단계에서 복잡한 다자간 계산(MPC)을 요구하지 않고도 탈중앙화된 환경을 위한 실행 가능한 메커니즘을 제공합니다.
StealthDust 프로토콜: 분할 지불 문제(단일 계정으로부터 병렬적인 비충돌 결제를 허용하는 문제)를 위한 새로운 프로토콜인 StealthDust를 설계했습니다. StealthDust는 이전의 최첨단 프로토콜(Bazzi와 Tucci [10])의 신원 노출 메커니즘을 대체하기 위해 시크릿 쿼럼을 적용합니다.

4. 결과 및 성능

시크릿 쿼럼을 분할 지불에 적용한 StealthDust는 강력한 적응형 및 러싱 공격자에 대한 탄력성을 유지하면서 복잡도와 지연 시간을 크게 개선합니다.

통신 복잡도(Communication Complexity):
- 결제 완료(Settlement): 이전 프로토콜(비밀 공유로 인한)의 $O(n^3)$ 에서 StealthDust의 $O(n^2)$ 로 감소했습니다.
- 환급(Redeem): $O(n^2)$ 에서 $O(n)$ 으로 감소했습니다.
- 결제(Payment): 결제 단계는 쿼럼 크기 $m$ 이 아닌 후보 집합 크기 $V_m$ 에 비례하는 비용이 발생하지만, 비밀 공유의 필요성을 제거합니다.
지연 시간(Latency):
- 결제 지연 시간이 블라인드 서명과 여러 라운드를 포함했던 이전 프로토콜의 5 메시지 지연에서 3 메시지 지연으로 감소했습니다.
보안성(Security): StealthDust는 원래의 분할 지불 프로토콜이 가진 안전성 및 활성(liveness) 보장을 유지하면서, 공격자가 선택 후 검증자를 식별하고 타락시키는 것을 방지합니다.

5. 의의 및 한계점

의의:
본 논문은 시크릿 쿼럼이 위원회 기반 프로토콜이 적응형 공격자를 처리하는 방식에 있어 근본적인 변화를 제공한다고 주장합니다. 정당성의 증명과 신원의 노출을 분리함으로써, 프로토콜은 소규모 쿼럼 시스템을 괴롭히는 "러시-앤-코럽트(rush-and-corrupt)" 공격 벡터를 차단합니다. 저자들은 이러한 보호가 비밀 공유의 무거운 오버헤드 없이도 달성될 수 있음을 입증하며, 이를 통해 고위험 환경에서도 소규모 쿼럼 프로토콜을 실행 가능하게 만듭니다.

제한 사항 및 한계:
저자들은 다음과 같은 몇 가지 트레이드오프와 한계점을 명시적으로 인정합니다:

익명성 집합 크기(Anonymity Set Size): 익명성은 후보 집합 크기 $V_k$ 에 의해 제한됩니다. $V_k$ 가 작으면 익명성 집합도 작아져 트래픽 분석에 취약할 수 있습니다. 가장 강력한 익명성은 $V_k = n$ 일 때 유지됩니다.
네트워크 메타데이터: 암호학적 증명이 신원을 숨기더라도, 네트워크 메타데이터(타이밍, 트래픽 분석)는 여전히 정보를 유출할 수 있습니다. 프로토콜은 이를 완화하기 위해 은닉된 전파(예: 가십, 배칭)를 가정합니다.
확률적 특성: 유효한 쿼럼의 선택은 확률적입니다. 시스템은 높은 확률로 최소 $k$ 개의 검증자가 선택됨을 보장하지만, 이는 결정론적이지 않습니다.
접근 전략: 이 구성은 랜덤 샘플링 접근 전략을 지원합니다. 쿼럼 멤버십이 시스템 상태나 이전 쿼럼에 의존하는 복잡한 접근 전략은 멤버십에 대한 정보를 유출할 수 있으므로 현재는 지원하지 않습니다.
암호학적 가정: 구현은 안전하고 효율적인 rVRF 프리미티브의 가용성에 의존합니다.

결론적으로, 본 논문은 시크릿 쿼럼을 익명성, 효율성, 보안성의 균형을 맞춘 실용적이고 최초로 실행 가능한 구성으로 제시하며, 적응형 위협에 대응하는 더욱 확장 가능하고 탄력적인 분산 시스템을 향한 경로를 제시합니다.