Once each block has those, then how can an attacker rewrite the history?
It's very easy for an attacker to rewrite history. Suppose normal chain has blocks A1, A2, A3 which reference T1, T2, T3.
Attacker will create alternative blocks A1', A2', A3' which also reference T1, T2, T3.
Perhaps he won't be able to create block A4 before T4 is known, but this has nothing to do with rewriting history.
Once things go past the +/- 1 Ti blocks segment, maybe there are ways to overcome the earliest/latest bracketing. Maybe you can point out the obvious way to overcome the entire network checking each submitted block for valid time sequence? It is possible, but it isnt totally wrong.
When you analyze consensus algorithms you should consider behavior of a new node which joins the network and doesn't have any pre-assumptions. So, suppose a new node connects to one honest node and one attacker's node. Suppose honest node gives it a chain which ends with A1...A100 and attacker's chain ends with blocks A1'...A100'. How can a new node tell which of them is valid? Timestamps don't help here.
It can be mathematically proven that your block-base timestamps are no better than ordinary UNIX timestamps, assuming that node clocks aren't horribly out of sync.
I believe your mathematical proof is not using the proper assumptions. Of course you can make some assumptions to prove what you say, but a bigger context can provide the external reference for the bootstrapping node.
With many chains all part of the system, they will all have hashes from the other chains. Wouldnt that require an attacker to compromise the majority of participating chains?
Even assuming the attacker has more than half the nodes, the new node will see many with A1... A100 along with the A1'...A100', however on all the other chains the A1'...A100' is not there.
So all the participating chains provides security to all the other chains. If each chain specifies which external chains they find as valid, this will prevent an attacker to set up a bunch of fake external chains.
Thank you for specific example. this is what is needed to make a bullet proof system. I believe you are agreeing that the sequence server does work for nodes that are current and the issue was the history attack. Let me know how you can mathematically prove that having a set of external chains cross verifying each other cannot provide an external reference for a bootstrapping node. Bootstrapping a node is a different case than confirming blocks, so it might be more than one method is needed to cover both aspects.
James
P.S. While I would like the BTC chain to also have the data, clearly it wont go into the bitcoin core, so the problem of how to validate data in the BTC chain needs to be solved before that can be used