Topic: Really Really ultimate blockchain compression: CoinWitness (Read 34234 times)

Yes, check out the recent paper on  "Scalable Zero Knowledge via Cycles of Elliptic Curves": http://eprint.iacr.org/2014/595

Which is a pretty wild technique.  Basically they managed (through an enormous amount of computation) to find a pair of pairing-compatible elliptic curves such that the number of points on one is the size of the finite field the other is defined over, and vice versa.

What this means is that in a ZKP written using curve A it's cheap to run the verifier for ZKP written in curve B. And for ZKP in curve B its cheap to verify proofs for curve A.

They take this structure and write proofs of the form "Verify a ZKP in the other curve of the machine state;  Execute one more instruction on top of that state.". Then they alternate these constructions, allowing for completely linear scaling.

The downside is that this magical stunt requires they use curves where the ultimate verifier (not insider a proof but on a computer) is a far bit slower. It also only allows for 80 bit security (The size ratios make achieving 128 bit security much harder). It also only helps for problems that work by repeated application of a universal circuit, like running tinyram, rather than running a hard wired application specific circuit— which many applications will have preferred for performance.

As people are talking about scalability again, is there any new development in SCIP?

Here is self-modifying code: http://eprint.iacr.org/2013/879

The class of techniques is universal up to the parametrized runtime limit, as you note— while that technically makes it non-universal— well, in a finite universe everything has a finite tape .
I'm told electrum now connects to multiple servers, which helps. Some of the things I was discussing here is SPV but counts on other people to go out and find and get mined the evidence of a longer chain, maybe arguably in-better.  SPV could— in theory— be boosted to full security compactly if you were able to have SNARKs for block validity as the block headers could carry proofs that they were a result of validating a faithful history though the engineering gap to verify such large computations is pretty big.

Somewhat relevant on the subject of the SPV tying of external systems is the abstract I submitted to an upcoming bitcoin workshop (and the citations it includes): http://0bin.net/paste/vkc4NWr3BeXwgO6O#TzYCxardJ3U4lkQAoP8mv+/nDJWZZk6TZeWKrMQ1Gcc=

This is really way cool stuff!



Er, not quite.  You have to commit to an upper bound on the running time in advance; Turing machines have unbounded tapes -- and the unboundedness of the tape is really critical to most reasoning and reductions involving TMs.

This doesn't change the fact that this is a fantastic idea, or the fact that SNARKs are cool.



This is one place where unboundedness matters.  An unbounded machine can emulate a machine that executes self-modifying code.  Compilers and proof checkers (as in logical proofs, not cryptographic proofs) are another.

Block depth check (as opposed to block height check).

• Electrum is (last time I checked) just block depth check.
• SPV is block depth check on the longest-header-chain (no block validation, header-hash-chaining and difficulty check only).
• Full clients are block height check on the longest-valid-block-chain (transactions validated).

At the moment there's not an enormous difference between the practical security level, but (as gmaxwell mentioned) the distinctions will start to become more pronounced as the block incentive drops.

In attempting to understand span programs and not having ready access to the citation [1], I found the following explanation available online at books.google.com.

Extremal Combinatorics: With Applications in Computer Science By Stasys Jukna


Also.

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs, 1.3 Monotone span programs

[1] Mauricio Karchmer and Avi Wigderson. On span programs. In Structure in Complexity Theory Conference, pages 102–111, 1993.

Here's my idea how to make something conceptually similar to CoinWitness for colored coins, without SCIP and without protocol changes: (SCIP is optional)


EDIT: Users who run thin clients and thus are unable to verify proofs themselves can outsource verification to a network of validators à la Ripple consensus (https://ripple.com/wiki/Consensus#Not_colluding). Of course, it is possible that these validators would collude and try to fool users. Such collusion can be detected by any entity which runs verification independently, and a cryptographic proof of wrongdoing can be produced. Due to the nature of colored coins, damage from this collusion will be limited to users who: 1) trusted validators; 2) accepted payments when collusion was in effect. Others will be unaffected. Thus robustness of colored coins w.r.t. erroneous transactions might allow us to replace a complex approach like SCIP with simpler one (but less reliable).

Thanks for bringing this to our attention  

I don't see how the blockchain validation scheme would work, seeing as somebody wishing to verify the blockchain would need to (according to the SNARK paper) perform operations of order > P to prepare for verification, where P is the program they could have just run to verify the blockchain. 

However, something like your CoinWitness seems feasible to me though I don't see all the details.  I am also excited that this type of scheme could be used as basis of a proof-of-work chain in which the work was programs submitted with a fee by parties who wanted the programs run for whatever purpose.  I think this was proposed elsewhere on this forum back in the day but I can't seem to bring it up.  Of course it would be even nicer if the computation were fully homomorphically encrypted but this is not necessary (there are programs people need run but don't care too much about the privacy of the contents and output). 

I have one more question for gmaxwell: how do you deal with the divisibility of the off-chain coin? It seems the off-chain coins are transferred like smart properties, which means that they are indivisible. If one tries to divide a coin in the off-chain system, there is no guarantee that the fractions will reunite in the future, making them permanently locked in the off-chain system. Therefore, people need to mint off-chain coins with different denominations for daily use. However redeeming a low value coin may not be economically viable due to relatively high bitcoin miner fee.

]
Yes, I was referring to that and I got my answer, thanks. Making it
harder for the oracle to cheat, fair enough.


But I still don't understand this part. The only stuff that changed was
on the oracle, not the chain. I don't get how Alice "spends her one
and only chance of redemption".


So coinA = {value, HA, previousHistory.append({previous owner pubkey, SHA})}
And coinB = {{value, HB, previousHistory.append({A pubkey, SHB})}}

I understand how the SCIP script can accept coinB for redeption now,
but I don't undesrtand why coinA cannot be used for redemption
anymore.
Alice has only signed additional data, but coinA as input for the
SCIP script should be producing the same result.

With the external chain approach I see the same problem. Unless the
bitcoin chain directly observes the current utxo for that chain, how
can the script tell if the transcript used for redemption contains
the full history of the colored coin and no transactions have been
validated in the external chain after that?

This double-redemption prevention mechanism that doesn't rely on
proof of work seems magical to me.
 
What am I missing?

By the way, the external chain approach reminds me a lot to private
chains in freimarkets. The blocks are signed by trusted accountants
that are responsible to prevent double-spending instead of having
proof of work, but he can still publish the chain or use SCIP-based
audit tools to prove he's accounting correctly so far.
Instead of this magical redemption, someone issues off-chain coins
that can be traded directly and atomically for bitcoins or other
in-chain assets. Users have to trust the issuer of the off-chain
asset too (which may not be the same person as the accountant of the
private chain), but again SCIP audits can make continued cheating
impossible.

Still, the in-chain coin and the off-coin chain are
different assets (one backed by the other, but not directly fungible)
and they need to be traded. If I get to understand your
double-redemption prevention mechanism, we could improve that
situation by incorporating it to our proposal.

That solution could also be used with other public chains. For
example, bitcoins could be moved in and out of the freicoin chain to
be traded there. But again, I just don't see how this is possible without
bitcoin and freicoin chains completely observing each other.

I think he's referring to my lately proposed system

Although there is only one "timestamp miner", i.e. the oracle, in my proposed system, the timestamps list is made public and everyone can verify. Although the oracle won't do any PoW, it can't trivially rewrite historical timestamps because they are buried in the bitcoin blockchain. So basically, it has the same security level of bitcoin: everyone can verify, and protected with SAME amount of PoW. Since the timestamps list is merely a list of hashes, there is no privacy concern.

The merchant will verify that there is no replay in the current and all previous timestamps. The future ones are irrelevant because the system will always favor the first owner of the off-chain coin.

For the rest of jtimon's questions, I think gmaxwell has answered.

The purpose of block confirmations is moving coins between different external systems, paying some who doesn't want to use those systems (because they do have a different security model than Bitcoin), etc.

Because to redeem Bob must first pay to a special "address" which is really just a blinded copy of the Bitcoin address he's paying it to. This would be the mandatory last step in the transcript. Alice cannot redeem because she used her one and only spend to pay bob.

Even if the oracle misbehaves it can not steal coins without the cooperation of the current or past owners of that coin. It is also completely blinded to the identity of the transactions is assisting in (can't tell their value, who they're coming from or where they're going, can't see any linking). And with the longest-transcript-timelocked-refunds discussed in some of the above posts the coins are all still completely recoverable if the oracle vanishes too.  Every possibility has its tradeoffs and this isn't perfect, but its certainly not the same security model as "deposit funds with an opaque bank".

Since the absence of replay transactions is not validated by miners when these timestamp blocks get into the chain, you still have to trust the oracle not to replay transactions. So I don't see what exactly the merchant gains from waiting for block confirmations instead of just quering the oracle directly and instantly.

I don't even undesrtand how the redeption is even secure.
If the off-chain coin goes from Alice to Bob. When Bob wants to redeem it for the in-chain coin, couldn't Alice still try to redeem it as well?

Before sending the off-chain coin to Bob, Alice could have exercise redemption with the proofs she already had. What exactly invalidates those proofs when she sends the off-chain coin to Bob?
I undesrtand how Alice's signature can give Bob the ability to redeem, but I don't undesrstand how she sacrifizes her own ability forredemption at the same time.

It seems to me that you will always need the signature of an external accountant to guarantee who is the current owner. At that point you're basically depositing the Bitcoins with the accountant, so basically you're sending BTC from one mtgox account to another, which doesn't remove much trust.

I have an idea to combine the blockchain-based and anti-replay oracle schemes for a stronger model.

1. The oracle will create an UTXO on the bitcoin blockchain and announce it to the world. (the "initial UTXO")

2. The oracle will collect timestamping requests from users. The requests are in the form of {HC,SHB} (as defined in OP). The oracle will accept a timestamping request only if it has never seen something beginning with the same HC before

3. With all timestamping requests collected, a Hash Merkle Root ("HMR") is calculated.

4. Using the initial UTXO as input, the oracle will create a transaction with only one output (the "second UTXO"), with a script like:

5. Before the transaction is mined, the oracle will update the transaction if it receives more timestamping requests. It will pay more fee to encourage miner to accept the updated transaction. (There is no big deal if an old version is mined. Just some people need to wait for the next block)

6. When the transaction is mined, the oracles will publish all timestamped requests.

7. The oracle will use the second UTXO to create a new timestamping transaction. The procedure is repeated, making it a chain of time stamps.

8. Usually there should be only one timestamping transaction in a block. After a blockchain re-org there could be more than one such tx in a block. But this is okay since the sequence is always clear.

On the user side:

1. When a merchant receives an off-chain coin (as described in the anti-replay oracle in OP), he will not deliver the product until he finds that the off-chain coin is timestamped in the blockchain with at least one confirmation. He will also check the hashes lists of the current and ALL previous timestamping transactions to make sure there is no replay. He will deliver when he is satisfied.

2. The merchant won't need to keep monitoring the future timestamping transactions. Instead, he will just monitor the bitcoin blockchain to see if someone is trying to redeem the SCIP-locked bitcoin. (Such redemption should not be possible unless the oracle replays)

3. We may have a separate P2P network to distribute the hash list, and use something like bloom-filter to allow light nodes to verify its newly accepted off-chain coins.

The SCIP-locked bitcoin:

1. The SCIP-locked bitcoin is redeemable with a proof of the full transcript (as OP suggest), PLUS the SPV links showing that the transcript is buried in the blockchain.

2. Using CoinCovenant, the SCIP-locked bitcoin is sent to another SCIP address. If it is not challenged by other people, the bitcoin could be sent to a normal bitcoin address after a timeout.

3. If the oracle replays, the first owner of the off-chain coin (the merchant in the last section) will find the redemption attempts on the blockchain. Now he will publish his transcript, with SPV links showing he is an earlier owner, and sends the SCIP-locked bitcoin to another SCIP address. Again, if it is not further challenged by other people, the bitcoin could be sent to the merchant's normal bitcoin address after the second timeout.

--------------------

This system is better than the original anti-replay oracle scheme because the bitcoin blockchain provides an undeniable proof of timestamp sequence, so the SCIP could judge who is the original owner.

I wrote up this little spec a while ago for such an oracle which would be immediately useful (e.g. useful without this coinwitness stuff), e.g. for anti-doublespending bitcoin transactions:

http://0bin.net/paste/JCtxYmKrRXfGE6jw#M2b+70sG971rHdEmDKIDgz2PT/zlgSDa8zCTLHE1xbM=

I think it would be useful to implement one— in a very "embedded system" style, e.g. straight C minimal/no dependencies— so that it could easily be ported to some strong trusted environment, even an IBM cryptocard ($$)... but to start it could run normally.   I make some suggestions on how it could avoid ever growing hashes, same as you're suggesting.

In theory a modern intel cpu with the right security bits and a tpm will get you working remote attest. I have no clue what the state of the software is in right now. But I'd suggest starting here.

My thinking is that such a system would have layered security— part from reputation, part from things like performance bonding, part from a trusted hardware environment, part from just simply having little incentive to cheat.  All these things don't need to exist at once in order to get something started and start creating applications.

I think this is a better idea than the "trusted-computing bank" proposed by retep, because the oracle won't directly hold bitcoins, and it is also much more anonymous. I'm quite interested to build one, just for fun and for experiment. However, I have the following practical issues:

1. Do I need to buy very expensive TPM hardware to run this? As I know current Intel CPUs have trusted computing support. Could that be used for such purpose

2. It seems I have to hold an ever-growing list of hashes to avoid replay. That won't scale in long-term. Is there any solution? One way I could think of is to revoke signing key regularly and drop the related hash table.

Oh, gotcha. Indeed, oracle based timeout means that prior parties to the transcript can make you waste your time.  Though if the horizon of it is set further than some likely lifetime of the coin, it's moot— and mostly serves the reduce the motivations someone might have in shutting down the oracles.

"You can kill these things, but if you to all you'll have successfully done is made their users wait a bit then waste some effort."

Sorry for the confusion. This comment is referring to the timeout mechanism for oracle-based system.

Hm? You'd still have to provide a transcript that shows the coin being directed back to bitcoin via sending it to a special destination.

You provide such a transcript to redeem the coin.

Someone else can provide a conflicting transcript but only if its of a longer conflicting chain.

So you can dos, but only if you're also reorganizing the secondary chain (or at least producing more POW than that chain).

Done. Thanks for elaborating. Good to see that we are not in disagreement.