C or C++ code for validating Bitcoin addresses

[Hyena]

I have been searching the Internet for quite some time now and haven't found an ultimate C or C++ function that validates Bitcoin addresses. Sure there is one here but it gives so many false answers it's unacceptable.

I need the strictest possible most complete and fail-proof function written in either C or C++. It should correctly cope with addresses as short as 26 characters. Also, it should understand that addresses starting with 3 are also valid. If the address has not enough 1s or has too many 1s in the beginning then the function should return false.

I believe I'm not the last developer out there searching for such a self-contained function so if you can help, please contribute to this topic.

[1714078760]

1714078760

[1714078760]

1714078760

[2c0de]

Are you sure you want to limit yourself to Bitcoin only? Depending, you might want to support Dogecoin and other clones as well.

Anyway to solve this problem, the  official place to look for this would be Bitcoin Core.

[Hyena]

Are you sure you want to limit yourself to Bitcoin only? Depending, you might want to support Dogecoin and other clones as well.

Anyway to solve this problem, the  official place to look for this would be Bitcoin Core.

Yes. Core has validateaddress RPC which is basically exactly what I need. However, Core's code is way too refactored. I need one function, self-contained, to do this all. Its only dependency would be SHA-256.

[2c0de]

maybe start from this place?

https://github.com/keeshux/basic-blockchain-programming

https://github.com/keeshux/basic-blockchain-programming/blob/master/base58.h

[Hyena]

maybe start from this place?

https://github.com/keeshux/basic-blockchain-programming

https://github.com/keeshux/basic-blockchain-programming/blob/master/base58.h

What confuses me the most is that hex 0000000000000000000000000000000000000000 is 1111111111111111111114oLvT2 (27 characters) but hex 0000000000000000000000000000000000000001 is 11111111111111111111BZbvjr (26 characters).

20 zeroes in the beginning of the BTC address payoad results in an address of length 27.
19 zeroes in the beginning of the BTC address payload and then byte with decimal value of 1 results in an address of length 26.

But now all of sudden 17 zeroes in the beginning followed by the byte with value 1 results in an address of length 27 again.

What logic is there? It is said that the number of 1s in the beginning of the address depends on the number of zeroes in the beginning of the address payload but this dependency is no way trivial.

[achow101]

But now all of sudden 17 zeroes in the beginning followed by the byte with value 1 results in an address of length 27 again.

What logic is there? It is said that the number of 1s in the beginning of the address depends on the number of zeroes in the beginning of the address payload but this dependency is no way trivial.

The logic is that a hash160 with 17 leading zeros and the 18th byte being 1 still has 2 following bytes that, even if zero, are not leading. So, those remaining 3 bytes concatenated with the 4 byte checksum is converted to base58. That number is larger than the 5 bytes of a hash160 with 19 leading zeros so the resulting encoding is longer.

[DannyHamilton]

What confuses me the most is that hex 0000000000000000000000000000000000000000 is 1111111111111111111114oLvT2 (27 characters) but hex 0000000000000000000000000000000000000001 is 11111111111111111111BZbvjr (26 characters).

20 zeroes in the beginning of the BTC address payoad results in an address of length 27.
19 zeroes in the beginning of the BTC address payload and then byte with decimal value of 1 results in an address of length 26.

But now all of sudden 17 zeroes in the beginning followed by the byte with value 1 results in an address of length 27 again.

What logic is there? It is said that the number of 1s in the beginning of the address depends on the number of zeroes in the beginning of the address payload but this dependency is no way trivial.

Lets walk through the steps and see what happens:

Starting with an RIPEMD-160 hash of 20 bytes that are all 0's...
0000000000000000000000000000000000000000

Add a version byte in front (in the case of a P2PKH address, that would be a byte with value 0).

000000000000000000000000000000000000000000

Now we have 21 bytes that are all 0's.

Calculate a checksum on this value:

Code:

SHA256(SHA256(000000000000000000000000000000000000000000)) = 
94a00911c4da27f9271727ffa7a14d8d5588fc0fff9964340ec4065f387e622b

Append the first 4 bytes (8 characters) of the checksum to the RIPEMD-160 hash with version byte:
00000000000000000000000000000000000000000094a00911

Temporarily ignore leading zero bytes:
94a00911

Convert the value from hex to base58:
0x94a00911 =
4oLvT2 _{(base 58)}

Each LEADING 00 BYTE is replaced with a single 1:

Code:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Concatenate 21 ones with 6 base58 digits:
1111111111111111111114oLvT2

21 "ones" plus 6 base58 digits = 27 characters


Now lets try the same with 19 zeros and a bytes with value 1...

0000000000000000000000000000000000000001

Add a version byte in front (in the case of a P2PKH address, that would be a byte with value 0).

000000000000000000000000000000000000000001

Now we have 20 bytes that are all 0's, followed by a byte that is represented in hex as "01"

Calculate a checksum on this value:

Code:

SHA256(SHA256(000000000000000000000000000000000000000001)) = 
9d35b5b9d5befcf2d6b89994f7f64279b0645d5d4a5f1a6fa2dcc615bbed04ef

Append the first 4 bytes (8 characters) of the checksum to the RIPEMD-160 hash with version byte:
0000000000000000000000000000000000000000019d35b5b9

Temporarily ignore leading zero bytes:
019d35b5b9

Convert the value from hex to base58:
0x019d35b5b9 =
BZbvjr _{(base 58)}

Each LEADING 00 BYTE is replaced with a single 1:

Code:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Concatenate 20 ones with 6 base58 digits:
111111111111111111111BZbvjr

20 "ones" plus 6 base58 digits = 26 characters

(notice that the number of leading 0 bytes was decreased by 1 because the last byte was now a 01, however the number of base58 digits didn't increase since both 0x94a00911 and 0x019d35b5b9 can be represented with 6 base58 digits (4oLvT2 and BZbvjr respectively).

[DannyHamilton]

I don't have time to write the C code for you right now, but if you are capable of writing your own, the process to validate a bitcoin address (both P2PKH and P2SH) would be:

1. Convert each leading "one" to a single byte of value 0
2. Convert the remaining digits from base58 to hex
3. The result should be exactly 25 bytes long, if not you have an invalid address.
4. Make sure that the leading byte is either a value of 0 or a value of 5, if not you have an invalid address.
5. Remove the trailing 4 bytes, leaving you with a 21 byte hex value.
6. Calculate SHA256(SHA256()) on the 21 bytes.
7. Make sure the first 4 bytes of step 6 are equal to the 4 bytes removed in step 5, if not you have an invalid address.
8. If you get this far without determining that the address is invalid, then the address is valid.

(programmatically, you may find it easier to reverse the order of the first two steps)

[Hyena]

I don't have time to write the C code for you right now, but if you are capable of writing your own, the process to validate a bitcoin address (both P2PKH and P2SH) would be:

1. Convert each leading "one" to a single byte of value 0
2. Convert the remaining digits from base58 to hex
3. The result should be exactly 25 bytes long, if not you have an invalid address.
4. Make sure that the leading byte is either a value of 0 or a value of 5, if not you have an invalid address.
5. Remove the trailing 4 bytes, leaving you with a 21 byte hex value.
6. Calculate SHA256(SHA256()) on the 21 bytes.
7. Make sure the first 4 bytes of step 6 are equal to the 4 bytes removed in step 5, if not you have an invalid address.
8. If you get this far without determining that the address is invalid, then the address is valid.

(programmatically, you may find it easier to reverse the order of the first two steps)

Thank you so much for that explanation earlier and for these instructions. I think I can now understand the process fully and am able to implement the needed code. I will share it in this topic later when I'm finished. Also, seems that libbase58 library also has the necessary functionality included in it which I can slightly modify to meet my requirements.

[Hyena]

Below is the C code I just finished for the purpose described in OP.

Code:

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <openssl/sha.h>

/* Based on libbase58, see https://github.com/luke-jr/libbase58 for reference.*/
/* Returns the version of a valid Bitcoin address or a negative value if the  */
/* address is invalid.                                                        */
int validate_bitcoin_address(const char *address) {
    static const int8_t b58digits_map[] = {
        -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
        -1, 0, 1, 2, 3, 4, 5, 6,  7, 8,-1,-1,-1,-1,-1,-1,
        -1, 9,10,11,12,13,14,15, 16,-1,17,18,19,20,21,-1,
        22,23,24,25,26,27,28,29, 30,31,32,-1,-1,-1,-1,-1,
        -1,33,34,35,36,37,38,39, 40,41,42,43,-1,44,45,46,
        47,48,49,50,51,52,53,54, 55,56,57,-1,-1,-1,-1,-1,
    };

    unsigned char addrbin[25];
    size_t addrbinsz = sizeof(addrbin);

    void *bin = (void *) addrbin;
    size_t *binszp = &addrbinsz;
    const char *b58 = address;
    size_t b58sz = strlen(address);

    {
        const unsigned char *b58u = (void *) b58;
        unsigned char *binu = bin;
        uint32_t outi[(25 + 3) / 4];
        size_t outisz=(25 + 3) / 4;
        uint64_t t;
        uint32_t c;
        size_t i, j;
        uint8_t bytesleft = 25 % 4;
        uint32_t zeromask = bytesleft ? (0xffffffff << (bytesleft * 8)) : 0;
        unsigned zerocount = 0;

        if (!b58sz) b58sz = strlen(b58);
        memset(outi, 0, sizeof(outi));

        /* Leading zeros, just count */
        for (i = 0; i < b58sz && b58u[i] == '1'; ++i) ++zerocount;
        for ( ; i < b58sz; ++i) {
            if (b58u[i] & 0x80) return -1; /* High-bit set on invalid digit */
		    if (b58digits_map[b58u[i]] == -1) return -2; /* Invalid base58 digit */
            
            c = (unsigned)b58digits_map[b58u[i]];
            for (j = outisz; j--; ) {
                t = ((uint64_t)outi[j]) * 58 + c;
                c = (t & 0x3f00000000) >> 32;
                outi[j] = t & 0xffffffff;
            }

            if (c) return -3; /* Output number too big (carry to the next int32) */
            if (outi[0] & zeromask) return -4; /* Output number too big (last int32 filled too far) */
        }

        j = 0;
        switch (bytesleft) {
            case 3: *(binu++) = (outi[0] &   0xff0000) >> 16;
		    case 2: *(binu++) = (outi[0] &     0xff00) >>  8;
		    case 1: *(binu++) = (outi[0] &       0xff);  ++j;
		    default: break;
        }

        for (; j < outisz; ++j) {
            *(binu++) = (outi[j] >> 0x18) & 0xff;
            *(binu++) = (outi[j] >> 0x10) & 0xff;
            *(binu++) = (outi[j] >>    8) & 0xff;
            *(binu++) = (outi[j] >>    0) & 0xff;
        }

        binu = bin; /* Count canonical base58 byte count */
        for (i = 0; i < 25; ++i) {
            if (binu[i]) break;
            --*binszp;
        }
        *binszp += zerocount;
    }

    if (addrbinsz != 25) return -5;
    if (addrbin[0] != 0 && addrbin[0] != 5) return -6;

    {
        unsigned char d1[SHA256_DIGEST_LENGTH], d2[SHA256_DIGEST_LENGTH];
        SHA256(SHA256(addrbin, 21, d1), SHA256_DIGEST_LENGTH, d2);
        if (memcmp(addrbin + 21, d2, 4)) return -7;
    }

    return addrbin[0];
}

int main( int argc, char * argv [] ) {
    int i;

    for (i = 1; i < argc; ++i ) {
        bool valid = (validate_bitcoin_address(argv[i]) >= 0);
        printf( "%s is %s\n", argv[i], valid ? "VALID." : "INVALID!");
    }

    return 0;
}

[Hyena]

For the sake of completeness, here's the self-contained C function that turns payload into a valid bitcoin address.

Code:

/* Based on libbase58, see https://github.com/luke-jr/libbase58 for reference.*/
/* Attempts to convert the binary input to a Base58 format and returns true   */
/* on success.                                                                */
static bool generate_bitcoin_address(const unsigned char *payload, char type, char *b58, size_t *b58sz) {
    unsigned char address[25];

    address[0] = ( type == '1' ? 0 : 
                   type == '3' ? 5 : 111);
    memcpy(address+1, payload, 20);

    unsigned char d1[SHA256_DIGEST_LENGTH], d2[SHA256_DIGEST_LENGTH];
    SHA256(SHA256(address, 21, d1), SHA256_DIGEST_LENGTH, d2);
    memcpy(address+21, d2, 4);

    {
        static const char b58digits_ordered[] = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
        const uint8_t *bin = (const uint8_t *) address;
        int carry;
        ssize_t i, j, high, zcount = 0;
        size_t size;
        size_t uzcount = 0;

        while (uzcount < 25 && !bin[uzcount]) ++uzcount;
        zcount = uzcount;
        size =        (25 - zcount) * 138 / 100 + 1;
        uint8_t buf[ ((25 -      0) * 138 / 100 + 1) ];
        memset(buf, 0, size);
        for (i = zcount, high = size - 1; i < 25; ++i, high = j) {
            for (carry = bin[i], j = size - 1; (j > high) || carry; --j) {
                carry += 256 * buf[j];
                buf[j] = carry % 58;
                carry /= 58;
            }
        }

        for (j = 0; j < (ssize_t) size && !buf[j]; ++j);

        if (*b58sz <= zcount + size - j) {
            *b58sz = zcount + size - j + 1;
            return false;
        }

        if (zcount) memset(b58, '1', zcount);
        for (i = zcount; j < (ssize_t) size; ++i, ++j) b58[i] = b58digits_ordered[buf[j]];
        b58[i] = '\0';
        *b58sz = i + 1;
    }
    return true;
}

[jasonv75]

What confuses me the most is that hex 0000000000000000000000000000000000000000 is 1111111111111111111114oLvT2 (27 characters) but hex 0000000000000000000000000000000000000001 is 11111111111111111111BZbvjr (26 characters).

20 zeroes in the beginning of the BTC address payoad results in an address of length 27.
19 zeroes in the beginning of the BTC address payload and then byte with decimal value of 1 results in an address of length 26.

But now all of sudden 17 zeroes in the beginning followed by the byte with value 1 results in an address of length 27 again.

What logic is there? It is said that the number of 1s in the beginning of the address depends on the number of zeroes in the beginning of the address payload but this dependency is no way trivial.

Lets walk through the steps and see what happens:

Starting with an RIPEMD-160 hash of 20 bytes that are all 0's...
0000000000000000000000000000000000000000

Add a version byte in front (in the case of a P2PKH address, that would be a byte with value 0).

000000000000000000000000000000000000000000

Now we have 21 bytes that are all 0's.

Calculate a checksum on this value:

Code:

SHA256(SHA256(000000000000000000000000000000000000000000)) = 
94a00911c4da27f9271727ffa7a14d8d5588fc0fff9964340ec4065f387e622b

Append the first 4 bytes (8 characters) of the checksum to the RIPEMD-160 hash with version byte:
00000000000000000000000000000000000000000094a00911

Temporarily ignore leading zero bytes:
94a00911

Convert the value from hex to base58:
0x94a00911 =
4oLvT2 _{(base 58)}

Each LEADING 00 BYTE is replaced with a single 1:

Code:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Concatenate 21 ones with 6 base58 digits:
1111111111111111111114oLvT2

21 "ones" plus 6 base58 digits = 27 characters


Now lets try the same with 19 zeros and a bytes with value 1...

0000000000000000000000000000000000000001

Add a version byte in front (in the case of a P2PKH address, that would be a byte with value 0).

000000000000000000000000000000000000000001

Now we have 20 bytes that are all 0's, followed by a byte that is represented in hex as "01"

Calculate a checksum on this value:

Code:

SHA256(SHA256(000000000000000000000000000000000000000001)) = 
9d35b5b9d5befcf2d6b89994f7f64279b0645d5d4a5f1a6fa2dcc615bbed04ef

Append the first 4 bytes (8 characters) of the checksum to the RIPEMD-160 hash with version byte:
0000000000000000000000000000000000000000019d35b5b9

Temporarily ignore leading zero bytes:
019d35b5b9

Convert the value from hex to base58:
0x019d35b5b9 =
BZbvjr _{(base 58)}

Each LEADING 00 BYTE is replaced with a single 1:

Code:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Concatenate 20 ones with 6 base58 digits:
111111111111111111111BZbvjr

20 "ones" plus 6 base58 digits = 26 characters

(notice that the number of leading 0 bytes was decreased by 1 because the last byte was now a 01, however the number of base58 digits didn't increase since both 0x94a00911 and 0x019d35b5b9 can be represented with 6 base58 digits (4oLvT2 and BZbvjr respectively).

Holy shit! Thanks for that!

[Hyena]

Holy shit! Thanks for that!

Yep, that post by DannyHamilton indeed was very useful and educational.

[jasonv75]

Holy shit! Thanks for that!

Yep, that post by DannyHamilton indeed was very useful and educational.

Compressed and easy to understand information like that is rare!

Would have taken me days to figure out how the conversion would work step by step like that.

[DannyHamilton]

Holy shit! Thanks for that!

Yep, that post by DannyHamilton indeed was very useful and educational.

Compressed and easy to understand information like that is rare!

Would have taken me days to figure out how the conversion would work step by step like that.

Honestly guys, all I did was read these two pages:
https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
https://en.bitcoin.it/wiki/Base58Check_encoding

And re-state it in terms of the particular RIPEMD160 hashes that were being asked about (all zeros, and all zeros except the last byte).

[jasonv75]

Holy shit! Thanks for that!

Yep, that post by DannyHamilton indeed was very useful and educational.

Compressed and easy to understand information like that is rare!

Would have taken me days to figure out how the conversion would work step by step like that.

Honestly guys, all I did was read these two pages:
https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
https://en.bitcoin.it/wiki/Base58Check_encoding

And re-state it in terms of the particular RIPEMD160 hashes that were being asked about (all zeros, and all zeros except the last byte).

Ok... yea I feel a bit stupid now. lol

[mavenraven]

I know the topic has been solved, but here's something useful

http://rosettacode.org/wiki/Bitcoin/address_validation

could be buggy, though!

[Hyena]

I know the topic has been solved, but here's something useful

http://rosettacode.org/wiki/Bitcoin/address_validation

could be buggy, though!

I actually link to this page in OP already. The solutions there are very buggy indeed.