Atomic swaps using cut and choose

[TierNolan]

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.

[TPTB_need_war]

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.

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.

[TierNolan]

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.

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

[TPTB_need_war]

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.

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

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.

[jl777]

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<keypairs_needed; 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

[iamnotback]

Any way, I think I have thought of a solution for DE.

The key is to identify the attacker immediately so that all decentralized parties can apply my upthread blocking "Coin Days Destroyed" suggestion. The "Coin Days Destroyed" becomes the reference point that is signed by the owner of the resource, which thus apparently escapes from my generative essence conceptualization of the problem set.

So change to the protocol is the provider of the hash sends to the trade's counter party to sign it (hashed with the other party's UXTO address) so the counter party's UXTO can be identified. Then the hash provider (the potential jamming victim) posts this information in a timed refundable transaction to the block chain (spending to the payee contingent on releasing the hash). If the attacker never posts the reciprocal transaction on the other block chain, this enables anyone to identify that attacker and apply the Coin Days Destroyed filtering that I proposed upthread.

Note this eliminates the need for any fee. But I assume you can find some justification for a fee, such as perhaps keeping your source code for the DE app closed source and/or offering a centralized fee structure for matching orders, limit orders, etc.. You won't be able to steal funds, which afaik is the most significant advantage of DE over CE.

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

One way I contemplated is to have both parties sign the intention to trade, then they post it to this block chain. However, one might sign and the other might not, thus jamming the other party (in terms of computing the signature and the communication latency between the two parties). Also worse is that one party might sign more than one intention to trade or inadvertently do so if the attacker didn't sign immediately but later signed and published it to this block chain.

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.

[tempus]

Maybe somebody here is interested + skilled?

Lykke offer:





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

[tempus]

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







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

[Traxo]

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

[marcus_of_augustus]

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

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