anza-xyz / anza-xyz/kit

More sophisticated transaction planner based on multiple constraints

Aberta
#1,498 2 comentários 2 reações 0 responsáveis Ver no GitHub
Linguagem predominante
TypeScript
Estrelas
695
Forks
210
Merge médio
21h 33min
PRs com merge (30d)
90

Descrição

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.

Guia de contribuição

Abrir o guia de contribuição

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.