1. Introduction

Simply stated, a bitcoin transaction is a transfer of spending control between different parties over a pre-specified amount of satoshis. A satoshi is the smallest fraction of a bitcoin and is equivalent to BTC In order to successfuly complete said transfer, the sender must demonstrate that she is the rightful owner of the satoshis she wishes to spend. Such a proof is imperative as it allows the different nodes on the network to reach an agreement regarding the validity of the transaction and as a result, facilitate its inclusion in the blockchain.

At the time of writing, bitcoin’s proof of ownership is encapsulated in a particular type of digital signature known as the Elliptic Curve Digital Signature Algorithm (ECDSA). It is a variant of the Digital Signature Algorithm (DSA) that relies on Elliptic Curve Cryptography (ECC).

In the first section, we introduce the DSA scheme, prove its correctness, and discuss some of its security properties. In particular, we point out that as of the time of writing, and despite its prevalence in various cryptographic settings, we do not know of any valid security proof of DSA in the random oracle (RO) model. However, we highlight that slight variations of it can be proven to be secure.

In the second section, we introduce the ECDSA scheme and prove its correctness. Later on, we present a python-based implementation to further elucidate its building blocks. We also describe how an ECDSA signature gets typically encoded within a bitcoin transaction. Finally, we highlight some of the scheme’s potential shortcomings including the absence to-date of a security proof in the RO model, its susceptibility to being malleable, and its non-linear design that hinders an efficient implementation of multisignature transactions.

In order to better understand the material contained herein, we recommend that the reader familiarizes himself with the necessary prerequisites fleshed out in the following three posts:

1. Groups and Finite Fields
2. Elliptic Curve Groups
3. Digital Signatures and other Prerequisites

2. Digital Signature Algorithm (DSA)

The invention of the Digital Signature Algorithm (DSA) is attributed to David W. Kravitz [9] who used to work for the National Security Agency (NSA). The legitimacy of this invention has been contested by Claus Schnorr (the inventor of the Schnorr signature scheme), who asserted that DSA is covered in another patent of his [12]. Readers interested in the claims and counterclaims surrounding the origin of DSA can refer to e.g., [2].

The DSA scheme is built on the finite fields and where and are two large prime numbers of respective bit-lengths and and such that is a divisor of We can think of as the scheme’s security parameter. Let be an element of order in the multiplicative cyclic subgroup One way of finding such a consists in letting for arbitrary such that To see why this construction works, note that:

• By Lagrange’s theorem, we know that order divides Let order for some integer
• We then have This guarantees that order must be a divisor of But since is prime, it must be that order is either equal to or equal to
• If order were equal to 1, we would have But by definition, we required that As a result, it must be that order

Similarly to other signature schemes, we define DSA as a set of three algorithms:

• The DSA key generation algorithm . On input , it produces a pair of matching private and public keys where is a randomly chosen element in and The algorithm is modeled as a PPT Turing machine.
• The DSA signing algorithm . Suppose a user with private and public key pair decides to sign a message Let be an appropriate hashing function (e.g., SHA-256) and let

  

  be the truncation function mapping strings of arbitrary length to strings of length at most and such that:

  • It acts as the identity map if the input is of length at most
  • It outputs the least significant bits of its argument otherwise

  proceeds as follows:

  1. Let
  2. Select a random element We point out that it is crucial to select a different random for each signature instance. Otherwise, an adversary could use two signatures sharing the same to deduce the common value and subsequently break the signer’s private key as we explain later on.
  3. Set If go back to the previous step and choose another random
  4. Compute Here, is the mutiplicative inverse of in modulo arithmetic and we have previously seen in the prerequisite sections how to compute it efficiently using the Extended Euclidean Algorithm. If go back to the first step and choose another random

  finally outputs a signature . The algorithm is modeled as a PPT Turing machine.

• The DSA verification algorithm }. Given a signature a message , and the public key of the presumable signer, verifies the validity of by checking the following:
  • If or outputs False.
  • Otherwise:
    1. Compute and where is the multiplicative inverse of in modulo arithmetic.
    2. Compute
    3. If outputs True. Otherwise, it outputs False.

  is a deterministic algorithm as opposed to probabilistic.

Correctness of DSA The DSA scheme satisifies the correctness property. In other words, any signature generated by will cause the verification algorithm to output True. To see why, let be an appropriate signature on message First note the following chain of implications:

Recalling that order and noting that for some appropriate integer we have:

we get:

Similarly, for some appropriate integer we can write:

Using one more time the fact that order we get:

Upon verification, algorithm computes and concludes that based on the previous equality. This result shows that the output of satisfies the verification algorithm hence demonstrating the correctness of DSA.

Security of DSA: The importance of the randomness of the parameter A necessary condition for the DSA scheme to be secure is for the parameter to be used once per each signature instance. Indeed, if this were not the case, one would be able to derive the private key of the signer. To see why, suppose that and are two signatures generated by the same signer with private key and such that We write:

By design of we have

We then get:

This allows us to solve for the parameter as follows:

Finally, note that mandates that This implies that Consequently, one can retrieve by using either signatures or the hash of the corresponding message or and the common value

Security of DSA: A note on existential unforgeability. A security proof for a digital signature scheme is essentially a proof of resilience against existential forgeries in the adaptive chosen-message setting (EFACM). The rather odd observation is that despite the widespread adoption of DSA, there is no known proof of its security in the RO model. Typically, such proofs rely on a reduction technique that transforms a hypothetically successful forgery attack into a solution to a computational problem believed to be hard (e.g., finding discrete logarithms over certain finite groups).

Before proceeding further, we recommend that the reader familiarizes himself with the content of the following two posts for a better understanding of the logic outlined in this section:

• Digital Signature and other Prerequisites to learn more about digital signatures, forgeries, and security proofs.
• Pointcheval & Stern’s Generic Signature Scheme to see the reduction technique in action as it applies to e.g., the Schnorr signature scheme.

The belief that a DSA security proof may be difficult to construct rests on our inability to date to successfully leverage the reduction model (RM) in that respect. However, it is important to note that the absence of a proof at the time of writing does not imply that a proof does not exist. In what follows, we attempt to argue why a DSA security proof based on RM may be difficult to devise. To do so, we will need to revisit the foundational steps of the model as outlined in the aforementioned posts.

Recall that RM applies a reductio ad absurdum argument that starts by assuming that the signature scheme is not secure i.e., there exists a PPT adversary such that:

where is ‘s random tape, is the random tape of DSA’s signing algorithm (not to be confused with the that appears in ECDSA’s signature), is the random oracle, is DSA’s security parameter and a quantity non-negligible in

Subsequently, the model applies a series of steps that culminate in the extraction of a solution to a problem thought to be computationally hard e.g., finding the private key associated with a given public key . In DSA, one way of solving for the key consists in devising two distinct valid signatures and leading to a linear equation in Conditions C and C below are jointly sufficient for this to be possible:

C

C

To see why, substitute with and write C as Since order this implies that C would then allow us to solve for

In what follows, we derive necessary conditions for C and C to hold. We then argue why applying RM to the DSA scheme does not imply with certainty that these necessary conditions actually hold. This means that we cannot imply with certainty that C and C hold, leading us to conclude that solving for may be difficult after all. We reiterate that we are not arguing that a security proof for DSA is not possible, but rather that such a proof may be difficult to achieve using the reduction technique.

First, since both signatures are valid, the verification equations guarantee that for :

As a result:

C

Consequently, and must exhibit a certain relationship for the first condition to hold. With overwhelming probabilty, two randomly chosen parameters and will not satisfy this equality.

Since C and since for we get:

C C

We also know that for This yields:

The takeaway is that to be able to effectively use the reduction technique to solve for in the case of DSA, one will possibly need to ensure that valid signatures and satisfy the following at a minimum:

1. and
2. or

We deliberatly used the term “possibly” and the justification is two-fold:

1. In the above, we limit ourselves to a particular type of computationally difficult problem, namely solving a discrete logarithm over a multiplicative cyclic subgroup. Nothing prevents anyone from considering other hard problems for which C and C could become obsolete.
2. Conditions C and C were sufficient to solve for but not undoubtedly necessary.

In what follows, we apply the remaining steps of RM and for argument’s sake, we assume that steps two and three hold. In other words, we assume that we are able to:

• Build an adequate simulator where is the simulator’s random tape.
• Show that the probability of faulty collisions in this simulated environment is negligible.

In the fourth step, one would show that an adversary that can forge a signature, is also capable with non-negligible probability of creating a second forgery distinct from the first one. Most importantly, the two forgery attacks would behave in a similar way up to a certain well-defined event. Formally, one would show that the following quantity is non-negligible in :

When producing its first forgery , the adversary is assumed to make a number of queries to random oracle We denote the query as and its corresponding random oracle reply as (i.e., The second forgery is created through a process known as an “oracle replay attack” and consists of:

• Using the same random tape of the simulator used in the first attack.
• Using the same random tape of the adversary used in the first attack.
• Ensuring that the replies of the random oracle queried in the first and second attacks match up to the query ( after which the replies could start to diverge.

The standard forking lemma applied in RM subsequently leads to the following result: Given a successful forgery tuple we can find with non-negligible probability another successful forgery tuple such that:

, but

We let correspond to , and correspond to . At this stage, we highlight two important observations:

1. Adversary is bound to query on input at some point during the first forgery experiment. To see why, note that any successful forgery must pass the verification test. If never queried on input the probability of it generating a successful forgery would be upperbounded by the probability that (i.e., the value that RO returns to on query ) satisfies the verification condition, namely:

   
   
   

   Since could be any value in and since order is a prime number equal to the probability of such an event is on the order of which is negligible in .

2. Since the two forgery experiments have the same random tapes and , and since and behave the same way on the first queries, we can be confident that the first queries sent to the RO in the two experiments are identical. In particular the two queries are the same.

In light of the above observations, if we let be the index of the query corresponding to we can ensure that while This will satisfy part of the necessary conditions that we discussed earlier for C C to hold. The issue however, is with enforcing the remaining part of the necessary conditions, namely that and be appropriately linked. The reason this is difficult to enforce is because there is no guarantee that gets selected by before is queried to could very well be specified after the query causing the two signatures to have associated parameters and without any particular binding relationship.

Due to this limitation, one cannot conclude with certainty that DSA is necessarily secure in the RO model. However, slight variants of the DSA scheme can be shown to be secure. We mention below two such variants due to Brickell [5] and to Pointecheval and Vaudenay [11]:

1. The Brickell variant replaces the operation that appears in the calculation of in DSA’s algorithm and in the calculation of in DSA’s algorithm by a random oracle In other words, becomes and becomes We refer the reader to [5] for a proof of its security.
2. The Pointecheval-Vaudenay variant takes the hash of and combined instead of that of alone (i.e., instead of This construct seems to be the most natural, especially in light of the previous discussion about the difficulty of building a security proof for DSA. One can only wonder why the NSA did not adopt this formulation as part of its original scheme. We refer the reader to [11] for a proof of its security.

Aside from these variants, Fersch et al. [8] devised a security proof for the unmodified version of DSA by introducing an extra modeling constraint. This constraint, also known as the bijective random oracle, applies to the conversion function:

The conversion function is none else than the one that DSA’s signature algorithm uses to calculate with group element as input. The constraint that Fersch et al. impose consists of representing as a composition of three functions such that is a bijection and such that both and are modeled as random oracles. We will not go over the details of their proof, but the interested reader can refer to [8].

3. Elliptic Curve Digital Signature Algorithm (ECDSA)

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a variant of DSA that uses Elliptic Curve Cryptography (ECC), a topic that we previously introduced in the post on Elliptic Curve Groups. For a given public key length, ECC bestows on ECDSA a significant security advantage over its DSA counterpart. This advantage is a consequence of the observation that the security of cryptographic primitives built on the presumed hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP) surpasses that of those built on the presumed hardness of the Discrete Logarithm Problem (DLP) on multiplicative cyclic subgroups.

To put this comparative advantage into perspective, we point out that the difficulty of solving ECDLP with 160-bit long public keys is comparable to that of solving DLP on a multiplicative cyclic subgroup with -bit long public keys [3]. In this context, the notion of difficulty refers to the expected amount of time needed to break the discrete logarithm problem.

Being an ECC primitive, ECDSA requires signers and verifiers to agree on the parameters of the elliptic curve to be used. For bitcoin, the curve is secp256k1 whose defining parameters were previously introduced in the Elliptic Curve Groups post. We relist them below for ease of reference:

• The elliptic curve group associated with secp256k1 is where

  

  • is the prime
  • is the operation denoting elliptic curve point addition.
  • is the point at infinity.
• The chosen base point of has decimal coordinates given

  
  
  

  
  
  

  Bitcoin’s public-key cryptography is hence conducted on the subgroup

• Moreover, the order of is chosen to be a prime number equal to

  
  
  

• It turns out that the cardinality of is equal to which is a prime number. As a result, it is a cyclic group and any of its elements could serve as a generator (refer to Groups and Finite Fields for an introduction to cyclic groups).

We let denote the security parameter associated with ECDSA. In what follows we define this signature scheme as a set of three algorithms:

• The ECDSA key generation algorithm . On input , it produces a pair of matching private and public keys where is a random element in and is the elliptic curve point given by ( times). The algorithm is modeled as a PPT Turing machine.
• The ECDSA signing algorithm . Suppose a user with private and public key pair decides to sign a message Moreover, let be an appropriate hashing function (e.g., SHA-256), and let

  

  be the truncation function mapping strings of arbitrary length to strings of length at most and such that:

  • It acts as the identity map if the input string is of length at most
  • It outputs the least significant bits of its argument otherwise

  proceeds as follows:

  1. Let
  2. Select a random element As was the case for DSA, it is crucial for ECDSA to select a different random for each signature instance. A similar proof to the DSA case demonstrates that failure to do so would jeopardize the private key.
  3. Compute the elliptic curve point

     ( times)

  4. Set If go back to step 2 and choose another random
  5. Compute where is the multiplicative inverse of in modulo arithmetic. Note that as shown in the post on Groups and Finite Fields, if were not prime this inverse could not be guaranteed to exist for arbitrary If go back to step 2 and choose another random

  finally outputs a signature . The algorithm is modeled as a PPT Turing machine.

• The ECDSA verification algorithm . Given a signature a message , and the public key of the presumable signer, verifies the validity of by checking the following:
  1. If does not satisfy the elliptic curve equation or if (i.e., the identity element of the elliptic curve group), outputs False.
  2. If or , outputs False.
  3. Otherwise:
     • Compute and where is the multiplicative inverse of in modulo arithmetic.
     • Compute
     • If then outputs True. Otherwise, it outputs False.

is a deterministic algorithm as opposed to probabilistic.

Correctness of ECDSA. The ECDSA scheme satisifies the correctness property. In other words, any signature generated by will cause the verification algorithm to output True. To prove it, we follow a similar logic to the one used to prove DSA’s correctness. More specifically, let be a signature on message and note that:

The verification algorithm will then compute:

The previous equality allows us to conclude that:

hence validating and establishing ECDSA’s correctness.

Illustrative implementation in python. In what follows, we show how the ECDSA signature scheme could be implemented in python. Note that it is always recommended to rely on existing and well-tested implementations. The one below is for educational purposes and we built it from scratch with the sole intention of illustrating the process.

ECDSA relies on elliptic curve point addition and scalar multiplication. We include below five python methods, the first three of which feed into mul_scalar that perfoms elliptic-curve point multiplication. The last method verifies whether a point belongs to a pre-specified elliptic curve or not. The first two methods were sourced from [7].

1. extended_euclidean_algorithm(a, b): it takes two integers and and returns a three-tuple consisting of gcd and the bezout coefficients and that satisfy gcd (refer to Groups and Finite Fields):

   
   def extended_euclidean_algorithm(a, b):
       """
       Returns a three-tuple (gcd, x, y) such that a * x + b * y == gcd, where gcd is the greatest common divisor of a and b.
   
       This function implements the extended Euclidean algorithm and runs in O(log b) in the worst case.
       """
       s, old_s = 0, 1
       t, old_t = 1, 0
       r, old_r = b, a
   
       while r != 0:
           quotient = old_r // r
           old_r, r = r, old_r - quotient * r
           old_s, s = s, old_s - quotient * s
           old_t, t = t, old_t - quotient * t
   
       return old_r, old_s, old_t
   
   
   

2. inverse_of(n,p): it computes the inverse of mod by relying on the extended_euclidean_algorithm method (refer to Groups and Finite Fields):

   
   def inverse_of(n, p):
       """
       Returns the multiplicative inverse of n modulo p. This function returns an integer m such that (n * m) % p == 1.
       """
       gcd, x, y = extended_euclidean_algorithm(n, p)
       assert (n * x + p * y) % p == gcd
   
       if gcd != 1:
           # Either n is 0, or p is not a prime number.
           raise ValueError(
               '{} has no multiplicative inverse '
               'modulo {}'.format(n, p))
       else:
           return x % p
   
   
   

3. add_points(A, B, p, p1, p2): it adds two points and on the short Weierstrass form elliptic curve whose equation is

   

   
   def add_points(A, B, p, p1, p2):
       if (p1 == "O"): return p2        # "0" denotes the identity element of the group
       elif (p2 == "O"): return p1
   
       else:
           x_p1, y_p1 = p1
           x_p2, y_p2 = p2
   
           if (not ((x_p1 - x_p2) % p) and ((y_p1 - y_p2) % p)): return "O"
           elif (not ((x_p1 - x_p2) % p) and (not ((y_p1 - y_p2) % p)) and (not (y_p1 % p))):
               return "O"
           elif (not ((x_p1 - x_p2) % p) and (not ((y_p1 - y_p2) % p)) and (y_p1 % p)):
               c = ((3*x_p1**2 + A) * inverse_of(2*y_p1, p)) % p
               d = (y_p1 - c*x_p1) % p
               x_p12 = (c**2 - 2*x_p1) % p
               return (x_p12, (-c*x_p12 - d) % p)
           elif ((x_p1 - x_p2) % p):
               c = ((y_p2 - y_p1) * inverse_of(x_p2 - x_p1, p)) % p
               d = ((x_p2 * y_p1 - x_p1 * y_p2) * inverse_of(x_p2 - x_p1, p)) % p
               x_p12 = (c**2 - x_p1 - x_p2) % p
               return (x_p12, (-c*x_p12 - d) % p)
   
   
   

4. mul_scalar(A, B, p, p1, m): it multiplies a scalar by a point on the short Weierstrass form elliptic curve whose equation is

   

   It implementats the double-and-add algorithm previously introduced in the Elliptic Curve Groups post and it relies on the add_points method

   def mul_scalar(A, B, p, p1, m):
       output = "O"
       while m>0:
           if (m & 1): output = add_points(A, B, p, p1, output)
           m >>= 1
           p1 = add_points(A, B, p, p1, p1)                           
       return output;
   
   

5. is_on_ec(A, B, p, p1): it checks if a given point belongs to the elliptic curve group associated with the elliptic curve equation

   def is_on_ec(A, B, p, p1):
       if (p1 == "O"): return True 
   
       x_p1, y_p1 = p1
       return ((y_p1 ** 2)%p == (x_p1**3 + A*x_p1 + B)%p)
   
   

We also saw that bitcoin’s ECDSA uses the secp256k1 elliptic curve. The following python variables specify the parameters of this curve:

• p_dec denotes the decimal value of the order of the underlying finite field.
• G_dec corresponds to the decimal coordinates modulo p_dec of the base point G.
• n_dec is the decimal value of the order of , the subgroup generated by G.
• A_dec and B_dec are the decimal values modulo p_dec of the parameters and appearing in the short-Weierestrass form representation of the elliptic curve:

  

  For secp256k1, A_dec  and B_dec 

  p_dec = long(2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)                         
  
  G_dec = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
           32670510020758816978083085130507043184471273380659243275938904335757337482424)
  
  n_dec = 115792089237316195423570985008687907852837564279074904382605163141518161494337      
  
  A_dec = 0
  B_dec = 7
  
  

The ECDSA algorithm requires us to specify an appropriate hashing function. In the case of bitcoin, we use SHA256. In addition, the algorithm makes use of a truncated version of the hash of the message. These two operations are implemented as follows:

• The method truncate(num, L_n) outputs the integer representation of the least significant bits of the argument num.

  def truncate(num,Ln):
      # Convert to binary format, remove leading 2 characters and
      # extract leftmost Ln bits
      num_bin = bin(num)[2: Ln+2]
      return int(num_bin, 2)
  
  

• The method message_Hash(m) takes a string m, computes its SHA256, and outputs the corresponding integer digest.

  def message_Hash(m):
      # Transform m into byte format
      m_byte = m if isinstance(m, bytes) else bytes(m, 'utf-8')
  
      # Compute digest in hexadecimal format
      digest_hex = hashlib.sha256(m_byte).hexdigest() 
  
      # Compute digest in decimal format
      digest_int = int('0x' + digest_hex, 16) 
  
      return digest_int
  
  

Finally, we implement the three algorithms of the ECDSA scheme:

• ecdsa_Key_Generate() generates a private-public key pair

  def ecdsa_Key_Generate():
      # Generate decimal version of private key d which 
      # is a scalar in the field (F_n)*
      d_flag = False;
      while (d_flag == False):
          # Decimal value of random 256-bit scalar
          d = random.getrandbits(256)
          
          # Test if scalar is in the field (F_n)*       
          d_flag = 0 lt; d lt; n_dec              
      
      # Generate the decimal version of the public key H 
      # associated with the private key d
      H = mul_scalar(A_dec, B_dec, p_dec, G_dec, d)
      
      return (d, H)
  
  

• ecdsa_Sign(d,m) takes private key message and returns signature

  def ecdsa_Sign(d, m):                       
      # The call to the "truncate" method is not really needed 
      # since in this case, message_Hash corresponds to SHA256 
      # which is already 256-bit long
      z = truncate(message_Hash(m),256);      
      r, s = 0, 0;
      while ((r == 0) or (s == 0)):
          
          k_flag = False;
          while (k_flag == False):
              # Decimal value of random 256-bit scalar
              k = random.getrandbits(256)
              
              # Test if scalar is in the field (F_n)*     
              k_flag = 0 lt; d lt; n_dec          
          
          P = mul_scalar(A_dec, B_dec, p_dec, G_dec, k)
          r = P[0] % n_dec
  
          k_inv = inverse_of(k, n_dec);
          s = (k_inv * ((z + (d*r)) % n_dec)) % n_dec;
  
      return (r, s)  
  
  

• ecdsa_Verify(r,s,H,m) checks validity of on message and publick key :

  
  def ecdsa_Verify(r,s,H,m):                                   
      
      # check if the point H is actually on the curve
      if (not(is_on_ec(A_dec,B_dec,p_dec,H))): 
          return False
      
      # Check if r and s are both elements of F_n*
      if ((r lt; 1) and (r gt; n_dec - 1) or (s lt; 1) or (s gt; n_dec - 1)): 
          return False;
      
      z = truncate(message_Hash(m),256);
      s_inv = inverse_of(s, n_dec);
      u = (z * s_inv) % n_dec;
      v = (r * s_inv) % n_dec;
      w_1 = mul_scalar(A_dec, B_dec, p_dec, G_dec, u);
      w_2 = mul_scalar(A_dec, B_dec, p_dec, H, v)
      W = add_points(A_dec, B_dec, p_dec, w_1, w_2)
      
      return (r == (W[0] % n_dec))
  
  
  

• We run an instance of the above algorithms as follows:

  
  (d,H) = ecdsa_Key_Generate();
  print "\n---------------------------   ECDSA KEY PAIR GENERATION   --------------------------"
  print "The generated private key is \n--- d = ", d;
  print "The generated public key is H = (Hx, Hy) where: ";
  print "--- Hx = :", H[0];
  print "--- Hy = :", H[1];
  
  # Sign message
  print "\n---------------------------   ECDSA MESSAGE SIGNATURE    ---------------------------"
  m = "This is a test message";
  print "The signed message is m = '", m, "'";
  (r,s) = ecdsa_Sign(d, m);
  print "The resulting signature tuple (r,s) is given by:";
  print "--- r = ", r;
  print "--- s = ", s;
  
  # Verify signature on message
  print "\n--------------------------- ECDSA SIGNATURE VERIFICATION ---------------------------"
  ver = ecdsa_Verify(r,s,H,m);
  print "(r,s) is a ", ver, "signature on m using public key H";
  
  r_modified = r-1;
  print "r_modified is: ", r_modified;
  
  ver = ecdsa_Verify(r_modified,s,H,m);
  print "(r_modified,s) is a ", ver, "signature on m using public key H";
  
  

ECDSA encoding. In bitcoin, an ECDSA signature is not encoded as a simple concatenation of and Instead, it follows the Distinguished Encoding Rules or DER for short. Those rules are formalized in the Abstract Syntax Notation One standard (ASN.1 for short) commonly used to encode arbitrary data objects into a structured binary file [14]. They allow for data compatibility between systems that may use different representations. However, the merit of using it in bitcoin remains unclear.

When is encoded in DER format, we obtain a sequential structure of the form:

where:

• {hex representation of the byte-length of the signature}: This encapsulates the length of the full encoding to follow. is allocated 1 byte.
• {ASN.1 tag identifier for data of type “SEQUENCE”}: This indicates that the data to follow is a constructed sequence. In ASN.1, the corresponding hexadecimal value is always 0x30. is allocated 1 byte.
• {hex representation of the byte-length of the component}: This encapsulates the length of the component, inclusive of relevant ASN.1 tag identifiers as described hereafter. is allocated 1 byte.
• {ASN.1 tag identifier for data of type “INTEGER”}: This indicates that the data to follow is an integer. In ASN.1, the corresponding hexadecimal value is always 0x02. is allocated 1 byte.
• {hex representation of the byte-length of the component}: This encapsulates the length of the component. is allocated 1 byte.
• {big-endian format hex representation of the value}: This is the actual value of represented in hexadecimal.
• {ASN.1 tag identifier for data of type “INTEGER”}: This indicates that the data to follow is an integer. In ASN.1, the corresponding hexadecimal value is always 0x02. is allocated 1 byte.
• {hex representation of the byte-length of the component}: This encapsulates the length of the component. is allocated 1 byte.
• {big-endian format hex representation of the value}: This is the actual value of represented in hexadecimal.
• {Sighash byte}: A one-byte specifier that we will describe when we discuss bitcoin transactions in another post.

Note that the above structure allows us to automatically deduce that:

• 0x03. The 0x03 corresponds to the 3 bytes allocated to and
• 0x04. The 0x04 corresponds to the total bytes allocated to and
• Theoretically, and can take on any value between 1 and 33 (decimal) or equivalently 0x01 and 0x21 (hexadecimal). However, the most probable values are 32 and 33. To understand why, we first note that and are at most 256-bit long values by definition of bitcoin’s ECDSA. However:
  1. bitcoin’s implementation requires that the most significant bit in the binary representation of and be equal to As a result, if either or have a bit length that is a multiple of 8 i.e., of the form for , then a most significant 0 byte is added. In this case, the size of or becomes equal to bytes instead of bytes.
  2. The probability that either or be 33-byte long corresponds to the probability that either or be 256-bit long originally (i.e., in the notation above). That means that we are interested in the probability of the most significant bit of a 256-bit long sequence be equal to 1. This evaluates to since bits are chosen at random.
  3. The probability that either or be 32-byte long is equal to since it corresponds to the sum of:
     • The probability that the decimal value of the most significant byte of a 256-bit (i.e., 8 byte) long sequence be greater than or equal to 1 but less than 128. This occurs with probability
     • The probability that the most significant byte of a 256-bit (i.e., 8 byte) long sequence be equal to 0 and the first bit of the second most significant byte be equal to 1. This occurs with probability
  4. So the probability that either or be 32 or 33 bytes long is equal to There remains a probability of for the length to be less than 32-byte long. One can calculate the probability of occurence of any of these lengths by following a similar logic to the one just outlined above.

To see an example of how this encoding is conducted in practice, consider an signature given by its decimal representation:

This translates to a big-endian hexadecimal representation given by:

0x

0x

• Since is 32-byte long with a most significant bit of 1, the bitcoin protocol mandates the addition of an extra 0 most significant byte. As such, we get:

  0x (i.e., 33 in decimal)

  0x
  

• On the other hand, is 32-byte long with a most significant bit of 0. We get:

  0x (i.e., 32 in decimal)

  0x
  

• We also have 0x since they specify an integer value.
• The above allows us to compute 0x04 0x
• Assume that 0x01, i.e. the sighash byte is set to 1 (we will introduce sighash when we discuss bitcoin transactions in another post).
• By definition, 0x
• Finally, we calculate 0x03 0x

As a result, the DER-encoding of becomes:

Security of ECDSA: The importance of the randomness of the parameter  A necessary condition for the ECDSA scheme to be secure is for the parameter to be used once per each signature instance. The same logic applied earlier to DSA demonstrates that if this were not the case, one could easily retrieve the private key of the signer. DSA’s derivation can be replicated by replacing with and with

An example that underscores the importance of is the hacking incident that affected Sony in December 2010. At the time, a group known as “fail0verflow” successfully retrieved the ECDSA private key that signed software for PlayStation3. The reason the hackers were able to do so was because Sony misimplemented ECDSA’s algorithm by forcing a static instead of choosing a random one for every signature.

Security of ECDSA: A note on existential unforgeability. There are no known proof of ECDSA’s security in the RO model. This may be surprising, given ECDSA’s usage in bitcoin. Here too, similarly to DSA, the belief that a security proof may be difficult to construct rests on our inability to date to successfully leverage the reduction model.

One can use the same reasoning outlined earlier for DSA to argue why a security proof for ECDSA based on the reduction model may be difficult to devise. The aforementioned logic can be applied in exactly the same way, save for a few nuances surrounding condition C that we describe next. One way of solving for an ECDSA private key is by constructing two distinct signatures and that lead to a linear equation in the unknown Conditions C’ and C below are jointly sufficient for this to be possible:

C’

C

Writing , condition C’ becomes:

Invoking C along with the fact that order we can compute:

.

In what follows, we derive necessary conditions for C’ and C to hold. Since both signatures are assumed to be valid, the verification equations guarantee that:

, for

As a result:

C’

Consequently, and must exhibit a certain relationship for the first condition to hold. With overwhelming probabilty, two randomly chosen parameters and will not satisfy this equality.

Since C’ and since for we can write:

C’ C

Recalling that for we conclude that:

Similarly to DSA, the takeaway is that to be able to effectively use the reduction technique to solve for in the case of ECDSA, one will possibly need to ensure that valid signatures and satisfy the following at a minimum:

1. and
2. or .

Here too, we purposely used the term “possibly”. The remaining part of the argumentation is exactly the same as the one we previously outlined for DSA. We highlight again that out objective was not to argue that a security proof for ECDSA is not possible, but rather that such a proof may be difficult to achieve using the reduction technique.

Despite the absence to date of a security proof for ECDSA in the RO model, slight variants were shown to be secure:

1. The Brickell variant consists of replacing the function that appears in ECDSA’s and algorithms by a random oracle In other words, becomes and the verification algorithm checks if A proof of its security could be constructed in a similar way to the one provided for DSA in [5].
2. The Pointecheval-Vaudenay-Lee-Smart variant also known as ECDSA – II takes the hash of and combined instead of that of alone (i.e., instead of This construct is similar to the DSA variant introduced earlier and we refer the reader to [10] for a proof of its security.

Aside from these variants, Brown [6] and Fersch et al. [8] devised two different security proofs for the unmodified version of ECDSA by introducing extra modeling constraints.

1. In the case of Brown, is not assumed to behave as a random oracle. However, the underlying group is modeled as a generic group. The generic group assumption is a strong one since it was shown in [13] that it implies that ECDSA would be strongly unforgeable (and hence non-malleable), a conclusion that is known not to be valid for ECDSA as we discuss in a subsequent section. We will not go over the details of generic groups or Brown’s model, but refer the interested reader to [6].
2. In the case of Fersch et al., is assumed to be a random oracle. In addition, the authors impose a constraint (similar to the one imposed in their proof for the DSA case), known as the bijective random oracle. This constraint is applied to the conversion function which in the case of ECDSA is defined as:

The conversion function is none else than the one that ECDSA’s algorithm uses to calculate with elliptic curve point as input. The constraint that Fersch et al. impose consists of representing as a composition of three functions such that is a bijection and such that both and are modeled as random oracles. We will not go over the details of their proof, but the interested reader can refer to [8].

Security of ECDSA: Signature’s malleability. Once a signature has been issued on a given message it is reasonable to require that no adversary be able to devise another valid signature on the same message. A signature is said to be malleable if it is not subjected to the aforementioned requirement. As a result, signature malleability could potentially lead to an instance of forgery, albeit in a restrictive sense since the message is taken to be the same. On the other hand, signatures that are simulteneously not malleable and existentially unforgeable (i.e., resilient against EFACM) are referred to as strongly unforgeable [4].

Signature malleability leads to transaction malleability, a notion that we will discuss in a separate post dedicated to bitcoin transactions. For the purpose of our current discussion, it suffices to highlight that a bitcoin transaction is a data structure that encompasses four main categories of information:

1. Source(s) of funds to be transfered, also known as unspent transaction output(s) or UTXO(s).
2. Destination(s) of the funds (i.e., the intended recipient(s) addresse(s)).
3. Exact amount to be sent to each destination address.
4. Information containing the DER-encoded ECDSA signature(s) on the relevant UTXO(s).

Transactions are represented in a serialized byte format that we discuss in more detail in the bitcoin transactions post. The raw serialization is subjected to a double SHA-256 operation that outputs a hexadecimal digest known as the transaction id or txid for short. Any alteration to the body of the transaction, no matter how small, results in a different txid. This is a direct consequence of the expected behavior of a hashing function.

The critical observation is that although a signature is part of the body of the transaction, it is logically infeasible to sign a data structure inclusive of the resulting signature itself. Instead, the signing process is applied to the content of the transaction exclusive of the signature. More specifically, the message that gets signed includes information about the funding UTXOs, the destination addresses and their respective intented amounts.

By definition, a malleable signature scheme could lead to the creation of two valid but different signatures applied to the same transaction. Such an event would cause the bitcoin network to end up with at least two different txids referencing the same content. Such a situation could motivate a specific type of attack known as a malleability attack. The gist of it is as follows:

1. Suppose Alice issues a BTC payment to Bob. Let be its transaction id.
2. Suppose that Bob alters the signature of Alice’s transaction (assuming it is a malleable scheme) right before gets any confirmation on the blockchain. This alteration results in a new transaction id, namely on the same content (i.e., the intended recipient is still Bob, the funding UTXOs are still the same, and the amount remains as is).
3. If gets confirmed on the blockchain before , the latter will become orphaned. If Alice does not have the required level of sophistication to track UTXOs on the blockchain in order to verify that her original UTXOs have been spent, it will rely instead on the confirmation status of Given that it was orphaned, it will conclude that the funds never reached Bob’s address.
4. Bob could then defraud her by asking her to issue a new payment knowing that he would have already received the intended funds by virtue of being confirmed. He would then receive twice the intended amount.

The above malleability attack can be interpreted as an instance of double-spending, although the malicious party in this case is the receiver and not the sender.

It turns out that ECDSA is malleable. In what follows, we describe three possible avenues to change it without modifying relevant content in the transaction. We highlight that the first two avenues could be exploited by any party including e.g., the recipient of a given transaction. As a result, they are conducive to malleability attacks. On the other hand, the third avenue is specific to the holder of the private key. If the sender is the only holder of the key, one can reasonably assume that no malleability attacks would ensue. We point out that bitcoin has already implemented measures to prevent the first two avenues from being nefariously exploited:

1. Malleability caused by Non-DER encoded ECDSA signatures: We described earlier how to encode an ECDSA signature into DER format. Given an pair, one can see that by diligently applying the DER encoding procedure, the resulting output will be unique. In particular, a strict implementation of DER would not allow prepending any number of 0 bytes to the octet representation of integers. The only exception occurs if the most significant bit of this octet representation is equal to 1, in which case we prepend a single 0 byte. For example:
   • An value of 0x cannot be encoded as e.g., 0x
   • An value of 0x must be encoded as 0x (since the most significant bit is equal to 1), but cannot be encoded as e.g., 0x

   However, bitcoin’s original implementation did not strictly enforce this rule. As a result, one could derive an infinite number of encodings for a given pair. This source of signature malleability has been addressed in Bitcoin Improvement Protocol 66 (BIP 66) [15].

2. Malleability caused by ECDSA’s inherent signature construct: Given an ECDSA signature one can automatically devise another valid signature on by replacing with where is the order of In other terms, is a valid signature on To see why, recall that satisfies the verification algorithm which consists of the following steps:
   • Compute
   • Calculate
   • Compute
   • Validate that

   On the other hand, running the verification algorithm on will:

   • Compute
   • Calculate
   • Compute
   • Check if

   Let We get the following implications:

   

   

   

   As a result, we rewrite ‘s verification steps as follows:

   • Compute
   • Computing
   • Computing Recall that as was introduced in the Elliptic Curve Group post, the inverse of the elliptic curve point is And so
   • Since is a valid signature, we have In light of the previous equality, we deduce that and as a result, that is also a valid signature on

   This type of signature malleability was supposed to be addressed in BIP62, but had to wait until Pull Request #6769 [1] to be resolved. The mitigation mechanism consisted of requiring that only the signature with the lowest value be valid.

3. Malleability caused by ECDSA’s reliance on the random parameter : The third source of signature malleability is a direct result of the presence of the parameter in the signing algorithm A signer could decide to sign the message as many times as she likes, and the randomly generated parameter will ensure that these signatures are different. However, as mentioned earlier, this source of malleability does not lend itself to attacks of the type previously described.

ECDSA multisignatures. So far, our discussion of ECDSA signatures was limited to single signers. It turns out that more elaborate signatures could be constructed. In particular, we could have private keys jointltly sign a transaction in what is commonly known as a multisignature. An important observation is that the implementation of multisignatures in bitcoin consists of creating a separate signature for each private key and then grouping these signatures together. This construct results in at least three disadvantages:

1. Size inefficiency: The multisignatures size grows linearly with the number of signers. A direct impact is that multisignatures will occupy a bigger portion of a block on the blockchain. And since block issuance is kept constant at 1 block per 10 minutes, this results in a lower transaction throughput and slower processing.
2. Higher cost: Transaction fees in bitcoin are calculated on a kilobyte basis. This implies that larger transaction sizes will cost more. As a result, multisignatures are more costly than monosignatures.
3. Less privacy: In order to verify the validity of an ECDSA multisignature, the network must have access to the set of the public keys of the signers. Making the public key set known will signal that the transaction is of a multisignature type and could draw unecessary attention from potential attackers. Ideally, one would want to keep private the multisignature nature of a given transaction.

In conclusion, we note that despite the ECC-inherited security features of ECDSA, the signature scheme is not fully immune to drawbacks including:

1. An absence to-date of a proof of ECDSA’s security in the RO model. For some, this may be a non-issue, but others would prefer to use a scheme that is at least provably secure in this idealized setting.
2. An inherent malleability buit in ECDSA signatures.
3. A size-inefficient, more costly and less private implementation of multisignatures.

In light of these shortcomings, a new BIP advocating the adoption of a different signature scheme has been put forth. It turns out that similar to the Schnorr scheme, a variant of it known as Elliptic Curve Schnorr [16] is provably secure and non-malleable in the RO model. Moreover, this variant benefits from the linearity property that allows multiple private key holders to jointly sign a transaction such that the resulting signature is not a naive concatenation of individual signatures, but rather a non-trivial aggregation that reduces to a monosignature. We will discuss multisignatures and explain the advantages of the Elliptic Curve Schnorr variant in a separate post.

4. References

[1] Pull request 6769 – Script Verify Low s, 2015.

[2] Anonymous. Rebutal to Schnorr’s patent claims re DSA, August 1998.

[3] Elaine Barker. Recommendation for key management part 1. NIST Special Publication 800-57 Part 1 Revision 4, January 2016.

[4] D. Boneh, E. Shen, and B. Waters. Strongly unforgeable signatures based on computational Diffie-Hellman. PKC LNCS, 3958:229-240, 2006.

[5] Ernest Brickell, David Pointcheval, Serge Vaudenay, and Moti Yung. Design validations for discrete logarithm based signature schemes. Public Key Cryptography. PKC 2000. Lecture Notes in Computer Science, 1751, 2000.

[6] Daniel R.L. Brown. The exact security of ECDSA. Technical Report CORR 2000-34 Certicom Research, 2000.

[7] Andrea Corbellini. Elliptic curve cryptography, a gentle introduction, 2015.

[8] Manuel Fersch, Eike Kiltz, and Bertram Poettering. On the provable security of (EC)DSA signatures. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1651-1662, October 2016.

[9] David W. Kravitz. Digital Signature Algorithm patent, 1991.

[10] John Malone-Lee and Nigel P. Smart. Modifications of ECDSA. Selected Areas in Cryptography|SAC, 2595:1-12, 2003.

[11] David Pointcheval and Serge Vaudenay. On provable security for digital signature algorithms. 11 1996.

[12] Claus P. Schnorr. Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system, 1989.

[13] J. Stern, D. Pointcheval, J. Malone-Lee, and N.P. Smart. Flaws in applying proof methodologies to signature schemes. CRYPTO, pages 93-110, 2002.

[14] International Telecommunication Union. Itu-t x.690, July 2002.

[15] Pieter Wuille. BIP66 – Strict DER signatures, 2015.

[16] Pieter Wuille. Proposed BIP for 64-byte Elliptic Curve Schnorr signatures, July 2018.