Recently Artem Chystiakov ran the first Simplicity CTF challenge, with a real-money prize in Liquid Bitcoin (LBTC). This reminded me that I’ve wanted to run some prize contests to show off Simplicity and encourage people to learn more about it.
One simple pattern is to create a contract that arithmetically recognizes some kind of mathematical object (like a list of integers that are related to each other in some way) and approves payment requests whenever such an object is provided as a witness. It’s pretty easy to create contests from this without trivially giving away the answers, because there are many mathematical problems whose answers are easy to verify but apparently hard to find. We already have an example along these lines with a hash function in the SimplicityHL examples. It looks like this:
/*
* REVEAL COLLISION
*
* The coins move if someone is able to provide a SHA2 collision, e.g.,
* two distinct byte strings that hash to the same value.
*
* We cannot test this program because no SHA2 collision is known :)
*
* https://docs.ivylang.org/bitcoin/language/ExampleContracts.html#revealcollision
*/
fn not(bit: bool) -> bool {
<u1>::into(jet::complement_1(<bool>::into(bit)))
}
fn sha2(string: u256) -> u256 {
let hasher: Ctx8 = jet::sha_256_ctx_8_init();
let hasher: Ctx8 = jet::sha_256_ctx_8_add_32(hasher, string);
jet::sha_256_ctx_8_finalize(hasher)
}
fn main() {
let string1: u256 = witness::STRING1;
let string2: u256 = witness::STRING2;
assert!(not(jet::eq_256(string1, string2)));
let hash1: u256 = sha2(string1);
let hash2: u256 = sha2(string2);
assert!(jet::eq_256(hash1, hash2));
}
This is a good challenge problem because nobody has ever publicly revealed such a collision for SHA256, although it’s not a great challenge problem because it’s too hard (it might take decades, centuries, or longer before anyone will win the challenge).
Something of more customizable difficulty would be integer factorization challenges like the RSA numbers (or other challenge numbers). It’s extremely easy to generate these challenges at any desired level of difficulty, and we could write a contract that says “here is a specific challenge number n; to claim these assets, submit a transaction with two integers witness::p and witness::q such that p×q=n”.
However, the simple structure of “show us an example of numbers with these properties” has a security vulnerability because there’s no strong commitment connecting the winning information with a specific winner (or the winner’s on-chain address). If I reveal a winning answer, it is inherently valid for anyone to submit. During the time when a transaction has been submitted to the mempool, anybody (including a miner) who can view the mempool could see the answer, and could construct a totally new transaction with a higher fee that claims the same coins using the same solution!
(Sorry the AI hallucinated two different handsets on the attacker’s phone. Maybe it’s just a really fancy kind of phone?)
The key is just that the attacker has to submit a copy of the claim faster or merely with a somewhat higher fee to make it more appealing to a miner. Then the attacker’s version of the claim is likely to be accepted as authoritative and appear on the blockchain, in preference to the original claim.
Again, the SHA256 collision challenge above suffers from this problem. A bot could watch for claims in the mempool, check whether they’re valid, and quickly submit higher-fee copies of the claims sending the prize to the bot’s owner instead.
When I talked to Andrew Poelstra and Russell O’Connor about this issue a few months ago, they suggested a two-phase claim process with a deposit and timeout. The idea is that the prize money is held by a covenant that can go back and forth between two different states. (I believe the version I present here is my slight adaptation of Russell O’Connor’s solution.)
In the READY state, the covenant is not prepared to pay out the prize. However, it is prepared to accept a deposit from anyone in order to enter the LOCKED state. The deposit amount is verified as sufficient, and gets added to the covenant’s prize pool. The READY → LOCKED transition also lets the person making the deposit specify a withdrawal address, which the covenant will remember when in the LOCKED state.
In the LOCKED state, the covenant can do two different things:
- Process a claim. The user submits a claim; if it is correct (according to the solution-checking logic in the contract), the prize money can be paid out, but only to the remembered address.
- Return to
READYstate. If an observer notes that the contract has been inLOCKEDstate for too long (beyond a timeout duration), the observer can return the contract back toREADYstate, and be rewarded with a small fee (less than the amount of the deposit).
The advantage of this is that the contract is committed (in LOCKED state) to only paying the prize to the specific party that put the contract into LOCKED state, regardless of whether other transactions appear that claim the prize based on the same witness data. However, a user can’t tie up the contract in LOCKED state forever, and there is a financial cost to submitting a spurious claim or locking the contract without submitting a claim at all (the loss of the deposit). A user with a valid claim doesn’t need to worry too much about the deposit cost because the deposit will be refunded along with the successful prize claim.
Here’s a flowchart of that logic:
I’ve almost finished implementing this and hope it will be a nice example of practical uses of state commitments in SimplicityHL, as well as a practical demo of how to work around the witness swiping issue. We may even be able to run some more contests using this approach!
