Ultimate blockchain compression w/ trust-free lite nodes

[etotheipi]

The number one problem that this solves (besides blockchain pruning) is one of trust.  When a new node gets on the network right now, there are two options:

(1) Run a full node, with full blockchain, ultimate security -- verify everything in the blockchain yourself
(2) Run a lightweight node, with reduced level of security -- trust that someone else gave you your own correct balance, and have no way to check whether transactions are valid, especially zero-conf tx

With this meta-chain in place, you can run (1) for a lot less disk space, and (2; lightweight nodes) can achieve the ultimate security model without needing to hold the full chain.  I can verifiably import my own wallet knowing nothing but the headers and verify it directly against the blockchain.  If someone gives me a zero-conf tx, I can check not only that its inputs exist, but that the inputs haven't been spent yet.  Zero-conf tx should not really be trusted, anyway... but at least you can verify whether it's even possible for the network to accept it, which what a full node does.

[Serith]

If someone gives me a zero-conf tx, I can check not only that its inputs exist, but that the inputs haven't been spent yet.  Zero-conf tx should not really be trusted, anyway... but at least you can verify whether it's even possible for the network to accept it, which what a full node does.

I posted an idea about how to make 0-conf tx safe. There was some discussion, and the idea wasn't killed so far, but there wasn't much of an interest either, so I am starting to believe that there is no need in 0-conf tx.

[casascius]

I posted an idea about how to make 0-conf tx safe. There was some discussion, and it wasn't killed so far, but there wasn't much of an interest either, so I am starting to believe that it's not something demanded.

I think when one of the core developers immediately points out how it can be used to reliably defraud somebody, that makes it pretty much DOA.  But I would propose that there is indeed demand for a reliable zero-confirmation transaction.

[etotheipi]

I posted an idea about how to make 0-conf tx safe. There was some discussion, and it wasn't killed so far, but there wasn't much of an interest either, so I am starting to believe that it's not something demanded.

I think when one of the core developers immediately points out how it can be used to reliably defraud somebody, that makes it pretty much DOA.  But I would propose that there is indeed demand for a reliable zero-confirmation transaction.

I hate bringing up zero-conf tx in general, because there are so many issues with them that they are useful only in isolated cases, usually partial-trust situations.  I guess, this shouldn't be seen as a driving force for implementing this proposal, but more seen as an example of how much verifiable information can be obtained from the network with minimal download.  It's fast enough that a light node could obtain as much information about a zero-conf tx as a full-node, with just a few kB downloaded.  Regardless of how that information is used, it's a huge functional advantage from where we are currently.

[Serith]

I posted an idea about how to make 0-conf tx safe. There was some discussion, and it wasn't killed so far, but there wasn't much of an interest either, so I am starting to believe that it's not something demanded.

I think when one of the core developers immediately points out how it can be used to reliably defraud somebody, that makes it pretty much DOA.  But I would propose that there is indeed demand for a reliable zero-confirmation transaction.

I believe he was wrong, at least no one objected when I explained why it is not a problem, a basic double spend check from a pool completely solves it. And if you are agree with him could you elaborate your opinion here or in the thread? The good thing about the idea is that it has the same property as etotheipi's proposal of how non-disruptive it is. It doesn't require any changes in Bitcoin, just collaboration between 2 or 3 major pools.

I pay you normally without using this system, then use the pool-signed txn to pay myself in a doublespend.  It would make attacks very reliable.

A pool must check if there is any conflicting transaction already present and if true then refuse to sign the multi-signature transaction.

[casascius]

Instead of saying your idea is wrong, maybe I can contribute to it.

One of the things gmaxwell pointed out was that mining pools may be around now but there is no guarantee they will be around later, in fact he thinks they probably won't. So depending on them as fundamental architecture is probably a bad idea all around.

But imagine miners (both solo and pools) included a IP:Port calling card in the coinbase of their block. The calling card would convey the message: I am a miner, you can contact me via udp directly at (ip:port), send me your transaction, and if it looks valid, I will give you a signed promise (signed by coinbase key) that I accept and plan to confirm this transaction.

One would know what percentage of the mining pool any given calling card represents just by the number of recent blocks containing it.

Someone wanting a miner commitment on a transaction would blast out that transaction via UDP to all of the miners whose calling cards appear in the last 1000 blocks.  That sounds extreme, but we're only talking a few hundred kilobytes total, with the total going to each miner being under 1-2KB.

By using UDP instead of TCP, one could blindly blast out a bunch of simultaneous requests into the internet on a "best effort" basis with low overhead, knowing most of them will arrive and many won't and that that's OK.  The responses would arrive the same way.

Either the sender or the recipient of a transaction could immediately contact thousands of miners with a blast of udp packets and rapidly get an accurate feel for how much mining power supporting the transaction has just by gauging the udp responses that come back within the following 10 seconds.

If it is a supermajority you have success.

Such could be the standard practice for accepting zero conf transactions.  It could be an excellent revenue generator for the mining community as a whole in the form of a for-pay service (example, all miners could stipulate that this UDP confirmation service is only available if transaction fee [in the transaction being zero-confirmed] is meets a far more generous criterion than the satoshi client minimum)

To address gmaxwell's rightfully placed fear that I could pay "you" and then use the premium service to pay the doublespend to myself... if getting zero-conf is a fee-based service paid by the payer, then "you" could demand, as a condition of giving me goods with zero conf, that I include a fee big enough to ensure that you can click a button in your client and enjoy the confirmation service yourself, prepaid.

[Serith]

Instead of saying your idea is wrong, maybe I can contribute to it.

One of the things gmaxwell pointed out was that mining pools may be around now but there is no guarantee they will be around later, in fact he thinks they probably won't. So depending on them as fundamental architecture is probably a bad idea all around.

But imagine miners (both solo and pools) included a IP:Port calling card in the coinbase of their block. The calling card would convey the message: I am a miner, you can contact me via udp directly at (ip:port), send me your transaction, and if it looks valid, I will give you a signed promise (signed by coinbase key) that I accept and plan to confirm this transaction.

One would know what percentage of the mining pool any given calling card represents just by the number of recent blocks containing it.

Someone wanting a miner commitment on a transaction would blast out that transaction via UDP to all of the miners whose calling cards appear in the last 1000 blocks.  That sounds extreme, but we're only talking a few hundred kilobytes total, with the total going to each miner being under 1-2KB.

By using UDP instead of TCP, one could blindly blast out a bunch of simultaneous requests into the internet on a "best effort" basis with low overhead, knowing most of them will arrive and many won't and that that's OK.  The responses would arrive the same way.

Either the sender or the recipient of a transaction could immediately contact thousands of miners with a blast of udp packets and rapidly get an accurate feel for how much mining power supporting the transaction has just by gauging the udp responses that come back within the following 10 seconds.

If it is a supermajority you have success.

Such could be the standard practice for accepting zero conf transactions.  It could be an excellent revenue generator for the mining community as a whole in the form of a for-pay service (example, all miners could stipulate that this UDP confirmation service is only available if transaction fee [in the transaction being zero-confirmed] is meets a far more generous criterion than the satoshi client minimum)

To address gmaxwell's rightfully placed fear that I could pay "you" and then use the premium service to pay the doublespend to myself... if getting zero-conf is a fee-based service paid by the payer, then "you" could demand, as a condition of giving me goods with zero conf, that I include a fee big enough to ensure that you can click a button in your client and enjoy the confirmation service yourself, prepaid.

I agree with you and the second part of gmaxwell's post, that my proposal brings more centralization, and that's not ideal. You are thinking about making 0-confirmation tnx accepted in decentralize or less centralized way, that would be great if it's possible. I see problems with your proposal, but I am not ready to discuss it yet.

I think we are derailing etotheipi's thread so I made a copy of the post in my thread.

[eldentyrell]

Trustless lightweight-node support

It doesn't seem trustless to me. Lightweight nodes (not storing all unspent outputs) can't know whether a block is valid, so they need to trust the majority of the network's mining power. This is no more secure than SPV, though possibly a little easier for lightweight nodes.

This is a subtle but important point.  A while back I wrote a section about it on the bitcoin wiki.  The Satoshi client never uses "number of blocks deep" as a measure of confidence that a transaction is valid.  Depth is used only as a measure of the likelihood of another, longer chain branch emerging that omits the transaction.

A truly trustless thin client needs to be able to be able to verify a recent block's height (that there really are 180,000 blocks before this one and they obey the max-4x-difficulty-adjustment rule) rather than its depth (that there really were 6 blocks built on top of it -- also known as confirmations).

It's possible to do height verification probabilistically without 2GB of disk+download, but you need more than a tree-of-unspent-transactions to do it -- the block chain has to look more like an upside-down tree or DAG (most recent block is the root) giving you multiple hash-secured O(log n)-long paths from any block to the genesis block.  These "shortcut ancestor links" can be added without 51% agreement.  If each challenge consists of the thin client picking the log(n)-long path and the server replying with the block headers along that path, it doesn't take many challenges or much time/bandwidth/space to drive the probability-of-being-snookered down to something well below the probability of your hardware randomly failing.  Once you have block height verification you can be truly trustless -- or, at least as trustless as the Satoshi client.

[galambo]

This is a subtle but important point.  A while back I wrote a section about it on the bitcoin wiki.  The Satoshi client never uses "number of blocks deep" as a measure of confidence that a transaction is valid.

A truly trustless thin client needs to be able to be able to verify a recent block's height (that there really are 180,000 blocks before this one and they obey the max-difficulty adjustment rules) rather than its depth (that there really were 6 blocks built on top of it -- also known as confirmations).

It's possible to do height verification probabilistically without 2GB of disk+download, but you need more than a tree-of-unspent-transactions to do it -- the block chain has to look more like a tree giving you multiple hash-secured O(log n)-long paths from any block to the genesis block).  These "shortcut ancestor links" can be added without 51% agreement.

How will the lightweight node know the path hashes are incorrect and to reject that part of a block?

I can see how the thick clients can verify this, but an incorrect path would require all of the thick clients to reject the block if it contained a false path. I think this means another protocol decision point like P2SH.  Otherwise, we'd have ignorant thick clients forwarding malicously crafted "tree transactions" to the light clients.

This isn't meant to be a gotcha. I like your idea (a lot), but I'd like some clarification. I've only started looking into this part of Bitcoin and I'm not a very big data structures guy.

I also don't understand why you think these could be added without the "51%."

[eldentyrell]

How will the lightweight node know the path hashes are incorrect and to reject that part of a block?

All of these "links" are hashes -- they're self-validating just like the previous-block (prevblock) hash that Bitcoin currently uses.  These are just "extra prevblock pointers", but they're in the coinbase instead of in the headers and they point to an arbitrary ancestor instead of the immediate predecessor.  I'll call these new pointers non-prevblock pointers to distinguish them from the pointers we already have.

I can see how the thick clients can verify this, but an incorrect path would require all of the thick clients to reject the block if it contained a false tree.

I definitely do not propose adding any new block validity criteria.  You're right: hostile miners can add blocks with broken non-prevblock pointers.

Otherwise, we'd have ignorant thick clients forwarding malicously crafted "tree transactions" to the light clients.

If a hostile miner gets a block with broken non-prevblock pointers into the chain, it will amount to -- at worst -- a DOS attack on thin clients until the next block is found by friendly miners.  As long as the hostile block is at the top of the chain, all thin clients will believe that all servers are lying to them.  But they won't be compromised -- they'll simply twiddle their thumbs saying "Nobody has been able to convince me of what reality ought to look like".

As soon as the next {non-prevblock-pointer}-aware miner finds a block, they will add a block which refrains from creating any new paths through the malicious block.  Thin clients resume operation as normal.  In effect, blocks with broken non-prevblock pointers get excluded from the "DAG-within-the-blockchain".

Thin clients which were connected before the malicious block arrived won't be affected.

There are ways to make the cost of the DOS attack above very large (like >99% hashpower) but they add complexity.  

I think this means another protocol decision point like P2SH.

Definitely not!  I believe the trustless thin client problem can be solved without another hardfork (or even miners-only fork).

I also don't understand why you think these could be added without the "51%."

Right, so, suppose I control 1% of the network hashpower.  That means I create 1% of the blocks.  If the radix of the non-prevblock-pointer tree is, say, 200 (i.e. each block can have 200 non-prevblock pointers) that means that my block will be reducing the average path length in the tree more rapidly than the other 99% of the network is adding new blocks.  So the average path length will gradually converge to log(height), even if only 1% of the miners are adding the new pointers -- it's just that each block they add has to include more than 100 new pointers.  Of course, the more miners you have the more rapidly we get to the ideal log(height) situation…

[eldentyrell]

If each challenge consists of the thin client picking the log(n)-long path and the server replying with the block headers along that path, it doesn't take many challenges or much time/bandwidth/space to drive the probability-of-being-snookered down to something well below the probability of your hardware randomly failing.

By the way, since these servers are full clients they could charge thin clients some tiny amount like 0.00000001 BTC per challenge, giving people an incentive to run full-chain clients on machines with big disks.

Thin clients should use whichever server they are able to contact that has failed the fewest challenges (an honest server will only fail challenges if there is a hostile block at the top of the chain).  Bad guys could run a server without a blockchain that just spews back junk answers, but they'd only get one challenge per thin client and then be promptly ignored -- not enough money to be worth the trouble.

[maaku]

Over in the altchain section I announced a crowd funding campaign for a demurrage currency. If we reach our goal, one of the things we will do is fully implement etothepi's proposal, either in Armory or the official client, and back-port the changes to Bitcoin.

Although relevant, I don't want to spam the forum, so this will be my only cross-post regarding it.

[btharper]

Sub, and I think I'll have to reread everything already, I'm not sure there's one post with a full description anymore, just a lot of ideas that have been getting pieced together. Not to say that's bad, I just need to make sure I can parse out the current "best" proposal.

[mp420]

I think this, and other related proposals, are the only ones around that are really taking scalability seriously. I haven't really gotten my head around the specifics yet, but the thing I really like about this proposal is that it requires no changes in the "Bitcoin Proper" at all.

I really hope this goes forward.

[unclescrooge]

Hello,

Did the developers reach an agreement on how to prune the blockchain?

I didn't see much activity on the mailing list?

[apetersson]

i think right now we need an experimental implementation to see how this approach would perform in practice.

IMO, the ideas outlined by etotheipi are the right way to go for a tiered bitcoin network, and for better scalability.

[jgarzik]

Did the developers reach an agreement on how to prune the blockchain?

sipa has been working on his "ultraprune" branch at github.  It is discussed on IRC.

[apetersson]

sipa has been working on his "ultraprune" branch at github.  It is discussed on IRC.

the prunig efforts are nice and will lead to much faster desktop clients and full nodes, but they do not really solve the problem of very light nodes trying to obtain their bitcoin balance and transaction history from the network quickly.

[ArticMine]

Before commenting on this thread I reviewed Satoshi Nakamoto's original paper: Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org/bitcoin.pdf, and I am left with two questions:

1) How is this proposal better or worse than 7. Reclaiming Disk Space in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to overall blockchain size management?
2) How is this proposal better or worse than 8. Simplified Payment Verification in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to verifying payments?

[casascius]

Before commenting on this thread I reviewed Satoshi Nakamoto's original paper: Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org/bitcoin.pdf, and I am left with two questions:

1) How is this proposal better or worse than 7. Reclaiming Disk Space in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to overall blockchain size management?

This works as a way to reclaim disk space provided you are starting with the whole block chain, but as presented, there is no way for one node to convey that stubbed tree to another node along with the assurance that only spent transactions have been removed.  If I run a node that prunes and stubs off a transaction showing I spent some coins, and then send you that pruned block, my spent coins look unspent to you.

Since it's a solution that's only useful to a node with the full block chain, and the real problem we face is more the downloading of the block chain rather than storing it, a solution that requires a full block chain download before anything can be safely pruned doesn't address the problem.

2) How is this proposal better or worse than 8. Simplified Payment Verification in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to verifying payments?

That proposal suggests spending the funds and then watching to see if the rest of the network confirms the spend into a block before any useful verification is possible, or freshly receiving the funds while watching new blocks.  The idea discussed in this thread would allow instant verification of the existence of pre-existing funds without having to spend them first or downloading any blocks at all - and is actually not a different proposal, but the same proposal with significant improvements.