P2SH assurance contract

[MathieuG]

Context

Flipstarter is a popular crowdfunding method on Bitcoin Cash. It uses the anyonecanpay flag so pledgers can sign an input to a partial transaction and only when all the inputs sum up to the campaign goal, the transaction becomes valid and can be broadcast on the network. Because of the limit on maximum transaction of 100kb each campaign can have maximum ~650 pledges (each input being ~148 bytes). This results in a minimum pledge amount for participating if all pledges have to go through. The current implementation calculates this minimum by dividing the outstanding sum to be raised with the number of pledges that can still fit in. Which results in a high(er) minimum at first which lowers over time. People have expressed their frustration with having to recheck for the minimum to drop to be able to contribute to a campaign.

P2SH approach

Instead of making one big transaction with a ton of inputs an alternative approach is to have a campaign fundraiser covenant contract which is restricted to accepting pledges, paying out the campaign address at completion or refunding the pledges at expiry. Then each pledge becomes a separate transaction that interacts with the campaign covenant. This approach does not run into the maximum transaction limit which means you can have arbitrarily many contributors and don’t need a relatively high minimum pledge.

Contract Demo

The approach above was known and discussed two years ago already and implemented by Tobias Ruck with spedn (but remained untested and would still run into tx limits for refund transactions). The 32bit integer restriction came up as a major reason not to go ahead with this. Now with the May 15th introspection & 64bit integers upgrade I revisited the idea again, prototyped it with cashscript and successfully demoed it on testnet. The contract makes use of the new native introspection capabilities to inspect inputs and only restrict certain outputs. (tweet on the succesful demo)

At contract expiry anyone can “roll back” the chain of contracts refunding pledgers one by one. As pointed out here by @im_uname this would improve the UX over the current approach as you would no longer have to “trigger a move away from the pledging, partially-signed output”. But also gets rid of the cancel-pledge-at-any-time concept.
The latest setup allows for campaign payouts to both P2PKH & P2SH locking scripts.
The contract currently requires the pledgers first input to have a P2PKH locking script which is reused in case of refunds. It will be future work to see if this constraint can be relaxed so as to also allow that to be a P2SH input & have P2SH refunds.
Finally, with minimal modification the smart contract approach also allows for stretch goals, meaning that a campaign payout can only happen after a certain time allowing for raising past the initial goal with extra deliverables at certain funding marks.

[ShadowOfHarbringer]

This could end up as an amazing achievement that lets Bitcoin Cash replace platforms like GoFundMe and Kickstarter overnight in case of some dark scenario (government intervention).

Importance of this cannot be underestimated.

[Jonathan_Silverblood]

I believe the chain of pledges is but one of many ways in which it should be possible to implement an assurance contract on-chain after the math and introspection upgrade. I don’t have time to work on it at this point, but I want to bring it up so that others who want to look at this don’t think “there’s only one way”.

The build-up and roll-back setup here has one set of advantages and disadvantages, and I’m concerned that in order to make it function you need to trust a coordinator with temporary custody, or build out a much better wallet ecosystem (and this is why I don’t have time to build flipstarter today, I need to build that wallet stack).

I might be wrong, as I haven’t spent much time thinking on this particular contract setup, and so far it does look like the best approach that’s on the table for upgrading flipstarter, but I think it would be good to think over more alternatives and to consider the implementation details of this approach in more detail before settling on it as the way forward.

[MathieuG]

@Jonathan_Silverblood

I’m concerned that in order to make it function you need to trust a coordinator with temporary custody, or build out a much better wallet ecosystem (and this is why I don’t have time to build flipstarter today, I need to build that wallet stack).

A much better wallet ecosystem would be awesome, great to hear you’re working on that!
The way I see it this is a general problem, this solution could also have a Electron Cash plugin or like recently proposed for Flipstarter, a webwallet widget that broadcasts the special transaction. So the tradeoffs apply generally, to all “special” transactions.

I think it would be good to think over more alternatives

I was first looking at a tree structure but without loops you need to have a fixed number of inputs which is a big drawback. Native introspection does not give acces to hash_outpoints so you need to provide the full locking bytecode and amount for each refund output in the unlockingscript which you have to parse and require one by one (as there is no loops this will probably make you run into opcodecount or bytecode size limits) and this is limited to 1,650 bytes.

to consider the implementation details of this approach in more detail before settling on it as the way forward.

Agreed! Especially to see if P2SH refunds can be enabled without adding too much complexity.

[bitcoincashautist]

@MathieuG

Native introspection does not give acces to hash_outpoints so you need to provide the full locking bytecode

What do you mean by this? There’s OP_OUTPOINTTXHASH and there’s OP_UTXOBYTECODE which returns the prevout’s fixed-size P2SH pattern.
On the other hand, OP_ACTIVEBYTECODE provides the “unpacked” redeem script being executed.

[MathieuG]

I meant that if you have a hash of refund outpoints you can’t simply require all outpoints of a tx to be equal to that hash. In cashscript terms with the op_checkdatasig preimage hack you could

require(tx.hashOutputs == hashRefundOutputs);

but with native introspection you’d do

require(hash160(refundOutputs)==hashRefundOutputs);

// need to parse refundOutputs

require(tx.outputs[0].value == valueOutput0);
require(tx.outputs[0].lockingBytecode == bytecodeOutput0);

require(tx.outputs[1].value == valueOutput1);
require(tx.outputs[1].lockingBytecode == bytecodeOutput1);

... //repeated for each outpoint

because the hash of all outpoints, which you can get from the preimage, did not get its own opcode. So you need to provide all the value & bytecode data in the unlocking script.

[bitcoincashautist]

ahh got it, you meant hash of all outputs, like an aggregate function

[MathieuG]

Improved the contract to allow for p2sh refunds.
Here’s the cashscript code, the repo contains a version with and without the stretch goals described at the very end. Both are commented as to hopefully make them understandable to anyone interested.
Any feedback or question are welcome

GitHub - mr-zwets/p2shAssuranceContract

[MathieuG]

I looked into adding the option to cancel at any time to the p2sh setup. Instead of pledging directly to the payout chain, a pledger would fund a contract which allows for 1) the pledger to withdraw from at any time 2) anybody to initialize a refund after campaign expiry or 3) the funds to be added to a payoutchain right before campaign expiry.

The reason this solution is not as good as I initially thought is because a campaign can start multiple payout chains and lock pledges in complex and hard to recover ways. It would also add the requirement to keep track of many p2sh pledge utxos compared to just one campaign utxo.

[bitjson]

This is really awesome, thanks for working on it!

@MathieuG

I looked into adding the option to cancel at any time to the p2sh setup.

Sorry if you’ve already discussed it, but if you’re still looking for options to allow pledges to be cancelled in any order: have you considered saving proof of each pledger’s contribution to a refund merkle tree in the covenant? E.g. a tree with a depth of 20 gives you >1 million available leaves. Each pledger can add to the pot and simultaneously prove that they have added the correct “refund leaf” (e.g. their refund P2PKH public key concatenated with the satoshi amount) in place of any empty leaf in the contract’s merkle tree (like this demo). If anyone wants to cancel their pledge, they can prove they own the refund address by signing a cancellation message, remove their leaf from the merkle tree, and withdraw their money.

(Note, if we eventually get CashTokens, this sort of merkle tree can be replaced by issuing NFTs that can be burned back to the covenant to get refunds. It’s the same user experience though, using NFTs just optimizes transaction sizes and allows for more complex refund addresses.)

[MathieuG]

@bitjson

if you’re still looking for options to allow pledges to be cancelled in any order: have you considered saving proof of each pledger’s contribution to a refund merkle tree in the covenant?

You’re right of course that this is the way to go for cancel-any-time, I’m a bit embarrassed to say I knew of your merkle tree example but did not consider to use it here .

When I was talking about a “tree structure” higher up, I was simply thinking about grouping inputs and refunds in groups of 10 or so but that was obviously not the way to go.

So the tradeoff of the refund merkle tree is that both pledge and refund transactions would become quite a bit bigger in size and computationally a lot more intensive with all the hashing. Also managing a large merkle tree is not trivial for me but a good excuse to learn how to work with more complex data structures I guess ! That Cashtoken NFTs would also be great in this context really demonstrates to me how versatile they are

edit: maybe large merkle trees aren’t even currently possible with the 520 bytecode limit and 201 opcode limit?

[bitjson]

@MathieuG

So the tradeoff of the refund merkle tree is that both pledge and refund transactions would become quite a bit bigger in size and computationally a lot more intensive with all the hashing. Also managing a large merkle tree is not trivial for me but a good excuse to learn how to work with more complex data structures I guess ! That Cashtoken NFTs would also be great in this context really demonstrates to me how versatile they are

edit: maybe large merkle trees aren’t even currently possible with the 520 bytecode limit and 201 opcode limit?

Yeah, we definitely need to improve our contract tooling to make merkle trees easier for developers to use. As of now, it can be worth it to drop features just to avoid needing merkle trees.

Some napkin math: the unlocking bytecode would require 21 bytes for each tree level (OP_PUSHBYTES_20 and the 20 byte hash), plus the actual value committed to the tree – a 20 byte public key hash, and an 8 byte satoshi amount. So for ~1.04 million leaves, that is 448 bytes in the unlocking bytecode (limited at 1650 bytes, A.K.A. MAX_TX_IN_SCRIPT_SIG_SIZE) for any spending paths which read or modify the merkle tree.

For the contract redeem bytecode itself (limited at 520 bytes and 201 opcodes), you need the hash (20 bytes), and each tier requires 8 bytes/7 opcodes, so 20 levels is only up to 180 bytes/140 opcodes. Adding the P2SH redeem bytecode to the 448 bytes above, we have ~630 bytes, well under that limit (of 1650 bytes) and still smaller than e.g. a large multisig transaction (>8 signatures).

So you’re well under all the limits for trees well into the millions. If you don’t need much other logic, with the current network limits you can actually support 2**27 (~134 million) leaves (with 11 opcodes and plenty of bytes remaining).

Relevant CHIPs: with CashTokens, you’d be able to fully offload state in this case (no merkle tree needed), so you’d save ~600 bytes on transaction size. With bounded loops the merkle tree verification compresses down to ~20 bytes, and with better targeted limits you’d easily have room for several such merkle tree validations (without increasing worst-case validation costs for full nodes).

[MathieuG]

@bitjson

Some napkin math:

Thanks!

@bitjson

For the contract redeem bytecode itself (limited at 520 bytes and 201 opcodes), you need the hash (20 bytes), and each tier requires 8 bytes/7 opcodes , so 20 levels is only up to 180 bytes/140 opcodes.

Is this not just half the picture, only the inclusion proof?
A new tree would also have to be constructed bringing the total to 18 bytes or 14 opcodes for each layer? I think this means that with 140 opcodes you could only have 10 layers or 1024 leaves.

@bitjson

with CashTokens, you’d be able to fully offload state in this case (no merkle tree needed)

Which sounds awesome!

[bitjson]

@MathieuG

Is this not just half the picture, only the inclusion proof?
A new tree would also have to be constructed bringing the total to 18 bytes or 14 opcodes for each layer?

Ah, you’re right! I also failed to count quite a bit of (unoptimized) stack item duplication and juggling. (Sorry to mislead you!)

That demo also didn’t prevent malleability around the merkle path (e.g. someone pushing 2s rather than 1s for the OP_IFs; back in scope if we don’t have PMv3’s detached signatures). It also needs to be updated to use OP_HASH256 rather than OP_HASH160 (anticipating some 32-byte P2SH solution – I’m working on another forum post for that).

As currently written, thats ~2 extra bytes per level in addition to requiring two separate merkle tree validations. So that puts us at ~18 opcodes per level, not counting a malleability solution. (A more secure merkle tree also costs us 12 more bytes in the unlocking bytecode per level, but that isn’t a limiter, it just increases transaction size.)

Ouch, hopefully we can get at least 10 levels (plus other logic) within the current limits. I bet we can avoid the alt stack and do both merkle tree verifications simultaneously to save some bytes/opcodes. And of course, clients can be written to handle malleability gracefully, so we could save bytes there if necessary. I’ll try to experiment with that later this week.

[bitjson]

Ok, I put together a more optimized demo: Experimenting with Contract State Merkle Trees | Bitauth IDE (Aside: I think merkle tree state-management schemes can be made reasonably easy to build/audit with a reusable/composable “standard library”. Components like build_tree_level here could be well standardized.)

Hopefully more correct napkin math:

The contract redeem bytecode requires the 32-byte hash, the unrolled, simultaneous merkle tree validation (per tier: 17 opcodes, 18 bytes), and any other logic (in this example, 25 opcodes). This construction manages to trim malleability prevention down to 3 opcodes for each level, so dropping that (at the cost of wallet clients having to be a bit more intelligent) gets it down to 14 opcodes/15 bytes per level. This demo includes some sample leaf validation logic, so its overhead of ~80 bytes is probably a reasonable estimate beyond tree validation, so for 12 levels (12*18 bytes) that brings us to less than 300 bytes. (Well below the 520 byte push limit; the 201 opcode limit is the issue.) So with malleability protection: 11 levels (2,048 leaves), without: 12 levels (4,096 leaves).

The unlocking bytecode requires 34 bytes for each level (push opcode, 32 byte hash, and OP_1/OP_0 to indicate proof path), plus the values changed in the tree (the “before” and “after” leaf) – in this P2SH assurance contract case, a 20 byte public key hash and an 8 byte satoshi amount. So for 12 levels, unlocking bytecode is somewhere around ~460 bytes + ~300 byte redeem bytecode, for a total of ~760 bytes.

So we have a more definitive answer to what is immediately possible after May 2022. Not nearly as exciting as I thought, but maybe still useful in some cases. Tweaking my overview from above:

• With better targeted limits we could easily do 4 of these 32-level merkle tree “leaf replacements” with room/hashes to spare (without increasing worst-case validation costs for full nodes).
• With bounded loops this merkle tree verification compresses down to ~22 bytes (for both merkle trees!).
• And with CashTokens, we could fully offload this state (no merkle tree needed), saving ~700 bytes on transaction size and allowing for an unlimited number of pledges (refunded in any order).

[emergent_reasons]

Some context on how that plays out regarding minimum pledge in a 1000 BCH Flipstarter assurance contract, where the app does its best to ensure the contract can complete without requiring unreasonably large pledges:

First image: Today with 600 input slots using either the average method (what is implemented now) or the power curve method (which I would like to implement).

Second image: Same but with 4096 input slots (much better in both cases!)

[bitjson]

Ok, as mentioned above:

P2SH32: a long-term solution for 80-bit P2SH collision attacks

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.) This means: Common single-signature addresses are not affected. (Pay to Public Key Hash, P2PKH) Practica…

I’m afraid just about any P2SH-based flipstarter construction is going to be vulnerable to this attack unless we developed some pre-commitment scheme for anyone who might possibly join the contract.

Alternatively, if we can get a solution locked in for 2023, any would-be attackers probably won’t bother investing in infrastructure. That would keep attack profitability low, but only if 20-byte P2SH-based campaigns stay below some limit. I’m not a good person to figure out what that limit is, hopefully other people can chime in and offer estimates.

Both of those options seem pretty rough though – it may be a better use of resources for people to focus on infrastructure that would be ready to deploy on upgrade day in 2023. (Would probably make for an exciting upgrade!)

[MathieuG]

@bitjson

And with CashTokens , we could fully offload this state (no merkle tree needed), saving ~700 bytes on transaction size and allowing for an unlimited number of pledges (refunded in any order)

Indeed! With the Cashtokens upgrade a fundraising campaign with any number of pledges that can each cancel at any time is possible! Keeping the same interactive design where users add pledges to a campaign covenant, the covenant would then keep a minting NFT to give each pledger a receipt. This receipt is an immutable NFT containing the pledge amount and refund address. At any time the pledger send this NFT to the campaign contract to undo his pledge.

Automatic refunds can be enabled by allowing anybody after the campaign expiration to send the NFTs back to the campaign contract and allow to withdraw the pledge amount to the refund address.

@bitjson

I’m afraid just about any P2SH-based flipstarter construction is going to be vulnerable to this attack

The new architecture would not need to add user input to the “simulated state” instead the state about refunds is kept in NFTs so the vulnerability of 20byte p2sh wouldn’t be present anymore!

A drawback of this interactive architecture is that there’s a need for a specialized wallet to interact with the campaign covenant. I am prototyping what the Cashtoken upgraded cashscript contract would look like assuming these new introspection commands.

[MathieuG]

@bitcoincashautist and I also did some brainstorming on non-interactive designs for a p2sh flipstarter that are made possible by the Cashtokens upgrade. Imagine an open source website used by all campaigns were you put in your campaignID and refund address and it generates a p2sh address where you can send your pledge to, this would work with any normal BCH wallet. The campaign would have to keep track of all the separate pledge utxos, tally them up with an NFT and once the campaign-goal has been reached those utxos could be used a inputs for a payout transaction.

However there’s tradeoffs: first, a user can’t cancel at any time without a smart contract wallet which knows the locking script and can provide a signature to spend the funds and undo the pledge. Second, because it is difficult to audit the total amount raised the campaign might hide some contributions and raise more than the campaign-goal. When stretch goals are explicitly disallowed the campaign still might pick and chose utxos to add to the campaign contributions. Third, tallying up all the pledges requires as many transactions as there are pledges.

My takeaway from the discussion was that the non-interactive design might work well if canceling at any time is not a requirement and if all all pledges can be linked somehow (such as dusting the same address) so each pledger can know the total amount raised and so the utxos can be found if the campaign database were to crash.

[MathieuG]

Completed the 2nd version of the p2sh assurance contracts and added it to the same repository under the folder v2! It utilizes the Cashtokens features to enable cancel-at-any-time!
The 2nd version consists of two separate contracts: one for the campaign and one for the cancel/refund NFT. I made a version with and without stretch goals like I did for v1.

Curious to hear any feedback! I think making this was a great way to learn the power of cashtokens!

GitHub - mr-zwets/p2shAssuranceContract