|
Title: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 20, 2025, 04:35:30 PM I think OP_SHA256 OP_CHECKSIG (https://bitcointalk.org/index.php?topic=5479881.0) 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: +--------+----------------------------------------------------------------+----------------------------------------------------------------------------------+ 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 (https://bitcointalk.org/index.php?topic=5373858), 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: achow101 on July 21, 2025, 05:05:12 AM 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.
Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 21, 2025, 06:06:14 AM Quote 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. Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 21, 2025, 12:41:39 PM 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?
Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 21, 2025, 01:37:43 PM Quote 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/tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9dQuote 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/8397c2323e3fa099c15be68399346b2b3d223ef8e81e553242763e1a4c60771aFor the first puzzle, you can have something like that: Code: 30380215 //DER encoding 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 21, 2025, 04:39:05 PM 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.
Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 21, 2025, 05:09:14 PM Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 21, 2025, 09:07:56 PM Sweeped
I think something is off though - the harder the puzzle, the less the reward. Was this on purpose? Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 22, 2025, 03:35:11 AM Quote 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. Quote 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.Quote Sweeped Congratulations! So, now it is officially started, because I am no longer the only one, who can move these coins.Edit: Quote 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.Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 22, 2025, 11:08:36 AM 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 22, 2025, 11:52:21 AM Quote 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 Code: s=00123456789abcdef0123456789abcde789abcdef0123456789abcdef0123455 Quote 2 SHA256 + 1 RIPEMD160 for every out address candidate But why RIPEMD160? In case of P2WSH, it is never needed.Quote 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 Quote 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. 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.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. 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: Quote 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.Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 22, 2025, 02:16:21 PM Quote 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. Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 22, 2025, 05:00:24 PM Quote 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 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 Code: 3038021a //DER encoding Edit: Another interesting scripts, which require some Proof of Work: Code: <signature> OP_SWAP OP_CHECKSIG //easy Code: 301d020d //DER encoding Code: 30110207 //DER encoding Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: amaclin1 on July 23, 2025, 06:26:05 PM 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 24, 2025, 02:36:13 AM Quote https://mempool.space/tx/9cb29e46e3a2e47f041681ff54f5236cb9430086abf259573cf1fd091bb5f0a5 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.OP_PUSHBYTES_9 300602010202010201 OP_SWAP OP_CHECKSIG Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 24, 2025, 02:27:37 PM 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 24, 2025, 04:16:51 PM 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). Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 24, 2025, 06:25:13 PM Lucky hit after less than 3 hours. It's even a 53 bit PoW lol.
Code: [9845 s] nLT012 = 4818944; 18211.71 M/s 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 03:25:24 AM Quote Now... the next puzzle costs around 150 $ to solve, so I'll stop for now. What about additional 200k sats?Code: decoderawtransaction 02000000000102d36528b10fcb97b2449878da63c905360ea634613000dcd3734d6405b7ddc6680100000000fdffffff01280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab0600000000fdffffff0130e00300000000000451024e730247304402202c368f7b1bb7cd891f1a082773f6cca1219fb42ba6797c407ef34142debc685902204b8391fca6320f7eea32b77215f962fa019364c4f73272a73be0002f3a37eb89022102a2231b027ae19ac2f05fc8e2a63ed19494630c478732f0f5702d3495474d853f0000000000 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). Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 01:22:55 PM 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). Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 01:43:34 PM Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 02:25:41 PM This is how a signed message looks like:
Code: SZ 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 03:45:36 PM Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 04:01:44 PM Quote 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 Quote One thing all signature hash types sign is the transaction’s locktime. Quote “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 Maybe I'm wrong. Or not. You can try playing with different Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 04:10:41 PM Quote 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 (https://mempool.space/testnet4/tx/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. Quote SIGHASH_NONE only clears the outputs. Quote Code: // nSequence of signed input Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 04:48:48 PM Quote 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. 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?... Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 05:50:03 PM Quote 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 Quote 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).Quote 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.Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 06:28:10 PM Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 25, 2025, 07:20:22 PM Quote 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.Quote 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.Quote 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). Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 25, 2025, 10:42:40 PM 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 26, 2025, 03:22:55 AM Quote 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.https://static.learnmeabitcoin.com/diagrams/png/keys-signature-hash-types.png 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 Code: version: 02000000 Code: 02000000b1c51c7749ba3e73fc3d654eded376bea18749e28ec6d5b2411346f768dd539300000000000000000000000000000000000000000000000000000000000000006fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e0000000001976a914905ecffe7891667b664957eb430bbb0793420a7288ac40420f0000000000fdffffff00000000000000000000000000000000000000000000000000000000000000000000000002000000 Code: b767da967e94bdc8bb421910af4b32576b383c36c6d6876edca60f5746f54840 Code: Q=02bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e Code: $ ./bitcoin-cli -testnet4 createrawtransaction '[{"txid":"95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8","vout":1}]' '[{"tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9":0.01222599}]' 0 trueCode: $ ./bitcoin-cli -testnet4 decoderawtransaction 020000000001026fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e00000000000fdffffffc85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad8950100000000fdffffff01c7a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b0247304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf022102bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e023a303702153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021e0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0dedbadc0ded812882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000 Code: ./bitcoin-cli -testnet4 createrawtransaction '[{"txid":"95d89a3e03361e9b1f8412928656dac03c92979469dbfc0bcabdeaedcdc45fc8","vout":1}]' '[{"tb1qkvhjwzgpy5y9x4zud8sgarmnhl5fx9rtkumau9":0.01222423}]' 0 trueCode: version: 02000000 Code: sequence: 0x00065f4b Code: 0200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000c85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad895010000002882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac876503000000000000065f4bf350d9623a117997f15e212fe9e931223c94d1e5b56167218ae1f1012c89ae300000000081000000 Code: 00001e00b434ae7e5eb15fa41fa0b64e7805d4cd7e4bd68039662970066eaf32 Code: $ curl -X POST -sSLd "020000000001026fa78bfd10bbfd6e04e94357945d5e7c1f59e57bda7746e6393c7b41ca97d7e00000000000fdffffffc85fc4cdedeabdca0bfcdb699497923cc0da56869212841f9b1e36033e9ad895010000000000065f4b0117a7120000000000160014b32f270901250853545c69e08e8f73bfe893146b0247304402202fab8564b6633015c745da23e33356699169e24a2aa767a09b09495f0441fea202204640b1badfcea835b4dd5a499aabf88f7a5a687aaf04a8deb07889952fea30bf022102bf87b7b578af7d22160ae2c96ba0ab7f0152c27ac9a60fb50f8116ac691c504e023a303702153b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63021e3c0168695cfcbd62bfbf30de191c034d84c326830151cce7808cff9c972a812882013b9f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac00000000" "https://mempool.space/testnet4/api/tx" 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: NotATether on July 27, 2025, 01:05:45 PM 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.
Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 27, 2025, 02:10:53 PM Quote 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=5373858Code: 30060201 //DER encoding Code: 30330215 //DER encoding Quote 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.Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 27, 2025, 06:06:21 PM 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 28, 2025, 03:30:22 PM 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: {Message signed by the puzzle input Code: 020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d2000000000000fff3203331047d8cff70aa0819eb13395e40f74da7d3c134dfa9964649821d24f8028cf50000000081000000 with Z and S Code: Z = 800000000000304cf8094748ee5d720ad814dc87290e12ee40dbd5a153082707 BIP68 snippet: Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 28, 2025, 04:13:12 PM Hmm, let's see: https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki
Quote 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on July 28, 2025, 04:24:42 PM 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on July 28, 2025, 04:27:12 PM Quote 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on August 04, 2025, 02:21:51 PM yo\(~
57-bit DONE after 8 days! The found S actually had 58 leading bits of 0 (57 were enough). Code: MSG = 020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d20000000000003d74fbff045b0f32c7adb53ce93b424e7ba280a4328ef880b60058c771b3ef599f9e95840000000081000000 https://talkimg.com/images/2025/08/04/UH9t4a.png Server logs... Code: New key: 0x524f8523a3e703801c And total running stats.... Code: Total jobs: 30314 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 :) Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on August 04, 2025, 03:41:39 PM Quote 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). Quote 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. Quote 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). Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on August 04, 2025, 04:11:30 PM Assuming you got everything Code: Message: Solved by kTimesG Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: AbadomRSZ on August 05, 2025, 04:24:25 PM yo\(~ 57-bit DONE after 8 days! The found S actually had 58 leading bits of 0 (57 were enough). Code: MSG = 020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001280bc5682e0cbe78108912437ab583daa49a8fe66e995001a22a44aec2a3ab06000000288201369f69210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798acf0d20000000000003d74fbff045b0f32c7adb53ce93b424e7ba280a4328ef880b60058c771b3ef599f9e95840000000081000000 https://talkimg.com/images/2025/08/04/UH9t4a.png Server logs... Code: New key: 0x524f8523a3e703801c And total running stats.... Code: Total jobs: 30314 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? Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: kTimesG on August 06, 2025, 01:03:49 PM 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. Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: stwenhao on August 15, 2025, 10:31:06 AM Some untested ideas for other Proof of Work scripts:
Code: decodescript 82013d0146a569210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ac Code: +--------+----------------------------------------------------------------+--------------------------------------------------------------------------------------+ Code: +------------+----------------------------------------------------------------+--------+ Code: decodescript a67cac Edit: It seems that picking a given difficulty can be delegated. For example: Code: Input: <puzzleSignature> <sponsorSignature> Code: Input: <sigPuzzle> <sig1> <sig2> <sig3> <sig4> <sig5> <sig6> 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 Title: Re: Proof of Work transaction puzzle, based on DER signature size Post by: ertil on August 23, 2025, 08:03:04 AM I read that topic about Proof-of-work based signet faucet (https://delvingbitcoin.org/t/proof-of-work-based-signet-faucet/937) 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 Code: OP_SIZE <timestamp> OP_ADD OP_CHECKSEQUENCEVERIFY OP_DROP <pubkey> OP_CHECKSIG 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 |
