Distributed blockbuilding networks via secure knapsack auction

The article proposes building distributed block builder networks on a secure knapsack auction, run with multiparty computation (MPC), so that no participant learns others' transactions or bids. It compares a dynamic programming solver, which always finds an optimal 0-1 knapsack solution but takes O(nW) time and storage in its naive form, with a greedy algorithm that guarantees a result within a factor of 1/2 of optimal and runs in O(n log n) time with O(n) storage. The authors say benchmarks support pursuing the greedy approach, and they argue that MPC suits this setting better than zero-knowledge proofs, fully homomorphic encryption, or SGX because it supports multiple mutually distrusting parties and returns the computed result.