Proof of Activity Proposal

[iddo]

If you want a really good challenge to work on, I suggest:
4) eliminate the need for hard-coded timing parameters, such as 10 minutes in between blocks

See https://bitcointalk.org/index.php?topic=79837.0
However, you're in the wrong thread, please visit https://bitcointalk.org/index.php?topic=102357.0 and keep the discussion in this thread focused on the PoA protocol.

[iddo]

Implementing voting weights is complex and probably involves computationally intensive calculations by all the network nodes. But it might be possible just to penalize an address that attempted to provide PoA signatures in more than one fork, by including the evidence that it signed another fork in the blockchain (same issue arises with Meni's voting weights idea). This idea should be investigated if there plausible attack scenarios (perhaps your scenario). We shouldn't assume that the majority of stakeholders is malicious, but we should assume that the majority is rational.

Well, instead of using weights we can just ban whole address so he won't be able to spend his coins, is that what you've meant?

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.

[killerstorm]

However, there's a crypto issue with this suggestion: we would include a signature of random data (hash of a block in an orphaned branch) as evidence that an address should be banned from providing proof-of-stake.

I'm not sure I follow you, coblee wrote:

Block signing is achieved by spending the PoA coinbase output. When the selected stakeholder spends that coinbase output, he is effectively "signing" that block.

So apparently evidence of banning should include that spending and corresponding block header with coinbase.

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.

Well, if you want block signature to work this way, evidence of wrongdoing should include at least a whole block header.

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.

I still don't get what kind of problem PoA is trying to fix.

[killerstorm]

Point taken. Do you see a way to fix up this proposal so that it's not theoretically weaker?

I still don't get what kind of attack are you trying to defend against with PoA. What problem is it trying to fix?

If it is about small-scale reorgs, I doubt anything can be done at all since ultimately weight modification from signing increases variance and thus likelihood of attacks "from time to time".

If you focus on large reorgs, i.e. it is a defense against attacks which aim to discredit currency as a whole, I'd say introducing lag should help. I.e. you can sign block only once it has like 50 confirmations.

This way block signing for double-spends will become largely impractical. One can try to use PoA vector in that large attack, but (arguably) that's harder than simply borrowing hashing power. Additionally you can implement punishment to make it even better, but it's not necessary to have punishment from start. I.e. it is required only against really sophisticated attack.

And in general I would advice to follow Meni's PoS design, PoA with lag will be similar to it. If you want extra double-spend protection you can add cementing. Also, stuff that iddo have written, i largely agree with him.

(Note that Meni pretty much confirms that you cannot prevent small-scale reorgs with PoS, but you can prevent them with cementing, and you can fix problems which arise from use of cementing with PoS (or PoA)).

[iddo]

However, there's a crypto issue with this suggestion: we would include a signature of random data (hash of a block in an orphaned branch) as evidence that an address should be banned from providing proof-of-stake.

I'm not sure I follow you, coblee wrote:

Block signing is achieved by spending the PoA coinbase output. When the selected stakeholder spends that coinbase output, he is effectively "signing" that block.

So apparently evidence of banning should include that spending and corresponding block header with coinbase.

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.

I still don't get what kind of problem PoA is trying to fix.

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.

[killerstorm]

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.

Err, let's start from beginning. WHAT is included into a block chain as an evidence of wrongdoing? I see two options:

1. block-signing transaction itself as self-evident thing
2. a special message with a special format which includes both that txn and all require information

Apparently if we choose second approach we can include as much information as needed (i.e. block header, coinbase) so cheating would be not possible.

If you're concerned about 'signature of random data' then you probably assuming approach number 1 as it requires less coding. But I guess in that case a block-signing txn must have a certain format to distinguish it from normal txns... Otherwise block will be considered invalid as it contains invalid transaction.

(We cannot assume that all invalid transactions are evidence of wrong-doing because they might be traces of double-spends performed ON that user, not BY that user.)

Thus we can assume that a coinbase output for block-signing has some special scriptPubKey and block-signing txn includes scriptSig which matches that scriptPubKey.

For example: scriptSig might include 1) magic number which distinguishes it from normal txns. 2) signature for coinbase txn spend. 3) block metadata like timestamp, height; 4) signature for that metadata.

As metadata is not random, we no longer have random-key attack, do we? If we demand meta-data to be plausible, this would significantly limit attacker.

(While we are here, what if we just request two signatures: for block's hash and for block's hash hash? Attacker can choose any block's hash, but then he cannot choose block's hash hash, is it still RPA? I really don't know much about ECDSA.)

At the most basic level, PoA tries to fix the scenario where an attacker with large hashpower could do double-spending.

Double-spending, sure, but we should probably differentiate small-scale double spending caused by reorg of ~10 blocks (6 blocks is a standard for Bitcoin, I think) from large-scale double-spending, like 100+ blocks.

I believe that neither PoA nor PoS can directly help with small-scale double-spending as they more like increase fork/main chain weight variance.

For this reason Meni's scheme aims to prevent this small-scale double-spending with cementing, and PoS just fixes split issue which arises from double-spending.

PoS and PoA can, in theory, help against large-scale reorgs.

But I'm not convinced that automatic resolution is really needed here. A low tech solution is to bring client into a panic mode if it sees large reorg. Then a human operator can analyze what happened and either checkpoint an older (pre-attack) chain which would invalidate all of attacker's blocks, or he will follow longer chain if he sees that it was probably a network split.

So you just need to add:

1. Panic mode.
2. An RPC call for user to checkpoint older (cemented?) chain.
3. An RPC call for user to continue reorg.

It's much simpler than PoA/PoS and likely more reliable. And this would completely remove profit motive from such reorgs.

Attacker can still try to do that as a form of DoS, but then it is not really a double-spend attack, it is a DoS attack you're preventing.

And, again, I believe that there is an easy, low-tech solution to frequent DoS attacks: give user an option to do auto-cementing. Then watch how idiot burns his money trying to DoS you. (Alternative: an option to temporarily enable centralized checkpointing like in PPCoin.)

(Just to give due credit, I largely designed this solution for an alt-chain I intended to do myself, but then I talked to Lolcust and it turned out that he had similar solution in mind. So it might be possible that some ideas expressed here are Lolcust's (or somebody else's). So if somebody finds it new and wants to include somewhere, mention Lolcust in credits.)

[iddo]

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?

[cunicula]

I'm kind of confused by the debate here. Isn't my proposal already good enough? As described in the wiki, it simultaneously uses coin-age as in PPCoin and work as in bitcoin. In the proof-of-stake wiki, I call "coin-age" "coin-confirmations".

Voting power is determined by a weighted average of hashing power and coin-age (coin-confirmations), rather than coin-age alone. [for details see wiki]

There is no requirement for multiple signatures to be recorded in the blockchain. (there would have to be one additional txn per block, recording the block miner's use of coin-confirmations)
 
The system is stochastic because the hashing power element of voting power is stochastic.

Like bitcoin, validity is assesed based on comparison of the block to a periodically-revised difficulty target. (a stochastic system prevents the possibility of establishing an irreversible, infeasible target.)

The primary criticism of PPCoin is that it is vulnerable to purposeful accumulation of coin-age for double-spending purposes. I think that some minimal level of additional security is sufficient to prevent this, and it can be provided by the proof-of-work element in a mixed proof-of-work/proof-of-stake scheme.

For an example of a robust system that prevents periodic double spends, consider an equal geometric weighting of coin-confirmations and work. Say you want to temporarily acquire 51% control here for double-spends. To do this, you wait an extremely long time until you have a stockpile of 99% of all outstanding coin-confirmations. Hold that stockpile fixed during the short interval you attempt double-spends. How much hashing power would you need to acquire to double spend? About 25% of the total outstanding supply. The hashing power requirement seems like a very large barrier to double-spending. It should remain adequate even after the aggregate hash rate drops to a low level. The potential gains from periodic double-spends are likely small.

Symmetrically, say you have 99% of hashing power and want to establish lasting control over the network (not just temporary control). The potential gains from lasting control are larger, so a much bigger obstacle is needed here. To achieve lasting control, you would need 25% of the total coin supply. Acquiring that would be prohibitively expensive. Both the short-term and long-term security issues appear well-addressed. Is there another security issue that I am missing here?

What about energy efficiency? Does mixed proof-of-work/proof-of-stake sacrifice energy efficiency goals? Energy efficiency is determined by the overall hashrate which is a function of block reward. As long block reward drops, future energy efficiency is assured. The problem is ensuring that security persists after energy efficiency is obtained.

Anyways, I apologize for cluttering up discussion here by rehashing my own old idea. However, because I am often flamed, I do not feel that starting my own thread is a good idea. I am not aware of a critical flaw with my idea. Perhaps there is one. If so, point it out, so we can discuss (feel free to start a new thread for this).

[iddo]

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?

[cunicula]

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?

I support the brainstorming of other ideas. Sorry if I came across badly. I just feel that my idea is not so popular and I want to understand why.

(1) Stake and work do not have to be co-located. The GPU-starved stakeholder could rent hashing power online. Provided the stakeholder's computer is on and connected to the net, I'm sure this could be worked out. [Its also possible to allow stake to be rented to people with hashing power, but I'm not as comfortable with this]

(2) It kind of depends on how confirmations are measured and reset across multiple addresses. I don't really understand this well enough. However, its worth remarking though that there is no advantage to combining your coins in one single account. Average mining output per unit time is the same regardless of whether all coins are held in one account or divided arbitrarily across multiple accounts. This is based on simulations.

To see this heuristically, suppose that you solve a block whenever you hit 100 coin-confirmations (deterministic case). If you have 100 coins in one account, then you have just enough coins to mine every single block into the indefinite future. Suppose instead that you have 1 coin in each of 100 separate accounts and that each of these coins starts with 100-confirmations. Again, you have just enough coins to mine every single block into the indefinite future.

[iddo]

I support the brainstorming of other ideas. Sorry if I came across badly. I just feel that my idea is not so popular and I want to understand why.

(1) Stake and work do not have to be co-located. The GPU-starved stakeholder could rent hashing power online. Provided the stakeholder's computer is on and connected to the net, I'm sure this could be worked out. [Its also possible to allow stake to be rented to people with hashing power, but I'm not as comfortable with this]

(2) Over a long time-span, there is no advantage to combining your coins in one single address. Average mining output per unit time is the same regardless of whether all coins are held in one mining address or divided arbitrarily across multiple mining addresses. This is based on simulations (I suspect it can be proven, but I'm not that skilled in this regard and don't want to spend a lot of time on it.)

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?

[killerstorm]

For an example of a robust system that prevents periodic double spends, consider an equal geometric weighting of coin-confirmations and work. Say you want to temporarily acquire 51% control here for double-spends. To do this, you wait an extremely long time until you have a stockpile of 99% of all outstanding coin-confirmations. Hold that stockpile fixed during the short interval you attempt double-spends. How much hashing power would you need to acquire to double spend? About 25% of the total outstanding supply.

This is intriguing, but I don't understand where do you get these numbers from. Is there a more detailed example?

On wiki page I see  

Code:

target/coin-confirmations^4

formula. This means that twice more confirmations equals 16 more hash power, right?

So if I have 6 accounts with twice the average coin-confirmations I'll be able to do a 6-block reorg with just 51/16 = 3% of hashing power.

[killerstorm]

Imagine our whole world consists of 100 identical hashing units which consist of 1 unit of hashing power and 1 coin which is used to get coin-confirmations.

One averaged, out of 100 solved blocks one block belongs to each hashing unit.

Now let's say I own 6 hashing units and I want to do a 6-block reorg. I stop hashing on my units for some time. Difficulty stays the same or decreases.

After I waited enough (say, for 100 blocks) I start hashing. I have twice the average coin-confirmations in my hashing units. Besides that, I have 6 units. So chances that next block would be solved by one of my units are something like

Code:

6*16/100 = 0.96

(I'm probably very wrong here, but it doesn't matter much -- I just need to wait enough for chances to be close to 1.)

OK, one of my hashing units is out of coin-confirmations, but I have 5 more. And, again, chances that one of them will solve the block are high. Thus I have high chances of solving 6 blocks in a row, achieving desired reorg.

If I'm not mistaken, achieving a reorg with this wonderful system is as simple as waiting a bit, neither large hashing power nor high stake are required.

Your mistake, cunicula, is that you consider only output averaged over a large interval of time. It is true that you cannot increase your output by splitting/merging your coins/hashing power. But you can affect temporal clustering of your blocks via splitting and waiting, and it makes a reorg of arbitrary size possible with little resources.

[cunicula]

For an example of a robust system that prevents periodic double spends, consider an equal geometric weighting of coin-confirmations and work. Say you want to temporarily acquire 51% control here for double-spends. To do this, you wait an extremely long time until you have a stockpile of 99% of all outstanding coin-confirmations. Hold that stockpile fixed during the short interval you attempt double-spends. How much hashing power would you need to acquire to double spend? About 25% of the total outstanding supply.

This is intriguing, but I don't understand where do you get these numbers from. Is there a more detailed example?

On wiki page I see  

Code:

target/coin-confirmations^4

formula. This means that twice more confirmations equals 16 more hash power, right?

So if I have 6 accounts with twice the average coin-confirmations I'll be able to do a 6-block reorg with just 51/16 = 3% of hashing power.

Your mistake, cunicula, is that you consider only output averaged over a large interval of time.

As you note, I messed up the calculation. However, my broader point still holds. The system is quite robust to double spends. Thanks for questioning me so I can offer the correct argument.

The formula in the wiki weights PoS heavily. I think that protection even with the high PoS weighting is likely adequate. For this formula, your statement would be correct if you replaced "twice the average" with two-thirds of all the current coin confirmations engaged in mining. This seems difficult enough to me (though probably not to you).

For equal weighting, the formula becomes [target/coin-confirmations]. Equal weighting makes double-spends much more difficult. Let's look at the equal weighting formula.

Suppose, you have 99% of the outstanding coin-confirmations. The rest of the mining world has the other 1% of outstanding coin-confirmations and is combining them with work to try to mine the current block. If you just want to mine the current block, then all of your coins will need to be concentrated in one account. Due to this concentration, your PoW difficulty target will be 99 times easier (let's round to 100) than the average PoW difficulty faced by other miners. In order to mine just the next block with >50% prob you need 1% of hashing power.

Mining several blocks in a row is much more difficult. In order to mine 6 blocks in a row, then you will need to divide your 99% across six separate accounts. Because of this division, your difficulty target will only be 99/6=16.5 times easier than the average for rest of the mining world [importantly you aren't competing with another individual miners, but all other miners collectively]. In order to mine six blocks in a row with >50% prob, you will then need about 6% of hashing power.

That is really pretty difficult to acquire. 99% of all outstanding coin-confirmations and 6% of hashing power is a high bar.

However, if this isn't good enough for you, why not just wait for more confirmations. Suppose you want to do a 50 block reorg, you will need to divide your coins across 50 separate accounts. To mine a longer chain over 50 consecutive blocks with non-negligible probability, you would need about 25% of hashing power.

You are correct that any double-spend is achievable if you wait long enough, but, unless you hold a very large stockpile of coins, the waiting period could be decades for just one measly double-spend. I'm not really worried about people planning a double spend decades in advance.

[killerstorm]

Mining several blocks in a row is much more difficult. In order to mine 6 blocks in a row, then you will need to divide your 99% across six separate accounts. Because of this division, your difficulty target will only be 99/6=16.5 times easier than the average for rest of the mining world. In order to mine six blocks in a row with >50% prob, you will then need about 6% of hashing power.

Seems to be about right except number 99%.

Let's re-purpose my previous example: there are 94 hashing units which have 100 coin-confirmations on average each, thus their cumulative hashing power is 94*100 = 9400.
I have 6 hashing units with 1600 coin-confirmations each, my hashing power is 6*1600 = 9600. So I can perform 51% attack and mine next 6 blocks with ~50% probability.

Thus I need only about 50% of total coin-confirmations and 6% of hashing power to run this attack.

I guess we get different numbers (50% vs 99%) because you consider only momentary hash power parity to mine next block, while you should consider hash power parity to mine _any_ block. I.e. you assume that 1% of coin-confirmations sits in one account and so 99 hashing units can compete with 1 hashing unit and 99% coin-confirmations. It is true that they have 50% chance of mining next block, but note that if rest-of-the-world actually wins, it now has 0% of confirmations and attacker has 100%. So you need to consider a scenario where that 1% of coin-confirmation is spread over many accounts, and each such account gives only a minuscule bonus to hashing power.

That is really pretty difficult to acquire. 99% of all outstanding coin-confirmations is a very high stake threshold to meet. Waiting a little while won't do it. I need to work harder to figure out exactly how long you'd need to wait.

Well, in my example if you have 6% of coins you need to wait 1600 confirmations = ~11 days. Which isn't good, IMO: it means that a mid-sized miner can mount double-spends from time to time, and he doesn't even need to spend much on electricity.

However, if this isn't good enough for you, why not just wait for more confirmations. Suppose you want to do a 50 block reorg, you will need to divide your coins across 50 separate accounts. To mine a longer chain over 50 consecutive blocks with non-negligible probability, you would need about 25% of hashing power.

I agree that getting 50+ blocks in a row is not a small feat. But still, this design is weaker than pure PoW for relatively short reorgs. I.e. if we adopt it, we would have to wait for more confirmations for each payment. (Same is true for PPCoin and PoA.)

[cunicula]

Mining several blocks in a row is much more difficult. In order to mine 6 blocks in a row, then you will need to divide your 99% across six separate accounts. Because of this division, your difficulty target will only be 99/6=16.5 times easier than the average for rest of the mining world. In order to mine six blocks in a row with >50% prob, you will then need about 6% of hashing power.

Seems to be about right except number 99%.

Let's re-purpose my previous example: there are 94 hashing units which have 100 coin-confirmations on average each, thus their cumulative hashing power is 94*100 = 9400.
I have 6 hashing units with 1600 coin-confirmations each, my hashing power is 6*1600 = 9600. So I can perform 51% attack and mine next 6 blocks with ~50% probability.

[Edit: I am actually confused here. ]

No, you are confused. You really do need something like 99% of the outstanding stock of coin-confirmations and 6% of hashing power to double-spend. The problem has to be analyzed block by block. There is an important asymmetry between the attacker's problem and the legit miner's problem that you are ignoring.

As an attacker, you have 1600 coin confirmations to spend for block 1. The other 8000 have to wait in reserve for blocks 2,3,4,5, and 6 (1600 per block). If you spend all of your stock on block 1, you will have no hope of continuing the chain to blocks 2,3,...

As a legit miner, you do not need (or want) to horde coin confirmations. Hording causes you to lose mining revenue. Hording is only useful for attack purposes.  Therefore, you would attempt to mine with all 9400 coin confirmations for every individual block. (or rather 94 different miners will want to mine will all of their 100 coin-confirmations, it doesn't matter at all whether they are coordinated or not)

The attacker is at a gross disadvantage with only 14.5% of the stock of outstanding coin confirmations to spend on each block. Given his low share in the outstanding coin-confirmation stock, he would require much more hashing power than the defenders to succeed. The sufficient number is not 6 units of hashing power, it is (85.5/14.5)*94=554 units of hashing power.

Contrary to what you are trying to say, double-spending is very hard in this system, even for a short interval such as 6 blocks.

[cunicula]

It is true that they have 50% chance of mining next block, but note that if rest-of-the-world actually wins, it now has 0% of confirmations and attacker has 100%. So you need to consider a scenario where that 1% of coin-confirmation is spread over many accounts, and each such account gives only a minuscule bonus to hashing power.

[Edit: This is wrong, please ignore. It does matter if the money is divided across many people when analysing short reorgs. It matters less and less as reorgs become longer and longer and doesn't matter at all for permanent control]

No, the rest-of-the-world is divided among many miners. Say there are 1000 identical people in the rest-of-the-world. Every one of them is contributing to defense against the attacker. Ex-post only of them actually suffers a loss in coin-confirmations when each block is found. The others accumulate coin confirmations. For the rest-of-the-world, it is completely irrelevant for security purposes if the money is concentrated in a few accounts or divided across many. There is no need to analyze the two situations separately.


I'm going to get frustrated here soon. Anyone understand me and want to help explain?

[killerstorm]

As an attacker, you have 1600 coin confirmations to spend for block 1. The other 8000 have to wait in reserve for blocks 2,3,4,5, and 6 (1600 per block). If you spend all of your stock on block 1, you will have no hope of continuing the chain to blocks 2,3,...

Yes. I have 6 accounts with 1 coin in each account. I wait for 1600 confirmations (~11 days), now I have 1600 coin-confirmations in each account, 9600 coin-confirmations.

At the same time rest of hashing units (which act independently) each have about 100 confirmations on average, 94*100 = 9400 total.

I have a hashing power of 9600 and rest of network has hashing power of 9400 if each hashing unit is hashing on its own. Thus, I win having just ~50% of total coin-confirmations stock and 6% of hashing power.

So, again, a person owning 6% of coins and 6% of hashing power (which he can buy temporarily from Amazon, so only ownership of coins is required) can do 6-block deep reorg in 11 days.

Likewise a person having 5% of coins and 5% of hashing power can do a 50 block deep reorg in 138 days.

As a legit miner, you do not need (or want) to horde coin confirmations. Hording causes you to lose mining revenue. Hording is only useful for attack purposes.  Therefore, you would attempt to mine with all 9400 coin confirmations for every individual block. (or rather 94 different miners will want to mine will all of their 100 coin-confirmations, it doesn't matter at all whether they are coordinated or not)

If a miner has 9400 coin-confirmations in one account and he has 94 units of hashing power, he has an apparent 883600 hashing power.

If there are 94 miners which have 100 coin-confirmations each on average, and each one uses 1 unit of hashing power, apparent hashing power of a system is 94*100 = 9400.

A model where there are 94 miners is correct because on the next block they have an apparent hash power of 9400 again, i.e. hashing power is stable.

But a single miner will have 0 coin-confirmations for the second block, so winning a string of blocks afterwards would be trivial.

Say there are 1000 identical people in the rest-of-the-world. Every one of them is contributing to defense

Then when you say that rest of the network has 1% of coin-confirmations it means that each person has 0.001% of coin-confirmations. You need to plug this value into hash-target calculation, not the sum of coin-confirmations they have.

I'm going to get frustrated here soon. Anyone understand me and want to help explain

I find it rather strange that I have to explain that in a system where build-up of coin-confirmations compensates for lack of hashing power attacker can perform a double-spend if he waits enough. It is absolutely obvious.

I have no interest in further discussion. I've already demonstrated that your system if faulty with numbers. There is no need to explain me anything.

If you still don't get it please re-read my message enough times.

[cunicula]

Then when you say that rest of the network has 1% of coin-confirmations it means that each person has 0.001% of coin-confirmations. You need to plug this value into hash-target calculation, not the sum of coin-confirmations they have.

Sorry, you are right and I screwed up again. Not much sleep recently, I apologize.  

As you point out, my numbers applied to a single legit miner and the short-term reorg situation is different when miners are numerous. For short-term reorgs, the correct reference is to a representative, average miner like you say. However, when the number of miners increases, the average number of coin-confirmations in a successfully mined block tends would tend to increase in a similar proportion. Thus, it is not obvious that it actually becomes progressively easier to do reorgs as mining becomes more atomistic. We need to analyze the entire system to get an answer here.


Take the 50-50 weighting. For simplicity normalize total coins and hashing power to 1.

Suppose there is one legit miner who owns c 0<c<1 coins and x, 0<x<1, hashing power.  The legit miner maximizes block output per unit time.
There is also one attacker who controls 1-c of the coins and 1-x of the hashing power. The attacker maximizes 6 block reorgs. How often can the attacker double spend?

Excluding periodic reorgs, the legit miner will consecutively mine every single block with c coin-confirmations. The legit miner's voting power is xc. The attacker will need to exceed this for 6 consecutive blocks to do a reorg. Let w be the number of blocks the attacker waits between attacks. The attacker's coin-confirmations are w(1-c). The attacker is tied with the legit miner if w*(1-c)*(1-x)= 6xc. Solving for w indicates how long the attacker need to wait between attacks. w=6xc/[(1-c)(1-x)]

Thus, if the attacker has 5% of coins (c=0.95) and 5% of hashing power (x=0.95), he can attack every 2166 blocks. That is about once every 15 days. Attacking generates 6 blocks. Legit mining would generate 0.05*2166=108 blocks. There is a sacrifice of 102 blocks to facilitate attacks. Each attack pays off if it facilitates a theft equivalent in value to 102 block rewards.

What if mining is more atomized than this. Suppose there are n identical legit miners, who own nc coins in total, 0<nc<1, and nx hashing power in total, 0<nx<1. The legit miners maximize block output per unit time.
There is also one attacker who controls 1-nc of the coins and 1-nx of the hashing power. The attacker maximizes 6 block reorgs. How often can the attacker double spend?

Excluding periodic reorgs, each legit miner will mine once every n blocks with nc coin coin-confirmations. An individual legit miner's mining power will be nxc. Collectively, the n individual miners have mining power of n^2xc. The attacker will need to exceed this collective mining power for 6 consecutive blocks to do a reorg. Let w be the number of blocks the attacker waits between attacks. The attacker's coin-confirmations are w(1-nc). The attacker is tied with the legit miners if w*(1-nc)*(1-nx)= 6n^2xc. Solving for w indicates how long the attacker need to wait between attacks. w=6(nx)(xc))/[(1-nc)(1-nx)].

Thus, if the attacker has 5% of coins (nc=0.95) and 5% of hashing power (nx=0.95), again he can attack every 2166 blocks. Atomizing mining doesn't change anything.


Suppose we decide that this is to frequent and want to enforce a threshold of once a year (every 52560 blocks) in this scenario (nc=0.95) (nx=0.95). This would mean that each 6 block reorg would need to pay off 2622 blocks rewards in theft value to payoff. Remember the attacker is forgoing 2622 mined blocks in order to prepare each double spend. Seems like a lot.

To achieve this, the stake weighting needs to be lowered.  We started out with 50-50, we would achieve this target if we reduce stake to 41 and raise work to 59. Perhaps 40 stake-60 work is a good split.

Notes:

We must find g such that 52560=2166^g
g=ln 52560/ln2166
g=1.41520944787
(1-p)/p=g (where p is the stake weighting and 1-p is the work weighting)
p=1/2.41520944787=0.41

[cunicula]

The relevant question is how long an attacker would need to wait to perform one 6 block reorg. Is it hours, days, months, years, decades, or centuries? Say the answer is 1 day. Surely, there is no way an attacks could occur that frequently with the 50-50 weighting. However, for the purpose of argument, let's assume they could. The problem is simple to fix. Tweak the weighting to offer stronger protection against double spends and weaker protection against permanent control. Let's go through the numbers for an 80 work 20 stake weighting and see how waiting time compares to the 50-50 case. Remember, with 50-50, we assumed  attacks were possible once a day.

Formula Becomes [target/(coin-confirmations)^0.25]


Temporary Double-Spends

Coin-confirmations in n prepared accounts are 1000 times that of an average miners' coin confirmations -> attacker needs at least 15% of total hashing power for reorg of length n
      
Waiting time has increased by about 200-fold relative to the 50 work 50 stake scenario, where you just needed about a 5-fold coin confirmation edge to succeed with 15% of hashing power.
1 day of waiting becomes 0.5 years.

Coin-confirmations in n prepared accounts are 1,000,000 times that of an average miners' coin confirmations, attacker needs at least 3% of total hashing power for reorg of length n

Waiting time has increased by about 30,000-fold relative to the 50 work 50 stake scenario, where you just needed about a 30-fold coin confirmation edge to succeed with 3% of hashing power.
1 day of waiting now becomes 82 years.

Coin-confirmations in n prepared accounts are 1,000,000,000 times that of an average miners' coin confirmations, attacker needs at least 0.6% of total hashing power for reorg of length n

Waiting time has increased by about 6-million fold relative to the 50 work 50 stake scenario, where you just needed a 200-fold coin confirmation edge to succeed with 0.5% of hashing power.
1 day becomes 16,000 years.


Permanent Control

Hashing Power is close to 100% of network total -> need ownership of 0.5^(80/20)=3.125% of total coins in circulation to exert permanent 51% control

That's not as good as before. With 50-50, you needed 25% of the money supply and 100% of hashing power. With 20-80. you need 3.125% of the money supply and 100% of hashing power. This is still a tall order. Even if the total hashrate becomes very small and trivial to acquire, the 3.25% remains a very costly barrier to permanent control. That is the point of proof of stake. My guess is that there is a happy medium somewhere. I'm not sure if it is 20-80, 50-50, or 80-20, though.

sorry for posting all this crap everyone, just wanted to make the arithmetic as transparent as possible; best way to catch errors