Bitcoin Forum
January 25, 2021, 07:07:18 AM *
News: Latest Bitcoin Core release: 0.21.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1] 2 »
1  Alternate cryptocurrencies / Altcoin Discussion / do any coins rival Grin's simplicity? on: January 16, 2021, 02:50:20 PM
Simplest possible consensus model: Proof of Work. Grin uses Nakamoto consensus just like Bitcoin.

Simplest possible emission: 1 grin per second forever. Grin uses Tail Emission from launch, the complete opposite of Bitcoin's Capped Supply. The latter is known to suffer from insecurity and mining instability once the block subsidy becomes insignificant, unless a constant backlog of high fee paying transactions can be created (which Bitcoin seems to manage with its constrained block size). Emission properties are further explored in [1a] and [1b].

Simplest possible blockchain protocol: Pure Mimblewimble. In Mimblewimble, outputs are Pedersen commitments r*G+v*H which combine value and blinding factor into a single curve point. The blinding factor serves both to hide the value and to control ownership. Correspondingly, a single (multi-)signature serves both to prove value balance (non-inflation) and to authorize transfer of ownership. The magic doesn't stop there, as transaction cut-through results in the collapse of the entire transaction history into a single transaction with no inputs and the current UTXO set as outputs [2].

Simplest possible blockchain sync: verify UTXO set. Grin still verifies transaction history by means of a ~100 byte kernel that remains for every transaction, but doesn't need to know anything about spent outputs.

Simplest possible (memory hard) Proof of Work Algorithm: Cuckatoo Cycle. Its mathematical specification is only 13 lines [3a] based on the very simple siphash-2-4 hash function. Which translates to just 42 lines of C code [3b]. Like Bitcoin, solutions can be instantly verified, but unlike Bitcoin, a single solution attempt (searching a graph) takes on the order of a second.

Simplest possible Difficulty Adjustment Algorithm: wtema. Just one line of code [4] that outperforms many other DAAs [5].

Simplest possible scripting functionality: scriptless scripts. Grin does away with Bitcoin's script and all its complexity, but retains a lot of its functionality, including multi-signatures, and both absolute and relative timelocks. It easily supports atomic swaps, discreet log contracts, and bidirectional payment channels. It lacks hash locks, but finds a superior alternative in adaptor signatures

The simplicity is reflected in the relatively small Rust codebase of the reference implementation [6] and the alternative C++ implementation [7].

[1a] https://john-tromp.medium.com/a-case-for-using-soft-total-supply-1169a188d153

[1b] https://medium.com/@CryptoProfG/grin-money-explained-4-exploring-grins-monetary-model-e48b1761653

[2] https://phyro.github.io/what-is-grin/mimblewimble.html

[3a] https://github.com/tromp/cuckoo/blob/master/doc/mathspec

[3b] https://github.com/tromp/cuckoo/blob/master/doc/spec

[4] https://github.com/mimblewimble/grin/blob/master/core/src/consensus.rs#L371-L372

[5] https://read.cash/@jtoomim/bch-upgrade-proposal-use-asert-as-the-new-daa-1d875696

[6] https://github.com/mimblewimble/grin

[7] https://github.com/GrinPlusPlus/GrinPlusPlus
2  Alternate cryptocurrencies / Altcoin Discussion / Pure Linear Emission / Constant Reward on: December 14, 2020, 11:11:12 AM
Which blockchains feature a pure linear emission, i.e. a constant block reward?

3  Bitcoin / Development & Technical Discussion / Musings on Proof of Disk Space on: September 30, 2019, 02:00:05 PM
I'd like to explore some simple-minded proof of disk space (PoD) design based on
the idea of separate PoD and tx chains, a characteristic shared by Burst and Chia.
I want to keep things as simple as possible. In particular,
- no proof of time
- no need to process more than a few disk blocks per second

The PoD chain will be as deterministic as possible, to prevent the possibility
of grinding attacks. It will not commit to any transaction data.
Each PoD block will just have the following fields
- height
- previous block hash
- timestamp
- farmer public key
- PoW solution.

A PoD block is valid if its timestamp is larger than the previous block's, and

    hash(prePoW) <= hash(PoW solution) < hash(prePoW) + 1 / difficulty

where prePoW consists of all fields apart from the PoW solution, and hashes are
interpreted as fractions in [0,1). The underlying PoW can be anything, either
hashcash or some memory hard asymmetric PoW with instant verification. We need
each PoW instance to commit to the farmer public key though, so that no
grinding is possible over the public key. Valid PoD blocks with timestamps in
the future are not considered until the local time catches up.

The separate tx chain will have blocks of tx data, each of which links to a
same-height PoD block and is signed with the public key in the latter.

The farming process
=============
I.e. how to extend the PoD chain.

Each farmer computes prePow hashes at increasingly larger timestamps and
looks for a close enough stored PoW solution hash on its hard disk.
On success, it regenerates the PoW instance and solves it to complete the new PoD block.

Storage of PoW hashes
===============

Let a PoW record be a pair (index, hash) where the 64-bit index allows us to
reconstruct the PoW instance, and hash is the most significant 64-bits of the
hash of the PoW solution.

A typical 4TB hard disk costs $100. Let's use up to $100 worth of leased mining
hardware and electricity to fill the disk with bucket sorted 12-byte PoW
records, where the most significant 32 bits of hash are used as bucket
selector.  Each of the 2^32 buckets will have on average 4*10^12/2^32/12 ~ 78
hash-sorted records, taking up under 1KB, or 2 512-byte disk blocks.

Work per PoW record
==============

If we optimistically assume that electricity costs $0.04 per KWh and that we
spend $10 on electricity, then that gives us (10 / 0.04) * 3600J = 0.9 MJ of energy.
Dividing that over the 10^12/3 PoW records gives 2.7 uJ (microJoule) per PoW
solution.  With memory access costs measured in picoJoules per bit, that could
involve on the order of a million bit accesses.

PoW solution rate
============

If we want to fill the disk in about one month, or 30 days, than the mining
hardware will use 250KWh / (30*24h) ~ 350W, and will need to produce 10^12/3 /
(30*24*3600) = 128600 solutions per second.

PoD as PoW amplification
================

Although this scheme aims to substitute disk space for work, it still involves a
large amount of work in filling the disk. This is mostly due to PoW records
being so compact. One would like to force them to take more space, but I do
not see any way to do so. Perhaps this is the real reason that Chia needs
to use proof of time.
This scheme can also be seen as a PoW amplifier. A 30 day run of a mining rig
is captured on disk so that it can be re-used for many years.

Questions
=========

- Is there some big error in my calculations?
- Or in the logic of this scheme?
- Is there anything left to grind?
- Is anything to be gained by not storing PoW records?
- Is anything to be gained by storing PoW records differently?
- Can we force larger PoW records?
- Is the assumed mining hardware within the realm of feasibility?
- Will the hard disk manufacturer have to prepare disks, presumably in a place with very cheap electricity?

-John
4  Alternate cryptocurrencies / Mining (Altcoins) / New Cuckoo Cycle GPU solver available. Bounties included... on: January 30, 2018, 10:11:06 PM
See report at https://github.com/tromp/cuckoo/blob/master/GPU.md
5  Alternate cryptocurrencies / Marketplace (Altcoins) / Cuckoo Cycle proof-of-work: $15000 in bounties on: March 03, 2017, 09:41:35 PM
Cuckoo Cycle is an instantly verifiable memory bound Proof-of-Work,
whose run time is dominated by memory latency.

I invite anyone to try claim one of the following bounties
(backed by the Cuckoo Cycle Bounty Fund)
for improving my C++/CUDA solvers:

performance improvement   4x           2x           sqrt(2)x
CPU                                    $6000     $3000     $1500
TMTO                                  $6000     $3000     $1500
GPU                                    $3000     $1500     $ 750

Details at

https://github.com/tromp/cuckoo

Happy bounty hunting...
6  Bitcoin / Development & Technical Discussion / Cuckoo Cycle proof-of-work: $5000 in bounties on: November 09, 2016, 08:52:37 PM
Cuckoo Cycle is an instantly verifiable memory bound Proof-of-Work,
whose run time is dominated by memory latency.

I invite anyone to try claim one of the following bounties for performance doubling
of my C++/CUDA solvers:

CPU   $2000
TMTO $2000
GPU   $1000

or half the above bounties for a sqrt(2) performance improvement. Details at

https://github.com/tromp/cuckoo

Happy bounty hunting...
7  Alternate cryptocurrencies / Marketplace (Altcoins) / Cuckoo Cycle proof-of-work: $5000 in bounties on: November 07, 2016, 10:18:03 PM
Cuckoo Cycle is an instantly verifiable memory bound Proof-of-Work,
whose runtime is dominated by memory latency.

I invite anyone to try claim one of the following bounties for performance doubling:

CPU   $2000
TMTO $2000
GPU   $1000

or half the above bounties for a sqrt(2) performance improvement. Details at

https://github.com/tromp/cuckoo

Happy bounty hunting.
8  Alternate cryptocurrencies / Altcoin Discussion / Making PoW useful on: July 30, 2016, 03:00:10 AM
Global bitcoin mining power consumes hundreds of megawatts, which many people have characterized
as a colossal waste. Meanwhile, datacenters worldwide consume thousands of megawatts,
an estimated 25-40% of which is spent on DRAM memory. Quoting from
Rethinking DRAM design and organization for energy-constrained multi-cores[1],
modern DRAM architectures are ill-suited for energy-efficient operation because
they are designed to fetch much more data than required, having long been optimized for cost-per-bit
rather than energy efficiency.
Thus there is enormous energy savings potential in accelerating the development of more efficient
DRAM designs. While this paper and others like The Dynamic Granularity Memory System[2]
have proposed several sensible and promising design improvements, memory manufacturers have
taken a wait-and-see approach, likely due to the need for more advanced memory controllers, which they don't develop
themselves, and uncertainty about market demand. However, a widely adopted PoW whose very bottleneck
is purely random accesses to billions of individual bits would provide such demand.
The world has little need for the extremely specialized SHA256 computation being efficient.
But it stands to benefit a lot from more energy efficient random access memories (that, unlike SRAM, also
remain very cost efficient).

[1] https://www.cs.utah.edu/~rajeev/pubs/isca10.pdf
[2] http://mbsullivan.info/attachments/papers/yoon2012dgms.pdf
9  Alternate cryptocurrencies / Altcoin Discussion / LEGO coin on: March 07, 2016, 09:49:36 PM
LEGO coin may not exist yet, but it's destined to use PoW on its blocks:

http://technabob.com/blog/2016/03/07/lego-mario-pow-block/
10  Alternate cryptocurrencies / Mining (Altcoins) / 50 days left to claim 3x$500 in bounties for Cuckoo Cycle proof-of-work on: November 11, 2015, 10:52:15 PM
(erroneously posted to Marketplace yesterday)

Since mid-2014,
  https://github.com/tromp/cuckoo
has offered bounties for disproving that Cuckoo Cycle,
myProof-of-Work that spends most time on memory latency,
- has an optimal reference miner
- has no feasible memory-time trade-off
- offers no advantage for GPUs

These bounties are set to expire at the end of this year,
so get coding for a modest Xmas bonus!
11  Alternate cryptocurrencies / Marketplace (Altcoins) / 50 days left to claim 3x$500 in bounties for Cuckoo Cycle proof-of-work on: November 11, 2015, 02:55:31 AM
Since mid-2014,
  https://github.com/tromp/cuckoo
has offered bounties for disproving that Cuckoo Cycle,
my Proof-of-Work that spends most time on memory latency,
- has an optimal reference miner
- has no feasible memory-time trade-off
- offers no advantage for GPUs

These bounties are set to expire at the end of this year,
so get coding for a modest Xmas bonus!
12  Bitcoin / Development & Technical Discussion / Cuckoo Cycle revisited on: July 30, 2014, 03:29:01 PM
This is about the graph theoretic proof-of-work algorithm that I originally proposed in January and which is still not in use in any crypto-currency. Please see

https://bitcointalk.org/index.php?topic=707879.0

for an introduction to Cuckoo Cycle and the bounties I am offering to support its claims of optimality, memory-hardness, and GPU resistance.
13  Alternate cryptocurrencies / Altcoin Discussion / Cuckoo Cycle Speed Challenge; $2500 in bounties on: July 24, 2014, 03:49:32 AM
Cuckoo Cycle is the first graph-theoretic proof-of-work.

Proofs take the form of a length 42-cycle in a bipartite graph
with N nodes and N/2 edges, with N scalable from millions to billions and beyond.
This makes verification trivial: compute the 42*2 edge endpoints
with one initialising sha256 and 84 siphash24 computations, check that
each endpoint occurs twice, and that you come back to the
starting point only after traversing 42 edges.
A final sha256 can check whether the 42-cycle meets a difficulty target.

With siphash24 being a very lightweight hash function, this makes for
practically instant verification.

This is implemented in just 157 lines of C code (files cuckoo.h and cuckoo.c) at
https://github.com/tromp/cuckoo, where you can also find a whitepaper.

From this point of view, Cuckoo Cycle is a rather simple PoW.

Finding a 42-cycle, on the other hand, is far from trivial,
requiring considerable resources, and some luck
(for a given header, the odds of its graph having a 42-cycle are about 2.5%).

The algorithm implemented in cuckoo_miner.h runs in time linear in N.
(Note that running in sub-linear time is out of the question, as you could
only compute a fraction of all edges, and the odds of all 42 edges of a cycle
occurring in this fraction are astronomically small).
Memory-wise, it uses N/2 bits to maintain a subset of all edges (potential cycle edges)
and N additional bits (or N/2^k bits with corresponding slowdown)
to trim the subset in a series of edge trimming rounds.
Once the subset is small enough, an algorithm inspired by Cuckoo Hashing
is used to recognise all cycles, and recover those of the right length.

I'd like to claim that this implementation is a reasonably optimal Cuckoo miner,
and that trading off memory for running time, as implemented in tomato_miner.h,
incurs at least one order of magnitude extra slowdown.
I'd further like to claim that GPUs cannot achieve speed parity with server CPUs.

To that end, I offer the following bounties:

Speedup Bounty:

$500 for an open source implementation that finds 42-cycles twice as fast (disregarding memory use).

Linear Time-Memory Trade-Off Bounty:

$500 for an open source implementation that uses at most N/k bits while running up to 15*k times slower, for any k>=2.

Both of these bounties require N ranging over {2^28,2^30,2^32} and #threads ranging over {1,2,4,8},
and further assume a high-end Intel Core i7 or Xeon and recent gcc compiler with regular flags as in my Makefile.

GPU Speed Parity Bounty:

$1000 for an open source implementation for an AMD R9 280X or nVidia GeForce GTX 770 (or similar high-end GPU)
that is as fast as a high-end Intel Xeon running 16 threads. Again with N ranging over {2^28,2^30,2^32}.

Note that there is already a cuda_miner.cu, my attempted port of the edge trimming part
of cuckoo_miner.c to CUDA, but while it seems to run ok for medium graph sizes,
it crashes my computer at larger sizes, and I haven't had the chance to debug the issue yet
(I prefer to let my computer work on solving 8x8 connect-4:-)
Anyway, this could make a good starting point.

These bounties are to expire at the end of this year. They are admittedly modest in size, but then
claiming them might only require one or two insightful tweaks to my existing implementations.

I invite anyone who'd like to see my claims refuted to extend any of these bounties
with amounts of your crypto-currency of choice.

(I don't have any crypto-currencies to offer myself, but if need be, I might be able to convert
a bounty through a trusted 3rd party)

Happy bounty hunting!

-John
14  Alternate cryptocurrencies / Altcoin Discussion / THIS IS A BLOCKCHAIN --- all posts must be linked by proof-of-work on: April 12, 2014, 05:56:47 AM
Please have a look!

I'd like to start a little experiment with a blockchain of posts, embedded right into this forum.

Each successive post must start by quoting the last line of the previous post, and end with a proof of work based off that post.
Specifically, it must be a cuckoo32 proof for a header consisting of the quote tag followed by the author name, followed by any nonce.
To generate the last line of this post, I ran

Code:
> git clone git://github.com/tromp/cuckoo.git
> make cuckoo32
> HEADER="[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766]"
> for i in {0..99}; do ./cuckoo32 -t 4 -h "$HEADER tromp $i"; done

and waited for a 42-cycle to be found. Since the probability of a 42-cycle is about 2.2%, it should take on average 45 runs to find one.

Curiously, I found one after *exactly* 45 tries, as you can see in the transcript at the bottom, which ends this post with the required proof.
As there was no previous post in this thread, I instead quoted my original announcement of Cuckoo Cycle from Jan 8.

cuckoo32 requires 768MB of memory. You can reduce this to 512MB by running cuckoo32.1 which will take about 50% longer,
or to 384MB by running cuckoo32.2, which is much slower still. The load shows how densely loaded the hash table datastructure
will be that's used in the final phase to actually find the cycles.
This has to drop below 100% for the hash table to work (it actually requires load <90%).

The proof can be verified with
Code:
> make verify32
> ./verify32 -h "[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45"

and feeding the solution line on standard input. This should output:

Code:
Verifying size 42 proof for cuckoo32("[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45") with 50% edges
Solution 91353d 7044ed7 eab3c18 11cc7bd5 11dbab29 155aeb72 171fafe9 18423605 1d18e11b 1f498480 209c0518 242e865a 2dda66a3 312e6228 31dbee8c 3585254e 35dc6d39 3f2eaa8b 40a25d6c 43d2b2ab 464b2c17 48ea7ef3 4bce1ea9 4dc4d7e6 546b3e05 55f4daa3 5937c994 66961386 675c49a8 67933a95 6b4fd632 72da1d3b 74b57814 76032cbd 774cacdd 79eb4cf1 7b20cfa7 7b8f8a15 7de1f1f1 7f6b78ef 7f7cc3ef 7fbd9ecb
Verified with cyclehash 13d4d71265d1bd8f6a75c90e5ae3759086ee3d742dd9405aac9b4519fee56db1


This post will serve as the genesis "block". Non-conforming posts risk being deleted.

Happy mining!

(I'm afraid there's no reward for "mining" new posts, just bragging right for being in a post blockchain)





...
Looking for 42-cycle on cuckoo32("[ quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45") with 50% edges, 8 trims, 3 threads
Using 256MB edge and 512MB node memory.
initial load 3200%
1 trims: load 947%
2 trims: load 373%
3 trims: load 201%
4 trims: load 126%
5 trims: load 87%
6 trims: load 63%
7 trims: load 48%
8 trims: load 38%
  16-cycle found at 2:99%
 218-cycle found at 0:99%
 452-cycle found at 1:99%
  42-cycle found at 0:99%
  80-cycle found at 1:99%
 3094-cycle found at 0:99%
Solution 91353d 7044ed7 eab3c18 11cc7bd5 11dbab29 155aeb72 171fafe9 18423605 1d18e11b 1f498480 209c0518 242e865a 2dda66a3 312e6228 31dbee8c 3585254e 35dc6d39 3f2eaa8b 40a25d6c 43d2b2ab 464b2c17 48ea7ef3 4bce1ea9 4dc4d7e6 546b3e05 55f4daa3 5937c994 66961386 675c49a8 67933a95 6b4fd632 72da1d3b 74b57814 76032cbd 774cacdd 79eb4cf1 7b20cfa7 7b8f8a15 7de1f1f1 7f6b78ef 7f7cc3ef 7fbd9ecb
15  Alternate cryptocurrencies / Altcoin Discussion / High Frequency Trading not ASIC resistant! on: April 07, 2014, 03:05:37 PM
http://www.computerworld.com.au/article/542273/asic_examines_pause_tackle_hft_report/

Sorry, I couldn't resist :-)
16  Alternate cryptocurrencies / Altcoin Discussion / how to be botnet resistant on: April 05, 2014, 03:25:09 AM
Or in other words, how to make botnet operators vastly prefer other coins over yours?
I can think of 4 ways.

1) make your coin worthless.
    duh!

2) make your pow so highly parallelizable that an average CPU is 100x slower than a GPU

3) make your pow require so much memory that it typically won't fit in memory
    (in other words, limit it to high-end desktops, servers and "big" GPUs)

4) make your pow so hard that solving a single instance on an average CPU
    takes more time than the block interval.
    (limit it to many-core CPUs and GPUs, but unlike in 2) they need only be 10x faster)

Feel free to add to the list if I missed some...

17  Alternate cryptocurrencies / Altcoin Discussion / where are the gpu-proof and botnet-resistant cpu-only coins? on: March 30, 2014, 10:46:23 PM
The beefiest GPU card only has 6GB of memory.
Your typical botnet computer has less than 4GB of free memory.

A proof-of-work that requires more than 6GB of memory is
automatically gpu-proof and botnet-resistant.

Strangely, no coin has adopted such a proof-of-work...
18  Alternate cryptocurrencies / Mining (Altcoins) / help wanted testing new proof-of-work on: February 24, 2014, 07:23:56 PM
I'm trying to determine how parallelizable my Cuckoo Cycle proof-of-work is. See this thread for details if you have access to a computer with more than 32 threads:

https://bitcointalk.org/index.php?topic=485170.0
19  Bitcoin / Development & Technical Discussion / help me measure parallellizability of new memory-hard proof-of-work scheme on: February 24, 2014, 07:16:19 PM
As developer of the Cuckoo Cycle proof of work, I'm trying to determine the maximum number of threads that can effectively work together on a single problem instance.

The largest machine I have access to has 32 threads (dual 8 core hyperthreaded) which yield a speedup of 16.7 over single-threaded runs. I'm very curious to know how many threads it takes to saturate the memory IO, so that additional threads bring no benefit.

The Makefile provided at https://github.com/tromp/cuckoo contains a basic speedup test
  make speedup.25
that only goes up to 8 threads, using 128MB instances (size 25).

If anyone has access to a Linux machine with more than 32 threads, could you please run a variation of that test with instances of size 28 (using 1GB) and as many threads as your system supports, and post a summary of your results?

For instance, if your system supports up to 60 threads, and you only want to try a subset of thread counts, you could do

for i in 1 2 8 16 32 48 52 56 60; do echo $i; cc -o cuckoo.spd -DNTHREADS=$i -DSIZEMULT=1 -DSIZESHIFT=28 cuckoo.c -O3 -std=c99 -Wall -Wno-deprecated-declarations -pthread -l crypto; time for j in {0..9}; do ./cuckoo.spd $j; done; done

Each single threaded run at size 28 takes about half a minute, so the entire test above should take under 15 minutes.

Any help is appreciated!







20  Bitcoin / Mining speculation / low-power mining on: February 07, 2014, 07:46:41 PM
Mining is generally considered to be inherently power hungry but it need not be.
Itís a consequence of making the proof of work computationally intensive.
If computation is minimized in favor of random access to gigabytes of memory
(incurring long latencies), then mining will require large investments in RAM
but relatively little power.

Bitcoin mining is all computation and no memory.

Litecoin mining requires 128KB of memory per scrypt instance but only 1024
random accesses, with negligable latency.

Primecoin mining has a sieving and a modular exponentiation component, the latter of
which is pure computation, while the former requires a few megabytes of memory
(with non-random access).

Protoshares mining with Momentum requires 512MB but performs at least one complex SHA512
computation for each memory access, with a choice of algorithms some of which avoid random access.

The memory requirements above are not absolute but allow a trade-off between time and memory.

Guess which proof-of-work system achieves the following:

1) it performs only one very cheap hash computation for several random accesses to memory,

2) its memory requirement can be set arbitrarily and doesn't allow for any time-memory trade-off.

3) verification of the proof of work is instant

Runtime is completely dominated by memory latency. It promotes the use
of commodity general-purpose hardware over custom designed single-purpose hardware,
making mining more sustainable.
Pages: [1] 2 »
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!