anza-xyz / anza-xyz/kit

More sophisticated transaction planner based on multiple constraints

未關閉
#1,498 2 則留言 2 個 reaction 已指派 0 人 在 GitHub 檢視
主要語言
TypeScript
星號
695
分支
210
平均合併
21 小時 33 分鐘
30 天內合併 PR
90

描述

Simplifying a lot, the transaction planner (after #1497) does something like:

For each instruction `i`, for each partially packed transaction `t`, add `i` to `t`. If it compiles to a transaction under the size limit, continue. Else try another `t`. Else create a new message.

The 'if it compiles' part here is now doing a lot of work. If the instruction takes the transaction over 64 accounts, or over 12 signers, or over 64 instructions, then compile will throw.

It's likely that we could write a more optimal algorithm, that can find an instruction that does not violate constraints, by making the planner itself aware of these constraints. This would probably become some variant of a multi-dimensional knapsack problem, with dimensions like number of accounts, number of signers, number of bytes. The goal would be (probably) to minimise the total number of transactions for a given instruction plan.

This is complex because the cost of adding an instruction depends on what is already added. An instruction that uses 20 accounts may add anywhere from 0-20 new accounts to the transaction, depending which accounts are used by existing instructions. This also affects how many bytes it adds, and how many signers. Additionally we must respect the sequential constraints between instructions.

My initial guess is that an algorithm might want to optimise for instructions with shared accounts being packed together as a starting point.

貢獻指南

開啟貢獻指南

評估

這個 Issue 還沒有評估資料。

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。