Can you help me fix this address?

Question

I just got this address: 1a8LDh3qtCdMSAgRXzMr4zB8w1EG4h1Xi, but the checksum doesn't validate. Can someone help me fix it by changing some characters that look/sound similar?

Answer 1

Just for fun, here is some code I threw together that will try substituting up to n characters to try to make a valid address.

As a disclaimer, there's no guarantee that any address it finds is actually the "right" one; it could be a different address that is valid but doesn't belong to anyone, in which case any coins sent there would be lost forever. Use at your own risk.

Running it with n=3 found the address

1a8LDh3qtCdMFAgRXzMrdvB8w1EG4h1Xi

which has a balance of BTC 29658.80268195. It appears to be the current resting place of the Bitcoins seized from Silk Road that were auctioned today.

---

To compile (on Linux):

gcc -O3 -o subst subst.c -lssl -lcrypto

You will need the OpenSSL headers and libraries installed.

To run:

 ./subst 2 1a8LDh3qtCdMSAgRXzMr4zB8w1EG4h1Xi

Will try to replace up to any 2 characters to make a valid address. You can replace 2 by 1 if you are impatient, or by a larger number if you are very patient.

Here is subst.c. There is an unused function to try transposing characters from the address, but it is redundant with n >= 2. The validation code is from Rosetta Code.

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

const char *coin_err;
#define bail(s) { coin_err = s; return 0; }

static const char *tmpl = "123456789"
        "ABCDEFGHJKLMNPQRSTUVWXYZ"
        "abcdefghijkmnopqrstuvwxyz";

char *xstrdup(const char *s) {
    char *p;
    p = strdup(s);
    if (!p) {
        fprintf(stderr, "How can you be out of memory?\n");
        exit(1);
    }
    return p;
}

int unbase58(const char *s, unsigned char *out) {
    int i, j, c;
    const char *p;

    memset(out, 0, 25);
    for (i = 0; s[i]; i++) {
        if (!(p = strchr(tmpl, s[i])))
            bail("bad char");

        c = p - tmpl;
        for (j = 25; j--; ) {
            c += 58 * out[j];
            out[j] = c % 256;
            c /= 256;
        }

        if (c) bail("address too long");
    }

    return 1;
}

int valid(const char *s) {
    unsigned char dec[32], d1[SHA256_DIGEST_LENGTH], 
        d2[SHA256_DIGEST_LENGTH];

    coin_err = "";
    if (!unbase58(s, dec)) return 0;

    SHA256(SHA256(dec, 21, d1), SHA256_DIGEST_LENGTH, d2);

    if (memcmp(dec + 21, d2, 4))
        bail("bad digest");

    return 1;
}

inline void try(const char *s) {
    if (valid(s)) {
        printf("Valid:\t%s\n", s);
    }
}

void subst_int(char *s, char *p0, int n) {
    if (n == 0)
        return;
    char *p;
    for (p = p0; *p; p++) {
        char orig = *p;
        const char *q;
        for (q = tmpl; *q; q++) {
            if (*q != orig) {
                *p = *q;
                try(s);
                subst_int(s, p+1, n-1);
            }
        }
        *p = orig;
    }
}

void subst(const char *s, int n) {
    char *buf = xstrdup(s);
    subst_int(buf, buf, n);
    free(buf);
}

inline void swap(char *p, char *q) {
    char tmp;
    tmp = *p;
    *p = *q;
    *q = tmp;
}

void transposition(const char *s) {
    char *buf = xstrdup(s);
    char *p, *q;
    for (p = buf; *p; p++) {
        for (q = p + 1; *q; q++) {
            if (*p != *q) {
                swap(p, q);
                try(buf);
                swap(p, q);
            }
        }
    }
}

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

    if (argc < 3 || (n = atoi(argv[1])) <= 0) {
        fprintf(stderr, "Usage: %s n addr...\n", argv[0]);
        fprintf(stderr, "Substitute up to n characters\n");
        exit(2);
    }


    for (i = 2; i < argc; i++) {
        char *s = argv[i];
        printf("%s:\t%s\n", valid(s) ? "Valid" : "Orig", s);
        subst(s, n);
#if 0 /* redundant with n >= 2 */
        transposition(s);
#endif
        if (i+1 < argc)
            printf("\n");
    }
    return 0;
}