Inner working of OP_IF and OP_ELSE

Question

How does OP_ELSE work exactly? Is there an else if in Script?

---

According to https://en.bitcoin.it/wiki/Script#Flow_control, the statements after an OP_ELSE are executed in three cases. It says:

If the preceding OP_IF or OP_NOTIF or OP_ELSE was not executed then these statements are.

I'd like to understand how the 3rd case works, i.e. when there's a preceding OP_ELSE that is not followed. Consider this script and a True at the top of the stack:

OP_IF
    <foo>
OP_ELSE
    <bar>
OP_ELSE
    <baz>
OP_ENDIF

If we follow the explanation of the quote to the letter, then that means that <foo> and <baz> are executed. This however is quite counter-intuitive. If this is the case, then the second OP_ELSE is redundant, as <baz> can simply go after <foo> to the same effect and with less opcodes.

Is there some other interpretation I'm missing?

I stumbled upon this detail while trying to write a script with 3 different branches, something like

OP_IF top stack item is 0
    <foo>
OP_ELSEIF top stack item is 1
   <bar>
OP_ELSE
   <baz>
OP_ENDIF

I know the above isn't valid Script, but can something to this effect be achieved without resorting to the following?

OP_IF
    <foo>
OP_ELSE
    OP_IF
        <bar>
    OP_ELSE
        <baz>
    OP_ENDIF
OP_ENDIF

Note that this is more expensive not only because it has more opcodes, but because two stack items are needed in the witness in order to execute <bar> or <baz>.

Answer 1

Inner working of conditionals in Bitcoin Script

The conditionals in Bitcoin Script are conceptually implemented using a stack of booleans, each boolean indicating whether to execute the current opcode when iterating through the Script for each depth of the conditional (nested IF / ELSE).

To grasp the functioning, let's first consider a single-boolean conditioned execution of opcodes. The interpreter will iterate through the Script by setting the boolean to true (do execute ops) at the beginning. When encountering an IF it will set the boolean to the value of the pushed data preceding the IF, casted to a boolean (CastToBool in the reference implementation).
If this was true it will continue the execution of the following opcodes, effectively executing "the if {} branch".
If it was false, it will suspend execution until .... It encounters an ELSE! Encountering an ELSE will toggle the global boolean suspending execution. If it was previously false, it will become true and effectively execute "the else {} branch". To the contrary if it was true, it will become false and suspend execution of "the else {} branch".

With a bit of ASCII art (fExec is the global boolean telling whether to actually execute the OPs):

Value of fExec:  true    true      true         true  true    true         false      false            ???

Script        : |start| OP_BLABLA OP_DOSOMETHING <1> OP_IF OP_DOSOMESTUFF OP_ELSE OP_DOANOTHERSTUFF OP_ENDIF

Value of fExec:  true    true      true         true  false    false       true      true             ???

Script        : |start| OP_BLABLA OP_DOSOMETHING <0> OP_IF OP_DOSOMESTUFF OP_ELSE OP_DOANOTHERSTUFF OP_ENDIF

Note how i marked the value of fExec as ??? when encountering OP_ENDIF. That's because the real implementation is slightly more complicated: in order to support nested conditionals, this is not a single boolean but a vector of booleans that are used to determine execution. That is:

• OP_IF will push a new boolean to the vector
• OP_ELSE will toggle the last boolean of the vector
• OP_ENDIF will pop the last element of the vector

Going further

Multiple ELSE for a single IF

Note that the implementation of the ELSE being a single toggle it means that nothing prevents to toggle two times in a row. That is, you can have many following ELSE opcodes before the ENDIF. Two following ELSEs would effectively toggle the last boolean twice, hence executing the following opcodes as it would for "the if {} branch".

Therefore in the example from your question:

OP_IF <foo> OP_ELSE <bar> OP_ELSE <baz> OP_ENDIF

That's indeed <foo> and <baz> that will be executed.

Quadratic behaviour when computing fExec from the vector of booleans

The implementation of the conditional logic was modified in 2020 by Pieter Wuille to fix a quadratic behaviour found by Segio Demian Lerner.
Therefore the actual implementation does not actually use a stack for the booleans anymore, rather it stores the "top boolean" in a dedicated data structure imitating the previous implementation.

Slightly related Tapscript rule

The proposed new addition to the Script rules as part of the proposed Taproot soft fork (Tapscript) lifts the limit of 201 OP codes. This was made possible by the elimination of the aforementioned quadratic behaviour.