Bitcoin Forum April 16, 2018, 03:48:09 PM
Welcome, Guest. Please login or register.
News: Latest stable version of Bitcoin Core: 0.16.0 [Torrent]. (New!)
HOME
HELP
SEARCH
DONATE
LOGIN
REGISTER
Search
Bitcoin Forum > Bitcoin > Development & Technical Discussion (Moderators: gmaxwell, achow101) > Really Really ultimate blockchain compression: CoinWitness « previous topic next topic » print
Pages: [1] 2 3 All Author
Topic: Really Really ultimate blockchain compression: CoinWitness (Read 33697 times)
gmaxwell
Really Really ultimate blockchain compression: CoinWitness
Moderator Legendary
August 19, 2013, 05:53:55 AM
#1
In this message I offer a brief start of a proposal for improving the scalability, flexibility, privacy, and fungibility of Bitcoin. The idea is based on bleeding-edge cryptography and would require a soft-fork to deploy—so it is not something which could be implemented immediately, but I believe it would be a useful area for further research. Activity: 2436 Merit: 1183
In SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge (referred to as SCIP below), Eli Ben-Sasson et al. describe their work on highly efficient non-interactive proofs with zero-knowledge for the faithful execution of programs written in C. Eli also presented at the Bitcoin conference. The short layman's explanation of their work is that they've constructed a system where someone can run an arbitrary program inside a special environment and then publish a very compact and quickly-checkable proof which will convince anyone that 1) they ran the program faithfully (e.g., without modification or tampering) and 2) that the program "accepted" (e.g., exited with return true;) with a given set of public inputs and (optionally) additional non-public inputs. Because their system provides computational zero knowledge, the program's execution can also depend on any non-public inputs and the validator learns nothing about them beyond the fact that the program accepted. The mathematics behind this are highly dense—starting with the surprising result from over twenty years ago that all programs can be converted into interactive proofs, they apply many layers of techniques to build a concrete system with performance that could actually be used, rather than just a proof that proofs of programs are possible. I've proposed some interesting ideas on how to use this kind of technology with Bitcoin which don't require any changes to Bitcoin itself elsewhere. But if you add the technology directly to Bitcoin some more interesting things become possible. One of the obvious applications of this idea is that it could replace script in Bitcoin. Instead of embedding the rules that govern an output inside the blockchain, you'd instead embed a proof that the rules were followed. Instead of everyone checking that a transaction was permitted to be spent, they'd instead check that you checked. This is itself interesting, as it would make much more powerful scripts possible without burdening the network with their execution, but improvements to script aren't terribly exciting when the existing system is so far mostly unused. Additionally, the verification of SCIP proofs is somewhat slow compared to ECDSA (on the order of, say, several hundred times slower), and although it scales excellently most transactions are very simple with only a single hash and ECDSA operation. Here I suggest one very interesting way this functionality could be used. Let's imagine that my friends and I agree on a set of rules for a verifiable off-chain transaction system. By "verifiable", I mean that if its users record a transcript of the activity for a single coin, they could show the transcript to a third party, and the third party would be convinced that the system is behaving correctly and would know who the ultimate owner of the coin was. Here are two example systems which would meet that criteria: Anti-replay oracle based Alice has a digital coin: coin={Value, Alice's pubkey, transcript of the coin's history}, and wants to assign it to Bob. Bob tells Alice Hash(bob's pubkey)=HB. Alice computes Hash(coin)==HC, and also Sign(HB)==SHB. Alice contacts a trusted anti-replay oracle, telling it {HC,SHB}. The oracle returns Sign({HC,SHB}) if and only if it has never signed something which began with HC before. Alice passes this information on to Bob, along with the coin. Bob checks the coin's history and is satisfied that he has a valid coin which has not been doublespent. This can be continued on and on, passing a coin from party to party, producing an ever-growing transcript. It can be trivially extended by using M of N anti-replay oracles, or other similar improvements. The anti-replay oracles this uses are trusted to not replay, but since they only deal with hashes they learn nothing about the transactions (or even that they're being used for a currency-like use—it might just be timestamping for all the oracle can tell). Such an oracle could be on trusted hardware, fidelity bonded, secured by a bounty txout that you can redeem if and only if you can publish a proof showing a replay, etc. Blockchain based Alice has a bitcoin which is represented by a colored coin in some other specific blockchain, perhaps a geographic-specific blockchain. Alice passes it to Bob by transacting in the normal way. Bob can form the verifiable transcript by grabbing every transaction along the colored coin's path along with the SPV fragments connecting them to the chain and some additional blockchain headers to show the transactions are adequately buried. (I provided two examples here to make a point that the idea is completely general. Any other system with the verifiable property, E.g. OpenTransactions, complicated ones involving voting by all participants, or even trivial ones that doesn't have double spending prevention, could be used. Though they'd work best if constructed for very efficient validation.) The idea I'm calling CoinWitness is this: You write down a small program which verifies the faithfulness of one of these transcripts for your chosen verifiable off-chain system. The program requires that the last transaction in the transcript is special in that it pays to a Bitcoin scrippubkey/p2sh. The same address must also be provided as a public input to the program. We call this program a "witness" because it will witness the transcript and accept if and only if the transcript is valid. You then use the SCIP proof system to convert the program into a verifying key. When someone wants to create a Bitcoin in an off-chain system, they pay that coin to the hash of that verifying key. People then transact in the off-chain system as they wish. To be confident that the system works faithfully they could repeat the computationally-expensive verifying key generation process to confirm that it corresponds to the transaction rules they are expecting. When a user of one of these coins wants to exit the system (to compact its history, to move to another system, to spend plain Bitcoins, or for any other reason), they form a final transaction paying to a Bitcoin address, and run the witness on their transcript under SCIP and produce a proof. They create a Bitcoin transaction redeeming the coin providing the proof in their script (but not the transcript, thats kept private), and the Bitcoin network validates the proof and the transaction output. The public learns nothing about the intermediate transactions, improving fungibility, but unlike other ideas which improve fungibility this idea has the potential to both improve Bitcoin's scalability and securely integrate new and innovative alternative transaction methods and expand Bitcoin's zero-trust nature to more types of transactions. Open challenges: This depends on new cryptographic techniques which may have security weaknesses and may have much room for performance improvement. Use of it requires adding the validation software to the Bitcoin network, which then fixes a particular proof format in stone. The SCIP proof validation is slow by our standard. In the paper they give an example from their implementation on a 2.4 GHz host where validation of a proof (which is only 2576 bits long for 80-bit security) on a small public input (which is the case for CoinWitness) takes 100ms. This is fast enough that it may actually be viable without further optimization considering the potential for compression of multiple transactions into one. SCIP proof construction is enormously slow by our standards. In an example given in their paper for a 100-instruction program which executes for 11001 cycles, proof generation takes 155 minutes. Proof time is basically linear with the number of operations, so bringing a coin with a long transcript back into the chain may be computationally prohibitive. However, since this is done off-chain, it at least puts the work with an interested party instead of externalizing it on the whole Bitcoin userbase. (And there likely is a lot of room to improve the performance with software engineering, in particular, the problem is very parallelizable) The SCIP keys must have an upper bound on the number of operations performed by the program baked into them. This results in a maximum transcript length which must be committed to in advance. I believe all these issues are surmountable, in time, barring any really exciting cryptographic breaks in the approach. This CoinWitness idea is something of a less ambitious example of what Eli suggested in his talk—effectively running blockchain validation under SCIP to produce UTXO checkpoints that have cryptographic proof of their correctness. But instead of validating all transactions from a public blockchain, here I suggest validating small sequences of private transactions to avoid ever making them public at all and, in doing so, improve the scalability, flexibility, privacy, and fungibility of Bitcoin. (And, in fact, this idea may in fact be trivially obvious to those working on the SCIP tools, but I expect it will blow some minds here).
Bitcoin will not be compromised
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
gmaxwell
Re: Really Really ultimate blockchain compression: CoinWitness
Moderator Legendary
August 19, 2013, 05:58:57 AM
Activity: 2436 Merit: 1183
#2
One cute note on the above is that in the blockchain based off-chain example system, the "off-chain" blockchain could be colored _Bitcoins_. Using Bitcoin as the consensus system eliminate the scaling advantages and flexibility in transaction rules, but it means you don't even have to assume an off-chain system if you just want the privacy benefits. The advantage from using Bitcoin itself and making one of the public inputs to the witness be a hash of a block which is required to be in the chain, you can increase the security of the "off-chain" coin from SPV+headers fragment to full security.
Bitcoin will not be compromised
Mike Hearn
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 19, 2013, 09:36:23 AM
#3
I wonder how this system compares to Pinnochio which has similar capabilities. Activity: 1526 Merit: 1000
http://research.microsoft.com/apps/pubs/default.aspx?id=180286 However, my understanding is that the performance is significantly better. One area I'm interested in the use of this is digesting bearer tokens like e-Passports into less sensitive, app-specific proofs that are combined with key material. For instance, I'd like to be able to sign payment requests as "myself" so purchasers can prove they really bought something from Mike Hearn the legal entity. It provides certainty and avoids some kinds of fraud. But my e-Passport doesn't support signing things itself (it could do, but it's an optional feature and the British government chose not to provide it, presumably for cost reasons). It boils down to a signed piece of data that is by itself quite useless. But with provable computation, I could generate a private key, give the public key+signed e-Passport data as an input, the program checks the signatures on the ePassport data to prove it's valid and then spits out its own kind of "certificate" containing some selected fields like name/date of birth/photo-hash plus my public key. The certificate is not a normal PKIX style certificate but rather is a proof that such a certificate was verified, along with the other inputs that were provided. At the moment this is too inefficient as you'd have to implement an entire crypto library inside the provable computation. I contacted one of the Pinnochio researchers and they said they were planning to explore ways to do crypto-inside-crypto in more efficient ways.
marcus_of_augustus
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 19, 2013, 01:30:32 PM
#4
Quote
Activity: 2590 Merit: 1050
starting with the surprising result from over twenty years ago that all programs can be converted into interactive proofs,
Interesting ... are there constraints on the set of programs or is it really 'all programs'? Quote
The idea I'm calling CoinWitness is this: You write down a small program which verifies the faithfulness of one of these transcripts for your chosen verifiable off-chain system. The program requires that the last transaction in the transcript is special in that it pays to a Bitcoin scrippubkey/p2sh. The same address must also be provided as a public input to the program. We call this program a "witness" because it will witness the transcript and accept if and only if the transcript is valid. You then use the SCIP proof system to convert the program into a verifying key. When someone wants to create a Bitcoin in an off-chain system, they pay that coin to the hash of that verifying key. People then transact in the off-chain system as they wish. To be confident that the system works faithfully they could repeat the computationally-expensive verifying key generation process to confirm that it corresponds to the transaction rules they are expecting. When a user of one of these coins wants to exit the system (to compact its history, to move to another system, to spend plain Bitcoins, or for any other reason), they form a final transaction paying to a Bitcoin address, and run the witness on their transcript under SCIP and produce a proof. They create a Bitcoin transaction redeeming the coin providing the proof in their script (but not the transcript, thats kept private), and the Bitcoin network validates the proof and the transaction output. The public learns nothing about the intermediate transactions, improving fungibility, but unlike other ideas which improve fungibility this idea has the potential to both improve Bitcoin's scalability and securely integrate new and innovative alternative transaction methods and expand Bitcoin's zero-trust nature to more types of transactions.
Wow, sounds good ... better than good. Monetary Freedom - an inalienable right Per aspera ad astra
EmperorBob
Re: Really Really ultimate blockchain compression: CoinWitness
Member
August 19, 2013, 03:49:45 PM
#5
Correct me if I'm wrong, but it's still possible to double spend the transcripted coin? Activity: 67 Merit: 10
1. Alice sends Bob the using the off-chain system. 2. She also redeems it onto the chain. She can do this anytime before Bob does (or whoever he passes it on to). Or is the idea that redemption step still requires the participation of the offchain system? If so it's still superior to existing off-chain systems in that funds can only be frozen, not confiscated.
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 04:16:31 PM
#6
Quote from: gmaxwell on August 19, 2013, 05:53:55 AM
Activity: 360 Merit: 250
When a user of one of these coins wants to exit the system (to compact its history, to move to another system, to spend plain Bitcoins, or for any other reason), they form a final transaction paying to a Bitcoin address, and run the witness on their transcript under SCIP and produce a proof. They create a Bitcoin transaction redeeming the coin providing the proof in their script (but not the transcript, thats kept private), and the Bitcoin network validates the proof and the transaction output. The public learns nothing about the intermediate transactions, improving fungibility, but unlike other ideas which improve fungibility this idea has the potential to both improve Bitcoin's scalability and securely integrate new and innovative alternative transaction methods and expand Bitcoin's zero-trust nature to more types of transactions.
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? Peter Todd
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 19, 2013, 04:32:03 PM
#7
Quote from: iddo on August 19, 2013, 04:16:31 PM
Activity: 1106 Merit: 1000
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?
Basically the idea is that in this case the funds are not spendable only by a privkey. Essentially the way it works is kinda like this: Make a transaction that tells the whole world that some funds are now only spendable if someone proves a certain computer program was run. Magic! Make a proof that computer program was run. (also magic) Show the rest of the Bitcoin world that proof, which shows why the funds are now allowed to move. This is basically how Bitcoin already works... except normally to verify the computer program was run, currently all Bitcoin nodes actually run that program. With SCIP, they don't need to actually do that - just the proof that someone ran it is enough. Yes I know that sounds kinda crazy, but amazingly math actually lets you verify that someone ran a particular computer program honestly without actually running it yourself or seeing all the data it operated on. Of course that program can be as simple as "Bob signed a message saying Alice deserves the funds now" or as complex as some multi-stage off-chain transaction thing where double-spends are prevented by a signing oracle that sees nothing more than some nonce values it timestamps. BTC: 1FCYd7j4CThTMzts78rh6iQJLBRGPW9fWv PGP: 7FAB114267E4FA04
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 04:35:06 PM
#8
Quote from: EmperorBob on August 19, 2013, 03:49:45 PM
Activity: 360 Merit: 250
Correct me if I'm wrong, but it's still possible to double spend the transcripted coin? 1. Alice sends Bob the using the off-chain system. 2. She also redeems it onto the chain. She can do this anytime before Bob does (or whoever he passes it on to).
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... iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 04:57:14 PM
#9
Quote from: retep on August 19, 2013, 04:32:03 PM
Activity: 360 Merit: 250
Quote from: iddo on August 19, 2013, 04:16:31 PM
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?
Basically the idea is that in this case the funds are not spendable only by a privkey. Essentially the way it works is kinda like this: Make a transaction that tells the whole world that some funds are now only spendable if someone proves a certain computer program was run. Magic! Make a proof that computer program was run. (also magic) Show the rest of the Bitcoin world that proof, which shows why the funds are now allowed to move. This is basically how Bitcoin already works... except normally to verify the computer program was run, currently all Bitcoin nodes actually run that program. With SCIP, they don't need to actually do that - just the proof that someone ran it is enough. Yes I know that sounds kinda crazy, but amazingly math actually lets you verify that someone ran a particular computer program honestly without actually running it yourself or seeing all the data it operated on. Of course that program can be as simple as "Bob signed a message saying Alice deserves the funds now" or as complex as some multi-stage off-chain transaction thing where double-spends are prevented by a signing oracle that sees nothing more than some nonce values it timestamps.
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? gmaxwell
Re: Really Really ultimate blockchain compression: CoinWitness
Moderator Legendary
August 19, 2013, 05:36:34 PM
#10
Quote from: iddo on August 19, 2013, 04:57:14 PM
What do the Bitcoin nodes verify exactly when a user exits the off-chain system?
Activity: 2436 Merit: 1183
Exactly what they need to, no less, no more. Or to be more specific, what you want to know is what the witness verifies. The Bitcoin nodes only ever verify that the witness was satisfied. If that sounds a little orbicular, it's because it depends on the details of the system in question. What I'm suggesting is a, effectively, an application for a replacement script system, the users provide the script. In general you'd provably destroy the coins in the off-chain system, in a way which binds the destruction to the bitcoin address you want to pay or in some other way visible to the off-chain users unbind them. The witness' job is to observe the transcript and be convinced by it. For the anti-replay-oracle example, you'd make a final off chain transaction with something like H('hello bitcoin!'||nonce||bitcoinaddress) as the destination, instead of a public key. This makes the coin forever unspendable in the off-chain system. For the colored-coin example, you might do something similar— you could pay the coin to an unspendable address that was really some hash of the intended bitcoin destination and a nonce, or you'd could just have the funds pass through a transaction that has a zero value OP_RETURN {hash like above}, not discarding the coin at all, but signaling to all the other users of your colored coin (by convention established in the coding of your witness) that it has lost its color in order to move it back to Bitcoin. (This latter case means you would need to be using special colored coin software for your intermediate transactions that watched for this happening in order to avoid getting cheated). In either case the nonce would never be made public, for privacy sake. It would be placed in the transcript, however, so that the witness could verify that you will be paying the correct Bitcoin destination, which you include as a public input so it can be checked against what you actually provided (I suppose technically it would be a hash of the masked redemption transaction and sighash flags and not an address, but ... implementation details). But whatever you're doing for double-spending prevention off-chain you'd effectively be using the same thing here to convince the witness that you're not doublespending your redemption. Or not— none of this actually requires you to be secure against double spending if you don't want to adopt rules which are... but, uh, no one else may want your double-spendable coins. Quote from: EmperorBob on August 19, 2013, 03:49:45 PM
If so it's still superior to existing off-chain systems in that funds can only be frozen, not confiscated.
And even there, part of the reason I gave an example using a hash blinded oracle is that it was one where the trusted part is so deprived of information it could only prevent spending by shutting down completely (and even not then if you use M of N them) or if the penultimate off-chain holder cooperates with it. I could easily imagine witness designs that reduce the frozen funds risk further in exchange for some double-spend risk. For example, if there is an alternative way to redeem the coin by providing a incomplete transcript (e.g. one where you're the final owner, but there is no transfer into Bitcoin at the end) plus Bitcoin headers proving that the current time is in the sufficiently far future. There is a risk that a prior owner of the coin will steal it at this point (by truncating their transcript), but that risk may be better then allowing the coin to be frozen forever if the off-chain system fails, and would only exist if the holder of the coin failed to exit the offchain system before their previously agreed on timeout ran out. Quote from: marcus_of_augustus on August 19, 2013, 01:30:32 PM
Interesting ... are there constraints on the set of programs or is it really 'all programs'?
It's turing complete, and for the purposes here it really is all programs. The system emulates a specialized harvard architecture virtual machine and cannot, as currently defined, run self-modifying code. The execution environment can only do input by reading from two one way input tapes (one for public inputs, one for private ones), and can only output by "accepting" or failing to accept by the time the user specified time limit is up. None of this is problematic for the use we'd want here— e.g. any output you make an input, and have the program accept only if it matches. The primary limitation that would confront users doing what I've proposed is that longer proof computation time results from longer execution time and larger proof construction memory (and also larger programs, but the growth is well controlled). Bitcoin will not be compromised
Mike Hearn
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 19, 2013, 06:21:37 PM
#11
OK, from re-reading the Pinnochio paper and a quick look at the zk-SNARKs paper, it seems like Pinnochio is much faster but has a much more heavily restricted variant of C. For instance qcc doesn't support mutable state or iteration so it unrolls all loops. Activity: 1526 Merit: 1000
Ben-Sasson et als work is therefore much more general, but also has way higher proving time. edit: actually I just noticed they have an entire section devoted to discussing Pinnochio. I didn't see it because they never refer to it by name, only by citing the paper (the title of which also does not mention the name). Quote
All previous implementation work (except the work of Canetti et al. [CRR11] on competing provers) requires an instance to be represented as a circuit, or other similar “low-level” representations. While [SBW11, SMBW12, CMT12, TRMP12] do not address the problem of converting arbitrary programs to a circuit representation, [SVP+12, SBV+13] do consider the problem of programming arithmetic circuits. Specifically, they present a solution, based on the Fairplay compiler [MNPS04, BDNP08], for compiling programs written in a special language called SFDL. Next, both [SVP+12, SBV+13] convert the output of the FairPlay compiler to the constraints required by their respective protocols. Compared with high-level programming languages like C, SFDL is quite limited in the sense that it does not support important primitives and has inefficient support for others. For example, SFDL does not support loops with a non-constant number of iterations; also, it does not support recursions. Furthermore, each array access of the form A, where A is an array and i is an index, is implemented via a multiplexer circuit over the entire array. In particular, relying on a compiler such as FairPlay has a severe drawback: the circuits it generates have size that is quadratic in the time bound T in the worst case, due to inefficient support of memory accesses. So, e.g., the prover in all previous works runs in time that is (T2) in the worst case. Parno et al. [PGHR13] do not rely on the Fairplay compiler, but also rely on an approach with a blowup that is at least quadratic in the worst case. Indeed, they provide a compiler for a basic subset of C that, like SFDL, is very restrictive: memory accesses are static constants, loops are unrolled up to a static bound, both branches of a conditional are executed, and so on. In particular, accesses to memory are inefficiently supported. The quadratic blowup in previous work is not accidental but is due to a fundamental difficulty: how is consistency of random-access memory achieved? As discussed (see Section 2.3.2), the naive solution of multiplexing from memory at each time step is inefficient. Instead, in this work (see Section 2.3) we implement an efficient circuit generator: by leveraging nondeterminism and routing [BCGT13a], we generate an arithmetic circuit whose size is only O(T log T). The bound holds even when a program makes use of datadependent loops, control flow, recursions, and memory accesses. (Indeed, the bound holds for all TinyRAM programs.) Because most prior works support circuit satisfiability, all these prior works directly benefit from our circuit generator in the sense that their circuit generators can be replaced with our more efficient one.
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 06:46:21 PM
#12
Quote from: gmaxwell on August 19, 2013, 05:36:34 PM
Activity: 360 Merit: 250
In general you'd provably destroy the coins in the off-chain system, in a way which binds the destruction to the bitcoin address you want to pay or in some other way visible to the off-chain users unbind them.
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? Quote from: gmaxwell on August 19, 2013, 05:53:55 AM
This CoinWitness idea is something of a less ambitious example of what Eli suggested in his talk—effectively running blockchain validation under SCIP to produce UTXO checkpoints that have cryptographic proof of their correctness. But instead of validating all transactions from a public blockchain, here I suggest validating small sequences of private transactions to avoid ever making them public at all and, in doing so, improve the scalability, flexibility, privacy, and fungibility of Bitcoin. (And, in fact, this idea may in fact be trivially obvious to those working on the SCIP tools, but I expect it will blow some minds here).
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. gmaxwell
Re: Really Really ultimate blockchain compression: CoinWitness
Moderator Legendary
August 19, 2013, 07:31:20 PM
#13
Quote from: iddo on August 19, 2013, 06:46:21 PM
Activity: 2436 Merit: 1183
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 compiled program that references the pubkey of the oracle.
The oracle doesn't have to know the coin is destroyed, though it could if you wanted to. In my example the coin is just paid to some hashed destination as far as the oracle can tell (well, technically the oracle doesn't even know there is a coin: It's just timestamping some data with a prefix that its never seen before). Other uses of the off-chain system know that destination isn't them, and thats sufficient to prevent double-spending. The witness knows the destination is Bitcoin because the redeemer provides the nonce. The distinction isn't super important, but it does inhibit certain kinds of DOS attacks (like the oracle refusing to let you take coins out of the system and put them back into Bitcoin). Quote
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?
Correct. A soft-fork change is one which strictly decreases the set of valid transactions. Old nodes accept valid ones under the new rules, but they also accept transactions which are invalid under the new rules so the network risks diverging unless at least a significant super-majority of mining hash-power enforces the new rules. We've made soft-forking changes a number of times, and I think we can make them pretty safely... or at least will continue to be so long as there remains a single codebase used for the full-nodes behind almost all mining. But they are still inherently risky and imply a long term commitment to the change and a public consensus to make it, so they can't be made lightly or experimentally. Quote from: iddo on August 19, 2013, 06:46:21 PM
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.
There are many neat off-chain systems possible— including ones with really good scaling properties (e.g. no global consensus, indeed what ripple could have been before the change in ownership)—, but even when they are themselves zero-trust or nearly zero-trust getting value in and out of Bitcoin without trust is a hard problem. I hope here that I've shown a potential tool we could employ to address that challenge. New cryptographic tools make many things possible which were unthinkable before. Someday people will look back at the things we invent between then and now and with a surprised tone exclaim "What? wasn't that obvious??", as some do even now about Bitcoin itself. I thought the idea was interesting, or else I wouldn't have posted about it— but I can't deny that at least half of the idea comes from simply having a basic understanding of these new tools. The potential to make easy discoveries like this is why tools like SCIP and Bitcoin are the new frontier and thats one reason I enjoy thinking about them and working with them. Bitcoin will not be compromised
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 08:52:55 PM
#14
Quote from: gmaxwell on August 19, 2013, 07:31:20 PM
Activity: 360 Merit: 250
Quote from: iddo on August 19, 2013, 06:46:21 PM
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 compiled program that references the pubkey of the oracle. The oracle doesn't have to know the coin is destroyed, though it could if you wanted to. In my example the coin is just paid to some hashed destination as far as the oracle can tell (well, technically the oracle doesn't even know there is a coin: It's just timestamping some data with a prefix that its never seen before). Other uses of the off-chain system know that destination isn't them, and thats sufficient to prevent double-spending. The witness knows the destination is Bitcoin because the redeemer provides the nonce. The distinction isn't super important, but it does inhibit certain kinds of DOS attacks (like the oracle refusing to let you take coins out of the system and put them back into Bitcoin).
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. Quote from: gmaxwell on August 19, 2013, 07:31:20 PM
Correct. A soft-fork change is one which strictly decreases the set of valid transactions. Old nodes accept valid ones under the new rules, but they also accept transactions which are invalid under the new rules so the network risks diverging unless at least a significant super-majority of mining hash-power enforces the new rules. We've made soft-forking changes a number of times, and I think we can make them pretty safely... or at least will continue to be so long as there remains a single codebase used for the full-nodes behind almost all mining. But they are still inherently risky and imply a long term commitment to the change and a public consensus to make it, so they can't be made lightly or experimentally.
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? Peter Todd
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 19, 2013, 09:01:15 PM
#15
Quote from: iddo on August 19, 2013, 08:52:55 PM
Activity: 1106 Merit: 1000
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?
That is exactly the case; see BIP 16 for an example where a soft-fork was used in that way. CoinWitness could be implemented similarly. Basically it isn't safe to use CoinWitness until >50% of the hashing power rejects invalid CoinWitness transactions, but unless you are a miner you don't actually need to upgrade your node. BTC: 1FCYd7j4CThTMzts78rh6iQJLBRGPW9fWv PGP: 7FAB114267E4FA04
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 19, 2013, 11:36:44 PM
Activity: 360 Merit: 250
#16
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 untaint 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 nonprotocol 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.
gmaxwell
Re: Really Really ultimate blockchain compression: CoinWitness
Moderator Legendary
August 20, 2013, 01:00:49 AM
#17
Quote from: iddo on August 19, 2013, 11:36:44 PM
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. Activity: 2436 Merit: 1183
Perhaps but there are deployment challenges, this technology will not be easy to get mature and adopted. I have alternatives which are more pragmatic if not as impressive in their mechanisms. You are going to like my next post too.
Bitcoin will not be compromised
iddo
Re: Really Really ultimate blockchain compression: CoinWitness
Sr. Member
August 20, 2013, 03:02:08 PM
#18
Quote from: gmaxwell on August 20, 2013, 01:00:49 AM
Activity: 360 Merit: 250
Quote from: iddo on August 19, 2013, 11:36:44 PM
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. Perhaps but there are deployment challenges, this technology will not be easy to get mature and adopted.
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. Mike Hearn
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 20, 2013, 03:05:22 PM
Activity: 1526 Merit: 1000
#19
Yeah, I was wondering yesterday how much scope there is for custom opcodes. I guess the issue is that each special opcode complicates the transition function and thus the circuit so it results in extra blowup per time step. Perhaps it's possible to have transition circuits that vary depending on what instructions are possible at each given point.
ShadowOfHarbringer
Re: Really Really ultimate blockchain compression: CoinWitness
Legendary
August 20, 2013, 03:33:43 PM
#20
Quote from: retep on August 19, 2013, 04:32:03 PM
Activity: 1470 Merit: 1000
This is basically how Bitcoin already works... except normally to verify the computer program was run, currently all Bitcoin nodes actually run that program. With SCIP, they don't need to actually do that - just the proof that someone ran it is enough. Yes I know that sounds kinda crazy, but amazingly math actually lets you verify that someone ran a particular computer program honestly without actually running it yourself or seeing all the data it operated on.
This may be the most fucking brilliant idea i have seen since the dawn of proof-of-work (or sliced bread), however I am obviously too stupid to verify if that will work or if that is even possible.
Bringing Legendary Har® to you since 1952 {{ Bitcoin.pl Elite Member, Bitcointalk HLegendaryH [1344] }} 1NLWBAD7ZD82fJDDawKfp5RAKSR8YWWYd3 | GPG/PGP Keys [3072D/F92EDBA4] Hate forced fees ? Use "No Forced TX Fee" Bitcoin Client fork. Now updated to v0.10.1 ! (use carefully !) Should the Bitcoin Foundation be moved to Switzerland ? Vote here print
Pages: [1] 2 3 All
Bitcoin Forum > Bitcoin > Development & Technical Discussion (Moderators: gmaxwell, achow101) > Really Really ultimate blockchain compression: CoinWitness
« previous topic next topic »
Jump to: => Development & Technical Discussion
Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines
go
