「TezosのProof-of-stake」を編集中
この編集を取り消せます。
下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
| 最新版 | 編集中の文章 | ||
| 1行目: | 1行目: | ||
| − | = | + | = Proof-of-stake in Tezos = |
| − | + | This document provides an in-depth description of the Tezos proof-of-stake algorithm. '''WORK IN PROGRESS, CONSTANTS STILL SUBJECT TO ADJUSTMENT.''' '''THIS DOES NOT CONTAIN CHANGES INTRODUCED BY PVSS.''' | |
| − | == | + | == Blocks == |
| − | + | The Tezos blockchain is a linked list of blocks. Blocks contain a header, and a list of operations. The header itself decomposes into a shell header (common to all protocols) and a protocol specific header. | |
| − | + | Shell header <sub><sub><sub><sub>~</sub></sub></sub>~</sub> | |
| − | + | The shell header contains | |
| − | * <code> level </code> | + | * <code>level</code>: the height of the block, from the genesis block |
| − | * <code> proto </code> | + | * <code>proto</code>: number of protocol changes since genesis (mod 256) |
| − | * <code> | + | * <code>predecessor</code>: the hash of the preceding block. |
| − | * <code> timestamp </code> | + | * <code>timestamp</code>: the timestamp at which the block is claimed to have been created. |
| − | * <code> validation_pass </code> | + | * <code>validation_pass</code>: number of validation passes (also number of lists of lists of operations) |
| − | * <code> fitness </code> | + | * <code>fitness</code>: a sequence of sequences of unsigned bytes, ordered by length and then lexicographically. It represents the claimed fitness of the chain ending in this block. |
| − | * <code> operations_hash </code> | + | * <code>operations_hash</code> The root hash of a merkle tree of a list of root hashes of merkle trees for various sets of operations in the block. |
| − | * <code> context </code> | + | * <code>context</code> Hash of the state of the context after application of this block. Useful for light clients. |
| − | + | Protocol header (for tezos.alpha): <sub><sub>~</sub><sub><sub><sub><sub><sub><sub><sub><sub><sub><sub><sub><sub>~</sub></sub></sub></sub></sub></sub></sub></sub></sub></sub></sub></sub></sub>~~ | |
| − | * <code> signature </code> | + | * <code>signature</code>: a digital signature of the shell and protocol headers (excluding the signature itself). |
| − | * <code> priority </code> | + | * <code>priority</code>: every block height in tezos.alpha is associated with an ordered list of bakers. The first baker in that list is the first one who can bake a block at that height, one minute after the previous block. The second baker in the list can do so, but only two minutes after the previous block, etc, the third baker three minutes after. This integer is the priority of the block. |
| − | * <code> seed_nonce_hash </code> | + | * <code>seed_nonce_hash</code>: a commitment to a random number, used to generate entropy on the chain. Present in only one out of (<code>BLOCKS_PER_COMMITMENT</code> = 32) blocks. |
| − | * <code> proof_of_work_nonce </code> | + | * <code>proof_of_work_nonce</code>: a nonce used to pass a low-difficulty proof-of-work for the block, as a spam prevention measure. |
| − | + | Block size <sub><sub>~</sub>~</sub>~~ | |
| − | + | Tezos does not download blocks all at once, but rather considers headers and various lists of operations separately. In Tezos.alpha, a maximum size in bytes is applied to the list of transactions <code>MAX_TRANSACTION_LIST_SIZE</code> = 500kB (that's 5MB every 10 minutes at most). | |
| − | + | Other lists of operations (endorsements, denounciations, reveals) are limited in terms of number of operations (though the defensive programming style also puts limits on the size of operations it expects). | |
| − | + | This ensure that consensus critical operations do not compete with transactions for block space. | |
| − | == | + | == Delegation == |
| − | Tezos. | + | Tezos.alpha uses a delegated proof-of-stake model. DPOS has come to design a specific type of algorithm used, for instance in in Bitshares. This is ''not'' the model used in Tezos.alpha, though there is a concept of delegation. |
| − | + | Delegates <sub>~<sub>~</sub></sub>~ | |
| − | tezos. | + | In tezos.alpha, tokens are controlled through a private key called the "manager key". Tezos.alpha accounts let the manager specify a public delegate key. This key may be controlled by the manager themselves, or by another party. The responsibility of the delegate is to take part in the proof-of-stake consensus algorithm and in the governance of Tezos. |
| − | |||
| − | + | The manager can generally change the delegate at any time, though contract can be marked to specify an immutable delegate. Though delegation can be changed dynamically, the change only becomes effective after a few cycles. | |
| − | + | There are also default accounts in Tezos, which are just the hash of the public key. These accounts do not have an attached delegate key and do not participate in the proof-of-stake algorithm. | |
| − | + | Finally, delegate accounts (used for placing safety deposits) are automatically delegated to the delegate itself. | |
| − | + | Active and passive delegates <sub><sub><sub><sub><sub><sub><sub><sub><sub><sub><sub><sub>~</sub></sub></sub></sub></sub></sub></sub></sub></sub></sub></sub>~</sub> | |
| − | + | A delegate can be marked as either active or passive. A passive delegate cannot be selected for baking or endorsement. | |
| − | + | A delegate becomes passive for cycle <code>n</code> when they fail to create any of the blocks or endorsements in the past <code>CYCLES_BEFORE_DEACTIVATION</code> = 5 cycles, or to change their security deposit. So, in this case, in cycles <code>n-1</code>, <code>n-3</code>, ..., <code>n - CYCLES_BEFORE_DEACTIVATION</code>. | |
| − | + | A small delegate who is afraid they might be deactivated because they were not given the opportunity to create any block or endorsement can ensure they do not become deactivated by making small, meaningless transactions with their security deposits once every two cycles. | |
| − | + | Discussion: giving <code>CYCLES_BEFORE_DEACTIVATION</code> a small value means the chain adapts more quickly to participants disappearing. It's not unlike the "difficulty adjustment" of Bitcoin. However, a long value would ensure that a minority fork progresses more slowly for a longer period of time than the majority fork. <code>CYCLES_BEFORE_DEACTIVATION</code> gives the majority chain a "headstart". | |
| − | + | This does not affect voting rights for protocol changes. | |
| − | + | Rolls <sub>~</sub>~~ | |
| − | + | In theory, it would be possible to give each token a serial number, and track the specific tokens assigned to specific delegates. However, it would be too demanding of nodes to track assignement at such a granular level. Instead we introduce the concept of rolls. A roll represents a set of coins delegated to a given key. When tokens are moved, or a delegate for a contract is changed, the rolls change delegate according to the following algorithm. | |
| − | + | Each delegate has a stack of roll ids plus some "change" which is always an amount smaller than <code>TOKENS_PER_ROLLS</code>. When tokens are moved from one delegate to the other, first, the change is used. If it is not enough, rolls need to be "broken" which means that they move from the delegate stack to a global, unallocated, roll stack. This is done until the amount is covered, and some change possibly remains. | |
| − | + | Then, the other delegate is credited. First the amount is added to the "change". If it becomes greater than <code>TOKENS_PER_ROLLS</code>, then rolls are unstacked from the global unallocated roll stack onto the delegate stack. If the global stack is empty, a fresh roll is created. | |
| − | + | This preserves the property that if the delegate is changed through several transactions, the roll assignment is preserved, even if each operation moves less than a full roll. | |
| − | + | The advantage of tracking tokens in this way is that a delegate creating a malicious fork cannot easily change the specific rolls assigned to them, even if they control the underlying tokens and shuffle them around. | |
| − | + | Rolls hold <code>TOKENS_PER_ROLLS</code> = 10,000 tokens and thus there should be about 80,000 rolls in the Tezos foundation's planned genesis block, though the number of rolls will increase with inflation and / or participation in the delegation. | |
| − | |||
| − | + | Roll snapshots <sub><sub><sub><sub><sub><sub>~</sub></sub></sub></sub></sub></sub>~ | |
| − | + | Roll snapshots represent the state of rolls for a given block. Roll snapshots are taken every <code>BLOCKS_PER_ROLL_SNAPSHOT</code> = 256 blocks, that is 16 times per cycle. There is a tradeoff between memory consumption and economic efficiency. If roll snapshots are too frequent, they will consumme a lot of memory. If they are too rare, strategic participants could purchase many tokens in anticipation of a snapshot and resell them right after. | |
| − | + | == Cycles == | |
| − | + | Blocks in the Tezos.Alpha Blockchain are grouped into "cycles" of <code>BLOCKS_PER_CYCLE</code> = 4,096 blocks. Since blocks are at least <code>TIME_BETWEEN_BLOCKS</code> = one minute apart, this means a cycle lasts ''at least'' 2 days, 20 hours, and 16 minutes. In the following description, the current cycle is referred to as <code>n</code>, it is the nth cycle from the beginning of the chain. Cycle <code>(n-1)</code> is the cycle that took place before the current one, cycle <code>(n-2)</code> the one before, cycle <code>(n+1)</code> the one after, etc. | |
| − | + | At any point, the tezos shell will not implicitly accept a branch whose fork point is in a cycle more than <code>ALLOWED_FORK</code> = 5 cycles in the past (that is ''at least'' 14 days, 5 hours, and 20 minutes). | |
| − | + | Security deposits <sub>~<sub><sub><sub><sub><sub>~</sub></sub></sub></sub></sub></sub>~ | |
| − | + | The cost of a security deposit is <code>BLOCK_SECURITY_DEPOSIT</code> = 512 XTZ per block created and <code>ENDORSEMENT_SECURITY_DEPOSIT</code> = 64 XTZ per endorsement. | |
| − | + | Each delegate key has an attached security deposit account controlled by the same key. Delegates can withdraw and deposit in this account, but they cannot withdraw more than the "frozen" amount. Each blocks created, each endorsement signed increases the amount that is frozen. | |
| − | + | It is possible to deposit a bond just prior to creating a block requiring this deposit. Deposits for blocks and endorsements in cycle <code>n</code> are "unfrozen" at the end of cycle <code>n+ALLOWED_FORK</code>. | |
| − | + | Since deposits are locked for a period of <code>ALLOWED_FORK</code> one can compute that at any given time, about ((<code>BLOCK_SECURITY_DEPOSIT</code> + <code>ENDORSEMENT_SECURITY_DEPOSIT</code> * <code>ENDORSERS_PER_BLOCK</code>) * (<code>ALLOWED_FORK</code> + 1) * <code>BLOCKS_PER_CYCLE</code>) / <code>763e6</code> = 8.25% of all tokens should be held as security deposits. It also means that a delegate should own over 8.25% of the amount of token delegated to them in order to not miss out on creating any block. | |
| − | + | Baking rights <sub><sub><sub><sub><sub>~</sub></sub></sub></sub></sub>~~ | |
| − | + | Baking in tezos.alpha is the action of signing and publishing a block. In Bitcoin, the right to publish a block is associated with solving a proof-of-work puzzle. In tezos.alpha, the right to publish a block in cycle <code>n</code> is assigned to a randomly selected roll in a randomly selected roll snapshot from cycle <code>n-ALLOWED_FORK-2</code>. | |
| − | + | We admit, for the time being, that the protocol generates a random seed for each cycle. From this random seed, we can seed a CSPRNG which is used to draw baking rights for a cycle. | |
| − | + | To each position, or slot, in the cycle, is associated a priority list of bakers. This is drawn randomly, with replacement, from the set of active rolls. Each roll is associated with the public key of a delegate, therefore, for each slot in the cycle, we have an ordered list of public keys which may create and sign a block. It is possible that the same public key appears multiple times in this list. | |
| − | + | The delegate with the highest priority can bake a block with a timestamp greater than <code>timestamp_of_previous_block</code> plus <code>TIME_BETWEEN_BLOCKS</code> = one minute. The one with the kth highest priority, <code>TIME_BETWEEN_BLOCKS + k * TIME_DELAY_FOR_PRIORITY</code> = (1 + k) minutes. | |
| − | + | In future versions, <code>TIME_DELAY_FOR_PRIORITY</code> may be set to a lower value than <code>TIME_BETWEEN_BLOCKS</code>. | |
| − | + | Baking a block gives a block reward of <code>BLOCK_REWARD</code> = 16 XTZ plus all fees paid by transactions inside the block. | |
| − | + | Endorsements <sub><sub><sub><sub>~</sub></sub></sub>~</sub> | |
| − | + | To each baking slot, we associate a list of <code>ENDORSERS_PER_BLOCK</code> = 32 "endorsers". Endorsers are drawn from the set of delegates, by randomly selecting 32 rolls with replacement. | |
| − | + | Endorsers receive a reward (at the same time as block creators do). The reward is <code>ENDORSEMENT_REWARD</code> = 2 / <code>BLOCK_PRIORITY</code> where block priority starts at 1. So the endorsement reward is only half if the block of priority 2 for a given slot is being endorsed. | |
| − | + | Inflation <sub>~<sub>~</sub></sub>~ | |
| − | + | Inflation from block rewards and endorsement reward is at most <code>ENDORSERS_PER_BLOCK</code> * <code>ENDORSEMENT_REWARD</code> + <code>BLOCK_REWARD</code> = 80 XTZ. This means at most 5.51% annual inflation. | |
| − | + | Random seed <sub><sub><sub>~</sub></sub></sub>~<sub>~</sub> | |
| − | + | Cycle <code>n</code> is associated with a random seed, a 256 bit number generated at the end of cycle <code>(n-ALLOWED_FORK-1)</code> using commitments made during cycle <code>(n-ALLOWED_FORK-2)</code>, in one out of every <code>BLOCKS_PER_COMMITMENT</code> = 32 blocks. | |
| − | + | The commitment must be revealed by the original baker during cycle <code>(n-ALLOWED_FORK-1)</code> under penalty of forfeiting the security deposit. | |
| − | + | A "revelation" is an operation, and multiple revelations can thus be included in a block. The revelations are hashed together to generate a random seed at the very end of cycle <code>(n-ALLOWED_FORK-1)</code>. | |
| − | + | Revelations are free operations which do not compete with transactions for block space. Up to <code>MAX_REVELATIONS_PER_BLOCK</code> = 32 revelations can be contained in any given block. Thus, 1 / (<code>MAX_REVELATIONS_PER_BLOCK</code> * <code>BLOCKS_PER_COMMITMENT</code>) = 1/1024 of the blocks in the cycle are sufficient to include all revelations. | |
| + | |||
| + | == Denounciations == | ||
| + | |||
| + | If two endorsements are made for the same slot or two blocks at the same height by a delegate, this can be denounced. The denounciation would be typically be made by the baker, who includes it as a special operation. In a first time, denounciation will only forfeit the security deposit for the doubly signed operation. However, over time, as the risk of accidental double signing becomes small enough, denounciation will forfeit the entirety of the safety deposits. Half is burned, and half is added to the block reward. | ||
