From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 07 Jul 2025 18:15:53 -0700 Received: from mail-oo1-f55.google.com ([209.85.161.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 1uYww4-0004Fj-PB for bitcoindev@gnusha.org; Mon, 07 Jul 2025 18:15:53 -0700 Received: by mail-oo1-f55.google.com with SMTP id 006d021491bc7-60f430ab80esf3463209eaf.0 for ; Mon, 07 Jul 2025 18:15:52 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1751937346; cv=pass; d=google.com; s=arc-20240605; b=kVFz2RMoHgY0TrNBA58s8NjiSRRdpEBkwmLBdD8eSb0FD9tHZ8aOg4WDfsCOmYlucL CcTOWCrzGmFWmxyo9oCGSzubtu4xY2UMNZmKdUIVlCAU5FMsFO1W/Hl/aJapf7+a98eC 1Un+dQTcD/HDJcZ485v/Bx73JfnZiP1ZNxwt+bBlylRHWC6lU5JvmK4IVcJx9u/um61x V1vkwak9gTamZA1ykptnvAE3MU/Uw91m3d5ukZLBH8uRAfZZ8uTzviHs5rRIxHakHdTQ WmFzmBjcYaiijWGqQ04HSVN2KIj1IqZBgV/HDBUJ3QdaD6rmkKYqBmInTnzqSErLGrqh ksiQ== 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=dRszU/z94E5eJ8zyXyZ51Itur79FCFdOdt8dAf0Y8Mc=; fh=JzgvIcrVWIOAVtWUVioKbjZKWun0eihl7OqgtsQd/YQ=; b=YJxVgkz6TUAcogxYAxitJMZ6zr4GnlUAQER0fk6dsvz07VXEplhKRdVJF+YhgbLTlV b4ZhpcNlpdsO4830kPyr/F7Ta91q6xPLMtfLBzkRLQKVobdPMV1FrLdNimzaxIZoniCb vT2ItYL+5r2YVfI+kYsH7vC+8TfPSgTvVI5A/ee+GUesDR994qrCCzERnikqR0qKiiRY +csbI5yPZ+5T0k0gOxiuhv+RHoWBc6/nFaMfD5EI3kBhhTpJ866Z9n/16IJ1hQ76GktA exbF9ZRjpPsT8a5SrGPIqipycFjdJsWY1MjsU2pQ6vJ9dQ/xWy/C0NmCRFSpSupi2w0s e4gg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=Y5pQlo8r; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.29 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=1751937346; x=1752542146; 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=dRszU/z94E5eJ8zyXyZ51Itur79FCFdOdt8dAf0Y8Mc=; b=Q6EAuAkuOGq8gmkW3zIYzfXIYg0U3Qi7mMLqSg524BgP3xfqbAf/xpHaMHmt/QUdY0 y9XHDw9l3VUzqN93/UYbc65gRMAXSotrl6Y6Xd+kiEfvSIyaX9LqhqIh8N5aZFCyTMkj XT9xcti4wCVo6sWF62McsTWrASBuIAFz2kTi/PuFEmTq7Z11zn0x3I+FxeTovFEZABYR sgjXQ8hhata1krih9HuCypWo5u0MCMnuU4StHpHlE9xAnEBAUlraOzNT5pRKG79hEisU beQBJn3nEKdwZe3E7/GWWacwL9UToIB6O/PS9jtfvaMeyLJ0/QPTRmxQc6WSAIM7JUpl 1TGA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1751937346; x=1752542146; 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=dRszU/z94E5eJ8zyXyZ51Itur79FCFdOdt8dAf0Y8Mc=; b=i/s1nydh1tzMQWuz8nvRCi7EdPxrO7mqEGKH6yvVtGIg08EAS1TKzPQTwEqdBZI/gh uulITYW8CmcOTAp1NoCD2ptni5yL2eB2IXnE99VASATi/8owGHYdJ9kokgq0JuG4jNFJ 7ThVmLIuqHLnqZ4gJywv9UvUWL+nxEAMOQZq1P0m2x0ANeNhhf5vvelm6SUksMd1unrD G1jsHO0dS+9bAO2nzdHidCbUbd/yj2trgEjy0HY8p/cPGO7hxdVQPUV0ALYWHv3tB1Li 12jttua6mKUpkwFPPh/peEpHy0GeBAbiQOr+nFJYSZQz2jN+hSsAfXDu5ULNFP37UQhv 1caw== X-Forwarded-Encrypted: i=2; AJvYcCUCbFvMw1wRB6dwngX+h3xKFioFZuP1k4ja5syij8FozQrO/uEFMfa2xOcvA83o2ouOP0tUdoLVAmv2@gnusha.org X-Gm-Message-State: AOJu0YxU8F6baCfweQksXvudc33RFPHnrkB6syMjg/ITOlFt2XvTRbe+ WyfGEnafbD3Kt+6o7BmsnrLWTGHL7TKoOr8et0zfQBy03D2W7Fix1Ekq X-Google-Smtp-Source: AGHT+IFp+l4mdMXsmcuvzsSBLt3cU/sPH+NBZrOSjx9HrFZX6wDynQyd0jZqb7MUQ8IeJd8L7EQiWw== X-Received: by 2002:a05:6808:3a0e:b0:407:9a0a:3f54 with SMTP id 5614622812f47-411493890acmr717311b6e.14.1751937346548; Mon, 07 Jul 2025 18:15:46 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZdwzG/kNSLreqUtf2nDnX4gGAd+Os54cCc+dwf78njuvQ== Received: by 2002:a05:6870:219d:b0:2da:80e4:fad4 with SMTP id 586e51a60fabf-2f79b748155ls1553477fac.2.-pod-prod-00-us; Mon, 07 Jul 2025 18:15:43 -0700 (PDT) X-Received: by 2002:a05:6808:80af:b0:40b:a4ca:f7cb with SMTP id 5614622812f47-4114edb0ab0mr594362b6e.15.1751937343763; Mon, 07 Jul 2025 18:15:43 -0700 (PDT) Received: by 2002:ab3:145:0:b0:2b1:97ca:fe9d with SMTP id a1c4a302cd1d6-2b8ea2340e7msc7a; Mon, 7 Jul 2025 17:49:35 -0700 (PDT) X-Received: by 2002:a05:651c:20db:20b0:32c:4306:5a7b with SMTP id 38308e7fff4ca-32e5f568d5dmr27135141fa.6.1751935772962; Mon, 07 Jul 2025 17:49:32 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1751935772; cv=none; d=google.com; s=arc-20240605; b=ecDfjrpex42Dq6/sR3Ir9irUl1/UIPkUGjqR/SP1SQj4HXzDQGC0ds8cY45CgK+oZo eEfBNNUCqkabGuNcdQ8srpXE+GMe+RK96qmrVNYTVJcu31IqkxcLMzjfWxEgPixBfshy Ax0GWYSW5KlG34pZmv8jStQqMLTZb9tXCI5cN18e7ikNlaNm5l3ai1yuONKfQ7ih0hdl IMt/anTLf4ISntLqZvM6aBhNPzb8Q/AsWVnP6EbUnoGlRtfhSlbfn/dGFJOOw1YC/Yvo jfsICUb5qt2TWmrwzoG5ZbSCoD+X2lTnBeKKR9cUs/hMh4XcjH1wPIK4Kj9vbz4KXAO3 Afbw== 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=86C+74wop1L03rPykCbW77bk9Dc0e6JQoIHXi2sqdSE=; fh=MjdRPwMMqTCvqsS0x8/KiUP5ScpwSKUUuPzaYsRCcYc=; b=fGaSDPF1HBTJBIrhUIun0+XbLUvZMB8tBVPSlJzI2S881y+DihMnmO6+omtwuN6yqV V9oVBc/BV7TsEJOcjfo3Kq1vH6m9FeX+xeHihDACGSlk0u7+nKxR/O6uNUlvzcArfVdO mmOtfOYTkxvil0Lgm3xYu9igdHTnmFcGlGc9pUaXWbneD0ora+UEEhyiMmPkihOtEzEJ rnhnYGdlej7l5EOSWBO5Bmjgm6cJZyq/a13FbEELVMf4Q+q+f12N7oc+AWPkRL1AW3k4 XCv0gqC7ceTlSRJMgAzHMXkc7vfqZmgyo8TtQX1RbeGB9e4vKFaPtMgFd+V9X0zm6hnu wLfg==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=Y5pQlo8r; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.29 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-10629.protonmail.ch (mail-10629.protonmail.ch. [79.135.106.29]) by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-32e1b002c69si2065491fa.2.2025.07.07.17.49.32 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jul 2025 17:49:32 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 79.135.106.29 as permitted sender) client-ip=79.135.106.29; Date: Tue, 08 Jul 2025 00:49:27 +0000 To: Jonas Nick From: "'conduition' via Bitcoin Development Mailing List" Cc: bitcoindev@googlegroups.com Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures Message-ID: In-Reply-To: References: Feedback-ID: 72003692:user:proton X-Pm-Message-ID: 9a175c44a3ed48914092d5a3f607ce49b901d00c MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------28181ae1678496ea12aabdba076df9e0cf71568ee8a80cb5a8fb81e19c0c5be8"; 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=Y5pQlo8r; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.29 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) --------28181ae1678496ea12aabdba076df9e0cf71568ee8a80cb5a8fb81e19c0c5be8 Content-Type: multipart/mixed;boundary=---------------------3a31977699c472b1d663e8a288ff6a85 -----------------------3a31977699c472b1d663e8a288ff6a85 Content-Type: text/plain; charset="UTF-8" Hey Jonas, really cool to hear from you on this :) > For further reductions in size, it may be worth looking > into "Target Sum Winternitz" [0], where the checksum is > hardcoded into the verifier instead of being an explicit > part of the signature, at the cost of additional signing > complexity. If you take a second look at the script, we're actually doing fixed-sum winternitz [0]. For w = 16 as I selected, the optimal checksum for efficient signing is 512. You can compute the optimal checksum with the expression `w*(n / log2(w))/2` where n is the bit-length of the message to sign. Though unlike traditional fixed-sum WOTS, I didn't implement the random salt counter appended to the sig, as it isn't strictly needed. Remember: we're not WOTS-signing a static TX sighash - we're signing an EC signature which in turn signs the TX sighash. We can retry the EC signature generation step with a new nonce `R` unlimited times until we get an `(R, s)` pair whose hash fits the hardcoded checksum requirement. > I think the size difference largely comes from the fact > that my implementation [2] is based on W-OTS+ [3] and not > on W-OTS. The main difference is that W-OTS relies on > some variant of collision-resistance of the hash > function, whereas W-OTS+ only relies on the weaker > preimage resistance property. Agreed. AFAICT, the only reason we'd use WOTS+ over stock WOTS (w/o randomizers) would be if we wanted to use a less collision-resistant hash algo (RMD160) as the primary hash function. Someone would need to do the math to see if the hash size savings are enough to offset the added script size cost. Maybe you're not the right person to ask, but riddle me this: Would OP_HASH160 (aka rmd160(sha256(...))) be a possible contender for the hash function here, to shrink the witness size further while still retaining some of the collision resistance of SHA256? [0]: https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182#file-winternitz-ts-L95-L98 regards, conduition On Monday, July 7th, 2025 at 3:43 AM, Jonas Nick wrote: > Hi conduition, > > Thanks for this work. I think it provides a very useful data point. > > For further reductions in size, it may be worth looking into "Target Sum > Winternitz" [0], where the checksum is hardcoded into the verifier instead > of being an explicit part of the signature, at the cost of additional > signing complexity. In this scheme, the signer has to hash their message > with some randomness, encode into chunks and check if the sum of the chunks > matches the checksum. If not, they rehash the message with new randomness > until they have found the randomness that results in the correct checksum. > > There is also some more recent work that promises "20% to 40% improvement in > the verification cost of the signature" [1]. However, I have not read the > paper and the increase in Bitcoin Script size may eat up theoretical > reductions in verification cost. > > > I believe my construction improves on Jonas', on two counts: [...] My > > > script results in much smaller witnesses. 8kb vs 24kb. > > > I think the size difference largely comes from the fact that my > implementation [2] is based on W-OTS+ [3] and not on W-OTS. The main > difference is that W-OTS relies on some variant of collision-resistance of > the hash function, whereas W-OTS+ only relies on the weaker preimage > resistance property. W-OTS+ is also standardized as part of XMSS [4] in the > form of a variant that was proven secure a little later [5]. > > However, using just W-OTS and therefore relying on collision-resistance seems > okay because Bitcoin already relies on collision-resistance of SHA256. If that > property was broken, the blockchain and the transaction Merkle tree would not > provide integrity anymore, resulting in chain splits. Therefore, I suggested [6] > to change my implementation to a Winternitz variant that does rely on > collision-resistance and whose Blockchain footprint is smaller. So far, no one > has implemented that, but it would certainly be very interesting to see if a > Great Script Restoration based implementation can significantly improve over > your implementation. > > [0] https://eprint.iacr.org/2025/055.pdf > [1] https://eprint.iacr.org/2025/889.pdf > [2] https://github.com/jonasnick/GreatRSI > [3] https://eprint.iacr.org/2017/965.pdf > [4] https://datatracker.ietf.org/doc/html/rfc8391 > [5] https://tches.iacr.org/index.php/TCHES/article/download/8730/8330/5451 > [6] https://github.com/jonasnick/GreatRSI/issues/1#issuecomment-2548062773 > > -- > 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/c2abfd68-f118-4951-ba4a-499fc819332f%40gmail.com. -- 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/Um1180WhyfREJS4CHTfTCzAuDywzNlFlsaIFFwLEGcETcwKCDuJMgSwSs4idfqgCDqtMTuc4FUmcTHWnK2z_tzxw8bdVD9zDiGTCfdbJFjs%3D%40proton.me. -----------------------3a31977699c472b1d663e8a288ff6a85 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== -----------------------3a31977699c472b1d663e8a288ff6a85-- --------28181ae1678496ea12aabdba076df9e0cf71568ee8a80cb5a8fb81e19c0c5be8 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmhsawcJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmeD886WrELY5HiUHvNxUtRGD4+lyjraSmF6JckY hScGWBYhBEdIka0CMtrLdg13a3gpbO2E9rPFAAChegD/UtcY3O+eWTowLmdq 1p1WLz0heJzZTSxJkBbg4HrmQkgBAPUlkdvD/BXHdEx5mQ2MCnf9N+GsG71Q 3RDUTLCTTTYA =9pmx -----END PGP SIGNATURE----- --------28181ae1678496ea12aabdba076df9e0cf71568ee8a80cb5a8fb81e19c0c5be8--