From: Boris Nagaev <bnagaev@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] OP_CIV - Post-Quantum Signature Aggregation
Date: Sat, 1 Nov 2025 18:34:45 -0700 (PDT) [thread overview]
Message-ID: <19701913-9225-45b3-8a2c-d620c53d8873n@googlegroups.com> (raw)
In-Reply-To: <kBNJjQ46doVAAXAOjzIoBdtX4UikDa2YCqKdPbzEK-QjbBUHdl2V_5T-Ay6Z76lnj5BHmrAWg9FS1eHT_PgJmoEFFuPkWt5i8LPEvY3wmKk=@proton.me>
[-- Attachment #1.1: Type: text/plain, Size: 11203 bytes --]
Hi Tadge, Conduition, and all,
I think Conduition's stateless take can go a little further with a simple
indexing trick. Give every address a monotonic index i, and from the seed
derive a long sequence of shared keys K_0, K_1, .... When we create address
i, we add taproot leaves for K_i through K_{i+N-1}. That is a sliding
window of size N.
When a spend gathers a set of our inputs, let i_min be the smallest 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 touches 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 working across
older UTXOs. Wallets that need giant sweeps can still consolidate inside
windows. The number of full signatures in a transaction is the number of
windows inputs belong to.
Curious whether this sounds workable.
Best,
Boris
On Saturday, November 1, 2025 at 8:09:52 PM UTC-3 conduition 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, especially
for deterministic backup wallets which is likely the bulk of modern Bitcoin
usage. I could imagine offline/hardware wallets having a very tough time
with this.
Consider a more conservative (but also very common) use case: Aggregating
inputs controlled by the same owner. In this context, what the sender is
really trying to prove here isn't whether UTXO A committed to UTXO 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 pubkey,
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 creates
statefulness), you could commit a taptree to a deterministic set of
pubkeys, such as "the nearest 100 addresses in the same BIP32 account". 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 stateless address
generation, while also allowing a single signature to cover all common
inputs in a wallet.
This would have pretty bad effects on UTXO privacy, because the
common-owner heuristic would become even stronger and would be provable
on-chain, 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 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 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:
<input_index> <output_index> <txid> <nonce> <OP_CIV>
Where <input_index> 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.
<output_index> and <txid> together form the outpoint, or UTXO identifier to
look for at the <input_index> location. If these two stack elements are
malformed, or the resulting outpoint does not match 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 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, <input_index>, 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+...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/bitcoindev/05195086-ee52-472c-962d-0df2e0b9dca2n%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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/19701913-9225-45b3-8a2c-d620c53d8873n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 13141 bytes --]
next prev parent reply other threads:[~2025-11-02 1:45 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-11-01 17:11 Tadge Dryja
2025-11-01 22:56 ` 'conduition' via Bitcoin Development Mailing List
2025-11-02 1:34 ` Boris Nagaev [this message]
2025-11-02 18:47 ` adiabat
2025-11-28 18:52 ` 'conduition' via Bitcoin Development Mailing List
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=19701913-9225-45b3-8a2c-d620c53d8873n@googlegroups.com \
--to=bnagaev@gmail.com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox