How do I Base58 Checked encode / decode an address in C#? What does "normalize leading zeros" mean?

Question

I am trying to encode and decode a Base58 address in C#. The following function is a start, but it has a few issues:

• This code does not normalize leading zeros (what does that look like?)

• If this method is repeatedly called in rapid succession many string objects will be created, putting pressure on the GC

.NET 4.5 Code

Note add a reference to System.Numerics

BigInteger  bi =  System.Numerics.BigInteger.Parse("00010966776006953D5567439E5E39F86A0D273BEED61967F6", NumberStyles.HexNumber);

string b58 = EncodeBase58(bi);
Console.WriteLine(b58 + Environment.NewLine + "16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM");

   /// .... SNIP

   public static String sBase58Alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
    public static String EncodeBase58(BigInteger numberToShorten)
    {
        // WARNING: Beware of bignumber implementations that clip leading 0x00 bytes, or prepend extra 0x00 
        // bytes to indicate sign - your code must handle these cases properly or else you may generate valid-looking
        // addresses which can be sent to, but cannot be spent from - which would lead to the permanent loss of coins.)


        // Base58Check encoding is also used for encoding private keys in the Wallet Import Format. This is formed exactly
        // the same as a Bitcoin address, except that 0x80 is used for the version/application byte, and the payload is 32 bytes
        // instead of 20 (a private key in Bitcoin is a single 32-byte unsigned big-endian integer). Such encodings will always
        // yield a 51-character string that starts with '5', or more specifically, either '5H', '5J', or '5K'.   https://en.bitcoin.it/wiki/Base58Check_encoding
        const int sizeWalletImportFormat = 51;

        char[] result = new char[33];

        int i = 0;
        while (numberToShorten >= 0 && result.Length > i)
        {
            var lNumberRemainder = BigInteger.Remainder(numberToShorten, (BigInteger)sBase58Alphabet.Length);
            numberToShorten = numberToShorten / (BigInteger)sBase58Alphabet.Length;
           result[result.Length - 1- i] = sBase58Alphabet[(int)lNumberRemainder] ;
           i++;
        }

        return new string(result);
    }
    //public static long DecodeBase58(String base58StringToExpand)
    //{
    //    long lConverted = 0;
    //    long lTemporaryNumberConverter = 1;

    //    while (base58StringToExpand.Length > 0)
    //    {
    //        String sCurrentCharacter = base58StringToExpand.Substring(base58StringToExpand.Length - 1);
    //        lConverted = lConverted + (lTemporaryNumberConverter * sBase58Alphabet.IndexOf(sCurrentCharacter));
    //        lTemporaryNumberConverter = lTemporaryNumberConverter * sBase58Alphabet.Length;
    //        base58StringToExpand = base58StringToExpand.Substring(0, base58StringToExpand.Length - 1);
    //    }
    //}

Answer 1

To normalize leading zeros is documented in this link, namely this text at the bottom:

In a standard base conversion, the 0x00 byte on the left would be irrelevant (like writing 052 instead of 52) but in the BTC network the left most zero chars are carried through the conversion. So for every 0x00 byte on the left end of the binary address, we will attach one '1' character to the Base58 address. This is why the main-network addresses all start with 1.

The following code will address the GC issue with over-allocation and discarding of the String type, however it does not properly handle the leading zero bytes. I either need to find a list of expected lengths per type or some other approach.

    public static String sBase58Alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
    public static String EncodeBase58(BigInteger numberToShorten)
    {
        // WARNING: Beware of bignumber implementations that clip leading 0x00 bytes, or prepend extra 0x00 
        // bytes to indicate sign - your code must handle these cases properly or else you may generate valid-looking
        // addresses which can be sent to, but cannot be spent from - which would lead to the permanent loss of coins.)


        // Base58Check encoding is also used for encoding private keys in the Wallet Import Format. This is formed exactly
        // the same as a Bitcoin address, except that 0x80 is used for the version/application byte, and the payload is 32 bytes
        // instead of 20 (a private key in Bitcoin is a single 32-byte unsigned big-endian integer). Such encodings will always
        // yield a 51-character string that starts with '5', or more specifically, either '5H', '5J', or '5K'.   https://en.bitcoin.it/wiki/Base58Check_encoding
        const int sizeWalletImportFormat = 51;

        char[] result = new char[33];

        Int32 iAlphabetLength = sBase58Alphabet.Length;
        BigInteger iAlphabetLength2 = BigInteger.Parse(iAlphabetLength.ToString());

        int i = 0;
        while (numberToShorten >= 0 && result.Length > i)
        {
            var lNumberRemainder = BigInteger.Remainder(numberToShorten, iAlphabetLength2);
            numberToShorten = numberToShorten / iAlphabetLength;
           result[result.Length - 1- i] = sBase58Alphabet[(int)lNumberRemainder] ;
           i++;
        }

        return new string(result);
    }