The classical solution is using the Merkle-Tree. To use the Merkle-Tree for uploading, the client forms the Merkle-Tree and calculates the hashes, and sends you the root hash in advance in a secure channel with a digital signature.
In the Merkle Tree, the data (chunk) can arrive at the server in random order with the sibling hashes of the path from the data to the root. The server can use the root hash and the data and sibling hashes to check that the data is valid.
This will increase the bandwidth with
O(log n) where
n is the number of parts. With MD5 it will be
128*log n ( The
log n is used for the height of the tree).
For example for a
1GB file, with each part is
1MB and using a
32B Hash function, like SHA256, for this the client needs to store 64KB hash values and for sending a
1MB chunk with a 320KB hash data will be transmitted and the overhead of the transfer will be
The cost of verifying for each chunk will be
O(log n), and remember the Cryptographic hash functions are very fast.
and don't use MD5 it is no longer considered to be secure Cryptographic hash function, rather prefer at least SHA256 or use the Blake2 which has speed records. There are also parallel hashes like ParallelHash of SHA3 and the Blake3. This can fasten the calculations whenever the parallelization provides benefits.
For a nice and comprehensive guide to how the Merkle-Tree works see Squeamish Ossifrage' answer on Cryptography.SE