Michel Buffa
email: buffa@univ-cotedazur.fr

Antoine Vidal
email: antoine.vidal-mazuy@etu.univ-cotedazur.fr

WAM-studio, a Digital Audio Workstation (DAW) for the Web

Keywords: Software and its engineering → Abstraction, modeling and modularity Web Audio, DAWs, plugin architecture, Web standards

This paper presents WAM Studio, an open source, online Digital Audio Workstation (DAW) that takes advantages of several W3C Web APIs, such as Web Audio, Web Assembly, Web Components, Web Midi, Media Devices etc. It also uses the Web Audio Modules proposal that has been designed to facilitate the development of inter-operable audio plugins (effects, virtual instruments, virtual piano keyboards as controllers etc.) and host applications. DAWs are feature-rich software and therefore particularly complex to develop in terms of design, implementation, performances and ergonomics. Very few commercial online DAWs exist today and the only open-source examples lack features (no support for inter-operable plugins, for example) and do not take advantage of the recent possibilities offered by modern W3C APIs (e.g. Au-dioWorklets/Web Assembly). WAM Studio was developed as an open-source technology demonstrator with the aim of showcasing the potential of the web platform, made possible by these APIs. The paper highlights some of the difficulties we encountered (i.e limitations due to the sandboxed and constrained environments that are Web browsers, latency compensation etc.). An online demo, as well as a GitHub repository for the source code are available.

INTRODUCTION

Computer Assisted Music (CAM) is an ever-evolving field that uses computers to record, edit, and produce music. Digital Audio Workstations (DAWs) are specially designed software for CAM , allowing users to create and manipulate digital audio content,as well as MIDI WWW'23Companion,April30-May4,2023,Austin,TX,USA https://doi.org/10.1145/3543873.3587987 content. Audio plugins are software modules that add additional features to DAWs, giving users greater flexibility and control over their music production. The CAM market became popular with the Atari ST (1985) and the Cubase DAW proposed by Steinberg (1989) 1 . Soon, the VST standard for audio plugins has been proposed (1997) and since then thousands of plugins have been developed, that can be used in the main native DAWs available on the market. On the Web platform, the first online DAWs appeared in 2008 and used the Flash technology. The first DAWs that used HTML5 and the Web Audio API for audio processing did not emerge until the period between 2015 and 2016. A DAW is a feature-rich software and therefore particularly complex to develop in terms of design, implementation, and ergonomics. It allows the creation of multi-track pieces by directly using audio samples (e.g. by incorporating into a track an audio file or by recording from a microphone or sound card input), mixing them, applying sound effects to each track (e.g. reverb, frequency equalization, or autotune on vocals), but also using tracks with virtual instruments (software recreation of a piano, violin, synthesizer, drum kit, etc.). The track is then recorded in MIDI format : as events corresponding to notes and additional parameters (such as the strength with which one pressed the keys of a piano keyboard, for example). These events allow the track to be played by requesting a virtual instruments to synthesize the signal. The DAW therefore allows for the playing, recording and mixing of both audio and MIDI tracks, edition of these tracks (copy/cut paste within a track or between tracks), the management of real-time audio effects and virtual instruments, mixing, and exporting the final project in a simple format (e.g. .wav or .mp3 file). In the native world, these effects and instruments are the "audio plugins" that extend the capabilities of standard DAWs. Since 1997, an important market for third-party plugin developers has developed. Four DAWs dominate the market (Logic Audio, Ableton, Pro Tools, Cubase), and the existence of several proprietary plugin formats complicates the task of developers. On the Web, the market is emerging, the technologies more recent, and few DAWs exist, mostly commercial. Nevertheless, an inter-operable plugin format called Web Audio Modules (WAM), currently undergoing active development exists and is backed by at least one commercially available online DAW.

THE WEB AUDIO API

Since 2018, the W3C Web Audio API has been a "candidate recommendation" (a frozen standard). It offers a set of Audio Node generators that process or produce sound. These nodes can be connected to form an "audio graph". The sound travels through this graph at a sample rate of 44100 times per second (default value, this can be changed) and undergoes transformations [START_REF] Buffa | Towards an open Web Audio plug-in standard[END_REF]. Some nodes are wave generators or sound sources corresponding to a microphone input or a sound file loaded into memory, others transform the sound. Connecting these nodes in the browser is done through JavaScript and enables a wide range of different applications involving real-time audio processing [START_REF] Choi | Audioworklet: the Future of Web Audio[END_REF]. Music applications are not the only ones requiring complex audio back-ends, and the API is also designed to meet the needs of games and other use cases, not only for computer music. The API comes with a limited set of standard nodes for common operations such as volume control, audio filtering, delay/echo, reverb, dynamic processing, spatialization, etc.

Usually, in multi-core processor systems, audio libraries/APIs split the work between a control thread and a render thread [START_REF] Déchelle | jMax: an environment for real-time musical applications[END_REF][START_REF] Mccartney | Rethinking the computer music language: Super collider[END_REF][START_REF] Miller Puckette | FTS: A real-time monitor for multiprocessor music synthesis[END_REF]. The Web Audio API is no exception and also uses this pattern: a render thread called the "audio thread" is solely responsible for rendering the audio graph and delivering the samples to the operating system so they can be played by the hardware. This thread has hard real-time constraints and has a high priority -if it fails to provide the next block of audio samples on time (128 samples by default in the case of the Web Audio API), there will be audible glitches. On the other hand, the control thread (generally running JavaScript code for the GUI, and making Web Audio API calls) manages all changes to the audio graph. It allows the user to connect/disconnect nodes and to adjust their parameters. Audio Nodes process the sound in the audio thread, and the algorithms used cannot be changed, only parameter changes are allowed. The recent addition (2018) of the AudioWorklet node provided a solution for implementing custom low-level audio processing running in the audio thread [START_REF] Choi | Audioworklet: the Future of Web Audio[END_REF].

The nodes in the Web Audio API can be assembled into an "audio graph," which developers can use to create more complex audio effects or instruments. Here are some examples of audio effects that could be built this way: echo (DelayNode, BiquadFilterNode, GainNode), auto-wah (BiquadFilterNode, OscillatorNode), chorus (multiple DelayNodes and OscillatorNodes for modulation), distortion (GainNode, WaveShaperNode), synthesizers, samplers etc. Existing DSP code in other languages such as C/C++ or coded using Domain Specific Languages such as FAUST, can be cross-compiled to Web Assembly and run in a single AudioWorklet node. Over the years, lots of high-level audio effects and instruments have been developed [START_REF] Buffa | Emerging W3C APIs opened up commercial opportunities for computer music applications[END_REF]. However, it is often necessary to chain such audio effects and instruments together (for example, in a guitarist's pedalboard) and during music composition/production in DAWs, multiple effects and instruments are used. These are cases where the Web Audio API nodes are too low-level, hence the need for a higher-level unit to represent the equivalent of a native audio plugin [START_REF] Buffa | Making a guitar rack plugin -WebAudio Modules 2.0[END_REF]. For the Web Platform, such a high-level standard for "audio plugins" and "host" applications did not exist before 2015 [START_REF] Kleimola | Web Audio Modules[END_REF]. Several initiatives have aroused and one emerged as a "community standard", which we detail in the following section.

WEB AUDIO MODULES

In 2015, Jari Kleimola and Olivier Larkin proposed the Web Audio Modules (WAM) [START_REF] Kleimola | Web Audio Modules[END_REF], a standard for Web Audio plugins and DAWs. Soon later, Jari Kleimola was involved in the creation of ampedstudio.com, one of the first online DAWs using the WebAudio API. In 2018, the WAM initial project was further developed by researchers with the help of developers from the digital audio workstation industry, resulting in a more versatile standard [START_REF] Buffa | Towards an open Web Audio plug-in standard[END_REF]. Finally, the 2.0 version of Web Audio Modules has been released in 2021. This version aimed, in addition to setting a community standard (API, SDK), to bring more versatility to developers, more performance, to simplify access to plugin parameters, and facilitate integration in DAWs [START_REF] Buffa | Web Audio Modules 2.0: An Open Web Audio Plugin Standard[END_REF]. We will come back to this feature later, but WAM 2.0 uses an original design for handling the communication between plugins and host applications that do not rely on the low-level parameter management provided by the Web Audio API. The main reason for that is to allow high performances in the case where both a DAW and plugins are implemented as AudioWorklets. At the time the WebAudio API has been designed, AudioWorklets did not exist and some use cases could not be taken into account. Indeed, if the DAW is built using AudioWorklet nodes for processing audio, then some parts of the code run in the high priority / audio thread. Then, if a WAM plugin is associated with a given track in a DAW project, and if the plugin is itself built using an AudioWorklet node, it also has custom code running in the audio thread. The WAM framework has been designed to handle this particular case and will enable DAW/plugins communication without crossing the audio thread barrier. Let us take one example: while playing, a MIDI track sends notes to a virtual instrument plugin, and changes some of the parameters of this plugin at the frequency rate. Remember that a DAW can have multiple tracks associated to dozen of plugins, and each plugin can have dozens of parameters. The WAM framework detects this case, and will seamlessly use Shared Array Buffers and a ring buffer, without crossing the audio thread barrier. No need to send events from the control/GUI thread, that would have been mandatory if the Web Audio API audio node parameter management was used. To sum up, the WAM framework streamlines the creation of plugins and host applications and enables highly efficient communication between hosts and plugins.

RELATED WORKS: COMMERCIAL AND OPEN SOURCE DAWS

The first online DAWs based on the WebAudio API appeared in 2015-2018 and are still available today: Audiotools [START_REF] Lazarevic | Unrevealed Potential in Delivering Distance Courses: the Instructional Value of Audio[END_REF], Bandlab, Amped-Studio, Soundtrap [START_REF] Lind | Soundtrap: A collaborative music studio with Web Audio[END_REF], Soundation. These DAWs have in common the fact that they are commercial, closed source and received very little academic publication. They facilitate remote collaboration on musical projects, and have gained increased attention during the COVID-19 pandemic (2021-2022). The mode of collaboration varies (synchronous like Google Docs or asynchronous through sharing links), as well as the communication tools provided (chat, video conferencing), but all these DAWs have the classic features: audio and MIDI recording, track editing, mixing, support for effects and virtual instruments, etc. Some have been designed mainly for desktop computers while others are particularly adapted to mobile devices. They mainly differ in terms of ergonomics : some of these applications are aimed at a very wide audience and have focused on simplicity (BandLab, SoundTrap) while others have chosen a more "professional" and sober look and feel, like AmpedStudio. Audiotools is more a "virtual studio" than a pure DAW and finds its market mainly in the education domain. Implementation details of these applications are unknown as the source code is not publicly accessible. However, through limited academic publications and presentations/interviews, it is known that AmpedStudio uses a cross-compiled C++ engine and AudioWorklets, while Soundtrap has primarily utilized the standard Web Audio API nodes. BandLab is supposed to have a core written in C++, and relies also on Au-dioWorklet, with possibly a specific mobile version. Audiotools runs also in AudioWorklet node(s) with a flash port of the audio engine, effects, instruments... Recently, a new DAW named Arpeggi.io has emerged, which highlights its use of the blockchain technology (for tracking who, when, and how sounds and music are used) and NFTs for monetizing creations. These DAWs differ also in the way they manage audio effects and instruments. It is obvious that some support external plugins: AmpedStudio supports the WAM standard -developers from the company contributed to the proposal-and the web site has a shop for "enabling" premium plugins. The other commercial online DAWs seems to use a proprietary format, while integrating some third party ports of native plugins (Soundtrap proposes the famous "Autotune" plugin made by Antares). Propellerheads, a company well known for its native DAW Reason, also published web versions of its Europa synthesizer plugin (available now in AmpedStudio and in Soundation). So far, AmpedStudio is the only DAW that supports an open plugin standard: Web Audio Modules. Figure 1 illustrates the similarities and differences between these commercial online DAWs.

Gridsound is an open source DAW, that has been developed since 2015 2 . It supports audio and MIDI and is a fully functional DAW. It does not support plugins but comes with a set of audio effects and virtual instruments whose format is specific. There are also popular JavaScript libraries for developing a multi-track player/recorder, such as wavesurfer.js or waveform-playlist 3 , and some audacity like audio buffer editors such as AudioMass 4 . None of these open source initiatives use AudioWorklets and low-level processing, nor take care about optimizing DAW/plugin communication, preserving audio thread isolation, nor use external plugins. This is the main reason why we developed Wam-Studio: as a demonstrator of these techniques.

WAM-STUDIO DESIGN AND IMPLEMENTATION

Wam-Studio is an online tool for creating audio projects that you can imagine as multi-track music. Each track corresponds to a different "layer" of audio content that can be recorded, edited, or just integrated (using audio files for example). Some track can be used to control virtual instruments: in that case we record the sound that is generated internally by these virtual instruments (and played using a MIDI piano keyboard, for example). Tracks can be added or removed, played isolated or with other tracks. They can also be "armed" for recording, and when the recording starts, all other tracks will play along, while the armed track will record new content.

The tracks

A DAW track is a container for audio-related data that comes with an interactive display of these data, editing and processing facilities and few default parameters such as volume and left/right panning. Figure 2 shows an isolated audio track with the wave- form display of the associated audio buffer, and the default track controls/parameters on the left side (mute/solo, volume, stereo panning). As many tracks can be rendered, scrolled during playback, zoomed in/out and edited, we used the pixi.js library to handle drawing and interactions. This library uses gpu accelerated webgl rendering, and provides many features for handling multiple layers over a single HTML5 canvas. As shown in Figure 4, each track can also be associated with a set of plugins for adding audio effects or for generating music (in the case of instrument plugins). Figure 3 shows the audio graph that corresponds to the audio processing chain of an audio track. The sounds goes from left to right: first the "track player/recorder/editor" is implemented as an AudioWorklet node, using custom code for rendering an audio buffer, then the output signal has its gain and stereo panning adjusted, then we have another AudioWorket node for rendering the volume in a canvas (vu-meter), and at the end we find a chain of WAM plugins for adding audio effects.

Figure 3: Audio graph of an audio track in Wam-Studio

There are two types of tracks: Audio tracks : they contain recorded audio, such as a vocal take, a guitar recording, or any other type of audio signal, that are generally rendered graphically as waveforms that represents the actual signal stored (as a set of sound samples). These tracks can be edited, processed and mixed by copying/cutting and pasting audio samples in the audio buffer associated to the track. Audio track's output can be further processed by a chain of audio effects. MIDI tracks : they contains MIDI data (the pitch -the note an instrument would play, velocity, and duration). MIDI data does not contain audio information but are rather used to control virtual instruments such as synthesizers, samplers, drum machines, etc. MIDI tracks can be edited, in that case, it is possible to change the MIDI events stored in the track in a matrix-like display. MIDI tracks are generally associated with one or more virtual instruments. The MIDI events can target all track instruments or some specifically. The tracks are usually organized vertically within the DAW's graphical user interface and can be separately managed in terms of volume, stereo positioning, effects processing, and automation of effects or instruments (as shown in Figure 4). Each track output is connected to a "master track" where it is possible to adjust globally the volume and panning of the final mix. Like for any other tracks, it is also possible to associate a chain of audio effects to the Master track (adjusting final dynamics, frequencies). All audio effects and virtual instruments are WAM plugins in the case of our DAW. This design gives an extensive degree of control and adaptability and enables users to blend and manipulate the sound of each track with high precision and sophistication, thus making it easier to create intricate audio productions. A DAW track is also capable of "rendering" the track into an audible audio signal (when the track is being played). When one presses the play button of the DAW, all the tracks are rendered simultaneously, and the final output signal is what is called "the mix". DAWs also have an "offline rendering" option, for exporting the final mix as a file, on local hard disk or on the cloud (using the OfflineAudioContext5 provided by the WebAudio API).

Track core implemented as an AudioWorklet processor

Let us focus for the moment on an Audio track. The Web Audio API provides the AudioBufferSourceNode that is a container for an audio buffer. This standard node is enough to play any audio buffer stored in memory. However, we will explain why this is not sufficient for a high performance DAW... Remember what can be done in DAWs while a multi-track piece is being played (or recorded): parameter automation! This means interpolating plugin and track parameters at the frequency rate, 44100 times per second. Moreover, these automated parameters can encompass any characteristic of any plugin associated with any track. It is a substantial amount of information that can be exchanged between the DAW and WAM plugins, making performance a crucial aspect that requires careful consideration. By designing our own low-level audio player (instead of using the standard AudioBufferSourceNode), we gain total control over the playback/recording behaviour of each track. We designed each audio track core as an AudioWorklet processor, more precisely, as an instance of a subclass of the WamProcessor class provided by the Web Audio Modules SDK, that inherits from the AudioWorkletProcessor class. According to the API, each processor implements a process method that will be called at the sampling rate. Inside this method, we output the sound samples and render the buffer, but we can also send data to WAM plugins. The WAMProcessor class we inherit from provides methods for handling DAW/plugins communication efficiently. With the WebAudio API, AudioWorklets are comprised of two components, reflecting the multi-threaded nature of the environment: the AudioWorkletNode and the AudioWorkletProcessor. The WAM framework extends them into the WamNode and the WamProcessor classes, which serve as the main thread and audio thread of WAM powered software, respectively. WAM-Studio is a WAM host application, and its tracks are implemented as sub-classes of WamProcessor. The WAM plugins associated to these tracks can also have their DSP core implemented as subclasses of WamProcessor, but this is not mandatory. Some WAM plugins implementations utilize a single node, while others utilize a subgraph consisting of a combination of builtin web audio nodes and custom audio nodes, as abstracted through the WamNode and WamProcessor interfaces. This abstraction enables seamless interoperability between a WAM hosts and plugins, regardless of the underlying implementation, and across all threads.

In other words : if a track is a WamProcessor and if plugins are also WamProcessors, their DSP code runs in the audio thread and highly optimized communication can be achieved: Shared Array Buffers can be used for DAW/Plugin communication. If a plugin is not a WamProcessor, then the DAW code that "talks" with it remains unchanged and the underlying implementation will be suboptimal and will involve crossing the thread barrier. Handling multiple plugins in a chain: The WAM framework employs a singleton object, referred to as the WamEnv, which is attached to the global scope of the audio thread and serves as a mediator for interactions between hosts and processors/plugins. Processors/plugins are structured into WamGroups, managed by the WamEnv, where each group comprises plugins created by a specific host. Considerable effort was exerted to reduce the number of assumptions made by the API regarding host implementation, with the WamEnv and WamGroup being the only objects within the WAM system that are anticipated to be supplied by the host. WamEnv is allocated when the DAW is created, and WamGroup instances are associated with each track.

Managing plugin chains

Plugin chains are handled using a special WAM plugin that acts also as a "mini host". We called it the WAM pedalboard [START_REF] Buffa | Making a guitar rack plugin -WebAudio Modules 2.0[END_REF]. It connects to a plugin server that sends back the list of plugins available as a JSON array of URIs (a WAM plugin can be loaded simply using a dynamic import and its URI, see [START_REF] Buffa | Web Audio Modules 2.0: An Open Web Audio Plugin Standard[END_REF]). From this list of URIs, WAM plugin descriptors are retrieved, that contain metadata about the plugins: name, version, vendor, thumbnail image URI, etc. When the pedalboard plugin is being displayed in the DAW, it is empty, and plugins can be added to the processing chain, removed, re-ordered, and their parameters can be set. Any configuration can be saved as ). Presets can be organized into banks ("rock", "funk", "blues"). The management of the organization and naming of banks and presets is the responsibility of the pedalboard plugin. The parameters exposed by this plugin correspond to the entire set of parameters of the active preset (that is, the sum of the parameters of the plugins associated in the preset), and can be automated by the DAW. The Web Audio Modules API allows for sending events to the DAW when changes occur in the plugin configuration (addition or removal) and the menu provided in the DAW for selecting automatable parameters is automatically updated. All WAM plugins implement getState/setState methods to serialize/deserialize their state. When a project is saved, the state of each track, audio buffers, etc. are saved, as well as the state of the plugin configuration. The recording process using a DAW is more constrained and structured compared to using a simple recording app like a memo recorder, as we must take into account different kind of latencies. The input latency is the time between when an audio signal is captured by the input device and when it is processed by the audio context. It depends on the OS, the configuration of the input device, the processing time of the audio system, and the buffer size used by the audio context. The output latency represents the time between when a sound is generated and when it is actually heard by the user. The sum of these two latency represents the round-trip latency and can be measured using an external recording device with two microphones: one at the source of the physical sound (for example, on the body of a guitar plugged in a sound card), and one in front of the speakers. Hit the body of the guitar, record the output and compare the input and the output signals. We did such measurements in the past [START_REF] Buffa | Real time tube guitar amplifier simulation using WebAudio[END_REF] and showed that the round-trip latency using MacOS with common sound cards available on the market was around 19-23ms with an audio buffer of 128 samples (on Windows this was much bigger, 50-75ms). The WebAudio API exposes two properties of the AudioContext that could have been useful. The baseLatency property represents the number of seconds the AudioContext uses for its internal processing once the audio reaches the AudioDestinationNode (final output of the audio graph). On Chrome it represents the minimum guaranteed latency that an audio context will add to the input audio stream before it is played through the output, and can be calculated as the audio buffer size divided by the sample rate. It is a rough approximation of the real input latency, while on Firefox it is always zero (as Firefox processes the audio directly in the audio callback 6 ). The outputLatency property represents the number of seconds between the audio reaching the AudioDestinationNode (conceptually the audio sink of the audio processing graph) and the audio output device. In February 2023 it is not implemented in all major browsers. This situation makes these properties nearly useless, as we will see. Figure 6 shows the audio graph involved during the track recording process: we need first to obtain a MediaStream from the user's microphone or from a sound card input using the MediaDevices API. Then, we can use a Web Audio API MediaStreamSourceNode in the audio graph, passing the MediaStream to its constructor. This is how we expose a live audio stream to the Web Audio API. In a second step, we need a way to record this stream in a buffer. This can be done using the W3C MediaRecorder API, or using low-level solutions using an AudioWorklet. The MediaRecorder solution has for advantage its simplicity but all tests we conducted showed that this is an unreliable solution as the time it takes for allocating audio buffers and starting recording is unpredictable, even when we conduct latency measurements/calibration, as explained later on. We ultimately decided on a low-level, precise solution that uses a WamProcessor to record the sound samples that are received. This solution was crucial, as it was necessary to have full control over the buffer in order to expand it during extended recording sessions. When recording a guitar track, for example, other tracks such as drum and bass tracks can be being played simultaneously, and the guitar sound is processed by a chain of plugins (i.e guitar amplifier simulation, EQ, delay,etc.). The processed recorded guitar sound must be heard real-time in sync with the other tracks and free from any noticeable latency while being played (and recorded). This is why the overall round-trip latency should be as low as possible. We represented it with the red path in Figure 6. Using a 128 sample buffer size, the round-trip latency of 23ms we measured on MacOS [START_REF] Buffa | Real time tube guitar amplifier simulation using WebAudio[END_REF], even with pro guitar players, was comfortable and comparable with what we can achieve using native applications in similar use cases (guitar, Logic Audio, guitar amp sim plugin, audio buffer size 128). The recording process requires also proper allocation and management of the track audio buffer, as well as continuous storage of the sound samples coming from the input stream. Here, the input latency is important as the recording process may be delayed due to hardware and software configurations (audio driver, etc.), but also the buffer allocation should be done with care: pre-allocate it before even pressing the recording button, use a ring buffer and start recording as soon as the track is "armed" (DAWs generally provide an "arm" button to select tracks that will be recorded), then store a timestamp when the recording really starts. To ensure that the recorded guitar track plays back in sync with the other tracks, we do some "latency compensation" i.e shift back in time the buffer content, depending on the input latency. Do you remember that we do not know its accurate value? The problem is that it is rather complicated to find this number in a program running, for a variety of reasons (again, see Paul Adenot blog post on footnotes). The solution we use consists in calibrating the DAW along with the hardware used, prior to recording. This process involves the use of a microphone to record a pre-generated sound emitted by the DAW and determining the time elapsed between the emission of the signal and its recording. This value is then used for latency compensation. The AmpedStudio DAW proposes a similar approach for calibration in its setting menu. Soundtrap authors explained that they rather use lookup tables with entries for the most common OS/soundcard pairs, calibrated by hand, and hard coded in the code [START_REF] Lind | Soundtrap: A collaborative music studio with Web Audio[END_REF]. They then use some heuristics to guess the current configuration (checking the OS, guessing the sound card model looking at the number of inputs/outputs exposed using the MediaDevice API, etc.). In WAM-Studio, latency compensation is a work in progress: for the moment we do it manually by entering a value measured by an external utility software 7 we developed, that uses the calibration process we just described (emit a sound, record, compare input and output).

Recording process, dealing with latency

CONCLUSION

As of today, WAM-Studio is an open source example of a DAW using advanced features such as external plugin support, high performance DAW/plugins communications, audio track playing, recording and editing. As a demonstrator, it shows the capabilities of the Web Audio API, and how the Web Audio Modules framework can be used to ease the development of complex web based audio applications with support for external plugins. Midi tracks support is still a work in progress 8 and development is active. The source code can be found on a GitHub repository 9 , and the application is available online 10 .

Figure 1 :

 1 Figure 1: Comparison table of the main online DAWs on the market

Figure 2 :

 2 Figure 2: A track in the DAW GUI

Figure 4 :

 4 Figure 4: A plugin chain associated to the selected track

Figure 5 :

 5 Figure 5: the WAM Pedalboard that manages plugin chains associated to DAW tracks

Figure 6 :

 6 Figure 6: Track recording process in WAM-Studio

https://www.musicradar.com/news/tech/a-brief-history-of-computer-music-177299

https://gridsound.com/. See also the GridSound video presentation at ADC 2021 conference: https://www.youtube.com/watch?v=ejTtENwRxnA

https://github.com/naomiaro/waveform-playlist

https://audiomass.co/

In contrast with a standard AudioContext, an OfflineAudioContext doesn't render the audio to the device hardware; instead, it generates it, as fast as it can, and outputs the result to an AudioBuffer

See Paul Adenot blog post https://blog.paul.cx/post/audio-video-synchronizationwith-the-web-audio-api/


Daiki Miyahara
email: miyahara@uec.ac.jp

Éo Robert

Pascal Lafourcade

Takaaki Mizuki

Léo Robert
email: leo.robert@u-picardie.fr

x, xxxxxxx 20xx ZKP protocols for Usowan, Herugolf and Five Cells

Keywords: ZKP protocol, playing cards, card-based cryptography, physical assumptions, Usowan, Herugolf, Five Cells 1 Intoduction

A Zero-Knowledge Proof (ZKP) protocol allows a participant to prove the knowledge of some secret without revealing any information about it. While such protocols are typically executed by computers, there exists a line of research proposing physical instances of ZKP protocols. Up to now, many card-based ZKP protocols for pen-and-pencil puzzles, like Sudoku, have been designed. Those games, mostly edited by Nikoli, have simple rules, yet designing them in card-based ZKP protocols is non-trivial. In this work, we propose a card-based ZKP protocol for Usowan, a Nikoli game. In Usowan, for each room of a puzzle instance, there is exactly one piece of false information. The goal of the game is to detect this wrong data amongst the correct data and also to satisfy the other rules. Designing a card-based ZKP protocol to deal with the property of detecting a liar has never been done.

.

In this extension, we propose two other protocols, for Herugolf and Five Cells. The puzzles are specifically chosen because each of those three puzzles shares a common constraint, connectivity. However, showing the connected configuration cannot be done with generic approach and brings new construction to the existing connectivity ZKP protocol. Indeed, in Herugolf, the connectivity is handled with a given length of cell which is decremental (i.e., the length of each connected cell decreases by one at each step). For Five Cells, there is an additional step in the setup allowing to encode all the information needed to ensure a valid ZKP protocol.

solution is hard. Such construction already exists and can be found in the field of cryptography. Indeed, a Zero-Knowledge Proof (ZKP) is a process where one party can prove the knowledge of information without revealing it.

A simple application to ZKP can be related to password authentication for a website; only the person with this password can access to sensitive data but it is preferable to never reveal the password. A second example can be given in electronic voting. In this system, voters want to enforce the correctness of mixing ballots (without revealing how the mix was done). Finally, crypto-currencies, such as Bitcoin, Monero, or Zcash, are eager to include a mechanism to enforce knowledge of some secrets without revealing it (e.g., for anonymous transactions).

More formally, a ZKP protocol is between two However, no information about s should leak during the protocol. Notice that some information can be recovered by the verifier without participating in the protocol. The information that cannot be leaked are the one directly linked with the protocol. Note also that some protocols are non-interactive meaning that the prover does not interact with the verifier in order to prove the knowledge of a secret. However, we only consider here interactive protocols where both parties are interacting during the protocol.

A ZKP protocol must guarantee three security properties:

• Completeness: if P knows s then V is convinced when the protocol ends.

• Soundness: if P does not have the solution, then V will detect it during the protocol.

• Zero-knowledge: V learns nothing about s.

Most of the practical applications for ZKP protocols are executed by computers. We restrict ourselves by using only physical cards and envelopes, hence providing a more understandable approach of how ZKP protocols are designed.

In [START_REF] Robert | Hide a liar: Card-based ZKP protocol for usowan[END_REF], we presented a physical ZKP protocol for Usowan [1] which is a pencil puzzle played with a rectangular grid composed of numbered cells and white cells delimited by regions (thick edges).

The goal is to fill (in black) some cells:

We depict in Fig. 1 an initial Usowan grid with its solution and the corresponding rules in Fig. 2. Notice that numbered cell whose number is four (or more) is automatically a liar. Indeed, if there are four black cells around a numbered cell, then the numbered cell cannot be connected to other white cells. This information is not considered as a leak from the protocol since it is deducible from the initial setup (and not from an interaction during the protocol).

While the hardness of the resolution for the underlying problem (here filling an Usowan grid) is not crucial for a physical protocol, a usual ZKP protocol needs to be based on a NP-complete problem (otherwise Fig. 1 Initial Usowan grid and its solution taken from [1].

Usowan Rules:

(1) The numbered cells must remain white.

(2) The white cells form a connected shape.

(3) The black cells cannot connect vertically or horizontally.

(4) A numbered cell has the corresponding number of black cells around it (vertically or horizontally). However, each region has exactly one liar i.e., the number of black cells is not equal to the numbered cell.

Fig. 2 Rules for Usowan [1].

the verifier could compute the secret in polynomial time). Fortunately, the NP-completeness of Usowan has been proved in [START_REF] Iwamoto | Computational complexity of Usowan puzzles[END_REF]. This result ensures that there exists a ZKP protocol.

In this paper, we design two other protocols for two puzzles, Herugolf and Five Cells. Herugolf has been proven NP-complete in [START_REF] Iwamoto | Herugolf and Makaro are np-complete[END_REF] and Five Cells in [START_REF] Iwamoto | Five cells and tilepaint are np-complete[END_REF]. Five Cells. The goal of this puzzle is to divide the grid into blocks of cells, where the constraints are given in Fig. 3 and an example is illustrated in Fig. 4.

Five Cells Rules:

(1) Each block is composed of exactly five cells.

(2) A number indicates how many lines there are around the cell (edges are also considered).

Fig. 3 Rules for Five Cells. in straightline, from center to center of cells. Each numbered cell must be connected with "H" (hole) cell. The constraints are given in Fig. 5 with an example in Fig. 6.

Herugolf Rules:

(1) Show the movement of a circle by an arrow, with the tip of the arrow in the cell where it stops. The arrows can not cross other circles, H cells, or lines of other arrows.

(2) The first arrow from the numbered cell goes across that number of cells (indicated by the number). Other arrows are decreasing, in the number of cells, of 1.

(3) An arrow cannot leave the grid, or stop in the gray area (but an arrow can pass through it). Contributions. We constructed in [START_REF] Robert | Hide a liar: Card-based ZKP protocol for usowan[END_REF] a physical ZKP protocol for Usowan, giving the first application to detecting if a puzzle has flaws (i.e., the liar rule) while ensuring that the prover has the solution. It is the first physical ZKP protocol to prove that some information is incorrect among correct information. For this, we only used cards and envelopes. Moreover, we proposed a trick that uses the rules of a Usowan grid in order to prove that exactly one piece of information is wrong in each room. We used several sub-protocols to verify the rules and proposed a completely novel ZKP protocol.

In this paper, we propose two other protocols for two different puzzles, Five Cells and Herugolf. The link between the three puzzles presented here is the connectivity constraint which enforces that each white cell must share at least one adjacent white cell. For Five Cells, the difficulty, in constructing a ZKP protocol, lies in changing the usual encoding for the connectivity problem. Indeed, our new protocol must solve the issue of having an encoding for connectivity and an encoding for delimiting region (i.e., encode lines between cells).

For Herugolf, the main challenge is to design a ZKP protocol with a decrement for the connectivity length.

Note that this work is an extension of a previously accepted paper [START_REF] Robert | Hide a liar: Card-based ZKP protocol for usowan[END_REF] where only the Usowan protocol was proposed.

Related Work. Goldwasser et al. [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF] proved that any NP-complete problem has its corresponding interactive ZKP protocol. Yet the generic approach has tremendous overhead leading to an impractical result. Works on implementing cryptographic protocols using physical objects are numerous, such as in [START_REF] Mizuki | Practical card-based cryptography[END_REF]; or in [START_REF] Dreier | Secure auctions without cryptography[END_REF] where a physical secure auction protocol was proposed. Other implementations have been studied using cards in [START_REF] Den | More efficient match-making and satisfiability: The five card trick[END_REF][START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF], polarising plates [START_REF] Shinagawa | Secure computation protocols using polarizing cards[END_REF], polygon cards [START_REF] Shinagawa | Cardbased protocols using regular polygon cards[END_REF], a standard deck of playing cards [START_REF] Mizuki | Efficient and secure multiparty computations using a standard deck of playing cards[END_REF], using a PEZ dispenser [START_REF] Abe | Efficient private PEZ protocols for symmetric functions[END_REF][START_REF] Balogh | Private computation using a PEZ dispenser[END_REF], using a dial lock [START_REF] Mizuki | Secure multiparty computations using a dial lock[END_REF], using a 15 puzzle [START_REF] Mizuki | Secure multiparty computations using the 15 puzzle[END_REF], or using a tamper-evident seals [START_REF] Moran | Polling with physical envelopes: A rigorous analysis of a human-centric protocol[END_REF][START_REF] Moran | Split-ballot voting: everlasting privacy with distributed trust[END_REF][START_REF] Moran | Basing cryptographic protocols on tamper-evident seals[END_REF]. ZKP's for several other puzzles have been studied such as Sudoku [START_REF] Ruangwises | Two standard decks of playing cards are sufficient for a ZKP for Sudoku[END_REF][START_REF] Sasaki | Efficient card-based zeroknowledge proof for Sudoku[END_REF], Akari [START_REF] Bultel | Physical zeroknowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Takuzu [START_REF] Bultel | Physical zeroknowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF]18], Kakuro [START_REF] Bultel | Physical zeroknowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF][START_REF] Miyahara | Card-based physical zeroknowledge proof for Kakuro[END_REF], KenKen [START_REF] Bultel | Physical zeroknowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Makaro [START_REF] Bultel | Physical zeroknowledge proof for Makaro[END_REF][START_REF] Ruangwises | Physical ZKP for Makaro using a standard deck of cards[END_REF], Norinori [START_REF] Dumas | Interactive physical zero-knowledge proof for Norinori[END_REF], Nonogram [START_REF] Chien | Cryptographic and physical zero-knowledge proof: From Sudoku to Nonogram[END_REF][START_REF] Ruangwises | An improved physical ZKP for Nonogram[END_REF], Nurimisaki [START_REF] Robert | Card-based ZKP protocol for Nurimisaki[END_REF], Slitherlink [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF], Suguru [START_REF] Robert | Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle[END_REF][START_REF] Robert | Physical zero-knowledge proof for suguru puzzle[END_REF], Nurikabe [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF], Ripple Effect [START_REF] Ruangwises | Physical zeroknowledge proof for Ripple Effect[END_REF], Numberlink [START_REF] Ruangwises | Physical zero-knowledge proof for Numberlink puzzle and k vertex-disjoint paths problem[END_REF], Bridges [START_REF] Ruangwises | Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems[END_REF], Shikaku [START_REF] Ruangwises | How to physically verify a rectangle in a grid: A physical ZKP for shikaku[END_REF] and Cryptarithmetic [START_REF] Isuzugawa | Zero-knowledge proof protocol for Cryptarithmetic using dihedral cards[END_REF].

Outline. In Sect. 2, we explain how to encode a grid with some cards in order to be able to construct our ZKP protocols. We also recall the existing card-based simple protocols of the literature that we use in our constructions. In Sect. 3, we briefly present our ZKP protocol for Usowan.

Next, Sect. 4 and Sect. 4.3 give the description of our ZKP protocol for Five Cells and its security proof, respectively.

Before concluding in Sect. 6, we present our ZKP protocol for Herugolf in 5 and its security proof in Sect. 5.2.

Preliminaries

We explain the notations and sub-protocols used in our construction. We first introduce the general framework of card-based protocols, then present the existing sub-protocols used in our constructions.

Cards and Encoding. The cards consist of clubs ♣ and hearts ♡ whose backs are identical ? . We encode three colors {black, white, red} with the order of two cards as follows:

♣ ♡ → black, ♡ ♣ → white, ♡ ♡ → red.

(

We call a pair of face-down cards ? ? corresponding to a color according to the above encoding rule a commitment to the respective color. We also use the terms, a black commitment, a white commitment, and a red commitment. We sometimes regard black and white commitments as bit values, based on the following encoding:

♣ ♡ → 0, ♡ ♣ → 1. (2)
For a bit x ∈ {0, 1}, if a pair of face-down cards satisfies the encoding (2), we say that it is a commitment to x, denoted by ? ?

x .

We also define two other encodings [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF]:

• ♣-scheme: for x ∈ Z/pZ, there are p cards composed of p-1 ♡s and one ♣ at position (x+1) from the left. For example, 2 is represented as ♡ ♡ ♣ ♡ in Z/4Z.

• ♡-scheme: same encoding as above but the ♡ and ♣ are reversed. For instance, 2 is represented as

♣ ♣ ♡ ♣ in Z/4Z.
2.1 Pile-shifting shuffle [START_REF] Nishimura | Pile-shifting scramble for card-based protocols[END_REF][START_REF] Shinagawa | Cardbased protocols using regular polygon cards[END_REF] This shuffling action means to shuffle piles of cards cyclically. More formally, given m piles, each of which consists of the same number of face-down cards, denoted by (p 1 , p 2 , . . . , p m ), applying a pile-shifting shuffle (denoted by

⟨•∥ • • • ∥•⟩) results in (p s+1 , p s+2 , . . . , p s+m ): ? p 1 ? p 2 • • • ? p m → ? • • • ? p s+1 p s+m ,
where s is uniformly and randomly chosen from Z/mZ. We can simply implement this shuffling action using physical cases that can store a pile of cards, such as boxes and envelopes. A player (or players) cyclically shuffles them manually until everyone (i.e., P and V ) loses track of the offset. Note that this shuffle can be "input-preserving" by writing ordered numbers at the back of envelopes. When all operations are done, players can put back to their initial positions all the commitments using those numbers. We implicitly use this when commitments need to be placed back to their initial positions after a shuffle.

Mizuki-Sone

Copy Protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] We use it to copy commitments, ensuring to V that this is indeed a correct copy of a given commitment (i.e., P cannot cheat with arbitrary value). Note that a red commitment is not considered in this protocol.

This description is a compact version of the original one [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF]. Here, we use a pile-shifting shuffle in step 2 instead of using a random bisection cut invented in [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF].

The protocol proceeds as follows.

(1) Turn over all face-up cards and put the commitment to a above the four additional cards as follows:

? ? a ♣ ♡ ♡ ♣ → ? ? a ? ? 0 ? ? 1 .
Note that black-to-red represents 0, and red-toblack represents 1 according to Eq. ( 2).

(2) Apply a pile-shifting shuffle as follows: ? ? ? ? ? ? → ? ? ? ? ? ? .

(3) Reveal the two above cards and obtain two commitments to a as follows (note that negating a commitment is easy).

(a) If they are ♣ ♡ , then the four bottom cards are ? ? 2.3 Input-preserving Five-card Trick [18] This sub-protocol allows to compute an OR operation while being able to replace commitments back to their original configuration.

(1) Add helping cards and swap the two cards of the commitment to a so that we have the negation b, as follows: ? ? (2) Rearrange the sequence of cards and turn over the face-up cards as:

? ? ♡ ? ? ♡ ♣ ♣ ♣ ♣ → ? ? ♡ ? ? ♡ ♣ ♣ ♣ ♣ → ? ? ♡ ? ? ? ? ? ? ? .

(3) Regarding cards in the same column as a pile, apply a pile-shifting shuffle to the sequence:

? ?

? ?

? ?

? ?

? ?

→ ? ? ? ? ? ? ? ? ? ? .

(4) Reveal all the cards in the above row.

(a) If the resulting sequence is ♣ ♣ ♡ ♡ ♡ (up to cyclic shifts), then a ∨ b = 0.

(b) If it is ♡ ♣ ♡ ♣ ♡ (up to cyclic shifts), then a ∨ b = 1.

(5) After turning over all the face-up cards, apply a pile-shifting shuffle.

(6) Reveal all the cards in the bottom row; then, the revealed cards should include exactly one ♡ .

(7) Shift the sequence of piles so that the leftmost card is the revealed ♡ and swap the two cards of the commitment to b to restore commitments to a and b.

How to Form a White Polyomino

Before explaining the protocol, we need to describe two crucial sub-protocols first, namely the chosen pile protocol and the 4-neighbour protocol. [START_REF] Dumas | Interactive physical zero-knowledge proof for Norinori[END_REF] This protocol allows P to choose a pile of cards without V knowing which one it is. Some operations can be done on this pile while all the commitments are replaced in their initial order.

Chosen Pile Protocol

This protocol is an extended version of the "chosen pile cut" proposed in [START_REF] Koch | Foundations for actively secure card-based cryptography[END_REF]. Given m piles (p 1 , p 2 , . . . , p m ) with 2m additional cards, the chosen pile protocol enables a prover P to choose the ith pile p i (without revealing the index i) and revert the sequence of m piles to their original order after applying other operations to p i .

(1) Using m -1 ♣ s and one ♡ , P places m facedown cards (denoted by row 2) below the given piles such that only the i-th card is ♡ . V further places m cards (denoted by row 3) below the cards such that only the first card is ♡ as depicted in Fig. 7. (2) Considering the cards in the same column as a pile, apply a pile-shifting shuffle to the sequence of piles.

? p 1 ? p 2 • • • ? p i-1 ? p i ? p i+1 • • • ? p m ? ♣ ? ♣ • • • ? ♣ ? ♡ ? ♣ • • • ? ♣ ← row 2 ? ♡ ? ♣ • • • ? ♣ ? ♣ ? ♣ • • • ? ♣ ← row 3
(3) Reveal all the cards in row 2. Then, exactly one ♡ appears, and the pile above the revealed ♡ is the i-th pile (thus P can obtain p i ). After this step is invoked, other operations are applied to the chosen pile. Then, the chosen pile is placed back to the i-th position in the sequence.

(4) Remove the revealed cards, i.e., the cards in row 2. (Note, therefore, that we do not use the card ♡ revealed in Step 3.) Then, apply a pile-shifting shuffle.

(5) Reveal all the cards in row 3. Then, one ♡ appears, and the pile above the revealed ♡ is p 1 . Therefore, by shifting the sequence of piles (such that p 1 becomes the leftmost pile in the sequence), we can obtain a sequence of piles whose order is the same as the original one without revealing any information about the order of the input sequence.

Sub-protocol: 4-Neighbour Protocol [31]

Given pq commitments placed on a p × q grid, a prover P has a commitment in mind, which we call a target commitment. The prover P wants to reveal the target commitment and another one that lies next to the target commitment (without revealing their exact positions). Here, a verifier V should be convinced that the second commitment is a neighbour of the first one (without knowing which one) as well as V should be able to confirm the colours of both the commitments. To handle the case where the target commitment is at the edge of the grid, we place commitments to red (as "dummy" commitments) in the left of the first column and the below of the last row to prevent P from choosing a commitment that is not a neighbour. Thus, the size of the expanded grid is (p + 1) × (q + 1).

Note that we do not place dummy commitments in the row above the first one and in the column right to the last one because in the expanded grid of size (p + 1)(q + 1) the row above the first one can be regarded as the last row, i.e., dummy commitments. Thus, we do not need dummy commitments placed in the row above the first one, which also holds for the column right to the last one.

The sub-protocol proceeds as follows.

(1) P and V pick the (p + 1)(q + 1) commitments on the grid from left-to-right and top-to-bottom to make a sequence of commitments:

? ? ? ? ? ? ? ? • • • ? ? .

(2) P uses the chosen pile protocol (Sect. 2) to reveal the target commitment.

(3) P and V pick all the four neighbours of the target commitment. Since a pile-shifting shuffle is a cyclic reordering, the distance between commitments are kept (up to a given modulo). That is, for a target commitment (not at the edge), the possible four neighbours are at distance one for the left or right one, and p+1 for the bottom or top one. Therefore, P and V can determine the positions of all the four neighbours.

(4) Among these four neighbours, P chooses one commitment using the chosen pile protocol and reveals it.

(5) P and V end the second and first chosen pile protocols.

Full Protocol

Assume that there is a grid having p × q cells. Without loss of generality, P wants to arrange white commitments on the grid such that they form a whitepolyomino while V is convinced that the placement of commitments is surely a white-polyomino. The method is as follows.

(1) P and V place a black commitment (i.e., ♣ ♡ ) on every cell and red commitments as mentioned in Sect. 2.4.2 so that they have (p + 1)(q + 1) commitments on the board.

(2) V selects a black commitment on any cell that should be colored white by rules (e.g., numbered cells in a Usowan puzzle) and swaps the two cards constituting the commitment so that it becomes a white commitment (recall the encoding (1)).

(3) P and V repeat the following steps exactly pq -1 times.

(a) P chooses one white commitment as a target and one black commitment among its neighbours using the 4-neighbour protocol; the neighbour is chosen such that P wants to make it white.

( ii. Regarding cards in the same column as a pile, V applies a pile-shifting shuffle to the sequence of piles:

? ? ? ? → ? ? ? ? .

iii. V reveals the two cards in the second row. If the revealed right card is ♡ , then V swaps the two cards in the first row; otherwise V does nothing.

(d) P and V end the 4-neighbour protocol.

(4) P and V remove all the red commitments (i.e., dummy commitments) so that we have pq commitments on the board.

After this process, V is convinced that all the white commitments represent a white-polyomino. Therefore, this method allows a prover P to make a solution that only P has in mind, guaranteed to satisfy the connectivity constraint.

* One might think that this step can be simply achieved by letting P privately change the neighbour commitment. However, it might violate the soundness property because P can freely change it (e.g., into a red commitment), and hence, we have to additionally verify that P correctly changes the commitment.

If the number of white cells in the final polyomino, say k, is public to a verifier V , it is sufficient that in Step 3, P and V repeat k -1 times and in Step 3c, and hence, V simply swaps the two cards constituting the neighbour commitment to make it white (without P 's choice).

Sum in Z [39]

We give an overview of the protocol described in [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF] for adding elements in Z/2Z with result in Z. This protocol is needed for the liar rule 4.

Given commitments to x i ∈ Z/2Z for i ∈ {1, . . . , n} along with one ♣ and one ♡ , the protocol produces their sum S = n i=1 x i in Z/(n + 1)Z encoded in the ♡-scheme without revealing x i . The computation is performed inductively; when starting by the two first commitments to x 1 and x 2 , they are transformed into x 1 -r and x 2 + r encoded in the ♡-scheme and ♣-scheme, respectively, for uniformly random value r ∈ Z/3Z. Then x 2 + r is revealed (no information about x 2 is revealed because r is random), and x 1 -r is shifted by x 2 + r positions to encode

(x 1 -r) + (x 2 + r) = x 1 + x 2 .
Note that this result is in Z/(p + 1)Z (or simply Z because the result is less than or equal to p) for elements x 1 , x 2 in Z/pZ.

Let us describe the protocol. First, notice that black cells are assumed to be equal to 1 and white cells are equal to 0 (see Eqs. ( 1) and ( 2)). Two commitments to x 1 and x 2 (either 0 or 1) will be changed to x 1 + x 2 :

? ? x1 ? ? x2 ♣ ♡ → ? ? ? x1+x2 .
(1) Swap the two cards of the commitment to x 1 and add a ♣ face down to the right. Those three cards represent x 1 in the ♡-scheme in Z/3Z:

-→ ←- ? ? x1 ? ♣ → ? ? ? x1 .
(2) Add a ♡ on the right of the commitment to x 2 . Those three cards represent x 2 in the ♣-scheme in Z/3Z: ? ? .

For a uniformly random value r ∈ Z/3Z, we obtain three cards representing x 1 + r and those representing 2 -x 2 + r.

(c) Reverse the order of the three cards representing 2 -x 2 + r to obtain those representing x 2 -r: ? ? ?

x1+r ? ? ?

x2-r .

(4) Reveal the three cards representing x 2 -r, and shift to the right the three cards representing x 1 + r to obtain those representing x 1 +x 2 in the ♡-scheme; apply the same routine for the remaining elements to compute the final sum.

Notice that we described the protocol for a result in Z/3Z but it is easily adaptable for a result in, let say, Z/qZ. Indeed, during the first step, we add a single ♣ to the first commitment and a single ♡ to the second; thus for a sum that could be equal to q -1, we add q -2 ♣ s to the first commitment and q -2 ♡ s to the second.

ZKP protocol for Usowan

We present a card-based ZKP protocol for Usowan. Consider an Usowan instance composed as a rectangular grid of size p × q.

Setup phase

The verifier V and prover P place black commitments on each cell of the p × q grid (also on the numbered cells) and place red commitments ("dummy" commitments) on the left of the frst column and below the last row so that we have (p + 1)(q + 1) commitments.

Connectivity phase

We apply the sub-protocol introduced in Sect. 2.4 to form a white connected figure. After this phase, V is convinced that the white commitments are connected (rule 2). Moreover, V reveals the commitments corresponding to numbered cells to check that they are indeed white (rule 1). Notice that revealing directly those commitments does reveal information about the solution (i.e., V learns that those cells are white), but this information is already known independently of the protocol.

Verification Phases

There are two rules to check: black commitments cannot touch horizontally nor vertically (rule 3) and each numbered cell has the corresponding number of black cells around it except for one liar in each region (rule 4).

Lonely black. For each pair of adjacent commitments, V applies the five-card trick introduced in Sect. 2.3 to the two commitments to compute their disjunction. We consider here that a white commitment is equal to 1 while a black commitment is equal to 0 (see the encoding (2)). Hence, if the output is 1 then it means that at least one commitment is white so V continues, otherwise V aborts (because the only case of output 0 is when there are two black commitments).

Liar. V needs to check that each numbered cell has the corresponding number of black cells around it except for exactly one liar in each region. We cannot simply check the number of black cells because it leaks information. Instead, we compute the sum of black cells in Z/5Z introduced in Sect. 2.5 for all numbered cells in a region. However, we do not directly reveal the result but just the (x-1)-st card of the output sequence. This ensures that the sum is equal or not to x instead of giving the actual sum.

It remains one sub-protocol to use because the addition is destructive; thus, we need to copy commitments sharing a numbered cell. The copy protocol is described in Sect. 2.2. We can now formally describe the liar verification. For every region, apply the following steps:

(1) For each cell that shares k > 1 numbered cells, apply the copy protocol (introduced in Sect. 2.2) k -1 times.

(2) For each numbered cell, compute the addition of its four neighbors † . Recall that the result is encoded as the ♡-scheme (see Sect. 2); thus, the result of the sum has a ♡ in its corresponding position (and all other cards are ♣s).

(3) For each sequence obtained in the previous step, pick the card in the position that corresponds to the number written on the numbered cell. The result must be kept secret (i.e., keep the cards face-down). For example, if the number is three, then the color of the fourth card from the left represents the sum as follows:

b a 3 c d -→ a + b + c + d = ? 0 ? 1 ? 2 ? 3 ↑ ? 4 .
(4) Shuffle and reveal all the cards previously chosen.

If exactly one club is revealed, then continue (i.e., there is exactly one liar); otherwise aborts.

Security Proofs

Our protocol needs to verify three security properties given as theorems. Note that the sub-protocols used from the literature have been proven secure i.e., they are correct, complete, sound and zero-knowledge.

Theorem 1 (Completeness) If P knows the solution of an Usowan grid, then P can convince V .

Proof P convinces V in the sense that the protocol does not abort which means that all the rules are satisfied. The protocol can be split into two phases: (1) the connectivity phase and (2) the verification phase.

(1) Since P knows the solution, the white cells are connected and hence P can always select a black commitment in step 3a to swap it to white.

(2) For the lonely black verification, there is no configuration of two black cells that are touching horizontally nor vertically hence for every pair of adjacent cells, there is always at least one white cell.

For the liar verification, there is exactly (in each region) one numbered cell surrounded by a different number of black cells. Suppose, without lost of generality, that the liar cell is equal to i in a given region (the same result could be applied for each other region). When the sum of the four neighbours is done, the card at position (from left) i + 1 is ♣ otherwise the numbered card is not a liar. Thus when revealing the cards at the last step, there is always a ♣ card. ■ Theorem 2 (Soundness) If P does not provide a solution of the p × q Usowan grid, P is not able to convince V .

Proof Suppose that P does not provide a solution. If the white cells are not connected, then P cannot choose a neighbor commitment that P wants to change at step 3c. If there are two black commitments touching (or more), then the five-card trick will output 0; hence, V will abort. Finally, if there is not one liar exactly in a given region, then the last step of the verification will reveal either no ♣ or at least two ♣ s; hence, V will abort.

■ Theorem 3 (Zero-knowledge) V learns nothing about P 's solution of the given grid G.

Proof We use the same proof technique as in [START_REF] Gradwohl | Cryptographic and physical zeroknowledge proof systems for solutions of Sudoku puzzles[END_REF], namely the description of an efficient simulator that simulates the interaction between an honest prover and a cheating verifier. The goal is to produce an indistinguishable interaction from the verifier's view (with the prover). Notice that the simulator does not have the solution but it can swap cards during shuffles. Informally, the verifier cannot distinguish between the distributions of two protocols, one that is run with the actual solution and one with random commitments. The simulator acts as follows.

• The simulator constructs a random connected white polyomino. • During the lonely black verification, the simulator replaces the cards in the five-card trick introduced in Sect. 2.3 with ♡ ♣ ♡ ♣ ♡ . While the latter sequence is randomly shifted, this ensure that the protocol continues. • During the liar verification, the simulator simply replaces, in the last step, the cards to have exactly one ♣ and the rest as ♡ s. This ensure that there is exactly one liar in a given region, meaning that the protocol does not abort. The simulated and real proofs are indistinguishable and hence V learns nothing from the connectivity and verification phases. Finally, we conclude that the protocol is zero-knowledge. ■

ZKP Protocol for Five Cells

This puzzle is different from the two others presented here, as the player solving it must fill, not the cells themselves, but the edges between them. So the first step is to provide a specific setup to handle this difference. We thus need to add commitments between each cell, to encode lines forming regions; this is done by adding (q + 1) × p commitments in columns and (p + 1) × q commitments in rows. We depict this setup in Fig. 8 in case of (p, q) = (5, 3), where D denotes a red commitment as a dummy.

For encoding, we introduce another color, gray, to distinguish cells from lines. The four colors are encoded as follows:

♣ ♡ → black, ♡ ♣ → white, ♡ ♡ → red, ♣ ♣ → gray. In our ZKP protocol, either white or gray commitment is placed on each cell, and either black or red commitment is placed in-between, i.e., the color of its second card represents either a cell or a line.

We informally define our protocol for Five Cells, illustrated in Fig. 9, as follows:

(1) P puts commitments between cells as described above and accordingly to its solution.

(2) V verifies the number rule by taking commitments around the cell; then shuffle them to reveal all the commitments. If the number of black commitments is the same as the number written in the cell, then V continues.

(3) The goal for P is to construct a pentomino without V knowing which shape it is. Since the total number of pentominoes is known ( p×q 5 ), the following constructive step is done for each pentomino: P chooses two adjacent commitments and V checks that there is no line in-between (then repeated 5 times to form a pentomino).

Checking the Shape

Each delimited region must form a pentomino (i.e., composed of five connected cells). The shape is verified through the connectivity constraint using a variant of sub-protocol in Sect. 2.4.

However, we change the grid to add commitments representing the lines; so we cannot apply directly the sub-protocol of Sect. 2.4. Basically, the neighbours of a given cell have not the same distance when put in sequence but still follow the same evaluation. We give the corresponding distance in Table 1.

Notice that those distances are correct if the grid does not contain holes i.e., there are commitments between each cells. This means that we need to add dummy commitments D to fill the grid. They are red commitments and only used to balance the grid to enforce the results of Table 1. Setup: P and V prepare the grid. They add commitments representing the lines between each cell.

Connectivity:

P places lines according to the solution.

V only knows that the figures are composed of 5 cells.

Verification:

V verifies rule 2: by taking the commitments around numbered cells.

Fig. 9 Overview of our Five Cells protocol.

Finally, we must also add dummy commitments above the first row and on the left of the first column. This comes from the fact that commitments at the edge of the intial grid have no neighbour, but to avoid leaking information, we need to add dummy commitments. In the original protocol (see Sect. 2.4), there is only one row/column of such dummies but here we need to add two rows/columns to keep the correct distances about neighbours. So in total, we go from a p × q grid to a (2p + 1 + 2) × (2q + 1 + 2) = (2p + 3) × (2q + 3) grid (commitments between each cell and the outer part giving (2p + 1) × (2q + 1) grid and then two rows/columns on the left and bottom part of the grid). Table 1 Distance (given for initial grid of a p × q size) from a cell when all commitments are put in sequence (as in step (1) of protocol in Section 2.4.2).

Our Protocol for Five Cells

Setup. The initial grid is modified as explained in Section 4.1. Moreover, P applies its solution on the grid by putting black commitments to indicate edges and red commitments to indicate absence of edge, for each in-between cells. The commitments corresponding to actual cells of the grid is set to white by V .

Checking numbers (rule 2). The verifier V checks the rule number by applying the following, on each numbered cell with number i:

(1) V picks the four closest commitments (corresponding to the presence or absence of edges) and shuffles them.

(2) V reveals all the commitments and checks if the number of black commitments is equal to i. If so, V continues otherwise aborts.

(3) V puts back in their initial position the four commitments.

Checking pentominoes (rule 1). We have now all the material to verify the pentominoes. Repeat the following steps p×q 5 times:

(1) P chooses a white cell to begin its pentomino using the chosen-pile protocol.

(2) V reveals the commitment to check if it is white; if so, V turns it to gray and continues, otherwise aborts.

(3) P and V execute the 4-neighbour protocol and confirm that the target commitment is gray, but instead of taking one neighbour in each direction, they pick the two closest in each direction.

(4) V makes the second commitment to gray and reveal the first commitment; if it is red, then continues, otherwise aborts.

(5) P and V repeat steps 3 and 4 until a pentomino is constructed.

(6) P and V execute the chosen-pile protocol and check that the chosen commitment (inside the pentomino) is gray; if so, V turns it to black and continues, otherwise aborts.

(7) V takes the first cards of every two closest commitments (of the previously chosen commitment) in each direction, shuffles the eight cards, and reveals them; if they are four ♡ s and four ♣ s, then V continues; otherwise, aborts.

(8) P and V repeat steps 6, 7, and 8 four times.

When all the pentominoes are constructed, V reveals the commitments corresponding to the cells of the grid (not the commitment corresponding to the lines). If all the cells are black then V is convinced that rule 1 is respected.

Security Proofs for Five Cells

Our protocol needs to verify three security properties given as theorems. Note that the sub-protocols used from the literature have been proven secure i.e., they are correct, complete, sound and zero-knowledge.

Theorem 4 (Completeness) If P knows the solution of an Five Cells grid, then P can convince V .

Proof P convinces V in the sense that the protocol does not abort, which means that all the rules are satisfied. The protocol can be split into two phases: (1) verifying the number rule and (2) checking the shape.

(1) Since P knows a solution, the number of black commitments (i.e., lines) around every numbered cell should be equal to that number. Thus, revealing the black commitments (after shuffling) as in the protocol, this rule is verified.

(2) Even if any of four cells in a pentomino are colored with red, P can always find a white cell next to one of the red cells such that there is no line between them because P knows a solution. This means that P can always choose two white commitments starting from a red commitment via the 4-neighbour protocol at Step 3 such that the protocol never aborts. ■ Theorem 5 (Soundness) If P does not provide a solution of the p × q Five Cells grid, P is not able to convince V .

Proof Suppose that P does not provide a solution. We directly apply the soundness proof of [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF] for the connectivity since our variant could be seen as their connectivity sub-protocol (described in Sect. 2.4) by adding commitments between each initial cell. This means that their connectivity construction can be modeled as our encoding (i.e., with additional commitments) by considering that there is no line delimiting region, hence no region is formed.

Having checked the connectivity constraint, there is an additional property to check (which is out of scope for [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF]), the region are formed of five cells and no more (or less). If a region is not formed of exactly five cells then our protocol will detect it. Indeed, by adding a color to the encoding (i.e., gray), there is a verification about all cells in a region. Each neighbour of a cell (inside a region, and detected by the gray color) has each neighbour either gray with no line (i.e., both are inside the region) or white/red with a line between them (the cell is at the edge). When the pentomino is check then its color is turned to black, meaning that P cannot continue this pentomino to add cells. ■ Theorem 6 (Zero-knowledge) V learns nothing about P 's solution of the given grid G.

Proof We use the same proof technique as in [START_REF] Gradwohl | Cryptographic and physical zeroknowledge proof systems for solutions of Sudoku puzzles[END_REF], namely the description of an efficient simulator that simulates the interaction between an honest prover and a cheating verifier. The goal is to produce an indistinguishable interaction from the verifier's view (with the prover). Notice that the simulator does not have the solution but it can swap cards during shuffles. Informally, the verifier cannot distinguish between the distributions of two protocols, one that is run with the actual solution and one with random commitments. The simulator acts as follows.

• For the connectivity phase, the simulator simply draws random pentominoes to construct a tilling of the grid. Notice that this is not the solution with overwhelming probability but V will not abort at this point. • Now, for each numbered cell, the simulator swaps card to the corresponding number being equal to the number of black commitments (which is possible since there is a shuffle). Thus V will not abort. The simulated and real proofs are indistinguishable and hence V learns nothing from our protocol, so we conclude that the protocol for Five Cells is zeroknowledge. ■

ZKP protocol for Herugolf

The setup is straightforward since our protocol is constructive (P will construct its solution throughout the protocol).

We emphasize that all cells are considered as white commitments. Additionally, we place a black card ♣ under each commitment; this will be used later to mark the tip of the arrow. Let us call this row the tip row.

For clarity, suppose we need to construct the arrows depicted in Fig. 10. The following steps are done for each numbered cell (but examplify with the configuration of Fig. 10):

(1) V takes the four (corresponding to 4 ) commitments, and the four cards in tip row, in each direction to form four (one for each direction) piles p 1 , p 2 , p 3 , p 4 : Additionally, V reveals the commitment of the circle cell (here 4 ) and aborts if it is black; otherwise continues.

(2) P and V apply the chosen pile protocol to p 1 , p 2 , p 3 , p 4 so that P can hoose in which direction the arrow is formed.

(3) V reveals all the commitments of the chosen pile; V aborts if there is at least one black commitment (meaning that there is already another arrow).

Then V swaps all commitments so that all the commitments are now black.

(4) Before replacing back the piles, V replaces a red card under the last commitment (the number 4 of the pile) in tip row: (6) V reveals the tip row corresponding to cells in the gray area. This ensures that rule 3 is respected.

(7) Seeing Fig. 10, P wants to continue the path by constructing arrows of sizes 3 and 2, but an arrow of size 1 is not needed. Let k denote the length of the next arrow we consider (i.e., k = 3 for this example). Let ℓ denote the length of the last arrow P wants to construct (i.e., ℓ = 2). At this step, we create k commitments, each of which will be used at step 9, as follows.

(a) V prepares k commitments to 0, places a commitment to 1 on the right side of them, and places k -1 commitments to 1 on the left side of them. Then V places k + 2 cards representing ℓ encoded in the ♡-scheme and a face-down ♣ under them as follows.

? ? (b) V applies a pile shifting shuffle to the two sequences of cards placed at the previous step, regarding cards in the same column as a pile.

(c) V reveals all the cards of the bottom sequence. Then exactly one ♡ is revealed, and take the commitment above the revealed ♡ as well as the k -1 commitments to the right (apart from cyclic rotation). We call these k commitments CC 1 , CC 2 , . . . , CC k starting from the left.

(8) P wants to continue the path by constructing an arrow of size 3. The 4-neighbour protocol described in Section 2.4.2 is used except that 3 commitments are taken (except of just 1). The technique for Five Cells is used to know which commitment to take in the large sequence:

+1 +1p -1p -1 +2 +2p -2p -2 +3 +3p -3p -3
where the tip is denoted by the middle triangle. Note that V knows which cell corresponds to the tip by revealing a card in tip row.

(9) P applies the chosen pile protocol to choose its direction to form the next arrow, and prepares two identical commitments ♣ ♡ (if P wants to not draw the arrow anymore, he would have chosen ♡ ♣ ). For this, P takes CC 1 created at step 7, and V copies it with the copy protocol of Section 2.2 (this ensures that the same commitments are used).

(10) V places the three commitments chosen at the previous step, CC 1 , and additional cards, forming two piles p 1 , p 2 :

CC ′ ♣ ♡ CC 1 ? ? 1 ♡ ♣ 2 ♡ ♣ 3 ♡ ♣ ? ? ? ? ? ? p 1 p 2
where CC ′ denotes a commitment specifying the "real" arrow. V then turns over all the face-up cards, shuffles the two piles p 1 , p 2 , and reveals CC 1 . Then either ♣ ♡ or ♡ ♣ is revealed, and V reveals the three commitments above the revealed ♡ ; V aborts if there is at least one black commitment. Finally, V swaps them so that they are now black.

(11) V shuffles p 1 and p 2 again and reveals CC ′ . Then we derive the "real" arrow above the revealed ♡ .

(12) The commitments are swapped with P 's solution and without V knowing if there is an arrow. Now, this step ensures that the tip of the arrow is marked on the newly created arrow (if so) or stays on the previous one. For this, V uses the second commitment of CC 1 (the first one has been used in the previous step) by replacing them with the cards of tip row. Concretely, V replaces the ♡ card of tip row by the left card of CC 1 and the card under the third commitment by the right card of CC 1 :

CC 1 ? ?

tip row ? ? ? ?

? ? ? ? ? ? commit. (13) Put back all the commitments in their respective position in the grid.

V reveals the tip row corresponding to the gray area; this ensures that no tip is placed on those forbidden cells thus ensuring rule 3. ( 14) P and V repeat steps 8 to 13 by decreasing the length of the arrow 1 and takeing a commitment sequentiall starting from CC 1 until reaching a length arrow equal to 1.

Verification Phase

V simply reveals the tip row of the "H" cells to check that the tip is a ♡ (meaning that each numbered cell is connected with a hole and that every arrow ends at a hole).

Security Proofs for Herugolf

As before, our protocol needs to verify three security properties given as theorems. Note that the subprotocols used from the literature have been proven secure i.e., they are correct, complete, sound and zeroknowledge.

Theorem 7 (Completeness) If P knows the solution of an Herugolf grid, then P can convince V .

Proof P convinces V in the sense that the protocol does not abort, which means that all the rules are satisfied. In particular, each numbered cell is connected with a hole cell without crossing branches.

Firstly, given a numbered cell, an arrow is always depicted in a direction P chooses, and its tip is represented in tip row by executing steps 1 to 6. The length of the arrow is always the same as the number written on the given numbered cell because in step 3, V changes the same number of white commitments into black ones.

Next, CC 1 , CC 2 , . . . , CC k are derived in step 7. In the case of Fig. 10, each of them denotes the following commitment:

CC 1 = ? ? and in step 7(c), the commitment above the revealed ♡ is taken as CC 1 , i.e., a commitment to 0. CC 2 and CC 3 are the commitments to the right of CC 1 , i.e., , commitments to 0 and 1, respectively. For any case, CC i is always a commitment to 1 if CC i-1 is a commitment to 1 for 2 ≤ i ≤ k.

Finally, each of remaining arrows is depicted in the remaining steps. Because the cell where P strats depicting an arrow is represented in tip row (and is updated in step 12), P can always select such a cell using the 4-neighbour protocol in step 8. If P does not want to depict an arrow anymore and take CC i for some i in step 10, then CC i is always a commitment to 1 because P sets an appropriate value to ℓ in step 7. Thus, once an arrow approaching a hole is depicted, no more arrows must be depicted, and V never aborts in step 10 because the "dummy" arrow (i.e., commitments in p 1 ) is always revealed. In step 12, tip rowis updated by replacing the corresponding cards with CC i for some i. Because CC i is a commitment to 1 if and only if P does not want to depict an arrow, the cards in tip rowremains unchanged even if executing step 12. When CC i is a commitment to 0, the cards in tip roware updated so that the new tip is represented in an appropriate cell, and the old tip disappears. ■ Theorem 8 (Soundness) If P does not provide a solution of the p × q Herugolf grid, P is not able to convince V .

Proof We rely on the proof of [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF] for the connectivity construction, i.e., , arrows P depicts are always connected for each numbered cell using the 4-neighbor protocol. Notice that rule 3 is checked but revealing the tip row during the connectivity construction phase. ■ Theorem 9 (Zero-knowledge) V learns nothing about P 's solution of the given grid G.

Proof As in the previous proofs for the two other puzzles, we describe an efficient simulator. Informally, the verifier cannot distinguish between the distributions of two protocols, one that is run with the actual solution and one with random commitments. The simulator simply swaps cards to ensure that V will not abort. This is possible since each revealing step is preceded by a shuffle.

The simulated and real proofs are indistinguishable and hence V learns nothing from our protocol, so we conclude that the protocol for Herugolf is zeroknowledge. ■

Conclusion

We propose three ZKP protocols dedicated to convince a verifier that a prover has the solution without leaking any bit of information of the solution. Those protocols are designed for each of the following puzzles: Usowan, Five Cells and Herugolf. Those three puzzles share a common connectivity constraint but with additional specific constraints.

The design of the ZKP protocol for Usowan uses mainly the sum sub-protocol while Five Cells is design through an hybrid encoding of the commitments (for the cells but also for the edge delimiting the region). The proposed ZKP protocol for Herugolf is somewhat in extension of the connectivity protocol which allows to construct connected figures of given length.

Acknowledgment

We thank the anonymous referees, whose comments have helped us improve the presentation of the paper. The first and third authors were partially supported by the French ANR project ANR-18-CE39-0019 (MobiS5). Other programs also fund to write this paper, namely the French government research program "Investissements d'Avenir" through the IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01). Finally, the French ANR project DECRYPT (ANR-18-CE39-0007) and SEVERITAS (ANR-20-CE39-0009) also subsidize this work.

The second author was supported in part by Kayamori Foundation of Informational Science

Fig. 4 Five

 4 Fig.4Five Cells initial grid and its solution

Fig. 5

 5 Fig. 5 Rules for Herugolf.

Fig. 6

 6 Fig.6Herugolf initial grid and its solution

  If they are ♡ ♣ , then the four bottom cards are ? ?

Fig. 7

 7 Fig. 7 Configuration at step 1 in the chosen pile protocol

.( 3 ) 1 :

 31 Obtain three cards representing x 1 + r and those representing x 2 -r for a uniformly random value r ∈ Z/3Z as follows.(a) Place in reverse order the three cards obtained in Step 2 below the three cards obtained inStep

TsinghuaFig. 8

 8 Fig. 8 Commitments setup for a Five Cells grid of 5 × 3. Commitments represent line between regions. The notation D refers to dummy commitments.

4 HFig. 10

 410 Fig. 10 Example of our protocol for Herugolf

( 5 )

 5 P and V replace back all the commitments to their initial positions by ending the chosen pile protocol.

0, CC 2 = ? ? 0 , CC 3 = ? ? 1 ,

 01 because in step 7(a), the sequence of cards is placed by V and P as follows:

  b) V reveals the target commitment. If it corresponds to white, then V continues; otherwise V aborts.

(c) V reveals the neighbour commitment (chosen by P ). If it corresponds to black, then P makes the neighbour white or keep it black (depending on P 's choice) by executing the following steps; otherwise V aborts. * i. If P wants to change the commitment, P places face-down club-to-heart pair below it; otherwise, P places a heart-toclub pair: ? ? → ? ? ♣ ? ? ♡ or ? ? ♡ ? ? ♣ .

Tsinghua Science and Technology, xxxxx 20xx, 2x(x): xxx-xxx

† For a numbered cell in the edge of the board, compute the addition of its three or two neighbors.

Advancement and JSPS KAKENHI Grant Number JP23H00479. The fourth author was supported in part by JSPS KAKENHI Grant Numbers JP21K11881 and JP23H00479.


Aneta Gorczynska

Bernard Le Gall

Pierre Stéphan

Yvan Pailler

An interdisciplinary

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

An interdisciplinary approach to Recent/Final Neolithic coastal gallery graves in Brittany, France.

The 3D-structure, origin of rock material, and paleoenvironmental setting of the Kernic and Lerret monuments.

Aneta Gorczynska * 1 , Bernard Le Gall , Pierre Stephan 2 , and Pailler Yvan

Résumé

This project presents an interdisciplinary study carried out on two Recent/Final Neolithic gallery graves (Kernic and Lerret) located on the northwestern coast of Brittany (western France). These monuments show striking similarities in terms of architectural style and geographical position. This research aims to provide a better understanding of the construction strategy of these monuments by : (i) determining the origin of the megalithic blocks from petro-structural analyses, (ii) reconstructing the coastal environments from the analysis of sediment cores, and (iii) defining the place of these monuments in the territories from intervisibility analysis. The study reveals important differences between the two monuments. The Lerret gallery grave was erected in direct proximity to a unique source of rock material on the margins of a marshland zone. In contrast, the Kernic monument shows a deliberate diversification of stone extraction sites and was established on the edge of an estuary. An intervisibility analysis shows a dense network of visual interconnections between the megalithic tombs in the study area, in which the two monuments occupy very different sites. The social dimensions of stone selection and the geographical location of Recent/Final Neolithic funerary monuments are also discussed in an enlarged regional context.

Mots-Clés: : Gallery grave, Recent/Final Neolithic, megalithic tombs, rock material, coastal paleoenvironment, petro, structural, paleoenvironmental and intervisibility analyses

  Institut national de recherches archéologiques préventives, centre archéologique de Cesson-Sévigné (Inrap, Cesson-Sévigné) -Institut national de recherches archéologiques préventives -37 rue Bignon, CS67737, 35577 Cesson-Sévigné, France 4 Chaire Archéologie Maritime et Recherche Interdisciplinaire Environnementale (Chaire Armerie) -Institut national de recherches archéologiques préventives, Université de Bretagne Occidentale (UBO) : UMR6554 -Institut Universitaire Européen de la Mer Rue Dumont d'Urville, Technopôle Brest Iroise 29280 PLOUZANE, France

	3,4
	1 Laboratoire Geo-Ocean, UMR 6538 -Université de Bretagne Occidentale [UBO], CNRS : UMR6538,
	Ifremer, Brest -France
	2 Littoral, Environnement, Télédétection, Géomatique (LETG -Géomer) -CNRS : UMR6554,
	Université de Bretagne Occidentale (UBO) -Place Nicolas Copernic, 29280 Plouzané, France
	3