feat: binary operations for frontend.Variable

[zliucd]

It would be very useful to provide more arithmetic operations for frontend.Variable, including:

• left and right shift
• rotate left and right shift

The arithmetic operations can be user-friendly APIs to use. Example code:

var X frontend.Variable
r0 := api.Lsh(X, 3)        // left shift
r1 := api.Rsh(X, 3)        // right shift
r2: = api.Lor(X, 3)       // left rotate shift
r3: = api.Ror(X, 3).     // right rotate shift

gnark/std/math/bits provide compatible types(e.g., U8), but direct APIs for Variable are more convenient.

I have implemented a demo:

/**
* Left shift input by `shift` bits  
* 
* Input:
*   - api:  gnark api
*   - X: input
*   - shift: number of bits to shift
* 
* Output: shifted result
*/
func Lsh(api frontend.API, X frontend.Variable, shift uint) frontend.Variable {

	var output frontend.Variable

	// bits: [LSB, MSB]
	bits := api.ToBinary(X)
	N := len(bits)

	// [zeroes, len: shift] + [bits, len: N - shift]
	bits_final := make([]frontend.Variable, len(bits))
	for i := 0; i < len(bits_final); i++ {
		bits_final[i] = 0
	}

	for i := shift; i < uint(N) - shift; i++ {
		bits_final[i] = bits[i - shift]
	}

	output = api.FromBinary(bits_final...)

	return output
} 

[ivokub]

Good idea. We have for now postponed implementing such methods as in general the arithmetic in circuits are done on field elements and doing bit operations is quite expensive (as we need to decompose the field elements to bits etc.). But I do see that this kind of functionality is needed anyway, so it would be good to have idiomatic way. But if we implement it, then I think it makes more sense to have them as gadgets (e.g. in std/ package) instead of extending frontend.API.

[zliucd]

Thanks for the feedback especially shedding light on "bit operations is quite expensive". Another thought is the granuality of bitwise operations, which may potentially generate unexpected result.

Example:
a is a fixed 8-bit value , left shift by 4 bits should result in ( 0xc5 << 4 ) & 0xff = 0x50. Following code shows the unexpected result, as Variable has no semantics of bit level granularity.

var a, b frontend.Variable
a = 0xc5
b = Lsh(a, 4)     //   b = 0xc5 << 4 = 0x0c50 (16bit integer)

We can again use another gadget to perform AND to get correct result, e.g., result := and(b, 0xff). It would be nice to provide an option bits in binary gadgets for convenient use:

• 0: no limit (original shifted result)
• 8: lower 8 bits
• 16: lower 16 bits
  ...

[ivokub]

See the https://pkg.go.dev/github.com/consensys/[email protected]/std/math/uints package which wraps the frontend.Variable type to allow byte operations