CH

June 8, 2017

An implementation of Mircea Popescu's Fabulous Hash Function

Filed under: common lisp, tmsr — Benjamin Vulpes @ 5:40 p.m.

At the beginning of March (you're stuck believing me, I keep detailed logs of this sort of thing), I wrote an implementation of Mircea Popescu's Fabulous Hash Function, in the process finding a few mistakes in his documentation.

I left off before publishing at the time, as while the individual operations worked, the assemblage together didn't return the same values I saw on Trilema. I got distracted, life moved on, and the proggy sat on my drive, further unexamined. Today, the hash function's author pointed out that he'd published results from an implementation of an older spec, Stan exhorted me to publish and reconcile, and here we are.

Updated: June 9, 2017: 4:03

'twas only my just deserts for sitting on a piece of code for months and then releasing it abruptly without loading it into my head fully: asciilifeform found the most glaringest flaw in the whole thing, that while the rest of the program operates in a destructive fashion, the invert operation returned the array that should have been emplaced into its input argument. More beatings is the only remedy...

Patch to fix follows:
In the interest of preserving my sanity, I'll not be hosting patches for this thing.


Updated: June 9, 2017: 7:24

Turns out, it doesn't work at all.


Updated: June 10, 2017: 01:05

I'm excising the old code below, and commit to maintaining an up-to-date version below. To paraphrase Mircea Popescu, it does something, although whether it does the right thing is hard to tell. Hash functions, amirite?

Please join us in #trilema on the Freenode IRC network to play with the bot. Demo session here:

http://btcbase.org/log/2017-06-10#1667948


Updated: Jun 10, 2017 01:24

Bug in the spec. Code updated. Combatants licking their wounds.


Updated: June 10, 2017 06:02
Reordered updates first to last, like a sane person.

Astonishment and awe, as the element expected to bring chaos brought instead entirely predictable order.Ambiguity in the spec this time!

And ultimately, sweet sweet synchrony.

With candidate canonical implementations in the field, it's time for another round of tests. I'll list some results here and hopefully enterprising souls will come up with some new mismatches to run down.

(mpfhf:mpfhf #*1111 4)
#*1010

(mpfhf:mpfhf #*11111111111111111111111111111111 64)
#*0110100011001111010010001111100000000001110001111000001001000001

(mpfhf:mpfhf #*1111111111111111111111111111111111111111111111111111111111111111 64)
#*0010111010001000101011101000100000110011110111011111001001110010

 (mpfhf:mpfhf #*1111111111111111111111111111111111111111111111111111111111111111 128)
#*01101000010111101000010110001100001011110000110000101110110101111010010101000000011011111010011011110001001100010111101010011100

(mpfhf:mpfhf #*11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 256)
#*1111111010101111011001101011011111101000101011111101011110010111010011100111000011000101000010111000111011110100100101010011011111010111001011011101010011011101011000100010001000111110000010010011001100011111100000100001010111101111010110000111010101011100

And, the final torture test: a 64-bit MPFHF of the text document found here: http://thebitcoin.foundation/declaration.txt

#*0000000011110000101000010101001010110110111001110111100101111000

Updated: June 30, 2017 06:02

I've squeezed the obvious gains out of the thing, but it's still clocking in at some ~4X the runtime of sina's golang implementation. I can squeeze another 25% out of it by constraining hash output sizes, but that's not actually a useful optimization.

I find myself woefully underequipped to profile this code for the hot spots. More research on benchmarking and profiling CL to follow...

Currently operational implementation:

(defpackage :mpfhf
  (:use :cl :bit-smasher)
  (:export :flip :invert :screw :expand :mpfhf :hash-string :main))
(in-package :mpfhf)

(defparameter *log-out* nil)

(declaim (inline expand flip invert underlying-screw screw half-screw rewind))

(defun flip (element target)
  (declare ((array bit 1) element)
           (fixnum target))
  (let* ((original (bit element target))
         (new (if (= 0 original) 1 0)))
    (setf (bit element target) new)
    element))

(defun invert (element)
  (declare ((array bit 1) element))
  (adjust-array
   element (array-dimensions element)
   :initial-contents (bit-not element)))

(defun underlying-screw (b m-position count)
  (declare ((array bit 1) b)
           (fixnum m-position count))
  (loop for i integer below count do
       (let* ((product (* i m-position))
              (target (rem product (length b))))
         (flip b target))))

(defun half-screw (a b m-position)
  (declare ((array bit 1) a b)
           (fixnum m-position))
  (underlying-screw b m-position (floor (/ (length a) 2))))

(defun screw (a b m-position)
  "screw a in b"
  (declare ((array bit 1) a b)
       (fixnum m-position))
  (underlying-screw b m-position (length a)))

(defun expand (element)
  (declare ((array bit 1) element))
  (let ((original-size (array-total-size element)))
    (adjust-array element (+ 1 original-size) :initial-element 0)
    element))

(defun rewind (place)
  (declare (fixnum place))
  (if (= 0 place)
      nil
      (decf place)))

(defun mpfhf (m hash-length)
  (declare ((array bit 1) m)
           (fixnum hash-length))
  (let ((s (make-array 1 :element-type 'bit :initial-element 0 :adjustable t))
        (r (make-array hash-length :element-type 'bit :initial-element 0 :adjustable t))
        (message-length (length m)))
    (loop
       for message-position fixnum = 0 then (+ 1 message-position)
       for steps fixnum = 0 then (+ 1 steps)
       until
         (>= message-position message-length)
       do
         (progn
           (case (elt m message-position)
             (0
              (expand s)
              (screw s r message-position)
              (case (elt r (rem message-position hash-length))
                (0 (flip r (rem message-position hash-length))
                   (if (= 0 message-position) nil (decf message-position)))
                (t (flip r (rem message-position hash-length))
                   (invert s))))
             (1
              (half-screw s r message-position)
              (let ((idx-a (rem message-position hash-length))
                    (idx-b (rem message-position (array-total-size s))))
                (cond
                  ((= (the bit (elt r idx-a))
                      (the bit (elt s idx-b)))
                   (expand s)
                   (screw r s message-position))
                  (t
                   (flip r (rem message-position hash-length)))))))))
    (values r *log-out*)))

(defun hash-string (message length)
  (declare (simple-string message)
           (fixnum length))
  (let* ((bits (loop for c character across message appending
                    (coerce (bit-smasher:bits<- (char-code c)) 'list)))
         (bit-message (make-array (* 8 (length message))
                                  :element-type 'bit
                                  :initial-contents bits)))
    (mpfhf bit-message length)))

(defun main ()
  (let ((message (second sb-ext:*posix-argv*))
        (length (parse-integer (third sb-ext:*posix-argv*))))
    (format t "~A~%" (hash-string message length))))

Not shown above, the MPFHF returning a log stream (and the log lines, for sanity's sake) so that the bot can slam it into my pastulator. As of this update, the logs are so verbose that the pastulator won't eat them for larger hashes, and my MPFHF implementation consumes absurd amounts of memory when logging.

The test cases are from the Trilema article linked above, and as they are notionally from runs of an implementation of a different spec, none match.

Reconciliation notes, bug reports, portability mistake reports, and any other sort of suggestions welcome.

January 8, 2017

CORRECTION: multiple channel patches for irc/logbot

Filed under: V, common lisp, tmsr, version control — Benjamin Vulpes @ 9:58 a.m.

I discovered earlier this evening that I mis-ground the patches adding multiple-channel support to trinque's ircbot/logbot systems. Details here.

Attached find corrected versions of both of these patches.

ircbot-multiple-channels-corrected.vpatch
ircbot-multiple-channels-corrected.vpatch.ben_vulpes

logbot-multiple-channels-corrected.vpatch
logbot-multiple-channels-correctedvpatchben_vulpes

My apologies.

January 4, 2017

How to (actually) "learn programming"

Filed under: bitcoin, software development, tmsr — Benjamin Vulpes @ 3:03 a.m.

More or less the same way you learn any other very complicated craft with oodles of knowledge both formalized and oral: by finding the most strict and knowledgeable master you can, and slaving for him as best you can for as long as you can tolerate it. Proper apprenticeships are an unlikely model in the States, as everyone with 9 months of React under their belt expects 140KUSD per annum and a title, but you wanted to know how to actually learn programming.

Most masters that you'll find in the wild world of shartups are neither particularly masterful nor particularly willing to entertain your novicehood. This manifests in "industry" (to the extent that building javascript webapps might be called industry) as "software engineers" (lacking the "senior" honorific) train "junior software engineers" inserted into their organization by the Diversity Machine. This is not the sort of master you'll learn much useful from, regardless of what you think of the type of master you'd like to learn from.

Since you'll not find anyone to beat 40 years of slapdash hacks into your head on the shartup circuit, you're stuck learning from the cruel, busy, cryptic and reluctant peers of The Republic, who won't be particularly useful on the curricula front.

Reading:

- Applied Cryptography, Bruce Schneier (first edition)
Read the first edition, with the red BLUE (Red is the bullshit version. Kudos to mod6 for the catch.) cover. Schneier redacted all of the actual goodies so that he might land a job with people who find that kind of behavior appealing and not appalling.

- Common Lisp the Language, 2nd Edition, Guy Steele
The peers have largely settled on Common Lisp as a programming lingua franca. It's an entirely adequate language, featuring ~everything you'll find in "modern" programming languages like PHP or Python. While I'm not convinced that one can "learn programming" in any other way than by building things and practicing constantly and with a relentless eye towards self improvement, reading this book won't hurt you (too much).

Exercises:

- generate and secure GPG keys

This is the single most important task for anyone who intends to join The Republic. You must learn what it means to generate keys securely, how to use them securely, enumerate the kinds of threat you wish to secure your keys against, and then effect a system that tends to all of these needs.

You also must establish and practice your backup and restoration process for these keys. Everything dies, including computer hardware, so you must ensure that you do not fail to maintain access to the anchor to reality and key to the door of The Republic's forum.

- set up and operate a virtual server

While I cannot recommend that you make a permanent home in a virtualized server on someone else's hardware, you need a persistent Linux box that can do...things. It more or less doesn't matter which Linux you settle on if you're reading this for advice, but you should operate under the assumptions that a) you'll be relegating the machine to the dustbin at some point and b) you'll probably want to change Linux distributions as well.

- set up an IRC bouncer

If you have the remotest dream of anyone in The Most Serene Republic of Bitcoin giving a shit about you and your problems, you'll quickly discover the importance of maintaining your own connection to the forum and not annoying the peers by reconnecting constantly. Establishing and maintaining a persistent and robust IRC connection will teach you much about the Linux and IRC client you've chosen to operate.

- set up a blog

Recount your travails in "learning programming". Muse in public. Offer your thoughts that others may know them and contradict you. This is as close as you'll get to "having a master", so have opinions, be ready to defend them, and prepare to accept that you're wrong. Don't neglect your comment system and for the love of all that is holy don't outsource it.

- operate a server

There are many ways to get into operating your own hardware, and many tradeoffs to make in the hardware procurement project. Migrating from virtualized servers to your own metal in a datacenter somewhere will illuminate all sorts of dusty corners in your head where the advocates of feeding the world with McDonald's hide the assumptions they programmed you with as a child. This project will acquaint you with the engineering tradeoffs with which programmering as a career is rife.

- run a "The Real Bitcoin" node

Once you've grown into your own hardware and have at least 5GB of RAM and 200GB of disk to spare, consider operating a TRB node. TRB is downright finicky in constrained and virtualized environments, and you're on a course to digital literacy and self-sufficiency.

Projects:

- extend Diana Coman's "foxybot", a bot for Mircea Popescu's MMORPG Eulora

MP runs an MMORPG and encourages players to automate their activities in it. Diana Coman, the current project lead/developer (do forgive the possibly-insulting title) maintains and extends both the game's codebase and that of it's dominant bot "foxybot". The link to foxybot above has a list of features the playerbase would like to see implemented.

Working in this environment will teach you about the wonders of C++ and Crystalspace; a programming language with which one must be conversant but that is not particularly...good, and a "game development engine" that isn't as loathsome as other engines respectively.

- (re)implement V

V is a hard crypto source distribution tool. Reimplementing a working V will demonstrate that you understand a foundational building block of our world.

- make a Lamport Parachute

Stan says it all, go read it.

- operate an IRC bot

trinque and I (but mostly trinque) have put some work into a Common Lisp IRC bot. Stand one up and keep it up.

- build and host a log viewer

If you're already operating an IRC bot (and when we've made it so easy for you to do so, not doing so begins to look a bit lazy), you may contribute to The Republic's own form of distributed redundancy: many different implementations of core functionality -- in this case, log viewers. Public logs civilize the chaos and noise of IRC, and cross-referencing upgrades logs to Talmudic stature. phf hosts the canonical logs at http://btcbase.org/log , I host a set at http://bvulpes.com/logs , and Framedragger hosts a set at http://log.mkj.lt/trilema/today .

This project will acquaint you with the miseries of building wwwtronic software. Implementing search and cross-referencing will teach you even more.

Coda

There is no point to "learn programming" if you're just going to further the works of evil by battling for the empire's hegemony with JavaScript and "mobile apps". If all you desire is a good job and enough money to pay for beer, food, and box for your meat so that you may attract a girl in her late thirties who's looking to settle, go sign up for your local code school, capitalize on their placement program, and settle down to devour your brain elsewhere. The Republic will continue to fight without you, ensuring access to strong cryptography (see: FUCKGOATS, the only high-grade entropy source on the market in the whole world), and a Bitcoin implementation that keeps pestilential currency-fascists and -devaluators at bay.

The reading section is currently woefully incomplete, indicative of both the reading I've done in the field and what I consider the utility of various "programming books". Suggestions welcome.

December 22, 2016

veh.lisp genesis.vpatch

Filed under: bitcoin, software development, tmsr — Benjamin Vulpes @ 11:06 p.m.

At phf's prodding, I present in this post a genesis vpatch and corresponding signature for my Common Lisp implementation of asciilifeform's V. In case you've forgotten, V is a hard-crypto software source distribution tool that gives The Republic delightfully hard guarantees about who has endorsed what changes to a software project. Details are here: V-tronics 101.

It is useful for code-savvy folks in The Republic to reimplement basic tools like this. Multiple implementations of an ambiguous specification provide far more value than the "many eyes" mantra of open source advocates. For example, an implementation in Python might burn the eyes of a Perl hacker, and the Perl be entirely inscrutable to a man who's never touched it before, and even were such a man to sit down and learn Python for the purpose of auditing another's V implementation, it is in no way obvious that the time cost of his learning the language combined with the risk that he misses details in the audit is a better resource expenditure than simply implementing the tool again in his language of choice. Multiple implementations provide the Republic defense in depth, in stark contrast to the Silicon Valley software monocultures, and demonstrate to the Peers that the authors understand the goals and subtleties of the project in question.

phf did not just prod me to post my implementation, however. The charges are serious, so allow me to quote in full:

phf: ben_vulpes: this subthread since your response to my original statement is one example of what i'm talking about. in this case none of the v implementations are on btcbase, because nobody wants to sign own hacks, because the cost of failure is too high.

For an example of just how this notion that "the cost of failure is too high" came to be:

mircea_popescu: to put it in you'll have to sign it. if it turns out later to have a hole, people will negrate you.

To contextualize phf's comment properly: the man set up a spiffy loggotron (the one I cite here constantly, actually) and then hared off to the desert for a few weeks without ironing some stability issues out first, which left us without logs for a bothersome amount of time. While kicking a process over may be acceptable (in some contexts, on the deficit budget the Republic operates), that style of process monitoring and uptime insurance only works if someone is available to restart the process in question whenever it goes down. Which it wasn't, and for which he was roundly scolded upon his return.

So yes, the reputational costs of operating critical infrastructure (in phf's case, the canonical log of the Forum's dealings) for The Republic and then letting that infrastructure fail is rather steep. Note, however, that he has since ironed the stability issues out and the whole episode largely left behind. No negative ratings were issued as a result, that's for damn sure.

The brouhaha that kicked off my rewrite of my V implementation is barely worth going into1 but for four details: the discovered bug was not a hole, but required that an operator attempt an action actively harmful to their own health; the implementation's author fixed the problem in short order; was already a member in good standing of the #trilema Web of Trust; and the issue was discovered by members of the Republic and not leveraged into an attack.

Much of the Republic's otherwise incomprehensible-to-outsiders behavior may be chalked up to precisely this sort of "trust building exercise", and there is no way to build a nation of men but this way. A strong reputation buttresses a sapper against charges of treason, leaving space for the WoT to entertain the notion that the sapper is not treasonous but has merely made a mistake. Moreover, fear of failure's repercussions must always be evaluated and mitigated in the same way that one performs security analyses: "What are the downsides here? How might these changes fuck my wotmates? How pissed could they reasonably get at me for hosing them thusly? How would I respond to allegations of treason?" Not that anyone's on the stand for such, but one must entertain the gedankenexperiment.

So, in the spirit of:

phf: but the reason i made those statements yesterday is because i think that like saying things in log is an opportunity to be corrected, so does posting a vpatch, it could be a learning experience. instead the mindset seems to be http://btcbase.org/log/2016-02-20#1411214
a111: Logged on 2016-02-20 22:45 phf: "i, ordained computron mircea lifeform, in the year of our republic 1932, having devoted three months to the verification of checksums, with my heart pure and my press clean, sit down to transcribe vee patch ascii_limits_hack, signed by the illustrious asciilifeform, mircea_popescu, ben_vulpes and all saints."

I am proud to publish a genesis vpatch for my own V implementation in Common Lisp. It is a "harem-v" (which is to say a V implementation that this individual uses in the privacy of his own workshop, and may not suit your needs or even desires), but I daresay that it is correct in the important places. Even if it is wildly incorrect in those important places, it demonstrates quite completely that The Republic outperforms classic "open source" communities by reproducing and spot-checking each other's work instead of pretending to read it and only ever actually grepping for hateful words in order to be a most respectably-woke Github contributor. I also offer it in the spirit of the above log line: to seek correction and feedback on best practices from peers more competent with the parens than myself.

genesis.vpatch
genesis.vpatch.sig

Updated 12/27/2016 with hashes_and_errors.vpatch

hashes_and_errors.vpatch
hashes_and_errors.vpatch.ben_vulpes.sig

One simplification from v.pl and v.py that I made in this implementation is that I iterate naïvely through all of the signatures (until one is found that verifies) when confirming that a patch has a signature from wot-members, rather than sorting the list of patches and signatures and making assumptions about patch/signature naming. This slows `press' operations down significantly, but `flow' calculations complete nearly instantly.

Enjoy! If you find anything heinously wrong, do let me know. I shan't be falling on my sword over it, but I will fix it if you can show me that it is in fact broken.

Updated 01/04/2017 with 2017_cleanup.vpatch

2017_cleanup.vpatch
2017_cleanup.vpatch.ben_vulpes.sig

  1. tl;dr: a V implementation was willing to press to heads for which it had no signatures. Its author has since remedied that. []

November 17, 2016

[ANN] a mailhole

Filed under: projects, tmsr — Benjamin Vulpes @ 2:04 a.m.

For the glory of The Republic, I present an implementation of Mircea Popescu's idea, a mailhole1 .

It's pretty simple, there's not much too it. Anyone may send email to any address @ bvulpes.com. Email to foo@bvulpes.com will show up at m.bvulpes.com/foo@bvulpes.com.

Caveats:
- mail older than 30 days is purged weekly
- only the first "message part" and the first header is shown
- email sucks, and is a miserable dinosaur of a comms medium. gossipd whennnnn

If your emails don't show up, drop by #trilema and bug me there.

  1. Incidentally, this makes a data point as well: time from "hey this would be neat" to "deployed wwwtronix" in just under a month. For context, 90% of the work was in reading through the dbmail DB definitions and thinking for more than five minutes about what parts of the messages to show. Long story short, the classic email implementation of attachments is total garbage, and when gossipd ever gets an implementation the whole shebang will be eaten along DNS and the rest of the star topology. []
Older Posts »

---