Cached hashes

[NicolasDorier]

I am using a shared map<txid,cachedhashes> protected by a lock. A hash may be calculated several time because there is no lock at the transaction level.

[theuni]

A few issues:

• libbitcoinconsensus needs to be boost/lock free. Is it necessary to have caching there?
• Looks like there's an out-of-bounds access of vtxinwit in the tx_valid test. I don't see how you would've caused that, though.

[NicolasDorier]

@theuni this is not out of bound as https://github.com/sipa/bitcoin/blob/segwit/src/primitives/transaction.h#L298 resize the witscript to the length of inputs.

I'll think today about a way to remove the lock out of the consensus path. There may be a way.

[theuni]

@NicolasDorier There's an out-of-bounds somewhere: https://travis-ci.org/sipa/bitcoin/jobs/120930116#L5390

Maybe it's caused by a new test?

[NicolasDorier]

Wow very strange the tests passed on my machine. I will add a check just to be sure.

Is there any compile debug flag which would have make me catch such error ?

[NicolasDorier]

@theuni I addressed both of your concern. Can you check if it is ok for you now ? I'm also wondering why I did not have the out of bound error on my local dev machine. I could not check with Travis, because travis crash on a non determistic test fixed by https://github.com/bitcoin/bitcoin/commit/fa3fafc96076afb15fa77e01d5f6aff88a333a7e . (not merged to segwit for now)

For people wanting to benchmark the time difference with and without cache, you can check with the following code in big witnesss test:

int64_t before = GetTimeMicros();
for(uint32_t i = 0; i < mtx.vin.size(); i++) {
    std::vector<CScriptCheck> vChecks;
    CScriptCheck check(coins, tx, i, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, false, &cachedHashesMap);
    vChecks.push_back(CScriptCheck());
    check.swap(vChecks.back());
    control.Add(vChecks);
}

bool controlCheck = control.Wait();
assert(controlCheck);

int64_t after = GetTimeMicros();
BOOST_CHECK_MESSAGE(false, (after - before) * 0.000001);

before = GetTimeMicros();

for(uint32_t i = 0; i < mtx.vin.size(); i++) {
    std::vector<CScriptCheck> vChecks;
    CScriptCheck check(coins, tx, i, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, false, NULL);
    vChecks.push_back(CScriptCheck());
    check.swap(vChecks.back());
    control.Add(vChecks);
}

 controlCheck = control.Wait();
assert(controlCheck);

after = GetTimeMicros();

BOOST_CHECK_MESSAGE(false, (after - before) * 0.000001);

[sipa]

@NicolasDorier By default, libc does not do bounds checks for vector accesses.

[NicolasDorier]

I am thinking about adding an overload to VerifyScript of libconsensus to provide a way to the user to specify CachedHashes so libconsensus user can protect themselves against the O(n²) problem. What do you think ? should I do it ? if yes, in this PR ?

[NicolasDorier]

I gave up changing libconsensus for now I did this: a807f422fe649c9ccbc218e495388221e623bea9 which can be useful for later. (after first release of segwit) The problem with such commit was that it exposed internal plumbing to the API. I explored solutions, but it would have meant that the "cache object" would not be thread safe, making a burden to the caller.

5:28 PM <sipa> honestly i think we should revamp the consensus api after c++11, and have it expose contexts for block, transaction, and script validation
5:28 PM <sipa> which maintain the caches
5:28 PM <sipa> and have locks internally

[NicolasDorier]

rebased on segwit4 https://github.com/sipa/bitcoin/pull/70