TAPROOT, the next bitcoin evolution

Many have heard about the next upgrade proposal for bitcoin as specified by BIP341, known as taproot and BIP342 (tapscript). The objective is to improve efficiency of bitcoin transaction processing by reducing the size as well as increasing privacy, ie releasing only the minimum information for the correct execution of the transactions.

Serving your script fresh

What does this mean? Currently when you want to execute a transaction you need to publish a script, which is a (small) sequence of instructions. For instance a HTLC script (used for opening a channel on Lightning Network) is a small script containing a timelock, a set of public keys, instruction to hash data, instructions to branch code (IF THEN ELSE) etc…

While the script is small, using it millions of time can increase dramatically the size of the shared Bitcoin blockchain and can endanger the future efficiency of bitcoin. Also obviously, you can’t use large scripts.

Publishing the whole script can also give hints about the use of the transaction. For instance a HTLC transaction can be linked to a Lightning network and, while mostly never used, one can identified who can receive the funds should the timelock be activated.

That is what taproot tries to solve. Here are the simplified details of the proposal.

Merkle Tree, Schnorr signatures

Under the hood, the technology bricks are Merkle Trees and Schnorr Signatures.

A Merkle Tree is an incredibly simple yet very powerful data model, likely more powerful than the blockchain actually. It is very hard to grasp the power of this structure, as I needed several years myself to understand it. In a nutshell Merkle Trees are organising data in a such way that you don’t need to know all the data to verify they are correct, and have not been tampered with. Given a big set of data, if you are interested in verifying that only a small portion is legit you actually need to verify a lot less data because you only need a fingerprint of the rest.

Standardised by BIP340, Schnorr Signatures are also interesting in comparison with classic Digital Signature Algorithm (DSA) used today in bitcoin. The main point is that you can ‘merge’ (aggregate) many different signatures and public keys into a single one. Looking at this single signature, one does not actually know whether it is a single or several merged signatures. Also Schnorr are faster to validate, more secure than DSA, shorter in size and can be validated in batches making even faster to build the bitcoin blockchain from scratch.

How Bitcoin works today and what taproot improves for the future

Now, when you need to use bitcoin, you build a transaction spending other transactions. Those spent transactions contains one or several outputs. One output can be a public key (Pay to Public Key or P2PK, the simplest way to address an account) or a hash of a script (Pay to Script Hash or P2SH). In order to spend the transactions you need to include in your transaction the information matching the output. If the output is a P2PK, well you need to make a valid signature corresponding to the public key. If the output is a P2SH, you need to publish the script (so one can compute the hash of the script and see that the hash is the same as the output) AND execute the script (give the right input information so when the script is executed it gives ‘successful’ execution in the end, otherwise the transaction fails). For instance in a multi signature script, you need to input the correct signatures so when executed it validates enough signatures corresponding to the public keys in the script.

The main issue is that when you a run whatever program, you have a huge amount of code that is not run because they are branched out in some way, using IF THEN ELSE for instance. In most of the cases, this is ok, since you are running the code so many times with different inputs that in overall most of the code is run at least once. However in Bitcoin, you run it once and unlock your transaction. Thus the code that did not get executed in this single run is wasting space on the blockchain and leaking information.

With Taproot, you will change the way you hash the script, using a Merkle Tree instead of the flat Reverse Polish Notation (RPN). This new technique, called MAST for Merkelized Abstract Syntax Tree, has been first elaborated by Russell O’Connor and Pieter Wuille. It has been first standardised in the now deprecated BIP114. The objective is to transform a Bitcoin script into a merkle tree in such way that when you run a script, you publish only the code you run, and never publish the parts that will never be executed anyway!

Example

Here is an example with the following script ($ being the input number the user give to the script) which simply sends the transaction BTC to A if the input script is 0, and to B otherwise:

if $ = 0 then sendto A else sendto B

For simplification i am not using RPN used in bitcoin scripts, and also leaving away some extra things like version management. Also for the purpose of explanation, the way to merkelize the script is simplified and far from optimal.

In order to publish the script we create an ‘output’ in the following way:

• without taproot using classical hash256 function

output = hash256(“if $ = 0 then sendto A else sendto B”)

• with taproot the hash function is slightly more complex, to prevent from a few known attack schemes :

output = hash(hash(hash(hash(if $=0)+hash(then))+hash(hash(sendto)+hash(A)))+hash(hash(else)+hash(hash(sendto)+hash(B)))

Ok let see as a Merkle Tree to better understand the formula

The values of the green bubbles are actually fingerprints that does not leak their meanings

Validating pre-taproot script

In order to validate the pre-taproot script given the output, you need to send a transaction that contains:

• the script if $ = 0 then sendto A else sendto B
• The input $ so when it is executed. If you send $=0, then the funds are sent to A, otherwise the funds are sent to B

Validating taproot script

In the taproot case, you need to send a transaction built this way:

• If you want to send the fund to A, in order to rebuild and validate the merkle tree, you must include

- 'if $=0'
- 'then'
- 'sendto'
- 'A'
- H = hash(hash(else)+hash(hash(sendto)+hash(B)))
- $ = 0

You don’t publish anything meaningful about B, only a hash

• If you want to send the fund to B, in order to rebuild and validate the merkle tree, you must include

- 'if $=0'
- H1 = hash(then)
- H2 = hash(hash(sendto)+hash(A))
- 'else'
- 'sendto'
- 'B'
- $ = 1

Nothing meaningful about A, only 2 hashes

So you don’t need anymore to reveal all the script and nobody will ever know that you could have sent the transaction to B if you send the funds to A.

You can remark that depending on the situation, you can send more or less hashes to rebuild and validate the Merkle tree root. The way you build the tree can be optimised in order to transmit less hashes in the most likely case. In our case we would have built the tree differently if we expect that sending funds to B is more likely to happen.

To take a real world example here is a HTLC script template:

  HASH160 DUP <R-HASH> EQUAL
  IF
        "24h" CHECKSEQUENCEVERIFY
        2DROP
        <Alice's pubkey>
  ELSE
        <Commit-Revocation-Hash> EQUAL
        NOTIF
            "Timestamp" CHECKLOCKTIMEVERIFY DROP
        ENDIF
        <Bob's pubkey>
  ENDIF
  CHECKSIG

Using the MAST technique, you would publish only one of these 3 script parts, depending on the conditions, the other parts being completely obfuscated:

1 - HASH160 <R-HASH> EQUALVERIFY "24h" CHECKSEQUENCEVERIFY <Alice's pubkey> CHECKSIGVERIFY
2 - HASH160 <Commit-Revocation-Hash> EQUALVERIFY <Bob's pubkey> CHECKSIGVERIFY
3 - "Timestamp" CHECKLOCKTIMEVERIFY <Bob's pubkey> CHECKSIGVERIFY

Schnorr Signatures for better privacy

But okay, you tell me, if A and B are part of the script, they likely want to sign together the script before it is validated, which defeat the point, because to verify their signatures they have to publish their public key. Enter Schnorr signatures.

The linearity of Schnorr signatures allows A and B to construct an aggregated key C that leaks no information about A and B. And then giving a signature corresponding to the new Key C by aggregating their signatures is the same way. There even no way to be sure it is actually not a 3rd person C signing the transaction to spend his fund to A or B! No leak about B identity any more if the funds are spent to A.

What you can do with taproot

Being able not to publish only a part of the script is actually quite powerful. Merkle trees are able to logarithmically compress the size of the data you need to publish, which means you could have much more complex and bigger scripts with little impact to the size (and thus the fees) when you need to execute them. In fact the specification includes the possibility to use Huffman compression technique (like for a zip file) to construct shorter Merkle tree path for the part of the scripts that are more likely to be used. The limitation of the merle tree size is 128, which mean you could theoretically ingest a script containing for 2⁶⁴ = 1.8e+19 instructions that would fit into over billions of GB!!! Provided the maximum number of actually executed instructions is 64 in the end… While this calculation is theoretical — I don’t see the point of such a script — this clearly opens up many new possibilities for bitcoin partly compensating the lack of Turing completeness of its scripting language.

If you liked the content of this article, please clap and share to show your support!