Skip to content

Instantly share code, notes, and snippets.

@CodesInChaos
Created July 25, 2012 12:43
Show Gist options
  • Save CodesInChaos/3175971 to your computer and use it in GitHub Desktop.
Save CodesInChaos/3175971 to your computer and use it in GitHub Desktop.
Base58 encoding in C# (Used for BitCoin addresses)
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);
}
}
}
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;
}
}
}
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));
}
}
}
@CodesInChaos
Copy link
Author

Code isn't optimized for performance
I put this code into the public domain

@rostcheck
Copy link

Thanks for this; I found it super helpful!

@dotnetchris
Copy link

dotnetchris commented Aug 25, 2016

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment