RLP Strictness Questions

[fjl]

While working on improving the strictness of the RLP decoder in
go-ethereum (ethereum/go-ethereum#711), a few questions have popped up:

Minimal Size

In any context (also for non-scalars), the following encodings
are invalid because their size is not minimal:

non-canonical encoding	should be
8102	02
B800	80
B90000	80
BA0002FFFF...	B902FFFF...

The paper doesn't seem to resolve this ambiguity. Should it?

Encoding of fixed-size values

Some ethereum values (such as addresses) have a fixed bit width.
go-ethereum currently accepts byte arrays of smaller size and pads the
resulting value with zero bytes.

Example: when decoding into [20]byte, the input 8101 would be accepted and
would produce {1, 0, 0, 0, ...} as the result.

Should the encoding of fixed size types be restricted so the full number
of bytes must be encoded?

[winsvega]

Actually there are cases when BA0002FFFF should be 0002FFFF like when we are importing "data" field.
The client should do it strict. If we are importing int value, then it should throw an error while decoding such RLP (leading zeros).

[fjl]

Note: BA0002FFFF... means:

b	meaning
BA	byte array with two bytes of length of length
0002	length of length is two bytes (this one has a leading zero byte)
FFFF	length of content is 0xFFFF bytes
...	content of the byte array

My example was wrong though, now updated.

[winsvega]

I see. leading zeros in length of length are not covered.

[fjl]

The leading zeros rule does not seem strict enough to cover cases such as 8102, which should encoded as a single byte.

[winsvega]

according to the YP:

If the byte-array contains solely a single byte and that single byte is less than 128, then the input is exactly equal to the output.

81xx should be xx if xx < 128, otherwise it is 81xx

and length is expected to be:
BE(||x||)

BE means it could not have leading zeros.
So I guess the YP has resolved this ambiguity.

Should the encoding of fixed size types be restricted so the full number
of bytes must be encoded?

Yes it should, otherwise you state such RLP as invalid Transaction/Block RLP. (not incorrect RLP, though)

I will add RLP tests for your scenarios.

[fjl]

Thank you.

‎Maybe ‎the part about length encoding should be more explicit since an input such as 8154
is invalid (not minimal) but does not contain a leading zero.

[fulldecent]

I think this latest RLP "minimum" language addresses all of the items in this issue. Is anything left? Can this be closed?

[acoglio]

I believe that this could be indeed closed.

The YP defines the encoding function RLP in eqs. (179), (180), etc., and with that, implicitly, the set of valid encodings as the image of that function (excluding \varnothing). Anything outside that set (e.g. 8102, B800, etc.) cannot be produced by the encoding function, and thus is not a valid encoding as defined.

Decoding is implicitly defined as the inverse of encoding. A "relaxed" decoder that accepts 8102, B800, etc. would be a left inverse of encoding, but not a right inverse. It must reject those to be both a left and right inverse.

Just for reference, here is a formally verified RLP decoder that I wrote in the ACL2 theorem prover:

• https://github.com/acl2/acl2/blob/master/books/kestrel/ethereum/rlp/decoding-executable.lisp (code)
• http://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/?topic=ETHEREUM____RLP-DECODING-EXECUTABLE (documentation)

[acoglio]

@nicksavers Do you agree that this Issue can be closed?

[fjl]

Yes, we can close this issue now.