Re: [cryptography] a new blockchain POW proposal

[travis+ml-rbcryptography]

On Sun, Jan 17, 2016 at 11:49:20PM -0800, 
travis+ml-rbcryptogra...@subspacefield.org wrote:
> On Sun, Jan 17, 2016 at 08:31:44PM -, John Levine wrote:
> > >1) Can we use SAT (or another NPC problem) as a POW?
> > 
> > Meybe.  Remember that a POW has to be hard to compute but easy
> > to verify and each instance should be roughly the same difficulty.
> > My impression is that some SAT problems are a lot harder than others,
> > and you can't tell in advance which is which.
> 
> IIUC, making sure the first N bits of a hash are zero, is basically
> the SAT problem (make these equations equal one), with random
> equations/functions ("random oracle model" of ideal hashes).
> 
> A SAT solution would provide input variables that made all the
> equations 1 (or equivalently, zero) and should probably be much
> more efficient than computing a hash, although perhaps the general
> solution is not as efficient as the specific form solution defined
> by a given hash.

On the solution side, you could take the ordinal number in this set
size, and use it to generate the coefficients in the maximal
conjunctive normal form; for each input variable apearance, it might
be (+) present, (-) inverted, or (0) absent from that spot.

Assuming the maximal conjunctive normal form is:
y_n = (c_n1 x1 v c_n2 x2) ^ (c_n3 x1 v c_n4 x2)

Then for c_1 = { 1 -1 0 1 }
y1 = (x1 v -x2) ^ (x2)

Actually, that's not fully general, as it fails to give enough
opporunities for variables and their negations to play in every
possible way; it would, for example, make it impossible to
represent y = (x1) ^ (-x1 v -x2) ^ (x2) ^ (-x1 v x2)

I'm pretty sure there's some fancy work you could do to get this all
straightened out and make it such that a certain size bitstring
enumerates all possible NPC SAT problems in a certain number of
variables, possibly by treating a variable and its negation as two
input variables, for the purposes of generating equations, and
supressing them with zero coefficients.

In this case, the block chain simply iterates that bitstring
(representing vector c), lets people submit a solution, and then
iterates again, until it rolls over.

The brute force miners could continue to iterate solutions the way
they still have; by trying all possible input bits drawn by random
selection - and see if the equations evaluate to true.  Anyone who
wants to check their work, takes their vector for x and plugs them in
with vector c to evaluate y.  If y comes up all 1s, it's legit.
These guys set the ceiling of how much work it should take.

The SAT solving miners, might see some pattern in c that allows them
to compute the answer quicker.  Bully for them.

Other miners might use humans a la the Verigames game Paradox:
http://paradox.centerforgamescience.org/paradox/Paradox.html
-- 
http://www.subspacefield.org/~travis/ | if spammer then j...@subspacefield.org
"Computer crime, the glamor crime of the 1970s, will become in the
1980s one of the greatest sources of preventable business loss."
John M. Carroll, "Computer Security", first edition cover flap, 1977
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] a new blockchain POW proposal

[Tony Arcieri]

On Sun, Jan 17, 2016 at 2:13 AM,  wrote:

> 4) Would it be useful to decouple any of the aspects of the block
> chain from each other?


Right now Bitcoin's transaction throughput is inherently capped by the
combination of how many transactions fit in a block and how frequently new
blocks are published (hence the "Bitcoin XT" debacle).

The proof-of-work function provides what's effectively a Sybilproof leader
election system. I thought a clever idea was to decouple leader election
from authenticating transactions:

http://arxiv.org/abs/1510.02037

(This specific approach has flaws, but I'd like to see the general idea
better explored)

-- 
Tony Arcieri
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] gfverif, djb's ECC bugfinder

[travis+ml-rbcryptography]

http://gfverif.cryptojedi.org/

(Humorous logo of Evariste Galois and a checkmark elided)

Cryptographic software needs to be correct: even a tiny bug can have
disastrous consequences for security, as illustrated by Brumley,
Barbosa, Page, and Vercauteren exploiting an ECDH carry bug in OpenSSL
0.9.8g. Standard software-testing techniques catch many bugs but did
not prevent, e.g., further OpenSSL carry bugs announced in January
2015 (initial analysis: too expensive to exploit) and December 2015
(initial analysis: exploitable by well-equipped attackers).

The goal of gfverif is to integrate highly automated proofs of
correctness into the ECC software-development process. These proofs
can be compromised by bugs in gfverif, but eliminating those bugs is a
relatively small one-time task. Correct proofs will eliminate all ECC
software bugs, including the low-probability carry bugs that slip past
testing. Of course, bug-free software can be compromised by hardware
bugs and compiler bugs, but separate projects are underway to
eliminate those bugs.

...

We have proven the correctness of a reference implementation of X25519
elliptic-curve scalar multiplication. The implementation is, except
for a few minor tweaks, the preexisting "ref10" implementation in
C. Correctness means that, under plausible assumptions regarding the
behavior of the C compiler, the implementation computes exactly the
function specified by a concise high-level description of X25519.

...

gfverif focuses on finite-field computations. This is slightly broader
than ECC (for example, it can handle HECC and can probably handle
NTRU) but it isn't all of core crypto. On the other hand, it's a
significant chunk of core crypto.

etc.
-- 
http://www.subspacefield.org/~travis/ | if spammer then j...@subspacefield.org
"Computer crime, the glamor crime of the 1970s, will become in the
1980s one of the greatest sources of preventable business loss."
John M. Carroll, "Computer Security", first edition cover flap, 1977
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] a user's request for usable storage crypto

[travis+ml-rbcryptography]

https://www.corelan.be/index.php/2016/01/06/crypto-in-the-box-stone-age-edition/
-- 
http://www.subspacefield.org/~travis/ | if spammer then j...@subspacefield.org
"Computer crime, the glamor crime of the 1970s, will become in the
1980s one of the greatest sources of preventable business loss."
John M. Carroll, "Computer Security", first edition cover flap, 1977
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography