aaaxn
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 05, 2013, 11:55:19 AM |
|
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.
|
|
|
|
Nite69
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 05, 2013, 12:01:27 PM |
|
+1
|
Sync: ShiSKnx4W6zrp69YEFQyWk5TkpnfKLA8wx Bitcoin: 17gNvfoD2FDqTfESUxNEmTukGbGVAiJhXp Litecoin: LhbDew4s9wbV8xeNkrdFcLK5u78APSGLrR AuroraCoin: AXVoGgYtSVkPv96JLL7CiwcyVvPxXHXRK9
|
|
|
Nite69
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 05, 2013, 12:04:06 PM |
|
hmm.. keep the balances on other chain.. would we get the same result, if the protocol forces that all inputs of a certain address is used if any of them is used? This way, the latest output is *allways* the balance of that address.
Edit; of course not. If a payment comes to that address later.. but maybe the new transaction might include the destination address as an input to that payment, even without sercet key?
|
Sync: ShiSKnx4W6zrp69YEFQyWk5TkpnfKLA8wx Bitcoin: 17gNvfoD2FDqTfESUxNEmTukGbGVAiJhXp Litecoin: LhbDew4s9wbV8xeNkrdFcLK5u78APSGLrR AuroraCoin: AXVoGgYtSVkPv96JLL7CiwcyVvPxXHXRK9
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 05, 2013, 08:19:28 PM Last edit: May 05, 2013, 11:15:19 PM by bitfreak! |
|
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. Hmmm... I think I see what you are getting at here. The attacker generates a fake chain in the background using the real proof chain but a fake account tree. He outpaces the real mini-blockchain for a full cycle until there's no evidence left to indicate his account tree is fake and releases the fake chain. That would be one hell of an attack to pull off and even after pulling it off there's a low chance the fake account tree would propagate enough to become the main account tree. But this just goes to show the mini-blockchain does need to hold at least maybe a week or more worth of transaction history. Although I think one possible way to dramatically minimize the threat of this attack is to make it so a node who has been connected to the network for a while will only accept a different chain with more power if they know where the chain came from, that it didn't just pop out of thin air. For example a node who has been validating blocks longer than the cycle of the mini-blockchain can simply ignore a new chain if it appears to that node as if the chain popped out of no where. This will still allow the normal process of block orphaning to occur because the chains do not pop out of no where in that case.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 05, 2013, 11:56:41 PM |
|
With the solution I described in my last post, the attacker would only succeed if he convinced enough new nodes to accept his fake chain and together they could supply more hashing power to the fake chain than the older nodes to the real chain. While that seems virtually impossible it may be some what possible if the attacker continues to contribute hashing power even after tricking new nodes to accept the chain. Because obviously this attacker must have an ungodly amount of hashing power to outpace the real mini-blockchain for a full cycle.
One way to really drill the final nail into the coffin of this attack might be this: if a new node detects two full mini-blockchain's which both originate from the same proof chain it can simply resort to a peer vote system by asking older nodes which chain is the valid one. Legitimate older nodes who noticed the fake chain appear out of thin air would reply to the new node telling them not to trust the one which appeared to come out of no where. Now the attacker would have an extremely hard time getting enough slaves in on his little scheme.
Even if the attacker had a huge botnet at his disposal at least 80 to 90 percent of existing and new nodes would reject the fake chain and continue working on the real chain. Soon enough the attacker wouldn't be able to afford continuing the attack and he would give up. The real mini-blockchain would quickly overtake the fake chain once the attacker stopped contributing his hashing power to it. With these mechanisms in place the attacker has no hope of convincing more than half the network to use his fake chain.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
aaaxn
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 08:09:42 AM |
|
That would be one hell of an attack to pull off and even after pulling it off there's a low chance the fake account tree would propagate enough to become the main account tree. But this just goes to show the mini-blockchain does need to hold at least maybe a week or more worth of transaction history.
If it would be longer than main chain nodes would switch to it and start extending it so it would definitely propagate. Although I think one possible way to dramatically minimize the threat of this attack is to make it so a node who has been connected to the network for a while will only accept a different chain with more power if they know where the chain came from, that it didn't just pop out of thin air.
For example a node who has been validating blocks longer than the cycle of the mini-blockchain can simply ignore a new chain if it appears to that node as if the chain popped out of no where. This will still allow the normal process of block orphaning to occur because the chains do not pop out of no where in that case.
I think simplest solution is to forbid nodes to switch to other chain if its divergence from current chain happened before range of mini blockchain. How many previous blocks node stores could be customizable parameter. Professional machines could keep longer history if they wish while client nodes could store just default length ( month or so ). One way to really drill the final nail into the coffin of this attack might be this: if a new node detects two full mini-blockchain's which both originate from the same proof chain it can simply resort to a peer vote system by asking older nodes which chain is the valid one. Legitimate older nodes who noticed the fake chain appear out of thin air would reply to the new node telling them not to trust the one which appeared to come out of no where. Now the attacker would have an extremely hard time getting enough slaves in on his little scheme.
I think new nodes in this situation (it should be extremely rare or never) should just query nodes for blockchain all the way to block in which competing chains diverged and if no one around has this long history node should just refuse to operate and wait until thing settle. Or it can be advised to download updated client which should in this situation contain hardcoded checkpoint provided by community pointing to right chain.
|
|
|
|
aaaxn
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 08:31:05 AM |
|
I would advise to update address structure proposed in this paper. I think binary hash tree would be better. Your proposal would require to constantly make hashes over vast amounts of data (all sector hashes) so this data would need to be kept in memory. Moreover with accounts packed in 1000 blocks there is also a lot of data to hash and as transactions would be randomly distributed to all sectors large portions of tree would need to be recalculated in every block. With binary tree you would always need to update just 2 * LOG(N) hashes per transaction and all hashes would be made over fixed length strings. N is number of accounts in tree. This way only small subset of tree would need to be kept in memory.
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 09:00:56 AM |
|
If I recall correctly maximum information density is achievable at numeral system based on number e (2.718). So triple hash tree could be better than binary one.
|
|
|
|
aaaxn
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 09:22:14 AM Last edit: May 06, 2013, 09:38:12 AM by aaaxn |
|
If I recall correctly maximum information density is achievable at numeral system based on number e (2.718). So triple hash tree could be better than binary one.
Maybe in theory but from practical point o view binary trees fit nicely in binary world ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) First thing which comes to my mind is that transaction would probably operate on account offsets to save space. When you have offset all you have to do is read its binary representation bit by bit and you get exact path you need to follow in binary tree to reach this node. It would require more work on ternary tree. I found that binary trees have already been discussed ( with nice diagrams ) in context we are talking about. Its was for unspent txouts, but we would just use account balances. https://en.bitcoin.it/wiki/User:DiThi/MTUThttps://bitcointalk.org/index.php?topic=88208.0
|
|
|
|
Impaler
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 826
Merit: 250
CryptoTalk.Org - Get Paid for every Post!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 10:27:02 AM |
|
How dose this solution compare to Ripple, your ledger system looks similar to what I hear it uses but the mini block chain gives a bit 'memory' then I think Ripple has, you seem to have elegantly combined both concepts here and gotten the strengths of both, I'm going to tell the other FRC developers about it, our lead has expressed interest in doing block-chain trimming.
|
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 10:40:55 AM |
|
I haven't really looked into it but Ripple appears to use some sort of pseudo-centralized solution. I don't think the coins were created in a decentralized way. And there was just a thread about a Ripple account being hacked because of a weak password or something. So the accounts even appear to be centrally managed.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
GCInc.
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 06, 2013, 08:07:34 PM |
|
I admire the ingenuity of this idea.
Now, projecting the potential timelines this opportunity casts, how feasible would it be for Bitcoin to adopt such a mini-chain at a future point in time? Technically and theoretically I mean, casting the massive political obstacles out of the way. Rather simple to convert the full blockchain to mini and proof when the open source framework (from this new crypto) is available, no?
|
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 01:53:25 AM |
|
how feasible would it be for Bitcoin to adopt such a mini-chain at a future point in time? Probably pretty unfeasible. Even something like the "rolling chain" idea mentioned in the paper would be extremely tricky to implement with Bitcoin. I spent a lot of time thinking about ways the Bitcoin blockchain could be made much smaller but the only thing I could really come up with was to create a whole new crypto-currency.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
Etlase2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 02:03:50 AM |
|
One way to really drill the final nail into the coffin of this attack might be this: if a new node detects two full mini-blockchain's which both originate from the same proof chain it can simply resort to a peer vote system by asking older nodes which chain is the valid one. Legitimate older nodes who noticed the fake chain appear out of thin air would reply to the new node telling them not to trust the one which appeared to come out of no where. Now the attacker would have an extremely hard time getting enough slaves in on his little scheme. What you are trying to accomplish to fix your problem here is an uninformed, relatively untrustworthy consensus (how does a new node know which nodes are legitimate?). The two part amazing solution is to use a proof of consensus system that does not rely on proof of work. Much more secure, much more energy efficient. I wasn't lying when I said I've already solved the problems of doing this. Even if the attacker had a huge botnet at his disposal at least 80 to 90 percent of existing and new nodes would reject the fake chain and continue working on the real chain. Soon enough the attacker wouldn't be able to afford continuing the attack and he would give up. The real mini-blockchain would quickly overtake the fake chain once the attacker stopped contributing his hashing power to it. With these mechanisms in place the attacker has no hope of convincing more than half the network to use his fake chain.
He can still repeatedly get away with double spending.
|
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 02:18:34 AM |
|
What you are trying to accomplish to fix your problem here is an uninformed, relatively untrustworthy consensus (how does a new node know which nodes are legitimate?). It doesn't know. That's why it's a vote system. The node assumes that the majority of votes will be from legitimate nodes. Of course that wont always be the case but it will be the case at least 80% of the time. He can still repeatedly get away with double spending. An attacker with enough power to outpace the blockchain for a day or more is obviously going to get away with something. Even in Bitcoin an attacker with that much power over such a long period of time could do a bit of damage. But it's still not a true form of double spending, it's a temporary illusion, and if the attacker had a hard time getting any other node to accept his fake chain wouldn't it be virtually impossible for him to achieve a double spend?
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
Etlase2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 02:27:39 AM |
|
It doesn't know. That's why it's a vote system. The node assumes that the majority of votes will be from legitimate nodes. Of course that wont always be the case but it will be the case at least 80% of the time. But the basic rule of defending against a sybil attack is that the majority cannot be trusted. An attacker with enough power to outpace the blockchain for a day or more is obviously going to get away with something. Even in Bitcoin an attacker with that much power over such a long period of time could do a bit of damage. But it's still not a true form of double spending, and if the attacker had a hard time getting any other node to accept his fake chain wouldn't it be virtually impossible for him to achieve a double spend?
I actually should have said, he can get away with almost anything against a node that hasn't been around recently. And yes, the same is true of bitcoin. Lots of bad things can be accomplished when you rely on hashing power to determine who is right. Hell, new nodes won't have any idea of whom to trust. Grabbing thousands or millions of IPs is easy; will be drastically easier when IPv6 is the standard. There IS a way to return to the at-worst bitcoin 51% attack while reducing storage, and that is keeping a historic record for at least a year. Keep the hash of the account ledger rolling through each block, have each tx spend from the ledger not previous txouts, and work from there. If a node was suspicious at the validity of someone's block, they could request its history and hashing power proof over that year or whatever seems reasonable. At least then it's not all time. Compressed account ledger and 1 year of tx history+hashing power is pretty solid proof that it's the real chain. It still requires proof of work though which means it can be 51% attacked and it wastes a boatload of energy for nothing useful when it can be done a better way.
|
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 02:41:41 AM |
|
But the basic rule of defending against a sybil attack is that the majority cannot be trusted.
Yes that is a valid point but all the older legit nodes can still be trusted, there's no way the attacker can trick them. Not only would the attacker need a boatload of hashing power but also a boatload of IP's and bandwidth to out number the legit nodes. Of course that is still possible so perhaps the best method to solve this problem would not be a voting system but the solution aaxon suggested: I think new nodes in this situation (it should be extremely rare or never) should just query nodes for blockchain all the way to block in which competing chains diverged and if no one around has this long history node should just refuse to operate and wait until thing settle. Or it can be advised to download updated client which should in this situation contain hardcoded checkpoint provided by community pointing to right chain. That pretty much seems like the best solution because it would cut new nodes out of the picture and leave the legit nodes to wear down the attacker until he gives up.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
Etlase2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 02:52:04 AM |
|
Yes that is a valid point but all the older legit nodes can still be trusted, there's no way the attacker can trick them. Not only would the attacker need a boatload of hashing power but also a boatload of IP's and bandwidth to out number the legit nodes. IPs and bandwidth are hardly issues. Many theoretical attacks should propose "what kind of defense do you have if you're surrounded by bad nodes?" It doesn't necessarily mean the system is weak if it fails to pass these tests, but it does mean it has weaknesses. That pretty much seems like the best solution because it would cut new nodes out of the picture and leave the legit nodes to wear down the attacker until he gives up.
It's also effectively DDoSing the network for lite clients. I'm just sayin'...
|
|
|
|
bitfreak! (OP)
Legendary
Offline
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 03:01:36 AM |
|
It's also effectively DDoSing the network for lite clients. I'm just sayin'...
You'll need to elaborate, I don't understand what you mean.
|
XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
|
|
|
Etlase2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 07, 2013, 03:12:44 AM |
|
If lite clients shut down in the face of competing chains, commerce cannot continue. aaaxn states that it should rarely be a problem, but the problem exists when someone is making a coordinated attack against the network. These are issues with bitcoin as well, there is nothing particularly wrong with your idea, it just allows for completely forking networks. SPV clients (lite clients) AFAIK can work because hash trees can be used to prove the existence of txouts deep in the chain. That can't be done here because the hash tree disappears after a short period of time, being replaced by a ledger. You have to hope that someone does not perform a sustained attack where they ruin other miner's profitability in an effort to get them to leave, then unleash a devastating attack where they *could* rewrite balances. Some full nodes would complain (full nodes only being run as altruistic measures, yay), but they'd have no chain to champion. Very dire situation.
|
|
|
|
|