If you find the following post helpful. It was quite a bit of work so any donations would be very appreciated. BTC:1NjNo3pfjC2fHWRPdSNvmWiyLXsGh5Y7p6 NXT:17286747867026237511
Klee and Come-from-Beyond believe and have informed me that my interrogation of Come-from-Beyond on the issue of block authoring and my subsequent findings may make me eligible for a bounty as they may constitute an audit of the mining algorithm. I also may be uniquely qualified to provide this audit since I authored a very similar proposal here
https://bitcointalksearch.org/topic/a-legitimately-novel-idea-for-a-new-crypto-343923 as it turns out 1 day before BTCNext.
As a disclaimer, as you all know the code is still closed source until jan 3rd so my findings will rely on claims by BTCNext being truthful and accurate.
First a summary of my findings:
The shortcomings that face POW schemes are myriad. I don't want to get into explanations here but I will list three of those shortcomings. Hashing efficiency scales logarithmically with investment in infrastructure. In lay-terms that means a person who invests 10billion in mining infrastructure will be able to produce significantly more than 10 times as much hashing power as someone who has invested 1 billion. This creates pressure towards centralization as the capitalization of the POW coin market increases. Additionally there is the excessive warrant-less (warrant-less only because NXT exists now
) use of silicon, electricity, and human labor in the production and maintenance of mining hardware. Finally there is a need to keep block sizes smaller than would otherwise be the case in order to prevent incentives for centralization.
The natural solution to these problems, proof of stake, was imagined years ago. Peercoin is the most noteworthy implementation of POS and all of the other POS schemes on the market, as i understand it, are forks of Peercoin. Peercoin was an innovative step in the right direction. It solved the above mentioned problems but only at the cost of introducing new problems. Peercoin's security model relies on the assumption that large stake holders will remain honest for fear that the loss to the value of their stake would outweigh the advantages of a successful double-spend. The main problem with this assumption is that two different people will never have the same idea about what constitutes self interest. Imagine, for just one possible example, a situation where a large stake holder in peercoin is an even larger stake holder in alternative monetary schemes and stands to benefit from the peercoin capital exodus by being on the receiving end of that exodus in his other investments.
The natural solution to the problems outlined in peercoin is to introduce randomness into the selection of which stake holder wins the right to author a block. It sounds simple, but its not actually as simple as it sounds. You see, you can't just hash the previous block and use the digest as the parameter for selecting the winner of the right to author the next block because, the block authors would contrive transactions in that block that digested into a hash that gave him the the right to author the next block. In-fact you cant base it off of a digest of any part of the block that the author has free reign over or you will run into the same problem. So here is the million dollar question, how do you arrive at a series of unpredictable but consensus verifiable number without proof of work? This is NXT's key innovation. It is to BTCNext as the block chain is to Satoshi.
In essence it works by having the author of the next block be selected by comparing the public key that he is using to hold his stake to the public key of the author of the previous block. In-order to prevent the new block author from simply creating a public key that would win and loading that public key with his stake BTCNext introduced the idea of effective stake. Only stake that has remained stationary for 1440 blocks (24 hours) has the right to author a block. Would be attackers can not calculate 1440 blocks into the future because they have no idea who is going to author the very next block, let alone the next 1440 blocks. Inorder to prevent an attacker from creating a "trap" where if he manages to become lucky enough to author one block in the future than he has prepared a set of funded addresses which would "catch" the subsequent blocks, we don't only rely on the previous block authors signature alone, but build an entirely separate "block chain" which is the result of hashing every public key ever used to author a block.
That was my attempt to explain the basic idea for how it works conceptually. It of course is not a technical explanation of how it ACTUALLY works. (i may come back and add that later if there is demand but it would mostly be a copy paste job from BTCNext anyway).
I have to be honest here. The code is still closed source. It could turn out that this is all a scam. Buying nxt will continue to be a huge risk until the code is published open source. But I will tell you why I am buying. What would be the point in BTCNext conceptually solving all of these problems and creating a truly great model for how a crypto could work, and then create enough infrastructure to make a convincing facade, when he could have almost as easily as creating such a convincing facade, implemented all of the brilliant ideas he conceptually outlined?! That would be crazy! And even if NXT does turn out to be a scam, we should still build a real crypto out of these ideas.
Anyway for anyone who wants more details I will post a full transcript of my conversation with Come-from-Beyond below:
OH HECK YES! afk while i buy a million of these things Grin
oh but hey can you do me one more favor. can you link me to the original source where you got this information. i really want to read more.
Other guy has answered on nextcoin.org about that.
FROM NEXTCOIN.ORGEach block has "generationSignature" parameter. An active account signs "generationSignature" of the previous block with its private key. This gives 64 bytes which are hashed with SHA256. The first 8 bytes of the hash gives a number (I call it a "hit"). The hit is compared to the current "target" (64bit number). If the hit is lower than the target then next block can be generated.
The target for each account is proportional to the balance. Someone holding 1000 coins gets a 50 times bigger target than someone with 20 coins. Thus the owner of 1000 coins will generate 50 times more blocks than the owner of 20 coins (in the long run).
The target is not constant, it grows each second passed since the timestamp of the previous block. If noone generated a block on the first second then the target becomes 2 times bigger and so on. The base target is the target on the 60 second mark. If there is only a few active accounts then after a long time someone will generate a block because the target will become very big. If you open the client and log with any funded account you can see a ticking timer in BLOCKS widget. It shows when the target will become greater than your hit.
No that was the first time and I wrote about it the same day that i thought of it. But you say that I posted it 1 day before nxt right? that technically makes it my invention right?
haha no I'm a scrub programmer. my highest programming accomplishment to date is chess in the console with no AI. I'm much better at conceptualizing higher level abstractions than the logistics of implementation.
actually this is a really common thing. inventions are more often than not invented by a half a dozen people all over the world at the same time. we probably thought of it at the exact same time and i just wrote about it first. here is wikipedia on the phenomena
http://en.wikipedia.org/wiki/Multiple_discoveryill check it out.
I think I'm starting to get it. Is it true that the generationSignatures are totally deterministic? If you wanted too you could spend computing power to calculate who would win the right to author blocks far off into the future?
Output of next signature depends only on input of previous one. For example:
F(x) = x*2
Then we have such a sequence of outcomes: 1, 2, 4, 8, 16, 32...
Transactions included into a block can't change it, there is a special "blockSignature" for them.
Great! im definitely beginning to understand.
So next question. What mechanism prevents people from purposefully creating accounts with public keys which will allow them to author an upcoming block?
*edit* there is definitely a tip in this for you if you have good answers to all of my questions
Cunicula (as attacker) and BCNext (as defender) came to the following algo:
1. Brand new accounts must wait 1440 blocks before they r given permission to forge blocks
2. Old accounts forge blocks as if their balance doesn't include coins received in the previous block
Amount that is used for forging is called "effective balance".
is it really that difficult to calculate out 1441 blocks ahead? it doesn't sound difficult. If it is so difficult now what happens when computers become faster and more powerful in the future? is the plan to just fork it from time to time?
it seems like if the generationSignature was additionally a product of the hash of the public key of the account that authored the previous block than that would add a measure of security for little additional cost. as in, unlike including phony transactions to get the result you want out of the digest of a whole block, it would be difficult to coax the result you wanted out of a public key funded with a large amount of cash 1441 blocks ahead of time.
What should be calculated ahead to be able to generate all blocks?
My understanding is that the next generationSignatureB is a digest of generationSignatureA and generationSignatureC is a digest of generationSignatureB ect... So what i mean is, what stops an attacker from calculating generationSignatures 1441 steps into the future and then creating and funding account that will win the right to author that 1441st block. It should in theory be rather simple to generate 1441 signatures if it is a purely deterministic process right?
U must predict amounts on other accounts in 1440 steps, coz time when u generate a block depends on ur effective balance. It's possible only for empty blocks. If someone's account becomes larger then he will get chance to inject his block into ur chain completely ruining all ur computations.
oooh so the generationSignature is a digest of the previous generationSignature + the time-stamp of the previous block?
No. It's digest of prevGenSignature only.
How determined the generator (account) of the next block:
1. X = digest of prevGenSignature gives 256 bits
2. First 64 bits of X is a HIT
3. Target = BaseTarget (which is the same for all accounts) * Balance * Time_since_previous_block
4. If HIT < Target then next block can be generated
Edit: Target grows each second until it "crosses" HIT of one of the accounts
All you would have to do is brute force the creation of a key pair that digested the 1440th genSignature to a hit that was below everyone elses target. It would be totally doable.
This problem is super solvable though. BTNext should make the BaseTarget adjustable with an algo similar to bitcoins re-target algo. Then Increae the 1440 block (24 hours) restriction for effectiveBalance out to about 43200 (1 month) just to be extra super safe (its best to pick absurdly safe parameters when dealing with billions or possibly even trillions of dollars someday). Then finally make the nextGenSignature a digest of the prevGenSignature + the public key of the author of the last block. You couldnt game it with intentionally selected keys because you would have to pick the key 1 month ahead of time and there would be no way to predict who would author which blocks 1 month out since miners drop in and out of the network at random.
1440 blocks is safe number coz u have to know who will sign the 1439th block which depends on the signer of the 1438th block and so forth. To know future signers u must know future balances. Even if u know future balances u must know future topology of the network to predict which blocks will be orphaned.
im so sorry to keep pestering you. but why is this the case. inorder to do this all you would have to do is brute force the creation of a key pair that digested the 1440th genSignature to a hit that was below everyone elses target. It would be totally doable. why must you need to know future signers?
Coz block 1440 winner is determined as Digest(Digest(Digest(...1435times...Digest(Signature_of_block_1)...))).
But that doesnt explain why you would need to know who future signers are. It only says that you would need to calculate the 1440th generationSignature and pre-empt it by creating an account with a key-pair that would cause your hit to be lower than everyone elses targets right? how do future signers effect that situation?
Output of the last digest depends on ur public key and generating signature of previous block. It's deterministic but still can't be guessed. Look at this example:
Alice signs block 1 - signature is A
Bob signs block 2 - signature is Digest(A + Bob_public_key)
Charlie signs block 3 - signature is Digest(Digest(A + Bob_public_key) + Charlie_public_key)
See? U can choose any Charlie_public_key but without knowing Bob_public_key in advance it gives no advantage at all.
yep! i do understand. we just weren't communicating properly. as soon as i thought i saw a problem what you wrote up there is exactly the solution i proposed.
bcnext is a freaking genius. I worked so hard to try to figure something out like this myself to no avail. What i proposed in my thread is a far cry from this much better solution.
I am only qualified to audit the ideas. Someone else has to tell me whether the ideas that BTCNext says he implemented are actually implemented the way he says they are. 
