From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 07 Jul 2025 03:43:26 -0700 Received: from mail-qt1-f186.google.com ([209.85.160.186]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uYjJl-0004mU-Js for bitcoindev@gnusha.org; Mon, 07 Jul 2025 03:43:25 -0700 Received: by mail-qt1-f186.google.com with SMTP id d75a77b69052e-4a9764b4dc9sf70381201cf.2 for ; Mon, 07 Jul 2025 03:43:25 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1751884999; cv=pass; d=google.com; s=arc-20240605; b=E79FBwYzxhHSOPZpg70A71euMGlVnkujrdcHAwiIV5o0lF6PO+fzf+JrjHX/GkjQ1+ PpTvfFwolq5cunA/NRTCkfSVHoDXO0pGD/hOQ+aT72Q2EKvQHruKOoEw8QORoTYq9uPK y0vj66OZjrZqBPkLCcDjDTTqR/M0H6prSPBeTCZDsyXUJT+jiI8kDPwiO6UrMGwE+sWX SAHQopKa6S4ECgvITNkV/qxliGtRS0ZHMA6FEl5fFay7WMALor/gyD5m8VXWmddnhcsW fZ7RbzwKN2JJQJyLlv4UviGeIlehPZB9fmkDx+SOp8x1quJ9qEzRte9F2tiA9EFrcKGo ONfQ== 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:in-reply-to:from:content-language :references:to:subject:user-agent:mime-version:date:message-id :sender:dkim-signature; bh=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=; fh=VtNEVHVdlKz+f7W0vVYEBLsLb3zNYLHOVcWEodboUCY=; b=biucNY1+f7+iZfwIXtDth8ZmIC/jT6xt/hB3te+PUWoIz0EIJV9AiXULwWPBbHOZB0 mQ7LPlJdJkqaBZxkmaWRKc0v9a7UUmpHh09jE7RmDGBnOfwBY73LTdU83HDrpQ4avcR+ vlBkq80pK7ORvBqIfmVMEzsyNAhBS5aXXJuGuBGf3t4z0oTGFRghnrFzxhty/L/jfpja bgP/JDjNBVTBDJet419c8LqiaKIVJapgrKkez2pHg6lwbLgR3bg5cPoqcf3fYt1q+cLP vdEGZvX17FHkcxFC63DOLqUzOzPzlfD+TQqwoOn8lm3HKcHFYUb752r48ddWl7MIAvoJ l8gg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ckoXlurT; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1751884999; x=1752489799; 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:from:content-language:references:to :subject:user-agent:mime-version:date:message-id:sender:from:to:cc :subject:date:message-id:reply-to; bh=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=; b=mdtxZbKWd/c8sCNB1JBBvt34/1So8Dx3cbXlZ+PawtVWBdra9Iptbt0TcnJoQy5XRU ZXGZ80WBIRU3WjMuVJnI3RSOrinQiZgl8fGfj45vcYFcuyg6pcB3INLP1bNhhuSyvwww jj4DCE3gd2Xwk0VogKWnxetoO+wheRVNAA99GV+2TuflL9ZhHI4uHCm0XUF4Aa8UYwfP w26HFb1ua8fKK8mbbkl+hItJkenEFDgwlXPoMBu2QLbulHvs9HeMfWCYqoReqDGNCG5Y wTfk3r4ZI+dqZfskLqzsGm4aoKnRBoUdin8xClt9lQpaKL2fR3WQCZieEMezgEDuC52z i5+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1751884999; x=1752489799; 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:from:content-language:references:to :subject:user-agent:mime-version:date:message-id:sender:x-beenthere :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=; b=nCJg3Fq3xixR4n68VNxjeZ3puzz4tcKzENu7qXmtEBo0IpQmneV8OkeJ0NGh74G3tJ iBiV19w8lvlHmX9ngUF9roX6gKX4W/uZY1v+s1WR/j/Yuc6QAZho7Hm2o27iyq+xfWHQ DxEg+XlEwiipKVHcm6rxUpbhuD7dd4j+cO4o1oJ/S3mUxfB13XTh/lCBsZJFu8/94j0p C5PwL4FAOreoIAstNUB7PojShv9BE3I0zhj0YLdnGslokSPvbgP7XUn3b77PIiRhXXte r467gegJdr+M4uOIDntkiZyalWWyV4FDr+jRxXhDdeDcKzGnltEuST28OUw0MVFgE82t P6Gg== X-Forwarded-Encrypted: i=2; AJvYcCX0TzLrW4WNAxoXlKZcNxTwSxUPW0I3vVd5jZMjw9Fz1LpZP6O/bWcrRPSePj+RFilm5abYdzTTr1eV@gnusha.org X-Gm-Message-State: AOJu0YxTy226hd5MREXth4A5GtvdHXEqqciNSH5auwp2nAdiLoZAD72M JW170zpw6m5tftXuxSFmncpLjBNwOZbnGWBpG7AhtY7mFmX9y8ZjWdb+ X-Google-Smtp-Source: AGHT+IF3P76Yt9HQFDRohpSgsqv4G28Lh8ofWoaCzdz1JV51aTh10Meft6IKWkraUaxgCsjv+7Wanw== X-Received: by 2002:ac8:7d95:0:b0:4a7:5c51:cf5 with SMTP id d75a77b69052e-4a9987b05c2mr140636891cf.26.1751884998052; Mon, 07 Jul 2025 03:43:18 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcLBghtiJ63+9QIaYB8S19P9yOK74tDpdAZDt/SyCekzQ== Received: by 2002:a05:622a:50b:b0:4a5:a87e:51cf with SMTP id d75a77b69052e-4a99be502b0ls54920491cf.1.-pod-prod-07-us; Mon, 07 Jul 2025 03:43:13 -0700 (PDT) X-Received: by 2002:a05:620a:45a0:b0:7d4:4214:2cba with SMTP id af79cd13be357-7d5df1695cdmr1314689085a.40.1751884993779; Mon, 07 Jul 2025 03:43:13 -0700 (PDT) Received: by 2002:a05:6504:d91:b0:2b1:9626:e73d with SMTP id a1c4a302cd1d6-2b5fb63a227msc7a; Mon, 7 Jul 2025 03:40:38 -0700 (PDT) X-Received: by 2002:a05:6512:2104:b0:553:522f:61bb with SMTP id 2adb3069b0e04-557e5515b2emr1747271e87.12.1751884835579; Mon, 07 Jul 2025 03:40:35 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1751884835; cv=none; d=google.com; s=arc-20240605; b=C3S3CR+/bd/V5syfuoDo/0X1jqw+cGDh2J3j+hsrfIfmhVVlhdlHt/epj2ap5adeal JY5R/LC0rqgGVQjplopmHzJT+YnCWwDsH0NhdicOD9we0AGi4MW7aXrGROwWnKpRsBTm uYC0GPi65djQbQFOf/cCA/oGIVCnHZoFL1jmCCgsGKAXTGEh9OLcF+KyVeqB7CXVFi7X cpqkQ+fGtGn4kxmUYqGLYLJoZVRgs8GF/i1xPzfxm57E0H6lOqK0lBFFGLZqn9rObru3 Dw449XdIQr+vHZWla70ZSNUZ1lahwNGe63tV9PT3JhlJ1aMn3w5bKeF2YnUYvppZok/c WXOA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=content-transfer-encoding:in-reply-to:from:content-language :references:to:subject:user-agent:mime-version:date:message-id :sender:dkim-signature; bh=nIsG/c2qmGFhKMnXGC8sw3czuVmjz3qOppF9w+/Ya8s=; fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=; b=UKEBnJrfI+0B0AwpIzao62+g8G0P7D3iHKJn1fuhHu3FM5zMx2k/WwKohunMIVme9/ 4Ak1BmKutMZ6BEySczDF1dDazz85b5qMlxbUx6rS5MegHazHXZfAoXoqY36goszcSFHe uAWZjOw6OhyzW1QQi/Dd2YnfGBesGwnwpJ5ISY7ZJvVypvA3LZBfCZ3W+43Bm/EWerab i3aH04RGy9m3YG6WwDDoPD3uHKDD1KzDyozG3BxBZKRpF2D1uAS9LyxHRbKeRWyAj93l v769BtHIVuRymfKofAWeabOkrNIS7zZONK/BD+Hm2tFoY5GCMF1Ezhj+i+B6yrw5TsF2 y1DA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ckoXlurT; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com. [2a00:1450:4864:20::52f]) by gmr-mx.google.com with ESMTPS id 2adb3069b0e04-5563838e94dsi151778e87.1.2025.07.07.03.40.35 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Jul 2025 03:40:35 -0700 (PDT) Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f as permitted sender) client-ip=2a00:1450:4864:20::52f; Received: by mail-ed1-x52f.google.com with SMTP id 4fb4d7f45d1cf-607cf70b00aso5691449a12.2 for ; Mon, 07 Jul 2025 03:40:35 -0700 (PDT) X-Gm-Gg: ASbGncvq52L15MwHQO8VsBkY0O8QxlgjIWpt/pZEHYmQScOV3qN15m6Fg68Q/S2sr6W lizgAsxViQ1vDw9A+hRs/1CJpD/eKUvokyh4CdU1crWZshb6cjXeFd2XzPWut+b3xh+gcdafzuX IkT7WaGZmO1GYt4mwpRsm/RVQmaDezwUEhRdkIANtqOxTjuY3OPtXZ3OSVmeU1YGR3LSJEJtZYw CxD/kJjKU9OuJTTBaiGHF3/tnIVivWxo4vwfPgOi1Sbb7d1bnfV6V4tbZ5uMLQl9t7XQ3W43vsb ZmHuen+nRSjKFBjb+vbo89fmnyHk19OaT8qJJHHmZaJhUSnvxbtwRmSlfgMIBt8N5NxSgm/XMoO bqsZDKlDZLvExuHHrlXMGJENZPf4IIPNx5ZY= X-Received: by 2002:a05:6402:518d:b0:607:f63b:aa31 with SMTP id 4fb4d7f45d1cf-60ff38183b4mr7249477a12.6.1751884834491; Mon, 07 Jul 2025 03:40:34 -0700 (PDT) Received: from [192.168.1.55] (188-22-134-228.adsl.highway.telekom.at. [188.22.134.228]) by smtp.googlemail.com with ESMTPSA id 4fb4d7f45d1cf-60feaf48af3sm3846126a12.35.2025.07.07.03.40.32 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Jul 2025 03:40:33 -0700 (PDT) Sender: Jonas Nick Message-ID: Date: Mon, 7 Jul 2025 10:40:32 +0000 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures To: bitcoindev@googlegroups.com References: Content-Language: en-US From: Jonas Nick In-Reply-To: Content-Type: text/plain; charset="UTF-8"; format=flowed X-Original-Sender: jonasdnick@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ckoXlurT; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/) 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.