Utreexo: നിരവധി UTXO ബിറ്റ്കോയിൻ കംപ്രസ് ചെയ്യുന്നു

ഹേ ഹബർ!

ബിറ്റ്‌കോയിൻ നെറ്റ്‌വർക്കിൽ, എല്ലാ നോഡുകളും, സമവായത്തിലൂടെ, ഒരു കൂട്ടം UTXO-കൾ അംഗീകരിക്കുന്നു: ചെലവഴിക്കുന്നതിന് എത്ര നാണയങ്ങൾ ലഭ്യമാണ്, ആർക്ക്, ഏത് വ്യവസ്ഥകളിൽ. ഒരു വാലിഡേറ്റർ നോഡിന് ആവശ്യമായ ഏറ്റവും കുറഞ്ഞ ഡാറ്റയാണ് UTXO സെറ്റ്, ഇത് കൂടാതെ ഇൻകമിംഗ് ഇടപാടുകളുടെയും അവ അടങ്ങിയ ബ്ലോക്കുകളുടെയും സാധുത പരിശോധിക്കാൻ നോഡിന് കഴിയില്ല.

ഇക്കാര്യത്തിൽ, ഈ സെറ്റിന്റെ സംഭരിച്ച പ്രാതിനിധ്യം കുറയ്ക്കുന്നതിനും സുരക്ഷാ ഗ്യാരന്റി നഷ്ടപ്പെടാതെ കംപ്രസ് ചെയ്യുന്നതിനും സാധ്യമായ എല്ലാ വഴികളിലും ശ്രമങ്ങൾ നടക്കുന്നു. സംഭരിച്ച ഡാറ്റയുടെ അളവ് കുറയുമ്പോൾ, വാലിഡേറ്റർ നോഡിന്റെ ഡിസ്ക് സ്പേസ് ആവശ്യകതകൾ കുറയുന്നു, ഇത് ഒരു വാലിഡേറ്റർ നോഡ് ലോഞ്ച് ചെയ്യുന്നത് വിലകുറഞ്ഞതാക്കുന്നു, ഇത് നെറ്റ്‌വർക്ക് വികസിപ്പിക്കാനും അതുവഴി നെറ്റ്‌വർക്കിന്റെ സ്ഥിരത വർദ്ധിപ്പിക്കാനും നിങ്ങളെ അനുവദിക്കുന്നു.

ഈ പോസ്റ്റിൽ ഒരു സഹ-രചയിതാവിൽ നിന്നുള്ള സമീപകാല നിർദ്ദേശത്തിന്റെ ഒരു റസ്റ്റ് പ്രോട്ടോടൈപ്പ് ഞങ്ങൾ പോസ്റ്റ് ചെയ്യും മിന്നൽ നെറ്റ്‌വർക്ക് പേപ്പർ, തദ്ദ്യൂസ് ഡ്രൈജ - Utreexo: ബിറ്റ്‌കോയിൻ UTXO സെറ്റിനായി ഒപ്റ്റിമൈസ് ചെയ്‌ത ഡൈനാമിക് ഹാഷ് അധിഷ്‌ഠിത അക്യുമുലേറ്റർ, ഇത് വാലിഡേറ്റർ നോഡുകൾക്കുള്ള ഡിസ്ക് സ്പേസ് ആവശ്യകതകൾ കുറയ്ക്കാൻ അനുവദിക്കുന്നു.

എന്തെങ്കിലും പ്രശ്നം?

ബിറ്റ്‌കോയിന്റെ വറ്റാത്ത പ്രശ്‌നങ്ങളിലൊന്ന് അതിന്റെ സ്കേലബിളിറ്റിയാണ്. "നിങ്ങളുടെ സ്വന്തം ബാങ്ക്" എന്ന ആശയത്തിന് നെറ്റ്‌വർക്ക് പങ്കാളികൾ ഉപയോഗത്തിന് ലഭ്യമായ എല്ലാ ഫണ്ടുകളുടെയും രേഖകൾ സൂക്ഷിക്കേണ്ടതുണ്ട്. ബിറ്റ്കോയിനിൽ, ലഭ്യമായ ഫണ്ടുകൾ ചിലവഴിക്കാത്ത ഔട്ട്പുട്ടുകളുടെ ഒരു കൂട്ടമായി പ്രകടിപ്പിക്കുന്നു - ഒരു UTXO-സെറ്റ്. ഇത് പ്രത്യേകിച്ച് അവബോധജന്യമായ ഒരു പ്രാതിനിധ്യമല്ലെങ്കിലും, ഓരോ "വാലറ്റിനും" ഒരു പ്രത്യേക എൻട്രിയായി "ബാലൻസ്" ഉള്ള ഒരു പ്രാതിനിധ്യത്തിന് മേലുള്ള നിർവ്വഹണ പ്രകടനത്തിന്റെ കാര്യത്തിൽ ഇത് പ്രയോജനകരമാണ്, കൂടാതെ സ്വകാര്യത ചേർക്കുകയും ചെയ്യുന്നു (ഉദാ. കോയിൻജോയിൻ).

ഇടപാടുകളുടെ ചരിത്രവും (ബ്ലോക്ക്ചെയിൻ എന്ന് വിളിക്കപ്പെടുന്നവ) സിസ്റ്റത്തിന്റെ നിലവിലെ അവസ്ഥയും തമ്മിൽ വേർതിരിച്ചറിയേണ്ടത് പ്രധാനമാണ്. ബിറ്റ്കോയിൻ ഇടപാട് ചരിത്രം നിലവിൽ ഏകദേശം 200 GB ഡിസ്ക് സ്പേസ് എടുക്കുന്നു, അത് വളരുകയും ചെയ്യുന്നു. എന്നിരുന്നാലും, 4 GB എന്ന ക്രമത്തിൽ, സിസ്റ്റത്തിന്റെ അവസ്ഥ വളരെ ചെറുതാണ്, നിലവിൽ ആരെങ്കിലും നാണയങ്ങൾ കൈവശം വച്ചിരിക്കുന്നു എന്ന വസ്തുത മാത്രം കണക്കിലെടുക്കുന്നു. ഈ ഡാറ്റയുടെ അളവും കാലക്രമേണ വർദ്ധിക്കുന്നു, പക്ഷേ വളരെ സാവധാനത്തിൽ, ചിലപ്പോൾ കുറയുന്നു (സിഡിപിവി കാണുക).

സ്വകാര്യ കീകൾ ഒഴികെയുള്ള മിനിമം അവസ്ഥ (UTXO-സെറ്റ്) സംഭരിക്കാനുള്ള കഴിവിന് ലൈറ്റ് ക്ലയന്റുകൾ (SPV) വ്യാപാര സുരക്ഷ ഉറപ്പുനൽകുന്നു.

UTXO, UTXO-സെറ്റ്

UTXO (അൺസ്പെന്റ് ട്രാൻസാക്ഷൻ ഔട്ട്പുട്ട്) എന്നത് ചെലവാക്കാത്ത ഇടപാട് ഔട്ട്പുട്ടാണ്, ഇടപാടുകളിൽ കൈമാറ്റം ചെയ്യപ്പെടുന്ന ഓരോ സതോഷിയുടെയും യാത്രയുടെ അവസാന പോയിന്റ്. ചെലവഴിക്കാത്ത ഔട്ട്‌പുട്ടുകൾ പുതിയ ഇടപാടുകളുടെ ഇൻപുട്ടുകളായി മാറുകയും അങ്ങനെ ചെലവഴിക്കുകയും (ചെലവഴിക്കുകയും) UTXO-സെറ്റിൽ നിന്ന് നീക്കം ചെയ്യുകയും ചെയ്യുന്നു.

പുതിയ UTXO-കൾ എപ്പോഴും ഇടപാടുകൾ വഴി സൃഷ്ടിക്കപ്പെടുന്നു:

• ഇൻപുട്ടുകളില്ലാത്ത കോയിൻബേസ് ഇടപാടുകൾ: ഖനിത്തൊഴിലാളികൾ നാണയങ്ങൾ നൽകുമ്പോൾ പുതിയ UTXO-കൾ സൃഷ്ടിക്കുക
• പതിവ് ഇടപാടുകൾ: നിലവിലുള്ള UTXO-കളുടെ ഒരു നിശ്ചിത സെറ്റ് ചെലവഴിക്കുമ്പോൾ പുതിയ UTXO-കൾ സൃഷ്ടിക്കുക

UTXO-യുമായി പ്രവർത്തിക്കുന്നതിനുള്ള പ്രക്രിയ:

ഈ വാലറ്റിന് ചെലവാക്കുന്നതിന് ലഭ്യമായ UTXO തുകയെ അടിസ്ഥാനമാക്കി, ചിലവഴിക്കാൻ ലഭ്യമായ നാണയങ്ങളുടെ എണ്ണം (ബാലൻസ്) വാലറ്റുകൾ കണക്കാക്കുന്നു.

ഇരട്ട ചെലവ് ശ്രമങ്ങൾ തടയാൻ ഓരോ വാലിഡേറ്റർ നോഡും സെറ്റ് നിരീക്ഷിക്കണം всех പരിശോധിക്കുമ്പോൾ UTXO ഓരോന്നും ഇടപാടുകൾ ഓരോന്നും തടയുക.

നോഡിന് ലോജിക് ഉണ്ടായിരിക്കണം:

• UTXO-സെറ്റിലേക്കുള്ള കൂട്ടിച്ചേർക്കലുകൾ
• UTXO-സെറ്റിൽ നിന്നുള്ള ഇല്ലാതാക്കലുകൾ
• ഒരു സെറ്റിൽ ഒരൊറ്റ UTXO യുടെ സാന്നിധ്യം പരിശോധിക്കുന്നു

ഘടകങ്ങൾ ചേർക്കുന്നതിനും നീക്കം ചെയ്യുന്നതിനുമുള്ള കഴിവ് നിലനിർത്തിക്കൊണ്ടുതന്നെ, ഒരു സെറ്റിലെ ഒരു മൂലകത്തിന്റെ അസ്തിത്വം പരിശോധിക്കുകയും തെളിയിക്കുകയും ചെയ്യുന്നതിലൂടെ ഒരു സെറ്റിനെ കുറിച്ചുള്ള സംഭരിച്ചിരിക്കുന്ന വിവരങ്ങളുടെ ആവശ്യകതകൾ കുറയ്ക്കുന്നതിനുള്ള വഴികളുണ്ട്. ക്രിപ്റ്റോഗ്രാഫിക് അക്യുമുലേറ്ററുകൾ.

UTXO-നുള്ള ബാറ്ററികൾ

ഒന്നിലധികം UTXO-കൾ സംഭരിക്കുന്നതിന് ബാറ്ററികൾ ഉപയോഗിക്കുന്ന ആശയം ചർച്ച ചെയ്തു നേരത്തെ.

പ്രാരംഭ ബ്ലോക്ക് ഡൗൺലോഡ് (IBD) സമയത്ത് UTXO-സെറ്റ് ഈച്ചയിൽ നിർമ്മിച്ചതാണ്, പൂർണ്ണമായും ശാശ്വതമായും സംഭരിച്ചിരിക്കുന്നു, അതേസമയം നെറ്റ്‌വർക്കിന്റെ പുതിയതും ശരിയായതുമായ ഓരോ ബ്ലോക്കിൽ നിന്നുമുള്ള ഇടപാടുകൾ പ്രോസസ്സ് ചെയ്തതിന് ശേഷം അതിന്റെ ഉള്ളടക്കങ്ങൾ മാറും. ഈ പ്രക്രിയയ്ക്ക് ഏകദേശം 200 GB ബ്ലോക്ക് ഡാറ്റ ഡൗൺലോഡ് ചെയ്യേണ്ടതുണ്ട്, കൂടാതെ ദശലക്ഷക്കണക്കിന് ഡിജിറ്റൽ സിഗ്നേച്ചറുകൾ പരിശോധിക്കേണ്ടതുണ്ട്. IBD പ്രോസസ്സ് പൂർത്തിയായ ശേഷം, UTXO-സെറ്റ് ഏകദേശം 4 GB ഉൾക്കൊള്ളും എന്നതാണ് ഏറ്റവും പ്രധാന കാര്യം.

എന്നിരുന്നാലും, അക്യുമുലേറ്ററുകൾക്കൊപ്പം, ഫണ്ടുകൾക്കായുള്ള സമവായത്തിന്റെ നിയമങ്ങൾ ക്രിപ്‌റ്റോഗ്രാഫിക് തെളിവുകളുടെ പരിശോധനയ്ക്കും ജനറേഷനും ആയി ചുരുക്കി, ലഭ്യമായ ഫണ്ടുകൾ ട്രാക്ക് ചെയ്യുന്നതിനുള്ള ഭാരം ആ ഫണ്ടുകളുടെ ഉടമസ്ഥനിലേക്ക് മാറ്റുന്നു, അവർ അവരുടെ നിലനിൽപ്പിന്റെയും ഉടമസ്ഥതയുടെയും തെളിവ് നൽകുന്നു.

ഒരു അക്യുമുലേറ്ററിനെ ഒരു സെറ്റിന്റെ കോം‌പാക്റ്റ് പ്രാതിനിധ്യം എന്ന് വിളിക്കാം. സംഭരിച്ച പ്രാതിനിധ്യത്തിന്റെ വലുപ്പം ഒന്നുകിൽ സ്ഥിരമായിരിക്കണം , അല്ലെങ്കിൽ സെറ്റിന്റെ കാർഡിനാലിറ്റിയും മൂലകത്തിന്റെ വലിപ്പവും സംബന്ധിച്ച് ഉപരേഖയായി വർദ്ധിപ്പിക്കുക, ഉദാഹരണത്തിന് , ഇവിടെ n എന്നത് സംഭരിച്ചിരിക്കുന്ന സെറ്റിന്റെ കാർഡിനാലിറ്റിയാണ്.

ഈ സാഹചര്യത്തിൽ, സെറ്റിൽ (ഉൾപ്പെടുത്തൽ തെളിവ്) ഒരു ഘടകം ഉൾപ്പെടുത്തിയതിന്റെ തെളിവ് സൃഷ്ടിക്കാൻ അക്യുമുലേറ്റർ അനുവദിക്കുകയും ഈ തെളിവ് ഫലപ്രദമായി പരിശോധിക്കുന്നത് സാധ്യമാക്കുകയും വേണം.

ബാറ്ററി എന്ന് വിളിക്കുന്നു ചലനാത്മക ഒരു സെറ്റിൽ നിന്ന് ഘടകങ്ങൾ ചേർക്കാനും നീക്കം ചെയ്യാനും നിങ്ങളെ അനുവദിക്കുകയാണെങ്കിൽ.

അത്തരമൊരു ബാറ്ററിയുടെ ഉദാഹരണം ഇതായിരിക്കും 2018 ഡിസംബറിൽ Boneh, Bunz, Fisch എന്നിവർ നിർദ്ദേശിച്ച RSA അക്യുമുലേറ്റർ. അത്തരമൊരു അക്യുമുലേറ്ററിന് സംഭരിച്ച പ്രാതിനിധ്യത്തിന്റെ സ്ഥിരമായ വലുപ്പമുണ്ട്, പക്ഷേ സാന്നിധ്യം ആവശ്യമാണ് രഹസ്യം പങ്കിട്ടു (വിശ്വസനീയമായ സജ്ജീകരണം). ഈ ആവശ്യകത ബിറ്റ്‌കോയിൻ പോലുള്ള വിശ്വസനീയമല്ലാത്ത നെറ്റ്‌വർക്കുകൾക്ക് അത്തരം ഒരു അക്യുമുലേറ്ററിന്റെ പ്രയോഗത്തെ നിരാകരിക്കുന്നു, കാരണം രഹസ്യ ജനറേഷൻ സമയത്ത് ഡാറ്റ ചോർച്ച ഒരു UTXO-യുടെ അസ്തിത്വത്തിന് തെറ്റായ തെളിവ് സൃഷ്ടിക്കാൻ ആക്രമണകാരികളെ അനുവദിക്കും, അത്തരം ഒരു അക്യുമുലേറ്ററിനെ അടിസ്ഥാനമാക്കിയുള്ള UTXO-സെറ്റ് ഉള്ള നോഡുകളെ കബളിപ്പിക്കുന്നു.

യുട്രെക്സോ

തദ്ദിയസ് ഡ്രൈജ നിർദ്ദേശിച്ച Utreexo ഡിസൈൻ സൃഷ്ടിക്കുന്നത് സാധ്യമാക്കുന്നു ചലനാത്മകമാണ് аккумулятор ഇല്ലാതെ വിശ്വസനീയമായ സജ്ജീകരണം.

തികഞ്ഞ ബൈനറിയുടെ ഒരു വനമാണ് Utreexo മെർക്കൽ മരങ്ങൾ അവതരിപ്പിച്ച ആശയങ്ങളുടെ വികാസമാണ് വിതരണം ചെയ്ത pki-യ്‌ക്കുള്ള കാര്യക്ഷമമായ അസിൻക്രണസ് അക്യുമുലേറ്ററുകൾ, ഒരു സെറ്റിൽ നിന്ന് ഘടകങ്ങൾ നീക്കം ചെയ്യാനുള്ള കഴിവ് ചേർക്കുന്നു.

ബാറ്ററി ലോജിക്കൽ ഘടന

അനുയോജ്യമായ ബൈനറി മരങ്ങളുടെ വനത്തിലാണ് ബാറ്ററി സെല്ലുകൾ ക്രമീകരിച്ചിരിക്കുന്നത്. മരങ്ങൾ ഉയരം അനുസരിച്ച് ക്രമീകരിച്ചിരിക്കുന്നു. ഈ പ്രാതിനിധ്യം ഏറ്റവും വിഷ്വൽ ആയി തിരഞ്ഞെടുത്തു, ബാറ്ററിയിലെ പ്രവർത്തന സമയത്ത് മരങ്ങളുടെ ലയനം ദൃശ്യവൽക്കരിക്കാൻ നിങ്ങളെ അനുവദിക്കുന്നു.

വനത്തിലെ എല്ലാ മരങ്ങളും അനുയോജ്യമായതിനാൽ, ഏത് സ്വാഭാവിക സംഖ്യയെയും രണ്ടിന്റെ ശക്തികളുടെ ആകെത്തുകയായി പ്രതിനിധീകരിക്കുന്നത് പോലെ, അവയുടെ ഉയരം രണ്ടിന്റെ ശക്തിയായി പ്രകടിപ്പിക്കപ്പെടുന്നുവെന്ന് ഗ്രന്ഥകാരൻ രേഖപ്പെടുത്തുന്നു. അതനുസരിച്ച്, ഏത് കൂട്ടം ഇലകളെയും ബൈനറി മരങ്ങളായി തരംതിരിക്കാം, എല്ലാ സാഹചര്യങ്ങളിലും, ഒരു പുതിയ ഘടകം ചേർക്കുന്നതിന് അറിവ് ആവശ്യമാണ്. സംഭരിച്ചിരിക്കുന്ന മരങ്ങളുടെ റൂട്ട് നോഡുകളെ കുറിച്ച് മാത്രം.

അങ്ങനെ, 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(), നൽകിയിരിക്കുന്ന രണ്ട് മൂലകങ്ങളുടെ പേരന്റ് നോഡ് തിരിച്ചറിയുന്നു.

പാരന്റ്() പ്രവർത്തനം

ഞങ്ങൾ മെർക്കൽ ട്രീകൾ ഉപയോഗിക്കുന്നതിനാൽ, ചൈൽഡ് നോഡുകളുടെ ഹാഷുകളുടെ സംയോജനത്തിന്റെ ഹാഷ് സംഭരിക്കുന്ന ഒരു നോഡാണ് രണ്ട് നോഡുകളുടെയും പാരന്റ്:

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

• ആദ്യ കൊട്ടയിൽ ചേർത്ത ഇനങ്ങൾ ബാക്കിയുള്ളവയുമായി സംയോജിപ്പിക്കുക:
  • ഒന്നിലധികം ഇനങ്ങളുള്ള എല്ലാ വണ്ടികൾക്കും:
    1. കൊട്ടയുടെ അറ്റത്ത് നിന്ന് രണ്ട് ഘടകങ്ങൾ എടുക്കുക, അവയുടെ പാരന്റ് കണക്കാക്കുക, രണ്ട് ഘടകങ്ങളും നീക്കം ചെയ്യുക
    2. കണക്കാക്കിയ രക്ഷിതാവിനെ അടുത്ത കാർട്ടിലേക്ക് ചേർക്കുക

കോഡ്

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), ബാറ്ററിയിൽ ഒരു ഘടകം ചേർത്തിട്ടുണ്ടെന്ന് നിങ്ങൾക്ക് തെളിവ് സൃഷ്ടിക്കാൻ കഴിയും. ഇത് ചെയ്യുന്നതിന്, ഞങ്ങൾ വരുത്തിയ മാറ്റങ്ങളുടെ പട്ടികയിലൂടെ കടന്നുപോകുകയും മെർക്കലിന്റെ പാതയിലേക്ക് ഓരോ ഘട്ടവും ചേർക്കുകയും ചെയ്യുന്നു, അത് പിന്നീട് തെളിവായി വർത്തിക്കും:

കോഡ്

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

ഒരു തെളിവ് സൃഷ്ടിക്കുന്ന പ്രക്രിയ

ഒരു ഘടകത്തിനായുള്ള തെളിവ് പരിശോധിക്കുന്നു

ഒരു മൂലകത്തിന്റെ ഇൻക്ലൂഷൻ പ്രൂഫ് പരിശോധിക്കുന്നത്, അത് നിലവിലുള്ള ഒരു റൂട്ട് എലമെന്റിലേക്ക് നയിക്കുന്നത് വരെ മെർക്കൽ പാത പിന്തുടരുന്നതിലേക്ക് ചുരുങ്ങുന്നു:

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

ദൃശ്യപരമായി:

എയുടെ തെളിവ് പരിശോധിക്കുന്ന പ്രക്രിയ

ഇനങ്ങൾ നീക്കംചെയ്യുന്നു

ബാറ്ററിയിൽ നിന്ന് ഒരു സെൽ നീക്കംചെയ്യുന്നതിന്, സെൽ അവിടെ ഉണ്ടെന്നതിന് നിങ്ങൾ സാധുവായ തെളിവ് നൽകണം. തെളിവിൽ നിന്നുള്ള ഡാറ്റ ഉപയോഗിച്ച്, അക്യുമുലേറ്ററിന്റെ പുതിയ റൂട്ട് ഘടകങ്ങൾ കണക്കാക്കാൻ കഴിയും, അതിനായി നൽകിയിരിക്കുന്ന തെളിവ് ഇനി ശരിയാകില്ല.

അൽഗോരിതം ഇപ്രകാരമാണ്:

1. കൂടാതെ, ബാസ്‌ക്കറ്റ് സൂചികയിൽ നിന്ന് രണ്ടിന്റെ ശക്തിക്ക് തുല്യമായ ഉയരമുള്ള മെർക്കൽ മരങ്ങൾക്ക് അനുയോജ്യമായ ഒരു കൂട്ടം ശൂന്യമായ കൊട്ടകൾ ഞങ്ങൾ സംഘടിപ്പിക്കുന്നു.
2. മെർക്കൽ പാതയുടെ പടികളിൽ നിന്ന് ഞങ്ങൾ ഘടകങ്ങൾ കൊട്ടകളിലേക്ക് തിരുകുന്നു; ബാസ്‌ക്കറ്റ് സൂചിക നിലവിലെ ഘട്ടത്തിന്റെ എണ്ണത്തിന് തുല്യമാണ്
3. തെളിവിൽ നിന്നുള്ള പാത നയിക്കുന്ന റൂട്ട് ഘടകം ഞങ്ങൾ നീക്കംചെയ്യുന്നു
4. ചേർക്കുന്നത് പോലെ, കൊട്ടകളിൽ നിന്നുള്ള ഘടകങ്ങൾ ജോഡികളായി സംയോജിപ്പിച്ച് അടുത്ത ബാസ്‌ക്കറ്റിലേക്ക് യൂണിയൻ ഫലം നീക്കി പുതിയ റൂട്ട് ഘടകങ്ങൾ ഞങ്ങൾ കണക്കാക്കുന്നു.

കോഡ്

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-കളും സംഭരിക്കുന്നതിന് ഒരു DB ഉപയോഗിക്കുന്നത് നോഡുകൾക്ക് ഒഴിവാക്കാനാകും. എന്നിരുന്നാലും, തെളിവുകൾക്കൊപ്പം പ്രവർത്തിക്കുന്നതിനുള്ള പ്രശ്നം ഉയർന്നുവരുന്നു.

UTXO അക്യുമുലേറ്റർ ഉപയോഗിക്കുന്ന വാലിഡേറ്റർ നോഡിനെ നമുക്ക് വിളിക്കാം ഒതുക്കമുള്ളത് (കോംപാക്റ്റ്-സ്റ്റേറ്റ് നോഡ്), കൂടാതെ ഒരു അക്യുമുലേറ്റർ ഇല്ലാത്ത വാലിഡേറ്റർ ആണ് പൂർണ്ണമായ (മുഴുവൻ നോഡ്). രണ്ട് തരം നോഡുകളുടെ അസ്തിത്വം അവയെ ഒരൊറ്റ നെറ്റ്‌വർക്കിലേക്ക് സംയോജിപ്പിക്കുന്നതിന് ഒരു പ്രശ്‌നം സൃഷ്ടിക്കുന്നു, കാരണം കോം‌പാക്റ്റ് നോഡുകൾക്ക് ഇടപാടുകളിൽ ചെലവഴിക്കുന്ന UTXO-കളുടെ അസ്തിത്വത്തിന്റെ തെളിവ് ആവശ്യമാണ്, അതേസമയം പൂർണ്ണ നോഡുകൾ അങ്ങനെയല്ല. എല്ലാ നെറ്റ്‌വർക്ക് നോഡുകളും ഒരേസമയം ഏകോപിപ്പിച്ച് Utreexo ഉപയോഗിക്കുന്നതിലേക്ക് മാറുന്നില്ലെങ്കിൽ, കോം‌പാക്റ്റ് നോഡുകൾ അവശേഷിക്കുകയും ബിറ്റ്‌കോയിൻ നെറ്റ്‌വർക്കിൽ പ്രവർത്തിക്കാൻ കഴിയാതെ വരികയും ചെയ്യും.

നെറ്റ്‌വർക്കിലേക്ക് കോം‌പാക്റ്റ് നോഡുകൾ സംയോജിപ്പിക്കുന്നതിനുള്ള പ്രശ്നം പരിഹരിക്കുന്നതിന്, ഒരു അധിക ക്ലാസ് നോഡുകൾ അവതരിപ്പിക്കാൻ നിർദ്ദേശിക്കുന്നു - പാലങ്ങൾ. Utreexo ബാറ്ററിയും പവർ-ഓൺ പ്രൂഫും സംഭരിക്കുന്ന ഒരു സമ്പൂർണ്ണ നോഡാണ് ബ്രിഡ്ജ് നോഡ് всех UTXO-സെറ്റിൽ നിന്ന് UTXO. ബ്രിഡ്ജുകൾ പുതിയ ഹാഷുകൾ കണക്കാക്കുകയും ഇടപാടുകളുടെ പുതിയ ബ്ലോക്കുകൾ വരുമ്പോൾ അക്യുമുലേറ്ററും പ്രൂഫുകളും അപ്‌ഡേറ്റ് ചെയ്യുകയും ചെയ്യുന്നു. അക്യുമുലേറ്ററും പ്രൂഫുകളും പരിപാലിക്കുന്നതും അപ്‌ഡേറ്റ് ചെയ്യുന്നതും അത്തരം നോഡുകളിൽ അധിക കമ്പ്യൂട്ടേഷണൽ ലോഡ് ചുമത്തുന്നില്ല. ബ്രിഡ്ജുകൾ ഡിസ്ക് സ്പേസ് ബലികഴിക്കുന്നു: കാര്യങ്ങൾ ക്രമീകരിക്കേണ്ടതുണ്ട് ഹാഷുകൾ, അപേക്ഷിച്ച് കോംപാക്റ്റ് നോഡുകൾക്കുള്ള ഹാഷുകൾ, ഇവിടെ n എന്നത് UTXO സെറ്റിന്റെ ശക്തിയാണ്.

നെറ്റ്‌വർക്ക് ആർക്കിടെക്ചർ

നിലവിലുള്ള നോഡുകളുടെ സോഫ്റ്റ്‌വെയർ മാറ്റാതെ നെറ്റ്‌വർക്കിലേക്ക് കോംപാക്റ്റ് നോഡുകൾ ക്രമേണ ചേർക്കുന്നത് ബ്രിഡ്ജുകൾ സാധ്യമാക്കുന്നു. പൂർണ്ണ നോഡുകൾ മുമ്പത്തെപ്പോലെ പ്രവർത്തിക്കുന്നു, ഇടപാടുകളും ബ്ലോക്കുകളും പരസ്പരം വിതരണം ചെയ്യുന്നു. Utreexo ബാറ്ററി ഡാറ്റയും ഒരു കൂട്ടം ഇൻക്ലൂഷൻ പ്രൂഫുകളും സംഭരിക്കുന്ന പൂർണ്ണ നോഡുകളാണ് ബ്രിഡ്ജ് നോഡുകൾ. всех ഇപ്പോൾ UTXO. ബ്രിഡ്ജ് നോഡ് സ്വയം പരസ്യപ്പെടുത്തുന്നില്ല, എല്ലാ പൂർണ്ണ നോഡുകൾക്കും ഒരു പൂർണ്ണ നോഡും എല്ലാ കോംപാക്റ്റ് നോഡുകൾക്കും ഒരു കോംപാക്റ്റ് നോഡും ആണെന്ന് നടിക്കുന്നു. ബ്രിഡ്ജുകൾ രണ്ട് നെറ്റ്‌വർക്കുകളേയും ഒരുമിച്ച് ബന്ധിപ്പിക്കുന്നുണ്ടെങ്കിലും, അവ യഥാർത്ഥത്തിൽ അവയെ ഒരു ദിശയിൽ മാത്രമേ ബന്ധിപ്പിക്കേണ്ടതുള്ളൂ: നിലവിലുള്ള പൂർണ്ണ നോഡുകളിൽ നിന്ന് കോംപാക്റ്റ് നോഡുകളിലേക്ക്. ഇടപാട് ഫോർമാറ്റ് മാറ്റേണ്ടതില്ലാത്തതിനാൽ ഇത് സാധ്യമാണ്, കൂടാതെ കോം‌പാക്റ്റ് നോഡുകൾക്കുള്ള UTXO പ്രൂഫുകൾ നിരസിക്കാൻ കഴിയും, അതിനാൽ ഏത് കോം‌പാക്റ്റ് നോഡിനും ബ്രിഡ്ജ് നോഡുകളുടെ പങ്കാളിത്തമില്ലാതെ എല്ലാ നെറ്റ്‌വർക്ക് പങ്കാളികളിലേക്കും ഇടപാടുകൾ പ്രക്ഷേപണം ചെയ്യാൻ കഴിയും.

തീരുമാനം

ഞങ്ങൾ Utreexo ബാറ്ററി നോക്കി അതിന്റെ പ്രോട്ടോടൈപ്പ് റസ്റ്റിൽ നടപ്പിലാക്കി. ബാറ്ററി അടിസ്ഥാനമാക്കിയുള്ള നോഡുകളുടെ സംയോജനം അനുവദിക്കുന്ന നെറ്റ്‌വർക്ക് ആർക്കിടെക്ചർ ഞങ്ങൾ പരിശോധിച്ചു. കോം‌പാക്റ്റ് ക്യാച്ചുകളുടെ പ്രയോജനം സംഭരിച്ച ഡാറ്റയുടെ വലുപ്പമാണ്, ഇത് UTXO-കളുടെ സെറ്റിന്റെ ശക്തിയെ ലോഗരിഥമിക് ആയി ആശ്രയിച്ചിരിക്കുന്നു, ഇത് അത്തരം നോഡുകൾക്കുള്ള ഡിസ്‌ക് സ്ഥലത്തിന്റെയും സംഭരണ ​​​​പ്രകടനത്തിന്റെയും ആവശ്യകതകളെ വളരെയധികം കുറയ്ക്കുന്നു. തെളിവുകൾ കൈമാറുന്നതിനുള്ള അധിക നോഡ് ട്രാഫിക്കാണ് പോരായ്മ, എന്നാൽ തെളിവുകളുടെ അഗ്രഗേഷൻ ടെക്നിക്കുകളും (ഒരു തെളിവ് നിരവധി ഘടകങ്ങളുടെ അസ്തിത്വം തെളിയിക്കുമ്പോൾ) കാഷിംഗും ട്രാഫിക്കിനെ സ്വീകാര്യമായ പരിധിക്കുള്ളിൽ നിലനിർത്താൻ സഹായിക്കും.

റെഫറൻസുകൾ:

• റസ്റ്റിലെ Utreexo പ്രോട്ടോടൈപ്പിന്റെ GitHub
• തദ്ദ്യൂസ് ഡ്രൈജ - Utreexo: ബിറ്റ്‌കോയിൻ UTXO സെറ്റിനായി ഒപ്റ്റിമൈസ് ചെയ്‌ത ഡൈനാമിക് ഹാഷ് അധിഷ്‌ഠിത അക്യുമുലേറ്റർ
• ലേഖനത്തിൽ നിന്നുള്ള ആനിമേറ്റഡ് ചിത്രീകരണങ്ങൾ

അവലംബം: www.habr.com