Proposal to allow free UTXO creation in Qtum

So there is one big thing that is annoying about UTXOs. Namely, that in order to do anything you first need your very own UTXO. They're easy to get, and come in any size you want above 0... but you can't make them out of thin air if you don't already own one. Getting one involves you being friendly either with a staker who can create you one for free in the coinstake transaction, or having someone else pay the network fees and be willing to give you a few satoshi.

The way contracts figure out who sent the message (and authenticate it) is to check "ok, did this person spend a UTXO in this transaction" (even if they merely spent it and sent all the funds back to themselves). This sounds a bit wasteful, but the worse problem is that without a UTXO it's impossible to authenticate that you're sending a message to the contract. Even if someone else pays the fees and everything else for you, you still need a UTXO to really do anything with most contracts. This issue commonly comes up in other cases as well. Your wallet has multiple addresses and each address has it's own set of UTXOs. The blockchain is incapable of knowing that those addresses belong to the same wallet. So, what happens when you choose to send QRC20 tokens to some certain address, but then find out that address has no UTXOs. You will be incapable of spending the QRC20 tokens, since you have no way of proving to the contract that you are that certain address. The official workaround for this problem is to simply send that certain address any amount of coins (even 1 satoshi) so that it has a UTXO, and then you can withdraw your QRC20 tokens or whatever. Later, Qtum Core will (by default) make sure to use change addresses to ensure that address always has a UTXO.

This is wasteful of precious UTXO set space, but most of all it's incredibly annoying. Our Dapps have complained about it, their users, our users, myself. It's a problem... and it makes it harder to use a lot of different and otherwise awesome use cases unique to the UTXO model in Qtum.

My (definetely not 100% proven and thought out) proposal is to extend Bitcoin's fundamentals to support an otherwise boring edge case. In Bitcoin (and Qtum right now), in order to even prove a signature or anything like that on the blockchain, you must give a TXID and a Vout number, indicating which UTXO you will be spending, then you provide a signature that basically makes the UTXO's "vout script" evaluate to true. There's other cool stuff about this, but for the case we're interested in, it involves checking the signature of the public key in the UTXO for the hash of all inputs and outputs of the transaction. So, what if we gave another way of looking up that public key to check the signature of?

My proposal: Allow a TXID and Vout of 0 to be permissable and assumed to have 0 value, but otherwise to be infinitely spendable. To prevent duplicate transactions potentially being valid, all complete transactions must consist of at least one actual vin with a TXID that's not 0. It would probably be very ill-advised to use SIGHASH_ANYONECANPAY, as inputs created with this method could be used in any transaction without restriction (ie, duplicated). This gives no threat to the blockchain, but could be a huge security hole for users with no practical use. Thus, SIGHASH_ANYONECANPAY will most likely be prohibited when using this functionality. To be safest, it would probably be a requirement to only allow the SIGHASH_ALL (default) signature scheme. Otherwise, anyone with early knowledge of the transaction (such as nodes/stakers) could potentially rewrite the transaction to include another output that executes a contract and drains ERC20 balances or whatever.

No new opcodes need to be introduced and in theory this has no ill effect on Bitcoin or Qtum blockchains at this moment if allowed. Qtum would make use of this functionality though by extending the Account Abstraction Layer so that it can run these vin scripts that would otherwise be useless. It could check for pattern matching so that P2SH or PUBKEYHASH scripts could be identified and classified as an address, along with being run as a normal script to verify signatures of course. Thus, it would be possible to take an address never used on the blockchain, construct a vin that uses and verifies that address, but points to no UTXO. In theory this could be used for many purposes. You could use P2SH/Multisig addresses without UTXOs, send messages from contracts (pending attack vector verification), and even use it with Segwit addresses.

The pattern matching would probably be the most difficult part and might actually require an additional opcode for simplicity. The opcode could be something like OP_VOUTBEGINSHERE or whatever and actually do nothing other than be a marker for pattern matching.

Practical Usecase

A user wants to use a Dapp but has never used Qtum before. In order to begin using the Dapp, they must register an account on the blockchain. The Dapp maintainer has an off-chain registration portal to allow for someone to register on the Dapp for free. This works by the Dapp maintainer paying for the gas fees of on-chain registration.

This is possible today (though has not been used by anyone yet), but with a caveat. The new user must have a UTXO to prove their identity and complete the registration.. they don't actually need any money, but the only way to prove ownership of a certain address is by spending a UTXO. With this proposal, it'd be possible for the user to create a UTXO from nothing using only their public/private key.

The actual workflow is that the user would register off-chain or whatever to basically prove that they are worthy of the Dapp site paying for their gas fees (remember spam is still possible and must be handled somehow). The user would then provide their address to the Dapp site. The Dapp site would then send the user a partially completed transaction composing of the following:

  • Input: Created user address utxo from txid 0. This is unsigned at this point. This the first input so that the user address will be the msg.sender to contract code
  • Input: Dapp UTXO that pays for keys; This is signed and marked SIGHASH_ALL
  • Output: Dapp contract execution that does the registration process on-chain etc. The amount of gas given is chosen by the Dapp and is measured to be the correct amount.
  • Output: Change address to send remaining funds back to the Dapp UTXO address

The user would receive this transaction and validate that it is as expected. They would check that the Dapp contract output only does registration. They would also ensure that no additional outputs are added to the transaction other than the change address UTXO (and they would check that to ensure there is not a hidden contract execution).

Once the user is satisfied and has determined the transaction is secure, the user will sign the first input and use the SIGHASH_ALL signature scheme to ensure nothing can be added or removed to the transaction. The user then broadcasts the transaction to the blockchain (or hands it to the Dapp site to broadcast if they aren't running a node).

Once the transaction is executed and confirmed, the address of the user will be registered with the Dapp on-chain, even though this address has never actually received any Qtum coins or had any other activity to "establish" the address.

Many identity based Dapps in the ecosystem right now struggle with this problem. Users might pay with Bitcoin or a credit card or some other off-chain method of payment for the Dapp to register them, but if the Dapp sends them Qtum (or ETH, whatever) to the address as a stipend for registering on-chain there is no method of actually enforcing that. In addition, the Dapp could get in serious legal trouble since exchanging fiat to cryptocurrency in most countries has a lot of legal regulation like money transmission licenses etc. With this method, gas and transaction fees can easily be paid by the Dapp in an enforced way. The user can't just run off with that stipend and choose to cash it out, or spend it on a different contract execution. Thus it is (btw, IANAL, don't take this as legal advice) probably safe legally to take fiat and use it to pay for the fees of a specific on-chain transaction.

Another simpler use case is for an ERC20 token provider to provide the gas fees for sending tokens to an address. If we're working in a world where people might not own Qtum, but do use the Dapps on the Qtum blockchain, then there needs to be systems for using Dapps without actually owning any Qtum to pay for your own transaction fees. This proposal is just the first step in making this a practical reality. There are various workarounds in Qtum and Ethereum to solve this problem, but they are clunky and definitely not ideal.

Posted: 10/18/2018 7:33:05 PM

What is a UTXO, and how does it work for a blockchain ledger?

Today I'd like to introduce the basics of how a blockchain works, and how it keeps track of money in a secure manner. I will be covering the UTXO model, as it is used by Bitcoin and Qtum. There is another way of managing funds on the blockchain called the account model, but it will not be covered here.

First I'd like to give some definitions in case you do not know anything about Bitcoin.

  • One-way hash (or just "hash") - A cryptographic algorithm which converts an arbtritrary amount of data into a fixed-length "digest". The algorithm does this in a way that given just the digest it is impossible to determine what the input data was, and furthermore it is impossible to predict what the digest is from the given input data. The most common example is SHA256 which is used extensively in Bitcoin, but there are many others including SHA3, RIPEMD160, scrypt, and many others.
  • Public key cryptography - A cryptographic mechanism by which a "private" secret key can be converted into a "public" key and used to prove ownership of the private key without giving away the secret. Additionally it is possible to encrypt data using the public key so that only the person holding the private key can decrypt it. In Bitcoin this is commonly used to sign transactions. It is possible to prove that the creator of the transaction owns the secret private key by using only the signature data and the public key.
  • Merkle root - A tree data structure that uses one-way hashing to hold multiple pieces of data making it so that any data in the input of the tree can not be modified without changing the final value of the merkle root hash.
  • UTXO - Unspent Transaction Output, an unspent vout from a transaction
  • Block - The smallest verifiable and unforgeable unit on the blockchain. It contains various data to prove it's consensus as well as transactions

So, let's talk about how transactions work in this. Transactions in Bitcoin resemble a cashier's check in some ways. When you want to spend an "output" of a transaction you must spend the entire thing. It's similar to how you can't walk into the bank and say "I want to cash half of this check". However, in this model there is no equivalent of cash or bank accounts. So in order to send money anywhere you must "cash" a check written out to you, and "output" from that cashing process a check to your intended destination, and another check back to yourself.

This "cashing process" is actually a transaction in Bitcoin. In a transaction you spend 1 or more "checks" (actually known as UTXOs) and create 1 or more UTXOs to new destinations from those spent funds. The UTXOs you spend in a transaction are called "vins", and the new UTXOs you create are called "vouts". Once a UTXO is spent by a transaction it can be considered gone and destroyed. You can see it's history in the blockchain, but there is nothing that can done with it.

So, one problem in our system so far is that checks are normally written out to names, such as "Jordan Earls". Anyone of course can say they are any name on the internet. This is where we introduce public key cryptography and programming into UTXOs. In Bitcoin UTXOs contain a script, or a computer program, which are only spendable if you can make that script end by saying "True". Let's look at the most simple script possible that does something useful:

[pubKey] OP_CHECKSIG

This is referred to as a "pay-to-pubkey" script. It was the first standard Bitcoin transaction type. The first item is [pubKey]. This is the data for a public key. Remember that for each public key there is a private key which is kept secret by it's owner. It is safe to publish the public key, but not the private key. The Bitcoin "Script" language is stack based. So imagine you have a stack of papers. You write the public key on a piece of paper and then place it on the stack. The next piece of this script is OP_CHECKSIG. This specific operation will take 2 things off of the top of the stack. The first thing it takes off is the public key. Then, the second thing it takes off is the cryptographic signature.

This is confusing now though. OP_CHECKSIG takes 2 values from the stack (also known as arguments), but our script appears to only have 1 value, pubKey. This is where the vin portion becomes important. You can imagine the vout script as the "pay to" field on a check, and the vin script as the place you sign on the back, proving that you are indeed the intended party from the "pay to" field. In Bitcoin, a script is not executed until it is spent. And when it is spent, it first executes the vin script, and then places the resulting data from the vin stack on to the vout stack. So in actual execution, the script might look rather like:

[signature from vin] [pubKey] OP_CHECKSIG

One could consider the vout script as a challenge, and the vin as the answer to give the vout to satisfy it. Anyway, now that we have a vin providing the signature and attempting to spend these funds, we can actually execute the script. If the signature and public key is valid, then OP_CHECKSIG will push "true" on the stack, resulting in the UTXO being succesfully spent.

So in a transaction, each vin specifies a previous UTXO, and provides an answer that causes the UTXO's script to return "true". If an invalid signature or similar is used, then the scripts will return "false" and the transaction will not be valid. It is not possible to partially spend a UTXO. It must be completely spent or left untouched. This means that if you have a UTXO worth 10 tokens, and you want to send 7 tokens to Bob, then you must make a transaction that spends this 10 token UTXO, and creates 2 outputs. One output to Bob (using his public key), and one output back to yourself (ensuring that you can provide an "answer" to the vout to spend it successfully). This second output back to yourself is called a "change address".

Finally, we have a reasonable way of exchanging tokens using transactions and scripts. However, we face a problem. When someone sends you a transaction output, how can you be sure that their vins for that transaction only use unspent outputs. This is where the concept of the blockchain becomes important.

A block in Bitcoin has a header. The header contains the following:

  • Version
  • Previous block header hash
  • Merkle root hash of all transactions in the block
  • Time of creation
  • Difficulty
  • Nonce

The body of the block is complete transactions (and eventually witnesses as well, but that's another topic).

Because each block includes a reference to the previous block, it is impossible to modify a previous block sereptitiously. To modify a previous block would change the block hash, and thus break the "chain" made of block hashes.

Bitcoin uses the Proof of Work (PoW) consensus system. This will be explained more in a later article, but basically it is a system which requires participants (miners) in the block creation process to put in a certain amount of computational work to solve a difficult puzzle. The first miner to solve the puzzle gets a reward and their created block is added to the network's blockchain. How much work must be done is controlled by the "difficulty" specified in the block.

In PoW, only the block header is actually used for the consensus mechanism. The merkle root hash ensures that despite this, it is possible to validate every transaction in the body of the block, as well as ensure that every transaction has been received.

Once a block has been created, it's transactions can be mostly considered permanent. The only way to "double spend" a UTXO is to replace the block in which the spending transaction took place. This can happen naturally in some cases (known as orphan blocks), but as more blocks are built on top of the transaction containing block, the likelyhood of this becomes exponentially less likely, and furthermore, would require exponentially more work to maliciously attack and replace.

This is why many services that accept Bitcoin wait for 3 or 6 confirmations (blocks placed on top of the transaction containing block). It becomes incredibly unlikely that the blockchain could be broken and those funds spent by another transaction.

We have only one remaining problem. Where do the tokens initially come from? They come from the mining process. As part of mining, the miner adds a special transaction called a "coinbase" transaction. This transaction has no inputs, and is allowed to have outputs worth a set amount (currently 12 in Bitcoin). This coinbase transaction is where all of the tokens in circulation actually come from. Without tokens there would be no transactions to create, and thus nothing to be done.

Now we have a functioning blockchain that is capable of holding it's value securely, ensuring that double spends are extremely difficult to execute (and increasing in difficulty with more confirmations). You should now know enough to understand how Bitcoin, Qtum, and other UTXO cryptocurrencies really work at the protocol level and can begin to look into more advanced topics on the blockchain.

References:

  1. https://en.bitcoin.it/wiki/Script#Obsolete_pay-to-pubkey_transaction
Posted: 7/27/2017 6:20:44 PM