論文 / 著書情報
Article / Book Information
題目(和文)
Title(English)

Primitives and Variants of the Proof-of-Work Mechanism in BlockchainBased Consensus Protocols

著者(和文)

蘇翔宇

Author(English)

Xiangyu Su

出典(和文)

学位:博士(理学),学位授与機関:東京工業大学,
報告番号:甲第12511号,
授与年月日:2023年9月22日,
学位の種別:課程博士,
審査員:田中 圭介,伊東 利哉,尾形 わかは,鹿島 亮,安永 憲司

Citation(English)

Degree:Doctor (Science),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第12511号,
Conferred date:2023/9/22,
Degree Type:Course doctor,
Examiner:,,,,

学位種別(和文)

博士論文

Type(English)

Doctoral Thesis

Powered by T2R2 (Tokyo Institute Research Repository)

Primitives and Variants of the Proof-of-Work
Mechanism in Blockchain-Based Consensus
Protocols
Xiangyu Su
Supervisor: Keisuke Tanaka
Department of Mathematical and Computing Science
Tokyo Institute of Technology

August 24, 2023

Acknowledgements
First and foremost, I would express my deepest gratitude to my supervisor Professor Keisuke Tanaka for all the support and encouragement since I
joined his laboratory in 2016. I am really, really glad and honored to havethe opportunity to be a member of his laboratory. I sincerely appreciate thetime he and Prof. Mario Larangeira spent on our discussion and the valuableadvice they gave us.
I want to express my great thanks to Prof. Xavier Defago and Dr. Yasumasa Tamura for their time and advice on Chapter 5.
I would thank Prof. Toshiya Ito, Prof. Wakaha Ogata, Prof. Ryo
Kashima, and Prof. Kenji Yasunaga, who referees my doctoral thesis andthank for their precious feedback.
I would also like to thank all members and related members of Tanaka
Laboratory for the delightful time we spent both in and out of the office.
I would especially thank Dr. Maxim Jourenko, Dr. Masayuki Tezuka, andPengfei Wang for the fruitful time in collaboration studies with them.
I would express my gratitude to my family for their support, and especially to my grandpa, who always felt proud of me.
At last, I would thank my beloved girlfriend Yue Zhang for her company,
support, and the colorful life she brought to me. Also, I would like to thankmy cute cat, Homura, for all the MEOWs.

1

Contents
1 Introduction
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 PoW from Computationally Hard Primitives . . . . . .
1.2.2 Blockchain from Deep Learning Tasks . . . . . . . . . .
1.2.3 Consensus from Competitive PoX . . . . . . . . . . . .

4
4
5
6
6
7

2 Preliminaries
2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Frameworks and Definitions . . . . . . . . . . . . . . . . . . .
2.2.1 General PoX Framework . . . . . . . . . . . . . . . . .
2.2.2 Security Definitions . . . . . . . . . . . . . . . . . . . .

8
8
8
8
9

3 PoW from Computationally Hard Primitives
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Our Trusted Generator PoW Scheme . . . . . . . . . . . . . .
3.2.1 Formal Syntax . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Security Properties . . . . . . . . . . . . . . . . . . . .
3.3 Our Construction . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Generic Construction . . . . . . . . . . . . . . . . . . .
3.3.3 Concrete Constructions . . . . . . . . . . . . . . . . . .
3.4 Efficiency and Security . . . . . . . . . . . . . . . . . . . . . .
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12
12
13
13
14
16
16
19
20
21
24

4 Blockchain from Deep Learning Tasks
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Review of Existing Works . . . . . . . . . . . . . . . .
4.1.2 Our Approach and Contributions . . . . . . . . . . . .
4.1.3 Final Preparations . . . . . . . . . . . . . . . . . . . .
4.2 The D-PoDL Scheme . . . . . . . . . . . . . . . . . . . . . . .

25
25
25
27
29
29

2

4.2.1 Design Overview . . . . . . . . . . . . . . . . . . . . .
4.2.2 Formal Syntax and Construction . . . . . . . . . . . .
4.2.3 Design Choices Explanation . . . . . . . . . . . . . . .
D-PoDL-Based Blockchain Protocols . . . . . . . . . . . . . .
4.3.1 Generic Protocol Workflow . . . . . . . . . . . . . . . .
4.3.2 Concrete Protocols . . . . . . . . . . . . . . . . . . . .
Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 The Training Oracle . . . . . . . . . . . . . . . . . . .
4.4.2 Proving Ledger Properties . . . . . . . . . . . . . . . .
Implementation of D-PoDL Scheme . . . . . . . . . . . . . . .
Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30
31
33
35
36
39
40
41
43
46
48

5 Consensus from Competitive PoX
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Our Approach and Contributions . . . . . . . . . . . .
5.1.2 Final Preparations . . . . . . . . . . . . . . . . . . . .
5.2 Model of Blockchain-Based Double Auction . . . . . . . . . .
5.2.1 Definitions for the Blockchain Data Structure . . . . .
5.2.2 The Bid Assignment Problem (BAP) . . . . . . . . . .
5.3 BAP-Based PoW and Competitive PoX . . . . . . . . . . . . .
5.3.1 Formal Syntax of BAP-based PoW . . . . . . . . . . .
5.3.2 Competitive PoX and Scheme Modeling . . . . . . . .
5.4 Competitive PoX-Based Protocol . . . . . . . . . . . . . . . .
5.4.1 Block-Tree and Score of Branches . . . . . . . . . . . .
5.4.2 Protocol Description . . . . . . . . . . . . . . . . . . .
5.5 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Persistence . . . . . . . . . . . . . . . . . . . . . . . .
5.5.2 Block-Liveness . . . . . . . . . . . . . . . . . . . . . .
5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49
49
50
53
54
55
57
61
63
67
69
70
72
74
75
82
82

4.3

4.4

4.5
4.6

3

Chapter 1
Introduction
1.1

BackgroundConsensus has been a long-standing research topic in the field of distributed
systems for multiple decades. Participants in a consensus protocol seek toagree on a log of messages that satisfies two crucial properties: (1) persistence, i.e., all honest participants’ logs agree with each other except for somelogs may progress faster than others; (2) liveness, i.e., messages received as
input by honest participants get confirmed in all honest participants’ logs
quickly [26,45]. Conventionally, this can be achieved by the Byzantine FaultTolerance (BFT) algorithms [13,37]. However, the high communication complexity of these algorithms prevents them from being deployed in large-scale
networks, e.g., decentralized digital currency systems, in which consensus isnecessary for settling transactions.
In light of early attempts of digital currencies [14,15], Satoshi Nakamoto [42]proposed the Bitcoin system atop a proof-of-work (PoW) [20]-based blockchain
protocol. On a high level, a blockchain is formed by chaining blocks of messages (or transactions in the case of digital currency) with hash functions,
i.e., by requiring the later block to include the hash of its previous block.
In order to generate a block, the PoW mechanism requires its participants(usually called provers or miners) to solve a moderately hard computationaltask, i.e., the difficulty of PoW. Hence, provers who successfully solve thetask are eligible to collect transactions and generate a block.
The public verifiability of the hash chain and the task guarantees thatany participants in a blockchain protocol can verify the validity of any given
block or blockchain. Moreover, due to the difficulty of PoW, the number ofvalid blocks generated during a period of time is bounded by the provers’
computing power. If the number is one, then participants will agree on the4

only valid block to extend the blockchain. Otherwise, there will be “forks”.
By assuming an honest majority, i.e., more than half of the participants arehonest, and applying the longest-chain rule [26], i.e., honest participants only
accept and extend the longest chain in their view, the shorter chain (fork)
will eventually “die out”. The reason is that honest computing power within
the network will concentrate on the longest chain and outperform adversaries
who intend to work on shorter forks.
Considering a concrete PoW, the most well-adopted construction is basedon hash functions. Given a difficulty parameter T > 0, provers are required
to find a nonce such that the hash of the previous block and the nonce is lessthan T . For a hash function Hash : {0, 1}∗ → {0, 1}n , finding a valid nonce
is expected to need 2n /T hash evaluations; whereas, the verification requires
only one hash check.
Although it has been proven that the Nakamoto-style blockchain protocol
from the aforementioned hash-based PoW satisfies persistence and livenessunder the random oracle model [26], the hash evaluation itself is wasteful inenergy and meaningless other than generating blocks. Therefore, numerous
alternative PoW schemes, i.e., proof-of-X (PoX), have been proposed to utilize more “useful” tasks, e.g., proof-of-useful-work (PoUW) [6, 23], or otherresource, e.g., proof-of-stake [19, 35] and proof-of-space [22].

1.2

Our Results

In this thesis, we will present three results [51–53] related to these primitives and variants of PoW. We start from looking back into the origin [20],i.e., a resource-demanding verifiable computation (for combating junk mail).
Instead of hash functions, we show a generic construction based on computationally hard primitives that can be instantiated with different kinds ofresources (i.e., time and memory); Next, back in the sense of blockchain protocols, we investigate a subset of the PoUW, i.e., with deep learning tasks as
the useful work. We propose a distributed proof-of-deep-learning (D-PoDL)
scheme and transform it into a provably secure blockchain protocol that cantake different chain selection rules into consideration; Finally, in the last result, we consider a competitive PoX framework which is generalized froma score-based assignment problem abstracted from double auction systems.
We show the design of a competitive PoX-based blockchain protocol that canalso achieve consensus but requires significant modification compared to theexisting approaches.

51.2.1

PoW from Computationally Hard Primitives

In contrast to the hash-based construction that requires the random oracle
model in security analysis, one can better argue the security of a computationally hard primitive-based PoW [6]. This result proposes a generic PoW
construction based on one-way trapdoor functions [29] and asymmetricallyhard functions [8]. Intuitively, provers are required to invert a one-way function with the help of an instance from the hard function. The task is designed
in a way that the evaluation of the hard function instance equals the trapdoor of the one-way function. Hence, the prover can compute the inversion
by first evaluating the hard function to obtain the trapdoor. Additionally,
we show two concrete constructions based on the RSA problem [49]. The
first one takes time as the difficulty resource, which is built atop the RSWtime-lock puzzle [48]; whereas, the second one considers memory and is built
atop a memory-hard function, i.e., the DIODON function [8]. Note that ourtask generation unavoidably incurs trust in the generator, which will limit
the usefulness of our approach in distributed scenarios. However, since thisresult considers PoW as a resource-demanding verifiable computation, we
argue that our constructions fulfill this purpose and show enough versatility
for being capable of using either time or memory as the difficulty resource.

1.2.2

Blockchain from Deep Learning Tasks

For the second result, we investigate the potential of using deep learning tasks
as useful work in PoUW. Existing works on deep learning-based PoUW1 relyon strong assumptions, cannot act as a distributed solver among provers,
and lack security proofs for the blockchain protocols built atop them. We
overcome these drawbacks by designing a hash-train-hash structure in thesolving algorithm and enabling provers to refer to others’ pre-trained models with a model-referencing mechanism. Then, based on our scheme, we
propose a generic blockchain protocol that is capable of two different chain
selection rules: i.e., the longest-chain rule [26] and the weight-based framework [27, 33]. Hence, we can derive two concrete blockchain protocols fromthe generic design. For security, we analyze the block generation rate andshow both our concrete protocols satisfy the robust ledger properties [26,33],
i.e., chain growth, chain quality, and common prefix, which derive persistence
and liveness as proven in [26].
1Details of related works can be found in Chapter 4.

6

1.2.3

Consensus from Competitive PoX

The starting point of this result has two aspects: (1) a general double auction
system in which participants can bid and match their bids to form transactions; (2) the weight-based PoW has a rather constrained weight distribution [33] for satisfying consensus which cannot be applied for general (scorebased) optimization problems. Therefore, we first refine the blockchain data
structure to add support for bidding operation. Then, we abstract a bidassignment problem (BAP) as the underlying task for a PoW. However, weobserve that, unlike any existing PoX schemes, the difficulty of the BAPbased PoW lies in competition among provers. Hence, we further abstract
it into a competitive PoX framework. Notice that we can drop the “work”,
but only need to focus on the score distribution of blocks. Based on theframework, we design a protocol that achieves consensus on a blockchain
but has intermediate states in the tree (forest) structure. By considering
the accumulated score of each branch on the tree and adopting the “highestscored-branch” rule, we conclude that under an appropriate accumulating
function, our protocol can achieve consensus even assuming an arbitrary
score distribution.

7

Chapter 2
Preliminaries
2.1

NotationsThroughout this thesis, we use λ for the security parameter. The negligible
function of λ is denoted with negl(λ). For an integer k ∈ N, [k] denotes$

the set {1, . . . , k}. Given a set X , x ← X denotes that x is randomly anduniformly sampled from X . For an algorithm Alg, x ← Alg denotes that x
is assigned the output of an algorithm Alg on fresh randomness. Let Hashdenote a collision-free hash function.

2.2

Frameworks and Definitions

Execution model. General protocol executions are modeled by the standard Interactive Turing Machines (ITM) approach [12]. A protocol refers
to algorithms for a set of nodes (participants) to interact with each other.
All corrupted participants are considered to be controlled by an adversary
A who can read inputs and set outputs for these nodes. We will present
concrete settings with respect to each result.
Next, we show the general PoX framework.

2.2.1

General PoX Framework

Recall the hash-based PoW. Given a hash function Hash : {0, 1}∗ → {0, 1}nand a difficulty parameter T > 0, provers are required to find a nonce nonce
such that Hash(prevBK, nonce) < T . We abstract this approach into a general
PoX framework which involves a task generation algorithm TaskGen, a solving
algorithm Solve, and a verification algorithm Verify.

8Definition 1 (Syntax of General PoX) The tuple of algorithms (TaskGen,
Solve, Verify) in a general PoX scheme performs as follows:• TaskGen(1λ , kind, u) takes as input the security parameter λ, the kind ofresource kind, e.g., time, memory or storage, and the designed amountof resource units u. It outputs public parameters pp such that (kind, u) ∈pp, and a task task;• Solve(pp, task) takes as input pp, a task task. It outputs a proof π forthe given task task;• Verify(pp, task, π) takes as input pp, a task task, and a proof π. It
outputs 1 if π is a valid according to task; Otherwise, it outputs 0.
Here, we consider the correctness and efficiency of the general framework.
Other security definitions, e.g., difficulty, will be given with respect to concrete schemes.
Definition 2 (Correctness) A general PoX satisfies perfect correctness if
the following property holds for any λ, kind, u, and (task, aux) ← TaskGen(1λ ,kind, u):Pr [Verify(pp, task, Solve(pp, task) = 1] = 1.
Efficiency requires that TaskGen and Verify should run in time Õ(λ)1 , andshould be logarithm of the run time of Solve.

2.2.2

Security Definitions

Here, we introduce security definitions of blockchain protocols in the following.
Persistence and liveness. Typically in distributed ledgers, each transaction changes the state of the protocol. Thus, it is convenient to introduce anotation to address this framework. Assume the existence of two states st1tx
and st2 , let st1 → st2 denote the state change from st1 to st2 introduced by∗a transaction tx. Moreover, let st → st′ denote the transition between two
states caused by a finite number of transactions. Under our protocol execution setting, we recall the ledger properties, i.e., persistence and liveness, as
discussed in [26].
1

If f (λ) ∈ Õ(λ), there exists k > 0 such that f (λ) ∈ O(λ · logk (λ).

9• Persistence. For any two nodes, say, S1 and S2 , and any two slots t1 ≤ t2 ,if the list of settled transaction of S1 in t1 is equal to LOG1 , and the totaltransactions for S2 is LOG2 , thus LOG1 is a prefix of LOG2 ;• Liveness. If a transaction tx is available to all nodes at a point when thelatest slot for the honest nodes is t, then any node whose clock advancesτ slots to the point of t′ , we will have a ledger such that the state st, for∗tx∗which it holds that st0 → st1 → st2 → st.
Robust ledger properties. The definitions of robust ledger properties,i.e., chain growth, chain quality, and common prefix, originate from [26]. We
adopt the modified version from [23] for the longest-chain-based protocol.
Moreover, we also include the weight-based variant from [33].
Definition 3 (Robust Ledger Properties) The three aspects of the robust ledger properties are defined as follows.
• Chain growth: For any honest miner with chain chain at a round, thechain growth with parameter τ ∈ (0, 1] and s ∈ N states that for any
portion of chain spanning s consecutive rounds, the number of blocks inthis portion is at least τ s;
• Existential chain quality: For any honest miner with chain chain at around, the existential chain quality with parameter s ∈ N states thatfor any portion of chain spanning s consecutive rounds, at least one
honestly-generated block appears in this portion;• Common prefix: For any two honest miners with chains chain1 , chain2
at round r1 , r2 respectively, where r1 ≤ r2 , the common prefix withparameter s ∈ N indicates that chain1 should be a prefix of chain2 after
removing the last s blocks.
Definition 4 (Weight-Based Robust Ledger Properties) The three aspects of the weight-based robust ledger properties are defined as follows.
• Chain growth: For any honest miner with chain chain at a round, thechain growth with parameter τ ∈ (0, 1] and s ∈ N states that for any
portion of chain spanning s consecutive rounds, the accumulated weights
appearing in this portion is at least W(chain2 ) ≥ W(chain1 ) + τ s;
• Existential chain quality: For any honest miner with chain chain at around, the existential chain quality with parameter s ∈ N states thatfor any portion of chain spanning s consecutive rounds, the fraction ofhonest blocks’ weights in this portion is at least µ;
10• Common prefix: For any two honest miners with chains chain1 , chain2
at round r1 , r2 respectively, where r1 ≤ r2 , the common prefix withparameter s ∈ N indicates that chain1 should be a prefix of chain2 after
removing the last s blocks.
As explained in [45], persistence is equivalent to the common prefix property, and liveness can be derived from robust ledger properties.

11

Chapter 3
PoW from Computationally
Hard Primitives
This chapter takes a detour to investigate PoW outside the blockchain scenario. In this case, it can be regarded as a resource-demanding computation
mechanism with public and efficient verification. We show a generic construction that can be instantiated with primitives requiring different kindsof resources (i.e., time and memory) [52].

3.1

Overview

Since our purpose is to construct PoW from computationally hard primitives,a naive idea is to invert one-way functions [29]. However, (1) a PoW should
be moderately hard, and (2) the difficulty of PoW should be easy to adjust,
we notice that: (1) inverting a general one-way function may require morecomputing power than being “moderate”, and (2) adjusting difficulty usuallyends in changing the security parameter, hence, the security guarantee of thewhole PoW.
Another straightforward idea is to require provers to evaluate a hard
function. Proposed in [8], evaluating such functions requires a significant but
adjustable amount of resources. However, it is hard to verify the result of ageneral hard function1 , i.e., verifiers may have to run the whole evaluation,
hence, violating the efficiency requirement of PoW.
Now, we consider a trapdoored version of the one-way function. Inverting
such a function with the corresponding trapdoor will be easy. Hence, our final idea is to provide provers with the trapdoor of the one-way function from
1
There exists efficient proofs [46, 54] for concrete hard functions, e.g., the RSW timelock puzzle [48].

12the evaluation of a hard function. However, this approach requires that thetask generator must set the result of hard function evaluation to the trapdoorof the one-way function, which means: (1) the task generator must be trustworthy; (2) an efficient task generator must be able to bypass the hardness ofthe hard function. For the second aspect, we adopt the asymmetrically hard
function [8], in which resource consumption for evaluation can be reducedwith a corresponding bypassing key.
In the following section, we will first present the syntax of our trusted
generator PoW (TG-PoW).

3.2

Our Trusted Generator PoW Scheme

As introduced above, our TG-PoW extends the conventional PoW by granting provers an auxiliary input corresponding to the task. This design enables
provers to compute a piece of aid from the auxiliary that significantly reduces
the computing time of solving the task. Hence, instead of relying on the difficulty of the computational task, TG-PoW requires its provers to contributeenough resources in computing the aid. With concrete constructions given in
Section 3.3.3, we will show that the resource can be time like in conventional
PoW schemes, or memory, without changing the TG-PoW framework.

3.2.1

Formal Syntax

Like the general PoX framework, the TG-PoW scheme consists of three algorithms. However, in order to reflect the characteristic of our task generationand solving process, we add modifications to these algorithms. Note that weonly consider time and memory as the resource in the following.
Definition 5 (TG-PoW Scheme) The tuple of algorithms (tdTaskGen, EvalSolve,
Verify) in a TG-PoW scheme performs as follows:• tdTaskGen(1λ , kind, u, td) takes as input the security parameter λ, thekind of computational resource kind ∈ {time, memory}, the designed
amount of resource units u, and an additional trapdoor td. It outputs
public parameters pp such that (kind, u) ∈ pp, and a computational task
task with its corresponding auxiliary aux;
• EvalSolve(pp, task, aux) takes as input pp, a computational task task,
and an auxiliary input aux. It is divided into two sub-procedures:– Eval(pp, aux) outputs a piece of aid information aid;
13

– Solve(pp, task, aid) outputs a solution solution of the given task;• Verify(pp, task, solution) takes as input pp, a task task, and a solution
solution. It outputs 1 if solution is a valid solution of task; Otherwise,
it outputs 0.

3.2.2

Security Properties

Similar to the general PoX framework, we define correctness.
Definition 6 (Correctness) A TG-PoW scheme satisfies perfect correctness if the following property holds for any λ, kind, u, td, and (task, aux) ←tdTaskGen(1λ , kind, u, td):
Pr [Verify(pp, task, EvalSolve(pp, task, aux) = 1] = 1.
Next, we consider the primary security property, i.e., difficulty, of our
TG-PoW scheme. Following the same notation of the hash-based PoW, wedenote the task difficulty with parameter T (λ, u) where λ is the security
parameter, and u is the resource demand. Difficulty requires that any prover
can only produce a valid solution to the task by using significantly fewer
resources with negligible probability of λ.
In order to formally define difficulty with respect to TG-PoW, we introduce two prior properties: soundness and hardness. Soundness requiresthat unless the adversary A honestly computes the piece of aid aid′ from
Eval with the given aux, the probability of the obtained solution solution′ ←A(pp, task, aid′ ) such that Verify(pp, task, solution′ ) = 1 is negligible of λ. In
contrast, hardness is defined over the resource, i.e., time and memory. It
indicates that any adversary on given aux can only obtain the valid aid using
less than the designed amount of resource with negligible probability of λ.
Formally, we define soundness as follows.
Definition 7 (Soundness) A TG-PoW scheme satisfies soundness if for
any adversary A who runs in time t(λ, c) ∈ (T (λ, u), O(2λ/c )) where c is a significant large constant value, the following property holds for any large enoughλ, any kind ∈ {time, memory}, u, td, and any (task, aux) ← tdTaskGen(1λ , kind,u, td):

aid′ ← A(pp, task) :Verify(pp, task, solution′ ) = 1
Pr≤ negl(λ).
solution′ ← Solve(pp, task, aid′ )Remark 1 (Achievable Soundness) Note that soundness requires bounds
on the adversary’s run time, i.e., t(λ, c) ∈ (T (λ, u), O(2λ/c )). The upper
14

bound derives from the run time upper bound of solving the underlying task
by brute force; whereas, the lower bound indicates that solving task without
using aux should be more difficult than evaluating the hard function on aux2 .
Next, we show the formal definitions for hardness with respect to timeand memory. First, we consider a generic game between a hardness adversary A and a challenger CH. The adversary is given access to an evaluation oracle OEval such that on query aux, and the oracle returns aid ←Eval(pp, aux, td). In general, the definitions are parameterized by a function
δ(λ, u) (in memory-hardness, we use (δtime , δmemory ) for potential time-memory
trade-offs [31]), which represents the designed resource demand when running
Eval honestly. The time-hardness is defined as follows.
Definition 8 (Time-Hardness) A TG-PoW scheme satisfies δ(u)-timehardness if for any ϵ > 0 and any adversary A who runs in time δ(u)1−ϵ
after oracle access (OEval ), the following property holds for any large enoughλ, u, kind=time, td, and any (task, aux∗ ) ← tdTaskGen(1λ , kind, u, td):
st ← AOEval (pp, {aux}[q] )Verify(pp, task, solution′ ) = 1  ≤ negl(λ).
Pr  aid′ ← A(st, aux∗ ) :solution′ ← Solve(pp, task, aid′ )∧aux∗ ∈
/ {aux}[q]Similarly, we have the following definition for memory-hardness.
Definition 9 (Memory-Hardness) A TG-PoW scheme satisfies (δtime (λ),δmemory (u))-memory-hardness if for any ϵ > 0 and any adversary A who runs
with (δtime (λ), δmemory (u)1−ϵ ) resource (considering potential time-memory tradeoff ) after oracle access (OEval ), the following property holds for any large
enough λ, u, kind=time, td, and any (task, aux∗ ) ← tdTaskGen(1λ , kind, u, td):
st ← AOEval (pp, {aux}[q] )Verify(pp, task, solution′ ) = 1  ≤ negl(λ).
Pr  aid′ ← A(st, aux∗ ) :solution′ ← Solve(pp, task, aid′ )∧aux∗ ∈
/ {aux}[q]Finally, in the difficulty game, we provide the adversary the full powerwith task and auxiliary. Recall that the soundness game only provides task,
whereas the hardness games only provide auxiliary. We grant the adversary
access to the evaluation oracle and an additional solving oracle OSolve suchthat on query (task, aux), OSolve returns solution ← EvalSolve(pp, task, aux) if(task, aux) ← tdTaskGen(·); otherwise, it returns ⊥. The difficulty is defined
as follows.
2

Otherwise, provers will solve task directly.

15

Definition 10 (Difficulty) A TG-PoW scheme satisfies T (λ, u)-difficulty
if for any ϵ > 0 and any adversary A who runs in time T (λ, u)1−ϵ (or T (λ)∆
time with at most u1−ϵ memory units after oracle access (O = (OEval , OSolve )),the following property holds for any large enough λ, u, kind=time, td, and any(task∗ , aux∗ ) ← tdTaskGen(1λ , kind, u, td):
st ← AO (pp, {(task, aux)}[q] ) :Verify(pp, task, solution′ ) = 1∧Pr
≤ negl(λ).
solution′ ← A(st, task∗ , aux∗ ) task∗ ∈/ {task}[q] ∧ aux∗ ∈/ {aux}[q]3.3

Our Construction

In this section, we first introduce the formal treatments of our aforementioned building blocks, i.e., one-way trapdoor functions [29] and asymmetrically hard functions [8]. Then, we show a generic construction of our TGPoW scheme from these building blocks. Finally, we instantiate the genericconstruction with the RSA [49] problem representing one-way trapdoor functions, the RSW time-lock puzzle [48] for asymmetrically time-hard functions,and the DIODON function [8] for asymmetrically memory-hard functions.

3.3.1

Building Blocks

We first adopt the definition of one-way trapdoor function families.
Definition 11 (One-Way Trapdoor Function Families) Let I be an in∆dex set. A collection of functions F = {fi : DiF → RFi }i∈I is one-way
trapdoor if the following properties hold.
• There exists a PPT algorithm GenF (1λ ) that takes as input the security
parameter λ, and outputs an index i ∈ I with the corresponding trapdoor
tdi of function fi ;• There exists a PPT algorithm SampleF (1λ , i) that takes as input λ andan index i ∈ I, and outputs x ∈ DiF ;• Given (i, x), the value fi (x) is polynomial-time computable;• One-wayness. For any PPT adversary A, for any (i, tdi ) ← GenF (1λ )and any x ← SampleF (1λ , i), we have:Pr[fi (A(1λ , i, fi (x))) = fi (x)] ≤ negl(λ);• Trapdoor one-wayness. There exists a PPT algorithm Invert(1λ , i, tdi , fi (x))
that outputs x for all x ∈ DiF .
16

Here, we formalize the implied definitions of asymmetrically hard functions from [8] under the similar syntax of function families. The definition
goes as follows.
Definition 12 (Asymmetrically Hard Function Families) Let I be an∆index set. A collection of functions G = {gi : DiG → RGi }i∈I is asymmetricallyhard if the following properties hold.
• There exists a PPT algorithm GenG (1λ , kind) that takes as input the
security parameter λ and resource kind kind ∈ {time, memory}, andoutputs an index i ∈ I with the corresponding bypassing key aki offunction gi ;• There exists a PPT algorithm SampleG (1λ , i) that takes as input λ andan index i ∈ I, and outputs x ∈ DiG and resource demand u;• Resource hardness. For any ϵ > 0 and any adversary A with at mostδ(u)1−ϵ resource for time (or (δtime (λ), δmemory (u)1−ϵ ) resource for memory), for any (i, aki ) ← GenG (1λ ) and any (x, u) ← SampleG (1λ , i), we
have:
Pr[A(1λ , i, x, u) = gi (x, u)] ≤ negl(λ);• Asymmetrical hardness. There exists a PPT algorithm AsyEval(1λ , i, aki ,x, u) that outputs gi (x, u) for all x ∈ DiG .
Asymmetrically hard function candidates. This chapter focuses on
asymmetrically hard functions with two kinds of resources, i.e., time andmemory. Here, we show the candidate constructions: the RSW time-lock
puzzle [48] for time-hardness and the DIODON function [8] for memoryhardness. We give descriptions of these constructions and prove them satisfying Definition 12.
Construction 1 (RSW Time-Lock Puzzle) The algorithms in the RSWtime-lock puzzle perform as follows. We omit G for simplicity.
• Gen(1λ , time) samples a large integer N = pq where p, q are prime numbers of length λ. It outputs (N, ϕ(N ) = (p−1)(q−1));$• Sample(1λ , N ) samples x ← Z∗N and outputs (x, u);• The function g(x, u) = x2u

mod N ;• AsyEval(1λ , N, ϕ(N ), x) outputs y = x2

u17

mod ϕ(N )mod N .

By Euler’s theorem, it is easy to prove y = g(x, u). Now, we formalize
the following assumption, which was implicitly mentioned in [10]. Recently,
this assumption has been proven to hold under the strong algebraic groupmodel [34].
Assumption 1 (RSW Time-Lock Assumption) For any ϵ > 0 and any
adversary A runs in at most δ(u)1−ϵ time, for any (i, aki ) ← GenG (1λ ) andany (x, u) ← SampleG (1λ , i), the following property holds:uPr[A(1λ , N, x, u) = x2

mod N ] ≤ negl(λ).

Hence, we conclude that the RSW time-lock puzzle scheme satisfies Definition 12 with the following lemma.
Lemma 1 RSW time-lock puzzles form an asymmetrically time-hard function family if the RSW time-lock assumption holds.
Now, we introduce the construction of the DIODON function from [8].
It puts forward the idea of the RSW time-lock puzzle, generating a list that
stores the results of RSW evaluations. Memory-hardness derives from chaining these results with a memory-hard hash function, i.e., the Scrypt [2],so that provers cannot delete a large fraction of stored results to finish theevaluation of the DIODON function.
Construction 2 (DIODON Function) The algorithms in the DIODON
function perform as follows. We omit G for simplicity.
• Gen(1λ , memory) samples a large integer N = pq where p, q are prime
numbers of length λ. It outputs (N, ϕ(N ) = (p−1)(q−1));$• Sample(1λ , N ) samples x ← Z∗N and outputs (x, (k, l, u)) where k, l are
additional parameters for the RSW time-lock puzzle and the Scrypt hashfunction;• The function first computes u RSW time-lock puzzles and stores thekresults in a list L = {L0 } ∪ {Li }i∈[u−1] where L0 = x and Li = L2i−1
k·i
mod N . Hence, for any i ∈ [u − 1], Li = x2
mod N . On the list,
the function performs the Scrypt hash function with parameter l, i.e.,
starting from Lu−1 , it computes an index j = Lu−1 mod u, and hashes
over Lu−1 and Lj . It then iterates l − 1 times with the result from theprevious hash as input. Finally, the function value g(x, u) is set to thelast result. Concrete algorithm can be found in Algorithm 1;

18

• AsyEval(1λ , N, ϕ(N ), x, (k, l, u)) evaluates the Scrypt hash function by
k·i
computing each result block of index i ∈ [u − 1] with x2 mod ϕ(N )mod N . It sets the final result as y. The concrete algorithm can befound in Algorithm 2.
Likewise, we have the following lemma for the DIODON function.
Lemma 2 DIODON functions form an asymmetrically memory-hard function family if the RSW time-lock assumption holds.
Proof 1 By Euler’s theorem, it is easy to prove y = g(x, u). Moreover, as
shown in [2], considering time-memory trade-off, the DIODON function is
optimally linearly memory-hard, i.e., there exists δtime (k, l, u) × δmemory (u) is
constant. Hence, to evaluate an instance of the DIODON function, a prover
can save a fraction of memory but must pay the same factor in time.

Algorithm 1: The DIODON Evaluation g(x, u)
Input N and (x, (k, l, u));Let L0 = x;
3 for i ∈ [u − 1] dok4
Li = L2i−1 mod N ;5 end
6 Let temp = Lu−1 ;7 for i ∈ {0} ∪ [l − 1] do
8Let j = temp mod u;
9Compute temp = H(temp, Lj );10 end11 Return g(x, u) = temp
1

2

Algorithm 2: The DIODON AsyEval
Input (N, ϕ(N )) and (x, (k, l, u));Compute e = 2k·(u−1) mod ϕ(N );3 Let temp = xe mod N ;4 for i ∈ {0} ∪ [l − 1] do
5Let j = temp mod u;
6Compute ej = 2k·j mod ϕ(N );7temp = H(temp, (xej mod N ));8 end
9 Return y = temp;
1

2

3.3.2

Generic Construction

Intuitively, the trusted generator first samples an asymmetrically hard func$tion g(·) ← G and its instance as aux. The generator evaluates g(aux) with the19asymmetrical evaluation process of the hard function, i.e., AsyEval(g, aux).
∆
By regarding the aid aid = g(aux) as the trapdoor of a one-way trapdoor
function, the generator can then find such a function f (·) ∈ F. Finally,tdTaskGen outputs an instance task = f (solution) of inverting the one-way
trapdoor function providing provers the auxiliary aux.
Construction 3 (Generic TG-PoW Construction) The tuple of algorithms (tdTaskGen, EvalSolve, Verify) of a TG-PoW scheme performs as follows.
• The trusted task generator performs tdTaskGen(1λ , kind, u, td):
– Run (g, ak) ← GenG (1λ , kind) such that g : DG → RG is an asymmetrical kind-hard function; Sample a ← SampleG (1λ , g) and set∆∆

aux = a; Run y ← AsyEval(1λ , g, ak, a, u) and set aid = y;
– Run (f, td) ← GenF (1λ ) such that f : DF → RF is an one-way
trapdoor function with trapdoor aid; Sample x ← SampleF (1λ , f )∆and set task = f (x);∆– Output (task, aux) = (f (x), a).
• Provers perform EvalSolve(pp, task, aux):– Parse (kind, u) ∈ pp and (task, aux) = (f (x), a);– Compute aid′ = g(a, u);∆– Output solution = x′ ← Invert(1λ , f, aid′ , f (x)).
• Any participant can perform Verify(pp, task, solution):– Parse (kind, u) ∈ pp, (task, aux) = (f (x), a), and solution = x′ ;– Output 1, if f (x′ ) = f (x); otherwise, output 0.

3.3.3

Concrete Constructions

Now, we instantiate our generic construction with two concrete constructions.
In both cases, we use the RSA problem [49] for the one-way trapdoor function.
Whereas, in the time-hard TG-PoW scheme, we utilize the RSW time-lock
puzzle [48] for the asymmetrically time-hard function; and in the memoryhard scheme, we use the DIODON function [8]. Concrete instantiations are
as follows.

20

Construction 4 (Time-Hard TG-PoW) Let p,q be two prime numbersof length λ.
• tdTaskGen(1λ , time, u, td). Parse td = (p, q). Compute N = pq andϕ(N ) = (p − 1)(q − 1). Sample a ← Z∗N and compute the u-RSW
utime-lock puzzle with td (or precisely, ϕ(N )), i.e., aid = a2 mod ϕ(N )∆mod N . If gcd(aid, ϕ(N )) ̸= 1, resample a. Otherwise, set aux = a.
Compute e, such that e · aid ≡ 1 mod ϕ(N ). Sample y ← Z∗N and∆output (task, aux) = ((N, e, y), a);• EvalSolve(pp, task, aux). Parse (kind, u) ∈ pp and (task, aux) = ((N, e, y), a).
u
Evaluate the u-RSW time-lock puzzle, i.e., aid′ = a2 mod N . Com′∆
pute x′ = y aid mod N and output solution = x′ ;• Verify(pp, task, solution). Parse (kind, u) ∈ pp, (task, aux) = ((N, e, y), a),and solution = x′ . Output 1 if x′ e = y mod N ; otherwise, output 0.
Construction 5 (Memory-Hard Construction) Let p,q be two prime numbers of length λ.
• tdTaskGen(1λ , memory, (k, l, u), td). Parse td = (p, q). Compute N =pq and ϕ(N ) = (p−1)(q−1). Sample a ← Z∗N and compute the (k, l, u)DIODON function with td (or precisely, ϕ(N )). If gcd(aid, ϕ(N )) ̸= 1,∆
resample a. Otherwise, set aux = a. Compute e, such that e · aid ≡ 1∆
mod ϕ(N ). Sample y ← Z∗N and output (task, aux) = ((N, e, y), a);• EvalSolve(pp, task, aux). Parse (kind, u) ∈ pp and (task, aux) = ((N, e, y),′a). Evaluate the (k, l, u)-DIODON function for aid′ . Compute x′ = y aid∆
mod N and output solution = x′ ;• Verify(pp, task, solution). Parse (kind, u) ∈ pp, (task, aux) = ((N, e, y), a),and solution = x′ . Output 1 if x′ e = y mod N ; otherwise, output 0.

3.4

Efficiency and Security

We first estimate the lower bound of solving the RSA problem so that thesoundness parameter in the TG-PoW scheme, i.e., t(λ, c) in Definition 7,
is meaningful (as discussed in Remark 1). Considering the general number
field sieve algorithm [47], one of the fastest algorithms for factoring large
integers3 , we have the following assumption.
3

It is not clear if solving the RSA problem is as hard as factoring [11].

21Assumption 2 Let p,q be two prime numbers of length λ. Let N = pq andϕ(N ) = (p − 1)(q − 1). Given a well-chosen instance of the RSA problem,$i.e., (N, e, y) where gcd(e, ϕ(N )) = 1 and y ← Z∗N , for any algorithm A runsin ω(2λ/c ) time with c being a large enough coefficient, the following property
holds:
ePr[x′ ← A(N, e, y) : x′ = y mod N ] ≤ negl(λ).
Assumption 2 draws the line for soundness. Hence, we have a precise relation: T (λ, u) ≪ 2λ/c so that the soundness of TG-PoW with such parametersis achievable. With this in mind, the efficiency of the concrete constructions(time-hard one as an example) is as follows.
• tdTaskGen samples two elements from Z∗N and computes the RSW timelock puzzle via asymmetrical evaluation. The cost is determined by two
exponentiation operations in Z∗N , hence, in Õ(λ);• EvalSolve evaluates the RSW time-lock puzzle without the bypassing
key and computes the inversion of the RSA problem with a corresponding trapdoor. The cost is determined by the RSW evaluation, which is
δ(u), hence, matching the designed resource demand.
• Verify checks the validity of inverting the RSA problem with one exponentiation in Z∗N . Hence, the cost is Õ(λ).
Security Analysis In this section, we showcase the security proofs forthe time-hard TG-PoW construction. We first prove soundness and timehardness under Assumption 1 and Assumption 2c, respectively. Then, weshow difficulty as a derived property from soundness and hardness. The
security proof for memory-hard construction follows the same process with
only minor changes concerning the time-memory trade-off.
Theorem 1 Our time-hard TG-PoW in Construction 4 satisfies the following properties:• Correctness.
• Soundness under Assumption 2.
• Time-hardness under Assumption 1, following Lemma 1.
• Difficulty, by soundness and time-hardness.

22

Proof 2 Correctness is obvious due to the construction. We prove soundness, time-hardness, and difficulty as follows.
$Soundness: The uniform sampling a ← Z∗N ensures the uniformity of aid
and e that satisfy e · aid ≡ 1 mod ϕ(N ). In order to break soundness, given(N, e, y), the adversary should produce a valid aid′ . However, by uniformity,
Pr[aid′ = aid] ≤ negl(λ). Moreover, as we bound the adversary’s run time by
2λ/c , it cannot invert (N, e, y) directly.
Time-hardness: Both hardness definitions enable the adversary to makeat most q queries to the hard function evaluation oracle. This approach captures the pre-processing procedure of the adversary learning polynomial many(aux, aid) pairs from previous evaluations. In order to break time-hardness,
the adversary must produce a valid aid′ given a freshly generated aux∗ . As
shown above, the uniformity of auxiliary ensures that aid′ being valid is negligible of λ. Moreover, by Lemma 1, the time-hardness of the RSW time-lock
puzzle ensures that the probability of the adversary obtaining a valid solution
with less than δ(u)1−ϵ is negligible of λ.
Difficulty: From soundness and time-hardness, we cannot directly yield
difficulty. This is because aux may leak information of aid, i.e., accelerating
the evaluation of the hard function. Hence, following [10], we consider theunpredictability (min-entropy) of the RSW time-lock puzzle, which guarantees that no adversary can guess any bits in aid from aux without performing
enough evaluation, i.e., less than δ(u)1−ϵ (captured by hardness). As soundness already shows that no adversary can break the TG-PoW task by brute
force, we consider a reduction from difficulty to time-hardness with the following chain of games:
1. Game 0: The original difficulty game (Definition 10). The adversary
is given (task∗ , aux∗ ) ← tdTaskGen(·) with the corresponding pp as the
inputs for its EvalSolve algorithm;
2. Game 1: We replace the challenge task task∗ with an arbitrary task
task;
3. Game 2: The original hardness game (Definition 8). The adversary is
only given aux∗ .
Since reduction loss between each game is negligible of λ, difficulty holds aslong as hardness holds.

23

3.5

Discussion

This chapter presents a PoW scheme under the assumption that task generator is trustworthy. Such an assumption will significantly prevent ourconstruction from being adopted in decentralized environments as the hashbased PoW. Interestingly, this problem also burdens the existing deep learningbased PoUW schemes, hence, being a part of our motivation for the next
result presented in Chapter 4. However, unlike our next result successfully
overcomes this drawback, we argue that until today, it is not easy to createa distributed task generation protocol for our TG-PoW constructions. One
reason is that there is no simple distributed generation protocol for the RSA
problem.
Recall that our initial purpose is to investigate the original use case of
PoW schemes, i.e., a resource-demanding computation mechanism with public and efficient verification. We argue that our TG-PoW constructions(generic and concrete) satisfy this goal. Moreover, like the timed-release
symmetric key encryption scheme proposed in [48] using the RSW time-lock
puzzle, we observe that our generic construction is easy to transform into atimed-release public key encryption scheme under slight modifications.

24

Chapter 4
Blockchain from Deep Learning
Tasks
The starting point of this chapter [53] lies in an observation: Despite thepotential applications, research of deep learning-based proof-of-useful-work(PoUW) severely lacks formality in syntax and security analysis. Our result overcomes these problems by proposing a generic and two concrete
blockchain protocols based on a novel distributed proof-of-deep-learning (DPoDL) scheme. Moreover, our protocols can be proven secure under robust
ledger properties (Definition 3 and 4, which further yields persistence andliveness, i.e., the standard notion of consensus protocols.

4.1

Overview

Recently, Chenli et al. [17] propose a PoUW scheme that utilizes the training
process of deep learning tasks as useful work. To the best of our knowledge,
there are only a handful of papers targeting the same problem [5,16,17,38–40].
We show a brief analysis to them in the following.

4.1.1

Review of Existing Works

These projects all involve interactions between task publishers who oversee
the publication of deep learning tasks and miners who aim to solve thesetasks. In most cases, task publishers are restricted from participating as
miners due to limited computational power or security concern. An exception to this is Proof-of-Learning (PoLe) [38], which avoids this impracticallimitation by introducing secure mapping layers during model training. However, this approach hinders collaboration among miners, which goes against
25

our objective. A typical deep learning task comprises several components: adescription of the task, a training dataset, a potential test dataset, and accuracy target thresholds. In Proof-of-Deep-Learning (PoDL) [17], Li et al.’s
work [39], and PoLe [38], miners are required to train a model on the training dataset, and the model is verified according to the test dataset and test
accuracy. This approach relies on a strong synchronous network assumption,
where the task publisher needs to release the test dataset only after miners
have finished training their models. Without this synchronicity, an adversary can train their model directly using the test dataset, undermining theprocess.
DLchain [16] overcomes the strong synchronous assumption by removing
the test dataset-based verification. Instead, it focuses on improving training
accuracy. In order to verify a trained model efficiently, DLchain utilizes
a merkle-tree-based verification [18] to check training history. Moreover,DLchain considers a similar goal to distribute PoDL, i.e., achieving better
accuracy distributively. They partially fulfill the goal with priorly determined“short-term targets” which are accuracy targets below the threshold. Miners
can generate blocks once their models surpass a short-term accuracy target.
However, considering only training accuracy may result in overfitting, anddetermined short-term targets can affect blockchain growth rate, which may
weaken the security of the protocol [26].
CoinAI [5] is a descriptive work that proposes an outline for designing a
deep learning-based PoUW and proof-of-storage scheme. The authors propose a “hash-to-architecture” mapping based on format context-free grammar. It maps a hash value to an initial deep learning model concerning modelarchitectures, including hyper-parameters and initial learnable-parameters.
The hash-to-architecture technique is vital for security since it prevents miners from grinding initial parameters. However, the security impacts are notclarified due to the lack of formality in [5]. Instead of proposing a PoUWbased blockchain protocol, Lihu et al. [16] aim at taking blockchain’s security to enhance artificial intelligence systems. However, the protocol requires
a dedicated blockchain structure and suffers from complicated system design. For example, participants must select their role before execution, and aunique type of participant called the supervisor needs to monitor all message
history during the execution. Thus, their work cannot be integrated into any
current blockchain-based protocols.
To sum up, none of these works can serve as a fully distributive deep learning task solver, which is more desirable in distributed environments. Anothercrucial problem is the lack of proper security analysis of the blockchain protocol. For example, only DLchain [16] provides security proof against doublespending attacks. However, a secure blockchain protocol should satisfy robust26ledger properties, i.e., the chain growth, chain quality, and common prefix.
Therefore, our motivation for this chapter is to overcome the problems inthe deep learning-based PoUW schemes mentioned above, i.e., (1) to remove
strong or impractical assumptions; (2) to distribute the computation of deeplearning-based PoUW; (3) to provide concrete and thorough security analysis for blockchain protocols based on our extended scheme. Next, we further
detail our result’s significance.

4.1.2

Our Approach and Contributions

This chapter proposes a distributed proof-of-deep-learning (D-PoDL) schemeby extending deep learning-based PoUW schemes so that provers can work
collaboratively on given tasks. Note that the term “distributed” in D-PoDL
differs from distributed deep learning, i.e., we do not require provers to perform a single training course together but let them train atop publishedpre-trained models.
Intuitively, D-PoDL provers train a model from a given deep learning
task as their useful work. We propose a “hash-training-hash” structure toachieve adjustable difficulty while preventing provers from cherry-picking
initial parameters (grinding attack) and pre-computing task instances (precomputation resilience). As a result, the provers output a trained model withthe corresponding accuracy and step number for D-PoDL verifiers to check.
Another novelty of our scheme lies in how we handle intermediate models.
Throughout the chapter, an intermediate model, also called a pre-trainedmodel, is a model “somewhat” trained yet failing to meet a given accuracy
or security level. Instead of discarding such a model, we propose “modelreferencing” that enables any prover to reference the pre-trained model.
Hence, provers can start their training process atop the referenced model.
Moreover, a referenced model will be rewarded so that even if the prover
fails to meet the goals, it is incentivized to do more training iterations. We
emphasize that this approach forms the distributed training process amongprovers, and such a design is never discussed in any previous work.
The second contribution is that we build a generic blockchain protocol
based on our proposed D-PoDL scheme. We clarify the roles of participants:
task publishers, miners, and external storage providers. Instead of assuming
task publishers’ inability to train models properly, we enable them to perform
as miners while preventing them from pre-computing deep learning tasks withthe hash-training-hash structure. Only Pole [38] shares the same property
by embedding secure mapping layers into its training algorithm. Moreover,
we make use of both training and test datasets. Concretely, miners (DPoDL provers) extend the blockchain with models that have better training27

accuracy. In order to mitigate the overfitting problem while avoiding thestrong synchronous network setting, we require miners to work on each deeplearning task for multiple time slots. Hence, task publishers can evaluate
the produced models with test dataset and select according to test accuracy.
Since the training process is publicly verifiable, task publishers cannot takeadvantage by training directly on the test dataset. We will also discuss model
verification and storage issues in Section 4.2.3 and Section 4.3.1.
Furthermore, the generic D-PoDL-based blockchain protocol is capableof two different chain selection rules: i.e., the conventional “longest-chainrule” [26] and the “weight-based” framework [27, 33]. The former requires
honest miners to choose the longest branch as their chain whenever a fork
occurs. In contrast, the weight-based framework assigns blocks with weights
according to their quality. Hence, honest miners choose the branch withhigher accumulated weight as their chain. Although the longest-chain rulecan be considered a special case of the weight-based framework, we separate
them into two concrete protocols and prove the robust ledger properties foreach. Finally, we implement our D-PoDL scheme and compare it to existing
schemes.
Table 4.1 compares our result and related works. Note that we omit
CoinAI [5] due to its informality and Lihu et al.’s work [40] due to theirdifferent research focus. We also include a recent result on stochastic local search-based PoUW [23]. The difference between our result and the
PoUW [23] is that we leverage deep learning characteristics, e.g., verifiable
training steps and test datasets, and derive a simple yet versatile protocol(i.e., proven secure under different chain selection rules).
Table 4.1: Comparison with Previous Works
Network
Publisher
Synchronicity As Miner
Chenli et al. [17]Test accuracy
StrongX
Lan et al. [38]Test accuracy
Strong✓1
Li et al. [39]Training accuracy
BoundedX
Chenli et al. [16] Training accuracy
BoundedX
Fitzi et al. [23]—4Bounded✓Our result
Training and test
Bounded✓Protocols

Work Evaluation

Distributed
Task Solver
X
X
X
△2
✓
✓

FormalSecurity
X
X
X
△3
✓5
✓6

Notes: (1) By secure mapping layers; (2) By pre-determined short-term targets; (3)Against double-spending attack; (4) Stochastic local search; (5) Under the longest-chain
rule [26]; (6) Against robust ledger properties under the longest-chain rule [26] and theweight-based framework [27, 33].

28

4.1.3

Final Preparations

We finalize our overview by presenting our modification to the hash-toarchitecture mapping mechanism [5] and the concrete execution setting of
the blockchain protocol.
Hash-to-architecture mapping. The hash-to-architecture mapping mechanism from [5] is based on the formal context-free grammar and used toestablish a surjective function between a hash value and a proper deep learning architecture setup. Denote the original hash-to-architecture mappingwith HtoA∗ , i.e., given a hash value h, HtoA∗ (h) = (A(hpp), initLP) whereA(hpp) is the architecture A concerning hyper-parameters hpp, and initLP denotes the initial learnable parameters. Our modification, denoted by HtoA,
is to generate an additional random value from the hash, i.e., given a hashvalue h = h1 ||h2 and a hash function Hash : {0, 1}∗ → {0, 1}λ , we extractr = Hash(h2 ) and run HtoA∗ (h1 ) = (A(hpp), initLP) so that the outputs ofHtoA(h) is (A(hpp), initLP, r).
Concrete execution settings. We present our D-PoDL-based blockchain
protocol settings as follows.
• Time and network: We assume the protocol execution proceeds inrounds, which corresponds to the smallest unit of time of interest. The
network is synchronous with a known bounded delay δ time on thedelivery time, i.e., any message sent by an honest node in round r is
guaranteed to arrive at all honest nodes until round r + δ;
• Corruptions: We allow the adversary to corrupt up to β < 21 fraction ofnodes before each round, i.e., a corrupted node is under the adversary’s
complete control from the round. We also assume the adversary is rushing, i.e., it receives honest users’ messages first and decides the orderof message delivery or whether to inject messages for each recipient.

4.2

The D-PoDL Scheme

As an extension to deep learning-based PoUW schemes, our D-PoDL scheme
provides an interface for its provers to solve a deep learning task together.
Like PoUW, a D-PoDL scheme involves two types of participants: provers
and verifiers. On a given deep learning task, a prover intends to output
a trained model, and claims the corresponding training accuracy and step
number. Whereas, a verifier checks if the model matches the prover’s claims
29and responds accordingly. This section presents the D-PoDL scheme in termsof requirements and syntax. We focus on a setting where provers work on
a priorly given deep learning task with a designed target threshold. We
clarify that the scheme focuses on solving the task and verifying the model.
Discussions about task selection, block generation, and blockchain dynamics
can be found in the protocol description in later sections, i.e., Section 4.3
and Section 4.4.
Additional requirements for D-PoDL. A D-PoDL scheme should satisfy the requirements given in Section 2.2.1 and follow the same security requirements [23] as the PoUW, i.e., no-grinding, pre-computation resilience,
and adjustable difficulty. Here, we list the informal requirements as follows.
• (1a) No-grinding: The adversary cannot cherry-pick hyper-parameters
to gain training advantages, i.e., less training steps with higher accuracy;• (1b) Pre-computation resilience: The adversary cannot manufacture
problem instances to train the model faster;• (1c) Adjustable difficulty: The block difficulty (measured by training
accuracy) can be adjusted to the computing power of the network;• (2a) Efficient verification: The running time of the verification algorithm should be at most poly-logarithm of provers’ training time;• (2b) Measurable usefulness: The usefulness of a training process canbe quantified and compared to each other.

4.2.1

Design Overview

Along with the two processes in a D-PoDL scheme, i.e., solving a deep learning task and verifying the correctness of the solution, we propose a novel“hash-training-hash” structure for the solving process and utilize a widelyused merkle-tree-based verification procedure [18] as a black-box for the verification process. Additionally, we propose a weighting algorithm to evaluate
a weight function that quantifies a solution’s usefulness. We describe the“hash-training-hash” structure briefly in this section. More details of ourdesign choices can be found after the formal definition.
Intuitively, on a given deep learning task, we enable provers to initialize its solving algorithm with either a fresh or a pre-trained model fromany prover, i.e., for “model-referencing”. The first hash requires provers to30

perform a proof-of-work (PoW) with threshold T1 , i.e., a prover needs tofind a nonce such that the hash value of the previous block, potentially a
pre-trained model and the nonce is less than T1 . If the hash value passes
the PoW check (less than T1 ), the prover can map the hash value to an architecture with respect to hyper-parameters, (initial) learnable-parameters
and a random seed with our modified hash-to-architecture algorithm. As
introduced in Section 4.1.3, the architecture (with hyper-parameters) andlearnable-parameters determine a deep learning model. The prover trains themodel by updating learnable-parameters iteratively. The post-hash checks
the output model against threshold T2 to decide if the models are eligible forpublishing. If the post-hash fails, the prover can return to the pre-hash or
training process. The prover must perform more training iterations in bothcases to generate a valid model.

4.2.2

Formal Syntax and Construction

A D-PoDL scheme involves a tuple of algorithms (Setup, Solve, Verify, Weight).
Setup extracts a training dataset and a designed target threshold from a
deep learning task. Solve consists of three sub-algorithms PreHash, Train,
and PostHash. In general, PreHash determines the initial model, including
its architecture, hyper-parameters, learnable-parameters, and a random seed.
Train casts the training process and outputs a model with the corresponding accuracy and step number. Note that we do NOT restrict the training
algorithm to provide generality for our design. Instead, as we will show in
Section 4.4.1, we model it with an oracle due to its stochastic nature andmodel provers’ computing power by their capability of oracle queries. Next,
due to security concerns, PostHash returns a bit according to a hash proof.
Verify verifies the trained model’s validity concerning accuracy. Weight isavailable to both provers and verifiers, and it evaluates a weight function
w : acc × Tacc → R, which maps the model’s accuracy and a priorly decided target threshold to a real value. We present the formal syntax andconstruction of the D-PoDL scheme as follows.
Construction 6 (D-PoDL Scheme) Given the hash-to-architecture algorithm HtoA(·) from Section 4.1.3 and the weight function w : acc × Tacc → R,
the tuple algorithm of a D-PoDL scheme (Setup, Solve, Verify, Weight) works
as follows:• Setup(1λ , task) takes as input the security parameter λ and the description of a deep learning task task from the task publisher. Setup extracts
the public parameter pp and a pair of threshold (T1 , T2 ) for security concerns from the system. It parses the task with a training dataset D and31

a target threshold Tacc . Setup outputs (pp, T1 , T2 , D, Tacc ). We omit pp
later for simplicity;• Solve((T1 , prevBK, refM), (D, Tacc ), T2 ). We divide Solve into three algorithms: (PreHash, Train, PostHash).
– PreHash(T1 , prevBK, refM) takes as input T1 , a previous block prevBK
and potentially a pre-trained model refM. It samples nonce suchthat Hash(prevBK, refM, nonce) = h1 ≤ T1 . If refM =⊥, PreHash
runs HtoA(h1 ) = (A(hpp), lp, r) where A(hpp) denotes the architecture, lp is the learnable-parameters, and r is the random seed. It
sets initM = (A(hpp), lp); Otherwise, It parses refM = (A(hppref ), lpref )and sets initM ∈ {refM, (A(hpp), lp)}. Then, PreHash returns (nonce,
initM, r);– Train(D, Tacc , initM, r) takes as input the training dataset D, a target threshold Tacc , a initial model initM and a random seed r.
It parses initM = (A(hpp), lp) and trains the model by updating
learnable-parameters iteratively. Train returns M = (A(hpp), lp∗ ),the corresponding training accuracy acc ∈ [0, 1], step number S∆
and a list of checkpoints CPs = {(Mi , acci , Si )} where each entry
denotes an intermediate result of the training process;– PostHash(T2 , M, acc, S) takes as input T2 and a model M withthe corresponding accuracy acc and step number S. It computes
Hash(M, acc, S) = h2 . If h2 ≤ T2 , PostHash returns 1; Otherwise,
it returns 0.
Finally, Solve outputs ((refM, nonce, initM, r), (M, acc, S), b) where b ∈{0, 1};• Verify((T1 , prevBK, refM, nonce, initM, r), (D, Tacc , M, acc, S, CPs), (T2 , b))checks:– If Hash(prevBK, refM, nonce) = h1 ≤ T1 and if initM is derived
correctly from refM;– If M is trained correctly from initM with Train according to (S, CPs)and if the corresponding accuracy acc′ = acc;
– Compute PostHash(T2 , M, acc, S) = b′ and check if b′ = b.
If the situations above are satisfied, Verify outputs 1; Otherwise, it outputs 0.
• Weight(acc, Tacc ) evaluates the weight function w and outputs w ∈ R.
32

4.2.3

Design Choices Explanation

Here, we explain our construction choices with respect to the requirements.
Setting up initial models with pre-hash. There are countless different
architectures in deep learning, each with its characteristics and limitations.
After selecting an appropriate architecture A, provers need to choose hyperparameters and initial learnable-parameters for the model, which may affectthe speed and quality of the training process. Usually, hyper-parameters are
not learnable, so provers must go through random sampling before obtaining
a good set of hyper-parameters. However, we may open a gate for grinding
attacks (Requirement 1a) if we offer provers the ability to choose hyperparameters and initial learnable-parameters. An adversary may outperform
honest users’ training speed and quality by cherry-picking.
In order to mitigate this problem, we adopt the same approach as in
Ofelimos [23]. Concretely, we rely on a PoW scheme with threshold T1 , which
requires provers to sample a nonce nonce randomly and compute the hash of
the previous block (prevBK), potentially a pre-trained model refM with thenonce such that Hash(prevBK, refM, nonce) = h1 ≤ T1 . The hash function’s
uniformity prevents provers from grinding hyper-parameters and learnableparameters. Note that our T1 should not be as hard as a stand-alone PoW,
e.g., the one in the Bitcoin system, because we intend to encourage provers
to train models instead of solving PoW. Finally, if refM is empty, the proverneeds to generate an initial model with HtoA(h1 ) = (A(hpp), lp, r) such that
initM = (A(hpp), lp); Otherwise, the prover can either refer to the pre-trainedmodel refM = (A(hppref ), lpref ) or use the freshly generated hyper-parameters
and the pre-trained learnable-parameters (A(hpp), lpref ) as its initial model.
In this case, the pre-hash enforces provers to establish links from their model
to previous blocks and the referenced models. Such links are crucial to thesecurity of model-referencing.
Model-referencing and pre-computation resilience. An initial model
can be sampled from HtoA or from a pre-trained model refM. The purposeof taking as input a pre-trained model is to enable provers to work atop any
valid but not-good-enough model. Hence, we prevent their computing powerfrom being wasted and form a distributed solver for given deep learning tasks.
However, starting from a pre-trained model can shorten the prover’s training
iteration because these models may be only a few steps from reaching theaccuracy target threshold. For example, an adversary may steal an honest
prover’s outputs (M0 , acc0 , S0 ) and produce a new model MA with accuracy
accA ≥ Tacc ≥ acc0 and a claimed step number SA . Such an attack vio33

lates pre-computation resilience (Requirement 1b) because the adversary
achieves better accuracy while performing only (SA − S0 ) training steps.
In order to tackle this problem, we design a novel mechanism called“model-referencing”. We require provers to make references if their models
are trained based on another model. Otherwise, their models are regarded
as invalid. The reference is (prevBK, refM, nonce), which can be publicly verified with Hash(prevBK, refM, nonce) ≤ T1 . Hence, model-referencing enables
provers to train each others’ models together for the same goal (surpassing
the target threshold and post-hash check threshold) while preventing themfrom stealing others’ models (by discarding those “use-without-reference”
models). Furthermore, the provers should only reference the latest models,i.e., if two pre-trained models share the same setup, provers should reference
the model with higher accuracy and step number. With this setting, we also
prevent provers from flooding the system with too many pre-trained models. Therefore, the mechanism inherently forms an additional “link” (like thehash link between blocks) that connects models, i.e., a valid block must be
linked to a previous block and a previous model. More details can be foundin Section 4.3.1.
Adjusting computation with post-hash. One argument concerning theadjustable difficulty (Requirement 1c) is that training a model so that its
accuracy surpasses the target threshold Tacc should be harder than finding a
nonce to meet the PoW puzzle with threshold T1 . Otherwise, the computational difficulty is determined by the PoW rather than the training process,which violates the usefulness of our scheme. Hence, we propose a solution
based on [9]’s approach, which requires the provers to perform one “posthash” against a threshold T2 to decide if their models are eligible for publishing. If a model fails the post-hash, the prover must revert to the pre-hashor training process. The threshold T2 guarantees the overall security andusefulness level for our scheme, e.g., to preserve the 10 minutes interval forblock generation while enforcing provers’ computation focus on model training instead of PoW. We will show the impact of the post-hash algorithm
during our implementation of the D-PoDL scheme in Section 4.5.
Model verification. In order to verify the outputs of a prover, a verifier
needs to check three conditions: (1) If the nonce satisfies the PoW checkwith threshold T1 ; (2) If the model has the claimed accuracy; (3) If the posthash outputs a correct bit. In this section, we focus on verifying the modeland its accuracy. A naive approach is to check the prover’s model with thegiven training dataset. However, it takes as many iterations as the training34

algorithm, which violates the efficiency requirement (Requirement 2a).
We solve this problem by adopting the widely used merkle-tree-based
verification [18] as a black box. This approach is also mentioned in the previous work [16]. Namely, provers are required to include several intermediate
results as checkpoints into their training outputs and build a merkle-treeaccordingly. Hence, verifiers only need to check the validity of these checkpoints. Given n checkpoints, the time complexity for verifiers can be reducedto O(polylog(n)) at the cost of provers’ space complexity being O(poly(n)).
Moreover, there is a trivial trade-off between the interval of two checkpoints
and the granularity of the check. As pointed out by [16], the interval setting
can be left to users in real-life applications and adjusted according to accuracy thresholds. However, since each checkpoint has the size of a model, we
explain this in Section 4.3.1 with respect to external storage providers.
Measuring usefulness. The D-PoDL scheme focuses on improving themodels’ training accuracy, whereas, the test accuracy is left for the protocol.
Except for the conventional longest-chain-based blockchain protocols [26], we
intend to build our D-PoDL scheme under a weight-based framework by [33].
In such a setting, blocks are assigned with weight, and the chain is selectedbased on the accumulated weight. We argue that the weight-based approachis natural for the D-PoDL scheme because accuracy can be regarded as aquantified measurement for usefulness (Requirement 2b). Moreover, we
can generalize the weight-based approach to arbitrary PoUW schemes aslong as their usefulness is measurable.

4.3

D-PoDL-Based Blockchain Protocols

This section describes the transformation from our D-PoDL scheme to DPoDL-based blockchain protocols. As mentioned in the execution modelfrom Section 4.1.3, our protocol proceeds in rounds. Honest users may sharea slightly different view of the round number. We further divide our protocol
execution into time slots. Each time slot is associated with a deep learningtask, and the time slot ends when a validly generated block is added to theblockchain. Thus, a time slot may include multiple rounds. Considering
the workflow within a time slot, we propose a generic D-PoDL blockchain
protocol design as in Figure 4.1. Then, two concrete protocols are derived
from the generic design by instantiating the chain selection rule with thelongest-chain rule [26] and the weight-based framework [33]. Finally, we
discuss the incentive model of our protocols.

35

nonceprevBK

Pre_Hash

False

h1

(initM;r)=HtoA(h1) or refM

h1<T1

True

Train(initM,D;r)(M,acc,S)

Post_Hash(M,acc,S,b)

refM
False

taski

b=1

True and acc>=Tacc

BK_Candidate
with model M*

True and acc<Tacc
False
Model_TX mtx
with pre-trained M
Publisher
Network

task1
task2
...
taskn

True
(i=i+1)

M* test accuracy

UpdatedBlockchain

Chain Selection

Figure 4.1: Design of our Generic D-PoDL Blockchain Protocol

4.3.1

Generic Protocol Workflow

The generic blockchain protocol involves three types of participants: task
publishers, miners, and external storage providers. Task publishers handle
deep learning tasks. Each task is associated with a dataset and desired
accuracy thresholds. Task publishers first split the dataset into a training
dataset and a test dataset. They publish the task description, the training dataset, and the corresponding desired training accuracy as the target
threshold. Miners perform the protocol by generating and verifying blocks
according to the D-PoDL scheme’s instructions. Concerning the size of deeplearning models and checkpoints (which are the same size as models), we
employ the approach from [16] to prevent storage overhead, i.e., embedding
only a downloadable link within the block and relying on external storage tostore the whole model and checkpoints.
Task publication. We start our generic D-PoDL blockchain protocol fromthe task publication mechanism. In order to keep the task publication as
generic as possible, we consider a situation in which these publishers form a
network to publish and decide the order of tasks. They aim to organize a
distributed solver for deep learning tasks and can be benefited from receiving
the solutions. The only requirement is that the outputs of the publisher
network should be an ordered list of deep learning tasks. We denote theoutput as {taski }i∈[n] where taski spans over a period of ℓi time slots in
Ti = {ti,j }j∈[ℓi ] .
Note that we do NOT separate task publishers from miners, i.e., a task
publisher can participate in the protocol as a miner and gain mining re-36

wards. We argue that the task publisher cannot pre-compute the task to
gain advantages over regular miners due to the pre-hash algorithm and themodel-referencing mechanism. Without loss generality, let the current timeslot be tp,q , we consider an adversarial publisher who intends to pre-computedeep learning task taski where i > p, q ∈ [ℓp ]. Since i > p, without pre-trainedmodels, the publisher has to train an initial model generated from HtoA, i.e.,
to find nonce such that Hash(prevBK, nonce) = h1 ≤ T1 where prevBK associates with slot ti−1,ℓi−1 −1 ∈ Ti−1 and compute initM from HtoA(h1 ). To findsuch a nonce requires the publisher to either predict the block in the future
or find a collision in the hash function. Since the probabilities of both cases
are negligible, the publisher cannot produce a trained or pre-trained model
to pass the D-PoDL scheme’s verification by pre-computing taskk .
Execution of D-PoDL scheme. Now, we consider a deep learning task
taski given to miners in time slot ti,j where j ∈ [ℓi ]. Each miner runs as
a prover of the D-PoDL scheme. The Setup algorithm first extracts public parameters, a training dataset, and thresholds (T1 , T2 , Tacc ). The minerthen finds a nonce and initializes initM with PreHash; It runs the training
course on the initial model with the randomness r to obtain a model M, thecorresponding accuracy acc and step number S; PostHash tests the modelaccording to T2 and outputs a bit b. The miner outputs a tuple, including
potentially a pre-trained model as the reference, a nonce, an initial model, arandom training seed, a trained model with the corresponding accuracy andstep number, and a post-hash check bit.
According to the post-hash check, the miner decides if its model is eligible for publishing. Moreover, for generality, we introduce a relation between
the model accuracy and the target threshold as R(acc, Tacc ), which will be
instantiated in concrete protocols. Hence, when b = 1 ∧ R(acc, Tacc ) = 1, theminer collects transactions from the mempool as in conventional blockchain
protocols and generates a block candidate embedding the obtained model M;
Otherwise, the miner generates a special model-transaction mtx for modelreferencing, which contains the outputs of the Solve algorithm, i.e., mtx =(prevBK, (refM, nonce, initM, r), (D, Tacc , M, acc, S, CPs), 1). mtx is publishedinto the mempool as ordinary transactions. Any miner can reference themodel M in the model-transaction mtx by including mtx in the miner’s
newly found block or model-transaction. That is, the miner takes as input refM′ = M for its Solve algorithm. Note that different miners can referto the same model-transaction. We do not count this as “double-spending”
since no ordinary (money-used) transaction is involved. Newly trained models still need to compete for acceptance. Moreover, miners can reference37model-transactions recursively, i.e., generating a model-transaction mtx′ withhigher accuracy from mtx is acceptable. The only restriction here is that miners must reference the latest model-transaction, which embeds a pre-trainedmodel with the highest accuracy observed so far. This prevents the adversary
from releasing a large amount of model-transaction to DoS attack [44] the
network.
Cross time slot attacks and restrictions on step number. We leave
block selection (with respect to forks) to concrete protocols in Section 4.3.2.
Here, we consider the whole period (a span of time slots) associated with adeep learning task. Once the blockchain gets updated, miners proceed to thenext time slot. A task can span over multiple time slots so that the publisher
network can check each selected model with the corresponding test dataset.
This approach is to mitigate the trend toward overfitting models since miners
are given only training datasets to overcome the strong synchronous network
assumption.
However, this approach allows adversaries to reference models generated
in different time slots from the block they extend. Given a fragment of theblockchain that associates with a deep learning task, we illustrate two attack
strategies in Figure 4.2a and 4.2b. Note that the adversary can also reference
models embedded in blocks. We use model-transactions here for generality.
Model-referencing
Model-referencing
mtx
BKi

BKi+1

Extending
Extending

...

BKi+j

BKadv

mtx

BKadv
BKi
BKi+j+1

BKi+1

...

BKi+j

BKi+j+1(b) The adversary intends to extend
block bki by referencing a modeltransaction mtx that links to block
bki+j .

(a) The adversary intends to extend
block bki+j by referencing an mtx thatlinks to block bki .

Figure 4.2: Intuition of Cross Time Slot Attacks
The first attack enables the adversary to extend the blockchain with fewer
training steps while not violating model-referencing requirements. In thesecond attack, the adversary can produce a model with higher accuracy orweight using new information, e.g., the model in mtx of Figure 4.2b. This attack may subvert blockchain history if the adversary produces enough blocks
to compete with the selected chain.
In order to tackle these problems, we restrict the training step number
in published blocks. We introduce a lower bound of acceptable step number
as smin to control the selected blocks’ step number during the period of a38

given task task. Denote the period with T = {ti }i∈[ℓ] , and for each i ∈[ℓ], we denote the selected model (in a block on the chain) with Mi ∈ bki
and the model’s corresponding step number with Si . Now, consider a blockcandidate bk embedding Mbk trying to extend bkn with n ∈ [ℓ − 1]. Let
M = (M′j )j∈[k] be Mbk ’s recursively referenced model list. Each of thesemodels is either embedded in a block or a model transaction that extends
some blocks on the blockchain. Without loss of generality, we assume thefirst block being extended by one of these models in the period to be bkm
where m ∈ [ℓ − 1], m ≤ n. The restriction on Mbk ’s step number Sbk is:
k−1
X

Sj′ + Sbk ≥

j=0

n−1
X

Si + smin.

(4.1)

i=m

Intuitively, the restriction requires that a newly generated block and its
referred models have no less training steps than the steps on the main
blockchain. It is reasonable in the sense that we require not only the accuracy of models/blocks, but also miners donating enough computing power(training steps). Moreover, our D-PoDL scheme enables us to leverage steps
in model verification. The goal is to stabilize the block generation rate, andwe will discuss this later in Section 4.4.2. Finally, miners repeat the above
process when the publisher network proceeds to a new task.

4.3.2

Concrete Protocols

In this section, we instantiate the chain selection rule with the longest-chain
rule from [26] and the weight-based framework from [33].
Longest-chain-based D-PoDL blockchain. First, in the longest-chainbased protocol, we clarify the relation introduced above as: R(acc, Tacc ) = 1
if acc ≥ Tacc . Hence, a model is eligible to be published as a block if b =1 ∧ acc ≥ Tacc . Otherwise, i.e., acc < Tacc , the model can be embedded ina model-transaction mtx and published to the mempool; if b = 0, the miner
must continue training the model or resample the nonce for another initialmodel to be trained. By the longest-chain rule, miners of each time slot add
blocks to the end of the longest blockchain they have observed and broadcast
the chain to the network. Later, we will show that forks of the same length
as the main chain can exist only with negligible probability by proving therobust ledger properties [26] for our longest-chain-based protocol.
Weighted-based D-PoDL blockchain. In the weight-based protocol,
R(acc, Tacc ) = 1 for any pair of (acc, Tacc ). The situation indicates that a39miner can generate a block even if its deep learning model fails to surpass
the target threshold. However, the number of blocks produced in a time slot
can be overwhelming without proper filtering. Therefore, Kamp et al. [33]
introduce a weight function to quantify the quality of blocks so that miners only choose the blockchain with the highest (accumulated) weight. Our
weight function evaluates the embedded model according to (acc, Tacc ) with
the Weight algorithm. Instead of showing specific constructions, we will introduce two crucial properties for proving the security of the weight-based
D-PoDL blockchain in the next section. With these properties, we showthat forks with comparable weights as the main chain can only exist withnegligible probability by proving the weight-based variant of robust ledger
properties [33] for our weight-based protocol.
Discussion: Incentive models. The incentive model is crucial to a practical protocol. We aim to reward miners according to their useful computation, i.e., training iterations. Moreover, our protocol differs from previous works in that miners can reference model-transactions to generate another model-transaction, or a block, without training models from the sketch.
Models in model-transactions may have inferior accuracy. However, they are
crucial in forming the distributed deep learning task solver. Hence, in order to incentivize miners to produce models, we reward not only the miners
who produce selected blocks but also the model-transactions referenced by
selected blocks. The rewards are given according to the model accuracy
and the step number. For example, let M be the selected model, which istrained for S steps. Furthermore, let its recursively referenced models set
be M = {Mj }j∈[k] , andP each j ∈ [k], Mj is trained for Sj steps. Hence,
M’s miner receives S/(
Sj + S) fraction of the total rewards, and each Mj ’sPminer receives Sj /( Sj + S) of the total rewards. Finally, we want to clarify
that incentive models may affect the assumptions on honest miners’ fraction,
which will further affect chain growth for robust ledgers [3]. However, we
assume honest miners’ fractions directly. Hence, the incentive model in thissection will not change our security proofs.

4.4

Security Analysis

Our security analysis focuses on the period of one single deep learning task
because switching to a new task can be regarded as a mining difficulty
shift in the PoW-based protocols. However, extending the result to thewhole blockchain is easy if we assume the difficulty, represented by the accuracy target threshold, is stable across different tasks. To clarify, the terms
40

“model-transaction” and “block” refer to the model embedded in the modeltransaction or block.
Robust ledger properties. In this section, we focus on proving the robust
ledger properties, i.e., the chain growth, chain quality, and common prefix,
for our concrete protocols. Recall the definitions from Chapter 2. We unify
them as follows.
Definition 13 ((Weight-Based) Robust Ledger Properties) The three
aspects are defined as follows.
• Chain growth: For any honest miner with chain chain at a round, thechain growth with parameter τ ∈ (0, 1] and s ∈ N states that for any
portion of chain spanning s consecutive rounds, the number of blocks
appearing in this portion is at least τ · s (the accumulated weights
W(chain2 ) ≥ W(chain1 ) + τ s);• Existential chain quality: For any honest miner with chain chain at around, the existential chain quality with parameter s ∈ N states thatfor any portion of chain spanning s consecutive rounds, at least one
honestly-generated block appears in this portion (the fraction of honest
blocks’ weights is at least µ;);• Common prefix: For any two honest miners with chains chain1 , chain2
at round r1 , r2 respectively, where r1 ≤ r2 , the common prefix withparameter s ∈ N indicates that chain1 should be a prefix of chain2 after
removing the last s blocks.

4.4.1

The Training Oracle

Our first step models the combination of training and post-hash process witha training oracle. Following [33]’s approach, we assume protocol participants
can make at most one query to the training oracle in each round. This
assumption is reasonable because a round is the smallest unit of time ofinterest in our protocol and corresponds to the time for evaluating the hashfunction over one training iteration on one miner’s computing device. Fora real-world miner with the computing power of more than one device, we
model it as a collection of “one-query-per-round” participants.
In each round, a miner queries the oracle OTrain with (Mpre , accpre , S; r)where Mpre denotes the pre-query model, accpre and S denotes the corresponding training accuracy and step number, and r denotes the random

41

seed for training. The oracle OTrain first verifies the queried model and returns ⊥ if the model is invalid. Otherwise, OTrain performs one training
iteration with r to obtain (Mafter , accafter , S+1) where Mafter and accafter denote the model and training accuracy after query, respectively. It samples
a random value h2 ← {0, 1}λ uniformly, where λ is the security parameter that indicates the length of the hash function output. OTrain returns(Mafter , accafter , S+1, h2 ). Moreover, regarding queries with different random
seeds (r) as different queries, OTrain keeps a list of performed queries andreplies to former queries according to the list.
The uniqueness of our model is that OTrain performs one training iteration
before sampling the random value. A query is said to be successful only if theoutput model satisfies: h2 ≤ T2 ∧ R(accafter , Tacc ) = 1. Since h2 ’s distribution
is defined to be uniform, we now consider the distribution of the output
accuracy accafter . Note that training accuracy usually grows faster before
achieving a certain value. Like in [16], we name this value difficulty threshold,denoted by Dacc . Our model focuses on the training process after such athreshold. The reason is that, as explained in [7], increasing the training
accuracy requires stochastic/random search after this threshold. Hence, we
assume that if accpre ≥ Dacc , accafter follows an arbitrary distribution D over∆{acc : acc ≥ Dacc } such that f1 = Pr[accafter ≥ Tacc |accpre ≥ Dacc ], e.g.,
1−Tacc. Otherwise, i.e., accpre < Dacc , we assume
when D is uniform, f1 = 1−D
acc
accafter increase be monotonically but unlikely to surpass Tacc , i.e., less thanϵ, negligible of the security parameter λ. Therefore, we argue that the overall
probability is Pr[accafter ≥ Tacc ] ≥ 12 f1 because the number of training steps
before reaching the difficulty threshold is much less than the step number
afterward. The training oracle goes as follows.
Training Oracle OTrain
Let task be a deep learning task with dataset D and accuracy target
threshold Tacc . The oracle OTrain keeps a list L with performed queries.
On a query (Mpre , accpre , S; r) from a miner in a round:• If (Mpre , accpre , S; r) is invalid, i.e., Mpre has unmatched accuracy
or step number, return ⊥;• If (Mpre , accpre , S; r) ∈ L, return the reply entry (Mafter , accafter ,S+1) according to the list L;• Otherwise, run one training step Train(D, Tacc , Mpre , r) → (Mafter ,accafter , S+1) and sample h2 ← {0, 1}λ uniformly at random.

42

Add ((Mpre , accpre , S; r), (Mafter , accafter , S+1, h2 )) to L and return(Mafter , accafter , S+1, h2 ) to the miner.
We assume the distribution of accafter following the distribution D over{acc : acc ≥ Dacc } such that Pr[accafter ≥ Tacc |accpre ≥ Dacc ] = f1 , andPr[accafter ≥ Tacc |accpre < Dacc ] = ϵ where ϵ is negligible of the security
parameter λ.

4.4.2

Proving Ledger Properties

Consider the situation in which a deep learning task taski spans over timeslots Ti = {ti,j }j∈[ℓ] . We omit i in the following for simplicity. The hashfunction in the PreHash algorithm guarantees that a new block is never added
between two existing blocks (insertions), the same block never occurs in two
different positions (copies), and a block never extends a block that will bemined in later time slots (predictions).
The longest-chain-based protocol. A miner who outputs a block inslot tj that meets the post-hash check, target accuracy, and step restriction
has to perform at least Sj training steps, which is equivalent to Sj queries
to OTrain . As miners, honest or adversarial, are bounded by the numberof queries they can make in each round, they cannot generate too many
blocks in any polynomial many consecutive rounds within the period T oftaski . Simultaneously, miners cannot generate too few blocks because theprobability of at least one honest miner outputting a block is lower boundedby the success rate of the oracle.
Like [26], we define typical execution for the situation in which miners
generate not too many nor too few blocks in polynomial many consecutive
rounds of protocol execution. First, we consider three Boolean random variables Xr , Yr , Zrpq . If at round r an honest miner obtains an output fromthe oracle OTrain that satisfies h2 ≤ T2 ∧ R(accafter , Tacc ) = 1, then Xr = 1,otherwise Xr = 0. If at round r exactly one honest miner obtains suchan output, then Yr = 1, otherwise Yr = 0. For the adversary, if at roundr, the p-th corrupted miner’s q-th query to the oracle OTrain obtains suchan output, P
thenPZrpq = 1, otherwise Zrpq = 0. Hence, we define a variable Zr =rounds, we define
P p q Zrpq . For
P a set X of k consecutiveP
X(X ) = r∈X Xr , Y (X ) = r∈X Yr , Z(X ) = r∈X Zr .
Definition 14 ((ϵ, k)-typical execution) Let ϵ ∈ (0, 1) and k ∈ N, an
execution is (ϵ, k)-typical if for any set X of at least k consecutive rounds
43within the period of a deep learning task, the following holds:• (1 − ϵ)E[X(X )] < X(X ) < (1 + ϵ)E[X(X )], (1 − ϵ)E[Y (X )] < Y (X );• Z(X ) < E[S(X )] + ϵE[X(X )].
Theorem 2 Assume the training oracle and at most β < 21 corrupted miners each round, the longest-chain-based D-PoDL blockchain protocol satisfies
the robust ledger properties (Definition 3).
Proof 3 We first prove the following lemma.
2Lemma 3 An execution is (ϵ, k)-typical with probability 1−e−Ω(ϵ kp) where pis the probability of at least one honest miner obtaining a model that satisfies
h2 ≤ T2 ∧ acc ≥ Tacc .

Let accafter be the input accuracy to OTrain and Dacc be the difficulty threshold, according to our oracle description, the probability of the output accuracy
accafter surpassing the target threshold Tacc in a query reply is:
Pr[accafter ≥ Tacc ] = Pr[accafter ≥Tacc ∧ accpre ≥ Dacc ]+ Pr[accafter ≥ Tacc ∧ accpre < Dacc ]≥ Pr[accafter ≥Tacc |accpre ≥ Dacc ] · Pr[accpre ≥ Dacc ]= f1 · Pr[accpre ≥ Dacc ],For a query, we have Pr[accpre ≥ Dacc ] ≥ 1/2, as we assumed training steps
before reaching Dacc , which is less than the step number afterward. Thus, aminer who makes at least one query to OTrain in a round obtains accafter ≥ Tacc
from OTrain with probability at least 12 · f1 .
Let f2 be the probability of at least one honest miner obtaining an h2 fromthe training oracle OTrain that satisfies h2 ≤ T2 in a round. Because the outputof the training algorithm is independent to the hash function, the probabilityof at least one honest miner obtaining a tuple (Mafter , accafter , S+1, h2 ) thatsatisfies h2 ≤ T2 ∧ accafter ≥ Tacc should be at least p ≥ 12 · f1 · f2 (and at mostp ≤ f2 ).
Next, we analyze the probability of execution being typical. Note that thetraining oracle OTrain takes queries with different training random seeds (r)as different queries. Moreover, a hash function, modeled as a random oracle,
generates such random seeds in the pre-hash PreHash algorithm. Hence, theprobability of two honest parties querying OTrain with the same input in polynomial many rounds of execution is negligible of the security parameter λ.
Such property enables us to condition the probability space on the event that44

no two honest parties query OTrain with the same input in a polynomial manyrounds of execution. In this space, the random variables Xr (and similarly
Yr and Zrpq ) are independent Bernoulli trials where each trail is successful
with probability Θ(p) (as analyzed above). Hence, by the Chernoff bound, we
2
prove the probability of an (ϵ, k)-typical execution is 1 − e−Ω(ϵ kp) .
Directly from [26], we have the following lemma that parameterizes thechain growth, existential chain quality, and common prefix in a typical execution.
Lemma 4 In an (ϵ, k)-typical execution, the chain growth property holds forparameter τ = (1 − ϵ)p and s ≥ k, the existential chain quality property holds
for parameter s ≥ 2kp, and the common prefix property hold for parameters ≥ 2kp.
Finally, by Lemma 3, we choose k = Ω(log2 λ) so that an execution fails
to be typical with negligible probability of the security parameter λ. Therefore,
we prove Theorem 2 with the parameters following Lemma 4.
The weight-based protocol. One concern is that selecting models withinferior accuracy may accelerate the block generation rate because training
such models requires fewer steps in each time slot. The block may not beadequately propagated to all honest miners before the next block is generated. To prevent so, we require the weight function to be appropriately
bounded (with isolated-lower-bounds and upper-bounds, definitions can befound in [33]) so that the low block weight indicates low model accuracy
and the low accuracy models are hard to be selected according to the weightfunction. Like the typical execution, we adopt model isolation (Definition 15)
from [33] for the situation in which the round gap between any two models
with sufficient accuracy is longer than the unknown network delay. Under
the properly bounded weight functions, we further argue that our modelreferencing mechanism cannot break model isolation. A miner has to performenough training steps so that the total step number of its model, including all
the referenced models, is no less than the total steps of the selected models(Restriction). Hence, the model-referencing mechanism offers no advantage
to the miner in generating a model faster. Finally, we conclude the following
theorem for the weight-based protocol.
Definition 15 (acc-Isolation) Let M be the model embedded in the block
mined in round r within the period of a deep learning task. M is left-isolated
if M is generated by an honest miner, accM ≥ acc, and there is no block on
the left embedding a model with accuracy higher than acc in rounds [r − ∆, r]45

where ∆ is the unknown network delay. M is isolated if M is generated byan honest miner, accM ≥ acc, and there is no block embedding a model withaccuracy higher than acc in rounds [r − ∆, r + ∆].
Theorem 3 Assume the training oracle and at most β < 12 corrupted miners each round, the weight-based D-PoDL blockchain protocol satisfies theweight-based robust ledger properties (Definition 4) if the weight function isisolated-lower-bounded and upper-bounded.
Proof 4 It has been proven that a secure longest-chain-based blockchain protocol can be transformed into a secure weight-based protocol as long as theweight function is properly bounded [33]. We refer to their results and argue
that our model-referencing mechanism will not break the proof.
First, for chain growth, the restrictions on training step number in Section 4.3.1 enable honest miners to have enough time for block propagation.
Therefore, honest miners will have at least one chain that accumulates theweight from all left-isolated blocks. Assuming the weight function is leftisolated-lower-bounded, the probability of this accumulated weight being inferior to the lower bound is negligible to the security parameter. Next, for chain
quality, the chain growth property guarantees that the chain will accumulate
at least all left-isolated blocks’ weights. Moreover, the adversary cannot generate left-isolated blocks fast enough because it has to perform enough training
steps, and the total weight is upper bounded by the weight function. Finally,
since model-referencing will not change block selection, i.e., honest miners
will only extend chains with sufficient weights by each round, common prefix
preserves regardless of model-referencing.

4.5

Implementation of D-PoDL Scheme

The average time consumption of block generation and the variance in thetime reflect the stability of the protocol, which may affect users’ experience.
Further, this time consumption can be analyzed with the solving time of
the underlying schemes. Therefore, this section shows a toy example for
our D-PoDL scheme implementation. We compare the PoW scheme and theplain deep learning to our D-PoDL scheme with different sets of thresholdparameters (T1 , T2 , Tacc ). We utilize the MNIST dataset to implement deeplearning-based schemes, i.e., plain deep learning and our D-PoDL, and follow
the original split of 60000 images for training and 10000 images for testing.
Results can be found in Table 4.2.
In the PoW implementation, we use a 256-bit hash function, e.g., SHA256, and set the difficulty to be T = 2228 , i.e., to find a nonce with Hash(prevBK,
46

Table 4.2: Experiment Results
Scheme/Algorithm
Average Maximum Minimum Variance224
PoW (2 )433.371242.530.63122336.11
Deep learning (0.97)
81.88
126.61
75.24
109.19240 256
D-PoDL (2 , 2 , 0.97)
94.26
122.3875.23
320.99244 255
D-PoDL (2 , 2 , 0.97) 140.60
195.68115.36648.97On MacBook Pro with 2.3GHz quad-core Intel Core i5 and 8GB of
2133MHz LPDDR3 onboard memory; Time consumption is presented
in seconds and recorded for 20 attempts.
nonce) < T . Hence, the expected hash iteration is 228 . Next, In the plain
deep learning implementation, we set the batch size to 128, the learning rate
to 0.001, and the target threshold to 0.97. Most models reach this threshold in 2 epochs, each including 387 training steps. Finally, in the two DPoDL’s Solve algorithm, we implement with (T1 , T2 , Tacc ) = (2240 , 2256 , 0.97)
and (2244 , 2255 , 0.97). For T2 = 2256 , since the post-hash accepts all models,
we use it to distinguish the impact of the pre-hash algorithm PreHash. Thechange in time comes from two factors: (1) Computation overhead from thehash function; (2) Training speed due to the different hyper-parameters. For
the second D-PoDL implementation, the post-hash check significantly prolongs the average solving time despite the fact that we lower the pre-hashthreshold T1 to 2244 . The result indicates that the post-hash plays an important role in controlling the solution generation speed, which is the overall
difficulty of the scheme.
Concerning variance values, we observe a big gap between deep learningbased schemes and the PoW scheme. The reason is that the stochastic gradient descent algorithm that optimizes the neural network has a more consistent convergence speed. In contrast, a well-behaving hash function in the
PoW scheme should follow the uniform distribution with a high variance.
However, low variance is not always preferable because the algorithm should
involve enough stochasticity to prevent domination, i.e., the miner with themost computing power generates all blocks. By comparing the variance valueof the deep learning-based schemes, we notice that both pre-hash and posthash algorithms involve randomness in the solving time, which can benefit
the fairness among miners.

47

4.6

Discussion

This chapter extends the existing deep learning-based PoUW schemes byremoving impractical assumptions and providing a distributed approach forprovers to collaborate together solving the PoUW. Based on the proposed DPoDL scheme, we construct blockchain protocols and show the protocol canenable its participants to achieve consensus. However, we need to point out
that our proofs are also based on two crucial assumptions: (1) The parameterin the protocol, i.e., (T1 , T2 , Tacc ), are well-chosen so that the rate of block
generation prevents too many forks from being added to the main blockchain;(2) We assume honest majority so that more than half of the participants
follows our protocol instruction. The former highlights the needs of taking
deep consideration in deploying the protocol into practice; whereas, the latter
requires us to reconsider the incentive model (like in Section 4.3.2) and give
better reasons why participants will follow instruction.

48

Chapter 5Consensus from Competitive
PoX
The initial motivation of this chapter [51] is a concrete problem: Can blockchainaided protocols contribute to the development and deployment of “smart
grids”, a novel power grid structure that enables peer-to-peer energy trading (P2PET). We answer this question with a blockchain protocol based ona novel PoW variant from an assignment problem (bid-assignment problem(BAP)) in general double auction systems. Further, we generalize the idea of
the BAP-based PoW alongside the weight-based blockchain framework into
what we call “competitive PoX”. Finally, we give a security analysis for ourblockchain protocol based on the competitive PoX.

5.1

Overview

The shift to renewable energy sources, which are less reliable than traditional
options, urges a significant change in the current power grid structure, i.e.,
moving away from the centralized uni-directional system to decentralized bidirectional smart grids. In a smart grid, individuals known as prosumers
are both producers and consumers of energy. The smart-grid infrastructure
enables its users (prosumers) to trade energy and exchange data, thereby
promoting regional self-sustainability. A control system, i.e., the P2PET
system, is employed to monitor and manage user operations within the smart
grid. Its primary functionality is to securely record the history of energy
trading, allowing users to perform accordingly. Usually, in a decentralized
environment, a public ledger is used to ensure user consensus and to prevent
any manipulation of data by a single entity. As introduced in Chapter 1,
it is a natural choice to utilize a blockchain as the implementation of the49distributed ledger in P2PET systems.
Related works. Numerous studies investigate the application of blockchain
technology in P2PET [1,30,36]. However, these studies are built atop generalpurpose blockchain protocols and rely on smart contract capabilities [41],e.g., as provided in Ethereum [55] and Cardano [24]. Unfortunately, thisapproach has its limitations, as it restricts opportunities for optimizationand often leads to high maintenance fees for users when submitting smart
contract-based transactions to the network [41, 50]. Additionally, most protocols employ the hash-based PoW, which involves computationally intensive
tasks, and hence, being energy intensive. This requirement contradicts theobjectives of enhancing energy trading and reducing overall energy consumption. Needless to say, these repeated hash evaluations have no connection
with the market that may exist on the top of the system. Therefore, we aim
to address these gaps.
We explore the design of a dedicated blockchain protocol for P2PET, departing from the reliance on smart contracts and conventional PoW schemes.
We thoroughly redesign, from the fundamental components, the blockchain
data structure itself. This allows us to leverage the operations within theP2PET system and introduce a new approach called BAP-based PoW (to bedetailed later). Unlike the PoW paradigm, in which much computing (andelectrical) power is wasted in order to pace the block generation as a cornerstone for ensuring a robust ledger, the BAP-based PoW scheme capitalizes
the existing architecture and structure of power distribution to provide aleaner and more effective solution. In summary, our novel design integrates
the underlying network mechanism that ensures the robust ledger with themarket dynamics of the system.

5.1.1

Our Approach and Contributions

Now, we show a brief image of our approach. The first step is to extract
settings and unique operations from the P2PET system.
Abstracted P2PET. In a P2PET system, the control system operates
within a smart grid and facilitates interactions between users and potentially regional power plants within a tight-knit community, e.g., a town. The
smart grid infrastructure provides users with equipment to produce, store,
and transmit energy. Each user is equipped with certified smart metersthat honestly measure energy production and consumption, ensuring tamperproof measurements. Additionally, users have Home Energy Management50

Systems (HEMS) associated with their smart meters, which oversee energy
management processes. Unlike smart meters, HEMS are more sophisticatedand capable of computations but are not assumed to be entirely trustworthy.
Multiple local smart grids can be combined to form larger systems, and thishierarchical structure can be recursively implemented.
This chapter focuses on a typical standalone P2PET system within asmall community, where users and a power plant are interconnected throughbi-directional power lines with a fixed physical topology. Each user has the
freedom to produce or consume energy as needed. However, due to theunpredictable nature of energy production, users may encounter situations
where there is a shortage of energy when they are not producing enough or
an excess of energy when they are producing more than required. In suchcases, the trading capability of the P2PET system becomes crucial, as itallows users to buy or sell energy to meet their needs. Furthermore, thesmart grid infrastructure enables users to store energy. Therefore, users canalso buy energy at low prices for storage and sell it at higher prices for profit.
While the specific purpose of users is not specified, we primarily focus on thebuy/sell operations within the system. In order to support these operations,recall a double-sided auction market in which users buy some product at a
price by issuing a buy bid, and sell some product at a price by issuing a sellbid. We follow the same process of bidding with energy as the product.
Next, we consider the formation of trading agreements from the bids.
Each agreement, later referred to as a transaction, consists of a buy bid anda sell bid that satisfy specific constraints, e.g., the buy bid’s price is higher
than the sell bid’s price. The public ledger of P2PET should record theseproperly formed transactions, allowing users to transmit energy and makepayments accordingly. It may have been noticed that two crucial questions
are not mentioned above: (1) Given a set of bids, how to generate a setof transactions; (2) How to ensure a robust ledger in such a setting. The
following sections thoroughly answer these questions.
It is important to note that our result primarily focuses on the designof the blockchain protocol level rather than the intricacies of the P2PET
system or smart grids. Therefore, aspects such as the dynamics of the energy
trading market or issues related to the physical infrastructure (e.g., energy
transmission loss) are not thoroughly investigated. However, the protocol
proposed is designed to be flexible enough to accommodate such challenges.
P2PET meets blockchain: A brief description. In order to integrate
the bidding operations of P2PET with blockchain protocols, we begin byrefining the blockchain data structure. Specifically, we introduce a bid layer

51

containing information such as the type (buy or sell), quantity, and unit price.
In this context, a transaction is defined as the combination of a buy and asell bid. The block is then defined as a container of bids and transactions,and the blockchain is represented as an ordered linked list of blocks.
Next, we formalize the process of generating transactions using a manyto-many assignment problem, i.e., the Bid Assignment Problem (BAP). The
BAP can be viewed as a special case of the Generalized Multiple-Assignment
Problem (GMAP) [43]. We establish a generic framework for the BAP inwhich a set of bids serves as the input, and an index set of assigned bid
pairs is the output based on a scoring function. Then, by instantiating the
BAP’s outputs with blocks and defining the scoring function’s domain overthe block’s space, we create the instantiation of the BAP referred to as the”BAP for block generation” (bk-BAP). Ultimately, the bk-BAP will serve as
the foundation for our ”proof-of” scheme, the BAP-based PoW scheme.
Before introducing the formal syntax of the BAP-based PoW scheme, we
introduce the concept of a bidpool, which resembles the mempool of transactions in conventional blockchain protocols. Each BAP-based PoW user
(formally called prover) maintains and verifies a bidpool based on their viewof the blockchain. The BAP-based PoW scheme consists of algorithms for (1)sampling a bid set from the bidpool, (2) solving the bk-BAP using the sampled bid set, and (3) evaluating the bk-BAP solution according to the public
scoring function. Here, the scoring function can incorporate specific market
dynamics by assigning different scores to particular transactions. As we aim
to showcase the flexibility of our design and not fully explore the underlying
market, we keep the scoring function as general as possible. When analyzing the computation in BAP-based PoW with respect to the general scoring
function, we employ the universal sampler [9, 32], which follows arbitrary
distributions when sampling blocks and their corresponding scores. Thismodeling approach is similar to how hash computations in PoW blockchain
protocols are represented by the query to a random oracle [26].
The earlier outlined bid-related block design is a key technical innovationin our proposal. To the best of our knowledge, this has not been introduced
before. Additionally, our protocol’s block selection and blockchain dynamics
provide another unique feature. Instead of requiring optimality in each user’s
block generation, i.e., finding the best possible bid match combination, we
encourage users to compete with each other. This competition eventuallyleads to a chain of blocks with the highest overall score. To maintain theblocks visible to users in the protocol (referred to as the local view), we
consider a tree structure where each branch represents a valid chain of blocks.
Branches are assigned scores based on the score of each block in the branch,allowing users to select the branch with the highest score. The security proof52

of our system is intricate and constitutes a significant technical contribution
to this result. In essence, the security is demonstrated by analyzing the local
tree dynamics of honest users. We prove that, given any score distribution(using the universal sampler of [9, 32]), our protocol satisfies robust ledger
properties with overwhelming probability.
To sum up, the contributions are threefold: (1) we abstract the processof generating transactions from bidding with a combinatorial optimization
problem that extends the GMAP [43]; (2) we design a dedicated blockchain
protocol for the P2PET system that can be further extended for general
double-sided auction markets; (3) we prove that our protocol fulfills theledger properties by modeling the computation in BAP-based PoW withthe modified universal sampler [9, 32].

5.1.2

Final Preparations

We finalize our overview by presenting the concrete execution setting of theblockchain protocol.
Concrete execution settings. The settings are as follows.
• Time and slots: Time is divided into discrete units called time slots,indexed by an integer ℓ ∈ {1, 2, . . . }. We assume a globally synchronized clock T is equipped with a key pair (skT , pkT ) from the signature scheme SIG. Users can submit queries (σT , ℓ) ← T (m) such that
(σT , ℓ) ← SIG.Sign(skT , m, ℓ) where m is the query message and ℓ is
the index of the current slot;• Synchrony: We adapt the δ-synchronous setting from [12] to our slotbased execution where δ is the known network delay. Suppose an honestuser sends a message in slot t, the message is guaranteed to be received
by all honest users in any slot ℓ ≥ t + δ. Moreover, we assume thediffusion functionality from [26];• Rushing adversary: We consider a rushing network adversary who isable to: (1) receive any message from honest users first; (2) decide
for each recipient whether to inject additional messages; (3) decide theorder of message delivery; (4) diffuse its (the adversary’s) messages
after seeing all honest messages;• Permissionless setting with static corruption: We follow the constrained
permissionless setting from [45]. In each slot, there are exactly n ∈ Nusers executing the protocol, and at least one is honest. Whenever an
53

honest user joins, the protocol informs her with the parameters (n, δ).
Moreover, we assume a static corruption model so that the adversary
cannot corrupt honest users after they are spawned.
Remark 2 (P2PET Rationale) In the P2PET system, users must perform energy transmission and payment activities periodically. In order tohandle the periodical activities, time is divided into discrete time slots likein [35]. Each user has a local clock implemented by the certified smart meter, which may not be fully synchronized in real-life. However, the length ofeach time slot can be adjusted to ensure that any differences in local time
between users are negligible. For the sake of convenience, we assume thepresence of a globally synchronized clock. Moreover, the certified hardware
used in the system allows a permissioned setting, where a fixed number ofusers are initialized before the protocol starts, and everyone knows who thehonest users are. However, the security proof does not depend on this specificsetting. Therefore, we adopt a constrained permissionless setting, which ismore general and inclusive.

5.2

Model of Blockchain-Based Double Auction

This section presents the basic system model abstracted from the underlying
blockchain-based P2PET, including our redesigned data structure and theconsidered problem.
The first step is to define the blockchain’s data structure to support operations in the P2PET system. Recall that the system enables its users to buy
or sell energy with energy storage and transmit equipment. Concretely, if auser produces more energy than she needs, the surplus can be stored. Then,the user can use the energy afterward or sell it through the system network.
The buy/sell operation resembles a double-sided auction market with energy
as the trading resource. Hence, we borrow the term “bid”, which is further categorized as “buy bid” (from buyers) or “sell bid” (sometimes called“ask”, from sellers). Therefore, in order to support the bid operation, we add
a bid layer to the conventional “transaction-block” structure. Moreover, as
in conventional blockchain protocols, a transaction is regarded as the agreement of trading, which, in our case, is the energy transmission and payment
agreement between a buyer and a seller. Thus, we define the transaction as a
combination of a buy and a sell bid with some restrictions which are specified
in later sections.

54

Next, we abstract the process of generating a set of transactions from agiven set of bids, as the early outlined BAP, in which we define a generalscoring function to quantify the quality of the solutions, i.e., each presented
set of transactions. The BAP, with respect to the scoring function, is acombinatorial optimization problem, and can be regarded as a many-to-many
assignment problem, a special case of the GMAP [43], as it was alreadydescribed. Note that the BAP is the underlying problem of our PoW for ourblockchain protocol. We formally introduce the BAP and review the GMAP
in the next sections.

5.2.1

Definitions for the Blockchain Data Structure

The redefined definitions include bids, transactions, and, for completeness,block, and chain [51]. In the following, we denote each instance as bid, tx, bk,
and chain, whereas we denote users as U. For bids or blocks, when specifying
issuer (or generator) U and time slot ℓ ≥ 1, we denote them explicitly as bidℓU
or bkℓU , respectively. Moreover, each instance is associated with an identifier,which is set to be the hash of the instance’s contents, e.g., bidID = Hash(bid)is the identifier of a given bid bid. As we mentioned in the execution model,
within the definitions, we assume that the global time server T is securedby the signature scheme SIG. The server T (m) returns queries for m, fromusers, with (σT , ℓ) ← T (m) such that σT = SIG.Sign(skT , m, ℓ) and time slotℓ.
Starting with bids, users have two options: (1) to buy a quantity of energy
units for an initial price (anything lower is acceptable); (2) to sell a quantityof energy units for an initial price (anything upper is acceptable). A bid
should include its generation and expiration time slots. They must be signedby their issuer and the time server. The formal definition is as follows.
Definition 16 (Bid) A bid bid issued by a user U who holds a key pair∆(sk, pk) from the signature scheme SIG is defined as bid = (bidraw , auxU , auxT )and is associated with an identifier bidID = Hash(bid) where:∆• The bid’s raw content, bidraw = (kind ∈ {buy, sell}, q, p, tGen , tExp ):– kind ∈ {buy, sell} indicates the bid’s kind, i.e., a buy bid or a sellbid;
– q, p > 0 denote the bid’s quantity and unit price, respectively;– tGen , tExp denote the bid’s generation and expiration time slots, respectively.

55∆• Information relates to the user’s signature, auxU = ((pk, σ), misc):– (pk, σ) is the user’s public key and signature, i.e., σ = SIG.Sign(sk,bidraw );– misc contains additional information from the user, e.g., a certificate by a trusted authority attesting the user’s public key.
∆

• auxT = (pkT , σT ) consists of the public key and signature from the time
server T , i.e., σT = SIG.Sign(skT , (bidraw , auxU )).
Moreover, we denote the bid space by BID.
Next, a transaction combines a buy and a sell bid at the selected quantityand price. Intuitively, the transaction’s quantity should not exceed the original bids’ quantity, and the price should be in the range of the original bids’
prices. However, note that we enable our protocol to handle more complex
bid assignments. Concrete restrictions will be presented in Section 5.3.
∆

Definition 17 (Transaction) A transaction tx is defined as tx = (bidID1 ,bidID2 , qtx , ptx ) and is associated with an identifier txID = Hash(tx) where:• bidID1 , bidID2 are the identifiers of two bids bid1 , bid2 . We may use
bid1 , bid2 directly for simplicity;• qtx ≥ 0, ptx > 0 denote the agreed quantity and unit price of the trade.
Moreover, we denote the transaction space by TX.
Here, for completeness, we also present the definition of a block. A blockembeds both a bid set and a transaction set, in which the transaction set isderived from the bid set via the BAP. The block should also include a hashlink pointing to its parent block. Similar to bids, the user who generates
blocks need to secure the block with the signatures from herself and the time
server.
Definition 18 (Block) A block bk generated by a user U with (sk, pk) from∆
SIG is defined as bk = (prevHash, bkraw , auxU , auxT ). It is associated with an
identifier bkID = Hash(bk) and a score Sbk . In a block bk:• prevHash denotes the identifier of the block’s parent block, i.e., the hashof the block that bk intends to extend;∆• The block’s raw content, bkraw = (BIDs, TXs, t):56

– BIDs ̸= ∅, TXs denote the set of bids and transactions embedded in
the block;– t denotes the block’s generation time slot.
∆∆• Information of signatures auxU = ((pk, σ), misc) and auxT = (pkT , σT )are similar as in bids (Definition 16) where σ = SIG.Sign(sk, (prevHash,bkraw )) and σT = SIG.Sign(skT , (prevHash, bkraw , auxU )).
Moreover, we denote the block space by BK.
Finally, as in conventional blockchain protocols, the chain is defined as
an ordered linked list of blocks. The first block is called genesis block anddenoted by bkG , which contains the public keys of users and is publicly known
to all users. Then, all the users, when aware of new block candidates, will
discard the ones which are signed with public keys that are not in the initial
list.
Definition 19 (Chain) Let || denotes block concatenation, i.e., if bkt ||bkt+1 ,then bkt+1 ’s prevHash equals to bkt ’s identifier. Hence, a chain chain is an∆ordered linked list of blocks defined as chain = bkG ||bk1 ||bk2 || · · · where bkG
is the genesis block that contains the public keys of the users of the system.
Note that we consider a tree structure in the protocol description (Section 5.4) and security analysis (Section 5.5). Hence, we may use “branch”,
i.e., branch, as an interchangeable term of “chain” (Definition 30).

5.2.2

The Bid Assignment Problem (BAP)

Based on the refined data structure, we propose BAP that abstracts theprocess of finding an “optimal” set of combinations of bids, i.e., a set oftransactions. The optimality is defined based on a scoring function whichshould be sophisticatedly designed according to a real-life situation, e.g., market dynamics in the P2PET system. We emphasize again that this chapter
focuses on the protocol-level design instead of fully investigating the underlying energy trading market. Hence, we leave the scoring functions general
to showcase the flexibility of our design.
Concretely, we proceed with our definitions by first showing a genericframework of the BAP with an unspecified scoring function. Next, we consider the scoring function on the transaction level and then extend it to theblocks. These scoring functions are still general, but their domains are defined on the concrete data structure, i.e., transaction sets and blocks. The

57

scoring function for transaction sets is taken as an intermediate step because a transaction set must be output before generating a block. Finally,
with the scoring function for blocks, we define the BAP for block generation(bk-BAP). The purpose of bk-BAP is to argue our highest-score-based blockselection rules in the protocol design.
The generic BAP. Our explanation starts from the generic version of the
BAP, i.e., we consider an unspecified scoring function s : X → R where X isan arbitrary space. Later, we instantiate s. The BAP takes as input a nonempty set of bids, denoted by BIDs. Here, for simplicity, we assume all bids
in the set are “alive”, i.e., the bid was issued before and is not expired, andall bids’ signatures are valid (the signature scheme’s verification algorithm
outputs 1, i.e., 1 ← SIG.Verify). Hence, we can focus on the quantity andprice constraints in the BAP. That is, we reframe the bids as bid = (kind, q, p)
in the following description. Next, according to each bid’s kind, we canfurther divide the input set BIDs into a buy bid set and a sell bid set. Without∆
B
B
loss generality, we write BIDs = B ∪ S where B = {bidB
i = (buy, qi , pi )}i∈[m]∆

is a buy bid set of size m, and S = {bidSj = (sell, qjS , pSj )}j∈[n] is a sell bid setof size n such that B ∩ S = ∅. Then, all the combinations of the bids can be∆Sgiven by the index set I = {(i, j) : bidBi ∈ B ∧ bidj ∈ S} = {(i, j)}i∈[m],j∈[n] .
SAn assignment between a buy bid bidBi ∈ B and a sell bid bidj ∈ S is atransaction in the sense of Definition 17, and it can be denoted by a tuple withrespect to indices: (i, j, qij , pij ) where qij and pij are the assigned quantityand price, respectively.
Next, we consider the assignment constraints. Note that, unlike matching problems, we enable many-to-many assignments, i.e., a buy bid can be
assigned to multiple sell bids, and multiple buy bids can be assigned to asell bid. Hence, the total assigned quantity of a bid should not exceed thebid’s original quantity, and the assigned price of a buy and a sell bid should
fall in the range of their original prices. Then, for all (i, j) ∈ I, we have thefollowing constraints.
qij ≥ 0,n−1Xqij ≤ qiB ,j=0

pSj ≤ pij ≤ pB
i ,

m−1
X

qij ≤ qjS ;i=0

if qij ̸= 0.

(5.1)

We can now clarify the scoring function’s domain by defining the assignment space A. Concerning the input bid set BIDs ̸= ∅, denote an assignment∆
set with A = {(i, j, qij , pij ) : Given BIDs, ∀(i, j) ∈ I, Equation 5.1 holds}.
Then, the space of all assignment sets with respect to BIDs can be defined58

∆

as ABIDs . We define the space of all assignment sets as A = {A : A ∈ABIDs }BIDs∈BID and rewrite the scoring function as s : A → R. Finally, theformal definition of our Generic BAP is given as follows.
Definition 20 (Generic BAP) Let BIDs ⊆ BID be a non-empty set ofB
Bbids, which can be divided into B = {bidB
i =(buy, qi , pi )}i∈[m] and S ={bidSj =(sell, qjS , pSj )}j∈[n] , such that BIDs = B ∪ S and B ∩ S = ∅. Let
I = {(i, j)}i∈[m],j∈[n] be the index set. Given the scoring function s : A → R
where A denotes the assignment space, the Generic BAP is to find a set∆
X = {(i, j, qij , pij ) : (i, j) ∈ I} that maximizes s(X) and satisfies the constraints given by Equation 5.1.
We say a solution to the BAP is “valid” if the output set X is an assignment set, i.e., X = {(i, j, qij , pij ) : Given BIDs, ∀(i, j) ∈ I, Equation 5.1 holds}.
Hence, the validity of BAP solutions does not require optimality, which isconvenient to define the BAP-based PoX scheme later in Section 5.3 (Definition 25).
BAP for block generation. The Generic BAP provides an intuition of
the problem’s input and output. However, in order to integrate the BAP
into our P2PET blockchain protocol, we need to adapt the problem so thatit can output blocks, and the scoring function should be able to quantify thequality of blocks. As mentioned above, we first consider a general scoring
function for transaction sets. Then, here, we extend it to the scoring function
for blocks sbk . The latter will instantiate the scoring function in the Generic
BAP (Definition 20) and complete our BAP for block generation (bk-BAP)
Definition next.
We start from a function that evaluates one transaction stx : TX → R andan aggregation function Aggtxs : R∗ → R. The aggregation function takes
as input all evaluated values within the given transaction set and outputs
the aggregated value as the score of the set. Hence, the scoring function
for an arbitrary k-size transaction set TXs = {txi }i∈[k] can be written as∆

stxs (TXs) = Aggtxs (stx (tx1 ), . . . , stx (txk )). Here, we show a toy example. Let
stx (tx) = qtx · ptx for any transaction tx = (bid1 , bid2 , qtx , ptx ) ∈ TX, and let
Aggtxs be thePsum function. Then, given any transaction set TXs ⊆ TX,
stxs (TXs) = tx∈TXs qtx · ptx .
Next, recall the structure of blocks given in Definition 18. For simplicity,
we reframe the blocks as bk = (TXs, AUX) where AUX = (prevHash, BIDs, t, auxU ,auxT ). Following the same process of defining stxs , let saux be the scoring function for auxiliary information, and Aggbk : R2 → R be a general aggregation
59

function. The function Aggbk aggregates the score of a transaction set andthe score of auxiliary information within the given block. Hence, given any
block bk = (TXs, AUX) ∈ BK, the scoring function for blocks is defined as∆
sbk (bk) = Aggbk (stxs (TXs), saux (AUX)). We have the following definition.
Definition 21 (Scoring Function for Blocks) Let stx : TX → R be afunction that maps a transaction to a real value, and let Aggtxs : R∗ → R bea general aggregation function. The scoring function for transaction sets is
stxs : TX∗ → R such that for any k-size transaction set TXs = {txi }i∈[k] , then∆stxs (TXs) = Aggtxs (stx (tx1 ), . . . , stx (txk )). Let saux : {0, 1}∗ → R be a functionthat maps auxiliary information of blocks to a real value. We use {0, 1}∗ todenote the unspecified input domain. Next, let Aggbk : R2 → R be anotheraggregation function that takes as input two real values. The scoring function
for blocks is given by sbk : BK → R such that for any block bk = (TXs, AUX):∆

sbk (bk) = Aggbk (stxs (TXs), saux (AUX)).
Finally, we refine the Generic BAP with our newly defined scoring function for blocks sbk to complete the bk-BAP.
Definition 22 (bk-BAP) Let BIDs ⊆ BID be a non-empty set of bids,
S
B
B
which can be divided into B = {bidB
i =(buy, qi , pi )}i∈[m] and S = {bidj =(sell,
qjS , pSj )}j∈[n] , such that BIDs = B ∪ S and B ∩ S = ∅. Let I = {(i, j)}i∈[m],j∈[n]
be the index set. Given the scoring function for blocks sbk : BK → R as
in Definition 21, the bk-BAP is to find a block bk = (TXs, AUX) whereS
TXs = {(bidB
i , bidj , qij , pij ) : (i, j) ∈ I} and BIDs ∈ AUX. The block bk
should maximize sbk (·), and the transaction set TXs should satisfy constrains
given by Equation 5.1.
Remark 3 (Extensions) The data structure and BAPs can be extended in
multiple ways depending on the real-life requirements of the P2PET system.
For example: When trading energy, users may have preference targets tosell to or buy from. Hence, we can embed a target list (potentially orderedaccording to priority) within the bid data structure, i.e., (U, targets) ∈ bid
where U is the bid’s issuer, and targets ⊆ {Ui }i∈[N ] is a subset of the all Nusers with whom the user willing to trade. Then, the BAPs should: (1) take
into consideration the target constraints when assigning bids, i.e., for any pairof buy and sell bids, bid1 = (buy, U1 , targets1 ) and bid2 = (sell, U2 , targets2 ),addition to constraints in Equation 5.1, assignment (bid1 , bid2 ) should alsosatisfy U1 ∈ targets2 ∧ U2 ∈ targets1 ; (2) adjust scoring function so thatprioritized target grant higher scores. We hope this example can demonstrate
our abstraction’s capability of modeling the real-life system.
60

In the following two sections, we show our design of a blockchain protocolthat takes the competitive PoX as its core. We argue that extensions like theexample given above can be easily integrated into our design with significant
changes in the (yet to be presented) security analysis.

5.3

BAP-Based PoW and Competitive PoXThis section introduces a PoW scheme based on the bk-BAP. Like conventional PoW, the BAP-based PoW involves two types of participants: provers
and verifiers. Note that both types are performed by users in our protocol.
The separation here only aims to clarify the algorithms, i.e., the prover runs
a solving algorithm to solve the bk-BAP; Whereas the verifier evaluates thesolution’s validity and its score.
In order to present our scheme, we consider the setting where provers
maintain a pool of bids alongside their views of the blockchain. For simplicity,
we assume all bids are issued with valid signatures and correct identifiers, i.e.,
computed honestly from the hash function. The “bidpool” is similar to themempool in other blockchain protocols, with the difference that the mempool
keeps transactions. A prover needs to update her bidpool according to thebidding history in the P2PET system and the transaction history recordedby the blockchain.
Our BAP-based PoW scheme starts with each prover holding a bidpool,and then the prover samples a bid set as the input for the bk-BAP. Hence, wefirst (1) show an algorithm for updating the bidpool, and then (2) present
the formal syntax of the BAP-based PoW scheme. Finally, we model thescheme with a universal sampler [9,32], which has the interesting property ofallowing random sampling from arbitrary distribution. In our case, we relyon this property to randomly sample BAP-based PoW solutions (blocks andcorresponding scores). Moreover, we argue the reason and the limitation ofthis modeling.
We clarify that this section focuses on algorithms and the model of BAPbased PoW. Block selection and blockchain maintenance are explained in
Section 5.4, which utilizes our modeling, is presented in Section 5.5.
Starting with the bidpool. Its purpose is to keep track of a continuous
view of all available bids in each time slot so that provers can sample their
input bid sets for generating blocks by solving the bk-BAP. Each prover
maintains her bidpool concerning two aspects: (1) The bidding and transaction history embedded in the prover’s blockchain; (2) The newly issued
bids in the previous slot. Therefore, this section starts with the definitionsof the history. Then, by introducing the “residual” of bids, i.e., the unas61

signed (quantity) part of bids in the history, we show the concrete approachand specify the algorithm for updating the bidpool (the yet to be introduced
Algorithm 3) later.
Definition 23 (Bid History and Transaction History) For any prover,let chain = bkG ||bk1 || . . . ||bkℓ be the prover’s blockchain, and for t ∈ [ℓ],let bktraw = (BIDst , txt , t) ∈ bkt . The bid and transaction history with re∆spect to chain is defined as H ℓbid = {bidID : bid ∈ BIDs1 ∪ · · · ∪ BIDsℓ } and∆H ℓtx = {txID : tx ∈ TXs1 ∪ · · · ∪ TXsℓ } where bidID and txID are the identifiersof bid and tx, respectively. For convenience, we may also use the corresponding bid or transaction for the given identifier.
Recall that the transaction sets are generated following the constraints
given in Equation 5.1, i.e., the sum of assigned quantity in all transactions
that involve a given bid should not surpass the bid’s original quantity. Thus,in order to reduce the waste in energy trading, we enable provers to include
bids with unassigned quantities into their bidpool. We name such bids as
residual bids. A residual bid is a bid that exists on the blockchain, i.e., in
the bid history, that has unassigned quantities larger than 0.
Definition 24 (Residual Bid) Let chain = bkG ||bk1 || . . . ||bkℓ be a blockchain.
Denote its bid and transaction history with H ℓbid and H ℓtx , respectively. Givena bid bid = (kind, q, p, aux) with identifier bidID ∈ H ℓbid , the residual bid of∆∆
bid is defined as rbid = (kind, qrbid , p, aux) if qrbid > 0, and rbid =⊥ if qrbid ≤ 0.
Here:
X
qtx .
(5.2)
qrbid = q −{tx:txID∈H ℓtx ∧bidID∈tx}

If rbid ̸=⊥, we set its identifier to bidID, i.e., the original bid’s identifier.
We denote the set of all residual bids with respect to a given chain as Rchain .
Provers can assign a residual bid into a new transaction without exhausting the bid’s qrbid , thereby deriving a new residual bid from the originalresidual bid. That is, we enable provers to assign bids recursively as longas the bid is not expired. Moreover, because the residual bid’s identifier is
identical to its original (residual) bid, it is possible to maintain the historyof each bid by tracking unique identifiers. This is also the reason we define
the history using identifiers in Definition 23. Therefore, in the following,
we denote the bidpool with Pool and use mappings to represent entries inthe bidpool, i.e., (bidID:bid or rbid) ∈ Pool where bidID is the identifier of a(residual) bid.

62

The algorithm for updating bidpools. Considering the process of updating the bidpool for any prover P, at the beginning of time slot ℓ ≥ 1, let
the prover hold a bidpool from the previous slot, denoted by Poolℓ−1 , and a
blockchain chainℓ−1 = bkG ||bk1 || . . . ||bkℓ−1 . We denote the set of bids in which∆
all bids are issued in slot ℓ−1 with P ℓ−1 = {bid : tGen = ℓ−1}. Here, tGen is thebid’s generation time slot. Then, the algorithm that outputs the updated bidpool for slot ℓ can be written as Poolℓ ← UpdatePool(Poolℓ−1 , chainℓ−1 , P ℓ−1 ).
For consistency of format, we may reframe the bid set P in the form of mapping, i.e., P ℓ−1 = {(bidID:bid) : tGen = ℓ−1}. Note that ℓ = 1 is slightly
different because in the previous slot, PoolG = ∅ and chain = bkG . That is,G
it contains no history, i.e., H G
bid = ∅, H tx = ∅.
Next, we clarify that for any t ∈ [ℓ−1], the block bkt−1 is generated
based on the bidpool in the same slot Poolt−1 . In other words, we need toremove the duplicated identifiers from the bidpool referring to the block’s bid
set. Then, by adding the set of freshly issued bids from the previous slot tothe bidpool, we obtain a pool that contains all viable unique bid identifiers.
Thus, we can refer to the transaction history on the blockchain to derive
residual bids for these identifiers. The last step of the UpdatePool algorithm
is to remove the outdated bids, i.e., bids with expiration slots tExp earlier
than the current slot. Finally, the algorithm outputs the new bidpool fromthe identifiers and their corresponding bids or residual bids. The procedure
is formally specified in Algorithm 3.

5.3.1

Formal Syntax of BAP-based PoW

Given any time slot ℓ ≥ 1, the BAP-based PoW scheme consists of the∆tuple of algorithms PoBA = (SampleBIDs, Solve, Eval). The SampleBIDs algorithm samples a bid set from the prover’s updated bidpool as the input of
the bk-BAP; Solve outputs the corresponding blockchain of a valid solution(block) to the bk-BAP. As mentioned before, by valid, we mean the solution
satisfying the constraints and signatures being valid; Finally, the evaluation
algorithm Eval verifies the validity of the whole blockchain and outputs thescore of the latest block according to the public scoring function. We define
the BAP-based PoW correctness (Definition 27) after presenting the formal
syntax in the next definition.
Definition 25 (BAP-based PoW Scheme) Let Hash : {0, 1}∗ → {0, 1}λbe a collision-free hash function, and let sbk : BK → R be a publicly known
scoring function for blocks as given in Definition 21. In time slot ℓ ≥ 1,
for any prover P, let PoolℓP be her updated bidpool from Algorithm 3, and63

Algorithm 3: The UpdatePool algorithm. Let ℓ ≥ 1 be the current time slot. UpdatePool is parameterized by a bidpool Poolℓ−1 , a
blockchain chainℓ−1 , and a set of bids P ℓ−1 .
function UpdatePool(Poolℓ−1 , chainℓ−1 , P ℓ−1 );Let Poolℓ = ∅;3 if ℓ = 1 then4
Parse PoolG = ∅, chain = bkG , and P G = {(bidID:bid) : tGen = G};
5
Return Pool1 = P G
6 elseℓ−17Parse chainℓ−1 = bkG ||bk1 || . . . ||bkℓ−1 and bkℓ−1, txℓ−1 , ℓ−1) ∈ bkℓ−1 ;raw = (BIDsℓ−1
8Parse P= {(bidID:bid) : tGen = ℓ−1};// Remove duplicated identifiers from Poolℓ−1 .
9for bid ∈ BIDsℓ−1 do
10
if bidID ∈ Poolℓ−1 then11
Delete the entry from Poolℓ−1
12
end
13
end
// Collect all unique bid identifiers.
14
Set Poolℓ = Poolℓ−1 ∪ P ℓ−1 ;// Derive (residual) bids for each identifier with Equation 5.2.
15
Parse the transaction history of chain as H ℓ−1tx ;16
for bidID ∈ Poolℓ do// Let q be the original
bid’s quantity with bidID.
P
17
Compute qrbid = q − {tx:txID∈H ℓ−1 ∧bidID∈tx} qtx ;
1

2

tx

if qrbid > 0 thenReplace the entry in Poolℓ with (bidID:rbid) such that qrbid ∈ rbid;
end

18
19
20

end
// Remove outdated bids from Poolℓ .
for bidID ∈ Poolℓ do// Let tExp be the bid’s expiration slot with bidID.
if tExp < ℓ thenDelete the entry from Poolℓ
end
end
Return Poolℓ

21

22
23
24
25
26
27
28

end

let chainℓ−1= bkG ||bk1 || . . . ||bkℓ−1 be her current blockchain. The proverP
performs (SampleBIDs, Solve), and any verifier performs Eval.
• SampleBIDs(PoolℓP , N; rPℓ ) takes as input the prover’s bidpool PoolℓP , anupper bound N for the size of bid sets, and a random seed rPℓ . The
randomness can be omitted, we write it explicitly for later modelingthe computation in BAP-based PoW. SampleBIDs outputs a set of bids
BIDsℓP ⊆ PoolℓP such that |BIDsℓP | ≤ N;ℓℓℓ
• Solve(chainℓ−1
P , BIDsP ) takes as input a bid set BIDsP that satisfies |BIDsP |≤ N. The algorithm outputs the prover’s solution to the bk-BAP,
i.e., a block candidate bkℓP = (TXs, AUX), with the corresponding new

64

∆

ℓ
ℓ
blockchain chainℓP = chainℓ−1
P ||bkP . Here, AUX = (prevHash, bidP , ℓ,auxP , auxT ), prevHash = Hash(bkℓ−1 ), and all signatures in (auxP , auxT )are valid;• Eval(chaintP ∗ , N) takes as input a blockchain chaintP ∗ from prover P ∗and the size bound N for bid sets. If t ̸= ℓ, Eval outputs (0, ⊥).
Otherwise, parse chainℓP ∗ = chainℓ−1 ||bkℓP ∗ where bkℓP ∗ is generated byℓ−1
P ∗ , and assume (1, ·) ← Eval(chainℓ−1 , N). Let H ℓ−1
debid and H tx
note the bid and transaction history of chainℓ−1 , respectively. ParsebkℓP ∗ = (prevHash, (BIDs∗ , TXs∗ , t∗ ), auxP ∗ , auxT ), if all the following
conditions hold, the algorithm outputs (1, sbk (bkℓP ∗ )), and we say theblockchain and the new block are valid:
1. For previous hash prevHash: Let bkℓ−1 be the latest block on theverified blockchain chainℓ−1 : prevHash = Hash(bkℓ−1 );2. For bid set bid∗ : (1) |BIDs∗ | ≤ N; (2) For each bid ∈ BIDs∗ withgeneration and expiration time slots (tGen , tExp ), the current slot ℓ ∈[tGen , tExp ]; (3) Let bidID be bid ∈ BIDs∗ ’s identifier, if bidID ∈/ H ℓ−1bid ,and the signatures in bid are valid;
3. For transaction set TXs∗ : Let BI = {bidID : bid ∈ BIDs∗ } and T I ={txID : tx ∈ TXs∗ } be the identifier sets given by BIDs∗ and TXs∗ , respectively. Then: (1) For each tx = (bidID1 , bidID2 , qtx , ptx ) ∈ TXs∗ ,ℓ−1ℓbidID1 , bidID2 ∈ H ℓ−1
bid ∪ BI; (2) Let H tx,P ∗ = H tx ∪ T I. For eachtx = (bidID1 , bidID2 , qtx , ptx ) ∈ H ℓtx,P ∗ , without loss of generality, let
bid1raw = (buy, q1 , p1 ) has identifier bidID1 , and bid2raw = (sell, q2 , p2 )has identifier bidID2 , and the assigned quantity and price of tx satisfies:
X^X^
qtx ≤ q1
qtx ≤ q2 p2 ≤ ptx ≤ p1 .
txID∈H ℓtx,P ∗ ∧bidID1 ∈tx

txID∈H ℓtx,P ∗ ∧bidID2 ∈tx

4. For block generation slot t∗ : t∗ = ℓ;
5. For auxiliary information (auxP ∗ , auxT ): The signatures are valid.
Otherwise, the algorithm outputs (0, ⊥).
Correctness of the BAP-based PoW scheme requires that the Eval algorithm accepts any blockchain from honestly executed SampleBIDs and Solvealgorithms. Because the SampleBIDs algorithm starts with a bidpool, we needto first define validity for bidpools. Here, we consider a VerifyPool algorithm
to check “conflicts” between an updated bidpool and the blockchain.
65

Definition 26 (Validity of Bidpool) For any prover in time slot ℓ ≥ 1,
let Poolℓ be her bidpool, and let chainℓ−1 = bkG ||bk1 || . . . ||bkℓ−1 be her blockchain.
The prover performs VerifyPool.
• VerifyPool(Poolℓ , chainℓ−1 ) takes as input the bidpool Poolℓ and the blockchainℓ−1ℓ−1
chainℓ−1 . Let H ℓ−1. If the folbid and H tx denote the history of chain
lowing conditions hold, VerifyPool outputs 1, and we say the bidpool
Pool is valid regarding the blockchain chain.
1. The blockchain is valid, i.e., (1, ·) ← PoBA.Eval(chainℓ−1 , N) where
N is the size bound of the bid set embedded in each block on theblockchain;
2. For each bidID ∈ Poolℓ , let its corresponding (residual) bid havequantity qrbid , and have generation and expiration time slots (tGen , tExp ):(1) The current time slot ℓ ∈ [tGen , tExp ]; (2) If bidID ∈ H ℓ−1
bid , qrbid
computed from Equation 5.2 is larger than 0; (3) If bidID ∈/ H ℓ−1bid ,and the signatures in the corresponding bid are valid.
Otherwise, the algorithm outputs 0.
The reason why VerifyPool considers only an updated bidpool regarding
the blockchain is that provers would not keep tracking old bidpools and bid
sets after updating them to the new bidpool. Hence, the proposed algorithm
is to verify the validity of bidpools, instead of deciding the correctness of
the UpdatePool algorithm. Next, we define the correctness of the BAP-based
PoW scheme.
Definition 27 (Correctness of the BAP-based PoW Scheme) Given any
prover P in time slot ℓ ≥ 1, let (chainℓ−1 , Poolℓ , N) be the prover’s input tuple such that (1, ·) ← Eval(chainℓ−1 , N) and 1 ← VerifyPool(Poolℓ , chainℓ−1 ).
The BAP-based PoW scheme is correct, if BIDs ← SampleBIDs(Poolℓ , N) andℓℓ−1
chainℓ−1
P ||bkP ← Solve(chainP , BIDs) are honestly executed, then:ℓPr (1, sbk (bkℓP )) ← Eval(chainℓ−1
P ||bkP , N) = 1.
Usually, in general PoX schemes (Definition 1) that involve computationaltasks, e.g., PoW [20] and proof-of-useful-work [6,23], the difficulty is anothercrucial property. Intuitively, it requires provers to contribute enough computing power to generate valid blocks. Otherwise, adversarial provers cangenerate massive blocks in a short period of time, and the network cannot
be finalized on a chain of blocks but with many “forks”.
However, the validity of blocks in our BAP-based PoW scheme does not
require optimality. Hence, it is easy to generate valid blocks for any prover.
66

Instead, our “difficulty” lies in the competition, i.e., honest provers only
select the highest-scored blocks (or precisely, blockchains as it will be introduced in Section 5.4.2). Relying on block scores in BAP-based PoW ismeaningful because the score relates to the underlying P2PET system. Then,a higher-scored block is preferable to the system regardless of who (honest ornot) generates the block. Hence, despite that we follow conventional modeling approaches [26] that differentiate the computing power of the honest
provers in contrast with adversarial provers, we show in Section 5.5, that thisdifferentiation does not change the security of our protocol (a higher score
block, even if adversarial, is still useful for the overall system).

5.3.2

Competitive PoX and Scheme Modeling

Here, we abstract away from concrete problems but return to our general PoX
framework in Definition 1. This approach is appropriate based on the following evidence: (1) Given a well-chosen scoring function, the BAPs (genericand bk-BAP) can be reduced to the generalized multiple-assignment problem, which has been proven to be NP-complete [43]; (2) Stochasticity arises
in assignment problems due to the uncertainty in problem inputs [21], i.e.,
in our case, BAP-based PoW requires provers to sample input bid sets from
bidpools for the bk-BAP, hence, some bids may not need to be assigned.
Therefore, instead of concrete implementations of the general scoring function, we consider a competition among provers whose solutions are assigned
scores according to some distribution determined by the function. This abstraction enables us to model the provers’ operations with queries to a scoringoracle represented by a modified universal sampler [9].
In the following, we mimic the BAP-based PoW and show the syntax ofour competitive PoX framework.
Definition 28 (Competitive PoX CPoX) Let s : P → R be a publicly
known scoring function where P denotes the solution space. The tuple of algorithms (TaskGen, Solve, Eval) in a general PoX scheme performs as follows:• TaskGen(1λ ) takes as input the security parameter λ. It outputs publicparameters pp and a task task;• Solve(pp, task) takes as input pp, a task task. It outputs a proof π forthe given task task;• Eval(pp, task, π) takes as input pp, a task task, and a proof π. It outputs(1, s(π)) if π is a valid according to task; Otherwise, it outputs (0, ⊥).

67

Like Definition 25, we also extend the evaluation algorithm Eval to the whole
blockchain. It outputs (1, s(π)) if all solution on the chain is valid and thelast solution being π. Otherwise, it outputs 0.
Next, we first show the definition of the modified universal sampler [9].
Then, we detail the interaction between BAP-based PoW provers and theuniversal sampler.
Definition 29 (Universal Sampler [9]) A universal sampler scheme con∆sists of algorithms US = (Setup, Sample) that are performed as follows.
• Setup(1λ ) takes as input the security parameter λ and outputs sampler
parameters U ;• Sample(U, d, β) takes as input sampler parameters U , the description ofa program d with a random seed for the program to generate samples.
It outputs induced samples pd .
We instantiate the definition above by specifying the program descrip∆tion with d = (task, s) where task is the underlying task of the competitive
PoX scheme and s is the general scoring function associated with the task.
The universal sampler is accessible by any prover performing the competitive PoX scheme via queries in which the prover sends its own bidpool and arandom seed. That is, for any prover P, her query to the universal sampler∆
is β = (taskP , rP ). Here, we follow the conventional model approach that ineach time slot, each honest prover can make at most q > 0 queries, whereas,
the adversarial prover can make at most qA > q queries. We denote theupper bound of total query number in each slot by Q ∈ N. The difference inquery capabilities indicates the difference in computing power between honest and adversarial provers. Moreover, we clarify that the communication
between provers and the universal sampler cannot be delayed by the network
adversary, given it is oracle access. This is a natural setting since the universal sampler captures the capability of provers to internally and locally selectbids and generate blocks relying only on her randomness and the solving
algorithm.
Then, the Sample algorithm has the single property of randomly samDpling a solution π∈P such that s(π) ← S where D and S denotes the score
distribution and score space determined by the scoring function. With awell-chosen scoring function, blocks can be strictly ordered by the score withhigh probability. Concretely, the universal sampler works as follows.

68Universal Sampler
In any time slot ℓ ≥ 1, setup up the universal sampler with U ←US.Setup(1λ ). Let LℓP = {(·, ·, ·, ·)} ∈ U be the list kept by the universal
sampler for any prover P. The total size of lists is upperSbounded by
Q ∈ N, i.e., let Pℓ denote the set of all provers in slot ℓ, | P∈Pℓ LℓP | ≤Q.
On a query (PoolℓP , rPℓ ) from P:• If: there exists a tuple (taskℓP , rPℓ , πPℓ , s(πPℓ )) ∈ LℓP , then, return(πPℓ , s(πPℓ ));• Else if: |LℓP | > q when P is honest or |LℓP | > qA when P isadversarial, then, return ⊥;• Else: run and return (πPℓ , s(πPℓ )) ← US.Sample(U, (task, s),(taskℓP , rPℓ )), and add (taskℓP , rPℓ , πPℓ , s(πPℓ )) to LℓP .
The output distribution. The output from the universal sampler can bemodeled as a continuous random variable X following a score distribution∆
D on a score space S = [smin, smax]. Here, D, smin, smax are determinedby the general scoring function sbk (·). We denote the probability density
function and the distributionfunction of D with f (·) and F (·) such thatRx
F (x) = Pr[X ≤ x] = smin f (t)dt.
Discussion: Block re-using attack. An issue with the BAP-based PoW(or competitive PoX) and our modeling is that it cannot prevent adversaries
from re-using other users’ valid block candidates, e.g., the adversaries canclaim others’ blocks as theirs or modify the block slightly to achieve higherscores without performing enough computation. Hence, in order to tackle theblock re-using attack, we consider an exact time barrier for diffusing blockcandidates in each time slot so that no honest user will diffuse its block before
this time barrier. This is achievable given the globally synchronized clock T .
We clarify that this is the only place in this result where we use the strong
synchronicity of the global clock, and it is a natural setting for P2PET.

5.4

Competitive PoX-Based Protocol

In any given time slot, each user obtains a list of solutions (or block candidates when considering blocks) from the competitive PoX, which is modeled69

by the universal sampler. Each honest user diffuses her highest-scored candidates through the network; Whereas, a rushing adversary, as mentioned in
Section 5.1.2, receives all honest blocks, manages the order, and diffuses its(the adversary’s) candidates accordingly. Since there is more than one block
being delivered to users, and each block can only extend one blockchain, we
consider a directed tree (or precisely, a directed forest due to missing blocks)
structure that stores blocks locally for each user. The root of the “block-tree”
is the genesis block as given in Definition 19. Users extend their block-treein each time slot with newly received blocks and select the “best” branchon the block-tree as their blockchain. Hence, we extend the notion score forbranches to support this selecting operation. Users will output the confirmed
part of their blockchain when asked to report the ledger.

5.4.1

Block-Tree and Score of Branches

Now, we start with the necessary definitions for the block-tree structure andthe scoring function for branches. Given a time slot ℓ ≥ 1, we first consider amaster-tree mtreeℓ that contains all valid blocks (block candidates) generated(NOT diffused) by users (honest or not) from the genesis slot to slot ℓ. Then,
we define the master-tree mtreeℓ = (V, E) as a directed tree such that its
vertex set corresponds to blocks and the edge set corresponds to the hashlink between blocks. Hence, the genesis block bkG is the root of mtreeℓ . Recall
the height definition from graph theory: (1) The vertex height in a directed
tree is defined as the number of edges between the vertex and the root; (2)The tree height is defined as the number of edges in the longest path between
a leaf vertex and the root. Hence, mtreeℓ is of height ℓ. Furthermore, forvertices in mtreeℓ of the same height, the corresponding blocks are generated
in the same time slot. A user may only see a part of the master-tree because
we assume the rushing adversary controls block diffusion. Hence, denote theblock-tree of a user U as treeℓU = (VU , EU ), we have treeℓU ⊆ mtreeℓ , i.e.,
VU ⊆ V and EU ⊆ E. The formal definition is as follows.
Definition 30 (Master-Tree, User’s Block-Tree, Branch) Let bkG be
the genesis block. For any ℓ ≥ 1 and all i ∈ [n] where n is the number∆of users participating the protocol, let BKit = {bkti } ̸= ∅ denote the set of∆ S
valid blocks generated by user Ui in slot t ∈ [ℓ]. Then, BK t = i∈[n] BKit
denotes the set of valid blocks generated in slot t. The master-treeof slotSGℓℓ is defined as mtree = (V, E) such that V = {bk } ∪ t∈[ℓ] BK t , andS
E = {(bkG , bk1 ) : ∀bk1 ∈ BK 1 } ∪ t∈[ℓ−1] {(bkt , bkt+1 ) : ∀bkt ∈ BK t , bkt+1 ∈BK t+1 , prevHash = Hash(bkt )} where prevHash is the previous hash value
70entry in block bkt+1 , i.e., blocks (bkt , bkt+1 ) are linked by the hash function
Hash as in the BAP-based PoW scheme (Definition 25). A block-tree of user
U is denoted by treeℓU = (VU , EU ), and satisfies treeℓU ⊆ mtreeℓ . Moreover,given a block-tree (master or user’s) of slot ℓ as Gℓ = (V ℓ , E ℓ ), a branch is∆∆defined branchℓ = bkG ||bk1i1 || . . . ||bkℓiℓ where I = {i1 , . . . , iℓ } is the index setof block generators such that branchℓ ⊆ Gℓ , i.e., for any t ∈ [ℓ], bktit ∈ V ,and for any t ∈ [ℓ−1] and it , it+1 ∈ I, (bktit , bkt+1
it+1 ) ∈ E.
Recall that the branch definition resembles the definition of blockchain as
mentioned after Definition 19. We may also distinguish them by using branch
for arbitrary branches on a given block-tree, and chain for the highest-scoredbranch.
Moreover, we use branchℓ⌈k for k ∈ N to denote the chain of blocks resulting from the removal of the k rightmost blocks of the branch branchℓ . Ifk ≥ ℓ, we define branchℓ⌈k = ε, i.e., the empty chain. Then, by treeℓ⌈k , wedenote the sub-tree constructing from branchℓ⌈k for all branch ⊆ treeℓ . Notethat in the case of master-tree mtreeℓ , since it contains all generated blocks
in the protocol, we have for any t ∈ [ℓ] and k = ℓ − t: mtreet = mtreeℓ⌈k .
Next, in order to define the best branch with respect to scores, we extend
the scoring function by taking blocks’ generation slots into consideration.
That is, given a branch branchℓ = bkG ||bk1 || . . . ||bkℓ in time slot ℓ ≥ 1, we
introduce an accumulating function acc(t) ∈ R for all t ∈ [ℓ]. Then, the scoreof each slot t is defined as acc(t) · sbk (bkt ). Finally, the score of the branch
is defined as the sum of all slot scores. Formally, we write the score of the
branch branchℓ = bkG ||bk1 || . . . ||bkℓ as follows.
∆

Sbranchℓ =ℓX

acc(t) · sbk (bkt ).

(5.3)

t=1

Note that in our protocol, blocks generated in the same time slot sharethe same height in the block-tree. Then, given an arbitrary block-tree, users
can compute the score of all branches on the tree with Equation 5.3. Hence,
for a user U holding a block-tree treeℓU in time slot ℓ ≥ 1, the user selects her
branch, denoted by chainℓU ⊆ treeℓU , such that:
SchainℓU =maxbranch⊆treeℓU

Sbranch .

(5.4)

As we will show in Section 5.5, the accumulating function parameterizes thepossibility of our protocol achieving consensus.

715.4.2

Protocol Description

Finally, we can present the full description of our protocol. In the following,
we show the workflow of an honest user in an arbitrary time slot where she
maintains her bidpool, generates a block, extends her block-tree, and reports
her confirmed blockchain to the system.
Let U be an honest user among the n ∈ N users performing the protocol intime slot ℓ ≥ 1. Denote the user’s view of the block-tree at the end of slot ℓ−1
with treeℓ−1 . Here, we do not specify them to U because our permissionlesssetting cannot guarantee the user to participate in slot ℓ−1. However, we
require that for any branch branch ⊆ treeℓ−1 , (1, ·) ← CPoX.Eval(branch) as
given in Definition 28. Then, following Equation 5.4, the user selects her
branch, which is denoted by chainℓ−1
U .
Let the input for U’s execution in slot ℓ be (taskℓ−1 , chainℓ−1
U ). By performing the competitive PoX scheme as a prover, the user obtains a set ofvalid solutions (embedded in block candidates), i.e., U generates candidates
with πUℓ ← Solve(taskℓ−1
U ). Denote the set of candidates that embed solu∆ℓtions as BKU = {bki,U }i∈N . Our protocol requires honest users only diffuse
their highest-scored block candidate and the corresponding blockchain, i.e.,
U diffuses the block bkℓU that satisfies s(πUℓ ) = maxbk∈BKU bk, and the corresponding blockchain chainℓ−1
U .
In addition to chain diffusion, users also receive blockchains from others.
Here, we consider the process of the honest U updating her local block∆tree treeℓ−1 = (V ℓ−1 , E ℓ−1 ) when receiving a blockchain (including her own)′
chaintU ∗ . We use U ∗ for unspecified users and t′ for the slot index to beverified. The user U first performs as the verifier in the competitive PoX with′(b, ·) ← CPoX.Eval(chaintU ∗ ). If b = 0, U discards the blockchain. Otherwise,
she compares the incoming blockchain with her local block-tree and adds
missing blocks with hash links to the tree. Concretely, when b = 1, we
have t′ = ℓ. Then, we can rewrite the incoming blockchain with chainℓU ∗ =ℓbkG ||bk1U ∗ || . . . ||bkℓ−1
U ∗ ||bkU ∗ . Note that users accept blockchains. Hence, weonly need to consider a sub-chain bktU ∗ || . . . ||bkℓU ∗ ⊆ chainℓU ∗ such that bkt−1
U∗ ∈treeℓ−1 and bktU ∗ ∈/ treeℓ−1 . Therefore, denote the updated block-tree as
treeℓU = (VUℓ , EUℓ ), we have VUℓ = V ℓ−1 ∪ {bktU ∗ , . . . , bkℓU ∗ } and EUℓ = E ℓ−1 ∪tℓ−1ℓ{(bkt−1
process of blockU ∗ , bkU ∗ ), . . . (bkU ∗ , bkU ∗ )}. We summarize the update′trees with an algorithm: tree′ ← UpdateTree(tree, chaintU ∗ ). Note that we usetree and tree′ instead of specifying slot indices (ℓ−1 and ℓ) because users may
receive more than one blockchain candidate within one slot. The algorithm
is specified in Algorithm 4.
Finally, the user is responsible for reporting her confirmed blockchain to
the protocol with respect to a parameter k (to be estimated in Section 5.5),72

Algorithm 4: The UpdateTree algorithm. Let ℓ ≥ 1 be the current
time slot. UpdateTree is parameterized by a block-tree tree and a′
blockchain candidate chaintU ∗ .
′12function UpdateTree(tree, chaintU ∗ );Parse tree = {V, E};// Verify each blockchain candidate.
′3
4

Run (b, ·) ← CPoX.Eval(chaintU ∗ );if b = 1 then// t′ = ℓ.
′ℓParse chaintU ∗ = bkG ||bk1U ∗ || . . . ||bkℓ−1
U ∗ ||bkU ∗ ;// Find the first block not in tree.

5′

for bktU ∗ ∈ chaintU ∗ dot
if bkt−1/ tree thenU ∗ ∈ tree and bkU ∗ ∈Set V ′ = V ∪ {bktU ∗ , . . . , bkℓU ∗ };ℓ−1
tℓ
Set E ′ = E ∪ {(bkt−1
U ∗ , bkU ∗ ), . . . (bkU ∗ , bkU ∗ )};ℓ′′
Return tree = (V , E )
end
end

6
7
8
9
10
11
12
13

end

i.e., given the user’s updated block-tree treeℓU , the user outputs chainℓU accordℓ⌈k
ing to Equation 5.4 such that chainU is the confirmed part of the blockchain.
Our Competitive PoX-Based Blockchain Protocol Πn,δ,k,sbk ,acc
Let U be an honest user among the n users executing the protocol
Πn,δ,k,sbk ,acc in time slot ℓ ≥ 1. Here, δ is the known network delay, k isa parameter for blockchain confirmation, sbk (·) is the general scoring
function for blocks, and acc(·) is the accumulating parameter function
for branch scores. Given the UpdateTree algorithm and the competitive
PoX scheme CPoX, the user U takes as input treeℓ−1 from the previous
slot ℓ−1.
• Block Generation: U generates block candidates with the comℓℓ−1
petitive PoX scheme, i.e., chainℓ−1
U ||bkU ← CPoX.Solve(chainU );• Block-Tree Update: U initializes an intermediate variable∆
tree = treeℓ−1 . Whenever U receives a blockchain candidate′′
chaintU ∗ , she runs tree′ ← UpdateTree(tree, chaintU ∗ ) and updates
her temporary variable with tree ← tree′ . Finally, the user obtains treeℓU after updating her local block-tree with all blockchain
candidates received in slot ℓ;• Ledger Reporting: Upon queried by the protocol Π, U outputs

73her blockchain chainℓU ⊆ treeℓU that satisfies Equation 5.4, andℓ⌈kregard chainU as the confirmed part of the blockchain.
Discussion: Incentive model. The security proofs of this result are
based on practical assumptions in the sense of implementation. However,
we do NOT analyze the reason behind these assumptions based on rational
analysis as shown in [3,4,25]. Given the richness of the area, we only discuss
the intuition of the incentive model. Like conventional blockchain protocols, there are two layers of incentive: inherent (e.g., transaction fee) and
explicit (e.g., block reward). The inherent incentive in our protocol derives
from where users can tweak transactions to benefit themselves, e.g., assigning higher buy price for their sell bids or lower sell price for their buy bids.
However, prioritizing their own bids in the solving algorithm will potentiallysacrifice the block scores. Hence, the blocks may fail to be selected in theconfirmed blockchain. The trade-off between this inherent reward and thescarification of block scores requires a case-by-case analysis with respect toconcrete scoring functions.
However, problems arise when considering explicit incentives, i.e., rewards to block generators. We argue that a well-chosen scoring function in
BAP-based PoW prevents adversarial users from attacking the underlying
P2PET and from disturbing consensus in the network (as shown in Section 5.5). However, the computation in BAP-based PoW is unfair, i.e., adversaries can dominate the block generation without dominating computing
power. The explicit incentive intensifies unfairness.

5.5

Security Analysis

This section proves the security of our protocol Πn,δ,k with respect to ledger
properties, i.e., persistence and liveness [26]. We first provide the definitionof persistence by adopting the slightly refined version from [23]. For liveness,
existing definitions require that if an honest user receives a transaction, then,
the transaction will eventually be output by all honest users in their ledger,
i.e., blockchain. However, as shown in previous sections, transactions are
not diffused solely in our protocol but are released within blocks. Moreover,each user maintains a local block-tree to keep tracking blocks of the protocol.
Hence, we define block-liveness instead of the original liveness to fit ourdesign.

74

Definition 31 (Persistence and Block-Liveness) Denote blockchain as
chain and block-tree as tree.
• Persistence: For any two honest users with blockchains chainℓ11 , chainℓ22
at time slot ℓ1 , ℓ2 ≥ 1, respectively. Without loss of generality, letℓ1 ≤ ℓ2 . Persistence with parameter k ∈ N indicates that chainℓ11 , should
be a prefix of chainℓ22 after removing the rightmost k blocks;• Block-liveness: For any honest user with chainℓ in time slot ℓ ≥ 1,
block-liveness states that for any t ∈ [ℓ], chaint is extended by at exact
one block.
Remark 4 (Relaxation in Liveness) As discussed above, we cannot define liveness for transactions in our protocol due to the change in the data
structure. There are two options: one is to define liveness for blocks as in
Definition 31, which can be considered as a relaxation of the original livenessproperty, and in fact, our protocol satisfies block-liveness by design (Theorem 5). Whereas, the other option is to define liveness for bids, which can bemeaningless in real life. This is because our main purpose is to require honest
users to find good assignments (higher-scored blocks) according to the scoring function derived from the underlying P2PET system instead of enforcing
them to include every bid.

5.5.1

Persistence

In order to prove persistence, we first make an additional assumption on theadversary. Recall the rushing adversary in our execution model who canlearn all block (blockchain) candidates generated, i.e., the adversary holds
the master-tree of the protocol. We assume that this adversary sends thehighest-scored blockchain of each time slot to at least one honest user.
Assumption 3 Let mtreeℓ be the master-tree in time slot ℓ, and let A be therushing adversary who holds mtreeℓ . Let chainℓ ⊆ mtreeℓ be the highest-scoredbranch that satisfies:
Schainℓ =maxbranch⊆mtreeℓ

Sbranch .

(5.5)

We assume that at least one honest user among the n users who participate
in the protocol receives chainℓ by the end of slot ℓ.
Next, we consider honest users’ local block-tree dynamics. It takes two
steps to achieve persistence: (1) The highest-scored branch of each time slot
should be eventually known to all honest users; (2) Highest-scored branchesof different time slots should have a long enough common prefix.
75Disclosing highest-scored branches. If a block or branch is known to allhonest users, we say it is disclosed, i.e., given a block bk (or a branch branch),
for any honest user with block-tree tree, it holds bk ∈ tree (or branch ⊆ tree).
Remark that given the δ-bounded communication network, a block candidate
generated by an honest user is always disclosed after δ time slots. Generally,
we define d-disclosure for blocks and branches.
Definition 32 (d-Disclosure) Let bkt be a valid block generated in timeslot t ≥ 1, the block is d-disclosed if for any honest user with block-tree treeℓin slot ℓ such that ℓ ≥ t + d, then, bkt ∈ treeℓ . We say a branch is d-closed
if the rightmost block on the branch is d-disclosed.
The following lemma indicates that if a branch is selected as the highestscored branch by any user, the branch will eventually be disclosed.
Lemma 5 Let mtreet be the master-tree in time slot t ≥ 1. Assuming the
network is δ-synchronous, if a branch brancht ⊆ mtreet is selected as thehighest-scored branch according to Equation 5.5, the branch is at most (δ+1)disclosed.
Proof 5 Denote the branch with brancht = bkG || . . . ||bkt , we first consider
the situation where bkt is generated by an honest user, then, it is δ-disclosedby δ-bounded network setting. Hence, branch is also δ-disclosed. Otherwise,
the block is first received by the rushing adversary A in slot t. Because
brancht ⊆ mtreet is the highest-scored branch according to Equation 5.5, by
Assumption 3, an honest user will receive the branch in slot t. Denote theuser’s local block-tree with treet . Since treet is a sub-graph of mtreet , branch
is the highest-scored branch in treet . Hence, the honest user will generate ablock atop branch in the following slot t+1, which is also δ-disclosed. Therefore, the branch is at most δ + 1-disclosed.
Directly from Lemma 5, we have the following proposition for all disclosed
highest-scored branches in the master-tree.
Proposition 1 Assuming the network is δ-slot synchronous, let mtreet be
the master-tree in time slot t in which brancht is selected as the highest-scoredbranch according to Equation 5.5. All blocks on branches in {brancht }t∈[ℓ−(δ+1)]
is disclosed for any ℓ > δ + 1.
Common prefix among selected branches. Proposition 1 only indicates that the highest-scored branch of each time slot will eventually beknown to all honest users. However, even in the master-tree (i.e., everything is known), given two conjunctive slots, the highest-scored branches
76may be different from each other, e.g., a high-but-not-highest-scored branch
gets extended by an extremely high-scored block so that the new branch is
selected in the next time slot. Such a substitution causes the blockchain to
be unstable and prevents honest users from agreeing on the same chain. We
consider two situations: (In the illustration, the circle denotes the blocks
on the branches, and the double circle denotes the branch being selected as
the highest-scored one): (1) If the change of branch selection happens frequently, the block history cannot be settled (Figure 5.1a); (2) If the selectedbranches of different slots have too many distinct blocks, the block history
can get reset (Figure 5.1b). In either case, invalid bids and transactions in
the unconfirmed blocks can disturb the underlying P2PET market.

(a) The selected chain swings overconjunctive time slots and the blocks
during these slots cannot settle.

(b) A branch substitutes the selected
chain after it gets selected for multiple slots so that the history gets reset.

Figure 5.1: Intuition of Chain Instability: In the successful attack, the adversary forces the nodes to keep changing the chain between two cases.
In order to tackle this problem, we first define divergence between branches
and branch viability. The definitions originate from [35], we refine them withrespect to the score of branches. Moreover, since we focus on the highestscored branches in each time slot, and they are disclosed as shown in Proposition 1, we will consider the master-tree in the following analysis for simplicity.
Definition 33 (Divergence and Viability) Let mtreeℓ be the master-treeof time slot ℓ ≥ 1. For any t ∈ [ℓ], given any two branches brancht1 , brancht2 ⊆mtreet , the divergence of brancht1 and brancht2 is given by:div(brancht1 , brancht2 ) = |Sbrancht1 − Sbrancht2 |.
Moreover, let chaint be the highest-scored branch selected from mtreet according to Equation 5.5. A branch brancht∗ ̸= chaint is viable, if div(brancht∗ , chaint ) ≤smax−smin where [smin, smax] is the range of block scores given by sbk (·).
A branch in slot t is viable if the divergence between the branch and thehighest-scored branch can be covered by a single block. That is, the viablebranch could be extended with a block with higher score and substitute theselected chain. We formally define this situation as chain substitution with a77

parameter τ ≥ 1. For convenience, we first introduce the injection operation. . . ||bkℓ11 be a branch of slot
for branches. Let branch1 = bkG || . . . ||bkt ||bkt+1
1. . . ||bkℓ22 be a branch of slot
ℓ1 ≥ 1, and let branch2 = bkG || . . . ||bkt ||bkt+1
2ℓ2 ≥ 2 where t ∈ [min(ℓ1 , ℓ2 )]. Then, the intersection of branch1 and branch2
is denoted by branch1 ∩ branch2 = bkG || . . . ||bkt .
Definition 34 (τ -Chain Substitution) Let mtreeℓ be the master-tree oftime slot ℓ>τ . For any t ∈ [ℓ−τ ], let chaini and chaini+1 be the highestscored branches in slot i and i+1 where i ∈ [t−1, t−2+τ ] such that chaini+1 =t+τbe highest-scored block that extends chaint−1+τ in slot
chaini ||bki+1
c . Let bkc∆
t+τ . Denote the new branches branchc = chaint−1+τ ||bkt+τ
c . A τ -chain substitution occurs if there exists a branch such that brancht−1+τ ∩ chaint−1+τ =∆chaint−1 , and is extended by block bkt+τ
b , denote the new branch branchb =brancht−1+τ ||bkt+τ
b , such that:
Sbranchb =maxbrancht+τ ⊆mtreet+τ

Sbrancht+τ .

A chain can only be substituted by a branch if the branch is viable, andt+τ
the blocks extending them satisfies sbk (bkt+τ
b ) − sbk (bkc ) ≥ Schaint−1+τ −Sbrancht−1+τ , i.e., Sbranchb ≥ Sbranchc . The parameter τ ≥ 1 indicates that achain is substituted after being selected for τ conjunctive slots. Assuming
arbitrary distribution D for our scoring function sbk (·), the following lemmashows a loose upper bound for the probability of τ -chain substitution.
Lemma 6 Let mtreeℓ be the master-tree of time slot ℓ>τ . For any t ∈ [ℓ−τ ],given any score distribution D, there exists an accumulating function acc(·)(Equation 5.3) such that the probability of τ -chain substitution occurring isO(c−τ ) where c is a constant value given by acc(·).
Proof 6 We start from the easy case where τ = 1. By Definition 34,
chaint = chaint−1 ||bktc and branchc = chaint ||bkt+1
c . Consider a viable branchthat satisfies brancht ∩ chaint = chaint−1 and is extended by a block bkt+1
such
b
t
t+1
that branchb = branch ||bkb substitutes branchc . Then, by Equation 5.3, wehave:sbk (bktc ) ≥ sbk (bktb ),acc(t)
acc(t)
sbk (bktc ) + ·sbk (bkt+1
sbk (bktb ) + sbk (bkt+1
c ) ≤
b ).
acc(t+1)
acc(t+1)(5.6)

For simplicity, we omit the subscript in the scoring function with s(·) as weacc(t)
with c(0, 1). Then, theonly consider block scores. We also rewrite acc(t+1)
78

probability of branchc substituted by branchb , denoted by Pr[τ = 1, branchb ],equals to joint probability of events in Equation 5.6. That is, we need toestimate the following.

t+1
Pr[s(bktc )−s(bktb ) ≥ 0∧c(0, 1) · s(bktc ) − s(bktb ) + s(bkt+1c ) − s(bkb ) ≤ 0]
(5.7)
Now, we denote the random variables representing the scores of the tuple
t+1
t+1
t
t
t+1
(bktc , bktb , bkt+1
c , bkb ) with (Xc , Xb , Xc , Xb ). Furthermore, we use two
random variables Y t and Y t+1 to represent the subtraction of scores. Thatis,
Y t = Xct − Xbt = s(bktc ) − s(bktb ),t+1
Y t+1 = Xct+1 − Xbt+1 = s(bkt+1c ) − s(bkb ).

Following in our universal sampler model, (Xct , Xbt , Xct+1 , Xbt+1 ) are independent and follow the same distribution DX = D on [smin, smax]. Hence, Y t
and Y t+1 are independent, and distributed identically and symmetrically [28]on [smin−smax, smax−smin]. We denote the distribution of Y t and Y t+1 with
DY , and let fY (·) and FY (·) be the probability density function and the distribution function of DY . We can rewrite Equation 5.7 in the form of randomvariables:
Pr[(Y t ≥ 0) ∧ c(0, 1) · Y t + Y t+1 ≤ 0)].
(5.8)
Consider the event: {Y t = y ∧ Y t+1 ≤ −c(0, 1)y} for all y ∈ [0, smax−smin].
For simplicity, we rewrite r = smax−smin. By Y t is independent of Y t+1 , we
have:
Z r
Pr[Y t = y] · Pr[Y t+1 ≤ −c(0, 1)y]dy
Equation 5.8 =0
Z r Z −c(0,1)y
fY (y)fY (x)dxdy.
(5.9)
=
0

−r

Here, we consider the upper-bound of Equation 5.9 by scaling up fY (·)
with two coefficients c1 , c2 > 0 as follows.
(2≤ c1 · e−c2 ·y , if y ∈ [−r, r],fY (y)(5.10)= 0,otherwise.
Rr
Note that fY (y) is a probability density function, hence, it satisfies −r fY (y)dy =R∞
2
1. Then, for c1 , c2 , we have the estimation: −∞ c1 · e−c2 ·y dy ≥ 1, which is
c21 /c2 ≥ π −1 . The manipulation of inequality gives us:
Z ∞ Z −c(0,1)y
c1 2
1
c1 2
−y 2 −x2
−1
·tan
≤
.
Equation 5.9 ≤e ·e dxdy =2c2c(0, 1)2c2 · c(0, 1)
0−∞(5.11)
79

That is, Pr[τ = 1, branchb ] ≤ c1 2 /(2c2 · c(0, 1)) for any c1 , c2 ≥ 0 and c21 /c2 ≥acc(t)
π −1 where c(0, 1) = acc(t+1).
Now, we consider the probability of 1-chain substitution, denoted by Pr[τ =1]. Let q be the number of viable branches of slot t. Recall our universal
sampler, Q is the upper bounded of the total number of queries (regardless ofhonest or not) made in each time slot, i.e., q ≤ Q as shown in Section 5.3.2(universal sampler functionality). Then, we have:c21
Pr[τ = 1] ≤ 1 − 1 −2c2 · c(0, 1)Q.

Next, chain substitution with τ > 1 follows the same methodology ofτ = 1. Consider a branch that satisfies brancht−1+τ ∩ chaint−1+τ = chaint−1 .
Denote the distinct blocks on brancht−1+τ with bktb , . . . , bkt−1
b +τ . Comparing
them with the blocks on chaint−1+τ , and comparing the new blocks bkt+τ
inbt+τ
branchb and bkc in branchc , by rewriting Equation 5.8, the probability of
branchc substituted by branchb , denoted by Pr[τ > 1, branchb ], equals to:

!
!
i
τ
^
X
X
acc(t+j)acc(t+i)Pr · Y t+j ≥ 0  ∧· Y i ≤ 0 ,
acc(t+i)acc(t+τ)j=0
i=0i∈[τ −1](5.12)
t+i= Xct+i − Xbt+i for any i ∈ {0, . . . , τ } are independent and dis-

where Ytributed identically with DY on [smin−smax, smax−smin]. For simplicity, we∆rewrite acc(j)with c(j, i), and let c(i, i) = 1. Hence, Equation 5.12 equals to:acc(i)
Z r

Z r
···

=
0

"
−1
Πτi=0
Pr[Y t+i = yi ] · Pr Y t+τ ≤ −

rτ −1

···

=
0

rτ −1

#
c(i, τ ) · yi dy0 · · · dyτ −1

i=0−1
Z r Z − Pτi=0c(i,τ )·yi

Z r

τ −1
X

−1
Πτi=0
fY (yi ) · fY (x)dxdy0 · · · dyτ −1 .

(5.13)−r

We denote the lowerPbound of random variable Y t+i for any i ∈ [τ −1] asri . Hence ri = − i−1
j=0 c(j, i) · yj . Here, we use a small trick to scale
Equation 5.13. Note that ri is not necessarily larger than 0. We scale
yi down to −r for all iP∈ [τ −1]. Then,R the upper bound of Y t+τ satisfiesr−1
Y t+τ ≤ −c(0, τ )y0 + r · τi=1
c(i, τ ). By −r fY (yi )dyi ≤ 1 for any i ∈ [τ −1],
we have:−1
Z r Z −c(0,τ )y0 +r·Pτi=1
c(i,τ )
Equation 5.13 ≤fY (y0 )fY (x)dxdy0 .
(5.14)0−r

80

Pτ −1∆r
Finally, by setting y ′ = y0 − c(0,τ·i=1 c(i, τ ) and the bound of fY (·) given)
in Equation 5.10:

Z ∞ Z −c(0,τ )y′
c1 2
1
c2
−y ′ 2 −x2′−1e·e dxdy =Equation 5.14 ≤·tan≤ 1 ·c(0, τ ).
c2
c(0, τ )c2−∞ −∞(5.15)
That is, Pr[τ > 1, branchb ] ≤ c1 2 /c2 · c(0, τ )}, for any c1 , c2 ≥ 0 and c21 /c2 ≥acc(t)
π −1 where c(0, τ ) = acc(t+τ. Then, similar to τ = 1, we compute the prob)
ability of τ ≥ 1-chain substitution, denoted by Pr[τ > 1], as follows. Let q
be the number of viable branches in slot t. Then, by our universal sampler,q ≤ Q, where Q is the upper bound of the total number of queries (regardlessof honest or not) made in each time slot. Hence,Pr[τ > 1] ≤ 1 − 1 −c21
c2 · c(0, τ )

Q
.
c2

Combining the discussion above, we consider a constant value c > max{1, c12 },Qc2
and let acc(t) = ct . Then, Pr[τ ≥ 1] ≤ 1 − 1 − c2 ·c1−τ
is of the same orderas Q · c−τ . Note that we only use the upper bound of total queries to theuniversal sampler instead of honest queries. Finally, we can conclude that
τ -chain substitution occurs with probability O(c−τ ).
Therefore, we have the following theorem on persistence.
Theorem 4 (Persistence) Assuming at least one honest user, the protocol
Πn,δ,k,sbk ,acc among the n users, it holds that the protocol parameterized withk ≥ δ+1 satisfies persistence (Definition 31) with probability at least 1 −Ω(c−k+δ ).
Proof 7 Suppose persistence with parameter k ≥ δ + 1 is violated. It follows
that, for honest users in two different time slots ℓ1 ≤ ℓ2 holding chainℓ11 andℓ ⌈kchainℓ22 , chain11 is not the prefix of chainℓ22 . Hence, there exists blocks on′ℓ ⌈kchain11 not on chain2 ̸= ∅. Denote the first distinct block with bkℓ11 −k , thenk ′ ≥ k.
By Proposition 1, in slot ℓ2 , highest-scored branches of any slot beforeℓ2 − (δ + 1) are disclosed to all honest users. Hence, the block-tree treeℓ2 of theuser who holds chainℓ22 contains all highest-scored branches before ℓ2 − (δ + 1).
ℓ ⌈δ+1
Then, chain11∈ treeℓ2 . The chain substitution must happen in the slot
after ℓ−δ+1. Without loss of generality, we consider the situation that fori
all i ∈ {ℓ1 − k ′ , . . . , ℓ1 − (δ + 1)}, chaini1 = chaini−1
1 ||bk for all i ∈ {ℓ1 −ℓk ′ , . . . , ℓ1 − (δ + 1)}, i.e., blocks on chain 1 are selected conjunctively for k ′ −δ81

slots from ℓ−k ′ to ℓ−(δ+1). Therefore, by Lemma 6, the probability of this′(k ′ −δ)-chain substitution occurs with probability of O(c−k +δ ) which is lessthen O(c−k+δ ). Finally, we conclude that the probability of persistence withk ≥ δ + 1 is at least 1 − Ω(c−k+δ ).

5.5.2

Block-LivenessFor completeness, we show the following theorem for block-liveness.
Theorem 5 (Block-liveness) Assuming at least one honest user executes
the protocol Πn,δ,k,sbk ,acc among the n users, it holds that the protocol satisfies
block-liveness (Definition 31) unconditionally.
The proof is straightforward. Assuming the one honest user is unaware of
any other blocks, she can trivially extend her block-tree by generating blocks
locally with the bidpool and selecting the blockchain accordingly.

5.6

Discussion

The starting point of our protocol is to implement the ledger of the P2PET,
where the underlying problem of matching buy and sell bids, can be usedin conjunction with a blockchain data structure. Despite the fact that users
need to be certificated to participate in the system, we adopt a more general
execution: permissionless with static corruptions and δ-synchronous communication network. Moreover, we assume the existence of a globally synchronized clock, which, at first glance, is a constrained setting. However, it
can easily be implemented by the secure hardware provided by the P2PET
system.
One component of our construction is the scoring function for blocks,
i.e., sbk , and the BAP-based PoW scheme (BAP-based PoW), implementing
a novel consensus protocol. The purpose of the scoring function is to provide
a “notion of optimal” to the system. Among all the blocks available ineach time slot, it chooses the “most optimal” choice to extend a (redefined)
blockchain data structure. At the same time, it is used as accounting forthe auction market underpinning the system. Instantiated with a concrete
function, the adversary, once given the description for the scoring function,
could adapt and get an advantage in constructing the next block. Thus, its
adaptability, in fact, helps the optimality of the overall protocol. We advocatethat the study of more concrete constructions of sbk is of independent interest
and out of the scope of this chapter.

82

In our analysis, the competitive PoX scheme is replaced by a universal
sampler which samples blocks and corresponding scores from score space ineach time slot. This, in fact, simplifies our analysis without the loss of thewhole motivation of our construction. We remark that, although it is anadvanced random oracle, it is practical [32], since it can be easily used inpractice with a random function.
Considering the universal sampler in our protocol execution setting, we
showed that our protocol has persistence and block-liveness when at least
one user is honest. We recall that block-liveness is a variant of the standard
security liveness property. This variant is necessary and meaningful in our
setting, given that in every time slot all honest participants issue candidate
blocks. Thus, the property is that one block among them is always chosenfrom all candidates. Needless to say, by fulfilling the block-liveness property,
we also obtain the regular liveness property, thereby constructing a fully
secure system.
Finally, we remark that we did not thoroughly investigate potential incentive frameworks for our proposed system in the presence of a rational
adversary. This topic seem to be out of the scope of the current chapter
despite its importance. In particular, the study of the overall behavior of
the system in the presence of such adversary. We leave this topic for future
works.

83

Bibliography[1] Akhras, R., El-Hajj, W., Majdalani, M., Hajj, H.M., Jabr,
R.A., Shaban, K.B.:
Securing smart grid communication using ethereum smart contracts. In:
16th International Wireless Communications and Mobile Computing Conference, IWCMC
2020, Limassol, Cyprus, June 15-19, 2020. pp. 1672–1678. IEEE
(2020). https://doi.org/10.1109/IWCMC48107.2020.9148345, https://doi.org/10.1109/IWCMC48107.2020.9148345[2] Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt
is maximally memory-hard. In: Coron, J., Nielsen, J.B. (eds.) Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Paris, France, April 30 - May 4, 2017, Proceedings,
Part III. Lecture Notes in Computer Science, vol. 10212, pp. 33–
62 (2017). https://doi.org/10.1007/978-3-319-56617-7 2, https://doi.
org/10.1007/978-3-319-56617-7_2[3] Badertscher, C., Garay, J.A., Maurer, U., Tschudi, D., Zikas, V.: But
why does it work? A rational protocol design treatment of bitcoin. In:
Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT
2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May
3, 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol.
10821, pp. 34–65. Springer (2018). https://doi.org/10.1007/978-3-31978375-8 2, https://doi.org/10.1007/978-3-319-78375-8_2[4] Badertscher, C., Lu, Y., Zikas, V.: A rational protocol treatment of
51% attacks. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings,
Part III. Lecture Notes in Computer Science, vol. 12827, pp. 3–32.
Springer (2021). https://doi.org/10.1007/978-3-030-84252-9 1, https://doi.org/10.1007/978-3-030-84252-9_1
84

[5] Baldominos, A., Saez, Y.: Coin.ai: A proof-of-useful-work scheme
for blockchain-based distributed deep learning. Entropy 21(8),723 (2019). https://doi.org/10.3390/e21080723, https://doi.org/10.
3390/e21080723[6] Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work fromworst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) Advancesin Cryptology - CRYPTO 2018 - 38th Annual International Cryptology
Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings,
Part I. Lecture Notes in Computer Science, vol. 10991, pp. 789–819.
Springer (2018). https://doi.org/10.1007/978-3-319-96884-1 26, https://doi.org/10.1007/978-3-319-96884-1_26[7] Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13, 281–305 (2012), http://dl.acm.org/
citation.cfm?id=2188395[8] Biryukov, A., Perrin, L.: Symmetrically and asymmetrically hard
cryptography. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the
Theory and Applications of Cryptology and Information Security,
Hong Kong, China, December 3-7, 2017, Proceedings, Part III. Lecture Notes in Computer Science, vol. 10626, pp. 417–445. Springer(2017). https://doi.org/10.1007/978-3-319-70700-6 15, https://doi.
org/10.1007/978-3-319-70700-6_15[9] Blocki, J., Zhou, H.: Designing proof of human-work puzzles forcryptocurrency and beyond. In: Hirt, M., Smith, A.D. (eds.) Theory of Cryptography - 14th International Conference, TCC 2016B, Beijing, China, October 31 - November 3, 2016, Proceedings,
Part II. Lecture Notes in Computer Science, vol. 9986, pp. 517–
546 (2016). https://doi.org/10.1007/978-3-662-53644-5 20, https://doi.org/10.1007/978-3-662-53644-5_20[10] Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings,
Part I. Lecture Notes in Computer Science, vol. 10991, pp. 757–788.
Springer (2018). https://doi.org/10.1007/978-3-319-96884-1 25, https://doi.org/10.1007/978-3-319-96884-1_25

85

[11] Brown, D.R.L.: Breaking RSA may be as difficult as factoring. J. Cryptol. 29(1), 220–241 (2016). https://doi.org/10.1007/s00145-014-9192-y,https://doi.org/10.1007/s00145-014-9192-y[12] Canetti, R.: Universally composable security: A new paradigm
for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001,
Las Vegas, Nevada, USA. pp. 136–145. IEEE Computer Society(2001). https://doi.org/10.1109/SFCS.2001.959888, https://doi.org/
10.1109/SFCS.2001.959888[13] Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Seltzer,
M.I., Leach, P.J. (eds.) Proceedings of the Third USENIX Symposium
on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999. pp. 173–186. USENIX
Association (1999), https://dl.acm.org/citation.cfm?id=296824[14] Chaum, D.: Blind signatures for untraceable payments. In: Chaum,D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology:
Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982. pp. 199–203. Plenum Press, New York (1982).
https://doi.org/10.1007/978-1-4757-0602-4 18, https://doi.org/10.
1007/978-1-4757-0602-4_18[15] Chaum, D., Fiat, A., Naor, M.: Untraceable electronic cash. In: Goldwasser, S. (ed.) Advances in Cryptology - CRYPTO ’88, 8th Annual
International Cryptology Conference, Santa Barbara, California, USA,
August 21-25, 1988, Proceedings. Lecture Notes in Computer Science,
vol. 403, pp. 319–327. Springer (1988). https://doi.org/10.1007/0-38734799-2 25, https://doi.org/10.1007/0-387-34799-2_25[16] Chenli, C., Li, B., Jung, T.: Dlchain: Blockchain with deep learning as proof-of-useful-work. In: Ferreira, J.E., Palanisamy, B., Ye,
K., Kantamneni, S., Zhang, L. (eds.) Services - SERVICES 2020 16th World Congress, Held as Part of the Services Conference Federation, SCF 2020, Honolulu, HI, USA, September 18-20, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12411, pp. 43–60.
Springer (2020). https://doi.org/10.1007/978-3-030-59595-1 4, https://doi.org/10.1007/978-3-030-59595-1_4[17] Chenli, C., Li, B., Shi, Y., Jung, T.:
Energy-recycling
blockchain with proof-of-deep-learning. In: IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2019, Seoul,86

Korea (South), May 14-17, 2019. pp. 19–23. IEEE (2019).
https://doi.org/10.1109/BLOC.2019.8751419, https://doi.org/10.
1109/BLOC.2019.8751419[18] Coelho, F.: An (almost) constant-effort solution-verification proof-ofwork protocol based on merkle trees. In: Vaudenay, S. (ed.) Progressin Cryptology - AFRICACRYPT 2008, First International Conference
on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5023, pp. 80–93.
Springer (2008). https://doi.org/10.1007/978-3-540-68164-9 6, https://doi.org/10.1007/978-3-540-68164-9_6[19] David, B., Gazi, P., Kiayias, A., Russell, A.: Ouroboros praos:
An adaptively-secure, semi-synchronous proof-of-stake blockchain. In:
Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT
2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May
3, 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol.
10821, pp. 66–98. Springer (2018). https://doi.org/10.1007/978-3-31978375-8 3, https://doi.org/10.1007/978-3-319-78375-8_3[20] Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In:
Brickell, E.F. (ed.) Advances in Cryptology - CRYPTO ’92, 12th Annual
International Cryptology Conference, Santa Barbara, California, USA,
August 16-20, 1992, Proceedings. Lecture Notes in Computer Science,
vol. 740, pp. 139–147. Springer (1992). https://doi.org/10.1007/3-54048071-4 10, https://doi.org/10.1007/3-540-48071-4_10[21] Dyer, M.E., Frieze, A.M.: Probabilistic analysis of the generalised assignment problem. Math. Program. 55, 169–181 (1992).
https://doi.org/10.1007/BF01581197,
https://doi.org/10.1007/
BF01581197[22] Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs ofspace. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa
Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9216, pp. 585–605. Springer(2015). https://doi.org/10.1007/978-3-662-48000-7 29, https://doi.
org/10.1007/978-3-662-48000-7_29[23] Fitzi, M., Kiayias, A., Panagiotakos, G., Russell, A.: Ofelimos: Combinatorial optimization via proof-of-useful-work - A provably secure87blockchain protocol. In: Dodis, Y., Shrimpton, T. (eds.) Advances in
Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology
Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18,
2022, Proceedings, Part II. Lecture Notes in Computer Science, vol.
13508, pp. 339–369. Springer (2022). https://doi.org/10.1007/978-3-03115979-4 12, https://doi.org/10.1007/978-3-031-15979-4_12[24] Foundation, C.: Cardano Hub. https://www.cardano.org/ (2023),[Online; accessed 26-May-2023][25] Garay, J.A., Katz, J., Maurer, U., Tackmann, B., Zikas, V.:
Rational protocol design: Cryptography against incentive-driven
adversaries. In: 54th Annual IEEE Symposium on Foundationsof Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. pp. 648–657. IEEE Computer Society (2013).
https://doi.org/10.1109/FOCS.2013.75, https://doi.org/10.1109/
FOCS.2013.75[26] Garay, J.A., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: Analysis and applications. In: Oswald, E., Fischlin, M. (eds.)
Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings,
Part II. Lecture Notes in Computer Science, vol. 9057, pp. 281–310.
Springer (2015). https://doi.org/10.1007/978-3-662-46803-6 10, https://doi.org/10.1007/978-3-662-46803-6_10[27] Garay, J.A., Kiayias, A., Leonardos, N., Panagiotakos, G.: Bootstrapping the blockchain, with applications to consensus and fast PKI setup.
In: Abdalla, M., Dahab, R. (eds.) Public-Key Cryptography - PKC
2018 - 21st IACR International Conference on Practice and Theory of
Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018,
Proceedings, Part II. Lecture Notes in Computer Science, vol. 10770,
pp. 465–495. Springer (2018). https://doi.org/10.1007/978-3-319-765815 16, https://doi.org/10.1007/978-3-319-76581-5_16[28] George E.P. Box, G.C.T.: Bayesian Assessment of Assumptions 1. Effectof Non-Normality on Inferences about a Population Mean with Generalizations, chap. 3, pp. 149–202. John Wiley and Sons, Ltd (1992).
https://doi.org/https://doi.org/10.1002/9781118033197.ch3, https://
onlinelibrary.wiley.com/doi/abs/10.1002/9781118033197.ch3

88

[29] Goldreich, O.:
The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press (2001).
https://doi.org/10.1017/CBO9780511546891,
http://www.wisdom.
weizmann.ac.il/%7Eoded/foc-vol1.html[30] Górski, T., Bednarski, J.: Modeling of smart contracts in blockchain
solution for renewable energy grid. In: Moreno-Dı́az, R., Pichler,F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory EUROCAST 2019 - 17th International Conference, Las Palmas deGran Canaria, Spain, February 17-22, 2019, Revised Selected Papers,
Part I. Lecture Notes in Computer Science, vol. 12013, pp. 507–514.
Springer (2019). https://doi.org/10.1007/978-3-030-45093-9 61, https://doi.org/10.1007/978-3-030-45093-9_61[31] Hellman,
M.E.:
A cryptanalytic time-memory trade-off.
IEEE Trans. Information Theory 26(4),
401–406 (1980).
https://doi.org/10.1109/TIT.1980.1056220,
https://doi.org/10.
1109/TIT.1980.1056220[32] Hofheinz, D., Jager, T., Khurana, D., Sahai, A., Waters, B., Zhandry,M.: How to generate and use universal samplers. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology
and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10032, pp.
715–744 (2016). https://doi.org/10.1007/978-3-662-53890-6 24, https://doi.org/10.1007/978-3-662-53890-6_24[33] Kamp, S.H., Magri, B., Matt, C., Nielsen, J.B., Thomsen, S.E.,
Tschudi, D.: Weight-based nakamoto-style blockchains. In: Longa,
P., Ràfols, C. (eds.) Progress in Cryptology - LATINCRYPT 2021
- 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6-8, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12912, pp. 299–319.
Springer (2021). https://doi.org/10.1007/978-3-030-88238-9 15, https://doi.org/10.1007/978-3-030-88238-9_15[34] Katz, J., Loss, J., Xu, J.: On the security of time-lock puzzles
and timed commitments. In: Pass, R., Pietrzak, K. (eds.) Theory of Cryptography - 18th International Conference, TCC 2020,
Durham, NC, USA, November 16-19, 2020, Proceedings, Part III. Lecture Notes in Computer Science, vol. 12552, pp. 390–413. Springer89

(2020). https://doi.org/10.1007/978-3-030-64381-2 14, https://doi.
org/10.1007/978-3-030-64381-2_14[35] Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: A provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham,H. (eds.) Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August
20-24, 2017, Proceedings, Part I. Lecture Notes in Computer Science,
vol. 10401, pp. 357–388. Springer (2017). https://doi.org/10.1007/978-3319-63688-7 12, https://doi.org/10.1007/978-3-319-63688-7_12[36] Kirli, D., Couraud, B., Robu, V., Salgado-Bravo, M., Norbu, S., Andoni,M., Antonopoulos, I., Negrete-Pincetic, M., Flynn, D., Kiprakis, A.:
Smart contracts in energy systems: A systematic review of fundamental
approaches and implementations. Renewable and Sustainable Energy
Reviews 158, 112013 (2022)[37] Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401(1982). https://doi.org/10.1145/357172.357176, https://doi.org/10.
1145/357172.357176[38] Lan, Y., Liu, Y., Li, B., Miao, C.: Proof of learning (pole): Empowering machine learning with consensus building on blockchains (demo).
In: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021,
Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advancesin Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021.
pp. 16063–16066. AAAI Press (2021), https://ojs.aaai.org/index.
php/AAAI/article/view/18013[39] Li, B., Chenli, C., Xu, X., Jung, T., Shi, Y.: Exploiting computation power of blockchain for biomedical image segmentation.
In: IEEE Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2019, Long Beach, CA,
USA, June 16-20, 2019. pp. 2802–2811. Computer Vision Foundation / IEEE (2019). https://doi.org/10.1109/CVPRW.2019.00339,
http://openaccess.thecvf.com/content_CVPRW_2019/html/
BCMCVAI/Li_Exploiting_Computation_Power_of_Blockchain_
for_Biomedical_Image_Segmentation_CVPRW_2019_paper.html

90

[40] Lihu, A., Du, J., Barjaktarevic, I., Gerzanics, P., Harvilla, M.: A
proof of useful work for artificial intelligence on the blockchain. CoRR
abs/2001.09244 (2020), https://arxiv.org/abs/2001.09244[41] Luu, L., Chu, D., Olickel, H., Saxena, P., Hobor, A.: Making smart contracts smarter. In: Weippl, E.R., Katzenbeisser, S.,
Kruegel, C., Myers, A.C., Halevi, S. (eds.) Proceedings of the 2016
ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016. pp. 254–269. ACM(2016). https://doi.org/10.1145/2976749.2978309, https://doi.org/
10.1145/2976749.2978309[42] Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008),
http://bitcoin.org/bitcoin.pdf[43] Park, J.S., Lim, B.H., Lee, Y.: A lagrangian dual-based branch-andbound algorithm for the generalized multi-assignment problem. Manage.
Sci. 44(12), 271–275 (dec 1998)[44] Pass, R., Shi, E.: Fruitchains: A fair blockchain. In: Schiller,
E.M., Schwarzmann, A.A. (eds.) Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017,
Washington, DC, USA, July 25-27, 2017. pp. 315–324. ACM(2017). https://doi.org/10.1145/3087801.3087809, https://doi.org/
10.1145/3087801.3087809[45] Pass, R., Shi, E.: Thunderella: Blockchains with optimistic instant confirmation. In: Nielsen, J.B., Rijmen, V. (eds.) Advancesin Cryptology - EUROCRYPT 2018 - 37th Annual International
Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings,
Part II. Lecture Notes in Computer Science, vol. 10821, pp. 3–33.
Springer (2018). https://doi.org/10.1007/978-3-319-78375-8 1, https://doi.org/10.1007/978-3-319-78375-8_1[46] Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (ed.)
10th Innovations in Theoretical Computer Science Conference, ITCS
2019, January 10-12, 2019, San Diego, California, USA. LIPIcs,
vol. 124, pp. 60:1–60:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ITCS.2019.60, https://doi.org/10.4230/LIPIcs.ITCS.2019.60[47] Pomerance, C., Erdös, P.: A tale of two sieves (1998), https://api.
semanticscholar.org/CorpusID:1695797
91

[48] Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timedrelease crypto. Tech. rep., USA (1996)[49] Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital
signatures and public-key cryptosystems. Commun. ACM 21(2), 120–
126 (1978). https://doi.org/10.1145/359340.359342, https://doi.org/
10.1145/359340.359342[50] Robertson, H.: Ethereum transaction fees are running sky-high. (2021),“https://markets.businessinsider.com/news/currencies/ethereumtransaction-gas-fees-high-solana-avalanche-cardano-crypto-blockchain2021-12”[51] Su, X., Défago, X., Larangeira, M., Mori, K., Oda, T., Okumura,Y., Tamura, Y., Tanaka, K.: Peer-to-peer energy trading meetsblockchain: Consensus via score-based bid assignment. Cryptology
ePrint Archive, Paper 2022/1471 (2022), https://eprint.iacr.org/
2022/1471, https://eprint.iacr.org/2022/1471[52] Su, X., Larangeira, M., Tanaka, K.: How to prove work: With time or
memory. In: IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2021, Sydney, Australia, May 3-6, 2021. pp. 1–3. IEEE
(2021). https://doi.org/10.1109/ICBC51069.2021.9461131, https://doi.org/10.1109/ICBC51069.2021.9461131[53] Su, X., Larangeira, M., Tanaka, K.: Provably secure blockchain protocols from distributed proof-of-deep-learning. In: Li, S., Manulis, M.,
Miyaji, A. (eds.) Network and System Security - 17th International
Conference, NSS 2023, Canterbury, UK, August 14-16, 2023, Proceedings. Lecture Notes in Computer Science, vol. 13983, pp. 114–136.
Springer (2023). https://doi.org/10.1007/978-3-031-39828-5 7, https://doi.org/10.1007/978-3-031-39828-5_7[54] Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2019 - 38th
Annual International Conference on the Theory and Applications of
Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III. Lecture Notes in Computer Science, vol. 11478,
pp. 379–407. Springer (2019). https://doi.org/10.1007/978-3-030-176594 13, https://doi.org/10.1007/978-3-030-17659-4_13[55] Wood, G.: Ethereum yellow paper (2014)92