Topic: [NXT] Reference materials for paper on pos algo (Read 2411 times)
reserved
reserved
reserved
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.
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.
Quote from: Come-from-Beyond
Other guy has answered on nextcoin.org about that.
Quote from: Anon136
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? Grin
before nxt right? that technically makes it my invention right? Grin
Quote from: Come-from-Beyond
Right. And technically this makes me to suspect that u r BCNext.
Edit: I'd like to hear ur opinion regarding https://bitcointalksearch.org/topic/transparent-mining-or-what-makes-nxt-a-2nd-generation-currency-364218
Edit: I'd like to hear ur opinion regarding https://bitcointalksearch.org/topic/transparent-mining-or-what-makes-nxt-a-2nd-generation-currency-364218
Quote from: Anon136
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_discovery
ill 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?
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_discovery
ill 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?
Quote from: Come-from-Beyond
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.
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.
Quote from: Anon136
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 Grin
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 Grin
Quote from: Come-from-Beyond
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".
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".
Quote from: Anon136
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.
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.
Quote from: Come-from-Beyond
What should be calculated ahead to be able to generate all blocks?
Quote from: Anon136
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?
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?
Quote from: Come-from-Beyond
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.
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.
Quote from: Anon136
oooh so the generationSignature is a digest of the previous generationSignature + the time-stamp of the previous block?
Quote from: Come-from-Beyond
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
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
Quote from: Anon136
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.
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.
Quote from: Come-from-Beyond
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.
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.
Quote from: Anon136
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?
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?
Quote from: Come-from-Beyond
Coz block 1440 winner is determined as Digest(Digest(Digest(...1435times...Digest(Signature_of_block_1)...))).
Quote from: Anon136
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?
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?
Quote from: Come-from-Beyond
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.
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.
Quote from: Anon136
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. Grin 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.
is exactly the solution i proposed. Grin 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.
Quote from: inbox
Quote from: Anon136
If the chain requires little computational resources to calculate, what prevents an alternative massive chain from be injected?
Quote from: Come-from-Beyond
To inject an alt chain an adversary must own 51% of coins (90% with TF). Also there is a limit of 720 blocks for the max chain rollback depth.
Quote from: Anon136
ok but why? suppose I am one of the original 73 and i own 50 million nxt. What if i create an alt chain where my 50 million is spread into 50 1 million nxt account. Then i compute a chain where my 50 accounts author all of the blocks. Then i compute it to the point where that chain longer than the main chain. Specifically how do peoples clients know that this is not the real chain? All the maths would check out. The targets would update to the point where it didnt seem like transactions were coming in too quickly.
So then if you have a rule that says longest chain wins, and all the math was legit on this artificial chain that this guy created, everyone would adopt that chain. So you clearly need something more. If you make a rule that says the chain that, on average, has hits on lower targets wins than this would protect against the previously mentioned attack vector. But then if you use this rule clients would sometimes ignore longer but legitimate chains.
anyway just looking for some clarification here. thanks in advance.
So then if you have a rule that says longest chain wins, and all the math was legit on this artificial chain that this guy created, everyone would adopt that chain. So you clearly need something more. If you make a rule that says the chain that, on average, has hits on lower targets wins than this would protect against the previously mentioned attack vector. But then if you use this rule clients would sometimes ignore longer but legitimate chains.
anyway just looking for some clarification here. thanks in advance.
Quote from: Come-from-Beyond
What do u mean by
Quote
What if i create an alt chain where my 50 million is spread into 50 1 million nxt account. Then i compute a chain where my 50 accounts author all of the blocks.
? This doesn't look feasible having only 50 accounts (if I got ur idea correctly).Quote from: Anon136
Sure so you would just write the blockchain as if only those 50 accounts were forging. The targets would readjust and even though only 50million nxt was being used to forge that chain, the blocks would still come in at ~1 minute. Or atleast thats how you would record it having happened. technically you would just be computing it all and building the fake chain yourself.
Quote from: Come-from-Beyond
R u talking about a situation when TF penalizes forgers that skip their turn?
If no, then cumulative difficulty will be 20 times lower and blockchain won't be accepted as longest. (This is how it's now)
If yes, then nodes will choose a branch where their balance is higher.
If no, then cumulative difficulty will be 20 times lower and blockchain won't be accepted as longest. (This is how it's now)
If yes, then nodes will choose a branch where their balance is higher.
Quote from: Anon136
So instead of longest chain, it uses cumulatively most difficult chain?
Quote from: Come-from-Beyond
Yes. "Longest" is just a convenient word used since Bitcoin times.
Quote from: Anon136
If we went for "chain that demonstrates the participation of most stake" rather than "chain that is longest" you can imagine a situation where a couple of confirmations could get rolled back. though you would see the risk coming because it would only come after a ridiculously slow block. so any time you have a really really really slow block, you just trust the confirmations a little less after that right? and after a few you still have strength.
Quote from: Come-from-Beyond
Actually, time gap between blocks doesn't matter when TF is enabled. We can use anisotropic time scale and forge blocks exactly each 60'000 ms. In the future when Internet becomes much faster we could process blocks at 2-3 blocks/min rate. Time between blocks is used only to choose the next forger, we don't have to wait that long. I've never mentioned this coz BCNext prefer that people don't realize full power of TF until Nxt network becomes strong enough to survive an attack from entities with billions of dollars in the pocket.
Quote from: Anon136
So what happens if the network is able to predict too far into the future? Too far being 24 hours. If you can make even reasonable guesses as to who will author a block 24 hours from now the entire system breaks down.
Quote from: Come-from-Beyond
This requires too much memory and computing power and still very non-reliable.
Cunicula offered to assign a unique id to each coin and do the lottery by choosing the owner of next winning coin. His approach requires only 1 computation for each block prediction. BCNext used other approach that requires to iterate thru all accounts to pick the winner, this greatly increases requirement to computing power necessary for prediction.
Cunicula offered to assign a unique id to each coin and do the lottery by choosing the owner of next winning coin. His approach requires only 1 computation for each block prediction. BCNext used other approach that requires to iterate thru all accounts to pick the winner, this greatly increases requirement to computing power necessary for prediction.
Quote from: Anon136
so ive been thinking more about how to clients can handle choosing the right chain. im not sure i still understand exactly how nxt does it. but i independently figured out how it could be done. so i thought maybe you would find some value in my independent evaluation.
Suppose you have a hand full of chains and we want to figure out which one is the real one. First compare the genesis block of the chain to a hash of the correct genesis block which is downloaded with the client. Discard any chains that have a genesis block that does not digest properly. Next look at the time that the genesis block was published. Then look at the targets that hit each block and reverse engineer the exact time of each block. Add all of those times up and make sure that the sum total is < the current time. Discard any chains that claim to be time traveling back from the future. Finally, from the chains that you have left, take an arbitrarily large number and subtract the target that was used to hit on each block from that arbitrarily large number. Add all of those values to-gather. Once added togather the chain with the largest summed value is proven to be the one with the greatest stake participation.
Maybe your way is better but if you happen to find anything wrong with it than atleast you have a backup plan now.
Suppose you have a hand full of chains and we want to figure out which one is the real one. First compare the genesis block of the chain to a hash of the correct genesis block which is downloaded with the client. Discard any chains that have a genesis block that does not digest properly. Next look at the time that the genesis block was published. Then look at the targets that hit each block and reverse engineer the exact time of each block. Add all of those times up and make sure that the sum total is < the current time. Discard any chains that claim to be time traveling back from the future. Finally, from the chains that you have left, take an arbitrarily large number and subtract the target that was used to hit on each block from that arbitrarily large number. Add all of those values to-gather. Once added togather the chain with the largest summed value is proven to be the one with the greatest stake participation.
Maybe your way is better but if you happen to find anything wrong with it than atleast you have a backup plan now.
Quote from: Come-from-Beyond
Nxt works this way but that arbitrary number is ZERO. What benefit do we get when it > 0?
Quote from: Anon136
lets see:
(0-6)+(0-5)+(0-7)+(0-6)+(0-5)+(0-7)=-36
(0-5)+(0-4)+(0-6)+(0-5)+(0-4)+(0-6)=-30
-30>-36, the second chain is indeed the one with more stake. yep all checks out. didn't have a paper and pencil in hand at the time of figuring it out.
i just want to reiterate how brilliant this all is. it blows my mind.
(0-6)+(0-5)+(0-7)+(0-6)+(0-5)+(0-7)=-36
(0-5)+(0-4)+(0-6)+(0-5)+(0-4)+(0-6)=-30
-30>-36, the second chain is indeed the one with more stake. yep all checks out. didn't have a paper and pencil in hand at the time of figuring it out.
i just want to reiterate how brilliant this all is. it blows my mind.
Quote from: https://bitcointalksearch.org/topic/nxt-descendant-of-bitcoin-updated-information-345619
Quote from: opticalcarrier
Anon136's video described it as the chain that had the most stake involved in forging the blocks was the 'correct' one, even though there may be a longer chain.
Quote from: Come-from-Beyond
It's slang. "Longer chain" == "chain with the most stake involved".
Quote from: ChuckOne
@Anon136
If so, could we stick to the 'longer chain' theme? It's just because it makes more sense to most people (even those that are familiar with graph theory).
If so, could we stick to the 'longer chain' theme? It's just because it makes more sense to most people (even those that are familiar with graph theory).
Quote from: Anon136
i mean it works as slang but it is technically incorrect since its trivially easy to make a chain as long as you want. you could make a 1 million block long chain on my desktop computer in minutes if i wanted.
Quote from: ChuckOne
Err, so, what? 
Sorry, but it's a bit confusing if you don't know what's right and what's wrong.
In plain english: what's the right way of finding consensus in NXT?
Sorry, but it's a bit confusing if you don't know what's right and what's wrong.In plain english: what's the right way of finding consensus in NXT?
Quote from: Anon136
by looking for the chain that demonstrates the greatest stake participation without claiming to be from the future.
Quote from: ChuckOne
Ah, okay.
Just to get that sure:
- the longest branch in the sense of graph theory is totally irrelevant
Just to get that sure:
- the longest branch in the sense of graph theory is totally irrelevant
Quote from: Anon136
well idk anything about graph theory but yes the length of the chains is irrelevant.
Quote from: ChuckOne
Okay, so now we have:
Consensus in NXT is found by looking for the branch that demonstrates the greatest stake participation without claiming to be from the future.
This is achieved by summing up the targets on each branch and the branch with the smallest total is the correct one.
Got it right?
Consensus in NXT is found by looking for the branch that demonstrates the greatest stake participation without claiming to be from the future.
This is achieved by summing up the targets on each branch and the branch with the smallest total is the correct one.
Got it right?
Quote from: Come-from-Beyond
No. U sum 1/target and want to get the highest value.
Quote from: Anon136
there we go cfb. thanks that clarifies what i was going to ask you about. thanks as usual.
additionally there is a conversation that i lost which deals with the fact that when we calculate who has the right to author the next block first, the two most acceptable submissions are considered equally valid. this means that when trying to calculate who will author blocks out into the future, you never know which one of those two eligible nodes will end up getting orphaned and which will become part of the main chain. meaning that when you try to calculate the hash chain out into the future it becomes
("how far out you want to calculate"^2)*"total number of stake holders"
potential outcomes. since you need to calculate 1440 blocks into the future to game the system by preemptively planting stake that will win in the future (due to the 1440 block holding period before stake becomes active). this becomes an imposable large space to make predictions in. especially since there is a fee for transactions set at 1NXT right now meaning each guess costs 1NXT.
Jump to: