From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 (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 ; 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 Date: Sun, 28 Apr 2024 20:30:30 -0400 Message-ID: Subject: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed) To: Bitcoin Development Mailing List 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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
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 sign= s the spending transaction.

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.

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

Our approach differs= from the Jeremy Rubin's approach in [7] as we do not require OP_CAT an= d 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 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).

## Signing a Bitcoin Transacti= on 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 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.

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't matter for our purpo= ses.

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) com= putations assuming no mathematical shortcut such as the one used to find k= =3D1/2.


To explain how to use the above observative to sign Bitc= oin transactions with Lamport signatures, let'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.

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's look at an example:<= br>
Alice computes her Lamport public keys and signing keys
x00 =3D H= ash(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 re= deem script looks like:
```
PUSH ecdsaPubkey0
OP_CHECKSIG (ecdsaSi= g0)
// Verify lamport signature on ecdsaSig0
PUSH x00, x01
if OP_S= IZE (ecdsaSig0) =3D=3D 59:
=C2=A0 if OP_HASH(y00) !=3D x00: OP_RETURNelse if OP_SIZE (ecdsaSig0) < 59:
=C2=A0 if OP_HASH(y01) !=3D x01: O= P_RETURN

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

= // Verify lamport signature on ecdsaSig2
PUSH ecdsaPubkey2
OP_CHECKSI= G (ecdsaSig2)
// Verify lamport signature on ecdsaSig1
PUSH x20, x21<= br>if OP_SIZE (ecdsaSig2) =3D=3D 59:
=C2=A0 if OP_HASH(y20) !=3D x10: OP= _RETURN
else if OP_SIZE (ecdsaSig2) < 59:
=C2=A0 if OP_HASH(y21) != =3D x21: OP_RETURN
```

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.

The spend script pseudocode:
```
PUSH ecdsa= Sig0
PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
PUSH ecds= aSig1
PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59PUSH ecdsaSig2
PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59<= 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.

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's signature on the attacker's very first try!

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

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 s= ignatures 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 leng= th signatures, but generate them in the same position as Alice generated th= em. The probability an attacker will generate exactly m <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

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.

## Known weaknesses

1. *The= Tuning Attack:* The attacker can use different SIG_HASH flags per signatur= e to attack each signature individually. For instance ecdsaSig1 doesn'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.

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.

## Known= Improvements

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.

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_SIZ= E(ecdsaSig2)=3D=3D59) ...

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.

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.


## Open Questions

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.
=
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?

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.

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?

5. Is there any use for thi= s beyond a fun party trick?

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

[0]: &= quot;Bitcoin Wallet Recovery via ECDSA Short Signatures" htt= ps://github.com/demining/Bitcoin-Wallet-Recovery?tab=3Dreadme-ov-file=C2=A0
[1]: "Constructing Digital Signatures from a One Way Funct= ion", Leslie Lamport (1979), h= ttps://www.microsoft.com/en-us/research/publication/constructing-digital-si= gnatures-one-way-function/

[2]: "A Certified Digital Signat= ure", Ralph C. Merkle (1979), https://www.ralphmerkle.com/papers/Certified1979.p= df

[3]: "Timelocked Proof of Work via signature length"= ;, =C2=A0Robin Linus (2021), https://gist.github.com/R= obinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md

[4]: = "Proof of Work in Bitcoin Script", Robin Linus (2020), htt= ps://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md
<= br>[5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022), https://github.com/VzxPLnHqr/si= g-pow/

[6]: "[Lightning-dev] Better privacy with SNARKs&quo= t;, Anthony Towns (2015), https://lists.linuxfoundatio= n.org/pipermail/lightning-dev/2015-November/000344.html

[7]: &qu= ot;Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021), https://rubin.io/blo= g/2021/07/06/quantum-bitcoin/

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

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://gro= ups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2= BqR8-uDot25tM%3DXA%40mail.gmail.com.
--0000000000007afa040617315e51--