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
   s/2=00091a2b3c4d5e6f78091a2b3c4d5e6f3c4d5e6f78091a2b3c4d5e6f78091a2b
   r=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
(s/2)-r=00091a2b3c4d5e6f780919efc37f082fb2ac70db631370028f3fc798fea97dc8
   z=00091a2b3c4d5e6f780919efc37f082fb2ac70db631370028f3fc798fea97dc8

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

Code:

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

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

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.

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

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

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

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

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

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

Edit:

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.