Pages:
Author

Topic: Ultimate blockchain compression w/ trust-free lite nodes - page 15. (Read 87932 times)

hero member
Activity: 501
Merit: 500
I tried to read the OP again and I have a question. I apologize for the fact that I'm not very Bitcoin-literate and I may be asking things that are obvious.

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Or is there a zero-trust way for a full node to assure the lite-node that a TxOut hasn't been spent since the last altchain block that does not require the lite node to ever download full primary-chain blocks?

Of course if we drop the zero-trust requirement, it's trivial to set up a third party service that does the validation for the lite clients up to the last alt-chain block.
jr. member
Activity: 33
Merit: 7
Without being too snarky, we have such an index: it's called the block chain. A full node would send the transaction in which it was spent, the block header that transaction was included in, and the path through the transaction Merkle-tree linking the two.

Now in the far, distant future it might be useful to have an index of block hashes so that the lite node doesn't even have to keep track of that information, but right now the overhead of maintaining that tree vs the storage cost (about ~1.25MB per year) doesn't make sense.

Yes indeed, you're quite right, my worry was groundless. Well then, this is really exciting, the road to a secure lightweight client is open and clear!
legendary
Activity: 905
Merit: 1012
Without being too snarky, we have such an index: it's called the block chain. A full node would send the transaction in which it was spent, the block header that transaction was included in, and the path through the transaction Merkle-tree linking the two.

Now in the far, distant future it might be useful to have an index of block hashes so that the lite node doesn't even have to keep track of that information, but right now the overhead of maintaining that tree vs the storage cost (about ~1.25MB per year) doesn't make sense.
jr. member
Activity: 33
Merit: 7
It would be a bit different than that. Rather than saying "spent" it would say and prove "not unspent".

The way it would do this is by sending the leaf nodes immediately surrounding where the unspent tx would go IF it existed, along with Merkle lineage. This would be like me proving to you there are no "fockheads" in the phone book by sending you the pages immediately surrounding "fockhead" alphabetically (e.g. Freitag thru Foster). This assumes everything is kept in a sorted order, and that is what is proposed in this thread.


Ah, of course! Thanks for the explanation.

Perhaps a record of spent txouts would still be of some value, to cover the case where a light client wants to query a full node with "prove to me how (i.e. into what tx) this txout was spent"? (But then again, maybe the need (if any) for such a query type would be sufficiently rare and specialized that running a full node oneself can be deemed the reasonable way to meet such an "expert" need.)
legendary
Activity: 2282
Merit: 1050
Monero Core Team

It's also useful for instantly screening an incoming unconfirmed transaction as being "good pending confirmation" versus "totally bogus and no chance of confirmation" without needing a block chain at all.

It's also useful not just for physical bitcoins, but if people start printing disposable bitcoin cash from their printer. (example: user clicks File -> Print Money to "be their own bank" instead of driving to an ATM and paying an ATM fee - something I see as wildly compatible with the average joe.  such self-printed bills would have the same requirements as physical bitcoins). 

Basically any situation where one needs to prove what the balance is in a particular bitcoin address without actually spending the coins in that address.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
It would be a bit different than that. Rather than saying "spent" it would say and prove "not unspent".

The way it would do this is by sending the leaf nodes immediately surrounding where the unspent tx would go IF it existed, along with Merkle lineage. This would be like me proving to you there are no "fockheads" in the phone book by sending you the pages immediately surrounding "fockhead" alphabetically (e.g. Freitag thru Foster). This assumes everything is kept in a sorted order, and that is what is proposed in this thread.
jr. member
Activity: 33
Merit: 7
Apologies if this is a stupid question, but... would it not also be of benefit to make available, by the same sort of methods, a record of all the spent txouts? I'm thinking of how things can go when a future light client is querying (in untrusting style) a full client node - perhaps in exchange for a micropayment, or a subscription or whatever - about whether various txouts are spent or unspent. Here's an anthropomorphized dialogue. (Obviously the number of rounds back and forth is higher than it needs to be, just for the sake of anthropomorphizing the exchange.)

Light client (LC): hi, is this txout (.....) spent or unspent?
Full client (FC): unspent.
LC: ...and your proof? (I don't trust you, remember!)
FC: here's the merkle chain [or similar thing for whatever the data structure is exactly] leading from your txout to the root hash, which you can acquire from the network with suitably impressive [merged-]mining effort associated therewith. (transmits a pleasantly short merkle chain)
LC: ok, thanks very much! now, what about this txout: spent or unspent?
FC: spent.
LC: ...and your proof?
FC: well, uh, the proof is the fact that I'm not sending you a merkle chain like I did with the unspent one!
LC: sorry, but that's not a proof from my point of view!

With a record of spent txouts, the FC can send a merkle chain convincing the untrusting LC of a txout's spent status, rather than having to say "trust my absence-of-proof-of-unspent to mean it's spent".

(Maybe this is overkill? The FC could just send the transaction which spends the given txout. But maybe that was a transaction that "died" (failed to be bedded down in the winning blockchain) long ago, and for the FC to send it is misleading. Admittedly, the main reason for such "dyings" is losing a double-spending battle, in which case the relevant txout is likely still in fact spent, just not by the transaction the FC is advertising. But one can imagine scenarios where the LC wants proof not just of spent status, but of where it went, and a suitable data structure could support a reply of "it's spent, and here's the tx it went into, and here's a pleasantly short merkle chain establishing this".)
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
The fact that the correct data is pruned is secured on a second blockchain with merged mining. I can see the point of this for certain applications such as verifying the integrity of a physical Bitcoin without actually opening it up and spending the funds. So there is an advantage in that respect over the proposal in Bitcoin: A Peer-to-Peer Electronic Cash System.

It's also useful for instantly screening an incoming unconfirmed transaction as being "good pending confirmation" versus "totally bogus and no chance of confirmation" without needing a block chain at all.

It's also useful not just for physical bitcoins, but if people start printing disposable bitcoin cash from their printer. (example: user clicks File -> Print Money to "be their own bank" instead of driving to an ATM and paying an ATM fee - something I see as wildly compatible with the average joe.  such self-printed bills would have the same requirements as physical bitcoins). 
legendary
Activity: 2282
Merit: 1050
Monero Core Team
Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?

The subsequent block hashes don't tell you whether or not the funds are spent.  The only way you know funds are spent is that you know of a transaction that spends it.  There is no present way to know that certain funds are NOT spent unless you have the whole block chain coming after that transaction.

Remember, the goal is to eliminate a boundless multi-gigabyte download for new users.  The only way to solve that is to remove some information from that data set so it is smaller.  The party receiving the reduced data set can be assured that the data that's there actually belongs there, but he has no way to know whether the missing (pruned) data was actually supposed to be pruned.  This proposal addresses that.

The fact that the correct data is pruned is secured on a second blockchain with merged mining. I can see the point of this for certain applications such as verifying the integrity of a physical Bitcoin without actually opening it up and spending the funds. So there is an advantage in that respect over the proposal in Bitcoin: A Peer-to-Peer Electronic Cash System.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?

The subsequent block hashes don't tell you whether or not the funds are spent.  The only way you know funds are spent is that you know of a transaction that spends it.  There is no present way to know that certain funds are NOT spent unless you have the whole block chain coming after that transaction.

Remember, the goal is to eliminate a boundless multi-gigabyte download for new users.  The only way to solve that is to remove some information from that data set so it is smaller.  The party receiving the reduced data set can be assured that the data that's there actually belongs there, but he has no way to know whether the missing (pruned) data was actually supposed to be pruned.  This proposal addresses that.
legendary
Activity: 2282
Merit: 1050
Monero Core Team
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.

Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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.
legendary
Activity: 2282
Merit: 1050
Monero Core Team
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?
hero member
Activity: 668
Merit: 501
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.
legendary
Activity: 1596
Merit: 1100
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.

hero member
Activity: 668
Merit: 501
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.
hero member
Activity: 868
Merit: 1000
Hello,

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

I didn't see much activity on the mailing list?
hero member
Activity: 501
Merit: 500
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.
sr. member
Activity: 389
Merit: 250
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.
legendary
Activity: 905
Merit: 1012
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.
Pages:
Jump to: