NethermindEth / cairo-vm-go

A virtual machine for Cairo written in Go
MIT License
79 stars 49 forks source link

`UsortVerifyMultiplicityBody` hint is wrongly implemented #391

Closed TAdev0 closed 3 months ago

TAdev0 commented 3 months ago

Python hint :

//> current_pos = positions.pop()
//> ids.next_item_index = current_pos - last_pos
//> last_pos = current_pos + 1

Current go hint:

newCurrentPos, err := utils.Pop(&positions)
if err != nil {
    return err
}

currentPos, err := ctx.ScopeManager.GetVariableValue("current_pos")
if err != nil {
    return err
}

currentPosInt, ok := currentPos.(int64)
if !ok {
    return fmt.Errorf("cannot cast current_pos to int64")
}

lastPos, err := ctx.ScopeManager.GetVariableValue("last_pos")
if err != nil {
    return err
}

lastPosInt, ok := lastPos.(int64)
if !ok {
    return fmt.Errorf("cannot cast last_pos to int64")
}

// Calculate `next_item_index` memory value
newNextItemIndexValue := currentPosInt - lastPosInt

currentPos, err := ctx.ScopeManager.GetVariableValue("current_pos") is problematic , and should not exist. current_pos is calculated with utils.Pop(&positions) and there are only positions and last_pos taht should be fetched from the scope.

Also:

return ctx.ScopeManager.AssignVariables(map[string]any{
    "current_pos": newCurrentPos,
    "last_pos":    int64(currentPosInt + 1),
}

will write in scope current_pos while it shouldn't. current_pos is calculated with positions.pop() for each iteration in the recursive call to verify_multiplicity

https://github.com/starkware-libs/cairo-lang/blob/efa9648f57568aad8f8a13fbf027d2de7c63c2c0/src/starkware/cairo/common/usort.cairo#L99C12-L99C31