Separating timestamp function and verification function

[TierNolan]

Bitcoin merges these 2 functions.  The block chain creates a well defined ordering of blocks and also confirms that they are verified.

You could have 2 separate chains for this purpose.

The timestamp chain would timestamp a merkle root.  The leaf nodes would have no specific meaning.  It would only create an ordering of leaf nodes, rather than specify the exact time.  There is no verification performed on the timestamp chain, except that it meets POW.

The verification chain would act the same way as the current chain, except that the blocks would not have any proof of work requirement.  The header would include proof that it was included in the timestamping chain and a link to the previous verification block.

If there is a fork in the verification chain, then the block which occurs earliest in the timestamp chain would win (assuming both were actually valid blocks).  The timestamp chain would inherently order its leaves.

So, verifiers would collect minting and tx fees.  They would pay miners to timestamp their block.  They would add a requirement that no alternative block from the same chain be included in the timestamp block.

This means that the miners still get paid, so it encourages hashing of the timestamp chain.

This is effectively merged mining against a pure timestamp chain.

It creates an ordering of all transactions between all chains.  This allows atomic transfers between chains, as long as the chains in question allow a reference to the timestamp block number.

The timestamp chain doesn't even need to include the full merkle tree.  It would be a pure header system.  When a verifier asks a miner to miner his block's hash, the miner could send back the root and path to the verifier.  The verifier just has to watch the main chain and can submit his block to the local chain if he he sees that root.

[jgarzik]

Certainly.  One way for bitcoin to scale is making the primary, strong chain just timestamp another chain.

However, you still must pay miners.

[TierNolan]

However, you still must pay miners.

As I said, verifiers would pay timestampers.

You could auction off the slots.  The price per node would drop by a factor of 2 as you get further from the root node.

[Peter Todd]

Actually there are some subtle flaws possible with PoW schemes where you can't easily tell what any given leaf is for, especially if you want to define total difficulty such that subsequent miners add to it regardless of what chain they are mining: PoW reuse and PoW hiding. Basically you don't want it to be possible to use a PoW twice, and you also don't want to make it easy to hide the chain that was worked on and reveal it after the fact.

The latter problem essentially comes down to the fact that you don't want it to be possible for a lot of work to be done on a chain - adding blocks to it - without that being public knowledge. PoW schemes don't have that problem generally because they assume no on entity controls more than 50% of the hashing power. The chain can only be extended by being public so lots of people work on it.

But with a timestamping scheme the whole point is to let the chain be extended by people who aren't involved with your currency, and may not even know it exists. But lets jump to problem #1 again for a second.

If your timestamping scheme's merkle tree allows the block hash for the chain to be placed anywhere in the tree's roots someone can mine two blocks at once. This is bad because no node can know which of the two blocks is correct, and making one of the blocks preferred by a rule like "lowest block hash wins at a given height" causes convergence problems. (you can withhold a particularly good solution and release it after someone finds another block, making the best block tip your block again and resetting the confirmation)

The former problem has an (attempted) solution in the merged mining specification by having a system of slots for each alt-coin mined, and making the order of those slots deterministic. Unfortunately it's broken and doesn't work. FWIW this actually got implemented due to a slightly different and more serious problem: early attempts at merge mining still defined the block hash as the hash of the alt-chain's header, so you could mine multiple blocks in one go. A better merge mining system re: PoW re-use would be some kind of defined path, basically from the tip of the tree "go left, then right, then right, then left etc." in a long sequence, and provided the path follows the right sequence it's valid, but that's maybe a little lower level than the overall ideas I'm describing here.

Going back to problem #2, lets suppose chain height was defined as increasing for every "timestamp" block added to the overall chain. If #1 isn't solved, you can just mine the occasional block here and there, hold that back, and then suddenly tell the world "Hey! Look at this really long chain I have!", deceiving clients into thinking they're on a valid chain. It's not an insurmountable problem - carefully chosen rules to chose what the best block may be solve it - but it makes SPV clients quite a bit more complex and the whole issue needs to be very carefully considered. AFAIK no-one has done the research required to do this properly.

I know I haven't explained the issue fully, but that's kinda my point: even after seven paragraphs of text I'm not even close to talking about all the subtle issues and no-one is really sure if there are even more subtle problems inherent in these ideas. It'd be nice if some alt-coins explored them, but that's a lot more work than pump-n-dump schemes...

[gmaxwell]

Actually there are some subtle flaws possible with PoW schemes where you can't easily tell what any given leaf is for, especially if you want to define total difficulty such that subsequent miners add to it regardless of what chain they are mining: PoW reuse and PoW hiding. Basically you don't want it to be possible to use a PoW twice, and you also don't want to make it easy to hide the chain that was worked on and reveal it after the fact.

There is perhaps an even more subtle point to make here— what Bitcoin does isn't _just_ proof-of-work. It's also a kind of proof-of-honest-belief: Because work is expensive if you work on an invalid or otherwise losing chain its almost certain that your work will be lost. If you work on a good chain your work is an investment which is preserved in the continued value of that chain.  Sort of like the idea of how attaching a real money market to predictions makes people make more honest predictions.

If you decouple PoW too much from validation then PoW no longer constitutes costly-work-at-stake and thus can't demonstrate commitment to a single particular solution.

[mmeijeri]

Bitcoin merges these 2 functions.  The block chain creates a well defined ordering of blocks and also confirms that they are verified.
The timestamp chain would timestamp a merkle root.  The leaf nodes would have no specific meaning.  It would only create an ordering of leaf nodes, rather than specify the exact time.  There is no verification performed on the timestamp chain, except that it meets POW.

Why would the timestamp chain even contain the leaf nodes? Why not make it a generic timestamping chain for more than just currencies?

[Peter Todd]

If you decouple PoW too much from validation then PoW no longer constitutes costly-work-at-stake and thus can't demonstrate commitment to a single particular solution.

Excellent points.

To simplify things you can basically say merge mining in general has this problem that because you are mining multiple chains, and thus have multiple sources of profit, the actual investment in mining any one chain is low so you're incentive to validate and do the job properly is less.

[TierNolan]

Actually there are some subtle flaws possible with PoW schemes where you can't easily tell what any given leaf is for, especially if you want to define total difficulty such that subsequent miners add to it regardless of what chain they are mining: PoW reuse and PoW hiding. Basically you don't want it to be possible to use a PoW twice, and you also don't want to make it easy to hide the chain that was worked on and reveal it after the fact.

Hmm true.

I think an option would be that the POW degrades as you go down the tree (each step reduces it by a factor of 2).  However, that is splitting the POW between chains, which defeats the purpose of combining them.

It still creates an "official" ordering of all blocks across alt-chains, but doesn't re-use POW for all chains.

Going back to problem #2, lets suppose chain height was defined as increasing for every "timestamp" block added to the overall chain. If #1 isn't solved, you can just mine the occasional block here and there, hold that back, and then suddenly tell the world "Hey! Look at this really long chain I have!", deceiving clients into thinking they're on a valid chain. It's not an insurmountable problem - carefully chosen rules to chose what the best block may be solve it - but it makes SPV clients quite a bit more complex and the whole issue needs to be very carefully considered. AFAIK no-one has done the research required to do this properly.

An orphan chain like that wouldn't count, since it would have lower total POW.

[Peter Todd]

It still creates an "official" ordering of all blocks across alt-chains, but doesn't re-use POW for all chains.

Remember that to create an actual ordering of blocks between two different chains, just use timestamps. Take the block header of chain #1 and get it timestamped in chain #2 and vice-versa. Now it's not official because unless you have the most tightly constrained possible timestamp you never know if someone will reveal a more tight constraint later, but for many purposes that unofficial ordering might be enough.