Created
July 25, 2012 12:43
-
-
Save CodesInChaos/3175971 to your computer and use it in GitHub Desktop.
Base58 encoding in C# (Used for BitCoin addresses)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Code isn't optimized for performance
I put this code into the public domain