Bitcoin Forum
December 06, 2016, 08:26:09 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 [7] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 »  All
  Print  
Author Topic: Ultimate blockchain compression w/ trust-free lite nodes  (Read 68564 times)
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
June 22, 2012, 12:08:58 PM
 #121

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.


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!)
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Serith
Sr. Member
****
Offline Offline

Activity: 269


View Profile
June 22, 2012, 04:46:33 PM
 #122

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
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
June 22, 2012, 04:49:16 PM
 #123

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
June 22, 2012, 07:38:33 PM
 #124

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.

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!)
Serith
Sr. Member
****
Offline Offline

Activity: 269


View Profile
June 22, 2012, 11:43:28 PM
 #125

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
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
June 23, 2012, 12:33:42 AM
 #126

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
Serith
Sr. Member
****
Offline Offline

Activity: 269


View Profile
June 23, 2012, 09:37:09 PM
 #127

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
Donator
Legendary
*
Offline Offline

Activity: 966


felonious vagrancy, personified


View Profile WWW
June 24, 2012, 09:45:09 PM
 #128

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.

The printing press heralded the end of the Dark Ages and made the Enlightenment possible, but it took another three centuries before any country managed to put freedom of the press beyond the reach of legislators.  So it may take a while before cryptocurrencies are free of the AML-NSA-KYC surveillance plague.
galambo
Sr. Member
****
Offline Offline

Activity: 390



View Profile
June 24, 2012, 10:46:45 PM
 #129


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
Donator
Legendary
*
Offline Offline

Activity: 966


felonious vagrancy, personified


View Profile WWW
June 24, 2012, 10:55:29 PM
 #130

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…

The printing press heralded the end of the Dark Ages and made the Enlightenment possible, but it took another three centuries before any country managed to put freedom of the press beyond the reach of legislators.  So it may take a while before cryptocurrencies are free of the AML-NSA-KYC surveillance plague.
eldentyrell
Donator
Legendary
*
Offline Offline

Activity: 966


felonious vagrancy, personified


View Profile WWW
June 24, 2012, 11:35:40 PM
 #131

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.

The printing press heralded the end of the Dark Ages and made the Enlightenment possible, but it took another three centuries before any country managed to put freedom of the press beyond the reach of legislators.  So it may take a while before cryptocurrencies are free of the AML-NSA-KYC surveillance plague.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
June 25, 2012, 02:41:59 PM
 #132

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.

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
btharper
Sr. Member
****
Offline Offline

Activity: 389



View Profile
June 26, 2012, 06:49:13 AM
 #133

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
Hero Member
*****
Offline Offline

Activity: 501


View Profile
June 27, 2012, 08:48:06 AM
 #134

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
aka Raphy
Hero Member
*****
Offline Offline

Activity: 868


View Profile
July 06, 2012, 12:53:30 PM
 #135

Hello,

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

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

apetersson
Hero Member
*****
Offline Offline

Activity: 666


mycelium.com


View Profile WWW
July 06, 2012, 03:01:21 PM
 #136

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
Legendary
*
qt
Offline Offline

Activity: 1470


View Profile
July 06, 2012, 03:45:28 PM
 #137

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.


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
apetersson
Hero Member
*****
Offline Offline

Activity: 666


mycelium.com


View Profile WWW
July 06, 2012, 08:49:05 PM
 #138

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
Legendary
*
Offline Offline

Activity: 1792


Monero Core Team


View Profile
July 11, 2012, 10:55:24 PM
 #139

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?

Concerned that blockchain bloat will lead to centralization? Storing less than 4 GB of data once required the budget of a superpower and a warehouse full of punched cards. https://upload.wikimedia.org/wikipedia/commons/8/87/IBM_card_storage.NARA.jpg https://en.wikipedia.org/wiki/Punched_card
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
July 11, 2012, 11:07:56 PM
 #140

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
Pages: « 1 2 3 4 5 6 [7] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 »  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!