Multi-objective optimization has been extensively used to eficiently solve real-world problems. In this work, we address privacy-preserving multi-objective optimization of non-fungible token bartering problem with the consideration of two conflicting objectives as: (i) the maximization of the number of bids satisfied and (ii) the maximization of the budget after the bids costs are paid. To solve this problem, we propose a novel multiobjective approach (i.e. zkMOBF - Z ero K nowledge-based Multi-Objective Bellman-Ford) utilizing zero-knowledge proofs to preserve the privacy of these bids. Our approach takes the global bid graph as input and extracts optimized bartering solution(s) through four phases. Publicly-verifiable proof of this approach is generated of-chain and later verified on-chain on Ethereum Sepolia test network. In our empirical study, we measure proof generation/verification times, proof artifact sizes and blockchain gas consumption for three bartering scenarios. The work justifies the validity and the applicability of our approach.
Multi-objective optimization refers to a specific group of problems that involve the minimization or maximization of multiple objectives simultaneously [1]. Multi-objective modelings of real-world problems may ofer certain benefits over their single-objective counterparts by allowing for the consideration of trade-ofs. For instance, single-objective modelings may neglect significant objectives while trying to push the limit of only one objective (e.g. neglecting cost to minimize time) where it may lead to practically infeasible solutions (e.g. too high cost to pay). In the literature, there exist many works that adopt multi-objective techniques [2, 3, 4]. Therefore, we model a multi-objective bartering with two conflicting objectives in this work as the maximization of number of bids satisfied and maximization of the budget after bid costs are paid. The cost of a bid may result from the urgency to satisfy it where an urgent bid is associated with a lower cost.
In certain scenarios, privacy concerns may arise in real-world multi-objective optimization while processing confidential user data (e.g. recommendation systems on mobile user data [ 5]). In this context, we define privacy-preserving variant of multi-objective optimization as a more specific group of problems with multiple objectives, which ensures the confidentiality of certain data during computation. There also exist works that address the notion of privacy-preservation on blockchain, especially for federated learning [6]. However, to the best of our knowledge, there exists no work that considers both privacy-preservation and multi-objective optimization on blockchains in the literature. In this work, we propose a multi-objective approach for token bartering by preserving the privacy of bids via zero-knowledge proofs and deploying the corresponding contract on blockchain for proof verification.
The main contributions of our work can be enumerated as follows: • We address privacy-preserving multi-objective optimization of our token bartering problem which involves performing a publicly-verifiable computation on the private bids to find an optimal
CEUR Workshop
ISSN1613-0073
bartering solution by considering multiple objectives. • We propose a novel privacy-preserving approach (i.e. zkMOBF ) with four phases: (i) detecting cycles in bid graph with the Bellman-Ford algorithm, (ii) evaluating these cycles (i.e. solutions) for two conflicting objectives, (iii) ranking the feasible solutions with pareto-domination to find the non-dominated solutions and (iv) applying a utility function over the non-dominated solutions to determine the final solution. To the best of our knowledge, this is the first work that introduces novelty of solving a multi-objective problem on zero-knowledge proof in the literature. • We perform experiments over three scenarios (i.e. small, medium and large) with respect to the number of bids to measure (i) proof generation and verification times, (ii) proof artifact size (e.g. size of proof circuit) and (iii) blockchain gas consumption for contract deployment. This study justifies the applicability of our protocol.
Privacy-preserving multi-objective bartering problem refers to a secure optimization problem which
aims to find the best token bartering solution(s) with respect to the available bids and by considering
several conflicting objectives at the same time. In the scope of the problem, we define the set of bidders
as:
where represents the th bidder while is the total number of bidders. We also define the set of
non-fungible tokens (e.g. NFTs) as:
(
) = { 1( ), 2( )} 1( ) = ..
∑ − ⋅ ≥ ∑ + ⋅ where represents the th token while is the total number of tokens. Each bidder is associated with a bid as: also assume that each bidder can propose one bid at most at a time. where − ∈ is the token to be supplied, + ∈ is the token to be demanded and the bid while Φ is the set of all bids. The problem is a single-token single-instance bartering problem where bidders can supply and demand at most one instance of one token (| −| = | +| = 1). Here, we is the cost of
The multi-objective modeling of this problem evaluates the set of feasible solutions with several
objectives simultaneously by mapping each solution ∶ ⟨ 0 , 1 , … , , … , , −1 ⟩ and ∈ {0, 1} from
the decision space to a point in the objective space:
where Equation (
We present a simple bartering scenario in Fig. (
In this section, we propose the zkMOBF approach with four phases as: (i) detecting cycles on bid graph
with the Bellman-Ford algorithm, (ii) evaluating feasible cycles (i.e. solutions) with the objectives, (iii)
ranking solutions with pareto-domination and (iv) decision-making with utility function for the final
solution. This approach is: (i) privacy-preserving since it protects the privacy of bids throughout the
calculations, (ii) multi-objective since it considers the optimization of two objectives at the same time, (iii)
publicly-verifiable since the of-chain proof generation for the calculations can be verified in blockchain,
(iv) non-interactive since it does not require communication during proof generation or verification.
We present where zkMOBF is positioned to solve the privacy-preserving multi-objective bartering
problem in Fig. (
The bids of the bidders constitute the global bid graph altogether. The constraint given in Equation (
The cycles (i.e. feasible solutions) found in the given global bid graph must be evaluated with respect to
the existing objectives of the multi-objective optimization to find their qualities. We already
mathematically define our two objectives in Equation (
In single-objective optimization, the solutions can be ranked by simply sorting their values on that
objective ascendingly or descendingly with respect to the type of the problem (i.e. minimization or
maximization). However, multi-objective optimization requires a more sophisticated ranking mechanism
where we apply pareto-domination in this work. This technique is based on pairwise solution comparison
where a solution 1 dominates another solution 2 in case 1 is no worse than 2 for all the objectives
and 1 is strictly better than 2 in at least one objective, 2 ≺ 1. More formally:
∀ ( 2) ≤ ( 1) ∧ ∃ ( 2) < ( 1)
(
In our work, the third phase generates a pareto-optimal set (i.e. POS) that consists of only the
nondominated solutions by cleansing the useless solutions for our problem. The selection of the final
solution to be applied over the bids from this set requires an additional phase. For this phase, we
incorporate a utility function that represents a group of probabilities to measure user preferences.
These preferences simply show how important an objective is with respect to the other objective(s).
Since we have two objectives in our problem, we can represent this function as ∶ ⟨ 1, 2⟩ where 1
and 2 are the probabilities for the first and second objectives, respectively by satisfying the condition
of 1 + 2 = 1. The calculations for this phase correspond to Lines 11-14 in Fig. (
We use the ZoKrates framework [8] to implement zkMOBF over zero-knowledge proof. The proof generations and verifications are performed of-chain on the command line. The smart contracts corresponding to the proofs are automatically generated by the framework itself and ready to be deployed on Ethereum Sepolia only for proof verification. During our experiments, we consider three increasingly-complex graphs as small (with 10 bids), medium (with 30 bids) and large (with 50 bids). The open-source implementation of zkMOBF is available in our website [9] for further inspection and experimental reproducibility. The experiments are carried out on MacBook Air with M2 chip, 8 GB memory and 8 cores.
In this experiment, we measure the proof generation and verification times on the command line with ten independent runs. The results of the experiment are given in Table 1 for the small, medium and large bid graphs. From the table, we simply observe that the time to generate proof increases with the increasing graph complexity (e.g. from 23.67 seconds for small to 188.75 seconds for large). But, the standard deviations between runs are quite low (e.g. 0.01, 1.2 and 1.8 seconds for small, medium and large, respectively). On the other hand, we observe that the proof verification remains constant regardless of the graph complexity. This implies that the proof generation is computationally more expensive than the proof verification, especially for complex instances. Hence, ZoKrates strategically moves proof generation out of blockchain to external nodes while still keeping proof verification on-chain.
In this experiment, we measure the size of several proof artifacts including the proof circuit, the proving key, the verification key and the proof itself. The results of the experiment are given in Table 2 for the small, medium and large bid graphs. From the table, we observe that the number of constraints in circuits and the proving key size increase with the increasing graph complexity (e.g. from +1.5M for small to +8.5M for large in circuits and from 0.63GB for small to 3.78GB for large in proving key). On the other hand, verification keys and proofs remain constant all the time. This is beneficial for blockchain applications since verification keys and proofs are processed on-chain while proving keys are stored of-chain. For the large graph, the proving key is x2.7M larger than the verification key while the proof is the shortest.
In this experiment, we simply deploy the smart contracts that the ZoKrates framework automatically generates to blockchain. The structures of these contracts for small, medium and large graphs are basically the same except the verification keys. These keys result from the one-time setup where they are perfectly matched with their corresponding proving keys. According to our experiments, the smart contracts need approximately 1,069,149 gas units (i.e. approximately $3.51) to be deployed on Ethereum Sepolia.
We address the privacy-preserving multi-objective bartering problem to find optimal bartering solution(s) to be applied over the bids. It considers two objectives as the maximization of the number of bids and the maximization of the budget left over. For the problem, we contribute a novel privacy-preserving approach (i.e. zkMOBF ) on zero-knowledge proof by incorporating the Bellman-Ford algorithm, the nondominated ranking and the utility function-based decision-making. We evaluate the performance over three bartering scenarios with increasing complexity to measure proof generation times, proof artifact size and blockchain gas consumption. This empirical study indicates the validity and applicability of the approach. In the future, we also plan to construct solutions as union of cycles. During the preparation of this work, the author(s) used ChatGPT in order to: Grammar and spelling check, Peer review simulation. After using this tool/service, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content.