{"action":"created","issue":{"url":"https://api.github.com/repos/stellar/stellar-protocol/issues/75","repository_url":"https://api.github.com/repos/stellar/stellar-protocol","labels_url":"https://api.github.com/repos/stellar/stellar-protocol/issues/75/labels{/name}","comments_url":"https://api.github.com/repos/stellar/stellar-protocol/issues/75/comments","events_url":"https://api.github.com/repos/stellar/stellar-protocol/issues/75/events","html_url":"https://github.com/stellar/stellar-protocol/issues/75","id":289383873,"node_id":"MDU6SXNzdWUyODkzODM4NzM=","number":75,"title":"Update \"surge pricing\" to be more fair","user":{"login":"MonsieurNicolas","id":4213763,"node_id":"MDQ6VXNlcjQyMTM3NjM=","avatar_url":"https://avatars3.githubusercontent.com/u/4213763?v=4","gravatar_id":"","url":"https://api.github.com/users/MonsieurNicolas","html_url":"https://github.com/MonsieurNicolas","followers_url":"https://api.github.com/users/MonsieurNicolas/followers","following_url":"https://api.github.com/users/MonsieurNicolas/following{/other_user}","gists_url":"https://api.github.com/users/MonsieurNicolas/gists{/gist_id}","starred_url":"https://api.github.com/users/MonsieurNicolas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MonsieurNicolas/subscriptions","organizations_url":"https://api.github.com/users/MonsieurNicolas/orgs","repos_url":"https://api.github.com/users/MonsieurNicolas/repos","events_url":"https://api.github.com/users/MonsieurNicolas/events{/privacy}","received_events_url":"https://api.github.com/users/MonsieurNicolas/received_events","type":"User","site_admin":false},"labels":[{"id":1012947435,"node_id":"MDU6TGFiZWwxMDEyOTQ3NDM1","url":"https://api.github.com/repos/stellar/stellar-protocol/labels/core","name":"core","color":"1d76db","default":false}],"state":"open","locked":false,"assignee":{"login":"MonsieurNicolas","id":4213763,"node_id":"MDQ6VXNlcjQyMTM3NjM=","avatar_url":"https://avatars3.githubusercontent.com/u/4213763?v=4","gravatar_id":"","url":"https://api.github.com/users/MonsieurNicolas","html_url":"https://github.com/MonsieurNicolas","followers_url":"https://api.github.com/users/MonsieurNicolas/followers","following_url":"https://api.github.com/users/MonsieurNicolas/following{/other_user}","gists_url":"https://api.github.com/users/MonsieurNicolas/gists{/gist_id}","starred_url":"https://api.github.com/users/MonsieurNicolas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MonsieurNicolas/subscriptions","organizations_url":"https://api.github.com/users/MonsieurNicolas/orgs","repos_url":"https://api.github.com/users/MonsieurNicolas/repos","events_url":"https://api.github.com/users/MonsieurNicolas/events{/privacy}","received_events_url":"https://api.github.com/users/MonsieurNicolas/received_events","type":"User","site_admin":false},"assignees":[{"login":"MonsieurNicolas","id":4213763,"node_id":"MDQ6VXNlcjQyMTM3NjM=","avatar_url":"https://avatars3.githubusercontent.com/u/4213763?v=4","gravatar_id":"","url":"https://api.github.com/users/MonsieurNicolas","html_url":"https://github.com/MonsieurNicolas","followers_url":"https://api.github.com/users/MonsieurNicolas/followers","following_url":"https://api.github.com/users/MonsieurNicolas/following{/other_user}","gists_url":"https://api.github.com/users/MonsieurNicolas/gists{/gist_id}","starred_url":"https://api.github.com/users/MonsieurNicolas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MonsieurNicolas/subscriptions","organizations_url":"https://api.github.com/users/MonsieurNicolas/orgs","repos_url":"https://api.github.com/users/MonsieurNicolas/repos","events_url":"https://api.github.com/users/MonsieurNicolas/events{/privacy}","received_events_url":"https://api.github.com/users/MonsieurNicolas/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/stellar/stellar-protocol/milestones/2","html_url":"https://github.com/stellar/stellar-protocol/milestone/2","labels_url":"https://api.github.com/repos/stellar/stellar-protocol/milestones/2/labels","id":3518303,"node_id":"MDk6TWlsZXN0b25lMzUxODMwMw==","number":2,"title":"core v11","description":"","creator":{"login":"jedmccaleb","id":399067,"node_id":"MDQ6VXNlcjM5OTA2Nw==","avatar_url":"https://avatars1.githubusercontent.com/u/399067?v=4","gravatar_id":"","url":"https://api.github.com/users/jedmccaleb","html_url":"https://github.com/jedmccaleb","followers_url":"https://api.github.com/users/jedmccaleb/followers","following_url":"https://api.github.com/users/jedmccaleb/following{/other_user}","gists_url":"https://api.github.com/users/jedmccaleb/gists{/gist_id}","starred_url":"https://api.github.com/users/jedmccaleb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jedmccaleb/subscriptions","organizations_url":"https://api.github.com/users/jedmccaleb/orgs","repos_url":"https://api.github.com/users/jedmccaleb/repos","events_url":"https://api.github.com/users/jedmccaleb/events{/privacy}","received_events_url":"https://api.github.com/users/jedmccaleb/received_events","type":"User","site_admin":false},"open_issues":2,"closed_issues":0,"state":"open","created_at":"2018-07-24T00:10:34Z","updated_at":"2018-08-02T21:44:54Z","due_on":null,"closed_at":null},"comments":5,"created_at":"2018-01-17T19:25:30Z","updated_at":"2018-09-10T21:30:19Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"I think that the implementation to enforce a maximum number of transactions predated the addition of operations.\r\n\r\nHow this works today:\r\nthe \"surge pricing\" logic kicks in when a validator encounters more transaction candidates than `maxTxPerLedger` (defined in the ledger header). The first pass at filtering is done by sorting transaction candidates by fee ratio (defined as `fee/min_fee` where `min_fee` is `base_fee*nb_operations`).\r\nThe idea is that in a situation where too many transactions are pending, we prioritize the ones with higher average fees.\r\nIf fees are equal, the `sourceID` of the transactions is used as a tie breaker.\r\n\r\nProposal for new behavior:\r\n1. build a transaction set that maximizes the number of operations in a ledger, up to the maximum `maxOperationsPerLedger` defined by the network\r\n2. sort transactions using the average fee per operation as the way to compare transaction fees (done simply by comparing `left.fee * right.nb_ops` with `right.fee * left.nb_ops`)\r\n3. break ties using a deterministic yet randomizing scheme, giving priority to different accounts for each ledger.  Using `sourceID XOR hash_ofPreviousLedger` seems to fit the bill.\r\n\r\nIn order to implement 1 and 2, the candidate transaction set is build as follows:\r\n1. trim the transaction set such that it only includes valid transactions (including sequence number and fee)\r\n2. perform a lexicographical sort the candidate transactions by fee (descending), xored `source ID` (ascending), sequence number (ascending)\r\n3. iterate over that sorted list:\r\n   1. if the transaction can fit in the candidate set (ie, `newTxSetOpCount <= maxOperationsPerLedger`), add it to the set\r\n   2. otherwise, skip the transaction and any other transactions from the same source account\r\n\r\nSomething else to discuss here is what to do with the ledger header.\r\nRight now the XDR is:\r\n```\r\nstruct LedgerHeader\r\n{\r\n    uint32 ledgerVersion;    // the protocol version of the ledger\r\n    Hash previousLedgerHash; // hash of the previous ledger header\r\n    StellarValue scpValue;   // what consensus agreed to\r\n    Hash txSetResultHash;    // the TransactionResultSet that led to this ledger\r\n    Hash bucketListHash;     // hash of the ledger state\r\n\r\n    uint32 ledgerSeq; // sequence number of this ledger\r\n\r\n    int64 totalCoins; // total number of stroops in existence.\r\n                      // 10,000,000 stroops in 1 XLM\r\n\r\n    int64 feePool;       // fees burned since last inflation run\r\n    uint32 inflationSeq; // inflation sequence number\r\n\r\n    uint64 idPool; // last used global ID, used for generating objects\r\n\r\n    uint32 baseFee;     // base fee per operation in stroops\r\n    uint32 baseReserve; // account base reserve in stroops\r\n\r\n    uint32 maxTxSetSize; // maximum size a transaction set can be\r\n\r\n    Hash skipList[4]; // hashes of ledgers in the past. allows you to jump back\r\n                      // in time without walking the chain back ledger by ledger\r\n                      // each slot contains the oldest ledger that is mod of\r\n                      // either 50  5000  50000 or 500000 depending on index\r\n                      // skipList[0] mod(50), skipList[1] mod(5000), etc\r\n\r\n    // reserved for future use\r\n    union switch (int v)\r\n    {\r\n    case 0:\r\n        void;\r\n    }\r\n    ext;\r\n};\r\n```\r\n\r\nin particular the line\r\n```\r\n    uint32 maxTxSetSize; // maximum size a transaction set can be\r\n```\r\n\r\nThere are two options on how we would change the ledger header:\r\n1. change the name of `maxTxSetSize` to be more generic, something like `txSetSize`, that maps to \"number of transactions\" in older versions of the protocol and \"number of operations\" in newer versions of the protocol (binary format stays the same).\r\n2. make the `ext` union support `v = 1`, we would add the new field\r\n```\r\n    // reserved for future use\r\n    union switch (int v)\r\n    {\r\n    case 0:\r\n        void;\r\n    case 1:\r\n        uint32 maxOperationsPerLedger;\r\n    }\r\n    ext;\r\n```\r\n`maxTxSize` would be set to `numeric_limits<uint32>::max()`\r\n\r\nI prefer option 1 as it keeps the ledger header tidy.\r\nThere are very few consumers of this field, and for the most part only use it for reporting. Code that actually cares about it can, just like core's implementation, use it based on what the protocol version is.\r\n\r\nThis issue was first opened as a core issue https://github.com/stellar/stellar-core/issues/1030\r\n"},"comment":{"url":"https://api.github.com/repos/stellar/stellar-protocol/issues/comments/420067904","html_url":"https://github.com/stellar/stellar-protocol/issues/75#issuecomment-420067904","issue_url":"https://api.github.com/repos/stellar/stellar-protocol/issues/75","id":420067904,"node_id":"MDEyOklzc3VlQ29tbWVudDQyMDA2NzkwNA==","user":{"login":"MonsieurNicolas","id":4213763,"node_id":"MDQ6VXNlcjQyMTM3NjM=","avatar_url":"https://avatars3.githubusercontent.com/u/4213763?v=4","gravatar_id":"","url":"https://api.github.com/users/MonsieurNicolas","html_url":"https://github.com/MonsieurNicolas","followers_url":"https://api.github.com/users/MonsieurNicolas/followers","following_url":"https://api.github.com/users/MonsieurNicolas/following{/other_user}","gists_url":"https://api.github.com/users/MonsieurNicolas/gists{/gist_id}","starred_url":"https://api.github.com/users/MonsieurNicolas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MonsieurNicolas/subscriptions","organizations_url":"https://api.github.com/users/MonsieurNicolas/orgs","repos_url":"https://api.github.com/users/MonsieurNicolas/repos","events_url":"https://api.github.com/users/MonsieurNicolas/events{/privacy}","received_events_url":"https://api.github.com/users/MonsieurNicolas/received_events","type":"User","site_admin":false},"created_at":"2018-09-10T21:30:19Z","updated_at":"2018-09-10T21:30:19Z","author_association":"CONTRIBUTOR","body":"I have been thinking about this a bit more.\r\n\r\nAs we're looking at fairness, I think that it's actually important to preserve the \"round robin\" property that we have when applying transactions (for transactions with the same fee ratio) otherwise we may end allocating too many transactions from the same account in the same ledger.\r\n\r\nThis ends up being pretty much what @robdenison described (reworded below to summarize).\r\n\r\nI would suggest not using the next transaction fee ratio to break ties, but instead use pseudo-randomness.\r\n\r\nSo the algorithm is:\r\n1. for each account, construct a queue of transactions for that account, sorted by sequence number in ascending order\r\n2. construct a heap of those queues, sorted by:\r\n    * the fee rate of the first transaction in each queue (so that the queue whose first transaction has the highest fee rate is on top of the heap)\r\n     * account ID (pseudo-random)\r\n3. `nb_operations_to_add = txSetSize`\r\n4. while (`nb_operations_to_add > 0 && !heap.empty()`)\r\n   * queue = heap.pop()\r\n   * if nb_operations(first transaction \"tx\" from queue)  <= nb_operations_to_add\r\n     * push tx into txSet\r\n     * nb_operations_to_add = nb_operations_to_add - nb_operations(tx)\r\n     * pop tx from queue\r\n     * if queue non empty, push it into the heap\r\n  "}}
{"actor":{"display_login":"MonsieurNicolas"}}