# An Anonymous yet Accountable Contract Wallet System using Account
Abstraction

Kota Chin
University of Tsukuba
National Institute of
Information and
Communications Technology
Japan Keita Emura
Kanazawa University, Japan
National Institute of
Information and
Communications Technology
Japan Kazumasa Omote
University of Tsukuba
National Institute of
Information and
Communications Technology
Japan

###### Abstract

Account abstraction allows a contract wallet to initiate transaction
execution. Thus, account abstraction is useful for preserving the privacy of
externally owned accounts (EOAs) because it can remove a transaction issued
from an EOA to the contract wallet and hides who issued the transaction by
additionally employing anonymous authentication procedures such as ring
signatures. However, unconditional anonymity is undesirable in practice
because it prevents to reveal who is accountable for a problem when it arises.
Thus, maintaining a balancing between anonymity and accountability is
important. In this paper, we propose an anonymous yet accountable contract
wallet system. In addition to account abstraction, the proposed system also
utilizes accountable ring signatures (Bootle et al., ESORICS 2015). The
proposed system provides (1) anonymity of a transaction issuer that hides who
agreed with running the contract wallet, and (2) accountability of the issuer,
which allows the issuer to prove they agreed with running the contract wallet.
Moreover, due to a security requirement of accountable ring signatures, the
transaction issuer cannot claim that someone else issued the transaction. This
functionality allows us to clarify the accountability involved in issuing a
transaction. In addition, the proposed system allows an issuer to employ a
typical signature scheme, e.g., ECDSA, together with the ring signature
scheme. This functionality can be considered an extension of the common multi-
signatures that require a certain number of ECDSA signatures to run a contract
wallet. The proposed system was implemented using zkSync (Solidity). We
discuss several potential applications of the proposed system, i.e., medical
information sharing and asset management.

###### Index Terms:

Blockchain, Account abstraction, Contract wallet, Accountable ring signatures.

##  I Introduction

###  I-A Introduction of Account Abstraction

Ethereum involves two kinds of accounts, i.e., externally owned accounts
(EOA), which are controlled by a user-managed secret key, and contract
accounts (contract wallets), which are controlled by smart contracts. In the
current implementation of Ethereum, to run a contract wallet, an EOA must send
a transaction to the contract wallet. Then the contract wallet runs a
transaction according to the rule specified in the contract. Account
abstraction [11] allows a contract wallet to initiate transaction execution,
i.e., it can remove a transaction sent from an issuer to the contract. Account
abstraction provides two primary benefits. The first benefit is the reduction
of gas costs because account abstraction can remove a transaction sent from an
issuer to the contract wallet. The second benefit is flexible verification. In
the current Ethereum implementation, transactions, issued by EOAs, are
verified according to the validity of signatures generated by secret keys of
EOAs, and the underlying signature scheme is restricted to the elliptic curve
digital signature algorithm (ECDSA). Thus, ECDSA signatures are employed
generally when transaction validity is verified in the contract, although,
theoretically, any signature schemes can be employed because signatures are
verified by programs. In contrast, due to account abstraction, no EOA issues
transactions, and thus any signature schemes can be employed more easily to
verify transaction validity in the contract. For example, CRYSTALS-Dilithium
[15], FALCON [18], and SPHINCS+ [4], which have been selected by the NIST
Post-Quantum Cryptography Standardization, can be employed under the
assumption they can be implemented by a program language that can be run by
the contract wallet, e.g., Solidity.111Although we consider only signatures in
this paper, any verification method can be employed or a contract wallet with
no verification step can be constructed. In addition, account abstraction
allows us to employ signatures with rich functionalities, such as accountable
ring signatures [10]. Representative examples of systems that support account
abstraction include StarkNet [2] and zkSync [3], which are network
technologies in Ethereum Layer 2 (L2). Note that L2 is described in further
detail in Section II-B.

Transactions between the EOAs and contract wallets are removed; thus account
abstraction is useful for preserving the privacy of EOAs. In fact, EIP-2938
[11] states that “ _Privacy-preserving systems like tornado.cash_ ” are a
motivation to introduce account abstraction (tornado.cash is a mixing
service). Concretely, it is expected that account abstraction can hide the
issuer of a transaction. Note that a contract wallet typically verifies a
signature using a verification key that has been registered in the contract
program. Since the verification key is public (in a public blockchain), anyone
can identify who issued the transaction (precisely, which verification key is
used and the key holder who issued the transaction). In other words, account
abstraction does not hide transaction issuer information. We emphasize that
unconditional anonymity could promote crime. For example, tornado.cash is a
tool that could be misused to facilitate money laundering, and the Fiscal
Information and Investigation Service, an agency of the government of the
Netherlands, arrested a 29-year-old man in Amsterdam as a suspected developer
[1]. This indicates maintaining a balancing between anonymity and
accountability is important.

###  I-B Privacy on Ethereum

Each EOA manages an ECDSA verification key $\mathsf{vk}$, and the
corresponding address is a (last 20 bytes of) hashed value of $\mathsf{vk}$
(here Keccak-256 hash function is used). Here, as each address appears
random,222Vanity addresses are often used to reduce the storage cost of
addresses. For example, using an address 0x0000…, a part of address
“0$\cdots$0” does not need to be stored. Even in this case, pseudonymity level
privacy protection is guaranteed.  anyone can easily determine whether
multiple transactions were issued by the same EOA, although it is difficult to
detect the EOA in the real world. This means that issuer privacy is preserved
in the sense of pseudonymity in crypto asset trading.

Does Pseudonymity Provide Sufficient Privacy Protection? When crypto assets
are traded between individuals, the pseudonymity level privacy protection
might be sufficient. However, some information leakage occurs if a system is
implemented using smart contracts.

For example, assume that a request to view patient data is made by a
transaction in an electronic medical record system using Ethereum smart
contracts [26, 22, 5, 20, 16, 33, 30, 25, 17]. In this case, we assume that
multi-patient data are accessed from the same address. Then, we expect that
the transaction issuing address is managed by a doctor or researcher. In
addition, we expect that patients are suffering from similar diseases. Here,
if the doctor or researcher associated with the address is identifiable,
information identifying the patient’s disease may be leaked (although this was
not authorized by the patient) depending on the specialty of the issuer of the
transaction. Thus, no information about hospitals and medical offices should
be leaked from transactions. However, it is necessary to internally verify who
issued the transaction in order to prevent unnecessary access to medical data.

In the case of group asset management, pseudonymity level privacy protection
would make the investment performance of each address public. Thus, it is
desirable to be able to prove the investment performance internally while
keeping information about the issuer of the transaction secret externally.

A Naive Solution 1: Key Sharing. Let a pair of signing and verification keys
be generated and let all members of a group share the key pair. When a member
issues a transaction, the same signing key is used to generate a signature.
Then, anonymity level privacy protection is provided because a contract wallet
uses the same verification key to verify the signature. However, there is no
way to identify who issued the transaction, even among group members.
Unconditional anonymity is undesirable in practice because it prevents to
reveal who is accountable for a problem when it arises. In addition,
determining how to revoke the signing key when a member leaves the group is a
nontrivial problem.

A Naive Solution 2: External Services. Amazon Web Services (AWS) Key
Management Service or a system on permissioned blockchain that support a
trusted execution environment (TEE), e.g., Intel SGX, can be used to solve the
above problems. By using such services, group members can issue a transaction
without sharing the signing key. Here, anonymity still holds because the
contract wallet uses the same verification key. In addition, group members can
internally identify who issued a transaction via an access log (AWS Key
Management Service) or the transaction (permissioned blockchain). Member
revocation is also possible via access control to the services. Thus,
technically we can provide both anonymity (for outside of the group) and
accountability (for the group) simultaneously. However, both methods assume
trust in AWS and TEE, which is undesirable relative to increase trust points.

Figure 1: Proposed System

###  I-C Our Contribution

In this paper, we focus on account abstraction, which is attractive in terms
of constructing a privacy-preserving system, and we propose an anonymous yet
accountable contract wallet system (Figure 1).333We used Free Clip Art
(http://www.clker.com/). In addition to account abstraction, the proposed
system employs accountable ring signatures [10].444A user (EOA) needs to issue
a transaction to a contract wallet when account abstraction is not employed.
Thus, information that who issued a transaction is leaked even a ring
signature scheme is employed in this case. Thus, both account abstraction and
ring signatures are required mandatory in our system. We do not the following
one-time deployment case that a contract wallet is newly deployed for issuing
a transaction because it is not realistic solution. We implemented the
proposed system using zkSync (Solidity). Precisely, we implemented the
verification algorithm of the underlying accountable ring signature scheme
using Solidity. The proposed system is briefly introduced as follows.

  * •

To issue a transaction, a ring signature is sent to a contract wallet, and the
contract wallet verifies the signature. Then, the contract wallet uses a ring
(i.e., a set of verification keys) to verify the signature. Anonymity holds in
the sense that the contract wallet cannot identify the issuer among the
verification key holders.

  * •

The opening functionality of the accountable ring signatures allows the actual
issuer to prove that they issued the transaction, and other users can
recognize this fact. In contrast, due to a security requirement of accountable
ring signatures (i.e., opening soundness), no user can prove that they issued
a transaction if they did not actually issue the transaction, and moreover the
transaction issuer cannot claim that someone else issued the transaction. In
addition, the proof can be generated by other ring members who share the
secret opening key of the underlying accountable ring signatures. This
functionality allows us to clarify the accountability involved in issuing a
transaction. We remark that we mainly focus on how to identify/prove who
issued a transaction in this paper. That is, we assume that the organization
to which the transaction issuer belongs is accountable, and we do not address
what penalties that organization would impose on the transaction issuer if the
transaction became problematic, or how that organization would be held
accountable.

  * •

The proposed system allows an issuer to employ a typical signature scheme,
e.g., ECDSA, with the ring signature scheme. This functionality can be
considered an extension of the typical multi-signatures that require a certain
number of ECDSA signatures to run a contract wallet. For example, the contract
wallet determines whether one of the issuers belongs to a group (in an
anonymous manner), and a specific user (in the usual manner) agrees to run the
contract wallet by verifying a ring signature and an ECDSA signature. This is
illustrated in Figure 2. In the usual multi-signatures setting, anyone can
recognize who agreed with running the contract wallet by observing ECDSA
verification keys used for ECDSA signatures verification. Note that if two
signatures are sent to the contract wallet separately, one of them must be
preserved in the contract wallet which incurs an additional gas cost. To
reduce the cost, one sender can collect all of the required signatures, and
send them to the contract wallet.

Figure 2: Extended Multi-Signatures

###  I-D Applications

Potential applications of the proposed system include, but are not limited to,
the following.

Medical Information Sharing. As mentioned previously, when a request to view
patient data is made by a transaction in an electronic medical record system
using Ethereum smart contracts, it is highly desirable that no information
about hospitals and medical offices is leaked from the transactions. However,
it is also essential to be able to internally verify who issued the
transaction in order to prevent unnecessary access to medical data. With the
proposed system, from the outside, it is possible to hide who is accessing
patient data among members in an organization. For example, when a hospital is
specified as the organization, it is possible to keep secret which doctors’
offices have access to medical data. If a clinical department, e.g., internal
medicine, psychosomatic medicine, or plastic surgery, is specified as the
organizational unit, which department is related to which disease is leaked,
but no other information is leaked because which doctor accessed the patient
data is kept secret. In addition, dividing the organization into independent
departments relative to the actual medical offices may further prevent
unnecessary leakage of information. Thus, by setting organizational units
appropriately, we can control leaked information. In addition, more flexible
settings can be realized by using our extended multi-signatures. For example,
we can consider a case where the hospital director or a department head must
agree to issue a transaction. Here, one person in a medical office needs to
agree to issue the transaction.

Asset Management. The range of blockchain-based asset management has expanded
due to the advent of smart contracts. Thus, the number of investment companies
that manage their clients’ funds has been increasing. In some cases, the
addresses held by lenders are known publicly. Then, the status of the fund
management can be checked.555In fact, these addresses are not disclosed by
lenders intentionally. Here, they are assumed to be lenders’ addresses based
on the asset management status.  It is assumed that there are cases where
multiple users share an EOA as the address, and cases where multiple users
employ contract wallets where transactions can be issued with the consent of a
certain number of users. In the former case, it is impossible to know who
issued the transaction internally. In the latter case, due to the pseudonymity
level privacy protection, anyone can check the investment performance of each
address. Except for cases where the investment status is disclosed
intentionally, such information can be leaked unexpectedly. By employing the
proposed system, the investment status of each address is not disclosed
externally, and the investment status of each individual can be known
internally.

##  II Preliminaries

###  II-A Accountable Ring Signatures

As a generalization of ring signatures [29] and group signatures [13], Xu and
Yung proposed accountable ring signatures [34]. Briefly, as in ring
signatures, each user generates their own public key $\mathsf{pk}$ and secret
key $\mathsf{sk}$. This decentralized structure matches blockchain systems. An
opener has a public key $\mathsf{opk}$ and a secret key $\mathsf{osk}$. When a
user who has $(\mathsf{pk},\mathsf{sk})$ generates a ring signature $\Sigma$
on a message $M$, the user selects a set of public keys, which we refer to as
ring $R$, and we assume that $\mathsf{pk}\in R$, and selects the opener by
indicating $\mathsf{opk}$. We say that $(\Sigma,M)$ is valid if the signer is
a member of $R$, i.e., there exists $\mathsf{pk}\in R$ for which the
corresponding $\mathsf{sk}$ has been used to generate $\Sigma$. As in group
signatures, the designated opener can trace the signer using $\mathsf{osk}$.
Moreover, the opening algorithm produces a proof $\pi$ proving that $\Sigma$
is generated by $\mathsf{sk}$ corresponding to $\mathsf{pk}\in R$. We
introduce the syntax defined by Bootle et al. [10] as follows.

######  Definition 1 (Syntax of Accountable Ring Signatures [10])

  * •

${\sf Setup}(1^{\lambda})$: The setup algorithm takes the security parameter
$\lambda\in\mathbb{N}$ as input and outputs the common parameter
$\mathsf{pp}$.

  * •

${\sf OKGen}(\mathsf{pp})$: The opener key generation algorithm takes
$\mathsf{pp}$ as input and outputs the opener public and secret keys
$\mathsf{opk}$ and $\mathsf{osk}$, respectively.

  * •

${\sf UKGen}(\mathsf{pp})$: The user key generation algorithm takes
$\mathsf{pp}$ as input and outputs the user public verification key
$\mathsf{pk}$ and user secret signing key $\mathsf{sk}$.

  * •

${\sf RSign}(\mathsf{opk},M,R,\mathsf{sk})$: The signing algorithm takes
$\mathsf{opk}$, a message $M$ to be signed, a ring $R$, and $\mathsf{sk}$ as
inputs and outputs a ring signature $\Sigma$. Here, $R$ is a set of user
public keys and the $\mathsf{pk}$ corresponding to $\mathsf{sk}$ is assumed to
be $\mathsf{pk}\in R$.

  * •

${\sf RVerify}(\mathsf{opk},M,R,\Sigma)$: The verification algorithm takes
$\mathsf{opk}$, $M$, $R$, and $\Sigma$ as inputs and outputs 1 (accept) or 0
(reject).

  * •

${\sf Open}(M,R,\Sigma,\mathsf{osk})$: The open algorithm takes as $M$, $R$,
$\Sigma$, and $\mathsf{osk}$ as inputs and outputs $\mathsf{pk}\in R$ of the
signer and its proof $\pi$ or $\bot$ otherwise.

  * •

${\sf Judge}(\mathsf{opk},M,R,\Sigma,\mathsf{pk},\pi)$: The judge algorithm
takes $\mathsf{opk}$, $M$, $R$, $\Sigma$, $\mathsf{pk}$, and $\pi$ as inputs
and outputs 0 if ${\sf RVerify}(\mathsf{opk},M,R,\Sigma)=0$; otherwise, it
outputs 1 to indicate that $\Sigma$ is generated by $\mathsf{sk}$
corresponding to $\mathsf{pk}$, and 0 otherwise.

We require correctness holds where an honestly generated signature is always
valid (the ${\sf RVerify}$ algorithm outputs 1), and a proof generated by the
${\sf Open}$ algorithm against the signature and corresponding verification
key is always accepted by the ${\sf Judge}$ algorithm. Bootle et al. defined
full unforgeability, anonymity, traceability, and tracing soundness, which are
briefly explained as follows. Refer to the literature [10] for details on
these security definitions.

  * •

Full Unforgeability: It ensures that no adversary $\mathcal{A}$ (who may
control the opener) can falsely accuse an honest user of creating a ring
signature, nor $\mathcal{A}$ can forge a ring signature on behalf of an honest
ring.

  * •

Anonymity: It ensures that no adversary $\mathcal{A}$ (who does not have
$\mathsf{osk}$) can identify the signer, i.e., a signature does not reveal the
identity of the ring member who generated it.

  * •

Traceability: It ensures that no adversary $\mathcal{A}$ can produce a
signature that is valid but untraceable.

  * •

Tracing Soundness: It ensures that no adversary $\mathcal{A}$ can produce
proofs for a signature that are accepted by the ${\sf Judge}$ algorithm for
different verification keys.

Some studies have employed accountable ring signatures in blockchain systems
[31, 19] due to its decentralized structure. In addition, Qiao et al. [28]
removed the opening functionality from group signatures to reduce its
centralized structure; however, it still has a centralized structure because a
group manager issues signing keys to the group members unlike to (accountable)
ring signatures. Linkable ring signatures [23, 8, 24] have been employed to
provide a pseudonymity level privacy protection. As mentioned previously, this
is insufficient; thus, anonymity level privacy protection is desirable.
Delegatable anonymous credentials (DAC) [12] have been employed for eKYC
systems [9, 32], where KYC stands for Know-Your-Customer. However, DACs are
not applicable in the proposed system because they do not provide tracing
functionality. Connolly et al. [14] proposed a revocable and auditable
anonymous credential scheme called Protego, and they considered its
application to Hyperledger Fabric. Although it might be employed in the
proposed system, Connolly et al. only considered permissioned blockchains.
Thus, accountable ring signatures are employed in the proposed system.

###  II-B Layer 2

Ethereum is widely recognized as providing high security as a smart contract-
enabled blockchain. However, in terms of ensuring security and providing a
distributed structure, there is room for improvement regarding scalability.
Concretely, the number of transactions that can be processed within a certain
time period is less than that of other blockchain systems. Thus, transaction
fees (gas costs) will increase when many EOAs want to issue transactions. To
solve this problem, we can issue a transaction off-chain, and the proof that
the transaction is generated correctly, is only stored on the Ethereum
blockchain. In this case, the blockchain and off-chain are referred to as
Layer 1 (L1) and Layer 2 (L2), respectively. For example, when a Merkle tree
is used to generate a hash chain, the proof that the hash chain satisfies the
Merkle tree is stored in L1. To reduce the proof size stored in L1, the zk-
STARK (zero-knowledge Scalable Transparent ARgument of Knowledge) [6] or zk-
SNARK (zero-knowledge Succinct Non-interactive ARguments of Knowledge) [21,
27] are employed.

zkSync [3] is an Ethereum L2 network technology that supports zk-SNARK. The
goal of L2 technologies to provide the same execution environment of Ethereum
(i.e., the EVM: Ethereum Virtual Machine), and zkSync nearly supports the same
execution environment of Ethereum, i.e., it is EVM-compatible and can run a
smart contract programed by Solidity. Thus, we can utilize Ethereum ecosystem
tools, and smart contracts on zkSync are described by Solidity. This means
that the proposed system can be used directly when Ethereum supports account
abstraction.

###  II-C Account Abstraction

In the following, we describe account abstraction. A user sends the code of a
contract wallet to nodes that support account abstraction, and requests to its
deployment. Note that the user does not need to be an issuer of a transaction.
After deploying the contract wallet, an issuer sends transaction data to
blockchain via nodes. Finally, the contract wallet runs the transaction
according to the rule described in the code. We illustrate the flow of
transaction issuing when account abstraction is/is not employed in Figure 3
and Figure 4.

Figure 3: Usual Transaction Issuing Figure 4: Account Abstraction

Here, the issuer (User (EOA)) communicates with nodes, their IP address is
known by nodes which break anonymity trivially. Thus, we exclude the nodes in
our anonymity requirement.666This restriction can be removed if a user (who
issued a transaction) prepares a node. However, currently only a test net
supports account abstraction, and users who can prepare nodes are restricted.

##  III Proposed Anonymous yet Accountable Contract Wallet System

In this section, we describe the proposed anonymous yet accountable contract
wallet system. First, we classify users who issue transactions.

  * •

Group User: a user $i$ who manages a key pair of the underlying accountable
ring signature scheme $(\mathsf{pk}_{i},\allowbreak\mathsf{sk}_{i})$ and the
common opening key $\mathsf{osk}$. $i\in R$ denotes when user $i$ is a group
member where $R$ is the ring used for signature verification (i.e.,
$\mathsf{pk}_{i}\in R$).

  * •

Individual User: a user $j$ who manages own ECDSA key pair
$(\mathsf{vk}_{j},\allowbreak\mathsf{sigk}_{j})$.

For simplicity, we assume that an issuer is either a group user or individual
user. Thus, we define a policy $\mathsf{Policy}$ that specifies when the
contract wallet runs a transaction. For example, let
$\mathsf{Policy}:=\\{R,j\\}$. Then, a transaction is run when one group user
who belongs $R$ and one individual user $j$ agree with the execution of the
transaction. In this case, the ring $R=\\{\mathsf{pk}_{i}\\}$ and ECDSA
verification key $\mathsf{vk}_{j}$ are registered in the contract wallet.

###  III-A Security Requirements

We require the following security notions hold. Especially, due to the
provability and proving soundness, the protocol is accountable because they
allow us to clarify the accountability involved in issuing a transaction.

  * •

Anonymity: All entities that can observe transactions including contract
wallets and excluding group users and nodes that communicate with the
transaction issuer, cannot identify the actual issuer among the verification
key holders contained in ring $R$.

  * •

Unforgeability: As long as all signatures (either/both the ring signatures
and/or the ECDSA signatures) specified by the $\mathsf{Policy}$ are sent to a
contract wallet, no entity can issue a transaction that is valid under the
$\mathsf{Policy}$.

  * •

Provability: When a group user $i$ sends a ring signature to issue a
transaction, the user can generate its proof.

  * •

Proving Soundness: When a group user $i$ does not send a ring signature to
issue a transaction, the user cannot generate its proof.

###  III-B High-level Description

In the following, we explain the case of $\mathsf{Policy}:=\\{R,j\\}$. First,
we assume that all group users belonging to $R$ share $\mathsf{osk}$. Let a
group user $i\in R$ issue a transaction. Then, the user $i$ generates a ring
signature $\Sigma$, and the individual user $j$ generates an ECDSA signature
$\sigma$, respectively. After these signatures are sent to a contract wallet,
the contract wallet checks whether $\Sigma$ is valid under $R$, and $\sigma$
is valid under $\mathsf{vk}_{j}$. If both signatures are valid, then the
contract wallet runs the transaction. We note that only the signature
verification is executed on-chain. Next, the user $i$ runs the ${\sf Open}$
algorithm using $\mathsf{osk}$, generates $\pi$ that is a proof of transaction
issuing, and sends $\pi$ to other group users (via an off-chain channel). For
example, any information sharing tool used in the organization (e.g., a
bulletin board in the organization or e-mails) can be used for sending pi.
Other group users can recognize that the user $i$ issues the transaction by
checking $\pi$ using the ${\sf Judge}$ algorithm.

We can easily consider a case that consents of two or more individual users
are required. For example, $\mathsf{Policy}:=\\{R,j,k\\}$. Similarly, we can
consider two or more rings, e.g., $R_{1}$ and $R_{2}$. Here, we assume that
$R_{1}\cap R_{2}=\emptyset$ and do not consider the case $R_{1}\cap
R_{2}\neq\emptyset$ because the contract wallet cannot distinguish whether one
user who belongs to $R_{1}\cap R_{2}\neq\emptyset$ sends two ring signatures
or not, due to anonymity. Similarly, we do not consider a case that consents
two or more group users belonging to the same ring are required because the
contract wallet cannot distinguish whether one user who belongs to the ring
sends two or more ring signatures or not, due to anonymity. We remark that
ring members can internally check whether one user who belongs to the ring
sends two or more ring signatures or not. Thus, in the case that the proof
$\pi$ will be opened after issuing the transaction, these restrictions could
be removed.

###  III-C Proposed System

Here, we describe the proposed anonymous yet accountable contract wallet
system. The proposed system consists of two procedures,
$\mathsf{DeployContractWallet}$ and $\mathsf{SecdTransaction}$. The
$\mathsf{DeployContractWallet}$ protocol is used to deploy a contract wallet,
and the $\mathsf{SecdTransaction}$ protocol issues a transaction against a
transaction issuing request.

  * •

$\mathsf{DeployContractWallet}(\mathsf{Code},\mathsf{BlockChain})$: Let
$\mathsf{Code}$ be the code of a contract wallet. In the protocol,
$\mathsf{Code}$ is sent to nodes that support account abstraction. Here, we
describe $\mathsf{BlockChain}$ as the set of nodes. Then, $\mathsf{Code}$
contains a policy $\mathsf{Policy}$, and a set of verification keys (a ring
$R$ and ECDSA verification keys), and the rule that specifies the procedure
run after the verification of signatures is passed. Finally, deploy a contract
wallet $\mathsf{CW}$.

  * •

$\mathsf{SecdTransaction}(\mathsf{TransactionData},\mathsf{BlockChain},\mathsf{CW})$:
A transaction data $\mathsf{TransactionData}$, containing accountable ring
signatures and ECDSA signatures, is sent to $\mathsf{CW}$ via nodes described
by $\mathsf{BlockChain}$. Then, $\mathsf{CW}$ checks the validity of
signatures according to $\mathsf{Policy}$, and issues a transaction.

In our system, the ${\sf RVerify}$ algorithm is run on-chain by the contract
wallet, as in the case of ECDSA signatures, because any one can issue a
transaction if no verification is involved. One may think that the ${\sf
RVerify}$ algorithm could be run off-chain, e.g., the operator of the
underlying L2 system runs the ${\sf RVerify}$ algorithm and sends the validity
result to the wallet. However, it requires to assume an additional trust to
the operator

###  III-D Security Discussion

  * •

Anonymity: Due to account abstraction and the anonymity of the underlying
accountable ring signature scheme, the fact that a group user $i$ belonging
$R$ generates the signature to issue a transaction is not leaked.

  * •

Unforgeability: Due to the unforgeability of the underlying accountable ring
signature scheme and ECDSA, no entity, that does not belong to $R$ or does not
have a signing key corresponding to $\mathsf{vk}$ specified by
$\mathsf{Policy}$, can issue a transaction. Due to the tamper resistance of
the blockchain, the code of a contract wallet is not modified after its
deployment. Thus, as long as all signatures (either/both ring signatures
and/or the ECDSA signatures) specified by $\mathsf{Policy}$ are sent to a
contract wallet, no entity can issue a transaction that is valid under the
$\mathsf{Policy}$.

  * •

Provability: Let $\Sigma$ be a ring signature generated by $\mathsf{sk}_{i}$
and verified by a contract wallet. Due to the correctness of the underlying
accountable ring signature scheme, ${\sf
Judge}(\mathsf{opk},M,R,\Sigma,\mathsf{pk}_{i},\pi)=1$ holds.

  * •

Proving Soundness: Let a ring signature be generated by $\mathsf{sk}_{i}$. Due
to the tracing soundness, no user (including group users) can produce $\pi$
that is accepted by the ${\sf Judge}$ algorithm with
$\mathsf{pk}\neq\mathsf{pk}_{i}$.

##  IV Implementation

The dominant of the proposed system in terms of cryptographic operations is to
verify accountable ring signatures on-chain. Thus, we mainly focus on the
accountable ring signature scheme in our implementation.

We implemented the Bootle et al. accountable ring signature scheme using
Node.js. Because it is secure under the Decisional Diffie-Hellman (DDH)
assumption, we employed secp256k1 as the underlying elliptic curve, which is
known as a DDH-hard curve. We also implemented the ${\sf RVerify}$ algorithm
using Solidity because the verification procedure is run on-chain (by the
contract wallet). For ECDSA signature verification, we employed the
OpenZeppelin library777https://docs.openzeppelin.com/.

###  IV-A Contract Wallet Deployment

First, we show that ergs (which is used in zkSync) for contract wallet
deployment (which represent the average of ergs of 100-times deployment in the
case of $|R|=4$ and $|R|=10$). We estimate the case of $|R|=4$ and $|R|=10$
(i.e., four/ten verification keys are contained in the ring). We also
calculate the corresponding ETH and USD (using chart on 2022 December 1st). We
can see that the costs are almost independent to the number of verification
keys, i.e., $|R|$, because each verification key is represented by two
unsigned integers only.

TABLE I: Ergs for Contract Wallet Deployment | $|R|=4$ | $|R|=10$
---|---|---
| 32,397,344 [ergs] | 32,369,062 [ergs]
Deployment | 0.0032 [ETH] | 0.0032 [ETH]
| 4 [USD] | 4 [USD]

###  IV-B Implementation by Node.js

Here, we describe our implementation environment of Node.js in Table II.

TABLE II: Implementation Environment of Node.js OS | Ubuntu 22.04.1 LTS
---|---
CPU | Intel Xeon E-2288G (3.70 [GHz])
Memory | 128 [GB]

We show our implementation results (which represent the average of running
times of 100-times executions) of the accountable ring signature scheme in
Table III. We estimate the case of $|R|=4$ and $|R|=10$.

TABLE III: Running Times Algorithms | $|R|=4$ | $|R|=10$
---|---|---
${\sf RSign}$ | 329 [ms] | 473 [ms]
${\sf RVerify}$ | 276 [ms] | 387 [ms]
${\sf Open}$ | 296 [ms] | 393 [ms]
${\sf Judge}$ | 287 [ms] | 393 [ms]

Although they depend on the ring size, they are reasonable because they are
run off-chain, except the ${\sf RVerify}$ algorithm in the proposed system.
The running time of the ${\sf RVerify}$ algorithm here is also important
because the ${\sf Open}$ and ${\sf Judge}$ algorithms internally run the ${\sf
RVerify}$ algorithm, since the corresponding ring signatures to be opened are
required to be valid.

###  IV-C Implementation by Solidity

Here, we describe our implementation environment of Solidity in Table IV.

TABLE IV: Implementation Environment of Solidity Version | Solidity @0.8.16
---|---
Compiler | hardhat-zksync-solc @0.3.9
Docker Image | matterlabs/geth

We show our implementation results (which represent the average of ergs of
100-times executions in the case of $|R|=4$ and $|R|=10$) of the accountable
ring signature scheme in Table V. We also calculate the corresponding ETH and
USD (using chart on 2022 December 1st). Currently, transaction fee to run
zkSync is not strictly established, and thus, they are reference values.
Nevertheless, they are quite expensive as a fee to issue a transaction. We
note that the ECDSA verification algorithm is run by 574,254 ergs. The main
reason of these high costs is inefficiency of elliptic curve operations in
Solidity. Moreover, it seems that the transaction needs to be divided in the
real environment due to the ergs costs because there is a limitation on the
transaction size that can be executed in a single transaction in the mainnet.

TABLE V: Ergs for Running ${\sf RVerify}$ Algorithm | $|R|=4$ | $|R|=10$
---|---|---
| 316,093,429 [ergs] | 471,635,458 [ergs]
${\sf RVerify}$ | 0.0316 [ETH] | 0.0471 [ETH]
| 40 [USD] | 60 [USD]

##  V Conclusion

In this paper, we proposed an anonymous yet accountable contract wallet system
based on account abstraction and accountable ring signatures. The proposed
system is implemented using Solidity for zkSync. Moreover, we discussed
potential of the proposed system, e.g., medical information sharing and asset
management. Since the current implementation results using Solidity show the
required costs are expensive, our result here might be regarded as somewhat
conceptual. However, to the best of our knowledge, no previous implementation
result is known that confirms the cost to run an accountable ring signature
scheme in Solidity to date, and we believe that our result can be seen as an
important stepping stone to provide anonymity and accountability
simultaneously in blockchain systems.

Investigating other applications of the proposed system will be left to future
work. The underlying account ring signature scheme does not provide post-
quantum security due to the discrete logarithm-based construction. Thus, it is
difficult to accept the current construction as a platform to manage large
amounts of assets due to the progress of quantum computing. Because a post-
quantum accountable ring signature scheme has been proposed in [7], it would
be interesting to employ the scheme, precisely, how to implement it using
Solidity is left to future work.

Acknowledgment: The authors would like to thank Dr. Miyako Ohkubo (NICT) for
her invaluable comments and suggestions. This work was supported by JSPS
KAKENHI Grant Numbers JP21K11897 and JP22H03588.

## References

  * [1] Arrest of suspected developer of Tornado Cash.  https://www.fiod.nl/arrest-of-suspected-developer-of-tornado-cash/.  August 12, 2022.
  * [2] StarkNet.  https://starkware.co/starknet/.
  * [3] zkSync.  https://zksync.io/.
  * [4] Jean-Philippe Aumasson, Daniel J. Bernstein, Ward Beullens, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hülsing, Panos Kampanakis, Stefan Kölbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, and Bas Westerbaan.  SPHINCS+: Submission to the NIST post-quantum project, v.3.1.  https://sphincs.org/data/sphincs+-r3.1-specification.pdf.
  * [5] Asaph Azaria, Ariel Ekblaw, Thiago Vieira, and Andrew Lippman.  MedRec: Using blockchain for medical data access and permission management.  In 2016 2nd International Conference on Open and Big Data (OBD), pages 25–30, 2016.
  * [6] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev.  Scalable, transparent, and post-quantum secure computational integrity.  IACR Cryptol. ePrint Arch., page 46, 2018.
  * [7] Ward Beullens, Samuel Dobson, Shuichi Katsumata, Yi-Fu Lai, and Federico Pintore.  Group signatures and more from isogenies and lattices: Generic, simple, and efficient.  In EUROCRYPT, pages 95–126, 2022.
  * [8] Ward Beullens, Shuichi Katsumata, and Federico Pintore.  Calamari and Falafl: Logarithmic (linkable) ring signatures from isogenies and lattices.  In ASIACRYPT, pages 464–492, 2020.
  * [9] Dmytro Bogatov, Angelo De Caro, Kaoutar Elkhiyaoui, and Björn Tackmann.  Anonymous transactions with revocation and auditing in hyperledger fabric.  In CANS, pages 435–459, 2021.
  * [10] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, Jens Groth, and Christophe Petit.  Short accountable ring signatures based on DDH.  In ESORICS, pages 243–265, 2015.
  * [11] Vitalik Buterin, Ansgar Dietrichs, Matt Garnett, Will Villanueva, and Sam Wilson.  EIP-2938: Account Abstraction.  https://eips.ethereum.org/EIPS/eip-2938, 2020.
  * [12] Jan Camenisch, Manu Drijvers, and Maria Dubovitskaya.  Practical uc-secure delegatable credentials with attributes and their application to blockchain.  In ACM CCS, pages 683–699, 2017.
  * [13] David Chaum and Eugène van Heyst.  Group signatures.  In EUROCRYPT, pages 257–265, 1991.
  * [14] Aisling Connolly, Jérôme Deschamps, Pascal Lafourcade, and Octavio Perez-Kempner.  Protego: Efficient, revocable and auditable anonymous credentials with applications to hyperledger fabric.  In INDOCRYPT, pages 249–271, 2022.
  * [15] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé.  CRYSTALS-Dilithium: A lattice-based digital signature scheme.  IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, 2018.
  * [16] Kai Fan, Shangyang Wang, Yanhui Ren, Hui Li, and Yintang Yang.  MedBlock: Efficient and secure medical data sharing via blockchain.  Journal of Medical Systems, 42(8):136:1–136:11, 2018.
  * [17] Tomilayo Fatokun, Avishek Nag, and Sachin Sharma.  Towards a blockchain assisted patient owned system for electronic health records.  Electronics, 10(5), 2021.
  * [18] Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang.  FALCON: Fast-fourier lattice-based compact signatures over NTRU.  https://falcon-sign.info/falcon.pdf.
  * [19] Tomoki Fujitani, Keita Emura, and Kazumasa Omote.  A privacy-preserving enforced bill collection system using smart contracts.  In AsiaJCIS, pages 51–60. IEEE, 2021.
  * [20] Merlin George and Anu Mary Chacko.  MediTrans - patient-centric interoperability through blockchain.  International Journal of Network Management, 32(3), 2022.
  * [21] Jens Groth.  Short non-interactive zero-knowledge proofs.  In ASIACRYPT, pages 341–358, 2010.
  * [22] Yiheng Liang.  Identity verification and management of electronic health records with blockchain technology.  In ICHI, pages 1–3. IEEE, 2019.
  * [23] Joseph K. Liu, Victor K. Wei, and Duncan S. Wong.  Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract).  In ACISP, pages 325–335, 2004.
  * [24] Xingye Lu, Man Ho Au, and Zhenfei Zhang.  Raptor: A practical lattice-based (linkable) ring signature.  In ACNS, pages 110–130, 2019.
  * [25] Mohammad Moussa Madine, Ammar Ayman Battah, Ibrar Yaqoob, Khaled Salah, Raja Jayaraman, Yousof Al-Hammadi, Sasa Pesic, and Samer Ellahham.  Blockchain for giving patients control over their medical records.  IEEE Access, 8:193102–193115, 2020.
  * [26] Abdullah Al Omar, Md. Zakirul Alam Bhuiyan, Anirban Basu, Shinsaku Kiyomoto, and Mohammad Shahriar Rahman.  Privacy-friendly platform for healthcare data in cloud based on blockchain environment.  Future Gener. Comput. Syst., 95:511–521, 2019.
  * [27] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova.  Pinocchio: nearly practical verifiable computation.  Communications of the ACM, 59(2):103–112, 2016.
  * [28] Sen Qiao, Varun Madathil, and Kemafor Anyanwu.  Integrating group signatures in complex decentralized marketplace transactions for improved buyer privacy.  In Blockchain, pages 139–148. IEEE, 2022.
  * [29] Ronald L. Rivest, Adi Shamir, and Yael Tauman.  How to leak a secret.  In ASIACRYPT, pages 552–565, 2001.
  * [30] Alex Roehrs, Cristiano Andre da Costa, and Rodrigo da Rosa Righi.  OmniPHR: A distributed architecture model to integrate personal health records.  Journal of Biomedical Informatics, 71:70–81, 2017.
  * [31] Teppei Sato, Keita Emura, Tomoki Fujitani, and Kazumasa Omote.  An anonymous trust-marking scheme on blockchain systems.  IEEE Access, 9:108772–108781, 2021.
  * [32] Kazuo Takaragi, Takashi Kubota, Sven Wohlgemuth, Katsuyuki Umezawa, and Hiroki Koyanagi.  Secure revocation features in eKYC - privacy protection in central bank digital currency.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 106-A(3), 2023.
  * [33] Qi Xia, Emmanuel Boateng Sifah, Kwame Omono Asamoah, Jianbin Gao, Xiaojiang Du, and Mohsen Guizani.  MeDShare: Trust-less medical data sharing among cloud service providers via blockchain.  IEEE Access, 5:14757–14767, 2017.
  * [34] Shouhuai Xu and Moti Yung.  Accountable ring signatures: A smart card approach.  In CARDIS, pages 271–286, 2004.


# LLM-POET: Evolving Complex Environments using Large Language Models

Fuma Aki  0009-0008-8620-9695 ,  Riku Ikeda  0009-0002-6919-3149 ,  Takumi
Saito  0009-0000-9838-0408 ,  Ciaran Regan  0009-0001-8377-7231 and  Mizuki
Oka  0000-0003-3915-4712<EMAIL_ADDRESS>University of Tsukuba1
Chome-1-1 TennodaiTsukubaIbarakiJapan305-8577

###### Abstract.

Creating systems capable of generating virtually infinite variations of
complex and novel behaviour without predetermined goals or limits is a major
challenge in the field of AI. This challenge has been addressed through the
development of several open-ended algorithms that can continuously generate
new and diverse behaviours, such as the POET and Enhanced-POET algorithms for
co-evolving environments and agent behaviour. One of the challenges with
existing methods however, is that they struggle to continuously generate
complex environments. In this work, we propose LLM-POET, a modification of the
POET algorithm where the environment is both created and mutated using a Large
Language Model (LLM). By fine-tuning a LLM with text representations of
Evolution Gym environments and captions that describe the environment, we were
able to generate complex and diverse environments using natural language. We
found that not only could the LLM produce a diverse range of environments, but
compared to the CPPNs used in Enhanced-POET for environment generation, the
LLM allowed for a 34% increase in the performance gain of co-evolution. This
increased performance suggests that the agents were able to learn a more
diverse set of skills by training on more complex environments.

Open-Ended Evolution, Large Language Models, POET Algorithm, Evolution Gym

††ccs: Computing methodologies Genetic algorithms††ccs: Computing
methodologies Evolutionary robotics††ccs: Computing methodologies Artificial
life

##  1\. Introduction

Recent advancements in AI have led to the development of agents that can
succeed in challenging, yet domain-specific tasks. Once the domain has been
mastered, however, learning typically ends. This domain-specific learning is
in contrast to the real world, which is an ever-changing, open-ended ecosystem
of new problems which require novel solutions. This challenge has been
addressed through the development of several open-ended algorithms that can
continuously generate new and diverse behaviours (NoveltySearch, ; NSLC2011, ;
MapElites2015, ). Among the various open-ended evolution (OEE) algorithms
developed, co-evolution, the simultaneous evolution of the agent and the
environment, is a remarkably advantageous approach, as demonstrated in studies
such as hide and seek (baker2019emergent, ) or minimal criterion co-evolution
(brant2017minimal, ; brant2020diversity, ).

To evaluate and compare co-evolution algorithms, Evolution Gym was developed,
which offers a benchmark for co-optimizing the design and control of soft-
robot agents (Evogym, ). In this benchmark, both the agent and the environment
are composed of different types of voxels (soft, rigid, actuators, empty),
resulting in a vast space of possible agent and environment configurations.

Paired Open-Ended Trailblazer (POET) (POET, ) and its successor Enhanced-POET
(wang2020enhanced, ) are co-evolutionary algorithms originally introduced to
solve challenges in OpenAI Gym environments, such as the “Bipedal Walker”
environment, but more recently have been implemented in Evolution Gym
(oka2023beginning, ). In these algorithms, both the agent and the environment
co-evolve, with agent-environment pairs optimised before agents are
transferred to other environments in the population for further learning. One
of the challenges with these POET algorithms, however, is the difficulty in
continually generating complex environments, as the level of environmental
difficulty tends to reach an upper limit.

To address this limitation, we propose LLM-POET, a modification of the
Enhanced-POET algorithm in which the environments are created and mutated
using a LLM instead of a CPPN. By fine-tuning a LLM with environment-caption
pairs, complex and varied environments can be generated using natural
language. Not only can the LLM create a wide range of environments, our
results suggest that implementing LLMs for environment generation in the POET
algorithm leads to an increase in the effectiveness of co-evolution due to the
diversity of environments created.

##  2\. LLM-POET

In this work, we propose LLM-POET, a modification of Enhanced-POET in which
the environment generating CPPN is replaced with a LLM. The LLM takes as input
a prompt that describes an environment in natural language and outputs a
string representation of an Evolution Gym environment. In addition, we
introduce an environment mutation method, making use of few-shot prompting and
the LLM’s ability to understand interesting environment mutations. These two
features are then implemented into the POET algorithm, enabling the continuous
evolution of complex environments through natural language. An overview of
LLM-POET is depicted in Fig 1.

Figure 1. An overview of LLM-POET.

LLM-POET.

###  2.1. Dataset Creation and LLM Fine-Tuning

To create a LLM capable of creating Evolution Gym environments, OpenAI’s
GPT-3.5 Turbo was fine-tuned using a dataset of environment-caption pairs.
These environment caption-pairs were manually created using the Evolution Gym
design tool GUI, and exported in JSON format. For each environment, a caption
was also manually created, describing the shape and abstract difficulty of the
environment, as well as its size. This process is illustrated in Fig 2.

Figure 2. Overview of LLM fine-tuning.

Taking inspiration from MarioGPT (sudhakaran2023mariogpt, ), the proposed LLM
takes as input the description of an environment and outputs a string
containing characters representing the different types of voxels in Evolution
Gym, such as ‘H’ for rigid, ‘S’ for soft or ‘-’ for empty voxels. At inference
time, instructions such as “simple environment”, “environment with many
holes”, and “ difficult environment with mountains” can be given, and the
corresponding environment is output in two dimensions, as in Evolution Gym.

After fine-tuning however, the size of the environment output by the LLM does
not always match the size requested in the prompt. Additionally, the LLM may
occasionally output symbols which do not correspond to Evolution Gym voxels.
To overcome these discrepancies, minor post-processing of the output string is
necessary. After post-processing, the strings are converted into Evolution Gym
environments, examples of which are shown in Fig 3.

In addition to being able to create a wide range of environments, the fine-
tuned LLM is shown to create environments with words such as “pyramid” or
“spiky” without these words being used in the fine-tuning dataset.
Furthermore, since there were no environments in the training dataset where
the blocks were arranged vertically, vertical environments generated from
words such as “spiky” in Fig 3(d) demonstrate that fine-tuning allowed the LLM
to understand the relationship between the caption and the environment.

(a) 100*20 size Evolution Gym environment that consists of flat terrain.

(b) 100*20 size Evolution Gym environment that is shaped like a pyramid.

(c) 100*20 size Evolution Gym environment that is complex and challenging.

(d) 100*20 size Evolution Gym environment that is spiky.xxxxxx

Figure 3. Environments generated using a variety of prompts with the fine-
tuned LLM.

###  2.2. Integration with POET

As POET is an open-ended learning algorithm which continuously alters existing
environments, a method to evolve environments using a LLM is proposed. To
achieve this environment mutation, two approaches are used. First, due to the
nondeterministic nature of the LLM’s output when a non-zero temperature is
used, an environment can be mutated by simply prompting the LLM with the same
initial prompt. Second, to increase the complexity of environments, mutating
the input prompt itself is also considered. Mutating the prompt using LLMs is
inspired by (bradley2023qualitydiversity, ), which showed that LLMs have
demonstrated an ability to recognise interesting mutations. To achieve this
mutation, few-shot prompting was used to alter the original prompt.

Figure 4. Mutating environments with the original or mutated prompts. Figure
5. Calculating score differences. The difference between PPO only score (left)
and the POET score (right) quantifies the ability of the environment
generation model to create diverse environments, leading to improved agent
learning.

When integrating this mutation into the Enhanced-POET algorithm, either the
original prompt or a mutated prompt will be input to the LLM with a 50%
probability. An example of this prompt and environment mutation is shown in
Fig 4. The environment-generating LLM and the environment mutation method can
then be implemented in the POET algorithm to allow for continually evolving
environments.

##  3\. Experiment

To evaluate LLM-POET and Enhanced-POET, direct comparison of scores is
impractical as the POET algorithm is continuously generating different
environments. To overcome this, the following evaluation method is proposed.
For each environment generated by Enhanced-POET and LLM-POET, an agent is
trained using PPO alone, without co-evolution. By comparing the best score of
the agent trained with PPO only, to the score of the agent trained with either
Enhanced-POET or LLM-POET, the performance gain of co-evolution in that
environment can be measured. This is depicted in Fig 5.

In this evaluation, the difference in scores obtained by the agents trained
using the POET algorithm and the PPO algorithm can be considered as the effect
of learning from the POET algorithm. This is because the PPO algorithm is used
when the agent learns the environment within the POET algorithm, and the
difference in scores can be attributed to the effect of the agent learning
while transferring between environments. Therefore, in this experiment, where
the only difference is the environment generation method, it can be said that
the method with more diverse environments had a larger difference between the
POET and PPO scores.

The experiment and evaluation procedure can then be summarized as:

  1. (1)

Use LLM to create an environment for use in the POET algorithm (LLM-POET).

  2. (2)

Obtain the score of the agent in the environment using the POET algorithm.

  3. (3)

Extract each environment, perform reinforcement learning with PPO five times,
and compare the best score with that of POET.

  4. (4)

Repeat the above with the CPPNs for environment generation (Enhanced-POET).

  5. (5)

Compare environment generation methods by comparing the score differences of
step 3.

with the POET algorithm taking the following form:

  1. (1)

Generate 10 initial environment pairs.

  2. (2)

Perform 30 steps of PPO learning for all environment-agent pairs. PPO performs
learning four times in each iteration. The score of an agent in an environment
is determined by how much distance the agent has travelled along the x-axis.

  3. (3)

Transfer each agent to another environment. If the agent in the new
environment has a better score than the agent originally trained in the
environment, replace the agent.

  4. (4)

Randomly select a single high-scoring environment and generate a new
environment using either CPPNs or a LLM.

Steps 2-4 were repeated 100 times to train agents on a vast range of
environments.

##  4\. Results

(a) All environments generated using LLM-POET.

(b) All environments generated using Enhanced-POET.

Figure 6. Comparison of environments generated by LLM-POET and Enahnced-POET

The LLM-POET algorithm resulted in 97 unique environments, with the Enhanced-
POET algorithm resulting in 95 environments, shown in niche history in Fig
6(a) and 6(b) respectively. The difference between the best PPO scores and the
best POET scores for these environments was then calculated. The average score
difference was found to be $1.11\pm 0.42$ for LLM-POET, and $0.83\pm 0.42$ for
Enhanced-POET, a 34% increase in the performance gain of co-evolution when
using LLMs for environment generation. One possible explanation for this is
the increased complexity of environment in the niche history.

Additionally, the histogram of score differences is shown in Fig 7. The
skewness of these distributions was found to be $1.517$ and $1.652$ for the
LLM-POET and Enhanced-POET difference respectively, with the lower value for
LLM-POET indicating that it is slightly more left-skewed with a greater
difference in scores. Although the uncertainty in the result is high, the 34%
increase in the POET performance gain suggests that the agents were able to
train on more complex environments using LLMs for environment generation.

Figure 7. The distribution of score differences.

##  5\. Conclusion

In this work, we introduce LLM-POET, a modification of the Enhanced-POET
algorithm, in which a LLM is used for both environment generation and
mutation. Not only have we shown that a fine-tuned model can generate
Evolution Gym compatible environments, but when implemented into an open-ended
learning algorithm such as POET, this environment generation method can lead
to an increase in the effectiveness of open-ended learning.

To evaluate the effectiveness of LLMs for open-ended learning, LLM-POET is
compared to Enhanced-POET, which uses CPPNs for environment generation. Our
results suggest that LLM-POET has a 34.4% increase in the effectiveness of
open-ended learning when compared to Enhanced-POET. This improvement in the
performance of the POET algorithm indicates that the environments generated by
LLM-POET have more diversity, which allows the agents to learn more
sophisticated behaviors, addressing one of the key challenges in open-ended
research.

###### Acknowledgements.

A special thanks to Nanami Iwahashi for assistance with the figures, enhancing
the clarity of this work.

## References

  * [1] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch.  Emergent tool use from multi-agent autocurricula.  arXiv preprint arXiv:1909.07528, 2019.
  * [2] Jagdeep Bhatia, Holly Jackson, Yunsheng Tian, Jie Xu, and Wojciech Matusik.  Evolution gym: A large-scale benchmark for evolving soft robots.  Advances in Neural Information Processing Systems, 34:2201–2214, 2021.
  * [3] Herbie Bradley, Andrew Dai, Hannah Teufel, Jenny Zhang, Koen Oostermeijer, Marco Bellagente, Jeff Clune, Kenneth Stanley, Grégory Schott, and Joel Lehman.  Quality-diversity through ai feedback.  arXiv preprint arXiv:2310.13032, 2023.
  * [4] Jonathan C. Brant and Kenneth O. Stanley.  Minimal criterion coevolution: A new approach to open-ended search.  In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 67–74, New York, NY, USA, 2017. Association for Computing Machinery.
  * [5] Jonathan C. Brant and Kenneth O. Stanley.  Diversity preservation in minimal criterion coevolution through resource limitation.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20, pages 58–66, New York, NY, USA, 2020. Association for Computing Machinery.
  * [6] Joel Lehman and Kenneth O. Stanley.  Abandoning Objectives: Evolution Through the Search for Novelty Alone.  Evolutionary Computation, 19(2):189–223, 06 2011.
  * [7] Joel Lehman and Kenneth O. Stanley.  Evolving a diversity of virtual creatures through novelty search and local competition.  In Proc. of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO ‘11), pages 211–218, 2021.
  * [8] Jean-Baptiste Mouret and Jeff Clune.  Illuminating search spaces by mapping elites.  arXiv preprint arXiv:1504.04909, 2015.
  * [9] Mizuki Oka, Takumi Saito, and Takeshi Shimada.  Open-ended Evolutionary Algorithms in Python.  O’Reilly, 2023.
  * [10] S Sudhakaran, M González-Duque, C Glanois, M Freiberger, E Najarro, and S Risi.  Mariogpt: open-ended text2level generation through large language models.  arXiv preprint arxiv:2302.05981, 2023.
  * [11] Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley.  Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions.  arXiv preprint arXiv:1901.01753, 2019.
  * [12] Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeffrey Clune, and Kenneth Stanley.  Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions.  In International Conference on Machine Learning, pages 9940–9951. PMLR, 2020.


# A Python library for nonlinear system identification using Multi-Gene
Genetic Programming algorithm

Henrique Carvalho de Castro
Universidade Federal de Lavras
Minas Gerais, MG, Brazil
<EMAIL_ADDRESS>
&Bruno Henrique Groenner Barbosa
Universidade Federal de Lavras
Minas Gerais, MG, Brazil
<EMAIL_ADDRESS>
The authors would like to thank the nancial support from the Brazilian
agencies Capes, CNPq and FAPEMIG.

###### Abstract

Models can be built directly from input and output data trough a process known
as system identification. The Nonlinear AutoRegressive with eXogenous inputs
(NARMAX) models are among the most used mathematical representations in the
area and has many successful applications on data-driven modeling in different
fields. Such models become extremely large when they have high degree of non-
linearity and long-term dependencies. Hence, a structure selection process
must be performed to make them parsimonious. In the present paper, it is
introduced a toolbox in Python that performs the structure selection process
using the evolutionary algorithm named Multi-Gene Genetic Programming (MGGP).
The toolbox encapsulates basic tools for parameter estimation, simulation and
validation, and it allows the users to customize their evaluation function
including prior knowledge and constraints in the individual structure (gray-
box identification).

_Keywords_ System identification $\cdot$ NARMAX $\cdot$ MGGP $\cdot$ Nonlinear
systems

##  1 Motivation and significance

System identification is the process through which models are built directly
from input and output data. The first step in this process is to choose the
mathematical representation that will fit the data. In this sense, the NARMAX
(Nonlinear Autoregressive Moving Average with eXogenous inputs) models
Leontaritis and Billings (1985) are of great interest due to their flexibility
and representation capabilities. They are composed of lagged input, output and
prediction errors. The key point in working with such models is the selection
of the appropriate structure, which must be as simple as possible, but
sufficiently complex to capture the dynamics underlying the data Aguirre and
Letellier (2009).

The Forward Regression Orthogonal Estimator (FROE) Billings et al. (1989) is a
standard algorithm to perform the structure selection of NARX models. It is
based on the Error Reduction Ratio (ERR) measure, which evaluates how good
each single model term is in explaining the output data variance. There are
some important disadvantages in the use of this technique: it has limitations
for training data with the presence of certain input characteristics Piroddi
and Spinelli (2003); and it suffers from the curse of dimensionality with the
increment of the degree of non-linearity and higher long-term dependencies. To
circumvent these problems, one can resort to Evolutionary Algorithms (EA),
such as Genetic Algorithms (GA) Holland (1975); Goldberg and Holland (1988),
Genetic Programming (GP) Koza (1992) and Multi-Gene Genetic Programming (MGGP)
Hinchliffe et al. (1996); Hinchliffe (2001); Hinchliffe and Willis (2003).
Recently, several modeling and forecasting works have been developed with the
use of MGGP (as in Ghareeb and El Saadany (2013); Mehr and Kahya (2017);
Safari and Mehr (2018); Riahi-Madvar et al. (2019)). The algorithm has shown
itself to be very flexible and to present good performance.

To the best of the authors’ knowledge, the only available toolbox capable of
performing MGGP optimization is the GPTIPS Searson et al. (2010), a machine
learning platform for MATLAB focused on symbolic regression. Unfortunately, it
is restricted to those who own the licenses which hinders contribution from
the community.

This paper presents the mggp package in python. In addition to the MGGP
evolutionary algorithm framework, we encapsulate basic methods to work with
NARMAX models, i.e. parameter estimation, model simulation and validation
methods; so that the user can easily work on the evaluation function to be
optimized.

##  2 Software description

The current toolbox is focused on the structure selection of NARX/NARMAX
models using an evolutionary algorithm called MGGP. To structure the adequate
framework that is representative of such models, we attempted to develop a
well organized Object Oriented program that comprises all necessary tools to
perform the task, i.e. model coding (representation), basic parameter
estimation, simulation and validation methods, and the aimed structure
selection algorithm.

Figure 1: MGGP individual representation. It is a sequel of genetic programs
as basis functions. The linear combination of these programs represents the
mathematical model. It is highlighted one single gene that represents the
mathematical function $2x_{2}+x_{1}$.

###  2.1 Representation

In NARMAX models, the current output is obtained from past input-output and
residual signals, as follows:

$\begin{split}y[k]=\mathit{F}^{l}(&y[k-1],...,y[k-n_{y}],u[k-1],...,\\\
&u[k-n_{u}],\xi[k-1]...\xi[k-n_{\xi}])+\xi[k],\end{split}$ (1)

where $F[\cdot]$ is a nonlinear function; $y[k]$, $u[k]$ and $\xi[k]$ are the
output signal, input signal and residual vector, respectively; and $n_{y}$,
$n_{u}$ and $n_{\xi}$ are their respective maximum lags. These models are
extensions of NARX models in which residual terms are included to remove
parameters’ bias. In the case of polynomial models, the nonlinear function is
a polynomial function of degree $l$ ($F^{l}$). The MGGP fits naturally as a
NARMAX description since it can be represented as the linear combination of
separated basis functions:

$g(\varphi,\Theta)=\sum^{m}_{i=1}\theta_{i}g_{i}(\varphi),$ (2)

where $m$ is the number of basis functions, $g_{i}$ represents individual
functions and $\theta_{i}$ the model parameters. It can be seen as a GA
individual Holland (1975); Goldberg and Holland (1988) in which each gene
contains one GP individual (Koza, 1992; Eiben et al., 2003; Poli et al., 2008)
as the basis function (see more in Hinchliffe (2001) and Hinchliffe and Willis
(2003)). Figure 1 graphically presents an MGGP individual representation as a
sequel of GP individuals, which are tree representations of mathematical
functions. To codify such representation we use the GA and GP frameworks
available in the Distributed Evolutionary Algorithms in Python (DEAP) Fortin
et al. (2012) package.

Figure 2: Mono-objective MGGP optimization algorithm flowchart.

###  2.2 MGGP algorithm

As an EA, the MGGP possesses a standard behavior. It begins with a initial
population of random individuals (chromosomes) and at each generation (main
loop) the best solutions are sought (selection), then combined
(recombination/reproduction/crossover and mutation) in order to generate even
better individuals. The MGGP works with two levels of crossover: low-level
crossover and high-level crossover. In the former, one gene is randomly
selected from each parent individual and they exchange GP subtrees as genetic
material. In the latter, the genetic materials are exchanged as entire basis
functions in a way similar to GA one-point crossover. We include two kinds of
mutation in the algorithm: an inner mutation, which occurs as a GP subtree
mutation, and an outer mutation, which swaps a gene for a new one, with an
entirely new basis function (see Poli et al. (2008) for details on GP genetic
operators).

Figure 2 exhibits a flowchart of the toolbox mono-objective MGGP algorithm. It
begins with a initial population that is evaluated. Then, the generation loop
starts: i) the parent individuals are selected via tournament, ii) each parent
couple has a chance to be recombined (CXPB), iii) each individual that has not
been recombined has a chance to be mutated (MTPB), iv) the individuals are
evaluated, and v) the elitism operator is applied. The evaluation function
shall be customized by the user.

The MGGP multi-objective evolution uses the NSGA2 framework Deb et al. (2000).
It differs from the mono-objective optimization in the tournament and
selection of the next generation (elitism) which must observe the Pareto
Optimal Set.

###  2.3 Computational implementation

The mggp package, available on GitHub for pull
requests111https://github.com/CastroHc/MGGP and in the PyPI repository for
installation222pip install mggp, is composed of two classes: the mggpElement
class and the mggpEvolver class.

An mggpElement object is responsible for carrying the attributes and methods
used to create, simulate and evaluate individuals from an MGGP population.
This class is able to build single-input single-output (SISO) and multiple-
input single-output (MISO) models and works with NARX and NARMAX
representations. It comprises three simulation methods, i.e. one-step-ahead
prediction, free-run simulation and multiple-shooting, and their respective
mean-squared error (MSE) scores (see Ribeiro et al. (2020) for comparison
analysis); the Least Squares (LS) and Extended Least Squares (ELS) parameter
estimation methods Young (1968); and a standard FROE structure selection
method Chen et al. (1989). The NARMAX terms, which are GP individuals, are
constructed from a set of mathematical functions that can be customized by the
user. The mggpElement class has a built-in back-shift operator to determine
the lag of a term.

An mggpEvolver object is responsible to execute the evolution of a population.
The individuals from this population are created according to the primitive
set of mathematical functions defined in the mggpElement object. It is able to
perform mono- and multi-objective optimizations.

##  3 Illustrative Example

In this section we illustrate how to use the mggp toolbox through a simple
example. We will show (i) how to set up an mggpElement object, (ii) how to
define a specific model and simulate it, (iii) how to build an evaluation
function, and (iv) how to set up an mggpEvolver object and run the
optimization algorithm.

###  3.1 Simulate a system using the mggpElement class

Use the setPset() method to define the maximum delay of a single back-shift
operator as one ($q1$) and the number of variables as two (one input and one
output). This way the primitive set is able to define polynomial NARX models
(it is already set to use multiplication function).

⬇

from mggp import mggpElement

element = mggpElement()

element.setPset(maxDelay=1,numberOfVariables=2)

element.renameArguments({’ARG0’:’y1’,’ARG1’:’u1’})

Consider a stochastic system given by Piroddi and Spinelli (2003):

$y[k]=0.75y[k-2]+0.25u[k-1]-0.20y[k-2]u[k-1],$

where $u[k]$ is a White Gaussian Noise with mean of zero and variance one. Use
the createModel() method to build a model from a list of strings that is
representative of the system and then compile it. The model parameters are
known.

⬇

listStrings = [’q1(y1)’,’u1’,’mul(q1(y1),u1)’]

model = element.createModel(listStrings)

element.compile_model(model)

theta = np.array([0.75,0.25,-0.20])

Use the predict_freeRun() method to simulate the system from a initial
condition and the input vector.

⬇

u = np.random.normal(loc=0,scale=1,size=(500))

y0 = np.zeros(2)

y = element.predict_freeRun(model,theta,y0,u[:-1])

###  3.2 Define the evaluation function and run the optimization

The MGGP is an optimization algorithm that minimizes an evaluation (or cost)
function. In this sense, the mggpEvolver class is set to run an evaluation
function that receives as only argument the individual to be evaluated. We
present a very simple example in which we seek to minimize the one-step-ahead
MSE and the model parameters are estimated via LS method. An exception
treatment must be performed to keep the program running after a Singular
Matrix Exception error is raised.

⬇

def evaluate(ind):

try:

element.compile_model(ind)

theta = element.ls(ind,y,u)

return element.score_osa(ind, theta, y, u),

except np.linalg.LinAlgError:

return np.inf,

Use the mggpEvolver constructor to set up the MGGP parameters. It must be
defined the population size (popSize), the crossover probability (CXPB), the
mutation probability (MTPB), the number of generations to be run (n_gen), the
maximum height of the trees that represents model terms (maxHeight), the
maximum number of terms an individual may possess (maxTerms), the percentage
of individuals from a population to be kept after a generation (elite) and the
mggpElement object that carries information about individual creation. The
evaluation function is sent as an argument of the run() method, which returns
a log of fitnesses history and the resultant elite population (hall of fame -
hof).

⬇

from mggp import mggpEvolver

mggp = mggpEvolver(popSize=500,CXPB=0.9,MTPB=0.1,n_gen=50,

maxHeight=3,maxTerms=5,verbose=True,elite=10,

element=element)

hof,log = mggp.run(evaluate=evaluate)

model = hof[0]

for term in model:

print(term)

###  3.3 Multi-objective example

For a multi-objective optimization, the mggpElement must be set to create
individuals with the weight attribute that indicates the number of objectives
and the type of optimization (maximization/minimization). This is done in the
constructor, as follows:

⬇

from mggp import mggpElement

element = mggpElement(weights=(-1,-1))

element.setPset(maxDelay=1,numberOfVariables=2)

element.renameArguments({’ARG0’:’y1’,’ARG1’:’u1’})

The argument ‘weights=(-1,-1)’ defines an mggpElement object that minimizes
two objectives. Next, define the cost function to minimize the objectives: (i)
the one-step-ahead prediction error and (ii) the number of model terms. The
mggpEvolver object may be initialized as in the previous example. Finally, use
the runMO() method to execute the optimization:

⬇

def evaluate(ind):

try:

element.compile_model(ind)

theta = element.ls(ind,y,u)

return element.score_osa(ind, theta, y, u), len(ind)

except np.linalg.LinAlgError:

return np.inf, np.inf

hof,log = mggp.runMO(evaluate=evaluate,popPercent=0.8)

The attribute popPercent defines the number of individuals to be kept in the
next generation. It is a percentage of popSize and selects this number of
individuals from the current population plus the resultant offspring observing
the Pareto Optimal Set.

##  4 Impact

The mggp is an open source and easy-to-use toolbox that performs the nonlinear
system identification task via MGGP algorithm. It allows the automatic
construction of NARX/NARMAX models using any mathematical function included in
the primitive set of an mggpElement object (e.g. exponential, sine, tanh,
greater than, etc.). The built-in back-shift operator releases the user of the
responsibility to predetermine maximum term lags and to build the whole set of
candidate terms. Further, researchers can customize the evaluation function
using their own algorithms that are not encapsulated in mggpElement class.
This widens the toolbox application allowing the inclusion of prior knowledge
to evaluate individuals and set constraints in the parameters values or in the
model structure (gray-box identification).

##  5 Conclusion

In the present work a new package in python is introduced that performs system
identification using NARMAX models. The package encapsulates basic methods of
black-box identification such as LS, ELS and FROE and performs mono- and
multi-objective optimizations. The users are free to build their cost
functions using any method not encapsulated in the package classes. Thus, a
broad range of researches in the area of system identification via MGGP is
opened. The project is available on GitHub so that users can contribute via
forking and making pull requests, please refer to the repository indicated in
the metadata.

###  5.1 Future versions

Some issues for future versions are listed in the following.

MIMO models: the extension to multiple-output is essential to widen
applications. In its actual version, the mggp package is capable of building
up to MISO models.

ERR methods: there are several algorithms of the FROE type for structure
selection using ERR measures with different properties and capabilities.

Human-machine interface: we have received feedback from users about the use of
the package for several inputs. It may get complicated for the users to
implement their cost functions and perform analysis. We intend to simplify the
interface to ease its use.

Optimization algorithms: there are few built-in operators for cross-over and
mutation processes. The algorithms for mono- and multi-optimization are rigid
and do not accept modifications. We intend to widen the possibilities taking
advantage of the object oriented structure of the package and create an
abstract interface for genetic operators. Thus, in future versions, the user
may customize the optimization algorithm including genetic operator objects
into the mggpEvolver object.

## References

  * Leontaritis and Billings [1985] IJ Leontaritis and Stephen A Billings.  Input-output parametric models for non-linear systems part i: deterministic non-linear systems.  _International journal of control_ , 41(2):303–328, 1985.
  * Aguirre and Letellier [2009] Luis A Aguirre and Christophe Letellier.  Modeling nonlinear dynamics and chaos: a review.  _Mathematical Problems in Engineering_ , 2009, 2009.
  * Billings et al. [1989] SA Billings, S Chen, and MJ Korenberg.  Identification of mimo non-linear systems using a forward-regression orthogonal estimator.  _International journal of control_ , 49(6):2157–2189, 1989.
  * Piroddi and Spinelli [2003] Luigi Piroddi and William Spinelli.  An identification algorithm for polynomial narx models based on simulation error minimization.  _International Journal of Control_ , 76(17):1767–1781, 2003.
  * Holland [1975] John H Holland.  Adaptation in natural and artificial systems.  _The University of Michigan Press_ , 1975.
  * Goldberg and Holland [1988] David E Goldberg and John H Holland.  Genetic algorithms and machine learning.  _Machine learning_ , 3(2):95–99, 1988.
  * Koza [1992] John R Koza.  _Genetic programming: on the programming of computers by means of natural selection_ , volume 1.  MIT press, 1992.
  * Hinchliffe et al. [1996] MP Hinchliffe, MJ Willis, H Hiden, MT Tham, B McKay, and GW Barton.  Modelling chemical process systems using a multi-gene genetic programming algorithm.  In _Genetic Programming: Proceedings of the First Annual Conference (late breaking papers)_ , pages 56–65, 1996.
  * Hinchliffe [2001] M. P. Hinchliffe.  _Dynamic modelling using genetic programming_.  PhD thesis, University of Newcastle upon Tyne, UK, 2001.
  * Hinchliffe and Willis [2003] Mark P. Hinchliffe and Mark J. Willis.  Dynamic systems modelling using genetic programming.  _Computers $\&$ Chemical Engineering_, 27(12):1841 – 1854, 2003.
  * Ghareeb and El Saadany [2013] W. T. Ghareeb and E. F. El Saadany.  Multi-Gene Genetic Programming for Short Term Load Forecasting.  In _2013 3rd International Conference on Electric Power and Energy Conversion Systems (EPECS)_ , International Conference on Electric Power and Energy Conversion Systems, 2013.
  * Mehr and Kahya [2017] Ali Danandeh Mehr and Ercan Kahya.  A Pareto-optimal moving average multigene genetic programming model for daily streamflow prediction.  _Journal of Hydrology_ , 549:603–615, 2017.
  * Safari and Mehr [2018] Mir Jafar Sadegh Safari and Ali Danandeh Mehr.  Multigene genetic programming for sediment transport modeling in sewers for conditions of non-deposition with a bed deposit.  _International Journal of Sediment Research_ , 33(3):262–270, 2018.
  * Riahi-Madvar et al. [2019] Hossien Riahi-Madvar, Majid Dehghani, Akram Seifi, and Vijay P. Singh.  Pareto Optimal Multigene Genetic Programming for Prediction of Longitudinal Dispersion Coefficient.  _Water Resources Management_ , 33(3):905–921, 2019.
  * Searson et al. [2010] Dominic P Searson, David E Leahy, and Mark J Willis.  Gptips: an open source genetic programming toolbox for multigene symbolic regression.  In _Proceedings of the International multiconference of engineers and computer scientists_ , volume 1, pages 77–80. Citeseer, 2010.
  * Eiben et al. [2003] Agoston E Eiben, James E Smith, et al.  _Introduction to evolutionary computing_ , volume 53.  Springer, 2003.
  * Poli et al. [2008] Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee.  _A field guide to genetic programming_.  Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008.
  * Fortin et al. [2012] Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné.  DEAP: Evolutionary algorithms made easy.  _Journal of Machine Learning Research_ , 13:2171–2175, jul 2012.
  * Deb et al. [2000] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and Tanaka Meyarivan.  A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii.  In _International conference on parallel problem solving from nature_ , pages 849–858. Springer, 2000.
  * Ribeiro et al. [2020] Antônio H. Ribeiro, Koen Tiels, Jack Umenberger, Thomas B. Schön, and Luis A. Aguirre.  On the smoothness of nonlinear system identification.  _Automatica_ , 121:109158, 2020.
  * Young [1968] Peter C Young.  The use of linear regression and related procedures for the identification of dynamic processes.  In _Seventh Symposium on Adaptive Processes_ , pages 53–53, Los Angeles, CA, USA, 1968. IEEE.
  * Chen et al. [1989] Sheng Chen, Stephen A Billings, and Wan Luo.  Orthogonal least squares methods and their application to non-linear system identification.  _International Journal of control_ , 50(5):1873–1896, 1989.