RFC: Compact UDT Lock

English CKB Development & Technical Discussion
1

RFC: Compact UDT Lock

Compact UDT lock leverages Sparse Merkle Tree to reduce storage requirements for user defined tokens on CKB. As a pure lock script, compact UDT lock is compatible with both sUDT and xUDT. One CKB cell using compact UDT lock can keep UDT balances for arbitrary number of users, while remaining constant in CKB requirements for the cell. To further optimize the transfer operations, open transaction style action is introduced, so multiple transfers can be packed together as a single CKB transaction.

Data Structure

Cell structure

For simplicity, we use compact UDT cell to refer to a cell that:

  • Uses compact UDT lock as the lock script
  • Uses either sUDT or xUDT script as the type script

Compact UDT lock uses different data layouts for sUDT and xUDT respectively. For sUDT, the cell structure looks like following:

data:
    <amount: uint128> <4 byte hardcoded data 0xFFFFFFFF> <SMT root hash>
type:
    code_hash: simple udt type script
    args: <owner lock script hash>
lock:
    <compact UDT lock script>

For xUDT, the cell structure looks like following

data:
    <amount: uint128> <xudt data>
type:
    code_hash: extensible udt type script
    args: <owner lock script hash> <xudt args>
lock:
    <compact UDT lock script>

Whereas xudt data contains the following data:

lock: <compact UDT lock data>
data: <xUDT extension specific data>

In both cases, compact UDT cell contains a SMT root hash. The SMT used here uses identity as keys, the value part for each key, is the combination of several items:

  • 16 byte amount associated with the particular identity
  • 4 byte nonce field
  • 12 byte reserved field set to all zeros for now. One potential use case, is we can expand this to a since field to represent time lock.

The sum of all amounts stored in non-zero key/value pairs of the SMT tree, should be equal to the UDT amount stored in the first 16 bytes of cell data in the compact UDT cell.

Compact UDT lock script structure

A compact UDT lock script has the following structure

code_hash: <compact UDT lock script code hash>
hash_type: <compact UDT lock script hash type>
args: <1 byte version> <32 byte type ID> <optional 21 byte identity field>

For now, the version field of compact UDT lock should always be set to zero.

Type ID field used in compact UDT cell should be generated per steps documented here.

A compact UDT lock script can also have an optional identity field. When present, one must provide a proper signature for the identity, in order to unlock the cell. When missing, anyone providing a proper transfer action can thus update values stored in the compact UDT cell.

Witness structure

Compact UDT cell expects a proper WitnessArgs as most CKB lock scripts in the first witness of its script group. The lock field of WitnessArgs, should contain a molecule serialized CompactUDTEntries data structure as defined below:

array Uint128 [byte; 16];
array Byte32 [byte: 32];
vector Bytes <byte>;

vector Signature <byte>;
array ScriptHash [byte: 32];
array Identity [byte: 21];

table Deposit {
  source: ScriptHash,
  target: Identity,
  amount: Uint128,
  fee:    Uint128
}

vector DepositVec <Deposit>;

table MoveBetweenCompactSMT {
  script_hash: ScriptHash,
  identity: Identity,
}

union TransferTarget {
  ScriptHash,
  Identity,
}

table RawTransfer {
  source: Identity,
  target: TransferTarget,
  amount: Uint128,
  fee:    Uint128,
}

table Transfer {
  raw: RawTransfer,
  signature: Signature,
}

vector TransferVec <Transfer>;

struct KVPair {
  k: Byte32,
  v: Byte32,
}

vector KVPairVec <KVPair>;

table CompactUDTEntries {
  deposits: DepositVec,
  transfers: TransferVec,
  kv_state: KVPairVec,
  kv_proof: Bytes,
}

A Deposit structure transfers UDTs from other cells into current compact SMT cell. A Transfer structure, depending on the value of TransferTarget, either moves tokens between identities in current compact SMT cell, or transfers UDTs from current compact SMT cell to other cells. In all cases, other cells only refer to UDT cells other than the current SMT cell in the enclosing transaction. No assumptions have been made on the specific format of those other cells, they could be ACP cells, cheque cells, or they can also be compact UDT cells.

Each signature in Transfer data structure signs on the ckbhash of a concatenation of the following items:

  • The type ID field of the current compact UDT cell
  • The nonce field of the source identity in current compact UDT cell
  • The raw field stored in the same Transfer structure as the signature

Notice the nonce field shall be updated after processing each Transfer structure. For example, the nonce for Aliceā€™s identity in a compact UDT cell is now 5, a transaction contains 2 Transfer entries using Aliceā€™s identity as the source field. The first entry shall use 5 as the nonce field when generating the signature, while the second entry shall use 6 as the nonce field when generating the signature.

Execution flow

When a compact UDT cell is updated in a CKB transaction, the compact UDT lock script performs the following checks:

  • It first loops through all other UDT cells in current transaction, gathers the UDT changes amongst all other cells in current transaction. Those changes act as the de-facto data for deposits and withdraws of the compact UDT cell.
    • For simplifying the implementation of compact UDT cell, we introduce a manual limit here: at most 2000 unique lock scripts can be used amongst all other UDT cells.
  • A SMT state is initialized based on values in kv_state. SMT proof validation is also performed here using kv_state and kv_proof against SMT root hash in input compact UDT cell for correctness check.
  • For each Deposit in CompactUDTEntries, the lock script checks against data gathered in other UDT cells, to ensure enough deposits are provided from the specified source(denoted via lock script hash of other UDT cells). It also updates SMT state to reflect the updates. Notice more than one deposit might come from the same source.
  • For each Transfer in CompactUDTEntries, the lock script either updates balances for source and target identities directly in the SMT state(for internal transfers), or update the balance for source identity in SMT state, then check against other UDT cells, ensuring correct withdraw has been performed. Notice more than one withdraw might be performed to the same target.
    • There is one special case here: in case a target is MoveBetweenCompactSMT type, we are moving tokens between compact SMT cells, in this case, current lock script should perform one extra step: it needs to check against witness field of the target compact SMT cell, ensuring a valid Deposit entry of using current compact SMT cell as source, and the identity in MoveBetweenCompactSMT as target. Otherwise there might be chance of manipulation when moving tokens between compact SMT cells.
    • There is also a hidden implication: with the exception of compact SMT lock script itself, the lock script used as targets in withdrawing requests, must represent the full identity of the recipient. ACP and cheque script are examples of scripts that satisfy this requirement, but compact SMT cell itself is not, since the actual identity is kept as key in SMT. Assuming there is a different lock script, which also keeps track of multiple usersā€™ balance in cell data part, compact SMT lock script has no way of knowing the details of this lock script, hence it can only ensure tokens are withdrawed to a cell using this particular lock script, but the actual token, can be deposited to any users managed by this seperate cell.
  • For each Deposit and Transfer request, a fee field might be present, the lock script should also ensure that enough fees have been deducted from the designated source field.
  • Finally, SMT proof validation is performed in the updated SMT state using kv_proof against SMT root hash in output compact UDT cell, ensuring the valid SMT root hash has been generated reflecting on states after performing all operations.

Examples

Depositing into a compact SMT cell

CellDeps:
    <...>
Inputs:
    <vec> Compact UDT Cell
        Data: <1000 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> UDT Cell
        Data: <2000 UDT>
        Type: <UDT Script 1>
        Lock: <lock 1>
    <...>
Outputs:
    <vec> Compact UDT Cell
        Data: <1200 UDT> <new SMT root hash>
        Type: <UDT script>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> UDT Cell
        Data: <1799 UDT>
        Type: <UDT Script 1>
        Lock: <lock 1>
    <...>
Witnesses:
    WitnessArgs structure:
      Lock:
        deposits:
            <vec> Deposit Entry
                source: lock 1
                target: Alice
                amount: 200 UDT
                fee: 1 UDT
        transfers: []
        kv_state:
            <vec> Alice's SMT Entry
                k: Alice
                v: 1000 UDT | nonce 5
        kv_proof: <valid proof>
      <...>

After this transaction, the updated SMT tree shall contain the following KV pairs:

  • Aliceā€™s SMT Entry
    • k: Alice
    • v: 1200 UDT | nonce 5

In other words, deposit request does not change nonce of targets.

Transferring within a compact SMT cell

CellDeps:
    <...>
Inputs:
    <vec> Compact UDT Cell
        Data: <1000 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <...>
Outputs:
    <vec> Compact UDT Cell
        Data: <1000 UDT> <new SMT root hash>
        Type: <UDT script>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <...>
Witnesses:
    WitnessArgs structure:
      Lock:
        deposits: []
        transfers:
            <vec> Transfer Entry
                source: Alice
                target: (Identity) Bob
                amount: 50 UDT
                fee: 1 UDT
                signature: Signature from Alice covering <type ID 1>, nonce 5 and the above fields.
        kv_state:
            <vec> Alice's SMT Entry
                k: Alice
                v: 200 UDT | nonce 5
            <vec> Bob's SMT Entry
                k: Bob
                v: 0 UDT | nonce 0
        kv_proof: <valid proof>
      <...>

After this transaction, the updated SMT tree shall contain the following KV pairs:

  • Aliceā€™s SMT Entry
    • k: Alice
    • v: 149 UDT | nonce 6
  • Bobā€™s SMT Entry
    • k: Bob
    • v: 50 UDT | nonce 0

Nonce field for targets in Transfer request is not changed as well.

This example is also a slight simplification. Alice also pays 1 UDT of fee, the SMT actually also contains a different entry which collects the fee paid.

Withdrawing from a compact SMT cell

CellDeps:
    <...>
Inputs:
    <vec> Compact UDT Cell
        Data: <1000 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> UDT Cell
        Data: <2000 UDT>
        Type: <UDT Script 1>
        Lock: <ACP lock 1>
    <...>
Outputs:
    <vec> Compact UDT Cell
        Data: <799 UDT> <new SMT root hash>
        Type: <UDT script>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> UDT Cell
        Data: <2200 UDT>
        Type: <UDT Script 1>
        Lock: <ACP lock 1>
    <...>
Witnesses:
    WitnessArgs structure:
      Lock:
        deposits: []
        transfers:
            <vec> Transfer Entry
                source: Alice
                target: (ScriptHash) ACP lock 1
                amount: 200 UDT
                fee: 1 UDT
                signature: Signature from Alice covering <type ID 1>, nonce 0 and the above fields.
        transfers: []
        kv_state:
            <vec> Alice's SMT Entry
                k: Alice
                v: 350 UDT | nonce 0
        kv_proof: <valid proof>
      <...>

After this transaction, the updated SMT tree shall contain the following KV pairs:

  • Aliceā€™s SMT Entry
    • k: Alice
    • v: 49 UDT | nonce 1

More complicated example

Letā€™s combine more operations in one transaction:

CellDeps:
    <...>
Inputs:
    <vec> Compact UDT Cell
        Data: <1000 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> Compact UDT Cell 2
        Data: <400 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 2>
    <...>
Outputs:
    <vec> Compact UDT Cell
        Data: <1100 UDT> <new SMT root hash>
        Type: <UDT script>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 1>
    <vec> Compact UDT Cell 2
        Data: <300 UDT> <old SMT root hash>
        Type: <UDT script 1>
        Lock:
            code_hash: Compact UDT Lock
            args: <version: 0x0> <type ID 2>
    <...>
Witnesses:
    WitnessArgs structure for compact UDT cell 1:
      Lock:
        deposits: []
        transfers:
            <vec> Transfer Entry
                source: Alice
                target: (Identity) Bob
                amount: 50 UDT
                fee: 0 UDT
                signature: Signature from Alice covering <type ID 1>, nonce 5 and the above fields.
            <vec> Transfer Entry
                source: Alice
                target: (MoveBetweenCompactSMT)
                    Compact UDT Cell 2's lock script hash
                    Charlie as identity
                amount: 100 UDT
                fee: 0 UDT
                signature: Signature from Alice covering <type ID 1>, nonce 6 and the above fields.
        kv_state:
            <vec> Alice's SMT Entry
                k: Alice
                v: 400 UDT | nonce 5
            <vec> Bob's SMT Entry
                k: Bob
                v: 10 UDT | nonce 1
        kv_proof: <valid proof>
      <...>
    WitnessArgs structure for compact UDT cell 2:
      Lock:
        deposits:
            <vec> Deposit Entry
                source: Compact UDT Cell 1's lock script hash
                target: Charlie
                amount: 100 UDT
                fee: 0 UDT
        transfers:
            <vec> Transfer Entry
                source: Charlie
                target: (Identity) Alice
                amount: 20 UDT
                fee: 0 UDT
                signature: Signature from Charlie covering <type ID 2>, nonce 0 and the above fields.
        kv_state:
            <vec> Charlie's SMT Entry
                k: Charlie
                v: 0 UDT | nonce 0
            <vec> Alice's SMT Entry
                k: Alice
                v: 5 UDT | nonce 4
        kv_proof: <valid proof>
      <...>

After this transaction, the updated SMT tree in compact SMT cell shall contain the following KV pairs:

  • Aliceā€™s SMT Entry
    • k: Alice
    • v: 250 UDT | nonce 7
  • Bobā€™s SMT Entry
    • k: Bob
    • v: 60 UDT | nonce 1

Te updated SMT tree in compact SMT cell 2 shall contain the following KV pairs:

  • Charlieā€™s SMT Entry
    • k: Charlie
    • v: 80 UDT | nonce 1
  • Aliceā€™s SMT Entry
    • k: Alice
    • v: 25 UDT | nonce 4

Acknowledgement

Many have contributed in the completion of this spec, including my fellow colleagues at Cryptape, Frank Lou at lay2 as well as many who have read the initial idea. Huge thanks to everyone, this spec wonā€™t be complete without all the contributions from the warm Nervos community.

7 Likes