Blockchain UTXO Model is a Dead End for General Purpose Applications

in #blockchain8 years ago

Bitcoin was the first cryptocurrency to introduce the UTXO (Unspent Transaction Output) model for tracking database state. Every Bitcoin transaction consumes (spends) outputs from prior transactions and produces new outputs to be consumed by future transactions. Each output can only be consumed once. This structure has many very nice mathematical properties, including structurally proving that the same tokens can never be spent twice provided every transaction proves that the sum of its inputs is greater than the sum of its outputs.

Today many of the thought leaders at organizations such as R3, Blockstream, BOSCoin, and Qtum continue to advance the notion of the UTXO model. In some cases, they are pitching it superior to other approaches and their entire business is focused around this model. The main reason UTXO is presented as superior is because it has natural parallelism as every transaction can be processed in parallel because they all refer to independent / non-conflicting outputs. From a theoretical computer science perspective, UTXO is elegant and easy to prove. In the real world however, things are very different.

Limited Application of UTXO

The UTXO model is only suitable for applications where each output is owned by exactly one individual. This fits the currency model perfectly and is why it works with Bitcoin. However, if there ever exists an output that could potentially be consumed by two or more people at the same time, then the entire process breaks down.

A prime example would be an exchange limit order. In the UTXO world this would be represented by an output that could be claimed provided the claimer paid the prior owner the price they demanded. If there was no competition over this output then everything works perfectly; however, as soon as two people wish to claim the output at the same time problems occur.

Alice and Bob both construct a transaction to consume the order, a few seconds later Bob finds out that Alice’s transaction won and his failed. So Bob attempts to construct a new transaction to take the next available order. Unfortunately, this also fails because someone else claimed it first. Bob is forced to loop in a tight script that will produce and sign transactions until one of them succeeds. This problem is made more complicated on blockchains where short-term chain reorganizations are common (proof of work).

This problem is amplified even further if one wishes to construct an exchange that enforces the requirement that orders are filled from highest to lowest on a first come, first serve basis. Instead of the order book being represented as a hundreds of individual outputs, it becomes one giant output that contains the entire state of the order book. All transactions take the current order book as their input and produce a new order book as their output. Rather than Alice and Bob fighting over a single output, you have every market participant fighting over it.

From an information theory perspective, this pure functional approach to the order book is extremely elegant, but once you consider the cost of duplicating and verifying the content, broadcasting it over and over, and lock contention it is clear that an elegant mathematical model is not enough.

Simplest Possible Example

Imagine a smart contract that implements a counter that can be incremented by anyone. Imagine that there is some economic incentive to be increment the counter before as many people as possible and that there are 1000 people actively attempting to increment this counter as soon and as frequently as possible.

The UTXO model would represent this as an output with a single number that can be claimed provided the transaction produces a new output with that same number incremented by 1. How fast could the counter increment?

If we assume a 3 second block interval, then it would increment once every 3 seconds. If we assume that people speculative build on pending UTXO then it would increment once every 250ms (global latency for peers around the world). Of course, allowing people to build off of unconfirmed UTXO would create a combinatorial explosion as everyone attempts to build off of every pending UTXO until a block producer finally picks some and rejects others.

To prevent network spam, peers would be forced to block transactions that build off of too many speculative transaction chains.

UTXO forces a Synchronization Point

The UTXO model forces exactly one person to grab a lock on the output, perform some transformation, and produce a new output. In computer science this pattern is known as Compare and Swap and it is normally used in tight loops to synchronize parallel access to data.

The difference between a CPU level compare-and-swap, and a UTXO level compare-and-swap is in how long the operation takes. A UTXO is limited by network latency and two peers on opposite sides of the globe would be lucky to achieve 5 successful operations per second. It is well known that heavy contention on a CPU compare and swap can cause multi-threaded performance to be far slower than a single-threaded alternative. This property applies even more so to UTXO.

UTXO forces State into Transactions

Every transaction explicitly includes its new output state. This state includes everything that must be modified in an atomic manner. If the UTXO were an exchange order book, then the state would be the entire order book. What works for Bitcoin currency (a short script and a balance), doesn’t work for anything that is even slightly more complex or that refers to more data.

Lets consider the counter again, only this time lets assume that the counter is attached to a 1 MB databuffer whose value changes deterministically every time the counter changes. Now the network and blockchain end up processing 1MB of data per transaction. This is exactly what would happen if exchanges, social media content, and other applications were implemented as a UTXO.

UTXO forces unnatural Designs

Because of these drawbacks, people who build applications based upon UTXO are forced to limit the amount of state impacted by each output. This means exchanges without rules on the order in which things are filled. This means anything that is the result of aggregating input from multiple parties is likely not viable.

Alternative Message Based Approach

Steem and Bitshares adopt a message based approach. In this case, the blockchain represents a consensus over the order of messages and the state is deterministically derived from these messages.

To implement a counter, each user would simply sign a message requesting to increment the counter by 1. The message would not need to know the current state of the counter in order to be a valid message. This means that 1000 people could submit the request at the same time and that the block producer could aggregate all requests into a block and 3 seconds later the counter will have gone from 0 to 1000.

Conclusion

What we can conclude from this article is that any blockchain that is building on a UTXO model is inherently limiting their applications to those involving a single owner per output. Any multi-owner output would be restricted by latency due to the speed of light to just a couple transactions per second. What works great for a currency like Bitcoin, does not work at all for general purpose applications.

Sort:  

I'm glad to know you've changed your mind about posting here. Do you have plans to remove your witness votes or will you continue to monitor the community and exert influence there?

As for this:

Steem and Bitshares adopt a message based approach. In this case, the blockchain represents a consensus over the order of messages and the state is deterministically derived from these messages.

I've been diving into BitShares / Open Ledger the last few days and learning more about how things work. Pretty amazing stuff, and I'm looking forward to learning more. I'm curious how BitShares will hold up against the Ethereum community which seems to have a lot of attention right now. From your perspective, are these projects similar in scope and if so, why should someone develop on BitShares over Ethereum?

The simple answer?

Graphene doesnt really have this problem...

Ethereum is not using UTXO model.. that's another issue.

When I replied to Dan, I assumed Ethereum was using UTXO so before posting, I queried and found this: https://github.com/ethereum/wiki/wiki/Design-Rationale Seems they came to some of the same conclusions as to why UTXO has limits.

We need this kind of documents.

Looks like fuzzy needs to learn more about this part ;)

Thanks abit

Hah! That's funny. Is he tweeting from the future?

Edit: Or... I'm just thinking in terms of America's stupid date structure. :)

Edit2: there it is: https://twitter.com/VladZamfir/status/838006311598030848

So that raises the next question... what the hell? BitShares seems pretty freaking amazing (as does Steemit). Why the lack of love from the masses?

Maybe humans really are silly meat bags confused by shinny marketing.

Wow good catch. Not sure how that date is there...

My bad (see edits). It's just the day first, the month second. I found the original tweet. It's legit.

I really don't get why we stupid Americans put the month first. That makes no sense at all.

But its 3-26-17 though...i think u are right...

I just wonder how that date got onto screenshot...cause to me it looks like the future.

@lukestokes, that is one of my biggest peevs :)

But its 3-26-17 though.

My Swedish twitter UI says "4 mars 2017"

Oh wait. Mar...not may. Now it makes sense.

VladZamfir Vlad Zamfir tweeted @ 04 Mar 2017 - 12:40 UTC

Ethereum isn't safe or scalable. It is immature experimental tech. Don't rely on it for mission critical apps unless absolutely necessary!

Disclaimer: I am just a bot trying to be helpful.

Looks like fuzzy needs to learn more about this part ;)

Thanks abit

Luke u and i should get a beee sometime....i have many thoughts on the matter and a pretty frigging large amount of history that makes it alll a very interesting story.

Man, definitely! You free some time next week? Let's make it happen. You can email me at luke.stokes @ gmail

Hopefully this gets documented.

Naw. But ill tell him a long story with my own perspective on the situation... ;)

He may well be getting someone to post for him so might not be reading the comments.

No one but Dan can write posts like these!

Wow what is that?

it's something that reminded me of dan.

I doubt it. It looks like dans writing (unless hes been doing this for a long time with a ghost writer) :D

Lol!

Thanks for explaining a key difference of blockchains using UTXO vs. message-based models. From a software development perspective, I'd imagine using messages is easier to reason about when building a blockchain application... and also much leaner on resources.

I didn't understand a lot of this article. This is by far your most challenging article I've read. I'll need to re-read a couple of times and do some research to try to see what I can get from it. Same for it's follow up. Thanks!

I kind of agree with you, for those who are not software architects and engineers, all the detailed explanations can be quite hard to 100% understand. The way everything is written is pretty much how I would like to see it though, since it tries to bring forward all the complex architecture stuff in not too much of engineering language.

The high level reasons why UTXO is not good for certain type of applications, and why Bitshares and Steem doesn't have that problem is however quite clearly explained, at least for me, but I'm used to talk with software architects, that helps I think.

Maybe it is just sufficient to know the result, the conclusion. Depends of course what you want to do with it. I for sure do not want to start discussing this topic with architects, but I may discuss this with lesser technical people, business people, financial people and with such information you will be seen as an expert in their eyes, so they start listening to you.

Very interesting... UTXO ensures that action is legit, in your example, can system have transactions that are validated directly and have block time same as latency and stay decentralized?!

Utxo does not impact dectralization at all. All actions on steem and bitshares are legit and dectralized.

Yes I know, I was referring to hypothetical situation where block time is dynamic and same as latency...

What do you think about other approaches in the blockchain universe, like Tendermint? It looks to me that Tendermint, by implementing a BFT blockchain, will split from the UTXO model as well.

Give 'em a left, and a right,...defend your head at all times,....

Good information and resteem

Thank you for sharing

Basically you're saying that QTUM project will fail.

I believe qtum is like bitcoin with evm rather than bitcoins scripts.

Seeing this makes me sad:

I've worked with a business partner for 10 years. It's hard. I wish you all could have worked it out. :(

i guess whale experiment is still on, and @dantheman is breaking the rules on a site he built. Now that sounds like a killer article title! Corrected: Ned flagged it before Dan upvoted it...

I didn't break the whale vote treaty, Ned flagged it before I voted so I negated the flag.

OH LORD. That's just not very funny at all. What a bizarre deal. Ned is not looking great in this situation.

OH LORD. That's just not very funny at all. What a bizarre deal. Ned is not looking great in this situation. @stellabelle

I get you and I share some of the same sentiments yet Steem is a great show and we don't have all of the information. Long live Steem!

Yes, that was a depressing moment for me as well.
Social media that's turned out to be well.......not very social.

wow, great post.
number one is the best..
thanks for sharing,, @dantheman

Really, didn't understand a thing. But it is not necessary to exactly understand a surgeon as long as you are sure he knows what he was talking about. Otherwise, someone might take a serious operation on your wallet ;)