RLP Encoding vs Decoding Analysis for EOA Validate function

[danilowhk]

RLP Encoding vs Decoding Analysis for EOA Validate function

Context

For Kakarot EOA / AA, upon receiving the raw TX data, we need to:

1. Decode the raw data to extract the values.
2. Extract the r,s,v
3. Reencode the data to extract the signature

(Here is the initial discussion.)

The process of decoding, extracting, and encoding can take place either on the RPC or within the EOA itself. For instance:

1. The RPC could decode the raw tx and then transmit the decoded data to the EOA Contract. The contract would then re-encode it (in Cairo) and hash it to verify the signature.
2. Alternatively, the RPC could decode the rawTx, extract r,s,v, encode the data, transmit the encoded data and r,s,v directly to the EOA Contract. The contract would then decode it (in Cairo) and utilize the input data to hash and verify the transaction.

To determine which flow is most efficient, I have drafted this document to provide a clearer perspective on the decision.

In Cairo, certain mathematical operations are more cost-effective than others; for example, multiplication, addition, and subtraction are less expensive than division and modulo.

Thus, in this document, I present an example flow detailing each logical step required for both encoding and decoding. I also describe the mathematical primitives (add, mul, sub, div, mod) and computational primitives associated with each logical step."

RLP Encoding

Data to Encode: List containing two numbers [1, 100000]

1. Determine the Type of Data

• Outcome: It's a list.
• Example: [1, 100000]
• Math Primitives: None
• Computational Primitives: If statements (data type check)

2. Convert Each Number to Its Byte Representation

• Sub-step: Convert numbers to bytes.
  • 1 -> [0x01]
  • 100000 -> [0x01, 0x86, 0xA0]
• Outcome: [0x01], [0x01, 0x86, 0xA0]
• Math Primitives: Division, modulo
• Computational Primitives: Loops

3. Calculate the Length of Each Item

• Sub-step: Measure the length in bytes.
  • 1 -> 1 byte
  • 100000 -> 3 bytes
• Outcome: Lengths are 1 and 3.
• Example: [1, 3]
• Math Primitives: None
• Computational Primitives: Counting (array.len())

4. Calculate the Total Length of the List

• Sub-step: Sum the lengths.
• Outcome: Total length is (1 + 3 = 4).
• Example: Length = 4
• Math Primitives: Addition
• Computational Primitives: None

5. Prepare the Prefix for Each Item

• Sub-step 1: For 1, the length is 1, so no prefix is needed.
• Sub-step 2: For 100000, the length is 3, which requires a prefix of 0x83.
• Outcome: Prefixes are [None, 0x83]
• Example: [0x01, 0x83, 0x01, 0x86, 0xA0]
• Math Primitives: Addition
• Computational Primitives: If statements

6. Prepare the Prefix for the List

• Sub-step: The list is not "long" (not over 55 bytes), so the prefix is 0xc0 + 4 = 0xc4.
• Outcome: The prefix for the list is 0xc4.
• Example: [0xc4, ..., ..., ..., ..., ...]
• Math Primitives: Addition
• Computational Primitives: If statements

7. Append the Data to the List's Prefix

• Sub-step: Add the encoded items (1 and 100000) to the list's prefix.
• Outcome: [0xc4, 0x01, 0x83, 0x01, 0x86, 0xA0]
• Example: [0xc4, 0x01, 0x83, 0x01, 0x86, 0xA0]
• Math Primitives: None
• Computational Primitives: Loops , Concatenation

Final Encoded Data: [0xc4, 0x01, 0x83, 0x01, 0x86, 0xA0]

RLP Decoding

Data to Decode: [0xc4, 0x01, 0x83, 0x01, 0x86, 0xA0]

1. Read the First Byte to Get the Prefix

• Outcome: The prefix is 0xc4.
• Example: [0xc4, ..., ..., ..., ..., ...]
• Math Primitives: None (data retrieval)
• Computational Primitives: None

2. Identify the Type and Length from the Prefix

• Sub-step: Deduct 0xc0 from 0xc4 to find the length.
• Outcome: The data type is a list, and the length is 4 bytes.
• Example: List of length 4
• Math Primitives: Subtraction
• Computational Primitives: If statements

3. Slice the Payload from the Data

• Outcome: The payload is [0x01, 0x83, 0x01, 0x86, 0xA0].
• Example: Payload = [0x01, 0x83, 0x01, 0x86, 0xA0]
• Math Primitives: None
• Computational Primitives: Array slicing

4. Identify Items in the Payload

• Sub-step 1: The first byte 0x01 is a single byte item.
• Sub-step 2: The second byte 0x83 indicates the next item is 3 bytes long.
• Outcome: We have two items: 0x01 and 0x83 0x01 0x86 0xA0.
• Example: [0x01], [0x83, 0x01, 0x86, 0xA0]
• Math Primitives: None
• Computational Primitives: Loops, If statements, Array slicing

5. Decode Each Item

• Sub-step 1: Decode 0x01 to 1.
• Sub-step 2: Decode 0x83 0x01 0x86 0xA0 to 100000.
• Outcome: The decoded items are 1 and 100000.
• Example: [1, 100000]
• Math Primitives: Multiplication, addition
• Computational Primitives: Loops, If statements

Final Decoded Data: [1, 100000]

Ethereum Spec implementation

https://github.com/ethereum/execution-specs/blob/fade6e95726c9c0b47b779fd8873b5737fbea3b3/src/ethereum/rlp.py#L27

Simple Benchmark Simple Short List Encoding function vs Herodotus Short List Decoding

OBS: As I implemented the Simple Short List Encoding, there could definitely have some optimizations to be done, but either way would like to share the current state of the tests:

Overall Encoding Code:

fn rlp_encode_long_list(items: Span<u128>) -> Span<u8> {
    let mut payload: Array<u32> = ArrayTrait::new();
    let mut items_len = items.len();
    loop {
        if items_len == 0 {
            break;
        }
        let index = items_len - 1;
        let value = *items[index];
        let encoded_item = rlp_encode_item(value);

        let mut encoded_item_len = encoded_item.len();
        loop {
            if encoded_item_len == 0 {
                break;
            }
            payload.append(*encoded_item[encoded_item_len - 1]);
            encoded_item_len -= 1;
        };
        items_len -= 1;
    };

    let mut len_of_len: u32 = payload.len();
    let mut encoded: Array<u8> = ArrayTrait::new();

    encoded.append(192 + len_of_len.try_into().unwrap());

    loop {
        if len_of_len == 0 {
            break;
        }
        let counter = len_of_len - 1;
        let value = *payload[counter];
        encoded.append(value.try_into().unwrap());
        len_of_len -= 1;
    };

    return encoded.span();
}

fn rlp_encode_item(item: u128) -> Array<u32> {
    let mut encoded_item: Array<u32> = ArrayTrait::new();
    if item < 128 {
        encoded_item.append(item.try_into().unwrap());
    } else {
        let mut reserverd_bytes = ArrayTrait::new();
        let mut temp_value = item;

        loop {
            if temp_value == 0 {
                break;
            }
            let (quotient, remainder) = u128_safe_divmod(temp_value, u128_as_non_zero(256));
            reserverd_bytes.append(remainder);
            temp_value = quotient;
        };

        let mut reserved_bytes_len = reserverd_bytes.len();
        encoded_item.append(reserved_bytes_len + 128);

        loop {
            if reserved_bytes_len == 0 {
                break;
            }
            let index = reserved_bytes_len - 1;
            let value = *reserverd_bytes[index];
            encoded_item.append(value.try_into().unwrap());
            reserved_bytes_len -= 1;
        };
    }
    encoded_item
}

Encoding Test

#[test]
#[available_gas(99999999999)]
fn test_rlp_encode_short_list() {
    let input_array = array![0x353589, 0x42, 0x453892];
    let encoded = rlp_encode_long_list(input_array.span());
    let expected = array![0xc9, 0x83, 0x35, 0x35, 0x89, 0x42, 0x83, 0x45, 0x38, 0x92];
    assert(encoded == expected.span(), 'Wrong value');
}

Decoding Test

#[test]
#[available_gas(99999999999)]
fn test_rlp_decode_short_list() {
    let mut arr = array![0xc9, 0x83, 0x35, 0x35, 0x89, 0x42, 0x83, 0x45, 0x38, 0x92];
    let (res, len) = rlp_decode(arr.span()).unwrap();
    assert(len == 1 + (0xc9 - 0xc0), 'Wrong len');

    let mut expected_0 = array![0x35, 0x35, 0x89];
    let mut expected_1 = array![0x42];
    let mut expected_2 = array![0x45, 0x38, 0x92];

    let expected = array![expected_0.span(), expected_1.span(), expected_2.span()];
    let expected_item = RLPItem::List(expected.span());

    assert(res == expected_item, 'Wrong value');
}

Results

test benchmark_space::test_encode_vs_decode::test_rlp_encode_short_list ... ok (gas usage est.: 603680)
test benchmark_space::test_encode_vs_decode::test_rlp_decode_short_list ... ok (gas usage est.: 387990)

Conclusion

Given that Div and Mod is a lot more expensive in Cairo and there isn't bigger difference in computational primitives between encoding and decoding (decoding might have a few more checks) , my conclusion is that we should just send the encoded data as u8 to the EOA Contract, decode it as u8 and use the same encoded data to generate the hash.

[enitrat]

3. Calculate the Length of Each Item
   Sub-step: Measure the length in bytes.
   1 -> 1 byte
   100000 -> 3 bytes

How do you intend to do that without loops and divs ?

[danilowhk]

Its not possible, thats why decoding is cheaper than encoding in Cairo