Ey Habr!
Bitcoin ağında, tüm düğümler fikir birliği yoluyla bir dizi UTXO üzerinde anlaşırlar: Harcama için kaç adet coinin mevcut olduğu, tam olarak kime ve hangi koşullar altında. UTXO kümesi, bir doğrulayıcı düğüm için gereken minimum veri kümesidir; bu küme olmadan düğüm, gelen işlemlerin ve bunları içeren blokların geçerliliğini doğrulayamaz.
Bu bağlamda, bu kümenin depolanan gösterimini azaltmak, güvenlik garantilerini kaybetmeden sıkıştırmak için mümkün olan her şekilde girişimde bulunulmaktadır. Depolanan verilerin hacmi ne kadar küçük olursa, doğrulayıcı düğümün disk alanı gereksinimleri de o kadar düşük olur; bu, doğrulayıcı düğümün başlatılmasını ucuz hale getirir, ağı genişletmenize ve böylece ağın kararlılığını artırmanıza olanak tanır.
Bu yazıda ortak yazarlardan birinin yakın zamanda sunduğu bir teklifin Rust prototipini yayınlayacağız. , - Doğrulayıcı düğümler için disk alanı gereksinimlerinin azaltılmasına olanak tanır.
Sorun ne
Bitcoin'in daimi sorunlarından biri ölçeklenebilirliği olmuştur. "Kendi bankanız" fikri, ağ katılımcılarının kullanıma hazır tüm fonların kayıtlarını tutmasını gerektirir. Bitcoin'de mevcut fonlar, bir dizi harcanmamış çıktı (UTXO seti) olarak ifade edilir. Bu özellikle sezgisel bir temsil olmasa da, her "cüzdan"ın ayrı bir giriş olarak bir "bakiyeye" sahip olduğu ve ayrıca gizlilik eklediği bir temsile göre uygulama performansı açısından faydalıdır (örn. ).
İşlemlerin geçmişi (blok zincir olarak adlandırılan) ile sistemin mevcut durumu arasında ayrım yapmak önemlidir. Bitcoin işlem geçmişi şu anda yaklaşık 200 GB disk alanı kaplıyor ve büyümeye devam ediyor. Bununla birlikte, sistem durumu 4 GB civarında çok daha küçüktür ve yalnızca birisinin halihazırda madeni paraya sahip olduğu gerçeğini hesaba katar. Bu verilerin hacmi de zamanla artar, ancak çok daha yavaş bir oranda ve hatta bazen azalma eğilimi gösterir (bkz. CDPV).
Hafif istemciler (SPV'ler), özel anahtarlar dışında hiçbir minimum durumu (UTXO seti) saklama yeteneği için ticari güvenlik garantileri verir.
UTXO ve UTXO seti
UTXO (Harcanmamış İşlem Çıkışı), işlemlerde aktarılan her Satoshi'nin yolculuğunun bitiş noktası olan harcanmamış işlem çıktısıdır. Harcanmamış çıktılar, yeni işlemlerin girdisi haline gelir ve dolayısıyla harcanır (harcanır) ve UTXO kümesinden çıkarılır.
Yeni UTXO'lar her zaman işlemler tarafından oluşturulur:
- Girdisiz Coinbase işlemleri: Madenciler coin çıkardığında yeni UTXO'lar oluşturun
- düzenli işlemler: belirli bir dizi mevcut UTXO'yu harcarken yeni UTXO'lar oluşturun
UTXO ile çalışma süreci:
Cüzdanlar, bu cüzdanın harcayabileceği UTXO miktarına bağlı olarak, harcanabilecek para sayısını (bakiye) sayar.
Çift harcama girişimlerini önlemek için her doğrulayıcı düğümün seti izlemesi gerekir Tüm UTXO kontrol ederken her işlemler her engellemek.
Düğümün mantığı olmalıdır:
- UTXO setine eklemeler
- UTXO setinden silme işlemleri
- Bir sette tek bir UTXO'nun varlığını kontrol etme
Bir küme hakkında saklanan bilgi gereksinimlerini azaltmanın, aynı zamanda öğe ekleme ve çıkarma yeteneğini korumanın, bir kümedeki bir öğenin varlığını kontrol etme ve kanıtlamanın yollarını kullanarak yöntemler vardır. .
UTXO için piller
Birden fazla UTXO'yu depolamak için pil kullanma fikri .
UTXO seti, ilk blok indirme (IBD) sırasında anında oluşturulur, tam ve kalıcı olarak saklanır ve içeriği, ağdaki her yeni ve doğru bloktan gelen işlemlerin işlenmesinden sonra değişir. Bu işlem yaklaşık 200 GB blok verinin indirilmesini ve yüz milyonlarca dijital imzanın doğrulanmasını gerektirir. IBD işlemi tamamlandıktan sonra sonuç olarak UTXO setinin yaklaşık 4 GB yer kaplayacağı ortaya çıkıyor.
Bununla birlikte, akümülatörlerde, fonlar için fikir birliği kuralları, kriptografik kanıtların doğrulanması ve oluşturulmasına indirgenir ve mevcut fonların takibinin yükü, bu fonların varlığına ve mülkiyetine dair kanıt sağlayan bu fonların sahibine kaydırılır.
Akümülatöre bir kümenin kompakt temsili denilebilir. Saklanan gösterimin boyutu sabit olmalıdır veya kümenin önem düzeyine ve öğenin boyutuna göre alt çizgisel olarak artar; örneğin n, saklanan kümenin önem derecesidir.
Bu durumda akümülatör, bir elemanın sete dahil edildiğine dair bir kanıt oluşturulmasına (dahil edilme kanıtı) izin vermeli ve bu kanıtın etkili bir şekilde doğrulanmasını mümkün kılmalıdır.
Pil denir dinamik if, bir kümeden öğe eklemenize ve öğeleri kaldırmanıza olanak tanır.
Böyle bir pilin bir örneği şöyle olabilir: . Böyle bir akümülatör, sabit boyutta depolanmış temsile sahiptir, ancak varlığı gerektirir paylaşılan sır (güvenilir kurulum). Bu gereklilik, böyle bir akümülatörün Bitcoin gibi güvenilir olmayan ağlar için uygulanabilirliğini ortadan kaldırır; çünkü gizli oluşturma sırasında veri sızıntısı, saldırganların bir UTXO'nun varlığına dair sahte kanıt oluşturmasına ve bu tür bir akümülatöre dayalı bir UTXO seti ile düğümleri aldatmasına olanak tanıyabilir.
Utreexo
Thaddeus Dryja tarafından önerilen Utreexo tasarımı, dinamik аккумулятор olmadan güvenilir kurulum.
Utreexo mükemmel bir ikili ormandır ve burada sunulan fikirlerin bir gelişimidir. , bir kümeden öğeleri kaldırma yeteneğinin eklenmesi.
Pil Mantıksal Yapısı
Pil hücreleri ideal ikili ağaçlardan oluşan bir ormanda düzenlenmiştir. Ağaçlar boylarına göre sıralanır. Bu gösterim en görsel olanı olarak seçilmiştir ve akü üzerinde yapılan işlemler sırasında ağaçların birleşmesini görselleştirmenize olanak tanır.
Yazar, ormandaki tüm ağaçların ideal olması nedeniyle, herhangi bir doğal sayının ikinin kuvvetlerinin toplamı olarak temsil edilebilmesi gibi, boylarının da ikinin kuvvetleri olarak ifade edildiğini belirtiyor. Buna göre, herhangi bir yaprak kümesi ikili ağaçlar halinde gruplandırılabilir ve her durumda yeni bir öğenin eklenmesi bilgi gerektirir. yalnızca depolanan ağaçların kök düğümleri hakkında.
Bu nedenle, Utreexo akümülatörünün depolanan temsili kök düğümlerin (Merkle kökü) bir listesidir, ve tüm ağaç ormanı değil.
Kök elemanların listesini şu şekilde temsil edelim: Vec<Option<Hash>>. İsteğe bağlı tip Option<Hash> kök elemanın eksik olabileceğini, yani akümülatörde uygun yükseklikte ağaç bulunmadığını belirtir.
/// 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],
}
}
}Öğe ekleme
Öncelikle fonksiyonu tanımlayalım parent()Verilen iki öğe için üst düğümü tanıyan.
ebeveyn() işlevi
Merkle ağaçlarını kullandığımız için, iki düğümden her birinin ebeveyni, alt düğümlerin karmalarının birleşiminin karma değerini saklayan bir düğümdür:
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[..])
}Yazar, Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir ve Sebastien Zimmer'in anlattığı saldırıları önlemek için şunları belirtiyor:
birleştirme işlemine iki hash'in yanı sıra ağacın içindeki yükseklik de eklenmelidir.
Akümülatöre öğe ekledikçe hangi kök öğelerin değiştiğini takip etmeniz gerekir. Eklediğiniz her öğe için kök öğeleri değiştirme yolunu izleyerek daha sonra bu öğelerin varlığına dair bir kanıt oluşturabilirsiniz.
Değişiklikleri ekledikçe takip edin
Yapılan değişiklikleri takip etmek için yapıyı deklare edelim. UpdateDüğüm değişiklikleriyle ilgili verileri depolayacak.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Aküye bir eleman eklemek için şunlara ihtiyacınız vardır:
- Kök öğelerden oluşan bir dizi sepet oluşturun
new_rootsve mevcut kök öğeleri her paket için bir tane olacak şekilde buraya yerleştirin:
Kod
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);
}- Eklenecek öğeleri ekleyin (dizi
insertions) ilk arabayanew_roots[0]:
Kod
new_roots[0].extend_from_slice(insertions);- İlk sepete eklenen ürünleri geri kalanlarla birleştirin:
- Birden fazla ürün içeren tüm sepetler için:
- Sepetin sonundan iki eleman alın, ebeveynlerini hesaplayın, her iki elemanı da çıkarın
- Hesaplanan ebeveyni bir sonraki sepete ekleyin
- Birden fazla ürün içeren tüm sepetler için:
Kod
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 });
}
}- Kök öğeleri kutulardan elde edilen akümülatör dizisine taşıyın
Kod
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]);
}
}Eklenen öğeler için kanıt oluşturma
Hücrenin aküye dahil edildiğine dair kanıt (Proof) bir zincirden oluşan Merkle Yolu görevi görecek ProofStep. Eğer yol hiçbir yere çıkmıyorsa kanıt yanlıştır.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Bir öğe (yapı) eklerken daha önce elde edilen bilgilerin kullanılması Update), pile bir elemanın eklendiğine dair kanıt oluşturabilirsiniz. Bunu yapmak için, yapılan değişiklikler tablosunu inceliyoruz ve her adımı daha sonra kanıt olarak hizmet edecek olan Merkle'nin yoluna ekliyoruz:
Kod
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
}
}Kanıt oluşturma süreci
Bir elemanın kanıtını kontrol etmek
Bir öğenin dahil edilme kanıtını kontrol etmek, mevcut bir kök öğeye ulaşana kadar Merkle yolunu takip etmekten ibarettir:
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
}
}görme:
A'nın kanıtını kontrol etme süreci
Öğeleri kaldırma
Pilden bir hücreyi çıkarmak için hücrenin orada olduğuna dair geçerli bir kanıt sunmanız gerekir. İspattan elde edilen verileri kullanarak, akümülatörün, verilen ispatın artık geçerli olmayacağı yeni kök elemanlarını hesaplamak mümkündür.
Algoritma aşağıdaki gibidir:
- Ek olarak sepet indeksinden ikinin kuvvetine eşit yükseklikte Merkle ağaçlarına karşılık gelen bir dizi boş sepet düzenliyoruz.
- Merkle yolunun basamaklarından elemanları sepetlere yerleştiriyoruz; sepet indeksi geçerli adımın sayısına eşittir
- Kanıttan gelen yolun götürdüğü kök öğeyi kaldırıyoruz
- Eklemede olduğu gibi, sepetlerdeki elemanları çiftler halinde birleştirerek ve birleştirme sonucunu bir sonraki sepete taşıyarak yeni kök elemanları hesaplarız.
Kod
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" elemanını çıkarma işlemi:
Mevcut bir ağa entegrasyon
Önerilen akümülatörü kullanarak düğümler, UTXO setini değiştirmeye devam ederken tüm UTXO'ları depolamak için bir DB kullanmaktan kaçınabilir. Ancak delillerle çalışma sorunu ortaya çıkıyor.
UTXO akümülatörünü kullanan doğrulayıcı düğümü çağıralım kompakt (kompakt durum düğümü) ve akümülatörsüz doğrulayıcı tam (tam düğüm). İki düğüm sınıfının varlığı, bunları tek bir ağa entegre etme konusunda sorun yaratır; çünkü kompakt düğümler, işlemlerde harcanan UTXO'ların varlığının kanıtını gerektirirken tam düğümler bunu gerektirmez. Tüm ağ düğümleri aynı anda ve koordineli bir şekilde Utreexo kullanımına geçmezse kompakt düğümler geride kalacak ve Bitcoin ağı üzerinde çalışamayacaktır.
Kompakt düğümleri ağa entegre etme sorununu çözmek için, ek bir düğüm sınıfının tanıtılması önerilmektedir - мосты. Köprü düğümü aynı zamanda Utreexo pilini ve açılış kanıtını da saklayan eksiksiz bir düğümdür. Tüm UTXO setinden UTXO. Köprüler yeni karmaları hesaplar ve yeni işlem blokları geldikçe akümülatörü ve kanıtları günceller. Akümülatörün ve kanıtların bakımı ve güncellenmesi, bu tür düğümlere ek hesaplama yükü getirmez. Köprüler disk alanını feda eder: işleri düzenli tutma ihtiyacı ile karşılaştırıldığında karmalar Kompakt düğümler için karmalar; burada n, UTXO kümesinin gücüdür.
Ağ mimarisi
Köprüler, mevcut düğümlerin yazılımını değiştirmeden ağa yavaş yavaş kompakt düğümler eklemeyi mümkün kılar. Tam düğümler daha önce olduğu gibi çalışır ve işlemleri ve blokları kendi aralarında dağıtır. Köprü düğümleri, ek olarak Utreexo pil verilerini ve bir dizi dahil edilme kanıtını depolayan tam düğümlerdir. Tüm Şimdilik UTXO. Köprü düğümü, tüm tam düğümler için tam bir düğüm ve tüm kompakt olanlar için kompakt bir düğüm gibi davranarak kendisini bu şekilde tanıtmaz. Köprüler her iki ağı da birbirine bağlasa da aslında onları yalnızca tek bir yönde bağlamaları gerekir: mevcut tam düğümlerden kompakt düğümlere. Bu mümkündür çünkü işlem formatının değiştirilmesine gerek yoktur ve kompakt düğümler için UTXO kanıtları atılabilir, böylece herhangi bir kompakt düğüm, köprü düğümlerinin katılımı olmadan işlemleri tüm ağ katılımcılarına benzer şekilde yayınlayabilir.
Sonuç
Utreexo bataryasını inceledik ve prototipini Rust'ta uyguladık. Pil tabanlı düğümlerin entegrasyonuna olanak sağlayacak ağ mimarisine baktık. Kompakt yakalamaların avantajı, UTXO kümesinin gücüne logaritmik olarak bağlı olan depolanan verilerin boyutudur; bu, bu tür düğümler için disk alanı ve depolama performansı gereksinimlerini büyük ölçüde azaltır. Dezavantajı, kanıtların iletilmesi için ek düğüm trafiğidir, ancak kanıt toplama teknikleri (bir kanıtın birkaç öğenin varlığını kanıtlaması durumunda) ve önbelleğe alma, trafiği kabul edilebilir sınırlar içinde tutmaya yardımcı olabilir.
referanslar:
- -
Kaynak: habr.com