💻 computer science

Giskard : Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

Giskard는 참여자들을 위원회 트리로 구성하여 통신 복잡도를 줄인 보안 가능한 성분별 근사 중앙값 집합(coordinate-wise approximate median aggregation)을 수행함으로써 데이터 기밀성과 비잔틴 강건성을 동시에 보장하는 대규모 분산 학습을 위한 확장 가능한 프로토콜이다.

원저자: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

게시일 2026-06-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

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

수많은 사람들이 함께 거대한 퍼즐을 풀려고 노력하는 모습을 상상해 보세요. 각 개인은 자신만의 고유한 퍼즐 조각(개인 데이터)을 가지고 있으며, 자신의 조각을 누구에게도 보여주지 않고도 최종적인 그림(머신러닝 모델)을 완성하는 데 기여하고 싶어 합니다. 이것이 바로 **분산 학습(decentralized learning)**의 세계입니다.

하지만 여기에는 두 가지 큰 문제가 있습니다.

교활한 방해꾼들 (비잔틴 결함, Byzantine Faults): 그룹 중 일부는 퍼즐을 망치려는 목적으로 참여할 수 있습니다. 그들은 가짜 조각이나 왜곡된 버전의 조각을 제출하여 최종 이미지를 망가뜨릴 수 있습니다.
비밀 유지 (기밀성, Confidentiality): 다른 모든 사람들은 자신의 퍼즐 조각을 숨기고 싶어 합니다. 만약 그들이 단순히 퍼즐 조각을 건네준다면, 방해꾼들이나 호기심 많은 이웃들이 개인의 사적인 세부 정보를 엿볼 수 있기 때문입니다.

보통, 여러분은 하나를 선택해야만 합니다. 방해꾼을 잡기 위해 모든 사람의 조각을 검사하거나(이것은 비밀을 드러내게 됩니다), 혹은 비밀을 지키기 위해 조각을 숨기는 것(이것은 방해꾼을 잡기 어렵게 만듭니다) 중 하나를 말이죠.

Giskard의 등장: "위원회 트리(Tree of Committees)" 솔루션

이 논문은 이 두 가지 문제를 동시에 해결하면서도, 그룹의 규모가 백만 명까지 커져도 작동하는 영리한 새로운 방식인 Giskard를 소개합니다. 이 방식이 어떻게 작동하는지 쉬운 비유를 통해 설명해 드리겠습니다.

1. 기존 방식의 문제점

그룹이 모든 사람이 서로에게 답을 외치는 방식으로 퍼즐을 풀려고 한다고 가정해 봅시다.

"전체 대 전체(All-to-All)" 방식: 모든 사람이 모두와 대화합니다. 사람이 1,000명이면 백만 번의 대화가 필요합니다. 만약 백만 명이라면 네트워크가 다운될 것입니다. 너무 시끄럽고 너무 느립니다.
"하나의 거대 위원회(One Big Committee)" 방식: 그룹에서 100명의 소규모 팀을 뽑아 모든 검사와 계산을 수행하게 합니다. 나머지 사람들에게는 이 방식이 빠르겠지만, 이 100명의 팀원들은 과부하에 걸리게 됩니다. 그룹이 백만 명으로 늘어나더라도, 이 작은 팀은 여전히 모든 무거운 작업을 떠맡아야 하며 결국 압박을 견디지 못하고 무너질 것입니다.

2. Giskard의 솔루션: 계층적 트리

Giskard는 사람들을 소규모 위원회의 트리로 조직함으로써 게임의 판도를 바꿉니다.

잎사귀 (사람들, The Leaves): 모든 사람이 서로 대화하는 대신, 사람들은 약 50~100명 정도의 소규모 팀(위원회)으로 그룹화됩니다.
가지 (위원회들, The Branches): 이 소규모 팀들이 서로 대화하고, 그들의 "부모" 팀이 다시 그 "부모" 팀과 대화하며, 트리 꼭대기까지 올라갑니다.
뿌리 (최상위 위원회, The Root): 맨 꼭대기에 있는 마지막 소규모 팀이 최종 결정을 내립니다.

마법 같은 기술: "숫자 맞히기" 게임
Giskard는 속이기 쉬운 "평균"을 구하거나, 비밀리에 하기 어려운 "정렬"을 하는 대신, **비밀 이진 탐색(secret binary search)**을 이용한 "숫자 맞히기" 게임을 수행합니다.

피벗 (Pivot): 그룹은 중간 숫자(피벗)를 하나 정합니다.
비밀 투표: 모든 사람은 자신의 숫자를 확인하고, "내 숫자가 피벗보다 작은가?"라고 자문합니다. 그들은 "예" 또는 "아니오"라고 소리 내어 말하지 않습니다. 대신, 종이에 답을 적고 이를 갈갈이 찢은 뒤, 조각들을 자신의 소규모 위원회에 전달합니다.
위원회의 집계: 소규모 위원회는 **안전한 다자간 계산(Secure Multi-Party Computation)**이라는 수학적 마법을 사용하여 이 조각들을 다시 합쳐서 "예"라는 투표가 몇 개인지 계산합니다. 그들은 누가 "예"라고 했는지는 알지 못하지만, 총 몇 명이 "예"라고 했는지는 알 수 있습니다.
책임 넘기기: 위원회는 이 집계 값을 트리 위로 보냅니다. 다음 단계의 위원회는 자식 위원회로부터 받은 집계 값을 더하고, 이 과정이 반복되어 꼭대기 위원회는 전체 그룹의 총 "예" 투표 수를 알게 됩니다.
업데이트: 총 "예" 투표 수를 바탕으로, 그룹은 "진짜 정답"이 피벗보다 높은지 낮은지 알 수 있습니다. 그러면 새로운 피벗을 정하고 게임을 반복합니다.

3. 왜 이것이 혁신적인가?

비밀이 보장됩니다: "조각난" 종이(비밀 공유)를 기반으로 수학적 계산이 이루어지기 때문에, 그 어떤 단 한 명의 사람이나 소규모 그룹도 원래의 숫자를 재구성할 수 없습니다. 방해꾼들은 데이터를 볼 수 없습니다.
강력합니다 (Robust): 소규모 위원회 내의 일부 사람들이 집계 값을 속이려는 방해꾼이라 할지라도, 위원회의 과반수가 정직하다면 수학적 원리에 의해 최종 집계는 정확하게 유지됩니다. 즉, 방해꾼들이 "숫자 맞히기" 게임을 속일 수 없도록 설계되었습니다.
빠릅니다 (Scalable): 이것이 가장 큰 승리입니다. 기존의 "하나의 거대 위원회" 방식에서는 사람 수가 두 배로 늘어나면 위원회의 업무량이 훨씬 더 무거워집니다. 하지만 Giskard에서는 업무가 트리 전체로 분산되기 때문에, 사람을 추가해도 개별 인원이 느끼는 업무량은 거의 늘어나지 않습니다.
- 논문의 주장: Giskard는 각 개인이 주고받는 통신 비용을 획기적으로 줄여서 백만 명의 참가자를 효율적으로 처리할 수 있습니다. 가장 가까운 경쟁 모델과 비교했을 때, 네트워크 규모가 매우 커질 경우 Giskard는 각 개인이 보내야 하는 데이터를 1,775배나 줄여줍니다.

4. 결과

저자들은 최대 백만 명의 시뮬레이션 참가자를 대상으로 Giskard를 테스트했습니다.

속도: Giskard는 이전 방식들보다 훨씬 더 효율적입니다. 다른 방식들이 백만 명의 인원을 처리하는 데 몇 년이 걸릴 수 있다면, Giskard는 (인터넷 속도에 따라 다르겠지만) 몇 분에서 몇 시간 내에 이론적으로 완료할 수 있습니다.
정확도: 그룹의 25%가 모델을 망치려는 방해꾼이라 할지라도, Giskard는 여전히 높은 품질의 모델을 만들어냈으며, 프라이버시를 보호하지 않는 일반적인 방식들과 대등한 성능을 보여주었습니다.

요약하자면:
Giskard는 마치 거대하고 비밀스러운, 방해꾼 방지 투표 시스템을 조직하는 것과 같습니다. 모든 사람이 투표를 외치는 방식(느리고 보안에 취к)이나 하나의 작은 그룹이 모든 계산을 떠맡는 방식(과부하 발생) 대신, 작은 팀들이 트리의 가지를 타고 비밀스러운 집계 값을 전달하는 방식을 사용합니다. 이를 통해 백만 명의 사람들이 서로의 비밀을 지키고, 방해꾼들이 파티를 망치는 것을 막으면서도, 네트워크가 대화의 무게로 인해 무너지지 않고 함께 학습할 수 있게 해줍니다.

기술 요약: Giskard

문제 정의

탈중앙화 학습은 신뢰할 수 있는 중앙 오케스트레이터 없이 참여자들이 피어 투 피어(P2P) 방식으로 상호작용할 수 있게 함으로써, 개인정보를 보호하는 대안을 제공합니다. 그러나 이러한 시스템은 두 가지의 동시적이며 종종 상충하는 과제에 직면해 있습니다:

비잔틴 강건성(Byzantine Robustness): 악의적이거나 결함이 있는 노드가 글로벌 모델을 오염시키기 위해 임의로 조작된 모델 업데이트(모델 포이즈닝)를 제출할 수 있습니다. 이를 방어하기 위해서는 일반적으로 개별 기여도를 검사하고 비교하여 이상치를 필터링하는 과정(예: 좌표별 중앙값 또는 절단 평균 사용)이 필요합니다.
기밀성(Confidentiality): 참여자들은 자신의 로컬 데이터와 모델 업데이트를 비공개로 유지해야 합니다. 다자간 계산(MPC)과 같은 암호화 기술은 이러한 업데이트를 숨겨주지만, 표준적인 강건한 집계 함수(정렬 및 비교에 의존함)는 암호화된 형태로 구현하기에 계산 비용이 매우 높습니다.

기존 솔루션들은 이러한 문제들을 별도로 해결하거나, 확장성이 낮은 방식으로 MPC를 결합하여 사용합니다. 기존의 많은 탈중앙화 MPC 방식은 전방위 통신(all-to-all communication)에 의존하거나 계산을 단일 소규모 위원회에 위임하며, 이로 인해 노드 수가 증가함에 따라 노드당 통신 복잡도가 선형 또는 그 이상( $O(n)$ 또는 $O(n \log^2 n)$ )으로 증가하는 근본적인 확장성 병목 현상을 초래합니다. 이는 대규모 배포(예: $n \ge 10^4$ ) 시 치명적입니다.

방법론: Giskard 프로토콜

Giskard는 서브 리니어(sub-linear) 통신 복잡도를 가지면서도 완전한 탈중앙화 환경에서 비잔틴 강건성과 기밀성을 모두 달려하는 프로토콜입니다. 이 프로토콜은 최대 $f < n/4$ 의 참여자가 부패할 수 있는 정적이고 계산적으로 제한된 적대자 모델 하에서 작동합니다.

핵심 기술적 통찰

중앙값을 위한 이진 탐색(Binary Search for Median): 값 도메인에서의 보안 이진 탐색으로 중앙값 계산을 재구성함으로써, 비용이 많이 드는 일반적인 정렬 회로를 구현하는 대신 문제를 해결합니다. 프로토콜은 피벗 $p_t$ 보다 작은 입력의 개수를 세는 과정을 통해 $[Left, Right]$ 범위를 반복적으로 좁혀 나갑니다. 이는 문제를 일련의 보안 카운팅 연산으로 축소합니다.
계층적 위원회 트리(Hierarchical Committee Tree): 계산 부하를 분산하기 위해, Giskard는 $n$ $n$ 명의 참여자를 각 크기가 $m = O(\log n)$ $m = O (lo g n)$ 인 $k$ $k$ -ary 트리 구조의 위원회로 구성합니다.
- 리프 노드 (Level 0): 개별 참여자는 자신의 로컬 벡터를 현재 피벗과 비교하고, 결과 비트 벡터를 할당된 베이스 위원회에 비밀 공유(secret-share)합니다.
- 베이스 위원회 (Level 1): 차수-2 증명을 사용하여 공유된 비트의 도메인을 검증(비트가 0 또는 1인지 확인)하고, 셰어를 집계한 후 부분 합을 상위 레벨로 다시 공유합니다.
- 중간 위원회 (Levels 2 to $L-1$ ): 하위 위원회로부터 셰어를 받아 검증 가능한 재공유(verifiable resharing)를 수행하고 상위로 집계합니다.
- 루트 위원회 (Level $L$ ): 글로벌 카운트를 평문(in the clear)으로 복구하고, 피벗을 업데이트한 뒤 다음 반복을 위해 트리를 따라 새로운 피벗을 브로드캐스트합니다.
암호화 프리미티브: 프로토콜은 악의적인 적대자에 대한 보안을 보장하기 위해 BGW 스킴(Asharov 및 Lindell 기반)에 기초한 검증 가능한 비밀 공유(VSS)를 활용합니다. 또한 보안이 입증된(UC-secure) 공유, 곱셈, 재공로(resharing)를 위한 서브 프로토콜을 채택합니다.

보안 및 강건성 보장

기밀성: 개별 입력과 중간 카운트는 숨겨지며, 오직 피벗 업데이트에 사용되는 최종 집계 카운트만이 공개됩니다.
비잔틴 강건성: 프로토콜은 최대 $n/4$ 의 비잔틴 참여자를 허용합니다. 이는 $(f, \kappa)$ -비잔틴 강건성 기준을 충족하여, 출력이 정직한 업데이트의 평균에 가깝게 유지되도록 보장합니다.
정확성: 이진 탐색은 정밀도 $q$ 에 대해 $N_{iter} = \lceil \log_2(2u/q) \rceil$ 번의 반복 후에 중앙값으로 수렴합니다.

주요 기여

새로운 프로토콜 제안: 수백만 명의 참여자 규모로 확장 가능한 강건하고 기밀한 탈중앙화 학습 프로토큘인 Giskard를 제안했습니다.
이론적 보안: Giskard가 표준 암호학적 가정과 서브 프로토콜(BA, VSS 등)의 보안성에 기반하여 하이브리드 모델에서 UC-보안(UC-secure)을 갖는다는 공식적인 증명을 제공합니다.
통신 복잡도 분석: Giskard의 최악의 경우 노드당 통신 복잡도가 $O(d \cdot N_{iter} \cdot \log^3 n)$ 임을 입증하여, All-to-All( $O(d \cdot n^2)$ )이나 All-to-Committee( $O(d \cdot n \log^2 n)$ )와 같은 경쟁 모델보다 크게 개선되었음을 보여줍니다.
실험적 검증: $n=10^6$ 규모의 네트워크 크기에서 MNIST 및 CIFAR-10 데이터셋을 이용한 광범위한 평가를 수행했습니다.

실험 결과

저자들은 Giskard를 두 가지 베이스라인 토폴로지인 All-to-All (A2A) 및 All-to-Committee (A2C)와 비교 평가했습니다.

확장성 (통신 비용):
- 비잔틴 비율이 10%인 $n=10^6$ 상황에서, Giskard는 A2C 대비 약 1,775배, A2A 대비로는 수 차례 이상의 격차로 노드당 통신량을 줄였습니다.
- A2C는 부하를 단일 위원회에 집중시켜 대규모 환경에서 대역폭 제한으로 인해 실용성이 떨어지는 반면, Giskard는 트리를 통해 부하를 분산함으로써 $n=10^6$ 에서도 노드당 비용을 관리 가능한 수준으로 유지합니다.
- 대규모 환경에서 A2C 및 A2A의 예상 실행 시간은 며칠에서 몇 년에 달해 실용적 한계를 넘어서지만, Giskard는 몇 분에서 몇 시간 내에 완료됩니다.
모델 유용성 (강건성):
- Non-i.i.d. 데이터에 대한 네 가지 모델 포이즈닝 공격(Label Flipping, Sign Flipping, IPM, ALIE) 하에서, Giskard의 이진 탐색 중앙값은 최신 평문 강건 집계 방식(Trimmed Mean, Median)과 대등한 테스트 정확도를 달성했습니다.
- MNIST의 경우 정확도 차이가 0.4% 미만이었으며, CIFAR-10의 경우 정밀한 조작이 필요한 고도로 최적화된 공격에 대해서는 약간 높은 차이(최대 2.7%)를 보였으나 전반적으로 1.5% 미만의 차이를 유지했습니다.
- 실험을 통해 이진 탐색 반복 횟수( $N_{iter}$ )에 대한 급격한 임계값을 확인했습니다. 약 10회 이상의 반복은 유의미한 강건성 향상을 가져오지 못하는 대신 통신 비용만 선형적으로 증가시켰습니다.

의의 및 주장

본 논문은 Giskard가 탈중앙화 학습에서 확장성과 보안 사이의 간극을 메운다고 주장합니다. 계층적 위원회 구조와 특화된 이진 탐색 기반 중앙값 형식을 결합함으로써 Giskard는 다음을 달성합니다:

서브 리니어 통신: 완전한 탈중앙화 환경에서 비잔틴 강건하고 기밀한 집계를 위해 폴리로그(polylogarithmic) 노드당 통신을 달성한 최초의 프로토콜입니다.
공식적 보장: 휴리스틱 접근 방식과 달리, Giskard는 UC-보안 증명과 공식적인 강건성 경계를 제공합니다.
실용성: 실험 결과는 이 프로토콜이 이전의 MPC 기반 솔루션들이 계산적, 통신적으로 불가능했던 최대 100만 명 규모의 대규모 배포에서도 실행 가능하다는 것을 입증합니다.

저자들은 이 프로토콜이 반복 횟수와 정밀도 사이의 트레이드오프를 도입하지만, 제안된 시스템이 기밀성, 강건성, 확장성을 효과적으로 균형 있게 조절하여 대규모 보안 탈중앙화 학습을 실용적으로 만든다고 결론짓습니다. 향-후 연구로는 비용을 더욱 낮추기 위해 암호학적 가정에 기반한 계산적 변형을 탐구할 것을 제안합니다.