Summary
The function lshift_prevent_overflow assumes that its helper shifters populate the altstack with $(N_\text{LIMBS}-1)$ intermediate limbs and, unconditionally, pulls exactly $(N_\text{LIMBS}-1)$ items back via a trailing loop of OP_FROMALTSTACK.
This assumption is violated when bits = 0: both limb_lshift_without_carry(0) and limb_lshift_with_carry(0) execute the for i in 1..=bits body zero times and therefore never reach the branch that performs OP_TOALTSTACK.
Consequently, no elements are pushed to the altstack, while lshift_prevent_overflow still executes the following:
for _ in 1..Self::N_LIMBS {
OP_FROMALTSTACK
}
which attempts to pop $(N_\text{LIMBS}-1)$ items from an empty altstack.
The observable effects are (i) an immediate stack underflow at runtime, or (ii) a silent stack-shape mismatch depending on the embedding, both of which break the function’s stated contract.
Expected Behavior
For any bits ∈ [0, LIMB_SIZE], the function should return the left-shifted BigInt with correct carry propagation, preserve stack discipline, and leave the altstack empty upon return.
In particular, bits = 0 is a semantic no-op: the input BigInt must be returned unchanged, and the altstack must not be touched (or, if touched, must be restored to its prior state).
Acknowledgments: This issue was identified using Pomelo (https://eprint.iacr.org/2024/1768) by the UCSB/Nubit team.
Summary
The function lshift_prevent_overflow assumes that its helper shifters populate the altstack with $(N_\text{LIMBS}-1)$ intermediate limbs and, unconditionally, pulls exactly $(N_\text{LIMBS}-1)$ items back via a trailing loop of OP_FROMALTSTACK.
This assumption is violated when bits = 0: both limb_lshift_without_carry(0) and limb_lshift_with_carry(0) execute the for i in 1..=bits body zero times and therefore never reach the branch that performs OP_TOALTSTACK.
Consequently, no elements are pushed to the altstack, while lshift_prevent_overflow still executes the following:
which attempts to pop $(N_\text{LIMBS}-1)$ items from an empty altstack.
The observable effects are (i) an immediate stack underflow at runtime, or (ii) a silent stack-shape mismatch depending on the embedding, both of which break the function’s stated contract.
Expected Behavior
For any bits ∈ [0, LIMB_SIZE], the function should return the left-shifted BigInt with correct carry propagation, preserve stack discipline, and leave the altstack empty upon return.
In particular, bits = 0 is a semantic no-op: the input BigInt must be returned unchanged, and the altstack must not be touched (or, if touched, must be restored to its prior state).
Acknowledgments: This issue was identified using Pomelo (https://eprint.iacr.org/2024/1768) by the UCSB/Nubit team.