Utreexo: 많은 UTXO 비트코인 ​​압축

헤이 하브르!

비트코인 네트워크에서 모든 노드는 합의를 통해 일련의 UTXO(사용할 수 있는 코인 수, 정확히 누구에게, 어떤 조건에서)에 동의합니다. UTXO 세트는 검증인 노드에 필요한 최소 데이터 세트이며, 이 세트가 없으면 노드는 들어오는 트랜잭션과 이를 포함하는 블록의 유효성을 확인할 수 없습니다.

이와 관련하여 이 세트의 저장된 표현을 줄이고 보안 보장을 잃지 않고 압축하기 위해 가능한 모든 방법을 시도하고 있습니다. 저장된 데이터의 양이 작을수록 검증인 노드의 디스크 공간 요구 사항이 낮아져 검증인 노드를 저렴하게 출시할 수 있어 네트워크를 확장할 수 있어 네트워크의 안정성이 높아집니다.

이 게시물에서 우리는 공동 저자의 최근 제안에 대한 Rust 프로토타입을 게시할 것입니다. 라이트닝 네트워크 페이퍼, 타 데우스 드라이야 - Utreexo: 비트코인 ​​UTXO 세트에 최적화된 동적 해시 기반 누산기이는 검증자 노드에 대한 디스크 공간 요구 사항을 줄일 수 있습니다.

문제가 무엇입니까?

비트코인의 지속적인 문제 중 하나는 확장성이었습니다. "자신의 은행"이라는 개념에서는 네트워크 참가자가 사용 가능한 모든 자금에 대한 기록을 보관해야 합니다. 비트코인에서 사용 가능한 자금은 사용되지 않은 출력 세트, 즉 UTXO 세트로 표현됩니다. 이는 특별히 직관적인 표현은 아니지만 각 "지갑"이 별도의 항목으로 "잔액"을 갖고 개인 정보 보호(예: 코인 조인).

거래 내역(블록체인이라고 함)과 시스템의 현재 상태를 구별하는 것이 중요합니다. 비트코인 거래 내역은 현재 약 200GB의 디스크 공간을 차지하고 있으며 계속해서 증가하고 있습니다. 그러나 시스템 상태는 4GB 정도로 훨씬 작으며 현재 누군가가 코인을 소유하고 있다는 사실만 고려합니다. 이 데이터의 양도 시간이 지남에 따라 증가하지만 속도가 훨씬 느리고 때로는 감소하는 경향이 있습니다(CDPV 참조).

라이트 클라이언트(SPV)는 개인 키 이외의 최소 상태(UTXO 세트)를 저장할 수 없도록 보안을 보장합니다.

UTXO 및 UTXO 세트

UTXO(Unspent Transaction Output)는 사용되지 않은 거래 출력이며, 거래에서 전송된 각 사토시 여정의 끝점입니다. 사용되지 않은 출력은 새로운 거래의 입력이 되어 소비(지출)되고 UTXO 세트에서 제거됩니다.

새로운 UTXO는 항상 트랜잭션에 의해 생성됩니다.

• 입력 없는 코인베이스 거래: 채굴자가 코인을 발행할 때 새로운 UTXO를 생성합니다.
• 일반 거래: 특정 기존 UTXO 세트를 사용하면서 새로운 UTXO를 생성합니다.

UTXO 작업 프로세스:

지갑은 이 지갑에서 지출할 수 있는 UTXO 양을 기준으로 지출할 수 있는 코인 수(잔고)를 계산합니다.

이중 지출 시도를 방지하기 위해 각 검증인 노드는 세트를 모니터링해야 합니다. 모든 확인 시 UTXO 각각의 업무 각 차단하다.

노드에는 논리가 있어야 합니다.

• UTXO 세트에 대한 추가
• UTXO 집합에서 삭제
• 세트에 단일 UTXO가 있는지 확인

요소를 추가 및 제거하는 기능을 유지하면서 세트에 대해 저장된 정보에 대한 요구 사항을 줄이고 다음을 사용하여 세트에서 요소의 존재를 확인 및 증명하는 방법이 있습니다. 암호화 누산기.

UTXO용 배터리

여러 개의 UTXO를 저장하기 위해 배터리를 사용한다는 아이디어 논의 된 이전.

UTXO 세트는 초기 블록 다운로드(IBD) 중에 즉시 구축되어 완전하고 영구적으로 저장되며, 네트워크의 각각의 새롭고 올바른 블록에서 트랜잭션을 처리한 후 내용이 변경됩니다. 이 프로세스에는 약 200GB의 블록 데이터를 다운로드하고 수억 개의 디지털 서명을 확인해야 합니다. IBD 프로세스가 완료된 후 결론적으로 UTXO 세트는 약 4GB를 차지하게 됩니다.

그러나 누산기를 사용하면 자금에 대한 합의 규칙이 암호화 증명의 확인 및 생성으로 축소되고 사용 가능한 자금을 추적하는 부담은 자금의 존재 및 소유권을 증명하는 해당 자금의 소유자에게 이전됩니다.

누산기는 집합의 간결한 표현이라고 할 수 있습니다. 저장된 표현의 크기는 일정해야 합니다. , 또는 세트의 카디널리티 및 요소 자체의 크기와 관련하여 준선형적으로 증가합니다. 예를 들어 , 여기서 n은 저장된 세트의 카디널리티입니다.

이 경우 누산기는 집합에 요소가 포함되어 있다는 증명(포함 증명)을 생성하고 이 증명을 효과적으로 검증할 수 있도록 해야 합니다.

배터리라고 합니다 동적 if를 사용하면 세트에서 요소를 추가하고 제거할 수 있습니다.

그러한 배터리의 예는 다음과 같습니다. 2018년 XNUMX월 Boneh, Bunz, Fisch가 제안한 RSA 누산기. 이러한 누산기는 저장된 표현의 일정한 크기를 가지지만 존재가 필요합니다. 공유 비밀 (신뢰할 수 있는 설정). 이 요구 사항은 비트코인과 같은 무신뢰 네트워크에 대한 이러한 누산기의 적용 가능성을 무효화합니다. 왜냐하면 비밀 생성 중 데이터 누출로 인해 공격자가 UTXO 존재에 대한 거짓 증거를 생성하여 그러한 누산기에 기반한 UTXO 세트로 노드를 속일 수 있기 때문입니다.

유트렉소

Thaddeus Dryja가 제안한 Utreexo 디자인은 다음과 같은 것을 가능하게 합니다. 역동적 인 축 압기 без 신뢰할 수 있는 설정.

Utreexo는 완벽한 바이너리의 숲입니다 머클 트리 에 제시된 아이디어의 발전입니다. 분산 pki를 위한 효율적인 비동기 누산기, 세트에서 요소를 제거하는 기능을 추가합니다.

배터리 논리적 구조

배터리 셀은 이상적인 이진 트리 숲에 배열됩니다. 나무는 높이에 따라 정렬됩니다. 이 표현은 가장 시각적으로 선택되었으며 배터리 작업 중 나무 병합을 시각화할 수 있습니다.

저자는 숲속의 모든 나무가 이상적이기 때문에 모든 자연수가 2의 거듭제곱의 합으로 표현될 수 있는 것과 마찬가지로 그 나무의 높이는 2의 거듭제곱으로 표현된다고 지적합니다. 따라서 모든 리프 세트는 이진 트리로 그룹화될 수 있으며 모든 경우에 새 요소를 추가하려면 지식이 필요합니다. 저장된 트리의 루트 노드에 대해서만.

따라서 Utreexo 누산기의 저장된 표현은 루트 노드(Merkle 루트)의 목록입니다. 나무 숲 전체가 아니라.

루트 요소 목록을 다음과 같이 표현해 보겠습니다. Vec<Option<Hash>>. 선택적인 유형 Option<Hash> 이는 루트 요소가 누락되었을 수 있음을 나타냅니다. 이는 누산기에 적절한 높이의 트리가 없음을 의미합니다.

/// SHA-256 хеш
#[derive(Copy, Clone, Hash, Eq, PartialEq)]
pub struct Hash(pub [u8; 32]);

#[derive(Debug, Clone)]
pub struct Utreexo {
    pub roots: Vec<Option<Hash>>,
}

impl Utreexo {
    pub fn new(capacity: usize) -> Self {
        Utreexo {
            roots: vec![None; capacity],
        }
    }
}

요소 추가

먼저 기능을 설명하자면 parent(), 이는 주어진 두 요소의 상위 노드를 인식합니다.

부모() 함수

Merkle 트리를 사용하고 있으므로 두 노드 각각의 부모는 자식 노드의 해시 연결 해시를 저장하는 하나의 노드입니다.

fn hash(bytes: &[u8]) -> Hash {
    let mut sha = Sha256::new();
    sha.input(bytes);
    let res = sha.result();
    let mut res_bytes = [0u8; 32];
    res_bytes.copy_from_slice(res.as_slice());

    Hash(res_bytes)
}

fn parent(left: &Hash, right: &Hash) -> Hash {
    let concat = left
        .0
        .into_iter()
        .chain(right.0.into_iter())
        .map(|b| *b)
        .collect::<Vec<_>>();

    hash(&concat[..])
}

저자는 Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir 및 Sebastien Zimmer가 설명한 공격을 방지하기 위해
디더링된 해시 함수에 대한 두 번째 사전 이미지 공격, 두 개의 해시 외에도 트리 내부 높이도 연결에 추가되어야 합니다.

누산기에 요소를 추가할 때 어떤 루트 요소가 변경되는지 추적해야 합니다. 추가하는 각 요소의 루트 요소를 변경하는 경로를 따르면 나중에 이러한 요소가 존재한다는 증거를 구성할 수 있습니다.

변경사항을 추가하면서 추적하세요.

변경 사항을 추적하기 위해 구조를 선언해 보겠습니다. Update, 노드 변경에 대한 데이터를 저장합니다.

#[derive(Debug)]
pub struct Update<'a> {
    pub utreexo: &'a mut Utreexo,
    // ProofStep хранит "соседа" элемента и его положение
    pub updated: HashMap<Hash, ProofStep>,
}

배터리에 요소를 추가하려면 다음이 필요합니다.

• 루트 요소로 구성된 바구니 배열 만들기 new_roots 각 버킷마다 하나씩 기존 루트 요소를 배치합니다.

암호

let mut new_roots = Vec::new();

for root in self.roots.iter() {
    let mut vec = Vec::<Hash>::new();
    if let Some(hash) = root {
        vec.push(*hash);
    }

    new_roots.push(vec);
}

• 추가할 요소 추가(배열 insertions) 첫 번째 카트로 new_roots[0]:

암호

new_roots[0].extend_from_slice(insertions);

• 첫 번째 바구니에 추가된 항목을 나머지 항목과 합칩니다.
  • 두 개 이상의 품목이 포함된 모든 카트의 경우:
    1. 바구니 끝에서 두 요소를 가져와서 상위 요소를 계산하고 두 요소를 모두 제거합니다.
    2. 계산된 상위 항목을 다음 장바구니에 추가

암호

for i in 0..new_roots.len() {
    while new_roots[i].len() > 1 {
        // Объединяем два элемента в один и удаляем их
        let a = new_roots[i][new_roots[i].len() - 2];
        let b = new_roots[i][new_roots[i].len() - 1];
        new_roots[i].pop();
        new_roots[i].pop();
        let hash = self.parent(&a, &b);

        // Наращиваем количество корзин если требуется
        if new_roots.len() <= i + 1 {
            new_roots.push(vec![]);
        }

        // Помещаем элемент в следующую корзину
        new_roots[i + 1].push(hash);

        // Не забываем отслеживать изменения;
        // это пригодится для генерации доказательства добавления элементов
        updated.insert(a, ProofStep { hash: b, is_left: false });
        updated.insert(b, ProofStep {hash: a, is_left: true });
    }
}

• 루트 요소를 bin에서 결과 누산기 배열로 이동합니다.

암호

for (i, bucket) in new_roots.into_iter().enumerate() {
    // Наращиваем аккумулятор если требуется
    if self.roots.len() <= i {
        self.roots.push(None);
    }

    if bucket.is_empty() {
        self.roots[i] = None;
    } else {
        self.roots[i] = Some(bucket[0]);
    }
}

추가된 요소에 대한 증명 만들기

배터리에 셀이 포함되어 있다는 증거(Proof)는 체인으로 구성된 Merkle Path 역할을 합니다. ProofStep. 경로가 아무데도 연결되지 않으면 증명이 잘못된 것입니다.

/// Единичный шаг на пути к элементу в дереве Меркла.
#[derive(Debug, Copy, Clone)]
pub struct ProofStep {
    pub hash: Hash,
    pub is_left: bool,
}

/// Доказательство включения элемента. Содержит сам элемент и путь к нему.
#[derive(Debug, Clone)]
pub struct Proof {
    pub steps: Vec<ProofStep>,
    pub leaf: Hash,
}

요소(구조)를 추가할 때 앞서 얻은 정보를 사용하여 Update), 배터리에 요소가 추가되었다는 증거를 만들 수 있습니다. 이를 위해 변경 사항 표를 검토하고 Merkle의 경로에 각 단계를 추가합니다. 이는 이후에 증거로 사용됩니다.

암호

impl<'a> Update<'a> {
    pub fn prove(&self, leaf: &Hash) -> Proof {
        let mut proof = Proof {
            steps: vec![],
            leaf: *leaf,
        };

        let mut item = *leaf;
        while let Some(s) = self.updated.get(&item) {
            proof.steps.push(*s);
            item = parent(&item, &s);
        }

        proof
    }
}

증거를 만드는 과정

요소에 대한 증명 확인

요소의 포함 증명을 확인하는 것은 기존 루트 요소로 연결될 때까지 Merkle 경로를 따르는 것으로 요약됩니다.

pub fn verify(&self, proof: &Proof) -> bool {
    let n = proof.steps.len();
    if n >= self.roots.len() {
        return false;
    }

    let expected = self.roots[n];
    if let Some(expected) = expected {
        let mut current_parent = proof.leaf;
        for s in proof.steps.iter() {
            current_parent = if s.is_left {
                parent(&s.hash, &current_parent)
            } else {
                parent(&current_parent, &s.hash)
            };
        }

        current_parent == expected
    } else {
        false
    }
}

분명히:

A에 대한 증명을 확인하는 과정

항목 제거

배터리에서 셀을 제거하려면 셀이 거기에 있다는 유효한 증거를 제공해야 합니다. 증명의 데이터를 사용하여 주어진 증명이 더 이상 참이 아닌 누산기의 새로운 루트 요소를 계산하는 것이 가능합니다.

알고리즘은 다음과 같습니다.

1. 추가와 마찬가지로 우리는 바구니 인덱스에서 2의 거듭제곱과 동일한 높이를 가진 Merkle 트리에 해당하는 빈 바구니 세트를 구성합니다.
2. Merkle 경로 단계의 요소를 바구니에 삽입합니다. 바스켓 인덱스는 현재 단계의 번호와 같습니다
3. 증명의 경로가 이어지는 루트 요소를 제거합니다.
4. 추가와 마찬가지로 바구니의 요소를 쌍으로 결합하고 결합 결과를 다음 바구니로 이동하여 새로운 루트 요소를 계산합니다.

암호

fn delete(&self, proof: &Proof, new_roots: &mut Vec<Vec<Hash>>) -> Result<(), ()> {
    if self.roots.len() < proof.steps.len() || self.roots.get(proof.steps.len()).is_none() {
        return Err(());
    }

    let mut height = 0;
    let mut hash = proof.leaf;
    let mut s;

    loop {
        if height < new_roots.len() {
            let (index, ok) = self.find_root(&hash, &new_roots[height]);
            if ok {
                // Remove hash from new_roots
                new_roots[height].remove(index);

                loop {
                    if height >= proof.steps.len() {
                        if !self.roots[height]
                            .and_then(|h| Some(h == hash))
                            .unwrap_or(false)
                        {
                            return Err(());
                        }

                        return Ok(());
                    }

                    s = proof.steps[height];
                    hash = self.parent(&hash, &s);
                    height += 1;
                }
            }
        }

        if height >= proof.steps.len() {
            return Err(());
        }

        while height > new_roots.len() {
            new_roots.push(vec![]);
        }

        s = proof.steps[height];
        new_roots[height].push(s.hash);
        hash = self.parent(&hash, &s);
        height += 1;
    }
}

요소 "A"를 제거하는 과정:

기존 네트워크에 통합

제안된 누산기를 사용하면 노드는 UTXO 집합을 계속 변경할 수 있으면서도 모든 UTXO를 저장하기 위해 DB를 사용하는 것을 피할 수 있습니다. 그러나 증거 작업의 문제가 발생합니다.

UTXO 누산기를 사용하는 검증인 노드를 호출해 보겠습니다. 콤팩트 (컴팩트 상태 노드), 누산기가 없는 검증기는 다음과 같습니다. 완전한 (풀노드). 두 클래스의 노드가 존재하면 이를 단일 네트워크로 통합하는 데 문제가 발생합니다. 컴팩트 노드에는 트랜잭션에 사용되는 UTXO의 존재에 대한 증거가 필요한 반면, 전체 노드는 그렇지 않기 때문입니다. 모든 네트워크 노드가 동시에 조정된 방식으로 Utreexo를 사용하도록 전환하지 않으면 컴팩트 노드가 남게 되어 비트코인 ​​네트워크에서 작동할 수 없게 됩니다.

컴팩트 노드를 네트워크에 통합하는 문제를 해결하기 위해 추가 노드 클래스를 도입하는 것이 제안됩니다. 교량. 브리지 노드는 Utreexo 배터리와 전원 공급 증명도 저장하는 완전한 노드입니다. 모든 UTXO 세트의 UTXO. 브리지는 새로운 해시를 계산하고 새로운 거래 블록이 도착하면 누산기와 증명을 업데이트합니다. 누산기와 증명을 유지하고 업데이트해도 해당 노드에 추가 계산 부하가 부과되지 않습니다. 브리지는 디스크 공간을 희생합니다. 정리된 내용을 유지해야 합니다. 해시와 비교 컴팩트 노드의 해시. 여기서 n은 UTXO 세트의 거듭제곱입니다.

네트워크 아키텍처

브리지를 사용하면 기존 노드의 소프트웨어를 변경하지 않고도 네트워크에 소형 노드를 점진적으로 추가할 수 있습니다. 풀 노드는 이전과 같이 작동하며 트랜잭션과 블록을 서로 분산합니다. 브리지 노드는 Utreexo 배터리 데이터와 다음에 대한 포함 증명 세트를 추가로 저장하는 전체 노드입니다. 모든 지금은 UTXO입니다. 브리지 노드는 모든 풀 노드에 대해 풀 노드이고 모든 컴팩트 노드에 대해 컴팩트 노드인 것처럼 가장하여 자신을 광고하지 않습니다. 브리지는 두 네트워크를 함께 연결하지만 실제로는 기존 풀 노드에서 컴팩트 노드까지 한 방향으로만 연결하면 됩니다. 이는 트랜잭션 형식을 변경할 필요가 없고 컴팩트 노드에 대한 UTXO 증명을 폐기할 수 있기 때문에 가능합니다. 따라서 모든 컴팩트 노드는 브리지 노드의 참여 없이 모든 네트워크 참가자에게 유사하게 트랜잭션을 브로드캐스트할 수 있습니다.

결론

우리는 Utreexo 배터리를 살펴보고 Rust로 프로토타입을 구현했습니다. 우리는 배터리 기반 노드의 통합을 허용하는 네트워크 아키텍처를 살펴보았습니다. 컴팩트 캐치의 장점은 저장된 데이터의 크기이며, 이는 UTXO 세트의 성능에 대수적으로 의존하므로 해당 노드의 디스크 공간 및 스토리지 성능에 대한 요구 사항이 크게 줄어듭니다. 단점은 증명 전송을 위한 추가 노드 트래픽이지만 증거 집계 기술(하나의 증명이 여러 요소의 존재를 증명하는 경우)과 캐싱을 사용하면 트래픽을 허용 가능한 한도 내로 유지하는 데 도움이 될 수 있습니다.

참조:

• Rust의 Utreexo 프로토타입 GitHub
• 타 데우스 드라이야 - Utreexo: 비트코인 ​​UTXO 세트에 최적화된 동적 해시 기반 누산기
• 기사의 애니메이션 일러스트레이션

출처 : habr.com