Proposal: A Second Chain for Scalability

[BrightAnarchist]

Hey thanks for the feedback, I am learning a lot more about Bitcoin just by thinking about this stuff ( and realizing how little I really understand! ).

Ideally yes a test altchain is the way to go.

[1713567296]

1713567296

[1713567296]

1713567296

[1713567296]

1713567296

[fivebells]

• Every block in the block chain only pays out 90% 99.9% of its block reward. The other 10% 0.1% is kept on reserve in the block.

[

• The balance chain difficulty is 100X 1000X the transaction chain difficulty.
• The node that solves a balance chain block recieves all of the reserved block rewards from the included transaction blocks.

/li]
[/list]

  Under this scheme, the relative reward for mining in the two chains would likely vary over time.  You probably want to make the expected reward per compute cycle equal for the two chains or you might see fluctuations in hashing power between them.  Merged mining, like d'aniel suggested, is probably a better idea.

[dscotese]

I like being able to trace bitcoin all the way back to the generating transaction.  Not that I've done it, but it's interesting and I imagine it could be useful.  I started looking at this thread because I had an idea (deemed "bad" for now because of some aspects which I think can be fixed) for increasing the cost and decreasing the benefit to thieves who steal bitcoin.

[MoonShadow]

Although this is an interesting idea, I don't think that it's viable.  How do you encentivise miners to secure this alt-chain?  However, a running balance table server isn't a bad idea as a pay-for service for light clients to use as a means to check their own addresses to make sure that they havn't missed something.  For example, one (or serveral) balance servers could exist that individual lightweight clients could contact out-of-bitcoin-band as a quick check upon startup, or a secondary check.  If the balance returned does not match, the lightweight client may have to try again, but if the balance returned matches what it thinks that it should have upon startup, the client can happily assume that it has all the relevant transactions to continue.

The service could be paid for in an anonymous, monthly fee.  Once every 30 days or so, the client tries to send the chosen balance server a small tip, and the server collects the addresses presented in that transaction (since lightweight clients tend to use fewer new addresses, or a more sophisticated lightweight client for the desktop could simply create a special transaction that uses as many input address as may be important, or simply uses the monthy transaction to consolidate addresses into a new operating address producing the server's monthly fee in the process).  When the client is restarted in the middle of the month according to the datetime available to the client, it first checks to see what it thinks that it's balance is, and then sends off the appropriate requests to the subscribed balance server.  If the server responds with the matching balance, the client happliy can quick boot and be ready for action (like bitcoinspinner).  If the balance returned is differnet, the client then should tell the user that it needs to update itself before spending, and proceed to do so in the background.  If the server feels it's not been properly paid, it returns an error code; or of the address is unknown in the blockchain; which would likely be the same as a zero balance to a running balance server.  Lightweight clients (that hold block headers) could still manage local transactions sans live Internet access, but with a warning to the user that Internet was not present and this could present a risk.  This setup would allow android clients to get into a working condition as fast as BitcoinSpinner most of the time, while also permitting delayed transactions/offline transactions to occur, which BitcoinSpinner & BitcoinJ most certainly cannot do.

[etotheipi]

Although this is an interesting idea, I don't think that it's viable.  How do you encentivise miners to secure this alt-chain? 

Why do users run Tor exit nodes?  Why do people participate in P2Pool?   There's a dozen things like it -- and people do it anyway because it adds value to the system (which means it also adds value for themself).  If the incentive is that we help avoid centralization of a this global currency, then people will do it, as long as the cost isn't too high.

You're right, though, if it's too expensive: if it requires a system with 192 GB of RAM and 48 CPU cores to keep the second chain updated, then it's probably a no-go.  But in the absence of that, people will do it, maybe solely because they're selfish and they want better performance&security on their own smartphone. 

I haven't done the calculation yet.  However, I suspect that once the second blockchain has been seeded (i.e. one can securely acquire the current unspent-txout-tree), then a regular computer will be able to maintain and update that unspent-txout-tree (short of Visa-level tx volume).  In that case, there will be no problem getting users and miners to support it,

EDIT:  Also, If merged mining didn't exist then I would 100% agree with you.  But because it does exist, the second chain be secured for "free", which lowers the cost and risk dramatically.

However, a running balance table server isn't a bad idea as a pay-for service for light clients to use as a means to check their own addresses to make sure that they havn't missed something.  For example, one (or serveral) balance servers could exist that individual lightweight clients could contact out-of-bitcoin-band as a quick check upon startup, or a secondary check.  If the balance returned does not match, the lightweight client may have to try again, but if the balance returned matches what it thinks that it should have upon startup, the client can happily assume that it has all the relevant transactions to continue.

The service could be paid for in an anonymous, monthly fee.  Once every 30 days or so, the client tries to send the chosen balance server a small tip, and the server collects the addresses presented in that transaction (since lightweight clients tend to use fewer new addresses, or a more sophisticated lightweight client for the desktop could simply create a special transaction that uses as many input address as may be important, or simply uses the monthy transaction to consolidate addresses into a new operating address producing the server's monthly fee in the process).  When the client is restarted in the middle of the month according to the datetime available to the client, it first checks to see what it thinks that it's balance is, and then sends off the appropriate requests to the subscribed balance server.  If the server responds with the matching balance, the client happliy can quick boot and be ready for action (like bitcoinspinner).  If the balance returned is differnet, the client then should tell the user that it needs to update itself before spending, and proceed to do so in the background.  If the server feels it's not been properly paid, it returns an error code; or of the address is unknown in the blockchain; which would likely be the same as a zero balance to a running balance server.  Lightweight clients (that hold block headers) could still manage local transactions sans live Internet access, but with a warning to the user that Internet was not present and this could present a risk.  This setup would allow android clients to get into a working condition as fast as BitcoinSpinner most of the time, while also permitting delayed transactions/offline transactions to occur, which BitcoinSpinner & BitcoinJ most certainly cannot do.

I think what you've posted there is a good idea, in general.  However, I'm more interested in finding solutions that don't involve third-parties and extra fees.  Or rather, I just don't like conceding to them until it's clear that a decentralized P2P solution is infeasible. 

[fivebells]

Why do users run Tor exit nodes?  Why do people participate in P2Pool?   There's a dozen things like it -- and people do it anyway because it adds value to the system (which means it also adds value for themself).  If the incentive is that we help avoid centralization of a this global currency, then people will do it, as long as the cost isn't too high.

  Not sure that this is a good analogy, since there would be economic incentive to merged-mine both chains.

[etotheipi]

Why do users run Tor exit nodes?  Why do people participate in P2Pool?   There's a dozen things like it -- and people do it anyway because it adds value to the system (which means it also adds value for themself).  If the incentive is that we help avoid centralization of a this global currency, then people will do it, as long as the cost isn't too high.

  Not sure that this is a good analogy, since there would be economic incentive to merged-mine both chains.

I don't follow.  The proposal in this thread suggests that there would be a second chain, and it's purpose would be for nodes to securely exchange pruned/compressed blockchain snapshots.  The result of mining a block on the second chain would not produce anything of financial value, but it doesn't matter because it's basically free with merged mining (besides a software upgrade).

If someone or a team produced this solution, and there was great confidence in this solution being correct and usable -- then the cost for users to support it is:

(1) Upgrade their mining servers and probably miners, too.
(2) Spend electricity computing unspent-TxOut-tree snapshots

I have no doubt that someone or a team would step up and produce the solution.  And I have no doubt that users/miners would do (1) if they were confident that it would work.  Number (2) is more uncertain, but if it's a matter of a CPU-minute every hour, most miners would do it given the benefits it brings to the network.  Plus, you only need some miners to participate, you don't even need a majority.

Btw:  I don't have much experience with merged mining, so maybe I'm making a poor assumption here...

[MoonShadow]

I have no doubt that someone or a team would step up and produce the solution.  And I have no doubt that users/miners would do (1) if they were confident that it would work.  Number (2) is more uncertain, but if it's a matter of a CPU-minute every hour, most miners would do it given the benefits it brings to the network.  Plus, you only need some miners to participate, you don't even need a majority.

Perhaps, but only if the benefit to the network is demonstratable as compared to alternatives.  While a p2p solution might be possible, it's not always necessary.  And if it's not necessary, it's not likely resource/economicly justifiable.  Bitcoin is p2p for sound reasons, but what reasons carry over to what amounts to a tracking service?  If the server that a particular client chooses should go down or be DDOS'ed, the result from the perspective of the user is the same as if he had left his service area; a temporary inconveince.  And in the case of header-only/lightweight clients, not necessarily even a dehibilitating one.  I'll admit, this idea has merit; but it seems to lack encentive.  I can admit I might be overlooking something here, but what gain does a miner have for participating and sharing his findings?  Both are important, because if his gains are personal, he then has limited incentive to share the results.

A co-dependent blockchain with the same period as bitcoin itself seems like it's just adding noise.
However, a daily digest of (postive) balances might be useful in a number of ways; with (perhaps) an hourly update produced of recent (but 6 confirms deep) changes to that digest.  I can see such a bitstream being used as a secondary verification of authenticity for major retail chains that didn't want to track the blockchain at every location, but wanted to also protect against some form of local hack/fraud/yet-unknown-attack-vector.  I could also see small, independent vendors on the edge of the network (read not enough bandwidth to commit) to maintain a realitively trustworthy local database of address balances so that he could accept bitcoin transactions from walk-in customers without getting hosed by every script-kiddie in his neighborhood.

[etotheipi]

I have no doubt that someone or a team would step up and produce the solution.  And I have no doubt that users/miners would do (1) if they were confident that it would work.  Number (2) is more uncertain, but if it's a matter of a CPU-minute every hour, most miners would do it given the benefits it brings to the network.  Plus, you only need some miners to participate, you don't even need a majority.

Perhaps, but only if the benefit to the network is demonstratable as compared to alternatives.  While a p2p solution might be possible, it's not always necessary.  And if it's not necessary, it's not likely resource/economicly justifiable.  Bitcoin is p2p for sound reasons, but what reasons carry over to what amounts to a tracking service?  If the server that a particular client chooses should go down or be DDOS'ed, the result from the perspective of the user is the same as if he had left his service area; a temporary inconveince.  And in the case of header-only/lightweight clients, not necessarily even a dehibilitating one.  I'll admit, this idea has merit; but it seems to lack encentive.  I can admit I might be overlooking something here, but what gain does a miner have for participating and sharing his findings?  Both are important, because if his gains are personal, he then has limited incentive to share the results.

Just to clarify:  I have in mind the hybrid solution between this thread (a second chain w/ merged mining for non-disruptively maintaining snapshot info) and my modification of the unspent-TxOut-tree idea for compression and pruning.  If all we were talking about was compression/pruning, then I understand why you're skeptical, though I still disagree (I believe it would be widely supported).

But we're talking about any client having the ability to retrieve full unspent-TxOut lists, nearly instantaneously, with the same confidence as a full node, with only headers, and while maintaining complete decentralization.  If lightweight clients suddenly have the same usability & confidence as full clients and everything remains completely decentralized -- that's an extraordinary boon to the network that a lot of users would go out of their way to support.  I mean, really go out of their way to support it.

Hell, even if it was just compression/pruning, I think users would still support it.  Therefore, I think the extra benefits would have users racing to implement and support it.   Though, if that idea turns out not to work, it is still relevant to talk about the expected acceptance of a second blockchain solely for compression purposes.

[MoonShadow]

Just to clarify:  I have in mind the hybrid solution between this thread (a second chain w/ merged mining for non-disruptively maintaining snapshot info) and my modification of the unspent-TxOut-tree idea for compression and pruning.  If all we were talking about was compression/pruning, then I understand why you're skeptical, though I still disagree (I believe it would be widely supported).

But we're talking about any client having the ability to retrieve full unspent-TxOut lists, nearly instantaneously, with the same confidence as a full node, with only headers, and while maintaining complete decentralization. 

Yet, 1) those goals are the same as the pruning & lightweight client features of the protocol, not yet ready and 2) I don't agree that those goals can be met with a dependent & parallel chain any better (and probably less well) than #1.  You're still talking about a potentially huge block/file that would have to be downloaded every ten minutes.  What gain is there in that?  Might as well stick with the main network or an overlay such as Stratum.

And it's quite literally impossible for lightweigt clients to have the 'same confidence as" a full node.  The best that a lightweight client can have is some confidence.

If lightweight clients suddenly have the same usability & confidence as full clients and everything remains completely decentralized -- that's an extraordinary boon to the network that a lot of users would go out of their way to support.  I mean, really go out of their way to support it.

Hell, even if it was just compression/pruning, I think users would still support it.  Therefore, I think the extra benefits would have users racing to implement and support it.   Though, if that idea turns out not to work, it is still relevant to talk about the expected acceptance of a second blockchain solely for compression purposes.

It certainly doesn't hurt to talk about it, but I don't agree that such an idea has merit when compared to other methods od achieving similar goals already discussed.  And if I can't see it, I'f wager that there are many more who are going to be sceptical of it's value as well.  Without a minimum critical mass, nothing is going to matter.

[etotheipi]

And it's quite literally impossible for lightweigt clients to have the 'same confidence as" a full node.  The best that a lightweight client can have is some confidence.

Go back and read the proposal.  It allows for a lightweight node to carry nothing but the headers (for both chains) and then it can verify the full unspent-TxOut-list directly against the headers.  Ultimately that's what a full node does -- the headers are the base of all trust.  Therefore, once you've got the headers and the longest chain figured out, a wallet of 100 addresses could be sync'd and verified against the headers with the same confidence as a full-node with less than 1 MB of downloading.  (that's for the initial sync -- after that you either re-sync, or update the unspent-TxOut-list for your wallet with the new blocks/tx as they come in)

For the nodes that are maintaining the compressed/pruned list, they only need to do that massive full-chain calculation once.  The tree/snapshot can then be updated incrementally, which is many orders of magnitude faster than recomputing the whole thing on every block.

It certainly doesn't hurt to talk about it, but I don't agree that such an idea has merit when compared to other methods od achieving similar goals already discussed.  And if I can't see it, I'f wager that there are many more who are going to be sceptical of it's value as well.  Without a minimum critical mass, nothing is going to matter.

My concern with other methods is lack of verifiability that your node actually has the correct tree.  It could be corrupted, or maliciously modified, and there's no way to know, since nothing in the tree is traceable back to the headers.  The only solution is to trust a third-party/server, or download substantial portions of the entire blockchain.  

It's for this reason that I thought blockchain pruning would not work without enforcing accurate snapshot hashes in the header, and thus it wouldn't work because no one would support such a huge change to the protocol.  But the idea of putting all that data into another chain with merged mining makes it completely feasible and non-disruptive to others that don't care.

[MoonShadow]

And it's quite literally impossible for lightweigt clients to have the 'same confidence as" a full node.  The best that a lightweight client can have is some confidence.

Go back and read the proposal.  It allows for a lightweight node to carry nothing but the headers (for both chains) and then it can verify the full unspent-TxOut-list directly against the headers.  Ultimately that's what a full node does -- the headers are the base of all trust.  

While this is true, it's far from a complete picture of the intergrated security model that full nodes have access to.  In order for a lightweight client to accept a payment transaction, it must either 1) have Internet and access to a supporting server or 2) accept the evidence that the sender's client provides.  Although a lightweight client sending to another should have no problem sending a copy of the input transactions, which the lightweight client can then verify that it fits into it's own claimed spot on the merkle tree connecting to it's own copy of the block header, this is still not quite the same as what options of verfications that a full client has.

Therefore, once you've got the headers and the longest chain figured out, a wallet of 100 addresses could be sync'd and verified against the headers with the same confidence as a full-node with less than 1 MB of downloading.  (that's for the initial sync -- after that you either re-sync, or update the unspent-TxOut-list for your wallet with the new blocks/tx as they come in)

I don't see that, sorry.

For the nodes that are maintaining the compressed/pruned list, they only need to do that massive full-chain calculation once.  The tree/snapshot can then be updated incrementally, which is many orders of magnitude faster than recomputing the whole thing on every block.

Of course, but this is holds no notable advantage over just a lightweight client once the running network can fully support them.  I can't really see what the use case is beyond what lightweight clients & pruning can't provide.

It certainly doesn't hurt to talk about it, but I don't agree that such an idea has merit when compared to other methods od achieving similar goals already discussed.  And if I can't see it, I'f wager that there are many more who are going to be sceptical of it's value as well.  Without a minimum critical mass, nothing is going to matter.

My concern with other methods is lack of verifiability that your node actually has the correct tree.  It could be corrupted, or maliciously modified, and there's no way to know, since nothing in the tree is traceable back to the headers.  The only solution is to trust a third-party/server, or download substantial portions of the entire blockchain.  

Of course a lightweight client can download the merkle tree and verifty that.  It jsut needs to be able to identify conditions that would prompt that action based upon some local risk model.  There is nothing that prevents a lightweight client from collecting the block headers, and downloading up to and including an entire block if a risky inbound transaction is received.

It's for this reason that I thought blockchain pruning would not work without enforcing accurate snapshot hashes in the header, and thus it wouldn't work because no one would support such a huge change to the protocol.  But the idea of putting all that data into another chain with merged mining makes it completely feasible and non-disruptive to others that don't care.

The block headers do contain accurate snampshot hashes.  That's why the merkle tree exists and why the merkle tree root(s) (current block & previous block) is in the block headers.

[tvbcof]

... How do you encentivise miners to secure this alt-chain? ...

That's pretty straightforward.  Give them more BTC than they could earn mining Bitcoin.  As the reward drops it will only become that much easier.

[etotheipi]

And it's quite literally impossible for lightweigt clients to have the 'same confidence as" a full node.  The best that a lightweight client can have is some confidence.

Go back and read the proposal.  It allows for a lightweight node to carry nothing but the headers (for both chains) and then it can verify the full unspent-TxOut-list directly against the headers.  Ultimately that's what a full node does -- the headers are the base of all trust.  

While this is true, it's far from a complete picture of the intergrated security model that full nodes have access to.  In order for a lightweight client to accept a payment transaction, it must either 1) have Internet and access to a supporting server or 2) accept the evidence that the sender's client provides.  Although a lightweight client sending to another should have no problem sending a copy of the input transactions, which the lightweight client can then verify that it fits into it's own claimed spot on the merkle tree connecting to it's own copy of the block header, this is still not quite the same as what options of verfications that a full client has.

The solution I proposed does not rely on a "supporting server". It does not require trusting the sender's client.  And the internet access part is a given for any node that has any hope of accepting zero-confirmation transactions with less than complete-trust.  I have assumed all along that the node has a connection.

The solution I proposed does not require any trust of any nodes, any more than a full node on currently trusts any other node -- you trust the longest chain of headers.  Any data that is consistent with the longest chain is as trustworthy as it gets, regardless of who it came from.  In this case, the second-chain headers contain a hash of a merkle tree specifically designed for a node to verify the complete unspent-TxOut-list for any script/address.  

Let's say you have only the headers of both chains and you are verifying  an input of a zero-conf tx.  A peer sends you a list of unspent outputs.  But, how do you know the list is legit?  Even if you verified the outputs are part of the blockchain, how do you know they haven't been spent since then?  

The solution I proposed does exactly this.  I download an additional 1-2kB of data (the master merkle branch for that address), and then I can see that the unspent output list is correct against the headers.  This includes the fact that none of those outputs have been spent since then.  

Therefore, once you've got the headers and the longest chain figured out, a wallet of 100 addresses could be sync'd and verified against the headers with the same confidence as a full-node with less than 1 MB of downloading.  (that's for the initial sync -- after that you either re-sync, or update the unspent-TxOut-list for your wallet with the new blocks/tx as they come in)

I don't see that, sorry.

[/quote]

Then we're not talking about the same thing.  I'll make a graphic to depict this concept more clearly.  Until then, this conversation can't continue, because you will otherwise never believe that what I am proposing is possible.  I didn't believe it was possible, either... which is why I'm so excited about this idea because it actually does this

[MoonShadow]

And it's quite literally impossible for lightweigt clients to have the 'same confidence as" a full node.  The best that a lightweight client can have is some confidence.

Go back and read the proposal.  It allows for a lightweight node to carry nothing but the headers (for both chains) and then it can verify the full unspent-TxOut-list directly against the headers.  Ultimately that's what a full node does -- the headers are the base of all trust.  

While this is true, it's far from a complete picture of the intergrated security model that full nodes have access to.  In order for a lightweight client to accept a payment transaction, it must either 1) have Internet and access to a supporting server or 2) accept the evidence that the sender's client provides.  Although a lightweight client sending to another should have no problem sending a copy of the input transactions, which the lightweight client can then verify that it fits into it's own claimed spot on the merkle tree connecting to it's own copy of the block header, this is still not quite the same as what options of verfications that a full client has.

The solution I proposed does not rely on a "supporting server". It does not require trusting the sender's client.  And the internet access part is a given for any node that has any hope of accepting zero-confirmation transactions with less than complete-trust.  I have assumed all along that the node has a connection.

Then this proposal is already a fail.  Because what do you offer then?  Decentralization?  You might as well say 'the cloud' for all the relevance that would have to the end user.

The solution I proposed does not require any trust of any nodes, any more than a full node on currently trusts any other node -- you trust the longest chain of headers.

Again, not materially different than a lightweight client or any normal full client willing to provide a pruned block upon request.

 Any data that is consistent with the longest chain is as trustworthy as it gets, regardless of who it came from.  In this case, the second-chain headers contain a hash of a merkle tree specifically designed for a node to verify the complete unspent-TxOut-list for any script/address.  

Not any data so consistant, which is why bitcoin requires the format that it presently does.  The blockchain structure is self-re-enfircing from amny directions; not just from a single merkle tree branch up to the block header.  It is possible, although unlikley, to create a transaction that falsely gives you an arbitrary amount of bitcoins from non-existant inputs and find a merkle tree branch that it can 'fit' in, but that would never last a millisecond of verfications from a full client.

Let's say you have only the headers of both chains and you are verifying  an input of a zero-conf tx.  A peer sends you a list of unspent outputs.  But, how do you know the list is legit?  Even if you verified the outputs are part of the blockchain, how do you know they haven't been spent since then?  

The solution I proposed does exactly this.  I download an additional 1-2kB of data (the master merkle branch for that address), and then I can see that the unspent output list is correct against the headers.  This includes the fact that none of those outputs have been spent since then.  

But requires constant Internet, so offers zero advantage over the (full future) live network or an overlay network such as Stratum.  In fact, Startum does eactly what you seem to want to do both decentralized and without an alt-chain.

Again, a lightweight client can become up to a full client at will, as well as participate in Stratum where it might need to.  There is noting that prevents this kind of actions.

Therefore, once you've got the headers and the longest chain figured out, a wallet of 100 addresses could be sync'd and verified against the headers with the same confidence as a full-node with less than 1 MB of downloading.  (that's for the initial sync -- after that you either re-sync, or update the unspent-TxOut-list for your wallet with the new blocks/tx as they come in)

I don't see that, sorry.

Then we're not talking about the same thing.  I'll make a graphic to depict this concept more clearly.  Until then, this conversation can't continue, because you will otherwise never believe that what I am proposing is possible.  I didn't believe it was possible, either... which is why I'm so excited about this idea because it actually does this
[/quote]

Okay.

[punningclan]

Couldn't merged mining be used to secure the alt-chain?

[MoonShadow]

Couldn't merged mining be used to secure the alt-chain?

Probably, under certain conditions. 

[etotheipi]

In fact, Startum does eactly what you seem to want to do both decentralized and without an alt-chain.

Sorry, I'm not familiar with the Stratum alternative.  If there is no alt-chain for verification, what is stopping malicious nodes from distributing bogus data to the rest of the network?  Someone malicious can effectively DoS a significant proportion of lite nodes just by setting up a thousands of fake peers that connect to as many other peers as possible and all give out the same incorrect data.  It might take more work for nodes to sort it out than if you just decided to be a full node (credit to Casascius for this argument).

This goes back to the original source of this thread:  an overlay network makes sense in some contexts, but perhaps using an alt-chain secured through merged mining might be a better alternative (albeit more complex).

Under what criteria does a node decide that important data is correct in an overlay network if there is no way to compare directly to the blockheaders?   It seems that to do this in a decentralized manner without an alt-chain,  you have to trust whatever information is given to you by the majority of your peers.  But peers are cheap and easily spoofed.  One resourceful attacker can muck up the entire network with a million fake nodes.  This is where an alt-chain is beneficial:

--In a non-alt-chain network, you need a majority of nodes telling you the correct answer to end up with the correct answer
--With an alt-chain secured through merged mining, it only takes only one honest node for you to get the correct answer (verified through proof-of-work), even if the other 999 peers are malicious

Unfortunately, my understanding of merged mining and Stratum's overlay network is really weak.  Please fill me in if I'm missing the mark.

[fivebells]

I don't follow.  The proposal in this thread suggests that there would be a second chain, and it's purpose would be for nodes to securely exchange pruned/compressed blockchain snapshots.

  You're right,  I was confused.  Thanks.

[MoonShadow]

In fact, Startum does eactly what you seem to want to do both decentralized and without an alt-chain.

Sorry, I'm not familiar with the Stratum alternative.  If there is no alt-chain for verification, what is stopping malicious nodes from distributing bogus data to the rest of the network? 

Stratum uses a different model.  I'm not one of the developers, so I only understand what the intent is; but each stratum server is a full bitcoin client first, and also participates in the secondary network.  The stratum servers don't depend upon each other to do anything outside of what the bitcoin network already does.  The stratum protocol functions as a controlled spigot to the bitcoin network firehose.  A stratum capable client can query a single stratum server that the user trusts (because he has a service paid for, or because he personally set up that particular server) and privately query the stratum server for data about particular addresses or transactions.  The client, should it not trust any particular server, can reach out to several stratum servers in a semi-random way (either biased towards servers that it has contacted before and not be told falsehoods, or by some other method) and query multiple servers and check responses against each other.  It provides a standard method for a single full bitcoin node to function as the blockchain to hundreds or thousands of light clients, that may or may not actually maintain either block headers or transaction inputs.  Like a distributed version of a split wallet service, like BitcoinSpinner without the vendor lock-in.

 Someone malicious can effectively DoS a significant proportion of lite nodes just by setting up a thousands of fake peers that connect to as many other peers as possible and all give out the same incorrect data.  It might take more work for nodes to sort it out than if you just decided to be a full node (credit to Casascius for this argument).

That a remote possibility, but again most of the light clients that we expect to see in the future will be desktop apps that don't mine but are still capable of switching to full node mode at will or by user direction.  If the stratum network is being DDOSed, or is otherwise unreachable, most (probably not all) such clients would simply jump directly onto the main bitcoin network to acheive their ends.  This is likely to cause problems in it's own right, but the option always remains open.

This goes back to the original source of this thread:  an overlay network makes sense in some contexts, but perhaps using an alt-chain secured through merged mining might be a better alternative (albeit more complex).

I'm skeptical of that, myself.  I will reserver my final judgement based upon what you can show me later.

Under what criteria does a node decide that important data is correct in an overlay network if there is no way to compare directly to the blockheaders? 

First, it can compare to local blockheaders, it's just not limited to that.

Second, see above about checking several servers against each other, or simply running your own stratum server at home for use on your android.

 It seems that to do this in a decentralized manner without an alt-chain,  you have to trust whatever information is given to you by the majority of your peers.  But peers are cheap and easily spoofed.  One resourceful attacker can muck up the entire network with a million fake nodes.  This is where an alt-chain is beneficial:

You make that sound like that's easy to do, or cheap.  Yes, such an attack vector is possible under thin conditions.  Still, it's potential gain is limited to what the spoofed client is willing to send or what he believes that he has received, not all he has.  I can't see all that kind of effort just to steal my lunch money.  If you're buying a new car with bitcoin, you're going to be taking some more deliberate steps anyway.  The general trend is that security & convience are at odds to each other, and these light clients are intended for convience with relative security, not the full absolute security that a hardened full client could provide while also running it on a cell phone.  This also doesn't consider the use of risk assessment algos.  For example, if your client tries to reach out to the stratum network to check a transaction sent to itself, but can't connect to your personal stratum server, so it falls back to polling 8 random servers & eight servers from within it's own 'good' history.  It gets back all the right responses, but the version number of the nodes it knew about all have different checksums than last time.  Could be that you haven't used this app in a while and everyone really has upgraded, or it could be that you've been corralled into a honey-pot network.  The client notifies you of it's risk assesment, you can either take the transaction on faith or reject it and refuse to hand over the product.

--In a non-alt-chain network, you need a majority of nodes telling you the correct answer to end up with the correct answer

True.  You also need the same from an alt-chain just to be able to have one.  That only shifts the problem across time, it does not change teh problem logically.

--With an alt-chain secured through merged mining, it only takes only one honest node for you to get the correct answer (verified through proof-of-work), even if the other 999 peers are malicious

Once the block has been created, true.  Not true while the block is being settled upon.  This is why bitcoin, itslef, requires 6 confirmations before the standar client will resend the coins.

Unfortunately, my understanding of merged mining and Stratum's overlay network is really weak.  Please fill me in if I'm missing the mark.

My understanding of merged mining is limited, but my understanding of regular proof-of-work is not.  That said, as I undertstand it, merged mining permits the alt chain to leverage bitcoin's securlty to shore up it's own; generally by inerweaving specially identified transactions into the bitcoin blocks, while interweaving all or part of the last bitcoin block's header into the alt-chains's header; thus proving a time sequence in lockstep with bitcoin's own.  While this little hack would permit a mnor alt-chain to benefit from the securty of the bitcoin blockchain, it does nothing that I know of to actually improve teh trustworthyness of the miners that created the alt-chain block to begin with.  Does namecoin do this?