From: Peter Todd <pete@petertodd•org>
To: bitcoin-development@lists•sourceforge.net
Cc: Andrew Miller <amiller@cs•umd.edu>
Subject: Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
Date: Sun, 21 Dec 2014 19:11:37 -0500 [thread overview]
Message-ID: <20141222001136.GA10165@savin.petertodd.org> (raw)
In-Reply-To: <20141220144800.GA26284@savin.petertodd.org>
[-- Attachment #1: Type: text/plain, Size: 2832 bytes --]
On Sat, Dec 20, 2014 at 09:48:01AM -0500, Peter Todd wrote:
Andrew Miller asked me to publish the following to the mailing list on his
behalf: (https://twitter.com/socrates1024/status/546819355565391872)
One of the main points in this note is that you can use a
"proof-of-publication" system to implement an "anti-replay" system.
However this isn't true - at least not given the description of
proof-of-(non)-publication in 2) and the definition of "anti-replay"
given here.
In 2), proof-of-*non*-publication allows you to prove that *some
specific message* has never been published. You can imagine having a
function ProveNotPublished(m), which proves "message m was not
published."
However, the anti-replay mechanism is about proving that *no* message
satisfying some property has been published. Hence
VerifyAntiReplaySig(m, p, s) checks that "for all possible messages m'
(distinct from m), AntiReplaySign(m', p) has not been called."
This isn't *just* splitting hairs, this distinction is actually
relevant for analyzing several cryptocurrency designs. You can imagine
extending the definition of proof-of-(non)-publication to take in some
predicate P, so that you can prove "no message m such that P(m) holds
has ever been published." However, to do this efficiently requires
anticipating some classes of P and building some appropriate indices.
- As a baseline, as long as you have the whole blockchain available,
you can scan through the entire blockchain and evaluate P for every
transaction, but this is pretty inefficient.
- Other tradeoffs are available if you are willing to trust some
(quora of) servers to maintain indices for you
- Bitcoin's UTXO set effectively supports a predicate for each txout,
where P(x) = "x is a valid tranasction that spends <txout>"
- Ethereum contracts, in a sense, allow for general purpose contracts
to 'build-your-own" index. On the other hand its key-value store
doesn't support range queries, so it's not necessarily "universal" or
as expressive as SQL, for example.
But the point isn't to argue about design choices and tradeoffs in
this thread. The main point I want to make is:
*Indexes and Validation Matter!*
The classic "proof-of-publication" system is to embed opaque data (as
far as bitcoin miners are concerned) in transactions using OP_RETURN.
A significance of establishing "proof-of-publication" as a universal
underlying primitive is that this OP_RETURN trick is then sufficient
for anything you might want. But part of what Bitcoin provides is
indexing and validation/exclusion, and this is important for
supporting efficient anti-replay proofs. Proof-of-(non)-publication
alone isn't sufficient for this.
--
'peter'[:-1]@petertodd.org
00000000000000000a7b40becd0babbd64ec49b8b34823fb4f4b081c95188b66
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
next prev parent reply other threads:[~2014-12-22 0:11 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
2015-01-06 11:03 ` joliver
2014-12-22 20:05 ` Adam Back
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20141222001136.GA10165@savin.petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=amiller@cs$(echo .)umd.edu \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox