Author Topic: Index of papers attacks, etc.?  (Read 3219 times)

evand

  • Newbie
  • *
  • Posts: 5
    • View Profile
Index of papers attacks, etc.?
« on: July 25, 2015, 07:32:13 pm »
Is there a good index of papers on potential / actual attacks somewhere?

I only know of a few attacks, and it seems like there's not really a good organized repository with a current list of known attacks and how viable they seem to be.

(I would also want to include proposed attacks that aren't obviously ridiculous, but also don't seem to work.)

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #1 on: July 25, 2015, 08:21:32 pm »
I can get the list of attacks started.

Besides attacks on the cryptocurrency level like:
* filling up the blockchain with data so that it can't be downloaded in a reasonable timeframe.
* 51% attacks to double-spend money.
* long-range attacks https://blog.ethereum.org/2014/05/15/long-range-attacks-the-serious-problem-with-adaptive-proof-of-work/
* https://blog.ethereum.org/2015/01/28/p-epsilon-attack/ at the blockchain level, which is similar to a 51% attack, except everyone who is selfish will help you pull off the attack.
* The most common bug: finding a message that makes nodes crash, and sending it to everyone at once. (Flying Fox uses Erlang supervisors to avoid this problem.)
Here is an analysis of FlyingFox's security at the blockchain level: https://github.com/BumblebeeBat/FlyingFox/blob/master/docs/failure_modes.md
It is secure against up to 49% of coins being held by attackers.

truth coin has some additional attacks we need to worry about at the PM level:
* front running trades (I think putting the trades into a lightening network of channels is the best way to solve this, which is why Flying Fox has channels.)
* oracle gives incorrect outcome (Flying Fox lets the free market determine who is a worthy oracle. Augur only has 1 giant oracle which hopefully never lies)
* trading is blocked for a period of time. The validation of blocks, and the oracles are different jobs. A poorly designed blockchain would allow the block validators to block trading or oracles. (channels can make trading unblock-able, since it occurs off-chain.)
« Last Edit: July 25, 2015, 08:45:45 pm by zack »

evand

  • Newbie
  • *
  • Posts: 5
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #2 on: July 25, 2015, 08:48:44 pm »
So obviously it imports any attacks that work against Bitcoin, of which there are also some you haven't listed.

Incorrect oracle results are also possible because of simpler attacks than p+epsilon, such as ordinary bribery, and one person / group quietly buying up half the votecoins.

Frontrunning also has some more interesting and complex solutions involving batch market processing; see http://cdetr.io/smart-markets/ for some details and other useful implications.

In addition to simple front running, if all share creation must pass through market orders against the AMM, you get other HFT-ish problems when two people have client-side limit orders that are being reconciled over the course of many small trades. (This assumes there's no way for two limit orders that are large compared to the liquidity parameter to meet on the blockchain.)

There's also the freeloader market problem: can someone create a competing market that is cheaper to operate because it imports the truthcoin oracle results for market resolution without paying for them? Obviously they could do this as a centralized business, but that has a whole host of downsides. But can this be done as eg an Ethereum smart contract? (Counterpoints: will Eth work? Is that contract expensive to run on-chain? etc.) Can it be done as a separate chain, whose only goal is to be a leech?

I'm not sure whether the whole class of problems surrounding poorly resolved vague claims counts as an attack, but I haven't seen much discussion beyond "hopefully authors will learn that's a dumb idea".

Then there's the "unethical claims" problem: I've seen advocacy that such claims should be judged "undecidable", but I suspect the Schelling point and equilibrium behavior is to actually judge them as written. (In particular, I suspect that for any common set of norms, I as an attacker can find a claim where the question "is claim X ethical?" is a divisive question, and that I can often find such a claim where the answer to that depends on what exact event caused the claim to resolve that way.) I'm not sure how much of a problem this really is, but I've seen a lot of people assuming it would be bad. It also leads into the question of "paying for public bads".



In general, it seems that blockchain-level attacks are getting good, thorough discussion, and papers written that summarize the major points. But I'm not seeing that for stuff specific to Truthcoin, which bothers me. But there's a limit when the community is this much smaller.

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #3 on: July 26, 2015, 01:39:53 am »
1. Incorrect oracle results are also possible because of simpler attacks than p+epsilon, such as ordinary bribery, and one person / group quietly buying up half the votecoins.

2. Frontrunning also has some more interesting and complex solutions involving batch market processing; see http://cdetr.io/smart-markets/ for some details and other useful implications.

3. In addition to simple front running, if all share creation must pass through market orders against the AMM, you get other HFT-ish problems when two people have client-side limit orders that are being reconciled over the course of many small trades. (This assumes there's no way for two limit orders that are large compared to the liquidity parameter to meet on the blockchain.)

4. There's also the freeloader market problem: can someone create a competing market that is cheaper to operate because it imports the truthcoin oracle results for market resolution without paying for them? Obviously they could do this as a centralized business, but that has a whole host of downsides. But can this be done as eg an Ethereum smart contract? (Counterpoints: will Eth work? Is that contract expensive to run on-chain? etc.) Can it be done as a separate chain, whose only goal is to be a leech?

5. I'm not sure whether the whole class of problems surrounding poorly resolved vague claims counts as an attack, but I haven't seen much discussion beyond "hopefully authors will learn that's a dumb idea".

6. Then there's the "unethical claims" problem: I've seen advocacy that such claims should be judged "undecidable", but I suspect the Schelling point and equilibrium behavior is to actually judge them as written. (In particular, I suspect that for any common set of norms, I as an attacker can find a claim where the question "is claim X ethical?" is a divisive question, and that I can often find such a claim where the answer to that depends on what exact event caused the claim to resolve that way.) I'm not sure how much of a problem this really is, but I've seen a lot of people assuming it would be bad. It also leads into the question of "paying for public bads".

In general, it seems that blockchain-level attacks are getting good, thorough discussion, and papers written that summarize the major points. But I'm not seeing that for stuff specific to Truthcoin, which bothers me. But there's a limit when the community is this much smaller.

You only have yourself to blame, I'm afraid.

Did you visit the front page? It has a link to: http://www.truthcoin.info/weaknesses/

Or, open the whitepaper and use cntrl + f to find responses to #1, #2, #4 ("free rider"), and #5. In the FAQ I mention that #6 will be addressed in an appendix, which I've finished but haven't taken the time to edit. The last item, #3, I really don't know what you mean.
Nullius In Verba

evand

  • Newbie
  • *
  • Posts: 5
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #4 on: July 26, 2015, 03:04:27 am »
> You only have yourself to blame, I'm afraid.

You're being rather obnoxious about this, and I don't understand why. If you'd rather not answer my questions, please don't; perhaps someone else will. I'm not an idiot, I've read your whitepaper more than once, I've read your FAQ and weaknesses section, and I still have questions. Have you considered alternate explanations beyond "Evan is an idiot"? Some obvious ones that spring to mind include:

* I haven't communicated my questions in a way you understand
* You haven't communicated your answers in a way I understand
* The answers exist and are well communicated, but are difficult to find

I was specifically trying to assume the third case when I created the thread. It's not obvious where to find an index of such papers, or whether they exist. What I'm hoping is that the original whitepaper spurred some discussion (probably in the form of forum posts or email threads or irc chats) that is a lot of work to follow, and that someone then turned that discussion into papers that reasonably summarize the state of the art of current (or near-current) research. It seems to me the "papers" section on the website hasn't been updated in quite some time.

Searching "free rider" in the white paper produces no results, "free" produces 6 that look unrelated. I haven't reread the entire thing, but I did skim it and look at every page, and didn't see anything that looked relevant. The paper has no table of contents, and no index that would make finding such things easy if I chose the wrong search terms but knew what good search terms might look like. I've been reading forum posts a bit, but have yet to read all of them. I freely admit my understanding of the state of the art of Truthcoin is neither complete nor fully current; that's why I was asking if there exists a good index of the current state of the art, so that I could get up to speed faster than reading everything that's ever been written, in particular the results of post-whitepaper research.

When Zack started a list of known attacks going, I figured I'd add to it. I'm well aware there has been discussion of some of these attacks before, both the ones Zack listed and the ones I listed. I was assuming nothing I said was novel, merely asking where to find organized info, if such info has been organized.

re: #3, what is the expected sequence of events when one trader is willing to buy YES shares at probabilities as high as 0.51, the price is currently 0.51, a new trader arrives who is willing to buy NO shares at probabilities as low as 0.49, and their willingness to trade is large compared to the amount of liquidity the AMM will provide between those prices? Does this result in more than 2 transactions? Do those transactions leak information in such a way that someone can make informed HFT guesses about the traders intents and make money?

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #5 on: July 26, 2015, 03:35:22 am »
I don't think you're an idiot. Sorry if you feel that way, but if you're going to ignore what's written the first time around, what's the point of writing it a second time? Duplication of the explanations is not only more work, but it is actually highly dangerous, because it increases the liklihood of errors / out-of-context explanations. On top of that, people will assume (as you have) that they need to track down and read all kinds of scattered Q&A, when they do not. The whitepaper is maintained to be the single authoritative up-to-date document, and it links to its own errata section (which is https://github.com/psztorc/Truthcoin/tree/master/docs#addendum--errata ).

Comments such as these:
In general, it seems that blockchain-level attacks are getting good, thorough discussion, and papers written that summarize the major points. But I'm not seeing that for stuff specific to Truthcoin, which bothers me. But there's a limit when the community is this much smaller.
...I find to be offensive, given that I have a "Weaknesses" section on my website (inside which I could link to any relevant criticisms). Comments such as the above make it seem like having a conversation with you about Truthcoin's weakness is a waste of time, because your behavior only makes sense if you believe that my own publications, on that very topic, are irrelevant.

The phrase "free-riding" is in a figure on page 26, which wasn't OCR'ed (and wouldn't show up in cntrl+f). It is discussed lightly on page 28.

Zack is a very interesting guy doing a lot of cutting-edge work on blockchains in general ("cutting edge" being both "potentially great" and "a lot of work to make sure it actually works"). I consider "attacks inherited from Bitcoin" to be out of the scope of this project. You should also know that I consider Vitalik's P+e attack to be rather sophomoric, having dismissed it in a single comment on his post, and even explained on this forum how Truthcoin can profit if someone attempts it (through it's unique ability to split perfectly-coordinated votes).

Zack's work on channels may improve the trading experience, and front-running experience, greatly.

re: #3, what is the expected sequence of events when one trader is willing to buy YES shares at probabilities as high as 0.51, the price is currently 0.51, a new trader arrives who is willing to buy NO shares at probabilities as low as 0.49, and their willingness to trade is large compared to the amount of liquidity the AMM will provide between those prices? Does this result in more than 2 transactions? Do those transactions leak information in such a way that someone can make informed HFT guesses about the traders intents and make money?
Are you sure you set this example up correctly? It seems to me that no one will want to trade at all. I don't see how a sequence of trades would leak reliable info pre-trade.
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Index of papers attacks, etc.?
« Reply #6 on: July 26, 2015, 04:28:29 am »
Welcome to the forum Evan

re: #3, what is the expected sequence of events when one trader is willing to buy YES shares at probabilities as high as 0.51, the price is currently 0.51, a new trader arrives who is willing to buy NO shares at probabilities as low as 0.49, and their willingness to trade is large compared to the amount of liquidity the AMM will provide between those prices? Does this result in more than 2 transactions? Do those transactions leak information in such a way that someone can make informed HFT guesses about the traders intents and make money?

Im not sure I completely understand your question, but it sounds like a failure mode I think about.

With Truthcoin as Paul wrote in the white paper there is an LMSR market maker to determine the price. The example that breaks the system is when two traders want to move the price back and forth between a small range, like 2%. For example, one trader wants the price at 51% and the other wants it at 49%
They would take turns buying the same amount of shares back and forth, and the price would jump between 0.49 and 0.51
Every time the price moves it would be another transaction on the blockchain with another tx fee. You have to wait multiple blocks of confirmations between each trade for it to be secure. Eventually one of them spends as much money as they are willing, and would stop moving the price back and forth. Since it is repetitive, it is dangerous that someone could front run it.

With Flying Fox it would be an order book instead of an LMSR. Channels make things a lot nicer.
The first trader would make an order to bet at or below the price 0.51, and they put 1000 money units, then a different trader could come and match that trade. The server that stores the order book and matches up the pair of traders takes a small fee in the trade. The traders are using channels to make the bet, so none of it gets put onto the blockchain. You don't have to wait any confirmations, and fees will be thousands of times smaller. 
« Last Edit: July 26, 2015, 04:44:33 am by zack »