Pledging coins for ultimate blockchain compression

[d'aniel]

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]

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]

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]

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.

[Mike Hearn]

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

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]

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]

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]

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

[jtimon]

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 ?

[maaku]

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.

[maaku]

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

[jtimon]

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.

[justusranvier]

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

[ripper234]

So, I'm doing a cleanup of old wallets ... and this one seems to have 5.725 BTC & BCH, currently worth a total of $48,977.83.

I think the "Blockchain pruning" project counts as abandoned by now:

> 8. Project abandonment - if sufficient time has passed (> 1 year), and I deem the project is abandoned by its originators and there is no interest to develop it in the community, then funds will be donated to a Bitcoin-related organization (e.g. developers of Bitcoin-qt, managers of bitcointalk.org, etc...). I will choose the organization/s, and will consult on this thread before doing so (but the final call will be mine).

I plan to take a couple of weeks to find a proper home for this money.
As it's been years since the bounty was started, I don't want to take any action to swiftly - I will give people a chance to voice in any issues they have.
Barring any concrete issues, the money will be donated to a relevant project within a couple of weeks.

[ripper234]

Update: I think BCH should go to a relevant BCH project, and not to Bitcoin/BTC.

Also, I'm in contact with Anton from Scaling Bitcoin conference (upcoming in Tel Aviv on September), sponsoring that might be a good usage of the funds.

Posted on /r/bitcoin + another thread on /r/btc for donating the BCH.

[BitUsher]

Eltoo and lightning seem to be properly funded and with a ton of help already, Ruben needs some help.

Best to hire a developer or offer rewards for different milestones to test and work on statechains -

https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39

https://tokyo2018.scalingbitcoin.org/files/Day2/statechains.pdf

https://www.youtube.com/watch?v=eG8th2x8XHY

I am sure several developers can multisig this in a responsible manner for payouts.

[ripper234]

My favorite way to proceed is to give the funds to the Scaling Bitcoin committee, and they can decide how to distribute the funds to the various projects.

[Sukrim]

My favorite way to proceed is to give the funds to the Scaling Bitcoin committee, and they can decide how to distribute the funds to the various projects.

Sounds good, these reddit threads were a bit depressing when looking at the quality of answers...

[aspect]

Following discussions over the past few weeks within the Bitcoin community in Israel and members of the Scaling Bitcoin Planning Committee, it has been decided that funds held by Ron Gross will be contributed to the Scaling Bitcoin event.

The established requirement is that roughly ~50% of these funds will be used for R&D stimulus, while the remaining ~50% will be contributed to the event budget. Since a large portion of Scaling sponsorships is used to provide for academic and developer subsidies, received funds allocated toward the budget will be prioritized to cover our subsidy and diversity efforts.

For the R&D stimulus, we will allocate 3.0 BTC for grants and form a grant committee that will award these funds to presenters at Scaling. The grant committee will establish the required criterion for the award recipients. Participants in the grant committee will be published at a later date on the Scaling Bitcoin website.

The only requirement we would like to set forth is that only the work that directly relates to and impacts the Bitcoin protocol or Bitcoin development qualifies as a recipient of these awards. This was the initial purpose of the donations collected, so this remains the priority.

Funds will be transferred in the coming days to 1V5Sbs6TghoaEJzoWkmsSGefNaAbhVdwY following which, 3 BTC will be parked at 3A8oxUi1XFoX9umM1VDD9ChPywMgG2kz22 pending the conference.  The conference will take place on 11th and 12th of September 2019 at the Tel Aviv University and funds will be awarded on the 12th of September at the end of the conference.  The award ceremony is scheduled to take place at approximately 17:55 IDT (UTC+3) but the conference schedule frequently drifts.  For a more detailed schedule and related information please visit https://telaviv2019.scalingbitcoin.org#schedule

On behalf of the Bitcoin development community, we would like to thank Ron Gross for such generous contribution and in the coming weeks, we will be making sure these funds are used to produce the maximum impact on the Bitcoin community.

Best,

Anton Yemelyanov
On behalf of the Scaling Bitcoin Planning Committee

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Receiving Address: 1V5Sbs6TghoaEJzoWkmsSGefNaAbhVdwY

===
Upon receipt, 3 BTC allocated toward R&D grants will be parked at 3A8oxUi1XFoX9umM1VDD9ChPywMgG2kz22
This message is signed with the address that will receive funds on behalf of the Scaling Bitcoin 2019 Planning Committee
Anton Yemelyanov / Chairman of the Scaling Bitcoin Planning Committee
https://keybase.io/aspectron PGP 20B0 E184 0CA0 E895
===
HxycmRJcgc/w9CYCfzP5/AxTINFSKLsMNl2ayRKBbi57Izg9u83C1alPf1Rh6p89YRHgQiUVGE9NLFA3YKvLZgs=

-----BEGIN PGP SIGNATURE-----
wsFcBAEBCAAGBQJdURWoAAoJECCw4YQMoOiV9GYQAJrHP0hsODHfc4IHpmnG
daivbsdqhwPuWrh6i9o4Sa64MZ+cptsy7vepkJZqhAS0qK/QCOZOh7UYId4l
PqAknIBNvroL+U/B/9htt/BSTaxKOAccOfS/SJ+Mx4FfrTmMVAz/7OgZx9hM
vRkxk59bHdyb4RZkiwDhpeH3ercuoKGpItVF56skJq/ttDg3OUEZx+YcQ4qP
ABv6upU3jeC9+EvKSIrAW6cDCzNDH3VvgU5LJ3QQdr3HUfrPDTSVUFIBhEmG
57kKrA8pUWZl/PpoctRsbvzEzGtMJOGH34bRqQFuvvIi5T3KdFSAz+NKcF8A
rKBX3Sw4U3luqBfdKF8kU7/NhQbc6UyXwKRvz4aa8n7HzO8SGYItP3jeEapV
dfgKV0poDW/O/slazgicRC2JPJfvDPfBhyhbyeTTvelfDKPmwcWSfjSyLwyi
TuyjUhphUB/Dow1VnCGU54chUNcGkn3h+mYnb2FBf0KfcL38YKJl4WiIsmhW
T+0kNnnz79cLznQV9/l+7U6viJsBjrdGDEwjekDKrjC7LSBlD00qdvL/sFIZ
nCOBJur+dpRXKOcb222Dp6Q571oU3RND5jevqLdEkKednyxgtKP69+DeRp1g
c5SJup5224BFNXJ46cqrz4FBUUsEKE2qfU+isW4nwBVfOK06yor4Lzs1kJwS
1gaM
=4ndb
-----END PGP SIGNATURE-----

[ripper234]

Following discussions over the past few weeks within the Bitcoin community in Israel and members of the Scaling Bitcoin Planning Committee, it has been decided that funds held by Ron Gross will be contributed to the Scaling Bitcoin event.

The established requirement is that roughly ~50% of these funds will be used for R&D stimulus, while the remaining ~50% will be contributed to the event budget. Since a large portion of Scaling sponsorships is used to provide for academic and developer subsidies, received funds allocated toward the budget will be prioritized to cover our subsidy and diversity efforts.

For the R&D stimulus, we will allocate 3.0 BTC for grants and form a grant committee that will award these funds to presenters at Scaling. The grant committee will establish the required criterion for the award recipients. Participants in the grant committee will be published at a later date on the Scaling Bitcoin website.

The only requirement we would like to set forth is that only the work that directly relates to and impacts the Bitcoin protocol or Bitcoin development qualifies as a recipient of these awards. This was the initial purpose of the donations collected, so this remains the priority.

Funds will be transferred in the coming days to 1V5Sbs6TghoaEJzoWkmsSGefNaAbhVdwY following which, 3 BTC will be parked at 3A8oxUi1XFoX9umM1VDD9ChPywMgG2kz22 pending the conference.  The conference will take place on 11th and 12th of September 2019 at the Tel Aviv University and funds will be awarded on the 12th of September at the end of the conference.  The award ceremony is scheduled to take place at approximately 17:55 IDT (UTC+3) but the conference schedule frequently drifts.  For a more detailed schedule and related information please visit https://telaviv2019.scalingbitcoin.org#schedule

On behalf of the Bitcoin development community, we would like to thank Ron Gross for such generous contribution and in the coming weeks, we will be making sure these funds are used to produce the maximum impact on the Bitcoin community.

Best,

Anton Yemelyanov
On behalf of the Scaling Bitcoin Planning Committee

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Receiving Address: 1V5Sbs6TghoaEJzoWkmsSGefNaAbhVdwY

===
Upon receipt, 3 BTC allocated toward R&D grants will be parked at 3A8oxUi1XFoX9umM1VDD9ChPywMgG2kz22
This message is signed with the address that will receive funds on behalf of the Scaling Bitcoin 2019 Planning Committee
Anton Yemelyanov / Chairman of the Scaling Bitcoin Planning Committee
https://keybase.io/aspectron PGP 20B0 E184 0CA0 E895
===
HxycmRJcgc/w9CYCfzP5/AxTINFSKLsMNl2ayRKBbi57Izg9u83C1alPf1Rh6p89YRHgQiUVGE9NLFA3YKvLZgs=

-----BEGIN PGP SIGNATURE-----
wsFcBAEBCAAGBQJdURWoAAoJECCw4YQMoOiV9GYQAJrHP0hsODHfc4IHpmnG
daivbsdqhwPuWrh6i9o4Sa64MZ+cptsy7vepkJZqhAS0qK/QCOZOh7UYId4l
PqAknIBNvroL+U/B/9htt/BSTaxKOAccOfS/SJ+Mx4FfrTmMVAz/7OgZx9hM
vRkxk59bHdyb4RZkiwDhpeH3ercuoKGpItVF56skJq/ttDg3OUEZx+YcQ4qP
ABv6upU3jeC9+EvKSIrAW6cDCzNDH3VvgU5LJ3QQdr3HUfrPDTSVUFIBhEmG
57kKrA8pUWZl/PpoctRsbvzEzGtMJOGH34bRqQFuvvIi5T3KdFSAz+NKcF8A
rKBX3Sw4U3luqBfdKF8kU7/NhQbc6UyXwKRvz4aa8n7HzO8SGYItP3jeEapV
dfgKV0poDW/O/slazgicRC2JPJfvDPfBhyhbyeTTvelfDKPmwcWSfjSyLwyi
TuyjUhphUB/Dow1VnCGU54chUNcGkn3h+mYnb2FBf0KfcL38YKJl4WiIsmhW
T+0kNnnz79cLznQV9/l+7U6viJsBjrdGDEwjekDKrjC7LSBlD00qdvL/sFIZ
nCOBJur+dpRXKOcb222Dp6Q571oU3RND5jevqLdEkKednyxgtKP69+DeRp1g
c5SJup5224BFNXJ46cqrz4FBUUsEKE2qfU+isW4nwBVfOK06yor4Lzs1kJwS
1gaM
=4ndb
-----END PGP SIGNATURE-----

Confirmed. I will give a few days for additional feedback, and then transfer the funds.