Intrinsic::toRadix handles constant and non-constant inputs differently

[TomAFrench]

Aim

I'm wanting to get consistent behaviour between a to_be_bytes call made with constant inputs or with unknown inputs.

Expected Behavior

The results of x.to_be_bytes(31) should return the same value whether x is known at compile time or not.

Bug

If the to_be_radix call gets an constant input and is simplified then we add extra padding terms.

noir/crates/noirc_evaluator/src/ssa/ir/instruction/call.rs

Lines 315 to 347 in 168e0db

	fn constant_to_radix(
	endian: Endian,
	field: FieldElement,
	radix: u32,
	limb_count: u32,
	dfg: &mut DataFlowGraph,
	) -> ValueId {
	let bit_size = u32::BITS - (radix - 1).leading_zeros();
	let radix_big = BigUint::from(radix);
	assert_eq!(BigUint::from(2u128).pow(bit_size), radix_big, "ICE: Radix must be a power of 2");
	let big_integer = BigUint::from_bytes_be(&field.to_be_bytes());
	// Decompose the integer into its radix digits in little endian form.
	let decomposed_integer = big_integer.to_radix_le(radix);
	let mut limbs = vecmap(0..limb_count, |i| match decomposed_integer.get(i as usize) {
	Some(digit) => FieldElement::from_be_bytes_reduce(&[*digit]),
	None => FieldElement::zero(),
	});
	if endian == Endian::Big {
	limbs.reverse();
	}
	// For legacy reasons (see #617) the to_radix interface supports 256 bits even though
	// FieldElement::max_num_bits() is only 254 bits. Any limbs beyond the specified count
	// become zero padding.
	let max_decomposable_bits: u32 = 256;
	let limb_count_with_padding = max_decomposable_bits / bit_size;
	while limbs.len() < limb_count_with_padding as usize {
	limbs.push(FieldElement::zero());
	}
	make_constant_array(dfg, limbs, Type::unsigned(bit_size))
	}

This padding does not exist however if we are performing this to_be_radix call at runtime.

noir/crates/noirc_evaluator/src/ssa/acir_gen/acir_ir/acir_variable.rs

Lines 809 to 860 in 168e0db

	pub(crate) fn radix_decompose(
	&mut self,
	endian: Endian,
	input_var: AcirVar,
	radix_var: AcirVar,
	limb_count_var: AcirVar,
	result_element_type: AcirType,
	) -> Result<Vec<AcirValue>, RuntimeError> {
	let radix = match self.vars[&radix_var].as_constant() {
	Some(radix) => radix.to_u128() as u32,
	None => {
	return Err(RuntimeError::InternalError(InternalError::NotAConstant {
	name: "radix".to_string(),
	call_stack: self.get_call_stack(),
	}));
	}
	};
	let limb_count = match self.vars[&limb_count_var].as_constant() {
	Some(limb_count) => limb_count.to_u128() as u32,
	None => {
	return Err(RuntimeError::InternalError(InternalError::NotAConstant {
	name: "limb_size".to_string(),
	call_stack: self.get_call_stack(),
	}));
	}
	};
	let input_expr = self.var_to_expression(input_var)?;
	let bit_size = u32::BITS - (radix - 1).leading_zeros();
	let limbs = self.acir_ir.radix_le_decompose(&input_expr, radix, limb_count, bit_size)?;
	let mut limb_vars = vecmap(limbs, |witness| {
	let witness = self.add_data(AcirVarData::Witness(witness));
	AcirValue::Var(witness, result_element_type.clone())
	});
	if endian == Endian::Big {
	limb_vars.reverse();
	}
	// `Intrinsic::ToRadix` returns slices which are represented
	// by tuples with the structure (length, slice contents)
	Ok(vec![
	AcirValue::Var(
	self.add_constant(FieldElement::from(limb_vars.len() as u128)),
	AcirType::field(),
	),
	AcirValue::Array(limb_vars.into()),
	])
	}

This is an inconsistency which mean two calls with otherwise identical inputs to have different results.

To Reproduce

Compile the program below

// x = 2040124
fn main(x : Field) {
    let byte_array = x.to_be_bytes(31);
    let x_as_constant = 2040124;
    let constant_byte_array = x_as_constant.to_be_bytes(31);
    assert(constant_byte_array.len() == byte_array.len());
    for i in 0..constant_byte_array.len() {
        assert(constant_byte_array[i] == byte_array[i]);
    }
}

The array length assertion will fail.

(I've been a bit roundabout with the equality checking as assert(constant_byte_array == byte_array) causes a panic)

Installation Method

Compiled from source

Nargo Version

nargo 0.10.3 (git version hash: 168e0db, is dirty: true)

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response