[white paper] Purely P2P Crypto-Currency With Finite Mini-Blockchain

[aaaxn]

Now attack scenario. Suppose there is attacker with more than 50% of hashing power. He takes hash of current best block N and tries generating a next one but instead of using real account database he just create new one in which he holds all coins. If he is able to keep this chain in front of original one for as long as original network looses block N contents he can reveal his chain and it would look perfectly valid for all nodes because they lost track of how account database looked on block N.

It looks like algorithm presented in this paper is only as secure as mini blockchain is secure and if attacker could sustain 51% hashing power for as long as mini blockchain cycle completes it could cause much more severe problems than in bitcoin, because attacker could rewrite entire account balances database and not just make some double spends.

Essentially Bitcoin has the same risk for clients that don't download the entire transaction history, and the solution is the same which is to ask the peers that have the relevant transaction history to prove which chain is not valid.

On further thought, aaaxn's proposed attack is impossible if the cryptographic hash used to construct the Account Tree and Proof Chain can't be preimaged.

Because there is no way the attacker can find a suitable set of replacement addresses and balances to match the hash in the Proof Chain.

Thus all the discussion that followed aaaxn's post above regarding centralization and the need to remember transaction data history is irrelevant.

Wow, I didn't think anyone is still discussing this idea but still no one actually tried to implement it

As for the problem, I think you are mistaken. Attacker does not need to match hash in original proof chain. Proof chain contain only hashes, and without accompanying transaction data there is no way to tell if transformation of account tree from state which hashes to A to state with B hash is valid.
When attacker start his own branch he can create new tree and just tell that this hash resulted from set of legal transactions. After full cycle these transactions are lost and no one can prove he lied.

I still don't think it is a problem because we only have problem reaching consensus in short term. No one will have any problem with determining if blockchain which tries to overwrite few months of history is legitimate or not.

[ondratra]

Read first few pages - it sounds awesome! If you will need any help from web developer in future you can count on me

[AnonyMint]

Now attack scenario. Suppose there is attacker with more than 50% of hashing power. He takes hash of current best block N and tries generating a next one but instead of using real account database he just create new one in which he holds all coins. If he is able to keep this chain in front of original one for as long as original network looses block N contents he can reveal his chain and it would look perfectly valid for all nodes because they lost track of how account database looked on block N.

It looks like algorithm presented in this paper is only as secure as mini blockchain is secure and if attacker could sustain 51% hashing power for as long as mini blockchain cycle completes it could cause much more severe problems than in bitcoin, because attacker could rewrite entire account balances database and not just make some double spends.

Essentially Bitcoin has the same risk for clients that don't download the entire transaction history, and the solution is the same which is to ask the peers that have the relevant transaction history to prove which chain is not valid.

On further thought, aaaxn's proposed attack is impossible if the cryptographic hash used to construct the Account Tree and Proof Chain can't be preimaged.

Because there is no way the attacker can find a suitable set of replacement addresses and balances to match the hash in the Proof Chain.

Thus all the discussion that followed aaaxn's post above regarding centralization and the need to remember transaction data history is irrelevant.

Wow, I didn't think anyone is still discussing this idea but still no one actually tried to implement it

As for the problem, I think you are mistaken. Attacker does not need to match hash in original proof chain. Proof chain contain only hashes, and without accompanying transaction data there is no way to tell if transformation of account tree from state which hashes to A to state with B hash is valid.
When attacker start his own branch he can create new tree and just tell that this hash resulted from set of legal transactions. After full cycle these transactions are lost and no one can prove he lied.

I believe you are mistaken.

The Account Tree is a hierarchy of hashes and the single hash at the top of the tree is stored in the Proof chain. Thus in order to create an alternative history for the Account Tree, the adversary would need to construct an Account Tree history (at each block interval) which matches the Proof chain hashes (for each block) because the history of the Proof chain is never discarded. This can not be mathematically accomplished in log O(log N) time (i.e. not in exponential time) if the hashing algorithm approximates a Random Oracle or actually less restrictively for as long as it can't be preimaged, i.e. if a cryptographically secure hash is employed.

I still don't think it is a problem because we only have problem reaching consensus in short term. No one will have any problem with determining if blockchain which tries to overwrite few months of history is legitimate or not.

All that consensus discussion upthread has been rendered irrelevant by my assertion above. TADA!

[aaaxn]

I believe you are mistaken.

The Account Tree is a hierarchy of hashes and the single hash at the top of the tree is stored in the Proof chain. Thus in order to create an alternative history for the Account Tree, the adversary would need to construct an Account Tree history (at each block interval) which matches the Proof chain hashes (for each block) because the history of the Proof chain is never discarded. This can not be mathematically accomplished in log O(log N) time (i.e. not in exponential time) if the hashing algorithm approximates a Random Oracle or actually less restrictively for as long as it can't be preimaged, i.e. if a cryptographically secure hash is employed.

Transactions included in block describe operations which you have to do on current account tree to get updated version of this tree.
In block N Account Tree was in state X. We apply transactions and get state Y. Hashes of account tree in both states are included in adjacent blocks. Question is: what information do we need to verify if set of transactions which caused transition from state X to state Y obeyed network rules? Hashes in Proof Chain are not enough, they are just random strings for outside observer. Full Account Trees in both states are potentially not enough too (maybe txns in block N really sent all existing coins to single address ?). We need transactions. (BTW: header of transactions tree also need to be in proofchain).

I still don't think it is a problem because we only have problem reaching consensus in short term. No one will have any problem with determining if blockchain which tries to overwrite few months of history is legitimate or not.

All that consensus discussion upthread has been rendered irrelevant by my assertion above. TADA!

In real world - yes. Just imagine what would happen if suddenly someone would emerge with longer bitcoin blockchain invalidating months of current blockchain. We would get a patch in no time with hardcoded checkpoint just after branching. Same thing will happen with any future sufficiently important cryptocurrency, so why keep pretending wee need system to resolve such conflicts in software?

[AnonyMint]

Question is: what information do we need to verify if set of transactions which caused transition from state X to state Y obeyed network rules? Hashes in Proof Chain are not enough, they are just random strings for outside observer. Full Account Trees in both states are potentially not enough too (maybe txns in block N really sent all existing coins to single address ?). We need transactions. (BTW: header of transactions tree also need to be in proofchain).

You are still not grasping the mathematical point I made. There is no mathematical way to create an Account Tree in each block that is different from the only one that will hash to the hash value in the Proof Chain.

The Proof Chain guarantees that the Account Tree chain is not an imposter, even if the history of the Account Tree is discarded.

[aaaxn]

Question is: what information do we need to verify if set of transactions which caused transition from state X to state Y obeyed network rules? Hashes in Proof Chain are not enough, they are just random strings for outside observer. Full Account Trees in both states are potentially not enough too (maybe txns in block N really sent all existing coins to single address ?). We need transactions. (BTW: header of transactions tree also need to be in proofchain).

You are still not grasping the mathematical point I made. There is no mathematical way to create an Account Tree in each block that is different from the only one that will hash to the hash value in the Proof Chain.

The Proof Chain guarantees that the Account Tree chain is not an imposter, even if the history of the Account Tree is discarded.

And you are not grasping the point that you don't need to create different account tree with same hash as real one to cheat the system. Hash tree changes from one block to other and that's when you cheat. In next block (of your alternate proofchain) you just provide hash of tree which was not result of applying valid transactions to previous state but just made out of thin air. Without transactions you cant prove it's invalid.

[AnonyMint]

Transaction history is retained for some reasonable window of time, e.g. a month.

To present to the network a blockchain which differs from the one others have, the only possible way is the differences must originate from before the retained transaction history (or the differences must include only transactions the attacker can sign which is same vulnerability in Bitcoin), because the attacker can't sign transactions for which he doesn't hold the private key.

Your only valid point is that if someone has significantly more than the network hashrate, they can compute a fake Proof Chain going back to before the retention window of transaction data, then they could claim any Account Tree they wish to.

Then you claim that nodes who have not always been online since the time of the deviation of the Proof Chain would not know which blockchain to trust (they would naturally trust the one with more hashrate).

But Bitcoin has a similar vulnernability, in that nodes would not know which transaction history to trust, i.e. the coinbase coins rewards that were for the miner could be awarded to the attacker. Fact is that there are records on the internet kept and so no one wold dare try this, because it would be front page news.

Thus your argument is silly. Copies of the valid Proof Chain will be stored all over the internet. Anyone trying to go back months and change the Proof Chain is going to be thwarted by the power of human communication.

Orphaned chains resolve on the order of hours, i.e. one chain doesn't hide from the world for months, then suddenly appear and expect to not be outed by human communication. Impossible.

For both mini-block chain coins and Bitcoin, the attacker would create a fork which no one would follow except for followers that were deviously (or fooled by some very powerful entity that could paint the media story) intent on following the attacker's theft.

[aaaxn]

Transaction history is retained for some reasonable window of time, e.g. a month.

To present to the network a blockchain which differs from the one others have, the only possible way is the differences must originate from before the retained transaction history (or the differences must include only transactions the attacker can sign which is same vulnerability in Bitcoin), because the attacker can't sign transactions for which he doesn't hold the private key.

Your only valid point is that if someone has significantly more than the network hashrate, they can compute a fake Proof Chain going back to before the retention window of transaction data, then they could claim any Account Tree they wish to.

Then you claim that nodes who have not always been online since the time of the deviation of the Proof Chain would not know which blockchain to trust (they would naturally trust the one with more hashrate).

But Bitcoin has a similar vulnernability, in that nodes would not know which transaction history to trust, i.e. the coinbase coins rewards that were for the miner could be awarded to the attacker. Fact is that there are records on the internet kept and so no one wold dare try this, because it would be front page news.

Thus your argument is silly. Copies of the valid Proof Chain will be stored all over the internet. Anyone trying to go back months and change the Proof Chain is going to be thwarted by the power of human communication.

Orphaned chains resolve on the order of hours, i.e. one chain doesn't hide from the world for months, then suddenly appear and expect to not be outed by human communication. Impossible.

For both mini-block chain coins and Bitcoin, the attacker would create a fork which no one would follow except for followers that were deviously (or fooled by some very powerful entity that could paint the media story) intent on following the attacker's theft.

Well, I can only fully agree with you, because that's exactly what I was saying. It is possible, but we don't have to worry about it for reasons you stated.

Side note: bitcoin is slightly more resilient because you can't rewrite history from before of chain spilt, but it doesn't matter anyway.