VanitySearch (Yet another address prefix finder)

[NotATether]

An update about the chronic address bug on VanitySearch:

I have found the source of the error. In case you didn't know, everything released after VanitySearch 1.13 fails to math any base58 address, on newer GCC (11+, and maybe 10 as well)

This has to do with the sha256.cpp and sha256_sse.cpp files inside the hash/ folder. Specifically, sha256_checksum and sha256sse_checksum functions.

These functions fail to make the correct checksum when you are running with optimization flags on, but I managed to get even more specific than that.

It appears that a single O2 optimization flag, -fstrict-aliasing is causing all the chaos. Taking the SSE version of this function for example:

Code:

void sha256sse_checksum(uint32_t *i0, uint32_t *i1, uint32_t *i2, uint32_t *i3,
  uint8_t *d0, uint8_t *d1, uint8_t *d2, uint8_t *d3) {

  __m128i s[8];

  _sha256sse::Initialize(s);
  _sha256sse::Transform2(s, i0, i1, i2, i3);

#ifndef WIN64
  uint32_t *s32 = (uint32_t *)(&s[0]);
  *((uint32_t *)d0) = __builtin_bswap32(s32[3]);
  *((uint32_t *)d1) = __builtin_bswap32(s32[2]);
  *((uint32_t *)d2) = __builtin_bswap32(s32[1]);
  *((uint32_t *)d3) = __builtin_bswap32(s32[0]);
#else
  *((uint32_t *)d0) = _byteswap_ulong(s[0].m128i_u32[3]);
  *((uint32_t *)d1) = _byteswap_ulong(s[0].m128i_u32[2]);
  *((uint32_t *)d2) = _byteswap_ulong(s[0].m128i_u32[1]);
  *((uint32_t *)d3) = _byteswap_ulong(s[0].m128i_u32[0]);
#endif

}

Aliasing is an optimization technique where the compiler assumes that you're never going to cast variables into crazy types of different sizes and makes some fast but unsafe memory writes as a result.

It's unsafe because if the type indeed is cast into a larger size type, then some garbage will be written into the higher parts of the variable. That's where the gibberish in the checksum characters comes from. The parameters d0-3 are expanded into uint32 and then assigned, and that's where strict aliasing messes things up.

Something similar happens with sha256_checksum but with memcpy instead.

These functions were introduced in the following commit: https://github.com/JeanLucPons/VanitySearch/commit/ea177b7b36c0db66f110d4358fd4fd4704a6603d right before v1.14 was released.

To fix this mess, all you have to do is pass -fno-strict-aliasing (please write this carefully) in the CXXFLAGS in the makefile.

I am working on a patched version of this where only the offending functions get this flag. So my codebase is spaghetti right now. Please stand by.

[WanderingPhilospher]

An update about the chronic address bug on VanitySearch:

I have found the source of the error. In case you didn't know, everything released after VanitySearch 1.13 fails to math any base58 address, on newer GCC (11+, and maybe 10 as well)

This has to do with the sha256.cpp and sha256_sse.cpp files inside the hash/ folder. Specifically, sha256_checksum and sha256sse_checksum functions.

These functions fail to make the correct checksum when you are running with optimization flags on, but I managed to get even more specific than that.

It appears that a single O2 optimization flag, -fstrict-aliasing is causing all the chaos. Taking the SSE version of this function for example:

Code:

void sha256sse_checksum(uint32_t *i0, uint32_t *i1, uint32_t *i2, uint32_t *i3,
  uint8_t *d0, uint8_t *d1, uint8_t *d2, uint8_t *d3) {

  __m128i s[8];

  _sha256sse::Initialize(s);
  _sha256sse::Transform2(s, i0, i1, i2, i3);

#ifndef WIN64
  uint32_t *s32 = (uint32_t *)(&s[0]);
  *((uint32_t *)d0) = __builtin_bswap32(s32[3]);
  *((uint32_t *)d1) = __builtin_bswap32(s32[2]);
  *((uint32_t *)d2) = __builtin_bswap32(s32[1]);
  *((uint32_t *)d3) = __builtin_bswap32(s32[0]);
#else
  *((uint32_t *)d0) = _byteswap_ulong(s[0].m128i_u32[3]);
  *((uint32_t *)d1) = _byteswap_ulong(s[0].m128i_u32[2]);
  *((uint32_t *)d2) = _byteswap_ulong(s[0].m128i_u32[1]);
  *((uint32_t *)d3) = _byteswap_ulong(s[0].m128i_u32[0]);
#endif

}

Aliasing is an optimization technique where the compiler assumes that you're never going to cast variables into crazy types of different sizes and makes some fast but unsafe memory writes as a result.

It's unsafe because if the type indeed is cast into a larger size type, then some garbage will be written into the higher parts of the variable. That's where the gibberish in the checksum characters comes from. The parameters d0-3 are expanded into uint32 and then assigned, and that's where strict aliasing messes things up.

Something similar happens with sha256_checksum but with memcpy instead.

These functions were introduced in the following commit: https://github.com/JeanLucPons/VanitySearch/commit/ea177b7b36c0db66f110d4358fd4fd4704a6603d right before v1.14 was released.

To fix this mess, all you have to do is pass -fno-strict-aliasing (please write this carefully) in the CXXFLAGS in the makefile.

I am working on a patched version of this where only the offending functions get this flag. So my codebase is spaghetti right now. Please stand by.

Can you enlighten me to what exactly the bug is/is doing? Is it only the -check unit test?

[NotATether]

Can you enlighten me to what exactly the bug is/is doing? Is it only the -check unit test?

It's not just in the unit test, it's also in the main loop when it's generating Base58 addresses (the checksums made after an equality comparison or regex match, specifically).

In the above code piece for creating the checksum, it runs fine without any optimizations at all.

But, when -fstrict-aliasing is switched on as a result of using -O2, the compiler assumes that variables of different types being assigned to each other have the same size (as in sizeof()) and optimizes out some internal ASM that would've otherwise been generated.

The ASM being removed here is parts of the assignment statements in the snippet above (and in the non-SSE version). Those areas still have junk values from when those automatic variables were declared.

So the SHA256 checksum contains some garbage bytes. When this is encoded into Base58, it can only generate wrong addresses. And this is despite all private keys being 100% correct.

That's why it works in debug mode and not in production.

[WanderingPhilospher]

Can you enlighten me to what exactly the bug is/is doing? Is it only the -check unit test?

It's not just in the unit test, it's also in the main loop when it's generating Base58 addresses (the checksums made after an equality comparison or regex match, specifically).

In the above code piece for creating the checksum, it runs fine without any optimizations at all.

But, when -fstrict-aliasing is switched on as a result of using -O2, the compiler assumes that variables of different types being assigned to each other have the same size (as in sizeof()) and optimizes out some internal ASM that would've otherwise been generated.

The ASM being removed here is parts of the assignment statements in the snippet above (and in the non-SSE version). Those areas still have junk values from when those automatic variables were declared.

So the SHA256 checksum contains some garbage bytes. When this is encoded into Base58, it can only generate wrong addresses. And this is despite all private keys being 100% correct.

That's why it works in debug mode and not in production.

So is it just when the -check is used? I'm confused lol.

How does it impact searching for keys...

[NotATether]

So is it just when the -check is used? I'm confused lol.

How does it impact searching for keys...

No it literally breaks the address finding process too.

As in, it finds the correct address/private key, but then when it goes to verify the address is correctb(all this happens in Vanity.cpp) that fails and you get a warning because of botched base58 checksums.

This means that VanitySearch will never exit even if it finds the right keys.

[WanderingPhilospher]

So is it just when the -check is used? I'm confused lol.

How does it impact searching for keys...

No it literally breaks the address finding process too.

As in, it finds the correct address/private key, but then when it goes to verify the address is correctb(all this happens in Vanity.cpp) that fails and you get a warning because of botched base58 checksums.

This means that VanitySearch will never exit even if it finds the right keys.

OK, a few followup questions.

Does this only impact Linux, or does it impact Windows as well?

Is it hit or miss (the bug) because obviously I find addresses and their keys when running tests.

Is there a test to run that will duplicate these botched checksums?

[WhyFhy]

Hey guys in regards to recent events with coldkey sweeping funded wallets,
 I proposed this app's (VanitySearch) split key feature for makers. (and of course https://1splitkey.com service that's built off of it. because that's why I made it to simplify it.)
This notion seems to be rejected when I propose it, and these guys are proposing less than ideal solutions, ignoring this likely due to it being "Me" that proposed it.
This kind of makes me feel some type of way about the community in general.
https://bitcointalk.org/index.php?topic=5387113.msg61631653


However I see this as a potential opportunity to shutdown my free service and release the sourcecode and walk away from the project.
In all likelihood this is the only way 1splitkey will be utilized.
I have restraints about the implications of repurposing splitkeys backend. which contains tesla agents and things of that nature for client control and server communications.
They are used in a manner that's obvious the same way client side gpu miners are set up.

Should I take one for the team and release the SC for the good of the physical's community?

If I do this, I'll be shutting 1SK down as it will even be harder to fight bad actors.
 
I'll let you guys decide. I dont want to see all the sweat equity from this just get brushed off, it's a beautiful system that's currently just toiling in obscurity.

[NotATether]

I pushed my fixes to the gpu branch, but apparently someone is using my Vast GPU, so I can't test the GPU build until it becomes free again.

Hey guys in regards to recent events with coldkey sweeping funded wallets,
 I proposed this app's (VanitySearch) split key feature for makers. (and of course https://1splitkey.com service that's built off of it. because that's why I made it to simplify it.)
This notion seems to be rejected when I propose it, and these guys are proposing less than ideal solutions, ignoring this likely due to it being "Me" that proposed it.
This kind of makes me feel some type of way about the community in general.
https://bitcointalk.org/index.php?topic=5387113.msg61631653


However I see this as a potential opportunity to shutdown my free service and release the sourcecode and walk away from the project.
In all likelihood this is the only way 1splitkey will be utilized.
I have restraints about the implications of repurposing splitkeys backend. which contains tesla agents and things of that nature for client control and server communications.
They are used in a manner that's obvious the same way client side gpu miners are set up.

Should I take one for the team and release the SC for the good of the physical's community?

If I do this, I'll be shutting 1SK down as it will even be harder to fight bad actors.
 
I'll let you guys decide. I dont want to see all the sweat equity from this just get brushed off, it's a beautiful system that's currently just toiling in obscurity.

Is this generating any revenue for you right now?

If it's just sitting there collecting hosting fees, then yeah, you can release the code, and maybe one of us will find a way to utilize it.

[NotATether]

Guys I updated my VanitySearch clone to work on GPU as well as CPU, so you guys shouldn't have any problems with that. I'm still debugging some issues with ".*" and ".+" wildcards that citb0in spotted, and the GPU build has a nasty and unexpected 5x slowdown. Which is pretty weird since almost all of the GPU codebase is the same as the original.

[WanderingPhilospher]

Guys I updated my VanitySearch clone to work on GPU as well as CPU, so you guys shouldn't have any problems with that. I'm still debugging some issues with ".*" and ".+" wildcards that citb0in spotted, and the GPU build has a nasty and unexpected 5x slowdown. Which is pretty weird since almost all of the GPU codebase is the same as the original.

What exactly is different about your clone versus the original? Thanks.

[WhyFhy]

Guys I updated my VanitySearch clone to work on GPU as well as CPU, so you guys shouldn't have any problems with that. I'm still debugging some issues with ".*" and ".+" wildcards that citb0in spotted, and the GPU build has a nasty and unexpected 5x slowdown. Which is pretty weird since almost all of the GPU codebase is the same as the original.

Ive always noticed a slowdown on verbose wildcard vanities. specially ones like 1test*test.
usually, its indexes much slower with split key generation + wildcards toss in a split key +1test*test even with -c it seems to take a while longer than it should.

[NotATether]

Guys I updated my VanitySearch clone to work on GPU as well as CPU, so you guys shouldn't have any problems with that. I'm still debugging some issues with ".*" and ".+" wildcards that citb0in spotted, and the GPU build has a nasty and unexpected 5x slowdown. Which is pretty weird since almost all of the GPU codebase is the same as the original.

What exactly is different about your clone versus the original? Thanks.

My clone has regex support instead of just the two wildcards ? and * (had to rip out all the legacy wildcard code out in the process because it was overcomplicating things) and it also support searching for multiple prefixes simultaneously.

It is available at https://github.com/ZenulAbidin/VanitySearch (warning: still experimental software).

[WanderingPhilospher]

Guys I updated my VanitySearch clone to work on GPU as well as CPU, so you guys shouldn't have any problems with that. I'm still debugging some issues with ".*" and ".+" wildcards that citb0in spotted, and the GPU build has a nasty and unexpected 5x slowdown. Which is pretty weird since almost all of the GPU codebase is the same as the original.

What exactly is different about your clone versus the original? Thanks.

My clone has regex support instead of just the two wildcards ? and * (had to rip out all the legacy wildcard code out in the process because it was overcomplicating things) and it also support searching for multiple prefixes simultaneously.

It is available at https://github.com/ZenulAbidin/VanitySearch (warning: still experimental software).

Can you give me an example of how regex works/is different than current program?

current program can search strings like:

1NotATeth
1NotATeth*

How is regex different? I read your github page

Does your version still support full address search?

also, current program can search up to 32 million prefixes simultaneously (I haven't tried more than 32 million).

[NotATether]

Ultimately, it will not only allow prefix searches, but also suffix searches and also for vanity characters in an arbitrary part of the address.

Does your version still support full address search?

I didn't modify that particular section so that should work just fine.

also, current program can search up to 32 million prefixes simultaneously (I haven't tried more than 32 million).

How did you input these prefixes? Using the command-line, or another way?

Original VanitySearch only reads the first prefix on the command line, but I tweaked it to read all of them.

Side note: Regex matching on GPU seems to work, but I am going to revert all the changes I made to GPU because there's an alternate way of matching strings using the "|" operator, which makes everything I made in that section obsolete (and is probably the cause of the 5x GPU slowdown anyway).

[WanderingPhilospher]

How did you input these prefixes? Using the command-line, or another way?

From input file, the original -i  flag; 1 per line

[NotATether]

How did you input these prefixes? Using the command-line, or another way?

From input file, the original -i  flag; 1 per line

Good to know. Although it would still be handy to read prefixes from the command line too: VanitySearch 1abcd bc1qabcd for example.

[PX-Z]

Thanks for this, i just discovered this thread and eventually generate mine with native segwit wallet address ^{(check my profile)}. Well it's was generated almost in instant since i only use 3 character in reference with my username.

[WanderingPhilospher]

How did you input these prefixes? Using the command-line, or another way?

From input file, the original -i  flag; 1 per line

Good to know. Although it would still be handy to read prefixes from the command line too: VanitySearch 1abcd bc1qabcd for example.

Easy to do, but I wouldn't wanna put 32 million prefixes on cmd line LOL.

Just keep parsing over the CMD line...

[digaran]

I have a few questions if you don't mind.

1: how do we know if a custom address could exist and is valid?
2: if I already know a vanity address's private key/ key range, would it be easier to generate that address if I could set a specific range for the tool to search only in that range? Would that reduce the difficulty and the time needed?

[nc50lc]

May I?

I have a few questions if you don't mind.

1: how do we know if a custom address could exist and is valid?

As long as the address has a valid checksum, it's valid.
The checksum is the last 4Bytes of the address after decoding it in base58;
To be valid, it should match the first 4Bytes of the SHA256D hash of the rest of the characters (w/o the checksum).

In fact, even without the private key, you can make valid custom address that "could exist".
Here's a tool for example: https://gobittest.appspot.com/ProofOfBurn

2: if I already know a vanity address's private key/ key range, would it be easier to generate that address if I could set a specific range for the tool to search only in that range? Would that reduce the difficulty and the time needed?

Yes, but why search if you already know the private key?

Take note that similar vanity addresses like 1banana12345...... and 1banana12344...... have no correlation to their private key's ranges.
Addresses are just the base58 encoding of the HASH160 (sha256 and then ripemd160) of the public key which is pseudorandom, plus some additional data.
Knowing the former's private key wont trivialize the search for the latter's private key.