* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-12 9:05 Peter Todd
2014-12-12 12:25 ` Gareth Williams
` (2 more replies)
0 siblings, 3 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-12 9:05 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 17259 bytes --]
Introduction
============
While not a new concept proof-of-publication is receiving a significant
amount of attention right now both as an idea, with regard to the
embedded consensus systems that make use of it, and in regard to the
sidechains model proposed by Blockstream that rejects it. Here we give a
clear definition of proof-of-publication and its weaker predecessor
timestamping, describe some usecases for it, and finally dispel some of
the common myths about it.
What is timestamping?
=====================
A cryptographic timestamp proves that message m existed prior to some
time t.
This is the cryptographic equivalent of mailing yourself a patentable
idea in a sealed envelope to establish the date at which the idea
existed on paper.
Traditionally this has been done with one or more trusted third parties
who attest to the fact that they saw m prior to the time t. More
recently blockchains have been used for this purpose, particularly the
Bitcoin blockchain, as block headers include a block time which is
verified by the consensus algorithm.
What is proof-of-publication?
=============================
Proof-of-publication is what solves the double-spend problem.
Cryptographic proof-of-publication actually refers to a few closely
related proofs, and practical uses of it will generally make use of more
than one proof.
Proof-of-receipt
----------------
Prove that every member p in of audience P has received message m. A
real world analogy is a legal notice being published in a major
newspaper - we can assume any subscriber received the message and had a
chance to read it.
Proof-of-non-publication
------------------------
Prove that message m has *not* been published. Extending the above real
world analogy the court can easily determine that a legal notice was not
published when it should have been by examining newspaper archives. (or
equally, *because* the notice had not been published, some action a
litigant had taken was permissable)
Proof-of-membership
-------------------
A proof-of-non-publication isn't very useful if you can't prove that
some member q is in the audience P. In particular, if you are to
evaluate a proof-of-membership, q is yourself, and you want assurance
you are in that audience. In the case of our newspaper analogy because
we know what today's date is, and we trust the newspaper never to
publish two different editions with the same date we can be certain we
have searched all possible issues where the legal notice may have been
published.
Real-world proof-of-publication: The Torrens Title System
---------------------------------------------------------
Land titles are a real-world example, dating back centuries, with
remarkable simularities to the Bitcoin blockchain. Prior to the torrens
system land was transferred between owners through a chain of valid
title deeds going back to some "genesis" event establishing rightful
ownership independently of prior history. As with the blockchain the
title deed system has two main problems: establishing that each title
deed in the chain is valid in isolation, and establishing that no other
valid title deeds exist. While the analogy isn't exact - establishing
the validity of title deeds isn't as crisp a process as simple checking
a cryptographic signature - these two basic problems are closely related
to the actions of checking a transaction's signatures in isolation, and
ensuring it hasn't been double-spent.
To solve these problems the Torrens title system was developed, first in
Australia and later Canada, to establish a singular central registry of
deeds, or property transfers. Simplifying a bit we can say inclusion -
publication - in the official registery is a necessary pre-condition to
a given property transfer being valid. Multiple competing transfers are
made obvious, and the true valid transfer can be determined by whichever
transfer happened first.
Similarly in places where the Torrens title system has not been adopted,
almost always a small number of title insurance providers have taken on
the same role. The title insurance provider maintains a database of all
known title deeds, and in practice if a given title deed isn't published
in the database it's not considered valid.
Common myths
============
Proof-of-publication is the same as timestamping
------------------------------------------------
No. Timestamping is a significantly weaker primitive than
proof-of-publication. This myth seems to persist because unfortunately
many members of the Bitcoin development and theory community - and even
members of the Blockstream project - have frequently used the term
"timestamping" for applications that need proof-of-publication.
Publication means publishing meaningful data to the whole world
---------------------------------------------------------------
No. The data to be published can often be an otherwise meaningless
nonce, indistinguishable from any other random value. (e.g. an ECC
pubkey)
For example colored coins can be implemented by committing the hash of
the map of colored inputs to outputs inside a transaction. These maps
can be passed from payee to payor to prove that a given output is
colored with a set of recursive proofs, as is done in the author's
Smartcolors library. The commitment itself can be a simple hash, or even
a pay-to-contract style derived pubkey.
A second example is Zerocash, which depends on global consensus of a set
of revealed serial numbers. As this set can include "false-positives" -
false revealed serial numbers that do not actually correspond to a real
Zerocash transaction - the blockchain itself can be that set. The
Zerocash transactions themselves - and associated proofs - can then be
passed around via a p2p network separate from the blockchain itself.
Each Zerocash Pour proof then simply needs to specify what set of
priorly evaluated proofs makes up its particular commitment merkle tree
and the proofs are then evaluated against that proof-specific tree. (in
practice likely some kind of DAG-like structure) (note that there is a
sybil attack risk here: a sybil attack reduces your k-anonymity set by
the number of transactions you were prevented from seeing; a weaker
proof-of-publication mechanism may be appropriate to prevent that sybil
attack).
The published data may also not be meaningful because it is encrypted.
Only a small community may need to come to consensus about it; everyone
else can ignore it. For instance proof-of-publication for decentralized
asset exchange is an application where you need publication to be
timely, however the audience may still be small. That audience can share
an encryption key.
Proof-of-publication is always easy to censor
---------------------------------------------
No, with some precautions. This myth is closely related to the above
idea that the data must be globally meaningful to be useful. The colored
coin and Zerocash examples above are cases where censoring the
publication is obviously impossible as it can be made prior to giving
anyone at all sufficient info to determine if the publicaiton has been
made; the data itself is just nonces.
In the case of encrypted data the encryption key can also often be
revealed well after the publication has been made. For instance in a
Certificate Transparency scheme the certificate authority (CA) may use
proof-of-publication to prove that a certificate was in a set of
certificates. If that set of certificates is hashed into a merkelized
binary prefix tree indexed by domain name the correct certificate for a
given domain name - or lack thereof - is easily proven. Changes to that
set can be published on the blockchain by publishing successive prefix
tree commitments.
If these commitments are encrypted, each commitment C_i can also commit
to the encryption key to be used for C_{i+1}. That key need not be
revealed until the commitment is published; validitity is assured as
every client knows that only one C_{i+1} is possible, so any malfeasance
is guaranteed to be revealed when C_{i+2} is published.
Secondly the published data can be timelock encrypted with timelocks
that take more than the average block interval to decrypt. This puts
would-be censoring miners into a position of either delaying all
transactions, or accepting that they will end up mining publication
proofs. The only way to circumvent this is highly restrictive
whitelisting.
Proof-of-publication is easier to censor than (merge)-mined sidechains
----------------------------------------------------------------------
False under all circumstances. Even if the publications use no
anti-censorship techniques to succesfully censor a proof-of-publication
system at least 51% of the total hashing power must decide to censor it,
and they must do so by attacking the other 49% of hashing power -
specifically rejecting their blocks. This is true no matter how "niche"
the proof-of-publication system is - whether it is used by two people or
two million people it has the same security.
On the other hand a (merge)-mined sidechain with x% of the total hashing
power supporting it can be attacked at by anyone with >x% hashing power.
In the case of a merge-mined sidechain this cost will often be near zero
- only by providing miners with a significant and ongoing reward can the
marginal cost be made high. In the case of sidechains with niche
audiences this is particularly true - sidechain advocates have often
advocated that sidechains be initially protected by centralized
checkpoints until they become popular enough to begin to be secure.
Secondly sidechains can't make use of anti-censorship techniques the way
proof-of-publication systems can: they inherently must be public for
miners to be able to mine them in a decentralized fashion. Of course,
users of them may use anti-censorship techniques, but that leads to a
simple security-vs-cost tradeoff between using the Bitcoin blockchain
and a sidechain. (note the simularity to the author's treechains
proposal!)
Proof-of-publication can be made expensive
------------------------------------------
True, in some cases! By tightly constraining the Bitcoin scripting
system the available bytes for stenographic embedment can be reduced.
For instance P2SH^2 requires an brute force exponentially increasing
amount of hashes-per-byte-per-pushdata. However this is still
ineffective against publishing hashes, and to fully implement it -
scriptSigs included - would require highly invasive changes to the
entire scripting system that would greatly limit its value.
Proof-of-publication can be outsourced to untrusted third-parties
-----------------------------------------------------------------
Timestamping yes, but proof-of-publication no.
We're talking about systems that attempt to publish multiple pieces of
data from multiple parties with a single hash in the Bitcoin blockchain,
such as Factom. Essentially this works by having a "child" blockchain,
and the hash of that child blockchain is published in the master Bitcoin
blockchain. To prove publicaiton you prove that your message is in that
child chain, and the child chain is itself published in the Bitcoin
blockchain. Proving membership is possible for yourself by determining
if you have the contents corresponding to the most recent child-chain
hash.
The problem is proving non-publication. The set of all *potential*
child-chain hashes must be possible to obtain by scanning the Bitcoin
blockchain. As a hash is meaningless by itself, these hashes must be
signed. That introduces a trusted third-party who can also sign an
invalid hash that does not correspond to a block and publish it in the
blockchain. This in turn makes it impossible for anyone using the child
blockchain to prove non-publication - they can't prove they did not
publish a message because the content of *all* child blockchains is now
unknown.
In short, Factom and systems like it rely on trusted third parties who
can put you in a position where you can't prove you did not commit
fraud.
Proof-of-publication "bloats" the blockchain
--------------------------------------------
Depends on your perspective.
Systems that do not make use of the UTXO are no different technically
than any other transaction: they pay fees to publish messages to the
Bitcoin blockchain with no amortized increase in the UTXO set. Some
systems do grow the UTXO set - a potential scaling problem as currently
that all full nodes must have the entire UTXO set - although there are a
number of existing mechanisms and proposals to mitigate this issue such
as the (crippled) OP_RETURN scriptPubKey format, the dust rule, the
authors TXO commitments, UTXO expiry etc.
From an economic point of view proof-of-publication systems compete with
other uses of the blockchain as they pay fees; supply of blockchain
space is fixed so the increased demand must result in a higher
per-transaction price in fees. On the other hand this is true of *all*
uses of the blockchain, which collectively share the limited transaction
capacity. For instance Satoshidice and similar sites have been widely
condemned for doing conventional transactions on Bitcoin when they could
have potentially used off-chain transactions.
It's unknown what the effect on the Bitcoin price will actually be. Some
proof-of-publication uses have nothing to do with money at all - e.g.
certificate transparency. Others are only indirectly related, such as
securing financial audit logs such as merkle-sum-trees of total Bitcoins
held by exchanges. Others in effect add new features to Bitcoin, such as
how colored coins allows the trade of assets on the blockchain, or how
Zerocash makes Bitcoin transactions anonymous. The sum total of all
these effects on the Bitcoin price is difficult to predict.
The authors belief is that even if proof-of-publication is a
net-negative to Bitcoin as it is significantly more secure than the
alternatives and can't be effectively censored people will use it
regardless of effects to discourage them through social pressure. Thus
Bitcoin must make technical improvements to scalability that negate
these potentially harmful effects.
Proof-of-publication systems are inefficient
--------------------------------------------
If you're talking about inefficient from the perspective of a full-node
that does full validation, they are no different than (merge)-mined
sidechain and altcoin alternatives. If you're talking about efficiency
from the perspective of a SPV client, then yes, proof-of-publication
systems will often require more resources than mining-based
alternatives.
However it must be remembered that the cost of mining is the
introduction of a trusted third party - miners. Of course, mined
proof-of-publication has miners already, but trusting those miners to
determine the meaning of that data places significantly more trust in
them than mearly trusting them to create consensus on the order in which
data is published.
Many usecases involve trusted third-parties anyway - the role of
proof-of-publication is to hold those third-parties to account and keep
them honest. For these use-cases - certificate transparency, audit logs,
financial assets - mined alternatives simply add new trusted third
parties and points of failure rather than remove them.
Of course, global consensus is inefficient - Bitcoin itself is
inefficient. But this is a fundemental problem to Bitcoin's architecture
that applies to all uses of it, a problem that should be solved in
general.
Proof-of-publication needs "scamcoins" like Mastercoin and Counterparty
-----------------------------------------------------------------------
First of all, whether or not a limited-supply token is a "scam" is not a
technical question. However some types of embedded consensus systems, a
specific use-case for proof-of-publication, do require limited-supply
tokens within the system for technical reasons, for instance to support
bid orders functionality in decentralized marketplaces.
Secondly using a limited-supply token in a proof-of-publicaton system is
what lets you have secure client side validation rather than the
alternative of 2-way-pegging that requires users to trust miners not to
steal the pegged funds. Tokens also do not need to be, economically
speaking, assets that can appreciate in value relative to Bitcoin;
one-way-pegs where Bitcoins can always be turned into the token in
conjunction with decentralized exchange to buy and sell tokens for
Bitcoins ensure the token value will always closely approximate the
Bitcoin value as long as the protocol itself is considered valuable.
Finally only a subset of proof-of-publication use-cases involve tokens
at all - many like colored coins transact directly to and from Bitcoin,
while other use-cases don't even involve finance at all.
--
'peter'[:-1]@petertodd.org
00000000000000000681f4e5c84bc0bf7e6c5db8673eef225da652fbb785a0de
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 9:05 [Bitcoin-development] Setting the record straight on Proof-of-Publication Peter Todd
@ 2014-12-12 12:25 ` Gareth Williams
2014-12-12 17:04 ` Alex Mizrahi
2014-12-12 13:41 ` odinn
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
2 siblings, 1 reply; 30+ messages in thread
From: Gareth Williams @ 2014-12-12 12:25 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1428 bytes --]
On 12/12/14 20:05, Peter Todd wrote:
> Secondly using a limited-supply token in a proof-of-publicaton system is
> what lets you have secure client side validation rather than the
> alternative of 2-way-pegging that requires users to trust miners not to
> steal the pegged funds.
"Secure" and "client side validation" don't really belong in the same
sentence, do they?
If I am to accept a transaction with any assurance of security at all,
the important question to ask is not: "does my client consider this
valid?" but: "does the rest of the world consider this valid?"
Validated data in the blockchain is far more useful for this purpose
than unvalidated data with a mere proof of publication in the
blockchain, precisely because it records what /everybody else/ considers
valid history (and very likely will continue to consider valid history
in future.)
Pegged sidechains have their challenges, but at least they provide
distributed consensus on transaction history.
Proof-of-publication systems like Counterparty and Mastercoin require me
to trust, with zero evidence, that everybody else's client has the exact
same interpretation of transaction history as mine, and will continue to
have for the indefinite future. How is that not a horribly broken
security model? I'd use a sidechain - with reasonable parameters that
disincentivise peg theft as much as practical - over that any day.
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 9:05 [Bitcoin-development] Setting the record straight on Proof-of-Publication Peter Todd
2014-12-12 12:25 ` Gareth Williams
@ 2014-12-12 13:41 ` odinn
2014-12-12 14:17 ` Justus Ranvier
2014-12-15 4:59 ` Peter Todd
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
2 siblings, 2 replies; 30+ messages in thread
From: odinn @ 2014-12-12 13:41 UTC (permalink / raw)
To: bitcoin-development
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
Peter... It kind of sounds to me that (as fine of a position paper as
this is) on _certain_ points, you're falling prey to the "but it's
inefficient, but it's a scamcoin, but luke-jr told me so" argument...
I think the Mastercoin devs are doing fine work and I consider the
zerocash devs to have developed (in v2, mint and pour) to have
developed something that will really turn the world on its ear, but
what do I know? Nothing. Nothing at all.
gmorning
Peter Todd:
> Introduction ============
>
> While not a new concept proof-of-publication is receiving a
> significant amount of attention right now both as an idea, with
> regard to the embedded consensus systems that make use of it, and
> in regard to the sidechains model proposed by Blockstream that
> rejects it. Here we give a clear definition of proof-of-publication
> and its weaker predecessor timestamping, describe some usecases for
> it, and finally dispel some of the common myths about it.
>
>
> What is timestamping? =====================
>
> A cryptographic timestamp proves that message m existed prior to
> some time t.
>
> This is the cryptographic equivalent of mailing yourself a
> patentable idea in a sealed envelope to establish the date at which
> the idea existed on paper.
>
> Traditionally this has been done with one or more trusted third
> parties who attest to the fact that they saw m prior to the time t.
> More recently blockchains have been used for this purpose,
> particularly the Bitcoin blockchain, as block headers include a
> block time which is verified by the consensus algorithm.
>
>
> What is proof-of-publication? =============================
>
> Proof-of-publication is what solves the double-spend problem.
>
> Cryptographic proof-of-publication actually refers to a few
> closely related proofs, and practical uses of it will generally
> make use of more than one proof.
>
>
> Proof-of-receipt ----------------
>
> Prove that every member p in of audience P has received message m.
> A real world analogy is a legal notice being published in a major
> newspaper - we can assume any subscriber received the message and
> had a chance to read it.
>
>
> Proof-of-non-publication ------------------------
>
> Prove that message m has *not* been published. Extending the above
> real world analogy the court can easily determine that a legal
> notice was not published when it should have been by examining
> newspaper archives. (or equally, *because* the notice had not been
> published, some action a litigant had taken was permissable)
>
>
> Proof-of-membership -------------------
>
> A proof-of-non-publication isn't very useful if you can't prove
> that some member q is in the audience P. In particular, if you are
> to evaluate a proof-of-membership, q is yourself, and you want
> assurance you are in that audience. In the case of our newspaper
> analogy because we know what today's date is, and we trust the
> newspaper never to publish two different editions with the same
> date we can be certain we have searched all possible issues where
> the legal notice may have been published.
>
>
> Real-world proof-of-publication: The Torrens Title System
> ---------------------------------------------------------
>
> Land titles are a real-world example, dating back centuries, with
> remarkable simularities to the Bitcoin blockchain. Prior to the
> torrens system land was transferred between owners through a chain
> of valid title deeds going back to some "genesis" event
> establishing rightful ownership independently of prior history. As
> with the blockchain the title deed system has two main problems:
> establishing that each title deed in the chain is valid in
> isolation, and establishing that no other valid title deeds exist.
> While the analogy isn't exact - establishing the validity of title
> deeds isn't as crisp a process as simple checking a cryptographic
> signature - these two basic problems are closely related to the
> actions of checking a transaction's signatures in isolation, and
> ensuring it hasn't been double-spent.
>
> To solve these problems the Torrens title system was developed,
> first in Australia and later Canada, to establish a singular
> central registry of deeds, or property transfers. Simplifying a bit
> we can say inclusion - publication - in the official registery is a
> necessary pre-condition to a given property transfer being valid.
> Multiple competing transfers are made obvious, and the true valid
> transfer can be determined by whichever transfer happened first.
>
> Similarly in places where the Torrens title system has not been
> adopted, almost always a small number of title insurance providers
> have taken on the same role. The title insurance provider maintains
> a database of all known title deeds, and in practice if a given
> title deed isn't published in the database it's not considered
> valid.
>
>
> Common myths ============
>
> Proof-of-publication is the same as timestamping
> ------------------------------------------------
>
> No. Timestamping is a significantly weaker primitive than
> proof-of-publication. This myth seems to persist because
> unfortunately many members of the Bitcoin development and theory
> community - and even members of the Blockstream project - have
> frequently used the term "timestamping" for applications that need
> proof-of-publication.
>
>
> Publication means publishing meaningful data to the whole world
> ---------------------------------------------------------------
>
> No. The data to be published can often be an otherwise meaningless
> nonce, indistinguishable from any other random value. (e.g. an ECC
> pubkey)
>
> For example colored coins can be implemented by committing the hash
> of the map of colored inputs to outputs inside a transaction. These
> maps can be passed from payee to payor to prove that a given output
> is colored with a set of recursive proofs, as is done in the
> author's Smartcolors library. The commitment itself can be a simple
> hash, or even a pay-to-contract style derived pubkey.
>
> A second example is Zerocash, which depends on global consensus of
> a set of revealed serial numbers. As this set can include
> "false-positives" - false revealed serial numbers that do not
> actually correspond to a real Zerocash transaction - the blockchain
> itself can be that set. The Zerocash transactions themselves - and
> associated proofs - can then be passed around via a p2p network
> separate from the blockchain itself. Each Zerocash Pour proof then
> simply needs to specify what set of priorly evaluated proofs makes
> up its particular commitment merkle tree and the proofs are then
> evaluated against that proof-specific tree. (in practice likely
> some kind of DAG-like structure) (note that there is a sybil attack
> risk here: a sybil attack reduces your k-anonymity set by the
> number of transactions you were prevented from seeing; a weaker
> proof-of-publication mechanism may be appropriate to prevent that
> sybil attack).
>
> The published data may also not be meaningful because it is
> encrypted. Only a small community may need to come to consensus
> about it; everyone else can ignore it. For instance
> proof-of-publication for decentralized asset exchange is an
> application where you need publication to be timely, however the
> audience may still be small. That audience can share an encryption
> key.
>
>
> Proof-of-publication is always easy to censor
> ---------------------------------------------
>
> No, with some precautions. This myth is closely related to the
> above idea that the data must be globally meaningful to be useful.
> The colored coin and Zerocash examples above are cases where
> censoring the publication is obviously impossible as it can be made
> prior to giving anyone at all sufficient info to determine if the
> publicaiton has been made; the data itself is just nonces.
>
> In the case of encrypted data the encryption key can also often be
> revealed well after the publication has been made. For instance in
> a Certificate Transparency scheme the certificate authority (CA)
> may use proof-of-publication to prove that a certificate was in a
> set of certificates. If that set of certificates is hashed into a
> merkelized binary prefix tree indexed by domain name the correct
> certificate for a given domain name - or lack thereof - is easily
> proven. Changes to that set can be published on the blockchain by
> publishing successive prefix tree commitments.
>
> If these commitments are encrypted, each commitment C_i can also
> commit to the encryption key to be used for C_{i+1}. That key need
> not be revealed until the commitment is published; validitity is
> assured as every client knows that only one C_{i+1} is possible, so
> any malfeasance is guaranteed to be revealed when C_{i+2} is
> published.
>
> Secondly the published data can be timelock encrypted with
> timelocks that take more than the average block interval to
> decrypt. This puts would-be censoring miners into a position of
> either delaying all transactions, or accepting that they will end
> up mining publication proofs. The only way to circumvent this is
> highly restrictive whitelisting.
>
>
> Proof-of-publication is easier to censor than (merge)-mined
> sidechains
> ----------------------------------------------------------------------
>
> False under all circumstances. Even if the publications use no
> anti-censorship techniques to succesfully censor a
> proof-of-publication system at least 51% of the total hashing power
> must decide to censor it, and they must do so by attacking the
> other 49% of hashing power - specifically rejecting their blocks.
> This is true no matter how "niche" the proof-of-publication system
> is - whether it is used by two people or two million people it has
> the same security.
>
> On the other hand a (merge)-mined sidechain with x% of the total
> hashing power supporting it can be attacked at by anyone with >x%
> hashing power. In the case of a merge-mined sidechain this cost
> will often be near zero - only by providing miners with a
> significant and ongoing reward can the marginal cost be made high.
> In the case of sidechains with niche audiences this is particularly
> true - sidechain advocates have often advocated that sidechains be
> initially protected by centralized checkpoints until they become
> popular enough to begin to be secure.
>
> Secondly sidechains can't make use of anti-censorship techniques
> the way proof-of-publication systems can: they inherently must be
> public for miners to be able to mine them in a decentralized
> fashion. Of course, users of them may use anti-censorship
> techniques, but that leads to a simple security-vs-cost tradeoff
> between using the Bitcoin blockchain and a sidechain. (note the
> simularity to the author's treechains proposal!)
>
>
> Proof-of-publication can be made expensive
> ------------------------------------------
>
> True, in some cases! By tightly constraining the Bitcoin scripting
> system the available bytes for stenographic embedment can be
> reduced. For instance P2SH^2 requires an brute force exponentially
> increasing amount of hashes-per-byte-per-pushdata. However this is
> still ineffective against publishing hashes, and to fully implement
> it - scriptSigs included - would require highly invasive changes to
> the entire scripting system that would greatly limit its value.
>
>
> Proof-of-publication can be outsourced to untrusted third-parties
> -----------------------------------------------------------------
>
> Timestamping yes, but proof-of-publication no.
>
> We're talking about systems that attempt to publish multiple pieces
> of data from multiple parties with a single hash in the Bitcoin
> blockchain, such as Factom. Essentially this works by having a
> "child" blockchain, and the hash of that child blockchain is
> published in the master Bitcoin blockchain. To prove publicaiton
> you prove that your message is in that child chain, and the child
> chain is itself published in the Bitcoin blockchain. Proving
> membership is possible for yourself by determining if you have the
> contents corresponding to the most recent child-chain hash.
>
> The problem is proving non-publication. The set of all *potential*
> child-chain hashes must be possible to obtain by scanning the
> Bitcoin blockchain. As a hash is meaningless by itself, these
> hashes must be signed. That introduces a trusted third-party who
> can also sign an invalid hash that does not correspond to a block
> and publish it in the blockchain. This in turn makes it impossible
> for anyone using the child blockchain to prove non-publication -
> they can't prove they did not publish a message because the content
> of *all* child blockchains is now unknown.
>
> In short, Factom and systems like it rely on trusted third parties
> who can put you in a position where you can't prove you did not
> commit fraud.
>
>
> Proof-of-publication "bloats" the blockchain
> --------------------------------------------
>
> Depends on your perspective.
>
> Systems that do not make use of the UTXO are no different
> technically than any other transaction: they pay fees to publish
> messages to the Bitcoin blockchain with no amortized increase in
> the UTXO set. Some systems do grow the UTXO set - a potential
> scaling problem as currently that all full nodes must have the
> entire UTXO set - although there are a number of existing
> mechanisms and proposals to mitigate this issue such as the
> (crippled) OP_RETURN scriptPubKey format, the dust rule, the
> authors TXO commitments, UTXO expiry etc.
>
> From an economic point of view proof-of-publication systems compete
> with other uses of the blockchain as they pay fees; supply of
> blockchain space is fixed so the increased demand must result in a
> higher per-transaction price in fees. On the other hand this is
> true of *all* uses of the blockchain, which collectively share the
> limited transaction capacity. For instance Satoshidice and similar
> sites have been widely condemned for doing conventional
> transactions on Bitcoin when they could have potentially used
> off-chain transactions.
>
> It's unknown what the effect on the Bitcoin price will actually be.
> Some proof-of-publication uses have nothing to do with money at all
> - e.g. certificate transparency. Others are only indirectly
> related, such as securing financial audit logs such as
> merkle-sum-trees of total Bitcoins held by exchanges. Others in
> effect add new features to Bitcoin, such as how colored coins
> allows the trade of assets on the blockchain, or how Zerocash makes
> Bitcoin transactions anonymous. The sum total of all these effects
> on the Bitcoin price is difficult to predict.
>
> The authors belief is that even if proof-of-publication is a
> net-negative to Bitcoin as it is significantly more secure than
> the alternatives and can't be effectively censored people will use
> it regardless of effects to discourage them through social
> pressure. Thus Bitcoin must make technical improvements to
> scalability that negate these potentially harmful effects.
>
>
> Proof-of-publication systems are inefficient
> --------------------------------------------
>
> If you're talking about inefficient from the perspective of a
> full-node that does full validation, they are no different than
> (merge)-mined sidechain and altcoin alternatives. If you're talking
> about efficiency from the perspective of a SPV client, then yes,
> proof-of-publication systems will often require more resources than
> mining-based alternatives.
>
> However it must be remembered that the cost of mining is the
> introduction of a trusted third party - miners. Of course, mined
> proof-of-publication has miners already, but trusting those miners
> to determine the meaning of that data places significantly more
> trust in them than mearly trusting them to create consensus on the
> order in which data is published.
>
> Many usecases involve trusted third-parties anyway - the role of
> proof-of-publication is to hold those third-parties to account and
> keep them honest. For these use-cases - certificate transparency,
> audit logs, financial assets - mined alternatives simply add new
> trusted third parties and points of failure rather than remove
> them.
>
> Of course, global consensus is inefficient - Bitcoin itself is
> inefficient. But this is a fundemental problem to Bitcoin's
> architecture that applies to all uses of it, a problem that should
> be solved in general.
>
>
> Proof-of-publication needs "scamcoins" like Mastercoin and
> Counterparty
> -----------------------------------------------------------------------
>
> First of all, whether or not a limited-supply token is a "scam" is
> not a technical question. However some types of embedded consensus
> systems, a specific use-case for proof-of-publication, do require
> limited-supply tokens within the system for technical reasons, for
> instance to support bid orders functionality in decentralized
> marketplaces.
>
> Secondly using a limited-supply token in a proof-of-publicaton
> system is what lets you have secure client side validation rather
> than the alternative of 2-way-pegging that requires users to trust
> miners not to steal the pegged funds. Tokens also do not need to
> be, economically speaking, assets that can appreciate in value
> relative to Bitcoin; one-way-pegs where Bitcoins can always be
> turned into the token in conjunction with decentralized exchange to
> buy and sell tokens for Bitcoins ensure the token value will always
> closely approximate the Bitcoin value as long as the protocol
> itself is considered valuable.
>
> Finally only a subset of proof-of-publication use-cases involve
> tokens at all - many like colored coins transact directly to and
> from Bitcoin, while other use-cases don't even involve finance at
> all.
>
>
>
> ------------------------------------------------------------------------------
>
>
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and
> Dashboards with Interactivity, Sharing, Native Excel Exports, App
> Integration & more Get technology previously reserved for
> billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
>
>
>
>
> _______________________________________________ Bitcoin-development
> mailing list Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
- --
http://abis.io ~
"a protocol concept to enable decentralization
and expansion of a giving economy, and a new social good"
https://keybase.io/odinn
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCgAGBQJUivCNAAoJEGxwq/inSG8ChVUH/26zj2pj7AF+oa2RDkPZN980
qFTY7x2s9w97bEuCiFfFpYjIP26mY4+snuoTWBa8yCp7gLVVsk9JKkN0dmXIboXf
ocoJY9s/wT7QLqJMRRwWb/8XPKwjXB10PNawCRoUk++8E0Y+W6mxiH5Gs1UnYKwI
2DHHh/hTh35mR5burwdLGEMLaVtK4BFLJTZwW+4xlWESsoWeQnxEuty799HldOaN
+wms8dvtZlzJElLUPjBGBZT6DRTaPsvqSvQ0CnHI84LYwuUObMcV89mkBcfTHlMt
MczwaO7CCc/jmoOoQKDyIVuW1eJeXggln+LOS34qwH8rCgjdOZeT3y4PgUTZ+AM=
=Sm96
-----END PGP SIGNATURE-----
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 13:41 ` odinn
@ 2014-12-12 14:17 ` Justus Ranvier
2014-12-15 4:59 ` Peter Todd
1 sibling, 0 replies; 30+ messages in thread
From: Justus Ranvier @ 2014-12-12 14:17 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 795 bytes --]
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256
On 12/12/2014 01:41 PM, odinn wrote:
> I think the Mastercoin devs are doing fine work
I wonder if all the Mastercoin devs would agree with that statement.
- --
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJUivkLAAoJEMP3uyY4RQ21r5cIANvabja0i5j79a6KSkKOgEyR
LhBz4mugzTc8Zej2NBeyEtv0pzO4fs5wvQo4N/1BW7aHXuFJsgJpGlV8thkuFhek
UhoPC23i7u3jCPQ30PintqvCBCimse+PJa60KE2QL2DZn7WgRGKrEuo41AROxeit
vfVMcFULc6bB9hxIEBpcU4RuwKJHVgzSHMkO75/uHHtPLJ9TbCfqcxT146cZvSjc
Tc62ukuX1xBj5PhQM8GaUGzkQcfcZ+7d3DD1X22Gk1U6w+zat52dapy/qYgn9oA5
ubk/p/7Kywd8D44rPsr/pbdlDZxG0w77yRJIMboXhFMV7rY3sMRHHQmAUz+I8FY=
=R4pR
-----END PGP SIGNATURE-----
[-- Attachment #2: 0x38450DB5.asc --]
[-- Type: application/pgp-keys, Size: 14542 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 12:25 ` Gareth Williams
@ 2014-12-12 17:04 ` Alex Mizrahi
[not found] ` <CAOG=w-v3qjG3zd_WhfFU-OGnsHZEuYvY82eL4GqcdgY6np5bvA@mail.gmail.com>
0 siblings, 1 reply; 30+ messages in thread
From: Alex Mizrahi @ 2014-12-12 17:04 UTC (permalink / raw)
To: Gareth Williams; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 850 bytes --]
>
> "Secure" and "client side validation" don't really belong in the same
> sentence, do they?
>
Well, client-side validation is mathematically secure, while SPV is
economically secure.
I.e. it is secure if you make several assumptions about economics of the
whole thing.
In my opinion the former is transfinitely more secure than the later.
But it's more of a philosophical question, sure.
The good thing about PoW-based consensus is that it is robust against
version inconsistencies and various accidents of this nature up to a
certain degree. But you hardly can depend on that:
You know, The Great Fork of 2013 was resolved through human intervention,
Bitcoin nodes were not smart enough to detect that something is going awry
on their own.
Naive proof-of-publication is very fragile in that respect, but you can
easily bring back robustness.
[-- Attachment #2: Type: text/html, Size: 1208 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
[not found] ` <CAOG=w-v3qjG3zd_WhfFU-OGnsHZEuYvY82eL4GqcdgY6np5bvA@mail.gmail.com>
@ 2014-12-12 17:50 ` Alex Mizrahi
2014-12-13 13:32 ` Gareth Williams
2014-12-15 4:17 ` Peter Todd
0 siblings, 2 replies; 30+ messages in thread
From: Alex Mizrahi @ 2014-12-12 17:50 UTC (permalink / raw)
To: Mark Friedenbach; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1403 bytes --]
> I think what Gareth was getting at was that with client-side validation
> there can be no concept of a soft-fork. And how certain are you that the
> consensus rules will never change?
>
Yes, it is true that you can't do a soft-fork, but you can do a hard-fork.
Using scheduled updates: client simply stops working at a certain block,
and user is required to download an update.
In Bitcoin we can operate with some assurance that hard-forks will almost
> never happen, exactly because extensions are more likely to occur via
> soft-fork mechanisms. In such a case, old non-updated clients will still
> generate a correct view of the ledger state. But this is not so with client
> side validation!
>
You assume that an ability to operate with zero maintenance is very
important, but is this a case?
There was a plenty of critical bugs in bitcoind, and in many cases people
were strongly encouraged to upgrade to a new version.
So, you urge people to keep their clients up-to-date, but at the same time
claim that keeping very old versions is critically important.
How does this make sense? Is this an exercise at double-think?
An alternative to this is to make updates mandatory. You will no longer
need to maintain compatibility with version 0.1 (which is impossible) and
you can also evolve consensus rules over time.
It looks like people make a cargo cult out of Bitcoin's emergent
properties.
[-- Attachment #2: Type: text/html, Size: 1918 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 17:50 ` Alex Mizrahi
@ 2014-12-13 13:32 ` Gareth Williams
2014-12-15 4:52 ` Peter Todd
2014-12-15 4:17 ` Peter Todd
1 sibling, 1 reply; 30+ messages in thread
From: Gareth Williams @ 2014-12-13 13:32 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3998 bytes --]
On 13/12/14 04:04, Alex Mizrahi wrote:
> Well, client-side validation is mathematically secure, while SPV is
> economically secure.
> I.e. it is secure if you make several assumptions about economics of the
> whole thing.
Comparisons with the SPV security of sidechains are fallacious. The
alternative to a proof-of-publication system reliant on client-side
validation is a blockchain. The question of whether the token used on
said blockchain should be two-way-pegged to BTC is completely orthogonal.
(ie. yes, sidechains are "economically secure", in that you're reduced
to balancing economic incentives to avoid peg theft. But sidechains also
give us something unique in return - the ability to innovate without
needing to start new artificial scarcity races. Nothing else can do that.)
<snip>
> You know, The Great Fork of 2013 was resolved through human
> intervention, Bitcoin nodes were not smart enough to detect that
> something is going awry on their own.
I hate to think what the outcome would've been on a proof-of-publication
system. You don't even have a fork. You just have a whole bunch of nodes
who sort-of-mostly agree on a shared history, except where they don't.
Maybe they just disagree on the validity of a single transaction.
They'll slowly diverge over time (as bad transactions are used as input
to other transactions.) You have no reliable way to detect this lapse in
consensus, nor any mechanism to incentivse convergence. Indeed, you have
no consensus mechanism in the first place.
Bitcoin is where it is today because of Satoshi's elegant solution to
exactly such problems. Which some people now appear to be in a hurry to
discard :)
Alex Mizrahi wrote:
> Using scheduled updates: client simply stops working at a certain block,
> and user is required to download an update.
<snip>
> An alternative to this is to make updates mandatory. You will no longer
> need to maintain compatibility with version 0.1 (which is impossible)
> and you can also evolve consensus rules over time.
Peter Todd might disagree with the wisdom of that :) He wrote an
excellent email to this list not long ago warning of the dangers of
centralisation. IIRC one point he made was that scheduled, regular
hardforks were a real threat - if a single entity (eg. the Bitcoin
Foundation) were to become politically established as the coordinator of
such forks, they would have de-facto control over the protocol.
Even in that dark scenario, I would feel a measure of confidence that
past transactions I had received could not be tampered with. The fact
that those transactions happened, and that there was (and is) consensus
they were valid, is publicly documented in the blockchain. I trust any
reasonable person would not accept a client that ignored validated data
in the blockchain as "Bitcoin" any more.
Your proof-of-publication system with mandatory updates is another
matter entirely. No public record of transactions I have received with
that system exists, anywhere. If tomorrow's mandatory update has the
effect of zeroing my account balance (by happening to now interpret one
or more transactions I received, or their inputs, as invalid) then I
have no recourse. I won't find sympathy with the majority of users, who
are unaffected and just accept the update.
In short, what you describe doesn't sound very decentralised :) Do you
want transactions you receive validated by distributed consensus and
burried under PoW, or validated by some guy's mandatory-updating python
script?
(Also worth noting: all such systems are effectively "mandatory
updating" due to the risk of subtle consensus bugs of the type I
described above. Your only assurance that your view of the world is the
same as everyone elses' is that you're running the exact same software.
I played with Counterparty a while ago and quickly learned - the hard
way - to do a 'git pull' before any important operation.)
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 17:50 ` Alex Mizrahi
2014-12-13 13:32 ` Gareth Williams
@ 2014-12-15 4:17 ` Peter Todd
1 sibling, 0 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-15 4:17 UTC (permalink / raw)
To: Alex Mizrahi; +Cc: Bitcoin Dev, Mark Friedenbach
[-- Attachment #1: Type: text/plain, Size: 3130 bytes --]
On Fri, Dec 12, 2014 at 07:50:48PM +0200, Alex Mizrahi wrote:
> > I think what Gareth was getting at was that with client-side validation
> > there can be no concept of a soft-fork. And how certain are you that the
> > consensus rules will never change?
> >
>
> Yes, it is true that you can't do a soft-fork, but you can do a hard-fork.
> Using scheduled updates: client simply stops working at a certain block,
> and user is required to download an update.
You're quite mistaken actually. One of the first things to come out of
my research as Mastercoin's Chief Scientist - indeed after a week on the
job - was how to safely upgrade embedded consensus systems in a
decentralized fashion:
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03890.html
To recap, where valuable scarce tokens are concerned we want to ensure
that an attacker can't use a fork caused by an upgrade to double-spend
tokens. We solve this problem by ensuring that when a token visible to
version V_i is spent in a V_{i+1} client, the token appears spent to
version V_i clients as well. This is easy to accomplish by a "split
transaction" scheme that separates all operations into separate
"increment" and "decrement" operations.
The simplest example of this principle in action is colored coins, which
are certainly an example of an embedded consensus system. Colored coin
implementations naturally ensure that all versions of the system see a
token getting spent the same way - the corresponding txout is spent! So
long as changes to the coloring rules are handled such that only one set
of rules - one version - can apply to a given txout spend we get
anti-doublespend protection.
The second aspect of the problem is the social/political implications of
upgrades - because embedded consensus systems don't outsource trust they
very clearly require the co-operation of the economic majority in an
upgrade. For instance if the community has two competing proposals for
how to upgrade version V1 of Counterparty, V2a and V2b, choosing to move
your tokens to either version becomes a vote with serious economic
consequences. In fact, it's quite possible that a community would choose
to simply fork into two different systems each offering a different set
of features. Equally in the event of such a fork someone can create a
third version, V3, that recombines the two incompatible forks. Again,
anyone who agrees with version V3 can choose to move their tokens to it,
healing the fork.
Arguably this process of handling forks by direct economic voting is
significantly *more* decentralized than Bitcoin's soft-fork mechanism as
adoption of a new version is something all participants in the system
play a part in equally. (as measured by economic stake) Of course, it
will lead to sometimes ugly political battles, but that's simply part of
the cost of having democratic systems.
> It looks like people make a cargo cult out of Bitcoin's emergent
> properties.
+1
--
'peter'[:-1]@petertodd.org
00000000000000000681f4e5c84bc0bf7e6c5db8673eef225da652fbb785a0de
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-13 13:32 ` Gareth Williams
@ 2014-12-15 4:52 ` Peter Todd
2014-12-17 11:55 ` Gareth Williams
0 siblings, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-15 4:52 UTC (permalink / raw)
To: Gareth Williams; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 5228 bytes --]
On Sun, Dec 14, 2014 at 12:32:22AM +1100, Gareth Williams wrote:
> On 13/12/14 04:04, Alex Mizrahi wrote:
> > Well, client-side validation is mathematically secure, while SPV is
> > economically secure.
> > I.e. it is secure if you make several assumptions about economics of the
> > whole thing.
>
> Comparisons with the SPV security of sidechains are fallacious. The
> alternative to a proof-of-publication system reliant on client-side
> validation is a blockchain. The question of whether the token used on
> said blockchain should be two-way-pegged to BTC is completely orthogonal.
>
> (ie. yes, sidechains are "economically secure", in that you're reduced
> to balancing economic incentives to avoid peg theft. But sidechains also
> give us something unique in return - the ability to innovate without
> needing to start new artificial scarcity races. Nothing else can do that.)
I covered this in my original post: 1-way-pegs allow the creation of new
valuable tokens without those tokens being useful for speculation.
To recap, a 1-way-peg allows the conversion of Bitcoins to another token
by provably destroying the Bitcoins, thus capping the maximum possible
value of that token and ensuring the token can-not become an investment.
For owners of these tokens they can convert them back to Bitcoin by
selling them at a discount to buyers who would otherwise be able to
purchase them via provable destruction. A pragmatic implementation may
wish to make obtaining the token via destruction option unattractive
compared to obtaining them through trade by incorporating a time delay
into the destruction process to encourage liquidity. (interestingly a
natural outcome of an announce-commit sacrifice-to-fees scheme)
Of course even without 1-way-pegs there's a much more important issue
with your objection: worrying about creating new artificial scarcity
races while innovating is fundementally a *moralistic* and *regulatory*
concern that has no little if any bearing on whether or not the systems
created are useful and secure. It's also an objection that raises
serious questions about conflicts of interest between giving accurate
and honest technical advice and promoting ways of using Bitcoin that
will drive the price up.
> > You know, The Great Fork of 2013 was resolved through human
> > intervention, Bitcoin nodes were not smart enough to detect that
> > something is going awry on their own.
>
> I hate to think what the outcome would've been on a proof-of-publication
> system. You don't even have a fork. You just have a whole bunch of nodes
> who sort-of-mostly agree on a shared history, except where they don't.
> Maybe they just disagree on the validity of a single transaction.
> They'll slowly diverge over time (as bad transactions are used as input
> to other transactions.) You have no reliable way to detect this lapse in
> consensus, nor any mechanism to incentivse convergence. Indeed, you have
> no consensus mechanism in the first place.
A number of mechanisms for detecting divergence are possible in embedded
consensus systems, some of them even natural outcomes. For instance
transactions can contain a hash of the previous consensus state, thereby
creating an indicator of consensus measured in terms of economic stake.
Extending that idea many anti-censorship proposals are to use such state
hashes as encryption keys - if you are out of consensus you won't even
see the transaction. (and you can't be double-spent either if
implemented correctly; see my other reply to this thread today)
> Bitcoin is where it is today because of Satoshi's elegant solution to
> exactly such problems. Which some people now appear to be in a hurry to
> discard :)
FWIW usually Satoshi's solution is described as a hack, sometimes as an
elegant hack.
> Peter Todd might disagree with the wisdom of that :) He wrote an
> excellent email to this list not long ago warning of the dangers of
> centralisation. IIRC one point he made was that scheduled, regular
> hardforks were a real threat - if a single entity (eg. the Bitcoin
> Foundation) were to become politically established as the coordinator of
> such forks, they would have de-facto control over the protocol.
Indeed I did, which is why I worked out a better way to do upgrades
almost a year ago:
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg06578.html
> (Also worth noting: all such systems are effectively "mandatory
> updating" due to the risk of subtle consensus bugs of the type I
> described above. Your only assurance that your view of the world is the
> same as everyone elses' is that you're running the exact same software.
> I played with Counterparty a while ago and quickly learned - the hard
> way - to do a 'git pull' before any important operation.)
The quality of Counterparty's software engineering has no bearing on
whether or not the underlying idea is a good one; you wouldn't say ring
signatures are an inherently bad idea just because the CryptoNote
implementation of them is atrocious.
--
'peter'[:-1]@petertodd.org
00000000000000000681f4e5c84bc0bf7e6c5db8673eef225da652fbb785a0de
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-12 13:41 ` odinn
2014-12-12 14:17 ` Justus Ranvier
@ 2014-12-15 4:59 ` Peter Todd
2014-12-17 1:16 ` odinn
1 sibling, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-15 4:59 UTC (permalink / raw)
To: odinn; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1101 bytes --]
On Fri, Dec 12, 2014 at 01:41:34PM +0000, odinn wrote:
> Peter... It kind of sounds to me that (as fine of a position paper as
> this is) on _certain_ points, you're falling prey to the "but it's
> inefficient, but it's a scamcoin, but luke-jr told me so" argument...
I prefer to make robust arguments; if I can start with accepting that
95% of what my opponents say is true, yet still end up being correct,
all the better!
> I think the Mastercoin devs are doing fine work and I consider the
> zerocash devs to have developed (in v2, mint and pour) to have
> developed something that will really turn the world on its ear, but
> what do I know? Nothing. Nothing at all.
My personal opinion is that what Mastercoin has started will turn the
world on its ear, but I'd be surprised if the succesful implementations
of the underlying ideas come from that team. But there's nothing
surprising about that - when was the last time you used Netscape
Navigator, let alone NCSA Mosaic?
--
'peter'[:-1]@petertodd.org
00000000000000000681f4e5c84bc0bf7e6c5db8673eef225da652fbb785a0de
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-15 4:59 ` Peter Todd
@ 2014-12-17 1:16 ` odinn
0 siblings, 0 replies; 30+ messages in thread
From: odinn @ 2014-12-17 1:16 UTC (permalink / raw)
To: Peter Todd; +Cc: bitcoin-development
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
bleep bloop
Peter Todd:
> On Fri, Dec 12, 2014 at 01:41:34PM +0000, odinn wrote:
>> Peter... It kind of sounds to me that (as fine of a position
>> paper as this is) on _certain_ points, you're falling prey to the
>> "but it's inefficient, but it's a scamcoin, but luke-jr told me
>> so" argument...
>
> I prefer to make robust arguments; if I can start with accepting
> that 95% of what my opponents say is true, yet still end up being
> correct, all the better!
>
>> I think the Mastercoin devs are doing fine work and I consider
>> the zerocash devs to have developed (in v2, mint and pour) to
>> have developed something that will really turn the world on its
>> ear, but what do I know? Nothing. Nothing at all.
>
> My personal opinion is that what Mastercoin has started will turn
> the world on its ear, but I'd be surprised if the succesful
> implementations of the underlying ideas come from that team. But
> there's nothing surprising about that - when was the last time you
> used Netscape Navigator, let alone NCSA Mosaic?
>
- --
http://abis.io ~
"a protocol concept to enable decentralization
and expansion of a giving economy, and a new social good"
https://keybase.io/odinn
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCgAGBQJUkNluAAoJEGxwq/inSG8CKy0IAJmCUmDbaCx33/km0J2mP7ha
kxX3fxiPpicD8hXa4FXBsrYqj7ZFu0OmFOU/ei0AXMOuu94rQdIp6hon3f5GO73J
WVT2Toqd2GTCXhmddyqtOzZ5mYOyZhlJUYlNjbwTmlk+U2hQbZC1aJ4AKdmjQn5v
9DFkZfqBSsNhcoLCKoVqY3l4qzw0XqeL6fOYkz2H9AssWdcUV9JB5C0wm8rI70AX
qcxABgrKDwhThWgHyHGZXHLCvRRpMUFFVbzO67BPZA2R+gXYtOAVDozl7jdx7PLl
x3nyzZK3pX1bqcT2T5fD8wQtu4yJ3RCBVWzHfrA5MF6q4Yh6DEh7DnO8ccOnPlk=
=1os7
-----END PGP SIGNATURE-----
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-15 4:52 ` Peter Todd
@ 2014-12-17 11:55 ` Gareth Williams
2014-12-21 6:12 ` Peter Todd
0 siblings, 1 reply; 30+ messages in thread
From: Gareth Williams @ 2014-12-17 11:55 UTC (permalink / raw)
To: Bitcoin Dev
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
^ permalink raw reply [flat|nested] 30+ messages in thread
* [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-12 9:05 [Bitcoin-development] Setting the record straight on Proof-of-Publication Peter Todd
2014-12-12 12:25 ` Gareth Williams
2014-12-12 13:41 ` odinn
@ 2014-12-20 14:48 ` Peter Todd
[not found] ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
` (4 more replies)
2 siblings, 5 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-20 14:48 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 9383 bytes --]
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/
--
'peter'[:-1]@petertodd.org
000000000000000001eeaba4cdadaf5b8338cb1b2ae0cf969de77437dd83faac
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
[not found] ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
@ 2014-12-21 5:52 ` Peter Todd
[not found] ` <CAOG=w-tZke--6OsqNjJhE9SOdCwdZYZM8iz1VBTFziegt9UZWw@mail.gmail.com>
2014-12-21 11:25 ` Jorge Timón
0 siblings, 2 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-21 5:52 UTC (permalink / raw)
To: Mark Friedenbach; +Cc: Bitcoin Development
[-- Attachment #1: Type: text/plain, Size: 1353 bytes --]
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?
--
'peter'[:-1]@petertodd.org
000000000000000017d70ee98f4cee509d95c4f31d5b998bae6deb09df1088fc
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] Setting the record straight on Proof-of-Publication
2014-12-17 11:55 ` Gareth Williams
@ 2014-12-21 6:12 ` Peter Todd
0 siblings, 0 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-21 6:12 UTC (permalink / raw)
To: Gareth Williams; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 4019 bytes --]
On Wed, Dec 17, 2014 at 10:55:28PM +1100, Gareth Williams wrote:
> > I covered this in my original post: 1-way-pegs allow the creation of new
> > valuable tokens without those tokens being useful for speculation.
>
> I stand corrected. A permanent 1-way-peg is sufficient to preserve
> scarcity; "nothing else can do that" WRT 2-way-pegs was overreaching.
Yup.
> I still don't see what "2-way-peg vs. 1-way-peg" has to do with
> "embedded consensus vs. blockchain consensus" though, and feel it
> disingenious to conflate them.
1-way-pegs don't require the Bitcoin protocol to change; 2-way-pegs do.
> Blockchain consensus (eg. sidechains) can utilise either mechanism,
> 1-way-peg or 2-way-peg. Arguments in favour of 1-way-peg are
> interesting, but they're ultimatley just arguments in favour of one
> type of sidechain over another.
No, they're in favor of systems that are client-side validatable vs.
systems that either allow anyone with sufficient hashing power to steal
coins *or* require "moon-math" that isn't yet available to production
systems.
> IMO the question of whether scarcity can be preserved while enabling
> innovation bears heavily on the liklihood of longterm viability of
> said innovations - and perhaps of Bitcoin itself.
>
> FWIW I'll happily declare that I hold a modest amount of BTC and have
> an interest in the price appreciating. I'm sure you'll admit you're
> hardly an impartial party in this discussion yourself Peter :) But it
> really shouldn't matter. I'm not here today to make it, but I think
> the argument for preservation of scarcity stands quite well on its own
> merits - as rightly it should, regardless of anybody's interests.
But again, all these discussions about scarcity are fundementally
*moral* arguments that have no bearing on what's actually the most
appropriate solution for an *individual* problem.
In a decentralized system filled with anonymous actors telling people
"stop doing that! it's bad!" on reddit has pretty severe limitations in
trying to convince people to act against their own best interests.
> > The quality of Counterparty's software engineering has no bearing on
> > whether or not the underlying idea is a good one; you wouldn't say ring
> > signatures are an inherently bad idea just because the CryptoNote
> > implementation of them is atrocious.
>
> Very interesting. I admit I hadn't come across these ideas before; I
> really must search the archive before posting :) They certainly offer
> a measure of robustness over the naive approach. I'm not sure they
> address my primary concerns however, WRT how consensus is demonstrated
> and incentivised.
I think you think consensus in Bitcoin is more "magical" than it really
is; Bitcoin is just code running on computers; consensus isn't really
incentivised at the protocol level beyond "screw it up and you'll lose
money"
Embedded consensus systems are no different: screw up consensus and
you'll lose money in a variety of ways.
> The obvious "embedded consensus" answer of "wait until N other
> transactions have occurred that include a hash of system state that
> includes your transaction" doesn't provide me with any confidence; it
> could be simulated with a Sybil attack.
No it can't - the transactions are in the blockchain so the sybil attack
has to attack the host system as well.
In any case, keep in mind all of this is in the context of tradeoffs:
for a different and sometimes more fragile consensus mechanism embedded
consensus gets immunity to attack by miners. You're trading off one type
of fragility for another - I'd much rather take the "one-time" fragility
inherent in having to write really solid software than the ongoing
fragility of always being vulnerable to miners.
Notably this is the exact same tradeoff taken elsewhere by the majority
of the crypto world.
--
'peter'[:-1]@petertodd.org
000000000000000017d70ee98f4cee509d95c4f31d5b998bae6deb09df1088fc
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
[not found] ` <CAOG=w-tZke--6OsqNjJhE9SOdCwdZYZM8iz1VBTFziegt9UZWw@mail.gmail.com>
@ 2014-12-21 7:01 ` Peter Todd
[not found] ` <CAOG=w-s1_VXJAKxBpMOK=B50qnHjxSe4J=vwwSfFPRz0_Cb9rA@mail.gmail.com>
0 siblings, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-21 7:01 UTC (permalink / raw)
To: Mark Friedenbach; +Cc: Bitcoin Development
[-- Attachment #1: Type: text/plain, Size: 1549 bytes --]
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
--
'peter'[:-1]@petertodd.org
000000000000000000c879729eae178096b092248706a407ec1b18eb62a792e9
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
[not found] ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
@ 2014-12-21 10:01 ` Adam Back
2014-12-21 15:29 ` Peter Todd
2014-12-21 13:49 ` paul snow
` (2 subsequent siblings)
4 siblings, 1 reply; 30+ messages in thread
From: Adam Back @ 2014-12-21 10:01 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Dev
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
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 5:52 ` Peter Todd
[not found] ` <CAOG=w-tZke--6OsqNjJhE9SOdCwdZYZM8iz1VBTFziegt9UZWw@mail.gmail.com>
@ 2014-12-21 11:25 ` Jorge Timón
2014-12-21 16:07 ` Peter Todd
1 sibling, 1 reply; 30+ messages in thread
From: Jorge Timón @ 2014-12-21 11:25 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Development, Mark Friedenbach
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.
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
[not found] ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
2014-12-21 10:01 ` Adam Back
@ 2014-12-21 13:49 ` paul snow
2014-12-21 15:22 ` Peter Todd
2014-12-22 0:11 ` Peter Todd
2014-12-22 20:05 ` Adam Back
4 siblings, 1 reply; 30+ messages in thread
From: paul snow @ 2014-12-21 13:49 UTC (permalink / raw)
To: Peter Todd; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 2062 bytes --]
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.
[-- Attachment #2: Type: text/html, Size: 2256 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 13:49 ` paul snow
@ 2014-12-21 15:22 ` Peter Todd
2014-12-21 15:41 ` paul snow
0 siblings, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-21 15:22 UTC (permalink / raw)
To: paul snow; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3135 bytes --]
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
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 10:01 ` Adam Back
@ 2014-12-21 15:29 ` Peter Todd
0 siblings, 0 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-21 15:29 UTC (permalink / raw)
To: Adam Back; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2078 bytes --]
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.
--
'peter'[:-1]@petertodd.org
000000000000000012f5511833a1304a72a754df8afef26f5712438bcc40826b
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
[not found] ` <CAOG=w-s1_VXJAKxBpMOK=B50qnHjxSe4J=vwwSfFPRz0_Cb9rA@mail.gmail.com>
@ 2014-12-21 15:32 ` Peter Todd
0 siblings, 0 replies; 30+ messages in thread
From: Peter Todd @ 2014-12-21 15:32 UTC (permalink / raw)
To: Mark Friedenbach; +Cc: Bitcoin Development
[-- Attachment #1: Type: text/plain, Size: 1427 bytes --]
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.
--
'peter'[:-1]@petertodd.org
000000000000000012f5511833a1304a72a754df8afef26f5712438bcc40826b
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 15:22 ` Peter Todd
@ 2014-12-21 15:41 ` paul snow
0 siblings, 0 replies; 30+ messages in thread
From: paul snow @ 2014-12-21 15:41 UTC (permalink / raw)
To: Peter Todd; +Cc: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3950 bytes --]
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
>
[-- Attachment #2: Type: text/html, Size: 4617 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 11:25 ` Jorge Timón
@ 2014-12-21 16:07 ` Peter Todd
2014-12-21 19:39 ` Jorge Timón
0 siblings, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-21 16:07 UTC (permalink / raw)
To: Jorge Timón; +Cc: Bitcoin Development, Mark Friedenbach
[-- Attachment #1: Type: text/plain, Size: 2953 bytes --]
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.
--
'peter'[:-1]@petertodd.org
000000000000000002661192e72bdc83e6c8101371520159531301aa1437cc2c
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-21 16:07 ` Peter Todd
@ 2014-12-21 19:39 ` Jorge Timón
0 siblings, 0 replies; 30+ messages in thread
From: Jorge Timón @ 2014-12-21 19:39 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Development, Mark Friedenbach
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
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
` (2 preceding siblings ...)
2014-12-21 13:49 ` paul snow
@ 2014-12-22 0:11 ` Peter Todd
2015-01-06 11:03 ` joliver
2014-12-22 20:05 ` Adam Back
4 siblings, 1 reply; 30+ messages in thread
From: Peter Todd @ 2014-12-22 0:11 UTC (permalink / raw)
To: bitcoin-development; +Cc: Andrew Miller
[-- Attachment #1: Type: text/plain, Size: 2832 bytes --]
On Sat, Dec 20, 2014 at 09:48:01AM -0500, Peter Todd wrote:
Andrew Miller asked me to publish the following to the mailing list on his
behalf: (https://twitter.com/socrates1024/status/546819355565391872)
One of the main points in this note is that you can use a
"proof-of-publication" system to implement an "anti-replay" system.
However this isn't true - at least not given the description of
proof-of-(non)-publication in 2) and the definition of "anti-replay"
given here.
In 2), proof-of-*non*-publication allows you to prove that *some
specific message* has never been published. You can imagine having a
function ProveNotPublished(m), which proves "message m was not
published."
However, the anti-replay mechanism is about proving that *no* message
satisfying some property has been published. Hence
VerifyAntiReplaySig(m, p, s) checks that "for all possible messages m'
(distinct from m), AntiReplaySign(m', p) has not been called."
This isn't *just* splitting hairs, this distinction is actually
relevant for analyzing several cryptocurrency designs. You can imagine
extending the definition of proof-of-(non)-publication to take in some
predicate P, so that you can prove "no message m such that P(m) holds
has ever been published." However, to do this efficiently requires
anticipating some classes of P and building some appropriate indices.
- As a baseline, as long as you have the whole blockchain available,
you can scan through the entire blockchain and evaluate P for every
transaction, but this is pretty inefficient.
- Other tradeoffs are available if you are willing to trust some
(quora of) servers to maintain indices for you
- Bitcoin's UTXO set effectively supports a predicate for each txout,
where P(x) = "x is a valid tranasction that spends <txout>"
- Ethereum contracts, in a sense, allow for general purpose contracts
to 'build-your-own" index. On the other hand its key-value store
doesn't support range queries, so it's not necessarily "universal" or
as expressive as SQL, for example.
But the point isn't to argue about design choices and tradeoffs in
this thread. The main point I want to make is:
*Indexes and Validation Matter!*
The classic "proof-of-publication" system is to embed opaque data (as
far as bitcoin miners are concerned) in transactions using OP_RETURN.
A significance of establishing "proof-of-publication" as a universal
underlying primitive is that this OP_RETURN trick is then sufficient
for anything you might want. But part of what Bitcoin provides is
indexing and validation/exclusion, and this is important for
supporting efficient anti-replay proofs. Proof-of-(non)-publication
alone isn't sufficient for this.
--
'peter'[:-1]@petertodd.org
00000000000000000a7b40becd0babbd64ec49b8b34823fb4f4b081c95188b66
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
` (3 preceding siblings ...)
2014-12-22 0:11 ` Peter Todd
@ 2014-12-22 20:05 ` Adam Back
4 siblings, 0 replies; 30+ messages in thread
From: Adam Back @ 2014-12-22 20:05 UTC (permalink / raw)
To: Peter Todd; +Cc: Bitcoin Dev
(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.
^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
2014-12-22 0:11 ` Peter Todd
@ 2015-01-06 11:03 ` joliver
0 siblings, 0 replies; 30+ messages in thread
From: joliver @ 2015-01-06 11:03 UTC (permalink / raw)
To: bitcoin-development
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?
^ permalink raw reply [flat|nested] 30+ messages in thread
* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-17 22:20 paul snow
0 siblings, 0 replies; 30+ messages in thread
From: paul snow @ 2014-12-17 22:20 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3831 bytes --]
[[Since I sent this while the List Server was down, it didn't actually go
to everyone. Forgive me if you ended up with two copies.]]
Peter provides an excellent summary of Proof of Publication, which starts
with defining it as being composed of a solution to the double spend
problem. He requires Proof-of-receipt (proof every member of p in audience
P has received a message m), Proof-of-non-publication (proof a message m
has not been published to an audience P), and Proof-of-membership (proof
some q is a member of P).
He goes on to state (curiously) that Factom cannot provide Proof of
Publication.
Proof of Membership
================
Let's first satisfy the easier proofs. A Factom user can know they are a
member of the Factom audience if they have access to the Bitcoin
Blockchain, knowledge of Factom's first anchor (Merkle root stored in the
blockchain) and the Factom network for distributing Factom's structures.
They can pretty much know that they are in the Audience.
Proof of Receipt
============
Proof of receipt is also pretty easy for the Factom user. User submit
entries, and Factom publishes a Merkle Root to the Bitcoin Blockchain. The
Merkle proof to the entry proves receipt. To get the Merkle proof requires
access to Factom structures, which all in the audience have access to by
definition. But the proof itself only requires the blockchain.
At this point the user can have a Merkle proof of their entry rooted in the
blockchain.
Proof of non-publication
==================
Last, can the Factom user have a Proof-of-non-publication? Well,
absolutely. The Factom state limits the public keys that can be used to
write the anchors in the blockchain. Transactions in Bitcoin that are not
signed with those public keys are discounted out of hand. Just like
publishing in Mad Magazine does not qualify if publishing a notice in the
New York Times is the standard.
The complaint Peter has that the user cannot see all the "child chains"
(what we call Factom Chains) is invalid. The user can absolutely see all
the Directory Blocks (which documents all Factom Chains) if they have
access to Factom. But the user doesn't need to prove publication in all
chains. Some of those chains are like Car Magazines, Math Textbooks,
Toaster manuals, etc. Without restricting the domain of publication there
is no proof of the negative. The negative must be proved in the standard of
publication, i.e. the user's chain. And the user can in fact know their
chain, and can enumerate their chain, without regard to most of the other
data in Factom.
Peter seems to be operating under the assumption that the audience for a
Factom user must necessarily be limited to information found in the
blockchain. Yet the user certainly should have access to Factom if they
are a Factom user. Factom then is no different from the New York Times,
and the trust in Factom is less. As Peter says himself, he has to trust the
New York Times doesn't publish multiple versions of the same issue. The
user of the New York Times would have no way to know if there were other
versions of an issue outside of looking at all New York Times issues ever
published.
Factom on the other hand documents their "issues" on the blockchain. Any
fork in publication is obvious as it would require different Bitcoin
addresses to be used, and the blocks would have to have validating
signatures of majorities of all the Factom servers. As long as a fork in
Factom can be clearly identified, and no fork exists, proof of the negative
is assured. And upon a fork, one must assume the users will specify which
fork should be used.
Proof of publication does not require a system that cannot fork, since no
such non-trivial system exists. What is required is that forks can be
detected, and that a path can be chosen to move forward.
[-- Attachment #2: Type: text/html, Size: 5373 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
* [Bitcoin-development] Setting the record straight on Proof-of-Publication
@ 2014-12-16 20:28 paul snow
0 siblings, 0 replies; 30+ messages in thread
From: paul snow @ 2014-12-16 20:28 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 3668 bytes --]
Peter provides an excellent summary of Proof of Publication, which starts
with defining it as being composed of a solution to the double spend
problem. He requires Proof-of-receipt (proof every member of p in audience
P has received a message m), Proof-of-non-publication (proof a message m
has not been published to an audience P), and Proof-of-membership (proof
some q is a member of P).
He goes on to state (curiously) that Factom cannot provide Proof of
Publication.
Proof of Audience
=============
Let's first satisfy the easier proofs. A Factom user can know they are in
the Factom audience if they have access to the Bitcoin Blockchain,
knowledge of Factom's first anchor (Merkle root stored in the blockchain)
and the Factom network for distributing Factom's structures. They can
pretty much know that they are in the Audience.
Proof of Receipt
============
Proof of receipt is also pretty easy for the Factom user. User submit
entries, and Factom publishes a Merkle Root to the Bitcoin Blockchain. The
Merkle proof to the entry proves receipt. To get the Merkle proof requires
access to Factom structures, which all in the audience have access to by
definition. But the proof itself only requires the blockchain.
At this point the user can have a Merkle proof of their entry rooted in the
blockchain.
Proof of non-publication
==================
Last, can the Factom user have a Proof-of-non-publication. Well,
absolutely. The Factom state limits the public keys that can be used to
write the anchors in the blockchain. Entries that are not written with
those public keys are discounted out of hand. Just like publishing in Mad
Magazine does not qualify if publishing a notice in the New York Times is
the standard.
The complaint Peter has that the user cannot see all the "child chains"
(what we call Factom Chains) is invalid. The user can absolutely see all
the Directory Blocks (which documents all Factom Chains) if they have
access to Factom. But the user doesn't need to prove publication in all
chains. Some of those chains are like Car Magazines, Math Textbooks,
Toaster manuals, etc. Without restricting the domain of publication there
is no proof of the negative. The negative must be proved in the standard of
publication, i.e. the user's chain. And the user can in fact know their
chain, and can enumerate their chain, without regard to most of the other
data in Factom.
Peter seems to be operating under the assumption that the audience for a
Factom user must necessarily be limited to information found in the
blockchain. Yet the user certainly should have access to Factom if they
are a Factom user. Factom then is no different from the New York Times,
and the trust in Factom is less. As Peter says himself, he has to trust the
New York Times doesn't publish multiple versions of the same issue. The
user of the New York Times would have no way to know if there were other
versions of an issue outside of looking at all New York Times issues ever
published.
Factom on the other hand documents their "issues" on the blockchain. Any
fork in publication is obvious as it would require different Bitcoin
addresses to be used, and the blocks would have to have validating
signatures of majorities of all the Factom servers. As long as a fork in
Factom can be clearly identified, and no fork exists, proof of the negative
is assured. And upon a fork, one must assume the users will specify which
fork should be used.
Proof of publication does not require a system that cannot fork, since no
such non-trivial system exists. What is required is that forks can be
detected, and that a path can be chosen to move forward.
[-- Attachment #2: Type: text/html, Size: 4077 bytes --]
^ permalink raw reply [flat|nested] 30+ messages in thread
end of thread, other threads:[~2015-01-06 11:03 UTC | newest]
Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-12-12 9:05 [Bitcoin-development] Setting the record straight on Proof-of-Publication Peter Todd
2014-12-12 12:25 ` Gareth Williams
2014-12-12 17:04 ` Alex Mizrahi
[not found] ` <CAOG=w-v3qjG3zd_WhfFU-OGnsHZEuYvY82eL4GqcdgY6np5bvA@mail.gmail.com>
2014-12-12 17:50 ` Alex Mizrahi
2014-12-13 13:32 ` Gareth Williams
2014-12-15 4:52 ` Peter Todd
2014-12-17 11:55 ` Gareth Williams
2014-12-21 6:12 ` Peter Todd
2014-12-15 4:17 ` Peter Todd
2014-12-12 13:41 ` odinn
2014-12-12 14:17 ` Justus Ranvier
2014-12-15 4:59 ` Peter Todd
2014-12-17 1:16 ` odinn
2014-12-20 14:48 ` [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles Peter Todd
[not found] ` <CAOG=w-vrHPY1aCNndmoW9QyCh9XnWyv8uZn2PyjZ6rNg2MoSSw@mail.gmail.com>
2014-12-21 5:52 ` Peter Todd
[not found] ` <CAOG=w-tZke--6OsqNjJhE9SOdCwdZYZM8iz1VBTFziegt9UZWw@mail.gmail.com>
2014-12-21 7:01 ` Peter Todd
[not found] ` <CAOG=w-s1_VXJAKxBpMOK=B50qnHjxSe4J=vwwSfFPRz0_Cb9rA@mail.gmail.com>
2014-12-21 15:32 ` Peter Todd
2014-12-21 11:25 ` Jorge Timón
2014-12-21 16:07 ` Peter Todd
2014-12-21 19:39 ` Jorge Timón
2014-12-21 10:01 ` Adam Back
2014-12-21 15:29 ` Peter Todd
2014-12-21 13:49 ` paul snow
2014-12-21 15:22 ` Peter Todd
2014-12-21 15:41 ` paul snow
2014-12-22 0:11 ` Peter Todd
2015-01-06 11:03 ` joliver
2014-12-22 20:05 ` Adam Back
2014-12-16 20:28 [Bitcoin-development] Setting the record straight on Proof-of-Publication paul snow
2014-12-17 22:20 paul snow
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox