Checksums

A checksum is a small value computed from a block of data and kept alongside it, so whoever reads the data later can recompute it and notice if even one bit changed by accident. It turns silent corruption (a flipped bit in a router’s memory, a disk that writes to the wrong sector, a truncated upload) into a loud, retryable error. It detects damage but does not repair it, and an ordinary checksum does nothing against someone who changes the data on purpose.

Picture it first: the band on a bundle of notes

A cash van carries bundles of ₹500 notes from a currency chest to bank branches. Each bundle wears a paper band printed “100 notes · ₹50,000”. At the branch a clerk runs the bundle through a counting machine. If the machine says 99, something went wrong on the way, so the branch refuses the bundle and asks for another.

Notice what the band can and can’t do:

• It detects a problem but can’t say which note is missing, or put it back. The fix is to reject the bundle and get a fresh one.
• It catches accidents, not thieves. Someone who pockets a note can print a new band saying “99 notes · ₹49,500”. Stopping that needs a tamper-evident seal that only the chest can make.
• It is only as good as the moment it was written. If the chest miscounted before banding, the band faithfully vouches for the wrong bundle.
• A count can be fooled: shuffle the notes and the total is unchanged.

Map it back: the bundle is your data (a packet, a disk block, an uploaded file), the band is the checksum, the counting machine is the reader recomputing it, the refusal is a retry or repair, and the seal is a MAC or signature.

What a checksum is, and isn’t

A checksum function takes any number of bytes and returns a fixed-size value, usually 16 to 256 bits. The writer computes it and keeps it with the data: in a packet header, a file trailer, block metadata or an HTTP header. The reader recomputes it over what arrived and compares. Equal means “almost certainly unchanged”; different means “definitely changed”.

The damage it is built for is accidental, and it comes from everywhere:

• Bit flips on a wire, in RAM without error correction, or in a router’s buffer.
• Truncation: a connection that drops mid-file, a process killed mid-write.
• Torn writes: power fails after only part of a 4 KiB block reached the disk.
• Misdirected and lost writes: firmware puts the right data in the wrong place, or reports success for a write that never happened.
• Software bugs: a copy loop that drops, duplicates or swaps bytes.

Two things a checksum is not:

• Not error correction. Error-correcting codes (ECC memory, the Reed–Solomon codes inside drives, erasure coding across servers) add enough redundancy to rebuild damaged bits. A checksum adds just enough to notice; recovery comes from elsewhere, such as a retransmission or another replica. Real systems pair them: erasure coding rebuilds a fragment, and checksums tell it which fragment is bad.
• Not security. A CRC is a public formula with no key, so anyone who can change the data can recompute the checksum to match. Protecting against people needs a keyed MAC or a digital signature.

The odds: why the number of bits matters

A good n-bit check maps damaged data to an essentially random n-bit value. A random corruption slips through only if it happens to land on the one correct value, so the miss rate is about 1 in 2ⁿ:

“One in 65,536” sounds safe until you multiply. Stone and Partridge captured traffic at several points on the internet for two years (SIGCOMM 2000). Between 1 packet in 1,100 and 1 in 32,000 failed the TCP checksum, even though every link had its own CRC, and in one hour-long test the rate hit 1 in 400. They estimated that 1 packet in 16 million to 1 in 10 billion carried an error that the TCP checksum missed.

Now take one server sending 100,000 packets a second:

100,000 packets/s × 86,400 s/day   = 8.64 billion packets/day
8.64 × 10⁹ ÷ (16 × 10⁶)            ≈ 540 silently corrupted packets/day (bad path)
8.64 × 10⁹ ÷ 10¹⁰                  ≈ 0.86 per day (good path)

Those bytes reach your application looking perfect. Add a 32-bit CRC computed by the application and the bad case falls to 540 ÷ 4.3 billion per day: about one undetected bad packet every 22,000 years. That arithmetic is the whole case for an end-to-end check.

Two caveats keep the maths honest. The 2⁻ⁿ figure assumes errors look random, and weak sums do far worse on real, patterned data: the paper cites a 16-bit sum missing about 1 error in 2¹⁰ (1,024) on real file data. And errors cluster. In every trace, one or two “bad apple” hosts or paths caused a large share, and an application stuck behind one could accept corrupted data every few minutes.

The Internet checksum, by hand

IPv4 headers, TCP and UDP all use the same 16-bit check, described in RFC 1071:

1. Split the bytes into 16-bit words, padding an odd final byte with zero.
2. Add the words with one’s-complement addition: any carry out of the top bit is added back in at the bottom (the “end-around carry”).
3. Invert every bit of the result. That is the checksum.
4. The receiver adds every word including the checksum. A clean packet sums to 0xFFFF.

A worked example with three words:

  0x4A61
+ 0xB2C4   = 0xFD25
+ 0x9E10   = 0x19B35  → carry out of bit 15, so 0x9B35 + 1 = 0x9B36
checksum   = NOT 0x9B36 = 0x64C9
receiver:  0x9B36 + 0x64C9 = 0xFFFF  ✓

It was chosen for speed, not strength. Addition is cheap, works in either byte order, can be split into parallel chunks, and can be updated incrementally: when a router decrements the IP time-to-live field, it adjusts the header checksum by the difference, C' = C + (m' − m), instead of re-adding the whole header.

The price is blind spots. Addition ignores order, so swapped 16-bit words pass. Two errors that cancel, one word one larger and another one smaller, pass too. Stone and Partridge note that it catches every burst error of 15 bits or fewer; beyond that, detection is only probabilistic.

From sums to CRCs to cryptographic hashes

Stronger checks spread every input bit across every output bit. They cost more CPU, and only the keyed ones stop an attacker.

Parity. One extra bit that makes the count of 1s even. It catches any single flipped bit and misses any two.

Fletcher and Adler-32. Two running sums: one of the bytes and one of the running totals, so position matters and reordering is caught. Adler-32, used by zlib (RFC 1950), keeps both sums modulo 65,521. It is weak on short inputs: in a 128-byte packet the byte sum can reach at most 255 × 128 = 32,640, so it never wraps and the checksums bunch together. SCTP replaced Adler-32 with CRC-32C for exactly this reason (RFC 3309).

CRC-32. A cyclic redundancy check treats the data as one huge binary polynomial, divides it by a fixed 33-bit polynomial and keeps the 32-bit remainder. Division mixes every bit into the result, so the guarantees are strong: CRC-32 detects every error confined to fewer than 32 consecutive bits and every pair of flipped bits less than 2,048 bits apart, and other errors slip by about 1 time in 2³². Ethernet’s frame check sequence, gzip and PNG use it.

CRC-32C (Castagnoli). The same idea with a better polynomial. Castagnoli’s team searched tens of thousands of candidates in 1993 for stronger error detection, and RFC 3385 picked the winner for iSCSI because it protects larger blocks and copes better with patterned data. It has since become the storage default: Btrfs, HDFS, Kafka record batches, Google Cloud Storage. Modern CPUs have an instruction for it (on x86, SSE4.2’s crc32), so it is close to free. CRC-64 widens the same design; it is what S3 now attaches by default.

Fast non-cryptographic hashes (xxHash). 64 or 128 bits, built for hash tables and dedupe hints. Nothing in their design resists an attacker either.

Cryptographic hashes (SHA-256, BLAKE2, BLAKE3). Designed so nobody can find two inputs with the same digest, or craft an input for a given one. That makes them safe to use as names: Git object IDs, container image digests, dedupe keys and published download digests. A hash alone still isn’t authentication: an attacker who can replace a file can usually replace the digest printed next to it, unless the digest arrives over a channel you trust.

MACs (HMAC, AEAD tags). A message authentication code mixes in a secret key; RFC 2104 defines HMAC as H((K ⊕ opad) ‖ H((K ⊕ ipad) ‖ m)). Without the key nobody can produce a valid tag, so it proves who sent the data as well as that it is intact. Webhook signatures work this way. AEAD ciphers such as AES-GCM build a tag into encryption, which is how TLS protects each record.

The cost column matters at line rate. The Btrfs documentation measured cycles per 4 KiB block on a 3.6 GHz Intel CPU, which converts straight into throughput per core:

Per-hop checks versus end-to-end checks

Saltzer, Reed and Clark’s 1984 paper End-to-End Arguments in System Design uses checksums as its first example. Their “careful file transfer” moves a file from host A’s disk to host B’s disk and lists what can go wrong: the disk returns bad data, software mis-copies a buffer, the CPU or memory has a transient fault, the network flips or drops bits, or a host crashes halfway. A perfectly reliable network removes just one of those five threats.

So the application must still checksum the file, have B read its copy back from disk, recompute, compare with A’s value, and retry on a mismatch. Once that check exists, reliability inside the network only makes retries rarer; it cannot make the result correct. That is the end-to-end argument: per-hop checks are a performance optimisation, and the end-to-end check is the correctness mechanism.

The paper’s real example is worth retelling in an interview. An MIT network checksummed every hop between gateways, so programmers assumed transfers were safe. One gateway developed a fault that swapped a pair of bytes about once in every million bytes it copied between buffers. Each hop computed its checksum after the swap, so every check passed. Operating-system source files were corrupted, and their owners repaired them by comparing against old printouts.

Stone and Partridge found the same pattern in 2000. A link CRC is checked and then regenerated at every hop, so damage inside a router or a host’s network card leaves with a fresh, valid CRC, and only the end-to-end TCP sum can notice it. They traced errors to memory, DMA engines, buggy drivers and even TCP bugs. One of the authors had long recommended computing the checksum during DMA in the network card for speed; the paper calls that advice wrong, because it leaves data exposed to hardware errors. Their conclusion: valuable data, and they name financial data, needs its own application-level checksum.

Three details the figure hides:

• The IPv4 header checksum covers only the header, and every router recomputes it as the time-to-live changes.
• NICs often compute the TCP checksum in hardware (“checksum offload”), so host memory is outside it.
• TLS 1.3 protects every record with an AEAD cipher, and per RFC 8446 a record that fails decryption ends the connection with a bad_record_mac alert. Corruption on the wire becomes a dropped connection rather than bad data, one more reason to use HTTPS even inside a data centre.

Where checksums live in real systems

File systems and storage engines

• ZFS checksums every block, by default with fletcher4 (SHA-256 when dedup is on), and stores each block’s checksum in its parent’s block pointer rather than beside the block (OpenZFS docs).
• Btrfs checksums data and metadata by default with CRC-32C, with xxHash, SHA-256 and BLAKE2b as options. Metadata blocks carry their checksum inline; data blocks keep theirs in a separate checksum tree.
• HDFS stores a 4-byte CRC-32C for every 512 bytes (dfs.bytes-per-checksum, dfs.checksum.type). That is 4 ÷ 512 ≈ 0.78% overhead, or 262,144 checksums (1 MiB) per 128 MiB block. A client that finds a mismatch reads the block from another DataNode (HDFS architecture).
• Write-ahead logs usually checksum each record. After a crash, the first record that fails its check marks the torn tail of the log, and replay stops there (see write-ahead logging).

Messaging

Kafka puts a CRC-32C in every record batch, covering everything from the attributes field to the end of the batch, including the possibly compressed records. The partition leader epoch sits outside the CRC on purpose: the broker stamps it on every batch it receives, and leaving it out spares the broker from recomputing the checksum each time. A consumer can then check each batch it reads against the CRC the batch carries.

Object stores

• Amazon S3 accepts headers such as x-amz-checksum-crc32c and x-amz-checksum-sha256; its list now covers CRC-64/NVME, CRC-32, CRC-32C, SHA-1, SHA-256, SHA-512, MD5 and three xxHash variants. S3 recomputes the value, rejects a mismatch with BadDigest, and stores it as metadata so downloads can be checked too. If neither you nor the SDK sends one, S3 attaches CRC-64/NVME. The older Content-MD5 header still works for single-part uploads.
• Google Cloud Storage keeps CRC32C and MD5, recommends CRC32C, and supports only CRC32C for objects uploaded in pieces (GCS docs). A mismatched upload is rejected with a 400.

Downloads, content addressing and dedupe

Release pages publish SHA-256 digests, Git names every object by its hash, and container images are pulled by sha256: digest. When the name is the checksum, a corrupted or substituted blob can’t be served under the right name. Dedupe works the same way: a Dropbox-style store keys each chunk by its SHA-256, so a marksheet PDF uploaded by a thousand students to a DigiLocker-style service is stored once.

Design patterns: compute early, verify everywhere

1. Compute at the source: in the client SDK before upload, in the producer before the batch leaves. A checksum computed after a bug damaged the buffer just certifies garbage.
2. Store it with the data: object metadata, block headers, a manifest. Any later reader can verify, years later, without trusting anything in between.
3. Verify on every read and every copy: replication, compaction, tiering to cold storage, cross-region copies. Check the source before copying and the destination after; GCS, for example, validates copies and rewrites against the stored checksum.
4. Never return bad data silently. On a mismatch, retry the read, try another replica, serve the good copy, repair the bad one and emit a metric naming the disk and host. If no good copy exists, fail loudly.
5. Scrub in the background, because reads only check data someone reads, and cold data can rot for years.
6. Decide which bytes you checksum. gzip and zlib checksum the uncompressed data, which also verifies the decompressor. Kafka’s batch CRC covers the compressed bytes, so a broker can verify a batch without decompressing it.
7. Reuse it for idempotency. Store a hash of the request body with each idempotency key, so a retry with the same key but a different body is rejected instead of replayed.

Scrubbing: find rot before the last good copy goes

Bairavasundaram and colleagues studied 1.53 million disks over 41 months (FAST ’08) and found more than 400,000 checksum mismatches. 0.86% of nearline (SATA) disks and 0.065% of enterprise disks developed at least one. Background scrubs found 49% of the nearline mismatches and 73% of the enterprise ones, but 8% of nearline mismatches surfaced only during RAID reconstruction, exactly when a second fault means data loss. At that rate, a fleet of 10,000 nearline disks would have about 86 disks quietly holding bad blocks after a few years.

Scrubbing costs disk bandwidth, so it is throttled, and the throttle must match the disk. HDFS’s block scanner defaults to 1 MiB/s per volume and scans each block at most once per 504 hours (three weeks). That reads at most 504 × 3,600 s × 1 MiB/s ≈ 1.7 TiB per volume per period, so covering a 16 TB disk every three weeks needs about 16 × 10¹² B ÷ 1,814,400 s ≈ 8.8 MB/s. You gain early detection while the other replicas are healthy; you pay steady background I/O.

Verifying a 50 GB upload in parts

Send it as, say, 500 parts of 100 MB, each with its own CRC-32C, so a damaged part is retried alone (see large file uploads). For the whole object, S3 offers two shapes:

• Full-object checksum, CRCs only (CRC-64/NVME, CRC-32, CRC-32C). CRCs combine mathematically, so S3 derives the whole-file CRC from the part CRCs, and it matches a CRC computed locally over the file whatever the part size.
• Composite checksum: a checksum of the part checksums. It works with SHA-256 and others, but the value depends on where the parts were cut.

ETags are not MD5s. An S3 ETag is the MD5 of the content only for single-part uploads that are unencrypted or use SSE-S3. With SSE-KMS or SSE-C it is not (S3 API reference), and after a multipart upload it is the MD5 of the concatenated part MD5s plus “-N” for N parts. HDFS has the same trap: its default file checksum (MD5MD5CRC) can’t be compared across files with different block layouts, while COMPOSITE_CRC can.

Merkle trees: comparing replicas cheaply

A checksum of a whole replica gives one bit of news: same or different. A Merkle tree also says where. Each leaf is the hash of a key range and each parent is the hash of its children. Two replicas compare roots; if they match, they are in sync after one exchange. If not, they compare children and descend only into subtrees that differ. Dynamo uses this for anti-entropy between replicas, as do Cassandra-style stores (see quorums and leaderless replication).

Going deeper: how checksums fail

The checksum is computed after the damage

The MIT gateway and the DMA errors share one cause: the check was computed over data that was already wrong. NIC checksum offload has the same shape, since the TCP checksum is computed after the bytes leave host memory. The reverse bites too: Btrfs warns that a program changing an O_DIRECT buffer after its checksum is computed causes false mismatches, so newer kernels fall back to buffered writes. Checksum and data must describe the same moment.

The checksum is stored next to the data

A block that carries its own checksum is self-consistent even when it is the wrong block. If firmware silently drops a write, or puts it in the wrong sector, the reader gets stale or misplaced data with a matching checksum. Bonwick’s answer in ZFS was to keep each block’s checksum in its parent’s block pointer, one level up a tree that has already been verified. Elsewhere, include the block’s identity (object ID, offset, version) in the checksummed bytes, so a misplaced block fails.

Collisions in dedupe

With k items and an n-bit check, the chance that some two collide is about k² ÷ 2ⁿ⁺¹. A 32-bit check reaches even odds at about 1.18 × √2³² ≈ 77,000 items, so a CRC must never serve as an identity. SHA-256 over 10¹⁵ chunks gives about 10³⁰ ÷ 2²⁵⁷ ≈ 4 × 10⁻⁴⁸. That is why OpenZFS allows dedup only with cryptographic hashes.

CPU cost and offload

At 25 Gbit/s, hardware CRC-32C costs about a tenth of a core and SHA-256 about 1.6 cores (Fig. 2). Use CRC-32C on hot paths, a cryptographic hash only where you need names or resistance to attackers, and offload where you can (NICs for TCP, QuickAssist cards for ZFS), knowing that an offloaded check covers less of the path.

Fields that change in flight

Leave mutable fields out of the checksum, as Kafka does with the leader epoch, or update it incrementally, as routers do with the time-to-live. Recomputing a checksum at every hop quietly turns an end-to-end check back into a per-hop one.

Cheat sheet

How to say it in the interview

“A checksum lets the reader detect accidental change. TCP’s 16-bit sum misses about 1 in 65,536 corruptions and ends at every proxy, so for durable data I add an end-to-end CRC-32C: the client computes it, the API verifies it before acknowledging, it is stored with every replica, and every read, copy and scrub re-checks it. On a mismatch I serve another replica and repair the bad one. Where the digest doubles as an ID I use SHA-256, and anything crossing a trust boundary gets an HMAC or a signature.”

TCP already has a checksum. Why add one? It is 16 bits, real traffic slipped 1 corrupted packet in 16 million to 10 billion past it, and it ends at every proxy without seeing memory or disk. Only an end-to-end check proves the stored bytes are right.

CRC-32C or SHA-256 for verifying uploads? CRC-32C to catch accidents: about 16 times cheaper and combinable across parts. SHA-256 when the digest is also a name or dedupe key. Neither proves who uploaded.

How would you detect silent corruption in a blob store with three replicas? Checksum every chunk on every replica, verify on every read and fall back to another replica, scrub fast enough to cover each disk every couple of weeks, repair from a good copy, alert per disk, and compare replicas with Merkle trees.

Checksum vs hash vs HMAC? A checksum catches accidents; a cryptographic hash also resists deliberate collisions, so it can name content; an HMAC adds a secret key, so it also proves the sender.

How do you verify a 50 GB file uploaded in parts? A CRC per part so a bad part is retried alone, then a full-object CRC derived from the parts and compared with one computed locally. Not the ETag: after a multipart upload it isn’t an MD5 of the file.

Where to go next

• TCP vs UDP: the transports that carry the 16-bit checksum.
• The OSI model: which layer each check belongs to.
• HTTP and HTTPS: TLS and its record integrity.
• Webhooks: HMAC signatures in practice.
• Data replication: the replicas a scrubber repairs from.
• Blob storage (S3) and design an object store like S3: checksums inside a full storage design.
• Encryption and key management: keys for HMACs and signatures.

References and further reading

1. RFC 1071 — Computing the Internet Checksumrfc-editor.orgThe 16-bit one’s-complement sum used by IPv4, TCP and UDP, with worked examples and the incremental-update formula.
2. RFC 3385 — iSCSI CRC/Checksum Considerationsrfc-editor.orgCompares CRC-32, CRC-32C, Fletcher and Adler for undetected-error probability, and explains why iSCSI chose CRC-32C.
3. When the CRC and TCP Checksum Disagree (Stone and Partridge, SIGCOMM 2000)conferences.sigcomm.orgTwo years of internet traces: how often packets fail the TCP checksum, how many errors it misses, and where the damage comes from.
4. End-to-End Arguments in System Design (Saltzer, Reed and Clark, 1984)web.mit.eduThe “careful file transfer” argument for end-to-end checksums, and the MIT gateway that swapped byte pairs.
5. An Analysis of Data Corruption in the Storage Stack (Bairavasundaram et al., FAST ’08)usenix.orgChecksum mismatches across 1.53 million disks over 41 months, and how many were found by scrubbing versus RAID reconstruction.
6. ZFS End-to-End Data Integrity (Bonwick, 2005, archived)web.archive.orgWhy a checksum stored with its own block misses phantom and misdirected writes, and why ZFS keeps it in the parent block pointer.
7. Btrfs documentation: Checksummingbtrfs.readthedocs.ioDefault CRC-32C, the xxHash, SHA-256 and BLAKE2b options, measured cycles per 4 KiB for each, and the direct-I/O buffer pitfall.
8. Apache Hadoop: hdfs-default.xmlhadoop.apache.orgDefaults for bytes per checksum (512), checksum type (CRC32C), checksum combine modes and the DataNode block scanner.
9. Apache Kafka documentation: Message formatkafka.apache.orgThe record batch layout, which bytes the CRC-32C covers, and why the partition leader epoch is left out.
10. Amazon S3 User Guide: Checking object integrity for data uploadsdocs.aws.amazon.comSupported checksum algorithms, BadDigest on mismatch, full-object versus composite checksums for multipart uploads, and multipart ETags.