New OpCode that would allow for algo<->{ed25519 blockchain} cross-chain atomic swap

[HashMapsData2Value]

Problem

I want to do atomic swaps between Algorand and scriptless blockchains. Specifically, ed25519-compliant ones. The full protocol is listed in this ARC issue.

It is based off of this paper here detailing the BTC-XMR cross-chain atomic swap, using "adaptor signatures" and semi-scriptless protocol. Note that one requires the use of ZKP to bridge the gap between ed25519 and secp256k1 (Bitcoin).

Solution

I need a new opcode, tentatively called ed25519skpkeq or ed25519equiv (or whatever you guys come up with). It takes in an ed25519 secret key and public key and returns a 1 if they correspond to each other. It generates a public key from the private key and compares it to the public key (which would've been loaded into it from the start).

Basically something like this in crypto/curve25519.go, plus/minus the pointer stuff. (I'm not a golang programmer and haven't done anything in C in years so forgive me.)

func ed25519Equiv(inputPublic ed25519PublicKey, secret d25519PrivateKey) bool {
    // https://libsodium.gitbook.io/doc/public-key_cryptography/public-key_signatures#extracting-the-seed-and-the-public-key-from-the-secret-key
    var result C.int
    var generatedPublic ed25519PublicKey

    result = C.crypto_sign_ed25519_sk_to_pk((*C.uchar)(&generatedPublic[0]), (*C.uchar)(&secret[0]))

    return *generatedPublic == *inputPublic
}

"You DO realise that this will LEAK the private key to the WHOLE WORLD?"

YES! That is precisely the point :-) Both of the participants have exchanged their public keys and created a new compound public key. The point is precisely for one of them to leak their private key (in exchange for some Algo or ASA trapped in the smart contract), and in the process give access to this new account on the other blockchain to their counterpart.

ALTERNATIVELY, if the Inc or Foundation would spare the time of one of the cryptographers, it might be possible to devise a better strategy using curveEd25519 or some convoluted ZKP solution. But the point here is to leak the private key regardless so I do not see any point in

Dependencies

Since go-algorand comes with its own LibSodium fork, everything needed is already inside. There is NO need for anything new. Just a matter of writing up the go code, creating the tests, determining the opcode cost and adding to the docs.

Urgency

As high as can be :1st_place_medal:

I am blocked by not having this so would love it if it could be added. Being able to build trustless bridges to ed25519 blockchains (not just Monero but also Nano, or even Cardano though I suspect something much better using State Proofs could eventually be made for the latter) would be a big boon to Algorand.

You can find the contract itself here: https://github.com/HashMapsData2Value/gjallarbru/blob/main/contracts/algo-ed25519/

These lines right here: Txn.note() == App.globalGet(alice_partial_pk), # REPLACE with NEW OPCODE Txn.note() == App.globalGet(bob_partial_pk), # REPLACE with NEW OPCODE

They are currently useless, just there for me to test out the protocol. The idea is that they would be replaced with:

ed25519equiv(Txn.note(), App.globalGet(alice_partial_pk)) ed25519equiv(Txn.note(), App.globalGet(bob_partial_pk))

And in the Txn.note(), alice or bob respectively (depending on the path in the protocol) would supply their respective private keys.

[jannotti]

I don't believe that function does what you think it does. Here it is:

int
crypto_sign_ed25519_sk_to_pk(unsigned char *pk, const unsigned char *sk)
{
    memmove(pk, sk + crypto_sign_ed25519_SEEDBYTES,
            crypto_sign_ed25519_PUBLICKEYBYTES);
    return 0;
}

In libsodium, a private key literally contains the public key. So there's no confirmation process here, it just extracts some bytes. So someone can "lie" to this function by slapping a random "private key" onto the public key in question.

I think that you would need an opcode that actually performs a signature with a private key, and then verifies that signature with the public key, to ensure they go together.

[HashMapsData2Value]

So how about this then @jannotti :

1. Decide on some piece of data A.
2. Use ed25519sign, passing in the data A and an inputted private key SK. Receive signature B.
3. Use ed25519verify, passing in data A, the signature B and the public key PK. Receive a boolean True/False.

Assert(ed25519verify(A, ed25519sign(Txn.Note(), A), PK))

ed25519verify is already an opcode (that costs 1900) but ed25519sign is not currently exposed.

Is this x2 something that would be able to fit inside the opcode budget? Would it be feasible to get ed25519sign as its own opcode, or the entire statement as its own opcode?

[HashMapsData2Value]

Realizing that it might be better to simply expose crypto_scalarmult_ed25519_base which directly computes the ed25519 public key/point on the curve from the inputed scalar.

(Since there is still some thought needed for this the priority is low.)

[kayabaNerve]

It's trivially possible to use any ed25519 signature verification opcode as a scalarmul verifier if you can obtain a byte comparison of the first 32 bytes of the signature you want to verify. By ensuring it's 32 0s, with the first byte set to 1 (so actually 31 0s), you're confirming it's the identity point. That means it's using an r of 0 and the s value is challenge * private key. This allows offchain recovery by calculating the multiplicative inverse of the challenge and multiplying it by s.

The protocol this is intended to implement, atomic swaps, specifically the design by h4sh3d, does not require any onchain cryptographic opcodes. It solely requires basic fund handling (and signature verification IIRC, which I'm not considering as cryptography, despite obviously being so, due to how high level it is under the current discussion).

Either: A) Implement adaptor signatures. It's not some insane ZKP solution. It's an established and well documented construction used in multiple places. B) If you do want your proof of concept to do this on chain, bloating it unnecessarily in a rejection of cryptography despite the Ethereum reference you cite actively working to remove it's onchain processing of this, use the existing opcodes.

That's my two cents on the matter. No experience with Algorand, nor the process here. Just commenting as someone who's implemented this protocol before, and assuming opcodes are not flippantly added. I'll also post my feedback on the ARC.

[HashMapsData2Value]

Thanks so much @kayabaNerve! Super grateful for your input. I'm closing this since it seems we can do this natively with ed25519verify.