Quick Notiﬁcation of Block Generation
Using Bloom Filter in a Blockchain
Tsuyoshi Hasegawa

Akira Sakurai

Kazuyuki Shudo

Kyoto University
Kyoto, JapanTokyo Institute of Technology
Tokyo, Japan

Kyoto University
Kyoto, Japan

Abstract—Forks in a blockchain sacriﬁce security. In thispaper, we propose a protocol for quickly propagating block
generation notiﬁcations in the blockchain network quickly to
reduce the fork rate. Block generation notiﬁcations contain a
Bloom ﬁlter that represents transactions in the generated block.
Thus, when nodes receive a block generation notiﬁcation, they canstart mining the next block. In experiments in which a simulator
is used, we compared the propagation time of a block generation
notiﬁcation with that of a block in the existing protocol. As aresult, the propagation time of the 50 %ile is 41.1 % of an
existing protocol, the 90 %ile is 39.2 % of the existing protocol,and the fork rate calculated from the average propagation timeis 40.8 % of the existing protocol.
Index Terms—blockchain, block propagation, fork rate

I. I NTRODUCTION
Blockchain is a decentralized system that is difﬁcult totamper with and utilized on a cryptocurrency basis. Currently,
a disadvantage of blockchains is that they can only approve
few transactions in a unit of time. Speciﬁcally, the performance of Bitcoin [1] transaction approval was initially only
7 TPS (transactions / sec). If the block generation interval isshortened to resolve the lack of TPS, the blockchain security
is sacriﬁced [2]. The solution increases the possibility of a
new block being generated by a node that has not received
the generated block and divergence in the blockchain. The
divergence in the blockchain is referred to as a fork and the rateof fork occurrence is referred to as a fork rate. By shortening
the block propagation time, the fork rate can be reduced andthe block generation interval can be shortened.
We propose a protocol that quickly propagates a block
generation notiﬁcation, which informs nodes that a block has
been generated. We assume blockchains in which a fork canoccur because all nodes probabilistically generate blocks.
In Section II, we show related research on block propagation
between nodes. In Section III, we describe the proposed
protocol. In Section IV, we show the results of simulation
experiments. In Section V, we summarize our research.

Block Relay (CBR) [3] and Graphene [4], which are efﬁcient
block transfer protocols between nodes.
A. Legacy Protocol
In the legacy protocol, a block itself is transmitted between
nodes. First, the block sender node sends an inventory (inv)message that informs which block will be transmitted to areceiver node, and the receiver sends a getdata message
if the block is needed. The sender transmits the block itself
when receiving the getdata message. The size of the block
is limited by 1 MiB [5].
B. Compact Block Relay
In the Compact Block Relay (CBR), a compact block thatconsists of a header and set of transaction ids is sent insteadof a full block. Transactions have been sent to the blockchain
network and nodes collect them in their transaction pool(mempool), thus, the node receiving the compact block canreconstruct the full block using the set of transaction ids. If
the receiver does not have all transactions in the full block,the node request lacks transactions for the sender. The sizeof the compact block is smaller than that of the full block,approximately 18 KiB [6], thus it can be transmitted at a fasterrate than the full block.

II. R ELATED R ESEARCH

C. Graphene
Graphene is a protocol that uses two probabilistic data structures, the Bloom ﬁlter [7] and Invertible Bloom Lookup Table(IBLT) [8], to efﬁciently encode the transactions containedin a block. The sender transmits a Bloom ﬁlter S and IBLTI that encode the transactions in the block, and the receivertries to decode them. If the receiver succeeds in decoding, thenode can know all transactions in the block. In the case of adecoding failure, the receiver sends another Bloom ﬁlter R,
and the sender sends another IBLT J and expectes to lacktransaction set C. Then, the receiver tries to decode IBLT
J. If the second attempt also fails, a normal block transfer
is performed. In Graphene, the size of the data transferred
between nodes is less than the CBR in total.

In the blockchain, the block consists of a header and a setof transactions. Nodes mined the block, and if they succeeded,transmitted the block to their neighbor nodes. For this node-tonode transfer protocol, ﬁrst, we describe the normal node-tonode protocol (legacy protocol). Second, we describe Compact

III. P ROPOSED P ROTOCOLThis section describes the proposed protocol to reduce thefork rate in blockchains.
In this paper, we propose a protocol to quickly notify
the nodes in the blockchain network that a block has been

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023

TABLE I
S TRUCTURE OF A BLOCK GENERATION NOTIFICATION ( BLOCK HEADER ).
Element
Transaction ﬁlter

Prerequisite block indicesVersionPrevious Block Hash
Merkle Root
Timestamp
Difﬁculty Target
Nonce

Description
Bloom ﬁlter with UTXOs utilized intransactions in the generated block as
an element
Indices of prerequisite blocks at generated block
Software / protocol version number
Hash of the parent block
Root hash of the Merkle Tree for alltransactions in the block
Generation time of the block
Difﬁculty of proof of work during
block generation
Counters used in proof of work

generated. We refer to this notiﬁcation as a block generation
notiﬁcation. The block generation notiﬁcation includes information about the generated block, and the nodes that receive
the notiﬁcation start the next mining based on the notiﬁcation.
The rapid propagation of block generation notiﬁcations and thenotion that the nodes that receive them start the next mining
with the block corresponding to the notiﬁcation as its parent
reduces the fork rate. Hence, a space-efﬁcient data structure,
the Bloom ﬁlter, is selected to represent the information of
the generated block and is included in the block generation
notiﬁcation.
Table I shows the structure of a block generation notiﬁcation. In the proposed protocol, the block header is extended to
be a block generation notiﬁcation. The structure is similar to
the Bitcoin header, with the exception that a transaction ﬁlter
and prerequisite block indices are added. The miner mines
using the extended header and propagates the header as a
block generation notiﬁcation when the block is successfully
generated. In this way, the node receiving the block generation
notiﬁcation can check the metadata of the generated block andconﬁrm that the creator of the block generation notiﬁcation has
indeed successfully mined the proof of work. The transaction
ﬁlter is discussed in more detail in Subsection III-A, and theprerequisite blocks are discussed in more detail in Subsection
III-B. Figure 1 shows a summary of the proposed protocol.
A possible method for implementing block generation notiﬁcations in Bitcoin is to include them in transactions madeby miners and propagate them to the blockchain network.
A. Transaction Filter
The transaction ﬁlter Fh is a Bloom ﬁlter whose elements
are the UTXOs consumed by the transactions in the generated
block Bh . A node that receives a block generation notiﬁcation
Nh determines the UTXOs consumed by each transaction in
its own transaction pool using transaction ﬁlter Fh . If all
consuming UTXOs for each transaction are negative, the node
determines that it is not included in the generated block Bhand includes it in the next mining.
Bloom ﬁlters have the potential for false positives. Ways toaddress false positives are discussed in Subsection III-B.

Algorithm 1 Validation of block generation notiﬁcation Nh
1: Validate one previous block generation notiﬁcation Nh−1 .
2: Validate blocks activated by Nh .
3: Validate each header element of Nh (no validation of
the Merkle root, otherwise the same as Bitcoin header
validation).

B. Activation of Blocks
Bloom ﬁlters have the problem of false positives, whichmeans that transactions that are false positives by a certaintransaction ﬁlter can no longer be included in the mining. A
transaction that is a false positive by a transaction ﬁlter Fh ofa certain height h can be determined to be a false positiveby checking transactions at the corresponding same heightblock Bh . The transaction ﬁlter Fh can be inactivated by block
Bh . Ensuring the existence of block Bh and inactivating thecorresponding transaction ﬁlter Fh is referred to as enabling
block Bh . Activating a block held by each node at mining
inactivates the corresponding transaction ﬁlter and solves the
problem of false positives.
However, the block propagation status is not the same foreach node. When verifying block Bh , each node needs to know
which blocks were activated when the block Bh was generated.
Hence, the proposed method is to include in the block generation notiﬁcation the information of the blocks that each node
has received and for which the corresponding transaction ﬁlter
has been inactivated at mining. This information is referred toas the prerequisite block indices. By using the prerequisite
block indices in block generation notiﬁcation Nh of heighth and activating these blocks, the status of the active blocks
at height h can be identiﬁed for all nodes. Conversely, theblock is unconﬁrmed until it is activated by a block generation
notiﬁcation.
A possible attack by malicious nodes is to propagate only
block generation notiﬁcation Nh and not block Bh uponsuccessful mining of height h. By this attack, the corresponding transaction ﬁlter Fh cannot be inactivated because block
Bh cannot be propagated to ensure that transactions that are
positive due to Fh can not be included in the mining. To
counter this attack, a time limit is set on block activation.
Speciﬁcally, if block Bh is not activated for b consecutive
blocks, i.e., if block Bh is not included in the prerequisite
block information of a block generation notiﬁcation of heighth + 1 to h + b, the transaction ﬁlter Fh is disabled and Bhcannot be activated thereafter. Since block Bh can no longer
be activated, all transactions that were positive by transaction
ﬁlter Fh are included in the mining. Subsection III-F describes
how the system-wide parameter b is determined.
C. Validation of Block Generation Notiﬁcation
Algorithm 1 shows the algorithm for validation of theblock generation notiﬁcation, which is performed by the node
receiving block generation notiﬁcation Nh of height h.
In the validation of block generation notiﬁcation Nh , ﬁrst,
one previous block generation notiﬁcation Nh−1 is checked

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023

Block Height

Block Generation
Notification (BGN)

Block

h-b

h-1

h

h+1

h+n

Headerelements

Headerelements

Headerelements

Headerelements

Headerelements

Transaction
filterTransaction
filterTransaction
filterTransaction
filterTransaction
filterPrerequisite
Blocksindices

Prerequisite
Blocksindices

Prerequisite
Blocksindices

Prerequisite
Blocksindices

Prerequisite
Blocksindices

Header(BGN)

Header(BGN)

Header(BGN)

Header(BGN)

Header
(BGN)

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..
.

.

validate

activate

Headerelements
Bitcoin’s
header elements

Tx
inactivetransaction.

Txactivetransaction.

Txunconfirmed
transaction

Transaction
filterinactive
filter.
Transaction
filteractivefilterFig. 1. Summary of the proposed protocol.

Algorithm 2 Validation of block Bh
1: Block generation notiﬁcation Nh id validated.
2: All transactions in block Bh are checked to ensure thatthey pass through the integration ﬁlter Ih .
3: Each transaction in block Bh id validated.
Algorithm 3 Creation of integration ﬁlter Ih
1: An integration ﬁlter Ih = an empty Bloom ﬁlter that is a
bit array, all set to 0.
2: r = h
3: while r ≥ 0 do
4:
if Fr is not inactivated then5:
Th = Unite(Th , Fr ) ▷ U nite is a function thattakes the logical OR of each bit.
6:
end if7:
r =r−18: end while
9: return Th

to ensure that it has been validated. Thus, to validate Nh ,it is recursively required that all previous block generation
notiﬁcations have been validated. Second, the prerequisite
block indices in Nh are checked, and the activated blocks
are validated. If the node receiving Nh has not received theseblocks, the node requests them for the Nh sender. Last, eachheader element of Nh are validated. In this validation, theMerkle root is not validated because block Bh is required forthis validation; otherwise, the same is true for the validationof the Bitcoin header. Block Bh is not validated in the Nhvalidation.

D. Validation of Block
Algorithm 2 shows the algorithm for validation of block Bhof height h. The node receiving a block generation notiﬁcation
higher than height h activating block Bh validates block Bh .
In the validation of block Bh , ﬁrst, the corresponding block
generation notiﬁcation Nh is validated. Second, the next stepis to check that all transactions in block Bh pass through the
integration ﬁlter Ih . The integration ﬁlter is the integration of
the active transaction ﬁlters at height h, and the algorithm forcreating the integrated ﬁlter is given by Algorithm 3. Last,each transaction in block Bh is validated. The validation of
one previous block Bh−1 is not performed because in the
proposed protocol, blocks are activated by a block generation
notiﬁcation, and the prerequisite block when block Bh was
generated is indicated in block generation notiﬁcation Nh andis validated in the ﬁrst Nh veriﬁcation (Algorithm 1).
E. Mining
Algorithm 4 shows the algorithm by which the node receives
block generation notiﬁcation Nh and starts the next mining.
When ntheode that received a block generation notiﬁcation
Nh starts the next mining, it validates the received Nh (Algorithm 1). Then, if any block Bi up to the previous b blocks
already received has not yet been activated, the correspondingtransaction ﬁlter Fi is inactivated, and the prerequisite blockindices are updated (there can be multiple blocks to be
activated). Subsequently, an integrated ﬁlter Ih is generated(Algorithm 3). The generated integrated ﬁlter Ih is then used todetermine transactions in the transaction pool of the receiver.
The UTXOs consumed by each transaction are determined by
the integrated ﬁlter Ih and at least one positive transaction
is excluded from mining. From the remaining transactions,

Algorithm 4 Mining
1: Block generation notiﬁcation Nh is validated.
2: Transaction ﬁlters corresponding to blocks that have notbeen activated up to b blocks already received are inactivated.
3: References of blocks that have not been activated up to b
blocks already received are added to the prerequisite blockindices.
4: An integrated ﬁlter Ih is created.
5: Transactions in the transaction pool are determined by Ih .
6: Transactions included in the next block Bh+1 are determined.
7: A transaction ﬁlter Fh+1 is created.
8: The transaction ﬁlter Fh+1 and prerequisite block indicesin the block header are included, and then mining isstarted.
9: Mining success.
10: The block header of the generated block Bh+1 is propagated as a block generation notiﬁcation.
11: Block Bh+1 is propagated.

Fig. 2. Size of the Bloom ﬁlter when r is varied.

For the ratio of false positive transactions to the total numberof transactions that should be available for mining to be lessthan or equal to r, the inequality satisﬁed by f ′ isb∑f ′ (1 − f ′ )k−1 ≤ r.

(2)

k=1

a new transaction ﬁlter Fh+1 is created to determine thetransactions to be included in the next block Bh+1 . Mining isthen started by including the transaction ﬁlter and prerequisite
block indices in the extended block header. If the mining is
successful, the block header of the generated block Bh+1 is
propagated as block generation notiﬁcation Nh+1 and thenblock Bh+1 is propagated.
F. Size of a transaction ﬁlter
We consider the size of a transaction ﬁlter included in theblock generation notiﬁcation. The transaction ﬁlter should be
as small as possible to minimize the propagation time of theblock generation notiﬁcation.
The transaction ﬁlter Fh is inactivated if the corresponding
block Bh is not activated for b blocks (Subsection III-B).
Hence, the number of active transaction ﬁlters is highest
when b consecutive blocks have not been activated by block
generation notiﬁcations, and the number is b. In this paper,
we set the false positive rate of the Bloom ﬁlter so that theratio of the highest number of false positive transactions to
the total number of transactions that have not been includedin the generated block and should be available for mining isless than or equal to the parameter r. The size of the smallest
Bloom ﬁlter is − nlnln2 2f bits when the number of ﬁlter elements
is n and the false positive rate is f .
The average number of UTXOs consumed by a transactionis three [9]. We use this ﬁgure to determine the size of theBloom ﬁlter. When at least one of the consuming UTXOs
is positive, the transaction is not included in the next mining.
Therefore, the probability f ′ of an originally usable transaction
becoming a false positive transaction isf ′ = 1 − (1 − f )3 ,where f is the false positive rate of the Bloom ﬁlter.

(1)

Substituting Equation (1) into inequality (2) and rearranging,
we obtain1

f ≤ 1 − (1 − r) 3b .

(3)

The false positive rate and size in a Bloom ﬁlter is a trade-off.
Thus, the false positive rate of the Bloom ﬁlter is maximized
to be as small as possible. Thus, the false positive rate of theBloom ﬁlter is1

f = 1 − (1 − r) 3b .

(4)

We describe parameter b. From Equation (4), f decreases
as b increases when r is ﬁxed. Since the size of a Bloom
ﬁlter increases as the false positive rate decreases, the size
increases as b increases. Therefore, to make the size as small
as possible, we obtain the smallest acceptable b. Malicious
nodes can inactivate the b + 1 previous block by creating
blocks without activating this block b consecutive times. If
b is small, the possibility of the success of such an attack
increases. We set b such that the possibility that malicious
nodes succeed in generating block b consecutive times is lower
than the possibility of a successful double-spending attack. The
possibility that malicious nodes succeed in generating blocks
b consecutive times is hb when h is the hash rate of malicious
nodes. With reference to the possibility of a successful doublespending attack depending on the hash rate by Chaudhary et
al. [10], b = 4 is sufﬁcient.
Figure 2 shows the size of the transaction ﬁlter when r isvaried, b = 4, and the number of transactions included in a
block is 2000. The transaction ﬁlter size is 7.181 KiB whenr = 0.1, and 4.391 KiB when r = 0.5.
The size of the block generation notiﬁcation is sufﬁciently
small; thus, the proposed protocol does not use inv messages
when sending block generation notiﬁcations.

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023

G. Impact of attacks and countermeasures
Possible attacks on the proposed method, their impact andcountermeasures are described.
1) Attacks that do not propagate blocks: As described in
Sections III-B and III-F, when a block is generated, there is apossible attack where only the block generation notiﬁcation
is propagated and the block is not propagated. To address
this attack, blocks that have not been activated for b blocks
inactivate the corresponding transaction ﬁlter (Section III-B).
However, since the corresponding transaction ﬁlter is notinactivated until b blocks have been accumulated, there is aproblem that for this period the transactions made positive bythat transaction ﬁlter cannot be included in the mining. We
propose a method for setting the size of the transaction ﬁlter
so that the number of worst-case false positive transactions is
below a certain percentage.
2) Attacks that do not activate blocks: As described in
Section III-F, a possible attack occres when malicious nodes
inactivate the b + 1 previous block by creating blocks without
activating this block b consecutive times. Since the successprobability of this attack decreases as the parameter b increases, in this paper the value of the parameter b is set suchthat the success probability of this attack is lower than that ofthe double-spending attack.
3) Attacks that keep certain transactions positive: It is
possible to prevent certain transactions from being used bycreating a transaction ﬁlter such that certain transactions are
positive when malicious nodes succeed in mining. This step
could lead to an attack whereby successful mining occurs
again before the b blocks stack up, keeping certain transactions
positive and preventing them from being included in the block.
This attack has a trade-off with the attack in which theblocks above are not propagated, as the probability of successincreases as b increases.
4) Attacks that propagate a malformed transaction ﬁlter:
By propagating a malformed transaction ﬁlter such that all
UTXOs are positive, all transactions become unusable. To address this attack, a possible approach is to limit the percentage
of bits with a value of 1, assuming that the initial value of theBloom ﬁlter is 0 and that the positive bits have a value of 1.
It is possible that the number of bits with a value of 1 may
exceed the limit even for nonmalicious nodes by chance. In
this case, we allow the reconﬁguration of the Bloom ﬁlter andinclude information in the notiﬁcation indicating the numberof reconﬁgurations.
IV. E XPERIMENT
We show that block generation notiﬁcations in the proposed
protocol quickly propagate. A simulator is used to measure thepropagation time of the proposed protocol and compare related
studies.
A. Experimental Method
We use SimBlock [11], [12] a blockchain network simulator
for experiments. The Legacy protocol and CBR have been

TABLE IINETWORK PARAMETERS .

Number of nodes
Block generation intervalSize of block
Distribution of hash rate
Average of hash rate
Variance of hash rate

10000
10 min1.0 MiB
Normal distribution
400000 / sec
100000 / sec

TABLE IIICBR PARAMETERS .
Compact block size
Ratio of churn nodes
Block reconstruction failure rate in churn nodes
Block reconstruction failure rate in control nodes

18 KiB
0.97
0.27
0.1

implemented in SimBlock, so Graphene and the proposed protocol are additionally implemented, and the propagation timeis measured. For the proposed protocol, the propagation timesof the block generation notiﬁcation and the block body aremeasured. The propagation time of the block generation notiﬁcation is employed for comparison with other methods because
miners stop the current mining and start the next mining at
the time of receiving the block generation notiﬁcation. Since
the experiments are intended to reveal the fork rate for each
protocol, it is sufﬁcient to consider only the propagation timeof the block generation notiﬁcation for the proposed protocol.
Table II shows the parameters of the blockchain network inthe simulation. Network parameters other than those in Table
II include node distribution, bandwidth, and network delay,
the values of which are obtained from Nagayama et al. [6].
1) Implemention of CBR: Table III shows the CBR parameters in SimBlock. Control nodes are nodes that always
participate in the blockchain network, while churn nodes arenodes that repeatedly join and leave the blockchain network.
Churn nodes and control nodes have different rates of blockreconstruction failure in the CBR, and the distribution of
the number of missing transactions in the event of blockreconstruction failure is also different for control nodes andchurn nodes. Nagayama et al. [6] calculate the cost of sending
the missing transactions based on each distribution. These
parameters are utilized in this experiment.
2) Implemention of Graphene: Table IV shows the parameters of Graphene in SimBlock implemented in this experiment.
The number of transactions per block and the number oftransactions in the transaction pool of a node are referred toin [5]. The ratio of churn nodes is the same as the CBR(Table III). From these parameters, we calculated the sizeof the Bloom ﬁlters S, R, and IBLT I and J, as describedin subsection II-C. For simplicity, the size of the missing
transactions in the CBR is applied. The decoding of IBLT I
is assumed to succeed 100 % of the time if the percentage ofthe number of missing transactions is less than 2 % (scenario
1) since the decoding will almost succeed in scenario 1. The
decoding succeed probability is assumed to be 0 % when thepercentage of missing transactions exceeds 2 % (scenario 2)

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023

TABLE IV
G RAPHENE PARAMETERS .
Number of transactions per block
Number of transactions in a transaction pool (mempool)
Bloom ﬁlter S size
IBLT I size
Bloom ﬁlter R size
IBLT J size
Probability of 1st decoding success (scenario 1)
Probability of 1st decoding success (scenario 2)
Probability of 2nd decoding success

TABLE VI
P ROPAGATION TIME OF BLOCK GENERATION NOTIFICATION BY R .
2000
4000
2.434 KiB
0.901 KiB
1.453 KiB
1.407 KiB
100 %
0%
100 %

TABLE VP ROPOSED P ROTOCOL PARAMETERS .
Block generation notiﬁcation size
Block size
Methods of block propagation
Depth of prerequisite block7.272 KiB (r = 0.1) or
4.468 KiB (r = 0.5)
1.0 MiB
CBR
1, 2 or 3

r = 0.1
274
453
634
302

50 %ile propagation time [ms]90 %ile propagation time [ms]100 %ile propagation time [ms]Average propagation delay [ms]r = 0.5
242
418
601
269

TABLE VIIP ROPAGATION TIME OF BLOCK GENERATION NOTIFICATION BY DEPTH OF
A DEPENDENT BLOCK BODY.
50 %ile propagation time [ms]90 %ile propagation time [ms]100 %ile propagation time [ms]Average propagation delay [ms]Requests number for prerequisite blocks

Depth 1
274
453
634
302
3802710

Depth 2
267
443
564
293
133445Depth 3
267
443
570
293
118951since the decoding almost fails in scenario 2. The successprobability of the second decoding, i.e. the decoding of IBLT J
is assumed to always succeed, as it is almost 100 % accordingto Ozisik et al. [4].
3) Implementation of the Proposed Protocol: Table V
shows the parameters of the proposed protocol implemented
in this experiment. The size of a block generation notiﬁcationis the sum of the size of a transaction ﬁlter described in
Section III and the block header of Bitcoin. The prerequisite
block indices are disregarded because they are very small.
Parameter r is the ratio of the highest number of false positivetransactions to the total number of transactions that have notbeen included in the block and should be available for mining.
In this experiment, we set r = 0.1 and, 0.5 and compare.
Mining is assumed to be a constant depth block on all nodes,
and the compared depth is 1 to 3. Block bodies are propagatedwith CBR.

prerequisite block was requested, as the block body was spreadout in the blockchain network, and the average propagation
time was correspondingly shorter. In the real situation, thedepth of a prerequisite block is changed by the spread of theblock in the blockchain network. However, the impact of thedepth of a prerequisite block body on the block propagation
time is small.
2) Comparison between each protocol: Figure 3 and Table
VIII show the propagation delay for each protocol. In the
proposed protocol, the parameter r = 0.1 and the depth of aprerequisite block is 1 and the propagation time of the block
generation notiﬁcation is measured. The propagation delay
for the proposed protocol was the smallest in all percentiles,
followed by Graphene and the CBR, with the legacy protocol
having the largest propagation time. Compared to Grapheene,
the propagation time of the 50 %ile, 90 %tile, and 100 %tile
for the proposed protocol is 41.1 %, 39.2 %, 27.8 %, respectively, and the average is 40.8 %.

B. Results and Consideration

C. Network communication amount

We describe the comparison of propagation times according
to the parameters of the proposed protocol and those between
each protocol. The end block height of the simulation is100,000 blocks.
1) Comparison according to the parameters of the proposed
protocol: Table VI shows the comparison of the propagation
times of the block generation notiﬁcation at r = 0.1 and
0.5. The depth of a prerequisite block is 1. The size of theblock generation notiﬁcation is 7.272 KiB when r = 0.1 and4.468 KiB when r = 0.5; consequently, the propagation timeis smaller for r = 0.5 than for r = 0.1.
Table VII compares the propagation times of the block
generation notiﬁcation and the number of requests for theprerequisite block when the depth of the prerequisite blockis varied. The value of the parameter r is 0.1. The difference
between the average propagation time of the block generation
notiﬁcation for depths 1 and 2 was 9 ms, while for depths 2
and 3 the average propagation times were equal. The larger
the depth of a prerequisite block is, the fewer times the

Figure 4 shows the expected value of the total message
size for the transmission of a block or a block generation
notiﬁcation between two nodes for each protocol, where theparameters of each protocol are shown in Section IV-A. For the
proposed protocol, two separate message sizes are presented:
a message for the block generation notiﬁcation only, and another message for the block and block generation notiﬁcation.
The message size of the block generation notiﬁcation isimportant in terms of the fork rate. The expected total size ofthe messages between two nodes per hop is 7.3 KiB, with thesmallest block generation notiﬁcation of the proposed protocol,
followed by Graphene with 13 KiB and the CBR with 43 KiB.
Legacy protocols were the largest with 1 MiB.
D. Fork rate
The fork rate is calculated as F = TW /T ,where F is thefork rate, TW is the average block propagation time weighted
by the hash rate, and T is the block generation interval [13].
Table IX shows TW and the fork rate calculated by each TW .

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023

Fig. 5. Fork rate.
TABLE IXF ORK RATE

Fig. 3. Propagation time for each percentile.
TABLE VIIIP ROPAGATION TIME .

50 %ile propagation time [ms]90 %ile propagation time [ms]100 %ile propagation time [ms]Average propagation time [ms]Proposed
Graphene CBR
protocol
274
666
746
1154
1241
453
634
2282
2367
302
741
828

TW [ms]F

Proposed protocol
302
0.000503

Graphene
741
0.00123

CBR
828
0.00138

legacy6478
0.0107

legacy
6182
8633
15326
6478

ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Number JP21H04872.
R EFERENCES

Fig. 4. Expected message size between two nodes per hop.

Figure 5 shows the fork rate. We measure the propagation timeof the block generation notiﬁcation for the proposed protocol.
These results show that the proposed method had the best fork
rate, which is 40.8 % of that of Graphene.
V. C ONCLUSION
In this paper, we proposed a protocol for quickly propagating block generation notiﬁcation using a Bloom ﬁlter in theblockchain network to reduce the fork rate. In experiments inwhich a simulator is used, the propagation time of the 50 %ile
was 41.1 % of an existing protocol, that of the 90 %ile was39.2 % of the existing protocol, and the fork rate calculated
from the average propagation time is 40.8 % of the existing
protocol. Although shortening the block generation interval
increases the fork rate [2], it can be offset by suppressing
the fork rate using the proposed protocol, so that the block
generation interval can be shortened while maintaining the fork
rate. Arakawa et al. [14] proposed such a method.

[1] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system.
Decentralized business review, page 21260, 2008.
[2] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction
processing in bitcoin. In Financial Cryptography and Data Security:
19th International Conference, FC 2015, San Juan, Puerto Rico, January
26-30, 2015, Revised Selected Papers 19, pages 507–527. Springer,
2015.
[3] Matt Corallo.
Bip 152: Compact block relay, 2016.
https://github.com/Bitcoin/bips/blob/master/bip-0152.mediawiki.
[4] A Pinar Ozisik, Gavin Andresen, Brian N Levine, Darren Tapp, George
Bissias, and Sunny Katkuri. Graphene: efﬁcient interactive set reconciliation applied to blockchain propagation. In Proceedings of the ACM
Special Interest Group on Data Communication, pages 303–317. 2019.
[5] Blockchain.com, (Accessed on 10/12/2022). https://www.blockchain.
com/explorer/charts.
[6] Ryunosuke Nagayama, Ryohei Banno, and Kazuyuki Shudo. Identifying
impacts of protocol and internet development on the bitcoin network.
In 2020 IEEE Symposium on Computers and Communications (ISCC),
pages 1–6. IEEE, 2020.
[7] Burton H Bloom. Space/time trade-offs in hash coding with allowableerrors. Communications of the ACM, 13(7):422–426, 1970.
[8] Michael T Goodrich and Michael Mitzenmacher. Invertible bloom
lookup tables. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 792–799. IEEE, 2011.
[9] Bitcoin visuals, (Accessed on 10/12/2022). https://Bitcoinvisuals.com/
chain-input-count-tx.
[10] Kaylash C Chaudhary, Vishal Chand, and Ansgar Fehnker. Doublespending analysis of bitcoin. In Paciﬁc Asia conference on information
systems. Association for Information Systems, 2020.
[11] Yusuke Aoki, Kai Otsuki, Takeshi Kaneko, Ryohei Banno, and Kazuyuki
Shudo. Simblock: A blockchain network simulator. In IEEE INFOCOM
2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 325–329. IEEE, 2019.
[12] Ryohei Banno and Kazuyuki Shudo. Simulating a blockchain networkwith simblock. In 2019 IEEE international conference on blockchain
and cryptocurrency (ICBC), pages 3–4. IEEE, 2019.
[13] Akira Sakurai and Kazuyuki Shudo. Impact of the hash rate on
the theoretical fork rate of blockchain. In 2023 IEEE International
Conference on Consumer Electronics (ICCE), pages 1–4. IEEE, 2023.
[14] Masumi Arakawa and Kazuyuki Shudo. Block interval adjustment basedon block propagation time in a blockchain. In 2022 IEEE International
Conference on Blockchain (Blockchain), pages 202–207. IEEE, 2022.

Proc. 28th IEEE Symposium on Computers and Communications(IEEE ISCC 2023), July 2023