# What are Borromean signatures?

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

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).

• So basically that would decrease transaction size right? Verification faster etc? Dec 9, 2016 at 5:12
• Yes, the signature size (included in the tx data) becomes smaller. The verification time will also become slightly faster, technically speaking, since a single hash function call is needed for `c_1` (as opposed to `m` calls for `c_1^j`). Dec 9, 2016 at 5:15
• What sort of impact will this have on ringct transaction size? Is it a constant reduction, or is it proportional to the mixin? Dec 9, 2016 at 11:25
• It's inverse proportional to mixin; with `m` inputs and `n-1` mixin, the signature size changes from `m*(n+1)` to `m*n+1`, so the reduction ratio would be `((m*n+m)-(m*n+1)) / (m*n+m) = (m-1) / (m*n+m)`. For example, with `m=3, n=5`, the reduction is 11%. The real impact would be for the range proof where `m=64, n=2` and the reduction is 33%. Dec 9, 2016 at 11:57
• Note that it's not an effective size change at all. Borromean replaced ASNL in the Monero codebase, which had a problem in its proof, but was the same size. It would be a size reduction if it were replacing certain other types. Dec 9, 2016 at 20:40