## 4 Privacy-Preserving Incentive Mechanism
### Collaborative Routing Scheme  
The collaborative routing scheme consists of an off-chain MPC and an on-chain incentive freezing process. The off-chain MPC takes the optimal route flows as public inputs and the value of time of vehicles in the local vehicle group as private inputs to generate route suggestions and associated incentive amounts for vehicles in the group. With the envy-freeness analysis in [21], rational users will always choose the suggested routes. After confirmation from users, the incentives will be frozen in a series of cascading multi-signature wallets for each vehicle until they pass further route validations. First, we describe how \(g\) generates pseudonyms for vehicles that participate in the mechanism for the first time using an Elliptic Curves Cryptography (ECC) based combined-public key (CPK) scheme. Identity-based CPK derives public keys (pseudonyms) from real-world identities; hence, it does not require certificates as traditional public key encryptions, reducing the key management burden [37]. In our case, the public keys are derived from the VIN (Vehicle Identification Number) of vehicles. The identity generation process is as follows:  
1. Select an elliptic curve \(\mathcal{C}\). Let \(\mathcal{H}\) be an addition group of points on \(\mathcal{C}\), and let \(P\) be the generator of \(\mathcal{H}\). \(q\in\mathcal{H}\) is an order of \(\mathcal{H}\) (most encryption/signature schemes in this study are based on ECC; please refer to [16] for ECC basics). 2. Generate an \(m\)-length master private key vector \(\mathcal{X}=(x_{1},x_{2},\dots,\ x_{m})\), where \(x_{i}\) are randomly selected from \(\mathbb{Z}_{q}\). 3. Generate the corresponding public key vector \(\mathcal{Y}=(y_{1},y_{2},\dots,y_{n})\), where \(y_{i}=x_{i}\cdot P\). 4. Using \(\mathcal{X}\) and \(\mathcal{Y}\), generate the private key and public key for each vehicle as follows: \[sk_{ID}=\sum_{i=1}^{m}h_{i}(ID)x_{i}\bmod q,\] (1a) \[pk_{ID}=\sum_{i=1}^{m}h_{i}(ID)y_{i},\] (1b) where \[h_{i}(ID)\] is the \[i\] th bit of the digest of the vehicle's VIN generated by \[H_{0}:\{0,\ 1\}^{*}\rightarrow\{0,\ 1\}^{m}\]. It is trivial to see that \[pk_{ID}=sk_{ID}\cdot P\] holds, i.e., \[(pk_{ID},\ sk_{ID})\] is a valid pair of ECC keys. 5. Send vehicles their private keys through secure communication channels along with the following information as the public parameters of the cryptographic system \((\mathcal{H},q,\ J,(H_{0},H_{1},H_{2},\ H_{3},\ H_{4},H_{5},\ H_{6}),\ E)\), where \(E\) is a symmetric encryption protocol (given cyphertext {y}=E_{k}(x)\); we can obtain the plaintext \(x=E_{k}^{-1}(y)\)), and \(H_{i}\) represents hash functions used in the schemes. Using the pseudonyms, vehicles can initiate and participate in the collaborative routing scheme, which can be described as follows:  
1. One vehicle (defined as the leader of the collaborative routing scheme \(\mathcal{L}^{R}\)) initiates a request for collaborative route updating by sending nearby vehicles the message \(\{ID_{L},\ des,\ sig_{L}\}\), where \(ID_{L}\) is the VIN of \(\mathcal{L}^{R}\), \(des\) is the destination identifier, and \(sig_{L}=sign(sk_{L},\ H_{1}(des))\) is the signature that \(\mathcal{L}^{R}\) signs using its secret key \(sk_{L}\) on the digest of \(des\), \(H_{1}(des)\). 2. Vehicles heading to the same destination and interested in joining the collaborative routing scheme (defined as the followers of the collaborative routing scheme \(\mathcal{T}^{R}\)), after verifying the request (\(isValid(pk_{L},\ des,\ sig_{L})\), each vehicle can reply a signed bit \(1,sig_{ID}=sign(sk_{ID},\ 1)\) together with its VIN \(ID\) to \(\mathcal{L}^{R}\). 3. \(\mathcal{L}^{R}\) collects the responses from \(\mathcal{T}^{R}\), verifies the responses (\(isValid(pk_{ID},\ 1,\ sig_{ID})\), and counts the total number of vehicles participating in this session, \(n_{s}\) (which is the demand of this specific OD pair). 4.