Challenging Proof of Work with DER Signatures

Using OP_SHA256 OP_CHECKSIG seems too basic for a quantum context. It'll show us if there's a problem but lacks depth. I came up with a more layered approach for that reason... remember to use minimally encoded CScriptNum when dealing with Proof of Work scripts!

From what I know about Shor's algorithm, figuring out discrete logs on small curve points shouldn’t be simpler than on any others. It’s still limited by the 256-bit curve order. To really gain an edge, we’d need a curve with a smaller order, which Bitcoin doesn’t support.

Exactly. We've got OP_CHECKSIG and secp256k1 at our disposal. If someone can cash out from an OP_SHA256 OP_CHECKSIG TapScript, they can solve my puzzle too. Having a private key linked to a low x-value public key could shrink the r-value from 21 bytes to just 1 byte, making it super easy to sweep.

Wait, what’s the actual challenge here? Is it about mining a specific nonce to get a low X (r) value, which in turn cuts down the signature size?

Check out my examples on testnet4 where I showed how some addresses are actually spendable. It's about the security of secp256k1 and SHA-256. Each signature is two-part: (r,s). If you're using half the generator and k=(1/2), the r-value is tiny... lets you create a DER signature that’s just 60 bytes.

Got it, you’re doing a vanity search on the s values to find the private key for the UTXO. Sounds interesting, I might try that.

Right now, that’s the deal. But it'll shift to a vanity search on r-values when s-values become tricky. Repeating r-values exposes the k-value, letting everyone figure out how to make smaller signatures if a solver reveals it twice.

Swept 60 and 59, but convincing the transaction bytes to comply with the witness script was tough. Feels like the harder it gets, the lesser the reward. Was that the intention?

The point was to store Script info under P2WSH somehow. The amount you use ties to the signature size. I just went with a basic approach, didn’t think too far ahead about profitability.

Some highlights from my notes... DER encodes negative values with an extra byte, meaning PoW effort doubles. Found the 3 bytes puzzle after over 33 million hashes instead of 16.7 million. Also, the two nonces (-1/2 and 1/2) doubles the S candidates.

Yeah, but don't forget the s-value should be less than a certain threshold or it'll be non-standard. You’ll need to talk to miners directly for that. Plus, grinding low z-values works, but you could also tweak around with bigger numbers.

So far, I’ve done four sweeps with -1/2 as the nonce. AFAIK, ECDSA automatically handles S normalization below N/2. The output scriptPubKey was the first thing I altered to mine for shorter S values.

You could tackle this by making Proof of Work optional. I avoided that to prevent random stops in sweeping everything, but if you're up for it, there are many ways to attach PoW to your scripts.

Check this link for an example transaction with some OP commands. I’m only sharing it to show how this could get harder with hash functions.

Quick update on my progress for those interested: Puzzle #1 was solved in Python, single-thread, about 4000 sig/s. Puzzle #2 had the same speed. Puzzle #3 hit 200 Ksig/s, and Puzzle #4 jumped to 32 Msig/s thanks to switching to C.

That’s nice! The next puzzles are getting done faster. Though, I bet soon it’ll take ages to clear the next ones. At some point, fighting for tiny rewards might not be worth it.

Just got lucky, wrapped it up in less than 3 hours. Next puzzle costs about 150 bucks to solve, so I’ll pause for now.

Feel like testing transaction sponsorship could bring in an extra 200k sats? The transaction is signed with SIGHASH_NONE, so it should only work within this puzzle.

We might need a different nonce since nLockTime is signed. But using OP_RETURN could allow some grinding, and nSequence might be unsigned too.

This adds some hassle since you have to recalculate the outputs hash with every OP_RETURN change. That means more SHA256 calls, which slows everything down. And yes, nLockTime affects the signature, so performance might take a hit.