P2PTradeX revisted

[Sergio_Demian_Lerner]

I came up with an attack on my P2PTradeX protocol (https://bitcointalk.org/index.php?topic=91843.0), which, in most cases, would thwart severely its utility. Let’s first review the protocol. A first party issues a conditional transaction in a block chain X, which contains a contract. The contract requests the the other party to provide a proof that a payment has been issued on the Bitcoin block chain. The proof consist of a Merkle branch from the Merkle root to the paying transaction, the block header plus the block headers of several confirmation blocks. The attack works as follows: if the attacker can perform simultaneous trades, then he can create a single counterfeit block branch containing many fake transactions. Almost 2200 standard looking fake transactions can be stored in a block. This block branch can be presented simultaneously to all the traders, sharing the cost of orphan mining over all the executed trades. The attack can be “pipelined” so the counterfeit branch is partially reused for each new batch of attacks performed in each new block. If the block reward is 25 BTC, then this limits the amount of money that can be safely traded to 11 mBTC per transaction, or 11 USD at 1K USD/BTC exchange rate.

Mitigations

If you want to trade higher amounts (say n BTC) you should either trade them by dividing n in many transactions of 11 mBTC each or, better, create a transaction whose size is (n*0.011) times the standard transaction size, adding more inputs. Outputs could also be added, but some other standard condition must be specified on transactions to avoid reusing the outputs for different trades.

Since traders request block chain branches that are recent, the attacker may not be able to reuse the fake block chain branch for many block intervals. To achieve the maximum revenue from the attack, the attacker may need to perform millions of simultaneous trades, at a rate of 3.6 trades per second. This may be impractical due to the lack of market for trades. If the trading market executes 1 order per second (1/7 of the maximum Bitcoin transaction rate) then the maximum secure trade per transaction rises to  40 mBTC.

Last, if the Bitcoin chain has periodic checkpoints (e.g. 1 per day) signed by a trusted authority, then the contracts may specify that the last block header should be check-pointed. This eliminates the problem completely but slows downs trade rate considerably and requires a TTP.

Conclusion

It’s has to be evaluated if the P2PTradeX is worth it’s complexity now that it has been found that it severely limits the amounts traded. Recently some other protocols have been designed that achieve the same result but do not require changing the core protocol, such as the one described by Socrates1024 in https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031. In comparison Socreates1024 protocol requires that some non-standard transaction templates are re-enabled in both block-chains but does not limit the amounts traded, while P2PTradeX does not impose any restriction on the Bitcoin side, while requires much computing effort on the alternate coin side, and restricts traded amounts.

 

[Sergio_Demian_Lerner]

A better analysis:

Suppose that the proof length is k=6 and that each block can carry n transactions, and the block can be rooted at most t=6 blocks in the past. If the block reward is 25 BTC, then the attacker may try to attack n*t victims by mining (t+k) blocks, and filling the first t blocks with n*t fake transactions. This will cost the attacker 25*(t+k) BTC.  This limits the amount of money that can be safely traded in each transaction to 25*(t+k)/(n*t).   Currently n is approximately 2200, and assuming t=k=6 we have that the maximum would be 22 mBTC per transaction, or 22 USD at 1K USD/BTC exchange rate, for a 6 block length contract. If the contract specifies values of k much higher than t, then the t value in the upper term can be ignored.  The approximate formula  for the upper limit when t=6 becomes 1.8*k mBTC.

A trade of 1 BTC in a single transaction will therefore require almost 3 days to be executed.

[socrates1024]

Isn't it the case that the other coin-swapping protocols are susceptible to this same weakness? This applies generally to double-spends too. The cost of mining a big-enough "attack fork" can be amortized over many concurrent double-spend attacks using the same attack fork.

Also....

Recently some other protocols have been designed that achieve the same result but do not require changing the core protocol, such as the one described by Socrates1024 in https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031.

Please cite this protocol as TierNolan's, I gave a clearer description but changed nothing https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949

[Sergio_Demian_Lerner]

Isn't it the case that the other coin-swapping protocols are susceptible to this same weakness? This applies generally to double-spends too. The cost of mining a big-enough "attack fork" can be amortized over many concurrent double-spend attacks using the same attack fork.

Yes, you're partially right, but I think there is at least one key difference. The difference that comes to my mind is the "visibility" of the attack event:

in TierNolan's protocol the attacker would need to create a long fork that everyone will see and that will become the best chain, and that will roll back tens of thousands of normal transactions, and that will destroy the credibility of one of the cryptocurrency involved. So the attack cannot be profited: if the attacker tries to cheat and get the coins of both cryptocurrencies in the trade, one of them will loose completely its value, so there is no incentive for the attack. Also the attack cannot be repeated.

In  p2ptradex you may do it without affecting the users of the BTC side of the chain. The attack will just prove that with enough incentives an attacker can "hire" mining power and execute the parallel attack and build a competing block branch, but without actually putting this branch "life". If does not need to be the best chain.  The fake chain will only be used to prove other users that certain transactions were done, when in fact they weren't. This does not destroy the credibility of the system, but just proves that the users did not paid attention to the recommended maximum trading limits, and made risky operations.


Iit has to be carefully analyzed in TierNolan's protocol what's the effect to forking at each protocol step, but I think that in every possible attack the attacker must build and publish his own long best chain. 

Also in both protocols there is the possibility of a miners-conspirancy not to include certain "redeem" transaction, but this will require almost all miners to be part of the clan.

 

[Sergio_Demian_Lerner]

Re-thinking: In  TierNolan's protocol, the attacker could include in the fork many (almost all) the transactions in the previous best chain, except for the redeem transactions he's attacking. I have no idea of what people will think of a kind of targeted attack that replaces a 50-block branch with another with almost the same transactions, but not all. But nothing good....