Technically feasible to play chess using Bitcoin?

[go1111111]

Someone recently posted an article about playing chess on an altcoin blockchain. It was interesting and got me thinking whether there's some way to do this with Bitcoin, and if not, if there was some plausible addition to Bitcoin that would allow it.

The TL;DR of the article is that putting every move on-chain is super expensive and not advisable with any blockchain. So a "challenge/response" system is developed where game-related transactions only hit the blockchain if there is a dispute. This seems like the right architecture for Bitcoin too. Ideally the whole game could be played over Lightning channels so even the result of the game didn't have to hit the blockchain.

However with the setup in the linked article, the blockchain still needs to be able to evaluate the following question: "is move M a valid move from board state S?" In other words the blockchain needs some way to represent the rules of chess.

It seems hard to write a Bitcoin script that takes a board state and a move and verifies whether the move is legal. Seems like there are too many possibilities, even with MAST. I was thinking maybe after you move you could also create a MAST script which accepts any valid continuation from your opponent. However without some smart contract that knows the rules of chess, you could just claim the moves you don't want your opponent to make aren't available to him.  

Greg Maxwell has a post talking about how various problems like this could be solved in Bitcoin.

The most heavy duty solution is SNARKS. They'll let you use an arbitrary program to verify a computation. So you wouldn't have to be restricted to Bitcoin Script. However that seems pretty far away.

The other option seems to be zero knowledge contingent payments (which Greg talks about here). It is claimed that you can run arbitrary programs which never hit the blockchain. It seems from Greg's description like the only downside is that the contract won't be private. This is fine in the chess case though. If contract privacy is the only difference in power between ZKCPs and SNARKS, then ZKCPs are a lot more powerful than I realized.

So, my question: is it actually possible today to use ZKCPs to play chess for bitcoins, trustlessly, using the Bitcoin blockchain in such a way that only one transaction hits the chain when the game ends?

If this is not possible, what is keeping it from being feasible?

Are there other approaches that I missed?

[1714914304]

1714914304

[1714914304]

1714914304

[1714914304]

1714914304

[1714914304]

1714914304

[1714914304]

1714914304

[awesome31312]

Or you could go to lichess.org and host a game there, and do send me the link when you set it up, I kick ass at it

[2112]

If this is not possible, what is keeping it from being feasible?

Competitive chess playing is very resource intensive: fastest multicore processors, gigabytes of hash tables for middle game, hundreds of megabytes for opening books, tens or hundreds of gigabytes for endgame tablebases (6- or 7-piece respectively).

You would have to come up with a different chess game scoring system that doesn't take account of time.

Also, chess has no hidden state, so what would be benefit of using the zero-knowlegde system in the game?

[go1111111]

Or you could go to lichess.org and host a game there, and do send me the link when you set it up, I kick ass at it

The purpose of this question is not to play chess, it's to explore the power of smart contracts using Bitcoin. The idea is that if any technique that allows us to play chess using Bitcoin should be powerful enough to allow lots of other interesting uses.

Competitive chess playing is very resource intensive:

The smart contract would not be generating moves. Just officiating a human vs. human match. I have in mind something like in the article I linked to. Checking whether a move is valid is far easier than generating good moves.

You would have to come up with a different chess game scoring system that doesn't take account of time.

Timing moves is tricky, however it may be possible to play long games where the time per move is measured in blocks. If the time is long enough (for instance, 100 blocks per move), the variance of block creation may not be an issue. However since the goal is not to post every move on the chain (as mentioned in the original post, this is super inefficient), there may be some way to play with faster time controls with all verification done off-chain or over a Lightning channel.

Also, chess has no hidden state, so what would be benefit of using the zero-knowlegde system in the game?

I mention zero knowledge proofs because those are solutions that Greg mentioned already exist (ZKCP) or are eventually coming (SNARKS). You're right that it seems like zero knowledge shouldn't be needed for this. If anyone knows how to trustlessly verify an arbitrary computation without it, I'm interested to know how.

[2112]

The smart contract would not be generating moves. Just officiating a human vs. human match. I have in mind something like in the article I linked to. Checking whether a move is valid is far easier than generating good moves.

I'm sorry, I misunderstood your intentions.

Timing moves is tricky, however it may be possible to play long games where the time per move is measured in blocks. If the time is long enough (for instance, 100 blocks per move), the variance of block creation may not be an issue. However since the goal is not to post every move on the chain (as mentioned in the original post, this is super inefficient), there may be some way to play with faster time controls with all verification done off-chain or over a Lightning channel.

But judging the game isn't just verification of the moves. Most of the effort in judging actually goes to verifying the fairness, meaning that any of the sides isn't using any disallowed resources. So it would not be "human vs. human" but more like "correspondence game with unlimited computing resources and unlimited consultation".

I mention zero knowledge proofs because those are solutions that Greg mentioned already exist (ZKCP) or are eventually coming (SNARKS). You're right that it seems like zero knowledge shouldn't be needed for this. If anyone knows how to trustlessly verify an arbitrary computation without it, I'm interested to know how.

Is that a trick question? If you know the computation program and the input state then just rerun that computation as many times as you want until the you are convinced. Do you have some strange definition of "trustlessness" in your mind? Something like "left hand doesn't trust right hand?"

I think chess programming is just a nice way to really learn a new programming languages. It is non-trivial yet small enough that interesting and sensible programs can be written by a single programmer. Other than that what is the point? It really is "play to play" not "play to win".

[go1111111]

So it would not be "human vs. human" but more like "correspondence game with unlimited computing resources and unlimited consultation".

Yes, that's fine for my purposes. As I told the other person above, this is a learning exercise to explore what Bitcoin is capable of.

Is that a trick question? If you know the computation program and the input state then just rerun that computation as many times as you want until the you are convinced. Do you have some strange definition of "trustlessness" in your mind? Something like "left hand doesn't trust right hand?"

The point of using Bitcoin is that we want its blockchain to know the program and the inputs and verify the output, then release funds depending on the output. It isn't enough that both you and I can run the program off the blockchain, because one of us could lie and say "hey when I run this program it says I won, so give me the money." Trustless here means you don't have to trust your partner to be honest and pay you if he loses. The blockchain resolves any dispute about who the winner is, and causes funds to be paid to them.

[2112]

Yes, that's fine for my purposes. As I told the other person above, this is a learning exercise to explore what Bitcoin is capable of.

Understood.

The point of using Bitcoin is that we want its blockchain to know the program and the inputs and verify the output, then release funds depending on the output. It isn't enough that both you and I can run the program off the blockchain, because one of us could lie and say "hey when I run this program it says I won, so give me the money." Trustless here means you don't have to trust your partner to be honest and pay you if he loses. The blockchain resolves any dispute about who the winner is, and causes funds to be paid to them.

OK. So we have fairly unsophisticated but way too large (for current Bitcoin blocks) program to verify the result of the game. We could say it is doable with a future soft fork.

The only remaining problem is how to verifiably enter the moves of the players into that program. Do you want to do that (1) one by one (2) in pairs (3) entire game in one fell swoop? I guess we now have a "trustless move

After the soft-fork gets implemented the whole operation would be:

<white-pubkey> <black-pubkey> OP_OFFICIATE_CHESS_GAME

which pops two public keys of the stack and pushed one of three numbers {0,1/2,1} back onto the stack.

So you are back into square one of Bitcoin: at least 50%+ of miners have to have the correct implementation of OP_OFFICIATE_CHESS_GAME soft-forked operator. It isn't a technical problem but a political one.

More precisesly: it isn't 50% of all miners, but of those miners that implement and mine OP_OFFICIATE_CHESS_GAME a majority (>50%) have to use the correct implementation.

[go1111111]

To clarify, I am interested in techniques that are general enough to support many other use cases without having to do a fork to support each one.

[awesome31312]

You could play correspondence chess, the type that only gives the moves, then you have to project them on a board manually

And my point was, no, it's not feasible to play chess using Bitcoin, because Lichess is there.

[X7]

how about a chess site with micro amounts used to play per blitz game? so say... 100-1000 bits per blitz game etc

[go1111111]

It seems like people in this thread are still focusing too much on tangential chess use cases, and not on the problem I described.

The problem is: how do you use the Bitcoin blockchain to enforce the rules of chess, such that you could bet on a game with your opponent without having to trust them? And, if this is not possible, is there a general solution that will be available in the future?