bump

Very true, but I spoke with Eli today and maybe particular opcodes can be optimized especially for Bitcoin. For example the TinyRAM can include a special opcode to verify ECDSA signatures, that would be optimized by avoiding the need to translate a C style ECDSA algorithm to a circuit, and instead directly use an algebraic circuit over F_p that implements the ECDSA verification algorithm. There's a lot of room for optimizations.

Bootstrapping this process works ok? The initial scriptpubkey of the input transaction didn't have this validation key, so the SCIP program should say that a standard input there is ok too?

If I understand correctly, the user who receives the coin is the one who decides to add the extra THIS_VALIDATION_KEY rule that will be enforced forever from this point forward? So this user is restricting himself to receive a coin that can only be spent in the future if the extra validation rule holds? I suppose that this would make the coin less valuable in comparison to a regular coin that doesn't have this restriction, so why would the user decide to add this extra validation rule to the coin that he receives in the first place? For example the most extreme validation rule would be that this coin is destroyed and cannot be spent at all, and here obviously the user would prefer to receive a fully-functional coin instead of this destroyed coin.

I agree in general that it's a good idea to make the Bitcoin client operate (by default) in a simple way that influences users to conform with security guidelines and match the vast majority of common use cases.
However, we should consider whether what you suggested indeed covers all the common use cases. One particular point that we should keep in mind is that BIP32 is a standard for creating keys rather than Bitcoin scripts/addresses. So for example if the user wishes to enhance his security by using a P2SH address that can be redeemed via one privkey that resides on his smartphone and one privkey that resides on his laptop, then he will need to give the sender a pair of account numbers (one that belongs to his smartphone's BIP32 wallet and one that belongs to his laptop's BIP32 wallet), and each time that the sender wishes to send a payment he will construct a script from two fresh pubkeys and thereby derive the P2SH address to send the coins to?

An observation regarding privacy/fungibility: if a user sends a tainted coin even to a dummy off-chain system (i.e. a supposedly off-chain system that he runs by himself and only he is aware of its existence), and after a while sends the coin back into the Bitcoin network, then it seems to me that that's already enough to un-taint the coin, because the rest of the Bitcoin network cannot distinguish between this scenario and a scenario in which multiple users sent coins to the off-chain system and mixed their coins among themselves so that the user who sent the tainted coin received a different coin in the transaction that's sent back into the Bitcoin network. In other words, the mere possibility that off-chain mixing systems exist is already enough to un-taint coins, without really doing any mixing. Note that the size of the proof is short i.e. not linear in the size of the computation or anything like that (it's the Merkle root hash of the PCP style proof + pseudorandom queries that are derived from the root hash to entries in the proof), so there isn't even a need to bloat the coin's transcript in the off-chain system so that nodes who try to impose policies on tainted coins couldn't see that the proof is too short, but anyway a dummy transcript that does one extra step of sending/receiving a coin once is enough in any case.

It seems to me that this general framework that Gregory Maxwell describes here supercedes other mixing proposals like the ideas of Adam Back, zerocoin, or non-protocol extensions that can be used on top of Bitcoin. And that's even before we start talking about the other important benefits in terms of scalability and extendibility of the off-chain systems.

Right, I wrote it less clearly than you. So the oracle only prevents double-spending in a generic way and he's oblivious to the fact that he assisted to destroy the coin, but the signature that the oracle provides for the particular off-chain transaction that destroys the coin is required for the verification (by Bitcoin nodes) to pass when trying to redeem that coin back into the Bitcoin network.


Maybe the distinction between soft-fork and hard-fork is less important than I thought, but I'm still a bit confused on why this is a soft-fork. With regard to a valid transaction that passes the SCIP verification (from the off-chain system back into the Bitcoin network), can you please explain why the older nodes would consider it to be a valid transaction? If that's the case, it means that the older nodes would allow anyone to spend such outputs, without checking anything at all?

Right, I see now. The thing that I missed is that you'd provably destroy the coins in the off-chain system. So for example in the anti-replay oracle system, the proof of destruction will be of a computation that includes a signature by the oracle that he considers the coin to be destroyed, so when a user initially sends a coins into this off-chain system he sends it to a SCIP program that references the pubkey of the oracle.

But why do you say that it's a soft-fork? Isn't it true the current Bitcoin nodes cannot verify such proofs-of-computation, and therefore they will disagree with the newer nodes regarding whether the transaction of the user who exited the off-chain system is valid, so the network would split unless the older nodes upgrade?


Yes, this new idea has much more beneficial properties (compared to just "compressing" the blockchain in order for nodes to be able to get UTXO checkpoints in a trustless manner, instead of getting the entire blockchain history from archival nodes). From what I know, I doubt that this idea was trivially obvious to anyone before now. If I remember correctly, you've said in the past that the properties that this kind of system can accomplish is what Ripple should have tried to accomplish.

OK, but I was looking for more specific details. What do the Bitcoin nodes verify exactly when a user exits the off-chain system? If a Bitcoin user transfers a bitcoin to an off-chain system, then later only another user who now controls that coin in the off-chain system can transfer it back to the Bitcoin network, right? So if a previous owner of that coin in the off-chain system could have produced (at an earlier point in time) the transaction that redeems that coin back into the Bitcoin network, what prevents this previous owner from redeeming that coin now that he no longer owns it in the off-chain system?

If I understand correctly, the transaction that redeems the coin back into the Bitcoin chain embeds inside it a required SCIP proof of a transcript that specifies that the latest history of this coin is that it is now spent back to the Bitcoin network. Thefore, Alice cannot also send this coin to Bob in the off-chain system, under the assumption that the double-spending prevention in the off-chain system is functional. But we'll wait for more info from gmaxwell...

The user who can create the Bitcoin transaction that redeems the coin back into the Bitcoin network is the one who holds the privkey that corresponds to the pubkey at the top of the coin's transcript in the off-chain system? If I understand correctly then the Bitcoin nodes cannot be completely oblivious to the off-chain system. So can you please elaborate on what exactly do the Bitcoin nodes verify when a user exits the off-chain system? You've mentioned in the first paragraph that this can be achieved as a soft-fork to Bitcoin, are you sure about that?

Similarly to atomic cross-chain trading (link), I think that a fair coin toss (without the possibility of extortion) can be implemented by selecting the winner via the least significant bit of two committed secrets, as follows:

Edit: Adam Back's protocol in post #37 supersedes this protocol (see also post #49).

1. Alice and Bob wish to do a fair coin toss where each of them inputs X coins and the winner gets the 2X coins.

2. Alice picks some secret A1 and reveals to Bob the value A2=SHA256(A1), and Bob picks some secret B1 and reveals to Alice the value B2=SHA256(B1)

3. Alice creates a "bet" transaction that takes Alice's input of X coins and Bob's input of X coins, and can be spent by ((Alice's signature + Bob's signature) OR (LSB of (A1 xor B1) is 0, and Alice's signature) OR (LSB of (A1 xor B1) is 1, and Bob's signature)), I mean here that this "bet" transaction has A2 and B2 hardcoded in it, and (A1 xor B1) is computed using OP_SHA256 when the script is executed with the needed preimages.

4. Alice signs the refund transaction that spends those 2X coins back to addresses of Alice and Bob (so each gets X coins back), and has locktime of (say) 300 blocks into the future, and asks Bob to sign this refund transaction.

5. After Bob signs the refund transaction, Alice asks Bob to sign the "bet" transaction and broadcast the "bet" transaction to the Bitcoin network.

6. Alice creates a "Reveal1" transaction that takes as input (say) 3X of her own coins, and can be spent by ((Alice's signature + Bob's signature) OR (revealing some B that satisfies OP_SHA256(B)==B2, and Bob's signature))

7. Alice asks Bob to sign a refund transaction for "Reveal1" with locktime of (say) 100 blocks into the future.

8. Bob creates a "Reveal2" transaction that takes as input (say) 3X of his own coins, and can be spent by ((Alice's signature + Bob's signature) OR (revealing some A that satisfies OP_SHA256(A)==A2 and revealing some B that satisfies OP_SHA256(B)==B2, and Alice's signature))

9. Bob asks Alice to sign a refund transaction for "Reveal2" with locktime of (say) 200 blocks into the future.

10. Bob broadcasts his "Reveal2" transaction, and when Alice is confident enough that "Reveal2" will be mined into the blockchain she broadcasts her "Reveal1" transaction. Depending on the amount X of the bet, Alice can choose the appropriate confidence threshold. For example. if Alice doesn't wait for at least 1-confirmation then it might be risky because Bob could try to broadcast a conflicting transaction (after Alice broadcasts "Reveal1") with a higher fee that spends the 3X coins input of "Reveal2" to an address that he controls.

11. If Bob spends Alices's 3X coins via the transaction "Reveal1" in the next 100 blocks then he reveals his preimage B1

12. Now Alice can spend the transaction "Reveal2" in the next (at least) 100 blocks and thereby reveal her preimage A1, to get back the 3X coins that she lost.

13. Now the winner of the bet can spend the 2X coins to an address of his choice, in the next (at least) 100 blocks.


We can of course replace this 300 locktime number with a smaller number like 6 or whatever. If the client implements this protocol without a need for human intervention then short locktime numbers should be fine. Alice and Bob can broadcast all those transactions before any new blocks are mined, therefore if neither of them is malicious then the winner of the bet will be revealed instantly.

So, is it true that this protocol gives a fair coin toss with no possibilities for extortion and no need to trust a third party, or could someone spot any defects in it?
Maybe someone could come up with a more simple protocol that accomplishes the same goal?

1JpVUU3VQjkYKSfot6PDQXs8un11Dg2ZZN
I'll put it in my signature too.
Thanks.

I tried it now, it mostly works quite nicely...
Issues:
1) When reloading the page the BTC balance increases (as gbl08ma said) but no new testnet transaction actually occurs, and when reloading again the balance returns back to the correct lower balance.
2) The "Block Explorer" links don't seem to work (when clicking the small play button next to the transactions), even though the testnet transactions are real (I received coins with other faucets too), because http://blockexplorer.com/testnet isn't up-to-date.
3) It was a little confusing that the p2ptrade dialog window "X" close-button on top-right is invisible until hovering on it, at first I reloaded the page to get out of there.
4) The p2ptrade buy/sell of colored coins doesn't seem to execute. After issuing new colored coins and using p2ptrade to sell some of these colored coins, I do see in the other wallet (in incognito browser) the sell order so I have the corresponding (blue) "buy" button there, and when I click on this "buy" button it creates buy orders with the correct price, but the orders don't actually execute as far as I can see. On the other hand, the "send coins" button for sending colored coins directly to a (colored) address (in the other wallet) works well.

The 10% discount on the product itself will stay (when paying with Bitcoin), the 10% discount on shipping I'm not sure.

My familiy's business now accepts Bitcoin: http://aviot.com/vb/index.html

We are selling original wooden game stations that are called "Vector Ball", take a look at the video clips for a demonstration.

Here is another video that illustrates the mechanism in some of the more complex models: http://www.youtube.com/watch?v=ZFn5nsz6mL0

I listed on the website some selected shipping costs of ours. It's difficult to find cheaper shipping options due to the dimensions and weight (120x120x60 cm, 65 kg). The Vector Ball station will be packaged inside a specially prepared wooden box. Right now if you pay with Bitcoin then we will give 10% discount on the shipping too. It's an air freight door-to-door shipping, and it will take 12 business days to arrive if the Vector Ball model is in stock. If it isn't in stock then it will take up to two additional weeks to assemble it. Some models don't have a price listed next to them, which means that they are out of production.

Regarding my trustworthiness, you can check my posts history on bitcointalk, and I also know in real life other reputable forum members (link) and people who attended the Bitcoin conference. BTW these Vector Ball game stations were featured at an exhibition in the national museum of science in my country, unfortunately I cannot find English links, here are some translated links instead: [1] [2]

If anyone has any questions, for example a technical question about the mechanism of a Vector Ball station, or a question about other wood products on our website, then please ask in this thread.

If the chain forks, each node needs to decide whether it goes with the branch that's endorsed by your centralized checkpoints, or with a competing branch. All the nodes that trust your centralized control will enable the centralized checkpoints system. Furthermore, it would be rational for every node that doesn't trust you but still believes that in case of a fork the majority will go with your endorsed branch (because many other miners will trust the checkpoints system) to also enable the centralized checkpoints system, so that it would avoid financial loss in case of a fork. If the primecoin protocol is sound, i.e. it is secure against double-spending attacks, then this centralized checkpoints system isn't needed under the assumption that the majority of the mining power is honest. If a dedicated attacker spends his money on mining power in order to attack your sound+innovative protocol, you should take it as a compliment. If the primecoin protocol is unsound, this entire discussion is meaningless. The checkpoints of Bitcoin are in client upgrades that are signed by multiple developers, and their upgrade process is meticulous and transparent, though still there's room to discuss better options than the inelegant checkpoints that Bitcoin uses. There is a substantive distinction between a miner who chooses to run client software with past checkpoints the the developers signed (as in Bitcoin), and a miner who chooses to run client software that selects the winning branch according to future checkpoints that are continuously being fed to it by a central entity. If you think that the primecoin protocol is sound, I recommend that you remove this automatic checkpoints system. Both because it will be bad PR for you as scamcoin accusations may persist (and they wouldn't be without merit), and because it's useless over the long term if the majority is honest. Otherwise, maybe someone else who cares about decentralization and thinks that the primecoin protocol is sound will try to initiate a new chain by forking your client, which would dilute the honest mining power.

Edit: replaced hashpower with mining power

This idea keeps getting reincarnated in different forms, but it's a naive idea. For example I remember that I discussed it with Meni in the context of cementing prior to decentralized checkpoint blocks (where the client could un-cement at the checkpoint, which would be better than what you propose). The problem with this idea is that an attacker can create netsplits by broadcasting a competing branch with same height as the cementing limit, and potentially cause chaos (under the assumption that the network is decentralized). Gregory Maxwell explains nicely the naivety of this idea:

No, that's why it's called "atomic", either both parties live up to their end of the bargain, or nothing happens.


No, if one party aborts in the middle then both parties retain the coins that they originally had. Therefore extortion isn't possible.

Not sure what's the proposal that you have in mind, I remember others talking about such ideas in 2011 in #bitcoin-dev (link), and these ideas could be a lot more efficient than using ZK proofs.

I believe that the idea is that instead of how blocks are created now for the blockchain, the network nodes will create "mixed" blocks in 3 rounds of communication, instead of 1 round. Suppose Alice wants to send 5 bitcoins to Bob, Carol wants to send 4 bitcoins to Dave, Ellen wants to send 3 bitcoins to Frank, and we now wish to construct the next block with these three transactions. So in round 1 Alice broadcasts a message that declares that she intends to send 5 bitcoins to Bob's address (without signing this message with her privkey), and Carol and Ellen do the same. Now in round 2 the miners prepares a single transaction with the inputs of Alice,Carol,Ellen (12 bitcoins in total) and the outputs of 5 bitcoins to Bob's address, 4 bitcoins to Dave's address, 3 bitcoins to Frank's address, and broadcast this single transaction. In round 3 Alice signs this single transaction and broadcasts her signature, and Carol and Ellen do the same. Now the miners can do PoW work on a block that contains this transaction, and finally broadcast the valid block that they solved. This way the block is created in a mixed fashion, in the sense that the data that resides in the blockchain doesn't specify whether Alice's (possibly tainted) coins were sent to Bob or Dave or Frank. After iterating this same process with the next blocks, it would be practically impossible to tell where Alice's tainted coins ended up at. An attacker can eavesdrop on the network and know that Alice sent her coins to Bob, but he cannot prove anything because Alice's message in round 1 isn't signed and therefore can be forged by anyone.

Problems with this idea:
1) Alice must send a fee as a secondary signed transaction in round 1, otherwise if Alice is malicious then she could refuse to participate in round 3 to carry out a denial of service attack, because the single mixed transaction is valid only if both Alice and Carol and Ellen sign it. On the other hand, malicious miners could now collect fees without including txns in blocks. Maybe it can work if the fee in round 1 is smaller than the fee that Alice would pay for the actual transaction where she transfer her coins Bob, so the miners will have an incentive to generate non-empty blocks (i.e. not to generate blocks that contain only the fees of round 1) ?
2) When the miners are working on the PoW, if other transactions (with high fees) were broadcasted in the meanwhile, then in order to include the extra transactions they'd have to prepare another single mixed transaction (because the signatures for the first mixed transaction have already been provided). So it appears that this process will work in batches, where a block could contain several such mixed transactions. We should be careful that the default behavior of nodes is to prefer signing mixed transactions with many inputs, otherwise malicious miners could attempt to reduce the overall privacy.

Any suggestions on how to improve this idea?

Edit: Looking at another thread (link), I see that here too we'll have to do the knapsack-style random value splits. I suppose that it means that Alice should request several receiving addresses from Bob before she sends her coins to him? Or maybe just one pubkey and chaincode, if Bob is using type-2 deterministic wallet.

Ahh, I see, in post #19 I responded to an earlier variation where you were using the OWF txcommit=SHA256(tx) rather than the reversible txcommit=AES(K,tx) with K=SHA256(pub), so with this variation if an attacker somehow obtains a pubkey then he can unblind/decommit a blind txn that's on the blockchain, but he cannot lock coins forever with junk txn data. Therefore if Alice tries to double-spend, she reveals the pubkey and then the network can fully examine the earlier blind txn and see that it's valid, and reject Alice's double-spend attempt.

I guess that the main issues are:
(1) attackers could spam the chain with blind commitments that consist of junk (random hash of supposed pubkey), and all the nodes would have to perform extra work on an ever-increasing set of blind-UTXO for verification whenever a legitimate pubkey is decommitted.
(2) as follows from (1), the txn-fees for blind commitments will probably be much higher than regular txns?
(3) if some pubkey leaks then an attacker can immediately un-blind the relevant txn. I'm not sure what are the negative implications here. If I understand correctly then you claim that it's fine to un-blind when the blind commitment is already buried under enough PoW blocks, because the recipient can create a new blind commitment that spends those coins (since the recipient hashed address that appeared in the first blind commitment will be different than the secondary e.g. SHA1(SHA256()) hash that would appear in the following blind commitment, so even if the first txn gets un-blinded and revealed as tainted, the network cannot detect that the following blind txn is linked to it) ?
(4) the extra layers of complexity for the symmetric encryption and MAC, though it's not really a big deal I suppose.