Bitcoin

Graftroot on Bitcoin today: No fork needed

This post was first published on Medium.

We have demonstrated how to implement Taproot on the original Bitcoin using contractless contract. We show that its follow-up proposal, Graftroot, can be implemented in a similar fashion.

Bitcoin Magazine
Source: Bitcoin Magazine

Graftroot in BTC

Similar to Taproot, there are two ways to spend fund locked in an aggregated public key P, created by multiple parties:

  1. Cooperative Case: a.k.a. Default Key Spending Path
    All parties agree and sign to release the fund in a regular payment transaction, the same as in Taproot.
  2.  Uncooperative Case: a.k.a. Alternative Script Spending Path

If any party fails to sign, an alternative script is chosen to run to unlock the fund. In Taproot, the script is a leaf node in a Merklized Alternative Script Tree (MAST). It is authorized by linking the root of the MAST m in P and verifying the script is indeed a leaf of the MAST via Merkle proof. In Graftroot, however, the alternative script, called a surrogate script, is authorized simply by all parties jointly signing the script itself. This is similar to key delegation we have introduced before, except that a script is delegated by signing, instead of a public key.

Compared with Taproot

During setup, all parties jointly sign all possible surrogate scripts. When spending, some party may be unwilling or unavailable to sign. In this case, Graftroot enjoys a few salient advantages over Taproot:

  1. It scales at O(1) rather than O(log n), where n is the total number of alternative scripts, each representing a way to spend. Regardless of n, a single signature is needed. While in Taproot, a Merkle proof of size O(log n) is needed when spending.
  2. New alternative script can be delegated after the fact in Graftroot, any time between setup and spending. This is impossible in Taproot since the MAST root is committed and cannot be modified after setup.

Graftroot in the Original Bitcoin

It turns out Graftroot can be achieved on Bitcoin, without any change to the original protocol.

The following diagram shows Taproot on Bitcoin between Alice and Bob. There are four alternative spending scripts (S₀, S₁, S₂, and S₃), which lie at the leaf nodes of the MAST with root m.

Figure 1: Taproot with 4 Alternative Spending Scripts
Figure 1: Taproot with 4 Alternative Spending Scripts

Instead of committing four scripts in a MAST in a single transaction tx2, each script can be made into a separate transaction. All transactions (i.e., tx2_0, tx2_1, tx2_2, and tx2_3) are signed and held off-chain by both parties after running the Nakamoto Signing Protocol. Both parties delegate a script by jointly signing the transaction containing it. For example, both signing tx2_0 makes S₀ a surrogate.

In the uncooperative case, one of these four transactions, containing the chosen script, can be broadcasted. At most one of them can be redeemed, since they all spend from the same UTXO in tx1.

Figure 2: Graftroot with 4 Alternative Spending Scripts

Comparing Figure 1 and Figure 2, it is obvious that spending from an alternative script, say S₀ in tx2_0, costs less, without the overhead of its Merkle proof.

More script can be delegated, as long as both parties agree. For instance, a new script S₄ can be added as a surrogate by both parties signing tx2_4 containing it.

Summary

Since Graftroot on Bitcoin does not require any consensus changes, unlike on BTC, it can be leveraged today for improved privacy and efficiency. For example, the signature used for delegation can be checked using existing opcode OP_CHECKSIG, while BTC requires new opcode such as OP_CHECKSIGFROMSTACK since the signed message is the script itself, not the transaction data.

Watch: CoinGeek New York panel, Bitcoin & Blockchain – Can Real Value Come from Real Utility?

New to Bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide to learn more about Bitcoin—as originally envisioned by Satoshi Nakamoto—and blockchain.

[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]
[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]