Why is mining a pubkey maybe cryptographically dubious?

[gwillen]

I had trouble finding where the note to this effect was originally added to the documentation. I was hoping for some kind of explanation of just how dubious.

[jb55]

On Wed, Sep 13, 2023 at 03:29:19PM -0700, Glenn Willen wrote: I had trouble finding where the note to this effect was originally added to the documentation. I was hoping for some kind of explanation of just how dubious.

I'm not sure if it is or not. It is just a statement of ignorance.

[gwillen]

Well, I was specifically wondering what would make it more dubious than just regular key generation. After reading the source, I'm assuming it's about the fast trick for generating the next candidate, at the bottom of the loop?

[jb55]

On Fri, Sep 15, 2023 at 01:08:52PM -0700, Glenn Willen wrote: Well, I was specifically wondering what would make it more dubious than just regular key generation. After reading the source, I'm assuming it's about the fast trick for generating the next candidate, at the bottom of the loop?

I think I was wondering if grinding a pubkey with a certain number of leading zeros would reduce the uniformity of the keyspace or something, and if that opened it up to some kind of attacks. I didn't think it would be an issue but I'm not sure becase I'm not cryptographer. The xor thing seemed fine? I hope? =/

[gwillen]

I am also not a cryptographer but I have worked with a few. I'm pretty sure grinding itself is fine, I'm pretty sure I had cryptographically-knowledgeable ex-coworkers who used bitcoin vanity addresses (which are ground like this.)

The xor thing is kind of sus to me, in the way of "I'm pretty sure it's fine; I couldn't come up with anything wrong with it in 5 minutes of thinking, which was enough for me to use it; but I would run it by a cryptographer to be sure."

I can try to get one of of my Blockstream ex-coworkers to look at it if you like.

[jb55]

On Sat, Sep 16, 2023 at 02:39:12PM -0700, Glenn Willen wrote: I am also not a cryptographer but I have worked with a few. I'm pretty sure grinding itself is fine, I'm pretty sure I had cryptographically-knowledgeable ex-coworkers who used bitcoin vanity addresses (which are ground like this.) The xor thing is kind of sus to me, in the way of "I'm pretty sure it's fine; I couldn't come up with anything wrong with it in 5 minutes of thinking, which was enough for me to use it; but I would run it by a cryptographer to be sure." I can try to get one of of my Blockstream ex-coworkers to look at it if you like.

sure! thanks!

[apoelstra]

There is no problem grinding a secret key to get some property of the public key, as long as the only thing you're filtering for is a pubkey property. (If this were a problem, then an attacker could e.g. scan the Bitcoin blockchain for public keys that naturally had a lot of 0s, and then apply whatever attack your grinding supposedly enabled, and normal non-grinding public key cryptography would be vulnerable. At least in a world where there were lots of public keys. But it is not, so you are fine.)

But this xor thing does seem super weird, and this tactic of repeatedly generating fresh independent keys is extremely slow. You should be able to get a multiple-hundred-times speedup by using e.g. bitcoin-core/secp256k1#507

[apoelstra]

Because it is not otherwise linked here, the grinding code is at

nostril/nostril.c

Line 255 in 8726ad3

static int generate_key(secp256k1_context *ctx, struct key *key, int *difficulty)

[jb55]

On Sun, Sep 17, 2023 at 06:36:26AM -0700, Andrew Poelstra wrote: There is no problem grinding a secret key to get some property of the public key, as long as the only thing you're filtering for is a pubkey property. (If this were a problem, then an attacker could e.g. scan the Bitcoin blockchain for public keys that naturally had a lot of 0s, and then apply whatever attack your grinding supposedly enabled, and all of pubkey cryptography.) But this xor thing does seem super weird, and this tactic of repeatedly generating fresh independent keys is **extremely** slow. You should be able to get a multiple-hundred-times speedup by using e.g. bitcoin-core/secp256k1#507

happy to drop it, I'll look into applying this patch locally if it hasn't bitrotted.

[apoelstra]

@jb55 even if the patch does not apply, you can get a speedup by using the public API to repeatedly call pubkey_tweak_add and seckey_tweak_add with the same fixed value (say, 1). This should still give you a massive speedup, though it will still leave a lot of performance on the table.

[jb55]

On Sun, Sep 17, 2023 at 08:01:29AM -0700, Andrew Poelstra wrote: @jb55 even if the patch does not apply, you can get a speedup by using the public API to repeatedly call `pubkey_tweak_add` and `seckey_tweak_add` with the same fixed value (say, 1). This should still give you a massive speedup, though it will still leave a lot of performance on the table.

oh! ok that makes sense. If someone reading this wants to PR that I would appreciate it.

[melvincarvalho]

I think I was wondering if grinding a pubkey with a certain number of leading zeros would reduce the uniformity of the keyspace or something, and if that opened it up to some kind of attacks. I didn't think it would be an issue but I'm not sure becase I'm not cryptographer.

Just on this.

Choosing a public key with a vanity pattern doesn’t weaken the elliptic-curve maths, because you are searching for the privkey which will still be the same entropy. So long as that is generated randomly, you are safe.

Regarding the speedup, here's a web version I made, that lets you have various prefixes on your key, and is multi core.

https://melvincarvalho.github.io/noskey/vanitygen.html

Its quite fun, because it also allows you to use your current npub (login with nostr) and get a new vanity address. People can then send coins to that vanity address and it's very hard for an observer to link the two. Users can also have as many vanity addresses as they want seeded from their npub.

If I get time I'll have a look at the PR and see if it can do a speedup. Basically EC_ADD is cheaper than privkey to pubkey