2

Background

Tertiary to this question, I have been building my own imageboard that prevents [for example] duplicate images from being downloaded again and again on behalf of the client. How I do this, is that I keep all files in a database with a key being a hash of the file. The client sees the hash, and first checks its database to see if it has been downloaded before actually making a request. Similarly for my server; I also prevent duplicate uploads by having the client send me the hash first.

I am expanding a more general purpose networking library for downloading files from the web, and to my dismay; I discovered that not all servers will supply me with some sort of hash.

Question

In an effort to de-duplicate downloads, and to continue partial downloads in which their url has changed, is there a way to reliably fingerprint a file from its headers and url?

Just taking an example here, of a plain HEAD request

QVariant reply->header( QNetworkRequest::ContentLengthHeader )
int
44374

QUrl url
scheme()   : https
userName() : NULL
password() : NULL
host()     : i.imgur.com
port()     : -1
path()     : /oEdf6Rl.png
fragment() : NULL
query()    : NULL
https://i.imgur.com/oEdf6Rl.png

QNetworkReply* reply

Connection
keep-alive

Content-Length
44374

Last-Modified
Sun, 21 Feb 2021 15:14:36 GMT

ETag
"83c16cca4ee371145485130383104315"

Content-Type
image/png

cache-control
public, max-age=31536000

Accept-Ranges
bytes

Date
Fri, 26 Feb 2021 04:14:22 GMT

Age
392375

X-Served-By
cache-bwi5134-BWI, cache-yul12821-YUL

X-Cache
HIT, HIT

X-Cache-Hits
1, 2

X-Timer
S1614312862.217094,VS0,VE0

Strict-Transport-Security
max-age=300

Access-Control-Allow-Methods
GET, OPTIONS

Access-Control-Allow-Origin
*

Server
cat factory 1.0

X-Content-Type-Options
nosniff

NoError
Unknown error

The only things that seem static here, are the Mime Type, and the file size. One thing I would be willing to do is do a Accept-Ranges Download of certain bits, as I have found most servers do support this header, and from there; create a hash of the corresponding bytearray, and fingerprint it that way.

However, I am skeptical whether this would work reliably, especially concerned with something like two image frames that are nearly identical, but are in fact, not.

Am I pursuing a lost cause here? Or is there a reasonable way to fingerprint a file hosted on the web, without having to fully download it?

I'd like to do this with any file above 1mb large, because I have an exceptionally slow connection at times. Thanks.

5
  • 1
    Are a photograph, the same photo cropped by a few pixels and the same photo stored in a different format (e.g. JPG vs PNG) duplicate images for your software or not? Simple hashing of the file contents will indicate they are different, but people viewing them will say they are the same. Feb 26, 2021 at 7:02
  • 1
    There is no standard for this. Quaternary to the question, learn about the Armstrong Condenser (I'm taking the liberty to coin that term, after all, it likely is a necessary step before we can make a Matrioshka brain). Oh, wait, this is not worldbuilding.stackexchange.com. See also Content-addressable memory.
    – Theraot
    Feb 26, 2021 at 7:20
  • @BartvanIngenSchenau No different containers/MIME types and different compression methods etc of the same photo I definitely consider to be different files, especially if the file size is different. I am not looking to take on the arduous task of creating an identical fingerprint for a jpg and a png, I just used two images being nearly identical as being a possible and likely way that two files could end up having the same filesize, as well as the same byte array for say 99% of the file.
    – Anon
    Feb 26, 2021 at 7:24
  • @Theraot do you mind expanding on your comment there? Regarding Content-Addressable memory; its a fairly broad topic, and going down the road brings up some interesting theories, althoug probably none which solve my problem of getting a fingerprint of the file before the download.
    – Anon
    Feb 26, 2021 at 8:16
  • 4
    @Akiva I don't think you are going to have a neat solution to your problem. At least not without the server collaborating. At least you need to create or extend a protocol to talk with the collaborating server. Without server collaboration, you may, for example, have a server download the content and hash it, and then the client can talk to that other server... That way you prevent the client having to download the contents if it is duplicate. Then that server you set up has all the cache problems. We can also imagine a torrent-like solution that distributes this task in a decentralized way.
    – Theraot
    Feb 26, 2021 at 8:23

2 Answers 2

1

The only way to definitively state that two files are identical is to compare every single byte of their contents.

Every operation where you represent the file with fewer bits that its actual contents, be it a size-compare or a fingerprint/hash value, will result in the risk that two different files end up with the same size/fingerprint/hash. Those techniques are useful to classify files as "definitively different" or "possibly identical", but you can't get a guarantee they are identical.

If you are willing to accept/assume that each URL refers to a different file, then you can use the HTTP cache invalidation mechanisms to determine if you need to re-download a file you previously downloaded from a given URL.

8
  • Not all applications require this level of rigor. If it's merely for caching purposes, simply sampling the beginning of a file might do. After the first 100 bytes or so, the likelihood of a photographic file being different from another becomes vanishingly small. Feb 26, 2021 at 15:18
  • @RobertHarvey Wouldn't that depend heavily on the file contents and format? The OP seems to be asking about general deduping of arbitrary files. The possibility of of two files that are identical in a portion and different for the rest (a document that's been copied and added to, and two memes using the same image, etc) seems hard to exclude. If any of them are encoded in a format where the identical portion is all that's represented in the first 100 bytes (which is obviously possible for things like bitmaps and text files), then "vanishingly small" seems pretty overconfident to me.
    – Ben
    Feb 26, 2021 at 22:35
  • The OP states that their application is an "image board." My point is, depending on the use case, you may not need perfect fidelity. Feb 26, 2021 at 22:37
  • @RobertHarvey, maybe "possibly equal" for some confidence level in possibly is good enough for the OP. I don't know what confidence level the OP wants to have. Feb 27, 2021 at 12:28
  • The proof for this is also rather simple if I remember correctly. Essentially, it is just a formal way of saying "if you base your decision on a subset of the bytes, then you cannot detect a difference in the bytes you didn't look at." Feb 27, 2021 at 19:16
0

The "Etag" header could be used for this purpose. It's supposed to tell intermediate caches when a value has changed. If you request URL X and get Etag Y, then later request the same URL and get a different Etag Z, then it's probably changed. If you get the same Etag you don't need to re-download it.

Across different URLs, there's just no guarantee. You can't even be sure that the same URL will give you the same image every time.

2
  • Etag isn't exactly common though is it? And not to mention that each server has its own "ETag" type of thing, if any, some even providing hashes? Finally; the same file from two different servers will not be detected as duplicates..
    – Anon
    Feb 26, 2021 at 16:00
  • 1
    @Akiva If the Etag returned by an url changed, the contents changed. There is no guarantee of two different urls that have the same contents having the same Etag. And yes, some servers will use some Hash or HMAC for Etag, either of the contents or simply of the timestamp of the modification. No idea how common those are.
    – Theraot
    Feb 27, 2021 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.