# Term Finance Improvement Proposal

## Abstract
This document proposes a series of smart contract changes to infinitely scale Term Finance's auction model by use of a ZK-powered architecture. It aims to provide a more efficient replacement to the current auction mechanism ensuring a future-proof protocol.

## Motivation

Currently, the gas cost to clear and settle a Term Finance auction scales linearly with the number of bids and offers. This translates to lower protocol revenue and higher servicing fees for borrowers. Furthermore, the number of bids and offers that the protocol is able to match is limited by Ethereum's block gas limit, and the maximum for each is hardcoded to be $150$. While this ceiling has not been reached yet, it still constrains how much the protocol can grow.

The motivation behind this proposal is to implement a ZK-based, fixed gas-cost model to clear and settle auctions to i) effectively remove the block gas limit constraint, and ii) increase protocol revenue and lower servicing fees. The directive behind this proposal is to do so in the **least invasive way possible**, aiming to keep most of the legacy code, both to reduce development time and audit complexity.

## Specification

This proposal primarily affects the entire auction process: placing sealed bids/offers, revealing bids/offers, computing the clearing price, and settling and clearing the auction.

### Placing/Updating a Bid/Offer

The interface for placing/updating a bid/offer stays mostly unaltered, except for using a `uint92` instead of `bytes32` to define the unique identifier, `id`, for each bid/offer.

Instead of directly storing all order information onchain, we use a [hash chain](https://en.wikipedia.org/wiki/Hash_chain) to encode it into a single `uint256` value. This value defines a cryptographic commitment to all the bids/offers that were made during the entire auction window. Each time a new order is placed, we update this hash chain. This can look something like:

// Placing/updating a bid
accBidHash = keccak256(abi.encodePacked(accBidHash, bid.hash()));

// Placing/updating an offer
accOfferHash = keccak256(abi.encodePacked(accOfferHash, offer.hash()));

In order to keep track of the locked amount behind each order, we also need to define the mappings:

// Indexed by abi.encodePacked(bidder, id)
mapping(bytes32 => uint256) lockedBids;

// Indexed by abi.encodePacked(offeror, id)
mapping(bytes32 => uint256) lockedOffers;

Which get correspondingly updated each time a bidder/offeror places or updates a bid/offer.

Note how this hash chain-based approach would also reduce the gas cost associated with placing bids and offers, which are directly incurred by the users. This is because the order information no longer needs to be stored onchain, and is instead *encoded* into a single `uint256` value.

### Revealing a Bid/Offer

The interface for revealing a bid/offer stays unaltered. The `id` associated with each bid/offer is defined as `abi.encodePacked(bidder, id)` or `abi.encodePacked(offeror, id)`, respectively.

Instead of directly storing all revealed prices onchain, we use a [hash chain](https://en.wikipedia.org/wiki/Hash_chain) to encode it into the same `uint256` value defined above. This value therefore commits to the entire auction window and reveal period. When prices are revealed, we update this hash chain. This can look something like:

// Revealing a bid
accBidHash = keccak256(abi.encodePacked(
    accBidHash,
    bidId,
    bidPrice,
    bidNonce
));

// Revealing an offer
accOfferHash = keccak256(abi.encodePacked(
    accOfferHash,
    offerId,
    offerPrice,
    offerNonce
));

Contrary to the current design, **the validity of the revealed price is not checked onchain**. This check is later done *inside the ZK proof*, which equally prevents tampering with the price. If the price that was submitted onchain cannot be verified inside the ZK proof, the order is considered as left on the table, and tenders unlocked.

Since the frontend can directly check if the revealed price is valid, there is no need to rely on a smart contract to do this check. This logic is instead offset to the ZK proof, equally preventing any tampering. Note how this hash chain-based approach would also reduce the gas cost associated with revealing bids and offers.

### Generating the Auction Proof

The general outline of the auction proof is as follows:
1. All valid placed bids/offers are loaded.
2. All valid revealed prices are loaded.
3. The values `accBidHash` and `accOfferHash` are reconstructed, and must match those recorded onchain.
4. A clearing rate is computed, as defined by the `_calculateClearingPrice()` function.
5. Bids and offers are either assinged or left on the table.
6. A single cryptographic commitment, `auctionResultRoot`, is computed, encoding the the entire auction results.

In essence, the proof verifies the same logic as defined in the current `completeAuction()` function, but instead of settling fills and unlocking tenders left on the table, it commits to these results by use of a [lean incremental Merkle tree](https://zkkit.pse.dev/classes/_zk_kit_lean_imt.LeanIMT.html). Inside this tree are encoded all auction results: collateral tokens belonging to assigned bids, purchase tokens belonging to assigned bids, repo tokens belonging to assigned offers, and collateral tokens and purchase tokens associated with tenders left on the table.

The proof exposes a **single public output**, defined as:

uint256 publicOutput = keccak256(abi.encodePacked(
    proverAddress, // type address
    collateralPrice,
    accBidHash,
    accOfferHash,
    auctionResultRoot
));

Where the `collateralPrice` is the current price of the collateral as determined by the corresponding onchain oracle.

:::info
The general outline of the auction proof could be designed to stop at step #4, such that the auction settlement is performed directly onchain. Such design would follow a similar implementation as was described above.

From a technical standpoint, opting for this design may not be the best choice: order placing and revealing would become more expensive instead of cheaper, and the development and auditing complexity would not be substantially reduced.
:::

### Settling the Auction

The auction is settled by verifying the above defined proof inside the smart contract. This proof verifies that the auction logic was executed correctly given all the bids/offers that were previously placed and revealed onchain. The results of the auction all get encoded inside the single value `auctionResultRoot`.

For a bidder/offeror to get their assigned/unlocked amounts they would first need to:
- Provide a valid Merkle proof that shows that their assigned/unlocked amounts are part of the commited [lean incremental Merkle tree](https://zkkit.pse.dev/classes/_zk_kit_lean_imt.LeanIMT.html) with root `auctionResultRoot`.
- Nullify the index of their leaf, which prevents double spending.

This process can be carried out by any given party and in batches, or the user can be tasked with claiming their result after the auction is settled.

### Liquidating/Repurchasing/Locking/Unlocking/Rolling Over Collateral

While the process of liquidating/repurchasing/locking/unlocking/rolling over collateral stays the same, users first need to fetch the amount of their collateral tokens from the tree if that action had not been done before.

As an example, let's consider the case when a borrower wants to add to their collateral balance. If their repurchase obligation has not been fetched from the [lean incremental Merkle tree](https://zkkit.pse.dev/classes/_zk_kit_lean_imt.LeanIMT.html) yet, they would have to call a function that looks something like:

function externalLockCollateral(
    MerkleProof merkleProof,
    address collateralToken,
    uint256 amount
) {
    // Verifies the Merkle proof
    merkleProof.verify();
    // Stores the repurchase obligation
    termRepoServicer.setBorrowerRepurchaseObligation(
        msg.sender,
        merkleProof.amount
    );
    
    // Maintains the same logic
    externalLockCollateral(collateralToken, amount);
}

While if their repurchase obligation was already fetched, they would call the already existing `externalLockCollateral` function: the core logic stays the same.

## Backwards Compatibility

As this proposal focuses on improving the auction process, Term Finance [evergreen contracts](https://developers.term.finance/term-finance-protocol/protocol-contracts) would stay unaffected. Similary, the logic behind [Term Repo Tokens](https://developers.term.finance/term-finance-protocol/term-repo/term-repo-token) is unaffected.

The changes described above are designed to be minimal, primarily targeting the [Term Auction contracts](https://developers.term.finance/term-finance-protocol/term-repo/term-auction-group), with very minor modifications to [Term Servicer contracts](https://developers.term.finance/term-finance-protocol/term-repo/term-servicer-group) to be able to fetch repurchase obligations if they were not made available already.

## Security Considerations

In theory, since verifying a zero-knowledge proof is an arbitrary computation, doing so onchain inherits the full security guarantees of Ethereum. In practice, using zero-knowledge proofs can increase the attack surface and introduce additional security considerations. **Soundness bugs** in a given implementation can allow an exploiter to convince a verifier (the Ethereum chain) to accept an otherwise fraudulent proof.

### Risk Mitigation Strategies

It is, however, possible to mitigate the risk introduced by the use of ZK proofs. Some possible ways are:
- Use of **permissioned provers**: we can restrict the ability to settle auctions to only a set of trusted parties. This is the same strategy used by most existing L2s, where only whitelisted addresses are allowed to update the rollup state.
- Using **independent implementations**: it is highly unlikely that two independent implementations, each based on different cryptographic primitives, would both share the same critical bug.
- Defining a **challenge window**: if an attacker was able to trick the verifier into accepting a proof that results in a fraudulent state, actors watching the chain could submit a different valid proof that would arrive at a different state to trigger a conflict. A **security council** could then come in to settle the dispute.

## Development Strategy

In order to speed up development time, while still minimizing security risks, the auction proof defined above can be directly implemented in Rust and proven via existing production-ready zkVMs like Succinct's [SP1](https://www.google.com/search?client=ubuntu-sn&channel=fs&q=sp1+succinct) or [Risc Zero](https://github.com/risc0/risc0). These zkVMs have undergone third party audits and are already being used to secure billions of dollars in value.

>This work is licensed under [CC BY-NC-ND 4.0](https://creativecommons.org/licenses/by-nc-nd/4.0/).