Multisignature and OP

gavinandresen commented at 10:10 pm on November 28, 2011: contributor

This implements BIPS 11, 12, and 13 :

OP_CHECKMULTISIG transactions supported, for up to 3 public keys, as ‘standard’ transactions
OP_EVAL (same opcode as OP_NOP1) as a new opcode
New OP_EVAL-based ‘standard’ transaction type and Bitcoin address
Blocks mined with this patch will have the string “OP_EVAL” in the coinbase scriptSig, so we can tell when a majority of miners support it.
New RPC command to add a multisignature-required address to the wallet: addmultisigaddress <nrequired> <’[“key1”,…]’> [account] (enabled only for use on the -testnet for now)
The ‘validateaddress’ RPC command shows the full public key of addresses in your wallet
Internal changes so if you own all the private keys of a multisignature transaction, then you are able to spend the transaction (and the amount shows up in your balance, and the transaction is listed in listtransactions output)

There is still a lot of work to be done to get multi-device transaction authorization or multi-party escrow; in particular, this pull doesn’t include any support for gathering transaction signatures from multiple places or showing the user transactions that they are involved in but can’t spend without getting more signatures from other devices/people. It just implements the lowest-level support, along with the bare minimum needed to test to make sure the lowest-level stuff is working properly.

To test / play with:

Run bitcoind -daemon -testnet
Get public keys from 2 or 3 new bitcoin addresses– e.g. run this twice: ./bitcoind -testnet validateaddress $(./bitcoind getnewaddress)
Generate a new multisignature address using the public keys from validateaddress– ./bitcoind addmultisigaddress 2 ‘["…public_key_1…","…public_key_2…"]’
Send funds to that address – ./bitcoind sendtoaddress …result of addmultisigaddress… 11.11

Step (4) can be done from another ./bitcoind, either on another machine or same machine, different -datadir, as long as it is running this patch. The coins should show up in the wallet, be listed in listransactions, and you should be able to spend them as if they were single-signature transactions.

Step (2) could be done on two or three different machines, but without more work you’ll have no way to spend coins sent to the resulting multisignature address.

in src/db.h: in d433be2841 outdated

419@@ -420,6 +420,18 @@ public:
420         return Write(std::make_pair(std::string("mkey"), nID), kMasterKey, true);
421     }
422 
423+    bool ReadCScript(const uint160 &hash, std::vector<unsigned char>& data)

mikehearn commented at 11:06 pm on November 30, 2011:

Maybe add comments in keystore.h and db.h indicating why you might want to store scripts keyed by hash in your wallet, as this is not obvious at all given the readers basic mental model of how Bitcoin works.

in src/keystore.h: in d433be2841 outdated

27@@ -28,17 +28,23 @@ public:
28     // This may succeed even if GetKey fails (e.g., encrypted wallets)
29     virtual bool GetPubKey(const CBitcoinAddress &address, std::vector<unsigned char>& vchPubKeyOut) const;
30 
31+    virtual bool AddCScript(const uint160 &hash, const std::vector<unsigned char>& data) =0;

mikehearn commented at 11:07 pm on November 30, 2011:

Same here, consider comments explaining what this is all about and why scripts are keyed by hash. Also, the methods say “AddCScript” but actually take an arbitrary byte buffer - which do you want, scripts or any data? Be consistent.

in src/keystore.h: in d433be2841 outdated

42 // Basic key store, that keeps keys in an address->secret map
43 class CBasicKeyStore : public CKeyStore
44 {
45 protected:
46     KeyMap mapKeys;
47+    DataMap mapData;

mikehearn commented at 11:07 pm on November 30, 2011:

mapData is not a very descriptive name, don’t all maps contain data?

gavinandresen commented at 3:31 am on December 1, 2011:

I hate naming things… must be my Australian roots. I’ll call it Bruce.

in src/main.cpp: in d433be2841 outdated

249+        // in an OP_EVAL, which is 3 ~80-byte signatures, 3
250+        // ~65-byte public keys, plus a few script ops.
251+        if (txin.scriptSig.size() > 500)
252+            return error("nonstandard txin, size %d\n", txin.scriptSig.size());
253+        if (!txin.scriptSig.IsPushOnly())
254+            return error("nonstandard txin: %s", txin.scriptSig.ToString().c_str());

mikehearn commented at 11:08 pm on November 30, 2011:

Maybe state explicitly in these messages why they are considered non-standard (too large, opcodes present)

in src/main.cpp: in d433be2841 outdated

268+// which will get accepted into blocks. The script being
269+// EVAL'ed can be anything; an attacker could use a very
270+// expensive-to-check-upon-redemption script like:
271+//   DUP CHECKSIG DROP ... repeated 100 times... OP_1
272+//
273+bool CTransaction::IsStandardInputs(std::map<uint256, std::pair<CTxIndex, CTransaction> > mapInputs) const

mikehearn commented at 11:09 pm on November 30, 2011:

::AreInputsStandard?

Consider commenting (or using a typedef) that the map key is a tx hash

in src/main.cpp: in d433be2841 outdated

281+        assert(mapInputs.count(prevout.hash) > 0);
282+        CTransaction& txPrev = mapInputs[prevout.hash].second;
283+
284+        vector<vector<unsigned char> > vSolutions;
285+        txntype whichType;
286+        if (!Solver(txPrev.vout[vin[i].prevout.n].scriptPubKey, whichType, vSolutions))

mikehearn commented at 11:11 pm on November 30, 2011:

This is a fairly complex expression, comment what txPrev.vout[vin[i].prevout.n] refers to here (I know it’s obvious if you think about it but it’s easier to read….)

gavinandresen commented at 3:33 am on December 1, 2011:

That (and several of your other line comments here) is SatoshiCode, just moved around. But you’re right, this is a good opportunity to make it easier to read….

in src/main.cpp: in d433be2841 outdated

282+        CTransaction& txPrev = mapInputs[prevout.hash].second;
283+
284+        vector<vector<unsigned char> > vSolutions;
285+        txntype whichType;
286+        if (!Solver(txPrev.vout[vin[i].prevout.n].scriptPubKey, whichType, vSolutions))
287+            return false;

mikehearn commented at 11:11 pm on November 30, 2011:

return error("…")? same for other locations in this function?

in src/main.cpp: in d433be2841 outdated

912+        if (!fFound && (fBlock || fMiner))
913+            return fMiner ? false : error("FetchInputs() : %s prev tx %s index entry not found", GetHash().ToString().substr(0,10).c_str(),  prevout.hash.ToString().substr(0,10).c_str());
914+
915+        // Read txPrev
916+        CTransaction& txPrev = inputsRet[prevout.hash].second;
917+        if (!fFound || txindex.pos == CDiskTxPos(1,1,1))

mikehearn commented at 11:14 pm on November 30, 2011:

What does the magic 1,1,1 mean, maybe this should be a global constant?

gavinandresen commented at 3:34 am on December 1, 2011:

Darn good question. More SatoshiCode (in this case, I think just the indentation level changed).

mikehearn commented at 11:19 am on December 1, 2011:

Yup, sorry, I realize it’s not yours. Just might as well fix up minor things like this whilst there is attention on a particular part of the code.

in src/main.cpp: in d433be2841 outdated

972+                if (fBlock)
973+                {
974+                    // To avoid being on the short end of a block-chain split,
975+                    // interpret OP_EVAL as a NO_OP until blocks with timestamps
976+                    // after opevaltime:
977+                    int64 nEvalSwitchTime = GetArg("opevaltime", 1328054400); // Feb 1, 2012

mikehearn commented at 11:17 pm on November 30, 2011:

Would it be worth allowing the default time to be adjusted using a message signed by you, embedded in a block coinbase?

Alternatively, calculate it dynamically based on the frequency of the coinbase markers?

gavinandresen commented at 3:37 am on December 1, 2011:

Luke-Jr was big on doing something like that. I don’t think the extra code complication is worth it; this is the Simplest Possible Thing That Will Work. Keeping track of frequency, or a signed message, means storing the message somewhere, or storing the frequency somewhere (or recomputing it in LoadBlockChain and recomputing it whenever there’s a new block or a block chain reorg, etc etc etc).

in src/main.cpp: in d433be2841 outdated

2991@@ -2862,6 +2992,12 @@ void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int&
2992     ++nExtraNonce;
2993     pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nTime << CBigNum(nExtraNonce);
2994     pblock->hashMerkleRoot = pblock->BuildMerkleTree();
2995+
2996+    // Put "OP_EVAL" in the coinbase so everybody can tell when

mikehearn commented at 11:18 pm on November 30, 2011:

That’s rather verbose. Why not just have some kind of code prefix like “FM” and then 16 feature bits, in case you want to do this again in future?

gavinandresen commented at 3:40 am on December 1, 2011:

Again, Simplest Possible Thing that will work.

The release after OP_EVAL has majority mining support this code will be removed– I assume the big mining pools aren’t going to remove support for it once they add support for it. The next time with have an OP_EVAL-like change, we’ll lobby miners to put some other string in their coinbases….

in src/script.cpp: in d433be2841 outdated

88+const char* GetOpName(opcodetype opcode)
89+{
90+    switch (opcode)
91+    {
92+    // push value
93+    case OP_0                      : return "0";

mikehearn commented at 11:20 pm on November 30, 2011:

This sort of table is often done with a macro to avoid the possibility of typos.

in src/script.cpp: in d433be2841 outdated

1025+                        return false;
1026+                    valtype& vchScript = stacktop(-1);
1027+                    CScript subscript(vchScript.begin(), vchScript.end());
1028+                    popstack(stack);
1029+                    
1030+                    // Codeseparators not allowed

mikehearn commented at 11:21 pm on November 30, 2011:

Why forbid them?

gavinandresen commented at 4:03 am on December 1, 2011:

Because they don’t make sense inside OP_EVAL’ed code.

Example: scriptPubKey: DUP HASH160 …hash of serialized script… EQUALVERIFY EVAL

Redeemed in a transaction that has: scriptSig: serialized(stuff… CODESEPARATOR CHECKSIG)

So: CHECKSIG takes the part of the scriptPubKey from the last CODESEPARATOR to the end of the scriptPubKey and replaces the scriptSig with that.

But there is no CODESEPARATOR in the scriptPubKey. It is buried inside the scriptSig. The scriptSig that is signed will be DUP HASH160 <hash_of_serialized_script> EQUALVERIFY EVAL

I suppose OP_EVAL could interact with OP_CHECKSIG so the scriptPubKey is rewritten to “expand out” all the OP_EVALs somehow before evaluation so CODESEPARATORS inside the EVAL would make sense… but since I don’t see a use for CODESEPARATOR and since that would add quite a lot of extra code and complication just disallowing CODESEPARATOR inside EVAL’d scripts seems like the correct thing to do.

mikehearn commented at 11:18 am on December 1, 2011:

Makes sense. Best to put the explanation in a comment rather than a code review thread though.

in src/script.cpp: in d433be2841 outdated

69@@ -70,20 +70,187 @@ static inline void popstack(vector<valtype>& stack)
70 }
71 
72 
73-bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)
74+const char* GetTxnTypeName(txntype t)

mikehearn commented at 11:22 pm on November 30, 2011:

These are actually types of scriptPubKeys, not transactions

gavinandresen commented at 4:06 am on December 1, 2011:

Naming again…. GetScriptPubKeyTypeName ? Is there a better term for “part of a transaction that specifies the conditions necessary to redeem” ?

mikehearn commented at 11:17 am on December 1, 2011:

GetOutputType?

in src/script.cpp: in d433be2841 outdated

1559+
1560+    if (typeRet == TX_MULTISIG)
1561+    {
1562+        nRequiredRet = vSolutions.front()[0];
1563+        int n = vSolutions.back()[0];
1564+        for (vector<valtype>::const_iterator it = vSolutions.begin()+1; it != vSolutions.begin()+vSolutions.size()-1; it++)

mikehearn commented at 11:27 pm on November 30, 2011:

this might be clearer using integer indexs

in src/test/script_op_eval_tests.cpp: in d433be2841 outdated

241+
242+    int nUnused = 0;
243+    BOOST_CHECK(VerifyScript(txTo.vin[0].scriptSig, txFrom.vout[0].scriptPubKey, txTo, 0, nUnused, 0, false));
244+
245+    // After eval switchover, it should be considered invalid:
246+    SetMockTime(nEvalSwitchover);

mikehearn commented at 11:35 pm on November 30, 2011:

Do you need to reset the mock time afterwards? Don’t recall how this works.

gavinandresen commented at 4:57 pm on December 1, 2011:

The test fixture resets mock time between tests. Although the mock time doesn’t matter any more– a previous refactoring added Yet Another argument to VerifyScript that controls whether it interprets OP_EVAL as a no-op or not. I’ll fix the test case.

in src/wallet.cpp: in d433be2841 outdated

373@@ -365,6 +374,16 @@ int64 CWallet::GetDebit(const CTxIn &txin) const
374     return 0;
375 }
376 
377+bool CWallet::IsChange(const CTxOut& txout) const
378+{
379+    CBitcoinAddress address;
380+    if (ExtractAddress(txout.scriptPubKey, this, address) && !address.IsScript())
381+        CRITICAL_BLOCK(cs_wallet)
382+            if (!mapAddressBook.count(address))

mikehearn commented at 11:37 pm on November 30, 2011:

That’s a bit confusing. Isn’t there a simpler way to phrase this check?

luke-jr commented at 1:57 am on December 3, 2011: member

NACK

9db95d3 introduces a regression: when you send-to-self, and have to pay a fee, instead of the usual send/receive pair in listtransactions, we now get a second ‘send’ instead of the ‘receive’. This ‘send’ has an amount that appears to be your change from the transaction, shown in negative.

gavinandresen commented at 2:21 am on December 3, 2011: contributor

Nice catch on the listtransactions regression.

Collapse no-op ExtractAddress/ExtractAddressInner 7e55c1ab65

Rework unit tests so test_bitcoin.cpp does not #include them all 1466b8b78a

Support 3 new multisignature IsStandard transactions

Initial support for (a and b), (a or b), and 2-of-3 escrow
transactions (where a, b, and c are keys).

bf798734db

Global fixture to send output to console instead of debug.log cc40ba2151

OP_EVAL implementation

OP_EVAL is a new opcode that evaluates an item on the stack as a script.
It enables a new type of bitcoin address that needs an arbitrarily
complex script to redeem.

e679ec969c

Put OP_EVAL string in coinbase of generated blocks d7062ef1bd

Disable addmultisigaddress if not testnet fae3e2aab6

Interpret OP_EVAL as OP_NOP until Feb 1, 2012 a0871afb2b

Use block times for 'hard' OP_EVAL switchover, and refactored EvalScript

so it takes a flag for how to interpret OP_EVAL.
Also increased IsStandard size of scriptSigs to 500 bytes, so
a 3-of-3 multisig transaction IsStandard.

2a45a494b0

Fix logic for IsChange() for send-to-self transactions. be237c119e

Update bitcoin address numbers for latest luke-jr/sipa scheme 9e470585b3

include util.h to get SecureString definition. 77f21f1583

gavinandresen merged this on Dec 20, 2011

gavinandresen closed this on Dec 20, 2011

ptschip referenced this in commit 42bcdf440c on Jun 15, 2017

laanwj referenced this in commit b586bbd558 on Nov 6, 2019

laanwj referenced this in commit 97b66d34eb on Nov 7, 2019

laanwj referenced this in commit e9c85bb139 on Nov 7, 2019

laanwj referenced this in commit c92f7af618 on Nov 7, 2019

laanwj referenced this in commit 656712fe94 on Dec 9, 2019

laanwj referenced this in commit 4abd92d5c4 on Dec 12, 2019

laanwj referenced this in commit 89c8fe5189 on Jan 2, 2020

laanwj referenced this in commit 66480821b3 on Jan 28, 2020

Losangelosgenetics referenced this in commit de6dde8482 on Mar 12, 2020

backpacker69 referenced this in commit 9a4d4e59a3 on Mar 28, 2021

rajarshimaitra referenced this in commit 47c1762c46 on Aug 5, 2021

DrahtBot locked this on Sep 8, 2021

Multisignature and OP_EVAL support #669