How to Save 70% Gas Fee on Aptos PancakeSwap with Only ~40 Lines of Code?

Overview

  1. Aptos standard library & Aptos framework
  2. pancake’s implementation of Math lib and U256 lib

Expensive Code Identification

Optimization Step1

  • b_x and P are both of type u64, thus their product can always be represented by a u128
  • a_ {x,in} is a u64. Multiplying it with 25 results in a product within the limit of u128
  • Ignoring the underflow, the difference between two u128 can be represented by a u128.
let prec = (PRECISION as u128);
let balance_x_adjusted = (balance_x as u128) * prec - (amount_x_in as u128) * 25u128;
let balance_y_adjusted = (balance_y as u128) * prec - (amount_y_in as u128) * 25u128;
let reserve_x_adjusted = (reserves.reserve_x as u128) * prec;
let reserve_y_adjusted = (reserves.reserve_y as u128) * prec;
let p = u256::mul(u256::from_u128(balance_x_adjusted), u256::from_u128(balance_y_adjusted));
let k = u256::mul(u256::from_u128(reserve_x_adjusted), u256::from_u128(reserve_y_adjusted));
let compare = u256::compare(&u256::mul(balance_x_adjusted, balance_y_adjusted), &k);
assert!(compare == u256::get_greater_than() || compare == u256::get_equal(), ERROR_K);

Optimization Step2

471  <-- 471 interpreted as 4*100 + 7*10 + 1
* 32 <-- 32 interpreted as 3*10 + 2
-------
2 <-- 1*2, 0 left shift
14 <-- 7*2, 1 left shift
8 <-- 4*2, 2 left shift
3 <-- 1*3, 1 left shift
21 <-- 7*3, 2 left shift
+ 12 <-- 4*3, 3 left shift
-------
15072
        a1 a0  <--- a = (a1<<64) + a0
* b1 b0 <--- b = (b1<<64) + b0
-------------
w1 w0 <--- [Step 1] a0*b0, 0 left shift
x1 x0 <--- [Step 2] a1*b0, 1 left shift
y1 y0 <--- [Step 3] a0*b1, 1 left shift
+ z1 z0 <--- [Step 4] a1*b1, 2 left shift
-------------
v3 v2 v1 v0 <--- interpreted as (v3<<192) + (v2<<128) + (v1<<64) + v0

Step 0. Digits extraction

let a1 = (a >> 64);
let a0 = (a & U64_MAX);

let b1 = (b >> 64);
let b0 = (b & U64_MAX);

Step 1: a0 and b0

let p = a0 * b0;
let v1 = (p >> 64);
let v0 = (p & U64_MAX);

Step 2: a1 and b0

let p = a1 * b0;
v1 = v1 + (p & U64_MAX) ;
let v2 = (p >> 64);
if (v1 > U64_MAX) {
v2 = v2 + (v1 >> 64);
v1 = (v1 & U64_MAX);
};

Step 3: a0 and b1

let p = a0 * b1;
v1 = v1 + (p & U64_MAX);
if (v1 > U64_MAX) {
v2 = v2 + (v1 >> 64);
v1 = (v1 & U64_MAX);
};
v2 = v2 + (p >> 64);
let v3 = (v2 >> 64);
if (v2 > U64_MAX) {
v2 = (v2 & U64_MAX);
};

Step 4: a1 and b1

let p = a1 * b1;
v2 = v2 + (p & U64_MAX);
if (v2 > U64_MAX) {
v3 = v3 + (v2 >> 64);
v2 = (v2 & U64_MAX);
};
v3 = v3 + (p >> 64);

Final Touch

U256 { 
v0: (v0 as u64),
v1: (v1 as u64),
v2: (v2 as u64),
v3: (v3 as u64),
}
#[test]
fun test_mul_u128() {
let a = U128_MAX - 3;
let b = U128_MAX - 9;
    let p1 = mul_u128(a, b);
let p2 = mul(from_u128(a), from_u128(b));
assert!(p1 == p2, 0);
}
spec pancake::u256 {
spec module { pragma verify = false; }
spec fun value_of_U256(a: U256): num {
a.v0 +
a.v1 * P64 +
a.v2 * P64 * P64 +
a.v3 * P64 * P64 * P64
}
spec mul_u128 {
pragma verify = true;
pragma timeout = 3600;
ensures value_of_U256(result) == a * b;
}
}

Complete Code

public fun mul_u128(a: u128, b: u128): U256 {
let a1 = (a >> 64);
let a0 = (a & U64_MAX);
let b1 = (b >> 64);
let b0 = (b & U64_MAX);
// Step 1, v0 v1 created
let p = a0 * b0;
let v1 = (p >> 64);
let v0 = (p & U64_MAX);
// Step 2: v2 created, v1 modified
let p = a1 * b0;
v1 = v1 + (p & U64_MAX) ;
let v2 = (p >> 64);
if (v1 > U64_MAX) {
v2 = v2 + (v1 >> 64);
v1 = (v1 & U64_MAX);
};
// Step 3: v3 created, v2 v1 modified
let p = a0 * b1;
v1 = v1 + (p & U64_MAX);
if (v1 > U64_MAX) {
v2 = v2 + (v1 >> 64);
v1 = (v1 & U64_MAX);
};
v2 = v2 + (p >> 64);
let v3 = (v2 >> 64);
if (v2 > U64_MAX) {
v2 = (v2 & U64_MAX);
};
// Step 4: v3 v2 modified
let p = a1 * b1;
v2 = v2 + (p & U64_MAX);
if (v2 > U64_MAX) {
v3 = v3 + (v2 >> 64);
v2 = (v2 & U64_MAX);
};
v3 = v3 + (p >> 64);
// Result
U256 { v0: (v0 as u64), v1: (v1 as u64), v2: (v2 as u64), v3: (v3 as u64) }
}
/// Greater or equal to
public fun ge(a: &U256, b: &U256): bool {
if (a.v3 != b.v3) { return a.v3 >= b.v3 };
if (a.v2 != b.v2) { return a.v2 >= b.v2 };
if (a.v1 != b.v1) { return a.v1 >= b.v1 };
(a.v0 >= b.v0)
}
let prec = (PRECISION as u128);
let balance_x_adjusted = (balance_x as u128) * prec - (amount_x_in as u128) * 25u128;
let balance_y_adjusted = (balance_y as u128) * prec - (amount_y_in as u128) * 25u128;
let reserve_x_adjusted = (reserves.reserve_x as u128) * prec;
let reserve_y_adjusted = (reserves.reserve_y as u128) * prec;
let p = u256::mul_u128(balance_x_adjusted, balance_y_adjusted);
let k = u256::mul_u128(reserve_x_adjusted, reserve_y_adjusted);
assert!(u256::ge(&p, &k), ERROR_K);

Conclusion

--

--

Pioneers in Move Security

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store