a16z Crypto：무상태 블록체인 실현의 불가능성 탐구

원문 제목：상태 없는 블록체인의 불가능성에 대하여

저자：미란다 크리스트, 콜롬비아 대학교 CS 박사, a16z 여름 인턴 연구원 \& 조셉 보노, a16z 연구 파트너

편집：bayemon.eth, ChainCatcher

블록체인 기술 사용자 수의 증가와 그 위에서 발생하는 거래의 빈번함에 따라, 검증자가 거래를 검증하기 위해 저장해야 하는 정보량("상태")도 증가하고 있습니다. 예를 들어, 비트코인에서는 상태가 사용되지 않은 거래 출력(UTXO)의 집합으로 구성됩니다. 이더리움에서는 상태가 각 계정의 계좌 잔액과 각 스마트 계약의 코드 및 저장 공간을 포함합니다.

충분한 계정이나 UTXO를 가진 블록체인에 대해 이러한 저장 부담은 블록체인이 상당한 수의 사람들의 실제 일상 거래를 지원하기 어렵게 만들며, 이로 인해 이러한 사용자들은 검증자가 될 수 없고, 따라서 탈중앙화에 위협이 됩니다. Merkle Tree와 ZK와 같은 도구들이 블록체인이 놀라운 목표를 달성하는 데 도움을 주었기 때문에, 우리는 암호학을 통해 적절한 해결책을 찾고자 합니다.

이것이 바로 "상태 없는 블록체인"의 목표입니다. 그러나 이 분야에서 많은 작업이 이루어졌음에도 불구하고, 해당 솔루션은 여전히 실용화되지 않았습니다. 그러나 사실, 구조와 실용성 간의 메울 수 없는 간극 때문에 이러한 진전이 지연되는 것은 본질적인 문제로 보이며, 이는 모든 산업 발전 과정에서 자연스러운 장애물로 보입니다. 우리의 최신 연구는 "상태"를 관리하기 위한 추가 조치를 취하지 않는 한, 아무리 스마트한 상태 없는 블록체인 솔루션이라도 실행 가능하지 않다는 것을 보여줍니다. 그러나 본 문서의 끝에서 언급한 바와 같이, 결과가 실용적이지 않더라도 우리는 낙담해서는 안 됩니다.

상태 없는 것이란 무엇인가

현재 상태는 방대하지만 관리하기 쉽습니다. 예를 들어, 비트코인 노드는 약 7GB의 데이터를 저장하고, 이더리움 노드는 약 650GB의 데이터를 저장합니다. 그러나 전체 노드의 저장 부담은 체인의 처리량(초당 거래 수 또는 TPS)과 대략 선형적으로 증가하지만, 현재 메인 체인의 처리량은 실로 낮습니다. 현재 설계에 따르면, 실제 일상 거래(수만에서 수십만 TPS)를 지원하는 데 필요한 상태는 매우 방대하여 수 TB 또는 심지어 수 PB의 저장 공간이 필요합니다.

메인 체인의 제한된 성능은 검증자가 필요한 상태 양을 대폭 줄이기 위한 기술적 방법을 찾도록 유도합니다. 가장 좋은 기술적 방법은 상태 없는 블록체인을 구축하는 것입니다. 즉, 거래 처리량에 관계없이 검증자는 고정 크기의 상태만 저장하면 됩니다. (이 용어는 실제로 오해의 소지가 있습니다: 상태는 여전히 고정 크기로 존재하지만, 미래의 어떤 처리량에서도 정상적으로 작동할 수 있을 만큼 작습니다). 상태 없는 블록체인은 하드웨어의 저장 요구 사항을 대폭 줄여 검증자 노드를 운영하기 쉽게 만들며, 낙관적으로는 모든 사람이 휴대폰에서 노드를 운영할 수 있게 합니다. 검증자 수의 증가는 체인의 보안을 높이므로, 검증자의 진입 장벽을 낮추는 것이 매우 중요합니다.

Todd, Buterin, Boneh 및 Srinivasan과 같은 사람들이 상태 없는 블록체인에 대해 많은 연구를 했지만, 완전한 구현에는 여전히 거리가 있으며, 현재로서는 성공적으로 배포된 상태 없는 블록체인은 없습니다. 알려진 모든 상태 없는 블록체인의 근본적인 문제는 사용자가 추가 데이터를 저장해야 한다는 것입니다(이를 "증인 Witness"라고 함), 이는 검증자가 해당 계정과 관련된 거래를 검증하는 데 도움을 줍니다. 예를 들어, 이러한 증인은 사용자의 계정 및 잔액이 전역 상태 약속에 포함되어 있음을 나타내는 Merkle 포함성 증명일 수 있습니다. 사용자가 거래를 수행할 때, 그들은 검증자에게 해당 증명을 제출하여 자신의 계정에 충분한 잔액이 있음을 나타냅니다.

변경되지 않는 개인 키와 달리, 이러한 증인은 자주 변경되며, 적극적으로 거래하지 않는 사용자에게도 마찬가지로 적용되어 사용자가 상상할 수 없는 부담을 안겨줍니다. 만약 당신이 자신의 신용 카드를 사용하기 위해 전 세계의 모든 다른 신용 카드 거래를 지속적으로 모니터링하고, 그에 따라 일부 로컬 데이터를 업데이트해야 한다면, 이는 불필요한 문제를 일으킬 것입니다. 따라서 블록체인이 실용적으로 작동하려면 사용자가 오프라인 상태를 유지할 수 있어야 하며, 거래를 제출할 때만 블록체인과 상호작용해야 합니다. 이는 하드웨어 지갑을 포함한 여러 경우에서 증인을 완전히 업데이트할 수 없음을 의미합니다.

이로 인해 우리는 자연스럽게 연구 문제를 떠올리게 됩니다: 우리는 증인을 업데이트할 필요가 없는(또는 매우 적게 필요한) 상태 없는 블록체인을 구축할 수 있을까요? 이 질문에 답하기 위해, 우리는 상태 없는 블록체인을 일반화하는 새로운 이론적 프레임워크(철회 가능한 증명 시스템)를 개발했습니다. 이 프레임워크를 사용하여 우리는 명확한 불가능한 사건을 증명했습니다: 간결한 전역 상태와 빈번한 증인 업데이트 사이의 균형을 맞추는 것은 거의 불가능합니다. 우리의 증명 기술은 정보 이론적이며, 이는 미래의 컴퓨터가 이 문제를 해결할 만큼 강력하지 않을 것임을 의미합니다: 상태 없는 블록체인 구조와 실용성 간의 간극은 영원히 메울 수 없습니다.

연구 배경

위에서 언급한 "불가능한 사건"을 더 직관적으로 이해하기 위해, 우리는 먼저 Merkle Tree를 사용하여 상태 없는 블록체인의 자연스러운 방법을 설명하겠습니다(비록 Merkle Tree 기반 솔루션의 효율성이 높지 않더라도). 우리의 목표는 검증자가 사용자가 제출한 거래가 유효한지 확인하는 것입니다. 예를 들어, 사용자가 거래에 사용할 수 있는 충분한 계좌 잔액을 보유하고 있는지 확인하는 것입니다. 상태 없는 블록체인 솔루션에서 검증자는 고정 크기의 상태를 저장하며, 사용자가 거래를 수행할 때 그들의 거래는 증인을 포함해야 합니다. 검증자는 현재 상태와 사용자가 제출한(거래, 증인) 쌍을 사용하여 해당 사용자가 거래를 수행할 수 있는 충분한 계좌 잔액을 보유하고 있는지 확인할 수 있습니다.

우리는 먼저 Merkle Tree를 구축합니다. 여기서 각 쌍(계정 ID, 잔액) 키-값 쌍(a,b)은 트리의 잎입니다. 검증자가 저장하는 고정 크기의 상태 V는 이 트리의 루트이며, 계정-잔액 키-값 쌍의 약속 역할을 합니다. 각 사용자는 Merkle 포함 증명을 통해 자신의(계정 ID, 잔액) 정보를 유지해야 합니다. 잎(a,b)의 Merkle 포함 증명은 루트로 가는 경로의 노드 집합(v1, …, vk)으로 구성됩니다. 검증자는 (a,b)의 증명(v1, …, vk)과 현재 상태 V를 확인하여 b가 실제로 계정 a의 잔액인지 확인할 수 있습니다. Merkle Tree의 한 가지 특성은 잎의 Merkle 포함 증명이 주어지면, 잎이 변경될 때 결과 루트를 쉽게 계산할 수 있다는 것입니다. 다시 말해, 검증자는 거래 실행 후 계정 a의 새로운 잔액을 포착할 수 있는 업데이트된 상태 V'를 쉽게 계산할 수 있습니다.

그러나 Merkle Tree에는 두 가지 주요 단점이 있습니다. 첫째, 사용자 증인은 상대적으로 큽니다. 이는 시스템의 계정 총 수의 로그에 따라 증가합니다. 이상적으로는, 이들은 고정 크기여야 하며 RSA 누산기와 같은 솔루션을 사용하여 구현할 수 있습니다(본에 등은 상태 없는 블록체인에서 이에 대해 연구했습니다).

두 번째 단점은 피할 수 없습니다: 다른 사용자가 거래를 수행하는 한, 계정-잔액 키-값 쌍의 증명이 변경됩니다. 잎의 증명이 잎에서 루트로 가는 경로의 노드 집합으로 구성된다는 점을 기억해 보십시오. 다른 잎 중 하나라도 변경되면, 이러한 노드 중 하나도 변경됩니다. 이는 실제 문제를 야기합니다. 대부분의 블록체인 사용자는 자신의 코인을 지갑에 수동으로 보관하고, 거래를 하고 싶을 때만 온라인 상태가 되기를 원합니다. 그러나 이러한 상태 없는 블록체인의 실제 응용에서 사용자는 자신의 증인이 최신 상태인지 확인하기 위해 다른 사람의 거래를 지속적으로 모니터링해야 합니다. (비록 제3자가 사용자를 대신하여 모니터링할 수 있지만, 이는 표준 상태 없는 블록체인 모델에서 벗어납니다. 우리는 이 문제를 본 문서의 마지막에서 논의할 것입니다). 실제로, 이는 상태 없는 블록체인에게 극복하기 어려운 도전 과제가 되어 사용자에게 큰 부담을 안겨줍니다.

결론: 상태 없는 블록체인은 실현 불가능하다

이러한 현상은 Merkle Tree의 고유한 결함이 아닙니다. 현재 알려진 모든 상태 없는 블록체인 솔루션은 사용자가 해당 증인 정보를 자주 업데이트해야 한다고 요구합니다. 더 정확하게 말하면, 증인 정보를 업데이트해야 하는 사용자 수는 모든 사용자의 거래 총량과 대략 선형적으로 증가하며, 단조롭게 증가합니다.

이는 사용자 앨리스가 거래를 하지 않더라도, 그녀의 증인 정보가 다른 사용자의 거래에 따라 변경될 수 있음을 의미합니다. 검증자가 저장하는 간결한 상태가 전체 상태(즉, 모든 계좌 잔액의 집합)를 포착하기에는 너무 작다면, 간결한 상태 저장의 규모가 증가하는 것은 아무런 도움이 되지 않습니다. 우리는 이러한 암묵적인 관계를 시각화하면서, 다양한 처리량을 가진 블록체인이 매일 필요한 검증자 변경 횟수를 출력했습니다. 이러한 그래프는 최적의 상태 없는 블록체인에 필요한 증인 변경 횟수를 보여줍니다. 여기서 데이터 우주(data universes)는 계정 모델 하의 계정 총 수 또는 UTXO 모델 하의 UTXO 총 수를 의미합니다.

우리가 증명한 핵심은 정보 이론적 증명입니다. 클로드 섀넌이 공식적으로 제안한 정보 이론의 핵심 원칙은 다음과 같습니다: 만약 앨리스가 크기가 2n인 집합에서 무작위로 객체를 선택하고, 그녀의 선택을 밥에게 알리고자 한다면, 그녀는 최소한 n 비트를 밥에게 전송해야 합니다. 만약 상태 없는 블록체인 솔루션이 존재하고 사용자가 증인을 업데이트할 필요가 없다면, 앨리스는 n 비트보다 적은 비용으로 밥에게 그녀의 구체적인 선택을 알릴 수 있습니다. 그러나 섀넌은 이것이 불가능하다고 증명했습니다. 따라서 우리는 그러한 상태 없는 블록체인이 존재할 수 없다고 생각합니다.

간단히 하기 위해, 우리는 사용자가 영원히 증인을 업데이트할 필요가 없는 상태 없는 블록체인이 존재할 수 없다는 약화된 증명을 먼저 제시합니다. 증명의 핵심 과정은 앨리스가 상태 없는 블록체인 솔루션을 사용하여 그녀의 정보를 밥에게 인코딩하여 전송하는 것입니다. 처음에 앨리스와 밥은 모든 n명의 사용자의 모든 계정-잔액 쌍을 알고 있으며, 각 계정 잔액은 최소한 1이라고 가정합니다. 또한, 앨리스와 밥은 상태 없는 블록체인의 간결한 상태 V와 모든 계정 잔액 쌍(ai, bi)의 증인 wi를 알고 있으며, 두 사람은 정보와 계정 집합 간의 매핑에 대해 합의합니다. 앨리스는 그녀의 정보에 해당하는 계정 A의 집합을 선택하고, 계정 잔액을 사용하여 소비한 후, 최종적으로 상태 없는 블록체인을 사용하여 밥에게 그녀가 선택한 계정 집합을 전달합니다. 밥은 이 계정 집합에서 그녀의 정보가 무엇인지 알 수 있습니다.

인코딩: 앨리스는 상태 없는 블록체인 솔루션을 사용하여 업데이트된 상태 V'를 계산하고, 이를 밥에게 전송합니다.

디코딩: 각 i에 대해, 밥은 Verify(wi,(ai,bi))를 확인합니다. 밥은 Verify(wi, (ai, bi)) = false가 되는 계정 집합 B를 출력합니다.

결국, 밥은 앨리스가 선택한 동일한 집합을 성공적으로 출력하게 되며, 즉 B = A입니다. 먼저, 앨리스가 계정 ai에서 동전을 소비했다면, 그녀의 이전 잔액에 대한 증인은 더 이상 수용되어서는 안 됩니다. 그렇지 않으면 앨리스는 중복 소비를 할 수 있습니다. 따라서 A에 있는 각 계정 ai에 대해 Verify(wi, (ai, bi)) = false가 되어야 하며, 밥은 이 계정을 B에 포함시킵니다. 반면에, 밥은 잔액이 변하지 않는 계정을 B에 포함시키지 않을 것입니다. 왜냐하면 이러한 계정의 잔액은 변하지 않으며, (우리가 증명해야 할 "약화된" 진술을 기억해 보십시오) 이들의 증인은 영원히 변하지 않기 때문입니다. 따라서 B는 정확히 A와 같습니다.

마지막으로, 우리는 앨리스가 밥에게 전송해야 했던 비트 수를 계산하여 모순을 도출합니다. 그녀가 선택할 수 있는 계정의 하위 집합은 2n개가 있으며, 따라서 섀넌 법칙에 따르면 그녀는 최소한 n 비트를 밥에게 전송해야 합니다. 그러나 그녀는 고정 크기의 상태 V'만 전송했으며, 이는 n 비트보다 훨씬 짧습니다.

(암호학에 익숙한 독자는 우리가 여기서 몇 가지 세부 사항을 생략했음을 주목할 수 있습니다. 예를 들어, 디코딩 실패 확률은 무시할 수 있습니다. 우리의 논문에는 완전한 증명이 포함되어 있습니다).

우리가 상태 없는 블록체인을 사용하여 우리의 증명을 설명했지만, 앨리스와 밥은 다양한 인증 데이터 구조(누산기, 벡터 약속 및 인증된 사전 등)를 사용하여 유사한 효율적인 통신을 수행할 수 있습니다. 우리는 이러한 데이터 구조를 형식화하기 위해 새로운 추상 개념인 철회 가능한 증명 시스템(revocable proof system)을 사용합니다.

결론의 의미

위의 결과는 우리가 "암호 기술로 상태를 완전히 제거할 수 없다"는 것을 보여주며, 따라서 사용자가 영원히 증인을 업데이트할 필요가 없는 상태 없는 블록체인을 구축할 수 있는 쉬운 솔루션이 없음을 의미합니다. 상태는 사라지지 않으며, 검증자로부터 사용자에게 빈번하게 업데이트되는 증인의 형태로 전이됩니다.

현재 엄격한 상태 없는 블록체인 모델에서 벗어난 몇 가지 합리적인 해결책이 존재합니다. 이러한 모델에 대한 자연스러운 완화 중 하나는 제3자(사용자도 검증자도 아님)가 전체 상태를 저장하는 것을 허용하는 것입니다. 이 쪽은 증명 서비스 노드(proof service node)라고 불리며, 이는 전체 상태를 사용하여 사용자를 대신해 최신 증인을 생성합니다. 그런 다음 사용자는 이러한 증인을 사용하여 거래를 수행할 수 있으며, 일반 상태 없는 블록체인에서와 마찬가지로 검증자는 여전히 간결한 상태만 저장합니다. 이 시스템의 인센티브 메커니즘, 특히 사용자가 증명 서비스 노드에 어떻게 보상할 것인가는 흥미로운 개방 연구 방향입니다.

지금까지의 논의가 주로 L1 블록체인에 집중되었지만, 우리의 결과는 롤업(roll up)과 같은 L2 시스템에도 영향을 미칠 것입니다. 낙관적(Optimistic) 또는 zk 롤업의 경우, 일반적으로 더 큰 상태 값을 생성하고, 해당 수단을 통해 L1에 작은 값을 제출하고 저장합니다. 우리는 이러한 사용자가 L2 서버의 협조 없이 직접 계좌 잔액 증인을 통해 L1에서 자금을 인출할 수 있기를 바랍니다. 우리의 모델에서 이러한 설정은 철회 가능한 증명 시스템의 한 예입니다. 사실, 상태 없는 블록체인은 이미 L2 롤업의 형태로 실현되었다고 할 수 있습니다.

하지만 유감스럽게도, 우리의 "불가능한 사건"은 직접적으로 적용될 수 없습니다. 사용자의 롤업 철회 증인은 지속적으로 변경되고 동기화되어야 하며, 그렇지 않으면 거의 전체 L2 상태가 L1에 모두 기록되어야 합니다. 따라서 현재의 롤업 솔루션은 일반적으로 데이터 가용성 위원회(data availability committee)를 설정하며(때때로 "validium"이라고 불림), 이는 사용자가 철회할 준비가 되었을 때 새로운 증인을 계산하는 데 도움을 주는 "증명 서비스 노드"와 유사한 기능을 수행합니다. 우리의 연구 결과는 거래 데이터에 접근할 수 없다면 사용자가 자금 소유권을 증명하고 인출을 수행하는 데 필요한 Merkle Tree를 계산할 수 없음을 보여줍니다. 이는 이더리움 문서에서 사용자에게 항상 적용되는 경고입니다.

블록체인 시스템의 발전과 함께, 더 효율적인 블록체인 상태 관리 방법을 개발하는 것이 점점 더 중요해질 것입니다. 비록 우리의 연구가 상태 없는 블록체인이 실용화될 수 없다는 결과가 부정적으로 보일 수 있지만, 이 결론은 블록체인 설계자에게 여전히 의미가 있습니다. 왜냐하면 이는 연구의 초점을 다른 곳으로 옮기고, 가능한 해결책을 더 빨리 찾는 데 도움이 될 수 있기 때문입니다.