Subject: Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles

From: Peter Todd <[email-masked]>
Date: Sun, 21 Dec 2014 10:22:56 -0500

On Sun, Dec 21, 2014 at 07:49:17AM -0600, paul snow wrote:
> On Dec 20, 2014 8:49 AM, "Peter Todd" <[email-masked]> wrote:
> >
> > However the converse is not possible: anti-replay cannot be used to
> implement proof-of-publication. Knowing that no conflicting message exists
> says nothing about who be in posession of that message, or indeed, any
> message at all. Thus anti-replay is not sufficient to implement other uses
> of proof-of-publication such as decentralized exchange³.
> 
> How does proof of publication prove who is in possession of that message?
> Or of any message at all?

With the blockchain you prove the message in in the blockchain; anyone
in posession of the blockchain will be in posession of the message.
Secondly determining if you are in posession of the blockchain is
possible subject to the usual considerations about attacker size,
whether or not your local clock is up-to-date, etc.

> The data written in an anti-replay system and
> the data written in a proof of publication system differs in that you can't
> repeat data in an anti-replay system according to some understanding of the
> rules of the meaning of the data (if I am following your description
> correctly).

I'm not sure you understand what an anti-replay system is; data isn't
written to them; they're an abstract mathematical model that may be
actually implemented in a variety of ways.

Now it is true that any conceivable implementation must involve some
type of storage, but that storage can easily 100% local to the
anti-replay oracle and need not store the data itself. For instance a
trusted computer in a vault that maintains an extremely large bloom
filter of previously used keys would be a perfectly reasonable
implementation.

> If the data itself defines possession, the "ownership of the message" (it
> isn't even clear to me what you mean by that phrase) isn't defined by
> either proof, but by the message itself.  And the message itself isn't
> constrained by either to prohibit proving ownership (what ever you mean by
> that).

Wait, where did I say "ownership of the message"? What you quoted above
says *posession*, which != ownership.

> Of course, I do assume I can test a message (or a set of messages sharing
> some feature like a particular input on a transaction) as being publishable
> in an anti-replay system without actually publishing it.  That does allow
> one to prove non-publishing.  You can determine if a message exists that
> would preclude the publishing of a message; the very purpose of an
> anti-replay proof.
>
> And I would assert that such a search (i.e. the idea that such a search has
> meaning in a anti-replay system) is already incorporating the assumption
> that such a search is possible and must be possible for an anti-replay
> system.

You're confused about what an anti-replay system actually is - you're
really talking about a specific implementation of one based on
proof-of-publication, not the concept itself.

-- 
'peter'[:-1]@petertodd.org
00000000000000001b728df6414af5ef95388557f1c3e5d29c569d7636b93681