Pay to Script Hash (P2SH, BIP16) addresses/contracts are vulnerable to a 2^80 collision attack which can also be performed with trivial memory usage in 2^82. The attack is made possible if the attacker can introduce data to a contract without being forced to pre-commit to the introduced data. (This problem has been mentioned before on BCR, but it’s probably time for a dedicated topic.)
Common single-signature addresses are not affected. (Pay to Public Key Hash, P2PKH)
Practically all multi-party contracts (P2SH) are vulnerable unless the wallet software uses a carefully implemented pre-commitement scheme: when creating the wallet, the parties must share a hash of their public keys before revealing actual public keys. This prevents any party from grinding for a collision that allows them to later sweep the wallet.
Further, because many kinds of contracts cannot practically implement the above pre-commitment scheme (e.g. if users can “join” or otherwise provide new data to a contract after it is initially funded):
- Practically all contracts that accept new data after contract creation are vulnerable, e.g. many kinds of delayed-withdrawal vaults and most public covenants like crowdfunding/assurance contracts and decentralized oracles/autonomous organizations.
This attack is still only practical/profitable against large wallets because it requires significant investment in hardware and/or electricity, but it’s also more profitable with scale (e.g. building ASICs). I’m not the right person to estimate cost, but it seems safest to assume an attack can be made profitable against vulnerable setups holding as little as a few hundred thousand (2021) USD in value. (Can anyone offer a more substantiated estimate? Note also, the fact that we’re discussing solutions is protective in that it reduces the expected value of attack infrastructure.)
Bitcoin Cash contracts are becoming much more useful in May 2022 with introspection and 64-bit math – use cases like long/hedge derivatives and recurring payments become much more efficient, and we can now build far more secure wallets. While many of these use cases can be carefully implemented to prevent the attack, pre-commitment strategies are also impractical for some important use cases (e.g. decentralized oracles). Even for use cases with viable pre-commitment strategies, these strategies can require both larger contracts and larger transaction sizes than would be required if a 32-byte P2SH solution were available. (And with current VM limits, that means some valuable use cases are also not possible to make secure.)
Additionally, because designing and auditing implementations of pre-commitment schemes is not trivial (even for simple multi-signature wallets), a 32-byte P2SH solution would be valuable for improving the overall security of the ecosystem, reducing the chance that an average BCH user is impacted by a vulnerability in one of their preferred wallets or applications. (When an opportunity arises to eliminate a class of vulnerabilities, we should take it.)
Finally, any solution here should not affect existing, 20-byte P2SH applications – simple multi-signature wallets may choose to continue using 20-byte P2SH in cases where a pre-commitment scheme is easily implemented, saving the additional 12 bytes per output.
The Bitcoin Cash VM currently supports hashing algorithms with two output lengths:
- 20 bytes (160 bits):
- 32 bytes (256 bits):
The existing 20-byte P2SH uses
OP_HASH160 (one pass through
SHA256, then a pass through
RIPEMD160), so the simple solution is to add a 32-byte P2SH construction which uses
OP_SHA256. Because the existing P2SH feature is already implemented using pattern matching (and changing that would break many contracts/clients), implementing a 32-byte P2SH using the same strategy costs very little in terms of additional protocol complexity.
The CashAddress format also offers a simple, existing solution for representing 32-byte P2SH addresses – the
Version byte has 3 bits devoted to
Size, where a value of
0b011) is already specified to represent
256 bit (32-byte) hashes. In fact, 32-byte P2SH CashAddresses have been in the test vectors and implemented in many libraries since 2018, in anticipation of some future solution to this issue.
Given all of this existing infrastructure – an existing hashing algorithm by which the attack is mitigated (
OP_SHA256), an existing P2SH implementation/deployment strategy to reuse, and an existing 32-byte P2SH address format, there are surprisingly few technical decisions left to make.
All that to say: I think we should hammer out the details and deploy 32-byte P2SH in 2023.
Before I put together a CHIP, I’d appreciate any thoughts on some of these technical details I’m considering:
I’d like to see boolean malleability resolved for 32-byte P2SH contracts – that would eliminate the remaining known sources of third-party transaction malleability, paying dividends in practical security for average users over the coming decade(s). (This was considered for the Nov. 2019 upgrade, but deemed better to leave for a future upgrade.)
In practice, eliminating boolean malleability means simpler, safer-by-default, easier-to-audit contracts, less error-prone wallet implementations, and reduced transaction sizes (e.g. this merkle tree leaf replacement construction would save ~3 bytes per level by eliminating the need for the extra malleability protection code). An incomplete solution (the
MINIMALIF flag) has been present in most Bitcoin Cash implementations since before 2017, and is now part of consensus on other networks (BTC after BIP342).
Deploying this for 32-byte P2SH contracts offers immediate security gains: phasing in malleability protection for existing P2SH contracts would probably require multiple years (first with standardness, then consensus), but if boolean malleability is eliminated at the outset for 32-byte P2SH contracts, new development can completely avoid having to handle that class of vulnerabilities. (And I think we should also consider phasing protection into P2SH via standardness over the next few years.)
Existing P2SH contracts use
OP_HASH160 ... OP_EQUAL, so it’s easy to assume
OP_HASH256 ... OP_EQUAL is the proper 32-byte equivalent. However, length extension attacks are not relevant to P2SH, so there’s no reason to spend an extra SHA256 digest iteration on 32-byte script hashes. (See also: BTC’s
P2WSH uses single-SHA256.)
P2SH contracts are currently limited to 520 bytes because BIP16 was introduced as a covert upgrade where the contract is technically pushed to the stack (and stack items are limited to 520 bytes). There’s actually no reason for implementations to stepwise-evaluate the “P2SH wrapper” – the VM is already pattern matching to process P2SH outputs differently, it can just as easily skip pretending the P2SH contract is pushed the stack. (Note, such an upgrade is only possible on Bitcoin Cash because Bitcoin Cash has been using opt-in upgrades since 2017; our upgrades aren’t designed to fool outdated full nodes into believing no upgrade occurred.)
Cleaning this up would allow P2SH contracts to use the same limit as the rest of the
scriptSig (unlocking bytecode),
MAX_TX_IN_SCRIPT_SIG_SIZE (1650 bytes). And with only a reasonable hashing limit, we can both eliminate the
OP_CODESEPARATOR quadratic sighash issue and stop naively counting opcodes. That would allow developers to write much more interesting/advanced contracts without impacting node validation cost (and we don’t even need to increase maximum stack item length from 520 bytes).