Ultimate blockchain compression w/ trust-free lite nodes

[FreeMoney]

Why would people mine this other chain?

If it has lower hashing power is everyone trusting it more susceptible to double spends somehow?

[maaku]

Conceivably you could run an even lighter client that just implicitly trusts the head of the alt-chain. Such a client would rely upon honest miners doing the work of verifying the alt-chain, and not actually perform such checks itself.

[Maged]

Why would people mine this other chain?

Why do miners currently mine transactions that don't have a fee? The answer to both of these questions are that doing such things aren't terribly costly, but more importantly, it encourages further adoption of Bitcoin which will directly result in increased revenue for miners in the future.

[Serith]

I think that if you want to have the root value to be the same regardless of order in which a tree or any hierarchical structure was created, then you would need a hash function that has commutative and associative properties.

[Technomage]

Why do miners currently mine transactions that don't have a fee? The answer to both of these questions are that doing such things aren't terribly costly, but more importantly, it encourages further adoption of Bitcoin which will directly result in increased revenue for miners in the future.

This is changing faster than we've anticipated though. Due to the sheer volume of transactions that SatoshiDice produces, higher fees will start to get priority. The bad thing is that current Bitcoin clients don't have a very sophisticated fee system or fee options.

[ffe]

Tracking

[jl2012]

I have a proposal as an "add-on" to this

When a miner sees a tx, he could either 1. grab the tx fee, or 2. "donate" the tx fee to the alt-chain.

Grabbing the tx free is essentially the current practice

If it is "donated", it will go to a jackpot pool for the alt-chain. A miner who find a valid block in the alt-chain will claim the jackpot.

By donating the tx fee, miner will get a "discount" in their mining difficulty. The discount will be calculated in a pay-per-share manner. For example, the current difficulty is 1583 177.847444 with block reward of 50BTC. A fair PPS would be 0.00003158. Therefore, a tx fee of 0.0005 is equivalent to 15.831778 shares. By donating the tx fee, the miner will only need to find a block with difficulty of 1583177.847444-15.831778 = 1583162.015666.

Miner will want to donate tx fee since this helps them to find a block easier and reduce  variation. It also provide a feedback mechanism for mining. In a bad luck turn where many tx accumulate, difficulty is reduced and the bad luck turn could be ended earlier.
The effective difficulty is no longer a constant throughout 2016 blocks. Instead, it will be a zig-zag function: highest at the beginning of a round, keep decreasing as unconfirmed tx accumulate, and jump back to the highest value when a block is found. The average block generation rate is still 10-minutes but the variation is reduced too.

Some miners may abuse this system by creating tx with high tx fee (e.g. 25BTC) and donating it to the alt-chain, so their difficulty is reduced by 50%. To prevent this, we may put a cap on the difficulty discount (e.g. 10% of difficulty) and/or calculate the discount with <100% PPS (So the expected return will be decreased).

[flower1024]

isn't it possible to merge mine the balance chain just like many pools do with namecoin?
that way there is not need to give any reward to miners. just include it in bitcoind as a "protocol requirement" for mining.

[etotheipi]

isn't it possible to merge mine the balance chain just like many pools do with namecoin?
that way there is not need to give any reward to miners. just include it in bitcoind as a "protocol requirement" for mining.

Yup.  The second chain doesn't need incentive due merged mining, unless it's particularly resource-consuming.  If the software is already written, and integrates into bitcoind or other mining software transparently, and doesn't impact mining performance, then miners would [likely] have no complaints about adopting it given the huge upside it offers.  It's basically free, from their perspective.

Though I don't agree it would be a "protocol requirement."  Miners have various reasons for doing what they do.  And this is being promoted as non-disruptive and optional.  But you don't need more than, probably 20% of mining power to engage this idea for it to be successful.  I'm not even sure what a 51% attack would look like on the alt-chain, but it wouldn't be very exciting -- the worst you could do is prevent some lite-nodes being able to verify their own balance -- but there would be no financial gain for it, and it would cost a fortune.  20% seems like a number high enough that there would always be a "checkpoint" nearby, and high enough that it would be vastly too expensive for a prankster to do anything to that chain.

[blueadept]

If the altchain has some place to put a scriptPubKey or an array of them in every block, the chain could be funded with network assurance contracts as proposed by Mike Hearn for the main chain when the subsidy gets lower than fees.

[casascius]

If the idea works and becomes essential to the way most people use Bitcoin, all developers could easily strategize and decide that a future version of clients will only relay/accept blocks when their coinbase contains a valid merged mining record for the other chain's most recent valid block.  It might then be properly called a "meta chain" rather than an "alt chain".

[maaku]

It might then be properly called a "meta chain" rather than an "alt chain".

That's much better terminology. Thank you.

[FreeMoney]

isn't it possible to merge mine the balance chain just like many pools do with namecoin?
that way there is not need to give any reward to miners. just include it in bitcoind as a "protocol requirement" for mining.

Yup.  The second chain doesn't need incentive due merged mining, unless it's particularly resource-consuming.  If the software is already written, and integrates into bitcoind or other mining software transparently, and doesn't impact mining performance, then miners would [likely] have no complaints about adopting it given the huge upside it offers.  It's basically free, from their perspective.

Though I don't agree it would be a "protocol requirement."  Miners have various reasons for doing what they do.  And this is being promoted as non-disruptive and optional.  But you don't need more than, probably 20% of mining power to engage this idea for it to be successful.  I'm not even sure what a 51% attack would look like on the alt-chain, but it wouldn't be very exciting -- the worst you could do is prevent some lite-nodes being able to verify their own balance -- but there would be no financial gain for it, and it would cost a fortune.  20% seems like a number high enough that there would always be a "checkpoint" nearby, and high enough that it would be vastly too expensive for a prankster to do anything to that chain.

Thanks, that makes sense.

[theymos]

Trustless lightweight-node support:  New nodes entering the network for the first time, will only have to download a tiny amount of data to get full, verifiable knowledge of their balance and how to spend it (much of which can be stored between loads).  A single honest peer out of thousands guarantees you get, and recognize, good data.

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.

There is an advantage to "mostly-full" nodes who store all unspent transactions: they don't have to download all past blocks to start validating. But a regular Merkle tree of unspent outputs works just as well.

Using an alt chain instead of putting the Merkle root in a main-chain transaction seems unnecessarily complex.

[etotheipi]

Trustless lightweight-node support:  New nodes entering the network for the first time, will only have to download a tiny amount of data to get full, verifiable knowledge of their balance and how to spend it (much of which can be stored between loads).  A single honest peer out of thousands guarantees you get, and recognize, good data.

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 doesn't make sense at all.  The entirety of all Bitcoin trust relies on trusting "the majority of the network's mining power."  That is the security model of Bitcoin itself, and has the benefit that you only need one honest node out of one million to be able to distinguish truth amongst a sea of malicious peers.

The issue with SPV is that you have to trust either random peers to give you the correct/complete info, or connect to your own trusted system/subscription to get reliable information.  Without a subscription service, you have to query lots of peers and possibly use filtering/profiling games with peers to identify untrusted nodes, etc.   With this idea, you minimize the amount of information needed to be downloaded, and can compare directly against the headers -- you can get all the information you need from a single peer and know it's right (assuming you've already got the headers).

And that is actually just a side-benefit of it -- the original goal was blockchain compression, which this does near-optimally.

I agree that complexity is high.  But I disagree with the notion that you're not getting something for it.

[theymos]

This doesn't make sense at all.  The entirety of all Bitcoin trust relies on trusting "the majority of the network's mining power."  That is the security model of Bitcoin itself, and has the benefit that you only need one honest node out of one million to be able to distinguish truth amongst a sea of malicious peers.

If I have a copy of all unspent outputs, the majority of mining power can only change the ordering of transactions (and this ability might be more limited in the future). But a lightweight node will accept double-spends within the block chain, too-high block subsidies, invalid scripts, etc. if the attacker has enough mining power.

The issue with SPV is that you have to trust either random peers to give you the correct/complete info, or connect to your own trusted system/subscription to get reliable information.

You don't have to trust random peers with SPV. SPV clients have the block headers and can use the Merkle roots to accurately get the number of confirmations for any transaction.

[socrates1024]

If I have a copy of all unspent outputs, the majority of mining power can only change the ordering of transactions (and this ability might be more limited in the future). But a lightweight node will accept double-spends within the block chain, too-high block subsidies, invalid scripts, etc. if the attacker has enough mining power.

Notice that if the lightweight Client runs the Merkle tree scheme I described, it can rejected double-spends, invalid scripts, etc. Even without needing to store a copy of the unspent outputs.

Instead, the Client receives each block header, as well as O(M log N) of verification data (paths through the Merkle tree). This way, the Client can check each transaction against the database, as indicated by the current root hash. Only a full node acting as an untrusted helper needs to store the entire unspent outputs database, in order to generate the verification data.

[etotheipi]

The issue with SPV is that you have to trust either random peers to give you the correct/complete info, or connect to your own trusted system/subscription to get reliable information.

You don't have to trust random peers with SPV. SPV clients have the block headers and can use the Merkle roots to accurately get the number of confirmations for any transaction.

Yes, but how do you know a particular TxOut hasn't been spent since it appeared in the blockchain?  I can verify, by downloading full transactions, that a particular TxOut was valid at one point in time, but I have no way to determine if it's been spent since that time.  Whether I'm verifying my own balance, or trying to confirm the validity of the inputs of another transaction, any malicious node can give me seemingly correct information, but still make my node incapable of operating -- perhaps because when I got online the first time an imported my wallet, I was given only old TxOuts that have since been spent, and my node will be stuck creating invalid transactions trying to spend them.

This is the basis of the overlay network that Electrum/Stratum uses.  I don't think there's anything wrong with that overlay network, other than it relies on trusted nodes being setup and available, or subscribing to a service, all of which is a degree of centralization (and extra user effort).  This chain avoids all of it, providing (at the expense of complexity), more reliable information without trusting anyone.  

If that was the only benefit, I'd agree it wouldn't be worth the hassle.  But as I said, that's a secondary benefit of this structure.  The main reason to do it is compression.

Which could be implemented with a simpler tree structure using an alt/meta-chain.  Or this tree-structure using a different distribution technique (protocol change, overlay network, trusting random peers, etc).

[theymos]

This is the basis of the overlay network that Electrum/Stratum uses.

Electrum and Stratum don't use SPV. Those clients don't keep block headers (AFAIK). BitcoinJ uses SPV.

Yes, but how do you know a particular TxOut hasn't been spent since it appeared in the blockchain?

I wait until it has 6 confirmations. SPV allows me to determine the number of confirmations accurately (assuming the majority of mining power is honest).

[etotheipi]

This is the basis of the overlay network that Electrum/Stratum uses.

Electrum and Stratum don't use SPV. Those clients don't keep block headers (AFAIK). BitcoinJ uses SPV.

Yes, but how do you know a particular TxOut hasn't been spent since it appeared in the blockchain?

I wait until it has 6 confirmations. SPV allows me to determine the number of confirmations accurately (assuming the majority of mining power is honest).

I'm not concerned about enough confirmations.  I'm actually concerned that it has 10,000 confirmations, and that it was actually spent 3,000 blocks ago, and that I have to search through 10,000 full blocks in order to know whether it's still a valid output.  Or, I can ask other nodes for help, but I how do I know to trust them?