Utreexo 어큐뮬레이터을 활용한 비순차적 블록 검증

요약: 본 아티클에서는 100x 그룹의 연구지원금 수여자 캘빈 김 (Calvin Kim)이 Utreexo에서는 검증되는 블록의 순서가 중요하지 않은지에 대하여 설명합니다. 이와 같은 이유는 디스크 공간 절약이 UTXO 스냅샵을 실용적으로 만들어서, 비트코인 블록체인의 검증이 병렬화 될 수 있도록 허용하기 때문입니다. 이어서 캘빈은 사용자가 수신 전송을 UTXO 세트에 접근할 필요 없이 어큐뮬레이터 증명 검증으로 유효성을 확인할 수 있을지에 대하여 다루고 있습니다. 이와 같은 방식으로 Utreexo 노드가 디스크 접근 요구를 제거할 수 있도록 하고, 그 대신 더 많은 해싱을 요구하게 합니다. 꽤 훌륭한 절충안이 될 수 있지요. 그 다음 캘빈은 Utreexo가 우리가 생각하는 블록 검증을 어떻게 변화시킬 수 있을지에 대하여 논의하고 있습니다.

This image has an empty alt attribute; its file name is 1-1024x726.png
 
 

별도의 아티클에서 비트코인 코어 v21.0.0과 Utreexo 어큐뮬레이터가 실행되고 있는 저희으 노드 간의 블록 검증 속도 차이에 대한 벤치마크를 제시하였습니다. Utreexo 어큐뮬레이터가 블록 검증을 병렬식으로 할 수 있도록 하기 때문에 가능한 것이었죠. 

assumeUTXO 스타일의 비동기식 검증과 일반적인 아이디어는 비슷합니다. 하지만 Utreexo 어큐뮬레이터에서는 UTXO 세트를 수백 바이트 내에서 나타낼 수 있어서, UTXO 세트의 다양한 표시를 직접 이진법으로 하드코드 할 수 있도록 하기 때문입니다. 이와 같은 모든 하드코드 세트가 검증이 되는 한, 검증되는 블록의 순서는 중요하지 않고, 이것은 다수의 블록을 동시에 검증할 수 있도록 합니다. Utreexo 어큐뮬레이터는 또한 디스크 접근을 더 많은 SHA256 해싱으로 대체하여서, 발생할 수 있는 디스크 i/o 병목현상을 제거합니다. 

Utreexo 어큐뮬레이터로 단일 전송 검증하기

Utreexo 어큐뮬레이터머클트리(Merkle Tree)를 변형시킨 것입니다. Utreexo 어큐뮬레이터의 인터페이스는 추가(add), 제거(Remove), 증명(prove), verify(검증)이라는 4가지 행동을 가지고 있습니다. 어큐뮬레이터 증명을 엘러먼트가 존재하는 사용자를 증명하기 위하여 생성할 수 있습니다. 그 후 또다른 사용자는 이와 같은 어큐뮬레이터 증명을 검증할 수 있게 됩니다. 이와 같은 모든 행동들은 Utreexo 루트(Utreexo Roots)라고 명명한 머클트리의 루트로만 진행이 가능합니다. 이와 관한 자세한 내용은 Utreexo 연구보고서 원본을 참고하기 바랍니다.  

Utreexo 어큐뮬레이터가 도입된 비트코인 노드를 활용하여 우리는 UTXO 세트를 유지할 필요가 없었습니다. 대신 유일한 요건인 Utreexo 루트를 유지할 수 있었습니다. 자신의 UTXO를 지불하고 싶은 사람은 다음의 두 가지 사항을 저희에게 제시해야만 합니다. 첫째, Utreexo 루트까지 해싱하기 위해 필요한 모든 엘러먼트인 어큐뮬레이터 증명(accumulator proof)을 제시해야만 합니다. 둘째, UTXO를 지불할 수 있음을 증명(주로 디지털 서명이 해당됨)하기 위한 UTXO 데이터를 제시해야만 합니다. 저희는 이와 같은 정보를 Utreexo 증명이라고 부릅니다. 

This image has an empty alt attribute; its file name is 1-1-1024x719.png
 
 

위 그림의 Hash 0-0에 대한 Utreexo 증명은Hash 0-0, Hash 0-1, Hash 1가 될 수 있습니다. 이와 같은 증명을 검증하기 위하여 저희는 다음의 작업을 수행했습니다: 

  1. Hash 0-0와 Hash 0-1를 SHA256에 입력하여Hash 0를 얻음
  2. Hash 0(개발팀이 산출)과 Hash 1을 SHA256에 입력하여Root를 얻음.
  3. 산출된 Root가 개발팀이 보관한 Root와 일치하는지 확인함. 만약 일치하지 않을 경우, Utreexo 증명은 틀렸고 연구진은 해당 전송을 거절함.  
  4. 모든 UTXO 데이터를 확인함. 만약 데이터가 유효하지 않다면, Utreexo 증명이 잘못된 것이고 개발팀은 전송을 거절함.

Utreexo 어큐뮬레이터로 단일 블록을 어떻게 검증할 수 있을까요?

Utreexo 어큐뮬레이터로 단일 블록을 검증하기 위해서는 다음의 데이터가 필요합니다:

  1. 블록 자체의 데이터.
  2. 블록 내 지불된 모든 UTXO의 Utreexo 증명.  
  3. UTXO 세트의 루트.

저희는 친구들로부터 블록의 데이터를 받았습니다. 다른 점은 저희 역시 저희가 받은 블록에 대한 Utreexo 증명을 받았다는 것입니다. 블록의 유효성은 (여러 컨센서스 규칙 중에서도) 블록 내 모든 전송의 유효성에 따릅니다. 

Utreexo 노드에 대한 단일 전송의 유효성은 다음과 같은 두 항목으로 구성된 Utreexo 증명의 유효성에 따릅니다: 

  1. 어큐뮬레이터 중명의 유효성. 
  2. 사용자 본인이 UTXO (하나 또는 여러 개의 UTXO)를 보유하고 있는지를 증명하는 디지털 서명의 유효성. 

(1)이 다르다는 것을 유념하시기 바랍니다. 현재 비트코인 노드에서 사용자는 사용자 본인의 UTXO 세트 내에서 UTXO가 존재하는지를 확인해야만 합니다. 이와 같은 작업은 디시키 접근을 필요로 합니다. Utreexo 노드를 활용하면, 사용자는 어큐뮬레이터 증명을 검증하고 이것이 유효한지만 확인하면 됩니다. 이 때 필요한 것이 SHA256 해싱입니다. 알아둘 것은 Utreexo 어큐뮬레이터를 이용한다면, 디스크 접근을 SHA256 해싱으로 대체할 수 있다는 것입니다. 

Utreexo 어큐뮬레이터는 tx 검증동안 더 많은 SHA256 해싱에 대한 디스크 접근을 제거합니다.   

이와 같은 절충안은 SHA@56이 매우 빠르게 진행될 수 있기 때문에 아주 훌륭하다고 생각합니다. 디스크 접근 시간은 (가장 빠른 NVMe SSDs 환경에서 조차도) 비교적 속도가 느리고 그렇게 빨라지지 않습니다.

블록검증에 대한 관점 전환하기

많은 사람들이 블록체인을 지불할 수 있는 모든 코인이 저장된 곳이라고 생각합니다. 하지만, 이것이 완전하게 맞는 말은 아닙니다. 새로운 블록이나 전송을 검증하기 위하여 필요한 정보가 저장된 곳이 UTXO 세트입니다. 사실, 저희는 이미 가지치기 노드(pruned node)라고 하는 비트코인 풀노드 모드를 보유하고 있습니다. 이 노드는 오래되고 필요없는 블록 데이터를 삭제하지요. 

대신, 블록들은 UTXO 세트를 변경하는 미미한 기능을 가지고 있습니다. 각각의 블록은 많은 UTXO의 소유권 변경에 대한 정보를 보관합니다.  모든 과거 블록들이 UTXO 세트의 최신 상태에 들어가야만 하는 소유권 변경에 대한 모든 정보이지요. 블록을 검증할 때, 저희가 한 것은 UTXO 세트의 상태 변환(state transition)이 유효한지를 확인한 것이었습니다.

This image has an empty alt attribute; its file name is 2-1-1024x518.png
 
 

만약 비트코인 블록이 UTXO 세트의 단일 상태 변환이었다면, 블록의 체인이 UTXO 세트의 여러 상태 변환이 됩니다. 블록체인을 UTXO 세트 수정의 연속이라고 보았을 때, 비트코인 블록체인을 어떻게 나타낼 수 있을지를 아래의 그림에서 보여주고 있습니다.

This image has an empty alt attribute; its file name is 3-1-1024x529.png
 
 

모든 블록을 연속적으로 검증해야 하는 이유는 무엇인가?

블록 0에서 시작해서 모든 블록을 하나씩 검증하는 이유는 블록 500에서의 전송이 블록 499에서 생성된 UTXO를 참조할 수 있기 때문입니다. 만약 블록 499 수정이 발생한 뒤 UTXO 세트의 상태를 보유하고 있지 않다면, 유효한 전송을 무효하다고 표시할 수 있고 비트코인 네트워크에서 포크할 수 있게 됩니다. 

예를 들어서 앨리스가 밥에게 50 비트코인을 주고 해당 전송이 블록 499에 포함되어 있다면, 밥은 블록 499에서 수정한 뒤 UTXO를 참조해야만 할 것입니다. 만약 저희의 UTXO 세트가 블록 499에서의 수정을 보유하고 있지 않다면, 저희는 밥이 아니라 앨리스가 여전히 50 비트코인을 보유하고 있다고 잘못 명시하게 될 것입니다. 그리고 밥이 앨리스로 부터 받은 50비트코인을 사용할 때, 모든 사람들이 밥의 전송이 유효하다고 하는 반면 저희는 그렇지 않다고 말하게 됩니다. 이것으로 인해 비트코인 네트워크에서 저희의 네트워크가 포크되도록 할 것입니다. 

비순차적 블록 검증에 대한 일반적인 아이디어 

저희는 풀 노드가 모든 블록을 처음부터 하나씩 검증해야 한다는 것을 알고 있습니다. 그렇다면 비순차적 블록 검증을 적용했을 때에는 어떻게 될까요? 비순차적 블록 검증의 경우, 블록을 검증할 때 필요한 UTXO 세트를 제시하기만 하면 됩니다. 이와 같은 아이디어가 바로 assumeUTXO 비동기식 검증의 바탕입니다.

블록 1-300,000까지의 블록 검증할 경우에 비순차적 블록 검증의 간단한 예시를 살펴보도록 하지요.

This image has an empty alt attribute; its file name is 4-1-1024x572.png
 
 

UTXO 세트를 100,000와 200,000 블록 높이로 하드코딩 했습니다. 100,000와 200,000 높이에 있는 UTXO 세트가 무엇인지 알기 때문에, 저희는 블록 범위 1-100,000, 100,000-200,000, 그리고 200,000-300,000를 나누어서 검증할 수 있었습니다. 이 세 가지 블록 범위에서 블록 검증이 끝났을 때, 저희는 산출된 세 종의 UTXO 세트를 확인할 수 있었습니다. 하나는 블록 100,000, 다른 하나는 블록 200,000, 그리고 또 다른 하나는 블록 300,000에서의 값이었습니다. 

그리고 블록 100,000에서 하드코딩 된 UTXO 세트를 블록 100,000에서 산출된 UTXO와 비교했습니다. 만약 이 값이 동일하다면, 하드코딩 된 UTXO 세트가 올바른 것으로 검증된 것입니다. 저희는 블록 200,000에서도 동일하게 UTXO 세트를 비교했습니다. 만약 이 값들이 동일하다면, 저희는 블록 300,000 수정 후 UTXO 세트 최신값이 정확함을 알 수 있습니다. 이와 같은 개념으로 저희는 비순차적 블록 검증을 제시할 수 있게 되었습니다.

This image has an empty alt attribute; its file name is 5-1024x584.png
 
 

만약 모든 블록에서 모든 UTXO 세트를 하드코딩 했다면, 저희는 순서와 무관하게 어떤 블록 높이에서든 모든 블록을 검증할 수 있었습니다.

This image has an empty alt attribute; its file name is 6-1-1024x588.png
 
 

블록 검증 기능은 다음과 같이 간단하게 묘사할 수 있습니다:

This image has an empty alt attribute; its file name is 7-1-1024x583.png
 
 

시작 UTXO(Start UTXO) 세트종료 UTXO(End UTXO) 세트는 블록 높이 n과 n+1에 위치한 UTXO 세트입니다. 블록 데이터(Block Data)는 저희가 검증할 블록 높이 n의 데이터입니다. 규칙(Rules)은 해당 블록 높이에 필요한 체인 규칙입니다. 새로운 규칙은 소프트 포크를 통해 도입이 되기 때문에, 해당 기능 내에 새로운 규칙이 포함 되어야만 합니다. 규칙은 세그윗(Segwit) 규칙이 활성화되었는지, 탭루트(Taproot) 규칙이 활성화되었는지 등을 포함합니다. 

Utreexo 어큐뮬레이터에 대한 필요성

Utreexo 어큐뮬레이터가 이러한 타입의 블록 검증에 왜 필요한지에 대한 두 가지 이유는 다음과 같습니다.

  1. Utreexo는 매우 작습니다.
  2. Utreexo는 디스크 접근을 제거합니다.

1. Utreexo는 매우 작습니다.

비순차적 블록 다운로드는Utreexo 어큐뮬레이터 없이 이론적으로 가능합니다. 하지만, UTXO 세트가 크기 면에서 4GB 이상이기 때문에, 비순차적 블록 다운로드는 전체 블록체인을 검증하기 위해서 아주 많은 UTXO 세트를 제공해야 한다는 점에서 실질적으로 타당하지 않습니다. 체인 내에서 각각의 블록을 검증하기 위해서 사용자는 8GB 데이터를 필요로 합니다. 필요한 데이터는 빠르게 추가되면서(100개의 블록은 800GB를 필요로 함), 이진법으로 하드코딩 될 수 없게 됩니다. 

Utreexo 어큐뮬레이터라면 UTXO 세트를 몇 백 바이트라는 적은 규모에서 표시할 수 있게 되면서 이러한 가설이 타당하게 됩니다. 다음의 그림에서 json 내 실제 하드코딩 된 Utreexo 루트 예시를 보여주고 있습니다:

This image has an empty alt attribute; its file name is 8-1-1024x567.png
 
 

이렇게 하고 저희는 Utreexo 어큐뮬레이터를 블록 검증 대신 사용하도록 기능을 수정할 수 있었습니다. 블록 검증 기능은 다음과 같이 나타낼 수 있습니다:

This image has an empty alt attribute; its file name is 9-1024x540.png
 
 

시작 Utreexo 루트종료 Utreexo 루트는 블록 높이 n과 n+1에서의 UTXO 세트와 동일합니다. Utreexo 증명은 블록 데이터를 검증할 수 있도록 하기 위하여 추가되었습니다.

2. Utreexo는 더 많은 SHA256 해싱에 대한 디스크 접근을 제거합니다. 

Utreexo 어큐뮬레이터를 활용하여서 저희는 크기 문제를 해결할 수 있습니다. 하지만 Utreexo 어큐뮬레이터가 해결할 수 있는 문제는 이것뿐만이 아닙니다. Utreexo 어큐뮬레이터는 더 많은 SHA256 해싱에 대한 디스크 접근을 제거합니다. 이러한 내용은 Utreexo 어큐뮬레이터 없이 디스크 i/o가 병목현상이 발생할 수 있다는 점에서 매우 큰 중요성을 가지고 있습니다.   

UTXO 세트를 활용한 전송 검증은 필요로 하는 UTXO를 디스크에서 페칭(fetching)하는 것에 달려있을 수 있습니다. 이러한 과정이 아주 작은 규모의 무작위 디스크 접근이 될 수 있기도 한데, 다들 작은 규모의 무작위 디스크 접근이 빠르지 않다는 것을 알고 있습니다. 블록 검증의 경우, 작은 규모의 무작위 디스크 접근이 다수 실행됩니다. 병렬식 블록 검증의 경우, 이와 같은 무작위 디스크 접근의 횟수가 급증할 수 있습니다. 이와 같은 요청에 부응할 수 있는 SSD가 없지요.

Utreexo는 전송 검증 동안 더 많은 SHA256 해싱에 대한 디스크 접근을 제거합니다. 하나의 블록이 여러 전송을 모은 것이기 때문에, Utreexo는 블록 검증 동안 더 많은 SHA256 해싱에 대한 디스크 접근 역시 제거합니다. 그러므로 하나의 블록을 검증하는 것이 필수적으로 (다른 컨센서스 규칙을 확인하는 것 중)  SHA256 해시를 산출하는 것이 됩니다. 블록체인은 블록이 연속된 것일 뿐이므로, 전체 블록체인을 검증할 때 디스크 접근을 필요로 하지 않는 대신 더 많은 SHA256 해싱을 필요로 하게 됩니다. 그러므로 IBD 과정은 다수의 SHA256 해시가 산출되는 결과를 만들 수 있습니다. 양호한 상황이지요. 왜냐하면 저희는 SHA256 해시를 어떻게 하면 매우 빠르게 산출할 수 있는지 알기 때문입니다. 

이와 같은 이유로 Utreexo 어큐뮬레이터는 병렬식 블록체인 검증에서 필수적입니다. Utreexo 어큐뮬레이터는 한 번에 두 가지 큰 문제를 해결하고, 병렬식 블록체인 검증을 완료할 수 있도록 합니다.

결론

시간이 흐르면서 블록체인 내 검증되어야 하는 데이터량은 증가하게 됩니다. 검증되어야 하는 데이터 증가를 상쇄하는 것이 진입 장벽으로서의 IBD를 최소화된 상태를 유지하기 위한 소프트웨어 최적화와 함께 대단히 중요하지요. Utreexo 어큐뮬레이터라면 이것이 가능합니다. 앞으로 추가 연구가 필요한 더 많은 Utreexo 어큐뮬레이터 최적화 작업과 함께 저는 앞으로의 연구 과제와 비트코인 생태계에서의 Utreexo 어큐뮬레이터 잠재력에 대하여 매우 큰 기대를 하고 있습니다. 이와 같은 저희 개발팀의 행보는 github.com/mit-dci/utreexo에서 함께하실 수 있습니다.