From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 01 Nov 2025 16:10:00 -0700 Received: from mail-oi1-f183.google.com ([209.85.167.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vFKjP-0004QA-5r for bitcoindev@gnusha.org; Sat, 01 Nov 2025 16:10:00 -0700 Received: by mail-oi1-f183.google.com with SMTP id 5614622812f47-44e905f7fd4sf3448871b6e.2 for ; Sat, 01 Nov 2025 16:09:58 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1762038593; cv=pass; d=google.com; s=arc-20240605; b=TNTf3HvyTg9Cz53aATbbYOmw6gEW5l6BAp4brrG+dNwfbIkEHMA2WRRroWCG3nWjFQ WDfmqH3pAMzY9OV18PwQ9g2E2u+cEcCFkOV9vR3yjxOPUQwiMMzpriUAgbddHlHNHQho ylkwxPAdM/YPnJxJun+8Q/+1hBcv+f1up78kbSrh5FFySpKW9jwu5y2ElE2anMALGvEh b1PoDadb4XT/Gb5Xqz+fNIgRHHCny87Vah6FqhG95qvfkaKOXhDiZNK5dBn2fQKHvSi5 hd6A6u4ZPhVaQL/ZUlUBK1Dw0nAholTmeIdwu5nsdgtEyUKGHXzfPG8VR8yWftTKp9Lx KKbQ== 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=KcK3wjH1fcv3kp1AzGiwur0pvcGCsQ2hIyZhZY7Vvnw=; fh=H9A2rWgH+U7TynwtwCYGp7OUdmFVnPlVPoZXrtZBJsU=; b=di/rlSlMnqn0+Uxl5EvOqbsM7/z/ecNJVGqJxHU73KwY4hXqhJtoTTmqQHHFIuD/vF pNEyfE2uIWq6k4TwpOYgqB6+ytX1BlofglBcqiBJDkF1gaN7ue7Y3UTqCA1MwPh+28B2 HBga4UrLtwN78QpXsf5LjeFEWhh9ZU3N9ACSK/MvVybDr9EwuAWancJS1vNryl063Qg3 y1Yso6lo2+Ew//uSFuLRE6++ZFjGjanFrlLMK+L0YR4VGnymuPfxt38YHGS28XXKqJlB gt7uIa1/n+9N2XB9GzVrZWnbdWtwfmP4oqR4lYhrytx6eA5w/ptzDoWBUIdlW0vmqZdq ZHFw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=aI8liuHp; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 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=1762038593; x=1762643393; 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=KcK3wjH1fcv3kp1AzGiwur0pvcGCsQ2hIyZhZY7Vvnw=; b=rgQOV2Z7NXixtldCNGzU8IvJK6eCgGX9QQzbna81il9CEHIj8gz27lOeNT14Do3YQ5 Uo+EHu8rL+WUvBOFoZoLEsLzlI+z9nOP2VMEh0I6aKlLm+jCrMoX5CwfQ6iOCC7ZdoKs P5TPSCvpnxl5o7rXzul/G/BK2ZqnwLAj3PYKoREEiKHxd2o1wquNNYQ1JDKBLBDwnLur vAcE/P1R+bfanbca0X2rqYwRCcbpogH5JAn9onNGILTnHHmhMlnfB3X4MmHb0N2tA4uE ArmrEm/Tq9/CvcKKBLzlRix0nRFkM1WYoGqEUT+AfHq4yhkAifsvsV4FFrsbFoSfvXFo LR7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762038593; x=1762643393; 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=KcK3wjH1fcv3kp1AzGiwur0pvcGCsQ2hIyZhZY7Vvnw=; b=S69SwEjAft+Ps/q6xIl4b2myYaC9BK9YplDeLtcR44ySjF506rX8gKRf7c4XCaTERN Kgygv+I+9s1NpoKtfLT+EG44kWvvH0uhatZ4Sq8Ownj+0N5CC1QC19y+WxliLUWuWf+e TZShCHG94sKXNawl4w0tnF/eRgxHrR9BFFkBJaxCwy/55fmHGsEMCdYijbXq0QjrQHsk F/u0eke2IQGcJXqsQAXj28orfDXnM9aK11rVqYpfeDfEH+PpvAb+xjMrmJLKLi/GVIqB aG3Qc2byXF8vNRkitk8aI+LpWAI8bhT6sjO0VOFKCPTb+YmGHTPKC3IN2OHflTyoFbGO ADEA== X-Forwarded-Encrypted: i=2; AJvYcCUlCQ2iUMTMsU4KkIXdsth67SH4rP+sCUmhIp1HFLxF9Ad1u+SU5piRKHzRnpI5huRBLtO+4GKl7UM7@gnusha.org X-Gm-Message-State: AOJu0YzvqW7y0y5peyXQ318riLwj1nKukLVX5qObkA+EKXY7x1cPl1RQ e375LvZWTW5LV77EPjN7WoYmNx3+yWUMEIZ4kkCHSwPRUpnXBwy/PlQi X-Google-Smtp-Source: AGHT+IFWGDI9j+m4ie3FujQwFdkUFASEiGfAlVGlPsqBsWr6oW1E5rUbGEaOP9Ljx3blT/TqnLyeRw== X-Received: by 2002:a05:6808:23cd:b0:43d:24b7:2b93 with SMTP id 5614622812f47-44f95eb8411mr3936602b6e.17.1762038592810; Sat, 01 Nov 2025 16:09:52 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+atDCXQC9xzel38FLvUb6xRCE6ewIjEvwesUYmTpY1OxA==" Received: by 2002:a4a:d805:0:b0:656:8226:7303 with SMTP id 006d021491bc7-6568249c5d9ls1311765eaf.1.-pod-prod-08-us; Sat, 01 Nov 2025 16:09:48 -0700 (PDT) X-Received: by 2002:a05:6808:1785:b0:44d:b8d3:322a with SMTP id 5614622812f47-44f95fda3e6mr3357243b6e.41.1762038588819; Sat, 01 Nov 2025 16:09:48 -0700 (PDT) Received: by 2002:a05:6402:d4a:b0:640:aaf6:8ce4 with SMTP id 4fb4d7f45d1cf-640aaf68ec1msa12; Sat, 1 Nov 2025 15:56:29 -0700 (PDT) X-Received: by 2002:a17:907:2d90:b0:b47:de64:df34 with SMTP id a640c23a62f3a-b707062c89dmr737065066b.51.1762037787003; Sat, 01 Nov 2025 15:56:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1762037786; cv=none; d=google.com; s=arc-20240605; b=i/ErOg3Ei5PgagNCDu9s2tDIRpvYJ5swSmznJf5recmf05U4qSBLY6ips94o1XLtmQ jChx8mVj24O9yXvxJ3UCSBAdFNjNJdpi24v3FMylfbZCmks9Cei0yr+3fPXPxr0IKE9h Gl8pZCx5IoxjKXu29nde/+F8XoaB4Kqg/5c86Zs1fzryzkolX8o7+5iUdp9+8Mo6aHOT T0YDmLUKPXcKaiuPVyOdSGyzzDtYt3n6qW9KNU3B/Oadhk7mLIlQPpEfvrOyEuM9H5ce fbe1hzyL0B1iK0VmF7LhgsRSeP4SdJaCFVdvyBBrG3cqp45WA5nnYppsQh9S11R74YOX lBGg== 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=/P01hV9/2ggGG6JlmBdeolMCV8XTOYykyD0ImP+R31Y=; fh=iL9DSYpC5RGeithzN5d/JVKj3o11LZT+9z7PU5q/3vc=; b=FwjoAhhKx2Z0S4YLij8S5cIMb/Qw1RRvNEftbCliriEnUmgfbW6xendo4gje78ztFa 61AMGCP+TyVOL6EDXAo5wpnfwvEEfbVBIV0oSjD3ataO9MiXz0LQs5XZcZfafjp2iMyC iMdWH/dfwiOcynzLg7nmyvR0uDEpe53uNCa+J2CwPYDQunMOwyrTiWQagiPTIdmxSzmq 9BE4Nxu0/J0LeB9Ct/mr16rAVWJ7kuZsJhmfmBL/DmAc1QbRQL1PIWVtWMjIN13BT1rU Xf/3pQ9me01uHEAV2Xjrx+giau74MJTSLew1e9+iL994iOMcppCRzERdmQiyW70Rjm1r A6aQ==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=aI8liuHp; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch. [185.70.43.22]) by gmr-mx.google.com with ESMTPS id a640c23a62f3a-b7077b505d2si19685566b.2.2025.11.01.15.56.26 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 01 Nov 2025 15:56:26 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) client-ip=185.70.43.22; Date: Sat, 01 Nov 2025 22:56:22 +0000 To: Tadge Dryja From: "'conduition' via Bitcoin Development Mailing List" Cc: Bitcoin Development Mailing List Subject: Re: [bitcoindev] OP_CIV - Post-Quantum Signature Aggregation Message-ID: In-Reply-To: <05195086-ee52-472c-962d-0df2e0b9dca2n@googlegroups.com> References: <05195086-ee52-472c-962d-0df2e0b9dca2n@googlegroups.com> Feedback-ID: 72003692:user:proton X-Pm-Message-ID: dad9e80d327abe71be750bcbee63f86634842aba MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------21cb616d2ed00440ce7393aaa8c95f08a76f8cf7533a585052baf4dd09a1771c"; 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=aI8liuHp; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 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) --------21cb616d2ed00440ce7393aaa8c95f08a76f8cf7533a585052baf4dd09a1771c Content-Type: multipart/mixed;boundary=---------------------e9dda4dadcdc1bd2117c29fcf3d7d461 -----------------------e9dda4dadcdc1bd2117c29fcf3d7d461 Content-Type: multipart/alternative;boundary=---------------------08b84a6e6e7d23c3981712d6397864e1 -----------------------08b84a6e6e7d23c3981712d6397864e1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" Neat idea! The need to commit each script pubkey to other prevouts in the T= X would probably hold the concept back from being practical, especially for= deterministic backup wallets which is likely the bulk of modern Bitcoin us= age. I could imagine offline/hardware wallets having a very tough time with= this. Consider a more conservative (but also very common) use case: Aggregating i= nputs controlled by the same owner. In this context, what the sender is rea= lly trying to prove here isn't whether UTXO A committed to UTXO B. For sign= ature aggregation across commonly-owned inputs, they just need to be able t= o prove that UTXO A and UTXO B are spendable under the same pubkey, and tha= t they, the pubkey owner, authorized both of them via a single signature. So instead of committing a taptree to pre-existing UTXOs (which creates sta= tefulness), you could commit a taptree to a deterministic set of pubkeys, s= uch as "the nearest 100 addresses in the same BIP32 account". At spending t= ime, we reveal the same pubkey's script leaf on all inputs, plus a signatur= e that covers all the inputs.=C2=A0This would allow stateless address gener= ation, 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-owne= r 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 th= e fee savings would be worth it, esp for big exchanges which consolidate hu= ndreds or thousands of UTXOs at a time. -conduition On Saturday, November 1st, 2025 at 2:02 PM, Tadge Dryja w= rote: > Hello- >=20 > Here's an idea for Post-Quantum cross-input signature aggregation. It's n= ot quite "signature aggregation" the way we normally think of it, but gives= similar benefits while not being tied to a particular signature scheme. >=20 > Folks have discussed Cross-input signature aggregation (CISA) in Bitcoin = a while now, and while related research such as MuSig2, FROST, and ROAST ha= ve been implemented in wallets, so far there is no consensus change in bitc= oin to enable CISA. My hunch is that one of the reasons this hasn't been ad= opted is that the space savings aren't that large. With taproot outputs, si= gnatures are 64 bytes, and discounted to 16 vBytes. https://github.com/Bloc= kstreamResearch/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. >=20 > One place where the size of signatures *is* a problem is with post-quantu= m signatures. The two most discussed PQ signature schemes, SPHINCS+ and CRY= STALS-Dilithium, both have pubkey+signature sizes in the kilobytes range. T= his would be a great opportunity for CISA, since even with a 75% witness di= scount, signatures would cost over 90% of the vBytes in a transaction. >=20 > Unfortunately all the great EC based signature aggregation tools people h= ave built don't work for lattices and hash-based signatures. Here's a way t= o get some of the same effects which would work with any signature type (in= cluding EC signatures, but if you've got EC signatures, existing CISA techn= iques are much better). I'm not attached to the name but for people familia= r with bitcoin, the easiest to understand would be OP_CIV or OP_CHECKINPUTV= ERIFY. >=20 > 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 "t= hat'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 nor= mal (perhaps PQ) SIGHASH_ALL signature. Input 1 has a proof pointing to inp= ut 0. Since input 0 exists within the transaction, input 1 is valid. >=20 > The arguments and usage of the would be: >=20 > >=20 > Where is the input number in the current transaction being = validated to look. If this stack element isn't a number, or the number exce= eds the number of inputs in the transaction, the opcode fails. >=20 > 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 th= e transaction, the opcode fails. >=20 > 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 tap= tree, 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 own= er. This nonce would prevent such an attack. >=20 > That's pretty much it for script evaluation. >=20 > The idea would be that a taproot tree would have at the root a "normal" p= ubkey capable of creating arbitrary signatures. Lower down in the tree, the= re 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 tra= nsaction 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 inpu= t in a transaction to use OP_CIV since that would require a hash cycle. >=20 > For the wallet side implementation, every time a wallet generates a new a= ddress, it looks up some or all of the current UTXOs in the wallet, and add= s a branch for each of them in the taproot tree. The wallet adds blinding d= ata to each OP_CIV script to prevent an attacker from being able to guess o= ther 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 priva= te key and the outpoint being pointed to, somewhat like the use of RFC6979 = for ECDSA nonces. (Eg nonce =3D hash(private_key, outpoint)). >=20 > Wallets constructed in such a way would often only need 1 signature per t= ransaction, as all other UTXOs could point to the oldest input in the trans= action. This savings doesn't work when a new wallet generates many addresse= s at once, and then over time coins are sent to those addresses. In that ca= se a wallet would end up with a number of UTXOs which don't point to each o= ther. Those UTXOs would all need to sign, but they might be paired with lat= er UTXOs which point to them. >=20 > Deterministic key wallets >=20 > One complication is key recovery for deterministic wallets. If only the m= aster key / seed phrase is known, all the root pubkeys can be recovered, bu= t the wallet has "forgotten" which pubkeys point to which UTXOs. Determinis= tic nonces make recovery possible, but in a naive implementation, there wou= ld be an exponential blowup if when addresses are created they point to all= existing UTXOs in the wallet. There are several workarounds, such as limit= ing the number of OP_CIV scripts in the tree to eg 10 (resulting in a ~1000= X slowdown in recovery while maintaining a good chance of OP_CIV use), or i= ncluding OP_CIV scripts pointing to all TXOs that the wallet knows have alr= eady been spent, increasing taptree size but reducing the number of guesses= needed for recovery. >=20 > Address re-use and replay attacks >=20 > 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 addres= s 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 avoide= d by using SIGHASH_ALL in the input that does sign, so that even if an atta= cker learns the full taptree of all the UTXOs of a wallet, they can't const= ruct or modify a transaction without the ability to sign. >=20 > Other uses >=20 > 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 the= y already control a different specified UTXO. I think it's mostly useful fo= r making PQ transactions smaller, but transaction introspection opcodes oft= en have interesting use cases and OP_CIV may as well >=20 > Real life example of OP_CIV commitments >=20 > I gave a talk about this at TABConf a couple weeks ago; I was hoping to h= ave 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 th= at also means that this mailing list post is able to link to the TABConf ta= lk: https://www.youtube.com/watch?v=3Dcqjo3rmd6hY. >=20 > Wonder if anyone has ideas / improvements / downsides to this idea. Thank= s for any feedback! > -Tadge >=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= email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/05195086-ee52-472c-962d-0df2e0b9dca2n%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/= kBNJjQ46doVAAXAOjzIoBdtX4UikDa2YCqKdPbzEK-QjbBUHdl2V_5T-Ay6Z76lnj5BHmrAWg9F= S1eHT_PgJmoEFFuPkWt5i8LPEvY3wmKk%3D%40proton.me. -----------------------08b84a6e6e7d23c3981712d6397864e1 Content-Type: multipart/related;boundary=---------------------2a4e9dcf558a1d66349985b38828e58a -----------------------2a4e9dcf558a1d66349985b38828e58a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Neat idea! = The need to commit each script pubkey to other prevouts in the TX would pro= bably hold the concept back from being practical, especially for determinis= tic backup wallets which is likely the bulk of modern Bitcoin usage. I coul= d imagine offline/hardware wallets having a very tough time with this.

=
Consider a = more conservative (but also very common) use case: Aggregating inputs contr= olled 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 aggre= gation across commonly-owned inputs, they just need to be able to prove tha= t 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 commi= tting a taptree to pre-existing UTXOs (which creates statefulness), you cou= ld 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, whil= e also allowing a single signature to cover all common inputs in a wallet.<= /span>

= This would have pretty bad effects on UTXO privacy, because the common-owne= r 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 th= e fee savings would be worth it, esp for big exchanges which consolidate hu= ndreds or thousands of UTXOs at a time.

-co= nduition
On Saturday, November 1st, 2025 at 2:02 PM, Tadge Dryja <rx@awso= mnet.org> wrote:
Hello-

Here's an idea for Post-Quantum cross-input signa= ture aggregation. 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 Bitcoin a while now, and while related res= earch 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 t= hat one of the reasons this hasn't been adopted is that the space savings a= ren't that large. With taproot outputs, signatures are 64 bytes, and disco= unted to 16 vBytes. https://github.com/BlockstreamResearch/cross-input-agg= regation/blob/master/savings.org shows a 7.1% vByte savings using full aggr= egation. Signatures just aren't that big of a part of the transaction, esp= ecially after the 75% segwit discount.

One place w= here the size of signatures *is* a problem is with post-quantum signatures.= The two most discussed PQ signature schemes, SPHINCS+ and CRYSTALS-Dilith= ium, both have pubkey+signature sizes in the kilobytes range. This would b= e a great opportunity for CISA, since even with a 75% witness discount, sig= natures would cost over 90% of the vBytes in a transaction.

<= /div>
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 C= ISA techniques are much better). I'm not attached to the name but for peop= le familiar with bitcoin, the easiest to understand would be OP_CIV or OP_C= HECKINPUTVERIFY.

The basic idea is that a transact= ion 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", wit= hout providing one of its own. Take for example a transaction with 2 input= s: input 0 and input 1. Input 0 has a normal (perhaps PQ) SIGHASH_ALL sign= ature. Input 1 has a proof pointing to input 0. Since input 0 exists with= in the transaction, input 1 is valid.

The argument= s and usage of the would be:

<input_index> <output_index&= gt; <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 o= f 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 malf= ormed, or the resulting outpoint does not match the outpoint seen in the tr= ansaction, the opcode fails.

<nonce> is popped off the stack a= nd 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 tr= ee, trying to assign UTXOs to the same owner. This nonce would prevent suc= h 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 w= ould be several / many OP_CIV scripts, each one pointing to a different out= point. When a UTXO is being spent, if it is being spent in the same transa= ction as any of the UTXOs pointed to by the OP_CIV scripts, one of those ca= n be revealed instead of supplying a signature. At least one input in a tr= ansaction 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 a= ddress, it looks up some or all of the current UTXOs in the wallet, and add= s 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 argumen= t, <input_index>, is left empty in the script and supplied at spendin= g time. To avoid the need to generate and store additional entropy, the wa= llet can generate the blinding data deterministically, using the root pubke= y's private key and the outpoint being pointed to, somewhat like the 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= transaction, as all other UTXOs could point to the oldest input in the tra= nsaction. This savings doesn't work when a new wallet generates many addre= sses at once, and then over time coins are sent to those addresses. In tha= t case a wallet would end up with a number of UTXOs which don't point to ea= ch other. Those UTXOs would all need to sign, but they might be paired wit= h later UTXOs which point to them.

Deterministic key wallets
One complication is key recovery for deterministic wallets. If only the m= aster key / seed phrase is known, all the root pubkeys can be recovered, bu= t the wallet has "forgotten" which pubkeys point to which UTXOs. Determini= stic nonces make recovery possible, but in a naive implementation, there wo= uld be an exponential blowup if when addresses are created they point to al= l existing UTXOs in the wallet. There are several workarounds, such as lim= iting the number of OP_CIV scripts in the tree to eg 10 (resulting in a ~10= 00X 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 a= lready been spent, increasing taptree size but reducing the number of guess= es 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 mi= ght be, but OP_CIV points to outpoints, not addresses or keys, so address r= euse for the UTXOs being pointed to shouldn't matter. For address re-use w= ith 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 attack= er learns the full taptree of all the UTXOs of a wallet, they can't constru= ct 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 s= ecret (a spend path & nonce) that allows someone to take a UTXO, but on= ly if they already control a different specified UTXO. I think it's mostly= useful for making PQ transactions smaller, but transaction introspection o= pcodes 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 TABCo= nf a couple weeks ago; I was hoping to have sent this writeup out before th= e 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 l= ist post is able to link to the TABConf talk: https://www.youtube.com/watch= ?v=3Dcqjo3rmd6hY.

Wonder if anyone has ideas / improvements / downsi= des 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 e= mail to bitcoindev+unsubscribe@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 &= 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/bitcoindev/kBNJjQ= 46doVAAXAOjzIoBdtX4UikDa2YCqKdPbzEK-QjbBUHdl2V_5T-Ay6Z76lnj5BHmrAWg9FS1eHT_= PgJmoEFFuPkWt5i8LPEvY3wmKk%3D%40proton.me.
-----------------------2a4e9dcf558a1d66349985b38828e58a-- -----------------------08b84a6e6e7d23c3981712d6397864e1-- -----------------------e9dda4dadcdc1bd2117c29fcf3d7d461 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== -----------------------e9dda4dadcdc1bd2117c29fcf3d7d461-- --------21cb616d2ed00440ce7393aaa8c95f08a76f8cf7533a585052baf4dd09a1771c Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmkGkAcJEHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmeWdRv4VoZiWx9VuxYVuPObHO9UX7ZExJKl32+R uhGeKRYhBEdIka0CMtrLdg13a3gpbO2E9rPFAABV3gEAwtY8IwIvTqX8mwFn /eQe0Lf6kFAL7FmqqNErMAxLr8YBAN4DJRZrC3Wnms0stAa/b7TjWK8r5kjA YccU4sZuaIwF =J1T6 -----END PGP SIGNATURE----- --------21cb616d2ed00440ce7393aaa8c95f08a76f8cf7533a585052baf4dd09a1771c--