Cross Curve Atomic Swaps
Date: March 5, 2018
Transcript By: Bryan Bishop
Tags: Adaptor signatures
Category: Core dev tech
https://twitter.com/kanzure/status/971827042223345664
Draft of an upcoming scriptless scripts paper. This was at the beginning of 2017. But now an entire year has gone by.
post-schnorr lightning transactions https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/001031.html
An adaptor signature.. if you have different generators, then the two secrets to reveal, you just give someone both of them, plus a proof of a discrete log, and then you say learn the secret to one that gets the reveal to be the same. It’s a proof of equivalence discrete log. You decompose a secret key into bits. For these purposes, it’s okay to have a 128-bit secret key, it’s only used once. 128 bits is much smaller than secp and stuff. We can definitely decompose it into bits. You need a private key, but lower than the group ordering in both. I am going to treat the public key… I’m going to assume– it’s going to be small enough, map from every integer into a range, bijection into the set of integers and set of scalars in secp and the set of scalars in… It’s just conceptually because otherwise it doesn’t make sense to do that. In practice, it’s all the same numbers. You split it into bits, similar to the Monero Ring-CT thing, which is an overly complicated way to describe it. What about schnorr ring signatures? Basically, the way this works, a Schnorr signature has a choice of a nonce, you hash it, then you come up with an S value that somehow satisfies some equation involving the hash and the secret nonce and the secret key. The idea is that because the hash commits to everything including the public key and the nonce, the only way you can make this equation work is if you use – the secret key– and then you can compute S. And if hte hash didn’t commit, then you could just solve for what the public nonce should be. But you can’t do that because you have to choose a nonce before a hash. In a schnorr ring signature, you have a pile of public keys, you choose a nonce you get a hash, but then the next key you have to use that hash but the next key, and eventually you get bcak to the beginning and it wraps around. You start from one of the secret keys, you start one key passed that, you make up random signatures and solve them and go back, and eventually you can’t make a random signature and solve it, and that’s the final hash, which is already determined, and you’re not allowed to make it again, you have to do the right thing, you need a secret key. The verifier doesn’t know the order, they can’t distinguish them. What’s cool about this is that you’re doing a bunch of algebra, you’re throwing some shit into a hash, and then you’re doing more algebra again and repeating. You could do this as long as you want, into the not-your-key ring signature, you just throw into random stuff into this hash. You could show a priemage and prove that it was one of those people, it’s unlinkability stuff. You could build a range proof out of this schnorr ring signature. Suppose you have a pedersen commitment between 0 and 10, call it commitment C. If the commitment is 0, then I know the discrete log to C. If the commitment is to 1, then I know C - H, and if it’s 2 then it’s C-2H, and then I make a ring with C - H, up to C-10H, and if the range is in there, then I will know one of those discrete logs. You split your number into bits, you have a commitment to either 0, 1, or 0, 2, or 0, 4, or 0, 8, and you add all of these up. Each of these individual ring signatures is linear in the number of things. You can get a log sized proof by doing this. These hashes– because we’re putting points into these hashes, and hashes is just using this data. I can do a simultaneous ring signature where every state I’m going to share a hash function, I will do both ring signatures, but I’m using the same hash for both of them, so I choose a random nonce over here, I hash them both, and then I compute an S value on that hash on both sides, I get another nonce and I put both of those into the next hash, and eventually I’ll have to actually solve on both sides. So this is clearly two different ring signatures that both are sharing some…. But it’s true that the same index.. I have to know the secret key of the same index on both of them. One way to think about this is that I have secp and ed, and I am finding a group structure in this in the obvious way, and then my claim is that these two points, like Tsecp and Ted have the same discrete log. In this larger group, I’m claiming this discrete log of this multipoint is T, T and both the components are the same. I do a ring signature in this cartesian product group, and I’m proving that they are the same in both step, and this is equivalent to the same thing where I was combining hashes.
Say we’re trying to do an atomic swap. I have an adaptor signature where I can put some coins into a multisig. You give me an adaptor signature, which gives me the ability to translate your signature, which you will later reveal to take the coins, into some discrete log challenge. You give me an adaptor signature and some values, and I say yeah as long as this happens hten I will sign. So coins can use one curve, and you can claim curves from the other coin. On the other chain we do the same way, so you give me an adaptor signature with the same t value. I only have the adaptor signatures now. You sign to take your coins, I use your signature to learn the secret key, and then I can use that to take coins on my end. What if this was an ed25519 coin and a secp coin? It’s dependent on using the same t on both sides. I want you to give me two t’s and one on secp and one on ed25519 and a proof that they are using the same private key. How do you make the key– how do you limit the… When you make this ring signature thing, you have only so many digits. You divide it up into digits, you add up all the digits. For each digit, you give me a– you say this is either the secret key of 0 or 1, or 0 or 2, etc. Doesn’t have to be 128-bits. These proofs are pretty big. Each ring signature is like… if you do it in binary, 96 bytes per digit, 96 bytes * 128 in this case. This is just p2p. It’s like 10-20 kb. It’s not very much.
Do people currently have cross-chain atomic swaps for different curves? You could just use hashes, but anyone could see the hashes. They can link them.
The signer could give you a signature and the adaptor signature. There’s a challenger-responder protocol in that draft of the scriptless script.
We need a new definition or letter for sG. We use that a lot.