Adaptor signature on ECDSA

Adaptor signature series
1.Adaptor signature -Schnorr signature and ECDSA-
2.Adaptor signature on Schnorr -Cross chain atomic swaps-
3.Adaptor signature on Schnorr -Lightning Network-
4.Adaptor signature on ECDSA
5.Adaptor signature in Discreet Log Contracts on ECDSA

The previous chapters described Adaptor signatures constructions based on Schnorr signatures, which cannot be used on Bitcoin mainnet at this time.

Currently, only ECDSA can be used in Bitcoin, and because ECDSA equations are not linear (including r-1 term) it is not possible to create multi-party signatures by simply adding them together. (Please refer to the first chapter “Adaptor signature -Schnorr signature and ECDSA-” for details.)

While 2 party ECDSA signature protocols and adaptor signature constructs have been proposed, they rely on complex cryptography and additional security assumptions making them difficult to use in practice.

Fortunately, an elegant alternative for 2 party ECDSA adaptor signatures was proposed. This proposal makes use of OP_CHECKMULTISIG to replace the complexity of the above mentioned protocols with a simple Bitcoin script operation. While this reduces privacy as the OP_CHECKMULTISIG itself is visible in the transactions, the secret value t used in the Adaptor signature cannot be retrieved by any third party. We refer to this approach as “semi-scriptless”. This chapter will focus on “semi-scriptless protocol on ECDSA”.

1–1.ECDSA Adaptor signing and decryption
ESDSA Adaptor signatures are tweaked using multiplication instead of addition, unlike Schnorr signatures. This is due to the fact that the ECDSA equation is not linear.

1–2.ECDSA Adaptor signing verification

In order to verify an ECDSA adaptor signature without having knowledge of the secret value t, we make use of an extra point R’= Rt ​​= rT. Here, R’ is defined as an elliptic curve point generated by multiplying the point T by the scalar r.

However, the third party cannot verify that it is created with R’= rT (They don’t know r). To prove this relationship a proof of discrete logarithm equivalence(DLEQ) is used.

1–3.DLEq

The goal of a DLEq proof is for a prover to convince a verifier that two elements have the same discrete logarithm with respect to two different generators, without revealing what the discrete logarithm is. This is exactly what we need to guarantee that R and R’ are indeed related and were generated using the same secret t. In other words, this proof will show that the same r value was used to generate both

The proof follows a standard proof of knowledge structure in three phases:

1.The proving party (prover) starts by choosing a random number r2, and provides the verifying party (verifier) with the values R2=r2*G and R2’=r2*T. This part of the protocol is called commitment, as the prover commits to a random value by giving its image in the groups G and T.

2.The verifier choses a random value e and sends it back to the prover. This phase of the protocol is called challenge, as the verifier is challenging the prover with a random value that it chose.

3.The prover computes s, and sends back this value to the verifier.

4.The verifier checks that:

Now let’s try to understand how this protocol works. First you should have noticed something about the equation at step 3. This is the same equation as for a Schnorr signature! So the prover is sending a Schnorr signature to the verifier, over a message chosen by the verifier. If this signature is valid, the verifier can be sure that the prover knows the value r. However, recall that our goal was to ensure that R’=t*R(=r*t*G). This is why the verifier performs two checks. Let’s look at these checks to understand better.

Notice that if these two equations hold, there must be a linear relation between them, and in fact this relationship is t:

The proof presented here has however one downside, the required interactivity between the prover and the verifier. Hopefully, there exists a mechanism, the so-called Fiat-Shamir transform, that enables taking an interactive proof and transforming it into a non-interactive one. This is at the cost of an extra security assumption, which assumes the existence of a truly random function that returns a different (and uniformly chosen) value for each unique query (this is the famous “random oracle model”). In practice, and for our proof, this means replacing the challenge part by requiring the prover to submit the e value, which is constructed using a hash function as follows:

The intuition behind this is that it would be very difficult (in practice impossible) for the prover to choose initial r and r2 values so that the result of this hash would not be a random value.
To come back to ECDSA adaptor signatures, they must thus be composed of the s’, R and R’ value, together with a non-interactive DLEq proof so that the receiver can verify that R and R’ are in fact related.
We have learned to verify the Adaptor signatures on ECDSA between multiple parties by proving the equivalence of the discrete logarithms in this way.

In the next post, we’ll pick up DLC with Adaptor signatures on ECDSA and go into more detail.

Reference:
Scriptless Scripts(May. 2017,Andrew Poelstra)
Simple Schnorr Multi-Signatures with Applications to Bitcoin (2018,Gregory Maxwell, Andrew Poelstra, Yannick Seurin2,Pieter Wuille)
Fast Secure Two-Party ECDSA Signing(2017,Yehuda Lindell)
Scriptless Scripts with ECDSA(Apr. 2018,Pedro Moreno-Sanchez, Aniket Kate)
Payment points without 2p-ECDSA or Schnorr(Oct. 2019,uSEkaCIO)
One-Time Verifiably Encrypted Signatures A.K.A. Adaptor Signatures (Oct. 2019 Lloyd Fournier)
Stack Exchange Q.How can we prove that two discrete logarithms are equal?