Эй Хабр!
Bitcoin тармагында, консенсус аркылуу бардык түйүндөр UTXOнун топтому боюнча макулдашат: канча монета сарптоо үчүн жеткиликтүү, кимге так жана кандай шарттарда. UTXO топтому валидатордук түйүн үчүн талап кылынган маалыматтардын минималдуу топтому, ансыз түйүн кириш транзакцияларынын жана аларды камтыган блоктордун тууралыгын текшере албайт.
Ушуга байланыштуу, бул топтомдун сакталган өкүлчүлүгүн азайтуу, коопсуздук кепилдиктерин жоготпостон аны кысуу аракети ар тараптан жасалууда. Сакталган маалыматтардын көлөмү канчалык аз болсо, валидатор түйүнүнүн диск мейкиндигине талаптары ошончолук төмөн болот, бул валидатордук түйүндү ишке киргизүүнү арзан кылат, тармакты кеңейтүүгө жана ошону менен тармактын туруктуулугун жогорулатууга мүмкүндүк берет.
Бул постто биз авторлоштун акыркы сунушунун Rust прототибин жарыялайбыз , - , бул валидатордук түйүндөр үчүн диск мейкиндигине талаптарды азайтууга мүмкүндүк берет.
Көйгөй эмнеде?
Биткойндун көп жылдык көйгөйлөрүнүн бири анын масштабдуулугу болгон. "Өз банкыңыз" идеясы тармактын катышуучуларынан колдонуу үчүн жеткиликтүү болгон бардык каражаттардын эсебин жүргүзүүнү талап кылат. Биткойндо колдо болгон каражаттар сарпталбаган жыйынтыктардын жыйындысы катары көрсөтүлөт - UTXO топтому. Бул өзгөчө интуитивдик өкүлчүлүк болбосо да, ар бир "капчыкта" өзүнчө жазуу катары "баланс" бар өкүлчүлүккө караганда ишке ашыруунун натыйжалуулугу жагынан пайдалуу, ошондой эле купуялуулукту кошот (мис. ).
Транзакциялардын тарыхын (блокчейн деп аталган) жана системанын учурдагы абалын айырмалоо маанилүү. Bitcoin транзакция тарыхы учурда диск мейкиндигинде болжол менен 200 ГБ ээлейт жана өсүүнү улантууда. Бирок, системанын абалы 4 ГБ тартиби боюнча, алда канча азыраак жана кимдир бирөө учурда тыйынга ээ экендигин эске алат. Бул маалыматтардын көлөмү да убакыттын өтүшү менен көбөйөт, бирок бир кыйла жайыраак ылдамдыкта, ал тургай кээде төмөндөө тенденциясына ээ ( CDPV караңыз ).
Жеңил кардарлар (SPV) жеке ачкычтардан башка эч кандай минималдуу абалды (UTXO топтомун) сактоо мүмкүнчүлүгү үчүн коопсуздук кепилдиктерин соодалашат.
UTXO жана UTXO топтому
UTXO (Uspent Transaction Output) – транзакцияларда которулган ар бир Сатошинин саякатынын акыркы чекити, сарпталбаган транзакциянын натыйжасы. Сарпталбаган жыйынтыктар жаңы транзакциялардын киришине айланат жана ошентип сарпталат (сарпталат) жана UTXO топтомунан алынып салынат.
Жаңы UTXO ар дайым транзакциялар аркылуу түзүлөт:
- салымсыз coinbase транзакциялары: кенчилер монеталарды чыгарганда жаңы UTXO түзүңүз
- үзгүлтүксүз транзакциялар: учурдагы UTXOлордун белгилүү бир топтомун сарптоо менен жаңы UTXO түзүңүз
UTXO менен иштөө процесси:
Капчыктар сарптоо үчүн жеткиликтүү болгон монеталардын санын (баланс) бул капчыкта сарптоо үчүн жеткиликтүү UTXO суммасына жараша эсептейт.
Ар бир валидатордук түйүн, эки жолу сарптоо аракеттерин болтурбоо үчүн, топтомду көзөмөлдөшү керек всех Текшерүүдө UTXO ар бир бүтүмдөр ар биринин блок.
Түйүн логикага ээ болушу керек:
- UTXO топтомуна толуктоолор
- UTXO топтомунан өчүрүүлөр
- Бир топтомдо бир UTXO бар экендигин текшерүү
Элементтерди кошуу жана алып салуу, топтомдо элементтин бар экендигин текшерүү жана далилдөө мүмкүнчүлүгүн сактоо менен, топтом жөнүндө сакталган маалыматка талаптарды азайтуунун жолдору бар. .
UTXO үчүн батареялар
бир нече UTXO сактоо үчүн батареяларды колдонуу идеясы .
UTXO-топтом алгачкы блокту жүктөө (IBD) учурунда түз курулуп, толук жана биротоло сакталат, ал эми анын мазмуну тармактын ар бир жаңы жана туура блогунан транзакцияларды иштетүүдөн кийин өзгөрөт. Бул процесс болжол менен 200 ГБ блоктук маалыматтарды жүктөп алууну жана жүз миллиондогон санариптик кол тамгаларды текшерүүнү талап кылат. IBD процесси аяктагандан кийин, UTXO топтому болжол менен 4 ГБ ээлейт.
Бирок, аккумуляторлор менен, каражаттар үчүн консенсус эрежелери криптографиялык далилдерди текшерүүгө жана генерациялоого кыскарат, ал эми колдо болгон каражаттарды көзөмөлдөө жүгү ошол каражаттардын ээсине жүктөлөт, ал алардын бар экендигин жана ээлик кылуусун далилдейт.
Аккумуляторду топтомдун компакттуу көрүнүшү деп атоого болот. Сакталган өкүлчүлүктүн өлчөмү же туруктуу болушу керек , же топтомдун кардиналдуулугуна жана элементтин өзүнүн өлчөмүнө карата субсызыктуу түрдө көбөйөт, мисалы , мында n - сакталган топтомдун кардиналдуулугу.
Мында аккумулятор элементтин топтомго киргизилгендигинин далилин (кошуунун далили) генерациялоого мүмкүндүк берүүгө жана бул далилди натыйжалуу текшерүүгө мүмкүндүк берүүгө тийиш.
Батарея деп аталат динамикалык if сизге элементтерди кошууга жана топтомдон элементтерди алып салууга мүмкүндүк берет.
Мындай батарейканын мисалы болот . Мындай аккумулятор сакталган өкүлчүлүктүн туруктуу өлчөмү бар, бирок катышуусун талап кылат сыр бөлүштү (ишенимдүү орнотуу). Бул талап мындай аккумулятордун Биткойн сыяктуу ишенимсиз тармактар үчүн колдонулушун жокко чыгарат, анткени жашыруун генерация учурунда маалыматтардын агып чыгышы чабуулчуларга UTXO бар экендигинин жалган далилин түзүүгө мүмкүндүк берет, мындай аккумулятордун негизинде UTXO топтому менен түйүндөрдү алдоо.
Utreexo
Thaddeus Dryja тарабынан сунушталган Utreexo дизайны түзүүгө мүмкүндүк берет динамикалык батарея жок ишенимдүү орнотуу.
Utreexo кемчиликсиз бинардык токой болуп саналат жана берилген идеяларды иштеп чыгуу болуп саналат , топтомдон элементтерди алып салуу мүмкүнчүлүгүн кошуу.
Батареянын логикалык структурасы
Батарея клеткалары идеалдуу экилик дарактардан турган токойго жайгаштырылган. Бак-дарактар бийиктигине жараша иреттелген. Бул өкүлчүлүк эң визуалдуу катары тандалган жана батарейка менен иштөө учурунда бактардын биригүүсүн элестетүүгө мүмкүндүк берет.
Автор белгилегендей, токойдогу баардык дарактар идеалдуу болгондуктан, алардын бийиктиги экинин даражасы катары көрсөтүлөт, ошондой эле ар кандай натурал сан экинин даражасынын суммасы катары көрсөтүлөт. Демек, жалбырактардын ар кандай топтому бинардык дарактарга топтоштурса болот жана бардык учурларда, жаңы элементти кошуу билимди талап кылат. сакталган дарактардын тамыр түйүндөрү жөнүндө гана.
Ошентип, Utreexo аккумуляторунун сакталган өкүлчүлүгү тамыр түйүндөрүнүн тизмеси (Merkle root), жана дарактардын бүтүндөй токой эмес.
катары тамыр элементтердин тизмесин көрсөтөлү Vec<Option<Hash>>. Кошумча түрү Option<Hash> тамыр элементи жок болушу мүмкүн экенин көрсөтүп турат, бул аккумулятордо тиешелүү бийиктиктеги дарак жок дегенди билдирет.
/// 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],
}
}
}Элементтерди кошуу
Биринчиден, функцияны сүрөттөп берели parent(), бул эки берилген элемент үчүн ата-энелик түйүндү тааныйт.
parent() функциясы
Биз Merkle дарактарын колдонуп жаткандыктан, эки түйүндүн ар биринин ата-энеси бала түйүндөрдүн хэштеринин конкатенациясынын хэштерин сактаган бир түйүн болуп саналат:
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[..])
}Автор белгилегендей, Чарльз Бульяге, Пьер-Ален Фуке, Ади Шамир жана Себастьян Циммер тарабынан сүрөттөлгөн чабуулдардын алдын алуу үчүн
, эки хэштен тышкары, дарактын ичиндеги бийиктикти да бириктирүүгө кошуу керек.
Аккумуляторго элементтерди кошкондо, кайсы тамыр элементтери өзгөртүлгөнүнө көз салып туруу керек. Ар бир кошулган элемент үчүн тамыр элементтерин өзгөртүү жолу менен, сиз кийинчерээк бул элементтердин бар экендигинин далилин түзө аласыз.
Өзгөртүүлөрдү кошуп жатканыңызга көз салыңыз
Киргизилген өзгөртүүлөргө көз салуу үчүн структураны жарыялайлы Update, ал түйүндөрдүн өзгөрүүлөрү жөнүндө маалыматтарды сактайт.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Батареяга элемент кошуу үчүн, сизге керек:
- Тамыр элементтеринин себеттеринин массивдерин түзүңүз
new_rootsжана ал жерге учурдагы тамыр элементтерин, ар бир чака үчүн бирден жайгаштырыңыз:
коду
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);
}- Кошула турган элементтерди кошуңуз (массив
insertions) биринчи арабагаnew_roots[0]:
коду
new_roots[0].extend_from_slice(insertions);- Биринчи себетке кошулган нерселерди калгандары менен бириктириңиз:
- Бирден ашык нерсеси бар бардык арабалар үчүн:
- Себеттин учунан эки элементти алып, алардын ата-энесин эсептеп, эки элементти тең алып салыңыз
- Эсептелген ата-энени кийинки арабага кошуңуз
- Бирден ашык нерсеси бар бардык арабалар үчүн:
коду
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 });
}
}- Тамыр элементтерин кутулардан келип чыккан аккумулятор массивине жылдырыңыз
коду
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]);
}
}Кошулган элементтер үчүн далил түзүү
Батареяга клетканын кошулгандыгынын далили (Proof) чынжырдан турган Меркле жолу болуп кызмат кылат ProofStep. Эгер жол эч жакка алып барбаса, анда далил туура эмес.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Элементти кошууда мурда алынган маалыматты колдонуу (структура Update), сиз элементтин батареяга кошулганын далилдей аласыз. Бул үчүн, биз киргизилген өзгөртүүлөр таблицасын карап чыгып, Merkle жолуна ар бир кадамды кошобуз, ал кийинчерээк далил катары кызмат кылат:
коду
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
}
}Далил түзүү процесси
Элементтин далилин текшерүү
Элементтин кошулуу далилин текшерүү Merkle жолун ээрчип, учурдагы тамыр элементине алып келмейинче төмөндөйт:
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
}
}Визуалдык түрдө:
А үчүн далилдерди текшерүү процесси
Элементтерди алып салуу
Батареядан уячаны алып салуу үчүн, клетканын бар экенине жарактуу далилдерди беришиңиз керек. Далилден алынган маалыматтарды колдонуу менен аккумулятордун жаңы түпкү элементтерин эсептөөгө болот, алар үчүн берилген далил мындан ары чындыкка жатпайт.
Алгоритм төмөнкүчө:
- Кошумча катары, биз бийиктиги себеттин индексинен экиге барабар болгон Merkle дарактарына туура келген бош себеттердин топтомун уюштурабыз.
- Биз себеттерге Merkle жолунун кадамдарынан элементтерди киргизебиз; себеттин индекси учурдагы кадамдын санына барабар
- Биз далилдөөчү жол алып баруучу тамыр элементин алып салабыз
- Кошуу сыяктуу эле, биз себеттердин элементтерин жуптарга бириктирип, биримдиктин натыйжасын кийинки себетке жылдыруу менен жаңы тамыр элементтерин эсептейбиз.
коду
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;
}
}"А" элементин алып салуу процесси:
Учурдагы тармакка интеграциялоо
Сунушталган аккумуляторду колдонуу менен түйүндөр UTXO топтомун өзгөртө алган учурда бардык UTXOларды сактоо үчүн МБны колдонуудан качышы мүмкүн. Бирок, далилдер менен иштөө маселеси келип чыгат.
UTXO аккумуляторун колдонгон валидатордук түйүндү чакыралы компакттуу (компакт-мамлекеттик түйүн) жана аккумулятору жок валидатор болуп саналат толук (толук түйүн). Түйүндөрдүн эки классынын болушу аларды бирдиктүү тармакка интеграциялоодо көйгөй жаратат, анткени компакттуу түйүндөр транзакцияларга сарпталган UTXOлордун бар экендигин далилдөөнү талап кылат, ал эми толук түйүндөр андай эмес. Эгерде бардык тармак түйүндөрү бир убакта жана макулдашылган түрдө Utreexo колдонууга өтпөсө, анда компакттуу түйүндөр артта калып, Bitcoin тармагында иштей албай калат.
Тармакка компакттуу түйүндөрдү интеграциялоо маселесин чечүү үчүн түйүндөрдүн кошумча классын киргизүү сунушталууда - көпүрө. Көпүрө түйүнү - бул Utreexo батареясын жана күйгүзүү далилин сактаган толук түйүн всех UTXO топтомунан UTXO. Көпүрөлөр жаңы хэштерди эсептеп, транзакциялардын жаңы блоктору келгенде аккумуляторду жана далилдерди жаңыртышат. Аккумуляторду жана далилдерди сактоо жана жаңыртуу мындай түйүндөргө кошумча эсептөө жүктөмүн салбайт. Көпүрөлөр диск мейкиндигин курмандыкка чалышат: нерселерди иретке келтирүү керек менен салыштырганда хэштер компакт түйүндөр үчүн хэштер, мында n - UTXO топтомунун күчү.
Тармак архитектурасы
Көпүрөлөр бар түйүндөрдүн программалык камсыздоосун өзгөртпөстөн, акырындык менен тармакка компакттуу түйүндөрдү кошууга мүмкүндүк берет. Толук түйүндөр мурункудай иштешип, транзакцияларды жана блокторду өз ара бөлүштүрүшөт. Көпүрө түйүндөрү - бул Utreexo батарейкасынын маалыматтарын жана кошуу далилдердин топтомун кошумча сактаган толук түйүндөр. всех Азырынча UTXO. Көпүрө түйүнү өзүн бардык толук түйүндөр үчүн толук түйүн жана бардык компакттуу түйүндөр үчүн компакт түйүн катары көрсөтүп, өзүн жарнамалабайт. Көпүрөлөр эки тармакты тең бириктирсе да, аларды бир гана багытта туташтыруу керек: учурдагы толук түйүндөрдөн компакт түйүндөргө чейин. Бул мүмкүн, анткени транзакциянын форматын өзгөртүүнүн кереги жок жана компакт түйүндөр үчүн UTXO далилдери жокко чыгарылат, ошондуктан ар кандай компакт түйүн көпүрө түйүндөрүнүн катышуусуз эле транзакцияларды тармактын бардык катышуучуларына уктурууга болот.
жыйынтыктоо
Биз Utreexo батарейкасын карап, анын прототибин Rustто ишке ашырдык. Батареяга негизделген түйүндөрдү интеграциялоого мүмкүндүк берүүчү тармак архитектурасын карадык. Компакттык кармоолордун артыкчылыгы сакталган маалыматтардын өлчөмү болуп саналат, ал логарифмдик түрдө UTXO топтомунун кубаттуулугуна көз каранды, бул диск мейкиндигине жана мындай түйүндөр үчүн сактоонун иштөөсүнө талаптарды бир топ азайтат. Кемчилиги далилдерди берүү үчүн кошумча түйүн трафиги, бирок далилдерди топтоо ыкмалары (бир далил бир нече элементтердин бар экенин далилдегенде) жана кэштөө трафикти алгылыктуу чектерде кармоого жардам берет.
шилтемелер:
- -
Source: www.habr.com