txOutputVector expected to have less than 252 elements but not enforced

[sr-gi]

validateAndParseFundingSPVProof expects to have a _txOutputVector with no more than 252 (0xFC) values, but this is not enforced by _txOutputVector.validateVout().

tbtc/solidity/contracts/deposit/DepositUtils.sol

Lines 190 to 216 in 100e5aa

	function validateAndParseFundingSPVProof(
	DepositUtils.Deposit storage _d,
	bytes4 _txVersion,
	bytes memory _txInputVector,
	bytes memory _txOutputVector,
	bytes4 _txLocktime,
	uint8 _fundingOutputIndex,
	bytes memory _merkleProof,
	uint256 _txIndexInBlock,
	bytes memory _bitcoinHeaders
	) public view returns (bytes8 _valueBytes, bytes memory _utxoOutpoint){
	require(_txInputVector.validateVin(), "invalid input vector provided");
	require(_txOutputVector.validateVout(), "invalid output vector provided");
	bytes32 txID = abi.encodePacked(_txVersion, _txInputVector, _txOutputVector, _txLocktime).hash256();
	_valueBytes = findAndParseFundingOutput(_d, _txOutputVector, _fundingOutputIndex);
	require(bytes8LEToUint(_valueBytes) >= _d.lotSizeSatoshis, "Deposit too small");
	checkProofFromTxId(_d, txID, _merkleProof, _txIndexInBlock, _bitcoinHeaders);
	// The utxoOutpoint is the LE txID plus the index of the output as a 4-byte LE int
	// _fundingOutputIndex is a uint8, so we know it is only 1 byte
	// Therefore, pad with 3 more bytes
	_utxoOutpoint = abi.encodePacked(txID, _fundingOutputIndex, hex"000000");
	}

BTCUtils defines _nOutputs as a uint256 (https://github.com/summa-tx/bitcoin-spv/blob/master/solidity/contracts/BTCUtils.sol#L487-L489).

Since _fundingOutputIndex is defined as a uint8, values over 255 will fail, however values 253-255 will be wrongly parsed, creating at least two issues with the current code.

findAndParseFundingOutput will fail

findAndParseFundingOutput extracts the output that needs to be checked (extractOutputAtIndex). This extraction implies a varint parsing, that for output indexes 0xFD, 0xFE and 0xFF will return a data length of 2, 4 and 8 respectively. Since the output passed is a single byte the function will return an error that will make this require to fail.

Given that findAndParseFundingOutput is called as part of provideBTCFundingProof, this will case funds to be potentially lost if the deposit is funded with an output in the 253th, 254th or 255th position (any other output further down will also fail, but this is expected given the uint8 restriction of _fundingOutputIndex).

_utxoOutpoint will be wrongly encoded

If we ignore the previous issue, the incorrect parsing of the _fundingOutputIndex would make the contract store an invalid _utxoOutpoint for the same value range:

value | expected | encoded 
0xFD  | 0xFDFD00 | 0xFD0000
0xFE  | 0xFDFE00 | 0xFE0000
0xFF  | 0xFDFF00 | 0xFF0000

This will cause the redemption of the funds to fail, since the output that will be extracted and compared on redemption will not match the one stored in the contract.

tbtc/solidity/contracts/deposit/DepositRedemption.sol

Lines 345 to 348 in 100e5aa

	require(
	keccak256(_input.extractOutpoint()) == keccak256(_d.utxoOutpoint),
	"Tx spends the wrong UTXO"
	);

[sr-gi]

PS2: I guess UX-wise it'll be good to document the 252 max output index limitation (if it is not lifted), since I didn't realise about it from reading https://docs.keep.network/tbtc/.

This may cause some issues if creating the funding from a wallet you have no complete control of, for instance an exchange that may batch redemptions into a transaction with many outputs.

[mhluongo]

I guess UX-wise it'll be good to document the 252 max output index limitation (if it is not lifted),

Exactly- in the mainnet dApp we made "not funding from a wallet I don't control" a click-through. Even without this issue there, exchange batching can grow the size of a tx beyond what we can verify in a block

We'll make sure it's properly documented in #646

[sr-gi]

After carefully checking Summa's BTCUtils I found this has actually two issues that come from the fact that the _txOutputVector max value is not being enforced.

I will update the issue to cover both.

[Shadowfiend]

To check my overall understanding here, the core issue is that currently it's impossible to provide funding proof for output indexes >252. 253-255 ultimately fail the extractOutputAtIndex require, so provideBTCFundingProof in that scenario will revert with Read overrun during VarInt parsing, while >255 will fail at encoding time.

Continuing down that, the bad UTXO endpoint encoding cannot happen in tBTC due to the above, though it would be nice if bitcoin-spv handled this for completeness.

Given that, is it fair to say that this is solely an issue for UX? Or is there a mitigation we need to implement in the contract that I missed?

[sr-gi]

Given that, is it fair to say that this is solely an issue for UX? Or is there a mitigation we need to implement in the contract that I missed?

Ideally, _fundingOutputIndex should be uint256 so funds could be deposit using any output. Practically, this seems to be an issue, since parsing hundreds of outputs may be non feasible. This may change with the new approach being currently implemented by @prestwich, but I guess he'll be best to asses that.

Until then, as long as you have a way to prevent the user from funding from a wallet he does not control (as @mhluongo was referring in an earlier message) or make sure the user is aware that funding from a high output index will involve lose of funds, it should be OK.

[Shadowfiend]

Yeah, the current implementation already maxes out the block gas limit before we hit 200 outputs, I believe (see this analysis of gas costs for on-chain SPV proofs that @NicholasDotSol did). Definitely hoping the memviews boost us past that for the next version, though I believe when we looked at Bitcoin transaction history that large-output-count transactions from exchanges could get very large indeed. Need to dig up some numbers from February.

[Shadowfiend]

Closing this in favor of #646, which is a placeholder for the UX warnings around this.