You can see someone attempting this right now with "mastercoin" which is apparently supposed to be an alt-coin which forces Bitcoin nodes to store its data by stuffing them in perpetually non-redeemable utxo... so it even goes a step beyond undermining the rules with an alternative system, it moots pruning in Bitcoin and would eventually— if successful— make it much harder to run a validating node.

Please stop!

You are creating enormous amounts of  nonredeemable UTXO.  This kind of usage undermines the scalability of Bitcoin because you are pushing data storage into the UTXO set and not merely into the transaction history. The UTXO set must be rapidly available for validation and can not be pruned unlike the rest of the blockchain.  Currently pruning yields 50:1 compression (and improving) of the space required to run a full node. The addition of never-redeemable outputs undermines that.

I am not following you here.

You use the technique there to generate the deck.

You generate a hash tree over the resulting cards and publish the root for all to see. You give the players their hands and the hashtree fragments. Any player can now prove to anyone else that their card was in the deck at whatever position it was at.

At the end of the came the dealer can reveal his secret and thus the whole deck, and everyone can verify the root.

If you actually need to _never_ reveal some of the cards (sorry, I know nothing about poker—) then you can encrypt each card before you shuffle the deck and also commit to a hash of the encrypted cards. You then do the same procedure, giving the users the decryption key for each card as you hand it to them. At the end the shuffle is proven faithful, and the identity of all revealed cards is known.  (though perhaps your deck contained fake cards in the set that were unrevealed— but thats a consequence of not revealing them. Fixing that requires you go into fancypants math)

Yes, I didn't give them their shuffle, and I later warned them that that was biased. I think they fixed it eventually. Its trivial to fix in any case.

All you should do is read ceil(log2(remaining cards)) random bits (uh, please with an integer implementation of the uprounding log2) and if the resulting index is too high throw out the number and retry.

Also send him your debug.log (likewise, reveals your IP, and may also reveal transactions which you are a party to, if you have a wallet on that node that you've been using)

A couple minutes ago Phantomcircuit directed me to this writeup, which I'd not see before. It's a great proposal and does better from a privacy perspective of my earlier suggestions of ZC + TOR or Cham+Tor.  And it's not especially new either! here we see the problem with just pumping out theory and not implementations: The activity in this thread is already more practically useful than that year old blog post.

In any case, they propose using multi-party computation to SORT a list of pubkeys provided by the participants.  This accomplishes two things:  Blinds the participants to whos keys is whos but makes sure that everyone knows that the pubkeys all came from the participants.  Using chaum accomplishes only the latter but would depend on using tor (or the like) to prevent participants from learning the mapping.  This is somewhat non-ideal if we want to be super paranoid about such things since tor is very vulnerable to timing analysis.

I'd looked into using MPC for this before but I was overthinking it and expecting the MPC to do too much and it didn't seem practical. It did not occur to me that we only needed a _sort_ to hide the correspondence.

So to make this real you need a multi-party computation system that can implement a sort:   Here you go: http://viff.dk/   to use it build it then run

./apps/generate-config-files.py 127.0.0.1:10001 127.0.0.1:10002 127.0.0.1:10003
then
./apps/sort.py  --no-ssl player-1.ini
./apps/sort.py  --no-ssl player-2.ini
./apps/sort.py  --no-ssl player-3.ini

(It appears to be a bit python bitrotted and doesn't actually work for me ATM)

The sort.py script is setup for three players providing inputs, and they pick random values to sort (with an array of size .. all of this can easily be adjusted.

The protocol requires log2^2(N) communications between all the participants. You'd have every player provide a pubkey, at the end they all get a sorted list and learn nothing about who sent what.

Downsides:

* Thats a boatload of communication for a lot of participants, especially since you'd still run this over tor to hide the inputting parties IPs. This means that you probably have to have all parties online and communicating in realtime... if people are only logging on once per day, an 8 party operation would take 10 days I think. (log2^2(N))

* The MPC implementation in viff only has security against passive attackers e.g. they might snoop but they follow the protocol.  VIFF has some code for a different kind of MPC which is secure against active attackers but I've never been able to get it to work before (in particular, it doesn't seem to have a comparison operator... which.. uh. sort really needs).

* Also, this is all expensive enough that it's probably not helpful for preventing DOS even if the activity model does let you detect which party is misbehaving.

Upside: no depending on TOR for hiding the mapping between parties, and stronger fundamental security than tor, to keep players identity secret from each other.

(Also downside— will take work to go implement this in an actual system )

I intended it as "make a proposal, do work, receive some baconreward". Obviously, if people want to appear with fully formed solutions they should get rewards too.  My main criteria is that work done be actually usable by someone for something, we're awash with ideas around here (myself included): so show me the code.  I am very much in support of the spirit here of just getting some stuff published and getting people trying it... this means both simple tools that don't implement a more complete vision, and more powerful ones too. The whole idea is to flow some funds from people who want to see this exist to people who are working on making it exist and everyone leaving happy, and so I think exposing a lot of really exacting procedural requirements isn't a grand idea.  (Also, it's likely the case that I didn't foresee all the things that needed to be done in my post. Please: solve problems I didn't know existed too.)

(And yes, I need to pay out some bounties to the work done by people so far ... I'm afraid that it's probably going to wait until this weekend before I can try out the tools and talk to the other signers! (and feedback from donors and other people who've tried the stuff out!))

Once a transaction is in the aux block all of its children must forevermore be in the aux block.

This was also how I thought we could implement a new transaction syntax (one that makes the scriptsigs prunable) and switch to using hash-sum trees to make the coinbase value provable: move all txn into a separate tree eventually, and eventually require that the only txn in a block be the coinbase.

The downside is that until the transition is complete you have degraded fungibility with two kinds of Bitcoins.

Bcp19, you should be ashamed of yourself.  I would remove your posts but D&T has already locked and started a self-moderated thread, leaving your posts makes the necessity of it clear.

If you are on a restricted network you should run Bitcoin over tor, and tor can happily work with these restrictions.

It depends on how it is implemented. The simplest ways of implementing it make either a meeting point "server" learn the correspondence, or all the participating users.  More complicated ways result in no one knowing. (I sketched out at a very high level in the other thread two distinct ways on the more complicated ends of the spectrum, but there are many possible ways with distinct trade-offs in security, implementation complexity, resistance to denial of service attack, etc)

No. The whole transaction  ("this group of things to that group of things") is the intention the transaction coveys, and it cannot be separated when using sighash all (the default sighash type).  Thats the point. There are possible side channels— how different clients encode signatures, for example, but the transaction style itself doesn't leak any information about the mapping when used correctly.

There is no fundamental requirement in the Bitcoin protocol for them to be the same, but if they are different sizes you likely leak some information about the input to output mapping: If I put in 5 and you put in 50... and addr X gets out 50 and Y gets out 5 ... how do you think they map?

See the thread on the general idea for my thoughts on the general question.

See also the BIP32.5 thread on Bitcoin development. It would be preferable if it also only produced even signatures, so that the signatures produced won't have to be postprocessed to remove the malleability attacks.

PLEASE USE DERANDOMIZED DSA.  There is absolutely no reason to have MORE wallet leaks. DSA signing information leaks are completely preventable.

If trezor uses randomized DSA its users will have no way of knowing that their device isn't just slowly leaking out an encrypted copy of their master root key a bit or two at a time in their signatures.

Oh woe woe is me:  I bought batch 1 avalon and paid about 110 BTC for only 60GH/s... if only I'd waited and bought asicminer blades! I could have saved 80%! ... and lost a lot of coin.

Pricing this out in Bitcoin is misguided. In a counterfactual world the BTC exchange rate could have tanked over the same time.  If you want to speculate on BTC, fine enough, but thats no reason to slam BFL— there are plenty of real reasons for that.

Split from the CoinWitness

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.

This is a misrepresentation of what the feature is for in Bitcoin.  Primarily, it prevents a newly installed node which is being subject to a isolation attack (e.g. by an ISP) from putting it on a fantasy network, it also inhibits a bunch of DOS attacks which could be better solved other ways but were more easily solved with the checkpoints way in the short term. It also triggers some performance optimizations, which, likewise could be done other ways. Bitcoin checkpoints are never placed with a couple thousand blocks of the tip, and thus are not useful against your typical double spend concerns at all.

In more recent times we've been talking about drastically reducing the static checkpoints role in Bitcoin and very likely will in the next major release. We may even remove them completely.

In Bitcoin we would _never_ deploy something that looked liked this advanced checkpointing feature, as doing so would be abandoning our security model. The user community wouldn't accept it, and if by some weird chance they did no sane developer would accept access to the keys lest their lives be put in danger.

Like many other "ways of preventing '51% attacks'" broadcast checkpointing prevents the attack by making the network constantly under the control of a perpetual "ultimate majority" "attacker", though hopefully a benevolent one. ... but thats a return to the old trusted model that runs under classical payment networks like visa... and if you're willing to trust you can construct systems far more efficient than blockchains.

Of course, things are— no doubt— different in the land of crazy altcoins.  Realsolid did a lot worse things in the day with users happily accepting it... so I do not say this to judge— this may be a good, even necessary step considering the environment that you're in... I'd just prefer that you not misrepresent Bitcoin while explaining your feature here.

(As an aside: I was one of the earliest miners on PPC and mined about 250k coins. I stopped when one of the broadcast checkpoints reorged out some of my blocks)

Uh. Does someone have a bug to report for a tool from this thread?  (If you want you can report to me in pgp email anonymously.)

Does the cryprographic protocol I made for btcjack21 accomplish what you want?

You can enhance it in the game by doing the split and sort of the deck, and then announcing a hashtree over the cards, allowing you to prove to each player that the card you gave to them was the right one, and then at the end you can also prove that you shuffled the deck fairly. ... though it's probably just adequate to prove the deck at the end.

Versions without a house doing the cards aren't too hard..., you just need users to encrypt and shuffle the deck, and use cut-and-choose to prove that their actions were faithful... but no need to go that route if you have a house.

But you could have non-random decks, including ones stacked in particular players favors (e.g. the Nth player, and then you make sure your compatriots play that role). I strongly suggest the protocol I linked above.

There is an entirely subfield of cryptography that deals with zero-knoweldge signatures of knowledge which are mathematical systems for producing convincing evidence that a person with knowledge of some specific secret data, matching a criteria set by an arbitrary computable function, signed a given public value without revealing anything about the secret data at all, except that the person knew it.

Though without a more concrete description of what you're actually trying to accomplish I can't say what else might meet the criteria you're going for... for many things involving a finite number of people set up in advance who can all interact there are other options beyond signatures of knowledge, including interactive proof protocols and secure group computing.

For some kinds of proof systems can be easily and understably constructed from nothing more than authenticated data-structures, or simple elliptic curve homomorphism.  I'd be happy to tell you exactly how to do so with one of these simple techniques if what you want is possible, but you've managed to write a lot of text without actually communicating to me what you're trying to accomplish.

Going from what you've said, I can't determine where this procedure fails you: Alice picks a random value, publishes the hash.  Bob picks a random value, publishes the hash. Done.

Obviously you want to accomplish more/different than that, but I can't tell what.

I believe that proving something known to one party is _unknown_ to another party, when they potentially could have cooperated is impossible (until you upload humans and can subject their minds to mathematical proofs).