0.005BTC
no offense but i bet its awful

There are 8 days left to submit papers to the Bitcoin'17 research workshop!
http://fc17.ifca.ai/bitcoin/cfp.html


This is a peer-reviewed academic workshop that will be held in Malta, next April. I'm posting the call for papers here because many Bitcoin developers are on the program committee (which is who reviews the papers), and many original technical ideas discussed in this particular forum would be on topic and appreciated at this venue (several have been published at this workshop in prior years). Please consider submitting a paper here!

This looks interesting to me, it basically extracts the weird part of segwit, but minus the signature-specific details.

Kanzure points out this looks possibly similar to "aux blocks" https://bitcointalk.org/index.php?topic=283746.0
Do you see a difference?

1. Call for proposals! The Bitcoin Foundation has a quarterly grant program that provides funding for community led projects that promote and improve Bitcoin. In the past few quarters, up to $20,000 has been given out. Previously funded projects have included petertodd's seed server, Coinpunk, Bitnodes.io  and a Bitcoin simulator.
https://bitcoinfoundation.org/about/grant-program/

There are two weeks left to submit a proposal for the next cycle of funding (by Sept 1).

2. Reviewers needed! The proposals received each quarter are reviewed by a committee. The Bitcoin Foundation board ultimately decides on which projects to fund, but they generally go along with the committee's recommendations. This is your chance to help direct some funding for important projects. Last season we had 30 proposals, and we want each proposal to be reviewed by 3 people. We need to recruit a few more committee members. If you're interested in joining, please contact me amiller@bitcoinfoundation.org or post in the foundation forum thread: https://bitcoinfoundation.org/forum/index.php?/forum/34-grants/

Here's my Satoshi conspiracy theory. I don't have any particular evidence to support this, but it's a clever story that gives me great personal pleasure to think about, and no one else has posed it. Of course, Satoshi's identity is totally irrelevant at this point, so I really don't care what the true answer is. I'll be a little disappointed if someone proves this idea *isn't* the case, but, oh well, go ahead. I'll happily collect all the points if this ends up being correct!

1. Wei Dai invented it. B-Money is by far the closest related conceptual work. It has most of the critical parts, such as broadcasting digitally-signed transactions to everyone on the network, who collectively maintain a ledger and transaction history.
http://www.weidai.com/bmoney.txt
http://cypherpunks.venona.com/date/1998/12/msg00194.html
None of Wei Dai's posts ever mentioned the use of proof-of-work puzzles to resolve conflicts and coordinate global consistency. But these techniques were well-known at the time (e.g., Hashcash), just not for this application. Once that missing piece was put in its place, he also came up with the plan to develop and launch it (rather than just write more about it on the mailing list).

2. Ben Laurie wrote the code, but hates the idea. Laurie is a prominent crypto engineer and coder, having written code for OpenSSL and an ecash library called Lucre. He thinks proof-of-work is nonsense though, and would prefer a digital currency system based on a quorum of semi-trusted designated servers.
http://www.links.org/files/decentralised-currencies.pdf

3. Nick Szabo wrote the whitepaper, but this was his only involvement. Szabo has written tons of great essays on this history of currency technology http://szabo.best.vwh.net/ and frequented the cyperpunks mailing list. This explains the text-analysis trail.

This is a really insightful point, and my response to it so far is, at best, sketchy and speculative. This point has been brought up by others including gmaxwell, SDLerner, and zooko.

First of all, suppose that we solve the low-variance problem, and solo individual miners are able to choose whatever sort of risk profile they want, without having to join a pool. Now lower-variance isn't a reason to join a pool or hire a cloud miner.

However, there are still reasons to hire a cloud miner... cloud miners enjoy some economies of scale, and may benefit from vertical integration and custom mining rigs. It may be the case, given this, that cloud mining is inevitable and decentralized proof-of-work is doomed.

I think there's a plausible(ish?) alternate outcome. It's outlined in this post https://bitcointalk.org/index.php?topic=305781.0 but I'll repeat a bit of it here.
- Bitcoin mining is unprofitable, on average. It's so unprofitable, that even vertically-integrated cloud miners are unprofitable or unsustainable.
- Even though it's unprofitable, people are still systematically incentivized to mine, for the same reason that State Lotteries are a big business: in some cases, people actually PREFER a high variance prospect, if there's the *chance* of winning a large jackpot. Bitcoin mining is an occasionally lucky gamble, rather than a reliable profit.

In other words, this is based on a premise that potential miners -- in the future, if not now -- actually have some appetite for variance and luck. Right now there's only one game - the 25btc jackpot. But imagine you can choose a puzzle that has some chance of giving you 0.1 btc, some chance of giving you 1btc, some chance of giving you 10 btc, and so on. Go to any gas station (in the US) and look at the variety of lotto games you can play for inspiration.

If miners choose something with a high-enough-variance component, then they'll be suspicious of a cloud provider that can get away with stealing their "lucky" jackpots, if not their every-day 0.01 btc consolation prizes.

I don't have the tools to really evaluate or justify this hypothesis. For sure it's outside the scope of this present paper. An ASIC resistant puzzle, if there truly is one, may diminish the effectiveness of cloud mining. It's also possible that a nonoutsourceable puzzle is the best we can do, and this gap just has to be tolerated.

In case anyone has missed it, Eyal&Sirer have posted about an enhancement to my puzzle scheme that makes it possible to reuse existing Bitcoin miners. It's too bad I missed this! Compatibility with existing Bitcoin miners is a major win for the plausibility of implementing this as a practical fix.
http://hackingdistributed.com/2014/06/18/how-to-disincentivize-large-bitcoin-mining-pools/

The 2-Phase puzzle they propose is a "weakly nonoutsourceable" puzzle according to my definition. The main idea is that instead of *each* attempt requiring knowledge of a private key, only some constant fraction (1/Y) of attempts need to. First you, configure an existing Bitcoin miner to mine blocks at a very low difficulty (1/X chance of winning), where your coinbase contains a commitment to some public key. Every time your mining rig outputs a partial solution, you perform a second check, which essentially involves signing the solution with the corresponding private key.

In total, 1/(XY) attempts must be made to find a solution, so XY should be set equal to the current difficulty. The tradeoff between X and Y should be chosen so that Y is small enough that an ordinary GPU or CPU can "keep pace" with the partial solutions generated by a typical Bitcoin mining rig, but Y is large enough that it would be infeasible for a miner to *interact* with the pool operator without learning the private key on its own. This is actually the same sort of analysis we did in Permacoin.

This scheme is compatible with most of the work of my existing puzzle schemes:
1. A good candidate for the signature scheme is the Merkle tree-based signature scheme used in this paper and in Permacoin. ECDSA, however, is out. It's essential that the signature scheme is deterministic - there should be exactly one valid signature for a given message and keypair.
2. Since this is a "weakly nonoutsourceable" puzzle, it can be *upgraded* to a "strongly nonoutsourceable" puzzle using the generic scheme described in our paper.... basically you can take any weak-NO puzzle and make it strong-NO by adding a zkSNARK option.

This is not the case. Suppose a pool member finds a nonce, and publishes a ZK block solution. Even if the pool also finds this nonce by rescanning, it cannot associate the ZK block solution with it. This is because the ZK NIZK proofs (the GGPR scheme) are information-theoretically hiding.


This is only partially true. Any detection scheme like this is susceptible to false positives. Someone else who finds a ZK block at roughly the same time as a pool member is effectively framing them. Again, our definition says that a stolen ZK puzzle is indistinguishable from one created independently.

A preprint of my paper can be found here:
http://cs.umd.edu/~amiller/nonoutsourceable_full.pdf

The major features include:
- Formal definitions of Scratch-off puzzles (a generalization of Bitcoin's proof of work)
- Formal definitions of Outsource schemes (a generalization of the "shares" system used by mining pools)
- Formal definitions of Non-outsourceable puzzles (a weak version, which lets pool members "steal" the reward from a pool, and a strong version, which lets them evade detection!)
- A simple construction (no moon math, just hashes and Merkle trees) for the weak-case
- An upgraded scheme (using SNARKs and other moon math) for the stronger-case
- Proofs
- Benchmark implementation results using Pinocchio (though these would likely improve by orders of magnitude if we use libsnark instead)

I'm working on a series of future posts explaining some of the concepts in better detail and summarizing the implementation issues that petertodd, gmaxwell, and others have raised.

Yes, the way to read this is: if hosted mining catches on, but users are suspicious that the service may be cheating them unless the host provides proof to the contrary, then this puzzle may be effective since it's designed to *prevent* such proofs.

Imagine a user that says "I'll hire a hosted mining service, but only if they can prove to me they aren't ripping me off; otherwise I'll solo mine." Then this user would hire the hosted mining service in the current Bitcoin puzzle, but would solo mine given this modification.

My interpretation of the "spirit of Bitcoin" is that it is about *trust in a population's predictable response to incentive structures,* rather than *trust in the benevolence of oligarchs* or *trust in the responsiveness of vigilantes* etc. The point is that the behaviors we see now and will see in the future are largely a result of the incentive mechanism we implement. Altruism exists, and campaigns appealing to miners' long term stake in the stability of Bitcoin may be effective, etc. -- but correctly designing the incentive mechanism is an essential concern. I don't think we've fully tuned it yet, and the large mining pools are an example of this. Accurately predicting how people will react to the wide array of possible incentive designs is still an open research question.

This proposal is counterintuitive in that it involves engineering distrust between self-interested parties (pool members), as a way of encouraging safe behavior (solo mining) overall.

Also, in the interest of being self-contained, I repeat that this proposal is a useful technique but not a panacea on it's own. Several other non-trivial changes would need to be adopted at the same time as this puzzle, in order to provide the same low-variance option to solo miners, who otherwise would switch to Dogecoin or quit altogether.

Update: my advisors at University of Maryland and I have recently written a research paper about an improved version of this basic scheme, including a proof-of-concept implementation. The paper is currently undergoing peer review, but we will announce a preprint of the paper in the next week.

Here's my take on this:

- Both Mixcoin and CoinJoin work just fine with existing Bitcoin, no need for an altcoin or Bitcoin modification

- DarkWallet is already an implementation of CoinJoin, so you may just want to start there

- CoinJoin relies on some kind of matchmaking service, at least in the form of a public message board or chatroom. As far as I can tell, the DarkWallet implementation for now uses a central chat lobby for this purpose (or perhaps there are multiple lobbies, but you're only mixing with whoever is in that lobby) and does 2-person CoinJoins. I don't know any really great alternative to this kind of matchmaking that also prevents denial of service or sybils. Blockchain.info also implements a CoinJoin, they themselves act as the matchmaker.

- In Mixcoin, the implementation challenge is to build a mixing server, and a mixing client. The mix server can be fairly simple, needs a small amount of crypto (just ordinary signatures). The client is more complicated, as it needs to a) keep track of and interact with multiple mix servers b) monitor the blockchain (or some other channel) for fraud alerts about mixes c) schedule mix interactions automatically in the background.

So actually some of what remains to be implemented (like interacting with multiple servers) is the same for both Mixcoin and Coinjoin.

This is the same idea as in:
https://bitcointalk.org/index.php?topic=309073.0

First of all DSA signatures don't work since it's easy to create a new valid DSA signature from an old one and some partial state, so you could easily outsource a partial attempt and the pool participant could keep iterating without needing to know the key.

The other thing is that the "non outsourceable puzzle" focuses on preventing the outsourcer from just posting a bond "I promise 2x the reward of a block never to steal the reward" by using zero knowledge proofs. If this is too exotic, and the goal is just to discourage pools (rather than hosted mining as well), then maybe using just a (deterministic, strongly unforgeable) signature may be enough.

 

I don't agree with this part. The coin-age destroyed among a set of blocks mined by an adversary does not necessarily follow any particular distribution. However, you are right that there are many possible choices for determining "value" other than distance from 0. You could, for example, interpret the "value" (beyond difficulty) as the *least-significant bit* zeros instead, since conditioned on a mining attempt beating the difficulty target, the distribution of the value in this case is still as it should be.

Anyway since that's a really minor point, here's some more useful technical content. One surprising thing the attacker can do is to create a really *large* proof. The attacker does this by throwing away every block *except* the value=1 blocks, which don't exceed the difficulty target at all. This only requires throwing away 50% of the work, but it results in a proof where the "up" links are always null, and you have to traverse every damn block to validate his proof.

This isn't a problem, for the following reason. You can make progress on validating the SPV proof for multiple chains concurrently. So if one peer tries to send you a really slow proof, you should request different proofs from a different nodes and process them in parallel.

The option of this strategy is what motivates the performance goal I mentioned as a caveat at the end of the writeup. The "honest prover" should, with high probability, produce a proof that is reasonably compact. It's okay if a dishonest prover produces a long proof. Regardless of length, the prover should be unable (except with low probability) to produce a convincing proof that the amount of work done to bury some transaction exceeds the actual amount of work (including the attacker's work plus any honest work) by some fraction.

*** edit ***
Actually, now that I've written this response out, I realize another attack that's modeled in my security definition, but isn't adequately addressed in my scheme. The problem is that an attacker can, by rejecting 50% of his work, cause an honest proof to contain less useful back links. It's important to set the verification parameters loose enough so that even if the attacker does this, he can't cause honest chains to fail verification. But, if the verification parameters are suitably widened, it must also not make the ease of forging a proof much higher. All of this relates to analysis i haven't finished in my writeup, so these are things I need to address. I don't think this should affect the choice of data structure though (only the guidelines for choosing parameters).

I wrote down a rough outline of a security game definition, and a clearer description of the algorithms with pseudocode.
https://docs.google.com/document/d/12xl5eRtoE0uISUX188jnmGSb-bwG4yXByRBbdr2r97A

I also wrote out an implementation in OCaml of the key operations (using the Lambda-auth language/compiler I made especially for this sort of thing), for building the hash-value highway and creating/verifying the compact SPV proofs. It compiles but I haven't tested it, I plan to use it to create some illustrative graphs.
https://gist.github.com/amiller/9635632

Any of the above could be totally broken, but hopefully this gets the conversation moving along more concretely!

Thanks for the writeup, I'm glad there's some renewed interest in this.
I can't figure out what the difference is specifically, though, with what you've written up. The proposal in this thread already includes commitments to back links. The way I think of it is that each block contains a claim about how much cumulative work went into creating it. The proof process is basically a hypothesis test, for whether the actual work matches the claim. In fact it's a recursive hypothesis test, because if you follow the "up" links you quickly (O(log n)) arrive at a block that should divide the total cumulative work into two segments. Then you do the hypothesis test on each of these.

I'm currently trying to figure out how to phrase this as a formal security game, which should make it a little more clear how to evaluate whether either of our proposals actually achieves what it's supposed to.

Sticking to a few common coin sizes should improve anonymity in fewer rounds, even when using CoinJoin, and even if your wallet helps keeps track. The simple reason is that if your coins are already in typical denominations, you can participate in another mixing round immediately without having to make change. On the other hand if every mixing round uses a different size, you will always need to make change, and then would need to mix the change as well.

We (Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua Kroll) are a group of cryptographers spread across a few universities (mostly Princeton, also UMD and Concordia) who have being doing research on Bitcoin. Some of our past and on-going projects include anonymity in Bitcoin, discussion of the “Bitcoin is Broken” paper (1, 2, 3), distributed prediction markets, authenticated data structures, Bitcoin as a consensus game, and CommitCoin.

We have recently written a paper about Bitcoin mixing that will appear at Financial Cryptography 2014, and wanted to present it to the Bitcoin community here in this thread.


Our broad research goal is to analyze Bitcoin with an eye towards improvements that will help cryptocurrencies gain more adoption and acceptance. We believe there are benefits to financial privacy and improving this would be in the interests of the Bitcoin community and society at large.

Our method has been to design a protocol for third-party mixing services, and then analyze it in an economic model involving competing rational mixes and a population of users. We describe a potential design strategy which we call “Mixcoin” in our full paper. To be clear, we are not proposing an altcoin but providing suggestions for a mixing layer which can be implemented immediately, incrementally, and without any modifications to Bitcoin. While we aren’t providing a complete system with running code, existing mix services can incorporate our design, as we elaborate below.

There’s a well-known principle in anonymity research “anonymity loves company”. This means any anonymity service requires a large population of participating users, ideally with different adversaries, so that one can’t simply assume all coins passing out of the mixing service are “tainted” (implicated as having participated in the mix). So it’s important that mixing is sufficiently automated, fast, low-cost, and safe that a large population of users is willing to participate. Our economic analysis is about a world with multiple independent mixes that compete economically, but also operate a mutually-compatible service. Our analysis includes the incentives of the mixes; for example, we’re interested in understanding whether utility-maximizing mixes are likely to behave correctly and provide a sufficient volume of service. Overall, the conclusion of our analysis is that a world with competing for-profit mixes can sustain itself and provide sufficient anonymity.

The functionality we have had to design for our mixes in order to arrive at this result can thus be seen as good design guidelines for mixes. It is our hope that implementers of mix projects (like CoinJoin or DarkWallet), will be informed by our analysis and evaluation framework, and can benefit from our particular design suggestions. We’d appreciate feedback from the community on our proposals, and we will be happy to discuss our insights and perspectives gained from our research.


We have made the following specific suggestions for mixes:

- First, users will want to use multiple mixes, and mixes should make this easy. Primarily, they should have standardized APIs for initiating a run of the mixing protocol. Some of our other suggestions depend to a degree on users being able to automate their interactions with mixes.

- Second, all mixing transactions should appear indistinguishable in the blockchain. Otherwise, an adversary can try to separately deanonymize different subsets of users who mix in distinguishably different ways. This means primarily that all mixing transactions should be of the same value (which we call a “chunk size”), just like Tor packets have a constant size.

- Third, automation of the client-side is necessary to achieve meaningful anonymity. This is not just because funds to be mixed have to be split into a large number of chunks, but also because mixing opens up way too many side channels. Our protocol has logic built-in to it that minimizes these side channels. In particular, participation in rounds of mixing should happen periodically, at intervals chosen randomly from a memoryless (exponential) distribution. This distribution should be mostly standardized among client software implementations.

Nonetheless, there are limits to how well you can hide side channels in a mixing-based anonymity system. High-level flows could still be identifying. For example, if Alice receives 43.12312 BTC per week as salary/income and always transfers these payments to Bob, we suspect that this pattern can at best be obfuscated, not obliterated. There are still some open questions in quantifying side channels.

These parameters should be left free to change in the future, but defaults are important. If most users use one of a small number of client implementations then we expect they’ll converge on constant parameters including a constant chunk size.

- Fourth, mixing fees should be all-or-nothing, that is, for every chunk of money the mix should either retain all of it or none. This might sound strange, but it greatly improves anonymity against clever analysis of the blockchain. If every time a user mixes a chunk the mix takes a constant 2% cut (or a randomized 1–3% cut) as a fee, then a chunk passing through multiple mixes in a row will have its value decrease in a traceable way. We can avoid this with all-or-nothing fees.

There are two consequences of this. First, the chunks should be small enough (say 0.01 BTC at the current exchange rate) that most mix users will accept the variance associated with random transaction fees. Second, this will mean that to mix realistic volumes, users will necessarily have to automate their interactions with mixes.

How will users (or their client software) verify that mixes that aren’t taking more than their cut? In the paper, we provide a cryptographically secure way to do this. But that’s not strictly necessary — since these chunks are quite small and most users will have significant numbers of chunks that they’ll move through each mix, clients can statistically verify if the mix deviates from it’s posted policy on the transaction fee.

- Finally, from the cryptographic perspective, the key innovation in our paper is a “warranty” mechanism that allows users to provably expose cheating mixes. This is what allows us to prove, in a certain economic model, that rational mixes will choose to stay in business rather than defect with users’ funds. In practice, it’s plausible that if mixes incorporate our other suggestions and see a lot of volume as a result, then reports by community members of cheating vs. honest mixes should be sufficient to act as a reputation mechanism. Still, should consider the warranty mechanism that we propose as a further guarantee of service.


Comparisons to CoinJoin and Zerocoin
Existing proposals for coin mixing fall into 3 basic models: mixing using a third party (e.g., Mixcoin), mixing arranged through peer-to-peer interactions (e.g., CoinJoin), and protocol-level integration of anonymity where anonymization is handled by the miners (e.g., Zerocoin).

CoinJoin is a technique for peer-to-peer mixing that requires users to coordinate through some rendezvous mechanism. Implementations to date have entrusted a third party matchmaker to fulfill this role. Although CoinJoin has the benefit that there is never a risk of losing coins, it is susceptible to Denial of Service since parties can withdraw after the second interaction required for the transaction to complete. As with mixes, anonymity may also be compromised, even if blinded tokens are used (as suggested by gmaxwell), by matching up real users with sock-puppets. In short, both third-party and peer-to-peer mixing seem to offer features that the other doesn’t.

Zerocoin (including the improved variant, Zerocash) requires a substantial change to the existing protocol, and so seems unlikely to catch on unless it is introduced as an altcoin (as its authors have recently proposed to do). Zerocoin also relies on an implicit trusted third party for a setup phase - a party who learns the trapdoor created during the setup phase can silently forge coins and increase the money supply.

Nonetheless, much of our analysis is independent of exactly how anonymity is achieved, and applies to CoinJoin and Zerocoin as well. As one example, if a matchmaker service for Coinjoin were to charge service fees, our analysis suggests a way to do it without the fee amounts compromising anonymity; another is defeating timing side-channels by sampling from a memoryless-distribution to decide when to participate in a mix. The paper goes into detail on this and other issues. We don’t consider Mixcoin to be the final word, and some combination of these techniques may lead to the best design.


tl;dr: We wrote a paper about Bitcoin mixes, in which we proposed techniques to keep mixes accountable and mutually-compatible, and argued they're economically viable.

Isn't it the case that the other coin-swapping protocols are susceptible to this same weakness? This applies generally to double-spends too. The cost of mining a big-enough "attack fork" can be amortized over many concurrent double-spend attacks using the same attack fork.

Also....
Please cite this protocol as TierNolan's, I gave a clearer description but changed nothing https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949

One big problem with the N-way lottery protocol in this paper is that it requires an extremely steep security deposit. Each player wagers only 1 coin, but has to additionally deposit N(N-1) coins. In total, only N coins are wagered, but O(N³) coins are escrowed for fairness. They argue (and I agree with it) that this is the best that can be done... for a one round protocol!

I claim that we can improve on this, having exactly the same payoff structure and security, and deposits only of size N. The caveat is that it requires log₂ N rounds. The protocol is a tournament bracket. Each player commits to log₂ N random numbers. In first round, player 0 plays a 50/50 coinflip game with player 1, player 2 plays with player 3, etc. If a player reveals their random secret, they can immediately exit the game and get their deposit back. If they win, they go on to the next round. If one player in a match does not reveal their secret, then their deposit is forfeited.

[edit]I actually have no idea how to pull this off. Seems impossible to me at the moment.