The lower-post-volume people behind the software in Debian. (List of feeds.)

Touchscreens are quite prevalent by now but one of the not-so-hidden secrets is that they're actually two devices: the monitor and the actual touch input device. Surprisingly, users want the touch input device to work on the underlying monitor which means your desktop environment needs to somehow figure out which of the monitors belongs to which touch input device. Often these two devices come from two different vendors, so mutter needs to use ... */me holds torch under face* .... HEURISTICS! :scary face:

Those heuristics are actually quite simple: same vendor/product ID? same dimensions? is one of the monitors a built-in one? [1] But unfortunately in some cases those heuristics don't produce the correct result. In particular external touchscreens seem to be getting more common again and plugging those into a (non-touch) laptop means you usually get that external screen mapped to the internal display.

Luckily mutter does have a configuration to it though it is not exposed in the GNOME Settings (yet). But you, my $age $jedirank, can access this via a commandline interface to at least work around the immediate issue. But first: we need to know the monitor details and you need to know about gsettings relocatable schemas.

Finding the right monitor information is relatively trivial: look at $HOME/.config/monitors.xml and get your monitor's vendor, product and serial from there. e.g. in my case this is:

  <monitors version="2">
   <configuration>
    <logicalmonitor>
      <x>0</x>
      <y>0</y>
      <scale>1</scale>
      <monitor>
        <monitorspec>
          <connector>DP-2</connector>
          <vendor>DEL</vendor>              <--- this one
          <product>DELL S2722QC</product>   <--- this one
          <serial>59PKLD3</serial>          <--- and this one
        </monitorspec>
        <mode>
          <width>3840</width>
          <height>2160</height>
          <rate>59.997</rate>
        </mode>
      </monitor>
    </logicalmonitor>
    <logicalmonitor>
      <x>928</x>
      <y>2160</y>
      <scale>1</scale>
      <primary>yes</primary>
      <monitor>
        <monitorspec>
          <connector>eDP-1</connector>
          <vendor>IVO</vendor>
          <product>0x057d</product>
          <serial>0x00000000</serial>
        </monitorspec>
        <mode>
          <width>1920</width>
          <height>1080</height>
          <rate>60.010</rate>
        </mode>
      </monitor>
    </logicalmonitor>
  </configuration>
</monitors>
  
Well, so we know the monitor details we want. Note there are two monitors listed here, in this case I want to map the touchscreen to the external Dell monitor. Let's move on to gsettings.

gsettings is of course the configuration storage wrapper GNOME uses (and the CLI tool with the same name). GSettings follow a specific schema, i.e. a description of a schema name and possible keys and values for each key. You can list all those, set them, look up the available values, etc.:


    $ gsettings list-recursively
    ... lots of output ...
    $ gsettings set org.gnome.desktop.peripherals.touchpad click-method 'areas'
    $ gsettings range org.gnome.desktop.peripherals.touchpad click-method
    enum
    'default'
    'none'
    'areas'
    'fingers'
  
Now, schemas work fine as-is as long as there is only one instance. Where the same schema is used for different devices (like touchscreens) we use a so-called "relocatable schema" and that requires also specifying a path - and this is where it gets tricky. I'm not aware of any functionality to get the specific path for a relocatable schema so often it's down to reading the source. In the case of touchscreens, the path includes the USB vendor and product ID (in lowercase), e.g. in my case the path is:
  /org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/
In your case you can get the touchscreen details from lsusb, libinput record, /proc/bus/input/devices, etc. Once you have it, gsettings takes a schema:path argument like this:
  $ gsettings list-recursively org.gnome.desktop.peripherals.touchscreen:/org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/
  org.gnome.desktop.peripherals.touchscreen output ['', '', '']
Looks like the touchscreen is bound to no monitor. Let's bind it with the data from above:
 
   $ gsettings set org.gnome.desktop.peripherals.touchscreen:/org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/ output "['DEL', 'DELL S2722QC', '59PKLD3']"
Note the quotes so your shell doesn't misinterpret things.

And that's it. Now I have my internal touchscreen mapped to my external monitor which makes no sense at all but shows that you can map a touchscreen to any screen if you want to.

[1] Probably the one that most commonly takes effect since it's the vast vast majority of devices

Posted Tue Mar 12 04:33:00 2024 Tags:

As a 3d printing hobbyist with opinions about the strength of different types of materials I’ve sometimes had discussions with people with Real Engineering Degrees who feel the need to mansplain to me trivia about the different types of strength and how I’m using the terms all wrong. It might sound weird that I’m being dismissive of people who have an actual degree and are using real scientific jargon, but this is a case of knowing a lot of trivia while missing the underlying point.

Within engineering there’s a range of measurement types between ‘fundamental physics’ and ‘empirical rules of thumb’, with weight on one extreme and coefficient of friction on the other. It isn’t that weight has no artifacts: Objects are affected by moving them close to other objects, and when in orbit the centrifugal effect changes it a lot, but it’s so close to the fundamental physics concept of mass that we’ve relied on it for making very prices scales since antiquity. Coefficient of friction on the other hand is a vague concept about ‘how well these two things mash into each other’, strongly affected by how long they’ve been meshed together, how much force has been pushed into them orthogonally, whether they’ve been moved already, the phase of the moon, and the purity of the soul of the person conducting the experiment. When building things which rely on coefficient of friction we run the numbers, add an order of magnitude to it, and then test the real thing to find out when it actually breaks.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Measures of hardness are much closer to coefficient of friction than mass. Take the Mohs scale, which is literally a metric of who beats who in a scratching contest. It’s more meaningful than IQ scores, but directly comparable to Chess ratings, which are at almost exactly the same point on the metric accuracy scale (but to their credit both are closer to real than the the metric accuracy scale itself).

For measuring strength there’s all manner of terms used, but they’re all different benchmarks based off what a particular measurement happens to say. The Shore measurement scale literally specifies the size and shape of objects to attempt to jam into the material and then measure penetration at different pressures. The different shapes have a fair amount of correlation but often deviate based on their size and spikyness. There’s no platonic ideal being measured here, it’s just an empirical value.

When you bend a ‘strong’ object it tends to snap back to where it was when you’re done but there are a lot of things which could happen during bending. Maybe it got little microfractures from the bending which build up at some schedule if you bend it repeatedly. Maybe it underwent some amount of plastic deformation. If it did maybe it lost some of its strength, or maybe it will stay a bit bent permanently. Maybe it undergoes plastic deformation slowly, and will snap back varying amounts based on how long you keep it bent, possibly on a schedule which doesn’t look very linear. The details are so varied and hard to measure that most of the measures of strength simply ignore the amount of material failure which happened during the test. This is an expedient but dubious approach. John Henry only technically defeated the steam engine. He died with a hammer in his hand. By any reasonable standard the steam engine won.

A material can be ‘stiff’, meaning it’s hard to bend in the first place, and it can be ‘tough’, meaning it doesn’t undergo much damage when it’s bent. PLA is still but not tough and tends to fail catastrophically. TPU is tough but not stiff. Nylon is both stiff and tough, but not as stiff as PLA or as tough as TPU. In general PLA+ is PLA with something added which makes it less stiff but more tough so it doesn’t undergo catastrophic failure. The downside is that it then undergoes material failure much sooner. This makes it do better on strength tests while making it a worse material for making real things out of. For some niche safety related applications it’s important that things fail visibly but not catastrophically, but for the vast majority of practical applications you don’t care how gracefully things fail, you care about them not failing in the first place. For that you need stiffness, and as boring of a result as it is PLA wins the stiffness competition against the other common and even not so common 3d printing materials. If your parts are failing you should design them more robustly not try to switch to some unobtanium printing material.

With that very disappointing result out of the way, the question is, what if you want to find some material which really is stronger than PLA? Having a 3d printer which could work with solder would be awesome, but there aren’t any of those on the market right now and I don’t know what it would take to make such a thing. Short of that the best material is… PLA. Even within PLA there are different levels of quality based on how long the chains are at the molecular level and how knotted up in each other they are, but as you may have gathered from the tirade about PLA+ about the PLA vendors are less than up front about the quality of their material and it isn’t possibly to simply buy higher quality PLA right now. Within what’s available now you can use PLA a bit better. If you print in a warm chamber and only slowly cool it down once printing is done you’ll get some annealing in and have a stronger final product which gets soft at a higher temperature. Ideally you’d repeatedly reheat the entire chamber to the temperature you’d properly anneal at and cool it back down again after every layer, which would result in an amazing quality product but take forever.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Sat Mar 9 21:29:27 2024 Tags:

There are two arguments about Bitcoin inscriptions: One is that it’s playing completely within the rules of Bitcoin and is fine. The other is that it’s massively increasing the costs of running full nodes and hence bad. Both are technically correct.

Rather than get moralizing and playing dumb cat and mouse games about letting them into blocks, which is what’s happening now, it would be far better for Bitcoin development to put together a soft fork to create a vbytes cost for UTXO creation. That should have been in there in the first place. The downside is that this reduces chain throughput even for people who have nothing to do with it. But they’ll get more space by having less inscription to compete with. And the vbytes cost necessary to keep UTXO size increase under control is small enough that there’s a sweep spot which doesn’t do much damage, nowhere near knocking down chain capacity to what it was pre-segwit.

If Bitcoin development were healthy the details of this would be getting hashed out in polite, highly technical, and frankly kind of boring discussions, but it isn’t. Back in 2015 such things got railroaded through so fast that even the core devs were alarmed at how much it smacked of centralized control, but now there’s the opposite problem, where even simple obvious fixes can’t get in.

Posted Fri Mar 8 20:22:56 2024 Tags:

At the start of the last pandemic I happened to have a huge bag of flour and a single packet of yeast and wound up living off homemade bread with a yeast culture I kept alive for a while. This is a pretty good plan for having a stockpile of food around for such an emergency, with dried rice, beans, and pasta being other good options, along with all manner of canned goods.

The good news from the experiences of the last pandemic is that although supply chains may be disrupted there will always be plenty of food. It may be necessary to drive around in tanks to crush the zombies on the road, but we’ll still have Door Dash via tank, because we aren’t savages.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Still, it’s fun to consider what one would do to survive if all one had was an apartment or possibly a suburban lawn to get food off of. For basic calories there’s a clear winner: potatoes. Potatoes are the uber crop, able to be grown trivially and producing mass amounts of calories. They aren’t terribly nutritious, but they’ll keep you alive for a long time.

If things go long enough you’ll need a source of protein. We humans can eat practically any animal, but most of them have issues which make their domestication problematic. There are some animals which can be raised trivially under just the right conditions, for example sometimes you can build an artificial berm in the ocean and simply pick up oysters from it as they grow naturally, but for the most part the standard animals raised for meat are well the best in terms of ease of raising and yield of meat. Chickens are a ridiculous outlier in terms of yield but aren’t terribly conducive to keeping indoors. Crickets are another huge outlier in productivity and in principle can be ranched indoors but the equipment for that isn’t terribly common.

For ease of raising them indoors with occasionally letting them outside to graze there’s a clear winner: guinea pigs. The biggest problem would be people being able to bring themselves to slaughter them. Rabbits are close behind with similar slaughtering issues. Other reasonably easy animals which are bigger include goats and pigs. You’d be basically raising a petting zoo for food, which is good for having cute animals around but bad for getting attached to them.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Mon Mar 4 19:40:47 2024 Tags:

Back when I was 12 years old I got obsessed with solving the Rubik’s Cube and eventually figured out a method for it. Normally these sorts of solutions are just sort of bad, but because I hadn’t figured out commutators as a concept there aren’t any inverse sequences done and everything is ‘forward’, resulting in a very unusual and hopefully interesting approach.

The ground rules I was playing with were that I didn’t want any external help whatsoever, which for some reason included using a pen and paper to make notes. I felt I’d been given a bit of a spoiler by being told about layer by layer. Because of this the method doesn’t so much give sequences of things to do but notes as to what to do in different situations which feed into each other nicely. Most of these were found by trial and error. Anyhow, here’s the instructions:

  1. Solve the bottom cross. This is done intuitively as in most solutions.

  2. Solve the bottom corners. Again this is done intuitively.

  3. Solve the middle edges. This is done with the sequence FU2F’U2L’U’L which puts the FU edge into FL and its mirror image F’U2FU2RUR’ which puts the FU edge into FR. To use them position an edge which needs to go in the middle so that its top sticker matches the front center sticker and then use the sequence starting with F if it needs to go in the FL position or F’ if it needs to go in the FR position. If none of the edges on the top go in the middle but there are still edges in the middle positioned wrong use one of those sequences to put one of the edges on the top into the position of one of the misplaced edges in the middle and proceed from there.

  4. Get the top edges positioned and oriented. The basic move for this is to use one of the sequences in step 3 to move an edge from the top layer to the middle layer then use the the other handed sequence to fix it. Starting this with an F’ is a ‘left break’ and starting it with an F is a ‘right break’. Each case is defined by a first move to do then you forget about what you just did and go back to the beginning of this step with a new observation of where everything is. These cases feed into each other in a way which is guaranteed to always eventually solve the top edges. The different cases are as follows:

    1. If none of the top edges are in the correct orientation do a left break.

    2. If all of the top edges are in the correct orientation rotate the top until either all four are in correct positions or exactly two are in correct positions. If all of them are positioned correctly you’re ready for the next step, otherwise

      1. If the two incorrectly positioned edges are opposite each other position the cube so that one of the correctly oriented but wrongly positioned edges is in the front and do a left break.

      2. Otherwise the two wrongly positioned edges will be next to each other. Position the cube as a whole such that one of them is in the front and the other is on the left and do a left break.

    3. If exactly two of the top edges are correctly oriented and they’re adjacent to each other then rotate the top as few units as possible so that at least one of the edges is in the correct position, (in the case of at least one of the correctly oriented top edges already being in the right position this means don’t rotate the top at all). Then position the cube such that the remaining incorrectly positioned edge is in the front. If there is no such edge orient the cube so that either of the correctly oriented edges is in the front. Then do a break in the directly of the other correctly oriented edge.

    4. If exactly two of the top edges are correctly oriented and they’re opposite each other then if neither of those edges is correctly oriented do a U2 to get at least one of them correctly positioned. If even that wouldn’t correctly position either of them then rotate the top until at least one of them is correctly positioned. Then:

      1. If both of those edges are in the correct position orient the cube as a whole so that one of them is in the front and do a left break.

      2. Otherwise orient the cube as a whole so that the correctly oriented but incorrectly positioned top edge is in the front and do a break in the direction where color of the sticker on the top edge matches the color of the front center sticker.

  5. Position the top corners. To cycle UFR → UBR → UBL do a left break and start over. To cycle UFL → UBL → UBR do a right break and start over. It’s always possible to position the corners using these sequences at most twice.

  6. Orient the top corners. The rotation sequence used for this turns UFR clockwise and UBR counterclockwise. It’s done by doing a left break and starting over. (This kicks off a cycle done in step 5 which you’ll then fix doing step 5 again.) To use this to solve the orientations in the fewest steps:

    1. If all four of the top corners are oriented wrong do the rotation sequence so only two or three of the top corners are oriented wrong.

    2. If three of the top corners are oriented wrong do the rotation sequence so that only two adjacent corners are oriented wrong.

    3. If two non-adjacent corners are oriented wrong do the rotation sequence so that two adjacent corners are oriented wrong.

    4. If only two adjacent corners are oriented wrong then if it’s possible to finish solving with a single use of the rotation move do that. Otherwise redesignate the side face they’re both adjacent to as the top and you’ll be able finish the solve with a single use of the rotation move.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Wed Feb 14 23:06:19 2024 Tags:
As was recently announced, the Linux kernel project has been accepted as a CNA as a CVE Numbering Authority (CNA) for vulnerabilities found in Linux. This is a trend, of more open source projects taking over the haphazard assignments of CVEs against their project by becoming a CNA so that no other group can assign CVEs without their involvment. Here’s the curl project doing much the same thing for the same reasons.
Posted Tue Feb 13 00:00:00 2024 Tags:

This paper has a very impressive result: They got a neural network based program to play chess at grandmaster level with no search whatsoever. While technically speaking there’s plenty of opportunity for tactical analysis to be happening here that’s all going on within the neural network and not using the custom written code for it.

The approach used is to take a corpus of chess positions, evaluate them using Stockfish (the world’s strongest custom chess engine) and then train a neural network to replicate those evaluations. This sounds like a simple idea, but it’s hard to get the details right and it requires a lot of computational power to actually do it.

The next step for this is to make it a ‘zero’ engine, meaning that it doesn’t have any training based off custom written software. First you start with the engine being random. Then you plug that in as the evaluation function into an alpha-beta pruner which has the extra board evaluation function that it detects when the game has been won. That will spit out board evaluations which, while still very poor quality, are more accurate than random numbers. You then train a new neural network on those numbers. Then you switch to the other corpus of chess positions (you need to alternate between two of them) and repeat the process again. With each generation the neural network will become stronger until it hits the same level it got with the non-zero approach.

Using positions from human or Stockfish games for the corpus of positions should work fine but it seems more appropriate to have the engine generate positions for itself. A reasonable approach to that would be each time an engine is generated it plays a set of games against itself and the positions from those are the alternate set of positions to be used in the generation after the next one.

Posted Mon Feb 12 04:08:11 2024 Tags:

What I’d always believed (and assume been told) was that the way to improve at Chess was by learning to be systematic in analysis, acquiring understanding of deep positional principles and a systematic, disciplined approach to manually doing alpha-beta pruning yourself when confronted with a position, and start with long time controls and work your way down as things become more automatic. What you don’t want to do is learn a bunch of silly little tricks which are only rarely applicable and do so at quick time controls which aren’t developing much of any discipline.

That advice is about 80% wrong. There’s some utility to basic positional formulas like improved piece weights and of course looking ahead multiple moves is a core skill especially at long time controls. But most of the rest of the advice is wrong, more based on a fantasy of what Chess is all about that what it actually is. In reality Chess, first and foremost, is a game of tactics. A reasonable definition of a game being ‘tactical’ is ‘If you slap together a crude manually designed board evaluation algorithm and an alpha-beta pruner it will obliterate even very strong humans’. Another way to think about it is how close the game is to a wordfind. Chess is obviously not a wordfind, but it is a tacticsfind. At each move the player finds the best tactic they can, resulting in a stronger or weaker position. How good of a tactic they find is directly correlated to how many moves they’re looking into the future.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Of course as one gets stronger seeing basic tactics becomes more of a given. Probably around 2300 playing strength the main determiner of Chess playing strength switches from how good you are at tactics to how good is your opening preparation. (Sorry, couldn’t resist.) But at my level the differences in board value caused by subtle positional differences are so small compared to swings caused by tactical misses that they’re a bit lost in the noise. What I’ve been getting a lot of benefit from is using this tactics trainer for a few minutes a day (mostly instead of checking social media). The key to getting improvement out of it is not to spend lots of time on each puzzle but to give yourself only a few seconds for each one, then play through the solution when you miss it, come up with an explanation of how your could have figured it out, and commit that to memory. The more of them you get through, the more you’ll remember. Yes it’s only teaching you silly tricks, but that’s most of what Chess is. Positional concepts themselves are often just acknowledgement of tactical potential which isn’t quite manifesting yet, like noticing when pieces aren’t defended even when nothing’s attacking them, or they’re attacked even when they’re currently adequately defended.

Even with only a few seconds to evaluate each position It’s possible to do quite a bit of lookahead, particularly once you get good at pulling out candidate moves. Where human lookahead deviates a lot from slavish alpha-beta pruning is that especially in very tactical positions you often see something which almost works which then suggests something you didn’t initially consider as a candidate move, especially if it involves distracting an enemy piece so it’s no longer defending something or in the way of something. It’s also common for something to be an obvious candidate move a few moves down and the better move order to be the less obvious one.

My own natural skill level at Chess isn’t very high, owing to a serious lack of visual memory. Okay okay, it’s a low natural skill level on the scale of mathematicians, and I can ‘visualize’ some things very well but it’s all 3d not 2d and not very useful for 2d board games. In any case, I’ve played enough Chess in my life that I should be a lot stronger than I am. But after doing tactics training for a few minutes a day for a few months my estimated strength by tactics hovers around 2200 or so depending on how long I take for each one and how tired I am my current caffeine and blood sugar levels. Playing strength seems to be around 1750 or so. It’s weaker because I’ve barely been playing actual chess games, resulting in my time management being awful and also my consistency at easier tactics isn’t what I’d like. It would be nice if the tactics trainer threw in a lot more ‘easy’ problems so there were strong rewards for getting easy problems right almost all the time instead of being so focused on getting hard problems right half the time. It would also be nice if it were more consistent at keeping the problem going through the hard to see move and making the opponent always force you to play the hard to find move even when it’s a weaker line for them. But tactics trainers are hard to write, and that’s by far the best one I know of.

Around 2300 is where tactics puzzle seem to switch over to needing some positional understanding, in that the resulting position from the right series of moves is superior for some subtle positional reason instead of conferring a clear material advantage. It’s interesting watching Chess commentary after gaining some basic skills. It becomes very obvious which commentators are strong players themselves and which are weak players using Stockfish, because the weak ones completely skip over obvious-to-strong-player variants which don’t work out in the end for very involved tactical reasons.

Next you’ll probably ask whether cheesy math team problems are better for improving at mathematics than learning actual deep concepts. To that I say that teaching integration should skip ahead to Laplace transforms and not waste all that time on techniques which get subsumed by it.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Sat Feb 3 03:14:45 2024 Tags:

This is a follow-up from our Spam-label approach, but this time with MOAR EMOJIS because that's what the world is turning into.

Since March 2023 projects could apply the "Spam" label on any new issue and have a magic bot come in and purge the user account plus all issues they've filed, see the earlier post for details. This works quite well and gives every project member the ability to quickly purge spam. Alas, pesky spammers are using other approaches to trick google into indexing their pork [1] (because at this point I think all this crap is just SEO spam anyway). Such as commenting on issues and merge requests. We can't apply labels to comments, so we found a way to work around that: emojis!

In GitLab you can add "reactions" to issue/merge request/snippet comments and in recent GitLab versions you can register for a webhook to be notified when that happens. So what we've added to the gitlab.freedesktop.org instance is support for the :do_not_litter: (🚯) emoji [2] - if you set that on an comment the author of said comment will be blocked and the comment content will be removed. After some safety checks of course, so you can't just go around blocking everyone by shotgunning emojis into gitlab. Unlike the "Spam" label this does not currently work recursively so it's best to report the user so admins can purge them properly - ideally before setting the emoji so the abuse report contains the actual spam comment instead of the redacted one. Also note that there is a 30 second grace period to quickly undo the emoji if you happen to set it accidentally.

Note that for purging issues, the "Spam" label is still required, the emojis only work for comments.

Happy cleanup!

[1] or pork-ish
[2] Benjamin wanted to use :poop: but there's a chance that may get used for expressing disagreement with the comment in question

Posted Mon Jan 29 07:58:00 2024 Tags:

I’ve recently started teaching juggling with a new approach which seems to be very effective, often getting someone competently juggling in only a single session. Because I want more people to learn how to juggle I’ll now explain it in the hopes that others start using this approach to good effect as well.

The problem with learning juggling (and with going to higher numbers) is that it’s too big of a leap. What you want are ‘stepping stones’: patterns which are within what the student can do or close to it but challenging enough that they’re getting useful feedback and improving from trying to do them. Ideally you’d have a low gravity chamber for people to juggle in while practicing and gradually increase the gravity level until it was Earth normal. Sadly physics doesn’t allow for that. Maybe having people roll balls up an angled board and gradually increasing the angle until it was vertical and removing it completely would work well, but I haven’t tried that.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

The difficult of a juggling pattern has to do with the ratio of balls to hands. Since the vast majority of people only have two hand and their feet are fairly useless for juggling increasing the number of hands is not an option. If you go down from 3 to 2 balls it’s no longer juggling, it’s just holding balls, and since there’s on integer between 2 and 3 [citation needed] there’s no easier pattern available.

But there’s a loophole! You can do pattern which the beginner does in collaboration with an expert. This allows for a lower ratio of balls to hands by adding more hands, allows the beginner to only use one hand, and averages out the skill of the jugglers to be between the expert and the beginner which allows for harder patterns than the beginner could do alone. Not only does this allow for stepping stone patterns but it’s very good motivationally because beginners can participate in a legitimate juggling pattern right off the bat.

The first pattern to do is four balls and three hands with the beginner doing one of the three hands. It’s best to start with throwing a single ball through its orbit to get a feel for what the throws are. (This applies to all the later patterns as well so pretend I repeat the advice about starting with one ball for each one). To make later patterns easier the student should make inside throws. They should stand face to face with the teacher and throw from their right hand to the teacher’s right hand, which then throws to the teacher’s left hand, and finally the student’s right hand. It’s easiest to start with the student holding two balls and they initiate the pattern. Also gets the used to starting with two which they’ll eventually have to do when juggling by themselves. After they get the hang of their right hand you can switch to their left hand, where the ball goes from the student’s left hand to the the teacher’s left hand, then the teacher’s right hand, and finally back to the student’s left hand. For left handed students the other order should be used.

The next pattern up is five balls and four hands, which is an even lower ratio of balls to hands but does require the student use both hands. The student should do the inside throw half of the pattern because inside throws are what they’ll need to do for juggling by themselves. The pattern is that balls go from the student’s right hand to the teacher’s right hand, then the student’s left hand, then the teacher’s left hand, and finally back to the student’s right hand. It’s easiest to start with the student having two balls in their right and and one in their left and initiating the first throw. (Or starting with two in their left and one in their right if they’re left handed.)

Almost at the end is pair juggling with three balls and two hands where the student does the right hand and the teacher does the left, then the mirror image pattern where the student does the left hand and the teacher does the right. Finally the student has mastered all the elements which need to be put together and they’re ready to try full-blown juggling by themselves. The build-up patterns have covered the elements of it enough that some people with no athletic backgrounds can manage to get in good runs after less than an hour of training.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Fri Jan 26 23:19:04 2024 Tags:

This world jigsaw is very cool but feels a bit imperfect

The problem is that you can’t take multiple copies of the puzzle and tessellate them about the plane without visible seams showing up all over the place. This is because it’s based off an icosahedron and when it smushes flat the vertices of the triangles have to have a bit missing.

There are two possible geometries which could fix this. One is to divide the globe into two hemispheres, cut those out, and deform them both to be flat squares. Those squares can then be used to tesselate the plane via the hack of four of them going around their vertices instead of two. As a result the world is doubled around those vertices but topologically normal everywhere else.

The second geometry which works is to divide the world into triangles corresponding to the faces of a tetrahedron then deform all of those to be flat triangles. Those can the tessellate the plane by putting six triangles around each vertex instead of three, again doubling the world around the corners but leaving it topologically normal everywhere else.

There’s an interesting question of how to nicely align either of these geometries. For the first one I think it’s possible to make the squares aligned nicely with the equator and put two vertices in the Pacific Ocean and two in the Atlantic Ocean. The tetrahedral one may require the vertices be closer to land bodies and not align with latitude so well, although there’s no requirement that latitude and longitude lines be included on the map.

Posted Thu Jan 18 18:03:20 2024 Tags:

BIP-341 defines Taproot outputs as either a single key, or a key and some script info. You use a dummy key if you only want to use the script. This “tapscript” is currently very similar to Segwit v0 P2WSH, but carefully defined to be easily upgradable.

Unfortunately, when we actually try to use this upgrade flexibility (for OP_CHECKTEMPLATEVERIFY or OP_TXHASH for example) we quickly find as Steven Roose pointed out to me that users also want a neutered Segwit v0 variant: using Tapscript requires a 33 byte penalty over simple P2WSH!

The fix is both simple and annoying: allowing the BIP-341 control block to be empty (or, perhaps, 32*m bytes) to indicate the key is the NUMS point lift_x(0x50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) as suggested by BIP-341. BIP-341 suggests using a tweak of this key, which hides the existence of the script (if it were guessable) but forcing this at users expense was a mistake given the existence of P2WSH.

Regrettably, allowing this simple change requires (I think) using a Segwit version of 2, since BIP-341 defines v1 to fail if the control block is not an accepted length. Others might have an idea if we want to roll in other changes at that point.

Enjoy!

Posted Mon Jan 15 13:30:00 2024 Tags:

As I explore the use of Bitcoin Script for introspection, I am not overly concerned with total script size, because if common usage patterns emerge those can be soft-forked into new opcodes, or new address types. But I have been concerned with constructions which require the use of Child-Pays-For-Parent for fee paying, as that makes the transaction significantly more expensive than using inline fees and Replace-By-Fee.

Lightning uses this kind of “anchor” construction, and although it’s only used in the forced-closure case, it’s wasteful of onchain space when it happens. It also uses a “bring your own fee” construction for HTLC transactions, using SIGHASH_SINGLE|SIGHASH_ANYONECANPAY which means only the input and outputs are fixed, and the operation of this is much smoother in general.

(It’s not coincidence that my main contribution to the Eltoo construction was to use a similar single-input/output scheme to allow such last-minute fee binding and RBF).

More recently, Peter Todd argues that such inefficient fee bumping is a threat to decentralization as it creates significant incentive to use out-of-band fees, which would have to be paid in advance and thus would favor large miners.

Stacking Transactions: Adding Fees Later

If you carefully construct your covenant to allow addition of a fee input (and usually a change output) later, you can avoid the expense of a child transaction and put the fees inline.

If you’re really clever, you can combine multiple covenant transactions into one transaction, and add a fee input/change output to all of them at once and reduce total costs even more. I call this stacking, and my thesis is that Bitcoin fees will rise and eventually make such joining profitable, normal and necessary.

Note that such stacking requires real engineering work: we’ve seen how long it took Bitcoin exchanges to implement even simple batching! And for full disclosure: stacking like this is already possible with Lightning with anchor outputs and HTLC transactions, which are signed with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY, and yet I still haven’t implemented stacking in Core Lightning!

I now want to discuss the dangers of doing this incorrectly, and how OP_TXHASH can support doing it in various scenarios.

Partial Validation Attacks: A Primer

I vaguely recall first learning of this attack in the context of signing devices, but I cannot find a reference. ~I’ll add one when some clever reader points it out!~ Greg Sanders’s post Hardware Wallet attacks by input ownership omission and fix though I may have cribbed it from Bitcoin OpTech (Greg he also mentioned jl2012 may have been involved).

Consider a transaction designed to take a 1BTC input and pay Bob 0.1BTC, with the remaining 0.9BTC going to a change address. Your software asks a signing device to sign the first input. It checks the input, checks the outputs are correct, prompts the user (telling it we’re paying Bob 0.1BTC) and signs it.

Now consider a transaction which has two identical inputs. Our naive signing device, asked to sign the first input, would see it as valid, and sign it. If we then ask it to sign the second input it would also see it as valid, and sign it. But the transaction would actually pay 1BTC to fees!

I call this a “Partial Validation Attack”, and the same problem can occur with stacking! In this case, it’s the covenant checking the input, not the hardware wallet. If it does not check other inputs (because it wants to allow you to add fees and/or stack other transactions together), and it would allow other covenants to validate the same outputs, it is vulnerable.

Partial Validation Exploit: A Covenant Example.

Imagine you want to create a covenant that forces a transaction to pay all its input amount to a given address, and you have OP_TXHASH and OP_CAT.

You want it to stack, so you simply validate that output #0 go to the given address, and that the amount match the input amount of the current input. This is fairly easy, you can either use OP_TXHASH to get the hashed amount from output #0, and again from the input and compare, or require the output supply the amount on the stack, duplicate it and hash it, then call OP_TXHASH to hash the output #0 amount and the current input amount, and make sure that’s what they provided.

Then when you want to spend it, you can pay fees by adding as many inputs (and outputs) as you need without invalidating the transaction.

Now, you create two 1BTC outputs to this covenant address. Mallory creates a transaction which spends both at once: it pays 1BTC to your required address (output #0) and sends the other 1BTC to their own address, stealing your funds. Both inputs’ covenants check that output #0 pays the full amount to the required address, and are satisfied. Oops!

Avoiding Partial Validation Issues When Stacking Transactions

This can avoided in one of four ways:

  1. Specify the entire transaction, CTV-style. But then you cannot add fees inline.
  2. Have each input examine all the other inputs. This is limited since there is no looping in Script.
  3. Insist the current input also be at index #0, so there can only be one.
  4. Use relative output addressing, so we examine the output corresponding to the current input.

Of these options, only the final one (relative output addressing) allows stacking, so obviously that’s my preferred approach.

Unfortunately, this stacking is only possible with current OP_TXHASH if the number of inputs is equal to the number of outputs. This can often be arranged, but any shared UTXO arrangement results in multi-in-single-out and single-in-multi-out. Can we do better?

Stacking Odd-Shaped Transactions

We can imagine OP_TXHASH supporting an indexing scheme which lets you refer to “output = input-number * N” (I proposed this as a possibility in my BIP review). (We can also imagine OP_TX which would let you push the current input number on the stack directly, to do this calculation yourself!).

This would let us stack have several 1-input/2-output txs. But it wouldn’t let us stack different topologies, like a 1-in/2-out on top of a 2-in/1-out tx.

I considered adding an “output accumulator” where some OP_TXHASH field selector would increment the “next output” counter. But writing it up I realized that this fails in the presence of OP_SUCCESS which can cause an input to be skipped; that would be a hard fork!

If we really want to do this in general, we would need to flag how many outputs each input “owns”, such as in the nSequence field. And then have a “relative to owned outputs” modifier in OP_TXHASH. As nSequence bits are limited and this would irreversibly consume some, I am reluctant to propose this unless real world usage of covenants (i.e. after they’re enabled by a soft-fork) shows it would have real onchain benefits.

Side Note: Things That Don’t Work

You can imagine handing the output number(s) in the witness (and changing them when you stack the transactions), but that re-introduces the “partial transaction” bug. Similarly, providing multiple signatures for different stacking cases would expose you to the issue.

Summary

I believe stacking transactions is going to become popular to reduce fees: while this is currently easy for 1-input-1-output transactions, and the OP_TXHASH proposal makes it possible for N-input-N-outputs, I suspect the N-inputs-1-output an 1-input-N-output cases will be common (shared UTXOs), so we should try to allow those. It would also be nice to design such that we can allow nSequence bits to indicate the number of associated outputs in a future soft fork.

Posted Sun Jan 7 13:30:00 2024 Tags:

In my previous post on Examing scriptpubkeys in Script I pointed out that there are cases where we want to require a certain script condition, but not an exact script: an example would be a vault-like covenant which requires a delay, but doesn’t care what else is in the script.

The problem with this is that in Taproot scripts, any unknown opcode (OP_SUCCESSx) will cause the entire script to succeed without being executed, so we need to hobble this slightly. My previous proposal of some kind of separator was awkward, so I’ve developed a new idea which is simpler.

Introducing OP_SEGMENT

Currently, the entire tapscript is scanned for the OP_SUCCESS opcodes, and succeeds immediately if one it found. This would be modified:

  1. The tapscript is scanned for either OP_SEGMENT or OP_SUCCESSx.
  2. If OP_SEGMENT is found, the script up to that point is executed. If the script does not fail, scanning continues from that point.
  3. If OP_SUCCESSx is found, the script succeeds.

This basically divides the script into segments, each executed serially. It’s not quite as simple as “cut into pieces by OP_SEGMENT and examine one at a time” because the tapscript is allowed to contain things which would fail to decode altogether, after an OP_SUCCESSx, and we want to retain that property.

When OP_SEGMENT is executed, it does nothing: it simply limits the range of OP_SUCCESS opcodes.

Implementation

The ExecuteWitnessScript would have to be refactored (probably as a separate ExecuteTapScript since 21 of its 38 lines are an “if Tapscript” anyway), and it also implies that the stack limits for the current tapscript would be enforced upon encountering OP_SEGMENT, even if OP_SUCCESS were to follow after.

Interestingly, the core EvalScript function wouldn’t change except to ignore OP_SEGMENT, as it’s already fairly flexible.

Note that I haven’t implemented it yet, so there may yet be surprises, but I plan to prototype after the idea has received some review!

Enjoy!

Posted Wed Jan 3 13:30:00 2024 Tags:
Analyzing the NSA/GCHQ arguments against hybrids. #nsa #quantification #risks #complexity #costs
Posted Tue Jan 2 16:59:39 2024 Tags:

A thing I sometimes dabble on nights and weekends is improved geometries for clustering algorithms. Just added new geometries for larger dimensions based on sphere packing. Software packages which do clustering should be able to switch to these and magically work better for only minor computational cost. Benchmarks here:

Space type comparisons

This metric is a good measure of how much unnecessary noise is added to distances and how easily points can slide past each other when being annealed.

The lattice implementation benchmarks look a little bumpy because of strangeness in sphere packing in different numbers of dimensions. It is optimal in dimensions 2, 3, 4, 6, and 8, but there are improvements which could be implemented with a bunch of work in 5, 7, and 9 dimensions. Above that the best option is an open mathematical problem but those are large numbers of dimensions to use for clustering anyway.

For visualization 2d lattice should be used. It 'crystallizes' nicely as shown here:

Crystallizing in 2d

For applications which need antipodes (opposite points) Torus is best.

This is based on the sphere packing thoughts I had earlier. It turns out the extra 2 spheres for the kissing number in 7 dimensions come from squeezing spheres in at the north and south poles, which Henry Cohn kindly explained to me. I had the bright idea of trying to squeeze an extra sphere in just the north pole for 6 dimensions and then anneal everything else out of the way, which sadly doesn’t quite work but did result in a new record for the spherical code for 6 dimensions and 73 spheres.

It also turns out that although this kissing number construction forms lattices in 6 and 8 dimensions (the construction in 8 dimensions is explained on Wikipedia) in 5 and 7 dimensions because they’re odd going to the offset of the ‘filled in antipode’ twice would result in landing on a lattice point which has been knocked out because it’s of the opposite parity. It’s a bit bizarre that these match exactly the kissing numbers from the optimal packings anyway, which seems to imply that they can be used to tesselate space to form a sphere packing which is of maximal density.

Posted Sat Dec 30 03:02:35 2023 Tags:

As noted in my previous post on Dealing with Amounts in Bitcoin Script, it’s possible to use the current opcodes to deal with satoshi values in script, but it’s horribly ugly and inefficient.

This makes it obvious that we want 64-bit-capable opcodes, and it makes sense to restore disabled opcodes such as OP_AND/OP_OR/OP_XOR/OP_INVERT, as well as OP_LSHIFT, OP_RSHIFT and maybe OP_LEFT, OP_RIGHT and OP_SUBSTR.

Blockstream’s Elements Arithmetic Opcodes

Blockstream’s Elements codebase is ahead here, with a full set of 64-bit opcodes available for Liquid. All these operations push a “success” flag on the stack, designed that you can follow with an OP_VERIFY if you want to assert against overflow. They then provide three conversion routines, to convert to and from CScriptNum, and one for converting from 32-bit/4-byte values.

But frankly, these are ugly. We need more than 31 bits for satoshi amounts, and we may never need more than 64 bits, but the conversions and new opcodes feel messy. Can we do better?

Generic Variable Length Amounts

Script amounts are variable length, which is nice when space matters, but terribly awkward for signed values: using the high bit of the last byte, this being little-endian, requires a 0 padding byte if the high bit would otherwise be set. And using negative numbers is not very natural (pun intended!), since we have OP_SUB already.

What if we simply used unsigned, variable-length little-endian numbers? These are efficient, retain compatibility with current unsigned Script numbers, and yet can be extended to 64 bits or beyond, without worrying about overflow (as much).

I propose OP_ADDV, which simply adds unsigned two little-endian numbers of arbitrary length. 64 bits is a little simpler to implement, but there are a number of useful bit tricks which can be done with wide values and I can’t see a good reason to add a limit we might regret in future.

OP_SUBV would have to be Elements-style: pushing the absolute result on the stack, then a “success” flag if the result isn’t negative (effectively, a positive sign bit).

Limitations on Variable Operations

If OP_CAT is not limited to 520 bytes as per OP_CAT beyond 520 bytes, then we could make OP_ADDV never fail, since the effective total stack size as per that proposal could not be increased by OP_ADDV (it consumes its inputs). But that introduces the problem of DoS, since on my laptop 2 million iterations (an entire block) of a mildly optimized OP_ADDV of 260,000 bytes would take 120 seconds.

Thus, even if we were to allow more then 520 byte stack elements, I would propose either limiting the inputs and outputs to 520 bytes, or simply re-using the dynamic hash budget proposed in that post for arithmetic operations.

Multiply And Divide

Restoring OP_MUL to apply to variable values is harder, since it’s O(N^2) in the size of the operands: it performs multiple shifts and additions in one operation. Yet both this and OP_DIV are useful (consider the case of calculating a 1% fee).

I suggest this is a good case for using an Elements-style success flag, rather than aborting the script. This might look like:

  1. Normalize the inputs to eliminate leading zeros.
  2. If either input exceeds 128 bits, push 0 0.
  3. For OP_DIV, if the divisor is 0, push 0 0.
  4. For OP_MUL, if the output overflows, push 0 0.
  5. Otherwise the (normalized) result and 1.

Both GCC and clang support an extension for 128 bit operations via __uint128_t, so this implementation is fairly trivial (OP_MUL overflow detection is assisted greatly by __builtin_mul_overflow extension in GCC and clang).

Shift Operations, Splitting and Comparison

OP_LSHIFT and OP_RSHIFT would now be restored as simple bit operations (there’s no sign bit), treating their argument as unsigned rather than a signed amount. OP_LSHIFT would fail if the result would be excessive (either a 520 byte limit, or a dynamic hash budget limit). Neither would normalize, leaving zero bytes at the front. This is useful when combined with OP_INVERT to make a mask (0 OP_ADDV can be used to normalize if you want).

OP_LEFT, OP_SUBSTR and OP_RIGHT should probably return empty on out-of-range arguments rather than failing (I’m actually not sure what the original semantics were, but this is generally sensible).

OP_EQUAL just works, but we need at least a new OP_GREATERTHANV, and I suggest the full complement: OP_GREATERTHANOREQUALV, OP_LESSTHANV and OP_LESSTHANOREQUALV.

Use for Merkle Tree Construction.

Regretfully, our comparison opcodes don’t work as OP_LESS which is required for Merkle Tree construction to examine scripts: the SHA256 hashes there need to be compared big-endian, not little endian! So I suggest OP_BYTEREV: this adds some overhead (reverse both merkle hashes to compare them), but is generally a useful opcode to have anyway.

Summary

We can extend current bitcoin script numbers fairly cleanly by having new opcodes which deal with variable-length little-endian unsigned numbers. The limits on most of these can be quite large, but if we want excessive limits (> 520 bytes) we need to have a budget like the checksig budget.

We can deal easily with current CScriptNum numbers, 32-bit numbers used by nLocktime, and 64-bit numbers used by satoshi amounts.

The soft fork would restore the following opcodes:

  • OP_LSHIFT[^simplified]
  • OP_RSHIFT[^simplified]
  • OP_AND
  • OP_OR
  • OP_XOR
  • OP_INVERT
  • OP_MUL[^extended]
  • OP_DIV[^extended]
  • OP_LEFT
  • OP_RIGHT
  • OP_SUBSTR

And add the following new ones:

  • OP_ADDV: add two little-endian unsigned numbers
  • OP_SUBV: sub two little-endian unsigned numbers, push non-negative flag
  • OP_GREATERTHANV: compare two little-endian unsigned numbers
  • OP_GREATERTHANOREQUALV: compare two little-endian unsigned numbers
  • OP_LESSTHANV: compare two little-endian unsigned numbers
  • OP_LESSTHANOREQUALV: compare two little-endian unsigned numbers
  • OP_BYTEREV: reverse bytes in the top stack element

This would make it far easier to deal with numeric fields to bring covenant introspection to its full potential (e.g. OP_TXHASH).

[^simplified] The original versions preserved sign, but we don’t have that. [^extended] These apply to unsigned numbers up to 128 bits, not just signed 31 bit values as the originals did.

Posted Fri Dec 29 13:30:00 2023 Tags:

Continuing on my posts about eventually consistent merge algorithms, this one finally gets something decent. While eventual consistency sounds a bit impractical and unimportant it turns out this approach leads to a straightforward and reliable implementation of cherry picking which makes the whole exercise very compelling.

The other day I presented an algorithm for doing merging which is eventually consistent but complained that it’s ‘goofy’. The problem is that it invokes lexical order as a tiebreak way too often, with the ideal amount being ‘never’. That ideal isn’t reachable because in a distributed system if one person inserts a line into AB to make ACB and another does ADB then some tiebreak rule to determine the relative order of C and D which is consistent across the entire universe needs to be invoked. That said, if a series of updates are made to a file sequentially there doesn’t appear to be a reason why you shouldn’t be able to record the entire history with no lexical tiebreaks whatsoever, and I’ll now present a slightly quirky data structure which accomplishes exactly that.

The core idea is to organize all lines in a file in a tree. Each node in the tree corresponds to a line in the file except for the root which is the file’s beginning. Every node also has a notation as to whether it’s before or after its parent in the file. When generating an actual file out of this the rule is that if A is not a descendent of B and C is a descendent of B then B and C must both be on the same side of A. Only if a node has two descendants both in the same direction does the lexical order tiebreak rule get invoked. Usually it doesn’t have to be, because whenever a line is inserted between two others there will always be at least one of the two neighbors which has never had a descendant in the direction of the new line. (Note that this is a weave and deleted lines need to be included when deciding where a new line is inserted!)

Okay that was a bit of a mouthful so let’s do an example. Let’s say that we make an initial commit of a file as ABC. There are a few ways this can be interpreted, including:

  • File beginning

    • → A

      • → B

        • → C

or

  • File beginning

    • → C

      • ← A

        • ← B

or

  • File beginning

    • → B

      • ← A

      • → C

It isn’t clear which of these is best. The first option seems cleanest. A binary splitting one will result in smaller representations of cherry picks. It may have about as much significance as which orientation you install toilet paper, or maybe there’s some compelling motivation for some order I haven’t thought of yet. Much more important than the specific interpretation is that one needs to be selected at commit time and that needs to be respected forever after.

For the sake of clarity let’s go with the first interpretation. Now let’s say you insert two lines to make ADEBC. There are two possible interpretations of this:

  • File beginning

    • → A

      • ← D

        • → E

      • → B

        • → C

or

  • File beginning

    • → A

      • ← E

        • ← D

      • → B

        • → C

Again there’s no compelling reason to prefer one over the other. Let’s go with the first one because it seems less weird. The three ways of inserting a line F around DE now result in:

  • File beginning

    • → A

      • ← D

        • ← F

        • → E

      • → B

        • → C

  • File beginning

    • → A

      • ← D

        • → E

          • ← F

      • → B

        • → C

  • File beginning

    • → A

      • ← D

        • → E

          • → F

      • → B

        • → C

To do merges with this approach all the usual weave stuff applies: Every line which has ever been included in the file is remembered with a generation count where even numbers mean deleted (or in the case of 0 not born yet) and odd numbers mean present. When two versions of the same line are merged together the larger generation count wins. For two lines to be ‘the same’ they need not just their contents but their entire path to the root to be identical.

To do cherry picks with this structure the modified lines are presented with their updated generation counts. Note that sometimes these lines are dependent on other lines which aren’t updated. Those should be presented with generation count zero, so they’re enforcing position but their state is always deferred to the other side of a merge. Note that although cherry picks are explicit and can handle just about any historical ordering they don’t reference the history themselves.

There’s an interesting question of what order new lines should go in relative to lines which were previously deleted in the same location. The simple heuristic ‘new lines always go first’ may work fine but I haven’t thought through what edge cases there might be.

What form of lexical order should be used for tiebreaks probably doesn’t matter much but there may be some reason why it’s a good idea for empty lines to specifically go first or last.

If you’re presenting a conflict and have, for example, lines which are in the order 1234 and one side contains 13 and the other 24 rather than blow up the order by presenting that conflict as a simple two way one it’s probably better to present it as a conflict between 1 and 2 followed by a conflict between 3 and 4. If there’s a conflict between 13 and 2 that can be presented as a conflict between 1 and 2 followed by a conflict between 3 and nothing.

Although this supports cherry picking very well it requires explicit specification of what the cherry picks are to work properly. You can and should make it so that if the exact same patches are made in the exact same order then they’ll clean merge but if any sort of squashing is done differently on one side all bets are off. It appears that implicit cherry-picking is a fundamentally busted concept, similar to how implicit undo is a fundamentally busted concept. That said, we now have explicit local undo which works very well! To use it, make a local undo, then a create a redo which increments the generation counts to undo the undo, and apply that redo to the main branch. This is remarkably straightforward given the amount of flailing which has gone into figuring out methods of supporting it.

Another thing this doesn’t support is moves within files. It may be that implicit moves within files is a fundamentally busted concept because cleanly applying a change to a similar looking but actually different function is much more of a disaster than having an unnecessary conflict. Maybe there’s a way of supporting explicit moves within files, but that would be a big extension to the underlying data structure and a lot of complicated UX for very limited functionality gained.

Thanks for reading Bram’s Thoughts! Subscribe for free to receive new posts and support my work.

Posted Sat Dec 23 23:46:57 2023 Tags:

The original OP_CAT proposal limited the result to be 520 bytes, but we want more for covenents which analyze scripts (especially since OP_CAT itself makes scripting more interesting).

My post showed that it’s fairly simple to allow larger sizes (instead of a limit of 1000 stack elements each with a maximum of 520 bytes each, we reduce the element limit for each element over 520 bytes such that the total is still capped the same).

Hashing of Large Stack Objects

But consider hashing operations, such as OP_SHA256. Prior to OP_CAT, it can only be made to hash 520 bytes (9 hash rounds) with three opcodes:

OP_DUP
OP_SHA256
OP_DROP

That’s 3 hash rounds per opcode. With OP_CAT and no 520 byte stack limit we can make a 260,000 byte stack element, and that’s 4062 hash rounds, or 1354 per opcode, which is 450x as expensive so we definitely need to think about it!

A quick benchmark shows OpenSSL’s sha256 on my laptop takes about 115 microseconds to hash 260k: a block full of such instructions would take about 150 seconds to validate!

So we need to have some limit, and there are three obvious ways to do it:

  1. Give up, and don’t allow OP_CAT to produce more than 520 bytes.
  2. Use some higher limit for OP_CAT, but still less than 260,000.
  3. Use a weight budget, like BIP-342 does for checksig.

A quick benchmark on my laptop shows that we can hash about 48k (using the OpenSSL routines) in the time we do a single ECDSA signature verification (and Taproot charges 50 witness weight for each signature routine).

A simple limit would be to say “1 instruction lets you hash about 1k” and “the tightest loop we can find is three instructions” and so limit OP_CAT to producing 3k. But that seems a little arbitrary, and still quite restrictive for future complex scripts.

My Proposal: A Dynamic Limit for Hashing

A dynamic BIP-342-style approach would be to have a “hashing budget” of some number times the total witness weight. SHA256 uses blocks of 64 bytes, but it is easier to simply count bytes, and we don’t need this level of precision.

I propose we allow a budget of 520 bytes of hashing for each witness byte: this gives us some headroom from the ~1k measurement above, and cannot make any currently-legal script illegal, since the opcode itself would allow the maximal possible stack element.

This budget is easy to calculate: 520 times total witness weight, and would be consumed by every byte hashed by OP_RIPEMD160, OP_SHA1, OP_SHA256, OP_HASH160, OP_HASH256. I’ve ignored that some of these hash twice, since the second hash amounts to a single block.

Is 520 Bytes of hashing per Witness Weight Too Limiting?

Could this budget ever be limiting to future scripts? Not for the case of “your script must look like {merkle tree of some template}” since the presence of the template itself weighs more than enough to allow the hashing. Similarly for merkle calculations, where the neighbor hashes similarly contribute more than enough for the hash operations.

If you provide the data you’re hashing in your witness, you can’t reasonably hit the limit. One could imagine a future OP_TX which let you query some (unhashed) witness script of (another) input, but even in this case the limit is generous, allowing several kilobytes of hashing.

What Other Opcodes are Proportional to Element Length?

Hashing is the obvious case, but several other opcodes work on arbitrary length elements and should be considered. In particular, OP_EQUAL, OP_EQUALVERIFY, the various DUP opcodes, and OP_CAT itself.

I would really need to hack bitcoind to run exact tests, but modifying my benchmark to do a memcmp of two 260,000 byte blobs takes 3100ns, and allocating and freeing a copy takes 3600.

The worst case seems to be arranging for 173k on the stack then repeatedly doing:

OP_DUP
OP_DUP
OP_EQUALVERIFY

4MB of this would take about 8.9 seconds to evaluate on my laptop. Mitigating this further would be possible (copy-on-write for stack objects, or adding a budget for linear ops), but 10 seconds is probably not enough to worry about.

Posted Thu Dec 21 13:30:00 2023 Tags:

You may have seen the news that Red Hat Enterprise Linux 10 plans to remove Xorg. But Xwayland will stay around, and given the name overloading and them sharing a git repository there's some confusion over what is Xorg. So here's a very simple "picture". This is the xserver git repository:

$ tree -d -L 2 xserver
xserver
├── composite
├── config
├── damageext
├── dbe
├── dix
├── doc
│   └── dtrace
├── dri3
├── exa
├── fb
├── glamor
├── glx
├── hw
│   ├── kdrive
│   ├── vfb
│   ├── xfree86              <- this one is Xorg
│   ├── xnest
│   ├── xquartz
│   ├── xwayland
│   └── xwin
├── include
├── m4
├── man
├── mi
├── miext
│   ├── damage
│   ├── rootless
│   ├── shadow
│   └── sync
├── os
├── present
├── pseudoramiX
├── randr
├── record
├── render
├── test
│   ├── bigreq
│   ├── bugs
│   ├── damage
│   ├── scripts
│   ├── sync
│   ├── xi1
│   └── xi2
├── Xext
├── xfixes
├── Xi
└── xkb
The git repo produces several X servers, including the one designed to run on bare metal: Xorg (in hw/xfree86 for historical reasons). The other hw directories are the other X servers including Xwayland. All the other directories are core X server functionality that's shared between all X servers [1]. Removing Xorg from a distro but keeping Xwayland means building with --disable-xfree86 -enable-xwayland [1]. That's simply it (plus the resulting distro packaging work of course).

Removing Xorg means you need something else that runs on bare metal and that is your favourite Wayland compositor. Xwayland then talks to that while presenting an X11-compatible socket to existing X11 applications.

Of course all this means that the X server repo will continue to see patches and many of those will also affect Xorg. For those who are running git master anyway. Don't get your hopes up for more Xorg releases beyond the security update background noise [2].

Xwayland on the other hand is actively maintained and will continue to see releases. But those releases are a sequence [1] of

$ git new-branch xwayland-23.x.y
$ git rm hw/{kdrive/vfb/xfree86/xnest,xquartz,xwin}
$ git tag xwayland-23.x.y
In other words, an Xwayland release is the xserver git master branch with all X servers but Xwayland removed. That's how Xwayland can see new updates and releases without Xorg ever seeing those (except on git master of course). And that's how your installed Xwayland has code from 2023 while your installed Xorg is still stuck on the branch created and barely updated after 2021.

I hope this helps a bit with the confusion of the seemingly mixed messages sent when you see headlines like "Xorg is unmaintained", "X server patches to fix blah", "Xorg is abandoned", "new Xwayland release.

[1] not 100% accurate but close enough
[2] historically an Xorg release included all other X servers (Xquartz, Xwin, Xvfb, ...) too so this applies to those servers too unless they adopt the Xwayland release model

Posted Thu Dec 14 04:13:00 2023 Tags: