EVM Static Jumps and Stack Limitations

validate.c

code[code_size] contains code to validate
frame_size[code_size] is filled with -1
validated_subs = Set()
subs_validation_queue = FIFO()

validate()
{
    // Validate the "main" subroutine
    validate_subroutine(0, 0, 0)

    while subs_validation_queue not empty
    {
        entersub_PC = subs_validation_queue.pop()

        // Validate the subroutine, but skip the ENTERSUB instruction.
        validate_subroutine(advance_pc(entersub_PC),
                            arg_size(entersub_PC),
                            return_size(entersub_PC))
    }
}

enqueue_subroutine_validation(entersub_PC)
{
    if entersub_PC not in validated_subs
    {
        validated_subs.insert(entersub_PC)
        subs_validation_queue.push(entersub_PC)
    }
}

struct Sub
{
    entersub_PC
    jumpdests = Set()
}

build_entersub_jumpdest_sets()
{
    PC = 0
    subs = Set()
    current_subs = []
    global_jumpdests = Set()
    in_global = true

    while PC < len(code)
    {
        instruction = code[PC]

        if instruction is JUMPDEST
            for sub in current_subs
                sub.jumpdests.insert(PC)
            if in_global
                global_jumpdests.insert(PC)

        if instruction is STOP, RETURN, SUICIDE, RETURNSUB
            current_subs.reset()
            in_global = false

        if instruction is ENTERSUB
            sub = Sub(PC)
            subs.insert(sub)
            current_subs.append(sub)

        PC = advance_pc(PC)
    }

    return subs, global_jumpdests
}

build_jumpdest_set(PC)
{
    set = Set()
    while true
    {
        instruction = code[PC]

        if instruction is STOP, RETURN, SUICIDE or RETURNSUB
            break

        if instruction is JUMPDEST
            set.insert(PC)

        PC = advance_pc(PC)
    }
    return set
}

validate_subroutine(PC, arg_size, return_size)
{
    local_size = 0
    jumpdests = build_jumpdest_set(PC)

    // traverse code sequentially, recurse for jumps
    while true
    {
        instruction = code[PC]

        // check condition 3 & 6
        // The requires_stack() informs how many stack items an
        // instruction is expecting, e.g. DUP16 - 16, ADD - 2.
        // This value is represented by “alpha” in YP.
        if local_size < required_stack(instruction)
            return false

        // FIXME: I'm not sure about it, we are allowing unbalanced stack here.
        if instruction is STOP, RETURN, or SUICIDE
            return true

        // check condition 9
        if instruction is JUMPDEST
        {
            // if frame size set we have been here before
            if frame_size[PC] >= 0
                return local_size == frame_size[PC]

            frame_size[PC] = local_size
        }

        // add or remove stack items according to instruction
        local_size = adjust_sp(local_size, instruction)

        // check conditions 3 & 5
        if local_size < 0
            return false
        if local_size > 1024
            return false

        // Additional entry point, here not treated as a new subroutine.
        // This ENTERSUB might be also added to the queue by explicit JUMPSUB.
        if instruction is ENTERSUB
            if local_size < arg_size(PC)
                return false

        // return from recursion to subroutine entry - goto last check.
        if instruction is RETURNSUB
            break

        // reset PC and do not advance it at end of loop
        if instruction is JUMPTO
        {
            PC = jumpdest(PC)
            if PC not in jumpdest
                return false
            continue
        }

        // recurse to validate conditional branch
        if instruction is JUMPTOIF
        {
            PC = jumpdest(PC)
            if PC not in jumpdest
                return false
            // TODO!!!!
        }

        // check condition 7
        if instruction is JUMPSUB
        {
            entersub_PC = entersub(PC)
            if local_size != arg_size(entersub_PC)
                return false
            enqueue_subroutine_validation(entersub(PC))
            local_size -= arg_size(entersub_PC)
            local_size += return_size(entersub_PC)
        }

        // advance PC according to instruction
        PC = advance_pc(PC)
    }

    return local_size == return_size
}