Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RLP Strictness Questions #116

Closed
fjl opened this issue Apr 15, 2015 · 10 comments
Closed

RLP Strictness Questions #116

fjl opened this issue Apr 15, 2015 · 10 comments

Comments

@fjl
Copy link

fjl commented Apr 15, 2015

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
Copy link
Contributor

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
Copy link
Author

fjl commented Apr 15, 2015

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
Copy link
Contributor

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

@fjl
Copy link
Author

fjl commented Apr 15, 2015

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

@winsvega
Copy link
Contributor

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
Copy link
Author

fjl commented Apr 15, 2015

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
Copy link
Contributor

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

@acoglio
Copy link
Member

acoglio commented Apr 13, 2019

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:

@acoglio
Copy link
Member

acoglio commented May 12, 2019

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

@fjl
Copy link
Author

fjl commented May 12, 2019

Yes, we can close this issue now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants