1

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.

1

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.

  • Very helpful, thanks David. So what is the relationship between taproot and MAST? It seems like taproot is a proposed implementation of MAST, but with the added benefits of a consolidated pubKey? – Raz Lemniscate Aug 17 '18 at 15:12
  • That's correct, Taproot is a form of MAST where the merkle root is combined with a public key to create a secondary public key that can be spent by the private key corresponding to the primary public key. Basically, if you take an ECDSA public key and add an integer to it to create a secondary public key, you can create the corresponding secondary private key by adding the name integer to it. Revealing the number later doesn't reduce the security of the primary keypair, so if you need to publicize the merkle root to use MAST, you can---but otherwise you can just sign. – David A. Harding Aug 17 '18 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.