Truthcoin Talk 2.0

Vitalik talks about an effective attack against POW starting at 52:27 in this video https://www.youtube.com/watch?v=S47iWiKKvLA
This family of attacks can also be used against the truthcoin consensus mechanism.
I will attempt outline an example scenario below:
Lets say that there is a prediction market for a presidential election that Obama won. The attacker bets the wrong way (on McCain), and attempt to convince the votecoin-holders to claim that McCain won.
The attacker makes a contract which gives a bunch of money to votecoin-holders who choose McCain.
If the prediction says McCain wins, then the contract gives 0.01 of the attacker's money units to the owner of every 1 money unit worth of votecoins that chose McCain.
If the prediction says Obama wins, then the contract gives  1.00 of the attackr's money units to the owner of  every 1 money unit worth of votecoins that chose McCain.  Since the market ends on McCain, the attacker only has to pay the smaller amount, which is worth as much as 0.5% of the votecoins.The attacker needs to be able to afford to purchase 50% of the votecoins.

If we use Paul's smoothing constant of 0.9, it is 10x worse. The attacker only needs to afford 5% of the votecoins, and he only has spend as much as 0.05% of the votecoins is worth.This problem only effects Paul's version of rep. My version, which is like colored-coins is immune to this attack.

Moderator Note: Changed title to include "P + e Attack"

Quote from: zack on January 11, 2015, 06:37:13 PM
Vitalik talks about an effective attack against POW starting at 52:27 in this video https://www.youtube.com/watch?v=S47iWiKKvLA

Too busy to watch. I'll leave it to you (or any forum-member) to summarize any relevant parts.

Quote from: zack on January 11, 2015, 06:37:13 PM
Lets say that there is a prediction market for a presidential election that Obama won. The attacker bets the wrong way (on McCain), and attempt to convince the votecoin-holders to claim that McCain won.
The attacker makes a contract which gives a bunch of money to votecoin-holders who choose McCain.
If the prediction says McCain wins, then the contract gives 0.01 of the attacker's money units to the owner of every 1 money unit worth of votecoins that chose McCain.
If the prediction says Obama wins, then the contract gives  1.00 of the attackr's money units to the owner of  every 1 money unit worth of votecoins that chose McCain.  Since the market ends on McCain, the attacker only has to pay the smaller amount, which is worth as much as 0.5% of the votecoins.The attacker needs to be able to afford to purchase 50% of the votecoins.

While I agree that one could do this, you have not shown that there is a unique strategic equilibrium (http://en.wikipedia.org/wiki/Nash_equilibrium) where everyone expects everyone to vote for McCain, and no one can do better. One requirement would be to consider the effect of "counter-contracts" with McCain and Obama swapped, neutralizing the first "contract". Is it just a bidding war with no convergence? VTC-holders have a direct incentive to protect the value of the VTC they purchased by assurance-contracting these counter-contracts into existence. They are rewarded with their own money so this doesn't seem to go anywhere... (either way, it is up to you, not me, to demonstrate that the attack-equilibrium can survive this new choice-dimension).

But, for fun, let's say no one countered the contract.

What if every single voter responds to this by splitting his/her votecoins into two pools: one 98% of their holdings, and the other 2% of their holdings? With the 98% they vote Obama, with the 2% they vote McCain. Each persons' 2% account loses a substantial portion of VoteCoin (in fact, the smallest VTC holder gets a full alpha=.1 wiped out of his 2% account), but each person's 98% account regains exactly as much VTC. There is no net difference to anyone (Authors, Miners, Traders, Voters), other than that every Voter collects "1.00 of the attackr's money units". A direct transfer from the attacker to the VTC holders.

Because anyone can backstab this strategy to exchange lost-VTC for gained-contract-payments, I would expect individuals would increase and decrease that 2% parameter, in relation to the size of the payoff. The only reason that this state of affairs is not a Nash Equilibrium is because the attacker can profitably deviate...by not attacking at all.

Quote from: zack on January 11, 2015, 06:37:13 PM
My version, which is like colored-coins is immune to this attack.

Perhaps you should be a little more measured, given your track record.

PS>They are rewarded with their own money so this doesn't seem to go anywhere
Sorry, I didn't explain clearly. The attacker has to be able to afford to purchase 1/2 of the votecoins. He gives a binding contract to purchase them. The votecoin holders aren't getting their own money back, they are sacrificing their votecoins to get a larger sum of money which the attacker is putting at risk.

PS>But, for fun, let's say no one countered the contract.
These contracts are very expensive to make. I doubt anyone is altruistic enough to throw away so much money.

PS>What if every single voter responds to this by splitting his/her votecoins into two pools: one 98% of their holdings, and the other 2% of their holdings

If you only cheat with 2% of your money, then you are only earning about 2% money as you possibly could. If you know that 98% of people are going to be honest, then you should vote 100% dishonest so that you can take more money from the attacker.

I will make a square showing how much the votecoin-holder can earn in each case, to show Nash equilibrium.
____________|LIE____|HONEST
attack fails____|1.51___|1.5
attack succeeds|1.5____|0

Whether the attack fails or succeeds, it is still in the interest of the votecoin-holders to vote incorrectly.
So, the Nash equilibrium is that the attack will succeed.

Quote from: zack on January 11, 2015, 08:43:59 PM
PZ>They are rewarded with their own money so this doesn't seem to go anywhere
The attacker has to be able to afford to purchase 1/2 of the votecoins. He gives a binding contract to purchase them. The votecoin holders aren't getting their own money back, they are sacrificing their votecoins to get a larger sum of money which the attacker is putting at risk.

Wouldn't it be clearer to just say what the attacker does?

Quote from: zack on January 11, 2015, 08:43:59 PM
PZ>But, for fun, let's say no one countered the contract.
I don't understand "counter the contract".

Imagine all VTC owners collectively have the option to make an assurance contract saying:
"""
The attacker makes a contract which gives a bunch of money to votecoin-holders who choose Obama.
If the prediction says Obama wins, then the contract gives 0.01 of the attacker's money units to the owner of every 1 money unit worth of votecoins that chose Obama.
If the prediction says McCain wins, then the contract gives  1.00 of the attackr's money units to the owner of  every 1 money unit worth of votecoins that chose Obama.
"""
This would be a "counter-contract", because now VTC are being bribed equally, no matter what they do.

Quote from: zack on January 11, 2015, 08:43:59 PM
PZ>What if every single voter responds to this by splitting his/her votecoins into two pools: one 98% of their holdings, and the other 2% of their holdings

If you only cheat with 2% of your money, then you are only earning about 2% money as you possibly could. If you know that 98% of people are going to be honest, then you should vote 100% dishonest so that you can take more money from the attacker.

No, because 1 * 2% = .02, which is more than .01 * 100% = .01.  And this ignores the effect on the VTC market cap.

You did not explain where your numbers come from, so your square proves nothing.

In response to the counter-contract idea: The votecoin-holders could make a bigger counter-contract. Then the outcome of the prediction market will be decided by whoever is willing to spend more money on making the bigger contract.

The attacker makes a contract that says this:
"If Obama wins, then I give 2.01 votecoin worth of cashcoin to every votecoin-holder who voted for McCain and
if McCain wins, then I give 0.01 votecoin worth of cashcoin to every votecoin-holder who voted for McCain"

____________|LIE____|HONEST
attack fails____|2.01___|2
attack succeeds|2.01____|0

Derivation of each number from table explained:
If the votecoin-holder lies, and the attack fails, then he loses his votcoin, but he he gets the 2.01 prize from the attacker to make up for it.
If the votcoin-holder is honest, and the attack fails, then he doubles his votecoin, since he takes the votecoin away from the liar.
If the votecoin holder lies, and the attack succeeds, then he doubles his votecoin, since he takes the votecoin away from the honest votecoin-holder. and he also gets the 0.01 prize from the attacker.
If the votecoin-holder is honest, and the attack succeeds, then he loses his votecoin, and does not get a prize from the attacker, so he has 0.

Quote from: zack on January 11, 2015, 09:50:56 PM
In response to the counter-contract idea: The VTC owners cannot make a contract that spends the attackers funds because they don't know the attacker's private key. They could offer to spend more money. So the outcome of the prediction market will be decided by whoever is willing to spend more money.

They aren't. So the above is not a "response to the counter-contract idea".

Quote from: zack on January 11, 2015, 09:50:56 PM
The attacker makes a contract that says this:
"If Obama wins, then I give 2.01 votecoin worth of cashcoin to every votecoin-holder who voted for McCain and
if McCain wins, then I give 0.01 votecoin worth of cashcoin to every votecoin-holder who voted for McCain"

____________|LIE____|HONEST
attack fails____|2.01 ___|2
attack succeeds|2.01____|0

	0%-LIE	2%-LIE	100%-LIE
Attack Fails	(0.00*2.01)	(0.02*2.01)	(1.00*2.01)
Attack Succeeds	{(0.00*0.01) - x }	{(0.02*0.01) - x }	{(1.00*0.01) - x }

Where x is the (nonzero, evenly-felt) loss of each VTC owner due to the attack. (Of course, in this instance, it happens to make no difference).
We then rank the preferences as follows:

	0%	2%	100%
Fails	#3	#2	#1
Succeeds	#6	#5	#4

Obviously, if every VTC owner used the strategy I outlined for "2%", the attacker would 'Fail', putting us at a stable #2 Nash Equilibrium. By deviating toward 100%, they would risk hitting #4 instead of #1. They can all simultaneously guarantee that they don't trip the attack-success barrier by splitting their vote, as I described. They could even safely split 51% 49% (of their account), but if others split on a different level (for example, 100% 0%), the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50. This is because all the lie-ballots are the same, and will draw for last [or second, or whatever non-first slot] and bleed a proportion of their VTC. Less in those ballots, the less bleeding.

If the votecoin holders give encrypted votes, and the votes are tallied up in a SMPC (Secure Multi-Party Computation), then this vulnerability disappears. It is no longer possible to which way each voter voted.

This solution takes ~1/100th as much time and fees as SMPC:

Say there are 100 votecoin holders in a jury.
Each voter makes their encrypted vote, then they collect all the encrypted votes onto one big page.
Each voter make sure that their own vote is on the page.
Each voter signs the page.
Each voter then creates an un-signed transaction that reveals their vote.It would be impossible for a voter to prove how he voted (unless all 100 voted the same way). So the attacker wont know who to reward.

This seems a little ad hoc. I would prefer to discuss my claim that, fundamentally, such a bribe wouldn't be a problem at all.

Putting all the votes onto one page and having everyone sign the page does not work.
If we cannot tell how they voted, then we cannot redistribute the votecoin.

SMPC would still work, because we can make everyone's votecoin balances encrypted.

>I would prefer to discuss my claim that, fundamentally, such a bribe wouldn't be a problem at all.

Now I am confused. You even made a chart where each row is strictly increasing.
Why do you still think the bribe wont be a problem?

>the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50
I assume you are looking at the row where the attack fails.
When the attack fails, the VTC owners who 100% dishonest earn more money than they would have received from <100% dishonest.
(When the attack succeeds, the VTC owners who 100% dishonest earn more money than they would have received from <100% dishonest)
VTC do get transferred from the dishonest towards honest, so the honest nodes are rewarded in excess of a normal round of voting.
The bribe is big enough to exceed how many VTC are lost _and_ more than make up for how much money they could have made by being honest.
The attacker needs to put a very large amount of money at risk. There is a possibility that 49% of voters will be dishonest, and then the contract will give a ton of the attacker's money to the dishonest voters.

Quote from: zack on January 12, 2015, 12:31:53 PM
Now I am confused. You even made a chart where each row is strictly increasing.
Why do you still think the bribe wont be a problem?

I would only be repeating myself.

I guess I can clarify that the #'s are ranks, not raw payouts (hence the phrase "rank the payouts"), players want to have #1 more than #2. By moving to the right, one risks falling to the second (worse) row. This is pretty clear from the payout table, which has obviously superior 'up' and 'right' directions. The issue is that if >50% of the VTC move right, everyone risks falling to the second row...they will only move right enough to exploit the attacker, and they will want to do this in a very safe way. It is all explained in the first post ("What if every single...").

Quote from: zack on January 12, 2015, 12:31:53 PM
>the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50
I assume you are looking at the row where the attack fails.

No, I am looking at the RBCR from the SVD-consensus code in Truthcoin.

Quote from: zack on January 12, 2015, 12:31:53 PM
When the attack fails, the VTC owners who 100% dishonest earn more money than they would have received from <100% dishonest.
(When the attack succeeds, the VTC owners who 100% dishonest earn more money than they would have received from <100% dishonest)

No. #2 > #4.
#2: (0.02*2.01) = .0402
#4: {(1.00*0.01) - x } = .0100 - x   (x is positive)
( Since you didn't read the table in the first place, I struggle to understand what's to be gained by my explaining the table in the second place... )

Quote from: zack on January 12, 2015, 12:31:53 PM
VTC do get transferred from the dishonest towards honest, so the honest nodes are rewarded in excess of a normal round of voting.
The bribe is big enough to exceed how many VTC are lost _and_ more than make up for how much money they could have made by being honest.

No. Again, you did not read my initial response about the pooling (2%) strategy, so there is nothing to be gained by my repeating it again. Hopefully, anyone who is interested in my response to this can scroll up to "What if every single...". If anyone has specific questions about this example-strategy, I am willing to answer them.

Quote from: zack on January 12, 2015, 12:31:53 PM
The attacker needs to put a very large amount of money at risk. There is a possibility that 49% of voters will be dishonest, and then the contract will give a ton of the attacker's money to the dishonest voters.

The strategy I described attempts to drain this money from the attacker in a safe, incentive-compatible way. You should read about it so that you can point out any flaws in it. However, the fact that failure pays more than success creates attraction in that area, which is already attractive because of x (the VTC market cap).

I agree with you that the votecoin-holders collectively would much prefer the attack to fail, but that just isn't how nash equilibrium work.
Here are a bunch of examples where the nash equilibrium is not the highest pay-out.
*tragedy of the commons. Collective interest is to preserve the public good. Individual interest is to exploit it.
*Crabs in a bucket. They all hold each other down so no-one can climb out. It is in their collective interest to stop climbing, and climb out one at a time, but the nash equilibrium works to trap them all.
*Stampeding crowds of humans fighting to go through a doorway. The collective interest is for orderly lines, the individual interest is to get out first.
*We speak english instead of esperanto or toki pona. The collective interest is towards an easier more precise language, the individual interest is to talk to their peers and not waste time learning multiple languages.

The attack is explained pretty well on lesswrong
http://lesswrong.com/lw/dr9/game_theory_as_a_dark_art/
under the subheading "The Hostile Takeover"

It was in the shareholder's collective interest to sell at the higher price, but because of the greed of a minority, they ended up selling at the lower price.

Quote from: zack on January 12, 2015, 08:56:11 PM
Here are a bunch of examples where the nash equilibrium is not the highest pay-out.

It is you who does not understand how nash equilibria work. They have nothing to do with "the highest payout".

You are instead describing coordination failure, but in my first post I explained how to safely coordinate in a way that is also a NE.

The consensus is such that voters are unable to coordinate. That way the voters cannot make the prediction contradictory to the real world and steal funds from users.

So why do you think the voters will suddenly gain the ability to coordinate every time this attack occurs?

So, it is indeed possible to make a counter-coordination contract to defeat the first contract. However, this does result in a bidding war, and so the wrong answer is going to win if the attacker overpowers the combined weight of altruists (note that that's specifically the weight of _altruists_, or rather in my lingo altruists-prime, not just the combined weight of people who have _any_ incentive to see their preferred outcome win, due to the public goods problem). But an algorithm that works only if the attacker has less economic weight than altruists-prime is a low bar; even naive PoS beats it.

> VTC-holders have a direct incentive to protect the value of the VTC they purchased by assurance-contracting these counter-contracts into existence.

Ah, so that's why we'll have different views on this. My position is that assurance contracts don't work :)

Now, there is another kind of counter-coordination that Vlad Zamfir figured out that does work. Essentially, first of all, instead of the naive Schellingcoin mechanism where winners get P and losers get 0, we add the anti-coordination game to at least the extent at which the mechanism always has an equal total revenue, ie. if there are k winners, winners get NP/k and losers get 0. Then, set up the contract C such that:

(i) to join C you need to put down a security deposit
(ii) after you join C, you need to provably vote with a 60% chance of Obama and a 40% chance of McCain (ie. use some common entropy to decide your vote with that probability distribution, eg. vote Obama iff sha3(block hash) % 10 < 6)
(iii) after you join C and get your reward if you vote Obama, you need to equally redistribute the reward that you get, as well as any bribes that you receive, among all participants in C
(iv) if you violate (ii) or (iii) you lose the deposit

The expected collective payoff, assuming everyone joins C, is going to be P * N + (P + ϵ) * N * 0.4 ~= P * N * 1.4. The incentive to join C is that you receive an expected payoff of 1.4 * P instead of P. Once you join, the security deposit bounds you to participate. The key trick here is that the contract allows the participants to provably share the rewards and collect the maximum possible benefit from the entire combined game. The mechanism doesn't inherit the problems of assurance contracts for public goods because you have the ability to exclude non-participants from sharing in the collective gain (namely, the attacker's attempted bribe).

Essentially, this is basically a way of using a version of my decentralized coordination contract from https://www.youtube.com/watch?v=S47iWiKKvLA&feature=youtu.be (52:27) against Andrew Miller's centralized coordination contract.

Quote from: zack on January 13, 2015, 03:20:06 AM
The consensus is such that voters are unable to coordinate. That way the voters cannot make the prediction contradictory to the real world and steal funds from users.

So why do you think the voters will suddenly gain the ability to coordinate every time this attack occurs?

It is about information sets...the true ballot (" b* ") is known to everyone, actual votes cast are unknown, and there is an incentive to become a double-agent (which discourages cartels).

Voters can coordinate on b*, because there is low-cost/publicly-available information for them to use. Coordinating a lie is difficult because the only info-source (the liar himself) is suspect (because of RBCR).

The coordination-scheme I proposed uses only public information (in your attack, you assumed that all Voters would all learn of the existence of you attack-contract).

Quote from: vbuterin on January 13, 2015, 07:59:56 PM
So, it is indeed possible to make a counter-coordination contract to defeat the first contract. However, this does result in a bidding war, and so the wrong answer is going to win if the attacker overpowers the combined weight of altruists (note that that's specifically the weight of _altruists_, or rather in my lingo altruists-prime, not just the combined weight of people who have _any_ incentive to see their preferred outcome win, due to the public goods problem). But an algorithm that works only if the attacker has less economic weight than altruists-prime is a low bar; even naive PoS beats it.

I do agree that the counter-contracts create a bidding war, and that bidding wars are a low bar. Although in this case the right answer is winning by default, and in cases of a tie, I readily agree that it would hardly be satisfying if I stopped here.

Quote from: vbuterin on January 13, 2015, 07:59:56 PM
> VTC-holders have a direct incentive to protect the value of the VTC they purchased by assurance-contracting these counter-contracts into existence.

Ah, so that's why we'll have different views on this. My position is that assurance contracts don't work :)

Oh, what a noble mind is here o'erthrown 8)

Quote from: vbuterin on January 13, 2015, 07:59:56 PM
Now, there is another kind of counter-coordination that Vlad Zamfir figured out that does work. Essentially, first of all, instead of the naive Schellingcoin mechanism where winners get P and losers get 0, we add the anti-coordination game to at least the extent at which the mechanism always has an equal total revenue, ie. if there are k winners, winners get NP/k and losers get 0. Then, set up the contract C such that:

(i) to join C you need to put down a security deposit
(ii) after you join C, you need to provably vote with a 60% chance of Obama and a 40% chance of McCain (ie. use some common entropy to decide your vote with that probability distribution, eg. vote Obama iff sha3(block hash) % 10 < 6)
(iii) after you join C and get your reward if you vote Obama, you need to equally redistribute the reward that you get, as well as any bribes that you receive, among all participants in C
(iv) if you violate (ii) or (iii) you lose the deposit

The expected collective payoff, assuming everyone joins C, is going to be P * N + (P + ϵ) * N * 0.4 ~= P * N * 1.4. The incentive to join C is that you receive an expected payoff of 1.4 * P instead of P. Once you join, the security deposit bounds you to participate. The key trick here is that the contract allows the participants to provably share the rewards and collect the maximum possible benefit from the entire combined game. The mechanism doesn't inherit the problems of assurance contracts for public goods because you have the ability to exclude non-participants from sharing in the collective gain (namely, the attacker's attempted bribe).

Essentially, this is basically a way of using a version of my decentralized coordination contract from https://www.youtube.com/watch?v=S47iWiKKvLA&feature=youtu.be (52:27) against Andrew Miller's centralized coordination contract.

Such a scheme strikes me as remarkably similar to my original response (which everyone seems to be overlooking!! ...it begins with: "What if every single voter...."). Instead of joining with some probability, everyone partially joins, and instead of using a new smart contract to redistribute the proceeds, each person partially benefits. From my tinkering, I confidently guess that a safe equilibrium

I would have been very interested (but overwhelmingly surprised) if no such counter-scheme existed or could be discovered...it occurred to me that, if so, the mere existence of Ethereum could invalidate many blockchain consensus schemes (even those powering Ethereum itself), as well as rival Ethereum contracts. In fact, precisely because of that reductio ad absurdum, I wasn't so worried.

I enjoyed your presentation...lots of practical game theory. I glad to see you excited about these Kaldor-Hicks/compensation-principle puzzles...it suits Ethereum.

I don't think Vlad's counter-contract will work.

On a normal round, everyone puts M money at risk, and gets M money back. If nearly half the players lie, then the other half win nearly 2M, and the liars get none.
Attacker offers P+e to liars if the attack fails, where P=2M.
He offers e to liars if the attack succeeds.
joining C puts a bond a risk size B>>2M.
People in C are expected to be honest 60%, and to lie 40%.
_____________|Join C and lie|Join C and conform|Don't join C and be honest100%|Don't join C and lie 100%|
Attack fails____|-B+P+e______|1.2M+0.4P+0.4e__|2M_______________________|P+e
Attack succeeds|-B+2M+e_____|0.8M+0.4e______|_________________________|2M+e

The biggest number in each row (by just 0.6 e) is "Don't join C and lie 100%", so the Nash equilibrium is that the attack will succeed.

I think this is a bidding war where the attacker has to be willing to spend 1.0 in attack-bribes to overtake 0.6 spent on defence-bribes.

QuoteWhat if every single voter responds to this by splitting his/her votecoins into two pools: one 98% of their holdings, and the other 2% of their holdings? With the 98% they vote Obama, with the 2% they vote McCain. Each persons' 2% account loses a substantial portion of VoteCoin (in fact, the smallest VTC holder gets a full alpha=.1 wiped out of his 2% account), but each person's 98% account regains exactly as much VTC. There is no net difference to anyone (Authors, Miners, Traders, Voters), other than that every Voter collects "1.00 of the attackr's money units". A direct transfer from the attacker to the VTC holders.

So, the only issue there is, why would each voter do that? If it is better to do 98/2 in favor of Obama rather than 100/0, why not do 0/100 in favor of McCain? It's certainly in the collective interest to do 98/2, but not in the individual interest. The difference between this and the counter-coordination contract approach is that with the counter-coordination contract, by joining the contract you are pre-committing to vote 98/2 (or 60/40 as I suggested), and it's this pre-commitment that guarantees that others will pre-commit to share bribes with you. It's a different game, because it's two-stage.

Quote from: psztorc on January 13, 2015, 08:36:16 PM
I would have been very interested (but overwhelmingly surprised) if no such counter-scheme existed or could be discovered...it occurred to me that, if so, the mere existence of Ethereum could invalidate many blockchain consensus schemes (even those powering Ethereum itself), as well as rival Ethereum contracts. In fact, precisely because of that reductio ad absurdum, I wasn't so worried.

So, the problem here is that you are assuming Ethereum is necessary for secure coordination. It's not. It's necessary for _the average person_ to easily engage in secure coordination. Large businesses and governments can perform any of these attacks with no Ethereum required just by making promises and using their reputation as collateral.

Quote
I don't think Vlad's counter-contract will work.

So, to give what I think is a summary, if the attacker instead promises substantially more than P as a bribe if the mechanism loses, then it will indeed make more sense to not participate and lie, because by lying you're guaranteed 100% of the attacker's reward instead of just 40% of it. Okay, I'll be awaiting Vlad's response :)

Quote from: vbuterin on January 13, 2015, 09:25:25 PM
So, the only issue there is, why would each voter do that? If it is better to do 98/2 in favor of Obama rather than 100/0, why not do 0/100 in favor of McCain? It's certainly in the collective interest to do 98/2, but not in the individual interest.

No, not in this case. I explain in sentence 4 and elaborate in 5 and 6:

Quote from: psztorc on January 11, 2015, 10:26:05 PM
They could even safely split 51% 49% (of their account), but if others split on a different level (for example, 100% 0%), the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50. This is because all the lie-ballots are the same, and will draw for last [or second, or whatever non-first slot] and bleed a proportion of their VTC. Less in those ballots, the less bleeding.

Voters want to coordinate a globally identical split-% (even if they don't want to split at all, the split would be 0, 100%). They coordinate on a level which doesn't allow the attack to succeed, primarily because it pays more (but also because it hurts them less).

Quote from: vbuterin on January 13, 2015, 09:25:25 PM
The difference between this and the counter-coordination contract approach is that with the counter-coordination contract, by joining the contract you are pre-committing to vote 98/2 (or 60/40 as I suggested), and it's this pre-commitment that guarantees that others will pre-commit to share bribes with you. It's a different game, because it's two-stage.

Is there an echo in here?

Quote from: psztorc on January 13, 2015, 08:36:16 PM
...instead of using a new smart contract to redistribute the proceeds, each person partially benefits.

Quote from: vbuterin on January 13, 2015, 09:25:25 PM

Quote from: psztorc on January 13, 2015, 08:36:16 PM
I would have been very interested (but overwhelmingly surprised) if no such counter-scheme existed or could be discovered...it occurred to me that, if so, the mere existence of Ethereum could invalidate many blockchain consensus schemes (even those powering Ethereum itself), as well as rival Ethereum contracts. In fact, precisely because of that reductio ad absurdum, I wasn't so worried.

So, the problem here is that you are assuming Ethereum is necessary for secure coordination. It's not. It's necessary for _the average person_ to easily engage in secure coordination. Large businesses and governments can perform any of these attacks with no Ethereum required just by making promises and using their reputation as collateral.

I am not assuming that at all, what gave you that idea? I am merely saying that, if you could build a PoW-killer, or a Truthcoin-killer, then that doesn't leave much hope for any blockchain or smart contract (they can all be killed with the killer).

Quote from: psztorc on January 14, 2015, 06:03:28 PM
I am merely saying that, if you could build a PoW-killer, or a Truthcoin-killer, then that doesn't leave much hope for any blockchain or smart contract (they can all be killed with the killer).

Correct. That is why there is so much controversy about proof of stake.
I think it needs to work this way: If 2 people are in disagreement, then the one who is willing to burn more money wins. No one will waste money on a P+E, E attack, they will just burn it to get their way.

I am trying to implement proof of stake because it is needed for truthcoin.

QuoteBy deviating toward 100%, they would risk hitting #4 instead of #1

In my models I generally assume that the good guys are all infinitely small and thus have zero individual incentive to benefit the collective good; if a mechanism does not work under this assumption then it's only as strong as it is monopolistic and that's not really a good place to be. I once did a statistical analysis of the level of combined incentive of this altruism-prime effect (that's the sum over all nodes of "probability_of_being_pivotal(node) * incentive(node)") on the Ethereum crowdsale database and found that it can be overcome by an attacker with 8% of stake in the absolute best case, and often less than 1%.

Quoteif others split on a different level (for example, 100% 0%), the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50. This is because all the lie-ballots are the same, and will draw for last [or second, or whatever non-first slot] and bleed a proportion of their VTC. Less in those ballots, the less bleeding.

So, there are two arguments here. The first argument is the individual incentive without looking at each individual's influence on the system (as I generally prefer to). Here, there is a simple appeal to linearity: if the attacker's bribe makes B more profitable than A, then B will also be more profitable than 0.49 * B + 0.51 * A. The second argument is what happens when we do look at the individual incentive. Then, we have a situation where the equilibrium is 49/51, and it's the individual's choice of whether to vote probabilistically, vote B or vote A. If the individual's vote power is less than 1%, then if the attacker's bribe exceeds the reward that's all you need for the attack to succeed. If the individual's vote power is greater than 1%, then the absolutely optimal strategy seems to be to try to target a 49.999999/50.000001 split, but then your mechanism becomes infinitely fragile (assurance contracts also have this problem; sure, you _can_ force absolutely everyone to contribute and that resolves my incentive concerns, but then if even one person does not pay up the whole thing breaks), and because of imperfect information you get right back to this "low probability of being pivotal" problem that allows attackers to succeed just fine with even a moderate extra bribe.

Quote from: psztorc on January 14, 2015, 06:03:28 PM
I am not assuming that at all, what gave you that idea? I am merely saying that, if you could build a PoW-killer, or a Truthcoin-killer, then that doesn't leave much hope for any blockchain or smart contract (they can all be killed with the killer).

Actually, no. PoS is not a multi-equilibrium system in the same way that PoW is; you slash double-signers so the attacker still massively loses even if they win (there is a slight expansion to the weak subjectivity norm by which you can wait for a few minutes to check if a fork refuses to include evidence, and refuse to accept it if it does). But yeah, PoW is, as John Maynard Keynes would say, a barbarous relic.

It seems that you've misunderstood my point of view in several ways:

Quote from: vbuterin on January 25, 2015, 03:39:42 PM
In my models I generally assume that the good guys are all infinitely small and thus have zero individual incentive to benefit the collective good; if a mechanism does not work under this assumption then it's only as strong as it is monopolistic and that's not really a good place to be. I once did a statistical analysis of the level of combined incentive of this altruism-prime effect (that's the sum over all nodes of "probability_of_being_pivotal(node) * incentive(node)") on the Ethereum crowdsale database and found that it can be overcome by an attacker with 8% of stake in the absolute best case, and often less than 1%.

Those payoffs are all individual payoffs (as always)...

Quote from: vbuterin on January 25, 2015, 03:39:42 PM
So, there are two arguments here. The first argument is the individual incentive without looking at each individual's influence on the system (as I generally prefer to). Here, there is a simple appeal to linearity: if the attacker's bribe makes B more profitable than A, then B will also be more profitable than 0.49 * B + 0.51 * A.

I explained why the payoff is nonlinear two weeks ago:

Quote from: psztorc on January 11, 2015, 10:26:05 PM
...They could even safely split 51% 49% (of their account), but if others split on a different level (for example, 100% 0%), the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50. This is because all the lie-ballots are the same, and will draw for last [or second, or whatever non-first slot] and bleed a proportion of their VTC. Less in those ballots, the less bleeding.

This also explains why the [.50-e vs .50+e] (such as .49 vs .51) equilibrium, while worst for the attacker and best for the Voters, is itself unstable and will collapse to a unique e* (itself proportional to the magnitude of the bribe).

Quote from: vbuterin on January 25, 2015, 03:39:42 PM
The second argument is what happens when we do look at the individual incentive. Then, we have a situation where the equilibrium is 49/51, and it's the individual's choice of whether to vote probabilistically, vote B or vote A. If the individual's vote power is less than 1%, then if the attacker's bribe exceeds the reward that's all you need for the attack to succeed. If the individual's vote power is greater than 1%, then the absolutely optimal strategy seems to be to try to target a 49.999999/50.000001 split, but then your mechanism becomes infinitely fragile (assurance contracts also have this problem; sure, you _can_ force absolutely everyone to contribute and that resolves my incentive concerns, but then if even one person does not pay up the whole thing breaks), and because of imperfect information you get right back to this "low probability of being pivotal" problem that allows attackers to succeed just fine with even a moderate extra bribe.

I wrote about "splitting" one's vote, precisely to avoid this problem and introduce a stable equilibrium.

Quote from: psztorc on January 11, 2015, 07:47:03 PM
What if every single voter responds to this by splitting his/her votecoins into two pools: one 98% of their holdings, and the other 2% of their holdings? ...

Quote from: vbuterin on January 25, 2015, 03:39:42 PM

Quote from: psztorc on January 14, 2015, 06:03:28 PM
I am not assuming that at all, what gave you that idea? I am merely saying that, if you could build a PoW-killer, or a Truthcoin-killer, then that doesn't leave much hope for any blockchain or smart contract (they can all be killed with the killer).

Actually, no. PoS is not a multi-equilibrium system in the same way that PoW is; you slash double-signers so the attacker still massively loses even if they win (there is a slight expansion to the weak subjectivity norm by which you can wait for a few minutes to check if a fork refuses to include evidence, and refuse to accept it if it does). But yeah, PoW is, as John Maynard Keynes would say, a barbarous relic.

Firstly, I don't feel you've demonstrated a difference between PoW and PoS (double-hashers also "lose" in PoW). Perhaps you can formally define "not a multi-equilibrium system"? But I was referring not to consensus algorithms but instead to smart contracts in general (data feeds, hedging contracts, autonomous agents, as they could all be bribed or leeched / self-referenced into oblivion, assuming that such attacks were profitable [as you suggest]).

Quote
I wrote about "splitting" one's vote, precisely to avoid this problem and introduce a stable equilibrium.

Yeah, so the problem with splitting one's vote is that the mechanism is still fragile. Here's how. Suppose that I precommit to making a 100/0 split, and shut off my computer and go away. Then the community has the incentive to create a split that leads to a maximally close to 50/50 outcome without me. If your argument is correct, then they will succeed. However, I collect twice as many bribes as they do, so assuming bribes exceed intrinsic revenue doing what I did is a dominant strategy. This is a similar argument to one of the secondary reasons why assurance contracts don't work: even if it looks like you're pivotal, you're actually (very very probably) not, because if you disappear others will have the incentive to pick up the slack.

Quote from: psztorc on January 11, 2015, 10:26:05 PM
...They could even safely split 51% 49% (of their account), but if others split on a different level (for example, 100% 0%), the VTC-owners who split closer to 50-50 stand to lose VTC to those who split further from 50-50. This is because all the lie-ballots are the same, and will draw for last [or second, or whatever non-first slot] and bleed a proportion of their VTC. Less in those ballots, the less bleeding.

So, if the voters that split 50/50 get less than the voters that go 100/0 (which I will accept; since by voting 100/0 you are exerting influence over the result and hence increasing your probability of winning). But then doesn't that make 50/50 not a stable equilibrium?

Quote

Quote from: vbuterin on January 25, 2015, 03:39:42 PM

Quote from: psztorc on January 14, 2015, 06:03:28 PM
I am not assuming that at all, what gave you that idea? I am merely saying that, if you could build a PoW-killer, or a Truthcoin-killer, then that doesn't leave much hope for any blockchain or smart contract (they can all be killed with the killer).

Actually, no. PoS is not a multi-equilibrium system in the same way that PoW is; you slash double-signers so the attacker still massively loses even if they win (there is a slight expansion to the weak subjectivity norm by which you can wait for a few minutes to check if a fork refuses to include evidence, and refuse to accept it if it does). But yeah, PoW is, as John Maynard Keynes would say, a barbarous relic.

Firstly, I don't feel you've demonstrated a difference between PoW and PoS (double-hashers also "lose" in PoW). Perhaps you can formally define "not a multi-equilibrium system"? But I was referring not to consensus algorithms but instead to smart contracts in general (data feeds, hedging contracts, autonomous agents, as they could all be bribed or leeched / self-referenced into oblivion, assuming that such attacks were profitable [as you suggest]).

PoW doesn't have a concept of double-hashing but it does have a concept of "wrong-hashing" (mining on the wrong fork). If you mine on the wrong fork and it wins, you win, and if you mine on the right fork and the wrong fork wins, you lose. By "not a multi-equilibrium system" I mean "the correct way to behave remains the optimal way to behave (assuming bribes less than some security margin) regardless of what everyone else is doing".

I do have an alternative design that "rescues" Schelling-like schemes to some degree, although at some cost of ugliness and (yay!) quasi-subjectivity; look out for an upcoming blog post :)

You dropped a "[ quote ]" I added it back for you.

Quote from: vbuterin on January 26, 2015, 04:12:13 AM
Yeah, so the problem with splitting one's vote is that the mechanism is still fragile. Here's how. Suppose that I precommit to making a 100/0 split, and shut off my computer and go away. Then the community has the incentive to create a split that leads to a maximally close to 50/50 outcome without me. If your argument...

My position has nothing to do with precommitment, and has never been that voters will want to approach a 50% 50% split.

To restate my position yet again, in yet another way, consider this timeline: "Bribe" -> "Voters use { bribe magnitude, VTC market cap } to compute optimal split e* ( which will always be between .000 and .500, and in practice might be between .001 and .030 )" -> "all Voters split their VTC holdings by e*" -> "bribe fails (and pays out big), resolution succeeds".

Anyone who splits too low (closer to 0-100) passed up on free bribe money, and anyone who split too high (closer to 50-50) effectively sold VTC at a cheaper-than-market price.

If Voters are too lazy to do the computation for e*, they might be in the first case (and lose out on bribe money), but they will pick up new VTC for free (the total-market-value-of-the-free-VTC will be lower than the bribe-one-could-have-received-if-one-computed-e*). The bribe is a buy offer like any other...the Outcome-Resolution process still works as intended. So even lazy voters will just split 0-100 and profit at the briber's expense.

Quote from: vbuterin on January 26, 2015, 04:12:13 AM
So, if the voters that split 50/50 get less than the voters that go 100/0 (which I will accept; since by voting 100/0 you are exerting influence over the result and hence increasing your probability of winning). But then doesn't that make 50/50 not a stable equilibrium?

To repeat myself yet again, I have never claimed that 50-50 is a stable equilibrium. I did say "safely split 51% 49%", but by "safely" I meant that the outcome-resolution process would be "safe" from the "attack" (the bribe). If one finishes the sentence, it is overwhelmingly clear that the "safe 51% 49%" is a non-equilibrium and completely hypothetical situation.

Quote from: vbuterin on January 26, 2015, 04:12:13 AM
PoW doesn't have a concept of double-hashing but it does have a concept of "wrong-hashing" (mining on the wrong fork). If you mine on the wrong fork and it wins, you win, and if you mine on the right fork and the wrong fork wins, you lose. By "not a multi-equilibrium system" I mean "the correct way to behave remains the optimal way to behave (assuming bribes less than some security margin) regardless of what everyone else is doing".

I still see no difference. Because PoW is cumulative, this is (in expectation) exactly how PoW already works (PoW is "not a multi-equilibrium system"). You are most likely to win if you mine on the longest chain (given that you do not control 51%).

Quote from: vbuterin on January 26, 2015, 04:12:13 AM
I do have an alternative design that "rescues" Schelling-like schemes to some degree, although at some cost of ugliness and (yay!) quasi-subjectivity; look out for an upcoming blog post :)

I often feel patronized when people give me unsolicited advice (even when the advice is given privately and is ultimately very helpful). However, at my own peril, let me suggest that you consider taking a break from Theory, which has made-useless many a young genius.

"""
In the 1920s, there was a dinner at which the physicist Robert W. Wood was asked to respond to a toast ... 'To physics and metaphysics.'

Now by metaphysics was meant something like philosophy—truths that you could get to just by thinking about them. Wood took a second, glanced about him, and answered along these lines:

The physicist has an idea, he said. The more he thinks it through, the more sense it makes to him. He goes to the scientific literature, and the more he reads, the more promising the idea seems. Thus prepared, he devises an experiment to test the idea. The experiment is painstaking. Many possibilities are eliminated or taken into account; the accuracy of the measurement is refined. At the end of all this work, the experiment is completed and ... the idea is shown to be worthless. The physicist then discards the idea, frees his mind (as I was saying a moment ago) from the clutter of error, and moves on to something else. The difference between physics and metaphysics, Wood concluded, is that the metaphysicist has no laboratory.
"""
-Carl Sagan

Quote
Anyone who splits too low (closer to 0-100) passed up on free bribe money, and anyone who split too high (closer to 50-50) effectively sold VTC at a cheaper-than-market price.

So I suppose it's the latter part of the claim that I don't see being the case at all. As I see it, whatever slight nonlinearity exists in the payout (and in any case a sufficiently high bribe will outweigh this nonlinearity) actually works against the mechanism, as pushing your vote further toward one end or the other further increases the probability that the side that you are favoring wins.

Quote
I still see no difference. Because PoW is cumulative, this is (in expectation) exactly how PoW already works (PoW is "not a multi-equilibrium system"). You are most likely to win if you mine on the longest chain (given that you do not control 51%).

Except that "mining on what is currently the longest chain" is NOT always the optimal behavior. If the current longest chain is A, and you expect in the near future that everyone else will switch to B, then it is your incentive to switch to B.

Quote from: vbuterin on January 26, 2015, 04:37:37 PM

Quote
Anyone who splits too low (closer to 0-100) passed up on free bribe money, and anyone who split too high (closer to 50-50) effectively sold VTC at a cheaper-than-market price.

So I suppose it's the latter part of the claim that I don't see being the case at all. As I see it, whatever slight nonlinearity exists in the payout (and in any case a sufficiently high bribe will outweigh this nonlinearity) actually works against the mechanism, as pushing your vote further toward one end or the other further increases the probability that the side that you are favoring wins.

It might, if you made a bunch of extra assumptions about "trembling hands" or miscommunications, but I am not talking probability one bit. These are all pure strategies. No randomness, no mixing, no variability, no probabilities. In equilibrium (with no profitable deviations, no regrets) the bribe fails to achieve its objective, and it fails with certainty.

Quote from: vbuterin on January 26, 2015, 04:37:37 PM

Quote
I still see no difference. Because PoW is cumulative, this is (in expectation) exactly how PoW already works (PoW is "not a multi-equilibrium system"). You are most likely to win if you mine on the longest chain (given that you do not control 51%).

Except that "mining on what is currently the longest chain" is NOT always the optimal behavior. If the current longest chain is A, and you expect in the near future that everyone else will switch to B, then it is your incentive to switch to B.

I agree that this is a distinction between PoW and PoS, that expectations of the future matter less in PoS, and I agree that expectations can be manipulated using bribes. Well done.

However, my original argument stands: In Bitcoin-only, one cannot construct such a smart-contract bribe. However, in Ethereum, one can. Would Ethereum smart contracts attack each other in endless cycles, making the platform useless?

Quote from: psztorc on January 26, 2015, 05:59:49 PM

Quote from: vbuterin on January 26, 2015, 04:37:37 PM

Quote
Anyone who splits too low (closer to 0-100) passed up on free bribe money, and anyone who split too high (closer to 50-50) effectively sold VTC at a cheaper-than-market price.

So I suppose it's the latter part of the claim that I don't see being the case at all. As I see it, whatever slight nonlinearity exists in the payout (and in any case a sufficiently high bribe will outweigh this nonlinearity) actually works against the mechanism, as pushing your vote further toward one end or the other further increases the probability that the side that you are favoring wins.

It might, if you made a bunch of extra assumptions about "trembling hands" or miscommunications, but I am not talking probability one bit. These are all pure strategies. No randomness, no mixing, no variability, no probabilities. In equilibrium (with no profitable deviations, no regrets) the bribe fails to achieve its objective, and it fails with certainty.

Right, so I do assume miscommuncations, trembling hands and just plain bounded rationality prohibiting non-obvious game-theoretic reasoning deeper than a few steps. Perhaps this is the fundamental difference between our approaches.

But I still am not convinced of one thing. Even if you are correct, and there is a nonlinearity favoring moderate strategies over extreme ones, I still think that the derivative d(intrinsic reward)/d(% of money voting 1) is bounded, and so if the attacker credibly commits to a bribe whose value exceeds that upper bound, people will have the incentive to go 100-0 in favor of the attacker.

Quote
However, my original argument stands: In Bitcoin-only, one cannot construct such a smart-contract bribe. However, in Ethereum, one can. Would Ethereum smart contracts attack each other in endless cycles, making the platform useless?

So I think this is where I got the idea that you were implying Ethereum is necessary for secure coordination and credible commitment; maybe you weren't, it doesn't matter much. The issue I have is, if a particular smart contract is attackable, and if we agree that game-theoretic incentive incompatibility implies that the contract will eventually be profitably attacked, then in the presence of Ethereum that smart contract will be attacked by Ethereum and in the absence of Ethereum it will be attacked by credible commitment schemes using plain old real-world trusted parties (eg. lawyers, a Codius multisig with parties from five different countries, etc). And if a smart contract is not (profitably) attackable, then it will be fine under both models.

Quote from: vbuterin on January 27, 2015, 07:20:09 AM

Quote from: psztorc on January 26, 2015, 05:59:49 PM
It might, if you made a bunch of extra assumptions about "trembling hands" or miscommunications, but I am not talking probability one bit. These are all pure strategies. No randomness, no mixing, no variability, no probabilities. In equilibrium (with no profitable deviations, no regrets) the bribe fails to achieve its objective, and it fails with certainty.

Right, so I do assume miscommuncations, trembling hands and just plain bounded rationality prohibiting non-obvious game-theoretic reasoning deeper than a few steps. Perhaps this is the fundamental difference between our approaches.

This is not "a difference between our approaches", fundamental or otherwise. My model neither requires nor contains uncertainty (and trembling hands and bounded rationality would not introduce uncertainty) so there is no "probability that the side that you are favoring wins". However, if you introduced a new model with miscommunications in a way that contained uncertainty, you could tautologically introduce uncertainty in the outcome. However, you could do that anywhere, with anything, which is what I was trying to say: You can have uncertainty in the outcome, if you create uncertainty in the inputs. I was (charitably) using your example to show that your point was irrelevant.

But suppose you had introduced uncertainty...as the split approached 50-50, whatever (tiny) uncertainties you had contrived to introduce (people voting the wrong way on accident, despite being paid not to do this) would contribute to a larger failure probability (if the split is 2-98 and the uncertainties can only shift NORM(0%,3%), the attack still fails with near-certainty, but with a 49-51 split the attack may succeed with some "probability"). Even if you trembled into an "I'll just join the attacker because I'm very confused and want the bribe"-strategy, others have a profitable reaction to that tremble (and will be trembling the other way, anyways).

For reasonable bribes, you can change the attack-hit-rate from .001% to .002%, but only by assuming that Voters are careless (which would introduce uncertainty anyway, making the bribe irrelevant). Additional uncertainties-conditional-on-bribes are not necessary, because the strategy I outlined survives (and thrives) under voter communication.

Quote from: vbuterin on January 27, 2015, 07:20:09 AM
But I still am not convinced of one thing. Even if you are correct, and there is a nonlinearity favoring moderate strategies over extreme ones, I still think that the derivative d(intrinsic reward)/d(% of money voting 1) is bounded, and so if the attacker credibly commits to a bribe whose value exceeds that upper bound, people will have the incentive to go 100-0 in favor of the attacker.

That's true, but the bribe would have to be a credible purchase of 50% of the VTC. If one could commit to that, they could do the same attack just by buying, not bribing. That attack is completely different from the one proposed here (and I'm not very worried about it).

Quote from: vbuterin on January 27, 2015, 07:20:09 AM

Quote
However, my original argument stands: In Bitcoin-only, one cannot construct such a smart-contract bribe. However, in Ethereum, one can. Would Ethereum smart contracts attack each other in endless cycles, making the platform useless?

So I think this is where I got the idea that you were implying Ethereum is necessary for secure coordination and credible commitment; maybe you weren't, it doesn't matter much. The issue I have is, if a particular smart contract is attackable, and if we agree that game-theoretic incentive incompatibility implies that the contract will eventually be profitably attacked, then in the presence of Ethereum that smart contract will be attacked by Ethereum and in the absence of Ethereum it will be attacked by credible commitment schemes using plain old real-world trusted parties (eg. lawyers, a Codius multisig with parties from five different countries, etc). And if a smart contract is not (profitably) attackable, then it will be fine under both models.

That's nice logic, but "plain old real-world trusted parties (eg. lawyers)" are in fact very limited in what they can do, even if we ignore the tremendous costs involved. (Codius would seem to overlap almost-completely with Ethereum, not lawyers). Bitcoin would be 51% attacked to death if we had a real-world trusted alternative...because the coins would have no value, and so there would be no way to pay for the PoW-clock. The long arm of the law can't reach into a coder's imagination.

https://blog.ethereum.org/2015/01/28/p-epsilon-attack/

There are many practical reasons what this attack won't work

The attack assumes that "the attacker needs to be able to afford to purchase 50% of the votecoins". The problem is that affordability is undecidable and highly unprobable due to the way markets are working.
Liquidity: markets don't allow to instantly and atomically execute huge positions: they are limited by liquidity and I have never seen a market with 50% of the float available for sale.
Reflexivity: markets tend to trend against large interests entering the market. Executing too quick will make the price grow superlinearly. Executing too slowly allows observers to do trend analysis and detect the buy pressure. Either way, there is no way to buy 50% of the float of a market without sending the price through the roof, which makes "affordability" something undecidable in advance and highly doubtful.
Fixed income cost: TruthCoin yield commissions. As such, there is an incentive for holders to hold them in the network as opposed to an exchange. This will further reduce liquidity. And if there are exchanges that will offer to hold the coins, participate in voting, and pay back the yield to despositors, this will foil the attack further as now one or serveral exchanges will have to risk their whole business to gain from this attack and it's a safe bet that they won't.
Biaised equilibrium: the affordability condition ties the voting game to another game: the price disovery mecanism of the market. If you publish a contract that will in fine oblige you to make large TruthCoin purchases on the market, you are giving a strong bullish signal to market participants (the voters themselves) that their TruthCoins are going to gain value in the event where the attack fails, which means that they will move their orders to sell higher, and possibly even buy into the orders of less responsive participants, so that the attack will increasingly be perceived as less and less affordable, the contract as  more and more liquely to default, which will desincentivize voters to put all the truthcoins on the fake outcome since the contract and will incentivize them to simply withdraw their coins to the exchange and try to sell them in the crazy rally the contract is going to generate. I don't have a payoff matrix as the situation is near to impossible to model, but the least I can say is that in that dual-attractor setup with a market feeding into a prisonner-dilemma game, there is no trivial winning strategy for the attacker and all participants. The best strategy for the attacker is to not attack.

Now you could say that this can be worked around by buying progressively enough TruthCoins on the market before the attack. But then the attacker will own the majority of the shares, so he doesn't even need the contract, he can just chose the outcome he likes, win his bet, and watch the value of all his CashCoin and TruthCoin holdings go away in smoke as the market realizes that TruthCoin has been attacked and makes the price tank. And of course, no time to close so large positions in the market before the price goes south.

Either way, that attack is completely unrealistic.

klosure, thanks for taking interest in truthcoin. Welcome to the forum.

The P,epsilon attack attacks the oracle, not the market maker.
The oracle is the thing that lets the blockchain learn facts about meatspace. There are many people who have reputation, and they all report to the blockchain about what happened. If the players are honest, their reputation is supposed to grow, if they are dishonest it is supposed to shrink.

The P, epsilon attack causes the reputation holder to be dishonest, even though they may lose some reputation.
The attack is significant because it costs almost nothing to do it.
The attack is limited because the attacker has to be very rich, he has to be approximately rich enough to buy all the reputation at the current price. I say "approximately" because it depends on what percentage of users are rational vs byzantine vs altruistic.

I cannot explain as well as vitalik. Please consider reading his essay about this: https://blog.ethereum.org/2015/01/28/p-epsilon-attack/

If truthcoin is vulnerable to this attack, it isn't necessarily the end of truthcoin. We can use secure multiparty computation to fix this vulnerability https://blog.ethereum.org/2014/12/26/secret-sharing-daos-crypto-2-0/

Let me reiterate: I have never felt that Truthcoin was vulnerable to this kind of attack.

Furthermore, I make the stronger claim that my very first response ( http://forum.truthcoin.info/index.php/topic,173.msg849.html#msg849 ) fully refutes the attack (so long as the attacker is not willing-and-able to purchase >50% of the Votecoins). I thirdly claim that all subsequent posts by zack and vbuterin (whatever their other merits) fail to grasp my concept of "splitting" one's vote, let alone the relevance of this "split-concept" to the problem.

I agree with klosure, in particular I would like to direct the reader's attention to "High, Uncertain, Nonlinear Costs of Buying" in my weakness page (http://www.truthcoin.info/weaknesses/) (which I am currently improving, but is reasonably complete as is).

The Augur project is taking a similar position as Psztorc on this issue, so they will launch an implementation of truthcoin without SMPC (secure multi-party computation).

P+epsilon attacks also work against proof of work, so bitcoin is broken.
I have dropped everything else and am trying to create a proof of stake blockchain https://github.com/tendermint/tendermint/ with Jae Kwon. Once blockchains are fixed I will start working on truthcoin again.

Hey, (from the Augur project here) --- I used to think this attack was an issue (and SMPC *is* in our roadmap in the long run due to that reason, if it'll stay there depends on computational costs, etc.).  I too don't get the splitting vote solution - I ran the numbers splitting my votes into 2% on the failing lie and 98% truth and it's still more profitable to vote 100% lie. 

However, on "Salvaging Schelling Schemes" in Vitalik's blog post he brings up a good point (I think Paul brought this up a few times too): "Hence, in order to overcome such a mechanism, one would need to be able to prove that one is capable of pulling off a 51% attack, and perhaps we may simply be comfortable with assuming that attackers of that size do not exist." 

The reasons klosure brought up are very similar to my thinking re 51% attacks on reputation; it's the same way I answer it when people ask me about "well what if i bought up 51% of rep?"  If you need to prove you're capable of pulling off a 51% attack to execute a p+epsilon attack, you may as well just execute a regular old 51% attack, which as klosure pointed out is very difficult for one actor (if not nigh impossible).

The type of 51% attack I am concerned about regarding this project is if people collude for voting on outcomes.  The only way you can really do this is if you can prove to other people how you voted before the outcome is resolved.  One way to prevent this is to make people's reputation itself be a bond (and if someone can prove you leaked how you voted they get that reputation - got this idea from Zack).  Even if there wasn't a system like Zack proposed, there's still no way to know if you will change your vote at the last minute before consensus is calculated. 

It's slightly disturbing to me that you "ran the numbers splitting my votes into 2%" and then reached some conclusion. The magnitude of 2, in range(0,50) was just an example (the split magnitude depends on the bribe magnitude).

Quote from: psztorc on January 26, 2015, 04:20:55 PM
To restate my position yet again, in yet another way, consider this timeline: "Bribe" -> "Voters use { bribe magnitude, VTC market cap } to compute optimal split e* ( which will always be between .000 and .500, and in practice might be between .001 and .030 )" -> "all Voters split their VTC holdings by e*" -> "bribe fails (and pays out big), resolution succeeds".

Did your 100%-lie player lose Votecoins? Did you calculate the implied economic cost of that loss (as, perhaps, percentage of the market cap)?

As to the collusion...it is discussed in the FAQ as well as elsewhere in the forum, in addition to being addressed in, -gasp-, Whitepaper 1.0 which was published over a year ago.

For example: http://forum.truthcoin.info/index.php/topic,127.0.html

The Augur version of Truthcoin has no chance of success if it is going to be 12 months behind any literate competitor...12 months is an eternity in this space.

And it is entirely possible to pull off a 51% ownership attack...the attacker can slowly accumulate 51% over time.

The question is if anyone can pull off a profitable 51% attack...in Whitepaper 1.4 I (will) demonstrate a few simple ways that the attack can be virtually guaranteed to be unprofitable.

Quote from: psztorc on February 10, 2015, 04:45:14 AM
It's slightly disturbing to me that you "ran the numbers splitting my votes into 2%" and then reached some conclusion. The magnitude of 2, in range(0,50) was just an example (the split magnitude depends on the bribe magnitude).

Quote from: psztorc on January 26, 2015, 04:20:55 PM
To restate my position yet again, in yet another way, consider this timeline: "Bribe" -> "Voters use { bribe magnitude, VTC market cap } to compute optimal split e* ( which will always be between .000 and .500, and in practice might be between .001 and .030 )" -> "all Voters split their VTC holdings by e*" -> "bribe fails (and pays out big), resolution succeeds".

Did your 100%-lie player lose Votecoins? Did you calculate the implied economic cost of that loss (as, perhaps, percentage of the market cap)? 

As to the collusion...it is discussed in the FAQ as well as elsewhere in the forum, in addition to being addressed in, -gasp-, Whitepaper 1.0 which was published over a year ago.

For example: http://forum.truthcoin.info/index.php/topic,127.0.html

The Augur version of Truthcoin has no chance of success if it is going to be 12 months behind any literate competitor...12 months is an eternity in this space.

If everyone lies, they get the biggest payout, that's how the p+epsilon attack works...

Accumulating 51% is extremely difficult as it would push the price up enormously high.

Your collusion solution solves collusion at the expense of making a highly convoluted process most users won't understand: "you mean my pubkey is my private key? And I have to make a new key after I vote.. what?". 

With Zack's proposed modification we can eliminate the use of symmetric key encryption, however you have not proposed this idea anywhere.  Sure, I can encrypt the votes with symmetric encryption, but now I can't send votes easily to other users because my public key is my private key.  This solution is quite convoluted and requires assigning your votes to a new key after consensus, making things further computationally expensive as well (yet another massive set of data to keep track of). (and having one's vote encrypting key doesn't even allow you to take their votes because if it did, anyone could steal anyone's votes at any time due to the nature of blockchains & symmetric crypto).

We're not twelve months behind, we're focusing on improvements to a reporting design that will currently make no sense to the vast majority of users.

"d. Voters encrypt, sign, and broadcast a
Ballot which contains their Votes and a new public key (for which they have the
corresponding private key)." 

"Voters
reveal the private key used to encrypt their votes in (5), allowing these votes to be
decrypted and read into the consensus algorithm. "

This suggests you're using standard public-private key cryptography, so it's really unclear from the combinations of your examples whether you suggest using symmetric keys (which have the problems I posted above) or pub-private key crypto.  If you are talking about pub-private crypto, you encrypt using your public key, making it so I can share my vote with anyone... which is solvable with Zack's solution.  You do not encrypt using your private key...

Moving on to your FAQ:
"Ballots are encrypted, and contain a new destination (public key), for this reason. Votes are cast in one period, and unsealed in a later period (during which no new votes are cast). Because private keys are required to decrypt, it is always impossible to prove that you've voted a certain way"

Here's an easy way to prove you voted a certain way, allowing one to collude very easily (unless you use zack's soln.):
1) I publish my encrypted ballot using my public key
2) I publish the unencrypted ballot, my public key, and any random person can take the ballot, encrypt it with my pubKey and see that I voted a certain way.  They don't need to take the encrypted ballot and use my private key to decrypt it to discover my vote.

A solution from twelve months ago that fails to take into account the basics of public-private key crypto is also slightly disturbing ;)

If you do have a solution, and can explain it in a step by step manner that's consistent and doesn't mix asymmetric + symmetric crypto and doesn't involve encrypting with a private key, please explain it as I'd like to read it.

The expectation was to use the ECDSA private key as the vote-encryption symmetric public key.

The cryptographers I ran it past were not confused...nonetheless, for extra clarity, in Whitepaper 1.2, on page 23 (which was published May 21, 2014), I linked to a discussion of this usage ( https://bitcointalk.org/index.php?topic=196378.0 ).

Furthermore, zack and I discussed a nearly-identical solution in public and on this forum using hash functions instead of encryption, so that keys would not need to be revealed, which some people found more comfortable. I'm not sure why zack didn't mention it to you.

If you were confused, you should have just asked. Instead you are changing to something that [you yourself admit] you don't understand? ...you certainly admit to being "concerned about" your own solution a few replies above.

For those of you in the audience, despite nearly 20 attempts, the hit-rate on "Augur/zack has thought they were improving something AND it actually turned out to be an improvement" is still 0%.

ECDSA private keys are not designed to be used for encryption, using crypto in unintended ways tends to result in massive failures...  Hash functions are superior to encryption in this use case, that's how I've been implementing it.  "Public key cryptosystems are extremely fragile. Do not use them differently than they were designed." ~ Stack Overflow

The hash function idea has a flaw... I can publish my salt and not-hashed ballot and you can prove I voted a certain way.  Hash functions are pretty simple, so I'm not sure where you got the idea that I'm switching to something I don't understand.  I'm "concerned about" the solution re hashing, which doesn't work due to the reason in this paragraph.

Again, the way to fix this is to use rep. as a bond itself and if I prove someone revealed their vote early I get their rep (which is nowhere to be found in the whitepaper nor any whitepaper talk on hashing votes).  Another improvement people have come up with (Martin I believe) is using a liquidity sensitive MSR and linear time deterministic pca ;).  Truthcoin isn't perfect, heck, it even has errors in the SVD description in the whitepaper.

The odd ECDSA private key encryption is again expensive, hash functions + collusion checking are a cheap and more intuitive solution, I see no reason why we shouldn't continue to implement it that way (if there is I'd still like to see one, although I haven't yet in these past few messages).

Quote from: joeykrug on February 10, 2015, 11:48:43 PM
ECDSA private keys are not designed to be used for encryption, using crypto in unintended ways tends to result in massive failures...  Hash functions are superior to encryption in this use case, that's how I've been implementing it.  "Public key cryptosystems are extremely fragile. Do not use them differently than they were designed." ~ Stack Overflow

This sophistry implies that the stability of the cryptosystem itself relies on an "unintended use". In reality the use is irrelevant to the cyptosystem's stability, trivial, easily-to control, and motivated by the convenience of sticking with keys that already exist.

To be complete, the whitepaper needed only to say that the problem was solvable. Improvements are possible and welcome, but they have to actually improve something.

Quote from: joeykrug on February 10, 2015, 11:48:43 PM
Another improvement people have come up with (Martin I believe) is using a liquidity sensitive MSR and linear time deterministic pca ;).  Truthcoin isn't perfect, heck, it even has errors in the SVD description in the whitepaper.

Obviously every blockchain-operation would have to be deterministic...describing those operations would be out of scope for the truthcoin whitepaper. Even the LS-LMSR I am still not 100% sold on, as it has some trading complications (which perhaps, being 12 months behind, you haven't discovered yet). Martin, incidentally, has a 100% hit rate on pointing out "problems which are actually problems", so you might want to run your "critical flaws" past him first to make sure you haven't misunderstood.

And, while the paper has typos, the SVD-code I released with the paper (12 months ago) worked perfectly.

Quote from: joeykrug on February 10, 2015, 11:48:43 PM
The hash function idea has a flaw... I can publish my salt and not-hashed ballot and you can prove I voted a certain way.
...
Again, the way to fix this is to use rep. as a bond itself and if I prove someone revealed their vote early I get their rep (which is nowhere to be found in the whitepaper nor any whitepaper talk on hashing votes).

....what an amazing "flaw" you've "discovered".
http://forum.truthcoin.info/index.php/topic,128.msg517.html#msg517
http://forum.truthcoin.info/index.php/topic,131.msg538.html#msg538
...among several other places which I'm simply to lazy to link to.

I never claimed to have discovered the flaw, just pointing out that it was the only thing that really concerned me and that since it's easily fixable I wasn't actually concerned.  And that you have not mentioned hashing the votes with a salt in your whitepaper as an alternative to using unconventional crypto practices (which is an improvement for usability & simplicity). 

The problems with LS-LMSR and trading are significantly less than LMSR's (considering you can have a setup of 1000 vs 1100 and buy 10 shares for 1000 vs 1110 and end up paying 9.999999 with LMSR).  Even Hanson agrees with the idea of using some sort of liquidity sensitive market maker; it doesn't offend him if we don't use lmsr ;)  Of course, being an advisor to our project I'd hope you would bring up any further issues with LS-LMSR you know about, but if you want to keep them secret that's fine, LS-LMSR runs better in sims in the vast majority of scenarios compared to LMSR so it'd take a lot of convincing to get us to go with vanilla lmsr.

This flaw isn't critical, the only one to claim that is you, as it's quite easily solvable I don't really care how "critical" it may or may not have been (although without a bond mechanism it does make collusion easy unless one goes with the convoluted reporting technique described in the whitepaper, so perhaps you're right about it being critical)! 

The problem with linear PCA algos is the results vary when run even on the same machine when you rerun the program, that's what this algo solves (which is a major problem if you rely on nodes to get the same result, although you could just implement rounding into the protocol).  It's also much faster.

More babble.

I could explain why your MSR comments are wrong, but I'm forecasting another derailed thread of me repeating myself endlessly only to be ultimately ignored. I'm not sure I can handle another dose of boredom.

The implication that my great respect for Dr. Hanson would lead me to mis-favor certain mathematical formulas that he published personally (over slight-modifications to those formulas) in the hopes of not offending him is ridiculous.

Quote from: psztorc on February 11, 2015, 04:52:08 AM
More babble.

I could explain why your MSR comments are wrong, but I'm forecasting another derailed thread of me repeating myself endlessly only to be ultimately ignored. I'm not sure I can handle another dose of boredom.

The implication that my great respect for Dr. Hanson would lead me to mis-favor certain mathematical formulas that he published personally (over slight-modifications to those formulas) in the hopes of not offending him is ridiculous.

I ran that LMSR test using your excel file, can post you a link of my test where the cost is 9.999999 with vanilla lmsr vs ls-lmsr if you don't believe it.  Of course, if you think the price is justified when in a traditional parimutuel wager that would be absurd, then my point about ls-lmsr being better in this case is rendered invalid

Edit: Sorry, let me correct that, it's 9.999997

I don't know why I'm bothering...

You used the sheet without understanding it. The price reaction is the same for both if their betas are the same. Take all of the "overpayments" in LS-LMSR, and add them up, if that quantity of money was used to amp beta in the vanilla LMSR (where these overpayments were never made), the vanilla LMSR would have a beta which precisely equalized the price-reaction.

The LS-LMSR is better because it forces "who pays for this liquidity" in the blockchain to more-resemble "who pays for this liquidity" in real life. It doesn't magically produce liquidity somehow.

If you want to do something that actually would help me, why don't you try to derive the formula for transforming LMSR prices into their LS-LMSR counterparts. They are both 0 and 1 at their extremes, and at uniform ( 50%-50% in the basic two State case) they are each multiplied by v (from the paper, alpha = v / (n log(n)) ). Last weekend I tried transformations for two hours, trying to cheat and grab it easily using statistics.

Later this week, I will resign myself to do the...algebra...

I'm trying to follow this conversation, but can't see what you are talking about.  Could someone tell me where can I find the LS-LMSR?

http://www.eecs.harvard.edu/cs286r/courses/fall12/papers/OPRS10.pdf

LMSR requires one to set an initial "beta" parameter, but in LS-LMSR the beta is beta = alpha * sum(outstanding shares). Choice of alpha is actually very stable at  ( .05 / (n log n ) ) which produces slightly more tractable markets. Traders suffer under LS-LMSR (they are always overcharged).

Feel free to email me, I can send you an in-progress Excel sheet which tries to clarifies the differences.