¡Hola, Habr!
En la red Bitcoin, todos los nodos, mediante consenso, acuerdan un conjunto de UTXO: cuántas monedas están disponibles para gastar, para quién exactamente y bajo qué condiciones. El conjunto UTXO es el conjunto mínimo de datos requerido para un nodo validador, sin el cual el nodo no podrá verificar la validez de las transacciones entrantes y los bloques que las contienen.
En este sentido, se está intentando por todos los medios reducir la representación almacenada de este conjunto, comprimirlo sin perder las garantías de seguridad. Cuanto menor sea el volumen de datos almacenados, menores serán los requisitos de espacio en disco del nodo validador, lo que hace que el lanzamiento de un nodo validador sea económico, le permite expandir la red y, por lo tanto, aumentar la estabilidad de la red.
En esta publicación publicaremos un prototipo de Rust de una propuesta reciente de un coautor. , - , lo que permite reducir los requisitos de espacio en disco para los nodos validadores.
Cual es el problema
Uno de los eternos problemas de Bitcoin ha sido su escalabilidad. La idea de “su propio banco” requiere que los participantes de la red mantengan registros de todos los fondos disponibles para su uso. En Bitcoin, los fondos disponibles se expresan como un conjunto de productos no gastados: un conjunto UTXO. Si bien esta no es una representación particularmente intuitiva, es beneficiosa en términos de rendimiento de implementación sobre una representación en la que cada "billetera" tiene un "saldo" como una entrada separada, y también agrega privacidad (p. ej. ).
Es importante distinguir entre el historial de transacciones (lo que se llama blockchain) y el estado actual del sistema. El historial de transacciones de Bitcoin ocupa actualmente unos 200 GB de espacio en disco y sigue creciendo. Sin embargo, el estado del sistema es mucho más pequeño, del orden de 4 GB, y sólo tiene en cuenta el hecho de que alguien posee monedas actualmente. El volumen de estos datos también aumenta con el tiempo, pero a un ritmo mucho más lento y en ocasiones incluso tiende a disminuir (ver CDPV).
Los clientes ligeros (SPV) comercializan garantías de seguridad por la capacidad de no almacenar ningún estado mínimo (conjunto UTXO) que no sean claves privadas.
UTXO y conjunto UTXO
UTXO (Salida de transacción no gastada) es la salida de transacción no gastada, el punto final del viaje de cada Satoshi transferido en transacciones. Los productos no gastados se convierten en insumos de nuevas transacciones y, por lo tanto, se gastan y se eliminan del conjunto UTXO.
Los nuevos UTXO siempre se crean mediante transacciones:
- Transacciones de Coinbase sin entradas: cree nuevos UTXO cuando los mineros emitan monedas
- transacciones regulares: cree nuevos UTXO mientras gasta un cierto conjunto de UTXO existentes
Proceso de trabajo con UTXO:
Las billeteras cuentan la cantidad de monedas disponibles para gastar (saldo) en función de la cantidad de UTXO disponibles en esta billetera para gastar.
Cada nodo validador, para evitar intentos de doble gasto, debe monitorear el conjunto todos UTXO al verificar cada transacciones cada cuadra.
El nodo debe tener lógica:
- Adiciones al conjunto UTXO
- Eliminaciones del conjunto UTXO
- Comprobando la presencia de un único UTXO en un conjunto
Hay formas de reducir los requisitos de información almacenada sobre un conjunto, manteniendo al mismo tiempo la capacidad de agregar y eliminar elementos, verificar y probar la existencia de un elemento en un conjunto usando .
Baterías para UTXO
La idea de utilizar baterías para almacenar múltiples UTXO .
El conjunto UTXO se construye sobre la marcha, durante la descarga del bloque inicial (IBD), se almacena de forma completa y permanente, mientras que su contenido cambia después de procesar las transacciones de cada bloque nuevo y correcto de la red. Este proceso requiere descargar aproximadamente 200 GB de datos en bloque y verificar cientos de millones de firmas digitales. Una vez completado el proceso IBD, la conclusión es que el conjunto UTXO ocupará aproximadamente 4 GB.
Sin embargo, en el caso de los acumuladores, las reglas de consenso para los fondos se reducen a la verificación y generación de pruebas criptográficas, y la carga del seguimiento de los fondos disponibles se traslada al propietario de esos fondos, quien proporciona pruebas de su existencia y propiedad.
Un acumulador puede denominarse representación compacta de un conjunto. El tamaño de la representación almacenada debe ser constante , o aumentar sublinealmente con respecto a la cardinalidad del conjunto y el tamaño del propio elemento, por ejemplo , donde n es la cardinalidad del conjunto almacenado.
En este caso, el acumulador debería permitir generar una prueba de la inclusión de un elemento en el conjunto (prueba de inclusión) y permitir verificar eficazmente esta prueba.
La bateria se llama dinámico Si le permite agregar elementos y eliminar elementos de un conjunto.
Un ejemplo de una batería de este tipo sería . Un acumulador de este tipo tiene un tamaño constante de representación almacenada, pero requiere la presencia secreto compartido (configuración confiable). Este requisito niega la aplicabilidad de un acumulador de este tipo para redes no confiables como Bitcoin, ya que la fuga de datos durante la generación secreta puede permitir a los atacantes crear pruebas falsas de la existencia de un UTXO, engañando a los nodos con un conjunto de UTXO basado en dicho acumulador.
Utreexo
El diseño Utreexo propuesto por Thaddeus Dryja permite crear dinámico acumulador sin configuración confiable.
Utreexo es un bosque de binario perfecto y es un desarrollo de las ideas presentadas en , agregando la capacidad de eliminar elementos de un conjunto.
Estructura lógica de la batería
Las celdas de la batería están dispuestas en un bosque de árboles binarios ideales. Los árboles están ordenados por altura. Esta representación fue elegida como la más visual y permite visualizar la fusión de árboles durante las operaciones en la batería.
El autor señala que como todos los árboles del bosque son ideales, su altura se expresa como una potencia de dos, de la misma manera que cualquier número natural se puede representar como una suma de potencias de dos. En consecuencia, cualquier conjunto de hojas se puede agrupar en árboles binarios y, en todos los casos, agregar un nuevo elemento requiere conocimiento. sólo sobre los nodos raíz de los árboles almacenados.
Por tanto, la representación almacenada del acumulador Utreexo es una lista de nodos raíz (raíz de Merkle), y no todo el bosque de árboles.
Representemos la lista de elementos raíz como Vec<Option<Hash>>. Tipo opcional Option<Hash> indica que puede faltar el elemento raíz, lo que significa que no hay ningún árbol con la altura adecuada en el acumulador.
/// 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, describamos la función. parent(), que reconoce el nodo padre de dos elementos determinados.
función padre ()
Como estamos usando árboles Merkle, el padre de cada uno de los dos nodos es un nodo que almacena el hash de la concatenación de los hashes de los nodos secundarios:
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[..])
}El autor señala que para prevenir los ataques descritos por Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir y Sébastien Zimmer en
, además de los dos hashes, también se debe agregar a la concatenación la altura dentro del árbol.
A medida que agrega elementos al acumulador, debe realizar un seguimiento de qué elementos raíz se modifican. Si sigue el camino de cambiar los elementos raíz para cada elemento que agregue, luego podrá construir una prueba de la presencia de estos elementos.
Realice un seguimiento de los cambios a medida que los agrega
Para realizar un seguimiento de los cambios realizados, declaremos la estructura. Update, que almacenará datos sobre cambios de nodo.
#[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:
- Crea una serie de cestas de elementos raíz.
new_rootsy coloque los elementos raíz existentes allí, uno para cada depósito:
código
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 que se agregarán (matriz
insertions) al primer carritonew_roots[0]:
código
new_roots[0].extend_from_slice(insertions);- Fusiona los artículos añadidos a la primera cesta con el resto:
- Para todos los carritos con más de un artículo:
- Tome dos elementos del final de la canasta, calcule su padre, elimine ambos elementos
- Agregue el padre calculado al siguiente carrito
- Para todos los carritos con más de un artículo:
código
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 los contenedores a la matriz de acumuladores resultante
código
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]);
}
}Creando una prueba para elementos agregados
Prueba de inclusión de la celda en la batería (Proof) servirá como Merkle Path, que consta de una cadena ProofStep. Si el camino no lleva a ninguna parte, entonces la prueba es incorrecta.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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 al agregar un elemento (estructura Update), puede crear pruebas de que se ha agregado un elemento a la batería. Para ello, repasamos la tabla de cambios realizados y sumamos cada paso al camino de Merkle, que posteriormente nos servirá como prueba:
código
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
}
}Proceso de creación de una prueba.
Comprobando la prueba de un elemento.
Verificar la prueba de inclusión de un elemento se reduce a seguir el camino de Merkle hasta que conduzca a un 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, ¤t_parent)
} else {
parent(¤t_parent, &s.hash)
};
}
current_parent == expected
} else {
false
}
}Claramente:
Proceso de verificación de la prueba de A
Eliminando elementos
Para quitar una celda de una batería, debe proporcionar evidencia válida de que la celda está allí. Utilizando los datos de la prueba, es posible calcular nuevos elementos raíz del acumulador para los cuales la prueba dada ya no será cierta.
El algoritmo es como sigue:
- Al igual que con la suma, organizamos un conjunto de cestas vacías correspondientes a árboles Merkle con una altura igual a la potencia de dos del índice de cestas.
- Insertamos elementos de los pasos del camino Merkle en las cestas; el índice de la cesta es igual al número del paso actual
- Eliminamos el elemento raíz al que conduce el camino de la prueba.
- Al igual que con la suma, calculamos nuevos elementos raíz combinando elementos de cestas en pares y moviendo el resultado de la unión a la siguiente cesta.
código
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 eliminación del elemento "A":
Integración en una red existente
Al utilizar el acumulador propuesto, los nodos pueden evitar el uso de una base de datos para almacenar todos los UTXO y al mismo tiempo pueden cambiar el conjunto de UTXO. Sin embargo, surge el problema de trabajar con evidencia.
Llamemos al nodo validador que usa el acumulador UTXO. compacto (nodo de estado compacto), y el validador sin acumulador es completar (nodo completo). La existencia de dos clases de nodos crea un problema para integrarlos en una sola red, ya que los nodos compactos requieren prueba de la existencia de UTXO, que se gastan en transacciones, mientras que los nodos completos no. Si todos los nodos de la red no cambian simultáneamente y de manera coordinada para usar Utreexo, entonces los nodos compactos quedarán atrás y no podrán operar 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 también almacena la batería de Utreexo y la prueba de encendido para todos UTXO del conjunto UTXO. Los puentes calculan nuevos hashes y actualizan el acumulador y las pruebas a medida que llegan nuevos bloques de transacciones. Mantener y actualizar el acumulador y las pruebas no impone una carga computacional adicional en dichos nodos. Los puentes sacrifican espacio en disco: es necesario mantener las cosas organizadas hashes, en comparación con hashes para nodos compactos, donde n es la potencia del conjunto UTXO.
Red de arquitectura
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 puente son nodos completos que además almacenan datos de la batería de Utreexo y un conjunto de pruebas de inclusión para todos UTXO por ahora. 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 compactos. Aunque los puentes conectan ambas redes, en realidad solo necesitan conectarlas en una dirección: desde nodos completos existentes hasta nodos compactos. Esto es posible porque no es necesario cambiar el formato de la transacción y las pruebas UTXO para nodos compactos se pueden descartar, por lo que cualquier nodo compacto puede transmitir transacciones de manera similar a todos los participantes de la red sin la participación de los nodos puente.
Conclusión
Analizamos la batería Utreexo e implementamos su prototipo en Rust. Analizamos la arquitectura de red que permitirá la integración de nodos basados en baterías. La ventaja de las capturas compactas es el tamaño de los datos almacenados, que depende logarítmicamente de la potencia del conjunto de UTXO, lo que reduce en gran medida los requisitos de espacio en disco y rendimiento de almacenamiento para dichos nodos. La desventaja es el tráfico de nodo adicional para transmitir pruebas, pero las técnicas de agregación de pruebas (cuando una prueba prueba la existencia de varios elementos) y el almacenamiento en caché pueden ayudar a mantener el tráfico dentro de límites aceptables.
referencias:
- -
Fuente: habr.com