From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 28 Nov 2025 11:05:50 -0800 Received: from mail-oi1-f187.google.com ([209.85.167.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 1vP3mu-0007Cv-ON for bitcoindev@gnusha.org; Fri, 28 Nov 2025 11:05:50 -0800 Received: by mail-oi1-f187.google.com with SMTP id 5614622812f47-450c9057874sf166688b6e.2 for ; Fri, 28 Nov 2025 11:05:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1764356742; x=1764961542; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :from:to:cc:subject:date:message-id:reply-to; bh=TTkUcWQWShGEtSYiaAzBrOLrvKtu3VHZ3ZQKnEnwoUg=; b=Uo27qVg+hDiy5sslNrJ58h+VcCOWazUqI6kB1PD6pDg0uFo88U3OrwZdbXLwLTYmbx ADaeUOdVRCHlWe0fcwjU6il6cJiDcSI5+eXZb1ajKhvNap0yjiquUxzh46Jn67nbtQjp fqngLAyWr4NqmZUZgkHJ6EF/7QGuZGi+7LGqTr9Bmc0W3jd7Emv+GTIm+eLoG3ismmOi UW6jrjrVA9MVnTlDMsfk+ohnYLXF0u+r7hOm61p66d2YiLM5yDefL/87BczTQWTy76io ya4rfJX6vRBggfTXjYYGE4JGKjnG+n0yVQg0trgEY7y9aI42zGXN1L2FRlPacQVPIzuI tdxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764356742; x=1764961542; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=TTkUcWQWShGEtSYiaAzBrOLrvKtu3VHZ3ZQKnEnwoUg=; b=xHdk9I4OGK2WRyiE/QFa/YIXoCCfODSqFeXUgv+zXEmPyF5bcC2gOaJZgZQjL/YvN8 TQJP2/QWJHWiNTY4N6I84gtdtH5ZRHoJcFq+rNBz5gx9keIkFutlS7ypZLW/F61Y+vIQ A3Ts8EArgnDPnJEL+EW3ZlioVgIsr1xX5CQrfzVe3ysO84iFSgBqEp3q+5iorUyHHuUD F3V3mrCD/mlsom8iP14m93pgZTxUe5CHtlnooxhDVRGhGmSgV84EgKmeTNAf6T0Bo1ag iQ5jicnF+VPPJoFGXLPndDO1+3U2Ta5530hLro9G/ecQxl0gKrYqNUxCWBJ4XXZDm+Nv w2tA== X-Forwarded-Encrypted: i=1; AJvYcCUk6s+8F/IijmbeZFnIAlRSnMYZDcUmCFdiTb/KHAfmexTgzBoIRlC5yGnnstI0HoQ6g3m1dsSbcT7/@gnusha.org X-Gm-Message-State: AOJu0Yx2A13o+f28EN/Bo2XdCrI8P1qTm8MWSlCjDY/RTMBfFCGCIoeG /KVTq3Z/e/z9/CWIGIIHfKrKp3lcbb8kQv+hmXtb77XsFUnG01iNj+ct X-Google-Smtp-Source: AGHT+IHzUUqq7d7ZGc3vPesIYDqd+ki5Jj0r9M5qDlJAX96TBDlrPHaSCxcRaBgkOPpMDBm/G+qpzQ== X-Received: by 2002:a05:6870:e0d1:b0:3c9:8985:2b70 with SMTP id 586e51a60fabf-3ecc3db84d4mr7578809fac.8.1764356742322; Fri, 28 Nov 2025 11:05:42 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+a0HmpwRcuIS/qifkHpG+MIjaSlRTX0RnAN0zEO9U7y8A==" Received: by 2002:a05:6870:184e:b0:3e8:4817:7a50 with SMTP id 586e51a60fabf-3f0d1f7cba3ls1160944fac.0.-pod-prod-05-us; Fri, 28 Nov 2025 11:05:37 -0800 (PST) X-Received: by 2002:a05:6808:1a19:b0:44f:6d70:45af with SMTP id 5614622812f47-451159c79ddmr10169582b6e.9.1764356737006; Fri, 28 Nov 2025 11:05:37 -0800 (PST) Received: by 2002:a81:fb03:0:b0:786:8d90:70d8 with SMTP id 00721157ae682-78ac3365063ms7b3; Fri, 28 Nov 2025 10:52:28 -0800 (PST) X-Received: by 2002:a05:690e:2112:b0:63f:9d85:4dd5 with SMTP id 956f58d0204a3-64302ad80edmr14923273d50.60.1764355947398; Fri, 28 Nov 2025 10:52:27 -0800 (PST) Date: Fri, 28 Nov 2025 10:52:27 -0800 (PST) From: "'conduition' via Bitcoin Development Mailing List" To: Bitcoin Development Mailing List Message-Id: <02e3cb64-50e8-4814-bf53-72db87deafc8n@googlegroups.com> In-Reply-To: References: <05195086-ee52-472c-962d-0df2e0b9dca2n@googlegroups.com> <19701913-9225-45b3-8a2c-d620c53d8873n@googlegroups.com> Subject: Re: [bitcoindev] OP_CIV - Post-Quantum Signature Aggregation MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1231592_1068747594.1764355947077" X-Original-Sender: conduition@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 (-) ------=_Part_1231592_1068747594.1764355947077 Content-Type: multipart/alternative; boundary="----=_Part_1231593_1554968221.1764355947077" ------=_Part_1231593_1554968221.1764355947077 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hey Tadge, You're right that OP_CIV would discourage address reuse, but it'd also make= =20 life difficult for wallet developers who want to adopt it. Some wallet devs= =20 *today* don't even bother with multi-address support, so imagine if to do= =20 so effeciently, they needed to statefully track prior UTXOs and generate=20 addresses based on a changing UTXO set over time. Also I want to mention, there's a big privacy difference between these CISA= =20 techniques, and CISA via address reuse.=20 If I receive two payments to the same address, i immediately reveal that=20 those UTXOs are owned by the same entity: me. If I receive two payments to *distinct* addresses which are linked via your= =20 OP_CIV (or via my idea by committing to pubkeys) then I can choose when and= =20 whether to reveal the fact that those UTXOs are commonly owned. Most user= =20 wallets have more than just two UTXOs, so in a setting where I have=20 possibly dozens of UTXOs, this offers me more flexibility with respect to= =20 my on-chain privacy, allowing me to choose when and how to reveal common=20 UTXO ownership. This is kind of already the status quo, because chainalysis= =20 uses common-input ownership heuristics even if they are flawed/incorrect,= =20 just for the sake of having a "working" tool they can sell. Regarding the extra cost, we can quantify that! Let's say we have a taptree= =20 of height `h` with `2^h` leaves. We use one leaf for a unique pubkey, and= =20 the other `2^h - 1` tap leaves store commitments to other pubkeys or to=20 pre-existing UTXOs. To spend a TX with `n` inputs using this CISA paradigm,= =20 we need one signature, plus `n - 1` taproot control blocks and tapscripts.= =20 Each control block has size `h * 32`, plus ~32 bytes to reference the other= =20 pubkey or UTXO in the locking tapscript. So in total, the witness size=20 scales as: `(n - 1)((h + 1) * 32)`. In other words, for every additional=20 input covered by the CISA scheme, we must pay for roughly `(h + 1) * 32`=20 extra witness bytes. For example, with `h =3D 8`, we get taptrees which cov= er=20 at most 255 CISA commitments, and adding inputs covered by CISA costs=20 roughly 288 witness bytes per input. Comparatively, the smallest ML-DSA=20 parameter set's signature+pubkey tuple is 3732 bytes. regards, conduition On Sunday, November 2, 2025 at 11:27:51=E2=80=AFAM UTC-8 adiabat wrote: > Hi Conduition & Boris- > > (I wrote a response yesterday but it's gone, I think I used the google > groups interface instead of the e-mail client... anyway if a similar / > duplicate response ends up on this mailing list, oops) > > I agree that using "addresses" (scriptPubKeys) (yeah I know they're > not quite the same thing but close enough :) ) instead of outpoints > would probably work, and would have some advantages. But I lean > towards using outpoints mostly for privacy reasons. > > It seems that if you're OK with having 1 address link to another > address, then an obvious optimization would be to have the addresses > implicitly linked to themselves. So if a transaction has 2 inputs, > both with the same scriptPubKey, only 1 of them needs to sign. Why > bother sending and verifying 2 signatures from the same key? > > But if you do implement that, then the incentive for all wallets is to > just use 1 address. Because not only is it simpler, it's also > cheaper. > > Part of why I like linking to outpoints is that it disincentivizes > address re-use. If you just keep using the same address many times, > you can't use OP_CIV, and can't get any fee savings through it. If > instead you generate a new address each time you need one, and that > address commits to some / most of your UTXOs at the time, then you can > use OP_CIV and will have lower fees when spending. You could, in > theory, use the same root pubkey and *only* change which OP_CIV > branches you add, but that seems like a bad idea: if you're changing > the address anyway, why not change the pubkey. > > A related reason is that in SPHINCS+ and other hash-based signature > designs, one of the most important parameters is how many times a > pubkey can be re-used before becoming insecure. Since in bitcoin we > tend to want to discourage address re-use, it makes sense to reduce > that parameter, which would give smaller, faster to verify signatures, > at the cost of not allowing many instances of address re-use. > > These are somewhat subjective reasons, and I agree that in terms of > coding a wallet to do this stuff, having addresses point to each other > is probably easier than having addresses point to outpoints. I think > the privacy gains could be worth using outpoints, but even then, maybe > there's a better way that can really preserve privacy, and be used > with coinjoin transactions. (OP_CIV maybe could but only with > multisig outputs set up beforehand, which seems impractical.) > > Thanks for feedback on this & I will also keep looking at it > > -Tadge > > > > > > > > On Sat, Nov 1, 2025 at 9:45=E2=80=AFPM Boris Nagaev wr= ote: > > > > Hi Tadge, Conduition, and all, > > > > I think Conduition's stateless take can go a little further with a=20 > simple indexing trick. Give every address a monotonic index i, and from t= he=20 > seed derive a long sequence of shared keys K_0, K_1, .... When we create= =20 > address i, we add taproot leaves for K_i through K_{i+N-1}. That is a=20 > sliding window of size N. > > > > When a spend gathers a set of our inputs, let i_min be the smallest=20 > index and i_max the largest. If i_max - i_min < N, every input already ha= s=20 > a leaf for K_{i_max}, so we reveal that leaf everywhere and sign once und= er=20 > K_{i_max}. No state needed: the rule is deterministic. > > > > Because an index i is spent only once, the first spend that touches it= =20 > is the only transaction that ever reveals K_i. Backups stay simple too: a= ny=20 > device with the master seed can recompute the indices and shared keys=20 > without knowing past wallet state, as long as it knows N. > > > > Larger N means more leaves per address but keeps aggregation working=20 > across older UTXOs. Wallets that need giant sweeps can still consolidate= =20 > inside windows. The number of full signatures in a transaction is the=20 > number of windows inputs belong to. > > > > Curious whether this sounds workable. > > > > Best, > > Boris > > > > On Saturday, November 1, 2025 at 8:09:52=E2=80=AFPM UTC-3 conduition wr= ote: > > > > Neat idea! The need to commit each script pubkey to other prevouts in= =20 > the TX would probably hold the concept back from being practical,=20 > especially for deterministic backup wallets which is likely the bulk of= =20 > modern Bitcoin usage. I could imagine offline/hardware wallets having a= =20 > very tough time with this. > > > > Consider a more conservative (but also very common) use case:=20 > Aggregating inputs controlled by the same owner. In this context, what th= e=20 > sender is really trying to prove here isn't whether UTXO A committed to= =20 > UTXO B. For signature aggregation across commonly-owned inputs, they just= =20 > need to be able to prove that UTXO A and UTXO B are spendable under the= =20 > same pubkey, and that they, the pubkey owner, authorized both of them via= a=20 > single signature. > > > > So instead of committing a taptree to pre-existing UTXOs (which creates= =20 > statefulness), you could commit a taptree to a deterministic set of=20 > pubkeys, such as "the nearest 100 addresses in the same BIP32 account". A= t=20 > spending time, we reveal the same pubkey's script leaf on all inputs, plu= s=20 > a signature that covers all the inputs. This would allow stateless addres= s=20 > generation, while also allowing a single signature to cover all common=20 > inputs in a wallet. > > > > This would have pretty bad effects on UTXO privacy, because the=20 > common-owner heuristic would become even stronger and would be provable= =20 > on-chain, but OP_CIV would also likely have a similar effect on chain=20 > forensics. Maybe the fee savings would be worth it, esp for big exchanges= =20 > which consolidate hundreds or thousands of UTXOs at a time. > > > > -conduition > > On Saturday, November 1st, 2025 at 2:02 PM, Tadge Dryja < > r...@awsomnet.org> wrote: > > > > Hello- > > > > Here's an idea for Post-Quantum cross-input signature aggregation. It's= =20 > not quite "signature aggregation" the way we normally think of it, but=20 > gives similar benefits while not being tied to a particular signature=20 > scheme. > > Folks have discussed Cross-input signature aggregation (CISA) in Bitcoi= n=20 > a while now, and while related research such as MuSig2, FROST, and ROAST= =20 > have been implemented in wallets, so far there is no consensus change in= =20 > bitcoin to enable CISA. My hunch is that one of the reasons this hasn't= =20 > been adopted is that the space savings aren't that large. With taproot=20 > outputs, signatures are 64 bytes, and discounted to 16 vBytes.=20 > https://github.com/BlockstreamResearch/cross-input-aggregation/blob/maste= r/savings.org=20 > shows a 7.1% vByte savings using full aggregation. Signatures just aren't= =20 > that big of a part of the transaction, especially after the 75% segwit=20 > discount. > > > > One place where the size of signatures *is* a problem is with=20 > post-quantum signatures. The two most discussed PQ signature schemes,=20 > SPHINCS+ and CRYSTALS-Dilithium, both have pubkey+signature sizes in the= =20 > kilobytes range. This would be a great opportunity for CISA, since even= =20 > with a 75% witness discount, signatures would cost over 90% of the vBytes= =20 > in a transaction. > > > > Unfortunately all the great EC based signature aggregation tools people= =20 > have built don't work for lattices and hash-based signatures. Here's a wa= y=20 > to get some of the same effects which would work with any signature type= =20 > (including EC signatures, but if you've got EC signatures, existing CISA= =20 > techniques are much better). I'm not attached to the name but for people= =20 > familiar with bitcoin, the easiest to understand would be OP_CIV or=20 > OP_CHECKINPUTVERIFY. > > > > The basic idea is that a transaction input can prove a linkage to=20 > another input within the same transaction, and by pointing to another inp= ut=20 > say "that's the signature I'm using", without providing one of its own.= =20 > Take for example a transaction with 2 inputs: input 0 and input 1. Input = 0=20 > has a normal (perhaps PQ) SIGHASH_ALL signature. Input 1 has a proof=20 > pointing to input 0. Since input 0 exists within the transaction, input 1= =20 > is valid. > > > > The arguments and usage of the would be: > > > > > > > > Where is the input number in the current transaction bein= g=20 > validated to look. If this stack element isn't a number, or the number=20 > exceeds the number of inputs in the transaction, the opcode fails. > > > > and together form the outpoint, or UTXO identifie= r=20 > to look for at the location. If these two stack elements ar= e=20 > malformed, or the resulting outpoint does not match the outpoint seen in= =20 > the transaction, the opcode fails. > > > > is popped off the stack and discarded. It can be OP_0, but=20 > random bytes here can protect privacy. After an output is spent revealing= =20 > the taptree, someone could try to grind through other possible outpoints = to=20 > see if they show up elsewhere in the tree, trying to assign UTXOs to the= =20 > 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"= =20 > pubkey capable of creating arbitrary signatures. Lower down in the tree,= =20 > there would be several / many OP_CIV scripts, each one pointing to a=20 > different outpoint. When a UTXO is being spent, if it is being spent in t= he=20 > same transaction as any of the UTXOs pointed to by the OP_CIV scripts, on= e=20 > of those can be revealed instead of supplying a signature. At least one= =20 > input in a transaction would have a normal signature; it's not possible f= or=20 > every input in a transaction to use OP_CIV since that would require a has= h=20 > cycle. > > > > For the wallet side implementation, every time a wallet generates a new= =20 > address, it looks up some or all of the current UTXOs in the wallet, and= =20 > adds a branch for each of them in the taproot tree. The wallet adds=20 > blinding data to each OP_CIV script to prevent an attacker from being abl= e=20 > to guess other UTXO linkages other than those explicitly revealed. The la= st=20 > argument, , is left empty in the script and supplied at=20 > spending time. To avoid the need to generate and store additional entropy= ,=20 > the wallet can generate the blinding data deterministically, using the ro= ot=20 > pubkey's private key and the outpoint being pointed to, somewhat like the= =20 > use of RFC6979 for ECDSA nonces. (Eg nonce =3D hash(private_key, outpoint= )). > > > > Wallets constructed in such a way would often only need 1 signature per= =20 > transaction, as all other UTXOs could point to the oldest input in the=20 > transaction. This savings doesn't work when a new wallet generates many= =20 > addresses at once, and then over time coins are sent to those addresses. = In=20 > that case a wallet would end up with a number of UTXOs which don't point = to=20 > each other. Those UTXOs would all need to sign, but they might be paired= =20 > with later UTXOs which point to them. > > > > Deterministic key wallets > > > > One complication is key recovery for deterministic wallets. If only the= =20 > master key / seed phrase is known, all the root pubkeys can be recovered,= =20 > but the wallet has "forgotten" which pubkeys point to which UTXOs.=20 > Deterministic nonces make recovery possible, but in a naive implementatio= n,=20 > there would be an exponential blowup if when addresses are created they= =20 > point to all existing UTXOs in the wallet. There are several workarounds,= =20 > such as limiting the number of OP_CIV scripts in the tree to eg 10=20 > (resulting in a ~1000X slowdown in recovery while maintaining a good chan= ce=20 > of OP_CIV use), or including OP_CIV scripts pointing to all TXOs that the= =20 > wallet knows have already been spent, increasing taptree size but reducin= g=20 > 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= =20 > it might be, but OP_CIV points to outpoints, not addresses or keys, so=20 > address reuse for the UTXOs being pointed to shouldn't matter. For addres= s=20 > re-use with addresses that have OP_CIV scripts in them, replay attacks ar= e=20 > avoided by using SIGHASH_ALL in the input that does sign, so that even if= =20 > an attacker learns the full taptree of all the UTXOs of a wallet, they=20 > 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=20 > haven't come up with one, but it gives a tool where you can reveal a secr= et=20 > (a spend path & nonce) that allows someone to take a UTXO, but only if th= ey=20 > already control a different specified UTXO. I think it's mostly useful fo= r=20 > making PQ transactions smaller, but transaction introspection opcodes oft= en=20 > 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= =20 > have sent this writeup out before the talk but didn't have time. That mea= ns=20 > that my TABConf talk was not able to link to this mailing list post. But= =20 > that also means that this mailing list post is able to link to the TABCon= f=20 > talk: https://www.youtube.com/watch?v=3Dcqjo3rmd6hY. > > > > Wonder if anyone has ideas / improvements / downsides to this idea.=20 > Thanks for any feedback! > > -Tadge > > > > -- > > You received this message because you are subscribed to the Google=20 > Groups "Bitcoin Development Mailing List" group. > > To unsubscribe from this group and stop receiving emails from it, send= =20 > an email to bitcoindev+...@googlegroups.com. > > To view this discussion visit=20 > https://groups.google.com/d/msgid/bitcoindev/05195086-ee52-472c-962d-0df2= e0b9dca2n%40googlegroups.com > . > > > > > > -- > > You received this message because you are subscribed to the Google=20 > Groups "Bitcoin Development Mailing List" group. > > To unsubscribe from this group and stop receiving emails from it, send= =20 > an email to bitcoindev+...@googlegroups.com. > > To view this discussion visit=20 > https://groups.google.com/d/msgid/bitcoindev/19701913-9225-45b3-8a2c-d620= c53d8873n%40googlegroups.com > . > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 02e3cb64-50e8-4814-bf53-72db87deafc8n%40googlegroups.com. ------=_Part_1231593_1554968221.1764355947077 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hey Tadge,

You're right that OP_CIV would discourage a= ddress reuse, but it'd also make life difficult for wallet developers who w= ant to adopt it. Some wallet devs today=C2=A0don't even bother with = multi-address support, so imagine if to do so effeciently, they needed to s= tatefully track prior UTXOs and generate addresses based on a changing UTXO= set over time.

Also I want to mention, there's = a big privacy difference between these CISA techniques, and CISA via addres= s reuse.=C2=A0

If I receive two payments to the = same address, i immediately reveal that those UTXOs are owned by the same e= ntity: me.

If I receive two payments to distinct=C2=A0addresses which are linked via your OP_CIV (or via my id= ea by committing to pubkeys) then I can choose when and whether to reveal t= he fact that those UTXOs are commonly owned. Most user wallets have more th= an just two UTXOs, so in a setting where I have possibly dozens of UTXOs, t= his offers me more flexibility with respect to my on-chain privacy, allowin= g me to choose when and how to reveal common UTXO ownership. This is kind o= f already the status quo, because chainalysis uses common-input ownership h= euristics even if they are flawed/incorrect, just for the sake of having a = "working" tool they can sell.

Regarding the extr= a cost, we can quantify that! Let's say we have a taptree of height `h` wit= h `2^h` leaves. We use one leaf for a unique pubkey, and the other `2^h - 1= ` tap leaves store commitments to other pubkeys or to pre-existing UTXOs. T= o spend a TX with `n` inputs using this CISA paradigm, we need one signatur= e, plus `n - 1` taproot control blocks and tapscripts. Each control block h= as size `h * 32`, plus ~32 bytes to reference the other pubkey or UTXO in t= he locking tapscript. So in total, the witness size scales as: `(n - 1)((h = + 1) * 32)`. In other words, for every additional input covered by the CISA= scheme, we must pay for roughly `(h + 1) * 32` extra witness bytes. For ex= ample, with `h =3D 8`, we get taptrees which cover at most 255 CISA commitm= ents, and adding inputs covered by CISA costs roughly 288 witness bytes per= input. Comparatively, the smallest ML-DSA parameter set's signature+pubkey= tuple is 3732 bytes.

regards,
conduit= ion

On Sunday, November 2, 2025 at 11:27:51=E2=80=AFAM UTC-8 a= diabat wrote:
Hi Conduition & Boris-

(I wrote a response yesterday but it's gone, I think I used the goo= gle
groups interface instead of the e-mail client... anyway if a similar /
duplicate response ends up on this mailing list, oops)

I agree that using "addresses" (scriptPubKeys) (yeah I know t= hey're
not quite the same thing but close enough :) ) instead of outpoints
would probably work, and would have some advantages. But I lean
towards using outpoints mostly for privacy reasons.

It seems that if you're OK with having 1 address link to another
address, then an obvious optimization would be to have the addresses
implicitly linked to themselves. So if a transaction has 2 inputs,
both with the same scriptPubKey, only 1 of them needs to sign. Why
bother sending and verifying 2 signatures from the same key?

But if you do implement that, then the incentive for all wallets is to
just use 1 address. Because not only is it simpler, it's also
cheaper.

Part of why I like linking to outpoints is that it disincentivizes
address re-use. If you just keep using the same address many times,
you can't use OP_CIV, and can't get any fee savings through it.= If
instead you generate a new address each time you need one, and that
address commits to some / most of your UTXOs at the time, then you can
use OP_CIV and will have lower fees when spending. You could, in
theory, use the same root pubkey and *only* change which OP_CIV
branches you add, but that seems like a bad idea: if you're changin= g
the address anyway, why not change the pubkey.

A related reason is that in SPHINCS+ and other hash-based signature
designs, one of the most important parameters is how many times a
pubkey can be re-used before becoming insecure. Since in bitcoin we
tend to want to discourage address re-use, it makes sense to reduce
that parameter, which would give smaller, faster to verify signatures,
at the cost of not allowing many instances of address re-use.

These are somewhat subjective reasons, and I agree that in terms of
coding a wallet to do this stuff, having addresses point to each other
is probably easier than having addresses point to outpoints. I think
the privacy gains could be worth using outpoints, but even then, maybe
there's a better way that can really preserve privacy, and be used
with coinjoin transactions. (OP_CIV maybe could but only with
multisig outputs set up beforehand, which seems impractical.)

Thanks for feedback on this & I will also keep looking at it

-Tadge







On Sat, Nov 1, 2025 at 9:45=E2=80=AFPM Boris Nagaev <bna...@gmail.com> wrote:
>
> Hi Tadge, Conduition, and all,
>
> I think Conduition's stateless take can go a little further wi= th a simple indexing trick. Give every address a monotonic index i, and fro= m the seed derive a long sequence of shared keys K_0, K_1, .... When we cre= ate address i, we add taproot leaves for K_i through K_{i+N-1}. That is a s= liding window of size N.
>
> When a spend gathers a set of our inputs, let i_min be the smalles= t index and i_max the largest. If i_max - i_min < N, every input already= has a leaf for K_{i_max}, so we reveal that leaf everywhere and sign once = under K_{i_max}. No state needed: the rule is deterministic.
>
> Because an index i is spent only once, the first spend that touche= s it is the only transaction that ever reveals K_i. Backups stay simple too= : any device with the master seed can recompute the indices and shared keys= without knowing past wallet state, as long as it knows N.
>
> Larger N means more leaves per address but keeps aggregation worki= ng across older UTXOs. Wallets that need giant sweeps can still consolidate= inside windows. The number of full signatures in a transaction is the numb= er of windows inputs belong to.
>
> Curious whether this sounds workable.
>
> Best,
> Boris
>
> On Saturday, November 1, 2025 at 8:09:52=E2=80=AFPM UTC-3 conduiti= on wrote:
>
> Neat idea! The need to commit each script pubkey to other prevouts= in the TX would probably hold the concept back from being practical, espec= ially for deterministic backup wallets which is likely the bulk of modern B= itcoin usage. I could imagine offline/hardware wallets having a very tough = time with this.
>
> Consider a more conservative (but also very common) use case: Aggr= egating inputs controlled by the same owner. In this context, what the send= er is really trying to prove here isn't whether UTXO A committed to UTX= O B. For signature aggregation across commonly-owned inputs, they just need= to be able to prove that UTXO A and UTXO B are spendable under the same pu= bkey, and that they, the pubkey owner, authorized both of them via a single= signature.
>
> So instead of committing a taptree to pre-existing UTXOs (which cr= eates statefulness), you could commit a taptree to a deterministic set of p= ubkeys, such as "the nearest 100 addresses in the same BIP32 account&q= uot;. At spending time, we reveal the same pubkey's script leaf on all = inputs, plus a signature that covers all the inputs. This would allow state= less address generation, while also allowing a single signature to cover al= l common inputs in a wallet.
>
> This would have pretty bad effects on UTXO privacy, because the co= mmon-owner heuristic would become even stronger and would be provable on-ch= ain, but OP_CIV would also likely have a similar effect on chain forensics.= Maybe the fee savings would be worth it, esp for big exchanges which conso= lidate hundreds or thousands of UTXOs at a time.
>
> -conduition
> On Saturday, November 1st, 2025 at 2:02 PM, Tadge Dryja <r...@awsomnet.org> wrote:
>
> Hello-
>
> Here's an idea for Post-Quantum cross-input signature aggregat= ion. It's not quite "signature aggregation" the way we normal= ly think of it, but gives similar benefits while not being tied to a partic= ular signature scheme.
> Folks have discussed Cross-input signature aggregation (CISA) in B= itcoin a while now, and while related research such as MuSig2, FROST, and R= OAST 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= 9;t been adopted is that the space savings aren't that large. With tapr= oot 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 r= ange. This would be a great opportunity for CISA, since even with a 75% wit= ness discount, signatures would cost over 90% of the vBytes in a transactio= n.
>
> Unfortunately all the great EC based signature aggregation tools p= eople have built don't work for lattices and hash-based signatures. Her= e's a way to get some of the same effects which would work with any sig= nature 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 O= P_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 i= nput 1. Input 0 has a normal (perhaps PQ) SIGHASH_ALL signature. Input 1 ha= s 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:
>
> <input_index> <output_index> <txid> <nonce>= ; <OP_CIV>
>
> Where <input_index> is the input number in the current trans= action being validated to look. If this stack element isn't a number, o= r the number exceeds the number of inputs in the transaction, the opcode fa= ils.
>
> <output_index> and <txid> together form the outpoint, = or UTXO identifier to look for at the <input_index> location. If thes= e two stack elements are malformed, or the resulting outpoint does not matc= h the outpoint seen in the transaction, the opcode fails.
>
> <nonce> is popped off the stack and discarded. It can be OP_= 0, but random bytes here can protect privacy. After an output is spent reve= aling the taptree, someone could try to grind through other possible outpoi= nts 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 &qu= ot;normal" pubkey capable of creating arbitrary signatures. Lower down= in the tree, there would be several / many OP_CIV scripts, each one pointi= ng to a different outpoint. When a UTXO is being spent, if it is being spen= t in the same transaction as any of the UTXOs pointed to by the OP_CIV scri= pts, one of those can be revealed instead of supplying a signature. At leas= t one input in a transaction would have a normal signature; it's not po= ssible for every input in a transaction to use OP_CIV since that would requ= ire 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 bli= nding 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 ar= gument, <input_index>, is left empty in the script and supplied at sp= ending time. To avoid the need to generate and store additional entropy, th= e wallet can generate the blinding data deterministically, using the root p= ubkey's private key and the outpoint being pointed to, somewhat like th= e use of RFC6979 for ECDSA nonces. (Eg nonce =3D hash(private_key, outpoint= )).
>
> Wallets constructed in such a way would often only need 1 signatur= e per transaction, as all other UTXOs could point to the oldest input in th= e transaction. This savings doesn't work when a new wallet generates ma= ny 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 onl= y the master key / seed phrase is known, all the root pubkeys can be recove= red, but the wallet has "forgotten" which pubkeys point to which = UTXOs. Deterministic nonces make recovery possible, but in a naive implemen= tation, there would be an exponential blowup if when addresses are created = they point to all existing UTXOs in the wallet. There are several workaroun= ds, such as limiting the number of OP_CIV scripts in the tree to eg 10 (res= ulting 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 wall= et 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 att= acks 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, t= hey 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 to= day. I 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. I think it'= ;s mostly useful for making PQ transactions smaller, but transaction intros= pection 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 hopi= ng 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 p= ost. But that also 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= . 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+...@= googlegroups.com.
> To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/05195086-ee52-472c-962d-0df2e0b9dca= 2n%40googlegroups.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+...@= googlegroups.com.
> To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/19701913-9225-45b3-8a2c-d620c53d887= 3n%40googlegroups.com.

--
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/02e3cb64-50e8-4814-bf53-72db87deafc8n%40googlegroups.com.
------=_Part_1231593_1554968221.1764355947077-- ------=_Part_1231592_1068747594.1764355947077--