From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 30 Apr 2024 05:45:16 -0700 Received: from mail-ot1-f60.google.com ([209.85.210.60]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s1mrC-0005li-Uh for bitcoindev@gnusha.org; Tue, 30 Apr 2024 05:45:16 -0700 Received: by mail-ot1-f60.google.com with SMTP id 46e09a7af769-6ee1421ce19sf3442690a34.3 for ; Tue, 30 Apr 2024 05:45:14 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1714481108; cv=pass; d=google.com; s=arc-20160816; b=F+h6KGwaxmnypGq0MnhLJSTJwi72t2WRc4Abkwh9G3saCtXkqE2Q+J+lNW8rgqaOvR DBEgaT8M7aPeaLBOwGeJ8u/aZ2Psz7gvudwwfDWXw+xwBZTtlINs2lBlu61Vle+7Rk2/ TgTw1xCCq0pUhqqTGk7/7rCj5PtnfsFia9phif2zQ30VlLzEvvq9vCAfO0BWCQAcQ6pI Enes8E4km1oTHWR5BVq6C8bMvTGO6oEpUrCFDxtYeubMUdmHeqvXjujCPsvQ9lpbCl3T DLhXtHMnnHtLUxzKSPNMqAWbB7Owy6t4sXnRPehNaVoQ+UzcZ+HbRUm7W9WsehEwqYAa 8NOQ== 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=Ob6D7dENxMij/O8zTrhhDn8EPQAU/i8ZfbDhlaBop2w=; fh=cSVXYqUO8B5IOC2NJlMdhznziinjrBDp0LfegfUl0Xs=; b=L3Kbj6irTr19mM+1XjI/A9hiVhKgqazktylkl9OQOllrXzFcHp4VWIDyHr+nDjM5fk 4GVVhmCmLLbl/uUkli33A94dhBMxRevcb/l4oULvZ3cQBJvB/bdOEq1yheKrEtZesZ0o EEEc5Fdpi/baYAMXoEZnbs1mMUgISY30V8A8z4N+Xq7+4T9ynXvP+Y0/huWU/jwBW6qE phYdMAqGvq40HB70VcrznB4cUOdAMjMEYtubLqPHPf8qQOBzf9YQZdqRtp5yvAa/thIA BHZp8SPWsnYHxg09gUmoPUNfNQb2n0gfPf4o8njS3S/yUs2kF28TsS92TvVYD9SKYIAq bbOw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=N+tc7zM8; spf=pass (google.com: domain of pinheadmz@gmail.com designates 2607:f8b0:4864:20::62f as permitted sender) smtp.mailfrom=pinheadmz@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=1714481108; x=1715085908; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=Ob6D7dENxMij/O8zTrhhDn8EPQAU/i8ZfbDhlaBop2w=; b=EpzAYEvtZacYbeBjUvMvWrucHZNCuzMlXQaJN7PMUjqV6p4tnyAVSu/lHUDYiNlBmq kdBNDFNVy/anPepO239lXKbhlXsQnjINUCsmSHoJvgyH1LnJXE1UWS3qA+mxhEHzKDud 7KROxIRdJdkSusiIXmGt/7jpz2wdQvY28pVsH/pQUcZ/AgYbxxGukpSj7PWzk0aeWEpp ANPA2bqVQJyzVKm4fthiwbZJuRkijMmp93akcSi+ejbUGVPOLRtxuXa64qcCH27n2qGs SPn8IldiI4p4cI/CfA9sLk0WYsWTr2hrlVwBzcYUV70lwyEt8zHihxbgGDuBaFdeWXtS g78g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714481108; x=1715085908; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=Ob6D7dENxMij/O8zTrhhDn8EPQAU/i8ZfbDhlaBop2w=; b=VUHqUrvniTAH8iJa8uZTk+xOXEXs/jFqPaKbzcffpu8DHtgmUtvq9Vy/l6S0g3kN6A mxNdFgQD6oOvbey3/fJZKd3Gr8Aq9K8ILq6bMjVqwOHdFqNdtCuq7zJ5Bzczna8vb5+C tAlEvnU1HSydDo13AbSjFMncOM21DiOZfUuc4EwGHGs2oHFT9U46KuIS8OOy66QHkdZy /dhUkWJ4O/bXscoOQy5orMUIRhWWhwY60EC1ry46yQRrkXQwqeejfztXQ4nVWWYeBqE2 LtJGvtltJJl4MDhqpwZXsec6BrvCCu5EdjYkEtMTovyxKYxYaM03aPpLsqngR1Z0GHPF E7EA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714481108; x=1715085908; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-beenthere:x-gm-message-state:sender:from :to:cc:subject:date:message-id:reply-to; bh=Ob6D7dENxMij/O8zTrhhDn8EPQAU/i8ZfbDhlaBop2w=; b=mK9ylwlPOfyXg8MHVJBQmlHEP9r2mZuItxH4gZIPl3GfG80Up2Bk/UlaSJKDxSqOR4 QaaLKPpJk1KRLOG1IWUUXdklRVsBKkh+q4eNn5i0QNnlFzO9htg2U2TuPSKWgLXdYqZY W9j/UU5LSm9Od5DvFxC/ylDMR9XMacp/OL6pwRklfIXX34oMGCHyjueBoRQ+F+ebPN26 uRm6RE7pGrkubbvmoAPFdNdTgCwZKRIRsS3u0K7fks5y7/BEs1jv5dBgDgijPSYePtru yBVeZRfcAml53WUdYos2nKMR8v8DR1p26y9u1RmMycjJ0xVe0ohbyCdzwUpI8nC25ewv cKug== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCVdu0FgV79SChyRKiEWzCB9pIk/dWuaAe6q5gE7GwdjuemCi9ZiCGlqJHZxgZGm8Em0dIqH/ZtkYqqEU320SJz8+aSWn30= X-Gm-Message-State: AOJu0YzhJ5Q38oZGfbjf/aZgMTjgWVEmG0b3gkNyYQmnZgD2nm2oSKgQ U64l6pyyEg6x7RThvEOOjDruDa38HMi2+xt1b4zmxhRM/ML3npiv X-Google-Smtp-Source: AGHT+IFB0GJxH76gTIVnjYJhJY7bOv9FT9J3gv1iJdJQ0jMDnF/lfk9B8ZlG4GevgfXuKYLICmGgKw== X-Received: by 2002:a9d:6209:0:b0:6eb:8338:dd21 with SMTP id g9-20020a9d6209000000b006eb8338dd21mr13190810otj.37.1714481108521; Tue, 30 Apr 2024 05:45:08 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a4a:5e82:0:b0:5ae:1f6c:8981 with SMTP id 006d021491bc7-5af5d3797c5ls6792742eaf.2.-pod-prod-08-us; Tue, 30 Apr 2024 05:45:07 -0700 (PDT) X-Received: by 2002:a05:6808:198d:b0:3c7:493a:e5f5 with SMTP id bj13-20020a056808198d00b003c7493ae5f5mr52218oib.10.1714481107141; Tue, 30 Apr 2024 05:45:07 -0700 (PDT) Received: by 2002:a05:6808:23d0:b0:3c8:63a7:bea with SMTP id 5614622812f47-3c863a70f75msb6e; Tue, 30 Apr 2024 05:32:55 -0700 (PDT) X-Received: by 2002:a05:6808:19a0:b0:3c8:3771:6cdc with SMTP id bj32-20020a05680819a000b003c837716cdcmr16796721oib.45.1714480374888; Tue, 30 Apr 2024 05:32:54 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1714480374; cv=none; d=google.com; s=arc-20160816; b=akZdX70jUCfBZhH5OA4Ka9Dby9MeXlPnFEYNvuPoboYj0n6STli7ekhiJvb4O0ljwW 8rOhIL70xm31vz7l+s6JgW+/0dRihbBbU3fVa+WFN6RRZOj3RxjpGwW9lmDU5ajmzHCh E4Ua6ICRFLlumCvqlQD2z3pkY5TRwc1w+6FlFaaME9xcFyFxQ4SZLXIKpFjf04mSU3TA UPBskPZAvFmQMHga7pNy/kSaliyCOs1l1KVCSSy/4+vVsr7TnbBnQeEvl7rCCJXAbUt+ 4AjIDPx1twyTieCXVvqZnb+kaATfvSFpDFkz9VDb4NJ9DQ/i3gAWk8G9TmuIYeO94VIK Tq+g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=cW4lKpRsMqouTVyn7bJhsAXdWJxYwwbCLR8qsq5dPHM=; fh=MhNL3lrwfbsRO5DJHn9ZZ/LeA3+mAuX0vCziGEghh6s=; b=xQ1IJ1f3LnKy2nVHHltz51XQ3dPN9cTYVzFYkZc6leWYBpoBZ6AbFGOMzhZWu3n3xe VHXZhH26+VYkES8vw1pbS4rcj6fEmXrw/eFEmG69Q6BY1EQMZlWFVPDOiXz37U5DIpcY Q1EBziKUigtR676Kb6aY/rA51LzXXRV469xPdCNRt6PohzOD2jjIvtZmb5MrHgjeX/rN 4FrJaKFBShE3C/QQGsnpkH7YQwRSwjpE6+7kCP0aNyp7/U3mpXRykMih6NAE31nmk+9+ x/qwqe+u7eTMI0iPqymGWUhGmHHNqwG2LthE/+lCv/48wJ2fj0TG/wFOcNi9wgH42Mc4 8eSw==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=N+tc7zM8; spf=pass (google.com: domain of pinheadmz@gmail.com designates 2607:f8b0:4864:20::62f as permitted sender) smtp.mailfrom=pinheadmz@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from mail-pl1-x62f.google.com (mail-pl1-x62f.google.com. [2607:f8b0:4864:20::62f]) by gmr-mx.google.com with ESMTPS id qf10-20020a0562144b8a00b0069cfe7e48aesi2080556qvb.5.2024.04.30.05.32.54 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 30 Apr 2024 05:32:54 -0700 (PDT) Received-SPF: pass (google.com: domain of pinheadmz@gmail.com designates 2607:f8b0:4864:20::62f as permitted sender) client-ip=2607:f8b0:4864:20::62f; Received: by mail-pl1-x62f.google.com with SMTP id d9443c01a7336-1e4bf0b3e06so55797035ad.1 for ; Tue, 30 Apr 2024 05:32:54 -0700 (PDT) X-Received: by 2002:a17:903:2d0:b0:1e0:b62c:460d with SMTP id s16-20020a17090302d000b001e0b62c460dmr17168323plk.38.1714480373468; Tue, 30 Apr 2024 05:32:53 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Matthew Zipkin Date: Tue, 30 Apr 2024 08:32:42 -0400 Message-ID: Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed) To: Ethan Heilman Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000a29bba06174f91a8" X-Original-Sender: pinheadmz@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=N+tc7zM8; spf=pass (google.com: domain of pinheadmz@gmail.com designates 2607:f8b0:4864:20::62f as permitted sender) smtp.mailfrom=pinheadmz@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 (/) --000000000000a29bba06174f91a8 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable We discussed this scheme at NY BitDevs last night and one participant made a great point: > 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. If we are assuming discrete log is still hard, why do we need Lamport signatures at all? In a post-quantum world, finding k such that r is 21 bytes or less is efficient for the attacker. On Sun, Apr 28, 2024 at 8:50=E2=80=AFPM Ethan Heilman wr= ote: > 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 VzxPLnHq= r > [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 has= h. > > Our Lamport scheme is based on the following observation. ECDSA signature= s > 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 lengt= h > 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 Virz= a > and Andrew Poelstra both pointed out to me when discussing this scheme th= at > 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)`. Grindin= g > 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 functi= on > H, to compute: x0 =3D H(y0), x1 =3D H(y1). Next, you publish x0,x1 as you= r > 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)=3D5= 8, > 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 has= h > that matches the size of her signatures for each different ECDSA signatur= e. > The probability an attacker manages this for three random ECDSA signature= s > 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 a= s > Alice is: (255/256)^(n-m)*(1/256)^m > > On average Alice would need 1000 attempts to sign with n=3D800,m=3D10. Wh= ereas > 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 t= he > security of her signatures by increasing length diversity. Unclear if thi= s > 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 mak= e > 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 i= f > 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 directl= y > signing the ECDSA signatures lengths, you construct a 32-bit bit vector o= f > 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 i= s > 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 oth= er > ECDSA signatures. That said, perhaps there is some way it can be exploite= d > 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 > 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 use= of > ECDSA pubkey recovery. This does not work for our scheme as we must commi= t > 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 Cur= ve > math lines up perfectly with a 256 bit space especially for a fixed r-val= ue > that has special mathematical properties. Non-uniformity here could end u= p > 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 givin= g > me feedback. This initial discuss was fueled by the MIT DCI espresso > machine. I've attempted to credit all ideas contributed to the contributo= r, > 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= -signatures-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-= sig_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/0= 00344.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/ > > -- > You received this message because you are subscribed to the Google Groups > "Bitcoin Development Mailing List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDM= zQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com > > . > --=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/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw%40mail.gma= il.com. --000000000000a29bba06174f91a8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
We discussed this scheme at NY BitDevs last night and= one participant made a great point:

> if an at= tacker managed to grind a 23-byte r-value at a cost of 2^72 computations, i= t would provide the attacker some advantage.

If we= are assuming discrete log is still hard, why do we need Lamport signatures= at all? In a post-quantum world, finding k such that r is 21 bytes or less= is efficient for the attacker.


On Sun, Apr 28, 202= 4 at 8:50=E2=80=AFPM Ethan Heilman <= eth3rs@gmail.com> wrote:
One day having lunch at the MIT DCI and di= scussing OP_CAT and lamport signatures we came up with a scheme to do lampo= rt signatures on Bitcoin transactions without OP_CAT.

This scheme ha= s 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 no= t use this signature scheme in a Bitcoin output unless your intent is for t= hat output to be a fun crypto bounty. I have not tested this in Bitcoin scr= ipt.

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

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

## Signing a B= itcoin 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 n= once
- dA is the signing key,
- z is derived from the hash of the si= gned message, i.e., transaction hash.

Our Lamport scheme is based on= the following observation. ECDSA signatures in bitcoin are variable in len= gth and that the length of an s-value in an ECDSA signature for a fixed non= ce, k, and fixed signing key has its length determined by the transaction h= ash. We can use OP_SIZE to get the size of a signature and we can use Lampo= rt 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 Virz= a and Andrew Poelstra both pointed out to me when discussing this scheme th= at setting k=3D1/2, that is setting k to the multiplicative inverse of 2, r= esults in a k with a very short r (r=3D0x00000000000000000000003b78ce563f89= a0ed9414f5aa28ad0d96d6795f9c63) [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 byte= s long! A publicly known k leaks the signing key, but that doesn't matt= er for our purposes.

Using this k, we can ensure that the r values o= n 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 byt= es of zeros) computations assuming no mathematical shortcut such as the one= used to find k=3D1/2.


To explain how to use the above observati= ve to sign Bitcoin transactions with Lamport signatures, let's remind o= urselves how Lamport signatures [1] =C2=A0work. To sign 1-bit with a Lampor= t 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 bi= t 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 t= o sign the length of a bitcoin signature. The length of the signature serve= s as a proxy for the transaction hash of the spending transaction. Repeatin= g this many times provides cryptographic levels of security. Let's look= at an example:

Alice computes her Lamport public keys and signing k= eys
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 pseudocod= e Alice's redeem script looks like:
```
PUSH ecdsaPubkey0
OP_C= HECKSIG (ecdsaSig0)
// Verify lamport signature on ecdsaSig0
PUSH x00= , x01
if OP_SIZE (ecdsaSig0) =3D=3D 59:
=C2=A0 if OP_HASH(y00) !=3D x= 00: OP_RETURN
else if OP_SIZE (ecdsaSig0) < 59:
=C2=A0 if OP_HASH(= y01) !=3D x01: OP_RETURN

PUSH ecdsaPubkey1
OP_CHECKSIG (ecdsaSig1= )
// Verify lamport signature on ecdsaSig1
PUSH x10, x11
if OP_SIZ= E (ecdsaSig1) =3D=3D 59:
=C2=A0 if OP_HASH(y10) !=3D x10: OP_RETURN
e= lse if OP_SIZE (ecdsaSig1) < 59:
=C2=A0 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:
=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 sig= natures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For example let=E2=80=99s say OP_= SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D58, OP_SIZE(ecdsaSig2)=3D59. Thu= s, to spend she generates a Lamport signature over those lengths by releasi= ng the preimages: y00, y11, y20.

The spend script pseudocode:
```=
PUSH ecdsaSig0
PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 5= 9
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 attemp= ting to steal her funds is that all Alice has to do is release the preimage= s for the lengths 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 different ECDSA signature. The probability an attacker manages thi= s for three random ECDSA signatures given the lengths above (59,58,59) is 2= 55/256 * 1/256 * 255/256 ~=3D 0.3%. Alice can arbitrarily amplify her secur= ity 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 val= ue, not the bit length. This means most of the time if Alice just used thre= e ECDSA signatures, they would all be length 59. In such a case the attacke= r would have (255/256)^3 =3D 98% probability of generating a transaction th= at can be spent using Alice's signature on the attacker's very firs= t 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 d= iversity 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 Al= ice 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. Whereas an attacker would need to ma= ke 2^84 attempts to brute force the output after seeing alice attempt to sp= end that output using a n=3D800,m=3D10 signature.

## Known weaknesse= s

1. *The Tuning Attack:* The attacker can use different SIG_HASH fl= ags per signature to attack each signature individually. For instance ecdsa= Sig1 doesn't have the right length, the attacker can try SIGHASH_NONE t= o try again without changing any of the other signature lengths. This provi= des the attacker some advantage but with sufficient numbers of signatures i= t does not break the scheme. Alice can also use this approach to increase t= he security of her signatures by increasing length diversity. Unclear if th= is 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 by= tes would allow an attacker to make a few more individual attempts on a par= ticular 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-valu= e 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 len= gth is 59 or less. We could extend the scheme to sign multiple ECDSA signat= ure length values, 59, 58, 57, 56... This could enable Alice to greatly inc= rease her security as say 56 would only occur 1 out of every 2^32 signature= s. Winternitz One Time signatures (WOTs) [2] could be used here to compress= signature length.

1. Jeremy Rubun suggested the following optimizat= ion: rather than directly signing the ECDSA signatures lengths, you constru= ct a 32-bit bit vector of the signature lengths using OP_MUL, OP_ADD.
<= br>bit vector =3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D5= 9) + 4*(OP_SIZE(ecdsaSig2)=3D=3D59) ...

Then you compute a Winternit= z One Time signature over this bit vector. This would require also computin= g a WInternitz or Lamport signature over a checksum of the bit vector. This= would substantially reduce the number of lamport public keys and signing k= eys 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 sig= n 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 strengthe= n or weaken the security of this scheme. Alice using OP_CODESEPARATOR to st= rengthen the security of this scheme by increasing signature length diversi= ty 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_CODESEP= ARATOR would still influence all the other ECDSA signatures. That said, per= haps 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 remove 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 p= ossible to create transaction signatures that have r=3D1 without knowing k,= through the use of ECDSA pubkey recovery. This does not work for our schem= e as we must commit 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 bi= ts of security does each ECDSA signature contribute in this scheme given th= e 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 w= ith a 256 bit space especially for a fixed r-value that has special mathema= tical properties. Non-uniformity here could end up helping (increasing leng= th diversity) or hurting (a pattern an attacker could exploit to match the = length faster than brute force) the security.

4. An attacker could t= rade 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 a= ny use for this beyond a fun party trick?

Thanks to Madars Virza, Da= n Gould, Armin Sabouri, Neha Narula, Jeremy Rubin, Andrew Poelstra, Robin L= inus for discussing this with me and giving me feedback. This initial discu= ss 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-Rec= overy?tab=3Dreadme-ov-file
=C2=A0
[1]: "Constructing Digital= Signatures from a One Way Function", Leslie Lamport (1979), https://www.microsoft.co= m/en-us/research/publication/constructing-digital-signatures-one-way-functi= on/

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

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

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

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

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

[7]: "Qua= ntum Proofing Bitcoin with a CAT", Jeremy Rubin (2021), https://r= ubin.io/blog/2021/07/06/quantum-bitcoin/

[8]: "CheckSigFrom= Stack for 5 Byte Values", Jeremy Rubin (2021), https://rubin.io/b= log/2021/07/02/signing-5-bytes/

--
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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNO= ekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com.

--
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://groups.go= ogle.com/d/msgid/bitcoindev/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwact= Pnrgyw%40mail.gmail.com.
--000000000000a29bba06174f91a8--