We could leverage commitment squashing and private kernels to create efficient state channel scheme. Here is how it could work for turn-based games:
Users A and B initialize the game by depositing a stake in the game contract and passing in identity_hash.
User A calls turn(0) function where 0 is a turn_counter. Even number corresponds to user A, odd to user B.
turn(counter2) function then does the following:
3.1 Calls get_secret oracle and checks that hash(secret) is equal to identity_hash of user A if counter % 2 = 0 or user B if counter % 2 = 1,
3.2 calls get_turn oracle and progresses the game state,
3.3 calls turn(counter + 1) if the game has not reached final condition. If final condition was reached finalize() function gets called and the user submits the result for settlement.
If the game did not finish in point 3.3, user A submits the proof to user B and user B continues with the game (point 3.1)
Loop until finalize() function gets called.
Efficiency
Since the game state would be represented by a note (or a set of notes) and we would nullify and “re-create” this game state note in each turn the commitments would get squashed and only the final note would be posted on chain.
Issues
This scheme is elegant but what if
I start losing and I decide to not continue with the game?
I decide to revert the game a few turns?
Joe’s solution to problem 1
Context: “I am a user A and user B decides to grief the game and never send user A his turn.”
User A calls slash(userB) function on the game contract. Given that user B might be completely innocent and user A might actually be the malicious one and ignoring user B’s response, user B will have the power to revoke the slashing by calling revoke_slash(kernel_proof, new_turn_of_user_B, secret) function. This function will verify the proof, revokes the slashing and progresses the game state. If user B never calls revoke_slash the game can be finalized by user A, making him a winner.
If one of the players decides to be malicious again the game will progress on L2 via the slashrevoke_slash functions.
The worst outcome the attacker can achieve is forcing the game on L2 and making it more costly for both users. This issue can be mitigated by having a game reputation score which would stick with users between games and would be adjusted during a game finalization based on the amount of slashings that occurred in the game. Since we can’t prove who of the 2 users was the malicious one both users would get slashed. This would not be that big of a deal because villains would naturally get weeded out of the game since they would receive the most slashings (and then they would lose all the frens and end up being sad and alone like peepo bellow).
Context: “I am a user A and I realize that I did a bad turn n rounds ago so I revert the game and choose a different turn.”
Since user B would not accept the play at that point, the game would have to go on chain. Once malicious user A is forced on chain via the slash-revoke_slash scheme user B could call dispute(kernel_proof). The function would verify the kernel proof and check that the new state advanced further than the one submitted by user A.
Love the idea! And I think you can remove the need for an identity_hash by just leveraging authwits: you can just call each account contract playing and ask them if the move they’re trying to execute is authorized or not, which will trigger a request for an authwit.
A roadblock that was found while experimenting with this scheme is that on point 3.3, functions must call the next step of the state channel in order to process the next turn. However, in the private context calling a function implies that the hash of the callstackitem is added to the public inputs of the caller.
This means that you cannot finish executing a function until you’ve finished all the functions that it calls. This makes every call graph a hash tree, where all the functions point via hashes to their children, and the root of the tree is the entry point. However, this breaks the state channel scheme, since you need to be able to pass a valid kernel proof of executing one function without knowing the result of whole call graph.
Calling a function pushes the whole callstack item to the stack to be able to constrain the results of executing that function. This is not the case when calling a public function, since that execution happens out of band, you don’t receive the results so the callstackitem that is pushed only expresses intent, not the result.
A possible solution to this problem could be adding a variant of call_private_function that doesn’t return a full callstackitem, just a execution request. Users of this function won’t receive any result of execution such as return values. This allows to prove the execution of a function without executing all the nested calls first. We could reuse some of the logic that we have in place for this in public calls.
@leila proposed another solution to the issue of the nested calls. Instead of players exchanging kernel proofs, players could exchange function proofs instead.
// This function holds the application logic. Players would exchange proofs of calling this function with the correct context and parameters
fn turn(account, game_state) {
let is_owner = check_account(account, game_state);
if is_owner {
play(game_state)
} else if (timeout) {
game_state.winner = account;
game_state
}
assert("permission denied");
}
fn round(game_state) {
game_state = turn(A, game_state);
if game_state.winner {
finalize(game_state.winner)
}
game_state = turn(B, game_state);
if game_state.winner {
finalize(game_state.winner)
}
game_state
}
fn continue_game(game_state) {
let game_state = round(game_state);
if !game_state.winner {
continue_game(game_state)
}
}
// When a player wishes to submit a game they would call this function to assemble the turns into one tx
fn start_game() {
continue_game(initial_state)
}
fn continue_game(game_state) {
let game_state = round(game_state);
if !game_state.winner {
continue_game(game_state)
}
}
The above could be generalized to a scheme where turn() calls are steps in a state channel and start_game is just a recursive assembler of multiple steps to submit in just one tx.
While the current sandbox mocks proving, where functionally does proving of the app circuit occur? This is important to point 3
The core building block seems to be ExecutionResult. This includes PartialWitness which is compromising information that should not be shared with counter-parties. As far as we can tell, this should not be used during kernel proof generation. With our current understanding, it is logically grouped here because all recursive proofs are created by one client in a standard transaction, but we can construct the necessary PrivateCallData for turn N without supplying the partial witness for turns 1…N-1
Can we successfully break this apart/ not include partial witnesses in the ExecutionResult for kernel proving? If not, this could be a critical failure for the state channel architecture since it would reveal any private keys fetched by oracles for nullification/ secret hashes used in shielding tokens.
The actual thing we need to accumulate is PrivateCallData for each iteration. Since it happens in reverse, we can send currentExecution without including nested executions (they can manually be filled in from db). We can also omit private and public call requests since we know privateCallRequests will just be the previous iteration and public call requests will be empty (except at the last request, whether timeout or double spend or rational). Beyond execution result, we only need to provide read request membership witnesses (which shouldn’t expose private note data). Does this track?
Do read request membership witnesses leak compromising information (assuming a note that cannot be 1st preimage attacked)? According to the ReadRequestMembershipWitness class, it initially looks like there is no issue here. However, perhaps the PXE uses this information to look up the note? I think not if this is the (Note Hash Tree)[https://docs.aztec.network/concepts/advanced/data_structures/trees#note-hash-tree] but this needs to be confirmed. While it wouldn’t
How does nested execution get simulated? Specifically, simulator.run() only calls executePrivateFunction once. Additionally, how does nestedExecutions get filled? It appears that it comes from ClientExecutionContext which has callPrivateFunction itself to fill the nested execution array, but it is unclear where this function is called by executePrivateFunction
Bonus Question- Double Spends: We need to punish players who construct two proofs for the same turn/ state increment. Perhaps it would be possible to have a “slash_double_spend” function call that has to prove the entire chain of both turns (i.e. for turn 4A and turn 4B, you have slash_double_spend → 4A → 3 → 2 → 1 → 4B → 3 → 2 → 1 → publicly resolve game)
fn slash_double_spend(4A_args, 4B_args) {
// prove that both iterations are valid
context.call_private_function(4A_args);
context.call_private_function(4B_args);
// prove turn in 4A_args and 4B_args are the same
...
// prove args hash of 4A_args and 4B_args is different
...
// trigger force game exit
context.call_public_function...
}
The issue with this is that it could quickly violate the callstack limit when a single chain of steps would be compliant. Alternatively, we could simply rely on timeouts to force a party to use the most advantageous note for their counterparty. Thoughts?
edit: this would not work because the notes would be nullified…
Use executePrivateFunction. Using the ACVM will not use oracles. We can treat whatever function as the entrypoint in this way.
Proving will occur after ExecutionResult but before a kernel proof. There will be a new ProvenExecutionResult value. It will not contain the partial witness as obviously only the proof and VK are needed to check the correct execution of the private function
It should be possible to omit this information from the kernel prover. This could be problematic with the introduction of folding, however…
Generally correct, but also an incorrect understanding of how the state channel itself will operate. See “notes on the architecture” below for context on why “since it (state increments) happen in reverse” is an eroneous statement.
No private leafs were harmed in the making of this state channel
The entry point is simulated with simulator.executePrivateFunction. Inside the simulation of this circuit, there will be oracle calls via ClientExecutionContext.callPrivateFunction to execute additional functions (pushing them to the callstack and simulating them before completing the current simulation to provide the return values as needed by current witness).
Notes on the architecture: Leila’s prescribed solution actually has a bunch of app circuits that do not call any other functions during execution. Instead, there is an “orchestrator” app circuit which is responsible for calling all other functions. It will need to recurse over itself every 4 calls to avoid a call limit. So long as commitments are squashed as the state increments and remains below the maximum of 64, it is possible to recurse infinitely. The caveat here is that squashed commitments currently count towards this maximum, but will not in the future.
Given each app circuit exists with no child function calls, it is quite trivial to implement a mechanism for punishing the “double spend” case where two proofs for the same increment in a state channel are created by a single party.
