Computer NetworksHTTP/2

HTTP/2: The Modern Web Protocol

LevelIntermediate

Duration90 mins

TopicHTTP/2

3 / 5

Header Compression: HPACK Algorithm Deep Dive

The Header Redundancy Crisis

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.

What You Will Learn

By the end of this page, you will understand: (1) Why general-purpose compression (gzip, deflate) is unsuitable for HTTP headers, (2) How HPACK's static and dynamic tables eliminate redundancy, (3) The Huffman encoding used for literal values, (4) How HPACK maintains state across requests, (5) Security considerations like CRIME and BREACH that shaped HPACK's design, and (6) Real-world compression performance characteristics.

The HTTP Header Problem

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.

Header Redundancy in Practice
Header	Size (bytes)	Changes Between Requests?	Redundancy Type
User-Agent	100-200	Never (same browser)	Completely redundant
Accept-Language	20-50	Never	Completely redundant
Accept-Encoding	20-30	Never	Completely redundant
Cookie	200-2000	Rarely (session-based)	Mostly redundant
Authorization	100-500	Rarely (token-based)	Mostly redundant
:path	10-100	Often (different URLs)	Partially redundant
:method	3-6	Sometimes	Highly redundant (GET common)

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.

Why Not Just Use gzip?

HTTP/1.1's body compression (Content-Encoding: gzip) works well for content. But using general-purpose compression for headers enables CRIME/BREACH attacks—attackers inject data and observe compressed size changes to extract secrets. HPACK was designed from the ground up to prevent these attacks while providing excellent compression.

HPACK Design Principles

HPACK (RFC 7541) was designed with specific goals:

Security: Resist CRIME-style compression oracle attacks
Efficiency: Minimize header bytes on the wire
Statefulness: Leverage repetition across multiple requests
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

Converting Mermaid diagram...

Encoding Strategies:

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

Strategy	When Used	Wire Size
Indexed (table match)	Header name:value in table	1 byte (index)
Literal with indexing	New header, should be remembered	Name ref + literal value
Literal without indexing	Header shouldn't be indexed (privacy)	Name ref + literal value
Literal never indexed	Sensitive header (never cache)	Name ref + literal value

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.

Stateful Compression

Unlike stateless compression (gzip each message independently), HPACK maintains state across the entire connection. Both encoder and decoder maintain synchronized copies of the dynamic table. This is why HTTP/2's HEADERS frames must be processed in order—the compression state depends on seeing every header block.

The Static Table

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):

HPACK Static Table (Selected Entries)
Index	Name	Value
1	:authority	(empty)
2	:method	GET
3	:method	POST
4	:path	/
5	:path	/index.html
6	:scheme	http
7	:scheme	https
8	:status	200
14	:status	500
15	accept-charset	(empty)
19	accept-language	(empty)
22	allow	(empty)
32	content-type	(empty)
50	range	(empty)
61	www-authenticate	(empty)

Using the Static Table:

Consider encoding a GET request to /:

:method: GET → Index 2 (exact match) → 1 byte
:path: / → Index 4 (exact match) → 1 byte
: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:

: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.

Pseudo-Headers in HTTP/2

HTTP/2 uses pseudo-headers (prefixed with ':') to replace the request line. Instead of 'GET /path HTTP/2', HTTP/2 sends :method, :path, :scheme, and :authority as regular (but special) headers. This unifies the header encoding mechanism and aligns with the binary framing model.

The Dynamic Table

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:

Connection starts with empty dynamic table
When encoder sends a header with "add to table" flag, entry is added
Both encoder and decoder maintain synchronized tables
Subsequent references can use the table index instead of literal values
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]

Dynamic Table Operations
Operation	Effect on Table	When Used
Add entry	New entry at index 62; others shift up	New header should be remembered
Reference entry	No change to table	Header already in table
Evict entry	Oldest entries removed	Table size exceeds limit
Resize table	May trigger evictions	SETTINGS frame changes max size
Clear table	All entries removed	SETTINGS with size = 0

Table Synchronization is Critical

Encoder and decoder must have identical dynamic tables. If they diverge (due to a missed header block), subsequent decoding will produce garbage. This is why HTTP/2 prohibits interleaving HEADERS/CONTINUATION frames with other frame types for the same stream—the decompressor must see all header blocks in order.

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.

Huffman Encoding

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)

huffman_examples.txt

Text

// Example: Encoding "text/html"
Character  ASCII (8 bits)  Huffman (HPACK)
't'        01110100        100010 (6 bits)
'e'        01100101        00100 (5 bits)
'x'        01111000        111111000 (9 bits)
't'        01110100        100010 (6 bits)
'/'        00101111        011001 (6 bits)
'h'        01101000        100000 (6 bits)
't'        01110100        100010 (6 bits)
'm'        01101101        101010 (6 bits)
'l'        01101100        11101 (5 bits)
 
ASCII:   9 × 8 bits = 72 bits (9 bytes)
Huffman: 6+5+9+6+6+6+6+6+5 = 55 bits (7 bytes, padded)
 
Savings: 22% for this short string

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.

Huffman Padding

Since Huffman codes aren't byte-aligned, HPACK pads with the EOS symbol's prefix bits. The decoder detects padding by checking for more than 7 consecutive '1' bits at the end. Improper padding is a protocol error—this prevents certain oracle attacks that exploit padding behavior.

Encoding Format Details

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.

HPACK Encoding Types (First Byte Patterns)
Pattern	Type	Description
1xxxxxxx	Indexed Header	Full name:value match in table; index in lower 7 bits
01xxxxxx	Literal with Indexing	Add to dynamic table; 6-bit name index prefix
000xxxxx	Literal without Indexing	Don't add to table; 4-bit name index prefix
0001xxxx	Literal Never Indexed	Never add (sensitive); 4-bit name index prefix
001xxxxx	Dynamic Table Size Update	Change max table size

Complete Encoding Example:

Let's encode this header block:

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

Encoding Process:

:method: GET → Index 2 (static table exact match)
- Binary: 10000010 (indexed, index=2)
- Wire: 1 byte
: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]
: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]
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)

Never Indexed for Secrets

The 'never indexed' instruction is crucial for security. Authorization tokens, session cookies, and other sensitive values should never be stored in the dynamic table where intermediary proxies might cache them. HPACK implementations must respect this flag even when suboptimal for compression.

Security Considerations

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:

Attacker injects guesses into victim's requests (via XSS or similar)
If guess matches existing content, compression shrinks the request
Attacker observes response size to detect matches
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:

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.
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.
Never-Indexed Literals: Sensitive headers can be marked to never enter the dynamic table, preventing any compression-based inference.
Per-Connection Tables: Dynamic tables are connection-scoped. Cross-connection attacks can't leverage one connection's table state.

HPACK Security Properties

•No Cross-Request Pattern Matching: HPACK doesn't find patterns between headers; it only indexes complete name:value pairs
•Fixed Encoding Table: Huffman codes are static, providing no side-channel based on compression ratio
•Sensitive Header Protection: 'Never indexed' instruction prevents sensitive values from being cached
•Table Isolation: Each connection has its own dynamic table; no cross-origin pollution
•Size-Based Attacks Mitigated: Table size limits and eviction make size-guessing attacks impractical

BREACH Still Applies to Bodies

While HPACK protects headers, response body compression (gzip) can still leak data via BREACH attacks. If secret tokens appear in both body and reflected user input, attackers can extract them. This is a general issue—mitigations include masking secrets and using SameSite cookies—not specific to HTTP/2.

Implementation Considerations

Implementing HPACK correctly requires attention to several details that affect both correctness and performance.

Decoder Requirements:

Table Synchronization: Decoder must track dynamic table exactly as encoder does
Size Limit Enforcement: Reject table sizes exceeding SETTINGS limit
Huffman Validation: Detect improper padding (too many 1 bits)
Integer Overflow: Handle variable-length integers safely
Memory Management: Allocate/evict table entries efficiently

Encoder Strategies:

Table Utilization: Good encoders maximize table usage for repeated headers
Sensitivity Detection: Mark cookies, auth tokens as never-indexed
Size Optimization: Choose Huffman vs. raw based on actual size
Entry Priority: Decide which headers to add to limited table space

hpack_decoder.pseudo

Pseudocode

// Simplified HPACK decoder logic
function decodeHeaderBlock(bytes):
    headers = []
    i = 0
    
    while i < bytes.length:
        firstByte = bytes[i]
        
        if firstByte & 0x80:  // Indexed header (1xxxxxxx)
            index = decodeInteger(bytes, i, 7)
            name, value = lookupTable(index)
            headers.add(name, value)
            
        else if firstByte & 0x40:  // Literal with indexing (01xxxxxx)
            nameIndex = decodeInteger(bytes, i, 6)
            if nameIndex > 0:
                name = lookupTable(nameIndex).name
            else:
                name = decodeString(bytes, i)
            value = decodeString(bytes, i)
            headers.add(name, value)
            dynamicTable.add(name, value)  // Add to table!
            
        else if firstByte & 0x20:  // Table size update (001xxxxx)
            newSize = decodeInteger(bytes, i, 5)
            dynamicTable.setMaxSize(newSize)
            
        else:  // Literal without/never indexing
            // Similar to 0x40 case but don't add to table
            ...
    
    return headers

Common Implementation Pitfalls:

Issue	Symptom	Prevention
Table desync	Garbage headers after N requests	Process all header blocks in order
Integer overflow	Connection reset / crash	Limit maximum integer value
Huffman padding	Protocol error	Validate ≤7 padding bits
Table size exceeded	Memory exhaustion	Enforce SETTINGS limit strictly
Missing never-indexed	Security vulnerability	Default sensitive headers to never-index

Testing HPACK Implementations

The nghttp2 project provides an HPACK test suite with edge cases. The HTTP/2 spec includes example encodings for validation. Fuzzing with AFL or similar tools is essential—HPACK parsers are security-critical code handling untrusted input.

Performance Characteristics

HPACK's real-world performance depends on traffic patterns, table size settings, and implementation quality.

Compression Ratios:

Typical compression ratios observed:

Scenario	Compression Ratio	Notes
Single request	40-50%	Only static table + Huffman
After 10 requests	70-80%	Dynamic table warming up
Steady state	85-95%	Full table utilization
API traffic (JSON)	80-90%	High header redundancy
Mixed origins	60-75%	Less repetition across origins

REST APIs benefit enormously—every request has identical Accept, Content-Type, and Authorization headers.

Table Size Impact:

Larger dynamic tables increase compression but consume memory:

Table Size	Memory Per Connection	Compression Benefit
0 bytes	~0	No dynamic compression
4,096 bytes (default)	~4KB	Good for most traffic
16,384 bytes	~16KB	Better for large cookie/token sites
65,536 bytes	~64KB	Maximum practical benefit

Servers with millions of connections must balance table size against memory. A 16KB table with 1M connections = 16GB just for HPACK tables!

Optimizing HPACK Performance

•Consistent Header Order: Send headers in same order to maximize table hits
•Minimize Header Variation: Avoid unnecessary per-request header changes
•Appropriate Table Size: Increase for high-header-volume applications
•Header Normalization: Lowercase names, consistent value formats
•Avoid Large Cookies: Large cookies evict other table entries quickly

HPACK vs QPACK

HTTP/3 uses QPACK instead of HPACK because QUIC's out-of-order delivery breaks HPACK's synchronization requirements. QPACK adds explicit table state acknowledgments, allowing headers to be decoded even when earlier header blocks are delayed. QPACK preserves HPACK's core concepts but adapts them for unreliable transport.

Summary: HPACK Eliminates Header Redundancy

HPACK represents a carefully-designed solution to HTTP header redundancy, balancing compression efficiency against security requirements.

Key Takeaways

•Headers are hugely redundant — Typical pages waste tens of KB on repeated User-Agent, Cookie, and Accept headers.
•HPACK uses three mechanisms — Static table (61 predefined entries), dynamic table (connection-specific), and Huffman encoding (bit-level compression).
•Static table handles common cases — :method: GET, :path: /, :scheme: https encode in 1 byte each.
•Dynamic table learns from traffic — Headers are indexed and reused, achieving 85-95% compression in steady state.
•Huffman compresses literals — Variable-length codes save 25-35% on string values.
•Security is foundational — Never-indexed literals and fixed Huffman tables prevent compression oracle attacks like CRIME.
•Stateful compression requires synchronization — Encoder and decoder must process all header blocks in order.

What's Next:

With binary framing, multiplexing, and header compression understood, we now explore HTTP/2's proactive feature: Server Push. Server push allows servers to send resources before clients request them, potentially eliminating round-trip latency for critical assets.

Page Complete

You now understand HTTP/2's header compression mechanism—how HPACK's tables and Huffman encoding eliminate header redundancy while maintaining security. This compression, combined with multiplexing, makes HTTP/2 dramatically more efficient than HTTP/1.1 for header-heavy workloads like REST APIs and content-rich web pages.

3 / 5

Loading learning content...

Computer NetworksHTTP/2

HTTP/2: The Modern Web Protocol

LevelIntermediate

Duration90 mins

TopicHTTP/2

3 / 5

Header Compression: HPACK Algorithm Deep Dive

The Header Redundancy Crisis

What You Will Learn

The HTTP Header Problem

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.

Header Redundancy in Practice
Header	Size (bytes)	Changes Between Requests?	Redundancy Type
User-Agent	100-200	Never (same browser)	Completely redundant
Accept-Language	20-50	Never	Completely redundant
Accept-Encoding	20-30	Never	Completely redundant
Cookie	200-2000	Rarely (session-based)	Mostly redundant
Authorization	100-500	Rarely (token-based)	Mostly redundant
:path	10-100	Often (different URLs)	Partially redundant
:method	3-6	Sometimes	Highly redundant (GET common)

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.

Why Not Just Use gzip?

HPACK Design Principles

HPACK (RFC 7541) was designed with specific goals:

Security: Resist CRIME-style compression oracle attacks
Efficiency: Minimize header bytes on the wire
Statefulness: Leverage repetition across multiple requests
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

Converting Mermaid diagram...

Encoding Strategies:

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

Strategy	When Used	Wire Size
Indexed (table match)	Header name:value in table	1 byte (index)
Literal with indexing	New header, should be remembered	Name ref + literal value
Literal without indexing	Header shouldn't be indexed (privacy)	Name ref + literal value
Literal never indexed	Sensitive header (never cache)	Name ref + literal value

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.

Stateful Compression

The Static Table

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):

HPACK Static Table (Selected Entries)
Index	Name	Value
1	:authority	(empty)
2	:method	GET
3	:method	POST
4	:path	/
5	:path	/index.html
6	:scheme	http
7	:scheme	https
8	:status	200
14	:status	500
15	accept-charset	(empty)
19	accept-language	(empty)
22	allow	(empty)
32	content-type	(empty)
50	range	(empty)
61	www-authenticate	(empty)

Using the Static Table:

Consider encoding a GET request to /:

:method: GET → Index 2 (exact match) → 1 byte
:path: / → Index 4 (exact match) → 1 byte
: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:

: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.

Pseudo-Headers in HTTP/2

The Dynamic Table

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:

Connection starts with empty dynamic table
When encoder sends a header with "add to table" flag, entry is added
Both encoder and decoder maintain synchronized tables
Subsequent references can use the table index instead of literal values
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)

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]

Dynamic Table Operations
Operation	Effect on Table	When Used
Add entry	New entry at index 62; others shift up	New header should be remembered
Reference entry	No change to table	Header already in table
Evict entry	Oldest entries removed	Table size exceeds limit
Resize table	May trigger evictions	SETTINGS frame changes max size
Clear table	All entries removed	SETTINGS with size = 0

Table Synchronization is Critical

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.

Huffman Encoding

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)

huffman_examples.txt

Text

// Example: Encoding "text/html"
Character  ASCII (8 bits)  Huffman (HPACK)
't'        01110100        100010 (6 bits)
'e'        01100101        00100 (5 bits)
'x'        01111000        111111000 (9 bits)
't'        01110100        100010 (6 bits)
'/'        00101111        011001 (6 bits)
'h'        01101000        100000 (6 bits)
't'        01110100        100010 (6 bits)
'm'        01101101        101010 (6 bits)
'l'        01101100        11101 (5 bits)
 
ASCII:   9 × 8 bits = 72 bits (9 bytes)
Huffman: 6+5+9+6+6+6+6+6+5 = 55 bits (7 bytes, padded)
 
Savings: 22% for this short string

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.

Huffman Padding

Encoding Format Details

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.

HPACK Encoding Types (First Byte Patterns)
Pattern	Type	Description
1xxxxxxx	Indexed Header	Full name:value match in table; index in lower 7 bits
01xxxxxx	Literal with Indexing	Add to dynamic table; 6-bit name index prefix
000xxxxx	Literal without Indexing	Don't add to table; 4-bit name index prefix
0001xxxx	Literal Never Indexed	Never add (sensitive); 4-bit name index prefix
001xxxxx	Dynamic Table Size Update	Change max table size

Complete Encoding Example:

Let's encode this header block:

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

Encoding Process:

:method: GET → Index 2 (static table exact match)
- Binary: 10000010 (indexed, index=2)
- Wire: 1 byte
: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]
: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]
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)

Never Indexed for Secrets

Security Considerations

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:

Attacker injects guesses into victim's requests (via XSS or similar)
If guess matches existing content, compression shrinks the request
Attacker observes response size to detect matches
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:

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.
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.
Never-Indexed Literals: Sensitive headers can be marked to never enter the dynamic table, preventing any compression-based inference.
Per-Connection Tables: Dynamic tables are connection-scoped. Cross-connection attacks can't leverage one connection's table state.

HPACK Security Properties

•No Cross-Request Pattern Matching: HPACK doesn't find patterns between headers; it only indexes complete name:value pairs
•Fixed Encoding Table: Huffman codes are static, providing no side-channel based on compression ratio
•Sensitive Header Protection: 'Never indexed' instruction prevents sensitive values from being cached
•Table Isolation: Each connection has its own dynamic table; no cross-origin pollution
•Size-Based Attacks Mitigated: Table size limits and eviction make size-guessing attacks impractical

BREACH Still Applies to Bodies

Implementation Considerations

Implementing HPACK correctly requires attention to several details that affect both correctness and performance.

Decoder Requirements:

Table Synchronization: Decoder must track dynamic table exactly as encoder does
Size Limit Enforcement: Reject table sizes exceeding SETTINGS limit
Huffman Validation: Detect improper padding (too many 1 bits)
Integer Overflow: Handle variable-length integers safely
Memory Management: Allocate/evict table entries efficiently

Encoder Strategies:

Table Utilization: Good encoders maximize table usage for repeated headers
Sensitivity Detection: Mark cookies, auth tokens as never-indexed
Size Optimization: Choose Huffman vs. raw based on actual size
Entry Priority: Decide which headers to add to limited table space

hpack_decoder.pseudo

Pseudocode

// Simplified HPACK decoder logic
function decodeHeaderBlock(bytes):
    headers = []
    i = 0
    
    while i < bytes.length:
        firstByte = bytes[i]
        
        if firstByte & 0x80:  // Indexed header (1xxxxxxx)
            index = decodeInteger(bytes, i, 7)
            name, value = lookupTable(index)
            headers.add(name, value)
            
        else if firstByte & 0x40:  // Literal with indexing (01xxxxxx)
            nameIndex = decodeInteger(bytes, i, 6)
            if nameIndex > 0:
                name = lookupTable(nameIndex).name
            else:
                name = decodeString(bytes, i)
            value = decodeString(bytes, i)
            headers.add(name, value)
            dynamicTable.add(name, value)  // Add to table!
            
        else if firstByte & 0x20:  // Table size update (001xxxxx)
            newSize = decodeInteger(bytes, i, 5)
            dynamicTable.setMaxSize(newSize)
            
        else:  // Literal without/never indexing
            // Similar to 0x40 case but don't add to table
            ...
    
    return headers

Common Implementation Pitfalls:

Issue	Symptom	Prevention
Table desync	Garbage headers after N requests	Process all header blocks in order
Integer overflow	Connection reset / crash	Limit maximum integer value
Huffman padding	Protocol error	Validate ≤7 padding bits
Table size exceeded	Memory exhaustion	Enforce SETTINGS limit strictly
Missing never-indexed	Security vulnerability	Default sensitive headers to never-index

Testing HPACK Implementations

Performance Characteristics

HPACK's real-world performance depends on traffic patterns, table size settings, and implementation quality.

Compression Ratios:

Typical compression ratios observed:

Scenario	Compression Ratio	Notes
Single request	40-50%	Only static table + Huffman
After 10 requests	70-80%	Dynamic table warming up
Steady state	85-95%	Full table utilization
API traffic (JSON)	80-90%	High header redundancy
Mixed origins	60-75%	Less repetition across origins

REST APIs benefit enormously—every request has identical Accept, Content-Type, and Authorization headers.

Table Size Impact:

Larger dynamic tables increase compression but consume memory:

Table Size	Memory Per Connection	Compression Benefit
0 bytes	~0	No dynamic compression
4,096 bytes (default)	~4KB	Good for most traffic
16,384 bytes	~16KB	Better for large cookie/token sites
65,536 bytes	~64KB	Maximum practical benefit

Servers with millions of connections must balance table size against memory. A 16KB table with 1M connections = 16GB just for HPACK tables!

Optimizing HPACK Performance

•Consistent Header Order: Send headers in same order to maximize table hits
•Minimize Header Variation: Avoid unnecessary per-request header changes
•Appropriate Table Size: Increase for high-header-volume applications
•Header Normalization: Lowercase names, consistent value formats
•Avoid Large Cookies: Large cookies evict other table entries quickly

HPACK vs QPACK

Summary: HPACK Eliminates Header Redundancy

HPACK represents a carefully-designed solution to HTTP header redundancy, balancing compression efficiency against security requirements.

Key Takeaways

•Headers are hugely redundant — Typical pages waste tens of KB on repeated User-Agent, Cookie, and Accept headers.
•HPACK uses three mechanisms — Static table (61 predefined entries), dynamic table (connection-specific), and Huffman encoding (bit-level compression).
•Static table handles common cases — :method: GET, :path: /, :scheme: https encode in 1 byte each.
•Dynamic table learns from traffic — Headers are indexed and reused, achieving 85-95% compression in steady state.
•Huffman compresses literals — Variable-length codes save 25-35% on string values.
•Security is foundational — Never-indexed literals and fixed Huffman tables prevent compression oracle attacks like CRIME.
•Stateful compression requires synchronization — Encoder and decoder must process all header blocks in order.

What's Next:

Page Complete

3 / 5