버클 트리

버클 트리("벡터 커밋먼트(Vector commitment)"와 "머클 트리(Merkle Trees)"의 합성어)는 블록 검증 능력을 잃지 않으면서도 대량의 상태 데이터를 저장하지 않도록 이더리움 노드를 업그레이드하는 데 사용할 수 있는 데이터 구조입니다.

무상태성

버클 트리는 무상태(stateless) 이더리움 클라이언트로 나아가는 과정에서 중요한 단계입니다. 무상태 클라이언트는 수신되는 블록을 검증하기 위해 전체 상태 데이터베이스를 저장할 필요가 없는 클라이언트입니다. 무상태 클라이언트는 블록을 검증하기 위해 이더리움 상태의 로컬 복사본을 사용하는 대신, 블록과 함께 도착하는 상태 데이터의 "증거"를 사용합니다. 증거는 특정 트랜잭션 세트를 실행하는 데 필요한 상태 데이터의 개별 조각 모음이자, 해당 증거가 전체 데이터의 일부임을 증명하는 암호학적 증명입니다. 증거는 상태 데이터베이스 대신 사용됩니다. 이것이 작동하려면 검증자가 12초 슬롯 내에 처리할 수 있도록 네트워크를 통해 안전하게 브로드캐스트될 수 있을 만큼 증거의 크기가 매우 작아야 합니다. 현재의 상태 데이터 구조는 증거가 너무 크기 때문에 적합하지 않습니다. 버클 트리는 작은 크기의 증거를 가능하게 하여 이 문제를 해결하고, 무상태 클라이언트를 구현하는 데 있어 주요 장벽 중 하나를 제거합니다.

현재 이더리움 클라이언트는 상태 데이터를 저장하기 위해 패트리샤 머클 트라이(Patricia Merkle Trie)라는 데이터 구조를 사용합니다. 개별 계정에 대한 정보는 트라이의 리프(leaf)로 저장되며, 단일 해시만 남을 때까지 리프 쌍이 반복적으로 해시됩니다. 이 최종 해시를 "루트(root)"라고 합니다. 블록을 검증하기 위해 이더리움 클라이언트는 블록 내의 모든 트랜잭션을 실행하고 로컬 상태 트라이를 업데이트합니다. 블록 제안자와 검증 노드가 수행한 연산에 차이가 있으면 루트 해시가 완전히 달라지기 때문에, 로컬 트리의 루트가 블록 제안자가 제공한 루트와 동일한 경우에만 블록이 유효한 것으로 간주됩니다. 이 방식의 문제점은 블록체인을 검증하려면 각 클라이언트가 헤드 블록과 여러 과거 블록에 대한 전체 상태 트라이를 저장해야 한다는 것입니다(Geth의 기본 설정은 헤드 뒤의 128개 블록에 대한 상태 데이터를 유지하는 것입니다). 이로 인해 클라이언트는 대용량 디스크 공간에 접근할 수 있어야 하며, 이는 저렴하고 전력 소모가 적은 하드웨어에서 풀 노드를 실행하는 데 장벽이 됩니다. 이에 대한 해결책은 전체 상태 데이터 대신 공유할 수 있는 데이터에 대한 작은 "증거"를 사용하여 요약할 수 있는 더 효율적인 구조(버클 트리)로 상태 트라이를 업데이트하는 것입니다. 상태 데이터를 버클 트리로 재구성하는 것은 무상태 클라이언트로 이동하기 위한 디딤돌입니다.

증거란 무엇이며 왜 필요한가요?

블록을 검증한다는 것은 블록에 포함된 트랜잭션을 재실행하고, 변경 사항을 이더리움의 상태 트라이에 적용하며, 새로운 루트 해시를 계산하는 것을 의미합니다. 검증된 블록은 계산된 상태 루트 해시가 블록과 함께 제공된 해시와 동일한 블록입니다(이는 블록 제안자가 실제로 자신이 수행했다고 주장하는 연산을 수행했음을 의미하기 때문입니다). 오늘날의 이더리움 클라이언트에서 상태를 업데이트하려면 로컬에 저장해야 하는 대규모 데이터 구조인 전체 상태 트라이에 접근해야 합니다. 증거에는 블록의 트랜잭션을 실행하는 데 필요한 상태 데이터의 조각만 포함됩니다. 그러면 검증자는 해당 조각들만 사용하여 블록 제안자가 블록 트랜잭션을 실행하고 상태를 올바르게 업데이트했는지 확인할 수 있습니다. 그러나 이는 증거가 이더리움 네트워크의 피어 간에 충분히 빠르게 전송되어 각 노드가 12초 슬롯 내에 안전하게 수신하고 처리할 수 있어야 함을 의미합니다. 증거가 너무 크면 일부 노드가 이를 다운로드하고 체인을 따라가는 데 너무 오랜 시간이 걸릴 수 있습니다. 이는 빠른 인터넷 연결을 가진 노드만이 블록 검증에 참여할 수 있음을 의미하므로 중앙화 요인으로 작용합니다. 버클 트리를 사용하면 하드 드라이브에 상태를 저장할 필요가 없습니다. 블록을 검증하는 데 필요한 _모든 것_이 블록 자체에 포함되어 있습니다. 안타깝게도 머클 트라이에서 생성할 수 있는 증거는 무상태 클라이언트를 지원하기에는 너무 큽니다.

버클 트리가 더 작은 증거를 가능하게 하는 이유는 무엇인가요?

머클 트라이의 구조는 증거 크기를 매우 크게 만듭니다. 12초 슬롯 내에 피어 간에 안전하게 브로드캐스트하기에는 너무 큽니다. 이는 증거가 리프에 보관된 데이터와 루트 해시를 연결하는 경로이기 때문입니다. 데이터를 검증하려면 각 리프를 루트에 연결하는 모든 중간 해시뿐만 아니라 모든 "형제(sibling)" 노드도 있어야 합니다. 증명에 있는 각 노드에는 트라이 위로 다음 해시를 생성하기 위해 함께 해시되는 형제가 있습니다. 이는 엄청난 양의 데이터입니다. 버클 트리는 트리의 리프와 루트 사이의 거리를 줄이고 루트 해시를 검증하기 위해 형제 노드를 제공할 필요성을 없앰으로써 증거 크기를 줄입니다. 해시 방식의 벡터 커밋먼트 대신 강력한 다항식 커밋먼트(polynomial commitment) 체계를 사용하면 훨씬 더 높은 공간 효율성을 얻을 수 있습니다. 다항식 커밋먼트를 사용하면 증명하는 리프의 수에 관계없이 증거가 고정된 크기를 가질 수 있습니다.

다항식 커밋먼트 체계 하에서 증거는 피어 투 피어 네트워크에서 쉽게 전송할 수 있는 관리 가능한 크기를 갖습니다. 이를 통해 클라이언트는 최소한의 데이터로 각 블록의 상태 변경을 검증할 수 있습니다.

증거 크기는 포함된 리프의 수에 따라 다릅니다. 증거가 1000개의 리프를 포함한다고 가정할 때, 머클 트라이의 증거는 약 3.5MB(트라이가 7레벨이라고 가정)가 됩니다. 버클 트리에서 동일한 데이터에 대한 증거(트리가 4레벨이라고 가정)는 약 150kB로, 약 23배 더 작습니다. 이러한 증거 크기의 감소는 무상태 클라이언트 증거가 허용 가능한 수준으로 작아질 수 있게 해줍니다. 다항식 증거는 사용되는 특정 다항식 커밋먼트에 따라 0.128~1kB입니다.

버클 트리의 구조는 무엇인가요?

버클 트리는 키가 31바이트의 _줄기(stem)_와 1바이트의 _접미사(suffix)_로 구성된 32바이트 요소인 (key,value) 쌍입니다. 이러한 키는 확장(extension) 노드와 내부(inner) 노드로 구성됩니다. 확장 노드는 서로 다른 접미사를 가진 256개의 자식에 대한 단일 줄기를 나타냅니다. 내부 노드도 256개의 자식을 가지지만, 다른 확장 노드가 될 수 있습니다. 버클 트리와 머클 트리 구조의 주요 차이점은 버클 트리가 훨씬 더 평평하다는 것입니다. 즉, 리프를 루트에 연결하는 중간 노드가 적으므로 증명을 생성하는 데 필요한 데이터가 적습니다.