Bitcoin Forum
June 20, 2019, 06:34:14 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Idea:Add the UTXO set to blocks  (Read 114 times)
bitrails
Newbie
*
Offline Offline

Activity: 2
Merit: 11


View Profile
February 26, 2018, 09:56:13 AM
Merited by malevolent (5), DannyHamilton (2), achow101 (2), ranochigo (1)
 #1

Motivation

At the moment, anyone wanting to bootstrap any sort of cryptocurrency full node needs the full block chain. For Bitcoin as of 2018-02-26 thats ...(does a quick google search) 160GB(and maybe the segwit data too, don't know if that's included in that number).

Not too awful ($8 @0.05$/GB(Amazon EC2 bandwidth fee)), but if anyone wanted to make the block sizes bigger it would makes getting all that data initially very expensive, which makes running a full node harder. I won't get into the arguments about why that's might or might not be important just consider it.

UTXO set?
Bitcoin full nodes maintain an internal UTXO set (set of all UnspentTransactionOutput(s)). This means they don't have to dig around in all the previous blocks to figure out whether an output is present and hasn't been spent yet. What I'm proposing is a block structure that includes a hash of a canonicalized merkle tree of this UTXO set. Additionally, there would be links between this tree and the transaction merkle tree and vice versa to justify any additions and removals to the UTXO tree and justify the presence of transaction inputs.

Normal full clients won't notice any difference, (although they would now maintain the canonicalized form of the UTXO tree internally) they don't ever need to send the UTXO tree over the network though since the transactions specify how to mutate the last block's UTXO tree to get the next block's UTXO tree. The same is true for archiving of blocks, just keep a cached copy of the UTXO tree for every Nth block and the rest can be computed on the fly.

The real magic is that a client can connect to the network, get the current block and UTXO tree, and just in the same way transaction confirmations increase confidence that a transaction won't be reverted, additional blocks show miners are willing to add work to this blockchain and the UTXO tree that was sent to you.

An attacker could fork the blockchain and modify the UTXO tree then send you that block but no sane profit motivated miner will work on that fork of the chain since it isn't a valid fork. Thanks to the links between the UTXO trees and transaction trees within blocks, and with the right UTXO tree structure it's possible to create a small proof that any given link in the blockchain is invalid by supplying the conflicting merkle branches.

This would be especially great for proof of stake systems since this allows for a small proof of chain link incorrectness and therefore of miner/stakeholder misbehavior.

Generalising
This is a specific case of adding redundancy to the (block/blockchain/distributed ledger) structure. Data structures which are redundant (and therefore don't add network/storage overhead) but that help achieve protocol goals (in this case:easier bootstrapping/validation of chain links). There is a trade-off in reducing implementation flexibility and increasing validation times (since the redundant structures must be built and verified) but it's a tool that might be useful.

Vague Implementation details
  • Transactions in each block generates UTXO entries.
  • These would be tagged with an index into the transaction merkle tree for the output transaction and put into a per block UTXO entry merkle tree.
  • The roots of the per block merkle trees are put into a larger merkle tree covering all per block UTXO trees (yes this means the root of a per block tree changes when an output generated there is spent.)
  • When a UTXO is spent, the entry in the UTXO tree is tagged with second tag listing an index into the transaction tree for the spending transaction.
  • The spent entry disappears in the next block.
  • An output created and spent in the same block would show up in that block's UTXO tree with both tags and then disappear.

Denial of service(not really)
For (Lots of money) you can buy hash power to mine an invalid block. For a short time you can send it to nodes and they will try validating it (and fail). Nodes can immunize others by circulating short proofs of chain link invalidity to other nodes who will then ignore your block. The proofs would be deleted after a certain number of new blocks have been generated under the assumption that the invalid fork hasn't been extended.

Any thoughts?
1561012454
Hero Member
*
Offline Offline

Posts: 1561012454

View Profile Personal Message (Offline)

Ignore
1561012454
Reply with quote  #2

1561012454
Report to moderator
1561012454
Hero Member
*
Offline Offline

Posts: 1561012454

View Profile Personal Message (Offline)

Ignore
1561012454
Reply with quote  #2

1561012454
Report to moderator
1561012454
Hero Member
*
Offline Offline

Posts: 1561012454

View Profile Personal Message (Offline)

Ignore
1561012454
Reply with quote  #2

1561012454
Report to moderator
COINSWITCH
Trade 300+ coins
No Login
No KYC
Get $5 on 1st order
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1561012454
Hero Member
*
Offline Offline

Posts: 1561012454

View Profile Personal Message (Offline)

Ignore
1561012454
Reply with quote  #2

1561012454
Report to moderator
DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1406



View Profile
February 26, 2018, 02:16:12 PM
 #2

It's an interesting idea, and I'd like to see an altcoin try it out.  Implementing it in Bitcoin would require a fork, and I don't see it being important enough for that to happen anytime soon.

I haven't given your idea a lot of thought yet, but it feels like the general concept ought to be possible even if the specifics that you've described have any shortcomings.

achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 1792
Merit: 2459


bc1qshxkrpe4arppq89fpzm6c0tpdvx5cfkve2c8kl


View Profile WWW
February 26, 2018, 04:27:49 PM
 #3

This is not a new idea and is something that is actively being worked on.

The UTXO set is actually extremely large and hashing all of it as you describe is actually kind of computationally expensive. Furthermore, that hash has to be recomputed with every block. However there has been work on a fast way to compute the hash of the UTXO set and to efficiently add and remove entries from the hash without having to recompute the whole thing. See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html.

DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1406



View Profile
February 26, 2018, 04:56:55 PM
 #4

This is not a new idea and is something that is actively being worked on.

The UTXO set is actually extremely large and hashing all of it as you describe is actually kind of computationally expensive.

Certainly. But so is processing through the entire historical blockchain.

Furthermore, that hash has to be recomputed with every block.

Perhaps.  I've got a gut feeling that might not be necessary, but I'm not sure. I'd have to think about it a bit.  Couldn't it just be computed once every 100 blocks (or 1000 blocks, or 10000 blocks, etc) as sort of a UTXO checkpoint? Then a new node could start up from that checkpoint instead of the genesis block?

I've got a feeling there will be some potential attack vectors here where an attacker can provide a false UTXO and block history, but the computational work of the "valid" chain should be a deterrent.  I haven't thought that all the way through yet.

However there has been work on a fast way to compute the hash of the UTXO set and to efficiently add and remove entries from the hash without having to recompute the whole thing. See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html.

I'll have to read up on that.

bitrails
Newbie
*
Offline Offline

Activity: 2
Merit: 11


View Profile
February 26, 2018, 08:30:18 PM
Last edit: February 26, 2018, 08:44:04 PM by bitrails
Merited by achow101 (1)
 #5

If the UTXO set is put into a merkle-tree then updating any entry just requires updating a set of log2(N) nodes in the merkle tree going down to the root. for a set of 1 billion values this works out to 32 SHA2 operations. (see https://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates)

Furthermore, my proposed implementation keeps UTXOs from all blocks separated and newer UTXOs are more likely to be spent. Most block UTXO trees won't need to be updated. This is the motivation behind the multi-level UTXO cache currently used in core (that only keeps recent UTXOs in memory).

All this updating is parallelizeable so checking block validity can be easily sped up by adding more computers to your full node (if you are a miner and block validation has to be fast).


Quote
but the computational work of the "valid" chain should be a deterrent.  I haven't thought that all the way through yet.
If an attacker wants to do this, they have to keep adding blocks to an invalid chain which no main chain aware nodes will ever accept (very costly). In proof of work this costs them electricity, in proof of stake this would actually cost them stake. (or fees if they don't disclose all information needed to validate the block since they can't double sign at a given height)

It's an interesting idea, and I'd like to see an altcoin try it out.  Implementing it in Bitcoin would require a fork, and I don't see it being important enough for that to happen anytime soon.

Actually, a soft fork is definitely possible by merge mining this "alt-coin" into the Bitcoin blockchain. It provides no validity guarantees (since maliciously merge-mined blocks don't penalize miners) but it's a way to signal acceptance.
piotr_n
Legendary
*
Offline Offline

Activity: 1988
Merit: 1048


aka tonikt


View Profile WWW
February 27, 2018, 02:01:44 AM
Last edit: February 27, 2018, 02:13:10 AM by piotr_n
 #6

As I said about 5 years ago, this would take at least 10 years to deliver for the core dev team.
So don't expect it within the next 5 years Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 1792
Merit: 2459


bc1qshxkrpe4arppq89fpzm6c0tpdvx5cfkve2c8kl


View Profile WWW
February 27, 2018, 09:34:09 PM
 #7

Actually, a soft fork is definitely possible by merge mining this "alt-coin" into the Bitcoin blockchain. It provides no validity guarantees (since maliciously merge-mined blocks don't penalize miners) but it's a way to signal acceptance.
It could be deployed just as a normal soft fork into Bitcoin by putting the UTXO set commitment into another OP_RETURN output just like what segwit does for the witness root commitment.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!