Header Compression: HPACK Algorithm Deep Dive

Every HTTP request carries headers—metadata describing the request, authentication credentials, content preferences, and more. In HTTP/1.1, these headers are transmitted as plain text with every single request, leading to staggering inefficiency.

Consider a typical web page that makes 70 requests. Each request might carry 800 bytes of headers. That's 56KB of header data—most of it identical across requests (User-Agent, Accept-Encoding, Cookie headers). On a mobile connection, this redundancy adds measurable latency.

HTTP/2 solves this with HPACK (Header Compression for HTTP/2), a specialized compression algorithm designed specifically for HTTP headers. HPACK doesn't just compress headers—it eliminates redundancy across requests, achieving compression ratios of 80-95% for typical traffic.

To understand HPACK's design, we must first appreciate the magnitude of the header redundancy problem.

Anatomy of HTTP Request Headers:

A typical browser request includes:

GET /api/data HTTP/1.1
Host: example.com
Connection: keep-alive
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36...
Accept: application/json, text/plain, */*
Accept-Encoding: gzip, deflate, br
Accept-Language: en-US,en;q=0.9
Cookie: session=abc123; user_id=789; tracking=xyz...
Authorization: Bearer eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9...
Cache-Control: no-cache

This might total 500-1500 bytes. Now consider that every request on the page repeats most of this. The User-Agent, Accept headers, and Cookies are identical across all 70 requests.

The Cumulative Cost:

For a page with 70 requests and 800-byte average headers:

• HTTP/1.1: 70 × 800 = 56,000 bytes of headers
• After HPACK (85% compression): ~8,400 bytes
• Savings: 47,600 bytes per page load

On a 1 Mbps connection, this saves ~380ms—a noticeable improvement. On congested mobile networks, savings can exceed 1 second.

HPACK (RFC 7541) was designed with specific goals:

1. Security: Resist CRIME-style compression oracle attacks
2. Efficiency: Minimize header bytes on the wire
3. Statefulness: Leverage repetition across multiple requests
4. Simplicity: Enable efficient implementation in constrained environments

To achieve these goals, HPACK uses three core mechanisms:

1. Static Table: A predefined dictionary of 61 common header name/value pairs

2. Dynamic Table: A connection-specific dictionary built from observed headers

3. Huffman Encoding: Bit-level compression of literal string values

Encoding Strategies:

When encoding a header, HPACK chooses one of several strategies:

The "never indexed" option is crucial for security—it prevents sensitive values (like Authorization tokens) from being stored in the dynamic table where they might leak.

HPACK defines a static table of 61 entries containing the most common HTTP/2 headers. These entries never change and are available from the start of every connection.

Static Table Entries (Excerpt):

Using the Static Table:

Consider encoding a GET request to /:

1. :method: GET → Index 2 (exact match) → 1 byte
2. :path: / → Index 4 (exact match) → 1 byte
3. :scheme: https → Index 7 (exact match) → 1 byte

These pseudo-headers that would be ~30 bytes in HTTP/1.1 are encoded in just 3 bytes!

For headers with only the name in the static table (empty value), the encoder uses the name's index plus a literal value:

4. :authority: example.com → Index 1 (name) + Huffman("example.com") → ~10 bytes

Static Table Design:

The 61 entries were carefully chosen based on analysis of real HTTP traffic:

• Pseudo-headers first (1-7): :authority, :method, :path, :scheme
• Status codes (8-14): Common response statuses
• Request headers (15-58): Alphabetically ordered common headers
• Response headers (59-61): set-cookie, strict-transport-security, etc.

Notice that many entries have empty values—the static table primarily indexes header names, with only the most common name:value pairs (like :method: GET) having both parts indexed.

The dynamic table is HPACK's secret weapon for eliminating cross-request redundancy. Unlike the static table, the dynamic table is built during the connection based on actual headers observed.

How the Dynamic Table Works:

1. Connection starts with empty dynamic table
2. When encoder sends a header with "add to table" flag, entry is added
3. Both encoder and decoder maintain synchronized tables
4. Subsequent references can use the table index instead of literal values
5. Table uses FIFO eviction when size limit is reached

Table Indexing:

Dynamic table entries are addressed by index, continuing after the static table:

Index 1-61:  Static table (never changes)
Index 62+:   Dynamic table (newest first)

When a new entry is added, it becomes index 62, and all existing dynamic entries increment by 1. This "newest first" ordering optimizes for temporal locality—recently used headers are likely to be used again soon.

Example Session:

Request 1: Cookie: session=abc123
  → Encoded as literal with indexing
  → Dynamic table: [62: cookie: session=abc123]

Request 2: Cookie: session=abc123  
  → Encoded as index 62 (1 byte!)
  → Same cookie, 95%+ savings

Request 3: authorization: Bearer token123
  → Encoded as literal with indexing
  → Dynamic table: [62: authorization: Bearer token123]
                   [63: cookie: session=abc123]

Table Size Management:

The dynamic table size is constrained by SETTINGS_HEADER_TABLE_SIZE (default: 4096 bytes). Entry size is calculated as:

Entry size = len(name) + len(value) + 32 bytes overhead

The 32-byte overhead accounts for implementation data structures. When adding an entry would exceed the limit, oldest entries are evicted until sufficient space exists.

A table size of 0 effectively disables the dynamic table—every header must be sent literally. This might be used in high-security contexts where caching headers is undesirable.

When HPACK must transmit literal values (not in any table), it can apply Huffman encoding to reduce their size. HPACK uses a fixed Huffman code table optimized for HTTP header content.

Huffman Coding Basics:

Huffman encoding assigns variable-length bit patterns to characters based on frequency. Common characters get shorter codes:

'a' → 11000 (5 bits)      // Very common
'0' → 00000 (5 bits)      // Common
' ' → 010100 (6 bits)     // Space is common
'X' → 1111111101100 (13 bits) // Rare

Typical ASCII uses 8 bits per character. Huffman achieves average of ~5-6 bits for HTTP headers, saving 25-35%.

HPACK's Huffman Table:

HPACK defines a fixed 256-entry Huffman code table based on analysis of real HTTP traffic. Some characteristics:

• Lowercase letters: 5-7 bits (very common in headers)
• Digits: 5 bits (common in values)
• Uppercase letters: 6-8 bits (less common)
• Symbols like '=' and ':': 5-6 bits
• Control characters: 10-15 bits (rare, but must be encodable)
• EOS (End of String): 30 bits (padding marker)

When to Use Huffman:

HPACK marks Huffman-encoded strings with a flag bit. Encoders choose based on which representation is smaller:

• Short, common strings: Huffman usually wins
• Already-compact strings (digits): Sometimes ties
• Binary/unusual data: Huffman may expand

Most implementations always try Huffman and compare sizes, using whichever is smaller. The flag bit signals the decoder which decoding path to use.

HPACK defines a precise binary format for encoding headers. Understanding this format reveals how the three mechanisms (static table, dynamic table, Huffman) work together.

Integer Representation:

HPACK uses a variable-length integer encoding for table indices and string lengths. The encoding optimizes for small values:

Pseudo-code for HPACK integer encoding:
if value < 2^prefix_bits - 1:
    encode in prefix_bits (1 byte, fits in first byte's remaining bits)
else:
    first byte = all 1s in prefix_bits
    remaining = value - (2^prefix_bits - 1)
    encode remaining in 7-bit chunks with continuation bit

This means indices 1-14 (common static entries) encode in a single byte.

Complete Encoding Example:

Let's encode this header block:

:method: GET
:path: /api/users
:authority: api.example.com
authorization: Bearer token123

Encoding Process:

1. :method: GET → Index 2 (static table exact match)

   • Binary: 10000010 (indexed, index=2)
   • Wire: 1 byte

2. :path: /api/users → Index 4 name only, literal value

   • Binary: 01000100 (literal+indexing, name index=4)
   • Value: Huffman("/api/users") with length prefix
   • Wire: ~10 bytes
   • Dynamic table updated: [62: :path: /api/users]

3. :authority: api.example.com → Index 1 name, literal value

   • Binary: 01000001 (literal+indexing, name index=1)
   • Value: Huffman("api.example.com") with length prefix
   • Wire: ~13 bytes
   • Dynamic table: [62: :authority: api.example.com, 63: :path: /api/users]

4. authorization: Bearer token123 → Literal name, literal value (never index!)

   • Binary: 00010000 (never indexed, name is literal)
   • Name: Huffman("authorization")
   • Value: Huffman("Bearer token123")
   • Wire: ~25 bytes
   • Dynamic table: unchanged (never indexed)

Total: ~49 bytes instead of ~130 bytes raw (62% compression)

HPACK's design was heavily influenced by known attacks on compression. Understanding these attacks explains why HPACK works the way it does.

CRIME Attack (2012):

CRIME (Compression Ratio Info-leak Made Easy) exploited TLS-level compression:

1. Attacker injects guesses into victim's requests (via XSS or similar)
2. If guess matches existing content, compression shrinks the request
3. Attacker observes response size to detect matches
4. Iteratively extracts secrets byte-by-byte

This attack worked because general-purpose compression (DEFLATE) finds patterns anywhere in the data. Session cookies could be extracted in minutes.

How HPACK Prevents CRIME:

HPACK's design prevents compression-based oracles:

1. Fixed Huffman Table: Unlike DEFLATE's adaptive compression, HPACK's Huffman table is static. Attackers can't observe compression ratio changes from injected data—the encoding is predictable.

2. Table-Based Compression Only: HPACK compresses by table reference, not pattern matching. A partial match provides no information—either the header is in the table (fully indexed) or it's not.

3. Never-Indexed Literals: Sensitive headers can be marked to never enter the dynamic table, preventing any compression-based inference.

4. Per-Connection Tables: Dynamic tables are connection-scoped. Cross-connection attacks can't leverage one connection's table state.