Subject: Fwd: New Version Notification for draft-vkrasnov-h2-compression-dictionaries-01.txt

From: Vlad Krasnov <[email-masked]>
Date: Tue, 1 Nov 2016 13:34:30 -0700

Hi,

Yesterday I posted a new version of my proposal that allows for cross-stream compression in HTTP/2.

This allows for significant improvement in compression ratio for a variety of use cases, including server->client and origin->server, and works with both deflate and brotli.

The main changes from the previous version include the option to concatenate dictionaries, and the use of static dictionaries, that improve compression ratio even for connections that serve only a single resource.

Feedback is appreciated.

Cheers,
Vlad

> Begin forwarded message:
> 
> From: [email-masked]
> Subject: New Version Notification for draft-vkrasnov-h2-compression-dictionaries-01.txt
> Date: 31 October 2016 at 10:42:44 GMT-7
> To: "Vlad Krasnov" <[email-masked]>
> 
> 
> A new version of I-D, draft-vkrasnov-h2-compression-dictionaries-01.txt
> has been successfully submitted by Vlad Krasnov and posted to the
> IETF repository.
> 
> Name:		draft-vkrasnov-h2-compression-dictionaries
> Revision:	01
> Title:		Compression Dictionaries for HTTP/2
> Document date:	2016-10-31
> Group:		Individual Submission
> Pages:		7
> URL:            https://www.ietf.org/internet-drafts/draft-vkrasnov-h2-compression-dictionaries-01.txt
> Status:         https://datatracker.ietf.org/doc/draft-vkrasnov-h2-compression-dictionaries/
> Htmlized:       https://tools.ietf.org/html/draft-vkrasnov-h2-compression-dictionaries-01
> Diff:           https://www.ietf.org/rfcdiff?url2=draft-vkrasnov-h2-compression-dictionaries-01
> 
> Abstract:
>   This document specifies a new HTTP/2 frame type and new HTTP/2
>   settings values that would enable the use of previously transferred
>   data as compression dictionaries, significantly improving overall
>   compression ratio for a given connection.
> 
>   In addition, this document proposes to define a set of industry
>   standard, static, dictionaries to be used with any Lempel-Ziv based
>   compression for the common textual MIME types prevalent on the web.
> 
> 
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> The IETF Secretariat
>

---

From: Martin Thomson <[email-masked]>
Date: Wed, 2 Nov 2016 14:14:17 +1100

I look forward to discussing this, particularly in comparison to SDCH.

A few comments from a brief skim:

MAJOR:

The document is really light on details regarding how to use a
dictionary.  I realize that this might /seem/ obvious, but it really
needs to explain how better (up front preferably) how it is intended
to work.  In particular, how do I tell what compression algorithm to
feed the dictionary into?  HTTP/2 doesn't know about compression, in
particular, HTTP/2 really *can't* use content-encoding.

minor stuff:

I see that you have settings for the number of dictionaries, and the
size of those dictionaries, this is good, but I think that you need to
set an overall limit instead of a per-dictionary limit
SETTINGS_MAX_DICTIONARY_SIZE (you get better efficiency that way).

I like the idea of static dictionaries, but your structure would force
an implementation to support ALL static dictionaries if they wanted to
support ANY dynamic dictionaries.  That might be inadvisable.  A
separate setting would be better I think.  (Static dictionaries could
start from the top of the numbering space, perhaps, so that you can
have many static dictionaries.)

The security considerations need a lot more detail about when it is
safe to use a compression dictionary, etc.

On 2 November 2016 at 07:34, Vlad Krasnov <[email-masked]> wrote:
> This allows for significant improvement in compression ratio for a variety
> of use cases, including server->client and origin->server, and works with
> both deflate and brotli.
>
> The main changes from the previous version include the option to concatenate
> dictionaries, and the use of static dictionaries, that improve compression
> ratio even for connections that serve only a single resource.
>
> Feedback is appreciated.
>
> Cheers,
> Vlad
>
> Begin forwarded message:
>
> Subject: New Version Notification for
> draft-vkrasnov-h2-compression-dictionaries-01.txt
> URL:
> https://www.ietf.org/internet-drafts/draft-vkrasnov-h2-compression-dictionaries-01.txt
> Status:
> https://datatracker.ietf.org/doc/draft-vkrasnov-h2-compression-dictionaries/
> Htmlized:
> https://tools.ietf.org/html/draft-vkrasnov-h2-compression-dictionaries-01
> Diff:
> https://www.ietf.org/rfcdiff?url2=draft-vkrasnov-h2-compression-dictionaries-01
>
> Abstract:

---

From: Vlad Krasnov <[email-masked]>
Date: Wed, 2 Nov 2016 11:10:15 -0700

> particular, HTTP/2 really *can't* use content-encoding.

Actually I was in the mind of reusing accept-encoding/content-encoding for this.

> SETTINGS_MAX_DICTIONARY_SIZE (you get better efficiency that way).

That sounds like a good idea. 
The benefit of having a per-dictionary limit, is that when you append a stream to an existing dictionary it is implied you only keep the maximal allowed amount of bytes.
After all there is no point of having a dictionary larger than your window.
With a global limit you might want to specify how many bytes to keep explicitly, that creates additional overhead.
Maybe combine both?

> have many static dictionaries.)

There a few options I considered for static dictionaries, and all of them are acceptable for me.
Currently I went for the cheapest option in terms of implementation simplicity/overhead.

> safe to use a compression dictionary, etc.

It should be OK compress same origin, self referenced requests, this however degrades performance on sharded websites.
Also the use of static dictionaries is quite safe.

---

From: Julian Reschke <[email-masked]>
Date: Wed, 2 Nov 2016 19:26:05 +0100

On 2016-11-02 04:14, Martin Thomson wrote:
> ...
> ...

What?

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 2 Nov 2016 20:42:03 +0200

> >particular, HTTP/2 really *can't* use content-encoding.

I presume somebody confused Content-Encoding and Transport-Encoding.

Content-Encoding is not merely changing the content for transport
(Transport-Encoding would) because things like ETag's are changed too.

HTTP/2 definitely does have C-E, but I don't think it has non-
trivial T-E.

-Ilari

---

From: Jyrki Alakuijala <[email-masked]>
Date: Wed, 2 Nov 2016 20:59:03 +0100

Brotli has two separate ways of using a static dictionary. The first way is
the traditional way that zlib supports. The current custom dictionary
interface in brotli supports this method.

The second way is denser. It allows for every pair of (length, distance) to
point to a unique dictionary sequence. Because of this, dictionary
sequences that point to length N strings would save log2(N) bits in
distance specification in comparison to traditional dictionaries.

Further, second way of coding dictionaries allows for simple
transformations of the dictionary, i.e., primitive grammar to be defined.

We didn't add a user-programmable interface to define these yet in
libbrotli, but the second way for static dictionaries is already used for
the internal static dictionary. Our experience with it is that it is
significantly more powerful in comparison than a simple sequence of bytes.

Ideally, when used with brotli, a dictionary sharing mechanism would allow
for both of these to be used, and to allow for primitive grammar support,
too. The primitive grammar support allows for a small dictionary of
prefixes and suffixes, for example the current prefix-suffix-dictionary is
208 bytes -- the \0s here are separators:

kPrefixSuffix :=
    "\0 \0, \0 of the \0 of \0s \0.\0 and \0 in \0\"\0 to \0\">\0\n\0.
\0]\0"
    " for \0 a \0 that \0\'\0 with \0 from \0 by \0(\0. The \0 on \0 as \0"
    " is \0ing \0\n\t\0:\0ed \0=\"\0 at \0ly \0,\0=\'\0.com/\0. This \0"
    " not \0er \0al \0ful \0ive \0less \0est \0ize \0\xc2\xa0\0ous "

In addition to this, there is a combination table that combines a prefix +
middle-out-transform + suffix (choosing from 21 pre-programmed 'middle-out'
transforms that operate on the dictionary entries).

These "grammar tables" are less than 1 kB in size, but give about 1.5 % in
compression density, much higher win than elsewhere in the static
dictionary. It is possible that such grammar tables give more gain for
languages that are heavy on their prefix use (articles, prepositions, etc.).

The second way allows for about 3 % increase in compression density in
comparison to the first way, or alternatively one can reach to same
compression density by using smaller dictionaries (possibly about half the
size).

---

From: Vlad Krasnov <[email-masked]>
Date: Wed, 2 Nov 2016 14:19:39 -0700

> Brotli has two separate ways of using a static dictionary. The first way is the traditional way that zlib supports. The current custom dictionary interface in brotli supports this method.

I tested Brotli with the traditional approach for both static and dynamic dictionaries, and the gains are much higher than those of deflate, I guess thanks in part to the much larger window.

For my current study on static dictionaries I generated dictionaries using a tool I wrote https://github.com/vkrasnov/dictator <https://github.com/vkrasnov/dictator> from the Alexa top 500, based on content-encoding. It is optimized for deflate, and there are things to improve there yet.

A bug plus it that the same dictionary is beneficial for both deflate and Brotli, or even LZMA as a matter of fact.

> The second way is denser. It allows for every pair of (length, distance) to point to a unique dictionary sequence. Because of this, dictionary sequences that point to length N strings would save log2(N) bits in distance specification in comparison to traditional dictionaries.

The second way is more expensive in terms of performance, but I suppose if you can generate static dictionaries only once, you only need to consider the cost of dictionary lookup.

The larger problem is that then we will have to support different dictionaries for different algorithms. We can do it, if like Martin suggested we have a versioning system for the dictionaries.

Another question then: do we support simultaneous use of dynamic and static dictionaries, which would only work with Brotli?

> The second way allows for about 3 % increase in compression density in comparison to the first way, or alternatively one can reach to same compression density by using smaller dictionaries (possibly about half the size).

My main goal here is to allow for efficient recompression on the fly even for static, or previously compressed, content. Using dynamic dictionaries, lets you compress/re-compress very well with lower compression setting, really fast.

For example if you already have a stream compressed with gzip, is it worth it for you to recompress it to brotli? When you use dynamic dictionaries (with the simple static dictionaries) the answer is definitely yes.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 3 Nov 2016 11:06:50 +1100

>> particular, HTTP/2 really *can't* use content-encoding.

HTTP/2 - at the layer Vlad is talking about - only knows about the
bytes that comprise a request or response.  What Vlad proposes
requires that the HTTP/2 layer look at the Content-Encoding header
field, determine that it *ends* with a compatible value and only then
do things to feed data to the compressor.  That's a massive
architectural upheaval.

---

From: Vlad Krasnov <[email-masked]>
Date: Wed, 2 Nov 2016 18:23:36 -0700

> On Nov 2, 2016, at 5:06 PM, Martin Thomson <[email-masked]> wrote:
> 
>> 
>> What?
> 

I know that it is not entirely "canonical" however even if implemented entirely at the protocol level, http/2 still has to know that no other content-encoding was used at the application layer.

At least from nginx viewpoint this is very simple, but I did not really consider how difficult it might be to implement in FF.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 3 Nov 2016 10:54:29 +0900

> I know that it is not entirely "canonical" however even if implemented entirely at the protocol level, http/2 still has to know that no other content-encoding was used at the application layer.

I agree with Martin that using an HTTP header for the purpose is not a
good idea.

One practical issue I am afraid of using Content-Encoding for such
purpose is that the checksum of the transferred file becomes different
from the original, since there is no deterministic way to reconstruct
the compressed form of a gzip. The draft alters some part of the
response (e.g. first 32KB after decompressed), and it is impossible
for a client to reconstruct how it looked like on the origin server
(under the compressed form).

I think this would cause interoperability issues due to the fact that
sometimes the checksum (or a signature) of a transmitted archive is
transferred separately.

Using transfer-encoding header would not cause this issue, but I think
things would become simpler if the identifier of the compression
method being applied was transmitted as an HTTP/2 frame rather than a
HTTP header.

Personally, I wonder if the approach could be adjusted to using a
shared compression context between the DATA frames of multiple
streams. Doing that way, the draft would become more attractive to
other use-cases (e.g. JSON API in microservices) where many tiny
responses are sent very frequently. Even if we changed the draft as
such, a server could still use the trailing part of a pre-compressed
file, by locking down the response being transmitted to that
particular one.

Anyways, I am looking forward to discussing the I-D at IETF, since I
think there'd be value in solving the issue (that the I-D tries to
solve).

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Thu, 3 Nov 2016 13:53:56 +1100

> file, by locking down the response being transmitted to that

I think that this is a better approach.  Treat this like a transfer
coding.  That gives you a lot more flexibility and it doesn't mess
with the representation in ways that might be surprising.

If you want to interact with content codings, make it a content
coding.  At that point, it would be better to make this HTTP version
agnostic, in the same way that SDCH is.  But then you are just
defining a variation on SDCH.

---

From: Matthew Kerwin <[email-masked]>
Date: Thu, 3 Nov 2016 12:55:37 +1000

Just chiming in without necessarily attaching to a particular thread of
discussion: I'm quite probably being thick here, but isn't there a problem
(of the abstraction/encapsulation flavour) with making a content-encoding
dependent on values sent at the transport layer? I think I'm just
reiterating what Martin was saying, but in a more vague and incoherent way.

If we're discussing compression parameters/algorithms/dictionaries/etc. at
the transport layer, shouldn't the entirety of the compression happen at
the transport layer? Thus making it like HTTP/2's new version of TE.

And if so, isn't transport layer compression a Bad Thing™? Because – thanks
to the wonder of abstraction – the transport machinery doesn't
(necessarily) know the provenance of the bytes it's compressing (thus
potentially allowing sensitive and attacker-controlled data to be
compressed in the same context – i.e. BREACH.)

So we bounce it up the stack to the application, which has a much better
chance of knowing who authored what bytes. And thus we end up back at
content-encoding.

If it's tied to content-encoding, it should be **entirely** contained in
the semantic layer – headers and payload entities. Isn't that what SDCH is?

If it's pushed down to the transport layer, isn't it just an even less safe
version of draft-kerwin-http2-encoded-data? (I said no shared compression
context between different frames, this is about sharing contexts between
completely different *streams*!)

I'm not entirely sure what new thing this particular proposal brings to the
table.

Cheers
-- 
  Matthew Kerwin
  http://matthew.kerwin.net.au/

---

From: Martin Thomson <[email-masked]>
Date: Thu, 3 Nov 2016 14:08:07 +1100

On 3 November 2016 at 13:55, Matthew Kerwin <[email-masked]> wrote:
> completely different streams!)

That is certainly a valid way of looking at this.

It's possibly true that you can avoid the nasty pitfalls here by only
using this for streams that are safe.  For instance, you might use
this over static resources.  BUT... just by altering the order of
requests, the size of resources can change, particularly if you know
where the compression window cuts off.  That makes me very wary about
making assertions about what is and isn't safe.

Example:  You only use this technique over a set of static images
(which should already be compressed, but we're looking for entire
images).  The attacker is able to cause a browser to make requests.
The attacker can therefore cause the window to be filled with images
that it knows about.  It can then use the size of the page load to
learn things about the images that were in that page load.  An
attacker maybe can't force a full network fetch, so it might have to
deal with caching but it can maybe find images that share pieces with
images of interest.  With a finite set of target images, you can get a
lot of information, especially if you are able to repeat the trial.

---

From: Vlad Krasnov <[email-masked]>
Date: Wed, 2 Nov 2016 22:43:57 -0700

> On 2 Nov 2016, at 19:55, Matthew Kerwin <[email-masked]> wrote:
> 
> Just chiming in without necessarily attaching to a particular thread of discussion: I'm quite probably being thick here, but isn't there a problem (of the abstraction/encapsulation flavour) with making a content-encoding dependent on values sent at the transport layer? I think I'm just reiterating what Martin was saying, but in a more vague and incoherent way.
> 
> If we're discussing compression parameters/algorithms/dictionaries/etc. at the transport layer, shouldn't the entirety of the compression happen at the transport layer? Thus making it like HTTP/2's new version of TE.
> 
> And if so, isn't transport layer compression a Bad Thing™? Because – thanks to the wonder of abstraction – the transport machinery doesn't (necessarily) know the provenance of the bytes it's compressing (thus potentially allowing sensitive and attacker-controlled data to be compressed in the same context – i.e. BREACH.)

Indeed, making a dumb compression at the transport layer is not my aim here.
A) It is indeed less safe
B) The compression benefits are much smaller when the protocol is unaware of the data type transported

Again, I am looking from the PoV of the nginx architecture that we use, and there is no clear distinction there between the layers, and introspection into the application level is easy to do. And from what I have seen in Apache, it is not that difficult either.

Certainly Server Push is a form of application/protocol level fusion.

Another approach can be client hints. Since we already have client hints in the form of priorities, we can not deny that http/2 is somewhat connected to the application level too.

> So we bounce it up the stack to the application, which has a much better chance of knowing who authored what bytes. And thus we end up back at content-encoding.

Doing it in the application level is also not as good. Because streams can get canceled, and reprioritized you are at a danger of fatal failures (such as deadlocks) if you try to control and optimize the process in the application.

> 
> If it's tied to content-encoding, it should be *entirely* contained in the semantic layer – headers and payload entities. Isn't that what SDCH is?

This is indeed not unlike SDCH and “quasi dictionaries” only your dictionary defined by a stream and not a different url. In fact it can be used with SDCH just as well.
My proposal tries to be as algorithm agnostic as possible.
However brolti compresses much better in that case. In fact from what I have seen brotli+”quasi” beats sdch+”quasi”+brotli (but maybe sdch+”quasi”+brotli+”quasi” will do even better?).

The point is you just can’t get that level of control purely at the application level or the protocol level. We should try and find a middle ground.

> 
> If it's pushed down to the transport layer, isn't it just an even less safe version of draft-kerwin-http2-encoded-data? (I said no shared compression context between different frames, this is about sharing contexts between completely different streams!)

Again, blindly compressing everything at the transport layer is not my suggestion. However even that is OK for the majority of the websites. I for one am not aware of a major effort to mitigate BREACH. 
However the methods to mitigate BREACH are valid for this proposal as well. In fact the greatest danger here is to make BREACH even faster, but isn’t the point moot when you can execute it in 30 seconds already?

> 
> I'm not entirely sure what new thing this particular proposal brings to the table.

Improved compression? 

Cheers,
Vlad

---

From: Jyrki Alakuijala <[email-masked]>
Date: Thu, 3 Nov 2016 11:32:14 +0100

On Thu, Nov 3, 2016 at 6:43 AM, Vlad Krasnov <[email-masked]> wrote:

> This is indeed not unlike SDCH and “quasi dictionaries” only your
> dictionary defined by a stream and not a different url. In fact it can be
> used with SDCH just as well.
> However brolti compresses much better in that case. In fact from what I
> have seen brotli+”quasi” beats sdch+”quasi”+brotli (but maybe
> sdch+”quasi”+brotli+”quasi” will do even better?).
>

Yes, this is consistent with our experiments. Brotli + custom dictionary is
more efficient than SDCH + custom dictionary with further gzip or brotli
compression.

With small (~150 kB) dictionaries brotli wins SDCH by 10-20 % (20 % at
brotli quality 11, 10 % at quality 6), with larger (1 MB) dictionaries
more, 20-30 % (30 % at brotli quality 11, 20 % at quality 6). The larger
the custom dictionary, the more powerful brotli comes in comparison to
SDCH. All our experiments indicate that SDCH is fully redundant and can be
abandoned if we add custom dictionary support to brotli content encoding.

---

From: Patrick McManus <[email-masked]>
Date: Thu, 3 Nov 2016 10:45:42 -0400

On Thu, Nov 3, 2016 at 6:32 AM, Jyrki Alakuijala <[email-masked]> wrote:

> Yes, this is consistent with our experiments. Brotli + custom dictionary
> is more efficient than SDCH + custom dictionary with further gzip or brotli
> compression.
>

this is a good discussion.

We should also be congnizant of the recent movement towards
"content-encodings should be self describing" that came out of the
encrypted object draft discussion - which sdch doesn't quite match (yet?).
Perhaps a brotli with a uri for its custom dictionary combined with push of
the dict gets us there (handwave).

---

From: Martin Thomson <[email-masked]>
Date: Fri, 4 Nov 2016 11:07:44 +1100

On 4 November 2016 at 01:45, Patrick McManus <[email-masked]> wrote:
> "content-encodings should be self describing" that came out of the encrypted
> object draft discussion - which sdch doesn't quite match (yet?). Perhaps a
> brotli with a uri for its custom dictionary combined with push of the dict
> gets us there (handwave).

I think that the main innovation in Vlad's proposal is that he doesn't
necessarily rely on a separate dictionary resource, he uses real
resources to prime the dictionary.  That means that you never spend
bytes on stuff that isn't immediately useful to you.  I'd be very
interested in seeing what effect that has on things like
responsiveness.

I agree with you that the content encoding being self-descriptive is
valuable, but I'm not quite seeing how we can get both of these things
just yet.  Maybe URLs are the wrong answer and we simply need to
identify a shared context somehow.

If you take Jyrki's observation that you might want multiple
dictionaries, you can have a header that includes a list of
dictionaries you want to use, plus optionally the dictionary that you
want to append to with this response.

Spitballing here... would identifying the context with a hash of its
state work?  Using hashes means that you don't ever have a problem
with state synchronization.  Synchronization is very much a problem if
you move to something like QUIC where inter-stream ordering is loose,
and it acts as a sanity check that you aren't corrupting data.