Develop an alternative leader scheduling proposal.

[aeyakovenko]

Problem

Our current implementation has a predetermined schedule for leaders to propose a block. The main problems with this approach are:

• leader schedule has to balance both performance and liveness requirements
• network has to wait for unavailable nodes
• network liveness depends on availability of scheduled nodes
• attackers know in advance all the leaders that propose a block

This proposal doesn't address the interactive leader VoteState account creation, and the delegation of votes, as these problems are general to DPOS.

Proposed Solution

A way to non-deterministically select a leader.

Leaders can generate a golden ticket to propose a block.

• N number of bits of a leader's VoteState Account owners signature that must match a PoH hash. This hash can be in between ticks.

The leader must find the golden ticket in the empty PoH Entries leading up to the proposed block. Once the golden ticket is found, the leader can propose the next slot. The Account owner signs the BlockHash of the block that the entries are generated from. Since each validator is resetting it's PoH every time it votes, each validator can search for a golden ticket from that starting point.

The same proposed [fork selection]/fork-selection.md) rules apply. Once a block is voted on, the validator would switch its PoH to reset on this new block, and either a new golden ticket block is proposed, or the next scheduled leader proposes a block.

Grinding

Because the golden ticket is biasable, the last leader has the most opportunity to influence the BlockHash to generate the golden ticket for itself. This BlockHash could be a grinding attack with N cores. Grinding should be a limited attack vector, since the difficulty is determined by the size of the delegates to the VoteState account.

Difficulty

Difficulty is the number of matching bits that the golden ticket needs to match the signature.

The golden ticket connects via PoH entries to a known block with an immutable account balance. So simple token balance can be used to set the difficulty. Hashing with 1 account that contains 100 tokens should generate as many tickets as 2 accounts with 50 tokens.

Generating VDFs for multiple forks

The number of potential forks the attacker can choose from would be limited by the fork selection algorithm. The generated golden ticket needs to be past the lockout distance for the rest of the network, and also be the heaviest fork based on lockout. Let's say the difficulty was set to the network generating a golden ticket block every 3 slots.

For example:

starting with n - 3 forks, the proposed block would only be valid if no one in the network voted, if they have, the golden ticket would need to be in the n + 7 slot, and propose the n + 8 block.

Transaction Ingress point

Because there is no deterministic ingress point, there is no place for validators to forward transactions. This design will end up requiring a shared mempool of transactions between all the nodes just like traditional PoW systems.

The validators already transmit their votes through the gossip network, so the golden ticket block can pick up the validator votes, and any additional transactions that have not been encoded into the ledger. These transactions could come from rejected forks.

Future Work

• This solution still requires a registered VoteState to exist and be valid in the epoch for a leader to propose a out of order block.

[aeyakovenko]

This is reminding me of https://en.wikipedia.org/wiki/ALOHAnet :). I wish I had a proof of this, but since the non-deterministic block generation requires a mempool, i think it will be strictly slower and less efficient than what we are doing.

[aeyakovenko]

whats worth exploring is a combination. Where a valid golden ticket block could be proposed concurrently with a scheduled one.

[aeyakovenko]

@rob-solana woot!!! with the new proposal for delegation #3148, the golden ticket leader can just inject a new votestate with 0 delegates.

[aeyakovenko]

@mvines this might become a mainnet blocker

[mvines]

Ok if so then please move it out of The Future with some details about why it's now a blocker

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs.

[stale]

This stale issue has been automatically closed. Thank you for your contributions.