SPECIAL SUBSETS OF ADDRESSES FOR

BLOCKCHAINS USING THE SECP256K1 CURVE

arXiv:2206.14107v1 [[Link]] 28 Jun 2022

ANTONIO J. DI SCALA1 , ANDREA GANGEMI1 , GIULIANO

ROMEO1 AND GABRIELE VERNETTI2
1
DISMA, Department of Mathematical Sciences, Politecnico of Turin
2
DAUIN, Department of Control and Computer Engineering,
Politecnico of Turin

Abstract. In 2020 Sala, Sogiorno and Taufer [14] have been able
to find the private keys of some Bitcoin addresses, thus being able
to spend the cryptocurrency linked to them. This result was unex-
pected, since the recovery of non-trivial private keys for blockchain
addresses is deemed to be an infeasible problem. In this paper we
widen this analysis by mounting a similar attack to other small sub-
sets of the set of private keys. We then apply it to other blockchains
as well, examining Ethereum, Dogecoin, Litecoin, Dash, Zcash and
Bitcoin Cash. In addition to the results, we also explain the tech-
niques we have used to perform this exhaustive search for all the
addresses that have ever appeared in these blockchains.

1. Introduction
The impact that Bitcoin has had on modern society hardly needs
to be explained. In just a few years since the publication of Satoshi
Nakamoto’s white paper [11], blockchain technology has taken hold all
over the world. Its main objective is the creation of an open, public,
decentralised and immutable ledger whose reliability is not based on a
trusted third-party. It is natural that a tool with these features could
find a use in several other fields besides transactions validation. Some
references on the various fields where the blockchain technology has
been employed can be found in [13].
The blockchain that has catched most of the interest after Bitcoin
is perhaps Ethereum, theorised in 2013 by Vitalik Buterin [6]. The
aim of Ethereum is to be a versatile world programmable computer in
which smart contracts, i.e. decentralised programs written in a Turing-
complete programming language, can be executed. A mathematical de-
scription of Ethereum’s blockchain has been published by Gavin Wood
in the yellow paper [16].
1
2 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

In a blockchain, the security of transactions is guaranteeed by public-

key cryptography and, in particular, by the difficulty of solving the
discrete logarithm problem. Using the best known algorithms it is
practically impossible, in a general case, to recover the private key
starting from the knowledge of the public address. For all these rea-
sons, it has been quite unexpected when, in 2020, Sala, Sogiorno and
Taufer [14] found the private keys of some existing Bitcoin addresses,
being able to spend cryptocurrencies on their behalf. They mounted an
attack on a small multiplicative subgroup of a group that is mapped to
the group of points of Bitcoin’s elliptic curve secp256k1. For this small
set, a brute-force attack has been feasible and, against any odds, 4 of
those addresses coincided with some actually used in Bitcoin’s history.
The same authors left open the problem of understanding the reasons
for such pathological behavior and the analysis of other cryptocurri-
ences together with other small algebraic structures.

In this paper we widen the range of the inspection to other 7 subsets

of the same order, obtained as cosets of the group used in [14]. Fur-
thermore, we perform the same examination for Ethereum addresses
and for some other famous cryptocurrencies that share the same ellip-
tic curve: Dogecoin [18], Litecoin [19], Zcash [4], Dash [20] and Bitcoin
Cash [21]. The paper is organised as follows: in Section 2 we list some
basic definitions useful for the following, in Section 3 we define the
small subsets we have decided to analyse, in Section 4 we summarise
the address generation algorithms used by the blockchains we have
chosen and in Section 5 we explain the strategies used to extract the
complete list of addresses. Finally, in Section 6 we report the results
we have obtained and we make a comparison with other elliptic curves
that we find particularly interesting.

2. Preliminaries
Let us recall some basic definitions from algebra and, in particular,
from group theory and elliptic curves over finite fields.

2.1. Group theory.

Lemma 1. Let us consider a cyclic group G = hgi of order n ∈ N.

Then for each divisor d of n there exists a unique subgroup H of order
n
d and one of its generators is g d .
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 3

Definition 2 (Coset). Let us consider a subgroup H ≤ G of a com-

mutative group G. A coset of H is the set
gH = Hg = {gh : h ∈ H},
where g ∈ G.
It is straightforward to verify that |gH| = |H| and that gH = H if
and only if g ∈ H.
Theorem 3. Let F be a field. Then the multiplicative group
F∗ = F\{0}
is a cyclic group.
2.2. Elliptic Curves and the secp256k1 .
Definition 4 (Elliptic Curve). Let F be a field with characteristic
different from 2 and 3. Let A, B ∈ F such that ∆ = 4A3 + 27B 2 6= 0.
Then we define an elliptic curve E(F) as the following subset of the
affine plane over F:
E(F) = {(x, y) ∈ F × F : y 2 = x3 + Ax + B} ∪ {O},
where O denotes the point at infinity.
It is possible to give an additive group structure to the set of points
of an elliptic curve E(F), with the inner chord-tangent point-addition
(see Chapter 2 of [15] for more details).

Let us now introduce the most relevant elliptic curve for our pur-
poses, which is the one used by all the cryptocurrencies that we are
going to consider.
Definition 5 (The secp256k1 curve). Let us consider the prime num-
ber
p = 2256 − 232 − 29 − 28 − 27 − 26 − 24 − 1.
The elliptic curve
E(Fp ) : Y 2 = X 3 + 7
is called secp256k1.

The number of rational points of the curve secp256k1 over Fp is the

prime number
q =1157920892373161954235709850086879078528375642790749043
82605163141518161494337,
4 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

so that the additive group E = E(Fp ) is isomorphic to Fq (+). A gen-

erator of this group is the point P = (Px , Py ), where
Px =55066263022277343669578718895168534326250603453777594
175500187360389116729240,
Py =32670510020758816978083085130507043184471273380659243
275938904335757337482424.
If they are given the point P and a point Q = kP (obtained by
summing k times the point P ), it is in general very hard to recover
the integer k. This is known as the Discrete Logarithm Problem over
Elliptic Curves (ECDLP).

3. The small subsets

As we have seen in Section 2, the group E(Fp ) of the curve secp256k1
has prime order
q =1157920892373161954235709850086879078528375642790749043
82605163141518161494337,
and it is then isomorphic to the additive group Fq (+). Hence, the
private key can be chosen among the non-zero elements of Fq (+), which
are q − 1. The set of all private keys, then, is in bijection with the
multiplicative group F∗q (·), which also has order q − 1 and, by Theorem
3, is a cyclic group. Therefore, by Lemma 1, it has a unique cyclic
subgroup of order d for any divisor d of q − 1. Its factorisation is
q − 1 = h · p1 · p2 · p3 ,
where
h = 18051648 = 26 · 3 · 149 · 631,
p1 = 107361793816595537,
p2 = 174723607534414371449,
p3 = 341948486974166000522343609283189.
In [14], the authors examined the multiplicative subgroup H ≤ F∗q ,
whose order is
|H| = h = 18051648,
since it can be fully investigated in a short time. As pointed out in the
same paper, it is worth to analyse also some other structures of the
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 5

same order, for example the cosets of G. Let us consider the generator
g = 7 of the group F∗q (·). In this way, using Lemma 1 and denoting by
g 0 = 7p 1 p 2 p 3 , g1 = 7hp2p3 , g2 = 7hp1 p3 , g3 = 7hp1p2 ,
g4 = 7hp1 , g5 = 7hp2 , g6 = 7hp3 , g 7 = 7h ,
we have that
|hg0 i| = |H| = h, |hg1 i| = p1 , |hg2i| = p2 ,
|hg3 i| = p3 , |hg4 i| = p2 p3 , |hg5i| = p1 p3 ,
|hg4 i| = p1 p2 , |hg7 i| = p1 p2 p3 .
The cosets that we investigate in this paper are gi H, for i ∈ {0, . . . , 7}.
Notice that g0 H = H, that is the same subgroup considered in [14].
Remark 6. What the authors have done in [14] is to search among the
multiplicative subgroups of F∗q (·), even though the private key space is
(E(Fp ), +) ∼
= Fq (+), hence additive. This observation makes the result
(4 keys detected) even more surprising, since it has been considered a
subgroup that is far from the actual nature of the group E(Fp ). This
very curious fact makes us think that the cause is some implementation
error that has occurred during the practical design of the wallets.

4. Address generation
In this section we examine how the addresses are generated starting
from the choice of the private key.
4.1. Private and Public Key. The private key is an arbitrary 256-
bit integer k. Using k, it is possible to compute the point
K = kP = (Kx , Ky )
over the elliptic curve, from which the public key is derived. We have
two different ways to represent the public keys:
i) P K1 = 0x04 || Kx || Ky ,
(
0x02 || Kx if Ky is even,
ii) P K2 =
0x03 || Kx if Ky is odd,

where we have denoted with || the string concatenation. In the first

case, the public key, also known as uncompressed public key, consists
of 65 bytes (32 bytes for Kx and Ky , plus the byte 0x04), while in
the second case the public key is called compressed public key and
6 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

consists of 33 bytes. The ways of obtaining the addresses for each

cryptocurrency are discussed in the following paragraphs.

4.2. Bitcoin addresses. There are three manners to generate Bitcoin

addresses starting from the point K = (Kx , Ky ).
First of all, two hash functions appear in Bitcoin address generation,
which are SHA-256 [12] and RIPEMD-160 [3]. Let us compute, for
i ∈ {1, 2} :
Wi = 0x00 || RIPEMD-160(SHA-256(P Ki )),
checksumi = (SHA-256(SHA-256(Wi )))[1..4],
where [1..4] denotes the first 4 bytes of that string. The first byte 0x00
is a prefix called version byte. Then, the first two ways to generate
Bitcoin addresses are, for i ∈ {1, 2},
Base58(Wi || checksumi ),
where Base58 [22] is an encoding scheme.
The addresses of the third kind have been introduced in 2017 and they
are called segwit addresses [23]. These addresses are computed only
starting from compressed public keys. First of all, it is computed
W = RIPEMD-160(SHA-256(P K2)),
then it is encoded using Bech32 [24] and it is concatenated to the
prefix bc1 in order to obtain the final address format
bc1 || Bech32(W ).

4.3. Ethereum addresses. Ethereum addresses are generated start-

ing from the uncompressed public key, that is
P K = 0x04||Kx||Ky .
However, a different hash function is used: KECCAK-256 [2]. The
address is computed as
KECCAK-256(P K)[1..20],
where [1..20] denotes the first 20 bytes of that string.
After this computation, the addresses are encoded following the rules
described in the EIP-55 document [25]. In short, the capitalisation
of certain alphabetic characters in the address is changed to obtain a
checksum that can be used to protect the integrity of the address from
typing or reading errors.
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 7

4.4. Dogecoin addresses. Dogecoin address generation is similar to

the first two methods described for Bitcoin, thus we can use uncom-
pressed or compressed public keys. It only changes the version byte
0x00 of Bitcoin into 0x1E. In this way, the final Base58 encoding gives
a D as the first letter for each address. Dogecoin does not generate
addresses following the segwit standard.
4.5. Litecoin addresses. Litecoin can generate addresses using all
the three methods described for Bitcoin. In the first two cases, the
prefix is the version byte 0x30 instead of 0x00. In this way, all the ad-
dresses start with the letter L. In the segwit case, the Bech32 encoding
of the address is concatenated with the prefix ltc1, that is
ltc1 || Bech32(RIPEMD-160(SHA-256(P K2 ))).
4.6. Dash addresses. The address generation is similar to Bitcoin,
but in this case the version byte is changed into 0x4c, so that all the
addresses start with the letter X. Dash does not generate addresses
following the segwit standard.
4.7. Zcash addresses. The address generation is similar to Bitcoin,
but in this case the version byte is changed into [0x1c, 0xb8]. Zcash
addresses can either start with the letter t, if they are transparent, or
z, if they are shielded. Zcash does not generate addresses following the
segwit standard.
4.8. Bitcoin Cash addresses. Bitcoin Cash (BCH) is the result of a
Bitcoin hard fork that happened in 2017, when some of Bitcoin nodes
did not share the segwit soft fork. BCH addresses are encoded two
times:
• first, an address with the same encoding of Bitcoin is obtained,
• finally, the address is encoded again, with an encoding scheme
called CashAddr [26], which is used by Bitcoin Cash only. This
encoding is similar to Bech32.
BCH addresses that are encoded twice start with the string bitcoin-
cash:q, or just with the letter q. It comes natural that Bitcoin Cash
does not generate addresses following the segwit standard.

5. Experimental environment and development

In this section we describe our experimental environment, which led
us to the results showed in the following section. In order to perform
a deep investigation for the existence of the addresses generated, we
used a database filled with all addresses that had ever appeared on the
8 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

blockchains of our interest, exploiting the MySQL Laragon tool for the
search operation [27].

5.1. Blockchain addresses extraction. The extraction of all the

addresses ever appeared on a blockchain can be done in different ways,
depending on the time availability.
Generally, the two most common methods are:
• setting up a full node (which contains a complete local copy of
the relative blockchain) and reading data from it,
• getting data through public Application Programming Inter-
faces (APIs) (available on the web).
In our case, we decided to set up full nodes when it was impossible
to retrieve data from any public API. In this regard, we would like
to point out that the availability of public APIs, documentation and
general support were very weak for any blockchain other than Bitcoin
and Ethereum.

5.2. Development. For some blockchains (Dogecoin, Litecoin, Bit-

coin Cash and Ethereum) we developed some Python scripts in order
to use the public APIs provided by Tatum [28] and Ankr [29]. Differ-
ently, to analyse Dash and Zcash, we had to build our own full nodes
and to get the blocks data from them. Finally, the list of Bitcoin ad-
dresses was taken from [30], which offers some interesting information
about the Bitcoin blockchain. For anyone interested in learning more,
our code is publicly accessible at [31]. We conclude this section by
reporting in the following table the number of addresses we have ex-
aminated, that is the totality of addresses that have ever been used in
the history of these blockchains.

Blockchain Addresses
Bitcoin 923.414.052
Ethereum 144.596.346
Dogecoin 69.817.509
Litecoin 134.530.241
Dash 92.456.113
Zcash 6.813.058
Bitcoin Cash 334.965.092
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 9

6. Cosets examination
In this section, we list the results that we have obtained by inspecting
the eight cosets gi H, i ∈ {0, . . . , 7}, of order h = 18051648 for the seven
blockchains we have chosen to investigate. The eight cosets contain a
total of 8h ≈ 144 million addresses. We have checked if these addresses
ever appeared in the blockchains mentioned above, i.e. if they have ever
held any amount of cryptocurrency.
More specifically, we have written some Python code that, start-
ing from the list of private keys, computes the resulting addresses in
the right format, and then checks if these addresses ever appeared on
the analysed blockchains. The code used in this analysis is publicly
accessible at [31]. The following table sums up all the results.

H gi H, i = 1, . . . , 7
Uncompressed Bitcoin addresses 4 addresses found [14] No address found
Compressed Bitcoin addresses 3 addresses found No address found
Segwit Bitcoin addresses 1 address found No address found
Ethereum 1 address found No address found
Dogecoin 3 addresses found No address found
Litecoin 2 addresses found No address found
Dash 2 addresses found No address found
Zcash No address found No address found
Bitcoin Cash 6 addresses found No address found

From this analysis, it turns out that only three addresses are non-
trivial, i.e. they do not have 1 or -1 as the private key. Notice that,
for example, in Dogecoin we have found 3 trivial addresses since each
private key can be associated to two different encodings of the public
key (compressed and uncompressed), for a total of 4 potential trivial
addresses. All of the three non-trivial addresses belong to the Bitcoin
blockchain. The two addresses already found by Sala et al. [14] were
generated in 2013 and 2014, so they are present in Bitcoin Cash as
well, while the third one is the address
1H1jFxaHFUNT9TrLzeJVhXPyiSLq6UecUy,
and it was generated starting from a compressed public key. It was
created on October 15, 2019, after the Bitcoin Cash fork, which is dated
August 1, 2017. The address has no cryptocurrency into it nowadays.
The story of the address
1PSRcasBNEwPC2TWUB68wvQZHwXy4yqPQ3,
10 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

already found by Sala et al., is somewhat interesting. That address

was created on March 15, 2014, and the funds got removed in June
2018 only after the authors of the previously cited papers contacted
them (read [14] to know more about what they have done). Hence, the
address is old enough to appear on BCH. It is indeed present:
qrmzrdndlfxpnkk3w5d5l7etnysnqfgk5yxsf6k0qq,
after the new encoding with the CashAddress format.
However, the address is empty as someone moved the funds on that
address on May 1, 2019. Then on November 15, 2018, Bitcoin Cash
had yet another hard fork, that led to the birth of Bitcoin SV. Hence,
this address must be present on that blockchain as well, with the funds
still into it. By examining a Bitcoin SV explorer, it turns out that the
funds from that address got also moved on May 1, 2019, two minutes
earlier than the transaction on Bitcoin Cash! It seems likely to assume
that the funds got moved from the same entity.

Finally, notice that we were not able to find any address on the
seven cosets we have chosen to examine. This is interesting, but not
unexpected, as the probability to find an address with this brute-force
method is really low [14]. In this way, the security of these blockchain
is not threatened since it results way more profitable to mine, i.e. to
join honestly the protocol, than trying to generate random private keys
with the aim of stealing cryptocurrency [5]. This may also confirm that
the non-trivial addresses were generated due to a poor implementation
of some wallets. It would also be interesting to try to understand which
Bitcoin wallets generated these addresses.

6.1. Other curves to examine. The most used elliptic curve in

blockchains, beside the secp256k1, is for sure the Curve25519. It is
employed in several blockchains, including Monero [1], Cardano [10],
Solana [17] and Algorand [7]. The defining curve is the Montgomery
curve
E(Fp ) : Y 2 = X 3 + 486662X 2 + X,
where p = 2255 − 19 is a prime number. The number of rational points
is n = 8l where
l = 2252 + 27742317777372353535851937790883648493.
Reasoning as in the case of the curve secp256k1, the private key can be
chosen among the non-zero points, whose number is
l − 1 = 22 · 3 · 11 · q1 · q2 ,
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 11

where
q1 = 276602624281642239937218680557139826668747,
q2 = 198211423230930754013084525763697.
The private key space is then in bijection with Z∗l (·), it is cyclic and
has a unique subgroup for each divisor of its order l − 1, by Lemma 1.
Notice that an analogue analysis can not be performed, since the small
subgroup contains only 132 = 22 · 3 · 11 points.

Finally, another curve that might be worth analysing in the future

is the NIST P-256 curve, defined in the specification [8]. It is actually
used by NEO [32], Tezos [9] and Ontology [33]. The curve is
E(Fp ) : Y 2 = X 3 − 3X + B,
where
B =410583637251521421293261297800472684091144410159937255
54835256314039467401291,
and p is the prime number
p = 2256 − 2224 + 2192 + 296 − 1.
The order of this curve is
q =115792089210356248762697446949407573529996955224135760
342422259061068512044369,
and q − 1 factorises as
q−1 = 24 ·3·71·131·373·3407·17449·38189·187019741·622491383·q1·q2 ,
where
q1 = 2624747550333869278416773953,
q2 = 1002328039319.
This case is certainly more interesting than the previous one, since there
are several subgroups of order dividing q − 1 that can be inspected.

7. Conclusions
In this paper we have tried to give an answer to two open questions
left in [14]. It turns out that the strange behaviour observed by Sala et
al. is a peculiarity of Bitcoin (and, of course, of its hard forks), where
we have also found a new address not detected in [14], since it uses the
compressed public key format. Instead, we have not been able to find
any non-trivial private keys for the other analysed blockchains and for
12 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS

the cosets of the starting subgroup.

Another contribution of this work is the comprehensive analysis of

the addresses we have extracted from some of the most important
blockchains to date. In fact, it is almost impossible to find relevant
information on the web for any blockchain other than Bitcoin and, for
some extent, Ethereum. The interested readers can extract addresses
with the same methods, using the scripts available in our GitHub folder
[31].

For future works, it might be interesting to analyse more thoroughly

the wallets used in the period these addresses were generated, to try
to confirm the hypothesis that this behavior really comes from an in-
correct implementation of the wallet itself. In addition, it would be
possible to examine the small subgroups found in Section 6.1 to under-
stand if also NIST P − 256 curve presents some strange behaviour on
those subsets.

References
[1] K. M. Alonso, S. Noether, Zero to Monero, Available online:
[Link] (2020).
[2] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, The Keccak SHA-3 submis-
sion, Submission to NIST (Round 3), (2011).
[3] A. Bosselaers, H. Dobbertin, B. Preneel, RIPEMD-160: A Strengthened Version
of RIPEMD, In International Workshop on Fast Software Encryption; Springer:
Berlin/Heidelberg, Germany, pp. 71–82, (1996).
[4] S. Bowe, D. Hopwood, T. Hornby, N. Wilcox, Zcash Protocol Specification,
Available online: [Link] (2016).
[5] A. Brighente, M. Camaioni, M. Conti, E. Olivastri, Should I Mine or Should I
Break: On the Worthiness of Brute-Forcing Cryptocurrency Addresses, IEEE In-
ternational Conference on Pervasive Computing and Communications Workshops
and other Affiliated Events, pp. 279-284 (2022).
[6] V. Buterin, Ethereum: A Next-Generation Smart Contract and Decentral-
ized Application Platform, Available online: [Link]
(2014).
[7] J. Chen, S. Micali, Algorand, Available online:
[Link] (2017).
[8] L. Chen, D. Moody, A. Regenscheid, K. Randall, Recommendations for Discrete
Logarithm-Based Cryptography: Elliptic Curve Domain Parameters, Draft NIST
Special Publication 800-186, (2019).
 SPECIAL SUBSETS OF ADDRESSES FOR BLOCKCHAINS 13

[9] L.M. Goodman, Tezos — a self-amending crypto-ledger, Available online:

[Link] (2014).
[10] C. Hoskinson, Why we are building Cardano, Available online:
[Link] (2017).
[11] S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, Available on-
line: [Link] (2008).
[12] W. Penard, T. van Werkhoven, On the Secure Hash Algorithm Family, Cryp-
tography in Context, Chapter 1 (2007).
[13] M. Pilkington, Blockchain technology: principles and applications, Research
handbook on digital transformations, Edward Elgar Publishing (2016).
[14] M. Sala, D. Sogiorno, D. Taufer, A Small Subgroup Attack on Bitcoin Address
Generation, Mathematics, 8:10, pp. 16451-16458 (2020).
[15] L. C. Washington, Elliptic Curves: Number Theory and Cryptography, Second
Edition, Chapman & Hall/CRC, (2008).
[16] G. Wood, Ethereum: A secure decentralised generalised transaction ledger,
Available online: [Link] (2014).
[17] A. Yakovenko, Solana: A new architecture for
a high performance blockchain, Available online:
[Link]
(2018).
[18] [Link]
[19] [Link]
[20] [Link]
[21] [Link]
[22] [Link]
[23] [Link]
[24] [Link]
[25] [Link]
[26] [Link]
[27] [Link]
[28] [Link]
[29] [Link]
[30] [Link]
[31] [Link]
[32] [Link]
[33] [Link]