Bitcoin Forum
December 05, 2016, 02:55:26 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3]  All
  Print  
Author Topic: Pledging coins for ultimate blockchain compression  (Read 5746 times)
justusranvier
Legendary
*
Offline Offline

Activity: 1400



View Profile WWW
March 10, 2013, 04:58:18 PM
 #41

The goal of UBC is to remove the requirement to choose between running a light node and acting as a first class network citizen.

The minimum amount of data needed to verify blocks and transactions is the UTXO set. The thread linked in the OP is a discussion about the best data structure for storing the UTXO set, with the goal of eventually including it into the block definition. If this is accomplished nodes could discard all prunable data, except for enough recent history to handle reorgs, but could still perform the network functions a reference node can perform now (except a full blockchain download).
1480949726
Hero Member
*
Offline Offline

Posts: 1480949726

View Profile Personal Message (Offline)

Ignore
1480949726
Reply with quote  #2

1480949726
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480949726
Hero Member
*
Offline Offline

Posts: 1480949726

View Profile Personal Message (Offline)

Ignore
1480949726
Reply with quote  #2

1480949726
Report to moderator
1480949726
Hero Member
*
Offline Offline

Posts: 1480949726

View Profile Personal Message (Offline)

Ignore
1480949726
Reply with quote  #2

1480949726
Report to moderator
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
March 10, 2013, 05:07:49 PM
 #42

There have been lots of discussion with the devs, though the most interesting ones I've had were on IRC.  The biggest concern was expressed by gmaxwell, which was that he doesn't see it being acceptable to further expand the computational requirements of miners, despite the benefits that are offered by this idea.  It risks creating further centralization, when miners with less-powerful hardware are pushed out.  That doesn't mean it couldn't exist in a side-chain, it just means that he doesn't think it could ever be accepted into the core protocol -- which I think would be a desirable goal for this in the long term.
Does gmaxwell still think this?  I've noticed lately he seems keen on the idea:
https://bitcointalk.org/index.php?topic=88208.msg1599126#msg1599126
https://bitcointalk.org/index.php?topic=137933.msg1599093#msg1599093

It's also in his alt-coin wishlist: https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas

I'm thinking he may have changed his mind because of its application to partial verification and fraud proofs.  Essentially this can be seen as part of an overall SPV trust model upgrade.  He explains this well in this post: https://bitcointalk.org/index.php?topic=137933.msg1596626#msg1596626
Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
March 11, 2013, 10:13:30 AM
 #43

Quote
The goal of UBC is to remove the requirement to choose between running a light node and acting as a first class network citizen.

The minimum amount of data needed to verify blocks and transactions is the UTXO set. The thread linked in the OP is a discussion about the best data structure for storing the UTXO set, with the goal of eventually including it into the block definition. If this is accomplished nodes could discard all prunable data, except for enough recent history to handle reorgs, but could still perform the network functions a reference node can perform now (except a full blockchain download).

All you've done in the second paragraph is describe how the Bitcoin-Qt app currently works. If you're maintaining a full copy of the UTXO set and verifying signatures, etc, then you're a full node by definition because you aren't relying on the majority consensus for anything except ordering.

It isn't feasible to do this in the places lightweight clients are currently used. It doesn't make sense to run a full node on a phone, for example, and as traffic ramps up it'll stop making sense to do it on laptops as well.

This is why I don't understand the proposal. The only reasonable way I've seen to get something in between SPV and full mode is d'aniels suggestions for various kinds of fraud proofs, but the whole point of a fraud proof is that you get one when the best chain is no longer following the rules .... making fraud proofs that rely on trusted commitments to the state of the UTXO set pointless (they would be a part of the fraud).
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
March 11, 2013, 10:47:35 AM
 #44

The only reasonable way I've seen to get something in between SPV and full mode is d'aniels suggestions for various kinds of fraud proofs, but the whole point of a fraud proof is that you get one when the best chain is no longer following the rules .... making fraud proofs that rely on trusted commitments to the state of the UTXO set pointless (they would be a part of the fraud).
The SPV clients would be auditing commitments to the UTXO set as well, of course.

Edit: One way I can see to do this is for each block, full nodes keep handy all the branches of the UTXO tree that get updated in the next block.  If they're pruning, then they only have to keep this data a reasonable ways back in the chain.  To audit commitments to the UTXO set in a given block, an SPV node would download transaction merkle branches in this block and the relevant branches in the UTXO tree from the previous block, then check that the commits were done properly, i.e. produce the correct root to the current UTXO tree.
etotheipi
Legendary
*
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
March 13, 2013, 10:16:41 PM
 #45

The final step of this project is "integrate with lightweight clients", but this is vague - what does it mean? Which clients?

Mike,

I can't tell if you misunderstood/didn't-read the UBC thread, or if you have understood it, picked it apart, and 12 steps ahead of me in considering the dynamics of it (and decided you don't like it).  I'll assume the former...

No one has to use it.  I don't think "integrate with lightweight clients" is a goal for the developer here, other than integrating it somewhere to demonstrate its benefits.  With the addition of subtree-sums in the data structure, it appears to solve even more problems than I originally posted.

I continue to be hounded by Armory users complaining of how long it takes to rescan the blockchain when they restore their wallet, or import a key.  I could ask another node for that information ... but there's no guarantee they tell me the truth, or that they even have the information.  So, I am at a trade-off between downloading some non-negligible part of the blockchain myself, just to make sure I know how to spend my coins, or accept the risk of other nodes playing game with me just so I can make a "simple" client.  And the users are making the same decision when deciding which client to use. 

But with this, there is no trade-off.  The simple client only needs the headers, and then about 2 kB/address to get a fully verifiable, spendable balance directly linked to the chain with the most work.  If the program saves the headers, it could save nothing else between loads, and redownload its own balance information every time for less than 1MB and without sacrificing security.  It would frequently be much less data than downloading hundreds of blocks since my device was last running, and more secure than trusting that nodes are filtering properly for me.  There is no more "rescanning" the blockchain.  No "searching" for your UTXOs.  You just get them, and it's easy for any to prove inclusion or exclusion of existing or non-existent UTXOs at any block.

In essence, forcing full nodes to maintain this "service" isn't just an upgrade, it changes the network in a positive way.  It means SPV doesn't even really exist anymore, you just have miners and you have secure-non-full-nodes that can run on just about any device.



Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
March 14, 2013, 12:50:19 PM
 #46

Well, you're right, I haven't understood your proposal. And I still don't Sad

Firstly I'm not sure I understand the rationale. Restoring a wallet or importing keys should be a very rare event. I'd hope that people don't need to restore from backup all that often, so optimizing for it is a bit puzzling. Perhaps they are doing this to satisfy some other use case that can be tackled in a better way.

But regardless, I don't see how implementing this proposal changes anything. With current SPV code the bottleneck in re-scanning the chain is how fast the blocks can be loaded off disk and scanned on the remote node side. The client itself only receives headers, merkle branches and the transactions it needs (along with a few false positives if it wants them). To make it faster still you don't need to put any new data into blocks, you can have additional indexes be created by nodes that want to offer that service so they can avoid loading/scanning blocks that don't contain any matching transactions. It's a protocol transparent upgrade, beyond maybe an addr service flag.

But I'm not sure that's really so important right now. BitcoinJ + an unloaded Bitcoin 0.8 node can scan through the latest parts of the chain at many hundreds of blocks per second. Even if your client was offline for a month it can catch up in less than 10 seconds, and that's with a completely unoptimized filtering implementation on the server (it's not doing bulk reads or multi-threaded filtering). It could go much faster still with smarter code on the C++ side. Bloom filtering really changes the game for thin client performance in a fundamental way, with only a simple protocol upgrade and without the maintenance of any additional indexes or data structures by peers.

Anyway, security. SPV nodes cannot have games played on them except in two ways: by a 51%+ miner who is forging a false chain, or (with bloom filtering) mounting a complicated DoS attack. You can solve the latter by just querying a bunch of different nodes and the former is inherent in any system in which you don't fully verify all transactions. Now as far as I can tell, what you're saying is that with extra data in the blocks you can have equivalent security to a full node, but without actually verifying all transactions. I don't see how that's possible. And yes I read your proposal so I guess I still don't understand it. If you're trusting some data you found in a coinbase input, then if I have majority hash power I can make a new best chain that contains whatever UTXO commitments I want, and you would accept it as valid. How is that not SPV-equivalent security?
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
March 14, 2013, 05:40:16 PM
 #47

The only reasonable way I've seen to get something in between SPV and full mode is d'aniels suggestions for various kinds of fraud proofs, but the whole point of a fraud proof is that you get one when the best chain is no longer following the rules .... making fraud proofs that rely on trusted commitments to the state of the UTXO set pointless (they would be a part of the fraud).
The SPV clients would be auditing commitments to the UTXO set as well, of course.

Edit: One way I can see to do this is for each block, full nodes keep handy all the branches of the UTXO tree that get updated in the next block.  If they're pruning, then they only have to keep this data a reasonable ways back in the chain.  To audit commitments to the UTXO set in a given block, an SPV node would download transaction merkle branches in this block and the relevant branches in the UTXO tree from the previous block, then check that the commits were done properly, i.e. produce the correct root to the current UTXO tree.
Upon rereading this, a better response would have been to say that this new trust model is "trust what you haven't seen a valid fraud proof disputing".  So if no false updates in the authenticated UTXO set have been proved to you, you assume it to be valid.

It's okay to base a fraud proof on the assumption of validity of the authenticated UTXO set because one could simply construct a proof that it was invalidly updated in order to prove any fraud that followed from this assumption being false.  This is the same as for the other fraud proofs, which all rely on the assumption that previous blocks upon which it was built have been valid.

The partial verification stuff I mentioned in the first response is just icing on the cake that helps ensure that fraud proofs are very likely to be found, even in the event that few full nodes are looking for them.
Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
March 15, 2013, 03:27:11 PM
 #48

But that's not the rationale that was being given before. I'm not sure why it even helps. You can prove double spending or fake spending of inputs just by providing the transactions and their merkle branches, it's not very intensive. To prove a coinbase is of the wrong size requires more, but how does putting a utxo commitment in every block help with that? You still need to download the entire block to check it's not valid.
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
March 16, 2013, 03:39:00 PM
 #49

But that's not the rationale that was being given before. I'm not sure why it even helps. You can prove double spending or fake spending of inputs just by providing the transactions and their merkle branches, it's not very intensive. To prove a coinbase is of the wrong size requires more, but how does putting a utxo commitment in every block help with that? You still need to download the entire block to check it's not valid.
That's true, it's not the rationale that was given before.  So if this is to be the current one (to be clear, it's just been my rationale), then it does bring the legitimacy of the pledges into question.  And you're right that it's not needed to prove any of these cases of fraud.

Excuse me while I think out loud for a minute...  On the one hand, having a trustworthy up-to-date commitment of the authenticated UTXO set - trustworthy because you haven't received any fraud proofs for it, and you assume you have at least one honest peer - would let you know for sure that a UTXO that you've received in a transaction hasn't been spent yet.  But on the other hand, it technically only requires one honest peer in the current arrangement to send you proof that such such a UTXO has been spent more recently than you've been led to believe.  So this proposed benefit seems kind of dubious...

The partial verification stuff is becoming less clear the more I think about it too...  But that's a far-in-a-hypothetical-future optimization anyway, to be made only if the number of full nodes becomes too low for comfort.  More important things to be funding currently IMHO.

I guess I'll have to eat my hat on this Wink
jtimon
Legendary
*
Offline Offline

Activity: 1246


View Profile WWW
March 16, 2013, 06:01:01 PM
 #50

Would it be feasible and useful to turn blocks and transactions themselves into Merkle trees too?
That way the index could reference smaller parts of the main block chain.
Does this make any sense? Why not?
I'm talking about miners signing a tree of transactions that are trees of entries (inputs and outputs) instead of the block as a list of transactions, so this would be a hard-fork.

Another question, does the proposed index use content addressable storage ?

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
maaku
Legendary
*
Offline Offline

Activity: 905


View Profile
May 12, 2013, 08:25:35 PM
 #51

Jtimon, that is what they do currently. The list entries are used as the leaves of a binary tree. hashMerkleRoot in the block header is the root hash of this tree.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
maaku
Legendary
*
Offline Offline

Activity: 905


View Profile
May 13, 2013, 08:33:32 PM
 #52

Various real-life events have conspired to find me in-between jobs right now. More than anything I would rather work on bitcoin full-time, and so I am taking a cue from @etotheipi and offering my services to the community to implement this proposal. Since this is a separate proposal from the OP's bounty, I have created a new thread:

https://bitcointalk.org/index.php?topic=204283.msg2135237#msg2135237

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
jtimon
Legendary
*
Offline Offline

Activity: 1246


View Profile WWW
May 14, 2013, 09:22:57 AM
 #53

Jtimon, that is what they do currently. The list entries are used as the leaves of a binary tree. hashMerkleRoot in the block header is the root hash of this tree.

Thank you for the clarification. I was whining about something not being done which was actually done.

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
justusranvier
Legendary
*
Offline Offline

Activity: 1400



View Profile WWW
May 31, 2013, 03:58:59 AM
 #54

I have a theory that the bounty will be more effective if we pledge income instead of a completion bonus. We should try to get enough donations to match a reasonable salary. I'll start:

I will pay USD500 per month (in bitcoins) for six months to a bitcoin developer willing to work full time on implementing this proposal.
This offer is now closed because I'm giving it to makku:

https://bitcointalk.org/index.php?topic=204283.0
Pages: « 1 2 [3]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!