bug: fn byte_array_to_felt252_[big/little]_endian

[RedVelvetZip]

• [ ] issue #170
• [ ] follows contribution guide
• [ ] code change includes tests

New fn byte_array_to_felt252_endian is designed to take in little-endian numbers, unlike byte_array_to_felt252, which takes in big-endian numbers. I'm unsure if byte_array_to_felt252 has relevance elsewhere in the project, so I created a new function rather than editing the existing one.

[vercel[bot]]

@RedVelvetZip is attempting to deploy a commit to the keep-starknet-strange Team on Vercel.

A member of the Team first needs to authorize it.

[RedVelvetZip]

outlining the process here in case any new contributors are using old PRs as a reference on where to dig in to get up to speed,

Process

Step 1: I added some debug logs to src/engine.cairo in the pull_data function

    fn pull_data(ref self: Engine, len: usize) -> Result<ByteArray, felt252> {
        let mut data = "";
        let mut i = self.opcode_idx + 1;
        let mut end = i + len;
        let script = *(self.scripts[self.script_idx]);

        // Debugging output
        println!("Pulling data: len = {}, start = {}, end = {}, script_len = {}", len, i, end, script.len());

        if end > script.len() {
            return Result::Err(Error::SCRIPT_INVALID);
        }
        while i < end {
            data.append_byte(script[i]);
            i += 1;
        };
        self.opcode_idx = end - 1;
        return Result::Ok(data);
    }

and some debug logs to src/opcodes/engine.cairo

pub fn opcode_push_data(n: usize, ref engine: Engine) -> Result<(), felt252> {
    // Debugging output before pulling data
    println!("opcode_push_data: Attempting to pull {} bytes", n);

    let data = engine.pull_data(n)?;

    // Debugging output after pulling data
    println!("opcode_push_data: Pulled data = {:?}", data);

    engine.dstack.push_byte_array(data);
    return Result::Ok(());
}

pub fn opcode_push_data_x(n: usize, ref engine: Engine) -> Result<(), felt252> {
    // Debugging output before pulling length
    println!("opcode_push_data_x: Attempting to pull length of {} bytes", n);

    let data_len: usize = utils::byte_array_to_felt252(@engine.pull_data(n)?).try_into().unwrap();

    // Debugging output after pulling length
    println!("opcode_push_data_x: Pulled data length = {}", data_len);

    // Debugging output before pulling actual data
    println!("opcode_push_data_x: Attempting to pull {} bytes of data", data_len);

    let data = engine.pull_data(data_len)?;

    // Debugging output after pulling actual data
    println!("opcode_push_data_x: Pulled data = {:?}", data);

    engine.dstack.push_byte_array(data);
    return Result::Ok(());
}

Step 2:

On execution of the suggested command to replicate the bug scarb cairo-run '[[],276712210673542446309439866597955351862704615481,20,[],16079555761881420,7]' , I received the following logs

Running Bitcoin Script with ScriptSig: '0x4e 0x01000000 0x09' and ScriptPubKey: '9 EQUAL'
opcode_push_data_x: Attempting to pull length of 4 bytes
Pulling data: len = 4, start = 1, end = 5, script_len = 6
opcode_push_data_x: Pulled data length = 16777216
opcode_push_data_x: Attempting to pull 16777216 bytes of data
Pulling data: len = 16777216, start = 5, end = 16777221, script_len = 6
Execution failed: Invalid script data
Run completed successfully, returning [0]

The value 0x01000000 is being interpreted as 16777216. This is bc that's what it equals in big-endian format

This issue stems from fn byte_array_to_felt252 misinterpretting the data as big-endian

big endian == least significant bits are on the right little endian == least significant bits are on the left

Bitcoin reads data in little endian in batches of two digits

so 0x01000000 is read as 00 concat with 00 concat with 00 concat with 01, which equals 1 instead of 2^24 (which equals 16777216)

Step 3:

To fix this, I created an additional fn

pub fn byte_array_to_felt252_little_endian(byte_array: @ByteArray) -> felt252 {
    let mut byte_shift = 1;
    let mut value = 0;
    let mut i = 0;
    let byte_array_len = byte_array.len();
    while i < byte_array_len {
        value += byte_shift * byte_array[i].into();
        byte_shift *= 256;
        i += 1;
    };
    value
}

and renamed the original function to [...]_big_endian bc the compiler still uses a big endian conversion from byte arrays to felt252s