Delivery-date: Mon, 09 Jun 2025 08:46:27 -0700 Received: from mail-qt1-f187.google.com ([209.85.160.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uOehe-0004eq-MC for bitcoindev@gnusha.org; Mon, 09 Jun 2025 08:46:27 -0700 Received: by mail-qt1-f187.google.com with SMTP id d75a77b69052e-4a584d0669fsf81792701cf.2 for ; Mon, 09 Jun 2025 08:46:26 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1749483981; cv=pass; d=google.com; s=arc-20240605; b=RJW5mNrjqfWXQ8yJYO26zCh8AA8y9f25tHDUjfQD2n0gUVrtlROgM9XIf5uhC4WL7m SNoBwLJWxROTC5G8k9xl9LmKtvYxNZU7X+LbTfb4LuEU3tg3F/0FiubrATcHm/+iyRn1 43P4smC3InXCVf7meltdXiYDyTDlABsSU6ZvcigafiNZxMG6X9RPRDVKjpoysAFjlb86 Ar2+QvQFS2bUWlTNZfLvMI0IMuGkuspcGLy5/1aq9nAHjO1i4PZhetoSQUuJ2LdYL7Wc oXzeC68An2OO662g+gKpAhT88qOIIKniQ5/C9DwcB2PAXH38wWq+UMVjqTy6ynqj0lQE A/Eg== 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=mnsjd75vsGSsNimGrIKQlZMK7O19LOm5XqC6234h4SA=; fh=xhOMkKaqZ0C+0ESUpoSL7FtLPX+zfQT9BNS9ZL3g5d0=; b=eggfQNGsWZT33OotO7mmB525EZXOYqOEnd5dVpPvoE6sWM1juqF02DTlTRxSEj8gUe u4T3WfVmTfPLG3zGAIluvaP/Sb9WybXxImPuMia4bs4ac5nynY2fPd1i3TWIZVCM9lKZ PSOsSt2+RcOeOdjrKNNdUaK6YR0Ilk5iSKZo6gv44j4FdoxTYSjDFnZ4w7AiaLLDteo7 0Y6nDBVzCpqNcZ0Dqq5uPmpdgpVzLmgjUz7+9vn7GHMWYk9AGPhs21BtMeEuzwq75R1Z f9izAw+PHj0mVeJxhb2+gfl99+QDCwkNAmOa9uWKJZIl81VUb0dQknAp4xCHJTs/xl2L NYmw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b="ga/ytJnW"; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.30 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=1749483981; x=1750088781; 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=mnsjd75vsGSsNimGrIKQlZMK7O19LOm5XqC6234h4SA=; b=N8kOY9XvGPlPePKQQMxKGA1X/S3IHBQzoD5QiCMn3WLQkFTJZ+IN9WnqKMaS17ao7S hBwi2f2seXLtWPYNL+QBTc5luaVPRCMpuVcOW82ZIYFYZepUmjLvieea7UN/BDv1t3PQ CE4iOf3lZpm5x+uYcArgPs7jJjIWCoufquFyu8lE7Wfor7FlGdrktX0xF/ov8eVeGJXX jSiA8dV42PsQhxc3FV51W92Cq3CixSmG5zDs9N7WMUnGiEddDrX2rV73a1wYU6IJfd1x w3DZwLuCXRTlrbvl53LPKrCE95mL3I2B2j8gNOnpgj/Akz+B6VyK2bWKlbHDvAaEREPf Vgbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749483981; x=1750088781; 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=mnsjd75vsGSsNimGrIKQlZMK7O19LOm5XqC6234h4SA=; b=imsz3fzyxo4L2JkGg+p8QwHvTmWaYM882l1ricg4cvWUnftNS/z2ZfitZI8eSDxiED uLyFTcFJyZXLtoJ01pTyUswu4nvFlH03Vs/DWPLf4uUKNUNuuyP6GPzXedGEhWLKfgsR yB372ukWJaAIo0z13idKacilJ9lJMWPxvIy2NkgRGRnzKksviuoOWu/O/3vmuHyCiqs5 ERgbQxb4Y/9dLOqiUpH4+X8pGDjyoyXX+VVKLmV7FX72YKCcjJQYwXwyRP1Tlx0jc7bF z9IWDiOMcpxuQe+q2lxjmyUlTbUOsI1Rz/VSJene5fgLlQYrrDJ35sTM/hCI0Z/7QDNB D2iw== X-Forwarded-Encrypted: i=2; AJvYcCWPT4UxqDoO7hQnb21HPQ8J4NLXQWXJ7KFtbrylmHX7EPK+BkeOGwkiu/t1mse1zKRSJ+y6s99DZSgJ@gnusha.org X-Gm-Message-State: AOJu0YwIrnnIS6N5YzGoWYkujI/pu0lRDyadPiLyYNN8kCuL7WJF6r8M F4NfbZVTe1fINSvYwTBGL3Ai3ZWgWLKvcx7qnlhRYBkgAw1PRGTlwh/M X-Google-Smtp-Source: AGHT+IG26QwDd6xb3Cj4swGTpolzGfzJbZhPfXJzEIseiHWiw+pCWQhZNkPgCW2fu/Pgv2y5H9TlIQ== X-Received: by 2002:a05:622a:4c10:b0:494:ab13:6824 with SMTP id d75a77b69052e-4a5b9a2a967mr225249841cf.15.1749483980448; Mon, 09 Jun 2025 08:46:20 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZfppe9IBspO1uQCPM/3txCBN2JRqe1/kU2sCi9ZjYxPbg== Received: by 2002:ac8:58d1:0:b0:476:8286:80fb with SMTP id d75a77b69052e-4a5aee9dfedls75282981cf.2.-pod-prod-01-us; Mon, 09 Jun 2025 08:46:16 -0700 (PDT) X-Received: by 2002:a05:620a:2494:b0:7d3:9012:75b7 with SMTP id af79cd13be357-7d390127a5bmr1093104685a.31.1749483976627; Mon, 09 Jun 2025 08:46:16 -0700 (PDT) Received: by 2002:a05:600c:4506:b0:442:dc76:9493 with SMTP id 5b1f17b1804b1-45222aacd4dms5e9; Mon, 9 Jun 2025 08:31:55 -0700 (PDT) X-Received: by 2002:a05:600c:4ed0:b0:439:5f04:4f8d with SMTP id 5b1f17b1804b1-4531cb49a8amr3050235e9.12.1749483113215; Mon, 09 Jun 2025 08:31:53 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1749483113; cv=none; d=google.com; s=arc-20240605; b=eXEwBA472nVj59YmGHoImW4Nsqc4fmKZZCVQrLePH+t0BTyj109bqsg+aRmiFzvl0P dygCYu/dfiNe6Zwxq7g/JOK6iv6KsRI/rgNORwwkPYrkJcINPp47n86QBUvtROAXzNzQ DX2P+Jlw6CyniH1WrbwdcIulKjEfQEgbqmtYnlMhjuLC8xFDjk8q5y1mo+Sd3rsr091t NjjeLj8gHL5hdEeioeWlUtdxrNq+dzRKN9KLBs/xaLeYcvx75FkvemSdKveNzVWDi3bm 6XiVBf6OoGAgYs4PsBKAfgdD9C54rEBzXUGM/Oj8pN2qAxezcuxHb7byjIjeJvHXeJnz Vv3Q== 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=Jcjf3xg1k53LEslhW9X0smiXmGTWZm8lDKwC2vQZn6Q=; fh=Fu/0X12jMFfnxpZZYBlgfbTQCZl5IbybcR1z6x5vbkE=; b=cnwwYwGHPY2pSl9ota8COFl5fEwR7bHxUuGGJOrFsOH3f0yE5LzMN7mImVWhVxmC6z XKeyxETTiIk856/GtornphWm9GfqIqR5iKrIOZ+kr5pjZGj3nTHHlM9RRRBt4C7L1T2E Et/lwe3z3995A6bQ7q8gZBMUfjKdg9m1+WIQgjjJK5z1VUzkyE0RpAUlN9U9C3f8PE6N c+dmEnGGC07Sp5BS+Cewf3s685GxP2ClZYS/SgU5YyF2MT7yXGii16D7nSIrPfDBdk7M Ocyx8iY+tYpuEVgptNa2VeaJJEX3w87ahz5pGH7XYzwTsTCNQYCgmtyjEwG9x/X4UiV9 wnBg==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b="ga/ytJnW"; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.30 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-10630.protonmail.ch (mail-10630.protonmail.ch. [79.135.106.30]) by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-452013ded78si1793675e9.0.2025.06.09.08.31.53 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 09 Jun 2025 08:31:53 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 79.135.106.30 as permitted sender) client-ip=79.135.106.30; Date: Mon, 09 Jun 2025 15:31:47 +0000 To: Dustin Ray 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: 1051db18c55e5dbe6f335e9438680e6d86e322ad MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------aca376e1348df49d826e95ed040c22f456d07bf2ec55df5cce13abe49a1c168f"; 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="ga/ytJnW"; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.30 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) --------aca376e1348df49d826e95ed040c22f456d07bf2ec55df5cce13abe49a1c168f Content-Type: multipart/mixed;boundary=---------------------ed80467f0feadd1dcf0685beb7c71811 -----------------------ed80467f0feadd1dcf0685beb7c71811 Content-Type: text/plain; charset="UTF-8" Hi Dustin, I agree that in a best case scenario, we should hope for much smaller signatures as the default in a post-quantum bitcoin network. Ideally some new age cryptography such as lattices allows this. If every Bitcoin transaction used a large hash-based signature like Lamport, WOTS, or SPHINCS, then L1 TPS would have to drop, or blocksize would have to increase, and nobody wants that. But it's good to have options. WOTS not an ideal one by any means, but it works, and assumes little compared to lattices. Maybe useful as an emergency quantum-resistant escape hatch, in case the network doesn't come to consensus on a more compact signature scheme, or if the novel scheme that we do use turns out to be insecure. Best case is that in a few years, someone invents a scheme with 64 byte signatures which is quantum resistant, and we add a new opcode or address format, and everyone migrates to that. But let's not put all our eggs in one basket. PS thanks for the link Yuval, I wasn't aware of that prior work. I believe my construction improves on Jonas', on two counts: - My approach requires only CAT, not full GSR. If we had more opcodes (namely OP_LSHIFT), my script would get even smaller. - My script results in much smaller witnesses. 8kb vs 24kb. However, I didn't attempt to implement WOTS+, only vanilla WOTS with checksum compression. This was mostly because of the difficulty of XORing without access to OP_XOR. regards, conduition On Sunday, June 8th, 2025 at 4:20 PM, Dustin Ray wrote: > I don't mean to sound crass but i do find it incredibly ironic that the same community that went to war over the block size all of those years ago is now seriously considering dumping kilobytes of possibly *stateful* signature data into the blockchain. > > I am very concerned that allowing that volume of data is going to seriously harm decentralization. Low power and casual devices might struggle to keep up with managing a ledger with such a substantial footprint. > > > > On Sun, Jun 8, 2025 at 3:59 AM, 'conduition' via Bitcoin Development Mailing List wrote: > > > Hi list, > > > > Jeremy Rubin's earlier work has already shown > > OP_CAT enables Lamport signatures [0]. Jeremy's > > approach gives us a script pubkey which is a little > > less than 8600 bytes, plus a witness stack of 2121 > > bytes, for a total witness size of ~10721 bytes. The > > scheme relied on using RMD-160 hashes to achieve these > > sizes - SHA256 would've bloated the scheme > > significantly. > > > > I'd like to concretely demonstrate one more post-quantum > > signature algorithm which OP_CAT enables: Winternitz > > One-Time Signatures (WOTS) [1]. Specifically we instantiate > > Winternitz using SHA256 hash chains of length 16 (AKA > > "w = 16"), with a checksum compression technique > > inspired by page 4 of the SPHINCS+ paper [2]. > > > > We use WOTS to sign the SHA256 hash of an EC signature, > > which is validated by OP_CHECKSIG. We break this 256 > > bit hash up into 64 words of 4 bits each, and then use > > script trickery to concatenate and verify the 64 words > > match the EC signature's hash. > > > > See a prototype implementation in pseudo-script on > > github here. > > > > https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182 > > > > With this approach, the script + witness stack are > > substantially smaller than with Lamport signatures, > > even when using 256-bit hashes. More concretely, the > > serialized witness stack looks like this: > > > > 64 x SHA256 hashes 2112 bytes > > 64 x message words 128 bytes > > 1 x BIP340 EC signature 65 bytes > > 1 x Witness Script 5610 bytes > > 1 x Control block 33 bytes > > -------------------------------------- > > Total 7948 bytes > > > > > > I suspect you could shrink this by a few more kilobytes: > > > > - If you were willing to compromise on security in favor > > of compactness, you could use RMD-160 hash chains, or > > sign RMD160(SHA256(ec_signature)) so that you only need > > to sign 40 words instead of 64 words. > > - One could experiment with Winternitz chains of length 4, > > breaking the message into 2-bit words instead of 4-bit words. > > - I'm no script wizard, so I'm sure there are optimizations > > left to make on the witness script. > > > > To be useful, this locking script would need to be > > hidden as a tapscript leaf and revealed only after > > OP_CAT activation. Naturally, this assumes key-path > > spending is disabled, otherwise the whole scheme would > > be easily defeated by a quantum attacker. > > > > I successfully tested this protocol out using a Bitcoin > > Inquisition [3] regtest node. A file containing example > > transactions is attached to this email. The second TX > > spends the first, using this Winternitz scheme. The > > spending TX comes in at only 2070 vbytes after accounting > > for the witness discount. > > > > (Big thanks to kallewoof for making the btcdeb > > debugging tool [4], without which I would've never > > gotten the script working) > > > > > > regards, > > > > conduition > > > > > > > > [0]: https://gnusha.org/pi/bitcoindev/CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com > > [1]: https://eprint.iacr.org/2011/191.pdf > > [2]: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10179381 > > [3]: https://github.com/bitcoin-inquisition/bitcoin > > [4]: https://github.com/kallewoof/btcdeb > > > > 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. > > > > -- > > 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/uCSokD_EM3XBQBiVIEeju5mPOy2OU-TTAQaavyo0Zs8s2GhAdokhJXLFpcBpG9cKF03dNZfq2kqO-PpxXouSIHsDosjYhdBGkFArC5yIHU0%3D%40proton.me. -- 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/PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk%3D%40proton.me. -----------------------ed80467f0feadd1dcf0685beb7c71811 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== -----------------------ed80467f0feadd1dcf0685beb7c71811-- --------aca376e1348df49d826e95ed040c22f456d07bf2ec55df5cce13abe49a1c168f Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmhG/lQJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmfAFCz2jFeFJYjTNmrH0njp/ASOJfYuMx0lhqxL LDN5GxYhBEdIka0CMtrLdg13a3gpbO2E9rPFAAA5LwEAiaHvYltYaZmedY5w N5TO6ViNE/GMIlpH5a2jMia8EY8BAIXLgXqXvWOXFFgSTOHkwNj0wIirsvyb O7+VF8VVQWYE =o9rN -----END PGP SIGNATURE----- --------aca376e1348df49d826e95ed040c22f456d07bf2ec55df5cce13abe49a1c168f--