Planet Scheme

Sunday, February 5, 2023

Scheme Requests for Implementation

SRFI 244: Multiple-value Definitions

SRFI 244 is now in final status.

A define-values form is a definition that binds multiple variables from a single expression returning multiple values.

by Marc Nieper-Wißkirchen at Sunday, February 5, 2023

Monday, January 30, 2023

Idiomdrottning

geminih — Not Invented Here gemtext to SXML

Geminih is a library for Chicken Scheme to turn gemtext into SXML.

It exports one procedure geminih, that can take a single string for the entire page, or a list of lines, or if given no argument reads from current-input-port.

That procedure returns a list of SXML tags that you can cons body or div on top of, or splice into a quasiquoted document.

For source code,

git clone https://idiomdrottning.org/geminih

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Monday, January 30, 2023

A simple parser

Acetone is a parser for Chicken Scheme that helps you turn lists into trees.

Acetone contains one procedure, parse, that works like a map-in-order:

(parse add1 '(0 1 2))
⇒ (1 2 3)

Except it can also handle multiple values, or zero:

(parse (fn (when (even? x) (values x x))) '(0 1 2 3))
⇒ (0 0 2 2)

It can also insert parentheses by using the keywords #:open and #:close like this:

(parse (fn (cond ((zero? (modulo x 3)) (values #:open x))
                 ((= 2 (modulo x 3)) (values x #:close))
                 (else x)))
       (iota 8))
⇒ ((0 1 2) (3 4 5) (6 7))

So once you have your lists of tokens (you get that from a lexer, which means something like string-split or read-lines), you can use parse with a procedure you write that transforms the tokens and adds structure with #:open and #:close.

This also works which is sometimes useful:

((parse add1) (iota 3))
⇒ (1 2 3)

But my transformations depend on state

No problem, just use side-effects! Keep track of state separately, with parameters, call-tables, or closures.

But I want to reorder things

Moving things down is no problem, just stash them in separate state and grab them back when you need them.

Moving things up requires separate passes. Go through it once, yank out and collect everything you want to move up (in a call-table for example), and then go through it again and put it in where it belongs.

Source code

git clone https://idiomdrottning.org/acetone

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Monday, January 30, 2023

Friday, January 27, 2023

Idiomdrottning

Undertexter

It’s fun and easy to play mp4 videos in the browser directly from a web dirlisting without having to set up a complex and heavy media server but you can’t select subtitles. So here’s a brev app that generates a minimal HTML file that just has a video tag.

It shells out to ffmpeg, which is a requirement, to convert the SRTs.

Usage

undertexter --help
Usage: undertexter [OPTIONS]
 --video=ARG              Video file
 --sub-dir=ARG            Subs directory

Installation

There’s no egg for this one yet but install csc and chicken-install and ffmpeg and then:

git clone https://idiomdrottning.org/undertexter
cd undertexter
chicken-install brev
csc -prologue <(echo "(import brev)") undertexter.brev

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Friday, January 27, 2023

Andy Wingo

three approaches to heap sizing

How much memory should a program get? Tonight, a quick note on sizing for garbage-collected heaps. There are a few possible answers, depending on what your goals are for the system.

you: doctor science

Sometimes you build a system and you want to study it: to identify its principal components and see how they work together, or to isolate the effect of altering a single component. In that case, what you want is a fixed heap size. You run your program a few times and determine a heap size that is sufficient for your problem, and then in future run the program with that new fixed heap size. This allows you to concentrate on the other components of the system.

A good approach to choosing the fixed heap size for a program is to determine the minimum heap size a program can have by bisection, then multiplying that size by a constant factor. Garbage collection is a space/time tradeoff: the factor you choose represents a point on the space/time tradeoff curve. I would choose 1.5 in general, but this is arbitrary; I'd go more with 3 or even 5 if memory isn't scarce and I'm really optimizing for throughput.

Note that a fixed-size heap is not generally what you want. It's not good user experience for running ./foo at the command line, for example. The reason for this is that program memory use is usually a function of the program's input, and only in some cases do you know what the input might look like, and until you run the program you don't know what the exact effect of input on memory is. Still, if you have a team of operations people that knows what input patterns look like and has experience with a GC-using server-side process, fixed heap sizes could be a good solution there too.

you: average josé/fina

On the other end of the spectrum is the average user. You just want to run your program. The program should have the memory it needs! Not too much of course; that would be wasteful. Not too little either; I can tell you, my house is less than 100m², and I spend way too much time shuffling things from one surface to another. If I had more space I could avoid this wasted effort, and in a similar way, you don't want to be too stingy with a program's heap. Do the right thing!

Of course, you probably have multiple programs running on a system that are making similar heap sizing choices at the same time, and the relative needs and importances of these programs could change over time, for example as you switch tabs in a web browser, so the right thing really refers to overall system performance, whereas what you are controlling is just one process' heap size; what is the Right Thing, anyway?

My corner of the GC discourse agrees that something like the right solution was outlined by Kirisame, Shenoy, and Panchekha in a 2022 OOPSLA paper, in which the optimum heap size depends on the allocation rate and the gc cost for a process, which you measure on an ongoing basis. Interestingly, their formulation of heap size calculation can be made by each process without coordination, but results in a whole-system optimum.

There are some details but you can imagine some instinctive results: for example, when a program stops allocating because it's waiting for some external event like user input, it doesn't need so much memory, so it can start shrinking its heap. After all, it might be quite a while before the program has new input. If the program starts allocating again, perhaps because there is new input, it can grow its heap rapidly, and might then shrink again later. The mechanism by which this happens is pleasantly simple, and I salute (again!) the authors for identifying the practical benefits that an abstract model brings to the problem domain.

you: a damaged, suspicious individual

Hoo, friends-- I don't know. I've seen some things. Not to exaggerate, I like to think I'm a well-balanced sort of fellow, but there's some suspicion too, right? So when I imagine a background thread determining that my web server hasn't gotten so much action in the last 100ms and that really what it needs to be doing is shrinking its heap, kicking off additional work to mark-compact it or whatever, when the whole point of the virtual machine is to run that web server and not much else, only to have to probably give it more heap 50ms later, I-- well, again, I exaggerate. The MemBalancer paper has a heartbeat period of 1 Hz and a smoothing function for the heap size, but it just smells like danger. Do I need danger? I mean, maybe? Probably in most cases? But maybe it would be better to avoid danger if I can. Heap growth is usually both necessary and cheap when it happens, but shrinkage is never necessary and is sometimes expensive because you have to shuffle around data.

So, I think there is probably a case for a third mode: not fixed, not adaptive like the MemBalancer approach, but just growable: grow the heap when and if its size is less than a configurable multiplier (e.g. 1.5) of live data. Never shrink the heap. If you ever notice that a process is taking too much memory, manually kill it and start over, or whatever. Default to adaptive, of course, but when you start to troubleshoot a high GC overhead in a long-lived proess, perhaps switch to growable to see its effect.

unavoidable badness

There is some heuristic badness that one cannot avoid: even with the adaptive MemBalancer approach, you have to choose a point on the space/time tradeoff curve. Regardless of what you do, your system will grow a hairy nest of knobs and dials, and if your system is successful there will be a lively aftermarket industry of tuning articles: "Are you experiencing poor object transit? One knob you must know"; "Four knobs to heaven"; "It's raining knobs"; "GC engineers DO NOT want you to grab this knob!!"; etc. (I hope that my British readers are enjoying this.)

These ad-hoc heuristics are just part of the domain. What I want to say though is that having a general framework for how you approach heap sizing can limit knob profusion, and can help you organize what you have into a structure of sorts.

At least, this is what I tell myself; inshallah. Now I have told you too. Until next time, happy hacking!

by Andy Wingo at Friday, January 27, 2023

Wednesday, January 25, 2023

Idiomdrottning

Everyone, learn how to code

For once, Internet was good today instead of just a constant bruising source of pain and misery.

I had a fun conversation with akareilly, who wrote:

If you insist that people learn to code in order to use technology, I’m going to insist that you grow your own flax, do the retting, spin it, weave it, and sew it before you’re allowed to wear pants.

Yes, except not ironically. Knowing how to craft and repair clothes is a pretty good thing.

Absolutely! It doesn’t take expensive supplies to start mending, and there are many resources online now.

I am actually capable of doing all of these things using Neolithic tech. Apocalypse skills, sorted.

There are darning looms, tablet weaving supplies, rigid heddle looms, backstrap looms, spinning wheels, knitting machines, knitting belts and pins, sewing machines, and all sorts of things here.

I never worked with textiles professionally, but in school we were taught braiding, carding, spinning, weaving, knitting, darning, and crocheting. This started before we were taught grammar and multiplication. I appreciate being shown those things because it’s good to not get too abstracted from the levers we’re using to interact with the world.

Things like math and logic and writing and physics and drawing and all kinds of things got way easier after I had started learning to code. The same goes for the spiritual or psychological experience. Coding (probably better known as meta-thinking, thinking about thinking) is an amazing foundation for other fields.

(On the other hand I hate modern, commercial tech ���♀�)

We didn’t get fiber arts in school but I was lucky enough to have computers at school and at home.

3-2-1 Contact magazine had BASIC code for games that we typed into a Commodore64. Now there are fun, visual tools to get kids started.

Everyone should have the opportunity to code.

It’s also OK if kids find that boring and do something else.

If you also feel that way about writing, reading, math, politics, history, physics then that’s food for thought for me, I’d have to think about to what extent the grown-up world should insist on teaching things. Interesting dilemma ���♀�

If it’s coding specifically then I’m not onboard.

Kids should have a basic understanding of things that they find boring. With any new skill, there’s a certain level of learning that many people need to reach to know whether they really enjoy it or not. If someone gets to that point and can program something basic, or even reaches professional competence, and decides they don’t like code? That’s fine. The point is to try.

Then, programmers should understand that “can’t be bothered� isn’t “can’t�.

Just like the kids who don’t make all their own clothes. They still get to wear clothes and have preferences.

That’s what I find weird about open source software developers not taking feedback, and responding to any requests with “just fork it�. If you say “OK, stop buying clothes if you don’t like what you have� the answer might be “but I don’t have time to learn this! I wouldn’t have time to code! I could learn but I need to make software instead!�

I hate programming so much 😭

People don’t get that since I’m the world’s best programmer. They’re like “why don’t you program more?� Because I hate it.

As far as open source software developers not taking feedback specifically, I’ve argued against that refusal.

So in that specific fight, I’m with you.

Learning the basics of how code works and how to code simple things is all I’m asking; as you point out, the difference between knowing how it’s constructed vs having the time, resources, skill level to do everything from scratch always.

Code can also be copied so there’s a degree of cooperation and standing on each other’s shoulders that’s possible in code that’s not possible to the same extent in textile.

I thought we were talking about something else. When I’m like “everyone should learn how to code�, it’s not to give credence to your basic GitHub issues sourpuss. I’m with you on that one. Instead, it’s a reaction to the veneer of network path dependent silos like Instagram, Hacker News, Facebook, YouTube, how our infastructure is being gatekept by modern-day Priests of Ra who are stacking their castle walls on layers and layers and layers of abstraction and toolkits, locking everything down and wrapping your basic everyday tools in hard plastic and planned obsolescence. It’s a celebration of how coding can be a foundation for other fields and philosophies, how it can help us reason about our interactions with nature, others, and ourselves. How market capitalism is a broken program and how we need the best minds of our generation to set things straight before we burn the world. 🤷��♀�

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Wednesday, January 25, 2023

Tuesday, January 24, 2023

Andy Wingo

parallel ephemeron tracing

Hello all, and happy new year. Today's note continues the series on implementing ephemerons in a garbage collector.

In our last dispatch we looked at a serial algorithm to trace ephemerons. However, production garbage collectors are parallel: during collection, they trace the object graph using multiple worker threads. Our problem is to extend the ephemeron-tracing algorithm with support for multiple tracing threads, without introducing stalls or serial bottlenecks.

Recall that we ended up having to define a table of pending ephemerons:

struct gc_pending_ephemeron_table {
  struct gc_ephemeron *resolved;
  size_t nbuckets;
  struct gc_ephemeron *buckets[0];
};

This table holds pending ephemerons that have been visited by the graph tracer but whose keys haven't been found yet, as well as a singly-linked list of resolved ephemerons that are waiting to have their values traced. As a global data structure, the pending ephemeron table is a point of contention between tracing threads that we need to design around.

a confession

Allow me to confess my sins: things would be a bit simpler if I didn't allow tracing workers to race.

As background, if your GC supports marking in place instead of always evacuating, then there is a mark bit associated with each object. To reduce the overhead of contention, a common strategy is to actually use a whole byte for the mark bit, and to write to it using relaxed atomics (or even raw stores). This avoids the cost of a compare-and-swap, but at the cost that multiple marking threads might see that an object's mark was unset, go to mark the object, and think that they were the thread that marked the object. As far as the mark byte goes, that's OK because everybody is writing the same value. The object gets pushed on the to-be-traced grey object queues multiple times, but that's OK too because tracing should be idempotent.

This is a common optimization for parallel marking, and it doesn't have any significant impact on other parts of the GC--except ephemeron marking. For ephemerons, because the state transition isn't simply from unmarked to marked, we need more coordination.

high level

The parallel ephemeron marking algorithm modifies the serial algorithm in just a few ways:

  1. We have an atomically-updated state field in the ephemeron, used to know if e.g. an ephemeron is pending or resolved;

  2. We use separate fields for the pending and resolved links, to allow for concurrent readers across a state change;

  3. We introduce "traced" and "claimed" states to resolve races between parallel tracers on the same ephemeron, and track the "epoch" at which an ephemeron was last traced;

  4. We remove resolved ephemerons from the pending ephemeron hash table lazily, and use atomic swaps to pop from the resolved ephemerons list;

  5. We have to re-check key liveness after publishing an ephemeron to the pending ephemeron table.

Regarding the first point, there are four possible values for the ephemeron's state field:

enum {
  TRACED, CLAIMED, PENDING, RESOLVED
};

The state transition diagram looks like this:

  ,----->TRACED<-----.
 ,         | ^        .
,          v |         .
|        CLAIMED        |
|  ,-----/     \---.    |
|  v               v    |
PENDING--------->RESOLVED

With this information, we can start to flesh out the ephemeron object itself:

struct gc_ephemeron {
  uint8_t state;
  uint8_t is_dead;
  unsigned epoch;
  struct gc_ephemeron *pending;
  struct gc_ephemeron *resolved;
  void *key;
  void *value;
};

The state field holds one of the four state values; is_dead indicates if a live ephemeron was ever proven to have a dead key, or if the user explicitly killed the ephemeron; and epoch is the GC count at which the ephemeron was last traced. Ephemerons are born TRACED in the current GC epoch, and the collector is responsible for incrementing the current epoch before each collection.

algorithm: tracing ephemerons

When the collector first finds an ephemeron, it does a compare-and-swap (CAS) on the state from TRACED to CLAIMED. If that succeeds, we check the epoch; if it's current, we revert to the TRACED state: there's nothing to do.

(Without marking races, you wouldn't need either TRACED or CLAIMED states, or the epoch; it would be implicit in the fact that the ephemeron was being traced at all that you had a TRACED ephemeron with an old epoch.)

So now we have a CLAIMED ephemeron with an out-of-date epoch. We update the epoch and clear the pending and resolved fields, setting them to NULL. If, then, the ephemeron is_dead, we are done, and we go back to TRACED.

Otherwise we check if the key has already been traced. If so we forward it (if evacuating) and then trace the value edge as well, and transition to TRACED.

Otherwise we have a live E but we don't know about K; this ephemeron is pending. We transition E's state to PENDING and add it to the front of K's hash bucket in the pending ephemerons table, using CAS to avoid locks.

We then have to re-check if K is live, after publishing E, to account for other threads racing to mark to K while we mark E; if indeed K is live, then we transition to RESOLVED and push E on the global resolved ephemeron list, using CAS, via the resolved link.

So far, so good: either the ephemeron is fully traced, or it's pending and published, or (rarely) published-then-resolved and waiting to be traced.

algorithm: tracing objects

The annoying thing about tracing ephemerons is that it potentially impacts tracing of all objects: any object could be the key that resolves a pending ephemeron.

When we trace an object, we look it up in the pending ephemeron hash table. But, as we traverse the chains in a bucket, we also load each node's state. If we find a node that's not in the PENDING state, we atomically forward its predecessor to point to its successor. This is correct for concurrent readers because the end of the chain is always reachable: we only skip nodes that are not PENDING, nodes never become PENDING after they transition away from being PENDING, and we only add PENDING nodes to the front of the chain. We even leave the pending field in place, so that any concurrent reader of the chain can still find the tail, even when the ephemeron has gone on to be RESOLVED or even TRACED.

(I had thought I would need Tim Harris' atomic list implementation, but it turns out that since I only ever insert items at the head, having annotated links is not necessary.)

If we find a PENDING ephemeron that has K as its key, then we CAS its state from PENDING to RESOLVED. If this works, we CAS it onto the front of the resolved list. (Note that we also have to forward the key at this point, for a moving GC; this was a bug in my original implementation.)

algorithm: resolved ephemerons

Periodically a thread tracing the graph will run out of objects to trace (its mark stack is empty). That's a good time to check if there are resolved ephemerons to trace. We atomically exchange the global resolved list with NULL, and then if there were resolved ephemerons, then we trace their values and transition them to TRACED.

At the very end of the GC cycle, we sweep the pending ephemeron table, marking any ephemeron that's still there as is_dead, transitioning them back to TRACED, clearing the buckets of the pending ephemeron table as we go.

nits

So that's it. There are some drawbacks, for example that this solution takes at least three words per ephemeron. Oh well.

There is also an annoying point of serialization, which is related to the lazy ephemeron resolution optimization. Consider that checking the pending ephemeron table on every object visit is overhead; it would be nice to avoid this. So instead, we start in "lazy" mode, in which pending ephemerons are never resolved by marking; and then once the mark stack / grey object worklist fully empties, we sweep through the pending ephemeron table, checking each ephemeron's key to see if it was visited in the end, and resolving those ephemerons; we then switch to "eager" mode in which each object visit could potentially resolve ephemerons. In this way the cost of ephemeron tracing is avoided for that part of the graph that is strongly reachable. However, with parallel markers, would you switch to eager mode when any thread runs out of objects to mark, or when all threads run out of objects? You would get greatest parallelism with the former, but you run the risk of some workers prematurely running out of data, but when there is still a significant part of the strongly-reachable graph to traverse. If you wait for all threads to be done, you introduce a serialization point. There is a related question of when to pump the resolved ephemerons list. But these are engineering details.

Speaking of details, there are some gnarly pitfalls, particularly that you have to be very careful about pre-visit versus post-visit object addresses; for a semi-space collector, visiting an object will move it, so for example in the pending ephemeron table which by definition is keyed by pre-visit (fromspace) object addresses, you need to be sure to trace the ephemeron key for any transition to RESOLVED, and there are a few places this happens (the re-check after publish, sweeping the table after transitioning from lazy to eager, and when resolving eagerly).

implementation

If you've read this far, you may be interested in the implementation; it's only a few hundred lines long. It took me quite a while to whittle it down!

Ephemerons are challenging from a software engineering perspective, because they are logically a separate module, but they interact both with users of the GC and with the collector implementations. It's tricky to find the abstractions that work for all GC algorithms, whether they mark in place or move their objects, and whether they mark the heap precisely or if there are some conservative edges. But if this is the sort of thing that interests you, voilà the API for users and the API to and from collector implementations.

And, that's it! I am looking forward to climbing out of this GC hole, one blog at a time. There are just a few more features before I can seriously attack integrating this into Guile. Until the next time, happy hacking :)

by Andy Wingo at Tuesday, January 24, 2023

Monday, January 23, 2023

Scheme Requests for Implementation

SRFI 239: Destructuring Lists

SRFI 239 is now in final status.

This SRFI provides the list-case, the syntactic fundamental list destructor.

by Marc Nieper-Wißkirchen at Monday, January 23, 2023

GNU Guix

Meet Guix at FOSDEM

GNU Guix will be present at FOSDEM next week, February 4th and 5th. This is the first time since the pandemic that FOSDEM takes place again “in the flesh” in Brussels, which is exciting to those of us lucky enough to get there! Everything will be live-streamed and recorded thanks to the amazing FOSDEM crew, so everyone can enjoy wherever they are; some of the talks this year will be “remote” too: pre-recorded videos followed by live Q&A sessions with the speaker.

Believe it or not, it’s the 9th year Guix is represented at FOSDEM, with more than 30 talks given in past editions! This year brings several talks that will let you learn more about different areas of the joyful Hydra Guix has become.

This all starts on Saturday, in particular with the amazing declarative and minimalistic computing track:

There are many other exciting talks in this track, some of which closely related to Guix and Guile; check it out!

You can also discover Guix in other tracks:

Guix Days logo

As was the case pre-pandemic, we are also organizing the Guix Days as a FOSDEM fringe event, a two-day Guix workshop where contributors and enthusiasts will meet. The workshop takes place on Thursday Feb. 2nd and Friday Feb. 3rd at the Institute of Cultural Affairs (ICAB) in Brussels.

Again this year there will be few talks; instead, the event will consist primarily of “unconference-style” sessions focused on specific hot topics about Guix, the Shepherd, continuous integration, and related tools and workflows.

Attendance to the workshop is free and open to everyone, though you are invited to register (there are few seats left!). Check out the workshop’s wiki page for registration and practical info. Hope to see you in Brussels!

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, AArch64, and POWER9 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by Ludovic Courtès at Monday, January 23, 2023

Tuesday, January 17, 2023

Jérémy Korwin-Zmijowski

Test driving the development of a testing framework using itself in Guile

Guile Logo

Previously :

My last post was full of errors ! I guess I got lost in the REPL state and faced ghosts, like variables and procedures no more defined… In this post, I give you a new version of the code without errors. You also get a bonus feature : the failing tests are named in the summary. Enjoy ! The steps followed are almost the same as the one in the previous article of this serie. The difference lies in the way I encapsulate everything inside functions : * gunit-test is the function responsible for running the tests. * runner and summary are the functions under test. * gunit-project is the function that ensure my REPL is not relying on the state of old evaluations.

(use-modules ((debugging assert) #:select (assert))
             (ice-9 exceptions))

(define (gunit-project)

  (define* (runner #:key (setup (const #f)) (teardown (const #f)))
    (let ([count (vector 0 0)]
          [failures '()])
      (lambda* (#:rest procs)
        (map
         (lambda (proc)
           (vector-set! count 0 (1+ (vector-ref count 0)))
           (guard (e
                   ((exception? e)
                    (vector-set! count 1 (1+ (vector-ref count 1)))
                    (set! failures (cons (symbol->string (procedure-name proc)) failures))))
             (dynamic-wind setup proc teardown)))
         procs)
        (values count failures))))

  (define (summary count failures)
    (format #f "~A run, ~A failed~A"
            (vector-ref count 0)
            (vector-ref count 1)
            (string-concatenate (map
                                 (lambda (failure)
                                   (format #f "\n- ~A" failure))
                                 failures))))

  
  (define (gunit-test)

    (define log "")
    (define (test-proc) (set! log (string-append log "proc ")))
    (define (test-proc-broken) (raise-exception (make-exception)))
    (define (setup-proc) (set! log (string-append log "setup ")))
    (define (teardown-proc) (set! log (string-append log "teardown ")))
    
    (define (test-template)
      ((runner #:setup setup-proc #:teardown teardown-proc) test-proc)
      (assert (string=? log "setup proc teardown ")))

    (define (test-result)
      (call-with-values (lambda () ((runner) test-proc))
        (lambda (count failures)
          (assert (string=? "1 run, 0 failed" (summary count failures))))))

    (define (test-failed-result)
      (call-with-values (lambda () ((runner) test-proc-broken))
        (lambda (count failures)
          (assert (string=? "1 run, 1 failed\n- test-proc-broken" (summary count failures))))))

    (define (test-suite)
      (call-with-values (lambda () ((runner) test-proc test-proc-broken))
        (lambda (count failures)
          (assert (string=? "2 run, 1 failed\n- test-proc-broken" (summary count failures))))))
    
    (let* ([setup (lambda () (set! log ""))]
           [run (runner #:setup setup)])
      (call-with-values (lambda ()
                          (run test-template
                               test-result
                               test-failed-result
                               test-suite))
        (lambda (count failures)
          (summary count failures)))))

  
  (gunit-test))

(gunit-project)

Thank you very much for reading this article!

Don't hesitate to give me your opinion, suggest an idea for improvement, report an error, or ask a question ! I would be so glad to discuss about the topic covered here with you ! You can reach me here.

Don't miss out on the next ones ! Either via RSS or via e-mail !

And more importantly, share this blog and tell your friends why they should read this post!

#gnu #guile #tdd #book #english

GPG: 036B 4D54 B7B4 D6C8 DA62 2746 700F 5E0C CBB2 E2D1

Tuesday, January 17, 2023

Monday, January 16, 2023

Scheme Requests for Implementation

SRFI 238: Codesets

SRFI 238 is now in final status.

Many programming interfaces rely on a set of condition codes where each code has a numeric ID, a mnemonic symbol, and a human-readable message. This SRFI defines a facility to translate between numbers and symbols in a codeset and to fetch messages by code. Examples are given using the Unix errno and signal codesets.

by Lassi Kortela at Monday, January 16, 2023

Sunday, January 15, 2023

Göran Weinholt

Akku website updates

I have had some free time recently between working for clients, and took this opportunity to implement new features for Akku’s website.

In case you did not know, Akku is a package manager with features specially designed for R6RS and R7RS Scheme.

The library systems in Scheme make it possible to automatically analyze source code to find libraries, exports and imports. Akku combines such analysis with a package index that lets you install packages from the command line, automatically resolving dependencies and placing files in the right place. Dependencies and installed files are project-specific, so you can concentrate on each project separately.

Search box

The top of the page now has a handy search box:

DuckDuckGo site search

It uses DuckDuckGo, which I think is a good balance between privacy and functionality.

At some point it would be good to set up a custom search engine which also searches through all source code.

Who uploaded the package?

Akku has over 500 packages in its index. Many of them have been uploaded by me personally when I initially set up the archive. Packaging is really simple due to the automatic analysis built-in to Akku, so when packaging something new I just needed to read through the code to see that nothing bad was going on, then add the required dependencies and write a description.

The package uploader is identified through their OpenPGP signature on the uploaded package at https://archive.akkuscm.org/archive/packages/. The website generator uses this signature to figure out who uploaded the package and shows their name if it is different from the (single) package author.

Authors box showing an uploader's name

There’s an exception for packages mirrored from Snow. Those are all signed by me anyway, as there is no way to directly upload a Snow package to Akku. Those all have to go through snow-fort.org first.

Anyone can upload packages to Akku’s archive, so if you find some cool R6RS project that’s missing in Akku then you can go ahead and upload it. See the man page for instructions. (If you want to upload a new version of a package that already exists then that’s okay too, but if the author themselves uploaded the previous version then please check with them first).

Before packages are published in the archive they are manually reviewed to verify that they’re not up to any funny business. I think this is the only way to truly prevent the attacks that regularly happen to the larger package repositories for other languages. The work is manageable today and if Akku gets more popular then it should still be sustainable with increased automation to help with the tedious parts of the manual review.

Where do I get that library?

If you have some Scheme code in front of you that imports a library then you might like to find the package that contains it. There is now a new page with just such an index:

Image showing the Libraries page

The index is still small enough that everything fits on one page. On the left you see libraries, which are tagged as R6RS libraries, R7RS libraries or implementation-specific modules. On the right you see which packages contain the library.

A library can exist in multiple packages, so you will see some libraries with links to multiple packages. When Akku encounters this situation it is the order of the dependencies in Akku.manifest that determines which variant “wins”: dependencies can overwrite files from dependencies specified earlier in the list.

Image shows the (sdl2) package on the libraries page

Who exports this identifier?

Akku’s archive also has information about what identifiers are exported by each library, so I have made a page where you can look for identifiers and find the relevant libraries and packages.

Image showing the packages export "fail", etc

I’m not too happy about the usability of this page, and ideas for improvements are very welcome. I tried putting it all on one page, thinking that at least then you can search in the browser, but Mr. Browser got slow and the page was 11MB. So instead there’s an awkward split into multiple pages. It should however make search engines happy, and that’s good enough for now.

What’s in the package?

Akku’s analyzer knows what is in each package and the archive software has been publishing this information for some time, but it has never been visualized before. The only information you got on the website was a synopsis, a list of authors, maybe a description and a reference to the source code.

Package contents of the spdx package

The new “Package contents” box lists all libraries and modules that are found in the package. The first row under each library name is the list of exported identifiers, followed by one row for each imported library. Meta-information is added to the rows, like a little tag showing if it’s an R6RS library, an R7RS library, or an implementation-specified module format.

A library name can show up multiple times if there are implementation-specific variants, e.g., one variant for Chez Scheme and another one for Chibi-Scheme. This is also shown with a little tag on the package name.

SRFI library names are linked to the relevant page on https://srfi.schemers.org. This type of linking is something that should be expanded on later, but for now that’s the only type of link you will see on a library.

I think this type of information adds a lot to the package pages. You get a deeper insight into what libraries there are, what libraries they use, and you can quickly see if the package is missing library variants for your Scheme implementation. An example is the wak-common package and its (wak private include compat) library, which exists only for Chez Scheme, GNU Guile, Ikarus, Mosh, Racket and Ypsilon. However, if you look in the library index then you can see that the akku package also has a variant of this library for Loko Scheme.

Future work

There is more I would like to add to the web site, and they are not such small projects:

  • Documentation. Some packages have proper documentation and it would be good to link to this. It might require an update to Akku’s package format so that it will be built properly, e.g., if there are PDFs to generate. It’s also common for other languages to have automatically extracted documentation from comments, but today there is no wide-spread tool for Scheme that does this.

  • Test reports. Many packages have automatic test suites, but Akku does nothing with them at the moment. An even simpler test would be to just try importing each library in each Scheme and see if that works.

Suggestions and merge requests are welcome at the website’s project page: https://gitlab.com/akkuscm/akku-web.

by weinholt at Sunday, January 15, 2023

Friday, January 6, 2023

GNU Guix

The Filesystem Hierarchy Standard Comes to Guix Containers

GNU Guix is different from most other GNU/Linux distributions and perhaps nowhere is that more obvious than the organization of the filesystem: Guix does not conform to the Filesystem Hierarchy Standard (FHS). In practical terms, this means there is no global /lib containing libraries, /bin containing binaries,¹ and so on. This is very much at the core of how Guix works and some of the convenient features, like per-user installation of programs (different versions, for instance) and a declarative system configuration where the system is determined from a configuration file.

However, this also leads to a difference in how many pieces of software expect their world to look like, relying on finding a library in /lib or an external tool in /bin. When these are hard coded and not overcome with appropriate build options, we patch code to refer to absolute paths in the store, like /gnu/store/hrgqa7m498wfavq4awai3xz86ifkjxdr-grep-3.6/bin/grep, to keep everything consistently contained within the store.

It all works great and is thanks to the hard work of everyone that has contributed to Guix. But what if we need a more FHS-like environment for developing, testing, or running a piece of software?

To that end, we've recently added (available in Guix 1.4.0) a new option for guix shell (previously called guix environment): --emulate-fhs (or -F). This option is used in conjunction with the --container (or -C) option which creates an isolated, you guessed it, container. The new --emulate-fhs option will set up an environment in the container that follows FHS expectations, so that libraries are visible in /lib in the container, as an example.

Here is a very simple example:

$ guix shell --container --emulate-fhs coreutils -- ls /bin | head
[
b2sum
base32
base64
basename
basenc
cat
catchsegv
chcon
chgrp

and

$ guix shell --container --emulate-fhs coreutils -- ls /lib | head
Mcrt1.o
Scrt1.o
audit
crt1.o
crti.o
crtn.o
gconv
gcrt1.o
ld-2.33.so
ld-linux-x86-64.so.2

Contrast that with /bin on a Guix system:

$ ls /bin -l

total 4
lrwxrwxrwx 1 root root  61 Dec 12 09:57 sh -> \
    /gnu/store/d99ykvj3axzzidygsmdmzxah4lvxd6hw-bash-5.1.8/bin/sh*

and /lib

$ ls /lib
ls: cannot access '/lib': No such file or directory

Or, if you like to see it more in motion, here's a gif (courtesy of Ludovic Courtès): An animated gif showing the above 'guix shell' output.

Additionally, for the more technically-minded, the glibc used in this container will read from a global cache in /etc/ld.so.cache contrary to the behavior in Guix otherwise. This can help ensure that libraries are found when querying the ld cache or using the output of ldconfig -p, for example.

There are several uses that spring to mind for such a container in Guix. For developers, or those aspiring to hack on a project, this is a helpful tool when needing to emulate a different (non-Guix) environment. For example, one could use this to more easily follow build instructions meant for a general distribution, say when a Guix package is not (yet) available or easy to write immediately.

Another usage is to be able to use tools that don't really fit into Guix's model, like ones that use pre-built binaries. There are many reasons why this is not ideal and Guix strives to replace or supplement such tools, but practically speaking they can be hard to avoid entirely. The FHS container helps bridge this gap, providing an isolated and reproducible environment as needed.

Users not interested in development will also find the FHS container useful. For example, there may be software that is free and conforms to the Free System Distribution Guidelines (FSDG) Guix follows, yet is not feasible to be packaged by our standards. JavaScript and particularly Electron applications are not yet packaged for Guix due to the difficulties of a properly source-based and bootstrapable approach in this ecosystem.

As a more interesting example for this last point, let's dive right into a big one: the popular VSCodium editor. This is a freely licensed build of Microsoft's VS Code editor. This is based on Electron and pre-built AppImages are available. Downloading and making the AppImage executable (with a chmod +x), we can run it in a container with

guix shell --container --network --emulate-fhs \
    --development ungoogled-chromium gcc:lib \
    --preserve='^DISPLAY$' --preserve='^XAUTHORITY$' --expose=$XAUTHORITY \
    --preserve='^DBUS_' --expose=/var/run/dbus \
    --expose=/sys/dev --expose=/sys/devices --expose=/dev/dri \
    -- ./VSCodium-1.74.0.22342.glibc2.17-x86_64.AppImage --appimage-extract-and-run

The second line is a handy cheat to get lots of libraries often needed for graphical applications (development inputs of the package ungoogled-chromium) though it can be overkill if the AppImage does actually bundle everything (they don't!). The next line is for display on the host's X server, the one after for DBus communication, and lastly exposing some of the host hardware for rendering. This last part may be different on different hardware. That should do it, at least to see basic functionality of VSCodium. Note that we can't run an AppImage without the --appimage-extract-and-run option as it will want to use FUSE to mount the image which is not possible from the container.²

The FHS container is also useful to be able to run the exact same binary as anyone else, as you might want to for privacy reasons with the Tor Browser. While there is a long-standing set of patches to build the Tor Browser from source, with a container we can run the official build directly. After downloading, checking the signature, and unpacking, we can launch the Tor Browser from the root of the unpacked directory with:

guix shell --container --network --emulate-fhs \
    --preserve='^DISPLAY$' --preserve='^XAUTHORITY$' --expose=$XAUTHORITY \
    alsa-lib bash coreutils dbus-glib file gcc:lib \
    grep gtk+ libcxx pciutils sed \
    -- ./start-tor-browser.desktop -v

Here we've used a more minimal set of package inputs, rather than the ungoogled-chromium trick above. Usually this is found through some trial and error, looking at log output, maybe tracing, and sometimes from documentation. Though documentation of needed packages often has some assumptions on what is already available on typical systems. (Thanks to Jim Newsome for pointing out this example on the guix-devel mailing list.)

Another example is to get the latest nightly builds of Rust, via rustup.

$ mkdir ~/temphome

$ guix shell --network --container --emulate-fhs \
    bash coreutils curl grep nss-certs gcc:lib gcc-toolchain \
    pkg-config glib cairo atk pango@1.48.10 gdk-pixbuf gtk+ git \
    --share=$HOME/temphome=$HOME

~/temphome [env]$ curl --proto '=https' --tlsv1.2 -sSf <https://sh.rustup.rs> | sh

First we created a ~/temphome directory to use as $HOME in the container and then included a bunch of libraries in the container for the next example.

This will proceed without problem and we'll see

info: downloading installer

Welcome to Rust!

This will download and install the official compiler for the Rust
programming language, and its package manager, Cargo.

...

Rust is installed now. Great!

To get started you may need to restart your current shell.
This would reload your PATH environment variable to include
Cargo's bin directory ($HOME/.cargo/bin).

To configure your current shell, run:
source "$HOME/.cargo/env"

After updating the shells environment as instructed, we can see it all worked

~/temphome [env]$ rustc --version
rustc 1.65.0 (897e37553 2022-11-02)

as Guix's current Rust is at 1.61.0 and we didn't even include Rust in the container, of course.

Finally, we can build a Rust project of desktop widgets, ElKowars wacky widgets (eww), following their directions. Ultimately this uses just the standard cargo build --release and builds after downloading all the needed libraries.

~/temphome/eww [env]$ git clone https://github.com/elkowar/eww
...
~/temphome/eww [env]$ cd eww

~/temphome/eww [env]$ cargo build --release
info: syncing channel updates for 'nightly-2022-08-27-x86_64-unknown-linux-gnu'
info: latest update on 2022-08-27, rust version 1.65.0-nightly (c07a8b4e0 2022-08-26)
...

Finished release [optimized] target(s) in 2m 06s

With this being a fresh container, you will need to make some directories that normally exist, like ~/.config and ~/.cache in this case. For basic display support, it is enough to add --preserve='^DISPLAY$' --preserve='^XAUTHORITY$' --expose=$XAUTHORITY to the container launch options and run the first example widget in the documentation.

As we can see, with containers more generally we have to provide the right inputs and options as the environment is completely specified at creation. Once you want to run something that needs hardware from the host or to access host files, the container becomes increasingly porous for more functionality. This is certainly a trade-off, but one which we have agency with a container we wouldn't get otherwise.

The FHS option provides another option to make a container in Guix to produce other environments, even those with a vastly different philosophy of the root filesystem! This is one more tool in the Guix toolbox for controlled and reproducible environments that also let's us do some things we couldn't (easily) do otherwise.

Notes

¹ Other than a symlink for sh from the bash package, for compatibility reasons.

² Actually, one can use flatpak-spawn from flatpak-xdg-utils to launch something on the host and get the AppImage to mount itself. However, it is not visible from the same container. Or, we can use a normal mounting process outside of the container to inspect the contents, but AppImages will have an offset. We can use the FHS container option to get this offset and then mount in one line with mount VSCodium-1.74.0.22342.glibc2.17-x86_64.AppImage <mountpoint> -o offset=$(guix shell --container --emulate-fhs zlib -- ./VSCodium-1.74.0.22342.glibc2.17-x86_64.AppImage --appimage-offset)

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, AArch64, and POWER9 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by John Kehayias at Friday, January 6, 2023

Wednesday, January 4, 2023

GNU Guix

Dissecting Guix, Part 1: Derivations

To a new user, Guix's functional architecture can seem quite alien, and possibly offputting. With a combination of extensive #guix-querying, determined manual-reading, and plenty of source-perusing, they may eventually figure out how everything fits together by themselves, but this can be frustrating and often takes a fairly long time.

However, once you peel back the layers, the "Nix way" is actually rather elegant, if perhaps not as simple as the mutable, imperative style implemented by the likes of dpkg and pacman. This series of blog posts will cover basic Guix concepts, taking a "ground-up" approach by dealing with lower-level concepts first, and hopefully make those months of information-gathering unnecessary.

Before we dig in to Guix-specific concepts, we'll need to learn about one inherited from Nix, the original functional package manager and the inspiration for Guix; the idea of a derivation and its corresponding store items.

These concepts were originally described by Eelco Dolstra, the original author of Nix, in their PhD thesis; see ยง 2.1 The Nix store and ยง 2.4 Store Derivations.

Store Items

As you probably know, everything that Guix builds is stored in the store, which is almost always the /gnu/store directory. It's the job of the guix-daemon to manage the store and build things. If you run guix build PKG, PKG will be built or downloaded from a substitute server if available, and a path to an item in the store will be displayed.

$ guix build irssi
/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3

This item contains the final result of building irssi. Let's peek inside:

$ ls $(guix build irssi)
bin/  etc/  include/  lib/  share/
$ ls $(guix build irssi)/bin
irssi*

irssi is quite a simple package. What about a more complex one, like glib?

$ guix build glib
/gnu/store/bx8qq76idlmjrlqf1faslsq6zjc6f426-glib-2.73.3-bin
/gnu/store/j65bhqwr7qq7l77nj0ahmk1f1ilnjr3a-glib-2.73.3-debug
/gnu/store/3pn4ll6qakgfvfpc4mw89qrrbsgj3jf3-glib-2.73.3-doc
/gnu/store/dvsk6x7d26nmwsqhnzws4iirb6dhhr1d-glib-2.73.3
/gnu/store/4c8ycz501n2d0xdi4blahvnbjhd5hpa8-glib-2.73.3-static

glib produces five /gnu/store items, because it's possible for a package to produce multiple outputs. Each output can be referred to separately, by prefixing a package's name with :OUTPUT where supported. For example, this guix install invocation will add glib's bin output to your profile:

$ guix install glib:bin

The default output is out, so when you pass glib by itself to that command, it will actually install glib:out to the profile.

guix build also provides the --source flag, which produces the store item corresponding to the given package's downloaded source code.

$ guix build --source irssi
/gnu/store/cflbi4nbak0v9xbyc43lamzl4a539hhb-irssi-1.4.3.tar.xz
$ guix build --source glib
/gnu/store/d22wzjq3xm3q8hwnhbgk2xd3ph7lb6ay-glib-2.73.3.tar.xz

But how does Guix know how to build these store outputs in the first place? That's where derivations come in.

.drv Files

You've probably seen these being printed by the Guix program now and again. Derivations, represented in the daemon's eyes by .drv files, contain instructions for building store items. We can retrieve the paths of these .drv files with the guix build --derivations command:

$ guix build --derivations irssi
/gnu/store/zcgmhac8r4kdj2s6bcvcmhh4k35qvihx-irssi-1.4.3.drv

guix build can actually also accept derivation paths as an argument, in lieu of a package, like so:

$ guix build /gnu/store/zcgmhac8r4kdj2s6bcvcmhh4k35qvihx-irssi-1.4.3.drv
/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3

Let's look inside this derivation file.

Derive([("out","/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3","","")],[("/gnu/store/9mv9xg4kyj4h1cvsgrw7b9x34y8yppph-glib-2.70.2.drv",["out"]),("/gnu/store/baqpbl4wck7nkxrbyc9nlhma7kq5dyfl-guile-2.0.14.drv",["out"]),("/gnu/store/bfirgq65ndhf63nn4q6vlkbha9zd931q-openssl-1.1.1l.drv",["out"]),("/gnu/store/gjwpqzvfhz13shix6a6cs2hjc18pj7wy-module-import-compiled.drv",["out"]),("/gnu/store/ij8651x4yh53hhcn6qw2644nhh2s8kcn-glib-2.70.2.drv",["out"]),("/gnu/store/jg2vv6yc2yqzi3qzs82dxvqmi5k21lhy-irssi-1.4.3.drv",["out"]),("/gnu/store/qggpjl9g6ic3cq09qrwkm0dfsdjf7pyr-glibc-utf8-locales-2.33.drv",["out"]),("/gnu/store/zafabw13yyhz93jwrcz7axak1kn1f2cx-openssl-1.1.1s.drv",["out"])],["/gnu/store/af18nrrsk98c5a71h3fifnxg1zi5mx7y-module-import","/gnu/store/qnrwmby5cwqdqxyiv1ga6azvakmdvgl7-irssi-1.4.3-builder"],"x86_64-linux","/gnu/store/hnr4r2d0h0xarx52i6jq9gvsrlc3q81a-guile-2.0.14/bin/guile",["--no-auto-compile","-L","/gnu/store/af18nrrsk98c5a71h3fifnxg1zi5mx7y-module-import","-C","/gnu/store/6rkkvvb7pl1l9ng8vvywvwf357vhm3va-module-import-compiled","/gnu/store/qnrwmby5cwqdqxyiv1ga6azvakmdvgl7-irssi-1.4.3-builder"],[("allowSubstitutes","0"),("guix properties","((type . graft) (graft (count . 2)))"),("out","/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3"),("preferLocalBuild","1")])

It's... not exactly human-readable. We could try to format it and break it down, but it'd still be pretty hard to understand, since .drv files contain no labels for the fields or any other human-readable indicators. Instead, we're going to explore derivations in a Guile REPL.

Exploring Guix Interactively

Before we continue, we'll want to start a REPL, so that we can try out the Guix Guile API interactively. To run a REPL in the terminal, simply call guix repl.

If you're using Emacs, you can instead install Geiser, which provides a comfortable Emacs UI for various Lisp REPLs, invoke guix repl --listen=tcp:37146 &, and type M-x geiser-connect RET RET RET to connect to the running Guile instance.

Your .guile file may contain code for enabling colours and readline bindings that Geiser will choke on. The default Guix System .guile contains code to suppress these features when INSIDE_EMACS is set, so you'll need to run guix repl like this:

INSIDE_EMACS=1 guix repl --listen=tcp:37146 &

There are a few Guix modules we'll need. Run this Scheme code to import them:

(use-modules (guix)
             (guix derivations)
             (guix gexp)
             (guix packages)
             (guix store)
             (gnu packages glib)
             (gnu packages irc))

We now have access to the store, G-expression, package, and derivation APIs, along with the irssi and glib <package> objects.

Creating a <derivation>

The Guix API for derivations revolves around the <derivation> record, which is the Scheme representation of that whole block of text surrounded by Derive(...). If we look in guix/derivations.scm, we can see that it's defined like this:

(define-immutable-record-type <derivation>
  (make-derivation outputs inputs sources system builder args env-vars
                   file-name)
  derivation?
  (outputs  derivation-outputs)      ; list of name/<derivation-output> pairs
  (inputs   derivation-inputs)       ; list of <derivation-input>
  (sources  derivation-sources)      ; list of store paths
  (system   derivation-system)       ; string
  (builder  derivation-builder)      ; store path
  (args     derivation-builder-arguments)         ; list of strings
  (env-vars derivation-builder-environment-vars)  ; list of name/value pairs
  (file-name derivation-file-name))               ; the .drv file name

With the exception of file-name, each of those fields corresponds to a field in the Derive(...) form. Before we can examine them, though, we need to figure out how to lower that irssi <package> object into a derivation.

guix repl provides the ,lower command to create derivations quickly, as shown in this sample REPL session:

scheme@(guile-user)> ,use (guix)
scheme@(guile-user)> ,use (gnu packages irc)
scheme@(guile-user)> irssi
$1 = #<package irssi@1.4.3 gnu/packages/irc.scm:153 7f3ff98e0c60>
scheme@(guile-user)> ,lower irssi
$2 = #<derivation /gnu/store/drjfddvlblpr635jazrg9kn5azd9hsbj-irssi-1.4.3.drv => /gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3 7f3ff7782d70>
;; Below we use the $N variable automatically bound by the REPL.
scheme@(guile-user)> (derivation-system $2)
$3 = "x86_64-linux"

Since ,lower is a REPL command, however, we can't use it in proper Scheme code. It's quite useful for exploring specific derivations interactively, but since the purpose of this blog post is to explain how things work inside, we're going to use the pure-Scheme approach here.

The procedure we need to use to turn a high-level object like <package> into a derivation is called lower-object; more on that in a future post. However, this doesn't initially produce a derivation:

(pk (lower-object irssi))
;;; (#<procedure 7fe17c7af540 at guix/store.scm:1994:2 (state)>)

pk is an abbreviation for the procedure peek, which takes the given object, writes a representation of it to the output, and returns it. It's especially handy when you want to view an intermediate value in a complex expression.

The returned object is a monadic value (more on those in the next post on monads) that needs to be evaluated in the context of a store connection. We do this by first using with-store to connect to the store and bind the connection to a name, then wrapping the lower-object call with run-with-store:

(define irssi-drv
  (pk (with-store %store
        (run-with-store %store
          (lower-object irssi)))))
;;; (#<derivation /gnu/store/zcgmhac8r4kdj2s6bcvcmhh4k35qvihx-irssi-1.4.3.drv => /gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3 7fe1902b6140>)

(define glib-drv
  (pk (with-store %store
        (run-with-store %store
          (lower-object glib)))))
;;; (#<derivation /gnu/store/81qqs7xah2ln39znrji4r6xj85zi15bi-glib-2.70.2.drv => /gnu/store/lp7k9ygvpwxgxjvmf8bix8d2aar0azr7-glib-2.70.2-bin /gnu/store/22mkp8cr6rxg6w8br9q8dbymf51b44m8-glib-2.70.2-debug /gnu/store/a6qb5arvir4vm1zlkp4chnl7d8qzzd7x-glib-2.70.2 /gnu/store/y4ak268dcdwkc6lmqfk9g1dgk2jr9i34-glib-2.70.2-static 7fe17ca13b90>)

And we have liftoff! Now we've got two <derivation> records to play with.

Exploring <derivation>

<derivation-output>

The first "argument" in the .drv file is outputs, which tells the Guix daemon about the outputs that this build can produce:

(define irssi-outputs
  (pk (derivation-outputs irssi-drv)))
;;; ((("out" . #<<derivation-output> path: "/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3" hash-algo: #f hash: #f recursive?: #f>)))

(pk (assoc-ref irssi-outputs "out"))

(define glib-outputs
  (pk (derivation-outputs glib-drv)))
;;; ((("bin" . #<<derivation-output> path: "/gnu/store/lp7k9ygvpwxgxjvmf8bix8d2aar0azr7-glib-2.70.2-bin" hash-algo: #f hash: #f recursive?: #f>) ("debug" . #<<derivation-output> path: "/gnu/store/22mkp8cr6rxg6w8br9q8dbymf51b44m8-glib-2.70.2-debug" hash-algo: #f hash: #f recursive?: #f>) ("out" . #<<derivation-output> path: "/gnu/store/a6qb5arvir4vm1zlkp4chnl7d8qzzd7x-glib-2.70.2" hash-algo: #f hash: #f recursive?: #f>) ("static" . #<<derivation-output> path: "/gnu/store/y4ak268dcdwkc6lmqfk9g1dgk2jr9i34-glib-2.70.2-static" hash-algo: #f hash: #f recursive?: #f>)))

(pk (assoc-ref glib-outputs "bin"))
;;; (#<<derivation-output> path: "/gnu/store/lp7k9ygvpwxgxjvmf8bix8d2aar0azr7-glib-2.70.2-bin" hash-algo: #f hash: #f recursive?: #f>)

It's a simple association list mapping output names to <derivation-output> records, and it's equivalent to the first "argument" in the .drv file:

[ ("out", "/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3", "", "")
]

The hash-algo and hash fields are for storing the content hash and the algorithm used with that hash for what we term a fixed-output derivation, which is essentially a derivation where we know what the hash of the content will be in advance. For instance, origins produce fixed-output derivations:

(define irssi-src-drv
  (pk (with-store %store
        (run-with-store %store
          (lower-object (package-source irssi))))))
;;; (#<derivation /gnu/store/mcz3vzq7lwwaqjb8dy7cd69lvmi6d241-irssi-1.4.3.tar.xz.drv => /gnu/store/cflbi4nbak0v9xbyc43lamzl4a539hhb-irssi-1.4.3.tar.xz 7fe17b3c8d70>)

(define irssi-src-outputs
  (pk (derivation-outputs irssi-src-drv)))
;;; ((("out" . #<<derivation-output> path: "/gnu/store/cflbi4nbak0v9xbyc43lamzl4a539hhb-irssi-1.4.3.tar.xz" hash-algo: sha256 hash: #vu8(185 63 113 82 35 163 34 230 127 66 182 26 8 165 18 174 41 227 75 212 165 61 127 34 55 102 102 10 170 90 4 52) recursive?: #f>)))
  
(pk (assoc-ref irssi-src-outputs "out"))
;;; (#<<derivation-output> path: "/gnu/store/cflbi4nbak0v9xbyc43lamzl4a539hhb-irssi-1.4.3.tar.xz" hash-algo: sha256 hash: #vu8(185 63 113 82 35 163 34 230 127 66 182 26 8 165 18 174 41 227 75 212 165 61 127 34 55 102 102 10 170 90 4 52) recursive?: #f>)

Note how the hash and hash-algo now have values.

Perceptive readers may note that the <derivation-output> has four fields, whereas the tuple in the .drv file only has three (minus the label). The serialisation of recursive? is done by adding the prefix r: to the hash-algo field, though its actual purpose is difficult to explain, and is out of scope for this post.

<derivation-input>

The next field is inputs, which corresponds to the second field in the .drv file format:

[ ("/gnu/store/9mv9xg4kyj4h1cvsgrw7b9x34y8yppph-glib-2.70.2.drv", ["out"]),
  ("/gnu/store/baqpbl4wck7nkxrbyc9nlhma7kq5dyfl-guile-2.0.14.drv", ["out"]),
  ("/gnu/store/bfirgq65ndhf63nn4q6vlkbha9zd931q-openssl-1.1.1l.drv", ["out"]),
  ("/gnu/store/gjwpqzvfhz13shix6a6cs2hjc18pj7wy-module-import-compiled.drv", ["out"]),
  ("/gnu/store/ij8651x4yh53hhcn6qw2644nhh2s8kcn-glib-2.70.2.drv", ["out"]),
  ("/gnu/store/jg2vv6yc2yqzi3qzs82dxvqmi5k21lhy-irssi-1.4.3.drv", ["out"]),
  ("/gnu/store/qggpjl9g6ic3cq09qrwkm0dfsdjf7pyr-glibc-utf8-locales-2.33.drv", ["out"]),
  ("/gnu/store/zafabw13yyhz93jwrcz7axak1kn1f2cx-openssl-1.1.1s.drv", ["out"])
]

Here, each tuple specifies a derivation that needs to be built before this derivation can be built, and the outputs of the derivation that the build process of this derivation uses. Let's grab us the Scheme equivalent:

(define irssi-inputs
  (pk (derivation-inputs irssi-drv)))
;;; [a fairly large amount of output]

(pk (car irssi-inputs))
;;; (#<<derivation-input> drv: #<derivation /gnu/store/9mv9xg4kyj4h1cvsgrw7b9x34y8yppph-glib-2.70.2.drv => /gnu/store/2jj2mxn6wfrcw7i85nywk71mmqbnhzps-glib-2.70.2 7fe1902b6640> sub-derivations: ("out")>)

Unlike derivation-outputs, derivation-inputs maps 1:1 to the .drv form; the drv field is a <derivation> to be built, and the sub-derivations field is a list of outputs.

Builder Configuration

The other fields are simpler; none of them involve new records. The third is derivation-sources, which contains a list of all store items used in the build which aren't themselves built using derivations, whereas derivation-inputs contains the dependencies which are.

This list usually just contains the path to the Guile build script that realises the store items when run, which we'll examine in a later post, and the path to a directory containing extra modules to add to the build script's %load-path, called /gnu/store/...-module-import.

The next field is derivation-system, which specifies the system type (such as x86_64-linux) we're building for. Then we have derivation-builder, pointing to the guile executable that runs the build script; and the second-to-last is derivation-builder-arguments, which is a list of arguments to pass to derivation-builder. Note how we use -L and -C to extend the Guile %load-path and %load-compiled-path to include the module-import and module-import-compiled directories:

(pk (derivation-system irssi-drv))
;;; ("x86_64-linux")

(pk (derivation-builder irrsi-drv))
;;; ("/gnu/store/hnr4r2d0h0xarx52i6jq9gvsrlc3q81a-guile-2.0.14/bin/guile")

(pk (derivation-builder-arguments irrsi-drv))
;;; (("--no-auto-compile" "-L" "/gnu/store/af18nrrsk98c5a71h3fifnxg1zi5mx7y-module-import" "-C" "/gnu/store/6rkkvvb7pl1l9ng8vvywvwf357vhm3va-module-import-compiled" "/gnu/store/qnrwmby5cwqdqxyiv1ga6azvakmdvgl7-irssi-1.4.3-builder"))

The final field contains a list of environment variables to set before we start the build process:

(pk (derivation-builder-environment-vars irssi-drv))
;;; ((("allowSubstitutes" . "0") ("guix properties" . "((type . graft) (graft (count . 2)))") ("out" . "/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3") ("preferLocalBuild" . "1")))

The last record field, derivation-file-name contains the path to the .drv file, and so isn't represented in a serialised derivation.

Utilising <derivation>

Speaking of serialisation, to convert between the .drv text format and the Scheme <derivation> record, you can use write-derivation, read-derivation, and read-derivation-from-file:

(define manual-drv
  (with-store %store
    (derivation %store "manual"
                "/bin/sh" '())))

(write-derivation manual-drv (current-output-port))
;;; -| Derive([("out","/gnu/store/kh7fais2zab22fd8ar0ywa4767y6xyak-example","","")],[],[],"x86_64-linux","/bin/sh",[],[("out","/gnu/store/kh7fais2zab22fd8ar0ywa4767y6xyak-example")])

(pk (read-derivation-from-file (derivation-file-name irssi-drv)))
;;; (#<derivation /gnu/store/zcgmhac8r4kdj2s6bcvcmhh4k35qvihx-irssi-1.4.3.drv => /gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3 7fb3798788c0>)

(call-with-input-file (derivation-file-name irssi-drv)
  read-derivation)
;;; (#<derivation /gnu/store/zcgmhac8r4kdj2s6bcvcmhh4k35qvihx-irssi-1.4.3.drv => /gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3 7fb37ad19e10>)

You can realise <derivation>s as store items using the build-derivations procedure:

(use-modules (ice-9 ftw))

(define irssi-drv-out
  (pk (derivation-output-path
       (assoc-ref (derivation-outputs irssi-drv) "out"))))
;;; ("/gnu/store/v5pd69j3hjs1fck4b5p9hd91wc8yf5qx-irssi-1.4.3")

(pk (scandir irssi-drv-out))
;;; (#f)

(pk (with-store %store (build-derivations %store (list irssi-drv))))
;;; (#t)

(pk (scandir irssi-drv-out))
;;; (("." ".." "bin" "etc" "include" "lib" "share"))

Conclusion

Derivations are one of Guix's most important concepts, but are fairly easy to understand once you get past the obtuse .drv file format. They provide the Guix daemon with the initial instructions that it uses to build store items like packages, origins, and other file-likes such as computed-file and local-file, which will be discussed in a future post!

To recap, a derivation contains the following fields:

  1. derivation-outputs, describing the various output paths that the derivation builds
  2. derivation-inputs, describing the other derivations that need to be built before this one is
  3. derivation-sources, listing the non-derivation store items that the derivation depends on
  4. derivation-system, specifying the system type a derivation will be compiled for
  5. derivation-builder, the executable to run the build script with
  6. derivation-builder-arguments, arguments to pass to the builder
  7. derivation-builder-environment-vars, variables to set in the builder's environment

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, AArch64 and POWER9 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by ( at Wednesday, January 4, 2023

Wednesday, December 28, 2022

Jeremy Kun

Estimating the Security of Ring Learning with Errors (RLWE)

This article was written by my colleague, Cathie Yun. Cathie is an applied cryptographer and security engineer, currently working with me to make fully homomorphic encryption a reality at Google. She’s also done a lot of cool stuff with zero knowledge proofs.


In previous articles, we’ve discussed techniques used in Fully Homomorphic Encryption (FHE) schemes. The basis for many FHE schemes, as well as other privacy-preserving protocols, is the Learning With Errors (LWE) problem. In this article, we’ll talk about how to estimate the security of lattice-based schemes that rely on the hardness of LWE, as well as its widely used variant, Ring LWE (RLWE).

A previous article on modulus switching introduced LWE encryption, but as a refresher:

Reminder of LWE

A literal repetition from the modulus switching article. The LWE encryption scheme I’ll use has the following parameters:

  • A plaintext space $\mathbb{Z}/q\mathbb{Z}$, where $q \geq 2$ is a positive integer. This is the space that the underlying message comes from.
  • An LWE dimension $n \in \mathbb{N}$.
  • A discrete Gaussian error distribution $ D$ with a mean of zero and a fixed standard deviation.

An LWE secret key is defined as a vector in $\{0, 1\}^n$ (uniformly sampled). An LWE ciphertext is defined as a vector $a = (a_1, \dots, a_n)$, sampled uniformly over $(\mathbb{Z} / q\mathbb{Z})^n$, and a scalar $b = \langle a, s \rangle + m + e$, where $e$ is drawn from $D$ and all arithmetic is done modulo $q$. Note that $e$ must be small for the encryption to be valid.

Learning With Errors (LWE) security

Choosing appropriate LWE parameters is a nontrivial challenge when designing and implementing LWE based schemes, because there are conflicting requirements of security, correctness, and performance. Some of the parameters that can be manipulated are the LWE dimension $n$, error distribution $D$ (referred to in the next few sections as $X_e$), secret distribution $X_s$, and plaintext modulus $q$.

Lattice Estimator

Here is where the Lattice Estimator tool comes to our assistance! The lattice estimator is a Sage module written by a group of lattice cryptography researchers which estimates the concrete security of Learning with Errors (LWE) instances.

For a given set of LWE parameters, the Lattice Estimator calculates the cost of all known efficient lattice attacks – for example, the Primal, Dual, and Coded-BKW attacks. It returns the estimated number of “rops” or “ring operations” required to carry out each attack; the attack that is the most efficient is the one that determines the security parameter. The bits of security for the parameter set can be calculated as $\log_2(\text{rops})$ for the most efficient attack.

Running the Lattice Estimator

For example, let’s estimate the security of the security parameters originally published for the popular TFHE scheme:

n = 630
q = 2^32
Xs = UniformMod(2)
Xe = DiscreteGaussian(stddev=2^17)

After installing the Lattice Estimator and sage, we run the following commands in sage:

> from estimator import *
> schemes.TFHE630
LWEParameters(n=630, q=4294967296, Xs=D(σ=0.50, μ=-0.50), Xe=D(σ=131072.00), m=+Infinity, tag='TFHE630')
> _ = LWE.estimate(schemes.TFHE630)
bkw                  :: rop: ≈2^153.1, m: ≈2^139.4, mem: ≈2^132.6, b: 4, t1: 0, t2: 24, ℓ: 3, #cod: 552, #top: 0, #test: 78, tag: coded-bkw
usvp                 :: rop: ≈2^124.5, red: ≈2^124.5, δ: 1.004497, β: 335, d: 1123, tag: usvp
bdd                  :: rop: ≈2^131.0, red: ≈2^115.1, svp: ≈2^131.0, β: 301, η: 393, d: 1095, tag: bdd
bdd_hybrid           :: rop: ≈2^185.3, red: ≈2^115.9, svp: ≈2^185.3, β: 301, η: 588, ζ: 0, |S|: 1, d: 1704, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^265.5, red: ≈2^264.5, svp: ≈2^264.5, β: 301, η: 2, ζ: 215, |S|: ≈2^189.2, d: 1489, prob: ≈2^-146.6, ↻: ≈2^148.8, tag: hybrid
dual                 :: rop: ≈2^128.7, mem: ≈2^72.0, m: 551, β: 346, d: 1181, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^119.8, mem: ≈2^115.5, m: 516, β: 314, d: 1096, ↻: 1, ζ: 50, tag: dual_hybrid

In this example, the most efficient attack is the dual_hybrid attack. It uses 2^119.8 ring operations, and so these parameters provide 119.8 bits of security. The reader may notice that the TFHE website claims those parameters give 128 bits of security. This discrepancy is due to the fact that they used an older library (the LWE estimator, which is no longer maintained), which doesn’t take into account the most up-to-date lattice attacks.

For further reading, Benjamin Curtis wrote an article about parameter selection for the CONCRETE implementation of the TFHE scheme. Benjamin Curtis, Martin Albrecht, and other researchers also used the Lattice Estimator to estimate all the LWE and NTRU schemes.

Ring Learning with Errors (RLWE) security

It is often desirable to use Ring LWE instead of LWE, for greater efficiency and smaller key sizes (as Chris Peikert illustrates via meme). We’d like to estimate the security of a Ring LWE scheme, but it wasn’t immediately obvious to us how to do this, since the Lattice Estimator only operates over LWE instances. In order to use the Lattice Estimator for this security estimate, we first needed to do a reduction from the RLWE instance to an LWE instance.

Attempted RLWE to LWE reduction

Given an RLWE instance with $ \text{RLWE_dimension} = k $ and $ \text{poly_log_degree} = N $, we can create a relation that looks like an LWE instance of $ \text{LWE_dimension} = N * k $ with the same security, as long as $N$ is a power of 2 and there are no known attacks that target the ring structure of RLWE that are more efficient than the best LWE attacks. Note: $N$ must be a power of 2 so that $x^N+1$ is a cyclotomic polynomial.

An RLWE encryption has the following form: $ (a_0(x), a_1(x), … a_{k-1}(x), b(x)) $

  •   Public polynomials: $ a_0(x), a_1(x), \dots a_{k-1}(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} (\mathbb{Z}/{q \mathbb{Z}[x]} ) / (x^N + 1)^k$
  •   Secret (binary) polynomials: $ s_0(x), s_1(x), \dots s_{k-1}(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} (\mathbb{B}_N[x])^k$
  •   Error: $ e(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} \chi_e$
  •   RLWE instance: $ b(x) = \sum_{i=0}^{k-1} a_i(x) \cdot s_i(x) + e(x) \in (\mathbb{Z}/{q \mathbb{Z}[x]} ) / (x^N + 1)$

We would like to express this in the form of an LWE encryption. We can make start with the simple case, where $ k=1 $. Therefore, we will only be working with the zero-entry polynomials, $a_0(x)$ and $s_0(x)$. (For simplicity, in the next example you can ignore the zero-subscript and think of them as $a(x)$ and $s(x)$).

Naive reduction for $k=1$ (wrong!)

Naively, if we simply defined the LWE $A$ matrix to be a concatenation of the coefficients of the RLWE polynomial $a(x)$, we get:

$$ A_{\text{LWE}} = ( a_{0, 0}, a_{0, 1}, \dots a_{0, N-1} ) $$

We can do the same for the LWE $s$ vector:

$$ s_{\text{LWE}} = ( s_{0, 0}, s_{0, 1}, \dots s_{0, N-1} ) $$

But this doesn’t give us the value of $b_{LWE}$ for the LWE encryption that we want. In particular, the first entry of $b_{LWE}$, which we can call $b_{\text{LWE}, 0}$, is simply a product of the first entries of $a_0(x)$ and $s_0(x)$:

$$ b_{\text{LWE}, 0} = a_{0, 0} \cdot s_{0, 0} + e_0 $$

However, we want $b_{\text{LWE}, 0}$ to be a sum of the products of all the coefficients of $a_0(x)$ and $s_0(x)$ that give us a zero-degree coefficient mod $x^N + 1$. This modulus is important because it causes the product of high-degree monomials to “wrap around” to smaller degree monomials because of the negacyclic property, such that $x^N \equiv -1 \mod x^N + 1$. So the constant term $b_{\text{LWE}, 0}$ should include all of the following terms:

$$\begin{aligned}
b_{\text{LWE}, 0} = & a_{0, 0} \cdot s_{0, 0} \\
 – & a_{0, 1} \cdot s_{0, N-1} \\
 – & a_{0, 2} \cdot s_{0, N-2} \\
 – & \dots \\
 – & a_{0, N-1} \cdot s_{0, 1}\\
 + & e_0\\
\end{aligned}
$$

Improved reduction for $k=1$

We can achieve the desired value of $b_{\text{LWE}}$ by more strategically forming a matrix $A_{\text{LWE}}$, to reflect the negacyclic property of our polynomials in the RLWE space. We can keep the naive construction for $s_\text{LWE}$.

$$ A_{\text{LWE}} =
\begin{pmatrix}
a_{0, 0}   & -a_{0, N-1} & -a_{0, N-2} & \dots & -a_{0, 1}\\
a_{0, 1}   & a_{0, 0}    & -a_{0, N-1} & \dots & -a_{0, 2}\\
\vdots     & \ddots      &             &       & \vdots   \\
a_{0, N-1} & \dots       &             &       & a_{0, 0} \\
\end{pmatrix}
$$

This definition of $A_\text{LWE}$ gives us the desired value for $b_\text{LWE}$, when $b_{\text{LWE}}$ is interpreted as the coefficients of a polynomial. As an example, we can write out the elements of the first row of $b_\text{LWE}$:

$$
\begin{aligned}
b_{\text{LWE}, 0} = & \sum_{i=0}^{N-1} A_{\text{LWE}, 0, i} \cdot s_{0, i} + e_0 \\
b_{\text{LWE}, 0} = & a_{0, 0} \cdot s_{0, 0} \\
 – & a_{0, 1} \cdot s_{0, N-1} \\
 – & a_{0, 2} \cdot s_{0, N-2} \\
 – & \dots \\
 – & a_{0, N-1} \cdot s_{0, 1}\\
 + & e_0 \\
\end{aligned}
$$

Generalizing for all $k$

In the generalized $k$ case, we have the RLWE equation:

$$ b(x) = a_0(x) \cdot s_0(x) + a_1(x) \cdot s_1(x) \cdot a_{k-1}(x) \cdot s_{k-1}(x) + e(x) $$

We can construct the LWE elements as follows:

$$A_{\text{LWE}} =
\left ( \begin{array}{c|c|c|c}
A_{0, \text{LWE}} & A_{1, \text{LWE}} & \dots & A_{k-1, \text{LWE}} \end{array}
 \right )
$$

where each sub-matrix is the construction from the previous section:

$$ A_{\text{LWE}} =
\begin{pmatrix}
a_{i, 0}   & -a_{i, N-1} & -a_{i, N-2} & \dots & -a_{i, 1}\\
a_{i, 1}   & a_{i, 0}    & -a_{i, N-1} & \dots & -a_{i, 2}\\
\vdots     & \ddots      &             &       & \vdots   \\
a_{i, N-1} & \dots       &             &       & a_{i, 0} \\
\end{pmatrix}
$$

And the secret keys are stacked similarly:

$$ s_{\text{LWE}} = ( s_{0, 0}, s_{0, 1}, \dots s_{0, N-1} \mid s_{1, 0}, s_{1, 1}, \dots s_{1, N-1} \mid \dots ) $$

This is how we can reduce an RLWE instance with RLWE dimension $k$ and polynomial modulus degree $N$, to a relation that looks like an LWE instance of LWE dimension $N * k$.

Caveats and open research

This reduction does not result in a correctly formed LWE instance, since an LWE instance would have a matrix $A$ that is randomly sampled, whereas the reduction results in an matrix $A$ that has cyclic structure, due to the cyclic property of the RLWE instance. This is why I’ve been emphasizing that the reduction produces an instance that looks like LWE. All currently known attacks on RLWE do not take advantage of the structure, but rather directly attack this transformed LWE instance. Whether the additional ring structure can be exploited in the design of more efficient attacks remains an open question in the lattice cryptography research community.

In her PhD thesis, Rachel Player mentions the RLWE to LWE security reduction:

In order to try to pick parameters in Ring-LWE-based schemes (FHE or otherwise) that we hope are sufficiently secure, we can choose parameters such that the underlying Ring-LWE instance should be hard to solve according to known attacks. Each Ring-LWE sample can be used to extract $n$ LWE samples. To the best of our knowledge, the most powerful attacks against $d$-sample Ring-LWE all work by instead attacking the $nd$-sample LWE problem. When estimating the security of a particular set of Ring-LWE parameters we therefore estimate the security of the induced set of LWE parameters.

This indicates that we can do this reduction for certain RLWE instances. However, we must be careful to ensure that the polynomial modulus degree $N$ is a power of two, because otherwise the error distribution “breaks”, as my colleague Baiyu Li explained to me in conversation:

The RLWE problem is typically defined in using the ring of integers of the cyclotomic field $\mathbb{Q}[X]/(f(X))$, where $f(X)$ is a cyclotomic polynomial of degree $k=\phi(N)$ (where $\phi$ is Euler’s totient function), and the error is a spherical Gaussian over the image of the canonical embedding into the complex numbers $\mathbb{C}^k$ (basically the images of primitive roots of unity under $f$). In many cases we set $N$ to be a power of 2, thus $f(X)=X^{N/2}+1$, since the canonical embedding for such $N$ has a nice property that the preimage of the spherical Gaussian error is also a spherical Gaussian over the coefficients of polynomials in $\mathbb{Q}[X]/(f(X))$. So in this case we can sample $k=N/2$ independent Gaussian numbers and use them as the coefficients of the error polynomial $e(x)$. For $N$ not a power of 2, $f(X)$ may have some low degree terms, and in order to get the spherical Gaussian with the same variance $s^2$ in the canonical embedding, we probably need to use a larger variance when sampling the error polynomial coefficients.

The RLWE we frequently use in practice is actually a specialized version called “polynomial LWE”, and instantiated with $N$ = power of 2 and so $f(X)=X^{N/2}+1$. For other parameters the two are not exactly the same. This paper has some explanations: https://eprint.iacr.org/2018/170.pdf

The error distribution “breaks” if $N$ is not a power of 2 due to the fact that the precise form of RLWE is not defined on integer polynomial rings $R = \mathbb{Z}[X]/(f(X))$, but is defined on its dual (or the dual in the underlying number field, which is a fractional ideal of $\mathbb{Q}[X]/(f(x))$), and the noise distribution is on the Minkowski embedding of this dual ring. For non-power of 2 $N$, the product mod $f$ of two small polynomials in $\mathbb{Q}[X]/(f(x))$ may be large, where small/large means their L2 norm on the coefficient vector. This means that in order to sample the required noise distribution, you may need a skewed coefficient distribution. Only when $N$ is a power of 2, the dual of $R$ is a scaling of $R$, and distance in the embedding of $R^{\text{dual}}$ is preserved in $R$, and so we can just sample iid gaussian coefficient to get the required noise.

Because working with a power-of-two RLWE polynomial modulus gives “nice” error behavior, this parameter choice is often recommended and chosen for concrete instantiations of RLWE. For example, the Homomorphic Encryption Standard
recommends and only analyzes the security of parameters for power-of-two cyclotomic fields for use in homomorphic encryption (though future versions of the standard aim to extend the security analysis to generic cyclotomic rings):

We stress that when the error is chosen from sufficiently wide and “well spread” distributions that match the ring at hand, we do not have meaningful attacks on RLWE that are better than LWE attacks, regardless of the ring. For power-of-two cyclotomics, it is sufficient to sample the noise in the polynomial basis, namely choosing the coefficients of the error polynomial $e \in \mathbb{Z}[x] / \phi_k(x)$ independently at random from a very “narrow” distribution.

Existing works analyzing and targeting the ring structure of RLWE include:

It would of course be great to have a definitive answer on whether we can be confident using this RLWE to LWE reduction to estimate the security of RLWE based schemes. In the meantime, we have seen many Fully Homomorphic Encryption (FHE) schemes using this RLWE to LWE reduction, and we hope that this article helps explain how that reduction works and the existing open questions around this approach.

by j2kun at Wednesday, December 28, 2022