[bitcoindev] Bitcoin PoW locked outputs with arbitrary difficulty

[Adam Borcany <adamborcany@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 33772 bytes --]

Hello everyone,

The discussion about Signing a Bitcoin Transaction with Lamport Signatures
<https://groups.google.com/g/bitcoindev/c/mR53go5gHIk> here on the mailing
list sparked an idea about using the mathematical properties of short
DER-encoded ECDSA signatures for proof-of-work locked outputs allowing for
arbitrary difficulty.

Here I am posting a write-up defining how exactly to do this along with the
proof of concept Node.JS code allowing you to create PoW-locked output
scripts & mining them: https://github.com/adambor/btc-pow-locked-outputs/.
The full write-up below.

# Bitcoin PoW-locked outputs with arbitrary difficulty

## Abstract

The best current way to do PoW-locked output scripts in bitcoin is to use
signature grinding, this however doesn't allow smooth difficulty
adjustments, as it works with byte size of the DER encoded signature, so
the adjustment steps are either 256 times the prior difficulty to the the
upside or prior difficulty divided by 256. Here we first present current
way to do bitcoin script PoW locking with ECDSA signatures along with its
limitations and then we present a new way of locking bitcoin outputs with
fully arbitrary difficulty (the lowest difficulty being 2^18) by just using
12 signatures, a well-known short nonce and carefully choosen set of 12
private keys. Moreover the PoW is based on grinding the transaction hash
(SHA-256d) and using simple comparisions in the 256-bit integer space, it
involves no operations in the finite field or elliptic curve operations.

## Simple signature grinding

Signature grinding is based on the fact that ECDSA signatures in bitcoin
are DER encoded, so they have variable size based on the amount of leading
zero bytes in the signature's **r** & **s** values. The size of the DER
encoded signature is 2 (DER prefix) + 2 (r value prefix) + size(**r**) + 2
(s value prefix) + size(**s**) + 1 (sighash flag) = 7 + size(**r**) +
size(**s**), where size() is the encoded byte size of the variable, it's
also important to note that encoded integers must always have their most
signification bit set to 0, as that represents the sign of the integer (all
integers in DER are signed).

The **r** value is the x coordinate of a signing nonce point
(**r**=x_only(**k**\*G)), as discrete log is presumed to be hard in EC, one
needs to grind through multiple nonces **k** to get the **r** value that
has a pre-defined amount of leading zero bytes.

The **s** value can be computed as **s**=**k**^-1\*(z+**dr**), where z is
the transaction hash, and **d** a private key, the miner can easily grind
the transaction hash z here and check if the resulting **s** value has the
required amount of leading zero bytes.

### Application

As we can only restrict the full length of the signature (including length
changes from both **r** & **s** values combined) with OP_SIZE opcode, the
best course of action for a miner is to use a short enough nonce, such that
grinding **s** value will then be easier for him as he will require fewer
leading zero bytes. This nonce can also be re-used because the private key
locking the output is not a secret.

#### Base case

In the base case this would mean miners constantly running an algorithm
trying to find the **k** value producing the **r** with most amount of
leading zeto bytes and then using that **k** to grind the **s** value,
since private key **d** is publicly known, everyone would get to know the
**k** used to produce the short **r** (one can easily solve
**s**=**k**^-1\*(z-**dr**) for **k** by knowing s, r, d & z) and other
miners can now re-use it.

#### Using well known short nonce point

For the secp256k1 curve we already know of a specific **k**=1/2 value
producing
**r**=0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
with 11 leading zero bytes (88-bits). Producing a shorter **r** is highly
unlikely as it would require grinding through 2^96 **k** values to have 50%
chance of finding it. Therefore rational miners would just use this nonce
and then grind just the transaction hash. Then the size of the DER encoded
signature is 7 + 21 (well-known short **r** value) + **p**. We can
therefore tune the difficulty of the PoW by adjusting **p**, then the work
required is 2\*256^**p** (the 2 multiple is because of the most signficant
bit having to be 0).

### Drawbacks

As can be seen from the equation above, the work can only scale in the
powers of 256 (because **p** is an integer), so the difficulty can be
either multiplied by 256 or divided by 256. One can use multiple signatures
to allow for smoother difficulty adjustement e.g. 256 signatures can be
used to allow for increments/decrements by 0.4%, however this is not
practical due to P2WSH redeem script limitations such as 10kB of size & up
to 201 of non-push opcodes.

## Mathematical structure of short signatures

For the signature value **s** to be short (have certain amount of leading
zero bytes), we can say that **s** < 2^(8\*(32-**b**)-1), where **b** is
the amount of leading zero bytes that we want to achieve. Let's look more
closely into a specific case where we want to achieve 1 leading zero byte &
use the well known short nonce **k** - the DER encoded signature size in
this case is 59 bytes or less.

**s**=**k**^-1\*(**z**+**dr**) mod **n**; **s** < 2^247

Since comparison operators are not defined over a finite field (and
calculation of **s** is done in the finite field modulo field order **n**),
we can create a set of all the integers 0..(2^247-1) and then see if the s
value is contained in this set, therefore we can write

**s** ∈ {i ∈ Z | i < 2^247}\
**k**^-1\*(**z**+**dr**) ∈ {i ∈ Z | i < 2^247}

**k** is 1/2 so the inverse is 2, and we can also let **x**=-**dr** mod
**n**, since **d** is a constant private key and **r** is also a constant
since we use a constant **k** (the minus sign will become apparent later).

2\*(**z**-**x**) ∈ {i ∈ Z | i < 2^247}\
(**z**-**x**) ∈ {i/2 | i < 2^247}

Which we can write as (keep in mind i/2 is division in the finite field)

(**z**-**x**) ∈ {i ∈ Z | i < 2^246} ∪ {i ∈ Z | **n** div 2 + 1 ≤ i < **n**
div 2 + 1 + 2^246}, where div is integer division\
**z** ∈ {i + **x** mod **n**| i < 2^246} ∪ {i + **x** mod **n** | **n** div
2 + 1 ≤ i < **n** div 2 + 1 + 2^246}

**I(x)** = {i + **x** mod **n**| i < 2^246} ∪ {i + **x** mod **n** | **n**
div 2 + 1 ≤ i < **n** div 2 + 1 + 2^246}\
**z** ∈ **I(x)**

This complicated-looking interval can be easily represented on the finite
field circle

![FF circle single key](
https://github.com/adambor/btc-pow-locked-outputs/blob/main/single-key-diagram.png
)

What this shows is that the signature's s-value having at least 1 leading
zero byte depends on the transaction hash **z** being in some interval
**I(x)**, which is a function of the constant **x**=-**dr** and therefore
depends only on the choosen private key **d** (**r** is fixed, since
**k**=1/2). Moreover the interval always has the size of 2^247 field
elements - hence when requiring just 1 leading zero byte the chance that
any **z** will be in the interval is 2^247/**n** (n ~ 2^256) ~ 0.2%.

### Abitrary sized intervals

By using 2 private keys, and requiring that the miner produces short
signatures for both of them over a single transaction hash we can make sure
that the transaction hash is included in both of the intervals, or in other
words the transaction hash is in the intersection of the 2 intervals.

Let **d1**, **d2** be the private keys, then **x1**=-**d1**\***r** and
**x2**=-**d2**\***r**.\
**z** ∈ **I(x1)**\
**z** ∈ **I(x2)**\
**C(x1, x2)** = **I(x1)** ∩ **I(x2)**\
**z** ∈ **C(x1, x2)**

![FF circle two key](
https://github.com/adambor/btc-pow-locked-outputs/blob/main/two-key-diagram.png
)

The interval **C(x1,x2)** (dotted area on the circle) can therefore be of
aribtrary size, the size of **C** (how many element it contains) can be
calculated as 2^247-2\*∆x, where ∆x = abs(x1-x2). The chance that any **z**
will be in the interval is P(∆x) = (2^247-2\*∆x)/**n**, or in other words,
the work required is W(∆x) = **n**/(2^247-2\*∆x). This way we can fine-tune
the chance that any transaction hash **z** will be in the interval (produce
short s-values for both private keys) and therefore adjust the amount of
work required to satisfy the output script. We still need to make sure that
the transaction hash **z** is the same for both signatures, since miner can
use different sighashes, and in that case transaction hash for the 2
signatures is not the same.

### Non-overlapping intervals

If we were to use ∆x>2^246, the size of the interval turns negative i.e.
intersection of the interval becomes an empty set **C**=∅. We can therefore
be sure that it is impossible to produce short s-values for both private
keys over the same transaction hash, so if this happens we can be sure that
2 signatures are produced over different transaction hashes (i.e. different
sighash flag in bitcoin). This means that if we use 2 private keys with
their corresponding **x** values (recall **x**=-**dr** mod **n**) further
than 2^246 apart from each other (such that their intervals **I(x)** don't
overlap) we can force the miner to use 2 different sighashes. By extension
if we use 6 private keys that produce non-overlapping intervals we can
force the miner to use all 6 possible sighashes possible on bitcoin today.

## Arbitrary difficulty signature grinding

We will use a mix of overlapping & non-overlapping intervals to force the
miner to produce signatures under all the sighashes, making sure that the
signatures supplied to the overlapping interval pairs use the same
transaction hash (have the same sighash flag).

Let ∆x be a pre-selected offset between private key **x** values defining
the difficulty of the PoW output, we will create a set of 6 pairs of
private keys (here represented by their corresponding **x** value, one can
simply calculate private key **d**=-**x**/**r** mod **n**), where private
keys in pair have an overlap defined by ∆x and different pairs have no
overlap.

(x1a, x1b) = (1, 1 + ∆x)\
(x2a, x2b) = (2^248 + 1, 2^248 + 1 + ∆x)\
(x3a, x3b) = (2\*2^248 + 1, 2\*2^248 + 1 + ∆x)\
(x4a, x4b) = (3\*2^248 + 1, 3\*2^248 + 1 + ∆x)\
(x5a, x5b) = (4\*2^248 + 1, 4\*2^248 + 1 + ∆x)\
(x6a, x6b) = (5\*2^248 + 1, 5\*2^248 + 1 + ∆x)

This forces the miner to use a different sighash flag for every one of the
6 intervals defined by overlapping interval private key pairs, ensuring
that our need for both signatures to use the same transaction hash for
overlapping intervals holds.

### Estimating difficulty

A naive approach would be to say that the difficulty (work required) in
this construction is (W(∆x)^6)/6! - as we need to hit 6 different
transaction hashes **z** within a pre-specified intervals. It is important
to note however that some sighashes can be independent of each other. Here
is a table of bitcoin sighashes and their dependencies in a 2-input &
2-output bitcoin transaction:

| Sighash flag                   |                   |         |         |
         |          |
|--------------------------------|-------------------|---------|---------|----------|----------|
| SIGHASH_NONE \| ANYONECANPAY   | locktime, version | input 0 |         |
         |          |
| SIGHASH_NONE                   | locktime, version | input 0 | input 1 |
         |          |
| SIGHASH_SINGLE \| ANYONECANPAY | locktime, version | input 0 |         |
output 0 |          |
| SIGHASH_SINGLE                 | locktime, version | input 0 | input 1 |
output 0 |          |
| SIGHASH_ALL \| ANYONECANPAY    | locktime, version | input 0 |         |
output 0 | output 1 |
| SIGHASH_ALL                    | locktime, version | input 0 | input 1 |
output 0 | output 1 |

Therefore the optimal way to produce all the required hashes/signatures is
as follows:

1. SIGHASH_NONE \| ANYONECANPAY - grind the transaction locktime & input 0
nSequence number to get a valid transaction hash in any of the intervals,
work required is W(∆x)/6
2. SIGHASH_NONE - grind the input 1, since only UTXO transaction hash &
vout is used in the transaction hash we need to create an intermediate
transaction, whose UTXO we will use as input 1 and then grind the
transaction id of this intermediate transacton, which will affect the
transaction hash of this transaction, work required is W(∆x)/5, however as
we need to do 2x more hashing (since we also need to hash the intermediate
transaction every time) the real work is 2*W(∆x)/5
3. SIGHASH_SINGLE \| ANYONECANPAY and SIGHASH_SINGLE - these need to be
done together, since only difference between them is the input 1, which was
already set in step 2, we can grind the output 0 locking script or value,
the work required is W(∆x)^2/4\*3
4. SIGHASH_ALL \| ANYONECANPAY and SIGHASH_ALL - these also need to be done
together, since only difference between them is again just the input 1,
which was already set in step 2, we can grind the output 1 locking script
or value, the work required is W(∆x)^2/2\*1

We can therefore express the total work that needs to be done by a miner as
**Wt(∆x)** = **W(∆x)**/6 + 2\***W(∆x)**/5+ **W(∆x)**^2/4\*3 +
**W(∆x)**^2/2. Based on this equation we can derive an equation for
calculating **∆x** from the required work **Wt**.

**Wt(∆x)** = **W(∆x)**/6 + 2\***W(∆x)**/5 + **W(∆x)**^2/4\*3 +
**W(∆x)**^2/2\
**Wt(∆x)** = 17/30\***W(∆x)** + 7/12\***W(∆x)**^2\
0 = 7/12\***W(∆x)**^2 + 17/30\***W(∆x)** - **Wt(∆x)**

**W(∆x)** = (-17/30 + sqrt(289/900 + 7/3\***Wt(∆x)**))/(7/6)\
**W(∆x)** = 1/105*(3\*sqrt(289+2100\***Wt(∆x)**) - 51)\
**n**/(2^248-2**∆x**) = 1/105*(3\*sqrt(289+2100\***Wt(∆x)**) - 51)\
2^247-2**∆x** = 105**n**/(3\*sqrt(289+2100\***Wt(∆x)**) - 51)

**∆x** = 105**n**/(102 - 6\*sqrt(289+2100\***Wt(∆x)**)) + 2^246

### Claim transaction structure

The claim transaction needs to be carefully crafted as to not allow other
miners to gain advantage from it.

If the claim transaction is already published in the mempool, it makes it a
bit easier to mine for others as they can re-use the short signatures for
SIGHASH_NONE \| ANYONECANPAY, this is not signficant though, since grinding
the SIGHASH_NONE \| ANYONECANPAY is the easiest (total work contribution is
just **W(∆x)**/6, compared to e.g. **W(∆x)**^2/2 for both SIGHASH_ALL &
ANYONECANPAY) - this is something we cannot eliminate.

Other miners could also re-use SIGHASH_SINGLE \| ANYONECANPAY, but this
would mean they cannot change the output 0 of the transaction, it is
therefore required to put the most significant output (e.g. the payout
output) as the first output of the transaction. Same applies for
SIGHASH_ALL \| ANYONECANPAY, however this is already covered by just using
the output 0 of the transaction as the most significant output.

To prevent other miners from re-using non-ANYONECANPAY signatures, the
input 1 of the transaction should be a P2WPKH utxo, signed with
SIGHASH_ALL, changing the transaction in any way would therefore invalidate
the signature of this input.

| Inputs                                        | Outputs
              |
|-----------------------------------------------|-----------------------------------------|
| input0: PoW-locked UTXO                       | output0: Most significant
(e.g. payout) |
| input1: P2WPKH UTXO (signed with SIGHASH_ALL) | output1: Insignificant
(e.g. OP_RETURN) |

### Example

There is a Node.JS application in /example directory of the repo, allowing
you to create & mine PoW-locked output with arbitrary difficulty (work).
Here is a detailed example of how the code actually works.

#### Setup

A simple example for constructing an output with a difficulty of 2^18 (a
miner on average has to go through 262144 hashes to find a solution) - all
numbers are in hexadecimal.

Field order **n** =
0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\
Required work **Wt** = 0x40000\
**∆x** = 0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc163

Interval pairs (**x** values)

(x1a, x1b) =
(0x0000000000000000000000000000000000000000000000000000000000000001,
0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)\
(x2a, x2b) =
(0x0100000000000000000000000000000000000000000000000000000000000001,
0x010f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)\
(x3a, x3b) =
(0x0200000000000000000000000000000000000000000000000000000000000001,
0x020f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)\
(x4a, x4b) =
(0x0300000000000000000000000000000000000000000000000000000000000001,
0x030f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)\
(x5a, x5b) =
(0x0400000000000000000000000000000000000000000000000000000000000001,
0x040f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)\
(x6a, x6b) =
(0x0500000000000000000000000000000000000000000000000000000000000001,
0x050f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164)

Derive private key pairs from the **x** value pairs, **d**=-**x**/**r** mod
**n**

(d1a, d1b) =
(0x714c150e7cc990721378a2c2e5793c970352349ca849e07402b70a634efca6fd,
0xa0cc0ae9058236ed8b9791845c0533cf2c8371f96ee9b9db36bfcdf3e6eb8cd6)\
(d2a, d2b) =
(0x55bbf0ee65ba65767b8ce233c711b1fcae7c097ac42a5977ba1876c7ce530395,
0x853be6c8ee730bf1f3abd0f53d9da934d7ad46d78aca32deee213a586641e96e)\
(d3a, d3b) =
(0x3a2bccce4eab3a7ae3a121a4a8aa276259a5de58e00ad27b7179e32c4da9602d,
0x69abc2a8d763e0f65bc010661f361e9a82d71bb5a6aaabe2a582a6bce5984606)\
(d4a, d4b) =
(0x1e9ba8ae379c0f7f4bb561158a429cc804cfb336fbeb4b7f28db4f90ccffbcc5,
0x4e1b9e88c054b5fac3d44fd700ce94002e00f093c28b24e65ce4132164eea29e)\
(d5a, d5b) =
(0x030b848e208ce483b3c9a0866bdb122daff9881517cbc482e03cbbf54c56195d,
0x328b7a68a9458aff2be88f47e2670965d92ac571de6b9dea14457f85e444ff36)\
(d6a, d6b) =
(0xe77b606e097db9881bdddff74d73879215d239d9e2f4ddc2577086e69be2b736,
0x16fb56489236600393fcceb8c3ff7ecb84549a4ffa4c16edcba6ebea639b5bce)

Finally derive public keys from the private key pairs, **P**=**d**\*G, here
the public keys are expressed in their compressed form.

(P1a, P1b) =
(02f8f1e55f7349f7ab27c078a916ec02e055164fc7e69fc23e402fa9809acfd4f4,
029472f72b94a45f0580aa1fa4556710f314c90131c2ca6008a6654610889dd954)\
(P2a, P2b) =
(037309a5ba25f35a9fac04bba70ff53fad7e571b204fae5b15823d2043536b874e,
025432596e0bc862a0600c33ab8ae3894178aec2609ff2f61302a2c101542a0031)\
(P3a, P3b) =
(02df8c2213cd1e506a71188075614630380cefb5e1f4ae403ce43a0c55eb3666f3,
031395738095ed0121e2747cb47473d1a25af083312d4fb58c66de32315fe2701d)\
(P4a, P4b) =
(03a4dc09a46077c7f58be8a70a9bff31637b58a94ebbe85215449da0f647be90b0,
02c8aa00ccde29e951e77c1d891a09f996f2484dff7d5e061a8bc5705c7074bc0b)\
(P5a, P5b) =
(02dada669eeafb333374f467c3514f7b2dfcc57a67b659c2da4f989f53b4c71875,
022ba85a0fe3eef9d9144ee70ac2d9e8487954ca4cc27450be5641721a6b3852eb)\
(P6a, P6b) =
(035df4a0bb365ba44df94e9bd2f343111e17d74e26afbe525e9c629c967a53da6f,
027bcbda9aa7d2ca15499e56e819f3144f805c35e5724e050fac30542f9746ccf2)

Now we can create a locking script requiring that the signature sizes under
all the public keys be of 59 bytes or less

```
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
02f8f1e55f7349f7ab27c078a916ec02e055164fc7e69fc23e402fa9809acfd4f4
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
029472f72b94a45f0580aa1fa4556710f314c90131c2ca6008a6654610889dd954
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
037309a5ba25f35a9fac04bba70ff53fad7e571b204fae5b15823d2043536b874e
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
025432596e0bc862a0600c33ab8ae3894178aec2609ff2f61302a2c101542a0031
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
02df8c2213cd1e506a71188075614630380cefb5e1f4ae403ce43a0c55eb3666f3
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
031395738095ed0121e2747cb47473d1a25af083312d4fb58c66de32315fe2701d
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
03a4dc09a46077c7f58be8a70a9bff31637b58a94ebbe85215449da0f647be90b0
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
02c8aa00ccde29e951e77c1d891a09f996f2484dff7d5e061a8bc5705c7074bc0b
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
02dada669eeafb333374f467c3514f7b2dfcc57a67b659c2da4f989f53b4c71875
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
022ba85a0fe3eef9d9144ee70ac2d9e8487954ca4cc27450be5641721a6b3852eb
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
035df4a0bb365ba44df94e9bd2f343111e17d74e26afbe525e9c629c967a53da6f
OP_CHECKSIGVERIFY
OP_SIZE 3c OP_LESSTHAN OP_VERIFY
027bcbda9aa7d2ca15499e56e819f3144f805c35e5724e050fac30542f9746ccf2
OP_CHECKSIGVERIFY
```

A P2WSH address of the above redeem script on testnet results in:
tb1qtcsnxzxefxvv0jqe9ax5mq45fcn4lv6rttccuhe97g3057py7wuqgnuz40

Finally we can fund the address output with some amount of BTC which will
be a reward for the miner. Like transaction
[2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075](
https://mempool.space/testnet4/tx/2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075#vout=0)
on testnet.

#### Mining/grinding

An example for mining the PoW locked output. We will use the output created
above and go through the steps required to mine it.

UTXO of the PoW locked output:
[2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075:0](
https://mempool.space/testnet4/tx/2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075#vout=0
)

We will also need a UTXO that we control, to be used in the intermediate
transaction that we will use for grinding SIGHASH_NONE.

UTXO for the intermediate transaction:
[63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd98813f254299c:1](
https://mempool.space/testnet4/tx/63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd98813f254299c#vout=1
)

##### Preparation

Convert the **x** pairs to intervals of transaction hash, the interval is
always in the form **Cn** = \[**xnb**, **xna**+2^246) ∪ \[**xnb**+(**n**
div 2)+1, **xna**+2^246+(**n** div 2)+1)

C1 = \[0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0040000000000000000000000000000000000000000000000000000000000001) ∪
\[0x800f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x803fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C2 = \[0x010f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0140000000000000000000000000000000000000000000000000000000000001) ∪
\[0x810f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x813fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C3 = \[0x020f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0240000000000000000000000000000000000000000000000000000000000001) ∪
\[0x820f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x823fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C4 = \[0x030f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0340000000000000000000000000000000000000000000000000000000000001) ∪
\[0x830f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x833fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C5 = \[0x040f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0440000000000000000000000000000000000000000000000000000000000001) ∪
\[0x840f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x843fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C6 = \[0x050f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164,
0x0540000000000000000000000000000000000000000000000000000000000001) ∪
\[0x850f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x853fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)

##### Grinding

###### SIGHASH_NONE \| ANYONECANPAY

We can vary this sighash by incrementing the nSequence of the input 0 (this
can go from 0 to 2^31) & timelock of the transaction (this can go from
500000000 to 1700000000).

Using locktime=500000000 & input 0's nSequence=11 produces a valid
sighash=0x032c7a1ced956bf3847a1063ac6e283e06554142ead66b194d3478ab4e46845a
which is contained in the interval **C4**.

###### SIGHASH_NONE

For this we need to create intermediate transaction using the intermediate
UTXO provided, such that we can vary its txId by changing intermediate tx's
locktime & nSequence fields.

We first create an ephemeral key
**de**=0x3f45d97dc47b0c2eefb61d94b6855a58247f8fdb256048d5ab65e71273031893
that will be used for the output of the intermediate tx, with corresponding
public key
**Pe**=034d1f488236a356bbc6ddcdaaaed2472af502b0206fd3b036c82f656aa30c7bb7
and P2WPKH locking script 0014366bf8aaf0e672d2c28b2a4e1c5d6a6dcb1048f6.

We create an intermediate transaction like so:

| Inputs                                                             |
Outputs
           |
|--------------------------------------------------------------------|----------------------------------------------------------------------------------------|
| 63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd98813f254299c:1 |
P2WPKH(034d1f488236a356bbc6ddcdaaaed2472af502b0206fd3b036c82f656aa30c7bb7):
18190 sats |

Which is then used in the claim transaction like so:

| Inputs                                                             |
|--------------------------------------------------------------------|
| 2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075:0 |
| \<intermediate txId\>:0                                              |

We can now start incrementing nSequence of the input 0 of the intermediate
transaction (this can go from 0 to 2^31) & timelock of the intermediate
transaction (this can go from 500000000 to 1700000000).

Using locktime=500000000 & input 0's nSequence=200 produces an intermediate
transaction
txId=23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f,
which when used as input 1 of the claim transaction creates a valid
sighash=0x051c2fb4ae682f4598c45146ec16fcd1944fa7b674571dbb4f3ba9c85c79bd6f
which is contained in the interval **C6**.

###### SIGHASH\_SINGLE and SIGHASH\_SINGLE \| ANYONECANPAY

We need to grind these 2 together, since we have no way to influence one
without also changing the other. We do this by changing the output 0's
script. To do this we could simply generate random private keys & P2WPKH
locking scripts to them, however this means generating public keys from
private keys which is orders of magnitude slow than hashing. We will
therefore use a P2WSH script which includes the nonce and then simply drops
it from the stack & then verifies the signature. The redeem script looks
like this:

```
<nonce> OP_DROP <public key> OP_CHECKSIGVERIFY OP_1
```

Using this we can simply change the nonce to change the script hash and
influence the P2WSH output script, while keeping the same public key.

We create a random claim key
**dc**=0x6484e2ecd66d7b834272e26a82aa9115b7b0591dca5b6b17ca316d58fe00a297,
with its corresponding public key
**Pc**=02b0db6b93ed9284dc957718faf3f1464cf2a47f35c12ddc1783cbebed3952d3dbad.

Now we can start incrementing the nonce in the P2WSH output script.

Using nonce=44966 we get the following P2WSH redeem script:

```
afa6 OP_DROP
02b0db6b93ed9284dc957718faf3f1464cf2a47f35c12ddc1783cbebed3952d3dbad
OP_CHECKSIGVERIFY OP_1
```

Which translates to the output script
00200369b6c884a12874f75c3d1285ca2a7119f0d977e0c60f84034b31291c6ce9fe and
produces a valid sighashes -
sighash(SIGHASH\_SINGLE)=0x012a4533d9bbc900bf5757dcc6b2f3aa8925a2fbc42708afe22b0921124f62a2
which is contained in the interval **C2** & sighash(SIGHASH\_SINGLE \|
ANYONECANPAY)=0x841d8ccc1fa672da928aae66b5a1653a227abc1fedab8a55d1c0300cf4337a33
which is contained in the interval **C5**

###### SIGHASH\_ALL and SIGHASH\_ALL \| ANYONECANPAY

We again need to grind these 2 together, since we have no way to influence
one without also changing the other. We do this by changing output 1's
output script, here we can simply use OP_RETURN.

```
OP_RETURN <nonce>
```

Now we can start incrementing the nonce in the OP_RETURN output.

Using nonce=68976 we get valid sighashes -
sighash(SIGHASH\_ALL)=0x022a721e26c9115172fc219abde406bab532df328fc83c16e8820a82f9bada6a
which is contained in the interval **C3** & sighash(SIGHASH\_ALL \|
ANYONECANPAY)=0x803fcf5814aa36a5d6488fdf26d949b5871f29764b20842170cbbccce4eb15e4
which is contained in **C1**

##### Transactions

We now have a valid set of transactions

###### Intermediate transaction

locktime=500000000

| Inputs
          | Outputs
                       |
|------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------|
| 63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd98813f254299c:1,
nSequence: 200 |
P2WPKH(034d1f488236a356bbc6ddcdaaaed2472af502b0206fd3b036c82f656aa30c7bb7):
18190 sats |

txId = [23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f](
https://mempool.space/testnet4/tx/23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f
)

###### Claim transaction

locktime=500000000

| Inputs
        | Outputs
                                                        |
|----------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------|
| 2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075:0,
nSequence=11 | P2WSH(afa6 OP_DROP
02b0db6b93ed9284dc957718faf3f1464cf2a47f35c12ddc1783cbebed3952d3db
OP_CHECKSIGVERIFY OP_1): 18690 sats |
| 23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f:0,
nSequence=0  | OP_RETURN 010d70: 0 sats
                                                             |

txId=[4017bedd84d88658291797d8cd9751fa20fa1216b1cf34cf808331c4522c66b3](
https://mempool.space/testnet4/tx/4017bedd84d88658291797d8cd9751fa20fa1216b1cf34cf808331c4522c66b3
)

We produce valid signatures by using the corresponding intervals & their
private keys:

1. Interval C1 was hit by SIGHASH\_ALL \| ANYONECANPAY, therefore we take
private keys **d1a** & **d1b**, and sign the transaction with SIGHASH\_ALL
\| ANYONECANPAY by them.
2. Interval C2 was hit by SIGHASH\_SINGLE, therefore we take private keys
**d2a** & **d2b**, and sign the transaction with SIGHASH\_SINGLE by them.
3. Interval C3 was hit by SIGHASH\_ALL, therefore we take private keys
**d3a** & **d3b**, and sign the transaction with SIGHASH\_ALL by them.
4. Interval C4 was hit by SIGHASH\_NONE \| ANYONECANPAY, therefore we take
private keys **d4a** & **d4b**, and sign the transaction with SIGHASH\_NONE
\| ANYONECANPAY by them.
5. Interval C5 was hit by SIGHASH\_SINGLE \| ANYONECANPAY, therefore we
take private keys **d5a** & **d5b**, and sign the transaction with
SIGHASH\_SINGLE \| ANYONECANPAY by them.
6. Interval C6 was hit by SIGHASH\_NONE, therefore we take private keys
**d6a** & **d6b**, and sign the transaction with SIGHASH\_NONE by them.

###### Spend transaction

Locktime or nSequences are not important here

| Inputs                                                             |
Outputs                                                |
|--------------------------------------------------------------------|--------------------------------------------------------|
| 4017bedd84d88658291797d8cd9751fa20fa1216b1cf34cf808331c4522c66b3:0 |
tb1qcjrfydsykze2htqcp6thau3v7nk5hndrsywwv6: 18550 sats |

txId=[921ba28a5f30060e8771efb9b47e83fd3d36d9f69948af2d225760a269675fca](
https://mempool.space/testnet4/tx/921ba28a5f30060e8771efb9b47e83fd3d36d9f69948af2d225760a269675fca
)

### Edge cases

#### Not enough variety for SIGHASH_NONE \| ANYONECANPAY

It might happen that in case the difficulty is high enough, the grinding
for SIGHASH_NONE \| ANYONECANPAY couldn't find any valid solution by
grinding the transaction locktime (around 1200000000 possibilities) & input
0's nSequence (around 2^31 possibilities with the most significant enable
bit being 0 to ensure no consensus meaning) - in total around ~2^61
possibilities, in that case only other option is to start grinding
transaction version, resulting in the total of ~2^93 possibilities - this
will however make the transaction non-standard and it will have to be
broadcasted directly to a miner to include it in the block. This is
unlikely to happen anytime soon though, as even with the bitcoin's current
block difficulty the chance of it happening is just \~1:10^8.

### Improvements

Miners can cache intermediary states of sha256 hash function when grinding
just parts of the transaction to speed up the process, they can also cache
sha256 hashes of outputs & inputs, respectively when changing the other.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAOY%3Dfzk-ksDGT_oyCKF%3DEJnnXaXoCbfCzxW%2B9PBQV%3Dus-K%3DPuQ%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 36583 bytes --]