My reading of iwilcox's post (well, my reading of the big diagram with nodes circled) is that the preimages of the child-node hashes (just the preimages of the hashes actually in the path from user's account to root --- the whole tree is not expanded of course!) are given to the user, so the user can verify this. I haven't verified that that's what olalonde's code actually does, but I'd expect it to be the case.

Hi charlescharles,

Good catch. This actually addressed in iwilcox's writeup --- grep for "similar customer pairing trick". In fact this is safe, since the sum for each node is part of its hash. This means that if you tried to zero out one of the children, that child's hash would change. So even though the unsummed child amounts are not explicitly hashed, the are committed to as part of the child nodes' hashes. I hope that make sense.

By the way, in future, if you think you've found a security/crypto bug, it's best to bug people in private (in this case olalonde or gmaxwell would be appropriate -- or go on IRC #bitcoin-wizards and ask to PM somebody). Especially if there is a possibility of loss of funds (if the wrong people know about something before it's fixed) responsible disclosure is critical.

Thanks for auditing code!

Andrew

DannyHamilton has gone above and beyond the call of duty for a number of years now, providing detailed, thoughtful, consistently correct advice on this forum. He has a wide understanding of Bitcoin's operation and explains things in great detail, often even to users who are clearly unwilling to invest a fraction of the time reading his posts that he spends writing them. There is an overwhelming amount of repetitive and ill-advised material on this board and it handling it would be far more hopeless without him.

It is easy to become frustrated in such a situation, and also difficult to communicate tone through a text-based medium, so I hope you will give him the benefit of the doubt in future. And do not call him ignorant. That is not only untrue, but uncivil conduct. This sort of behaviour is why more knowledgable people won't take the time to participate on this board, and is detrimental to everyone.

Sigh, ASIC hardness has been discussed ad nauseum. It is neither possible nor desirable.

When you unlock coins on the mainchain, all that it sees is a SPV proof of ownership on the sidechain. It would look for things like the amount of coins being proven in some standard location. So it'd be easy for the sidechain to put some amount different from the "real" amount to simulate a changing exchange rate. Since this amount would change in a predictable fashion with each block, it could be a consensus rule on the sidechain, so it'd be just as secure as the ordinary case.

So your idea is definitely workable.

But notice the economics here -- users are moving their coins to a sidechain which will cause them to devalue, rather than directly paying fees. I think the effect from a user perspective is actually the same -- so if users don't want to pay fees, they won't want to use this sidechain either. (Maybe there is some economic argument about inflation versus direct fees, I dunno.)

Because every transaction must be stored by every archival node forever; it must be validated by every full node; its outputs must be stored by every full node at least until they are spent.


Well, no, this is a good point. It would be better to have privacy such that the network could not distinguish between these transactions, but the fact would remain that one is an infrequent permanent transfer of land for a significant amount of funds, while the other is a sale of a consumable which happens millions of times a day and nobody cares if individual transactions go through or not. To be a useful network, Bitcoin needs to be able to handle the first without fear of fraud or reversal. The second is not so important.


I'm not sure about "an intermediate layer for clearing". Probabilistic transactions don't feel like an intermediate layer, for example.

The problem (and also the problem with using Hashcash for email spam) is that attackers are always willing to invest more on dishonest behaviour than honest users are willing to invest on honest behaviour. They can buy dedicated hardware, use botnets, etc., meanwhile honest users will be trying to build transactions on slow devices with low battery capacity.

Also, unlike email "spam" in Bitcoin can be produced by honest users simply because there are so many of them relative to the limited blocksize. So for a hashcash-like system to actually filter transactions to the degree necessary, it would need to be turned up so high that users could not do the computation on their own devices. So then they'd pay some third party and you're back to the fee situation, except now the people choosing the transactions aren't the ones receiving the fees, so you have an incentive mismatch.

Please take this garbage elsewhere.

The Bitcoin protocol is perfectly capable of handling micropayments. Most nodes will not relay transactions with tiny outputs because they are not interested in storing and indexing them, they are not compensated for doing so, and if there was somehow compensation, it would overwhelm the amount of the micropayment.

Since I started typing this, a somebody (actually several somebodies) in Bejing purchased a cup of coffee. It does not make sense that everyone around the world should need to be aware of this, let alone store and validate information about it.

Signing a transaction with a private key to which an address corresponds is nothing like "sending from an address" the way than any English speaker would understand "sending". Did you read the linked article?


How many blocks back? From which block(s) are you extracting randomness? Can you describe the ways that various parties would try to game this system and what the costs to them would be?

Provably unspendable outputs do not need to be stored by every single full node on the network for eternity. Non-provably unspendable (but unspendable) outputs do have this property.

Suppose the blockhashes were to lie in [0, 9] rather than [0, 2^256-1], and that there were nine participants. Do you see why taking RNG([0, 9]) mod 9 will result in zero appearing twice as often as every other number?

Addresses do not appear in the protocol.

This is already the case.

You can burn coins by use of provably unspendable outputs.

It is possible to create addresses for which "everyone is sure" that nobody owns corresponding key material, by use of nothing-up-my-sleeve numbers or "hashes" with too much structure to have possibly been found by searching. But you cannot make them provably unownable, so doing this is strictly inferior to using ordinary provably unspendable outputs.


This is already the fee semantics, and has nothing to do with addresses.


Fees are not a lottery. You later indicate that this new reward has a fixed miner-independent destination determined by the protocol, so I suppose I am misunderstanding. In future, I advise you to not use the term "reward" to describe coinbase outputs which are not miner rewards, since this will only cause confusion.


Who lists your address? Every validator, I suppose. How do they know it? Was it encoded in the burn address somehow?

How is the ordering of these addresses determined? Why have you chosen a probability distribution so that the ones near the front of the list are more likely to be selected than ones on the last? (The difference is negligible, but totally unnecessary.) Also, miners would always take this reward since they control what goes into the list of addresses, so the distribution is irrelevant.


Have you investigated any of the other research into trustless lotteries? For example this one?

Wouldn't surprise me.

Not quite. The receiver needs to decrypt the message before checking the hash, which creates a difference in timing for "valid hash, bad message" and "invalid hash" so it is potentially possible for an attacker to guess messages and use timing to glean information. If there are error messages or observable behavioural differences, these could be used instead of timing. Also there are possibly things like length-extension attacks on the hash function. In fact, regardless of hash function strength, by exposing a hash of the message to the public, you run the risk of predictable messages being found by brute forcing a preimage of the hash. Using an HMAC (a) blocks potential regularity problems in the hash function, e.g. length extension, (b) doesn't give the public any information about the message, regardless of its predictability, (c) allows you to put the authentication on the ciphertext, avoiding the timing problem above.

Note that timestamps are low-entropy and can probably be confined to a small range using public information for most applications.


Thanks, glad we're on the same page .

Is this CCA-secure? (I dunno ... I would guess so in the random oracle model, but I wouldn't build a cryptosystem based on a guess.) Rather than using a plain old hash, an HMAC keyed with the shared secret would be better. This lets you apply authentication after the encryption, to avoid running afoul of "encrypt-then-MAC, never MAC-then-encrypt" as well as to avoid using multiple channels for a single message (which increases your attack and analysis surface significantly). Using a MAC-then-encrypt scheme is a very dangerous idea, so don't do it.


These aren't theoretical attacks. Any reaction to a marred ciphertext except outright immediate rejection will be used in a real attack. The only "theory" here is modeling the attack using a decryption oracle, but that's just a formal way of describing "any reaction to a marred ciphertext". Cryptography is broken unless proven secure, and if it has been proven secure, it should be assumed broken until it has been both audited by experts and used in the real world.

I'm describing problems with your scheme to give you an idea of the subtleties involved in designing cryptosystems. I'm a finite being and you should have no problem designing a system that will satisfy me by simply running through all the concerns I can think of. This will not give you a secure cryptosystem. It will give you a system that is as secure as I can design while communicating over the English language (which is very lossy) and without devoting any time to working through the details. So I can't give you specific attacks on specific implementations...this is unfortunate from a didactic perspective, but says nothing about the security of your system.

Edit: To be clear, you aren't being dense. This is really tricky stuff. But I want to say "these are the things you should be thinking about when thinking about crypto" without saying "it's safe under any circumstances to create your own crypto".

The idea is that the attacker could modify the message along it's way from the messenger to the address controller. Or more likely, snoop the message off the wire or the blockchain or wherever, tweak it, and submit it separately. In either case the attacker can submit a message he doesn't know (except that it is a real message corrupted in some predictable way) and observe the address owner's response.

Note that even with a CCA-secure encryption scheme, messages should have a timestamp or nonce or something to prevent simple replay attacks.

In academic cryptography you want well-defined security against arbitrary adversaries with well-defined powers. To make these useful in the real world, we try to make the definition of "security" as strong as possible: typically you want "indistinguishability", meaning that if the attacker gives you two messages of his choosing, and you reply with the encryption of one, he cannot tell which one with probability significantly different from 1/2. Here "significantly different" roughly means "goes to zero very quickly as you increase the bit security of the cryptosystem".

Two standard sets of adversary powers are

• Chosen plaintext adversary (CPA, "semantic security", "passive attacker"): The attacker has access to all the public parameters and public keys. He can therefore encrypt whatever he likes before and after submitting his two messages for encryption.
• Chosen ciphertext adversary (CCA, "active attacker"). The attacker also has access to a decryption oracle. Here before and after submitting two messages for encryption, he can also submit arbitrary ciphertexts for decryption to see what he gets back. The only rule is, after receiving the challenge encryption, he can't submit this to the decryption oracle!

These are deliberately very general. If you are arguing security along the lines of "oh, well, as long as the user only does this, or the attacker can only do that, or..." then you've got two problems. The first is that it's probably really hard to argue security rigorously under such an ad hoc definition. The second is that the security of your system now depends on exactly the way that it's used. This means that every change to the surrounding context of your system (e.g. how is the message transmitted, which messages are legal, who has access to what keys, etc., etc.) is now potentially a security bug. Nobody can do this kind of analysis continuously so you are screwed. A classic example of this sort of problem is the crazy mess that is TLS. That blog post also talks about encrypt-then-authenticate vs authenticate-then-encrypt, which is actually a instance of this CPA security being used where CCA security is needed.

Roughly, what CCA security means is that given a ciphertext, there is somehow a way to prove that it is a "real" ciphertext. (Not a way to prove that the ciphertext came from the right person, mind you, that is what Crowex is talking about. Just that it's not deliberately mangled in an effort to learn about its contents. As a simple example, suppose your cryptosystem was "derive an ephemeral shared secret C, then coerce the message M to a curvepoint and the encryption is CM". Believe it or not, simple multiplication like this is the basis for most CPA-secure systems --- you can see, if C is random to the attacker, then CM will be too, so the attacker sees the encryption as random data, and therefore cannot learn about the message well enough to tell one from the other with probability different from 1/2. But in the CCA game, this is easily broken. As the attacker, this is what I do: submit two messages M, M' and receive an encryption C. Submit 2C to the decryption oracle and receive a decryption P. Then P/2 was the original message.

What's interesting is that given a CPA-secure encryption system it is basically always possible to "bootstrap" this into a CCA-secure system. For example the Naor-Yung system (gzipped postscript --- anyone have a PDF link?. Maybe try Naor's website which has a link at "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", but this is broken for me.) works by encrypting the same message twice using different public keys, and providing a zero-knowledge proof that they are the same message. The trick is that the zero-knowledge proof requires knowledge of the shared secret (more specifically, knowledge of the random nonce used in the encryption --- it is not relevant to Naor-Yung that this randomness is used to generate an ephemeral shared secret). So when I try to do something sneaky like taking a ciphertext C and submitting 2C, I won't be able to make a new zero-knowledge proof, and the decryption oracle will simply reject the ciphertext.

This is cool: it means that CPA-secure systems are still interesting, even if their direct use is limited to pre-authenticated channels. So a good exercise is to head to IACR's eprint archive, find some CPA-secure systems, and try to break them in the CCA game. This is almost always possible --- sometimes as easily as I described above, sometimes not.

So here's your problem: with an unauthenticated channel (like broadcasting encryptions) you need CCA security. Otherwise an attacker can submit arbitrary ciphertexts, and depending on the details of the system (remember, this dependence is deadly!), will be able to get some sort of decryption oracle. Maybe this is simply "output an error if the message is not well-formed, or its padding is not well-formed, or whatever". No matter how weak the oracle is, it's still outside of the CPA security game under which the cryptosystem was proven secure. (In fact, error messages are exactly how the original TLS timing attack I linked earlier worked!) In any case, the result is that the security of your system is basically an accident of the exact way you set it up and the exact way your users use it. So in the future, they will do something weird, and the system will be broken as a consequence.

I hope this helps clarify the original message.

Oleg's scheme is also inappropriate because it gives no ability to the blindsigner to check what he is signing. (And if you give him enough information to verify this, he'll have enough information to sign anything he wants, so again you fail to have a threshold consent scheme.)

Then use multisignature transactions. SSSS is inappropriate because the secret dealer has access the entire key, and once all parties recreate the full key any one of them can do anything at all, they do not need to agree, just race each other.

https://download.wpsoftware.net/bitcoin/asic-faq.pdf

Questions 2.5 and 2.6 cover the obvious problems with this proposal, but almost the entire document is applicable.

What are you trying to do?

Can you cite a single core developer suggesting that any of these are targeted or even solvable problems?


What does this mean?