From Bitcoin to CKB

In Part I of Enable Bitcoin Taproot on CKB, we’ve learned the basics of Schnorr Signature and the Merkle Tree, two major components of Bitcoin's Taproot technology. Our next step is to see how to apply Taproot without softfork but only through smart contract on CKB, the layer 1 blockchain of the Nervos Network. We’ll examine the lock script, witness and the two unlocking methods that CKB Taproot offers: the key path spending and the script path spending (where CKB Taproot’s power lies!). I’ve also prepared a Taproot demo so you can run and test it out!

The design of CKB Taproot is straightforward. Two code paths are involved: one is directly using Schnorr Signature and the other is using the scripts hidden in the Merkle Tree. These two paths are known as key path spending and script path spending respectively. They are mutually exclusive, meaning only one can be chosen during execution. For key path spending, we adopt Bitcoin's secp256k1 library, while for script path spending, Sparse Merkle Tree (SMT), a Merkle Tree variant built from scratch by the CKB team. SMT is different from MAST, another variant of Merkle Tree used in Bitcoin Taproot.

Authentication

Before diving into the Taproot lock script, let’s have a quick recap on the concept of Authentication (auth). It was first proposed in the design of another lock script called Omnilock. CKB Taproot lock uses the same auth concept as Omnilock. It is an identity with a 21-byte long data structure containing the following components:

<1 byte flag> <20 bytes auth content>

Depending on the value of the flag, authentication can take on different interpretations. Possible interpretations are listed in my previous post. A new auth flags value (0x6) is allocated for the Taproot lock. The auth content is the blake160 hash of taproot output key. A taproot output key is a 32-byte array that represents a Schnorr public key according to BIP340.

Taproot Lock Script

Lock script controls access and ownership of a CKB cell. Cell is the smallest unit where the transaction data is stored. Lock script determines who has permission to use the cell.

CKB Taproot lock script has the following structure:

Code hash: Taproot lock script code hash
Hash type: Taproot lock script hash type
Args: <21 byte Auth>

Taproot Witness

When unlocking a Taproot lock, the corresponding witness must be a proper WitnessArgs data structure in molecule serialization format. In the lock field of the WitnessArgs, a TaprootLockWitnessLock data structure must be present as follows:

import blockchain;

table TaprootScriptPath {
    taproot_output_key: Byte32,
    taproot_internal_key: Byte32,
    smt_root: Byte32,
    smt_proof: Bytes,
    y_parity: byte,
    exec_script: Script,
    args2: Bytes,
}

option TaprootScriptPathOpt (TaprootScriptPath);

table TaprootLockWitnessLock {
    signature: BytesOpt,
    script_path: TaprootScriptPathOpt,
}

Here the SMT in smt_root and smt_proof fields refers to an optimized compacted Sparse Merkle Tree. Sparse Merkle Tree can compress a large key-value map into short bytes represented by the Merkle root, and generate existence or non-existence proof for keys in the tree. In addition to the advantages of SMT, the optimized version SMT in CKB Taproot has the following features:

• No pre-calculated hash set
• Efficient existence/non-existence proof
• Efficient storage space

When the signature is present, it must follow the following data structure:

<pubkey, 32 bytes> <signature, 64 bytes>

The details of pubkey and signature are described in BIP340. The pubkey in BIP 340 is identical to the "Taproot output key" in BIP341.

The script_path and signature can neither be simultaneously present nor absent: One and only one can be chosen. The fields of script_path will be described in the following sections.

As its major feature, Taproot provides 2 unlock methods: key path spending and script path spending. They are almost identical to the Script validation rules in BIP341, except for some data structures.

Tagged Hash

Tagged hash refers to the hash value tweaked with a context-dependent tag name, to ensure that the hash used in one specific context can't be arbitrarily reused in any other case.

In BIP340, the tagged hash is defined as:

tagged_hash(tag, x) = SHA256(SHA256(tag) || SHA256(tag) || x)

In CKB Taproot, we define it as:

ckb_tagged_hash(tag, x) = blake2b(tag || x)

CKB adopts blake2b as the default hash algorithm “ckbhash” and uses it in two unlock methods, key path spending and script path spending. The tag in CKB taproot share the same string in BIP341 which is “TapTweak”.

Key Path Spending

Key path spending is the default unlocking method, like a regular Bitcoin spend. It unlocks the output by providing an empty input script and a Schnorr Signature of the corresponding private key in the witness program.

When signature is not none, while script_path is: the key path spending is used. It uses Schnorr Signature to unlock the cell. The auth content in script args is the blake160 hash of Taproot output key in signature.

Figure 4. Key Path Spending-The Traditional Way of Unlocking

Because Schnorr Signature has not been standardized yet, at the moment we follow the improvements proposed in BIP340, including:

• Signature encoding: a simple fixed 64-byte format, replacing the DER-encoding which is variable in size, and up to 72 bytes)
• Public key encoding: encoded in 32 bytes, replacing the compressed 33-byte encodings of elliptic curve points which are common in Bitcoin
• Implicit Y coordinates: to support efficient verification and batch verification
• Final scheme: using public key pk which is the X coordinate of a point P on the curve whose Y coordinate is even and signatures (r, s) where r is the X coordinate of a point R whose Y coordinate is even. The signature satisfies s⋅G = R + tagged_hash (r || pk || m)⋅P

Script Path Spending

The other way to unlock is through script path spending. Let me introduce an example to illustrate the user scenario.

Alice is the owner of her private key. Taproot allows her to keep backups of the private key. Suppose she creates Key B and gives it to her friend Bob, and Key C, to another friend Charlie.

Now Alice wants to set up a contract like this in her Taproot lock: key path spending, or the traditional approach, allows Alice to spend her money whenever she pleases with her private key. But if she cannot sign herself for some reason, Bob and Charlie, the owners of the backup keys, can unlock Alice’s money through script path spending. Whether Bob and Charlie sign a multisig transaction after 1 year, or one of them signs alone after 2 years, either way can spend Alice's money.

Thus, script path spending allows alternative spending conditions. Those conditions are hashed together in a Merkle Tree, which forms the script path. Script path spending uses one of the leaves by satisfying one of the scripts in the tree.

When signature is null and script_path is not: the script path spending is executed. We use some Python codes to demonstrate when necessary. The referenced functions in Python demo can be found in bip340 reference.py.

• A tweaked key is calculated from taproot_internal_key and smt_root. A calculated y_parity is also returned.

def taproot_tweak_pubkey(pubkey: bytes, h: bytes) -> Tuple[int, bytes]:
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    # bip-0341: If t ≥ (order of secp256k1), fail.
    if t >= SECP256K1_ORDER:
        raise ValueError
    # bip-0341: Let p = c[1:33] and let P = lift_x(int(p)) 
    # where lift_x and [:] are defined as in BIP340.
    # Fail if this point is not on the curve.
    P = lift_x(pubkey)
    if P is None:
        raise ValueError        
    # bip-0341: Let Q = P + int(t)G.
    Q = point_add(P, point_mul(G, t))
    return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q))
(returned_y_parity, returned_tweaked_key) = taproot_tweak_pubkey(taproot_internal_key, smt_root)

• If the returned tweaked key is not the same as taproot_output_key, the unlocking fails.
• If the returned y_parity is not the same as y_parity, the unlocking fails.
• SMT verification: The SMT proof scenarios are inherited from Omnilock. When SMT verification is used, the SMT node key (32 bytes) is the blake2b hash of the molecule serialized of exec_script. The SMT node value can be any fixed value. An array of data [1, 0, 0, ...] is used. The smt_root and smt_proof are also passed as arguments. If the smt_verify return a failed status, the unlocking fails.
• Call exec syscall with arguments of code_hash, hash_type, and args in exec_script.

The syscall is described in Nervos RFC0034, a new syscall included in the first CKB Hardfork (note the new syscall is not required for Taproot on CKB, it makes the implementation simpler). The exec syscall is inspired by linux exec system calls. The exec syscall in CKB replaces the current executing script with a new script. The wrapped C version of exec syscall is shown as follows:

int ckb_exec_cell(const uint8_t* code_hash, uint8_t hash_type, uint32_t offset,
                  uint32_t length, int argc, const char* argv[]);

The args in exec_script is converted to hex format and then used as argv[0] in syscall. For example, an array of four bytes:

[1,2,15,16]

This array is converted to string: "01020F10". If the length of args is zero, then argv[0] is NULL. The same rule is applied to args2 in TaprootScriptPath: which is used as argv[1].

• The return code of exec is the final result of the unlocking process.

Figure 5. Alternative Ways of Spending Through Script Path Spending

To solidify our understanding of CKB Taproot, here are the code examples of the two unlocking methods.

Unlock Via Key Path Spending

CellDeps:
    <vec> Taproot Script Cell
Inputs:
    <vec> Cell
        Data: <...>
        Type: <...>
        Lock:
            code_hash: Taproot Lock
            args: <flag: 0x6> <taproot output key 1 hash>
    <...>
Outputs:
    <vec> Any cell
Witnesses:
    WitnessArgs structure:
      Lock:
        signature: <taproot output key 1> <valid Schnorr Signature for taproot output key 1>
        script_path:  <EMPTY>
      <...>

Unlock Via Script Path Spending

CellDeps:
    <vec> Taproot Script Cell
    <vec> Exec Script Cell
Inputs:
    <vec> Cell
        Data: <...>
        Type: <...>
        Lock:
            code_hash: Taproot Lock
            args: <flag: 0x6> <taproot output key 1 hash>
    <...>
Outputs:
    <vec> Any cell
Witnesses:
    WitnessArgs structure:
      Lock:
        signature: <EMPTY>
        script_path:
            taproot_output_key: <taproot output key 1>
            taproot_internal_key: <taproot internal key>
            smt_root: <SMT root>
            smt_proof: <SMT proof>
            y_parity: <parity of Y which belongs to a point P on the curve whose X coordinate is taproot output key 1>
            exec_script:
                code_hash: <code hash of exec script>
                hash_type: <hash type of exec script>
                args: <exec arguments>
      <...>

Taproot Demo: Transactions on Testnet

Let’s suppose Alice wants to send some coins to Bob without knowing whether Bob will or can accept them. If not, Alice can still take her coins back.

With CKB Taproot, this transaction is processed as follows:

1. Alice receives Bob's Schnorr public key
2. Alice transfers some CKBs to the cell locked by Taproot lock script whose lock script args is a hash of Taproot output key. Alice also embeds Bob’s Schnorr public key into Taproot output key. You can see the details on CKB Explorer.
3. If Bob doesn’t accept the coins for several weeks, Alice can reclaim the money by Taproot output secret key by key path spending; If Bob accepts the coins, it is done by script path spending. Transaction details in real world can be found on CKB Explorer Link 1and CKB Explorer Link 2, respectively.

To deploy smart contracts on the testnet, you need this SDK as the framework. For more information about CKB Taproot deployment, please visit this GitHub page. Please note that this demo is primarily intended for you to try out. The final release of CKB Taproot might differ slightly from this version.

This demo wraps up our 2-part tour of CKB Taproot. I invite you to continue exploring on your own. The full implementation of CKB Taproot can be found at this pull request on GitHub. Feel free to leave comments to help us improve!

✍🏻 Witten by: Jiandong Xu

---

By the same author:

• Enable Bitcoin Taproot on CKB (Part I)
• Omnilock, a Universal Lock that Powers Interoperability
• RVV (RISC-V V Extension): Key to the Efficient On-Chain Cryptography

---

You might be also interested in:

• How CKB Turns User Defined Cryptos Into First-Class Assets
• Blockchain Projects at Top Security Conferences
• Transparent SNARKs from DARK Compilers