Bitcoin Forum
October 19, 2018, 11:05:12 PM *
News: Make sure you are not using versions of Bitcoin Core other than 0.17.0 [Torrent], 0.16.3, 0.15.2, or 0.14.3. More info.
 
  Home Help Search Donate Login Register  
  Show Posts
Pages: « 1 2 [3] 4 5 »
41  Other / Meta / Can moderator names be obfscuated in the HTML? on: October 17, 2013, 05:44:36 PM
It's effectively impossible to search for my old posts on the forum via google because my name is on every thread in the subforums I moderate.
42  Bitcoin / Development & Technical Discussion / Proof of Storage to make distributed resource consumption costly. on: October 13, 2013, 11:28:40 PM
Motivation:
Consider a mutually distrusting decentralized network where each node has some finite capacity, like Bitcoin's P2P network, with 100,000 nodes.

An attacker wants to soak up all the connection capacity of the all the nodes in order to funnel new peers to malicious nodes the attacker controls.  Each node can perform actions to make resource usage costly. For example, each node could reject additional connections from single IPs or subnets, requiring the attacker to have access to more address space (a scarce resource) in order to use up that nodes' capacity. Or they could prioritize peers that present a costly Bitcoin bond (e.g. a Fidelity bond/SIN).

The problem there is that the attackers effectiveness scales with the number of victims— e.g. each IP or bond or whatever lets them use 100k sockets—, since the nodes are mutually distrusting and thus can't collaborate to reject an attacker who makes one connection per IP to every single node in the network.

The network could respond by requiring a scarce resource to connect— e.g. a POW or a Bitcoin fee. But an on-connect fee doesn't really map well to a ongoing resource utilization.  You could require a periodic fee (e.g. intermittent POW), but setting the rates so that it doesn't favor attackers (e.g. an attacker might not mind spending a half bitcoin to attack the whole network, but regular users might not tolerate a 0.0001/per connect cost).

Also, most POW schemes are subject to huge speedups by more efficient implementations. E.g. a FPGA or even GPU implementation will be enormously faster than a java one used in most clients.  A memory hard function may narrow the gap, but common memory hard functions are just as memory hard to validate as they are to produce (though it's possible to do otherwise), and increasing the server's resource utilization is not a great way to address a resource exhaustion attack.

What might be useful is a POW function which maps well to the kind of resource usage that holding a connection represents and is also less vulnerable to speedup for specialized attackers.

One idea that has been suggested for this would be to have a storage hard function: Some function that forces you to store a bunch of data and continue to prove you're still storing it while the connection is up.  Making one that is storage hard for the client but not the server seemed pretty tricky and eluded a number of people for some time. I had a prior idea, which required fully homorphic encryption to create a sequential function with a trap-door property to allow random access... which might have worked but it was so complicated that no one would ever bother with it. Fortunately I've since had a better idea:

A proof of storage system:

Take some fast cryptographically strong pseudorandom function, e.g. like Blake2 or another hash function H().

The server gives the client a random seed and a target size. The client repeatedly applies H() in a tree, e.g.  {Left, Right} = H(seed) and so on, to build up the target size worth of data.  The client takes the final leaves of this tree-structured pseudo-random function and appends their index and sorts the data (or, equivalently, stores it in a binary search tree).

The server then can periodically pick a random index and perform log2(size) hash operations to determine the value at that index and then can challenge the client to provide the corresponding index for that value.

The tree structuring of the function means that you can cheaply lookup the value for a given index,  but looking up the index for a given value requires computing the whole thing (and storing it, if you want to efficiently perform multiple lookups).

(There are some possible optimizations in the client, like common prefix compression, but they're only small optimizations because the function is strongly pseudorandom)

A gigabyte table wouldn't be too insanely burdensome for many kinds of clients, but would require a terabyte for an attacker to use resources on 1000 nodes. Such a scheme could be offered optionally to clients (e.g. if you perform a storage proof you get a preferred connection slot) and so it might provide some value in making some attacks ineffective.
43  Bitcoin / Mining speculation / Whos paying for the DOS attacks? on: October 12, 2013, 01:16:14 AM
A lot of pools have been DDOSed lately, including ones like Bitparking which aren't even that big.

Any speculation as to whats funding these attacks?
44  Bitcoin / Hardware / KNC, 100% of their hashing is currently going into their own pocket. on: September 30, 2013, 10:57:14 PM
I guess I feel a bit left out of all the trolling—

KNC is now mining on their hardware, while customers wait for it to ship:

http://eligius.st/~wizkid057/newstats/userstats.php/17Czc8RVL3FU5T2MLx2zLbRnpfBNgH9vFo

This is, as far as I know, 100% of the KNC hashrate in existence. Pedantically speaking, it means that KNC is violating their 5% commitment.

Testing doesn't involve using the production network. Production mining is unlikely to test finding blocks— whereas testnet, or replays of past found blocks are more complete tests.  Mining on the mainnet increases the difficulty and takes income from customers who are waiting on units that will be late.  Every bit of earlier mining is worth large amounts of future mining due to expected growth.

I do not understand why miners keep funding mining hardware companies that mine in competition with their own customers.
45  Bitcoin / Development & Technical Discussion / Salvaging refund protocols from malleability attacks with P2SH on: September 26, 2013, 06:31:15 PM
In the fair coin toss thread I pointed out that protocols which depend on precomputed refunds to prevent holdup risk are currently unsafe in Bitcoin because of transaction malleability.  Turns out they can be partially rescued even before we fix malleability— this is good news because completely fixing malleability will likely take a long time.

This applies to protocols like this:

(1) Alice wants to put 1 BTC into a 2 of 2 Alice + Bob escrow,  but is concerned that Bob might try to extort her by refusing to sign according to their prior agreements.

(2) Alice writes a transaction paying to 2of2 Alice,Bob.

(3) Before announcing this transaction Alice also writes a refund transaction, sending that 1 BTC back to Alice, with a lock time sufficiently far in the future.

(4) Alice asks Bob to sign the refund transaction without ever giving bob the escrow payment. Bob signs it.

(5) Alice then announces the escrow payment.  Confident that if all else fails she can get her funds back later using the refund.

The attack is this:

After (5) bob grabs the escrow payment off then network and mutates the signature to produce an equivalent transaction with a different transaction id. E.g. he replaces the signature (r,s) with (r,s+order).  He then gets lucky or pays a miner to mine his instead.

Now alice's refund is no good and bob is free to extort her if she ever wants her 1 BTC back.

But P2SH can save the day:

We change the protocol so that the escrow payment is to P2SH(2 of 2 Alice2, Bob2) and Alice2 and Bob2 are new keys that they've never used elsewhere and Bob does not know Alice2.

Alice computes the refund but instead of telling bob the refund transactions, she tells Bob only the hash value she wants signed with Bob2.

When Alice announces the payment into the escrow, Bob cannot identify it— unless its the only P2SH transaction of the expected value— and so he would have to mutate every possible transaction in order to get a mutant mined instead. This would be much harder/more costly (at least if P2SH were widely used).

After the escrow payment is confirmed Alice can show it to Bob along with the refund, and so Bob is also confident that the protocol has been followed faithfully.
46  Bitcoin / Development & Technical Discussion / Bag of keys vs BIP32 on: September 25, 2013, 10:48:28 PM
My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets.  The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse.
It doesn't. This is a spurious claim. (and in Bitcoin-QT we would normally use the type-1 'private' derivation, for primary addresses)
47  Other / Meta / "Watching" posts, no longer needed can we kill them? on: September 17, 2013, 02:21:41 AM
Would it be really awful to regexp filter posts for something like^\w*[Ww]atching\.?\w*$ and deny the post and tell the user about the watchlist feature?
48  Other / Meta / Ads on backbutton on: September 16, 2013, 06:16:12 AM
Sometimes I click away and then only notice the ad "wait! what was that?"... it would be kinda nice if they were stable on the back button press... maybe only stable within a few minutes would be fine, and probably not lower impressions substantially.

Or is there some page that shows everything in rotation that I can browse through?
49  Bitcoin / Development & Technical Discussion / All Bitcoind / Bitcoin-qt nodes failing to come up. Workaround inside! on: September 09, 2013, 09:35:02 AM
Due to a bug introduced in Bitcoind/-qt introduced in v0.8.0 nodes may fail to come up after restart, reporting:

": *** coin database inconsistencies found"
and/or
"Do you want to rebuild the block database now?"

Reindexing will not solve the problem (so I do not recommend you do so, at it will just waste your time).

You can workaround this issue by adding -checklevel=2 to your command-line arguments or checklevel=2 to your configuration file.

The problem that an inconsistency in the transaction database has been caused by some unusual whos version cannot be represented in the database. This inconsistency is correctly detected by the agressive database sanity-checks on startup.  Because this inconsistency happens to be in a field we currently do not use for anything, it is safe to ignore it for now. Lowering the checklevel skips these and other checks and allows the node to proceed as usual.

The issue may resolve itself within another 200 blocks or so if no more of the trigger transactions are added to the blockchain after the triggering block falls out of the window used for consistency checking, but because it could easily happen again a longer term fix is required and has been submitted for review.

UPDATE: 0.8.5 is now out and fixes this issue.

Walkthrough in OSX:
Open a terminal and type
open /Applications/Bitcoin-Qt.app --args -checklevel=2

Walkthrough in Windows:
In Windows, locate the file bitcoin-qt.exe
Usually is to be found in C:\Program Files (x86)\Bitcoin\ (on 64 bit version) or C:\Program Files\Bitcoin\

Right click on the file bitcoin-qt.exe  and select Create Shortcut. On the new file that appeared (bitcoin-qt.exe - Shortcut or bitcoin-qt.lnk) right click and select Properties.
add to Target line
-checklevel=2

as in this picture

http://i.imgur.com/8P1rnRA.png

Then click Apply, then execute.
50  Bitcoin / Bitcoin Technical Support / All Bitcoind / Bitcoin-qt nodes failing to come up. Workaround inside! on: September 09, 2013, 09:33:47 AM
Due to a bug introduced in Bitcoind/-qt introduced in v0.8.0 nodes may fail to come up after restart, reporting:

": *** coin database inconsistencies found"
and/or
"Do you want to rebuild the block database now?"

Reindexing will not solve the problem (so I do not recommend you do so, at it will just waste your time).

You can workaround this issue by adding -checklevel=2 to your command-line arguments or checklevel=2 to your configuration file.

The problem that an inconsistency in the transaction database has been caused by some unusual whos version cannot be represented in the database. This inconsistency is correctly detected by the agressive database sanity-checks on startup.  Because this inconsistency happens to be in a field we currently do not use for anything, it is safe to ignore it for now. Lowering the checklevel skips these and other checks and allows the node to proceed as usual.

The issue may resolve itself within another 200 blocks or so if no more of the trigger transactions are added to the blockchain after the triggering block falls out of the window used for consistency checking, but because it could easily happen again a longer term fix is required and has been submitted for review.

UPDATE: 0.8.5 is now out and fixes this issue.


Walkthrough in OSX:
Open a terminal and type
open /Applications/Bitcoin-Qt.app --args -checklevel=2

Walkthrough in Windows:

In Windows, locate the file bitcoin-qt.exe
Usually is to be found in C:\Program Files (x86)\Bitcoin\ (on 64 bit version) or C:\Program Files\Bitcoin\

Right click on the file bitcoin-qt.exe  and select Create Shortcut. On the new file that appeared (bitcoin-qt.exe - Shortcut or bitcoin-qt.lnk) right click and select Properties.
add to Target line
-checklevel=2

as in this picture

http://i.imgur.com/8P1rnRA.png

Then click Apply, then execute.

51  Bitcoin / Development & Technical Discussion / [Semi-OT] Using tree-secrets to reduce bandwidth in cut-and-choose on: August 30, 2013, 08:32:46 AM
[Just a random OT cryptographic though, which I thought I'd write down before I forget it.]

Bob would like to have some Alice provide him with a randomly permuted deck of cards which is encrypted with secrets unknown to him. He doesn't trust Alice to perform this task faithfully. They can use this protocol:

First, Alice selects a secret value. Alice then expands that secret value into two secret values using H(Secret|1) and H(Secret|2), where H is some cryptographic hash. Alice repeats this process recursively, producing a tree of secret values until she has a final set of— say— 65536 secret values.

Alice then computes a tree commitment over these 65536 secret values hashing them up in pairs to form a hash tree root.

Alice then commits to this root by telling it to Bob.

Bob then picks a long random number and tells it to Alice.

Alice generates 65536 ordered decks of cards and proceeds to encrypt them using the first half of each of her 65536 secret values.

Alice then hashes the second half of the secret value with Bob's random number and uses the result to drive a PRNG to fairly shuffle the decks.

Alice then computes another tree commitment, this time over the encrypted permuted decks, and gives the result to Bob.

Bob then picks 1 deck to use and 65535 out of the 65536 decks for Alice to decrypt reveal to him.  Alice the considers the tree of secret values and sends the minimum number of secrets needed for Bob to recover all the secrets except the one for the non-revealed deck: this will be no more than log2(n)=16 values.

Alice also sends the non-revealed encrypted deck.

Bob can now repeat Alice's computation and recompute the root be and confident that the deck he has is good (with security related to the number of decks, p>=65555/65536 of being caught for this example).

The use of the tree structured CSPRNG in this protocol to generate the secrets reduces sending 65536 decks down to sending 16 secret values.

I originally had the idea of using tree structured secrets when thinking about ways to make lamport signatures smaller. The compression in the case of a lamport signature is not very great because the value being signed is a random hash (so it only reduces the average size by 1/3rd or something like that).  In a protocol like this where all but one secret is revealed the proof is incredibly sparse and the compression is tremendous.

If you replace decks of cards in this toy example with ballots in a homomorphic reencryption mixer used for secure voting for a less silly example of how this can be used. Or, for that matter, as a mechanism to securely shuffle transaction data to improve privacy for Bitcoin users.

For lamport signatures in Bitcoin we could further compress signatures by moving everything but the signature root out of the block then using the hash of the block as our validator's randomness to deterministically pick small subsets of the proofs to include with the block, which we decrease in size as the block becomes further buried... as the computational cost of mining prevents an unfaithful signer from rebinding a signature by continually retrying. ... and this could be accomplished in a single block, rather than needing a space wasting two stage commitment that a guy fawkes signature normally requires, since the full uncompressed proof could be sent to the miners.

This is a tremendous reduction in the bandwidth needed for reasonable security levels for cut-and-choose protocols for proofs of faithfulness in these environments. (Other methods may be smaller and easier to compute, but this requires smaller amounts of fancy math which is beneficial if trust requires your users to understand the protocol).
52  Bitcoin / Development & Technical Discussion / SCIP POW on: August 28, 2013, 06:00:57 PM
Split from the CoinWitness

(And as said we've not talked about SCIP-based
productive proof-of-work yet...)
I don't think this is very interesting, beyond aligning the POW to some other processing which is also useful to Bitcoin. Our proof of work is already productive: It secures Bitcoin. I am currently shaking my fist at your comment promoting the misunderstanding that our work isn't useful.

POW is generally the same up to some constant factors. It all provably expends energy in order to force the miners to choose a unique history to support instead of greedily supporting multiple chain-heads.

Having secondary uses of the work is not obvious adventitious for the system: It may dilute the motivation to participate honestly, if you try to mine on a fork you would at least still conserve the value of this other work, instead of wasting your effort entirely.

As far as using SCIP for this, you're talking about a prover overhead of thousands of times slowdown. This is unlikely to keep your useful work useful. Also, because of the non-determinstic input necessary in any SCIP like system which is either succinct proofs or zero-knoweldge almost certainly means that a single program execution run can be fuzzed into an infinite number of POW hashes, so even using SCIP evaluation of your function can't guarantee non-trivial amounts of your desired work is getting done.

If you wan to wax philosophic about alternative POW, ones that create proofs that the miner isn't just some blind remote computing service and actually knows what they're validating (e.g. memory hard proofs over UTXO queries) are probably more interesting than arbitrary functions.
53  Bitcoin / Development & Technical Discussion / Transaction cut-through on: August 26, 2013, 10:17:19 PM
As an aside from the CoinJoin discussion, it occurred to me that another transaction size optimization is possible with CoinJoin like transactions.

Say there is a collection of related unconfirmed transactions:
(u signifies an unconfirmed output)


             / uI     
A -> uB -> uH  - uJ
       /
     C

D -> uE -\
          uK -> uL       
F -> uG -/


The authors of the earliest unconfirmed transactions could write replacements for their transactions:


A->ul/uj
    /   
   C
 D   
  \   
F->uL 


This transformation is lossless with respect to the final coin ownership, but the intermediate transactions were cut-through. This works even if the original coin ending up in the final outputs came from multiple parties, as they can coinjoin to preserve the final outcome.

Because the replacements are atomic and consume the original inputs this transformation is safe, assuming people in the middle can handle any accounting complications that arise. (E.g. figuring out that their payment really was completed). So you'd want to have a way of signaling "I permit you to conflict this transaction with one that pays its children, if you can figure out how".

Nlocktime could be set in the mild future in order to create time for these kinds of arrangements to be found, and if blocks are found to fast— no harm, the cutthrough doesn't have to happen all the time.

Because people don't currently spend unconfirmed inputs I expect this wouldn't get much compression now, but in the future it might have quite an impact.
54  Bitcoin / Hardware / Do we want to continue to allow various vendor hate in here? on: August 26, 2013, 01:53:19 AM
The forum is overrun with the hate of the day with various "hardware"(/vaporware) vendors, it has become hard to discuss anything else. Many of the participants are behaving like animals.

I'm sensitive to the risk of suppressing complaints. There have been many scam hardware "vendors" of various degrees. People should be able to communicate about the risks, seek recourse, etc.   At the same time, these complaints have reached an intensity where they are self defeating.  If you tell me vendor X is a scam I don't know if its because they are or because you're crazy, because you're a shill for another vendor, because you're a shill for them trying to make the complainers look crazy, if you're a miner trying to scare people out of mining, etc.  As a warning this information is no longer very helpful.

I have multiple people I know (and have met in person and know not to be socks) begging me to do something about the sad state of this subforum.  But I'm at a loss... how do we defeat troll culture when it's taking the form of "concern troll" about concerns we should be careful to preserve? And how can we do it without making me and miningbuddy censors who have to vet every single post?

Does anyone have any great ideas?
55  Bitcoin / Development & Technical Discussion / CoinJoin: Bitcoin privacy for the real world on: August 22, 2013, 02:32:31 AM
Bitcoin is often promoted as a tool for privacy but the only privacy that exists in Bitcoin comes from pseudonymous addresses which are fragile and easily compromised through reuse, "taint" analysis, tracking payments, IP address monitoring nodes, web-spidering, and many other mechanisms. Once broken this privacy is difficult and sometimes costly to recover.

Traditional banking provides a fair amount of privacy by default. Your inlaws don't see that you're buying birth control that deprives them of grand children, your employer doesn't learn about the non-profits you support with money from your paycheck, and thieves don't see your latest purchases or how wealthy you are to help them target and scam you. Poor privacy in Bitcoin can be a major practical disadvantage for both individuals and businesses.

Even when a user ends address reuse by switching to BIP 32 address chains, they still have privacy loss from their old coins and the joining of past payments when they make larger transactions.

Privacy errors can also create externalized costs: You might have good practices but when you trade with people who don't (say ones using "green addresses") you and everyone you trade with loses some privacy.  A loss of privacy also presents a grave systemic risk for Bitcoin:  If degraded privacy allows people to assemble centralized lists of good and bad coins you may find Bitcoin's fungibility destroyed when your honestly accepted coin is later not honored by others, and its decentralization along with it when people feel forced to enforce popular blacklists on their own coin.

As I write this people with unknown motivations are raining down tiny little payments on old addresses, presumably in an effort to get wallets to consume them and create evidence of common address ownership.

I think this must be improved, urgently.

This message describes a transaction style Bitcoin users can use to dramatically improve their privacy which I've been calling CoinJoin. It involves no changes to the Bitcoin protocol and has already seen some very limited use spanning back a couple of years now but it seems to not be widely understood.

I first publicly described this transaction style in a whimsically-named thread— "I taint rich!"— where I focused on a specific side effect of these transactions, with an expectation that people would see the rest of the implications on their own.

Explicit beats implicit, and even people who understand the idea have had some questions which could use answering. Thus this post.

The idea is very simple, first some quick background:

A Bitcoin transaction consumes one or more inputs and creates one or more outputs with specified values.

Each input is an output from a past transaction. For each input there is a distinct signature (scriptsig) which is created in accordance with the rules specified in the past-output that it is consuming (scriptpubkey).

The Bitcoin system is charged with making sure the signatures are correct, that the inputs exist and are spendable, and that the sum of the output values is less than or equal to the sum of the input values (any excess becomes fees paid to miners for including the transaction).

It is normal for a transaction to spend many inputs in order to get enough value to pay its intended payment, often also creating an additional 'change' output to receive the unspent (and non-fee) excess.

There is no requirement that the scriptpubkeys of the inputs used be the same; i.e., no requirement that they be payments to the same address. And, in fact, when Bitcoin is correctly used with one address per payment, none of them will be the same.

When considering the history of Bitcoin ownership one could look at transactions which spend from multiple distinct scriptpubkeys as co-joining their ownership and make an assumption: How else could the transaction spend from multiple addresses unless a common party controlled those addresses?

In the illustration 'transaction 2' spends coins which were assigned to 1A1 and 1C3. So 1A1 and 1C3 are necessarily the same party?

This assumption is incorrect. Usage in a single transaction does not prove common control (though it's currently pretty suggestive), and this is what makes CoinJoin possible:

The signatures, one per input, inside a transaction are completely independent of each other.  This means that it's possible for Bitcoin users to agree on a set of inputs to spend, and a set of outputs to pay to, and then to individually and separately sign a transaction and later merge their signatures. The transaction is not valid and won't be accepted by the network until all signatures are provided, and no one will sign a transaction which is not to their liking.

To use this to increase privacy, the N users would agree on a uniform output size and provide inputs amounting to at least that size. The transaction would have N outputs of that size and potentially N more change outputs if some of the users provided input in excess of the target.  All would sign the transaction, and then the transaction could be transmitted. No risk of theft at any point.

In the illustration 'transaction 2' has inputs from 1A1 and 1C3. Say we beliece 1A1 is an address used for Alice and 1C3 is an address used for Charlie. Which of Alice and Charlie owns which of the 1D and 1E outputs?

The idea can also be used more casually. When you want to make a payment, find someone else who also wants to make a payment and make a joint payment together. Doing so doesn't increase privacy much, but it actually makes your transaction smaller and thus easier on the network (and lower in fees); the extra privacy is a perk.

Such a transaction is externally indistinguishable from a transaction created through conventional use. Because of this, if these transactions become widespread they improve the privacy even of people who do not use them, because no longer will input co-joining be strong evidence of common control.

There are many variations of this idea possible, and all can coexist because the idea requires no changes to the Bitcoin system. Let a thousand flowers bloom: we can have diversity in ways of accomplishing this and learn the best.

FAQ:

Don't you need tor or something to prevent everyone from learning everyone's IP?

Any transaction privacy system that hopes to hide user's addresses should start with some kind of anonymity network. This is no different. Fortunately networks like Tor, I2P, Bitmessage, and Freenet all already exist and could all be used for this. (Freenet would result in rather slow transactions, however)

However, gumming up "taint analysis" and reducing transaction sizes doesn't even require that the users be private from each other. So even without things like tor this would be no worse than regular transactions.

Don't the users learn which inputs match up to which outputs?

In the simplest possible implementation where users meet up on IRC over tor or the like, yes they do. The next simplest implementation is where the users send their input and output information to some meeting point server, and the server creates the transaction and asks people to sign it. The server learns the mapping, but no one else does, and the server still can't steal the coins.

More complicated implementations are possible where even the server doesn't learn the mapping.

E.g. Using chaum blind signatures: The users connect and provide inputs (and change addresses) and a cryptographically-blinded version of the address they want their private coins to go to; the server signs the tokens and returns them. The users anonymously reconnect, unblind their output addresses, and return them to the server. The server can see that all the outputs were signed by it and so all the outputs had to come from valid participants. Later people reconnect and sign.

Similar things can be accomplished with various zero-knowledge proof systems.

Does the totally private version need to have a server at all? What if it gets shut down?

No. The same privacy can be achieved in a decentralized manner where all users act as blind-signing servers. This ends up needing n^2 signatures, and distributed systems are generally a lot harder to create.  I don't know if there is, or ever would be, a reason to bother with a fully distributed version with full privacy, but it's certainly possible.

What about DOS attacks? Can't someone refuse to sign even if the transaction is valid?

Yes, this can be DOS attacked in two different ways: someone can refuse to sign a valid joint transaction, or someone can spend their input out from under the joint transaction before it completes.

However, if all the signatures don't come in within some time limit, or a conflicting transaction is created, you can simply leave the bad parties and try again. With an automated process any retries would be invisible to the user. So the only real risk is a persistent DOS attacker.

In the non-decentralized (or decentralized but non-private to participants) case, gaining some immunity to DOS attackers is easy: if someone fails to sign for an input, you blacklist that input from further rounds. They are then naturally rate-limited by their ability to create more confirmed Bitcoin transactions.

Gaining DOS immunity in a decentralized system is considerably harder, because it's hard to tell which user actually broke the rules. One solution is to have users perform their activity under a zero-knowledge proof system, so you could be confident which user is the cheater and then agree to ignore them.

In all cases you could supplement anti-DOS mechanisms with proof of work, a fidelity bond, or other scarce resource usage. But I suspect that it's better to adapt to actual attacks as they arise, as we don't have to commit to a single security mechanism in advance and for all users. I also believe that bad input exclusion provides enough protection to get started.

Isn't the anonymity set size limited by how many parties you can get in a single transaction?

Not quite. The anonymity set size of a single transaction is limited by the number of parties in it, obviously. And transaction size limits as well as failure (retry) risk mean that really huge joint transactions would not be wise. But because these transactions are cheap, there is no limit to the number of transactions you can cascade.

In particular, if you have can build transactions with m participants per transaction you can create a sequence of m*3 transactions which form a three-stage switching network that permits any of m^2 final outputs to have come from any of m^2 original inputs (e.g. using three stages of 32 transactions with 32 inputs each 1024 users can be joined with a total of 96 transactions).  This allows the anonymity set to be any size, limited only by participation.

In practice I expect most users only want to prevent nosy friends (and thieves) from prying into their financial lives, and to recover some of the privacy they lost due to bad practices like address reuse. These users will likely be happy with only a single pass; other people will just operate opportunistically, while others may work to achieve many passes and big anonymity sets. All can coexist.

How does this compare to zerocoin?

As a crypto and computer science geek I'm super excited by Zerocoin: the technology behind it is fascinating and important. But as a Bitcoin user and developer the promotion of it as the solution to improved privacy disappoints me.

Zerocoin has a number of serious limitations:
  • It uses cutting-edge cryptography which may turn out to be insecure, and which is understood by relatively few people (compared to ECDSA, for example).
  • It produces large (20kbyte) signatures that would bloat the blockchain (or create risk if stuffed in external storage).
  • It requires a trusted party to initiate its accumulator. If that party cheats, they can steal coin. (Perhaps fixable with more cutting-edge crypto.)
  • Validation is very slow (can process about 2tx per second on a fast CPU), which is a major barrier to deployment in Bitcoin as each full node must validate every transaction.
  • The large transactions and slow validation also means costly transactions, which will reduce the anonymity set size and potentially make ZC usage unavailable to random members of the public who are merely casually concerned about their privacy.
  • Uses an accumulator which grows forever and has no pruning. In practice this means we'd need to switch accumulators periodically to reduce the working set size, reducing the anonymity set size. And potentially creating big UTXO bloat problems if the horizon on an accumulator isn't set in advance.

Some of these things may improve significantly with better math and software engineering over time.

But above all: Zerocoin requires a soft-forking change to the Bitcoin protocol, which all full nodes must adopt, which would commit Bitcoin to a particular version of the Zerocoin protocol. This cannot happen fast—probably not within years, especially considering that there is so much potential for further refinement to the algorithm to lower costs. It would be politically contentious, as some developers and Bitcoin businesses are very concerned about being overly associated with "anonymity". Network-wide rule changes are something of a suicide pact: we shouldn't, and don't, take them lightly.

CoinJoin transactions work today, and they've worked since the first day of Bitcoin. They are indistinguishable from normal transactions and thus cannot be blocked or inhibited except to the extent that any other Bitcoin transaction could be blocked.

(As an aside: ZC could potentially be used externally to Bitcoin in a decentralized CoinJoin as a method of mutually blinding the users in a DOS attack resistant way. This would allow ZC to mature under live fire without taking its costs or committing to a specific protocol network-wide.)

The primary argument I can make for ZC over CoinJoin, beyond it stoking my crypto-geek desires, is that it may potentially offer a larger anonymity set.  But with the performance and scaling limits of ZC, and the possibility to construct sorting network transactions with CJ, or just the ability to use hundreds of CJ transactions with the storage and processing required for one ZC transactions, I don't know which would actually produce bigger anonymity sets in practice. E.g. To join 1024 users, just the ZC redemptions would involve 20k * 1024 bytes of  data compared to less than 3% of that for a complete three-stage cascade of 32 32-way joint transactions. Though the ZC anonymity set could more easily cross larger spans of time.

The anonymity sets of CoinJoin transactions could easily be big enough for common users to regain some of their casual privacy and that's what I think is most interesting.

How does this compare to CoinWitness?

CoinWitness is even rocket-sciency than Zerocoin, it also shares many of the weaknesses as a privacy-improver: Novel crypto, computational cost, and the huge point of requiring a soft fork and not being available today. It may have some scaling advantages if it is used as more than just a privacy tool. But it really is overkill for this problem, and won't be available anytime real soon.

Sounds great! Where is it?

Theres the rub: There exist no ready made, easy-to-use software for doing this.  You can make the transactions by hand using bitcoin-qt and the raw transactions API, as we did in that "taint rich" thread, but to make this into a practical reality we need easy-to-use automated tools.

Luke has written up some sketches a protocol which would enable establishing joint transactions over the regular Bitcoin network.

The Bitcoin-qt RPC system provides everything someone needs to write a side-car applet (including the ability to lock txouts to prevent them from being spent out from from under it) that participants in such a system. But the fact that so many users use centralized webwallets today which can spy on them will ultimately limit the userbase for these tools.

Personally, most of my coding brain capacity is spent on other things which are even more important to me. And what I could spare on Bitcoin is spent on more core and security things— if I work on anything wallet related anytime soon it will likely be improving the privacy behavior of coin selection... But moreover:

Anyone who builds this is going to be accused of enabling criminal activity, it doesn't matter if any actual criminals use this or not: Criminal activity sells headlines. Being a Bitcoin core developer already fills my quota for accusations of this kind, especially my quota for risk that I'm not even paid for. Smiley

In reality, real criminals don't need CoinJoin if they have even the slightest clue: They can afford to buy privacy in a way that regular users cannot, it's just a cost of their (often lucrative) business.

Joe-criminal can go out and buy 120% PPS mining to get brand new coins, or run his money through a series of semi-sham high cashflow gambling businesses for a 50% cut, they can afford the cost of seeking out and interfacing with these seedy services... Joe and Jane doe? Their names are up in neon on blockchain.info. It might not seem great to them, but if there a high cost of fixing it they simply won't, because the cost of fixing it is very concrete and the cost or privacy loss is speculative and distant. They might just need to give up bitcoin and switch to something almost totally private: cash... Regular users need efficient and inexpensive privacy if it is to help them at all.

I know that making such a tool doesn't fit into the get-rich-quick mold of many Bitcoin businesses, but the importance is self-apparent and the simplest versions of this don't require very deep technical wizardry. I think the "political" risk of improving people's privacy is a real one that you should carefully consider, but around these parts I see people sticking their names on some rather outrageously risky stuff. I'd hoped the "taint rich" thread would be enough to inspire some community action, but perhaps this will be.

So, instead, I ask you: Where is it?
56  Bitcoin / Development & Technical Discussion / CoinCovenants using SCIP signatures, an amusingly bad idea. on: August 20, 2013, 12:01:55 PM
First go read and understand CoinWitness, it describes an application for using proven computation in scripts, and also provides some background about the provable computation tools which I won't repeat here.

In this message I describe another application for using provable computation (SCIP) as a script replacement, but this one isn't at all serious. It's downright amusingly bad.

A checksig operation in a transaction script logically receives a pubkey, a signature, and a hash of the masked transaction (effectively a hash of the transaction with the scriptsigs removed; all this ignoring sighash flags for the purpose of discussion).

In a world where we have a SCIP-script checksig operator it would work similarly:  It would receive some optional additional public data, a public key (verification key), a signature (proof), and a hash of the masked transaction.   To produce a signature for this system you would run the SCIP-script program corresponding to the verification key inside the SCIP prover, giving it as a public input the hash of the masked transaction and any extra public or non-public inputs. If the program accepts the result is the proof your transaction needs to be considered valid.

Because the hash of the masked transaction itself is part of the public input, the SCIP-script could also require the unhashed masked transaction as a non-public input when it runs. The program could then test any of the non-masked data in the transaction, and only ACCEPT if it likes it.  E.g. it could check the scriptpubkeys against a list or their output values against a range.  It could choose to only sign if the transactions' nlocktime was high or low enough, or any mixture of these options.  Because the inputs (which are themselves transaction hashes) are covered under the hash,  the script could go further and require that you provide the input transactions— and it could apply whatever tests it wants on the inputs— potentially following them all the way back to an enormous number of coinbase transactions, imposing any computable rules it likes along the way.   If you can't satisfy the rules, you can't spend the coin.

A particular sort of rule could take the form of requiring any output scriptpubkey to be of the form THIS_VALIDATION_KEY && {whatever rules you want} and by doing so you have effectively created a coin which is forever subject to a covenant which will run with the coin and forever constrain the use of it and its descendants degrading and its fungibility.

(Actually accomplishing this requires a bit of a hack: a SCIP program can't have its own validation key built into it, as that would be circular. But that is no fundamental limit here: the script can go read it out of the scriptpubkey of the input transaction that is being spent we can trust that its the right one because if it isn't transaction will be invalid even though the proof accepted).

Any attempt to think of why someone might want to do this leaves me screaming in horror— Which you should expect as this is the robotic equivalent of a home owners association.

(E.g.  In a fit of tonal advocacy, Luke-Jr could start stamping coins with a covenant that only allows or makes their user pay higher txn fees unless the txout amounts were round tonal numbers.)

A more serious point is that this kind of tool makes it rather difficult to intentionally exclude functionality from script— any data under the signature in a cryptographically strong way, even indirectly like all the data in prior transactions, its subject to testing by the script.

What horrifying ways can you imagine covenants being used? Tongue
57  Bitcoin / Development & Technical Discussion / Really Really ultimate blockchain compression: CoinWitness on: August 19, 2013, 05:53:55 AM
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.

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

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

58  Bitcoin / Hardware / Referral link spam on: August 14, 2013, 04:34:44 AM
Posters: Please don't create threads just to promote your referral links. It's spammy BS and if everyone did it the forum would be useless... rewarding just the few of you selfish enough to behave in a way that harms the forum is not in our interest.

The form has official ads, and the social norms here seem to tolerate advertising in signatures— or limited referral links in the context of places where you would naturally provide the same link absent the referral incentive. Creating a bunch of new threads purely to direct people to referral links clearly harms the signal to noise ratio here.

Vendors: Please don't create referral programs which are highly vulnerable to abuse, and to the extent that your programs can be abused by spamming please police yourselves by de-crediting users who promote through outright spamming.  If you don't do this you may find your services completely blacklisted from places where they've become a nuisance.  You can't claim zero responsibility for the foreseeable abusive behavior your programs encourage.

59  Economy / Service Discussion / Lavabit— A best case outcome for blockchain.info? on: August 09, 2013, 01:17:54 AM
Lavabit was a web-based email service which kept all email encrypted a key protected by the user's password to how mywallet works. Today lavabit shut down without any advance notice. Details are scarce, but they are claiming that they were being ordered by the us government to do things which they considered wrong. Many believe they were ordered to intercept users (such as Edward Snowden) passwords, or send specific users zero-day exploit code, and chose to shut down rather than comply with the order.

Many other services would and have just simply captured the passwords and gone on with life,  many many more are not designed in such a way that they could even resist such an order. The operators of lavabit appear to have taken a remarkably principled position.

Eventually it seems likely to be that hosted wallet services like blockchain.info's my wallet will encounter a similar interaction with the relevant authorities intent on seizing some funds.

It's possible that they could just comply completely, perhaps they could shutdown like lavabit rather than attempt to betray their user's trust, or maybe there is some other possibility.

What would be a best case outcome there?


Edit:And now silentmail has preemptively shut down rather than be placed in the same position.
60  Bitcoin / Bitcoin Discussion / OTR chat encryption project is taking Bitcoin donations! on: July 25, 2013, 01:27:35 AM
 http://www.cypherpunks.ca/otr/donate.php

OTR is one of the best pieces of encryption technology available today.

It does all the right stuff from a security perspective but more importantly it does things in a way which is deeply thoughtful about the user factors.  While it's fairly difficult to use GPG/PGP and thus really hard to get people to use them: OTR works pretty transparently and in doing so turns otherwise treacherous commercial chat networks into ones that are a little less able to betray their users.

OTR opportunistically encrypts whenever it can (my minor contribution to the protocol, years ago), and allows strong authentication when the users are willing and able. For authentication you can do the boring fingerprint comparison stuff, or it can use a challenge question based on a zero-knowledge-proof:  The math is complicated but the result is security that works for how regular people usually talk, no dorky key signing parties required. It certainly doesn't depend on any of the horrible hole ridden and difficult to use PKI CA infrastructure. If you're not up for authentication you still get crypto which kills passive snoops dead.

Unlike most prior chat encryption systems when authenticated it operates without actually cryptographically signing your messages and creating proof of what you said that a treacherous counter-party could show to others against your wishes. Non-repudiation is very good, but you should only have it when you want it and know that it's there. OTR tries to minimize surprises.

In spite of all the great things that OTR already does there is still a lot left that could be done:  Support for additional chat systems and clients, further attack hardned software, additional authentication options, multiparty chat, encrypted file / multimedia transmission, formally specifying the protocol in an internet draft, and many other things.  While there are many commercial companies out there creating snake-oil closed source crypto— stuff that inevitability turns out insecure— are now exploiting the NSA/prism stuff to make a pretty penny on the various app stores, OTR has continued trucking along delivering the real deal to everyone at no cost while advancing the art in both cryptography and cryptographic usability.

I think in general the Bitcoin community can learn a lot from how OTR uses technology to serve human interests without compromising on the security— something we should always strive for in the tools and infrastructure we build. Without secure communications our whole economy is more fragile: Bitcoin depends on information being easy to spread and hard to stifle.

I've donated: OTR is something that many of us have reason to support.
Pages: « 1 2 [3] 4 5 »
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!