Recently, we wrote a Base58Check encoder to power our Bitcoin private key and public address generator. Being the diligent developers that we are, we added a unit test to ensure that our encoder was working as we expected.

But was that enough?

Call me a coward, but relying on a solitary unit test based on a single example pulled from a wiki article doesn’t instill huge amounts of confidence in our solution.

Let’s thoroughly test our solution with the help of property-based testing tools and an external oracle!

Oracles and Property Testing

The Base58Check encoding algorithm has been implemented many times by many different developers. Wouldn’t it be great if we could automatically check our implementation against theirs?

We can!

In property-based testing vernacular, this is known as using an oracle. An oracle is another implementation of your solution that is known to be correct under some domain of inputs.

Thankfully, we have a perfect oracle in the form of the Bitcoin Explorer’s CLI tools. Bitcoin Explorer ships with a base58check-encode utility that Base58Check encodes any Base16 string with a given version byte:

> bx base58check-encode abc123 --version 0
17WWM7GLKg9

Given this oracle, we can thoroughly and concisely test our implementation with a single property. The primary desired property of our solution is that it should match the output of bx base58check-encode for all valid inputs.

Getting Comfortable with our Tools

Property testing is simple in concept, but more difficult in practice.

It’s easy to say that for any given binary and any given byte, the output of our solution should match the output of my oracle. Actually generating those inputs and coordinating those test executions is a whole different ball game.

Thankfully, the groundwork has already been laid for us, and there are plenty of Elixir-based property testing tools for us to chose from. For this exercise, let’s use StreamData.

---

To get our feet wet, let’s write a simple property test using StreamData that verifies the associative property of the Kernel.+/2 addition function:

property "addition is associative" do
  check all a <- integer(),
            b <- integer(),
            c <- integer() do
    l = Kernel.+(Kernel.+(a, b), c)
    r = Kernel.+(a, Kernel.+(b, c))
    assert l == r
  end
end

The property keyword defines our new property test with a short description of the property under test.

The check all block lets us define our automatically generated inputs and a function block that will use those inputs to make assertions about our property.

Put simply, we’re telling StreamData that we want three random integers: a, b, and c. For every set of a, b, and c, we want to verify that (a + b) + c equals a + (b + c).

StreamData does this by generating many (one hundred by default) random sets of a, b, and c and checking them against our assertions. If any assertion fails, StreamData will try to “shrink” the input set (a, b, and c, in this case) to the simplest possible failing test case and present it to us.

> mix test
.

Finished in 0.06 seconds
1 property, 0 failures

Thankfully, addition is associative, and our test passes!

I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, nothing shows your support more than signing up for my mailing list.

Consulting the Oracle

Now let’s take the training wheels off and write a property test for our Base58Check encoder against our external oracle.

First, we’ll define a new test block:

property "gives the same results as bx base58check-encode" do
end

Within our test, we’ll generate two random variables, key and version:

check all key <- binary(min_length: 1),
          version <- byte() do
end

We’re telling StreamData that key can be any non-empty binary, and that version can be any byte.

Now that we have our set of test data, we’ll need to get the result of encoding key with version using our own implementation of the Base58Check encoding algorithm:

result = Base58Check.encode(key, <<version>>)

Next, we’ll use Elixir’s System.cmd to call bx base58check-encode, passing in our Base16-encoded key string and our version byte:

oracle =
  System.cmd("bx", [
    "base58check-encode",
    Base.encode16(key),
    "--version",
    "#{version}"
  ])
  |> elem(0)
  |> String.trim()

Now all that’s left to do is to verify that our result matches the output of our oracle:

assert result == oracle

If StreamData detects any failures in this assertion, it will simplify key and version to the simplest failing case and report the failure to us.

But thankfully, our implementation of the Base58Check encoding algorithm passes the test:

mix test
.

Finished in 1.0 seconds
1 property, 0 failures

Final Thoughts

I won’t pretend to be a property testing expert. I’m just a guy who’s read a few articles and who’s hopped on board the hype train. That said, property testing was the perfect tool for this job, and I can see it being an incredibly useful tool in the future. I’m excited to incorporate it into my testing arsenal.

If you’re interested in property-based testing, I recommend you check out Fred Hebert’s PropEr Testing, and Hillel Wayne’s articles on hypothesis testing with oracle functions and property testing with contracts.

Lastly, if you’re interested in Bitcoin development, I encourage you to check out Andreas Antonopoulos’ Mastering Bitcoin.