FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

`lshift_prevent_overflow(bits = 0)` empties/underflows `altstack` due to missing `OP_TOALTSTACK` pushes in limb shifters · Issue #399 · BitVM/BitVM · GitHub

/ BitVM Public

lshift_prevent_overflow(bits = 0) empties/underflows altstack due to missing OP_TOALTSTACK pushes in limb shifters #399

Description

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions


    Back | FazBrowse Home | New Git URL