Bitcoin/public point to address

Bitcoin uses a specific encoding format to encode the digest of an elliptic curve public point into a short ASCII string. The purpose of this task is to perform such a conversion.

The encoding steps are:

take the X and Y coordinates of the given public point, and concatenate them in order to have a 64 byte-longed string ;
add one byte prefix equal to 4 (it is a convention for this way of encoding a public point) ;
compute the SHA-256 of this string ;
compute the RIPEMD-160 of this SHA-256 digest ;
compute the checksum of the concatenation of the version number digit (a single zero byte) and this RIPEMD-160 digest, as described in bitcoin/address validation ;
Base-58 encode (see below) the concatenation of the version number (zero in this case), the ripemd digest and the checksum

The base-58 encoding is based on an alphabet of alphanumeric characters (numbers, upper case and lower case, in that order) but without the four characters 0, O, l and I.

Here is an example public point:

X = 0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352
Y = 0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

The corresponding address should be: 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Nb. The leading '1' is not significant as 1 is zero in base-58. It is however often added to the bitcoin address for various reasons. There can actually be several of them. You can ignore this and output an address without the leading 1.

Extra credit: add a verification procedure about the public point, making sure it belongs to the secp256k1 elliptic curve

C

<lang c>#include <stdio.h>

include <string.h>
include <ctype.h>
include <openssl/sha.h>
include <openssl/ripemd.h>

define COIN_VER 0

const char *coin_err;

typedef unsigned char byte;

int is_hex(const char *s) { int i; for (i = 0; i < 64; i++) if (!isxdigit(s[i])) return 0; return 1; }

void str_to_byte(const char *src, byte *dst, int n) { while (n--) sscanf(src + n * 2, "%2hhx", dst + n); }

char* base58(byte *s, char *out) { static const char *tmpl = "123456789" "ABCDEFGHJKLMNPQRSTUVWXYZ" "abcdefghijkmnopqrstuvwxyz"; static char buf[40];

int c, i, n; if (!out) out = buf;

out[n = 34] = 0; while (n--) { for (c = i = 0; i < 25; i++) { c = c * 256 + s[i]; s[i] = c / 58; c %= 58; } out[n] = tmpl[c]; }

for (n = 0; out[n] == '1'; n++); memmove(out, out + n, 34 - n);

return out; }

char *coin_encode(const char *x, const char *y, char *out) { byte s[65]; byte rmd[5 + RIPEMD160_DIGEST_LENGTH];

if (!is_hex(x) || !(is_hex(y))) { coin_err = "bad public point string"; return 0; }

s[0] = 4; str_to_byte(x, s + 1, 32); str_to_byte(y, s + 33, 32);

rmd[0] = COIN_VER; RIPEMD160(SHA256(s, 65, 0), SHA256_DIGEST_LENGTH, rmd + 1);

memcpy(rmd + 21, SHA256(SHA256(rmd, 21, 0), SHA256_DIGEST_LENGTH, 0), 4);

return base58(rmd, out); }

int main(void) { puts(coin_encode( "50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352", "2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6", 0)); return 0; }</lang>

D

Requires the second D module from the SHA-256 task.

Translation of: C

Translation of: Go

<lang d>import std.stdio, std.algorithm, std.digest.ripemd, sha_256_2;

// A Bitcoin public point. struct PPoint { ubyte[32] x, y; }

private enum bitcoinVersion = 0; private enum RIPEMD160_digest_len = typeof("".ripemd160Of).length; private alias sha = SHA256.digest; alias Address = ubyte[1 + 4 + RIPEMD160_digest_len];

/// Returns a base 58 encoded bitcoin address corresponding to the receiver. char[] toBase58(ref Address a) pure nothrow @safe {

   static immutable symbols = "123456789" ~
                              "ABCDEFGHJKLMNPQRSTUVWXYZ" ~
                              "abcdefghijkmnopqrstuvwxyz";
   static assert(symbols.length == 58);

   auto result = new typeof(return)(34);
   foreach_reverse (ref ri; result) {
       uint c = 0;
       foreach (ref ai; a) {
           immutable d = (c % symbols.length) * 256 + ai;
           ai = d / symbols.length;
           c = d;
       }
       ri = symbols[c % symbols.length];
   }

   size_t i = 1;
   for (; i < result.length && result[i] == '1'; i++) {}
   return result[i - 1 .. $];

}

char[] bitcoinEncode(in ref PPoint p) pure nothrow {

   ubyte[typeof(PPoint.x).length + typeof(PPoint.y).length + 1] s;
   s[0] = 4;
   s[1 .. 1 + p.x.length] = p.x[];
   s[1 + p.x.length .. $] = p.y[];

   Address rmd;
   rmd[0] = bitcoinVersion;
   rmd[1 .. RIPEMD160_digest_len + 1] = s.sha.ripemd160Of;
   rmd[$-4 .. $] = rmd[0 .. RIPEMD160_digest_len + 1].sha.sha[0 .. 4];
   return rmd.toBase58;

}

void main() {

   PPoint p = {

cast(typeof(PPoint.x)) x"50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352", cast(typeof(PPoint.y)) x"2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6"};

   p.bitcoinEncode.writeln;

}</lang>

Output:

16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Go

Library: Go sub-repositories

<lang go>package main

import (

   "crypto/sha256"
   "encoding/hex"
   "errors"
   "fmt"

   "code.google.com/p/go.crypto/ripemd160"

)

// Point is a type for a bitcoin public point. type Point struct {

   x, y [32]byte

}

// SetHex takes two hexidecimal strings and decodes them into the receiver. func (p *Point) SetHex(x, y string) error {

   if len(x) != 64 || len(y) != 64 {
       return errors.New("invalid hex string length")
   }
   if _, err := hex.Decode(p.x[:], []byte(x)); err != nil {
       return err
   }
   _, err := hex.Decode(p.y[:], []byte(y))
   return err

}

// A25 type in common with Bitcoin/address validation task. type A25 [25]byte

// doubleSHA256 method in common with Bitcoin/address validation task. func (a *A25) doubleSHA256() []byte {

   h := sha256.New()
   h.Write(a[:21])
   d := h.Sum([]byte{})
   h = sha256.New()
   h.Write(d)
   return h.Sum(d[:0])

}

// UpdateChecksum computes the address checksum on the first 21 bytes and // stores the result in the last 4 bytes. func (a *A25) UpdateChecksum() {

   copy(a[21:], a.doubleSHA256())

}

// SetPoint takes a public point and generates the corresponding address // into the receiver, complete with valid checksum. func (a *A25) SetPoint(p *Point) {

   c := [65]byte{4}
   copy(c[1:], p.x[:])
   copy(c[33:], p.y[:])
   h := sha256.New()
   h.Write(c[:])
   s := h.Sum([]byte{})
   h = ripemd160.New()
   h.Write(s)
   h.Sum(a[1:1])
   a.UpdateChecksum()

}

// Tmpl in common with Bitcoin/address validation task. var tmpl = []byte("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz")

// A58 returns a base58 encoded bitcoin address corresponding to the receiver. // Code adapted from the C solution to this task. func (a *A25) A58() []byte {

   var out [34]byte
   for n := 33; n >= 0; n-- {
       c := 0
       for i := 0; i < 25; i++ {
           c = c*256 + int(a[i])
           a[i] = byte(c / 58)
           c %= 58
       }
       out[n] = tmpl[c]
   }
   i := 1
   for i < 34 && out[i] == '1' {
       i++
   }
   return out[i-1:]

}

func main() {

   // parse hex into point object
   var p Point
   err := p.SetHex(
       "50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352",
       "2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6")
   if err != nil {
       fmt.Println(err)
       return
   }
   // generate address object from point
   var a A25
   a.SetPoint(&p)
   // show base58 representation
   fmt.Println(string(a.A58()))

}</lang>

Output:

16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Perl

Here we'll use the standard Digest::SHA module, and the CPAN-available Crypt::RIPEMD160. <lang perl>use bigint; use Crypt::RIPEMD160; use Digest::SHA qw(sha256); my @b58 = qw{

     1 2 3 4 5 6 7 8 9
   A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
   a b c d e f g h i j k   m n o p q r s t u v w x y z

}; my $b58 = qr/[@{[join , @b58]}]/x;

sub encode { my $_ = shift; $_ < 58 ? $b58[$_] : encode($_/58) . $b58[$_%58] }

sub public_point_to_address {

   my ($x, $y) = @_;
   my @byte;
   for (1 .. 32) { push @byte, $y % 256; $y /= 256 }
   for (1 .. 32) { push @byte, $x % 256; $x /= 256 }
   @byte = (4, reverse @byte);
   my $hash = Crypt::RIPEMD160->hash(sha256 join , map { chr } @byte);
   my $checksum = substr sha256(sha256 chr(0).$hash), 0, 4;
   my $value = 0;
   for ( (chr(0).$hash.$checksum) =~ /./gs ) { $value = $value * 256 + ord }
   (sprintf "%33s", encode $value) =~ y/ /1/r;

}

print public_point_to_address map {hex "0x$_"} ;

__DATA__ 50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6 </lang>

Output:

16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Perl 6

Translation of: Perl

<lang perl6>use SSL::Digest;

constant BASE58 = <

     1 2 3 4 5 6 7 8 9
   A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
   a b c d e f g h i j k   m n o p q r s t u v w x y z

>;

sub encode(Int $n) {

   $n < BASE58 ??
   BASE58[$n]  !!
   encode($n div 58) ~ BASE58[$n % 58]

}

sub public_point_to_address(Int $x is copy, Int $y is copy) {

   my @bytes;
   for 1 .. 32 { push @bytes, $y % 256; $y div= 256 }
   for 1 .. 32 { push @bytes, $x % 256; $x div= 256 }
   my $hash = rmd160 sha256 Blob.new: 4, @bytes.reverse;
   my $checksum = sha256(sha256 Blob.new: 0, $hash.list).subbuf: 0, 4;
   encode reduce * * 256 + * , 0, ($hash, $checksum)».list

}

say public_point_to_address 0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352, 0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6;</lang>

Output:

6UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Ruby

Translate public point to Bitcoin address
Nigel_Galloway
October 12th., 2014

require 'digest/sha2' def convert g

 i,e = ,[]
 (0...g.length/2).each{|n| e[n] = g[n+=n]+g[n+1]; i+='H2'}
 e.pack(i)

end X = '50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352' Y = '2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6' n = '00'+Digest::RMD160.hexdigest(Digest::SHA256.digest(convert('04'+X+Y))) n+= Digest::SHA256.hexdigest(Digest::SHA256.digest(convert(n)))[0,8] G = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" n,res = n.hex, while n > 0 do

 n,ng = n.divmod(58)
 res << G[ng]

end puts res.reverse </lang>

Output:

6UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Tcl

Library: Tcllib (Package: ripemd160)

Library: Tcllib (Package: sha256)

<lang tcl>package require ripemd160 package require sha256

Exactly the algorithm from https://en.bitcoin.it/wiki/Base58Check_encoding

proc base58encode data {

   set digits "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
   for {set zeroes 0} {[string index $data 0] eq "\x00"} {incr zeroes} {

set data [string range $data 1 end]

   }
   binary scan $data "H*" hex
   scan $hex "%llx" num
   for {set out ""} {$num > 0} {set num [expr {$num / 58}]} {

append out [string index $digits [expr {$num % 58}]]

   }
   append out [string repeat [string index $digits 0] $zeroes]
   return [string reverse $out]

}

Encode a Bitcoin address

proc bitcoin_mkaddr {A B} {

   set A [expr {$A & ((1<<256)-1)}]
   set B [expr {$B & ((1<<256)-1)}]
   set bin [binary format "cH*" 4 [format "%064llx%064llx" $A $B]]
   set md [ripemd::ripemd160 [sha2::sha256 -bin $bin]]
   set addr [binary format "ca*" 0 $md]
   set hash [sha2::sha256 -bin [sha2::sha256 -bin $addr]]
   append addr [binary format "a4" [string range $hash 0 3]]
   return [base58encode $addr]

}</lang> Demonstrating <lang tcl>puts [bitcoin_mkaddr \ 0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 \ 0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6]</lang>

Output:

16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

zkl

Uses shared library zklMsgHash. <lang zkl>var MsgHash=Import("zklMsgHash");

const symbols = "123456789" // 58 characters: no cap i,o; ell, zero "ABCDEFGHJKLMNPQRSTUVWXYZ" "abcdefghijkmnopqrstuvwxyz";

fcn base58Encode(bytes){ //Data-->String

  bytes=bytes.copy(); sink:=Sink(String);
  do(33){
     bytes.len().reduce('wrap(n,idx){
        n=n*256 + bytes[idx];
        bytes[idx]=(n/58);
        n%58;
     },0) : symbols[_] : sink.write(_)
  }
  sink.close().reverse();

}

const COIN_VER=0;

fcn coinEncode(x,y){ // throws if x or y not hex or (x+y) not even length

  bytes:=(x+y).pump(Data,Void.Read,fcn(a,b){ (a+b).toInt(16) }).insert(0,4);
  bytes=(MsgHash.SHA256(bytes,1,False):MsgHash.RIPEMD160(_,1,False))

.insert(0,COIN_VER);

  chkSum:=MsgHash.SHA256(bytes,1,False):MsgHash.SHA256(_,1,False)[0,4];
  base58Encode(bytes.append(chkSum));

}</lang> <lang zkl>e:=coinEncode(

  "50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352",
  "2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6");

(e=="16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM").println();</lang>

Output:

True