From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 30 Apr 2024 07:23:00 -0700 Received: from mail-oa1-f58.google.com ([209.85.160.58]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s1oNo-0007it-M0 for bitcoindev@gnusha.org; Tue, 30 Apr 2024 07:23:00 -0700 Received: by mail-oa1-f58.google.com with SMTP id 586e51a60fabf-23c436ee1ccsf2480098fac.1 for ; Tue, 30 Apr 2024 07:23:00 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1714486974; cv=pass; d=google.com; s=arc-20160816; b=M6xe4B3HY3kcv9jRrjPIDrwTZdWFqPF+gmg9MBxC/7U2fXp2xQ8vqAyJ31+pkppGvA +cqClo4tGNcFAbhZXUtA89a0KFyilk3ZRUkjDbietjofsdy2D0l094JXhcBqGL4XV1uV J1jgypD3Te46UTkSbRv+fNpFG+aBR2IkahU1e7qi9p27golP9Qu9r82FmXTQBT84rBFC RWEkdXdWbjG1/mIJARw8ueRwjyztXA14hHVfemZkp1vGbkQeruLHzVBw6nEz+GAiC6FW RDCQaq1uXE383P8HaQRKr8xH25BDxK3X5M+V+94BRXJmnmwE+6sVSgAUtKTyXZW5GwbR c9uw== 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:in-reply-to:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:sender :dkim-signature; bh=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=; fh=YVDvoCWtl+BaHy1XYszROR14Cw6wt1X3ywQ9SS9nEMc=; b=wXrNgqeTquvkYcFeiYBDmxCk5/9/IbnDC7i1GmX+gsUi3CavXX/qUbWDDUmS5wZ3ih 1o2BBkCZi8i5y6DiI9GaTTEkgxuGH1y1Ki9xdTUAOUxti1AYbxt4MHjEQaymRWep2FdQ hJBg4STJwA+pGxDff3csyQNOF5Tr02afAxVy1wePGXhEnluGSxTT4d818m18izXRW2fr O3kUlxgi3GNgkpn3VUt6Y05nqXwuX2kZupJ7Gpr1AgrM8sUzTnDYvv8zyL11R9T6gO6W DQ2iFn2Sg+BRMpqF8pZ6lbKxL+MjX6EY/YSfqqSqf9ICI7bEN/sn9eO8JVySL3UY/85M YQdQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1714486974; x=1715091774; 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:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:date:sender:from:to:cc :subject:date:message-id:reply-to; bh=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=; b=KJ45kBVVXPSYUbCCd49WrayZ5IoqLe6L+iPsJ0BiDSjhmpR0vEbtFk7UU2gcg1/aEv j+kSvAEPK1RaBUEimIBFpFuHnAH/GhdbxUxvUdAkJcGtWYVJOjdWm9I/AurpB+/zNJZ5 GwZ6xrL2bMRGcXY10kwbWkhRMBQLAW3FUV14JXe3muSgVb952N2eoTsdzkptkBqN4p3y B/n+JPD8ip5qIGWpm5oxhVShkrwW7u/Ton8UCdAsu7xh+J7j0aUZak5G9408gb4r+g4B ZlCq5qK3+qWHFamWmD1ipYduVyVJdit7CHpDNA4KKFnUU5okf0Nfa57Tki1/8i0woE6L eVdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714486974; x=1715091774; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=; b=rydx0Jc2DvgJYdmS3F9QBJwje2RrLAq7xEXfb+A99Qhiezq7P/JSyty40xUl2h+df8 zkjHHPwxSRNCtEFjyxkJqyHtzAZehzFfOiV3Xu2yVaRG+wgoWw1uo16r7fTVBDWQQo4Q eD4E+F9TvM+WHlZbcXYtvltx1l3oF2Q28yjLf+nBbub1Y/H9yWwH4o957PkKJjfNy+5i EKsSJm5jxySL7ul9+xWp7ECUZAAztxEgTFT8Tx5XeSGa7lBW0Pqs/gj71LA6aHKUb23j ivGWKRX7ZD0VD7EV/ITn+OsRcqDlmUKkNQSGQ2Rt8PwC5cZkGH/xOH1tK6J5o+uIQwEE wXzA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWkLq1aWLO3QTDak0622u/yeUFchI180YPsYlTkIZ9xet5uM87BMhHmubMWAf6AAlPKs91jkLyeDYnIcYadxbemdrgixhs= X-Gm-Message-State: AOJu0YxPGF2eCoNMwSdr+Yjh+UlfoLhQQzUnLpaBUSqxJ356oRpsbr1S r1XYxez74zBX/lGkNzCOOlYtN2I91V6gGoAoWzUI33ZTPHdF5uui X-Google-Smtp-Source: AGHT+IFzr5W21E0c49L7JxYCgQc71Fu1/U44TZzgxufVekSlHPzvAnW89ERNXFK75jweha+kpaFuXQ== X-Received: by 2002:a05:6871:6510:b0:22e:de21:e084 with SMTP id rl16-20020a056871651000b0022ede21e084mr15579212oab.9.1714486974591; Tue, 30 Apr 2024 07:22:54 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6870:2492:b0:23a:6680:6036 with SMTP id 586e51a60fabf-23b422f4240ls4328870fac.2.-pod-prod-07-us; Tue, 30 Apr 2024 07:22:53 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCUbUOs1BZkkr7hjrD3z5BdY44/QEAc8xxez60YYRqgsbySf7m0/ceiyFI0ERXri7ovFL+w7syFI9kenOUKubEiolEQN3GrfAGHt5xY= X-Received: by 2002:a05:6871:339f:b0:229:7ea3:7242 with SMTP id ng31-20020a056871339f00b002297ea37242mr738889oac.9.1714486973116; Tue, 30 Apr 2024 07:22:53 -0700 (PDT) Received: by 2002:a05:6808:1909:b0:3c7:2efe:13c8 with SMTP id 5614622812f47-3c855234df0msb6e; Tue, 30 Apr 2024 07:21:45 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCWnd19haoenaQCUWIhg4KvwfvPc0CyOQPP7JOqjhkrohTTVxBXMLx+/+9RtqcrVKAehxHDIt5f++/HaOL0wt6ZvauoUdwsrQIU4JAg= X-Received: by 2002:a05:6602:13cf:b0:7de:ce69:59b3 with SMTP id o15-20020a05660213cf00b007dece6959b3mr8451744iov.0.1714486904108; Tue, 30 Apr 2024 07:21:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1714486904; cv=none; d=google.com; s=arc-20160816; b=XX3jzBSIjSsbF1krs+Kndn/aOshF31bJdb1ggP3G9LHbi2LcI1bUAxkfPhZVsk/EbU 1yCocV1hPsxovDceaFuHyRw7VGhnIGuwQ05YJLVKJFwIA7xUhIpLVkvI12gTuN70bhw9 loFqsck0j+PSkYkgQZjWQ+9irYdGDzeQNV8hJH7PqPxW9sWY7XNBblZNwHV/IzAfpgjC mZ8ngcV1FjUqTIId5eUD/jl6ZoqVPdxmSep+DxsVNAmYwr/nQYvLaF1xj0IXbSeGuRxT XsAD59JmHcZhPzGzM1ukGITU1+VOtVySlUNVcHsWoiX7Y8HrXS36q7LOYuahZumMjUHC RdQg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:dkim-signature; bh=huahnpPsdftWHoy9pAy5+9Yk+Q+zk409uusVHnxUBns=; fh=BjIDVxpOvugBULxmWHhejF5MP/45cWrxFRfbz6qmqXk=; b=T1r2XzOIi9DoEP5jEHA2frMGcKGEwTP0YnErMtMiOFiPlAvY3cnYbjkQYT+9SDVtSH Nl0g/mADfJf+tAW7mB5eUga6pD4GlflK+s+z4DoXDMz7CuXaB1zhLWezSHY3I9mfg6Iq z5DrpFEm3xJTmBBzLF2RHEj0kB5iCq7yVK/yx627Y4i1LFp78q4Bb8lv2bx/XBGDp+Ln KM6NH4534s87YmDF8PlQH8SQ2f5zZ2eutIcJo0YWjTK1ghMMM3nIinB3Wj/BxJYNNszd Dwj0VTSmQEYA7PonMM/QnJL91xjN+Opmg/s/YWrSmC/emBmmoO5IYuDPuuA2W7B0mKG9 rd/A==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net Received: from mail.wpsoftware.net ([66.183.0.205]) by gmr-mx.google.com with ESMTP id v1-20020a5d9481000000b007deac6f33d6si572626ioj.4.2024.04.30.07.21.43 for ; Tue, 30 Apr 2024 07:21:43 -0700 (PDT) Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) client-ip=66.183.0.205; Received: from camus (camus-andrew.lan [192.168.0.190]) by mail.wpsoftware.net (Postfix) with ESMTPSA id F371C400ED; Tue, 30 Apr 2024 14:21:41 +0000 (UTC) Date: Tue, 30 Apr 2024 14:21:40 +0000 From: Andrew Poelstra To: Matthew Zipkin Cc: Ethan Heilman , Bitcoin Development Mailing List Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed) Message-ID: References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Lwd7sZ5ieIwUBdMT" Content-Disposition: inline In-Reply-To: X-Original-Sender: apoelstra@wpsoftware.net X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo; spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net 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.8 (/) --Lwd7sZ5ieIwUBdMT Content-Type: text/plain; charset="UTF-8" Content-Disposition: inline On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote: > > 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. > Aside from Ethan's point that a variant of this technique is still secure in the case that discrete log is totally broken (or even partially broken...all we need is that _somebody_ is able to find the discrete log of the x=1 point and for them to publish this). Another reason this is useful is that if you have a Lamport signature on the stack which is composed of SIZE values, all of which are small enough to be manipulated with the numeric script opcodes, then you can do covenants in Script. (Sadly(?), I think none of this works in the context of the 201-opcode limit...and absent BitVM challenge-response tricks it's unlikely you can do much in the context of the 4MWu block size limit..), but IMO it's a pretty big deal that size limits are now the only reason that Bitcoin doesn't have covenants.) -- Andrew Poelstra Director, Blockstream Research Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster -- 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/ZjD-dMMGxoGNgzIg%40camus. --Lwd7sZ5ieIwUBdMT Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmYw/nQACgkQxYjWPOQb l8EVRgf9Fr5cFPc7iiH1Pni22OgASDmDFNYK/KQipJJ5UtfhFk12DO77L25u74OU jCZFmhCWUs8JtBetekxCs4Tv7tfVMGSd9XAi1l0IBNn+8iV6iu89NBAmDbuaCV4j TgJAFtPjMlf8IufRd8uZGoq4XnvoINqDZe2o2h1qiFrGFzwyra6oNxM4OLSalWIL JMz6+5yu0XdGbRxj1V0pZ0KY8v02q5KRVy5enAhdkquklUKk1fefmbRm7UZrrefM dxdgOF15car2RaNZKqDYenwOhpDP32HYqEqT7HBuKj5PIKeVa6Iv/lhSnIdvnCuZ nXOhOLRbrw9rV6bTOxAagL6cAPCL9g== =bcrp -----END PGP SIGNATURE----- --Lwd7sZ5ieIwUBdMT--