Utreexo: compactando muito Bitcoin UTXO

Olá Habr!

Na rede Bitcoin, todos os nós concordam por consenso sobre os muitos UTXOs: quantas moedas estão disponíveis para gastar, com quem e em que condições. Um conjunto de UTXOs é um conjunto de dados que é minimamente necessário para um nó validador, sem o qual um nó não pode verificar a validade das transações recebidas e dos blocos que as contêm.

Nesse sentido, são feitas tentativas em todos os aspectos para reduzir a representação armazenada desse conjunto, para compactá-lo sem perda de garantias de segurança. Quanto menor o volume de dados armazenados, menores os requisitos de espaço em disco do nó validador, o que torna mais barato o lançamento do nó validador, permite expandir a rede e, assim, aumentar a estabilidade da rede.

Nesta nota, abordaremos o protótipo Rust de uma proposta recente do co-autor do Lightning Network Paper , Thaddeus Dryja - Utreexo: um acumulador dinâmico baseado em hash otimizado para o conjunto Bitcoin UTXO , que reduz os requisitos de espaço em disco para nós validadores.

Qual é o problema?

Um dos problemas eternos do Bitcoin era sua escalabilidade. A idéia de "possuir um banco" exige que os participantes da rede acompanhem todos os fundos disponíveis para uso. No Bitcoin, os fundos disponíveis são expressos como um conjunto de saídas não gastas - conjunto UTXO. Embora essa não seja uma visão muito intuitiva, é vantajosa em termos de desempenho da implementação, em comparação com uma visão em que cada carteira tem um "equilíbrio" como uma entrada separada e também adiciona privacidade (por exemplo, o CoinJoin fornece trabalho).

É importante distinguir entre um histórico de transações (o que é chamado de blockchain) e o estado atual do sistema. O histórico de transações do Bitcoin atualmente ocupa cerca de 200 GB de espaço em disco e continua a crescer. No entanto, o estado do sistema é muito menor, cerca de 4 GB, e leva em conta apenas o fato de alguém possuir atualmente moedas. O volume desses dados também aumenta com o tempo, mas a uma taxa muito mais baixa e, às vezes, até tende a diminuir (consulte KDPV).

Os clientes Light (SPVs) trocam garantias de segurança pela capacidade de não armazenar nenhum estado mínimo (conjunto UTXO), exceto chaves privadas.

Conjunto UTXO e UTXO

UTXO (Saída de transação não gasta) - saída de transação não gasta, o ponto final da jornada de cada satoshi transmitido nas transações. As saídas não gastas se tornam entradas de novas transações e, ao mesmo tempo, gastam e são removidas do conjunto UTXO.

Novos UTXOs são sempre criados por transações:

• transações com base de moedas sem insumos: crie novos UTXOs durante a emissão de moedas por mineradores
• transações convencionais: crie novos UTXOs, gastando algum conjunto de UTXOs existentes

O processo de trabalho com o UTXO:

As carteiras consideram o número de moedas disponíveis para gastar (saldo) com base na quantidade de UTXO disponível para essa carteira para gastar.

Cada nó validador, para evitar tentativas de gasto duplo, deve rastrear a coleção de todos os UTXOs durante a verificação de cada transação de cada bloco.

O nó deve ter lógica:

• Adições ao conjunto UTXO
• Exclusões do conjunto UTXO
• Verifica a presença de um único UTXO no conjunto

Existem maneiras de reduzir os requisitos de informações armazenadas sobre o conjunto, mantendo a capacidade de adicionar e remover elementos, verificar e provar a existência de um elemento no conjunto usando baterias criptográficas .

Baterias para UTXO

A idéia de usar baterias para armazenar muitos UTXOs foi discutida anteriormente .

O conjunto UTXO é construído em tempo real, durante o carregamento inicial da cadeia de blocos (IBD, download inicial de bloco), é armazenado total e constantemente, enquanto seu conteúdo muda após o processamento de transações de cada bloco de rede novo e correto. Esse processo requer o download de aproximadamente 200 GB de blocos de dados e a verificação de centenas de milhões de assinaturas digitais. Após a conclusão do processo IBD, o resíduo seco UTXO-set ocupará cerca de 4 GB.

No entanto, ao usar baterias, as regras de consenso relativas aos fundos se resumem à verificação e geração de evidências criptográficas, e o ônus de rastrear os fundos disponíveis é colocado sobre os ombros do proprietário desses fundos, o que fornece evidências de sua presença e propriedade.

A bateria pode ser chamada de representação compacta do aparelho. O tamanho da visualização armazenada, neste caso, deve ser constante $$$O (1)$, ou aumentar sublinearmente em relação à potência do conjunto e tamanho do próprio elemento, por exemplo $$$O (log (n))$onde n é a potência do conjunto armazenado.

Nesse caso, o acumulador deve permitir gerar evidências da inclusão de um elemento no conjunto (prova de inclusão) e permitir verificar efetivamente essa prova.

Uma bateria é chamada dinâmica se permitir adicionar e remover itens do aparelho.

Um exemplo dessa bateria é a bateria RSA proposta por Boneh, Bunz, Fisch em dezembro de 2018 . Essa bateria tem um tamanho constante da exibição armazenada, mas requer um segredo compartilhado (configuração confiável). Esse requisito nega a aplicabilidade desse acumulador para redes sem confiança, como o Bitcoin, pois o vazamento de dados durante a geração de um segredo pode permitir que os invasores criem evidências falsas da existência do UTXO, falsificando nós com um conjunto de UTXO baseado nesse acumulador.

Utreexo

O projeto Thaddeus Dryja proposto pela Utreexo permite criar uma bateria dinâmica sem uma configuração confiável.

Utreexo é uma floresta ideal de árvores Merkle binárias e é um desenvolvimento das idéias apresentadas em Acumuladores assíncronos eficientes para pki distribuído , adicionando a capacidade de remover elementos do conjunto.

A estrutura lógica da bateria

As células da bateria estão dispostas em uma floresta de árvores binárias perfeitas. As árvores são ordenadas por altura. Esta apresentação foi escolhida como a mais visual e permite visualizar a fusão de árvores durante as operações na bateria.

O autor observa que, como todas as árvores da floresta são perfeitas, sua altura é expressa pelo poder de dois, assim como qualquer número natural pode ser representado como a soma dos poderes de dois. Dessa forma, qualquer conjunto de folhas pode ser agrupado na forma de árvores binárias e, em todos os casos, a adição de um novo elemento requer conhecimento apenas sobre os nós raiz das árvores armazenadas .

Portanto, a exibição armazenada da bateria Utreexo é uma lista de nós raiz (raiz Merkle) e não toda a floresta de árvores .

Imagine a lista de elementos raiz como Vec<Option<Hash>> . O tipo opcional Option<Hash> indica que o elemento raiz pode estar ausente, o que significa que a árvore não possui uma árvore com uma altura apropriada.

 /// 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], } } } 

Adicionando itens

Primeiro, descrevemos a função parent() , que reconhece o nó pai para dois elementos fornecidos.

 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[..]) } 

Ao adicionar itens à bateria, você precisa acompanhar quais itens raiz estão sendo alterados. Seguindo o caminho de alterar os elementos raiz de cada elemento adicionado, você pode construir posteriormente uma prova da presença desses elementos.

 #[derive(Debug)] pub struct Update<'a> { pub utreexo: &'a mut Utreexo, // ProofStep  ""     pub updated: HashMap<Hash, ProofStep>, } 

Para adicionar um elemento à bateria, você precisa:

• Crie uma matriz de cestas de elementos raiz new_roots e coloque os elementos raiz existentes lá, um para cada cesta:

 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); } 

• Adicione os elementos adicionados (matriz de insertions ) ao primeiro carrinho new_roots[0] :

 new_roots[0].extend_from_slice(insertions); 

• Conduza a "coalescência" dos itens adicionados à primeira cesta com o restante:
  
  • Para todas as cestas com mais de um item:
    
    1. Pegamos dois elementos do final da cesta, calculamos o pai deles, excluímos os dois elementos
    2. Adicione o pai calculado à próxima cesta.

 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 }); } } 

• Mova os elementos raiz dos cestos para o conjunto de baterias resultante

 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]); } } 

Criando evidência para itens adicionados

A prova da inclusão do elemento na bateria ( Proof ) servirá como o caminho do Merkle (Caminho do Merkle), consistindo em uma cadeia de ProofStep . Se o caminho não leva a lugar algum, a prova está errada.

 ///         . #[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, } 

Usando as informações obtidas anteriormente durante a adição do elemento (estrutura de Update ), você pode criar evidências de que o elemento foi adicionado à bateria. Para fazer isso, contornamos a tabela de alterações feitas e adicionamos cada etapa ao caminho do Merkle, que posteriormente servirá como prova:

 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 } } 

Prova de evidência para um item

A verificação da prova da inclusão de um elemento (prova de inclusão) é reduzida para seguir o caminho do Merkle, até que ele leve ao elemento raiz existente:

 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 } } 

Claramente:

Excluir itens

Para remover um elemento da bateria, você deve fornecer uma prova válida de que o elemento está lá. Usando os dados da prova, podemos calcular os novos elementos raiz da bateria para os quais essa prova não será mais verdadeira.

O algoritmo é o seguinte:

1. Como na adição, organizamos um conjunto de cestas vazias correspondentes a árvores Merkle com uma altura igual a dois do índice da cesta
2. Insira itens das etapas do caminho Merkle nas cestas; o índice da cesta é igual ao número da etapa atual
3. Removemos o elemento raiz ao qual o caminho da prova leva.
4. Assim como na adição, calculamos os novos elementos raiz, combinando os elementos das cestas em pares e movendo o resultado da união para a próxima cesta

 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; } } 

O processo de remoção do item "A":

Integração em uma rede existente

Usando a bateria proposta, os nós podem se recusar a usar o banco de dados para armazenar todo o UTXO, mantendo a capacidade de alterar o conjunto de UTXO. No entanto, existe o problema de trabalhar com evidências.

Chamaremos um nó validador que usa uma bateria UTXO compacta (nó de estado compacto) e um validador sem bateria - cheio (nó completo). A existência de duas classes de nós cria o problema de integrá-las em uma única rede, pois os nós compactos exigem a prova da existência do UTXO, que é gasto em transações, mas os nós completos não. Se todos os nós da rede ao mesmo tempo e de maneira coordenada não mudarem para o Utreexo, os nós compactos serão deixados para trás e não poderão trabalhar na rede Bitcoin.

Para resolver o problema de integrar nós compactos à rede, propõe-se a introdução de uma classe adicional de nós - pontes . Um nó de ponte é um nó completo que, entre outras coisas, armazena a bateria do Utreexo e evidências de inclusão para todos os UTXOs do conjunto UTXO. As pontes calculam novos hashes e atualizam a bateria e as evidências à medida que novos blocos chegam com as transações. O suporte e a atualização da bateria e das evidências não impõem carga computacional adicional a esses nós. Pontes sacrificam espaço em disco: mantenha a ordem em ordem $$$2n$hashes em comparação com $$$log (n)$hashes para nós compactos, em que n é a potência do conjunto UTXO.

Arquitetura de rede

As pontes possibilitam adicionar gradualmente nós compactos à rede sem alterar o software dos nós existentes. Nós completos funcionam como antes, distribuindo transações e blocos entre si. Os nós de ponte são nós completos que armazenam adicionalmente dados da bateria do Utreexo e um conjunto de evidências de inclusão para todos os UTXO no momento. O nó da ponte não se anuncia como tal, fingindo ser um nó completo para todos os nós completos e um nó compacto para todos os nós compactos. Embora as pontes conectem as duas redes, na realidade, elas precisam estar conectadas em apenas uma direção: dos nós completos existentes aos nós compactos. Isso é possível porque o formato da transação não precisa ser alterado e as evidências do UTXO para nós compactos podem ser descartadas; portanto, qualquer nó compacto pode enviar transações para todos os participantes da rede da mesma maneira, sem a participação de nós da ponte.

Conclusão

Analisamos a bateria Utreexo e implementamos seu protótipo em Rust. Examinamos a arquitetura de rede, que integrará os nós com base na bateria. A vantagem da captura compacta é o tamanho dos dados armazenados, que depende logaritmicamente da potência de muitos UTXOs, o que reduz significativamente os requisitos de espaço em disco e o desempenho de armazenamento para esses nós. A desvantagem é o tráfego adicional do nó para a transferência de evidência, mas as técnicas de agregação de evidência (quando uma prova prova a existência de vários elementos) e o armazenamento em cache podem ajudar a manter o tráfego dentro de limites aceitáveis.

Referências :

• Protótipo de ferrugem Utreexo GitHub
• Thaddeus Dryja - Utreexo: um acumulador dinâmico baseado em hash otimizado para o conjunto Bitcoin UTXO
• Arte animada de um artigo