Blockchain Compression

[hazek]

The payment protocol is foundational work, it is required for a lot of other features. That's why it's important. Pruning is a needed scalability fix but we're far from having some kind of crisis because people can't afford the disk space. A lot of people blow more than 8 gigs of disk space on apps they simply forgot about.

Man, for a brilliant programmer I can't believe what utter shit you sometimes post.

Yes the disk space currently isn't a problem. But you know damn well that it only takes a little over 2 more doublings of transaction volume in terms of space and we're going to reach the hard limit of 1Mb. And then what, chief? Not to mention that this will mean 55GB blockchain size increase per year but undoubtedly you and Gavin will both lobby for a reckless hardfork then instead of trying to find a different solution now.

But I'm perfectly aware where your Google spoiled centrally planning head is coming from. You want more control cause it's easier from a technical standpoint, you don't care one bit about the decentralization part of Bitcoin and you don't care what sort of consequences not focusing on this issue now and forcing a hardfork then will have.

[TierNolan]

The payment protocol is foundational work, it is required for a lot of other features.

Is there a summary of what is being considered here?

[maaku]

Again, the "ultimate blockchain compression" thing doesn't make any technical sense, that's why it's not happening.

I'd love to hear your technical arguments regarding that.

[d'aniel]

Again, the "ultimate blockchain compression" thing doesn't make any technical sense, that's why it's not happening.

I'd love to hear your technical arguments regarding that.

He described them here once: https://bitcointalk.org/index.php?topic=93606.msg1607170#msg1607170

[Mike Hearn]

hazek, you are not a developer so you really shouldn't get angry about technical topics. I already explained that block chain pruning will allow you to run a full node that uses an arbitrary (user specified) amount of disk space. So when the chain gets to be 55 gigs, OK, if you can spare 55 gigs then keep all of it. Otherwise keep 30 gigs of it. Or 10. Or none. Regardless of what you can afford, you will still be able to run a full node. You just won't be able to serve the whole chain to a new node that's starting from scratch (so someone, somewhere will have to keep a full copy of the chain, but that's fundamental to how Bitcoin works).

If you don't understand what I'm talking about, go do some research and come back when you do understand. Flaming people because you prefer to believe in conspiracy theories than learn hard technical facts just makes you come across as immature.

By the way, I've spent over two years implementing SPV mode so people can use the P2P network directly without having to download the block chain - and without relying on any trusted servers. Only a handful of people have put as much effort into keeping Bitcoin decentralised as I have. So by saying that I don't care about decentralisation you just sound even more uninformed.

Is there a summary of what is being considered here?

It'll be written up in BIP form soon. Until then, this link is the first result on Google for "bitcoin payment protocol":

https://github.com/bitcoin/bitcoin/pull/2539

I'd love to hear your technical arguments regarding that.

The idea was to put a commitment to the UTXO set into the coinbase transactions. The claim was this lets you run a full node without processing the full chain, and that it helps lightweight clients. The first claim is not true, which is why it's now crossed out in the original post.

https://bitcointalk.org/index.php?topic=88208.0

You can't have full node security by bootstrapping off a miner-majority consensus, that's SPV level security by definition. To bootstrap a full node in a trust free manner you have to process the entire chain, or get a copy of the database from somewhere you "know" is correct (i.e. another one of your own nodes).

The second claim that it helps lightweight clients also isn't really right. I've actually implemented lightweight mode (the one described by Satoshi at least) and UTXO commitments really change much, at least not fundamentally. You still need all the block headers to track the consensus, and at that point you may as well ask for transactions that match your keys at the same time using the existing merkle trees. A UTXO commitment in the coinbase might make things faster if you were to import a private key, at the cost of significantly increasing resource usage of every single node on the network. Given that private key import is (or should be) rare, this isn't a good tradeoff.

Fortunately, none of that is needed. Satoshi already described everything that is required to make Bitcoin scale in his white paper nearly 5 years ago. Most of it is already implemented. The ability to delete old blocks from the chain when you start running out of disk space is waiting merely for the protocol to be upgraded so nodes can advertise how many blocks they have, and for wallet apps to be upgraded so they find nodes that still have the range of blocks they need to catch up with.

[hazek]

I apologize for my rudeness, my frustration got the best of me.

I already explained that block chain pruning will allow you to run a full node that uses an arbitrary (user specified) amount of disk space.

My complaint was that implementing it is not a priority when it should be and that implementing it too late might have grave consequences.

By the way, I've spent over two years implementing SPV mode so people can use the P2P network directly without having to download the block chain - and without relying on any trusted servers. Only a handful of people have put as much effort into keeping Bitcoin decentralised as I have.

Awesome job. However how does the use of SPV clients prevent centralization of the Bitcoin network? Are SPV clients equally sovereign when it comes to deciding which blockchain, which new blocks and transactions are valid?

If you read back my post, you will notice that I called you a brilliant programmer because I really think you are one. And I never said you are not putting in a significant effort in order to improve Bitcoin. My complaint was that the development that you are contributing isn't the development that Bitcoin crucially needs in order to remain decentralized and prosper. I mean unless I'm mistaken about SPV clients in which case please correct me.


p.s.: while I admit that the tone of my post was not entirely constructive, you definitely didn't rise above me by calling my a conspiracy theorist

[Mike Hearn]

Well Gavin, at least for now, isn't too worried about disk space usage.  It'd only take a couple of months to fully implement the last parts of pruning if he worked on it seriously, and it's hard to imagine the block chain doubling in size in only a few months. That'd be a nice problem to have. Even then, 16 GB isn't all that much. I have 182 GB free on my computer and it's a pretty ordinary laptop.

At the moment Gavin's biggest worry is security. The payment protocol is designed to complement the Trezor project and give us better security than the best banks. Also, as I said, Pieter has said he wants to work on pruning, so that might be another reason Gavin's not prioritising it at the moment. Pieter has a full time job these days so it's harder for him to find the time, but even so, he's done amazing work on scalability and I'm sure he'll be able to finish off the pruning work some time this year. I'd guess the block chain will be under 12 gigs by the time pruning starts. So no risk of a crisis.

In short, yes it's important and will happen, but we're not going to see Bitcoin collapse if it doesn't happen this year. The numbers just don't work out that way.

Awesome job. However how does the use of SPV clients prevent centralization of the Bitcoin network? Are SPV clients equally sovereign when it comes to deciding which blockchain, which new blocks and transactions are valid?

I guess that's a rhetorical question? Anyway, at least for other people who are reading, no as described in Satoshi's paper they only validate the block headers. So they pick the hardest chain and then assume the contents are likely to be correct. You can't mine with them but in practice "best chain is correct" is usually good enough, at least for normal individual users.

If you can afford a full node, that's better. But most casual users won't want to run one. The next most decentralised after that is SPV. No central or trusted servers. You place your trust in the majority consensus instead.

If we didn't have SPV clients then Bitcoin usage would be dominated by services like blockchain.info or Coinbase. Both great companies and sites, but ultimately people would end up putting their money into "BitBanks" and relying on third party companies. Those organisations would then either get regulated out of existence, or become real banks and start lending out their bitcoins at interest. In some ways Bitcoin usage is already dominated by these sorts of wallets and it's not even hard to run bitcoin-qt today, so you can imagine how common it'd be in future with much larger blocks. That's why my no 1 priority is to try and build SPV wallets that are competitive with centralised bank-like services, to avoid that future and keep people using the P2P network directly without any middlemen (or more technically, with only p2p nodes and miners as middlemen).

Re: conspiracy theories, yes, sorry. Quite often people on this forum claim that because I work for Google, I must have some incentive to try and centralise Bitcoin or <insert theory here>. It's nonsense of course, Google is focused on Google Wallet and hardly cares about Bitcoin. In fact Google not only employs me but also Pieter, who has done more work on pruning than anyone. It's about as relevant as the fact that Jeff once worked for Red Hat.

[maaku]

You can't have full node security by bootstrapping off a miner-majority consensus, that's SPV level security by definition. To bootstrap a full node in a trust free manner you have to process the entire chain, or get a copy of the database from somewhere you "know" is correct (i.e. another one of your own nodes).

Right now the choices are SPV or full node. The misnamed “ultimate blockchain compression” proposal would enable a wide spectrum of security modes in-between the two. Initial synchronization requires SPV level of trust in the checkpointed UTXO set. However from that point forward full validation can be performed, and history can be incrementally validated as far back as required (to the last checkpoint, for example, or the full history). The ability to construct fraud proofs provides an additional layer of security as it provides a compact way to inform other peers of an attack-in-progress. These are valuable options that enable secure limited-trust operation on constrained devices, or a graduated level of security as synchronization is performed.

The second claim that it helps lightweight clients also isn't really right. I've actually implemented lightweight mode (the one described by Satoshi at least) and UTXO commitments really change much, at least not fundamentally. You still need all the block headers to track the consensus, and at that point you may as well ask for transactions that match your keys at the same time using the existing merkle trees. A UTXO commitment in the coinbase might make things faster if you were to import a private key, at the cost of significantly increasing resource usage of every single node on the network. Given that private key import is (or should be) rare, this isn't a good tradeoff.

Mike, you seem content to trust that peers will send you transactions matching your bloom filter. I do not find that reasoning compelling. The UTXO index will give a short, verifiable proof that matching transactions are or are not reported.

[Mike Hearn]

Sure, you can start with SPV security and then convert yourself to full security, but that could be done today with no protocol changes. Pieter calls this "headers first mode". Over time I became less convinced it was a good idea to convert between them like that though. I used to think it was obvious but eventually concluded users should make an explicit choice to run a full node. Once they made that choice it doesn't really matter how long it takes to bootstrap, they're in it for the long haul anyway.

For a node that does a selective DoS on Bloom filtering, have you actually observed anyone do such a thing? What would be the motive and why is querying multiple nodes not enough to fix that?

I can see that with a properly constructed set of Merkle trees a remote node could provide a proof that it hasn't excluded any transactions, assuming you trust the last block. But most real wallets want to know about pending transactions too, and you still need the Bloom filtering for that. So the cost/benefit analysis for using address index commitments to avoid malicious Bloom filter drops feels rather questionable to me.

For fraud proofs, I think d'aniel raised that before, I'm afraid I don't remember which proofs require the commitments. Double spends don't. At any rate, whilst those proofs would indeed be useful they weren't the rationale given for "ultimate blockchain compression" originally. A full design doc for different kinds of fraud proofs would be useful.

[TierNolan]

It'll be written up in BIP form soon. Until then, this link is the first result on Google for "bitcoin payment protocol":

https://github.com/bitcoin/bitcoin/pull/2539

Heh, thanks, I guess I should have Googled.

[maaku]

Mike, you're putting up strawmen with your insistence on Alan's original rationale(s). Authenticated, committed UTXO index structures provide a variety of new capabilities some of which Alan et al may not have anticipated. You seem to think these new capabilities are not useful, or at least do not justify their cost, for unstated reasons that you think are obvious. I disagree.

For example, it does matter how long it takes to bootstrap when you're talking about initial user experience, or a user who would prefer to run a full node but not halt operations while syncing. There's a wide variety of reasons people run bitcoin nodes, and I see any reason to expect the associated security requirements to neatly fall into one or two different models.

As for a selective DoS on Bloom filtering, no I haven't observed such a thing, nor have I been looking either. But that's completely beside the point: in the security business it is our job to act preemptively and close attack vectors, ideally before the black-hat work is done to exploit them. As to querying multiple nodes, you are ignoring network operators who could filter or replace protocol message. The index structure, on the other hand, would allow authenticated negative responses as well, so the querying node won't be happy until it receives a proof or presence OR absence.

No one's arguing for UTXO indices over bloom filters. They each have their uses.

[hazek]

Pieter has a full time job these days so it's harder for him to find the time, but even so, he's done amazing work on scalability and I'm sure he'll be able to finish off the pruning work some time this year

I just want it done already and not potentially see it run into a huge problem that could blow up in all of our faces when we'd most need the solution finished hence why I think it should have priority.

Quite often people on this forum claim that because I work for Google, I must have some incentive to try and centralise Bitcoin

I don't think that at all. What I do think is that working for Google has affected you, I'm sure you'll admit it changed how you view certain things, I mean how could it not.., and what I think is it affected you in such a way where your vision and priorities for Bitcoin and my vision and priorities for Bitcoin differ significantly. That's all. - And of course I could be completely off base here, something I'd be really happy to be corrected on.

[Mike Hearn]

I guess I have a few concerns with your utxo commitments project.

The first problem is that it still comes with the ultimate blockchain compression name. That's the reason I'm "insisting" on the original rationale. You've said yourself you know that's wrong and decided to keep it anyway - now look at the first posts in this thread. The name is misleading people into thinking it has something to do with reducing the disk space usage of running a full node. But because you don't actually have a full node if you start from a miner-consensus utxo set, that's not what it does. If you go ahead and rebuild the same database in parallel, that's fine, but unless pruning is implemented you'd eventually end up with the same disk space usage as today (well, more as you need space for the extra indexes).

The second problem is that you don't need to make these changes to have immediate initial startup. SPV wallets can already do the initial sync in a few seconds. If you want to run a full node too, just run both MultiBit and bitcoind in parallel until the latter is ready. If you want it to be seamless, just bundle bitcoind with a MultiBit and make it connect to your new local node once it's finished syncing. SPV+local full node = full node security, except that it's a very simple implementation, with the advantage that you can seamlessly switch back and forth afterwards.

I'm not actually convinced it's a good idea though. The user experience of having a full node randomly start syncing in the background because something decided you had enough cpu/disk space is very poor. If the user ever shuts down their app they'll be surprised to discover that next time they start it up, it's a long way behind and takes ages to catch up. If the user is going to make an explicit decision to run a full node, they can as well just download Bitcoin-Qt and run it themselves - that's really a tiny action compared to the ongoing cost of being a full node.

You say, start from a miner-majority commitment to a UTXO set and do full verification from that point on whilst bringing up a full node in parallel. But is this small window of time where you get marginally better security for the small number of users who would run a full node worth all the extra overhead? It doesn't feel like it. Building the full indexes needed to calculate all those merkle trees has quite some overhead and every node would have to do it, or at least every mining node. That would raise the cost of running a node and require us to redo all the scalability calculations that were already done.

The final issue I have is that you've raised a fair bit of money to work on it, but I didn't see where you got consensus that it should be merged into existing codebases. Perhaps I missed it, but I don't think Gavin said he  agreed with the necessary protocol changes. He may well have accepted your design in some thread I didn't see though.

[2112]

If you go ahead and rebuild the same database in parallel, that's fine, but unless pruning is implemented you'd eventually end up with the same disk space usage as today (well, more as you need space for the extra indexes).

I don't know if Mike Hearn doesn't know it or just pretends to doesn't know. But it clearly fits his pattern of producing misdirecting arguments. He applied nearly the same misdirection almost a year ago in the "[POLL] Multi-sig or scalability--which is more pressing?" thread.

https://bitcointalk.org/index.php?topic=94453.msg1046473#msg1046473

Full undo/redo logs for a UTxO database will indeed consume the same (or slightly higher) amount of storage as a raw blockchain storage. But unlike raw blockchain storage undo/redo logs are temporally clustered. The older and older transaction logs can be put in a slower and slower storage. All good DBMS-es have a way of efficiently backing up old transaction logs and restoring them on demand.

This isn't a place to repeat the same old set of arguments that led to creation of the database management systems as an efficient way to exploit temporal clustering in the data sets. Any decent DBMS textbook will have them.

[Peter Todd]

The final issue I have is that you've raised a fair bit of money to work on it, but I didn't see where you got consensus that it should be merged into existing codebases. Perhaps I missed it, but I don't think Gavin said he  agreed with the necessary protocol changes. He may well have accepted your design in some thread I didn't see though.

My conversations with Gavin in the past were that UTXO commitments and UTXO fraud proofs are a necessary precondition to raising the blocksize because without them you have no way of knowing if miners are committing inflation fraud and no way of proving that to others. Other core dev's like Gregory Maxwell share that opinion. If anyone succeeds in creating a robust implementation doing a PR campaign to educate people about the risks of not making it part of a blocksize increase is something I would be more than happy to be involved with, and I'm sure you realize it'll be an even easier message to get across than saying limiting the blocksize is a good thing.

Who doesn't want auditing, fraud prevention and fresh home-made all-American apple pie?

One catch is that unfortunately UTXO commitments are in themselves very dangerous in that they allow you to safely mine without actually validating the chain at all. What's worse is there is a strong incentive to build the code to do so because that capability can be turned into a way to do distributed mining, AKA P2Pool, where every participate has low bandwidth requirements even if the overall blockchain bandwidth requirement exceeds what the participants can keep up with. If miners start doing this, perhaps because mining has become a regulated activity and people want to mine behind Tor, it'll reduce the threshold for what is a 51% attack by whatever % of hashing power is doing mining without validation; we're going to have to require miners to prove they actually posses the UTXO set as part of the UTXO-commitment system. That said I'm pretty sure it's possible to allow those possession proofs to be done in a way where participants can maintain only part of the UTXO set, and thus part of the P2P relay bandwidth, allowing low-bandwidth true mining + larger blocksizes without decreasing the 51% attack threshold and helping solve the censorship problem and keeping thus Bitcoin decentralized. The devil is in the details, but at worst it can be done as a merge-mined alt-coin.

Of course that still doesn't solve the fundamental economic problem that there needs to be an incentive to mine in the first place, but an alt-coin with sane long-term economic incentives (like a minimum inflation rate) can always emerge from Bitcoin's ashes after Bitcoin is destroyed by 51% attacks and such an alt-coin can be bootstrapped by having participants prove their possession or sacrifice of Bitcoin UTXO's to create coins in the "Bitcoin 2" alt-coin, providing a reasonable migration path and avoiding arguments about early-adopters. Similarly adding proof-of-stake to the proof-of-work can be done that way. (note that proof-of-stake may be fundamentally incompatible with SPV nodes; right now that's an open research question) None of this is an issue in the short-term anyway as the subsidy inflation won't hit 1% until around 2032 by the very earliest, even later than that in real terms depending on how many coins turn out to be lost. Applications like fidelity bonds and merge-mined alt-coins that all subsidize mining will help extend the economics incentives to mine longer as well.

Yes, I'm less worried about the blocksize question these days because I'm fairly confident there can exist a decentralized cryptocurrency in the future, but I don't know and don't particularly care if Bitcoin ends up being that currency. I'll also point out that if Bitcoin isn't that currency, the alt-coin that is can be created in a way that destroys Bitcoin itself, for instance by making the PoW be not only compatible with Bitcoin, but by requiring miners to create invalid, or better yet, valid but useless Bitcoin blocks so that increased adoption automatically damages Bitcoin. For instance a useless block can be empty, or just filled with low or zero fee transactions for which the miner can prove they posses the private keys too; blocking non-empty blocks would require nodes to not only synchronize their mempools but also adopt a uniform algorithm for what transactions they must include in a block for the block to be relayed and any deviation there can be exploited to fork Bitcoin. (another argument for requiring miners to prove UTXO set possession) Also note how a 51% attack by Bitcoin miners on the alt-coin becomes an x% attack on Bitcoin. Sure you can mess with the Bitcoin rules to respond, but it becomes a nasty cat-and-mouse game...

[d'aniel]

For fraud proofs, I think d'aniel raised that before, I'm afraid I don't remember which proofs require the commitments. Double spends don't. At any rate, whilst those proofs would indeed be useful they weren't the rationale given for "ultimate blockchain compression" originally. A full design doc for different kinds of fraud proofs would be useful.

Actually, none of the fraud proofs/challenges I mentioned in that thread relied on utxo set commitments.  Transactions with nonexistent txins would benefit from them, since then there could be concise proofs of nonexistent txins, but the way I described it, a peer would issue a challenge to find a valid Merkle branch to an allegedly nonexistent txin from some other peer.  If at least one peer is honest (which Bitcoin generally assumes anyway), then they will find the branch if the challenger turned out to be lying, and can ignore that him going forward.

Partially verifying nodes is what I ended up being interested in utxo set commitments for, and they seem to be really useful if/when we get efficient verifiable computing.  Though there definitely isn't any near-term need for this.

[Peter Todd]

For fraud proofs, I think d'aniel raised that before, I'm afraid I don't remember which proofs require the commitments. Double spends don't. At any rate, whilst those proofs would indeed be useful they weren't the rationale given for "ultimate blockchain compression" originally. A full design doc for different kinds of fraud proofs would be useful.

Actually, none of the fraud proofs/challenges I mentioned in that thread relied on utxo set commitments.  Transactions with nonexistent txins would benefit from them, since then there could be concise proofs of nonexistent txins, but the way I described it, a peer would issue a challenge to find a valid Merkle branch to an allegedly nonexistent txin from some other peer.  If at least one peer is honest (which Bitcoin generally assumes anyway), then they will find the branch if the peer turned out to be lying, and can ignore that peer going forward.

Yeah, you can go very far without UTXO set commitments, but without them your scenario only works if you assume your peers are full-nodes. If you are an SPV node with SPV peers - a completely valid scenario that we will need in the future and one that is useful with payment protocols - you're stuck and can't do anything with the fraud proofs.

The other issue is that only UTXO set commitments can prove inflation fraud without a copy of the blockchain, IE miners deciding to changing the subsidy and fee rules and create coins out of thin air.

[maaku]

Actually, none of the fraud proofs/challenges I mentioned in that thread relied on utxo set commitments.  Transactions with nonexistent txins would benefit from them, since then there could be concise proofs of nonexistent txins, but the way I described it, a peer would issue a challenge to find a valid Merkle branch to an allegedly nonexistent txin from some other peer.  If at least one peer is honest and the network operator (which Bitcoin generally assumes anyway), then they will find the branch if the challenger turned out to be lying, and can ignore that him going forward.

Fixed that for you. Without nonexistance proofs, network operator attacks are trivial.

[d'aniel]

Yeah, you can go very far without UTXO set commitments, but without them your scenario only works if you assume your peers are full-nodes. If you are an SPV node with SPV peers - a completely valid scenario that we will need in the future and one that is useful with payment protocols - you're stuck and can't do anything with the fraud proofs.

I don't follow.  How could an SPV node function with only SPV peers?  How would it get the tx data that it needs?

The other issue is that only UTXO set commitments can prove inflation fraud without a copy of the blockchain, IE miners deciding to changing the subsidy and fee rules and create coins out of thin air.

I addressed this as well in that thread: https://bitcointalk.org/index.php?topic=131493.msg1407971#msg1407971.  The Merkle tree of transactions is used to authenticate the maximum fee reward calculation in each block.  It didn't seem to require utxo set commitments.

[d'aniel]

Actually, none of the fraud proofs/challenges I mentioned in that thread relied on utxo set commitments.  Transactions with nonexistent txins would benefit from them, since then there could be concise proofs of nonexistent txins, but the way I described it, a peer would issue a challenge to find a valid Merkle branch to an allegedly nonexistent txin from some other peer.  If at least one peer is honest and the network operator (which Bitcoin generally assumes anyway), then they will find the branch if the challenger turned out to be lying, and can ignore that him going forward.

Fixed that for you. Without nonexistance proofs, network operator attacks are trivial.

Okay, so the network operator could mislead a node onto his invalid chain by handing it fake fraud challenges.  Can't he do this regardless, by simply refusing to relay valid block headers?