Base58 encoding in C# (Used for BitCoin addresses)

ArrayHelpers.cs

using System;
using System.Diagnostics.Contracts;
using System.Linq;

namespace Merkator.Tools
{
	public class ArrayHelpers
	{
		public static T[] ConcatArrays<T>(params T[][] arrays)
		{
			Contract.Requires(arrays != null);
			Contract.Requires(Contract.ForAll(arrays, (arr) => arr != null));
			Contract.Ensures(Contract.Result<T[]>() != null);
			Contract.Ensures(Contract.Result<T[]>().Length == arrays.Sum(arr => arr.Length));

			var result = new T[arrays.Sum(arr => arr.Length)];
			int offset = 0;
			for (int i = 0; i < arrays.Length; i++)
			{
				var arr = arrays[i];
				Buffer.BlockCopy(arr, 0, result, offset, arr.Length);
				offset += arr.Length;
			}
			return result;
		}

		public static T[] ConcatArrays<T>(T[] arr1, T[] arr2)
		{
			Contract.Requires(arr1 != null);
			Contract.Requires(arr2 != null);
			Contract.Ensures(Contract.Result<T[]>() != null);
			Contract.Ensures(Contract.Result<T[]>().Length == arr1.Length + arr2.Length);

			var result = new T[arr1.Length + arr2.Length];
			Buffer.BlockCopy(arr1, 0, result, 0, arr1.Length);
			Buffer.BlockCopy(arr2, 0, result, arr1.Length, arr2.Length);
			return result;
		}

		public static T[] SubArray<T>(T[] arr, int start, int length)
		{
			Contract.Requires(arr != null);
			Contract.Requires(start >= 0);
			Contract.Requires(length >= 0);
			Contract.Requires(start + length <= arr.Length);
			Contract.Ensures(Contract.Result<T[]>() != null);
			Contract.Ensures(Contract.Result<T[]>().Length == length);

			var result = new T[length];
			Buffer.BlockCopy(arr, start, result, 0, length);
			return result;
		}

		public static T[] SubArray<T>(T[] arr, int start)
		{
			Contract.Requires(arr != null);
			Contract.Requires(start >= 0);
			Contract.Requires(start <= arr.Length);
			Contract.Ensures(Contract.Result<T[]>() != null);
			Contract.Ensures(Contract.Result<T[]>().Length == arr.Length - start);

			return SubArray(arr, start, arr.Length - start);
		}
	}
}

Base58Encoding.cs

using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
using Merkator.Tools;

namespace Merkator.BitCoin
{
	// Implements https://en.bitcoin.it/wiki/Base58Check_encoding
	public static class Base58Encoding
	{
		public const int CheckSumSizeInBytes = 4;

		public static byte[] AddCheckSum(byte[] data)
		{
			Contract.Requires<ArgumentNullException>(data != null);
			Contract.Ensures(Contract.Result<byte[]>().Length == data.Length + CheckSumSizeInBytes);
			byte[] checkSum = GetCheckSum(data);
			byte[] dataWithCheckSum = ArrayHelpers.ConcatArrays(data, checkSum);
			return dataWithCheckSum;
		}

		//Returns null if the checksum is invalid
		public static byte[] VerifyAndRemoveCheckSum(byte[] data)
		{
			Contract.Requires<ArgumentNullException>(data != null);
			Contract.Ensures(Contract.Result<byte[]>() == null || Contract.Result<byte[]>().Length + CheckSumSizeInBytes == data.Length);
			byte[] result = ArrayHelpers.SubArray(data, 0, data.Length - CheckSumSizeInBytes);
			byte[] givenCheckSum = ArrayHelpers.SubArray(data, data.Length - CheckSumSizeInBytes);
			byte[] correctCheckSum = GetCheckSum(result);
			if (givenCheckSum.SequenceEqual(correctCheckSum))
				return result;
			else
				return null;
		}

		private const string Digits = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

		public static string Encode(byte[] data)
		{
			Contract.Requires<ArgumentNullException>(data != null);
			Contract.Ensures(Contract.Result<string>() != null);

			// Decode byte[] to BigInteger
			BigInteger intData = 0;
			for (int i = 0; i < data.Length; i++)
			{
				intData = intData * 256 + data[i];
			}

			// Encode BigInteger to Base58 string
			string result = "";
			while (intData > 0)
			{
				int remainder = (int)(intData % 58);
				intData /= 58;
				result = Digits[remainder] + result;
			}

			// Append `1` for each leading 0 byte
			for (int i = 0; i < data.Length && data[i] == 0; i++)
			{
				result = '1' + result;
			}
			return result;
		}

		public static string EncodeWithCheckSum(byte[] data)
		{
			Contract.Requires<ArgumentNullException>(data != null);
			Contract.Ensures(Contract.Result<string>() != null);
			return Encode(AddCheckSum(data));
		}

		public static byte[] Decode(string s)
		{
			Contract.Requires<ArgumentNullException>(s != null);
			Contract.Ensures(Contract.Result<byte[]>() != null);

			// Decode Base58 string to BigInteger 
			BigInteger intData = 0;
			for (int i = 0; i < s.Length; i++)
			{
				int digit = Digits.IndexOf(s[i]); //Slow
				if (digit < 0)
					throw new FormatException(string.Format("Invalid Base58 character `{0}` at position {1}", s[i], i));
				intData = intData * 58 + digit;
			}

			// Encode BigInteger to byte[]
			// Leading zero bytes get encoded as leading `1` characters
			int leadingZeroCount = s.TakeWhile(c => c == '1').Count();
			var leadingZeros = Enumerable.Repeat((byte)0, leadingZeroCount);
			var bytesWithoutLeadingZeros =
				intData.ToByteArray()
				.Reverse()// to big endian
				.SkipWhile(b => b == 0);//strip sign byte
			var result = leadingZeros.Concat(bytesWithoutLeadingZeros).ToArray();
			return result;
		}

		// Throws `FormatException` if s is not a valid Base58 string, or the checksum is invalid
		public static byte[] DecodeWithCheckSum(string s)
		{
			Contract.Requires<ArgumentNullException>(s != null);
			Contract.Ensures(Contract.Result<byte[]>() != null);
			var dataWithCheckSum = Decode(s);
			var dataWithoutCheckSum = VerifyAndRemoveCheckSum(dataWithCheckSum);
			if (dataWithoutCheckSum == null)
				throw new FormatException("Base58 checksum is invalid");
			return dataWithoutCheckSum;
		}

		private static byte[] GetCheckSum(byte[] data)
		{
			Contract.Requires<ArgumentNullException>(data != null);
			Contract.Ensures(Contract.Result<byte[]>() != null);

			SHA256 sha256 = new SHA256Managed();
			byte[] hash1 = sha256.ComputeHash(data);
			byte[] hash2 = sha256.ComputeHash(hash1);

			var result = new byte[CheckSumSizeInBytes];
			Buffer.BlockCopy(hash2, 0, result, 0, result.Length);

			return result;
		}
	}
}

Base58EncodingTests.cs

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Merkator.BitCoin.Tests
{
	[TestClass]
	public class Base58EncodingTests
	{
		// Test cases from https://github.com/bitcoin/bitcoin/blob/master/src/test/base58_tests.cpp
		Tuple<string, byte[]>[] testCases = new Tuple<string, byte[]>[]{
			Tuple.Create("",new byte[]{}),
			Tuple.Create("1112",new byte[]{0x00, 0x00, 0x00, 0x01}),
			Tuple.Create("2g",new byte[]{0x61}),
			Tuple.Create("a3gV",new byte[]{0x62,0x62,0x62}),
			Tuple.Create("aPEr",new byte[]{0x63,0x63,0x63}),
			Tuple.Create("2cFupjhnEsSn59qHXstmK2ffpLv2",new byte[]{0x73,0x69,0x6d,0x70,0x6c,0x79,0x20,0x61,0x20,0x6c,0x6f,0x6e,0x67,0x20,0x73,0x74,0x72,0x69,0x6e,0x67}),
			Tuple.Create("1NS17iag9jJgTHD1VXjvLCEnZuQ3rJDE9L",new byte[]{0x00,0xeb,0x15,0x23,0x1d,0xfc,0xeb,0x60,0x92,0x58,0x86,0xb6,0x7d,0x06,0x52,0x99,0x92,0x59,0x15,0xae,0xb1,0x72,0xc0,0x66,0x47}),
			Tuple.Create("ABnLTmg",new byte[]{0x51,0x6b,0x6f,0xcd,0x0f}),
			Tuple.Create("3SEo3LWLoPntC",new byte[]{0xbf,0x4f,0x89,0x00,0x1e,0x67,0x02,0x74,0xdd}),
			Tuple.Create("3EFU7m",new byte[]{0x57,0x2e,0x47,0x94}),
			Tuple.Create("EJDM8drfXA6uyA",new byte[]{0xec,0xac,0x89,0xca,0xd9,0x39,0x23,0xc0,0x23,0x21}),
			Tuple.Create("Rt5zm",new byte[]{0x10,0xc8,0x51,0x1e}),
			Tuple.Create("1111111111",new byte[]{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00})
		};

		[TestMethod]
		public void Encode()
		{
			foreach (var tuple in testCases)
			{
				var bytes = tuple.Item2;
				var expectedText = tuple.Item1;
				var actualText = Base58Encoding.Encode(bytes);
				Assert.AreEqual(expectedText, actualText);
			}
		}

		[TestMethod]
		public void Decode()
		{
			foreach (var tuple in testCases)
			{
				var text = tuple.Item1;
				var expectedBytes = tuple.Item2;
				var actualBytes = Base58Encoding.Decode(text);
				Assert.AreEqual(BitConverter.ToString(expectedBytes), BitConverter.ToString(actualBytes));
			}
		}

		[TestMethod]
		[ExpectedException(typeof(FormatException))]
		public void DecodeInvalidChar()
		{
			Base58Encoding.Decode("ab0");
		}

		// Example address from https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
		byte[] addressBytes = new byte[] { 0x00, 0x01, 0x09, 0x66, 0x77, 0x60, 0x06, 0x95, 0x3D, 0x55, 0x67, 0x43, 0x9E, 0x5E, 0x39, 0xF8, 0x6A, 0x0D, 0x27, 0x3B, 0xEE };
		string addressText = "16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM";
		string brokenAddressText = "16UwLl9Risc3QfPqBUvKofHmBQ7wMtjvM";

		[TestMethod]
		public void EncodeBitcoinAddress()
		{
			var actualText = Base58Encoding.EncodeWithCheckSum(addressBytes);
			Assert.AreEqual(addressText, actualText);
		}

		[TestMethod]
		public void DecodeBitcoinAddress()
		{
			var actualBytes = Base58Encoding.DecodeWithCheckSum(addressText);
			Assert.AreEqual(BitConverter.ToString(addressBytes), BitConverter.ToString(actualBytes));
		}

		[TestMethod]
		[ExpectedException(typeof(FormatException))]
		public void DecodeBrokenBitcoinAddress()
		{
			var actualBytes = Base58Encoding.DecodeWithCheckSum(brokenAddressText);
			Assert.AreEqual(BitConverter.ToString(addressBytes), BitConverter.ToString(actualBytes));
		}
	}
}

Thanks for this; I found it super helpful!

Nice post, thanks for the public domain work. Something that's kind of neat is this is one of the rare places the LINQ Aggregate operator shines:

BigInteger intData = data.Aggregate<byte, BigInteger>(0, (current, @byte) => current*256 + @byte);

(I'm sure this lowers performance marginally, unbenchmarked)