Topic: Atomic swaps using cut and choose (Read 12138 times)

.... you mean he finally did something instead of just talking about it? Let's see shall we?

@anonymint has apparently devised a secure and sound solution for cross-chain DEX:

https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers

Note he will not be able to discuss it with you here because he is perma-banned from bitcointalk.org.

There were participants but no submissions - therefore a second modified round:







https://streams.lykke.com/Project/ProjectDetails/5b33b9661c254022a8d0cb222b0d503b

Maybe somebody here is interested + skilled?

Lykke offer:





Details can be found here: https://streams.lykke.com/Project/ProjectDetails/b134b15b54e745559f26c217bef5a2f8

The above was an error. The reason had been stated before that above post was made as follows:


For example, an attacker could sign an intent to trade, but if I don't acknowledge it, then I would be implicated as the attacker. But if I sign an intent to trade and the attacker doesn't acknowledge it, then the attacker isn't implicated. So either way, it is flawed and doesn't solve the jamming problem that makes DEX (decentralized exchange between blockchains) implausible.

Bitshares' OpenLedger is decentralized exchange on the same blockchain employing pegged assets, but that is not equivalent (for one reason being that pegged assets do not precisely track the value of the asset they are supposedly pegged to).

I have devised another methodology for DEX which relies on selecting a mutual trusted party which cryptographically can't steal nor lockup the funds. This is a compromise between centralized exchanges (which can steal/lose funds) and purely DEX which can be jammed. jl777 is aware of the algorithm I have in mind.

I am finally close to finishing the iguanacore, the RPC layer is going through testing and so far all bugs found have been easy to fix.

So I am back to debugging the atomic swap and now have the state machine going through 80% of the process, but I am doing it in a loopback mode for now so I dont have to wait for new blocks and can just use the same unspents over and over for testing.

One issue with fully decentralized exchange is that people will lose their connections and the need to properly resume a pending trade needs to be solved. Assuming a power loss, then any temporary keypairs would need to be preserved so the funds can be properly claimed. Worst case is if a powerloss causes HDD corruption and you are in the protocol phase where you need the keys to claim it, you are losing funds.

So, this means a robust key storage and recovery mechanism is needed.

Or is it?

What I came up with is a deterministic keypairs system that allows recreating all temporary keys used for a specific swap, using just the accounts main keypair. I am assuming that proper care about backing up the main keypair is done.

Since there is a lot of divulging of the temporary keypairs going on, I wanted to make sure that neither the main keypair is compromised and also that this method doesnt open up an attack vector. I am thinking that since it has algebraic structure, it makes things a bit harder to spoof, but I cant see any direct way of the other party verifying things directly.

Here is the process:

bits256 instantdex_derivekeypair(struct supernet_info *myinfo,bits256 *newprivp,uint8_t pubkey[33],bits256 privkey,bits256 orderhash)
{
    bits256 sharedsecret;
    sharedsecret = curve25519_shared(privkey,orderhash);
    vcalc_sha256cat(newprivp->bytes,orderhash.bytes,sizeof(orderhash),sharedsecret.bytes,sizeof(sharedsecret));
    return(bitcoin_pubkey33(myinfo->ctx,pubkey,*newprivp));
}

A chain of keypairs are generated that starts from the main account keypair and that one needs to be protected. Each iteration of the chain uses the derivekeypair function. The orderhash is SHA256 of the orderbook entry that is being swapped. I am using the nodes orderbook entry, but maybe it is better to use the other party's entry, or a combine value. Probably the combined value is best, that way the keypairs chain is only for the exact swap.

The first step is to make a shared secret using the orderbook hash as the "pubkey" and the main account's privkey as the privkey. The curve25519 is used for speed and it does an SHA256 of the actual shared secret field element, so that protects the main privkey as well as curve25519 + SHA256 does.

This shared secret is put through another round of SHA256 with the orderhash and that is used as the privkey to generate an secp256k1 pubkey. There is a small chance of failure here as not all 256bit value are valid privkeys, but that is taken care of with the outer loop.

The outer loop does the following:
    for (n=0; n    {
        pubi = instantdex_derivekeypair(myinfo,&swap->privkeys[n],pubkey,privkey,hash);
        privkey = swap->privkeys[n];
        if ( pubkey[0] != firstbyte )
            continue;
        ...
     }

the first iteration, the privkey is the main account privkey, but after each iteration, the privkey is what is calculated in the prior iteration. Since each new privkey requires a shared secret using the main privkey, only the owner of that privkey is able to generate each iteration.

Also, I set all of Bob's privkey's so that the pubkey starts with 0x03 and Alice's starts with 0x02. that allows to use it as an extra consistency check and with the libsecp256k1 library, the time it takes is not really noticeable for generating about double the keypairs. this check also catches the case where the privkey is illegal as the first byte will be 0x00

Now comes the part I think might have some issues the part above that is in the  "..."

            calc_rmd160_sha256(secret160,swap->privkeys[n].bytes,sizeof(swap->privkeys[n]));
            memcpy(&txid,secret160,sizeof(txid));
            len += iguana_rwnum(1,(uint8_t *)&swap->deck[m][0],sizeof(txid),&txid);
            len += iguana_rwnum(1,(uint8_t *)&swap->deck[m][1],sizeof(pubi.txid),&pubi.txid);
            m++;

txid is a unit64_t and it is the lower 64bits of the bits256. I calculate both the rmd160+sha256 of the privkey and also the lower 64bits of the secp256k1 pubkey. These are the cut and choose keypairs that are sent to the other side. and all but the chosen one is sent back in full privkey form so the above uint64's can be verified.

maybe there is no need to send both variants and just one will suffice, but I have a feeling that with this additional constraint, it might be possible to get some proof that the chosen keypair is valid, prior to funds being committed via pederson commitments or something like that.

James

I will repeat again that the reason is that cut & choose (in theory) alters the economics of a 51% attack and thus (in theory) alters the security of the entire block chain where cut & choose is deployed (or other similar script ... which is why I have posited that multi-sig and for sure Turing-complete scripting is a generalized block chain security hole and scripts in zero knowledge may be the only way to close to hole).

Agreed that the security of block chains is predicated on there no being one (or coordinated) attacker with sufficient resources to perform a sufficiently long-range, lie-in-wait block reorganization. And this is predicated on the cost of the attack AND the potential gain from the attack. Cut & choose alters the economics of the plausibility of the gain from an attack. Mining concentration into pools (which may even be Sybil attacked so we don't know which pools are controlled by the same entity or which cooperate nefariously) coupled with hashrate rental capacities means that an attack is plausible except that these attackers don't want to be identified on a well established block chain (e.g. Bitcoin), because they don't want the community to fight them or otherwise destroy the viability of the block chain (e.g. the Chinese mining cartel allegedly controls 65% of Bitcoin's hashrate). With cut & choose, the 51% attacker can resign the DE transactions on the altcoin to pay to himself, but there is no way to prove which transactions were the attacker and which were the victim. Propagation is not proof, because nodes can lie about propagation and even be a Sybil attacked on the veracity of reported propagation. The only unequivocal proof is the longest chain rule (LCR).

Thus although we can't prove which of the double-spends are the victim, the victims can provably indicate that they took an order for a good or service from an attacker whom they can identify. Because if the attacker can't receive the good or service, then the attacker can't gain any income from the 51% attack. But with cut & choose, the attacker can't be identified.

Please understand the salient distinction. One general problem that I've observed numerous times in the block chain arena, is the very smart coders and mathematicians/cryptographers seem to have blind spots on economics (and even on the importance of degrees-of-freedom in design).



P.S. note I added a 4th bulleted point as quoted above.

(Again, I don't see how this attack is specific to cut and choose.)

The problem is fundamental to block chain crypto-currencies.  They inherently use a single validation (POW) to cover lots of transactions.  The security assumption is that no one attacker can controls enough of the transactions to make roll back worth it.

There are some egregious distinctions.

• Attacker identifies his own UXTO which the community can then decide to blacklist with a checkpointed fork. Thus taking away the attackers income and causing the attack to be a loss.
• Attacker will have a very difficult time purchasing things at sufficient scale that doesn't identify him in the real world. Whereas stealing balances will be impossible to prove for cut & choose
• The victims can prove they were double-spent by long-range chain reorganization. This isn't an absolute proof of an attack, but community evidence gathering at any sufficient scale of attack should come to a consensus about the existence of an attack.
• There is no way for any user to opt-out of this attack. Whereas, users can decide to not use a DE which exhibits being a risk, and/or to not use a block chain which enables such scripting. Thus in contrast, the community's diligence against this attack in existential. Meaning that the DE (and the general form of scripting that enables it) is likely to be shunned by users/investors once (in theory) the attacks occur. Whereas, a 51% attack is likely to be dealt with by community action by increasing hashrate and/or checkpointing.

This problem isn't really specific to currency trades.  An attacker could buy lots of stuff with an altcoin and then roll back all the payments a week later.

One of the weaknesses of an altcoin is that it has less security. 

The exchange creates a large market of things that you can (irreversibly and quickly) buy with the altcoins.  The underlying issue is that the altcoin has low security.

The concept behind the POW system is that a single POW can cover lots of trades.  This breaks down if enough people get together to try to double spend.  They can split the cost of double spending over all the attackers.

Some practical estimates:

Most top 100 bitcoin compatible altcoins trade a total of $1000 to $25000 per day, some get a lot more volume but usually it is due to CNY trading. The second 100 ranked trade $5000 or less as a guideline.

The CE risk is that 100% of all funds for all coins and in this aspect, even if it the only aspect, makes the DE much safer to trade. http://www.coindesk.com/court-cryptsy-ceo-predicted-exchange-failure/ vs blockchains to see where all the funds are. just the open disclosure would make DE superior, even if DE had all the same risks as CE. But I argue that DE risk is dramatically less due to the fragmenting of the funds across all coins. Also, the attacker is only able to make money by selling altcoins for BTC en masse to a lot of buyers which is quite a bit harder than the reverse

Let us say an exchange DE or CE gets 10% of the trading market and roughly $100,000 per day is traded. This would translate to a lot more on deposit, hard to estimate what percentage of trades are vs amount on deposit, if it is 10:1, then that means $1 million is at risk at this CE, all the time, from reorg attacks like DE and many other attacks and internal theft and simply flight of owner.

Now the DE, let us assume 100% of a coin is at risk, it is $2500 in this context. But actually it would be just the trades that are pending and if average trades complete in one hour or so, it might be $100.

With a budget of $100 or even $2500, I am having a hard time seeing that it would be a cash positive expectation if the process isnt fully automated. Even with a fully automated system, the cost to rent hashrate varies in realtime based on supply/demand and it is not like you can buy arbitrary amounts at a fixed cost.

My feeling is that like the cut and choose itself, it is all about positive expected return from conducting the attack and opportunity cost. Unless attacking the DE offers positive expected ROI, it is the same thing as saying someone can attack cut and choose and continue to lose money.

Can you estimate the hashrate it would take to attack some middlemarket coin,or rather, what coin could be attacked with a $2500 budget? Wouldnt the attacker need to pregenerate the blocks ahead of time? if so, there is a very big risk of not being able to make the trades to take advantage of this alternate chain. or can he wait until he has all the trades pending, then buy the hashrate, hope he is able to build a stronger attackchain with his double spends, then complete all the swaps, push the attack chain to reverse the altcoin payments.

Now he gets back the altcoins used for the trade, which had to be of equal value to the BTC gained, so he is stuck with altcoins for a chain that got attacked. maybe that will cause it to lose value and add more risk.

There seem to be quite a few "ifs" that all have to work out and the reward is 5BTC, not any 5000 BTC. So this seems an attack scenario for the financially challenged attacker, unless I am dramatically overestimating the cost to conduct the attack.

James

What is the method of attack if peers limit the amount of trades to the total fees paid by an address? other than some small amount for newbie accounts.

Wouldnt that require the attacker to conduct all attacks simultaneously using properly aged UTXO? Or are we assuming arbitrary depth of reorging the altcoin is available to attacker to deploy at anytime? Since the attacker wouldnt get the BTC until the trades complete, it seems he would have to borrow the BTC to buy the hashrate. And if an altcoin can be rewritten at will with the attacker's existing resources, what secures that chain without atomic swaps?

I guess the probability of successful attack creates some expected value, but I am having a hard time correlating the hashcosts for coins with decent trading volumes and the likely number of open trades at any given time. If the success of attack is not 100%, then that raises the risk of lost capital. I think realistic cost estimates are needed to attack the various chains and compare it to trading volume and amount of time that would be at risk

James

Attacker can make anchors for nearly free (large transaction values relative to transaction fees):

The attack is more general and it doesn't specifically attack the cut-and-choose system, I think.

- Offer to sell A altcoins for B Bitcoins to 1000 people
- Perform the atomic trades
- You now have 1000*B Bitcoins and lost your A altcoins
- Victims made sure there was 10*A worth of hashing confirmations on their transactions before moving to the next step
- You spend 50*A altcoins to buying hashing to rewind up to 50*A worth of blocks, which is more than their protection
- This rewinds history and your 1000*A altcoins are now yours again

A defense against this would be to mark the multisigs that are being used as anchors.  Rather than 2 of 2, you could use 2 of 3 with the 3rd key being a standard value.

You can then set k based on how many trades are happening on the altcoin chain.

As long as cross chain transfers are much smaller than real transfers, then this is less of a problem. 

Oh that reminds me what I meant to write in this thread when I woke up this morning but I got sidetracked.

The reason we can't allow Bob to sign instead of revealing his private key in order to reclaim his deposit, is because then the payments in the protocol can only be made contingent on revealing the private key. There is no way to put the deposit first on the block chain yet also have signing it require also signing the other transactions in the protocol, because those "other transactions" are not yet in the block chain when the deposit is confirmed (thus the deposit can't refer to transactions which are not yet confirmed as this would either be a security hole or would be impossible to pre-hash since the transaction paying Bob from Alice is not committed to a destination address).

You'd have to base these thresholds on a computation of how many other DE are operating on the same blocks, but then an attacker can DE trade to himself to fool your algorithm into an unbounded value of k (as high as the attacker wants to make it).

There are no solutions like that. The only solution is don't use cut & choose except where checkpoints are trusted, or develop the zero knowledge black box solution.

Indeed I predicted that

But credit gmaxwell's Coin Witness thread for making me aware of the SNARKs technology in 2013.

Gmaxwell just released a system for committing to an information exchange.

https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-February/012471.html

I think that solves the exchange problem.  In the article, they say it takes around 20 seconds to build up the proof for 5 SHA256 operations.  

In the zero knowledge proofs, you can prove that you ran a program.  The program of interest here would be


Bob could send Alice {BOB_PUB_KEY, BOB_PRIV_KEY_HASH, } and Alice could check that the proof proves that the program was run correctly and that it returned true.  It's a zero-knowledge-proof, which means that it gives Alice no info about bob_priv_key, but proves that Bob knows an input into the program that will get it to return true.

Since elliptic curve calculations are more complex than hashing operations, I think it might not be viable, but would work in theory.

[Edit]
Gmaxwell suggested using one of the schemes from here.

[Edit2]
The lightning dev list has some discussions about an opcode for checking public/private matches.  They call it CHECKPRIVPUBPAIR rather than CHECKPRIVATEKEYVERIFY.

http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011827.html

Because the altcoins are not confirmed spent on the Bitcoin block chain. The altcoin chain is free to disagree with the Bitcoin block chain.

The point about relative ordering of blocks between two chains (i.e. two partitions) is relevant to why it is impossible to enforce that the altcoin chain must follow the Bitcoin block chain's consensus. If you think out how you would attempt to specify a protocol for the altcoin chain so that it must obey the Bitcoin consensus, you will soon realize that it is impossible because no external truth exists in a block chain.


Sorry but you will need to read and understand deeply the threads I linked to. We've analyzed this already and it is an inviolable mathematical structure.

Although the "coin age" reference points are not absolute, i.e. could be rewritten by a chain reorganization attack, this will not reduce the squelching effect on a jamming attack, because that hashrate attack costs electricity (in PoW) and with the dual CLTV DE protocol, the attacker is not reimbursed.

The hard-coded destinations of a dual CLTV DE protocol obviously can't be altered by any hashrate attack so thus are absolute reference points.