Someone had expressed the following questions on IRC, but were never answered by a dev. I copy them here because I find them quite interesting: (exact copy) 1) How does a node know which tickets are live, i.e. a fresh node, or an unsynced node? Does it HAVE to trust other nodes for that info? Isn't it too heavy for a node to search 40960 blocks behind to find the live tickets??? 2) How are the 5 "lucky" tickets chosen? Are they chosen deterministically based on the block hash? Or else, WHO gets to decide and HOW (I know: the lottery, but I am asking here how exactly) which 5 are the lucky ones?
I'm fairly certain these are answered pretty thoroughly in the Understanding Proof of Stake thread. However I'll give a quick overview here: 1) Live tickets are simply the set of tickets that have been purchased and have reached maturity, have not expired, and have not already been selected. There is zero trust involved. Every full node updates the live ticket pool by computing this information as a part of the chain sync. 2) The selected tickets are the result of a deterministic PRNG algorithm which is seeded by the serialized header of the previous block. Every node independently knows exactly which tickets have been selected since they all are required by consensus to have the same live ticket pool, the algorithm is deterministic, and they all know the most recent block.
If my understanding is correct, fresh and un-synced nodes don't know about live tickets until they have fully completed sync. When the node has completed sync it has a full list of live tickets via the mechanism described by @davecgh - ie. the heavy operation you describe is part of the sync-ing process. This is one of the factors contributing to a fresh node taking a non-negligible amount of time to get in sync. When a node is in sync and a new block comes in, computing the new set of live tickets is not a heavy operation as it is simply an incremental update to the data already known by the node. Don't take the above as gospel - the main reason I have written it is so that somebody can correct my understanding if it is flawed
That is correct. There is a maximum of 5 votes (which removes 5 live tickets) and a maximum of 20 new tickets maturing per block (since each block can only have a max of 20 new tickets, there can't possibly be any more than that maturing). That means there is a maximum of 25 operations to be performed every 5 minutes on average (target block time). I should also note that in recent versions the live ticket "map" is actually using a purpose built immutable treap that automatically maintains the tickets in sorted order and supports O(log(n)) amortized inserts and deletes as well as O(1) snapshots (important for efficient evaluation of side chains). The target ticket pool size (aka live tickets) is 40960, so you're only talking about a rough max of 400 pointer manipulations per block. I don't remember the exact timing numbers, but I believe it either takes less than a millisecond or at most a few milliseconds to update per block.