Proof of Work transaction puzzle, based on DER signature size

[stwenhao]

I think OP_SHA256 OP_CHECKSIG is too simple for a quantum test. It will tell us, that things are broken, but won't tell us about the progress. For that reason, here is something more gradual, that I made:

Code:

+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
| Number | Address                                                        | Script                                                                           |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     60 | bc1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tlsfu3slz | 82013c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     59 | bc1qk3endeq6x0xj4pjt4zwag8wf3a629rzqr8jxd7jnmlac902wa5yshwd25y | 82013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     58 | bc1q22jvaveydlwxczfvgmsj8rguuk5x7j5xta78ztstnpckt0ajzevqggqgpd | 82013a9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     57 | bc1qsckg4lg74jyvjnzn4vnfu6e232gsq4drhl6e8qdze6j86c7htxgqu2gfum | 8201399f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     56 | bc1qqe4wgykwnk2x0rgvc0qlvplcv7l2kjjcfpsmkmtedelzx0p9zkssvcsvl4 | 8201389f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     55 | bc1qxnlp3emwhluxa3sr85s8xw49mgfzx45dsh0thn5vhpjhk36d6v7str4tjt | 8201379f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     54 | bc1qts0jh2d2nesmketmw3thedwrx939k2tqu04gy90x9hd4049g4uhs83ltjx | 8201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     53 | bc1qn9vp8l5rs7huyl237s4q9lhrzcs0mzaajt528ysq3wgnzvlkay5sdfz6am | 8201359f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     52 | bc1qcuawvnrfa2lleaf5u5qyxk7d34xn0m0kakqt7k3wac4700vxzg9q06p65d | 8201349f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     51 | bc1q2hr46qhfdum4zpvnx3rvupsk0canzuxd9gtslzx58lexly6n20xs63sszw | 8201339f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     50 | bc1qndpzf7522jtn7mfstwjqcn55rrlqxpzmqadyv3h4mgtk2m23xhtq2ae05f | 8201329f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     49 | bc1qn09x79u0vfzwlygk90zj0wtwuvvaw6nzlky3atp8lwqhshvswl0qzdn94s | 8201319f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     48 | bc1qd3fff42rjrsj97pkt0jqt9gd7qr9yc3yuphemmxus0023jgclppsyklcns | 8201309f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     47 | bc1qs4z4dg07f6r4w46g5j5lj5en65tafszdg7mfxk5n4wfuglzyzjas6yl326 | 82012f9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     46 | bc1qlskhz869r6ea7e7yvhnnx0lcgf7ylqkvkgu5ks7h48kht9t5fk8sq2anky | 82012e9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     45 | bc1qaea8zwfp8cm3hffuj29de6hzy6kuar4xz7cvykzff6rdg474d37sjr8ea5 | 82012d9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     44 | bc1q5f3sv9p2urcu90c22ewv6jg6g4jspzvfu78svxjprjhtddn5tylsglq5q2 | 82012c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     43 | bc1quct724atm82ssvd0273v3mwzu84tnevtt8magv4qywqx98t9cdaq8k8uv6 | 82012b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     42 | bc1qcj7mnlddf0fagvwsxk8gzvu9ae6a02ktjwkm5u6a6kv7z07v8d0q64ac0v | 82012a9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     41 | bc1qpqzzh9lt29z6p559d3ajh6qsg0m2s47fc9nty3s8yk8kjq9fcm5qa87v82 | 8201299f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     40 | bc1qc6zv4w8g3dqqmkrm9gan46837gnvzw6nhccrxqleuywpghpjxvpsqzmksu | 8201289f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     39 | bc1qh48gekh2u5qh825tnsql3l3qg350672p8ms5apgqjfuyy8z766fsqt8pwm | 8201279f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     38 | bc1qrhssslwre409nny7lk49z8hf56tzpywuwq0ykt4qqg9plnhk3n9sgs54jr | 8201269f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     37 | bc1qvsstwz7q5nc2l5gfy46ecrq4gly7fdutl3v6mneaesrl4q42p5aqs79sxd | 8201259f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     36 | bc1q5nnrkrwpunlrt37hdc09slw6x8tmtefgkcf3rvfj8tmlj3knydqs642y54 | 8201249f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     35 | bc1q5y3zsqws75klm272qjv7tw723k0pkq4amz7s9277vt7vx0tqe4vqr2h75a | 8201239f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     34 | bc1q8qqtmlxnhxkhlud29ulckef8zqntupn2yfukrqsuts9yksefxagqqnxfmt | 8201229f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     33 | bc1qxnv03h6x787qmplzj9l36st3tlsj0vcmhvzxa848zhqxwcd6ev5sk2a275 | 8201219f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     32 | bc1qm2w0cm93vuwzdj4s9j4r2h760pkcz5fh6mrvyuem9rdgv65v2a5sw8hw6g | 8201209f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     31 | bc1qq2f268tl7294y6mwggpxxlpkzhwgeflwu6xkyayvp49tfy8xjsaqmmrkmv | 82011f9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     30 | bc1q84chz6u2ayuvkkvjz68myuj4edjajctpl0sja9uw7hjq22przm2srnwcgc | 82011e9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     29 | bc1qmh7307pkmdxdmd663pt2sukxpl2r44ck7ctj9fp2n2t4ddm695cqth6pla | 82011d9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     28 | bc1qzd6pdkrhyw9nvmm7qf40323ktsdut7tk9d9mjhc0m7x3g29x98tsvgtdn9 | 82011c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     27 | bc1qq357t0u28ppmn6jz2j2fsmw56aydfxyygdlxs6xl5g748lnt6j4swtqfe6 | 82011b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     26 | bc1qdwrwvl6rsxdscsg0vu3v6kryvynrzxlqu8f6m5z5sgccxdxfj96qe5ws8f | 82011a9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     25 | bc1qunjltqwtzw2c2lretp638tkxwxp88h33tt4kl9efzaklttjlg3gqw6wcke | 8201199f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     24 | bc1ql6mlplvx8aqwytl9a7esxaaxqdzdehkxg2pv494ga9dajtw0uxgs6ax9t7 | 8201189f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     23 | bc1qs4kcykg0mu35axecxl33e2aem04p0he98madx22dxysuwugpryqsdgs94u | 8201179f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     22 | bc1qtlnrv6xm7wk22sphlmwtv53r2pw4q4gztq4z0u8n6w8hvdmxulrs693x83 | 8201169f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     21 | bc1qwhnww50d0h5c3exftpsqpyt7lgtzaala46rztf6n8eche2qz8vnqrnavst | 8201159f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     20 | bc1qwlamdvj56rkzgcdlycp902dw4m5cny8ajthkd3vdt98v7v99k08s27pmya | 8201149f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     19 | bc1qkxuzs6e8n5rv292xsqgvus35ul39kec2d20wwhqgwv7a69v7tpjq72clg4 | 8201139f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     18 | bc1qak0qjcx0fq593l4j05rt6jl5qg5xp0ecvd4avfn6meda6yamqhkq63uz4e | 8201129f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     17 | bc1q00ztwmcdh405ykw8qx0w6a9c8cxgu7j2ksavss0nca73x5eehdzsnkstf6 | 8201119f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac |
|     16 | bc1q9ndnp3pkzejhswjjvcr0trzs78r4sg69cfr6yvqemzyd6wnusezs9y9hjm | 82609f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
|     15 | bc1qtnwqzgrwe59md6hpury7tjeu0c5g2kq0y3cws5qgghz2398v44kqdcv5p0 | 825f9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+
|     14 | bc1qj5wmccmayunu3tylyemjfnj4fhr9lg0zqc3t7kr5r0qd0p0vxk3stk8plt | 825e9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
|     13 | bc1qqzxea5twr35sv0wcpmvnqtxwxnq0t6qpfzewry4u5zjsmzrqefvqkjx7c6 | 825d9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
|     12 | bc1q2wk3xlj3agqnsc60px0d9h8x24l2ell383agp9zvn5s89afut70qa3lskk | 825c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
|     11 | bc1qfcy96sdnu2yed6k02x84q09a3cs5lr57j6la7auc27e2u5cu6xyqw9upas | 825b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
|     10 | bc1qss67lljllhph4wnmzn7f8qpc3wh6q48hlpfpznt9sz2lntw963nssn6kzm | 825a9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac   |
+--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+

As I said in testnet4: Remember about minimally encoded CScriptNum, when you use Proof of Work scripts!

The puzzle starts from 60, because in that case, grinding a single byte is all you need, and it can be done on CPUs. Later, it gets harder and harder. First, it would probably require grinding only SHA-256 hashes, but after reaching a certain point, grinding low x-values in secp256k1 public keys will be profitable, and finding alternatives for half of the generator. The puzzle ends at 10, because 9-byte signature is the smallest valid one, where r-value and s-value has exactly one byte. It is the smallest valid signature, which would mean, that OP_CHECKSIG is fully broken, and can be used just as some 256-bit calculator, if it would be reached without public key recovery, in normal network circumstances.

Also, if you want to deposit something, then remember, that each and every coin requires a new Proof of Work, grinded from scratch. So, it is more profitable to send one output with 10k sats, than 10 outputs with 1k sats each, because even though the private key is known, and equal to one, I wouldn't be able to accumulate smaller deposits into bigger ones, without solving the puzzle by myself.

For that reason, I think depositing to the nearest unsolved address makes the most sense, and then switching to the next one, if that will be cleared. As long as every coin will be swept, the overall progress can be traced from the initial transaction.

By using "decodescript", you can get all needed details, for example for the first address from the puzzle:

Code:

decodescript 82013c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac
{
  "asm": "OP_SIZE 60 OP_LESSTHAN OP_VERIFY 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 OP_CHECKSIG",
  "desc": "raw(82013c9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac)#y8swm8mh",
  "type": "nonstandard",
  "p2sh": "3FarrwpVXsTxdscrDhZ97WVgu4jknxsPgc",
  "segwit": {
    "asm": "0 14253cba80c4fd4cd7006c31a195874c894cce1d9e01b62bea99d4178289a2ff",
    "desc": "addr(bc1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tlsfu3slz)#lnwxtrcf",
    "hex": "002014253cba80c4fd4cd7006c31a195874c894cce1d9e01b62bea99d4178289a2ff",
    "address": "bc1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tlsfu3slz",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "3Hmzt3jtw9grgoCFM6RpzWrkEVEj7iz1FM"
  }
}

Good luck!

[achow101]

From my admittedly rudimentary understanding of Shor's algorithm, computing the discrete log of small curve points shouldn't be any easier than computing the discrete log of any other curve point. It's still bounded by the fact that the order of the curve is 256 bits. What you'd actually need is a curve whose order is fewer bits, which Bitcoin doesn't support.

[stwenhao]

computing the discrete log of small curve points shouldn't be any easier than computing the discrete log of any other curve point

It is true. However:

1. We have OP_CHECKSIG, and we have secp256k1. If someone will be able to spend coins from "OP_SHA256 OP_CHECKSIG" TapScript, then that person should be able to solve my puzzle as well. Having a private key to some low x-value public key would mean, that the size of r-value will be reduced from 21 bytes into a single byte, which means sweeping everything from puzzle60 to puzzle40 on just a CPU.
2. If needed, different public keys can be used. I picked the generator as an example, and once confirmed, the puzzle will enforce it. However, by changing that public key to something different, it is possible to grind z-value of a signature, to match a different target. Which means, that it can be potentially used to join efforts, and make a signature, which would be valid in some "pay to Proof of Work" output, and also somewhere else.
3. Breaking secp256k1 alone won't make OP_CHECKSIG open to arbitrary attacks. My puzzle is a combination of secp256k1 security with SHA-256 security. Sometimes, making a smaller signature will require gradually breaking secp256k1, and sometimes SHA-256. I think solvers will have an incentive to balance it, if the value of Bitcoin will grow in the future, and if bigger amounts will be deposited. So, it is also my goal to show everyone, that fully invalidating OP_CHECKSIG may be unnecessary, because even in post-quantum world, it can be still useful, and still safe, if it will be used in a different way, than just "<pubkey> OP_CHECKSIG".
4. The puzzle is quite flexible. Anyone can use full-RBF or CPFP, and decide, how the final puzzle transaction would look like. The fee is low on purpose, also to correct some mistakes, if they will be noticed during early discussions. So, feel free to make a better Script proposals, so I can correct it, while it is still unconfirmed.

What you'd actually need is a curve whose order is fewer bits, which Bitcoin doesn't support.

It is partially supported. People can make DLEQ proofs, and use private keys, masked with zero bits. In this way, a valid signature for secp160k1 can be connected with a different valid signature for secp256k1. Then, everyone can be convinced, that the private key has at most 160 bits in both cases, and by breaking secp160k1, people can reuse the same key, and sweep coins from secp256k1 outputs.

In general, the famous "N-bit puzzle" from transaction https://mempool.space/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15 can be made provably fair, if the creator would share DLEQ proofs for all unsolved public keys. Also, range 161-256 can be recreated, because even if it is useless, when keys are hashed, then it can be still useful, when they are not.

[kTimesG]

I don't understand the challenge. Is this about finding ("mining") some specific nonce that produces a low X (r) value, resulting in a reduced length signature size?

[stwenhao]

I don't understand the challenge.

Then look at testnet4 examples, where I proved, that some addresses are spendable, for example: https://mempool.space/testnet4/address/tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d

Is this about finding ("mining") some specific nonce that produces a low X (r) value, resulting in a reduced length signature size?

It is about both secp256k1 and SHA-256 security. Each signature is a pair of two values: (r,s). When you use half of the generator, and k=(1/2), then r-value has some particularly small value. It allows you, to easily make a DER signature, which would take 60 bytes, as you can see in my example transaction: https://mempool.space/testnet4/tx/8397c2323e3fa099c15be68399346b2b3d223ef8e81e553242763e1a4c60771a

For the first puzzle, you can have something like that:

Code:

30380215                                                       //DER encoding
3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63                     //r-value
021f                                                           //DER encoding
52b332d15b1835a05cda978fabd3b0ba1675505c75e5ff71481bac66e4e52e //s-value
83                                                             //sighash

Here, the size of this signature is exactly 59 bytes, which is below 60, which means, that if the signature is valid, then coins can be moved.

At the beginning, I expect people will reuse magic value of "3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63" as their r-value, and they will focus on SHA-256 grinding s-values. However, when signatures will get smaller and smaller, then, after reaching some point in time, it may be more profitable, to find a different k-value than k=(1/2), which would lead us to some smaller r-value. Since then, sometimes secp256k1 grinding will be more profitable, and sometimes SHA-256 grinding. But in general, the main goal is to make the smallest valid signature, which would allow going below N bytes, and claiming the reward.

So, take your time, look at examples, try to validate them, and then try some grinding. The first five or so puzzles should be solvable on CPUs. Later, GPUs and ASICs will be needed, or even quantum devices, if they would make the challenge easier. In general, it can demostrate OP_CHECKSIG security, because by producing 9-byte signatures, it would signal to everyone, that OP_CHECKSIG is just some 256-bit calculator, and any 1-byte r-value, and 1-byte s-value can be easily reached. But now, we are far from that, and to get the first puzzles, you can just use some Proof of Work.

[kTimesG]

OK, I see what you did there. Basically a vanity search on the s values, so hunting down a private key for the created UTXO. I might give it a shot.

[stwenhao]

Basically a vanity search on the s values, so hunting down a private key for the created UTXO.

For now, it is the case. But later, it will be a vanity search on r-values (when grinding s-values alone will be too difficult), and then s-values again, after picking some r-value. Also, reusing two identical r-values will give everyone k-value, which means, that everyone will know, how to make a bit smaller signatures, if any solver will share it at least two times.

And also note, that I used public key, equal to the generator. Which means, that it is "s=(z+r)*2". However, if you replace it with a different key, then you will have "s=(z+template)*2". And then, other puzzles can be made, which would allow vanity searches on different s-values, picked by any puzzle maker.

Another interesting thing, is that each solver will always hash something different, because everyone will make its own transaction. And also, because TXIDs are unique, no solution can be reused, because "txid:vout" is always covered by all sighashes, even SIGHASH_NONE with SIGHASH_ANYONECANPAY. Which means, that the same Proof of Work cannot be reused, and if you deposit something twice, then each attempt to move it, will require grinding it again from scratch.

Also, it is one of those puzzles, which are more similar to collision puzzles, than to famous N-bit key puzzle, because the creator doesn't know the solution upfront. So, after sweeping the first coins, you can be easily convinced, that if my puzzle transaction will be confirmed, then I won't be able to sweep everything at once, and end the challenge, because it would require solving the puzzle by myself.

[kTimesG]

Sweeped 60 and 59 60, 59, and 58. Had a hard time convincing the TX bytes to surrender to the witness's script.

I think something is off though - the harder the puzzle, the less the reward. Was this on purpose?

[stwenhao]

the harder the puzzle, the less the reward. Was this on purpose?

The only purpose was to somehow store the information about the Script under P2WSH. Any amounts can be used. In N-bit puzzle, the amount is related to the number of non-zero bits in the private key. Here, the amount is related to the size of the signature. It can be anything, I just picked the simplest way I could come up with, not thinking too much about long-term consequences and profitability.

Also, the main goal was to show people, what is possible. Now, anyone can lock coins on Proof of Work. And it can be added to any Script you want, also with any other public key you want. Which means, that now, Alice and Bob can have for example some multisig, and they can lock their coins to any conditions, and Proof of Work. Then, the initial conditions will be enforced, and also Proof of Work between participants will decide, who should get the coins; also it will make producing double-spends harder, because each double-spend will require mining. Which means, that any second-layer protocol can use similar approach, to protect unconfirmed transactions from unwanted replacements.

Had a hard time convincing the TX bytes to surrender to the witness's script.

It is also possible as a raw Script or P2SH. But in that cases, it is non-standard. I picked P2WSH, because it was the only way I knew, to make things spendable by any user, and not only by miners. And in case of legacy Script, it is possible to make transaction, which will require hashing exactly 80 bytes. Then, grinding legacy outputs would be more aligned with grinding block headers, and for example block header nonce can be changed in a similar way, as transaction nLocktime field. Probably, grinding sighashes would also work as an additional nonce, but I didn't check, if it affects transaction standardness.

Sweeped 60 and 59 60, 59, and 58.

Congratulations! So, now it is officially started, because I am no longer the only one, who can move these coins.

Edit:

I think something is off though - the harder the puzzle, the less the reward.

Well, the same thing can be said about Proof of Work, and block rewards. Initially, anyone could get 50 BTC, by just mining it on a CPU. And now, a lot of ASICs are fighting, to get only 3.125 BTC and fees. However, in case of my puzzle, no halvings are needed: puzzle makers can pick anything they want (and also change the public key, then double-spending by the outside world will be possible only after broadcasting, unless someone will pass it directly to some mining pool). And also, the same tricks work not only on Bitcoin, but also on all altcoins, which copy-pasted its code, and where making similar Script can be done with a standard transaction.

[kTimesG]

Some takeaways so far...

- DER encodes negative values with an extra leading zero byte (even if less than 32B); so this means the PoW effort is double (for example, I found the 3 bytes puzzle after more than 33 million hashes, not after 16.7 million)

- two possible nonces (-1/2 and 1/2) = 2x times more S candidates (not just (z+r)*2)

- 2 SHA256 + 1 RIPEMD160 for every out address candidate.

I'm now writing the search in CUDA to speed up by 1.000.000 than the shitty pure Python.

[stwenhao]

two possible nonces (-1/2 and 1/2) = 2x times more S candidates (not just (z+r)*2)

Yes, but s-value has to be lower than 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1. If it is not, then it will be non-standard, and then it will require contacting Bitcoin miners directly.

And also, because of calculating things modulo n-value, not only grinding the lowest possible z-value works, but also working around 2^255 will do the trick. Some example, to explain it better:

Code:

      s=00123456789abcdef0123456789abcde789abcdef0123456789abcdef0123456
    s/2=00091a2b3c4d5e6f78091a2b3c4d5e6f3c4d5e6f78091a2b3c4d5e6f78091a2b
      r=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
(s/2)-r=00091a2b3c4d5e6f780919efc37f082fb2ac70db631370028f3fc798fea97dc8
      z=00091a2b3c4d5e6f780919efc37f082fb2ac70db631370028f3fc798fea97dc8

It is a classical example, where z-value is going to be the smallest one. However, this one will also work:

Code:

      s=00123456789abcdef0123456789abcde789abcdef0123456789abcdef0123455
    s/2=80091a2b3c4d5e6f78091a2b3c4d5e6e99a4cce2cfad6a491c368db5e0243acb
      r=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
(s/2)-r=80091a2b3c4d5e6f780919efc37f082f1003df4ebab7c0206f28f6df66c49e68
      z=80091a2b3c4d5e6f780919efc37f082f1003df4ebab7c0206f28f6df66c49e68

Which means, that z-value doesn't have to contain a lot of leading zeroes. It can start from 0x8000... as well, and after adding r, and multiplying it by two, it can overflow, and form a nice, small s-value.

2 SHA256 + 1 RIPEMD160 for every out address candidate

But why RIPEMD160? In case of P2WSH, it is never needed.

I'm now writing the search in CUDA to speed up by 1.000.000 than the shitty pure Python.

Wow, I didn't expect it will get so serious so quickly! But yes, I demonstrated a general way of adding Proof of Work to any scripts, so it can be used for many other things as well, for example to protect some transactions with zero confirmations from being easily replaced by a third party. Or: a classical example, made by Satoshi, can be now executed on-chain:

https://www.metzdowd.com/pipermail/cryptography/2008-November/014849.html

A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length.  Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble.  They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.

They don't particularly care when the attack will be, just that they all agree.  It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time.  The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.

They use a proof-of-work chain to solve the problem.  Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash.  The proof-of-work is so difficult, it's expected to take 10 minutes of them all working at once before one of them finds a solution.  Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they're working on.  If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.

After two hours, one attack time should be hashed by a chain of 12 proofs-of-work.  Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time.  They had to all have seen it because the proof-of-work is proof that they worked on it.  If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.

And now, it can be done on any on-chain coins, and also on top of many altcoins as well. Alice, Bob, and Charlie can form a network, where they will all agree to deposit funds to a shared Script, behind some hash, like P2WSH. Each of them will know the private key to the shared public key, but nobody else needs to know about it. Then, each party can use Proof of Work, and try to grind the transaction, which will sweep all coins. And then, they can share some in-the-middle progress, by broadcasting stronger, and stronger solutions, to see each other's progress, but finally, the winner will broadcast something on-chain, and will send all coins to the desired destination.

Then, as long as the computing power of all generals is stronger than all attackers, the transaction won't be double-spend on-chain, because any attacker would need to redo the work, even if the shared key will be trivially revealed to everyone, by using k=(1/2). And also, if they will send it to mining pools directly, then the rest of the network will see it, when it will already have a single confirmation. There is some potential to see it stolen by some mining pool, but if they didn't grab any funds from N-bit puzzle solvers, then they probably wouldn't do it here, because they also care about their reputation. Alternatively, someone can mine a given transaction first, and then mine a Bitcoin block, then things are similar to hash collision puzzles, where revealed solution can be captured by third parties, if seen too early.

I still think about Merged Mining, and how to improve my puzzle, to make it possible to mine Bitcoin, and my puzzle, with the same computing power. Because after all, double SHA-256 is used in both cases, and there is some potential to align it, if the proper public key will be used, and if the hashed message will start from the same initialization vector, as the latest block hash.

Edit:

But why RIPEMD160? In case of P2WSH, it is never needed.

Hmm, do you want to tell me, that each time, you tried to replace the full address of your destination output? You don't need it. You can disable RBF, and use nSequence of 0xffffffff, then nLocktime of your transaction will be ignored. And then, you can change your output address once per 2^32 hashes, just like real miners, which start tweaking merkle root, only when they have to do that.

[kTimesG]

two possible nonces (-1/2 and 1/2) = 2x times more S candidates (not just (z+r)*2)

Yes, but s-value has to be lower than 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1. If it is not, then it will be non-standard, and then it will require contacting Bitcoin miners directly.

The four sweeps so far were done using -1/2 as the nonce. AFAIK the S normalization below N/2 is done automatically by ECDSA. So it worked fine.

2 SHA256 + 1 RIPEMD160 for every out address candidate

But why RIPEMD160? In case of P2WSH, it is never needed.

Well, the output scriptPubKey was the H160 of the public key, and was the first thing I touched to actually alter the message digest, in order to mine for short S values.

But you're right, the nLockTime worked. This hint bypasses EC math almost completely.

[stwenhao]

Also, if you want to deposit something, then remember, that each and every coin requires a new Proof of Work, grinded from scratch. So, it is more profitable to send one output with 10k sats, than 10 outputs with 1k sats each, because even though the private key is known, and equal to one, I wouldn't be able to accumulate smaller deposits into bigger ones, without solving the puzzle by myself.

This problem can be solved, by making Proof of Work optional. I didn't want to do that in this specific puzzle, because then I could stop it at any moment, and sweep everything. And that would discourage people from joining the puzzle. However, if you want to attach optional Proof of Work to your scripts, you can consider using something like that:

Code:

OP_IF
  <authorKey>
OP_ELSE
  OP_SIZE <difficulty> OP_LESSTHAN OP_VERIFY <puzzleKey>
OP_ENDIF OP_CHECKSIG

As you can see, there are many possibilities. I am still trying to explore, what can be made out of it, but it seems, that there are a lot of different options. This setup above is something, which could be potentially done on top of Taproot, if OP_CAT would be there, or if Taproot would use DER encoded signatures. Because then, things could be spent by key, or by TapScript. And similar thing can be achieved in P2WSH, however, the whole Script with all conditions will be always revealed.

Edit: Using private key, equal to one, is a good starting point. However, mining would be probably a little bit easier, if a different point would be used instead. When we have "s=(z+rd)/k", and we use "d=1", then we have "s=(z+r)/k", and because k=(1/2) for now, then it is "s=(z+r)*2".

Instead of "d=1", we can pick a different d-value, where z-value would be less affected. For example, if "r*d=1", then it would be "s=(z+1)*2". In that case, the private key is "d=1/r", which is 8eb3eaf183366f8dec875d3d1a86c367b75ca84a06febfc7bd1b542981399a44, and then, the public key can be switched from 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 to 03f8f1e55f7349f7ab27c078a916ec02e055164fc7e69fc23e402fa9809acfd4f4.

Because this specific puzzle is already deployed, it can no longer be changed, but in general, you can consider using a different key in your own setups, which would allow grinding a specific pattern you want. Because in general, by using "s=(z+template)*2" equation, anything from 1 to N-1 can be used as our "template".

Now I wonder, how to calculate keys, which would allow grinding the puzzle, and something else, at the same time.

Edit: Grinding r-value is possible, but it is just not yet profitable. For example, I can imagine someone, who instead of spending it in this way:

Code:

30380215                                                       //DER encoding
3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63                     //r-value
021f                                                           //DER encoding
52b332d15b1835a05cda978fabd3b0ba1675505c75e5ff71481bac66e4e52e //s-value
83                                                             //sighash

Would do something like that instead, to move puzzle60:

Code:

3038021a                                                       //DER encoding
5bd132b3523b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63           //r-value
021a                                                           //DER encoding
1835a05cda978fabd3b0ba1675505c75e5ff71481bac66e4e52e           //s-value
83                                                             //sighash

It will be more important in the future, when SHA-256 grinding for the next unsolved outputs will be much harder, than it is now.

Edit: Another interesting scripts, which require some Proof of Work:

Code:

<signature> OP_SWAP OP_CHECKSIG //easy
  OP_SHA1   OP_SWAP OP_CHECKSIG //harder, hash is also DER encoded signature, size=20 bytes
  OP_SHA256 OP_SWAP OP_CHECKSIG //harder, hash is also DER encoded signature, size=32 bytes

Then, it can be moved, by using "<pubkey> <message>", where hash of the message will form some valid DER signature, and public key can be easily computed through public key recovery (and is needed mainly to check, if DER encoding is correct). In this case, something like that can be used for SHA-256:

Code:

301d020d                   //DER encoding
9414f5aa28ad0d96d6795f9c64 //r-value
020c                       //DER encoding
5c75e5ff71481bac66e4e52e   //s-value
83                         //sighash

Only DER encoding requires grinding, everything else can be pretty much random, as long as r-value is a valid point on a curve, and s-value starts with something from 0x01 to 0x7f. Or, for SHA-1 or RIPEMD-160:

Code:

30110207                   //DER encoding
0d96d6795f9c64             //r-value
0206                       //DER encoding
1bac66e4e52e               //s-value
83                         //sighash

It would require grinding around seven bytes for DER encoding and picked sighashes, which means checking around 2^56 hashes should allow doing tricks like that.

[amaclin1]

Edit: Another interesting scripts, which require some Proof of Work:
<signature> OP_SWAP OP_CHECKSIG //easy

https://mempool.space/tx/9cb29e46e3a2e47f041681ff54f5236cb9430086abf259573cf1fd091bb5f0a5
OP_PUSHBYTES_9 300602010202010201 OP_SWAP OP_CHECKSIG

[stwenhao]

https://mempool.space/tx/9cb29e46e3a2e47f041681ff54f5236cb9430086abf259573cf1fd091bb5f0a5
OP_PUSHBYTES_9 300602010202010201 OP_SWAP OP_CHECKSIG

I know it was already done. I added it only for comparison to explain, how it can be made harder, if hash functions would be used instead, to make a signature.

[kTimesG]

Status update (I can give more details if anyone cares):

- Puzzle #1 (8 bits): solved with Python, single thread, around 4000 sig/s (create every TX and privKey from scratch)
- Puzzle #2 (16 bits): solved with Python, same speed as #1
- Puzzle #3 (24 bits): solved with Python, around 200 Ksig/s (optimized TX buffer construction, multithread)
- Puzzle #4 (32 bits): switched to C, allowing SHA state reuse for the first 2 message blocks (the first 128 bytes are always the same) + keeping the same output scriptHash; around 32 Msig/s multithreaded
- Puzzle #5 (40 bits): solved with a laptop RTX 3050 (820 Msig/s, done in 15 minutes) - full SHA caching of the first 192 bytes of the TX bytes (part of it was 3 bytes of nLockTime), and reducing to an amortized single SHA256 round for the message digest (instead of 4). So for example for 2**32 (*2) sig checks, only 2 + 2**24 + 2**32 SHA256 rounds are needed (instead of 2**34). That is, 2 levels of SHA state cache and reuse.

Note that the speeds above are for checking both possible nonces (1/2 and -1/2), so they should be multiplied by 2. Also a handy math trick is that:

s1 = (z + r) * 2
s2 = (z + r) * -2 = -s1

so just a negation to get s2. Another weird thing I noticed is that Z (the message hash) usually has the same number of leading 1 bits as the S's number of leading 0 bits. Maybe that can be used to speed up the search, not sure yet.

I'm now grinding #6 (48 bits) on a RTX 4090. The speed is insane (much greater than a H160 vanity search). Will be solved by tonight.

[stwenhao]

Nice! Now, next puzzles are solved very quickly, sometimes it takes hours, and sometimes days. But I guess soon it will take weeks, months, or even years, to sweep next addresses (and it will no longer be profitable to fight for thousands of satoshis, because the reward will be worth much less, than the effort needed to get it).

Soon, additional incentive will be needed, to keep grinding. I thought for some time, how it could be done, and now I think I know: the solution is a transaction.

First, all sponsors prepare their own inputs, signed along with one or more puzzles, and they all use SIGHASH_NONE. Then, the difficulty and amount depends on picked puzzles, and the sum of all inputs. Because everyone signs everything (excluding puzzles) with SIGHASH_NONE, all inputs are signed, so it is impossible to steal the deposit, without solving the puzzle (the signature is invalid outside of signed set of inputs). And also, it doesn't commit to any outputs, so they can be freely chosen by the solver.

Then, partially signed transaction is shared anywhere. It can be done on forum, on some mining pool, over some P2P network, or anywhere else. Solvers can validate partially signed transactions, which would contain all needed inputs, and no outputs. Then, they will add any outputs they want, and grind solutions, signed with SIGHASH_ALL, to protect it from being stolen (and their Proof of Work will make it resistant enough to any double spends, if re-mining the solution will take more time, than getting a single confirmation).

I think I should make some experiments in test networks first, to make sure, that this model is safe, but it looks promising. And it is definitely much better, than depositing every coin on the same address, as existing puzzles, because then, it requires providing Proof of Work for each coin separately (which raises the difficulty to N*puzzleDiff).

[kTimesG]

Lucky hit after less than 3 hours. It's even a 53 bit PoW lol.

Code:

[9845 s] nLT012 = 4818944; 18211.71 M/s
[+] Key ID: 13949
S = 00000000000005a2844f65e43e868b000e27f653d19722b3da630bb59a57e34d
Z = 80000000000002d14227b2b6a674ef3fdaca7c092b7a374f200d1e4abbe775e4
Found! nLockTime = 498af3fc

Now... the next puzzle costs around 150 $ to solve, so I'll stop for now.

Here's the CUDA kernel.

Code:

#define GPU_CLOCK_FREQUENCY     2.712e9.   // RTX 4090 boost mode

__maxnreg__(128)
__global__
void kernelMineS(
    limb_t * __restrict__ pgSH,    // one script hash / thread
) {
    const U32 basePos = blockIdx.x * BLOCK_SIZE * 2 + threadIdx.x;
    const U128 * pSH = (U128 *) pgSH + basePos;

    U32 scriptHash[8];      // output script hash (32 bytes)
    U32 md[8];              // SHA256 [0:128] state (32 bytes)
    U32 total = 0;

    // load script hash from gmem to registers; coalesced
    LOAD_SH(scriptHash, pSH, 0, BLOCK_SIZE);

    // hash the first 128 bytes (same result for all threads and all scriptHashes)
    // (the message data is fixed all the way up to byte 157 - start of scriptHash)
    prepare_hash_12(md);

    U64 start_time = clock64();

    // iterate for all possible 3 last bytes of the 3rd message chunk
    // these bytes are part of the nLockTime
    for (U32 nLT012 = 0; nLT012 < 1 << 24; nLT012++) {
        U32 md2[8];            // SHA256 [0:192] state

        if (nLT012 % 2048 == 0
            && blockIdx.x == 0 && threadIdx.x == 0
        ) {
            U64 now = clock64();
            float elapsed_sec = float(now - start_time) / GPU_CLOCK_FREQUENCY;
            // counter * 256 tries * numBlocks * threadsPerBlock * 2 sigsPerCheck
            float keys_per_sec = (nLT012 * 256ULL * gridDim.x * BLOCK_SIZE * 2) / elapsed_sec;

            printf("[%.2f] nLT012 = %u, %.2f M/s\n",
                elapsed_sec, nLT012, keys_per_sec / 1e6);
        }

        // hash the 3rd chunk, by reusing the SHA state of first 2 chunks
        // this chunk contains the scriptHash of our thread, so we basically just
        // change the 3 bytes of the nLockTime and hash the new 64 bytes of data
        prepare_hash_3(md2, md, scriptHash, nLT012);

        // iterate through the 4th nLockTime byte
        for (U16 nLT3 = 0; nLT3 < 256; nLT3++) {
            // this does a single SHA256 for the last 5 bytes (4th data chunk)
            // by reusing the SHA state of the first 192 bytes hashed so far
            // Then, it hashes the final SHA to obtain the Z value
            // It then checks whether S = (Z + R) + (Z + R) mod N is a solution
            // or whether N - S is a solution
            // Another speed up is that Z must start with either 0x00000000, 0x80000000,
            // 0xffffffff, or 0x7fffffff in order for S to ever be a solution
            if (check_s(md2, nLT3)) {
                U32 nLockTime = nLT012 << 8 | nLT3;
                printf("Found! nLockTime = %08x\n", nLockTime);
                PTX_TRAP;
            }
        }
    }
}

[stwenhao]

Now... the next puzzle costs around 150 $ to solve, so I'll stop for now.

What about additional 200k sats?

Code:

decoderawtransaction 02000000000102d36528b10fcb97b2449878da63c905360ea634613000dcd3734d6405b7ddc6680100000000fdffffff01280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab0600000000fdffffff0130e00300000000000451024e730247304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb89022102a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f0000000000
{
  "txid": "db94eefbfa2b53a46995a23cd7984935ef46bfb97ebd7cc611abb111ba3eafdf",
  "hash": "6150f4cbe72257e524410e8d3fa0345a683273081de5723d938371c0d50a94c3",
  "version": 2,
  "size": 215,
  "vsize": 133,
  "weight": 530,
  "locktime": 0,
  "vin": [
    {
      "txid": "68c6ddb705644d73d3dc00306134a60e3605c963da789844b297cb0fb12865d3",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb8902",
        "02a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f"
      ],
      "sequence": 4294967293
    },
    {
      "txid": "aba3c2ae442aa20150996ee68f9aa4da83b57a4312891078be0c2e68c50b2801",
      "vout": 6,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 0.00254000,
      "n": 0,
      "scriptPubKey": {
        "asm": "1 29518",
        "desc": "addr(bc1pfeessrawgf)#d6x2lh3c",
        "hex": "51024e73",
        "address": "bc1pfeessrawgf",
        "type": "anchor"
      }
    }
  ]
}

Let's test transaction sponsorship. It is signed with SIGHASH_NONE, so it should be valid only within this specific puzzle. You can obviously change your output from bc1pfeessrawgf to anything else, because it is not signed.

I guess in that case, something else than nLockTime will be needed as a nonce, because unfortunately, it seems to be signed. However, by just using "OP_RETURN <anyData>" in some additional output, or using similar tricks, it should be possible to grind it. Also, as far as I know, nSequence should be unsigned, so it can be also used to grind it.

Also, I guess sponsors could potentially make their own transactions, if they would sign things with SIGHASH_SINGLE instead of SIGHASH_NONE, because then, they can pick a single address as a destination (but in this case they should be careful, to never sign out-of-bounds indexes, because it could be sweeped by anyone).

[kTimesG]

Let's test transaction sponsorship. It is signed with SIGHASH_NONE, so it should be valid only within this specific puzzle. You can obviously change your output from bc1pfeessrawgf to anything else, because it is not signed.

I guess in that case, something else than nLockTime will be needed as a nonce, because unfortunately, it seems to be signed. However, by just using "OP_RETURN <anyData>" in some additional output, or using similar tricks, it should be possible to grind it. Also, as far as I know, nSequence should be unsigned, so it can be also used to grind it.

Unfortunately this requires recomputing the outputs hash in the message data. So that means (for every change in OP_RETURN):

- one additional SHA256 to get the new 32 bytes for the TX outputs hash portion of the message
- one additional SHA256 to rehash the third message block each time

... and this halves the speed, so it doubles the costs. And you are correct, the nLockTime is part of the signature, so I don't see a way to keep the current performance (unless of course one would take the corresponding risks).