Utafiti huu unachunguza jinsi kituo katika mitandao ya njia za malipo kama Lightning Network kinavyoweza kuongeza jumla ya idadi ya miamala inayokubaliwa kwa kukubali au kukataa mapendekezo ya miamala yanapowasili, bila kujua ni miamala gani itakayokuja baadaye. Watafiti waliunda tatizo hili kama tatizo jipya la mkoba wa mtandaoni ambapo vipengele vyenye ukubwa chanya au hasi kulingana na mwelekeo wa muamala huwasili kwa mfuatano, na wakatengeneza algoriti ya uamuzi thabiti ya kukubali inayoitwa Exp. Imeonyeshwa kihisabati kwamba algoriti ya Exp ina uwiano wa ushindani wa O(log B) pale ukubwa wa miamala unapobaki ndani ya kikomo fulani cha juu; na kwamba kwa ujumla hakuna algoriti iliyobahatishwa inayoweza kuepuka kikomo cha chini cha Ω(log m).

Katika modeli, B inawakilisha kikomo kamili cha hali ya kituo, huku m ikiwakilisha ukubwa mkubwa zaidi wa muamala unaoweza kukubaliwa. Exp hukubali miamala ya mwelekeo kinyume ambayo husogeza salio la kituo kuelekea katikati, huku ikiweka kizingiti cha kiexponenti kinachozidi kuwa kikali kwa miamala inayoongeza zaidi salio katika mwelekeo wa kutokuwiana uliopo. Kwa njia hii, nafasi huachwa kwa miamala midogo na inayosawazisha, huku miamala mikubwa yenye hatari ya kumaliza ukwasi katika upande mmoja wa kituo ikikataliwa kwa kuchagua.

Katika uigaji uliotumia miamala sintetiki juu ya topolojia halisi ya Lightning Network, Exp ilikubali idadi ya miamala iliyo karibu na ile ya mbinu ya kawaida ya Greedy katika mtiririko wa miamala wa kila siku ulio wa nasibu na wenye uwiano. Katika hali ambapo miamala ilitiririka kwa kiasi kikubwa kwa mwelekeo mmoja kwenda kwa muuzaji mmoja na idadi ya vituo ilikuwa ndogo, Exp ilitoa idadi kubwa zaidi ya miamala iliyokubaliwa. Hata hivyo, utafiti hauchunguzi uboreshaji wa pamoja wa njia na ukwasi kwa mtandao mzima, bali uamuzi wa kukubali wa kila kituo kwa kiwango cha ndani; pia, badala ya historia halisi ya miamala, umetumia mitiririko ya miamala sintetiki iliyozalishwa juu ya topolojia halisi ya mtandao.

Swali kuu la utafiti ni lipi?

Mitandao ya njia za malipo huwezesha miamala kufanywa nje ya mnyororo kupitia njia zilizofadhiliwa mapema, badala ya kusubiri rekodi na uthibitisho mpya katika blockchain kwa kila muamala wa sarafu-fiche. Lightning Network na Raiden Network ni mifano inayojulikana ya mbinu hii.

Watumiaji wawili wanapofungua njia ya malipo, sehemu ya fedha yote huwa upande mmoja wa kituo na sehemu iliyobaki huwa upande mwingine. Malipo yanapofanywa kwa mwelekeo mmoja, ukwasi huhamia upande wa pili. Ikiwa salio la kutosha halibaki upande mmoja wa kituo, miamala mipya ya mwelekeo huo huo haiwezi kusafirishwa hata kama jumla ya fedha kwenye kituo inatosha.

Kwa sababu hiyo, kwa kituo kukubali kila muamala unaofaa si mara zote mkakati bora. Muamala mkubwa unaokubaliwa leo unaweza kusogeza salio la kituo hadi kwenye kikomo na kusababisha idadi kubwa ya miamala midogo inayokuja baadaye kukataliwa. Lakini katika hali ya mtandaoni algoriti haiwezi kuona ni miamala gani itakayokuja baadaye. Uamuzi lazima ufanywe mara tu kila muamala unapowasili na usiweze kurejeshwa.

Swali kuu la utafiti ni hili: Njia ya malipo inaweza vipi, bila kujua mapendekezo ya miamala ya baadaye, kuongeza kwa kiwango cha juu zaidi jumla ya idadi ya miamala inayokubaliwa katika hali mbaya zaidi huku ikiweka salio la kituo ndani ya masafa yanayoruhusiwa?

Kwa nini utafiti huu ni muhimu?

Katika mitandao ya njia za malipo, moja ya sababu muhimu za miamala kushindwa ni kwamba angalau kituo kimoja kwenye njia hakina ukwasi wa kutosha katika mwelekeo unaohitajika. Kituo kinapokosa uwiano, ili kiweze kutumika tena huenda ikalazimu kusubiri miamala ya mwelekeo kinyume, kufanya usawazishaji upya wa mzunguko, au kutekeleza muamala wenye gharama kwenye blockchain.

Ikiwa njia ya muamala inapitia zaidi ya kituo kimoja, vituo vyote lazima vikubali muamala huo. Kukataliwa na kituo kimoja kunamaanisha malipo yote kutoka mwanzo hadi mwisho yameshindwa. Kwa hiyo, kutoa maamuzi ya ndani ya kukubali kwa uangalifu kunaweza kuathiri uwezo wa miamala katika mtandao mzima.

Baadhi ya tafiti zilizotangulia zimechunguza matatizo ya uboreshaji nje ya mtandao ambapo mahitaji yote ya miamala yanajulikana mapema, huku nyingine zikichunguza mbinu za kiheuristiki zilizojaribiwa kwenye seti fulani za data. Utafiti huu, kwa upande mwingine, unachunguza modeli kali zaidi ya mtandaoni ambapo miamala huwasili kwa mpangilio wowote na siku zijazo hazijulikani.

Njia ya malipo imegeuzwaje kuwa tatizo la mkoba?

Watafiti wanawakilisha kila pendekezo la muamala kama kipengele chenye ishara:

\[ \sigma_1,\sigma_2,\ldots \]

Hapa σ_i ni kiasi chenye mwelekeo cha pendekezo la i la muamala linalowasili. Ishara chanya na hasi zinaonyesha muamala unasonga katika upi kati ya mielekeo miwili inayowezekana kwenye kituo. Ishara haimaanishi muamala “mzuri” au “mbaya”; inaonyesha tu ukwasi unasogezwa upande gani.

Ukubwa kamili wa kila muamala unakubaliwa kuwa ndani ya masafa yafuatayo:

\[ 1 \leq |\sigma_i| \leq m \]

• 1: Ni ukubwa mdogo zaidi wa muamala baada ya urekebishaji wa kipimo.
• m: Ni ukubwa mkubwa zaidi wa muamala unaoruhusiwa katika sera ya kukubali ya kituo.
• Katika muktadha wa Bitcoin, kipimo kidogo zaidi kinaweza kuwa satoshi.

Kuweka ukubwa mdogo zaidi wa muamala kuwa 1 hakupunguzi ujumla wa modeli. Ikiwa kiwango cha chini halisi cha muamala ni tofauti, kiasi chote, uwezo wa kituo na mkunjo wa kukubali vinaweza kupimwa kwa mgawo uleule.

Hali ya sasa ya kituo inaonyeshwa kwa s:

\[ s \in [-B,B] \]

B ni kikomo kamili cha hali ya kituo katika mwelekeo chanya au hasi. Hali ya kuanzia, isiposemwa vinginevyo, inachukuliwa kuwa:

\[ s_0=0 \]

Hii ina maana kwamba ukwasi wa awali katika pande mbili za kituo umesawazishwa. Ikiwa fedha za kuanzia si sawa, s₀ inaweza kuchaguliwa kuwa tofauti na sifuri.

Ikiwa algoriti inakubali muamala σ_i, hali inasasishwa kama ifuatavyo:

\[ s \leftarrow s+\sigma_i \]

Ikiwa muamala unakataliwa, s haibadiliki. Baada ya kila uamuzi:

\[ -B \leq s \leq B \]

ni lazima sharti hili lihifadhiwe.

Modeli inaongeza nini kwa kiwango cha juu?

Lengo ni kuongeza idadi ya miamala inayokubaliwa, si jumla ya thamani ya kifedha ya miamala iliyokubaliwa wala mapato ya ada yanayopatikana kutoka kwenye kituo. Katika modeli kila muamala unaokubaliwa hutoa faida ya kitengo kimoja.

• Muamala wa satoshi 1 pia huhesabiwa kama kukubaliwa mara moja.
• Muamala mkubwa zaidi pia huhesabiwa kama kukubaliwa mara moja.

Kwa hiyo, utafiti huu ni tofauti na tatizo la kusafirisha kiasi cha juu zaidi au kupata mapato makubwa zaidi ya ada. Watafiti wanalenga idadi ya miamala inayopita, yaani throughput ya kituo, badala ya ujazo wa miamala.

Mafanikio ya algoriti ya mtandaoni yanapimwaje?

Kwa mfuatano wa miamala σ:

• Alg(σ) ni idadi ya miamala inayokubaliwa na algoriti ya mtandaoni.
• Opt(σ) ni idadi ya miamala ambayo suluhisho bora zaidi la nje ya mtandao, linalojua mfuatano wote mapema, linaweza kukubali.

Algoriti ya uamuzi thabiti inachukuliwa kuwa c-ya ushindani ikiwa ukosefu wa usawa ufuatao unatimizwa kwa mifuatano yote ya miamala:

\[ c\cdot Alg(\sigma)\geq Opt(\sigma)-\beta \]

• c ni uwiano wa ushindani usio na kipimo.
• β ni konstanti ya nyongeza inayoweza kutegemea vigezo vya modeli kama B au m.
• β haiwezi kutegemea urefu au maudhui ya mfuatano wa miamala.

Kadiri c inavyokuwa ndogo, ndivyo dhamana ya hali mbaya zaidi ya algoriti ya mtandaoni inavyokuwa imara. Kwa algoriti zilizobahatishwa, badala ya Alg(σ) hutumiwa faida inayotarajiwa juu ya chaguo za bahati nasibu za algoriti.

Kwa nini mbinu ya Greedy haitoshi?

Algoriti ya Greedy hukubali kila muamala ambao hauvunji mipaka ya kituo. Mbinu hii inaonekana ya kawaida kwa muda mfupi; lakini kwa sababu haihifadhi nafasi kwa ajili ya siku zijazo, inaweza kuzalisha throughput ya chini sana katika mifuatano ya miamala iliyoandaliwa kwa nia mbaya.

Kwenye Kielelezo 1, mfuatano ufuatao wa miamala unaonyeshwa kwa B=10:

[ +3,\;-2,\;-5,\;+14,\;+1,\;+1,\;+1,\;+1 ]

Hali ya Greedy hatua kwa hatua ni kama ifuatavyo:

1. +3 inakubaliwa: hali inapanda kutoka 0 hadi 3.
2. -2 inakubaliwa: hali inashuka hadi 1.
3. -5 inakubaliwa: hali inashuka hadi -4.
4. +14 inakubaliwa: hali inapanda hadi kikomo kamili cha +10.
5. Miamala minne ya +1 inayofuata inakataliwa kwa sababu hali ingepita +10.

Greedy inakubali jumla ya miamala minne. Hata hivyo, suluhisho la nje ya mtandao linaweza kukataa muamala wa +14 na kukubali miamala mitatu ya kwanza pamoja na miamala minne midogo ya mwisho, hivyo kukamilisha jumla ya miamala saba. Mfano huu unaonyesha kwamba kukubali muamala mkubwa unaotoshea kwenye mpaka wa kituo kunaweza kuzuia miamala mingi midogo ya baadaye.

Kikomo cha chini cha kihisabati kwa Greedy

Watafiti wanaonyesha kwamba uwiano wa ushindani wa Greedy ni:

\[ \Omega(m) \]

Katika uthibitisho:

\[ d=\left\lceil\frac{B}{m}\right\rceil \]

na:

\[ m'=\frac{B}{d} \]

vinafafanuliwa. m′ ni thamani ya muamala inayoweza kuchaguliwa kati ya 1 na m na ambayo kwa uasimptoti iko katika ukubwa wa m.

Mfuatano wa hali mbaya huundwa kwa awamu za aina zifuatazo zinazofuatana:

• Kwanza idadi ndogo ya miamala mikubwa chanya, ikifuatiwa na idadi kubwa ya miamala midogo chanya.
• Kisha idadi ndogo ya miamala mikubwa hasi, ikifuatiwa na idadi kubwa ya miamala midogo hasi.
• Ishara hubadilishwa kwa zamu katika awamu zinazofuata.

Greedy hukubali miamala mikubwa mwanzoni mwa kila awamu na kujaza kikomo. Suluhisho la nje ya mtandao hukataa miamala mikubwa na kukubali idadi kubwa zaidi ya miamala midogo.

Kutokuwiana kwa uandishi wa kihisabati katika PDF: Katika maandishi ya uthibitisho, mstari unaotoa uwiano kati ya Greedy na suluhisho la nje ya mtandao umeandikwa kama Greedy(σ)=(B/d)·Off(σ). Hata hivyo, kwa kuzingatia idadi ya miamala iliyokubaliwa katika awamu na kikomo cha chini cha Ω(m) kinacholengwa na teorema, mwelekeo wa uhusiano unaonekana kuwa kinyume. Katika awamu 0, Greedy hukubali d na suluhisho la nje ya mtandao hukubali B, kwa hiyo uhusiano wa kawaida unapaswa kuwa Off(σ)=(B/d)·Greedy(σ). Hili ni tatizo la uandishi wa aljebra ambalo halibadilishi matokeo ya jumla ya teorema, lakini linapaswa kutajwa wazi katika PDF.

Wazo kuu la algoriti ya Exp ni lipi?

Algoriti ya uamuzi thabiti iliyopendekezwa na watafiti inaitwa Exp. Jina lake limetokana na mkunjo wa kukubali wa kiexponenti unaotumiwa.

Kwanza kipimo kisaidizi kifuatacho kinafafanuliwa:

\[ b=\frac{B}{\ln B} \]

Dhamana iliyothibitishwa ya algoriti inategemea masharti ya kiufundi yafuatayo:

\[ B\geq 4{,}1 \]

na:

\[ m\leq b=\frac{B}{\ln B} \]

Yaani, kiasi cha juu zaidi cha muamala kinapaswa kuwa kidogo kwa kiwango fulani kuliko kikomo cha hali ya kituo.

Kizingiti cha kukubali kinafafanuliwa na kazi ifuatayo:

\[ f(s)=b\cdot \exp\left(-\frac{|s|}{b}\right) \]

• s ni hali ya sasa ya kituo.
• |s| inaonyesha umbali wa kituo kutoka katikati yenye uwiano.
• b ni kipimo cha mkunjo wa kukubali.
• f(s) ni kiasi kikubwa zaidi cha muamala kinachoweza kukubaliwa katika mwelekeo wa kutokuwiana uliopo.

Exp hukubali muamala unaowasili σ_i ikiwa moja ya masharti mawili yafuatayo yanatimizwa:

1. Ikiwa ishara za muamala na hali ya sasa ni tofauti; yaani muamala unasawazisha kituo kuelekea katikati.
2. Ikiwa muamala uko katika mwelekeo uleule na kutokuwiana kwa sasa na:

\[ |\sigma_i|\leq f(s) \]

unatimiza sharti hilo.

Uamuzi wa Exp unapaswa kutafsiriwaje?

Kituo kinapokuwa na uwiano, |s| ni ndogo na f(s) huwa kubwa zaidi. Algoriti inaweza kukubali miamala mikubwa kiasi katika pande zote mbili. Kadiri kituo kinavyojaa upande mmoja, miamala mikubwa inayokuja katika mwelekeo huo huo huwa hatari zaidi na kizingiti hushuka kiexponenti.

Ikiwa kituo kinakaribia kikomo katika mwelekeo chanya:

• Kwa kuwa miamala chanya husogeza ukwasi zaidi katika mwelekeo huo huo, inakubaliwa tu ikiwa ni midogo sana.
• Miamala hasi hukubaliwa kwa sababu husogeza kituo kuelekea katikati.

Muundo huu huhifadhi akiba ya ukwasi kwa miamala midogo ya baadaye badala ya kujaza uwezo mara moja.

Mkunjo wa kukubali kwenye Kielelezo 2 unaeleza nini?

Kielelezo 2 kinaonyesha mkunjo wa f(s) kwa B=100. Mhimili mlalo unawakilisha hali ya kituo, na mhimili wima unawakilisha ukubwa kamili wa muamala.

Katika mfano huu:

\[ b=\frac{100}{\ln 100}\approx 21{,}7 \]

kwa hiyo, kituo kinapokuwa na uwiano kamili, muamala mkubwa zaidi unaoweza kukubaliwa katika mwelekeo huo huo ni takriban vitengo 21,7:

\[ f(0)=b\approx 21{,}7 \]

Kadiri |s| inavyoongezeka, mkunjo hushuka kwa kasi. Mkunjo ni linganifu katika pande chanya na hasi; kwa sababu kinachojalisha si upande gani umejaa, bali umbali wa kituo kutoka kwenye uwiano.

Ikiwa nukta kwenye grafu iko chini ya mkunjo, muamala hukubaliwa hata kama una ishara sawa na hali ya sasa. Ikiwa muamala na hali zina ishara tofauti, hukubaliwa bila kuangalia mkunjo.

Kwa nini algoriti haivunji mipaka ya kituo?

Teorema ya pili ya utafiti inaonyesha kwamba Exp huweka hali daima ndani ya masafa [-B,B] wakati B≥4,1.

Ikiwa s≥0 na muamala unaokubaliwa ni hasi, muamala husogeza kituo kuelekea katikati au upande wa pili. Kwa kuwa ukubwa wa muamala ni kiwango cha juu m≤b≤B, hali mpya haiwezi kupita kikomo cha chini:

\[ s+\sigma_i\geq s-m\geq -B \]

Ikiwa muamala ni chanya, Exp huuidhinisha tu ikiwa ukubwa wa muamala uko chini ya mkunjo wa kukubali:

\[ \sigma_i\leq f(s) \]

Waandishi wanafafanua hatua ya mwisho ya hali ambapo muamala mdogo zaidi wa mwelekeo huo huo wa 1 bado unaweza kukubaliwa kama:

\[ \hat{s}=b\ln b \]

Kwa sababu:

\[ f(\hat{s})=1 \]

hutokea. Katika hali iliyo juu zaidi ya hapo, hakuna muamala chanya unaoweza kukubaliwa.

Uwiano wa ushindani wa Exp umethibitishwaje?

Katika uthibitisho wa kikomo cha juu, mbinu ya kazi ya potenshali inatumika. Hali ya Exp baada ya muamala wa i inaonyeshwa kwa s_i, huku hali ya suluhisho bora linalojua siku zijazo zote ikiashiriwa kwa s_i^*.

Kutegemea hali ya suluhisho bora na ni kikomo kipi Exp iko karibu nacho:

\[ d_i= \begin{cases} 2B-s_i^*, & s_i\geq 0\\ 2B+s_i^*, & s_i<0 \end{cases} \]

inafafanuliwa.

Kazi ya potenshali:

\[ \Phi(i)=\frac{d_i}{f(s_i)} \]

huchaguliwa. Ikiwa Exp iko mbali na kikomo na katika hali inayonyumbulika, f(s_i) ni kubwa na hivyo potenshali ni ndogo. Exp inapokaribia kikomo, kizingiti cha kukubali hupungua na potenshali huongezeka.

Hatua kuu katika uthibitisho ni kutimizwa kwa ukosefu wa usawa ufuatao kwa kila muamala:

\[ Opt(i)+\Phi(i)-\Phi(i-1)\leq \left(1+(5e-3)\ln B\right)\cdot Exp(i) \]

Lema kisaidizi katika utafiti huweka kikomo cha mabadiliko katika kinyume cha kizingiti cha kukubali kwa muamala chanya unaokubaliwa katika mwelekeo huo huo kama ifuatavyo:

\[ \frac{1}{f(s+x)}-\frac{1}{f(s)} \leq\frac{e-1}{b} \]

Ukosefu wa usawa unapojumlishwa juu ya miamala yote, vipengele vya kati vya potenshali hufutana:

\[ \left(1+(5e-3)\ln B\right)\cdot Exp(\sigma) \geq Opt(\sigma)-O(B\log B) \]

Kwa hiyo, uwiano wa ushindani wa Exp hupatikana kuwa:

\[ O(\log B) \]

Matokeo haya hayamaanishi kwamba algoriti itakubali miamala mingi sawa na suluhisho bora. Yanamaanisha kwamba katika hali mbaya zaidi, tofauti kati ya optimum na Exp imewekewa kikomo na kizidishi cha kiwango cha logarithm ya uwezo.

Kikomo cha chini kwa algoriti zilizobahatishwa

Watafiti pia wameonyesha kwamba hakuna algoriti ya mtandaoni iliyobahatishwa inayoweza kuwa bora kuliko kikomo fulani cha logarithm.

Kwa kikomo cha chini:

\[ q=\left\lfloor\log_2(m/2)\right\rfloor \]

na:

\[ h=\left\lceil\frac{2B}{2^q}\right\rceil \]

vinafafanuliwa. Ingizo linazalishwa kutoka mchakato wa nasibu ambapo awamu chanya na hasi huwasili kwa kupokezana. Katika awamu moja, kwanza huja idadi ndogo ya miamala mikubwa, ikifuatiwa na idadi inayoongezeka ya miamala midogo.

Muda wa awamu z huchaguliwa kutoka usambazaji wa uwezekano ufuatao:

\[ \Pr[z=i]=\frac{2^{-i}}{1-2^{-q}}, \qquad i\in\{1,\ldots,q\} \]

Kwa sababu suluhisho bora la nje ya mtandao linajua awamu itaishia wapi, linaweza kulenga kundi la mwisho na dogo zaidi la miamala. Algoriti ya mtandaoni, kwa upande mwingine, haijui kama awamu itaendelea au la, hivyo inalazimika kugawanya uwezo wake kati ya miamala mikubwa inayowasili mapema na miamala midogo inayoweza kuja baadaye.

Kwa kutumia kanuni ya minimax ya Yao, kwa uwiano wa ushindani wa algoriti yoyote iliyobahatishwa hupatikana:

\[ \Omega(\log m) \]

kama kikomo cha chini.

Kwa nini matokeo yanachukuliwa kuwa bora kiasimptoti?

Kikomo cha juu cha Exp ni O(log B), huku kikomo cha chini cha jumla kikiwa Ω(log m). Wakati kipimo kikubwa zaidi kinachoruhusiwa na algoriti kinachaguliwa kuwa:

\[ m=b=\frac{B}{\ln B} \]

tunapata:

\[ \log m=\log\left(\frac{B}{\ln B}\right) =\Theta(\log B) \]

Kwa hivyo, vikomo vya chini na vya juu hufikia kiwango kilekile cha uasimptoti.

Neno “bora” hapa halimaanishi kwamba vizidishi thabiti ni vidogo zaidi. Linamaanisha kwamba vikomo vya chini na vya juu vinalingana katika kiwango cha ukuaji wa logarithm.

Uigaji uliundwaje?

Uchambuzi wa kinadharia unalenga mifuatano migumu zaidi ya miamala iliyoandaliwa kwa nia mbaya. Watafiti pia walijaribu ikiwa Exp ingekuwa ya tahadhari kupita kiasi katika hali za kawaida za miamala ya nasibu.

Sera nne zililinganishwa:

Uigaji ulifanywa kwenye Python NetworkX na vituo vyote viliwekwa katika hali ya s=0 mwanzoni.

Majaribio ya kituo kimoja na topolojia ya mtandao

Katika jaribio la kwanza, mtandao ulikuwa na njia moja tu ya malipo. Mielekeo ya miamala na ukubwa kamili vilizalishwa kwa nasibu kutoka katika masafa husika. Jumla ya idadi ya miamala iliongezwa kuwa 1.000, 10.000 na 100.000.

Matokeo makuu ya Kielelezo 3 ni kwamba Exp na Greedy zilikubali idadi ya miamala iliyo karibu katika trafiki ya nasibu ya kituo kimoja. Ulinzi wa Exp dhidi ya hali mbaya zaidi haukusababisha upotevu unaoonekana wa throughput katika mtiririko wa kawaida wa nasibu.

Katika majaribio ya mtandao, seti ya data ya Lightning Network Gossip ilitumika. Watafiti walitumia kifurushi cha data gossip-20230924 kujenga upya mwonekano wa mtandao wa tarehe 23 Septemba 2023. Taarifa za uwezo wa vituo zilizokosekana katika data ya Gossip zilikamilishwa kwa kutumia Mempool REST API.

Katika mchakato wa kusafisha:

• Kingo nyingi 23 zilizokuwa zinaunganisha jozi ileile ya nodi kwa vitambulisho tofauti vya muda mfupi vya kituo ziliondolewa.
• Kingo jozi 796 zilizopatikana mara mbili kwa kitambulisho kilekile cha muda mfupi cha kituo ziliunganishwa.
• Baada ya kingo 7.492 za awali, vituo 6.673 vilibaki.

Kwa kila muamala, nodi chanzo na lengwa zilichaguliwa kwa nasibu kwa uwezekano sawa, na njia yenye idadi ndogo zaidi ya kingo ilitafutwa. Malipo yalichukuliwa kuwa yamefaulu ikiwa vituo vyote vilivyokuwa kwenye njia vilikubali muamala.

Kwenye Kielelezo 4, matokeo ya Exp na Greedy yanaonekana kuwa karibu. Hii inaonyesha kwamba Exp haizalishi adhabu inayoonekana ya throughput katika trafiki ya mtandao yenye vyanzo na malengo ya nasibu.

Hali ya muuzaji

Katika hali ya muuzaji, miamala kutoka vyanzo vya nasibu huelekezwa kwenye nodi moja ya lengwa. Mtiririko huu kwa asili ni wa mwelekeo mmoja. Uwezekano wa uwiano wa kituo kujirekebisha wenyewe kupitia miamala kutoka mwelekeo kinyume ni mdogo zaidi.

Katika usambazaji wa miamala, kiasi kidogo kisichobadilika ni satoshi 1.000, huku kiasi kikubwa kikiwa:

\[ \left[ \frac{B_{\min}}{2\ln B_{\min}}, \frac{B_{\min}}{\ln B_{\min}} \right] \]

na huzalishwa kutoka katika masafa haya.

Kutokuwiana kwa mbinu katika PDF: Sehemu ya muhtasari wa majaribio inaeleza kwamba asilimia 85 ya miamala ilizalishwa kwa kiasi cha chini kisichobadilika, na asilimia 15 iliyobaki kutoka kwenye masafa yaliyoainishwa. Hata hivyo, sehemu ya mbinu ya kina inaeleza kwamba muamala mdogo ulizalishwa kwa uwezekano wa asilimia 15 na miamala mikubwa inayobadilika kwa uwezekano wa asilimia 85. Maelezo haya mawili ni kinyume cha kila mmoja. Bila msimbo au ufafanuzi wa waandishi, haiwezekani kubaini kwa uhakika kutoka PDF ni uwiano upi uliotumika.

Kielelezo 5 kinalinganisha idadi ya miamala iliyokubaliwa na Exp na Greedy kwa miamala 30.000 ya muuzaji kulingana na degree ya nodi lengwa:

• Degree ikiwa 3, nguzo ya kukubali ya Exp iko juu kwa kiasi kinachoonekana kuliko ya Greedy.
• Degree ikiwa 8, Exp inaendelea kuwa na faida lakini tofauti inapungua.
• Degree ikiwa 331, mbinu hizi mbili zinakaribiana sana.

Degree ndogo inamaanisha idadi ndogo ya vituo vinavyomfikia muuzaji na uwezo wa pamoja ulio na mipaka zaidi. Katika hali hii Greedy inaweza kukubali miamala mikubwa mapema na kujaza haraka idadi ndogo ya vituo. Kizingiti cha kiexponenti cha Exp huhifadhi uwezo kwa ajili ya miamala midogo na hivyo kuruhusu miamala mingi zaidi kupita.

Ni nguvu zipi za utafiti huu?

• Tatizo la kukubali kwenye njia ya malipo limeundwa wazi kama modeli mpya ya mkoba wa mtandaoni wenye vipengele chanya na hasi.
• Kikomo cha chini cha kihisabati kimetolewa kwa utendaji wa hali mbaya zaidi wa mbinu ya Greedy.
• Imethibitishwa kwamba algoriti ya Exp iliyopendekezwa huweka hali ya kituo daima ndani ya mipaka inayoruhusiwa.
• Kikomo cha juu cha wazi cha O(log B) kimetolewa kwa algoriti.
• Kikomo cha chini pia kinajumuisha algoriti zilizobahatishwa na kinategemea kanuni ya minimax ya Yao.
• Vikomo vya juu na vya chini hukutana katika kiwango kilekile cha uasimptoti kwenye mfumo unaofaa wa vigezo.
• Algoriti inaweza kufanya uamuzi kwa kutumia hali ya sasa pekee bila kuhifadhi historia ya mfuatano wa miamala.
• Matokeo ya kinadharia yameungwa mkono na uigaji wa kituo kimoja, topolojia halisi ya Lightning na trafiki ya muuzaji ya mwelekeo mmoja.

Ni mapungufu gani ya utafiti?

• Nadharia ya kituo kimoja: Modeli ya kihisabati huboresha uamuzi wa ndani wa kituo kimoja. Haijathibitishwa kwamba maamuzi kwenye njia yenye vituo vingi ni bora kwa pamoja katika kiwango cha mtandao mzima.
• Lengo la idadi ya miamala: Kila muamala una faida sawa ya kitengo kimoja. Kiasi cha muamala, ada ya uelekezaji, thamani ya kiuchumi au kipaumbele cha mtumiaji havimo katika kazi lengwa.
• Kikomo cha juu cha muamala: Dhamana ya O(log B) inategemea sharti m≤B/ln B.
• Trafiki sintetiki: Ingawa topolojia ya Lightning ni halisi, vyanzo, malengo na kiasi cha miamala vilizalishwa kutoka usambazaji sintetiki.
• Mwonekano wa zamani wa mtandao: Mwonekano wa mtandao uliotumika ni wa tarehe 23 Septemba 2023.
• Uchaguzi wa njia: Njia yenye idadi ndogo zaidi ya kingo pekee ndiyo ilitumika.
• Kutokuwepo kwa usawazishaji upya: Michakato ya cyclic rebalancing, submarine swap na kuongeza ukwasi kwenye mnyororo haikujumuishwa katika modeli.
• Ucheleweshaji na ulinganifu: Miamala hushughulikiwa kwa mfuatano.
• Mgongano wa usambazaji wa muuzaji: Uwiano wa asilimia 85/15 wa miamala midogo na mikubwa umetolewa kwa namna iliyo kinyume katika sehemu mbili.
• Uandishi katika uthibitisho wa Greedy: Katika uthibitisho wa Teorema 1, uwiano wa aljebra kati ya Greedy na suluhisho la nje ya mtandao unaonekana kuandikwa kinyume.
• Data za grafu: Vielelezo havitoi nguzo za makosa, idadi ya marudio wala majaribio ya umuhimu.

Utafiti unaunga mkono nini?

• Sera ya Greedy inayokubali kila muamala unaofaa inaweza kuwa na utendaji wa chini sana kwa idadi ya miamala katika mifuatano iliyoandaliwa kwa nia mbaya.
• Kupunguza kizingiti cha kukubali katika mwelekeo uleule kadiri kituo kinavyoondoka kwenye uwiano kunaweza kuhifadhi ukwasi kwa miamala midogo ya baadaye.
• Exp ina dhamana ya ushindani ya O(log B) chini ya masharti yaliyotajwa ya ukubwa wa miamala.
• Katika mfumo unaofaa wa vigezo, kiwango cha ushindani cha logarithm hakiwezi kuboreshwa kiasimptoti hata kwa algoriti zilizobahatishwa.
• Exp ilitoa throughput iliyo karibu na Greedy katika uigaji wa trafiki ya kila siku ya nasibu kwenye utafiti.
• Katika trafiki ya mwelekeo mmoja na muuzaji mwenye degree ndogo, Exp inaweza kukubali miamala mingi zaidi kuliko Greedy.

Utafiti hauthibitishi nini?

• Hauthibitishi kwamba Exp itakuwa bora kuliko Greedy katika data zote halisi za miamala ya Lightning.
• Hauonyeshi kwamba Exp huongeza hadi kiwango cha juu jumla ya kiasi cha Bitcoin kinachosafirishwa au mapato ya ada ya mwendeshaji wa kituo.
• Hauthibitishi kwamba maamuzi bora ya ndani kwa kituo kimoja huunda njia bora na usambazaji bora wa ukwasi kwa mtandao mzima.
• Hautoi dhamana ileile ya O(log B) wakati m>B/ln B.
• Hauonyeshi kwamba tabia halisi za watumiaji zinafuata usambazaji sintetiki uliotumika katika utafiti.
• Hauthibitishi kwamba matokeo yale yale yatadumu katika malipo ya njia nyingi au trafiki ya HTLC ya wakati mmoja.
• Hauonyeshi kwamba algoriti huondoa kabisa tatizo la kutokuwiana kwa kituo.

Ina maana gani kwa matumizi ya kila siku na teknolojia?

Nodi ya uelekezaji ya Lightning inaweza, badala ya kukubali kila muamala kwa kuangalia tu kama unatoshea kwenye salio la sasa, kutathmini kwa pamoja mwelekeo ambao kituo kimekosa uwiano na ukubwa wa muamala. Sera inayofanana na Exp inaweza hasa kusaidia miamala mingi midogo kupita katika vituo vya duka, mtoa huduma au lango la malipo vinavyopokea trafiki nzito ya mwelekeo mmoja.

Utekelezaji wa algoriti hauhitaji akili bandia inayotabiri siku zijazo, mwonekano wa kimataifa wa mtandao mzima, au historia ndefu ya miamala. Hata hivyo, ikiwa mwendeshaji anazingatia si tu idadi ya miamala bali pia mapato ya ada, kiasi cha malipo, umuhimu wa mteja na gharama ya usawazishaji upya, kazi lengwa inahitaji kupanuliwa.

Mbinu na Matokeo ya Utafiti

Matokeo makuu ya kinadharia:

• Uwiano wa ushindani wa algoriti ya Greedy ni Ω(m).
• Exp huweka hali ya kituo daima ndani ya masafa [-B,B] wakati B≥4,1.
• Chini ya sharti m≤B/ln B, uwiano wa ushindani wa Exp ni O(log B).
• Uwiano wa ushindani wa algoriti yoyote iliyobahatishwa ni Ω(log m).
• Katika mfumo wa m=B/ln B, vikomo vya juu na vya chini vinalingana katika kiwango cha Θ(log B).

Matokeo makuu ya uigaji:

• Katika miamala ya nasibu ya kituo kimoja, Exp na Greedy zilizalisha idadi ya kukubali iliyo karibu.
• Katika trafiki ya nasibu ya chanzo-lengwa kwenye topolojia halisi ya Lightning, mbinu hizi mbili pia zilionyesha utendaji ulio karibu.
• Katika mtiririko wa muuzaji wa mwelekeo mmoja na degree ndogo ya lengwa, Exp ilitoa faida inayoonekana.
• Kadiri degree ya nodi lengwa na uwezo wa pamoja wa vituo ulivyoongezeka, tofauti kati ya Exp na Greedy ilipungua.
• Kwa kuwa grafu hazina nguzo za makosa wala majaribio ya umuhimu, tofauti za kimajaribio hazipaswi kutafsiriwa kama ubora wa kitakwimu.

Maelezo ya Chanzo na Mbinu

Jina kamili la asili la utafiti: Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items

Waandishi na mpangilio wao: Marcin Bienkowski; Julien Dallot; Dominik Danelski; Maciej Pacut; Stefan Schmid.

Taarifa ya waandishi wa kwanza wenza: PDF haina taarifa ya mchango sawa au waandishi wa kwanza wenza.

Taarifa ya mwandishi wa mawasiliano: PDF haitaji wazi mwandishi wa mawasiliano wala anwani ya barua pepe ya mawasiliano.

Mahusiano ya taasisi:

• Marcin Bienkowski: University of Wrocław, Poland.
• Julien Dallot: TU Berlin, Germany.
• Dominik Danelski: TU Berlin, Germany.
• Maciej Pacut: TU Berlin, Germany.
• Stefan Schmid: TU Berlin na Weizenbaum Institute, Germany.

Ufadhili: German Research Foundation (DFG), SPP 2378 ReNO2, 2025–2029 na Polish National Science Centre, ruzuku nambari 2022/45/B/ST6/00559.

Aina ya chanzo: Toleo la makala ya mkutano/preprint katika taaluma ya sayansi ya kompyuta ya kinadharia na usanifu wa itifaki za mtandao, lenye uthibitisho wa kihisabati na uigaji.

Jukwaa la uchapishaji: arXiv.

Kitambulisho cha arXiv: arXiv:2604.08205v2.

Mwaka wa uchapishaji: 2026.

DOI: 10.48550/arXiv.2604.08205. DOI hii ni DOI ya preprint ya arXiv; DOI tofauti ya toleo la proceedings la mkutano haipo katika PDF.

Jarida au mkutano: Utafiti umewasilishwa kama makala ya mkutano; hata hivyo, PDF iliyopakiwa si nakala ya mwisho ya IEEE proceedings.

Mchapishaji: Taarifa ya mchapishaji wa mwisho wa proceedings haikuweza kuthibitishwa kikamilifu kutoka kwenye PDF.

Kiungo rasmi cha arXiv:https://arxiv.org/abs/2604.08205

Kiungo cha msimbo:https://git.tu-berlin.de/etua/negative-knapsack-network

Makala hii ya Verianla imeandaliwa kwa kuchunguza ufafanuzi wa modeli, algoriti, fomula, teorema, uthibitisho, vielelezo, mbinu za uigaji, mchakato wa kuandaa data za mtandao na matokeo yaliyomo katika PDF nzima iliyopakiwa. Hakuna matokeo ya kisayansi kutoka nje ya PDF yaliyoongezwa.

Mapungufu makuu ya utafiti ni kwamba matokeo ya kinadharia yanategemea modeli ya kituo kimoja, kazi lengwa hupima idadi ya miamala pekee, dhamana inategemea sharti m≤B/ln B, trafiki sintetiki imetumiwa juu ya topolojia halisi, njia nyingi na mifumo ya usawazishaji upya haijaigwa, grafu za majaribio hazina vipimo vya kutokuwa na uhakika, na usambazaji wa miamala ya muuzaji umeelezwa kwa uwiano unaokinzana katika sehemu mbili.

Katika PDF, mwelekeo wa usawa mmoja wa aljebra katika uthibitisho wa kikomo cha chini cha Greedy unaonekana kutokuwiana na idadi ya miamala iliyokubaliwa iliyotolewa katika awamu. Pia, katika hali ya muuzaji, sehemu mbili tofauti za maandishi zinaeleza kwa kinyume ikiwa miamala midogo ni asilimia 85 au asilimia 15. Kutokuwiana huku hakujarekebishwa kimya kimya, bali kumetajwa wazi.