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.

@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.

@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?

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 ?

@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 bitcoin@fa3fafc . (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);

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 ?

I gave up changing libconsensus for now I did this: a807f42 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

rebased on segwit4 #70