Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On 20 December 2014 at 14:48, Peter Todd p...@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 -- 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=164703151iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On Dec 20, 2014 8:49 AM, Peter Todd p...@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. -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On Sun, Dec 21, 2014 at 07:49:17AM -0600, paul snow wrote: On Dec 20, 2014 8:49 AM, Peter Todd p...@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 1b728df6414af5ef95388557f1c3e5d29c569d7636b93681 signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On Sun, Dec 21, 2014 at 10:01:37AM +, Adam Back wrote: On 20 December 2014 at 14:48, Peter Todd p...@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 12f5511833a1304a72a754df8afef26f5712438bcc40826b signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On Sun, Dec 21, 2014 at 03:11:32PM +0800, Mark Friedenbach wrote: On Sun, Dec 21, 2014 at 3:01 PM, Peter Todd p...@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 12f5511833a1304a72a754df8afef26f5712438bcc40826b signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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 p...@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 p...@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 1b728df6414af5ef95388557f1c3e5d29c569d7636b93681 -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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 02661192e72bdc83e6c8101371520159531301aa1437cc2c signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On Sun, Dec 21, 2014 at 5:07 PM, Peter Todd p...@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 02661192e72bdc83e6c8101371520159531301aa1437cc2c -- 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
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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 0a7b40becd0babbd64ec49b8b34823fb4f4b081c95188b66 signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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 00c879729eae178096b092248706a407ec1b18eb62a792e9 signature.asc Description: Digital signature -- 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=164703151iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
