OK I wrongly assumed that you wait q blocks and then do q attempts to build your k-blocks secret branch, to have q*1/q=1 successful attempt as the expectation, so overall you attack once every 2q blocks (where you sit idle for the first q blocks, but now I see that you meant that the time you sit idle is unrelated to q). Actually a crude upper bound would be q+k*q instead of 2q because of failed attempts that started but didn't reach length k.
Obviously it makes sense that p can be smaller when q is bigger, but this p^k * C(n, k)*k! > 1/q calculation doesn't take into account coin-confirmations at all? (i.e. that you have better probabilities at the later attempts because you have more coin-confirmations). So I suppose that a more precise calculation will show that you can have a (significantly?) smaller p to do double-spending attacks?

I've looked again at this thread and at the discussion between killerstorm and cunicula at the other threads.
Few of the earlier posts are somewhat unclear to me:
Where does killerstorm's 1/q number come from, at https://bitcointalk.org/index.php?topic=102342.msg1139483#msg1139483 ?
At the wiki (link), the terminology that cunicula uses seems a bit loose, when he writes that you double your hashpower and it increases your chance from 50% to 100%, it appears to mean that you take the other 50% of hashpower that the other miners had (so they now have 0% of the hashpower), unlike what we'd normally think that "double your haspower" means (you'd have 2x hashpower and rest of the network would have x hashpower). The calculation there is fine for the stylized example, but to avoid confusions it might be better to clarify similar terminology of some posts like post #40 here, or rewrite in wiki .

Maybe when you analysed double-spending attacks and fell-back to coinconfirms^(1/4) to allow better protection, you should also provide analysis of attacker with a lot of hashpower but without stake, who tries to do 6-block reorg, obviously coinconfirms^(1/t) for bigger t will make it easier for an attacker who has little or no stake.

About the last post #43 of cunicula, it seems similar to coblee's first idea (link) that we abandoned in favor of his 2nd (better) idea. Though it seems wasteful to do {hash (public key of address k,j)} where j=1,2,...,c because c might be large, instead simply do V'=c*hash(lucky-num,pubkey-address), the important observation is that PoW-only attacker cannot try to generate new (privkey,pubkey) pair which is close to the lucky-num using just hashpower, because this fresh pair will have 0-coinconfirms for the current block.

Regarding stakeholders who try to sign competing forks, and whether the protocol should punish them, some of my comments were confused and are relevant for Meni's scheme, but not really for the PoA scheme. In coblee's OP, the first attack vector (3rd paragraph of "Best Chain" subsection) describes a scenario where the signed block exists before the fork began, but the signature for this signed block exists in only one of the competing branches after the fork began. The idea is that the miners will use the signature txn also for the branch in which it is missing (when they calculate which branch is the winning branch), and then include this signature txn in the next block of that branch. Hopefully this idea is technically feasible, because non-miner nodes also need to calculate the winning branch, so this idea might be susceptible to DOS attacks? If this protocol behavior can be implemented without significant problems, then part of my response to gmaxwell in post #6 is meaningless: we don't need to wait N blocks before allowing the stakeholder to provide his signature.

If we conclude that short re-orgs are a problem with PoA (I'm not convinced yet, see next paragraph), then as mentioned in OP we can give weight to the signatures only after say N=100 blocks. So an attacker with 50% hashpower who can obtain more signatures than the honest network would need to prepare a secret branch of e.g. 106 blocks to have 6 valid signatures, while the branch of length 106 that the honest network generated during that time would have 3 valid signatures, assuming that the protocol re-targets the stakeholder reward so that about half of the blocks get signed. The disadvantage of N=100 before signatures become valid is that you cannot rely of the service that the stakeholders provide if you only wait for e.g. 6 confirmations. I'd also like to mention that cementing (mentioned in post #27) is an extra feature, it isn't required. The advantage of cementing (at e.g. 6 blocks) is that if you wait for more than 6 blocks then you can be confident that an attacker couldn't release a secret fork that would reverse your txn, and the disadvantage is that an attack who releases his fork at exactly 6 blocks can create havoc and split the hashpower of the honest network due to propagation lag (until it re-unites at the un-cement depth of e.g. 100 blocks).

About killerstorm's double-spending-bribes service scenario, let's use the following (standard) terminology:
* "honest" participant follows the protocol, so he runs only the official client code (or another client that implements exactly the same protocol), therefore he doesn't participate in the double-spending-bribes service because that involves running different code that connects to the attacker's branch instead of the honest network.
* "greedy" participant is rational/self-interested, he cares about earning more money for himself, and doesn't try to hurt the network on purpose.
* "malicious" participant tries to destroy the network.
If we assume that the majority is honest and isn't more lazy than the greedy+malicious participants, then PoA is more secure than pure-PoW (lazy means that honest participants provide less PoA signatures than greedy+malicious participants).
It isn't all that clear whether those who participate in the double-spending-bribes service are greedy or malicious, because if this service is successful then it obviously hurts the network. There's also an issue regarding your self-interest, because when the honest participants see that you provide signatures for the double-spending-bribes service they might blacklist your stake, etc. Therefore, it can make sense to assume that the majority of stakeholders are honest, as we assume with Bitcoin that the majority of miners are honest.
If this double-spending-bribes service was such a great idea, then it raises the question of whether such service is plausible with the pure-PoW Bitcoin network. As mentioned in earlier posts, the technical difference is that with PoA the greedy participants can provide their signatures both to the honest network and to the attacker (who pays them more), and if the attacker's fork fails then they still earn their regular reward with the honest network. With pure-PoW, the greedy participants contribute their hashpower to the attacker's fork, and if his attack fails then they earn nothing. So for pure-PoW, if this double-spending-bribes service is so great then maybe the (malicious, not greedy) attacker could incentivize greedy participants to contribute their hashpower to his attack by giving them significantly higher rewards, so it becomes worthwhile for them even after taking into account that when the double-spending attack fails they earn nothing.
One way to overcome this issue is to allow the PoA signature to be provided only in the next (say) 6 blocks, so now a greedy participant cannot withhold his signature from the honest network, as it'd be invalid if they try to provide it after 6 blocks. This idea doesn't necessarily interfere with the earlier issue that I mentioned here regarding the first attack vector (3rd paragraph of "Best Chain" subsection in the OP), for example if the protocol specifies that honest miners should include the PoA txn even after 6 blocks (but before 100 blocks) if they saw and verified a competing branch in which this PoA txn was included at depth 6 blocks or less, but the honest miners shouldn't include the PoA txn if if they just receive it for the first time after more than 6 blocks, and when calculating the blockchain-difficulty the relevant number for PoA txn to be valid is 100 rather than 6. However, the attacker could just release his losing branch anyway, to get the signatures included in the honest branch. I'm not sure if 6 blocks window for including the PoA signature is a good idea anyway, if it is then maybe there could be better ways to do it that I didn't think of.

Overall I still think that the PoA protocol as outlined by coblee is the best proof-of-stake scheme that we should implement in Litecoin. The option to have signing-key delegation is probably risky+problematic, so striving for e.g. 10% of the reward for stakeholders (who take the extra risk of using unencrypted wallet) seems like a good idea.

What about scrypt ASICs ? Have you seen the chart at page 19 of www.tarsnap.com/scrypt/scrypt-slides.pdf ?

There are ideas being discussed to make it even harder for govt to attack, namely proof-of-stake and BDD weight.

By this argument you could also say that it's easier for the govt to break scrypt-hashed passwords than sha256-hashed passwords.

Let's differentiate between an entity that tries to acquire scrypt hardware in secret, and an entity that tries to acquire scrypt hardware openly. If this entity tries to do it in secret, then obviously it'd wish to have ASIC that's as fast as possible.

Also, if Litecoin makes CPUs more competitive, then more honest hashpower could also join the network, not just CPUs that sit in govt offices or exploited by botnets. Let's imagine that the entire Bitcoin network switched to scrypt and even gained more CPU miners as a result, do you think that Bitcoin would be more prone to govt attack, or less prone to govt attack?

Yes, the scrypt parameters in Litecoin were a compromise, 128k fits into L2 cache.
Still, sha256 only needs to maintain a 512 bits internal state, so the ASIC that runs many hash attempts in parallel only needs 512 bits per hash attempt for sha256, compared to 128 kilobytes per hash attempt with scrypt.
I suspect that BFL couldn't manufacture a cost-effective scrypt ASIC even for the 128k memory buffer parameter.
Maybe coblee or pooler will start a new thread soon, to discuss benchmarks and solicit advise from hardware people on whether modifying the scrypt params of Litecoin (via hard fork) is a good idea.

No, he didn't misinterpreted that slide. Since scrypt ASIC is less cost-effective compared to sha256 ASIC, it would be more difficult for an attacker (who invests in ASIC) to outcompete the Litecoin distributed network, than to outcompete the Bitcoin distributed network. It also means more generally that the hashpower will be more decentralized.

But there are already manufacturing pipelines for the current PC design, so the question is whether retooling factories will be cost-effective? Let's say that we agree that the dedicated scrypt hardware will be 50x faster than regular CPUs, and that sha256 ASIC is 5000x faster than regular CPUs, is it really worthwhile to manufacture dedicated scrypt hardware just for 50x speedup? According to your previous theory, even the botnet operators will outcompete this 50x speedup...

The whole point of scrypt is that ASIC won't be available to the attacker.
Let's take tacotime's suggestion to use 8 gigabytes for the scrypt memory buffer... Admittedly, this suggestion is too extreme, but I guess that under this scenario nobody would be able to manufacture ASIC with more than a negligible advantage over a regular PC. It would be more cost-effective for any entity just to use regular PC hardware.

Do you mean 1-2 gig to verify the hash of single block? How long do you think it'd take for a modern computer? Let's say 1 minute? If the blockchain has 200,000 blocks, then it'd take 139 days to verify the blockchain after you download it for the first time.
I don't know if 1 minute is too little or too much (hardware people, could you provide an estimate?), but keep in mind that blocks are generated 4x times faster with Litecoin compared to bitcoin, so it'd grow from 200,000 blocks to higher numbers more rapidly.

You consider only the botnet attack, and proclaim that Bitcoin is more secure because of this particular attack.
Botnets are likely to attack just the poor computers under their controls, it isn't likely that a botnet will gain 51% hashpower (which wouldn't be enough for double-spending if Litecoin implements proof-of-stake).
However, a malicious entity (e.g. government) could invest in ASIC to gain 51% hashpower and attempt to destroy the network (by denying txns, proof-of-stake wouldn't help), scrypt protects against this attack.
More generally, ASIC tends to centralize to hashpower, which diminishes the overall security of the network.
If Litecoin modifies the scrypt parameters to make CPUs more competitive, then the hashpower will be more decentralized.
See also https://bitcointalk.org/index.php?topic=103085.msg1131548#msg1131548

6-8 gigabytes per each hash attempt? Then people who are non-miners and simply want to run the client to send/receive coins won't be able to do it, because verifying each block becomes too difficult for regular computers (that are supposed to multitask and run other apps at the same time).

Maybe your protocol is less popular because it's more complex to comprehend all of its security implications. If we had a comparison between the properties of each proof-of-stake proposal then it'd be easier for people to follow.

(1) Well, you wouldn't want to send your privkey in the clear to the hashpower entity that you're renting. Even if we could do signing-key delegation (still waiting for a reply from gmaxwell regarding ECC related keys, I thought about it and I don't think it's possible), you'd probably want to have the miner who solved the block send it to you for signing, before broadcasting it to the rest of the network. So I suppose that you'd be losing some precious seconds compared to the other miners. It should also be verified that the stakeholder isn't faking to attack honest miners, which he could do by spending his coins even after he provided an initial signature evidence to the miner. I bet there are all sorts of interesting scenarios that could arise, that we haven't thought of yet. I still conjecture that the scenario where the stakeholder simply wouldn't want to bother by delegating or investing in his own hashpower is a plausible scenario.

(2) Right, I was confused and missed the fact that your coins lose their weight after you use them when you solved the block. So I suppose that it's a question of variance, e.g. if you solve a block once in a blue moon then you'd probably prefer to have a single address that controls many coins. Also, maybe if one or a few malicious miners+stakeholders keep a large amount of coins in a single address then they could use it for double-spending attacks, under the assumption that the rest of the distributed network splits their coins among many addresses?

Hello cunicula,

Your protocol may be the most secure in terms of double-spending, I haven't looked carefully enough at the security analysis yet.

But I'm not sure why you're confused that we're brainstorming other ideas too, it seems to me that there are at least a couple of fundamental differences between your protocol and PoA:

(1) if someone buys let's say 100,000 coins with fiat money at an exchange, and now as a stakeholder he wants to contribute his services to the security of the distributed network, but he's not the kind of person who would mess with GPUs/ASICs hardware and become a miner, then under your protocol this stakeholder wouldn't participate?

(2) it appears that your protocol incentivizes stakeholders to keep their coins in a single address, in order to increase their coin-confirmation when they sign the block that they solved. This raises security concerns, and with PoA we don't have this problem because coblee's idea of follow-the-satoshi to determine the lucky stakeholder works even if that stakeholder splits his coins among many addresses. Have you thought of ways to discourage people from storing all their coins in a single address with your protocol? Maybe they'd have to add multiple signatures to the block that they solved?

If we switch to more intensive scrypt params (larger memory buffer) then GPUs will be less effective, but the performance will degrade even for non-miners who just send/receive litecoins, because the client will have to work harder to verify the blocks.

Yes, proof-of-stake becomes less secure than pure proof-of-work if the majority of stakeholders is malicious. The underlying assumption is that the majority of stakeholders is honest, and that stakeholders wouldn't want to see the value of their coins depreciate when the network is attacked.

There is a proposal to have signing key delegation, so that stakeholders could participate without online wallets (see the other thread mentioned in the OP).

"can"=="could have", it probably cannot when ASICs control the majority of the hashpower.
If a security flaw in sha256 is discovered then the situation could become messy, because ASICs aren't re-programmable and the people who bought ASICs would have a financial interest to stick with an insecure hash function.

It's highly unlikely that you'll see Litecoin ASICs, producing scrypt ASICs isn't cost-effective:
http://www.tarsnap.com/scrypt/scrypt-slides.pdf
https://github.com/litecoin-project/litecoin/wiki/Comparison-between-Bitcoin-and-Litecoin

However, there might be a hard fork that modifies the scrypt parameters in Litecoin so that it'd be more cost-effective to use CPUs (there are pros/cons with different scrypt params).

Yes, if you store more data than just the signature, then it's no longer RPA (but it still might be data that an attacker can attempt to generate, rather than data that the attacker doesn't have control over). So it bloats the blockchain a little more, but if attacks are plausible then it could be worthwhile to add it to the protocol. I think that the basic idea behind such attacks involves a majority (at a particular time) of stakeholders who tries to double-spend.

This PoA protocol is a form of PoS, that's more simple and more efficient because it doesn't require nodes to propagate proof-of-stake signatures and attach those signatures to the blockchain.

To help with small reorgs, maybe we can do cementing in PoA too: as coblee mentioned, PoA signatures should have little/no weight at start, until their block gets older, so maybe the node can cement i.e. refuse to switch to another branch that reverses at least (say) 6 of its last blocks, and will un-cement only if the signatures weight of the other fork passes some threshold.

It sounds risky to have panic mode with each user manually selecting which branch to use, instead of automatic rules that all nodes follow. If enough clueless users make a mistake, then the blockchain forks and the situation might escalate, because people in different forks begin to have financial interest to stay in their fork?

That spending is a signature of random data, because that data exists on an orphaned branch, and some of the network nodes have never seen and will never see this orphaned branch.


At the most basic level, PoA tries to fix the scenario where an attacker with large hashpower could do double-spending. It's infeasible to fake ECDSA signatures with large computation power, so this kind of attacker will fail if the protocol incorporates proof-of-stake. The question is whether we open the door to other kinds of attacks, and how to minimize these risks.
There might be other indirect benefits, for example if PoA would be useful in providing security from double-spending attacks, then maybe less hashpower would be needed to secure the network, so it could be more energy-efficient.

Yes, that's the kind of thing that I meant.
However, there's a crypto issue with this suggestion: we would include a signature of random data (edited: hash of a block in an orphaned branch in Meni's protocol, txn of some coinbase output in coblee's protocol) as evidence that an address should be banned from providing proof-of-stake. This means that the crypto security assumption that we're relying on is somewhat weaker, because we don't have a reduction from chosen-plaintext attacks to random-plaintext attacks. If you only know the pubkey and can sign random data, it obviously means that ECDSA is broken, but still it's a weaker assumption. If ECDSA wasn't resistant to RPA but still resistant to CPA, then the worst thing that an attacker could do is ban other addresses from providing proof-of-stake.
Another issue is that under this suggestion the signatures would probably also need to sign the height of the block, instead of just the hash of the block, otherwise an attacker could take an old block that you signed and claim that it's evidence that you're attempting to sign several forks now.

As a more general note, if we decide to implement PoA in Litecoin (maybe as a sandbox for Bitcoin) then I guess that we'd be biased towards simplicity, so handling far-fetched attack scenarios could be sacrificed for the sake of simplicity. This discussion is worthwhile, as we consider which attacks are plausible and which attacks are far-fetched.