Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
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? -- Dive into the World of Parallel Programming! The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net ___ 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
(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-a
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 " - 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=164703151&iu=/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 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 co
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=164703151&iu=/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" wrote: > On Sun, Dec 21, 2014 at 07:49:17AM -0600, paul snow wrote: > > On Dec 20, 2014 8:49 AM, "Peter Todd" 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=164703151&iu=/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 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=164703151&iu=/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 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=164703151&iu=/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" 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=164703151&iu=/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" 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=164703151&iu=/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
st On Sun, Dec 21, 2014 at 6:52 AM, Peter Todd 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. -- 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
Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles
On 20 December 2014 at 14:48, Peter Todd 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=164703151&iu=/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 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=164703151&iu=/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 11:57:51AM +0800, Mark Friedenbach wrote: > On Sat, Dec 20, 2014 at 10:48 PM, Peter Todd 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 17d70ee98f4cee509d95c4f31d5b998bae6deb09df1088fc 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=164703151&iu=/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 onc
