Utreexo: comprimiendo una gran cantidad de UTXO Bitcoin

Hola Habr!

En la red Bitcoin, todos los nodos acuerdan por consenso sobre los muchos UTXO: cuántas monedas están disponibles para gastar, a quién y bajo qué condiciones. Un conjunto de UTXO es un conjunto de datos que es mínimamente necesario para un nodo validador, sin el cual un nodo no puede verificar la validez de las transacciones entrantes y los bloques que las contienen.

En este sentido, se hacen intentos en todos los sentidos para reducir la representación almacenada de este conjunto, para comprimirlo sin pérdida de garantías de seguridad. Cuanto menor sea el volumen de datos almacenados, menores serán los requisitos para el espacio en disco del nodo validador, lo que hace que el lanzamiento del nodo validador sea económico, le permite expandir la red y, por lo tanto, aumentar la estabilidad de la red.

En esta nota, cubriremos el prototipo Rust de una propuesta reciente del coautor de Lightning Network Paper , Thaddeus Dryja - Utreexo: un acumulador dinámico basado en hash optimizado para el conjunto Bitcoin UTXO , que reduce los requisitos de espacio en disco para los nodos de validación.

Cual es el problema

Uno de los problemas eternos de Bitcoin fue su escalabilidad. La idea de "ser dueño de un banco" requiere que los participantes de la red realicen un seguimiento de todos los fondos disponibles para su uso. En Bitcoin, los fondos disponibles se expresan como un conjunto de salidas no gastadas: conjunto UTXO. Aunque esta no es una presentación particularmente intuitiva, es ventajosa en términos de rendimiento de implementación, en comparación con una presentación en la que cada billetera tiene un "equilibrio" como una entrada separada, y también agrega privacidad (por ejemplo, proporciona CoinJoin ).

Es importante distinguir entre un historial de transacciones (lo que se llama una cadena de bloques) y el estado actual del sistema. El historial de transacciones de Bitcoin actualmente ocupa alrededor de 200 GB de espacio en disco y continúa creciendo. Sin embargo, el estado del sistema es mucho más pequeño, aproximadamente 4 GB, y solo tiene en cuenta el hecho de que alguien posee actualmente monedas. El volumen de estos datos también aumenta con el tiempo, pero a un ritmo mucho más bajo y a veces incluso tiende a disminuir (ver KDPV).

Los clientes ligeros (SPV) intercambian garantías de seguridad para la capacidad de no almacenar ningún estado mínimo (conjunto UTXO), excepto las claves privadas.

UTXO y UTXO-set

UTXO (Salida de transacción no utilizada): salida de transacción no utilizada, el punto final del viaje de cada satoshi transmitido en transacciones. Las salidas no gastadas se convierten en entradas de nuevas transacciones y, al mismo tiempo, se gastan y se eliminan del conjunto UTXO.

Los nuevos UTXO siempre se crean mediante transacciones:

• transacciones de coinbase sin entradas: cree nuevos UTXO durante la emisión de monedas por parte de mineros
• transacciones convencionales: cree nuevos UTXO, mientras gasta un conjunto de UTXO existentes

El proceso de trabajar con UTXO:

Las billeteras consideran la cantidad de monedas disponibles para gastar (saldo) en función de la cantidad de UTXO disponible para esta billetera para gastar.

Cada nodo del validador, para evitar intentos de doble gasto, debe rastrear la colección de todos los UTXO durante la verificación de cada transacción de cada bloque.

El nodo debe tener lógica:

• Adiciones al conjunto UTXO
• Eliminaciones de UTXO-set
• Comprueba la presencia de un solo UTXO en el conjunto

Hay formas de reducir los requisitos de información almacenada sobre el conjunto, al tiempo que conserva la capacidad de agregar y eliminar elementos, verificar y probar la existencia de un elemento en el conjunto utilizando baterías criptográficas .

Baterías para UTXO

La idea de usar baterías para almacenar muchos UTXO ha sido discutida previamente .

UTXO-set se construye sobre la marcha, durante la carga inicial de la cadena de bloques (IBD, descarga inicial del bloque), se almacena completa y constantemente, mientras que su contenido cambia después de procesar las transacciones de cada bloque de red nuevo y correcto. Este proceso requiere descargar aproximadamente 200 GB de bloques de datos y verificar cientos de millones de firmas digitales. Después de que se complete el proceso de EII, en el residuo seco, el conjunto UTXO ocupará aproximadamente 4 GB.

Sin embargo, cuando se usan baterías, las reglas de consenso con respecto a los fondos se reducen a verificar y generar evidencia criptográfica, y la carga de rastrear los fondos disponibles recae sobre los hombros del propietario de estos fondos, lo que proporciona evidencia de su presencia y propiedad.

La batería se puede llamar una representación compacta del conjunto. El tamaño de la vista almacenada, en este caso, debe ser constante $$$O (1)$, o aumentar sublinealmente en relación con la potencia del conjunto y el tamaño del elemento en sí, por ejemplo $$$O (log (n))$donde n es el poder del conjunto almacenado.

En este caso, la batería debería permitir generar evidencia de la inclusión de un elemento en el conjunto (prueba de inclusión) y permitirle verificar efectivamente esta prueba.

Una batería se llama dinámica si le permite agregar elementos y eliminar elementos del conjunto.

Un ejemplo de dicha batería es la batería RSA propuesta por Boneh, Bunz, Fisch en diciembre de 2018 . Dicha batería tiene un tamaño constante de la vista almacenada, pero requiere un secreto compartido (configuración confiable). Este requisito niega la aplicabilidad de dicho acumulador para redes sin confianza como Bitcoin, ya que la fuga de datos durante la generación de un secreto puede permitir a los atacantes crear evidencia falsa de la existencia de UTXO al falsificar nodos con un conjunto UTXO basado en dicho acumulador.

Utreexo

El diseño Thaddeus Dryja propuesto por Utreexo le permite crear una batería dinámica sin una configuración confiable.

Utreexo es un bosque de árboles Merkle binarios ideales y es un desarrollo de las ideas presentadas en los acumuladores asíncronos eficientes para pki distribuido , agregando la capacidad de eliminar elementos del conjunto.

La estructura lógica de la batería.

Las celdas de la batería están dispuestas en un bosque de árboles binarios perfectos. Los árboles están ordenados por altura. Esta presentación fue elegida como la más visual y le permite visualizar la fusión de árboles durante las operaciones con la batería.

El autor señala que, dado que todos los árboles del bosque son perfectos, su altura se expresa mediante el poder de dos, al igual que cualquier número natural puede representarse como la suma de los poderes de dos. En consecuencia, cualquier conjunto de hojas puede agruparse en forma de árboles binarios, y en todos los casos, agregar un nuevo elemento requiere conocimiento solo sobre los nodos raíz de los árboles almacenados .

Por lo tanto, la vista almacenada de la batería Utreexo es una lista de nodos raíz (raíz de Merkle), y no todo el bosque de árboles .

Imagine la lista de elementos raíz como Vec<Option<Hash>> . El tipo opcional Option<Hash> indica que puede faltar el elemento raíz, lo que significa que el árbol no tiene un árbol con una altura adecuada.

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

Agregar elementos

Primero, describimos la función parent() , que reconoce el nodo padre para dos elementos dados.

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

Al agregar elementos a la batería, debe realizar un seguimiento de los elementos raíz que se están cambiando. Siguiendo el camino de cambiar los elementos raíz para cada elemento agregado, más tarde puede construir una prueba de la presencia de estos elementos.

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

Para agregar un elemento a la batería, necesita:

• Cree una matriz de cestas de elementos raíz new_roots y coloque allí los elementos raíz existentes, uno 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); } 

• Agregue los elementos agregados (matriz de insertions ) a la primera canasta new_roots[0] :

 new_roots[0].extend_from_slice(insertions); 

• Realice la "fusión" de los artículos agregados a la primera canasta con el resto:
  
  • Para todas las cestas con más de un artículo:
    
    1. Tomamos dos elementos del final de la canasta, calculamos su elemento primario, eliminamos ambos elementos
    2. Agregue el padre calculado a la 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 }); } } 

• Mueva los elementos raíz de las cestas al conjunto de baterías 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]); } } 

Crear evidencia para elementos agregados

La prueba de la inclusión del elemento en la batería ( Proof ) será el Camino Merkle, que consiste en una cadena de ProofStep de ProofStep . Si el camino no conduce a ninguna parte, entonces la prueba está equivocada.

 ///         . #[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 la información obtenida anteriormente durante la adición del elemento (Estructura de Update ), puede crear evidencia de que el elemento se agregó a la batería. Para hacer esto, recorra la tabla de cambios realizados y agregue cada paso a la ruta de Merkle, que posteriormente servirá como prueba:

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

Prueba de evidencia de un artículo

La comprobación de la prueba de inclusión de un elemento (prueba de inclusión) se reduce a seguir el camino de Merkle, hasta que conduce al elemento raíz 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:

Eliminar elementos

Para quitar un elemento de la batería, debe proporcionar una prueba válida de que el elemento está allí. Usando los datos de la prueba, podemos calcular los nuevos elementos raíz de la batería para los cuales esta prueba ya no será cierta.

El algoritmo es el siguiente:

1. Al igual que con la adición, organizamos un conjunto de cestas vacías correspondientes a los árboles Merkle con una altura igual a dos del índice de la cesta
2. Inserte artículos de los escalones del camino Merkle en las cestas; el índice de la cesta es igual al número de paso actual
3. Eliminamos el elemento raíz al que conduce la ruta de la prueba.
4. Al igual que con la adición, calculamos los nuevos elementos raíz, combinando los elementos de las canastas en pares y moviendo el resultado de la unión a la siguiente canasta

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

El proceso de eliminar el elemento "A":

Integración en una red existente

Usando la batería propuesta, los nodos pueden negarse a usar la base de datos para almacenar todos los UTXO, mientras mantienen la capacidad de cambiar el conjunto UTXO. Sin embargo, existe el problema de trabajar con evidencia.

Llamaremos a un nodo validador que utiliza una batería UTXO compacta (nodo de estado compacto) y un validador sin batería - lleno (nodo completo). La existencia de dos clases de nodos crea el problema de integrarlos en una sola red, ya que los nodos compactos requieren prueba de la existencia de UTXO, que se gasta en transacciones, pero los nodos completos no. Si todos los nodos de la red al mismo tiempo y de manera coordinada no cambian a Utreexo, entonces los nodos compactos se quedarán atrás y no podrán trabajar en la red Bitcoin.

Para resolver el problema de integrar nodos compactos en la red, se propone introducir una clase adicional de nodos: puentes . Un nodo puente es un nodo completo que, entre otras cosas, almacena la batería Utreexo y la evidencia de inclusión para todos los UTXO del conjunto UTXO. Los puentes calculan nuevos hashes y actualizan la batería y la evidencia a medida que llegan nuevos bloques con las transacciones. El soporte y la actualización de la batería y la evidencia no imponen una carga computacional adicional en dichos nodos. Los puentes sacrifican espacio en disco: mantenga el orden en orden $$$2n$hashes en comparación con $$$log (n)$hashes para nodos compactos, donde n es la potencia del conjunto UTXO.

Arquitectura de red

Los puentes permiten agregar gradualmente nodos compactos a la red sin cambiar el software de los nodos existentes. Los nodos completos funcionan como antes, distribuyendo transacciones y bloques entre ellos. Los nodos de puente son nodos completos que además almacenan datos de la batería Utreexo y un conjunto de evidencia de inclusión para todos los UTXO en este momento. El nodo puente no se anuncia como tal, pretendiendo ser un nodo completo para todos los nodos completos y un nodo compacto para todos los nodos compactos. Aunque los puentes conectan ambas redes, en realidad, necesitan conectarse en una sola dirección: desde nodos completos existentes hasta nodos compactos. Esto es posible porque el formato de transacción no necesita ser cambiado, y la evidencia de UTXO para nodos compactos puede descartarse, por lo que cualquier nodo compacto puede enviar transacciones a todos los participantes de la red de la misma manera sin la participación de nodos puente.

Conclusión

Revisamos la batería Utreexo e implementamos su prototipo en Rust. Examinamos la arquitectura de red, que integrará los nodos en función de la batería. La ventaja de la captura compacta es el tamaño de los datos almacenados, que depende logarítmicamente de la potencia de muchos UTXO, lo que reduce en gran medida los requisitos de espacio en disco y el rendimiento de almacenamiento para dichos nodos. La desventaja es el tráfico adicional de nodos para la transferencia de evidencia, pero las técnicas de agregación de evidencia (cuando una prueba demuestra la existencia de varios elementos) y el almacenamiento en caché pueden ayudar a mantener el tráfico dentro de límites aceptables.

Referencias

• Utreexo Rust Prototype GitHub
• Thaddeus Dryja - Utreexo: un acumulador dinámico basado en hash optimizado para el conjunto Bitcoin UTXO
• Ilustraciones animadas de un artículo