Magnitude-Nine Politics

StateTectonics

After an earthquake, people climb out from under their protective tables and doorways, look around, and try to make sense of the distorted landscape. After the political tectonics of 2016, Brexit and Trump, people did the same – a mood captured by P.J. O’Rourke in the title of his 2016 election memoir, How the Hell Did This Happen?

It wasn’t just in Britain and the U.S. that the ground moved. Across Europe nationalist parties have come to prominence, gaining power in Hungary and Poland. In France, the nationalists didn’t win but were defeated by Emmanuel Macron, whose En Marche party was only a year old. In Iceland, the Pirate Party, a five-year-old group whose symbol is a skull and crossbones flag, has fired a shot across the bow of the political establishment.

Prior to all of this, the Arab Spring toppled governments or ignited civil war in Tunisia, Libya, Egypt, Syria, and Yemen.

Companies, churches, and empires are the solid rocks that society is built on. These solid institutional rocks are floating on a swirling fluid magma of technology.

Different technologies support different institutions. The feudal church supported by swords and scriptoria is very different from the nation state supported by gunpowder and the printing press. Sailing ships support different-shaped empires than railway lines.

The technology layer is fluid, elastic, and constantly shifting. The institutions it supports are heavy, solid, and, ultimately, brittle. Institutions can be built on what look like solid foundations, but those foundations move and can tear apart the very thing they’re supposed to hold up.

In the 1850s telegraph wires bound the British Empire together. During the Indian Rebellion in 1857 the telegraph enabled British troops to communicate better than the rebels and suppress the mutiny. Fifty years later, rapid telegraphic communications enabled the cascade of events that triggered World War I, that unprecedented bonfire of empires.

Gunpowder enabled the formation of large armies of untrained men and hence large states. Gunpowder morphed into high explosives and then into nuclear weapons. States became empires became superpowers. The superpowers’ most powerful weapons are too dangerous to use – nuclear weapons haven’t been used since Nagasaki in 1945 but explosives in the form of Stinger missiles and car bombs or IEDs are now the weapon on choice against superpowers.

Those of us who live on top of geological fault lines have a visceral understanding of plate tectonics. Those of us who live amongst institutions whose technological foundations have moved will become familiar with state tectonics.

Several magmatic currents are tearing at the foundations of our social order. We are living on top of a complex fracture zone.

Social media has democratised propaganda. Where broadcast media once consolidated opinion and allowed the manufacture of consent, social media fragments opinion and enables strife. An Egyptian president of thirty years can be deposed by a hashtag. Fifty gigatons of Soviet warheads did nothing to lessen American power but $200-worth of Russian Facebook ads caused riots in American streets.

The printing press made us all readers, ended five centuries of feudalism, and gave birth to the modern age. Social media makes us all writers, persuaders, and propagandists and will upend the “broad church” political parties that have been at the centre of modern democracy.

Cyberwarfare has given the power to destroy infrastructure to anyone who can download a piece of code. The Wannacry ransomware worm brought British hospitals to their knees. The sort of havoc that used to require an air force is now available to anyone who can Google “EternalBlue”.

Information technology can either give us the tools to distribute and decentralise the electrical grid and make it highly resilient or provide the tools to cut off the lifeblood of civilisation.

Cryptocurrencies threaten the monopoly that governments have on issuing money. Taxation depends on knowing who earns what. Governments balance their books by expanding the supply of paper money. If either of these abilities disappears, everything we know about modern welfare states is up for grabs.

Bitcoin may or not be around in ten years but, either way, money printing and government debt is going to cause a crisis that will change money forever. Whether we end up with gold, IMF Special Drawing Rights, or a novel electronic currency is still to be decided but the existing order won’t last.

Machine learning, 3D printing, and robotics make it possible to manufacture all manner of goods with almost no staff. Where factories used to provide thousands of solid jobs, capital is often now cheaper than labour.

The Luddites tried to reverse the first industrial revolution by smashing weaving looms. History shows that the Luddites were wrong and that the industrial revolution created far more jobs and wealth than it cost. Automation and artificial intelligence will create even vastly more wealth but what will our relationship with the machines look like?

Quakes caused by any of these rifts could be dramatic. Together they’ll reshape the societal landscape like nothing we’ve ever seen and the results are unknowable.

MedievalTech.png

Five hundred years ago, similar forces reshaped Europe in the Reformation. Gunpowder and the printing press reduced city walls to rubble and ended the Church’s monopoly on Biblical interpretation. Both books and firearms were used in service of the Church but the changes they brought about inevitably swept feudalism away. Luther believed he was returning the Church to its origins but unwittingly launched Europe on the path to science and democracy, to secular humanism, via the catastrophe of the Thirty Years’ War.

ModernTech.png

The new reformation that we’re embarking on will have equally unknowable results. The question is: how can we survive and prosper through it?

FutureTech.png

BTC#: Digital Signatures

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: The Bitcoin Curve

Next: Digital Signature Code »

CryptographyBasicsTitle

Your digital identity is a private key, a secret number than only you know. It’s a bit like a PIN on your credit card but much, much longer. One of the major security flaws with credit cards is that you need to reveal your secret to authorise your spending.

CreditCardAliceBobEve.png

Digital signatures prove that you know a secret without revealing the secret. Only a person in possession of the secret can produce a particular digital signature and the signature can’t be produced without knowing the secret. In other words, a signature authenticates a message and its origin can’t be denied.

A digital signature also incorporates details of the message that was signed, so the message can’t be tampered with without invalidating the signature.

How Signatures Work

A signature is built up from the signatory’s private key, a hash of the document being signed, and an ephemeral key that is used for a single message. Of these, only the document hash is publicly known. The other two are protected by an irreversible elliptic curve multiplication. The signature is made up of two components, r and s.

SignatureDataFlow.png

To verify that a signature is valid, the receiver needs the signature, the document hash, and the signatory’s public key. The signature’s r-component is derived from the ephemeral key and the s-component is composed in such a way that we can confirm that it was created using the document hash and the two secrets, without exposing either of the secrets.

The verification algorithm is an equation in which all the parts cancel out if the correct document hash and public key are provided. If the signature was created using a different private key than the one used to create the public key, the equation doesn’t balance, meaning the signature is not authentic. If the signature was created using a different document hash, the equation doesn’t balance, meaning that the document has been tampered with.

SignatureEquation.png

Programming Bitcoin provides a baffling analogical explanation of digital signature verification involving William Tell, inscriptions on arrow heads, and x-ray machines, which can be skipped, but do go through the equations and their derivations. If you want to go direct to the source, it’s NIST’s Digital Signature Standard.

« Previous: The Bitcoin Curve

Next: Digital Signature Code »

BTC#: The Bitcoin Curve

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: BTC#: Elliptic Curves over Finite Fields

Next: BTC#: Digital Signatures »

The trick to breaking elliptic curve cryptography is reversing scalar multiplication of points on the curve. When we’ve got curves defined over small finite fields it’s easy: just work out the complete set of multiples (the members of the finite cyclic group) and look up the answer.

That’s why the prime used to define the finite field, and therefore the number of elements in the group, is mindbogglingly big.

The parameters of the secp256k1 curve used by Bitcoin are on the Bitoin Wiki.

EllipticCurveReal

I’ve copied those into a static Secp256k1 class. (There is a post on big integers in C# to jog your memory.)

public static class Secp256k1
    {
        // Highest order bit parsed as sign, so lead with 00.
        public static BigInteger P { get; } = BigInteger.Parse("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.AllowHexSpecifier);

        public static BigInteger A = BigInteger.Zero;

        public static BigInteger B = new BigInteger(7);

        public static BigInteger Gx { get; } = BigInteger.Parse("0079BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", NumberStyles.AllowHexSpecifier);

        public static BigInteger Gy { get; } = BigInteger.Parse("00483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", NumberStyles.AllowHexSpecifier);

        public static BigInteger N { get; } = BigInteger.Parse("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", NumberStyles.AllowHexSpecifier);
    }

I’ve also added a couple of extra constants to that class. These use the coefficients A and B and the prime P to create a curve object and the generator point coordinates Gx and Gy to create a generator point object.

public static EllipticCurveOverFiniteField Curve { get; } = new EllipticCurveOverFiniteField(A, B, P);

public static EllipticCurveFiniteFieldPoint G = Curve.GetPoint(Gx, Gy);

A couple of unit tests make sure that everything is defined properly.

[TestMethod]
public void Curve_GeneratorPointIsOnCurve()
{
    Assert.IsTrue(Secp256k1.Curve.PointIsOnCurve(Secp256k1.Gx, Secp256k1.Gy));
}

[TestMethod]
public void GeneratorPointHasOrderN()
{
    Assert.IsTrue((Secp256k1.N * Secp256k1.G).AtInfinity);
}

Note that the multiplication N x G, which checks the order of the generator point, would take vastly longer than the age of the universe to calculate by repeated addition but takes milliseconds when done by binary expansion.

This approach is slightly different to the one taken in the book, so compare them and use whichever you prefer.

« Previous: BTC#: Elliptic Curves over Finite Fields

Next: BTC#: Digital Signatures »

BTC#: Elliptic Curves over Finite Fields

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Elliptic Curve Point Addition

Next: The Bitcoin Curve »

Coding for elliptic curves over finite fields is the target of our work so far. In Programming Bitcoin, Song just passes FieldElement objects into Point’s constructor and lets the Python interpreter’s type inference do the rest. The mathematical code in the Point class just calls the operator functions defined on FieldElement instead of the integer versions.

In the strictly typed world of C#, we don’t get that luxury. There’s no interface or other generic type constraint common to our FiniteFieldElement and Int32, so I’ve written a new class, EllipticCurveFiniteFieldPoint. (Get the repo.)

Continue reading “BTC#: Elliptic Curves over Finite Fields”

BTC#: Elliptic Curve Point Addition

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: BTC#: Elliptic Curves

Next: Elliptic Curves over Finite Fields »

Point Addition

The elliptic curve points we’ve modelled with the code in the previous post represent points (x, y) on the curve. Adding points together is going to form the basis of our elliptic curve cryptography maths. However, elliptic curve point addition is not a lot like the vector addition you’ve seen elsewhere. We don’t just add the xs and ys.

Elliptic curve point addition is an operation on two point that results in a third. However, it doesn’t work the way you might intuitively think. We don’t just add the xs and ys. There are various rules for point addition depending on the relationship of the two points to be added.

PointAddition.png

The meaning of each of these cases is covered in the book.

The Point At Infinity

In the previous post where I created the EllipticCurvePoint class, I said that I’d made the y parameter nullable. This is to model the idea of “the point at infinity”. A vertical line intersecting the curve twice is regarded as also passing through the point at infinity.

public bool AtInfinity
{
    get { return !Y.HasValue; }
}

The point at infinity act as the identity in point addition, meaning that any point plus the point at infinity results in itself

A + I = A

and that any point added to its inverse, i.e. any point minus itself, results in the point at infinity

A + (-A) = I

This gives us the first couple of cases to model for our addition operator.

public static EllipticCurvePoint operator +(EllipticCurvePoint p1, EllipticCurvePoint p2)
{
    //At least one of the points is at infinity
    //This is the identity operation for addition so return the other point.
    if (p1.AtInfinity) return p2;
    if (p2.AtInfinity) return p1;

    //Same x, different y (or same y and tangent is vertical),
    //meaning that the line is vertical.
    //Return the point at infinity.
    if ((p1.X == p2.X && p1.Y != p2.Y) || (p1 == p2 && p1.TangentIsVertical))
    {
        return new EllipticCurvePoint(p1.X, null, p1.A, p1.B);
    }

    //More code here later...
}

Remaining Cases

There are two situations left that we need to handle, the addition of two points with different xs, and the addition of a point to itself. In the first case we need to find the line between the two points and find where else it intersects the curve, as in graph 1 above. In the second case we need to find the tangent to the point and see where that line intersects the curve, as in graph 2.

The derivation of the formulae for finding the gradients of these lines and, from there, where they intersect with the curve is somewhat involved and covered in detail in the book.

It’s worth reading through the explanations in the book, because repeated point addition on the bitcoin elliptic curve will be used later, in the cryptography section, to generate signatures.

With the formulae derived we can implement the rest of the addition operator.

public static EllipticCurvePoint operator +(EllipticCurvePoint p1, EllipticCurvePoint p2)
{
    //Previous code in here.

    //Where p1 coincides with p2, find the slope of the tangent.
    //Otherwise find the slope of the line between the points
    var slope = (p1 == p2)
        ? p1.SlopeOfTangent
        : (decimal)(p2.Y.Value - p1.Y.Value) / (p2.X - p1.X);
    var x3 = slope * slope - p1.X - p2.X;
    var y3 = slope * (p1.X - x3) - p1.Y.Value;

    return new EllipticCurvePoint((int)x3, (int)y3, p1.A, p1.B);
}

There are tests to cover each scenario.

[TestMethod]
public void operatorAddition_twoPointsReturnTheThird()
{
    var a = new EllipticCurvePoint(2, 5, 5, 7);
    var b = new EllipticCurvePoint(-1, -1, 5, 7);
    var c = new EllipticCurvePoint(3, -7, 5, 7);

    Assert.AreEqual(c, a + b);
}

Of course, as good TDD practitioners, the tests were written first.

Next time, I’ll combine the FiniteFieldElement with the elliptic curve code.

« Previous: BTC#: Elliptic Curves

Next: Elliptic Curves over Finite Fields »