public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-12  9:05 Peter Todd
  2014-12-12 12:25 ` Gareth Williams
                   ` (2 more replies)
  0 siblings, 3 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-12  9:05 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 17259 bytes --]

Introduction
============

While not a new concept proof-of-publication is receiving a significant
amount of attention right now both as an idea, with regard to the
embedded consensus systems that make use of it, and in regard to the
sidechains model proposed by Blockstream that rejects it. Here we give a
clear definition of proof-of-publication and its weaker predecessor
timestamping, describe some usecases for it, and finally dispel some of
the common myths about it.


What is timestamping?
=====================

A cryptographic timestamp proves that message m existed prior to some
time t.

This is the cryptographic equivalent of mailing yourself a patentable
idea in a sealed envelope to establish the date at which the idea
existed on paper.

Traditionally this has been done with one or more trusted third parties
who attest to the fact that they saw m prior to the time t. More
recently blockchains have been used for this purpose, particularly the
Bitcoin blockchain, as block headers include a block time which is
verified by the consensus algorithm.


What is proof-of-publication?
=============================

Proof-of-publication is what solves the double-spend problem.

Cryptographic proof-of-publication actually refers to a few closely
related proofs, and practical uses of it will generally make use of more
than one proof.


Proof-of-receipt
----------------

Prove that every member p in of audience P has received message m. A
real world analogy is a legal notice being published in a major
newspaper - we can assume any subscriber received the message and had a
chance to read it.


Proof-of-non-publication
------------------------

Prove that message m has *not* been published. Extending the above real
world analogy the court can easily determine that a legal notice was not
published when it should have been by examining newspaper archives. (or
equally, *because* the notice had not been published, some action a
litigant had taken was permissable)


Proof-of-membership
-------------------

A proof-of-non-publication isn't very useful if you can't prove that
some member q is in the audience P. In particular, if you are to
evaluate a proof-of-membership, q is yourself, and you want assurance
you are in that audience. In the case of our newspaper analogy because
we know what today's date is, and we trust the newspaper never to
publish two different editions with the same date we can be certain we
have searched all possible issues where the legal notice may have been
published.


Real-world proof-of-publication: The Torrens Title System
---------------------------------------------------------

Land titles are a real-world example, dating back centuries, with
remarkable simularities to the Bitcoin blockchain. Prior to the torrens
system land was transferred between owners through a chain of valid
title deeds going back to some "genesis" event establishing rightful
ownership independently of prior history. As with the blockchain the
title deed system has two main problems: establishing that each title
deed in the chain is valid in isolation, and establishing that no other
valid title deeds exist. While the analogy isn't exact - establishing
the validity of title deeds isn't as crisp a process as simple checking
a cryptographic signature - these two basic problems are closely related
to the actions of checking a transaction's signatures in isolation, and
ensuring it hasn't been double-spent.

To solve these problems the Torrens title system was developed, first in
Australia and later Canada, to establish a singular central registry of
deeds, or property transfers. Simplifying a bit we can say inclusion -
publication - in the official registery is a necessary pre-condition to
a given property transfer being valid. Multiple competing transfers are
made obvious, and the true valid transfer can be determined by whichever
transfer happened first.

Similarly in places where the Torrens title system has not been adopted,
almost always a small number of title insurance providers have taken on
the same role. The title insurance provider maintains a database of all
known title deeds, and in practice if a given title deed isn't published
in the database it's not considered valid.


Common myths
============

Proof-of-publication is the same as timestamping
------------------------------------------------

No. Timestamping is a significantly weaker primitive than
proof-of-publication. This myth seems to persist because unfortunately
many members of the Bitcoin development and theory community - and even
members of the Blockstream project - have frequently used the term
"timestamping" for applications that need proof-of-publication.


Publication means publishing meaningful data to the whole world
---------------------------------------------------------------

No. The data to be published can often be an otherwise meaningless
nonce, indistinguishable from any other random value. (e.g. an ECC
pubkey)

For example colored coins can be implemented by committing the hash of
the map of colored inputs to outputs inside a transaction. These maps
can be passed from payee to payor to prove that a given output is
colored with a set of recursive proofs, as is done in the author's
Smartcolors library. The commitment itself can be a simple hash, or even
a pay-to-contract style derived pubkey.

A second example is Zerocash, which depends on global consensus of a set
of revealed serial numbers. As this set can include "false-positives" -
false revealed serial numbers that do not actually correspond to a real
Zerocash transaction - the blockchain itself can be that set. The
Zerocash transactions themselves - and associated proofs - can then be
passed around via a p2p network separate from the blockchain itself.
Each Zerocash Pour proof then simply needs to specify what set of
priorly evaluated proofs makes up its particular commitment merkle tree
and the proofs are then evaluated against that proof-specific tree. (in
practice likely some kind of DAG-like structure) (note that there is a
sybil attack risk here: a sybil attack reduces your k-anonymity set by
the number of transactions you were prevented from seeing; a weaker
proof-of-publication mechanism may be appropriate to prevent that sybil
attack).

The published data may also not be meaningful because it is encrypted.
Only a small community may need to come to consensus about it; everyone
else can ignore it. For instance proof-of-publication for decentralized
asset exchange is an application where you need publication to be
timely, however the audience may still be small. That audience can share
an encryption key.


Proof-of-publication is always easy to censor
---------------------------------------------

No, with some precautions. This myth is closely related to the above
idea that the data must be globally meaningful to be useful. The colored
coin and Zerocash examples above are cases where censoring the
publication is obviously impossible as it can be made prior to giving
anyone at all sufficient info to determine if the publicaiton has been
made; the data itself is just nonces.

In the case of encrypted data the encryption key can also often be
revealed well after the publication has been made. For instance in a
Certificate Transparency scheme the certificate authority (CA) may use
proof-of-publication to prove that a certificate was in a set of
certificates. If that set of certificates is hashed into a merkelized
binary prefix tree indexed by domain name the correct certificate for a
given domain name - or lack thereof - is easily proven. Changes to that
set can be published on the blockchain by publishing successive prefix
tree commitments.

If these commitments are encrypted, each commitment C_i can also commit
to the encryption key to be used for C_{i+1}. That key need not be
revealed until the commitment is published; validitity is assured as
every client knows that only one C_{i+1} is possible, so any malfeasance
is guaranteed to be revealed when C_{i+2} is published.

Secondly the published data can be timelock encrypted with timelocks
that take more than the average block interval to decrypt. This puts
would-be censoring miners into a position of either delaying all
transactions, or accepting that they will end up mining publication
proofs. The only way to circumvent this is highly restrictive
whitelisting.


Proof-of-publication is easier to censor than (merge)-mined sidechains
----------------------------------------------------------------------

False under all circumstances. Even if the publications use no
anti-censorship techniques to succesfully censor a proof-of-publication
system at least 51% of the total hashing power must decide to censor it,
and they must do so by attacking the other 49% of hashing power -
specifically rejecting their blocks. This is true no matter how "niche"
the proof-of-publication system is - whether it is used by two people or
two million people it has the same security.

On the other hand a (merge)-mined sidechain with x% of the total hashing
power supporting it can be attacked at by anyone with >x% hashing power.
In the case of a merge-mined sidechain this cost will often be near zero
- only by providing miners with a significant and ongoing reward can the
marginal cost be made high. In the case of sidechains with niche
audiences this is particularly true - sidechain advocates have often
advocated that sidechains be initially protected by centralized
checkpoints until they become popular enough to begin to be secure.

Secondly sidechains can't make use of anti-censorship techniques the way
proof-of-publication systems can: they inherently must be public for
miners to be able to mine them in a decentralized fashion. Of course,
users of them may use anti-censorship techniques, but that leads to a
simple security-vs-cost tradeoff between using the Bitcoin blockchain
and a sidechain. (note the simularity to the author's treechains
proposal!)


Proof-of-publication can be made expensive
------------------------------------------

True, in some cases! By tightly constraining the Bitcoin scripting
system the available bytes for stenographic embedment can be reduced.
For instance P2SH^2 requires an brute force exponentially increasing
amount of hashes-per-byte-per-pushdata. However this is still
ineffective against publishing hashes, and to fully implement it -
scriptSigs included - would require highly invasive changes to the
entire scripting system that would greatly limit its value.


Proof-of-publication can be outsourced to untrusted third-parties
-----------------------------------------------------------------

Timestamping yes, but proof-of-publication no.

We're talking about systems that attempt to publish multiple pieces of
data from multiple parties with a single hash in the Bitcoin blockchain,
such as Factom.  Essentially this works by having a "child" blockchain,
and the hash of that child blockchain is published in the master Bitcoin
blockchain. To prove publicaiton you prove that your message is in that
child chain, and the child chain is itself published in the Bitcoin
blockchain.  Proving membership is possible for yourself by determining
if you have the contents corresponding to the most recent child-chain
hash.

The problem is proving non-publication. The set of all *potential*
child-chain hashes must be possible to obtain by scanning the Bitcoin
blockchain. As a hash is meaningless by itself, these hashes must be
signed. That introduces a trusted third-party who can also sign an
invalid hash that does not correspond to a block and publish it in the
blockchain. This in turn makes it impossible for anyone using the child
blockchain to prove non-publication - they can't prove they did not
publish a message because the content of *all* child blockchains is now
unknown.

In short, Factom and systems like it rely on trusted third parties who
can put you in a position where you can't prove you did not commit
fraud.


Proof-of-publication "bloats" the blockchain
--------------------------------------------

Depends on your perspective.

Systems that do not make use of the UTXO are no different technically
than any other transaction: they pay fees to publish messages to the
Bitcoin blockchain with no amortized increase in the UTXO set. Some
systems do grow the UTXO set - a potential scaling problem as currently
that all full nodes must have the entire UTXO set - although there are a
number of existing mechanisms and proposals to mitigate this issue such
as the (crippled) OP_RETURN scriptPubKey format, the dust rule, the
authors TXO commitments, UTXO expiry etc.

From an economic point of view proof-of-publication systems compete with
other uses of the blockchain as they pay fees; supply of blockchain
space is fixed so the increased demand must result in a higher
per-transaction price in fees. On the other hand this is true of *all*
uses of the blockchain, which collectively share the limited transaction
capacity. For instance Satoshidice and similar sites have been widely
condemned for doing conventional transactions on Bitcoin when they could
have potentially used off-chain transactions.

It's unknown what the effect on the Bitcoin price will actually be. Some
proof-of-publication uses have nothing to do with money at all - e.g.
certificate transparency. Others are only indirectly related, such as
securing financial audit logs such as merkle-sum-trees of total Bitcoins
held by exchanges. Others in effect add new features to Bitcoin, such as
how colored coins allows the trade of assets on the blockchain, or how
Zerocash makes Bitcoin transactions anonymous. The sum total of all
these effects on the Bitcoin price is difficult to predict.

The authors belief is that even if proof-of-publication is a
net-negative to Bitcoin as it is significantly more secure than the
alternatives and can't be effectively censored people will use it
regardless of effects to discourage them through social pressure. Thus
Bitcoin must make technical improvements to scalability that negate
these potentially harmful effects.


Proof-of-publication systems are inefficient
--------------------------------------------

If you're talking about inefficient from the perspective of a full-node
that does full validation, they are no different than (merge)-mined
sidechain and altcoin alternatives. If you're talking about efficiency
from the perspective of a SPV client, then yes, proof-of-publication
systems will often require more resources than mining-based
alternatives.

However it must be remembered that the cost of mining is the
introduction of a trusted third party - miners. Of course, mined
proof-of-publication has miners already, but trusting those miners to
determine the meaning of that data places significantly more trust in
them than mearly trusting them to create consensus on the order in which
data is published.

Many usecases involve trusted third-parties anyway - the role of
proof-of-publication is to hold those third-parties to account and keep
them honest. For these use-cases - certificate transparency, audit logs,
financial assets - mined alternatives simply add new trusted third
parties and points of failure rather than remove them.

Of course, global consensus is inefficient - Bitcoin itself is
inefficient. But this is a fundemental problem to Bitcoin's architecture
that applies to all uses of it, a problem that should be solved in
general.


Proof-of-publication needs "scamcoins" like Mastercoin and Counterparty
-----------------------------------------------------------------------

First of all, whether or not a limited-supply token is a "scam" is not a
technical question. However some types of embedded consensus systems, a
specific use-case for proof-of-publication, do require limited-supply
tokens within the system for technical reasons, for instance to support
bid orders functionality in decentralized marketplaces.

Secondly using a limited-supply token in a proof-of-publicaton system is
what lets you have secure client side validation rather than the
alternative of 2-way-pegging that requires users to trust miners not to
steal the pegged funds. Tokens also do not need to be, economically
speaking, assets that can appreciate in value relative to Bitcoin;
one-way-pegs where Bitcoins can always be turned into the token in
conjunction with decentralized exchange to buy and sell tokens for
Bitcoins ensure the token value will always closely approximate the
Bitcoin value as long as the protocol itself is considered valuable.

Finally only a subset of proof-of-publication use-cases involve tokens
at all - many like colored coins transact directly to and from Bitcoin,
while other use-cases don't even involve finance at all.

-- 
'peter'[:-1]@petertodd.org
00000000000000000681f4e5c84bc0bf7e6c5db8673eef225da652fbb785a0de

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

^ permalink raw reply	[flat|nested] 30+ messages in thread
* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-16 20:28 paul snow
  0 siblings, 0 replies; 30+ messages in thread
From: paul snow @ 2014-12-16 20:28 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 3668 bytes --]

Peter provides an excellent summary of Proof of Publication, which starts
with defining it as being composed of a solution to the double spend
problem.  He requires Proof-of-receipt (proof every member of p in audience
P has received a message m), Proof-of-non-publication (proof a message m
has not been published to an audience P), and Proof-of-membership (proof
some q is a member of P).

He goes on to state (curiously) that Factom cannot provide Proof of
Publication.

Proof of Audience
=============

Let's first satisfy the easier proofs. A Factom user can know they are in
the Factom audience if they have access to the Bitcoin Blockchain,
knowledge of Factom's first anchor (Merkle root stored in the blockchain)
and the Factom network for distributing Factom's structures.  They can
pretty much know that they are in the Audience.

Proof of Receipt
============

Proof of receipt is also pretty easy for the Factom user.  User submit
entries, and Factom publishes a Merkle Root to the Bitcoin Blockchain.  The
Merkle proof to the entry proves receipt.  To get the Merkle proof requires
access to Factom structures, which all in the audience have access to by
definition.  But the proof itself only requires the blockchain.

At this point the user can have a Merkle proof of their entry rooted in the
blockchain.

Proof of non-publication
==================

Last, can the Factom user have a  Proof-of-non-publication.  Well,
absolutely.  The Factom state limits the public keys that can be used to
write the anchors in the blockchain.  Entries that are not written with
those public keys are discounted out of hand.  Just like publishing in Mad
Magazine does not qualify if publishing a notice in the New York Times is
the standard.

The complaint Peter has that the user cannot see all the "child chains"
(what we call Factom Chains) is invalid.  The user can absolutely see all
the Directory Blocks (which documents all Factom Chains) if they have
access to Factom. But the user doesn't need to prove publication in all
chains.  Some of those chains are like Car Magazines, Math Textbooks,
Toaster manuals, etc. Without restricting the domain of publication there
is no proof of the negative. The negative must be proved in the standard of
publication, i.e. the user's chain.  And the user can in fact know their
chain, and can enumerate their chain, without regard to most of the other
data in Factom.

Peter seems to be operating under the assumption that the audience for a
Factom user must necessarily be limited to information found in the
blockchain.  Yet the user certainly should have access to Factom if they
are a Factom user.  Factom then is no different from the New York Times,
and the trust in Factom is less. As Peter says himself, he has to trust the
New York Times doesn't publish multiple versions of the same issue. The
user of the New York Times would have no way to know if there were other
versions of an issue outside of looking at all New York Times issues ever
published.

Factom on the other hand documents their "issues" on the blockchain.  Any
fork in publication is obvious as it would require different Bitcoin
addresses to be used, and the blocks would have to have validating
signatures of majorities of all the Factom servers. As long as a fork in
Factom can be clearly identified, and no fork exists, proof of the negative
is assured.  And upon a fork, one must assume the users will specify which
fork should be used.

Proof of publication does not require a system that cannot fork, since no
such non-trivial system exists.  What is required is that forks can be
detected, and that a path can be chosen to move forward.

[-- Attachment #2: Type: text/html, Size: 4077 bytes --]

^ permalink raw reply	[flat|nested] 30+ messages in thread
* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-17 22:20 paul snow
  0 siblings, 0 replies; 30+ messages in thread
From: paul snow @ 2014-12-17 22:20 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 3831 bytes --]

[[Since I sent this while the List Server was down, it didn't actually go
to everyone.  Forgive me if you ended up with two copies.]]

Peter provides an excellent summary of Proof of Publication, which starts
with defining it as being composed of a solution to the double spend
problem.  He requires Proof-of-receipt (proof every member of p in audience
P has received a message m), Proof-of-non-publication (proof a message m
has not been published to an audience P), and Proof-of-membership (proof
some q is a member of P).

He goes on to state (curiously) that Factom cannot provide Proof of
Publication.

Proof of Membership
================

Let's first satisfy the easier proofs. A Factom user can know they are a
member of the Factom audience if they have access to the Bitcoin
Blockchain, knowledge of Factom's first anchor (Merkle root stored in the
blockchain) and the Factom network for distributing Factom's structures.
They can pretty much know that they are in the Audience.

Proof of Receipt
============

Proof of receipt is also pretty easy for the Factom user.  User submit
entries, and Factom publishes a Merkle Root to the Bitcoin Blockchain.  The
Merkle proof to the entry proves receipt.  To get the Merkle proof requires
access to Factom structures, which all in the audience have access to by
definition.  But the proof itself only requires the blockchain.

At this point the user can have a Merkle proof of their entry rooted in the
blockchain.

Proof of non-publication
==================

Last, can the Factom user have a  Proof-of-non-publication?  Well,
absolutely.  The Factom state limits the public keys that can be used to
write the anchors in the blockchain.  Transactions in Bitcoin that are not
signed with those public keys are discounted out of hand.  Just like
publishing in Mad Magazine does not qualify if publishing a notice in the
New York Times is the standard.

The complaint Peter has that the user cannot see all the "child chains"
(what we call Factom Chains) is invalid.  The user can absolutely see all
the Directory Blocks (which documents all Factom Chains) if they have
access to Factom. But the user doesn't need to prove publication in all
chains.  Some of those chains are like Car Magazines, Math Textbooks,
Toaster manuals, etc. Without restricting the domain of publication there
is no proof of the negative. The negative must be proved in the standard of
publication, i.e. the user's chain.  And the user can in fact know their
chain, and can enumerate their chain, without regard to most of the other
data in Factom.

Peter seems to be operating under the assumption that the audience for a
Factom user must necessarily be limited to information found in the
blockchain.  Yet the user certainly should have access to Factom if they
are a Factom user.  Factom then is no different from the New York Times,
and the trust in Factom is less. As Peter says himself, he has to trust the
New York Times doesn't publish multiple versions of the same issue. The
user of the New York Times would have no way to know if there were other
versions of an issue outside of looking at all New York Times issues ever
published.

Factom on the other hand documents their "issues" on the blockchain.  Any
fork in publication is obvious as it would require different Bitcoin
addresses to be used, and the blocks would have to have validating
signatures of majorities of all the Factom servers. As long as a fork in
Factom can be clearly identified, and no fork exists, proof of the negative
is assured.  And upon a fork, one must assume the users will specify which
fork should be used.

Proof of publication does not require a system that cannot fork, since no
such non-trivial system exists.  What is required is that forks can be
detected, and that a path can be chosen to move forward.

[-- Attachment #2: Type: text/html, Size: 5373 bytes --]

^ permalink raw reply	[flat|nested] 30+ messages in thread
end of thread, other threads:[~2015-01-06 11:03 UTC | newest]

Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-12-12  9:05 [Bitcoin-development] Setting the record straight on Proof-of-Publication Peter Todd
2014-12-12 12:25 ` Gareth Williams
2014-12-12 17:04   ` Alex Mizrahi
     [not found]     ` <CAOG=w-v3qjG3zd_WhfFU-OGnsHZEuYvY82eL4GqcdgY6np5bvA@mail.gmail.com>
2014-12-12 17:50       ` Alex Mizrahi
2014-12-13 13:32         ` Gareth Williams
2014-12-15  4:52           ` Peter Todd
2014-12-17 11:55             ` Gareth Williams
2014-12-21  6:12               ` Peter Todd
2014-12-15  4:17         ` Peter Todd
2014-12-12 13:41 ` odinn
2014-12-12 14:17   ` Justus Ranvier
2014-12-15  4:59   ` Peter Todd
2014-12-17  1:16     ` odinn
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
     [not found]   ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
2014-12-21  5:52     ` Peter Todd
     [not found]       ` <CAOG=w-tZke--6OsqNjJhE9SOdCwdZYZM8iz1VBTFziegt9UZWw@mail.gmail.com>
2014-12-21  7:01         ` Peter Todd
     [not found]           ` <CAOG=w-s1_VXJAKxBpMOK=B50qnHjxSe4J=vwwSfFPRz0_Cb9rA@mail.gmail.com>
2014-12-21 15:32             ` Peter Todd
2014-12-21 11:25       ` Jorge Timón
2014-12-21 16:07         ` Peter Todd
2014-12-21 19:39           ` Jorge Timón
2014-12-21 10:01   ` Adam Back
2014-12-21 15:29     ` Peter Todd
2014-12-21 13:49   ` paul snow
2014-12-21 15:22     ` Peter Todd
2014-12-21 15:41       ` paul snow
2014-12-22  0:11   ` Peter Todd
2015-01-06 11:03     ` joliver
2014-12-22 20:05   ` Adam Back
2014-12-16 20:28 [Bitcoin-development] Setting the record straight on Proof-of-Publication paul snow
2014-12-17 22:20 paul snow

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox