bug: under constrained segments

[ClementWalter]

Bug Report

Kakarot version

We need to revise in the whole code base places where we allocate segments and then "fill" them with utils like RLP.decode or load_packed_bytes to make sure that the segments are actually constrained.

We also need to make sure that every arr is used with the proper arr_len to use the right segment arena

[obatirou]

For more context: rephrasing explanation in TG messages to ensure I understood well the problem and what is asked of this issue.

In the codebase, when a segment assignation is needed, it can be of 2 forms:

let (arr: felt*) = alloc();
let arr_len = foo(arr, data_len, data);

or

let (arr_len, arr) = foo(data_len, data)

If there is no need to fill an already existing segment or no need to assert depending of the function call (like RPL.decode which will have different assert depending tx type). The first form can be refactored to the second one for better guaranties by checking arr_len.

For form 1, we need to check that the returned segment is properly constrained For form 2, we need to check that arr_len is properly checked and correspond to what is expected.

For the form 2, it can be tricky, as a function can return it and the arr_len would be check in a completely different part of the codebase.

I think we should be several to do the check of the codebase as it can be easy to miss some.

[obatirou]

Did not found an undercontrained example on my end on first pass Will do an other one after a step back

[ClementWalter]

example of un underconstrained function is

https://github.com/kkrt-labs/kakarot/blob/a7af5dec26cea8fd191c8a2e98548ca19de7ee43/src/utils/rlp.cairo#L21-L57

where the data_len is not used so that when data_len = 0, [data] can be filled arbitrarily

[ClementWalter]

and following usages like

local len_bytes_count = prefix - 0xb7;
let string_len = Helpers.bytes_to_felt(len_bytes_count, data + 1);

we need to make sure that data_len > len_bytes_count

etc.