Generate bitcoin multisig addresses

In this post I’ll show you how I generate multisig bitcoin addresses in python3.6. In a previous post, we have seen how to generate P2PKH addresses.

With multisig addresses, you can delegate the expenditure of an UTXO to a set of public keys. Doing so, you can manage complex scenarios like death, lost keys, kidnapping or extortion.

We have already seen how to generate public keys so we shall to focus on the new parts of code to handle multisig generation.

Bitcoin P2SH

In contrast to what a lot of people think, Bitcoin has smart contracts. However, the language is not Turing complete and only a set of scripts are valid for a standard transaction. Standard transactions are those who are propagated by bitcoin nodes (you can activate the propagation of non standard programs but it’s not the default). Despite it can be seen as a limitation, it bring us much more security than other alternatives. It’s what we would expect from a platform where a lot of value will be stored.

Standard transactions

The following scripts are available for a standard pubkey:

  • Pubkey (P2PK) (first bitcoin 0.1 release)
    • Script PubKey: <pubkey> OP_CHECKSIG
    • ScriptSig: “<sig>“
    • witness: “(empty)“
  • Pay To Public Key Hash (first bitcoin 0.1 release)
    • ScriptPubKey: “OP_DUP OP_HASH160 <PubkeyHash> OP_EQUALVERIFY OP_CHECKSIG“
    • ScriptSig: “<sig> <PubKey>“
    • witness: “(empty)“
  • Pay To Witness Public Key Hash (P2WPKH) [BIP-141]
    • ScriptPubKey: “0 <v0-witness program>“
    • ScriptSig: “(empty)“
    • witness: “<sig> <PubKey>“
  • Pay To Script Hash (P2SH) [BIP-16]
    • ScriptPubKey: “OP_HASH160 <Hash160(redeemScript)> OP_EQUAL“
    • ScriptSig: “<sig> [sig] [sig…] <redeemScript>“
    • witness: “(empty)“
  • Pay To Witness Script Hash (P2WSH) [BIP-141]
    • ScriptPubKey: “0 <v0-witness program>“
    • ScriptSig: “(empty)“
    • witness: “0 <sig> [sig] [sig…] <v0-witnessScript>“
  • Pay To Script Hash Witness version (P2SH-P2WPKH/P2WSH) [BIP-141]
    • ScriptPubKey: “OP_HASH160 <Hash160(P2SH witness program)> OP_EQUAL“
    • ScriptSig: “0 <redeemScript>“
    • witness:
      • Option 1 (P2WPK): “<sig> <PubKey>“
      • Option 2 (P2WSH): “0 <sig> [sig] [sig…] <redeemScript>“
  • Multisig [BIP-11]
    • ScriptPubKey: “<m> <A pubkey> [B pubkey] [C pubkey…] <n> OP_CHECKMULTISIG“
    • ScriptSig: “OP_0 <A sig> [B sig] [C sig…]“
    • witness: “(empty)“
  • Null Data (it creates an UTXO that cannot be spent, we’ll ignore this case)
    • ScriptPubKey: “OP_RETURN <0 to 40 bytes of data>“
    • ScriptSig: “(Null data scripts cannot be spent, so there’s no signature script.)“
    • witness: “(empty)“

Generating the redeem script

Despite there is the opcode OP_CHECKMULTISIG, multisig addresses are now widely generated under the P2SH address schema. In a nutshell, with P2SH you are sending funds to a script. You, as a sender, only know the hash of this script. When the receiver wants to expend funds, he sends the redeem script and the needed data (signatures, etc.) for the script to execute successfully.

The redeem script addresses were defined in BIP-13. The valid redeem script schemes are:

  • P2PK: <pubkey> OP_CHECKSIG
  • P2PKH: OP_DUP OP_HASH160 <PubkeyHash> OP_EQUALVERIFY OP_CHECKSIG
  • Multisig: <m> <A pubkey> [B pubkey] [C pubkey…] <n> OP_CHECKMULTISIG

That’s the reason it’s commonly called P2SH-P2PKH, etc. Because you are paying to a script where the type of the script is a P2PKH. Remind that when you send funds to a script, you don’t know what type the script is. The redeem conditions are delegated to the receiver.

First, let’s define our multisig address:

  • 2 public keys will be able to unlock funds
  • From a total of 3 public keys

The 3 public keys are (you can generate them following the previous post):

  1. 04bb02aad88960b2b93c6b4a61b683966c3720e70ae7da71676129f441a095787e239b3e2ad9305f1011241d106fa0adabfb2eefe264b52a108051f324b01d4109
  2. 0497647726c390d855b7d208c841bf4a250816998eb169b60eaf3b9f7e058f42c8b4f8c9b6e0a4206dcabbf1ba851f56eff6c746e378aa62bf8bf25da0a10b65af
  3. 0460d434c9a71ec0eec0cf5905604a56c904d2cc4895e5d77292682be73cd2550224433462264a36e30d008f21daeb2d3ecf91fa6a87194ddaa00f9f926c3a9428

Then, we can construct our redeem script:

<m> <A pubkey> <B pubkey> <C pubkey> <n> OP_CHECKMULTISIG

Where (all data is represented in hexadecimal):

  • m = 2 = OP_2 = 52
  • A pubkey = 04bb02aad88960b2b93c6b4a61b683966c3720e70ae7da71676129f441a095787e239b3e2ad9305f1011241d106fa0adabfb2eefe264b52a108051f324b01d4109
  • B pukey = 0497647726c390d855b7d208c841bf4a250816998eb169b60eaf3b9f7e058f42c8b4f8c9b6e0a4206dcabbf1ba851f56eff6c746e378aa62bf8bf25da0a10b65af
  • C pubkey = 0460d434c9a71ec0eec0cf5905604a56c904d2cc4895e5d77292682be73cd2550224433462264a36e30d008f21daeb2d3ecf91fa6a87194ddaa00f9f926c3a9428
  • n = 3 = OP_3 = 53
  • OP_CHECKMULTISIG = ae

You can check the hexadecimal values of the opcodes in this page. If you want to know how this scripts are being executed, you can see this video from Andreas Antonopoulos.

For the data that is not an opcode, you have to specify the size, in bytes, before the data, ie, we have to prefix the addresses with the 41 hexadecimal number (that’s is 65 bytes or 132 bits).

Finally, we concatenate all the data:

524104bb02aad88960b2b93c6b4a61b683966c3720e70ae7da71676129f441a095787e239b3e2ad9305f1011241d106fa0adabfb2eefe264b52a108051f324b01d4109410497647726c390d855b7d208c841bf4a250816998eb169b60eaf3b9f7e058f42c8b4f8c9b6e0a4206dcabbf1ba851f56eff6c746e378aa62bf8bf25da0a10b65af410460d434c9a71ec0eec0cf5905604a56c904d2cc4895e5d77292682be73cd2550224433462264a36e30d008f21daeb2d3ecf91fa6a87194ddaa00f9f926c3a942853ae

Generating the bitcoin address

Once we have the redeem script, we follow the BIP-13 specification:

    base58-encode: [one-byte version][20-byte hash][4-byte checksum]

For mainnet, the one-byte version is 05. The 20-byte hash is the hash160 of the previous script:

def get_address_for_P2PSH_payments(self, redeemScript, encoding="base58"):
        address_version_byte = binascii.unhexlify("05")
        addr_without_checksum = address_version_byte + hash160(binascii.unhexlify(redeemScript)).digest()
        btc_addr = base58.b58encode_check(addr_without_checksum)
        return (btc_addr.decode(), redeemScript)

Source: https://github.com/albpal/my-crypto-wallet/blob/master/mycryptowallet/bitcoinAddress.py

The previous script give us the address: 338Qs329uDr8t12YNVdfBJqFWR9NoHdxTU

Annex

Python code

Reedem script generator

    def p2multisig_script(self, pubKeyList, n=1, m=1):
        redeemScript = binascii.unhexlify(hex(n + 80)[2:])

        uncompressed_pubkey = binascii.unhexlify("41") + binascii.unhexlify(pubKeyList[0].encode('utf-8'))
        redeemScript = redeemScript + uncompressed_pubkey

        for pubKey in pubKeyList[1:]:
            uncompressed_pubkey = binascii.unhexlify("41") + binascii.unhexlify(pubKey.encode('utf-8'))
            redeemScript = redeemScript + uncompressed_pubkey

        redeemScript = redeemScript + binascii.unhexlify(hex(m + 80)[2:]) + binascii.unhexlify("ae")
        return binascii.hexlify(redeemScript).decode()

Generate bitcoin addresses in python

In this post I’ll show you how I generate bitcoin addresses in python3.6. The purpose of these addresses is to hold bitcoins for long times and not for frequently usage (because if not, you should import the private key to other more complex software you have not fully read).

Why generate my own bitcoin addresses?

Because you should take care about everything that has been in contact with your private keys. Remember that if you don’t hold the private keys needed to spend your Bitcoins, you don’t own any Bitcoin. And if you don’t take care of your private keys, everyone that knows them will own also your Bitcoins.

Address generation

Let’s create an address for a pay to public key hash (P2PKH) payment. You don’t need to import it in any wallet. It’s just for generating an address to receive payments. If you import the private keys to a wallet (a software you has not validated) you should move back to an address you have generated and fully validated as soon as possible.

Generating private keys

A bitcoin private key is a number between 1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140. The critical point is to generate it from a source with the highest entropy possible.

A source with a high entropy, broadly speaking, is good at generating random numbers. Thus, we need a data source with the highest entropy possible to generate our private key. We have several options:

  • A good dice (the best choice in terms of security)
  • Rely on good programming libraries

It’s important to do not trust on human entropy generation. We tend to generate patterns so it’s really a bad idea. For the sake of simplicity, I’ll choice a python3 library named secrets.

import secrets
import binascii

def generatePrivateKey():
	number = int(secrets.randbelow(1 << 256))
	while number < 1 or number > 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140:
	    number = secrets.randbelow(1 << 256)
	return binascii.hexlify(number.to_bytes(32, byteorder='big'))

generatePrivateKey()

Voilà! This code snippet generates the most important thing we have to take care of: private keys.

Generating public keys

Bitcoin uses an algorithm named Elliptic Curve Digital Signature Algorithm (ECDSA) to generate, from the previous random number, a public key. In particular, the properties of the curve used in bitcoin is the curve secp256k1. We have used the following example as the private key: E9873D79C6D87DC0FB6A5778633389F4453213303DA61F20BD67FC233AA33262.

import ecdsa
import binascii

def generatePublicKey(privKey):
	bytes_privKey = binascii.unhexlify(privKey)
	return ecdsa.SigningKey.from_string(bytes_privKey, curve=ecdsa.SECP256k1).get_verifying_key().to_string()

binascii.hexlify(generatePublicKey(b"E9873D79C6D87DC0FB6A5778633389F4453213303DA61F20BD67FC233AA33262"))

Generating bitcoin addresses

The last step in order to be able to receive Bitcoins is to generate from the previous public key your bitcoin address. Bitcoin can perform that in different ways:

  • Base58Check encoding of the hash of the previous public key (P2PKH). Available since first bitcoin 0.1 release
  • Addresses for P2SH payments. Available since BIP-13 activation
  • Addresses for segregate witness payments. Available since BIP-141 activation

The most secure would be generating a 3of5 multisig script for P2PSH or P2WSH and share the keys among secure and different places/persons. However, for the sake of simplicity, we’ll explore P2PKH. In further posts, we will cover multisig address generation. The public key used is 588d202afcc1ee4ab5254c7847ec25b9a135bbda0f2bc69ee1a714749fd77dc9f88ff2a00d7e752d44cbe16e1ebcf0890b76ec7c78886109dee76ccfc844542.

import binascii
import hashlib

def ripemd160(x):
    d = hashlib.new('ripemd160')
    d.update(x)
    return d

def hash160(x):
    return ripemd160(hashlib.sha256(x).digest())

def get_address_for_P2PKH_payments(pubKey, addr_version=0):
	pubkey_hex = binascii.unhexlify(pubKey)
	hashed_key = hash160(pubkey_hex).digest()
	btc_addr = base58.b58encode_check(addr_version.to_bytes(1, byteorder="big") + hashed_key).decode()
	return btc_addr

get_address_for_P2PKH_payments(b"588d202afcc1ee4ab5254c7847ec25b9a135bbda0f2bc69ee1a714749fd77dc9f88ff2a00d7e752d44cbe16e1ebcf0890b76ec7c78886109dee76ccfc8445424")

It will generate the bitcoin address: 17Pe3AFYeqk3Nnneyr7SE3EkSauJkbHqaP

Conclusions

It’s really easy to generate bitcoin addresses trusting the minimum in third-party code (including open source, they are not as secure as you may think). You can master these pieces of code to generate your own addresses and provide an extra security. We have imported only the following libraries:

  • binascii
  • hashlib
  • ecdsa
  • secrets (we’ll see how generate entropy in further posts to avoid this dependency)

In future posts…

  • How to use a dice to generate entropy to avoid secrets or other third-party libraries/systems
  • How to generate a 3of5 multisig address to handle real circumstances: 2 private keys compromised, death, kidnapping or extortion

Buy Bitcoins securely below the price market

In this post I’m going to show you how to buy Bitcoins without a middleman holding your Bitcoins and below the price market . You will always keep your private keys with you and you won’t have to share them with others.

First of all, let me introduce an application: Bisq.

Bisq is an open-source desktop application that allows you to buy and sell bitcoins in exchange for national currencies, or alternative crypto currencies.

Once you create and setup an account in Bisq, you will be able to contact to other persons to buy Bitcoins (or sell).

Installing and setting up Bisq

Download Bisq for your operating system: https://bisq.network/downloads/.

You will see the below windows (or similar if your version is different) when you launch Bisq:

buy Bitcoins - main windows

Next, let’s configure an account:

buy Bitcoin - setup account

Despite we have chosen SEPA, you can select a different payment method. My suggestion is to choose a payment method broadly accepted in Bisq because it will be more liquid

After you have configured your account, setup a wallet seed and a wallet password by clicking the corresponding tabs as shown in the above image. Store both things in a secure way. After that, perform a backup (Certainly, I perform a backup every time I transact on Bisq).

Open a trade to buy Bitcoins

Finally, we can create an offer to buy Bitcoins:

buy Bitcoins - open trade

Notice how I have set a dynamic price of 1% below the price market. The price market is shown in red on the image. I have bought always, at least, at 1% below the price market (for those who think nobody will accept it). Also, look at the trade fee! Only 0.20%. You will have to hold some Bitcoins to pay in advance in escrow.

The not so good part

In contrast to the previous obvious benefits, the trade can take days to complete. The steps in a SEPA trade are:

  1. Create an offer
  2. Someone accepts your offer
  3. Send the SEPA transfer
  4. Wait for the counterpart to receive your payment
  5. When received, the funds will be send to you

While performing the above steps, the funds are locked and secured in a bitcoin smart contract. You can close the application and reopen it later without problem despite you have opened trades. However, if you have opened trades, you will have to open the application to check if someone has accept or modify your trade state. Otherwise your trade could be arbitrated and you may loose your Bitcoins stored as collateral in the smart contract.

If one of the parts behalf incorrectly, you can ask for two random arbitrators to review all the process. I have to admit I never asked for arbitrage.

Enjoy and hodl!!

Analyzing the hardware requirements to be an Ethereum full validated node II

Final story

After the first review about what we need, in terms of hardward, to run an Ethereum client in order to be a full validated node, I have summarized all my tests and calculated some ratios that can help you to estimate your requirements.

Test environment (you can skip it if you are not interested how I built the test environment)

Processor: Intel(R) Core(TM) i7–2600 CPU @ 3.40GHz

RAM: 4x RAM 4096 MB DDR3

Disk: 2x SSD SATA 240 GB

Monitoring tools: collectd, InfluxDB and Grafana

Metrics (most relevants): IO throughput, CPU usage and blocks per minute

Ethereum client: parity –no-warp –cache-size=4096 –db-compaction=ssd –scale-verifiers –num-verifiers=2

In order to limit machine resources I have applied CGroups to different executions of Parity.

Results

Test 1, 2 and 4 have limited disk throughput. Test 3 has limited CPU

As we can see, the most relevant resource for synchronization’s speed is disk throughput. CPU also has an impact but in a different order of magnitude.

A rule of thumb I have extracted empirically from the previous results is that the ratio between blocks / minute and Avg MB/s IO write goes from 21 (21MB/s) to close to 16 (35.6MB/s and 68MB/s):

It provides us with an estimation about how much time a machine will expend to sync a full validated node:

Last block height: 6677669

Processor: Intel(R) Core(TM) i7–2600 CPU @ 3.40GHz

AVG blocks/minute with a disk providing 48 MB/s of random writes: 48*16=768

Theoretical time to sync: 6677669/768 /60 /24 = 6.04 days

You can adjust it if your CPU is not the same. For example, if you only have 1/8 of the capacity of the previous CPU, adjust the AVG blocks/minute as follow:

768 – 1/(1/8)*9 = 696 block/minute

And it will take 6.66 days to sync.

Conclusions

  • I still cannot say what is the minimum hardware. The tests were not conclusive
  • However, the data shown here gives us an estimation
  • I will update the bottom part of this story with hardware that I know it can run a full validated node

Tested hardware

Warning: The disk space needed may vary if you are looking it long after I’ve written it down.


Processor: Intel(R) Core(TM) i7–2600 CPU @ 3.40GHz
RAM: 4x RAM 4096 MB DDR3
Disk: 2x SSD SATA 240 GB

PRICE: 32.54 EUR / month (https://www.hetzner.com/)

Hardware requirements to be an Ethereum full validated node

One of the mantras of crypto is:

Don’t trust. Verify

But, what verify means? When we talk about blockchain, it means to start at the beginning of the blockchain (the genesis block) and to pull every transaction ever recorded on blocks from peers you are connected at. Then, to execute every transaction to calculate the intermediate states (UTXO in Bitcoin or accounts state in Ethereum) and repeat it until you reach the latest block. This process is called synchronization of a full validated (full node in Bitcoin) node.

However, you could remove old states and blocks (pruning mode) and still being a full validated node, as you have validated all the blockchain to reach the latest state. You haven’t trusted anyone.

Lately this process has been quite expensive for Ethereum due to DoS attacks and the deployment of arbitrary code (smart contracts has to be executed in order to move from one state to another). So, what requirements in terms of hardware are needed to run a full validated Ethereum node and to be able to perform the verification without trusting anyone?

Monitoring the synchronization process

I have chosen Parity because it is the only client that is able to validate the full blockchain and prune the old state on the fly (and avoid to store +1TB of data). Geth is working on it but it’s not done yet.

Following the command line executed:

parity -no-warp -cache-size=4096 -db-compaction=ssd -scale-verifiers -num-verifiers=2

The sync process started at: Sep 19, 2018 14:13:22
The sync process ended at: Sep 23, 2018 17:38:24

It take about 4days to validate all the Ethereum blockchain. It’s not that much. But, what was the hardware consumption?

I have used Collectd + Influxdb + Grafana to monitor this consumption.

Consider it random writes!

You can see the minimum, maximum and average.

We can see that Parity makes an intensive use of syscalls

As you can see, there are a lot of syscalls (CPU interruptions) per second.

Intel(R) Core(TM) i7–2600 CPU @ 3.40GHz

Despite syscalls, the CPU seems to be OK. Maybe it will be a problem if the client shares the CPU resource with others (in fact, I had to moved from a LPAR cloud provider due to CPU interrupt abuse).

From a total of 16GB

(The y-axis label is incorrect. It is blocks per SECOND). At the beginning, the rate is very high. If we get the average rate removing the first moments:

(The y-axis label is incorrect. It is blocks per SECOND). If Ethereum miners find a block, in average, every 14 second, it means ~4.29 blocks per minute. I have got an average of 5.67 blocks per second (340.2 blocks per minute) so I would expect to sync a full validated node with less resources but expending more time.

Conclusions

  • To get a full validated Ethereum node without storing +1TB of SSD, we need a client permitting pruning while is syncing the full blockchain
  • It makes an intensive use of random writes to disk. It’s a lot included for a SSD
  • It makes an intensive use of syscalls which interrupt the CPU a lot
  • A SSD able to perform: 68 MB/s of random writes and 30.9 MB/s of randoms reads on average. +112GB of capacity (24/09/2018).
  • 13–14GB of RAM
  • A CPU able to handle a lot of interrupts
  • These requirements are not the minimums. With the above hardware, you will get a block synced per minute average of 340.2. You will eventually get synced with a rate of 4.29 and above but it will take more time
  • The Ethereum community is aware about these requirements and is trying to build a more efficient client. Check out the work of Alexey Akhunov https://www.youtube.com/watch?v=kJi77aV7Fk0 and https://medium.com/@akhounov/turbo-geth-beta-constantinopole-tests-fda38cbe87a

Future work

The main goal of this work is know the MINIMUM required hardware to run a full validated node. I have shared a valid configuration to start. However, I will restrict these resources to get the minimum and share the results again. (SECOND PART RELEASED: here)

Analyzing Ethereum storage cost

When we develop smart contracts, we have to take care of the storage cost. Let’s see the different types of storage:

  • Volatile stack access: Stack
  • Volatile memory access: Memory
  • Non-volatile: storage

Furthermore, we also have available the context information:

  • Code associated to the contracts
  • Access to the data field of the transactions

How to operate with the different storage types

Following, we are going to review the different storage types and their storage cost.

Stack

All Ethereum Virtual Machine operations (EVM opcodes), except the operations STOP, JUMPDEST and INVALID, use the stack both to read or to write on it. However, we are gonna see the operations that read or write data without performing any computation:

The stack depth ranges from 0 to a maximum of 1024

  • POP: Gets the value on the top of the stack (level 0)
  • PUSH1…PUSH32 (PUSHX): Inserts X bytes on top of the stack
  • DUP1…DUP16 (DUPX): Duplicates the value at X on top of the stack
  • SWAP1…SWAP16 (SWAPX): Swaps values on X and the top of the stack

Memory

The operations that access to this memory, either to read or to write, are:

  • CALLDATACOPY: Reads the data field of a transaction and load it in memory
  • CODECOPY: Reads the code associated to the current contract and load it in memory
  • EXTCODECOPY: Reads the code associated to an external contract and load it in memory
  • MLOAD: Reads, from the memory, a value
  • MSTORE: Stores in memory a word/32bytesvalue
  • MSTORE8: Stores in memory a 8bytesvalue

Storage

Unlike stack and memory, the data stored on this memory are persistent on the contract address for futures accesses. Following, the operations to manipulate this memory are:

  • SLOAD
  • SSTORE

It’s worth to mention the “S” and “M” of memory and storage respectively.

Costs

All previous operations have a storage cost expressed in GAS units. When an user sends a transactions he/she gives a ETH price per GAS unit. The miners have configured a minimum GAS price so a higher minimum GAS will let more margin but discarding a bigger number of transaction. Consequently, it generates a market where ETH is traded per GAS. The less the code consumes in terms of GAS, more efficient will be in terms of resources needed to execute the code. The following table shows the costs, in GAS, of the different operations depending of the size of the data:

The most expensive one is the non-volatile storage. Operate with the memory is similar to operate with the stack in term of GAS when the size is about the KB but it increases exponentially with the size. This relation is shown in the following picture:

3*<words>+ROUND(POWER(<words>,2)/512,0)

If we set a GAS price in ETH based on https://ethgasstation.info:

2018/01/14 12:17 AM

Then, we can make an estimation, in terms of ETH, of the cost per storage type:

STD=5gwei, FAST=50gwei

The miners will include transactions with a higher price so when an user pays more per GAS, more fast the his/her transaction will be included in a block.

Last, we can set a $/ETH rate, for example, 1356.30$:

1356.3$ = 1 ETH, 2018/01/14 12:17 AM

Conclusions

Therefore, store data permanently on Ethereum is extremely expensive as we have seen. Thus, it has no sense to use Ethereum to store data. Rather, it should store only the required data to work properly and delegate the storage to other solutions: Swarm, Filecoin, IPFS, etc. For example, a good idea is to store a Merkle Tree root hash as a tamper proof of data store on an external service.

Also an unexpected and fast increase of ETH prices can increase the cost of the operations in terms of FIAT money to a high levels. As a result, miners will have to adjust their min ETH price per GAS, if it happens, to readjust the costs.

Finally, it’s important to analyze smart contracts in terms of GAS consumption to control the operational costs.

References