Bitcoin Forum

Note:  This is under active development, currently on an experimental branch offering 5x speedup (https://github.com/nym-zone/segvan/tree/sipa_grind).  I will post further updates when appropriate.

---

By (https://bitcointalk.org/index.php?topic=2864073.msg29418075#msg29418075) popular (https://bitcointalk.org/index.php?topic=2864073.msg29490833#msg29490833) demand (https://bitcointalk.org/index.php?topic=25804.msg26877499#msg26877499):

Github: https://github.com/nym-zone/segvan

The code for this is reasonably solid, notwithstanding some inelegance in main() which will be refactored.  On FreeBSD, it’s been my dogfood for over six weeks; I have also built it and tried basic functionality on Linux.  But it needs error, warning, and usage messages—plus the manpage!

When there is significant news (such as major features or a Windows version), I will severely edit this post and bump the thread.

Two recent products (tips would be encouraging):


Those were done together, on one run with each key being searched for a Bech32 pattern and a nested “3” address pattern.  They took 500–600 CPU hours on an ultra-slow airgap laptop; for comparison, the same machine requires about 8 hours for a FreeBSD buildworld (!).  But I got lucky:  I hit a ^bc1qnullnym match after covering only about 25% of a 35-bit bruteforce search.  The other took a bit longer; but wasn’t so hard, because I permitted a potential extra digit: ^3[0-9]?segwit (case-insensitive matching).

Roadmap/TODO, in no particular order:

• Add threading.  I always simply run one instance per core.  That doesn’t waste anything, because it is a probabilistic search:  There is no concept of “progress”, no need to keep instances synchronized in any way.  Threads would make it more convenient.  However, before I add a simple pthreads implementation, I want to investigate the impact on the next item.
• Microsoft Windows version, likely via mingw.  This is in popular demand.  I can’t promise a binary on a platform I myself don’t even have in my house; but I will try to get a Windows binary made for folks who need it.
• Change/adjust the output format.  The current output format is intended for piping to shell scripts, especially for bulk generation mode.  If you need to generate ten thousand address/key pairs and pipe those into a `while read` loop, then the current format is ideal.
• Add warning/error/usage messages.  This started as an afternoon project for my own use.  The code is solid, despite some inelegance in main() which will also be refactored.  It’s solid, because I need it that way; however, unlike some of my other published software, this was not originally written with other people in mind.
• Finish the manpage!

(Reserved.)

Head meets wall repeatedly with mingw cross-compiling.  This is actually my first time ever attempting such a thing; the last time I needed a Windows binary, a significant number of years ago, I used MSVC on a Windows machine.

I want to help Windows users get spiffy new Segwit addresses; but I think I’ve spent enough time on that for now, whereas I should be writing documentation and improving the code.  If anybody who has a working mingw setup (including a POSIX regex package) on any platform could at least confirm that it compiles that way, I’d appreciate knowing that such a thing is possible without significant code changes before I spend more time trying.

If I can successfully produce a Windows binary myself, I will distribute it on Github PGP-signed (https://www.gpg4win.org/) using the ECC key identified in my signature.

I found a regex library for Windows at PCRE (http://gnuwin32.sourceforge.net/packages/pcre.htm), but now I need to go find a way to get openssl in there too because that's not on Windows either.

Thanks for your response.

I am under the impression that PCRE has wrappers for POSIX regex functionality (#include <regex.h>); so that should work.  I’ve also found a bunch of different links and discussions (mostly on Stackoverflow) leading me to believe there’s also a mingw regex package without PCRE.  I did not yet sort it all out.

I had forgotten about the OpenSSL libcrypto dependency.  Thanks for reminding me.  It is only used for hash functions, SHA-256 and RIPEMD-160.  If it would help, I could easily copy portable C code from FreeBSD’s libmd, and eliminate the -lcrypto entirely.

The biggest question to me is getting secp256k1’s build system to work with a mingw cross-compile.  The code is portable; it’s part of Bitcoin, which I will take as proof that it runs on Windows.  But the trick is to get it to cross-build the right way.  Have you tried this part on your Windows machine?

I just tried to use the makefile and deal with the errors in order, I didn't get there

The "Makefile" is for FreeBSD (and probably other BSD); the "GNUmakefile" is for Linux, and should automatically take precedence with gmake.  I assume you are using a GNU toolchain on Windows?  I could try to produce a makefile which makes isolating errors easier; let me add a no-libcrypto build option first.

Edit:  I thought tossing in the hash implementation C files would be a quick fix.  Oops.  This may take a few minutes.

You want this code:  https://github.com/bitcoin-core/secp256k1/pull/507  it will be astronomically faster than your current code.

I believe when I previously implemented the techniques in this code my result was faster than vanitygen on a GPU.

It could also be made faster still with some improvements.  E.g. it doesn't actually need to compute the y coordinate of the points, so several field multiplications could be avoided in the gej_to_ge batch conversion.   It could also avoid computing the scalar for any given point unless you found a match. (E.g. by splitting the scalar construction part into another function which you don't bother calling unless there is a match).


Another advantage of this code is that it is setup to allow an arbitrary base point.  This means you could use untrusted computers to search for you.

Sipa also has AVX2 8-way sha2 and ripemd160 that he might post somewhere if you asked.  An 8-way bech32 checksum generator should be really easy to do, though if your expression doesn't match on the final 6 characters you should avoid even running the checksum.

Thanks for this Greg. There's a lot I don't know about ECC but I'm hoping I can contribute in other ways.

I'm using mingw, so I've been running inside the project directory. I'll start using the GNUmakefile since I'm using the mingw version of gcc.

Thank you.  Yes, I want that code!  I will promptly set this as a priority feature; I can’t wait to measure the speedup.  secp256k1 already beat OpenSSL about 7x when I tried them head-to-head in my same code; looking at the description in the code, I am guessing that “astronomically” will mean “orders of magnitude”.

FWIW, the code checked into the tree is copied from Bitcoin Core v0.15.1.  I intended to mention that in my commit log, but forgot.  Of course, I follow the secp256k1 repository; but I know it does not yet have any releases, and I wanted to be just a tiny bit conservative when using software I know is marked experimental.


Excellent.  I see it.  That may call for going back to the drawing board, and performing some daemonology.  I’ll see what ideas I can cook up for a client/server generator.  It may be be a higher priority than full Windows port, if I can work out an easy way for Windows-only users to submit their requests to a “cloud” machine and then do the tweak multiplication on their own machines.


Will ask.  Actually, I think I may have this mentioned somewhere in GH discussions; I didn’t pay attention, because I don’t yet own any machines with AVX2.  Not quite as rich as people think I am. <g>

I myself will not try implementing such things, even the “really easy” ones.  I don’t have the CS background.  After tinkering for years, I learned programming by reading FreeBSD kernel code until I thoroughly understood almost everything except the CS-heavy subsystems (vm, scheduler, etc.).  I think you see that my code reflects the style you’d expect from that experience.  Otherwise, as in all else, I take pride in knowing enough to know the limits of my own knowledge.


Of course.  Avoiding unnecessary checksums is an easy optimization all around, though it will require some refactoring to open up a code path for that.  Also, I want to at least optionally support expressions such as 'qqqqqq$'.  I’ve had fun generating a few neat addresses that way.

Time to go code...

After playing around a bit, I decided that the sanest way (easiest for auditors) is to do this with a public fork.  I merged sipa’s 201802_grind branch into the current bitcoin-core/secp256k1 master:

https://github.com/nym-zone/secp256k1/commits/sipa_201802_grind

The code you will soon see show up in segvan will match the code you find there.

Thanks to gmaxwell for the tip!

---

Edit 2018-02-13 08:58 UTC:  As of an hour or two ago, I finished an initial working implementation with sipa’s key-grinder.  It compiles fine on Linux in the same tree where I ran autogen.sh; but the resulting configure/Makefile hork up errors when transferred to another system for tests.  I will update OP and bump the thread when I have real news to report.

The short version:  An untested, experimental branch of my code now finds a speedup of 5x for difficult patterns using sipa’s keygrind:

https://github.com/nym-zone/segvan/tree/sipa_grind

My code needs some work to take full advantage of this.  It will be worth it.  I wish I’d had this when making the addresses in my signature—well, perhaps soon I may make better addresses for my signature!


I’ve also been seriously mulling ideas for an online service which finds “vanity tweaks” for a private key held by a user—essentially, convenient results from rented time on powerful CPUs in the “cloud” (much though I loathe that word).  I’m curious as to how popular such a service could be.  Anybody interested?

---

(What took so long?  After whipping together a quick implementation, I had hours drained by the bane of my existence, GNU autoconf.  A hint at a solution was eventually found in a comment (not the answer) to a Stackoverflow question (https://stackoverflow.com/questions/24233721/build-m4-autoconf-automake-libtool-on-unix).  Then, I had to fix one of my own dumb mistakes.  —Then, speed test and explore the performance characteristics of this code.)

Allow me to knock your socks off:

Say you have N people who each want to find a vanity tweak of their pubkeys which will roughly take M million tries to find.

You can find all N of them with just ~M million tries, instead of the N*M million tries if they were to do them themselves alone.

Here is how.  Each person has a pubkey P_i,   they all come up with uniformly random tweaks T_i.  They tweak their keys, and send these resulting public keys to the hashing server. They keep the tweak and original pubkey private.   They also send the string(s) they want to match. They stay connected.

The sever takes all the strings and compiles them into a single match expression (which can be matched in log() operations at worst, probably better).

Then the server sums all the tweaked pubkeys and grinds on it comparing the output with the omnibus matcher.

When it gets a hit  it then demands all clients except the one with the match to tell them the private keys for their tweaked keys (this reveals nothing about the original private key, since it's been tweaked).    It then sums up the tweak it found and everyone elses private keys and gives that to the lucky user.

Everyone remaining sends new tweaked pubkeys  (probably in the same message they sent their prior private keys).  They get summed and the process continues with the new basepoint.

If someone fails to send their private key, you kick them off and ban them and you lose that result because you cannot reconstruct the tweaks without everyone elses keys.

Implemented correctly this is completely secure.

You could even have the individual users perform their own grinding.  So if they all had computers of the same speed, they effectively get an N fold speedup in how fast they find solutions.

To discourage abuse you could require a new participant grind without submitting their own keys and patterns for a while... There found tweaks prove the work they did, once someone has done enough you can give them a token they can use to submit a pubkey and pattern(s) for matching, if that user fails to reveal, you ban it.  They can rejoin ... but they have to do free work to get a new code.

I haven't previously implemented it because the protocol minutia with tracking and banning and whatnot is a PITA and only the mathematical part is interesting to me. :)

That, you did.  Too bad I could not deploy technical means to express as much, as I promptly attempted:


Thus instead, I’ve been trying to work out how best to refactor my code now to potentially support this feature and similar later.  (Also, I am trying to work out an adequate test system so I can freely add features without risk of burning Other People’s Money (https://bitcointalk.org/index.php?topic=2940686.msg30295658#msg30295658).)  Nothing is in the public repo, as of yet; it’s more of a “back to the design phase” thing, and I believe in trying to keep my scratch work in my own bitbucket rather than spreading it to everyone’s.  I want to be able to plug in one-at-a-time key generation search, sipa’s keygrinder, trustless client-server “vanity tweak” generation, this (which I’ll call it a trustless pool batch tweak generator), and any other key/tweak generation methods which may arise—without substantial code copypaste.

As for the rest, I’ll try to be brief (good luck), since I should code it instead of chatting about it:


Thus in code terms, clients do secp256k1_ec_pubkey_tweak_mul(ctx, P_i, T_i).  (Not looking for handholding here; I just want to confirm my understanding in terms which will compile.)

Question:  Can anybody cause problems of any kind by using nonrandom T_i and/or P_i with interesting properties?  I think not, but wish to confirm.


Side note:  I’ve been mulling a better regex system.  Something simple and fast (https://swtch.com/~rsc/regexp/), and also secure for use with expressions from untrusted sources.  I like sticking with POSIX <regex.h>, because I always try to minimize unnecessary dependencies.  But if trying to match expressions from multiple people, it would make sense to use a library which could compile multiple expressions into one match program without hackish text manipulation à la snprintf(... "(%s)|(%s)|(%s)" ...).

This problem is made worse by unpredictable behaviour in identifying submatches with nested parentheses.  Discussing backreferences, FreeBSD’s regex(3)’s BUGS section (https://www.freebsd.org/cgi/man.cgi?query=regex&apropos=0&sektion=3&manpath=FreeBSD+11.1-RELEASE&arch=default&format=html#BUGS) blames this on vagueness the POSIX standard; and the problem is confirmed by my experience.  Reliable identification of top-level submatches would be an absolutely necessity here, for obvious reasons.

Does there exist a secure, efficient library offering multi-expression composite compilation and reliable submatch numbering?


secp256k1_ec_pubkey_combine() over array of all received keys, then secp256k1_ec_grind() with the result as “master” and server-generated random seeds.

Question:  If the server’s PRNG is broken (whether through malice or incompetence), does this affect user security?  IOW, do users need to trust the server for that?  I don’t think so, but I want to be sure.


I don’t see any _privkey_combine() function.  Could the server iteratively loop secp256k1_ec_privkey_tweak_add() over all received private keys, plus the generated tweak?

The lucky user does the final secp256k1_ec_privkey_tweak_mul() on his original private key (since the result generated by the server is based on his T_i from the initial step).


So, pure P2P.  I will try to remember not to bolt a DHT onto it (https://bitcointalk.org/index.php?topic=662734.msg7521013#msg7521013) unless I have some extreme form of Sybil resistance. <g>


To protect the privacy of users who may wish to generate different vanity addresses for unlinked nyms, this could be handled with a blind signature token system.  However, a relatively modest project then grows a significant layer of complexity.

Good behaviour in submitting private keys when asked could be easily tracked anonymously with such a token:  Send a private key when asked, receive a sent_private_key token.  The problem with using that for tracking work in a P2P system is the same as with exchanging work generally:  How to prove that the work was done?  I am thinking that in exchange for tokens, users could provide lists of distinct matches they have found for e.g. the output public key’s Hash160 starting with n zeroes (for some medium-sized n).  For each submitted POW match, receive a POW token.

Submitting a search expression costs one sent_private_key token, plus a number of POW tokens.  Since I am far from implementing this particular feature, I’ll wave my hands over that number for now—and over the question of whether this could be done without a server, or at least a semi-trusted supernode, who could be trusted to not cheat the token system (but trusted with nothing else).


I enjoy daemonology, and I am limited in the higher maths.  So, that works for me.  I don’t know how much time I’ll be able to sink into this, when I should be coding a commercial service (some productive hackery of TLS protocol minutia) I have on the backburner; but it seems I’ve inadvertently stumbled into what could become a very popular utility if done right.

---

General design note:  I would aim for the cleanest feasible separation between the key-handling code and the network exchange of data.  I do dislike how Bitcoin marries the wallet to the network node; it’s a smaller issue with well-written code (thank you gmaxwell for all your refactoring work), but I still prefer process isolation.  In addition to memory separation, this also permits application of OS-specific sandboxing features such as capabilities mode, where supported.

Thus, I will write new code with an eye toward eventually running a secrets-handling process with no network access; and that process can use various methods (https://www.freebsd.org/cgi/man.cgi?query=shm_open&sektion=2&apropos=0&manpath=FreeBSD+11.1-RELEASE#DESCRIPTION) to exchange non-secret data with a network process which has no access even to the filesystem (let alone any secret keys).  The sandbox APIs are simple and easy on FreeBSD and OpenBSD.  I would accept well-written patches for Linux.  AFAIK, there is no such feature on Windows.  I don’t know anything about Mac.

---

Thanks again for the hardcore tech talk.  This is the forum I’ve said “I wish I could now experience” (https://bitcointalk.org/index.php?topic=2818350.msg29314081#msg29314081)!  I know that a post is most valuable when it takes me all day to digest it, mull its potential implications, and formulate proper questions in response.

Nullius great project I wish you the best of luck

Just wanted to put this out there for window users looking to generate non-native segwit / native segwit vanity addresses
you can follow this guide "https://www.youtube.com/watch?time_continue=229&v=YiMU_gtRrBQ" unfortunately the speed is slow
but if your a noob and have 0 linux experience like me it honestly wasn't that hard. It took me about 8 hours to generate the pattern a 4 letter pattern

If I were to attempt to write a similar program in Rust, are there documents anywhere that outline how I could generate keypairs efficiently like this?

If you have a foreign-function interface which can talk to C code, <secp256k1.h> has extensive comments explaining its proper use.  You may also use segvan.c as a concise guide—both for secp256k1 library use for generating public keys, and for the quite simple procedures for generating different address types.  I am currently amidst a major refactor and reorganization of the code (much delayed by recent business in Meta, etc.—sorry).  I will try to keep in mind that others may wish to use segvan code and comments as documentation for how to do these things.  I am also happy to provide tips and answer questions for other intelligent implementers, insofar as I am able.  (There’s nothing secret to what I’m doing here—and the one who actually writes the best code should get the most users!)

I would not recommend trying to implement your own secp256k1 library, unless you have extensive knowledge of both cryptography and computer science.  That said, if you want to study how this works, Dr. Wuille’s code (currently maintained it seems mostly by him (sipa) and gmaxwell) is concise and clear for those good at reading C code.  The secp256k1_ec_grind() function made famous by this thread fills less than 4 screenfulls when reading it with less(1) on a standard terminal.  That should provide a very exact answer to your specific question.  N.b. that to my understanding, the endomorphism performance increase bits may allegeably raise software patent questions (https://bitcointalk.org/index.php?topic=3008251.msg30937407#msg30937407) in some jurisdictions; they are marked “experimental” (remember that secp256k1 is a research library!), and should only be compiled in if you are doing research and/or you are not under the jurisdiction of whatever possible patents.  It is wise to protect users this way.

(Note:  This is one reason I like to write in C.  Most of the most awesome libraries have native C interfaces.  So it has been for decades, and so it will be for at least decades more.  Other languages come and go—so to speak.)

Nice work on the segwit vanity gen!
However, im currently facing some trouble as i cannot find any decent documentation about how this script works:

It's missing the --help argument, so what are the programmed options for this, and how do i use this?
Also, can i use the segwit addresses with electrum?

My apologies.  I usually publish software with a manpage, plus a usage info printout on entry of incorrect options; but in this case, I consider the options interface to be unstable.  It may change.  For now, here is an ad hoc rundown of (only) the most important options:


The two modes are exclusive of each other.  However, within each mode, different address types can be handled simultaneously.  If you want to search for both "3" addresses and bech32 addresses, each key tested will be tested against both patterns.

For bech32, case-insensitive search is always used (regardless of options) for reason that Bech32 addresses themselves are case-insensitive.

Patterns are POSIX Extended Regex (not PCRE or similar).  No attempt whatsoever will be made to prevent you from searching on an impossible pattern.  If you enter a pattern which cannot be matched by a valid address, then segvan will spin forever.

Upon SIGINT (Ctrl-C in the terminal), segvan will gracefully exit after it has finished the current iteration.  SIGINFO (on BSD) or SIGUSR1 (Linux) will print statistics to stderr.

Addresses and WIF-encoded private keys are output together on an output line, with an intervening tab.  This is intended to be friendly for piping through shell scripts.

By default (which may change), private keys use a WIF version which is specific to Electrum, and tells Electrum which address type to use.  This has been tested by me with Electrum 3.

There is currently no multithreading.  Vanity search is probabilistic, with no state or need for synchronization between search threads; therefore, you can get similar performance to what multithreading would provide by running one segvan process per CPU core.

More options exist, but I am reluctant to document them before they’re stable.  Also, there is a hidden option for generating old-style P2PKH “1” addresses.  I’m not sure whether I want to document that, because I desire to promote Segwit use.  At present, the only valid reason for generating new P2PKH addresses is if you need a Bitcoin key which can be used to sign arbitrary messages, such as forum “stake” messages.  (For that particular purpose, I suggest staking a PGP key instead.)

I hope this helps.  Please be advised that a major update is planned; it has been stalled the past week or so, due to some unfortunate and irrelevant distractions.  For now, the code in the master branch is non-feature-complete, but reliable for use; and the code in the keygrind branch is working, but not fully tested.

I just really need to figure this out already. I need more time in the day to go over this over and over until I can run it normally. Thanks for creating it and I'll be sure to post my address some day when I finally figure out what I'm doing  ;D

I'd be interested in a service like that. Please could you PM me if you ever get round to doing it? Thanks :)

If you want this to become more popular like vanitygen original version, you need to make windows version of it.
Most users using Windows while generating their private keys. You need above average knowledge to compile it yourself and use linux.

I just used segvan to find 3Jjjjj8466bZXCFJQGDk1reaAXwrri39Vz, 3AAaAAMy2auJ1c5wCRj7Qbzx8qshh9cVrx and 3FffFFLntXU14ePkYK3pyASx2Smaw5TfF1 :)

Unfortunately I had to build from master instead of the sipa_grind branch so I think I'm missing out on the huge performance improvements. Is the sipa_grind meant to be working right now?

What do you mean by that?
Native segwit addresses are done by this kind of command:


And P2SH or standard segwit addresses (P2SH) with following pattern:

All of those are done with the same pattern, allthough different kind of options. The later on option with "-R" is supported by more people, rather than the standard segwit addresses shown by the first pattern. Im not that familiar with nullius's segwit address vanity generator, but feel free to quote or PM and ask questions if you have any problems.
Im not really that experienced with this script, and probably nullius will be able to advise you better.

Best Regards, Sellingaccs

Sorry, I meant that everything was working fine, but after reading some previous posts I thought that there would be some magic performance improvements hidden away in the sipa_grind branch to try before I started throwing a load of hardware at finding some nice addresses.

So do you need help compiling that btach, or what is your point?
If you need help compiling, i will need to know your linux distribution for it.

Let me know if you need such a help via PM, and i will post the guide here publicly (will compile through a VM (Virtual Machine)).
To me it seems just very unclear what kind of help you need here, if you need any.

pc@pc:~/segvan$ ./segvan -r accs

Hi "Michael",

Hope you are doing well.  If you still need access to AWS, please DM me and I can provide that.

Best regards,
Ben

Nice work. I used the faster branch of Segvan to generate a few addresses in the last day and a half on my Ryzen CPU with 8 instances. The string I wanted was computationally difficult to come by. It probably would have taken forever on Vanitygen, if gmaxwell's post is anything to go by.

Old thread, but pulled this up as I've been trying to make a segwit vanity address and this seems to be the best option now. I know this is a fairly big gravedig but I'm currently using this on an eight-core cloud machine (with all egress blocked) to try to find a vanity address containing 'Diamond' - now trying to just make one with 'DCardz' at the start to save time.

https://i.gyazo.com/534e61fcf13c357660d62c80874997bc.png
(I've since gone from running it on 8 cores to 12 cores)

I've tested it with smaller addresses and it works well. I wonder where the original creator went, though. Are there any alternatives to segvan which are being maintained by members of the community who are still active or is this the main option? Anything faster floating about perhaps?

Leaving the previous for posterity but I've now realized that Jean_Luc (https://bitcointalk.org/index.php?action=profile;u=2550169) maintains a vanity address generator that supports segwit. Github link is here. (https://github.com/JeanLucPons/VanitySearch) It doesn't appear in searches however, while this one appears quite high. Hopefully by posting on this people who are looking for a segwit vanity generator will see this post and be redirected