Topic: What is the upper limit of 'm' and 'n' for m-of-n transactions? (Read 2328 times)

1. I'm not sure what you mean by "escrow form." In plain M-of-N the public keys are known to the network when funds are sent to them. In P2SH only the hash of these public keys is known. To create a Tx that spends these funds, one must know which public keys those were and also sign with the private keys. One person could collect public keys and create a P2SH address in which the other public key owners don't know about each other. The would have to trust this person to not create a different P2SH address and all owners would find out about each other's public keys when funds are spent from that address.

2. In plain M-of-N, the public key is known. In P2SH M-of-N, one must know the public keys to spend the funds. If you have a list of possible public/private keys, you have to try every possible combination. You don't even know what M and N are. This is why users of P2SH need to also store the output script (which contains the public keys) for that address.

3. They are trying to create an output script, which has public keys in it in some order, that hashes to the P2SH address.These keys are not publicly viewable on the blockchain unless funds have been spent from the address before.

4. A P2SH address is the hash of an output script. In M-of-N the output script looks like "M ... M OP_CHECKMULTISIG". When a Tx spends funds from the address, nodes check that it contains the output script by checking the hash of it against the address and then check that the signatures match the public keys. When someone sends funds to a P2SH address, they are essentially saying "any script that hashes to this hash can redeem these funds." That script doesn't have to be M-of-N (though it may be non-standard if it isn't).

Thank you this is very helpful.

Am I correct in thinking:

1. An m-of-n transaction is signed in series because the public keys are appended to the escrow form as each party signs so this total set of keys can be logged to the transaction in the blockchain? If this is the case then surely an overseer could have a selection of escrows sign in parallel and then collate these keys into the escrow form, thereby preventing each escrow of having any knowledge of who the other escrows are and what other keys are involved in the transaction?

2. Is there any way to see if a single private key goes with a multi-signature transaction? I.e. could an attacker try single keys from a multi-signature transaction in sequence to see if it is associated with a given multi-signature transaction or do all the keys have to be used together to see if they are for a given multi-signature transaction?

3. Assuming the latter is true for Q2, to undertake this brute-force attack is the attacker trying to match a single value generated from all the keys that is publicly viewable on the blockchain or do they have to submit a request to the network for each attempt?

4. I've read up on P2SH (pay-to-script-hash) but don't fully understand it yet. Is it a number (hash) representing all the signatures for a multi-signature transaction where just that number is stored on the blockchain, resultantly keeping the set of public keys used for that multi-signature transaction obfuscated?

Yes it is trivially easy.  The 20 public keys are known.  If they weren't how would the Bitcoin network validate the transaction.  If the attacker has 100 keys he computes the 100 public keys and within miliseconds locates the ones which are used in the transaction.

On edit:  TAC brought up a good point.  If the P2SH script is unknown then the attacker may be unable to brute force the proper keys however I can't really imagine a scenario where the private keys would be compromised but the p2SH script isn't.  I mean if that is the case whatever you did to keep the P2SH script safe ... do that to keep one or more of the private keys safe.

It depends. If funds had been sent in an M-of-N transaction with the output script exposing the public keys, the attacker can select the 20 private keys which belong to those public keys and create a new transaction spending the funds to himself. If the funds had been sent to a P2SH (pay-to-script-hash) address, and no funds have ever been spent FROM that address, then the attacker only knows the hash of the 20 public keys. In that case, he would have to brute-force it, trying every subset of 20 public keys from the 100. It turns out there are about 5.4 * 10^20 possible subsets, so it might not be possible to brute force in a reasonable time.

Scenario:

A 20-of-20 transaction is set up.

This 20-of-20 transaction exists in a pool of 100 escrow agents. The other 80 escrow agents each hold a key for other separate m-of-n transactions.

A malicious entity somehow infiltrates this pool and is able to access all 100 escrow keys for the m-of-n transactions, where a sub set of 20 of the keys are for the 20-of-20 transaction in question.

Would the malicious entity be able to identify which of those 100 escrow keys were associated with the same 20-of-20 transaction? Or are the keys impossible to correlate if the entity does not know which transactions they relate to?

In series but the order doesn't matter. Can't be parallel.

Thanks, so when the 20-of-20 transaction is set up do the escrows involved in it need to sign the 20-of-20 transaction request in series or can this be done in parallel?

The order never matters.  20 of 20 simply means all 20 keys must sign.  1 of 20 means any 1 of 20 can sign. 10 of 20 means ANY 10 of 20 can sign.

Private keys aren't formed by anything.  They are private keys (random 256 bit numbers).    Multi-sig simply requires/allows more than one private key to be used.

So for a 20-of-20 transaction does the order of signing to access funds at the destination address matter?

If so this would be a large number of combinations if the order were not known.

Are the private keys formed by the escrows in series or parallel?

Your wording seems to indicate you don't understand the concept of n of m.

1) There are no "part-private-keys.  A 2 of 20 setup means there are 20 valid private keys.
2) In a 2 of 20 setup there is no concept of order.  One just needs to sign a transaction with ANY 2 of the 20 VALID private keys to produce a valid transaction.

There is reassembled of private keys.

For example a "standard" transaction is a 1 of 1 transaction.  There is one private key.  The transaction must be signed by the one private key to be valid.
In a 1 of 2 transaciton there are 2 valid (unique and independent) private keys.  The transaction is valid if it is signed by ANY ONE of the TWO valid keys.
In a 10 of 10 transaction there are 10 valid (unique and independent) private keys.  The transaction is valid if it is signed by ALL TENS of the TEN valid keys.

TalkingAntColony, malevolent and scintill; thank you very much - for a person who can only read source code to a rudimentary level these answers are very concise. Much appreciated.

A further question: if a 2-of-20 transaction was split up amongst 18 escrow (I assume 18 as two parties are transacting) and one of the two parties gained access to all 18 escrow's private-part-keys, without knowing the order the 2-of-20 transaction was signed in by the escrows: would the party with the part-private-keys be able to infer the order those keys needed to be reassembled in or would they have to try all the possible combinations?

Only up to x-of-3 are standard.  As mentioned earlier 20 is the hard limit, but only up to 3 is by default relayed and mined.

Yes, but the limits are like the one you posted few posts above and exceeding them would render a transaction non-standard.

And also:

M-of-N are now a standard Tx, and thus relayed/mined.

See here:

https://en.bitcoin.it/wiki/BIP_0011
https://en.bitcoin.it/wiki/BIP_0016

I think currently the limits are the relay nodes which might not relay non-standard transactions and miners which might not include them in blocks.

M-of-N signatures are checked in scripts by OP_CHECKMULTISIG

It is limited to 20 public keys, so the limit of M and N is 20.
Source: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L871

The limit exists out of concern for limting the size and computational complexity of transactions. Private keys are not divided in M-of-N transactions. Rather, there are N private keys, of which M need to sign the transaction for it to be valid.

My incomplete understanding of how m-of-n transactions work is that the public keys are split up and spread between the parties involved.

Satoshi, in his infinite wisdom, has abstracted this mechanism so that 'm' part-keys are required from a set of 'n' participants to be able to form the complete private key to be able to access the funds in a given address.

My question is: what are the upper limits on 'm' or 'n'?

If a limit does exist is this in any way connected to the fact that the private keys can only be divided so much?