Ultimate blockchain compression w/ trust-free lite nodes

[sugarpuff]

Checkpoints are a temporary hack that will go away soon, we hope.

Maaku, I take your silence to indicate either that you believe I am wrong but do not (for whatever reason) want to explain why you think so.

Or... well, actually that's my only hypothesis.

For my part, I do not see how you can be right, and I provided my reasons for why I think that. As far as I can tell, once the leaves have all been fetched, miners can safely mine on the blockchain without having to download the histories of all those coins.

[maaku]

I explained myself, twice:

The miner needs to verify the entire block chain history because otherwise he has no way of knowing if he is actually on a valid chain or not. This has nothing to do with UTXO commitments, rolling root, or any other proposal. It's a basic, fundamental requirement of any consensus system: if the miners themselves operate in SPV mode (which you advocate), then anyone -- no matter their hashrate! -- can trick the network into mining an invalid chain. The attacker does so by mining a fork with invalid history and temporarily (by luck or 51%) overcoming the honest network. New miners coming online, or miners tricked into reseting their state then switch to the invalid chain This completely invalidates the SPV assumption and makes it unsafe for anybody to use the network.

[doldgigger]

Checkpoints are a temporary hack that will go away soon, we hope.

How is that? Performance suddenly considered a bad thing?

[sugarpuff]

I explained myself, twice:

The miner needs to verify the entire block chain history because otherwise he has no way of knowing if he is actually on a valid chain or not. This has nothing to do with UTXO commitments, rolling root, or any other proposal. It's a basic, fundamental requirement of any consensus system: if the miners themselves operate in SPV mode (which you advocate), then anyone -- no matter their hashrate! -- can trick the network into mining an invalid chain. The attacker does so by mining a fork with invalid history and temporarily (by luck or 51%) overcoming the honest network. New miners coming online, or miners tricked into reseting their state then switch to the invalid chain This completely invalidates the SPV assumption and makes it unsafe for anybody to use the network.

In what universe is that an answer to the facts that I pointed out?

You're continuing to ignore that:

1. I did not advocate SPV.
2. UTXO is not SPV.
3. Rolling root is not SPV.

The 51% attack you describe would have *equal* impact on nodes with the full history (so far as I understood what you're describing).

You never explained—anywhere—how UTXO "full-leaf nodes" are different in any meaningful manner from nodes with complete transaction histories.

Still waiting for that reply.

[instagibbs]

Still waiting for that reply.

Let's say we only have one ledger block, or whatever, or UTXO commitment thing. If we don't know the blocks before that, other than just headers, we can't verify that people are building on valid blocks. Someone could have made a fraudulent ledger block, and built on top of it. If people don't catch this, and never check contents before that, they have successfully attacked the network.

I think of it as SPV++ security: We are saying the ledger blocks/UTXO commitments are "secure" based on how deep in the chain they are, rather than looking at height. The only way to know the chain is valid is to start 100% from the beginning, and work your way through until you reach the current height.

[sugarpuff]

Let's say we only have one ledger block, or whatever, or UTXO commitment thing. If we don't know the blocks before that, other than just headers, we can't verify that people are building on valid blocks. Someone could have made a fraudulent ledger block, and built on top of it. If people don't catch this, and never check contents before that, they have successfully attacked the network.

(For any audience, "ledger block" is same thing as "rolling root".)

Thank you for the reply (and trying to address my questions)! I'm not convinced that is correct, however. How would this attacker create a convincing fraudulent ledger block that beats the ledger block of the honest nodes?

1. The ledger block of the honest nodes will contain transactions that can be verified to have thousands of confirmations.
2. The ledger block of the honest nodes will be part of a longer chain than the fraudulent one for the same reasons described in the bitcoin paper.

If I'm wrong, I must be missing some subtle and would appreciate it if you (or anyone else) could explain what that is.

[sugarpuff]

Edited point 1 in above post of mine to state:

1. The ledger block of the honest nodes will contain transactions that can be verified to have thousands of confirmations.

[instagibbs]

Edited point 1 in above post of mine to state:

1. The ledger block of the honest nodes will contain transactions that can be verified to have thousands of confirmations.

Ok, well again, this is still SPV-like security(block depth). That's the definition of the security model. Practically you might feel it's ok, but it's certainly a different security model than Bitcoin full node security.

[sugarpuff]

(For any audience, see SPV in Thin client security.)

Ok, well again, this is still SPV-like security(block depth). That's the definition of the security model. Practically you might feel it's ok, but it's certainly a different security model than Bitcoin full node security.

In that it is using block-depth it is like SPV (this I already acknowledged in a previous post), but it is not the same because of the extra information in the UTXO, and it is not the same as rolling-root/ledger-block because the current root is guaranteed to not have any relevant transactions prior to it.

Please be specific. What does the attack scenario look like with UTXO and/or ledger-block, and why does it require the full transaction history?

The wiki seems to agree with me actually:

If such UOT hashes were included in the block chain, a client which shipped with a checkpoint block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Block_chain_.28UOT.29

Edit: Although it is saying something slightly different (shipping clients with the full UTXO already intact, but I don't think that's necessary with rolling root. Would have to give it more thought, but might not be necessary for UTXO either. If there's a problem for UTXO, it could be fixed with a rolling-root type solution).

[instagibbs]

It's the difference between saying:

1) I believe the UTXO checkpoint is valid because people built on top of it. (SPV-like, depth-based)

and

2) I don't have to trust any checkpoint, I computed the address balances from the beginning of time.

I'm not even trying to argue about a practical attack, I'm simply explaining why they're different. They are.

[sugarpuff]

It's the difference between saying:

1) I believe the UTXO checkpoint is valid because people built on top of it. (SPV-like, depth-based)

With a UTXO checkpoint built-in to the client, safety is guaranteed (so far as I can tell) if the checkpoint is valid.

That is the scenario the wiki discusses. The scenario I originally asked about is downloading the entire UTXO chain (not a checkpoint of it).

I'm not even trying to argue about a practical attack, I'm simply explaining why they're different. They are.

They are different but if the difference isn't meaningful in terms of security for the chain then there's no issue and UTXO and/or ledger-block can be used instead of downloading everything from genesis (this is good news btw! You should want to make it work, otherwise bitcoin won't be sustainable).

[warpio]

If the client has a built-in feature that takes a checkpoint of the UTXO every so often based on the longest valid blockchain, and the code for that feature is well documented and understood, then I think there would be no problem with trusting the built-in UTXO checkpoints.

[sugarpuff]

I think it would be helpful (in general) for me to paste here my updated understanding of how these "full-security new lite-nodes" would be booted up:

For a new node to boot up from scratch and begin securing the network, approximately the following needs to happen:

1. Download entire BTC blockchain headers.
2. Download the entire UTXO meta chain.
3. Begin merged mining on UTXO and BTC blockchains. begin mining *only* when we've built up the complete UTXO tree.
4. For each new transaction the "almost-full node" receives, query other nodes for the block in which the payer's bitcoins were previously located, along with the hashes to verify the merkle root in the BTC blockchain. Verify the root can be found. Edit: This part is just regular SPV!
5. Query other nodes for the transactions and merkle root hashes that result in the merkle root hash of the most recent block in the UTXO blockchain. Verify that previous txn the coins belong to exists in the current data comprising the most recent merkle root of the UTXO blockchain.
6. If the transaction passes the above verifications, store all received data so far in order to build the Merkle hash tree that represents all the UTXOs.

To build the complete UTXO tree, ask for any missing children of our current UTXO merkle tree and verify them according to the above.

[sugarpuff]

Erm, just a note, I forgot to remove Step 7 when I copied that post:

7. Continue mining blocks as per above to secure the network and build new blocks, slowly transforming this light node into a full node.

I deleted that. Mining will commence only *after* our local UTXO merkle tree thing has be completed.

[maaku]

That appears to be a correct description of SPV+ mode.

[sugarpuff]

That appears to be a correct description of SPV+ mode.

OK cool, thanks maaku for reviewing it!

Then it sounds like UTXO / SPV+ is a solution to the long running problem of safely and quickly bringing new bitcoin nodes online. That's really great news if true!

So who's working on this? I haven't seen etotheipi post anything recently, is he still working on it? Does he still need donations?

[maaku]

I don't know of anyone besides me who is still working on UTXO commitments. It is developer time limited right now since for about six months I've been split between multiple projects trying to make ends meet. I posted a summary of the current state earlier in this thread, and any bitcoins or bitcoind developers would be appreciated in speeding the process along.

[sugarpuff]

I don't know of anyone besides me who is still working on UTXO commitments. It is developer time limited right now since for about six months I've been split between multiple projects trying to make ends meet. I posted a summary of the current state earlier in this thread, and any bitcoins or bitcoind developers would be appreciated in speeding the process along.

Mmmk, sent ya a PM.

[ittayEyal]

I guess I'm not sure what's the ultimate goal of this. Do you want to actually prune the Blockchain prefix at some point, or is this just a mechanism to speed up bootstrapping? My feeling is that this mechanism is secure enough for the latter cause, but not for the former.

To verify that a UTXO set i includes all utxo's, the verifier has to go back to the latest UTXO set it trusts j and make sure there are no missing outputs between j and i. There is no way to do that once the Blockchain get pruned at i.

Technically, it's possible to lose utxo's this way, if the network wrongfully accepts a partial UTXO set and prunes the prefix. That being said, it's quite difficult to take advantage of this vulnerability, so I think it is viable for fast bootstrapping.

Or perhaps I'm missing a part of the mechanism? Please correct me if I'm wrong.

[sugarpuff]

I guess I'm not sure what's the ultimate goal of this. Do you want to actually prune the Blockchain prefix at some point, or is this just a mechanism to speed up bootstrapping? My feeling is that this mechanism is secure enough for the latter cause, but not for the former.

What do you mean "not for the former"? This scheme would make the prefix irrelevant. If you don't care about the history of those coins there's no issue (that I can see).

To verify that a UTXO set i includes all utxo's, the verifier has to go back to the latest UTXO set it trusts j and make sure there are no missing outputs between j and i. There is no way to do that once the Blockchain get pruned at i.

Technically, it's possible to lose utxo's this way, if the network wrongfully accepts a partial UTXO set and prunes the prefix. That being said, it's quite difficult to take advantage of this vulnerability, so I think it is viable for fast bootstrapping.

Or perhaps I'm missing a part of the mechanism? Please correct me if I'm wrong.

I think either I've misunderstood what you're saying here, or you've misunderstood the how this would work. Please let me know either way.

Once a node has a complete UTXO tree that corresponds to the most recently accepted block, there should be no problems from that point on. It does not go to the UTXO to verify much of anything, but merely updates it based on newly minted blocks.

The blockchain can be pruned locally according to any lossless scheme the node desires. The only place I see a potential issue is if there's a reorganization (a different fork suddenly exceeds the current in length). If that happens, and the node pruned too closely to the current time, then it might not know how to safely deal with the reorg event. To mitigate against this, nodes can keep a blockchain prefix of sufficient length.