A User-centric System for Verified Identities on
the Bitcoin Blockchain
Daniel Augot123 , Hervé Chabanne45 , Thomas Chenevier4 , William George213 ,
Laurent Lambert4

arXiv:1710.02019v1 [cs.CR] 5 Oct 2017

1

2

INRIA, Palaiseau, France
daniel.augot@inria.fr
Laboratoire LIX, École Polytechnique & CNRS UMR 7161, Palaiseau, France
wgeorge@lix.polytechnique.fr
3
Université Paris-Saclay, France
4
OT-Morpho, Issy-les-Moulineaux, France
herve.chabanne@morpho.com
thomas.chenevier@morpho.com
laurent.lambert@morpho.com
5
Télécom ParisTech, Paris, France

Abstract. We present an identity management scheme built into the
Bitcoin blockchain, allowing for identities that are as indelible as the
blockchain itself. Moreover, we take advantage of Bitcoin’s decentralized
nature to facilitate a shared control between users and identity providers,
allowing users to directly manage their own identities, fluidly coordinating identities from different providers, even as identity providers can
revoke identities and impose controls.

Keywords: Bitcoin blockchain, Identity proofs, Discrete Logarithm REPresentation (DLREP), Personal Identity Management Systems (PIMS)

1

Introduction

We live in a world where the ways in which a person’s identity is being used
are increasingly complex. Appropriately handling sensitive personal data, such
as medical, financial, and employment data, is subtle and requires care [21]. In
this context, it is important to employ technical solutions that promote good
security practices and that ensure that users have appropriate controls over how
their data is being used. There are many [5] who advocate for a decentralized approach in which users directly manage their own identities via personal servers,
Personal Identity Management Systems (PIMS). Meanwhile, blockchains, most
notably Bitcoin [18], have provided new models of decentralization. In this work,
we propose a sort of “light-PIMS,” to be implemented on the Bitcoin blockchain.
The decentralized nature of the blockchain allows us to create a neutral space
where identity issuers and users share responsibility for users’ identities, providing protections and the capacity for oversight for both parties.

Related Work. In 2015 MIT Media Labs introduced a system for academic
certificates on the Bitcoin blockchain [20]. Taking advantage of the blockchain’s
persistence over time, this system gives students a convenient way of proving
that they graduated, see Section 2. The Blockstack project [6] has implemented
decentralized versions of PKI and DNS on the Bitcoin network. In [11], a decentralized scheme to issue credentials in the absence of a trusted third party
is proposed using Bitcoin. This scheme incorporates zero-knowledge protections
such as those we will deal in Section 2.3. The startup CryptID [1] has proposed a system where encrypted records of fingerprints (along with a password)
are stored in the Factom blockchain, which is itself periodically committed to
the Bitcoin blockchain, replacing the traditional centralized server in fingerprint
scanning identification systems with a more lightweight system. We generalize
these ideas to permit more flexible user identities that can contain different fields
of information useful in interacting with diverse service providers. We further explore the possibilities enabled by performing these interactions on a blockchain.
Some architectures propose new, application designed blockchains. For example,
the proposal of IDCoins [2] relies on a custom blockchain in which the proof of
work is related to the generation of GPG/PGP keys necessary to create a web
of trust. The Guardtime KSI blockchain, which forms the base of an electronic
records system used in Estonia [4], [23], is a permissioned blockchain. In [28] a
system is proposed to store user information such as the GPS data from their
phone in a distributed hash table and then store pointers to this data and permissions on how it may be used or retrieved on a blockchain. The proposition of
ChainAnchor [14] even allows to create a semi-permissioned structure that can
be placed on top of an existing blockchain such as that of Bitcoin by changing
the incentive structure of miners to promote permissioned transactions. For a
survey on other proposals that touch on the relationship between blockchains
and identity management, see [27] and [16].
Our Contribution. We propose an identity management system that will
take advantage of the decentralized nature of the Bitcoin blockchain to allow
for a balance between the ability for users to manage their own identities and
for issuers to establish controls. The different entities of our proposal communicate via Bitcoin transactions, allowing identity issuers to outsource much of
the infrastructure required for this system to the Bitcoin network, which as the
most robust, most established blockchain, has strong security properties, most
notably, that miner’s work maintains strong integrity of its data. Privacy during identity verification is ensured thanks to the attribute-based credentials of
Brands [8]. While [11] already proposes using Brands credentials in Bitcoin, their
protocol could, in fact, be implemented in any blockchain without major modifications. In contrast, our proposal takes advantage of the specifics of the Bitcoin
scripting language to encode identity meaning in Bitcoin syntax. Specifically, we
build upon the idea of MIT Media Labs [20] that revocation can be encoded in
terms of the status of a Bitcoin transaction to enable additional mechanisms for
issuer oversight which are then enforced by the Bitcoin network. Particularly, in
our system an issuer can limit the number of times an identity can be used, see
2

Section 3.5. At the same time, we will see that our system gives a great deal of
control to the user over her identity.
Note that in traditional systems the reconciliation between user control and
issuer oversight is problematic; in most systems the identity is generally controlled entirely by an on-line issuer with little input from the user [5], or alternatively the issuer will sign an identity to be managed by the user, then the issuer
will go offline ceding his capacity for oversight (See [9] for a further discussion
on the advantages and disadvantages of these two models.)
Compared to a traditional decentralized system, we offer more integrated
issuer controls. For example, compare the revocation mechanism discussed in
Section 3.4 to the challenges encountered using revocation lists in public key
infrastructures (PKIs) [17]. Additionally, we will see that our system has the
following advantages compared to centralized systems:
– Our system does not require identity providers to be as “lively” as they
must be in traditional, centralized systems. If an identity provider has placed
controls on an identity, such as a limit on the number of times it can be used,
then even if an identity issuer has a service interruption, a user can continue
to use her identity and these limits will continue to be enforced by the robust,
worldwide Bitcoin network. A user can even revoke her own identity without
intervention by the issuer.
– By providing a common space, control over which is shared between the
different actors through the mechanisms of the blockchain, we allow users
to coordinate several micro-identities, only needing to trust a small portion
of their identities to any given identity provider, see Section 3.6. While a
similar coordinate scheme is possible without a blockchain, in practice it is
highly impractical for a user to coordinate identities from different identity
providers each of whom uses his own distinct formatting and infrastructure.
On the other hand, our system has two (potential) drawbacks. First, as authentications are encoded in Bitcoin transactions, this requires paying transaction fees to miners, see Section 3.7 for an estimate of these fees. Second, Bitcoin
transactions are by their nature public, posing risks to user anonymity. The typical suggestion to ensure (pseudo-)anonymity in Bitcoin is to use each Bitcoin
address exactly one time. An analogous idea works here, at the expense of having
higher user fees, see Remark 5. Note that users have differing standards regarding the privacy that they expect in their interactions. Some users may be willing
to sacrifice some anonymity in exchange for lower fees. In fact, some users, such
as those that gladly link their Facebook account to their Instagram account or
their favorite blogs, may even prefer that metadata on their transactions be tied
to them, allowing them to create a digital presence on which they can build
a reputation. See Section 5 for a proposal on how a reputation system can be
built on top of our architecture. A user should be empowered to make choices
regarding how private they want to be.
3

2

Background

In this section we briefly recall some of the existing ideas, in Bitcoin and in the
work of Brands [8], upon which our system is built.
2.1

Bitcoin relevant notions

It is a particularity of Bitcoin that all bitcoins exist in the form of Unspent
Transaction Outputs (UTXOs) [18], [7, Chapter 5]. Each transaction may have
several inputs, each of which was an output UTXO for some previous bitcoin
transaction, and it may have several outputs. Most transaction outputs correspond to a bitcoin address, the hash of the public key that can spend it or a
hash of a script detailing how the coin can be reclaimed. (These are called Pay
to Public Key Hash P2PKH and Pay to Script Hash P2SH outputs respectively.)
Particularly, one can create P2SH outputs that can then be spend by an m of n
multisig. Also relevant to our work will be OP RETURN outputs; each such output
contains up to 80 bytes of space in which the sender of a transaction can store arbitrary information. Note, OP RETURN outputs must have zero bitcoins associated
to them; as such, they are provably not usable as inputs to later transactions.
The raw transaction that is broadcast to the nodes contains the amount
of bitcoin to associate to each output, the script permitting validation of each
output (P2SH, P2PKH, etc), and the scripts for each input that satisfy the
requirements set up when the corresponding input UTXO was created, generally
including a signature from a corresponding private key. The hash of this raw
transaction becomes the transaction identifier (txid), which is included in the
Merkle tree that produces a block header and is ultimately recorded in the
block chain in an immutable way. Thus, the given inputs and outputs of a given
transaction are provably linked together.
Financial friction in Bitcoin transactions Miners are compensated by
“fees.” The amount paid in fees for a given transaction is the difference between
the combined values of the inputs and the combined values of the outputs. Miners, who are limited in how many bytes they can fit a given block, generally
choose to include the transactions with the most profitable fees with respect to
the number of bytes in its raw transaction [7, Chapter 5]. When discussing our
schema, we will denote the fees for a given transaction by FNAME-OF-TRANSACTION . See
Section 3.7 for estimations of these amounts.
In order for a Bitcoin transaction to be considered valid it must satisfy certain
basic properties such as not double spending a previously spent output, having
valid signatures, etc. Any block that contains an invalid transaction will be
rejected by the network. In addition, the Bitcoin Core software distributions to
miners suggests requirements that transactions need to satisfy in order to be
considered “standard.” These requirements are implemented at the discretion
of each miner and thus vary slightly across the network; a miner may refuse
to include a given transaction in the blocks he mines as “non-standard,” but
4

if another miner broadcasts a block with this transaction in it, he will still
accept that block if the transaction is valid. In particular, for a transaction to
be considered standard, each of its non-OP RETURN output must have a minimal
value so as to prevent the network from being spammed by extremely low value
transactions. Any amount of bitcoin below this minimum is called “dust.” As
of version 0.14 (March 2017), Bitcoin Core [12] recommends that that miners
refuse transactions that have a P2PKH output of less than .00000546 bitcoin,
currently (June 2017, 1BTC=2720 USD) around .01 USD. We denote by D this
minimal amount. Fees and the requirement to leave dust can greatly erode the
value of a user’s bitcoins if she engages in many transactions of small amounts.
2.2

MIT Media Labs certificate issuing schema

We are inspired by the transaction structure used in [20]. In this system a certificate or diploma is issued to a user who completes a given program of study,
encoded in a Bitcoin transaction. The transaction has a single input, from the
credential issuer, so the transaction must be signed by the private key corresponding to the issuer’s address. Hence, verifiers can be confident that credential
was issued by an approved party. There are three outputs. The first is the Bitcoin
address of the user. Then the user can authenticate herself as the holder of the
credential by signing messages using the corresponding private key. The second
output is to an address again belonging to the issuer. If this output is spent, the
certificate is seen as being revoked. We view this revocation mechanism as a key
innovation of [20], and we integrate and develop it into our system. Finally, the
third output is an OP RETURN that contains the certificate information. Note that
as each of these UXTOs is thought of as having symbolic meaning, their bitcoin
values are secondary; indeed, they are assigned values slightly larger than D.

Input Addresses
Issuer

Amounts Output Addresses
.000155 BTC

Amounts

Recipient
.000275 BTC
Issuer (for revocation) .000275 BTC
OP RETURN( Certificate info) 0 BTC
Fees:

.0001 BTC

Fig. 1. Schema of an MIT certificate issuing transaction as in [20]. See, for example,
txid: 41740ae0812e5a7804778f43c9fd1f8df50fe1bcd0545e9d627a83ab9d0d3d07

2.3

The DLREP function

In [8], Brands proposed very efficient ways of revealing parts of an identity to
verifiers, relying on discrete logarithms and hash functions. All the following is
from [8]. Assume that n identity fields X1 , . . . , Xn are to be cryptographically
blinded for further proofs. Let q be a prime number and G a group of order q,
5

in which the discrete logarithm is hard. Typically, we take G to be the Koblitz
elliptic curve secp256k1 where points are represented with 64 bytes (we use
multiplicative notation for compatibility with [8]), namely we use the same G
that is already being used for the Bitcoin signature protocol. Let g0 , g1 , . . . , gn ∈
G. Furthermore, there is the need (see Section 3) for an auxiliary random X0 to
protect unknown fields from a dictionary attack when the other fields are known.
Definition 1 The tuple (X0 , X1 , . . . , Xn ) ∈ Zn+1
is called a Discrete Logarithm
q
n
Q
X
gj j ∈ G with respect to (g0 , g1 , . . . , gn ).
REPresentation (DLREP) of h =
j=0

To (non-interactively) prove knowledge of a DLREP of h to a verifier V, a
prover P performs the following protocol steps [8, §2.4.3]
1. P generates n + 1 secret, random numbers a0 , a1 , . . . , an in G. Let A =
n
Q
a
gj j , and compute c as c = H(A), where H is a one-way hash function.
j=0

2. P computes bj = aj + cXj , j = 0, 1, . . . , n and sends them, as well as c to V.
n
Q
b
3. The verifier V checks that H(
gj j h−c ) = c holds.
j=0

Then, [8, Chapter 3] shows how the DLREP can be used to selectively prove
properties about the Xj ’s, while any other information remains hidden. These
techniques can be used to prove arbitrary satisfiable Boolean statements about
the Xj ’s. For example, a prover can demonstrate that she is a French citizen AND
that she is either under 18 OR over 65. P can prove (true) statements about her
identity that contain an arbitrary number of ANDs, ORs, and NOTs in such a
way that V only learns information that can be computed using the status of
the formulas requested and information available a priori. See [8, Proposition
3.6.1] for a formal statement of this result. Brands [8] also shows that if the discrete logarithm problem is difficult, DLREP is one-way and collision-intractable,
preventing an adversary from forging an identity with a given DLREP.

3
3.1

Our proposal
Actors, protocol structure, and security assumptions

Our system will have three types of actors : Identity Providers (IP), Service
Providers (SP), and Users (USR). We borrow the following from [20]:
Definition 2 An identity is a tuple (X1 , . . . , Xn ) where each Xj ∈ Zq stands
for a different attribute, as exemplified below.
An attribute Xj may represent a name, a date of birth, a social insurance number, medical or financial data, or some other personal information about a user.
Typically, based on an identity provided by IP, a user (USR) wants to convince
SP to give her access to its services.
6

Assumptions on actors We consider that both the Bitcoin addresses of IP
and SP are well-established and public, aIP and aSP respectively. We will consider scenarios in which we have multiple identity providers and service providers,
whose addresses are denoted aIP 1 , aIP 2 , . . . and aSP 1 , aSP 2 , . . . respectively. In
(1)
(2)
contrast, USR may have different Bitcoin addresses aU SR , aU SR , . . . in order to
obfuscate the link between her identity transactions. When discussing a given
(i)
user’s address generally, we write aU SR to indicate one her addresses. Note that a
user should not re-use Bitcoin addresses that she has used for non-identification
transactions, in order to not link this identity with her other Bitcoin activity.
We assume that all of USR, IP, and SP are capable of sending and receiving
bitcoin and that they can perform operations in secp256k1. We will explore in
Section 3.9 further technical requirements on the ability of SP to track Bitcoin
transactions which will depend on SP’s security requirements. We assume that
IP validates a user’s real world identity (via a more or less rigorous verification
process) and then publishes documents that are correct. Furthermore, IP should
handle user personal data in a way that respects user-privacy. Note that IP does
not need to stay online for the identities it issues to be used, and only participates
for issuing and revocation of identities, and certain exceptional maintenance, see
Section 3.5. Service providers accept identities issued by identity providers they
wish to trust. Note that service providers may fail or refuse to provide a service,
a fact which can not be managed by our protocol. They may deviate from the
protocol (at the risk of impairing their reputation, see below).
Assumptions on Bitcoin network We will use the public ledger functionality
of Bitcoin: it is a “bulletin board” where anyone can post messages and read
messages posted. More precisely, [13] and [22] provide the definitions of liveness,
i.e. every honest participant will have its posted messages seen by every honest participant after some delay, and persistence, which means that every posted
message will indefinitely be seen at the same position by all participants. We will
also rely on the security semantics of the Bitcoin transaction verification procedure which ensure no double-spending, that each non-generation transaction
has inputs linked to previous transaction outputs, etc. Under some quantitative
bounds on the relative power of the adversary, be it computing power in [13],
and or computing and network power [22], the Bitcoin core protocol is proven
to securely provide these functionalities.
The above results are theoretical and quantitative. There could be real world
situations in the Bitcoin blockchain where the adversary has enough power to
violate the above quantitative bounds, and also accidental cases where problems
occurs like small forks, peer-to-peer failures, etc. We will discuss the impact of
these possible attacks and failures in Section 3.9 below.
Remark 1. Note that there are other relatively well-established blockchains such
as Ethereum that can also serve as a “bulletin board.” However, by working in
Bitcoin, we can use the linking mechanism of Bitcoin transactions, which is
not natively present in the account based model of Ethereum [26]. Also, the
7

total hash power of the Bitcoin network is substantially greater than that of
Ethereum [15], which can be seen as a sign that Bitcoin has a great resilience to
51% attacks.
There are three steps for our protocol: a Setup phase, an Enrollment
phase, and an Operational phase.
3.2

Setup phase

Each IP will choose some set of g0 , g1 . . . , gn ∈ G that will serve as the base for a
DLREP function. These gj should be public and readily available. For example,
IP could create a series of Bitcoin transactions with inputs from his address in
which the gj and the fields they represent are stored in OP RETURN outputs.
3.3

Enrollment phase

During the Enrollment phase, USR brings to IP the (physical, biometric, etc)
elements required to assert that her identity indeed matches all the Xj ’s. This
can be as strong as a physical meeting, in which the user shows a passport, or
as light as an authentication on a web server, depending on the policy of IP.
(i)
During this phase USR should provide IP with a Bitcoin address aU SR that
she controls and an element g0X0 to protect against dictionary attacks, where X0
is chosen at random by USR so that IP does not learn it. Then, IP can form
ha(i) = g0X0 g1X1 . . . gnXn , as in Section 2.3.
U SR
The Enrollment phase corresponds to a single Bitcoin transaction, TXPUBLISH .
The primary purpose of this transaction is to record ha(i) in the blockchain;
U SR
however, we see that this transaction will include other structure.
TXPUBLISH (Identity Establishment) : IP sends amounts of bitcoin to two
(i)
outputs. First a minimal amount of bitcoin D is sent to the user’s address aU SR ;
this ties the user’s address to the identity. Also, IP sends bitcoin to a 1 of 2
(i)
(i)
P2SH multisig of aU SR and aIP , denoted MSIG1 2(aU SR , aIP ), which we view
as an authentication token that the user will spend upon using her identity.
Moreover, either USR or IP can prevent further use of the token by USR by
sending it to IP or even spending it to a random address. This should be seen
as revocation. More precisely, when using her identity as described below in
Section 3.4, USR will send transactions of a specific form that return bitcoin
to the same multisg address of aIP and aU SR leaving a transaction output for
future authentications; if at any point USR or IP spend this output in a transaction that is not of the form of another authentication, then this transaction
is a TXREVOKE and the identity is seen as revoked. Finally, an OP RETURN contains
ha(i) .
U SR
The authentication token will be used in subsequent transactions; its amount
V will be calibrated to cover the costs of these transactions, see Section 3.7.
Note that the structure of TXPUBLISH is similar to that of the transactions in
the architecture of [20] as shown in Figure 1. Now, revocation can be performed
8

by both IP and by USR as both parties can destroy the authentication token
via a TXREVOKE .
Input Addresses
TXPUBLISH
aIP

Amounts Output Addresses
V + D + FPUBLISH

(i)

aU SR
(i)
MSIG1 2(aUSR , aIP)
OP RETURN ha(i)

Amounts
D
V

U SR

Fees:

FPUBLISH

Fig. 2. Structure of TXPUBLISH .

Remark 2. There are alternative zero-knowledge selective credential systems in
addition to that of Brands [8]. As discussed above, one advantage of using
Brands’ scheme is that its cryptographic primitives: discrete logarithms (in our
case on secp256k1) and hash functions are also primitives of Bitcoin, so we minimize the number of cryptographic assumptions necessary. Also, the commitments
of Brands are small enough (a compressed elliptic curve point of 33 bytes) to fit
in an OP RETURN. In contrast this is not the case for example for the commitments of the Camenisch-Lysyanskaya scheme which produces commitments of
670 bytes [24, Table 2].
Remark 3. One can imagine cases where a hostile or hacked IP uses the authentication token to obtain services acting as if it were the user, possibly with
the aim of harming the user’s reputation. However, when spending a multisig
output, it is visible which of the public keys one is signing by [7], thus such an
attack would be visible and, in fact, damage IP’s reputation.
3.4

Operational phase

The Operational phase is made up of two further Bitcoin transactions. We think
of certain outputs as being distinguished (or colored with a transferable semantic
meaning in the sense of Colored Coins [19, §9.2], [10]), corresponding to the
authentication token. The flow of this token will chain the transactions together
and ultimately to the creation of the identity in TXPUBLISH . We suppose SP informs
USR of what statement about her identity she needs to prove to authenticate.
Then we have the Bitcoin transactions:
TXREQUEST (Request for Service): USR creates a transaction where the in(i)
put is the MSIG1 2(aU SR , aIP ) from TXPUBLISH . One output is sent to aSP . One
(i)
output is sent back to MSIG1 2(aU SR , aIP ) and will serve as the authentication
token for future transactions. USR proves to SP the required Boolean statement about the Xj ’ s without revealing them as in Section 2.3 (see below for a
discussion of how this proof is transmitted and stored).
9

TXACCEPT (Acknowledgment of the Identity by SP): Upon validating the
proof of USR, checking that the authentication token is the result of a series of
TXREQUEST ’s each of whose input is the output of the previous chained back to a
TXPUBLISH , checking that TXPUBLISH was issued by a trusted IP, and verifying that
the multisig output of the most recent TXREQUEST has not been spent (namely that
there has not been a TXREVOKE ), SP accepts USR’s authentication and uses its
output from TXREQUEST to send bitcoins to aIP .

Input Addresses
TXREQUEST
(i)

Amounts Output Addresses

MSIG1 2(aU SR , aIP )

V

aSP
(i)
MSIG1 2(aU SR , aIP )
OP RETURN(proof-ref)

Amounts
FACCEPT + D
V − (FREQUEST + FACCEPT + D)
FREQUEST

Fees:
TXACCEPT
aSP

FACCEPT + D aIP

D
FACCEPT

Fees:

Fig. 3. The transactions that compose a typical authentication The inputs and outputs
highlighted in red are thought of as an authentication token that chain the user’s
transactions together and to TXPUBLISH .

Storage of proofs A careful reading of [8, Chapter 3] shows that the size of
the Brands proofs required to demonstrate a given Boolean statement about an
identity (X0 , . . . , Xn ) scales linearly in n, but also depends on the statement
being proven. We note that these proofs will generally be too large to be contained directly in an OP RETURN. Depending on the needs of USR and SP, we
propose three different mechanisms by which these proofs might be transmitted
and stored. 1. A user can store in the OP RETURN of TXREQUEST a link to a site where
the proofs are stored externally as well as a hash of the relevant contents of this
site. We denote this information by proof-ref. The hash will be included in mined
blocks, so the information on the site has the same protections against mutability
as other information on the blockchain. This is similar to how metadata is stored
in [10]. 2. A user that is very concerned about privacy, or who is proving a statement that is already sensitive, can transmit the Brands proofs entirely off-chain.
3. If one wants to avoid an off-chain storage mechanism, there are a number of
non-OP RETURN ways to store data in the Bitcoin blockchain (see [10]) such as
in a vanity address or using a fake 1 of N multisig. Alternatively, one can issue
a P2SH output in TXREQUEST with Pubkey Script OP HASH160 H(data) OP EQUAL
for which the corresponding input Sig Script is simply the data itself (see txid
db195e4bfcfb3cc6d47f8d6231cb59e543c31e01d196d557457bca0fa5c1aba0). While
10

there are still limits on how much data can be placed in a single input, through
using multiple inputs, one can store larger amounts of data in this fashion in
exchange for paying (much) higher transaction fees.
For the remainder of this article (and in Figure 3) we assume that proofs are
being referenced via a link and a hash in an OP RETURN.
Remark 4. TXACCEPT publicly shows that SP has accepted USR’s identity proofs
(i)
as valid, contributing to the reputation of aU SR (see Section 5). This is particularly useful if the proofs were conveyed off-chain or are otherwise unavailable.
TXACCEPT can also serve to alert IP that SP has used an identity that it provided,
and can even be a basis for a payment by SP for the issuing of this identity.

aIP

TX
A

SH
LI

B
X PU

T
(i)

CC
E

PT

aSP

MSIG1 2(aU SR , aIP )

TXREQUEST

Fig. 4. Scheme for users to prove their identity to service providers. An identity is
issued via a TXPUBLISH . Subsequently, each transaction takes as input the output of a
previous transaction (TXPUBLISH for the first authentication, TXREQUEST thereafter). For
simplicity, the OP RETURN output is not shown.

(i)

Remark 5. The transaction output of TXREQUEST to MSIG1 2(aU SR , aIP ) is necessary if the user wishes to reuse an identity, so that USR will have an UTXO tied
to her identity to spend in a subsequent TXREQUEST . This cyclic structure chains
the various authentications together permitting a verifier to trace any of them
back to the original identity issued in TXPUBLISH . Alternatively, USR can obtain a
(j)
new TXPUBLISH attached to a different address aU SR for each authentication if she
wishes to maintain a more complete anonymity in her authentications. However,
doing so is slightly more expensive as additional fees need to be paid for each
TXPUBLISH . Additionally, this limits the ability of a user to take advantage of the
reputation system we propose in Section 5. (See the discussion in the introduction on user empowerment over her level of privacy and compare to [8, Chapter
5.2.1], where Brands discusses the balance between reputation and anonymity
and proposes reuse solutions for his certificates.) In cases where the identity is
only designed to be used one time, this transaction output is unnecessary.
3.5

Limited use identities and setting Bitcoin values

Due to the chaining of authentications, when SP verifies the continued validity
of USR’s identity, the number of times this identity has been used can also be
11

calculated. Thus, if IP includes a use limit of N authentications with ha(i) in
U SR
the OP RETURN of TXPUBLISH , SP can check if this identity can still be used. Then,
(i)
IP should calibrate the amount of bitcoin, V , that is placed in the aU SR output
to cover these N authentications. As we saw in Figure 3 that each authentication
consumes FREQUEST +FACCEPT +D bitcoin before the authentication token is returned
to the user, and this returned token needs to have a value of at least D after the
last usage for the transaction to be accepted as standard, V must be at least
N (FREQUEST + FACCEPT + D) + D. Note, the fees required for a transaction to be
processed in a timely fashion slowly vary based on market forces, so IP should,
in practice, set V to be slightly larger than current market demands in case
miners increase their fees. Then, situations requiring IP to come online and top
up its users’ balances can be limited to cases of extreme changes in Bitcoin fees.
3.6

Coordinating multiple identities

Suppose a given user has obtained identities ha(1) and ha(2) from more than
U SR
U SR
one identity provider. We see that these identities can be coordinated.

Input Addresses
TXREQUEST-DOUBLE
(1)

MSIG1 2(aU SR , aIP )
(2)
MSIG1 2(aU SR , aIP )

Amounts Output Addresses
V1
V2

Amounts

aSP
(1)
MSIG1 2(aU SR , aIP )
(2)
MSIG1 2(aU SR , aIP )
OP RETURN(proof-ref)

2FACCEPT + 2D
V1 − (FREQUEST + FACCEPT + D)
V2 − (FREQUEST + FACCEPT + D)

Fees:

FREQUEST-DOUBLE

aIP 1
aIP 2

D
D

Fees:

FACCEPT-DOUBLE

TXACCEPT-DOUBLE
2FACCEPT + 2D

aSP

Fig. 5. Use of the authentication tokens of two identities together. The paths of these
tokens are colored in red and blue. The Brands proofs referenced in proof-ref are with
respect to the DLREP of equation 1

Concretely, suppose a user has been issued an identity by IP 1 consisting of
n
m
Q
Q
X
ha(1) =
gj j and another identity by IP 2 consisting of ha(2) =
(gu0 )Yu .
U SR

U SR

j=0

u=0

A service provider will be able to verify that each of these values correspond to
the respective TXPUBLISH transactions issued by the identity providers. Then
ha(1) · ha(2)
U SR

U SR

=

n
Y
j=0

12

Xj

gj

m
Y

(gu0 )Yu

u=0

(1)

is a DLREP commitment of the union of X0 , . . . Xn and Y0 , . . . , Ym . The user
can do proofs with selective disclosure using this commitment.
We preserve the chaining properties by having two transactions TXREQUEST-DOUBLE ,
which takes in the authentication tokens from both identities, and TXACCEPT-DOUBLE ,
which notifies both identity providers. The amounts used in these transactions
are chosen as in Figure 5 to ensure that a user’s balances decrease by no more
than what would have been the case for separate authentications with the two
identities, in keeping with the calibration of V in Section 3.5. (We will see in
Section 3.7, FREQUEST-DOUBLE ≤ 2FREQUEST and FACCEPT-DOUBLE ≤ 2FACCEPT , so adequate
fees are paid here; the change can be split between USR’s authentication tokens
for use in case of future Bitcoin fee increases, paid to SP, or left to the miners
to increase the speed of the transaction’s approvals). This schema can obviously
generalize to more than two identities.
Thus, a user can obtain many “micro-identities” - from the government,
from her bank, from her employer, from her health care provider - which she can
manage together without having to unnecessarily share information between her
identity providers. This is very much in the spirit of a PIMS [5].
Remark 6. The ability of USR to issue a transaction as in Figure 5, which requires signing with the private key corresponding to the address of each identity,
is already a weak way of establishing that these identities belong to the same
person. However, it is possible for malicious users to pool the private keys from
identities corresponding to distinct people. USR can provide stronger proof of
the connection of her identities if she shows as part of her proof in TXREQUEST that
h and h0 share common fields, such as name or social insurance number.
3.7

Estimates of cost

We now estimate the costs of the transactions we have introduced in the preceeding sections. As mentioned in Section 2, Bitcoin miners have flexibility in what
fees they demand. However, the current standard fee to have one’s transaction
processed in a timely manner is 360 satoshis, namely .0000036 bitcoins, per byte
[3]. Based on our schema, TXPUBLISH will contain one input, one P2PKH output,
one P2SH output, and an OP RETURN that contains one (compressed) point on
secp256k1. Hence the OP RETURN contains 33 bytes resulting in a total transaction size of roughly 267 bytes (see [7, Chapter 2] for more information on the
size of the various components of a Bitcoin transaction) costing .0009612 bitcoin.
At current market rates (June 2017, 1BTC=2720 USD), this corresponds to a
minimum transaction fee of approximately 2.61 USD. We compute the sizes and
costs of the other transactions similarly (based on proof-ref consisting of a 32
byte SHA-256 hash and a 30 byte url when necessary):
Transaction TXPUBLISH TXREVOKE TXREQUEST TXACCEPT TXREQUEST-DOUBLE TXACCEPT-DOUBLE
# Bytes
267
229
334
191
479
225
Cost (USD) 2.61
2.24
3.28
1.87
5.41
2.20
13

Then, building off Section 3.5, the total cost to issue an N use identity is the
value of the input issued by IP in TXPUBLISH . As in Figure 2, this is
Cost of N -use Id = V + D + FPUBLISH
= N (FREQUEST + FACCEPT + D) + 2D + FPUBLISH
≈ 5.2N + 2.6 USD.
Note that Bitcoin fees have increased substantially recently as the Bitcoin
community seeks consensus on how to scale block capacity. It is hoped that a
solution to this issue, such as an implementation of SegWit, will reduce fees [25].
3.8

Obtaining information about the Bitcoin network

Note that in the processing of an authentication, it is the service provider that
must verify the status of past Bitcoin transactions. Service providers with rigorous verification requirements, such as banks and insurance companies, should
run a full node or possibly a Simplified Payment Verification (SPV) client, see
[7]. Note the SPV protocol, which is already commonly used by vendors who
payment in Bitcoin, allows someone who downloads merely the 80 byte header
of each block to verify that a given transaction has been included in a block, upon
being provided with information related to that transaction by a full node. Hence,
a service provider running this protocol can verify that each of the TXREQUEST ’s
a user has issued, chained back to TXPUBLISH , counting the number of times the
identity has been used. This process also checks that the identity has not been
revoked as the SPV client sees that the network has accepted the most recent
transaction, so the transaction output controlled by the multisig between USR
and IP could not have already been spent in a TXREVOKE . Service providers with
less rigorous standards may retrieve their information from an online block explorer if they accept the additional risks of attacks on these sites.
3.9

Security considerations in case of blockchain failures

In Section 3.1, we place ourselves in a security model in which Bitcoin possesses
certain properties of an ideal blockchain. Here we explore the consequences on
our system when these properties are not satisfied.
Inconsistencies in the Bitcoin ledger: The integrity of the Bitcoin ledger
serves in our system to allow issuer oversight, concretely to allow the issuer to
revoke identities and to impose limits on the number of uses. On the other hand,
if there is a fork, a dishonest user can to continue to use an identity which
an issuer has revoked until the revocation transaction finally appears in the
dominant chain. If an attacker can issue a double spend (due to an accidental
fork, because the attacker has a large percentage of the mining power, etc), then
she can reuse her authentication token allowing her to exceed her usage limit.
Bitcoin network failure: We also rely on Bitcoin P2P infrastructure to
propagate the transactions that make up our protocol, and we rely on being able
to download information on previous Bitcoin transactions from nodes to check
14

the state of an identity. An attack on the P2P Bitcoin network can translate into
a denial of service attack on our system as one cannot issue TXPUBLISH , TXREQUEST ,
etc if the network does not relay them or if one cannot verify relevant previous
transactions. How vulnerable a service provider is to network attacks will depend
on how it receives information about the network as in Section 3.8. Note that,
regardless of this choice, user privacy is protected and impersonation is prevented
by the security of Brands’ protocols, see [8]. Even a service provider that obtains
its information from a block explorer can assure itself of the correctness of Brands
proofs and the validity of signatures.

4

Example use cases

In this section we propose a few use cases of our system that highlight its advantages versus existing systems.
4.1

University ID

We consider a university where the administration delivers identity credentials
to students, teachers, and staff. These credentials provide certificates of various
fields related to the user including their name, their status at the university
(student, teacher, etc), and their academic records. Individuals may use such
identities, revealing some (or none) of these fields, to authenticate themselves to
various university services such as the university pool or medical clinic.
Now imagine that a user wants to claim a discount on car insurance reserved for students with high GPAs. This student may need to coordinate her
university identity with a driver’s license issued by her local government. Then
she can selectively reveal information to the service provider, the insurer, using
the multi-IP protocols described in Section 3.6. If her status at the university
changes, her university identity can be revoked preventing her from performing
such authentications, even as her driver’s license identity remains valid.
4.2

Network of small museums

We imagine a group of small museums that form a partnership in which any
member of one museum is allowed a limited number of visits to the other museums. In this case, the user is a member of one of the museums, the identity
provider is the museum that issued the membership, and the other museums
are service providers. Then the user may selectively disclose fields such as her
membership status or category of membership. More sensitive information may
be included in the identity allowing the user to authenticate to tax authorities
which give a tax credit for museum memberships. The limit on the number of
visits is controlled through the methods of Section 3.5.
In contrast to the tax authorities, the security requirements of the museums
may allow them to obtain the transaction information from an online block explorer, completely outsourcing the costs of transmitting and storing information
15

to the Bitcoin network similar to how [1] uses the blockchain as a virtual server.
This may be substantially cheaper and more streamlined than traditional systems (namely, either for each of the museums to invest in infrastructure that
then has to be coordinated or for a single museum to set up infrastructure to
manage the entire system which may create conflicts of interest and be unacceptable to the other museums). Thus, our system allows the museums to create
a shared, neutral management space, maintaining transparency into exactly how
the data is stored and used, that minimizes infrastructure costs.

5

Building a reputation on the blockchain

We see in Section 4.2, in the case of our museums, that little infrastructure is
required of SP. Nonetheless, SP must be able to compute in secp256k1, perform
Bitcoin transactions, and be able to access the blockchain history, as discussed in
Sections 3.1 and 3.9. Imagine that some very lightweight service provider wants
to participate in this network, but does not have the security requirements, nor
the resources to justify performing these operations. For example, this may be
the case of a university pool in the university ID example of Section 4.
As all transactions are visible in the blockchain, a user can then simply direct
a lightweight service provider to her past transactions, which requires merely an
Internet connection, and prove that she controls the private key corresponding to
those transactions by issuing a signature. Then, if the lightweight service provider
is willing to trust the larger service providers that have already accepted the
user’s identity (e.g. if the university pool is willing to trust the campus medical
clinic in accepting that the user is a member of the university community),
it is not necessary to re-validate the relevant Brands proofs. As seen before
(see Section 3.6), a user may have had her identity established under different
Bitcoin addresses and proven to different service providers in such a way that
is unknown that these addresses belong to the same user. If the user has used
the two identities together in a TXREQUEST-DOUBLE , the light service provider may
be again willing to trust that the other service provider has verified these two
identities as corresponding to the same person. Alternatively, in situations with
lower security standards (as per Remark 6), the user can issue signatures for
both of the private keys corresponding to the identities used.
Moreover, the collection of transactions of a user, seen as having been accepted via TXACCEPT transactions, gradually forms a digital footprint of the user.
While some users will want to avoid reusing the same TXPUBLISH for multiple authentications for greater anonymity, for other users this digital presence, over
which the user has a great deal of direct control, can be a useful addition to the
online reputation they develop, for example through social media.

6

Conclusion

The Bitcoin blockchain is a global network, and by building on top of this network, we can take advantage of its existing infrastructure to reach a global scope
16

while minimizing overhead. Moreover, by placing an identity management system in this decentralized space, we have seen that we can strike a more equitable
balance between the rights and responsibilities of users and identity issuers.
Acknowledgment The work leading to this paper has received funding from
the European Community’s Framework Programme (FP7/2007- 2013) under
Grant Agreement n◦ 607049.

References
1. CryptID.
online, source code available at https://github.com/CryptidID/
Cryptid, Consulted 2017 April. http://cryptid.xyz/.
2. IDCoins, Consulted 2017 April. https://github.com/IDCoin/IDCoin.
3. Predicting Bitcoin fees for transactions, Consulted 2017 April.
https://
bitcoinfees.21.co/.
4. Estonian e-residency, Consulted 2017 March.
https://e-estonia.com/eresidents/about/.
5. Serge Abiteboul, Benjamin André, and Daniel Kaplan. Managing your digital life.
Commun. ACM, 58(5):32–35, April 2015.
6. Muneeb Ali, Jude Nelson, Ryan Shea, and Michael J. Freedman. Blockstack: A
global naming and storage system secured by blockchains. In 2016 USENIX Annual
Technical Conference (USENIX ATC ’16), Denver, CO, USA, June 22-24, 2016.
Proceedings, pages 181–194, 2016.
7. Andreas M. Antonopoulos. Mastering Bitcoin. O’Reilly Media, Sebastopol, California, 2015. ISBN: 978-1-449-37404-4.
8. Stefan Brands. Rethinking Public Key Infrastructures and Digital Certificates
(Building in Privacy). MIT Press, Cambridge, MA, USA, 2000.
9. Jan Camenisch, Anja Lehmann, and Gregory Neven. Electronic identities need
private credentials. IEEE Security & Privacy, 10(1):80–83, 2012.
10. Flavien Charlon. Open assets protocol (oap/1.0). Online, https://github.com/
OpenAssets/open-assets-protocol/blob/master/specification.mediawiki,
2011.
11. Ian Miers Christina Garman, Matthew Green. Accountable privacy for decentralized anonymous payments. In Financial Cryptography and Data Security, 2016.
12. The Bitcoin Core developers.
Bitcoin transactions primitives code, Consulted 2017 March.
https://github.com/bitcoin/bitcoin/blob/0.14/src/
primitives/transaction.h.
13. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Elisabeth Oswald and Marc Fischlin, editors,
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, volume 9057 of Lecture Notes in Computer
Science, pages 281–310. Springer, 2015.
14. Thomas Hardjono, Ned Smith, and Alex (Sandy) Pentland. Anonymous identities for permissioned blockchains. http://www.the-blockchain.com/docs/MITChainAnchor-DRAFT.pdf, January 2016.
15. Steven Hay. Bitcoin vs ethereum: Cryptocurrency comparison, 2017 March. https:
//99bitcoins.com/bitcoin-vs-ethereum-cryptocurrency-comparison/.

17

16. Ori Jacobovitz. Blockchain for identity management. https://www.cs.bgu.ac.il/
%7Efrankel/TechnicalReports/2016/16-02.pdf, December 2016.
17. Yabing Liu, Will Tome, Liang Zhang, David R. Choffnes, Dave Levin, Bruce M.
Maggs, Alan Mislove, Aaron Schulman, and Christo Wilson. An end-to-end measurement of certificate revocation in the web’s PKI. In Proceedings of the 2015
ACM Internet Measurement Conference, IMC 2015, Tokyo, Japan, October 28-30,
2015, pages 183–196, 2015.
18. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Online, http:
//bitcoin.org/bitcoin.pdf, 2008.
19. Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven
Goldfeder. Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press, 2016.
20. Juliana Nazaré, Kim Hamilton, and Philipp Schmidt. Digital certificates project.
online, source code available at https://github.com/digital-certificates,
Consulted 2016 December. http://certificates.media.mit.edu.
21. Office of the Privacy Commissionner of Canada. Privacy and your reputation who shapes your identity online?, 2012.
22. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol
in asynchronous networks. In Jean-Sébastien Coron and Jesper Buus Nielsen,
editors, 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 II, volume 10211 of Lecture
Notes in Computer Science, pages 643–673. Springer, 2017.
23. Giulio Prisco.
Estonian government partnerts with bitnation to offer blockchain notarization services to e-residents, 2015 November.
https://bitcoinmagazine.com/articles/estonian-government-partnerswith-bitnation-to-offer-blockchain-notarization-services-to-eresidents-1448915243/.
24. Security Team. Specification of the identity mixer cryptographic library version
2.3.0. Technical Report RZ 3730, IBM Research, Computer Science Dept, IBM
Research – Zurich, Switzerland, 2010. 48 pages.
25. Kyle Torpey. Are bitcoin miners making more money off small blocks?, 2017
March. https://bitcoinmagazine.com/articles/are-bitcoin-miners-makingmore-money-small-blocks/.
26. Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger,
EIP-150 REVISION (030c1b5 - 2017-07-10).
https://ethereum.github.io/
yellowpaper/paper.pdf.
27. Danny Yang, Jack Gavigan, and Zooko Wilcox-O’Hearn. Survey of confidentiality and privacy preserving technologies for blockchains. https://z.cash/static/
R3 Confidentiality and Privacy Report.pdf, November 2016.
28. Guy Zyskind, Oz Nathan, and Alex Pentland. Decentralizing privacy: Using
blockchain to protect personal data. In 2015 IEEE Symposium on Security and
Privacy Workshops, SPW 2015, San Jose, CA, USA, May 21-22, 2015, pages
180–184, Los Alamitos, CA, USA, 2015. IEEE Computer Society.

18

