[Bitcoin-development] Setting the record straight on Proof-of-Publication

[Bitcoin-development] Setting the record straight on Proof-of-Publication

[paul snow]

[-- 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 --]

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Peter Todd]

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

On Wed, Dec 17, 2014 at 10:55:28PM +1100, Gareth Williams wrote:
> > I covered this in my original post: 1-way-pegs allow the creation of new
> > valuable tokens without those tokens being useful for speculation.
> 
> I stand corrected. A permanent 1-way-peg is sufficient to preserve
> scarcity; "nothing else can do that" WRT 2-way-pegs was overreaching.

Yup.

> I still don't see what "2-way-peg vs. 1-way-peg" has to do with
> "embedded consensus vs. blockchain consensus" though, and feel it
> disingenious to conflate them.

1-way-pegs don't require the Bitcoin protocol to change; 2-way-pegs do.

> Blockchain consensus (eg. sidechains) can utilise either mechanism,
> 1-way-peg or 2-way-peg. Arguments in favour of 1-way-peg are
> interesting, but they're ultimatley just arguments in favour of one
> type of sidechain over another.

No, they're in favor of systems that are client-side validatable vs.
systems that either allow anyone with sufficient hashing power to steal
coins *or* require "moon-math" that isn't yet available to production
systems.

> IMO the question of whether scarcity can be preserved while enabling
> innovation bears heavily on the liklihood of longterm viability of
> said innovations - and perhaps of Bitcoin itself.
> 
> FWIW I'll happily declare that I hold a modest amount of BTC and have
> an interest in the price appreciating. I'm sure you'll admit you're
> hardly an impartial party in this discussion yourself Peter :) But it
> really shouldn't matter. I'm not here today to make it, but I think
> the argument for preservation of scarcity stands quite well on its own
> merits - as rightly it should, regardless of anybody's interests.

But again, all these discussions about scarcity are fundementally
*moral* arguments that have no bearing on what's actually the most
appropriate solution for an *individual* problem.

In a decentralized system filled with anonymous actors telling people
"stop doing that! it's bad!" on reddit has pretty severe limitations in
trying to convince people to act against their own best interests.

> > The quality of Counterparty's software engineering has no bearing on
> > whether or not the underlying idea is a good one; you wouldn't say ring
> > signatures are an inherently bad idea just because the CryptoNote
> > implementation of them is atrocious.
> 
> Very interesting. I admit I hadn't come across these ideas before; I
> really must search the archive before posting :) They certainly offer
> a measure of robustness over the naive approach. I'm not sure they
> address my primary concerns however, WRT how consensus is demonstrated
> and incentivised.

I think you think consensus in Bitcoin is more "magical" than it really
is; Bitcoin is just code running on computers; consensus isn't really
incentivised at the protocol level beyond "screw it up and you'll lose
money"

Embedded consensus systems are no different: screw up consensus and
you'll lose money in a variety of ways.

> The obvious "embedded consensus" answer of "wait until N other
> transactions have occurred that include a hash of system state that
> includes your transaction" doesn't provide me with any confidence; it
> could be simulated with a Sybil attack.

No it can't - the transactions are in the blockchain so the sybil attack
has to attack the host system as well.

In any case, keep in mind all of this is in the context of tradeoffs:
for a different and sometimes more fragile consensus mechanism embedded
consensus gets immunity to attack by miners. You're trading off one type
of fragility for another - I'd much rather take the "one-time" fragility
inherent in having to write really solid software than the ongoing
fragility of always being vulnerable to miners.

Notably this is the exact same tradeoff taken elsewhere by the majority
of the crypto world.

-- 
'peter'[:-1]@petertodd.org
000000000000000017d70ee98f4cee509d95c4f31d5b998bae6deb09df1088fc

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Gareth Williams]

On Mon, Dec 15, 2014 at 3:52 PM, Peter Todd <pete@petertodd.org> wrote:
>> Comparisons with the SPV security of sidechains are fallacious. The
>> alternative to a proof-of-publication system reliant on client-side
>> validation is a blockchain. The question of whether the token used on
>> said blockchain should be two-way-pegged to BTC is completely orthogonal.
>>
>> (ie. yes, sidechains are "economically secure", in that you're reduced
>> to balancing economic incentives to avoid peg theft. But sidechains also
>> give us something unique in return - the ability to innovate without
>> needing to start new artificial scarcity races. Nothing else can do that.)
>
> I covered this in my original post: 1-way-pegs allow the creation of new
> valuable tokens without those tokens being useful for speculation.

I stand corrected. A permanent 1-way-peg is sufficient to preserve
scarcity; "nothing else can do that" WRT 2-way-pegs was overreaching.

I still don't see what "2-way-peg vs. 1-way-peg" has to do with
"embedded consensus vs. blockchain consensus" though, and feel it
disingenious to conflate them.

Blockchain consensus (eg. sidechains) can utilise either mechanism,
1-way-peg or 2-way-peg. Arguments in favour of 1-way-peg are
interesting, but they're ultimatley just arguments in favour of one
type of sidechain over another.

Arguments in favour of embedded consensus - and I feel I'm being
generous with the term "consensus" here - should surely stand on their
own merit against blockchain consensus, if they're to be convincing.

> Of course even without 1-way-pegs there's a much more important issue
> with your objection: worrying about creating new artificial scarcity
> races while innovating is fundementally a *moralistic* and *regulatory*
> concern that has no little if any bearing on whether or not the systems
> created are useful and secure. It's also an objection that raises
> serious questions about conflicts of interest between giving accurate
> and honest technical advice and promoting ways of using Bitcoin that
> will drive the price up.

IMO the question of whether scarcity can be preserved while enabling
innovation bears heavily on the liklihood of longterm viability of
said innovations - and perhaps of Bitcoin itself.

FWIW I'll happily declare that I hold a modest amount of BTC and have
an interest in the price appreciating. I'm sure you'll admit you're
hardly an impartial party in this discussion yourself Peter :) But it
really shouldn't matter. I'm not here today to make it, but I think
the argument for preservation of scarcity stands quite well on its own
merits - as rightly it should, regardless of anybody's interests.

> A number of mechanisms for detecting divergence are possible in embedded
> consensus systems, some of them even natural outcomes. For instance
> transactions can contain a hash of the previous consensus state, thereby
> creating an indicator of consensus measured in terms of economic stake.
> Extending that idea many anti-censorship proposals are to use such state
> hashes as encryption keys - if you are out of consensus you won't even
> see the transaction. (and you can't be double-spent either if
> implemented correctly; see my other reply to this thread today)

<snip>

> Indeed I did, which is why I worked out a better way to do upgrades
> almost a year ago:
>
> http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg06578.html

<snip>

> The quality of Counterparty's software engineering has no bearing on
> whether or not the underlying idea is a good one; you wouldn't say ring
> signatures are an inherently bad idea just because the CryptoNote
> implementation of them is atrocious.

Very interesting. I admit I hadn't come across these ideas before; I
really must search the archive before posting :) They certainly offer
a measure of robustness over the naive approach. I'm not sure they
address my primary concerns however, WRT how consensus is demonstrated
and incentivised.

I know what my own node considers valid transaction history; how can I
be confident that everyone else takes the same view? For contrast,
with blockchain consensus, I can be confident that there is consensus
on the longest chain observed. If I receive a new transaction, simply
waiting for it to be buried under N blocks of PoW provides a high
level of confidence that everyone else considers it valid.

The obvious "embedded consensus" answer of "wait until N other
transactions have occurred that include a hash of system state that
includes your transaction" doesn't provide me with any confidence; it
could be simulated with a Sybil attack.

<snip>

> I prefer to make robust arguments; if I can start with accepting that
> 95% of what my opponents say is true, yet still end up being correct,
> all the better!

Indeed :) To avoid wasting time it's only ever worth arguing against
the strongest opposing position you're aware of (whether your opponent
is aware of it or not.)

https://en.wikipedia.org/wiki/Principle_of_charity

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

bleep bloop

Peter Todd:
> On Fri, Dec 12, 2014 at 01:41:34PM +0000, odinn wrote:
>> Peter... It kind of sounds to me that (as fine of a position
>> paper as this is) on _certain_ points, you're falling prey to the
>> "but it's inefficient, but it's a scamcoin, but luke-jr told me
>> so" argument...
> 
> I prefer to make robust arguments; if I can start with accepting
> that 95% of what my opponents say is true, yet still end up being
> correct, all the better!
> 
>> I think the Mastercoin devs are doing fine work and I consider
>> the zerocash devs to have developed (in v2, mint and pour) to
>> have developed something that will really turn the world on its
>> ear, but what do I know? Nothing.  Nothing at all.
> 
> My personal opinion is that what Mastercoin has started will turn
> the world on its ear, but I'd be surprised if the succesful
> implementations of the underlying ideas come from that team. But
> there's nothing surprising about that - when was the last time you
> used Netscape Navigator, let alone NCSA Mosaic?
> 

- -- 
http://abis.io ~
"a protocol concept to enable decentralization
and expansion of a giving economy, and a new social good"
https://keybase.io/odinn
-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJUkNluAAoJEGxwq/inSG8CKy0IAJmCUmDbaCx33/km0J2mP7ha
kxX3fxiPpicD8hXa4FXBsrYqj7ZFu0OmFOU/ei0AXMOuu94rQdIp6hon3f5GO73J
WVT2Toqd2GTCXhmddyqtOzZ5mYOyZhlJUYlNjbwTmlk+U2hQbZC1aJ4AKdmjQn5v
9DFkZfqBSsNhcoLCKoVqY3l4qzw0XqeL6fOYkz2H9AssWdcUV9JB5C0wm8rI70AX
qcxABgrKDwhThWgHyHGZXHLCvRRpMUFFVbzO67BPZA2R+gXYtOAVDozl7jdx7PLl
x3nyzZK3pX1bqcT2T5fD8wQtu4yJ3RCBVWzHfrA5MF6q4Yh6DEh7DnO8ccOnPlk=
=1os7
-----END PGP SIGNATURE-----

[Bitcoin-development] Setting the record straight on Proof-of-Publication

[paul snow]

[-- 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 --]

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Peter Todd]

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

On Fri, Dec 12, 2014 at 01:41:34PM +0000, odinn wrote:
> Peter... It kind of sounds to me that (as fine of a position paper as
> this is) on _certain_ points, you're falling prey to the "but it's
> inefficient, but it's a scamcoin, but luke-jr told me so" argument...

I prefer to make robust arguments; if I can start with accepting that
95% of what my opponents say is true, yet still end up being correct,
all the better!

> I think the Mastercoin devs are doing fine work and I consider the
> zerocash devs to have developed (in v2, mint and pour) to have
> developed something that will really turn the world on its ear, but
> what do I know? Nothing.  Nothing at all.

My personal opinion is that what Mastercoin has started will turn the
world on its ear, but I'd be surprised if the succesful implementations
of the underlying ideas come from that team. But there's nothing
surprising about that - when was the last time you used Netscape
Navigator, let alone NCSA Mosaic?

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

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Peter Todd]

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

On Sun, Dec 14, 2014 at 12:32:22AM +1100, Gareth Williams wrote:
> On 13/12/14 04:04, Alex Mizrahi wrote:
> > Well, client-side validation is mathematically secure, while SPV is
> > economically secure.
> > I.e. it is secure if you make several assumptions about economics of the
> > whole thing.
> 
> Comparisons with the SPV security of sidechains are fallacious. The
> alternative to a proof-of-publication system reliant on client-side
> validation is a blockchain. The question of whether the token used on
> said blockchain should be two-way-pegged to BTC is completely orthogonal.
> 
> (ie. yes, sidechains are "economically secure", in that you're reduced
> to balancing economic incentives to avoid peg theft. But sidechains also
> give us something unique in return - the ability to innovate without
> needing to start new artificial scarcity races. Nothing else can do that.)

I covered this in my original post: 1-way-pegs allow the creation of new
valuable tokens without those tokens being useful for speculation.

To recap, a 1-way-peg allows the conversion of Bitcoins to another token
by provably destroying the Bitcoins, thus capping the maximum possible
value of that token and ensuring the token can-not become an investment.
For owners of these tokens they can convert them back to Bitcoin by
selling them at a discount to buyers who would otherwise be able to
purchase them via provable destruction. A pragmatic implementation may
wish to make obtaining the token via destruction option unattractive
compared to obtaining them through trade by incorporating a time delay
into the destruction process to encourage liquidity. (interestingly a
natural outcome of an announce-commit sacrifice-to-fees scheme)

Of course even without 1-way-pegs there's a much more important issue
with your objection: worrying about creating new artificial scarcity
races while innovating is fundementally a *moralistic* and *regulatory*
concern that has no little if any bearing on whether or not the systems
created are useful and secure. It's also an objection that raises
serious questions about conflicts of interest between giving accurate
and honest technical advice and promoting ways of using Bitcoin that
will drive the price up.

> > You know, The Great Fork of 2013 was resolved through human
> > intervention, Bitcoin nodes were not smart enough to detect that
> > something is going awry on their own.
> 
> I hate to think what the outcome would've been on a proof-of-publication
> system. You don't even have a fork. You just have a whole bunch of nodes
> who sort-of-mostly agree on a shared history, except where they don't.
> Maybe they just disagree on the validity of a single transaction.
> They'll slowly diverge over time (as bad transactions are used as input
> to other transactions.) You have no reliable way to detect this lapse in
> consensus, nor any mechanism to incentivse convergence. Indeed, you have
> no consensus mechanism in the first place.

A number of mechanisms for detecting divergence are possible in embedded
consensus systems, some of them even natural outcomes. For instance
transactions can contain a hash of the previous consensus state, thereby
creating an indicator of consensus measured in terms of economic stake.
Extending that idea many anti-censorship proposals are to use such state
hashes as encryption keys - if you are out of consensus you won't even
see the transaction. (and you can't be double-spent either if
implemented correctly; see my other reply to this thread today)

> Bitcoin is where it is today because of Satoshi's elegant solution to
> exactly such problems. Which some people now appear to be in a hurry to
> discard :)

FWIW usually Satoshi's solution is described as a hack, sometimes as an
elegant hack.

> Peter Todd might disagree with the wisdom of that :) He wrote an
> excellent email to this list not long ago warning of the dangers of
> centralisation. IIRC one point he made was that scheduled, regular
> hardforks were a real threat - if a single entity (eg. the Bitcoin
> Foundation) were to become politically established as the coordinator of
> such forks, they would have de-facto control over the protocol.

Indeed I did, which is why I worked out a better way to do upgrades
almost a year ago:

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg06578.html


> (Also worth noting: all such systems are effectively "mandatory
> updating" due to the risk of subtle consensus bugs of the type I
> described above. Your only assurance that your view of the world is the
> same as everyone elses' is that you're running the exact same software.
> I played with Counterparty a while ago and quickly learned - the hard
> way - to do a 'git pull' before any important operation.)

The quality of Counterparty's software engineering has no bearing on
whether or not the underlying idea is a good one; you wouldn't say ring
signatures are an inherently bad idea just because the CryptoNote
implementation of them is atrocious.

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

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Peter Todd]

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

On Fri, Dec 12, 2014 at 07:50:48PM +0200, Alex Mizrahi wrote:
> > I think what Gareth was getting at was that with client-side validation
> > there can be no concept of a soft-fork. And how certain are you that the
> > consensus rules will never change?
> >
> 
> Yes, it is true that you can't do a soft-fork, but you can do a hard-fork.
> Using scheduled updates: client simply stops working at a certain block,
> and user is required to download an update.

You're quite mistaken actually. One of the first things to come out of
my research as Mastercoin's Chief Scientist - indeed after a week on the
job - was how to safely upgrade embedded consensus systems in a
decentralized fashion:

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03890.html

To recap, where valuable scarce tokens are concerned we want to ensure
that an attacker can't use a fork caused by an upgrade to double-spend
tokens. We solve this problem by ensuring that when a token visible to
version V_i is spent in a V_{i+1} client, the token appears spent to
version V_i clients as well. This is easy to accomplish by a "split
transaction" scheme that separates all operations into separate
"increment" and "decrement" operations.

The simplest example of this principle in action is colored coins, which
are certainly an example of an embedded consensus system. Colored coin
implementations naturally ensure that all versions of the system see a
token getting spent the same way - the corresponding txout is spent! So
long as changes to the coloring rules are handled such that only one set
of rules - one version - can apply to a given txout spend we get
anti-doublespend protection.

The second aspect of the problem is the social/political implications of
upgrades - because embedded consensus systems don't outsource trust they
very clearly require the co-operation of the economic majority in an
upgrade. For instance if the community has two competing proposals for
how to upgrade version V1 of Counterparty, V2a and V2b, choosing to move
your tokens to either version becomes a vote with serious economic
consequences. In fact, it's quite possible that a community would choose
to simply fork into two different systems each offering a different set
of features. Equally in the event of such a fork someone can create a
third version, V3, that recombines the two incompatible forks. Again,
anyone who agrees with version V3 can choose to move their tokens to it,
healing the fork.

Arguably this process of handling forks by direct economic voting is
significantly *more* decentralized than Bitcoin's soft-fork mechanism as
adoption of a new version is something all participants in the system
play a part in equally. (as measured by economic stake) Of course, it
will lead to sometimes ugly political battles, but that's simply part of
the cost of having democratic systems.


> It looks like people make a cargo cult out of Bitcoin's emergent
> properties.

+1

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

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Gareth Williams]

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

On 13/12/14 04:04, Alex Mizrahi wrote:
> Well, client-side validation is mathematically secure, while SPV is
> economically secure.
> I.e. it is secure if you make several assumptions about economics of the
> whole thing.

Comparisons with the SPV security of sidechains are fallacious. The
alternative to a proof-of-publication system reliant on client-side
validation is a blockchain. The question of whether the token used on
said blockchain should be two-way-pegged to BTC is completely orthogonal.

(ie. yes, sidechains are "economically secure", in that you're reduced
to balancing economic incentives to avoid peg theft. But sidechains also
give us something unique in return - the ability to innovate without
needing to start new artificial scarcity races. Nothing else can do that.)

<snip>

> You know, The Great Fork of 2013 was resolved through human
> intervention, Bitcoin nodes were not smart enough to detect that
> something is going awry on their own.

I hate to think what the outcome would've been on a proof-of-publication
system. You don't even have a fork. You just have a whole bunch of nodes
who sort-of-mostly agree on a shared history, except where they don't.
Maybe they just disagree on the validity of a single transaction.
They'll slowly diverge over time (as bad transactions are used as input
to other transactions.) You have no reliable way to detect this lapse in
consensus, nor any mechanism to incentivse convergence. Indeed, you have
no consensus mechanism in the first place.

Bitcoin is where it is today because of Satoshi's elegant solution to
exactly such problems. Which some people now appear to be in a hurry to
discard :)

Alex Mizrahi wrote:
> Using scheduled updates: client simply stops working at a certain block,
> and user is required to download an update.

<snip>

> An alternative to this is to make updates mandatory. You will no longer
> need to maintain compatibility with version 0.1 (which is impossible)
> and you can also evolve consensus rules over time.

Peter Todd might disagree with the wisdom of that :) He wrote an
excellent email to this list not long ago warning of the dangers of
centralisation. IIRC one point he made was that scheduled, regular
hardforks were a real threat - if a single entity (eg. the Bitcoin
Foundation) were to become politically established as the coordinator of
such forks, they would have de-facto control over the protocol.

Even in that dark scenario, I would feel a measure of confidence that
past transactions I had received could not be tampered with. The fact
that those transactions happened, and that there was (and is) consensus
they were valid, is publicly documented in the blockchain. I trust any
reasonable person would not accept a client that ignored validated data
in the blockchain as "Bitcoin" any more.

Your proof-of-publication system with mandatory updates is another
matter entirely. No public record of transactions I have received with
that system exists, anywhere. If tomorrow's mandatory update has the
effect of zeroing my account balance (by happening to now interpret one
or more transactions I received, or their inputs, as invalid) then I
have no recourse. I won't find sympathy with the majority of users, who
are unaffected and just accept the update.

In short, what you describe doesn't sound very decentralised :) Do you
want transactions you receive validated by distributed consensus and
burried under PoW, or validated by some guy's mandatory-updating python
script?

(Also worth noting: all such systems are effectively "mandatory
updating" due to the risk of subtle consensus bugs of the type I
described above. Your only assurance that your view of the world is the
same as everyone elses' is that you're running the exact same software.
I played with Counterparty a while ago and quickly learned - the hard
way - to do a 'git pull' before any important operation.)







[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Alex Mizrahi]

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

> I think what Gareth was getting at was that with client-side validation
> there can be no concept of a soft-fork. And how certain are you that the
> consensus rules will never change?
>

Yes, it is true that you can't do a soft-fork, but you can do a hard-fork.
Using scheduled updates: client simply stops working at a certain block,
and user is required to download an update.

In Bitcoin we can operate with some assurance that hard-forks will almost
> never happen, exactly because extensions are more likely to occur via
> soft-fork mechanisms. In such a case, old non-updated clients will still
> generate a correct view of the ledger state. But this is not so with client
> side validation!
>

You assume that an ability to operate with zero maintenance is very
important, but is this a case?

There was a plenty of critical bugs in bitcoind, and in many cases people
were strongly encouraged to upgrade to a new version.
So, you urge people to keep their clients up-to-date, but at the same time
claim that keeping very old versions is critically important.
How does this make sense? Is this an exercise at double-think?

An alternative to this is to make updates mandatory. You will no longer
need to maintain compatibility with version 0.1 (which is impossible) and
you can also evolve consensus rules over time.

It looks like people make a cargo cult out of Bitcoin's emergent
properties.

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Alex Mizrahi]

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

>
> "Secure" and "client side validation" don't really belong in the same
> sentence, do they?
>

Well, client-side validation is mathematically secure, while SPV is
economically secure.
I.e. it is secure if you make several assumptions about economics of the
whole thing.

In my opinion the former is transfinitely more secure than the later.
But it's more of a philosophical question, sure.

The good thing about PoW-based consensus is that it is robust against
version inconsistencies and various accidents of this nature up to a
certain degree. But you hardly can depend on that:
You know, The Great Fork of 2013 was resolved through human intervention,
Bitcoin nodes were not smart enough to detect that something is going awry
on their own.

Naive proof-of-publication is very fragile in that respect, but you can
easily bring back robustness.

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

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Justus Ranvier]

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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 12/12/2014 01:41 PM, odinn wrote:
> I think the Mastercoin devs are doing fine work

I wonder if all the Mastercoin devs would agree with that statement.

- -- 
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k
-----BEGIN PGP SIGNATURE-----

iQEcBAEBCAAGBQJUivkLAAoJEMP3uyY4RQ21r5cIANvabja0i5j79a6KSkKOgEyR
LhBz4mugzTc8Zej2NBeyEtv0pzO4fs5wvQo4N/1BW7aHXuFJsgJpGlV8thkuFhek
UhoPC23i7u3jCPQ30PintqvCBCimse+PJa60KE2QL2DZn7WgRGKrEuo41AROxeit
vfVMcFULc6bB9hxIEBpcU4RuwKJHVgzSHMkO75/uHHtPLJ9TbCfqcxT146cZvSjc
Tc62ukuX1xBj5PhQM8GaUGzkQcfcZ+7d3DD1X22Gk1U6w+zat52dapy/qYgn9oA5
ubk/p/7Kywd8D44rPsr/pbdlDZxG0w77yRJIMboXhFMV7rY3sMRHHQmAUz+I8FY=
=R4pR
-----END PGP SIGNATURE-----

[-- Attachment #2: 0x38450DB5.asc --]
[-- Type: application/pgp-keys, Size: 14542 bytes --]

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Peter... It kind of sounds to me that (as fine of a position paper as
this is) on _certain_ points, you're falling prey to the "but it's
inefficient, but it's a scamcoin, but luke-jr told me so" argument...

I think the Mastercoin devs are doing fine work and I consider the
zerocash devs to have developed (in v2, mint and pour) to have
developed something that will really turn the world on its ear, but
what do I know? Nothing.  Nothing at all.

gmorning

Peter Todd:
> 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.
> 
> 
> 
> ------------------------------------------------------------------------------
>
> 
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and
> Dashboards with Interactivity, Sharing, Native Excel Exports, App
> Integration & more Get technology previously reserved for
> billion-dollar corporations, FREE 
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
>
> 
> 
> 
> _______________________________________________ Bitcoin-development
> mailing list Bitcoin-development@lists.sourceforge.net 
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

- -- 
http://abis.io ~
"a protocol concept to enable decentralization
and expansion of a giving economy, and a new social good"
https://keybase.io/odinn
-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJUivCNAAoJEGxwq/inSG8ChVUH/26zj2pj7AF+oa2RDkPZN980
qFTY7x2s9w97bEuCiFfFpYjIP26mY4+snuoTWBa8yCp7gLVVsk9JKkN0dmXIboXf
ocoJY9s/wT7QLqJMRRwWb/8XPKwjXB10PNawCRoUk++8E0Y+W6mxiH5Gs1UnYKwI
2DHHh/hTh35mR5burwdLGEMLaVtK4BFLJTZwW+4xlWESsoWeQnxEuty799HldOaN
+wms8dvtZlzJElLUPjBGBZT6DRTaPsvqSvQ0CnHI84LYwuUObMcV89mkBcfTHlMt
MczwaO7CCc/jmoOoQKDyIVuW1eJeXggln+LOS34qwH8rCgjdOZeT3y4PgUTZ+AM=
=Sm96
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication

[Gareth Williams]

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

On 12/12/14 20:05, Peter Todd wrote:
> 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. 

"Secure" and "client side validation" don't really belong in the same
sentence, do they?

If I am to accept a transaction with any assurance of security at all,
the important question to ask is not: "does my client consider this
valid?" but: "does the rest of the world consider this valid?"

Validated data in the blockchain is far more useful for this purpose
than unvalidated data with a mere proof of publication in the
blockchain, precisely because it records what /everybody else/ considers
valid history (and very likely will continue to consider valid history
in future.)

Pegged sidechains have their challenges, but at least they provide
distributed consensus on transaction history.

Proof-of-publication systems like Counterparty and Mastercoin require me
to trust, with zero evidence, that everybody else's client has the exact
same interpretation of transaction history as mine, and will continue to
have for the indefinite future. How is that not a horribly broken
security model? I'd use a sidechain - with reasonable parameters that
disincentivise peg theft as much as practical - over that any day.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

[Bitcoin-development] Setting the record straight on Proof-of-Publication

[Peter Todd]

[-- 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 --]