We previously worked through the process of generating a Bitcoin private address and translating it into a shareable public address using only the tools and libraries shipped with Elixir and Erlang.

The guiding force behind that article was Andreas Antonopoulos’ excellent Mastering Bitcoin book.

Let’s take another bite out of Mastering Bitcoin and implement the algorithm Andreas describes for “mining for vanity addresses” at the end of chapter four. After we implement the basic algorithm, we’ll add our Elixir special sauce and turn it into a fully parallelized procedure.

## What is a Vanity Address?

The concept of a vanity address is simple. It’s a normal Bitcoin public address that contains some sequence of desired characters.

For example, a random Bitcoin public address might look like the following:

``````
1HKz4XU7ENT46ztEzsT83jRezyiDjvnBV8
``````

On the live network, Bitcoin addresses always begin with `1`, but the remaining characters are entirely random.

A vanity address might look like this:

``````
1pete7qrCiembh8AEf1zRP2zn6nDsLoHC
``````

You’ll notice that the first five characters of this address are `1pete`. This isn’t an accident! I’ve intentionally sought out a public address that begins with my name, Pete, so people know who they’re sending their large sums of Bitcoin to.

While the term “mining” sounds intimidating, the actual process of generating these vanity addresses is laughably simple.

## How do you Mine Vanity Addresses?

“Mining,” in this context, is just another term for repeatedly doing something until some condition is met. As in, “keep digging until you find gold!”

We’ll mine our vanity public address by repeatedly generating a private key, transforming it into a public address, and checking if the resulting address matches our desired pattern.

That’s it!

Building that in Elixir should be a walk in the park. We’ll start off by creating a new `VanityAddress` module and stubbing out a `generate_private_key/2` function:

``````
def generate_private_key(regex, version \\ <<0x00>>)
end
``````

Our `generate_private_key/2` function expects a `regex` which represents the pattern we’re trying to find in a vanity address (like `~r/^1pete/`), and a `version` byte that will used to indicate where this Bitcoin address will be used.

Within our `generate_private_key/2` function, we’ll kick off the mining process by generating a random private key and transforming it into a public address:

``````
private_key = PrivateKey.generate
``````

If the `public_address` we generated matches the pattern we provided in our `regex`, we’ve successfully mined a vanity address! In that case, we’ll return the `private_key`. Otherwise, we’ll repeat the entire process with a recursive call to `generate_private_key/2`:

``````
true -> private_key
false -> generate_private_key(regex, version)
end
``````

That’s all there is to it.

We can use our new `generate_private_key/2` function in conjunction with the `PrivateKey.to_public_address/2` function we built last time to view our newly mined vanity key:

``````
``````

Congratulations; we’re miners!

## Thinking in Parallel

The problem with our simple implementation of `generate_private_key/2` is that it’s slow.

While it’s true that the mining algorithm is inherently slow, there are many optimizations we could make to the code we’ve written. The most obvious improvement that comes to mind when using a “process-oriented” programming language like Elixir is to parallelize the mining algorithm across multiple processes.

However, parallelizing our mining algorithm presents an interesting set of challenges.

Each individual call to `generate_private_key/2` is completely synchronous and sequential. We won’t see much of a benefit by queuing up multiple concurrent calls to `generate_private_key/2` on the same CPU core. That said, while we’re running `generate_private_key/2` within a single process bound to a single CPU core, any other cores available to us are sitting idle.

Ideally, we could simultaneously run as many instances of our `generate_private_key/2` execution as we have cores. The moment any of our parallel executions find a matching key, it would be returned to the caller.

## Creating a Stream of Parallel Tasks

Elixir’s little known (to me) `Task.async_stream/3` function is the tool we need to implement this functionality.

`Task.async_stream/3` expects an enumerable as its first argument and a function to be applied concurrently to each element in the enumerable. Each element in the enumerable will have the provided function applied to it in a new process.

If we squint our eyes a little, we can see that this gives us what we need. The “enumerable” we pass into `Task.async_stream/3` will really be an infinite stream of zero-argument anonymous functions. Each of those anonymous functions simply calls `generate_private_key/2`.

We’ll use `Stream.cycle/2` to create an infinite stream of these functions:

``````
[fn -> generate_private_key(regex, version) end]
|> Stream.cycle
``````

The function that we want to run in parallel simply executes each of those passed in anonymous functions, one at a time, each in its own process:

``````
|> Task.async_stream(fn f -> f.() end)
``````

This is where our parallelization happens. Each call to `generate_private_key/2` is happening in a new process, and Elixir’s scheduler will spread each new process out over the available cores in the system.

By default, `Task.async_stream/3` will run up to `System.schedulers_online/0` parallel instances of our `generate_private_key/2` execution, and `System.schedulers_online/0` defaults to the number of available CPU cores in the system. This means we’ll always have one instance of `generate_private_key/2` running on each of our cores.

Perfect!

## Filtering Our Stream

`Task.async_stream/3` returns a stream that produces either an `{:ok, value}` tuple on success, or an `{:exit, reason}` tuple on failure. We don’t anticipate or care about failures in this situation, so we’ll `nil` them out with `Stream.map/2`:

``````
|> Stream.map(fn
{:ok, thing} -> thing
_ -> nil
end)
``````

Now we can use `Stream.reject/2` to filter out any `nil` values from our mapped stream:

``````
|> Stream.reject(&(&1 == nil))
``````

Let’s wrap what we’ve done in a function called `stream_private_keys/2` that accepts a `regex` and a `version`:

``````
def stream_private_keys(regex, version \\ <<0x00>>) do
[fn -> generate_private_key(regex, version) end]
|> Stream.cycle
|> Task.async_stream(fn f -> f.() end)
|> Stream.map(fn
{:ok, thing} -> thing
_ -> nil
end)
|> Stream.reject(&(&1 == nil))
end
``````

What we’re left with is a stream that will produce any number of valid Bitcoin vanity addresses for a given `regex` and `version`, using all of the available CPU cores on our system.

## Putting Our Stream to Use

Our stream doesn’t actually do anything until we try to pull values out of it using a function from the `Enum` module. Let’s use `Enum.take/2` to pull out three vanity Bitcoin addresses that match our desired pattern (`123`):

``````
|> Enum.take(3)
``````
``````
["123avbA76Zk98jik3ymTHkjbjKKftAhJiZ",
"123aGknGk5F2NPkB6e4e6pehVGL7gBR8az",
"123hzDB1CxcyDwusfsb8Pfh3Ti2i4NQLGR"]
``````

If we take a look at our CPU usage while our mining pipeline is chugging away, we’ll see that all of the CPUs on our machine are being fully utilized.

Success!

## Final Thoughts

Spoiler alert: the process of mining for Bitcoin is nearly identical to mining for vanity addresses. Instead of hashing private keys and looking for a random leading string like `1pete`, Bitcoin miners hash transaction data, looking for hashes that begin with some number of leading zeros corresponding to the current block difficulty.

There’s a huge amount of pomp and circumstance around the term “mining”, but at its core, it’s an incredibly simple and approachable idea.

Be sure to check out the `VanityAddress` module in my `hello_bitcoin` project on Github, and if this kind of thing is at all interesting to you, I highly recommend you pick up a copy of Andreas Antonopoulos’ Mastering Bitcoin.

Every object in Javascript is built on top of a “prototype”. A prototype can either be either another object, or `null`. When an object’s prototype is another object, the first object can inherit fields from the second.

This type of prototypal inheritance is well-accepted and relatively well understood by most Javascript developers, but there are dangerous implications behind this kind of inheritance model.

Let’s dive into how we can hack prototypal inheritance for fun and profit!

## How are Prototypes Created?

A Javascript object’s prototype is referenced through the hidden `__proto__` field. This field can be found on every object in an application. The `__proto__` field can either point to another object, or `null` if the current object has no prototype.

The two options for an object's prototype.

The prototype of an object can explicitly be set using `Object.create`, and passing in your desired prototype.

``````
let p = { foo: 123 };
let a = Object.create(p);
let b = Object.create(null);
``````

In this example, our new `a` object inherits the `foo` field from the `p` object being used as its prototype. Our new `b` object has no prototype, and inherits no fields.

Our two new objects and their prototype chains.

The prototype of an object can also be manually set through the `__proto__` field:

``````
let c = {};
c.__proto__ = { bar: 234 };
``````

In this case, we replace the reference to `c`’s original prototype with a reference to a new object. We can now access the inherited `bar` field through `c`.

It's objects all the way down.

By default, all Javascript objects created through the literal notion point to `Object.prototype` as their prototype. `Object.prototype` is an object that holds helper functions like `constructor`, `hasOwnProperty`, and `toString`. Additionally, `Object.prototype` has a prototype of `null`.

This means that in addition to the `bar` field, our `c` object also has access to everything living in `Object.prototype` via its prototype’s prototype!

## Setting the Scene

Armed with this information, let’s think about how we can exploit a simple (read: contrived) Node.js application.

Let’s assume that we’re building an application using an Express-like framework. We’ve created one endpoint to update values in an in-memory key-value store:

``````
const store = {
cats: "rule",
dogs: "drool"
};

app.post('/update/:key/:value', function(req, res) {
let { key, value } = req.params;
res.send(_.set(store, key, value));
});
``````

The `/update` route is used to update our `store` with various facts. This route is unauthorized as its intended to be used by unauthenticated clients.

We have another route, `/restricted`, that’s only intended to be used by authenticated, authorized users:

``````
app.post('/restricted', function(req, res) {
let user = getUser(req);
throw new Error("Not authorized!");
}
res.send("Permission granted!");
});
``````

Let’s assume that the `getUser` function returns a user object based on a session token provided through `req`. Let’s also assume that the `isAdmin` field is set to `true` on administrator user objects, and unset on non-administrator user objects.

## Hacking the Prototype

Now that the scene is set, imagine that we’re a normal, non-administrator, user of this application, and we want access to the `/restricted` endpoint.

Our calls to `/restricted` return a `"Not authorized!"` exception because our user object returned by `getUser` doesn’t have an `isAdmin` field. With no way of updating our admin flag, it seems we’re stuck.

Or are we?

Thankfully, our recent reading on prototypal inheritance has given us a flash of malevolent insight!

The `/update` endpoint is using Lodash’s `_.set` function to update the value of any field in our `store`, including nested fields. We can use this to our advantage. We quickly make a call to `/update` with a `key` of `"__proto__.isAdmin"`, and a `value` of `"true"` (or any other truthy value), and try our restricted endpoint again:

``````
Permission granted!
``````

Victory! We’ve given ourself access to a restricted endpoint by modifying an arbitrary object within our Javascript application!

But how did we do it?

## Explaining the Magic

As we mentioned earlier, unless specifically created with a different prototype, all objects reference `Object.prototype` as their prototype. More specifically, all objects in an application share the same reference to the same instance of `Object.prototype` in memory.

If we can modify `Object.prototype`, we can effectively modify the fields inherited by all of the objects in our application.

Our request to the `/update` endpoint, with a `key` of `"__proto__.isAdmin"`, and a `value` of `"true"` effectively turned into this expression on our server:

``````
``````

This expression reaches into `Object.prototype` through the `__proto__` field of our `store` and creates a new `isAdmin` field on that object with a value of `"true"`. This change has far reaching consequences.

After we update our “store”, every object that exists in our application now inherits an `isAdmin` field with a value of `"true"`. This means that on retrieving our user object from `getUser`, it looks something like this:

``````
{
_id: 123,
name: 'Pete',
__proto__: {
constructor: ...,
hasOwnProperty: ...,
toString: ...,
...
__proto__: null
}
}
``````

Because our base user object has no `isAdmin` field, trying to access `isAdmin` on this object results in the `isAdmin` field from our underlying `Object.prototype` object to be returned. `Object.prototype` returns a value of `"true"`, causing our server’s permission check to pass, and giving us access to juicy, restricted functionality.

## In Reality

Obviously, this a fairly contrived example. In the real world, this type of vulnerability wouldn’t present itself in such a simple way. That said, this vulnerability does exist in the real world. When it rears its head, it’s often incredibly ugly. Adding unexpected fields to every object in your system can lead to disastrous results.

For example, imagine a vulnerability like this existing in a Meteor application. Once the underlying `Object.prototype` is updated with superfluous fields, our entire applications falls to pieces. Any queries made against our MongoDB collections fail catastrophically:

``````Exception while invoking method 'restricted' MongoError:
Failed to parse: {
find: "users",
filter: {
_id: "NktioYhaJMuKhbWQw",
},
limit: 1,
``````

MongoDB fails to parse our query object with the added `isAdmin` fields, and throws an exception. Without being able to query our database, our application is dead in the water.

## Fixing the Vulnerability & Final Thoughts

The fundamental fix for this issue is incredibly simple. Don’t trust user-provided data.

If a user is allowed to update a field on an object (or especially a nested field in an object), always whitelist the specific fields they’re allowed to touch. Never use user-provided data in a way that can deeply modify an object (any object) on the server.

If you’re interested in this kind of thing, I encourage you to check out my latest project, Secure Meteor! It’s an in-the-works guide designed to help you secure your past, present, and future Meteor applications. As a token of thanks for signing up, I’ll also send you a free Meteor security checklist!

Lately I’ve been working my way through Mastering Bitcoin, implementing as many of the examples in the book in Elixir as I can.

I’ve been amazed at how well Elixir has fared with implementing the algorithms involved in working with Bitcoin keys and addresses. Elixir ships with all the tools required to generate a cryptographically secure private key and transform it into a public address string.

Let’s walk through the process step by step and build our our own Elixir module to generate private keys and public addresses.

## What are Private Keys and Public Addresses?

A Bitcoin private key is really just a random two hundred fifty six bit number. As the name implies, this number is intended to be kept private.

From each private key, a public-facing Bitcoin address can be generated. Bitcoin can be sent to this public address by anyone in the world. However, only the keeper of the private key can produce a signature that allows them to access the Bitcoin stored there.

Let’s use Elixir to generate a cryptographically secure private key and then generate its most basic corresponding public address so we can receive some Bitcoin!

## Pulling a Private Key Out of Thin Air

As I mentioned earlier, a Bitcoin private key is really just a random two hundred and fifty six bit number. In other words, a private key can be any number between `0` and `2^256`.

However, not all random numbers are created equally. We need to be sure that we’re generating our random number from a cryptographically secure source of entropy. Thankfully, Elixir exposes Erlang’s `:crypto.strong_rand_bytes/1` function which lets us easily generate a list of truly random bytes.

Let’s use `:crypto.strong_rand_bytes/1` as the basis for our private key generator. We’ll start by creating a new `PrivateKey` module and a `generate/0` function that takes no arguments:

``````
defmodule PrivateKey do
def generate
end
``````

Inside our `generate/0` function, we’ll request `32` random bytes (or `256` bits) from `:crypto.strong_rand_bytes/1`:

``````
def generate do
:crypto.strong_rand_bytes(32)
end
``````

This gives us a random set of `32` bytes that, when viewed as an unsigned integer, ranges between `0` and `2^256 - 1`.

Unfortunately, we’re not quite done.

## Validating our Private Key

To ensure that our private key is difficult to guess, the Standards for Efficient Cryptography Group recommends that we pick a private key between the number `1` and a number slightly smaller than `1.158e77`:

An excerpt of the SECG guidelines.

We can add this validation check fairly easily by adding the SECG-provided upper bound as an attribute to our `PrivateKey` module:

``````
@n :binary.decode_unsigned(<<
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE,
0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,
0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41
>>)
``````

Next, we’ll add a `valid?/1` function to our module that returns `true` if the provided secret key falls within this range, and `false` if it does not:

``````
defp valid?(key) when key > 1 and key < @n, do: true
defp valid?(_), do: false
``````

Before we pass our private key into our `valid?/1` function, we’ll need to convert it from a thirty two byte binary into an unsigned integer. Let’s add a third `valid?/1` function head that does just that:

``````
defp valid?(key) when is_binary(key) do
key
|> :binary.decode_unsigned
|> valid?
end
``````

We’ll finish off our validation by passing our generated private key into our new `valid?/1` function. If the key is valid, we’ll return it. Otherwise, we’ll generate a new private key and try again:

``````
def generate do
private_key = :crypto.strong_rand_bytes(32)
case valid?(private_key) do
true  -> private_key
false -> generate
end
end
``````

Now we can call `PrivateKey.generate` to generate a new Bitcoin private key!

## From Private Key to Public Key …

The most basic process for turning a Bitcoin private key into a sharable public address involves three basic steps. The first step is to transform our private key into a public key with the help of elliptic curve cryptography.

We’ll start by adding a new `to_public_key/1` function to our `PrivateKey` module:

``````
def to_public_key(private_key)
``````

In our `to_public_key/1` function, we’ll use Erlang’s `:crypto.generate_key` function to sign our `private_key` using an elliptic curve. We’ll specifically use the `:secp256k1` curve:

``````
:crypto.generate_key(:ecdh, :crypto.ec_curve(:secp256k1), private_key)
``````

We’re using the elliptic curve key generation as a trapdoor function to ensure our private key’s secrecy. It’s easy for us to generate our public key from our private key, but reversing the computation and generating our private key from our public key is nearly impossible.

The `:crypto.generate_key` function returns a two-element tuple. The first element in this tuple is our Bitcoin public key. We’ll pull it out using Elixir’s `elem/1` function:

``````
:crypto.generate_key(:ecdh, :crypto.ec_curve(:secp256k1), private_key)
|> elem(0)
``````

The returned value is a sixty five byte binary representing our public key!

## … Public Key to Public Hash …

Once we have our public key in memory, our next step in transforming it into a public address is to hash it. This gives us what’s called the “public hash” of our public key.

Let’s make a new function, `to_public_hash/1` that takes our `private_key` as an argument:

``````
def to_public_hash(private_key)
``````

We’ll start the hashing process by turning our `private_key` into a public key with a call to `to_public_key`:

``````
private_key
|> to_public_key
``````

Next, we pipe our public key through two hashing functions: SHA-256, followed by RIPEMD-160:

``````
private_key
|> to_public_key
|> hash(:sha256)
|> hash(:ripemd160)
``````

Bitcoin uses the RIPEMD-160 hashing algorithm because it produces a short hash. The intermediate SHA-256 hashing is used to prevent insecurities through unexpected interactions between our elliptic curve signing algorithm and the RIPEMD algorithm.

In this example, `hash/1` is a helper function that wraps Erlang’s `:crypto.hash`.

``````
defp hash(data, algorithm), do: :crypto.hash(algorithm, data)
``````

Flipping the arguments to `:crypto.hash` in this way lets us easily pipe our data through the `hash/1` helper.

## … And Public Hash to Public Address

Lastly, we can convert our public hash into a full-fledged Bitcoin address by Base58Check encoding the hash with a version byte corresponding to the network where we’re using the address.

Let’s add a `to_public_address/2` function to our `PrivateKey` module:

``````
``````

The `to_public_address/2` function takes a `private_key` and a `version` byte as its arguments. The `version` defaults to `<<0x00>>`, indicating that this address will be used on the live Bitcoin network.

To create a Bitcoin address, we start by converting our `private_key` into a public hash with a call to `to_public_hash/1`:

``````
private_key
|> to_public_hash
``````

All that’s left to do is Base58Check encode the resulting hash with the provided `version` byte:

``````
private_key
|> to_public_hash
|> Base58Check.encode(version)
``````

After laying the groundwork, the final pieces of the puzzle effortlessly fall into place.

## Putting Our Creation to Use

Now that we can generate cryptographically secure private keys and transform them into publishable public addresses, we’re in business.

Literally!

Let’s generate a new private key, transform it into its corresponding public address, and try out on the Bitcoin testnet. We’ll start by generating our private key:

``````
private_key = PrivateKey.generate
``````

This gives us a thirty two byte binary. If we wanted, we could Base58Check encode this with a testnet `version` byte of `0xEF`. This is known as the “Wallet Import Format”, or WIF, of our Bitcoin private key:

``````
Base58Check.encode(private_key, <<0xEF>>)
``````

As its name suggests, converting our private key into a WIF allows us to easily import it into most Bitcoin wallet software:

Importing our test private key.

Next, let’s convert our private key into a testnet public address using a `version` byte of `0x6F`:

``````
``````

Now that we have our public address, let’s find a testnet faucet and send a few tBTC to our newly generated address! After initiating the transaction with our faucet, we should see our Bitcoin arrive at our address on either a blockchain explorer, or within our wallet software.

Our tBTC has arrived.

Victory!

## Final Thoughts

Elixir, thanks to its Erlang heritage, ships with a wealth of tools that make this kind of hashing, signing, and byte mashing a walk in the park.

I encourage you to check our the `PrivateKey` module on Github to get a better feel for the simplicity of the code we wrote today. Overall, I’m very happy with the result.

If you enjoyed this article, I highly recommend you check out the Mastering Bitcoin book. If you really enjoyed this article, feel free to send a few Bitcoin to this address I generated using our new `PrivateKey` module:

``````
1HKz4XU7ENT46ztEzsT83jRezyiDjvnBV8
``````

Stay tuned for more Bitcoin-related content as I work my way through Mastering Bitcoin!