Proof of Activity Proposal

[killerstorm]

I didn't ignore that fact, I used the terminology "active stake" to refer to stakeholders who are online. Apologies that I wasn't clear enough.
Using the same terminology of post #156, you describe a scenario where the attacker has 33/50 = 66% of the active stake, while the honest network has 17/50 = 34% of the active stake. Obviously, if the attacker has the majority of the active stake then this protocol becomes much less secure than Bitcoin's pure-PoW.

Yup. The problem is that amount of active stake might vary greatly, so attacker having minority of total coins might have a majority of active stake at some point.

Edit: Also, I'm not sure whether the scenario that you were thinking of fits the numbers that you mentioned.  If we assume that the txn fees and signing-key limited-withdrawal delegation incentivize say 50% participation level of the honest stakeholders, and the attacker has 33% of the total stake, then the total honest stake is 66% which means that the active+honest stake is 33%, so the attacker still doesn't have an advantage over the honest network (unless he has >50% hashpower). In other words, the attacker would need more than 1/3 of the total stake in order to gain an advantage, assuming 50% participation level.

Ah, OK.

I wouldn't worry about double spends coming from someone with USD$20 million of bitcoin. He will be scrambling to keep the network secure and his fortune safe. Only an idiot would try to double spend from this position.

Well, I dunno... What if he borrows bitcoins to short them? Or rents the stake?

Suppose I have a lot of USD. I would try to borrow or rent as much BTC as possible (I have a lot of collateral and can offer all sorts of legal protections), do some double-spends. Then sell BTC.

Exchange rate plummets from panic and perceived lack of security. I buy bitcoins back at low price. and return them.

[cbeast]

For a long time I was considering a way to "balance" Proof-of-Work. I was trying to work out a way to offer some way to reward "loyal" Bitcoin network supporters on a merit system. The ideas keep coming back to something akin to a proof-of-stake, which I reject wholeheartedly. It all comes down to the nature of competition. Then I realized I was looking at it all wrong. This isn't a game like checkers or rock-scissors-paper, Bitcoin is chess. The Bitcoin Network is merely the board. The pieces are the physical and virtual connectors on the network itself. Miners are merely pieces. The whole damn thing is just too complex for anyone to solve for a simple solution.

The nature of competition is not just to be bigger, faster, and stronger. It's to be smarter and more adaptable. Anyone who thinks they have it all figured out is fooling themselves. I think that's what the math is saying when Satoshi chose the protocols that went into Bitcoin. You can't beat all the other players, because the protocol has enough flexibility to adapt to any game anyone tries to play against it. The difficulty factor, the ten minute propagation, the inflation rate, etc. all make Bitcoin a very difficult system to game as it scales. Other players will see moves coming and have time to make counter moves to protect their own interests. Changing the protocol to be anything other than being open for competition from anyone would be like poisoning your own watering hole just to kill your rival.

[iddo]

cunicula, when you're back, please take a look in particular at post #157, and killerstorm's post #161

I updated post #158 with some more info regarding our best PoA protocol so far.
More peer review please? Anyone?

[iddo]

About reviving lost coins: cunicula said that one of the features of voluntary PoA signatures is that it provides a useful mechanism to revive dead coins, but I suspect that a similar mechanism of equivalent usefulness could be easily achieved with pure-PoW. I realize that it's arguable whether reviving dead coins is a desirable property, and that there have been several threads about it here in the past (BTW what's the best thread to look at?).
Here is another idea on how to do it with Bitcoin's pure-PoW: a special "bet" txn could be added to the protocol, where you can spend (for example) X/10 coins to bet that an address that holds X coins is dead. During the next Y blocks, those X/10 coins are locked. If that address with X coins didn't move its coins within Y blocks, then you receive those X coins. If that address moved its coins within Y blocks, then that address receives your X/10 coins. The client software could notify users that a bet against their address took place, and/or if it's a "saving account" address that isn't online then you could register on websites (e.g. online wallet websites) to get email notification when a bet against you took place.
I think that the main negative implication of this idea is that a thief wouldn't need to actually obtain your privkeys, but instead it'd be enough for the thief to somehow destroy your privkeys, and then bet against you. Also, if someone has inside knowledge that you wouldn't be around for the next Y blocks, then he could steal your coins.
So instead of having to spend X/10 coins to place the bet, the protocol could specify that you may place the bet for a small fee, and you'd only receive twice the fee's amount if you win, and the rest of the X coins would be spread among the miners over a long time frame (for example X/1000 added to the block reward in the next 1000 blocks). If the address that you bet against did move its coins, then it receives your fee. In other words, if you lose your privkey/wallet that controls X coins, you couldn't get those coins back, but there wouldn't be monetary deflation.

[iddo]

I didn't ignore that fact, I used the terminology "active stake" to refer to stakeholders who are online. Apologies that I wasn't clear enough.
Using the same terminology of post #156, you describe a scenario where the attacker has 33/50 = 66% of the active stake, while the honest network has 17/50 = 34% of the active stake. Obviously, if the attacker has the majority of the active stake then this protocol becomes much less secure than Bitcoin's pure-PoW.

Yup. The problem is that amount of active stake might vary greatly, so attacker having minority of total coins might have a majority of active stake at some point.

It could be helpful to consider why this isn't a concern with Bitcoin's pure-PoW: suppose an attacker has e.g. 100 gigahash/s while the honest network has e.g. 20 terahash/s, would it be reasonable to say that the honest hashpower might vary greatly so the attacker's 100 gigahash/s might become a majority at some point? I suppose that we agree that it's unreasonable to say that, because the miners have a financial incentive to participate in the network (in the form of the block reward and fees). Note that miners who immediately exchange the coins that they mine for fiat currency don't have an incentive to secure the network.
Similarly, if the financial incentive for stakeholders is big enough, then it would also unreasonable to say that the honest+active stake might vary greatly so the attacker might gain a majority of the active stake. The problem is that if the protocol rewards the stakeholders too much, then it'd result in a situation where the rich get richer, so we have to strike a balance between the desired stakeholders' participation level and the stakeholders' reward. I think that after the monetary inflation ends (or becomes insignificant in comparison to txn fees), it's straightforward to accomplish this balance by giving e.g. 1/2 of the fees to the miners and 1/2 of the fees to the stakeholders, but it's unclear to me how to achieve this balance while the block reward subsidy is still significant. Also note that it's reasonable to assume that stakeholders have a greater incentive to secure the network than miners, so this also contributes to the overall stakeholders' participation level.

I wouldn't worry about double spends coming from someone with USD$20 million of bitcoin. He will be scrambling to keep the network secure and his fortune safe. Only an idiot would try to double spend from this position.

Well, I dunno... What if he borrows bitcoins to short them? Or rents the stake?

Suppose I have a lot of USD. I would try to borrow or rent as much BTC as possible (I have a lot of collateral and can offer all sorts of legal protections), do some double-spends. Then sell BTC.

Exchange rate plummets from panic and perceived lack of security. I buy bitcoins back at low price. and return them.

I hope that cunicula would respond soon. Let me just remark that I think that there's a significant difference between the total amount coins that were generated, and the amount of coins that can be bought at the exchanges. So if the attack requires millions of coins (for example 20% of the total stake, see post #158), then we're good.

[iddo]

Another idea: the lucky stakeholder who creates the block is allowed to also include in it (in addition to the regular txns) all the other empty blocks that the miners broadcasted, i.e. empty blocks that extend the previous block but don't derive him as the lucky stakeholder. Note that an empty block for this purpose is actually just the pair (pubkey_addr, nonce) and we verify its validity by hash(nonce+hash(prev_block_hash, pubkey_addr)), so this idea doesn't bloat the blockchain too much. The benefit of this idea is that now at the difficulty retarget window we can measure the stakeholders' participation level by summing up the amount of all the empty blocks that were created since the last difficulty retarget. This way we could increase the relative reward of the stakeholders if their participation level is too low. Assuming 50% stakeholders' participation level, with 3 pseudorandom stakeholders we expect the stakeholder who creates the block to include 7 other empty blocks, therefore if we see at the retarget window that more than 7 empty blocks were added on average, then the stakeholders' participation level is less than 50%, so the protocol could specify that a higher ratio of the reward goes to the stakeholders relative to the miners during the next retarget window. This should incentivize the network to always converge to at least 50% stakeholders' participation level. If for example it's a protocol where there is 1 pseudorandom stakeholder instead of 3 that are derived for each mined block, then on average we expect 1 additional empty block to be included in each block (assuming 50% stakeholders' participation level), so again we could retarget the incentive of the stakeholders accordingly. Maybe the stakeholder who creates the block should receive a small reward for including those extra empty blocks, again as a higher ratio of the total reward relative to the miner who solved that block, in order to incentivize the stakeholders to add the extra empty blocks. Or maybe not, if the higher reward to all the stakeholders at the next difficulty retarget window is enough of an incentive.

Unrelated note: if we implement this PoA protocol in Litecoin then we'd probably need to go with the simplified variation that derives only 1 pseudorandom stakeholder (instead of 3), otherwise in order to get 2.5 minutes blocks we will need the miners to solve and broadcast a block after 150/8 = 18.75 seconds on average, assuming 50% stakeholders' participation level, and that would probably be too burdensome on the network.

[iddo]

PoA academic paper is now public:
http://eprint.iacr.org/2014/452
It was accepted to NetEcon/SIGMETRICS workshop:
http://www.eurecom.fr/~loiseau/W-PIN+NetEcon2014/program.html
Given that Charles Lee came up with the original core idea of PoA and helped with our further improvements, he encouraged me to try to implement PoA on a Litecoin testnet (separate from the testnet of the reference Litecoin client), and I'm interested in the Litecoin community reaction towards incorporating PoA into Litecoin.
In the paper we have some C++ and Python code for benchmarks, and I now plan the more efficient/complete implementation (with PoA protocol parameter N=1). If you're a programmer who'd like to join this effort then email me.
However, forking to obtain controversial goals (as opposed to benign softforks like BIP16) is risky, so it should only be done if needed for actual security improvements (regarding this, see in particular section 2.1 of the PoA paper). When our testnet implementation is ready, we will analyse and re-evaluate whether adding PoA to Litecoin makes sense.

Edit: presentation slides at http://www.cs.technion.ac.il/~idddo/PoAslides.pdf

[coinxed]

I like the idea of probabilistic PoS. I think the motivating problem is exaggerated but this could have other advantages too.

Another way (not sure if easier are harder to calculate) is to have the mod of the previous block hash deterministically pinpoint a single satoshi from a coinbase transaction. Then follow that satoshi as it travels from transaction to transaction until it reaches an unspent output. Then that output address will be selected as the next stakeholder. You can do this deterministically. Since the initial satoshi picked from a coinbase output is evenly distributed, the eventual selection will be evenly distributed also. I can explain more if people are interested in how this will work.

I don't think satoshis are tracked the way you think they do. If there's a 50 BTC coinbase which is split to two addresses you can't say "this satoshi went to output A and this satoshi went to output B". Not a major problem though, if you agree on a randomness seed (deterministically from the blockchain) you can simply trace the chain forward, in each step choosing a random output weighted by number of coins.

Satoshis are not tracked that way, but you could track it that way. You just need a deterministic way to do it. So just map every satoshi in the input to a satoshi in the output using an ordered 1 to 1 mapping. So for example, if you are looking at a transaction with an input of 50 BTC and 2 outputs of 25 BTC each and you are tracking the a satoshi that is located at 26.11111111 of 50 BTC, then you would follow the 1.11111111 satoshi in the 2nd output. Does that make sense?

Yes, you could do that. You need to be very careful though not only with the order of inputs and outputs, but also with the order of transactions in a block since the satoshi can end up as a tx fee.

Essentially this is equivalent to how I suggested to look at it.

There is a standard ordering of transactions in blocks, right? If not, having it alphabetized by address is fine. As long as all the nodes use the same deterministic way, we are good. Satoshi ending up as a fee is fully supported. Since those will just be sent to the miner's block reward and it can continue follow the path.

The only catch is it's possible for a miner to destroy coins by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi, maybe we decide that there's no stakeholder for the next block.

is it's possible for a miner to destroy coins by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi, maybe we decide that there's no

 for a miner to destroy coins by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi, maybe we decide that

 to destroy coins by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi, maybe we

 by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi,

 the full 50 btc in the coinbase. When that happens to our

 btc in the coinbase. When that happens

 the coinbase. When

 coinbase.

coinbase
coinbase
COINBASE
COINBASE!!!!
!!!!!COINBASE!!!!

[bitcad4u]

If this PoA is a solution to the 51% attack and IF litecoin forked to implement such a solution... I could see litecoin prices hovering back in the 50-100 dollar range.... we need to INVENT -and stop following bitcoin.  The next gen coins (like NXT) are all ranking up the charts because they are offering something NEW and not just being a faster BTC clone.

Do it coblee!


and lol @ post above - coinbase  when indeed

[instagibbs]

What happens if the N PoS "miners" aren't online? That seems quite likely very often.

[killerstorm]

What happens if the N PoS "miners" aren't online? That seems quite likely very often.

Let's say N=3 and only 10% of all stake is online. Suppose our target is to generate 1 block in 10 minutes on average.

Then PoW miners need to generate 1000 valid block headers in 10 minutes. Then, statistically, one of block headers will have all 3 stakeholders online.

So, basically, N=3 and 10% of active stake corresponds to 1000 times lower PoW difficulty.

[coinsolidation]

If there is no merkle tree in the blockheader, does that not leave it open to transactions being removed / replaced /  double spent?

[Meni Rosenfeld]

If there is no merkle tree in the blockheader, does that not leave it open to transactions being removed / replaced /  double spent?

The initial empty block header doesn't reference any transactions. The Nth stakeholder (derived by the empty header's work) adds the transactions, and a Merkle root to match.

[Gyrsur]

found the news about PoA by accident.

[iddo]

About the weird post above by coinxed: coins can be destroyed by not redeeming the entire coinbase, and also by sending an unspent output to (non-P2SH) script that always returns false. Some relevant info is discussed in this thread (e.g. post #164), and in footnote 9 in the paper (post #167) etc.

What happens if the N PoS "miners" aren't online? That seems quite likely very often.

The reason why you aren't worried that all the PoW miners will go offline is that they're rewarded for their work. Similarly, if stakeholders are rewarded, then we can expect some fraction of them to be online. In section 3.2.1 of the paper we describe how to incentivize a target participation level of the online stake.

BTW in case someone prefers to look at the presentation form, here are the slides that I presented in a couple of talks:
http://www.cs.technion.ac.il/~idddo/PoAslides.pdf

[Stery]

Really cool thread.

Whats "double spend" ?

[Meni Rosenfeld]

Really cool thread.

Whats "double spend" ?

https://en.bitcoin.it/wiki/Double-spending

[instagibbs]

The reason why you aren't worried that all the PoW miners will go offline is that they're rewarded for their work. Similarly, if stakeholders are rewarded, then we can expect some fraction of them to be online. In section 3.2.1 of the paper we describe how to incentivize a target participation level of the online stake.

Ok, I understand why people would mine, that wasn't the question, but are you saying the system will automatically tune to 10 minutes for finding a successful block? I suppose it will just readjust based on the implicit(explicit?) fraction of BTC stakes, as well as the PoW being done?

edit: Reading the slides. While it's well-written, I'm always annoyed that in one breathe people are concerned that miners will mine empty blocks, but similarly we shouldn't worry about PoA stakers to not do it. They're both invested in the same system with equiv capital(theoretically). It's not a substantial difference. Otherwise, I'm enjoying the read. It's easily the most "believable" for a PoS skeptic like myself, for a number of reasons.

edit2: If we are capping value of blocks, will we have a rule that allows a single transaction block that goes over that limit? Otherwise you wouldn't be able to spend BTC at extremely large valued addresses. Would the cap value mean miners will just include tons of dust transactions? Or would the value cap be *in addition* to the 1MB data cap? Or are we hoping the size propagation penalty will naturally force this down? Would this also encourage people to split up their BTC into smaller value, increasing the UTXO set? Just random things to think about.

[Gyrsur]

is there a full reference implementation to extend a full Bitcoin node with PoA?

[Gyrsur]

can it be combined with a distributed mixer? PoA nodes should be mixer nodes too?