Ин таҳқиқот баррасӣ мекунад, ки дар шабакаҳои каналҳои пардохтӣ, ба монанди Lightning Network, як канал чӣ гуна метавонад шумораи умумии транзаксияҳои қабулшударо афзоиш диҳад, дар ҳоле ки намедонад дар оянда кадом транзаксияҳо меоянд ва пешниҳодҳои воридшавандаи транзаксияро қабул ё рад мекунад. Муҳаққиқон масъаларо ҳамчун масъалаи нави ҷузвдони онлайн моделсозӣ карданд, ки дар он унсурҳои дорои андозаи мусбат ё манфӣ вобаста ба самти транзаксия пайдарпай меоянд, ва алгоритми детерминистии қабул бо номи Exp-ро таҳия карданд. Аз ҷиҳати математикӣ нишон дода шудааст, ки алгоритми Exp, вақте андозаҳои транзаксия дар ҳудуди муайяни болоӣ боқӣ мемонанд, таносуби рақобатии O(log B) дорад; инчунин ягон алгоритми тасодуфигардондашуда умуман наметавонад аз ҳадди поёнии Ω(log m) канорагирӣ кунад.

Дар модел B ҳадди мутлақи ҳолати каналро, ва m бузургтарин андозаи транзаксияеро, ки метавонад қабул карда шавад, ифода мекунад. Exp транзаксияҳои самти муқобилро, ки тавозуни каналро ба марказ меоранд, қабул мекунад, аммо барои транзаксияҳое, ки тавозунро дар самти номувозунии мавҷуда боз ҳам бештар мекунанд, остонаи экспоненсиалии торафт сахттарро татбиқ менамояд. Ҳамин тариқ, барои транзаксияҳои хурд ва мувозинаткунанда ҷой нигоҳ дошта мешавад, дар ҳоле ки транзаксияҳои калон, ки хатари тамом кардани ликвидиятро дар як тарафи канал доранд, интихобан рад карда мешаванд.

Дар симулятсияҳо бо транзаксияҳои синтетикӣ дар топологияи воқеии Lightning Network, Exp дар ҷараёнҳои тасодуфӣ ва мутавозини ҳаррӯзаи транзаксияҳо шумораи транзаксияҳои ба усули маъмули Greedy наздикро қабул кардааст. Дар сенарияҳое, ки транзаксияҳо асосан ба як фурӯшанда дар як самт ҷараён мегирифтанд ва шумораи каналҳо маҳдуд буд, Exp шумораи бештари қабулҳоро таъмин кардааст. Бо вуҷуди ин, таҳқиқот оптимизатсияи муштараки масир ва ликвидиятро барои тамоми шабака не, балки қарори маҳаллии қабули ҳар як каналро меомӯзад; илова бар ин, ба ҷойи таърихи воқеии транзаксияҳо, ҷараёнҳои синтетикии транзаксия, ки дар топологияи воқеии шабака тавлид шудаанд, истифода шудаанд.

Саволи асосии таҳқиқот чист?

Шабакаҳои каналҳои пардохтӣ имкон медиҳанд, ки ба ҷойи интизор шудани сабт ва тасдиқи нав дар блокчейн барои ҳар як транзаксияи криптовалюта, транзаксияҳо тавассути каналҳои пешакӣ маблағгузоришуда берун аз занҷир анҷом дода шаванд. Lightning Network ва Raiden Network аз намунаҳои маъруфи ин равиш мебошанд.

Вақте ду корбар канали пардохтиро мекушоянд, қисми маблағи умумӣ дар як тарафи канал ва қисми боқимонда дар тарафи дигар ҷойгир мешавад. Бо анҷом додани пардохтҳо дар як самт, ликвидият ба тарафи муқобил мегузарад. Агар дар як тарафи канал бақияи кофӣ намонад, транзаксияҳои нави ҳамон самт, ҳатто агар маблағи умумии канал кофӣ бошад ҳам, интиқол дода намешаванд.

Аз ин рӯ, барои канал қабул кардани ҳар як транзаксияи мувофиқ ҳамеша беҳтарин стратегия нест. Транзаксияи калоне, ки имрӯз қабул мешавад, метавонад тавозуни каналро ба ҳадд расонад ва боиси рад шудани шумораи зиёди транзаксияҳои хурди оянда гардад. Аммо дар ҳолати онлайн алгоритм наметавонад бубинад, ки дар оянда кадом транзаксияҳо меоянд. Қарор бояд дар лаҳзаи расидани ҳар транзаксия ва ба таври бозпасногир қабул карда шавад.

Саволи асосии таҳқиқот чунин аст: Канали пардохтӣ чӣ гуна метавонад бе донистани пешниҳодҳои транзаксияҳои оянда, бо нигоҳ доштани тавозуни канал дар фосилаи иҷозатдодашуда, шумораи умумии транзаксияҳои қабулшударо дар шароити бадтарин ба ҳадди аксар расонад?

Чаро таҳқиқот муҳим аст?

Дар шабакаҳои каналҳои пардохтӣ яке аз сабабҳои муҳими нокомии транзаксияҳо он аст, ки ҳадди ақал яке аз каналҳои масир дар самти лозима ликвидияти кофӣ надорад. Вақте канал номутаносиб мешавад, барои дубора қобили истифода гардондани он мумкин аст интизори транзаксияҳои самти муқобил шудан, азнавмувозинаткунии даврӣ анҷом додан ё дар блокчейн транзаксияи хароҷотталаб иҷро кардан лозим шавад.

Агар масири транзаксия аз зиёда аз як канал гузарад, ҳамаи каналҳо бояд транзаксияро қабул кунанд. Рад кардани як канал маънои ноком шудани тамоми пардохти аз оғоз то анҷомро дорад. Аз ин рӯ, боэҳтиёт қабул кардани қарорҳои маҳаллӣ метавонад ба иқтидори транзаксионии тамоми шабака таъсир расонад.

Қисме аз таҳқиқоти қаблӣ масъалаҳои оптимизатсияи офлайнро баррасӣ кардаанд, ки дар онҳо тамоми талаботи транзаксия пешакӣ маълум аст, қисми дигар бошад усулҳои эвристикиро дар маҷмӯаҳои муайяни додаҳо санҷидаанд. Ин таҳқиқот бошад сахттарин модели онлайнро меомӯзад, ки дар он транзаксияҳо бо тартиби дилхоҳ меоянд ва оянда номаълум аст.

Канали пардохтӣ чӣ гуна ба масъалаи ҷузвдон табдил дода шудааст?

Муҳаққиқон ҳар як пешниҳоди транзаксияро ҳамчун унсури дорои аломат муаррифӣ мекунанд:

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

Дар ин ҷо σ_i маблағи самтдори пешниҳоди i-уми транзаксияи воридшаванда мебошад. Аломатҳои мусбат ва манфӣ нишон медиҳанд, ки транзаксия дар кадоме аз ду самти эҳтимолии канал ҳаракат мекунад. Аломат маънои транзаксияи “хуб” ё “бад”-ро надорад; он танҳо нишон медиҳад, ки ликвидият ба кадом тараф интиқол меёбад.

Андозаи мутлақи ҳар транзаксия дар фосилаи зерин қабул карда мешавад:

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

• 1: Андозаи миқёспазири хурдтарини транзаксия мебошад.
• m: Бузургтарин андозаи транзаксия мебошад, ки дар сиёсати қабули канал иҷозат дода шудааст.
• Дар заминаи Bitcoin, хурдтарин миқёс метавонад satoshi бошад.

Ба 1 баробар будани хурдтарин андозаи транзаксия умумиятро маҳдуд намекунад. Агар маблағи ҳадди ақали воқеии транзаксия дигар бошад, ҳамаи маблағҳо, иқтидори канал ва каҷи қабулро метавон бо ҳамон коэффисиент миқёспазир кард.

Ҳолати ҷории канал бо s нишон дода мешавад:

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

B ҳадди мутлақи ҳолати каналро дар самти мусбат ё манфӣ ифода мекунад. Ҳолати ибтидоӣ, агар дигар чиз зикр нашуда бошад:

\[ s_0=0 \]

қабул карда мешавад. Ин ҳолат маънои онро дорад, ки ликвидияти ибтидоӣ дар ду тарафи канал мутавозин аст. Агар маблағҳои ибтидоӣ баробар набошанд, s₀-ро метавон ғайрисифр интихоб кард.

Агар алгоритм транзаксияи σ_i-ро қабул кунад, ҳолат:

\[ s \leftarrow s+\sigma_i \]

ба ин шакл нав карда мешавад. Агар транзаксия рад карда шавад, s тағйир намеёбад. Пас аз ҳар қарор:

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

нигоҳ доштани ин шарт ҳатмист.

Модел чиро ба ҳадди аксар мерасонад?

Ҳадаф зиёд кардани шумораи транзаксияҳои қабулшуда аст, на арзиши умумии пулии транзаксияҳои қабулшуда ё даромади комиссияи аз канал гирифташуда. Дар модел ҳар транзаксияи қабулшуда як воҳид фоида медиҳад.

• Транзаксияи 1 satoshi низ ҳамчун як қабул ҳисоб мешавад.
• Транзаксияи хеле калонтар низ ҳамчун як қабул ҳисоб мешавад.

Аз ин рӯ, таҳқиқот аз масъалаи интиқоли маблағи баландтарин ё гирифтани даромади бештари комиссия фарқ мекунад. Муҳаққиқон ба ҷойи ҳаҷми транзаксия, шумораи гузариши транзаксияҳо, яъне throughput-и каналро ҳадаф мегиранд.

Муваффақияти алгоритми онлайн чӣ гуна чен карда мешавад?

Барои пайдарпаии транзаксияҳои σ:

• Alg(σ) шумораи транзаксияҳое мебошад, ки алгоритми онлайн қабул кардааст.
• Opt(σ) шумораи транзаксияҳое мебошад, ки беҳтарин ҳалли офлайн бо донистани тамоми пайдарпаӣ пешакӣ метавонад қабул кунад.

Алгоритми детерминистӣ c-рақобатӣ ҳисобида мешавад, агар нобаробарии зерин барои ҳамаи пайдарпаии транзаксияҳо иҷро шавад:

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

• c таносуби рақобатии беандоза мебошад.
• β собити иловагӣ мебошад, ки метавонад ба параметрҳои модел, ба монанди B ё m, вобаста бошад.
• β наметавонад ба дарозӣ ё мундариҷаи пайдарпаии транзаксияҳо вобаста бошад.

Ҳар қадар c хурд бошад, кафолати ҳолати бадтарини алгоритми онлайн ҳамон қадар қавитар аст. Дар алгоритмҳои тасодуфигардондашуда ба ҷойи Alg(σ) фоидаи интизоршаванда аз рӯи интихобҳои тасодуфии алгоритм истифода мешавад.

Чаро равиши Greedy нокифоя аст?

Алгоритми Greedy ҳар транзаксияеро, ки ҳаддҳои каналро вайрон намекунад, қабул мекунад. Ин равиш дар кӯтоҳмуддат табиӣ менамояд; аммо азбаски барои оянда ҷой нигоҳ намедорад, дар пайдарпаии транзаксияҳои қасдан бад тарҳрезишуда метавонад throughput-и хеле паст ба вуҷуд орад.

Дар Шакли 1 барои B=10 пайдарпаии зерини транзаксияҳо нишон дода шудааст:

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

Ҳолати Greedy қадам ба қадам чунин аст:

1. +3 қабул мешавад: ҳолат аз 0 ба 3 боло меравад.
2. -2 қабул мешавад: ҳолат ба 1 поён меравад.
3. -5 қабул мешавад: ҳолат ба -4 поён меравад.
4. +14 қабул мешавад: ҳолат ба ҳадди дақиқи +10 боло меравад.
5. Чор транзаксияи +1, ки баъд меоянд, рад карда мешаванд, зеро ҳолат аз +10 мегузарад.

Greedy дар маҷмӯъ чор транзаксияро қабул мекунад. Аммо ҳалли офлайн метавонад транзаксияи +14-ро рад карда, се транзаксияи аввал ва чор транзаксияи хурди охирро қабул кунад ва дар маҷмӯъ ҳафт транзаксияро анҷом диҳад. Ин мисол нишон медиҳад, ки қабули транзаксияи калоне, ки ба ҳадди канал ҷой мегирад, метавонад шумораи зиёди транзаксияҳои хурди ояндаро боздорад.

Ҳадди поёнии математикӣ барои Greedy

Муҳаққиқон нишон медиҳанд, ки таносуби рақобатии Greedy:

\[ \Omega(m) \]

мебошад. Дар исбот:

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

ва:

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

муайян карда мешаванд. m′ арзиши транзаксия мебошад, ки онро байни 1 ва m интихоб кардан мумкин аст ва аз ҷиҳати асимптотикӣ дар тартиби андозаи m қарор дорад.

Пайдарпаии ҳолати бад аз фазаҳои навъи зерин пайдарпай сохта мешавад:

• Аввал шумораи ками транзаксияҳои калони мусбат, сипас шумораи зиёди транзаксияҳои хурди мусбат.
• Баъд шумораи ками транзаксияҳои калони манфӣ, сипас шумораи зиёди транзаксияҳои хурди манфӣ.
• Аломатҳо дар фазаҳои минбаъда бо навбат иваз карда мешаванд.

Greedy транзаксияҳои калони аввали ҳар фазаро қабул карда, ҳаддро пур мекунад. Ҳалли офлайн бошад транзаксияҳои калонро рад мекунад ва шумораи хеле бештари транзаксияҳои хурдро қабул менамояд.

Номувофиқии навишти математикӣ дар PDF: Дар матни исбот сатрие, ки таносуби байни Greedy ва ҳалли офлайнро медиҳад, ба шакли Greedy(σ)=(B/d)·Off(σ) навишта шудааст. Аммо бо назардошти шумораҳои қабули дар фазаҳо овардашуда ва ҳадди поёнии Ω(m), ки теорема мехоҳад ба он расад, самти муносибат баръакс менамояд. Азбаски дар фазаи 0 Greedy d ва ҳалли офлайн B транзаксияро қабул мекунад, муносибати табиӣ бояд Off(σ)=(B/d)·Greedy(σ) бошад. Ин мушкили алгебравии навишт аст, ки натиҷаи умумии теоремаро тағйир намедиҳад, вале бояд дар PDF ошкоро қайд карда шавад.

Ғояи асосии алгоритми Exp чист?

Алгоритми детерминистии пешниҳодкардаи муҳаққиқон Exp ном дорад. Номи он аз каҷи экспоненсиалии қабул, ки истифода мебарад, гирифта шудааст.

Аввал миқёси ёрирасони зерин муайян карда мешавад:

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

Кафолати исботшудаи алгоритм ба шартҳои техникии зерин вобаста аст:

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

ва:

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

Яъне маблағи бузургтарини транзаксия бояд то андозае аз ҳадди ҳолати канал хурдтар бошад.

Остонаи қабул бо функсияи зерин муайян карда мешавад:

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

• s ҳолати ҷории канал мебошад.
• |s| нишон медиҳад, ки канал аз маркази мутавозин то чӣ андоза дур шудааст.
• b миқёси каҷи қабул мебошад.
• f(s) бузургтарин маблағи транзаксия мебошад, ки дар самти номувозунии мавҷуда қабул шуда метавонад.

Exp транзаксияи воридшавандаи σ_i-ро дар сурати иҷро шудани яке аз ду шарти зерин қабул мекунад:

1. Агар аломатҳои транзаксия ва ҳолати ҷорӣ гуногун бошанд; яъне транзаксия каналро ба марказ мувозинат кунад.
2. Агар транзаксия бо номувозунии мавҷуда дар як самт бошад ва:

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

шартро иҷро кунад.

Қарори Exp-ро чӣ гуна бояд шарҳ дод?

Вақте канал мутавозин аст, |s| хурд ва f(s) баландтар аст. Алгоритм метавонад транзаксияҳои нисбатан калони ҳар ду самтро қабул кунад. Ҳангоми пур шудани канал ба як тараф, транзаксияҳои калоне, ки дар ҳамон самт меоянд, хатарноктар мешаванд ва остона ба таври экспоненсиалӣ паст мешавад.

Агар канал дар самти мусбат ба ҳадд наздик шуда бошад:

• Азбаски транзаксияҳои мусбат ликвидиятро боз ҳам дар ҳамон самт мебаранд, танҳо вақте қабул мешаванд, ки хеле хурд бошанд.
• Транзаксияҳои манфӣ каналро ба марказ мебаранд, бинобар ин қабул мешаванд.

Ин сохтор ба ҷойи фавран пур кардани иқтидор, барои транзаксияҳои хурди оянда захираи ликвидият нигоҳ медорад.

Каҷи қабул дар Шакли 2 чиро нишон медиҳад?

Шакли 2 каҷи f(s)-ро барои B=100 нишон медиҳад. Меҳвари уфуқӣ ҳолати канал ва меҳвари амудӣ андозаи мутлақи транзаксияро ифода мекунад.

Дар ин мисол:

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

аз ин рӯ, вақте канал комилан мутавозин аст, бузургтарин транзаксияе, ки дар ҳамон самт қабул шуда метавонад, тақрибан 21,7 воҳид аст:

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

Бо зиёд шудани |s| каҷ зуд паст мешавад. Каҷ дар тарафҳои мусбат ва манфӣ симметрӣ аст; зеро муҳим он нест, ки кадом тараф пур аст, балки канал аз мувозинат то чӣ андоза дур шудааст.

Агар нуқтае дар график зери каҷ бошад, транзаксия ҳатто агар бо ҳолати ҷорӣ ҳамаломат бошад ҳам қабул мешавад. Агар транзаксия ва ҳолат аломатҳои гуногун дошта бошанд, бидуни нигоҳ кардан ба каҷ қабул мешавад.

Чаро алгоритм ҳаддҳои каналро вайрон намекунад?

Теоремаи дуюми таҳқиқот нишон медиҳад, ки ҳангоми B≥4,1 Exp ҳолатро ҳамеша дар фосилаи [-B,B] нигоҳ медорад.

Агар s≥0 ва транзаксияи қабулшуда манфӣ бошад, транзаксия каналро ба марказ ё ба тарафи муқобил мебарад. Азбаски андозаи транзаксия ҳадди аксар m≤b≤B аст, ҳолати нав аз ҳадди поён намегузарад:

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

Агар транзаксия мусбат бошад, Exp танҳо дар сурате онро тасдиқ мекунад, ки андозаи транзаксия зери каҷи қабул бошад:

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

Муаллифон нуқтаи охирини ҳолатро, ки дар он хурдтарин транзаксияи ҳамсамти 1 қабул шуда метавонад, чунин муайян мекунанд:

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

Зеро:

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

мешавад. Дар ҳолати баландтар аз ин ягон транзаксияи мусбат қабул шуда наметавонад.

Таносуби рақобатии Exp чӣ гуна исбот шудааст?

Дар исботи ҳадди боло техникаи функсияи потенсиалӣ истифода мешавад. Ҳолати Exp пас аз транзаксияи i-ум бо s_i, ва ҳолати ҳалли оптималӣ, ки тамоми ояндаро медонад, бо s_i^* нишон дода мешавад.

Вобаста ба ҳолати ҳалли оптималӣ ва ба кадом ҳадд наздик будани Exp:

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

муайян карда мешавад.

Функсияи потенсиалӣ:

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

интихоб мешавад. Агар Exp аз ҳадд дур ва дар ҳолати чандир бошад, f(s_i) калон ва бинобар ин потенсиал хурд аст. Вақте Exp ба ҳадд наздик мешавад, остонаи қабул хурд ва потенсиал баланд мешавад.

Қадами асосии исбот ин аст, ки барои ҳар транзаксия нобаробарии зерин иҷро мешавад:

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

Леммаи ёрирасони таҳқиқот тағйирёбии чаппаи остонаи қабулро барои транзаксияи мусбати ҳамсамти қабулшуда чунин маҳдуд мекунад:

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

Вақте нобаробариҳо дар тамоми транзаксияҳо ҷамъ карда мешаванд, аъзои мобайнии потенсиалӣ ҳамдигарро бекор мекунанд:

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

Ҳамин тавр, таносуби рақобатии Exp:

\[ O(\log B) \]

ба даст меояд. Ин натиҷа маънои онро надорад, ки алгоритм ба андозаи оптимум транзаксия қабул мекунад. Он ифода мекунад, ки дар ҳолати бадтарин фарқи байни оптимум ва Exp бо як зарбкунандаи тартиби логарифми иқтидор маҳдуд мешавад.

Ҳадди поён барои алгоритмҳои тасодуфигардондашуда

Муҳаққиқон инчунин нишон доданд, ки ҳеҷ як алгоритми онлайни тасодуфигардондашуда аз ҳадди муайяни логарифмӣ беҳтар шуда наметавонад.

Барои ҳадди поён:

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

ва:

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

муайян карда мешаванд. Вуруд аз як раванди тасодуфӣ тавлид мешавад, ки дар он фазаҳои мусбат ва манфӣ бо навбат меоянд. Дар як фаза аввал шумораи камтари транзаксияҳои калон, баъд шумораи торафт бештари транзаксияҳои хурд меояд.

Давомнокии фаза z аз тақсимоти эҳтимолияти зерин гирифта мешавад:

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

Азбаски ҳалли оптималии офлайн медонад, ки фаза дар куҷо анҷом меёбад, метавонад ба гурӯҳи охирин ва хурдтарини транзаксияҳо тамаркуз кунад. Алгоритми онлайн бошад намедонад, ки фаза идома меёбад ё не, бинобар ин маҷбур аст иқтидори худро байни транзаксияҳои калони барвақт ва транзаксияҳои хурде, ки мумкин аст баъдтар биёянд, тақсим кунад.

Бо истифода аз принсипи minimax-и Yao барои таносуби рақобатии ҳар гуна алгоритми тасодуфигардондашуда:

\[ \Omega(\log m) \]

ҳадди поён ба даст меояд.

Чаро натиҷа аз ҷиҳати асимптотикӣ оптималӣ ҳисобида мешавад?

Ҳадди болои Exp O(log B), ҳадди поёнии умумӣ бошад Ω(log m) мебошад. Вақте миқёси калонтарини иҷозатдодаи алгоритм:

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

интихоб мешавад:

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

мешавад. Ҳамин тариқ, ҳаддҳои поёнӣ ва болоӣ ба як тартиби асимптотикӣ меоянд.

Калимаи “оптималӣ” дар ин ҷо маънои хурдтарин будани коэффисиентҳои собитро надорад. Он маънои онро дорад, ки ҳаддҳои поёнӣ ва болоӣ дар тартиби афзоиши логарифмӣ мувофиқ меоянд.

Симулятсияҳо чӣ гуна сохта шудаанд?

Таҳлили назариявӣ ба душвортарин пайдарпаии транзаксияҳое, ки қасдан бад омода шудаанд, тамаркуз мекунад. Муҳаққиқон инчунин санҷидаанд, ки оё Exp дар шароити муқаррарии тасодуфии транзаксия аз ҳад муҳофизакор рафтор мекунад ё не.

Чор сиёсат муқоиса карда шудаанд:

Симулятсия дар Python NetworkX анҷом дода шуда, ҳамаи каналҳо дар оғоз ба ҳолати s=0 гузошта шудаанд.

Таҷрибаҳои як канал ва топологияи шабака

Дар таҷрибаи аввал шабака танҳо аз як канали пардохтӣ иборат аст. Самтҳои транзаксия ва андозаҳои мутлақ аз фосилаҳои дахлдор ба таври тасодуфӣ тавлид шудаанд. Шумораи умумии транзаксияҳо ба 1.000, 10.000 ва 100.000 зиёд карда шудааст.

Натиҷаи асосии Шакли 3 ин аст, ки Exp ва Greedy дар трафики тасодуфии як канал шумораи ба ҳам наздики транзаксияҳоро қабул мекунанд. Муҳофизати ҳолати бадтарини Exp дар ҷараёни муқаррарии тасодуфӣ талафоти намоёни throughput ба вуҷуд наовардааст.

Дар таҷрибаҳои шабакавӣ маҷмӯаи додаҳои Lightning Network Gossip истифода шудааст. Муҳаққиқон бо истифода аз бастаи gossip-20230924 намуди шабакаро барои 23 сентябри 2023 бозсозӣ карданд. Маълумоти иқтидори канал, ки дар додаҳои Gossip намерасид, бо Mempool REST API пур карда шудааст.

Дар раванди тозакунӣ:

• 23 канори сершумор, ки як ҷуфти гиреҳро бо шиносаҳои гуногуни кӯтоҳи канал пайваст мекарданд, хориҷ карда шуданд.
• 796 канори ҷуфтие, ки бо ҳамон шиносаи кӯтоҳи канал ду бор пайдо шуда буданд, муттаҳид карда шуданд.
• Аз 7.492 канори ибтидоӣ пас аз тозакунӣ 6.673 канал боқӣ монд.

Барои ҳар транзаксия гиреҳҳои манбаъ ва ҳадаф бо эҳтимолияти баробар ба таври тасодуфӣ интихоб шуда, масири дорои камтарин канор ҷустуҷӯ шудааст. Пардохт муваффақ ҳисобида шудааст, агар ҳамаи каналҳои масир транзаксияро қабул кунанд.

Дар Шакли 4 дида мешавад, ки натиҷаҳои Exp ва Greedy ба ҳам наздиканд. Ин нишон медиҳад, ки Exp дар трафики шабакавӣ бо манбаъҳо ва ҳадафҳои тасодуфӣ ҷаримаи намоёни throughput эҷод намекунад.

Сенарияи фурӯшанда

Дар сенарияи фурӯшанда транзаксияҳое, ки аз манбаъҳои тасодуфӣ меоянд, ба як гиреҳи ҳадаф равона мешаванд. Ин ҷараён табиатан яксамта аст. Эҳтимоли он ки мувозинати канал бо транзаксияҳои аз самти муқобил омада худ аз худ ислоҳ шавад, камтар аст.

Дар тақсимоти транзаксия, маблағи хурди собит 1.000 satoshi ва маблағҳои калон чунинанд:

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

ва аз ин фосила тавлид шудаанд.

Номувофиқии методологӣ дар PDF: Дар бахши шарҳи умумии таҷрибаҳо навишта шудааст, ки 85 фоизи транзаксияҳо бо маблағи пасттарини собит ва 15 фоизи боқимонда аз фосилаи нишондодашуда тавлид шудаанд. Аммо дар бахши муфассали методология гуфта мешавад, ки транзаксияи хурд бо эҳтимолияти 15 фоиз ва транзаксияҳои калони тағйирёбанда бо эҳтимолияти 85 фоиз тавлид шудаанд. Ин ду тавзеҳ баръакси ҳамдигар мебошанд. Бе код ё шарҳи муаллифон аз PDF қатъиян муайян кардан имкон надорад, ки кадом таносуб истифода шудааст.

Шакли 5 барои 30.000 транзаксияи фурӯшанда шумораи қабулҳои Exp ва Greedy-ро аз рӯи дараҷаи гиреҳи ҳадаф муқоиса мекунад:

• Вақте дараҷа 3 аст, сутуни қабули Exp назар ба Greedy ба таври намоён баландтар аст.
• Вақте дараҷа 8 аст, Exp бартарии худро нигоҳ медорад, аммо фарқ кам мешавад.
• Вақте дараҷа 331 аст, ду усул ба ҳам хеле наздик мешаванд.

Дараҷаи паст маънои шумораи ками каналҳое, ки ба фурӯшанда мерасанд, ва иқтидори муттаҳидаи маҳдудтарро дорад. Дар ин ҳолат Greedy метавонад транзаксияҳои калонро барвақт қабул карда, шумораи ками каналҳоро зудтар сер кунад. Остонаи экспоненсиалии Exp бо нигоҳ доштани иқтидор барои транзаксияҳои хурд имкон медиҳад, ки шумораи бештари транзаксия гузарад.

Ҷиҳатҳои қавии таҳқиқот кадомҳоянд?

• Масъалаи қабули канали пардохтӣ ба таври равшан ҳамчун модели нави ҷузвдони онлайн бо унсурҳои мусбат ва манфӣ формула шудааст.
• Барои иҷрои ҳолати бадтарини равиши Greedy ҳадди поёнии математикӣ дода шудааст.
• Исбот шудааст, ки алгоритми пешниҳодшудаи Exp ҳолати каналро ҳамеша дар ҳудудҳои иҷозатдодашуда нигоҳ медорад.
• Барои алгоритм ҳадди болои равшани O(log B) таъмин шудааст.
• Ҳадди поён алгоритмҳои тасодуфигардондашударо низ фаро мегирад ва ба принсипи minimax-и Yao такя мекунад.
• Ҳаддҳои боло ва поён дар режими мувофиқи параметрҳо ба як тартиби асимптотикӣ мерасанд.
• Алгоритм метавонад бе нигоҳ доштани таърихи транзаксияҳо танҳо аз рӯи ҳолати ҷорӣ қарор қабул кунад.
• Натиҷаҳои назариявӣ бо симулятсияҳои як канал, топологияи воқеии Lightning ва трафики яксамтаи фурӯшанда дастгирӣ шудаанд.

Маҳдудиятҳои таҳқиқот кадомҳоянд?

• Назарияи як канал: Модели математикӣ қарори маҳаллии як каналро оптимизатсия мекунад. Исбот нашудааст, ки қарорҳо дар масири бисёрканалӣ дар миқёси тамоми шабака якҷоя беҳтаринанд.
• Ҳадафи шумораи транзаксияҳо: Ҳар транзаксия фоидаи якхела дорад. Маблағи транзаксия, ҳаққи масирдиҳӣ, арзиши иқтисодӣ ё афзалияти корбар дар функсияи ҳадаф ҷой надоранд.
• Ҳадди болоии транзаксия: Кафолати O(log B) ба шарти m≤B/ln B вобаста аст.
• Трафики синтетикӣ: Гарчанде топологияи Lightning воқеӣ аст, манбаъҳо, ҳадафҳо ва маблағҳои транзаксия аз тақсимотҳои синтетикӣ тавлид шудаанд.
• Намуди кӯҳнаи шабака: Намуди шабакаи истифодашуда ба 23 сентябри 2023 тааллуқ дорад.
• Интихоби масир: Танҳо масири дорои камтарин канор истифода шудааст.
• Набудани азнавмувозинаткунӣ: Равандҳои rebalancing-и даврӣ, submarine swap ва илова кардани ликвидият дар занҷир ба модел дохил карда нашудаанд.
• Таъхир ва ҳамзамонӣ: Транзаксияҳо пайдарпай баррасӣ мешаванд.
• Зиддияти тақсимоти фурӯшанда: Таносубҳои 85/15 фоизи транзаксияҳои хурд ва калон дар ду бахш баръакс дода шудаанд.
• Навишти исботи Greedy: Дар исботи Теоремаи 1 таносуби алгебравии байни Greedy ва ҳалли офлайн баръакс навишта шуда ба назар мерасад.
• Додаҳои графикӣ: Дар шаклҳо сутунҳои хато, шумораи такрорҳо ва санҷишҳои аҳамиятнокӣ пешниҳод нашудаанд.

Таҳқиқот чиро дастгирӣ мекунад?

• Сиёсати Greedy, ки ҳар транзаксияи мувофиқро қабул мекунад, метавонад дар пайдарпаии қасдан бад тартибдодашуда аз рӯи шумораи транзаксияҳо иҷрои хеле паст дошта бошад.
• Ҳангоми дур шудани канал аз мувозинат кам кардани остонаи қабули ҳамсамт метавонад барои транзаксияҳои хурди оянда ликвидият нигоҳ дорад.
• Exp дар шароити зикршудаи андозаи транзаксия кафолати рақобатии O(log B) дорад.
• Дар режими мувофиқи параметрҳо тартиби рақобатии логарифмӣ аз ҷиҳати асимптотикӣ ҳатто барои алгоритмҳои тасодуфигардондашуда ҳам беҳтар карда намешавад.
• Exp дар симулятсияҳои трафики тасодуфии ҳаррӯзаи таҳқиқот throughput-и ба Greedy наздикро таъмин кардааст.
• Дар трафики яксамта ва фурӯшандаи дараҷаи паст Exp метавонад нисбат ба Greedy транзаксияҳои бештар қабул кунад.

Таҳқиқот чиро исбот намекунад?

• Он исбот намекунад, ки Exp дар ҳамаи додаҳои воқеии транзаксияҳои Lightning аз Greedy беҳтар хоҳад буд.
• Он нишон намедиҳад, ки Exp маблағи умумии Bitcoin-и интиқолёфта ё даромади ҳаққи оператори каналро ба ҳадди аксар мерасонад.
• Он исбот намекунад, ки қарорҳои оптималии маҳаллӣ барои як канал барои тамоми шабака масир ва тақсимоти оптималии ликвидиятро ба вуҷуд меоранд.
• Он ҳангоми m>B/ln B ҳамон кафолати O(log B)-ро пешниҳод намекунад.
• Он нишон намедиҳад, ки рафтори воқеии корбарон ба тақсимотҳои синтетикии таҳқиқот мувофиқ аст.
• Он исбот намекунад, ки дар пардохтҳои бисёрмасира ё трафики ҳамзамони HTLC ҳамон натиҷаҳо нигоҳ дошта мешаванд.
• Он нишон намедиҳад, ки алгоритм мушкили номувозунии каналро пурра аз байн мебарад.

Ин барои истифодаи ҳаррӯза ва технология чӣ маъно дорад?

Гиреҳи масирдиҳии Lightning метавонад ба ҷойи қабул кардани ҳар транзаксия танҳо аз рӯи он ки ба бақияи ҷорӣ мувофиқ аст ё не, ҳам самти номувозунии канал ва ҳам андозаи транзаксияро якҷоя арзёбӣ кунад. Сиёсати монанди Exp махсусан дар каналҳои мағоза, провайдери хидмат ё шлюзи пардохт, ки трафики зичи яксамта мегиранд, метавонад ба гузаштани шумораи бештари пардохтҳои хурд кумак кунад.

Барои татбиқи алгоритм зеҳни сунъие, ки ояндаро пешгӯӣ мекунад, намуди глобалии тамоми шабака ё таърихи дарози транзаксияҳо лозим нест. Бо вуҷуди ин, агар оператор на танҳо шумораи транзаксияҳо, балки даромади ҳаққ, маблағи пардохт, аҳамияти муштарӣ ва хароҷоти азнавмувозинаткуниро низ ба назар гирад, функсияи ҳадаф бояд васеъ карда шавад.

Усул ва Натиҷаҳои Таҳқиқот

Натиҷаҳои асосии назариявӣ:

• Таносуби рақобатии алгоритми Greedy Ω(m) аст.
• Exp ҳангоми B≥4,1 ҳолати каналро ҳамеша дар фосилаи [-B,B] нигоҳ медорад.
• Дар шарти m≤B/ln B таносуби рақобатии Exp O(log B) аст.
• Таносуби рақобатии ҳар гуна алгоритми тасодуфигардондашуда Ω(log m) аст.
• Дар режими m=B/ln B ҳаддҳои боло ва поён дар тартиби Θ(log B) мувофиқ меоянд.

Натиҷаҳои асосии симулятсия:

• Дар транзаксияҳои тасодуфии як канал Exp ва Greedy шумораҳои ба ҳам наздики қабулро тавлид кардаанд.
• Дар трафики тасодуфии манбаъ-ҳадаф дар топологияи воқеии Lightning ду усул боз ҳам иҷрои ба ҳам наздик нишон додаанд.
• Дар ҷараёни яксамтаи фурӯшанда ва дараҷаи пасти ҳадаф Exp бартарии намоён нишон додааст.
• Бо афзоиши дараҷаи гиреҳи ҳадаф ва иқтидори муттаҳидаи канал фарқи байни Exp ва Greedy кам шудааст.
• Азбаски дар графикҳо сутунҳои хато ва санҷишҳои аҳамиятнокӣ дода нашудаанд, фарқҳои таҷрибавӣ набояд ҳамчун бартарии оморӣ шарҳ дода шаванд.

Ёддошт оид ба Манбаъ ва Усул

Номи пурраи аслии таҳқиқот: Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items

Муаллифон ва тартиби онҳо: Marcin Bienkowski; Julien Dallot; Dominik Danelski; Maciej Pacut; Stefan Schmid.

Маълумот дар бораи ҳаммуаллифи аввал: Дар PDF изҳороти саҳми баробар ё ҳаммуаллифи аввал вуҷуд надорад.

Маълумот дар бораи муаллифи масъул: Дар PDF муаллифи масъул ё суроғаи почтаи электронии тамос ба таври возеҳ нишон дода нашудааст.

Пайвандҳои институтсионалӣ:

• Marcin Bienkowski: University of Wrocław, Лаҳистон.
• Julien Dallot: TU Berlin, Олмон.
• Dominik Danelski: TU Berlin, Олмон.
• Maciej Pacut: TU Berlin, Олмон.
• Stefan Schmid: TU Berlin ва Weizenbaum Institute, Олмон.

Маблағгузорӣ: German Research Foundation (DFG), SPP 2378 ReNO2, 2025–2029 ва Polish National Science Centre, гранти рақами 2022/45/B/ST6/00559.

Навъи манбаъ: Нусхаи мақолаи конфронсӣ/preprint дар соҳаи илми назариявии компютерӣ ва тарҳрезии протоколҳои шабакавӣ, ки исботҳои математикӣ ва симулятсияҳоро дар бар мегирад.

Платформаи нашр: arXiv.

Шиносаи arXiv: arXiv:2604.08205v2.

Соли нашр: 2026.

DOI: 10.48550/arXiv.2604.08205. Ин DOI-и preprint-и arXiv мебошад; DOI-и алоҳидаи нусхаи proceedings-и конфронс дар PDF ҷой надорад.

Маҷалла ё конфронс: Таҳқиқот ҳамчун мақолаи конфронсӣ пешниҳод шудааст; аммо PDF-и боршуда нусхаи ниҳоии IEEE proceedings нест.

Ношир: Маълумоти ношири ниҳоии proceedings аз рӯи PDF пурра тасдиқ карда нашуд.

Пайванди расмии arXiv:https://arxiv.org/abs/2604.08205

Пайванди код:https://git.tu-berlin.de/etua/negative-knapsack-network

Ин мақолаи Verianla бо баррасии таърифҳои модел, алгоритмҳо, формулаҳо, теоремаҳо, исботҳо, шаклҳо, усулҳои симулятсия, раванди омодасозии додаҳои шабака ва натиҷаҳои дар тамоми PDF-и боршуда мавҷудбуда омода шудааст. Аз берун аз PDF натиҷаи илмӣ илова нашудааст.

Маҳдудиятҳои асосии таҳқиқот аз инҳо иборатанд: натиҷаи назариявӣ ба модели як канал такя мекунад, функсияи ҳадаф танҳо шумораи транзаксияҳоро чен мекунад, кафолат ба шарти m≤B/ln B вобаста аст, дар топологияи воқеӣ трафики синтетикӣ истифода шудааст, механизмҳои бисёрмасира ва азнавмувозинаткунӣ моделсозӣ нашудаанд, дар графикҳои таҷрибавӣ ченакҳои номуайянӣ вуҷуд надоранд ва тақсимоти транзаксияҳои фурӯшанда дар ду бахш бо таносубҳои зиддиятнок шарҳ дода шудааст.

Дар PDF самти як баробарии алгебравӣ дар исботи ҳадди поёнии Greedy бо шумораҳои қабули дар фазаҳо овардашуда номувофиқ менамояд. Илова бар ин, дар сенарияи фурӯшанда дар ду бахши гуногуни матн баръакс навишта шудааст, ки транзаксияҳои хурд 85 фоизанд ё 15 фоиз. Ин номувофиқиҳо хомӯшона ислоҳ нашуда, ошкоро қайд шудаанд.