Yes, online storage services do store a checksum of the files. They can use that internally to periodically scrub their stored data. For example, if S3 has stored 3 copies of your file, they can use the hash to distinguish good and bad copies, and replace bad copies. For erasure-coded services like Backblaze B2, they can reconstruct a file using any 17 of 20 erasure segments, so with a known checksum they can figure out which segment is bad, delete it, and use the other segments to generate a replacement. I was told by Backblaze that they do periodically scrub B2 files.
HashBackup (I'm the author) has a lot of ways to verify backups. For B2 uploads, it generates a SHA1 hash before sending the data, stores that in a local database, sends the data with the hash, B2 generates an independent hash of the data, and compares it to the one HB sent. If there is a mismatch, an upload error occurs and the upload is retried.
On download, B2 sends the data and SHA1 hash (I'm assuming it verifies the hash during erasure reconstruction also), HB generates a SHA1 hash for the received data, verifies it against the SHA1 B2 sent, and verifies it against the SHA1 stored when the file was uploaded.
After the upload, files can be verified by:
- downloading the complete file as above, then verifying every block in the file
- getting the file size and SHA1 hash from B2 and verifying those against the local database (no data download)
- downloading N random samples from each file and verifying the block-level SHA1 for each sample
- downloading a small percentage of the files every day to verify the backup over time (this can be done with whole files or random samples)
If a problem is detected and you have other copies of the backup on another storage service or locally, HashBackup's selftest will fetch all copies of a file to reconstruct the original backup data to correct any errors, then upload the corrected file to all destinations.