Proof of Activity Proposal

[cunicula]

(Also it's worth noting that with your system top hash-rate equivalent is achieved when all money is in hands of one miner, as he will spend all his hasing power on account which highest coin-confirmations, while many independent miners would also waste their hashes on accounts with low coin-confirmations.)

I'm answering here because I don't want to clutter's Sunny's thread with irrelevant material. It encourages him to ignore our criticisms.

I don't understand what you are saying here. The amount of hashing you spend on hashing to maximize profits is subtle in my system. If you have an explicit formula, it could be really useful.

I only have results based on simulation. see https://bitcointalk.org/index.php?topic=68213.msg801253#msg801253 The simulation suggests that output per unit time is constant-returns-to-scale Cobb-Douglas. This implies that you optimally spend a fraction p of your mining investment on stake (where p is the proof-of-stake weighting) and 1-p on hashing power. Provided that perfect competition holds, this division is invariant to the scale of investment. I'm ignoring electricity use here and thinking about mining as powered by electricity efficient but capital-intensive ASICs.

I don't think scale matters at all unless someone is big enough to affect the aggregate hash rate. As in bitcon, domination big players affecting the aggregate hash rate decreases aggregate investment. You seem to be suggesting the opposite.

[killerstorm]

Apparently cluttering coblee's thread is OK

No, it's a different thing.

Here's an example with concrete numbers. Suppose there are 100 identical hashing units each having one coin.

If they all belong to one guy and he uses one account, then he will produce all blocks and his account always has 100 coin-confirmations (100 coins * 1 confirmation each). Thus apparent hashpower is 100*100 = 10000.

Suppose that guy wants to have 100 accounts for some reason. OK, no problem: he will put all of his hash-power into account which has most coin-confirmations, and usually that would be one with 100 coin-confirmations (1 coin which waited for 100 confirmations). So apparent hash-power is 100*100 again.

Now suppose all these accounts belong to different miners who do not cooperate: i.e. they won't work on each other's shares. Suppose that number of confirmations in each account is uniform 1..100 (it is not true, see below). In this case there are some miners who work on 100 coin-confirmation account, but also there are miners who work on 1 coin-confirmation accounts. On average there are 50 coin-confirmations, so apparent hashpower is 50*100.

But is assumption about uniform 1..100 true? Not really. There might be accounts with more than 100 coin-confirmations. But also note that to get to 100 confirmations account needs to get through 100 rounds, and it is likely to be reset to 1 confirmation somewhere in the middle. So distribution would be biases towards smaller accounts.

I've done a simulation, and it appears that mean confirmations for 100 independent miners is 66, while median is around 50. Moreover, these numbers scale linearly on the number of miners, i.e. 10 miners have around 6.6 confirmations mean.

So configuration with many independent miners is about 33% less efficient than one miner. This matches the general idea that cooperating miners will be better at resource allocation.

Now we can reduce double-spend analysis to a situation with one miner.

Suppose miner has h hashpower and c coins. His apparent hashpower is h*c.

I want to match this with h', c' and bonus b: h*c = h' * c' * b. Morover, to do n-deep double-spend, I need to do this with just c'/n coins, so:

Code:

b = (h/h')*(c/c')/n

So I have have 5% of coins and 5% of hashpower and want to do 50-deep reorg, I need a bonus of 20*20*50 = 20000 which matches previous results. (Which I obtained somewhat incorrectly). With 144 confirmations per day and equal weighting it is 139 days.

But in reality if there are many independent miners I get something like 33% bonus.

Now of course if you have c^0.25 bonus formula it is 20000^4, totally unfeasible. But smaller reorg is doable.

[cunicula]

Anyone have thoughts on the following mixed proof-of-work proof-of-stake system that incorporates a variant of Colbee's idea for a lottery. I personally prefer that
all blocks follow a symmetric system because it avoids unnecessary communication of blocks that don't provide useful security.

1) Lucky number

There is a lucky number each round. Lucky number should be a public random number that cannot be controlled without vast resources. Say it is a hash of the proof-of-work submitted in the last 100 blocks.

2) One lottery draw per coin confirmation

Each public address containing one or more coin confirmations provides lottery draw(s) which can be compared against the lucky number. Say an address k has c coin confirmations. This address k can then be used for c different lottery draws.

e.g. {lottery draw} = {hash (public key of address k,j)} where j = 1,2, ... ,  c if c>=1 and null set otherwise

Thus you get one lottery draw per coin confirmation. You only care about the best one in each round. Note that these draws are invariant over time. A set of possible draws can be computed once and for all time when the address is generated. They are public info, but only the address owner needs to care about them.

3) Each miner has a unique best lottery draw in the current round

In each round, a good lottery draw is close to the lucky number. Say we measure closeness as simple distance.

V(lottery draw, lucky number)= |(lucky number - lottery draw)|

A miner searches over his set of lottery draws and finds the one closest to the lucky lottery number. This determines his stake value, V', in the current round.

V*(lucky number) = min [V(lottery draw, lucky number)] in the set {lottery draw}

He only cares about the best possible lottery draw he has out of all of his addresses. Given that the draws are all pre-generated, finding his best draw should not be time-consuming.

4)  The miner faces a proof-of-work target. Most likely he can just connect to a pool and pay for access to their hashes.

target =  difficulty*V'^(p) where p >= 0

If p=0, then it is just like bitcoin. As p increases getting a good draw decreases the target more and more and proof-of-work becomes less and less important.

5) Block submission.

Miner submits proof-of-work that meets target and signs the block using the private key to his winning address. Anyone can verify that his proof-of-work, public key combination meets the target. As usual, difficulty is revised periodically to keep the block spacing to an average of 10 minutes.

I think the point of work here is to
a) manage the timing of block generation
b) ensure that the system cannot stop permanently because of an "unlucky" lucky number
c) generate lucky numbers


[edit: in the above, you could also replace one draw per coin-confirmations with one draw per coin and it wouldn't change much. One draw per coin-confirmation makes it easier for people with small balances to participate.]

[ripper234]

Can someone provide a tl;dr of what is the key problem in PoS that PoA is trying to solve, and how does it solve it?

[ripper234]

Please take a look at ThePiachu's answer and my comments. I think I now understand the difference between PoA and PoS, but I'm not sure what's the benefit of PoA.

[killerstorm]

I think iddo provided a good summary:

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.

So PoA is essentially one of possible implementations of PoS, presumably the advantage is that it is easier to implement. However, it depends on what we are comparing it to...

For example, PPCoin's PoS isn't particularly complex (it is already implemented) and it can be made about as secure as PoA. (Particularly, it should be PoW+PoS, not pure PoS.)

One can say that PoA can be a drop-in upgrade, but I think PPCoin demonstrate that PoS can be a drop-in upgrade too.

So this is largely a matter of aesthetics.

[iddo]

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.

[killerstorm]

Where does killerstorm's 1/q number come from, at https://bitcointalk.org/index.php?topic=102342.msg1139483#msg1139483 ?

It just means that attack is probabilistic, i.e. I do not need to attack at certain time with 100% certainty, but chances of success of 1/q are OK for my goals. q is something like "time I can spend on doing one attack on PPCoin, measured in blocks". (Suppose number of successful attacks has binomial distribution, n = q, p = 1/q. Then mean number of successful attacks in q blocks is q * (1/q) = 1.)

If you want 1 successful attack per week, choose q = 144*7=1008.

[iddo]

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?

[cunicula]

We need to make a list of objectives and then identify a proposal which best satisfies them. It would be better to agree on objectives first and then try to find a framework which realizes them. Otherwise people will talk past one another. Everyone is biased towards their own ideas.

Here are my own objectives:

1) Very expensive to perform a persistent 51% attack even with low aggregate hash rate.
2) Selling voting power to a third party is costly/personally risky.
3) 6 conf txns can be trusted even if an attacker controls 51% of work but no stake.
4) Attacker cannot perform 6-block reorgs with monthly frequency without controlling at least 10% of work and 10% of stake.
5) Constant returns to scale. i.e. Returns you get from 2% of stake and 2% of hashing power are approximately double those of 1% of stake and 1% of hashing power.
6) Voting for a fork which is not the main chain is costly.
7) Protocol rules are simple and transparent.

Do these seem reasonable to everyone else? Is there something which should be added to the list?

[iddo]

We need to make a list of objectives and then identify a proposal which best satisfies them. It would be better to agree on objectives first and then try to find a framework which realizes them. Otherwise people will talk past one another. Everyone is biased towards their own ideas.

Here are my own objectives:

1) Very expensive to perform a persistent 51% attack even with low aggregate hash rate.
2) Selling voting power to a third party is costly/personally risky.
3) 6 conf txns can be trusted even if an attacker controls 51% of work but no stake.
4) Attacker cannot perform 6-block reorgs with monthly frequency without controlling at least 10% of work and 10% of stake.
5) Constant returns to scale. i.e. Returns you get from 2% of stake and 2% of hashing power are approximately double those of 1% of stake and 1% of hashing power.
6) Voting for a fork which is not the main chain is costly.
7) Protocol rules are simple and transparent.

Do these seem reasonable to everyone else? Is there something which should be added to the list?

I wish that we could come up with a protocol that is at least as secure as pure-PoW, with extra proof-of-stake properties that may enhance the security, but don't introduce new security risks when compared to pure-PoW.
If the proof-of-stake signatures become valid only after many more blocks compared to the default 6-conf double-spending safety length, then the proof-of-stake can be thought of just as replacing the need for hardcoded developers checkpoints.
With Litecoin we could have the luxury of switching from default 6-conf to default 24-conf, so there's room to play with the numbers.

If we agree that (2) is risky then signing-key delegation is probably a bad idea (mentioned in post #14 here). It also probably requires linkages on the blockchain (though one linkage per deterministic wallet can be done), so miners might reasonably expect fees for the extra work. I doubt it's possible without linkages, I tried to ask gmaxwell about his comments (link), but he hasn't replied.
So it'd mean that stakeholders should either use an unencrypted wallet, or maybe they could register their email address on some blockexplorer website and receive notification when they should provide their proof-of-stake signature (for lucky-num proof-of-stake schemes such as PoA).

There's a contradiction between allowing stakeholders who aren't running their client 24/7 with unencrypted wallet to participate (by having a long time/blocks limit to provide the proof-of-stake signature), and attack scenarios like killerstorm's double-spending bribes service (where we'd rather allow only a short time/blocks limit to provide the proof-of-stake signature).

In (6) I suppose you mean that it should be costly for attackers to vote in competing forks, because we shouldn't punish honest miners who saw the losing branch first and signed it. But with lucky-num schemes this scenario doesn't occur anyway (discussed in post #47).

Regarding (4), with PoA an attacker with 10% of hashpower and 10% of stake cannot do anything, he's actually in worse shape compared to an attacker on pure-PoW network with 10% hashpower. But killerstorm conjectures that the attacker can get >50% stake using bribes service because stakeholders aren't honest, so maybe we should brainstorm about external remedies to handle such non-honest stakeholders, like blacklisting their stake, because the bribes service cannot be anonymous.

I would like to add one very important property to your list (though it might be considered orthogonal to proof-of-stake), which is security against attackers with large hashpower who try to deny txns (link). Security from this kind of attack is arguably even more important than security from double-spending attacks. Any thoughts on the best ways to implement this?

[cunicula]

If we agree that (2) is risky then signing-key delegation is probably a bad idea (mentioned in post #14 here).

A middle-of-the-road approach is appropriate here. Signers should have some skin in the game, but not too much.

Here is what I mean:
Two keys controlling the coins: 1) Full Spend Key 2) Sign/Withdrawal Limit Key
The withdrawal limit key can only include 1/k of the private key balance in any one txn (txns with this key must send k coins to the input address(es) for every 1 coin sent to an external address). That means it would take k blocks to deplete the full balance using the limited spend key. k could be user specified, but would have to be lower than a maximum value (say 10,000). Selling your withdrawal limit key to someone else would be very risky. Exposing your withdrawal limit key to the internet would be slightly risky too, but it is a limited risk because you can always invalidate key 2 using key 1. Withdrawal limits are a useful feature anyways.

In (6) I suppose you mean that it should be costly for attackers to vote in competing forks, because we shouldn't punish honest miners who saw the losing branch first and signed it. But with lucky-num schemes this scenario doesn't occur anyway (discussed in post #47).

PoA fails on point 6. As does every other PoS proposal except for my own. I'm an economist. Economists always assume profit-maximization. If you tell them that honest miners exist, they will say you're full of shit. Everyone is greedy according to economists. If you accept that (and I think the system should operate on that premise), proof-of-stake signing needs to involve opportunity cost in order for it to function as a branch selection mechanism. It needs to be more costly to sign two forks than it is to sign one fork. Otherwise, signing every fork you see is the strictly dominant strategy for miners. If all forks are signed, proof-of-stake will be completely useless as a security mechanism. To solve this, stake signatures need to be jointly submitted with proof-of-work.

This problem applies to Meni's proposal, PPCcoin, POA, etc. Killerstorm's suggested improvements. None of those ideas involve joint submission of work and stake. That is not good. Submission should be joint. Otherwise proof-of-stake has no theoretical purpose.

I'm not the only person who is hung up on this issue:
https://en.bitcoin.it/wiki/Talk:Proof_of_Stake   - look at the first comment by Ian Stewart (you can ignore the rest)
Luke-Jr puts it well here:

Proof-of-stake (at least all existing attempts I know of) also allows miners to use it for attacks in parallel to the legitimate blockchain. That is, there is no cost to attempt to fork the blockchain. Incentively speaking, this means rational miners should mine every chain that does not hurt them personally.

Also in this thread:

As far as the overall design goes, it seems to me that it has a weakness I'd call "unavailability of the preferable alternative" or a hobson's-choice-attack that I think exists in all the stochastic PoS schemes I've looked at.

I would like to add one very important property to your list (though it might be considered orthogonal to proof-of-stake), which is security against attackers with large hashpower who try to deny txns (link). Security from this kind of attack is arguably even more important than security from double-spending attacks. Any thoughts on the best ways to implement this?

Yes, I agree completely. In fact this is what I mean by persistent 51% attack, that is point (1). In my view, solving this is the whole point of proof-of-stake. Double spends are a side issue (albeit an important one).

[cunicula]

Any thoughts on the best ways to implement this?

I have a very simple proposal which an elaboration of the one in the proof-of-stake wiki. The proposal in the wiki is weak to short reorgs if the proof-of-stake weighting is high (see criticism by killerstorm). This is simple to fix, but requires introducing higher weighting on proof-of-work. However, it is possible to have the best of both worlds. To do this, include two types of blocks with type-specific weightings and difficulty settings. Block A can have a 0.1 stake weighting and a 0.9 work weighting. Block B can have a 0.9 stake weighting and a 0.1 work weighting. To be valid, blocks must be added in an ABABABAB pattern. Block A difficulty targets an average waiting time for each A block of x minutes.  Block B difficulty targets an average waiting time for each B block of x minutes. Users trust a txn once it receives 6 confirmations (i.e. 3 of type A and 3 of type B).

[yaffare]

In my opinion the only thing you all do is increase the difficulty of performing an attack.

This does not solve anything.

We must find a general way to completely eliminate attacks. If [richguy/country] wants to takeover bitcoin, they dont care if its
1 or 100 billion to spend for hardware.

I made a proposal by myself, but this is another topic.

[iddo]

If we agree that (2) is risky then signing-key delegation is probably a bad idea (mentioned in post #14 here).

A middle-of-the-road approach is appropriate here. Signers should have some skin in the game, but not too much.

Here is what I mean:
Two keys controlling the coins: 1) Full Spend Key 2) Sign/Withdrawal Limit Key
The withdrawal limit key can only include 1/k of the private key balance in any one txn (txns with this key must send k coins to the input address(es) for every 1 coin sent to an external address). That means it would take k blocks to deplete the full balance using the limited spend key. k could be user specified, but would have to be lower than a maximum value (say 10,000). Selling your withdrawal limit key to someone else would be very risky. Exposing your withdrawal limit key to the internet would be slightly risky too, but it is a limited risk because you can always invalidate key 2 using key 1. Withdrawal limits are a useful feature anyways.

Very interesting idea, delegating withdrawal-limited keys could answer coblee's concern. The exact behavior of the withdrawal limit can be debated, but the minimal limit has to be high enough to avoid delegating to that central signing entity from post #14. I agree that withdrawal-limited keys could be useful independently of proof-of-stake.
As for the implementation, I still think that the most straightforward option is that the proof-of-stake signature will sign an extra field with the delegated pubkey (i.e. this is where the linkage is established), and when using the corresponding delegated privkey you also specify the linkage block number, so the miners have to look at that older block to verify your (withdrawal-limited) signature. (earlier post on this).

In (6) I suppose you mean that it should be costly for attackers to vote in competing forks, because we shouldn't punish honest miners who saw the losing branch first and signed it. But with lucky-num schemes this scenario doesn't occur anyway (discussed in post #47).

PoA fails on point 6. As does every other PoS proposal except for my own. I'm an economist. Economists always assume profit-maximization. If you tell them that honest miners exist, they will say you're full of shit. Everyone is greedy according to economists. If you accept that (and I think the system should operate on that premise), proof-of-stake signing needs to involve opportunity cost in order for it to function as a branch selection mechanism. It needs to be more costly to sign two forks than it is to sign one fork. Otherwise, signing every fork you see is the strictly dominant strategy for miners. If all forks are signed, proof-of-stake will be completely useless as a security mechanism. To solve this, stake signatures need to be jointly submitted with proof-of-work.

I agreed earlier that we should assume that the majority is greedy rather than honest, but I'm less inclined to agree that stakeholders who participate in double-spending-bribes service are greedy rather than malicious. Also it might be risky because others could retaliate and blacklist your stake.
I agree that if stakeholders could provide their signatures to competing chains with impunity then the proof-of-stake scheme is worthless.
Any comments of my technical suggestion in post #47 for protocol behavior to deal with this issue? If the recommended safety length for double-spending protection is 6 confirms, and the protocol enforces that you cannot provide your proof-of-stake signature after 6 blocks, then you would select and sign only one branch (because signing multiple branches would be useless for the attacker).

I would like to add one very important property to your list (though it might be considered orthogonal to proof-of-stake), which is security against attackers with large hashpower who try to deny txns (link). Security from this kind of attack is arguably even more important than security from double-spending attacks. Any thoughts on the best ways to implement this?

Yes, I agree completely. In fact this is what I mean by persistent 51% attack, that is point (1). In my view, solving this is the whole point of proof-of-stake. Double spends are a side issue (albeit an important one).

Right, I now see that your point (1) meant to deal with this issue, apologies.
I also see that your next post #53 shows that this issue isn't necessarily unrelated to proof-of-stake, though it's still plausible that incorporating BDD could help too.
What would be the disadvantage of simply using pure-PoW for type A blocks?

[iddo]

We must find a general way to completely eliminate attacks.

This statement doesn't make sense. You can do brute-force attack on ECDSA with 2^128 iterations, to steal coins.

I made a proposal by myself, but this is another topic.

IMHO that proposal also doesn't make sense, allowing human discretion instead of using hardcoded protocol rules whenever a long re-org occurs is a terrible idea. See post #27 (and #26) here.

[cunicula]

[ If the recommended safety length for double-spending protection is 6 confirms, and the protocol enforces that you cannot provide your proof-of-stake signature after 6 blocks, then you would select and sign only one branch (because signing multiple branches would be useless for the attacker).

This doesn't help at all.

Assume you get a reward b for signing a branch and that the good branch ends up as the main chain with probability p. One of the bad branches will end up as the main chain with probability 1-p.

Suppose the official software allows you to sign only one branch. The expected payoff from signing the good branch is pb.

Now suppose unofficial software allows you to sign multiple branches. The expected reward payoff from signing multiple branches is b. Provided reorgs occur with positive probability, p > bp.
The unofficial client has strictly superior payoffs to the official client. Greedy people like it. Why should they care if they are signing a double-spend? It not going to be their coin at risk.

If everyone uses the unofficial client, proof-of-stake has absolutely no security functionality whatsoever. Use of the official client cannot be forced. Essentially you are relying on laziness and irrationality to secure the blockchain.

How do you prevent this? Stake signatures must be accompanied by proof-of-work. The proof-of-work costs w to create.

Say p(i) is the probability that branch i emerges as the main chain. The expected payoff from signing a branch i is p(i)b-w. You sign if p(i)b>=w and you do not sign otherwise. In other words, you only sign the main chain. You do not sign attackers chains. Attackers have to deal with the fact that you only sign their crap if you expect their attack to succeed with high probability. This makes it quite difficult to get a successful attack going.

Proof-of-stake works as intended. My proposals have always incorporated this essential feature. None of the other proposals have bothered to include it. PPCoin does not have it either.
 

[iddo]

uses the unofficial client, proof-of-stake has absolutely no security functionality whatsoever.

The official client behavior is that after you've signed one branch, you'll sign a competing branch only if you discover that this competing branch is winning (excluding the signature that you'd provide is probably the better rule).
If the unofficial client signs all the branches that it sees, then using the unofficial client is either greedy or malicious (let's not differentiate for the two for the moment), and if everyone uses the unofficial client then the network is equivalent to pure-PoW. This is the objective that I'm trying to achieve, i.e. that if the stakeholders are honest then the network is more secure than pure-PoW, and if the stakeholders are greedy/malicious then the network is at least as secure as pure-PoW.

Your comments appear to refer to the scenario where greedy stakeholders sign shorter public branches, to maximize their reward probability. Note that the double-spending attack scenario is different, there the attacker prepares 6-blocks branch in secret, bribes stakeholders to sign his secret branch, and then broadcasts his branch after it's at least 6-blocks deep and is the winning branch. If stakeholders refuse the bribe then they earn their regular reward on the honest network, if they accept the bribe then the attacker supposedly offers them a higher reward, but (unlike what killerstorm described) they cannot participate in the attack and then expect to collect the regular reward on the honest network in case the attack failed, because the attacker wouldn't want to pay stakeholders who also sign the honest branch in less than 6-blocks and therefore don't contribute to his attack. In other words, this kind of double-spending-bribes service is exactly the same as what can be achieved with pure-PoW network, as described in post #47.

If we could really agree that we have a protocol that is always at least as secure as pure-PoW, and more secure if stakeholders are honest, then IMHO it'd be major progress. Edit: Of course I don't rule out the possibility that your protocol would be even better, I'm just saying that if we could establish a protocol that is at least as secure as pure-PoW, then we would have a clear milestone that we could try to improve upon.
The problem is that even if you agreed with everything I said here, technically it's still unclear whether we could have a protocol that achieves these properties. Did you also consider my comments on how the protocol could enforce 6-blocks window for signing?

[cunicula]

The idea that the double-spend will need to be secret is silly. Profitable double-spends are likely to involve trading in financial assets. Other kinds of double-spends probably won't generate a large enough payoff to be worthwhile. All you will want to do is reverse an unfavorable trade. You don't need to steal the asset you traded. These double spends can be completely public. The public double spend problem could be made more severe by PoA.

Say for example you buy a large amount of USD and the BTC price goes up. You now regret your USD purchase and want execute a double spend.

90% of miners use my unofficial client and thus play no role in branch selection. The remaining 10% participate in the txn reversal service. The attacker pays them to withhold signatures from the good chain and only add them to his branch. The good branch will have 90% of possible signatures. The bad branch will have 100% of possible signatures. Voila double spend. The double spend is made easier by proof-of-stake.

To fix this, you need to introduce incentives which make use of the unofficial client unprofitable. i.e. submitting a stake signature must require an investment in work.

In game theory, signals (read stake signatures) which have no opportunity cost are called "cheap talk". In many kinds of games, "cheap talk" does not help players achieve good outcomes. By contrast, costly signals are more effective. That is the basic principle involved here.

[cunicula]

What would be the disadvantage of simply using pure-PoW for type A blocks?

It would work. This choice is not a big deal. I would need to simulate different scenarios before I could advocate for a specific weighting.

Main point:
Block A mostly or all proof-of-work
Block B mostly, but not all proof-of-stake

I can't be more precise about 'mostly' without some simulations.