As discussed in a previous post, one important factor of any digital currency is the ability of a holder of the asset to prove ownership. Specifically, if they want to make a payment by transferring the asset to another party, they need to submit a transaction to the network and be able to prove that this transaction has indeed been authorised by them. It should not be possible for a third party to be able to create any such authorised transactions involving the same holding, otherwise anyone would easily be able to steal the money. This is achieved with digital signatures implemented by public-key cryptography.
To explain this, let us start with a prospective holder of the cryptocurrency, called Alice. The first thing that she needs to do is to create key pair. This consists of a private (or, secret) key sk and a public key PK. The process of creating these keys depends on the signature algorithm being employed, but for the elliptic curve crytography (ECC) used by Bitcoin, for example, the private key is a random 256 bit number, and the public key is another number (of possibly varying length) derived from this.
As the name suggests, Alice needs to keep her private key sk secret. If anyone was to obtain it then they would be able to make transactions on her behalf, and steal her money. On the other hand, if she was to lose it, then she would no longer be able to sign transactions and would effectively lose her holdings of the digital asset. It is also for the reasons of security that the initial creation of the private key is random otherwise, if people know how it is constructed, then they would be able to recreate her key. It turns out that guessing a random 256 bit number is an effectively impossible task. It is difficult to emphasise quite how hard this is, even making quadrillions of guesses every nanosecond over the entire current age of the universe would give a vanishingly small probability of ever guessing correctly. For all realistic purposes, it is impossible. On the other hand, Alice’s public key PK can be shared freely.
Once this is done, Alice is able to digitally sign any message to prove that it has been authorised by her. In this context, the message is simply a block of digital data (a sequence of bits). Alice uses the message and the private key in the signature algorithm to generate the signature, which is another sequence of bits. For the ECDSA (Elliptic Curve Digital Signature Algorithm) used by Bitcoin, the signature is another string of bits, of variable length. The original message together with the signature can be shared publicly. Any third party in possession of Alice’s public key can then take the signed message and, by a verification algorithm, confirm that it has indeed been authorised by Alice. At least, he can verify that it has been signed by someone in possession of Alice’s private key. This is demonstrated in figure 1, where the third party ‘Bob’ wants to check the validity of the signed message.
As shown in the figure, the signing procedure performed by Alice requires the message and the private key in order to generate the signature, which is distributed along with the original message. You may notice that I included an additional input in parantheses to the signing process — the nonce. This is just an additional number required by some signature algorithms, usually chosen at random for security. It can be generated on the fly and thrown away after use, so is not distributed or kept hold of by Alice. It is really just an internal part of the signing process.
Any third party such as Bob can take the signed message along with the public key and apply the verification algorithm. This either gives True, verifying that the message was indeed signed by someone in possession of Alice’s private key. Or, it can return False, in which case the signature is invalid.
In summary then, digital signature methods enabling Alice to authorise messages involve three separate procedures.
- Generation of the public/private key pair, which must be performed by Alice since only she should have knowledge of the private key.
- Signing a message, which can only be done by Alice since it requires knowledge of the private key.
- Verification of the signed message, which can be performed by anyone in possession of the public key.
The important feature of this entire algorithm is that only someone in possession of Alice’s private key should be able to generate valid signatures. If not, the whole idea would be useless. From a logical standpoint though, anyone can generate valid signatures in theory, using a brute force attack. All that you need to do is to count through every possible signature string in turn, applying the verification algorithm, until you find one that is valid. In practice, signature strings are long and apparently random sequences of bits, meaning that there is a huge number of possibilities to check. Much like trying to guess a private key, the search space is so big that even with an infeasibly large amount of computing power and the entire age of the universe to perform the search, the chance of finding a valid signature is so small as to be effectively impossible. Signature algorithms are chosen so that finding a valid signature from a given message and public key is a hard problem. That is, although it is theoretically possible using brute force, there is no known method of doing this with any available amount of computing power.
Let’s get back to the application of all this to solving the ownership issue for cryptocurrencies. Recall that Alice is a prospective owner of the asset, and has generated a key pair. Suppose she purchases some of the asset from another party — Charlie, let’s say. She needs to provide her public key to Charlie so that he can create a transaction paying the correct quantity of the asset to an ‘address’ corresponding to this key. This transaction containing the public key will be added to the ledger (or blockchain). When Alice is ready to spend her coins, she creates a transaction with the input containing a digital signature. This signature is created as described above, using Alice’s transaction as the message and using her private key. Anyone can verify that this is a valid transaction, by applying the verify procedure to Alice’s transaction using the signature contained in the input and the public key in Charlie’s output. Since only Alice can create a valid signature for the given public key, only she is able to create valid transactions spending her coins.
Such digital signatures are used by Bitcoin although, for more flexibility, it is not simply a matter of including public keys and signatures in the transaction inputs and outputs. Rather, they include some computer code in a very simple programming language developed for this purpose known as Script, which contains special keywords for the verification part of the signature algorithm. Then, Charlie’s transaction contains a script referred to as scriptPubKey in the output corresponding to the coins paid to Alice. This will perform the verification part of the signature process, so contains Alice’s public key together with the verify function. When Alice wants to spend the coins, her transaction also contains a script, referred to as scriptSig, which contains the signature. Running scriptSig followed by scriptPubKey will push the signature and the public key onto the stack, and the verify function will check that the signature is valid for Alice’s transaction. In practice, a bitcoin address is just a representation of a scriptPubKey script which should be used for paying bitcoin to you. There are various standard scriptPubKey formats in use, corresponding to different types of bitcoin addresses. For example, for some additional security, P2PKH (Pay to PubKey Hash) contains a hash of the public key, rather than the key itself. For such addresses, Alice’s scriptSig used to spend the coins must contain the public key as well as the signature, and the scriptPubKey checks that the provided public key has the correct hash before applying the verify function. The use of Script rather than having a hardcoded signature process allows for further types of bitcoin addresses, such as multisig ones requiring more than one signature in order to spend the coins.
For cryptocurrency payments, digital signatures are used as described above to ensure that valid transactions spending any coins can only be created by the holder. However, signatures can be used for signing any message, not just transactions. For example, it is possible to prove that you are the owner of any particular bitcoin address without actually generating a transaction, by using the private key to sign a message. Although this is not commonly done, here is one interesting and slightly controversial example. The tech entrepreneur Craig Wright once provided a list of bitcoin addresses for a court case claiming that they were his, which were inadvertently made public in May 2020. However, the holder of the private keys of some of these addresses signed the following message.
Craig Steven Wright is a liar and a fraud. He doesn’t have the keys used to sign this message. The Lightning Network is a significant achievement. However, we need to continue work on improving on-chain capacity. Unfortunately, the solution is not to just change a constant in the code or to allow powerful participants to force out others. We are all Satoshi.
As it seems unlikely that Craig Wright would sign such a message himself, this at the very least demonstrates that someone other than him was in possession of those private keys.
Zero Knowledge 