a16z: "상태 없는 블록체인"의 불가능성에 대하여
저자: Miranda Christ, Joseph Bonneau
번역: TechFlow
블록체인에서 더 많은 사용자와 더 빈번한 거래를 지원함에 따라 검증자가 거래를 검증하기 위해 저장해야 하는 정보(즉, '상태')의 양도 증가한다. 예를 들어 비트코인에서는 상태가 미사용 거래 출력(UTXO) 집합으로 구성된다. 이더리움에서는 각 계정의 잔액과 각 스마트 계약의 코드 및 저장소로 구성된다.
계정 또는 UTXO 수가 인구 대부분의 일상적 거래를 실제로 지원할 만큼 커지게 되면 이러한 저장 부담은 통제 불가능해지고, 검증자 노드 운영이 어려워지며 탈중앙화에 위협이 된다. 매력적인 해결책은 머클 트리(Merkle tree)나 제로지식 증명(zero-knowledge proof) 같은 도구를 통해 과거에는 상상조차 할 수 없었던 일을 가능하게 해주는 암호학 기반 접근법이다.
이것이 바로 '무상태(stateless) 블록체인'의 목표다. 그러나 많은 연구에도 불구하고 무상태 블록체인은 여전히 실용성에서 멀다. 더욱이 이런 진전의 지연은 본질적인 문제이며, 구현 가능성과 실용성 사이의 격차는 결코 메워질 수 없다. 최근의 우리의 연구는 추가적인 상태 관리 조치 없이는, 아무리 정교한 설계라도 무상태 블록체인 방식은 실행 불가능하다는 것을 보여준다. 그러나 본문 마지막에서 보여주겠지만, 이러한 불가능성 결과가 낙심할 이유는 아니다.
무상태
현재 상태는 크기는 크지만 관리 가능한 수준이다. 예를 들어 비트코인 노드는 약 7GB의 데이터를 저장하고, 이더리움 노드는 약 650GB의 데이터를 저장한다. 그러나 전체 노드의 저장 부담은 체인 처리량(초당 거래 수, TPS)과 대략적으로 선형적으로 증가하며, 현재의 처리량은 여전히 받아들일 수 없는 수준이다. 현재 설계에 따르면 일상 거래를 진정으로 지원하려면 초당 수만에서 수십만 건의 거래를 처리해야 하며, 이 경우 상태는 기가바이트에서 페타바이트 규모의 저장 공간이 필요해져 통제 불가능한 수준이 된다.
이러한 이유로 검증자가 필요한 상태의 양을 크게 줄일 수 있는 기술적 방법을 찾으려는 노력이 있었다. 핵심은 검증자가 처리량에 관계없이 항상 일정한 크기의 상태만 저장하도록 하는 '무상태 블록체인'을 구현하는 것이다. (사실 이 용어는 다소 잘못된 명칭인데, 여전히 상태는 존재하지만 충분히 작아서 미래의 어떤 처리량에서도 실용적인 수준이기 때문이다—보통 일정한 크기이다.) 이러한 경량 저장 요구 사항은 검증자 노드 운영을 훨씬 쉽게 만들 것이며, 낙관적으로 말하면 누구나 자신의 휴대폰에서 노드를 실행할 수 있게 될 것이다. 검증자 수를 늘리는 것은 체인의 보안성을 높이므로, 검증자 참여 장벽을 낮추는 것이 중요하다.
무상태 블록체인에 대한 많은 연구(예: Todd, Buterin, Boneh 등과 Srinivasan 등의 연구)에도 불구하고, 아직 실용화까지는 매우 멀고, 우리가 아는 한 배포된 사례는 없다. 알려진 모든 무상태 블록체인의 근본적인 문제는 사용자가 자신의 계정과 관련된 거래를 검증자가 검증할 수 있도록 돕기 위해 '증거(witness)'라 불리는 추가 데이터를 저장해야 한다는 점이다. 예를 들어 이 증거는 사용자의 계정과 잔액이 전역 상태 커밋에 포함되어 있다는 것을 보여주는 머클 포함 증명일 수 있다. 사용자가 거래를 수행할 때 이 증거를 검증자에게 제출하여 자신의 계정에 충분한 잔액이 있음을 입증하는 것이다.
비밀키 저장은 영원히 변경할 필요가 없지만, 이 증거는 활발한 거래를 하지 않는 사용자조차도 자주 변경되어 비현실적인 부담을 준다. 마치 당신이 전 세계 다른 모든 신용카드 거래를 계속 모니터링하면서 그에 맞춰 로컬 데이터를 업데이트해야만 자신의 카드를 쓸 수 있다고 상상해보라. 블록체인이 실용적이려면 사용자는 오프라인 상태로 있어야 하며, 거래를 제출할 때만 블록체인과 상호작용할 수 있어야 한다. 하드웨어 지갑과 같은 경우, 증거를 업데이트하는 것은 단순히 불편한 것을 넘어 불가능한 경우도 많다.
이러한 상황은 자연스럽게 다음 연구 질문을 제기한다. 사용자가 증거를 자주 업데이트하지 않아도 되는 무상태 블록체인(또는 거의 업데이트하지 않는 블록체인)을 만들 수 있을까? 이 질문에 답하기 위해 우리는 무상태 블록체인을 일반화하는 새로운 이론적 프레임워크('철회 가능한 증명 시스템')를 개발했다. 이 프레임워크를 이용해 우리는 불가능성 결과를 증명했는데, 즉 간결한 전역 상태와 빈번한 증거 업데이트 사이의 트레이드오프는 본질적으로 조율하기 어렵다는 것이다. 우리의 증명 기법은 정보 이론적(information-theoretic)이며, 이는 미래의 컴퓨터조차도 이 문제를 해결할 능력이 없다는 의미다. 무상태 블록체인의 구성과 실용성 사이의 격차는 영원히 메워질 수 없다.
우리 연구의 배경
우리의 불가능성 결과를 이해하기 위해 먼저 머클 트리를 사용해 무상태 블록체인을 구축하는 자연스럽지만 비효율적인 방법을 설명하겠다. 우리의 목표는 검증자가 사용자가 제출한 거래가 유효한지 판단할 수 있도록 하는 것이다. 예를 들어 사용자가 거래를 수행할 충분한 계정 잔액을 가지고 있는지를 확인하는 것이다. 무상태 블록체인 방식에서 검증자는 일정한 크기의 상태만 저장한다. 사용자가 거래를 수행할 때, 그는 거래와 함께 증거를 포함해야 한다. 검증자는 현재 상태와 사용자가 제출한 (거래, 증거) 쌍을 이용해 해당 사용자가 거래를 수행할 충분한 잔액을 가지고 있는지 검증할 수 있다.
먼저 각 (계정 ID, 잔액) 쌍 (a, b)을 리프 노드로 포함하는 머클 트리를 구성한다. 검증자가 저장하는 일정한 크기의 상태 V는 이 트리의 루트로서, 일련의 계정 잔액 쌍에 대한 커밋 역할을 한다. 각 사용자는 자신의 증거를 머클 포함 증명으로 유지한다. 리프 (a, b)의 머클 포함 증명은 그 리프에서 트리 루트까지의 경로 상에 있는 형제 노드 (v1, ..., vk)로 구성된다. 계정 a가 주장하는 잔액 b로 거래를 수행한다고 가정할 때, 검증자는 (a, b)에 대한 증명 (v1, ..., vk)과 현재 상태 V를 비교하여 b가 실제로 계정 a의 잔액인지 검증할 수 있다. 만약 그렇다면 검증자는 거래를 실행하고 해당 계정의 잔액을 업데이트해야 한다. 머클 트리의 편리한 특징 중 하나는 리프의 머클 포함 증명을 주어졌을 때 그 리프가 변경되었을 때 결과 루트를 쉽게 계산할 수 있다는 점이다. 즉, 검증자는 계정 a의 새 잔액을 반영하는 업데이트된 상태 V'를 쉽게 계산할 수 있다.
이 머클 트리 방식은 두 가지 주요 단점이 있다. 첫째, 사용자의 증거는 시스템 내 전체 계정 수의 로그에 비례해 상대적으로 크다. 이상적으로는 일정한 크기여야 하며, RSA 어큐뮬레이터(RSA accumulator)와 같은 방식으로 이를 달성할 수 있다.
두 번째 단점은 더 피하기 어렵다. 다른 사용자가 거래를 할 때마다 계정 잔액 쌍에 대한 증거가 바뀐다. 리프 노드의 증거는 그 리프에서 트리 루트까지의 경로 상의 형제 노드들로 구성됨을 상기하라. 다른 리프 노드가 변경되면 그 중 하나의 노드도 변경되고, 이는 실제 문제를 야기한다. 대부분의 블록체인 사용자는 자신의 코인을 지갑에 수동적으로 보관하고 싶어하며, 거래를 하고 싶을 때만 온라인 상태가 된다. 그러나 이 무상태 블록체인에서는 사용자가 다른 사람들의 거래를 끊임없이 모니터링하여 자신의 증거를 최신 상태로 유지해야 한다. 제3자가 사용자를 대신해 이 모니터링을 수행할 수는 있지만, 이는 표준 무상태 블록체인 모델에서 벗어난다. 실제로 이것은 무상태 블록체인에 대해 극복할 수 없는 도전이며, 사용자에게 큰 부담을 준다.
우리의 결론: 무상태는 불가능하다
이 현상은 단지 이 머클 트리 구조에만 국한되지 않는다. 알려진 모든 무상태 블록체인 방식은 사용자가 자신의 증거를 빈번하게 업데이트하도록 요구하며, 우리는 여기서 이를 증명한다. 보다 정확히 말하면, 증거를 업데이트해야 하는 사용자 수는 모든 사용자가 수행하는 거래 총수와 대략적으로 선형적으로 증가한다는 것을 보여준다.
이 말은 사용자 앨리스가 아무런 거래도 하지 않더라도, 다른 사용자의 거래에 따라 그녀의 증거가 변경되어야 할 수 있다는 의미다. 검증자가 저장하는 간결한 상태가 너무 작아 전체 상태(즉, 모든 계정 잔액의 집합)를 포착할 수 없는 한, 간결한 상태의 크기를 늘리는 것은 거의 도움이 되지 않는다. 아래 그래프는 우리의 정리에 따라 증거 변경 횟수와 블록체인 처리량에 따른 하루 동안 필요한 증거 변경 수를 나타낸다. 이 그래프는 최선의 무상태 블록체인이 필요로 하는 증거 변경 횟수를 보여준다. 여기서 '데이터 우주(data universe)'란 계정 모델에서는 전체 계정 수를, UTXO 모델에서는 전체 UTXO 수를 의미한다.
우리의 증명의 핵심은 정보 이론적 논증이다. 클로드 섀넌(Claude Shannon)이 공식화한 정보 이론의 핵심 원칙은, 앨리스가 크기가 2ⁿ인 집합에서 임의의 객체를 선택하고 밥(Bob)에게 자신이 무엇을 선택했는지 알려주려면, 적어도 n비트를 보내야 한다는 것이다. 만약 사용자들이 거의 증거를 업데이트하지 않는 무상태 블록체인 방식이 존재한다면, 앨리스는 n비트보다 적은 비트로 밥에게 자신이 무엇을 선택했는지 전달할 수 있으며, 이는 섀넌이 증명한 것처럼 불가능하다. 따라서 그러한 무상태 블록체인은 존재할 수 없다.
간단함을 위해 여기서는 약간 약화된 명제의 증명을 설명하겠다: 사용자가 절대로 증거를 업데이트할 필요가 없는 무상태 블록체인은 존재하지 않는다. 핵심은 앨리스가 무상태 블록체인 방식을 사용해 메시지를 인코딩하여 밥에게 전송한다는 점이다. 처음에 앨리스와 밥은 n명의 사용자에 대한 전체 계정 잔액 쌍 집합을 알고 있다. 또한 각 계정은 최소한 하나의 코인을 가지고 있다고 가정하자. 앨리스와 밥은 무상태 블록체인의 간결한 상태 V와 모든 계정 잔액 쌍 (ai, bi)에 대한 증거 wi도 알고 있다. 또한 앨리스와 밥은 메시지와 계정 집합 사이의 매핑을 미리 정의한다. 앨리스는 자신의 메시지에 해당하는 계정 집합 A를 선택한 후, 그 계정들에서 코인을 소비한다. 그녀는 무상태 블록체인을 사용해 밥에게 자신이 선택한 집합을 전달하고, 밥은 그 집합을 통해 그녀의 메시지를 알아낼 수 있다.
인코딩: 앨리스는 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와 같다.
마지막으로 우리가 도달한 모순을 해결하기 위해 앨리스가 밥에게 보내야 하는 비트 수를 계산한다. 앨리스가 선택할 수 있는 부분집합은 2ⁿ개이므로, 섀넌의 법칙에 따라 적어도 n비트를 보내야 한다. 그러나 그녀는 상수 크기의 상태 V'만을 보냈으며, 이는 n비트보다 훨씬 짧다.
우리가 설명할 때 무상태 블록체인을 사용했지만, 앨리스와 밥은 어큐뮬레이터, 벡터 커밋먼트, 인증된 사전(authenticated dictionary) 등을 포함한 다양한 다른 인증된 데이터 구조를 사용해 유사한 효율적인 통신을 수행할 수 있다. 우리는 이러한 데이터 구조를 형식화하기 위해 '철회 가능한 증명 시스템'이라는 새로운 추상 개념을 사용한다.
결과의 함의
우리의 결과는 '암호학으로 상태를 제거하는' 것은 불가능하다는 것을 보여준다. 사용자가 절대 증거를 업데이트할 필요가 없는 무상태 블록체인을 구축할 수 있게 해주는 마법 같은 커밋 방식은 존재하지 않는다. 상태는 사라지지 않고, 검증자로부터 사용자에게 빈번한 증거 업데이트라는 형태로 전가될 뿐이다.
엄격한 무상태 블록체인 모델에서 벗어나는 또 다른 유망한 해결책들도 존재한다. 이 모델의 자연스러운 완화는 제3자(사용자도 검증자도 아닌)가 전체 상태 저장을 담당하도록 허용하는 것이다. 이 '증명 서비스 노드(proof service node)'라 불리는 제3자는 전체 상태를 사용해 사용자에게 최신 증거를 생성한다. 그 후 사용자는 검증자가 여전히 간결한 상태만 저장하는 일반적인 무상태 블록체인과 동일하게 이 증거를 사용해 거래를 수행할 수 있다. 이 시스템의 인센티브 메커니즘, 특히 사용자가 증명 서비스 노드에 어떻게 보상을 제공하는지 여부는 흥미로운 열린 연구 주제이다.
지금까지의 논의는 L1 블록체인에 초점을 맞췄지만, 우리의 결과는 롤업 서버와 같은 L2 시스템에도 영향을 미친다. 롤업(Optimistic이든 ZK든)은 일반적으로 작은 값을 사용해 L1에 큰 상태의 커밋을 저장한다. 이 상태에는 L2의 각 사용자 계정이 포함된다. 우리는 사용자가 L2 서버의 협력 없이 직접 L1에서 자금을 인출할 수 있기를 바라며, 이를 위해 자신의 현재 계정 잔액에 대한 증거를 게시한다. 이 설정 역시 우리 모델에서 '철회 가능한 증명 시스템'의 한 사례이다. 사실상 무상태 블록체인은 이미 L2 롤업 형태로 실천되고 있다고 볼 수 있다.
그러나 불행히도 이는 우리의 불가능성 결과가 직접 적용된다는 의미이기도 하다. 사용자의 롤업 인출 증거는 자주 변경되어야 하며, 그렇지 않으면 거의 전체 L2 상태를 L1에 기록해야 한다. 따라서 현재의 롤업들은 일반적으로 데이터 가용성 위원회(data availability committee)(때로는 'validium'이라 불림)가 존재한다고 가정하는데, 이는 '증명 서비스 노드'와 유사하게 사용자가 인출을 준비할 때 새로운 증거를 계산하는 것을 도와준다. 우리의 결과는 이더리움 문서에서 사용자에게 경고하는 "거래 데이터가 없다면, 사용자는 자금에 대한 소유권을 입증하고 인출을 수행하기 위한 머클 증명을 계산할 수 없다"는 내용이 항상 유효하다는 것을 시사한다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
a16z
