A communication relay program for causing a computer in a relay device in a communication system including a plurality of nodes having a distributed ledger function of storing one or more identifiers of a plurality of communication devices and a public key used for communication by a communication device in a distributed ledger to share the distributed ledger, the plurality of communication devices each of which is coupled to any one of the nodes, and the relay device coupled to any one of the nodes to execute, the communication relay program comprising: a transmission/reception process of transmitting and receiving a message to and from the plurality of communication devices; an authentication process of: transmitting to the node connected to the relay device request message including an identifier corresponding to a communication device included in the plurality of communication devices of a transmission source of the message for requesting a public key which corresponds to the communication device, receiving a response message including information on whether or not the public key is detected from among the distributed ledger, the response message being included the public key when the public key is detected, and authenticating a signature included in the message with the public key which is received when the public key is detected by the node; and a relay process of, when receiving a communication message including communication data to be transmitted to a second communication device by the first communication device, performing the authentication process on the communication message, and transmitting the communication message to the second communication device when the authentication is successful. a transmission/reception process of transmitting and receiving a message to and from the plurality of communication devices; an authentication process of: transmitting to the node connected to the relay device request message including an identifier corresponding to a communication device included in the plurality of communication devices of a transmission source of the message for requesting a public key which corresponds to the communication device, receiving a response message including information on whether or not the public key is detected from among the distributed ledger, the response message being included the public key when the public key is detected, and authenticating a signature included in the message with the public key which is received when the public key is detected by the node; and transmitting to the node connected to the relay device request message including an identifier corresponding to a communication device included in the plurality of communication devices of a transmission source of the message for requesting a public key which corresponds to the communication device, receiving a response message including information on whether or not the public key is detected from among the distributed ledger, the response message being included the public key when the public key is detected, and authenticating a signature included in the message with the public key which is received when the public key is detected by the node; and a relay process of, when receiving a communication message including communication data to be transmitted to a second communication device by the first communication device, performing the authentication process on the communication message, and transmitting the communication message to the second communication device when the authentication is successful.