Topic: superblock checkpoint architecture (Read 2213 times)

It is a work in progress (like most things related to Bitcoin).  The first step was getting nodes to store locally a pruned version of the blockchain.  The messages used by for inter-node communication will need to be extended to support requesting and sending pruned blocks.  If you have a full block it is relatively simple to compute a pruned version of the block and replace the transactions with placeholders.   However it probably makes more sense to first extend the block messages to support compact representation of the block which replaces the full transactions with just the transaction hashes (txid).  This would also speed up block propagation of new blocks as most nodes already have the set of transactions contained in the block.  Later the compact block message could be compacted further by using placeholders for the transactions which are pruned out of the merkle tree.

One correction to my prior response, all nodes need the genesis block (hardcoded to the client) and blockheaders, to perform basic validation.   This includes SPV clients as well. The good news is the headers are small (~5MB per block year).  The headers prior to the last checkpoint could even be included in the client to speed up bootstrapping.

As for how long would it take to bootstrap a new node from genesis block to fully validated UXTO?  Well that depends on the size of the UXTO.  The good news is the UXTO grows much slower than the full blockchain.  The bad news is that prior to the "dust" rules a lot of outputs were created which likely will never be spent because their value is so much smaller than the cost of spending them. They end up bloating the UXTO.  This is why the dust rules are so important (despite the poutrage from a vocal minority).  Someday it may make sense to allow limited spending with no fee of "old dust" by adding an exception to the high priority rules.  There are also a lot of optimizations that are possible.  In the future boostrapping nodes may take advantage of larger numbers of peers and multithreaded verification engine to receive, verify, and store pruned blocks much faster than they do now.

Great, so how do we ensure that I am getting a legit UXTO/tree set? 
Where are we now with this stuff?  I.e., can I start up a full honest node to help support the network in an hour or less? 

I imagine there are some problems that could develop should the number of full nodes continue to drop. 

For #1 you don't "need" anything more than the UXTO plus set of pruned merkle trees.   The same optimizations which improve the efficiency of #2 can be used to improve the efficiency of #1 as well.

I have considered a restructuring of the blockchain.  I've even written some code, but I've not fully vetted it yet nor used it in earnest.

It adds to the blockchain header  a hash of the UTXO set.  You could use a merkle root instead, but I don't think it buys you anything in this case.

This would make the blockchain header take an extra 16 bytes - which due to the way ASICs work and our desire not to invalidate the ASIC investment out there, would force us to add a 64-byte block to each header, increasing the total size of the blockchain headers by a ratio of 3:2.  

At the same time, add to each transaction a hash of a recent block within whose chain that transaction is valid.  This in turn makes the transactions larger by about 16 bytes each.

What we get in exchange for that is that when you get a transaction, you can look for a block with the matching hash and be absolutely guaranteed that you are not "on the wrong chain" with respect to that transaction.  You look in that block for the UTXO hash.  This links you to a UTXO set which should match the updated set as it was after processing that block, which you can use that to verify that the inputs used by the transaction exist.  Then you look at blocks since the key block to make sure those inputs have not been used by some other transaction.

The result is that unless you're interested in the history and verifying for yourself that the 'deep chain' run from block zero does in fact produce the UTXO tree whose Merkle root you have, you don't have to download all that much of the blockchain.  

When you download the last "confirmation depth" blocks, you can start processing transactions that are valid within that chain -- and you know that you're not on a false chain, at least not as far as those transactions are concerned, because they list the block hash and you have a block with a matching hash.  Likewise, you know that you have the right UTXO set for that block, because the block has the hash for the UTXO set.  That allows you to download the UTXO set directly from an untrusted source, because you can verify for yourself that the hash matches. 

I think that's nyfty, but there is a drawback; by tying each transaction firmly to a particular block so that it is not valid outside of a chain descended from that block, you create a situation in which a transaction can be invalidated by any sufficiently-deep chain reorg.  Lots of people have deep heebie-jeebies about transactions other than double spends ever becoming invalid due to a chain reorg.

In practice I think there's only ever been one chain reorg that spanned more than a hundred blocks, and that was due to a bug; using a database software that couldn't cope with not getting as many file handles as it wanted.  So I'd have no problem with anchoring each transaction to a block 100 blocks previous to where it was to appear in the blockchain.  

Thanks for your very helpful replies.   There are two issues we are discussing:

1) Cost of downloading & validating full chain
2) Cost of "keeping up" a full node

I guess your machine is 6000x more than adequate enough for task number two  
My original concern is with number 1. 

In general, do you think we are prepared to cope with these two costs with current software (e.g. core)?  Could you point toward some development task which could help keep these costs down?

 

Bitcoin doesn't track "addresses" it tracks txouts. There are currently 10,623,198 txouts and the data is 369,816,656 bytes serialized. And we already are storing it this way (which is why its so easy to produce these numbers, the gettxoutsetinfo rpc provides them).  We just do not have a facility to delete the historical blocks for two reasons:  One we need to add discovery mechanisms to synchronize nodes in a network where every full node doesn't juts have the blocks, and two just basic software engineering of finding all the stats/etc. features that use the historic data and disabling them in this state instead of allowing it to crash.

Oh you absolutely cannot just send 300MB, your peers could just lie to you and it would be greatly in their short term financial interest to do so (because they could make you accept inflation or spends of non-existing coins). But you can produce this trusted state for yourself and you don't need to store anything else.  ECDSA is cheap, with libsecp256k1 my i7 desktop here validates at almost 6000x the maximum realtime rate for the Bitcoin network.

OK I think I am finally getting your drift.  A full client can basically *already* (sorta?) make a utxo list and use that rather than hold the whole chain?  Incidentally if the set is 300mbytes my estimate was way off.  For 1 million addresses (I think we are at more than that now), at 160 bits each, that leaves 15 bits to each address for the amount of unspent.   Am I calculating something wrong there?  And if this is true, why aren't we doing it already?         



Yes, an increase in marginal cost of validation is a real concern.  I guess I am thinking that the marginal cost of validating 5+ years of dust and mixing transactions is already getting too high.  At the very least we will need some kind of intermediate node.  Sending all new nodes 20 gigs of data and checking ECDSA sigs when you could be sending 300Mb seems suboptimal.  Especially if that 300Mb list of UTXOs had been validated by the entire network of miners for 100 blocks or more.  If there is a better way to do that with minimal (or no) changes to the protocol I am all ears.       

Thanks! --     

The data you use to validate doesn't have to have any relationship to the data sent over the wire beyond the fact that you get the same results when verifying.  No hashing is required to verify a new transaction that shows up (other than the hashing in the signatures, of course).  A transaction shows up, it names which txid:vouts it is spending and provides the required scriptSigs. You look up those txid:vouts in your utxo set and accept the transaction if the signatures pass.  The utxo set is currently about 300mbytes. You don't store the history there, you just store the much smaller set of spendable coins. The resulting behavior is indistinguishable from a node with the history except that a node without it can't serve old blocks to new bootstraping nodes... and this all works today, Bitcoin core is already structured this way, but doesn't yet support actually removing the old data.

With some p2p protocol additions validation actually can be made completely storageless but as a non-trivial bandwidth cost (by instead storing the root of a hash tree over the utxo set and asking peers to give the connecting fragments whenever they give you a transaction)... but the bandwidth cost of doing that is high enough that it's probably not worthwhile.


 
Can is very different than _does_. Today everyone constantly validates these things and instantly rejects invalid data. If you instead make it so that validation has a high marginal cost and by default people don't validate then you'll find many never validate and a few do. If miners start rewarding themselves too much coin ("A bit of inflation is good for the economy!") the network will partition into real validating and non-real validating nodes.  You might then say that the non-validating now need to go fix themselves to validate but what if they have spends in the non-validating fork that they've already acted on which are conflicted in the other fork already they're certantly not going to want to do that. Once the network has a non-trivial partition there is an extreme risk that it is fundamentally impossible to resolve it without causing severe monetary loss for someone.  So the "don't check and if something goes wrong, hopefully people will figure something out" mode doesn't really work— the only time you can really deal with an invalid block is the moment it happens, not later after people have taken irreversible actions because they thought it was okay.

This one kind of blew my mind   You're not talking about SPV nodes either here I think.  I guess the idea is that when a transaction appears on the network and I want to validate it, the TX already has the UTXO data and I just need to hash it, if necessary up a tree until I can compare to a merkle root that I do have stored.  But if I really have nothing stored, then the high level security of validating everything myself can't possibly be there?  Anyway, I am looking forward to seeing more of this. 

What I am proposing is a restructuring of the database.  The block chain is a log structured database due to the way it is built, but this is in general not an efficient way to store this kind of data.  A restructuring could be performed and validated by the network.  However if I understand what you are saying it may never be necessary. 
 

How is this different than a miner today issuing a block with a coinbase transaction greater than 25 coins?  Anybody can verify at any time that the block is fraudulent and ignore it and all blocks above it.  With my proposal new nodes can always check old blocks to verify the chain and the checkpoint.  They just aren't required to store the old blocks.   

Cheers -   

Point taken. 

I'm just playing devils advocate a little to explore possibility of saving space.

What about storing archive copies of the entire blockchain, so that
the super block could be verified anytime one wants to?

I guess that doesn't really save storage space, but maybe it
Could create the ability for full nodes and "semi full nodes"
Who use the super block.

But then again, I assume that is probably currently
Possible without changing bitcoin?

We do not trust it to verify transactions, we trust it only to order transactions, verifying we do for ourselves.  By verifying for ourselves we eliminate possible benefits of including invalid transactions and the profit that would go along with doing so. This is important because we depend only on economic incentives to get the honest behavior for ordering at all— there is no exponential gap between attacking and defending in POW consensus. If by being dishonest you can steal coins (or even reclaim lost ones) it's an entirely different trade-off question than a case where you can only rearrange transactions (and potentially replace your own).  This isn't to say that a system couldn't be constructed where only miners verified, but its a different and weaker set of security/economic incentives— and not just some minor optimization.

In addition to the incentives point above: The participants are not constant  and  set out at the front... anonymous parties come and go, so what does a "consensus" really mean if you're not a part of it and all those who are are anonymous self-selecting parties and perhaps sybils?  If I spin up 100 fake nodes and create a "consensus" that I have a trillion bitcoins and you join later— so it it matters greatly that the rules were followed before you showed up, e.g. that the creator of the system hadn't magically assigned himself a trillion coins using a fake consensus before you showed up. Of course you don't need the data any more once you've validated it— you can just remember that it was valid... but if you haven't, how are you to know except either by processing a proof of it (e.g. checking it yourself) or by trusting a third party?  Bitcoin was created to eliminate the need for trust in currency systems, at least to the extent thats possible.

Thanks for comments! 

I guess one could argue that we trust the network to verify transactions and provide the block chain, why not trust it to make checkpoints?  I can see the argument that the integrity and security is better if every transaction back to 2008 is verified by every node, but that needs to be weighed against the integrity and security lost by the number of full nodes dropping slowly off due to the storage and computation requirements. 

I need to think more about the the potential attacks, but I'm not sure I follow the one you describe.  A state commitment which redistributes unspent outputs, lost or not, to different addresses, would be easily spotted and rejected.  I was more worried about incentivising nodes/miners to pay attention to checkpoints at all due to the extensive requirement of verification.  A miner would likely simply ignore superblock and try building on top of the last normal block rather than spend the time verifying a list of millions of entries and writing gigabytes to storage.

I had a look through
https://bitcointalksearch.org/topic/reducing-utxo-users-send-parent-transactions-with-their-merkle-branches-314467

looks relevant but I'm not proposing such a reduction here.         

Couldn't a block still be created and after consensus has been established on the block, and after some time has passed, it could be used instead of the entire chain? How would that violate security assumptions?

This kind of stuff has been discussed many times before.  What you're suggesting here violates the Bitcoin security assumptions— that the integrity of the data is solid because all nodes full nodes have verified it themselves and not trusted third parties to do it— and in the simple form described opens up some pretty nasty attacks:  Make your state commitment always be to one where you own all the "lost" coins, sure, you're unlikely to find the next commitment yourself, but if you do— ca-ching!.   Of course, if you're verifying the state commitments, then there is no reason to use a 'high apparent difficulty' to select which blocks provide them (see the proposals about merkleized utxo for how a reduced security model can be implemented this way).

I like the idea in theory. 

my opinions hold little weight,  but at least 1 person likes it. Lol

You can't get much smaller than a list of who has what money, that's the essential information. 

So that's 160 bits per address and lets say 32 bits per amount (in general more is needed but some compression could be used as most unspent amounts are less than 2^32 satoshi).  That's 640 bytes per entry.  At 2 million nonzero addresses (roughly where we are now) that is about 1.3 gigs.   

Seems like a lot for one block but if you are dropping 15 gigs of block chain the net gain in portability is substantial.  There will always be copies of the old chain lying around which can be verified as authentic as well as used to verify that superblocks are valid.     

After reading this I realized how I'm far away from understanding everything connected to the hardware

I was referring to the block itself

Good question.  I guess the answer depends on the exact implementation.  

Do you mean how much RAM required for verification or for creation?  Or the size of the superblock itself?  

One related question is how much "data efficiency" there is on the block chain, which we could define as the size of a list of all unspent output address/amount pairs divided by the total size of the block chain.  Lots of mixing and spending leads to lower data efficiency.  A quick back of the envelope calculation shows we are doing pretty well here now, I estimate 75% or so.    

Edit: more like 10%.  I had confused bits and bytes    

At this stage it seems clear that we don't need anything like this because TX pruning works pretty well already.  However as rumblings continue from block chain bloat and the number of running full nodes decreases due to storage costs could it become worth considering a solution of this nature?  

how much memory would that snapshot require do ya think?