On the Limits of Consensus under Dynamic Availability and Reconfiguration

사람들이 공유된 장부를 기록하기 위해 모이는 디지털 마을 광장을 상상해 보십시오. 옛날에는 이 마을 광장에 항상 깨어 있고, 항상 지켜보고 있으며, 항상 투표할 준비가 되어 있는 고정된 거주자 명단이 있었습니다. 만약 누군가 잠들거나 마을을 떠나면, 그 사람이 돌아올 때까지 전체 시스템은 멈춰버렸습니다. 하지만 오늘날의 디지털 마을은 다릅니다. 이곳은 거칠고, 개방적이며, 혼란스럽습니다. 사람들은 끊임없이 들어오고 나갑니다. 때로는 거주자들의 거대한 집단이 동시에 낮잠을 자러 가기도 합니다. 이것이 바로 **동적 가용성(Dynamic Availability)**의 세계입니다. 즉, 대부분의 투표자가 잠들어 있을 때도 시스템은 계속 작동해야 합니다.

상황을 더 까다롭게 만드는 것은, 투표 권한이 있는 사람의 명단이 고정되어 있지 않다는 점입니다. 이는 시간이 흐름에 따라 변합니다. 이를 **재구성(Reconfiguration)**이라고 부릅니다. 어떤 새로운 거주자가 집을 사서 투표권을 얻을 수도 있고, 오래된 거주자가 집을 팔고 떠날 수도 있습니다. 컴퓨터 과학자들의 큰 고민은 이것입니다. 투표자들이 끊임없이 낮잠을 자고 투표자 명단이 계속 바뀌는 상황에서 어떻게 마을 광장을 안전하고 정직하게 유지할 것인가? 만약 이를 잘못 처리한다면, 교활한 방해꾼이 역사를 새로 써서, 마치 마을이 결코 투표한 적 없는 일에 대해 투표한 것처럼 속이거나, 새로운 거주자를 가짜 마을 버전으로 속여 끌어들일 수 있습니다.

이 논문은 바로 그 문제에 깊이 파고듭니다. 저자인 하비에르 니에토(Javier Nieto), 요아힘 노이(Joachim Neu), 링 렌(Ling Ren)은 단순하지만 어려운 질문을 던집니다. 이 혼란스럽고 낮잠을 자는, 변화하는 마을을 안전하게 유지하기 위한 절대적인 최소 요구 사항은 무엇인가? 그들은 기존의 시스템들을 살펴보고, 많은 시스템이 "마법의 기술"이나 적절하지 않은 추가 규칙들에 의존하고 있다는 점을 발견했습니다. 예를 들어, 잠든 거주자들조차 비밀리에 비밀번호를 업데이트하고 있다거나, 새로운 거주자가 합류하기 전에 마법처럼 신뢰할 수 있는 친구에게 최신 소식을 물어볼 수 있다고 가정하는 식입니다. 저자들은 이러한 추가적인 규칙들을 모두 제거하여 "순수한(plain)" 버전의 문제에서 어떤 일이 일어나는지 확인합니다. 그들은 아무런 마법의 기술 없이 마을을 안전하게 유지하려면 매우 구체적인 조건이 필요하다는 것을 발견했습니다. 즉, 어느 순간에도 깨어 있는 정직한 사람의 수가 방해꾼의 수와 방해꾼이 대신할 수 있을 만큼 오랫동안 잠들어 있었던 사람의 수를 합친 것보다 많아야 한다는 것입니다. 그들은 이를 "시뮬레이션 저항적 정직한 다수(Simulation-Resistant Honest Majority)"라고 부릅니다.

하지만 저자들은 문제점을 찾는 데서 그치지 않고, 영리한 해결책도 제시합니다. 그들은 한 가지 작고 현실적인 규칙을 추가할 것을 제안합니다. 거주자가 마을을 떠나기로 결정했을 때, 반드시 "작별" 서명을 하고 예전의 열쇠를 버려야 한다는 것입니다. 이 간단한 행위는 방해꾼이 해당 거주자가 과거에 여전히 투표하고 있었다고 가장하는 것을 불가능하게 만듭니다. 이 작은 변화 하나로, 마을을 안전하게 유지하기 위한 규칙은 훨씬 쉬워지며, 모든 것이 순조롭게 진행될 때 시스템은 훨씬 더 빠르게 작동할 수 있습니다.

문제: 낮잠 자는 마을과 변화하는 방문객 명단

디지털 블록체인을 모든 네트워크 구성원이 함께 써 내려가는 거대한 공유 일기라고 상상해 봅시다. 이 일기가 제대로 작동하려면, 그룹은 다음에 무엇을 쓸지에 대해 합의해야 합니다. 과거의 지루한 컴퓨터 과학 세계에서는 그룹에 누가 있는지 정확히 알 수 있었고, 모두가 항상 깨어 있었습니다. 누군가 잠들면 회의는 중단되었습니다.

하지만 현대의 지분 증명(Proof-of-Stake) 블록체인(암호화폐의 기반이 되는 것들)의 세계는 무질서합니다.

1. 동적 가용성(Dynamic Availability): 노드(시스템을 실행하는 컴퓨터)는 잠들 수 있습니다. 컴퓨터를 끄거나, 인터넷 연결이 끊기거나, 그냥 휴식을 취할 수 있습니다. 시스템은 마을의 절반이 잠들어 있어도 계속 작동해야 합니다.
2. 재구성(Reconfiguration): 투표할 수 있는 사람의 명단이 변합니다. 새로운 노드가 합류하고, 기존 노드가 떠납니다. 이는 마치 매주 멤버십 명단이 업데이트되는 클럽과 같습니다.

이 두 가지가 결합되면 보안 측면에서 악몽 같은 시나리오가 발생합니다. 친구들이 영화를 고르려고 결정하는 상황을 상상해 보십시오. 절반은 잠들어 있고, 투표할 수 있는 명단은 5분마다 바뀝니다. 교활한 악당(공격자)은 이 그룹을 속이려 합니다.

악당은 두 가지 주요 수법을 사용합니다:

• 장기 공격(Long-Range Attack): 악당은 몇 년 전 클럽을 떠난 옛 멤버를 타락시킵니다. 그 사람은 여전히 옛날 신분증을 가지고 있기 때문에, 악당은 그 신분증을 사용하여 과거의 결정에 서명함으로써, 마치 클럽이 몇 년 전 다른 영화를 위해 투표한 것처럼 조작할 수 있습니다.
• 역방향 시뮬레이션(또는 비용 없는 시뮬레이션, Backward Simulation/Costless Simulation): 이것은 정말 까다로운 수법입니다. 아주 오랫동안 잠들어 있던 멤버를 상상해 보십시오. 악당은 '지금' 그 멤버를 타락시킵니다. 그 멤버는 잠자는 동안 신분증을 업데이트하거나 비밀번호를 바꾸지 않았기 때문에, 악당은 이제 이 사람이 과거에 깨어 있었고 투표 중이었다고 주장하며, 깨어난 사람들에게 완벽하게 유효해 보이는 가짜 역사를 만들어낼 수 있습니다.

"순수한" 문제: 마법은 허용되지 않는다

많은 기존 시스템은 추가적인 규칙을 더해 이 문제를 해결하려 합니다. 어떤 시스템은 "새 멤버는 신뢰할 수 있는 친구에게 최신 소식을 물어봐야 한다"(사회적 합의)고 말합니다. 다른 시스템은 "잠들어 있더라도 매초 비밀번호를 업데이트해야 한다"(연속적 키 진화)고 말합니다.

이 논문의 저자들은 이렇게 말합니다. "잠깐, 그건 속임수입니다." 그들은 "순수한 DAR 모델"에서 이 문제를 해결할 수 있는지 알고 싶어 합니다. 즉:

• 친구에게 도움을 요청하지 않습니다.
• 잠자는 동안 비밀리에 업데이트하지 않습니다.
• 마법은 없습니다.

그들은 묻습니다: 이 시스템을 안전하게 유지하기 위한 최소한의 조건은 무엇인가?

발견: "시뮬레이션 저항적" 규칙

저자들은 이 "순수한" 세상에서는 단순히 "나쁜 놈들보다 착한 놈들이 더 많으면 된다"는 것만으로는 부족하다는 것을 증명했습니다. 그것은 충분하지 않습니다. 더 강력한 것이 필요합니다.

그들은 **시뮬레이션 저항적 정직한 다수(Simulation-Resistant Honest Majority, SR-HM)**라는 개념을 도입합니다.

다음은 비유입니다. 마을 광장을 상상해 보십시오.

• 정직한 깨어 있는 사람들: 현재 일어나서 투표하고 평화를 유지하고 있는 사람들입니다.
• 나쁜 놈들: 깨어 있는 상태에서 혼란을 일으키려는 방해꾼들입니다.
• 시뮬레이션 가능한 사람들(Simulatable): 오랫동안 잠들어 있었던 사람들입니다. 그들은 키를 업데이트하지 않았기 때문에, 악당이 그들을 깨워 "내가 바로 당신이고, 어제 이 것에 투표했다!"라고 말하게 할 수 있습니다.

논문은 시스템이 안전하려면, 정직하게 깨어 있는 사람의 수가 나쁜 놈들의 수와 시뮬레이션 가능한 사람들의 수를 합친 것보다 엄격히 많아야 함을 증명합니다.

만약 악당들이 정직하게 깨어 있는 사람들보다 더 많은 사람인 척할 수 있다면, 그들은 역사를 새로 쓸 수 있습니다. 그들은 자신들이 투표에서 승리한 것처럼 보이는 가짜 타임라인을 만들 수 있으며, 아무도 그 차이를 구별할 수 없습니다. 저자들은 이 특정하고 더 엄격한 조건을 충족하지 못한다면, 어떤 정교한 코딩도 당신을 구할 수 없음을 보여줍니다. 그것은 수학적 불가능성입니다.

또한 그들은 "부트스트래핑 가젯(bootstrapping gadget)"을 구축했습니다. 이것은 방금 깨어난 새로운 거주자를 위한 특별한 지침서라고 생각하면 됩니다. 이 지침서는 그들에게 과거의 투표를 어떻게 살펴보고, 누가 신뢰할 수 있는지 파악하며, 악당에게 속지 않고 현재 그룹에 합류할 것인지를 알려줍니다. 그들은 SR-HM 규칙이 준수된다면 이 가젯이 완벽하게 작동함을 증명했습니다.

반전: "사인 오프(Sign-Off)" 솔루션

저자들은 현실 세계의 시스템(예: 지분 증명 블록체인)에서 사람들이 그냥 공중으로 사라지지 않는다는 점을 깨달았습니다. 클럽을 떠나기로 결정할 때, 보통 자신의 "지분"(투표권)을 다른 사람에게 양도하는 트랜잭션에 서명해야 합니다.

저자들은 새로운 모델인 **사인 오프가 있는 DAR(DAR with Sign-Off)**을 제안했습니다.
이 모델에서 노드가 떠날 때는 다음을 수행해야 합니다:

1. "나는 떠나며, 나의 권한은 X에게 간다"라고 적힌 트랜잭션에 서명합니다.
2. 자신의 개인 키를 버립니다(Key Disposal).

이 간단한 행위는 모든 것을 바꿉니다. 노드가 키를 버리면, 악당은 더 이상 그 노드를 사용하여 과거에 투표하고 있었다고 가장할 수 없습니다. 떠난 사람들은 이제 "처분된(Disposed)" 상태가 되어 조작할 수 없으므로, "시뮬레이션 가능한" 그룹의 규모가 줄어듭니다.

이 규칙을 통해 시스템은 훨씬 더 안전하고 빨라집니다. 저자들은 이 시나리오를 위한 두 번째 가젯을 만들었습니다.

• 좋은 경우: 만약 누구도 속임수(이중 지불 등)를 쓰려 하지 않는다면, 새로운 거주자는 "작별" 노트와 양도 트랜잭션을 살펴봄으로써 현재의 투표자 명단을 파악할 수 있습니다. 이는 매우 빠르고 효율적입니다.
• 나쁜 경우: 만약 누군가 속임수(이중 지불)를 쓰고 있다면, 시스템은 이를 해결하기 위해 더 느린 투표 기반 방식으로 돌아갑니다.

이것이 왜 중요한가

이 논문은 근본적인 한계 검사입니다. 이는 우리가 모든 것을 가질 수는 없다는 점을 알려줍니다. 만약 우리가 개방적인 시스템을 원하고, 사람들이 잠드는 것을 허용하며, 멤버십이 변하는 것을 허용하려면, 우리는 반드시 현재 깨어 있는 매우 강력한 정직한 다수를 확보해야 합니다. 그렇지 않다면 시스템은 해킹될 운명입니다.

하지만 이 논문은 희망도 줍니다. "제대로 작별 인사를 하고 키를 버린다"는 하나의 현실적인 규칙을 추가함으로써, 우리는 시스템을 훨씬 더 견고하고 효율적으로 만들 수 있습니다. 이는 디지털 합의라는 혼란스러운 세상에서, 때로는 가장 단순한 규칙(예: "제대로 작별 인사를 하는 것")이 우리가 가진 가장 강력한 도구가 될 수 있음을 상명해 줍니다.

저자들은 단순히 추측한 것이 아니라, 이를 수학적으로 증명했습니다. 그들은 이러한 조건 없이는 합의가 불가능하며, 이 조건이 있다면 효율적으로 가능하다는 것을 보여주었습니다. 이것은 현실 세계의 혼돈 속에서도 살아남을 수 있는 차세대 디지털 마을 광장을 건설하기 위한 지도입니다.