-
Notifications
You must be signed in to change notification settings - Fork 2
/
main.tex
715 lines (583 loc) · 64 KB
/
main.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
\PassOptionsToPackage{usenames}{xcolor}
\PassOptionsToPackage{dvipsnames}{xcolor}
\documentclass{llncs}
\usepackage[utf8]{inputenc}
\usepackage{booktabs} % For formal tables
\usepackage{multirow}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{url}
\usepackage{xspace}
\usepackage{pifont}% http://ctan.org/pkg/pifont
\usepackage{color}
\usepackage{boxedminipage}
\usepackage[ff,sets,keys,primitives,operators]{cryptocode}
\usepackage{framed}
\usepackage[group-separator={,}]{siunitx}
\newcommand\bmmax{2}
\usepackage{bm}
\usepackage{caption}
\usepackage{hyperref}
\usepackage{footnote}
\usepackage{units}
\usepackage{multicol,lipsum}
\colorlet{iomsg}{MidnightBlue}
\colorlet{party}{brown}
\colorlet{entry}{NavyBlue}
\colorlet{string}{BlueViolet}
\def\UrlBreaks{\do\/\do-}
\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\newcommand{\instantiated}{\mathsf{instantiated}}
\newcommand{\instantiatedno}{\mathsf{NO}}
\newcommand{\instantiatedyes}{\mathsf{YES}}
\newcommand{\gamestatus}{\mathsf{phase}}
\newcommand{\gameregister}{\mathsf{INIT}}
\newcommand{\gamesetup}{\mathsf{SETUP}}
\newcommand{\gameattack}{\mathsf{ATTACK}}
\newcommand{\gamereveal}{\mathsf{REVEAL}}
\newcommand{\gamewinner}{\mathsf{WIN}}
\newcommand{\gamefraud}{\mathsf{FRAUD}}
\newcommand{\gamefinished}{\mathsf{GAMEOVER}}
\newcommand{\chanstatus}{\mathsf{status}}
\newcommand{\chanon}{\mathsf{ON}}
\newcommand{\chandispute}{\mathsf{DISPUTE}}
\newcommand{\chanoff}{\mathsf{OFF}}
\newcommand{\hready}{\mathsf{hready}}
\newcommand{\hboard}{\mathsf{hboard}}
\newcommand{\hcell}{\mathsf{hcell}}
\newcommand{\hship}{\mathsf{hship}}
\newcommand{\hshiplocation}{\mathsf{hshiplocation}}
%\newcommand{\hash}{\textsf{H}}
\newcommand{\cmd}{\mathsf{cmd}}
\newcommand{\hstate}{\mathsf{hstate}}
\newcommand{\hstatei}{\mathsf{hstate}_{\monotoniccounter}}
\newcommand{\hstateplus}{\ensuremath{\mathsf{hstate}_{\monotoniccounter+1}}}
\newcommand{\hstateminus}{\ensuremath{\mathsf{hstate}_{\monotoniccounter-1}}}
\newcommand{\monotoniccounter}{\mathsf{i}}
\newcommand{\stateinfo}{\mathsf{state}}
\newcommand{\stateinfoi}{\mathsf{state}_{\mathsf{i}}}
\newcommand{\stateinfominus}{\mathsf{state}_{\mathsf{i-1}}}
\newcommand{\stateinfoplus}{\mathsf{state}_{\mathsf{i+1}}}
\newcommand{\participant}{\mathcal{P}}
\newcommand{\rani}{\mathsf{r}_{\mathsf{i}}}
\newcommand{\ran}{\mathsf{r}}
\newcommand{\ranminus}{\mathsf{r}_{\mathsf{i-1}}}
\newcommand{\ranplus}{\mathsf{r}_{\mathsf{i+1}}}
\newcommand{\statechannel}{\mathsf{SC}}
\newcommand{\statechanneldispute}{\mathsf{SC}.\mathsf{trigger}}
\newcommand{\statechannelsetstate}{\mathsf{SC}.\mathsf{setstatehash}}
\newcommand{\statechannelresolve}{\mathsf{SC}.\mathsf{resolve}}
\newcommand{\statechannelgetcommitment}{\mathsf{SC}.\mathsf{getstatehash}}
\newcommand{\statechannelgetdispute}{\mathsf{SC}.\mathsf{getdispute}}
\newcommand{\statechannelclose}{\mathsf{SC}.\mathsf{close}}
\newcommand{\sign}{\mathsf{Sign}}
\newcommand{\verifysig}{\mathsf{VerifySig}}
\newcommand{\battleship}{\mathsf{BS}}
\newcommand{\battleshipfraud}{\mathsf{BS.fraud}}
\newcommand{\battleshipattackcell}{\mathsf{BS.attackcell}}
\newcommand{\battleshipbegin}{\mathsf{BS.begingame}}
\newcommand{\battleshipquit}{\mathsf{BS.quitgame}}
\newcommand{\battleshipcommit}{\mathsf{BS.commit}}
\newcommand{\battleshipplacebet}{\mathsf{BS.placebet}}
\newcommand{\battleshipselectboard}{\mathsf{BS.select}}
\newcommand{\battleshiprevealcell}{\mathsf{BS.opencell}}
\newcommand{\battleshipsinking}{\mathsf{BS.sunk}}
\newcommand{\battleshiprevealships}{\mathsf{BS.openships}}
\newcommand{\battleshiprevealboard}{\mathsf{BS.openships}}
\newcommand{\battleshipgameover}{\mathsf{BS.gameover}}
\newcommand{\battleshipdeposit}{\mathsf{BS.deposit}}
\newcommand{\battleshipwithdraw}{\mathsf{BS.withdraw}}
\newcommand{\battleshipfinish}{\mathsf{BS.finish}}
%\newcommand{\battleshipshipnotplaced}{\mathsf{BS.fraudnothit}}
\newcommand{\battleshipdeclarednotsunk}{\mathsf{BS.declarednotsunk}}
\newcommand{\battleshipdeclarednothit}{\mathsf{BS.declarednothit}}
\newcommand{\battleshipdeclarednotwater}{\mathsf{BS.declarednotwater}}
\newcommand{\battleshipsamecell}{\mathsf{BS.attacksamecell}}
\newcommand{\battleshiptwoships}{\mathsf{BS.celltwoships}}
\newcommand{\battleshipchallengeexpired}{\mathsf{BS.expiredchallenge}}
\newcommand{\battleshiplock}{\mathsf{BS.lock}}
\newcommand{\battleshipunlock}{\mathsf{BS.unlock}}
\newcommand{\battleshipgetstate}{\mathsf{BS.getstate}}
\newcommand{\appcontract}{\mathsf{AC}}
\newcommand{\applock}{\mathsf{AC.lock}}
\newcommand{\appunlock}{\mathsf{AC.unlock}}
\newcommand{\timerchallenge}{\mathsf{\Delta}_{\mathsf{challenge}}}
\newcommand{\timechallenge}{\mathsf{t}_{\mathsf{challenge}}}
\newcommand{\timerextra}{\mathsf{\Delta}_{\mathsf{extra}}}
\newcommand{\timerdispute}{\mathsf{\Delta}_{\mathsf{dispute}}}
\newcommand{\timenow}{\mathsf{t}_{\mathsf{now}}}
\newcommand{\timestart}{\mathsf{t}_{\mathsf{start}}}
\newcommand{\timeend}{\mathsf{t}_{\mathsf{end}}}
\newcommand{\timedispute}{\timenow + \mathsf{\Delta}_{\mathsf{dispute}}}
% Colorful diagrams
\newcommand{\constructor}{\textcolor{entry}{\bf constructor }}
\newcommand{\oninput}{\textcolor{entry}{\bf function }}
\newcommand{\stringlitt}[1]{\texttt{\textcolor{string}{#1}}}
\begin{document}
\title{You sank my battleship! \\ A case study to evaluate state channels as a scaling solution for cryptocurrencies}
\author{Patrick McCorry\inst{1}, Chris Buckland\inst{1},
Surya Bakshi\inst{2}, Karl W\"ust\inst{3}, and Andrew Miller\inst{2} }
\institute{King's College London UK\\
\email{patrick.mccorry,chris.buckland@kcl.ac.uk}
\and
University of Illinois at Urbana Champaign\\
\email{sbakshi3,soc1024@illinois.edu}
\and
ETH Zurich\\
\email{karl.wuest@inf.ethz.ch}
}
\maketitle
\begin{abstract}
Off-chain protocols (or so-called Layer 2) are heralded as a scaling solution for cryptocurrencies.
One prominent approach is called a state channel which allows a group of parties to transact amongst themselves and the global blockchain is only used as a last resort to self-enforce any disputed transactions.
%In the optimistic case, the only transactions processed by the blockchain is to acquire a deposit from each party to set up the channel and to re-distribute the deposit based on the aggregation of all transactions authorised within the channel.
%As well, it promises instant finality for every authorised transaction and no transaction fees as there is no central operator to reward.
%In the worst case, the blockchain guarantees safety of all funds in the channel and liveness as the channel can be closed and its the application can be completed via the blockchain.
To evaluate state channels as a scaling solution, we provide a proof of concept implementation for a two-player battleship game.
Typically it is considered unreasonable to play via the blockchain which we confirm as a single game costs between \$16.27 and \$24.05, but it is perceived as an ideal application for a state channel.
We explore the minimal modifications required to deploy the battleship game as a state channel and propose a new state channel construction, \textsf{Kitsune}, which combines features from existing constructions.
While in the optimistic case we demonstrate the battleship game can be played efficiently in a state channel, the requirement for all parties to collectively authorise new transactions in the state channel introduces new economic and time-based attacks that if exploited renders the game as unreasonable to play.
\end{abstract}
\section{Introduction}
Since 2009, we have witnessed the rise of cryptocurrencies as the market capitalisation for all cryptocurrencies peaked to \$1 trillion US dollars in December 2017.
While Bitcoin \cite{nakamoto2008bitcoin} was the first cryptocurrency designed to support financial transactions, another promiment cryptocurrency called Ethereum \cite{wood2014ethereum} has emerged for executing programs called smart contracts.
The promise of smart contracts is to support the execution of applications without human oversight or a central operator.
Some applications proposed include decentralised (and non-custodial) token exchanges \cite{luukybernetwork}, publicly verifiable gambling games without dealers \cite{funfair}, auctions for digital goods without auctioneers \cite{auctions}, boardroom electronic voting wthout tallying authorities \cite{mccorry2017smart}, etc.
Cryptocurrencies do not yet scale.
Bitcoin can support approximately 7 transactions per second and Ethereum can support around 13 transactions per second.
The lack of scalability is one of the primary hurdles preventing global adoption of cryptocurrencies as the network's transaction fee typically become unaffordable for most users whenever the transaction throughput ceiling is reached (i.e. the average fee in Bitcoin reached \$20 in December 2017).
The community is pursuing three approaches to scale the network which include new blockchain protocols, sharding the blockchain and off-chain protocols.
New blockchain protocols can strictly increase the network's throughput \cite{sompolinsky2016spectre,eyal2016bitcoin,sompolinsky2015secure}, whereas sharding can be used to distribute transactions into processing areas such that peers only validate transactions that interest them \cite{kokoris2018omniledger,al2017chainspace,luu2016secure}.
However there is a tradeoff between increasing the network's transaction throughput to support a larger userbase in terms of affordable fees, and the number of validators with the necessary computational resources to validate every transaction \cite{mccorry2017atomically,gervais2016security,croman2016scaling}.
An alternative scaling approach consists of off-chain solutions to reduce the number of transactions processed by the blockchain.
It lets a group of parties deposit coins in the blockchain for use within an off-chain application.
Afterwards all parties can transact amongst themselves without interacting with the global network and the deposited coins are re-distributed depending on the application's outcome.
Two proposals include an alternative blockchain (i.e. a sidechain) or a channel.
A sidechain has block producers (i.e. miners or a single operator) for deciding the order of transactions and users who publish transactions for inclusion.
There are several sidechain protocols \cite{back2014enabling,dilley2016strong} which bootstrap from Bitcoin (including a live network by RSK \cite{sidechainrsk}), whereas Plasma\cite{poon2017plasma} and NOCUST\cite{khalilnocust} are non-custodial sidechains which bootstrap from Ethereum for financial transactions.
While sidechains are a promising off-chain solution, they still require a blockchain protocol which has a transaction throughput ceiling.
% and there is still no non-custodial sidechain protocol that can support executing smart contracts.
On the other hand, a channel can be considered an $n$ of $n$ consensus protocol as all parties collectively authorise the state of an application amongst themselves.
There is no blockchain protocol and all parties typically only store the most recently authorised state of the application.
Channels first emerged in Bitcoin to support one-way payments between two parties \cite{spilman2013,decker2015fast}, but has since evolved in Bitcoin towards the development of an off-chain payment network \cite{poon2016bitcoin} by several companies including Blockstream, LND and ACINQ.
% a sender can synchronise a single payment across a route of channels to the receiver.
%Several companies including Blockstream, LND and ACINQ are implementing this off-chain payment network.
At the same time, several proposals \cite{miller2017sprites,mccorry2018pisa,dziembowski2017perun,statechannelnetworks,coleman2018counterfactual,celernetwork,forcemove} collectively extend the capability of a channel to support a group of parties to execute a smart contract (i.e. a program) amongst themselves as opposed to simply payments.
A state channel promises instant finality for every transaction and no transaction fees as there is no operator to reward.
Channels are also self-enforcing as each party is protected against a full collusion of all other parties and in terms of scalability the throughput is only restricted by the network latency between the parties.
%when the group of parties have collectively authorised an application's new state, there are no transaction fees, the throughput is only restricted based on network latency between the users, and every user is protected against a full collusion of all other parties while they remain online.
%While payment channels in Bitcoin are only required to guarantee the safety of deposited funds, a state channel must also guarantee liveness of the application such that an application's progress can be continued via the blockchain if a single party does not co-operate in the channel.
The Ethereum Foundation has donated over \$2.7m \cite{efscaling1,efscaling2,efscaling3} and the Ethereum Community Fund has donated \$275k \cite{ecfscaling} to further explore state channels as a scaling solution.
As well, companies have raised substantial capital to deploy channels including Raiden at \$33m \cite{raidenICO} and FunFair at \$26m \cite{funfair}.
In this paper, we present an empirical evaluation in the form of a case study for a single-application state channel which must be a viable scaling option before a network of state channels is conceivable.
To aid this evaluation we have designed a two-player battleship game as a smart contract.
An application like battleship is not typically considered viable to execute via the blockchain due to the quantity of transactions required and in our experiment we confirm this perception as the financial cost is between \$16.27 and \$24.05.
However, state channels are perceived as a potential scaling solution to allow applications like battleship to be executed over the blockchain.
Our contributions are as follows:
\begin{itemize}
\item We explore the minimal modifications required to deploy a single-application smart contract as a state channel and propose a template of modifications that can be adopted by others deploying state channels.
\item We present a new state channel construction, \textsf{Kitsune}, which is application-agonostic, supports $n$ parties and allows the channel to be turned off such that the application's progress can continue via the blockchain. This combines the constructions from \cite{miller2017sprites}, \cite{mccorry2018pisa}, \cite{dziembowski2017perun}, \cite{croman2016scaling}.
\item We provide a proof of concept implementation to evaluate deploying applications within a state channel.
This experiment highlights the worst-case scenario of state channels and how it potentially renders applications like battleship as unreasonable to deploy within a state channel.
\end{itemize}
\section{Background}
In this section, we provide background information about Ethereum, smart contracts and how the concept of a channel has evolved.
\subsection{Ethereum and smart contracts}
All parties are responsible for generating their own pseudonymous account which is simply a public-private key pair.
If the account is associated with the network's native currency (i.e. ether), then the party can digitally sign transactions to send coins to other parties or they can interact with global programs called smart contracts.
All transactions are recorded and ordered in an append-only public ledger called the blockchain.
A group of financially invested users called miners are responsible for updating the blockchain with a new block of transactions via a proof of work competition.
If the block is accepted into the \textit{longest and heaviest blockchain}, then it is eventually considered the winner and in return the miner of this winning block is rewarded with newly minted coins.
% Ethereum's blockchain protocol implements a variation of the GHOST protocol to partially reward blocks that were mined, but are not part of the longest and heaviest blockchain.
Conceptually, a smart contract can be viewed as a trusted third party with public state.
It has a unique address on the network, it is instantiated based on the code supplied at the time of its creation, and all execution can be modelled as a state machine.
Every transaction executes a command in the smart contract and this transitions the state such that $\stateinfoplus = \mathsf{transition}(\stateinfoi, \mathsf{cmd})$.
It is considered a trusted third party as all parties must replicate the program's entire execution in order to verify the blockchain and join the network.
This mass-replication self-enforces a smart contract's correct execution and also implies that all data for the smart contract must be publicly accessible.
Finally all computation by a smart contract is measured using a metric called gas and the sender of a transaction sets a desired gas price.
The amount of gas used by a contract invocation multiplied by the gas price sets the transaction fee for incentivising a miner to include this transaction in their block.
\subsection{Evolution of channel constructions}
%A channel
%After every state transition, each party should have a signature from every other party for the new state.
We present a high-level overview of a channel before exploring the evolution of channel constructions from Bitcoin for financial transactions to Ethereum for executing arbitary smart contracts.
\paragraph{High level overview}
A channel lets $n$ parties agree, via unanimous consent, to new states that could be published to the blockchain.
As a result parties can transact amongst themselves instead of interacting via the global network.
%In this sense, a c non-fault tolerant consensus protocol (i.e. $n$ of $n$) which lets a group of parties to transact amongst themselves without interacting with the network.
To set up, each party in the group must lock coins in the underlying blockchain for the channel.
Afterwards all parties collectively execute state transitions and exchange signatures to authorise every new state (i.e. the balance of all parties, the state of a smart contract, etc).
If a single party does not co-operate to authorise a valid state transition, then the underlying blockchain is trusted to resolve disputed transactions and self-enforce the state transition.
In the case of Bitcoin, the blockchain gurantees \emph{the safety of coins for the online parties}, whereas in the case of a smart contract in Ethereum it also guarantees \emph{liveness such that an application will always progress and eventually terminate}.
\paragraph{Payment channels in Bitcoin}
Spilman proposed \textit{replace by incentive} which is the first state replacement technique for a channel.
It is designed for one-way payments from a sender to receiver \cite{spilman2013}.
The sender submits a deposit to open the channel and this deposit can be redeemed if one of the following two conditions are satisified.
Either the channel's expiry time is reached and the sender is refunded their coins, or both parties authorise the payment.
Every payment signed by the sender increments the coins owed to the receiver and decrements the coins owed to the sender.
The receiver must close the channel before its expiry time by signing and publishing the payment that pays them the most coins.
To support bi-directional payments, Decker proposed \textit{replace by time lock} which decrements the channel's expiry time whenever the payment direction changes \cite{decker2015fast}.
%This lets the receiver to publish the channel's new balance after receiving coins from the sender before any of their previous payments.
%Otherwise, the sender could publish a payment are eligible to be broadcast.
However both state replacement techniques require an expiry time which restricts the total number of transactions that can occur.
Poon and Dryja proposed a third state replacement technique called \textit{replace by revocation} for Lightning Channels \cite{poon2016bitcoin}.
It requires both parties to authorise each other's copy of the new state before sharing secrets to revoke the previously authorised state.
It also introduced the concept of a dispute process which lets one party publish a fully authorised state to close the channel and the blockchain provides fixed dispute period for the counterparty to prove the published state is invalid.
If fraud is proven, then the broadcaster is penalised and the counterparty is rewarded all coins in the channel.
After the dispute period has expired, both parties are sent their respective coins according to the final state accepted by the blockchain.
\paragraph{Payment channels in Ethereum}
Raiden proposed the first payment channel construction for Ethereum which is effectively a pair of replace by incentive channels \cite{raidenCode}.
Every payment increments the total coins owed to the counterparty and closing the channel requires each party to publish the final payment received.
Afterwards the smart contract computes each party's balance using the offset from the total coins owed to both parties.
Unlike in Bitcoin, this construction has no expiry time and does not restrict the total number of payments within the channel, but it is still restricted to two parties and the channel's state only considers the balance of both parties.
%If there is a dispute in the channel, then the blockchain accepts the state with the largest monotonic counter as the latest state.
%Both parties must increment a counter and sign every new state which is simply the balance of both parties.
\paragraph{State channels in Ethereum}
Both Sprites and Perun independently proposed a new state replacement technique called \textit{replace-by-version} \cite{miller2017sprites,dziembowski2017perun}.
While Sprites proposed a two-party payment channel, it also introduced a state channel construction to support $n$ parties and arbitrary applications.
Briefly, one party is responsible for proposing a command to transition the state.
All parties compute the state transition and increment a version number for the new state.
It is only considered authorised after each party has received a signature for the new state from every other party in the channel.
If one party does not co-operate, then any party can use the signed command (or issue their own command) to self-enforce the state transition via the blockchain using a dispute process.
%Briefly, one party is responsible for proposing a command to transition the state.
%All parties compute the state transition and increment a version number for the new state.
%Each party signs the new state and its version.
%It is only considered authorised after each party has received a signature from every other party in the channel.
%If one party does not co-operate, then any party can self-enforce the state transition via the blockchain using the dispute process.
To dispute, one party submits a state, its version and a list of signatures to prove this state was authorised by every party to a smart contract on the blockchain.
Next the party can trigger the dispute process and the blockchain provides a fixed time for all parties to submit signed commands.
After the dispute period the smart contract executes the submitted commands and transitions to the new state (and increments its version).
Any party can cancel the dispute during this fixed time period by submitting an authorised state with a a more recent version.
Pisa modified this state channel construction such that a commitment (i.e. hash) of the new state is signed instead of the plaintext state.
As a result, it proposed the first application-agnostic state channel smart contract.
\paragraph{Multiple-application state channels} \label{sec:multiapp}
Perun and Counterfactual channel constructions are designed for two parties and have extended the concept of a state channel in two ways \cite{dziembowski2017perun,coleman2018counterfactual}
First, they proposed the state within a channel can be organised in a hierarchy to support multiple-applications and the dispute process for one application does not impact other applications in the channel.
Second, they proposed virtual channels which allow two parties without a direct and established channel to connect with each other using a network of channels.
This requires all channels along the route to lock up collateral while the virtual channel is open.
Unlike Sprites, both constructions proposed the dispute process should be used to determine the final state and not to self-enforce a state transition directly.
This allows the channel to be turned off for a single application and for all future state transitions to be executed via the blockchain.
\section{State Channel Construction}
We propose a new state channel smart contract $\statechannel$ and an application template for a smart contract $\appcontract$ to support state channels.
The new state channel construction \textsf{Kitsune} relies on the dispute process model from Sprites/PISA to support $n$ parties and to allow the state channel contract to be application-agnostic.
However the dispute process is used to determine the final authorised state as proposed by Perun/Counterfactual.
This allows the state channel to be turned off and for the application's execution to continue via the blockchain.
%It is used to determine the final state to allow the channel to be turned off and for the smart contract's application to be progressed via the blockchain as proposed by Perun/Counterfactual.
Our template highlights the minimal modifications required for an application to support state channels and provides a mechanism to lock/unlock the application into a state channel upon approval of all parties.
\subsection{Overview of the State Channel}
An overview of the state channel contract is presented in Figure \ref{fig:statechannel} and the application template is presented in Figure \ref{fig:appmodify}.
Briefly, all parties must approve to lock the application using $\applock$.
This disables the application contract's functionality and instantiates the state channel contract.
The application's execution continues off-chain as all parties collectively sign the hash of every new state alongside an incremented version. %A state hash is only considered valid when each party has received a signature from every other party.
The channel can be co-operatively turned off using $\statechannelclose$, or any party can trigger the dispute process using $\statechanneldispute$.
This dispute process provides a fixed time period for all parties to publish the state hash with the largest version using $\statechannelsetstate$.
After the dispute process has expired, any party can resolve the dispute using $\statechannelresolve$ which turns off the channel and keeps a copy of the state hash with the largest version.
The application can be unlocked by submitting the entire state in plaintext using $\appunlock$.
This hashes the submitted state, fetches the final state hash from the state channel contract using $\statechannelgetcommitment$, and compares both hashes.
If satisified, the full state is stored and all functionality in the application contract is re-enabled to permit executing it via the blockchain.
\subsection{State channel contract}
We provide an overview of the state channel contract for \textsf{Kitsune} before discussing how to instantiate it, how parties collectively authorise new states off-chain and how the dispute process is used to confirm the final state hash.
\paragraph{Overview of the state channel contract}
Figure \ref{fig:statechannel} presents an overview of the state channel contract.
The state channel can be in one of three states which are $\chanstatus := \{\chanon, \chandispute, \chanoff\}$.
All parties can collectively authorise new states for the application when the state channel is set as $\chanstatus := \chanon$.
Any party can trigger a dispute which sets the state as $\chanstatus := \chandispute$ and this provides a fixed time period for all parties to submit an authorised state hash (and its corresponding version).
Once the dispute is resolved or if the channel is closed co-operatively, then the state is set to $\chanstatus := \chanoff$ and this determines the final state hash for the application.
If the channel is closed due to the dispute process, then a dispute record is stored which includes the starting time and finishing time for the dispute $\timestart, \timeend$ and the final version $\monotoniccounter$.
\paragraph{Creating the channel}
The application contract $\appcontract$ is responsible for instantiating the state channel contract with the list of participants $\participant_{1},...,\participant_{n}$ and the dispute timer $\timerdispute$.
The state channel is set as $\chanstatus := \chanon$ and the application contract's functionality is disabled.
%The state hash is $\hstatei = \hash(\stateinfoi, \rani, \statechannel)$, where $\stateinfoi$ is the full state and $\ran$ is a blinding nonce.
%Signing the new state hash is denoted as $\sigma_{\participant} := \sign_{\participant}(\hstatei, \monotoniccounter)$ where $\monotoniccounter$ is the incremented version for this state hash.
\paragraph{Authorising off-chain state hashes}
A command $\cmd$ is a function call within the application contract.
Any party $\participant$ can select a command $\cmd$ and propose a new state transition $\stateinfoplus := \mathsf{transition}(\stateinfoi, \cmd)$.
The new state is hashed with a blinding nonce\footnote{The blinding nonce is used for state privacy if resolving disputes is outsourced to an accountable third party as proposed by Pisa \cite{mccorry2018pisa}} $\hstateplus := \hash(\stateinfoplus, \ranplus)$ and signed $\sigma_{\participant} := \sign(\hstateplus,\monotoniccounter+1)$.
To complete the state transition, the party sends $\cmd,\hstateplus, \stateinfoplus, \ranplus$ and $\sigma_{\participant}$ to all other parties for their approval.
All other parties in the channel verify the state transition before authorising it.
To verify, each party re-computes the transition $\stateinfoplus' := \mathsf{transition}(\stateinfoi, \cmd)$ and state hash $\hstateplus' := \hash(\stateinfoplus', \ranplus)$.
Then each party verifies the signature $\verifysig(\participant, (\hstateplus', \monotoniccounter+1), \sigma_{\participant})$ and that the version is the largest received so far.
If satisfied, each party signs the state hash $\sigma_{k} := \sign(\hstateplus,\monotoniccounter+1, \statechannel, \appcontract)$ and sends this signature to all other parties.
A new state hash is only considered valid when each party has received a signature from every other party.
If one party does not receive all signatures by a local time-out, then this party can trigger the dispute process to turn off the channel, unlock the application and continue its execution via the blockchain.
\paragraph{Dispute process}
Any party can trigger the dispute process using $\statechanneldispute$.
This self-enforces the dispute time period $\timestart := \timenow$, $\timeend := \timedispute$ and sets $\chanstatus := \chandispute$.
All parties can submit the latest state hash, its version and the list of signatures to prove it was authorised using $\statechannelsetstate$.
The state channel contract $\statechannel$ only stores $\hstatei$ if it is signed by all parties and it has the largest version $\monotoniccounter$ received so far.
After the dispute period has expired, any party can resolve it using $\statechannelresolve$.
This sets $\chanstatus := \chanoff$, stores a dispute record ($\timestart,\timeend, \monotoniccounter$) and allows the application contract $\appcontract$ to fetch the final state hash $\hstatei$.
\paragraph{Co-operative close}
All parties can sign
$\sigma_{\participant} := \sign_{\participant}(\mathsf{'close'},\hstatei, \monotoniccounter, \statechannel)$ and submit it to the state channel using $\statechannelclose$.
This stores the state hash $\hstatei$, its version $\monotoniccounter$ and sets $\chanstatus := \chanoff$.
No dispute is recorded in the contract.
\subsection{Application Contract Template}
We present an application template that can be applied to easily add state channel support to an existing smart contract.
It demonstrates how to lock all functionality in the application for use in the state channel and how to unlock all functionality to permit the application's execution to continue via the blockchain.
\paragraph{Overview of template. } \label{sec:template}
Figure \ref{fig:appmodify} presents an overview of the application contract template.
After modifications, the application contract must explicitly record a list of participants $\participant_{1},...,\participant_{n}$, a dispute timer $\timerdispute$, whether the state channel has been instantiated $\instantiated := \{\instantiatedyes, \instantiatedno\}$ and if so it also stores the state channel's address $\statechannel$.
All functions within the application require a new pre-condition to check whether the state channel is instantiated and should only permit execution if $\instantiated = \instantiatedno$.
Finally the application must include two new functions $\applock$ that instantiates the state channel upon approval of all parties and $\appunlock$ that verifies a copy of the full state before re-enabling the application.
%A dispute time period
%An explicit list of participants
%A new boolean (on/off) and a pre-condition for every function in the contract (i.e. only allow function to be used if state channel is off)
%Two new functions: create channel (requires a signature from all parties) and setstate (receive full state, fetch hash, compare, store on-chain and re-enable functionality).
\paragraph{Lock application contract} All parties must agree to create the state channel by signing $(\chanon, \appcontract, \timerdispute, \mathsf{lockno}$), where $\chanon$ signals turning on the channel, $\mathsf{lockno}$ is an incremented counter to ensure freshness of the signed message and $\timerdispute$ is the fixed time period for the dispute process.
Any party can call $\applock$ with the list of signatures $\Sigma_{\participant}$, $\timerdispute$ and $\mathsf{lockno}$ to turn on the state channel.
The application contract $\appcontract$ verifies all signatures and that $\mathsf{lockno}$ represents the largest counter received so far.
If satisfied, $\appcontract$ sets $\instantiated := \instantiatedyes$ and this disables all functionality within the application.
Next $\appcontract$ creates the state channel contract $\statechannel$ which sets the list of participants $\participant_{1},...,\participant_{n}$ and the dispute timer $\timerdispute$.
Finally $\appcontract$ stores the state channel address $\statechannel$.
\paragraph{Unlock application contract}
After the dispute process has concluded in $\statechannel$, one party must send $\stateinfoi',\rani'$ using $\appunlock$ before the functionality can be re-enabled.
The application contract verifies that $\stateinfoi'$ indeed represents the final state by computing $\hstatei' := \hash(\stateinfoi', \rani')$, fetching the final state hash $\hstatei$ from $\statechannel$ using $\statechannelgetcommitment$ and checking $\hstatei' = \hstatei$.
If satisfied, $\appcontract$ stores $\stateinfoi'$ and re-enables all functionality by setting $\instantiated := \instantiatedno$.
Of course, if there is no activity within the state channel, then the state channel contract's dispute process can expiry without a submitted $\hstatei$.
In this case, the application contract verifies the state channel returns $\emptyset$ and re-enables all functionality without modifying the existing state.
%Notes: While all functionality is disabled on-chain; we need to be careful with how parties execute it off-chain! Not all functionality can be supported off-chain (i.e. contract to contract interaction); so this needs to be considered.
\section{Applying the Application Template for Battleship}
The full battleship contract is presented in Appendix \ref{sec:battleshipcontract} and it is designed to be executed via the blockchain by two players.
We explore how to apply the application template from Section \ref{sec:template} to the existing battleship contract such that it can be deployed within a state channel.
Afterwards we highlight some workarounds and pitfalls we discovered while building the proof of concept.
\subsection{Minimal modifications for a State Channel}
We present how to modify the battleship contract before deployment in order to support state channels.
This tracks whether a state channel was instantiated, the lock/unlock functionality to instantiate the state channel, a new pre-condition for every function in the game and how to handle functionality with side-effects in the off-chain contract.
\paragraph{Applying the application template}
%The purpose of our application template outlined in Section \ref{sec:template} is to allocate information for the state channel.
The application contract stores the dispute timer and a counter $\mathsf{instance}$ to track the number of times the state channel is turned on.
It sets $\instantiated := \instantiatedno$ and both players $\participant_{1},\participant_{2}$ for use by the state channel.
The pre-condition $\textbf{discard if}$ $ \instantiated = \instantiatedyes$ is included in every function except $\battleshipunlock$.
If the pre-condition is satisfied, then all future transactions that interact with this function will fail.
This disables all functionality within the application contract if it is locked and the state channel is turned on.
\paragraph{Lock and unlock functions}
The lock function $\battleshiplock$ requires a signature from both parties $\participant_{1},\participant_{2}$ to authorise creating the state channel which is denoted as $\sigma^{lock}_{\participant} := \sign_{\participant}('\mathsf{lock}', \mathsf{chan}_{\mathsf{ctr}}, \mathsf{round}, \battleship)$.
Once the state channel is turned on, the battleship contract sets $\instantiated := \instantiatedyes$, it creates a new state channel contract $\statechannel$ with the list of participants $\participant_{1},\participant_{2}$ and the dispute timer $\timerdispute$.
The unlock function $\battleshipunlock$ allows any party to submit the final game $\stateinfoi$ alongside the nonce $r$ after the dispute proces is resolved in the state channel contract.
The battleship contract verifies if it corresponds to the final state hash accepted by the state channel contract using $H(\stateinfo,r)$ == $\statechannelgetcommitment$.
If successful, the full state is stored and the flag $\instantiated$ is set as $\instantiatedno$.
This re-enables all functionality in the battleship contract.
\subsection{Workarounds for State Channel}
\paragraph{Off-chain contract}
Our proof of concept requires each player to deploy an off-chain version of the battleship contract to a local blockchain to replicate (and verify) the execution of all state transitions.
Without modifying the local blockchain instance, both the off-chain and on-chain battleship contracts have different addresses.
This poses problems for our fraud proofs if a message is signed for the off-chain contract address as it will not be valid when the on-chain contract is re-activated.
To alleviate this issue, we sign two messages for the on-chain and off-chain contract.
However there is an upcoming new consensus rule \cite{eip1014} to deterministically derive the contract's address which simplifies deploying an off-chain contract with the same address.
\paragraph{Loss of a global clock} Both parties no longer share a global clock within the channel to self-enforce time-based events.
We propose two approaches to handle time-dependent events.
First, the time $\timechallenge$ can be set by the player proposing a new state and the counterparty must verify the proposed time is within a range (i.e. a few minutes, or $n$ blocks) before mutually authorising it.
It must take into account the time required to turn off the channel via the dispute process and the time to initiate/settle the dispute such that $\timechallenge := \timenow + \timerchallenge + \timerdispute + \timerextra$.
An alternative approach is to set $\timechallenge$ as $\bot$ for all updates within the state channel.
Instead the time $\timechallenge$ is set by battleship contract when it is re-activated in the blockchain using $\battleshipunlock$ and if the game is in a relevant phase.
\paragraph{No external interaction or side-effects} \label{sec:sideffectshandle}
We define a side-effect as a state update that relies on an environmental variable or external interaction with another contract.
This is because the side-effects will not persist when the application is re-activated on the blockchain.
Some examples in Ethereum include the environment variables $\mathsf{msg}, \mathsf{block}, \mathsf{tx}$, and transfering coins to another contract.
%We discuss further in Section \ref{sec:sideffectshandle} how our experiment handles computing the contract's address $\mathsf{address(this)}$, the global clock $\mathsf{block.timestamp}$ or $\mathsf{block.blockhash}$ and the transaction sender $\mathsf{msg.sender}$.
All functions with side-effects should be deleted or disabled in the off-chain contract which for battleship includes the auxillery functions $\battleshipdeposit$ and $\battleshipwithdraw$.
% \paragraph{Authenticating the transaction signer}
\paragraph{Authenticating transaction signer and replay protection}
The battleship contract relies on $\mathsf{msg.sender}$ to authenticate the immediate caller as the transaction signer.
This requires the party to sign a transaction for execution in the counterparty's local blockchain.
Ethereum transactions have a $\mathsf{chain\_id}$ to prevent transactions signed for one blockchain being replayed to another blockchain.
The counterparty can verify the transaction has set $\mathsf{chain\_id}$ and it is destined for the off-chain contract address before executing it in their local blockchain.
Finally the off-chain contract can also include a new $\battleshipgetstate$ to return the full state and the corresponding $\hstate,\monotoniccounter$.
\paragraph{Persistent race conditions}
The gameplay for battleship is turn-based and it is clear which player is responsible for proposing every new state.
Setting up the game using $\battleshipselectboard$ or $\battleshipbegin$ has no order and both players may concurrently propose a state transition for the same version.
In our case, both players can use a deterministic rule to resolve the race condition (i.e. $\participant_{1}$ proposed state has priority) as the order of execution has no impact on the game's outcome.
This highlights that race conditions in the underlying application are reflected in the state channel and can result in the state channel being turned off if the order of execution has an impact on the application's outcome.
%
\paragraph{Limitations due to the EVM}
The mapping data structure in Solidity for the Ethereum contract environment poses problems for the state channel as it cannot simply delete all key-value pairs.
If a key-value pair is set to $\bot$ within the state channel, then this over-write must also occur when the full state is sent to the contract.
Otherwise, the key-value pair will persist in the application contract after the state channel is turned off.
For example, if a party's balance is set to $\bot$ off-chain, but this isn't reflected in the on-chain contract, then this party can withdraw more coins than they deserve.
\section{Proof of Concept Implementation}
\begin{table}
\centering
\begin{tabular}[]{l l c c}
\textbf{Step} & \textbf{Purpose} & \textbf{Gas Cost} & \textbf{\$\$} \\
\hline
\multicolumn{4}{c}{Battleship Game} \\
\hline
1 & Create BattleshipCon without State Channel & 10,020,170 & 7.97 \\
2 & Deposit ($\battleshipdeposit$) & 44,247 & 0.04 \\
3 & Place bet ($\battleshipplacebet$)& 34,687 & 0.03 \\
4 & Select counterparty's ships ($\battleshipselectboard$) & 422,894 & 0.34 \\
5a & Ready to play ($\battleshipbegin$) & 47,651 & 0.04 \\
5b & Do not play ($\battleshipquit$) & 388,805 & 0.31 \\
6 & Attack ($\battleshipattackcell$) & 69,260 & 0.06 \\
7a & Reveal cell ($\battleshiprevealcell$) & 73,252 & 0.06 \\
7b & Reveal ship ($\battleshipsinking$)& 111,372 & 0.09 \\
8 & Open ships ($\battleshiprevealboard$) & 159,748 & 0.13 \\
9 & Finish game ($\battleshipfinish$) & 275,521 & 0.22 \\
10 & Withdraw ($\battleshipwithdraw$) & 36,674 & 0.03 \\
11 & Fraud: Ships at same cell ($\battleshiptwoships$) & 280,766 & 0.22\\
12 & Fraud: Declared not hit ($\battleshipdeclarednothit$) & 284,261 & 0.23 \\
13 & Fraud: Declared not miss ($\battleshipdeclarednothit$) & 284,654 & 0.23 \\
14 & Fraud: Declared not sunk ($\battleshipdeclarednotsunk$) & 312,481 & 0.25 \\
15 & Fraud: Attack same cell ($\battleshipsamecell$) & 100,861 & 0.08 \\
16 & Challenge period expired ($\battleshipchallengeexpired$) &75,349 & 0.06 \\
\hline
\multicolumn{4}{c}{State Channel} \\
\hline
17 & Create BattleshipCon with State Channel & 13,607,0695 & 10.83 \\
18 & Lock ($\battleshiplock$) & 991,617 & 0.79 \\
19 & Trigger dispute ($\statechanneldispute$) & 84,106 & 0.07\\
20 & Set state hash ($\statechannelsetstate$) & 70,035 & 0.06 \\
21 & Resolve ($\statechannelresolve$) &89,745 & 0.07 \\
21 & Co-operative turnoff ($\statechannelclose$) & 90,354 & 0.07 \\
22a & Unlock ($\battleshipunlock$) & 725,508 & 0.6 \\
22b & Unlock (No Activity) ($\battleshipunlock$) & 51,454 & 0.04 \\
\hline
\multicolumn{4}{c}{Aggregated Statistics} \\
\hline
\multicolumn{2}{l}{Turn state channel on and off} & 1,961,011 & 1.56 \\
\multicolumn{2}{l}{Average case for game} & 20,451,633 & 16.27 \\
\multicolumn{2}{l}{Worst case for game} & 30,237,372 & 24.05 \\
\hline
\end{tabular}
\caption{Costs of running the battleship game within the state channel. We have approximated the cost in USD (\$) using the conversion rate of 1 ether = \$306 and the gas price of 2.6 Gwei which are the real world costs in September 2018. }\label{tab:costs}
\end{table}
\begin{table}
\centering
\begin{tabular}[]{l c c c}
\textbf{Purpose} & \textbf{Propose} & \textbf{Verify} & \textbf{Acknowledge}\\
\hline
% \multicolumn{5}{c}{Battleship in the State Channel} \\
% \hline
Place bet ($\battleshipplacebet$)& 232.18 & 212.23 & 0.44 \\
Select counterparty's ships ($\battleshipselectboard$) & 330.59 & 304.70 & 0.44 \\
Ready to play ($\battleshipbegin$) & 243.70 & 224.51 & 0.44 \\
Attack ($\battleshipattackcell$) & 267.09 & 243.69 & 0.35 \\
Reveal cell ($\battleshiprevealcell$) & 268.93 & 248.51 & 0.40 \\
Reveal ship ($\battleshipsinking$) & 291.25 & 276.97 & 0.38 \\
Open ships ($\battleshiprevealboard$) & 288.75 & 258.70 & 0.35 \\
Finish game ($\battleshipfinish$) & 376.05 & 349.20 & 0.30 \\
\hline
\end{tabular}
\caption{Time taken to propose, verify and acknowledge new state transitions, measured in milliseconds (ms) and calculated as an average over 100 runs.}\label{tab:timings}
\end{table}
We present a proof of concept implementation for our battleship game within a state channel\footnote{Anonymous code: https://www.dropbox.com/s/o5s5k662h9lqlk4/Battleship.zip?dl=0}. The experiment was performed using a Dell XPS 13 with Intel Core i5-7200U CPU @ 2.50GHz processor and 8GB LPDDR3 on a private Ethereum node using Ganache\cite{ganache}.
In the following we discuss Table \ref{tab:costs} which outlines the gas costs for our proposed modifications and Table \ref{tab:timings} which presents a timing analysis to propose, verify and acknowledge a state transition within the channel.
Our experiment involves three contracts which includes the unmodified battleship contract (Step 1), the battleship contract after applying the application template (Step 15) and the state channel contract (Step 16).
Deploying both the modified and unmodified battleship contract highlights the cost for modifying an application contract to support a state channel is approximately 1 million gas.
A single game of battleship (Steps 4-9) via the blockchain costs \$16.27 (approx 20 million gas) where each player takes 65 shots\footnote{This number of shots is based on the better than random algorithm in. \cite{battleshipdata}}.
In the worst case, the game requires one player to take 99 shots, and the counterparty to take 100 shots.
This worst-case costs \$24.05 (approx 30 million gas) to finish the game.
Locking the battleship game, creating the state channel, performing the dispute process costs and unlocking the battleship game costs \$1.56 (approx 1 million gas).
The cost for each fraud proof is presented in Steps 11-14 and only one fraud proof is required per game to prove the counterparty has cheated.
All timings in Table \ref{tab:timings} are approximations. We focus on the time taken to propose a new state transition, the time required for the counterparty to verify a state transition and for the initial proposer to verify the signed new state which is an acknowledgement from the counterparty that the state transition is complete.
Proposing a new state takes between 232-376ms.
This includes creating and signing a transaction at 12ms, executing the transaction within a local blockchain which is between 35-179ms (i.e. it depends on the function executed), retrieving the full new state from the local blockchain at 172ms, preparing a transaction for the counterparty and signing the full state’s hash at 15ms.
The state hash and signature is sent to the counterparty which incurs typical network latency.
The counterparty takes between 212-349ms to verify a state transition which includes verifying the received transaction’s signature (and checking it is destined for the off-chain contract) at 8 ms, executing the received transaction within the local blockchain which is between 34-163ms, retrieving the full new state from the local blockchain at 171ms, verifying the signature for the received state hash and verifying it matches the newly computed state hash at 0.4ms, and finally signing the new state hash at 4ms.
The counterparty sends the corresponding signature for the new state hash back to the proposer which incurs typical network latency.
Finally the proposer must verify the signature from the counterparty which takes 0.4ms.
Overall, while the timings are reasonable for real-world use, the most expensive operations involve interacting with the Ganache client.
\section{Discussion and Future Work}
%\paragraph{Worst-case scenario for state channels}
%
%One party can turn off the channel using the dispute process after all parties agree to execute the application off-chain.
%This is problematic as all parties are now committed to executing the entire application via the blockchain.
%In the case of battleship, both parties commit to the battleship game using $\battleshipbegin$ and afterwards must play the entire turn-based game via the blockchain which costs between \$16.27 and \$24.05.
%
%\paragraph{Incorporating command issuance}
%The state channel construction in Sprites allows parties to update the application contract's state without closing the channel.
%Any party can update the state channel contract with the latest state and the dispute process is used to receive a command from each party.
%After the dispute process has expired, the state transition is performed on-chain as each command is executed in the application contract and this results in a new state for use in the channel.
%This approach allows the state channel to support functionality with side-effects such as depositing/withdrawing coins or interacting with other contracts.
%However it also requires the application contract to include a new $\mathsf{AC.transition}$ function that can evaluate the submitted commands.
%While it appears compatible with our state channel construction, we have left it as future work to incorporate.
\paragraph{Funfair dilemma}
There is a chicken-and-egg problem on whether state channels should create and destroy applications off-chain, or if the state channel should first require an application to already exist on the blockchain.
Perun and Counterfactual advocate for the former to minimise the up front cost of creating the channel, whereas Funfair are pursing the latter to minimise cost of resolving a dispute as only the application's state is kept off-chain.
%Perun and Counterfactual propose minimising what is stored on the blockchain by deploying the state channel in advance and permitting multiple applications to be created/destroyed within the state channel.
%On the other hand, Funfair propose maximimising what is stored on the blockchain state by deploying the entire application to the blockchain in advance and only keeping the state off-chain.
% only store the state in the channel which is similar to our experiment.
Fundamentally both approaches have a different trust assumption on the likelihood one party will trigger a dispute and whether the financial cost to resolve a dispute can interfere with the application.
This dilemma can be summed up in a single question:
\begin{center}
\textit{If the player is about to win a \$10 bet, but the counterparty has stopped responding in the channel, then is it worthwhile for the player to turn off the channel, complete the dispute process, re-activate the application and win the bet via the blockchain if this process costs \$100?}
\end{center}
To evaluate this dilemma, our case study highlights that it costs \$1.56 to resolve the dispute and submit the full game state to the contract which is an affordable (and reasonable) cost.
However it does not consider the cost to deploy and instantiate the battleship game at \$7.97, the continued cost for both players to play battleship or the remaining time required to finish playing it.
%\$1.56 is an affordable and reasonable cost for sending the full game-state to the blockchain.
%However
%We conclude that \$1.56 is generally an affordable and reasonable cost for battleship.
%If we do not consider network congestion and whether tranasactionwhich can be considered affordable (and reasonable).
\paragraph{Dominant strategy to force-close}
Let's consider the worst-case for battleship.
Both players set up the game with an expectation to play it within the state channel, but afterwards one player triggers a dispute to turn off the channel and the game must be finished via the blockchain.
To play the entire game costs between \$16.27 to \$24.05 and every move requires a reasonable time period for moves to be accepted into the blockchain.
If it is set to 5 minutes per move and the game requires 200 transactions, then the game may take several hours (i.e. 16 hours) to complete.
This can be considered a dominant strategy by an adversarial player as it is likely rational players will simply forfeit their deposit (and bet) to quit the game early.
\paragraph{Inducing cooperative behaviour}
It is not straight-forward to distinguish why a channel broke down\footnote{A blockchain cannot distinguish if Alice refused to sign and send Bob the latest state, or if Bob claims he did not receive it. } or if any action can be taken to penalise the party at fault.
%The worst-case scenario exists due to the speaker-listener problem as state channels cannot yet distinguish the party responsible for the channel breaking down.
%
To workaround the inability to identify the misbehaving party, future work must focus on how to induce cooperative behaviour amongst all parties in the channel.
Any mechanism should not let an adversarial player to force-close a channel to their advantage (i.e. expecting rational players to simply give up).
On the other hand, it must be careful not to discoruage honest parties from closing the channel and continuing the application's execution via the blockchain.
%such that there is never a dominant strategy for adversial players to force-close the channel a the expectation the other players may simply give up (and thus terminate the application in the misbehaving player's favour).
%On the other hand, any mechanism to induce cooperative behaviour must also not discourage honest parties from closing the channel and continuing the application's execution via the blockchain.
\paragraph{Self-inspection of blockchain congestion}
On 6th January 2018, we witnessed the network's transaction fee spike to 95,788,574,583 wei \cite{etherscan}\footnote{The congestion was caused by a popular game called Cryptokitties.} as the network became congested due to a significant increase in transaction throughput.
Congestion impacts state channels as it increases the cost for resolving disputes (i.e. \$57.58 for battleship) and continuing the application's execution (between \$599 and \$886 for battleship).
If the increased transaction fees are not paid, then it is probable that a transaction will not be accepted into the blockchain within the dispute time period.
Future work should focus on a new operation code (i.e. CheckCongestion()) that can retrospectively self-inspect the previous $k$ of $n$ blocks to determine if it was affordable for an honest party's transaction to be accepted into the blockchain.
This could be used to extend the time period for resolving disputes and let players wait until the network is no longer congested before continuing the application's execution.
% extend the time each player has to challenge period each player to make their move. time period for dispute time period for r can be used to extend the dispute period
%If there is a dispute, then can the blockchain self-inspect itself? Otherwise dispute can be triggered during congestion and an honest party doesn't have an opportunity to respond.
%We suspect this will require a new consensus rule to collect transaction fee metrics from the blockchain.
%Finally if the network's transaction fee spikes due to blockchain congestion as it did on the 6th January 2018 to
\paragraph{What to consider before deploying a state channel}
%Our case study highlights several difficulties that must be considered.
State channels require unanimous consent which implies they are only useful for a small set of parties who can remain online throughout the entire application's execution.
The developer must take care to ensure the application can gracefully handle (or remove) all race conditions and they must be mindful to ensure the off-chain state size does not grow significantly which may prevent its publication to the blockchain.
The application should be self-contained, not rely on any side-effects, and explicitly consider how to handle time-based events.
Finally to guarantee liveness, it must always be reasonable to continue an application's execution via the blockchain.
%After all, state channels should be considered an optimistic scaling solution where an application can be executed off-chain if all parties can be trusted to co-operate.
%, and in the worst-case all parties will simply continue its execution via the blockchain.
% \paragraph{Supporting arbitration outsourcing of state channels}
%To alleviate the security assumption that all parties must remain online and synchronised with the blockchain to watch for disputes, PISA \cite{mccorry2018pisa} proposed that parties can hire an accountable third party to watch the channel on their behalf.
%The application-agnostic design of the new state channel construction \textsf{Kitsune} is beneficial to PISA as the accountable third party is only required to verify the state channel contract's bytecode (and not the application) before accepting a job from the customer.
%As well, the accountable third party only requires a signature from every party in the channel $\Sigma_{\participant}$, the state hash $\hstate$ and the version $\monotoniccounter$ to resolve disputes on the customer's behalf.
\paragraph{Applicable Applications}
We built battleship as it fits the category of applications (i.e. chess, tic tac toe, poker, etc) that are not reasonable to execute on the blockchain directly, but may be compatible to work within a state channel.
Our experiment practically demonstrates that a game like battleship is not yet compatible with state channels as it appears layer 2 is ultimately restricted by the underlying throughput of layer 1.
If we consider the overheads introduced by state channels and the above limitations, we must examine the type of applications that are applicable for state channels.
State channels appear useful for a small group of parties who can remain online throughout the application's life-time and each party only has to perform a limited number of movies.
It is also beneficial if all parties want to repeat the application's execution more than once such that the additional overhead to set up the channel costs less than simply executing it via the blockchain.
Some potential applications include payments, casino games, boardroom elections and auctions.
%\paragraph{Conclusion}
%State channels must strictly be viewed as an optimistic scaling solution where an application can be executed off-chain only if all parties are trusted to co-operate, and in the worst-case all parties will simply continue its execution via the blockchain.
% Future work should consider metrics to determine
%Thus state channels must strictly be viewed as an optimistic scaling solution as all parties are trusted to cooperate.
% Our case study highlights that layer 1 ultimately restricts layer 2 and that state channels must strictly be viewed as an optimistic scaling solution as all parties are trsuted to co-operate.
%\section{Conclusion}
%
%We proposed a new state channel construction that combines the work of \cite{miller2017sprites,mccorry2018pisa,dziembowski2017perun,statechannelnetworks,coleman2018counterfactual} and an application template which presents the minimal modifications required to deploy an application as a state chanel.
%%Battleship was chosen as it is considered unreasonable to play on the Ethereum blockchain (i.e. \$16.27-\$24.05 per game), but it is perceived as an ideal application for a state channel.
%%Our experiment highlights the worst-case where % that state channels may not be compatible for games l
%%each player may set up the game with an expectation to play it in the channel, but one party decides not to co-operate off-chain.
%%This requires both parties to play the entire game via the blockchain and incur the unreasonable financial cost.
%State channels must strictly be viewed as an optimistic scaling solution only if all parties are expected to co-operate.
%We demonstrate how this trust assumption introduces new attacks that exploit the victim financially (i.e. cost to resolve dispute) or in terms of labour (i.e. time to finish the application).
%To conclude, channels appear useful for applications that involve a small number of moves/rounds and all parties need to repeat the application's execution more than once.
%Some applications in this direction include payments, casino games, boardroom elections and auctions.
%%Finally we also proposed a new state channel construction that combines the work of \cite{miller2017sprites,mccorry2018pisa,dziembowski2017perun,statechannelnetworks,coleman2018counterfactual} which may be of independent interest.
%%Finally, we also proposed a new state channel construction which combines the work from Sprites, Pisa, Perun and Counterfactual that may be of independent interest.
\section{Acknowledgements}
Patrick McCorry and Chris Buckland are supported by an Ethereum Foundation scaling grant, Ethereum Community Fund grant and a Research Institute grant.
Andrew miller is supported by an NSF Grant 1801321.
We thank the IC3-ETH participants Frank Sauer, Matthew Salazar, Oded Naor, and Deepak Maram for their support at kick-starting this project (and winning third prize).
As well, we thank Tom Close for discussions around how to mitigate disputes in state channels. Finally we thank Master Workshop: Off the Chain for bringing together state channel researchers which helped bootstrap this paper.
\bibliographystyle{plain}
\bibliography{bib}
\appendix
\input{fullboard.tex}
\end{document}