From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 07 Jul 2025 18:15:50 -0700 Received: from mail-oa1-f63.google.com ([209.85.160.63]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uYww1-0004Ex-Vu for bitcoindev@gnusha.org; Mon, 07 Jul 2025 18:15:50 -0700 Received: by mail-oa1-f63.google.com with SMTP id 586e51a60fabf-2e95bf2f61dsf3196756fac.1 for ; Mon, 07 Jul 2025 18:15:49 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1751937343; cv=pass; d=google.com; s=arc-20240605; b=dAgqbN8gHhKkG+6i08w+9eVcQiSkoaLyaTed7x6hJKdkBphqWDhsI3HT/BMQZcO22l jHzuEB0FXfN2SFC9brKM4DCkwUIBcpUgLK53mS7Lg8drtTg6sGhY4POmJoIX2qKz4jkk 7G7FREHQJ9w4b14Vpg6o4KncdCDckxuz9oROJXF1UPhR4PmY+ybmo5Yg5GgP/WmiI8xf z4CKy3LK2LYk9Wc1z+IRtredOMN1oNErHuHQDWgfOGuTJy9dXne4pQja3cCu9cRtVDbz OJPUmv6qrWOW1MFsK5WpXYqTGa4y2PissFuhSdZlt1E9hraa0OOdERBLqawoI0K/LpTM EBzQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:mime-version:feedback-id :references:in-reply-to:message-id:subject:cc:from:to:date :dkim-signature; bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=; fh=55W0gd9zHgqJGE+YsV4y4Yuf59h/UWeiSUPEmHzyWIY=; b=dmxZAbxBr95MRe4CfsKN59SOipw2nIGd+AOjD8XC/ovkiojGtiakdQ4oVr3VKWvtyt RpCYA8zh2Ibt2maWvZaKVEKSdyhmjZaRUHz7RGvK2KokTrwG6xP9PHkXriXmObxhFZxG Ez6MiKa8Ey4MFSCZlZTMx0KpKyGG03r0bZRhdyrgIuhhV9pNVL2cQ/otGyVjOVKst7gM TRu/MD/3IwhhAsqsB7D7lwAd5s5VQ1/ZPGoZbfPdvo3Ba41ETWfecZ018sT2GVukOlag vOQH4J1C5sFSazPNHzXIBRTs4GUREcF5mV087SiO5RRr/8BsT2eKjBTNa+QkglF0lQK8 FSbw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=cJzNpeQX; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1751937343; x=1752542143; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:from:to:cc:subject:date:message-id:reply-to; bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=; b=HZkXJu1ztN5O2EqPabyuh9aYEMvYCogXeB2G8KVK6Yi37LaTOEf2HAebpGviZgkaj6 09j3mvS+1vPfJ0FkKe9fpTbnvX9h9wmRCji0JsnEB02fX5f2VaoX9hYqe6IvOKbaWV91 +JXZ1ZmLGwufMLYichbFvuW38SjYIXoN8zDO/+KDUlsL9aQwUrkrN20ta+H6rQA0CMjf tsQ+81+3Q53JeDjDMsf/WqOSwMpiZvd154QEfJEXZ/bli5orTCk8aOySgfuJYYJx/GJq 7nqqrBoqBhnk+DKUgOnxONPX6gDtP0pFlznXcskJggK1d4/P7yeMBy8yEOGQt0Sb6eWr fCJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1751937343; x=1752542143; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:x-beenthere:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=; b=EcLbnWCC46WnBkOYepbbEbUrpsuF0W/wPsbtvExS4Q262FDKWtwzziKzsrJzpMwear NxY7pB/9rtW5NFKV2l3RqsFp1e6INibAorDuDsvigqeszJ26SMB6biEEna9zk/d0bWIJ Y3d+dCJPu6BKzBEvKEwk1/fZRepuXRv6z0ZePBHILvWcKolEWUPjMWe76n6lTFEaQFP+ D4QFw+3/Lsdava3HOK0G1pFyZvZQXbaD9HEKcA3AUz5eakl1n+P3reRxMUhXjnWj7nlm YXwS3u5uIsu8GSBG8BNiiBpDhcbfnPN6DF/zNKIu10gThDIbR90knnA6PNHbvd4acIHJ 8XLQ== X-Forwarded-Encrypted: i=2; AJvYcCWZu2fxC/KRXPaRDycVwdT5+RF5GSZitQArj9rugXuhmem/Aoi3TmM+ZlHtwkxK19STQ0KYLlRX/leN@gnusha.org X-Gm-Message-State: AOJu0YwVOPhq40OrE58MMaac/ETt5daaF4xfzCuoLWlHAMa7Y/yAD7MH E6BWPH3M/nGIQvAQ/5DmN1qhsWHlw7ndJ0VgmulSCww7DJTPaKal3kII X-Google-Smtp-Source: AGHT+IGRW2fiWsZwreoo3n1i0D3rAk2eAUlbPsdLtn/io2IdTMkYk6Z50FbdMzCp0/b3V4K7AR2YBw== X-Received: by 2002:a05:6870:b204:b0:2e9:925b:206f with SMTP id 586e51a60fabf-2fb70ea7b5amr668047fac.17.1751937343490; Mon, 07 Jul 2025 18:15:43 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZflN1F3sfxB5mFKswBKKELLkbuw0rEZXrAcKCPnMdRHvw== Received: by 2002:a05:6870:c103:b0:2d5:17b7:9f8c with SMTP id 586e51a60fabf-2f79b6b651bls1584847fac.1.-pod-prod-00-us; Mon, 07 Jul 2025 18:15:39 -0700 (PDT) X-Received: by 2002:a05:6808:152b:b0:40a:641d:677e with SMTP id 5614622812f47-41148d481c0mr634714b6e.11.1751937339673; Mon, 07 Jul 2025 18:15:39 -0700 (PDT) Received: by 2002:a05:6808:870a:b0:40c:f667:a8e0 with SMTP id 5614622812f47-40cf667aaa7msb6e; Mon, 7 Jul 2025 17:16:39 -0700 (PDT) X-Received: by 2002:a05:6808:3a0e:b0:407:9a0a:3f54 with SMTP id 5614622812f47-411493890acmr608691b6e.14.1751933799189; Mon, 07 Jul 2025 17:16:39 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1751933799; cv=none; d=google.com; s=arc-20240605; b=Gxu1Rvc1ARCL+Y8FruGxu8P+ADczoqLvsopOXhQLU3Uz3QXp/rz4r5lBxqMeCHRCir FH8aWmVgM64pTLsGKbzBUHIFyL4v5Ir933kTZOmcErM/ptp3sJYZ51tt9guCy0WcoBmP SeEHtdOrSzWWjuUyVt8tYdO/oe4FGJxItrOFy1UD53zPGzbHsrph9FRUXo23E1yCy+Q+ /RRWG1H6vqi/zdiJxDVUMBvWNOguC7T4XDKT+7SJPOeO+WCKkWHyidD/W6bOcuoGM1/c P2ZlN4+WewuTcDRvkFxFgSKeEflt1O5UW3/z1gNLvTvZNA9vQbp8h0482jjMuL2L1JtQ 7Cog== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=mime-version:feedback-id:references:in-reply-to:message-id:subject :cc:from:to:date:dkim-signature; bh=+7tQjwno83wg0q6eenFVYar+jhsGFwsHHd78rVsQ8ks=; fh=eQwyrPB7DiKLZfk3HA1+IBNTG62m+FxzJ3AFq+zftRc=; b=UfbZ6UiKN5dq5qXoaCTKEQO4eeXdEBIs+cEoEmeqRzeua3V5nGh/SD0zF8bkZGQ5XE TD7lqMUAg6dDZ4AexUOEoduB5KFwV1S+BAxHxnQ0ialNoFAXmIbmL4On1gskuYJyYL0d C8eyQfyLFcdk+WaedWHUtpV0kEgm/RjZ6B4L5oPlGiFnwWZF6+scVgSQhJsstPa9BS49 ZK87Sjtadb6YRpQMDbt3PufESXR2YWIl38W5dAIMGGcBrKG/4LuwGC/DfMu/7cJqZEq6 4er8hdSpv1P81Jmt+Mv3mcbh4B5L4xWQeo1ro702ci9JDF7GXrKHl9B7tTtUp9bLokXK NfgQ==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=cJzNpeQX; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-24417.protonmail.ch (mail-24417.protonmail.ch. [109.224.244.17]) by gmr-mx.google.com with ESMTPS id 5614622812f47-40d02a1e4edsi398662b6e.1.2025.07.07.17.16.38 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jul 2025 17:16:38 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) client-ip=109.224.244.17; Date: Tue, 08 Jul 2025 00:16:33 +0000 To: Anthony Towns From: "'conduition' via Bitcoin Development Mailing List" Cc: Bitcoin Development Mailing List Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures Message-ID: In-Reply-To: References: Feedback-ID: 72003692:user:proton X-Pm-Message-ID: 56e6b3383c1a3bbf95c80801ff6cbdc8a2db62e2 MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef"; charset=utf-8 X-Original-Sender: conduition@proton.me X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=cJzNpeQX; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me X-Original-From: conduition Reply-To: conduition 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: -1.0 (-) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef Content-Type: multipart/mixed;boundary=---------------------8d0c2c9798e42661525f30a084d771e3 -----------------------8d0c2c9798e42661525f30a084d771e3 Content-Type: text/plain; charset="UTF-8" Great idea AJ, I didn't think about OP_DUP OP_ADD as a stand-in for OP_LSHIFT. That saves a bunch of bytes. We can save even more by using `OP_SIZE` to check if the combined number is greater than 127, since the interpreter's OP_ADD `output` should always be canonically represented as a 2-byte value if `128 <= output <= 255` (correct?). This lets us elide the SWAP/ROT operations, dropping it to 35 bytes per of script per iteration of that loop (down from 58 in my first impl!). Total savings across all loops is 736 bytes, bringing the total script+witness size down to about 7212 bytes, or 1803 vbytes. Very groovy! // ... SWAP DUP ADD DUP ADD DUP ADD DUP ADD ADD SIZE <2> EQUAL IF <128> SWAP SUB IFDUP NOT IF <0x80> ENDIF ELSE DUP NOT IF <0x00> ENDIF ENDIF I revised the gist with the updated bitshift code, and more detailed comments. Thank you! https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182#file-winternitz-ts-L100-L137 regards, conduition On Saturday, July 5th, 2025 at 6:54 AM, Anthony Towns wrote: > On Sun, Jun 08, 2025 at 03:20:08AM +0000, 'conduition' via Bitcoin Development Mailing List wrote: > > > See a prototype implementation in pseudo-script on > > github here. > > > > https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182 > > > I think you can do the four-bit pair to eight-bit conversion slightly > better with: > > DUP 8 GREATERTHANOREQUAL # is the high-bit going to be set? > SWAP ROT SWAP # drop that flag lower in the stack > DUP ADD DUP ADD DUP ADD DUP ADD ADD # combine them mathematically > SWAP IF # was the flag set? > 128 SWAP SUB # subtract from 128 converts 0x8100-0xff00 to 0x81-0xff > IFDUP NOT IF "0x80" ENDIF # special case 0x80 "negative zero" > ELSE > IFDUP NOT IF "0x00" ENDIF # special case actual 0 > ENDIF > > Should save about 640 bytes of script (11%, 8% total), I think. > > > PS If anyone would like to test this on signet, I'd > > be more than happy to help. I couldn't get my OP_CAT > > transactions mined for some reason so i stuck to regtest. > > > inquisition.bitcoin-signet.net was down for a few days when you posted > this, due to running out of disk space, which probably would have made > getting txs relayed pretty hard. You'd probably have more luck now. > > Cheers, > aj > > -- > 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 visit https://groups.google.com/d/msgid/bitcoindev/aGkYLuZZz2itqVJx%40erisian.com.au. -- 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 visit https://groups.google.com/d/msgid/bitcoindev/h9N4uIp0MgaASuEBpqsHjiQb9ahGbca3mG5V6iPVumT9ICT4monwV1ScgV3kdV2ka9CkQiSqEGkxA_eqqGQJ1TtFmWUlJEhi0McZU6yGBl0%3D%40proton.me. -----------------------8d0c2c9798e42661525f30a084d771e3 Content-Type: application/pgp-keys; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4ak1FWkRub0tSWUpLd1lCQkFI YVJ3OEJBUWRBcnBZYWFjZDgwcXdocmNaQW9VbW9NSHNWS21iZWlPZUEKcFhXbk1ybFdPZkxOSzJO dmJtUjFhWFJwYjI1QWNISnZkRzl1TG0xbElEeGpiMjVrZFdsMGFXOXVRSEJ5CmIzUnZiaTV0WlQ3 Q2pBUVFGZ29BUGdXQ1pEbm9LUVFMQ1FjSUNaQjRLV3p0aFBhenhRTVZDQW9FRmdBQwpBUUlaQVFL YkF3SWVBUlloQkVkSWthMENNdHJMZGcxM2EzZ3BiTzJFOXJQRkFBQTZhQUVBM1RmNHdqSVoKYnox K0diS0h4K09WQytNUXlVdi84RStoWUpjTE5QZnA0NEFBLzNiak5OTXN4WHdJTGZEM0xManNVVWFo CitBV2JyblVjVUFqQ2R1d3hUT01LempnRVpEbm9LUklLS3dZQkJBR1hWUUVGQVFFSFFDSXYxZW5J MU5MbAo3Zm55RzlVWk1wQ3ZsdG5vc0JrTmhQUVZxT3BXL3RKSkF3RUlCOEo0QkJnV0NBQXFCWUpr T2VncENaQjQKS1d6dGhQYXp4UUtiREJZaEJFZElrYTBDTXRyTGRnMTNhM2dwYk8yRTlyUEZBQUFR TFFEL2NCR2kwUDdwCkZTTkl2N1B6OVpkeUNVQjhzTy90dWZkV3NjQkNZK2ZMYTV3QkFNK0hTL3Jp S014RGt0TkhLakRGc2EvUgpEVDFxUGNBYXZCaXc2dDZ4Ti9jRgo9Y3d5eAotLS0tLUVORCBQR1Ag UFVCTElDIEtFWSBCTE9DSy0tLS0tCg== -----------------------8d0c2c9798e42661525f30a084d771e3-- --------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmhsY1IJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmf0ShO5xMGOnx8BOa3ifmhpGx3YyMIFpHXiwET0 /mhGqBYhBEdIka0CMtrLdg13a3gpbO2E9rPFAADJzgD+LWbQDKSJBvCSIHlv hId1rN7Hv1/ApIYFgZuDGK6wdxcBAOElQ7OukfmANqfir/fEJ3Xsvhpv9aK1 8aDitoNmZDUF =p+p3 -----END PGP SIGNATURE----- --------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef--