path: root/b7/511d27ee5a8e00005dd4a71830839d97004ecf

Delivery-date: Sun, 28 Apr 2024 17:50:21 -0700
Received: from mail-qv1-f55.google.com ([209.85.219.55])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBRG5XOYQMGQEYUQ7NZY@googlegroups.com>)
	id 1s1FDn-00028E-Ui
	for bitcoindev@gnusha.org; Sun, 28 Apr 2024 17:50:21 -0700
Received: by mail-qv1-f55.google.com with SMTP id 6a1803df08f44-69649f1894dsf67420436d6.0
        for <bitcoindev@gnusha.org>; Sun, 28 Apr 2024 17:50:19 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1714351813; cv=pass;
        d=google.com; s=arc-20160816;
        b=c26uH3QryuI3nGH4W3jiFmujI+4ZghceGXgcZtxf6AD7DWStH7WraGYq3ff5wX9w+a
         OKj1VURrnBHmlM068fmtu/nOT1VxdpFNjzIvqA3yYDC/aLb35y2GDI5QoNwUdGh9ZqWK
         D6rBBM8Ba0oCeHSF83pTaThh2eIGknAUTXLk21niNm6gRva7HXP9S0ci0miOCiiB6W74
         knCAb12fkB9bQi0dAiKklhM3I4nT9NZjGFyE74n18o8m8lGFoN0dsCykBb+AGPCCWiJS
         mq6+4Ra9eeJ7xtC9C+9NMNpuU8jUrftFBLVHCnpNzShHd6lXKokGpCz7JhJPZo0PPtAV
         DqQQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
        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=y0ytnzK9RmyDNt8DGXkTVdtnCb8MoHqwMFfHngQDonE=;
        fh=AAcOlSQoEJRUaM16bydWUu6biwq83WFBqLMDRwFf+zA=;
        b=a4KJvoco91P3nVLPIzXewpqSP40PODM2ZvzVm14l62pIRbYC8WbWf/mumn2FHq7k9Z
         SvG2x0647qSOT0ucLS2XLmiPehuYT98kpHprIiuceBPcbHqseYqFvmlyl6YlSzl/7itd
         BAZXGttXFC48RIfWieF+zUY4JCpgw9LVOCEjKz5UW+p9Cs7mvAuzFftXsWQ+2R3FGAro
         k9il6CPiNEuFCpjEHFV/dydW/KEOg/w6aa4MpTfMRlTvwPSK+Jn2hbxYgv+meOAG1cfg
         VuL7QlFtp3P/rJpnSAm9bI4YoVe6HfKBfnJyT8ElMdioeAdCAe/sq48V43UhIvQWB3bQ
         bNNg==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=gXoMlnlx;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12f as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1714351813; x=1714956613; 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=y0ytnzK9RmyDNt8DGXkTVdtnCb8MoHqwMFfHngQDonE=;
        b=P3+NYME91j/mVuBVrV6hLosKpIGBZExDrGh+HcxDqmpUoa5B4UkJXg/GvMgZx9oOa5
         wEELV9n4o2laY6sFNyPrzrZKIsM5Bz3Kj99t0Jar7Wsp2eIrNd2rhblAgGiaPBSkgcSi
         fs5jki/jFx0jd1auJorM+N1vczp2hUyGrlsXaOHbEzyOR29M7MPkRbdElGi3qr/eOWU6
         tl6pNnRB4qdgNMsrvK9W4Pj3XzAvbVyTNKBdTtj4FZEjMBHN5g8HSzGdQ4yNcleZvLg3
         FFHzrif+T2j7cfIFCntDn6bonxUff2ZHLPPS92O9D8Vfc3lq9lLOxlCGQPdySIp5ZaXZ
         N4UQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1714351813; x=1714956613; 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=y0ytnzK9RmyDNt8DGXkTVdtnCb8MoHqwMFfHngQDonE=;
        b=Q8fNVwu7gCOlVrZuJk7ZI4FN5qmaCKsm6WRV0yIzf3rPaPor/XRS8BEkZEAsvocFQB
         D+aKKFMC1Z62hnMU+aU+mk2/jzksXARD1BndBPcTUSKh6jEYIRZ1pw1xA9QijH0OgPpK
         aOZv/+XRi7VgqCjUiI1OgQHXM2K6mBrts42bi9jP4K5JBn0Nw4iEkgitDkzlcX6jBrxB
         04RTYFyI8HYLBaSz1kAAzaAWJF3AjvAMC02VWSh54KkJrpHFxHI8eoMfUcTfBXQlPifa
         P/8mXKQ2XA0llOnCjS64v33ZwKr8SlHQC38/oh66dCyQGrwsrTy0HXOfomI5fLb9ISgx
         q1xQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1714351813; x=1714956613;
        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=y0ytnzK9RmyDNt8DGXkTVdtnCb8MoHqwMFfHngQDonE=;
        b=pv9Wfz7zMVIXs+YnQfwyJ/eurWXfV2BDNYsZwKjy3wM84oVlsiQzYNU9xYSPMr2izU
         WNw7WwrUb4bUXilvMzq2X3RzhKjDEAwHUe6MXwCSrcjyczzBONssJ1WnLqrlEw85Q61h
         h0k4x8kTrOrjlEc0BrnIMQgP/IegmqrDLlhX4cS/tsWnlxWwa52fGS1baa70PmjEGYRO
         s2kcmzaiyg5ETMMvXSjOkv0mmnlGBXVPjRTlw+zCNwxcvPMbTJi0fdEKC+r1X7suC0dZ
         y7Cv5jg8HRrhBK+hgVikcd3cfodUN1SnQKJTvM41+52lYJGd6+XalsL+muD6zsCAx2nu
         aQuA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCX/XOBCyVs3T7Y8NSEkV4bg6QDaa4QYKKeGACyRj5XctL4ja1FDOsgwW1y6Y3bNN4OmXadcKxnJgEvwe0nMO8bKRjmD/tE=
X-Gm-Message-State: AOJu0YzJGLSSEUDQhrfQRyLgSeX5IVCeXG3o8rahmb0KrkAFVvg+YYQb
	8Jwz8UG5jpNS59mDAzYWx1jxwCc2QtvW3ulO/5XUd65v2h7J13Vs
X-Google-Smtp-Source: AGHT+IFqX3OyUggOofK1rCpkLiEDU6sjAxUwLtd2Jypnrz5NB/y5oR4NNh3xW17KAYoCIMsAKmxwiw==
X-Received: by 2002:a05:6214:27e5:b0:6a0:4255:b727 with SMTP id jt5-20020a05621427e500b006a04255b727mr11476439qvb.9.1714351813357;
        Sun, 28 Apr 2024 17:50:13 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:ad4:4ee1:0:b0:698:ed81:bc0e with SMTP id 6a1803df08f44-6a09c61c341ls35079136d6.1.-pod-prod-06-us;
 Sun, 28 Apr 2024 17:50:12 -0700 (PDT)
X-Received: by 2002:a05:6214:508c:b0:6a0:32b:dfa6 with SMTP id kk12-20020a056214508c00b006a0032bdfa6mr497958qvb.7.1714351812047;
        Sun, 28 Apr 2024 17:50:12 -0700 (PDT)
Received: by 2002:a05:620a:258f:b0:790:f573:2ec2 with SMTP id af79cd13be357-790f5733397ms85a;
        Sun, 28 Apr 2024 17:31:09 -0700 (PDT)
X-Received: by 2002:a2e:a608:0:b0:2e0:14bd:18f2 with SMTP id v8-20020a2ea608000000b002e014bd18f2mr1995341ljp.47.1714350667383;
        Sun, 28 Apr 2024 17:31:07 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1714350667; cv=none;
        d=google.com; s=arc-20160816;
        b=t1XKIoDnJICWHMmDXwBRRyfkLFp6Bg86zncgE0B6NvZzvEWd3Gm/vEOoCh7iyaQ07T
         8zhFVoryFd0tccPlgm0tmH8zIitdn3dhmEgPFFGHU8ko+2K/P3bh8JTGVsoXVpcMGaQH
         +1ExDvlYqWWoI9h38vRABwelYLZhe9ISCAxmxTufroPIuNibZ7DK+SC24Id5X6KDp7Kp
         NnZzxjCWU2LbAAbK6wyr3WvaO+WwF2nOh4DSWc+0t8iLJbK1BndjELqIRsiQqihbiWcd
         0GcoNL0JYzdSkITAWumh84uZm15ZTG6T1Tjia+XhEze0DWDWmNZJbarplXqMkDRII+L+
         BKGQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
        h=to:subject:message-id:date:from:mime-version:dkim-signature;
        bh=nWA1p9AqfRw002MRwk+I6X8HXPxgDNKl89tsmXcRxV4=;
        fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
        b=baLgonAQqYW1gR2LEZo8+LflYp/fFhP2Aa6+tLQTTWSuByB9+Pk9vk57HRunpb8Piv
         vb9hGM6k+0CkTAFw1oVrEUnYNp1Yy2x3L+5Nbx3zUrmA6G/gJyp3HppEFaXTSAJ3ayrl
         oTJpwynunVsaXtQzPkiuGVn+T7oIlpya1AxzxRvsx8YDSSUQbIti7umJ5labKU6gEm5e
         HtHNr1mkyoEzjmCnY1rinAAzvRUSwlEG6I0Z9CmcVaUBzURMQrV+HxwKfoTpAFhJPSAW
         DXWNZ0MBCY6eg7l0Owrk/yy0jNEVX2+dt7IJvgN26KekB4p9ORpA++M0oq5pkDVd7Z3c
         J3uQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=gXoMlnlx;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12f as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com
Received: from mail-lf1-x12f.google.com (mail-lf1-x12f.google.com. [2a00:1450:4864:20::12f])
        by gmr-mx.google.com with ESMTPS id l9-20020a2ea309000000b002df3ca1fcedsi226466lje.8.2024.04.28.17.31.07
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Sun, 28 Apr 2024 17:31:07 -0700 (PDT)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12f as permitted sender) client-ip=2a00:1450:4864:20::12f;
Received: by mail-lf1-x12f.google.com with SMTP id 2adb3069b0e04-516d2b9cd69so4668850e87.2
        for <bitcoindev@googlegroups.com>; Sun, 28 Apr 2024 17:31:07 -0700 (PDT)
X-Received: by 2002:ac2:5b47:0:b0:51b:e46c:19fd with SMTP id
 i7-20020ac25b47000000b0051be46c19fdmr5699866lfp.18.1714350666214; Sun, 28 Apr
 2024 17:31:06 -0700 (PDT)
MIME-Version: 1.0
From: Ethan Heilman <eth3rs@gmail.com>
Date: Sun, 28 Apr 2024 20:30:30 -0400
Message-ID: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
Subject: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures
 (no changes needed)
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="0000000000007afa040617315e51"
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=gXoMlnlx;       spf=pass
 (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12f as
 permitted sender) smtp.mailfrom=eth3rs@gmail.com;       dmarc=pass (p=NONE
 sp=QUARANTINE dis=NONE) header.from=gmail.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 (/)

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

One day having lunch at the MIT DCI and discussing OP_CAT and lamport
signatures we came up with a scheme to do lamport signatures on Bitcoin
transactions without OP_CAT.

This scheme has the following properties:
1. Should work with today's Bitcoin (no OP_CAT required).
2. Unlike other lamport signatures in Bitcoin script, this scheme signs the
spending transaction.

Disclaimer: This is very preliminary work and the security of these
signatures rests on a number of simplifying assumptions about ECDSA
signatures that may not be true. Do not use this signature scheme in a
Bitcoin output unless your intent is for that output to be a fun crypto
bounty. I have not tested this in Bitcoin script.

This idea of using signature length shares a lot in common with sigPOW
(signature POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr
[5] which uses signature length grinding as a transaction level POW
mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA
signature length constraints to force revealing signing key [6].

Our approach differs from the Jeremy Rubin's approach in [7] as we do not
require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin's
approach in [8] as our goal is to verify a Lamport signature on the
spending transaction rather than a Lamport signature on arbitrary data.
When compared with [7,8] our scheme is far less practical as it requires
very large numbers of signatures (below we discuss 1000 signatures).

## Signing a Bitcoin Transaction with Lamport Signatures

An ECDSA signature (r,s) is calculated as r =3D (k*G)_x, s=3D (z+r*dA)/k
- k is randomly chosen nonce
- dA is the signing key,
- z is derived from the hash of the signed message, i.e., transaction hash.

Our Lamport scheme is based on the following observation. ECDSA signatures
in bitcoin are variable in length and that the length of an s-value in an
ECDSA signature for a fixed nonce, k, and fixed signing key has its length
determined by the transaction hash. We can use OP_SIZE to get the size of a
signature and we can use Lamport signatures to sign this size. We explain
Lamport signatures below.

The security of our scheme rests on a way to fix the nonce k. Madars Virza
and Andrew Poelstra both pointed out to me when discussing this scheme that
setting k=3D1/2, that is setting k to the multiplicative inverse of 2,
results in a k with a very short r
(r=3D0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) [0=
].
This means that the first 11 bytes (88-bits of the r value are zero and
truncated) so the r-value is only 21 bytes long! A publicly known k leaks
the signing key, but that doesn't matter for our purposes.

Using this k, we can ensure that the r values on two signatures are the
same by inspecting their length using `OP_SIZE(sig) < (21+32+6)`. Grinding
r to find a smaller value requires 2^96 (12 bytes of zeros) computations
assuming no mathematical shortcut such as the one used to find k=3D1/2.


To explain how to use the above observative to sign Bitcoin transactions
with Lamport signatures, let's remind ourselves how Lamport signatures [1]
 work. To sign 1-bit with a Lamport signature you first use a hash function
H, to compute: x0 =3D H(y0), x1 =3D H(y1). Next, you publish x0,x1 as your
public key. Then, to sign the bit 0, you release the value y0. Anyone can
use y0 to verify that x0 =3D=3D H(y0). To sign the bit 1, you release y1.

We use Lamport signatures to sign the length of a bitcoin signature. The
length of the signature serves as a proxy for the transaction hash of the
spending transaction. Repeating this many times provides cryptographic
levels of security. Let's look at an example:

Alice computes her Lamport public keys and signing keys
x00 =3D Hash(y00)
x01 =3D Hash(y01)
x10 =3D Hash(y10)
x11 =3D Hash(y11)
x20 =3D Hash(y20)
x21 =3D Hash(y21)

In pseudocode Alice's redeem script looks like:
```
PUSH ecdsaPubkey0
OP_CHECKSIG (ecdsaSig0)
// Verify lamport signature on ecdsaSig0
PUSH x00, x01
if OP_SIZE (ecdsaSig0) =3D=3D 59:
  if OP_HASH(y00) !=3D x00: OP_RETURN
else if OP_SIZE (ecdsaSig0) < 59:
  if OP_HASH(y01) !=3D x01: OP_RETURN

PUSH ecdsaPubkey1
OP_CHECKSIG (ecdsaSig1)
// Verify lamport signature on ecdsaSig1
PUSH x10, x11
if OP_SIZE (ecdsaSig1) =3D=3D 59:
  if OP_HASH(y10) !=3D x10: OP_RETURN
else if OP_SIZE (ecdsaSig1) < 59:
  if OP_HASH(y11) !=3D x11: OP_RETURN

// Verify lamport signature on ecdsaSig2
PUSH ecdsaPubkey2
OP_CHECKSIG (ecdsaSig2)
// Verify lamport signature on ecdsaSig1
PUSH x20, x21
if OP_SIZE (ecdsaSig2) =3D=3D 59:
  if OP_HASH(y20) !=3D x10: OP_RETURN
else if OP_SIZE (ecdsaSig2) < 59:
  if OP_HASH(y21) !=3D x21: OP_RETURN
```

Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For
example let=E2=80=99s say OP_SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D58,
OP_SIZE(ecdsaSig2)=3D59. Thus, to spend she generates a Lamport signature
over those lengths by releasing the preimages: y00, y11, y20.

The spend script pseudocode:
```
PUSH ecdsaSig0
PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
PUSH ecdsaSig1
PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59
PUSH ecdsaSig2
PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59
```

The advantage Alice has over an attacker attempting to steal her funds is
that all Alice has to do is release the preimages for the lengths of all of
her ECDSA signatures, but an attacker has  to construct a transaction hash
that matches the size of her signatures for each different ECDSA signature.
The probability an attacker manages this for three random ECDSA signatures
given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~=3D 0.3%.
Alice can arbitrarily amplify her security by adding additional ECDSA
signatures.

It was pointed out to me by Andrew Poelstra that the probability that a
random signature is shorter by one byte is 1/256 because OP_SIZE only
measures the byte length of a value, not the bit length. This means most of
the time if Alice just used three ECDSA signatures, they would all be
length 59. In such a case the attacker would have (255/256)^3 =3D 98%
probability of generating a transaction that can be spent using Alice's
signature on the attacker's very first try!

For this reason Alice really needs a lot of ECDSA signatures and probably
also needs to grind for safer values to sign (safer =3D high diversity in
length).

Assuming a simplistic model of ECDSA signatures length Prob(1-1/256) for
length 59 and Prob(1/256) for length <59, the probability that Alice will
generate exactly m <59-length signatures and n-m 59 length signatures is:
`(255/256)^(n-m)*(1/256)^m*(n choose m)`.

An attacker would need to not only generate m <59-length signatures and n-m
59 length signatures, but generate them in the same position as Alice
generated them. The probability an attacker will generate exactly m
<59-length signatures and n-m 59 length signatures in the same position as
Alice is: (255/256)^(n-m)*(1/256)^m

On average Alice would need 1000 attempts to sign with n=3D800,m=3D10. Wher=
eas
an attacker would need to make 2^84 attempts to brute force the output
after seeing alice attempt to spend that output using a n=3D800,m=3D10
signature.

## Known weaknesses

1. *The Tuning Attack:* The attacker can use different SIG_HASH flags per
signature to attack each signature individually. For instance ecdsaSig1
doesn't have the right length, the attacker can try SIGHASH_NONE to try
again without changing any of the other signature lengths. This provides
the attacker some advantage but with sufficient numbers of signatures it
does not break the scheme. Alice can also use this approach to increase the
security of her signatures by increasing length diversity. Unclear if this
helps or hurts security more.

2. *Mix and Match Attack:* Even if an attacker can not grind a shorter
r-value, an r-value of roughly 21-23 bytes would allow an attacker to make
a few more individual attempts on a particular signature length. This is
because we only measure the total length of the ECDSA signature, so a
23-byte r-value combined with a 29-byte s-value would be 23+29+6 =3D 58
bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but if
an attacker managed to grind a 23-byte r-value at a cost of 2^72
computations, it would provide the attacker some advantage.

## Known Improvements

1. Rather than only signing if the length is 59 or less. We could extend
the scheme to sign multiple ECDSA signature length values, 59, 58, 57,
56... This could enable Alice to greatly increase her security as say 56
would only occur 1 out of every 2^32 signatures. Winternitz One Time
signatures (WOTs) [2] could be used here to compress signature length.

1. Jeremy Rubun suggested the following optimization: rather than directly
signing the ECDSA signatures lengths, you construct a 32-bit bit vector of
the signature lengths using OP_MUL, OP_ADD.

bit vector =3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D59) =
+
4*(OP_SIZE(ecdsaSig2)=3D=3D59) ...

Then you compute a Winternitz One Time signature over this bit vector. This
would require also computing a WInternitz or Lamport signature over a
checksum of the bit vector. This would substantially reduce the number of
lamport public keys and signing keys and likely reduce the size of redeem
script and spend script by half.

3. Since 59 is the default length, Alice does not in fact need to sign 59.
It could be inferred that if no preimage is given or say the preimage 0 is
given, the length that Alice intends is 59. This would save space on the
spend script and redeem script.


## Open Questions

1. Could OP_CODESEPARATOR be used by Alice or the attacker to either
strengthen or weaken the security of this scheme. Alice using
OP_CODESEPARATOR to strengthen the security of this scheme by increasing
signature length diversity was suggested by Jeremy Rubin. After some
discussion, the fact that the redeem script is part of the P2SH address
means that the data in OP_CODESEPARATOR would still influence all the other
ECDSA signatures. That said, perhaps there is some way it can be exploited
to either help Alice or help the attacker.

2. If a nonce value k was discovered such that k*G =3D r =3D 1, we could re=
move
the assumption that no could find a smaller r. It is unknown how to find
r=3D1 as it requires finding the discrete log. It is possible to create
transaction signatures that have r=3D1 without knowing k, through the use o=
f
ECDSA pubkey recovery. This does not work for our scheme as we must commit
to the ECDSA  public key in the spent transaction. Are there any known
smaller r values than r=3D1/2*G?

3. How many bits of security does each ECDSA signature contribute in this
scheme given the SIGHASH mix and match attack above? How many ECDSA
signatures are needed? We have modeled ECDSA s-values signatures being
uniformly drawn from 2^256. It seems unlikely to me that the Elliptic Curve
math lines up perfectly with a 256 bit space especially for a fixed r-value
that has special mathematical properties. Non-uniformity here could end up
helping (increasing length diversity) or hurting (a pattern an attacker
could exploit to match the length faster than brute force) the security.

4. An attacker could trade off brute forcing the transaction hash lengths
by computing a small r-value. What does the time-memory trade look like
here?

5. Is there any use for this beyond a fun party trick?

Thanks to Madars Virza, Dan Gould, Armin Sabouri, Neha Narula, Jeremy
Rubin, Andrew Poelstra, Robin Linus for discussing this with me and giving
me feedback. This initial discuss was fueled by the MIT DCI espresso
machine. I've attempted to credit all ideas contributed to the contributor,
if I got this wrong or missed a contribution shoot me an email. Any
mistakes are my own as I wrote this up.

[0]: "Bitcoin Wallet Recovery via ECDSA Short Signatures"
https://github.com/demining/Bitcoin-Wallet-Recovery?tab=3Dreadme-ov-file

[1]: "Constructing Digital Signatures from a One Way Function", Leslie
Lamport (1979),
https://www.microsoft.com/en-us/research/publication/constructing-digital-s=
ignatures-one-way-function/

[2]: "A Certified Digital Signature", Ralph C. Merkle (1979),
https://www.ralphmerkle.com/papers/Certified1979.pdf

[3]: "Timelocked Proof of Work via signature length",  Robin Linus (2021),
https://gist.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-si=
g_pow-md

[4]: "Proof of Work in Bitcoin Script", Robin Linus (2020),
https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md

[5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022),
https://github.com/VzxPLnHqr/sig-pow/

[6]: "[Lightning-dev] Better privacy with SNARKs", Anthony Towns (2015),
https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000=
344.html

[7]: "Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/06/quantum-bitcoin/

[8]: "CheckSigFromStack for 5 Byte Values", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/02/signing-5-bytes/

--=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 on the web visit https://groups.google.com/d/msgid/=
bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40ma=
il.gmail.com.

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

<div dir=3D"ltr">One day having lunch at the MIT DCI and discussing OP_CAT =
and lamport signatures we came up with a scheme to do lamport signatures on=
 Bitcoin transactions without OP_CAT.<br><br>This scheme has the following =
properties:<br>1. Should work with today&#39;s Bitcoin (no OP_CAT required)=
.<br>2. Unlike other lamport signatures in Bitcoin script, this scheme sign=
s the spending transaction.<br><br>Disclaimer: This is very preliminary wor=
k and the security of these signatures rests on a number of simplifying ass=
umptions about ECDSA signatures that may not be true. Do not use this signa=
ture scheme in a Bitcoin output unless your intent is for that output to be=
 a fun crypto bounty. I have not tested this in Bitcoin script.<br><br>This=
 idea of using signature length shares a lot in common with sigPOW (signatu=
re POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr [5] whic=
h uses signature length grinding as a transaction level POW mechanism and e=
arlier work by Anthony Towns and Greg Maxwell using ECDSA signature length =
constraints to force revealing signing key [6].<br><br>Our approach differs=
 from the Jeremy Rubin&#39;s approach in [7] as we do not require OP_CAT an=
d we use P2SH not tapscript and from Jeremy Rubin&#39;s approach in [8] as =
our goal is to verify a Lamport signature on the spending transaction rathe=
r than a Lamport signature on arbitrary data. When compared with [7,8] our =
scheme is far less practical as it requires very large numbers of signature=
s (below we discuss 1000 signatures).<br><br>## Signing a Bitcoin Transacti=
on with Lamport Signatures<br><br>An ECDSA signature (r,s) is calculated as=
 r =3D (k*G)_x, s=3D (z+r*dA)/k<br>- k is randomly chosen nonce<br>- dA is =
the signing key, <br>- z is derived from the hash of the signed message, i.=
e., transaction hash.<br><br>Our Lamport scheme is based on the following o=
bservation. ECDSA signatures in bitcoin are variable in length and that the=
 length of an s-value in an ECDSA signature for a fixed nonce, k, and fixed=
 signing key has its length determined by the transaction hash. We can use =
OP_SIZE to get the size of a signature and we can use Lamport signatures to=
 sign this size. We explain Lamport signatures below.<br><br>The security o=
f our scheme rests on a way to fix the nonce k. Madars Virza and Andrew Poe=
lstra both pointed out to me when discussing this scheme that setting k=3D1=
/2, that is setting k to the multiplicative inverse of 2, results in a k wi=
th a very short r (r=3D0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad=
0d96d6795f9c63) [0]. This means that the first 11 bytes (88-bits of the r v=
alue are zero and truncated) so the r-value is only 21 bytes long! A public=
ly known k leaks the signing key, but that doesn&#39;t matter for our purpo=
ses.<br><br>Using this k, we can ensure that the r values on two signatures=
 are the same by inspecting their length using `OP_SIZE(sig) &lt; (21+32+6)=
`. Grinding r to find a smaller value requires 2^96 (12 bytes of zeros) com=
putations assuming no mathematical shortcut such as the one used to find k=
=3D1/2.<br><br><br>To explain how to use the above observative to sign Bitc=
oin transactions with Lamport signatures, let&#39;s remind ourselves how La=
mport signatures [1] =C2=A0work. To sign 1-bit with a Lamport signature you=
 first use a hash function H, to compute: x0 =3D H(y0), x1 =3D H(y1). Next,=
 you publish x0,x1 as your public key. Then, to sign the bit 0, you release=
 the value y0. Anyone can use y0 to verify that x0 =3D=3D H(y0). To sign th=
e bit 1, you release y1.<br><br>We use Lamport signatures to sign the lengt=
h of a bitcoin signature. The length of the signature serves as a proxy for=
 the transaction hash of the spending transaction. Repeating this many time=
s provides cryptographic levels of security. Let&#39;s look at an example:<=
br><br>Alice computes her Lamport public keys and signing keys<br>x00 =3D H=
ash(y00) <br>x01 =3D Hash(y01)<br>x10 =3D Hash(y10)<br>x11 =3D Hash(y11)<br=
>x20 =3D Hash(y20)<br>x21 =3D Hash(y21)<br><br>In pseudocode Alice&#39;s re=
deem script looks like:<br>```<br>PUSH ecdsaPubkey0<br>OP_CHECKSIG (ecdsaSi=
g0)<br>// Verify lamport signature on ecdsaSig0<br>PUSH x00, x01<br>if OP_S=
IZE (ecdsaSig0) =3D=3D 59:<br>=C2=A0 if OP_HASH(y00) !=3D x00: OP_RETURN<br=
>else if OP_SIZE (ecdsaSig0) &lt; 59:<br>=C2=A0 if OP_HASH(y01) !=3D x01: O=
P_RETURN<br><br>PUSH ecdsaPubkey1<br>OP_CHECKSIG (ecdsaSig1)<br>// Verify l=
amport signature on ecdsaSig1<br>PUSH x10, x11<br>if OP_SIZE (ecdsaSig1) =
=3D=3D 59:<br>=C2=A0 if OP_HASH(y10) !=3D x10: OP_RETURN<br>else if OP_SIZE=
 (ecdsaSig1) &lt; 59:<br>=C2=A0 if OP_HASH(y11) !=3D x11: OP_RETURN<br><br>=
// Verify lamport signature on ecdsaSig2<br>PUSH ecdsaPubkey2<br>OP_CHECKSI=
G (ecdsaSig2)<br>// Verify lamport signature on ecdsaSig1<br>PUSH x20, x21<=
br>if OP_SIZE (ecdsaSig2) =3D=3D 59:<br>=C2=A0 if OP_HASH(y20) !=3D x10: OP=
_RETURN<br>else if OP_SIZE (ecdsaSig2) &lt; 59:<br>=C2=A0 if OP_HASH(y21) !=
=3D x21: OP_RETURN<br>```<br><br>Alice computes the ECDSA signatures: ecdsa=
Sig0, ecdsaSig1, ecdsaSig2. For example let=E2=80=99s say OP_SIZE(ecdsaSig0=
)=3D59, OP_SIZE(ecdsaSig1)=3D58, OP_SIZE(ecdsaSig2)=3D59. Thus, to spend sh=
e generates a Lamport signature over those lengths by releasing the preimag=
es: y00, y11, y20.<br><br>The spend script pseudocode:<br>```<br>PUSH ecdsa=
Sig0<br>PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59<br>PUSH ecds=
aSig1<br>PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59<b=
r>PUSH ecdsaSig2<br>PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59<=
br>```<br><br>The advantage Alice has over an attacker attempting to steal =
her funds is that all Alice has to do is release the preimages for the leng=
ths of all of her ECDSA signatures, but an attacker has =C2=A0to construct =
a transaction hash that matches the size of her signatures for each differe=
nt ECDSA signature. The probability an attacker manages this for three rand=
om ECDSA signatures given the lengths above (59,58,59) is 255/256 * 1/256 *=
 255/256 ~=3D 0.3%. Alice can arbitrarily amplify her security by adding ad=
ditional ECDSA signatures.<br><br>It was pointed out to me by Andrew Poelst=
ra that the probability that a random signature is shorter by one byte is 1=
/256 because OP_SIZE only measures the byte length of a value, not the bit =
length. This means most of the time if Alice just used three ECDSA signatur=
es, they would all be length 59. In such a case the attacker would have (25=
5/256)^3 =3D 98% probability of generating a transaction that can be spent =
using Alice&#39;s signature on the attacker&#39;s very first try!<br><br>Fo=
r this reason Alice really needs a lot of ECDSA signatures and probably als=
o needs to grind for safer values to sign (safer =3D high diversity in leng=
th).<br><br>Assuming a simplistic model of ECDSA signatures length Prob(1-1=
/256) for length 59 and Prob(1/256) for length &lt;59, the probability that=
 Alice will generate exactly m &lt;59-length signatures and n-m 59 length s=
ignatures is: `(255/256)^(n-m)*(1/256)^m*(n choose m)`. <br><br>An attacker=
 would need to not only generate m &lt;59-length signatures and n-m 59 leng=
th signatures, but generate them in the same position as Alice generated th=
em. The probability an attacker will generate exactly m &lt;59-length signa=
tures and n-m 59 length signatures in the same position as Alice is: (255/2=
56)^(n-m)*(1/256)^m<br><br>On average Alice would need 1000 attempts to sig=
n with n=3D800,m=3D10. Whereas an attacker would need to make 2^84 attempts=
 to brute force the output after seeing alice attempt to spend that output =
using a n=3D800,m=3D10 signature.<br><br>## Known weaknesses<br><br>1. *The=
 Tuning Attack:* The attacker can use different SIG_HASH flags per signatur=
e to attack each signature individually. For instance ecdsaSig1 doesn&#39;t=
 have the right length, the attacker can try SIGHASH_NONE to try again with=
out changing any of the other signature lengths. This provides the attacker=
 some advantage but with sufficient numbers of signatures it does not break=
 the scheme. Alice can also use this approach to increase the security of h=
er signatures by increasing length diversity. Unclear if this helps or hurt=
s security more.<br><br>2. *Mix and Match Attack:* Even if an attacker can =
not grind a shorter r-value, an r-value of roughly 21-23 bytes would allow =
an attacker to make a few more individual attempts on a particular signatur=
e length. This is because we only measure the total length of the ECDSA sig=
nature, so a 23-byte r-value combined with a 29-byte s-value would be 23+29=
+6 =3D 58 bytes. 29-byte s-value are rare and occur with ~1/2^24 probabilit=
y, but if an attacker managed to grind a 23-byte r-value at a cost of 2^72 =
computations, it would provide the attacker some advantage.<br><br>## Known=
 Improvements<br><br>1. Rather than only signing if the length is 59 or les=
s. We could extend the scheme to sign multiple ECDSA signature length value=
s, 59, 58, 57, 56... This could enable Alice to greatly increase her securi=
ty as say 56 would only occur 1 out of every 2^32 signatures. Winternitz On=
e Time signatures (WOTs) [2] could be used here to compress signature lengt=
h.<br><br>1. Jeremy Rubun suggested the following optimization: rather than=
 directly signing the ECDSA signatures lengths, you construct a 32-bit bit =
vector of the signature lengths using OP_MUL, OP_ADD. <br><br>bit vector =
=3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D59) + 4*(OP_SIZ=
E(ecdsaSig2)=3D=3D59) ...<br><br>Then you compute a Winternitz One Time sig=
nature over this bit vector. This would require also computing a WInternitz=
 or Lamport signature over a checksum of the bit vector. This would substan=
tially reduce the number of lamport public keys and signing keys and likely=
 reduce the size of redeem script and spend script by half.<br><br>3. Since=
 59 is the default length, Alice does not in fact need to sign 59. It could=
 be inferred that if no preimage is given or say the preimage 0 is given, t=
he length that Alice intends is 59. This would save space on the spend scri=
pt and redeem script.<br><br><br>## Open Questions<br><br>1. Could OP_CODES=
EPARATOR be used by Alice or the attacker to either strengthen or weaken th=
e security of this scheme. Alice using OP_CODESEPARATOR to strengthen the s=
ecurity of this scheme by increasing signature length diversity was suggest=
ed by Jeremy Rubin. After some discussion, the fact that the redeem script =
is part of the P2SH address means that the data in OP_CODESEPARATOR would s=
till influence all the other ECDSA signatures. That said, perhaps there is =
some way it can be exploited to either help Alice or help the attacker.<br>=
<br>2. If a nonce value k was discovered such that k*G =3D r =3D 1, we coul=
d remove the assumption that no could find a smaller r. It is unknown how t=
o find r=3D1 as it requires finding the discrete log. It is possible to cre=
ate transaction signatures that have r=3D1 without knowing k, through the u=
se of ECDSA pubkey recovery. This does not work for our scheme as we must c=
ommit to the ECDSA =C2=A0public key in the spent transaction. Are there any=
 known smaller r values than r=3D1/2*G?<br><br>3. How many bits of security=
 does each ECDSA signature contribute in this scheme given the SIGHASH mix =
and match attack above? How many ECDSA signatures are needed? We have model=
ed ECDSA s-values signatures being uniformly drawn from 2^256. It seems unl=
ikely to me that the Elliptic Curve math lines up perfectly with a 256 bit =
space especially for a fixed r-value that has special mathematical properti=
es. Non-uniformity here could end up helping (increasing length diversity) =
or hurting (a pattern an attacker could exploit to match the length faster =
than brute force) the security.<br><br>4. An attacker could trade off brute=
 forcing the transaction hash lengths by computing a small r-value. What do=
es the time-memory trade look like here?<br><br>5. Is there any use for thi=
s beyond a fun party trick?<br><br>Thanks to Madars Virza, Dan Gould, Armin=
 Sabouri, Neha Narula, Jeremy Rubin, Andrew Poelstra, Robin Linus for discu=
ssing this with me and giving me feedback. This initial discuss was fueled =
by the MIT DCI espresso machine. I&#39;ve attempted to credit all ideas con=
tributed to the contributor, if I got this wrong or missed a contribution s=
hoot me an email. Any mistakes are my own as I wrote this up.<br><br>[0]: &=
quot;Bitcoin Wallet Recovery via ECDSA Short Signatures&quot; <a href=3D"ht=
tps://github.com/demining/Bitcoin-Wallet-Recovery?tab=3Dreadme-ov-file">htt=
ps://github.com/demining/Bitcoin-Wallet-Recovery?tab=3Dreadme-ov-file</a><b=
r>=C2=A0<br>[1]: &quot;Constructing Digital Signatures from a One Way Funct=
ion&quot;, Leslie Lamport (1979), <a href=3D"https://www.microsoft.com/en-u=
s/research/publication/constructing-digital-signatures-one-way-function/">h=
ttps://www.microsoft.com/en-us/research/publication/constructing-digital-si=
gnatures-one-way-function/</a><br><br>[2]: &quot;A Certified Digital Signat=
ure&quot;, Ralph C. Merkle (1979), <a href=3D"https://www.ralphmerkle.com/p=
apers/Certified1979.pdf">https://www.ralphmerkle.com/papers/Certified1979.p=
df</a><br><br>[3]: &quot;Timelocked Proof of Work via signature length&quot=
;, =C2=A0Robin Linus (2021), <a href=3D"https://gist.github.com/RobinLinus/=
95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md">https://gist.github.com/R=
obinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md</a><br><br>[4]: =
&quot;Proof of Work in Bitcoin Script&quot;, Robin Linus (2020), <a href=3D=
"https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md">htt=
ps://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md</a><br><=
br>[5]: &quot;sig-pow - work-locked outputs&quot;, VzxPLnHqr (2022), <a hre=
f=3D"https://github.com/VzxPLnHqr/sig-pow/">https://github.com/VzxPLnHqr/si=
g-pow/</a><br><br>[6]: &quot;[Lightning-dev] Better privacy with SNARKs&quo=
t;, Anthony Towns (2015), <a href=3D"https://lists.linuxfoundation.org/pipe=
rmail/lightning-dev/2015-November/000344.html">https://lists.linuxfoundatio=
n.org/pipermail/lightning-dev/2015-November/000344.html</a><br><br>[7]: &qu=
ot;Quantum Proofing Bitcoin with a CAT&quot;, Jeremy Rubin (2021), <a href=
=3D"https://rubin.io/blog/2021/07/06/quantum-bitcoin/">https://rubin.io/blo=
g/2021/07/06/quantum-bitcoin/</a><br><br>[8]: &quot;CheckSigFromStack for 5=
 Byte Values&quot;, Jeremy Rubin (2021), <a href=3D"https://rubin.io/blog/2=
021/07/02/signing-5-bytes/">https://rubin.io/blog/2021/07/02/signing-5-byte=
s/</a><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 on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25t=
M%3DXA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://gro=
ups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2=
BqR8-uDot25tM%3DXA%40mail.gmail.com</a>.<br />

--0000000000007afa040617315e51--