Ola Habr!
Na rede Bitcoin, todos os nodos, por consenso, acordan un conxunto de UTXO: cantas moedas están dispoñibles para gastar, a quen exactamente e en que condicións. O conxunto UTXO é o conxunto mínimo de datos necesarios para un nodo validador, sen o cal o nodo non poderá verificar a validez das transaccións entrantes e dos bloques que as conteñen.
Neste sentido, estase intentando por todos os xeitos reducir a representación almacenada deste conxunto, para comprimila sen perder as garantías de seguridade. Canto menor sexa o volume de datos almacenados, menores serán os requisitos de espazo en disco do nodo validador, o que fai que o lanzamento dun nodo validador sexa barato, permítelle ampliar a rede e, así, aumentar a estabilidade da rede.
Neste post publicaremos un prototipo de Rust dunha proposta recente dun coautor , - , que permite reducir os requisitos de espazo en disco para os nodos validadores.
¿Queres facer?
Un dos problemas perennes de Bitcoin foi a súa escalabilidade. A idea do "seu propio banco" require que os participantes da rede manteñan rexistros de todos os fondos dispoñibles para o seu uso. En Bitcoin, os fondos dispoñibles exprésanse como un conxunto de saídas non gastadas: un conxunto UTXO. Aínda que esta non é unha representación especialmente intuitiva, é beneficiosa en termos de rendemento de implementación fronte a unha representación na que cada "cartera" ten un "saldo" como entrada separada e tamén engade privacidade (p. ex. ).
É importante distinguir entre o historial das transaccións (o que se chama blockchain) e o estado actual do sistema. O historial de transaccións de Bitcoin ocupa actualmente uns 200 GB de espazo en disco e segue crecendo. Non obstante, o estado do sistema é moito menor, da orde de 4 GB, e só ten en conta o feito de que alguén actualmente posúe moedas. O volume destes datos tamén aumenta co paso do tempo, pero a un ritmo moito máis lento e ás veces mesmo tende a diminuír (ver CDPV).
Garantías de seguridade comerciais dos clientes lixeiros (SPV) para a posibilidade de almacenar ningún estado mínimo (conxunto de UTXO) que non sexan as claves privadas.
UTXO e UTXO-set
UTXO (Saída de transacción non gastada) é a saída da transacción non gastada, o punto final da viaxe de cada Satoshi transferido nas transaccións. As saídas non gastadas convértense en entradas de novas transaccións e, polo tanto, gástanse (gastan) e elimínanse do conxunto UTXO.
As novas UTXO son sempre creadas por transaccións:
- Transaccións coinbase sen entradas: crea novas UTXO cando os mineiros emitan moedas
- transaccións regulares: crea novas UTXO mentres gastas un determinado conxunto de UTXO existentes
Proceso de traballo con UTXO:
As carteiras contan o número de moedas dispoñibles para gastar (saldo) en función da cantidade de UTXO dispoñible para esta carteira para gastar.
Cada nodo validador, para evitar intentos de dobre gasto, debe supervisar o conxunto Todo UTXO ao comprobar cada un transaccións de cada un bloque.
O nodo debe ter unha lóxica:
- Complementos a UTXO-set
- Eliminacións de UTXO-set
- Comprobación da presenza dun único UTXO nun conxunto
Hai formas de reducir os requisitos para a información almacenada sobre un conxunto, mantendo a capacidade de engadir e eliminar elementos, comprobar e probar a existencia dun elemento nun conxunto usando .
Baterías para UTXO
A idea de usar pilas para almacenar múltiples UTXO .
O UTXO-set constrúese sobre a marcha, durante a descarga do bloque inicial (IBD), almacenado de forma completa e permanente, mentres que o seu contido cambia tras procesar as transaccións de cada bloque novo e correcto da rede. Este proceso require descargar aproximadamente 200 GB de datos de bloque e verificar centos de millóns de sinaturas dixitais. Despois de completar o proceso IBD, a conclusión é que o conxunto UTXO ocupará uns 4 GB.
Non obstante, cos acumuladores, as regras de consenso para os fondos redúcense á verificación e xeración de probas criptográficas, e a carga do seguimento dos fondos dispoñibles trasládase ao propietario deses fondos, quen proporciona probas da súa existencia e propiedade.
Un acumulador pódese chamar representación compacta dun conxunto. O tamaño da representación almacenada debe ser constante , ou aumentar sublinealmente con respecto á cardinalidade do conxunto e ao tamaño do propio elemento, por exemplo , onde n é a cardinalidade do conxunto almacenado.
Neste caso, o acumulador debería permitir xerar unha proba da inclusión dun elemento no conxunto (proba de inclusión) e facer posible a verificación efectiva desta proba.
A batería chámase dinámico se permite engadir elementos e eliminar elementos dun conxunto.
Un exemplo de tal batería sería . Tal acumulador ten un tamaño constante de representación almacenada, pero require a presenza segredo compartido (configuración de confianza). Este requisito nega a aplicabilidade deste acumulador para redes sen confianza como Bitcoin, xa que a fuga de datos durante a xeración de segredos pode permitir aos atacantes crear probas falsas da existencia dun UTXO, enganando os nós cun conxunto de UTXO baseado nese acumulador.
Utreexo
O deseño Utreexo proposto por Thaddeus Dryja fai posible crear dinámico аккумулятор sen configuración de confianza.
Utreexo é un bosque de binario perfecto e é un desenvolvemento das ideas presentadas en , engadindo a posibilidade de eliminar elementos dun conxunto.
Estrutura lóxica da batería
As celas da batería están dispostas nun bosque de árbores binarias ideais. As árbores están ordenadas pola altura. Esta representación elixiuse como a máis visual e permite visualizar a fusión de árbores durante as operacións na batería.
O autor sinala que, dado que todas as árbores do bosque son ideais, a súa altura exprésase como unha potencia de dous, do mesmo xeito que calquera número natural pode representarse como unha suma de potencias de dous. En consecuencia, calquera conxunto de follas pódese agrupar en árbores binarias e, en todos os casos, engadir un novo elemento require coñecementos. só sobre os nodos raíz das árbores almacenadas.
Así, a representación almacenada do acumulador Utreexo é unha lista de nodos raíz (raíz de Merkle), e non todo o bosque de árbores.
Imos representar a lista de elementos raíz como Vec<Option<Hash>>. Tipo opcional Option<Hash> indica que pode faltar o elemento raíz, o que significa que non hai ningunha árbore coa altura adecuada no 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],
}
}
}Engadindo elementos
En primeiro lugar, imos describir a función parent(), que recoñece o nodo pai para dous elementos dados.
función parent().
Xa que estamos a usar árbores Merkle, o pai de cada un dos dous nós é un nodo que almacena o hash da concatenación dos hash dos nodos fillos:
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[..])
}O autor sinala que para evitar os ataques descritos por Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir e Sebastien Zimmer en
, ademais dos dous hash, tamén se debe engadir á concatenación a altura dentro da árbore.
Cando engades elementos ao acumulador, cómpre facer un seguimento dos elementos raíz que se modifican. Seguindo o camiño de cambiar os elementos raíz para cada elemento que engades, podes construír máis tarde unha proba da presenza destes elementos.
Rastrexa os cambios mentres os engades
Para seguir os cambios realizados, declaremos a estrutura Update, que almacenará datos sobre os cambios de nodos.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Para engadir un elemento á batería, necesitas:
- Crea unha matriz de cestas de elementos raíz
new_rootse coloque alí os elementos raíz existentes, un para cada balde:
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);
}- Engade os elementos a engadir (matriz
insertions) ao primeiro carronew_roots[0]:
Código
new_roots[0].extend_from_slice(insertions);- Combina os elementos engadidos á primeira cesta co resto:
- Para todos os carros con máis dun artigo:
- Colle dous elementos do final da cesta, calcula o seu pai, elimina ambos elementos
- Engade o pai calculado ao seguinte carro
- Para todos os carros con máis dun artigo:
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 });
}
}- Move os elementos raíz das papeleiras á 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]);
}
}Creación dunha proba para elementos engadidos
Proba de inclusión da pila na batería (Proof) servirá como o Camiño Merkle, composto por unha cadea ProofStep. Se o camiño non leva a ningún lado, entón a proba é 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,
}Utilizar a información obtida anteriormente ao engadir un elemento (estrutura Update), pode crear probas de que se engadiu un elemento á batería. Para iso, repasamos a táboa de cambios realizados e engadimos cada paso ao camiño de Merkle, que posteriormente servirá de proba:
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 dunha proba
Comprobación da proba dun elemento
Comprobar a proba de inclusión dun elemento redúcese a seguir o camiño de Merkle ata que conduce 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
}
}Visualmente:
Proceso de comprobación da proba de A
Eliminando elementos
Para eliminar unha pila dunha batería, debes proporcionar unha evidencia válida de que a cela está alí. Usando os datos da demostración, é posible calcular novos elementos raíz do acumulador para os que a demostración dada xa non será certa.
O algoritmo é o seguinte:
- Do mesmo xeito que con adición, organizamos un conxunto de cestos baleiros correspondentes ás árbores Merkle cunha altura igual á potencia de dous do índice de cestas.
- Introducimos elementos dos chanzos do camiño de Merkle nas cestas; o índice da cesta é igual ao número do paso actual
- Eliminamos o elemento raíz ao que leva o camiño da proba
- Do mesmo xeito que con engadir, calculamos novos elementos raíz combinando elementos de cestas por parellas e movendo o resultado da unión á seguinte 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;
}
}O proceso de eliminación do elemento "A":
Integración nunha rede existente
Usando o acumulador proposto, os nodos poden evitar usar unha base de datos para almacenar todos os UTXO aínda que poden cambiar o conxunto de UTXO. Non obstante, xorde o problema de traballar con probas.
Chamemos ao nodo validador que usa o acumulador UTXO compacto (nodo de estado compacto), e o validador sen acumulador é completo (nodo completo). A existencia de dúas clases de nodos crea un problema para integralos nunha única rede, xa que os nodos compactos requiren a proba da existencia de UTXO, que se gastan en transaccións, mentres que os nodos completos non. Se todos os nós de rede non cambian simultáneamente e de forma coordinada ao uso de Utreexo, entón os nodos compactos quedarán atrás e non poderán operar na rede Bitcoin.
Para resolver o problema da integración de nodos compactos na rede, proponse introducir unha clase adicional de nodos: pontes. Un nodo ponte é un nodo completo que tamén almacena a batería de Utreexo e a proba de encendido Todo UTXO de UTXO-set. Bridges calcula novos hash e actualiza o acumulador e as probas a medida que chegan novos bloques de transaccións. Manter e actualizar o acumulador e as probas non impón unha carga computacional adicional a tales nós. As pontes sacrifican espazo no disco: hai que manter as cousas organizadas hash, en comparación con hash para nodos compactos, onde n é a potencia do conxunto UTXO.
Arquitectura de rede
As pontes permiten engadir gradualmente nodos compactos á rede sen cambiar o software dos nodos existentes. Os nodos completos funcionan como antes, distribuíndo transaccións e bloques entre eles. Os nodos ponte son nodos completos que almacenan ademais os datos da batería de Utreexo e un conxunto de probas de inclusión Todo UTXO por agora. O nodo ponte non se anuncia como tal, pretendendo ser un nodo completo para todos os nodos completos e un nodo compacto para todos os compactos. Aínda que as pontes conectan ambas redes xuntas, en realidade só precisan conectalas nunha dirección: desde os nodos completos existentes ata os nodos compactos. Isto é posible porque non é necesario cambiar o formato de transacción e pódense descartar as probas de UTXO para nodos compactos, polo que calquera nodo compacto pode transmitir de forma similar transaccións a todos os participantes da rede sen a participación dos nodos ponte.
Conclusión
Observamos a batería Utreexo e implementamos o seu prototipo en Rust. Observamos a arquitectura de rede que permitirá a integración de nós baseados en batería. A vantaxe das capturas compactas é o tamaño dos datos almacenados, que depende logarítmicamente da potencia do conxunto de UTXOs, o que reduce moito os requisitos de espazo en disco e rendemento de almacenamento para tales nodos. A desvantaxe é o tráfico de nodos adicional para transmitir probas, pero as técnicas de agregación de probas (cando unha proba proba a existencia de varios elementos) e o caché poden axudar a manter o tráfico dentro de límites aceptables.
referencias:
- -
Fonte: www.habr.com