Punishing minting on multiple chains

Hey guys,

Gavin and others think that one mayor weakness of Peercoin is that it is possible to mint on several chains. Here is a quote from Gavin.

The trouble with Proof-of-stake is that there is nothing at stake." Consider the basic function of proof-of-work and the blockchain: together, they let the network come to a consensus when there are two (or more) different, competing chains. Miners must decide to dedicate their hashing power to just one chain-- they cannot "bet on" more than one. So their best strategy is to work on the chain that they think most other miners are working on, and that quickly drives the system to a consensus on a single, best chain. The trouble with proof-of-stake is there is no natural incentive stopping a miner from assigning their stake to multiple, competing chains. If you try to create such a system, you "go meta" -- you started by trying to solve the transaction double-spend problem (which proof-of-work and the blockchain handle nicely), and end up trying to solve a proof-of-stake double-spend problem.

I do not think that this is a problem, due to the fact that we have

  • a duplicate stake detection.
  • there is just a negligible incentive to mint on several chains

People are criticizing that the duplicate stake detection works just on the client level. Of course it would be favourable if we could prevent minting on multiple chains on a protocol level. My proposal will enforce a duplicate stake detection on a protocol level.

New Method: Voting on Blocks by Minting

The method voting on blocks by minting crossed my mind when I reflected Peercoin’s security. It is well known that the probability to conduct a double-spend successfully drops exponentially with the number of confirmation a client waits and does not correlate significantly with the time intervals between the blocks. From this point of view it would be favourable to make the blocktime interval as small as possible. Imagine Peercoin has a blocktime interval target of 1 min instead of 10 mins, this would imply that a attacker would have success probability of ~p^60 instead of ~p^6, if he wants to reorganize blocks produced in 1 hour.
But, from a technical point of view a blocktime interval of 10 mins is much more appropriated that a 1 min blocktime interval.

The solution for this dichotomy might work like this: We could introduce two PoSdifficulities. The first PoSdif1 is adjusted such that a valid kernel – a transaction output and a timestamp - is found every 10 mins in average. The owner of this kernel is allowed to build a new block. In contrast, the PoSdifficulty PoSdif2 is adjusted such that a valid kernel is found every 1min. The holder a valid kernel, such that PoSdif2 is met, is not allowed to construct a block. But he is allowed to vote on blocks. i.e. he is allowed to create a “voting transaction”, which sends his transaction-output, which found the kernel, to himself with an additionally annual reward. This transaction should also contain information about the valid timestamp of the kernel and the hash of the block this kernel is voting for.

Each time a new block is found, by a kernel meeting PoSdif1, all the voting transactions are collected. If the new block is build up on a previous block with the hash abc, all voting transactions for the block abc are allowed to be included into the new block. The chaintrust of this new blockchain should reflect how many votes are in this new block and how high the PoSdifficulties are.

bnChaintrust=(CBigNum(1)<<256) / (bnTarget1+1)+#Numberofvotes* (CBigNum(1)<<256) / (bnTarget2+1)

Here bnTarget1 is the Target for the PoSdif1 and bnTarget2 is the Target for the PoSdif2, just as in https://github.com/ppcoin/ppcoin/blob/master/src/main.h#L1269
From a security point of view, - I guess that- this new protocol behaves quite similarly as one would expected it from the Peercoin implementation with a block time interval of 1 min.
Using this technique, we can solve the dichotomy described above and thus improve the double-spend protection, while keeping a good blocktime interval.

But the mayor improvement would be that we could punish easily stakeholder minting on several chains. Imagine a stakeholder votes on two different blocks with the same kernel, by signing two voting transactions. Now a honest blockfinder could be allowed to include both voting transactions into his block. Then, every honest node sees that this kernel -transaction output - was used to mint on serveral chains. Thus, we can find a consensus on who tried to cheat. Having this consensus, we can punish these stakeholder. For example, we could freeze his account for 3 years, prohibit him to mint in these 3 years and disallow him get the annual reward for these 3 years.

I am not good at presenting new ideas, so please ask any questions, if something is not clear.

Under the bottom line this proposal has the following pros:
-improved doublespending protection
-punishment for minting on several chains
and cons:
-Peercoin’s complexity increases
-more minting outputs are used and thus a high percentage of coins might be in the 30 day maturing period.

I am curious about any comments!

I am wondering what prevents duplicate stake detection to be implemented at protocol level?

Currently any connected node already can see all blocks of duplicate stake (minting-on-multiple-chains), except for a small fraction of the blocks that fail to reach the node. Current duplicate stake detection already can weed out most attempt. Are you saying it cannot work on protocol level? The one-minnute block vote only seems to serve to pick up the missing blocks. How come it can work on protocol level then?

I am wondering what prevents duplicate stake detection to be implemented at protocol level?

Currently any connected node already can see all blocks of duplicate stake (minting-on-multiple-chains), except for a small fraction of the blocks that fail to reach the node. Current duplicate stake detection already can weed out most attempt. Are you saying it cannot work on protocol level? The one-minnute block vote only seems to serve to pick up the missing blocks. How come it can work on protocol level then?[/quote]
In order to implement duplicate stake detection at protocol level we need to store information about the duplicated stake in our block chain. If you would like to do it in the current implementation, you would have to store the whole duplicated block in the blockchain. That is a lot of data. If you only would have to store a additional “voting transaction” that would make everything easier.

In this post I would like to highlight the doublespend protection improvement of “voting by minting”

There is an excellent paper by Mine Rosenfeld:
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CEAQFjAD&url=https%3A%2F%2Fbitcoil.co.il%2FDoublespend.pdf&ei=EkYIVIT2EsO7O-3ugYgN&usg=AFQjCNEN_HGQi9xVcmBVx_tcrmYB0b0y-A&sig2=KkK2EOdU49HK02u6o9rwDQ&bvm=bv.74649129,d.ZWU&cad=rja

It analyses the probability of a double spend - even more accurate as satoshi did in his whitepaper.
Under the bottomline it says that the probability to double spend after n confirmations is given by:

if the attacker has p percent of the total hashing supply and q=1-p.
Furthermore it highlights the fact that the security of bitcoin does not depend on the time, but the number of confirmations a merchant waits.

As discussed over here: http://www.peercointalk.org/index.php?topic=3141.30 all these calculations are valid for proof of stake as well. The only difference is that the hashingpower is substituted by mintingpower, which is determined by the amount of coinsdays available for minting.

Thus, if an attacker has 10% of the minting power, his odds to reorganize 6 blocks is given by: 1-sum(ncr(m+6-1,m)(-(1/10)^6*(9/10)^m+(1/10)^m*(9/10)^6),m,0,6)=0.000591412

In contrast, the “voting method” would come up with the following number, if one waits 60 minutes, i.e 60 blocks.

1-sum(ncr(m+60-1,m)(-(1/10)^60*(9/10)^m+(1/10)^m*(9/10)^60),m,0,60)=2.1*10^-28

This is a radical improvement! The best is that you can include even more than 10 votes per block and hence boost the result even more!

A couple comments on the OP.

Changing the block time affects p, so it only changes the variance, not the attack difficulty, for small values of p. This is because a 10-times-faster block rate will result in a 10-times-lower difficulty.

Punishing a minter with a future penalty can’t be done, because it destroys the fungibility of the currency. Also, the cheater could simply send his “marked” peercoins to an exchange, and withdraw them again (optionally after some trades), which would withdraw different coins. Suddenly, it’s the exchange who is being punished.

Thank you, josojo, for submitting another creative idea for discussion. This is definitely a topic we need to be thinking about because many Bitcoin leaders are refusing to take a serious look into Peercoin because they are convinced a priori that “nothing-at-stake” is an inevitable weakness with PoS.

Even though we can reasonably expect any future legitimate Peercoin clients to incorporate all essential blockchain security operations such as duplicate stake detection, purists will insist that the blockchain itself needs a method for internal verification against fundamental risks. The primary threat arises from theoretical “attack” clients which will be capable of subverting the ledger while still contributing valid transactions/blocks.

I really want to spend some more time pondering the implications of josojo’s specific proposal because the geek in me is naturally attracted to the elegance of strictly logic-based solutions. However, in my professional career I have found it necessary to depend on theories and assumptions that are much more malleable and uncertain in order to accomplish valuable work. Sometimes, they say, the perfect is the enemy of the good.

So while I really don’t want to see the discussion get off track, my first reaction is somewhat of a philosophical response to the primary issue… namely, that I am not convinced that there is a practical distinction between “protocol” and “client” after all.

While I sympathize with the purists in seeking a pristine mathematically-autonomous edifice for securing the word’s economic future, I question whether it is truly possible or even necessary to sustain total isolation from extrinsic maintenance and control. The fundamental question, I believe, is not whether the blockchain will survive in every universe, but whether it has a very high probability of resisting the likely threats on this tiny planet (…something between asteroid collision and discovery of cold fusion.)

Is it possible to imagine a future wherein the Peercoin blockchain has accomplished universal acceptance as a major store of value but somehow its primary reference client is widely rejected? Certainly, one can conceive of competing wallets that not only disable duplicate stake protection but also selectively include/ignore transactions, propagate only orphan chains, ignore checkpoints etc… But what foreseeable sociological/economic/anthropological factors could ever create sufficient pressure to allow these deviant wallets to overtake the majority’s interest in sustaining a valid network?

This is where I think the notion of “protocol” really extends beyond simply the internal logic of the blockchain and includes protections that are best enforced on the client level. It doesn’t really matter if I build an alternative client that propagates duplicate stakes because no other nodes have sufficient motivation to participate in my scheme. Even if I build a flashy interface with unicorn farts and celebrity gossip, I doubt I could convince a significant percentage of the world’s stakeholders to choose to secure their wealth with my closed-source app over the open-source reference wallet.

In other words, while client-side operations lack mathematical immunity they are capable of overwhelming “herd” strength against manipulation and still allow for the most lightweight and efficient blockchain possible. The power of client-side duplicate block detection is achieved through the principal that the underlying blockchain “protocol” does not incentivize multi-chain minting enough to convince the majority of users to opt out (…and I believe with sigmike’s upcoming multi-stake rejection there will actually be true disincentive to doing so, albeit still on the client level.)

Having said all this, I want to emphasize again that I am very intrigued by josojo’s proposal and particularly the question of whether it is possible (or desirable) to emulate faster block times through voting. I’m looking forward to reading the linked article and seeing more discussion below!

Sorry Chronos for posting my wall of text on top of you… you slipped your post in while I was typing (for too long obviously!) You make some good points. I still want to look at the referenced paper to make sure I really understand the math, but my gut instinct is that it is not so easy to “exponentially” increase double-spend protection over the same total period of time…

[quote=“Chronos, post:5, topic:2849”]A couple comments on the OP.

Changing the block time affects p, so it only changes the variance, not the attack difficulty, for small values of p. This is because a 10-times-faster block rate will result in a 10-times-lower difficulty.[/quote]
I am sorry that I did not make that clear in the first post. p is just the percentage of minting power measured in coindays owned by the attacker. Thus it will not change. I described it better in the second post.

[quote=“Chronos, post:5, topic:2849”]A couple comments on the OP.

Punishing a minter with a future penalty can’t be done, because it destroys the fungibility of the currency. Also, the cheater could simply send his “marked” peercoins to an exchange, and withdraw them again (optionally after some trades), which would withdraw different coins. Suddenly, it’s the exchange who is being punished.[/quote]
Yes, we would have to freeze the cheaters peercoins as well. Once we have the cheater marked in the blockchain, we can freeze his account. This could be archived by skip all blocks with transactions from this cheating address. Thus we would have fungibility of all non-forzen accounts. This would be good enough for me :P. But yes, this is an issue which needs to be discussed.

@learnmore

I am happy that I could attract your inner geek ;D.

Yes, sometimes it is hard to differentiate between a protocol and a client level. I would say that my proposal works on a protocol level since the new protocol would punish financially public multichain minting. Thus there are “costs” that force the minter to mint on the right chain - just as in the Bitcoin protocol.

I might be way off but I thought a the foundation of cryptocurrency is that its protocol is enforced based on comparing hashes. Protocol level operations have to be implemented in math or in scripts. If you violate the protocol no node can get all the hashes to match, so the node has to discard your block. If you attack the network by letting many nodes to run a client that doesn’t follow the hash-match rules, you are not playing the cryptocurrency game anymore. You are just running a p2p network. That is the essential difference between protocol level and client level in my mind.

I don’t see why information has to store in the blockchain for it to work. “Duplicate” means having the same kernel on two (or more) chains simultaneously.

Singling out individual addresses (to punish) on protocol level is no easy task. No other coin has it for a good reason. Every node has to check theoretically an unlimited number of bad addresses for every candidate block.

Thanks for the discussion. It’s fun. :slight_smile:

Singling out individual addresses (to punish) on protocol level is no easy task. No other coin has it for a good reason. Every node has to check theoretically an unlimited number of bad addresses for every candidate block.[/quote]
I think it is an easy task. While validating a normal transaction, a client has to look up whether the outputs haven’t been already spend in another transaction. Quite similarly, a client could look up whether the outputs haven’t been used for double minting in another block. And if they would have been used for double minting, the client could refuse to handle this transaction. What would be the difference in your opinion?

I don’t see why information has to store in the blockchain for it to work. “Duplicate” means having the same kernel on two (or more) chains simultaneously.[/quote]

Honestly, I am a little bit confused about what is a protocol- and clientlevel. But all I wanted to state is that if you want to punish someone for double minting, probably you need to store informations on the chain. I can not imagine to introduce a punishment with a future penalty, if you do not store any information on the chain.

josojo’s point is that information regarding the existence or relative quality of multiple competing chains is not something that can be extrapolated from only the information currently contained within any single blockchain. His suggestion is to try to incorporate this data so that the underlying blockchain “protocol” is mathematically bound to the best chain rather than relying on the client layer to execute this judgement.

My initial response to this “problem” is that it may not realistically exist. Pushing the ideal of a completely “client-agnostic” protocol is interesting and attractive but probably not necessary or ultimately valuable.

Furthermore, after taking some more time to study the proposal I currently offer the following observations/objections:

[ol][li]A fundamental design principle of Peercoin is a small, efficient blockchain. This proposal works directly against this goal.

[/li]
[li]Although there is currently a hypothetical advantage to minting multiple chains (a very minimal gain through compounding 1% interest), sigmike is already working on a client-level change that obliterates this advantage.

[/li]

[li]The “PoSdif2” encourages fragmentation of large stakes without improving the coin-days-destroyed value of the chain. Ultimately, large stakeholders exert the same amount of influence but with much more blockchain bloat.

[/li]

[li]I think the assertion that 1-min blocktimes are “more secure” is false. After looking at the formulas and the linked document it appears that a fundamental insight is missing. Time is always a relevant factor because it is directly implicated in the difficulty. In Bitcoin, lowering the blocktime means lowering the difficulty. Lower difficulty = more blocks per unit of hashing power. The probability of a re-org ultimately remains proportional to hashing power irrespective of the number of blocks the re-org requires. In Peercoin, chains are valued according to coin-days-destroyed but the same principal applies: larger blocks = proportionally larger stakes required for re-org.
[/li][/ol]

By and by I remain convinced that Peercoin’s security assumptions are sound and that critics really need to take the time to fully understand the protocol (both blockchain and client level). I would love to see some formal academic testing and “proofs” of Peercoin’s design, and I am confident that these will come in time. As far as I’m concerned Bitcoin equally lacks a rigorous critique of the strength and sustainability of PoW.

As I said in the first post, I think that peercoin duplicate stake protection is fine, but my proposed protection would be better. Especially if you think about bribery attacks. Take a look over here: http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CEIQFjAD&url=http%3A%2F%2Fwww.cs.technion.ac.il%2F~idddo%2FCoA.pdf&ei=bw0LVMCsNqeP7AaVm4HgBg&usg=AFQjCNF24NWfjiDZTD1Nv9rOnDTHqZqSoQ&sig2=sErlVLpF71J9EX2M2_2_pg&bvm=bv.74649129,d.ZGU

This is true, but one has to weight in the benefits against the blockchain efficieny. As security has a fundamental importance, the benefits of this proposal could weight out all other aspects.

The "PoSdif2" encourages fragmentation of large stakes without improving the coin-days-destroyed value of the chain. Ultimately, large stakeholders exert the same amount of influence but with much more blockchain bloat.
fragmentation of large stakes is a good thing. If there are minting just a few big stackes PoSdifficulty will swing much more than if there are many little stacks. The more small stacks we have, the less is the variance in PoSdif and hence in PoS security. That is the reason why the Peercoin protocol splits our outputs every time we find a block in less than 60 days.

It is true that a lower difficulty implies more blocks per unit of hashing power. But this is not relevant. Due to bitcoins and peercoins genius model it is relevant how fast an attacker finds a new block compared to the mainchain. If you decrease the PoSdiffculty both the mainchain and the attacker will find blocks faster.

I wrote down several sentences in order to explain the mathematical theory behind this. But I deleted them all again, because it is so hard to describe the math in words.

But could you show me potential mistake in my calculations in the second post. That would convince me that you are right.

It is fun to argue against you. I guess it’s the best way to learn a lot about the peercoin security model for both of us.

The calculations have always appeared solid to me. That’s why I was convinced there had to be something missing in the underlying assumptions- but after spending a good bit of the day mulling over the topic further, I found it was my own assumptions that were problematic

As you already acknowledge, there are many important factors to consider when designing the block timing, but directly adjusting the “value” of confirmations (beyond the first) is not one of them. I stand corrected.

Indeed, I learned a lot today. You forced me to go back through a lot of my old research into Bitcoin inluding even Satoshi’s original paper which actually illustrates the concept right there!

I am so excited. I was able to convince one of our very intelligent peercoin members. Will I be able to convince even more ?

I would like to hear more opinions about freezing and punishing outputs that have been used to mint on several chains. Is this practical on a technical level? What is your opinion about my comment:[quote=“josojo, post:11, topic:2849”][quote=“mhps, post:10, topic:2849”][quote=“josojo, post:8, topic:2849”]we would have to freeze the cheaters peercoins as well.[/quote]

Singling out individual addresses (to punish) on protocol level is no easy task. No other coin has it for a good reason. Every node has to check theoretically an unlimited number of bad addresses for every candidate block.[/quote]
I think it is an easy task. While validating a normal transaction, a client has to look up whether the outputs haven’t been already spend in another transaction. Quite similarly, a client could look up whether the outputs haven’t been used for double minting in another block. And if they would have been used for double minting, the client could refuse to handle this transaction. What would be the difference in your opinion?[/quote]

Honestly, I am a little bit confused about what is a protocol- and clientlevel.[/quote]

Cunicula stated nicely why implementing on protocol level is important:
Anyways, the broader point is that security should be created by block validity rules. These rules are enforceable. Modifiable code should not be the basis for security. The blockchain-based solution is to require stakeholders to submit work when they submit signatures. This rule can be enforced in the blockchain.

But all I wanted to state is that if you want to punish someone for double minting, probably you need to store informations on the chain. I can not imagine to introduce a punishment with a future penalty, if you do not store any information on the chain.

In the nothing-at-stake scenario, a selfish node will try to use its coin age to extend chains other than the most promising chain in case those other chains turn out to be the main chain. These “other chains” have to be very recent to have reasonable chance to become the main chain. The selfish node will broadcast, hoping other node will extend based on its new block.

So if there are several chains being extended every node on the network should be able to see them, except for two small probability cases – somehow the block is lost, or the chain is a privately grown. Other nodes don’t need to look up any historical record to find duplicate stakes, because the duplicate stakes are all very recent – within 10min mostly.

Why punishment is risky was discussed at https://bitcointalk.org/index.php?topic=101954.msg1282457#msg1282457

Why punishment is risky was discussed at https://bitcointalk.org/index.php?topic=101954.msg1282457#msg1282457[/quote]
Thank you for this link. I enjoyed reading the old discussions of all these bright peoples.

Quote from cunicula

Punishments would likely cause reorganization of the currently accepted chain. Blocks and txns that were valid would become invalid once duplicate stake is incorporated in an older block. Strategic insertion of duplicate stake would become a double-spending strategy. My guess is that attempts to punish offending addresses will introduce very severe problems. People will strategically seek out these punishments to mess with the blockchain.


I do not think that punishments would cause reorganization. You just have to do the punishment right. In my proposal, we would freeze outputs and do not allow to mint the output for 3 years. But since the minting with this output would still be legit, there would not be any change in the chainTrustscore, hence there would be no reorganization.

I have not found any other problem with punishments in this thread. Did I overread some facts?

[quote=“mhps, post:16, topic:2849”]Cunicula stated nicely why implementing on protocol level is important: [i]
Anyways, the broader point is that security should be created by block validity rules. These rules are enforceable. Modifiable code should not be the basis for security. The blockchain-based solution is to require stakeholders to submit work when they submit signatures. This rule can be enforced in the blockchain.[/quote]
Thank you for quoting these wise words!

[quote=“mhps, post:16, topic:2849”]In the nothing-at-stake scenario, a selfish node will try to use its coin age to extend chains other than the most promising chain in case those other chains turn out to be the main chain. These “other chains” have to be very recent to have reasonable chance to become the main chain. The selfish node will broadcast, hoping other node will extend based on its new block.

So if there are several chains being extended every node on the network should be able to see them, except for two small probability cases – somehow the block is lost, or the chain is a privately grown. Other nodes don’t need to look up any historical record to find duplicate stakes, because the duplicate stakes are all very recent – within 10min mostly.[/quote]
You are right. Dupliated stack detection should work fine, as long as the majority of peercoinclients run the right sourcecode and not the modified opportunistic code with disabled duplicated stake detection. But with my solution it would not make sense to run a modified code. That’s why it is important.

I am still not convinced that this will not almost double the workload for every node. But assuming it is not an issue, implementing it seems a major change – a punishment “transaction” has to be introduced and implemented .

Let me describe how my method could work in detail.

Suppose a malicious stakeholder has found a valid kernel and submits a transaction of vote on the mainchain first. His voting transaction will be sth like:
I want to vote with my stake:“his transactoin ouput” and the timestamp “current timestamp” on the current block “abc”. Signature.

Active nodes will see this message and safe this stake in a vector “seenstakes”.
If the malicious minter then releases another voting transaction for another chain within 2 hours -2 hours is the timestamp valid:
I want to vote with my stake:“his transactoin ouput(same as above)” and the timestamp “current timestamp(same as above)” on the current block “block not in the mainchain”. Signature.

the active clients will build this vote also into the next block. Now, everyone will see that this is a double minting vote since the voting for current block for this is wrong.

In contrast if the malicious minter first mints on the attacker chain and then at the mainchain, both votes can be put into one block and the cheating is obvious.

After the new block is stored on the clients, they will build up their CTxIndex. Here the output, used to mint on several changes can be marked as vSpent. Take a look overhere: https://github.com/ppcoin/ppcoin/blob/master/src/main.h#L815

Later on, when the attacker tires to spend its output, we check in the funciton ConnectBlock whether this output is not marked as spent. See here:

What we would have to change is that the flag vSpent must be changed after 3 years such that the output is spendable by the attacker. And after the attacker changed the address of the his output, we would allow to mint him again.

This might be one rough way to implement it. Yes you are right, it would be a lot of work.

Sunny gave an update about Sigmike’s proposal here…

http://www.peercointalk.org/index.php?topic=3344.msg32385#msg32385