Bounty Hunting with Elixir

Does 'crypto bounty hunter' sound like your dream job title? Yes? Same here! And I've got good news for both of us.

Futurist crypto blog 1729 offers Bitcoin bounties for learning code, design, and content creation.

I've been following the project for the past few weeks and was pleased to find them in my inbox the other day, where they offered up a challenge in the Elixir programming language. Solve three Elixir problems in Exercism.io, they said, and you might win $100 in BTC.

Parallel Cores, Engage!

Elixir is a functional programming language that excels at concurrent processing (i.e., handling many operations at once). The "free lunch is over," they say, and in the near future it will only be languages capable of concurrency that will fully take advantage of the advances in processor speed. As computer scientist Herb Sutter has written,

applications will increasingly need to be concurrent if they want to fully exploit CPU throughput gains.

For its ability to run concurrent code, and its speed in handling massive computations, Elixir is a great choice for a budding crypto developer.

Discord uses Elixir to handle billions of messages on their backend. When Bleacher Report migrated, they moved from 150 Ruby-on-Rails servers to just 5 Elixir servers. You can read more evidence of Elixir's magic here.

I didn't know anything about the language when I started, but I'm
excited to learn more. Maybe my next project will be a Twitter clone, or perhaps a custom Elixir blockchain.

In this post I'm going to walk through the three challenges I completed for the 1729 bounty: a simple DateTime challenge, the Diffie-Hellman crypto algorithm, and a parallel-processed letter frequency calculator.

Installing Elixir and Exercism

If you're unaware, Exercism is an incredible platform for learning code. As a self-taught developer, I'm used to simply taking notes on Youtube videos (mostly by the King, Brad Traversy). I then build my own test projects out of what I've learned. Most challenge-based apps cost money and seem to limit this project-based self-pacing. I usually avoid them.

Exercism is different. In addition to being free, each Exercism module is supervised by a set of mentors who offer feedback on your code. There's an incredible diversity of languages to learn-- I think I'll finally get around to learning Python next.

Instructions for installing Elixir can be found here. As a Windows user, Chocolately is my go-to: cinst elixir and we were off to the races.

Setting up the Exercism CLI is as simple as following these instructions.

To get acquainted with the basics of the language, I recommend these free resources.

Gigasecond Challenge

The first 1729 challenge was to write a function that would add a billion seconds to a given date.

We were given two tuples containing Date and Time information, respectively. After poking around a bit and attempting to manually convert the integer, I had my first encounter with Elixir's useful in-house functions. The DateTime module contains an add function. It was easy as passing a billion as the add parameter and reformatting the tuple pair for the solution.

defmodule Gigasecond do
  @doc """
  Calculate a date one billion seconds after an input date.
  """
  @spec from({{pos_integer, pos_integer, pos_integer}, {pos_integer, pos_integer, pos_integer}}) ::
          :calendar.datetime()

  def from({{year, month, day}, {hours, minutes, seconds}}) do
  # piecing the incoming tuples together to get a DateTime object
  gd = elem(Date.new(year,month,day), 1)
  gt = elem(Time.new(hours,minutes,seconds),1)
  gdt = elem(DateTime.new(gd,gt),1)
  # using the DateTime add method
  gigatime = DateTime.add(gdt, 1000000000)
  # formatting the gigatime into tuple pair
  {{gigatime.year, gigatime.month, gigatime.day}, {gigatime.hour, gigatime.minute, gigatime.second}}
  end
end

Diffie-Hellman Key Exchange

After that encouraging warm-up, we moved into trickier territory. For the next challenge we needed to implement popular cryptography algorithm Diffie-Hellman in Elixir. Not knowing anything about DH, I started by studying the algorithm and making sure I understood the math of it. Computerphile came to the rescue, as did this Diffie-Hellman calculator.

Protip: Invest in a whiteboard.

After being certain of how the algo worked, the solution was only three in-built Elixir/Erlang modules away.

defmodule DiffieHellman do
  @moduledoc """
  Diffie-Hellman is a method of securely exchanging keys in a public-key
  cryptosystem.
  """

  @doc """
  Given a prime integer `prime_p`, return a random integer between 1 and `prime_p` - 1
  """
  @spec generate_private_key(prime_p :: integer) :: integer
  def generate_private_key(prime_p) do
  :crypto.rand_uniform(1, prime_p - 1)
  end

  @doc """
  Given two prime integers as generators (`prime_p` and `prime_g`), and a private key,
  generate a public key using the mathematical formula:

  (prime_g **  private_key) % prime_p
  """
  @spec generate_public_key(prime_p :: integer, prime_g :: integer, private_key :: integer) ::
          integer
  def generate_public_key(prime_p, prime_g, private_key) do
    :binary.decode_unsigned(:crypto.mod_pow(prime_g, private_key, prime_p))
  end

  @doc """
  Given a prime integer `prime_p`, user B's public key, and user A's private key,
  generate a shared secret using the mathematical formula:

  (public_key_b ** private_key_a) % prime_p
  """
  @spec generate_shared_secret(
          prime_p :: integer,
          public_key_b :: integer,
          private_key_a :: integer
        ) :: integer
  def generate_shared_secret(prime_p, public_key_b, private_key_a) do
    # secret they share is g^a*b mod p
    # public key b is the result of the preceding function for user b
    # pub_key_a ^ priv_key_a % prime_p independently verified in iex, so i know this works :)
    :binary.decode_unsigned(:crypto.mod_pow(public_key_b, private_key_a, prime_p))


  end
end

Parallel Letter Frequency

The final challenge was far-and-away the hardest. Given a list of strings--some in German, some in Dutch, some in English-- calculate the letter frequencies in each string concurrently, then combine them all into a single map.

The special German and Dutch characters highlighted a strength of Elixir, which is that its strings are read as low-level binaries. You can easily convert strings into their corresponding integers in binary or Unicode (though if your computer stumbles on rendering special characters ::cough Powershell:: it can be frustrating!)

I spent a solid day writing a program that:

• lowercased each string and removed numbers, punctuation, and spaces
• reduced each string to a list of its unique characters
• counted the occurrence of each unique character in the total list of graphemes
• processed each string concurrently using an async stream
• formatted the result and repeated the same workflow for the total list

Then this morning I found out I didn't need to do a whole lot of that, as Elixir has an in-built function for calculating letter frequencies! Oof.

Enum.frequency() allowed me to drastically simplify my code.

The Task module is similar to async/await in Javascript. The code below creates a "stream" of code waiting to be executed, then runs said code in parallel when the function is passed to an enumerator. That may sound complex, but after grokking a little Elixir, I believe you will find it simple! Simpler, in any case, than hacking through Promises in Javascript.

My refactored solution is below. Note the gorgeously simple method used to reduce all enumerated string-counters at the bottom. List.foldl compresses all items in a list according to an accumulator (the empty map) and a function (the similarly-elegant Map.merge function).

defmodule Frequency do
  @doc """
  Count letter frequency in parallel.

  Returns a map of characters to frequencies.

  """
  @spec frequency([String.t()], pos_integer) :: map
  def frequency(texts, workers) do

# first create a stream that will process each text in parallel
stream = Task.async_stream(texts, fn txt -> 
  if txt != nil do
    # convert each formatted text to graphemes
    grp = String.graphemes(
      String.downcase(String.replace(txt, ~r/[1234567890!#$%&()*+,.:;<=>?@\^_`{|}~-]/, ""))
    )
    # filter out empty spaces and count the frequencies 
     Enum.filter(grp, fn x -> x != " " end) |> Enum.frequencies()
  else %{} end
end, max_concurrency: workers)

# remove :ok atom from result and run all processes
total = Enum.map(stream, fn x -> elem(x,1) end)
# reduce all maps in total list by merging
List.foldl(total, %{}, fn x, a -> Map.merge(x, a, fn _k, v1, v2 ->
  v1 + v2
end)
end)
end
end

Lessons learned!

I may not win the prize, as others may have solved these challenges in simpler, more efficient ways. But I'm happy I took the time to figure out some Elixir. This is the second programming language I've learned (after Javascript), and it gives me a great deal of confidence moving forward.

The life of a bounty hunter is feast or famine, after all. Us Mandalorians must accept our fates, acquire our targets, and go where the bounties lead. Win or lose, we can accept that every hunt that does not kill us makes us stronger.

If you want to check out more of my adventures, swing by my website. Til next time!

Comments

[Joe Holmes]

Update: I won one of the prizes. Highly recommend getting paid in BTC by high-profile clients for teaching yourself things. It feels really, really, really good.