IACR News item: 30 September 2014
Juan Garay, Aggelos Kiayias, Nikos Leonardos
ePrint ReportIn this work, we extract and analyze the core of the Bitcoin
protocol, which we term the Bitcoin {\\em backbone}, and prove two of
its fundamental properties which we call {\\em common prefix} and {\\em chain
quality}. Our proofs hinge
on appropriate and novel assumptions on the ``hashing power\'\' of the
adversary relative to network synchronicity; our results are shown
to be tight under high synchronization.
Next, we
propose and analyze applications that can be built ``on top\'\' of the
backbone protocol, specifically focusing on Byzantine agreement (BA)
and on the notion of a public transaction ledger.
Regarding BA, we observe that Nakamoto\'s suggestion falls short of solving it,
and present a simple alternative
which works assuming that the adversary\'s
hashing power is bounded by $1/3$.
The public transaction ledger
captures the essence of Bitcoin\'s operation as a cryptocurrency,
in the sense that it guarantees the
``liveness\'\' and ``persistence\'\' of committed transactions.
Based on this notion
we describe and analyze the Bitcoin system
as well as
a more elaborate BA protocol,
proving them secure assuming high network synchronicity and that the
adversary\'s hashing power is strictly less than $1/2$, while the
adversarial bound needed for security decreases as the network desynchronizes.
Additional news items may be found on the IACR news page.