Bitcoin Forum
September 17, 2019, 08:11:57 PM *
News: If you like a topic and you see an orange "bump" link, click it. More info.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: How are UTXOs stored?  (Read 1724 times)
tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 25, 2015, 04:12:36 PM
 #1

As far as I understand, when bitcoin client starts it parses the whole blockchain back from genesis block to build UTXO database. Later when it verifies a new transaction it uses the UTXO database and doesn't read the actual blocks where the outputs come from. Correct?

How does it store the UTXO database? In memory or on disk? If on disk, are there any integrity checks to protect from a hacker silently breaking into the node machine and modifying the UTXOs to whatever he wants?

Simplicity is beauty
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1568751117
Hero Member
*
Offline Offline

Posts: 1568751117

View Profile Personal Message (Offline)

Ignore
1568751117
Reply with quote  #2

1568751117
Report to moderator
1568751117
Hero Member
*
Offline Offline

Posts: 1568751117

View Profile Personal Message (Offline)

Ignore
1568751117
Reply with quote  #2

1568751117
Report to moderator
1568751117
Hero Member
*
Offline Offline

Posts: 1568751117

View Profile Personal Message (Offline)

Ignore
1568751117
Reply with quote  #2

1568751117
Report to moderator
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
January 25, 2015, 04:16:29 PM
 #2

Quote
If on disk, are there any integrity checks to protect from a hacker silently breaking into the node machine and modifying the UTXOs to whatever he wants?
If hacker is able to modify utxo database he is also able to put new checksums for passing integrity checks.
domob
Legendary
*
Offline Offline

Activity: 1083
Merit: 1100


View Profile WWW
January 25, 2015, 04:47:33 PM
 #3

As far as I understand, when bitcoin client starts it parses the whole blockchain back from genesis block to build UTXO database. Later when it verifies a new transaction it uses the UTXO database and doesn't read the actual blocks where the outputs come from. Correct?

How does it store the UTXO database? In memory or on disk? If on disk, are there any integrity checks to protect from a hacker silently breaking into the node machine and modifying the UTXOs to whatever he wants?
They are stored on disk, in an instance of Google LevelDB.  But as amaclin already said, if someone breaks into your machine and gets to modify the data directory, they can just work around any integrity checks, too.

Use your Namecoin identity as OpenID: https://nameid.org/
Donations: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
Sukrim
Legendary
*
Offline Offline

Activity: 2506
Merit: 1002


View Profile
January 25, 2015, 05:48:37 PM
 #4

There are proposals out there to add a hash of a deterministically generated UTXO set (or rather tree) either in block headers or maybe coinbase transactions. To really enforce the correctness of these hashes though, you'd need at least a soft fork. They could give strong indication though.

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 25, 2015, 06:06:26 PM
 #5

So, before any of the proposals is implemented, if someone manages to poison UTXO databases of a few biggest miners or mining pools that hold more than 50% of hashing power combined, he'll be able to later spend a fake output that never existed (or had smaller value) and it'll get into a block? Other miners will reject the block but they are a minority. Non-mining nodes will also reject but who cares.

Simplicity is beauty
Sukrim
Legendary
*
Offline Offline

Activity: 2506
Merit: 1002


View Profile
January 25, 2015, 06:13:01 PM
 #6

The "illegal" UTXO would be easily identifiable and stick out like [insert metaphor].

Yes, it is a possible attack, it is definitely not "silent" at all and would very likely just lead to manually orphaning the blocks with this input. A LOT of people run non-mining nodes who do care quite a lot actually. Forking them all off is not something that you'll easily accomplish.

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2800
Merit: 2410



View Profile
January 25, 2015, 06:31:17 PM
 #7

There are proposals out there to add a hash of a deterministically generated UTXO set (or rather tree) either in block headers or maybe coinbase transactions. To really enforce the correctness of these hashes though, you'd need at least a soft fork. They could give strong indication though.
This doesn't do anything to answer the OP's proposed situation though, since someone who can modify that can modify _anything_.  There is, and seemingly can be, no protection against someone who can silently change arbitrary data on your computer... Fortunately thats just a personal risk and you can protect against it by securing your system in the first place.
Sukrim
Legendary
*
Offline Offline

Activity: 2506
Merit: 1002


View Profile
January 25, 2015, 06:46:21 PM
 #8

It would at least offer a shortcut to a complete -reindex and slightly raise the bar for an attacker.

"If running away from a lion you don't need to be faster than the lion, you need to be faster than the guy running next to you!" ~Anonymous

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2800
Merit: 2410



View Profile
January 25, 2015, 07:19:31 PM
 #9

It would at least offer a shortcut to a complete -reindex and slightly raise the bar for an attacker.
"If running away from a lion you don't need to be faster than the lion, you need to be faster than the guy running next to you!" ~Anonymous
I don't see how this raises a bar to an attacker in the slightest. The easiest attacks don't involve changing the utxo set at all.

Can you walk me through an attack which would be meaningfully thwarted which isn't already massively more complex than a simple attack? I'm not seeing it.
Sukrim
Legendary
*
Offline Offline

Activity: 2506
Merit: 1002


View Profile
January 25, 2015, 08:09:00 PM
 #10

The attack we're discussing is "someone injects their own transaction output into bitcoin's UTXO set so several miners would mine an invalid block containing that output", right?

With an external source for an UTXO set at a certain block height, it would be much easier to audit your own operation and you could even perform periodic online audits of your current proposed UTXO set as you only need a known good set and compare it to the couple transactions that you'll include in your block. Currently you'd need to parse all blocks from genesis to do this, so it is rarely, if ever, done.

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 25, 2015, 09:33:24 PM
 #11

This doesn't do anything to answer the OP's proposed situation though, since someone who can modify that can modify _anything_. 

Not quite anything. The safest place to store a checksum is blockchain itself since it cannot be modified without re-mining blocks.

How about this:
1. Include a hash of the current UTXO set in an OP_RETURN output of coinbase transaction.
2. Keep UTXO set strictly in memory so that it can't be manipulated by other processes.
3. Before loading UTXO set from disk (e.g. after restart) calculate its hash and check against the value stored in coinbase. Also, re-verify the block where the hash is stored.

Simplicity is beauty
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
January 25, 2015, 09:45:25 PM
 #12

Quote
The safest place to store a checksum is blockchain itself since it cannot be modified without re-mining blocks.
Checksum of what? Of levelDB files?
Are you sure that levelDB is perfect and immutable forever?
What if I want to use another database for storing blockchain or anoher levelDB version?

The checksum is *already* stored in blockcahin. This is a hash of latest block  Grin
Sukrim
Legendary
*
Offline Offline

Activity: 2506
Merit: 1002


View Profile
January 25, 2015, 09:53:02 PM
 #13

There is no canonical encoding for UTXO sets, so it is not 100% clear how this hash should be calculated to begin with.

Also to enforce that the UTXO hash in this OP_RETURN is actually valid and not just some bogus data, you'd need to add this as additional consensus rule --> this is called a soft fork. Yes, it might be nice to have but it would take quite some effort to actually accomplish. While there was sponsored work and some initial patches finished some time ago to do this (called "ultraprune" I think) by a Freicoin dev, they never made it into the mainline code afaik. Bitcoin-core devs generally try to keep the codebase small, so even adding code to generate UTXO-tree hashes that you can manually process will likely not make it into the client. You are free to try that of course and if nothing else works, maintain a fork.

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 25, 2015, 09:56:36 PM
 #14

Checksum of what? Of levelDB files?
Are you sure that levelDB is perfect and immutable forever?
What if I want to use another database for storing blockchain or anoher levelDB version?

Checksum (or rather hash) of UTXO data in some standardized format independent of storage engine.


The checksum is *already* stored in blockcahin. This is a hash of latest block  Grin
It is about securing UTXO set, not the latest block which is already safe.

Simplicity is beauty
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2800
Merit: 2410



View Profile
January 26, 2015, 06:17:10 AM
 #15

Please describe step by step the actual attack, which things would the attack do to whom and how would they profit from doing so.  AFAICT people are just handwaving here. Actually spelling it out can help clarify your thinking or help me understand (whichever is needing improvement).
tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 26, 2015, 08:28:50 AM
 #16

Please describe step by step the actual attack, which things would the attack do to whom and how would they profit from doing so.  AFAICT people are just handwaving here. Actually spelling it out can help clarify your thinking or help me understand (whichever is needing improvement).

1. Obtain access to a miner machine through a vulnerability.
2. Open his LevelDB database that stores UTXO set.
3. Insert a record that contains output to one of hacker's addresses. Alternatively, find a legitimate record that contains output to one of hacker's addresses and modify its value, say from 1 BTC to 100 BTC.
4. Cover your tracks by deleting logs that show the intrusion etc.
5. Repeat the steps above against other miners until the total hash power of the poisoned miners exceeds 50% (as of today, it is 4 mining pools). You don't need to hack all of them at the same time, the attack can span months.
6. Spend the output in step 3. Make sure the transaction goes directly to poisoned miners, not through clean non-mining nodes.

Simplicity is beauty
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
January 26, 2015, 08:34:49 AM
 #17

Quote
1. Obtain access to a miner machine through a vulnerability.
...
5. Repeat the steps above against other miners until the total hash power of the poisoned miners exceeds 50%
Too difficult. I have much more easy way:
1. Obtain access to a ATM through a vulnerability.
2. Take profit!
3. Repeat
hhanh00
Sr. Member
****
Offline Offline

Activity: 467
Merit: 261


View Profile
January 26, 2015, 09:03:54 AM
 #18

Please describe step by step the actual attack, which things would the attack do to whom and how would they profit from doing so.  AFAICT people are just handwaving here. Actually spelling it out can help clarify your thinking or help me understand (whichever is needing improvement).

1. Obtain access to a miner machine through a vulnerability.
2. Open his LevelDB database that stores UTXO set.
3. Insert a record that contains output to one of hacker's addresses. Alternatively, find a legitimate record that contains output to one of hacker's addresses and modify its value, say from 1 BTC to 100 BTC.
4. Cover your tracks by deleting logs that show the intrusion etc.
5. Repeat the steps above against other miners until the total hash power of the poisoned miners exceeds 50% (as of today, it is 4 mining pools). You don't need to hack all of them at the same time, the attack can span months.
6. Spend the output in step 3. Make sure the transaction goes directly to poisoned miners, not through clean non-mining nodes.

You don't benefit but just harm the miners. Even if one of the poisoned miners find a block, it will be checked by every other full node in the network. Therefore it will be rejected as soon as the miner tries to push out his block. It will be as if half the miners were on a bogus chain, the hash rate will be effectively reduced by half but eventually a non poisoned miner will find a block or a poisoned miner will correct his UTXO set. In the later case, he may never know what happened but fixing the situation is rather simple as it is a matter of rebuilding the database.

tonych
Hero Member
*****
Offline Offline

Activity: 887
Merit: 808


View Profile WWW
January 26, 2015, 09:59:12 AM
 #19

You don't benefit but just harm the miners. Even if one of the poisoned miners find a block, it will be checked by every other full node in the network. Therefore it will be rejected as soon as the miner tries to push out his block.

The vast majority of nodes will reject the block indeed, but it is mining power that is the point of reference here, not the number of nodes. Since most of the hash power was poisoned, the offending block will be accepted by miners who control more than 50% of the total hash power. Then there are more than 50% chances that the next block will be built on top of the offending one, and so on.

The merchant who would accept the payment typically waits for 3 confirmations, that is 30 minutes. It'll likely take longer before someone notices that almost the whole network boycotts the longest chain, identify the cause, and persuade the poisoned miners to manually orphan the bogus chain.

There is one more "if" though: the merchant must be directly connected to one of the poisoned miners and not running a full node himself.

Simplicity is beauty
hhanh00
Sr. Member
****
Offline Offline

Activity: 467
Merit: 261


View Profile
January 26, 2015, 10:51:50 AM
 #20

There is one more "if" though: the merchant must be directly connected to one of the poisoned miners and not running a full node himself.
Such a merchant - if he even exists - should not be in the Bitcoin business unless he sells hugs. He relinquished his trust to some other anonymous party. And for what reason? And why wait for this attack? The mining pools can collude and clean him out.

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!