Skip to content

Instantly share code, notes, and snippets.

Last active August 18, 2021 21:08
Show Gist options
  • Save markblundeberg/94650e69ebf056215de6ad1a716de559 to your computer and use it in GitHub Desktop.
Save markblundeberg/94650e69ebf056215de6ad1a716de559 to your computer and use it in GitHub Desktop.
How might Taproot be implemented in BCH, and do we need it?

Taproot is an interesting technology to enable multiparty privacy on a bitcoin. Currently, there is a problem with multiparty contracts in that they are obvious deviation from the most common script type (P2PKH), which hurts privacy. The script that gets used will typically indicate exactly what kind of protocol was at play. Also complex P2SH scripts take extra resources (transaction size and CPU cycles).

The basic idea with Taproot is that instead of P2SH where a script is committed by a hash, you can hide a script (or set of possible scripts) as a commitment within a normal-looking public key. Now there are two ways to spend from this public key:

  1. Create a normal transaction signature using the public key, or,
  2. Reveal the commitment, and provide parameters that satisfy the revealed script.

To do #1, it means you need to know the private key, or, you have a set of signers who are able to produce a signature (that's where Schnorr signatures come in to play, it's easier to create such a multi-party signature). To do #2, you don't need to know the private key, but you do need to know the hidden commitment and you need to satisfy the locking script's conditions (which will undoubtedly include a signature from another key).

Why this helps privacy is that if #1 happens, then nobody watching the blockchain will have any indication that there was a secret script, since all they see is an ordinary public key and an ordinary signature. Multi-party contracts can be carefully arranged so that all parties know the commitment #2, but nobody knows the private key for #1, so #1 can only be executed with all parties consent. The parties are incentivised to complete their smart contract by route #1: even though it's more awkward to arrange multi-party signing, the result is cheaper in fees and it is more private. But, in case of a breakdown, they can "appeal" to #2 and satisfy that contract instead.

The basic cryptographic primitive at work is that the on-chain public key, i.e., the "address" public key, is constructed as follows (n is the cryptographic group order):

X = Hash(inner pubkey, inner data)  mod n
Address pubkey = inner pubkey +  X * generator

Assuming that collisions in the hash function are impractical to discover, then it is impractical to find another inner pubkey and inner data that produce the same address pubkey. Thus, this address pubkey is a commitment to the inner pubkey and inner data in question. Yet, it is also easy to produce signatures that validate against this address key (since we have address privkey = (inner privkey + X) mod n), and never reveal that it was actually an implicit commitment. Multiparty signing schemes can trivially incorporate the key offset X, which just needs to be added to one party's key.

Taproot uses the above primitive to commit to a multitude of scripts by arranging the scripts as a merkle tree, and then putting the merkle root in Inner data. Security is strengthened by using various magic prefixes like "TapBranch" and "TapLeaf" in the hashes so as to not have merkle ambiguities nor interactions with other algorithms.

(One way) How we could do BCH Taproot

Taproot is a very generic technology and it could be introduced in many different ways. This is especially so for BCH, which is open to doing hard forks. I'd like to suggest one way that seems elegant to me. Taproot can be introduced to BCH in a purely-additive hard fork on P2PKH outputs. Purely additive hard forks have technical advantages for code complexity since after activation, we can pretend that Taproot was "always possible".

As a reminder, a regular P2PKH scriptPubKey is of the form OP_DUP OP_HASH160 <20 byte hash of pubkey> OP_EQUALVERIFY OP_CHECKSIG. Normally this is unlocked using the following two-push scriptSig, in the spending transaction:

<tx signature> <pubkey>

To make Taproot purely additive, we would spend a P2PKH like so, where there are additional pushes before the transaction signature, and the transaction signature is now NULL (pushed using OP_0):

<taproot data> ... <taproot data> <tx signature = null> <pubkey>

When the P2PKH script is run with this data, it will check that the correct pubkey was provided, then CHECKSIG will execute without error yet leave FALSE on the top of the stack, since it was performed with a NULL signature. Normally, leaving FALSE on the stack would then count as a script failure and invalidate the transaction. Thus, there exists no transaction on-chain where the P2PKH script returns false. The proposal to introduce taproot is as follows:

  • If the scriptPubKey is P2PKH (25 bytes long and with given prefix/postfix bytes),
  • and if the scriptPubKey has executed without error (which requires <pubkey> to be correct),
  • but it has left FALSE on the top of the stack,
  • then execute the remainder as in Taproot.

The <taproot data> above would be various pushes, in this order:

  • Any stack items that need to get consumed by the redeemScript,
  • The redeemScript itself,
  • Various merkle data that proves the redeemScript is committed as a leaf node from the root node (Inner data), and
  • The inner pubkey.

The resulting code implementation would resemble P2SH to a great deal (see the usage of redeemScript), except it would have more complex triggering preconditions.


The proposed mechanism for taproot achieves the best possible anonymity set since it hides amongst the very common P2PKH outputs that exist already. There is a danger here, just like when Schnorr signatures were introduced to BCH, that we are exposing existing keyholders and existing wallets to new cryptographic risk since a new algorithm is able to spend their coins. Even though the scheme seems safe, this risk needs to be seriously considered.

Key-offsetting schemes

As an example, one side-effect could be a weakening of the security of a hypothetical reusable payment code scheme. In such schemes, a sender sends funds not to the recipient's public key, but instead to a randomly offset variation on the recipient public key. Such schemes are used to prevent reuse of a static recipient address, without the recipient needing to generate and communicate a new address each time.

Now, suppose the scheme is too simple, so that the sender is able to choose the exact offset. With taproot, they now have an avenue to attack by choosing the offset to be a taproot commitment. This would allow the sender to take back the funds at any time, until the intended recipient spent them to a proper wallet address.

Collision attacks

The security of this P2PKH Taproot proposal in a multiparty setting can unfortunately be as low as 80 bits (i.e., just as low as P2SH can be), since engineering a collision in the pubkey hash (20 bytes) is sufficient to create an alternative spend path. This can be increased to 128 bits of security if the multiparty setup scheme is carefully designed to stop collision attacks, in which case a discrete logarithm attack on the public key is the fastest approach. Note that the collision attack does not necessarily require 2^80 memory, but actually can be done in small memory and ~2^82 iterations.

Unfortunately, preventing collision algorithms from working seems to always require some interactivity between the parties, during a setup phase. But remember, the primary advantage of Taproot (over just plain Schnorr with chained transactions) was that it allowed easier non-interactive setup!

I suspect it is for this reason that on BTC, the intent is to have 256-bit taproot addresses (128 bits of collision security) instead of 160-bit. On BCH, we could have equivalent security level by using "P2PKH2" addresses (using OP_HASH256 instead of OP_HASH160) or P2PK outputs (raw public keys), however if we do this then the whole anonymity set advantage of hiding behind P2PKH has disappeared.

All that said, it's worth noting that an attack requiring 2^82 iterations is nothing to sneeze at, especially since each iteration requires a scalar×point multiplication (the slowest elliptic curve operation, and far far slower than hashing). As an example, this FPGA accelerated elliptic curve system required 50 microjoules per scalar×point operation. An ASIC could do better, but I would be surprised to see better than 1 microjoule per scalar×point operation during the next decade. Even then, mounting a collision attack would be extremely expensive, billions of dollars in electricity costs alone. For everyday amounts of money locked up in Taproot contracts, mounting an attack will simply be uneconomical for quite some time. For comparison, collision attacks on P2SH do not necessarily need an elliptic curve operation (only hashing), and thus using ASICs (good mining asics get currently ~ 0.0005 microjoule per hash) it can be >10000x easier to engineer collisions on P2SH.

Does BCH need Taproot?

The stated advantage of Taproot is that parties can enter into a covenant without landing anything unusual on chain, in the case of cooperative closure.

In the interactive case this is however already mostly possible without Taproot, using private aggregated signature schemes together with prearranged off-chain refund transactions, provided that the parties are fully interactive during the setup and funding phases. Alice can create a funding on to an aggregated public key she shares with Bob, and she only broadcasts this provided that a second timelocked refund transaction has been arranged and signed (requiring both Alice & Bob) ahead of time. As long as malleability concerns are addressed, this is a secure scheme. I discussed this mechanism in my talk, a couple of months ago. This is however a bit limited due to the required interactivity and complications of off-chain transactions.

What Taproot offers is a less interactive setup and funding, and perhaps also simplification for protocol designers. The reduced need for interactivity might be essential for some protocols to gain privacy. I found it difficult to think up schemes that really benefit from Taproot, and this is the only example I could find:

  • a reusable payment code scheme can set the inner pubkey to a tweaked recipient public key, but also include a taproot script. The recipient can spend the funds at any time normally; the sender can refund using the taproot script, but only after a certain time. While similar refundable schemes could be done with off-chain transactions or shared private keys, it is not possible to prove whether funds have actually been accepted or not.

The collision threat does loom over all the noninteractive schemes -- they have to choose between lower privacy (using stronger-than-P2PKH address), or keeping the anonymity set with lower theoretical security (on P2PKH). But, in the case of payment code systems, at least Taproot is not making things worse since they anyway already have the vulnerability to collisions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment