Re: [bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures

From: Michael Folkson <michaelfolkson@protonmail•com>
To: Jonas Nick <jonasdnick@gmail•com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures
Date: Sun, 17 Jul 2022 13:26:26 +0000	[thread overview]
Message-ID: <uxodWlVSmJqvVHDuGevdDbsc5lXiyV6zONlNJtj6gDylkTXQzkPPokLXKJAVULMwPbduJJ7Fb-s0ZYKpduvIZ-LkCsfXClkDH5WhOFsTHts=@protonmail.com> (raw)
In-Reply-To: <33f275c2-06b1-4b4a-2a75-cafe36836503@gmail.com>

Thanks for this Jonas. One question that was asked on Telegram (credit: Antoine D) and isn't clear to me skimming the blog post and the draft BIP is whether half aggregation needs a new output type or not like we expect cross input signature aggregation (CISA) to [0]. My understanding is Schnorr signature batch verification (no aggregation of signatures) can be done today but half aggregation and CISA would need a soft fork and potentially a new output type in addition.

(I know this work is in its early stages and won't be proposed for a soft fork anytime soon. A few of us are just trying to get a basic sketch in our heads of what they require and whether they could be enabled in the same upgrade.)

[0]: https://bitcoin.stackexchange.com/questions/106240/will-cross-input-signature-aggregation-need-a-new-output-type/

--
Michael Folkson
Email: michaelfolkson at protonmail.com
Keybase: michaelfolkson
PGP: 43ED C999 9F85 1D40 EAF4 9835 92D6 0159 214C FEE3

------- Original Message -------
On Friday, July 8th, 2022 at 16:53, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:

> Half-aggregation has been mentioned several times on this list in various
> contexts. To have a solid basis for discussing applications of half-aggregation,
> I think it's helpful to have a concrete specification of the scheme and a place
> for collecting supplemental information like references to cryptographic
> security proofs. You can find the BIP draft at
>
> https://github.com/ElementsProject/cross-input-aggregation/blob/master/half-aggregation.mediawiki
>
> Similar to BIP-340, this BIP draft specifies only the cryptographic scheme and
> does not prescribe specific applications. It has not received an extensive
> security review yet. Thanks to Elliott Jin and Tim Ruffing for the review so
> far. One new feature that the specified scheme has is "incremental aggregation"
> which allows aggregating additional BIP-340 signatures into an existing
> half-aggregate signature.
>
> While BIP-340 has a pseudocode specification and a reference implementation in
> python, this BIP draft has a formal specification written in hacspec [0] and
> auxiliary pseudocode. The formal specification is a mathematically precise
> description of the scheme, which paves the way for computer-aided formal proofs.
> Software tools ("proof assistants") allow proving properties about the formal
> specification ("no integer overflow") and apply formal software verification
> ("implementation is behaviorally equivalent to the spec"). I don't have concrete
> plans (nor the skillset) to use these techniques. Still, I think this is an
> exciting area to explore because it has the potential to increase the Bitcoin
> ecosystem's robustness significantly and has little downside. Since hacspec's
> syntax is a subset of Rust's syntax, one can use the standard rust toolchain to
> compile, execute and test the specification.
>
> You can find a blog post that gives a broader context at
> https://blog.blockstream.com/half-aggregation-of-bip-340-signatures/
>
> [0] https://github.com/hacspec/hacspec
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev