Grin-Bitcoin Adaptor Signature Atomic Swap update thread

Hi everyone, I’m starting this thread for weekly progress updates on atomic swaps using adaptor signatures.

Over the past week, I’ve made decent progress implementing the cryptographic primitives needed for ECDSA adaptor signatures.

Not sure if the changes would be welcome upstream for rust-secp256k1, so will open discussion through an issue/PR. Depending on how the discussion goes, I may end up re-implementing ECDSA adaptor signatures as a libsecp256k1 module. Then expose interfaces in rust-secp256k1. TBD

Some problems came up when trying to implement Positive ECDSA pre-signatures. Because pre-signatures are not verified normally, I’m having a problem with the dual Schnorr proofs when s is negated (to ensure |s| <= (q-1) / 2).

The concrete NIZK proof isn’t specified in the paper, and I designed the dual Schnorr proof based on the scheme specified in https://tools.ietf.org/html/rfc8235. It works when s is not negated, but fails when s is. Still working on how to modify the proof to make it work, and still retain all its security properties.

When verifying the pre-signature in a way closer to how the original ECDSA schemes are verified:

r == f({H(m) * s^-1}*g + {r * s^-1}*X)
when r = k*g during signing

the signature verifies even when s is negated (as expected). So, the problem is definitely in the Schnorr proof I’m working on.

Will keep working on the problem, since it is fundamental for the security of the adaptor signature scheme.

After I solve the issue with the dual Schnorr proofs, I’ll continue with implementing the witness extraction and adaption algorithms.

When those are finished most of the cryptographic primitives will be finished™ (still need more testing and refactoring). Then I can start working on integrating the signatures into mimblewimble/grin-wallet and a PoC wallet using rust-bitcoin/rust-wallet.

Please feel free to ask questions, and give feedback in this thread.

Thanks for reading :grinning_face_with_smiling_eyes:

21 Likes

Awesome!! You are going to do great things for grin, you could cut-through the energy with a knife :slight_smile:

2 Likes

Think I found a partial solution to the pre-signature verification issue.

During verification of the Schnorr proof, now check the proof with both k*G and -k*G. So, when s is conditionally negated, the negation of the reconstructed K' passes verification, otherwise the normal reconstructed K' passes verification.

I think this may be secure, but allowing for two variations of the public key (that are attacker controlled), still feels like it will cause problems.

No knowledge of the private key is leaked, and the SUF-CMA property holds (no changes to the message or signature pass verification).

A question to the more experienced cryptographers in the community: does this solution open any known attack vectors? If so, what are they?

If anyone can see a problem with the scheme, please let me know. I’ll keep thinking about it, as I would like to have a clean solution.

Here is the relevant code snippet: https://github.com/GeneFerneau/adaptor/blob/main/src/schnorr.rs#L133-L148

7 Likes

Update 2021/04/02-09

Figured out the issue with negating s in the pre-signing phase, basically was doing the negation in the wrong place. Instead, s needs to be conditionally negated when adapting (“decrypting” in Elements terminology) the adaptor signature into a normal ECDSA signature. Then, during extraction (“recovery” in Elements terminology) test for whether the recovered private key’s inverse is negative. If it is negative, that means s was negated adapting to an ECDSA signature. So, you negate the private key to recover the correct key. That took a couple days to figure out…

I also changed the modified Schnorr identification proofs to Chaum-Pedersen proofs, since Chaum-Pedersen is the correct primitive to use. Didn’t know before Alex Xiong answered a related question on the Crypto StackExchange.

Incidentally, Elements Project developers were simultaneously implementing ECDSA adaptor signatures (I was unaware until recently). Their implementation follows a different paper One-Time Verifiably Encrypted Signatures A.K.A. Adaptor Signatures by LL Fournier.

The implementation doesn’t include a zero-knowledge proof that the “encryption public key” has a known private key (what Fischlin proofs are used for in my impl), but it appears their impl is the “official” ECDSA adaptor signature. I raised the question of adding Fischlin proofs to their scheme, so maybe that will be addressed.

The security risk is that a prover could provide a public key with no known private key, and the pre-signature verification would still pass. The verifier wouldn’t find out until the adapt/extract (decrypt/recover) phase. It also isn’t secure under the Universal Composability framework.

Either way, I will likely be adopting their impl going forward, since it includes standardization from BIP-0340. Will also raise an issue to see if anyone there is working on 2P-ECDSA, so that I don’t waste any more time duplicating work.

The next steps are to create the on-chain transactions for the atomic swaps on the Grin and Bitcoin chains. This will involve exposing libsecp256k1-zkp interfaces for ECDSA and Schnorr adaptor signatures to Rust (maybe this is already done, idk). With adaptor signatures exposed, can begin implementing the timelocked multisignatures using ECDSA-Schnorr and Schnorr-ECDSA adaptor multisignatures.

5 Likes

Update 2021/04/09-16

After discussion with @LLFourn and @jonasnick on GitHub, I understand the fundamental difference in approach between their ECDSA adaptor signature impl and mine. Their construction is secure, as long as it is not used to compose another scheme that relies on the Diffie-Hellman problem. If there is technical consensus to switch to Elements Project’s ECDSA adaptor signature impl, I’ll do so.

I have chosen to re-implement the generalized channel style ECDSA adaptor scheme in libsecp256k1-zkp, and am continuing with a Schnorr adaptor signature impl in the aggsig module. There is still some code cleanup in the ECDSA work, notably the extract algorithm allows for both the pre-signature s and its negation to extract the witness secret key.

Allowing the pre-signature s and -s to extract y decreases the search space by half for a brute-force attacker, which AFAIU takes one bit off the security of the scheme.

It doesn’t seem to seriously harm security, since an attacker could try s and -s anyway to achieve the same effect. While rejecting would drastically harm usability for honest users.

This is currently the biggest flaw I see in my impl. Only one version of the adapted signature s is allowed, and the rest of the scheme is SUF-CMA secure.

One possible solution is to simply reject high adapted s values in the adapt algorithm, instead of conditionally negating them. It will take more work to find a solution that doesn’t drastically hurt usablility, and remains SUF-CMA secure.

Edit: after reviewing the aggsig module, all the code is there for Schnorr adaptor signatures (many thanks @yeastplume @jaspervdm @garyyu!).

For the Schnorr adaptor signature impl, will use the aggsig module in secp256k1-zkp, and what’s outlined in the atomic swap section of the Grin docs. I may incorporate some of the BIP-340 stuff for nonce generation to create a “synthetic nonce” (the e value), since it hardens the scheme in low-entropy environments (like hardware wallets).

Synthetic nonce generation can be done in grin-wallet, other impls, or could use the HMAC-SHA256 based code in aggsig.

Now, can start integration work by adding a module to grin-wallet. Because I am working somewhat backwards from how I started (main impl in C, with Rust bindings), the integration into C/C++-based wallets should be even more straight-forward. However, integration into C/C++-based wallets will come after grin-wallet and rust-bitcoin/rust-wallet integration.

The main integration work of creating the multi-sig Bitcoin transaction should also be pretty straight-forward. Basically, the hash lock is replaced by a signature from the adaptor public key. The Grin side should be even easier, with maybe some additional slatepack types to support communication rounds. I’m optimistic for finishing the integration work next week to get to the point of making testnet transactions (it may end up taking longer).

Thanks for reading

10 Likes