Attack vector exploiting voter limit

Previous topic - Next topic

LimLims

First, just wanted to say this is a super interesting project. Cryptocurrencies that perform useful work, with the POW algorithm or otherwise, are of particular interest to me. The energy/carbon cost of POW coins is, IMO, inelegant and wasteful, and one of the biggest drawbacks of the technology. The problem is that it's very difficult to come up with a kind of practically useful computation that's difficult to solve but easy to verify, where difficulty can be predictably scaled, etc. Prediction markets may be an elegant solution to this problem, although I think engineering a robust implementation will be challenging.

From my reading of the various truthcoin docs, it appears there may be a potential attack vector for gaming the decision voting phase with untruthful votes. It's likely enough that I've misunderstood or missed some detail, but anyhow, this is the gist:

- The docs suggest there will be a limit to the number of voters for a given decision (I saw 100,000 mentioned)
- The cost of mounting a successful 51% attack is therefore: [the minimum wallet balance required to vote] * 50,001
- Effectively this means only a fraction of the current supply is required to mount a successful attack

This assumes that votes are not weighted proportionally to wallet balance, i.e. all votes are equal (ignoring reputation modifiers for now). Perhaps the intention is to weight votes in direct proportion to wallet balance, but I didn't see this mentioned in the docs.

In any case, I think the only solution is to weight votes proportionally with wallet balance. But this may have its own complications, e.g.:

- If the number of votes is limited to 100k for a given decision, there must be a system for selecting the set of contributing votes from the total pool of votes. Assuming the selection is random, an attacker could exclude the voting power of large wallets with some statistical certainty by creating a huge number of minimum-balance wallets (i.e. hundreds of millions+) and dominate the vote that way.
- If an attacker can dominate the voting pool by sheer # of wallets, the excluded wallets miss out on voting rewards

I suppose a solution could be to require a sizeable minimum wallet balance to be eligible to vote, AND weight votes proportionally to wallet balance. That amount should be calculated such that the 100k voter limit could never be reached, even if all wallets held the minimum. This would remove the incentive to try to dominate the vote through sheer # of voting wallets.

psztorc

My lunch half-hour is already over, but just quickly glancing at this, you may have fallen victim to a common confusion.

There are two layers - a reputation layer and a currency layer. The votes are entirely weighted by the 'balance' of their "Votecoins" in the reputation layer. I expect >95% of those individuals in a mature Truthcoin ecosystem would have 0 votecoins of any type and thus never vote.

I hope I didn't misunderstand you, later tonight I'll catch up more. I can see from paragraph one that we have a lot in common.
Nullius In Verba

LimLims

#2
Quote from: psztorc on June 11, 2014, 04:03:51 PM
My lunch half-hour is already over, but just quickly glancing at this, you may have fallen victim to a common confusion.

There are two layers - a reputation layer and a currency layer. The votes are entirely weighted by the 'balance' of their "Votecoins" in the reputation layer. I expect >95% of those individuals in a mature Truthcoin ecosystem would have 0 votecoins of any type and thus never vote.

I hope I didn't misunderstand you, later tonight I'll catch up more. I can see from paragraph one that we have a lot in common.

Ok -- fair enough, votes are weighted by the balance of votecoins. Even so, I think most of my post is still salient. If the minimum balance to be eligible to vote is a trivially small amount, an attacker could create an arbitrary number of voting wallets, effectively guaranteeing them all 100k voting slots, and at the same time excluding all other wallets from receiving voter fees.

If you don't have a limit to # of votes per decision you risk blockchain bloat. I think the only way to disincentivise this kind of vote spamming attack is to enforce a high enough minimum votecoin balance, such that an attacker cannot achieve enough statistical certainty of securing all 100k votes to make it worthwhile.

Of course, I may be misunderstanding something fundamental here, so I'm happy to be corrected. :)

zack

By destroying 1000 truthcoins, you can produce a bunch of votecoins of a new type. Each set of votecoins is like a new color of colored-coins. Someone may create a pool of votecoins for basketball, and give the coins to a bunch of people who are knowledgeable about basketball.

When you ask a question, you select a type of votecoins to ask. The question you asked is decided by all the people who own votecoins of the type you selected. If you want to ask who won a basketball game, it is best to ask the basketball-votecoin holders, instead of the hockey-votecoin holders.

There are strong incentives against trying to commit collude and do a 51% attack. If 2% of the colluders decided to create a counter-collusion, they could trick the tricksters.

Every voter has an incentive to trick the other voters into voting the wrong way. Whoever votes best gets the biggest prize, whoever votes worst pays the biggest penalty.

LimLims

Quote from: zack on June 11, 2014, 05:30:55 PM
By destroying 1000 truthcoins, you can produce a bunch of votecoins of a new type. Each set of votecoins is like a new color of colored-coins. Someone may create a pool of votecoins for basketball, and give the coins to a bunch of people who are knowledgeable about basketball.

When you ask a question, you select a type of votecoins to ask. The question you asked is decided by all the people who own votecoins of the type you selected. If you want to ask who won a basketball game, it is best to ask the basketball-votecoin holders, instead of the hockey-votecoin holders.

There are strong incentives against trying to commit collude and do a 51% attack. If 2% of the colluders decided to create a counter-collusion, they could trick the tricksters.

Every voter has an incentive to trick the other voters into voting the wrong way. Whoever votes best gets the biggest prize, whoever votes worst pays the biggest penalty.

Ok -- I do understand all that. The attack vector I'm describing here is less about collusion and more about the cost of mounting an attack to exploit the limited number of votes in a decision.

Perhaps I should rephrase it in the form of a few questions:

- What is the minimum cost of casting a valid vote?
- What is the minimum cost of casting 100k votes?
- What is the minimum cost of securing all 100k votes with 99% probability, assuming 500 other voters?

zack

If you are a voter, then you are in a pool of voters. Maybe you are 1 of 100.
You can cast 1 vote for free, but you cannot cast 2 votes without knowing someone else's private key.

If you only own 1 of the 100 votecoins in a pool, then you can only cast 1 vote out of 100 on decisions that were asked of your pool.
If you owned 5 out of a pool of 200 votecoins, then you can cast 5 votes out of 200 on decisions that were asked of your pool.
I expect the largest pools of votecoins wont get bigger than 1000.

psztorc

Quote from: LimLims on June 11, 2014, 05:42:46 PM
Ok -- I do understand all that. The attack vector I'm describing here is less about collusion and more about the cost of mounting an attack to exploit the limited number of votes in a decision.

Page 21 of the whitepaper: "We may have to limit the total number of Voters (but not Owners) on a single blockchain to 100,000 or similar, involving a sort and filter to remove the smallest values."

Quote from: LimLims on June 11, 2014, 05:42:46 PM
- What is the minimum cost of casting a valid vote?
- What is the minimum cost of casting 100k votes?
- What is the minimum cost of securing all 100k votes with 99% probability, assuming 500 other voters?
Miner fee (possibly free), but you need Votecoins to do it.
You'd have to split your coins into 100,000 pieces, many of which would be removed by a pre-SVD a sort and filter.
For 100% probability, you'd need to own 100% of the Votecoins, then (pointlessly) split the total into 100k pieces. Otherwise, assuming the other 500 voters vote and have more than 1/100,000 of total Votecoins, the cost is infinite.
Nullius In Verba

LimLims

Quote from: psztorc on June 13, 2014, 01:22:13 PM
Quote from: LimLims on June 11, 2014, 05:42:46 PM
Ok -- I do understand all that. The attack vector I'm describing here is less about collusion and more about the cost of mounting an attack to exploit the limited number of votes in a decision.

Page 21 of the whitepaper: "We may have to limit the total number of Voters (but not Owners) on a single blockchain to 100,000 or similar, involving a sort and filter to remove the smallest values."

Quote from: LimLims on June 11, 2014, 05:42:46 PM
- What is the minimum cost of casting a valid vote?
- What is the minimum cost of casting 100k votes?
- What is the minimum cost of securing all 100k votes with 99% probability, assuming 500 other voters?
Miner fee (possibly free), but you need Votecoins to do it.
You'd have to split your coins into 100,000 pieces, many of which would be removed by a pre-SVD a sort and filter.
For 100% probability, you'd need to own 100% of the Votecoins, then (pointlessly) split the total into 100k pieces. Otherwise, assuming the other 500 voters vote and have more than 1/100,000 of total Votecoins, the cost is infinite.

Thanks for clarifying. I was thinking a sort & filter would do the job, that makes sense.

The other concern is blockchain bloat & network chatter. You may need to introduce a nontrivial fee for voting, otherwise an attacker can bloat the blockchain & bog down the network with millions of votes for every decision. Without a voting fee, the attack is zero cost (beyond the initial cost of funding the wallets). Even if the votes are filtered out beyond 100k, they'll still all be recorded in the blockchain as they come in. I think the more elegant way to solve these problems (and avoid having to impose voting fees) is to require a minimum votecoin balance for a vote to be eligible.