universe: switch to 128-bit limbs for multiverse leaves or switch to top-level counter sum

[Roasbeef]

Background

Today we use 64-bit sum values. Where relevant, we also ensure that we bail out if an overflow happens.

Related to this the multiverse and universe trees. The universe tree for issuance has a sum value that's the sum of all the issued assets for a base universe/asset. This can then be extended to also track all transfers for a given asset, with the sum value now being the total units of the assets that have been exchanged. If we then combine several of those trees into a single tree, we end up with a value that's the total amount of units moved over all assets. This is where we need to address over flow concerns.

One path here would be: for the multiverse and normal universe trees, we just tally a single integer which tracks the number of transition events. This works, but then for cases where you want to keep track of the total supply of a sparse set of assets, you lose the ability to track an aggregated sum. Maybe this is ok though, as we already have the asset group system for this use case.

Assuming we want to enable tracking that aggregate sum value (still an open question), then we can move to a 128-bit integer for the root sum.

A GPT-generated type for this looks something like:

package main

import (
	"errors"
	"fmt"
)

// Limb represents a single 64-bit portion of our 128-bit number
type Limb uint64

// U128 represents a 128-bit unsigned integer
type U128 struct {
	High Limb
	Low  Limb
}

// Add performs 128-bit addition with overflow detection
func (u *U128) Add(other U128) (U128, error) {
	sumLow := u.Low + other.Low
	sumHigh := u.High + other.High

	// Detect overflow in low limb
	if sumLow < u.Low {
		sumHigh++ // Carry
	}

	// Detect overflow in high limb
	if sumHigh < u.High {
		return U128{}, errors.New("overflow detected in 128-bit addition")
	}

	return U128{High: sumHigh, Low: sumLow}, nil
}

// Mul performs 128-bit multiplication with overflow detection
// It uses "grade school" multiplication with 64-bit limbs
func (u *U128) Mul(other U128) (U128, error) {
	lowBits := (u.Low * other.Low)
	midBits1 := (u.Low * other.High)
	midBits2 := (u.High * other.Low)
	highBits := (u.High * other.High)

	// Overflow detection
	if midBits1 > (1<<64-1)-lowBits || midBits2 > (1<<64-1)-lowBits || highBits > 0 {
		return U128{}, errors.New("overflow detected in 128-bit multiplication")
	}

	resultLow := lowBits + (midBits1 << 32) + (midBits2 << 32)
	resultHigh := highBits + (midBits1 >> 32) + (midBits2 >> 32)

	return U128{High: resultHigh, Low: resultLow}, nil
}

func ToU128Uint(value uint64) (U128, error) {
	if value > 0xFFFFFFFFFFFFFFFF {
		return U128{}, errors.New("overflow: value is greater than 64 bits")
	}
	return U128{High: 0, Low: Limb(value)}, nil
}

Steps To Completion

• Decide on if we actually need to modify the normal Universe and Multiverse sum values.
• If so, swap the existing 64 bit sum value for this 128 bit sum value. Type parameters will likely be useful here, as then we can retain the same tree, and bind the type at compile time.

[Roasbeef]

Going with a mutli-pronged stop gap approach instead.

[Roasbeef]

Re-opening as wasn't meant to be closed.

[Roasbeef]

Relevant to #1059

Unless we decide to go in the big int direction there. Would need to add Div to this.