You can lie but not deny: SWMR registers with signature properties in systems with Byzantine processes

We define and show how to implement SWMR registers that provide properties of unforgeable digital signatures - without actually using such signatures - in systems with Byzantine processes. More precisely, we first define SWMR verifiable registers. Intuitively, processes can use these registers to write values as if they are ``signed'', such that these ``signed values'' can be ``verified'' by any process and ``relayed'' to any process. We give a signature-free implementation of such registers from plain SWMR registers in systems with $n > 3f$ processes, $f$ of which can be Byzantine. We also give a signature-free implementation of SWMR sticky registers from SWMR registers in systems with $n > 3f$ processes. Once the writer $p$ writes a value $v$ into a SWMR sticky register $R$, the register never changes its value. Note that the value $v$ can be considered ``signed'' by $p$: once $p$ writes $v$ in $R$, $p$ cannot change the value in $R$ or deny that it wrote $v$ in $R$, and every reader can verify that $p$ wrote $v$ just by reading $R$. This holds even if the writer $p$ of $R$ is Byzantine. We prove that our implementations are optimal in the number of Byzantine processes they can tolerate. Since SWMR registers can be implemented in message-passing systems with Byzantine processes and $n > 3f$ [9], the results in this paper also show that one can implement verifiable registers and sticky registers in such systems.