Published on: 2017-05-10T14:59:08+00:00
A potential vulnerability in Bitcoin's signature aggregation feature is discussed in this conversation. The Wagner generalized birthday attack could be used to manipulate the system by varying the R values and colliding hashes. To defend against this attack, a possible solution is proposed where the miner calculates s-aggregate and aggregates all the public keys from the aggregated signatures in the block. They then sort and hash the concatenated list of pubkeys, multiplying s by this combo-pubkey hash. Verification would involve creating the same combo-pubkey hash, multiplying s by the multiplicative inverse of the calculated h(c), and verifying s. However, the impact on verification speed is uncertain.Another optimization proposed involves concatenating all the R's or P's in the order they appear in the block. Then, the miner commits to s*h(c)^1, the multiplicative inverse of the hash of all those values. During verification, nodes can simply multiply by h(c) instead of calculating the inverse. Russell O'Connor argues that a proposal under consideration is flawed, demonstrating a scenario where Bob tries to steal Alice's UTXO using random values to create an invalid individual signature that becomes valid when combined with other inputs.Andrew Poelstra suggests using non-interactive Schnorr aggregation as a solution. This involves independent Schnorr sigs without aggregation until a miner produces a block. The miner multiplies each s_i by H(witness root || index), sums up the s_i's, and commits the sum somewhere that doesn't affect the root. Verifiers can recognize the signature given only the transaction it signs and R_i, which determine a valid signature.The proposal being discussed involves Schnorr signatures and non-interactive partial aggregation of signatures on a per-block basis. It aims to save space without apparent security issues but requires feedback from experts to ensure its safety. Private keys, public keys, and s values are generated for each signature. Unique R values are used for signing and verification. While interactive aggregate signatures require co-signers to build an aggregate R value, non-interactively half of the signature can be aggregated by summing up the s values. This approach reduces signature size to 32 bytes each, allowing more signatures in a block while taking up less disk and network space. However, caching signatures and quickly validating a block may be challenging, although validation with cached signatures seems possible without elliptic curve operations. Expert feedback is necessary to ensure the proposal's safety.The implementation of Schnorr signatures in a future witness version could potentially enable non-interactive partial aggregation of signatures on a per-block basis, saving space. There appear to be no security issues, but the author seeks feedback from the mailing list to identify any vulnerabilities. The signature process involves generating private keys multiplied by a generator to get public keys, followed by calculating 's' values for each signature. Interactive aggregate signatures involve co-signers sharing R values to build an aggregate R value. Non-interactively, half the signature can be aggregated by summing up the s values. When making transactions, wallets sign in the usual way, and the signature [R, s] goes into the witness stack. Miners remove the s values from compatible inputs when generating a block and commit to the aggregate s value in the coinbase transaction. The advantages include fitting more signatures in a block, occupying less disk and network space, and speeding up block verification.
Updated on: 2023-08-01T20:33:41.352835+00:00