Network coding v peer-to-peer sieťach

Network coding

Zatiaľ všetky spomenuté siete distribuovali samotné dáta súborov tak, že uzly si jednoducho posielali medzi sebou časti súborov. Takéto riešenie je funkčné a jednoduché, ale pri zriedkavých súboroch sa celkom často stáva, že pôvodný vlastník celého súboru opustí sieť a niekoľko uzlov ostane bez niektorej časti súboru. Klientské programy sa to väčšinou snažia riešiť tak, že sa snažia získať najprv najzriedkavejšiu časť súboru. Existuje ale spôsob, ktorý umožňuje, aby kusy súborov boli „navzájom zameniteľné“. V ideálnom prípade stačí ľubovolných rozdielnych n častí zakódovaného súboru namiesto konkrétnych n častí (ako v prípade klasických p2p sietí). Jedna z možností, ako to dosiahnuť, sa nazýva network coding. Network coding je pomerne rozsiahla teória, preto sa zameriame na jeden príklad, linear network coding. Na úplné pochopenie treba vedieť dosť z lineárnej algebry a konečných telies, ale myšlienka sa dá vysvetliť len s použitím jednoduchej (maximálne stredoškolskej) matematiky. Zároveň sa to bude ľahšie čítať a človeka hneď z toho netrafí šľak ;-) Pre účely výkladu nebudeme potrebovať nič zložitejšie než sčítanie, násobenie a umocňovanie v reálnych číslach.

Kódovanie súboru

Súbor sa, ako obvykle, najprv rozdelí na n častí. Teraz si predstavíme každú časť súboru nie ako postupnosť bitov, ale ako číslo (hoci šialene veľké), bity časti súboru sú reprezentácia toho čísla. Posielať nebudeme jednotlivé časti, ale ich lineárnu kombináciu. Lineárna kombinácia čísel a₁, a₂, …, a_n vznikne tak, že každý z členov vynásobíme nejakým koeficientom a sčítame, teda je to

c₁a₁ + c₂a₂ + … + c_n*a_n

Členy c_i sú koeficienty lineárnej kombinácie, ktoré si zvolíme. Pri kódovaní súboru si najprv náhodne zvolíme jednotlivé koeficienty c_i, napr. ako celé číslo od 0 po 2¹⁶-1. Väčšinu koeficientov si dokonca môžme zvoliť nulové, to znamená, že daná časť nebude zahrnutá v lineárnej kombinácii. Mnoho nulových koeficientov tiež znamená rýchlejšie počítanie. Po sieti iným účastníkom posielame práve až túto lineárnu kombináciu spolu s koeficientami, aké sme zvolili. Stiahnutie súboru teda znamená získanie n lineárnych kombinácií s ich koeficientami (matematici by doplnili, že lineárne nezávislých).

Najlepšie bude asi uviesť príklad. Predstavme si, že náš súbor rozdelíme na 4 kusy a tieto kusy budú mať hodnoty 4, 7, 12, 9 (v realite by boli samozrejme obrovské). Označíme tieto štyri hodnoty ako x, y, w, z. Účastník, ktorý si tento súbor bude chcieť od nás stiahnuť, si od nás teda vypýta postupne 4 lineárne kombinácie. Pošleme mu napríklad tieto štyri:

2x + 7w = 92, pošleme 92 a koeficienty (2, 0, 7, 0)
x + y + 3z = 32, pošleme 32 a koeficienty (1, 1, 0, 3)
7y + 7z = 112, pošleme 112 a koeficienty (0, 7, 0, 7)
5y + 14*z = 161, pošleme 161 a koeficienty (0, 5, 0, 14)

Dekódovanie súboru

Asi ste si už všimli, že sme tomu druhému účastníkovi vlastne poslali systém 4 lineárnych rovníc, kde neznáme sú práve časti súboru. Aby získal dekódovaný súbor, stačí mu vyriešiť ten systém. Na to klientský program musí invertovať maticu a vynásobiť ju obdržanými časťami. V skutočnosti sa koeficienty aj časti súborov nepočítajú v celých (alebo reálnych) číslach, ale v konečných telesách. Preto sa pri násobení/sčítavaní lineárne kombinácie nepredlžujú. Jediný overhead sú koeficienty, ale tie sú maličké (maximálne pár kB) oproti veľkosti lineárnej kombinácie (stovky kB až niekoľko MB).

Výhody network codingu

Pravdepodobnosť úspešného doťahania súboru je vždy aspoň taká, ako pri klasickej „rozdeľ a ťahaj“ metóde (vrátane stratégie „najzriedkavejšie prvé“), ale typicky vyššia. Jediný predpoklad je, že klient posielajúci lineárne kombinácie musí voliť koeficienty so správnym pravdepodobnostným rozdelením, tj. vhodný počet častí musí byť zahrnutý do lineárnej kombinácie a samotné koeficienty by sa nemali príliš opakovať (uniformné rozdelenie je asi dosť dobré).

Klient, ktorý ešte nemá doťahaný celý súbor (dostatočný počet lineárnych kombinácií), ich samozrejme môže zdieľať ďalej s ostatnými. Naviac má možnosť lineárne kombinácie ďalej kombinovať. Napr. dajme tomu, že má tieto tri lineárne kombinácie z prechádzajúceho príkladu (prvé číslo v zátvorke je hodnota tej lineárnej kombinácie, vnútorná zátvorka sú koeficienty):

(92, (2, 0, 7, 0)), (32, (1, 1, 0, 3)), (112, (0, 7, 0, 7))

Keď ho iný klient požiada o lineárnu kombináciu, vytvorí novú. Vyberie si najprv zase náhodne 3 koeficienty, každú z jeho troch lineárnych kombinácií vynásobí odpovedajúcim koeficientom a pošle ich súčet. Nové koeficienty vie vypočítať, pretože pozná staré. Napríklad si zvolí koeficienty 1, 2, 0. Vypočíta a pošle:

1(92, (2, 0, 7, 0)) + 2(32, (1, 1, 0, 3)) + 0*(112, (0, 7, 0, 7)) = (156, (4, 2, 7, 6))

Tým pádom vytvorí lineárnu kombináciu, ktorá obsahuje nové informácie, iné než ktorákoľvek jeho kombinácia predtým. Čím viac rozličných lineárnych kombinácií existuje, tým väčšia je pravdepodobnosť, že keď nejakú kombináciu stiahne od niektorého klienta, bude „vhodná“ (pre matematikov: lineárne nezávislá od už získaných). V skutočnosti ale klient nikdy nesťahuje nejakú kombináciu, o ktorej vie, že mu už nič nové nepovie. Pred stiahnutím kombinácie sa opýta druhého klienta najprv na koeficienty a porovná si ich s koeficientami už stiahnutých kombinácií. Ak by sa mu nehodili, povie druhému klientovi, nech mu ponúkne inú lineárnu kombináciu.

Pri network codingu (takmer) neexistuje „najzriedkavejší kus“, všetky časti (lineárne kombinácie) sú „rovnako dôležité“. Ako dôsledok sa (takmer) nikdy nestane, že by nejaký klient mal ako jediný určitú časť súboru, ktorú všetci chcú a musia na neho čakať.

Network coding vs. tradičné „rozdeľ a ťahaj“ metódy

O koľko lepší je vlastne linear network coding než klasický prenos skombinovaný so stratégiou „najprv najzriedkavejšie“? Na to nie je vôbec jednoduché odpovedať, existuje velmi veľa parametrov, od ktorých to závisí – počet uzlov siete, počet ľudí hľadajúcich daný súbor, počet ľudí zdieľajúcich daný súbor alebo jeho časť, priebeh pripájania a vypadávania uzlov, ktoré majú aspon časť súboru, atď.

Dá sa povedať, že pri populárnych súboroch (aspoň 100 ľudí zdieľa celý súbor) je pravdepodobnosť kompletného získania súboru takmer rovnaká (skoro 100%). Network coding ale môže stále optimalizovať samotný prenos. Vyplýva to z faktu, že network coding je teória založená na tokoch v sieťach, ktorá sa snaží minimalizovať nutnosť retransmisie rovnakých dát v sieti. Naopak je to ale pri zriedkavých súboroch – tam network coding ponúka veľké výhody.

Letní fotosoutěž o ceny

Čas dovolených, prázdnin a digitálních foťáků je tady. Připravili jsme pro vás na prázdniny velkou fotosoutěž o zajímavé ceny. Máte šanci vyhrát PDA s operačním systémem Palm OS, set-top-box pro příjem digitální televize a další skvělé ceny! Pošlete nám své fotky a vyhrajte.

Asi pred rokom vyšla štúdia, ktorá mala na túto otázku odpovedať – model siete Avalanche od výskumnej sekcie Microsoftu. Porovnáva sa tam BitTorrent oproti sieti s network codingom. Štúdia nie je zlá, ale porovnáva sa s pomerne starou verziou BitTorrent protokolu (čo jej Bram Cohen, autor siete BitTorrent, už vtedy vytýkal). Ďalej je to len model, skutočná implementácia ešte neexistuje. Je ale stále dosť možné, že by to naozaj bolo rýchlejšie, len by to chcelo skutočne namerať – modeluje sa to dosť ťažko. Pokiaľ viem, neexistuje žiadna p2p sieť, ktorá by implementovala network coding.

Nevýhody network codingu

Invertovanie matice (pri počítaní sústavy lineárnych rovníc) nie je zrovna rýchla operácia. Závisí od jej veľkosti, teda na koľko častí bude distribuovaný súbor rozdelený (viac častí znamená spomalenie). Oproti času sťahovania to ale stále nie je veľa, naviac invertovať sa dá postupne, ako prichádzajú jednotlivé lineárne kombinácie. Oveľa väčší problém je pamäťová náročnosť. Pre najrýchlejšie dekódovanie súboru by mali byť všetky lineárne kombinácie naraz v pamäti. Keďže lineárne kombinácie dokopy sú práve také veľké, ako sťahovaný súbor, pri (niekoľko)giga­bajtových súboroch to môže byť trocha problém. Problém pamäťovej náročnosti sa dá ale obísť za cenu dlhšieho počítania.

Je tu ale ešte jeden problém, ktorý sme nespomenuli: ako zaručiť integritu prenášaných častí? Tradičné haše ako SHA-1 nám príliš nepomôžu, pretože násobenie a sčítanie by ich úplne rozhádzalo. Integrita by sa dala overiť až po stiahnutí súboru, ale v prípade chyby by sme nevedeli, kde nastala. Existuje ale riešenie.

Homomorfný haš

Homomorfná hašovacia funkcia H je taká, ktorá má nasledovnú vlastnosť: pre každé dve čísla x, y (resp. bloky dát) platí

H(x+y) = H(x) * H(y)

Táto vlastnosť nám umožní overovať aj lineárne kombinácie blokov na základe známych hašov jednotlivých kusov súboru (tie zverejní vlastník pri zverejňovaní súboru). Naviac od našej funkcie požadujeme bezpečnostné vlastnosti, ako jednosmernosť a odolnosť na kolízie. Našu funkcia H skonštruujeme nasledovne: Súbor bude delený na rovnako veľké bloky (okrem posledného), napr. 8 MB. Pri počítaní hašu každého bloku ho rozdelíme na m podblokov (napr. 512) po 16 kB. Funkciu definujeme takto:

H(b) = g₁^b₁ * g₂^b₂ * … * g_m^b_m

kde ‚^‘ znamená umocnenie. Členy g_i sú tzv. generátory a sú pre všetkých rovnaké (raz určené pre celý systém), b predstavuje celý blok, b_i sú jednotlivé podbloky daného bloku (zase si ich predstavíme ako číslo). Hľadaná vlastnosť H(x+y) = H(x) * H(y) plynie z jednoduchej vlastnosti umocňovania, že a^(x+y) = a^x*a^y pre každé a>0, reálne x a reálne y. V skutočnosti sa to počíta zase v konečných telesách, pretože v reálnych číslach by haše boli šialene veľké.

Haš overíme tak, že najprv vypočítame haš práve stiahnutej lineárnej kombinácie. Jej koeficienty vieme a tiež vieme, aké haše by mali mať jednotlivé ešte nekódované bloky (to sme si zistili na začiatku). Nech c_i sú jednotlivé koeficienty a h_i sú haše jednotlivých blokov (i od 1 po n, čo je počet blokov). Vypočítame číslo:

h₁^c₁ * h₂^c₂ * … * h_n^c_n

Porovnáme toto číslo oproti práve vypočítanému hašu stiahnutej lineárnej kombinácie. Ak sedí, lineárna kombinácia je v poriadku, inak je chybná. Bezpečnosť (jednosmernosť) hašu spočíva v tom, že nikto nedokáže nájsť také i, j, x, y, že g_i^x = g_j^y – keby dokázal, mohol by haš falšovať (poprehadzovaním poradia blokov alebo výmenou blokov). To je druhý dôvod, prečo sa nepočíta v reálnych číslach, tam by stačilo vypočítať logaritmus. V konečných telesách je to ale inak – tzv. problém diskrétneho logaritmu je nemožné riešiť v rozumnom čase v telesách (grupách) s určitými vlastnosťami.

Homomorfná hašovacia funkcia má niekoľko parametrov: spomínané g_i a ešte dve prvočísla p a q. Výsledný haš je o dosť väčší než u klasických hašov typu SHA-1, rádovo 1024 bitov alebo viac. Problém diskrétneho logaritmu by bol riešiteľný v prípade, že by za p a q boli vybrané tzv. cooked primes („predvarené prvočísla“), čo sú špeciálne vybrané prvočísla, ktoré umožňujú niektoré inak nemožné útoky. Brániť sa dá tomu dvoma spôsobmi: buď veríme, že boli vybrané tvorcom software (p2p siete) poctivo, alebo budú vyberané pre každý súbor zvlášť. Vybratie pre daný súbor by vyzeralo tak, že by sa súbor zhašoval nejakou klasickou haš funkciou (napr. SHA-1) a tento haš by sa použil ako seed pre generátor pseudonáhodných čísel (PRNG). Nejaký jasne stanovený (a verejný) algoritmus by použil PRNG na vygenerovanie tých dvoch prvočísiel. Každý by si potom mohol overiť, že pre daný súbor boli vygenerované prvočísla čestne. Záujemcov o podrobnejší rozbor bezpečnosti homomorfného hašu odkážem na prácu On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution, sekcia IV – Homomorphic hashing.

Popísaná homomorfná hašovacia funkcia má kopu zaujímavých vlastností, ale má jednu drobnú chybu krásy – je o dosť pomalšia než bežné hašovacie funkcie (SHA-1, Tiger, atď.), pretože používa mnoho modulárneho umocňovania. Ak by ale network coding naozaj pomohol znížiť čas distribúcie súboru, tento nedostatok by sa tým mohol kompenzovať. Ďalšia pozitívna vec je, že takto definovaná homomorfná funkcia zrejme vydrží oveľa dlhšie snahám kryptoanalytikov o jej prelomenie, pretože je založená na dlho známom (a dlho odolávajúcom) probléme diskrétneho logaritmu.

Nabudúce

Keď sme už načali témy o bezpečnosti a integrite, pozrieme sa, ako fungujú siete snažiace sa o anonymitu účastníkov – siete založené na onion routingu.