`Value::prune` corrupts sum tag bits when prepending Left (0) tag

[KyrylR]

With a help of Claude and insight from @topologoanatom and @gerau, here what I have found and tested:

When Value::prune creates a Left value by calling Value::left(), the resulting value can have corrupted tag bits. This causes ReachedPrunedBranch errors during execution when the BitMachine reads the wrong branch selector.

In src/value.rs, the right_shift_1 function has an optimization bug. When prepending a 0 bit (for Left values) and bit_offset > 0, it simply decrements the bit_offset without clearing the existing bit:

} else {
    // ...and if we are inserting a 0 we don't even need to allocate a new [u8]
    (Arc::clone(inner), bit_offset - 1)
}

The bug is triggered when:

1. A witness value like Left(Right(data)) is pruned to a smaller type
2. The pruning creates nested Left/Right wrappers via Value::left() and Value::right()
3. The inner value's bit representation has a 1 at the position where the outer 0 tag should be inserted

This happened in the #333, where the program was with complex sum types that have multiple execution paths, where pruning converts Case nodes to AssertL/AssertR.

Possible fix

Check if the bit at new_bit_offset is already 0 before skipping allocation. If it's 1, allocate and clear it:

} else {
    let new_bit_offset = bit_offset - 1;
    let byte_idx = new_bit_offset / 8;
    let bit_mask = 1 << (7 - new_bit_offset % 8);
    if (inner[byte_idx] & bit_mask) == 0 {
        // The bit is already 0, no need to allocate
        (Arc::clone(inner), new_bit_offset)
    } else {
        // The bit is 1, we need to clear it to insert a 0
        let mut bx: Box<[u8]> = inner.as_ref().into();
        bx[byte_idx] &= !bit_mask;
        (bx.into(), new_bit_offset)
    }
}

With the fix above the bug described in the #333 does not happen

[roconnor-blockstream]

Yeah, the assumption that unused bits in the array backing are always 0 does seem to be faulty. In particular to_value() will clone a value by copying the entire inner array backing, which can have other unused bits set or not set.

I'm no Rust expert, but I'd be inclined to write that whole bit_offset > 0 branch to refactor common code:

    let new_bit_offset = bit_offset - 1;
    let byte_idx = new_bit_offset / 8;
    let mut bx: Box<[u8]> = inner.as_ref().into();
    let bit_mask = 1 << (7 - new_bit_offset % 8);
    if new_bit {
        bx[byte_idx] |= bit_mask;
    } else {
        bx[byte_idx] &= !bit_mask;
    }
    (bx.into(), new_bit_offset)

[topologoanatom]

Another possible fix is to ensure proper cleanup of offset bits higher up in the call tree. The right_shift_1() function is used only in the left() and right() functions, which in turn depend on product(). One approach is to clean the offset bits in product(), for example:

fn product(
    left: Option<(&Arc<[u8]>, usize)>,
    left_bit_length: usize,
    right: Option<(&Arc<[u8]>, usize)>,
    right_bit_length: usize,
) -> (Arc<[u8]>, usize) {
    if left_bit_length == 0 {
        if let Some((right, right_bit_offset)) = right {
            (Arc::clone(right), right_bit_offset) // may contain garbage bits
        } else if right_bit_length == 0 {
            (Arc::new([]), 0)
        } else {
            (Arc::from(vec![0; right_bit_length.div_ceil(8)]), 0)
        }
    ...

A second approach, as @roconnor-blockstream mentioned, is to clean the offset bits in the to_value() function. Both approaches fix the issue described in #333, but I think cleaning them in product() is more correct from a design standpoint.

Here is code for both solutions https://gist.github.com/topologoanatom/5cf8551918d9d0fd5c7788e90e65aecd