An Examination Protocol for Handling
Programmable Answers Using a Public Blockchain
Shu Takayama

Yuto Takei

Kazuyuki Shudo

Tokyo Institute of Technology
Tokyo, Japan
takayama.s.ae@m.titech.ac.jp

Tokyo Institute of Technology
Tokyo, Japantakei.y.aj@m.titech.ac.jp

Tokyo Institute of Technology
Tokyo, Japan
shudo@is.titech.ac.jp

Abstract—Examinations that involve programming, such as
programming contests and certiﬁcation exams, are common.
However, current examination protocols require full trust in theoperating organizations, which allows malicious organizations tocheat. As a countermeasure, efforts are being made to develop
examination protocols that do not need a trusted authority.
One way to build such a decentralized protocol is to apply
blockchain. Several blockchain-based examination protocols havebeen proposed, but they can only handle a ﬁnite set of correct
answers.
We propose an examination protocol that can handle a setof correct answers deﬁned by a program and mathematicallyguarantee the validity of the protocol. We also implement a
programming contest platform based on the proposed method on
Ethereum and show the feasibility of the method. Furthermore,
we measure the economic cost of the method using the implementation and conﬁrm that the method is feasible for approximately
30–40 USD.
Index Terms—blockchain, examination, Ethereum, competitive
programming

The pioneering work of Yoshimura [4], Sawada [5], andKaneko et al. [6] has convinced us of the possibility ofbuilding blockchain-based examination protocols. However,
the methods of these previous studies have the problem thatthey can handle only a ﬁnite set of correct answers and cannot
be used for exams that require complex correct and incorrect
judgments, such as programming contests.
Based on these previous studies, we propose a decentralized
examination protocol that can handle a correct answer set
deﬁned by a program. The proposed method is describedusing an original model of computation, and the validity ofthe method is mathematically guaranteed. We also implementa decentralized programming contest platform based on the
proposed method on Ethereum [7]. In addition, we propose
solutions to problems that emerged during the implementation
process and measure the economic cost of the method using
the implementation.
This paper is organized as follows: In Section 2, we clarify
the problems of previous studies and specify the properties thatthe proposed method should satisfy. In Section 3, we introduce
a computational model to describe the proposed method. In
Section 4, the basic proposed method α is discussed. In Section
5, we discuss the proposed method β, with reduced economic
cost. In Section 6, we propose solutions to problems thatemerged in the process of implementing the proposed method
and measure the economic cost of the method using theimplementation.

I. I NTRODUCTION
For the healthy operation of society, various types of examinations, such as proﬁciency tests and entrance exams, need
to be conducted without fraud. However, current examination
protocols are based on full trust in the operating organizations,which has led to incidents of malicious organizations falsifying
results [1].
The more fraud is uncovered, the more trust operatingorganizations need to gain. This trend will promote oligopolies
in the examination market and encourage individual exams tobecome larger. This makes auditing more difﬁcult and fraudeasier. One way to overcome this negative feedback loop is
to build examination protocols that do not need a trusted
authority.
Soon after Nakamoto [2] proposed Bitcoin, an electronic
currency without a trusted central authority, people realizedthat the core technology of Bitcoin, the blockchain, could be
used for applications other than currency. For example, Namecoin [3] provides a decentralized version of name registration
and resolution services traditionally provided by a DNS. Suchdecentralized applications have come to be known as dapps.
With this background, it was natural to propose an examination
protocol using blockchain.

Yoshimura [4] was the ﬁrst to propose an examination
protocol using dapp. Although Yoshimura’s method focuses
on a form of security contest called capture-the-ﬂag (CTF),
it can be extended to a general-purpose examination protocolthat handles a ﬁnite set of correct answers with some trivial
modiﬁcations. Some problems with Yoshimura’s method arethat it requires a ﬁxed set of answerers before an exam, andonly the fastest correct answerer in each exam is recorded.
The economic cost is O(|P ||A|) for a questioner and O(1)for an answerer, where P is a set of answerers and A is a setof correct answers1 .

This work was supported by JSPS KAKENHI Grant Number JP21H04872.
This work was supported by SECOM Science and Technology Foundation.

1 When implemented in a Bitcoin pay-to-script-hash (P2SH) transaction,O(1) is the cost for a questioner, and O(|P ||A|) is that for an answerer.

II. P REVIOUS S TUDIES

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

Sawada [5] combined Yoshimura’s method with a commitment scheme and improved it to handle an unlimited numberof answerers. The economic cost of Sawada’s method is
O(|A|) for both a questioner and an answerer, where A isa set of correct answers.
Kaneko et al. [6] proposed an examination protocol using dapp independently of Yoshimura and Sawada. Unlike
Yoshimura’s and Sawada’s methods, Kaneko et al.’s method
records all correct answerers. However, as in Yoshimura’s
method, it is necessary to ﬁx a set of answerers before an
exam. The economic cost is O(|P |) for a questioner andO(|A|) for an answerer, where P is a set of answerers and A
is a set of correct answers.
Some common problems for these existing methods are thatthey can handle only a ﬁnite set of correct answers and thatthey do not discuss how to distribute the content of a problem.
Based on the problems with these existing methods, we
propose a method that satisﬁes the following four points: First,
it can handle an unlimited number of answerers. Second, allcorrect answerers are recorded. Third, it can handle a set ofcorrect answers deﬁned by a program. Fourth, the integrity ofthe problem content can be guaranteed.
III. M ODEL OF C OMPUTATIONLet k ∈ N be a security parameter, and let N ∈ N be
sufﬁciently large. Let ∥ be the concatenation operator for two
sequences of bits, and let λ be the empty sequence.
A. Cryptographic Hash Function
We( deﬁne a cryptographic hashfunction as a 5)tuple {HK k }k∈N , Gen, l, Hash, CO satisfying the following
seven conditions:• (Hash key set) For each k ∈ N, HK k is a nonempty setof binary sequences.
• (Hash key generation function) Gen is a probabilistic
polynomial-time algorithm. For each k ∈ N, if 1k is
input, it outputs hk ∈ HK k .
• (Hash length) l : N → N• (Hash function) Hash is a polynomial-time algorithm. For∗
each k ∈ N, if hk ∈ HK k and x ∈ {0, 1} are input, itl(k)outputs y ∈ {0, 1} .
• (Compatible oracle set) CO is a nonempty set of oracles.
• (Collision resistance) Let A be any probabilistic
polynomial-time algorithm that is arbitrarily interrogatable to each oracle belonging to CO ′ , a ﬁnite subset of
CO. P(Collk,A = 1) is a negligible function for k, where
Collk,A is a probabilistic game deﬁned by the following:1) hk ← Gen(1k ).
2) (x, x′ ) ← A(hk ).
3) If x ̸= x′ ∧ Hash(hk , x) = Hash(hk , x′ ), return 1;
otherwise, return 0.
• (Preimage resistance) Let A be any probabilistic
polynomial-time algorithm that is arbitrarily interrogatable to each oracle belonging to CO ′ , a ﬁnite subset of
CO. P(Prek,A = 1) is a negligible function for k, where
Prek,A is a probabilistic game deﬁned by the following:1) hk ← Gen(1k ).
∪Nn2) Choose x uniformly from n=0 {0, 1} .
′3) x ← A(hk , Hash(hk , x)).
4) If Hash(hk , x) = Hash(hk , x′ ), return 1; otherwise,
return 0.
In what follows, we assume that there is one cryptographic
hash function.
B. Parties
We model a system as a sequence of probabilistic
polynomial-time algorithms. Each algorithm has a uniqueaddress of na bits. Algorithms send and receive messages
with each other. In other words, a party is a pair of an address
and a probabilistic polynomial-time algorithm. We denote theaddress of a party P as aP .
We consider two types of parties: external parties, which
represent system participants outside a blockchain, and contract parties, which represent programs on a blockchain.
External parties issue a send command to send a message.
Messages are expressed in a list format, where the ﬁrst termof each message is the destination address. Each sent message
is pushed to the message queue of the destination, with theﬁrst term replaced by the source address. To prevent contract
parties from sending messages to each other and creating aloop, contract parties do not send messages.
Parties issue a receive command to pop a message from theirmessage queue. If a message queue is empty, it returns a list
with all terms set to λ. In addition, as described below, there
are timing and frequency restrictions on receiving commands
for contract parties.
C. Execution Model
Execution of a system proceeds in phases.
In the ﬁrst phase of each execution, an initialization function
is ﬁrst executed to determine the initial arguments of eachparty. The arguments of an initialization function are given as
the arguments of an entire system.
At the beginning of each phase, external parties are in an
activated state, and contract parties are in a deactivated state.
Contract parties are activated when they receive a message
from another party and issue a receive instruction only once
immediately after activation. This restriction replicates the
behavior of dapps on Ethereum. On the other hand, external
parties are never activated by receiving a message. If an external party is deactivated during a phase, it remains deactivateduntil the start of the next phase.
Each party runs for a polynomial time with one activation.
This time restriction also applies to a party that deviates froma protocol due to a failure. When a party is deactivated andthen reactivated, the return value of the previous action is usedas the argument for the next action. When all the parties aredeactivated, the next phase is started.
D. Openness of Contract Parties
The initial arguments of contract parties, the return valuesof all actions of contract parties, and all messages addressed toProc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

content

correctness

O

C

hk

P1

P2

Pi

Figure 1. The parties in the proposed method α.

contract parties are recorded and can be accessed by external
parties. This is because contract parties run on a blockchain.
E. Failure Model
Contract parties do not fail, because they run on a
blockchain. External parties can fail, but the polynomial-time
restriction still applies.
IV. P ROPOSED M ETHOD Α
The proposed method α is designed as a dapp on a
blockchain. We describe the protocol using the computation
model introduced in Section 3.

Algorithm 1 Announcement start phase
1: function I NITIALIZE (hk ,content,correctness)
2:
Let
the
initialargumentsofO
be(hk ,content,correctness).
3:
Let
the
initialargumentsofC
be(hk ,λ,λ,λ,λ,{λ},λ,{λ}).
4:
Let the initial arguments of Pi be (hk ).
5: end function
6: procedure O(hk ,content,correctness)7:
send (aC , Hash(hk , content), Hash(hk , correctness))
8:
return (hk ,content,correctness)
9: end procedure
10: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })11:(from, d1 , d2 ) ← receive12:
if from = aO ∧ phase = λ then13:
return (hk , “announcement”, d1 , d2 , content ′ ,{hAnswer a }, correctness ′ , {correct a })14:
end if15:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })16: end procedure

A. Parties
The hash key is the same for all parties. Figure 1 illustrates
the parties in this method.
• Questioner O is an external party that holds an exam.
∪
O has the hash key hk ∈ k∈N HK k , the exam content∪Nncontent ∈ n=0 {0, 1} , and the correctness judgment∪Nnprogram correctness ∈ n=0 {0, 1} as the initial argu2
ments .
• Contract C is the only contract party required by our∪
method. C has the hash key hk ∈ k∈N HK k as its initialargument.
• Answerer Pi is an external party that takes an exam. Pi∪
has the hash key hk ∈ k∈N HK k as their initial argument. They can also interrogate an oracle answer i ∈ CO,
which outputs an answer of at most N − na bits whenthe exam content is input.
B. Intuitive Description1) (Announcement start phase) O sends Hash(hk , content)
and Hash(hk , correctness) to C. C records the receiveddata.
2) (Announcement phase) O announces an exam and invites answerers. The channel used for the announcement
is not speciﬁed in this method.
3) (Submission start phase) When it is time to start theexam, O sends content to C. C computes the cryptographic hash of the received data and veriﬁes that itmatches the one recorded in Step 1. If it matches, thereceived data are recorded as content ′ .
2 The judgment program must be a pure function. In other words, the program must not change its behavior according to the environment surrounding
it. Otherwise, the results of some judgments will be unable to be uniquelydetermined.

Algorithm 2 Announcement phase
1: Do nothing.

4) (Submission
phase)
Each
Pi
sends
Hash(hk , answer i (content ′ )∥aPi ) to C to submit
their answer3 .
5) (Judgment start phase) When it is time to end theexam, O sends the correctness to C. C computes thecryptographic hash of the received data and veriﬁes thatit matches the one recorded in Step 1. If it matches, thereceived data are recorded as correctness ′ .
6) (Judgment phase) Each Pi sends answer i (content ′ ) to
C. C computes the cryptographic hash of the bitstring
concatenation of the received data and the source address
and veriﬁes that the hash matches the hash recorded in
Step 4. If it matches, the received data are judged bycorrectness ′ , and the result of the judgment is recorded.
C. Formal Description
The formal description is given in Algorithms 1–6.
D. Validity
The validity of the method is mathematically guaranteed
by attributing it to the properties of the cryptographic hashfunction.
We omit detailed description of validity of the method α
due to page limit.
3 For the simplicity of the mathematical proof, we assume that each Pisubmits their answer only once in the model. In practice, this restrictionis unnecessary, and in our proof of concept using Ethereum, which will be
described later, an answerer can submit an answer any number of times.

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

Algorithm 3 Submission start phase
1: procedure O(hk ,content,correctness)2:
send (aC , content)
3:
return (hk ,content,correctness)
4: end procedure
5: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })6:(from, d) ← receive7:
if from = aO ∧ phase = “announcement” ∧Hash(hk , d) = hContent then8:
return(hk ,“submission”,
hContent,
hCorrectness, d, {hAnswer a }, correctness ′ , {correct a })9:end if10:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })11: end procedure
Algorithm 4 Submission phase
1: procedure Pi (hk )2:
Get content ′ from the return value of the most recent
action of C.
3:
send (aC , Hash(hk , answer i (content ′ )∥aPi ))4:
return (hk )5: end procedure
6: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })7:(from, d) ← receive8:
if phase = “submission” ∧ hAnswer from = λ then9:
{newHAnswer a }
←
{d
(a
=
from), hAnswer a (a ̸= from)}10:
return (hk , phase, hContent, hCorrectness,
content ′ , {newHAnswer a }, correctness ′ , {correct a })11:
end if12:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })13: end procedure
Algorithm 5 Judgment start phase
1: procedure O(hk ,content,correctness)2:
send (aC , correctness)3:
return (hk ,content,correctness)
4: end procedure
5: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })6:(from, d) ← receive7:
if from = aO ∧ phase = “submission” ∧Hash(hk , d) = hCorrectness then8:
return(hk ,“judgement”,
hContent,
hCorrectness, content ′ , {hAnswer a }, d, {correct a })9:end if10:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })11: end procedure

Algorithm 6 Judgment phase
1: procedure Pi (hk )2:
Get content ′ from the return value of the most recent
action of C.
3:
send (aC , answer i (content ′ ))4:
return (hk )5: end procedure
6: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })7:(from, d) ← receive8:
if phase = “judgement” ∧ Hash(hk , d∥from) =hAnswer from ∧ correct from = λ then9:
{newCorrect a } ← {correctness ′ (d) (a =from), correct a (a ̸= from)}10:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {newCorrect a })11:
end if12:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {correct a })13: end procedure

1) Impossibility of Changing Exam Content: It can be
guaranteed that O cannot change the exam content after thestart of the announcement.
2) Impossibility of Changing the Correctness Judgment
Programs: It can be guaranteed that O cannot change thecorrectness judgment program after the start of the announcement.
3) Impossibility of Changing Answers: It can be guaranteedthat Pi cannot change their answer after submitting it.
4) Validity of the Results of the Correctness Judgment:
The above properties provide a corollary that guarantees thevalidity of the result of the correctness judgments if nosabotage attack is made.
5) Conﬁdentiality of the Exam Content: It can be guaranteed that as long as O behaves correctly, Pi cannot know theexam content before the submission start phase.
6) Conﬁdentiality of the Correctness Judgment Programs:
It can be guaranteed that as long as O behaves correctly,
Pi cannot know the correctness judgment program before thejudgment start phase.
7) Conﬁdentiality of Answers: It can be guaranteed that a
Pi cannot know the answer of another who behaves correctly
before the judgment start phase.
E. Discussion
We discuss the feasibility of applied attacks on the proposed
method α and the economic cost when the complexity of thecorrectness judgment program is large.
1) Replay Attacks by Answerers: It is guaranteed thatanswerers cannot know the answers of others. However, even
if they cannot know the answers of others, they may be able
to conduct a replay attack to steal the answers by reproducing
the communication of others. Our method is also resistant
to replay attacks because answerers do not simply hash theirProc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

answer but combine it with their address before hashing. This
makes it impossible to steal the answers even if an answerer
reproduces the communication of others who have different
addresses.
2) Length Extension Attacks by Answerers: When answerers know hk and Hash(hk , m1 ), they may be able to compute
Hash(hk , m1 ∥m2 ), where m2 is chosen by them. This attack
is called a length extension attack and is known to be effective
against MD5 and SHA-1.
In our method, they may be able to steal answers by using
a length extension attack. As a countermeasure, we should use
SHA-256 or Keccak-256, which are resistant to attacks. In our
proof of concept using Ethereum, we use Keccak-256.
3) Sabotage Attacks by Questioners: In our method, O
needs to actively follow the protocol. Therefore, O can perform a sabotage attack. As a countermeasure, we can make O
pay a deposit in cryptocurrency in advance and conﬁscate it
when O performs a sabotage attack. In our proof of concept
using Ethereum, we implement this feature.
4) When Exam Content or a Correctness Judgment Program is Invalid: A malicious O may prepare invalid content
or correctness and conduct a meaningless exam. The only way
to prevent this attack is to perform a prior audit by a trusted
authority. However, in our method, content and correctness
are disclosed before the answers are disclosed, so it is possible
to prevent answers from being given to a malicious O.
5) When the Majority of Block Approvers are Bought Off:Thus far, we have assumed that each transaction is approved
after some time. However, it is possible to bribe the majorityof block approvers to stop the approval of a transaction.
We believe that this attack is not feasible on major
blockchains because the following disadvantages arise whenblock approvers participate in an attack:First, if a mining pool participates in an attack, the social
credibility of the pool will be lost. In major PoW-based
blockchains such as Ethereum, all the major block approvers
are mining pools, so this disadvantage cannot be ignored.
Second, if a major block approver participates in an attack,their blockchain loses its public trust. Therefore, the market
value of their cryptocurrency will decrease, and block approval
rewards will decrease.
Third, the risk of a 51% attack increases because the amountof computational power needed to extend the main chain is
reduced during an attempt at this attack; a successful 51%
attack results in a loss of public trust in the blockchain.
Some rewards in addition to the above disadvantages must
be offered to multiple block approvers. For example, Ethereum
requires the acquisition of at least three mining pools [9].
Therefore, we believe that this attack is not feasible.
6) When the Complexity of the Correctness Judgment Program is Large: In the proposed method α, the economic costof Pi becomes large when the complexity of correctness islarge. This is because the computation of correctness is doneon a blockchain. Therefore, we discuss the proposed method
β, which incorporates the concept of mutual evaluation.

V. P ROPOSED M ETHOD Β
The proposed method β reduces the economic cost by mutual evaluation among the answerers instead of a correctness
judgment on the blockchain.
A. Intuitive Description1) (Announcement start phase—Submission phase) These
are the same as those of the proposed method α.
2) (Publication start phase) This is the same as the judgment start phase of the proposed method α.
3) (Publication phase) Each Pi sends answer i (content ′ ) to
C to publish their answer. C computes the cryptographic
hash of the bitstring concatenation of the received data
and the source address and veriﬁes that the hash matches
the hash recorded in Step 4. If it matches, C records
the source address as participants n and the received
data as answers ′n , increments n, and records a uniformly
selected value from {0, . . . , n − 1} as r.
4) (Peer-review phase) Each Pi takes j suchthat participants j matches ( their own address)

sends
correctness ′ answers ′(j+r) mod n ,()
correctness ′ answers ′(j+r+1) mod n ,and()
correctness ′ answers ′(j+r+2) mod n to C to evaluate
the others’ answers. C takes j such that participants jmatches the source address and pushes the received
data to correct (j+r) mod n , correct (j+r+1) mod n , andcorrect (j+r+2) mod n . Finally, whether 2 or more True
are pushed to correct j determines the result of thecorrectness judgment of the answerer whose address isparticipants j .
5) (Revision phase) Pi sends j to C if the result of thecorrectness judgment of the answerer whose address isparticipants j is wrong. C revises the result by computing correctness ′ (answers j ).
andB. Formal Description
The formal description is given in Algorithms 7–9. We omit
the phases before the publication phase because they are only
trivial modiﬁcations of the proposed method α.
C. Discussion
We discuss the incentives and the number of people formutual evaluation. The discussion of the proposed method α
in Section IV-E is also applicable to the proposed method β.
1) The Economic Cost: If the mutual evaluation isdone properly, the economic cost of Pi decreases toO(|answer i (content)|) because nothing needs to be done in
the revision phase.
2) The Incentives: The discussion thus far does not take
into account the incentives for proper mutual evaluation, which
may not necessarily reduce the economic cost. As a countermeasure, we can make Pi pay a deposit in cryptocurrency
when they publish their answer and conﬁscate it when theyevaluate others’ answers improperly. Furthermore, a Pi who
revises the result of a correctness judgment in the revision

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

Algorithm 7 Publication phase
1: procedure Pi (hk )2:
Get content ′ from the return value of the most recent
action of C.
3:
send (aC , Hash(hk , answer i (content ′ )))4:
return (hk )5: end procedure
6: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })7:(from, d) ← receive8:
if phase = “publication” ∧ Hash(hk , d∥from) =hAnswer from ∧ from ∈/ {participants j | j ∈ {0, . . . , n −1}} then
9:{newPartcipants j } ← {participants j (j ∈{0, . . . , n − 1}), from (j = n)}10:{newAnswers j } ← {answer j (j ∈ {0, . . . , n −1}), d (j = n)}11:{newReviewedj } ← {reviewed j (j ∈ {0, . . . , n −1}), False (j = n)}
12:
newN ← n + 1
13:
Choose newR uniformly from {0, . . . , n − 1}.
14:
return(hk ,phase,
hContent,{hAnswer a },hCorrectness,
content ′ ,correctness ′ , {newParticipants j }, {newAnswers ′j },{newReviewedj }, newN , newR, {correct j })15:
end if16:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })17: end procedurephase can be compensated for the cost of the revision by
paying the conﬁscated cryptocurrency. In our proof of concept
using Ethereum, we implement this feature.
3) The Number of People: In the discussion thus far, thenumber of people for mutual evaluation has been set to 3, but
this is an example, and the number is arbitrary in practice.
VI. P ROOF OF C ONCEPT
We implemented a decentralized programming contest platform on Ethereum based on the proposed methods α and β.
The code is available at https://github.com/azonti/decentcoder.
The main branch corresponds to the proposed method α, andthe pm2 branch corresponds to the proposed method β.
Below, we propose solutions to the problems that emerged
during the implementation process and measure the economic
cost of the method using the implementation.
A. How to Distribute the Exam Content
When the proposed method is implemented as is, the exam
content is directly recorded on the blockchain. However,the cost of recording data on the Ethereum blockchain ishigh. Therefore, we implemented the following cost reduc-

Algorithm 8 Peer-review phase
1: procedure Pi (hk )2:
Get correctness ′ , {participants j }, {answers ′j }, n,and r from the return value of the most recent action ofC.
3:{j ′ } ← {j ∈ {0, . . . , n − 1} | participants j = aPi }
4:
send
(
(
)
aC , correctness ′ answers ′(j ′ +r) mod n ,()
correctness ′ answers ′(j ′ +r+1) mod n ,())
correctness ′ answers ′(j ′ +r+2) mod n
5:

return (hk )6: end procedureC(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })8:(from, d1 , d2 , d3 ) ← receive9:
if phase = “publication” ∧ from ∈ {participants j |j ∈ {0, . . . , n − 1}} ∧ from ∈/ {reviewed j | j ∈{0, . . . , n − 1}} then10:{j ′ } ← {j ∈ {0, . . . , n − 1} | participants j =
from}
11:
push d1 to correct (j ′ +r) mod n
12:
push d2 to correct (j ′ +r+1) mod n
13:
push d3 to correct (j ′ +r+2) mod n
14:{newReviewedj } ← {reviewed j (j ∈ {0, . . . , n −1} \ {j ′ }), True (j = j ′ )}15:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {newReviewedj }, n, r, {correct j })16:
end if17:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })18: end procedure
7: procedure

Algorithm 9 Revision phase
1: procedure Pi (hk )2:send (aC , j)3:
return (hk )4: end procedure
5: procedure C(hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })6:(from, d) ← receive7:
if phase = “publication” ∧ d ∈ {0, . . . , n − 1} then8:
push correctness ′ (answers ′d ) to correct d 4 times
9:
end if10:
return (hk , phase, hContent, hCorrectness,
content ′ , {hAnswer a }, correctness ′ , {participants j },{answers ′j }, {reviewedj }, n, r, {correct j })11: end procedure

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

tion method using the InterPlanetary File System (IPFS), a
distributed ﬁle system proposed by Benet [10]:1) In the announcement start phase, instead of recording
the cryptographic hash of the exam content on theblockchain, we record Advanced Encryption Standard(AES)-encrypted exam content on IPFS and record the
IPFS path on the blockchain.
2) In the submission start phase, instead of recording theexam content on the blockchain, the AES passphrase isrecorded on the blockchain.
Since the data on IPFS are content-addressed, it is possible
to achieve unchangeability similar to that of a cryptographic
hash function. However, since anyone who knows an IPFS
path can also know the content of the data, we use AES in
combination with this method to achieve conﬁdentiality.
B. How to Submit Answers
In the proposed method, when an answerer submits theiranswer, they submit the cryptographic hash of the bitstring
concatenation of their answer and their address. Then, thehash is computed on the blockchain when their answer ispublished and judged. However, this method requires loading
the entire answer into memory, which is costly. Therefore,
we implemented the following cost reduction method using
the EXTCODEHASH instruction proposed and introduced by
Johnson and Bylica [11]:1) In the submission phase, the answerers submit the hashof the bitstring concatenation of their answer’s hash andtheir address. In other words, their answer is hashedtwice.
2) In the publication and judgment phase, their answer
is deployed on the blockchain as a contract. In theblockchain, the EXTCODEHASH instruction is issued tocompute the hash of the answer, which is then combinedwith the source address and hashed again.
C. How to Check the Purity of Programs
The proposed method requires that correctness judgment
programs be pure; i.e., programs must not change their behavior according to the environment. Otherwise, some judgment
results will not be uniquely determined.
However, the Ethereum virtual machine has instructions toread values from the environment4 , which must be prohibited.
It may seem sufﬁcient to scan the instructions in a program
one by one to make sure that there are no instructions thatshould be prohibited. However, since there are also data areas
in a program, interpreting all data areas as instructions will
result in false positives with nonnegligible probability. We
devised the following method to reduce the probability of false
positives to a practical level:1) Scan the instructions in a program one by one from the
beginning. If an instruction that should be prohibited
4 ADDRESS, BALANCE, ORIGIN, CALLER, GASPRICE, EXTCODESIZE,
EXTCODECOPY, EXTCODEHASH, BLOCKHASH, COINBASE, TIMESTAMP,NUMBER, DIFFICULTY, GASLIMIT, SLOAD, GAS, CALL, CALLCODE,
DELEGATECALL, and STATICCALL

Table I
E CONOMIC COST
MethodαβFor a Questioner (USD)

For an Answerer (USD)

38.66
49.99

48.36
33.56

is encountered, go to step 2. If an invalid opcode,
STOP, JUMP, RETURN, REVERT, or SELFDESTRUCTis encountered, go to Step 3.
2) If JUMP, JUMPI, RETURN, or REVERT is encountered,determine that the program is nonpure. If an invalid
opcode, STOP, or SELFDESTRUCT is encountered, go
to step 3.
3) If JUMPDEST is encountered, go to Step 1.
The validity of this method is explained as follows: Only
areas from the beginning or JUMPDEST to invalid opcodes,
STOP, JUMP, RETURN, REVERT, or SELFDESTRUCT will
be executed. Therefore, only such areas need to be monitored.
Additionally, even if a prohibited instruction is executed, it
will be harmless because environment-dependent values will
be discarded unless JUMP, JUMPI, RETURN, or REVERTare executed afterwards. Hence, we only need to detect suchsituations.
D. Economic Cost Evaluation
We evaluated the economic cost of this implementation. The
data used to organize the pseudocontest for the evaluation areavailable at https://github.com/azonti/dbc001. Table I showsthe evaluation results. The gas price, which indicates theamount of cryptocurrency per instruction, was set to 25×10−9
ETH, and 1 ETH was set to 601.4 USD. The former is themedian gas price of newly approved transactions on December
6, 2020 [12], and the latter is the closing price of Bibox, acryptocurrency exchange, on December 6, 2020 [13].
E. Future Instruction Implementations Will Lower the Economic Cost
As mentioned earlier, this implementation guarantees thepurity of correctness judgment programs by scanning the
instructions. However, when the instructions below are implemented in the future, there will be no need to scan programs,
and the economic cost will decrease.
First, PURE_CALL is needed. Programs invoked throughthis instruction cannot execute instructions that read values
from the environment. This instruction was proposed by Buterin [14] in 2017 but has not yet been implemented.
Second, SANDBOXED_CALL is required. Programs called
through this instruction cannot call any other program. This
instruction was proposed by Zoltu [15] in 2016 but has not
yet been implemented.
Once the above instructions are implemented, we canprohibit the virtual machine from reading values from theenvironment. Thus, the need to scan programs is eliminated,
and the economic cost is reduced.

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021

Table II
E CONOMIC COST
WHEN PURE_CALL AND SANDBOXED_CALL ARE IMPLEMENTED
MethodαβFor a Questioner (USD)

For an Answerer (USD)

37.83
49.16

25.14
10.59

We estimated the economic cost of implementing these
instructions. The data used for the estimation are the sameas in Section VI-D. Table II shows the estimation results.
VII. C ONCLUSION
We proposed a decentralized examination protocol that canhandle a set of correct answers deﬁned by a program. The validity of the protocol, which consists of unchangeabilities andconﬁdentialities, is mathematically guaranteed by attributing
it to the properties of cryptographic hash functions. We alsostudied the feasibility of applied attacks such as replay attacks
and length extension attacks and proposed countermeasuresagainst such attacks.
We also implemented a decentralized programming contest
platform based on the proposed method on Ethereum anddemonstrated the feasibility of the method. In addition, we
proposed solutions to the problems that emerged during theimplementation process and measured the economic cost of themethod using the implementation. As a result, we conﬁrmedthat the method is feasible for approximately 30–40 USD.

R EFERENCES[1] J. Williams, “Who is Rick Singer? The key CEO helped Lori
Loughlin, Felicity Huffman daughters and plenty more wealthyscam their way into college,” https://www.newsweek.com/
rick-singer-college-admissions-scam-1384647, Apr. 2019, Accessed:
Aug. 1, 2021.
[2] S. Nakamoto, “Bitcoin: a peer-to-peer electronic cash system,” https://bitcoin.org/bitcoin.pdf, Oct. 2008.
[3] “Namecoin,” https://www.namecoin.org/.
[4] Y. Yoshimura, “New capture the ﬂag (CTF) using Bitcoin,” https://qiita.
com/yyu/items/b6f367eb876dd28e759a, Jan. 2018, Accessed: Dec. 10,2020 (in Japanese).
[5] K. Sawada, “CTF with prize using dapps,” https://narusejun.com/
archives/26/, Dec. 2018, Accessed: Dec. 10, 2020 (in Japanese).
[6] Y. Kaneko, S. Tanaka, T. Kimura, J. Okumura, S. Osada, S. Azuchi, “A
decentralized examination system using public blockchain technologies,”
IEICE Tech. Rep., 118(480), pp.233–238, Mar. 2019 (in Japanese).
[7] “Ethereum whitepaper,” https://ethereum.org/en/whitepaper/, Oct. 2020,
Accessed: Dec. 10, 2020.
[8] V. Buterin, “On public and private blockchains,” https://blog.ethereum.
org/2015/08/07/on-public-and-private-blockchains/, Aug. 2015, Accessed: Dec. 10, 2020.
[9] “Ethereum hash distribution,” https://blockchair.com/ethereum/charts/
hashrate-distribution.
[10] J. Benet, “IPFS — Content addressed, versioned, P2P ﬁle system,”arXiv:1407.3561v1 [cs.NI], Jul. 2014.
[11] N. Johnson, P. Bylica, “EIP-1052: EXTCODEHASH opcode,” Ethereum
Improvement Proposals, no.1052, May. 2018.
[12] “Ethereum median gas price chart,” https://blockchair.com/ethereum/
charts/median-gas-price.
[13] “ETH USD Bibox historical data,” https://www.investing.com/crypto/
ethereum/eth-usd-historical-data.
[14] V. Buterin, “Create pure_call.md,” https://github.com/ethereum/EIPs/
pull/195, Jan. 2017.
[15] M. Zoltu, “New opcodes: SANDBOXED_CALL,” https://github.com/
ethereum/EIPs/issues/117, Jun. 2016.

Proc. 4th IEEE Int'l Conf. on Blockchain(IEEE Blockchain 2021), pp.361-368, December 2021