New attack that the consensus might be vulnerable to ("P + e Attack")

[klosure]

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.

[zack]

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/

[psztorc]

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 (which I am currently improving, but is reasonably complete as is).

[zack]

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.

[joeykrug]

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. 

[psztorc]

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).

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.

[psztorc]

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.

[joeykrug]

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).

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.

[joeykrug]

"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.

[psztorc]

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%.

[joeykrug]

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).

[psztorc]

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.

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.

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.

[joeykrug]

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.

[psztorc]

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.

[joeykrug]

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