Cache hashes #8422

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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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:None 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