writeBits design is extremely inefficient for practical use

[colll78]

Describe the feature you'd like

Currently the signature of writeBits is:

-- | Given a 'BuiltinByteString', a list of indexes to change, and a list of values to change those
-- indexes to, set the /bit/ at each of the specified index as follows:
--
-- * If the corresponding entry in the list of values is 'True', set that bit;
-- * Otherwise, clear that bit.
writeBits ::
  BuiltinByteString ->
  BuiltinList BuiltinInteger ->
  BuiltinList BuiltinBool ->
  BuiltinByteString

Instead it should be:

-- | Given a 'BuiltinByteString', a list of indexes to change, and a boolean set/clear flag, set the /bit/ at each of the specified indices
-- if the boolean is true or clear the /bit/ at each of the specified indices if the boolean is false.
writeBits ::
  BuiltinByteString ->
  BuiltinList BuiltinInteger ->
  BuiltinBool ->
  BuiltinByteString

The issue with the current implementation is that any non-trivial use requires a huge amount of wasted work in constructing the BuiltinList BuiltinBool argument. If the caller wants to set and unset bits, they can simply call writeBits twice once with the indices they want to set and the flag set to true, and the second time with the indices they want to clear and the flag set to false.

Consider the current practical use-case:

-- | Return true iff the first 256 integers in the list are all unique.
isUniqueSet :: BuiltinList BuiltinInteger -> Bool
isUniqueSet xs = 
  let byteArray = replicateByte 32 0
       numEles = builtinListLength xs
       flagUniqueBytes = writeBits byteArray xs (replicateBuiltinTrue numEles)
   in (countSetBits flagUniqueBytes) == numEles
 
 replicateBuiltinTrue :: Integer -> BuiltinList BuiltinBool
 replicateBuiltinTrue n = go
   where 
     go n = 
       if (n == 0) 
       then BI.mkNilData BI.unitval
       else BI.mkCons (toOpaque True) $ go (n - 1)
 
 builtinListLength :: BuiltinList a -> Integer
 builtinListLength xs = go 0 xs 
   where 
     go acc l = matchList l (\_ -> acc) (\_ ys -> go (acc + 1) ys) 

Notice replicateBuiltinTrue blows up the script budget? Each recursive call invokes 4 builtin functions, a builtin ifThenElse, a builtin equalsInteger, a builtin subtractInteger, and a builtin mkCons.

Here is what the implementation would look like with the suggested interface for writeBits, notice that repliaceBuiltinTrue is not required. There is an absolutely massive difference in efficiency.

-- | Return true iff the first 256 integers in the list are all unique.
isUniqueSet :: BuiltinList BuiltinInteger -> Bool
isUniqueSet xs = 
  let byteArray = replicateByte 32 0
       flagUniqueBytes = writeBits byteArray xs (toOpaque True)
   in (countSetBits flagUniqueBytes) == builtinListLength xs
 
 builtinListLength :: BuiltinList a -> Integer
 builtinListLength xs = go 0 xs 
   where 
     go acc l = matchList l (\_ -> acc) (\_ ys -> go (acc + 1) ys) 

Describe alternatives you've considered

No response

[colll78]

The important thing to note is that even in the non-sensical case where the BuiltinList BuiltinBool list is provided already and does not need to be constructed / checked onchain, then this suggested change would only introduce 1 additional builtin call, ie. instead of calling writeBits once, we have to call it twice, once for the bits we want to set and once for the bits we want to clear. I'd imagine even in this scenario with the additional call it might still even be cheaper because the cost of writeBits would decrease as it no longer needs to fmap on the boolean flag list. But even if it isn't cheaper, the additional cost is completely negligible, where-as in any other scenario (where you either need to construct the BuiltinBool list onchain, or traverse it and apply validation to its contents) the cost is reduced by at-least n (where n is min length of both lists) builtin calls (required to construct the list) and often more (4 * n builtins each recursive call + lots of function applications to recurse) ie in the above example.

[effectfully]

This is great reasoning and I fully agree with it.

We can't change that much the signature of a builtin once it was released in a hard fork, but we can when the builtin isn't used by anything on the chain yet. Or we can introduce a new builtin.

@kwxm writeBits isn't used on the chain yet, right? Should we change before it's too late?

[colll78]

This is great reasoning and I fully agree with it.

We can't change that much the signature of a builtin once it was released in a hard fork, but we can when the builtin isn't used by anything on the chain yet. Or we can introduce a new builtin.

@kwxm writeBits isn't used on the chain yet, right? Should we change before it's too late?

For what it's worth I am strongly in favor of changing it now given that it has not been used onchain yet. This means we have a limited opportunity window to correct this now without needing to permanently introduce a new builtin or replace the old one (and thus break backwards compatibility between V1-3 scripts and >=V4 scripts). I will get confirmation from all the ecosystem dApps that they are either not currently working on a PlutusV3 upgrade, or if they are that it isn't using this builtin. I'll post the feedback here.

[zliu41]

It can't possibly have been used on the chain, since it won't be enabled until Chang+1.

If this problem is a serious concern, we should postpone enabling this particular builtin until Chang+2, since delaying Chang+1 is unlikely going to be an acceptable option.

[effectfully]

If this problem is a serious concern, we should postpone enabling this particular builtin until Chang+2

I'd vote for that.

[colll78]

That makes sense to me, sounds good!

[zliu41]

@kozross @kwxm what's your opinion?

[kozross]

@zliu41 - I find the reasoning persuasive, and the current implementation wasn't anyone's intent, but was forced by circumstances. Originally, it was meant to be a list of pairs of index-value, but that turned out to not be workable.

If we want to change writeBits, I support @colll78's proposed signature. This also nicely avoids some weirdness with the current implementation (such as 'what happens when the two lists don't match in length').

[kwxm]

I think this is a good idea and we should do it. It'll simplify the implementation and the specification signficantly as well.

[effectfully]

Originally, it was meant to be a list of pairs of index-value, but that turned out to not be workable.

It would probably be better w.r.t. what's discussed in this issue for some use cases, but

1. not for the one provided as an example, as instead of creating a new list you'd have to annotate elements of an existing one, which is no better
2. it's still a linear amount of additional builtin calls

Making writeBits receive a single Bool and calling the builtin twice is just a better approach overall.