Could Taproot or Graftroot enable the execution of complex scripts? From my understanding, Taproot uses a Merkle Tree structure whose root represents the outcome of a script. That representation is in the form of a signature that may unlock the inputs associated with its public key counterpart, which is shared by all participants.

I have two questions related to this:

First, how is the script structured in the tree? Does each path represent a different execution outcome? If so, how are the potential outcomes defined?

Second, if it follows a Merkle Tree structure, is there a limit in terms of the size of the script? I'm inclined to say no, given that this occurs off-chain, but I might be wrong.
First, how is the script structured in the tree? Does each path represent a different execution outcome? If so, how are the potential outcomes defined?


The taproot email doesn't specify how the script is placed into the merkle tree.  It can be that each leaf node in the tree is a different script (BIP114-style) or it can be that a parameter can be passed that allows extracting multiple leaves so that parts of the script can be reused (BIP116-style).

The reason this detail is not in the taproot email is because that email was about rearranging the previous ideas about merklized scripts (MAST) so that the expected default condition (everybody signs) was the easiest and cheapest option to use with no need to actually handle the merkle tree in the expected case.  The ideas about how to organize and use the tree are a separate discussion.


  Second, if it follows a Merkle Tree structure, is there a limit in terms of the size of the script? I'm inclined to say no, given that this occurs off-chain, but I might be wrong.


The merkle root / public key for taproot consumes a fixed number of bytes (say 64), which is trivial, but the spending transaction will have to provide the spending script as well as a merkle proof providing a list of hashes (and a few bits of path information) proving that the provided script connects to the taproot's merkle root.

This information will be subject to the fundamental block size limit of 4 million weight units and, depending on how it is implemented, may also be subject to Bitcoin's current limits on witness size (10,000 weight units for segwit v0).  The good news is that it's impossible for an honest person to create a merkle tree that requires more than about 8,000 bytes to create the merkle proof (not counting the script) even if they had at their disposal all the energy in the universe.  (Assuming we use Bitcoin's SHA256d hash function.)



The above is an illustration from my article about MAST showing how the encoding of alternative scripts (subscripts) into a MAST grows at log2 whereas it grows linearly with the existing mechanism.

For a script with a million possible outcomes (tree depth equals 20) would require about 643 bytes (20 * 32 + ceil(20 / 8)), allowing actual witness script and witness data to be up to about 9,300 bytes.  Of course, if everyone signs, you don't need to provide any of that data---you just push a single signature.