Proof of Work transaction puzzle, based on DER signature size

[kTimesG]

Assuming you got everything

Code:

Message: Solved by kTimesG

bc1qf7s6suv8pz75wc2u03gt77updt027zpuh50gh8
H4/TvPTO9h0nLwtNI56Y3P1k1GpcMxTIAOz9PWP7daDVBCl+6nt5XcxMpU6fs0mQvNuMRtNWxrCwicORYht7Gxk=

bc1q3mugyjeryqhcewtqrm47xnqs5rvxpphhpyezdc
IESzjsROAjA3rRYWMXaaaJ+7V3JxZL5cOO3oFnH9MDShdfj3yWbbHhD9GXn9Gjq/0I2J1n8CtmXBECAHt5ZdWHU=

bc1q3vyxfxg0u9gr8qecep59kac5w6f5cqqq7vxcc0
IIBROsMd2NI7rKMwxX2IctIvuWr1Qx+EgBIiOYMNtwErUuVOVNM0dBCD1Vh1blcLtX9mr87sjgLHRZLC+a+YCmc=

bc1qp90rk2uy7wwp29qxjm6uhvsgrr9s524c2rvmam
IEHKeCCIUb6UTC7S0LPzWF2utP+oGfxn8rNJWj/eVakqXfLfvnX1zOEfmWs0ad+mh44n1Q8AsErL2FordgWPM1E=

bc1q2rhvdwk2xq6es73r2msxnsqawrw26vnkpsfj82
H2VvI4X24IL40pUoEbXRHk2nujlu09J2j4obyjV43lZ9DzcSYs+/FVsvMI597B02ZwW8/pugQqUHS2jie6aXX5o=

bc1qpuddz0h4nr4gcv43ymjgay9wxdrhh9une9nt3p
H9z22sNtcp+8mMhDS+U6/0VDlkT6zqYfHbNGTsgtQt9FE0L3pEFUp9UVHYb3SkpHXed/b9v7ok+meB6zG2X3W7s=

bc1qlv4nl3cfc8jxaulxe7gqvj32p02hp5tzhk4c72
IJNd2jrvZfbLmumHrZDKNhvCQBOwW6BLieU7FbcnYZ7lewzFxepvG4fQnRRrkOHl/7Gt0HsBUtlQLfF14LBz9Wk=

[AbadomRSZ]

yo\(~

57-bit DONE after 8 days!

The found S actually had 58 leading bits of 0 (57 were enough).

Code:

MSG = 020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d20000000000003d74fbff045b0f32c7adb53ce93b424e7ba280a4328ef880b60058c771b3ef599f9e95840000000081000000
Z = ffffffffffffffedfe243987a5dfa917a1bba0978fd5ce30e6df1b23cf1d8fc4
S = 000000000000002403b78c79c2a4014f1ea49d7614fa4fc457cb59250f722a34

https://talkimg.com/images/2025/08/04/UH9t4a.png

Server logs...

Code:

New key: 0x524f8523a3e703801c
baseKey: 524f85230000000000
GPU GE1 idx: 41877
Extracted k for OP_RET: 524f8523a3e6ca801c launches: 5
OP_RET = 796f145c28bad77e = 8750234987057043326
Found nSequence: 4294669373 at iteration 297922 / 933888
SIG: 303202153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c6302192403b78c79c2a4014f1ea49d7614fa4fc457cb59250f722a34
Z: ffffffffffffffedfe243987a5dfa917a1bba0978fd5ce30e6df1b23cf1d8fc4
Fast S1: ffffffffffffffdbfc4873863d5bfeaf9c0a3f709a4e507768070567c0c4170d
Fast S2: 000000000000002403b78c79c2a4014f1ea49d7614fa4fc457cb59250f722a34
Sig len: 52 (+1)
S1 score: 0
S2 score: 58

And total running stats....

Code:

      Total jobs: 30314
    Scanned keys: 29606598993248256 = 29606 trillion
   Total results: 117

So that was around 59212 trillion signatures.

Total costs: 110 $

This was emotional. Up to the lucky hit, the best results that I got were all 54 bits or less, and I was starting to wonder whether the risk is worth it. Then 58 hit hard to compensate for the unexpected bad results

Did you create the repository for the application used?

[kTimesG]

Did you create the repository for the application used?

For the 57-bit, I already had 99% of everything that was required, I only tweaked the worker nodes code to solve this specific problem. If you're wondering whether any of the four huge projects, that were required for this adventure, are up on the internetz, no, they're not. I think the discussion here is more than enough for anyone to understand how the challenges were solved.

[stwenhao]

Some untested ideas for other Proof of Work scripts:

Code:

decodescript 82013d0146a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac
{
  "asm": "OP_SIZE 61 70 OP_WITHIN OP_VERIFY 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 OP_CHECKSIG",
  "desc": "raw(82013d0146a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac)#mes5v53f",
  "type": "nonstandard",
  "p2sh": "2Mw2fy8vwiyUKhVFrrD6VzXUahLTwr6P2nZ",
  "segwit": {
    "asm": "0 55582b7319de48ac18d654fba1400d417fa9249e3ba454fdb033b8937f5363d7",
    "desc": "addr(tb1q24vzkucemey2cxxk2na6zsqdg9l6jfy78wj9fldsxwufxl6nv0tspelg8s)#5rzugfva",
    "hex": "002055582b7319de48ac18d654fba1400d417fa9249e3ba454fdb033b8937f5363d7",
    "address": "tb1q24vzkucemey2cxxk2na6zsqdg9l6jfy78wj9fldsxwufxl6nv0tspelg8s",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "2NEBNyCcTMriMw346rwgvQ7yxPHZ5PUQVUH"
  }
}

Assuming standardness rules are enforced properly, and signatures should be minimal, or they are otherwise invalid, it should give an incentive to grind alternative points to half of the generator:

Code:

+--------+----------------------------------------------------------------+--------------------------------------------------------------------------------------+
| Number | Address                                                        | Script                                                                               |
+--------+----------------------------------------------------------------+--------------------------------------------------------------------------------------+
|     70 | tb1q24vzkucemey2cxxk2na6zsqdg9l6jfy78wj9fldsxwufxl6nv0tspelg8s | 82013d0146a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     69 | tb1qg57rdw4sl24cddmxghwd0dewgkzh55nracgfycz57hgzt0dsadhsz4wq6a | 82013d0145a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     68 | tb1q777srl54ha3mauekxvz9p3qlvcz92za66p2lhc3gnnrp37ljcjasryuegs | 82013d0144a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     67 | tb1qd07mp98yc2n9vna7ue0fk7645ecuf54uzn8rm08m8zj5u778hexspncvqd | 82013d0143a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     66 | tb1qzvsxvwf4d6fcmsx7v6jj7xmwdtwr9knjud95gsndr3e5cmgsgwpqlky0z5 | 82013d0142a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     65 | tb1qxstamf0k9c89m7gmk5fknxsr2qwxgtdlljp2q4mm3m76l95plp3qx05ge2 | 82013d0141a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     64 | tb1q6eefcrmcfu4uh05luuejmhfq2u3c5qmwytlmcc9kylccvlqfdelsdsrdvh | 82013d0140a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     63 | tb1qwluz4cqyu0nrm0cyrg94hp9y48z3lr4h6g9faa9afkr04lhtvuas73z02z | 82013d013fa569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     62 | tb1qk53l375y9pw84dcddx4sxax7dy6k08udzm8nt5dqwldhxtuck56qaamcw8 | 82013d013ea569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     61 | tb1qxydp6gqyttdn55n57czq3w9q79v7vgdtgh7j3u33flhepwglskas506hqj | 82013d88210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac       |
+--------+----------------------------------------------------------------+--------------------------------------------------------------------------------------+

And also, some hash-based Proof of Work:

Code:

+------------+----------------------------------------------------------------+--------+
|   Function | Address                                                        | Script |
+------------+----------------------------------------------------------------+--------+
| RIPEMD-160 | tb1q7l4c7xqjnc5uxzawu0nu7tld8g7209xcmv8xqj0ks8844jf9cstsz8ule9 | a67cac |
|      SHA-1 | tb1qwaarn9ss7znnrqr44r2jrku43nc3w38xvmarf7pecpj9uqpccguqvzpn9y | a77cac |
|    SHA-256 | tb1qx6ylc8wx4t0cu40tdy7d49zntjxwrk0tusmg7c9p22aprzlu9e7s58cm30 | a87cac |
| OP_HASH160 | tb1qesygpz74dkk94xqh7fhu368m5mycxaurap7rlcdgjt9l6spwf46ql0gu2p | a97cac |
| OP_HASH256 | tb1q3dzkf4xr7c4sg9d3hz8a0j45mdkuztsvrqjf2lp0z2r30ugj3f4s7d4sn3 | aa7cac |
+------------+----------------------------------------------------------------+--------+

In this case, some message is hashed first, and then, the hash should form a valid DER signature, which means grinding something around 56 bits (maybe a bit less, because there are six valid sighashes, so it is more like 54-bit hash).

Code:

decodescript a67cac
{
  "asm": "OP_RIPEMD160 OP_SWAP OP_CHECKSIG",
  "desc": "raw(a67cac)#03cp3pdm",
  "type": "nonstandard",
  "p2sh": "2N56nsSzfvJTvdtXmfyRg8PiUDD9X4BrkFD",
  "segwit": {
    "asm": "0 f7eb8f18129e29c30baee3e7cf2fed3a3ca794d8db0e6049f681cf5ac925c417",
    "desc": "addr(tb1q7l4c7xqjnc5uxzawu0nu7tld8g7209xcmv8xqj0ks8844jf9cstsz8ule9)#hltrrgm6",
    "hex": "0020f7eb8f18129e29c30baee3e7cf2fed3a3ca794d8db0e6049f681cf5ac925c417",
    "address": "tb1q7l4c7xqjnc5uxzawu0nu7tld8g7209xcmv8xqj0ks8844jf9cstsz8ule9",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "2MzT76E56RTHJVcjjMZG5dUe8XC56Dj5hdT"
  }
}

Edit: It seems that picking a given difficulty can be delegated. For example:

Code:

 Input: <puzzleSignature> <sponsorSignature>
Output: OP_SIZE OP_TOALTSTACK <sponsorKey> OP_CHECKSIGVERIFY OP_SIZE OP_FROMALTSTACK OP_LESSTHAN OP_VERIFY <puzzleKey> OP_CHECKSIG

Execution:

<puzzleSignature> <sponsorSignature>
<puzzleSignature> <sponsorSignature> <sponsorSignatureSize>
<puzzleSignature> <sponsorSignature>
<puzzleSignature> <sponsorSignature> <sponsorKey>
<puzzleSignature>
<puzzleSignature> <puzzleSignatureSize>
<puzzleSignature> <puzzleSignatureSize> <sponsorSignatureSize>
<puzzleSignature> OP_TRUE
<puzzleSignature>
<puzzleSignature> <puzzleKey>
OP_TRUE

And then, sponsor can sign a given transaction, and the solver has to provide a signature, which would take less bytes. Which means, that solver's signature is 256 times harder to generate than sponsor's signature. Also, the size of the required signature can be chosen dynamically. For example:

Code:

 Input: <sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <sig6>
Output:

<key6> OP_CHECKSIG OP_DUP OP_ADD OP_TOALTSTACK
<key5> OP_CHECKSIG OP_FROMALTSTACK OP_ADD OP_DUP OP_ADD OP_TOALTSTACK
<key4> OP_CHECKSIG OP_FROMALTSTACK OP_ADD OP_DUP OP_ADD OP_TOALTSTACK
<key3> OP_CHECKSIG OP_FROMALTSTACK OP_ADD OP_DUP OP_ADD OP_TOALTSTACK
<key2> OP_CHECKSIG OP_FROMALTSTACK OP_ADD OP_DUP OP_ADD OP_TOALTSTACK
<key1> OP_CHECKSIG OP_FROMALTSTACK OP_ADD OP_10 OP_ADD OP_TOALTSTACK
OP_SIZE OP_FROMALTSTACK OP_LESSTHAN OP_VERIFY <puzzleKey> OP_CHECKSIG

Execution:

<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <sig6>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <sig6> <key6>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <range(0,1)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <range(0,1)> <range(0,1)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <range(0,2)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <key5>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <range(0,1)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <range(0,1)> <range(0,2)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <range(0,3)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <range(0,3)> <range(0,3)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <range(0,6)>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4>
<sigPuzzle> <sig1> <sig2> <sig3> <sig4> <key4>
<sigPuzzle> <sig1> <sig2> <sig3> <range(0,1)>
<sigPuzzle> <sig1> <sig2> <sig3> <range(0,1)> <range(0,6)>
<sigPuzzle> <sig1> <sig2> <sig3> <range(0,7)>
<sigPuzzle> <sig1> <sig2> <sig3> <range(0,7)> <range(0,7)>
<sigPuzzle> <sig1> <sig2> <sig3> <range(0,14)>
<sigPuzzle> <sig1> <sig2> <sig3>
<sigPuzzle> <sig1> <sig2> <sig3> <key3>
<sigPuzzle> <sig1> <sig2> <range(0,1)>
<sigPuzzle> <sig1> <sig2> <range(0,1)> <range(0,14)>
<sigPuzzle> <sig1> <sig2> <range(0,15)>
<sigPuzzle> <sig1> <sig2> <range(0,15)> <range(0,15)>
<sigPuzzle> <sig1> <sig2> <range(0,30)>
<sigPuzzle> <sig1> <sig2>
<sigPuzzle> <sig1> <sig2> <key2>
<sigPuzzle> <sig1> <range(0,1)>
<sigPuzzle> <sig1> <range(0,1)> <range(0,30)>
<sigPuzzle> <sig1> <range(0,31)>
<sigPuzzle> <sig1> <range(0,31)> <range(0,31)>
<sigPuzzle> <sig1> <range(0,62)>
<sigPuzzle> <sig1>
<sigPuzzle> <sig1> <key1>
<sigPuzzle> <range(0,1)>
<sigPuzzle> <range(0,1)> <range(0,62)>
<sigPuzzle> <range(0,63)>
<sigPuzzle> <range(0,63)> 10
<sigPuzzle> <range(10,73)>
<sigPuzzle>
<sigPuzzle> <sigPuzzleSize>
<sigPuzzle> <sigPuzzleSize> <range(10,73)>
<sigPuzzle> OP_TRUE
<sigPuzzle>
<sigPuzzle> <puzzleKey>
OP_TRUE

Of course, pre-signing a transaction with a given address is much easier, but by exploring such examples, I am curious, what else can be built on top of it. Because I didn't expect, that the result of OP_CHECKSIG can be used as a number. And that also means, that OP_CHECKLOCKTIMEVERIFY, and OP_CHECKSEQUENCEVERIFY can be also executed on top of some OP_CHECKSIG result, which means, that it is possible to use dynamically picked locktime.

Edit: OP_WITHIN works fine, but people should be aware, that range from 61 to 70 means "greater or equal than 61, and less than 70". Which means, that "within 61 and 62" is the same as "equal to 61", and tb1qk53l375y9pw84dcddx4sxax7dy6k08udzm8nt5dqwldhxtuck56qaamcw8 is as hard to move as tb1qxydp6gqyttdn55n57czq3w9q79v7vgdtgh7j3u33flhepwglskas506hqj (which I didn't expect). But anyway: it works! See: https://mempool.space/testnet4/tx/5266048f001ffb92d5a00f0c5b197e8d103f15a94478744cbe38d96b30968f05

[ertil]

I read that topic about Proof-of-work based signet faucet yet again, and I think your Proof of Work puzzle can be improved, to have dynamically assigned difficulty, picked by miners. For example: if you allow any user to use any signature size at all, and you combine it with OP_CHECKSEQUENCEVERIFY, then anyone will be able to move these coins, but the smaller the signature, the faster it could be confirmed on-chain.

For example:

Code:

OP_SIZE <timestamp> OP_ADD OP_CHECKLOCKTIMEVERIFY OP_DROP <pubkey> OP_CHECKSIG

Or:

Code:

OP_SIZE <timestamp> OP_ADD OP_CHECKSEQUENCEVERIFY OP_DROP <pubkey> OP_CHECKSIG

Also, as in the original topic, a given timestamp can be doubled by some factor (like four, if it is counted in block numbers, and not seconds; but timestamps can be used as well, with a factor of 2048 or something), so that miners will have a chance to get a smaller signature confirmed, before a bigger one will arrive.

So, to have a factor of four, it can be written as:

Code:

OP_SIZE OP_DUP OP_ADD OP_DUP OP_ADD <blocknumber> OP_ADD OP_CHECK(something)VERIFY OP_DROP <pubkey> OP_CHECKSIG

Now I have to test it as well, but it looks promising.