From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 01 Nov 2025 11:02:38 -0700 Received: from mail-oo1-f58.google.com ([209.85.161.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 1vFFvx-0000ih-GV for bitcoindev@gnusha.org; Sat, 01 Nov 2025 11:02:38 -0700 Received: by mail-oo1-f58.google.com with SMTP id 006d021491bc7-654fa531042sf4302538eaf.1 for ; Sat, 01 Nov 2025 11:02:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1762020151; x=1762624951; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:sender:from:to:cc:subject:date :message-id:reply-to; bh=O6s0xdULlCnczElgq0SrC68uLK2I/Y/Oe9ZBdDsqRj8=; b=QYaMUvUHklnjYFcSdjJw6pZkhSFYzyFUVRMRECWOQ7Iq3jp6mpST36lM/Axu9z79Uh 5+11h90BJ2Zbmw6mhsrHp5kvqUgXufXoYOhlq9ekEPLwUpYBPRpn3xWwWjpAUjQCAi9J gjjbBnXZ/VnRTOIh3VFYiT6H8AjRw1lWAg0f3c3pkBuF2pHg8GSTiXka4vyKq7C9F4TA q/NquoeHJwfk7cv1Pm/nIy7y2vCcnjw9jz/MhSF1uI5rGiNXzjUnQhUjmK1ay6bOXEBO D/ypdaz/I0CYMVSDImv/7Z4KhjkRRRyZv8N1xdrqJKSt1hlM0EjoEjtchO2djoFDUijy 8r9A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1762020151; x=1762624951; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:from:to:cc:subject:date:message-id :reply-to; bh=O6s0xdULlCnczElgq0SrC68uLK2I/Y/Oe9ZBdDsqRj8=; b=XDyNDETKHEZ6nuoV+HlF8H5br+nUILNW7+ZfW8zFbk4oZEz/g5pOrsztJu2UJe8QEh t8a+6YphRUHRshjSZGZHT3sUd194p87MwIOrcG5fCkZR33uCdW+l48UaSkoEgCpxdLEj B/ZOu1IR/FRETgrzy4WaEmZ/4Ytdm/3IkKDw+0c3kFlkNjnrJCAZtnzCyeYyxQjbb5aw +zQ38WQnrKe6TTI8mpmZka7dVdHtdD8HfWpj/GBQZ7zzCmm9yyOyO8WO2uZJaBIjK1VL Y3Q3Wv1/MbLDpOUPlNIgoRhv3DltI6Tj6mHyKhR735AbZz1N993KpYs06z0ajSkROfWE Vu1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762020151; x=1762624951; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=O6s0xdULlCnczElgq0SrC68uLK2I/Y/Oe9ZBdDsqRj8=; b=Azx9CU5NhV7E5FYiVY9MHgFjcvUixEt/05Nra++RU0CxQsNKXqqlayH76Qe9NIN0Ep 5AhR3H0fLIL97KZLQTyqOsAnldPn15fwD5A+hI/DYCxygpzd07PSDXoECRsDd0eiPPCn Cq0w7zGeaQbQ2vUWB6z2NBcbpXjQlJWLFeHGP0CXeKHuR4ZOJaIb1e5nW+9hht+cXK0K 5psEw+YCO+ylXOi7LTN/kMgJrJXXuI/YXHMyzrzQb/1cBXHdkJ1pTx3/p1iZRQNxOcce iAVGi2nE2yFqjLMA38HX2ldz2BhG8VgLe/z0MEA9rsGPK77ZogQqIN1obFdm28YrPwoH P7pQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCU+35UbwVm9NxGXSUQh3/0Kjm1w/5HAAOoZeaTts1/f5HBE9GXbvQ6w0ZMPA1sNXYqvIc4ZchhAezlP@gnusha.org X-Gm-Message-State: AOJu0YwWHeNPpgWuB/mOjpcM0Xx82pNehJGmTwSPoN0aWDLoCqAKhGKS gSpuUgE5f8CMrZI3PpINxGgtV++GxoQwdzxmGLR7DJ9+VZvb8RM230fm X-Google-Smtp-Source: AGHT+IGPMoDN40K5/d4t1VkiFs2PyF+CvNDDXh3f/JOUFuXvkrsYJvBFGEb+fsR4BLdzLYOl8fEJHA== X-Received: by 2002:a05:6871:10a:b0:3c9:415b:a28a with SMTP id 586e51a60fabf-3daca51445bmr3711279fac.11.1762020151083; Sat, 01 Nov 2025 11:02:31 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+Y8QFaf5fU/dHgGVdMryXSZ4nAmRtgQhmtM7bps98XMtQ==" Received: by 2002:a05:6870:5cce:b0:3d4:b99b:c1e1 with SMTP id 586e51a60fabf-3d8be3da1d6ls1773619fac.2.-pod-prod-07-us; Sat, 01 Nov 2025 11:02:25 -0700 (PDT) X-Received: by 2002:a05:6808:3c43:b0:44d:aa6b:a59a with SMTP id 5614622812f47-44f95e36555mr3792960b6e.10.1762020145072; Sat, 01 Nov 2025 11:02:25 -0700 (PDT) Received: by 2002:a05:690c:dc1:b0:785:e55d:2dfd with SMTP id 00721157ae682-78649982b58ms7b3; Sat, 1 Nov 2025 10:11:25 -0700 (PDT) X-Received: by 2002:a05:690c:6d0e:b0:786:5379:afa0 with SMTP id 00721157ae682-7865379b329mr54301017b3.7.1762017085068; Sat, 01 Nov 2025 10:11:25 -0700 (PDT) Date: Sat, 1 Nov 2025 10:11:24 -0700 (PDT) From: Tadge Dryja To: Bitcoin Development Mailing List Message-Id: <05195086-ee52-472c-962d-0df2e0b9dca2n@googlegroups.com> Subject: [bitcoindev] OP_CIV - Post-Quantum Signature Aggregation MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_221046_2035362027.1762017084762" X-Original-Sender: rx@awsomnet.org 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.7 (/) ------=_Part_221046_2035362027.1762017084762 Content-Type: multipart/alternative; boundary="----=_Part_221047_1538654601.1762017084762" ------=_Part_221047_1538654601.1762017084762 Content-Type: text/plain; charset="UTF-8" Hello- Here's an idea for Post-Quantum cross-input signature aggregation. It's not quite "signature aggregation" the way we normally think of it, but gives similar benefits while not being tied to a particular signature scheme. Folks have discussed Cross-input signature aggregation (CISA) in Bitcoin a while now, and while related research such as MuSig2, FROST, and ROAST have been implemented in wallets, so far there is no consensus change in bitcoin to enable CISA. My hunch is that one of the reasons this hasn't been adopted is that the space savings aren't that large. With taproot outputs, signatures are 64 bytes, and discounted to 16 vBytes. https://github.com/BlockstreamResearch/cross-input-aggregation/blob/master/savings.org shows a 7.1% vByte savings using full aggregation. Signatures just aren't that big of a part of the transaction, especially after the 75% segwit discount. One place where the size of signatures *is* a problem is with post-quantum signatures. The two most discussed PQ signature schemes, SPHINCS+ and CRYSTALS-Dilithium, both have pubkey+signature sizes in the kilobytes range. This would be a great opportunity for CISA, since even with a 75% witness discount, signatures would cost over 90% of the vBytes in a transaction. Unfortunately all the great EC based signature aggregation tools people have built don't work for lattices and hash-based signatures. Here's a way to get some of the same effects which would work with any signature type (including EC signatures, but if you've got EC signatures, existing CISA techniques are much better). I'm not attached to the name but for people familiar with bitcoin, the easiest to understand would be OP_CIV or OP_CHECKINPUTVERIFY. The basic idea is that a transaction input can prove a linkage to another input within the same transaction, and by pointing to another input say "that's the signature I'm using", without providing one of its own. Take for example a transaction with 2 inputs: input 0 and input 1. Input 0 has a normal (perhaps PQ) SIGHASH_ALL signature. Input 1 has a proof pointing to input 0. Since input 0 exists within the transaction, input 1 is valid. The arguments and usage of the would be: Where is the input number in the current transaction being validated to look. If this stack element isn't a number, or the number exceeds the number of inputs in the transaction, the opcode fails. and together form the outpoint, or UTXO identifier to look for at the location. If these two stack elements are malformed, or the resulting outpoint does not match the outpoint seen in the transaction, the opcode fails. is popped off the stack and discarded. It can be OP_0, but random bytes here can protect privacy. After an output is spent revealing the taptree, someone could try to grind through other possible outpoints to see if they show up elsewhere in the tree, trying to assign UTXOs to the same owner. This nonce would prevent such an attack. That's pretty much it for script evaluation. The idea would be that a taproot tree would have at the root a "normal" pubkey capable of creating arbitrary signatures. Lower down in the tree, there would be several / many OP_CIV scripts, each one pointing to a different outpoint. When a UTXO is being spent, if it is being spent in the same transaction as any of the UTXOs pointed to by the OP_CIV scripts, one of those can be revealed instead of supplying a signature. At least one input in a transaction would have a normal signature; it's not possible for every input in a transaction to use OP_CIV since that would require a hash cycle. For the wallet side implementation, every time a wallet generates a new address, it looks up some or all of the current UTXOs in the wallet, and adds a branch for each of them in the taproot tree. The wallet adds blinding data to each OP_CIV script to prevent an attacker from being able to guess other UTXO linkages other than those explicitly revealed. The last argument, , is left empty in the script and supplied at spending time. To avoid the need to generate and store additional entropy, the wallet can generate the blinding data deterministically, using the root pubkey's private key and the outpoint being pointed to, somewhat like the use of RFC6979 for ECDSA nonces. (Eg nonce = hash(private_key, outpoint)). Wallets constructed in such a way would often only need 1 signature per transaction, as all other UTXOs could point to the oldest input in the transaction. This savings doesn't work when a new wallet generates many addresses at once, and then over time coins are sent to those addresses. In that case a wallet would end up with a number of UTXOs which don't point to each other. Those UTXOs would all need to sign, but they might be paired with later UTXOs which point to them. Deterministic key wallets One complication is key recovery for deterministic wallets. If only the master key / seed phrase is known, all the root pubkeys can be recovered, but the wallet has "forgotten" which pubkeys point to which UTXOs. Deterministic nonces make recovery possible, but in a naive implementation, there would be an exponential blowup if when addresses are created they point to all existing UTXOs in the wallet. There are several workarounds, such as limiting the number of OP_CIV scripts in the tree to eg 10 (resulting in a ~1000X slowdown in recovery while maintaining a good chance of OP_CIV use), or including OP_CIV scripts pointing to all TXOs that the wallet knows have already been spent, increasing taptree size but reducing the number of guesses needed for recovery. Address re-use and replay attacks I don't think replay attacks are too much of a problem here. I thought it might be, but OP_CIV points to outpoints, not addresses or keys, so address reuse for the UTXOs being pointed to shouldn't matter. For address re-use with addresses that have OP_CIV scripts in them, replay attacks are avoided by using SIGHASH_ALL in the input that does sign, so that even if an attacker learns the full taptree of all the UTXOs of a wallet, they can't construct or modify a transaction without the ability to sign. Other uses There might be other contract use cases for such an opcode even today. I haven't come up with one, but it gives a tool where you can reveal a secret (a spend path & nonce) that allows someone to take a UTXO, but only if they already control a different specified UTXO. I think it's mostly useful for making PQ transactions smaller, but transaction introspection opcodes often have interesting use cases and OP_CIV may as well Real life example of OP_CIV commitments I gave a talk about this at TABConf a couple weeks ago; I was hoping to have sent this writeup out before the talk but didn't have time. That means that my TABConf talk was not able to link to this mailing list post. But that also means that this mailing list post is able to link to the TABConf talk: https://www.youtube.com/watch?v=cqjo3rmd6hY. Wonder if anyone has ideas / improvements / downsides to this idea. Thanks for any feedback! -Tadge -- 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/05195086-ee52-472c-962d-0df2e0b9dca2n%40googlegroups.com. ------=_Part_221047_1538654601.1762017084762 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello-

Here's an idea for Post-Quantum cross-input signature agg= regation. =C2=A0It's not quite "signature aggregation" the way we normally = think of it, but gives similar benefits while not being tied to a particula= r signature scheme.
=C2=A0
Folks have discussed Cross-i= nput signature aggregation (CISA) in Bitcoin a while now, and while related= research such as MuSig2, FROST, and ROAST have been implemented in wallets= , so far there is no consensus change in bitcoin to enable CISA. =C2=A0My h= unch is that one of the reasons this hasn't been adopted is that the space = savings aren't that large. =C2=A0With taproot outputs, signatures are 64 by= tes, and discounted to 16 vBytes. =C2=A0https://github.com/BlockstreamResea= rch/cross-input-aggregation/blob/master/savings.org shows a 7.1% vByte savi= ngs using full aggregation. =C2=A0Signatures just aren't that big of a part= of the transaction, especially after the 75% segwit discount.
One place where the size of signatures *is* a problem is wit= h post-quantum signatures.=C2=A0 The two most discussed PQ signature scheme= s, SPHINCS+ and CRYSTALS-Dilithium, both have pubkey+signature sizes in the= kilobytes range. =C2=A0This would be a great opportunity for CISA, since e= ven with a 75% witness discount, signatures would cost over 90% of the vByt= es in a transaction.

Unfortunately all the great= EC based signature aggregation tools people have built don't work for latt= ices and hash-based signatures. =C2=A0Here's a way to get some of the same = effects which would work with any signature type (including EC signatures, = but if you've got EC signatures, existing CISA techniques are much better).= =C2=A0I'm not attached to the name but for people familiar with bitcoin, t= he easiest to understand would be OP_CIV or OP_CHECKINPUTVERIFY.
=
The basic idea is that a transaction input can prove a lin= kage to another input within the same transaction, and by pointing to anoth= er input say "that's the signature I'm using", without providing one of its= own. =C2=A0Take for example a transaction with 2 inputs: input 0 and input= 1. =C2=A0Input 0 has a normal (perhaps PQ) SIGHASH_ALL signature. =C2=A0In= put 1 has a proof pointing to input 0. =C2=A0Since input 0 exists within th= e transaction, input 1 is valid.

The arguments a= nd usage of the would be:

<input_index> <output_index&g= t; <txid> <nonce> <OP_CIV>

Where <input_in= dex> is the input number in the current transaction being validated to l= ook. =C2=A0If this stack element isn't a number, or the number exceeds the = number of inputs in the transaction, the opcode fails.

<outpu= t_index> and <txid> together form the outpoint, or UTXO identifier= to look for at the <input_index> location. =C2=A0If these two stack = elements are malformed, or the resulting outpoint does not match the outpoi= nt seen in the transaction, the opcode fails.

<nonce> is p= opped off the stack and discarded. =C2=A0It can be OP_0, but random bytes h= ere can protect privacy. =C2=A0After an output is spent revealing the taptr= ee, someone could try to grind through other possible outpoints to see if t= hey show up elsewhere in the tree, trying to assign UTXOs to the same owner= . =C2=A0This nonce would prevent such an attack.

That's pretty m= uch it for script evaluation.

The idea would be that a taproot t= ree would have at the root a "normal" pubkey capable of creating arbitrary = signatures. =C2=A0Lower down in the tree, there would be several / many OP_= CIV scripts, each one pointing to a different outpoint. =C2=A0When a UTXO i= s being spent, if it is being spent in the same transaction as any of the U= TXOs pointed to by the OP_CIV scripts, one of those can be revealed instead= of supplying a signature. =C2=A0At least one input in a transaction would = have a normal signature; it's not possible for every input in a transaction= to use OP_CIV since that would require a hash cycle.

For the wa= llet side implementation, every time a wallet generates a new address, it l= ooks up some or all of the current UTXOs in the wallet, and adds a branch f= or each of them in the taproot tree. =C2=A0The wallet adds blinding data to= each OP_CIV script to prevent an attacker from being able to guess other U= TXO linkages other than those explicitly revealed. =C2=A0The last argument,= <input_index>, is left empty in the script and supplied at spending = time. =C2=A0To avoid the need to generate and store additional entropy, the= wallet can generate the blinding data deterministically, using the root pu= bkey's private key and the outpoint being pointed to, somewhat like the use= of RFC6979 for ECDSA nonces. =C2=A0(Eg nonce =3D hash(private_key, outpoin= t)).

Wallets constructed in such a way would often only need 1 s= ignature per transaction, as all other UTXOs could point to the oldest inpu= t in the transaction. =C2=A0This savings doesn't work when a new wallet gen= erates many addresses at once, and then over time coins are sent to those a= ddresses. =C2=A0In that case a wallet would end up with a number of UTXOs w= hich don't point to each other. =C2=A0Those UTXOs would all need to sign, b= ut they might be paired with later UTXOs which point to them.

D= eterministic key wallets

One complication is key recovery for de= terministic wallets. =C2=A0If only the master key / seed phrase is known, a= ll the root pubkeys can be recovered, but the wallet has "forgotten" which = pubkeys point to which UTXOs. =C2=A0Deterministic nonces make recovery poss= ible, but in a naive implementation, there would be an exponential blowup i= f when addresses are created they point to all existing UTXOs in the wallet= . =C2=A0There are several workarounds, such as limiting the number of OP_CI= V scripts in the tree to eg 10 (resulting in a ~1000X slowdown in recovery = while maintaining a good chance of OP_CIV use), or including OP_CIV scripts= pointing to all TXOs that the wallet knows have already been spent, increa= sing taptree size but reducing the number of guesses needed for recovery.
Address re-use and replay attacks

I don't think repla= y attacks are too much of a problem here.=C2=A0 I thought it might be, but = OP_CIV points to outpoints, not addresses or keys, so address reuse for the= UTXOs being pointed to shouldn't matter. =C2=A0For address re-use with add= resses that have OP_CIV scripts in them, replay attacks are avoided by usin= g SIGHASH_ALL in the input that does sign, so that even if an attacker lear= ns the full taptree of all the UTXOs of a wallet, they can't construct or m= odify a transaction without the ability to sign.

Other uses

There might be other contract use cases for such an opcode even toda= y. =C2=A0I haven't come up with one, but it gives a tool where you can reve= al a secret (a spend path & nonce) that allows someone to take a UTXO, = but only if they already control a different specified UTXO. =C2=A0I think = it's mostly useful for making PQ transactions smaller, but transaction intr= ospection opcodes often have interesting use cases and OP_CIV may as well
Real life example of OP_CIV commitments

I gave a talk = about this at TABConf a couple weeks ago; I was hoping to have sent this wr= iteup out before the talk but didn't have time. =C2=A0That means that my TA= BConf talk was not able to link to this mailing list post. =C2=A0But that a= lso means that this mailing list post is able to link to the TABConf talk: = https://www.youtube.com/watch?v=3Dcqjo3rmd6hY.

Wonder if anyone = has ideas / improvements / downsides to this idea. =C2=A0Thanks for any fee= dback!
-Tadge

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/05195086-ee52-472c-962d-0df2e0b9dca2n%40googlegroups.com.
------=_Part_221047_1538654601.1762017084762-- ------=_Part_221046_2035362027.1762017084762--