Subject: [Gen-art] Gen-ART Last Call review of draft-alakuijala-brotli-08

From: Paul Kyzivat <[email-masked]>
Date: Fri, 1 Apr 2016 15:02:43 -0400

I am the assigned Gen-ART reviewer for this draft. The General Area 
Review Team (Gen-ART) reviews all IETF documents being processed by the 
IESG for the IETF Chair. Please treat these comments just like any other 
last call comments. For more information, please see the FAQ at 
<http://wiki.tools.ietf.org/area/gen/trac/wiki/GenArtfaq>.

Document: draft-alakuijala-brotli-08
Reviewer: Paul Kyzivat
Review Date: 2016-02-23
IETF LC End Date: 2016-04-08
IESG Telechat date: 2016-04-21

Summary:

This draft has serious issues, described in the review, and needs to be 
rethought.

Major: 1
Minor: 0
Nits:  0

==========

(1) Major:

In my opinion this document does not satisfy the purpose given in 
section 1.1 for the type of reader identified in section 1.2.

I spent many hours trying to decipher the document, but ultimately 
failed. (I have no experience in implementing compression/decompression 
algorithms, but I have many decades of programming experience including 
that involving detailed bit manipulation and data representation.)

If two expert programmers were asked to independently build 
encoder/decoders in accord with this document, IMO it would be 
incredibly unlikely (impossible) that the resulting programs would be 
interoperable. And given the complexity of the encoding it would also be 
extremely difficult to figure out *why* they didn't interoperate.

My sense from reading this document is that the format is operationally 
defined by an existing program (https://github.com/google/brotli) and 
that this document is an attempt to re-render the source code in 
English. However the algorithms being described are so complex that 
English (at least *this* English) is inadequate for the job.

I started out making notes about particular places where I found the 
language confusing or ambiguous. But there were so many that I 
ultimately gave up.

I have serious doubts that the goal of this document achievable using 
natural language text. I don't have much of an idea of what to try to 
achieve this. It will take much more than just patching the current 
document. If possible at all it will require a vastly different approach.

To achieve the goal of having a specification independent of a 
particular implementation it may be necessary to abandon backward 
compatibility with *this* implementation. (I recognize that doing so may 
be unacceptable.)

---

From: Zoltan Szabadka <[email-masked]>
Date: Tue, 12 Apr 2016 15:17:51 +0200

Thank you for reviewing this internet draft.

We do share your concern that it is very difficult to fully specify a
compressed data format of this complexity using natural language text alone.

To address this concern, the language and style of this internet draft
follows that of RFC 1951, which specifies a compression format closely
related to this one, to the extent that some common parts were taken over
verbatim. Moreover, we worked with three independent software implementers,
who agreed to use only the text of this draft to implement a brotli decoder
and provide feedback on where the text was ambiguous or unclear.

These independent implementations are the following:

    1) C language implementation of Mark Adler:
https://github.com/madler/brotli
    2) Rust language implementation of Thomas Pickert:
https://github.com/ende76/brotli-rs
    3) Go language implementation of Joe Tsai:
https://github.com/dsnet/compress/tree/brotli

The current -08 version of this internet draft addresses the findings of
these reviews, and we believe that it is possible to decide based on this
draft whether or not an arbitrary sequence of bytes is a valid brotli
stream; and what is the uncompressed sequence of bytes that a valid brotli
stream represents.

As the next step, we plan to update the draft with a section about
considerations for compressor implementations. In this, we will address:
    1) Jean-Loup Gailly’s review comment about how it is possible, if
desired, to make a sequence of blocks self-contained in a way that they can
be decompressed independently of previous blocks.
    2) The secdir review comments about CRIME and DoS attacks.

We expect to be ready with the next version of the draft in one week.

Kind Regards,
Zoltan

On Fri, Apr 1, 2016 at 9:02 PM, Paul Kyzivat <[email-masked]> wrote:

> I am the assigned Gen-ART reviewer for this draft. The General Area Review
> Team (Gen-ART) reviews all IETF documents being processed by the IESG for
> the IETF Chair. Please treat these comments just like any other last call
> comments. For more information, please see the FAQ at <
> http://wiki.tools.ietf.org/area/gen/trac/wiki/GenArtfaq>.
>
> In my opinion this document does not satisfy the purpose given in section
> 1.1 for the type of reader identified in section 1.2.
>
> I spent many hours trying to decipher the document, but ultimately failed.
> (I have no experience in implementing compression/decompression algorithms,
> but I have many decades of programming experience including that involving
> detailed bit manipulation and data representation.)
>
> encoder/decoders in accord with this document, IMO it would be incredibly
> unlikely (impossible) that the resulting programs would be interoperable.
> And given the complexity of the encoding it would also be extremely
> difficult to figure out *why* they didn't interoperate.
>
> that this document is an attempt to re-render the source code in English.
> However the algorithms being described are so complex that English (at
> least *this* English) is inadequate for the job.
>
> language confusing or ambiguous. But there were so many that I ultimately
> gave up.
>
> To achieve the goal of having a specification independent of a particular
> implementation it may be necessary to abandon backward compatibility with
> *this* implementation. (I recognize that doing so may be unacceptable.)
>
>

---

From: Paul Kyzivat <[email-masked]>
Date: Wed, 13 Apr 2016 16:17:14 -0400

Zoltan,

On 4/12/16 9:17 AM, Zoltan Szabadka wrote:
> related to this one, to the extent that some common parts were taken
> over verbatim. Moreover, we worked with three independent software
> implementers, who agreed to use only the text of this draft to implement
> a brotli decoder and provide feedback on where the text was ambiguous or
> unclear.
>

I will grant that these serve as existence proofs that the spec "works", 
given sufficient effort.

I'm still concerned, but you can just consider me to be one data point 
out of four.

> these reviews, and we believe that it is possible to decide based on
> this draft whether or not an arbitrary sequence of bytes is a valid
> brotli stream; and what is the uncompressed sequence of bytes that a
> valid brotli stream represents.
>
> desired, to make a sequence of blocks self-contained in a way that they
> can be decompressed independently of previous blocks.

One thing I realized later is that your draft is *informative*, not 
normative. Is that the intent? If so, what *is* normative?

If the *code* is normative, then there is no need to make the text 
unambiguous without the code. It might be better to simply rewrite the 
text as an explanation of the code.

OTOH, if this is intended to be normative, then it needs to be written 
with that in mind, using RFC2119 language, and with "Intended Status: 
Standards Track".

	Thanks,
	Paul

> Kind Regards,
> Zoltan
>
> On Fri, Apr 1, 2016 at 9:02 PM, Paul Kyzivat <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     Review Team (Gen-ART) reviews all IETF documents being processed by
>     the IESG for the IETF Chair. Please treat these comments just like
>     any other last call comments. For more information, please see the
>     FAQ at <http://wiki.tools.ietf.org/area/gen/trac/wiki/GenArtfaq>.
>
>     This draft has serious issues, described in the review, and needs to
>     be rethought.
>
>     Major: 1
>     Minor: 0
>     Nits:  0
>
>     ==========
>
>     (1) Major:
>
>     failed. (I have no experience in implementing
>     compression/decompression algorithms, but I have many decades of
>     programming experience including that involving detailed bit
>     manipulation and data representation.)
>
>     incredibly unlikely (impossible) that the resulting programs would
>     be interoperable. And given the complexity of the encoding it would
>     also be extremely difficult to figure out *why* they didn't
>     interoperate.
>
>     My sense from reading this document is that the format is
>     operationally defined by an existing program
>     (https://github.com/google/brotli) and that this document is an
>     attempt to re-render the source code in English. However the
>     algorithms being described are so complex that English (at least
>     *this* English) is inadequate for the job.
>
>     I have serious doubts that the goal of this document achievable
>     using natural language text. I don't have much of an idea of what to
>     try to achieve this. It will take much more than just patching the
>     current document. If possible at all it will require a vastly
>     different approach.
>
>     compatibility with *this* implementation. (I recognize that doing so
>     may be unacceptable.)
>
>

---

From: Paul Kyzivat <[email-masked]>
Date: Tue, 19 Apr 2016 11:05:38 -0400

I am the assigned Gen-ART reviewer for this draft. The General Area
Review Team (Gen-ART) reviews all IETF documents being processed by the
IESG for the IETF Chair. Please wait for direction from your document
shepherd or AD before posting a new version of the draft. For more
information, please see the FAQ at <​ 
http://wiki.tools.ietf.org/area/gen/trac/wiki/GenArtfaq>.

Review Date: 2016-04-19

Summary:

Major: 2
Minor: 0
Nits:  0

==========

(1) Major:

It is unclear to me whether this document seeks to be an authoritative 
specification of the Brotli format, or simply an explanation of the 
format the supplements another specification.

Evidence that it intends to be normative:

- The introduction states: "The purpose of this specification is to 
define a lossless compressed data format..." and "This specification is 
intended for use by software implementers to compress data into and/or 
decompress data from the brotli format."

- I had some discussion with the author after my Last Call review. In 
that discussion I learned of three successful attempts to create new 
implementations of Brotli using earlier versions of this document, 
without reference to another implementation.

Evidence that it doesn't intend to be normative:

- The intended status is Informational.

- There is no 2119 or similar language in the document

- The document provides a URL on github for an open source 
implementation. (However this is not a normative reference. There is no 
Reference section in the document.)

If this document is intended to be normative, then it should be 
restructured as such, using 2119 language, with actual references to 
stable documents, and with more clarity.

If this document is intended to be informative, then it should be 
restructured to formally identify the normative specification of the 
format, and then concentrate on supplementing that document with further 
explanation.

(2) Major:

If this document intends to be normative, *I* don't think it is 
sufficient for the task. I said the same in my Last Call review. I 
subsequently learned from the author that others have successfully used 
to create implementations, so perhaps my judgement is too harsh, but I 
remain concerned. I was told that an implementer spent 20-40 hours 
understanding this document sufficiently to create a decoder. (Distinct 
from the time required to do the implementation.) Perhaps the format is 
inherently difficult and such level of effort to understand it is 
expected. That is more effort than I was prepared to exert for a Gen-ART 
review. But without doing that I can't suggest how to improve the 
description.

The following is from my Last Call review:

---

From: Paul Kyzivat <[email-masked]>
Date: Thu, 28 Apr 2016 11:35:05 -0400

Document: draft-alakuijala-brotli-09
Reviewer: Paul Kyzivat
Review Date: 2016-04-28
IETF LC End Date: 2016-04-08
IESG Telechat date: 2016-05-05

Summary:

(Note: I first wrote this against -08 for an earlier telechat date. But 
it was rescheduled and -09 was released, so I'm resending it. I reviewed 
the changes between -08 and -09, and they don't affect my review.)

Major: 2
Minor: 0
Nits:  0

==========

(1) Major:

(2) Major: