Bitcoin Forum
December 09, 2016, 01:59:38 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: OP_CHECKMULTISIG - how does it work?  (Read 2127 times)
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 23, 2011, 06:10:33 PM
 #1

Firstly, what's the correct syntax? The comment in the code says

Code:
([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)

but how many signatures are present in [sig ...]? Is num_of_signatures the actual number of signatures provided or is it the number of valid signatures required for OP_CHECKMULTISIG to return true?

I'm reading the code for OP_CHECKMULTISIG in script.cpp. It allows for fewer signatures than public keys but seems to iterate through both the signatures and public keys without any attempt to find out which ones are missing. I don't see how this could work for even a 1 of 2 multisignature transaction in both cases where, in the first case the signature matches the first public key and in the second case the signature matches the second public key.

Even if both signatures are provided but one is just invalid, the verification will fail as nSigsCount will only be 1 and if the first verification fails, the other will not even be attempted.

Can anyone explain please? The issue is becoming relevant...

ByteCoin
1481291978
Hero Member
*
Offline Offline

Posts: 1481291978

View Profile Personal Message (Offline)

Ignore
1481291978
Reply with quote  #2

1481291978
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481291978
Hero Member
*
Offline Offline

Posts: 1481291978

View Profile Personal Message (Offline)

Ignore
1481291978
Reply with quote  #2

1481291978
Report to moderator
1481291978
Hero Member
*
Offline Offline

Posts: 1481291978

View Profile Personal Message (Offline)

Ignore
1481291978
Reply with quote  #2

1481291978
Report to moderator
1481291978
Hero Member
*
Offline Offline

Posts: 1481291978

View Profile Personal Message (Offline)

Ignore
1481291978
Reply with quote  #2

1481291978
Report to moderator
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2506


View Profile
August 23, 2011, 06:57:13 PM
 #2

If ScriptPubKey says:
Code:
2 KeyA KeyB KeyC 3 OP_CHECKMULTISIG
Then ScriptSig must provide signatures for exactly two of A-C, listed in order.

If ScriptPubKey says:
Code:
1 KeyA KeyB KeyC 3 OP_CHECKMULTISIG
Then ScriptSig must only provide one of A-C.

It's not sane to allow the scriptSig to provide the sig count, since it would be legal for them to set it to 0.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 23, 2011, 07:10:57 PM
 #3

Got it! Thanks! Seems obvious how the code works now. I don't know what I was thinking before!

listed in order.

This is what did it for some reason....

Anyway, so that this thread isn't a complete waste of time I'd like to observe that the current way of matching signatures to public keys is very wasteful of computation. For example, if you have a 1 of 100 multisignature then the code goes through the public keys sequentially trying to verify the signature until it either succeeds or runs out of public keys. As each transaction is verified each time it is relayed, wouldn't it make sense to indicate in the scriptSig the number of public keys to skip before attempting to verify the signature. This could be an (optional?) 1 byte parameter which would save a very large number of unnecessary signature verification attempts.

ByteCoin
jackjack
Hero Member
*****
Offline Offline

Activity: 882


May Bitcoin be touched by his Noodly Appendage


View Profile
August 23, 2011, 08:31:37 PM
 #4

Got it! Thanks! Seems obvious how the code works now. I don't know what I was thinking before!

listed in order.

This is what did it for some reason....

Anyway, so that this thread isn't a complete waste of time I'd like to observe that the current way of matching signatures to public keys is very wasteful of computation. For example, if you have a 1 of 100 multisignature then the code goes through the public keys sequentially trying to verify the signature until it either succeeds or runs out of public keys. As each transaction is verified each time it is relayed, wouldn't it make sense to indicate in the scriptSig the number of public keys to skip before attempting to verify the signature. This could be an (optional?) 1 byte parameter which would save a very large number of unnecessary signature verification attempts.

ByteCoin
Non-standard transaction, thus never relayed
Problem solved

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 23, 2011, 08:42:32 PM
 #5

Non-standard transaction, thus never relayed
Problem solved

It looks like it was necessary for me to qualify that the whole thread presupposes that a template allowing OP_CHECKMULTISIG in a transaction is added to the "standard" list for some reason in the near future.

ByteCoin
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
August 23, 2011, 09:02:02 PM
 #6

I've been working on a proposal to enable {1,2}-of-{1,2,3} signatures-required as standard transaction types.

I'll start another thread with more information...

How often do you get the chance to work on a potentially world-changing project?
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!