Setting the record straight on Proof-of-Publication

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.

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.

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

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

>
> "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.

> 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.

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.)

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

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.

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?

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

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

Gregory Maxwell recently pointed out to me in private conservation that there potentially existed a fundemental disagreement between him and I on our philosophical approaches to blockchains, in that he prioritised the notion of the blockchain as an anti-replay oracle, and I prioritised it as a publication layer. Here I'll talk about the differences and simularities between those two approaches.

What's Anti-Replay? ===================

We have some action - perhaps spending a txout - and we only want it to be possible for that action to happen once; we don't want it to be possible for that action to be replayed again. This is inherently not possible with cryptography alone as cryptography is just math and any mathematical calculation can be repeated with different parameters.

What's an Anti-Replay Oracle? =============================

We need the following primitives operating on message m, pubkey p, and a valid signature sig1 for m, p:

    AntiReplaySign(m, p, sig1) -> sig2
    VerifyAntiReplaySig(m, p, sig2) -> True or False

Additionally once AntiReplaySign() has been used once for a given pubkey it is impossible to re-run the primitive on a different message m'. This is of course impossible to implement with math alone, but we can implement it with a trusted third party. For instance Carol can perform the AntiReplaySign operation and make the promise that she will only ever perform it once for any given (m,p) tuple.

Maxwell points out in CoinWitness¹ that the anti-replay oracle is sufficient to implement a digital currency. So long as the trusted oracle, or majority of a federation of trusted oracles, is honest coins cannot be double-spent and can be securely passed from owner-to-owner with an ever-growing transcriptⁱ proving each valid spend.

i) The transcript is needed in this model only because the oracles do
   nothing more than promise to never sign a message twice; it can be
   removed if the oracles additionally validate transactions in some
   way.

The Blockchain as an Anti-Replay Oracle =======================================

In Bitcoin miners act as a trusted anti-replay oracle. If they follow the Bitcoin protocol faithfully for any given txout one and only one valid scriptSig will ever be accepted into the blockchain. Thus the spend of a txout is a valid anti-replay-protected signature, and the validity of that signature can be verified by SPV clients with a merkle path to the block headers.

Using proof-of-publication to prove non-replay ==============================================

Given a secure proof-of-publication² system we can prove non-replay. We define a valid signature as both being published on that system, as well as there existing no other valid signature. (proof-of-non-publication) An attempt to fraudulently create a second signature will either fail the first test - not being published at all - or will fail the second test - not being able to prove no other valid signature exists.

Thus we see that proof-of-publication can be used to securely audit the honesty of an anti-replay oracle, resulting in secure anti-replay protection without the requirement of trust.

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³.

Anti-replay in place of proof-of-publication to secure audit logs =================================================================

The author's proof-of-concept Uniquebits⁴ allows Alice to prove to Bob that some set of records R_i that she has given to Bob is the same set of records she has given to everyone else - that is no R_i' exists. Secondly Alice can update the records producing R_{i+1}, and Bob can determine if such an update exists.

Currently Uniquebits uses proof-of-publication via the Bitcoin blockchain directly for both guarantees. It could however make use of the anti-replay function provided by Bitcoin to satisfy the first requirement with the following protocol:

0) Alice publishes record set R_i such that H(T_i + n_i) is committed in
   R_i, where T_0 is a txout she controls, and n_i is a nonce.

1) Alice creates T_{i+1}, another txout that she controls, and nonce
   n_{i+1}

2) Alice creates R_{i+1} which commits to H(T_{i+1} + n_i)

3) Finally to publish R_{i+1} she spends T_i in a transaction X_{i+1}
   that commits to R_{i+1} (e.g. in an OP_RETURN output, or with
   pay-to-contract⁵/sign-to-contract)

This process can be repeated again indefinitely, starting at step #1. When Alice wants to prove to Bob - who has R_i - she simply gives him a SPV proof that transaction X_{i+1} exists in the blockchain along with n_i. This proves that T_i was spent, which can only happen once, and that it committed to R_{i+1}. As the output can only be spent once it is not possible to create a valid-looking R_{i+1}'

However to prove to Bob that R_{i+1} is the most recent set of records Alice still needs to use proof-of-publication, by showing him txout T_{i+1} is unspent.

Case study: Fidelity-bonded Ledgers/Federated Sidechains ========================================================

The author's Fidelity-Bonded Ledgers⁶ and the more general idea of Federated Sidechains⁷ both describe the notion of a trusted third party, possibly implemented as a federated majority set, who guarantees the correct maintenance of some financial ledger according to some set of rules. Coins can be moved to/from the ledger by payment to a specific set of scriptPubKey's. Federated sidechains proposes that the scriptPubKey simply be a n-of-m multisig; fidelity-bonded ledgers proposes new opcodes that allow redemption via proof-of-fraud.

In any case someone relying on a transaction within the ledger itself still needs to be able to audit that their view of the ledger is the same view everyone else sees; in short that there do not exist double-spends on the ledger. The author's fidelity-bonded ledgers paper proposed that the ledger be made available over a Tor-accessible website to prevent selective censorship. The federated sidechains proposal is mute on this issue.

As the state of the ledger is a specific instance of the more general set of records problem that Uniquebits solves as can use the same principles for fidelity-bonded ledgers/federated sidechains. The third party periodically publishes the ledger state to the Bitcoin blockchain allowing anyone to detect if their copy of the ledger is incomplete; if not there may be double-spends in it. Finally proof of such double-spends can trigger the destruction of a fidelity-bond⁸ and/or return funds to their rightful owners. (with appropriate opcodes⁷)

Censorship of the ledger state publications is an issue, however in the case of financial ledgers with pegged funds we can use the pegged funds themselves in the publication. Censoring those publications by preventing the designated txouts from being spent then becomes equivalent to blacklisting funds. This requires a majority of hashing power supporting the blacklist, and is a highly politically charged issue⁹ in the Bitcoin community.

References ==========

1) Really Really ultimate blockchain compression: CoinWitness,
   Gregory Maxwell, Aug 19th 2013, Accessed 2014-12-20,
   https://bitcointalk.org/index.php?topic=277389.msg2961736

2) Setting the record straight on Proof-of-Publication,
   Peter Todd, Dec 12th 2014,
   http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg06570.html

3) Decentralized digital asset exchange with honest pricing and market depth,
   Peter Todd, Feb 9th 2014,
   http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg03892.html

4) Uniquebits, Peter Todd, Accessed 2014-12-20,
   https://github.com/petertodd/uniquebits/tree/b9213f6769d80305bdd192925e8bd7bd04239d1b

5) Homomorphic Payment Addresses and the Pay-to-Contract Protocol,
   Ilja Gerhardt and Timo Hanke, Dec 13th 2012,
   http://arxiv.org/abs/1212.3257

6) Fidelity-bonded ledgers, Peter Todd, Feb 25th 2013,
   http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg01786.html

7) Enabling Blockchain Innovations with Pegged Sidechains,
   Blockstream, Oct 22nd 2014,
   SHA256: 680c71aef9ed578720e25c58fd50de5cdbee755c3800e7601dad9a745ca65cf3,
   http://www.blockstream.com/sidechains.pdf

8) Fidelity-bonded banks: decentralized, auditable, private, off-chain payments,
   Peter Todd, Feb 23rd 2014,
   https://bitcointalk.org/index.php?topic=146307.0

9) WARNING: Bitcoin Address Blacklists have been forced into the Gentoo Linux bitcoind distribution by Luke-jr against the will of other core devs. Gentoo maintainers are clueless and not reversing the change.  Boycott Gentoo now.,
   historian1111, Oct 10th 2014, Accessed 2014-12-20,
   https://www.reddit.com/r/Bitcoin/comments/2ityg2/warning_bitcoin_address_blacklists_have_been/

On Sun, Dec 21, 2014 at 11:57:51AM +0800, Mark Friedenbach wrote:

> On Sat, Dec 20, 2014 at 10:48 PM, Peter Todd <pete@petertodd•org> 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³.
> >
>
> I think you are trying to say something more specific / limited than that,
> and I suggest you adjust your wording accordingly. Decentralized exchange
> would be possible today with vanilla bitcoin using SIGHASH_SINGLE if only
> the protocol supported multiple validated assets (which it could, but
> doesn't). Rather straightforward further extensions to the protocol would
> enable market participants to use a wider class of orders, as well as
> enable the buyer rather than the seller to dictate order sizes via partial
> redemption, as we demonstrate in our Freimarkets paper.

Do you realise that all those Freimarket's uses are either based on proof-of-publication, or insecure due to sybil attacks?

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.

On Sun, Dec 21, 2014 at 02:18:18PM +0800, Mark Friedenbach wrote:

> Care to expand?
>
> Freimarkets does not require proof of publication of bids or asks, which
> are distributed out of band from the block chain until a match is made. It
> does not guarantee ordering of market transactions. Indeed, front-running
> is embraced as the mechanism for generating miner fees to pay for the
> service.

Right, so Freimarkets is delibrately insecure.

Best of luck on that.

> Sybil attacks? I'm not sure what you could be referring to. In Freimarkets
> a bid or ask is valid when received; a double-spend is required to cancel
> it. You could only flood the network with actual executable orders, and the
> counter-party to the order doesn't care if they all came from the same
> person or not.
>
> Can you explain what it is you are objecting to?

Read my paper¹ - proof-of-publication is what allows you to detect front-running robustly within certain parameters. Protecting against that is widely considered to be a very important goal by people actually in finance, to the point where I've had discussions with people where anti-front-running protection might be the *only* thing they use a decentralized system for.

1) Decentralized digital asset exchange with honest pricing and market depth,
   Peter Todd, Feb 9th 2014,
   http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg03892.html

On 20 December 2014 at 14:48, Peter Todd <pete@petertodd•org> wrote:

> We need the following primitives operating on message m, pubkey p, and a
> valid signature sig1 for m, p:
>
>     AntiReplaySign(m, p, sig1) -> sig2
>     VerifyAntiReplaySig(m, p, sig2) -> True or False
>
> Additionally once AntiReplaySign() has been used once for a given pubkey
> it is impossible to re-run the primitive on a different message m'. This
> is of course impossible to implement with math alone, but we can
> implement it with a trusted third party.

Well while you cant prevent it you could render it insecure enabling miners to take funds.

That could work via a one-show signature; normal ECDSA being address a=H(Q), public key Q=dG, R=kG, r=R.x, s=(H(m)+rd)/k, signature (r,s), verify: a=?H(Q) and sR=?H(m)G+rQ one-show being: a=H(Q,R), verify being: a=?H(Q,R) and sR=?H(m)G+rQ. Now that is unsafe to double-spend by design as only that specific R is usable and as we know reusing R with different messages leaks the private key because: s=(H(m)+rd)/k and s'=(H(m')+rd)/k implies sk=H(m)+rd and s'k=H(m')+rd so k=(H(m)-H(m'))/(s'-s), and d=(sk-H(m))/r.

Adam

st

On Sun, Dec 21, 2014 at 6:52 AM, Peter Todd <pete@petertodd•org> wrote:

> On Sun, Dec 21, 2014 at 11:57:51AM +0800, Mark Friedenbach wrote:
>> I think you are trying to say something more specific / limited than that,
>> and I suggest you adjust your wording accordingly. Decentralized exchange
>> would be possible today with vanilla bitcoin using SIGHASH_SINGLE if only
>> the protocol supported multiple validated assets (which it could, but
>> doesn't). Rather straightforward further extensions to the protocol would
>> enable market participants to use a wider class of orders, as well as
>> enable the buyer rather than the seller to dictate order sizes via partial
>> redemption, as we demonstrate in our Freimarkets paper.
>
> Do you realise that all those Freimarket's uses are either based on
> proof-of-publication, or insecure due to sybil attacks?

So let's go through an example to see in which ways non-proof-of-publication orders are "insecure".

Alice the seller wants to sell 1 unit of A for 100 units of B. Bob is willing to pay up to 200 Bs for 1 A.

Let's assume a proof of publication system first, in which the execution price is the mean between bid and ask. Alice publishes her order. Bob could publish his order at price 200 Bs and the order would execute at 150 Bs. But after seeing Alice's order he knows he doesn't need to pay that much, so he publishes and order buying for 100 Bs.

Alice gets 100 Bs (what she signed she wanted) and Bob pays less than he was wiling to pay, he pays 100 Bs. Everybody happy.

Now let's assume native assets and sighash_single.

Alice publishes her order (out of band, using various channels). Bob could publish his order at price 200 Bs and then a miner would execute at 100 Bs for Alice, at 200 Bs for Bob and pocket 100 Bs as mining fees. But after seeing Alice's order he knows he doesn't need to pay that much, so he publishes and order buying for 100 Bs.

Again, Alice gets 100 Bs (what she signed she wanted) and Bob pays pays 100 Bs. The main difference is that Alice didn't had to pay a fee to publish her binding order.

Now let's try to articulate your concerns. Your concern is that Carol, isolates Bob preventing him from seeing Alice's order. Then maybe Bob publishes his own order at 200 Bs. If Carol sees both orders while preventing the other participants from seeing them, she can build a tx in which Alice sells at 100, Bob buys at 200, and Carol pockets the difference. But...any smart miner will replace Carol's address with his own when processing the trade, so Carol cannot win this way.

Another thing Carol can do is to buy the A herself for 100 Bs, leaving Bob without them. If Alice cares about Bob getting the deal instead of Carol she can do two things: 1) Establish a direct communication channel with Bob 2) Move to a proof of publication system and start paying fees for publishing binding orders.

So again, what's the advantage that proof-of-publication provides TO ALICE so that she will be so eager to pay the higher costs to get the same deal? If this example is not enough to be able to explain the advantage of proof-of-publication markets feel free to write a more complex one.

On Dec 20, 2014 8:49 AM, "Peter Todd" <pete@petertodd•org> 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? 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).

Obviously you can publish the same data as many times as you like in a proof-of-publication system; the interpretation of what that data means would be the responsibility of the observers, not the "publishing vehicle". Repeated entries thus can be written, and the user of PoP can validate and prove they did so.

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).

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.

On Sun, Dec 21, 2014 at 07:49:17AM -0600, paul snow wrote:

> On Dec 20, 2014 8:49 AM, "Peter Todd" <pete@petertodd•org> 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.

On Sun, Dec 21, 2014 at 10:01:37AM +0000, Adam Back wrote:

> On 20 December 2014 at 14:48, Peter Todd <pete@petertodd•org> wrote:
> > We need the following primitives operating on message m, pubkey p, and a
> > valid signature sig1 for m, p:
> >
> >     AntiReplaySign(m, p, sig1) -> sig2
> >     VerifyAntiReplaySig(m, p, sig2) -> True or False
> >
> > Additionally once AntiReplaySign() has been used once for a given pubkey
> > it is impossible to re-run the primitive on a different message m'. This
> > is of course impossible to implement with math alone, but we can
> > implement it with a trusted third party.
>
> Well while you cant prevent it you could render it insecure enabling
> miners to take funds.
>
> That could work via a one-show signature; normal ECDSA being address
> a=H(Q), public key Q=dG, R=kG, r=R.x, s=(H(m)+rd)/k, signature (r,s),
> verify: a=?H(Q) and sR=?H(m)G+rQ one-show being: a=H(Q,R), verify
> being: a=?H(Q,R) and sR=?H(m)G+rQ.  Now that is unsafe to double-spend
> by design as only that specific R is usable and as we know reusing R
> with different messages leaks the private key because: s=(H(m)+rd)/k
> and s'=(H(m')+rd)/k implies sk=H(m)+rd and s'k=H(m')+rd so
> k=(H(m)-H(m'))/(s'-s), and d=(sk-H(m))/r.

There's no need to get into the specifics of crypto math so early; you can just as easily and only slightly less efficiently obtain the same result with a few extensions to the Bitcoin scripting system to verify ECDSA signatures directly.

The interesting question is how "risky" this actually is? Sybil attacks are reasonably easy to pull off, and users have little incentive to validate if 99% of the time everything works, so you don't want to create a system where an actual attack will likely go undetected. Talking about the low level details of how double-spend punishment is actually detailed is just premature optimization.

As usual in Bitcoin, the hard part is *not* the math.

On Sun, Dec 21, 2014 at 03:11:32PM +0800, Mark Friedenbach wrote:

> On Sun, Dec 21, 2014 at 3:01 PM, Peter Todd <pete@petertodd•org> wrote:
>
> > Right, so Freimarkets is deliberately insecure.
> >
>
> Please define your terms, particularly what your security requirements are
> here. In the architecture we created users remain in control of their funds
> at all times, and miners have incentives to mine the host chain. So I don't
> know what insecurity you are possibly talking about, and seem unwilling to
> elaborate.

Sybil attacks leading to front-running.

You may not be aware of this, but not being able to get the best price due to a sybil attack *is* considered to be a security issue by the users of these systems.

> I have read your posting and engaged with you in that very thread, where I
> point out that global ordering of bids & asks is a superfluous requirement.

It's superfluous until you have real businesses actually using these systems.

> As to front-running, there is a distinct difference between centralized
> systems where front-running is essentially theft, and a distributed block
> chain system with actual costs paid by fees captured from the spread.

Among other things, ever noticed how this incentivises people to sybil attack the entire system? Not good.

I could play the game where I say, "You don't understand," and, like you, not address any of your points.

First, there is no dependence on implementation in my arguments. If a system can prevent replay by some set of rules, it necessarily must be able to answer the question if a message is publishable. Non publishing proofs are thus possible and even required.

The argument that proof of audience isn't part of an anti-replay system is not one I picked up on, but an publicly auditable anti replay system necessarily must define its audience. Again, not an issue for an auditable system. On Dec 21, 2014 9:23 AM, "Peter Todd" <pete@petertodd•org> wrote:

> On Sun, Dec 21, 2014 at 07:49:17AM -0600, paul snow wrote:
> > On Dec 20, 2014 8:49 AM, "Peter Todd" <pete@petertodd•org> 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
>

On Sun, Dec 21, 2014 at 12:25:36PM +0100, Jorge Timón wrote:

> So let's go through an example to see in which ways
> non-proof-of-publication orders are "insecure".
>
> Alice the seller wants to sell 1 unit of A for 100 units of B.
> Bob is willing to pay up to 200 Bs for 1 A.
>
> Let's assume a proof of publication system first, in which the
> execution price is the mean between bid and ask.
> Alice publishes her order.
> Bob could publish his order at price 200 Bs and the order would
> execute at 150 Bs.
> But after seeing Alice's order he knows he doesn't need to pay that
> much, so he publishes and order buying for 100 Bs.
>
> Alice gets 100 Bs (what she signed she wanted) and Bob pays less than
> he was wiling to pay, he pays 100 Bs. Everybody happy.
>
> Now let's assume native assets and sighash_single.

Incidentally, SIGHASH_SINGLE is just as usable in embedded consensus; it's not specific to native assets.

> So again, what's the advantage that proof-of-publication provides TO
> ALICE so that she will be so eager to pay the higher costs to get the
> same deal?

Like I said the last time this issue was discused on the mailing list, it's silly to think the seller of an asset starts off with a specific price they want to sell it at and is happy no matter what happens or how it gets fufilled. In the real world sellers and buyers want to know they're connected to actual sellers and buyers - not sybil attackers trying to shave off a margin for themselves - and are willing to pay a premium for that. Note all the hatred and vitrol directed towards high-frequency traders...

How *much* of a premium is an interesting question, and depends a lot on the specific scenario. For instance I fully expect to see a whole variety of mediums become used for the proof-of-publication needed, ranging from directly on a major blockchain to minor/less secure blockchains like Bitmessage over treechains to centralized-but-audited proof-of-publication schemes - AKA centralized exchanges - to standard exchanges. Point is, the concept of proof-of-publication makes these tradeoffs and options available and lets end-users pick the right one for their needs.

Accurate unbiased price information is worth money. In systems that allow third-parties to republish asset bids and offers we'll even see third-parties republishing bids and offers from less secure systems to more secure systems to get better price discovery.

> If this example is not enough to be able to explain the advantage of
> proof-of-publication markets feel free to write a more complex one.

I gotta ask, have you actually run the design and tradeoffs of Friemarket's past actual finance types? I have, and it's remarkable how excited many of them are about cryptographically provable fair price discovery.

On Sun, Dec 21, 2014 at 5:07 PM, Peter Todd <pete@petertodd•org> wrote:

> On Sun, Dec 21, 2014 at 12:25:36PM +0100, Jorge Timón wrote:
>> So let's go through an example to see in which ways
>> non-proof-of-publication orders are "insecure".
>>
>> Alice the seller wants to sell 1 unit of A for 100 units of B.
>> Bob is willing to pay up to 200 Bs for 1 A.
>>
>> Let's assume a proof of publication system first, in which the
>> execution price is the mean between bid and ask.
>> Alice publishes her order.
>> Bob could publish his order at price 200 Bs and the order would
>> execute at 150 Bs.
>> But after seeing Alice's order he knows he doesn't need to pay that
>> much, so he publishes and order buying for 100 Bs.
>>
>> Alice gets 100 Bs (what she signed she wanted) and Bob pays less than
>> he was wiling to pay, he pays 100 Bs. Everybody happy.
>>
>> Now let's assume native assets and sighash_single.
>
> Incidentally, SIGHASH_SINGLE is just as usable in embedded consensus;
> it's not specific to native assets.
>
>> So again, what's the advantage that proof-of-publication provides TO
>> ALICE so that she will be so eager to pay the higher costs to get the
>> same deal?
>
> Like I said the last time this issue was discused on the mailing list,
> it's silly to think the seller of an asset starts off with a specific
> price they want to sell it at and is happy no matter what happens or how
> it gets fufilled. In the real world sellers and buyers want to know
> they're connected to actual sellers and buyers - not sybil attackers
> trying to shave off a margin for themselves - and are willing to pay a
> premium for that. Note all the hatred and vitrol directed towards
> high-frequency traders...

And like last time we discussed this on the mailing list my opinion differs from yours. You talk about "real world sellers and buyers" but ignore Alice the seller and Bob the buyer in my example. You failed to explain how sybil attackers (Carol) get all those margins. In my example I claim miners get them, what am I missing? How is the same example with a proof-of-publication market any better? Miners can reorder the orders with proof of publication too. If getting orders into mined blocks faster has an advantage miners can charge privileged traders for privileged connections (just like it happens today with "perfectly fair" centralized markets today that feature the high-frequency trading you mention). They could even charge for moving transactions around within the same block if that has any effect on the execution rules. I prefer that miners can get the difference between bids and asks directly to compensate for their hashing power.

> How *much* of a premium is an interesting question, and depends a lot on
> the specific scenario. For instance I fully expect to see a whole
> variety of mediums become used for the proof-of-publication needed,
> ranging from directly on a major blockchain to minor/less secure
> blockchains like Bitmessage over treechains to centralized-but-audited
> proof-of-publication schemes - AKA centralized exchanges - to standard
> exchanges. Point is, the concept of proof-of-publication makes these
> tradeoffs and options available and lets end-users pick the right one
> for their needs.

The point is that there's more models for p2p markets beyond those that require proof of publication for their orders, and you're claiming that only those using proof of publication are secure. That's incorrect.

> Accurate unbiased price information is worth money.

Can you define "Accurate unbiased price information"?

> In systems that
> allow third-parties to republish asset bids and offers we'll even see
> third-parties republishing bids and offers from less secure systems to
> more secure systems to get better price discovery.

Traders want to trade. The primary function of markets is exchange, not price discovery.

>> If this example is not enough to be able to explain the advantage of
>> proof-of-publication markets feel free to write a more complex one.
>
> I gotta ask, have you actually run the design and tradeoffs of
> Friemarket's past actual finance types? I have, and it's remarkable how
> excited many of them are about cryptographically provable fair price
> discovery.

"Provably fair price discovery" is probably impossible. But I can imagine how many people could get excited about such a technology. Can you formally define what you mean by this? You see, "fair" implies morality and therefore it's a very subjective term, so it's not obvious to me what you may mean by that.

> --
> 'peter'[:-1]@petertodd.org
> 000000000000000002661192e72bdc83e6c8101371520159531301aa1437cc2c

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.

(Again nothing new to say here, just putting my notes in this discussion, where I started with an earlier discussion that Peter wrote up with a subject of "disentangling" blockchain design).

In the discussion last year that started the analysis of "disentangling" blockchain design I had broken out the candidate layer properties that one could use as building blocks to construct a decentralised PoW-chain assured immutable history based ecash system as:

- time-stamping (really just time-ordered as network time is weak)

- namespace (first come first served name value pairs)

I thought it was interesting to look at potential minimum enabling functionality in order to explore whether the consensus critical code could be simplified for security, and also to understand the tradeoffs towards seeing if there were any improvements that could be found. (And it seems its pretty hard to find any improvements was my conclusion).

Time-stamping (or time-ordering) at a requirements level does not have to imply that there is a uniqueness guarantee, or even that the nodes see what they are time-stamping (it could be committed with a random nonce) and indeed hiding the committed data from the service and public view is a common property of time-stamping. Time-ordering just creates an immutable (and not strongly deduplicated) stream of data items that came from various users and had a time-ordering placed on them.

Minimally the person who submitted the data item would need to know the merkle path to it, and that might be achieved by publishing the merkle tree, where some or all of the leaves are hidden commitments.

For bitcoin composability purposes you might require that there be no hidden commitments, and then other miners and full nodes could download all the merkle trees for each PoW-interval and ignore duplicates.

Namespace service adds the uniqueness and first-come first-served property up-front (as its more efficient for people catching up to not have to download and discard duplicates/double-spends), and this more strict rule requires miners to know about (and presumably index) all previous information to avoid violating this rule. I assume name attributes to hold information like a public key to approve changes in ownership, an IP address, an email address etc. For efficient proof reasons there is still a merkle tree per PoW time-interval binding names into a hash-chain.

For bitcoin re-described using a namespace the unique coins are the names, and values and ownership public key etc are attributes of the name; names (coins) are only added (via mining) or after deletion (spend/transfer) of previous names. Transfers are approved via digital signature.

The additional property bitcoin requires is that the values add up.

I presume the phrase proof of publication means to draw out separately that the full-node version of bitcoin requires a rule that miners should not build on top of blocks unless they have copies of all data committed to. Otherwise a malicious party can hide ownership transfers that can be revealed later, so that no one is assured of ownership: any possibility for a gap in the ownership chain calls into question ownership. So from that perspective a miner consensus rule that it should not build on top of blocks that it hasnt seen a full gap-free history for makes the PoW chain a kind of proof that the miner population at one time saw all data hashed into it.

I think you need one more thing which is that the miners (and other full nodes who have copies of the data) are willing to share that historic data with you. There is some meta-incentive for bitcoin holders to help others catchup and be assured of the history and information has to be broadcast as there are many miners and full-nodes.

I presume anti-relay term is meant at system level, rather than node level, though technically bitcoin nodes in the current protocol version dont relay double-spent transactions. Particularly that miners wont bless double-spent transactions (and will do PoW only over non double-spent transfers).

While there does seem to be some confusion from some people perhaps not realising that it is essential that there are no gaps in the ownership chain, I am not sure there are necessarily any practical implication of philosophical differences between proof of publication & anti-relay (or namespace for that matter). It is also important that there is no way to attack the insertion logic so that eg someone cant get a hash into an internal nor leaf node of the merkle tree without the miners first seeing that data.

Presumably as they are all describing ways to think about bitcoin and assuming no one is confused about how bitcoin works, the distinction just comes down to what features are assumed to be naturally included in the layer definition, and what features have to be added. For example I think its relatively normally assumed that people can look up names.

I suppose it might be possible to put a self-authenticating access handle for the data item into the data set which points into a redundant immutable data store. In effect that is what the bitcoin nodes do provide (with full redundancy). But, more efficiently though perhaps with less redundancy and assurance, one could put the data into tahoe-lafs which implements immutability, append-only and self-authenticating urls and such properties. From that perspective it does make sense to say there is a layer that provides assurance of availability of history; the PoW-chain and merkle-tree in the header assures already immutability. The remaining thing that has to be assured is availability.

Adam

On 20 December 2014 at 14:48, Peter Todd <pete@petertodd•org> wrote:

> Gregory Maxwell recently pointed out to me in private conservation that
> there potentially existed a fundemental disagreement between him and I
> on our philosophical approaches to blockchains, in that he prioritised
> the notion of the blockchain as an anti-replay oracle, and I prioritised
> it as a publication layer. Here I'll talk about the differences and
> simularities between those two approaches.

On 2014-12-22 00:11, Peter Todd wrote:

> On Sat, Dec 20, 2014 at 09:48:01AM -0500, Peter Todd wrote:
> 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.

Are we going to get an answer to this or Adam Back's critique? Doesn't sound like this so-called "proof-of-publication" actually works according to the experts. Is it an concept anyone but Peter Todd actually believes in?