Ace Addresses And Signatures With Bitcoin

Co-authors

Zainab Hasan
Shakeib Shaida

Share

Share on facebook
Share on linkedin
Share on twitter
Share on telegram
Share on pocket
Bitcoin

Contents

Introduction

We have already discussed the architectural working of Bitcoin in our previous publication. This Publication mostly discusses the security aspect of Bitcoin Blockchain. In Bitcoin network, the security works around keys and addresses. To understand the concept, consider assets are people. To reside on Blockchain You need an account which can be referenced via addresses.  Now you being the owner have the power to lock, unlock and transfer the ownership of your assets to other accounts. For the above mentioned purposes the keys and addresses are used.

Let’s discuss keys and addresses in detail.

Keys And Addresses With Bitcoin

Bitcoin ensures ownership through digital keys, bitcoin addresses, and digital signatures. 

The digital keys are managed by the user’s wallet and are completely independent of the bitcoin protocol. The digital keys inherit multiple properties of bitcoin, including decentralized trust, ownership control, and the cryptographic-proof security model.

To understand the logic behind the cryptography of digital keys, we first introduce the mathematics used in bitcoin. Next, we will understand how keys are generated, stored, and managed. We will also review the different encoding formats of digital keys, addresses, and script addresses. Finally, at the end of this section, we will learn about vanity, multi-signature, script addresses, and paper wallets.

Asymmetric Cryptography 

Bitcoin utilizes asymmetric cryptography to form a key pair that controls access to bitcoin. This key pair consists of a private key and a unique public key. The private key is used to create and sign the transactions to spend bitcoin, while the public key is used to send bitcoin. 

Private Keys For Bitcoin

A private is a randomly generated number that provides ownership of all the funds associated with the user’s bitcoin address. The most critical step in generating keys is to find a secure source of entropy. Generating a private key is similar to picking a number between 1 and 2256. Many online wallet generators use the movement of the pointer to create randomness. We simply achieve this by feeding a larger string of random bits into the SHA256 hash algorithm, which will then reproduce a 256-bit hash. If the result is less than n, we have found a suitable key. Otherwise, keep trying the same process until you find one. 

An example of the randomly generated private key, represented in a hexadecimal format is given below.

1F00423A4E227608A14A2616A2B0E9E52CE6330AC530EDCC317FC6A526AEFF

The getnewaddress command is used to generate a new key with Bitcoin Core Client. This command only displays the public key for security reasons. To ask the bitcoin to expose the private key, use the dumpprivkey command. 

Public Keys For Bitcoin

The public key is derived from the private key using elliptic curve multiplication. Bitcoin uses the Secp256k1[1] elliptic curve algorithm to implement its public-key cryptography.

  Formula=  K = k*G

Where,

G is constant or Generator point

k is a private key

K is a public key

Starting with a private key generated from a random entropy k. We multiply it by a predetermined point on the curve as Generator point G to produce another point on the curve, which is the corresponding public key K. The generator point is fixed for all keys in bitcoin.

Since the Generator point is the same[2], the private key multiplied by G will always give the same public key. The relationship between K and k is one-directional. That’s why sharing a public key doesn’t reveal the user’s private key.

Let’s look at the elliptic curve cryptography in detail and how it is an irreversible process.

Why Elliptic Curve Cryptography?

To understand why bitcoin uses elliptic curve cryptography, we first need to understand what an elliptic curve is and how it behaves mathematically.

Elliptic curve cryptography is a type of asymmetric cryptography based on the discrete logarithm problem as expressed by the addition and multiplication of points on the elliptic curve. 

Formula,

Here, The mod p (modulo prime number p) indicates that this curve is over a finite field of prime order p which creates a visual of dots scattered in two dimensions. 

The elliptic curve is symmetric to the x-axis. If you draw a straight line through this curve it will intersect the curve and no more than three points. And these three points will create a mirror reflection to the negative x-axis. This will create an infinite loop of dots connecting to the limit of n(Private key) which is quite impossible to reverse back to compactly retrieve the private key.

Get in-depth insight on Elliptic curve cryptography here.

Now, we know that we have different encryption algorithms available such as the most famous RSA algorithm. But the reason why an elliptic curve is more efficient is that the key size of an elliptic curve is 256 bits in comparison to RSA, which has a size of 3072 bits. Apart from that, the elliptic curve is more cryptographically stronger than RSA.

Addresses In Bitcoin

A bitcoin address is made up of characters and digits, which is a public address to receive funds. The bitcoin address is derived from the public key cryptographic hashing. It is a one-way hashing algorithm that produces a hash of an arbitrary-sized input. The algorithms used to make addresses from public keys are Secure Hash Algorithm SHA and RIPEMD160[3].

Starting with the public key K, We first compute the SHA256 hash and then compute the RIPEMD160 of the hashed result, formulating a 20-byte number.

Where, 

A is Resulting Bitcoin Address

K is Public key

Addresses generated from public keys consist of a string of letters and numbers and always begin with the digit “1”. Such as given below.

17jmdb5rbbyUHENYdx39XVYK7fsLpEoXOy

Bitcoin addresses are encoded as “Base58Check” [4]. The Base58Check uses a Base58 number system and checksum to enhance human readability.

What Is Base58 And Base58Check Encoding?

In order to represent long numbers in a compact way, bitcoins use the Base58 number system. The Base58 is a subset of Base64, omitting the characters that are frequently mistaken for one another and can appear identical, for example, 0(number 0), O(capital 0), l(lower L), and I (capital i). 

The Base58Check encoding format is mainly used in bitcoin to add an extra security layer against transcription errors. The checksum is an additional four bytes added at the end of data being encoded. The checksum here is derived from the hash of data. When this encoded hash passes through Base58Check code, the decoding software calculates the checksum of the data and compares it to the checksum included in the code. If the two match, the data is valid.

In order to generate a new kind of wallet that may start with different characters, one can make changes in the base58Check encoding algorithm.

What Is A Bitcoin Wallet?

A wallet is a simple application that acts as a primary user interface. The wallet controls access to the user’s money, keys, and balance. It is also responsible for creating and signing transactions.

A most common misconception about wallets is that they contain our money, in this case, bitcoin. However, the wallets only contain our keys, while all our coins are stored on the blockchain network. There are primarily two types of wallets: deterministic and non-deterministic.

Non-Deterministic Wallets

In non-Deterministic wallets, each key is independently generated from a random number. These keys are not related to each other. These keys are only used once. The disadvantage of non-deterministic wallets is the keys are random and hence need to secure the copies of all of them. Meaning all the wallets need to be backed up frequently. The use of this type of wallet is discouraged as this is too cumbersome to use.

Deterministic Wallets 

Deterministic Wallets contain private keys, all derived from a common seed, through the use of a one-way cryptographic hash function. The seed is a list of words which is helpful to recover the bitcoin keys in case of any accidental loss. This seed is sufficient to recover all private keys, import private keys, and easy migration to different wallets. 

HD Wallets

HD Wallets are the advanced form of deterministic wallets defined by the BIP-32[5]. HD wallets contain keys derived in a key structure. The key structure behaves in a way that a parent key can derive all the children’s keys, each of which can derive a sequence of grandchildren keys and so on.

HD wallets offer two major advantages over non-deterministic wallets. First, the key structure provides additional structural meaning, such as allocating different branches to different subsidiaries of an organization. The second advantage is that a user can create a bunch of public keys without having access to corresponding private keys, issuing a different public key to each transaction.

HD wallets can be used to generate different wallets for different blockchains from a single parent key.

Seed Phrases

HD wallets provide a secure mechanism to manage multiple keys and addresses. They are more powerfully useful if combined with a standard way of creating seeds of English words. This is known as mnemonic and is defined by the BIP-39 standard. This is usually 12 to 24 words, depending upon the wallet.

BIP-39[7] defines the creation of a mnemonic code and seed into seven steps mainly:

  1. Create a random entropy sequence of 128 to 256 bits.
  2. Create a checksum of the random sequence by taking the first bits of its SHA256 hash.
  3. Add the checksum at the end of the random number sequence.
  4. Split the result into 11-bit length segments.
  5. Now each 11-bit value is mapped onto a word from the dictionary defined by BIP-39. Here you can see the word list.
  6. The entropy then is derived to form a longer 512-bit seed using the key-stretching function PBKDF2. The seed produced is used to create a deterministic wallet and derive its keys. The key-stretching function takes two inputs: the mnemonic and the salt. The main purpose of this salt is to make it difficult to build a lookup table, enabling a brute force attack.
  7. PBKDF2 takes both the mnemonic and the salt in the parameter. Salt is a fixed string constant “mnemonic” combined with an optional user-defined passphrase. Now the PBKDF2 stretches the parameters using 2048 rounds of hashing with the HMAC-SHA156 algorithm to produce a 512-bit final value.

Transaction Scripts And Script Language

The bitcoin transaction script language is called Script. It is a stacked base execution language. When a transaction is validated, the unlocking script in each input is executed alongside the corresponding locking script to measure if it satisfies the spending condition. In this section, we will discuss both the locking and unlocking script. 

Turing Incomplete

The bitcoin transaction script is deliberately limited in one important way: There are no loops and complex conditional capabilities, meaning the language has limited complexity and execution time also called Turing complete. This is to ensure that the language can not create any complex logic, embedded in a transaction that results in the denial of service attack. 

Stateless Verification In Bitcoin

In bitcoin, all the information needed to execute a script is within the script. There is no state prior to execution of script or state saved after. If your system verifies a script, meaning all the other nodes of the network will also verify the script.

Script Construction 

Bitcoin’s transaction script mechanism depends on two types of the script to validate transactions: a locking and an unlocking script.

A locking script is a script that places a spending condition that must be satisfied to spend the output in the future. The locking script is also called scriptPubKey because it usually contains a public key and a bitcoin address. On the other hand, an unlocking script is a script which “solves” the condition placed on an output to spend the funds(using locking script). The unlocking script is also called scriptSig because it usually contains a digital signature. 

Each input UTXO contains an unlocking script and refers to a previously existing UTXO. The validation software copies the unlocking script, retrieves the UTXO from the UTXO pool referenced by the input and copies the locking script from that UTXO. The input is valid if the unlocking script satisfies the locking script condition. 

Advanced Keys And Addresses In Bitcoin

In this section, We will explore the idea behind advanced keys and addresses such as script and multi-signature addresses and vanity addresses.

Private Key Encryption With BIP-38

The private key is a secret key that must be preserved from theft and loss.  BIP-38[6] is a proposal that proposes a common standard for encrypting private keys with a passphrase. The entered passphrase and key is then encoded with a Base58Check to ensure security. 

The P2PKH Script

The P2PKH Script is also known as the pay-to-public key hash script. Most of the transactions happening on the bitcoin network spend outputs locked with the pay-to-public key hash script. These outputs carry a script that locks the output to a public key hash or designated bitcoin address. An output locked by a P2PKH script can be spent by revealing a public key and a digital signature created by the corresponding private key.

The Digital Signatures Algorithm (ECDSA)

The P2PKH Script is also known as the pay-to-public key hash script. Most of the transactions happening on the bitcoin network spend outputs locked with the pay-to-public key hash script. These outputs carry a script that locks the output to a public key hash or designated bitcoin address. An output locked by a P2PKH script can be spent by revealing a public key and a digital signature created by the corresponding private key.

How Digital Signature Forms

A digital signature consists of two parts: Creating a signature using the private key, and the second part allows everyone to verify the signature, using the message and the public key of the sender.

Formula,

Sig=Fsig(Fhash(m, dA))

Where,

dA= Signing private key

m= Transaction

Fhash= Hash function

Fsig= ECDSA signing algorithm

Sig= Resulting signature

To verify a signature, you must have the signature, the transaction and the public key(that corresponds to the private key which has been used to create the signature). 

Multi Signatures Script And Why Do We Need It?

Multi-signature scripts are really important in terms of asset perseverance. Multisignature scripts use a special condition where N public keys are recorded in the unlocking Script, and at least M(threshold) of them must be provided to spend the funds. For example, A 2-3 multi-signature is one in which three public keys are listed as the potential signer, and at least two of the signers must sign the transaction to spend the funds. Now, multi-signature Script is restricted to 3 public keys, which are standard; however, this standard doesn’t imply that multi-signature scripts are wrapped in a pay-to-script-hash[11], which has a limit of 15 public keys.

The general form of a locking script setting an M-of-N multi-signature is:

M <Public Key 1> <Public Key 2> ….. <Public Key N> N CHECKMULTISIG

In the case of 2-3 multi-signature scripts, the locking and unlocking Script would form a combined script which is: 

<Signature A> <Signature B> 2 <Public Key A> <Public Key B> <Public Key C> 3 CHECKMULTISIG

Pay-To-Script Hash (P2SH)

Although multi-signature scripts are a powerful feature in the bitcoin world, they are cumbersome to use. Let’s validate the above-given statement. Suppose Jacob is an electronics importer, and he used multi-signature features extensively for its corporate accounts. He has created a multi-signature script of 2-3, which looks like this.

2 <Jacob’s Public Key> <Partner1 Public Key> <Partner2 Public Key> <Partner3 Public Key> <Attorney Public Key>  5 CHECKMULTISIG

In this case, each customer has to use a special wallet to create a custom transaction script. Furthermore, the preceding transaction is 5 times larger than a simple payment transaction; hence the burden of paying the fee will be on the customer for this large size of transaction. All of these issues make a locking script pretty complex to use. 

To cope with these issues, P2SH was developed. With P2SH, the complex Script is replaced with a cryptographic hash(redeem Script because it is presented in the system during redemption time). 

From Table2, you can witness that the complex script and conditions(redeem script) is not part of the locking script. Instead, the locking script contains the hash of the redeem Script, and the redeem Script itself is part of the unlocking Script, which shifts the burden of fees and complexity both from the sender to the recipient. Note that you can not put a P2SH inside a P2SH script because P2SH specifications are not recursive. However, technically this is possible using the RETURN function in a redeem script.

Data Recording Output(Op_RETURN)

In bitcoin, storing data unrelated to payment is controversial. Although blockchain possesses powerful capabilities, storing nonpayment data may cause blockchain overflow, burdening the nodes and creating UTXOs which can never be spent. A consensus was reached in version 0.9 of Bitcoin Core Client, with the introduction of the OP_RETURN script. 

OP_RETURN allows users to add extra 80 bytes of nonpayment data to a transaction output. This data is explicitly stored in an unspendable output structure.

What Are Timelocks?

Timelocks are the restrictions that imply that the transaction is only spendable after a certain time period. They are useful for postdating transactions and locking funds for the future.

Transaction Locktime(nLocktime)

Transaction locktime is a transaction level field that defines the propagation and execution time of a transaction. By default, it is set to zero. If nLocktime is below 500 million, it is considered as a block height, which implies that the transaction is not valid until the specific block height is achieved. On the other hand, if the nLocktime is greater than 500 million, it is interpreted as the Unix Time Epoch(that means the transaction is not valid until the specific time).

Limitations Of Transaction Locktime

Transaction Locktime, although makes it possible to spend some output in the future, it doesn’t make it possible. Want to know how? Let’s understand this with an example.

  1. Alice signs a transaction spending one of its outputs to Alice’s address with nLocktime of 3 months in the future(meaning Bob does not redeem the funds until 3 months).
  2. Alice can create another transaction with the same UTXO input (double spending) without nLocktime to Jack. Thus Bob can spend the Locked funds before the elapsed time while Alice can not.

To mitigate this issue, bitcoin has introduced a concept of time lock called, Check Lock Time Verify[8].

Check Lock Time Verify(CLTV)

In BIP-65, a new operator called Check Lock Time Verify was added to the scripting language. CLTV is a per-output timelock, unlike nLocktime, which was a per-transaction timelock. CLTV doesn’t replace nLocktime, while it adds another suffix Verify to restrict the specific UTXO to be spent in the future. CLTV halts the execution if the Script returns FALSE.

Let’s take the above Alice example here again. If Alice is paying Bob’s address, it will look like a simple P2PKH script. The locktime will be inserted into the redeem Script of an output.

DUP HASH160 <Bob’s Public Key Hash> EQUALVERIFY CHECKSIG

To lock the script for 3 months, a locking script with the hash of a redeem script will look like this.

<now + 3 months> CHECKLOCKTIMEVERIFY DROP DUP HASH160 <Bob’s Public Key Hash> EQUALVERIFY CHECKSIG

This script restricts both Alice and Bob to spend the locked UTXO for 3 months.

Relative Timelocks

Relative Timelocks are useful if one wants to create an off-chain transaction for two or more interdependent transactions while imposing a timelapse to one transaction that is dependent on the elapsed time of the confirmation from the previous transaction. Relative Timelocks are part of BIP-68 and BIP-112 and are integrable to both transaction-level feature and script level opcode using nSequence[9] and CHECKSEQUENCEVERIFY(CSV)[10] correspondingly.

A Consensus-Enforced Relative Timelock(nSequence)

nSequence allows the modification of the transaction in the mem pool. In that case, a transaction containing inputs with nSequence value below 232-1 (0xFFFFFFFF) indicated as “not finalized” or a transaction that would be held in the mem pool until it was replaced by another transaction spending the same input with a higher nSequence value.  Once a transaction whose nSequence is greater than 0xFFFFFFFF  is received, it will be considered finalized and mined.

Relative Timelock with Check Sequence Verify(CSV)

The CSV script code leverages the nsequence values in a script. The CSV op-code allow the only transactions whose nsequence value is gretaer than to the CSV parameter. The main purpose of CSV is to limit the spending of UTXO untill the specific time or block height is reached.

The CSV is briefly defined in the BIP-112.

The Segregated Witness

Before segwit, every input in a transaction was preceded by the witness data that unlocked it. This witness data is used to embed in the input transaction as part of each input. The term “segwit” means to simply separate the witness data from the unlocking script of a specific output. Segwit is an architectural change to bitcoin, which compels to move the witness data from the scriptSig to the separate witness data structure.

Segregated witness (segwit) is an upgrade to the bitcoin consensus rule and network protocol. It was proposed in BIP-69[13] and implemented as a soft fork on mainnet in august 2017.

Why Segwit?

Segwit has several effects on scalability, security, economic incentives, and performance of the bitcoin blockchain; a few of them are listed below.

  1. By moving witness data outside the transaction, the transaction hash no longer needs to hold witness data, which can be modified by a third party(malleability attacks).
  2. The witness data is often a big contributor to the size of transaction data. Scripts such as multi-sig are complex and are huge in size. By moving witness data outside of transactions, bitcoin improves scalability. The witness data doesn’t need to be stored by each node and can be ignored by nodes after a simplified payment transaction.
  3. Before segwit, the algorithm used to produce a signature required a computational power of O(n2). Segwit reduces this computational power by O(n).

Vanity Addresses 

Vanity addresses are used to create a bitcoin address with enhanced human readability. For example, 1QUITBPzzD72PUXLzCkYAtGFYmK5vYNR33 is a valid vanity address that contains the letter forming the word “QUIT” as the first four Base58 letters. Vanity addresses try multiple patterns by testing billions of private keys until an address with the desired pattern is found. 

Let’s take an example over here. Ali is doing an ICO for his project in the UK. Let’s say Ali is organizing a bitcoin ICO drive and wants to attain a vanity address to capture the attention of investors. Ali can create a vanity address that must start with “1 ICO” to promote the charity. This search of the address will look like a search from a range of 1ico1111111111111111111111111 to 1icozzzzzzzzzzzzzzzzzzzzzzzzzz. Each additional character will increase the difficulty by a factor of 58. Patterns with more than 7 characters will require extra hardware. 

Hence, to reduce the requirement of additional mining rigs, Ali can outsource the work to a pool of vanity miners. This pool is a special service with GPU hardware that allows the miners to earn bitcoin in search of vanity addresses. 

Vanity addresses can be used to increase the security measure against theft. This distinctive address makes it harder for adversaries to substitute their own address and foul your customers into paying them instead of you.

Glossary

Wallet: A crypto wallet is a type of digital wallet used to send and receive cryptocurrencies. This is analogous to a physical wallet. However, instead of storing physical currency, the wallet stores the cryptographic information used to access blockchain addresses and send transactions. (“Investopedia”, 2021)

References

1 River Financial, (n.d), Secp256k1

https://river.com/learn/terms/s/secp256k1/

2 River Financial, (n.d.), Generator Point retrieved from https://river.com/learn/terms/g/generator-point/

3 Bitcoin WIki, (2021), RIPEMD160

https://en.bitcoin.it/wiki/RIPEMD-160

4  Bitcoin Wiki, (2021), Base58Check Encoding Retrieved from https://en.bitcoin.it/wiki/Base58Check_encoding

5 Wuille P.,(Feb, 11 2012), Hierarchical Deterministic Wallets

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

6 Caldwell M., Voisine A.,(Nov,11 2021), Pass-phrase protected private key

https://github.com/bitcoin/bips/blob/master/bip-0038.mediawiki

7 Palatinus M., Voisine A., Bowe S., (Oct, 9 2013), Mnemonic code for generating deterministic keys

https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

8 Todd P., (2014, October 01), OP_CHECKLOCKTIMEVERIFY. Retrieved from https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki.

9 Friedenbach M., BtcDrak, Dorier N., Kinoshitajona, (2015, May 28), Relative lock-time using consensus-enforced sequence numbers. Retrieved from https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki.

10 BtcDrak,  Friedenbach M., Lombrozo E., (2015, August 10), CHECKSEQUENCEVERIFY. Retrieved from 

https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki.

11 Andresen G. (2011, October 18), Address Format for pay-to-script-hash. Retrieved from https://github.com/bitcoin/bips/blob/master/bip-0013.mediawiki.

12 Antonopoulos A. (Originally 2014, December), Mastering Bitcoin: Programming the Open Blockchain. Retrieved from https://github.com/bitcoinbook/bitcoinbook.

13 Atlas K., (June, 06 2015), Lexicographical Indexing of Transaction Inputs and Outputs. Retrieved from https://github.com/bitcoin/bips/blob/master/bip-0069.mediawiki.

You can also read on the first part of Bitcoin Publication here.

Co-authors

Zainab Hasan
Shakeib Shaida

Share

Share on facebook
Share on linkedin
Share on twitter

Read More Articles

Amphora
25
23