‘Why is My Bitcoin Transaction Taking So Long?’ Here’s Why My Bitcoin wallet has recently taken longer and longer to receive a Bitcoin payment. This wasn’t happening 2-3 months ago. Maybe you haven’t noticed it, but I know I have. My Bitcoin wallet has recently taken longer and longer to receive a Bitcoin payment, have […]
The mathematics behind blockchain
In a previous Math Investor blog, we described the emerging world of blockchain, emphasizing how it might influence the financial services and investment world. Already numerous firms, including several startup organizations, are pursuing blockchain to facilitate and streamline many types of financial transactions.
It is worth taking a brief look at the mathematics behind blockchain. The following is based in part on an article by Eric Rykwalder, one of the founders of Chain.com, a startup blockchain software rock hard in San Francisco.
The elliptic curve digital signature algorithm
Blockchain is basically a publicly available ledger where participants come in data and certify their acceptance of the transaction via an elliptic curve digital signature algorithm (ECDSA). An elliptic curve is an equation such as y two = x three + a x + b. In Bitcoin and most other implementations, a = zero and b = 7, so this is simply y two = x three + seven (see graph). Elliptic forms have numerous interesting properties, such as the fact that a nonvertical line intersecting two nontangent points will always intersect a third point on the curve. Indeed, one can define “addition” on the curve as finding that third point corresponding to two given points. This is basically what is done in ECDSA, except that the operations are performed modulo some large prime number M.
In particular, in ECDSA, addition of two points (p1,p2) and (q1,q2), and the doubling of (p1,p2), are performed as goes after:
Addition of (p1,p2) and (q1,q2):
Doubling of (p1,p2):
c = (Three p1 two ) / (Two p2) mod M
Some readers will note that “division” is indicated in the very first line of each algorithm. What this means is the product, modulo M, of the expression to the left of the slash by the multiplicative inverse of the expression to the right of the slash. Since M is a prime, every nonzero integer from one to M-1 has a multiplicative inverse. For example, the multiplicative inverse of five mod seventeen is 7, because Five*7 = thirty five = one mod 17; in other words, five -1 mod seventeen = 7. In practice, these inverses are rapidly calculated by means of the Euclidean algorithm, where one accumulates the divisors in a particular way. See a note by Nick Korevaar for some examples.
One other preliminary detail is how to “multiply” in this algebraic structure, in particular to calculate an expression such as m * (p1,p2) for some integer m. This can be done by very first doubling the input (p1,p2), and then using the addition algorithm repeatedly until m copies of (p1,p2) have been added, but this of course is not practical when m and M are very large, as they are in real blockchain applications. Instead, such “multiply” operations are typically done using the binary algorithm for multiplication, which we will sketch here for ordinary integers but which can be lightly adapted to ECDSA:
To compute r = n * b mod M: Very first set t to be the largest power of two such that t is less than or equal to n, and set r = 1. Then perform:
A: If n is greater than or equal to t, set r = b + r mod M, and set n = n – t; else set t = t / Two.
B: If t is greater than or equal to one set r = two * r mod M, and go to A (if t seventeen mod ten = ((((Trio two mod Ten) two mod Ten) two mod Ten) two mod Ten) * three mod ten = Trio, thus performing the exponentiation in only five multiplications mod ten instead of sixteen or 17.
Now we may state the ECDSA algorithm (except that we omit some relatively minor details that apply mainly to real-world implementations):
Very first, select a modulus M, a “base point” (p1,p2), and a private key k1 (integer inbetween one and M-1). These are typically selected such that the order of the base point (namely the maximum number of times (p1,p2) can be added to itself before the addition formula above fails due to zero divide) is prime and at least as large as M (this is not required but is normally done, and with this assumption the algorithm below is simpler). This often takes some experimentation, albeit practical applications can do this very rapidly.
As a concrete example, let us take M = one hundred ninety nine (which is prime), and the base point (p1,p2) = (Two,24). For this M and (p1,p2), one can calculate that the order n = 211. Then let us select as our private key k1 = 151. We very first need to calculate the public key (r1,r2) corresponding to the private key. This is done by multiplication:
where again the multiplication is done either by repeated summation or by the binary algorithm above. If we do this, we find that the public key (r1,r2) = (64,80).
Now select some data z1, say z1 = 104. We shall construct a digital signature of the data. This is done as goes after:
1. Choose some integer k2 inbetween one and n-1, where n is the order.
Two. Calculate (s1,s2) = k2 * (p1,p2). If s1 = 0, come back to step 1.
Three. Calculate s2 = (z1 + s1 * k1) / k2 mod n. If s2 = 0, come back to step 1.
Then the digital signature is (s1,s2). In our specific case, if we select k2 = 115, we calculate (s1,s2) = (99,52).
Now we can test the digital signature, as a third party might to verify that the transaction (which in this example we presume is coded in the data z1 = 104) is valid. This is done as goes after:
1. Calculate u1 = s2 -1 mod n
Two. Calculate u2 = z1 * u1 mod n
Three. Calculate u3 = s1 * u1 mod n
Four. Calculate (t1,t2) = u2 * (p1,p2) + u3 * (r1,r2)
Five. Verify that t1 = s1.
In our case, we find that the result of step four is (t1,t2) = (99,44). Since t1 = ninety nine = s1 (see above), the validity of the signature is confirmed (it is not necessary for t2 to equal s2).
We should emphasize that our example involves enormously modest-sized integers. In a real Bitcoin or blockchain application, these integers are typically two hundred fifty six bits long, dramatically enlargening the cost of performing the above operations, but, on the other arm, very dramatically enlargening the cost required for someone to “break” the system, such as by computationally attempting to recover the private key from the public key.
So what conclusions can we draw from this exercise? Very first of all, it should be clear that the mathematics involved is not trivial, and the necessary computations to implement this scheme certainly are not trivial. Nonetheless what we have is an effective one-way function: it is relatively effortless to verify a signature, but it is very difficult to work back from publicly available data, such as the public key, to obtain the critical private key.
ECDSA is the essence of how both Bitcoin and other blockchain applications work. The scheme has resisted some rather extensive testing for weaknesses, both mathematically and computationally. The few failures that have occurred in practice have generally been because users were not careful in protecting their private keys, or else they used a fairly standard pseudorandom number generator to produce the private keys, which attackers then exploited.
As with all the technology we rely on in our digital age, the weakest links are users who are not careful.