ppcoin - stake burn-through vulnerability

[Jutarul]

This is a result of a recent security analysis I performed for ppcoin. Comments are appreciated.

Abstract
========

A vulnerability in the POS scheme implemented by ppcoin is presented, where an attacker can increase the POS generating capacity of available stake by performing an exhaustive search for the POS target equation.

Introduction
============

The security model of ppcoin is based on a hybrid proof of work/stake (POW/POS) design, where the majority of new coins are generated through POW and the long-term network security is facilitated through POS generated blocks. Using the generated coins itself in the mining process has the obvious benefit of avoiding the consumption of a physical resource, e.g. electricity, in securing the network. The premise of POS is that by using existing coins as stake in competing for the generation of valid blocks, no entity can manipulate the blockchain growth in their favor, e.g. by performing double spending attacks, if the stake is sufficiently decentralized. However, the POS implementation of ppcoin has a vulnerability, which allows an entity with a moderately small amount of stake to temporarily gain control over blockchain growth, and thus perform double spending attacks. This is facilitated by "burning" the stake as fast as possible, which is possible by increasing the sampling rate at which each stake is tested against permutations of the seed constants in the POS generation process. As a consequence, an attacker only has to gain as much stake and computational power to outpace the network for a limited number of blocks, for the attack to go through. The speedup gained by burning stake as fast as possible can be significant (>1000), because the default sampling rate provided by standard client is low. Since the amount of stake required for exploiting this vulnerability is negligible, the premise of stake being a force to keep miners benevolent does not apply to this kind of attacker.

Discussion
==========

The hashing algorithm for POS tests each unspent output for the following target condition (wallet.cpp,1263/1264)

CoinDays*TargetPerCoinDay >= Hash(Difficulty + InputStakeBlockTimestamp + InputStakeTXByteOffset + InputStakeTimestamp + InputStakeTransactionOutputNumber + CoinstakeTimestamp)

The default client tests the result of this condition at a rate of 1 to 5 per second.
The left side of this equation depends on the amount and the age of the used stake (CoinDays) and the POS difficulty of the network (TargetPerCoinDay). The network difficulty is adjusted so as to keep the number of generated POS blocks per hour constant with a running average (logic defined in function GetNextTargetRequired() ). The right side of the equation is deterministic with a finite search space: The difficulty is a fixed number and only depends on the current height of the blockchain, the InputStakeBlockTimestamp, InputStakeTXByteOffset, InputStakeTimestamp and InputStakeTransactionOutputNumber are determined by the unspent stake output to be consumed and the CoinstakeTimestamp is taken from a 2 hour window from current to past time, with a granularity in seconds (thus about 7200 choices possible).

The likelihood of generating a POS block is defined by the proportions of the left and right side of the above equation and the number of trials:
P(success)=trials*P(left>=right,trial)
(approximation for P(left>=right,trial)<<1)

Thus one can directly see that increasing the #trials increases the overall capacity of a stake output to yield a valid POS block, given that the input for the right side of the target condition is variable. The reason to include variable input parameters is to prevent pre-computation attacks, where an attacker pre-computes valid POS blocks for highly predictable input parameters for the right side of the target equation. Including the Difficulty parameter in the target equation makes the computation dependent upon the current state of the network, and requires an attacker to have the required computational resources online at the time of the attack or compute a wide variety of difficulty pathways in advance. The purpose of the CoinstakeTimestamp parameter seems to be to constrain the validity of the input for the hash equation to a specific time regime, thus furthering the need for online computational resources.

Thus the POS scheme seems to be exposed to a dilemma: While the right hand side of the target equation needs to be variable and moderately unpredictable (to prevent pre-computation attacks), the increase in variability increases the benefit of using computational resources to extend the POS generating capacity of a stake by maximizing the #trials. The effectiveness of burning stake by maximizing the sampling rate is shown in the Appendix A.

Conclusion
=======

While this analysis discusses the effect of an exhaustive search on the target equation, the possibility for advanced pre-computation attacks is yet to be determined. At its current incarnation, the target equation is highly predictable which may allow an attacker to boost their POS generating capacity to ridiculous lengths, given enough computational resources. Under these conditions the amount of stake only determines the maximum time the attack can be sustained. However, many attacks, e.g. double spend attacks require only temporary control over blockchain growth.

What matters in the end is the effect of competition. I.e. if all major stake holders perform the same aggressive sampling strategies for generating POS blocks, the possibility to outpace the network is nullified. However, this degrades POS to POW, because suddenly finding valid POS blocks "fast" is a computational problem. This renders the POS implementation pointless.

Appendix A
=======

stats:

sampling rate: 200 trials per second per unspent output
stake: ~ 220k
65 consecutive blocks.
total time: 338 seconds
average time per block : 5.2 seconds


data:
[
    {
        "account" : "",
        "category" : "immature",
        "amount" : 510.32000000,
        "confirmations" : 65,
        "blockhash" : "a0442dead3d1bceaa718aee97e7596f021b8479b2abc2b0e1497b1578f1bbb42",
        "blockindex" : 1,
        "txid" : "2959d287035ad2d175b0280449d069f31c495e2ae801135ffcdc49cd69e84a8e",
        "time" : 1355456881
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 30357.96214200,
        "confirmations" : 64,
        "blockhash" : "b133bcdca074891a794f71dfa0de48392cf3895baabcc9f34297a28f8b14660c",
        "blockindex" : 1,
        "txid" : "dabb8946d34127cd384c2d502a399ceb730c7121ee40714c6ef2848da211e94f",
        "time" : 1355456883
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 505.21000000,
        "confirmations" : 63,
        "blockhash" : "337091f3fc8bd7552328594f5220d166df7af3c1bf311d8a33b0972b20e1a568",
        "blockindex" : 1,
        "txid" : "1f79c49e864c79eff344ee0d6450774164df49f0727ecad6a2809432380a3708",
        "time" : 1355456885
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 20237.07000000,
        "confirmations" : 62,
        "blockhash" : "0b68798eb95a1e8330300afff45f0d56a3ba9a48113c6e8dc0c699657834ebf2",
        "blockindex" : 1,
        "txid" : "ce9994dff5daddd0695f65b74f1d53cd1824c03f5dbafca5a2628c544a2fead8",
        "time" : 1355456889
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 494.62000000,
        "confirmations" : 61,
        "blockhash" : "b83596ba3330a1b184060bc80469b676ef2976c2e1a7f1c4f39749b50952cf89",
        "blockindex" : 1,
        "txid" : "5a54b3adeb75aa8d8e5b5a7b955c9ea759ea1eb48a65b8f98c59ec1e39273dad",
        "time" : 1355456891
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.94000000,
        "confirmations" : 60,
        "blockhash" : "49b7aa8cfdd316619ca5c068b6cf5796c8809a5163e2e2f20b3de85ca9afefaf",
        "blockindex" : 1,
        "txid" : "f8f2b3150a35b864b61214fe5b4577e70dcb6a6066e2003232a7f0bdf3ed2c7a",
        "time" : 1355456892
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 467.74000000,
        "confirmations" : 59,
        "blockhash" : "7b7af034a67580784c03cfb91422c9174ad1a97da5450634f62f13ba1471b767",
        "blockindex" : 1,
        "txid" : "b7666f758ea7cea963f1c879524c7f7e3b116ef1de9e62777283ebe489fcbb40",
        "time" : 1355456896
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 492.57000000,
        "confirmations" : 58,
        "blockhash" : "af7d0715036181c17409c6128d537c485abb51940ac1d604044bee1fa5d1cd86",
        "blockindex" : 1,
        "txid" : "21f4465e7c8029eb83cbc240f73de493b17a1b9a17169c5c23b9394dca5cb3c9",
        "time" : 1355456898
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 25050.01900000,
        "confirmations" : 57,
        "blockhash" : "db98001a686bb21437cadf1e005437581accc8d036ef437f6231015a70f5ff38",
        "blockindex" : 1,
        "txid" : "1f277e8325ba0b8de0b742a620e0187247f1a713c77d5871bbd7c42bb24d2c14",
        "time" : 1355456899
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 25049.97000000,
        "confirmations" : 56,
        "blockhash" : "ebc0e8bfdf0d6ab86ff801fc668f71fbfb3464954e7c38bd5ec0aa23fec34347",
        "blockindex" : 1,
        "txid" : "8bad2b7388a0846a359cd7cfa3e6ff97221ef1a72cb5579224b48b1d4476ae4a",
        "time" : 1355456900
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 467.38000000,
        "confirmations" : 55,
        "blockhash" : "d120330957f18a993876b9d214e9a116665e98d187c6895127edca37571053f5",
        "blockindex" : 1,
        "txid" : "359289ae189950764705204a6b2b44f60a8562e403eae079f50509aa83f46225",
        "time" : 1355456903
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 486.92000000,
        "confirmations" : 54,
        "blockhash" : "7834337f1f7f70bc173e1c35770e4516064df28d62839d236e2e4155d0fac2fd",
        "blockindex" : 1,
        "txid" : "7ef41a16fe434dae9168ba67ee2385112a38b3688550f587eb918c5462b8b4c1",
        "time" : 1355456905
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 20237.07900000,
        "confirmations" : 53,
        "blockhash" : "3602a2de65f16075cc50e1d97407aceb66ec3413c5c2e3d390f993171a4ce8ff",
        "blockindex" : 1,
        "txid" : "fcad1d0346ece08fbf46ff51ee2d37c277a9b6531801982170cb16966e4876f3",
        "time" : 1355456909
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 648.27000000,
        "confirmations" : 52,
        "blockhash" : "f2041ca5eced23278f7d2317ffb0ca16a5a6e8f187e5c38b59e8b8813364f62c",
        "blockindex" : 1,
        "txid" : "18315831ae180aac9a3f9f7c95197fb210f5612b28de8b0e6d7fc8f5cd923c64",
        "time" : 1355456910
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 462.63000000,
        "confirmations" : 51,
        "blockhash" : "2c68180d25e6b33f3dbf71f0370940520104c78e7766b3caf4df23f4d97c50bf",
        "blockindex" : 1,
        "txid" : "3911ecb39b10dae8a2983e68a4c436ad0923bc8707d35fd517e8a3dfdf4a9377",
        "time" : 1355456911
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 15044.72000000,
        "confirmations" : 50,
        "blockhash" : "053f07eba61e8ea6bff60c58d303ca314ce09f0c824eeaaf00b7b7cda04381d0",
        "blockindex" : 1,
        "txid" : "9034b1f2332ec6541cc477640093553835518e019da531c5766b1dbe63b41a7d",
        "time" : 1355456918
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 36353.70450000,
        "confirmations" : 49,
        "blockhash" : "8fea5879160022a693724e442100c5ca6b719e55a0b5a2329a0884c346b584b3",
        "blockindex" : 1,
        "txid" : "43ab940e4ff7921275e10ce0c273290ae834e318c0dd81a8757a8ea91ab5324e",
        "time" : 1355456920
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 15044.73000000,
        "confirmations" : 48,
        "blockhash" : "58ab27d76c98040aea794f61aed1df2cb767d66b5a83a519f4a3e4203274653b",
        "blockindex" : 1,
        "txid" : "88b0c796f505a6d8b128ab437e6a77eaf965173b56210fbeaea6577d3976516c",
        "time" : 1355456930
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 648.78000000,
        "confirmations" : 47,
        "blockhash" : "c57b9a541155c516b19cbae090f16573688bf25e3b449f9aefa6c952dcfa666b",
        "blockindex" : 1,
        "txid" : "b27716ae7394ac5ebe26a8cf5a72c8343af78506b101aac108d84cf36eaa7e03",
        "time" : 1355456931
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 652.79000000,
        "confirmations" : 46,
        "blockhash" : "c5420e4d261cf452ae55652c605a9b95cba197b97654cb17b1d99abf6e7d3606",
        "blockindex" : 1,
        "txid" : "5dea31e44ab8161819c8f4c3ed2a48e91f942a3490540574e65e2eff4d741acf",
        "time" : 1355456933
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 650.79000000,
        "confirmations" : 45,
        "blockhash" : "304310bc6df63c91e75d4ca9637f93da737ea14f117f564c53555ab4d628306d",
        "blockindex" : 1,
        "txid" : "e833565da3a8685806855b4bc3813056a2a8cb9ec83e1eb5a8577b473593131f",
        "time" : 1355456946
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 469.18000000,
        "confirmations" : 44,
        "blockhash" : "2e04000ec32f8d564496608de1a0f835797a3be0e4c03430fb8971615e7b7b69",
        "blockindex" : 1,
        "txid" : "e611626f4e96cf3640855e76e6501f2702bbc2390efa708fee1088707b0b6b5f",
        "time" : 1355456950
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 527.09000000,
        "confirmations" : 43,
        "blockhash" : "b88274f452c0e349dcb8ce6c28b1bb978496dc1d4fb7a45b32dcc2a1eff03fb0",
        "blockindex" : 1,
        "txid" : "43d770a920acdd258b3fe17d9e19cbdc6e4349fc4ebc497b88e63f0c6f999f11",
        "time" : 1355456956
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 498.67000000,
        "confirmations" : 42,
        "blockhash" : "c1e0b1a0c7253f3059cb1354d015970e1315ee669ddc47e44d2f54f85d2df364",
        "blockindex" : 1,
        "txid" : "a5a9bbad808d238aaf19636261cd7fdd529505e815c7a2219e55b471b7b7d28d",
        "time" : 1355456961
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 498.63000000,
        "confirmations" : 41,
        "blockhash" : "d9bc7ec706a6040a0b6908d158eb7df5e3fa6ffbe1b606a50ca2d4c9035939e5",
        "blockindex" : 1,
        "txid" : "eca52bdb6844ac1013a5c388b3b1bb429ca09708696dc434338b34cf749c32ce",
        "time" : 1355456968
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 319.34000000,
        "confirmations" : 40,
        "blockhash" : "6ef3d9f7e340fed3aab44891f59a90ead71fb284f5ac4301392ebdcf542254fe",
        "blockindex" : 1,
        "txid" : "908112498472e6ffe88b61d600742a0deda7716e1106db4a9b1037f33ff6290a",
        "time" : 1355456974
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 469.38000000,
        "confirmations" : 39,
        "blockhash" : "755b9e0e83a64e57f532bf5426ae8a8f1c91192f750aa20ce9069cf4b140dbfe",
        "blockindex" : 1,
        "txid" : "b51590d51d40e1f6358a306cdddc1a7a6dfd1640cda86146e2f6a4e90c80e129",
        "time" : 1355456975
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 498.64000000,
        "confirmations" : 38,
        "blockhash" : "aa8621fa4d98bebbbf1462d14ce676d5538b3cae05ce12a7a3aa08070371f9f6",
        "blockindex" : 1,
        "txid" : "bd2cf62998e686f9e0596c8c00f1712e4df96fc07b4085e86a77c3845431f9fe",
        "time" : 1355456976
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 568.10000000,
        "confirmations" : 37,
        "blockhash" : "bd7cf912bbf4a2d6d8ab1309efbb7bd20151b73e574725a15c191cdfdae8b190",
        "blockindex" : 1,
        "txid" : "8204a59a4485e0518b493fa25a62be934b1de352d840eeccd17e0f7fcf0b9b35",
        "time" : 1355456981
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 506.88000000,
        "confirmations" : 36,
        "blockhash" : "6f2b2050bf5ff51798e83ff64c8a9f8f6e4469f16f88bfeecc8602d6e4660cf4",
        "blockindex" : 1,
        "txid" : "1d44f557f1d5c1f9b31c3d7344d75bdc7f9778babbf502af36a4c21c5ce460e2",
        "time" : 1355456985
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 321.29000000,
        "confirmations" : 35,
        "blockhash" : "18f03e38baf5d6fe983d4617d636c7f2244da9b3115bab20972dc04c923eb266",
        "blockindex" : 1,
        "txid" : "5b6bf092e2f7795b51691294b66936a5377fa02bf0f82d3bf1cbf0843b842db8",
        "time" : 1355456988
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 650.79000000,
        "confirmations" : 34,
        "blockhash" : "a3eca62e97b3f2266f95109a67199e4a0c3353cdd9984198e95b2254cf21b04d",
        "blockindex" : 1,
        "txid" : "6d036d81202812feb1117d417bd93eb8cadc6b80970d350e3b5a2e28e5badb49",
        "time" : 1355456992
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 487.80000000,
        "confirmations" : 33,
        "blockhash" : "a59cf0036cbf87f1d1966700419b666666b2a0e819c9e14fa08b8b512e150ac8",
        "blockindex" : 1,
        "txid" : "230b119a46377a6541fa4bd29b9d347ff1ace8b6f7e36bdf10f72cdb8654c327",
        "time" : 1355456999
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 632.22000000,
        "confirmations" : 32,
        "blockhash" : "fd5fd5037bbed17de61ada93b10c19d86a4df942639562321d8947853c1cad18",
        "blockindex" : 1,
        "txid" : "fd9086608521623ec5f71d74a2f909b0990aedf2acf7891b8838e747eb1b8da2",
        "time" : 1355457000
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 489.19000000,
        "confirmations" : 31,
        "blockhash" : "e446a85be02585b9443aaa49ae290baccbade136213e15bea1434e4e9d177415",
        "blockindex" : 1,
        "txid" : "f6ff59524532ab164e1f95d612fb5bb999226d919082ceda92553d55e1b583c0",
        "time" : 1355457011
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 319.33000000,
        "confirmations" : 30,
        "blockhash" : "c73fc3ed722dcbe328d0b8f47bf5ff2130fad9cdc8d9abcc30abf98a8b80e26c",
        "blockindex" : 1,
        "txid" : "98133c6c6346ef943132ccdab4625388f24bf46952e9db2b837cbccbea3dbce4",
        "time" : 1355457016
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.73000000,
        "confirmations" : 29,
        "blockhash" : "8300ccc5d5891b202b53c7d5febaba9f98e2c8b7b683433b0daa87495f2566e6",
        "blockindex" : 1,
        "txid" : "738676c41f24482da9f75fde7e21ee240a30c74691a8e4e3d9c0997361476fdb",
        "time" : 1355457025
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 490.00000000,
        "confirmations" : 28,
        "blockhash" : "6fe04ef4fb6891fe08d6b666d8fef0a970070e515fae875f56dad134361e7079",
        "blockindex" : 1,
        "txid" : "384058e6c8efe5bd442da6522a8789eb84e02a5f4ad44a20d594f2ce317a77cb",
        "time" : 1355457035
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 321.95000000,
        "confirmations" : 27,
        "blockhash" : "c55fe48c01ab451f1a129afb0825084fea27727afe4920174b29c43e26719a92",
        "blockindex" : 1,
        "txid" : "dfc3353845d292b4b99f6b6f31e57877894763eeaf7933d488eaa66ef2003381",
        "time" : 1355457042
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.21000000,
        "confirmations" : 26,
        "blockhash" : "e28eb904d61bf52ffe286b459e83e87c071beda41c1a334fc759f6c7cc1dbb58",
        "blockindex" : 1,
        "txid" : "9ecb2c6d3bda59c5d8bce8cea0360aaa70cb8ad277d651af368d790256607004",
        "time" : 1355457043
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 649.11000000,
        "confirmations" : 25,
        "blockhash" : "d573c752087c1dbcb07d9eba96d8dd5c1f43caffeb8eba9fb3be90cb523eb8da",
        "blockindex" : 1,
        "txid" : "8801a14cadf8fc05429ca34db4937ab2697ea5812c01233ba74b42556844a251",
        "time" : 1355457054
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 501.43000000,
        "confirmations" : 24,
        "blockhash" : "3aa5e48e2f137c23f44e42d81130734cf5d52b7eb2f35b7e879b4da95098f99b",
        "blockindex" : 1,
        "txid" : "0141f7a6567a0474ea611eaad865c4479e225a86c36279e1cf098b80dc4c960d",
        "time" : 1355457069
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 642.79000000,
        "confirmations" : 23,
        "blockhash" : "5b6f765f97dc29d8b714513796b4d44ac4000e6014ee94573c1289ed02be18e1",
        "blockindex" : 1,
        "txid" : "be32dd4e5506e329111535c0aa99774b3a7883144e5fc1e337c57b4ef7e34db2",
        "time" : 1355457087
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 498.63000000,
        "confirmations" : 22,
        "blockhash" : "d36f7632bb7c72af65ee3add39c5aee5f38846309fa4709c531a86982e43c7f6",
        "blockindex" : 1,
        "txid" : "c89254bc563238b83bd7bf7cfa59991f17db3b761363d05705d0c2f46e259e46",
        "time" : 1355457090
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 526.80000000,
        "confirmations" : 21,
        "blockhash" : "512522593c0c2e05191bd6a5205e4489dbc07fe4815b3ce47e4ba88cb60c886e",
        "blockindex" : 1,
        "txid" : "6024918c15e594cc42c1079342e4d04359c5a14811e8fbb9221b9d09bd7bb1b3",
        "time" : 1355457094
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 4458.03000000,
        "confirmations" : 20,
        "blockhash" : "0ce4749af32d212d63066cc358ee543d442bae60b80fd9ceedce02b5a0f13649",
        "blockindex" : 1,
        "txid" : "72bc8650402b3c775b8f1f04d4d410ceab36489634ee75d1ca1c9820bf4b80d5",
        "time" : 1355457099
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 508.18000000,
        "confirmations" : 19,
        "blockhash" : "74468b0ea8fc955e792dd3962c97b4f4ccdd40390f401c00ff4305fc55d88211",
        "blockindex" : 1,
        "txid" : "6c7c93819e2f5e5f5f7e2730e5ff65e687676f1a8c37a48720b82f9c7cce34cb",
        "time" : 1355457109
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 322.57000000,
        "confirmations" : 18,
        "blockhash" : "f2f07c16eea19ca9268545ec93b7f81659016286e83ea12147b0aa7364f39369",
        "blockindex" : 1,
        "txid" : "13b46049dc7fc99b72c5bd1e26cdaa81862d309bbe6a1a2e0b6edda08aea2838",
        "time" : 1355457123
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 560.97000000,
        "confirmations" : 17,
        "blockhash" : "5ef456c062e96f24aaabb469ede2d77b7095385c41b8aa5cc7fafd329890125c",
        "blockindex" : 1,
        "txid" : "da00e83218eddf65e5ca83fc30d9a031614af18342842beb63f2961d2c584cc9",
        "time" : 1355457133
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.91000000,
        "confirmations" : 16,
        "blockhash" : "cd7cc429bc45f2f2694a2781c056f9e17a4f8d825604ae5b5d673b73d7b84416",
        "blockindex" : 1,
        "txid" : "d3fa6bbdb6b8c26995e95f9c777dcf4871a55028c854054fe57d5f9a9fa31e2c",
        "time" : 1355457141
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 507.57000000,
        "confirmations" : 15,
        "blockhash" : "d1b66934e1638d0366f807b6bc4004823fd413059d9d691e1d646ae8cd78af4a",
        "blockindex" : 1,
        "txid" : "9c97aea8659810f8a97af19ca2e3e1f42bf9ebc03403b9846ea6219587e96ddd",
        "time" : 1355457146
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 505.84000000,
        "confirmations" : 14,
        "blockhash" : "741d07bd69cddda2e228739648b41d37652aacdc63c363ab8c253b558ffcb05e",
        "blockindex" : 1,
        "txid" : "4e7bdb13c1a1590c56f21b9d43cd813a45a2ae3a4f0475ac61c4816a84dd8766",
        "time" : 1355457151
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 322.41000000,
        "confirmations" : 13,
        "blockhash" : "29f7ec6f8467734390b3dd624d027ffe5129c924e07290e3c9dbe259a96c44ba",
        "blockindex" : 1,
        "txid" : "861892a368d02ad327512961da8598164c12ba1fc406baf5906cb372ca680e33",
        "time" : 1355457154
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 496.25000000,
        "confirmations" : 12,
        "blockhash" : "5ce8069c05b1f1e70e9ecbc606c103a91a5cb19b58f058baa078a298f463d41a",
        "blockindex" : 1,
        "txid" : "53c0015c652b29ffad99d01f75dd2c3ee4cbb41d07a1a3efe6b704a4961cc65f",
        "time" : 1355457156
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 494.84000000,
        "confirmations" : 11,
        "blockhash" : "10f649a97f3160a5c68a66cc6e57879b8cce9390e7f00ba9d3e40cc739e39b5d",
        "blockindex" : 1,
        "txid" : "db04ccb1cbc82745d35994bbde35e3f893dabd157a9526474147153420ed321d",
        "time" : 1355457157
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 508.17000000,
        "confirmations" : 10,
        "blockhash" : "74707328536fde7c632fbe6425c8c5daa1ded05f84cb41c38f5a86bff693787f",
        "blockindex" : 1,
        "txid" : "8bbddb698e2a8923a2b9bf9e159f206b77b5c88eaa006e8e02de2c225e94e746",
        "time" : 1355457158
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 648.27000000,
        "confirmations" : 9,
        "blockhash" : "c2bbf7d374dca9c8f55ede03b99e90df10897315f3b0b6be1b399ed1751b983d",
        "blockindex" : 1,
        "txid" : "059982011ff184ae0cb06f14a088757c065af846ceec6d853f4dcccc18a56448",
        "time" : 1355457177
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 469.79000000,
        "confirmations" : 8,
        "blockhash" : "81fb6a17ff11043d03764f5de4e6fd985529491e9ce16ea21a905b78f507a7f8",
        "blockindex" : 1,
        "txid" : "ab552862ccf6f8f2238e2682c80971bdb3546880b379223def97f67d6c7f9ca3",
        "time" : 1355457178
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 462.64000000,
        "confirmations" : 7,
        "blockhash" : "974e4a931bf054368f151c93399dc9d3a04488cc5962b27f5281b253ea4d9173",
        "blockindex" : 1,
        "txid" : "d44a95c33256fa3ba2101eab9d3696b057f1b7bd85b073af4ce687b6321f69c4",
        "time" : 1355457182
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 630.06000000,
        "confirmations" : 6,
        "blockhash" : "909e6485cf6181eb85dc76e8325562cff8de9f0c164d7de9c5e445141796c4f8",
        "blockindex" : 1,
        "txid" : "cdbe89a540c87b533caefcbb4831654e970daeef87c16956989b3fd05a877a17",
        "time" : 1355457186
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.31000000,
        "confirmations" : 5,
        "blockhash" : "8464551a63c7d9daa2d85124d1dc79e0c827e3518e2be73e1bb57af468aa83db",
        "blockindex" : 1,
        "txid" : "d5774faa1cb899d51bd68609acb0bccc5ed02f2ed03a1961707336a691d013ab",
        "time" : 1355457194
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 652.79000000,
        "confirmations" : 4,
        "blockhash" : "fb79bc3fa44f8017df56bf2e7f7d63005f4bb68e90ef87c242bf47ba7f958aec",
        "blockindex" : 1,
        "txid" : "9752006bd57a13afbddef7f8cabcb5ebfe3de84f7da2792859221d8188e03546",
        "time" : 1355457200
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 320.20000000,
        "confirmations" : 3,
        "blockhash" : "9acb901213f61510fe7a034435a91ed2918aee42f2b82516951806ebbe5c4eac",
        "blockindex" : 1,
        "txid" : "3dcb531051e41809a5b27a618d8affb49d6cff9f15da2cfc21d995b50bc18084",
        "time" : 1355457201
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 501.83000000,
        "confirmations" : 2,
        "blockhash" : "3de56f4eaab7c153d886a408848ff08e48b3c73637fc0f36af37a517a728d3bc",
        "blockindex" : 1,
        "txid" : "fe7ed1f914e6f6f7cd78d7508517333352719448bf85157f60ef3ae95e811057",
        "time" : 1355457212
    },
    {
        "account" : "",
        "category" : "immature",
        "amount" : 491.74000000,
        "confirmations" : 1,
        "blockhash" : "d71a3d6c8077b64e4bd05b71dc46ad4806797f949d4f4cf30e0f1ec8cc06fff5",
        "blockindex" : 1,
        "txid" : "3965719c57d3fea593fe68fc9b33719cea8f21b98ad9400676255e4abe47a456",
        "time" : 1355457219
    }
]

[1714205972]

1714205972

[1714205972]

1714205972

[1714205972]

1714205972

[1714205972]

1714205972

[doublec]

Good catch. So POS is just another POW that users can speed up as much as they have CPU power available (and coins meeting the criteria)?

[Jutarul]

Good catch. So POS is just another POW that users can speed up as much as they have CPU power available (and coins meeting the criteria)?

Yes. The conclusion is that there is likely to be a POW arms race on top of the POS. However, unlike the hashing tech in bitcoin - this is an arms race which is unpredictable.

[markm]

Is the unpredictability of a kind that will make ASIC impractical? How about GPU? Does it give CPUs a massive advantage over GPU and/or ASIC, or any real advantage over them at all?

-MarkM-

[cabin]

Is the only source of variability the 7200 seconds? ie is there anything else you can increment arbitrarily to increase the sample space you can try? Decreasing that space would be an obvious solution. The trick would be to keep the value that is hashed impossible to guess in advance. Difficulty is stored as 32 bits which is a good start as that would be very difficult to predict precisely in advance and it does not increase the search space at all. However it is probably not enough given the hash speeds that will soon be possible. More variables should be added that are both not predictable and not increment-able.

I also don't think it would help at all if everyone sampled the space aggressively like this.. this would just exhaust everyone's stake coins quickly and spike the difficulty. Everyone can easily max out the 3.6kh per hour but then there would be a lull and the difficulty would drop again. To secure the network the difficulty would need to be raised long term somehow (or the sample space reduced drastically as above)

[tacotime]

Figured this would happen eventually.

[Jutarul]

Is the unpredictability of a kind that will make ASIC impractical? How about GPU? Does it give CPUs a massive advantage over GPU and/or ASIC, or any real advantage over them at all?

-MarkM-

When I say unpredictable, I mean more complex than in bitcoin. The POW scheme in bitcoin is simple: compute as many hashes as possible for the current block header. The more hashing capacity you have the higher your chances to yield a valid block.

The POW arms race on top of POS may be a bit more complex - at the current stage it is not clear which sampling strategies may be possible. The timestamp is simple - it's similar to the nonce in the bitcoin header. However, the difficulty parameter is semi-predictable, which means that it is known within a certain range. The question is whether it is possible to perform reasonable pre-computations for that parameter.

It should be noted that ppcoin is currently moderately immune to this attack vector, due to the checkpointing, which prevents blockchain reorganization beyond 5 blocks. However, for checkpointing to be abandoned eventually, the POS scheme has to be rock solid.

[Jutarul]

Is the only source of variability the 7200 seconds? ie is there anything else you can increment arbitrarily to increase the sample space you can try? Decreasing that space would be an obvious solution. The trick would be to keep the value that is hashed impossible to guess in advance. Difficulty is stored as 32 bits which is a good start as that would be very difficult to predict precisely in advance and it does not increase the search space at all. However it is probably not enough given the hash speeds that will soon be possible. More variables should be added that are both not predictable and not increment-able.

The difficulty parameter seems to be a candidate for implementing further sampling strategies. It is known within a certain range, which is enough to make a POW race out of it.

I also don't think it would help at all if everyone sampled the space aggressively like this.. this would just exhaust everyone's stake coins quickly and spike the difficulty. Everyone can easily max out the 3.6kh per hour but then there would be a lull and the difficulty would drop again. To secure the network the difficulty would need to be raised long term somehow (or the sample space reduced drastically as above)

I don't think that would be an issue. I expect no correlation between competing stake miners, thus the difficulty adaption should be moderately smooth.

[smoothie]

@OP:

Instead of truncating the difficulty at 2 decimial places (which I'm not sure if that's being done or not on the block explorer or at the code level)...couldn't the precision of the difficulty to the right of the decimal point just say have 20 significant digits would change the hash value of the function hash()?

If there is rounding in the function then that would make my suggestion irrelevant.

If i'm right, then adding precision to the difficulty calculation value to have a large number of significant digits (if the output of the function is not a integer) would decrease the chance for a successful attack to take place.

Sorry haven't looked at the code in depth. Just looking at the way Difficulty is presented with 2 significant digits and the formula you wrote in the OP.

[Jutarul]

If i'm right, then adding precision to the difficulty calculation value to have a large number of significant digits (if the output of the function is not a integer) would decrease the chance for a successful attack to take place.

I'd back away from using the difficulty as a variation parameter. The difficulty is highly predictable, because it's a running average.
What you want is something unpredictable which cannot be iterated. E.g. including the hash value from a previous block has this property.

As stated in the OP, the problem is that there is a search space. The reason for its existence, to my knowledge, is that it limits the validity of the stake hash to a location in the blockchain and absolute time, and to introduce the concept of chance towards generating stake. This is what makes the target equation something like "criterion >= trial".

The choice for the size of the search space is non-trivial. If you make it too big, you allow for a POW race. If you make it too small you limit the granularity of your stake input to larger amounts, because a low number of trials increases the time of arrival for a POS input, and I figure you want to keep it below 2 years.

Ideally this should all be documented in Sunny's design documents for ppcoin. With all the missing documentation in the public domain, ppcoin should be considered half-proprietary - assuming that such documentation exists.

[roalwe]

At the risk of being accused of necromancy, has this vulnerability been fixed (and has the fix been tested) ?

[Sunny King]

At the risk of being accused of necromancy, has this vulnerability been fixed (and has the fix been tested) ?

Disclosure here: https://bitcointalk.org/index.php?topic=131940.0;all
Fixed in v0.3.0: https://bitcointalk.org/index.php?topic=144964.0;all