Proof of Work transaction puzzle, based on DER signature size

[stwenhao]

and this halves the speed, so it doubles the costs

And what about nSequence? Is it signed or not? I only copy-pasted the output from Bitcoin Core, I didn't check my z-value yet, and what or how is signed exactly. But judging by BIPs, it should be unsigned, at least when it comes to the value used for the puzzle input.

Also note, that coins from the puzzle can be spent in the old way, but then, without knowing grinded locktime upfront, it is hard to pre-sign it. Obviously, it is possible to generate 2^32 different signatures, but it sounds like overkill. Also, assuming 64 bytes per signature, it would take 2^6*2^32=2^38 bytes, so 256 GB of signature data, definitely too much to share it conveniently (and it would potentially leak the key, if not done properly, because of potential attacks on large number of signatures).

Edit: But anyway, two times harder puzzle is not a disaster. Then, it is all about increasing deposits accordingly, or waiting until BTC value, denominated in fiat, will make it profitable again.

Or: maybe it is time to think about pooling, and sharing the reward between N people. Or about pre-signing different puzzles from the sponsor's address, each giving different amount, depending on the solver's ability to grind signatures.

I have to think more about it, maybe I will come up with yet another optimization, if nLockTime cannot be used, or if nSequence is not sufficient.

[kTimesG]

This is how a signed message looks like:

Code:

SZ
        // TX version
 4 VER  01000000
        // SHA256 of all inputs UTXOs
32 HPO  b0a785c30ed3f3a97b7deefb932db2f78f8913617d39934ccb49c36f355ec15d
        // SHA256 of all inputs nSequence
32 HS   e8421900817cfe6d5377a71cb681de004f52792ef448ff3c41d15a233e230b0a
        // UTXO of the input we're signing
32 UTXO 01280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab
 4 VOUT 05000000
        // UTXO redeem script
41 RSCR 288201379f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac
        // UTXO output amount (no relation to TX total value!)
 8 AMNT 18e4030000000000
        // nSequence of the signed input
 4 NSEQ ffffffff
        // SHA256 of all the outputs
32   OH e7b3e254a82a35a3f9fe591f002e4ae01c88a7eed71d177eaecddaa15167dfe0
        // TX lockTime
 4   LT 00000000
        // signature type (HASH_ALL)
 4  SIG 01000000

As you can see, the nSequence of all the inputs are hashed together and are used right from the first message block.

The problem is when the SHA256(outputs) needs to be updated, as it also indirectly requires the 3rd message block to be SHA256'ed as well.

[stwenhao]

As you can see, the nSequence of all the inputs are hashed together and are used right from the first message block.

Yes, because you use SIGHASH_ALL. But I used SIGHASH_NONE, which should clear some fields. And in general, you can grind the solution with SIGHASH_SINGLE, combined with SIGHASH_ANYONECANPAY, and put a higher output value than input value (to prevent it from being stolen).

And in that case, I think you should be able to pick a different nSequence. But it can be confirmed on testnets or regtest first with easier puzzles, before grinding the reward.

[kTimesG]

As you can see, the nSequence of all the inputs are hashed together and are used right from the first message block.

Yes, because you use SIGHASH_ALL. But I used SIGHASH_NONE, which should clear some fields. And in general, you can grind the solution with SIGHASH_SINGLE, combined with SIGHASH_ANYONECANPAY, and put a higher output value than input value (to prevent it from being stolen).

And in that case, I think you should be able to pick a different nSequence. But it can be confirmed on testnets or regtest first with easier puzzles, before grinding the reward.

SIGHASH_NONE only clears the outputs.

Also: https://developer.bitcoin.org/devguide/transactions.html

One thing all signature hash types sign is the transaction’s locktime.

“SIGHASH_NONE” signs all of the inputs but none of the outputs,

What I get from this is:

- the sponsor signed the nLockTime
- the sponsor signed the inputs (inc. nSequence)
- the sponsor also signed the output value (since it is part of the message, separate from the outputs hash). So a solver cannot even modify the fees.

Maybe I'm wrong. Or not. You can try playing with different output amounts / input nSequences / nLockTimes when you sign your data with SIGHASH_NONE and see if they change.

[stwenhao]

And in general, you can grind the solution with SIGHASH_SINGLE, combined with SIGHASH_ANYONECANPAY, and put a higher output value than input value (to prevent it from being stolen).

Example from testnet4 in transaction 8397c2323e3fa099c15be68399346b2b3d223ef8e81e553242763e1a4c60771a, where coins from tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d are sent to tb1q22jvaveydlwxczfvgmsj8rguuk5x7j5xta78ztstnpckt0ajzevqlqk8mz, and some input containing 0.01523662 tBTC is moved into some output containing 0.03141592 tBTC. From the perspective of this single signature, coins are made out of thin air. But because the rest of the transaction can provide coins for it, then it is considered valid.

But to be sure, I think I have to test it first. Because anyway, it seems like this will be the last puzzle, which could be potentially profitable to sweep now, as others require too much resources. Which means, that now we know, more or less, how much Proof of Work is needed, to make it resistant enough for double-spending, and to discourage transaction replacement, while it is flying in mempools.

SIGHASH_NONE only clears the outputs.

Code:

// nSequence of signed input

I think it means, that your nSequence can be different than mine. But it should be tested on easier puzzles first.

[kTimesG]

And in general, you can grind the solution with SIGHASH_SINGLE, combined with SIGHASH_ANYONECANPAY, and put a higher output value than input value (to prevent it from being stolen).

Example from testnet4 in transaction

My bad. So the output amount in the signed message refers to the UTXO value of the specific input to be signed. No relation to the output total value! Nice catch, if I would have went ahead to mine #7 I would have used a totally wrong value for this field (I was adding the sponsor's value here). That would have been fun (in the "what a disaster" kind of way).

So yeah, the output amounts can be changed, but still not sure how to avoid the need of doing the extra hashes.

LE: hmmmmmm, so according to BIP 143 the hashSequences is set to an empty buffer if SIGHASH_NONE is being used. This is in contrast with the older base signature scheme.

This means that we can keep the same hashOutputs and play with the nSequence.
That's only one extra hash instead of two.

But what are the dangers of changing the nSequence?

LLE ok nevermind. Changing the nSequence immediately changes the message's first block, since we need to compute hashSequences. So its even slower. Other ideas?...

[stwenhao]

since we need to compute hashSequences

For some sighashes you need it, for others you don't. Check how SIGHASH_SINGLE with SIGHASH_ANYONECANPAY is computed, based on examples. And if you move 54k sats input into over 200k sats output, then it would be valid, only if other inputs will put coins in, so even if someone else would copy-paste your signature somewhere else, your output will still get the amount you will pick.

Things to read about the way how Segwit scripts are validated for different sighashes: https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki

But what are the dangers of changing the nSequence?

As long as you don't use OP_CHECKSEQUENCEVERIFY anywhere in your transaction, it doesn't have that many consequences, even if it is enabled, and set to something else than 0xffffffff or 0xfffffffd. In that case, it affects mainly RBF (but since full-RBF, it is no longer important). And of course it affects signatures, if it is signed (but in some sighashes, some fields can be cleared).

Nice catch, if I would have went ahead to mine #7 I would have used a totally wrong value for this field (I was adding the sponsor's value here). That would have been fun (in the "what a disaster" kind of way).

I think you should first try everything on toy examples (like puzzle60 in testnet4, or make some local tests in regtest), and later attempt real puzzles, to not burn computing power for nothing. Because, just like in real block mining, if you mine invalid transactions, then you won't get any reward.

[kTimesG]

since we need to compute hashSequences

For some sighashes you need it, for others you don't. Check how SIGHASH_SINGLE with SIGHASH_ANYONECANPAY is computed, based on examples.

How about this:

Inputs:
   #0 Sponsor, SIGHASH_NONE
   #1 Puzzle PoWhatever
Outputs (mutable to whatever we want)
   #0 OP_RETURN ""
   #1 Transfer

Sponsor signed:
   - input #0 and #1 prevouts (assuming SIGHASH_ANYONECANPAY was not used)
   - lockTime, TX version, and of course its own input

NOT signed by sponsor:
   - nSequence of other inputs
   - outputs

Puzzle signs with SIGHASH_SINGLE:
   - input #0 and #1 prevouts (assuming SIGHASH_ANYONECANPAY was not used)
   - lockTime, TX version, and of course its own input
   - output #1

NOT signed:
    - nSequence of other inputs (immutable, signed by sponsor)
    - output #0

This disables hashSequence and allows modifying nSequence of the puzzle input, correct?

If we also add ANYONE_CAN_PAY, wouldn't this allow to attach the grinded signature arbitrarily to other inputs? For example: let's assume this scenario:

- I'm grinding a solution for 64 bits, signed with "anyone can pay"
- a bad actor sees it in mempool, and, assuming the existence of a whale sponsor partial TX (which is impossible to know if it exists) for that same puzzle, can simply steal my signature and replace the TX. Now, I will get my reward just fine (since my output's signed) but the actor gets 100x bigger reward from whale input.

Another big problem I see with this is output #0 being left totally mutable. No one signs it or even cares whats in there. I can think of possible interferences on it.

[stwenhao]

This disables hashSequence and allows modifying nSequence of the puzzle input, correct?

I think it should be. But to be sure, you can make a testnet or regtest example first, when you will set it up, and execute on some easier puzzle, to get some confidence, before grinding the real example.

If we also add ANYONE_CAN_PAY, wouldn't this allow to attach the grinded signature arbitrarily to other inputs?

Yes, but if you make your signed output bigger than your input, then even if someone will do that, then that person will have to put coins in, to make the whole transaction valid. Which means, that you can broadcast your solution, and someone can decide, that "let's replace stwenhao's 200k with my own 200k". And it would of course work, but you will get your payment anyway, from me, or from anyone else, who will do the replacement.

Now, I will get my reward just fine (since my output's signed) but the actor gets 100x bigger reward from whale input.

Each sponsor uses SIGHASH_NONE, but without SIGHASH_ANYONECANPAY, so each sponsor signs all inputs. Which means, that sponsor's signature is only valid for these inputs, and nowhere else.

Which also means, that when I put 200k sats, then I can be sure, that they will be used in this specific puzzle, or won't move at all, as long as I won't make another valid signature (yes, in theory, I could first deposit 200k, and then sweep it, just before you grind your solution, and make it "pending"; but other things like multisig or timelock can be done on sponsored inputs to prevent that, if you don't trust me; and if you use sighashes open for modifications, like SIGHASH_ANYONECANPAY in your puzzle, then anyone else could put 200k sats in, without forcing you to grind it again).

Another big problem I see with this is output #0 being left totally mutable. No one signs it or even cares whats in there. I can think of possible interferences on it.

That's why sponsor's transaction can use SIGHASH_SINGLE, instead of SIGHASH_NONE, to protect it. Or: you can use only SIGHASH_ANYONECANPAY, to accept any sponsors, but to still cover all outputs with SIGHASH_ALL.

By the way: initial funding transaction was done with just SIGHASH_ANYONECANPAY, combined with SIGHASH_ALL, for all three keys. Which means, that instead of three inputs, there could be more, if anyone would want to add more coins to bump fees.

So, to sum up: I think you are correct. But I also think you should test it first on some weaker examples, and not blindly trust, that I didn't make any mistakes.

[kTimesG]

Well, for now the only option can only be to sign the puzzle input with SINGLE, since using ANYONE_CAN_PAY will not make the TX valid if other inputs get added (as all the TX inputs are already signed by the sponsor). So I would never feel comfortable to use ANYONE_CAN_PAY, it would just be an open invitation to reuse the signature in some other TX, with a much higher value unlocked.

This makes the 56-bit challenge tractable, only one SHA256 round overhead, instead of two.

Though it remains a big curiosity what the deal would be with output #0 in this case. It seems to be able to contain basically anything we want, right? For example, someone can lower the fee and use #0 as a transfer, and it would be 100% valid, but probably the nodes will reject it.

[stwenhao]

It seems to be able to contain basically anything we want, right? For example, someone can lower the fee and use #0 as a transfer, and it would be 100% valid, but probably the nodes will reject it.

Then use different sighashes. You have six options to choose from.


Edit: Maybe some testnet4 example will make it more clear. First, there is some sponsored transaction, signed with SIGHASH_NONE:

Code:

$ ./bitcoin-cli -testnet4 decoderawtransaction 020000000001026fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e00000000000fdffffffc85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff01c7a71200000000000451024e730247304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf022102bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e0000000000
{
  "txid": "b8dfbfa149dfe1e0db4a7b8e97ba7a3115f7d742e2782c5015dccf361994e08c",
  "hash": "76dbbfde6faec2c9643fcb915836a2369cc5e80dfcffaf55a30c625f02a06888",
  "version": 2,
  "size": 215,
  "vsize": 133,
  "weight": 530,
  "locktime": 0,
  "vin": [
    {
      "txid": "e0d797ca417b3c39e64677da7be5591f7c5e5d945743e9046efdbb10fd8ba76f",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf02",
        "02bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e"
      ],
      "sequence": 4294967293
    },
    {
      "txid": "95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 0.01222599,
      "n": 0,
      "scriptPubKey": {
        "asm": "1 29518",
        "desc": "addr(tb1pfees9rn5nz)#8njps4hg",
        "hex": "51024e73",
        "address": "tb1pfees9rn5nz",
        "type": "anchor"
      }
    }
  ]
}

Then, it can be validated by every solver, by computing z-value, and checking, if a given signature is correct:

Code:

     version: 02000000
hashPrevouts: b1c51c7749ba3e73fc3d654eded376bea18749e28ec6d5b2411346f768dd5393
hashSequence: 0000000000000000000000000000000000000000000000000000000000000000
    outPoint: 6fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e000000000
  scriptCode: 1976a914905ecffe7891667b664957eb430bbb0793420a7288ac
      amount: 40420f0000000000
   nSequence: fdffffff
 hashOutputs: 0000000000000000000000000000000000000000000000000000000000000000
    locktime: 00000000
    hashtype: 02000000

Out of all of that, we have this hashed message:

Code:

02000000b1c51c7749ba3e73fc3d654eded376bea18749e28ec6d5b2411346f768dd539300000000000000000000000000000000000000000000000000000000000000006fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e0000000001976a914905ecffe7891667b664957eb430bbb0793420a7288ac40420f0000000000fdffffff00000000000000000000000000000000000000000000000000000000000000000000000002000000

Which gives us this z-value:

Code:

b767da967e94bdc8bb421910af4b32576b383c36c6d6876edca60f5746f54840

And now, we can go further, and validate sponsor's signature, to make sure, that coins are really waiting for us:

Code:

Q=02bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e
s=(z+rd)/k
sR=z+rQ
r=2fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea2
s=4640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf
rQ=03E3A13C85CFD7186067F307F8049A6782CF114F217A7DBEBBF512BD7D1A4216DC
sR1=032E1F9122E175EFF183F6FBB3EC62A8FFB6E120A0B4FC1596AEE78E6D4B64B7D0
sR2=022E1F9122E175EFF183F6FBB3EC62A8FFB6E120A0B4FC1596AEE78E6D4B64B7D0
z=b767da967e94bdc8bb421910af4b32576b383c36c6d6876edca60f5746f54840
z+rQ=032E1F9122E175EFF183F6FBB3EC62A8FFB6E120A0B4FC1596AEE78E6D4B64B7D0
R=R1 (the signature is valid)

So, now we know, that for example 0.01 tBTC is waiting. Instead of grinding nLockTime, we can try to grind nSequence this time, and see, how we can sweep it. Because we know, that our reward is now equal to 0.01222599 tBTC, instead of just 0.00222599 tBTC, we can make a transaction, where we would have our puzzle input, and some destination for our reward.

Code:

$ ./bitcoin-cli -testnet4 createrawtransaction '[{"txid":"95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8","vout":1}]' '[{"tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9":0.01222599}]' 0 true
0200000001c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff01c7a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b00000000
$ ./bitcoin-cli -testnet4 decoderawtransaction 0200000001c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff01c7a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b00000000
{
  "txid": "956f51aeed5702e6607d6119feb017296155f34196b8d14139dcad09983ca169",
  "hash": "956f51aeed5702e6607d6119feb017296155f34196b8d14139dcad09983ca169",
  "version": 2,
  "size": 82,
  "vsize": 82,
  "weight": 328,
  "locktime": 0,
  "vin": [
    {
      "txid": "95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 0.01222599,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 b32f270901250853545c69e08e8f73bfe893146b",
        "desc": "addr(tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9)#uuuzwl2r",
        "hex": "0014b32f270901250853545c69e08e8f73bfe893146b",
        "address": "tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9",
        "type": "witness_v0_keyhash"
      }
    }
  ]
}

And now, we can sign it. We can use a combination of SIGHASH_ALL with SIGHASH_ANYONECANPAY. Because our input amount is less than our output, this signature alone will have a negative fee. Which means, that we are safe, and nobody will steal it (even if it will be moved to another transaction, with different sponsors, we will still get our payment). We can try to prepare some dummy data first, just to calculate the size of our transaction:

Code:

$ ./bitcoin-cli -testnet4 decoderawtransaction 020000000001026fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e00000000000fdffffffc85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff01c7a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b0247304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf022102bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e023a303702153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021e0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0ded812882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000
{
  "txid": "ab7531d98df3991229fb41130f0d1856de1ee45ead518471ad6a13d1d8e611b8",
  "hash": "4faa34445c4700144541cec5eb6f93744dbcc661738f5753e542916594815434",
  "version": 2,
  "size": 333,
  "vsize": 176,
  "weight": 702,
  "locktime": 0,
  "vin": [
    {
      "txid": "e0d797ca417b3c39e64677da7be5591f7c5e5d945743e9046efdbb10fd8ba76f",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf02",
        "02bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e"
      ],
      "sequence": 4294967293
    },
    {
      "txid": "95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "303702153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021e0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0ded81",
        "82013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac"
      ],
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 0.01222599,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 b32f270901250853545c69e08e8f73bfe893146b",
        "desc": "addr(tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9)#uuuzwl2r",
        "hex": "0014b32f270901250853545c69e08e8f73bfe893146b",
        "address": "tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9",
        "type": "witness_v0_keyhash"
      }
    }
  ]
}

Now we know, that we can pay 176 satoshis for all of that, assuming 1 sat/vB. So, let's adjust our setup:

Code:

./bitcoin-cli -testnet4 createrawtransaction '[{"txid":"95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8","vout":1}]' '[{"tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9":0.01222423}]' 0 true
0200000001c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff0117a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b00000000

And now we can prepare data, which we are going to sign:

Code:

     version: 02000000
hashPrevouts: 0000000000000000000000000000000000000000000000000000000000000000
hashSequence: 0000000000000000000000000000000000000000000000000000000000000000
    outPoint: c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad89501000000
  scriptCode: 2882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac
      amount: 8765030000000000
   nSequence: fdffffff
 hashOutputs: f350d9623a117997f15e212fe9e931223c94d1e5b56167218ae1f1012c89ae30
    locktime: 00000000
    hashtype: 81000000

Instead of tweaking locktime as previously, we can now tweak our nSequence (without affecting sponsor's nSequence, because hashSequence is cleared). After some grinding, we can now get:

Code:

sequence: 0x00065f4b

And now we can confirm it. This is our message:

Code:

0200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad895010000002882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac876503000000000000065f4bf350d9623a117997f15e212fe9e931223c94d1e5b56167218ae1f1012c89ae300000000081000000

Which can be hashed into our z-value:

Code:

00001e00b434ae7e5eb15fa41fa0b64e7805d4cd7e4bd68039662970066eaf32

And now, we can prepare and broadcast our final version:

Code:

$ curl -X POST -sSLd "020000000001026fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e00000000000fdffffffc85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad895010000000000065f4b0117a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b0247304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf022102bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e023a303702153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021e3c0168695cfcbd62bfbf30de191c034d84c326830151cce7808cff9c972a812882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000" "https://mempool.space/testnet4/api/tx"

And now, you can see it on public block explorers: https://mempool.space/testnet4/tx/e83158da4fa0cbc76d79ac3f85c4d27392e95dc2a809b069c6d4468f9085a78c#vin=1

Of course, it is good to double-check if I didn't make any mistakes in my description, but testnet4 examples should convince you, that grinding nSequence instead of nLockTime is possible, and can work in practice. Also, you can hover your mouse over some signatures, and then, highlighted parts will show you, which inputs and outputs are signed for different sighashes.

[NotATether]

If the smallest possible size is 10 bytes (a 1-byte DER header followed by a 9-byte payload if my memory serves me correctly), does this mean you are only storing R values? Because S values can be obtained by multiplying the R by the message to sign (I think [let's call it Z]) and then normalized.

[stwenhao]

If the smallest possible size is 10 bytes (a 1-byte DER header followed by a 9-byte payload if my memory serves me correctly), does this mean you are only storing R values?

No. Each signature contains both r-value and s-value. The smallest example just uses one byte for r-value, and one byte for s-value, and the rest is related to DER encoding and sighash. Example: https://bitcointalk.org/index.php?topic=5373858

Code:

30060201 //DER encoding
01       //r-value
0201     //DER encoding
01       //s-value
03       //sighash

You can compare it with the smallest currently solved puzzle: https://mempool.space/tx/d545ad484d95fdf39c536de1b2956a6a3316a6ec99272212115b6c72c62814f7#vin=0

Code:

30330215                                             //DER encoding
3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63           //r-value
021a                                                 //DER encoding
05a2844f65e43e868b000e27f653d19722b3da630bb59a57e34d //s-value
01                                                   //sighash

As you can see, the smallest result so far is below 55 bytes, so it is 54-byte DER signature. Going to 9-byte example will take a lot of time, and will be very hard, but public key recovery can prove, that it is possible, at least in theory.

Because S values can be obtained by multiplying the R by the message to sign (I think [let's call it Z]) and then normalized.

The equation is "s=(z+rd)/k". When people currently use "k=1/2", and "r=3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63", then it is just "s=(z+3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63)*2". In this puzzle, we have "d=1", but in custom scripts, it can be changed, to make it "s=(z+template)*2", to grind different targets.

[kTimesG]

OK. Finished the full tests for the new strategy, and GPUs are now UP, with a guaranteed way to extract the correct results out of the madness of multiple GPUs / multiple hashOutputs / multiple nSequence. So it's now only a matter of time before the 56-bit falls (may be hours, may be days).

I am using a mixture of OP_RETURN to spice up the outputs (since I am using a fixed destination address across ALL the GPUs and it was way too overkill to generate and keep track of so many separate outputs) and then simply going across the nSequence from 0xffffffff down. Results are no longer printed on screen since its now obviously a distributed network of nodes, so I'm recovering the OP_RET and the nSequence centrally to get the Z and S.

Using SIGHASH_ANYONECANPAY | SIGHASH_ALL to allow any sponsor while disabling the ability to overspend in some other TX.

BTW it's purring at over 7500 MK/s on each RTX 4090. So not bad.

[kTimesG]

Stopped the search because I don't think the nSequence trick actually works.

Check this out:

Code:

02000000000102d36528b10fcb97b2449878da63c905360ea634613000dcd3734d6405b7ddc6680100000000fdffffff01280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab0600000000fff3203302b0df030000000000160014fb2b3fc709c1e46ef3e6cf90064a2a0bd570d16200000000000000000a6a08af2a0f9fecdf6d560247304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb89022102a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f0236303302153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021a6099f0128f08ce57909608bcb74fccbed9f21c007a62c899459381288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000

Yes, the sig is 54 bytes and won't pass the puzzle script check, but before that happens this error is thrown when trying to broadcast this TX:

Code:

Failed to broadcast transaction, reason: non-BIP68-final

Decoded TX looks "fine".

Code:

{
  "version": 2,
  "locktime": 0,
  "ins": [
    {
      "n": 1,
      "script": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293,
      "txid": "68c6ddb705644d73d3dc00306134a60e3605c963da789844b297cb0fb12865d3",
      "witness": [
        "304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb8902",
        "02a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f"
      ]
    },
    {
      "n": 6,
      "script": {
        "asm": "",
        "hex": ""
      },
      "sequence": 857797631,
      "txid": "aba3c2ae442aa20150996ee68f9aa4da83b57a4312891078be0c2e68c50b2801",
      "witness": [
        "303302153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021a6099f0128f08ce57909608bcb74fccbed9f21c007a62c899459381",
        "8201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac"
      ]
    }
  ],
  "outs": [
    {
      "n": 0,
      "script": {
        "addresses": [
          "bc1qlv4nl3cfc8jxaulxe7gqvj32p02hp5tzhk4c72"
        ],
        "asm": "OP_0 fb2b3fc709c1e46ef3e6cf90064a2a0bd570d162",
        "hex": "0014fb2b3fc709c1e46ef3e6cf90064a2a0bd570d162"
      },
      "value": 253872
    },
    {
      "n": 1,
      "script": {
        "addresses": [],
        "asm": "OP_RETURN af2a0f9fecdf6d56",
        "hex": "6a08af2a0f9fecdf6d56"
      },
      "value": 0
    }
  ],
  "hash": "5991296ed57e2cf01db3da92194dc8814ef64eca9ac7fda5ccf2fa257c482cc8",
  "txid": "5991296ed57e2cf01db3da92194dc8814ef64eca9ac7fda5ccf2fa257c482cc8"
}

Message signed by the puzzle input

Code:

020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d2000000000000fff3203331047d8cff70aa0819eb13395e40f74da7d3c134dfa9964649821d24f8028cf50000000081000000

with Z and S

Code:

Z = 800000000000304cf8094748ee5d720ad814dc87290e12ee40dbd5a153082707
S = 0000000000006099f0128f08ce57909608bcb74fccbed9f21c007a62c8994593

BIP68 snippet:

This specification defines the meaning of sequence numbers for transactions with an nVersion greater than or equal to 2 for which the rest of this specification relies on.

So it seems that having TX version = 2 in the sponsor's view of the TX is the main issue.

[stwenhao]

Hmm, let's see: https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki

If bit (1 << 31) of the sequence number is set, then no consensus meaning is applied to the sequence number and can be included in any block under all currently possible circumstances.

Which means, that one bit should be set to specific value. In case of your nSequence, you used 0x3320f3ff. It is below 0x80000000, so this bit is unset, and it triggers some conditions, which I didn't expect.

So, if you keep it in range between 0x80000000 and 0xffffffff, then it should work (unless I don't know about yet another consensus rule).

Which means, that you are right, and modifying nSequence has some consequences. But by keeping it in specific range, it should work.

[kTimesG]

So, if you keep it in range between 0x80000000 and 0xffffffff, then it should work (unless I don't know about yet another consensus rule).

OK, I tested with another nSequence with bit 31 set (I collect all 49+ bits signatures) and indeed the error this time was about input 1 sig not being valid. I need to modify my code a bit (literally, lol).

The problem was that I was dumping nSequence bytes in big-endian, even though it went down from 0xffffffff.

Code:

02000000000102d36528b10fcb97b2449878da63c905360ea634613000dcd3734d6405b7ddc6680100000000fdffffff01280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab0600000000fff1e1b102b0df030000000000160014fb2b3fc709c1e46ef3e6cf90064a2a0bd570d1620000000000000000066a04149c11c50247304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb89022102a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f0236303302153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021a28c4dcc7b4fec5c5b163990e617fa9ee9ca68f0a9942bf8cc34d81288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000

Code:

nSeq = b1e1f1ff
msg = 020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d2000000000000fff1e1b1ada4f81d8b5c88e0ce674fc29de9c82029ff95451b5179d9857eff36f312d4400000000081000000
Z = 80000000000014626e63da43ea148271a03db19f17a5f4487a60e5114e81e5e4
S = 00000000000028c4dcc7b4fec5c5b163990e617fa9ee9ca68f0a9942bf8cc34d

[stwenhao]

So it seems that having TX version = 2 in the sponsor's view of the TX is the main issue.

Well, it can be fixed. Two changes: one is transaction version, another is putting the puzzle as the first input, so SIGHASH_SINGLE can be applied, if any solver wants a single output.

Code:

decoderawtransaction 0100000000010201280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab0600000000fdffffffd36528b10fcb97b2449878da63c905360ea634613000dcd3734d6405b7ddc6680100000000fdffffff0130e00300000000000451024e73000247304402200f574c15f1a4468f942704a8ae580a32ac2783f5d6e7e6029ce46b8ebfd0f3590220262089defda8dc935ee32dac32d5273d167ec2b839e6bf1020c220f27eb86b12022102a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f00000000
{
  "txid": "9a1953e1d698b9510e686951fada7d3ddefbf0a4095b2c15367ba7d0ad10c527",
  "hash": "02e60e297b7fc6886c00d431ee3e2c66a53a40f39846a3933183890f065a56a6",
  "version": 1,
  "size": 215,
  "vsize": 133,
  "weight": 530,
  "locktime": 0,
  "vin": [
    {
      "txid": "aba3c2ae442aa20150996ee68f9aa4da83b57a4312891078be0c2e68c50b2801",
      "vout": 6,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293
    },
    {
      "txid": "68c6ddb705644d73d3dc00306134a60e3605c963da789844b297cb0fb12865d3",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "304402200f574c15f1a4468f942704a8ae580a32ac2783f5d6e7e6029ce46b8ebfd0f3590220262089defda8dc935ee32dac32d5273d167ec2b839e6bf1020c220f27eb86b1202",
        "02a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f"
      ],
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 0.00254000,
      "n": 0,
      "scriptPubKey": {
        "asm": "1 29518",
        "desc": "addr(bc1pfeessrawgf)#d6x2lh3c",
        "hex": "51024e73",
        "address": "bc1pfeessrawgf",
        "type": "anchor"
      }
    }
  ]
}

Please check the signature before grinding. But I think it should be correct. Also, other changes can be made, if needed.

[kTimesG]

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

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

[stwenhao]

57-bit DONE after 8 days!

Nice! I guess it will be the last one I could afford sponsoring now, but the mechanism is tested in practice, so now the community knows, how to keep it running, and how to deposit coins, without making the whole puzzle harder. And maybe in the future it will be more profitable, if the price of BTC in fiat will go up, or if someone will find some better optimizations, or reveal some private key to public keys with small x-values, which would shrink the signature.

Anyway, it is a long-term puzzle, sweeping everything would prove, that ECDSA is unsafe, so many coins will probably stay locked for quite long time. But at least now we can roughly estimate, how much difficulty can be put into sidechains, to reach a given time per sidechain block (which can be expressed as a valid on-chain transaction).

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.

Yes, sponsored transaction was just sitting on some public key, so I could in theory sweep it at any time. But, fortunately, if you have any solution with SIGHASH_ANYONECANPAY, then any new inputs can be used to process it. In practice, I guess more protections could be set, for example multisig or locktime on sponsored inputs, to make it harder to deposit something, and then sweep it, before solvers will submit the proper transaction.

I wondered, how much time it would take, and how many more coins I would need to put in, to encourage you to keep grinding, but I am happy to see, that it took days, and not months, to get there.

Total costs: 110 $

Assuming you got everything, you reached something around 600k sats, so claiming everything from puzzle60 to puzzle54 was probably worth it. But, more importantly, now we know, that Proof of Work can be really executed inside transactions, and I didn't mess it up, so more protocols can be safely created on top of such scripts. And also, it can be roughly estimated, how to set initial difficulty, to keep it profitable, but to also not make it too easy to grind.

However, it is just a Proof of Concept. Now, it would probably take some time, to create a real sidechain on top of it, and deploy something more serious. And also, it would be great, if it would be possible to mine real Bitcoin block, while mining some kind of puzzle like that, with the same power (but I don't know yet, how to implement Merged Mining inside Script).