10

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

10

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? – samwellj Dec 9 '16 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). – kenshi84 Dec 9 '16 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? – expez Dec 9 '16 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%. – kenshi84 Dec 9 '16 at 11:57
  • 3
    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. – Luigi Dec 9 '16 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.