No, go review it again. Thats not whats being described here. The PRNG has to have a special tree structure in order to make Alice's cost in producing an exact match query logarithmic in the tree size. You can trade off additional computation for space, but because the function is random this isn't terribly effective.

Bitcoin is first and foremost an autonomous zero trust system. All Bitcoin nodes, not just miners verify all transactions and blocks and enforce the rules. This is part of what creates the incentives for miners to behave honestly.

Mining will continue forever (or at least as long as Bitcoin does).  The award of the initial bitcoins (subsidy) is only a small part of mining. Mining's primary purpose is to establish a decisive consensus on the ordering of transactions— the one decision the network must make which cannot be decided purely in an autonomous manner.  As the subsidy goes away mining will be supported by transaction fees.

The autonomous zero trustness of Bitcoin ensures that people couldn't have violated the rules anywhere in Bitcoin's past. When it introduce a new node to the network it obtains the complete history and validates it as though it were watching all along. Along the way it produces a summary which is uses to efficiently validate new blocks and transactions as they come in.  Because of this, auditing the source code is sufficient to be absolutely confident that the systems properties are as promised.

Taking the idea further— something which couldn't be done in the current othercoin design as I understand it but perhaps interesting for the future (e.g. if othercoin used 2of2 instead of additive homomorphism):

It would be interesting that when you load a coin into an othercoin if the device couldn't help you establish an nlocktimed refund that releases the coins back to you at some far future date. E.g. the device was willing sign a refund but only with the locktime established far out after the load time but less than the current refund time if there is one.  The existence of this refund would, of course, be communicated with the coin so you wouldn't accept a coin which was about to return to sender.

This would provide an incentive to periodically refresh your othercoins, as while doing so you could reset the refund clock.

The advantage of this is that the coins aren't lost if the hardware is lost, instead they eventually return to the last party to have collected a refund transaction from them.  It would be a way of achieving backup for these coins which doesn't compromise their non-doublespendability.

Well, keep your enthusiasm bounded: This is strictly less secure than Bitcoin itself. If someone compromises a single card then the whole infrastructure is busted: Everyone becomes potentially vulnerable to double spending by an evil device which has seen the private keys they're holding, so they'd have to go redeem their coins on the network and pay them into new, hopefully more secure, cards.

It's a absolutely fantastic trade-off though: the reduction in security comes with privacy and convenience improvements. Even online, its useful for allowing instant transactions.

I'll make the idea even stronger:  Once you support in-field loading, it should be possible to "refresh" the coins on the card by spending them and doing a new in-field load.  If you successfully do that the coins you have refreshed are protected from double-spending by earlier holders.

Periodic refreshing would prevent a situation where someone runs a "spy card" that remembers a lot of private keys and does a lot of transactions and then suddenly one day captures up all the non-redeemed coins on the keys they've seen.

Yep. Privacy requires new keys, but in general any protocol with a blind refund must always use a new key.

Petertodd proposed above that the final releases should be accomplished by handing over the keys, which also is another reason why you want to use fresh keys.

One possibility though is making so that the authority doesn't have to fill it.   Card generates a private key, and then won't let you do anything with it until you provide the card with SPV proof (e.g. txn, fragment and 200 blocks of some suitable minimum difficulty) that the private key it generated has been paid.

Right, so what you need to do is have a snapshot of pre-existing coins that are in circulation in this system. Today you could accomplish that with just a copy of the utxo set. (e.g. only about 250 mbytes of data)

Another alternative, if the device knows what the address of its private key is... is that it can give you SPV fragments to show that key being paid... and then you only have to have (possibly somewhat old) block headers, to verify the amount.

There is some online preparation, but the actual payments can be offline.

A third party certificate authority which certifies the cards as being ones that will respect the anti-doublespending requirement.

Otherwise I just load one of these keys onto a fake card which double spends it. The tamper-resistance only matters if you actually can tell that you're talking to one of these tamper resistant cards.

Presumably the cards must present a certificate signed by a trusted (by the card) authority.

I suppose one way to go about the interface would be to first add some infrastructure for queued/delayed transactions. E.g. you could tell it {I want to pay 1AAA, with a timeout of N seconds} and it queues it and returns just a locally significant handle instead of a TXID (and in the GUI shows it in some queued transactions tab). This could obviously be used purely locally to merge multiple outputs of your own into a sendmany.  With that in place, I think casual coinjoins (where you're not trying super hard to match values, and only making them where you would have otherwise made a payment) would have no further interface impact except a switch to enable/disable using them to process queued transactions.

Hah. I don't _generally_ consider that a flaw. Selectable audibility is useful, so long as its the participants that control it.  What is a flaw here is that Carol can tell you about Alice.   In CJ, even a cryptographically blinded one, if setup right, you could also keep logs that enable you to prove to others how you transacted... but no one but you has that power. Doing so enables things like transparent business records— but ones which are only transparent to your investors, not your competition.

With privacy I generally want people to have the freedom to chose to not be private, but only if they can choose when and to whom to not be private with respect to. There are cases where you don't want this to be so— e.g. secret ballot elections need to have no way to opt out of privacy in order to defeat vote buying, so techniques need to exist for that so long as power imbalances between people can exist... but on the whole being able to selectively opt out is worth a little coercion risk for most applications.

So, does this make you happy?

I still don't agree that it's quite the amount of qualitative difference you were drawing, but considering that the alternative will potentially gain regular escrow users in their anonymity set, perhaps its more interesting to you.

Motivation:
Alice would like to pay Bob, but doesn't want the whole world (or even Bob) tracing her transactions.  Carol offers to receive Alice's coin and pay Bob with unconnected coin, but none of these parties trust each other— and Carol being able to steal coins makes Carol into a systemic risk, since the need for trust means that there can't be many Carols and Carol could be earning income on the side spying on Alices, or could get robbed, etc.

Oh, and they don't want to invoke novel cryptography or change the Bitcoin protocol.

Here I present a protocol where Alice can pay Bob by way of Carol where Carol can not rob them. The protocol requires four published transactions, but the transactions look like regular 2 of 2 escrow transactions (two escrow payments, two escrow releases) in the common case where everyone is honest. If Alice or Carol try to renege on their part of the protocol, it either cleanly unwinds or additional transactions are published to push through the transaction but without privacy.

A key concept behind this protocol is understanding that transactions can be protected by knowledge of the preimage of a hash.  E.g., you can write a transaction with a value HX specified in it, where to redeem the transaction the redeemer must provide some X such that Hash(X) = HX.   An example scriptPubKey would be "OP_RIPEMD160 PUSH{0xDEADBEEF} OP_EQUALVERIFY  PUSH{PUBKEY} CHECKSIGVERIFY"; to spend this coin the signature would need to end with a push of whatever value hashes to 0xDEADBEEF.

We form hashlocked transactions in the protocol proposed here, but they're not actually used or announced unless someone tries to cheat.

The general idea is that Alice<>Carol form a 2of2 escrow with Alice's coins,  and Carol<>Bob form a 2of2 escrow with Carol's coins. These escrows have a layer of precomputed time-out redemptions in case any of the parties vanish (Phase zero).  Then they setup a set of mutually signed escrow redeeming transactions which share a common hash-lock so that both of them can be redeemed if one is, but they do not announce them (Phase one).  By doing that, Carol can be confident that if Bob gets paid that Carol will also get paid.  Once Carol is confident that she can't get cheated, she releases her escrow to Bob, and then Alice releases her escrow to Carol (Phase two).

The result is a somewhat complicated protocol simply because it has many stages. Because of this it's explained in detail in the protocol diagram below.

History:
In "Idea for a mixer that can't run with your coins" Murphant proposed increasing financial privacy by performing pairs of transactions which were publicly unlinked if everyone was honest, but if someone tried cheating the funds could be redeemed by exposing the linkage. His proposed protocol would have resulted in unusual-looking transactions and, unfortunately, can't work without some pretty strong enhancements to Script—it would need to be able to verify SPV proofs embedded in transactions. Similar ideas without the SPV proof have been proposed from time to time, but they have extreme holdup/extortion risk.

In P2PTradeX Sergio had proposed a remarkably similar protocol using a SPV proof for doing trades between distinct blockchains. In that thread I proposed a transformation of the protocol that allowed most of the security but worked with Script today by using hash-locking to bind otherwise independent transactions and wondered if the same transformation could be applied to what Murphant was proposing.

My first attempt failed because of disabled OP codes—I wanted to use OP_ADD to blind the hash-locking so that in the common no-cheating case the hash linkage would be hidden, but OP_ADD only works for small integers and the suitable opcodes are disabled. In #bitcoin-wizards, Gavin noticed my mistake and Peter Todd rescued the protocol by pointing out that the hash-locking part could be made hidden by simply never announcing it. This greatly enhanced the protocol because it resulted in all of the transactions in the common case looking like plain escrow usage, plus it made it actually work in an unmodified Bitcoin network. Jcorgan suggested the name.

CoinSwap protocol:
In the protocol all parties are assumed to have private communications channels.

Phase 0. Sets up the escrows and their timeout refunds.
Phase 1. Makes it so that if Bob gets paid there is no way for Carol to fail to get paid.
Phase 2. Just releases the escrows directly because everyone is happy that cheating isn't possible.

  Alice                        Carol                        Bob
  =====================================================================================
0.Computes TX_0: 2of2{A,C}    |Computes TX_1: 2of2{C,B}    |                           \
1.Send TX_0 TXID ------------>                             |                           |
2.                            |Send TX_1 TXID ------------>                            |
3.                            |Computes TX_0 locked refund |Computes TX_1 locked refund|  
4.               <------------ Send TX_0_refund            |                           | Phase 0
5.                            |               <------------ Send TX_1_refund.          |
6.Announces TX_0 to network   |Announces TX_1 to network   |                           |
7.                            |                            |                           |
8.******    Network confirms TX_0: Alice pays according to 2 of {Alice, Carol}   ******|
9.******     Network confirms TX_1: Carol pays according to 2 of {Carol, Bob}    ******/
A.                            |                            |Selects secret value X     \
B.                            |                            |Computes HX = H(X)         |
C.                            |               <------------ Send HX                    |
D.               <----------------------------------------- Send HX                    |
E.Computes TX_2: TX_0>Carol+X |                            |                           | Phase 1
F.Send TX_2     ------------>                              |                           |
G.                            | Computes TX_3: TX_1>Bob+X  |                           |
H.                            | Send TX_3     ------------>                            |
I.                            |               <------------ Send X                     /
J.                            | Computes TX_4: TX_1>Bob    |                           \
K.                            | Send TX_4     ------------>                            |
L.                            |                            |Signs and announces TX_4   |
M.******       Network confirms TX_4: Carol pays Bob via 2 of {Carol, Bob}       ******|
N.Computes TX_5: TX_0>Carol   |                            |                           | Phase 3
O.Send TX_5      ------------>                             |                           |
P.                            |Signs and announces TX_5    |                           |
Q.******     Network confirms TX_5: Alice pays Carol via 2 of {Alice, Carol}     ******/
  =====================================================================================


Note that Alice could also pay the role of Bob, so that Bob doesn't have to take part in the protocol. She could then send on the freshly disconnected coins directly to Bob in the final release.

Also note that care related to mutability is required for the refunds until transaction mutability is solved.

Another key point is that Carol also receives unlinked coins (from Alice), and so in a P2P network a party could equally play the role of Alice or Carol, taking on whichever position was required.

TX_0_refund must have a further future locktime than TX_1_refund. Otherwise Bob can delay step (I.) in the protocol until the refunds become valid and then announce TX_3 while Alice announces TX_0_refund in order to try to cause Alice to get refunded while Bob still gets paid.

Comparison to CoinJoin:
There are a number of comparative advantages and disadvantages between CoinSwap and CoinJoin.

CoinJoin transactions are efficient—when people combine they can even save a little space over a common transaction. By contrast a CoinSwap requires a minimum of four transactions, although two CoinSwaps could effectively be performed at once. This means that CoinJoin is something wallets could reasonably do opportunistically on many transactions while CoinSwap would need to be some kind of periodic process.

CoinJoin's anonymity set is equal to the number of participants in a transaction (or a cascade of transactions). CoinSwap's anonymity set is all CoinSwaps going on at the same time, even if the users don't interact with each other, and all 2of2 secured wallet transactions going on at that time.

CoinSwap transactions look like regular 2of2 escrow transactions. If 2of2 escrows become common, then CoinSwap transactions may be less identifiable than large CoinJoin transactions with a bunch of equally-sized outputs, and thus more censorship-resistant.

To achieve privacy a CoinJoin transaction must have many participants. This somewhat complicates software design (basic state machine handling, dealing with DOS attacks, etc). If Alice plays the role of Bob in a CoinSwap, it's a two-party protocol, which may make it simpler to implement even though it involves roughly eight times the number of operations compared to a maximally simple CoinJoin.

CoinJoins can be done with a single round trip and no waits on the Bitcoin network. CoinSwaps require many more back and forths as well as waiting for confirmation of escrow payments.

CoinSwaps can happen across chains. CoinJoins are inherently single chain operations.

It's possible to construct cryptographically-blinded CoinJoins where _no one_ learns whose output is whose (except for each output's owner). CoinSwap results in the participants knowing the linkage.

I think there is a place for both kinds of transactions. CoinJoins can be used opportunistically and can be used to achieve stronger anonymity in smaller groups (avoiding the risk of sybil Carols), while potentially CoinSwaps could achieve much larger anonymity sets at the cost of additional transaction fees.

Thats kinda bad for privacy.  You could use a cryptographically secure bloom filter to improve privacy, but it's probably asking too much for your CPU power.

Interesting, done right you could probably make it so your alert mechnism wrote a cryptographic proof that could be showed to other people.

Because it was not anticipated that users would reuse addresses to begin with. It's intended that they use a new address for every transaction.

It can't— because you lose privacy that way. E.g. someone can look at the un-executed paths and see the hash-values and link them.

I moved the longer description to it's own thread: CoinSwap.

Petertodd would probably recommend bonding the cards in some (or multiple ways).

One way would be to make every card contain a shared bitcoin private key (same key in all cards) for some large amount of Bitcoin, visible sitting in the chain. The card could prove that it contains the key by being willing to do a bitcoin-signmessage for the key.

If someone can compromise your tamper resistance, they can obtain the coin and in doing so would alert everyone that the tamper-resistance has been compromised at least once.

Please say tamper-resistant.

Otherwise you are overselling the possible.

There is absolutely a place for that kind of system, but having a reasonable dialog requires being frank about precisely where the security breaks down.  E.g. if the tamper resistance is compromised, or the issuer cheats and issues fake cards or leaks their key, the result is a class break which renders all othercoin smartcards insecure and only useful for direct redemption to Bitcoin (because you couldn't trust if they were doublespends otherwise).

In general, it sounds like a fantastic idea.  I think it would also be neat if future Bitcoin hardware wallets had a smartcard slot that enabled them to host an othercoin card. (bitcoin hardware wallets are not as tamper resistant, but have important UI elements that protect you from compromise of your host).

I've referred to these as canary coins.

We do really believe that any G is equally good.  Sort of the sillyness I argued with nothing up my sleeve points in stupid protocols which really aren't nothing up my sleeve, there is nothing evil you can do with G selection.  In particular, the reason for this is because the group has the additive homomorphism, so if there were some magic G that let you solve the DLP you could reproject any pubkey onto a new G and then solve the DLP on that pubkey relative to the new G and thereby solve the original problem as well.

It's nice to have nothing to say at all, even in bad protocols though, so I tried to get DJB to change his definition of fully rigid to also encourage better G selection procedures, but I failed to convince him.  Our curve meets the definition of full-rigid as held by the currently strongest standards for EC by respected cryptographers today.

I gave an argument in SAGE:

F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
F2 = FiniteField(C.order())

#We anticipate someone to use 1/sqrt(2) to make a nothing up their sleeve point in this system:
Point_1 = C.lift_x(0x6A09E667F3BCC908B)
#(122254265231296204939 : 10348448370814257613525050294440956391133934006892469524333988955631776211309 : 1)

#Now we pick a random value to be the discrete log of our point.
DLP1 = 31337
#and set the generator of our new public cryptosystem:
G = Point_1 * int( 1 / F2(DLP1))
# (3289106939212447273101810288144217892737559734143795594097718377788892356978 : 93681368535132531056006250228841417954446824336668031982795047251196201715915 : 1)

#Now, observe:

G * DLP1 == Point_1
#True

# DLP1 is now the discrete log wrt G of our "nothing up our sleeve point".


To which he replied "Protocols such as signatures are designed to be secure no matter what the generator is.", which is absolutely true.