Bitcoin Forum
October 22, 2017, 05:20:43 AM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3]  All
  Print  
Author Topic: Really Really ultimate blockchain compression: CoinWitness  (Read 32979 times)
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
September 01, 2013, 05:31:41 PM
 #41

And I'd appreciate it if you'd go edit your post which claims that I was arguing otherwise there.

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

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
1508649643
Hero Member
*
Offline Offline

Posts: 1508649643

View Profile Personal Message (Offline)

Ignore
1508649643
Reply with quote  #2

1508649643
Report to moderator
1508649643
Hero Member
*
Offline Offline

Posts: 1508649643

View Profile Personal Message (Offline)

Ignore
1508649643
Reply with quote  #2

1508649643
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508649643
Hero Member
*
Offline Offline

Posts: 1508649643

View Profile Personal Message (Offline)

Ignore
1508649643
Reply with quote  #2

1508649643
Report to moderator
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
September 01, 2013, 09:33:53 PM
 #42

This will allow any previous owners to DoS the latest owner by forcing him to redeem the coin on the blockchain.
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).

Bitcoin will not be compromised
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
September 02, 2013, 02:01:53 AM
 #43

This will allow any previous owners to DoS the latest owner by forcing him to redeem the coin on the blockchain.
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).

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

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
September 02, 2013, 02:11:06 AM
 #44

Sorry for the confusion. This comment is referring to the timeout mechanism for oracle-based system.
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."

Bitcoin will not be compromised
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
September 13, 2013, 05:46:53 AM
 #45

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 double-spent.

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.


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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
September 13, 2013, 06:10:03 AM
 #46

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.

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.

Bitcoin will not be compromised
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
September 14, 2013, 05:57:47 PM
 #47

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:
Code:
OP_DUP OP_HASH160 <pubkey hash> OP_EQUALVERIFY OP_CHECKSIG <HMR> OP_DROP

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
jtimon
Legendary
*
Offline Offline

Activity: 1372


View Profile WWW
September 15, 2013, 03:23:42 AM
 #48

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.

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
September 15, 2013, 03:32:52 AM
 #49

So I don't see what exactly the merchant gains from waiting for block confirmations instead of just quering the oracle directly and instantly.
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.

Quote
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?
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.

Quote
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.
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".

Bitcoin will not be compromised
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
September 15, 2013, 05:47:17 AM
 #50

So I don't see what exactly the merchant gains from waiting for block confirmations instead of just quering the oracle directly and instantly.
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.

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
jtimon
Legendary
*
Offline Offline

Activity: 1372


View Profile WWW
September 15, 2013, 02:12:39 PM
 #51

]
I think he's referring to my lately proposed system

...the oracle [...] can't trivially rewrite historical timestamps because they are buried in the bitcoin blockchain.

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

Quote
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?
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.

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".

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 double-spent.

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.

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
September 15, 2013, 02:59:30 PM
 #52

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
hashman
Hero Member
*****
Offline Offline

Activity: 915



View Profile
October 29, 2013, 02:21:19 PM
 #53


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).


Thanks for bringing this to our attention Smiley 

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). 


killerstorm
Legendary
*
Offline Offline

Activity: 994



View Profile
December 27, 2013, 12:18:13 PM
 #54

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

Quote
I thought that my understanding of colored coins is more or less complete, but today I found that I had more to learn...

I've been looking through a very naive (and broken) proposal to have Mastercoin in multiple blockchains at once, which prompted me to think:
Is it even possible to do things like that? What is possible?

It's worth noting that I've been thinking about multi-blockchain interactions since 2011, and all potential solutions I'm aware of are quite a bit cumbersome.
(I'm not talking about cross-blockchain trade here, but about representing the same asset in multiple systems at once.)

I'll skip some details for now, the basic idea is that if it is possible to embed a compact cryptographic proofs of off-chain transfer into a colored coin transaction (which colored coin agents will be able to verify when necessary), then it is possible to integrate colored coins with off-chain systems in a consistent, trustless way.

The problem with off-chain transfers is that situations with ambiguity/lack of consensus are possible. But cryptocurrency transactions must be unambiguous. The current solution is to have a trusted party (potentially, some distributed entity, "d.a.c.") to work as an interface between an off-chain transfer system and a blockchain-based cryptocurrency (incl. colored coins).

But as I found today, it's also possible to do it the other way around: embed a reference to proof into colored coin transaction and let participants to verify the proof. There is no longer a need for a trusted party: when reference to a proof is embedded into a transaction, all potential ambiguities are eliminated.

To make it even better, we should re-think how we see colored coins. I think majority of people (at least, non-cryptographers) understand cryptocurrency as a ledger-based consensus: that is, there is a ledger which shows how much money each one has.

But a more general approach is to see it as a system based on proofs...
Say, "Alice has 50 coins" means that Alice is able to prove that she has 50 coins.
"Alice transfers 50 coins to Bob" means that Alice performed an action which now allows Bob to prove that he has 50 coins.

The difference is that we don't need to make sure that we know balance of each account; Alice and Bob are concerned only about their own balances.

Switching to this model would make off-chain transfers I've outlined above feasible in practice. Also it mitigates problems with consensus/hard forks: if we assume that an interactive proof protocol is used when payment is made, it's possible to make sure that hard forks can't result in permanent monetary loss.

Now the only problem which remains is compactness of proofs... I.e. a performance problem. Ultimately it can be addressed through SCIP or other compact proof system, I think.
But at least this framework lets users to choose level of assuredness they are comfortable with.

It's worth noting that it is somewhat similar to Gregory Maxwell's CoinWitness idea:
https://bitcointalk.org/index.php?topic=277389.0

The difference is that in my case neither SCIP nor changes to Bitcoin protocol are required.
So it's feasible to implement it right now, and it's not terribly complex... In terms of complexity, it is what a bunch of undergrad CS students could do.

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).

colored coins proof-of-concept: private currencies, stock/bond p2p exchange

Tips and donations: 16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
February 24, 2014, 02:30:39 AM
 #55

I wonder how this system compares to Pinnochio which has similar capabilities.

   http://research.microsoft.com/apps/pubs/default.aspx?id=180286

However, my understanding is that the performance is significantly better.

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

Quote
Chapter 16 Span Programs

A span program for a function f(x1,...,xn) is presented as a matrix over some field, with the rows labeled by variables xi or their negations !xi (one variable can label many rows). The span program accepts an input assignment if and only if the all-1 vector can be obtained as a linear combination of the rows who labels are satisfied by the input. The size of the span program is the number of rows in the matrix. The span program is monotone if only positive literals are used as labels of the rows, i.e. negated variables are not allowed.

The model appears to be quite strong: classical models for computing boolean functions — like the switching networks or DeMorgan formulas — can be simulated by span programs without any increase in size.

16.1 The model

We describe the model more precisely.
Let F be a field. A span program over F is given by a matrix M over F with its rows labeled by literals x1,...,xn,!x1,...,!xn. For an input a = (a1,...,an) ∈ {0,1}n, let Ma denote the submatrix of M obtained by keeping those rows whose labels are satisfied by a. That is, Ma contains rows labeled by those xi for which ai = 1 and by those !xi for which ai = 0. The program M accepts the input a if the all-ones vector 1 (or any other, fixed in advance, vector) belongs to the span of the rows of Ma. A span program computes a boolean function f if it accepts exactly those inputs a where f(a) = 1. The size of the span program is the number of rows in it.

The number of columns is not counted as part of the size. It is always possible to restrict the matrix of a span program to set of linearly independent columns without changing the function computed by the program, therefore it is not necessary to use more columns than rows. However, it is usually easier to design a span program with a large number of columns, many of which may be linearly dependent.

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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
eldentyrell
Donator
Legendary
*
Offline Offline

Activity: 980


felonious vagrancy, personified


View Profile WWW
March 22, 2014, 06:11:51 PM
 #56

Fair enough. There is ambiguity in what SPV means— e.g. go see what electrum, which does not monitor the network, calls itself or the BitcoinJ clients which get their peers exclusively via DNS.   Can you suggest a better name for "SPV with high risk of network isolation"? Tongue  It would probably be a good name to have.

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.

The printing press heralded the end of the Dark Ages and made the Enlightenment possible, but it took another three centuries before any country managed to put freedom of the press beyond the reach of legislators.  So it may take a while before cryptocurrencies are free of the AML-NSA-KYC surveillance plague.
eldentyrell
Donator
Legendary
*
Offline Offline

Activity: 980


felonious vagrancy, personified


View Profile WWW
March 22, 2014, 06:14:00 PM
 #57


This is really way cool stuff!


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.

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.


cannot, as currently defined, run self-modifying code

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.

The printing press heralded the end of the Dark Ages and made the Enlightenment possible, but it took another three centuries before any country managed to put freedom of the press beyond the reach of legislators.  So it may take a while before cryptocurrencies are free of the AML-NSA-KYC surveillance plague.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 23, 2014, 12:58:06 PM
 #58

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.
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 Smiley.
  • 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).
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=


Bitcoin will not be compromised
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
August 29, 2014, 03:06:16 PM
 #59

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

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
August 29, 2014, 07:32:42 PM
 #60

As people are talking about scalability again, is there any new development in SCIP?
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.

Bitcoin will not be compromised
Pages: « 1 2 [3]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!