Additional validation

We recommend to check the assumptions made in some functions for best practice. We collect such cases in this section.

Length of argument to Hash2FV

In the zk-bridge file circuits/fabric/headers/headerutil/utils.go, the function Hash2FV is implemented as follows:

func Hash2FV(h []byte) [2]frontend.Variable {
	return [2]frontend.Variable{
		new(big.Int).SetBytes(h[:16]),
		new(big.Int).SetBytes(h[16:]),
	}
}

This function is used to split up 32 bytes into two circuit variables. However, this function does not check that the input is actually 32 bytes long. Should the input be less than 16 bytes long, the code will panic due to an out-of-bounds access. In other cases, in which callers provide an input of length unequal to 32, behavior may be different than intended but not result in an error being returned or a runtime panic. We recommend to verify the length of h before use.

Size and range checks for decompose-related functions

The function decompose, which is implemented as displayed below, can lead to unintended behavior when bitSize is larger than the minimum of 64 and the number of bits that can be stored in type T.

func decompose[T uint | byte](data *big.Int, bitSize uint, length uint) []T {
	res := decomposeBig(data, bitSize, length)
	ret := make([]T, length)
	for i, limb := range res {
		ret[i] = T(limb.Uint64())
	}
	return ret
}

We recommend to document that this function should be used carefully regarding T's bit size, or add an assertion checking if bitSize is a valid size.

Also, the function decomposeBitsExact extracts the limbs of the absolute value of the input, which cannot be inferred from the function's name itself. We suggest changing the function's name to more detailed one like decomposeBitsExactOfAbs, or specifically document this behavior of the function.

Padded length-size check for function padBitsRight

The following is the implementation of the function padBitsRight in the sdk repository's sdk/utils.go.

func padBitsRight(bits []uint, n int, with uint) []uint {
	ret := make([]uint, n)
	for i := 0; i < len(bits); i++ {
		ret[i] = bits[i]
	}
	for i := len(bits); i < n; i++ {
		ret[i] = with
	}
	return ret
}

If len(bits) > n, so that the function should pad bits to length n, but bits is already longer than that, then the function will panic due to an out-of-bounds write. It may be neater to check if len(bits) > n and panic with a more descriptive error message, though that extra check will of course make the function slightly slower, so it is a trade-off.

Function FromBinary number or arguments

The following is the implementation of the FromBinary function for the sdk's Bytes32 type, from sdk/api_bytes32.go:

// FromBinary interprets the input vs as a list of little-endian binary digits
// and recomposes it to a Bytes32. Input size can be less than 256 bits, the
// input is padded on the MSB end with 0s.
func (api *Bytes32API) FromBinary(vs ...Uint248) Bytes32 {
	var list List[Uint248] = vs
	values := list.Values()
	for i := len(vs); i < 256; i++ {
		values = append(values, 0)
	}
	res := Bytes32{}
	res.Val[0] = api.g.FromBinary(values[:numBitsPerVar]...)
	res.Val[1] = api.g.FromBinary(values[numBitsPerVar:]...)
	return res
}

The arguments vs should be at most 256 many; however, there are no checks being done to ensure this, so passing more than 256 bits will just pass that through and can make res.Val[1] more bits wide than intended. Then, if ToBinary is called on this Bytes32 object, the constraints will not be satisfiable due to Val[1] not being eight bits wide only. We suggest making FromBinary already panic with a descriptive error message whenever len(vs) > 256. This will aid in debugging for users.

The same situation is present for the other types' FromBinary function.

Check for number of bits for Uint521 function ToBinary

The sdk's Uint521 type has a ToBinary function that is implemented as follows in sdk/api_uint521.go:

// ToBinary decomposes the input v to a list (size n) of little-endian binary digits
func (api *Uint521API) ToBinary(v Uint521, n int) List[Uint248] {
	reduced := api.f.Reduce(v.Element)
	bits := api.f.ToBits(reduced)
	ret := make([]Uint248, n)
	for i := 0; i < n; i++ {
		ret[i] = newU248(bits[i])
	}
	return ret
}

Should n > len(bits), a panic will occur due to out-of-bounds access in the loop. We recommend to instead explicitly check for n > len(bits) or n > 521 and panic with a descriptive error message in that case.

Additional length check regarding conversion between bits and bytes

Function bits2Bytes in the sdk repository's sdk/host_circuit.go and function addOutput in sdk/circuit_api.go are implemented as the following:

func (api *CircuitAPI) addOutput(bits []variable) {
	// the decomposed v bits are little-endian bits. The way evm uses Keccak expects
	// the input to be big-endian bytes, but the bits in each byte are little endian
	b := flipByGroups(bits, 8)
	api.output = append(api.output, b...)
	dryRunOutput = append(dryRunOutput, bits2Bytes(b)...)
}

func bits2Bytes(data []frontend.Variable) []byte {
	var bits []uint
	for _, b := range data {
		bits = append(bits, uint(fromInterface(b).Int64()))
	}

	bytes := make([]byte, len(bits)/8)
	for i := 0; i < len(bits)/8; i++ {
		for j := 0; j < 8; j++ {
			bytes[i] += byte(bits[i*8+j] << j)
		}
	}

	return bytes
}

Both functions relate to converting bits into bytes and are implemented in a way that will lead to incorrect results should the input length not be divisible by 8. We thus recommend to check this and panic otherwise.

Length of FlipByGroups being a multiple of groupSize

The function FlipByGroups in the zk-hash repository's utils/binary.go is implemented as following.

// FlipByGroups flips the order of the groups of groupSize. e.g. [1,2,3,4,5,6] with groupSize 2 is flipped to [5,6,3,4,1,2]
func FlipByGroups[T any](in []T, groupSize int) []T {
	res := make([]T, len(in))
	copy(res, in)
	for i := 0; i < len(res)/groupSize/2; i++ {
		for j := 0; j < groupSize; j++ {
			a := i*groupSize + j
			b := len(res) - (i+1)*groupSize + j
			res[a], res[b] = res[b], res[a]
		}
	}
	return res
}

The length of in should be a multiple of groupSize for this implementation to work properly; otherwise, the result would be unexpected. However, the current implementation does not check the length, and the following unexpected behavior is possible.

in: [1,2,3,4,5,6,7], groupSize: 2
res: [6,7,3,4,5,1,2]

We suggest adding a check for len(in) % groupSize == 0.

The sdk function OutputUint does not check maximum bit size

The following is the documentation and implementation for the function OutputUint in sdk/circuit_api.go of the sdk repository:

// OutputUint adds an output of solidity uint_bitSize type where N is in range [8, 248]
// with a step size 8. e.g. uint8, uint16, ..., uint248.
// Panics if a bitSize of non-multiple of 8 is used.
// Panics if the bitSize exceeds 248. For outputting uint256, use OutputBytes32 instead
func (api *CircuitAPI) OutputUint(bitSize int, v Uint248) {
	if bitSize%8 != 0 {
		panic("bitSize must be multiple of 8")
	}
	b := api.g.ToBinary(v.Val, bitSize)
	api.addOutput(b)
	_, ok := v.Val.(*big.Int)
	dbgPrint(ok, "added uint%d output: %d\n", bitSize, v.Val)
}

It is said that the function panics if bitSize is not a multiple of 8 or exceeds 248. This is a good sanity check to prevent incorrect usage. However, the implementation does not actually panic when bitSize exceeds 248. We recommend to add that check.

Negative offsets in offsetSlot

The offsetSlot function in the sdk's sdk/circuit_api.go is passed a slot and an offset, and it is roughly intended to return their sum. The function's implementation begins as follows:

func (api *CircuitAPI) offsetSlot(slotBits [256]variable, offset int) [256]variable {
	if offset <= 0 {
		return slotBits
	}

For offset = 0, the function returns slotBits, as is reasonable. However, for negative values of offset, the function also returns slotBits. If a negative offset should be supported, then it would make more sense to return the sum, as for the positive offsets. If negative offsets are not intended to be supported, then the function should reject them by panicking with a descriptive error message instead.

Number of values in Reduce

In the sdk repository's sdk/datastream.go, the function Reduce is implemented as follows:

func Reduce[T, R CircuitVariable](ds *DataStream[T], initial R, reducer ReduceFunc[T, R]) R {
	acc := initial
	for i, data := range ds.underlying {
		newAcc := reducer(acc, data)
		oldAccVals := acc.Values()
		values := make([]frontend.Variable, len(oldAccVals))
		for j, newAccV := range newAcc.Values() {
			values[j] = ds.api.g.Select(ds.toggles[i], newAccV, oldAccVals[j])
		}
		acc = acc.FromValues(values...).(R)
	}
	return acc
}

Note that, should newAcc.Values() be of a different length than acc.Values() in the loop body, then the function would not behave as intended. If the length is smaller, then values will be padded with default values at the end, which may cause the new acc to be incorrect. If the length is bigger, then the inner loop will attempt to make an assignment out of bounds, causing a panic.

The Reduce function should not be called with arguments for which such inconsistent lengths are possible, so this could be considered a user error. However, to prevent incorrect use and make debugging easier, we recommend to check that oldAccVals and newAcc.Values() have the same number of elements and, if they do not, the function should panic.

Checking for pinned data at too-high index

The BuildCircuitInput function in the sdk's sdk/app.go is used to, in particular, convert from rawData (for receipt, storage, and transaction data) to CircuitInput. See the descriptions in Findings ref↗ and ref↗ for a short overview of rawData. As the three types of data are handled completely analogously, we will in the following only mention receipts, but everything applies also to storage and transaction data.

To check that the rawData is compatible with the maximum sizes allocated for the CircuitInput, the function checkAllocations is used. For receipts, it carries out the following checks:

numReceipts := len(q.receipts.special) + len(q.receipts.ordered)
if maxReceipts%32 != 0 {
	return allocationMultipleErr("receipt", maxReceipts)
}
if numReceipts > maxReceipts {
	return allocationLenErr("receipt", numReceipts, maxReceipts)
}

// ..

total := maxReceipts + maxSlots + maxTxs
if total > NumMaxDataPoints {
	return allocationLenErr("total", total, NumMaxDataPoints)
}

The actual data to be assigned is only checked with the second of the two receipt-specific tests. What is checked is whether the number of pinned and unpinned data points is at most the maximum number of receipts. However, this does not ensure that all receipts will be assigned with indexes from 0 to maxReceipts - 1, as a receipt may have been pinned at a larger index. The remaining check total > NumMaxDataPoints only involves checking the total number of pinned or unpinned receipts, storage, and transaction data, which will also not catch a too-high pinned index.

After using checkAllocations, the BuildCircuitInput will call assignReceipts to actually assign the CircuitInput. Should a pinned index be too high, an out-of-bounds assignment will cause a panic in that function.

So the mistake of pinning at a too-large index will be caught. However, it would be easier to debug if this were checked in checkAllocations, by calculating the maximum key of q.receipts.special and returning an error with a descriptive error message if that value is bigger than or equal to maxReceipts — similarly for storage and transactions.

Possible out-of-bounds access in dotProduct

In the zk-hash repository, in mux/multiplexer.go, the dotProduct function would crash if called with a too-large value for width, due to out-of-bounds access. We recommend to check whether width > len(inputA) and panic with a descriptive error message if that holds.

Additional asserts for Pad101Bits

In the zk-hash implementation of the pad10*1 padding for Keccak in keccak/pad.go, the Pad101Bits function assumes that inBits divides 8. We recommend to check this and panic with a descriptive error message if it is not satisfied, to help avoid incorrect usage.

Additionally, we recommend to panic with an error message if inLenMin > inLenMax.

Checking for consistent column lengths in transpose

The zk-hash implementation of Keccak contains in keccak/keccak256.go an implementation of transposition (so switching of rows and columns):

func transpose(input [][]frontend.Variable) [][]frontend.Variable {
	rows := len(input)
	cols := len(input[0])
	output := make([][]frontend.Variable, cols)

	for i := 0; i < cols; i++ {
		output[i] = make([]frontend.Variable, rows)
		for j := 0; j < rows; j++ {
			output[i][j] = input[j][i]
		}
	}
	return output
}

Note that the number of columns is obtained from the length of the first row, input[0]. Because of this, should there be a j with len(input[j]) > len(input[0]), the extra components would not be copied to the output. If len(input[j]) < len(input[0]), then a panic due to an access out of bounds would happen when attempting to access nput[j][i] in the inner loop.

This is fine with regards to the intended functionality, as this function should only be called with rectangle-shaped inputs. However, we recommend to check that this is the case to make it easier to debug incorrect usage, by panicking if len(input[i]) != cols for any 1 <= i < rows.

Size check for Uint64s2Blocks

In keccak/periphery.go in the zk-hash repository, it might make sense in the Uint64s2Blocks function to check and panic with an error message if len(padded) > 17*MAX_ROUNDS. Currently, this would cause an out-of-bounds array access.