a16z: 상태 없는 블록체인의 불가능성에 대하여

원래 Miranda Christ와 Joseph Bonneau가 작성했습니다.

원문 편집: Deep Tide TechFlow

블록체인이 더 많은 사용자와 더 빈번한 트랜잭션을 지원함에 따라 유효성 검사기가 트랜잭션을 확인하기 위해 저장하는 정보(또는 상태)의 양이 늘어납니다. 예를 들어, 비트코인에서 상태는 사용되지 않은 트랜잭션 출력(UTXO) 세트로 구성됩니다. 이더리움에서 상태는 각 계정의 계정 잔액과 각 스마트 계약의 코드 및 저장 공간으로 구성됩니다.

블록체인이 인구의 상당 부분에 대한 실제 일일 거래를 지원하기에 충분한 계정 또는 UTXO로 성장함에 따라 이러한 저장 부담은 관리하기 어려워지고 검증자가 되기가 어려워지고 분산화에 위협이 됩니다. 흥미로운 해결책은 머클 트리 및 영지식 증명과 같은 도구를 사용하여 이전에는 상상할 수 없었던 일을 달성하는 데 도움이 되는 암호화로 전환하는 것입니다.

이것이 바로 상태 비저장 블록체인의 목표입니다. 그러나 이에 대한 광범위한 연구에도 불구하고 여전히 실용적이지 않습니다. 그러나 이러한 진행 지연은 본질적인 것으로 밝혀졌습니다. 이러한 빌드와 실용성 사이의 격차는 결코 메워지지 않을 것입니다. 우리의 최근 연구에 따르면 상태 비저장 블록체인 제안은 아무리 영리하더라도 상태를 관리하기 위한 추가 조치 없이는 실현 가능하지 않습니다. 하지만 이 글의 끝 부분에서 보여주듯이, 이러한 결과가 일어날 가능성이 낮다고 해서 낙담해서는 안 됩니다.

상태 없음

오늘날 상태는 거대하지만 관리가 가능합니다. 예를 들어 비트코인 ​​노드는 약 7GB의 데이터를 저장하고 이더리움 노드는 약 650GB의 데이터를 저장합니다. 그러나 전체 노드의 스토리지 부담은 체인의 처리량(초당 트랜잭션 또는 TPS)에 따라 대략 선형적으로 확장되는데, 이는 오늘날에도 여전히 허용할 수 없는 수준입니다. 현재 설계된 대로 일상적인 트랜잭션(초당 수만에서 수십만 트랜잭션)을 실제로 지원하는 데 필요한 상태는 관리하기 어려워져 기가바이트 또는 심지어 페타바이트의 스토리지가 필요하게 됩니다.

이는 사람들이 검증자에게 필요한 상태의 양을 크게 줄이는 기술적 방법을 찾도록 동기를 부여했습니다. 중요한 것은 상태 비저장 블록체인을 구현하는 것입니다. 이를 위해서는 검증인이 거래 처리량에 관계없이 일정한 크기의 상태만 저장해야 합니다. (실제로 이 용어는 잘못된 명칭입니다. 여전히 상태가 있고, 충분히 작기 때문에 어떤 미래에도 실용적일 수 있습니다. 처리량 - 일반적으로 일정한 크기). 이러한 경량 스토리지 요구 사항을 통해 검증자 노드를 더 쉽게 실행할 수 있으며, 낙관적으로는 모든 사람이 휴대폰에서 노드를 실행할 수 있습니다. 검증인의 수를 늘리면 체인의 보안이 향상되므로 검증인의 진입 장벽을 낮추는 것이 중요합니다.

상태 비저장 블록체인(예: Todd, Buterin, Boneh et al. 및 Srinivasan et al.)에 대한 많은 연구에도 불구하고 실용적이지 않으며 우리가 아는 한 아무것도 배포되지 않았습니다. 알려진 모든 상태 비저장 블록체인의 근본적인 문제는 사용자가 검증인이 자신의 계정과 관련된 거래를 확인할 수 있도록 증인이라는 추가 데이터를 저장해야 한다는 것입니다. 예를 들어, 이 증인은 사용자의 계정과 잔액이 글로벌 상태 약속에 포함되어 있음을 보여주는 Merkle 포함 증명일 수 있습니다. 사용자가 거래를 할 때 이 증인을 유효성 검사기에 제출하여 계정 잔액이 충분하다는 것을 보여줍니다.

결코 변경할 필요가 없는 개인 키를 저장하는 것과는 달리, 이러한 증인은 적극적으로 거래하지 않는 사용자의 경우에도 자주 변경되므로 사용자에게 비현실적인 부담을 줍니다. 마찬가지로, 전 세계적으로 다른 모든 신용 카드 거래를 지속적으로 모니터링하고 그에 따라 일부 로컬 데이터를 업데이트하여 자신의 신용 카드를 사용한다고 상상해 보십시오. 블록체인이 실용적이려면 사용자는 거래를 제출할 때만 오프라인으로 블록체인과 상호 작용할 수 있어야 합니다. 하드웨어 지갑과 같은 많은 경우 증인 업데이트는 불편할 뿐만 아니라 불가능합니다.

이는 우리에게 자연스러운 연구 질문으로 이어집니다. 빈번한 증인 업데이트가 필요하지 않은(또는 드물게 증인 업데이트만 필요한) 상태 비저장 블록체인을 구축할 수 있습니까? 이 질문에 답하기 위해 우리는 상태 비저장 블록체인을 일반화하는 새로운 이론적 프레임워크(취소 가능 증명 시스템)를 개발합니다. 이 프레임워크를 사용하여 우리는 있을 법하지 않은 결과를 보여줍니다. 컴팩트한 전역 상태와 빈번한 증인 업데이트 간의 균형은 본질적으로 조정하기 어렵습니다. 우리의 증명 기술은 정보 이론적입니다. 즉, 미래의 컴퓨터는 이 문제를 해결할 만큼 강력하지 않을 것입니다. 무상태 블록체인 구축과 실용성 사이의 격차는 결코 메워지지 않을 것입니다.

연구 배경

불가능성 결과를 이해하는 데 도움을 주기 위해 먼저 Merkle 트리를 사용하여 상태 비저장 블록체인을 구축하는 자연스러우면서도 비효율적인 방법을 설명합니다. 우리의 목표는 검증인이 사용자가 제출한 거래가 유효한지 여부(예: 사용자의 계정 잔액이 거래를 완료하기에 충분한지 여부)를 확인할 수 있도록 하는 것입니다. 상태 비저장 블록체인 체계에서 검증자는 일정한 크기의 상태를 저장합니다. 사용자가 거래를 할 때 거래에 증인을 포함해야 합니다. 검증인은 현재 상태와 사용자가 제출한 (트랜잭션, 증인) 쌍을 사용하여 사용자가 거래를 할 수 있는 충분한 계정 잔액을 가지고 있는지 확인할 수 있습니다.

먼저 각 (계정 ID, 잔액) 쌍 (a, b)이 리프 노드로 포함되는 Merkle 트리를 구축합니다. 검증인이 저장한 고정 크기 상태 V는 이 트리의 루트이며 계정 잔액 쌍 세트에 대한 약속 역할을 합니다. 각 사용자는 Merkle 포함 증명으로 증인을 유지합니다. 리프(a,b)에 대한 Merkle 포함 증명은 해당 리프에서 트리 루트까지의 경로를 따라 있는 파트너 노드(v1,...,vk)로 구성됩니다. 계정 a에 의한 거래와 청구된 잔액 b가 주어지면 검증자는 현재 상태 V에 대해 (a,b)의 증명 (v1,...,vk)을 확인하여 b가 실제로 계정 a의 잔액인지 확인할 수 있습니다. 그렇다면 검증인은 거래를 실행하고 이에 따라 계정 잔액을 업데이트해야 합니다. Merkle 트리의 편리한 속성은 리프에 대한 Merkle 포함 증명이 주어지면 해당 리프가 변경될 때 결과의 근을 쉽게 계산할 수 있다는 것입니다. 즉, 검증자는 트랜잭션이 실행된 후 계정 a의 새로운 잔액을 캡처하는 업데이트된 상태 V를 쉽게 계산할 수 있습니다.

이 머클 트리 방식에는 두 가지 주요 단점이 있습니다. 첫째, 사용자의 증인은 상대적으로 크며 시스템의 총 계정 수에 따라 대수적으로 증가합니다. 이상적으로는 크기가 일정해야 하며 RSA 누산기와 같은 체계를 사용하여 이를 달성할 수 있습니다.

두 번째 단점은 피하기가 더 어렵습니다. 다른 사용자가 거래를 할 때마다 계정 잔액 쌍의 증거가 변경됩니다. 리프 노드의 증명은 해당 리프 노드에서 트리 루트까지의 경로에 있는 파트너 노드로 구성된다는 점을 기억하세요. 다른 리프 노드가 변경되면 노드 중 하나가 변경되어 실제 문제가 발생합니다. 대부분의 블록체인 사용자는 자신의 코인을 지갑에 수동적으로 보관하고 거래를 원할 때만 온라인에 접속하기를 원합니다. 그러나 이러한 상태 비저장 블록체인에서 사용자는 증인 정보를 최신 상태로 유지하기 위해 다른 사람의 거래를 지속적으로 모니터링해야 합니다. 제3자가 사용자를 대신하여 이러한 모니터링을 수행할 수 있지만 이는 표준 상태 비저장 블록체인 모델에서 벗어납니다. 실제로 이는 무상태 블록체인의 경우 극복할 수 없는 과제이며 사용자에게 큰 부담을 줍니다.

우리의 결론: 무국적은 불가능합니다

이 현상은 이러한 종류의 머클 트리 구조에만 적용되는 것이 아닙니다. 알려진 모든 무상태 블록체인 체계에서는 사용자가 증인 정보를 자주 업데이트해야 합니다. 여기서는 이에 대해 설명합니다. 보다 정확하게는 증인 정보를 업데이트해야 하는 사용자의 수가 모든 사용자가 수행한 총 거래 수에 대략 선형적으로 증가한다는 것을 보여줍니다.

이는 사용자 Alice가 어떠한 거래도 하지 않더라도 다른 사용자의 거래에 따라 그녀의 증인 정보가 변경되어야 할 수도 있음을 의미합니다. 검증인이 저장한 컴팩트 상태가 전체 상태(예: 모든 계정 잔액 세트)를 캡처하기에는 너무 작은 경우 컴팩트 상태 크기를 늘리는 것은 거의 도움이 되지 않습니다. 우리는 처리량이 서로 다른 블록체인에 대해 하루에 필요한 증인 변경 수와 함께 우리의 정리를 기반으로 아래에 표시된 이 관계를 플롯합니다. 이 그래프는 최적의 무상태 블록체인이 증인 정보를 변경해야 하는 횟수를 보여줍니다. 여기서 데이터 유니버스는 계정 모델의 총 계정 수 또는 UTXO 모델의 총 UTXO 수를 의미합니다.

우리 증명의 핵심은 정보이론적 논증입니다. 클로드 섀넌(Claude Shannon)이 공식화한 정보 이론의 중심 교리는 앨리스가 크기 2n의 집합에서 무작위로 개체를 선택하고 밥에게 자신이 선택한 개체를 알리고자 한다면 적어도 n 비트를 그에게 보내야 한다는 것입니다. 사용자가 자신의 증인 정보를 거의 업데이트하지 않는 상태 비저장 블록체인 체계가 존재하는 경우 Alice는 Bob에게 자신이 선택한 객체를 n 비트 미만으로 알려줄 수 있습니다. 이는 Shannon이 입증한 것처럼 불가능합니다. 따라서 이러한 무상태 블록체인은 존재하지 않습니다.

단순화를 위해 여기서는 약간 약한 진술의 증거를 설명합니다. 즉, 사용자가 자신의 증인 정보를 업데이트할 필요가 없는 상태 비저장 블록체인은 없습니다. 요점은 Alice가 상태 비저장 블록체인 체계를 사용하여 Bob에게 보내는 메시지를 인코딩한다는 것입니다. 처음에 Alice와 Bob은 모두 n명의 사용자에 대한 전체 계정 잔액 쌍 세트를 알고 있습니다. 각 계정에 최소한 하나의 코인이 있다고 가정합니다. Alice와 Bob은 또한 무상태 블록체인의 간결한 상태 V와 모든 계정 잔액 쌍(ai, bi)의 증인을 알고 있습니다. Alice와 Bob은 메시지와 계정 집합 간의 매핑에도 동의합니다. 앨리스는 자신의 메시지에 해당하는 계정 세트 A를 선택한 다음 해당 계정에서 코인을 사용합니다. 그녀는 상태 비저장 블록체인을 사용하여 Bob이 그녀에 대해 배울 수 있는 선택 세트를 Bob에게 전달할 것입니다.

인코딩: Alice는 A의 각 계정에서 코인 1개를 사용합니다. 상태 비저장 블록체인 체계를 사용하여 Alice는 업데이트된 상태 V를 계산하고 이를 Bob에게 보냅니다.

디코딩: 각 i에 대해 Bob은 verify(wi, (ai, bi))가 참인지 확인합니다. Bob은 verify(wi, (ai, bi)) = false가 되도록 계정 세트 B를 출력합니다.

Bob은 Alice가 선택한 것과 동일한 집합인 B = A를 성공적으로 출력합니다. 먼저, Alice가 계정 ai의 코인을 지출하는 경우 기존 잔액에 대한 증인이 더 이상 허용되지 않아야 합니다. 그렇지 않으면 Alice가 이중 지출을 할 수 있습니다. 따라서 A의 각 계정 ai에 대해 verify(wi, (ai, bi)) = false이고 Bob은 이 계정을 B에 포함합니다. 반면에, Bob은 Alice가 코인을 사용하지 않은 B 계정을 결코 포함하지 않을 것입니다. 왜냐하면 이 계정의 잔액은 동일하게 유지되고 (우리가 증명하고 싶은 편안한 진술을 상기해 보세요) 그들의 증인은 결코 변하지 않을 것이기 때문입니다. 따라서 B는 A와 정확히 동일합니다.

마지막으로 Alice가 Bob에게 보내야 하는 비트 수를 계산하여 모순을 해결합니다. 그녀가 선택할 수 있는 하위 집합은 2^n이므로 Shannon의 법칙에 따라 Bob에게 최소한 n 비트를 보내야 합니다. 그러나 그녀는 n 비트보다 훨씬 짧은 일정한 크기의 상태 V만 보냅니다.

증명을 설명할 때 상태 비저장 블록체인을 사용했지만 Alice와 Bob은 누산기, 벡터 약속 및 인증된 사전을 포함한 다양한 다른 인증된 데이터 구조를 사용하여 유사하고 효율적인 통신을 수행할 수 있습니다. 우리는 취소 가능한 증명 시스템이라고 부르는 새로운 추상화를 사용하여 이러한 유형의 데이터 구조를 공식화합니다.

결과의 영향

우리의 결과는 암호적으로 상태를 제거할 수 없으며 사용자가 증인을 업데이트할 필요가 없는 상태 비저장 블록체인을 구축할 수 있는 약속 체계에 대한 묘책이 없다는 것을 보여줍니다. 상태는 사라지지 않지만 유효성 검사기에서 전송되어 빈번한 증인 업데이트 형태로 사용자에게 푸시됩니다.

엄격한 상태 비저장 블록체인 모델에서 벗어나는 몇 가지 다른 유망한 솔루션이 존재합니다. 이 모델의 자연스러운 완화는 제3자(사용자도 검증인도 아닌)가 전체 상태를 저장하는 책임을 맡도록 허용하는 것입니다. 증명 서비스 노드라고 불리는 이 제3자는 완전한 상태를 사용하여 사용자를 위한 최신 증인 정보를 생성합니다. 그런 다음 사용자는 검증자가 여전히 압축 상태만 저장하는 일반 상태 비저장 블록체인에서와 같이 이러한 증인을 사용하여 거래할 수 있습니다. 이 시스템의 인센티브 메커니즘, 특히 사용자가 서비스 증명 노드를 보상하는 방법은 흥미로운 공개 연구 방향입니다.

지금까지 우리의 논의는 L1 블록체인에 중점을 두었지만 우리의 결과는 롤업 서버와 같은 L2 시스템에도 영향을 미칩니다. 롤업(낙관적이든 ZK이든)은 일반적으로 L1에 작은 값으로 큰 상태에 대한 약속을 저장합니다. 이 상태에는 L2의 모든 사용자 계정이 포함됩니다. 우리는 이러한 사용자가 현재 계정 잔액에 대한 증인을 게시하여 L1(L2 서버의 협력 없이)에서 직접 자금을 인출할 수 있기를 바랍니다. 이 설정은 우리 모델의 가역적 증명 시스템의 인스턴스이기도 합니다. 실제로 상태 비저장 블록체인은 이미 L2 롤업의 형태로 실제로 구현되어 있다고 주장할 수 있습니다.

그러나 불행하게도 이는 우리의 불가능성 결과가 직접적으로 적용된다는 것을 의미합니다. 사용자의 롤업 가져오기 감시는 자주 변경되어야 합니다. 그렇지 않으면 거의 전체 L2 상태가 L1에 기록되어야 합니다. 결과적으로 오늘날 롤업은 일반적으로 사용자가 가져올 준비가 되었을 때 새로운 증인을 계산하는 데 도움이 되는 증명 서비스 노드와 유사한 데이터 가용성 위원회(유효성이라고도 함)의 존재를 가정합니다. 우리의 결과는 Ethereum 문서에서 사용자에게 경고하는 거래 데이터가 없으면 사용자는 자금 소유권을 증명하고 인출을 수행하기 위해 Merkle 증명을 계산할 수 없습니다.라는 경고가 항상 적용된다는 것을 보여줍니다.