Bitcoin multi-sign and the amount of storage it required

Question

I read the paper "Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security". The authors said that in the optimal threshold signature that they propose, players require just a constant amount of storage, while the previous threshold schemes were not efficient because the number of rounds increase according to the number of players; therefore, also the amount of storage that each player needs increased accordingly.

Now, I am wondering about the amount of storage that each players needs when they use multi-signature scheme? Is it constant or does it increase when the number of player increase?

Answer 1

Didn't find the reference of your text... I'll define usage of multisig and length a bit more generally. With a multisig scheme, you create a "funding" transaction with a redeem script. This redeem script is the hash of the n-of-m multisig identifiers, and the required pub keys. So the funding tx is not bigger than normal tx.

Then spending the multisig, the V_IN structure gets bigger, whereas V_OU remains the same size. Assume a multisig requires n-of-m signatures, and a typical sig looks like this:

48: OP_DATA_0x48:        push hex 48 (decimal 72) bytes on stack
30: OP_SEQUENCE_0x30:    type tag indicating SEQUENCE, begin sigscript
45: OP_LENGTH_0x45:      length of R + S
02: OP_INT_0x02:         type tag INTEGER indicating length
20: OP_LENGTH_0x20:      this is SIG R (32 Bytes)
    4673096ED91CC985:B05F64780BA123E1
    C193FC860B2163DC:B3B5D4F3049F30D2
02: OP_INT_0x02:         type tag INTEGER indicating length
21: OP_LENGTH_0x21:      this is SIG S (33 Bytes)
    00DE2CA5EBBCB5D1:19877AD737930BC5
    7F2356CBAC646405:DC881270CFAE78BF
    1D
01: OP_SIGHASHALL:       terminates ECDSA sig (ASN1-DER structure)

then the first byte already indicating the length of sig (there is comment from me at the top, to a link from Pieter Wuille, explaining length of Sigs to be 71 or 72 Bytes long). Additionally to the added signatures you have also the redeem script added to the tx, behind the signatures in the V_IN structure. The redeemscript has in a 2-of-3 music the typical structure: <2><3> Now it depends, if you use compressed or uncompressed pub keys (33 or 66 Bytes long). This increases your overall length of the tx. Summary for spending funds with a bitcoin tx:

normal tx has 1 sig          (at ~70 Bytes) and 1 pub key  (@ 33 or 66 bytes) 
multisig has  n (-of-m) sigs (at ~70 Bytes) and m pub keys (@ 33 or 66 bytes)