Léo Robert
email: leo.robert@uca.fr

Daiki Miyahara
email: miyahara@uec.ac.jp

Pascal Lafourcade
email: pascal.lafourcade@uca.fr

Takaaki Mizuki
email: mizukilncs@tohoku.ac.jp

Hide a Liar: Card-Based ZKP Protocol for Usowan

Keywords: Zero-knowledge Proof, Pencil Puzzle, Card-based Cryptography, Usowan

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. This is partly due to the fact that the solution should not be leaked during the protocol. In this work, we propose a card-based 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 some sense, we propose a physical ZKP for hiding of a liar.

Introduction

Usowan [1] 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: 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. 1

We depict in Fig. 1 an initial Usowan grid with its solution. Suppose that someone has found a solution for a given Usowan instance. Is it possible to design a protocol to convince anyone that he/she has the solution without revealing it? The answer 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.

More formally, a ZKP protocol is between two parties: a prover P who knows a solution s to a problem and a verifier V who wants to be sure that P is indeed in possession of the solution. However, no information about s should leak during the protocol (except the information recoverable without the help of the protocol). The 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.

Usually, ZKP protocols are executed by computers. We restrict ourselves by using only physical cards and envelopes. In this paper, we present a physical ZKP protocol for Usowan. 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 the verifier could compute the secret in polynomial time). Hopefully, 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.

Contributions. We construct 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 use cards and envelopes. Moreover, we propose 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. For this, we use several sub-protocols to verify the rules and propose a completely novel ZKP protocol.

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 Boer | 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 | Card-based 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 zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Takuzu [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF][START_REF] Miyahara | Card-based ZKP protocols for Takuzu and Juosan[END_REF], Kakuro [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF][START_REF] Miyahara | Card-based physical zero-knowledge proof for Kakuro[END_REF], KenKen [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Makaro [6,[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], 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], Nurikabe [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF], Ripple Effect [START_REF] Ruangwises | Physical zero-knowledge 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], 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 protocol. We also recall the existing card-based simple protocols of the literature that we use in our construction. In Sect. 3, we present our ZKP protocol for Usowan. We give in App. D the security proofs of our protocol.

Overview of our protocol. Before detailing our protocol and exisiting subprotocols involved, we present an intuition of our construction (see Fig. 2). We represent a colored cell by placing colored cards on the cell. In the connectivity phase, P and V construct a connected figure according to P 's solution without V knowing the exact shape. Thus, V is convinced that the resulting face-down cards satisfy the rule 2 (and the rule 1 can be easily verified by just revealing face-down cards on numbered cells).

Setup: P and V prepare the grid.

Connectivity: P constructs a shape according to the solution. V only knows that the figure P constructed is connected (rule 2 is verified). V reveals the colors of numbered cells (rule 1 checked).

Verification:

V verifies the remaining rules: • rule 3: each pair of adjacent cells is checked using a disjunction (white= 1 and black= 0).

• rule 4: sum the numbers of the neighbours around numbered cells.

Protocol: How to form a white polyomino (Sect. 2.4) Protocol: Five-card trick (Sect. 2.3) Protocol: Sum (Sect. 2.5)

Fig. 2. Overview of our protocol

Then, in the verification phase, V checks the two remaining rules. The rule 3 forces two adjacent cells to be composed of at least one white cell; this rule is verified by computing a disjunction of each possible pair. For verifying the rule 4, P and V compute the number of blacks around a given numbered cell. The result is represented as a sequence of face-down cards where the value is given by a position in the sequence. By revealing the card of position equal to the number written on the cell, V checks if the sum is equal or not (without knowing the exact value if different) to the numbered cell.

Preliminaries

We explain the notations and sub-protocols used in our construction; some of them are detailed in appendix while the general idea is given below. We first introduce the general framework of card-based protocols.

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. (1)
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.

Pile-shifting shuffle [26, 38]

This shuffling action means to shuffle piles of cards cyclically. More formally, given m piles, each of which consists of the same number of facedown 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+2 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.

Mizuki-Sone Copy Protocol [22]

The following protocol is used for copying commitments. We need it as a commitment can be used for several destructive2 computations (here an addition). Given a commitment to a ∈ {0, 1} along with four cards ♣ ♡ ♣ ♡ , the Mizuki-Sone copy protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] outputs two commitments to a. We specifically describe the protocol in Appendix A.

? ?

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

Input-preserving five-card trick [16]

This sub-protocol is used during the verification phase (see Sect. The original sub-protocol [START_REF] Den Boer | More efficient match-making and satisfiability: The five card trick[END_REF][START_REF] Miyahara | Card-based ZKP protocols for Takuzu and Juosan[END_REF] was designed for AND (a ∧ b), but we adjust it to compute OR (a ∨ b). We give the detailed description in Appendix B.

How to Form a White Polyomino [28]

We introduce the idea of the generic method of [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF] to perform the connectivity of colored cells without revealing any information about the resulting cells. We leave in Appendix C the details of the protocol. First, all commitments on a grid of size p × q are black, and P chooses a commitment to turn it white (without V knowing which cell); we use the chosen-pile described in Appendix C.1 for this. Then P chooses a commitment next to the previous commitment to either turn it white or leave it black; V is ensured that both commitments are neighbours (i.e., two adjacent cells) using a sub-protocol described in Appendix C.2. This step is repeated pq -1 times to ensure that V does not know the number of white cells at the end of the protocol. Finally, each time a white commitment is created, V only knows that it is adjacent to another white commitment; thus V is convinced that the figure composed of white commitments is connected without knowing the number of cells.

Sum in Z [34]

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 : ? ?

x 1 ? ?

x 2 ♣ ♡ → ? ? ?

x 1 +x 2 .

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:

-→ ←-? ?

x 1 ? ♣ → ? ? ?

x 1 .

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

x 2 ? ♡ → ? ? ?

x 2 .

3. 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 in Step 1:

? ? ?

x 1 ? ? ?

x 2 → ? ? ?

x 1 ? ? ? ? ?

? ? ? ? → ? ? ?

x 1 +r ? ? ?

2-x 2 +r
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: ? ? ?

x 1 +r ? ? ?

x 2 -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 fivecard trick introduced in Sect. 2.3 to the two commitments to compute their disjunction. We consider here 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 3 .

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).

Conclusion

We propose a physical ZKP protocol for Usowan, which has an interesting rule: some information on the initial grid are incorrect. For verifying such constraints without revealing knowledge about the solution, we construct a protocol based on computing the sum [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF]. With this trick we are able to prove that we can hide exactly one liar in each room. The next step will be to see how we can propose a cryptographic ZKP protocol to prove that someone is lying. This is clearly not easy and might require complex and modern cryptographic primitives while we are able to do it only with cards and envelopes in real life.

A Mizuki-Sone Copy Protocol [22]

The protocol proceeds as follows. 41. 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-to-black represents 1 according to Eq. ( 2).

B Input-preserving Five-card Trick [16]

The sub-protocol proceeds as follows.

1. Add helping cards and swap the two cards of the commitment to a so that we have the negation b, as follows:

? ? a ? ? b → ? ? a ♡ ? ? b ♡ ♣ ♣ ♣ ♣ .

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.

C How to Form a White Polyomino

Before explaining the protocol, we need to describe two crucial subprotocols first, namely the chosen pile protocol and the 4-neighbour protocol.

C.1 Chosen Pile Protocol [9]

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. 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 i-th 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 face-down cards (denoted by row 2) below the given piles such that only the i-th card is ♡ . We further put m cards (denoted by row 3) below the cards such that only the first card is ♡ :

? p 1 ? p 2 . . . ? p i-1 ? p i ? p i+1
. . . ? 2. Considering the cards in the same column as a pile, apply a pileshifting shuffle to the sequence of piles. 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.

C.2 Sub-protocol: 4-Neighbour Protocol [28]

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). 5This sub-protocol proceeds as follows.

1. P and V pick the (p + 1)(q + 1) commitments on the grid from leftto-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.

C.3 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 white-polyomino 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 commitment to black (i.e., ♣ ♡ ) on every cell and commitments to red as mentioned in Sect. 2.4 so that they have (p + 1)(q + 1) commitments on the board. 2. P uses the chosen pile protocol to choose one black commitment that P wants to change.

(a) V swaps the two cards constituting the chosen commitment so that it becomes a white commitment (recall the encoding (1)). (b) P and V end the chosen pile protocol to return the commitments to their original positions. 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. (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 ). 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.

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).

D 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 choose a black commitment at step 2 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 zero-knowledge 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.

Fig. 1 .

 1 Fig. 1. Initial Usowan grid and its solution taken from [1].

  3.3) for the lonely black rule (rule 3). Given two commitments to a, b ∈ {0, 1}based on the encoding rule (2), this sub-protocol[START_REF] Den Boer | More efficient match-making and satisfiability: The five card trick[END_REF][START_REF] Miyahara | Card-based ZKP protocols for Takuzu and Juosan[END_REF] reveals only the value of a ∨ b as well as restores commitments to a and b:

2-x 2 (

 2 b) Apply a pile shifting shuffle as follows:

3 . 4 4.

 34 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). Example:b a 3 c d -→ a + b + c + d = ?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.

  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 ? ? a ? ? a . (b) If they are ♡ ♣ , then the four bottom cards are ? ? a ? ? a .

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

	? ?	? ?	→	? ? ? ? .
				If it corre-
	sponds 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-to-club
	pair:
	? ? → ?
		?

♣ ? ? ♡ or ? ? ♡ ? ? ♣ .

ii.

This means that commitments used in the computation cannot be placed back with its initial value. A non-destructive protocol is called input-preserving (see Sect. 2.3).

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

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 pileshifting 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].

Here, 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.

Acknowledgements. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported in part by JSPS KAKENHI Grant Numbers JP21K11881 and JP18H05289. This study was 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 Ávenir" 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.


Victor Charpenay
email: victor.charpenay@emse.fr

Matteo Baldoni
email: matteo.baldoni@unito.it

Andrei Ciortea
email: andrei.ciortea@unisg.ch

Stephen Cranefield
email: stephen.cranefield@otago.ac.nz

Julian Padget
email: j.a.padget@bath.ac.uk

P Singh
email: mpsingh@ncsu.edu

Governing Agents on the Web (Blue Sky Ideas)

This paper investigates the interplay of multiagent systems (MAS) with the Web to identify research challenges related to the governance of Web-based MAS. We first consider as a case study the process for allocating donated bodily organs to potential transplant recipients. We then discuss candidate architectures for governance in Web-based MAS that would support this scenario, from which we derive several research questions that emerge in pursuing the aim of agents on the Web.

Introduction

There are significant similarities in the motivations behind multiagent systems (MAS) and the Web. Both disciplines and practices seek to advance decentralization and openness in that ideally there isn't a single locus of control and participants can behave and interact broadly autonomously under local control.

This paper addresses the interplay of multi-agent systems with the Web. Specifically, it concerns how constructs and techniques identified in the study of the governance of MAS be realized over the Web architecture and how the governance of the Web be beneficially structured based on constructs and techniques developed for the governance of MAS. In simple terms, it seeks to identify synergies in both these directions:

-What does the Web offer to support the governance of MAS?

We anticipate ways to use the interoperability and scalability of the Web to build easy-to-use, widely deployed MAS. Scalability, evolvability, and visibility are important non-functional requirements that are "guaranteed" if a system's architecture relies on the Web.

-What does the governance of MAS offer the Web?

We anticipate approaches for governance that provide flexibility and local control with formal models that support correctness and generality going beyond the typically procedural kinds of governance seen on the Web today. A challenge here is to map abstract models for governance in MAS to Web components, in a way that preserves Web architectural constraints and thereby guarantees the associated non-functional requirements of scalability and decoupling.

The main contribution of this paper is an identification of some of the crucial challenges pertaining to the interplay of MAS and the Web, and the formulation of some initial research questions that might guide future research on this topic.

Key Concepts and Considerations

MAS Concepts

There are three terms, as discussed here, in relation to MAS that are key to the exploration of the question of MAS and the Web, namely norms, governance and institutions. We put forward some general-purpose intuitions about each of those to ground the discussion that follows.

The notion of norm was well-established in other disciplines (social science, law, logic) before its importation into MAS, as signalled by [START_REF] Shoham | On the synthesis of useful social laws for artificial agent societies (preliminary report)[END_REF], amongst others. Much work in MAS tends to draw on [START_REF] Wright | Norm and Action: A Logical Enquiry[END_REF], which established the logic of forbidden, permitted and obliged actions or states of affairs, which Von Wright developed further [START_REF] Wright | Deontic logic: A personal view[END_REF] for the legitimate expectations of behaviour.

Both North [START_REF] North | Institutions, Instutional Change and Econonomic Performance[END_REF] and Ostrom [START_REF] Ostrom | Governing the Commons. The Evolutions of Institutions for Collective Action[END_REF] approach the matter of constraining behaviour from orthogonal economic perspectives, through the recognition of the notion of institution as a (consistent) set of norms that work together to support stakeholders goals.

Ostrom [START_REF] Ostrom | Governing the Commons. The Evolutions of Institutions for Collective Action[END_REF] however starts from the question of governance, in that she observes the process by which the norms are developed and refined into an institution, which is captured in the ADICO framework and the eight rules that she puts forward to characterise the circumstances of such social institutions. This is of course not the only model of governance and of institution creation, but it does provide great insight into normative structures that unite social and legal institutions.

Our goal here is to consider how these three concepts may be realised outside the controlled environment of a particular MAS platform and transplanted into the global computation ecosystem of the World Wide Web.

Web Concepts

We understand the Web as a combination of uniform resource identifiers (URI) supporting hyperlinked representations, along with a computational architecture that supports locating and accessing the identified resources. The computational architecture is based on standard protocols for manipulating resources (e.g., HTTP, CoAP). We think here of architectural constraints (such as for caching, layering, and uniform interaction) as captured by the original design rationale behind the Web Architecture [START_REF] Fielding | Principled design of the modern web architecture[END_REF]. The W3C Recommendation for the Web Architecture [START_REF] Jacobs | Architecture of the world wide web, volume one[END_REF] provides additional information on identification, interaction, and representation of resources on the Web. Linked Data principles [START_REF] Heath | Linked Data: Evolving the Web into a Global Data Space[END_REF] characterize the relevant constraints for large-scale data sharing, which can be supplemented by ontology specification [START_REF]W3C: OWL 2 Web Ontology Language: Document overview[END_REF] in general. Recent W3C Recommendations for the Social Web, including Linked Data Notifications, ActivityStream, ActivityPub and WebSub [START_REF] Guy | Social web protocols[END_REF], offer ways to develop social applications under Web architectural constraints.

Some extensions to the above computational and information architectures, such as through the observer pattern (implemented in CoAP [START_REF] Shelby | The Constrained Application Protocol (CoAP)[END_REF]) and local state transfer [START_REF] Singh | LoST: Local State Transfer-An architectural style for the distributed enactment of business protocols[END_REF], aim at moving from a Web of Documents [START_REF] Fielding | Reflections on the REST architectural style and "principled design of the modern web architecture[END_REF] towards a Web of Things [START_REF] Lagally | Web of things (WoT) architecture 1.1[END_REF] and a Web of Agents, in which interactions are highly asynchronous and potentially lossy.

Relating MAS and the Web

There exist numerous studies that relate the Web with MAS, following two general trends. Some studies focus on applying RDF and Linked Data to expose agents to hypermedia-driven environments [START_REF] Dikenelli | Where are all the semantic web agents: Establishing links between agent and linked data web through environment abstraction[END_REF][START_REF] Ciortea | Engineering world-wide multi-agent systems with hypermedia[END_REF][START_REF] O'neill | Delivering multi-agent microservices using cartago[END_REF][START_REF] Charpenay | A unifying framework for agency in hypermedia environments[END_REF]. Other studies combine a formal declarative model of norms [START_REF] Cliffe | Specifying and reasoning about multiple institutions[END_REF][START_REF] Singh | Norms as a basis for governing sociotechnical systems[END_REF][START_REF] Chopra | Custard: Computing norm states over information stores[END_REF] to specify social protocols [START_REF] Chopra | From social machines to social protocols: Software engineering foundations for sociotechnical systems[END_REF]. Such social protocols provide a more thoroughly decentralized conception of Berners-Lee's [START_REF] Berners-Lee | Weaving the Web: The Original Design and Ultimate Destiny of the World Wide Web[END_REF] notion of social machines.

Dimensions that are common to all MAS architecture, such as the environment, organization and interaction dimensions, are defined at a higher level of abstraction than Web resources and protocols. Constraints such as caching, layering and uniform interaction apply to components, exposing a certain functionality through ports. Web components may only have client or server ports, exchanging messages in a standard protocol. Components with client ports only are called origin clients, those with server ports only are origin servers and a third kind of components, proxies, have an equal number of client ports and server ports, forwarding requests from clients to servers or vice-versa [START_REF] Fielding | Principled design of the modern web architecture[END_REF].

To be able to analyse the interplay between MAS and the Web, a mapping from MAS abstractions to (more concrete) Web components is necessary. Given the complexity of both fields, there is no trivial mapping and most likely not a unique mapping across the two levels of abstraction. In the following, we perform a case study to help identify mappings that would preserve effective governance mechanisms developed in MAS research.

Case Study: Organ Allocation

As a case study, we consider a simplified version of the process for allocating donated bodily organs to potential transplant recipients [START_REF] Vázquez-Salceda | The organ allocation process: A natural extension of the Carrel agent-mediated electronic institution[END_REF]. Due to the scarcity of organ donors, the limited period of organ viability after removal from the donor, and the desire to maximise the chances of a successful outcome, national bodies such as the United Network for Organ Sharing (UNOS) 7 , in the United States, or the Organización Nacional de Trasplantes (ONT) 8 , in Spain, have been formed to manage organ waiting lists, match donors with recipients, and develop and monitor policies governing this process.

Carrel Revisited

Vázquez-Salceda et al. [START_REF] Vázquez-Salceda | The organ allocation process: A natural extension of the Carrel agent-mediated electronic institution[END_REF] present the design of Carrel, using an agent-mediated electronic institution (e-institution) [START_REF] Noriega | Agent-Mediated Auctions: The Fishmarket Metaphor. No. 8 in IIIA Monograph Series, Institut d'Investigació en Intel.ligència Artificial (IIIA)[END_REF] for the organ allocation process. This design specifies in a formal manner [START_REF] Esteva | Formalizing a language for institutions and norms[END_REF] the structure of the interactions between hospitals, tissue banks, and institutional agents managing the process, as well as the norms that govern these interactions and the match between a donor and recipient. The distribution of organs and tissues in Carrel, given its Spanish congtext, would be overseen by the Spanish ONT, together with the Catalan Organitzaciò CATalana de Trasplantament (OCATT) 9 .

The Carrel platform is conceived to model the servicing of hospitals by connecting them with sources of tissues and organs, where the goal is to provide the best matched organ or tissue across all the sources registered with the platform. The interpretation of best is complicated and depends on a variety of factors that change over time, particularly in the case of organs. A strong requirement for a capacity for evolution motivated the development using an e-institution, made concrete through explicit computable norms. Because capacity for evolution is one of the main properties of the Web, Carrel offers an interesting case study through which to start motivating our research questions.

Tissue distribution is essentially demand-driven because tissues can be preserved and stored over extended periods with no significant degradation. Organ distribution is essentially supply-driven because the need is known before a suitable part becomes available. For the purposes of this paper, we only consider organ distribution where the need is known before availability.

Each hospital interfaces with Carrel through its Transplant Coordination Unit (TCU). A surgeon can request an organ or tissue via this unit which leads to the creation of an agent whose task it is to join the Carrel institution to obtain an organ or tissue that satisfies the surgeon's requirements. The requirements include the urgency of the request, hospital authentication information, organ/tissue data, recipient data, and a set of constraints on the organ or tissue.

To achieve its goal, the requesting agent must negotiate with other agents representing hospitals with potential donors 10 All agents are subject to behavioral norms that, if violated, are sanctioned. In the original version of Carrel, which was based on the ISLANDER framework [START_REF] Esteva | ISLANDER: an electronic institutions editor[END_REF], participating agents are in effect regimented by so-called governor agents, to prevent non-compliance. Here, we make the more general assumption that agents are regulated by norms and may choose to take non-compliant actions. Thus, we assume that agent actions in this contemporary Carrel are all visible to the regulatory bodies, as is the case in the physical world: hospital TCUs communicate their requests to members of ONT/OCATT, who then contact other hospitals to find a donor and select the best match.

In the course of the negotiation, hospitals may be tempted to behave unfairly towards others. They may want to provide incorrect information to ONT/O-CATT to maximize their chances of finding a matching donor. The sanctioning power of ONT/OCATT is therefore essential. If the Carrel institution is to be cast as an (institutional) environment deployed on the Web, this sanctioning power should be retained by the environment. For the purposes of this paper, we consider a simple norm guaranteeing fair allocation of donors: a requesting agent must not accept a organ/tissue if it was previously offered a better match (with respect to criteria defined by the institution). The associated sanction is that the institution may reject any future request made by the violating agent.

Norms and Roles

Following one approach from the MAS literature [START_REF] Chopra | Protos: Foundations for engineering innovative sociotechnical systems[END_REF], we can capture the sociotechnical system requirements in terms of accountability [START_REF] Chopra | Accountability as a foundation for requirements in sociotechnical systems[END_REF] and only then proceed to identify the information exchanges between the agents and from there their individual actions.

For concreteness, in the example below, we adopt the Custard notation [START_REF] Chopra | Custard: Computing norm states over information stores[END_REF]. The language is based on a conventional relational model. We can think of each predicate, such as Registered and Certify, as mapping to a relation and containing event instances. Additional relations are computed from the norm semantics: these include violated(AcceptBestMatch), which refers to the event of the AcceptBestMatch norm being violated. In Listing 1, the concerned roles are institution and hospital. A computational entity representing the stakeholder playing the institution role is empowered to revoke the certification of an agent representing the stakeholder playing a hospital role. The power is instantiated when a hospital is registered and applies when it violates the AcceptBestMatch norm.

Listing 1. OCATT's power to revoke certification in Custard. Here, "power" is the norm type, "DecertifyPower" is its schema name, the IDs refer to the parties concerned with the "by" indicating who has power over whom; "create" is the event with which the schema is instantiated, "detach" is the event under which it goes into effect, and "discharge" is the event that describes what the power brings about. As in SQL, the attribute (column) names are elided but the matches (joins) take place based on their values.

power D e c e r t i f y P o w e r h o s p i t a l I D by i n s t i t u t i o n I D c r e a t e R e g i s t e r e d d e t a c h v i o l a t e d ( A c c e p t B e s t M a t c h ) d i s c h a r g e n o t C e r t i f y

Allocation Protocol

We provide an overview of the (simplified) negotiation protocol followed by TCU agents. The agent holding a surgeon's request for transplantation sends its request to another agent, which answers with a donation offer. The requesting agent has then the choice of confirming or rejecting the offer, presumably depending on the strength of this match vis à vis any other offers it may have received from other prospective donor hospitals.

Listing 2 shows a simple protocol in the Blindly Simple Protocol Language (BSPL) language [START_REF] Singh | Information-driven interaction-oriented programming: BSPL, the Blindingly Simple Protocol Language[END_REF]. Some message parameters are adorned out, meaning the sender can set them freely (constrained only by key integrity); the sending of a message generates a binding for each such parameter. Other parameters are adorned in, meaning the sender must know the binding prior to sending the message, which means it must have obtained the binding from a previous message it sent or from a message it received from another agent. In particular, the requesting agent must obtain a certificate to confirm or reject an offer. This certificate must be obtained by some system component that embodies ONT/O-CATT, which may or may not deliver it, depending on prior violations made by the agent. The protocol of Listing 2 assumes the certificate is known prior to this protocol being enacted, which fact is indicated by the in adornment on the parameter recipientCertificate. The norm of AcceptBestMatch would apply to how this protocol is enacted and the norm DecertifyPower builds on top of AcceptBestMatch. To give DecertifyPower teeth, the information architecture must be such that the requisite information is available to the concerned party (i.e., the institution).

Norm Representation and Monitoring

Over the last 30 years, researchers in MAS have proposed many approaches to reasoning about norms as well as computational approaches to monitoring a MAS for norm violations [START_REF] Conte | Introduction: Agents and norms: How to fill the gap?[END_REF][START_REF] Boella | Introduction to normative multiagent systems[END_REF][START_REF]Handbook of Normative Multiagent Systems[END_REF]. A crucial aspect of this work is to provide a formal representation of norms (see, e.g., [START_REF] Cranefield | Modelling and monitoring interdependent expectations[END_REF] for an overview of approaches). Here we choose one possible representation of the AcceptBestMatch norm for illustrative purposes (Listing 3). Using the Expectation Event Calculus (EEC) [START_REF] Cranefield | Agents and expectations[END_REF], we can express the norm as a conditional rule of expectation, i.e. one that introduces a constraint on the future, that should be monitored for fulfilment or violation, once a condition is satisfied. The first argument of this rule checks the record of messages, assumed to be recorded as event calculus 'fluents', for the existence of an organ request and offer that match with a quality Q1. If that condition is satisfied, an instantiation of the second argument is created within an expectation fluent, stating that it should never be the case that another offer with a lower match quality has been made then (eventually) confirmed by the recipient.

The EEC engine will track this expectation over time as new information arrives, and will create a violation event if such a confirmation occurs. Further reasoning with related norms may conclude that an associated sanction should be applied or that a compensating action should be performed. Here, the EEC engine is an example of an active component of an MAS governance system that should be accommodated within any architecture for governance of agents on the Web.

Candidate Architectures

On the Web, "effective" power is held on the server side: servers may hide information, redirect requests or reject them, thereby reducing the action space of agents. It is natural to think of institutions as components with a server port, receiving requests from the client port of agents, such as described in [START_REF] Padget | Deontic sensors[END_REF]. Several candidate architectures offer various level of control, however. We have identified four classes of components for institutions (see Table 1). Autonomous agents differ from classical user agents in the Web architecture (i.e., browsers). In particular, an autonomous agent might require both client and server roles simultaneously and can have one-sided elementary interactions, where they are not awaiting a response. The requirements of autonomous agents are closer to the ones of servients in the W3C Web of Things Architecture [START_REF] Lagally | Web of things (WoT) architecture 1.1[END_REF] lingo, which are components with both client and server roles that can interact in a peer-to-peer manner. An agent could be implemented as such a component, or it could be a process that runs in a runtime environment provided by such a component. If the agent is visible to other agents, i.e. if its representation is dereferenceable, the representation can point, for instance, to a Linked Data Notification inbox that receives messages from other agents [START_REF] Capadisli | Linked data notifications[END_REF].

In a typical MAS, an institution may not materialize as a Web component at all. If norms are defined at design time, agents are guaranteed to behave (in general) as per these norms. Certification may also occur at design time, such that an agent either uses a single certificate throughout the system's lifetime or periodically renews its certificate as long as its behavior specification does not change. In the above configuration, however, the institution has no sanctioning power at run time. It cannot easily redesign the normative framework in which agents interact either. Updating a norm would potentially require modifying the behavior of all agents at the same time.

Institution as Read-Only Server

Figure 1 illustrates one possible architecture. The behavior of an agent may easily be decoupled from the normative framework that regulates it, though: if norms are exposed by a read-only (origin) server, an agent may dereference the norms from time to time and internalize whatever formal specifications the server returns.

In this alternative configuration, the institutional component gains the power of dictating norms and changing them at run time. The ability of agents to get

Institution as Read-Write Server

In order for the institution to gain sanctioning power, another component may manage its real-time state.

The state of the institution includes the level of obedience of each participating agent, which is directly derived from the confirmations/rejections they generate. To be able to maintain its state, the new institutional component must be able to observe each agent-to-agent interaction. For instance, the certificate may be signed not for an agent but for a pair (agent, donation offer ID), forcing agents to request a new certificate every time they make a decision. If the certification server stores a history of confirmations/rejections, it effectively becomes an institutional component that is capable of deciding in real time whether agents violate norms and, if they do, to sanction them by rejecting their certification request.

The institutional server would become a stateful read-write component, as agents, through their certification requests, change the state of the overall institution. Yet, it remains a purely reactive component, with a single server port.

Institution as Proxy

In the above configuration, the institutional component has no knowledge of how agents negotiate. If the institution is to be omniscient, another kind of component should be used. On the Web, it is common to use proxy servers to monitor activity.

The main architectural constraint over proxies is that they have a client port and a server port, such that incoming requests (on the server port) are Fig. 3. Architecture for an institution governing Web agents: Institution as Proxy either immediately responded to or forwarded to another server, possibly after a rewriting step.

In our working example, the institutional server may be replaced by a proxy without modifying in any way the behavior of agents. Agents send requests to the proxy, which can keep track of negotiations and add a certificate on-the-fly if the requesting agent behaves properly. The proxy may also turn a confirmation into a rejection, to sanction any misbehaving agent. The requesting agent receives feedback on the sanction through the other agent (which acknowledges the rejection, instead of the initial confirmation).

Institution as Servient

An alternative is to capture the institution as an explicit stakeholder supported by an agent on par with the other parties in the system. The institution becoming both reactive and proactive, it must include independent client and server ports and becomes a minima a servient.

In ordinary operations, this agent may have little to say beyond conveying institutional norms and facts as in the previous approach. (In some real-life cases, the institutional agent is the same as a member of the system taking on that additional role.) However, by identifying this institutional entity, we make it subject to accountability. As a result, we can more perspicuously model the accountability relationships between the concerned parties than otherwise. A party can also question the institution, for example, if they fail to receive an organ in a timely fashion. This process may result in the institutional facts being disputed and adjudicated [START_REF] Telang | Combining practical and dialectical commitments for service engagements[END_REF] and the norms potentially revised.

If the institution is embodied by a agent, its monitoring and sanctioning power doesn't depend on architectural constraints (at the level of Web components) but on the behavior of other agents (at the level of MAS abstractions).

Hypermedia-driven Interaction

In the previous section, we discussed several alternatives for implementing institutions as Web components. To promote interoperability on the open Web, agents should be agnostic to such implementation details. This can be achieved by hiding the specifics of a configuration behind a (semantic) hypermedia layer.

To this end, hypermedia-driven interaction can support autonomous agents to interact with Web resources in a uniform way while being decoupled from the underlying components. Most prominently, this approach is used on the Web of Things to decouple clients from Web-enabled devices by hiding the interfaces used to access the devices behind abstract interaction possibilities and hypermedia controls. To illustrate how this works, an HTML page typically provides the user with a number of action possibilities, such as navigating to a different page by clicking a hyperlink or sending an order by filling out and submitting an HTML form. Performing any such action transitions the user to a new page and exposes a new set of possible actions. In each step, the user's browser retrieves not only an HTML representation of the current page from a server but also the hypermedia controls required to transition to new pages. Retrieving all this information through hypermedia allows websites to evolve without impacting the browser, and allows the browser to transition seamlessly across components. Hypermedia-driven interaction reduces coupling between components (e.g., browsers, proxies, origin servers) and allows them to be deployed and to evolve independently from one another-a central feature that allowed the Web to scale up to the size of the Internet.

In the context of an institution on the open Web, the various action possibilities-such as retrieving formal specifications of norms, requesting a certificate, or sending messages to other agents-can be made available to the agents through hypermedia controls. Such hypermedia controls would encapsulate all the information required by an agent to interact with the component(s) that implement the institution, but to use the hypermedia controls in a reliable manner the agent would have to operate on an abstract model of the institution. For example, if an agent is required to obtain a certificate at run time to enact the Organ Donation protocol in Section 3.3, the agent could discover such an action possibility through hypermedia-but the agent would have to be aware of the notion of a certificate and should have the ability to request a certificate at run time.

In long-lived Web-based MAS, the institutional model could also evolve throughout the agents' lifetime-for example, from using norms and certificates defined at design time to a model based on an evolving set of norms [START_REF] Savarimuthu | Norm creation, spreading and emergence: A survey of simulation models of norms in multi-agent systems[END_REF] and certificates that have to be obtained at run time. Such an evolution would be reflected in the hypermedia environment through the set of action possibilities provided to agents at run time-and thus, to cope with this evolution, the agents would have to adapt by synthesizing a new course of action that meets their design objectives. While engineering such agents is still an open challenge, some related work investigates the design of agents able to plan and adapt to dynamic hypermedia environments (e.g., see [START_REF] Kovatsch | Practical semantics for the internet of things: Physical states, device mashups, and open questions[END_REF][START_REF] Ciortea | Repurposing manufacturing lines on the fly with multi-agent systems for the web of things[END_REF]).

Discussion: Research Questions and Challenges

The main contribution of this paper is in identifying some interesting research questions that can motivate research on the interface of MAS and Web architectures. Specifically, we propose the following research questions:

How should we model the presence of a governance layer in a MAS? In most common approaches, the governance layer is either implicit (agents are regimented) or embodied by norm-enforcement agents. In the Custard language for instance (Listing 1), institutions and agents are at the same level of abstraction. An alternative approach would be to model an institutional environment, as a generalised form of agent environment (see [START_REF] Weyns | Environment as a first class abstraction in multiagent systems[END_REF][START_REF] Omicini | Artifacts in the A&A meta-model for multiagent systems[END_REF]), such that reusable server or proxy components may be applied on several MAS architectures.

What aspects of a web-based deployment of a MAS may be subject to governance policies and included in an institutional environment? Examples would include constraints on ownership and physical location of the component hosting an agent. A MAS that operates on a physical (or simulated) environment, e.g. on the Web of Things, must necessarily be regulated by stateful institutional components. Statefulness alone is however not enough, as institutional facts may be derived from brute facts generated in the physical environment. Only proxies and servients-components with a client port-could access the physical environment-exposed by environmental servers. If servers implement the observer pattern, as in CoAP, another class of institutional components may be added for "observer" servients. Observer servients would not be proactive (i.e. not agents) but still have the possibility to subscribe to environmental events.

How do we map the required properties of an institutional environment (monitoring, reasoning, sanctioning power) to constraints and mechanisms of a web-based deployment and more specifically to hypermedia control? Governance requires a certain point where governance decisions are made. Even in a decentralized architecture, that point reflects a form of centrality, albeit a weak one. Institutional components, such as the ones we have identified in the paper, have decreasing levels of centrality:

proxy (to enforce policies), which supports real-time sanctions and requires no effort to continually re-engineer agents.

institutional server (to maintain a shared institutional state), which supports violation detection and sanctioning but lets agents autonomously interact for the most part. federation of institutional servers, which relaxes the single institutional server case thereby reducing centrality but supporting potentially delayed sanctioning.

As suggested in Sec. 5, hypermedia controls, such as links and forms, should help agents follow high-level social protocols while still deviating locally, depending on the controls that servers expose. Hypermedia controls make it easy to decentralize interactions (a proxy may e.g. redirect to a read-write server at run time) but hard to recentralize interactions (if agents interact in a peer-topeer fashion, moving to proxy-mediated interactions would require to re-engineer all agents).

Conclusion

Thinking about MAS and the Web together opens up new opportunities in building large-scale sociotechnical systems. Such systems would take advantage of the flexibility derived from MAS and the scalability and familiarity (to most developers) derived from the Web. The possibilities are promising and we invite the research community to join us in investigating them.

Listing 2 .

 2 A possible Organ Donation protocol. D o n a t i o n { r o l e s R e c i p i e n t H , DonorH p a r a m e t e r s o u t o r g a n R e q u e s t I D key , o u t o f f e r I D key , o u t r e c i p i e n t I n f o , o u t d o n o r I n f o , i n r e c i p i e n t C e r t i f i c a t e p r i v a t e d e c i s i o n , t r a n s f e r I n f o R e c i p i e n t H -> DonorH : r e q u e s t [ o u t o r g a n R e q u e s t I D , o u t r e c i p i e n t I n f o ] DonorH -> R e c i p i e n t H : r e s p o n s e [ i n o r g a n R e q u e s t I D , o u t o f f e r I D , o u t d o n o r I n f o ] R e c i p i e n t H -> DonorH : c o n f i r m a t i o n [ i n o r g a n R e q u e s t I D , i n o f f e r I D , i n r e c i p i e n t C e r t i f i c a t e , o u t t r a n s f e r I n f o , o u t d e c i s i o n ] R e c i p i e n t H -> DonorH : r e j e c t i o n [ i n o r g a n R e q u e s t I D , i n o f f e r I D , i n r e c i p i e n t C e r t i f i c a t e , o u t d e c i s i o n ] }

Listing 3 .

 3 AcceptBestMatch orm expressed in the Expectation Event Calculus (EEC).

  e x p r u l e ( and ( [ r e q u e s t ( O r g a n R e q u e s t I D , R e c i p I n f o ) , r e s p o n s e ( O r g a n R e q u e s t I D , O f f e r I D 1 , D o n o r I n f o 1 ) , q u a l i t y o f m a t c h ( D o n o r I n f o 1 , R e c i p I n f o , Q1) ] ) , n e v e r ( and ( [ r e s p o n s e ( O r g a n R e q u e s t I D , O f f e r I D 2 , D o n o r I n f o 2 ) , q u a l i t y o f m a t c h ( D o n o r I n f o 2 , R e c i p I n f o , Q2) , Q2 < Q1 , e v e n t u a l l y ( c o n f i r m a t i o n ( O r g a n R e q u e s t I D , O f f e r I D 2

Fig. 1 .

 1 Fig. 1. Architecture for an institution governing Web agents: Institution as Read-Only Server

Fig. 2 .

 2 Fig. 2. Architecture for an institution governing Web agents: Institution as Read-Write Server

Table 1 .

 1 Mappings of an institution to Web components and associated characteristics with respect to governance; checkmark (✓): the characteristic of the institution is guaranteed by constraints on the Web component, question mark (?): the characteristic of the institution depends on the MAS architecture, not on the Web component

	Institutional component Norm update Statefulness Sanctioning
	Read-only server	✓
	Read-write server	✓	✓
	Proxy	✓	✓	✓
	Servient	✓	?	?

https://unos.org/

https://www.ont.es

https://trasplantaments.gencat.cat

in its original form, Carrel includes a waiting list of donors, which other TCU agents can consult once a donor is available. Here, we only consider agent-to-agent interactions and assume that the agent holding the request asks other agents for potential donors.

https://www.dagstuhl.de/23081

Acknowledgments

Singh thanks the US National Science Foundation (grant IIS-1908374) and the Department of Defense (Science of Security Lablet) for support for this research.

The authors collectively acknowledge Dagstuhl Seminar 23081: Agents on the Web 11 held in February 2023 for providing the working environment for the "Governance" group whose discussions provide the basis for this paper. In addition the authors acknowledge participation in working group discussions by Mehdi Dastani and Wendy Hall.


Mary Brennan
email: mary.brennan@teagasc.ie

Lorraine Balaine

Souhil Harchaoui

Joanna Frątczak-Müller

Xabier Díaz De Otálora

Cathal Buckley

Dominika Krol

Emma Soulé

Aurélie Wilfart

Federico Dragoni

DairyMix: Multi

Keywords:

come

1.Introduction 2. A focus on circularity

DairyMix aims to assess circularity on case study dairy farms in Europe and Argentina, with a circularity index.

Developing a circularity index

Circularity refers to the concept of creating closedloop systems where resources are used efficiently and waste is minimized.

Circularity assessment is important for agriculture due to its resource use and energy intensive nature.

The majority of dairy production systems rely heavily on external inputs, resulting in limited circularity.

Establish circularity performance of case study farms with circularity index. The DairyMix project aims to contribute to the development of more sustainable circular mixed farming systems for dairy production that reduce external inputs and develop decision support and management tools.

DairyMix will be a major step forward in achieving greenhouse gas mitigation and circularity between cropping systems and dairy production systems with flexible and context specific solutions being developed for key European areas and for Latin America.

4.Next stage of research

Project partners

DairyMix: Multi-criteria assessment, decision support and management tools for sustainable circular mixed farming systems for dairy production Mary Brennan 1* , Lorraine Balaine 1 , Souhil Harchaoui 2 , Joanna Fratczak-Muller 3 , Xabier Díaz de Otálora 4,5 , Cathal Buckley 1 , Dominika Krol 6 , Emma Soule 2 , Aurélie Wilfart 2 , Federico Dragoni 5 , Barbara Amon 3,5

  Funding acknowledgements: Joint Call of the Cofund ERA-Nets SusCrop (Grant N°771134), FACCE ERA-GAS (Grant N°696356), ICT-AGRI-FOOD (Grant N°862665) and SusAn (Grant N°696231). The authors acknowledge the financial support from national funding agencies, including the Irish Department of Agriculture, Food and the Marine (2021EN904). Further information on this project can be found at www.dairymix.eu. **Muscat, Abigail, et al. "Principles, drivers and opportunities of a circular bioeconomy." Nature Food 2.8 (2021): 561-566. Graphics courtesy of flaticon.com

  Compare index with sustainability indicators to identify trade offs and synergies. Incorporate results in DairyMix information platform to inform farmers and stakeholders. The circularity index will comprise indicators representative of the five principles of the circular bioeconomy, as identified by Muscat et al. (2021)**. (Image courtesy of Muscat et al. (2021))**


domain: phys spi

text:
M Rabaud
email: rabaud@fast.u-psud.fr

F Moisy

Laboratoire Fast

OPTICAL MEASUREMENT OF SHIP WAVES BY DIGITAL IMAGE CORRELATION

A large part of the drag experienced by fast sailing boats originates from the energy radiated at the sea surface by waves. Optimising hull shape in order to minimise wave resistance requires thus a good knowledge of the wave structure created by the ship as well as its evolution with boat heel and boat speed. This knowledge usually originates from numerical simulations or towing experiments. We present here an optical method allowing the determination of the instantaneous 3D water surface shape with a good vertical resolution on large horizontal scales. This method may be useful in towing tank tests and should allow detailed comparisons with computed surface deformation and thus help to validate Velocity Prediction Programs.

NOMENCLATURE

Fr

Froude

INTRODUCTION

A challenging domain in naval research is to design fast sailing boats minimizing the hull drag and more precisely the wave drag. Since the pioneering work of William Froude [START_REF] Thomson (lord | Popular Lectures and Addresses[END_REF] and Havelock [START_REF] Havelock | The Propagation of Groups of Waves in Dispersive Media, with Application to Waves on Water Produced by a Travelling Disturbance[END_REF], it is known that the drag experienced by a boat increases rapidly when its velocity increases and that most of this increase originates from the energy dissipated in wave formation. Large amplitude waves generated by the motion of the hull are known to be localised in a wedge of half angle 19.5°, the so called Kelvin wedge [START_REF] Tsai | Computation of Nonlinear Free Surface Flows[END_REF], but the exact wave pattern is a function of the hull shape and orientation, and of the dimensionless Froude number, Fr = U/U C , ratio of the boat speed to the critical hull speed:

U c = gL W π .
This critical velocity corresponds to the ship velocity for which the gravity waves moving with the ship have a wavelength equal to twice L W the waterline of the boat. When the boat sails faster than this critical hull speed, Fr > 1, the wave resistance decreases, mainly because an increase of the sustentation forces changes the wetted volume of the hull. Most modern fast sailing boats attempt to navigate above U c and a good prediction of their performance demands an accurate simulation of the generated wave pattern. These simulations are nowadays more and more accurate [START_REF] Tsai | Computation of Nonlinear Free Surface Flows[END_REF][START_REF] Parau | Nonlinear two-and three-dimensional free surface flows due to moving disturbances[END_REF][START_REF] Tuck | Wave Patterns and Minimum Wave Resistance for High-Speed Vessels[END_REF][START_REF] Garcia | An Unstructured Finite Element Solver for Ship Hydrodynamics Problems[END_REF] but comparisons with tank tests are still necessary in particular for unstationary conditions when wind waves or swell are present.

Usual measurements of wave pattern are based on local measurement by resistive, ultrasonic or capacitive probes. These probes or array of probes measure the water level when the boat passes by. From the time evolution h(t) the profile h(x) is reconstructed assuming a constant velocity of the boat. The wave resistance can then be deduced by the longitudinal cut method of Sharma [7]. Direct measurement of one height profile at different instants was developed recently, a camera imaging the intersection of a laser sheet with the water interface [START_REF] Nishio Shigeru | Image Measurement of the Wave Height Distributions around a Ship Hull in Regular Wave[END_REF]. However this method requires powerful lasers.

To our knowledge, no method until now was able to measure directly the full 3D water shape. In the present paper we thus address the possibility of measuring instantaneously the surface deformation h(x,y) with a good horizontal and vertical resolutions using light refraction through the deformed surface. This technique was shown to be simple and very efficient at small scale [START_REF] Moisy | Measurement by Digital Image Correlation of the topography of a liquid interface[END_REF] and a summary of these results is presented in the next section. We will discuss in section 3 the possibility to adapt this technique to measurement in towing tanks.

PRINCIPE OF THE METHOD

Our method is derived from PIV (Particle Image Velocimetry) technique, now currently used in fluid mechanics to determine fluid velocity in one plane.

EXPERIMENTAL SET-UP

In the present method a camera images randomly located dots (speckle pattern) printed on a plane screen through the air/water interface (Figure 1). A first reference image is taken when the interface is flat, and images taken when the interface is deformed are compared to the reference one.

The dots when seen through the deformed interface appear displaced on a small distance δr(x,y). To first order, if the camera is far enough and the slope of the interface is not too large, this displacement is proportional to the local slope grad(h) of the interface, to the air and water indexes n and n', and to the water depth h 0 : Experimental set-up showing the camera above the interface and the dotted screen located at the bottom of the tank.

δr ≈ - n'-n n' h 0 grad h ( ) . (1)

DETERMINATION OF THE SURFACE SHAPE

The displacement field δr is obtained by processing the reference image and the deformed image using a standard PIV algorithm2 . As the designed pattern is adjusted to reach the optimal dot concentration (about 50%) and the optimal dot size (few pixels), a subpixel resolution can be easily achieved. Equation (1) can then be integrated numerically in order to obtain the surface height h(x,y). Details of the integration method are given in Ref. 9. Figure 2 gives an example of surface obtained in a test case with small amplitude plane waves. The visualised domain is of the order of 15 cm x 15 cm, with a horizontal resolution of 0.5 mm and a vertical resolution of the order of few micrometers (1% of the wave amplitude). Small transverse oscillations are clearly visible on the main waves. Typical surface shape measured with plane waves in a test experiment.

ESTIMATED ACHIEVABLE RESOLUTION AND LIMITATIONS FOR TOWING TANK MEASUREMENT

In a real towing tank, dimensions are very different from the ones of our test case. We selected typical values for a towing tank : h 0 = 2 m for the mean water depth, and an imaged surface of 4 m x 4 m. With a 2048 x 2048 pixel camera imaging this surface, the pixel size would be of 2 mm. The typical size of the random dots on the bottom should then be of the order of 1 cm. Using PIV windows of 8 x 8 pixels, the x and y resolution will be of 16 mm, corresponding to 256 x 256 measurement points. As sub-pixel resolution is achievable, displacement of 0.2 mm should in principle be measurable.

In order to be far enough the camera must be located to an altitude H > 10 m for such large image. This is certainly a strong limitation if the ceiling of the towing tank is not high enough, however a 45° mirror could be add in order to use an horizontal optical axes.

With those order of magnitude, equation 1 predicts a slope resolution of 0.02°, and thus a vertical resolution of 6 µm. This excellent vertical resolution is possible because of the very good sensitivity of the PIV method and also because of the very large value of h 0 . However this large value of the distance from the surface to the dot pattern has an important drawback: It will limit the maximum measurable curvature. Indeed the crest of the wave acts as a converging lens, and for monochromatic waves of amplitude A and wavelength λ, as the deformed surface writes η=Acos(2πx/ λωt), the focal distance is λ 2 /(π 2 A). In order to avoid caustics or too large stretching of the dots this focal distance must remain much larger than the water depth h 0 . If it is not the case, the displacement field is no more invertible [START_REF] Moisy | Measurement by Digital Image Correlation of the topography of a liquid interface[END_REF]. This limits the measurable curvature of the interface:

A < λ 2 10h 0 . ( 2
)
For example with λ = 1 m and h 0 = 2 m, Eq. ( 2) limits the maximum measurable wave amplitude to A < 5 cm.

This limitation on the wave amplitude can be overcome however by decreasing h 0 using an immersed dot screen located above the tank bottom. If this is not possible because of the draft of the hull or because it will alter the wave dispersion (shallow water approximation) the camera can also be put under water and the screen in air above the water surface. This method should then allow observing larger amplitude waves.

CONCLUSIONS

A technique to measure the full deformation of sea surface behind a sailing boat was described. The technique was already tested at small laboratory scale and show very good resolution. We believe that it can easily be adapted to larger scales without many difficulties, as it does not ask for peculiar material or critical optical skills.

5.

  Figure 1:Experimental set-up showing the camera above the interface and the dotted screen located at the bottom of the tank.

Figure 2 :

 2 Figure 2: Typical surface shape measured with plane waves in a test experiment.

e.g. LaVision GmbH, Anna-Vandenhoeck-Ring 19,

37081, Goettingen, Germany, complemented with the PIVMat toolbox for Matlab, http://www.fast.upsud.fr/pivmat.

ACKNOWLEDGEMENTS

The authors acknowledge Kelvin Salsac for his help during the first stages of the experiment.