CashTokens & PMv3: fixed-size inductive proofs, transaction integer compatibility

Thanks for the clarifications!

Are there any other public forums with good technical discussion on Group Tokens? I’d love to have more background if it’s available anywhere.

Anyway, I’ve implemented it in the nextchain experimental testnet […]

Ah, nice. (Code here.)


So in summary, maybe the best comparison is:

Group Tokenization (prev. OP_GROUP) vs. CashTokens

Group Tokenization aims to be an all-inclusive framework for BCH token support – it’s much like Ethereum’s ERC20, except Group Tokens would be built directly into the BCH consensus protocol, including “groups”, “authorities”, “capabilities”, “subgroups”, etc.

CashTokens are “userland” protocols: they are completely implemented using the VM bytecode language. Like any contract, new ideas (for e.g. minting, redeeming, and token management) can be designed and deployed by anyone, whenever they want. The only prerequisite for people to get started building CashToken-style covenants is the ability to succinctly introspect parent transactions (e.g. a solution like hashed witnesses).

(discussion from CashToken Devs)


And again, I don’t think these are mutually exclusive upgrades: inductive proofs are needed for several covenant applications which aren’t likely to be covered by a built-in token protocol (e.g. weighted, blinded voting for two-way-bridged prediction markets). There are also definitely applications which could be optimized beyond inductive proofs – a future upgrade which lets us “group” and save token balances in with the UTXO set could save a lot of bytes per transaction.

1 Like

“it’s much like Ethereum’s ERC20

I wouldn’t put it that way. As I’m sure you know (but just setting the stage) Ethereum is basically a replicated computer with shared state. Things like tokens are built on top of that computer. Something like CashTokens uses that same architecture since the logic that creates tokens into the BCH scripting language.

This is a very fundamental architectural decision. Its much more fundamental IMHO than saying that Group Tokenization is like ERC20 because they both support feature X. In fact, that’s not even accurate. ERC20 just supports transfer – its up to each contract to layer on all the other features that Ethereum has taught us that we need.

The ramifications of this architectural decision influence EVERYTHING downstream. There are advantages and disadvantages.

Disadvantages of implementing tokens in the blockchain script:

  1. Safety: every token can be implemented differently so really before holding a token every person should review that code (which may be closed source).
  2. Scalability (CPU): no matter how much more efficient the blockchain scripting language gets, its unlikely to exceed the efficiency of native code. Additionally, the native code can leverage miner consensus and therefore “do” a lot less – in this case just a simple sum and compare of token inputs and outputs.
  3. Scalability (Space): the scripts that implement and enforce token constraints will take up space in transactions. Admittedly this space is very compressible using the macro scripting architecture that I laid out a few years ago but still it cannot be smaller than no script…

Advantages of implementing tokens in the blockchain script:

  1. Flexibility: There’s just the one, but its a big one!

So let’s talk product philosophy, because excepting BTC with its 1st mover advantages, blockchains are effectively products competing for users. Here’s a key product design idea:

If you can’t be better in all respects than an established competitor, then at least be different.

Why? Because your differences will mean that you are better at some things (while being worse at others). Ideally of course, you want to be better at MORE things then you are worse at. But even if you are worse at more things, your different product can find applications that specifically need what you are better at.

This is the philosophy I think we should use with Bitcoin Cash. Verses Bitcoin, we’ve made it worse on low end machines/internet connections to make it better at handling large volumes of transactions. Verses Ethereum, we shouldn’t make it a (worse) general purpose computer (and no, we are never going to slowly build BCH script into something that can out perform the ETH VM which is IIRC going to leverage web assembly). Instead, lets make it really good at handling crypto-financial computing. The way to do this is to have powerful primitives for that task. This is why I want super-efficient native tokens, rather than implementing them at the scripting layer. This is why I want OP_PUSH_TX_DATA (transaction introspection) rather than using the inefficient CDS “trick”. This is why nextchain.cash implements variable sized big nums rather than picking 256bits (say). Ethereum defines uint256… my big num implementation will be (perhaps – its using libgmp where very clever people are focused on performance and writing asm implementations for common architectures) very slightly less efficient at 256 bit numbers but more efficient at every other size.

1 Like

I’m still behind on reviewing the inductive proofs and other details from Jason, but I do like the discussion Andrew started.

What I specifically appreciate in Bitcoin is its scaling proposition. Validating a transction and/or script is very easy to shard over multiple processors, all parts are easy to parallelize. The only thing that we can’t parallelize is the UTXO. We need some locking in order to make sure we can detect a double spend within a signle block.

Based on the fact that the UTXO is the scaling bottleneck, I’m indeed happy with the general design in Jasons stuff: it doesn’t add anything to the UTXO.

The OP_GROUP and maybe the GROUP one too (I mirror Jasons request for some forum or documentation on it) have as a rather severe problem that they add a second 32-byte identifyer to every UTXO entry. As the current lookup is just a single 32-byte entry (and maybe a output-index), this is a rather large difference that will have an instant and negative effect on scaling.

1 Like

Related discussion about how inductive proof strategies can allow covenants to offload functionality to child covenants, allowing public covenants to be parallelized. This reduces competition over who gets to make the next covenant transaction (avoiding competing chains of unconfirmed covenant transactions):

It’s possible that BCH could ultimately support both parent transaction introspection (for complex covenant applications) and a built-in “group” token system (for stablecoins and other common token applications). There doesn’t seem to be a good thread on this forum about native token support, so I responded to @andrewstone’s comment here:

1 Like

The OP_GROUP and maybe the GROUP one too (I mirror Jasons request for some forum or documentation on it) have as a rather severe problem that they add a second 32-byte identifyer to every UTXO entry. As the current lookup is just a single 32-byte entry (and maybe a output-index), this is a rather large difference that will have an instant and negative effect on scaling.

Neither OP_GROUP nor GROUP modified a single line of the UTXO code and did not add an additional lookup. There is never a reason to look up a UTXO via group id. A UTXO that happens to contain tokens is the same 32 byte tx id + output index lookup.

It has been well documented, implemented, and even ported to and deployed on the ION cryptocurrency. Technical discussion with the BCH community happened years ago, so I don’t have ancient links handy, and was, frankly, not actually technical due to ABC’s terrible attitude towards cooperative-yet-also-competing clients.

1 Like

Responded to @andrewstone here: Native Group Tokenization - #3 by bitjson

1 Like

Another summary of this proposal derived from telegram discussions:

Bitcoin cash covenants already support introspection/validation of outputs, enforcing rules for future transactions.

PMv3 allows us to do validation looking backwards, inspecting elements of a covenant’s parent transaction and enforcing rules for parent transactions.

Support for both forward and backward validation unlocks a huge number of contract use cases: a lot of complex applications happening on “global state” chains like Ethereum can be implemented more scalably on BCH, with no other changes to the VM. (Details: Hashed Witnesses: Build Decentralized Applications on Bitcoin Cash)

Personally I prefer small incremental steps. Much easier to roll out and debug. As such it is important to notice that indeed they strenghthen each other, but they don’t depend on each other. They can be in two individual upgrades if that is the way it turns out.

Personally I prefer small incremental steps.

Strongly agree. Minimal changes, one at a time. :+1: :+1:

They can be in two individual upgrades

Sorry, I wasn’t clear – there’s only one upgrade we still need. The forward validation part is already working on mainnet. (E.g. CashChannels)

This PMv3 proposal focuses only on the minimum upgrade to support backward validation: “compression” of past proofs + script integer compatibility. With these two elements, we can succinctly introspect parent inputs in the same way we can currently introspect future outputs.

The other “features” of PMv3 (reduced TX size and an upgrade path to fractional satoshis) are just helpful byproducts of these two minimum changes.

So I strongly agree. There’s a chance people will want to pack in other changes too, so I tried to describe here why I think we should keep PMv3 minimal: CashTokens & PMv3: fixed-size inductive proofs, transaction integer compatibility - #2 by bitjson

After some more discussion on Telegram, I think it might be helpful for me to copy/paste some of the “most interesting” parts of the CashToken Demo here for start-to-end viewing (and mobile readers).

If you’re on a modern desktop browser, you can also jump right into the CashTokens template on Bitauth IDE:

CashTokens template screenshot

CashTokens Template Summary

This template provides scripts for each stage of a simplified "depository"
CashToken Corporation, where users may deposit 10,000 satoshis in exchange 
for a CashToken. This implementation supports exactly 4 homogeneous tokens. 
Tokens are tracked in a 2 level Merkle tree:
     rt
    /  \
   b0   b1
  / \   / \
 a0 a1 a2 a3

The covenant begins with no depositors (all leaves start as the hash of 0) and a
dust balance. A user deposits 10,000 satoshis, receiving a CashToken (recorded
at a0) secured by a single key. Then the CashToken is "notarized" to prove it is
a descendant of the mint transaction. Once notarized, the owner transfers the
CashToken to a 2-of-3 multisig for stronger security. From there, the owner
transfers the token to a different owner (now single sig). Finally, the new owner
redeems the CashToken with the corporation, withdrawing their 10,000 satoshi
deposit, and replacing a0 in the tree with the hash of 0 (making the leaf available
to other depositors).

There are 5 transaction types demonstrated:
- tx0: Incorporation TX - the "corporation" is established with a dust balance
- tx1: Token Mint TX - a CashToken is created
- tx2: Notarization TX - the CashToken is proven to be valid
- tx3: Token Transfer TX - the CashToken is transferred independently
- tx4: Token Redeem TX - the CashToken is redeemed with the "corporation"

Transaction Graph/Timeline:

tx0 --- tx1 -------------------------------------- tx4
           \--- tx2 --- tx3 --- tx3 --- ...tx3 ---/

Transaction Contents:

tx0: Incorporation TX - 
  Input 0 - any funding output (dust amount + tx fee)
  ---
  Output 0 - Corporation Covenant (dust amount)
  Output 1 - change output

tx1: Token Mint TX -
  Input 0 - tx0 output 0
  Input 1 - any funding output (10,000 satoshi deposit + tx fee)
  ---
  Output 0 - Corporation Covenant
  Output 1 - CashToken Covenant (Token ID is tx0 hash)
  Output 2 - change output

[Token circulates separately from the corporation covenant]

  tx2: Notarization TX
    Input 0 - tx1 output 1
    Input 1 - any funding output (tx fee)
    ---
    Output 0 - CashToken covenant
    Output 1 - change output

  tx3: Token Transfer TX
    Input 0 - tx2 output 0
    Input 1 - any funding output (tx fee)
    ---
    Output 0 - CashToken covenant
    Output 1 - a change output

[Token is redeemed with the corporation covenant]

tx4: Token Redeem TX
  Input 0 - tx1 output 0
  Input 1 - tx3 output 0
  Input 2 - any funding output (for fees)
  ---
  Output 0 - Corporation covenant
  Output 1 - a change output (+10,000 satoshi withdrawal)

---

Additional Notes

Indestructible Dust – Once created, this CashToken corporation
implementation cannot be destroyed. The covenant could be modified
to allow the final dust balance to be collected from the covenant if all
shares are unallocated, but the additional bytecode required over the
life of the covenant is likely to be more costly than the dust amount "saved"
when the covenant is abandoned. It's worth noting that any bitcoin user
can create an unlimited number of dust outputs at any time, so dust from
covenants is irrelevant from the perspective of the network.

Token Mint (Unlocks the Corporation Covenant)

/**
 * To mint a token we must prove:
 * - TX output 0 is the next covenant state where:
 *   - the new tree replaces an empty leaf (<0>) with the covenant outpoint TX hash
 *     - requires: new tree root, all opposite nodes, proof path
 *   - the new covenant UTXO has a value of 10,000 satoshis greater than before
 * - TX output 1 is the expected token pattern
 *   - requires: m-of-n and public keys to use for the token
 * 
 *     rt
 *    /  \
 *   b0   b1
 *  / \   / \
 * a0 a1 a2 a3
 * 
 * This example verifies that a0 is `0`, then replaces
 * it with the outpoint TX hash.
 */

<root_hash_after_mint> // rt
<sibling_tier_2_hash> // b1
<sibling_leaf_hash> // a1

<1> // tier 2 is left side (requires swap)
<1> // leaf is left side (requires swap)

<1> // enter branch: Mint Token

Corporation Covenant

<empty_root_hash> OP_TOALTSTACK 

OP_IF
/**
 * branch: Mint Token
 */

/**
 * we need 2 copies of the "validation path": 
 * 1. confirm the leaf was empty
 * 2. confirm the new root only changes that leaf
 */
OP_2DUP
OP_FROMALTSTACK OP_ROT OP_ROT // current_root_hash
OP_TOALTSTACK OP_TOALTSTACK

// First we confirm the leaf being updated was empty:
<4> OP_PICK // sibling_tier_2_hash
<4> OP_PICK // sibling_leaf_hash
<0> OP_HASH160 // constant: hash160 of <0>

OP_FROMALTSTACK // check if leaf requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH160

OP_FROMALTSTACK // check if tier 2 requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH160 // should be current root

OP_EQUALVERIFY // verified that replaced leaf was <0>

// Now we confirm that the new leaf uses outpoint TX hash

OP_TOALTSTACK OP_TOALTSTACK

OP_OUTPOINTTXHASH
OP_HASH160

OP_FROMALTSTACK // check if leaf requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH160

OP_FROMALTSTACK // check if tier 2 requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH160 // verified new root

OP_DUP OP_TOALTSTACK // save for later use
OP_EQUALVERIFY // new root is correct


// require that output 0 is 10_000 satoshis larger than last value
OP_UTXOVALUE
<10_000> OP_ADD
<0> OP_OUTPUTVALUE
OP_EQUALVERIFY // covenant has been paid properly

// require that the correct covenant script is used
<OP_PUSHBYTES_20>
OP_FROMALTSTACK // root_hash_after_mint
OP_UTXOBYTECODE // get this covenant's bytecode
/**
 * OP_SPLIT is often unsafe for user input, but this input
 * comes from the VM/previous contract.
 */
<21> OP_SPLIT OP_NIP // trim off previous root hash push
OP_CAT OP_CAT
OP_HASH160
<OP_EQUAL> <OP_HASH160> <OP_PUSHBYTES_20> OP_2SWAP
OP_CAT OP_CAT OP_CAT
// require that output 0 is the new covenant bytecode
<0> OP_OUTPUTBYTECODE
OP_EQUALVERIFY // TX pays to the updated covenant

// require that output 1 is a cashtoken UTXO
<1> OP_OUTPUTBYTECODE
<0xaabbccddee> // TODO: push expected cashtoken bytecode
/**
 * We get the Token ID from the last covenant TX ID. This: 
 * 1) prevents tokens from being created to impersonate existing tokens
 * 2) saves bytecode space (vs. pushing an ID)
 * 3) avoid bugs in wallet implementations (validating at contract-level)
 */
// TODO: use <0> OP_OUTPOINTTXHASH to get the Token ID, concat into CashToken covenant
OP_EQUAL
OP_ELSE
/**
 * branch: Redeem Token
 * TODO: leaving out of first draft, see notes in unlocking script
 */
OP_ENDIF

Notarization (Unlocks Token Covenant)

/**
 * This is the initial "Notarization" spend. It can only 
 * be successful if the parent (mint) transaction includes 
 * the outpoint TX hash referenced by the CashToken
 * covenant (in its 0th output). 
 * 
 * To prove that this notarization step has been
 * completed successfully, future spends need only 
 * prove that the covenant has previously been
 * successfully spent.
 * 
 * This implementation does not offer a way to transfer
 * the token to a new set of holders during the notarization
 * step. Rather, the notarization transaction must lock funds
 * in a covenant with the same signing requirements as those
 * specified in the mint transaction. This is a feature:
 * notarization can be safely performed by anyone, making
 * CashTokens slightly easier to implement in some types of
 * wallets (and reducing the size of the covenant by saving
 * on validation bytecode).
 */

<example_tx1> // TODO: switch to `<parent_mint_tx>`, fix scenario generation error (using `example_tx1` for `bytecode.parent_mint_tx`)

<0> <0>

Token Transfer (Also Unlocks Token Covenant)

/**
 * This script is use to transfer a notarized CashToken between
 * wallets. This implementation supports multisig wallets of
 * up to 3 keys.
 * 
 * Counterintuitively, the token transfer branch of this contract
 * does not place any limitations on the outputs to which a token
 * is spent. Instead, only its parent and grandparent transactions
 * are validated to ensure the tokens lineage. However, because
 * this covenant is impossible to spend without the proper
 * "proof-of-lineage", if any transfer does not properly continue
 * the covenant, the token is burned.
 * 
 * This means it is always possible to "burn" the token in one final
 * transaction – in this authentication template, the token should
 * be burned/redeemed back into the parent corporation covenant
 * (which itself then validates that the token's lineage was
 * unbroken). With this strategy, the parent covenant can validate
 * the authenticity of tokens.
 */

[...]

Token Covenant

/**
 * This script is the key to the inductive proof. It's 
 * designed to be unspendable unless:
 * 1. Its parent was the mint transaction funded by the transaction
 *    hash claimed (requires full parent transaction), or
 * 2. It was previously spent successfully – the parent's 0th input's
 *    UTXO used this covenant, i.e. the parent's 0th-input-parent's
 *    0th output uses this covenant. (Valiated by checking the full
 *    parent and grandparent transactions.)
 * 
 * With these limitations, if a user can move the CashToken,
 * we know the CashToken has the lineage it claims.
 */

/**
 * By "baking-in" the code branch selection, we prevent the
 * CashToken from being unecessarily notarized multiple times.
 */
<is_notarized>

// mint parent hash: the outpoint TX hash in the 0th output of the mint transaction
<tx0_hash> 

OP_TOALTSTACK // tx0_hash
OP_TOALTSTACK // is_notarized

<1> // threshold (m)

// push n public keys (up to 3)
// TODO: convert to variable
<first_holder_key.public_key>

<1> // count (n)

/**
 * Though this is only checked by the transfer branch,
 * it drops all ownership-related items from the stack
 * more efficiently than can be done with manual dropping
 * operations.
 * 
 * Note, notarizations could be restricted to token owners by
 * replacing this with OP_CHECKMULTISIGVERIFY.
 */
OP_CHECKMULTISIG

// in both branches, verify the full parent transaction is provided
OP_DUP
OP_HASH256
OP_OUTPOINTTXHASH

OP_DROP OP_DROP // debug: switch comment to skip check
// OP_EQUALVERIFY // verfied provided transaction is parent

OP_FROMALTSTACK // is_notarized
OP_NOTIF
    /**
     * Notarization branch:
     * Prove that this transaction's parent is the claimed token mint transaction,
     * i.e. its 0th input spends from the claimed token ID (outpoint TX hash).
     * 
     * Note, this branch can be executed by any interested observer (doesn't 
     * require access to any private keys), so it must be carefully validated
     * to avoid griefing.
     */

    OP_DROP // drop failed multisig check

    <4> OP_SPLIT OP_NIP // remove and discard tx version
    <1> OP_SPLIT OP_SWAP // get first byte of tx input count
    /**
     * Between 0 and 127, Script Numbers and VarInts are compatible.
     * 
     * 127 (`0xfc`) is the largest integer which can be represented
     * by the Script Number format in a single byte (0x80 begins 
     * the range negative 0 through 127).
     */
    <2> OP_EQUALVERIFY // require exactly 2 inputs (covenant + fee funding)

    <32> OP_SPLIT OP_DROP // get 0th outpoint tx hash, drop everything else
    OP_FROMALTSTACK // tx0_hash
    OP_EQUALVERIFY // Token ID verified: parent transaction spends from claimed outpoint tx hash

    /**
     * Verify the transaction's 0th output is re-assigned
     * the updated covenant.
     */
    OP_UTXOVALUE
    <0> OP_OUTPUTVALUE
    OP_EQUALVERIFY // require output value to be the same
    <OP_HASH160 OP_PUSHBYTES_20>
    <OP_1> OP_UTXOBYTECODE
    <1> OP_SPLIT OP_NIP OP_CAT // remove is_notarized of OP_0, replace with OP_1
    OP_HASH160 <OP_EQUAL>
    OP_CAT OP_CAT // expected P2SH bytecode
    <0> OP_OUTPUTBYTECODE
    OP_EQUAL // 0th output bytecode is correct
    /**
     * TODO: further optimization: after notarization, can we prune the
     * notarization branch?
     * Requires other changes to validation in both convenants.
     */

OP_ELSE
    /**
     * Transfer branch:
     * Prove that the outpoint tx spends from this same covenant. Then
     * prove that this transaction is signed by the required private key(s).
     * 
     * Note: to save space, this branch doesn't validate the locking bytecode
     * to which the transaction pays, making it possible for wallets to burn
     * the CashToken (intentionally or due to a bug). This is unlikely to
     * be a problem in practice because CashTokens can only be moved by
     * wallets which support the CashToken covenant template (no
     * backwards-compatibility with wallet which might unintentionally
     * burn tokens).
     * 
     * By not forward-validating outputs, we elliminate the need for each
     * CashToken covenant to be capable of correctly "identifying" its 
     * parent covenant during redeem transactions. (Instead, we verify the
     * lineage of the token by checking its parent and grandparent.)
     */

    OP_VERIFY // Signature validation must have been successful

    // Owner has authorized transfer, now prove lineage:

    // get parent tx's outpoint tx hash, then verify we have the grandparent
    <4> OP_SPLIT OP_NIP // remove and discard tx version (no validation)
    <1> OP_SPLIT OP_SWAP // get first byte of tx input count
    <0x02> OP_EQUALVERIFY // require exactly 2 inputs
    <32> OP_SPLIT // get parent outpoint tx hash
    <4> OP_SPLIT OP_DROP // get parent outpoint index, drop everything else
    OP_BIN2NUM
    <0> OP_EQUALVERIFY // must be grandparent's 0th output (grandparent may be 1th for mint)
    OP_TOALTSTACK // parent outpoint tx hash

    // validate and concat grandparent back together, confirming it used this covenant
    <
      0x02000000 // always require version 2
      0x02 // always require exactly 2 inputs
    >

    OP_SWAP // top is grandparent input 0 outpoint (hash + index)
    OP_SIZE <36> OP_EQUALVERIFY // require grandparent input 0 outpoint to be 36 bytes
    OP_CAT

    OP_SWAP // top is grandparent input 0 bytecode
    OP_SIZE 
    OP_DUP
    <4> OP_ROLL OP_EQUALVERIFY // provided bytecode is expected size
    OP_NUM2VARINT // serialize length
    OP_SWAP
    OP_CAT
    OP_CAT // grandparent TX up to input 1

    
    OP_SWAP // top is grandparent input 1 outpoint (hash + index)
    OP_SIZE <36> OP_EQUALVERIFY // require grandparent input 1 outpoint to be 36 bytes
    OP_CAT

    OP_SWAP // top is grandparent input 1 bytecode
    OP_SIZE
    OP_DUP
    <4> OP_ROLL OP_EQUALVERIFY // provided bytecode is expected size
    OP_NUM2VARINT // serialize length
    OP_SWAP
    OP_CAT
    OP_CAT // grandparent TX through inputs
    
    // start building grandparent outputs

    OP_SWAP // top is grandparent is_notarized
    <0> OP_EQUAL
    OP_IF
      /**
       * Grandparent is not notarized (mint transaction), the 1th output is the covenant.
       */
      <3> OP_CAT // require exatly 3 outputs in mint transaction
      OP_SWAP // top is 0th output satoshi value
      OP_SIZE <8> OP_EQUALVERIFY // satoshi value must be 8 bytes
      OP_CAT
      <$(<23> OP_NUM2VARINT)> // length of corporate covenant bytecode (P2SH)
      OP_CAT
      OP_SWAP
      OP_SIZE <23> OP_EQUALVERIFY // corporate covenant bytecode must be P2SH length
      OP_CAT
      // end of 0th output
    OP_ELSE
      /**
       * Grandparent is notarized, the 0th output is the covenant.
       */
      <0x02> OP_CAT // require exactly 2 outputs in transfer transactions
    OP_ENDIF

    OP_SWAP // top is grandparent's cashtoken covenant value
    OP_DUP
    /**
     * To support heterogenous tokens, this covenant prevents the
     * satoshi value of the token from changing during transfers.
     * 
     * However, we can't simply verify the "next" satoshi value is the
     * same as the "current" value - eventually, the token will be
     * redeemed with the corporation covenant, and the covenant's 
     * expected balance at that time can't necesssarily be predicted.
     * 
     * Instead, we only verify backwards by comparing the token output
     * values of the grandparent and current transaction. With this
     * limitation, we can know the token's value can't be modified
     * until the redeem transaction, where the parent covenant can
     * read the value before it is destroyed.
     */
    OP_UTXOVALUE <8> OP_NUM2BIN
    OP_EQUALVERIFY // disallow token value from being modified
    OP_CAT

    < <23> OP_HASH160 > OP_CAT // length of cashtoken covenant bytecode (P2SH)

    // begin transforming parent bytecode into grandparent bytecode for validation

    <OP_0> // is_notarized for mint transactions
    OP_UTXOBYTECODE // get parent bytecode
    <1> OP_SPLIT OP_NIP OP_CAT // replace is_notarized with OP_0
    
    <36> OP_SPLIT // preserve token ID (OP_0 + OP_PUSHBYTES_32 + 32 bytes + OP_TOALTSTACK + OP_TOALTSTACK)
    
    <1> OP_SPLIT OP_NIP // remove parent threshold pushing opcode (<<m>>)
    <3> OP_ROLL // add grandparent_threshold pushing opcode
    OP_SWAP // top is parent bytecode after removed m push

    <4> OP_ROLL // get parent public key count opcode

    // TODO: PRs welcome – are there more efficient ways to implement this "case" statement?
    // check for parent n of 1, 2, or 3 (saving the opcode)
    OP_TUCK 
    <<1>> OP_EQUAL OP_IF
      <34> OP_SPLIT
      OP_ELSE
      OP_OVER <<2>> OP_EQUAL OP_IF
        <$(<34> <34> OP_ADD)> OP_SPLIT
      OP_ELSE
        OP_OVER <<3>> OP_EQUAL OP_IF
          <$(<34> <34> <34> OP_ADD OP_ADD)> OP_SPLIT
        OP_ELSE
          OP_RETURN // fail, parent must match a planned n
        OP_ENDIF
      OP_ENDIF
    OP_ENDIF
    /**
     * TODO: SECURITY: do we need to validate these bytes? (E.g. in the
     * corporation covenant, they must be validated.) Can a malicious
     * grandparent transaction use different opcodes in these bytes to
     * defraud future token holders?
     */
    OP_NIP // drop the removed parent public key pushes
    OP_NIP // drop the parent public key count opcode
    <1> OP_SPLIT OP_NIP // drop parent n opcode from bytecode

    <4> OP_ROLL // pick grandparent public key count opcode
    // TODO: PRs welcome – there are definitely more efficient ways to implement this one
    OP_DUP
    <<1>> OP_EQUAL OP_IF
      <OP_PUSHBYTES_33> <6> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY
      OP_CAT
      OP_ELSE
      OP_DUP <<2>> OP_EQUAL OP_IF
        <OP_PUSHBYTES_33> <6> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY
        OP_CAT
        <OP_PUSHBYTES_33> <7> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY 
        OP_CAT OP_CAT
      OP_ELSE
        OP_DUP <<3>> OP_EQUAL OP_IF
          <OP_PUSHBYTES_33> <6> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY
          OP_CAT
          <OP_PUSHBYTES_33> <7> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY
          OP_CAT OP_CAT
          <OP_PUSHBYTES_33> <7> OP_ROLL OP_SIZE <33> OP_EQUALVERIFY
          OP_CAT OP_CAT
        OP_ELSE
          OP_RETURN // fail, grandparent must match a planned n
        OP_ENDIF
      OP_ENDIF
    OP_ENDIF
    OP_SWAP OP_CAT // concat grandparent n opcode after public key pushes

    OP_SWAP
    OP_CAT OP_CAT OP_CAT // reconstructed grandparent redeem bytecode
    OP_HASH160 // get redeem script hash
    OP_CAT
    <OP_EQUAL> OP_CAT

    OP_SWAP // top is remaining TX serialization

    // no need to verify remaining grandparent outputs

    OP_CAT // full grandparent transaction
    OP_HASH256 // grandparent transaction hash
    OP_FROMALTSTACK // outpoint tx hash from parent

    OP_DROP OP_DROP <1> // debug: switch comment to skip check
    // OP_EQUAL // verify grandparent is parent outpoint tx

    // (don't bother dropping the mint parent hash left on altstack)

OP_ENDIF

Again, these are just the most important parts.

As you can see, I’ve made comments documenting many design decisions and noting various security and usability concerns. You can read a more thorough intro on the CashToken Demo Gist.

If you’re on a supported browser, you can also jump right into the CashTokens template on Bitauth IDE to experiment with the full evaluation traces.


PMv3’s “hashed witnesses” allow scripts like the above Token Covenant to “compress” their parent transaction’s witness data (by hashing it), avoiding the uncontrolled growth in transaction sizes which currently prevents covenants from introspecting parent transactions. The second change proposed by PMv3 allows scripts to parse the integer format used in these parent transactions by making them compatible with the existing Script Number format. (Which also happens to save ~5% in transaction sizes.)

1 Like

Hashed Witnesses vs. MalFix, SIGHASH_NOINPUT, SegWit, etc.

The hashed witnesses half of this proposal could also be solved by any transaction malleability solution which removes witness data from the parent transaction’s outpoint transaction hash.

If there was any demand for a full transaction malleability solution, we might want to consider implementing that instead of hashed witnesses.

I personally don’t see the need for an additional “malleability fix”, so I prefer the hashed witnesses solution:

  • hashed witnesses avoid creating two different TXID formats (e.g. TXID and WTXID) – this keeps the system as simple as possible, ensuring the competing ID formats never confuse user experiences, and ensuring consistency between e.g. the TXID in SPV proofs and the TXID referenced in contracts.
  • hashed witnesses avoid the need for an additional TXID index – nodes don’t need to maintain an index to match the two TXID formats (with and without witness data) even at the P2P layer.
  • hashed witnesses don’t affect block merkle root construction or any system components other than v3 transactions (depending on the solution – malleability fixes can be more disruptive)

Unless someone can point out advantages in implementing a malleability solution instead, I prefer that this problem be solved with the hashed witnesses solution. I started a thread to collect discussion if anyone is interested:

Hashed Witnesses vs. TXID Merkle Trees

Just to document another possible alternative to hashed witnesses: a new transaction version could also use a new merkle tree construction for its TXID.

Instead of hashing the full, serialized transaction, each major component of the transaction could be hashed, allowing child transactions to only introspect e.g. a particular output during a proof. (So in a sense, this would be hashed witnesses + hashed everything else, in a tree.)

While this may save a few bytes for contracts which introspect a parent transaction, it would require significantly more hashing per transaction. And even for a relatively small type of tree, e.g. hash256([version][input merkle tree][output merkle tree][locktime]), the small additional savings would probably not be worth it. (Proofs would still require 32 bytes * node count; a minimal 330 byte proof could maybe be reduced to ~128 bytes, but at the cost of requiring possibly 10x as much hashing when computing TXIDs.)

I think hashed witnesses are a much better choice, only costing one additional hash for any inputs which use them (and users pay for the extra bytes, discouraging unnecessary use).

For users just seeing this thread: I’m hoping to get other commonly asked questions documented in an FAQ soon. I’m happy to answer any questions here or in the new CashToken Devs Telegram group.

Group is essentially having a new kind of cash bill with a 546 sats BCH anti-fraud strip attached to each bill (UTXO) which can later be reclaimed if the token becomes useless, even without melt authority - by consolidating all your tokens into one UTXO and reclaiming the anti-fraud strips from all other inputs. Since I realized this simple truth, I’m having trouble sleeping, I feel the need to write, to make noise, to let everyone know. Writing this had me up all night. Maybe you will cringe at me “selling” it like that, but I just want everyone to reach the “aha!” moment with this. We all need to want this. Maybe you will feel annoyed that I’m making noise. Well, that’s a small price to pay for what we could be getting. The missed opportunity cost of not having it due to ABC has already been huge. We could have owned USDT market.

It’s really a small protocol change. The consensus rules are simple and conceptually easy. Using those rules in a meaningful way from a wallet dev. perspective could be seen as large but they don’t have to support everything. Basic token transactions are as simple as any BCH transaction, it only needs to have the OP_GROUP quantity balance in addition to the BCH balance. Token mint/melt/authorize is as simple as including an extra UTXO in the inputs, which affects the balancing rule. Authority is just another balance to check. Token genesis is as simple as creating a single UTXO.

Building blocks are simple, that’s what Group is. What you build with them may or may not need to be complicated, but the blocks themselves aren’t complicated, they couldn’t be any simpler.

They aren’t, and that’s the great news! Since every Group UTXO is also a BCH UTXO you can do with those whatever you want from any smart contract platform we may roll out. I just disagree on the priorities when it comes to deployment. Ok, I’m a nobody, but please hear me out.

Group should come first, as soon as possible, and as a minimum viable (but future proof) product: mint/melt/baton/maybe subgroup because people also need time to work on wallet software once it’s out. We have time, but we have to work together. Have group first, and think about how you could use them from whatever smart contract platform you want ie work with the assumption that you will have Group tokens to use. That way we can get the synergy!

Everybody already has smart contracts that look like cash, nobody has actual hard cash that smart contracts can use, yet.

Cash is not just one currency.

Having them available before any smart contract platform will mean that anyone wanting tokens will prefer it for simple token usage, for which there’s lots of demand as we have seen. And later when you roll out smart contracts, you should be operate on those tokens exactly the same like you operate on BCH. Only exotic tokens should require being implemented by the contract. For a simple token, miner doesn’t need you to tell them that 1+1=2, they ought to know that already, and check for that in C++, the same place where they check the BCH “contract”.

Everyone is thinking in smart contracts, so they can’t see the simple truth: smart contracts need smartly designed electronic cash system. That’s what Group is.

@bitcoincashautist would you mind moving this comment to the Group Tokens topic? It would be valuable to keep that discussion in one place.

I don’t need further convincing: token support is valuable. :+1: I think that adding built-in support to the protocol could eventually make certain constructions slightly more efficient.

My concern remains that committing to a large protocol expansion like Group Tokens is a one-way change, and getting it correct in “one shot” is much less likely than if we allow the ecosystem to first experiment with tokens in “userland” before we lock ourselves to one particular token standard. I wrote more detail in that topic – if you’re interested, I would appreciate answers there.

For this topic:

Have you gotten to review CashTokens & PMv3 yet? Please don’t let the script stuff scare you, there’s no complex math: the “parent introspection” is just checking that two hashes are equal, and the “inductive proof” is just checking that two scripts are equal.

If contracts can efficiently inspect the contents of their parent transactions, wallet developers can design all kinds of new contracts without waiting for “permission” or BCH protocol changes – including token implementations like CashTokens.

2 Likes

Not only that, it would also require all parties that now can just hash a bytearray to introspect and understand the transaction.

Thanks for getting back on this and explaining a bit more about this on the dev-chat yesterday.

As we talked about here I’ll write my thoughts on the topic of the var ints.

Here the arguments for changing the transaction formats parts which encode numbers:

  • The current transaction format has 3 different ways to encode integers. You name 4 as you include the one inside of the script as well.
    The idea to replace all with one is attractive from a purely architectural point of view.
  • Bitcoin Script has severe problems with the var-width encoding when doing covenants.
  • Variable-width encoding gains in tx size are a couple of percent.
  • Variable width means that the ‘amount’ field can grow beyond the 64-bit limit it has today.
    Caveat is that the 21 million limit we have today only takes 6½ bytes. We could multiply it with 8196 without needing more bytes.

So, really the main reason you suggested this is because Bitcoin Script doesn’t understand one of the 3 used integer formats. The var-int. And your suggestion is for the rest of the transaction to use the integer encoding that the scritping VM already is familiar with.

So, I have a counter suggestion. Two actually.

Use a more common encoding scheme.

My thinking here is that interpreting transactions, at least at the basic level, is going to be something that a LOT of software libraries will do. On the other hand the amount of places that implement a VM will be much lower. Probably only the full nodes and some specialized software.

Based on this, I vastly prefer to solve your basic problem of Bitcoin Script not understanding the format by introducing two opcodes. One for each of the conversion directions and picking a format that is actually much more standardized. See Variable-width encoding - Wikipedia. Think UTF-8 as an example of this.

Now, if you are going to break 100% of all transaction parsing code-bases, I think it makes a lot of sense to include a little upgrade that makes future transaction format changes much easier. This is based on reseach I did some years ago in the project called “Flextrans”.

The basic idea is that each field becomes a “name / format / value” type. This allows inserting new data in the transaction at a later version without forcing everyone to AGAIN rewrite the entire transaction parsing. Just like adding a new html tag to the standard doesn’t require you to update the old parsers.

This thinking got me to suggestion two:

Use the current size-formats.

So, we can go fancy and require everyone to rewrite the format, while also requiring two new opcodes to do the conversion between tx-numbers and script-vm-numbers.
But, hang on. If you need those opcodes anyway, then why would we change the numbering format?

I liked (and still do) the FlexTrans approach. But the gains are small and the change intrusive.

I’d vastly prefer to not have a different numbering format and simply add two opcodes for the conversion.

2 Likes

In my deep dive into the protocol the disparity between the screams for restricting transaction sizes or growth of data and then how so many single digit numbers are expressed across multiple bytes has always confused me a bit. :slight_smile:

Your example of UTF-8’s encoding model is a good one. The Smalltalk community had something called State Replication Protocol (SRP) which was a way of streaming objects and entire networks of objects across different dialects of SmallTalk and even completely disparate hardware environments.

Similar to UTF-8, the high bit of a byte (octet as they called it - the single primitive in SRP) determines whether or not the value you’re dealing with continues on to the next octet or finishes there. Ultimately you get 7 bits of data for every octet. Any value under 128 is represented in a single byte. There’s also no limit to how large a number you can represent and no endian considerations to confuse.

Were I to make a new VM for a cryptoledger to execute on, I’d make SRP the native representation of all data. It naturally compresses the size of most data by eliminating wasteful fixed sizes above 8 bits. A type like this in BCH could be really helpful in eliminating wasteful padded bytes.

Thank you @tom for the detailed review! And thanks @proteusguy for digging into the spec too! I want to continue with some more research on the encoding options before I make changes to the spec and/or respond to specific points. (I’m going to be mostly offline from March 5-15, but I’m hoping to focus on this again at the end of March. Also posted in CashTokens Devs.)

For anyone interested in a high-level summary of this topic, I recently spoke with @GeorgeDonnelly about hashed witnesses, PMv3, CashTokens, prediction markets, synthetic assets, decentralized exchanges, BCH scaling considerations, comparisons with ETH, and more:

2 Likes