inclusion, all: RoundDownPowerOfTwo and RoundUpPowerOfTwo are very inefficient and can cause running out of RAM due to an integer overflow

[odeke-em]

Summary of Bug

While on a 3AM audit and vulnerability hunt, I noticed that Round*PowerOfTwo are heavily used within celestia's ecosytem by use of BlobMinSquareSize and SubTreeWidth.

If we examine the code for RoundUpPowerOfTwo, we can see this pattern

go-square/inclusion/blob_share_commitment_rules.go

Lines 52 to 59 in 8e9b275

	func RoundUpPowerOfTwo[I constraints.Integer](input I) I {
	var result I = 1
	for result < input {
	result <<= 1
	}
	return result
	}

which when read basically creates a value then per step of exponentiating 2 by 2 multiple times eventually will bump into a value less than the input, trying to get to that power of 2 in steps shall take a max of 64 loop iterations but sadly in that code there is an integer overflow when you pass in a signed integer int* due to this check

        var result I = 1 
 	for result < input { 
 		result <<= 1 
 	} 

so when you have for example input=1<<64 - 1; that code starts with result=1 and in each step result is bit shifted to the left which is exponentiation for 2; but when we hit 1<<63; that value is still less than 1<<63 and in the next loop becomes 1<<64 and oops, maInt = 1<<64 - 1 hence that value overflows and becomes negative :-( -9223372036854775808 so that loop then continues and now the negative value when multiplied by 2 again warps around back to 0 but hey 0 << 1 == 0 and that loop iterates until you run out of RAM or your system kills it

Remedy

We can make that code so much more efficient and not suspectible to any integer overflows using knowledge from bit shifting and fiddling by noticing a key component:

• a power of 2 has a single bit set in it e.g. 01000000 or 0000010 and if you subtracted by 1 any value with a bit mask of >= 0b10, the prior bit will be then 0b01 and fill the lower bits with 1 so for example 0b10000 - 0b01 = 0b01111 and from bit fiddling 0&1=0, 1&1=1 so the fast check for if a value is a power of 2 is simply if input&(input-1) == 0
• to find the next power of 2 for a non-power of 2, we just find the bit length and then left 1 by it so for example 6 = 0b110 which has 3 bits and 1<<3 = 0b1000 = 8 and for example 3 = 0b11 which has 2 bits and 1<<2 = 0b100 = 4 and that's why the logic works
• bits.Len64 uses a very efficient algorithm deBruijn with instrinsics, which I've attacked with no avail for these years and is well published of an algorithm for bit fiddlers and used in the Go standard library

func RoundUpPowerOfTwo[I constraints.Integer](input I) I {
        if input <= 1 {
                return 1
        }
        if input&(input-1) == 0 {
                return input
        }
        return 1 << bits.Len64(uint64(input))
}

// RoundDownPowerOfTwo returns the next power of two less than or equal to input.
func RoundDownPowerOfTwo[I constraints.Integer](input I) (I, error) {
        if input <= 0 {
                return 0, fmt.Errorf("input %v must be positive", input)
        }
        if input&(input-1) == 0 {
                return input, nil
        }
        return 1 << (bits.Len64(uint64(input)) - 1), nil
}

which run in basically constant time and not susceptible to integer overflows and will always run in deterministic time and should actually have a positive impact on Celestia given that the callers for those functions are hot and the crux of Celestia

Kindly cc-ing @Wondertan @walldiss @liamsi @veorq

Version

8e9b275

Steps to Reproduce

Run this code

	RoundUpPowerOfTwo(math.MaxInt)

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned