Cache hashes

NicolasDorier commented at 1:57 am on July 29, 2016: contributor

Alternative of #8259 as advised by @sipa. Mid hashes are calculated lazily instead of aggressively.

NicolasDorier commented at 2:00 am on July 29, 2016: contributor

test_big_witness_transaction add significant test duration because of the creation of many signature, I don’t feel like removing it as it may still be useful though.

NicolasDorier force-pushed on Jul 29, 2016

NicolasDorier commented at 3:34 am on July 29, 2016: contributor

travis fail probably unrelated to this PR

laanwj added the label Validation on Jul 29, 2016

in src/main.cpp: in 6c52333c6a outdated

1929+                                scriptPubKey.IsWitnessProgram(version, program) &&
1930+                                !cachedHashesMap->TryGet(this->ptxTo->GetHash(), &cachedHashes);
1931+    addCachedHashesToMap &= !cachedHashes.IsFull();
1932+    bool result = VerifyScript(scriptSig, scriptPubKey, witness, nFlags, CachingTransactionSignatureChecker(ptxTo, nIn, amount, cacheStore, cachedHashes), &error);
1933+    // do not update the cache if cachedHashes is still empty, it can happen if the evaluation ends before any segwit CheckSig operation could run
1934+    addCachedHashesToMap &= !cachedHashes.IsEmpty();

instagibbs commented at 1:01 pm on July 29, 2016:

Might make sense to check if any “progress” was made instead to avoid grabbing locks for setting any time the retrieved cachedHashes isn’t empty already.

NicolasDorier force-pushed on Jul 29, 2016

NicolasDorier commented at 5:14 pm on July 29, 2016: contributor

@instagibbs I’ve just updated the PR following your suggestion.

NicolasDorier force-pushed on Jul 29, 2016

sipa commented at 7:06 pm on July 29, 2016: member

You’re making script/interpreter depend on sync, which causes a compile failure as libconsensus (which uses script/interpreter) does not link in Boost.

One way would be to make CachedHashesMap a virtual class, with only a naive implementation (which does not cache anything). Then elsewhere you can create a derived class which adds the map and the lock.

EDIT: oh no, I think you just need to stop including cachedhashesmap.h from interpreter.h. EDIT2: verified, this is what causes the build failure.

sipa commented at 7:40 pm on July 29, 2016: member

Can you also follow the coding style? Spaces after if, and { on the same line (except for classes or function bodies).

NicolasDorier force-pushed on Jul 29, 2016

NicolasDorier commented at 7:52 pm on July 29, 2016: contributor

@sipa yes, it was a mistake just removed it and fixed coding style.

I am suprised, that https://travis-ci.org/bitcoin/bitcoin/builds/148371080 and when I compiled myself I did not experienced any build fails because of this mistake.

sipa commented at 7:54 pm on July 29, 2016: member

Did you run make check ?

NicolasDorier commented at 7:54 pm on July 29, 2016: contributor

nop, only make -j4. What does the check do ? I thought it was only running tests.

in src/main.cpp: in 16bc578300 outdated

1927+    std::vector<unsigned char> program;
1928+    // if the cache map is available, and we get a cache miss, then we'll need to update the cache later
1929+    // if the scriptPubKey is not witness program, no need for cachedHashes, so do not read the map (it would acquire the lock needlessly)
1930+    bool addCachedHashesToMap = cachedHashesMap != NULL &&
1931+                                scriptPubKey.IsWitnessProgram(version, program);
1932+    if(addCachedHashesToMap) {

sipa commented at 11:30 pm on July 29, 2016:

Space after if.

in src/main.cpp: in 16bc578300 outdated

1934+    }
1935+    CachedHashes originalCachedHashes = cachedHashes;
1936+    bool result = VerifyScript(scriptSig, scriptPubKey, witness, nFlags, CachingTransactionSignatureChecker(ptxTo, nIn, amount, cacheStore, cachedHashes), &error);
1937+    // do not update the cache if cachedHashes if it has not been updated
1938+    addCachedHashesToMap &= !(originalCachedHashes == cachedHashes);
1939+    if(addCachedHashesToMap) {

sipa commented at 11:30 pm on July 29, 2016:

Space after if.

in src/script/cachedhashesmap.cpp: in 16bc578300 outdated

21+    auto iter = map.find(txId);
22+    if (iter == map.end())
23+        map.insert(std::pair<uint256, CachedHashes>(txId, hashes));
24+    else
25+        iter->second.Merge(hashes);
26+}

sipa commented at 11:31 pm on July 29, 2016:

Newline at the end of the file.

in src/script/cachedhashesmap.cpp: in 16bc578300 outdated

17+
18+void CachedHashesMap::TrySet(uint256 txId, const CachedHashes& hashes)
19+{
20+    LOCK(cs);
21+    auto iter = map.find(txId);
22+    if (iter == map.end())

sipa commented at 11:31 pm on July 29, 2016:

This whole method can be written as LOCK(cs); map[txId].Merge(hashes);.

in src/script/cachedhashesmap.h: in 16bc578300 outdated

18+{
19+private:
20+    std::map<uint256, CachedHashes> map;
21+    CCriticalSection cs;
22+public:
23+    bool TryGet(uint256 txId, CachedHashes* hashes);

sipa commented at 11:32 pm on July 29, 2016:

Can you pass the uint256 as a const reference to avoid copying it?

in src/script/cachedhashesmap.cpp: in 16bc578300 outdated

0@@ -0,0 +1,26 @@
1+// Copyright (c) 2009-2010 Satoshi Nakamoto

sipa commented at 11:33 pm on July 29, 2016:

Satoshi did not write this.

in src/script/interpreter.h: in 16bc578300 outdated

 97@@ -98,13 +98,33 @@ enum
 98 
 99 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
100 
101+class CachedHashes

sipa commented at 11:33 pm on July 29, 2016:

You can turn this into a struct and drop the public: declaration.

in src/script/interpreter.h: in 16bc578300 outdated

152@@ -133,12 +153,14 @@ class TransactionSignatureChecker : public BaseSignatureChecker
153     const CTransaction* txTo;
154     unsigned int nIn;
155     const CAmount amount;
156+    mutable CachedHashes* cachedHashes;

sipa commented at 11:50 pm on July 29, 2016:

This mutable isn’t needed.

NicolasDorier commented at 4:06 am on July 30, 2016:

it is CachedHashes is modified by SignatureHash

sipa commented at 4:15 am on July 30, 2016:

it is CachedHashes is modified by SignatureHash

I don’t think so? cacheHashes is not modified. *cacheHashes is.

If you have a const TransactionSignatureChecker method, its cacheHashes variable is of type const pointer to non-const CachedHashes. It means the pointer can’t be changed, but the object pointed to can be.

NicolasDorier commented at 4:17 am on July 30, 2016:

oh, it is not needed, by which magic. I remember having to add it because I was modifying it in SignatureHash, why not anymore?

in src/test/transaction_tests.cpp: in 16bc578300 outdated

503+    threadGroup.join_all();
504+}
505+
506 BOOST_AUTO_TEST_CASE(test_witness)
507 {
508+    ScriptError serror;

sipa commented at 11:53 pm on July 29, 2016:

Unused variable.

NicolasDorier force-pushed on Jul 30, 2016

NicolasDorier commented at 4:22 am on July 30, 2016: contributor

@sipa nits fix

sipa commented at 6:06 pm on July 30, 2016: member

utACK 5547521c0ae38583e9f0504b3302bba928f5477d Will test.

MarcoFalke added the label Needs backport on Jul 31, 2016

sipa commented at 2:47 pm on August 1, 2016: member

Needs rebase.

NicolasDorier force-pushed on Aug 1, 2016

NicolasDorier commented at 3:11 pm on August 1, 2016: contributor

Rebased, it made the diff smaller as this commit removed a code path where CachedHashesMap was previously needed. (but not used)

sipa commented at 11:26 pm on August 2, 2016: member

Noting that this requires backport to 0.13 before segwit is activated.

in src/script/cachedhashesmap.h: in 7dbd2e7df5 outdated

0@@ -0,0 +1,27 @@
1+// Copyright (c) 2009-2015 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#ifndef SRC_CACHEDHASHESMAP_H
6+#define SRC_CACHEDHASHESMAP_H
7+
8+
9+#include "script/interpreter.h"

jtimon commented at 1:32 am on August 4, 2016:

You can move this include to the cpp or save the class CachedHashes; below.

in src/script/bitcoinconsensus.cpp: in 7dbd2e7df5 outdated

83@@ -84,8 +84,8 @@ static int verify_script(const unsigned char *scriptPubKey, unsigned int scriptP
84 
85         // Regardless of the verification result, the tx did not error.
86         set_error(err, bitcoinconsensus_ERR_OK);
87-
88-        return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), nIn < tx.wit.vtxinwit.size() ? &tx.wit.vtxinwit[nIn].scriptWitness : NULL, flags, TransactionSignatureChecker(&tx, nIn, amount), NULL);
89+        CachedHashes cachedHashes;
90+        return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), nIn < tx.wit.vtxinwit.size() ? &tx.wit.vtxinwit[nIn].scriptWitness : NULL, flags, TransactionSignatureChecker(&tx, nIn, amount, cachedHashes), NULL);

jtimon commented at 1:34 am on August 4, 2016:

Style: Maybe we want a variable for TransactionSignatureChecker here at some point?

jtimon commented at 1:54 am on August 4, 2016: contributor

utACK 7dbd2e7

in src/script/cachedhashesmap.cpp: in 7dbd2e7df5 outdated

0@@ -0,0 +1,21 @@
1+// Copyright (c) 2009-2015 The Bitcoin Core developers

btcdrak commented at 10:56 am on August 5, 2016:

s/2015/2016/

in src/script/cachedhashesmap.h: in 7dbd2e7df5 outdated

0@@ -0,0 +1,27 @@
1+// Copyright (c) 2009-2015 The Bitcoin Core developers

btcdrak commented at 10:56 am on August 5, 2016:

s/2015/2016/

btcdrak commented at 10:57 am on August 5, 2016: contributor

utACK 7dbd2e7

Cache hashes 910e7bb0fc

NicolasDorier force-pushed on Aug 5, 2016

NicolasDorier commented at 8:49 pm on August 5, 2016: contributor

@btcdrak updated the file header.

sipa commented at 5:17 pm on August 15, 2016: member

Tested ACK 910e7bb0fc519eacca6aff996dec31e9f0185bc8: I timed the verification in the added test_big_witness_transaction test, and backported it to master (without sighash cache); this PR made it 7.5 times faster.

sipa added this to the milestone 0.13.1 on Aug 15, 2016

sipa commented at 10:18 am on August 16, 2016: member

Merely listing this for exposure, as I am perfectly fine with merging this PR here as it is:

I made an altered implementation in https://github.com/sipa/bitcoin/commits/noprecomputecachedhashes that simply precomputes the 3 hashes for each transaction. In the listed benchmark, it is around 1% faster than the PR here. It may be preferable if we want to avoid contention on the sighash cache like in #8464.

NicolasDorier commented at 12:29 pm on August 16, 2016: contributor

@sipa actually I did that before (https://github.com/bitcoin/bitcoin/pull/8259)

EDIT: ah no, it is actually different

NicolasDorier commented at 12:35 pm on August 28, 2016: contributor

supersede by #8524

NicolasDorier closed this on Aug 28, 2016

MarcoFalke removed the label Needs backport on Sep 9, 2016

DrahtBot locked this on Sep 8, 2021

Cache hashes #8422