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

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

[Jonas Nick]

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

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

[Michael Folkson]

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

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

[Jonas Nick]

To be clear, whether "half aggregation needs a new output type or not" does not
become clear in the draft BIP because it is out of scope. Half-aggregation has a
few possible applications. The draft only specifies the cryptographic scheme.

The StackExchange post you link to argues that CISA requires a new output type.
The same argument applies to half aggregating signatures across transaction
inputs (CISHA, if you will). The only difference to "full aggregation" is that
the transaction signature is a single half-aggregate signature instead of a
64-byte signature. You're right that it's possible to do batch verification of
Taproot output key spends (Schnorr signatures) and script spends (key tweaks).

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

[Michael Folkson]

So this half aggregation BIP draft could potentially play the role that BIP340 did for BIP341/342 but it is too premature to start formalizing what the equivalent of BIP341/342 for this draft BIP would look like. And given there are use cases for this half aggregation BIP that can be worked on today (e.g. Lightning gossip [0], Lightning gossip seems to be a very interesting research area at the moment with a number of possible upgrades) it makes sense to focus on those first.

There is a section[1] in the CISA repo which I missed originally that describes some of the challenges of implementing CISA/CISHA as a consensus change. A couple of things that stand out to me if this was attempted in the long term. One is that there would almost need to be two tiers of verification: verification for single signature key path spends where CISA, CISHA could be applied and verification for Taproot script paths where CISA, CISHA couldn't be applied. It could even be the case that a new output type is defined specifically for the CISA, CISHA use case where there is no access to a script path at all (i.e. where users don't have a need for anything other than a single signature spend path). With SegWit v0 (and today with SegWit v1) the intention is to get the entire community to move to the new output type. But there could be a long term future where you pick an output type depending on your use case. I recall that Mimblewimble only worked if scripting was ditched entirely and every spend was assumed to be a single signature spend.

Anyway...thanks for indulging me on the long term stuff :)

[0]: https://github.com/ElementsProject/cross-input-aggregation#sigagg-case-study-ln-channel-announcements

[1]: https://github.com/ElementsProject/cross-input-aggregation#integration-into-the-bitcoin-protocol

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


------- Original Message -------
On Sunday, July 17th, 2022 at 21:45, Jonas Nick <jonasdnick@gmail.com> wrote:


> To be clear, whether "half aggregation needs a new output type or not" does not
> become clear in the draft BIP because it is out of scope. Half-aggregation has a
> few possible applications. The draft only specifies the cryptographic scheme.
>
> The StackExchange post you link to argues that CISA requires a new output type.
> The same argument applies to half aggregating signatures across transaction
> inputs (CISHA, if you will). The only difference to "full aggregation" is that
> the transaction signature is a single half-aggregate signature instead of a
> 64-byte signature. You're right that it's possible to do batch verification of
> Taproot output key spends (Schnorr signatures) and script spends (key tweaks).