Karatasi hii, "Uthibitishaji Sambamba wa Kazi na Mipaka Thabiti," inashughulikia kikomo cha msingi katika makubaliano ya mnyororo wa vitalu: hali ya uwezekano na ya asimptotiki ya usalama katika mifumo ya kawaida ya Uthibitishaji wa Kazi (PoW) kama vile Bitcoin. Ingawa makubaliano ya Nakamoto yalibadilisha misingi ya imani isiyo ya kati, hoja zake za usalama kwa kiasi kikubwa zimekuwa za heuristiki au asimptotiki, na kumwacha mtumiaji bila uhakika kuhusu muda halisi wa kusubiri unaohitajika kwa uthibitishaji wa mwisho wa shughuli. Kutokuwa na uhakika huku kunatumika na vitisho kama vile matumizi mara mbili na uchimbaji wa kujipendelea.
Waandishi, Patrik Keller na Rainer Böhme, wanapendekeza mabadiliko ya dhana kutoka kwa PoW ya mtiririko (ambapo kila kizuizi kinarejelea kitendawili kimoja cha awali) hadi PoW ya sambamba. Familia yao ya itifaki hutumia $k$ vitendawili huru kwa kila kizuizi, na kuwezesha muundo wa chini-kwa-juu kutoka kwa itifaki ndogo thabiti ya makubaliano. Mchango mkuu ni upatikanaji wa mipaka thabiti, isiyo ya asimptotiki kwa uwezekano wa kufeli katika mitanduo ya adui yenye usawazishaji. Mfano ulioonyeshwa na $k=51$ vitendawili unafikia uwezekano wa kufeli wa $2.2 \cdot 10^{-4}$ kwa uthabiti baada ya kizuizi kimoja, uboreshaji mkubwa zaidi kuliko PoW ya mtiririko iliyoboreshwa.
Itifaki hii imejengwa kutoka kanuni za msingi, ikijengwa juu ya miundo iliyothibitishwa kutoka kwa fasihi ya PoW ya mtiririko lakini inatofautiana katika mitambo yake ya msingi.
Tofauti kuu ya usanifu inaonekana katika Mchoro 1 wa karatasi. PoW ya Mtiririko (Bitcoin) huunda mnyororo wa mstari ambapo hash ya kila kizuizi ndiyo suluhisho la kitendawili kimoja kinachorejelea kizuizi kilichotangulia. PoW ya Sambamba (Ilipendekezwa) huunda kizuizi kilicho na $k$ suluhisho huru za vitendawili. Muundo huu hutenganisha kiwango cha fursa za makubaliano na kiwango cha uundaji wa vizuizi.
Msingi ni itifaki ya makubaliano $A_k$ kwa hali ya hivi karibuni. Nodi zaaminifu hujaribu kutatua $k$ vitendawili huru kwa sambamba. Makubaliano juu ya hali mpya hufikiwa kulingana na kizingiti cha vitendawili vilivyotatuliwa ndani ya mtandao. Itifaki hii ndogo kisha hurudiwa ili kuunda itifaki kamili ya urejeshi wa hali, ikirithi mipaka thabiti ya makosa ya hatua ya makubaliano.
Uchambuzi unadhania mtandao wenye usawazishaji na ucheleweshaji mbaya zaidi unaojulikana wa uenezi wa ujumbe $\Delta$. Adui anadhibiti sehemu $\beta$ ya jumla ya nguvu ya hesabu. Muundo huu unazingatia adui anayeweza kupotoka kiholela kutoka kwa itifaki lakini anayozuiwa na sehemu yake ya hesabu na usawazishaji wa mtandao.
Mchango mkubwa wa karatasi hii uko katika kuhamia kutoka kwa dhamana za usalama za asimptotiki hadi za thabiti.
Waandishi wanatoa mipaka ya juu kwa uwezekano mbaya zaidi wa kufeli (k.m., ukiukaji wa uthabiti). Uwezekano kwamba mashambulizi anaweza kufanikiwa kugawanya mnyororo au kutumia mara mbili unaonyeshwa kama utendakazi wa vigezo muhimu: idadi ya vitendawili kwa kila kizuizi ($k$), nguvu ya jamaa ya adui ($\beta$), ucheleweshaji wa mtandao ($\Delta$), na kiwango cha kutatua vitendawili cha mtandao waaminifu ($\lambda$). Kikomo hiki kinachukua umbo linalokumbusha mipaka ya mkia katika nadharia ya uwezekano, ikitumia muundo wa sambamba kuimarisha dhamana kwa kiasi kikubwa ikilinganishwa na mnyororo wa mtiririko.
Karatasi hii inatoa mwongozo wa vitendo kwa kuchagua $k$ na muda wa kizuizi ili kupunguza uwezekano wa kufeli kwa seti fulani ya hali ya mtandao ($\Delta$, $\beta$). Hii inabadilisha muundo wa itifaki kutoka kwa zoezi la heuristiki hadi shida ya uboreshaji yenye malengo yanayoweza kupimika.
Lengo: Uthabiti baada ya kizuizi 1 (uthibitishaji wa haraka).
Vigezo: $k=51$, $\beta=0.25$ (adui 25%), $\Delta=2s$.
Matokeo: Uwezekano wa Kufeli $\leq 2.2 \times 10^{-4}$.
Fasiri: Adui angehitaji kujaribu maelfu ya vizuizi kwa mashambulizi moja ya mafanikio ya uthabiti.
Muundo uliopendekezwa ulitathminiwa kupitia uigaji uliokusudiwa kujaribu uthabiti. Uigaji huo ulikiuka kwa makusudi baadhi ya mawazo madhubuti ya muundo (k.m., usawazishaji kamili) ili kukadiria tabia ya itifaki katika hali za mtandao zenye ukweli zaidi, "zisizo safi". Matokeo yalionyesha kuwa itifaki ilibaki thabiti hata kwa ukiukaji wa sehemu, ikionyesha kuwa mipaka ya kinadharia ni ya tahadhari na muundo huo una ustahimilivu wa vitendo.
Ulinganisho mkuu ni dhidi ya usanidi ulioboreshwa wa "Bitcoin ya haraka" (PoW ya mtiririko na muda mfupi zaidi wa kizuizi) unaolenga latensi sawa. Kama ilivyotajwa kutoka kwa Li et al. (AFT '21), itifaki kama hiyo ya mtiririko ina uwezekano wa kufeli wa ~9% chini ya hali zinazofanana ($\beta=0.25$, $\Delta=2s$). Itifaki ya PoW ya sambamba inapunguza hii kwa zaidi ya mamlaka mbili hadi $2.2 \times 10^{-4}$, na kuonyesha uwezo wake bora wa kutoa uthibitishaji wa haraka na salama.
Mtazamo wa Mchambuzi wa Sekta
Keller na Böhme hawabadilishi tu Bitcoin; wanabuni upya msingi wa imani wa minyororo ya vitalu ya PoW. Ufahamu wa msingi ni kwamba ucheleweshaji wa usalama (muda wa kufikia uthibitishaji) hauhusiani kiasili na ucheleweshaji wa uzalishaji wa vizuizi. Kwa kufanya kazi sambamba ndani ya kizuizi, wanatenganisha vigezo hivi viwili. Huu ni ubunifu wa kina zaidi kuliko kuongeza tu ukubwa au mzunguko wa kizuizi, kwani unashambulia chanzo cha msingi cha uthibitishaji wa uwezekano. Ni sawa na kuhamia kutoka kwa kichakataji kimoja, cha polepole, chenye kuaminika sana hadi safu ya vichakataji vya haraka, visivyoaminika kidogo, na kutumia mifumo ya kura (itifaki ndogo ya makubaliano $A_k$) kufikia uaminifu wa juu na kasi—dhana inayojulikana katika mifumo ya kompyuta yenye ustahimilivu wa hitilafu kama RAID au makundi ya Uvumilivu wa Hitilafu ya Byzantine (BFT), lakini sasa inatumika kwa vitendawili vya kisiri.
Mantiki ya karatasi hii ni ya chini-kwa-juu na ya ulinzi-kwanza: 1) Tambua Kiungo Dhaifu: Usalama wa asimptotiki hautoshi kwa fedha za ulimwengu halisi (kutaja kazi ya mipaka thabiti ya Li et al. kama kichocheo). 2) Tenga Msingi: Zingatia itifaki ndogo ya makubaliano, sio mnyororo mzima. Hii ni busara—inapunguza utata. 3) Buni upya Msingi: Badilisha mbio za kitendawili kimoja na makubaliano ya kizingiti cha vitendawili vingi. 4) Kadiria Kila Kitu: Pata mipaka thabiti kwa msingi huu mpya. 5) Unganisha Usalama: Onyesha kuwa kurudia msingi salama kunatoa mnyororo salama. Mtiririko huu unafanana na uhandisi mkali wa usalama katika nyanja zingine, kama vile mbinu ya usalama unaothibitika katika kisiri cha kisasa (k.m., kazi ya Shoup na Bellare-Rogaway juu ya uthibitisho wa usalama).
Nguvu: Mipaka thabiti ni mabadiliko makubwa kwa kupitishwa kwa biashara. Wakuu wa Fedha sasa wanaweza kukagua usalama wa mnyororo wa vitalu kama mfano wa kifedha. Nambari za utendaji zinavutia—uwezekano wa kufeli wa $2.2 \times 10^{-4}$ dhidi ya 9% sio uboreshaji wa kidogo; ni darasa tofauti la hatari. Mwongozo wa vigezo hubadilisha muundo wa itifaki kutoka sanaa hadi sayansi.
Kasoro na Tahadhari: Dhana ya mtandao wenye usawazishaji ndiyo kisigino cha kifusi chake. Ingawa uigaji unaonyesha uthabiti kwa usawazishaji mdogo, mipaka ya hali mbaya zaidi inategemea $\Delta$ inayojulikana. Katika ulimwengu halisi, ucheleweshaji wa mtandao hubadilika na unaweza kubadilishwa (k.m., kupitia kuvamia BGP). Itifaki hii pia inaongeza utata wa mawasiliano kwa kila kizuizi kwa sababu ya $k$ (suluhisho za kutangaza). Kwa $k=51$, hii si ya kawaida. Mwishowe, ingawa inapunguza matumizi mara mbili kwa ustadi, uchambuzi unaonekana kuzingatia uthabiti; mashambulizi mengine kama vile kuzuia shughuli au uchimbaji wa kujipendelea katika muundo huu wa sambamba yanahitaji uchunguzi wa kina zaidi.
Kwa wasanifu wa minyororo ya vitalu: Karatasi hii inatoa mwongozo wa kujenga minyororo ya PoW yenye dhamana ya juu na uthibitishaji wa haraka kwa matumizi maalum (k.m., malipo ya taasisi, mali za michezo) ambapo hali ya mtandao inaweza kuzuiwa au kutolewa kwa wingi. Mfano wa $k=51$ ni hatua ya kuanzia, sio bora kwa ulimwengu wote.
Kwa wawekezaji na wachambuzi: Tazama mnyororo wowote wa "PoW ya kasi ya juu" unaodai uthibitishaji wa haraka kwa mashaka isipokuwa unatoa mipaka thabiti sawa. Kazi hii inaweka kiwango kipya cha madai ya usalama.
Kwa watafiti: Fursa kubwa zaidi ni kuchanganya mbinu hii. Je, tunaweza kuchanganya mipaka thabiti ya PoW ya sambamba na njia mbadala ya makubaliano ya polepole, salama kwa usawazishaji (kama PoW iliyofumwa ya Chainweb au makubaliano ya Snowman) ili kushughulikia kukatika kwa mtandao? Utafutaji wa uthibitishaji thabiti, unaoweza kupimika sasa ndio changamoto kuu.
Uchambuzi wa usalama unategemea kuiga mchakato wa kutatua vitendawili wa nodi zaaminifu na adui kama michakato ya Poisson. Acha $\lambda$ iwe kiwango cha jumla cha hash cha mtandao waaminifu, na $\beta\lambda$ iwe kiwango cha adui ($0 < \beta < 0.5$). Katika itifaki ya sambamba na $k$ vitendawili, kiwango cha mtandao waaminifu cha kutatua kitendawili chochote kilichopewa ni $\lambda/k$.
Kiini cha kikomo kinahusisha kuhesabu uwezekano kwamba adui anaweza kutatua kwa siri idadi ya kutosha ya vitendawili ili kuunda mnyororo unaoshindana ambao unapita ukuaji wa mnyororo waaminifu katika dirisha fulani la muda, ambalo ni utendakazi wa ucheleweshaji wa mtandao $\Delta$. Muundo wa sambamba unaruhusu matumizi ya mipaka ya aina ya Chernoff kwa usambazaji wa binomial/Poisson ili kuzuia kwa ukali uwezekano huu. Uwezekano wa kufeli $\epsilon$ kwa uthabiti baada ya kizuizi kimoja umefungwa na usemi wa umbo: $$\epsilon \leq f(k, \beta, \lambda\Delta)$$ ambapo $f$ ni utendakazi unaopungua kwa kasi ya kielelezo au zaidi ya kielelezo na $k$ kwa $\beta$ na $\lambda\Delta$ zilizowekwa, na kuelezea uboreshaji mkubwa zaidi kuliko PoW ya mtiririko.
Hali: Mnyororo wa vitalu wa ushirika wa benki kwa malipo ya kati ya benki unahitaji uthibitishaji wa shughuli ndani ya dakika 15 na uwezekano wa kushindwa kwa usalama chini ya $10^{-6}$ kwa kila malipo. Mtandao umepangwa vizuri na ucheleweshaji wa juu unaopimika $\Delta = 1.5$ sekunde. Washiriki wanakadiria kuwa adui anayewezekana anaweza kudhibiti hadi 30% ya nguvu ya hesabu ($\beta=0.3$).
Utumiaji wa Mfumo:
Matumizi ya Haraka: Itifaki hii inafaa kabisa kwa minyororo ya vitalu ya mazingira yaliyodhibitiwa ambapo usawazishaji wa mtandao ni dhana ya busara. Hii inajumuisha minyororo ya kibinafsi/ushirika kwa malipo ya kifedha, asili ya mnyororo wa usambazaji, na ufuatiliaji wa mali ya biashara. Uwezo wake wa kutoa uthibitishaji wa haraka, unaoweza kupimika ni faida kubwa kuliko PoW ya kawaida au hata baadhi ya mifumo ya Uthibitishaji wa Hisa inayoshambuliwa kwa muda mrefu.
Mwelekeo wa Utafiti wa Baadaye: