<commit_before>\documentclass[11pt, oneside]{article}
\usepackage[margin=.9in]{geometry}
\usepackage{pgfplots}
\pgfplotsset{compat=default}
\newcommand{\cuckoo}{{\rm cuckoo}}
\newcommand{\hash}{{\rm siphash}}
\usepackage{hyperref}
\usepackage{listings}
\title{Cuckoo Cycle: \protect\\ a graph-theoretic proof-of-work system}
\author{<NAME>}
\begin{document}
\maketitle

\begin{abstract}
We introduce the first graph-theoretic proof-of-work system,
based on finding cycles in large random graphs.
Such problems are arbitrarily scalable and trivially verifiable.
Our implementation uses 1 bit per edge, and up to 1 bit per node.
We hypothesize that using significantly less causes superlinear slowdown.
\end{abstract}

\section{Introduction}
A ``proof of work'' (PoW) system allows a verifier to check with negligible
effort that a prover has expended a large amount of computational effort.
Originally introduced as a spam fighting measure, 
where the effort is the price paid by an email sender for demanding the
recipient's attention, they now form one of the cornerstones of
crypto-currencies.

As proof-of-work for new blocks of transactions,
Bitcoin~\cite{nakamoto2009bitcoin} adopted Adam Back's hashcash~\cite{back2002} proof-of-work.
This requires finding a nonce value such that
application of a cryptographic hash function (twofold SHA256 in Bitcoin's case)
to this nonce (and the rest of the block header) results in a number with
many leading 0s. The number of leading 0s is dynamically adjusted by the protocol
so as to maintain a certain average block interval (10-minutes for Bitcoin).

Since Bitcoin, many other crypto-currencies have adopted hashcash, with various
choices of underlying hash function. the most well-known being {\em scrypt} as
used in Litecoin.

Primecoin~\cite{king2013} introduced the notion of a number-theoretic proof-of-work,
as the first alternative to hashcash among crypto-currencies.
This requires finding long chains of nearly doubled prime numbers, with a certain
relation to the block header.<commit_msg>rephrase abstract<commit_after>\documentclass[11pt, oneside]{article}
\usepackage[margin=.9in]{geometry}
\usepackage{pgfplots}
\pgfplotsset{compat=default}
\newcommand{\cuckoo}{{\rm cuckoo}}
\newcommand{\hash}{{\rm siphash}}
\usepackage{hyperref}
\usepackage{listings}
\title{Cuckoo Cycle: \protect\\ a graph-theoretic proof-of-work system}
\author{<NAME>}
\begin{document}
\maketitle

\begin{abstract}
We introduce the first graph-theoretic proof-of-work system,
based on finding cycles in large random graphs.
Such problems are arbitrarily scalable and trivially verifiable.
Our cycle finding implementation uses 1 bit per edge, and up to 1 bit per node.
Runtime is linear in graph size and dominated by random access latency.
We exhibit a memory-time trade-off (TMTO) where using $k$ times less memory
incurs a slowdown of $k$ times half the cycle length, which we hypothesize
is the best possible.
\end{abstract}

\section{Introduction}
A ``proof of work'' (PoW) system allows a verifier to check with negligible
effort that a prover has expended a large amount of computational effort.
Originally introduced as a spam fighting measure, 
where the effort is the price paid by an email sender for demanding the
recipient's attention, they now form one of the cornerstones of
crypto-currencies.

As proof-of-work for new blocks of transactions,
Bitcoin~\cite{nakamoto2009bitcoin} adopted <NAME>'s hashcash~\cite{back2002} proof-of-work.
This entails finding a nonce value such that
application of a cryptographic hash function (twofold SHA256 in Bitcoin's case)
to this nonce (and the rest of the block header) results in a number with
many leading 0s. The number of leading 0s is dynamically adjusted by the protocol
so as to maintain a certain average block interval (10 minutes for Bitcoin).

Since Bitcoin, many other crypto-currencies have adopted hashcash, with various
choices of underlying hash function. the most well-known being {\em scrypt} as
used in Litecoin.

Primecoin~\cite{king2013} introduced the notion of a number-theoretic proof-of-work,
as the first alternative to hashcash among crypto-currencies.
This entails finding long chains of nearly doubled prime numbers, with a certain
relation to the block header.
{'fraction_non_alphanumeric': 0.06889304063521719, 'fraction_numerical': 0.011209715086408221, 'mean_word_length': 5.280058651026393, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5575541', 'n_tokens_mistral': 1227, 'n_tokens_neox': 1114, 'n_words': 552}