File transfer in de toekomst

[Aphelion]

Beste medetweakers,

Ik zit al een tijdje met het volgende in mijn hoofd. Computerontwikkelingen gaan de laatste tijd erg hard. Waar we een paar jaar terug nog computers hadden op 500 Mhz, tegenwoordig werken we op Quad processors van ieder 3,5 Ghz. We hebben ook steeds meer schrijfruimte. van Een paar GB naar personen met een prive raid setup van 1TerraByte.

Ik zit nu met een idee in mijn hoofd dat over circa een 10 jaar misschien mogelijk is. Een nieuwe manier om gegevens te versturen over het internet. Denk aan een nieuw protocol. Je hebt een Fileserver met grote bestanden, bijvoorbeeld grote documenten, trailers, mp3's etc. Stel nu dat die server in plaats van jou een file upload jou slechts een hash van de file meestuurt. Over 10 jaar is een computer waarschijnkijk snel genoeg om een document van 100mb in enkele seconden te bruteforcen. Je download alleen de hash, encode de file opnieuw en je hebt zonder enig gebruik van bandbreedte een groot file gedownload.

Is het mogelijk om dit te realiseren? Theoretisch goed uit te werken en mogelijk voor in de toekomst dus waarheid te maken?

De eerste problemen waar ik tegenkom zijn collisions. Dit kan je voorkomen voor herkenningspunten mee te geven, bijv: de bronfile moet beginnen met string "xxxxx" en eindigen met string "xxxxx". Kost een paar bytes extra en zal het decodeerproces versnellen.

Even snel een paar punten waar ik dan aan denk
+ Supersnel gegevens zenden over het internet
+ Geen bandbreedte gebruik, in feite unlimited snel gegevens downloaden

Ik kom meteen tot het volgende discussiepunt. Als dit in de toekomst mogelijkheid zou zijn. In hoeverre is grootte dan nog van belang?

Als we nog verder kijken. Is het dan niet mogelijk om enkel nog hashes van documenten te bewaren op een HDD, en deze realtime te decoderen en encoderen. Dan zou zelfs een harddisk van 1gb van nu terrabytes aan gegevens kunnen bevatten. Kijk eens naar de mogelijkheden die dit levert.

Kort samengevat:
- Is het mogelijk dit theoretisch uit te werken? (technieken, hash, protocol etc)
- Is het mogelkijk dit in de toekomst te realiseren?
- Heeft het nut om dit te realiseren?
- Wat zijn de voordelen
- Wat zijn de nadelen

Graag serieus meedenken ipv meteen het idee afkraken. Graag beargumenteerd meedenken. Dank

[Snake]

Dan moet je een hash creeeren die 100% uniek is!

En ik weet niet of dat mogenlijk is

[Verwijderd]

- Is het mogelijk dit theoretisch uit te werken? (technieken, hash, protocol etc)

Ik denk dat het goed mogelijk is om *iets* in de trant van wat je geschreven hebt te realiseren. Maar de ontwikkeling gaat zo hard, dat misschien de manier van data opslaan over +/- 10 jaar heel anders is.

- Is het mogelkijk dit in de toekomst te realiseren?

Dat weet je niet, je weet niet welke techniek(en) er in de toekomst gebruikt worden..... (zie ook hierboven)

- Heeft het nut om dit te realiseren?

Uiteraard Alles moet sneller, dus ook downloaden. Ik zie maar weinig mensen patsen met de uptime die hun pc haalt omdat ze een *groot bestand* ( ) aan het downloaden zijn. minder tijd=minder stroomverbruik=beter voor het milieu

- Wat zijn de voordelen

Beetje hetzelfde als hierboven

- Wat zijn de nadelen

Ik kan me er niet zo snel eentje bedenken. Het enige is dat je pc eventjes bezig is

[sjroorda]

Het idee klinkt erg leuk, alleen is een hash juist iets dat niet uniek is; voor zover ik weet bestaan er geen unieke hashes. Wat wellicht wel een oplossing zou kunnen zijn is het meegeven van de lengte van de 'string', zoals jij de begin- en eindbytes meegeeft. Echter, hiervoor zou je wel moeten kunnen garanderen dat de oplossing uniek is! Je kan dan net zolang extra informatie meegeven tot dat het geval is, maar dat kost onevenredig veel tijd.

Ik denk dat jij ook voorbij gaat aan andere facetten van vooruitgang: je doelt specifiek op geheugen en/of processorkracht, maar denk je niet dat ook dataoverdracht sneller gaat worden? Denk dat dit eerder het geval zal zijn!

Maar als je dit voor elkaar krijgt: patenteren dit idee! Kan je de rest van je leven op de Bahama's gaan liggen .

[ Voor 9% gewijzigd door sjroorda op 17-11-2005 20:28 ]

[Aphelion]

snake903 schreef op donderdag 17 november 2005 @ 20:23:
Dan moet je een hash creeeren die 100% uniek is!

En ik weet niet of dat mogenlijk is

Inderdaad. Hier heb ik ook over na gedacht. Als je een exta, stel een integer meestuurt waarin staat: het bronbestand moet xx bytes lang zijn, een ministring met waarmee het bestand moet beginnen en een aantal xx bytes over hoe het bestand moet eindigen. Hier verklein je de kans al vrij veel mee. Je kan in het 'protocol' toch een hoop gegevens kwijt die maar een x aantal bytes in beslag nemen om aan te geven hoe het doelbestand opgebouwd moet worden. Een boolean voor tekst/binary zou bijv. gemakkelijk zijn om sneller tekst bestanden te achterhalen.

[XTerm]

Dit is wiskundig onmogelijk mijn beste

Wat wel kan is betere compressie, maar dat is meer een algoritmisch probleem en niet zozeer computerkracht gelimiteerd.

Wat ik over 20 jaar wel zie gebeuren is zo'n grote capaciteit aan bandbreedte dat je zomaal aan alles kan van eender waar.

[sjroorda]

XTerm schreef op donderdag 17 november 2005 @ 20:30:
Dit is wiskundig onmogelijk mijn beste

In principe kan het mogelijk zijn, als je kan garanderen dat je code uniek is, zoals bijvoorbeeld door alle mogelijkheden op de coderende computer te controleren (brute-force).

Kan trouwens nog best wel eens een interessant uitgangspunt zijn: de coderende computer doet veel werk, maar (daardoor?) hebben de decoderende computers minder te doen. Werkt ook zo bij bijvoorbeeld film-compressie en andere compressie-formaten: één keer veel werk verzetten, en de eindgebruikers kunnen met minder inspanning het origineel achterhalen.

[Nvidiot]

sjroorda schreef op donderdag 17 november 2005 @ 20:33:
[...]

In principe kan het mogelijk zijn, als je kan garanderen dat je code uniek is, zoals bijvoorbeeld door alle mogelijkheden op de coderende computer te controleren (brute-force).

Kan trouwens nog best wel eens een interessant uitgangspunt zijn: de coderende computer doet veel werk, maar (daardoor?) hebben de decoderende computers minder te doen. Werkt ook zo bij bijvoorbeeld film-compressie en andere compressie-formaten: één keer veel werk verzetten, en de eindgebruikers kunnen met minder inspanning het origineel achterhalen.

De hash kan alleen uniek zijn indien je de complete file (of een rar/zip/lossless ingepakte versie) verstuurt. Helaas.

[sjroorda]

Maar het gaat hier om een hash met toegevoegde informatie; in principe is het dan mogelijk, alleen vraag ik me af of de kosten in resources het ooit rendabel zullen maken...

[Gerco]

Dit klinkt als Jan Sloot compressie. Er is al honderden malen bewezen dat wat jij wilt niet mogelijk is. Dat betekent natuurlijk niet dat het plafond is bereikt kwa compressie, maar wat jij hier voorstelt is onmogelijk

Als je een hash van x bits hebt, zijn er oneindig veel bestanden die overeenkomen met die hash. Als je de lengte en een paar bytes van in de file erbij geeft, is er een grotere kans dat die hash + metadata 1 bestand uniek identificeert.

Helaas zal zo lang de hash een beperkte lengte heeft en de metadata niet het hele bestand beslaat altijd een kans zijn dat er een tweede bestand is wat aan dezelfde voorwaarden voldoet. Het is alleen van tevoren niet te voorspellen of en zo ja welke bestanden zullen matchen.

[ Voor 55% gewijzigd door Gerco op 17-11-2005 20:40 ]

[engelbertus]

ik zou zeggen dat het lariekoek is, een has is altijd data verilies, op dit moment kun je alleen opnieuw een hash laten berekenen van een bestand en kijken of die hetzelfde is als de oorspronkelijke hash, om de echtheid / correctheid van het bestand aan te tonen.
het is echter zo dat er eigenlijk oneindig veel strings zijn die de zelfde hash hebben.
de echte oorspronkelijke has dan weer terg rekenen vanaf een hash is zelfs op dit moment onmogelijk. vals spelen met rainbowtables is niet echt handig, je krijgt databases ewaarin je dus complete films moet opslaan, om een has te kraken, en vervolgens evengoed die hele film uit de database downloaden.

er is gewoon op dit moment geen manier om een hash terug te rekenen naar een oorspronkelijke hash, en dat is ook niet mogelijk.

het toevoegen van een extra informatie zou in mijn ogen zo giigantisch veel extra info opleveren, dat het simpel versturen van de film eenvoudiger is.

je zou in dat geval mischien ipv hashen, spreken over een compressie factor, die met betree technieken dan mpeg4 of divx, veel betere resultaten oplerveren met minder info dan wat jij voorstelt.

in de werelijkheid zijn decompressie algoritmes ook al een vorm van "hashing" immers het is slechts een techniek die door intensief rekenen de hoeveelheid informatie verkleint, terwijl hij toch uniek en kenmerkend blijft voor het oorspronkelijke bestand.

er zijn dan verschillende algoritmes. het een is goed om beeld informatie compacter op te slaan, de ander beter om video te comprimeren, en md5 is een techniek die een resultaat van een vaste lengte oplevert op zodanige wijze dat men nog steeds een realtie overhoudt tussen hash en data. met probleem, of de opzet juist, bij md5, is dat de omgekeerde berekening niet mogelijk is.
een collision berekenen is dan welliswaar misschien in de toekomst mogelijk, maar daarvan zijn er oneindig veel. met extra informatie kun je de beperken, maar dan moet je alsnog door blijven rekeken tot je alle hashes, hebt doorgerekend, of toevaig 1 bent tegengekomen die een film als resultaat heeft
stel een film is 600 mb en je geeft als extra voorwaarden aan de hash mee dat de film 600 mb is, en de eerste en laatste mb van de film. voor de overige informatie in de film geld dan dat er nog steeds oneindig veel mogelijke ingevoegde data is, zij het dan slechts, of nog steeds ) beperkt door 598^8*aantal karakters in de tabel, bits. dus een gigahoeveelheid mogelijkheden die nog steeds allemaal dmv trial and error moeten worden berekend. je zit dan net zo lang te wachten tot het raak s is dan dat de film duurde inclusief het on demand downloaden.

de bandbreedte zal denk ik niet de beperkende factor gaan wprden.

[Aphelion]

Ik kreeg van een kennis de volgende reactie:

Een interessant onderwerp, dat zeker. Leuk dat je er ideeën over uitwerkt.
Nieuw zijn je ideeën echter niet. Programma's als Citrix en het daarvan afgeleide Windows Terminal Server beperken al de datastroom en leggen wat meer belasting op de processor. In het verleden was de bandbreedte vaak de bottleneck bij data-uitwisseling. In onze huidige tijd verdrievoudigt de bandbreedte per jaar volgens de tweede wet van Negroponte. Voor 2010 zou dat een bandbreedte thuis van ca. 30 Gigabit per seconde betekenen. Is het dan nog interessant om over compressie van dataverkeer te denken? Je ziet dat ik een heel andere benadering van data-uitwisseling heb. Ik ga uit van de toepasbaarheid, voordat ik me over mogelijke technieken buig. Jij gaat uit van technische mogelijkheden en het gevolg daarvan. Ik denk dat mijn benadering wat moderner is. Waarschijnlijk zullen we in 2010 geen films meer downloaden i.v.m. het gebruik van streaming media, maar als we Negroponte mogen geloven, kost het downloaden van een film in 2010 nog geen drie seconden.
Nogmaals bedankt voor je constructieve reactie.

Ik zie inderdaad in dat de toekomst niet meer te maken heeft met snelheden die te traag gaan. Ik was er ook niet van op de hoogte dat Cintrix en Windows Terminal Server de zelfde techniek al gebruiken, alleen dan in mindere mate. De persoon in bovenstaande quote bekijkt echter mijn idee voor het verminderen van bandbreedte gebruik. Maar ik kijk ook verder, hoe met de opslag van gegevens. Ookal hebben we in de toekomst harddisks van een TeraByte. Als je met deze techniek en voldoende rekenkracht dan ook nog eens opslagruimte tot een minimum kan beperken zou het nogsteeds heel mooi zijn. Dan kan je op 1TB effectief door rekenkracht kwa gegevens een veelvoudige kwijt.

[CodeCaster]

Het is TeraByte, niet TerraByte.

Het mooiste zou gewoon zijn qua datacompressie dat het on-the-fly kan. Bijvoorbeeld dat je dualcore processor 1 core gebruikt voor (de-)comprimeren van inkomende en uitgaande gegevens.

Zoals al gezegd, een hash betekent dataverlies.

Je kunt wel met dataverlies werken en dan terug laten berekenen, zoals met .par bestanden. Dat je maar 80% downloadt van wat je wilt hebben, + 5% aan pariteitsdata, waaruit het originele bestand weer herberekend wordt.

[leuk_he]

Aphelion schreef op vrijdag 18 november 2005 @ 12:45:
Ik kreeg van een kennis de volgende reactie:
[...]


Ik zie inderdaad in dat de toekomst niet meer te maken heeft met snelheden die te traag gaan. Ik was er ook niet van op de hoogte dat Cintrix en Windows Terminal Server de zelfde techniek al gebruiken, alleen dan in mindere mate. .

Tja, data compressie is zeker al vaak toegepast. het wordt zelfs optioneel toegepast op de html documenten die je NU download. (check je profile maar eens hier op gzip). In lossless compressie zit nog maar een beperkte rek. Voor lossy compressie (films,plaatjes,geluid) zit nog wat meer rek omdat dit nu steeds beter begrepen wordt hoe mensen plaatjes interpreteren.

offtopic:
meer een W&L topic, maar de vraag is of er daar begrip is voor je helaas verkeerde begrip van compressie en hashing

[Verwijderd]

Je kunt wel met dataverlies werken en dan terug laten berekenen, zoals met .par bestanden. Dat je maar 80% downloadt van wat je wilt hebben, + 5% aan pariteitsdata, waaruit het originele bestand weer herberekend wordt.

correct me if i'm wrong maar hoe jij het zegt download ik maar 80% van bv. mijn film +5% extra data
vervolgens gaat mijn pc de rest van de film berekenen.

volgens mij klopt dit niet maar werkt het zo:

de film is verdeeld over 50 .par files
iedere par file bevat niet 2% van de data maar 3%.
ik download alle files maar 4 par files zijn corrupted of heb ik niet. geen probleem want de data van die 4 kapotte files zit ook verdeeld over een aantal andere par files die ik wel heb

kortom: als ik 80% van de par's download heb ik eigenlijk toch 100% van de film gedownload
dit is dus een beetje het RAID striping+mirroring idee (weet ff het nummer niet zeker maar volgens mij is het RAID 0+1) (3 schijven, 2 schijven krijgen het halve bestand, 1 schijf het hele bestand)


maar goed, ik denk (weet eigenlijk wel zeker) dat jou idee niet te realiseren is. mijn onderbouwing hiervoor is eigenlijk al aanbod geweest dus dat ga ik niet meer herhalen.

ps. zie ook de nieuwspost die gister (toch?) op tweakers is geweest over de MD5 hash. dit is redelijk relevant hieraan

[Verwijderd]

Move NT > WL

[Confusion]

Aphelion schreef op donderdag 17 november 2005 @ 20:19:
Over 10 jaar is een computer waarschijnkijk snel genoeg om een document van 100mb in enkele seconden te bruteforcen. Je download alleen de hash

Laten we er even vanuit gaan dat we over de zo goed mogelijk gecomprimeerde versie van het bestand spreken (wat hier stond klopte niet). Dan moet de hash minimaal even groot zijn als dat bestand, anders zou hashen een effectievere compressiemethode zijn. Vervolgens zou het bruteforcen van de hash sneller moeten zijn dan het decomprimeren van het bestand. Dat lijkt me sterk, want het eerst zou juist niet bedoeld zijn om het bestand te kunnen reconstrueren. De best geschikte hash is dan de gecomprimeerde versie van het bestand.

Je bent in de war met de mogelijkheid om een bestand met een paar tekens zo aan te passen dat het dezelfde hash krijgt als een ander bestand. Een bestand is echter niet uit die veel kortere hash terug te rekenen. Dat gaat tegen de wetten van dit universum in .

[ Voor 4% gewijzigd door Confusion op 18-11-2005 16:20 ]

[Verwijderd]

Als je een unieke hash wil die 100 procent zeker te herleiden is tot 1 specifiek bestand, dan moet die hash + extra informatie ongeveer even groot zijn als je oorspronkelijke bestand.

Deze methode werkt alleen als je een manier hebt om snel alle mogelijke bestanden te bepalen die de hash opleveren, en en manier om daar de juiste uit te vissen op basis van de inhoud. Dat betekent dat je moet weten wat er in het bestand zit. Als je een text file verstuurt, kan je alle collisions die geen leesbare tekst bevatten zo afschrijven. Waarschijnlijk is er dan zelfs voor een relatief kleine hash maar 1 leesbare tekst. Dat kan dus wel tot compressie leiden. Op dezelfde manier zou je andere documenten, MP3, video, executables en andere bestanden met een interne structuur kunnen comprimeren.

Maar goed, ik betwijfel of je winst behaalt ten opzichte van de huidige compressie, die ook al gebruik maakt van de interne structuur van de te comprimeren bestanden. En de hoeveelheid benodigde rekenkracht zie ik ook in de toekomst nog niet zomaar beschikbaar komen.

[MSalters]

Kan niet, Pigeonhole principle. (Als je N duiventillen hebt, en N+1 duiven, dan heb je ongeacht de verdeling een duif teveel. Zelfde met bits: als je N bits in je hash hebt, en N+1 bits informatie, dan past het niet)

[XTerm]

Verwijderd schreef op vrijdag 18 november 2005 @ 22:36:
Als je een unieke hash wil die 100 procent zeker te herleiden is tot 1 specifiek bestand, dan moet die hash + extra informatie ongeveer even groot zijn als je oorspronkelijke bestand.

Deze methode werkt alleen als je een manier hebt om snel alle mogelijke bestanden te bepalen die de hash opleveren, en en manier om daar de juiste uit te vissen op basis van de inhoud. Dat betekent dat je moet weten wat er in het bestand zit. Als je een text file verstuurt, kan je alle collisions die geen leesbare tekst bevatten zo afschrijven. Waarschijnlijk is er dan zelfs voor een relatief kleine hash maar 1 leesbare tekst. Dat kan dus wel tot compressie leiden. Op dezelfde manier zou je andere documenten, MP3, video, executables en andere bestanden met een interne structuur kunnen comprimeren.

Maar goed, ik betwijfel of je winst behaalt ten opzichte van de huidige compressie, die ook al gebruik maakt van de interne structuur van de te comprimeren bestanden. En de hoeveelheid benodigde rekenkracht zie ik ook in de toekomst nog niet zomaar beschikbaar komen.

Proficiat je hebt net compressie met data verlies heruitgevonden !

[Brent]

Met een hash, een precieze filesize en een supercomputer kun je best ver komen denk ik...

Maar data lossy comprimeren en met behulp van de hash eea weer opbouwen, klinkt zo gek nog niet.

[Verwijderd]

Breepee schreef op vrijdag 18 november 2005 @ 22:47:
Met een hash, een precieze filesize en een supercomputer kun je best ver komen denk ik...

Maar data lossy comprimeren en met behulp van de hash eea weer opbouwen, klinkt zo gek nog niet.

Tja als je alle mogelijkheden gaat maken en dan kijkt welk bestand leesbaar is... lekker nuttig.

Er zijn zoals al eerder aangegeven heel veel mogelijkheden voor 1 hash.

[Voutloos]

MSalters schreef op vrijdag 18 november 2005 @ 22:42:
Kan niet, Pigeonhole principle. (Als je N duiventillen hebt, en N+1 duiven, dan heb je ongeacht de verdeling een duif teveel. Zelfde met bits: als je N bits in je hash hebt, en N+1 bits informatie, dan past het niet)

Precies, heb ik ook vaak genoeg gezegd in Jan Sloot achtige topics.

Breepee schreef op vrijdag 18 november 2005 @ 22:47:
Met een hash, een precieze filesize en een supercomputer kun je best ver komen denk ik...

Een precieze filesize helpt nog niet veel. Met N bits heb je 2x zoveel mogelijkheden als N-1 bits, etc. Als je dat doorrekent komt je erachter dat de filesize weten slechts de helft van de mogelijke bronstrings scheelt. Als er bij geen enkele hash gegokt mag worden wat de file was, moet elke hash uniek zijn -> pigeon hole principe.

Maar data lossy comprimeren en met behulp van de hash eea weer opbouwen, klinkt zo gek nog niet.

Klinkt wel heel erg gek, hashen != comprimeren op een reversible manier. Lossy kan op heel veel manieren. Captain Proton geeft een leuke optie om valse bronstrings weg te strepen, maar om het goed te doen met een algemeen protocol dat alle mogelijke files ondersteund ga je nog veel meer metadata nodig hebben, zoveel zelfs dat hash+metadata geen steek kleiner is.

Pas als iemand 4 dingen kan benoemen met alleen één 0 of 1 en dat ook kan uitleggen kijk ik weer naar een Jan Sloot fantasystory als dit.

[ Voor 12% gewijzigd door Voutloos op 18-11-2005 23:03 ]

[Verwijderd]

Proficiat je hebt net compressie met data verlies heruitgevonden !

Even aannemende dat deze post aan mij gericht was: waar zie je dataverlies? Ik heb juist compressie zonder dataverlies heruitgevonden, vergelijkbaar met zip en dergelijke. Met de methode die ik beschreef kan je de oorspronkelijke file bit voor bit weer reconstrueren uit de hash. De huidige compressiealgoritmen zullen alleen een stukje efficienter zijn, maar het was dan ook niet bedoeld als onderzoeksvoorstel ofzo Ik wilde slechts illustreren waarom het idee van de TS niet werkt en wat je moet doen om dat wel te laten werken...

En MSalters: Ik begrijp niet geheel wat je bedoelt. Een hash is korter dan de file waar die uit gemaakt wordt: Ik zie niet waarom het onmogelijk zou zijn een algorithme (desnoods een brute-force reverse algorithme dat simpelweg voor alle mogelijke bestanden van die lengte de hash berekent, dat mijn voorbeeld in de praktijk niet werkt is iedereen het denk ik wel over eens) te bedenken dat alle files genereert met een bepaalde lengte die die hash opleveren tijdens compressie. Zie niet in waarom dat niet zou kunnen. Daarna gebruik je de extra informatie over het bestand in kwestie (bijvoorbeeld: het is een engelse tekst) om te bepalen hoeveel bestanden daaraan voldoen (qua woorden, qua grammatica).

Om te encoderen, bereken je van je bestand een serie hashes via verschillende algoritmen en controleer je door gebruik te maken van het algorithme dat ik net beschreef wat de kortste hash is die nog precies 1 engelse tekst oplevert, naast uiteraard een eindeloze serie niet-engelse hashes. Die hash verstuur je of sla je op. Bij decompressie genereer je uit de hash weer alle mogelijke bestanden en zoek je tot je die ene engelse tekst weer hebt.

Deze compressiemethode werkt omdat een voor mensen nuttig bestand (behalve een bestand met random nummers) altijd een interne structuur zal hebben. Als die structuur bekend is, is het mogelijk daarvan gebruik te maken om het bestand in te korten. Dat is wat zip doet, en dat is ook wat mijn algorithme doet. Al is zip dus een stuk beter

maar om het goed te doen met een algemeen protocol dat alle mogelijke files ondersteund ga je nog veel meer metadata nodig hebben, zoveel zelfs dat hash+metadata geen steek kleiner is.

Bij alle mogelijke files uiteraard wel, maar in 4 bytes kan je 2³² fileformats encoderen, en daarmee heb je waarschijnlijk alle mogelijke file formats op deze planeet van nu en de komende 100 jaar wel te pakken

[ Voor 11% gewijzigd door Verwijderd op 18-11-2005 23:16 ]

[Voutloos]

Verwijderd schreef op vrijdag 18 november 2005 @ 23:11:
Bij alle mogelijke files uiteraard wel, maar in 4 bytes kan je 2³² fileformats encoderen, en daarmee heb je waarschijnlijk alle mogelijke file formats op deze planeet van nu en de komende 100 jaar wel te pakken

De definitie van een format telt imo ook mee als metadata. Format is dan altijd flink veel meer dan de (bijvoorbeeld) 4 bytes.

[Zoijar]

Sowieso is de benodigde rekenkracht te groot. Een file van 100MB brute forcen? 256^(104857600) mogelijke files? Dat lukt je nog niet als je elk deeltje in het universum als parallele computer gebruikt...

( je kan dit soort dingen trouwens ontkrachten met kolmogorov complexiteit. De complexiteit van een string, de lengte van het kortste programma dat de string genereert, zijn specifieke boven en onder grenzen voor. Funtie zelf is niet berekenbaar. Maar dat gaat buiten dit topic. In ieder geval voor iedereen die lossless compressie wil verbeteren: er zijn wiskundige grenzen aan compressie zonder data verlies. Die grenzen kan je niet omheen, ook niet door heel slim te zijn)

[ Voor 55% gewijzigd door Zoijar op 18-11-2005 23:36 ]

[Johnny]

Ik vind het raar dat je er vanuit gaat dat de hoeveelheid processorkracht, en de opslag nog explosief blijven doorgroeien maar de bandbreedte hetzelfde blijft en/of minder wordt.

Je kan zonder probleem in seconden gigabytes aan data downloaden, maar waarom zou je extra kopieen (bij jezelf) gaan maken als het origineel (op de server) altijd direct beschikbaar is?

Veruit de meeste media zal direct worden gestreamd, video-on-demand enzo, maar ook dingen zoals (virtual reality) games en applicaties zijn gewoon altijd berschikbaar ongeacht welk apparaat je gebruikt of waar je bent.

[Confusion]

Verwijderd schreef op vrijdag 18 november 2005 @ 23:11:
Een hash is korter dan de file waar die uit gemaakt wordt: Ik zie niet waarom het onmogelijk zou zijn een algorithme (desnoods een brute-force reverse algorithme dat simpelweg voor alle mogelijke bestanden van die lengte de hash berekent, dat mijn voorbeeld in de praktijk niet werkt is iedereen het denk ik wel over eens) te bedenken dat alle files genereert met een bepaalde lengte die die hash opleveren tijdens compressie.

Dat zijn tenminste 2 mogelijke files voor elke bit die de hash in lengte verschilt met de lengte van het (maximaal gecomprimeerde) bestand en dat loopt dus enorm snel op. Een hash van 99 Mb voor een bestand van 100 Mb komt dan al met 2^(1Mb) aan bestanden overeen; dat is een absurde hoeveelheid: dat zal nooit een efficientere methode opleveren. Als je dan ook nog voldoende lange strings moet meesturen om uit die 2^(1Mb) bestanden de goede uit te zoeken, dan moeten die strings precies de resterende informatie aanvullen, want dat is het enige dat uniek is.

[Zoijar]

Johnny schreef op vrijdag 18 november 2005 @ 23:50:
Ik vind het raar dat je er vanuit gaat dat de hoeveelheid processorkracht, en de opslag nog explosief blijven doorgroeien maar de bandbreedte hetzelfde blijft en/of minder wordt.

Je kan zonder probleem in seconden gigabytes aan data downloaden, maar waarom zou je extra kopieen (bij jezelf) gaan maken als het origineel (op de server) altijd direct beschikbaar is?

Veruit de meeste media zal direct worden gestreamd, video-on-demand enzo, maar ook dingen zoals (virtual reality) games en applicaties zijn gewoon altijd berschikbaar ongeacht welk apparaat je gebruikt of waar je bent.

Op zich is het idee niet raar. De data doorvoer in computers is _de_ bottleneck op het moment, en hoogst waarschijnlijk in de toekomst tenzij iemand met iets revolutionairs komt. Daarom zien we ook een switch tussen data doorsturen en data on-demand uitrekenen op lokatie. Als voorbeeld is het voor een GPU nu al makkelijker om bepaalde dingen zelf steeds opnieuw uit te rekenen (bv normalen oid) dan dat de CPU deze beschikbare informatie op de bus zet naar de GPU. Data doorvoer is een bottleneck, het is sneller om data opnieuw uit te rekenen. Naar verwachting wordt dit alleen maar erger in de toekomst. Netwerken kunnen nog wel groeien tot enkele GB/s, maar dan houdt het op. (graphics) processoren kunnen daarentegen in parallel al meerdere teraflops halen. Simpelgezien kan je dus een gigabyte doorsturen in de tijd dat je een terabyte kan berekenen.

[Aphelion]

Zoijar schreef op zaterdag 19 november 2005 @ 03:19:
[...]

Op zich is het idee niet raar. De data doorvoer in computers is _de_ bottleneck op het moment, en hoogst waarschijnlijk in de toekomst tenzij iemand met iets revolutionairs komt. Daarom zien we ook een switch tussen data doorsturen en data on-demand uitrekenen op lokatie. Als voorbeeld is het voor een GPU nu al makkelijker om bepaalde dingen zelf steeds opnieuw uit te rekenen (bv normalen oid) dan dat de CPU deze beschikbare informatie op de bus zet naar de GPU. Data doorvoer is een bottleneck, het is sneller om data opnieuw uit te rekenen. Naar verwachting wordt dit alleen maar erger in de toekomst. Netwerken kunnen nog wel groeien tot enkele GB/s, maar dan houdt het op. (graphics) processoren kunnen daarentegen in parallel al meerdere teraflops halen. Simpelgezien kan je dus een gigabyte doorsturen in de tijd dat je een terabyte kan berekenen.

Ik geef alleen een reactie op bovenstaande post. Dank iedereen voor het medenken tot zo ver. Het is leuk om te zien hoe de meningen hierover verschillen; mensen die wiskundig grenzen stellen en mensen die nadenken in de vorm van 'stel dat dit kan, dan...'.

Datadoorvoer zal ook in mijn ogen de grootste bottleneck zijn. Maar ik zag deze fantasiemethode ook als een leuke oplossing voor het vermenigvuldigen van je opslagcapaciteit. Als je voldoende rekenkracht hebt om dingen te herstellen adhv wat input is er ook geen noodzaak meer om uitwerkingen te bewaren op een harddisk maar kan je alles onthefly berekenen.

[Zoijar]

Aphelion schreef op zaterdag 19 november 2005 @ 11:42:
Ik geef alleen een reactie op bovenstaande post. Dank iedereen voor het medenken tot zo ver. Het is leuk om te zien hoe de meningen hierover verschillen; mensen die wiskundig grenzen stellen en mensen die nadenken in de vorm van 'stel dat dit kan, dan...'.

Datadoorvoer zal ook in mijn ogen de grootste bottleneck zijn. Maar ik zag deze fantasiemethode ook als een leuke oplossing voor het vermenigvuldigen van je opslagcapaciteit. Als je voldoende rekenkracht hebt om dingen te herstellen adhv wat input is er ook geen noodzaak meer om uitwerkingen te bewaren op een harddisk maar kan je alles onthefly berekenen.

Dat dingen on the fly uitrekenenen en niet opslaan een goed idee is blijkt wel uit de quantum mechanica Althans, zo zie ik het universum nog steeds. Een tweede voordeel is nl. dat je min of meer oneindige datasets kan gebruiken in eindige ruimte/tijd. Maar de manier van compressie met een hash is theoretisch niet mogelijk, en ook waarschijnlijk niet de slimste/beste manier. Compressie zonder verlies van data zit voor zover ik weet redelijk dicht bij de haalbare grenzen. Waar naar gekeken moet worden is de compressie met data verlies; ie, wat is nou echt fundamentele informatie. Zo kan je een matrix bv representeren met slechts een aantal belangrijke getallen, die het meest toevoegen (svd), of een signaal met een aantal belangrijke frequentie componenten etc. Daar moet je nieuwe compressie technieken vooral zoeken denk ik: alleen de kern van de data doorsturen.

[Verwijderd]

Ik zet mijn geld op beesten van fileservers. Machines met enorme opslagcapaciteit, maar eigenlijk vooral snelle schijftoegang en een enorm hoge uploadsnelheid. Het verschil tussen leessnelheid van een harde schijf en de bandbreedte van de internetverbinding wordt kleiner. En dan gaat het om een factor van hooguit enkele duizenden.

Als je processor snel genoeg moet zijn om in acceptabele tijd een file te reconstrueren uit een hash, waarbij je het merendeel van de gegevens NIET download, dan heb je het over bizar hoge snelheden. Op dit moment is het al haast belachelijk om reeksen van 128 bits te gaan bruteforcen, omdat dat al in de buurt komt van de lengte van de hash. Laat staan als je het over reeksen van 70 miljard bits hebt (een DVD bijvoorbeeld).

En even voor de goede orde, dat is dus inderdaad exponentieel. 2^70000000000 is belachelijk veel.

[Grijze Vos]

Wat ik in de TS zijn voorbeeldje niet snap is waarom die fileserver de grote bestanden wil hebben. Als de hash voldoende zou zijn om de data te reconstrueren hoeft dat ding zelf toch ook alleen die hashes op te slaan.

En verder is er al genoeg over gesproken, het is gewoon wiskundig onmogelijk.

[Verwijderd]

Je wilde het probleem met collisions oplossen door een kleine hoeveelheid van het originele bestand mee te sturen ter controle. Het enige wat je daarmee bereikt is het weten dat er in de controledata geen collisions zitten. Op alle andere plekken kunnen nog steeds collisions zitten.

Als je toch uitgaat van praktisch onbeperkte verwerkingskracht en wel een zeer beperkte bandbreedte is het waarschijnlijk verstandiger om de data als getal te bekijken, en de zender te laten uitrekenen in welke wiskundige formule het getal de definieren is. Met trial en error voor mijn part, laat de zender de data door een getal delen, begin bij 2, ga door tot data/getal klein genoeg is, "getal" ook klein genoeg is, en je de data dus kunt formuleren als: (data/getal) * getal.
Natuurlijk zou dat een te simpele formule zijn, vrij weinig data waarbij dit werkelijk ruimte zou besparen.

Met ingewikkelder formules ongetwijfeld wel. Natuurlijk, het duurt even, maar we gingen er van uit dat processoren enorm snel werden en bandbreedte afschuwelijk bleef.

[Verwijderd]

Wie weet vind men iets uit waardoor je gewoon een file draadloos van hier (BeNeLux) naar China kan sturen? Wie weet hoe snel het internet zal zijn binnen enkele jaren?

[eamelink]

Verwijderd schreef op donderdag 24 november 2005 @ 04:23:
Met ingewikkelder formules ongetwijfeld wel.

Dat denk ik eigenlijk niet. Als je alle mogelijke data wilt kunnen representeren met een formule zal dat voor een paar simpele gevallen best lukken, maar uiteindelijk groeit de complexiteit van de formule net zo hard als de data zelf .

Je kan ook voor een willekeurige bitreeks uit gaan zoeken vanaf welke decimaal die reeks voorkomt als subreeks van de decimalen van pi. Dan hoef je om al die data terug te halen maar twee getallen op te slaan : De decimaal van pi waar de reeks begint, en de lengte.

Helaas zal dat eerste getal een heel stuk groter zijn dan de originele data

[Spruit_elf]

eamelink schreef op donderdag 24 november 2005 @ 22:08:
[...]

Dat denk ik eigenlijk niet. Als je alle mogelijke data wilt kunnen representeren met een formule zal dat voor een paar simpele gevallen best lukken, maar uiteindelijk groeit de complexiteit van de formule net zo hard als de data zelf .

zoizo is dat onmogelijk want als je daardwerkelijk alle data wil bevatten dan moet die formule ook zichzelf bevatten, en nog veel meer en dan kom je op tereinen zoals http://www.miskatonic.org/godel.html

[Verwijderd]

mrcactus schreef op zondag 27 november 2005 @ 20:46:
zoizo is dat onmogelijk want als je daardwerkelijk alle data wil bevatten dan moet die formule ook zichzelf bevatten, en nog veel meer en dan kom je op tereinen zoals http://www.miskatonic.org/godel.html

Dat is niet erg als de beschrijving of het algoritme van de formulie veel kleiner is dan de data die hij representeert.

Het is bijvoorbeeld een peuleschilletje om een formule of algoritme te maken die alle mogelijke data output. Dus achter elkaar alle mogelijke streams van 1 bit, dan van 2, dan van 3, etc. Ook bij pi is het best mogelijk dat alle mogelijke eindige decimale rijen erin voorkomen (is nog geen zekerheid over) en een formule voor pi is klein.

Het probleem is dat je, om de gewenste data of een bepaald bestand weer uit (de output van) zo'n formule te halen, méér data nodig hebt om het bestand te indexeren of identificeren dan het bestand zelf oorspronkelijk kostte.

[Verwijderd]

Aphelion schreef op zaterdag 19 november 2005 @ 11:42:
Ik geef alleen een reactie op bovenstaande post. Dank iedereen voor het medenken tot zo ver. Het is leuk om te zien hoe de meningen hierover verschillen; mensen die wiskundig grenzen stellen en mensen die nadenken in de vorm van 'stel dat dit kan, dan...'.

Als je denkt dat er nog steeds mogelijkheden zijn, lees dan een aantal van bovenstaande reacties nog even goed door. Het kan écht niet

Sterker nog, ik kan je een bestand geven van 100 KB waarvan ik van te voren kan garanderen dat je het niet tot minder dan 99 KB gecompressed krijgt noch kunt verzenden met minder dan 99 KB aan traffic, ongeacht je compressie/encryptie/hasing/transfer methode.

[leuk_he]

Verwijderd schreef op maandag 28 november 2005 @ 09:57:
[...]
Sterker nog, ik kan je een bestand geven van 100 KB waarvan ik van te voren kan garanderen dat je het niet tot minder dan 99 KB gecompressed krijgt noch kunt verzenden met minder dan 99 KB aan traffic, ongeacht je compressie/encryptie/hasing/transfer methode.

Waarom 99? waarom geen 100? ben je niet helemaal zeker?

[Rey Nemaattori]

snake903 schreef op donderdag 17 november 2005 @ 20:23:
Dan moet je een hash creeeren die 100% uniek is!

En ik weet niet of dat mogenlijk is

Een unieke hash zou minstens even langm oetne zijn als het bron bestand. Tenslotten zijn er 2^1024 verschillende documeten mogelijk van 1kb(eigenlijk meer byte = 8bits), terwijl een hash van 8 alfanummerieke karakters slechts 8^36 mogelijk heden heeft. Een aantal van die documenten krijgt dus eenzelfde hash, de truuk is natuurlijk dezelfde hash dermate vaak voorlaten komen dat het vinden van een 2e doc met dezeflde hash langer duur dan dat de inhoud van zo'n document waarde heeft.

Bijvoorbeeld, als ik in oorlogtijd een docuemnt heb met de posities van mijn stellingen voor die dag en waar ze morgen heen gaan, is dat document overmorgen bijwijze van spreke nutteloos(niet helemaal natuurlijk, je kutn een route uitstippelen, aan de hand van wat je weet). Zou de vijand een week over doen om mijn encryptie te kraken, tja leuk en aardig, maar dan is het document dus waardeloos...

Het doel van necryptie is dan ook niet iets onkraakbaar maken, maar het kraken langer te laten duren dan dat de informatie geldig is. Als jij je php sessie met md5 beveiligd, en je stelt de max. sessie duur op een halfuur, zal niemand binnen die tijd de juiste hash kunnen genereren...dus is je beveiliging waterdicht...

[ Voor 16% gewijzigd door Rey Nemaattori op 28-11-2005 10:48 ]

[Verwijderd]

leuk_he schreef op maandag 28 november 2005 @ 10:37:
Waarom 99? waarom geen 100? ben je niet helemaal zeker?

Ik kan natuurlijk niet uitsluiten dat hij met een compressie algoritme aankomt wat dit bestand toevallig nét iets kleiner maakt.

Maar dat zou dan wel een erg lucky shot zijn, dus vooruit, ik durf ook wel te wedden dat het bestand zelfs geen bit kleiner wordt.

[Verwijderd]

Verwijderd schreef op maandag 28 november 2005 @ 11:05:

Ik kan natuurlijk niet uitsluiten dat hij met een compressie algoritme aankomt wat dit bestand toevallig nét iets kleiner maakt.

Maar dat zou dan wel een erg lucky shot zijn, dus vooruit, ik durf ook wel te wedden dat het bestand zelfs geen bit kleiner wordt.

Ga dan niet op de toer van de kansberekening, en houd het algemener. Laat iemand maar met een algoritme komen waarmee je ¹een willekeurige bitreeks kunt comprimeren tot een minder lange reeks.

Die nieuwe reeks moet (volgens uitgangspunt ¹) uiteraard ook weer te comprimeren zijn met hetzelfde algoritme. En het resultaat daarvan weer. En op een gegeven moment moet je op een niveau komen waarbij je moet uitleggen hoe je een DVD'tje in 1 of 2 bits kunt opslaan. Onzin dus.