half-aggregation.mediawiki

  Title: Half-Aggregation of BIP 340 signatures
  Status: EXPERIMENTAL

Table of Contents Introduction Abstract Copyright Motivation Design Description Specification Test Vectors Pseudocode Notation Aggregate IncAggregate VerifyAggregate

Introduction

Abstract

This document describes half-aggregation of BIP 340 signatures. Half-aggregation is a non-interactive process for aggregating a collection of signatures into a single aggregate signature. The size of the resulting aggregate signature is approximately half of the combined size of the original signatures.

Copyright

This document is licensed under the 3-clause BSD license.

Motivation

Half-aggregation is applicable if there is a verifier that needs to verify multiple signatures. Instead of sending individual signatures to the verifier, the signatures can be compressed into a single aggregate signature and sent to the verifier. If the verifier can successfully verify the aggregate signature, the verifier can be sure that the individual signatures would have passed verification.

The purpose of half-aggregation is to reduce the size of the data that is sent to the verifier. While n BIP 340 signatures are 64*n bytes, a half-aggregate of the same signatures is 32*n + 32 bytes. The process of half-aggregation is straightforward: it is a pure function of the input signatures, public keys, and messages. It is non-interactive and does not require cooperation from other parties, including signers or verifiers.

There are a variety of scenarios where half-aggregation of BIP-340 signatures is useful. To keep this section brief and avoid getting outdated quickly, we focus on listing example applications and defer the detailed discussion of the application-specific trade-offs to other places.

One example is the Lightning Network routing gossip protocol, which as of this writing involves messages that contain ECDSA signatures. If the signature scheme was changed to BIP 340, half-aggregation could reduce the total amount of gossiped data. Instead of sending individual gossip messages, nodes could assemble a batch of messages and half-aggregate the signatures of the individual messages into a single signature for the batch.

Another application of half-aggregation is within the Bitcoin consensus protocol. In particular, it has been discussed in the context of the Graftroot proposal. Half-aggregation would allow Graftroot spending to be as efficient as best-case Taproot spends by aggregating the signature of the surrogate script and signatures that satisfy this script. Moreover, half-aggregation improves the efficiency of proposed Bitcoin script opcodes that verify multiple signatures, such as OP_EVICT. We can also imagine adding a Bitcoin script opcode that verifies a half-aggregate signature, allowing for more efficient non-interactive multi and threshold signatures.

Half-aggregation can also be applied to the signatures in the inputs of Bitcoin transactions, a process known as cross-input signature aggregation (CISA). This reduces the size of an average transaction by 20.6% and the weight by 7.6%. A known downside of using half aggregation is that some uses of adaptor signature protocols may be incompatible. Usually, CISA is proposed with interactive full signature aggregation instead of non-interactive half-aggregation because creating a valid transaction already requires cooperation, and full signature aggregation is more efficient. However, the difference in complexity between half-aggregation and full aggregation is so significant that basing a CISA on half-aggregation is a legitimate approach.

The most invasive application to Bitcoin's consensus would be block-wide signature aggregation. It refers to a process where block producers aggregate as many transaction signatures as possible. In the best case, a full block would only have a single half-aggregate signature. While this is attractive from the efficiency perspective, block-wide aggregation requires more research (and, in particular, special attention to handling reorgs).

Design

The idea for half-aggregation of Schnorr signatures was brought up in the context of block-wide signature aggregation by Tadge Dryja on the Bitcoin mailing list in 2017. The scheme had a security flaw that was noticed and fixed shortly after by Russell O'Connor and Andrew Poelstra. In 2021 Chalkias, Garillot, Kondi and Nikolaenko published a security proof in the random oracle model (ROM) that reduces the security of half-aggregation to the security of Schnorr signatures. Chen and Zhao were able to produce a tight proof in the ROM and algebraic group model in the following year. Moreover, they came up with an elegant approach to incremental aggregation that is used in this document.

• Incremental aggregation allows non-interactively aggregating additional BIP 340 signatures into an existing half-aggregate signature.
• A half-aggregate signature of u BIP 340 input signatures is serialized as the (u+1)⋅32-byte array r₁ || ... || r_u || bytes(s) where r_i is a 32-byte array from input signature i and s is a scalar aggregate (see below for details).
• This document does not specify the aggregation of multiple aggregate signatures (yet). It is possible, but requires changing the encoding of an aggregate signature. Since it is not possible to undo the aggregation of the s-values, when verifying of such an aggregate signature the randomizers need to be the same as when verifying the individual aggregate signature. Therefore, the aggregate signature needs to encode a tree that reveals how the individual signatures were aggregated and how the resulting aggregate signatures were reaggregated.
• The first randomizer z₀ is fixed to the constant 1, which speeds up verification because z₀⋅R₀ = R₀. This optimization has been suggested and proven secure by Chen and Zhao.
• The maximum number of signatures that can be aggregated is 2¹⁶ - 1. Having a maximum value is supposed to prevent integer overflows. This specific value was a conservative choice and may be raised in the future (TODO).

Description

Specification

The specification is written in hacspec, a language for formal specifications and a subset of rust. It can be found in the hacspec-halfagg directory. Note that the specification depends the hacspec library and a hacspec implementation of BIP 340.

Test Vectors

Preliminary test vectors are provided in tests.rs. The specification can be executed with the test vectors by running cargo test in the hacspec-halfagg directory (cargo is the rust package manager).

Pseudocode

The following pseudocode is not a specification but is only intended to augment the actual hacspec specification.

Notation

The following conventions are used, with constants as defined for secp256k1. We note that adapting this specification to other elliptic curves is not straightforward and can result in an insecure scheme^[1].

• Lowercase variables represent integers or byte arrays.
  • The constant p refers to the field size, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.
  • The constant n refers to the curve order, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
• Uppercase variables refer to points on the curve with equation y² = x³ + 7 over the integers modulo p.
  • is_infinite(P) returns whether or not P is the point at infinity.
  • x(P) and y(P) are integers in the range 0..p-1 and refer to the X and Y coordinates of a point P (assuming it is not infinity).
  • The constant G refers to the base point, for which x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 and y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8.
  • Addition of points refers to the usual elliptic curve group operation.
  • Multiplication (⋅) of an integer and a point refers to the repeated application of the group operation.
• Functions and operations:
  • || refers to byte array concatenation.
  • The function x[i:j], where x is a byte array and i, j ≥ 0, returns a (j - i)-byte array with a copy of the i-th byte (inclusive) to the j-th byte (exclusive) of x.
  • The function bytes(x), where x is an integer, returns the 32-byte encoding of x, most significant byte first.
  • The function bytes(P), where P is a point, returns bytes(x(P)).
  • The function len(x) where x is a byte array returns the length of the array.
  • The function int(x), where x is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is x.
  • The function has_even_y(P), where P is a point for which not is_infinite(P), returns y(P) mod 2 = 0.
  • The function lift_x(x), where x is a 256-bit unsigned integer, returns the point P for which x(P) = x^[2] and has_even_y(P), or fails if x is greater than p-1 or no such point exists. The function lift_x(x) is equivalent to the following pseudocode:
    • Fail if x ≥ p.
    • Let c = x³ + 7 mod p.
    • Let y = c^(p+1)/4 mod p.
    • Fail if c ≠ y² mod p.
    • Return the unique point P such that x(P) = x and y(P) = y if y mod 2 = 0 or y(P) = p-y otherwise.
  • The function hash_tag(x) where tag is a UTF-8 encoded tag name and x is a byte array returns the 32-byte hash SHA256(SHA256(tag) || SHA256(tag) || x).
• Other:
  • Tuples are written by listing the elements within parentheses and separated by commas. For example, (2, 3, 1) is a tuple.

Aggregate

Aggregate takes an array of public key, message and signature triples and returns an aggregate signature. If every triple (p, m, s) is valid (i.e., Verify(p, m, s) as defined in BIP 340 returns true), then the returned aggregate signature and the array of (p, m) tuples passes VerifyAggregate. (However, the inverse does not hold: given suitable valid triples, it is possible to construct an input array to Aggregate which contains invalid triples, but for which VerifyAggregate will accept the aggregate signature returned by Aggregate. If this is undesired, input triples should be verified individually before passing them to Aggregate.)

Input:

• pms_0..u-1: an array of u triples, where the first element of each triple is a 32-byte public key, the second element is a 32-byte message and the third element is a 64-byte BIP 340 signature

Aggregate(pms_0..u-1):

• Let aggsig = bytes(0)
• Let pm_aggd be an empty array
• Return IncAggregate(aggsig, pm_aggd, pms_0..u-1); fail if that fails.

IncAggregate

IncAggregate takes an aggregate signature, an array of public key and message tuples corresponding to the aggregate signature, and an additional array of public key, message and signature triples. It aggregates the additional array of triples into the existing aggregate signature and returns the resulting new aggregate signature. In other words, if VerifyAggregate(aggsig, pm_aggd) passes and every triple (p, m, s) in pms_to_agg is valid (i.e., Verify(p, m, s) as defined in BIP 340 returns true), then the returned aggregate signature along with the array of (p, m) tuples of pm_aggd and pms_to_agg passes VerifyAggregate. (However, the inverse does not hold: given a suitable valid aggregate signature and suitable valid triples, it is possible to construct inputs to IncAggregate which contain an invalid aggregate signature or invalid triples, but for which VerifyAggregate will accept the aggregate signature returned by IncAggregate. If this is undesired, the input triples and the input aggregate signature should be verified individually before passing them to IncAggregate.)

Input:

• aggsig : a byte array
• pm_aggd_0..v-1: an array of v tuples, where the first element of each tuple is a 32-byte public key and the second element is a 32-byte message
• pms_to_agg_0..u-1: an array of u triples, where the first element of each tuple is a 32-byte public key, the second element is a 32-byte message and the third element is a 64-byte BIP 340 signature

IncAggregate(aggsig, pm_aggd_0..v-1, pms_to_agg_0..u-1):

• Fail if v + u ≥ 2¹⁶
• Fail if len(aggsig) ≠ 32 * (v + 1)
• For i = 0 .. v-1:
  • Let (pk_i, m_i) = pm_aggd_i
  • Let r_i = aggsig[i⋅32:(i+1)⋅32]
• For i = v .. v+u-1:
  • Let (pk_i, m_i, sig_i) = pms_to_agg_i-v
  • Let r_i = sig_i[0:32]
  • Let s_i = int(sig_i[32:64])
  • If i = 0:
    • Let z_i = 1
  • Else:
    • Let z_i = int(hash_{HalfAgg/randomizer}(r₀ || pk₀ || m₀ || ... || r_i || pk_i || m_i)) mod n
• Let s = int(aggsig[(v⋅32:(v+1)⋅32]) + z_v⋅s_v + ... + z_v+u-1⋅s_v+u-1 mod n
• Return r₀ || ... || r_v+u-1 || bytes(s)

VerifyAggregate

VerifyAggregate verifies a given aggregate signature against an array of public key and message tuples.

Input:

• aggsig : a byte array
• pm_aggd_0..u-1: an array of u tuples, where the first element of each tuple is a 32-byte public key and the second element is a 32-byte message

VerifyAggregate(aggsig, pm_aggd_0..u-1): The algorithm VerifyAggregate(aggsig, pm_aggd_0..u-1) is defined as:

• Fail if u ≥ 2¹⁶
• Fail if len(aggsig) ≠ 32 * (u + 1)
• For i = 0 .. u-1:
  • Let (pk_i, m_i) = pm_aggd_i
  • Let P_i = lift_x(int(pk_i)); fail if that fails
  • Let r_i = aggsig[i⋅32:(i+1)⋅32]
  • Let R_i = lift_x(int(r_i)); fail if that fails
  • Let e_i = int(hash_{BIP0340/challenge}(bytes(r_i) || pk_i || m_i)) mod n
  • If i = 0:
    • Let z_i = 1
  • Else:
    • Let z_i = int(hash_{HalfAgg/randomizer}(r₀ || pk₀ || m₀ || ... || r_i || pk_i || m_i)) mod n
• Let s = int(aggsig[u⋅32:(u+1)⋅32]); fail if s ≥ n
• Fail if s⋅G ≠ z₀⋅(R₀ + e₀⋅P₀) + ... + z_u-1⋅(R_u-1 + e_u-1⋅P_u-1)
• Return success iff no failure occurred before reaching this point.

The verification algorithm is similar to BIP340 Batch Verification. As in BIP340, using an efficient algorithm for computing the sum of multiple EC multiplications can significantly speed up verification.