What are Borromean signatures?

Question

For more background info visit GitHub or Bitcointalk

It looks like borromean signatures are going to be replacing schnorr signatures in the RingCT hardfork. What does this mean for Monero and RingCT performance etc? thanks

Answer 1

I happened to have read Greg Maxwell's paper recently, so here I try to lay down my interpretation in a bit abstract manner:

Before talking about the Borromean scheme, let us recapitulate the current ring signature scheme described in MRL-0005. The signature data looks like:

R = (M, {P_1,...,P_n}, c_1, {r_1,...,r_n})

where M is some message's hash, each P_i is a pubkey in the ring, and c_1 and r_i are scalars (the key image part is omitted here for brevity). Any participant in the network verifies this signature as follows:

L_1 = c_1 P + r_1 G
c_2 = H(M, L_1)               // H(...) is a hash function
...
L_i = c_i P + r_i G
c_{i+1} = H(M, L_i)
...
L_n = c_n P + r_n G

Finally, the signature is confirmed as valid if c_1 = H(M, L_n). I skip explaining how such a signature can be generated only by a true signer knowing the secret key x of one of the pubkeys P_s = xG for some secret index 1<=s<=n.

A transaction generally has multiple inputs, say m inputs, so you create a ring signature for each input:

R^j = (M, {P_1^j,...,P_n^j}, c_1^j, {r_1^j,...,r_n^j})

for j=1,...,m. Note that the signature contains m*(n+1) scalars of c's and r's. Note also that such a concatenation of multiple ring signatures is needed for RingCT when proving that a given committed amount is within a certain range (called range proof).

The goal of the Borromean ring signature scheme is to reduce the signature size by making all c_1^j's identical:

c_1^1 = c_1^2 = ... = c_1^m
      = c_1

so that the number of scalars stored in the signature becomes m*n+1.

To achieve this goal, the scheme modifies the verification rule a little bit. As before, the verifier computes for each j=1,...,m:

c_1 -> L_1^j -> c_2^j -> ... -> c_n^j -> L_n^j

and the signature is confirmed valid if the following holds:

c_1 = H(M, L_n^1, ..., L_n^m)

The signature generation can be implemented by adding some small modifications to the original scheme (I believe).