path: root/64/66fc7480c6cde4dc938a788051920242c7231c

Delivery-date: Mon, 04 Nov 2024 10:34:28 -0800
Received: from mail-oo1-f57.google.com ([209.85.161.57])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDGJL34JTMKRBKFHUS4QMGQEWVUV63A@googlegroups.com>)
	id 1t81uC-0001ij-VW
	for bitcoindev@gnusha.org; Mon, 04 Nov 2024 10:34:28 -0800
Received: by mail-oo1-f57.google.com with SMTP id 006d021491bc7-5ebb84a939asf2561510eaf.2
        for <bitcoindev@gnusha.org>; Mon, 04 Nov 2024 10:34:24 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1730745259; cv=pass;
        d=google.com; s=arc-20240605;
        b=UB1tDsGO/EmkbQIwrU20HSLt1urza0R7WX3kubzXSv2G7S7DCiwQH/xtpVpPDXgCmt
         iHK3RiW7CMb1EdD/E3ydmMEFKgEhvb/fHpaAl8EaqHzFSPCg9/cLCA+p6H7WS3/Ic/1R
         2G5/m7d+16KRPz5W6PoZAkw8l73trnRqZ39tNJqpVH3eQgAsH2ToRtRJCYxf3TYDdgck
         lh1zfx8iFPc9t6ipVi8rpbz3+ZW6yK6xx1gw4QiK4zlPautP5+2C4smnzKaZCqFH4HjI
         fZD85+To6/qZloq+c6to1rbqV6H7ar3Ulb1AUH8qW5vN9qvNJtWV/SX03KUmNlk8+vrd
         19NQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:to:subject:message-id:date:from
         :mime-version:sender:dkim-signature:dkim-signature;
        bh=641UjFPppicweKe+7PCXgyjnziAu7HlJGnvJSayjtkk=;
        fh=OKviJIHXU1uYp6UbvX+N4ca2GapDRtsvf9/KRTrC958=;
        b=ZVaeYnFKlG4hFSUeApMtqyRc2c7llP6ctco+6QYCFbHd3xKeSefpiDpfkRACK82r4j
         Ir/1MwT0TNwmZAqtqapxu1GJqHLJSBEUfrqjRWT9Kr3K7A71RT0xH2riZIXR4swy5MPI
         K3slKTz2IPiSu9sVDclub+XDOSQGxmUOlO9u9WeooMS3yxE7P4zYkIujXGkpe1TjbhwV
         fiUkKG1bQ51maz9Dn1zrKhpKV8qsTSxAOgwYy/qB9PIsavgbdC56omAWk0U6EFGQsklz
         Me98z3MUwm98Z32LIYeZrqCcEbxziRDAR6d/Zh5K3CMQdfhxfLInVVuiIacULB8MDJEw
         slFA==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Pz4oj7CM;
       spf=pass (google.com: domain of adamborcany@gmail.com designates 2607:f8b0:4864:20::132 as permitted sender) smtp.mailfrom=adamborcany@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1730745259; x=1731350059; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version
         :sender:from:to:cc:subject:date:message-id:reply-to;
        bh=641UjFPppicweKe+7PCXgyjnziAu7HlJGnvJSayjtkk=;
        b=MtiPn/c5xMz9lL6SSuXgFYMEKQjMzob3V5XNucD5P+pF/J4fO7VllvrCkcyIfbYG4Q
         Z9PCCYHfEvSSkthtuW8OApck0wAF3DO5AOOGSeOwKDvvvI6gx+sFROVz92EbjqiHP+GP
         /6B1xKwQg3wQ7qq0e1STOpMnn1pC5wcmDMXsLvWmtcWMeJSEKXvMCRj4eidpD8a99oIT
         g8QmoZtYAhVb6yel/FqPfv9fCRiMky2jw9Vba5yCjFQNjBlOhg8px0qFO6rkqhpd4r7c
         r+wneOoZKxezoPCqDJs6iMuXiDWOhoDLHzPUh9E3O7Voto1g519WDO6a22CtcEUXuDTI
         ogNg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1730745259; x=1731350059; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version:from
         :to:cc:subject:date:message-id:reply-to;
        bh=641UjFPppicweKe+7PCXgyjnziAu7HlJGnvJSayjtkk=;
        b=MQPp1OQjZdJcvZHGMxS2iv+kht3kF43kTa4RWCxP4OZxvq0iMl/cClXMnvdK0IDu9i
         zJlGemYLb5GZLvJ5T94WqNAPw6Uu1UoVq7GgmVHoUDnuHB/KspW2GedW2Rsddl9wIjeI
         hOsMBgyY/Fs1Bcpk/NRUKVdsLVCfQydbiWfSpimecv9GkxKAWeHmATTZdmeQ/n6b5aGR
         UAiUPAzGkAtCPOtEX1XvWnDhQui/wfUC1Hvdko6RhBhaAxjtcMC09jKtHGROwDlWWqco
         dxx8TVm85ZUgcIHhTikhcu4mtRxHA/bbqfD8ihJlNmgAsXHidTWfwT8aYIc+kAGn1qQe
         2VKw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1730745259; x=1731350059;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:to:subject:message-id:date:from:mime-version
         :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
         :message-id:reply-to;
        bh=641UjFPppicweKe+7PCXgyjnziAu7HlJGnvJSayjtkk=;
        b=OitFeYw83iNVwP0hKAFEB7sCiaF6WW4OFxCHZDqJUHaimFH4YQmLL6DVryCV+5oa29
         VByhxEX5wP1E0erhmo/AwivMT5PWvAco31AYKaROHKuHNUB8lq3dOasXFWvPbA+VB3Ud
         a83fjlRwj9aGrmqu5dJaTGBjd+Xh8yntbxmNH+k3oLLyfLKL0472lEXONv3t+q8RriMx
         mSZ3mXSXfA71AQoRvyxC3VwpnYYtQyARL7wyt9FZhY4bYWteD5Dm8YuACljt6o8cRGzc
         wI3xZYpp8l1logrjjfFgoxNbFzZHlZvMsDQj+Td0jm3ZcSXqZTihzD9xgvenBir34I/H
         szww==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCVUFXGTHFM9iZy7zKFA/0HHyu2y4izWgL3OmzqcU6dygFbb3ySSJXi7eYQ54WONklG8lrYjORTRM51K@gnusha.org
X-Gm-Message-State: AOJu0Yzu04SvGOyhcH5ut1Yt/UeDparKhfROKy8kMRzQ0L0Hoy1qtGx9
	UPIDsnvyBgLpmnK4ZO/VTq86I2eomwS44i7219mE+gBNd/D/uX91
X-Google-Smtp-Source: AGHT+IHDvDLYtPPpYHdG1niNmwv3Fh+55/2SgPocWai/6eZpEyUibtQTGG2GQfctqgGmDeKPSSsLDA==
X-Received: by 2002:a05:6820:50c:b0:5eb:c6ba:7835 with SMTP id 006d021491bc7-5ede6186e91mr6748775eaf.0.1730745258796;
        Mon, 04 Nov 2024 10:34:18 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a4a:e6da:0:b0:5eb:b8f8:e3d0 with SMTP id 006d021491bc7-5ec6d2acf72ls2709264eaf.1.-pod-prod-06-us;
 Mon, 04 Nov 2024 10:34:16 -0800 (PST)
X-Received: by 2002:a05:6808:3848:b0:3e0:7f4a:60c9 with SMTP id 5614622812f47-3e758c17af2mr12687402b6e.12.1730745256497;
        Mon, 04 Nov 2024 10:34:16 -0800 (PST)
Received: by 2002:a05:6808:3094:b0:3e6:5ac2:d166 with SMTP id 5614622812f47-3e75a3d37b1msb6e;
        Mon, 4 Nov 2024 07:34:40 -0800 (PST)
X-Received: by 2002:a17:90b:2d8c:b0:2e2:d9f5:9cf7 with SMTP id 98e67ed59e1d1-2e94c51b3ddmr18549091a91.26.1730734479634;
        Mon, 04 Nov 2024 07:34:39 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1730734479; cv=none;
        d=google.com; s=arc-20240605;
        b=Uc5/NiYhiy4FoOdTWTWqwV6nsUjJCE63GUMqBe7gjq377fXGAtOl5UO0ZwuX6mXPL+
         wN58zEUZW3fPySHvUH1idvJAe+VYCIITxw3JFR0dk3dfWUlCv2pGHDTuzcKsTWWhnrSx
         ZXoIml52vxnYbXJ00dKDabAYoudh/RZphBcBfzTjPoDxj/k9fvYhk4CwAWTYPhAkUilf
         wMbELtL/EWdu2QKTQeUpiJJS6yV5c1yAoOiYUl2FDCAigG5E+rKGJczXtUMt8ehhQkey
         9ZjHG9pwSDupm727XKlBDQYGcVA9CuW0popgfpwku1e6ZpnXo9tpq6+c+hBeLovvH+JJ
         3xqA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=to:subject:message-id:date:from:mime-version:dkim-signature;
        bh=lSOoiIOHMHMm2lhQoD+2vpizImgaMZK14wvw6Cu7fVo=;
        fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
        b=jW2VSLJqKRugijkDFIWLEpzVr8RhmyzVP19SlzJqBc+m0k4XL1oRbj7B45UbfIYv4M
         Xq6EKovtoEbrKXHKiMGGRpT1sfd0uvmSMOmfYLF3zDb/EKDSi2hpshLzyKx965796y5/
         S3boDxWEcl3RvQCrCWyD3QpaSu+J3VRUbwZLt0M1KkXWeL/ABlnUxsNg4YRwE1rzv2dM
         S0MXlm7i26i1oCVwDE1u7rd2mH6fiaCkly/VIoEe2kx5GHskrtiq+uDL5w9JbCqEhagz
         EZxm9dyVnhYOVbn5gHPGJv2X5SirpPRUfPVGIEcClCP86oc6vDk3gwskkcnkx1wWWrqk
         VEwQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Pz4oj7CM;
       spf=pass (google.com: domain of adamborcany@gmail.com designates 2607:f8b0:4864:20::132 as permitted sender) smtp.mailfrom=adamborcany@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-il1-x132.google.com (mail-il1-x132.google.com. [2607:f8b0:4864:20::132])
        by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-2e92fbef98esi433341a91.2.2024.11.04.07.34.39
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Mon, 04 Nov 2024 07:34:39 -0800 (PST)
Received-SPF: pass (google.com: domain of adamborcany@gmail.com designates 2607:f8b0:4864:20::132 as permitted sender) client-ip=2607:f8b0:4864:20::132;
Received: by mail-il1-x132.google.com with SMTP id e9e14a558f8ab-3a394418442so14088285ab.0
        for <bitcoindev@googlegroups.com>; Mon, 04 Nov 2024 07:34:39 -0800 (PST)
X-Received: by 2002:a05:6e02:1a48:b0:3a6:ad61:8006 with SMTP id
 e9e14a558f8ab-3a6b034b0edmr118031115ab.15.1730734477720; Mon, 04 Nov 2024
 07:34:37 -0800 (PST)
MIME-Version: 1.0
From: Adam Borcany <adamborcany@gmail.com>
Date: Mon, 4 Nov 2024 16:34:25 +0100
Message-ID: <CAOY=fzk-ksDGT_oyCKF=EJnnXaXoCbfCzxW+9PBQV=us-K=PuQ@mail.gmail.com>
Subject: [bitcoindev] Bitcoin PoW locked outputs with arbitrary difficulty
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="000000000000bec95b06261805c0"
X-Original-Sender: adamborcany@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=Pz4oj7CM;       spf=pass
 (google.com: domain of adamborcany@gmail.com designates 2607:f8b0:4864:20::132
 as permitted sender) smtp.mailfrom=adamborcany@gmail.com;       dmarc=pass
 (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

--000000000000bec95b06261805c0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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) =3D 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**=3Dx_only(**k**\*G)), as discrete log is presumed to be hard in EC, o=
ne
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**=3D**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**=3D**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**=3D1/2 value
producing
**r**=3D0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
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**=3D**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** =E2=88=88 {i =E2=88=88 Z | i < 2^247}\
**k**^-1\*(**z**+**dr**) =E2=88=88 {i =E2=88=88 Z | i < 2^247}

**k** is 1/2 so the inverse is 2, and we can also let **x**=3D-**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**) =E2=88=88 {i =E2=88=88 Z | i < 2^247}\
(**z**-**x**) =E2=88=88 {i/2 | i < 2^247}

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

(**z**-**x**) =E2=88=88 {i =E2=88=88 Z | i < 2^246} =E2=88=AA {i =E2=88=88 =
Z | **n** div 2 + 1 =E2=89=A4 i < **n**
div 2 + 1 + 2^246}, where div is integer division\
**z** =E2=88=88 {i + **x** mod **n**| i < 2^246} =E2=88=AA {i + **x** mod *=
*n** | **n** div
2 + 1 =E2=89=A4 i < **n** div 2 + 1 + 2^246}

**I(x)** =3D {i + **x** mod **n**| i < 2^246} =E2=88=AA {i + **x** mod **n*=
* | **n**
div 2 + 1 =E2=89=A4 i < **n** div 2 + 1 + 2^246}\
**z** =E2=88=88 **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-diag=
ram.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**=3D-**dr** and therefore
depends only on the choosen private key **d** (**r** is fixed, since
**k**=3D1/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**=3D-**d1**\***r** and
**x2**=3D-**d2**\***r**.\
**z** =E2=88=88 **I(x1)**\
**z** =E2=88=88 **I(x2)**\
**C(x1, x2)** =3D **I(x1)** =E2=88=A9 **I(x2)**\
**z** =E2=88=88 **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\*=E2=88=86x, where =E2=88=86x =3D abs(x1-x2). The cha=
nce that any **z**
will be in the interval is P(=E2=88=86x) =3D (2^247-2\*=E2=88=86x)/**n**, o=
r in other words,
the work required is W(=E2=88=86x) =3D **n**/(2^247-2\*=E2=88=86x). This wa=
y 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 =E2=88=86x>2^246, the size of the interval turns negative=
 i.e.
intersection of the interval becomes an empty set **C**=3D=E2=88=85. 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**=3D-**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 =E2=88=86x be a pre-selected offset between private key **x** values de=
fining
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**=3D-**x**/**r** mod **n**), where private
keys in pair have an overlap defined by =E2=88=86x and different pairs have=
 no
overlap.

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

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(=E2=88=86x)^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(=E2=88=86x)/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(=E2=88=86x)/5, how=
ever 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(=E2=88=86x)/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(=E2=88=86x)^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(=E2=88=86x)^2/2\*1

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

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

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

**=E2=88=86x** =3D 105**n**/(102 - 6\*sqrt(289+2100\***Wt(=E2=88=86x)**)) +=
 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(=E2=88=86x)**/6, compared to e.g. **W(=E2=88=86x)**^2/2 for both S=
IGHASH_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** =3D
0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\
Required work **Wt** =3D 0x40000\
**=E2=88=86x** =3D 0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081=
445bacc163

Interval pairs (**x** values)

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

Derive private key pairs from the **x** value pairs, **d**=3D-**x**/**r** m=
od
**n**

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

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

(P1a, P1b) =3D
(02f8f1e55f7349f7ab27c078a916ec02e055164fc7e69fc23e402fa9809acfd4f4,
029472f72b94a45f0580aa1fa4556710f314c90131c2ca6008a6654610889dd954)\
(P2a, P2b) =3D
(037309a5ba25f35a9fac04bba70ff53fad7e571b204fae5b15823d2043536b874e,
025432596e0bc862a0600c33ab8ae3894178aec2609ff2f61302a2c101542a0031)\
(P3a, P3b) =3D
(02df8c2213cd1e506a71188075614630380cefb5e1f4ae403ce43a0c55eb3666f3,
031395738095ed0121e2747cb47473d1a25af083312d4fb58c66de32315fe2701d)\
(P4a, P4b) =3D
(03a4dc09a46077c7f58be8a70a9bff31637b58a94ebbe85215449da0f647be90b0,
02c8aa00ccde29e951e77c1d891a09f996f2484dff7d5e061a8bc5705c7074bc0b)\
(P5a, P5b) =3D
(02dada669eeafb333374f467c3514f7b2dfcc57a67b659c2da4f989f53b4c71875,
022ba85a0fe3eef9d9144ee70ac2d9e8487954ca4cc27450be5641721a6b3852eb)\
(P6a, P6b) =3D
(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/2c6747829c435da3be23ba350c7d5eab5b9fb8717=
de2613973191305779e3075#vout=3D0)
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/2c6747829c435da3be23ba350c7d5eab5b9fb8717=
de2613973191305779e3075#vout=3D0
)

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/63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5=
a693273fbd98813f254299c#vout=3D1
)

##### Preparation

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

C1 =3D \[0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0040000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[0x800f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x803fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C2 =3D \[0x010f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0140000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[0x810f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x813fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C3 =3D \[0x020f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0240000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[0x820f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x823fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C4 =3D \[0x030f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0340000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[0x830f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x833fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C5 =3D \[0x040f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0440000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[0x840f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205,
0x843fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\
C6 =3D \[0x050f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164=
,
0x0540000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA
\[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=3D500000000 & input 0's nSequence=3D11 produces a valid
sighash=3D0x032c7a1ced956bf3847a1063ac6e283e06554142ead66b194d3478ab4e46845=
a
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**=3D0x3f45d97dc47b0c2eefb61d94b6855a58247f8fdb256048d5ab65e71273031893
that will be used for the output of the intermediate tx, with corresponding
public key
**Pe**=3D034d1f488236a356bbc6ddcdaaaed2472af502b0206fd3b036c82f656aa30c7bb7
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=3D500000000 & input 0's nSequence=3D200 produces an intermed=
iate
transaction
txId=3D23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f,
which when used as input 1 of the claim transaction creates a valid
sighash=3D0x051c2fb4ae682f4598c45146ec16fcd1944fa7b674571dbb4f3ba9c85c79bd6=
f
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**=3D0x6484e2ecd66d7b834272e26a82aa9115b7b0591dca5b6b17ca316d58fe00a297=
,
with its corresponding public key
**Pc**=3D02b0db6b93ed9284dc957718faf3f1464cf2a47f35c12ddc1783cbebed3952d3db=
ad.

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

Using nonce=3D44966 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)=3D0x012a4533d9bbc900bf5757dcc6b2f3aa8925a2fbc42708=
afe22b0921124f62a2
which is contained in the interval **C2** & sighash(SIGHASH\_SINGLE \|
ANYONECANPAY)=3D0x841d8ccc1fa672da928aae66b5a1653a227abc1fedab8a55d1c0300cf=
4337a33
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=3D68976 we get valid sighashes -
sighash(SIGHASH\_ALL)=3D0x022a721e26c9115172fc219abde406bab532df328fc83c16e=
8820a82f9bada6a
which is contained in the interval **C3** & sighash(SIGHASH\_ALL \|
ANYONECANPAY)=3D0x803fcf5814aa36a5d6488fdf26d949b5871f29764b20842170cbbccce=
4eb15e4
which is contained in **C1**

##### Transactions

We now have a valid set of transactions

###### Intermediate transaction

locktime=3D500000000

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

txId =3D [23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215e84f]=
(
https://mempool.space/testnet4/tx/23990f08e0e7cb6e22ea1837241d5884c84d2398a=
82f5469e63d022ce215e84f
)

###### Claim transaction

locktime=3D500000000

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

txId=3D[4017bedd84d88658291797d8cd9751fa20fa1216b1cf34cf808331c4522c66b3](
https://mempool.space/testnet4/tx/4017bedd84d88658291797d8cd9751fa20fa1216b=
1cf34cf808331c4522c66b3
)

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=3D[921ba28a5f30060e8771efb9b47e83fd3d36d9f69948af2d225760a269675fca](
https://mempool.space/testnet4/tx/921ba28a5f30060e8771efb9b47e83fd3d36d9f69=
948af2d225760a269675fca
)

### 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.

--=20
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 e=
mail 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.

--000000000000bec95b06261805c0
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hello everyone,</div><div><br></div><div>The discussi=
on about <a href=3D"https://groups.google.com/g/bitcoindev/c/mR53go5gHIk">S=
igning a Bitcoin Transaction with Lamport Signatures</a> here on the mailin=
g list sparked an idea about using the mathematical properties of short DER=
-encoded ECDSA signatures for proof-of-work locked outputs allowing for arb=
itrary difficulty.</div><div><br></div><div>Here I am posting a write-up de=
fining how exactly to do this along with the proof of concept Node.JS code =
allowing you to create PoW-locked output scripts &amp; mining them: <a href=
=3D"https://github.com/adambor/btc-pow-locked-outputs/">https://github.com/=
adambor/btc-pow-locked-outputs/</a>. The full write-up below.<br></div><div=
><br></div># Bitcoin PoW-locked outputs with arbitrary difficulty<br><br>##=
 Abstract<br><br>The best current way to do PoW-locked output scripts in bi=
tcoin is to use signature grinding, this however doesn&#39;t allow smooth d=
ifficulty adjustments, as it works with byte size of the DER encoded signat=
ure, so the adjustment steps are either 256 times the prior difficulty to t=
he the upside or prior difficulty divided by 256. Here we first present cur=
rent 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 wi=
th fully arbitrary difficulty (the lowest difficulty being 2^18) by just us=
ing 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 in=
volves no operations in the finite field or elliptic curve operations.<br><=
br>## Simple signature grinding<br><br>Signature grinding is based on the f=
act that ECDSA signatures in bitcoin are DER encoded, so they have variable=
 size based on the amount of leading zero bytes in the signature&#39;s **r*=
* &amp; **s** values. The size of the DER encoded signature is 2 (DER prefi=
x) + 2 (r value prefix) + size(**r**) + 2 (s value prefix) + size(**s**) + =
1 (sighash flag) =3D 7 + size(**r**) + size(**s**), where size() is the enc=
oded byte size of the variable, it&#39;s also important to note that encode=
d 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).<br><br=
>The **r** value is the x coordinate of a signing nonce point (**r**=3Dx_on=
ly(**k**\*G)), as discrete log is presumed to be hard in EC, one needs to g=
rind through multiple nonces **k** to get the **r** value that has a pre-de=
fined amount of leading zero bytes.<br><br>The **s** value can be computed =
as **s**=3D**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.<br><br>### Application<br><br>As we can only restrict the full lengt=
h of the signature (including length changes from both **r** &amp; **s** va=
lues combined) with OP_SIZE opcode, the best course of action for a miner i=
s 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.=
<br><br>#### Base case<br><br>In the base case this would mean miners const=
antly 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 grin=
d the **s** value, since private key **d** is publicly known, everyone woul=
d get to know the **k** used to produce the short **r** (one can easily sol=
ve **s**=3D**k**^-1\*(z-**dr**) for **k** by knowing s, r, d &amp; z) and o=
ther miners can now re-use it.<br><br>#### Using well known short nonce poi=
nt<br><br>For the secp256k1 curve we already know of a specific **k**=3D1/2=
 value producing **r**=3D0x00000000000000000000003b78ce563f89a0ed9414f5aa28=
ad0d96d6795f9c63 with 11 leading zero bytes (88-bits). Producing a shorter =
**r** is highly unlikely as it would require grinding through 2^96 **k** va=
lues 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 t=
he work required is 2\*256^**p** (the 2 multiple is because of the most sig=
nficant bit having to be 0).<br><br>### Drawbacks<br><br>As can be seen fro=
m 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 diff=
iculty 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 scrip=
t limitations such as 10kB of size &amp; up to 201 of non-push opcodes.<br>=
<br>## Mathematical structure of short signatures<br><br>For the signature =
value **s** to be short (have certain amount of leading zero bytes), we can=
 say that **s** &lt; 2^(8\*(32-**b**)-1), where **b** is the amount of lead=
ing zero bytes that we want to achieve. Let&#39;s look more closely into a =
specific case where we want to achieve 1 leading zero byte &amp; use the we=
ll known short nonce **k** - the DER encoded signature size in this case is=
 59 bytes or less.<br><br>**s**=3D**k**^-1\*(**z**+**dr**) mod **n**; **s**=
 &lt; 2^247<br><br>Since comparison operators are not defined over a finite=
 field (and calculation of **s** is done in the finite field modulo field o=
rder **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<br><br>=
**s** =E2=88=88 {i =E2=88=88 Z | i &lt; 2^247}\<br>**k**^-1\*(**z**+**dr**)=
 =E2=88=88 {i =E2=88=88 Z | i &lt; 2^247}<br><br>**k** is 1/2 so the invers=
e is 2, and we can also let **x**=3D-**dr** mod **n**, since **d** is a con=
stant private key and **r** is also a constant since we use a constant **k*=
* (the minus sign will become apparent later).<br><br>2\*(**z**-**x**) =E2=
=88=88 {i =E2=88=88 Z | i &lt; 2^247}\<br>(**z**-**x**) =E2=88=88 {i/2 | i =
&lt; 2^247}<br><br>Which we can write as (keep in mind i/2 is division in t=
he finite field)<br><br>(**z**-**x**) =E2=88=88 {i =E2=88=88 Z | i &lt; 2^2=
46} =E2=88=AA {i =E2=88=88 Z | **n** div 2 + 1 =E2=89=A4 i &lt; **n** div 2=
 + 1 + 2^246}, where div is integer division\<br>**z** =E2=88=88 {i + **x**=
 mod **n**| i &lt; 2^246} =E2=88=AA {i + **x** mod **n** | **n** div 2 + 1 =
=E2=89=A4 i &lt; **n** div 2 + 1 + 2^246}<br><br>**I(x)** =3D {i + **x** mo=
d **n**| i &lt; 2^246} =E2=88=AA {i + **x** mod **n** | **n** div 2 + 1 =E2=
=89=A4 i &lt; **n** div 2 + 1 + 2^246}\<br>**z** =E2=88=88 **I(x)**<br><br>=
This complicated-looking interval can be easily represented on the finite f=
ield circle<br><br>![FF circle single key](<a href=3D"https://github.com/ad=
ambor/btc-pow-locked-outputs/blob/main/single-key-diagram.png">https://gith=
ub.com/adambor/btc-pow-locked-outputs/blob/main/single-key-diagram.png</a>)=
<br><br>What this shows is that the signature&#39;s s-value having at least=
 1 leading zero byte depends on the transaction hash **z** being in some in=
terval **I(x)**, which is a function of the constant **x**=3D-**dr** and th=
erefore depends only on the choosen private key **d** (**r** is fixed, sinc=
e **k**=3D1/2). Moreover the interval always has the size of 2^247 field el=
ements - 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%.<br><br>###=
 Abitrary sized intervals<br><br>By using 2 private keys, and requiring tha=
t the miner produces short signatures for both of them over a single transa=
ction hash we can make sure that the transaction hash is included in both o=
f the intervals, or in other words the transaction hash is in the intersect=
ion of the 2 intervals.<br><br>Let **d1**, **d2** be the private keys, then=
 **x1**=3D-**d1**\***r** and **x2**=3D-**d2**\***r**.\<br>**z** =E2=88=88 *=
*I(x1)**\<br>**z** =E2=88=88 **I(x2)**\<br>**C(x1, x2)** =3D **I(x1)** =E2=
=88=A9 **I(x2)**\<br>**z** =E2=88=88 **C(x1, x2)**<br><br>![FF circle two k=
ey](<a href=3D"https://github.com/adambor/btc-pow-locked-outputs/blob/main/=
two-key-diagram.png">https://github.com/adambor/btc-pow-locked-outputs/blob=
/main/two-key-diagram.png</a>)<br><br>The interval **C(x1,x2)** (dotted are=
a 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\*=E2=88=86x, where =
=E2=88=86x =3D abs(x1-x2). The chance that any **z** will be in the interva=
l is P(=E2=88=86x) =3D (2^247-2\*=E2=88=86x)/**n**, or in other words, the =
work required is W(=E2=88=86x) =3D **n**/(2^247-2\*=E2=88=86x). This way we=
 can fine-tune the chance that any transaction hash **z** will be in the in=
terval (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.<br><br>### Non-overlapping intervals<=
br><br>If we were to use =E2=88=86x&gt;2^246, the size of the interval turn=
s negative i.e. intersection of the interval becomes an empty set **C**=3D=
=E2=88=85. 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 h=
appens we can be sure that 2 signatures are produced over different transac=
tion hashes (i.e. different sighash flag in bitcoin). This means that if we=
 use 2 private keys with their corresponding **x** values (recall **x**=3D-=
**dr** mod **n**) further than 2^246 apart from each other (such that their=
 intervals **I(x)** don&#39;t overlap) we can force the miner to use 2 diff=
erent sighashes. By extension if we use 6 private keys that produce non-ove=
rlapping intervals we can force the miner to use all 6 possible sighashes p=
ossible on bitcoin today.<br><br>## Arbitrary difficulty signature grinding=
<br><br>We will use a mix of overlapping &amp; 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 sam=
e transaction hash (have the same sighash flag).<br><br>Let =E2=88=86x be a=
 pre-selected offset between private key **x** values defining the difficul=
ty 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 p=
rivate key **d**=3D-**x**/**r** mod **n**), where private keys in pair have=
 an overlap defined by =E2=88=86x and different pairs have no overlap.<br><=
br>(x1a, x1b) =3D (1, 1 + =E2=88=86x)\<br>(x2a, x2b) =3D (2^248 + 1, 2^248 =
+ 1 + =E2=88=86x)\<br>(x3a, x3b) =3D (2\*2^248 + 1, 2\*2^248 + 1 + =E2=88=
=86x)\<br>(x4a, x4b) =3D (3\*2^248 + 1, 3\*2^248 + 1 + =E2=88=86x)\<br>(x5a=
, x5b) =3D (4\*2^248 + 1, 4\*2^248 + 1 + =E2=88=86x)\<br>(x6a, x6b) =3D (5\=
*2^248 + 1, 5\*2^248 + 1 + =E2=88=86x)<br><br>This forces the miner to use =
a different sighash flag for every one of the 6 intervals defined by overla=
pping interval private key pairs, ensuring that our need for both signature=
s to use the same transaction hash for overlapping intervals holds.<br><br>=
### Estimating difficulty<br><br>A naive approach would be to say that the =
difficulty (work required) in this construction is (W(=E2=88=86x)^6)/6! - a=
s we need to hit 6 different transaction hashes **z** within a pre-specifie=
d intervals. It is important to note however that some sighashes can be ind=
ependent of each other. Here is a table of bitcoin sighashes and their depe=
ndencies in a 2-input &amp; 2-output bitcoin transaction:<br><br>| Sighash =
flag =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0| =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br>|---------------------------=
-----|-------------------|---------|---------|----------|----------|<br>| S=
IGHASH_NONE \| ANYONECANPAY =C2=A0 | locktime, version | input 0 | =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0|<br>| SIGHASH_NONE =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 | locktime, version | input 0 | input 1 | =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br>| S=
IGHASH_SINGLE \| ANYONECANPAY | locktime, version | input 0 | =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 | output 0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br>| SIGHAS=
H_SINGLE =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | locktime=
, version | input 0 | input 1 | output 0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0|<br>| SIGHASH_ALL \| ANYONECANPAY =C2=A0 =C2=A0| locktime, version | in=
put 0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 | output 0 | output 1 |<br>| SIGHASH_AL=
L =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| lo=
cktime, version | input 0 | input 1 | output 0 | output 1 |<br><br>Therefor=
e the optimal way to produce all the required hashes/signatures is as follo=
ws:<br><br>1. SIGHASH_NONE \| ANYONECANPAY - grind the transaction locktime=
 &amp; input 0 nSequence number to get a valid transaction hash in any of t=
he intervals, work required is W(=E2=88=86x)/6<br>2. SIGHASH_NONE - grind t=
he input 1, since only UTXO transaction hash &amp; vout is used in the tran=
saction hash we need to create an intermediate transaction, whose UTXO we w=
ill use as input 1 and then grind the transaction id of this intermediate t=
ransacton, which will affect the transaction hash of this transaction, work=
 required is W(=E2=88=86x)/5, however as we need to do 2x more hashing (sin=
ce we also need to hash the intermediate transaction every time) the real w=
ork is 2*W(=E2=88=86x)/5<br>3. SIGHASH_SINGLE \| ANYONECANPAY and SIGHASH_S=
INGLE - 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(=E2=88=86x)^2/4\*3<br>4. SI=
GHASH_ALL \| ANYONECANPAY and SIGHASH_ALL - these also need to be done toge=
ther, since only difference between them is again just the input 1, which w=
as already set in step 2, we can grind the output 1 locking script or value=
, the work required is W(=E2=88=86x)^2/2\*1<br><br>We can therefore express=
 the total work that needs to be done by a miner as **Wt(=E2=88=86x)** =3D =
**W(=E2=88=86x)**/6 + 2\***W(=E2=88=86x)**/5+ **W(=E2=88=86x)**^2/4\*3 + **=
W(=E2=88=86x)**^2/2. Based on this equation we can derive an equation for c=
alculating **=E2=88=86x** from the required work **Wt**.<br><br>**Wt(=E2=88=
=86x)** =3D **W(=E2=88=86x)**/6 + 2\***W(=E2=88=86x)**/5 + **W(=E2=88=86x)*=
*^2/4\*3 + **W(=E2=88=86x)**^2/2\<br>**Wt(=E2=88=86x)** =3D 17/30\***W(=E2=
=88=86x)** + 7/12\***W(=E2=88=86x)**^2\<br>0 =3D 7/12\***W(=E2=88=86x)**^2 =
+ 17/30\***W(=E2=88=86x)** - **Wt(=E2=88=86x)**<br><br>**W(=E2=88=86x)** =
=3D (-17/30 + sqrt(289/900 + 7/3\***Wt(=E2=88=86x)**))/(7/6)\<br>**W(=E2=88=
=86x)** =3D 1/105*(3\*sqrt(289+2100\***Wt(=E2=88=86x)**) - 51)\<br>**n**/(2=
^248-2**=E2=88=86x**) =3D 1/105*(3\*sqrt(289+2100\***Wt(=E2=88=86x)**) - 51=
)\<br>2^247-2**=E2=88=86x** =3D 105**n**/(3\*sqrt(289+2100\***Wt(=E2=88=86x=
)**) - 51)<br><br>**=E2=88=86x** =3D 105**n**/(102 - 6\*sqrt(289+2100\***Wt=
(=E2=88=86x)**)) + 2^246<br><br>### Claim transaction structure<br><br>The =
claim transaction needs to be carefully crafted as to not allow other miner=
s to gain advantage from it.<br><br>If the claim transaction is already pub=
lished 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 n=
ot signficant though, since grinding the SIGHASH_NONE \| ANYONECANPAY is th=
e easiest (total work contribution is just **W(=E2=88=86x)**/6, compared to=
 e.g. **W(=E2=88=86x)**^2/2 for both SIGHASH_ALL &amp; ANYONECANPAY) - this=
 is something we cannot eliminate.<br><br>Other miners could also re-use SI=
GHASH_SINGLE \| ANYONECANPAY, but this would mean they cannot change the ou=
tput 0 of the transaction, it is therefore required to put the most signifi=
cant output (e.g. the payout output) as the first output of the transaction=
. Same applies for SIGHASH_ALL \| ANYONECANPAY, however this is already cov=
ered by just using the output 0 of the transaction as the most significant =
output.<br><br>To prevent other miners from re-using non-ANYONECANPAY signa=
tures, 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.<br><br>| Inputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| Outputs =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 |<br>|-----------------------------------------------|----------=
-------------------------------|<br>| input0: PoW-locked UTXO =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | output0: =
Most significant (e.g. payout) |<br>| input1: P2WPKH UTXO (signed with SIGH=
ASH_ALL) | output1: Insignificant (e.g. OP_RETURN) |<br><br>### Example<br>=
<br>There is a Node.JS application in /example directory of the repo, allow=
ing you to create &amp; mine PoW-locked output with arbitrary difficulty (w=
ork). Here is a detailed example of how the code actually works.<br><br>###=
# Setup<br><br>A simple example for constructing an output with a difficult=
y of 2^18 (a miner on average has to go through 262144 hashes to find a sol=
ution) - all numbers are in hexadecimal.<br><br>Field order **n** =3D 0xfff=
ffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\<br>Required =
work **Wt** =3D 0x40000\<br>**=E2=88=86x** =3D 0x000f1504f7dd7ed3811e84e2e6=
80f496e766d6579e327969296081445bacc163<br><br>Interval pairs (**x** values)=
<br><br>(x1a, x1b) =3D (0x0000000000000000000000000000000000000000000000000=
000000000000001, 0x000f1504f7dd7ed3811e84e2e680f496e766d6579e32796929608144=
5bacc164)\<br>(x2a, x2b) =3D (0x0100000000000000000000000000000000000000000=
000000000000000000001, 0x010f1504f7dd7ed3811e84e2e680f496e766d6579e32796929=
6081445bacc164)\<br>(x3a, x3b) =3D (0x0200000000000000000000000000000000000=
000000000000000000000000001, 0x020f1504f7dd7ed3811e84e2e680f496e766d6579e32=
7969296081445bacc164)\<br>(x4a, x4b) =3D (0x0300000000000000000000000000000=
000000000000000000000000000000001, 0x030f1504f7dd7ed3811e84e2e680f496e766d6=
579e327969296081445bacc164)\<br>(x5a, x5b) =3D (0x0400000000000000000000000=
000000000000000000000000000000000000001, 0x040f1504f7dd7ed3811e84e2e680f496=
e766d6579e327969296081445bacc164)\<br>(x6a, x6b) =3D (0x0500000000000000000=
000000000000000000000000000000000000000000001, 0x050f1504f7dd7ed3811e84e2e6=
80f496e766d6579e327969296081445bacc164)<br><br>Derive private key pairs fro=
m the **x** value pairs, **d**=3D-**x**/**r** mod **n**<br><br>(d1a, d1b) =
=3D (0x714c150e7cc990721378a2c2e5793c970352349ca849e07402b70a634efca6fd, 0x=
a0cc0ae9058236ed8b9791845c0533cf2c8371f96ee9b9db36bfcdf3e6eb8cd6)\<br>(d2a,=
 d2b) =3D (0x55bbf0ee65ba65767b8ce233c711b1fcae7c097ac42a5977ba1876c7ce5303=
95, 0x853be6c8ee730bf1f3abd0f53d9da934d7ad46d78aca32deee213a586641e96e)\<br=
>(d3a, d3b) =3D (0x3a2bccce4eab3a7ae3a121a4a8aa276259a5de58e00ad27b7179e32c=
4da9602d, 0x69abc2a8d763e0f65bc010661f361e9a82d71bb5a6aaabe2a582a6bce598460=
6)\<br>(d4a, d4b) =3D (0x1e9ba8ae379c0f7f4bb561158a429cc804cfb336fbeb4b7f28=
db4f90ccffbcc5, 0x4e1b9e88c054b5fac3d44fd700ce94002e00f093c28b24e65ce413216=
4eea29e)\<br>(d5a, d5b) =3D (0x030b848e208ce483b3c9a0866bdb122daff9881517cb=
c482e03cbbf54c56195d, 0x328b7a68a9458aff2be88f47e2670965d92ac571de6b9dea144=
57f85e444ff36)\<br>(d6a, d6b) =3D (0xe77b606e097db9881bdddff74d73879215d239=
d9e2f4ddc2577086e69be2b736, 0x16fb56489236600393fcceb8c3ff7ecb84549a4ffa4c1=
6edcba6ebea639b5bce)<br><br>Finally derive public keys from the private key=
 pairs, **P**=3D**d**\*G, here the public keys are expressed in their compr=
essed form.<br><br>(P1a, P1b) =3D (02f8f1e55f7349f7ab27c078a916ec02e055164f=
c7e69fc23e402fa9809acfd4f4, 029472f72b94a45f0580aa1fa4556710f314c90131c2ca6=
008a6654610889dd954)\<br>(P2a, P2b) =3D (037309a5ba25f35a9fac04bba70ff53fad=
7e571b204fae5b15823d2043536b874e, 025432596e0bc862a0600c33ab8ae3894178aec26=
09ff2f61302a2c101542a0031)\<br>(P3a, P3b) =3D (02df8c2213cd1e506a7118807561=
4630380cefb5e1f4ae403ce43a0c55eb3666f3, 031395738095ed0121e2747cb47473d1a25=
af083312d4fb58c66de32315fe2701d)\<br>(P4a, P4b) =3D (03a4dc09a46077c7f58be8=
a70a9bff31637b58a94ebbe85215449da0f647be90b0, 02c8aa00ccde29e951e77c1d891a0=
9f996f2484dff7d5e061a8bc5705c7074bc0b)\<br>(P5a, P5b) =3D (02dada669eeafb33=
3374f467c3514f7b2dfcc57a67b659c2da4f989f53b4c71875, 022ba85a0fe3eef9d9144ee=
70ac2d9e8487954ca4cc27450be5641721a6b3852eb)\<br>(P6a, P6b) =3D (035df4a0bb=
365ba44df94e9bd2f343111e17d74e26afbe525e9c629c967a53da6f, 027bcbda9aa7d2ca1=
5499e56e819f3144f805c35e5724e050fac30542f9746ccf2)<br><br>Now we can create=
 a locking script requiring that the signature sizes under all the public k=
eys be of 59 bytes or less<br><br>```<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 0=
2f8f1e55f7349f7ab27c078a916ec02e055164fc7e69fc23e402fa9809acfd4f4 OP_CHECKS=
IGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 029472f72b94a45f0580aa1fa45567=
10f314c90131c2ca6008a6654610889dd954 OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LES=
STHAN OP_VERIFY 037309a5ba25f35a9fac04bba70ff53fad7e571b204fae5b15823d20435=
36b874e OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 025432596e0bc=
862a0600c33ab8ae3894178aec2609ff2f61302a2c101542a0031 OP_CHECKSIGVERIFY<br>=
OP_SIZE 3c OP_LESSTHAN OP_VERIFY 02df8c2213cd1e506a71188075614630380cefb5e1=
f4ae403ce43a0c55eb3666f3 OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VER=
IFY 031395738095ed0121e2747cb47473d1a25af083312d4fb58c66de32315fe2701d OP_C=
HECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 03a4dc09a46077c7f58be8a70=
a9bff31637b58a94ebbe85215449da0f647be90b0 OP_CHECKSIGVERIFY<br>OP_SIZE 3c O=
P_LESSTHAN OP_VERIFY 02c8aa00ccde29e951e77c1d891a09f996f2484dff7d5e061a8bc5=
705c7074bc0b OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 02dada66=
9eeafb333374f467c3514f7b2dfcc57a67b659c2da4f989f53b4c71875 OP_CHECKSIGVERIF=
Y<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 022ba85a0fe3eef9d9144ee70ac2d9e848795=
4ca4cc27450be5641721a6b3852eb OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN O=
P_VERIFY 035df4a0bb365ba44df94e9bd2f343111e17d74e26afbe525e9c629c967a53da6f=
 OP_CHECKSIGVERIFY<br>OP_SIZE 3c OP_LESSTHAN OP_VERIFY 027bcbda9aa7d2ca1549=
9e56e819f3144f805c35e5724e050fac30542f9746ccf2 OP_CHECKSIGVERIFY<br>```<br>=
<br>A P2WSH address of the above redeem script on testnet results in: tb1qt=
csnxzxefxvv0jqe9ax5mq45fcn4lv6rttccuhe97g3057py7wuqgnuz40<br><br>Finally we=
 can fund the address output with some amount of BTC which will be a reward=
 for the miner. Like transaction [2c6747829c435da3be23ba350c7d5eab5b9fb8717=
de2613973191305779e3075](<a href=3D"https://mempool.space/testnet4/tx/2c674=
7829c435da3be23ba350c7d5eab5b9fb8717de2613973191305779e3075#vout=3D0">https=
://mempool.space/testnet4/tx/2c6747829c435da3be23ba350c7d5eab5b9fb8717de261=
3973191305779e3075#vout=3D0</a>) on testnet.<br><br>#### Mining/grinding<br=
><br>An example for mining the PoW locked output. We will use the output cr=
eated above and go through the steps required to mine it.<br><br>UTXO of th=
e PoW locked output: [2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191=
305779e3075:0](<a href=3D"https://mempool.space/testnet4/tx/2c6747829c435da=
3be23ba350c7d5eab5b9fb8717de2613973191305779e3075#vout=3D0">https://mempool=
.space/testnet4/tx/2c6747829c435da3be23ba350c7d5eab5b9fb8717de2613973191305=
779e3075#vout=3D0</a>)<br><br>We will also need a UTXO that we control, to =
be used in the intermediate transaction that we will use for grinding SIGHA=
SH_NONE. <br><br>UTXO for the intermediate transaction: [63e0fcd8c7a828dc97=
9da397fa82fdd7d8e49b9d5a693273fbd98813f254299c:1](<a href=3D"https://mempoo=
l.space/testnet4/tx/63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd9881=
3f254299c#vout=3D1">https://mempool.space/testnet4/tx/63e0fcd8c7a828dc979da=
397fa82fdd7d8e49b9d5a693273fbd98813f254299c#vout=3D1</a>)<br><br>##### Prep=
aration<br><br>Convert the **x** pairs to intervals of transaction hash, th=
e interval is always in the form **Cn** =3D \[**xnb**, **xna**+2^246) =E2=
=88=AA \[**xnb**+(**n** div 2)+1, **xna**+2^246+(**n** div 2)+1)<br><br>C1 =
=3D \[0x000f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0040000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x800f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x803fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\<br>C2 =
=3D \[0x010f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0140000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x810f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x813fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\<br>C3 =
=3D \[0x020f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0240000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x820f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x823fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\<br>C4 =
=3D \[0x030f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0340000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x830f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x833fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\<br>C5 =
=3D \[0x040f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0440000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x840f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x843fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)\<br>C6 =
=3D \[0x050f1504f7dd7ed3811e84e2e680f496e766d6579e327969296081445bacc164, 0=
x0540000000000000000000000000000000000000000000000000000000000001) =E2=88=
=AA \[0x850f1504f7dd7ed3811e84e2e680f49644be44caf5d6c9870949b08ac3c7e205, 0=
x853fffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2)<br><br>#=
#### Grinding<br><br>###### SIGHASH_NONE \| ANYONECANPAY<br><br>We can vary=
 this sighash by incrementing the nSequence of the input 0 (this can go fro=
m 0 to 2^31) &amp; timelock of the transaction (this can go from 500000000 =
to 1700000000).<br><br>Using locktime=3D500000000 &amp; input 0&#39;s nSequ=
ence=3D11 produces a valid sighash=3D0x032c7a1ced956bf3847a1063ac6e283e0655=
4142ead66b194d3478ab4e46845a which is contained in the interval **C4**.<br>=
<br>###### SIGHASH_NONE<br><br>For this we need to create intermediate tran=
saction using the intermediate UTXO provided, such that we can vary its txI=
d by changing intermediate tx&#39;s locktime &amp; nSequence fields.<br><br=
>We first create an ephemeral key **de**=3D0x3f45d97dc47b0c2eefb61d94b6855a=
58247f8fdb256048d5ab65e71273031893 that will be used for the output of the =
intermediate tx, with corresponding public key **Pe**=3D034d1f488236a356bbc=
6ddcdaaaed2472af502b0206fd3b036c82f656aa30c7bb7 and P2WPKH locking script 0=
014366bf8aaf0e672d2c28b2a4e1c5d6a6dcb1048f6.<br><br>We create an intermedia=
te transaction like so:<br><br>| Inputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 | Outputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0|<br>|---------------------------------------------=
-----------------------|---------------------------------------------------=
-------------------------------------|<br>| 63e0fcd8c7a828dc979da397fa82fdd=
7d8e49b9d5a693273fbd98813f254299c:1 | P2WPKH(034d1f488236a356bbc6ddcdaaaed2=
472af502b0206fd3b036c82f656aa30c7bb7): 18190 sats |<br><br>Which is then us=
ed in the claim transaction like so:<br><br>| Inputs =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 |<br>|---------------------------=
-----------------------------------------|<br>| 2c6747829c435da3be23ba350c7=
d5eab5b9fb8717de2613973191305779e3075:0 |<br>| \&lt;intermediate txId\&gt;:=
0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0|<br><br>We can now start incrementing nSequence of the input =
0 of the intermediate transaction (this can go from 0 to 2^31) &amp; timelo=
ck of the intermediate transaction (this can go from 500000000 to 170000000=
0).<br><br>Using locktime=3D500000000 &amp; input 0&#39;s nSequence=3D200 p=
roduces an intermediate transaction txId=3D23990f08e0e7cb6e22ea1837241d5884=
c84d2398a82f5469e63d022ce215e84f, which when used as input 1 of the claim t=
ransaction creates a valid sighash=3D0x051c2fb4ae682f4598c45146ec16fcd1944f=
a7b674571dbb4f3ba9c85c79bd6f which is contained in the interval **C6**.<br>=
<br>###### SIGHASH\_SINGLE and SIGHASH\_SINGLE \| ANYONECANPAY<br><br>We ne=
ed 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&#39;s script.=
 To do this we could simply generate random private keys &amp; P2WPKH locki=
ng 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 s=
tack &amp; then verifies the signature. The redeem script looks like this:<=
br><br>```<br>&lt;nonce&gt; OP_DROP &lt;public key&gt; OP_CHECKSIGVERIFY OP=
_1<br>```<br><br>Using this we can simply change the nonce to change the sc=
ript hash and influence the P2WSH output script, while keeping the same pub=
lic key.<br><br>We create a random claim key **dc**=3D0x6484e2ecd66d7b83427=
2e26a82aa9115b7b0591dca5b6b17ca316d58fe00a297, with its corresponding publi=
c key **Pc**=3D02b0db6b93ed9284dc957718faf3f1464cf2a47f35c12ddc1783cbebed39=
52d3dbad.<br><br>Now we can start incrementing the nonce in the P2WSH outpu=
t script.<br><br>Using nonce=3D44966 we get the following P2WSH redeem scri=
pt:<br><br>```<br>afa6 OP_DROP 02b0db6b93ed9284dc957718faf3f1464cf2a47f35c1=
2ddc1783cbebed3952d3dbad OP_CHECKSIGVERIFY OP_1<br>```<br><br>Which transla=
tes to the output script 00200369b6c884a12874f75c3d1285ca2a7119f0d977e0c60f=
84034b31291c6ce9fe and produces a valid sighashes - sighash(SIGHASH\_SINGLE=
)=3D0x012a4533d9bbc900bf5757dcc6b2f3aa8925a2fbc42708afe22b0921124f62a2 whic=
h is contained in the interval **C2** &amp; sighash(SIGHASH\_SINGLE \| ANYO=
NECANPAY)=3D0x841d8ccc1fa672da928aae66b5a1653a227abc1fedab8a55d1c0300cf4337=
a33 which is contained in the interval **C5**<br><br>###### SIGHASH\_ALL an=
d SIGHASH\_ALL \| ANYONECANPAY<br><br>We again need to grind these 2 togeth=
er, since we have no way to influence one without also changing the other. =
We do this by changing output 1&#39;s output script, here we can simply use=
 OP_RETURN.<br><br>```<br>OP_RETURN &lt;nonce&gt;<br>```<br><br>Now we can =
start incrementing the nonce in the OP_RETURN output.<br><br>Using nonce=3D=
68976 we get valid sighashes - sighash(SIGHASH\_ALL)=3D0x022a721e26c9115172=
fc219abde406bab532df328fc83c16e8820a82f9bada6a which is contained in the in=
terval **C3** &amp; sighash(SIGHASH\_ALL \| ANYONECANPAY)=3D0x803fcf5814aa3=
6a5d6488fdf26d949b5871f29764b20842170cbbccce4eb15e4 which is contained in *=
*C1**<br><br>##### Transactions<br><br>We now have a valid set of transacti=
ons<br><br>###### Intermediate transaction<br><br>locktime=3D500000000<br><=
br>| Inputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | Outputs =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br>|-----------------=
-------------------------------------------------------------------|-------=
---------------------------------------------------------------------------=
------|<br>| 63e0fcd8c7a828dc979da397fa82fdd7d8e49b9d5a693273fbd98813f25429=
9c:1, nSequence: 200 | P2WPKH(034d1f488236a356bbc6ddcdaaaed2472af502b0206fd=
3b036c82f656aa30c7bb7): 18190 sats |<br><br>txId =3D [23990f08e0e7cb6e22ea1=
837241d5884c84d2398a82f5469e63d022ce215e84f](<a href=3D"https://mempool.spa=
ce/testnet4/tx/23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d022ce215=
e84f">https://mempool.space/testnet4/tx/23990f08e0e7cb6e22ea1837241d5884c84=
d2398a82f5469e63d022ce215e84f</a>)<br><br>###### Claim transaction<br><br>l=
ocktime=3D500000000<br><br>| Inputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 |=
 Outputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 |<br>|------------------------------=
----------------------------------------------------|----------------------=
---------------------------------------------------------------------------=
--------------------------|<br>| 2c6747829c435da3be23ba350c7d5eab5b9fb8717d=
e2613973191305779e3075:0, nSequence=3D11 | P2WSH(afa6 OP_DROP 02b0db6b93ed9=
284dc957718faf3f1464cf2a47f35c12ddc1783cbebed3952d3db OP_CHECKSIGVERIFY OP_=
1): 18690 sats |<br>| 23990f08e0e7cb6e22ea1837241d5884c84d2398a82f5469e63d0=
22ce215e84f:0, nSequence=3D0 =C2=A0| OP_RETURN 010d70: 0 sats =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br><br>txId=3D[4017bedd84d88658291797d8=
cd9751fa20fa1216b1cf34cf808331c4522c66b3](<a href=3D"https://mempool.space/=
testnet4/tx/4017bedd84d88658291797d8cd9751fa20fa1216b1cf34cf808331c4522c66b=
3">https://mempool.space/testnet4/tx/4017bedd84d88658291797d8cd9751fa20fa12=
16b1cf34cf808331c4522c66b3</a>)<br><br>We produce valid signatures by using=
 the corresponding intervals &amp; their private keys:<br><br>1. Interval C=
1 was hit by SIGHASH\_ALL \| ANYONECANPAY, therefore we take private keys *=
*d1a** &amp; **d1b**, and sign the transaction with SIGHASH\_ALL \| ANYONEC=
ANPAY by them.<br>2. Interval C2 was hit by SIGHASH\_SINGLE, therefore we t=
ake private keys **d2a** &amp; **d2b**, and sign the transaction with SIGHA=
SH\_SINGLE by them.<br>3. Interval C3 was hit by SIGHASH\_ALL, therefore we=
 take private keys **d3a** &amp; **d3b**, and sign the transaction with SIG=
HASH\_ALL by them.<br>4. Interval C4 was hit by SIGHASH\_NONE \| ANYONECANP=
AY, therefore we take private keys **d4a** &amp; **d4b**, and sign the tran=
saction with SIGHASH\_NONE \| ANYONECANPAY by them.<br>5. Interval C5 was h=
it by SIGHASH\_SINGLE \| ANYONECANPAY, therefore we take private keys **d5a=
** &amp; **d5b**, and sign the transaction with SIGHASH\_SINGLE \| ANYONECA=
NPAY by them.<br>6. Interval C6 was hit by SIGHASH\_NONE, therefore we take=
 private keys **d6a** &amp; **d6b**, and sign the transaction with SIGHASH\=
_NONE by them.<br><br>###### Spend transaction<br><br>Locktime or nSequence=
s are not important here <br><br>| Inputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | Outputs =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|<br>|-------=
-------------------------------------------------------------|-------------=
-------------------------------------------|<br>| 4017bedd84d88658291797d8c=
d9751fa20fa1216b1cf34cf808331c4522c66b3:0 | tb1qcjrfydsykze2htqcp6thau3v7nk=
5hndrsywwv6: 18550 sats |<br><br>txId=3D[921ba28a5f30060e8771efb9b47e83fd3d=
36d9f69948af2d225760a269675fca](<a href=3D"https://mempool.space/testnet4/t=
x/921ba28a5f30060e8771efb9b47e83fd3d36d9f69948af2d225760a269675fca">https:/=
/mempool.space/testnet4/tx/921ba28a5f30060e8771efb9b47e83fd3d36d9f69948af2d=
225760a269675fca</a>)<br><br>### Edge cases<br><br>#### Not enough variety =
for SIGHASH_NONE \| ANYONECANPAY<br><br>It might happen that in case the di=
fficulty is high enough, the grinding for SIGHASH_NONE \| ANYONECANPAY coul=
dn&#39;t find any valid solution by grinding the transaction locktime (arou=
nd 1200000000 possibilities) &amp; input 0&#39;s nSequence (around 2^31 pos=
sibilities with the most significant enable bit being 0 to ensure no consen=
sus 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 bi=
tcoin&#39;s current block difficulty the chance of it happening is just \~1=
:10^8.<br><br>### Improvements<br><br>Miners can cache intermediary states =
of sha256 hash function when grinding just parts of the transaction to spee=
d up the process, they can also cache sha256 hashes of outputs &amp; inputs=
, respectively when changing the other.<br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CAOY%3Dfzk-ksDGT_oyCKF%3DEJnnXaXoCbfCzxW%2B9PBQV%3Dus-K%3DPuQ%40=
mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.googl=
e.com/d/msgid/bitcoindev/CAOY%3Dfzk-ksDGT_oyCKF%3DEJnnXaXoCbfCzxW%2B9PBQV%3=
Dus-K%3DPuQ%40mail.gmail.com</a>.<br />

--000000000000bec95b06261805c0--