Bitcoin Forum
January 19, 2020, 07:54:15 PM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: C or C++ code for validating Bitcoin addresses  (Read 2078 times)
Hyena
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 08, 2016, 03:37:01 PM
 #1

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.

1579463655
Hero Member
*
Offline Offline

Posts: 1579463655

View Profile Personal Message (Offline)

Ignore
1579463655
Reply with quote  #2

1579463655
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1579463655
Hero Member
*
Offline Offline

Posts: 1579463655

View Profile Personal Message (Offline)

Ignore
1579463655
Reply with quote  #2

1579463655
Report to moderator
1579463655
Hero Member
*
Offline Offline

Posts: 1579463655

View Profile Personal Message (Offline)

Ignore
1579463655
Reply with quote  #2

1579463655
Report to moderator
1579463655
Hero Member
*
Offline Offline

Posts: 1579463655

View Profile Personal Message (Offline)

Ignore
1579463655
Reply with quote  #2

1579463655
Report to moderator
2c0de
Full Member
***
Offline Offline

Activity: 138
Merit: 100


View Profile
July 08, 2016, 04:22:02 PM
 #2

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.

DHjxvnHB9RirtPbvkovSotn1fY2poNffoi
LWeT4wwDVdJ9x49UcXPyS6CznRpbQFM6nx
0x96273C2FD825f0A2745d917bbbfabD6032dC1aDD
Hyena
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 08, 2016, 04:26:09 PM
 #3

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
Full Member
***
Offline Offline

Activity: 138
Merit: 100


View Profile
July 08, 2016, 04:31:16 PM
 #4

maybe start from this place?

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

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


DHjxvnHB9RirtPbvkovSotn1fY2poNffoi
LWeT4wwDVdJ9x49UcXPyS6CznRpbQFM6nx
0x96273C2FD825f0A2745d917bbbfabD6032dC1aDD
Hyena
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 08, 2016, 04:44:15 PM
 #5


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
Moderator
Legendary
*
expert
Offline Offline

Activity: 2016
Merit: 3007


bc1qshxkrpe4arppq89fpzm6c0tpdvx5cfkve2c8kl


View Profile WWW
July 08, 2016, 05:08:03 PM
 #6

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
Legendary
*
Offline Offline

Activity: 2324
Merit: 1674



View Profile
July 08, 2016, 06:02:15 PM
 #7

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
Legendary
*
Offline Offline

Activity: 2324
Merit: 1674



View Profile
July 08, 2016, 06:13:31 PM
 #8

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
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 08, 2016, 06:26:25 PM
 #9

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
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 08, 2016, 08:00:22 PM
 #10

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
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 14, 2016, 02:35:25 PM
 #11

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
Full Member
***
Offline Offline

Activity: 156
Merit: 100

I'm an artist, my paint is code


View Profile WWW
July 14, 2016, 02:37:31 PM
 #12

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!

Veltor.
Hyena
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 14, 2016, 02:46:33 PM
 #13

Holy shit! Thanks for that!

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

jasonv75
Full Member
***
Offline Offline

Activity: 156
Merit: 100

I'm an artist, my paint is code


View Profile WWW
July 14, 2016, 06:00:01 PM
 #14

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.

Veltor.
DannyHamilton
Legendary
*
Offline Offline

Activity: 2324
Merit: 1674



View Profile
July 14, 2016, 06:18:30 PM
 #15

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
Full Member
***
Offline Offline

Activity: 156
Merit: 100

I'm an artist, my paint is code


View Profile WWW
July 14, 2016, 06:31:31 PM
 #16

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

Veltor.
mavenraven
Full Member
***
Offline Offline

Activity: 197
Merit: 100


View Profile
July 14, 2016, 07:26:09 PM
 #17

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

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

could be buggy, though!
Hyena
Legendary
*
Offline Offline

Activity: 2058
Merit: 1002



View Profile WWW
July 14, 2016, 07:56:34 PM
 #18

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.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!