RFC 9204
QPACK: Field Compression for HTTP/3
Internet Engineering Task Force (IETF) ๐ โ RFC 9204 โจ
okay bestie, the title block is giving professional networking energy ๐ผโจ so here's the tea: this one is by C. Krasic (Google), M. Bishop (Akamai Technologies), and A. Frindell, Ed. (Facebook). It's a Standards Track document, which means it's the real deal, not a vibes-only memo ๐ . It came out in June 2022, and it's officially RFC 9204 ๐ฆ.
Also, the title block doesn't say it obsoletes or updates anything, so this one stands on its own, no drama ๐.
The title is QPACK: Field Compression for HTTP/3 ๐ธ. ISSN is 2070-1721 if you're into that.
Abstract ๐ซถ
okay so the abstract is short and sweet ๐. It defines QPACK, a compression format for efficiently representing HTTP fields, and it's meant to be used in HTTP/3. It's basically a glow-up of HPACK, designed to reduce head-of-line blocking ๐ฅ.
Status of This Memo ๐
This is an Internet Standards Track document ๐.
It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG) โจ. If you want more info on Internet Standards, check out Section 2 of RFC 7841.
Info on the current status, errata, and how to give feedback is at https://www.rfc-editor.org/info/rfc9204 ๐ง.
Copyright Notice ๐
Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved ๐ .
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as of the publication date. Please read these carefully because they spell out your rights and restrictions ๐. Code components pulled from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Revised BSD License ๐.
Table of Contents ๐บ๏ธ
1. Introduction
1.1. Conventions and Definitions
1.2. Notational Conventions
2. Compression Process Overview
2.1. Encoder
2.1.1. Limits on Dynamic Table Insertions
2.1.2. Blocked Streams
2.1.3. Avoiding Flow-Control Deadlocks
2.1.4. Known Received Count
2.2. Decoder
2.2.1. Blocked Decoding
2.2.2. State Synchronization
2.2.3. Invalid References
3. Reference Tables
3.1. Static Table
3.2. Dynamic Table
3.2.1. Dynamic Table Size
3.2.2. Dynamic Table Capacity and Eviction
3.2.3. Maximum Dynamic Table Capacity
3.2.4. Absolute Indexing
3.2.5. Relative Indexing
3.2.6. Post-Base Indexing
4. Wire Format
4.1. Primitives
4.1.1. Prefixed Integers
4.1.2. String Literals
4.2. Encoder and Decoder Streams
4.3. Encoder Instructions
4.3.1. Set Dynamic Table Capacity
4.3.2. Insert with Name Reference
4.3.3. Insert with Literal Name
4.3.4. Duplicate
4.4. Decoder Instructions
4.4.1. Section Acknowledgment
4.4.2. Stream Cancellation
4.4.3. Insert Count Increment
4.5. Field Line Representations
4.5.1. Encoded Field Section Prefix
4.5.2. Indexed Field Line
4.5.3. Indexed Field Line with Post-Base Index
4.5.4. Literal Field Line with Name Reference
4.5.5. Literal Field Line with Post-Base Name Reference
4.5.6. Literal Field Line with Literal Name
5. Configuration
6. Error Handling
7. Security Considerations
7.1. Probing Dynamic Table State
7.1.1. Applicability to QPACK and HTTP
7.1.2. Mitigation
7.1.3. Never-Indexed Literals
7.2. Static Huffman Encoding
7.3. Memory Consumption
7.4. Implementation Limits
8. IANA Considerations
8.1. Settings Registration
8.2. Stream Type Registration
8.3. Error Code Registration
9. References
9.1. Normative References
9.2. Informative References
Appendix A. Static Table
Appendix B. Encoding and Decoding Examples
B.1. Literal Field Line with Name Reference
B.2. Dynamic Table
B.3. Speculative Insert
B.4. Duplicate Instruction, Stream Cancellation
B.5. Dynamic Table Insert, Eviction
Appendix C. Sample Single-Pass Encoding Algorithm
Acknowledgments
Authors' Addresses1. Introduction ๐ฆ
okay so the QUIC transport protocol ([QUIC-TRANSPORT]) was built to support HTTP semantics, and its design covers a lot of what HTTP/2 ([HTTP/2]) does ๐ . HTTP/2 uses HPACK ([RFC7541]) to compress the header and trailer sections. If HPACK were used for HTTP/3 ([HTTP/3]), it would cause head-of-line blocking for field sections, because HPACK assumes everything across all streams arrives in one total order ๐.
QPACK borrows core ideas from HPACK but is redesigned to stay correct when things arrive out of order, and implementations get to choose how to balance resilience against head-of-line blocking with the best compression ratio โจ. The goal is to get really close to HPACK's compression ratio while having way less head-of-line blocking under the same loss conditions ๐.
1.1. Conventions and Definitions ๐
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here ๐.
These terms show up in this document:
HTTP fields: metadata sent as part of an HTTP message. It covers both header and trailer fields. People often say "headers" for HTTP header fields and trailer fields, but this doc says "fields" to be more general ๐ธ.
HTTP field line: a name-value pair sent as part of an HTTP field section. See Sections 6.3 and 6.5 of [HTTP] ๐ง.
HTTP field value: the data tied to a field name. It's built from all the field line values with that name in the section, joined together with comma separators ๐.
Field section: an ordered collection of HTTP field lines attached to an HTTP message. A field section can have multiple field lines with the same name, and it can even have duplicate field lines. An HTTP message can include both a header section and a trailer section ๐.
Representation: an instruction that represents a field line, possibly by pointing at the dynamic and static tables ๐ฆ.
Encoder: an implementation that encodes field sections โจ.
Decoder: an implementation that decodes encoded field sections ๐ซถ.
Absolute Index: a unique index for each entry in the dynamic table ๐ฅ.
Base: a reference point for relative and post-Base indices. Representations that reference dynamic table entries are relative to a Base ๐.
Insert Count: the total number of entries inserted into the dynamic table ๐.
Note that QPACK is a name, not an abbreviation ๐ .
1.2. Notational Conventions ๐
Diagrams in this document use the format from Section 3.1 of [RFC2360], with these extra conventions ๐:
x (A) Indicates that x is A bits long.
x (A+) Indicates that x uses the prefixed integer encoding defined
in Section 4.1.1, beginning with an A-bit prefix.
x ... Indicates that x is variable length and extends to the end of
the region.2. Compression Process Overview ๐ธ
Like HPACK, QPACK uses two tables to map field lines ("headers") to indices ๐. The static table (Section 3.1) is predefined and holds common header field lines (some of them with an empty value). The dynamic table (Section 3.2) gets built up over the course of the connection, and the encoder can use it to index both header and trailer field lines in the encoded field sections โจ.
QPACK also defines unidirectional streams for sending instructions from encoder to decoder and the other way around ๐ง.
2.1. Encoder ๐ฆ
An encoder turns a header or trailer section into a series of representations, emitting either an indexed or a literal representation for each field line in the list. See Section 4.5 ๐ . Indexed representations get high compression by swapping the literal name (and maybe the value) for an index into the static or dynamic table ๐ฅ. References to the static table and literal representations don't need any dynamic state, so they never risk head-of-line blocking ๐. References to the dynamic table do risk head-of-line blocking if the encoder hasn't received an acknowledgment saying the entry is available at the decoder ๐.
An encoder MAY insert any entry it chooses into the dynamic table. It isn't limited to the field lines it's compressing ๐.
QPACK keeps the ordering of field lines within each field section. An encoder MUST emit field representations in the order they appear in the input field section ๐ซถ.
QPACK puts the burden of optional state tracking on the encoder, which keeps decoders relatively simple ๐.
2.1.1. Limits on Dynamic Table Insertions ๐ง
Inserting entries into the dynamic table might not be possible if the table holds entries that can't be evicted ๐.
A dynamic table entry can't be evicted right after insertion, even if nothing has referenced it yet. Once the insertion has been acknowledged and there are no outstanding references to the entry in unacknowledged representations, the entry becomes evictable ๐. Note that references on the encoder stream never block eviction of an entry, since those references are guaranteed to be processed before the instruction that evicts the entry โจ.
If the dynamic table doesn't have enough room for a new entry without evicting other entries, and the entries that would be evicted aren't evictable, the encoder MUST NOT insert that entry into the dynamic table (this includes duplicates of existing entries). To avoid this, an encoder that uses the dynamic table has to track each dynamic table entry referenced by each field section until the decoder acknowledges those representations. See Section 4.4.1 ๐ซถ.
This is the first part of 10! More parts are coming, so stay tuned, bestie ๐๐
2.1.1.1. Avoiding Prohibited Insertions ๐
okay so the encoder doesn't want to get stuck unable to add new entries ๐ญ the move is to just avoid referencing entries that are close to getting evicted ๐๏ธ. instead of referencing one of those, the encoder can send a Duplicate instruction (Section 4.3.4) and reference the duplicate instead ๐ง
deciding which entries are "too close to eviction" is literally the encoder's call ๐ one vibe check is to aim for a fixed amount of free room in the dynamic table, either unused space or space that can be reclaimed by evicting non-blocking entries โจ. to pull this off, the encoder can keep a draining index, which is the smallest absolute index (Section 3.2.4) in the dynamic table that it will emit a reference for. every time new entries get inserted, the encoder bumps the draining index up so the older part of the table stays off-limits for new references ๐ฆ. if the encoder doesn't create new references to anything below the draining index, the number of unacknowledged references to those entries will eventually hit zero, and then they can be evicted ๐ซถ
<-- Newer Entries Older Entries -->
(Larger Indices) (Smaller Indices)
+--------+---------------------------------+----------+
| Unused | Referenceable | Draining |
| Space | Entries | Entries |
+--------+---------------------------------+----------+
^ ^ ^
| | |
Insertion Point Draining Index Dropping
PointFigure 1: Draining Dynamic Table Entries ๐
2.1.2. Blocked Streams ๐ง
because QUIC doesn't guarantee order between data on different streams, a decoder might run into a representation that references a dynamic table entry it hasn't received yet ๐ฌ
each encoded field section carries a Required Insert Count (Section 4.5.1), which is the lowest possible value for the Insert Count that the field section can be decoded with. if the field section uses references to the dynamic table, the Required Insert Count is one larger than the largest absolute index of all referenced dynamic table entries. if there are no references to the dynamic table, the Required Insert Count is zero ๐
when the decoder gets an encoded field section whose Required Insert Count is greater than its own Insert Count, the stream can't be processed right away and is considered "blocked"; see Section 2.2.1 ๐
the decoder sets an upper bound on how many streams can be blocked using the SETTINGS_QPACK_BLOCKED_STREAMS setting; see Section 5. An encoder MUST limit the number of streams that could become blocked to the value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. If a decoder encounters more blocked streams than it promised to support, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED. bestie that is a hard no ๐
note that the decoder might not get blocked on every stream that risks it ๐ซ
an encoder gets to decide whether it wants to risk a stream getting blocked. if SETTINGS_QPACK_BLOCKED_STREAMS allows it, compression can often get better by referencing dynamic table entries that are still in transit, but if there's loss or reordering, the stream can get blocked at the decoder ๐. the safe play is only referencing entries that have been acknowledged, but that could mean sending literals. since literals make the encoded field section bigger, the encoder can end up blocked on congestion or flow-control limits ๐ญ
2.1.3. Avoiding Flow-Control Deadlocks ๐
writing instructions on streams that are limited by flow control can cause deadlocks ๐
a decoder might hold off issuing flow-control credit on the stream that carries an encoded field section until the necessary updates arrive on the encoder stream. if granting flow-control credit on the encoder stream (or the connection as a whole) depends on data being consumed and released on the stream carrying the encoded field section, a deadlock might happen ๐
more generally, a stream with a large instruction can get deadlocked if the decoder withholds flow-control credit until the whole instruction has been received ๐งฑ
to dodge these deadlocks, an encoder SHOULD NOT write an instruction unless there's enough stream and connection flow-control credit available for the entire instruction โจ
2.1.4. Known Received Count ๐ฌ
the Known Received Count is the total number of dynamic table insertions and duplications acknowledged by the decoder. the encoder tracks it so it knows which dynamic table entries can be referenced without potentially blocking a stream, and the decoder tracks it so it can send Insert Count Increment instructions ๐
a Section Acknowledgment instruction (Section 4.4.1) implies the decoder has received all the dynamic table state needed to decode that field section. if the Required Insert Count of the acknowledged field section is greater than the current Known Received Count, the Known Received Count gets updated to that Required Insert Count value ๐
an Insert Count Increment instruction (Section 4.4.3) increases the Known Received Count by its Increment parameter. see Section 2.2.2.3 for guidance ๐ง
2.2. Decoder ๐
as in HPACK, the decoder processes a series of representations and emits the corresponding field sections. it also processes instructions received on the encoder stream that modify the dynamic table. heads up: encoded field sections and encoder stream instructions arrive on separate streams ๐ this is unlike HPACK, where encoded field sections (header blocks) can contain instructions that modify the dynamic table, and there's no dedicated stream of HPACK instructions ๐ฆ
The decoder MUST emit field lines in the order their representations appear in the encoded field section ๐ซถ
2.2.1. Blocked Decoding ๐ซ
when an encoded field section comes in, the decoder examines the Required Insert Count. if it's less than or equal to the decoder's Insert Count, the field section can be processed immediately. otherwise, the stream the field section was received on becomes blocked ๐ค
while blocked, encoded field section data SHOULD remain in the blocked stream's flow-control window. this data is unusable until the stream becomes unblocked, and releasing flow control prematurely makes the decoder vulnerable to memory exhaustion attacks ๐จ A stream becomes unblocked when the Insert Count becomes greater than or equal to the Required Insert Count for all encoded field sections the decoder has started reading from the stream โ
Memory exhaustion attacks are no joke, bestie. Don't release that flow control early ๐
when processing encoded field sections, the decoder expects the Required Insert Count to equal the lowest possible value for the Insert Count with which the field section can be decoded, as laid out in Section 2.1.2. If it encounters a Required Insert Count smaller than expected, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED; see Section 2.2.3. If it encounters a Required Insert Count larger than expected, it MAY treat this as a connection error of type QPACK_DECOMPRESSION_FAILED ๐ค
2.2.2. State Synchronization ๐ค
the decoder signals the following events by emitting decoder instructions (Section 4.4) on the decoder stream.
2.2.2.1. Completed Processing of a Field Section โ
after the decoder finishes decoding a field section encoded using representations containing dynamic table references, it MUST emit a Section Acknowledgment instruction (Section 4.4.1). a stream may carry multiple field sections for intermediate responses, trailers, and pushed requests ๐ฆ the encoder interprets each Section Acknowledgment instruction as acknowledging the earliest unacknowledged field section containing dynamic table references sent on the given stream ๐
2.2.2.2. Abandonment of a Stream ๐ช
when an endpoint receives a stream reset before the end of a stream or before all encoded field sections are processed on that stream, or when it abandons reading of a stream, it generates a Stream Cancellation instruction; see Section 4.4.2. this signals to the encoder that all references to the dynamic table on that stream are no longer outstanding ๐ A decoder with a maximum dynamic table capacity (Section 3.2.3) equal to zero MAY omit sending Stream Cancellations, because the encoder cannot have any dynamic table references. an encoder can't infer from this instruction that any updates to the dynamic table have been received ๐
the Section Acknowledgment and Stream Cancellation instructions permit the encoder to remove references to entries in the dynamic table. when an entry with an absolute index lower than the Known Received Count has zero references, then it's considered evictable; see Section 2.1.1 ๐๏ธ
2.2.2.3. New Table Entries ๐
after receiving new table entries on the encoder stream, the decoder chooses when to emit Insert Count Increment instructions; see Section 4.4.3. emitting this instruction after adding each new dynamic table entry gives the encoder the timeliest feedback, but it could be redundant with other decoder feedback ๐ by delaying an Insert Count Increment instruction, the decoder might be able to coalesce multiple Insert Count Increment instructions or replace them entirely with Section Acknowledgments; see Section 4.4.1 โจ but delaying too long may lead to compression inefficiencies if the encoder waits for an entry to be acknowledged before using it โณ
2.2.3. Invalid References ๐จ
if the decoder encounters a reference in a field line representation to a dynamic table entry that has already been evicted, or that has an absolute index greater than or equal to the declared Required Insert Count (Section 4.5.1), it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED.
if the decoder encounters a reference in an encoder instruction to a dynamic table entry that has already been evicted, it MUST treat this as a connection error of type QPACK_ENCODER_STREAM_ERROR.
3. Reference Tables ๐
unlike in HPACK, entries in the QPACK static and dynamic tables are addressed separately. the following sections describe how entries in each table are addressed ๐ง
3.1. Static Table ๐๏ธ
the static table consists of a predefined list of field lines, each of which has a fixed index over time. its entries are defined in Appendix A โจ
all entries in the static table have a name and a value. however, values can be empty (that is, have a length of 0). each entry is identified by a unique index ๐
note that the QPACK static table is indexed from 0, whereas the HPACK static table is indexed from 1 ๐
when the decoder encounters an invalid static table index in a field line representation, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED. if this index is received on the encoder stream, this MUST be treated as a connection error of type QPACK_ENCODER_STREAM_ERROR ๐
3.2. Dynamic Table ๐
okay so the dynamic table is basically a list of field lines kept in first-in, first-out order ๐. A QPACK encoder and decoder share one, and it starts out totally empty ๐ซถ. The encoder adds entries and tells the decoder about them through instructions on the encoder stream (see Section 4.3) โจ.
The dynamic table can hold duplicate entries, meaning entries with the same name AND the same value. Duplicate entries MUST NOT be treated as an error by the decoder ๐ , so no drama there ๐ .
Dynamic table entries can have empty values ๐ธ.
3.2.1. Dynamic Table Size ๐
The size of the table is just the sum of the sizes of all its entries ๐ง.
The size of one entry is its name's length in bytes, plus its value's length in bytes, plus 32 extra bytes ๐ง. Those lengths get counted without Huffman encoding applied, so you use the raw, unencoded lengths ๐ค.
3.2.2. Dynamic Table Capacity and Eviction ๐งน
The encoder sets the capacity, which is the upper limit on the table's size. It starts at zero. To actually start using the table, the encoder sends a Set Dynamic Table Capacity instruction (Section 4.3.1) with a non-zero capacity ๐.
Before a new entry goes in, entries get evicted from the end of the table until the table size is less than or equal to (table capacity - size of new entry). The encoder MUST NOT cause a dynamic table entry to be evicted unless that entry is evictable; see Section 2.1.1 ๐. Then the new entry gets added. If the encoder tries to add an entry that's bigger than the dynamic table capacity, that's an error, and the decoder MUST treat this as a connection error of type QPACK_ENCODER_STREAM_ERROR ๐จ.
A new entry can reference an entry that's about to get evicted when the new entry goes in. Implementations are cautioned to avoid deleting the referenced name or value if the referenced entry is evicted before the new entry is inserted โ ๏ธ.
Heads up, bestie: if you evict an entry that a new entry is pointing at, don't delete the name or value it still needs ๐ญ.
Whenever the encoder reduces the dynamic table capacity (Section 4.3.1), entries get evicted from the end until the table size fits under the new capacity ๐. Setting the capacity to 0 can wipe the table completely, and you can bring it back later by restoring a capacity ๐ฆ.
3.2.3. Maximum Dynamic Table Capacity ๐
To keep the decoder's memory in check, the decoder caps the maximum capacity the encoder is allowed to set ๐ง . In HTTP/3, that cap is whatever SETTINGS_QPACK_MAX_TABLE_CAPACITY the decoder sent; see Section 5 โจ. The encoder MUST NOT set a capacity above that maximum, but it can pick something lower; see Section 4.3.1 ๐ซง.
For clients using 0-RTT data in HTTP/3, the server's max table capacity is the remembered value of the setting, or zero if it wasn't sent before ๐ฐ๏ธ. When the client's 0-RTT value of the SETTING is zero, the server MAY set it to a non-zero value in its SETTINGS frame. If the remembered value is non-zero, the server MUST send the same non-zero value in its SETTINGS frame. If the server specifies any other value, or leaves SETTINGS_QPACK_MAX_TABLE_CAPACITY out of its SETTINGS, the encoder must treat this as a connection error of type QPACK_DECODER_STREAM_ERROR ๐.
For clients NOT using 0-RTT data (whether 0-RTT wasn't attempted or got rejected), and for all HTTP/3 servers, the max table capacity is 0 until the encoder processes a SETTINGS frame with a non-zero value of SETTINGS_QPACK_MAX_TABLE_CAPACITY ๐ผ.
When the max table capacity is zero, the encoder MUST NOT insert entries into the dynamic table, and it MUST NOT send any encoder instructions on the encoder stream ๐.
3.2.4. Absolute Indexing ๐ข
Every entry gets an absolute index that stays fixed for its whole life ๐ . The first entry inserted gets absolute index 0, and the index goes up by one with each insertion after that ๐.
3.2.5. Relative Indexing ๐งญ
Relative indices start at zero and count in the opposite direction from absolute indices ๐. Which entry has relative index 0 depends on the context of the reference ๐.
In encoder instructions (Section 4.3), relative index 0 means the most recently inserted value in the dynamic table. Heads up: the entry a given relative index points to will change while you're interpreting instructions on the encoder stream ๐.
+-----+---------------+-------+
| n-1 | ... | d | Absolute Index
+ - - +---------------+ - - - +
| 0 | ... | n-d-1 | Relative Index
+-----+---------------+-------+
^ |
| V
Insertion Point Dropping Point
n = count of entries inserted
d = count of entries dropped
Figure 2: Example Dynamic Table Indexing - Encoder StreamUnlike encoder instructions, relative indices in field line representations are relative to the Base at the beginning of the encoded field section; see Section 4.5.1 ๐งธ. This keeps references stable even if encoded field sections and dynamic table updates get processed out of order ๐ฏ.
In a field line representation, relative index 0 refers to the entry with absolute index equal to Base - 1 ๐ซถ.
Base
|
V
+-----+-----+-----+-----+-------+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+ - +-----+ - +
| 0 | ... | n-d-3 | Relative Index
+-----+-----+-------+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2
Figure 3: Example Dynamic Table Indexing - Relative Index in
Representation3.2.6. Post-Base Indexing ๐ฆ
Post-Base indices are used in field line representations for entries whose absolute index is greater than or equal to Base ๐. They start at 0 for the entry with absolute index equal to Base, and they count up in the same direction as the absolute index ๐.
Post-Base indices let an encoder process a field section in a single pass, and they let it reference entries added while processing this field section (or other ones) ๐ช.
Base
|
V
+-----+-----+-----+-----+-----+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+-----+-----+-----+
| 1 | 0 | Post-Base Index
+-----+-----+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2
Figure 4: Example Dynamic Table Indexing - Post-Base Index in
Representation4. Wire Format โจ
4.1. Primitives ๐งฉ
4.1.1. Prefixed Integers ๐
The prefixed integer from Section 5.1 of [RFC7541] gets used a LOT in this doc ๐. The format from [RFC7541] is used unmodified. Just know that QPACK uses some prefix sizes that HPACK never actually used ๐.
QPACK implementations MUST be able to decode integers up to and including 62 bits long ๐ช.
4.1.2. String Literals ๐
The string literal from Section 5.2 of [RFC7541] also shows up everywhere, and it includes optional Huffman encoding ๐ซง.
In HPACK, string literals begin on a byte boundary. They start with a single-bit flag called 'H' in this document (it says whether the string is Huffman encoded), then the string length as a 7-bit prefix integer, then the indicated number of bytes of data ๐ญ. When Huffman encoding is on, the Huffman table from Appendix B of [RFC7541] is used without modification, and the length is the size of the string after encoding ๐ง.
This document stretches string literals by letting them begin somewhere other than a byte boundary ๐. An "N-bit prefix string literal" starts mid-byte, with the first (8-N) bits belonging to a previous field ๐ฆ. It uses one bit for the Huffman flag, then the length of the encoded string as an (N-1)-bit prefix integer ๐งฎ. The prefix size, N, can be anything from 2 to 8, inclusive ๐. The rest of the string literal stays unmodified ๐ .
A string literal with no prefix length noted is an 8-bit prefix string literal, and it follows the definitions in [RFC7541] without modification ๐ซถ.
4.2. Encoder and Decoder Streams ๐
QPACK defines two unidirectional stream types ๐:
- An encoder stream is a unidirectional stream of type
0x02. It carries an unframed sequence of encoder instructions from the encoder to the decoder ๐ค. - A decoder stream is a unidirectional stream of type
0x03. It carries an unframed sequence of decoder instructions from the decoder to the encoder ๐ฅ.
HTTP/3 endpoints contain a QPACK encoder and decoder ๐งโ๐คโ๐ง. Each endpoint MUST initiate, at most, one encoder stream and, at most, one decoder stream. Receiving a second instance of either stream type MUST be treated as a connection error of type H3_STREAM_CREATION_ERROR ๐ซ.
The sender MUST NOT close either of these streams, and the receiver MUST NOT request that the sender close either of them ๐. Closing either unidirectional stream type MUST be treated as a connection error of type H3_CLOSED_CRITICAL_STREAM ๐.
An endpoint MAY avoid creating an encoder stream if it won't be used. For example, that happens if its encoder doesn't want to use the dynamic table, or if the maximum dynamic table size the peer permits is zero ๐.
An endpoint MAY avoid creating a decoder stream if its decoder sets the maximum capacity of the dynamic table to zero ๐ซง.
An endpoint MUST allow its peer to create an encoder stream and a decoder stream, even if the connection's settings prevent their use ๐ค.
4.3. Encoder Instructions โ๏ธ
An encoder sends encoder instructions on the encoder stream to set the capacity of the dynamic table and to add dynamic table entries ๐. Instructions that add table entries can use existing entries to avoid sending redundant information โป๏ธ. The name can be sent as a reference to an existing entry in the static or the dynamic table, or as a string literal ๐งถ. For entries that already exist in the dynamic table, the full entry can also be used by reference, which creates a duplicate entry ๐ฏ.
4.3.1. Set Dynamic Table Capacity โจ
okay bestie, so this is how the encoder tells the decoder "hey, the dynamic table is changing size" ๐ it uses an instruction that starts with the 001 3-bit pattern ๐
, and then the new capacity comes after it as an integer with a 5-bit prefix (go peek at Section 4.1.1 if you want the deets ๐ง).
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | Capacity (5+) |
+---+---+---+-------------------+
Figure 5: Set Dynamic Table Capacityngl the rule here is super strict ๐ฅ the new capacity MUST be lower than or equal to the limit from Section 3.2.3. in HTTP/3 that limit is the value of the SETTINGS_QPACK_MAX_TABLE_CAPACITY parameter (Section 5) that the decoder sent over ๐ซถ and if the decoder sees a new capacity that goes over that limit, it MUST treat it as a connection error of type QPACK_ENCODER_STREAM_ERROR ๐ no vibes, just shutdown.
shrinking the table can kick entries out ๐ฆ (see Section 3.2.2), but it MUST NOT evict anything that isn't evictable (Section 2.1.1) ๐ and changing the capacity doesn't get an acknowledgment, because this instruction doesn't insert an entry. it's giving minimal ๐
4.3.2. Insert with Name Reference ๐ธ
so here the encoder adds an entry where the field name matches one that's already in the static or dynamic table ๐ the instruction starts with the 1 1-bit pattern, and the second bit, the T bit, tells you which table it's pointing at ๐ the 6-bit prefix integer (Section 4.1.1) that follows finds the name entry. when T=1 the number is the static table index, and when T=0 it's the relative index in the dynamic table โจ
the field name reference is then followed by the field value as a string literal (Section 4.1.2) ๐
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | T | Name Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+
Figure 6: Insert Field Line -- Indexed Name4.3.3. Insert with Literal Name ๐ฆ
this one is for when the encoder adds an entry and both the name and the value are sent as string literals ๐ the instruction starts with the 01 2-bit pattern โจ
after that comes the name as a 6-bit prefix string literal, then the value as an 8-bit prefix string literal (Section 4.1.2) ๐ซถ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | H | Name Length (5+) |
+---+---+---+-------------------+
| Name String (Length bytes) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+
Figure 7: Insert Field Line -- New Name4.3.4. Duplicate ๐ฏ
the encoder can duplicate an entry that's already in the dynamic table ๐ the instruction starts with the 000 3-bit pattern, followed by the relative index of that existing entry as an integer with a 5-bit prefix (Section 4.1.1) ๐ง
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | Index (5+) |
+---+---+---+-------------------+
Figure 8: Duplicatethe existing entry gets reinserted into the dynamic table without resending the name or the value, and this is useful for avoiding a reference to an older entry that might block new entries from getting inserted ๐ it's giving efficiency, no cap ๐
4.4. Decoder Instructions ๐
the decoder sends decoder instructions on the decoder stream to tell the encoder what it's done with field sections and table updates, so everyone stays on the same page about the dynamic table ๐ซถ
4.4.1. Section Acknowledgment โ
after the decoder processes an encoded field section whose declared Required Insert Count isn't zero, it sends a Section Acknowledgment instruction ๐ this starts with the 1 1-bit pattern, followed by the field section's stream ID as a 7-bit prefix integer (Section 4.1.1) ๐
this instruction gets used the way Sections 2.1.4 and 2.2.2 describe ๐ฆ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Stream ID (7+) |
+---+---------------------------+
Figure 9: Section Acknowledgmentokay the big rule: if an encoder gets a Section Acknowledgment that refers to a stream where every encoded field section with a non-zero Required Insert Count has already been acknowledged, that MUST be treated as a connection error of type QPACK_DECODER_STREAM_ERROR ๐ no acking twice, bestie ๐
the Section Acknowledgment might bump up the Known Received Count (Section 2.1.4) โจ
4.4.2. Stream Cancellation ๐ซ
when a stream gets reset or the reading gets abandoned, the decoder sends a Stream Cancellation instruction ๐ธ it starts with the 01 2-bit pattern, followed by the stream ID of the affected stream as a 6-bit prefix integer ๐
this one is used as described in Section 2.2.2 ๐ง
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Stream ID (6+) |
+---+---+-----------------------+
Figure 10: Stream Cancellation4.4.3. Insert Count Increment ๐
the Insert Count Increment instruction starts with the 00 2-bit pattern, followed by the Increment as a 6-bit prefix integer ๐ it raises the Known Received Count (Section 2.1.4) by the value of the Increment parameter ๐ the decoder should send an Increment that brings the Known Received Count up to the total number of dynamic table insertions and duplications it's processed so far โจ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | Increment (6+) |
+---+---+-----------------------+
Figure 11: Insert Count Incrementif an encoder gets an Increment of zero, or an Increment that pushes the Known Received Count past what the encoder has actually sent, that MUST be treated as a connection error of type QPACK_DECODER_STREAM_ERROR ๐
4.5. Field Line Representations ๐
an encoded field section is made of a prefix and a possibly empty sequence of representations (defined in this section) ๐ฆ each representation matches one single field line ๐ these representations point at the static table or the dynamic table in a particular state, but they don't change that state ๐ซถ
encoded field sections get carried in frames on streams that the enclosing protocol defines ๐
4.5.1. Encoded Field Section Prefix ๐ง
every encoded field section starts with two integers ๐ธ the Required Insert Count is encoded as an integer with an 8-bit prefix, using the encoding from Section 4.5.1.1 โจ the Base is encoded as a Sign bit (S) and a Delta Base value with a 7-bit prefix (Section 4.5.1.2) ๐
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| Required Insert Count (8+) |
+---+---------------------------+
| S | Delta Base (7+) |
+---+---------------------------+
| Encoded Field Lines ...
+-------------------------------+
Figure 12: Encoded Field Section4.5.1.1. Required Insert Count ๐ข
the Required Insert Count tells you what state of the dynamic table is needed to process the encoded field section ๐ blocking decoders use it to figure out when it's safe to process the rest of the field section ๐
the encoder transforms the Required Insert Count like this before encoding ๐
if ReqInsertCount == 0:
EncInsertCount = 0
else:
EncInsertCount = (ReqInsertCount mod (2 * MaxEntries)) + 1here MaxEntries is the maximum number of entries the dynamic table can have ๐ซง the smallest entry has empty name and value strings and has a size of 32, so MaxEntries gets calculated as ๐งฎ
MaxEntries = floor( MaxTableCapacity / 32 )MaxTableCapacity is the maximum capacity of the dynamic table, as the decoder specifies it (Section 3.2.3) ๐
this encoding keeps the prefix short on long-lived connections โจ
the decoder can rebuild the Required Insert Count using an algorithm like this one ๐ง if the decoder runs into an EncodedInsertCount value that a conformant encoder could never have produced, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED ๐
TotalNumberOfInserts is the total number of inserts into the decoder's dynamic table ๐ฆ
FullRange = 2 * MaxEntries
if EncodedInsertCount == 0:
ReqInsertCount = 0
else:
if EncodedInsertCount > FullRange:
Error
MaxValue = TotalNumberOfInserts + MaxEntries
# MaxWrapped is the largest possible value of
# ReqInsertCount that is 0 mod 2 * MaxEntries
MaxWrapped = floor(MaxValue / FullRange) * FullRange
ReqInsertCount = MaxWrapped + EncodedInsertCount - 1
# If ReqInsertCount exceeds MaxValue, the Encoder's value
# must have wrapped one fewer time
if ReqInsertCount > MaxValue:
if ReqInsertCount <= FullRange:
Error
ReqInsertCount -= FullRange
# Value of 0 must be encoded as 0.
if ReqInsertCount == 0:
Errorfor example, if the dynamic table is 100 bytes, then the Required Insert Count gets encoded modulo 6 ๐ if a decoder has received 10 inserts, then an encoded value of 4 means the Required Insert Count is 9 for the field section ๐ซถ this math is lowkey wild but it checks out ๐
4.5.1.2. Base ๐ฆ
okay so the Base is what you use to resolve references in the dynamic table, as described in Section 3.2.5. ๐
to save space, the Base isn't sent as-is. It's encoded relative to the Required Insert Count, using a one-bit Sign (that's the 'S' in Figure 12) plus the Delta Base value. ๐ง If the Sign bit is 0, the Base is greater than or equal to the Required Insert Count, so the decoder adds Delta Base to the Required Insert Count to get the Base. If the Sign bit is 1, the Base is less than the Required Insert Count, so the decoder subtracts Delta Base from the Required Insert Count and subtracts one to get the Base. the math looks like this:
if Sign == 0:
Base = ReqInsertCount + DeltaBase
else:
Base = ReqInsertCount - DeltaBase - 1a single-pass encoder figures out the Base before it encodes a field section. ๐ if the encoder inserted entries into the dynamic table while encoding that same field section and then references them, the Required Insert Count ends up greater than the Base. so the encoded difference is negative and the Sign bit is set to 1. if the field section didn't reference the most recent entry in the table and didn't insert anything new, the Base ends up greater than the Required Insert Count instead. the encoded difference is positive, so the Sign bit is 0. ๐ธ
the Base MUST NOT be negative. ๐ the protocol might work with a negative Base using post-Base indexing, but it's unnecessary and inefficient, so no thank you. an endpoint MUST treat a field block with a Sign bit of 1 as invalid if the Required Insert Count is less than or equal to Delta Base. that's a hard no. ๐
an encoder that produces table updates before it encodes a field section might set the Base to the Required Insert Count. in that case, both the Sign bit and Delta Base are set to zero. โจ
a field section that was encoded without any references to the dynamic table can use any value for the Base. setting Delta Base to zero is one of the most efficient encodings, which is very on-brand for it. ๐
for example, say the Required Insert Count is 9 and a decoder receives a Sign bit of 1 and a Delta Base of 2. that sets the Base to 6 and enables post-Base indexing for three entries. in this example, a relative index of 1 refers to the fifth entry that was added to the table, and a post-Base index of 1 refers to the eighth entry. ๐ฆ๐
4.5.2. Indexed Field Line ๐
an indexed field line representation identifies an entry in the static table, or an entry in the dynamic table with an absolute index that's less than the Base. ๐
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | T | Index (6+) |
+---+---+-----------------------+Figure 13: Indexed Field Line
this one starts with the '1' 1-bit pattern, followed by the 'T' bit, which tells you whether the reference is into the static or the dynamic table. ๐ฅ the 6-bit prefix integer (Section 4.1.1) that comes next is used to find the table entry for the field line. when T=1, the number is the static table index. when T=0, the number is the relative index of the entry in the dynamic table. ๐
4.5.3. Indexed Field Line with Post-Base Index โญ
an indexed field line with post-Base index representation identifies an entry in the dynamic table with an absolute index greater than or equal to the Base. ๐งโโ๏ธ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | Index (4+) |
+---+---+---+---+---------------+Figure 14: Indexed Field Line with Post-Base Index
this starts with the '0001' 4-bit pattern. then comes the post-Base index (Section 3.2.6) of the matching field line, written as an integer with a 4-bit prefix. see Section 4.1.1. ๐ซถ
4.5.4. Literal Field Line with Name Reference ๐
a literal field line with name reference representation encodes a field line where the field name matches either the field name of an entry in the static table, or the field name of an entry in the dynamic table with an absolute index less than the Base. ๐ธ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | N | T |Name Index (4+)|
+---+---+---+---+---------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+Figure 15: Literal Field Line with Name Reference
this starts with the '01' 2-bit pattern. the bit right after that is 'N', which says whether an intermediary is allowed to add this field line to the dynamic table on later hops. ๐ when the 'N' bit is set, the encoded field line MUST always be encoded with a literal representation. and if a peer gets a field line represented as a literal with the 'N' bit set and wants to forward it, it MUST use a literal representation to do that. this bit exists to protect field values that would be at risk if they got compressed. see Section 7.1 for more details. ๐ฅ
the fourth bit, 'T', tells you whether the reference is to the static or the dynamic table. the 4-bit prefix integer (Section 4.1.1) after it finds the table entry for the field name. when T=1, the number is the static table index. when T=0, it's the relative index of the entry in the dynamic table. ๐ฆ
only the field name gets taken from the dynamic table entry. the field value is encoded as an 8-bit prefix string literal, see Section 4.1.2. ๐
4.5.5. Literal Field Line with Post-Base Name Reference ๐
a literal field line with post-Base name reference representation encodes a field line where the field name matches the field name of a dynamic table entry with an absolute index greater than or equal to the Base. ๐
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | N |NameIdx(3+)|
+---+---+---+---+---+-----------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+Figure 16: Literal Field Line with Post-Base Name Reference
this starts with the '0000' 4-bit pattern. the fifth bit is the 'N' bit, same as in Section 4.5.4. next up is a post-Base index of the dynamic table entry (Section 3.2.6), encoded as an integer with a 3-bit prefix. see Section 4.1.1. ๐ง
only the field name gets taken from the dynamic table entry. the field value is encoded as an 8-bit prefix string literal, see Section 4.1.2. โจ
4.5.6. Literal Field Line with Literal Name ๐
the literal field line with literal name representation encodes both a field name and a field value as string literals. ๐ธ
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |NameLen(3+)|
+---+---+---+---+---+-----------+
| Name String (Length bytes) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+Figure 17: Literal Field Line with Literal Name
this starts with the '001' 3-bit pattern. the fourth bit is the 'N' bit, same as in Section 4.5.4. then comes the name, written as a 4-bit prefix string literal, and then the value, written as an 8-bit prefix string literal. see Section 4.1.2. ๐
5. Configuration โ๏ธ
QPACK defines two settings for the HTTP/3 SETTINGS frame. ๐
SETTINGS_QPACK_MAX_TABLE_CAPACITY (0x01): the default value is zero. see Section 3.2 for usage. this is the equivalent of theSETTINGS_HEADER_TABLE_SIZEfrom HTTP/2. ๐ฆSETTINGS_QPACK_BLOCKED_STREAMS (0x07): the default value is zero. see Section 2.1.2. ๐
6. Error Handling ๐จ
the following error codes are defined for HTTP/3 to indicate failures of QPACK that stop the stream or connection from continuing. ๐
QPACK_DECOMPRESSION_FAILED (0x0200): the decoder failed to interpret an encoded field section, and it can't keep decoding that field section. ๐QPACK_ENCODER_STREAM_ERROR (0x0201): the decoder failed to interpret an encoder instruction received on the encoder stream. ๐QPACK_DECODER_STREAM_ERROR (0x0202): the encoder failed to interpret a decoder instruction received on the decoder stream. ๐ญ
7. Security Considerations ๐
this section describes the potential security concerns with QPACK. ๐
- Use of compression as a length-based oracle for verifying guesses about secrets that are compressed into a shared compression context. ๐ง
- Denial of service resulting from exhausting processing or memory capacity at a decoder. ๐จ
7.1. Probing Dynamic Table State ๐
QPACK reduces the encoded size of field sections by exploiting the redundancy inherent in protocols like HTTP. ๐ธ the ultimate goal is to reduce the amount of data required to send HTTP requests or responses. โจ
the compression context used to encode header and trailer fields can be probed by an attacker who can both define fields to be encoded and transmitted, and observe the length of those fields once they're encoded. ๐ฑ when an attacker can do both, they can adaptively modify requests to confirm guesses about the dynamic table state. if a guess gets compressed into a shorter length, the attacker can observe the encoded length and infer that the guess was correct. ๐ต๏ธโโ๏ธ
this is possible even over the Transport Layer Security Protocol ([TLS]) and the QUIC Transport Protocol ([QUIC-TRANSPORT]), because while TLS and QUIC provide confidentiality protection for content, they only provide a limited amount of protection for the length of that content. ๐
Note: Padding schemes only provide limited protection against an attacker with these capabilities, potentially only forcing an increased number of guesses to learn the length associated with a given guess. Padding schemes also work directly against compression by increasing the number of bits that are transmitted. ๐ โโ๏ธ
Attacks like CRIME ([CRIME]) demonstrated the existence of these general attacker capabilities. ๐ฅ the specific attack exploited the fact that DEFLATE ([RFC1951]) removes redundancy based on prefix matching. that let the attacker confirm guesses a character at a time, turning an exponential-time attack into a linear-time attack. ๐คฏ
7.1.1. Applicability to QPACK and HTTP โจ
okay so QPACK helps with attacks modeled on CRIME ([CRIME]) ๐, but it doesn't completely prevent them ๐. The trick is that it makes an attacker guess a whole field line at once instead of one character at a time ๐. The attacker can only learn whether a guess is right or wrong, so they're stuck brute-forcing the field values for a given field name. It's giving guessing game ๐ฒ
So whether someone can actually recover a specific field value depends on how much entropy the value has ๐ฆ. High-entropy values are unlikely to get recovered ๐ซถ, but low-entropy values are still vulnerable ๐ญ.
These attacks are possible any time two mutually distrustful entities have requests or responses on the same HTTP/3 connection ๐. If the shared QPACK compressor lets one entity add entries to the dynamic table, and the other entity can refer to those entries while encoding the field lines it picks, then the attacker (that second entity) can learn the state of the table just by watching the length of the encoded output ๐. Main character villain energy, not it ๐ โโ๏ธ.
For example, requests or responses from mutually distrustful entities can show up when an intermediary either:
- sends requests from multiple clients on a single connection toward an origin server, or
- takes responses from multiple origin servers and places them on a shared connection toward a client.
Web browsers also need to assume that requests made on the same connection by different web origins ([RFC6454]) are made by mutually distrustful entities ๐ธ. Other scenarios with mutually distrustful entities are also possible โจ.
7.1.2. Mitigation ๐ก๏ธ
okay so users of HTTP who need confidentiality for header or trailer fields can use values with enough entropy to make guessing infeasible ๐. BUT ngl this is impractical as a general solution ๐ฉ, because it forces all users of HTTP to take steps to mitigate attacks. It would put new constraints on how HTTP gets used, and nobody asked for that ๐ .
So instead of making HTTP users do the work, a QPACK implementation can constrain how compression is applied to limit the potential for dynamic table probing ๐ง. Lowkey the smarter move.
The ideal solution segregates access to the dynamic table based on the entity that's constructing the message ๐. Field values added to the table get attributed to an entity, and only the entity that created a particular value can extract that value. Private diary energy ๐.
To improve compression performance with this option, certain entries might be tagged as public ๐. For example, a web browser might make the values of the Accept-Encoding header field available in all requests, since that's not a secret ๐.
An encoder that doesn't have good knowledge of where field values came from might instead introduce a penalty for many field lines with the same field name and different values ๐ค. This penalty could mean that a large number of attempts to guess a field value end up with the field not being compared to the dynamic table entries in future messages, which effectively stops further guesses ๐ซ.
This response might be made inversely proportional to the length of the field value ๐. Disabling access to the dynamic table for a given field name might happen for shorter values more quickly, or with higher probability, than for longer values ๐.
This mitigation is most effective between two endpoints ๐ซถ. If messages get re-encoded by an intermediary that doesn't know which entity constructed a given message, the intermediary could accidentally merge compression contexts that the original encoder had specifically kept separate ๐.
Note: Simply removing entries corresponding to the field from the dynamic table can be ineffectual if the attacker has a reliable way of causing values to be reinstalled. For example, a request to load an image in a web browser typically includes the Cookie header field (a potentially highly valued target for this sort of attack), and websites can easily force an image to be loaded, thereby refreshing the entry in the dynamic table. ๐
7.1.3. Never-Indexed Literals ๐
implementations can also choose to protect sensitive fields by not compressing them, and instead encoding their values as literals ๐.
Refusing to insert a field line into the dynamic table only works if that refusal happens on all hops ๐ฆ. The never-indexed literal bit (see Section 4.5.4) can be used to signal to intermediaries that a particular value was intentionally sent as a literal ๐ฉ.
An intermediary MUST NOT re-encode a value that uses a literal representation with the 'N' bit set with another representation that would index it. ๐ซ If QPACK is used for re-encoding, a literal representation with the 'N' bit set MUST be used. If HPACK is used for re-encoding, the never-indexed literal representation (see Section 6.2.3 of [RFC7541]) MUST be used. โจ Non-negotiable, bestie.
Deciding to mark a field value as never indexed depends on several factors ๐ง . Since QPACK doesn't protect against guessing an entire field value, short or low-entropy values are more easily recovered by an adversary ๐ฌ. So an encoder might choose not to index values with low entropy ๐ธ.
An encoder might also choose not to index values for fields that are considered highly valuable or sensitive to recovery, like the Cookie or Authorization header fields ๐.
On the contrary, an encoder might prefer to index values for fields that have little or no value if they were exposed ๐. For instance, a User-Agent header field doesn't commonly vary between requests and gets sent to any server anyway. In that case, confirming that a particular User-Agent value has been used provides little value ๐คทโโ๏ธ.
Note that these criteria for deciding to use a never-indexed literal representation will evolve over time as new attacks are discovered ๐. Stay curious, stay updated ๐ฆ.
7.2. Static Huffman Encoding ๐ท
There is no currently known attack against a static Huffman encoding ๐. A study has shown that using a static Huffman encoding table created an information leakage ๐. However, that same study concluded that an attacker couldn't take advantage of this leakage to recover any meaningful amount of information (see [PETAL]) ๐. Phew, no drama ๐ .
7.3. Memory Consumption ๐ง
An attacker can try to cause an endpoint to exhaust its memory ๐ฑ. QPACK is designed to limit both the peak and the stable amounts of memory allocated by an endpoint ๐ก๏ธ.
QPACK uses the maximum size of the dynamic table and the maximum number of blocking streams to limit how much memory the encoder can make the decoder consume ๐. In HTTP/3, these values are controlled by the decoder through the settings parameters SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS, respectively (see Section 3.2.3 and Section 2.1.2) ๐ฆ. The limit on the size of the dynamic table takes into account the size of the data stored in the dynamic table, plus a small allowance for overhead ๐ฆ. The limit on the number of blocked streams is only a proxy for the maximum amount of memory required by the decoder ๐. The actual maximum will depend on how much memory the decoder uses to track each blocked stream ๐งฎ.
A decoder can limit the amount of state memory used for the dynamic table by setting an appropriate value for the maximum size of the dynamic table ๐. In HTTP/3, this is done by setting an appropriate value for the SETTINGS_QPACK_MAX_TABLE_CAPACITY parameter ๐. An encoder can limit the amount of state memory it uses by choosing a smaller dynamic table size than the decoder allows, and signaling this to the decoder (see Section 4.3.1) ๐ซถ.
A decoder can also limit the amount of state memory used for blocked streams by setting an appropriate value for the maximum number of blocked streams ๐ง. In HTTP/3, this is done by setting an appropriate value for the SETTINGS_QPACK_BLOCKED_STREAMS parameter โจ. Streams that risk becoming blocked consume no additional state memory on the encoder ๐.
An encoder allocates memory to track all dynamic table references in unacknowledged field sections ๐๏ธ. An implementation can directly limit the amount of state memory by only using as many references to the dynamic table as it wishes to track, and no signaling to the decoder is required ๐คซ. However, limiting references to the dynamic table will reduce compression effectiveness ๐. Trade-offs, bestie ๐ .
The amount of temporary memory consumed by an encoder or decoder can be limited by processing field lines sequentially ๐โโ๏ธ. A decoder implementation doesn't need to retain a complete list of field lines while decoding a field section ๐ธ. An encoder implementation doesn't need to retain a complete list of field lines while encoding a field section if it's using a single-pass algorithm ๐ง. Note that it might be necessary for an application to retain a complete list of field lines for other reasons. Even if QPACK doesn't force this to happen, application constraints might make it necessary ๐ซ .
While the negotiated limit on the dynamic table size accounts for much of the memory that can be consumed by a QPACK implementation, data that can't be immediately sent due to flow control isn't affected by this limit ๐ฐ. Implementations should limit the size of unsent data, especially on the decoder stream, where the flexibility to choose what to send is limited ๐ฏ. Possible responses to an excess of unsent data might include limiting the ability of the peer to open new streams, reading only from the encoder stream, or closing the connection ๐ช. Choose wisely ๐.
7.4. Implementation Limits ๐ฆ
An implementation of QPACK needs to make sure that large values for integers, long encodings for integers, or long string literals don't create security weaknesses ๐.
An implementation has to set a limit on the values it accepts for integers, as well as on the encoded length (see Section 4.1.1) ๐. In the same way, it has to set a limit on the length it accepts for string literals (see Section 4.1.2) โ๏ธ. These limits SHOULD be large enough to process the largest individual field the HTTP implementation can be configured to accept ๐.
If an implementation encounters a value larger than it is able to decode, this MUST be treated as a stream error of type QPACK_DECOMPRESSION_FAILED if it's on a request stream, or as a connection error of the appropriate type if it's on the encoder or decoder stream ๐ฅ. Big yikes if you ignore it ๐ญ.
8. IANA Considerations ๐
This document makes multiple registrations in the registries defined by [HTTP/3] ๐๏ธ. The allocations created by this document all get permanent status, and they list a change controller of the IETF and a contact of the HTTP working group (ietf-http-wg@w3.org) ๐.
8.1. Settings Registration โ๏ธ
This document specifies two settings ๐. The entries in the following table are registered in the "HTTP/3 Settings" registry established in [HTTP/3] ๐ .
+==========================+======+===============+=========+
| Setting Name | Code | Specification | Default |
+==========================+======+===============+=========+
| QPACK_MAX_TABLE_CAPACITY | 0x01 | Section 5 | 0 |
+--------------------------+------+---------------+---------+
| QPACK_BLOCKED_STREAMS | 0x07 | Section 5 | 0 |
+--------------------------+------+---------------+---------+
Table 1: Additions to the HTTP/3 Settings RegistryFor formatting reasons, the setting names here are abbreviated by removing the SETTINGS_ prefix ๐ (no cap, it's just for the table to fit ๐).
8.2. Stream Type Registration ๐
okay so this section is all about stream types ๐ this doc adds two of them, and they get registered in the "HTTP/3 Stream Types" registry that [HTTP/3] already set up. here's the lineup ๐
+======================+======+===============+========+
| Stream Type | Code | Specification | Sender |
+======================+======+===============+========+
| QPACK Encoder Stream | 0x02 | Section 4.2 | Both |
+----------------------+------+---------------+--------+
| QPACK Decoder Stream | 0x03 | Section 4.2 | Both |
+----------------------+------+---------------+--------+Table 2: Additions to the HTTP/3 Stream Types Registry
8.3. Error Code Registration ๐ฆ
this part is the error code era ๐ this doc specifies three error codes, and they get added to the "HTTP/3 Error Codes" registry from [HTTP/3]. the table is giving very clear vibes ๐ฅ
+============================+========+=============+===============+
| Name | Code |Description | Specification |
+============================+========+=============+===============+
| QPACK_DECOMPRESSION_FAILED | 0x0200 |Decoding of a| Section 6 |
| | |field section| |
| | |failed | |
+----------------------------+--------+-------------+---------------+
| QPACK_ENCODER_STREAM_ERROR | 0x0201 |Error on the | Section 6 |
| | |encoder | |
| | |stream | |
+----------------------------+--------+-------------+---------------+
| QPACK_DECODER_STREAM_ERROR | 0x0202 |Error on the | Section 6 |
| | |decoder | |
| | |stream | |
+----------------------------+--------+-------------+---------------+Table 3: Additions to the HTTP/3 Error Codes Registry
9. References ๐
the reading list, bestie ๐ง everything the doc leans on is in here, so go check it out if you want the full picture ๐
9.1. Normative References ๐
these are the must-reads, the ones the spec basically can't function without ๐
[HTTP] Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke,
Ed., "HTTP Semantics", STD 97, RFC 9110,
DOI 10.17487/RFC9110, June 2022,
<https://www.rfc-editor.org/info/rfc9110>.
[HTTP/3] Bishop, M., Ed., "HTTP/3", RFC 9114, DOI 10.17487/RFC9114,
June 2022, <https://www.rfc-editor.org/info/rfc9114>.
[QUIC-TRANSPORT]
Iyengar, J., Ed. and M. Thomson, Ed., "QUIC: A UDP-Based
Multiplexed and Secure Transport", RFC 9000,
DOI 10.17487/RFC9000, May 2021,
<https://www.rfc-editor.org/info/rfc9000>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC2360] Scott, G., "Guide for Internet Standards Writers", BCP 22,
RFC 2360, DOI 10.17487/RFC2360, June 1998,
<https://www.rfc-editor.org/info/rfc2360>.
[RFC7541] Peon, R. and H. Ruellan, "HPACK: Header Compression for
HTTP/2", RFC 7541, DOI 10.17487/RFC7541, May 2015,
<https://www.rfc-editor.org/info/rfc7541>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.9.2. Informative References ๐ง
these ones are the extra credit reading, the nice-to-know stuff that isn't strictly required โจ
[CRIME] Wikipedia, "CRIME", May 2015, <http://en.wikipedia.org/w/
index.php?title=CRIME&oldid=660948120>.
[HTTP/2] Thomson, M., Ed. and C. Benfield, Ed., "HTTP/2", RFC 9113,
DOI 10.17487/RFC9113, June 2022,
<https://www.rfc-editor.org/info/rfc9113>.
[PETAL] Tan, J. and J. Nahata, "PETAL: Preset Encoding
Table Information Leakage", April 2013,
<http://www.pdl.cmu.edu/PDL-FTP/associated/CMU-PDL-13-106.pdf>.
[RFC1951] Deutsch, P., "DEFLATE Compressed Data Format Specification
version 1.3", RFC 1951, DOI 10.17487/RFC1951, May 1996,
<https://www.rfc-editor.org/info/rfc1951>.
[RFC6454] Barth, A., "The Web Origin Concept", RFC 6454,
DOI 10.17487/RFC6454, December 2011,
<https://www.rfc-editor.org/info/rfc6454>.
[TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/info/rfc8446>.Appendix A. Static Table ๐
okay last stop for this part ๐ซถ the static table was built by digging through real Internet traffic from 2018 and grabbing the most common header fields, after filtering out some unsupported and non-standard values. because of how it was made, a few entries can be a bit inconsistent or show up more than once with values that are similar but not exactly the same ๐ the order is also tuned so the most common header fields get encoded with the fewest bytes possible, which is honestly so smart ๐ง โจ
okay bestie, this is literally the ultimate cheat sheet ๐ static table entries 0 through 76, served fresh ๐ง
+=======+==================================+=======================+
| Index | Name | Value |
+=======+==================================+=======================+
| 0 | :authority | |
+-------+----------------------------------+-----------------------+
| 1 | :path | / |
+-------+----------------------------------+-----------------------+
| 2 | age | 0 |
+-------+----------------------------------+-----------------------+
| 3 | content-disposition | |
+-------+----------------------------------+-----------------------+
| 4 | content-length | 0 |
+-------+----------------------------------+-----------------------+
| 5 | cookie | |
+-------+----------------------------------+-----------------------+
| 6 | date | |
+-------+----------------------------------+-----------------------+
| 7 | etag | |
+-------+----------------------------------+-----------------------+
| 8 | if-modified-since | |
+-------+----------------------------------+-----------------------+
| 9 | if-none-match | |
+-------+----------------------------------+-----------------------+
| 10 | last-modified | |
+-------+----------------------------------+-----------------------+
| 11 | link | |
+-------+----------------------------------+-----------------------+
| 12 | location | |
+-------+----------------------------------+-----------------------+
| 13 | referer | |
+-------+----------------------------------+-----------------------+
| 14 | set-cookie | |
+-------+----------------------------------+-----------------------+
| 15 | :method | CONNECT |
+-------+----------------------------------+-----------------------+
| 16 | :method | DELETE |
+-------+----------------------------------+-----------------------+
| 17 | :method | GET |
+-------+----------------------------------+-----------------------+
| 18 | :method | HEAD |
+-------+----------------------------------+-----------------------+
| 19 | :method | OPTIONS |
+-------+----------------------------------+-----------------------+
| 20 | :method | POST |
+-------+----------------------------------+-----------------------+
| 21 | :method | PUT |
+-------+----------------------------------+-----------------------+
| 22 | :scheme | http |
+-------+----------------------------------+-----------------------+
| 23 | :scheme | https |
+-------+----------------------------------+-----------------------+
| 24 | :status | 103 |
+-------+----------------------------------+-----------------------+
| 25 | :status | 200 |
+-------+----------------------------------+-----------------------+
| 26 | :status | 304 |
+-------+----------------------------------+-----------------------+
| 27 | :status | 404 |
+-------+----------------------------------+-----------------------+
| 28 | :status | 503 |
+-------+----------------------------------+-----------------------+
| 29 | accept | */* |
+-------+----------------------------------+-----------------------+
| 30 | accept | application/dns- |
| | | message |
+-------+----------------------------------+-----------------------+
| 31 | accept-encoding | gzip, deflate, br |
+-------+----------------------------------+-----------------------+
| 32 | accept-ranges | bytes |
+-------+----------------------------------+-----------------------+
| 33 | access-control-allow-headers | cache-control |
+-------+----------------------------------+-----------------------+
| 34 | access-control-allow-headers | content-type |
+-------+----------------------------------+-----------------------+
| 35 | access-control-allow-origin | * |
+-------+----------------------------------+-----------------------+
| 36 | cache-control | max-age=0 |
+-------+----------------------------------+-----------------------+
| 37 | cache-control | max-age=2592000 |
+-------+----------------------------------+-----------------------+
| 38 | cache-control | max-age=604800 |
+-------+----------------------------------+-----------------------+
| 39 | cache-control | no-cache |
+-------+----------------------------------+-----------------------+
| 40 | cache-control | no-store |
+-------+----------------------------------+-----------------------+
| 41 | cache-control | public, max- |
| | | age=31536000 |
+-------+----------------------------------+-----------------------+
| 42 | content-encoding | br |
+-------+----------------------------------+-----------------------+
| 43 | content-encoding | gzip |
+-------+----------------------------------+-----------------------+
| 44 | content-type | application/dns- |
| | | message |
+-------+----------------------------------+-----------------------+
| 45 | content-type | application/ |
| | | javascript |
+-------+----------------------------------+-----------------------+
| 46 | content-type | application/json |
+-------+----------------------------------+-----------------------+
| 47 | content-type | application/x-www- |
| | | form-urlencoded |
+-------+----------------------------------+-----------------------+
| 48 | content-type | image/gif |
+-------+----------------------------------+-----------------------+
| 49 | content-type | image/jpeg |
+-------+----------------------------------+-----------------------+
| 50 | content-type | image/png |
+-------+----------------------------------+-----------------------+
| 51 | content-type | text/css |
+-------+----------------------------------+-----------------------+
| 52 | content-type | text/html; |
| | | charset=utf-8 |
+-------+----------------------------------+-----------------------+
| 53 | content-type | text/plain |
+-------+----------------------------------+-----------------------+
| 54 | content-type | text/ |
| | | plain;charset=utf-8 |
+-------+----------------------------------+-----------------------+
| 55 | range | bytes=0- |
+-------+----------------------------------+-----------------------+
| 56 | strict-transport-security | max-age=31536000 |
+-------+----------------------------------+-----------------------+
| 57 | strict-transport-security | max-age=31536000; |
| | | includesubdomains |
+-------+----------------------------------+-----------------------+
| 58 | strict-transport-security | max-age=31536000; |
| | | includesubdomains; |
| | | preload |
+-------+----------------------------------+-----------------------+
| 59 | vary | accept-encoding |
+-------+----------------------------------+-----------------------+
| 60 | vary | origin |
+-------+----------------------------------+-----------------------+
| 61 | x-content-type-options | nosniff |
+-------+----------------------------------+-----------------------+
| 62 | x-xss-protection | 1; mode=block |
+-------+----------------------------------+-----------------------+
| 63 | :status | 100 |
+-------+----------------------------------+-----------------------+
| 64 | :status | 204 |
+-------+----------------------------------+-----------------------+
| 65 | :status | 206 |
+-------+----------------------------------+-----------------------+
| 66 | :status | 302 |
+-------+----------------------------------+-----------------------+
| 67 | :status | 400 |
+-------+----------------------------------+-----------------------+
| 68 | :status | 403 |
+-------+----------------------------------+-----------------------+
| 69 | :status | 421 |
+-------+----------------------------------+-----------------------+
| 70 | :status | 425 |
+-------+----------------------------------+-----------------------+
| 71 | :status | 500 |
+-------+----------------------------------+-----------------------+
| 72 | accept-language | |
+-------+----------------------------------+-----------------------+
| 73 | access-control-allow-credentials | FALSE |
+-------+----------------------------------+-----------------------+
| 74 | access-control-allow-credentials | TRUE |
+-------+----------------------------------+-----------------------+
| 75 | access-control-allow-headers | * |
+-------+----------------------------------+-----------------------+
| 76 | access-control-allow-methods | get | +-------+----------------------------------+-----------------------+
| 77 | access-control-allow-methods | get, post, options |
+-------+----------------------------------+-----------------------+
| 78 | access-control-allow-methods | options |
+-------+----------------------------------+-----------------------+
| 79 | access-control-expose-headers | content-length |
+-------+----------------------------------+-----------------------+
| 80 | access-control-request-headers | content-type |
+-------+----------------------------------+-----------------------+
| 81 | access-control-request-method | get |
+-------+----------------------------------+-----------------------+
| 82 | access-control-request-method | post |
+-------+----------------------------------+-----------------------+
| 83 | alt-svc | clear |
+-------+----------------------------------+-----------------------+
| 84 | authorization | |
+-------+----------------------------------+-----------------------+
| 85 | content-security-policy | script-src 'none'; |
| | | object-src 'none'; |
| | | base-uri 'none' |
+-------+----------------------------------+-----------------------+
| 86 | early-data | 1 |
+-------+----------------------------------+-----------------------+
| 87 | expect-ct | |
+-------+----------------------------------+-----------------------+
| 88 | forwarded | |
+-------+----------------------------------+-----------------------+
| 89 | if-range | |
+-------+----------------------------------+-----------------------+
| 90 | origin | |
+-------+----------------------------------+-----------------------+
| 91 | purpose | prefetch |
+-------+----------------------------------+-----------------------+
| 92 | server | |
+-------+----------------------------------+-----------------------+
| 93 | timing-allow-origin | * |
+-------+----------------------------------+-----------------------+
| 94 | upgrade-insecure-requests | 1 |
+-------+----------------------------------+-----------------------+
| 95 | user-agent | |
+-------+----------------------------------+-----------------------+
| 96 | x-forwarded-for | |
+-------+----------------------------------+-----------------------+
| 97 | x-frame-options | deny |
+-------+----------------------------------+-----------------------+
| 98 | x-frame-options | sameorigin |
+-------+----------------------------------+-----------------------+
Table 4: Static TableOkay, that's the end of the static table! ๐ Any line breaks you see inside field names or values are only there because of formatting, so they aren't part of the actual names or values. Pinky promise ๐
Appendix B. Encoding and Decoding Examples โจ
okay so this appendix is my favourite bit ๐ฆ It's a little series of exchanges between an encoder and a decoder, bestie. The goal is to show off almost every QPACK instruction and the common patterns you'll run into, plus how each one changes the dynamic table. The encoder sends three encoded field sections with one field line each, and it also sends two speculative inserts that nobody references. Iconic behaviour ๐
Each table state shows the dynamic table's current size. Every entry has its Absolute Index (Abs), the number of outstanding encoded field sections that reference it (Ref), and its name and value. Anything above the "acknowledged" line has already been acknowledged by the decoder ๐ธ
B.1. Literal Field Line with Name Reference โจ
Here the encoder sends one encoded field section. The field is written as a literal, but its name gets borrowed from the static table ๐ง
Stream: 0
0000 | Required Insert Count = 0, Base = 0
510b 2f69 6e64 6578 | Literal Field Line with Name Reference
2e68 746d 6c | Static Table, Index=1
| (:path=/index.html)
Abs Ref Name Value
^-- acknowledged --^
Size=0B.2. Dynamic Table ๐
The encoder sets the dynamic table capacity and inserts a header with a dynamic name reference. Then it sends a potentially blocking, encoded field section that references this new entry. The decoder acknowledges processing that section, and that acknowledgment implicitly covers every dynamic table insertion up to the Required Insert Count. Main character energy, literally ๐
Stream: Encoder
3fbd01 | Set Dynamic Table Capacity=220
c00f 7777 772e 6578 | Insert With Name Reference
616d 706c 652e 636f | Static Table, Index=0
6d | (:authority=www.example.com)
c10c 2f73 616d 706c | Insert With Name Reference
652f 7061 7468 | Static Table, Index=1
| (:path=/sample/path)
Abs Ref Name Value
^-- acknowledged --^
0 0 :authority www.example.com
1 0 :path /sample/path
Size=106
Stream: 4
0381 | Required Insert Count = 2, Base = 0
10 | Indexed Field Line With Post-Base Index
| Absolute Index = Base(0) + Index(0) = 0
| (:authority=www.example.com)
11 | Indexed Field Line With Post-Base Index
| Absolute Index = Base(0) + Index(1) = 1
| (:path=/sample/path)
Abs Ref Name Value
^-- acknowledged --^
0 1 :authority www.example.com
1 1 :path /sample/path
Size=106
Stream: Decoder
84 | Section Acknowledgment (stream=4)
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
^-- acknowledged --^
Size=106B.3. Speculative Insert ๐ฆ
The encoder slides a header into the dynamic table using a literal name. The decoder acknowledges that it got the entry. The encoder doesn't send any encoded field sections in this one, so it's just vibes ๐
Stream: Encoder
4a63 7573 746f 6d2d | Insert With Literal Name
6b65 790c 6375 7374 | (custom-key=custom-value)
6f6d 2d76 616c 7565 |
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
^-- acknowledged --^
2 0 custom-key custom-value
Size=160
Stream: Decoder
01 | Insert Count Increment (1)
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
2 0 custom-key custom-value
^-- acknowledged --^
Size=160B.4. Duplicate Instruction, Stream Cancellation ๐
Okay, plot twist ๐ The encoder duplicates an entry that's already in the dynamic table, then sends an encoded field section that references the table entries, including the duplicate. The packet carrying the encoder stream data gets delayed. Before it shows up, the decoder cancels the stream and tells the encoder that the encoded field section was never processed. Ate the drama, no crumbs ๐
Stream: Encoder
02 | Duplicate (Relative Index = 2)
| Absolute Index =
| Insert Count(3) - Index(2) - 1 = 0
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
2 0 custom-key custom-value
^-- acknowledged --^
3 0 :authority www.example.com
Size=217
Stream: 8
0500 | Required Insert Count = 4, Base = 4
80 | Indexed Field Line, Dynamic Table
| Absolute Index = Base(4) - Index(0) - 1 = 3
| (:authority=www.example.com)
c1 | Indexed Field Line, Static Table Index = 1
| (:path=/)
81 | Indexed Field Line, Dynamic Table
| Absolute Index = Base(4) - Index(1) - 1 = 2
| (custom-key=custom-value)
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
2 1 custom-key custom-value
^-- acknowledged --^
3 1 :authority www.example.com
Size=217
Stream: Decoder
48 | Stream Cancellation (Stream=8)
Abs Ref Name Value
0 0 :authority www.example.com
1 0 :path /sample/path
2 0 custom-key custom-value
^-- acknowledged --^
3 0 :authority www.example.com
Size=217B.5. Dynamic Table Insert, Eviction ๐ธ
The encoder adds another header to the dynamic table, and that pushes out the oldest entry to make room. This time the encoder doesn't send any encoded field sections, so it's a quiet little moment ๐ซถ
Stream: Encoder
810d 6375 7374 6f6d | Insert With Name Reference
2d76 616c 7565 32 | Dynamic Table, Relative Index = 1
| Absolute Index =
| Insert Count(4) - Index(1) - 1 = 2
| (custom-key=custom-value2)
Abs Ref Name Value
1 0 :path /sample/path
2 0 custom-key custom-value
^-- acknowledged --^
3 0 :authority www.example.com
4 0 custom-key custom-value2
Size=215Appendix C. Sample Single-Pass Encoding Algorithm โจ
okay so this appendix is a little pseudocode treat ๐ง it shows how a single-pass encoder could work, and it's giving very "one pass and done" energy. it leaves out a few things on purpose: duplicates, non-blocking mode, encoder stream flow control, and reference tracking. those are handled elsewhere in the spec, so this is just the core vibe ๐
# Helper functions:
# ====
# Encode an integer with the specified prefix and length
encodeInteger(buffer, prefix, value, prefixLength)
# Encode a dynamic table insert instruction with optional static
# or dynamic name index (but not both)
encodeInsert(buffer, staticNameIndex, dynamicNameIndex, fieldLine)
# Encode a static index reference
encodeStaticIndexReference(buffer, staticIndex)
# Encode a dynamic index reference relative to Base
encodeDynamicIndexReference(buffer, dynamicIndex, base)
# Encode a literal with an optional static name index
encodeLiteral(buffer, staticNameIndex, fieldLine)
# Encode a literal with a dynamic name index relative to Base
encodeDynamicLiteral(buffer, dynamicNameIndex, base, fieldLine)
# Encoding Algorithm
# ====
base = dynamicTable.getInsertCount()
requiredInsertCount = 0
for line in fieldLines:
staticIndex = staticTable.findIndex(line)
if staticIndex is not None:
encodeStaticIndexReference(streamBuffer, staticIndex)
continue
dynamicIndex = dynamicTable.findIndex(line)
if dynamicIndex is None:
# No matching entry. Either insert+index or encode literal
staticNameIndex = staticTable.findName(line.name)
if staticNameIndex is None:
dynamicNameIndex = dynamicTable.findName(line.name)
if shouldIndex(line) and dynamicTable.canIndex(line):
encodeInsert(encoderBuffer, staticNameIndex,
dynamicNameIndex, line)
dynamicIndex = dynamicTable.add(line)
if dynamicIndex is None:
# Could not index it, literal
if dynamicNameIndex is not None:
# Encode literal with dynamic name, possibly above Base
encodeDynamicLiteral(streamBuffer, dynamicNameIndex,
base, line)
requiredInsertCount = max(requiredInsertCount,
dynamicNameIndex)
else:
# Encodes a literal with a static name or literal name
encodeLiteral(streamBuffer, staticNameIndex, line)
else:
# Dynamic index reference
assert(dynamicIndex is not None)
requiredInsertCount = max(requiredInsertCount, dynamicIndex)
# Encode dynamicIndex, possibly above Base
encodeDynamicIndexReference(streamBuffer, dynamicIndex, base)
# encode the prefix
if requiredInsertCount == 0:
encodeInteger(prefixBuffer, 0x00, 0, 8)
encodeInteger(prefixBuffer, 0x00, 0, 7)
else:
wireRIC = (
requiredInsertCount
% (2 * getMaxEntries(maxTableCapacity))
) + 1;
encodeInteger(prefixBuffer, 0x00, wireRIC, 8)
if base >= requiredInsertCount:
encodeInteger(prefixBuffer, 0x00,
base - requiredInsertCount, 7)
else:
encodeInteger(prefixBuffer, 0x80,
requiredInsertCount - base - 1, 7)
return encoderBuffer, prefixBuffer + streamBufferThe big picture: the encoder looks up each field line in the static table first, then the dynamic table. If there's no match and it's allowed to index the line, it inserts it and then references it. Otherwise it falls back to a literal, using a dynamic or static name when one exists. At the end it builds the prefix, which carries the Required Insert Count and Base. That's the whole glow-up in one loop ๐ธ
Acknowledgments
the IETF QUIC Working Group got SO much support from so many people ๐ซถ like, an enormous amount
the compression design team did serious work mapping out the problem space and shaping the early draft of this document ๐ง huge thanks to design team members Roberto Peon, Martin Thomson, and Dmitri Tikhonov, who are gratefully acknowledged ๐
the following people also made substantial contributions to this document ๐
- Bence Beky
- Alessandro Ghedini
- Ryan Hamilton
- Robin Marx
- Patrick McManus
- ๅฅฅ ไธ็ฉ (Kazuho Oku)
- Lucas Pardue
- Biren Roy
- Ian Swett
this document leans heavily on the text of [RFC7541] ๐ฆ the indirect input of those authors is also gratefully acknowledged, bestie
Buck Krasic's contribution was supported by Google during his employment there ๐
a portion of Mike Bishop's contribution was supported by Microsoft during his employment there ๐
Authors' Addresses
Charles 'Buck' Krasic
Email: krasic@acm.org
Mike Bishop
Akamai Technologies
Email: mbishop@evequefou.be
Alan Frindell (editor)
Email: afrind@fb.com
and that's the whole spec, bestie! ๐ the people who built this are literally iconic, and thank you for reading all the way to the end ๐
๐ฆ where this page comes from
- ietf: rfc9204 2022-06
- ๐ girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms