Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation
I messed up and only replied to Russel O'Connor; my response is copied below. And then there's a bit more. - Aha, Wagner's generalized birthday attack, the bane of all clever tricks! I didn't realize it applied in this case but looks like it in fact does. applies to this case. It would have to be a miner performing the attack as the s-value would only be aggregated in the coinbase tx, but that's hardly an impediment. In fact, sketching it out, it doesn't look like the need to know m1, m2... m_n is a big problem. Even if the m's are fixed after being chosen based on the P1... Pn's, (in bitcoin, m always commits to P so not sure why it's needed in the hash) there is still freedom to collide the hashes. The R values can be anything, so getting h(m1, R1, P1) + h(m2, R2, P2)... to equal -h(m0, R0, P0) is doable with Wagner's attack by varying R1, R2... to get different hashes. I *think* there is a viable defense against this attack, but it does make the whole aggregation setup less attractive. The miner who calculates s-aggregate could also aggregate all the public keys from all the aggregated signatures in the block (P0, P1...), sort them and hash the concatenated list of pubkeys. They could then multiply s by this combo-pubkey hash (call it h(c)). Then when nodes verify the aggregate signature, they need to go through all the pubkeys in the block, create the same combo-pubkey hash, and multiply s by the multiplicative inverse of the h(c) they calculate, then verify s. I believe this breaks the Wagner generalized birthday attack because every h(m_i, R_i, P_i)*h(c) included or omitted affects the c part of h(m0, R0, P0)*h(c). I'm not sure how badly this impacts the verification speed. It might not be too bad for verification as it's amortized over the whole block. For the miner doing the aggregation it's a bit slower as they need to re-sort and hash all the pubkeys every time a new signature is added. Might not be too slow. I'm not super confident that this actually prevents the generalized birthday attack though. I missed that attack in the previous post so I'm 0 for 1 against Wagner so far :) - Andrew: Right, commiting to all the R values would also work; is there an advantage to using the R's instead of the P's? At first glance it seems about the same. Another possible optimization: instead of sorting, concatenate all the R's or P's in the order they appear in the block. Then have the miner commit to s*h(c)^1, the multiplicative inverse of the hash of all those values. Then when nodes are verifying in IBD, they can just multiply by h(c) and they don't have to compute the inverse. A bit more work for the miner and a bit less for the nodes. -Tadge ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation
On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev wrote: > I'm a bit amateur at this sort of thing, but let me try to argue that this > proposal is in fact horribly broken ;) > > Suppose Alice has some UTXO with some money Bob wants to steal. Grant me > that the public key P0 protecting Alice's UTXO is public (say because the > public key has been reused elsewhere). > > Bob going to spend Alice's UTXO by generating random values s0, k0 and R0 > := k0*G and thus creating a random signature for it, [R0, s0]. Now clearly > this signature isn't going to be valid by itself because it is just random. > Bob's goal will be to make a transaction with other inputs such that, while > the individual signatures are not valid, the aggregated signature will be > valid. > If you seed the randomization with every R value (which would come for free if you used, say, the witness root) then Wagner's attack no longer applies. The idea is that no aggregation occurs until a miner produces a block. You have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multiples each s_i by H(witness root || index) or whatever, sums up the s_i's, and commits the sum somewhere where it doesn't affect the root. Verifiers then multiply each R_i by the same multiplying factors and are able to do a batch verification of them. Verifiers who have seen a signature before and cached it as valid can save themselves a bit of time by subtracting H(witness root || index)*s_i from the summed s-value and then skipping R_i in the above step. These are scalar operations and are extremely cheap. They can recognize the signature given only the transaction it signs and R_i, which uniquely determine a valid signature. I believe this is what Tadge was referring to when he mentioned a talk of mine. It's roughly what I've had in mind whenever I talk about non-interactive Schnorr aggregation. Cheers Andrew -- Andrew Poelstra Mathematics Department, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew "A goose alone, I suppose, can know the loneliness of geese who can never find their peace, whether north or south or west or east" --Joanna Newsom signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation
I'm a bit amateur at this sort of thing, but let me try to argue that this proposal is in fact horribly broken ;) Suppose Alice has some UTXO with some money Bob wants to steal. Grant me that the public key P0 protecting Alice's UTXO is public (say because the public key has been reused elsewhere). Bob going to spend Alice's UTXO by generating random values s0, k0 and R0 := k0*G and thus creating a random signature for it, [R0, s0]. Now clearly this signature isn't going to be valid by itself because it is just random. Bob's goal will be to make a transaction with other inputs such that, while the individual signatures are not valid, the aggregated signature will be valid. To do this Bob generates a set of random public keys P1 ... P_n of the form P_i := P0 + r_i*G, and a bunch of random k1 ... k_n with R1 := k1*G ... R_n := k_n*G, such that h(m1, R1, P1) + ... + h(m_n, R_n, P_n) = -h(m0, R0 P0) (modulo the order of the elliptic curve) I understand that this can be done efficiently with Wagner's Generalized Birthday attack. The RHS aggregated signature equation on the private side is k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... - h(m_n, R_n, P_n)(x0 + r_n) with x0 unknown to Bob. Rearranging the terms we get k0 + k1 + ... k_n - [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R_n, P_n)]*x0 - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] However [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R_n, P_n)] is 0 so cancelling that we are left with k0 + k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] which no longer depends on the unknown value x0, so that is good. Bob knows what this value is. Bob creates a set UTXOs by spending to the set of public keys P1 .. P_n. Bob don't know what the private keys are for these public keys, but that is going to be okay. Bob creates a final transaction that takes as input the UTXO of Alice's funds he wants to steal, with public key P0, and also his newly created UTXOs with public keys P1 ... P_n. For the signature on Alice's input he uses [R0,s0]. For the rest of the signature he picks s1 ... s_n such that s0 + s1 + ... + sn = k0 + k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] (which is equal to k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... - h(m_n, R_n, P_n)(x0 + r_n)). and uses signatures [R1, s1] ... [R_n, s_n] on his other inputs. Thus, while none of the individual signatures are valid, the aggregated signature does validate. One wrinkles in this argument is that Bob needs to pick m1 ... m_n before he knows what the transaction will be. I think this can be mitigated by using some combination of SIGHASH_ANYONECANPAY, but I'm not sure if that works. Even if my argument doesn't actually work, I think it is close enough to be pretty scary. Thanks goes to Pieter Wuille for helping explain things to me; however any errors above are my own. On Sun, May 7, 2017 at 2:45 AM, adiabat via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > If / when Schnorr signatures are deployed in a future witness version, it > may be possible to have non-interactive partial aggregation of the > signatures on a per-block basis. This could save quite a bit of space. It > *seems* not to have any security problems but this mailing list is very > good at finding vulnerabilities so that type of feedback is the main reason > I'm writing :) (A quick explanation of why this is horribly broken could > save me lots of time!) > (also sorry if this has been discussed; didn't see anything) > > Quick recap / context of Schnorr sigs: > > There are a bunch of private keys x1, x2, x3... > multiply by generator G to get x1G = P1, x2G = P2, x3G = P3 > > Everyone makes their sighash m1, m2, m3, and their random nonces k1, k2, > k3. > > To sign, people calculate s values: > > s1 = k1 - h(m1, R1, P1)x1 > s2 = k2 - h(m2, R2, P2)x2 > > (adding the P2 into the e hash value is not in most literature / > explanations but helps with some attacks; I beleive that's the current > thinking. Anyway it doesn't matter for this idea) > > Signature 1 is [R1, s1]. Verifiers check, given P1, m1, R1, s1: > > s1G =? R1 - h(m1, R1, P1)P1 > > You can *interactively* make aggregate signatures, which requires > co-signers to build an aggregate R value by coming up with their own k > values, sharing their R with the co-signers, adding up the R's to get a > summed R, and using that to sign. > > Non-interactively though, it seems like you can aggregate half the > signature. The R values are unique to the [m, P] pair, but the s's can be > summed up: > > s1 + s2 = k1 + k2 - h(m1, R1, P1)x1 - h(m2, R2, P2)x2 > > (s1 + s2)G = R1 + R2 - h(m1, R1, P1)P1 - h(m2, R2, P2)P2 > > To use this property in Bitcoin, when making transactions, wallets can > sign in the normal way, and the signature, consisting of [R, s] goes into > the witness stack. When miners generate a block, they remove the s-value > from all compatible