Base58 Encoding and Decoding Tutorial

Key Concepts

• Alphabet: 58 characters, designed for readability and error prevention.
• Base58Check: Adds a version byte and checksum for integrity (e.g., Bitcoin addresses).
• Use Cases: Cryptocurrency addresses, private keys, and compact number representation.

Mathematical Foundation

Let N be the input number (non-negative integer).

Encoding: Repeatedly compute d = N mod 58, append the character at index d in the alphabet, and update N = N / 58. Reverse the result to match big-endian order.

Decoding: For a string S = c_1 c_2 ... c_n, compute N = sum(index(c_i) * 58^(n-i)).

Pseudo-Code: Encoding

FUNCTION encode_base58(number: BigInteger) -> String:
    IF number < 0 THEN ERROR "Input must be non-negative"
    alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    result = empty string
    WHILE number > 0:
        remainder = number % 58
        result = alphabet[remainder] + result
        number = number / 58
    RETURN result
END

                

Pseudo-Code: Decoding

FUNCTION decode_base58(base58: String) -> BigInteger:
    alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    value = 0
    FOR each character c in base58:
        index = position of c in alphabet
        IF index = -1 THEN ERROR "Invalid Base58 character"
        value = value * 58 + index
    RETURN value
END

                

Base58 Encode/Decode

import java.math.BigInteger;
import java.util.Arrays;

public class Base58 {
    // Base58 alphabet
    private static final char[] ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();
    private static final BigInteger BASE = BigInteger.valueOf(ALPHABET.length);
    private static final int[] INDEXES = new int[128];

    static {
        Arrays.fill(INDEXES, -1);
        for (int i = 0; i < ALPHABET.length; i++) {
            INDEXES[ALPHABET[i]] = i;
        }
    }

    // Encode a BigInteger to a Base58 string
    public static String encode(BigInteger value) {
        if (value.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Input must be non-negative");
        }
        StringBuilder sb = new StringBuilder();
        while (value.compareTo(BigInteger.ZERO) > 0) {
            BigInteger[] divmod = value.divideAndRemainder(BASE);
            sb.append(ALPHABET[divmod[1].intValue()]);
            value = divmod[0];
        }
        return sb.length() > 0 ? sb.reverse().toString() : "";
    }

    // Decode a Base58 string to a BigInteger
    public static BigInteger decode(String input) {
        BigInteger value = BigInteger.ZERO;
        for (char c : input.toCharArray()) {
            int index = INDEXES[c];
            if (index == -1) {
                throw new IllegalArgumentException("Invalid Base58 character: " + c);
            }
            value = value.multiply(BASE).add(BigInteger.valueOf(index));
        }
        return value;
    }

    // Example usage
    public static void main(String[] args) {
        BigInteger value = new BigInteger("123456");
        String encoded = encode(value);
        BigInteger decoded = decode(encoded);
        System.out.println("Input: " + value); // 123456
        System.out.println("Base58: " + encoded); // LDP
        System.out.println("Decoded: " + decoded); // 123456
    }
}

                

Base58 Encode/Decode

using System;
using System.Numerics;
using System.Text;

public class Base58
{
    private const string Base58Chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    // Encode a BigInteger to a Base58 string
    public static string Encode(BigInteger value)
    {
        if (value < 0)
            throw new ArgumentException("Input must be non-negative");

        StringBuilder result = new StringBuilder();
        while (value > 0)
        {
            int index = (int)(value % 58);
            result.Insert(0, Base58Chars[index]);
            value /= 58;
        }
        return result.ToString();
    }

    // Decode a Base58 string to a BigInteger
    public static BigInteger Decode(string base58)
    {
        BigInteger value = BigInteger.Zero;
        foreach (char c in base58)
        {
            int index = Base58Chars.IndexOf(c);
            if (index == -1)
                throw new ArgumentException("Invalid Base58 character: " + c);
            value = value * 58 + index;
        }
        return value;
    }

    // Example usage
    public static void Main()
    {
        BigInteger value = new BigInteger(123456);
        string encoded = Encode(value);
        BigInteger decoded = Decode(encoded);
        Console.WriteLine($"Input: {value}"); // 123456
        Console.WriteLine($"Base58: {encoded}"); // LDP
        Console.WriteLine($"Decoded: {decoded}"); // 123456
    }
}

                

Logic and Behavior

Hex to Bytes: Convert the hex string to a byte array (e.g., "1E240" → { 0x1E, 0x24, 0x0 }).

BigInteger Constructor: Interprets the byte array as a little-endian two’s-complement number:

• If the first byte ≥ 0x80 (e.g., 0xFF), it’s negative unless a 0 byte is appended.
• Example: { 0xFF } → -1 (negative) without 0, 255 (positive) with 0.

Ensuring Positive: Append a 0 byte to guarantee a positive BigInteger:

BigInteger value = new BigInteger(data.Concat(new byte[] { 0 }).ToArray());

                

Why Always Add 0? It’s simpler than checking data[0] >= 0x80, covers all cases (empty arrays, all byte values), and aligns with Base58’s unsigned number requirement. The overhead is negligible.

Example Conversion:

public static BigInteger HexToBigInteger(string hex)
{
    byte[] data = FromHexString(hex);
    return new BigInteger(data.Concat(new byte[] { 0 }).ToArray()); // Ensure positive
}

private static byte[] FromHexString(string hex)
{
    if (string.IsNullOrEmpty(hex))
        throw new ArgumentException("Hex string cannot be null or empty.");

    hex = hex.Trim();
    if (hex.Length % 2 != 0)
        throw new ArgumentException($"Hex string length must be even, got {hex.Length} characters.");

    var numberChars = hex.Length;
    var hexAsBytes = new byte[numberChars / 2];
    for (var i = 0; i < numberChars; i += 2)
        hexAsBytes[i / 2] = Convert.ToByte(hex.Substring(i, 2), 16);

    return hexAsBytes;
}

                

Usage:

string hex = "1E240"; // 123456 in decimal
BigInteger value = HexToBigInteger(hex); // 123456
string base58 = Base58.Encode(value); // LDP

                

Reference Implementations

• Bitcoin Wiki: Base58Check Encoding
• Ripple Base58 Documentation
• Java BigInteger Documentation
• C# BigInteger Documentation

Further Reading

• Stack Overflow: Base58 Encoding
• Cryptography Stack Exchange: Base58 in Cryptocurrencies
• Wikipedia: Base58