CSAR: A practical and provable technique to make randomized systems accountable

Michael Backes, Peter Druschel, Andreas Haeberlen, and Dominique Unruh.
in NDSS 2009, The Internet Society, pp. 341-353, February 2009.


We describe a technique that enables accountability in systems that use randomized protocols. Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time, correct nodes are always able to defend themselves against false accusations. The key contribution is a novel technique for generating cryptographically strong, accountable randomness. The technique generates a pseudo-random sequence and a proof that the elements of this sequence have been correctly generated, while avoiding that future values of the sequence can be predicted. External auditors can check if a node deviates from its expected behavior without learning anything about the node's future random choices. In particular, an accountable node does not need to leak secrets that would make its future actions predictable. The technique is practical and efficient. We demonstrate that our technique is practical by applying it to a simple server that uses random sampling for billing purposes.

Files available online

This publication is accompanied by links to downloadable versions of this publication. These documents do not necessarily correspond exactly to the cited version. Instead, in most cases full, updated or preliminary versions are provided. For access to the official version, follow the "Official version" link to the publishers site.

Slides used in my talks are available upon personal request, as long as you agree not to disseminate them to a wider audience or make them available online. If in doubt, please ask.